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 »