AFTD Auto-Formalizing Theoretical Domains

min_two_insertion_collision_four

theoremverifiedformalization

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

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

    line 3

      rfl

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