AFTD Auto-Formalizing Theoretical Domains

op_1458_asymptotic_critical_exponent_le_critical_exponent

theoremverifiedformalization

For every infinite word w, the asymptotic critical exponent of w is at most the critical exponent of w in ℝ.

Statement

theorem op_1458_asymptotic_critical_exponent_le_critical_exponent {α : Type*} (w : ℕ → α) :
    word_asymptotic_critical_exponent w ≤ word_critical_exponent w
Formalizes
arXiv:2611.13676 Sec. 1
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…

Read back from the Lean

For any type α and any infinite word w : ℕ → α, the asymptotic critical exponent of w is less than or equal to the critical exponent of w. Here: - The **critical exponent** of w is defined as the real supremum (sSup) of all ratios (y.length : ℝ) / (x.length : ℝ) such that x, y : List α, x ≠ [], y is a factor of w (i.e., y equals the subword of w of length y.length starting at some index i : ℕ), and y is a prefix of x^m ((List.replicate m x).flatten) for some m : ℕ. - The **asymptotic critical exponent** of w is defined as the real infimum (sInf) over all N : ℕ with 1 ≤ N of the real supremum of the same ratios (y.length : ℝ) / (x.length : ℝ) with the additional constraint that N ≤ x.length.

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 asymptotic critical exponent of an infinite word w is defined as the infimum over N ≥ 1 of the suprema of repetition exponents with period length at least N, whereas the critical exponent is the supremum over all non-empty periods. The critical exponent corresponds exactly to the term N = 1, because a list is non-empty if and only if its length is at least 1. Since the empty factor always witnesses that 0 is an exponent, each supremum is non-negative and the family of suprema is bounded below by 0. By the defining property of the infimum, the infimum of this bounded-below family is at most its N = 1 member, which is the critical exponent.

  1. If a set of real numbers contains 0, its supremum is at least 0.

    We split into cases on whether the set T is bounded above. If T is bounded above, then since 0 ∈ T, 0 ≤ sSup T by `le_csSup`. If T is not bounded above, Mathlib defines sSup T = 0 (`Real.sSup_of_not_bddAbove`), which is also non-negative.

    lines 3–5

    uses le_csSup, Real.sSup_of_not_bddAbove

      by_cases h : BddAbove T
      · exact le_csSup h h0
      · rw [Real.sSup_of_not_bddAbove h]
  2. For any integer N ≥ 1, the exponent 0 belongs to the set of repetition exponents with period length at least N in w.

    We witness the existential quantifiers by choosing period x to be N copies of w(0), factor y to be the empty list, and exponent power m = 0. Since N ≥ 1, x is non-empty (`List.length_nil`, `List.length_replicate`) and has length N ≥ N. The empty list y is trivially a factor starting at index 0, is a prefix of any list (`List.nil_prefix`), and yields the exponent |y|/|x| = 0 / N = 0.

    lines 12–21

    uses List.length_nil, List.length_replicate, List.nil_prefix

      refine ⟨List.replicate N (w 0), [], 0, ?_, ?_, ?_, ?_, ?_⟩
      · intro h
        have : (List.replicate N (w 0)).length = 0 := by rw [h, List.length_nil]
        rw [List.length_replicate] at this
        omega
      · simp
      · refine ⟨0, ?_⟩
        simp
      · exact List.nil_prefix
      · simp
  3. To show that the asymptotic critical exponent is at most the critical exponent, it suffices to show that the family of suprema is bounded below and contains the critical exponent.

    Unfolding definitions, the asymptotic critical exponent is the infimum over N ≥ 1 of the suprema of exponents with period length at least N, while the critical exponent is the supremum over all non-empty periods. By `csInf_le`, the infimum of a set bounded below is bounded from above by any of its members.

    lines 26–27

    uses csInf_le

      unfold word_asymptotic_critical_exponent word_critical_exponent
      apply csInf_le
  4. The set of suprema indexed by N ≥ 1 is bounded below by 0.

    For any N ≥ 1, the exponent 0 belongs to the set of exponents with period length at least N by `op_1458_asymptotic_critical_exponent_le_critical_exponent_zero_mem`. By `op_1458_asymptotic_critical_exponent_le_critical_exponent_sSup_nonneg`, the supremum of this set is therefore non-negative, showing 0 is a lower bound.

    lines 28–31

    uses op_1458_asymptotic_critical_exponent_le_critical_exponent_sSup_nonneg, op_1458_asymptotic_critical_exponent_le_critical_exponent_zero_mem

      · refine ⟨0, ?_⟩
        rintro r ⟨N, hN, rfl⟩
        exact op_1458_asymptotic_critical_exponent_le_critical_exponent_sSup_nonneg
          (op_1458_asymptotic_critical_exponent_le_critical_exponent_zero_mem w N hN)
  5. The critical exponent belongs to the family of suprema as the member corresponding to N = 1.

    We choose N = 1, which satisfies 1 ≤ 1 by reflexivity (`le_rfl`). It remains to show that the set of exponents for all non-empty periods coincides with the set for period length at least 1. For any list x, x ≠ [] is equivalent to 1 ≤ x.length, as verified by case analysis on whether x is nil or cons. Thus the two sets of exponents are identical, so their suprema coincide.

    lines 32–43

    uses le_rfl

      · refine ⟨1, le_rfl, ?_⟩
        congr 1
        ext e
        constructor
        · rintro ⟨x, y, m, hx, hy, hpref, he⟩
          have h1 : 1 ≤ x.length := by
            cases x
            · contradiction
            · simp
          exact ⟨x, y, m, hx, h1, hy, hpref, he⟩
        · rintro ⟨x, y, m, hx, h1, hy, hpref, he⟩
          exact ⟨x, y, m, hx, hy, hpref, he⟩
le_csSup
In a conditionally complete lattice such as ℝ, any element of a set bounded above is less than or equal to the supremum of the set.
Real.sSup_of_not_bddAbove
The supremum of a set of real numbers that is not bounded above is defined to be 0.
List.length_nil
The length of the empty list is 0.
List.length_replicate
Replicating an element n times produces a list of length n.
List.nil_prefix
The empty list is a prefix of every list.
csInf_le
In a conditionally complete lattice, the infimum of a set bounded below is less than or equal to any element in the set.
op_1458_asymptotic_critical_exponent_le_critical_exponent_sSup_nonneg
If a set of real numbers contains 0, its supremum is at least 0.
op_1458_asymptotic_critical_exponent_le_critical_exponent_zero_mem
For any infinite word w and any integer N ≥ 1, the exponent 0 belongs to the set of repetition exponents of factors of w with period length at least N.
le_rfl
In any preorder, every element is less than or equal to itself (reflexivity).

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

lemma op_1458_asymptotic_critical_exponent_le_critical_exponent_sSup_nonneg    {T : Set ℝ} (h0 : (0 : ℝ) ∈ T) : 0 ≤ sSup T := by  by_cases h : BddAbove T  · exact le_csSup h h0  · rw [Real.sSup_of_not_bddAbove h]lemma op_1458_asymptotic_critical_exponent_le_critical_exponent_zero_mem    {α : Type*} (w : ℕ → α) (N : ℕ) (hN : 1 ≤ N) :    (0 : ℝ) ∈ { e : ℝ | ∃ (x y : List α) (m : ℕ), x ≠ [] ∧ N ≤ x.length ∧      (∃ i : ℕ, y = (List.range y.length).map (fun j => w (i + j))) ∧      y <+: (List.replicate m x).flatten ∧ e = (y.length : ℝ) / (x.length : ℝ) } := by  refine ⟨List.replicate N (w 0), [], 0, ?_, ?_, ?_, ?_, ?_⟩  · intro h    have : (List.replicate N (w 0)).length = 0 := by rw [h, List.length_nil]    rw [List.length_replicate] at this    omega  · simp  · refine ⟨0, ?_⟩    simp  · exact List.nil_prefix  · simp/-- The asymptotic critical exponent is bounded from above by the critical exponent. -/theorem op_1458_asymptotic_critical_exponent_le_critical_exponent {α : Type*} (w : ℕ → α) :    word_asymptotic_critical_exponent w ≤ word_critical_exponent w := by  unfold word_asymptotic_critical_exponent word_critical_exponent  apply csInf_le  · refine ⟨0, ?_⟩    rintro r ⟨N, hN, rfl⟩    exact op_1458_asymptotic_critical_exponent_le_critical_exponent_sSup_nonneg      (op_1458_asymptotic_critical_exponent_le_critical_exponent_zero_mem w N hN)  · refine ⟨1, le_rfl, ?_⟩    congr 1    ext e    constructor    · rintro ⟨x, y, m, hx, hy, hpref, he⟩      have h1 : 1 ≤ x.length := by        cases x        · contradiction        · simp      exact ⟨x, y, m, hx, h1, hy, hpref, he⟩    · rintro ⟨x, y, m, hx, h1, hy, hpref, he⟩      exact ⟨x, y, m, hx, hy, hpref, he⟩
See it in the graphDiscuss this resultChallenge it