op_1534_binary_length_two_one_deletion
For 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 qary_multiple_deletion_hinge 1 2 2 1 y ≤ qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) and qary_multiple_deletion_hinge 1 2 2 2 y ≤ qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 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_binary_length_two_one_deletion (y : Fin 2 → Fin 2) : qary_multiple_deletion_hinge 1 2 2 1 y ≤ qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 2 2 2 y ≤ qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide)) ∧ ((qary_multiple_deletion_hinge 1 2 2 1 y = qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 2 2 2 y = qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 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_binary_length_two_one_deletionFor 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',…
Read back from the Lean
For every binary sequence $y : \text{Fin } 2 \to \text{Fin } 2$ of length 2, the following three conditions hold:
1. qary_multiple_deletion_hinge 1 2 2 1 y ≤ qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)),
2. qary_multiple_deletion_hinge 1 2 2 2 y ≤ qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide)), and
3. Both equalities qary_multiple_deletion_hinge 1 2 2 1 y = qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) and qary_multiple_deletion_hinge 1 2 2 2 y = qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide)) hold if and only if $y$ is a constant word (is_constant_word 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
The theorem is verified by exhaustive finite check: there are only four binary words of length 2, and for each, the one-deletion hinge sums at thresholds 1 and 2 can be directly computed and compared against the all-zero word.
1 ≤ 2 automation
Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.
qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧
1 ≤ 2 automation
Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.
qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide)) ∧
1 ≤ 2 automation
Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.
qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧
1 ≤ 2 automation
Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.
qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide))) ↔
Revert y into the goal
Revert y.
revert y
Decide the whole statement automation
Decide.
decide
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 binary alphabet of length 2 with 1 deletion. -/theorem op_1534_binary_length_two_one_deletion (y : Fin 2 → Fin 2) : qary_multiple_deletion_hinge 1 2 2 1 y ≤ qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 2 2 2 y ≤ qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide)) ∧ ((qary_multiple_deletion_hinge 1 2 2 1 y = qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧ qary_multiple_deletion_hinge 1 2 2 2 y = qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide))) ↔ is_constant_word y) := by revert y decide