Skip to content

Erdős Problem #231

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

Given an alphabet of exactly \(k\) permitted symbols, Erdős asked whether every word of length \(2^k-1\) necessarily contains an abelian square: two adjacent nonempty blocks \(X,Y\) having the same counts of each letter, even if their orders differ.

For example, the word 1221 is an abelian square, divided as 12|21; the halves are permutations of each other rather than identical. A word without abelian squares must avoid every adjacent pair of equal-multiset blocks, not merely literal repeated substrings.

A small example

Over two symbols, the three-letter word 121 has no abelian square, disproving the assertion as literally phrased for \(k=2\); it has no two adjacent equal letters and is too short for two blocks of length two.

Over three symbols, 1213121 has length seven and is abelian-square-free. For \(k=4\) the fifteen-letter word

121312141213212

is abelian-square-free. It is a prefix of the catalogue's longer 16-letter example 1213121412132124, which is also abelian-square-free. Each is directly verifiable by comparing the Parikh vectors of all pairs of adjacent equal-length blocks.

These short explicit words remove any reliance on a speculative search result for the finite question.

What is known

DISPROVED, both for the finite universal formulation and the stronger infinite-word issue. Keränen (1992) constructed an infinite abelian-square-free word over four letters. Such a word has an abelian-square-free prefix of every finite length, disproving the \(2^k-1\) claim for any \(k\ge4\) by using only four of the permitted symbols.

The maintained Erdős #231 acknowledges the Keränen construction and its equivalence to #192, but also questions an earlier claimed counterexample for \(k=4\) at length \(2^k-1=15\). Its own displayed 16-letter counterexample has a 15-letter prefix, so that doubt is internally inconsistent. Finite counterexamples for \(k=2\) and \(k=3\) similarly follow directly from the words above.

Avoiding abelian squares is stronger than avoiding ordinary squares. Thue's three-letter infinite square-free construction is not an abelian-square-free four-letter construction.

GCL's current state

The pinned/live catalogue classify the conjecture DISPROVED. Original issue #1500. The exact finite counterexamples are locally verified; Keränen's full infinite morphism and any external formal proof are not independently reproduced here. The catalogue's misleading search remark is retained as a source-fidelity finding.

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 exhaustively checks all adjacent blocks in the three counterexamples, records their Parikh vectors, and independently counts abelian-square-free words of length seven over three symbols. Acceptance: the displayed words pass, the related 1212 fails at 12|12, and finite checking is separated from the infinite Keränen theorem. A proof-level task should replay Keränen's substitution with a fixed original source and prove indefinite avoidance.

Sources and claim boundaries

No new infinite-word construction, independent Keränen proof or protected editorial admission is claimed.

Catalogue and evidence provenance

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