Skip to content

Erdős Problem #192

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: arithmetic progressions, 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

Start at a point of \(\mathbb R^d\) and repeatedly move by a positive coordinate unit vector \(e_i\): exactly one coordinate increases by one at each step. Erdős and Graham asked for which dimensions \(d\) every infinite such walk contains three distinct visited points in an arithmetic progression:

\[ p,\ q,\ r,\qquad p+r=2q. \]

Every step must be a positive basis vector, never its negative or an arbitrary Euclidean unit vector. The selected triple may occur at nonconsecutive times on the walk.

A small example

Encode the sequence of steps as a word on an alphabet of \(d\) letters, the letter \(i\) representing \(e_i\). Consider two consecutive blocks of steps with the same multiset of letters but perhaps in different order. Their displacement vectors are equal, so the vertices at the beginning, boundary and end form a three-term arithmetic progression.

For example, the two-letter word \(1212\) contains consecutive blocks \(12\) and \(12\). In \(\mathbb R^2\) the walk goes \((0,0),(1,0),(1,1),(2,1),(2,2)\), and the points at times 0, 2, 4 form an arithmetic progression. The blocks could instead be \(12\) and \(21\); they need only be anagrams, not identical strings.

What is known

SOLVED by the theory of abelian squares in words. A word contains an abelian square when two adjacent nonempty blocks have the same letter-count vector. For a walk with positive basis-vector steps, the corresponding three vertices form an arithmetic progression if and only if its step word contains an abelian square.

Infinite abelian-square-free words do not exist on alphabets of at most three letters: the relevant finite obstruction can be checked by exhaustive search, with the maintained catalogue claiming that every ternary word of length seven contains an abelian square. That finite claim is false: the word \(1213121\) has length seven and no adjacent equal-multiset blocks. Exact enumeration instead finds no abelian-square-free ternary word of length eight. This numerical correction does not change the infinite-word classification. On a four-letter alphabet, Evgenii Keränen, Abelian squares are avoidable on 4 letters (1992), constructed an infinite word with no abelian square.

Consequently every infinite walk has an arithmetic triple for \(d\le3\), but a counterexample walk exists when \(d\ge4\) by embedding the four-coordinate construction in higher dimension. This answers the dimension-classification question exactly. The distinction between ordinary repeated adjacent blocks and equal letter counts is essential.

GCL's current state

The pinned and maintained Erdős #192, updated May 2026, classify the question SOLVED and report an external Lean proof. Original source issue: #1461. Keränen's original 1992 morphism and the external Lean artifact were not independently rebuilt or axiom-audited. The current catalogue's length-seven subclaim is contradicted by an exact finite counterexample and must not be copied into formal source files.

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 task enumerates all step words over alphabets of size two and three up to length seven, detects adjacent equal-multiset blocks with exact Parikh vectors, and verifies the equivalence to arithmetic triples in the resulting coordinate walk. Acceptance: both \(1212\) and \(1221\) yield arithmetic triples, the length-seven counterexample \(1213121\) passes the abelian-square-free test, whereas all length-eight ternary words fail, and the transformation is proved bidirectionally. Stop at this finite semantic result; no claim of independently constructing Keränen's infinite four-letter word.

Sources and claim boundaries

No new word-avoidance construction, GCL kernel proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1461 — 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