The longest code that survives every erasure

A polynomial through the gaps built the Reed–Solomon code: write a message of $k$ symbols as the coefficients of a polynomial of degree less than $k$ over a finite field, and send its values at $n$ points. Any $k$ values determine the polynomial, so any $n - k$ of the sent symbols can be lost without losing the message. No code can do better — losing $n - k + 1$ symbols leaves fewer than $k$, which cannot carry $k$ symbols of information — so a code with this tolerance is as good as a code of its length and size can be. Such codes are called maximum distance separable, MDS for short.

There is a catch, and erasures a code can see ended on it. A Reed–Solomon code needs a distinct point of the field for each symbol it sends, so over a field of $q$ elements it has length at most $q$, or $q + 1$ with one extra point at infinity. Longer codes need larger alphabets. The question is whether that limit belongs to Reed–Solomon codes or to MDS codes in general: can any code survive every pattern of $n - k$ erasures and be longer than $q + 1$?

The MDS conjecture says no, except in a specific family of cases where the field has even size and the length can reach $q + 2$. This essay checks it by brute force for every field of up to nine elements, finds the exceptions exactly where the conjecture puts them, and describes the proof that settles it for prime alphabets and why it stops there.

Fifty-six erasure patterns, all survived #

A linear code is described by a generator matrix: $k$ rows and $n$ columns, with the sent word the message times the matrix. Each sent symbol is the message combined with one column. Keeping a set of $k$ symbols means keeping $k$ columns, and the message can be recovered exactly when those $k$ columns are independent — when the square matrix they form can be inverted. So a code survives every pattern of $n - k$ erasures exactly when every $k$ of its $n$ columns are independent.

For the extended Reed–Solomon code of length 8 carrying 3 symbols of the field with seven elements, the columns are $(1, a, a^2)$ for each of the seven elements $a$, and one more column $(0, 0, 1)$. Every three of them are independent: three distinct values of $a$ give a Vandermonde matrix, whose determinant is a product of differences and never zero, and the extra column plays the role of a point at infinity. The figure checks all 56 triples.

A code with eight columns chosen at random does almost as well and not quite: four of its 56 triples are dependent, so four patterns of five erasures destroy the message. Random codes are good on average, as the previous essay’s random matrices were, but maximum distance separability is an all-or-nothing property, and a random choice almost never achieves it when the length is close to the limit.

The shortfall is easy to estimate. Three random columns over the field of seven elements form an invertible matrix with probability $\frac{(7^3 - 1)(7^3 - 7)(7^3 - 7^2)}{7^9} \approx 0.837$ — the first column must be non-zero, the second outside the first’s span, the third outside the plane of the first two. So each of the 56 triples fails with chance about $0.163$, and a random code of this shape has on average about nine dependent triples. The one drawn has four. For all 56 to succeed at once, every triple must avoid a small but real chance of failure, and the chance that a random code manages it is minute.

That is the general shape of the problem. Codes that are good on average are easy to find, and the rate a noisy channel allows proved Shannon’s theorem with them. Codes that are perfect in the worst case — every erasure pattern survived — need structure, and the structure that works is algebraic: the Vandermonde matrices of polynomial evaluation, where independence is guaranteed rather than likely.

Columns as points, codes as arcs #

The condition “every $k$ columns independent” is geometric. Two columns that are multiples of each other are dependent, so what matters about a column is only the line through the origin it spans — a point of the projective space of dimension $k - 1$ over the field. An MDS code of length $n$ is therefore a set of $n$ points in that space, every $k$ of them in general position: for $k = 3$, $n$ points in a projective plane with no three on a line.

Such sets are called arcs, and for the plane they are the subject of the curve that no three points in line define and every power of x that draws a hyperoval. The Reed–Solomon columns $(1, a, a^2)$ lie on the conic $y^2 = xz$, and a conic in a projective plane of order $q$ has exactly $q + 1$ points with no three in line. In the plane of order 8 the conic can be extended by one more point, its nucleus, to a hyperoval of 10 points — and a hyperoval is an MDS code of length $q + 2$.

The question about codes becomes a question about arcs: how many points can a projective space of dimension $k - 1$ over a field of $q$ elements hold with every $k$ in general position? For the plane, Beniamino Segre answered it in 1955: $q + 1$ when $q$ is odd, $q + 2$ when $q$ is even. In higher dimensions, Segre asked the same question, and the conjectured answer is the MDS conjecture.

Searching every code for small fields #

For small fields the question can be settled by exhaustive search. The search builds an arc point by point, keeping only points that stay in general position with every choice of $k - 1$ points already chosen, and backtracks when no point fits. A symmetry makes it fast: any $k + 1$ points in general position can be moved to the standard frame — the $k$ coordinate points and the all-ones point — by a change of coordinates, so the search may begin with those fixed.

The table records the result for every field of up to nine elements and $k$ up to 6. Every entry is $q + 1$ when $2 \le k < q$, except at $q = 4$ and $q = 8$ with $k = 3$, where it is $q + 2$: the hyperovals. When $k \ge q$ the answer is $k + 1$, which is trivial — the $k$ coordinate points and the all-ones point always work, and no more can be added. The conjectured formula predicts every cell, and the search finds nothing longer anywhere it can reach.

The smallest exception is worth seeing by hand. Over the field with four elements, a code carrying 3 symbols can have length 6, one more than $q + 1 = 5$: the six columns are the five points of a conic in the plane of order 4 together with the conic’s nucleus, the single point that every tangent line passes through. In odd characteristic the tangents to a conic do not meet in one point, there is no nucleus to add, and the conic’s $q + 1$ points are the most an arc can hold — which is Segre’s theorem for the plane.

The Hamming code of finding the error without reading the message is a useful contrast. It carries 4 bits in 7 and has minimum distance 3, one short of the Singleton bound’s $7 - 4 + 1 = 4$, so it is not MDS: some patterns of three erasures destroy its message. Over the field of two elements that is unavoidable — the table’s first row says an MDS code over two symbols can have length at most 3 for $k = 2$ — and binary codes buy their length by giving up the perfect tolerance.

The search is not the proof, and its reach is limited. The field of nine elements with $k = 6$ takes over a minute, and larger fields and dimensions grow far beyond exhaustion. What the table shows is the pattern the conjecture describes, confirmed without exception in the range where anything can be checked by hand or machine.

Flat at q plus one #

Plotted against $k$, the pattern is striking: the greatest length is flat. Over the field of seven elements it is 8 for $k = 2, 3, 4, 5, 6$ — carrying more symbols does not let such a code be longer. Over the field of eight elements it is 9, except for the bump to 10 at $k = 3$. Over nine elements it is 10 as far as the search reaches.

The flatness is the content of the conjecture. A longer code would need more points in general position, and adding dimensions gives more room for points but also makes “every $k$ in general position” a stronger demand, and the two effects cancel exactly: the normal rational curve $(1, t, t^2, \ldots, t^{k-1})$ with its point at infinity gives $q + 1$ points in every dimension, and nothing known gives more. If the conjecture is right, the Reed–Solomon construction is the whole story, apart from the even-characteristic bump.

The exception comes in pairs #

Every linear code has a dual: the words that are perpendicular to every codeword. If a code has length $n$ and carries $k$ symbols, its dual has the same length and carries $n - k$. A classical theorem says the dual of an MDS code is MDS. The figure checks it on the hyperoval code over the field of eight elements: its generator has 10 columns, every 3 independent; the dual’s generator, computed as the null space of the first, has 10 columns of length 7, and every 7 of them are independent.

So the exceptional length $q + 2$ appears twice for each even field: at $k = 3$, the hyperoval, and at $k = q - 1$, its dual. That is why the conjecture’s exceptions are stated as “$q$ even and $k$ equal to 3 or $q - 1$”. The search in the table reached $k = 3$ for $q = 8$; the dual exception at $k = 7$ lives in a projective space of dimension 6 with nearly 300,000 points, far beyond the search, and is known by duality rather than by search.

Weights that the parameters force #

An MDS code is rigid in another way. Its weight distribution — how many codewords have each number of non-zero symbols — depends only on its length, its dimension and the field, not on which MDS code it is. For length 8, dimension 3 and the field of seven elements, the counts are 1 codeword of weight 0, then none until weight 6, then 168 of weight 6, 48 of weight 7 and 126 of weight 8. The figure counts all $7^3 = 343$ codewords and matches the formula exactly.

The rigidity follows from the erasure property. Fixing any $n - k$ positions to zero leaves a code that must still behave perfectly on the rest, and counting codewords by where they vanish, over all choices of positions, determines every weight count by inclusion and exclusion. The minimum weight $n - k + 1 = 6$ is the Singleton bound met with equality, which is what “maximum distance” in the name means. The best a code can be compared codes against the Singleton bound and others; MDS codes are exactly the ones that meet it.

Where the perfect codes are used #

The limit $q + 1$ matters in practice because MDS codes are everywhere that data must survive losses. Compact discs protect their music with two interleaved Reed–Solomon codes over the field of 256 elements; QR codes carry Reed–Solomon check symbols that let a smudged square still be read; the Voyager probes sent their images home through a Reed–Solomon code of length 255 carrying 223 symbols; and the storage systems that keep data on many disks at once use MDS codes so that any few failed disks can be rebuilt from the rest.

Every one of those systems works over a field of $2^8 = 256$ elements, because a byte is eight bits, and every one is limited to lengths of about 257 symbols by the bound this essay is about. A storage system wanting to spread one file over a thousand disks with perfect tolerance must either use a larger field — more bits per symbol, and slower arithmetic — or give up perfect tolerance. The practical question of how long a code can be, over the field computers find natural, is exactly the part of the MDS conjecture that is still open.

Ball’s proof for prime alphabets #

Simeon Ball proved the MDS conjecture in 2012 for every field whose size is a prime $p$: no code over $\mathbb{F}_p$ that survives every pattern of $n - k$ erasures has length more than $p + 1$, for $k \le p$. His proof is algebraic. From a supposed arc larger than $q + 1$ it builds polynomials that vanish at many points of the field, and a lemma of Segre’s — a version of the fact that a polynomial of small degree cannot vanish too often — forces a contradiction.

The argument uses the prime field in a precise place: a binomial coefficient that must not be divisible by the characteristic, which fails when the field’s size is a higher power of its characteristic. Ball and Jan De Beule extended it to fields of size $p^h$ for $k$ up to $2p - 2$, but for larger $k$ over non-prime fields the argument breaks, and those cases — including many used in practice, where the field has $2^8 = 256$ elements — are open.

Solutions that come in multiples of p showed the same kind of polynomial counting at work in finite fields, where the number of solutions of an equation is forced to be a multiple of the characteristic. Ball’s proof lives in that tradition: it turns a question about configurations of points into a statement about which polynomials can exist.

Still open: fields of prime-power size #

The MDS conjecture is open for every field whose size is a prime power that is not prime, beyond the range Ball and De Beule reached. The field of 256 elements, used in almost every storage system that relies on Reed–Solomon codes, is one of them: it is believed, but not proved, that no MDS code over it is longer than 257, apart from the exceptions at $k = 3$ and $k = 255$.

The difficulty is structural. Arcs in projective spaces over fields of characteristic 2 have more room — the hyperovals are the evidence — and the arguments that bound arcs in odd characteristic fail there. Whether other exceptional arcs exist in higher dimensions over fields of characteristic 2, beyond the hyperoval and its dual, is exactly what the conjecture denies and what no proof yet rules out. The search above, which finds nothing longer, reaches only a few small cases of that question.

What the tables cannot show #

Every entry in the table was found by exhaustive search, starting from the standard frame, and every code drawn was checked by testing all its column subsets; the weight distribution was counted codeword by codeword. Those are complete checks of the cases shown and nothing more. The conjecture is about every field and every dimension, and the search covers fields of at most nine elements and dimensions of at most six.

The symmetry used to start the search is exact — any $k + 1$ points in general position can be moved to the standard frame — so the search misses nothing it claims to cover. But it only answers the question asked: the greatest length of an arc. It does not classify the arcs of that length, which for larger fields come in several inequivalent kinds, and it says nothing about fields beyond its reach.