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
- Erdős #231, Keränen [Ke92], Thue and Fici–Puzynina survey [FiPu23].
- Related Erdős #192, infinite four-letter avoidance.
- Original source issue #1500.
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.