Skip to content

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

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.

Back to catalogue · Compendium introduction