Monochromatic Hilbert cubes and arithmetic progressions

Additive Combinatorics, , ,

József Balogh, Misha Lavrov, Adam Wagner, and I recently uploaded our paper “Monochromatic Hilbert cubes and arithmetic progressions” to the arXiv.

Van der Waerden’s theorem is a central question in arithmetic Ramsey theory. The goal is to find bounds for {W(k,r)}, which is the least integer such that any {r}–coloring of {1 , \ldots , W(k,r)} contains a {k}–term arithmetic progression. The current records are of the form

\displaystyle c\cdot r^{k-1} \leq W(k,r) \leq 2^{2^{r^{2^{2^{k+9}}}}}.

The upper bound is due to Gowers, while the lower bound is due to Kozik and Shabanov (see also Blankenship, Cummings, and Taranchuk for the prime case).

A Hilbert cube, or affine {k}–cube, is a subset of the integers of the form

\displaystyle \left\{x_0 + \sum_{b \in B} b : B \subseteq A\right\} =: x_0 + \Sigma^* A,

for some {|A|=k} and {x_0 \in \mathbb{Z}}. Hilbert cubes are an important substructure in arithmetic Ramsey theory, coming up in the Gower’s uniformity norm, the density Hales Jewett theorem, and Szemerédi’s original proof of his theorem. We set {h(k,r)} to be the least integer such that any {r}–coloring of {1 , \ldots , W(k,r)} contains an affine {k}–cube. The current records are of the form

\displaystyle r^{ck^2} \leq h(k,r) \leq O(r)^k.

The lower bound is due to Conlon, Fox, and Sudakov, while the upper bound was originally due to Szemerédi and is the so–called Szemerédi cube lemma. Note that the gap in bounds for Hilbert cubes is much less than the gap in Van der Waerden’s problem.

Improving the upper bound would be of interest, and there are a plethora of proofs for it. For instance, one nice geometric proof can be found in this paper of Graham and Solymosi and a standard averaging can be found in these notes of Zeeuw.

We instead consider improving the lower bound. A first try is to randomly {r}–color the integers {1 ,\ldots , n} and show that with high probability there are no monochromatic affine {k}–cubes. An affine {k}–cube of the form {x_0 + \Sigma^* A} is not monochromatic with probability

\displaystyle \frac{2}{2^{\Sigma A}}.

It turns out if every {A} was disassociated, that is having {|\Sigma^* A| = 2^k}, then we could complete this argument and greatly improved upon the Conlon, Fox, Sudakov bound. The problem is with sets of the form {x_0 + \Sigma^* A}, where {\Sigma^* A} is small. The question is how small. It turns out that {|\Sigma^* A| \geq {k +1 \choose 2}}. To make improvements, we must consider the case {|\Sigma^* A| \leq k^{2 + \delta}}. But then, in light of Littlewood–Offord theory, one might expect {A} to look a lot like an arithmetic progression. Thus {\Sigma^* A} should also be like an arithmetic progression. Thus we are lead back to Van der Waerden’s problem. Our main tools for making this precise are this paper of Nguyen and Vu and this paper of Szemerédi and Vu.

Our main theorem is the following.

Theorem 1: Let {k \geq 3} be an integer. Then for every {\epsilon >0}, there is a {c > 0} such that

\displaystyle h(k,4) \ge \min\{W(\lfloor c k^2 \rfloor, 2), 2^{k^{2.5-\epsilon}}\}.

Theorem 1 asserts that either

  • (i) the best lower bound for {W(k,2)} is far from sharp and {h(k,4)} is larger than the Conlon, Fox, Sudakov bound,
  • (ii) the best lower bound for {W(k,2)} is nearly sharp and so the Hilbert cube number is very close to the Van der Waerden number.

Graham conjectured that {W(k,2)} should be closer to the lower bound as opposed to the tower type upper bound. One dream would be to use this to prove a $1000 conjecture of Graham, by showing a bound of the form {h(k,4) \leq 2^{k^{2.5 - \delta}}}. Needless to say, this is likely hard.

Leave a Reply