Logo
All Random Solved Random Open
SOLVED
Let $f_3(n)$ be the maximal size of a subset of $\{0,1,2\}^n$ which contains no three points on a line. Is it true that $f_3(n)=o(3^n)$?
Originally considered by Moser. It is trivial that $f_3(n)\geq R_3(3^n)$, the maximal size of a subset of $\{1,\ldots,3^n\}$ without a three-term arithmetic progression. Moser showed that \[f_3(n) \gg \frac{3^n}{\sqrt{n}}.\]

The answer is yes, which is a corollary of the density Hales-Jewett theorem, proved by Furstenberg and Katznelson [FuKa91].