  The Hales--Jewett theorem is one of the pillars of Ramsey theory, from which
many other results follow. A celebrated theorem of Shelah says that
Hales--Jewett numbers are primitive recursive. A key tool used in his proof,
now known as the cube lemma, has become famous in its own right. In its
simplest form, this lemma says that if we color the edges of the Cartesian
product $K_n \times K_n$ in $r$ colors then, for $n$ sufficiently large, there
is a rectangle with both pairs of opposite edges receiving the same color.
Shelah's proof shows that $n = r^{\binom{r+1}{2}} + 1$ suffices. More than
twenty years ago, Graham, Rothschild and Spencer asked whether this bound can
be improved to a polynomial in $r$. We show that this is not possible by
providing a superpolynomial lower bound in $r$. We also discuss a number of
related problems.
