/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 231

References:

    erdosproblems.com/231

    [Er57] Erdős, Paul, Some unsolved problems. Michigan Math. J. (1957), 291-300.

    [Er61] Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254.

    [Ke92] Keränen, Veikko, Abelian squares are avoidable on $4$ letters. Automata, languages and programming (Vienna, 1992) (1992), 41-52.

    [FiPu23] Fici, Gabriele and Puzynina, Svetlana, Abelian combinatorics on words: a survey. Comput. Sci. Rev. (2023), Paper No. 100532, 21.

@[expose] public sectionnamespace Erdos231

A string S contains an abelian square if it has two consecutive nonempty blocks x and y such that y is a permutation of x.

def ContainsAbelianSquare {α : Type*} (S : List α) : Prop := ∃ x y : List α, x ≠ [] ∧ x.Perm y ∧ x ++ y <:+: S

S contains an abelian square iff two consecutive blocks of some positive length L of S are permutations of each other.

α:Type u_1S:List αi:ℕL:ℕhL:0 < Lhle:i + 2 * L ≤ S.lengthhperm:(List.take L (List.drop i S)).Perm (List.take L (List.drop (i + L) S))this:List.take L (List.drop i S) ++ List.take L (List.drop (i + L) S) = List.take (L + L) (List.drop i S)⊢ List.take (L + L) (List.drop i S) <:+: S All goals completed! 🐙instance {α : Type*} [DecidableEq α] (S : List α) : Decidable (ContainsAbelianSquare S) := decidable_of_iff _ (containsAbelianSquare_iff S).symm

The string $1213121412132124$ of length $2^4$ over four characters contains no abelian square.

@[category API, AMS 5] theorem not_containsAbelianSquare_example : ¬ ContainsAbelianSquare ([0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 1, 0, 1, 3] : List (Fin 4)) := ⊢ ¬ContainsAbelianSquare [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 1, 0, 1, 3] All goals completed! 🐙

Every string of length $4$ over two characters contains an abelian square.

@[category API, AMS 5] theorem containsAbelianSquare_of_length_four (f : Fin 4 → Fin 2) : ContainsAbelianSquare (List.ofFn f) := f:Fin 4 → Fin 2⊢ ContainsAbelianSquare (List.ofFn f) ⊢ ∀ (f : Fin 4 → Fin 2), ContainsAbelianSquare (List.ofFn f) All goals completed! 🐙set_option maxRecDepth 200000 in

Every string of length $8$ over three characters contains an abelian square.

@[category API, AMS 5] theorem containsAbelianSquare_of_length_eight (f : Fin 8 → Fin 3) : ContainsAbelianSquare (List.ofFn f) := f:Fin 8 → Fin 3⊢ ContainsAbelianSquare (List.ofFn f) ⊢ ∀ (f : Fin 8 → Fin 3), ContainsAbelianSquare (List.ofFn f) All goals completed! 🐙

Let $S$ be a string of length $2^k-1$ formed from an alphabet of $k$ characters. Must $S$ contain an abelian square: two consecutive blocks $x$ and $y$ such that $y$ is a permutation of $x$?

Erdős initially conjectured that the answer is yes for all $k\geq 2$, but for $k=4$ this was disproved by de Bruijn and Erdős. Erdős then asked if there is in fact an infinite string formed from ${1,2,3,4}$ which contains no abelian squares? This is equivalent to 192, and such a string was constructed by Keränen [Ke92]. The existence of this infinite string gives a negative answer to the problem for all $k\geq 4$.

Containing no abelian squares is a stronger property than being squarefree (the existence of infinitely long squarefree strings over alphabets with $k\geq 3$ characters was established by Thue). We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results.

As stated, the answer is negative for every $k \geq 2$: the strings $121$ and $1213121$ of length $2^k - 1$ for $k = 2, 3$ contain no abelian square. See erdos_231.variants.two_pow for strings of length $2^k$.

@[category research solved, question, AMS 5, formal_proof using lean4 at "https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos231.lean#L38"] theorem erdos_231 : ¬ ∀ k : ℕ, 2 ≤ k → ∀ S : List (Fin k), S.length = 2 ^ k - 1 → ContainsAbelianSquare S := ⊢ ¬∀ (k : ℕ), 2 ≤ k → ∀ (S : List (Fin k)), S.length = 2 ^ k - 1 → ContainsAbelianSquare S All goals completed! 🐙

Perhaps Erdős meant $2^k$, where indeed there is an example for $k=4$: $$1213121412132124.$$ Every string of length $2^k$ over $k$ characters contains an abelian square for $k = 2, 3$, but not for $k \geq 4$.

@[category research solved, question, AMS 5] theorem erdos_231.variants.two_pow : ¬ ∀ k : ℕ, 2 ≤ k → ∀ S : List (Fin k), S.length = 2 ^ k → ContainsAbelianSquare S := ⊢ ¬∀ (k : ℕ), 2 ≤ k → ∀ (S : List (Fin k)), S.length = 2 ^ k → ContainsAbelianSquare S h:∀ (k : ℕ), 2 ≤ k → ∀ (S : List (Fin k)), S.length = 2 ^ k → ContainsAbelianSquare S⊢ False exact not_containsAbelianSquare_example (h 4 (h:∀ (k : ℕ), 2 ≤ k → ∀ (S : List (Fin k)), S.length = 2 ^ k → ContainsAbelianSquare S⊢ 2 ≤ 4 All goals completed! 🐙) _ rfl)

Every string of length $2^k$ over $k$ characters contains an abelian square for $k = 2, 3$.

k:ℕhk:k = 2 ∨ k = 3S:List (Fin k)hS:S.length = 2 ^ kkey:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn f⊢ ContainsAbelianSquare S key:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn fS:List (Fin 2)hS:S.length = 2 ^ 2⊢ ContainsAbelianSquare Skey:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn fS:List (Fin 3)hS:S.length = 2 ^ 3⊢ ContainsAbelianSquare S key:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn fS:List (Fin 2)hS:S.length = 2 ^ 2⊢ ContainsAbelianSquare S key:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn ff:Fin (2 ^ 2) → Fin 2hS:(List.ofFn f).length = 2 ^ 2⊢ ContainsAbelianSquare (List.ofFn f) All goals completed! 🐙 key:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn fS:List (Fin 3)hS:S.length = 2 ^ 3⊢ ContainsAbelianSquare S key:∀ {α : Type} (S : List α) {n : ℕ}, S.length = n → ∃ f, S = List.ofFn ff:Fin (2 ^ 3) → Fin 3hS:(List.ofFn f).length = 2 ^ 3⊢ ContainsAbelianSquare (List.ofFn f) All goals completed! 🐙end Erdos231