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\ge 3$ be an integer. Then for every $\epsilon >0$, there is a $c>0$ such that $$h(k,4)\ge \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 the if the Hilbert cube number is close 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).$$