Erdős Problem #171
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: additive combinatorics, 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
For an alphabet of \(t\) symbols, consider all words of length \(N\), namely \([t]^N\). A combinatorial line is a collection of \(t\) words formed by fixing some coordinates and replacing every remaining coordinate by a common variable that takes values \(1,\ldots,t\).
The density Hales–Jewett theorem asserts that, for every fixed \(t\ge1\) and density \(\varepsilon>0\), every sufficiently high-dimensional set \(A\subseteq[t]^N\) with at least \(\varepsilon t^N\) words contains a complete combinatorial line. It is a statement about positive density, not merely one colour class in a finite colouring.
A small example
In \([3]^2\), the three words \(11\), \(22\), \(33\) form a combinatorial line: both positions vary together. So do \(12\), \(22\), \(32\), because the second position is fixed while the first varies. The words \(11\), \(23\), \(32\) do not form such a line because the two coordinates do not share a common pattern of being fixed or varying.
Statement-fidelity warning: the displayed maintained problem page says “for each coordinate \(1\le j\le t\),” but the vectors have \(N\) coordinates. The quantifier must run over \(j=1,\ldots,N\) for the standard theorem. This is a minor indexing transcription error, not a new conjecture.
What is known
PROVED. Furstenberg and Katznelson established the density theorem in 1991 using ergodic methods. The D. H. J. Polymath collaboration published A new proof of the density Hales–Jewett theorem, Annals of Mathematics 175 (2012), 1283–1327, providing an elementary combinatorial proof and quantitative bounds.
For alphabet size three, the Polymath paper gives a quantitative sufficient dimension bounded by a tower of twos whose height is \(O(1/\varepsilon^2)\). The quantitative height is not a universal claim of polynomial dependence on \(1/\varepsilon\).
This is stronger than ordinary Hales–Jewett, where any finite colouring of a sufficiently high-dimensional cube forces a monochromatic line; the density theorem forces one inside every fixed-positive-density subset.
GCL's current state
Pinned and maintained Erdős #171 classify the question PROVED. Original issue: #1440. The original Polymath publication abstract was checked. The provider snapshot at its pinned revision lacks this theorem file; newer upstream formal-status metadata is not a protected GCL kernel certificate.
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 semantics task enumerates all combinatorial lines in \([3]^2\) and \([3]^3\), classifies each coordinate as fixed or varying, and compares this enumeration with the corrected \(N\) coordinate definition. Acceptance: the diagonal and one-coordinate-variable examples above are admitted, invalid mixed-coordinate cases rejected, and no numerical experiment is confused with the infinite-dimensional density theorem.
Sources and claim boundaries
- Polymath, Annals of Mathematics 175 (2012), primary modern proof.
- Erdős #171, Furstenberg–Katznelson 1991 historical proof.
- Original GCL issue #1440.
No new proof, independent formal certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1440 — 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.