Monochromatic Hilbert Cubes and Arithmetic Progressions

Abstract

The Van der Waerden number $W(k,r)$ denotes the smallest $n$ such that whenever $[n]$ is $r$–colored there exists a monochromatic arithmetic progression of length $k$. Similarly, the Hilbert cube number $h(k,r)$ denotes the smallest $n$ such that whenever $[n]$ is $r$–colored there exists a monochromatic affine $k$–cube, that is, a set of the form$$\left\{x_0 + \sum_{b \in B} b : B \subseteq A\right\}$$ for some $|A|=k$ and $x_0 \in \mathbb{Z}$.

We show the following relation between the Hilbert cube number and the Van der Waerden number. Let $k \geqslant 3$ be an integer. Then for every $\epsilon >0$, there is a $c > 0$ such that $$h(k,4) \geqslant \min\{W(\lfloor c k^2\rfloor, 2), 2^{k^{2.5-\epsilon}}\}.$$ Thus we improve upon state of the art lower bounds for $h(k,4)$ conditional on $W(k,2)$ being significantly larger than $2^k$. In the other direction, this shows that if the Hilbert cube number is close to its state of the art lower bounds, then $W(k,2)$ is at most doubly exponential in $k$.

We also show the optimal result that for any Sidon set $A \subset \mathbb{Z}$, one has $$\left|\left\{\sum_{b \in B} b : B \subseteq A\right\}\right| = \Omega( |A|^3) .$$