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 measure at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line.

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

Variants

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.

[Discuss DHJ(2.5), DHJ(j,k) here]

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.