Erdős Problem #185
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
In the cube \([3]^n=\{0,1,2\}^n\), how many vertices can be chosen without three distinct collinear points? Let \(f_3(n)\) be the largest such set size. Erdős and Moser asked whether \(f_3(n)/3^n\to0\) as the dimension grows. Lines are geometric: coordinates may rise or fall, and this is stronger than avoiding ordinary Hales–Jewett combinatorial lines.
A small example
In \([3]^1\), at most two vertices avoid a line. In \([3]^2\), the diagonal \((0,0),(1,1),(2,2)\) and antidiagonal \((0,2),(1,1),(2,0)\) are both geometric lines. The antidiagonal is not a standard combinatorial line, since its coordinates vary in opposite directions. Exact finite optima begin \(f_3(1)=2\), \(f_3(2)=6\).
What is known
PROVED. The density Hales–Jewett theorem of Furstenberg and Katznelson (1991) and the D. H. J. Polymath elementary proof imply the conjecture. Every fixed-density subset of \([3]^n\) contains a combinatorial line, hence a geometric line. Therefore the maximum density of a geometric-line-free subset tends to zero. This implication does not identify the exact finite values of \(f_3(n)\). Moser's construction gives \(f_3(n)\gg3^n/\sqrt n\), consistent with vanishing density.
GCL's current state
Pinned and maintained Erdős #185 classify the conjecture PROVED. Original source issue: #1454. The source theorem's implication was checked, but its proof and reported external formalization were not independently replayed on GCL's locked provider.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor enumerates every geometric three-point line in \([3]^n\) for \(n=1,2,3\), obtains exact maximal line-free subsets, and distinguishes them from Hales–Jewett combinatorial lines. Acceptance: the antidiagonal example is recognised as geometric but not combinatorial, and the first two optima are \(2\) and \(6\). Stop at finite semantics; do not infer the density theorem from these checks.
Sources and claim boundaries
- Polymath, Annals of Mathematics 175 (2012), primary modern proof.
- Erdős #185, Moser and Furstenberg–Katznelson history.
- OEIS A003142, finite Moser numbers.
No new density theorem, independent kernel certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1454 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.