op_1003_two_insertion_collision_defect_envelope_five
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
- min_two_insertion_collisionFor a natural number n, min_two_insertion_collision n is the minimum over all binary words w of length n of two_insertion_collision (n -…
- two_insertion_collision_defect_envelopeFor a natural number n, two_insertion_collision_defect_envelope n is n.choose 2 plus the minimum over all k in the defect set K_n of the…
- two_insertion_collision_defect_envelope_fiveThe two-insertion collision defect envelope two_insertion_collision_defect_envelope at n = 5 equals 20.
- Used by 1
- min_two_insertion_collision_fiveThe minimum two-insertion collision sum min_two_insertion_collision 5 equals 20.
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).
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`).
min_two_insertion_collision 5 = two_insertion_collision_defect_envelope 5 := rfl
- The proof is purely computational: Lean's kernel computes both finite expressions directly to the natural number 20 and verifies that they are definitionally equal.
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