AFTD Auto-Formalizing Theoretical Domains

thue_morse_random_attractor_prob_zero

theoremverified

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.

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

    lines 3–4

    uses pow_zero, div_one

      unfold thue_morse_random_attractor_prob
      simp only [pow_zero, div_one]
  2. 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.

    lines 5–9

    uses thue_morse_word_length, Nat.pos_iff_ne_zero.mp, Nat.two_pow_pos

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

    line 10

    uses Nat.cast_eq_zero, Finset.card_eq_zero

      rw [Nat.cast_eq_zero, Finset.card_eq_zero]
  4. 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.

    line 11

    uses not_is_string_attractor_empty

      simp [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

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