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 
![[3]^n](https://s0.wp.com/latex.php?latex=%5B3%5D%5En&bg=ffffff&fg=545454&s=0&c=20201002)
We also establish the asymptotic lower bounds
and
In contrast, the best known upper bound to these quantities is 
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.
What's new 
7 comments
Comments feed for this article
4 February, 2010 at 6:19 pm
Ryan O'Donnell
It 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
Michael
A huge thanks to Terry for getting this paper into shape
12 February, 2010 at 12:56 pm
obryant
I 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 Tao
Hmm, 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
obryant
I 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 Naslund
I 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 Naslund
I 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$)