← All papers
A Lean-Certified Proof of $K_8(4, 2) = 23$
cs.IT
Jun 15, 2026 · v1
TL;DR
Proves the octonary covering-code value K_8(4,2)=23 in Lean 4 with Lean-checked LRAT refutations.
Abstract
We prove the exact octonary covering-code value $K_8(4, 2) = 23$ in Lean 4. The upper bound is given by an explicit 23-word radius-two code in $(Fin\:8)^4$ , checked over all $8^4$ ambient words. The lower bound excludes covers with at most 22 words. A fiber-counting and missing-pair argument first rules out covers with at most 21 words. In the remaining 22-word case, the proof reduces a hypothetical cover to six missing-pair graphs coming from the coordinate-pair projections. Fiber-counting arguments constrain these graphs, and two Lean-checked Linear RAT (LRAT) refutations of stored conjunctive-normal-form (CNF) instances force a common 3 + 3 + 2 block structure. This structure is incompatible with a 22-word cover: the two three-symbol components already force 18 codewords, while the remaining two-symbol component would require a binary strength-two array of length four with at most four rows, which is impossible. The result is packaged as a proof-carrying Lean artifact: the explicit upper bound, structural lower bound, CNF instances, and LRAT refutations are checked inside Lean, with no external SAT solver used during proof replay.
Problem
Determine the exact octonary covering-code value K_8(4,2) and provide a fully machine-checked proof.
Approach
In Lean 4, the upper bound is an explicit 23-word radius-two code in (Fin 8)^4 checked over all 8^4 words. The lower bound excludes covers with at most 22 words via fiber-counting and missing-pair graph arguments, with two Lean-checked LRAT refutations of stored CNF instances. No external SAT solver is used during proof replay.
Results
Establishes K_8(4,2)=23, packaged as a proof-carrying Lean artifact bundling the upper bound, structural lower bound, CNF instances, and LRAT refutations.
