I’ve just uploaded the D.H.J. Polymath article “Density Hales-Jewett and Moser numbers” to the arXiv, submitted to the Szemeredi birthday conference proceedings.

This article investigates the Density Hales-Jewett numbers c_{n,3}, defined as the largest subset of the n-dimensional cube [3]^n containing no combinatorial line, as well as the related Moser numbers c'_{n,3}, defined as the largest subset of the n-dimensional cube containing no geometric line.  We compute the first six numbers in each sequence in this paper.  For the DHJ numbers, they are 1,2,6,18,52,150,450 and for the Moser numbers they are 1,2,6,16,43,124,353.  The last two elements of both sequences are new; the computation c'_{6,3}=353 was the hardest and required a non-trivial amount of computer assistance.

We also establish the asymptotic lower bounds

c_{n,3} \geq 3^n \exp( - O(\sqrt{\log n}) )


c'_{n,3} \geq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}.

In contrast, the best known upper bound to these quantities is O(3^n / \log^{1/3}_* n), obtained by the sister project to this Polymath project.

We also show a counterexample to a certain “hyper-optimistic conjecture” which would have generalised the Lubell-Yamamoto–Meshalkin (LYM) inequality to this setting.

Thanks to all the participants for this interesting experiment in collaborative mathematics.  This is certainly a different type of project from the ones I normally am involved in, but I found it to be an enjoyable and educational experience.

There is still some time to make further (minor) corrections; I think the deadline for the final submission should be in April.