Skip to content

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

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.

Back to catalogue · Compendium introduction