op_1458_asymptotic_critical_exponent_le_critical_exponent
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.
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.
uses
le_csSup,Real.sSup_of_not_bddAboveby_cases h : BddAbove T · exact le_csSup h h0 · rw [Real.sSup_of_not_bddAbove h]
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.
uses
List.length_nil,List.length_replicate,List.nil_prefixrefine ⟨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
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.
uses
csInf_leunfold word_asymptotic_critical_exponent word_critical_exponent apply csInf_le
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.
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)
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.
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).
- In Mathlib, `sSup` on ℝ is defined to be 0 for sets that are not bounded above (via `Real.sSup_of_not_bddAbove`), which is why the non-negativity helper lemma considers whether the set is bounded above.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩