thue_morse_unhit_mean_nonneg
For all n and k, 0 ≤ thue_morse_unhit_mean n k.
Statement
theorem thue_morse_unhit_mean_nonneg (n k : ℕ) : 0 ≤ thue_morse_unhit_mean n k- Source
- step towards thue_morse_random_attractor_lattice_gumbel
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- thue_morse_unhit_meanThe expected number of unhit inclusion-minimal factor coverages of t_n under a uniformly random k-tuple of positions: the sum over C in…
- thue_morse_min_factor_coverages_finset_memFor every n and every C, C belongs to thue_morse_min_factor_coverages_finset n if and only if C is an inclusion-minimal factor coverage of…
- word_min_factor_coverages_subsetEvery inclusion-minimal factor coverage is a factor coverage: H_min(w) ⊆ H(w).
- word_occurrence_coverage_subsetEvery coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
- thue_morse_word_lengthFor every natural number n, the length of the n-th Thue-Morse word t_n is 2^n.
- word_occurrence_coverageThe coverage Cov_w(x) of a word x in a finite word w: the union of the intervals [p, p+|x|−1] over all (1-based) occurrence starts p of x…
- word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
- thue_morse_min_factor_coverages_finsetThe finite set of inclusion-minimal factor coverages H_min(t_n) of the n-th Thue-Morse word, realized as a Finset of subsets of the…
- word_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors 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…
The proof, explained
The expected unhit mean is defined as a sum of powers (1 - |C| / 2^n)^k over all minimal factor coverages C of the n-th Thue-Morse word. Since sums and natural powers of nonnegative numbers are nonnegative, the claim reduces to showing that each term 1 - |C| / 2^n is nonnegative, or equivalently that |C| ≤ 2^n. This bound holds because every minimal factor coverage is a subset of the word's position indices {1, ..., length(w)}, and the n-th Thue-Morse word has length 2^n.
To show that the expected unhit mean is nonnegative, it suffices to show that |C| / 2^n ≤ 1 for every minimal factor coverage C of the n-th Thue-Morse word.
By definition, thue_morse_unhit_mean n k is the sum over all minimal factor coverages C of (1 - |C| / 2^n)^k. Because a sum of nonnegative terms is nonnegative (Finset.sum_nonneg) and natural powers of nonnegative numbers are nonnegative (pow_nonneg), it suffices to show 0 ≤ 1 - |C| / 2^n. This inequality is equivalent to |C| / 2^n ≤ 1 (sub_nonneg).
uses
Finset.sum_nonneg,pow_nonneg,sub_nonnegunfold thue_morse_unhit_mean apply Finset.sum_nonneg intro C hC apply pow_nonneg rw [sub_nonneg]
Every minimal factor coverage C is contained in the index set {1, ..., length(thue_morse_word n)}.
Membership in the finset of minimal factor coverages translates to membership in the set word_min_factor_coverages via thue_morse_min_factor_coverages_finset_mem. Any minimal factor coverage is a factor coverage (word_min_factor_coverages_subset), which by definition (word_factor_coverages, Set.mem_ofPred_eq) means C is the occurrence coverage of some non-empty factor x. By word_occurrence_coverage_subset, every occurrence coverage is a subset of {1, ..., length(thue_morse_word n)}.
uses
thue_morse_min_factor_coverages_finset_mem,word_min_factor_coverages_subset,word_factor_coverages,Set.mem_ofPred_eq,word_occurrence_coverage_subsethave hmem : C ∈ word_min_factor_coverages (thue_morse_word n) := (thue_morse_min_factor_coverages_finset_mem n C).mp hC have hsub : C ⊆ Finset.Icc 1 (thue_morse_word n).length := by have h := word_min_factor_coverages_subset (thue_morse_word n) hmem simp only [word_factor_coverages, Set.mem_ofPred_eq] at h obtain ⟨x, _, _, hxC⟩ := h rw [← hxC] exact word_occurrence_coverage_subset (thue_morse_word n) x
The size of C is at most 2^n.
Because C is a subset of {1, ..., length(thue_morse_word n)}, its cardinality is bounded by the cardinality of that interval (Finset.card_le_card). The interval [1, L] has cardinality L (Nat.card_Icc), and the length of the n-th Thue-Morse word is 2^n (thue_morse_word_length), giving |C| ≤ 2^n.
uses
Finset.card_le_card,Nat.card_Icc,thue_morse_word_lengthhave hcard : C.card ≤ 2^n := by have := Finset.card_le_card hsub rwa [Nat.card_Icc, thue_morse_word_length] at this
The ratio |C| / 2^n is at most 1, completing the proof.
Since 2^n > 0 (by positivity), |C| / 2^n ≤ 1 is equivalent to |C| ≤ 2^n (div_le_one). Casting the previously established bound |C| ≤ 2^n to the real numbers finishes the proof.
uses
div_le_onehave h2pos : (0:ℝ) < 2^n := by positivity rw [div_le_one h2pos] exact_mod_cast hcard
Finset.sum_nonneg- A finite sum of nonnegative terms is nonnegative.
pow_nonneg- A natural power of a nonnegative real number is nonnegative.
sub_nonneg- 0 ≤ a - b is equivalent to b ≤ a.
thue_morse_min_factor_coverages_finset_mem- Membership in the finset of minimal factor coverages of the n-th Thue-Morse word is equivalent to membership in the set of minimal factor coverages.
word_min_factor_coverages_subset- Every minimal factor coverage of a word is a factor coverage.
word_factor_coverages- The set of factor coverages of a word consists of occurrence coverages of non-empty factors of the word.
Set.mem_ofPred_eq- Membership in a set comprehension {y | p y} is equivalent to p holding for that element.
word_occurrence_coverage_subset- The occurrence coverage of any factor of a word w is a subset of the positions {1, ..., length(w)}.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Nat.card_Icc- The number of integers in the discrete interval [a, b] is b + 1 - a.
thue_morse_word_length- The length of the n-th Thue-Morse word is 2^n.
div_le_one- For positive b, a / b ≤ 1 is equivalent to a ≤ b.
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 expected unhit count is nonnegative, because every minimal coverage has size at most 2^n. -/theorem thue_morse_unhit_mean_nonneg (n k : ℕ) : 0 ≤ thue_morse_unhit_mean n k := by unfold thue_morse_unhit_mean apply Finset.sum_nonneg intro C hC apply pow_nonneg rw [sub_nonneg] have hmem : C ∈ word_min_factor_coverages (thue_morse_word n) := (thue_morse_min_factor_coverages_finset_mem n C).mp hC have hsub : C ⊆ Finset.Icc 1 (thue_morse_word n).length := by have h := word_min_factor_coverages_subset (thue_morse_word n) hmem simp only [word_factor_coverages, Set.mem_ofPred_eq] at h obtain ⟨x, _, _, hxC⟩ := h rw [← hxC] exact word_occurrence_coverage_subset (thue_morse_word n) x have hcard : C.card ≤ 2^n := by have := Finset.card_le_card hsub rwa [Nat.card_Icc, thue_morse_word_length] at this have h2pos : (0:ℝ) < 2^n := by positivity rw [div_le_one h2pos] exact_mod_cast hcard