AFTD Auto-Formalizing Theoretical Domains

op_1534_ternary_length_two_one_deletion

theoremverifiedoriginal

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

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`.

  1. 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`.

    lines 5–11

          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))) ↔
  2. 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.

    line 13

      revert y
  3. 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.

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