Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a string of length formed from an alphabet of characters. Must contain an abelian square: two consecutive blocks and such that is a permutation of ?
Let be a string of length formed from an alphabet of characters. Must contain an abelian square: two consecutive blocks and such that is a permutation of ?
Source: erdosproblems.com/231
An accepted solution exists. The statement is false.
The site shows DISPROVED (LEAN), crediting the negative answer for all to Keränen's infinite abelian-square-free word on four letters [Ke92], a label that describes the corrected Statement. The corrected Statement is disproved: the accepted claim is infinite abelian-square-free words on four letters, and the finite disproof at that Erdős attributes to de Bruijn and himself, published without a construction, is a pending claim, reported finite disproof at four letters. The site's wording, with length , already fails for , as the Notes record. The Lean artifacts behind the label's qualifier are described under Formalization.
The site's wording fails for : the strings ,
, and have length and no abelian
square (the strings and are noted in the formal-conjectures
file, and the string of length is Alexeev's, below). At length the
question holds for , as Erdős reports in [Er61] (below) and as the
formal-conjectures variant erdos_231.variants.two_pow_small proves for
by kernel computation. It fails at , by the site's string
, which has no abelian square.
The change replaces "" by ""; nothing else changes. The evidence is Erdős's own words about instances of the question. [Er61], Part II, item 2 (Some unsolved problems, 1961), calls two consecutive blocks "identical" when each symbol occurs equally often in both, and continues: "I conjectured that in a sequence of length formed from symbols there must be two “identical” blocks. This is true for , but for de BRUIJN and I disproved it". Both reports are true at length and false at length : at that length the conjecture already fails for , and is not its first failure. [Er57], item 28, printed p. 298 (Some unsolved problems, 1957), defines as the least such that every sequence of length over contains two adjacent blocks, each a rearrangement of the other, and reports that his "earliest conjecture, that , has been disproved by Bruijn and myself"; the strings above give for , so this print carries the same slip. The misprint is therefore already in both of the poser's texts, and the site's wording repeats it; his words about the instances hold only for length . The site's commentary suggests that Erdős may have meant ; that suggestion is not the evidence.
Results about the site's wording are credited here and count for nothing.
Boris Alexeev gave the ruler sequence on the site's
discussion thread on
2026-02-15, and the formal-conjectures statement file notes the strings
and . A Lean file in Alexeev's lean-proofs collection, whose header
names de Bruijn and Erdős as informal authors and AxiomProver as formal
author, published by Axiom Math, proves the negation of the site's wording,
not_erdos_231, (pinned
file;
copy at
lean-proofs)
from an abelian-square-free string of length over four characters; it is
linked from the
de Bruijn–Erdős page
and settles no instance of the corrected Statement.