thue_morse_random_attractor_prob_zero
For every natural number n, thue_morse_random_attractor_prob n 0 = 0.
Statement
theorem thue_morse_random_attractor_prob_zero (n : ℕ) : thue_morse_random_attractor_prob n 0 = 0- Source
- arXiv:2610.10950
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- not_is_string_attractor_emptyThe empty set is not a string attractor of a nonempty word.
- 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…
- thue_morse_word_lengthFor every natural number n, the length of the n-th Thue-Morse word t_n is 2^n.
- 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_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…
Read back from the Lean
For every natural number $n$, the value of thue_morse_random_attractor_prob n 0 is equal to 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof unfolds the definition of the random attractor probability at sample size 0, which reduces to checking whether any function from Fin 0 into the word's positions produces a string attractor. Since the domain is empty, any such function has empty image. Because the Thue-Morse word of order n has positive length 2^n and is therefore non-empty, the empty set cannot be a string attractor, leaving no valid witnesses and yielding a probability of 0.
The probability expression simplifies to the cardinality of the set of 0-sample attractor configurations.
Unfolding the definition of `thue_morse_random_attractor_prob` for sample size k = 0 gives a denominator of (2^n)^0, which simplifies to 1 via `pow_zero`. Dividing the numerator by 1 leaves just the cardinality via `div_one`.
uses
pow_zero,div_oneunfold thue_morse_random_attractor_prob simp only [pow_zero, div_one]
The n-th Thue-Morse word is non-empty.
Assuming for contradiction that the word is empty (`intro h`), its length would be 0. However, `thue_morse_word_length` states that its length is 2^n. Since 2^n > 0 by `Nat.two_pow_pos`, `Nat.pos_iff_ne_zero.mp` implies 2^n ≠ 0, giving a contradiction.
uses
thue_morse_word_length,Nat.pos_iff_ne_zero.mp,Nat.two_pow_poshave hne : thue_morse_word n ≠ [] := by intro h have hlen := thue_morse_word_length n rw [h] at hlen exact Nat.pos_iff_ne_zero.mp (Nat.two_pow_pos n) hlen.symm
It suffices to show that the set of valid configurations is empty.
A real-coerced natural number equals 0 if and only if the natural number is 0 (`Nat.cast_eq_zero`), and the cardinality of a finite set is 0 if and only if the set is empty (`Finset.card_eq_zero`).
uses
Nat.cast_eq_zero,Finset.card_eq_zerorw [Nat.cast_eq_zero, Finset.card_eq_zero]The set of valid configurations is empty, which completes the proof.
Each configuration is a map from the empty domain Fin 0, so its image is the empty set ∅. Since the word is non-empty (`hne`), `not_is_string_attractor_empty` states that ∅ is not a string attractor, so the filtering condition evaluates to false for all elements and the set is empty.
uses
not_is_string_attractor_emptysimp [not_is_string_attractor_empty hne]
pow_zero- Any element raised to the zeroth power equals 1.
div_one- Dividing any element by 1 yields the element itself.
thue_morse_word_length- The length of the n-th Thue-Morse word is 2^n.
Nat.pos_iff_ne_zero.mp- A strictly positive natural number is nonzero.
Nat.two_pow_pos- Any power of 2 is strictly positive.
Nat.cast_eq_zero- The coercion of a natural number into a characteristic-zero domain is zero if and only if the natural number is zero.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
not_is_string_attractor_empty- The empty set of positions cannot be a string attractor for any non-empty word.
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.
/-- The 0-sample random attractor probability of t_n is 0 for every n. -/theorem thue_morse_random_attractor_prob_zero (n : ℕ) : thue_morse_random_attractor_prob n 0 = 0 := by unfold thue_morse_random_attractor_prob simp only [pow_zero, div_one] have hne : thue_morse_word n ≠ [] := by intro h have hlen := thue_morse_word_length n rw [h] at hlen exact Nat.pos_iff_ne_zero.mp (Nat.two_pow_pos n) hlen.symm rw [Nat.cast_eq_zero, Finset.card_eq_zero] simp [not_is_string_attractor_empty hne]