is_recurrent_word
def
An infinite word w is recurrent if every factor of w occurs at least twice in w.
Statement
def is_recurrent_word {α : Type*} (w : ℕ → α) : Prop
- Defined in
- arXiv:2611.13676 Section 2
- Verified
- 12 Nov 2026
- Axioms
- none listed
Read back from the Lean
For an infinite sequence (word) w : ℕ → α over a type α, is_recurrent_word w asserts that for every finite list u : List α, if there exists an index i : ℕ such that u is the factor of w of length u.length starting at i (that is, u = (List.range u.length).map (fun j => w (i + j))), then there exist two indices i, j : ℕ with i < j such that u occurs in w at both starting positions i and j (that is, u = (List.range u.length).map (fun m => w (i + m)) and u = (List.range u.length).map (fun m => w (j + m))).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An infinite word is recurrent if every factor that occurs in it has at least two occurrences. -/ def is_recurrent_word {α : Type*} (w : ℕ → α) : Prop := ∀ u : List α, (∃ i : ℕ, u = (List.range u.length).map (fun j => w (i + j))) → ∃ i j : ℕ, i < j ∧ u = (List.range u.length).map (fun m => w (i + m)) ∧ u = (List.range u.length).map (fun m => w (j + m))