How One Missing Column Became a Covering Code

0. What was missing

The asymptotic question in Green's Problem 40 is deliberately out of reach here. The useful finite question was narrower: could one write down a parity-check matrix that improves a documented small parameter, then make the covering claim independently checkable?

For a binary parity-check matrix, the entire problem lives in syndrome space. If its columns form a set $S\subset\mathbb F_2^r$, radius at most 2 means that every syndrome is either zero, a column, or the sum of two columns. The desired matrix was therefore a small additive basis of order two, with no zero or repeated columns.

That reformulation made the proof tiny. It did not make the search easy.

1. The attractive gaps that did not close

The first target was $(r,n)=(8,25)$. The documented length was 26, and deleting a single column would settle a conspicuous one-column gap. Random annealing repeatedly came close, but its best 25-set missed three of the 256 syndromes. CP-SAT and Z3 encodings also ran to their limits without a model or a refutation.

The second target was $(9,38)$, one column below the documented length 39. Here the monolithic SAT instance had roughly 130,000 pair auxiliaries. A five-minute CP-SAT run returned UNKNOWN. Reconstructing the classical Gabidulin 39-column set helped, but every direct deletion missed eight syndromes, and an exhaustive two-out/one-in neighborhood contained no solution.

These failures had names and numbers: three missed at $(8,25)$, eight missed at $(9,38)$, and UNKNOWN from every bounded exact run. None was a lower bound.

2. What the failures taught us

The near-solutions exposed a mismatch between the prettiest parameter gaps and the easiest search landscapes. At $r=8,n=25$, there are only

zero-, one-, and two-column representations for 256 syndromes. Almost every collision matters. The 26-column algebraic seed was also highly regular: deleting any column destroyed many uniquely covered syndromes.

The search needed more slack and a less rigid seed. The current table supplied both at redundancy 10. Its 51-column Kaikkonen--Rosendahl matrix has 1,327 representations for 1,024 syndromes and an explicit hexadecimal description. Deleting its least costly column left only 11 syndromes uncovered—worse as an absolute number than the $r=8$ leftover, but with much more room to rearrange pair sums.

3. The click

The click was to stop asking which published bound was numerically closest and ask which seed had enough redundant representations to move.

The local-search state was a set of exactly 50 nonzero ten-bit columns. An array stored, for every syndrome, how many times it appeared as zero, a singleton, or a pair sum. Swapping one column changes only its singleton and the 49 pair sums involving it, so the uncovered count can be updated without recomputing all $\binom{50}{2}$ pairs.

Most proposals were targeted. Pick an uncovered syndrome $g$, then propose either $g$ itself or $g+s$ for a current column $s$; either choice has an immediate way to cover $g$, unless the compensating deletion breaks it again. Simulated annealing admitted the occasional uphill move needed to leave local minima.

With a fixed xorshift seed, run 0 reached zero uncovered syndromes at proposal 3,600,281. The result had 50 distinct nonzero columns.

4. Why the short certificate proves the coding statement

Let $H$ be the resulting $10\times50$ matrix and let $C=\ker H$. The independent checker first finds $\operatorname{rank}H=10$, so $C$ has dimension $50-10=40$.

Now take any word $x\in\mathbb F_2^{50}$ and compute its syndrome $s=Hx^T$. The certificate gives indices of at most two columns of $H$ whose sum is $s$. Put ones in those coordinate positions to obtain an error vector $e$ of weight at most two. Then

so $x-e\in C$ and $d(x,C)\le2$.

The radius is exactly 2, not merely at most 2: zero and the 50 singleton columns account for only 51 of the 1,024 syndromes. Some syndrome necessarily needs two columns.

5. What the computer checked

The committed certificate has one entry for every integer syndrome from 0 through 1,023. It uses the empty representation once, a singleton 50 times, and a pair 973 times. The verifier checks every supplied XOR, reconstructs the matrix from its text rows, computes its binary rank, and then ignores the certificate and performs a second exhaustive enumeration of all 1,276 representations.

That independent enumeration covers all 1,024 syndromes. Its multiplicity histogram is

where the key is the number of representations and the value is the number of syndromes with that multiplicity. In particular, there are no zeroes in the histogram.

The finite covering density is therefore

The November 2025 best-known table lists length 51 and density $1327/1024\approx1.29590$ at redundancy 10. The exhaustive witness moves that documented entry down by one column.

6. Proven, and still open

What is proved is concrete:

The matrix, all 1,024 certificate entries, the certificate generator, the independent verifier, and the deterministic search trace live under compute/. The witness reruns without Lean and without trusting the heuristic.

What is not proved matters just as much. The search did not show that 50 is optimal; its $n=49$ run stopped with seven uncovered syndromes. It did not resolve the 25-versus-26 gap at redundancy 8 or the 38-versus-39 gap at redundancy 9. Most importantly, one finite upper-bound improvement does not determine, or even claim to determine, Green's asymptotic constant $f(2)$.

The durable idea is the separation between discovery and proof. The heuristic only had to find the columns once. After that, a short syndrome argument and an exhaustive, independent certificate carried the mathematical claim.

7. The 49 push (quest q4): certified incomplete search, no improvement

A later session attacked $\ell_2(10,2)\le 49$ directly and did not land it. What it left behind is negative knowledge with certificates, under compute/q4/:

• Symmetry is dead at 49 = 7×7. If a 49-covering were invariant under a subgroup of $GL(10,2)$, it would be a union of orbits, and coverage collapses to orbit-class space where exhaustive search is feasible. Seventy-nine subgroup classes were exhausted with zero witnesses, including every $C_7\times C_7$ class (orbit sizes 1/7/49) and the order-7 classes with one-dimensional fixed space (up to 8.9 billion nodes each). The engine's negatives were validated three ways: planted direct-sum coverings recovered at n=62/78, a no-prune rerun, and an independent naive enumerator agreeing on 7.26 million leaves. A few fixed-space-heavy classes timed out and remain open.
• The 7-hole floor is real and deep. Fresh deterministic anneals reproduce exactly 7 uncovered syndromes. One such configuration is provably not within any swap of 5 columns of a covering (exhaustive over all 1.9M removal sets with an exact re-add search, validated on 4/4 planted controls); a second is proven to depth 4.
• There are at least two basins. The two 7-hole optima have identical GL-invariants — same multiplicity histogram, same hole-set structure (rank 5, one zero-sum quadruple) — yet an exhaustive color-guided search proves no linear map carries one onto the other.

None of this is a lower bound. $\ell_2(10,2)=49$ remains possible; what is excluded is every highly symmetric 49-covering in the classes listed, and every small perturbation of the best-known near-misses.

8. Zooming out: what the trajectory says about 49 (quest q9)

Before pushing on 49 again it is worth asking what the previous four answers at $r=10$ actually were.

53 is a lift. The even-$r$ family $\phi(2t)=27\cdot 2^{t-4}-1$ doubles $n+1$ every two units of redundancy. Its $r=10$ entry is nothing but the $r=8$ entry carried up one step: $2(26+1)-1=53$. If the pattern of the table were "improve the seed and re-lift", then $\ell_2(10,2)\le 49$ would want an $r=8$ length of $25$ — which is exactly the gap the q1 session failed to close, missing three of 256 syndromes.

51 and 50 are not lifts. This is checkable, and it was checked. Every subset of $\mathbb F_2^{10}$ decomposes, along each of the 174251 two-dimensional quotients $q:\mathbb F_2^{10}\to\mathbb F_2^2$, into four blocks $(A;B,C,D)$ with $A=S\cap\ker q$. A lift would be a quotient whose kernel block already covers $\ker q\cong\mathbb F_2^8$, with the other three blocks patching the cosets. Sweeping all 174251 quotients of the Kaikkonen–Rosendahl 51-set and of the certified 50-set: not one kernel block covers its own kernel. The 2003 decrease of 2 and the 2026 decrease of 1 both left the lift family behind and never came back.

What they are instead is flat. Across all 174251 quotients the kernel block size stays inside $3..27$ for the 51-set and $3..26$ for the 50-set, around a mean of $n/4\approx 12.5$. No quotient sees a lopsided object.

Put that next to what q4 established at $n=49$: no covering invariant under any of 79 exhausted subgroup classes of $GL(10,2)$, including every $C_7\times C_7$ class, so the "$49=7\times 7$" resonance is dead; and the 7-hole optima are not reachable by any swap of five columns or fewer. So the object that would be a 49 is not a lift, not a symmetry orbit, and not a small perturbation of the known near-misses. Three of the four obvious move classes are closed.

The fourth is a large exact rearrangement along a quotient. Fix the quotient and choose the coset representatives so that $t_{01}+t_{10}=t_{11}$; the twist vanishes and covering radius $\le 2$ becomes four conditions inside $\ker q$:

with $(10)$ and $(11)$ the two label-permuted twins and $\Delta(X)=\{x+x':x\ne x'\}$. Now freeze $A,B,C$ and ask for $D$. Every condition that mentions $D$ collapses into a hitting-set constraint — $u\notin (A^{+}+B)$ forces $D\cap(u+C)\ne\emptyset$, and so on — plus one pair constraint, $h\in\Delta(D)$ for each syndrome the other three blocks miss. That makes "is there any block of size $\le k$ that finishes this?" a finite exact question, decided by constraint-directed depth-first search.

The point is the size of the move. A block carries up to eighteen columns and they are all re-chosen at once, exactly. Asking for a block one column shorter than the one it replaces turns the certified 50-set directly into a candidate 49; asking for one the same size turns a 7-hole 49-residue into a candidate covering. Planted controls confirm the reach: erase an entire block of the certified 50-set, replace it by uniformly random elements of the kernel, and the solver reconstructs a valid block — 7 out of 7, at block sizes up to 14. That is a fourteen-column simultaneous swap, where q4's exhaustive prover stopped at five.

What the sweep found is recorded in ATTACK.md. It did not find a 49.

Asking for symmetry instead of asking for a neighbour

Every attack so far started from a covering somebody already had. Anneal the 51 down to a 50; shrink a block of the 50; repair a 7-hole 49. All of them measure distance from a known object, and after q9 the honest reading is that the 49, if it exists, is not near the 50 in any of those metrics.

So stop starting from the 50.

Pick instead a $\sigma\in GL(10,2)$ of order 7 and ask only for sets that $\sigma$ maps to themselves. The point is not that symmetry is likely — it is that symmetry is cheap. A $\sigma$-invariant set is a union of $\sigma$-orbits, and if $\sigma$ has a 1-dimensional fixed space then every orbit has size 7 and there are 146 of them. Since $49=7\cdot7$, and the single fixed vector $f$ cannot be used (7 does not divide 48), a $\sigma$-invariant 49-set is exactly seven of those 146 orbits. The search space has gone from $\binom{1023}{49}$ to $\binom{146}{7}$.

Then the structure keeps giving. $f$ still has to be covered, and $f\notin S$, so $f=a+b$ with $a,b\in S$ — which forces $b=a+f$, so the orbit of $b$ is the orbit of $a$ shifted by $f$. Every solution therefore contains a partner pair $\{O,O+f\}$. There are 73 of them, and the centraliser of $\sigma$ — which carries solutions to solutions — fuses them into one class, or three, depending on which of the two module types $\sigma$ has. Four searches, each about $\binom{144}{5}$ wide. Half a billion each, seconds of machine time, and they all come back empty.

The thing that makes this feel like mathematics rather than search is what happens next. $\sigma$ has odd order, so $V=M\oplus T$ splits canonically with $T$ the fixed space, and the projection onto $T$ is just $\pi_T(v)=\sum_{i<p}\sigma^i(v)$ — averaging, except that over $\mathbb F_2$ dividing by $p$ is free. Call $\pi_T(v)$ the layer. Now look at where sums can go:

The layer of every sum is forced. So a solution can only ever touch the layers in $\{0\}\cup\{t_i\}\cup\{t_i+t_j\}\cup\{t_i+g\}$, at most $1+k+\binom k2+km$ of them, and there are $2^c$ layers that all need covering. Sometimes that inequality just fails, and a whole family dies with no search at all: order 7 with a 7-dimensional fixed space, order 31, order 3 with $c=8$, and at $r=11$ order 7 with $c=8$ and order 31 with $c=6$. A second version of the same idea counts how full a cross-free layer can get, and independently kills the $(k,m)=(5,14)$ cases that the machine had already exhausted — the proof and the search agreeing is worth more than either alone.

What is left after all of it is a statement about an object nobody has seen. The odd primes dividing $|GL(10,2)|$ are $3,5,7,11,17,31,73,127$. Orders 11, 17, 31, 73, 127 die on arithmetic or on layers. Order 7 dies on 16 exhaustive searches covering every fixed-space dimension and both module types. So if a 49-set exists at all, its automorphism group is a $\{2,3,5\}$-group — it is, in a precise sense, almost rigid. That is not a lower bound and it does not build anything. It does say the 49 will not be found by asking it to be pretty.

The same machinery pointed at $r=11$, where the record 79 has far more slack, gave the one moment of real hope in the run: an element of order 23 acts on $\mathbb F_2^{11}$ with no fixed vectors at all and 89 orbits of size 23, so an invariant set has size a multiple of 23 — and $69=23\cdot3$ is ten below the record. Three orbits out of 89. Three thousand eight hundred and twenty-eight possibilities. All of them checked in under a second, and none of them is a covering. The same search happily produces a $C_{23}$-invariant 92-set, so the machinery works; 69 is simply not there.

There is a sting in the tail. Having spent the run asking which symmetries a 49-set could have, the obvious question is which symmetries the coverings we already have do have — and the answer is a lot. The certified 50-set has an automorphism group of order 128; the 2003 Kaikkonen–Rosendahl 51-set has one of order 512. Both are 2-groups. Both, that is, sit in exactly the one case the odd-prime sweep cannot reach, because a single involution never cuts the search enough to be worth prescribing.

That is not a contradiction, but it is a rebuke. The right reading is that these objects are built, not stumbled on, and what builds them is 2-group structure. Prescribing those particular groups at 49 fails for a reason you can see immediately once you look: the 127 vectors sitting in small $\mathrm{Aut}(50)$ orbits form a 7-dimensional subspace, so any invariant set assembled from them never leaves that subspace and misses 896 syndromes outright. The orbits that do reach are size 16, and $16+16+16+1$ is the only economical way to make 49 — all 74400 of those, and the best leaves 499 holes.

So the group is too coarse and the subgroups are too many. Sampled subgroups of order 16 get the residue down to 83 holes, which sounds close and is not: every one of those searches hit its cap, none was decided, and a hole count is not a bound. It is a signpost, and it points somewhere specific for once.

q11 — stop perturbing the set, prescribe the fibration

The previous two quests both took a covering as the thing to be modified: q9 swapped out one quotient block of the certified 50, q10 demanded that a group act on the answer. Both are moves on a set. The signpost at the end of q10 says the objects are built rather than stumbled on, so this time the thing that gets prescribed is not the set and not its symmetry but its shape.

Fix a splitting $\mathbb F_2^r = V\oplus W$ and demand that the column set have exactly one column over every nonzero point of $W$, with everything else in the kernel. Then $n = |A| + 2^{\dim W}-1$ is decided before any searching, and the covering condition falls apart into two clean halves: the kernel block $A$ must be a covering of $V$ by itself, and for each nonzero $u$ the pair sums $g(w)+g(w+u)$ must supply exactly the part of the fibre that $A$ cannot reach. The unknown is a function, not a set, and no known covering is anywhere in the input.

The pretty part came from noticing that the pair $\{w,w+u\}$ and the point $u$ span the same plane. So the quantity that matters, $g(w)+g(w+u)+g(u)$, is not a function of the pair at all — it is a function of the line of $\mathrm{PG}(\dim W-1,2)$ that the plane is. The whole condition then reads: a colouring of the lines by $V$ in which every point sees every colour of a fixed set $B$. The lengths run backwards through $|B|$, so the family is one question: how many colours can be made universal.

Two things fall out immediately once it is a colouring. A colour class has to cover every point with lines, so it needs at least a third of the points' worth of lines, and the classes are disjoint — that is a counting bound, and at $r=10$ it says the family can never produce a 47 or shorter, which is strictly better than what the volume count knows. And if $g$ is quadratic the colour set sits inside the image of an alternating form; over an odd-dimensional space every alternating form is degenerate, and running that through every linear functional collapses $B$ to nothing. $r=10$ has $\dim W=5$. The quadratic members are simply not there.

Then the family was run. It is exactly decidable at $r\le8$, and what it produces is startling in the wrong direction: 5, 13, 19, 26, 39 — the documented lengths at $r=4$, $6$, $7$, $8$, $9$, including both Gabidulin–Davydov–Tombak odd-$r$ values, out of a two-line definition, with $n=23$, $24$ and $25$ at $r=8$ exhausted so it provably cannot do better. One family, several records, no dent.

And at $r=10$ it tops out at 54. That is the useful failure. At odd $r$ the base can be one dimension bigger than the fibre, every fibre gets $2^m-1$ pairs to cover $2^m$ targets, and the arithmetic is comfortable — which is exactly why odd $r$ has a closed formula. At even $r$ the two halves must be equal, each fibre is short by half, and the deficit is paid by the kernel block, which then wastes almost all of its own pair sums: at $n=49$ the block of 18 supplies 171 covers for 31 targets and burns 140 of the 202 slack in a single fibre. The record 50 is not in the family, and it cannot be. The family says something about why 10 is the hard one — not about what a 49 looks like.

The near miss is at $r=9$, not $r=10$. A 38 there would beat 39, it needs eight universal colours, and eight universal colours are easy to get. Every single time, they came out as an affine hyperplane — and then the kernel block is a hyperplane minus zero, its own sums never leave the hyperplane, and fibre 0 is uncoverable no matter what $g$ does. Twenty-nine samples, thirteen distinct, all of them hyperplanes. That is a pattern, not a proof, and the honest name for $n=38$ is residue.

This session ends here

Overnight 2026-08-21: three construction families, no 49. The record is still $\ell_2(10,2)\le 50$. Sphere covering still only $\ge 45$.

The useful facts, in one place. The 51 and the 50 are not lifts of the $r=8$ record. A 49, if it exists, is not a single-block shrink of the 50, is not $C_7$-invariant, and is not in the fibered graph family that reproduces the odd-$r$ table values (that family cannot even reach 47 at $r=10$). Its automorphism group, if any, is a $\{2,3,5\}$-group; the known 50 and 51 are 2-group symmetric, which is the case nobody exhausted.

The nearest unfinished hole in these families is $n=38$ at $r=9$, not 49 at $r=10$: seventeen kernel-block classes, every one floors at the same 14 missing incidences, none decided. That is residue, not a bound.

Reopening at 817: the partition was already in the construction

The number that looked missing was 34. The notebook had a certified $26$ by $817$ radius-3 matrix, and QM₄³ at $m=6$ would turn it into $64(817+1)-1=52351$ columns, 64 below the published value at redundancy 44. But the lift needed a $(3,0)$-partition into at most 65 blocks. The matrix file had no such labels attached to it.

The recent OK37 attempt made the obvious next move look like another partition search: enumerate one-, two-, and three-column representations, encode block colours, and ask SAT to coarsen them. That route had just settled a 37-column seed at 18 rather than the needed 17. Scaling the same representation encoding to 817 columns would have attacked the bookkeeping before reading how those 817 columns were made.

That failure was useful because it put the emphasis on provenance. The 817 matrix is not an opaque set. It came from QM₅³, with a perfect Golay seed and the notebook's 50-column radius-2 matrix sitting inside its D₄ block. The proof of QM₅³ states the output partition count explicitly:

Then the click is only the substitution. The Golay partition is trivial, so it contributes 23 blocks. The embedded 50-column matrix has its certified 10-block partition. The Hamming W₅ columns form one more block. Thus $23+10+1=34$. What appeared to be a new colouring problem was an omitted artifact of the old construction.

The labels follow the column order of the existing builder. The first 31 W₅ columns share one block; the next 50 columns inherit their ten labels; and each of the 23 groups of 32 Golay lifts is one block. A refinement cannot destroy a representation whose columns already lie in distinct blocks. Split the first Golay group in two and split the 31 Hamming columns into singletons: $34+1+30=65$. Those 65 blocks can now receive, one each, every indicator in $\mathbb F_{64}\cup\{*\}$.

The computer check keeps the large space out of memory. A standalone C program uses an 8 MiB bitset and enumerates every allowed singleton, pair, and triple of the 817 seed columns. The 34-block labels cover all 67,108,864 syndromes; so do the 65 refined labels. It then checks the field $\mathbb F_2[x]/(x^6+x+1)$, rank and distinctness, and every one of the 52,351 columns against either D₃ or $A(h,\beta)$. The construction theorem, not a $2^{44}$ bitmap, carries that finite seed certificate to the output.

What is proved is the upper bound $\ell_2(44,3)\le52351<52415$. The output has covering radius exactly three: the theorem gives at most three, while the radius-two volume is smaller than $2^{44}$. Nothing here proves optimality, and none is claimed.

One block too many at redundancy 41

The 34-block partition above left a narrow gap. At $m=5$, the field plus $*$ has only 33 indicators; at $m=6$, it has 65. The latter gives the redundancy-44 construction, but the former would land at redundancy 41 with length 26,175. The missing degree of freedom was one merge of two inherited blocks, not a new field or seed matrix.

The earlier fixed-matrix partition attack on the 37-column Östergård–Kaikkonen seed had shown that its required 17-block threshold is impossible. That failure did not say anything about merging the 817-column seed. Nor did the radius-2 single-block replacements speak to this radius-3 partition. The useful lesson was to test the exact partition condition before building another large lift.

The test counted all admissible three-column representations of each seed syndrome. A proposed merge only destroys representations that use one column from each of the two merged blocks. If any representation survives, the syndrome remains covered. All 561 block pairs could therefore be tested against the same representation counts. Two survived: $(7,31)$ and $(15,24)$. The first was carried forward, giving 33 blocks.

The independent check then swept all $2^{26}$ seed syndromes under the new labels, verified the field $\mathbb F_2[x]/(x^5+x^2+1)$, and compared each of the 26,175 output columns with the QM$_4^3$ formula. The construction theorem turns that finite seed certificate into $\ell_2(41,3)\le26175<26238$. It also improves the notebook's earlier 26206. The large output syndrome space was not enumerated.

We next asked whether simply deleting a seed column would make the lift shorter still. Counting representations revealed a sharper obstruction: every one of the 817 columns is needed by at least one uniquely represented syndrome, even when block labels are ignored. That closes deletion from this particular seed. Other 816-column matrices, a different small radius-3 seed, and the 49-column radius-2 problem remain open.