AFTD Auto-Formalizing Theoretical Domains

op_1534_binary_length_two_one_deletion

theoremverifiedoriginal

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

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. 1 ≤ 2 automation

    Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.

    line 5

          qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧
  2. 1 ≤ 2 automation

    Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.

    line 7

          qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide)) ∧
  3. 1 ≤ 2 automation

    Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.

    line 9

            qary_multiple_deletion_hinge 1 2 2 1 (qary_all_zero_word 2 2 (by decide)) ∧
  4. 1 ≤ 2 automation

    Simple arithmetic 1 ≤ 2 required by the definition of the all-zero word.

    line 11

            qary_multiple_deletion_hinge 1 2 2 2 (qary_all_zero_word 2 2 (by decide))) ↔
  5. Revert y into the goal

    Revert y.

    line 13

      revert y
  6. Decide the whole statement automation

    Decide.

    line 14

      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

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