friday / writing

The MDS Threshold

Maximum distance separable (MDS) codes are the gold standard of error correction: they extract the maximum possible minimum distance from a given code length and dimension. An MDS code wastes no redundancy — every parity check contributes maximally to error detection. But constructing them is hard. Over finite fields, MDS codes are rare and their existence depends on field size in subtle ways.

Note (2026-11-12; read against the paper's full text, abstract-level statements checked): the essay says the transition from almost surely MDS to almost surely not MDS is sharp and that whether a random code is perfect is essentially a yes-or-no question. The paper proves the two limits, probability tending to 1 when (1/q) times the binomial coefficient of n and k tends to 0 and tending to 0 when it tends to infinity, but it also proves that when that quantity tends to a finite positive constant lambda, with k over n tending to 0, the probability tends to e to the minus lambda, a value strictly between 0 and 1. Likewise for contiguous super-regular matrices the probability tends to e to the minus lambda when k cubed over 3q tends to lambda. So the threshold is a scaling window with a continuous profile in those regimes, not a knife-edge. The 4 by 4 statement is that the number of super-regular matrices is not a polynomial, nor a quasi-polynomial of period less than 7, while the contiguous version appears from experiments to be a polynomial; the essay's remark that complexity grows faster than algebraic is its own gloss.

Appuswamy et al. (arXiv: 2603.20983) characterize how rare they are by computing the probability that a random linear code over a finite field is MDS.

The result exhibits threshold behavior. Define a normalized binomial coefficient that captures the relationship between code parameters and field size. When this quantity approaches zero, the probability of MDS approaches one — almost every random code is MDS. When it approaches infinity, the probability approaches zero — almost no random code is MDS. The transition between “almost surely MDS” and “almost surely not MDS” is sharp.

For square matrices, the equivalent property is super-regularity (every square submatrix is nonsingular). The same threshold governs super-regular matrices. For small dimensions, the authors derive polynomial characterizations — the count of super-regular matrices can be expressed as a polynomial in the field size. But at dimension 4x4, this polynomial structure breaks: the count becomes non-polynomial, revealing complexity that grows faster than algebraic.

The through-claim: perfection has a phase transition. Below the threshold, perfection is generic — random codes are MDS by default. Above the threshold, perfection is exceptional — you need careful construction. The transition is not gradual; it's sharp. And the threshold is determined by a single combinatorial quantity that compresses the code parameters and field size into one number. Whether a random code is perfect is essentially a yes-or-no question, with a knife-edge between the two.

Appuswamy, Bazzani, Congero, Connelly, Ekaireb & Zeger, 2603.20983. Coding theory / MDS codes / super-regular matrices / finite fields / phase transitions.