op_1534_ternary_length_two_one_deletion
For 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 qary_multiple_deletion_hinge 1 3 2 1 y ≤ qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) and qary_multiple_deletion_hinge 1 3 2 2 y ≤ qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide)), with equality holding simultaneously at r = 1 and r = 2 if and only if y is constant (is_constant_word y).
Statement
theorem op_1534_ternary_length_two_one_deletion (y : Fin 2 → Fin 3) : qary_multiple_deletion_hinge 1 3 2 1 y ≤ qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 3 2 2 y ≤ qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide)) ∧ ((qary_multiple_deletion_hinge 1 3 2 1 y = qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 3 2 2 y = qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide))) ↔ is_constant_word y)
- Related work
- arXiv:2407.10026 "Conditional entropies of k-deletion/insertion channels"
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- qary_all_zero_wordFor an alphabet size q with 1 ≤ q and length n, the all-zero word is the word in Fin n → Fin q taking constant value 0 (represented by ⟨0,…
- 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.
- decidable_is_constant_wordDecidability instance for the predicate that a word on Fin n over a type with decidable equality is constant.
- Used by 1
- op_1537_ternary_length_two_one_deletionFor 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…
Read back from the Lean
For every ternary word of length 2 (that is, every function y : Fin 2 → Fin 3):
1. The 1-hinge deletion quantity qary_multiple_deletion_hinge 1 3 2 1 y is less than or equal to qary_multiple_deletion_hinge 1 3 2 1 evaluated at the all-zero word qary_all_zero_word 3 2 _;
2. The 2-hinge deletion quantity qary_multiple_deletion_hinge 1 3 2 2 y is less than or equal to qary_multiple_deletion_hinge 1 3 2 2 evaluated at the all-zero word qary_all_zero_word 3 2 _;
3. Both quantities achieve equality with the all-zero word simultaneously if and only if y is a constant word (is_constant_word y, i.e., ∀ i j : Fin 2, y i = y j).
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 states that among ternary words of length 2, the one-deletion hinge sums at thresholds 1 and 2 are maximized by the all-zero word, with simultaneous equality if and only if the word is constant. After discharging the alphabet size condition 1 ≤ 3 in the statement, the proof generalizes over the word y and completes the verification by exhaustive finite computation via `decide`.
The alphabet size condition 1 ≤ 3 required to define the all-zero ternary word is satisfied. automation
The definition of `qary_all_zero_word 3 2` requires proof that the alphabet size is non-zero (specifically 1 ≤ 3) so that the symbol 0 is a valid element of Fin 3. In each of its four occurrences in the theorem statement (lines 5, 7, 9, and 11), this arithmetic fact is proved automatically by `decide`.
qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 3 2 2 y ≤ qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide)) ∧ ((qary_multiple_deletion_hinge 1 3 2 1 y = qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 3 2 2 y = qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide))) ↔
It suffices to prove the statement universally for all ternary words y of length 2.
The hypothesis `y` is generalized back into the goal using `revert y`, turning the goal into a universal statement ∀ (y : Fin 2 → Fin 3), ... over the finite type of all ternary words of length 2.
revert y
The theorem holds for all ternary words y of length 2. automation
Since the space of ternary words of length 2 has size 3² = 9 and the hinge sum iterates over words of length 3 (size 3³ = 27), the property is a decidable proposition on a finite domain. The `decide` tactic checks all 9 words by exhaustive evaluation, confirming the inequalities and the equivalence.
decide
- Lines 5, 7, 9, and 11 contain embedded proofs `(by decide)` verifying the side condition 1 ≤ 3 needed to construct the all-zero word over the ternary alphabet Fin 3.
- The main proof on line 14 is entirely computational: because there are only 3² = 9 ternary words of length 2 and 3³ = 27 ternary words of length 3, the universal statement is decidable and verified by exhaustive evaluation.
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-1534 holds for ternary alphabet of length 2 with 1 deletion. -/theorem op_1534_ternary_length_two_one_deletion (y : Fin 2 → Fin 3) : qary_multiple_deletion_hinge 1 3 2 1 y ≤ qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 3 2 2 y ≤ qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide)) ∧ ((qary_multiple_deletion_hinge 1 3 2 1 y = qary_multiple_deletion_hinge 1 3 2 1 (qary_all_zero_word 3 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 3 2 2 y = qary_multiple_deletion_hinge 1 3 2 2 (qary_all_zero_word 3 2 (by decide))) ↔ is_constant_word y) := by revert y decide