min_binary_deletion_collision_three_four
The minimum three-deletion collision sum min_binary_deletion_collision 3 4 equals 8.
Statement
theorem min_binary_deletion_collision_three_four : min_binary_deletion_collision 3 4 = 8- Source
- arXiv:2611.01064: Maximal input entropy for binary two-deletion and two-insertion channels
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- min_binary_deletion_collisionFor natural numbers k and n, min_binary_deletion_collision k n is the minimum over all binary words w of length n of…
Read back from the Lean
The theorem asserts that the minimum binary deletion collision value min_binary_deletion_collision 3 4 is equal to 8; that is, the minimum over all binary words $w : \mathrm{Fin}\ 4 \to \mathrm{Bool}$ of the sum over all binary words $u : \mathrm{Fin}\ (4 - 3) \to \mathrm{Bool}$ of the square of the number of strictly monotonic embeddings $f : \mathrm{Fin}\ 1 \to \mathrm{Fin}\ 4$ such that $w \circ f = u$ is 8.
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 establishes that the minimum 3-deletion collision sum for binary words of length 4 is 8. A 3-deletion of a 4-bit word leaves a 1-bit subword, so the number of embeddings of each bit is simply the number of times it appears in the word; the collision sum is the sum of squares of these counts, which is minimized when the 0s and 1s are balanced ($2^2 + 2^2 = 8$). Lean verifies this equality by pure computation using reflexivity (`rfl`) over the 16 possible binary words.
The minimum 3-deletion collision sum among binary words of length 4 is 8.
The definition searches over the finite domain of all $2^4 = 16$ binary words of length 4, and for each word counts occurrences of bits (words of length $4 - 3 = 1$), squares those counts, and sums them. Because all operations are on finite types, Lean evaluates the expression definitionally via `rfl` to confirm that the minimum is indeed 8.
uses
rfltheorem min_binary_deletion_collision_three_four : min_binary_deletion_collision 3 4 = 8 := rfl
rfl- Reflexivity of equality ($a = a$), which holds definitionally when both sides reduce to the same value.
- The proof relies entirely on definitional equality (`rfl`): Lean's kernel reduces the finite search space and evaluates the expression to 8 by computation.
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
/-- The minimum three-deletion collision sum for binary words of length 4 is 8. -/theorem min_binary_deletion_collision_three_four : min_binary_deletion_collision 3 4 = 8 := rfl