---

Claim. The density Hales--Jewett theorem of H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem, J. Analyse Math. 57 (1991), 64--119 (cited as [FuKa91] on the problem page), states that for every $\epsilon>0$ and $t\ge1$ every subset of $[t]^n$ of size at least $\epsilon t^n$ contains a combinatorial line once $n$ is large enough. With $t=3$ and the letters read as $0,1,2$, a combinatorial line $\{p_1,p_2,p_3\}\subseteq\{0,1,2\}^n$ has $p_2=(p_1+p_3)/2$ coordinate by coordinate, so its three points are collinear in $\mathbb{R}^n$. A subset of $\{0,1,2\}^n$ with no three points on a line therefore contains no combinatorial line, and its density tends to zero: $f_3(n)=o(3^n)$, the question of Problem 185, answered yes. The three-letter case the problem needs was published first, in H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem for $k=3$, Discrete Math. 75 (1989), 227--241 (issued May 1989, per its Crossref record), the claim's earliest public day, which dates this page; erdosproblems.com credits only the 1991 paper. The erdosproblems.com commentary records the answer as this corollary of the theorem; the one-line deduction is restated here and is not the paper's text. Neither paper is held in the library; the theorem's statement is taken from the problem page of Problem 171, whose question it is, and from Theorem 1.4 of the Polymath reproof (card), whose explicit bounds make the density of a combinatorial-line-free subset of $[3]^n$ at most $O(1/\sqrt{\log^*n})$, a quantitative form of the same answer.

Depends on. Furstenberg and Katznelson's density Hales--Jewett theorem, the theorem the corollary rests on; the deduction above uses nothing beyond its statement.

Acceptance. Refereed: the paper appeared in Journal d'Analyse Mathématique, volume 57, issue 1, and the three-letter case in Discrete Mathematics, volume 75. Crossref dates that issue to May 1989 without a day, so this page is named by the first day of that month. Reviewed: the erdosproblems.com curator, Thomas Bloom, records the answer as yes in the problem page's commentary (label PROVED (LEAN)). The curator records it as a corollary of the density Hales--Jewett theorem of Furstenberg and Katznelson. This is documented acceptance outside this project. The erdosproblems.com Lean marker traces to a formalization of the problem through the Dodos--Kanellopoulos--Tyros proof of the theorem, which is pinned on their claim page. It does not go through this proof, so no formalized evidence is listed. Nothing here is this project's own review of the proof.

Context from erdosproblems.com, not part of the claim: Moser first considered the problem. Trivially $f_3(n)\ge r_3(3^n)$, and Moser showed $f_3(n)\gg3^n/\sqrt n$.