50 columns
cover 1024
syndromes

Two different jobs a code can do

A computer stores data as strings of bits. A string of length n is a list of n zeros and ones. Noise flips some of those bits.

A code is a chosen subset of all the possible strings. We call the chosen strings codewords. You send only codewords. If noise flips a few bits, the result is usually not a codeword. The receiver then looks for the nearest codeword.

A code is designed for one of two opposite jobs.

The first job is error correction. Here you want the codewords far apart. If every pair of codewords has distance 5 or more, you can repair up to 2 flipped bits without any doubt. This is the packing problem. It asks you to pack many balls into the space without overlap.

The second job is covering. Here you want every string in the whole space to sit close to some codeword. No string is allowed to be far from everything. This page is about the second job only.

Covering codes are useful because they let you round. Take any string, move to the nearest codeword, and store the codeword instead. You lose at most 2 bits of accuracy. That idea appears in data compression, in steganography, and in the football pool problem, which asks how few betting slips guarantee a near-win.

The interesting question is cost. Codewords are cheap to store when there are few of them, but few codewords leave big gaps. So we ask a minimum question. How short can a code be and still have covering radius 2?

Why the whole problem fits in 1024 numbers

The question above involves 2ⁿ strings. That is far too many to search. The problem gets much smaller once we restrict to linear codes.

A linear code has a compact description. You write down a matrix H with r rows and n columns, filled with zeros and ones. A string x is a codeword exactly when Hx = 0, computed modulo 2. We call r the redundancy. The code then has 2ⁿ⁻ʳ codewords.

Now comes the step that makes the problem finite. Flip bit i of a string. The syndrome changes by exactly column i of H. Flip two bits, and the syndrome changes by the XOR of those two columns.

So the distance from x to the nearest codeword is the smallest number of columns that XOR to the syndrome of x. This gives the whole problem in one line. Write S for the set of columns of H.

Set r = 10. There are 1024 syndromes. The columns are themselves 10-bit numbers, so they live in the same set of 1024 values. The problem is now completely concrete.

Choose as few 10-bit numbers as you can, so that their pairwise XORs reach all 1024 values.

The example below uses the actual matrix. It shows a syndrome that needs two flips, and which two.

A counting bound gives 45. The published record is 51.

Start with a count. Take n columns. Then you get one empty sum, n single columns, and n(n−1)/2 pairs. Together they give

Solve it and you get n ≥ 45. This is the sphere-covering bound. No known code at r = 10 reaches it.

The count is optimistic because it assumes no two pairs collide. Real column sets collide constantly. In the 50-column matrix on this page, the 1225 pairs produce only 986 distinct results. That means 239 pairs land on a value another pair already reached. Each collision wastes one representation.

So the true answer sits above 45, and finding it is hard. Kaikkonen and Rosendahl published a 51-column matrix in 2003. That has stayed the shortest published answer for over twenty years. A search run in 2026 found a 50-column matrix. The map below is that matrix.

The map is mostly dark. Of the 973 syndromes that need a pair, 821 have exactly one pair that reaches them. The matrix has almost no spare capacity.

You can test this directly. Remove any single column and the map breaks. The least damaging choice still leaves 9 syndromes with nothing reaching them. Try the button and see.

How the search ran

The start was the published 51-column matrix. Among its 51 single deletions, removing the column stored as the integer 419 leaves 11 of the 1024 syndromes unreached, the fewest possible. That 50-column set was the seed.

The search keeps exactly 50 distinct nonzero columns at all times and scores a position by counting the syndromes that nothing reaches. A table of 1024 counters makes the score cheap to maintain. Swapping one column only touches its own counter and the 49 pair sums that involve it, about 100 updates instead of recounting all 1276 sums.

Most moves aim at a hole. Pick an unreached syndrome g, then offer g itself as a new column, or g XOR s for a current column s, so the swap covers the hole at once. One uniformly chosen column is deleted in exchange. Simulated annealing decides acceptance. Improvements always pass. Uphill steps pass with a probability that shrinks as the temperature falls from 3.5 to 0.05 across each cycle of 80,000 proposals. At the end of a cycle the search resets to the best state seen so far.

The random numbers come from a fixed xorshift64 seed, so the whole run replays exactly. Run 0 reached zero holes at proposal 3,600,281, a few hundred proposals after its 45th reset. The final matrix keeps 35 of the 50 seed columns. The committed script compute/search_radius2.py replays the run.

The same method failed on three nearby gaps. It missed 3 of 256 syndromes at redundancy 8. At redundancy 9, every single deletion from the published 39-column set left at least 8 of 512 unreached. With 49 columns at redundancy 10 it stalled at 7 of 1024. Exact solvers returned no verdict either way. Those numbers say where the search stopped, not what is impossible.

Why one column matters

The step from 51 to 50 looks small. Its effect is larger, because the published table is built by iteration.

Davydov, Marcugini and Pambianco published the current best bounds in November 2025. Their tables list a value for every redundancy r up to 64. They do not find each value separately. A construction they call QM₂² produces a long code from a short one.

Their radius-2 family iterates from a single starting point, the 51-column matrix at r = 10. Their own proof calls the structure of that matrix "very important for the next iterative process."

So the entry at r = 10 controls the family. Improve it by one column and every entry produced from it improves. The limit that the family approaches improves as well.

A shorter matrix is not enough

The growth construction needs a second thing from its starting matrix. It needs a way to sort the columns into blocks.

The number of blocks controls how much you can grow the code in one step. The construction requires p(H) ≤ 2ᵐ ≤ n. Fewer blocks means larger steps are legal.

The published 51-column matrix needs 11 blocks. The 50-column matrix accepts 10. That is both smaller and safely under the 16 that the first growth step requires.

Finding the split is a constrained graph coloring problem. The 821 syndromes with exactly one pair force those two columns into different blocks, which produces a graph with 821 edges. The other 152 syndromes are less constrained. Each one only needs one of its 2 to 6 pairs split across blocks.

A separate search on the same day found the split. That search code is not in the repository. The repository keeps the split itself as data, plus two independent verifiers, in two languages, that re-derive the columns from the matrix text and verify all 1024 syndromes. The block labels are the only thing read from the data file. Nobody has shown that 10 blocks is the fewest possible.

The matrix also has a third property that later growth steps need. It has exactly ten triples of columns that XOR to zero. Exactly one of them has its three columns in three different blocks.

What the new seed produces

Apply the published construction to the 50-column matrix. Take m = 4, then m = 5. Then verify the results by enumerating every syndrome, with no sampling.

The fourth column of that table has a name. It is the covering density: the total number of representations divided by the number of syndromes. It is the average number of ways each syndrome gets reached. It can never drop below 1. A value near 1 means an efficient code.

As redundancy grows, this family drives the density toward 2601/2048 ≈ 1.27002. Compare that to the record before it.

The step on the right is bigger than the step on the left. The 2025 paper moved a number that had stood for 33 years. Reseeding it with one fewer column moves it further.

What this does not prove

• 50 is not proven best. The counting bound only says ℓ₂(10,2) ≥ 45. Five columns of room remain unexplored.
• The failed search at 49 proves nothing. Every run stopped with 7 syndromes uncovered. Later work measured the depth of that leftover. No exchange of up to 5 columns repairs the best near-miss, an exhaustive claim. Two genuinely different near-misses exist that no linear map carries onto each other. That describes the search landscape. It says nothing about whether 49 columns suffice.
• Nobody has confirmed priority yet. The published table says "best as far as the authors know". Somebody must search the older workshop proceedings and the field bibliography before anyone claims a record.
• The far end of the family is weaker. The steps at m = 4 and m = 5 were verified exhaustively. Later steps rely on a bound from the paper instead of a computed block split. A referee will ask about this step first.
• The big question stays open. The limit of the best possible densities as redundancy grows has a name: Green's f(2). Nobody knows its value. It might be as low as 1. This work moves an upper limit on it and nothing else.
• Nearby cases did not fall. The same search failed at redundancy 8 and 9. It missed 3 and 8 syndromes there.

Search and proof are separate

The search only had to succeed once. The proof does not use it. The claim is a finite statement about 500 committed bits.

Two independent programs verify that statement in about two seconds. They read the matrix from text and do not trust the search or its author.