is_longest_word_run_of_constant
For any constant word y on Fin n with 1 ≤ n, the interval [0, n) is a longest run of y.
Statement
theorem is_longest_word_run_of_constant {n : ℕ} {α : Type*} (y : Fin n → α) (hconst : is_constant_word y) (hn : 1 ≤ n) : is_longest_word_run y 0 n
- Source
- folklore
- Verified
- 12 Nov 2026
- Axioms
Quot.soundpropext- Built on 4
- is_longest_word_runA run [a, b) of a word y : Fin n → α is a longest run if its length b - a is greater than or equal to the length b' - a' of every run [a',…
- is_word_runA pair of indices 0 ≤ a < b ≤ n forms a run [a, b) of a word y : Fin n → α if all symbols y i for a ≤ i < b are equal, and the block…
- is_constant_wordA word y on the finite index set Fin n is constant if all its symbols are equal, that is, y i = y j for all i and j in Fin n.
- is_word_run_of_constantFor any constant word y on Fin n with 1 ≤ n, the full interval [0, n) is a run of y.
Read back from the Lean
For any natural number $n$ and any type $\alpha$, let $y : \mathrm{Fin}\ n \to \alpha$. If $y$ is a constant word (i.e., $y(i) = y(j)$ for all $i, j : \mathrm{Fin}\ n$) and $1 \le n$, then the interval $[0, n)$ is a longest word run of $y$.
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
To show that [0, n) is a longest run of a constant word y of length n ≥ 1, we show that it is a run and that its length bounds that of any run. The lemma `is_word_run_of_constant` establishes that [0, n) is indeed a run. Any other run [a', b') must be contained within the domain, so b' ≤ n and a' ≥ 0, which implies b' - a' ≤ n - 0.
The interval [0, n) is a valid word run of y, reducing the goal to showing that no word run is longer.
By definition, [0, n) is a longest word run if it is a word run and every word run [a', b') satisfies b' - a' ≤ n - 0. The first part is provided directly by `is_word_run_of_constant`, leaving the maximality condition as the remaining goal.
uses
is_word_run_of_constantrefine ⟨is_word_run_of_constant y hconst hn, ?_⟩Any word run [a', b') satisfies b' - a' ≤ n - 0.
Let [a', b') be an arbitrary word run of y. By definition of `is_word_run`, we have a' < b' and b' ≤ n. Since natural numbers are non-negative, 0 ≤ a' and b' ≤ n immediately imply b' - a' ≤ n - 0, which linear arithmetic (`omega`) closes.
intro a' b' hr obtain ⟨hab, hbn, _⟩ := hr omega
is_word_run_of_constant- For any constant word y on Fin n with 1 ≤ n, the interval [0, n) is a word run of y.
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.
/-- For any constant word on Fin n with 1 ≤ n, the interval [0, n) is a longest run. -/theorem is_longest_word_run_of_constant {n : ℕ} {α : Type*} (y : Fin n → α) (hconst : is_constant_word y) (hn : 1 ≤ n) : is_longest_word_run y 0 n := by refine ⟨is_word_run_of_constant y hconst hn, ?_⟩ intro a' b' hr obtain ⟨hab, hbn, _⟩ := hr omega