AFTD Auto-Formalizing Theoretical Domains

min_two_insertion_collision_five

theoremverifiedoriginal

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
Used by 1

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.

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

    line 2

    uses op_1003_two_insertion_collision_defect_envelope_five.trans, two_insertion_collision_defect_envelope_five

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