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.