min_binary_deletion_collision_two_four
The minimum two-deletion collision sum min_binary_deletion_collision 2 4 equals 10.
Statement
theorem min_binary_deletion_collision_two_four : min_binary_deletion_collision 2 4 = 10- 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
min_binary_deletion_collision 2 4 is equal to 10, where for any natural numbers $k$ and $n$, min_binary_deletion_collision k n is defined as the minimum over all binary strings $w : \mathrm{Fin}\ n \to \mathrm{Bool}$ of the sum over all binary strings $u : \mathrm{Fin}\ (n - k) \to \mathrm{Bool}$ of the squared number of strictly monotonic embeddings $f : \mathrm{Fin}\ (n - k) \to \mathrm{Fin}\ n$ such that $w \circ f = u$.
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 asserts that the minimum two-deletion collision sum over all binary words of length 4 is equal to 10. Because the search space consists of only 16 words of length 4 and all deletion embeddings into length-2 subwords are over finite domains, the proof proceeds by direct computation: reflexivity (`rfl`) evaluates the finite sums and the minimum in the Lean kernel.
min_binary_deletion_collision 2 4 = 10
The statement follows by reflexivity (`rfl`). The definitions of `min_binary_deletion_collision`, `binary_deletion_collision`, and `binary_deletion_num_embeddings` operate entirely over finite domains (16 binary words of length 4, 4 binary words of length 2, and strictly increasing maps from Fin 2 to Fin 4). Lean's kernel evaluates the counts and sums definitorially for all 16 candidate words and confirms that the minimum value is 10.
theorem min_binary_deletion_collision_two_four : min_binary_deletion_collision 2 4 = 10 := rfl
- The entire proof is executed by reflexivity (`rfl`), which relies on Lean's kernel to compute and minimize the deletion collision sum over all binary words of length 4 by definitional reduction.
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 two-deletion collision sum for binary words of length 4 is 10. -/theorem min_binary_deletion_collision_two_four : min_binary_deletion_collision 2 4 = 10 := rfl