AFTD Auto-Formalizing Theoretical Domains

min_binary_deletion_collision_three_four

theoremverified

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.

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

    line 2

    uses rfl

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

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