AFTD Auto-Formalizing Theoretical Domains

min_binary_deletion_collision_two_four

theoremverified

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.

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

    line 2

    theorem min_binary_deletion_collision_two_four : min_binary_deletion_collision 2 4 = 10 := 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

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