MathDB

MDS conjecture for general codes

About 6 years old · traced to

Let G=([n],E)G=([n],E) be a kk-uniform hypergraph, and let q(G)q(G) be the smallest alphabet size for which there are encoding and decoding functions recovering every message from the symbols on every edge of GG. For the complete nn-vertex kk-uniform hypergraph κn,k\kappa_{n,k}, q(κn,k)q(\kappa_{n,k}) is the minimum alphabet size of a general (n,k)(n,k) MDS code. For integers k<q≠6k<q\neq 6, let n(q,k)n(q,k) be the largest integer nn such that q(κn,k)≤qq(\kappa_{n,k})\leq q. MDS conjecture for general codes.

n(q,k)≤{q+2if 4∣q and k∈{3,q−1},q+1otherwise.n(q,k)\leq\begin{cases}q+2 & \text{if }4\mid q\text{ and }k\in\{3,q-1\},\\q+1 & \text{otherwise.}\end{cases}

This is the classical upper bound on the length of general MDS codes over an alphabet of size qq. The supplied status evidence says that the linear version over prime fields has been proved, but it does not establish resolution of this general-code statement; its database status is therefore left open.

References

Primary source

Mira Gonen, Ishay Haviv, Michael Langberg and Alex Sprintson, “Minimizing the alphabet size of erasure codes with restricted decoding sets”, arXiv:2005.06947 (2020).

error-correcting-codesfinite-fieldsmds-codes
Posted

Progress summary

Refreshed
Open

The conjecture remains open: only the narrower linear case over prime fields is known to be settled, and no proof or counterexample for general codes was found.

The conjecture gives an upper bound on the length of a general MDS code over an alphabet of size qq, with an exceptional q+2q+2 bound when 4∣q4\mid q and k∈{3,q−1}k\in\{3,q-1\}. It was explicitly formulated as an open central problem in 2020.

Known results

  • The case k=2k=2 is known.
  • Ball proved the corresponding MDS conjecture for linear codes over prime fields.
  • Results for some restricted parameter ranges and erasure patterns are known, but do not settle general, possibly nonlinear, codes.

February 4, 2021 follow-up

A subsequent paper again treated both the general and linear statements as conjectures; its results concern restricted erasure patterns and hypergraph parameters, not the complete-hypergraph case. No claimed proof, counterexample, or later settlement was found.

Current status (as of September 2026): The linear version over prime fields is settled, but the general-code conjecture remains open, with no claimed proof or counterexample found.

Sources

Solutions 0

No solutions have been posted yet.