Tidy problem page

There is already a page devoted to unsolved problems related to the polymath1 project. This page is intended as a more polished page for unsolved problems. Contributions are welcome: they should be problems that are formulated precisely enough for others to think about without having to worry about what they mean. Additional commentary about the problems is also very useful. Also, it would be good if this page were reasonably organized: if you want to add a problem then try to put it near other related problems, and if there are two or three problems that could fit under a general heading, then add such a heading, and so on.

What is the correct one-dimensional generalization of Sperner's theorem?

As has been observed several times, if you apply the density Hales-Jewett theorem to sets [math]\displaystyle{ A }[/math] of sequences such that whether or not [math]\displaystyle{ x }[/math] belongs to [math]\displaystyle{ A }[/math] depends only on the number of 1s, 2s and 3s in [math]\displaystyle{ x }[/math], then you can easily deduce the corners theorem: that a dense subset of [math]\displaystyle{ [n]^2 }[/math] contains a triple of the form [math]\displaystyle{ (x,y),(x+d,y),(x,y+d) }[/math]. If you try the same thing with Sperner's theorem, you deduce the trivial one-dimensional result that a dense subset of [math]\displaystyle{ [n] }[/math] contains a pair of the form [math]\displaystyle{ (x),(x+d) }[/math]. (I have written these as "ordered singletons" to make the analogy clearer.) This is Szemerédi's theorem for arithmetic progressions of length 2.

Now the corners result is a natural generalization of Szemerédi's theorem for progressions of length 2, but so is Szemerédi's theorem itself. So a natural question (with potential applications to the project) arises:

• What generalization of Sperner's theorem relates to Sperner's theorem itself in the way that the general case of Szemerédi's theorem relates to the trivial case of progressions of length 2?

One theorem that does the job is the following: let [math]\displaystyle{ \mathcal{A} }[/math] be a subset of [math]\displaystyle{ [2]^n }[/math] such that the average density of [math]\displaystyle{ \mathcal{A} }[/math] in each slice of [math]\displaystyle{ [2]^n }[/math] is at least [math]\displaystyle{ \delta }[/math]. Then there are disjoint sets [math]\displaystyle{ A,D_1,\dots,D_k }[/math] all of the same size such that [math]\displaystyle{ A\cup D_1\cup\dots\cup D_j }[/math] belongs to [math]\displaystyle{ \mathcal{A} }[/math] for every [math]\displaystyle{ 0\leq j\leq k }[/math].

Proof: Pick a random permutation of [math]\displaystyle{ [n] }[/math]. Then on average there will be [math]\displaystyle{ \delta n }[/math] initial segments of the permuted set that belong to [math]\displaystyle{ \mathcal{A} }[/math]. By Szemerédi's theorem we can find an arithmetic progression of these of length [math]\displaystyle{ k }[/math].

There is one aspect of this statement that seems a bit artificial, which is the assumption that the [math]\displaystyle{ D_j }[/math] all have the same cardinality.

• Is it possible to justify this as a natural assumption (e.g. by showing that the theorem is useful)?

• Is there a more set-theoretic generalization of the statement?

• Can one find not just the sets of the form [math]\displaystyle{ A\cup D_1\cup\dots\cup D_j }[/math] but all sets of the form [math]\displaystyle{ A\cup\bigcup_{j\in S}D_j }[/math]?

Closely related to this last question is the same question but without the requirement that the [math]\displaystyle{ D_i }[/math] have the same cardinality:

• If [math]\displaystyle{ \mathcal{A} }[/math] is dense (either in the uniform probability measure on [math]\displaystyle{ [2]^n }[/math] or in the equal-slices measure) then must there exist disjoint sets [math]\displaystyle{ A,D_1\dots,D_k }[/math] such that [math]\displaystyle{ A\cup\bigcup_{j\in S}D_j\in\mathcal{A} }[/math] for every [math]\displaystyle{ S\subset\{1,2,\dots,k\} }[/math]?

It is possible to deduce a positive answer to this last question by using DHJ([math]\displaystyle{ 2^k }[/math]) and considering binary expansions of numbers in [math]\displaystyle{ [2^k] }[/math]. This gives sets [math]\displaystyle{ D_i }[/math] of the same cardinality. Is there a more elementary argument, either for this assertion if you are allowed to use Szemerédi's theorem, or for the assertion with sets of differing cardinalities if you are not?

How difficult is DHJ(j,k)?

One might expect that proving DHJ(j,k) is about as difficult as proving DHJ(j+1). But is this the case? In particular, is there a reasonably simple Sperner-style proof of DHJ(1,3)? (There is at least a proof of a fairly general case of this theorem, but it would be good to prove the whole thing in an elementary way.) If you are allowed to use DHJ(j+1) as a black box, can you give a combinatorial proof of DHJ(j,k) for all k?

Added later: it seems that we now know how to solve this problem, and that the answer is yes, but it remains to be completely checked.

For example, every set of complexity 1 in [math]\displaystyle{ [3]^n }[/math] is an intersection of a 1-set, a 2-set and a 3-set. With the help of Sperner's theorem we now know how to partition almost all of a 1-set into subspaces, then take the intersection of those subspaces with the 2-set, partition almost all of those intersections into subspaces, intersect those with the 3-set, and partition almost all of those into subspaces.

Hyper-optimistic conjectures

Full article: Hyper-optimistic conjecture

The proof of Sperner's theorem yields the following stronger result.

Theorem. If [math]\displaystyle{ \mathcal{A}\subset[2]^n }[/math] has equal-slices density greater than [math]\displaystyle{ 1/(n+1) }[/math] then [math]\displaystyle{ \mathcal{A} }[/math] contains two distinct sets A and B with [math]\displaystyle{ A\subset B. }[/math]

The proof makes use of the following trivial fact: if [math]\displaystyle{ A\subset\{0,1,\dots,n\} }[/math] has density greater than [math]\displaystyle{ 1/(n+1) }[/math] then A contains two distinct numbers x and y with [math]\displaystyle{ x\lt y. }[/math]

The trivial fact can be generalized to the corners theorem. For each n, let [math]\displaystyle{ \delta_n }[/math] be the minimal density needed to guarantee a corner. By analogy with the above two results, one might be "hyper-optimistic" and hope for the following to be true. (However, there is no good evidence for the conjecture that is to follow.)

Conjecture. If [math]\displaystyle{ \mathcal{A}\subset[3]^n }[/math] has equal-slices density greater than [math]\displaystyle{ \delta_n }[/math] then [math]\displaystyle{ \mathcal{A} }[/math] contains a combinatorial line.

Influence and obstructions in Sperner's theorem

Define an "equal-slices" density on pairs [math]\displaystyle{ A\subset B }[/math] of subsets of [math]\displaystyle{ [n] }[/math] as follows: to choose a random such pair, let [math]\displaystyle{ \pi }[/math] be a random permutation of [math]\displaystyle{ [n] }[/math], let r and s be a random pair of integers with [math]\displaystyle{ 0\leq r\lt s\leq n }[/math] and let [math]\displaystyle{ A=\{\pi(1),\dots,\pi(r)\} }[/math] and [math]\displaystyle{ B=\{\pi(1),\dots,\pi(s)\}. }[/math]

Let [math]\displaystyle{ \mathcal{A}\subset[2]^n }[/math] be a set of density [math]\displaystyle{ \delta }[/math] in the equal-slices measure. If [math]\displaystyle{ \mathcal{A}\subset[2]^n }[/math] is a random set, then we expect that the density of the set of pairs [math]\displaystyle{ A\subset B }[/math] such that [math]\displaystyle{ A,B\in\mathcal{A} }[/math] will be close to [math]\displaystyle{ \delta^2. }[/math] If it differs from [math]\displaystyle{ \delta^2 }[/math] by some constant [math]\displaystyle{ \eta, }[/math] then what can we say about [math]\displaystyle{ \mathcal{A} }[/math]?

A major source of examples is monotone sets, that is, sets [math]\displaystyle{ \mathcal{A} }[/math] such that if [math]\displaystyle{ A\in\mathcal{A} }[/math] and [math]\displaystyle{ A\subset B }[/math] then [math]\displaystyle{ B\in\mathcal{A}. }[/math] If we choose a monotone set that contains a significant fraction of one layer and misses a significant fraction of a much higher layer then when we choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n], }[/math] then the first initial segment that belongs to [math]\displaystyle{ \mathcal{A} }[/math] comes at a point with significant variance. An example of such a monotone set is the set of all sets that contain the element 1. It seems possible that for monotone sets that work there will always be a variable with high influence.

Moser's cube problem

Full article: Moser's cube problem

Let [math]\displaystyle{ c'_n }[/math] be the size of the largest subset of [math]\displaystyle{ [3]^n }[/math] which does not contain a geometric line. As a consequence of DHJ(3), we know that [math]\displaystyle{ c'_n = o(3^n) }[/math]. Open question: is there a combinatorial proof (and/or an effective bound) of this result?

Strong Roth theorem

An equivalent formulation of the strong Roth theorem can be found here.

Let’s say that a vector in [math]\displaystyle{ \mathbb{F}_3^r }[/math] is simple if either 1, or 2 does not appear among its coordinates; say, (1,0,0,1,0) and (2,2,2,0,2) are simple vectors, while (1,2,1,1,1) is not. Furthermore, call a three-term progression in [math]\displaystyle{ \mathbb{F}_3^r }[/math] simple if its difference is simple. Thus, a simple progression is a triple a,b,c of distinct elements of [math]\displaystyle{ \mathbb{F}_3^r }[/math] with a+b+c=0 and a-b,b-c,c-a all simple. The DHJ(3) implies that any positive density subset of [math]\displaystyle{ \mathbb{F}_3^r }[/math] contains a simple progression. Is there any combinatorial or Fourier-theoretic proof of this fact?

Notice that by the integer Roth theorem, any set [math]\displaystyle{ A\subseteq[N] }[/math] of positive density contains a three-term progression with the difference, say, at most [math]\displaystyle{ N^{0.1} }[/math]; however, the corresponding argument does not seem to extend onto simple progressions in [math]\displaystyle{ \mathbb{F}_3^r. }[/math]

The question has some formal similarities with results such as Roth's theorem in which the step of the progression is restricted to be square. Such questions are within the reach of (quadratic) Fourier analysis and so one may hope that the same is true here.