AFTD Auto-Formalizing Theoretical Domains

is_longest_word_run_of_constant

theoremverified

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.

  1. 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.

    line 4

    uses is_word_run_of_constant

      refine ⟨is_word_run_of_constant y hconst hn, ?_⟩
  2. 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.

    lines 5–7

      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

/-- 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
See it in the graphDiscuss this resultChallenge it