Problem Statement
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)$?
Categories:
Additive Combinatorics
Progress
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].Source: erdosproblems.com/185 | Last verified: January 14, 2026