Linear covering codes of radius two

• Slug: covering
• Solver: Codex gpt-5.6-sol Max (2026-08-16 overnight). Grok watched only.
• Status: $\ell_2(10,2)\le 50$, $\ell_2(41,3)\le26175$, $\ell_2(44,3)\le52351$, and $\ell_2(47,3)\le104703$ certified; $n=49$ still open (q9–q11 and q14 residue); $f(2)$ open
• Area: Coding theory
• Sources: Green 100 #40; Cohen et al., Covering Codes; Davydov–Marcugini–Pambianco, arXiv:2511.02542 (Tables 5.1, 7.2); Kaikkonen–Rosendahl
• Started: 2026-08-16
• Tonight: finite-cex — beat a documented small $\ell_2(r,2)$ length, emit H and an exhaustive radius-2 certificate

In general

For a binary linear code $C\le\mathbb F_2^n$ of codimension $r$, the covering radius is the least $R$ such that every vector of $\mathbb F_2^n$ lies at distance at most $R$ from $C$. Equivalently, if $H$ is an $r\times n$ parity-check matrix, every syndrome in $\mathbb F_2^r$ is a sum of at most $R$ columns of $H$. Write $\ell_2(r,R)$ for the least length of a binary linear code with redundancy $r$ and covering radius $R$.

Green's Problem 40 asks for the asymptotic density

The known range is $1\le f(2)\le 1.4238$; it is not even known whether $f(2)=1$. Tonight is not $f(2)$. Tonight is a documented finite length.

Stale as written. The $1.4238$ had already been superseded by arXiv:2511.02542 ($\approx 1.32031$) before this line was typed, and the $n=50$ seed brings it to $2601/2048\approx 1.27002$. See result/NOTE.md §6.

The November 2025 table of Davydov–Marcugini–Pambianco (arXiv:2511.02542v1, Table 5.1) lists $\ell_2(10,2)\le 51$ (Kaikkonen–Rosendahl), density $1327/1024\approx 1.29590$. Secondary holes in the same table: $\ell_2(8,2)\le 26$ and $\ell_2(9,2)\le 39$.

Precise statement

A binary $r\times n$ matrix $H$ has covering radius at most 2 if its columns $S\subset\mathbb F_2^r$ satisfy

Tonight's finite subquestion. Find an explicit $H$ whose length improves a documented table entry, preferably $\ell_2(10,2)\le 50$, and emit an independently re-runnable exhaustive certificate that every one of the $2^r$ syndromes is a sum of at most two columns. Do not claim $f(2)$.

Certified finite bound (quest q1, recovered)

Quest q1 found a binary $[50,40]$ code of covering radius exactly 2. The explicit parity-check matrix is compute/H_r10_n50.txt; the integer-column witness is compute/witness_r10_n50.json. Independent exhaustive pair-XOR cover: $1024/1024$ syndromes. Finite density $319/256=1.24609375$. This proves

and does not determine $f(2)$. An $n=49$ anneal left 7 uncovered syndromes — an incomplete search, not a lower bound.

Local 49-column switches (quest q14, 2026-09-23)

Exact enumeration around the published 50-set rules out every two-delete/one-add candidate (all 1,194,375 leave at least nine uncovered syndromes) and every three-delete/two-add completion (all 19,600 deletion triples fail). The exact restricted predicate and replay are in compute/q14/CLAIM.md. This is residue, not a lower bound; $\ell_2(10,2)\le49$ remains open.

Certified finite bounds (quest q5, 2026-08-19)

From the same 50-set, constructions $\mathrm{QM}_3^2$ and $\mathrm{QM}_5^2$ of arXiv:2511.02542 were implemented and independently replayed (official C verifier plus a second bitset checker; full $2^r$ sweeps):

• $\ell_2(22,2)\le 3325$ (paper 3389) — compute/H_r22_n3325.txt
• $\ell_2(24,2)\le 6653$ (paper 6781) — compute/H_r24_n6653.txt
• $\ell_2(26,2)\le 13309$ (paper 13565) — compute/H_r26_n13309.txt
• $\ell_2(28,2)\le 26111$ (paper 26623) — compute/H_r28_n26111.txt, $p(H)\le 64$

Theorem-only from the $r=28$ seed: $\ell_2(40,2)\le 1671167$, $\ell_2(42,2)\le 3342335$, $\ell_2(44,2)\le 6684671$ (not enumerated). $n=49$ is still a 7-hole incomplete search, not a lower bound.

Certified finite bounds (quest q6b, 2026-08-19)

• Exact 3-sum: every vector of $\mathbb F_2^{10}$ is a sum of exactly three distinct columns of the 50-set (1024/1024).
• $\ell_2(18,3)\le 151$ (table 153) — compute/H_R3_r18_n151.txt. QM$_4^3$ from a 9-block $(3,0)$-partition of $H_{OK}$. Full $2^{18}$ radius-3 sweep.
• $\ell_2(26,3)\le 817$ (paper 818) — compute/H_R3_r26_n817.txt. Full $2^{26}$ radius-3 sweep.
• $p(H)\le 64$ on the $r=28$ matrix — compute/partition_r28_n26111_p64.txt. Unlocks theorem-only $\ell_2(40,2)\le 1671167$.

Certified finite bound (quest q6c, 2026-08-19)

• $\ell_2(31,4)\le 689$ (paper 690) — compute/H_R4_r31_n689.txt. QM$_4^4$ from OK2 plus the 50-set. Blockwise certificate for all $2^{31}$ syndromes; radius exactly 4. Independent C replay in /tmp, not a flat sweep.

Certified finite bounds (quest q7c, 2026-08-19)

• $p(H_{18})\le 17$ on the certified $r=18$, $n=815$ matrix — compute/partition_r18_n815_p17.txt. Full $2^{18}$ cross-block sweep.
• $p(H_{20})\le 14$ on the certified $r=20$, $n=1631$ matrix — compute/partition_r20_n1631_p14.txt. Full $2^{20}$ cross-block sweep.
• Theorem-only $\ell_2(38,3)\le 13102$ (paper 13118) and $\ell_2(41,3)\le 26206$ (paper 26238) via QM$_5^3$ / Theorem 7.3. Not enumerated.

Certified finite bounds (quest q8, 2026-08-20)

Leftover unused constructions from compute/notes_from_authors_2026-08-19.md:

• $M_{OK}$ last word is independently 1CE (paper OCR ICE). Unique among 512 last words making $P_{OK}$ a $(3,1)$-partition.
• $\ell_2(21,3)\le 303$ (older table 308; matches the paper) — compute/H_R3_r21_n303.txt. Full $2^{21}$ radius-3 sweep: $2097152/2097152$.
• $\ell_2(26,2)\le 13070$ (paper 13565; previous certified 13309) — compute/H_r26_n13070.txt. QM$_2^1$ from $p(H_{18})\le 17$. Full $2^{26}$ sweep: $67108864/67108864$.
• $p(H_{26})\le 19$ — compute/partition_r26_n13070_p19.txt. Unlocks theorem-only $\ell_2(36,2)\le 418271$ (paper 425983). Not enumerated.

Certified finite bound (quest q8c, 2026-08-19)

• $p(H_{28})\le 28$ on the certified $r=28$, $n=26111$ matrix — compute/partition_r28_n26111_p28.txt. Full $2^{28}$ cross-block sweep. Improves the previous $p\le 64$. No new $r=38$ table length.

Certified residue (quest q9, 2026-08-21)

No new dent. The 2003 Kaikkonen-Rosendahl 51-set is recovered from the hex listing of arXiv:2511.02542 (4.9) and re-verified 1024/1024 — compute/q9/H_r10_n51_KR.txt. Over all 174251 two-dimensional quotients of $\mathbb F_2^{10}$, neither the 51-set nor the certified 50-set has a kernel block covering its own kernel, so neither is a lift of the $r=8$ record the way the 1992 value 53 was. An exact quotient-block replacement solver rules out, exhaustively, 271127 of the 279034 single-block shrinks of the 50-set with block width $\le 12$, and finds no 49 in four full sweeps. Search residue, not a lower bound; $\ell_2(10,2)\le 49$ remains open.

Certified residue (quest q10, 2026-08-21)

No new dent. Records unchanged: $\ell_2(10,2)\le 50$, $\ell_2(11,2)\le 79$. Prescribed automorphisms: if a 49-set exists, its automorphism group in $GL(10,2)$ is a $\{2,3,5\}$-group. Order 7 is settled at $r=10$ for every fixed-space dimension (both module types); orders 11, 17, 31, 73, 127 are killed by the same arithmetic plus the touched-layer bound. At $r=11$ no invariant set below the record 79 exists for orders 11, 17 or 23. The certified 50-set and the Kaikkonen–Rosendahl 51-set both have 2-group automorphism groups ($|\mathrm{Aut}|=128$ and $512$), which is the case the odd-order sweep does not reach. Material in compute/q10/. None of this is a lower bound.

Certified residue (quest q11, 2026-08-21)

No new dent. A construction family anchored to a fibration rather than to a set: split $\mathbb F_2^r=V\oplus W$ and take one column over every nonzero point of the base plus a kernel block, $S=A\times\{0\}\cup\{(g(u),u)\}$, $n=|A|+2^{\dim W}-1$. Radius 2 becomes a line-colouring condition on $\mathrm{PG}(\dim W-1,2)$, which yields two exact obstructions (no quadratic $g$ when $\dim W$ is odd; a line-cover count that forbids every $n\le47$ at $r=10$). The family contains the documented lengths at $r=4,7,8,9$ — explicit matrices in compute/q11/, each replayed by an independent full $2^r$ sweep — and at $r\le8$ it is exactly decided: $n=23,24,25$ are exhausted at $r=8$, so the family reproduces $\ell_2(8,2)\le26$ and provably cannot beat it. At $r=10$ its own best is 54; the record 50 is not in the family. $n=38$ at $r=9$ is search residue. $\ell_2(10,2)\le49$ remains open.

Certified finite bound (2026-09-11)

The existing $26$ by $817$ radius-3 matrix has an inherited 34-block $(3,0)$-partition: 23 Golay $A$-blocks, 10 blocks from its embedded $10$ by $50$ radius-2 matrix, and one $W_5$ block. An exhaustive compact-bitset check covers all $2^{26}$ seed syndromes, both before and after refining to 65 blocks. Construction QM$_4^3$ with $m=6$ then gives a $44$ by $52351$ matrix, proving

Davydov–Marcugini–Pambianco, arXiv:2511.02542v1, Table 7.2 gives 52415, so the improvement is 64 columns. The explicit matrix, partitions, manifest, Python constructor, and independent C verifier are in compute/q13/. The verifier checks every construction column; it does not sweep $2^{44}$ syndromes and makes no optimality claim.

Certified finite bound (2026-09-23)

The inherited 34-block $(3,0)$-partition of the $26\times817$ radius-3 seed admits two valid single merges among all 561 block pairs. Merging blocks 7 and 31 gives 33 blocks, which permits QM$_4^3$ with $m=5$. An independent C verifier sweeps all $2^{26}$ seed syndromes under the merged partition and checks every column of the resulting $41\times26175$ matrix. Therefore

This improves the published Table 7.2 length 26238 by 63 and the notebook's earlier 26206 by 31. The theorem carries the seed certificate to redundancy 41; no $2^{41}$ sweep is claimed. An exact representation count also shows that all 817 seed columns are essential for radius 3, even without partition restrictions, so deleting one column from this seed cannot improve it. Replay: compute/q16/run_all.sh; exact statement: compute/q16/CLAIM.md.

Certified finite bound at redundancy 47 (2026-09-23, q15)

A 129-block refinement of the same 817-column seed permits QM$_4^3$ with $m=7$. An independent C verifier checks the seed partition and every column of the resulting $47\times104703$ matrix. Therefore

This improves the published Table 7.2 length 104831 by 128. Replay: compute/q15/run_all.sh; exact statement: compute/q15/CLAIM.md.

What a solution looks like

• An explicit matrix under compute/ and a verifier that checks F$_2$-rank $r$ and that every syndrome is a sum of at most 2 columns.
• A documented comparison to the previous table entry.
• Do not claim $f(2)$. Do not claim optimality of the finite length without a matching lower bound.

Related

• Ben Green, 100 Open Problems, Problem 40
• Davydov–Marcugini–Pambianco, New upper bounds for binary linear covering codes, arXiv:2511.02542
• Cohen, Honkala, Litsyn, Lobstein, Covering Codes

Quests so far

Figures

Regenerated from compute/search_results.json: figures/q1_density_vs_length.png.

Interactive explainer (Claude Opus and Fable 5): explainer.html. PDF explainer (problem, process, result, verification): explainer.pdf.