AFTD Auto-Formalizing Theoretical Domains

op_1458_rich_repetition_threshold_le_asymptotic_of_projection

theoremverifiedformalization

For any integer d ≥ 2, if there exist a morphism π : Fin (2 * d - 1) → List (Fin d) and an infinite word z : ℕ → Fin d such that z is the morphic image of u_{2d-1} under π, z is uniformly recurrent and rich in palindromes, and the critical exponent of z equals the asymptotic critical exponent of u_{2d-1}, then the repetition threshold RT(C_d) is at most the asymptotic critical exponent of u_{2d-1}.

Statement

theorem op_1458_rich_repetition_threshold_le_asymptotic_of_projection
    (d : ℕ) (hd : 2 ≤ d)
    (π : Fin (2 * d - 1) → List (Fin d)) (z : ℕ → Fin d)
    (hz_morph : is_morphic_image z π (u_word (2 * d - 1) (by omega)))
    (hz_rec : is_uniformly_recurrent_word z)
    (hz_rich : is_rich_word z)
    (hz_crit : word_critical_exponent z = word_asymptotic_critical_exponent (u_word (2 * d - 1) (by omega))) :
    rich_repetition_threshold d ≤ word_asymptotic_critical_exponent (u_word (2 * d - 1) (by omega))
Formalizes
arXiv:2611.13676 Sec. 8, item 1
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • u_wordFor a positive integer k with proof hk : 0 < k, the infinite word u_word k hk : ℕ → Fin k is the fixed point of phi_morphism k, where the…
  • word_asymptotic_critical_exponentThe asymptotic critical exponent of an infinite word w is the real number defined as the real infimum (sInf) over all natural numbers N ≥…
  • word_critical_exponentThe critical exponent of an infinite word w : ℕ → α is the supremum over all nonempty words x and factors y of w that are prefixes of…
  • rich_repetition_thresholdThe repetition threshold RT(C_d) for d-ary rich words is the infimum of the set S_d of critical exponents of uniformly recurrent d-ary…
  • is_morphic_imageAn infinite word z is the morphic image of an infinite word w under f : α → List β if for every n, applying f to the prefix of length n of…
  • is_rich_wordAn infinite word w is rich in palindromes if every complete return word to a palindromic factor of w is itself a palindrome.
  • is_uniformly_recurrent_wordAn infinite word w : ℕ → α is uniformly recurrent if for every finite factor u of w, there exists a bound N such that every window of…
  • rich_word_critical_exponentsFor any positive integer d, the set S_d of critical exponents of uniformly recurrent d-ary rich words is the collection of all real…

Read back from the Lean

Let d be a natural number such that 2 ≤ d. Let π : Fin (2 * d - 1) → List (Fin d) and z : ℕ → Fin d. Assume: 1. hz_morph: z is a morphic image under π of u_word (2 * d - 1) _ (i.e., for every n : ℕ, applying π via flatMap to the prefix of length n of u_word (2 * d - 1) _ equals the prefix of z of the same length). 2. hz_rec: z is a uniformly recurrent word (for every factor u of z, there is an N : ℕ such that for every k : ℕ, an occurrence of u begins at some index j with k ≤ j ≤ k + N). 3. hz_rich: z is a rich word (for all lists c and q, if q is a palindrome, c is a complete return word to q, and c is a factor of z, then c is a palindrome). 4. hz_crit: the critical exponent of z equals the asymptotic critical exponent of u_word (2 * d - 1) _. Then the rich repetition threshold of d (the infimum of the critical exponents of uniformly recurrent rich words over Fin d) is less than or equal to the asymptotic critical exponent of u_word (2 * d - 1) _.

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 rich repetition threshold RT(C_d) is defined as the infimum of the critical exponents of all uniformly recurrent rich infinite words over d letters. Since z is assumed to be uniformly recurrent and rich, its critical exponent is an element of this set. Furthermore, every critical exponent is a supremum of non-negative length ratios, so the set is bounded below by 0. Therefore, the infimum RT(C_d) is at most the critical exponent of z, which equals the asymptotic critical exponent of u_{2d-1} by hypothesis.

  1. The index 2d - 1 is strictly positive. automation

    The definition of the infinite word u_{2d-1} requires a proof that its alphabet size 2d - 1 is strictly positive. In the theorem signature (lines 5, 8, and 9), this positivity condition is discharged by linear integer arithmetic (`omega`) using the assumption d ≥ 2.

    lines 5–9

        (hz_morph : is_morphic_image z π (u_word (2 * d - 1) (by omega)))
        (hz_rec : is_uniformly_recurrent_word z)
        (hz_rich : is_rich_word z)
        (hz_crit : word_critical_exponent z = word_asymptotic_critical_exponent (u_word (2 * d - 1) (by omega))) :
        rich_repetition_threshold d ≤ word_asymptotic_critical_exponent (u_word (2 * d - 1) (by omega)) := by
  2. The set of critical exponents of uniformly recurrent rich words over an alphabet of size d is bounded below by 0.

    We exhibit 0 as a lower bound for `rich_word_critical_exponents d`. Any element e in this set is the critical exponent of some uniformly recurrent rich word w, defined as the supremum of ratios |y| / |x| for non-empty factors x where y is a factor of w that is a prefix of some power of x. For each such ratio, since x is non-empty, List.length_pos_iff.mpr shows |x| > 0, and hence |y| / |x| ≥ 0. By Real.sSup_nonneg, the supremum of these non-negative ratios is non-negative, so e ≥ 0.

    lines 10–18

    uses List.length_pos_iff.mpr, Real.sSup_nonneg

      have hbdd : BddBelow (rich_word_critical_exponents d) := by
        refine ⟨0, ?_⟩
        rintro e ⟨w, -, -, rfl⟩
        exact Real.sSup_nonneg (by
          rintro q ⟨x, y, m, hx, -, -, rfl⟩
          have hxpos : (0 : ℝ) < (x.length : ℝ) := by
            have : 0 < x.length := List.length_pos_iff.mpr hx
            exact_mod_cast this
          positivity)
  3. The critical exponent of z belongs to the set of critical exponents of uniformly recurrent rich words over d letters.

    By hypotheses `hz_rec` and `hz_rich`, z is uniformly recurrent and rich. Packaging z together with these two properties directly witnesses the existential definition of `rich_word_critical_exponents d`.

    lines 19–20

      have hmem : word_critical_exponent z ∈ rich_word_critical_exponents d :=
        ⟨z, hz_rec, hz_rich, rfl⟩
  4. The rich repetition threshold RT(C_d) is at most the asymptotic critical exponent of u_{2d-1}.

    Rewriting via the hypothesis `hz_crit`, it suffices to show that RT(C_d) ≤ word_critical_exponent z. Since RT(C_d) is defined as the infimum of `rich_word_critical_exponents d`, which is bounded below by `hbdd` and contains word_critical_exponent z by `hmem`, csInf_le concludes that the infimum is at most this member.

    lines 21–22

    uses csInf_le

      rw [← hz_crit]
      exact csInf_le hbdd hmem
List.length_pos_iff.mpr
A list has strictly positive length if it is non-empty.
Real.sSup_nonneg
The supremum of a set of non-negative real numbers is non-negative.
csInf_le
In a conditionally complete lattice, the infimum of a set bounded below is less than or equal to any element of that set.

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 upper bound RT(C_d) ≤ E*(u_{2d-1}) follows from the existence of a uniformly recurrent rich projection. -/theorem op_1458_rich_repetition_threshold_le_asymptotic_of_projection    (d : ℕ) (hd : 2 ≤ d)    (π : Fin (2 * d - 1) → List (Fin d)) (z : ℕ → Fin d)    (hz_morph : is_morphic_image z π (u_word (2 * d - 1) (by omega)))    (hz_rec : is_uniformly_recurrent_word z)    (hz_rich : is_rich_word z)    (hz_crit : word_critical_exponent z = word_asymptotic_critical_exponent (u_word (2 * d - 1) (by omega))) :    rich_repetition_threshold d ≤ word_asymptotic_critical_exponent (u_word (2 * d - 1) (by omega)) := by  have hbdd : BddBelow (rich_word_critical_exponents d) := by    refine ⟨0, ?_⟩    rintro e ⟨w, -, -, rfl⟩    exact Real.sSup_nonneg (by      rintro q ⟨x, y, m, hx, -, -, rfl⟩      have hxpos : (0 : ℝ) < (x.length : ℝ) := by        have : 0 < x.length := List.length_pos_iff.mpr hx        exact_mod_cast this      positivity)  have hmem : word_critical_exponent z ∈ rich_word_critical_exponents d :=    ⟨z, hz_rec, hz_rich, rfl⟩  rw [← hz_crit]  exact csInf_le hbdd hmem
See it in the graphDiscuss this resultChallenge it