AFTD Auto-Formalizing Theoretical Domains

thue_morse_random_attractor_prob

def

For natural numbers n and k, the real number defined as the ratio whose numerator is the cardinality of the finset of functions f : Fin k → {p : ℕ // p ∈ Finset.Icc 1 (2^n)} whose image { (f i).val | i : Fin k } satisfies is_string_attractor (thue_morse_word n), and whose denominator is (2^n : ℝ)^k.

Statement

noncomputable def thue_morse_random_attractor_prob (n k : ℕ) : ℝ
Defined in
arXiv:2610.10950
Verified
29 Oct 2026
Axioms
none listed
Built on 2
  • is_string_attractorA set Γ ⊆ [1, |w|] of positions is a string attractor of the finite word w if Γ ∩ Cov_w(x) ≠ ∅ for every nonempty factor x of w.
  • thue_morse_wordThe n-th Thue-Morse word t_n over the alphabet {false, true}, defined recursively by t_0 = [false] and t_{n+1} obtained by replacing each…
Used by 2

Read back from the Lean

thue_morse_random_attractor_prob n k is defined as the real-valued probability that a sequence of $k$ positions chosen independently and uniformly at random with replacement from $\{1, \dots, 2^n\}$ forms a string attractor for the $n$-th Thue-Morse word. Specifically, it computes the cardinality of the set of functions $f : \mathrm{Fin}\ k \to \{p \in \mathbb{N} \mid 1 \le p \le 2^n\}$ whose image $\{f(i) \mid i \in \mathrm{Fin}\ k\}$ is a string attractor for thue_morse_word n, divided by $(2^n)^k$.

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

/-- The fraction of ordered k-tuples of positions from {1,...,2^n} whose distinct values form a string attractor of t_n. -/
noncomputable def thue_morse_random_attractor_prob (n k : ℕ) : ℝ :=
  open scoped Classical in
  let positions : Finset ℕ := Finset.Icc 1 (2^n)
  ((Finset.univ.filter (fun (f : Fin k → {p : ℕ // p ∈ positions}) =>
    is_string_attractor (thue_morse_word n) (Finset.image (fun i => (f i).val) Finset.univ))).card : ℝ) /
    ((2^n : ℝ) ^ k)
See it in the graphDiscuss this resultChallenge it