View source for DHJ(3)

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

== Versions of DHJ(3) ==

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

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

'''DHJ(3), Version 2'''. <math>\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>\delta > 0</math> there exists n such that every subset <math>A \subset [3]^n</math> of [[equal-slices density]] at least <math>\delta</math> contains a [[combinatorial line]].

(For the proof that Version 3 and Version 1 are equivalent, see [[equal-slices measure|this page]].)

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

(The equivalence of Version 1 and Version 2 follows by identifying a string <math>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>\delta > 0</math> there exists n such that if <math>(B_w)_{w \in [3]^n}</math> are a collection of Bernoulli (i.e. 01-valued) random variables <math>B_w</math> (not necessarily independent), each with probability at least <math>\delta</math>, then there exists a combinatorial line <math>w^1,w^2,w^3</math> such that <math>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>A := \{ w \in [3]^n: B_w \hbox{ holds} \}</math> has expected density at least <math>\delta</math>.  The reverse implication comes from a random sampling method, taking a random m-dimensional [[combinatorial subspace]] of <math>[3]^n</math> and letting <math>B_w</math> be the event that the image of <math>w\in [3]^m</math> under the subspace embedding map lies in A.)

'''DHJ(3), Version 6'''.  If the free group <math>F_3</math> on three generators acts in a measure-preserving fashion <math>(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>w^1,w^2,w^3</math> such that <math>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>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>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> be collections of subsets of <math>[n].</math> Define <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})</math> to be the set of all triples <math>(U,V,W),</math> where <math>U,V,W</math> are disjoint, and <math>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>[3]^n.</math>

Call <math>\mathcal{A}</math> a ''set of complexity 1'' if it is of the form <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})</math>.  For instance, a [[slice]] <math>\Gamma_{a,b,c}</math> is of complexity 1, as is the collection of all sequences with an even number of 1s in the first $latex n/2$ coordinates and an odd number of 2s in the last $latex n/3$ coordinates. 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>\mathcal{W}=[2]^n</math> and we interpret "dense" to mean "dense in the [[equal-slices measure]]".

First, choose a random permutation <math>\pi</math> of <math>[n]</math>. Without loss of generality it is the identity. Then the expected number of disjoint quadruples <math>(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>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> that partition <math>[n]</math> is approximately <math>\delta n^2/2</math>, where <math>\delta</math> is the equal-slices density of <math>\mathcal{A}</math>. (The total number of such triples if U, V and W don't have to belong to <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> is roughly <math>n^2/2.)</math> Therefore, there must exist some fixed set <math>W\in\mathcal{W}</math> such that the number of such triples <math>(U,V,W)</math> is at least <math>\delta n/2.</math> In particular, we can find two such triples <math>(U_1,V_1,W)</math> and <math>(U_2,V_2,W).</math> If <math>U_1\subset U_2,</math> then this gives us the combinatorial line <math>(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 [http://en.wikipedia.org/wiki/Hypergraph  hypergraphs]. A k-uniform hypergraph <math>H</math> could be said to have ''complexity'' j if there exists a j-uniform hypergraph <math>J</math> such that <math>H</math> consists of all sets A of size k with the property that every subset <math>B\subset A</math> of size j belongs to <math>J.</math> 

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

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

DHJ(j,k) is the assertion that a subset of <math>[k]^n</math> of complexity j and density at least <math>\delta</math> contains a [[combinatorial line]], if n is sufficiently large depending on <math>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>[k]^n</math> has complexity at most k-1.

==== DHJ(2.5) ====

DHJ(2.5) is the statement that if <math>A \subset [3]^n</math> has density <math>\delta</math>, and n is sufficiently large depending on <math>\delta</math>, then there exists a [[combinatorial line]] <math>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>[3]^n</math> into disjoint copies of <math>[2]^m</math> for various values of m; indeed, for each set <math>C \subset [n]</math> of cardinality n-m, we have a copy of <math>[2]^m</math> inside <math>[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>[2]^m</math> at which A has density at least <math>\delta/2</math> (say) will contain the first two points of a combinatorial line, if m is sufficiently large depending on <math>\delta</math>.  The remaining values of m only fill up a negligible portion of the cube <math>[3]^n</math>, and the claim follows.

==== [[DHJ(2.6)]] ====

DHJ(2.6) is the statement that if <math>A \subset [3]^n</math> has density <math>\delta</math>, and n is sufficiently large depending on <math>\delta</math>, then there exists r such that for each ij=01,12,20, there exists a [[combinatorial line]] <math>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 [[DHJ(2.6)|can be found here]].

==== [[DHJ(2.7)]] ====

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

Proofs of DHJ(2.7) and further discussion [[DHJ(2.7)|can be found here]].

===="Upside-down" DHJ(3)====

A [[corner]] in the grid can either be the right way up (if <math>d>0</math> so that the right angle is at the bottom left) or upside-down (if <math>d<0</math> so that the right angle is at the top right). However, if you take a combinatorial line in <math>[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>[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>(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>(A,B), (A\setminus D,B), (A,B\setminus D)</math> with <math>D\subset A\cap B.</math> 

To prove that every dense subset of <math>[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>(A\cup D,B\cup D).</math> However, it is much closer to the [[IP-Szemer&eacute;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>[2]^n\times[2]^n,</math> first choose a random permutation <math>\pi</math> of <math>[n]</math> and then choose a random pair of intervals in <math>\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>\pi</math> of <math>[n]</math> and then choose three random subintervals A, B and D in <math>\pi([n]).</math> If <math>D</math> is disjoint from <math>A\cup B</math> then define the corresponding square. One could hope that, according to this measure, a dense subset of <math>[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>c'_n = o(3^n)</math>, where <math>c'_n</math> is the size of the largest [[Moser set]] in <math>[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>c'_n</math> is known either.



====A strong Roth theorem====

''An equivalent formulation of the strong Roth theorem can be [[tidy_problem_page|found here]].''

The usual form of [[Roth's theorem]] in <math>\mathbb{F}_3^n</math> is that every dense subset of <math>\mathbb{F}_3^n</math> contains an [[algebraic line]], that is, a set of the form <math>(x,x+d,x+2d)</math> with <math>d\ne 0,</math> where x and d are elements of <math>\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>\mathbb{F}_3^n,</math> is it always possible to find a triple inside it of the form <math>(x,x+d,x+2d)</math> with <math>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>\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.

====Multi-wildcard versions====

Let S be a subset of the permutation group <math>S_3={123,132,213,231,312,321}</math>.  We can define an ''S-line'' to be a string of 1, 2, 3s, and wildcards <math>*_\alpha</math> for <math>\alpha \in S</math>, with at least one wildcard appearing in the S-line.  This gives rise to a triple of points, with the first, second, and third points formed by replacing each wildcard <math>*_{abc}</math> with a, b, c respectively.  For instance if S = {123,132}, the S-line

:<math> 3 *_{123} 1 *_{132} *_{123} </math>

gives rise to a triple

:<math> \{ 31111, 32132, 33123 \}</math>.

With this notation,

* A combinatorial line is a {123}-line.
* A geometric line is a {123,321}-line.
* A line for the purposes of the strong Roth theorem is a {123,231,312}-line.
* An algebraic line is a {123,132,213,231,312,321}-line.

Write <math>DHJ_S(3)</math> for the claim that any subset of <math>[3]^n</math> of density at least <math>\delta</math> contains an S-line for n large enough.  Then <math>DHJ_S(3)</math> implies <math>DHJ_{S'}(3)</math> whenever S' contains S.

One can now consider DHJ for various other types of sets S, e.g. {123,132}, which is not isomorphic to any of the previous examples.

== Consequences ==

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

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