AFTD Auto-Formalizing Theoretical Domains

min_two_insertion_collision_five_lt_alternating

theoremverifiedoriginal

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

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

    line 4

    uses min_two_insertion_collision_five

      rw [min_two_insertion_collision_five]
  2. 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.

    line 5

      decide
min_two_insertion_collision_five
The minimum two-insertion collision sum for binary words of length 5 is equal to 20.

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

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