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.
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.