Other proposed projects

This page is a repository for any polymath proposals which are not fleshed out enough to have their own separate posts for the proposal. Contributions are welcome.

Beating the trivial subset sum algorithm

This problem was proposed by Ernie Croot, though he would not have the time to run a project based on this problem.

It is a problem that is easy to state, probably will succumb to elementary methods, and probably could be solved if enough people contributed ideas. Here goes: consider the usual subset sum (or is it knapsack?) problem where you are given a list of positive integers N_1, …, N_k, and a target number T, and you must decide whether there is some subset of N_1, …, N_k that sums to T. The problem is to beat the “trivial algorithm”, which I shall describe presently.

The first thing to realize is that there is a subset sum equal to T iff there is one equal to S-T, where S=N_1 + … + N_k. Furthermore, subsets of size t summing to T correspond uniquely to subsets of size k-t summing to S-T. In this way, you only need to consider subsets of size at most k/2 (and check whether they sum of T or S-T) to solve the problem. But now you can use the usual “collision technique” to reduce the problem to subsets of size at most k/4, by forming a table of all subsets of at most this size, along with their sum of elements, until you find a disjoint pair of subsets that sums to either T or S-T. The running time of this procedure should be comparable to (k choose k/4) = c^(k+o(k)), for a certain constant c that is easy to work out. This is what I mean by the “trivial algorithm”. Now, the problem is find an algorithm — any at all — that runs in time at most d^k, where d < c. To my knowledge no such algorithm is know to exist!

Filters on posets and generalizations

I suggest to collaboratively finish writing my draft "Filters on posets and generalizations".

See this wiki.

Note that this manuscript contains this conjecture which can be separated into an other smaller polymath project.

Coupling determinantal processes

Any n-dimensional subspace V of a Euclidean space [math]\displaystyle{ {\Bbb R}^N }[/math] gives rise to a random subset A_V of {1,...,N}, with the probability that [math]\displaystyle{ A_V = \{i_1,\ldots,i_k\} }[/math] being the square of the magnitude of the projection of [math]\displaystyle{ e_{i_1} \wedge \ldots \wedge e_{i_n} }[/math] to V. This is known as the determinantal process associated to V.

If V is a subspace of W, it is known that one can couple [math]\displaystyle{ A_V }[/math] to [math]\displaystyle{ A_W }[/math] in such a way that the former set is a subset of the latter, but no "natural" way of doing this is known. One problem in this project would be to find such a natural way.

A related problem: if V, W are orthogonal, is it always possible to couple [math]\displaystyle{ A_V, A_W, A_{V+W} }[/math] together in such a way that [math]\displaystyle{ A_{V + W} = A_V \cup A_W }[/math]?

These questions are raised in page 38 of this paper of Lyons, and also discussed at this blog post.