min_two_insertion_collision_four
The minimum two-insertion collision sum min_two_insertion_collision 4 equals 10.
Statement
theorem min_two_insertion_collision_four : min_two_insertion_collision 4 = 10- Formalizes
- arXiv:2611.01064, Section 4.2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 -…
Read back from the Lean
min_two_insertion_collision 4 is equal to 10. That is, the minimum, over all binary sequences $w$ of length 4 (functions $w : \text{Fin } 4 \to \text{Bool}$), of the sum over all binary sequences $u$ of length 2 of the square of the number of strictly monotonic functions $f : \text{Fin } 2 \to \text{Fin } 4$ satisfying $w \circ f = u$, equals 10.
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 the minimum two-insertion collision sum for binary words of length 4 is 10. Because all types involved are finite—the search space consists of the 16 binary words of length 4, and the embedding counts run over the 4 words of length 2—the definition reduces entirely by computation in Lean, established immediately by reflexivity (`rfl`).
The minimum two-insertion collision sum for words of length 4 is 10.
The statement is verified by definitional reduction (`rfl`). The definition `min_two_insertion_collision 4` is a finite computation over the 16 binary words of length 4 and the 4 binary words of length 2, calculating the number of strictly monotonic subsequence embeddings and finding the minimum sum of squares. Lean evaluates this expression directly to 10.
rfl
- The result is proved purely by definitional equality (computation in Lean's kernel); no intermediate lemmas or mathematical derivations are recorded in the proof.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The minimum two-insertion collision sum for words of length 4 is 10. -/theorem min_two_insertion_collision_four : min_two_insertion_collision 4 = 10 := by rfl