DHJ(3)

The k=3 Density Hales-Jewett theorem (DHJ(3)) has many equivalent forms.

Versions of DHJ(3)

Let [math]\displaystyle{ [3]^n }[/math] be the set of all length [math]\displaystyle{ n }[/math] strings over the alphabet [math]\displaystyle{ 1, 2, 3 }[/math]. A subset of [math]\displaystyle{ [3]^n }[/math] is said to be line-free if it contains no combinatorial lines. Let [math]\displaystyle{ c_n }[/math] be the size of the largest line-free subset of [math]\displaystyle{ [3]^n }[/math].

DHJ(3), Version 1. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that every subset [math]\displaystyle{ A \subset [3]^n }[/math] of density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line.

DHJ(3), Version 2. [math]\displaystyle{ \lim_{n \rightarrow \infty} c_n/3^n = 0 }[/math].

(The equivalence of Version 1 and Version 2 is clear.)

DHJ(3), Version 3. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that every subset [math]\displaystyle{ A \subset [3]^n }[/math] of equal-slices density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line.

(For the proof that Version 3 and Version 1 are equivalent, see this page.)

DHJ(3), Version 4. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that every collection of pairs (U,V) of disjoint subsets of [n] of cardinality at least [math]\displaystyle{ \delta 3^n }[/math] contains a "corner" [math]\displaystyle{ (U,V), (U \cup D, V), (U, V \cup D) }[/math], where U, V, D are disjoint subsets of [math]\displaystyle{ [n] }[/math] (compare with the corners theorem).

(The equivalence of Version 1 and Version 2 follows by identifying a string [math]\displaystyle{ x \in [3]^n }[/math] with the pair (U,V) consisting of the 1-set and 2-set of x.)

DHJ(3), Version 5. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that if [math]\displaystyle{ (B_w)_{w \in [3]^n} }[/math] are a collection of Bernoulli (i.e. 01-valued) random variables [math]\displaystyle{ B_w }[/math] (not necessarily independent), each with probability at least [math]\displaystyle{ \delta }[/math], then there exists a combinatorial line [math]\displaystyle{ w^1,w^2,w^3 }[/math] such that [math]\displaystyle{ B_{w^0} \wedge B_{w^1} \wedge B_{w^2} }[/math] has positive probability.

(The implication of Version 5 from Version 1 follows from the first moment method, observing that the set [math]\displaystyle{ A := \{ w \in [3]^n: B_w \hbox{ holds} \} }[/math] has expected density at least [math]\displaystyle{ \delta }[/math]. The reverse implication comes from a random sampling method, taking a random m-dimensional combinatorial subspace of [math]\displaystyle{ [3]^n }[/math] and letting [math]\displaystyle{ B_w }[/math] be the event that the image of [math]\displaystyle{ w\in [3]^m }[/math] under the subspace embedding map lies in A.)

DHJ(3), Version 6. If the free group [math]\displaystyle{ F_3 }[/math] on three generators acts in a measure-preserving fashion [math]\displaystyle{ (T_w: X \to X)_{w \in F_3} }[/math] on a probability space X, and E is a set of positive measure in X, then there exists a combinatorial line [math]\displaystyle{ w^1,w^2,w^3 }[/math] such that [math]\displaystyle{ T_{w^1}^{-1}(E) \cap T_{w^2}^{-1}(E) \cap T_{w^3}^{-1}(E) }[/math] has positive measure (where we identify words with elements of [math]\displaystyle{ F_3 }[/math]).

(The equivalence of Version 1 and Version 6 follows from a variant of the Furstenberg correspondence principle.)

Variants

DHJ(k)

One can of course define DHJ(k) for any positive integer k by a similar method. DHJ(1) is trivial, and DHJ(2) follows quickly from Sperner's theorem.

DHJ(1,3)

The following variant of DHJ(3) is motivated by the proof of Sperner's theorem. Let [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] be collections of subsets of [math]\displaystyle{ [n]. }[/math] Define [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}) }[/math] to be the set of all triples [math]\displaystyle{ (U,V,W), }[/math] where [math]\displaystyle{ U,V,W }[/math] are disjoint, and [math]\displaystyle{ U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}. }[/math] These triples are in an obvious one-to-one correspondence with elements of [math]\displaystyle{ [3]^n. }[/math]

Call [math]\displaystyle{ \mathcal{A} }[/math] a set of complexity 1 if it is of the form [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}) }[/math]. For instance, a slice [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is of complexity 1. </math> DHJ(1,3) is the assertion that every dense set of complexity 1 contains a combinatorial line. Here is a proof of this assertion if we assume that [math]\displaystyle{ \mathcal{W}=[2]^n }[/math] and we interpret "dense" to mean "dense in the equal-slices measure".

First, choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math]. Without loss of generality it is the identity. Then the expected number of disjoint quadruples [math]\displaystyle{ (U,V,W) }[/math] such that U is an initial segment, W is a final segment, and U, V and W are elements of [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] that partition [math]\displaystyle{ [n] }[/math] is approximately [math]\displaystyle{ \delta n^2/2 }[/math], where [math]\displaystyle{ \delta }[/math] is the equal-slices density of [math]\displaystyle{ \mathcal{A} }[/math]. (The total number of such triples if U, V and W don't have to belong to [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] is roughly [math]\displaystyle{ n^2/2.) }[/math] Therefore, there must exist some fixed set [math]\displaystyle{ W\in\mathcal{W} }[/math] such that the number of such triples [math]\displaystyle{ (U,V,W) }[/math] is at least [math]\displaystyle{ \delta n/2. }[/math] In particular, we can find two such triples [math]\displaystyle{ (U_1,V_1,W) }[/math] and [math]\displaystyle{ (U_2,V_2,W). }[/math] If [math]\displaystyle{ U_1\subset U_2, }[/math] then this gives us the combinatorial line [math]\displaystyle{ (U_1,V_1,W),(U_2,V_2,W),(U_1,V_2,W\cup(U_2\cap V_1)). }[/math]

Quite possibly a proof of this kind can be devised that proves the full statement DHJ(1,3).

DHJ(j,k)

The statement DHJ(j,k) is motivated by concepts connected with hypergraphs. A k-uniform hypergraph [math]\displaystyle{ H }[/math] could be said to have complexity j if there exists a j-uniform hypergraph [math]\displaystyle{ J }[/math] such that [math]\displaystyle{ H }[/math] consists of all sets A of size k with the property that every subset [math]\displaystyle{ B\subset A }[/math] of size j belongs to [math]\displaystyle{ J. }[/math]

There is also a k-partite version of this definition. If the k vertex sets are all copies of [math]\displaystyle{ [n] }[/math], then we say that K has complexity j if for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] there is a j-uniform hypergraph [math]\displaystyle{ J_E }[/math] such that [math]\displaystyle{ K }[/math] consists of all k-tuples [math]\displaystyle{ (i_1,\dots,i_k) }[/math] such that for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] of size j the j-tuple [math]\displaystyle{ (i_s:s\in E) }[/math] belongs to [math]\displaystyle{ J_E. }[/math]

We can make a similar definition for sequences in [math]\displaystyle{ [k]^n }[/math], or equivalently ordered partitions [math]\displaystyle{ (U_1,\dots,U_k) }[/math] of [math]\displaystyle{ [n]. }[/math] This time we say that [math]\displaystyle{ \mathcal{A} }[/math] has complexity j if there are collections of sets [math]\displaystyle{ \mathcal{U}_E }[/math] such that [math]\displaystyle{ \mathcal{A} }[/math] consists of all ordered partitions [math]\displaystyle{ (U_1,\dots,U_k) }[/math] such that for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] of size j the ordered sequence of disjoint sets [math]\displaystyle{ (U_s:s\in E) }[/math] belongs to [math]\displaystyle{ \mathcal{U}_E. }[/math] For instance, the slice [math]\displaystyle{ \Gamma_{a,b,c} }[/math] has complexity 1.

DHJ(j,k) is the assertion that a subset of [math]\displaystyle{ [k]^n }[/math] of complexity j and density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line, if n is sufficiently large depending on [math]\displaystyle{ j,k,\delta }[/math]. It is not hard to check that DHJ(k-1,k) is the same as DHJ(j,k). In other words, every subset of [math]\displaystyle{ [k]^n }[/math] has complexity at most k-1.

DHJ(2.5)

DHJ(2.5) is the statement that if [math]\displaystyle{ A \subset [3]^n }[/math] has density [math]\displaystyle{ \delta }[/math], and n is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then there exists a combinatorial line [math]\displaystyle{ w^0, w^1, w^2 }[/math] whose first two elements lie in A. This is of course weaker than DHJ(3), which requires that all three elements of the combinatorial line lie in A.

DHJ(2.5) can be deduced from DHJ(2) by partitioning [math]\displaystyle{ [3]^n }[/math] into disjoint copies of [math]\displaystyle{ [2]^m }[/math] for various values of m; indeed, for each set [math]\displaystyle{ C \subset [n] }[/math] of cardinality n-m, we have a copy of [math]\displaystyle{ [2]^m }[/math] inside [math]\displaystyle{ [3]^n }[/math] formed by considering all the strings which equal 2 at C and equal 0 or 1 elsewhere. By Sperner's theorem or DHJ(2), any of the copies of [math]\displaystyle{ [2]^m }[/math] at which A has density at least [math]\displaystyle{ \delta/2 }[/math] (say) will contain the first two points of a combinatorial line, if m is sufficiently large depending on [math]\displaystyle{ \delta }[/math]. The remaining values of m only fill up a negligible portion of the cube [math]\displaystyle{ [3]^n }[/math], and the claim follows.

DHJ(2.6)

DHJ(2.6) is the statement that if [math]\displaystyle{ A \subset [3]^n }[/math] has density [math]\displaystyle{ \delta }[/math], and n is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then there exists r such that for each ij=01,12,20, there exists a combinatorial line [math]\displaystyle{ w^0, w^1, w^2 }[/math] with r wildcards whose i and j elements in A. This is of course weaker than DHJ(3), but implies DHJ(2.5).

Proofs of DHJ(2.6) and further discussion can be found here.

"Upside-down" DHJ(3)

A corner in the grid can either be the right way up (if [math]\displaystyle{ d\gt 0 }[/math] so that the right angle is at the bottom left) or upside-down (if [math]\displaystyle{ d\lt 0 }[/math] so that the right angle is at the top right). However, if you take a combinatorial line in [math]\displaystyle{ [3]^n }[/math] and use it to define a corner by associating with each point x in the combinatorial line the pair (number of 1s in x, number of 2s in x) you always get corners that are the right way up. Is there a version of the density Hales-Jewett theorem that allows upside-down corners as well? It turns out that such a version can be devised, and one can even define an analogue of the theorem that every dense subset of [math]\displaystyle{ [n]^2 }[/math] contains a square.

To do the second of these first, we define a square to be a quadruple of the form [math]\displaystyle{ (A,B),(A\cup D,B),(A,B\cup D),(A\cup D,B\cup D), }[/math] where A and B are allowed to intersect, but D must be disjoint from both A and B. Then an upside-down corner is a square without the bottom left vertex (A,B). It can also be described as a triple [math]\displaystyle{ (A,B), (A\setminus D,B), (A,B\setminus D) }[/math] with [math]\displaystyle{ D\subset A\cap B. }[/math]

To prove that every dense subset of [math]\displaystyle{ [2]^n\times[2]^n }[/math] contains an upside-down corner or a square is a very different problem from DHJ(3) because the sets are allowed to intersect. (It is essential to allow them to intersect because of the pair [math]\displaystyle{ (A\cup D,B\cup D). }[/math] However, it is much closer to the IP-Szemerédi theorem. It can also be brought closer to DHJ(3) if one uses something like equal-slices measure. To choose a random point in [math]\displaystyle{ [2]^n\times[2]^n, }[/math] first choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] and then choose a random pair of intervals in [math]\displaystyle{ \pi([n]). }[/math] Note that if we pick a random pair (A,B) according to this distribution then A and B are identically distributed but far from independent---they are much more likely to be disjoint than a random pair of sets, or even a random pair of sets of the same cardinality. One can place the following measure on the set of squares. Choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] and then choose three random subintervals A, B and D in [math]\displaystyle{ \pi([n]). }[/math] If [math]\displaystyle{ D }[/math] is disjoint from [math]\displaystyle{ A\cup B }[/math] then define the corresponding square. One could hope that, according to this measure, a dense subset of [math]\displaystyle{ [2]^n\times[2]^n }[/math] contains a dense set of squares.

(I have not thought for long enough about this problem to be sure that it is a sensible one.)

Moser(3)

Moser(3) is the claim that [math]\displaystyle{ c'_n = o(3^n) }[/math], where [math]\displaystyle{ c'_n }[/math] is the size of the largest Moser set in [math]\displaystyle{ [3]^n }[/math]. This is implied by DHJ(3) and implies Roth's theorem. No combinatorial proof of Moser(3) is currently known, and no effective decay rate for [math]\displaystyle{ c'_n }[/math] is known either.

Strong Roth in [math]\displaystyle{ \mathbb{F}_3^n }[/math]

The usual form of Roth's theorem in [math]\displaystyle{ \mathbb{F}_3^n }[/math] is that every dense subset of [math]\displaystyle{ \mathbb{F}_3^n }[/math] contains an algebraic line, that is, a set of the form [math]\displaystyle{ (x,x+d,x+2d) }[/math] with [math]\displaystyle{ d\ne 0, }[/math] where x and d are elements of [math]\displaystyle{ \mathbb{F}_3^n }[/math] and addition is pointwise mod 3.

A problem that is intermediate between this and DHJ(3) is the following. Given a dense subset of [math]\displaystyle{ \mathbb{F}_3^n, }[/math] is it always possible to find a triple inside it of the form [math]\displaystyle{ (x,x+d,x+2d) }[/math] with [math]\displaystyle{ d\ne 0, }[/math] where now we insist that all the coordinates of d are either 0 or 1? Obviously this is a strengthening of Roth's theorem in [math]\displaystyle{ \mathbb{F}_3^n. }[/math] It is also a weakening of DHJ(3), since with DHJ(3) one adds the extra condition that the supports of x and d are disjoint.

Strong Roth in [math]\displaystyle{ \mathbb{F}_3^n }[/math]

The usual form of Roth's theorem in [math]\displaystyle{ \mathbb{F}_3^n }[/math] is that every dense subset of [math]\displaystyle{ \mathbb{F}_3^n }[/math] contains an algebraic line, that is, a set of the form [math]\displaystyle{ (x,x+d,x+2d) }[/math] with [math]\displaystyle{ d\ne 0, }[/math] where x and d are elements of [math]\displaystyle{ \mathbb{F}_3^n }[/math] and addition is pointwise mod 3.

A problem that is intermediate between this and DHJ(3) is the following. Given a dense subset of [math]\displaystyle{ \mathbb{F}_3^n, }[/math] is it always possible to find a triple inside it of the form [math]\displaystyle{ (x,x+d,x+2d) }[/math] with [math]\displaystyle{ d\ne 0, }[/math] where now we insist that all the coordinates of d are either 0 or 1? Obviously this is a strengthening of Roth's theorem in [math]\displaystyle{ \mathbb{F}_3^n. }[/math] It is also a weakening of DHJ(3), since with DHJ(3) one adds the extra condition that the supports of x and d are disjoint.

Consequences

DHJ(3) implies the IP-Szemerédi theorem, which implies the corners theorem (in both [math]\displaystyle{ {\Bbb Z}/N{\Bbb Z} }[/math] and [math]\displaystyle{ [3]^n }[/math]), which in turn implies Roth's theorem (in both [math]\displaystyle{ {\Bbb Z}/N{\Bbb Z} }[/math] and [math]\displaystyle{ [3]^n }[/math]).

DHJ(3) also implies the k=3 version of the coloring Hales-Jewett theorem.