AFTD Auto-Formalizing Theoretical Domains

min_q_ary_deletion_collision_three_three_five

theoremverified

The minimum, over ternary words of length 5, of the 3-deletion collision sum is 14, so C_3(5) - binom(5,3) = 4.

Statement

theorem min_q_ary_deletion_collision_three_three_five : min_q_ary_deletion_collision 3 3 5 = 14
Source
Small case of OP-1359 (q = 3, n = 5); value from experiment 21007, attained by 01210.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • min_q_ary_deletion_collisionFor natural numbers q, k, and n, min_q_ary_deletion_collision q k n is the minimum over all q-ary words w of length n of the sum over all…

The proof, explained

The theorem asserts that the minimum 3-deletion collision sum over all ternary words of length 5 is 14. Because the search space consists of only $3^5 = 243$ words and subword embedding counts are finite, the statement is purely computational. The proof evaluates the finite combinatorial search exhaustively via Lean's kernel reduction.

  1. The minimum collision sum of 3-deletions among all ternary words of length 5 is 14. automation

    The equality is a decidable proposition over finite types: there are $3^5 = 243$ ternary words of length 5, and for each word the sum involves $3^{5 - 3} = 9$ subwords of length 2 and $\binom{5}{2} = 10$ index selections. The tactic `decide +kernel` evaluates this entire finite search by computational reduction directly inside Lean's kernel to verify that the minimum value is 14.

    line 1

    theorem min_q_ary_deletion_collision_three_three_five : min_q_ary_deletion_collision 3 3 5 = 14 := by decide +kernel

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

theorem min_q_ary_deletion_collision_three_three_five : min_q_ary_deletion_collision 3 3 5 = 14 := by decide +kernel
See it in the graphDiscuss this resultChallenge it