AFTD Auto-Formalizing Theoretical Domains

thue_morse_unhit_mean_nonneg

theoremverified

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.

  1. 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).

    lines 3–7

    uses Finset.sum_nonneg, pow_nonneg, sub_nonneg

      unfold thue_morse_unhit_mean
      apply Finset.sum_nonneg
      intro C hC
      apply pow_nonneg
      rw [sub_nonneg]
  2. 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)}.

    lines 8–15

    uses thue_morse_min_factor_coverages_finset_mem, word_min_factor_coverages_subset, word_factor_coverages, Set.mem_ofPred_eq, word_occurrence_coverage_subset

      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
  3. 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.

    lines 16–18

    uses Finset.card_le_card, Nat.card_Icc, thue_morse_word_length

      have hcard : C.card ≤ 2^n := by
        have := Finset.card_le_card hsub
        rwa [Nat.card_Icc, thue_morse_word_length] at this
  4. 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.

    lines 19–21

    uses div_le_one

      have 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

/-- 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
See it in the graphDiscuss this resultChallenge it