AFTD Auto-Formalizing Theoretical Domains

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))
See it in the graphDiscuss this resultChallenge it