min_two_insertion_collision_five_lt_alternating
The minimum two-insertion collision sum min_two_insertion_collision 5 is strictly less than two_insertion_collision 3 (alternating_word 5 false).
Statement
theorem min_two_insertion_collision_five_lt_alternating :
min_two_insertion_collision 5 < two_insertion_collision 3 (alternating_word 5 false)- 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 -…
- two_insertion_collisionFor a binary word w of length m + 2, two_insertion_collision m w is the sum over all binary words u of length m of the square of…
- min_two_insertion_collision_fiveThe minimum two-insertion collision sum min_two_insertion_collision 5 equals 20.
- alternating_wordGiven a natural number n and a boolean start, alternating_word n start is the function from Fin n to Bool that maps each index i : Fin n…
Read back from the Lean
The minimum over all boolean words $w : \text{Fin } 5 \to \text{Bool}$ of the 2-insertion collision count for subwords of length 3 is strictly less than the 2-insertion collision count of the alternating word of length 5 starting with false (i.e., the word $(0, 1, 0, 1, 0)$). In other words, the alternating word does not achieve the minimum 2-insertion collision count among length-5 boolean words.
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
This theorem proves that the alternating binary word of length 5 is strictly suboptimal for two-insertion collisions. The proof replaces the minimal collision value for length 5 with its previously computed value of 20, and then uses computational reflection (`decide`) to verify that the collision sum of the alternating word is strictly greater (evaluating to 22).
It suffices to show that 20 is strictly less than the two-insertion collision sum of the alternating word of length 5.
Rewriting with `min_two_insertion_collision_five` substitutes the left-hand side, the minimal two-insertion collision value for words of length 5, with its established value of 20.
uses
min_two_insertion_collision_fiverw [min_two_insertion_collision_five]The inequality 20 < two_insertion_collision 3 (alternating_word 5 false) holds. automation
Both sides of the inequality are concrete, finite combinatorial objects. The `decide` tactic computes the right-hand side by exhaustive evaluation (finding it to be 22) and verifies that 20 < 22.
decide
min_two_insertion_collision_five- The minimum two-insertion collision sum for binary words of length 5 is equal to 20.
- The `decide` tactic evaluates the collision count of the alternating word by finite computational reflection (yielding 22) and checks the inequality directly, without recording intermediate calculation steps in the proof script.
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 alternating word of length 5 is strictly suboptimal for two-insertion collisions. -/theorem min_two_insertion_collision_five_lt_alternating : min_two_insertion_collision 5 < two_insertion_collision 3 (alternating_word 5 false) := by rw [min_two_insertion_collision_five] decide