op_1458_rich_repetition_threshold_le_asymptotic_of_projection
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.
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.
(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
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.
uses
List.length_pos_iff.mpr,Real.sSup_nonneghave 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)
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`.
have hmem : word_critical_exponent z ∈ rich_word_critical_exponents d := ⟨z, hz_rec, hz_rich, rfl⟩
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.
uses
csInf_lerw [← 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.
- The tactics at lines 5, 8, and 9 are inline proofs (`by omega`) in the theorem signature establishing that 0 < 2 * d - 1 from d ≥ 2, which is required for the word u_{2d-1} to be well-formed.
- The hypothesis `hz_morph` (that z is a morphic image of u_{2d-1}) is not directly used in the proof body, as the equality between the critical exponent of z and the asymptotic critical exponent of u_{2d-1} is supplied directly as the hypothesis `hz_crit`.
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.
/-- 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