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* , defined as the largest subset of the n-dimensional cube containing no combinatorial line, as well as the related Moser numbers , 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 was the hardest and required a non-trivial amount of computer assistance.

We also establish the asymptotic lower bounds

and

.

In contrast, the best known upper bound to these quantities is , 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.

### Like this:

Like Loading...

## 7 comments

Comments feed for this article

4 February, 2010 at 6:19 pm

Ryan O'DonnellIt hardly matters since it’s on a log*, but… for the upper bounds, the power of 1/3 can be 1/2.

6 February, 2010 at 5:16 pm

MichaelA huge thanks to Terry for getting this paper into shape

12 February, 2010 at 12:56 pm

obryantI remember this being discussed, but I don’t recall if there was a decision as to whether to include a statement along the lines of: “participants were supported by grants from the National Science Foundation, the Research Foundation of CUNY, et cetera.”

12 February, 2010 at 4:45 pm

Terence TaoHmm, interesting question. We are not identifying individual authors in the current text (there would be a question of where does one draw the line – is supplying a single comment, for instance, sufficient to be considered an author?) so there does not appear to be any simple way to display individual grant information. One could instead display aggregate grant information, as you suggest, but this information may not have much content (again, what if a grantee only contributed a single comment to the project?).

One possibility would be to set up an “About the participants” page on the wiki page for this project, where everyone who was inclined could put some brief data to this effect on the page.

18 February, 2010 at 8:51 am

obryantI never thought of the grant information as being content. As far as I know, its only purpose is to make it easier for agencies to defend to their budgets to legislators. Do you think the grant info influences readers, or perhaps referees? I can see that happening: “well, I don’t have time to write this report, but the gal’s got NSF funding, so it’s probably alright.”

18 March, 2023 at 11:51 am

Eric NaslundI am curious whether a related concept has been considered. Let $c_{n,m,3}$ denote the largest subset of $\{1,2,…,m\}^n$ that does not contain $3$ elements $x,y,z$ such that for all $i$, either $x_i=y_i=z_i$ or $z_i-y_i=y_i-x_i=1$. Let $c_{n,m,3}’$ denote the largest subset of $\{1,2,…,m\}^n$ that does not contain $3$ elements $x,y,z$ such that for all $i$, either $x_i=y_i=z_i$ or $z_i-y_i=y_i-x_i=1$ or $z_i-y_i=y_i-x_i=-1$. Similarly define $c_{n,m,k}$ and $c_{n,m,k}’$ for $m\geq k\geq 3$ for sets with $k$ such elements.

Then $c_{n,k,k}$ and $c_{n,k,k}’$ are the counts for combinatorial lines and geometric lines, respectively, mentioned in the paper and the blog post. The methods of the paper apply equally for $m>k$.

Let’s define the following slight modification: Let $t_{n,m,3}$ ($t$ for torus) denote the largest subset of $\{1,2,…,m\}^n$ that does not contain $3$ elements $x,y,z$ such that for all $i$, either $x_i=y_i=z_i$ or $z_i-y_i \equiv y_i-x_i \equiv 1\pmod{m}$. Let $t_{n,m,3}’$ denote the largest subset of $\{1,2,…,m\}^n$ that does not contain $3$ elements $x,y,z$ such that for all $i$, they are all equal, or $z_i-y_i \equiv y_i-x_i \equiv 1\pmod{m}$ or $z_i-y_i \equiv y_i-x_i \equiv -1\pmod{m}$ (and similarly define $t_{n,m,k}$ and $t_{n,m,k}’$ for $m>=k>3$).

Is anything known about the correct size, up to sub-exponential factors, for any $t_{n,m,k}$ for any parameters other than $t_{n,3,3}’$ which is the capset problem? Has anyone written about this problem before?

In other words, is it known whether or not $$\lim_{n\rightarrow \infty} (t_{n,m,k})^{1/n} = m$$ for any parameters $m,k$?

Is it known whether or not

$$\lim_{n\rightarrow \infty} (t_{n,m,k}’)^{1/n} = m$$

for any parameters $m,k$ other than $m=k=3$?

18 March, 2023 at 11:58 am

Eric NaslundI can add – using the methods of [Tao and Sawin](https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/) I can show that the slice-rank method cannot yield exponential upper bounds for $t_{n,m,k}$ for $k\geq 3,m\geq 3$, and cannot yield exponential upper bounds for $t_{n,m,k}’$ for $k\geq 4,m\geq 5$.

I was very curious if these problems have been considered before in the literature. ($t_{n,3,3}$ corresponds to $3$-APs with difference in ${0,1}^n$)