op_1537_ternary_length_two_one_deletion
For any nonconstant ternary word y : Fin 2 → Fin 3 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run [a', b') of y such that the word y' obtained by changing every letter in [a', b') to y a satisfies qary_multiple_deletion_hinge 1 3 2 r y ≤ qary_multiple_deletion_hinge 1 3 2 r y' for all r ≥ 1, with strict inequality for at least one r ≥ 1.
Statement
theorem op_1537_ternary_length_two_one_deletion (y : Fin 2 → Fin 3) (hy : ¬ is_constant_word y) : ∃ (a b : ℕ) (hR : is_longest_word_run y a b) (a' b' : ℕ) (hR' : is_word_run y a' b') (hadj : b' = a ∨ b = a') (ha : a < 2), let y' := word_absorb_run y a' b' (y ⟨a, ha⟩) (∀ r : ℕ, 1 ≤ r → qary_multiple_deletion_hinge 1 3 2 r y ≤ qary_multiple_deletion_hinge 1 3 2 r y') ∧ (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 3 2 r y < qary_multiple_deletion_hinge 1 3 2 r y')
- Related work
- knowledgebase (OP-1537, OP-1534)
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_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',…
- word_absorb_runThe word obtained from y : Fin n → α by changing every letter in the index interval [a', b') to c, leaving all letters outside the…
- qary_multiple_deletion_hingeFor natural numbers t, q, n, and r, and a q-ary word y of length n (y : Fin n → Fin q), the t-deletion hinge sum is the sum over all words…
- 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.
- op_1534_ternary_length_two_one_deletionFor every ternary word y of length 2 (y : Fin 2 → Fin 3), the one-deletion hinge sums at thresholds r = 1 and r = 2 satisfy…
- decidable_is_constant_wordDecidability instance for the predicate that a word on Fin n over a type with decidable equality is constant.
- q_ary_subsequence_num_embeddingsFor words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is…
Read back from the Lean
For every ternary word $y : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 3$ of length 2 that is not constant (i.e. not all its symbols are equal), there exist natural numbers $a$ and $b$ such that the interval $[a, b)$ is a longest maximal run of identical symbols in $y$, and there exist natural numbers $a'$ and $b'$ such that $[a', b')$ is a maximal run of identical symbols in $y$, such that: 1. The two runs are adjacent (either $b' = a$ or $b = a'$); 2. $a < 2$; and 3. Letting $y'$ be the word obtained by replacing the symbols of $y$ on the index interval $[a', b')$ with the symbol $y(a)$ (the "absorbed" word): - For all natural numbers $r \ge 1$, the 1-deletion ternary hinge sum of $y$ with threshold $r$ is less than or equal to that of $y'$, i.e., $$\sum_{x \in (\mathrm{Fin}\ 3)^3} \max(0, \mathrm{emb}(y, x) - r) \le \sum_{x \in (\mathrm{Fin}\ 3)^3} \max(0, \mathrm{emb}(y', x) - r),$$ where $\mathrm{emb}(u, x)$ is the number of strictly monotone functions $f : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 3$ such that $x \circ f = u$; and - There exists a natural number $r \ge 1$ for which this inequality is strict ($<$).
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 theorem proves OP-1537 in the base case of length-2 ternary words with 1 deletion (n = 2, q = 3, t = 1). Because y is nonconstant of length 2, its two letters must differ, meaning y decomposes into two adjacent singleton runs [0, 1) and [1, 2). Absorbing the second run into the letter y(0) produces a constant word y'. By exhaustive finite evaluation, the deletion hinge values for nonconstant versus constant words are identical at r = 1 (both equal 2), strictly greater for constant words at r = 2 (0 versus 1), and vanish for both when r ≥ 3 because embedding counts cannot exceed 3. Consequently, the hinge value never decreases and strictly increases at r = 2.
For any ternary word of length 2, the deletion hinge at r = 1 is 2; at r = 2, the hinge is 0 if the word is nonconstant and 1 if the word is constant. automation
Since the domain Fin 2 → Fin 3 consists of only 3² = 9 words, Lean verifies both characterizations (`hnc_vals` and `hc_vals`) by exhaustive evaluation using the `decide` tactic.
have hnc_vals : ∀ (z : Fin 2 → Fin 3), ¬ is_constant_word z → qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 0 := by decide have hc_vals : ∀ (z : Fin 2 → Fin 3), is_constant_word z → qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 1 := by decide
For any ternary word z of length 2 and any r ≥ 3, the deletion hinge value at r is 0.
Any supersequence x of length 3 can contain a length-2 word w as a subsequence at most (3 choose 2) = 3 times (`hbound`, checked by `decide`). In the definition of the hinge function, each term in the sum over all x is the truncated natural difference (embeddings - r). Since the number of embeddings is at most 3 ≤ r, each difference is 0 by `Nat.sub_eq_zero_of_le` and `le_trans`, so the entire sum is 0 by `Finset.sum_eq_zero`.
uses
Finset.sum_eq_zero,Nat.sub_eq_zero_of_le,le_transhave hzero : ∀ (z : Fin 2 → Fin 3) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 3 2 r z = 0 := by intro z r hr have hbound : ∀ (x : Fin 3 → Fin 3) (w : Fin 2 → Fin 3), q_ary_subsequence_num_embeddings 3 2 3 w x ≤ 3 := by decide unfold qary_multiple_deletion_hinge apply Finset.sum_eq_zero intro x _ apply Nat.sub_eq_zero_of_le exact le_trans (hbound x z) hr
The two characters of y are distinct: y(0) ≠ y(1).
Assume for contradiction that y(0) = y(1). Then y(i) = y(j) for all i, j ∈ {0, 1}, meaning y is a constant word. This contradicts the hypothesis that y is nonconstant (`hy`).
have hne : y ⟨0, by norm_num⟩ ≠ y ⟨1, by norm_num⟩ := by intro h apply hy intro i j fin_cases i <;> fin_cases j <;> simp_all
The interval [0, 1) is a longest run of y.
First, [0, 1) is a valid run (`is_word_run`): its only index is 0, it starts at 0, and its right endpoint 1 has a distinct symbol y(1) ≠ y(0) by `hne`. Second, it is a longest run: any run [a', b') of y has length b' - a' ≤ 2. If b' - a' > 1, then a' = 0 and b' = 2, which would imply y(1) = y(0), contradicting `hne`. Hence every run has length at most 1 - 0 = 1.
uses
Or.inl,Or.inr,Ne.symm,Fin.ext,Nat.sub_zero,not_le.mphave hR : is_longest_word_run y 0 1 := by have hrun : is_word_run y 0 1 := by refine ⟨by norm_num, by norm_num, ?_, Or.inl rfl, Or.inr ⟨by norm_num, Ne.symm hne⟩⟩ intro i hi obtain ⟨-, hi2⟩ := hi have hi0 : i = ⟨0, by norm_num⟩ := by apply Fin.ext simp only omega rw [hi0] refine ⟨hrun, ?_⟩ intro a' b' hr' obtain ⟨hab, hbn, hconst, -, -⟩ := hr' simp only [Nat.sub_zero] by_contra h have h2 : 1 < b' - a' := not_le.mp h have ha' : a' = 0 := by omega have hb' : b' = 2 := by omega subst ha' subst hb' have h1 : y ⟨1, by norm_num⟩ = y ⟨0, by norm_num⟩ := by have := hconst ⟨1, by norm_num⟩ ⟨by norm_num, by norm_num⟩ simpa using this exact hne h1.symm
The interval [1, 2) is a run of y.
The interval [1, 2) contains only the index 1, its left endpoint is preceded by y(0) ≠ y(1), and its right endpoint is the end of the word (n = 2). Thus [1, 2) satisfies all conditions of `is_word_run`.
uses
Or.inr,Or.inl,Fin.exthave hR' : is_word_run y 1 2 := by refine ⟨by norm_num, by norm_num, ?_, Or.inr ⟨by norm_num, hne⟩, Or.inl rfl⟩ intro i hi obtain ⟨hi1, -⟩ := hi have hii : i = ⟨1, by norm_num⟩ := by apply Fin.ext simp only omega rw [hii]
Instantiate the existential witnesses with a = 0, b = 1 (the longest run) and a' = 1, b' = 2 (the adjacent run).
We supply the witnesses a = 0, b = 1, the proof `hR` that [0, 1) is a longest run, a' = 1, b' = 2, the proof `hR'` that [1, 2) is a run, the adjacency b = a' = 1 via `Or.inr rfl`, and the bound a < 2.
uses
Or.inrrefine ⟨0, 1, hR, 1, 2, hR', Or.inr rfl, by norm_num, ?_⟩ dsimp only
The word y' obtained by absorbing run [1, 2) into y(0) is a constant word.
For every index i ∈ {0, 1}, y'(i) = y(0): at index 0, it falls outside [1, 2) so it retains y(0); at index 1, it falls inside [1, 2) so it is overwritten with y(0). Therefore, y'(i) = y'(j) = y(0) for all i, j, showing y' is constant.
have hy'const : is_constant_word (word_absorb_run y 1 2 (y ⟨0, by norm_num⟩)) := by intro i j have hi : ∀ i : Fin 2, word_absorb_run y 1 2 (y ⟨0, by norm_num⟩) i = y ⟨0, by norm_num⟩ := by intro i fin_cases i <;> simp [word_absorb_run] rw [hi i, hi j]
For every r ≥ 1, the deletion hinge value satisfies hinge(y) ≤ hinge(y').
Split into cases using `lt_or_ge r 3`: if r < 3, then r = 1 or r = 2. For r = 1, both words give hinge value 2 by `hnc_vals` and `hc_vals`, so 2 ≤ 2. For r = 2, hinge(y) = 0 ≤ 1 = hinge(y'). For r ≥ 3, `hzero` shows hinge(y) = 0, which is ≤ hinge(y') by `Nat.zero_le`.
uses
lt_or_ge,Nat.zero_leconstructor · intro r hr rcases lt_or_ge r 3 with h3 | h3 · have : r = 1 ∨ r = 2 := by omega rcases this with rfl | rfl · rw [(hnc_vals y hy).1, (hc_vals _ hy'const).1] · rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2] norm_num · rw [hzero y r h3] exact Nat.zero_le _
There exists r ≥ 1 such that hinge(y) < hinge(y'), specifically at r = 2.
Taking r = 2, we have 1 ≤ 2, and the hinge values are hinge(y) = 0 and hinge(y') = 1 by `hnc_vals` and `hc_vals`. Since 0 < 1, the strict inequality holds.
· refine ⟨2, by norm_num, ?_⟩ rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2] norm_num
Finset.sum_eq_zero- A finite sum is zero if every term in the sum is zero.
Nat.sub_eq_zero_of_le- For natural numbers n and m, if n ≤ m, then their truncated difference n - m is 0.
le_trans- The order relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Or.inl- Proves a disjunction a ∨ b from a proof of its left conjunct a.
Or.inr- Proves a disjunction a ∨ b from a proof of its right conjunct b.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Nat.sub_zero- Subtracting zero from any natural number leaves it unchanged (n - 0 = n).
not_le.mp- For natural numbers, if a ≰ b, then b < a.
lt_or_ge- In any linear order, either a < b or b ≤ a.
Nat.zero_le- Zero is less than or equal to any natural number (0 ≤ n).
- Evaluation of the deletion hinge values for all ternary words of length 2 (for r ∈ {1, 2} and the upper bound on embedding counts) is offloaded to Lean's `decide` tactic via exhaustive computation on finite domains.
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.
/-- OP-1537 for ternary words of length 2 with one deletion (n = 2, q = 3, t = 1). -/theorem op_1537_ternary_length_two_one_deletion (y : Fin 2 → Fin 3) (hy : ¬ is_constant_word y) : ∃ (a b : ℕ) (hR : is_longest_word_run y a b) (a' b' : ℕ) (hR' : is_word_run y a' b') (hadj : b' = a ∨ b = a') (ha : a < 2), let y' := word_absorb_run y a' b' (y ⟨a, ha⟩) (∀ r : ℕ, 1 ≤ r → qary_multiple_deletion_hinge 1 3 2 r y ≤ qary_multiple_deletion_hinge 1 3 2 r y') ∧ (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 3 2 r y < qary_multiple_deletion_hinge 1 3 2 r y') := by have hnc_vals : ∀ (z : Fin 2 → Fin 3), ¬ is_constant_word z → qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 0 := by decide have hc_vals : ∀ (z : Fin 2 → Fin 3), is_constant_word z → qary_multiple_deletion_hinge 1 3 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 3 2 2 z = 1 := by decide have hzero : ∀ (z : Fin 2 → Fin 3) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 3 2 r z = 0 := by intro z r hr have hbound : ∀ (x : Fin 3 → Fin 3) (w : Fin 2 → Fin 3), q_ary_subsequence_num_embeddings 3 2 3 w x ≤ 3 := by decide unfold qary_multiple_deletion_hinge apply Finset.sum_eq_zero intro x _ apply Nat.sub_eq_zero_of_le exact le_trans (hbound x z) hr have hne : y ⟨0, by norm_num⟩ ≠ y ⟨1, by norm_num⟩ := by intro h apply hy intro i j fin_cases i <;> fin_cases j <;> simp_all have hR : is_longest_word_run y 0 1 := by have hrun : is_word_run y 0 1 := by refine ⟨by norm_num, by norm_num, ?_, Or.inl rfl, Or.inr ⟨by norm_num, Ne.symm hne⟩⟩ intro i hi obtain ⟨-, hi2⟩ := hi have hi0 : i = ⟨0, by norm_num⟩ := by apply Fin.ext simp only omega rw [hi0] refine ⟨hrun, ?_⟩ intro a' b' hr' obtain ⟨hab, hbn, hconst, -, -⟩ := hr' simp only [Nat.sub_zero] by_contra h have h2 : 1 < b' - a' := not_le.mp h have ha' : a' = 0 := by omega have hb' : b' = 2 := by omega subst ha' subst hb' have h1 : y ⟨1, by norm_num⟩ = y ⟨0, by norm_num⟩ := by have := hconst ⟨1, by norm_num⟩ ⟨by norm_num, by norm_num⟩ simpa using this exact hne h1.symm have hR' : is_word_run y 1 2 := by refine ⟨by norm_num, by norm_num, ?_, Or.inr ⟨by norm_num, hne⟩, Or.inl rfl⟩ intro i hi obtain ⟨hi1, -⟩ := hi have hii : i = ⟨1, by norm_num⟩ := by apply Fin.ext simp only omega rw [hii] refine ⟨0, 1, hR, 1, 2, hR', Or.inr rfl, by norm_num, ?_⟩ dsimp only have hy'const : is_constant_word (word_absorb_run y 1 2 (y ⟨0, by norm_num⟩)) := by intro i j have hi : ∀ i : Fin 2, word_absorb_run y 1 2 (y ⟨0, by norm_num⟩) i = y ⟨0, by norm_num⟩ := by intro i fin_cases i <;> simp [word_absorb_run] rw [hi i, hi j] constructor · intro r hr rcases lt_or_ge r 3 with h3 | h3 · have : r = 1 ∨ r = 2 := by omega rcases this with rfl | rfl · rw [(hnc_vals y hy).1, (hc_vals _ hy'const).1] · rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2] norm_num · rw [hzero y r h3] exact Nat.zero_le _ · refine ⟨2, by norm_num, ?_⟩ rw [(hnc_vals y hy).2, (hc_vals _ hy'const).2] norm_num