AFTD Auto-Formalizing Theoretical Domains

op_1003_two_insertion_collision_defect_envelope_five

theoremverified

The minimum two-insertion collision sum min_two_insertion_collision at length 5 equals two_insertion_collision_defect_envelope 5.

Statement

theorem op_1003_two_insertion_collision_defect_envelope_five :
    min_two_insertion_collision 5 = two_insertion_collision_defect_envelope 5
Source
arXiv:2611.01064 Maximal input entropy for binary two-deletion and two-insertion channels
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

The theorem asserts that min_two_insertion_collision 5 is equal to two_insertion_collision_defect_envelope 5. Specifically: - min_two_insertion_collision 5 is the minimum over all length-5 boolean sequences $w : \mathrm{Fin}\; 5 \to \mathrm{Bool}$ of the sum over all length-3 boolean sequences $u : \mathrm{Fin}\; 3 \to \mathrm{Bool}$ of the square of the number of strictly monotonic embeddings $f : \mathrm{Fin}\; 3 \to \mathrm{Fin}\; 5$ satisfying $w(f(i)) = u(i)$ for all $i$. - two_insertion_collision_defect_envelope 5 is $\binom{5}{2}$ plus the minimum over $k \in \{1\} \cup \{k \in \mathbb{N} \mid 2 \le k \le (5-2)/3 - 1\}$ (which evaluates to $\{1\}$) of $2k \cdot 5 + 2k^2 + 5 - 10k - 2 + (k + 1 - r) q^2 + r(q + 1)^2$, where $q = (5 - 2) / (k + 1)$ and $r = (5 - 2) \bmod (k + 1)$ (using truncated natural-number arithmetic).

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 for binary words of length 5, the minimum two-insertion collision sum equals the value given by the balanced defect envelope formula. Because both expressions are finite and fully concrete, Lean establishes the identity by directly evaluating both sides to the natural number 20 via definitional equality (reflexivity).

  1. min_two_insertion_collision 5 = two_insertion_collision_defect_envelope 5 (both evaluate to 20)

    Both sides of the equation are closed, computable expressions. The left-hand side computes the minimum two-insertion collision sum over all 2⁵ = 32 binary words of length 5, which equals 20. The right-hand side computes the defect envelope formula at n = 5 (where the candidate index set K contains only k = 1), which also evaluates to 10 + 10 = 20. Since both sides reduce to the same normal form 20, the equality holds by definitional equality (reflexivity, `rfl`).

    line 3

        min_two_insertion_collision 5 = two_insertion_collision_defect_envelope 5 := rfl

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- At received length five, the minimum two-insertion collision sum equals the balanced defect envelope value 20. -/theorem op_1003_two_insertion_collision_defect_envelope_five :    min_two_insertion_collision 5 = two_insertion_collision_defect_envelope 5 := rfl
See it in the graphDiscuss this resultChallenge it