op_1537_binary_length_two_one_deletion
For any nonconstant binary word y : Fin 2 → Fin 2 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 2 2 r y ≤ qary_multiple_deletion_hinge 1 2 2 r y' for all r ≥ 1, with strict inequality for at least one r ≥ 1.
Statement
theorem op_1537_binary_length_two_one_deletion (y : Fin 2 → Fin 2) (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 2 2 r y ≤ qary_multiple_deletion_hinge 1 2 2 r y') ∧ (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 2 2 r y < qary_multiple_deletion_hinge 1 2 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_binary_length_two_one_deletionFor every binary word y of length 2 (y : Fin 2 → Fin 2), 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 binary word $y$ of length 2 (a function $y : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 2$) that is not constant (i.e., not all of its characters are equal), there exist natural numbers $a, b$, a proof that $[a, b)$ is a longest maximal run of identical symbols in $y$, natural numbers $a', b'$, a proof that $[a', b')$ is a maximal run of identical symbols in $y$, a proof that the two runs are adjacent ($b' = a$ or $b = a'$), and a bound $a < 2$, such that: defining $y' : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ 2$ as the word obtained from $y$ by replacing the characters at indices in $[a', b')$ with $y(a)$, 1. for all natural numbers $r \ge 1$, the 1-deletion $r$-hinge sum of $y$ is at most that of $y'$, and 2. for some natural number $r \ge 1$, the 1-deletion $r$-hinge sum of $y$ is strictly less than that 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
For any nonconstant binary word y of length 2, the two letters y(0) and y(1) are distinct, so the intervals [0, 1) and [1, 2) form adjacent runs of length 1, with [0, 1) being a longest run. Absorbing the adjacent run [1, 2) into the letter y(0) produces a constant word y'. The deletion hinge values are determined by exhaustive evaluation: for any nonconstant word of length 2 they are 2, 0, 0 for r = 1, 2, ≥ 3, whereas for any constant word they are 2, 1, 0. Comparing these values proves that the hinge function is nondecreasing for all r ≥ 1 and strictly increases at r = 2.
For nonconstant binary words of length 2, the deletion hinge values at r = 1 and r = 2 are 2 and 0 respectively; for constant words, they are 2 and 1. automation
Because there are only four binary words of length 2 and eight potential supersequences of length 3, the deletion hinge values for r = 1 and r = 2 on both constant and nonconstant words are evaluated directly by exhaustive computation via boolean reflection.
have hnc_vals : ∀ (z : Fin 2 → Fin 2), ¬ is_constant_word z → qary_multiple_deletion_hinge 1 2 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 2 2 2 z = 0 := by decide have hc_vals : ∀ (z : Fin 2 → Fin 2), is_constant_word z → qary_multiple_deletion_hinge 1 2 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 2 2 2 z = 1 := by decide
For any binary word z of length 2 and any threshold r ≥ 3, the deletion hinge value of z is 0.
Any word of length 3 has only (3 choose 2) = 3 subsequences of length 2, so the number of embeddings of any length-2 word into any length-3 word is at most 3. For r ≥ 3, every term in the hinge summation is at most 3 - r = 0, so each term vanishes and the entire sum over supersequences is 0.
uses
Finset.sum_eq_zero,Nat.sub_eq_zero_of_le,le_transhave hzero : ∀ (z : Fin 2 → Fin 2) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 2 2 r z = 0 := by intro z r hr have hbound : ∀ (x : Fin 3 → Fin 2) (w : Fin 2 → Fin 2), q_ary_subsequence_num_embeddings 2 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 positions of y have distinct letters: y(0) ≠ y(1).
If y(0) = y(1), then checking all four pairs of indices in {0, 1} shows that y(i) = y(j) everywhere, making y constant and contradicting the hypothesis that y is nonconstant.
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 the word y.
The single-element interval [0, 1) is a valid run because its boundary conditions hold: the left boundary is 0, and the right adjacent letter y(1) differs from y(0) since y(0) ≠ y(1). Furthermore, it is a longest run: any run [a', b') has length b' - a' ≤ 1, because if b' - a' > 1 with 0 ≤ a' < b' ≤ 2, we would have a' = 0 and b' = 2, which would imply y(1) = y(0), a contradiction.
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 the word y.
The single-element interval [1, 2) is a valid run: it is contained in the range [0, 2], its only index is 1, its left adjacent letter y(0) differs from y(1), and its right boundary reaches the length of the word.
uses
Or.inl,Or.inr,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]
Choosing [0, 1) as the longest run and [1, 2) as the adjacent run, absorbing [1, 2) into the symbol y(0) yields a constant word y'.
The runs [0, 1) and [1, 2) meet the adjacency condition b = a' = 1. In the absorbed word y', the letter at index 1 is replaced by y(0), while the letter at index 0 remains y(0). Evaluating y' at both indices gives y(0), so y' is a constant word.
uses
Or.inrrefine ⟨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]
For all r ≥ 1, the deletion hinge value of y is less than or equal to that of y'.
We split into cases based on r. If r < 3, then r is either 1 or 2: at r = 1, both y (nonconstant) and y' (constant) have hinge value 2; at r = 2, y has hinge value 0 and y' has hinge value 1, so 0 ≤ 1. If r ≥ 3, the hinge value of y is 0, which is at most any natural number.
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 (specifically r = 2) where the deletion hinge value of y is strictly less than that of y'.
At r = 2, the nonconstant word y has hinge value 0 while the constant word y' has hinge value 1; since 0 < 1, the inequality is strict.
· 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 of terms is zero if every term in the sum is zero.
Nat.sub_eq_zero_of_le- For natural numbers, if n ≤ m, then truncated subtraction n - m equals 0.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Or.inl- A disjunction a ∨ b holds if the left disjunct a holds.
Or.inr- A disjunction a ∨ b holds if the right disjunct b holds.
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 a natural number leaves it unchanged: n - 0 = n.
not_le.mp- In a linear order, if a is not less than or equal to b, then b is strictly less than a.
lt_or_ge- In a linear order, for any two elements a and b, either a < b or b ≤ a.
Nat.zero_le- Zero is less than or equal to any natural number: 0 ≤ n.
- The hinge values for r = 1 and r = 2, as well as the upper bound on the number of subsequence embeddings of length-2 words into length-3 words, are verified by exhaustive finite evaluation via the decide tactic.
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 binary words of length 2 with one deletion (n = 2, q = 2, t = 1). -/theorem op_1537_binary_length_two_one_deletion (y : Fin 2 → Fin 2) (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 2 2 r y ≤ qary_multiple_deletion_hinge 1 2 2 r y') ∧ (∃ r : ℕ, 1 ≤ r ∧ qary_multiple_deletion_hinge 1 2 2 r y < qary_multiple_deletion_hinge 1 2 2 r y') := by have hnc_vals : ∀ (z : Fin 2 → Fin 2), ¬ is_constant_word z → qary_multiple_deletion_hinge 1 2 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 2 2 2 z = 0 := by decide have hc_vals : ∀ (z : Fin 2 → Fin 2), is_constant_word z → qary_multiple_deletion_hinge 1 2 2 1 z = 2 ∧ qary_multiple_deletion_hinge 1 2 2 2 z = 1 := by decide have hzero : ∀ (z : Fin 2 → Fin 2) (r : ℕ), 3 ≤ r → qary_multiple_deletion_hinge 1 2 2 r z = 0 := by intro z r hr have hbound : ∀ (x : Fin 3 → Fin 2) (w : Fin 2 → Fin 2), q_ary_subsequence_num_embeddings 2 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