min_two_insertion_collision_five
The minimum two-insertion collision sum min_two_insertion_collision 5 equals 20.
Statement
theorem min_two_insertion_collision_five : min_two_insertion_collision 5 = 20- Related work
- arXiv:2611.01064, Section 4.2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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 -…
- op_1003_two_insertion_collision_defect_envelope_fiveThe minimum two-insertion collision sum min_two_insertion_collision at length 5 equals two_insertion_collision_defect_envelope 5.
- two_insertion_collision_defect_envelope_fiveThe two-insertion collision defect envelope two_insertion_collision_defect_envelope at n = 5 equals 20.
- two_insertion_collision_defect_envelopeFor a natural number n, two_insertion_collision_defect_envelope n is n.choose 2 plus the minimum over all k in the defect set K_n of the…
- Used by 1
- min_two_insertion_collision_five_lt_alternatingThe minimum two-insertion collision sum min_two_insertion_collision 5 is strictly less than two_insertion_collision 3 (alternating_word 5…
Read back from the Lean
The value of min_two_insertion_collision 5 is equal to 20. That is, taking the minimum over all binary words $w : \mathrm{Fin}\,(5 - 2 + 2) \to \mathrm{Bool}$ of the sum over all binary words $u : \mathrm{Fin}\,3 \to \mathrm{Bool}$ of the square of the number of strictly monotone functions $f : \mathrm{Fin}\,3 \to \mathrm{Fin}\,(3 + 2)$ satisfying $w(f(i)) = u(i)$ for all $i$, yields 20.
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 proves that the minimum two-insertion collision sum for binary words of length 5 equals 20. The proof chains two equalities by transitivity: first, that this minimum collision sum equals the two-insertion collision defect envelope at 5, and second, that this defect envelope evaluates to 20.
min_two_insertion_collision 5 = 20
The minimum two-insertion collision sum for words of length 5 is shown to equal 20 by composing the equality min_two_insertion_collision 5 = two_insertion_collision_defect_envelope 5 via transitivity (op_1003_two_insertion_collision_defect_envelope_five.trans) with the evaluation two_insertion_collision_defect_envelope 5 = 20 (two_insertion_collision_defect_envelope_five).
uses
op_1003_two_insertion_collision_defect_envelope_five.trans,two_insertion_collision_defect_envelope_fivetheorem min_two_insertion_collision_five : min_two_insertion_collision 5 = 20 := op_1003_two_insertion_collision_defect_envelope_five.trans two_insertion_collision_defect_envelope_five
op_1003_two_insertion_collision_defect_envelope_five.trans- Specialization of transitivity of equality: if the defect envelope at 5 equals c, then the minimum two-insertion collision sum at 5 equals c.
two_insertion_collision_defect_envelope_five- The two-insertion collision defect envelope at length 5 equals 20.
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-insertion collision sum for words of length 5 is 20. -/theorem min_two_insertion_collision_five : min_two_insertion_collision 5 = 20 := op_1003_two_insertion_collision_defect_envelope_five.trans two_insertion_collision_defect_envelope_five