Erdős Problem #231
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problems openaigpt 6 astra ultra 100% cataloguedSolvedSolvedStatement
Must a word of length $2^k-1$ on $k$ letters contain two adjacent nonempty blocks with the same multiset of letters? The literal finite statement has a negative answer for every $k\geq1$. The construction below settles precisely this length formulation. The related existence of an infinite abelian-square-free word on four letters is a stronger theorem, due to Keränen, and is not proved here.
Restatement from Math-5520-A1 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Math-5520
Erdős Problem 231: finite words without abelian squares
1) Statement and scope
Must a word of length $2^k-1$ on $k$ letters contain two adjacent nonempty blocks with the same multiset of letters? The literal finite statement has a negative answer for every $k\geq1$. The construction below settles precisely this length formulation. The related existence of an infinite abelian-square-free word on four letters is a stronger theorem, due to Keränen, and is not proved here.2) Recursive counterexample
Let $W_1=1$ and, using a new letter at each stage, define \[ W_k=W_{k-1}\,k\,W_{k-1}\qquad(k\geq2). \] Induction gives $|W_k|=2^k-1$, and $W_k$ uses exactly the letters $1,\ldots,k$. The first examples are \[ 1,\qquad121,\qquad1213121,\qquad121312141213121. \] We prove by induction that $W_k$ contains no abelian square. The assertion is immediate for $k=1$. Suppose that two adjacent blocks $X,Y$ in $W_k$ have equal multisets. If their union contains the central letter $k$, that letter occurs exactly once in $XY$. It therefore cannot occur equally often in $X$ and $Y$, a contradiction. If their union avoids $k$, the contiguous block $XY$ lies wholly inside one of the two copies of $W_{k-1}$, contradicting induction. This proves the claim.3) Interpretation and attribution
The page's historical discussion suggests that a power-of-two length may have been intended in an older formulation. Our word has length $2^k-1$, not $2^k$; those questions must be distinguished. Also, taking a limit in this recursion introduces infinitely many different letters. It does not establish the infinite four-letter result. This is an elementary reconstruction addressing the displayed statement, with no claim of a new result or a new formal proof.Source: T. F. Bloom, Erdős Problem 231, https://www.erdosproblems.com/231, accessed 23 September 2026. The page attributes the infinite four-letter result to V. Keränen $1992$.