← All papers
First page of A Lean-Certified Proof of $K_8(4, 2) = 23$

A Lean-Certified Proof of $K_8(4, 2) = 23$

Andreas Florath

cs.IT Jun 15, 2026 · v1
Proves the octonary covering-code value K_8(4,2)=23 in Lean 4 with Lean-checked LRAT refutations.
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.

Determine the exact octonary covering-code value K_8(4,2) and provide a fully machine-checked proof.

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.

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.