You are currently browsing the tag archive for the ‘density Hales-Jewett’ tag.

This is a continuation of the 700-799 thread of the polymath1 project, which is now full.  During the course of that thread, we have made significant progress on the three problems being focused on:

1.  Upper and lower bounds for $c_n$ for small n.

Let $c_n$ be the largest size of a set in $[3]^n$ without a combinatorial line.   We now have both human and computer-assisted proofs of the first few values of this sequence:

$c_0=1; c_1=2; c_2=6; c_3=18; c_4=52; c_5 = 150; c_6 = 450$.

The current best-known bounds for $c_7$ are $1302 \leq c_7 \leq 1348$.  Given the gap involved here, and the rate at which the complexity of the problem has increased with n, it seems unlikely that we will be able to compute $c_7$ exactly any time soon, but it is possible that some improvement can still be made here.

2. A hyper-optimistic conjecture

Consider a variant of the above problem in which each element of $[3]^n$ with a 1s, b 2s, and c 3s is weighted by the factor $\frac{a! b! c!}{n!}$; this gives $[3]^n$ a total weight of $\frac{(n+1)(n+2)}{2}$. Let $c^\mu_n$ be the largest weight of a line-free set of $[3]^n$, and let $\overline{c}^\mu_n$ be the largest size of a subset of

$\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}$

which contains no upward-pointing equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with r>0. It is known that $c^\mu_n \geq \overline{c}^\mu_n$; the “hyper-optimistic conjecture” is that one in fact has $c^\mu_n = \overline{c}^\mu_n$. This would imply density Hales-Jewett for k=3.

Currently, the conjecture is verified for $n \leq 5$, where the values of $c^\mu_n = \overline{c}^\mu_n$ for $n=0,1,2,3,4,5$ are 1,2,4,6,9,12 respectively; see this page and this page for details.  It seems feasible to handle $n=6$.  Currently we know that $15 \leq \overline{c}^\mu_6 \leq 17$ and $\overline{c}^\mu_6 \leq c^\mu_6 \leq 28$.

3.  Asymptotics for Moser’s cube problem

Moser’s cube problem asks to compute the largest size $c'_n$ of a subset of the cube $[3]^n$ without geometric lines.  The first few values of $c'_n$ are known:

$c'_0=1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43$.

The best asymptotic lower bound known is still of the order of $3^n/\sqrt{n}$.  Improving this bound seems related to the well-known problem of improving the bounds in Behrend’s construction of an AP-3 free set of integers.

We are quite close now to pinning down $c'_5$; we know that it is equal to either 124 or 125, and it is looking increasingly unlikely that it is 125.

Comments on this thread should start at 900.

In this lecture, we describe the simple but fundamental Furstenberg correspondence principle which connects the “soft analysis” subject of ergodic theory (in particular, recurrence theorems) with the “hard analysis” subject of combinatorial number theory (or more generally with results of “density Ramsey theory” type). Rather than try to set up the most general and abstract version of this principle, we shall instead study the canonical example of this principle in action, namely the equating of the Furstenberg multiple recurrence theorem with Szemerédi’s theorem on arithmetic progressions.
Read the rest of this entry »