Math Conjectures

Main Conjecture for MDS Codes

OPENLandmarkConjectureProposed 1955 · Standard version

Canonical statement

Let qq be a prime power and 2≤k≤q−12\leq k\leq q-1. If C⊆FqnC\subseteq\mathbb F_q^n is a kk-dimensional linear code whose minimum Hamming distance is n−k+1n-k+1, then
n≤q+1, n\leq q+1,
except that, when qq is even and k∈{3,q−1}k\in\{3,q-1\}, the asserted bound is n≤q+2n\leq q+2. The Hamming distance between two words is the number of coordinates in which they differ; a code meeting the general bound n−k+1n-k+1 is called maximum-distance separable (MDS).
View source LaTeX
Let \(q\) be a prime power and \(2\leq k\leq q-1\).
If \(C\subseteq\mathbb F_q^n\) is a \(k\)-dimensional linear code whose
minimum Hamming distance is \(n-k+1\), then
\[
  n\leq q+1,
\]
except that, when \(q\) is even and \(k\in\{3,q-1\}\), the asserted
bound is \(n\leq q+2\). The Hamming distance between two words is the
number of coordinates in which they differ; a code meeting the general
bound \(n-k+1\) is called maximum-distance separable (MDS).
INFO-004:[Segre1955Ovals][Ball2012MDS][BallDeBeule2012MDS][HanRen2024MDS]
Information theoryCombinatorics

Notes

The conjecture is proved when qq is prime and in many parameter ranges over nonprime finite fields. The stated bound for all prime powers and all remaining dimensions is still unknown.
This record uses the standard linear-code form of the MDS conjecture.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.