is_uniformly_recurrent_word
An infinite word w : ℕ → α is uniformly recurrent if for every finite factor u of w, there exists a bound N such that every window of length N + |u| in w contains an occurrence of u.
Statement
def is_uniformly_recurrent_word {α : Type*} (w : ℕ → α) : Prop
- Defined in
- arXiv:2611.13676 Sec. 2
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Used by 2
- rich_word_critical_exponentsFor any positive integer d, the set S_d of critical exponents of uniformly recurrent d-ary rich words is the collection of all real…
- op_1458_rich_repetition_threshold_le_asymptotic_of_projectionFor any integer d ≥ 2, if there exist a morphism π : Fin (2 * d - 1) → List (Fin d) and an infinite word z : ℕ → Fin d such that z is the…
Read back from the Lean
For a type α and an infinite sequence w : ℕ → α, is_uniformly_recurrent_word w asserts that for every list u : List α, if there exists a natural number i such that u is equal to the subword of w of length u.length starting at index i (i.e., u = (List.range u.length).map (fun j => w (i + j))), then there exists a natural number N such that for every natural number k, there exists a natural number j such that k ≤ j ≤ k + N and u is equal to the subword of w of length u.length starting at index j (i.e., 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 uniformly recurrent if every factor appears with bounded gaps between consecutive occurrences. -/ def is_uniformly_recurrent_word {α : Type*} (w : ℕ → α) : Prop := ∀ u : List α, (∃ i : ℕ, u = (List.range u.length).map (fun j => w (i + j))) → ∃ N : ℕ, ∀ k : ℕ, ∃ j : ℕ, k ≤ j ∧ j ≤ k + N ∧ u = (List.range u.length).map (fun m => w (j + m))