An arXiv preprint, version 3 dated 2 September 2026, reports 84 bound-improvement cases across 83 distinct parameter cells in q-ary covering-code problems. It asks whether computational construction and certification can improve known upper and lower bounds for Kq(n,R). In plain terms, an upper bound comes from showing a code of a given size, while a certified lower bound marks a size that the quantity cannot fall below.
Where the bounds moved
The upper-bound arm contains 26 explicit-code bounds for q from 5 to 15. At K7(9,5), the reported upper bound falls from 323 to 240. At K8(10,5), it falls from 2,461 to 1,883. These constructions establish the new upper bounds, but not that no smaller code exists.
The lower-bound arm contains 58 semidefinite-programming bounds for q from 6 to 21. Its dual solutions were rounded to exact rational certificates and checked in exact arithmetic. For K6(10,4), the reported range narrowed from 417 to 2,952 to a range of 441 to 2,751, an improvement on both ends that still leaves a range rather than an exact answer.
The paper also improves every reported cell in the (n,R)=(8,2) family for q from 6 through 21. The increments ranged from 91 codewords at q=6 to 14,436 at q=21. The largest single increase was K10(10,2), whose lower bound rose from 2,676,660 to at least 2,699,348.
Search results also show why the upper figures need careful reading. For 24 of the 26 upper-bound searches, the final-budget run found no code one size below the reported result. Two searches were still producing smaller codes when the version was prepared. A failed search is not proof that no smaller code exists.
How the numbers were checked
On the lower-bound side, all 58 certificates used 200- or 250-bit working precision. The scaling factor was exactly 1 for 52 of them, and scaling did not change the integer bounds.
The standalone checker rebuilt the program from q, n and R, verified that the dual multipliers were nonnegative and the dual matrices positive semidefinite, then checked all dual inequalities in integer arithmetic. It used no floating-point computation for those tests.
Each of the 26 codes received four verification checks, followed by a separate fifth dilation check that reverified all 26 published codes. All 196 certificate files were rechecked. Of those, 58 improved the tabulated bound, 28 matched it exactly, 82 fell between the sphere-covering and tabulated bounds, and 28 fell below the sphere-covering bound. Only the 58 improving certificates were included in the reported tables and ancillary files.
What the paper leaves unresolved
Several questions remain open. For K8(4,2), local search, SAT solving and integer programming found neither a code of size 22 nor a proof that size 22 is impossible, leaving the value at either 22 or 23. Related searches found no code of size 11,775 for K9(10,4), and none below the direct-sum comparison of 27 times 729.
The results therefore mark progress in selected cells, not a final solution to the table. The explicit codes establish upper bounds rather than optimal values, failed searches do not prove nonexistence, and the improved lower bounds can still leave a gap above them.
The paper supplies ancillary files with 26 codes, 58 certificates, checkers and a README. It also identifies a repository for the search, certification and verification source code and for a machine-readable merged bounds table.
The preprint discloses that the AI system Claude drafted and edited the manuscript and wrote the search, certification and verification software. It says the statements and proofs were checked and that the author takes full responsibility for the content.
Paper data and sources
Original title: New upper bounds on covering codes K_q(n,R) for alphabets of size six and seven
Authors: Mark Marosi
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text