This is a continuation of the 900-999 thread of the polymath1 project, which is now full.  We’ve made quite a bit of progress so far on our original mission of bounding density Hales-Jewett numbers.  In particular, we have shown

  • c_6=450: Any subset of [3]^6 with 451 points contains a combinatorial line; and there is exactly one example with 450 points with no combinatorial line.  (We have two proofs, one by a large integer program, and the other being purely human-verifiable; the latter can be found here.)
  • c'_5=124: Any subset of [3]^5 with 125 points contains a geometric line; and we have several examples with 124 points with no geometric line.  (The proof is partly computer-assisted; details are here.)
  • 353 \leq c'_6 \leq 361: A genetic algorithm has constructed 353-point solutions in [3]^6 with no geometric line; in the other direction, linear and integer programming methods have shown that any set with 362 points must have a geometric line.
  • \overline{c}^\mu_{12} = 40: In the triangular grid \{(a,b,c) \in {\Bbb N}^3:a+b+c=12\}, any set of 41 points contains an upwards-pointing equilateral triangle (a+r,b,c),(a,b+r,c),(a,b,c+r) with r>0; and we have 40-point examples without such triangles.  This was conducted by an integer program.

This timeline shows the history of these and other developments in the project.

There are still several numbers that look feasible to compute.  For instance, the bounds on c'_6 should be able to be narrowed further.  Work is slowly progressing also on the equal-slices Hales-Jewett numbers c^\mu_n, which are hyper-optimistically conjectured to equal the Fujimura numbers \overline{c}^\mu_n; this has been verified by hand up to n=3 and by integer programming up to n=5.  We are also looking at trying to reduce the dependence on computer assistance in establishing the c'_5 = 124 result; the best human result so far is 124 \leq c'_5 \leq 125.

Some progress has recently been made on some other related questions.  For instance, we now have a precise description of the lower bound on c_n coming from the Behrend-Elkin construction, namely

c_n > C 3^{n - 4\sqrt{\log 2}\sqrt{\log n}+\frac 12 \log \log n}

for some absolute constant c.

Also, it is probably a good time to transport some of the discussion in earlier threads to the wiki and make it easier for outsiders to catch up.  (Incidentally, we need a logo for that wiki; any suggestions would be welcome!)

Comments on this thread should be numbered starting at 1100.