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 , which is the least integer such that any –coloring of contains a –term arithmetic progression. The current records are of the form
A Hilbert cube, or affine –cube, is a subset of the integers of the form
for some and . 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 to be the least integer such that any –coloring of contains an affine –cube. The current records are of the form
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 –color the integers and show that with high probability there are no monochromatic affine –cubes. An affine –cube of the form is not monochromatic with probability
It turns out if every was disassociated, that is having , then we could complete this argument and greatly improved upon the Conlon, Fox, Sudakov bound. The problem is with sets of the form , where is small. The question is how small. It turns out that . To make improvements, we must consider the case . But then, in light of Littlewood–Offord theory, one might expect to look a lot like an arithmetic progression. Thus 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 be an integer. Then for every , there is a such that
Theorem 1 asserts that either
- (i) the best lower bound for is far from sharp and is larger than the Conlon, Fox, Sudakov bound,
- (ii) the best lower bound for is nearly sharp and so the Hilbert cube number is very close to the Van der Waerden number.
Graham conjectured that 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 . Needless to say, this is likely hard.