AFTD Auto-Formalizing Theoretical Domains

thue_morse_random_attractor_prob_mem_unit_interval

theoremverified

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.

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

    lines 4–6

    uses Set.mem_Icc

      rw [Set.mem_Icc]
      unfold thue_morse_random_attractor_prob
      constructor
  2. 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.

    line 7

      · positivity
  3. The 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.

    lines 8–10

    uses div_le_one

      · have hpos : 0 < ((2 : ℝ) ^ n) ^ k := by positivity
        rw [div_le_one hpos]
        norm_cast
  4. 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`.

    lines 11–12

    uses le_trans, Finset.card_le_univ

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

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

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