Other proposed projects

2011-10-24T21:14:13Z

Squark: Added my quantum cellular automata proposal

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 [http://filters.wikidot.com/ this wiki].

Note that this manuscript contains [http://portonmath.wordpress.com/2009/07/31/complementive-complete-lattice/ 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>{\Bbb R}^N</math> gives rise to a random subset A_V of {1,...,N}, with the probability that <math>A_V = \{i_1,\ldots,i_k\}</math> being the square of the magnitude of the projection of <math>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>A_V</math> to <math>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>A_V, A_W, A_{V+W}</math> together in such a way that <math>A_{V + W} = A_V \cup A_W</math>?

These questions are raised in page 38 of [http://uk.arxiv.org/PS_cache/math/pdf/0204/0204325v4.pdf this paper of Lyons], and also discussed at [http://terrytao.wordpress.com/2009/08/23/determinantal-processes/ this blog post].

== Stable commutator length in the free group ==

Let G be the free group on two generators, and let [G,G] be the commutator subgroup. Given any g in [G,G], the commutator length cl(g) is the least number of commutators needed to express g, and the stable commutator length scl(g) is the lim of cl(g^n)/n.

It is known that scl(g) >= 1/2 for any non-trivial g. Find a combinatorial proof of this fact.

It is conjectured that { scl(g): g in [G,G] } has an isolated point at 1/2. Prove this.

Reference: scl, Danny Calegari

== Quantum cellular automata ==

The proposal is tackling [http://mathoverflow.net/questions/78707/are-all-quantum-cellular-automata-invertible-representable these 2 questions].

Polymath Wiki - User contributions [en]

Other proposed projects