AFTD Auto-Formalizing Theoretical Domains

is_rich_word

def

An infinite word w is rich in palindromes if every complete return word to a palindromic factor of w is itself a palindrome.

Statement

def is_rich_word {α : Type*} (w : ℕ → α) : Prop
Defined in
arXiv:2611.13676 Theorem 2.1
Verified
12 Nov 2026
Axioms
none listed
Built on 1
  • is_complete_return_wordA word c is a complete return word to a factor q if q is both a prefix and a suffix of c, strictly shorter than c, and q does not occur at…
Used by 2

Read back from the Lean

An infinite word w : ℕ → α is a rich word if and only if for every pair of finite lists c, q : List α, whenever q is a palindrome, c is a complete return word to q, and c occurs as a factor of w (i.e., there exists an index i : ℕ such that c equals [w i, w (i + 1), …, w (i + c.length - 1)]), then c is also a palindrome.

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 rich if every complete return word to any of its palindromic factors is a palindrome. -/
def is_rich_word {α : Type*} (w : ℕ → α) : Prop := ∀ c q : List α, q.Palindrome → is_complete_return_word c q →
  (∃ i : ℕ, c = (List.range c.length).map (fun j => w (i + j))) → c.Palindrome
See it in the graphDiscuss this resultChallenge it