thue_morse_random_attractor_prob_mem_unit_interval
For all n and k, 0 ≤ thue_morse_random_attractor_prob n k ≤ 1.
Statement
theorem thue_morse_random_attractor_prob_mem_unit_interval (n k : ℕ) :
thue_morse_random_attractor_prob n k ∈ Set.Icc (0 : ℝ) 1- Source
- step towards thue_morse_random_attractor_lattice_gumbel
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- thue_morse_random_attractor_probFor 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…
- thue_morse_word_lengthFor every natural number n, the length of the n-th Thue-Morse word t_n is 2^n.
- 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…
- 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.
The proof, explained
The theorem states that the probability of randomly choosing a string attractor of size k for the n-th Thue-Morse word lies in [0, 1]. The probability is defined as the count of successful choices divided by the total number of choices, (2^n)^k. Non-negativity holds because the numerator is a cardinality and the denominator is positive, while the upper bound holds because the successful choices form a subset of all (2^n)^k possible functions.
The goal reduces to proving that the probability is at least 0 and at most 1.
By `Set.mem_Icc`, membership in the closed interval [0, 1] means lying between 0 and 1. Unfolding the definition of `thue_morse_random_attractor_prob` reveals it as the fraction of functions from `Fin k` to positions `{1, ..., 2^n}` that form a string attractor, divided by `(2^n)^k`. We split this into two separate goals: non-negativity and being bounded above by 1.
uses
Set.mem_Iccrw [Set.mem_Icc] unfold thue_morse_random_attractor_prob constructor
The probability is non-negative. automation
The numerator is the cardinality of a finite set (coerced to real numbers, hence non-negative) and the denominator is a power of 2 (strictly positive). The `positivity` tactic determines that the quotient of a non-negative real by a positive real is non-negative.
· positivityThe upper bound reduces to showing that the number of attractor configurations is at most (2^n)^k in the natural numbers.
The denominator `(2^n)^k` is strictly positive (checked by `positivity`). Applying `div_le_one` reduces the inequality `numerator / denominator ≤ 1` to `numerator ≤ denominator`. Then `norm_cast` strips the coercion to ℝ, leaving an inequality between natural numbers.
uses
div_le_one· have hpos : 0 < ((2 : ℝ) ^ n) ^ k := by positivity rw [div_le_one hpos] norm_cast
The number of attractor configurations is at most (2^n)^k.
The attractor configurations form a sub-finset of all functions from `Fin k` to `{1, ..., 2^n}`. By `Finset.card_le_univ` and transitivity (`le_trans`), the size of this subset is at most the total number of such functions. Finally, `simp` computes that this function space has size `(2^n)^k`, which closes the inequality `(2^n)^k ≤ (2^n)^k`.
uses
le_trans,Finset.card_le_univrefine le_trans (Finset.card_le_univ _) ?_ simp
Set.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
div_le_one- For a strictly positive denominator b, the fraction a / b is at most 1 if and only if a ≤ b.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the entire type.
- On line 12, the `simp` tactic automatically calculates the cardinality of the function type `Fin k → Finset.Icc 1 (2^n)` as `(2^n)^k` using library lemmas about finite function types and intervals, then closes the resulting goal `(2^n)^k ≤ (2^n)^k` by reflexivity.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Each random-attractor probability lies in the unit interval. -/theorem thue_morse_random_attractor_prob_mem_unit_interval (n k : ℕ) : thue_morse_random_attractor_prob n k ∈ Set.Icc (0 : ℝ) 1 := by rw [Set.mem_Icc] unfold thue_morse_random_attractor_prob constructor · positivity · have hpos : 0 < ((2 : ℝ) ^ n) ^ k := by positivity rw [div_le_one hpos] norm_cast refine le_trans (Finset.card_le_univ _) ?_ simp