← All problems

Deep-hole classification conjectures for full-length Reed–Solomon codes

For every prime power qq and integer 1≤k<q1\le k<q, let RS⁡q(k)={(f(a))a∈Fq:f∈Fq[x], deg⁡f<k}⊆Fqq\operatorname{RS}_q(k)=\{(f(a))_{a\in\mathbb F_q}:f\in\mathbb F_q[x],\ \deg f<k\}\subseteq\mathbb F_q^q. For each received word u∈Fqqu\in\mathbb F_q^q, let fu∈Fq[x]f_u\in\mathbb F_q[x] be its unique interpolation polynomial of degree at most q−1q-1. Determine exactly all received words uu satisfying dist⁡(u,RS⁡q(k))=q−k\operatorname{dist}(u,\operatorname{RS}_q(k))=q-k, equivalently all deep holes of the full-length Reed–Solomon code, for arbitrary qq and kk.

References

Progress summary

Refreshed
Open · progress reported

A new paper reports substantial partial classifications and exclusion results, but the complete classification remains open.

The problem seeks a complete description of deep holes in full-length standard Reed–Solomon codes for all parameters. Existing conjectures and results cover important ranges, but not the full arbitrary-parameter problem.

Known results

  • Cheng–Murray, 2007: proposed the standard deep-hole classification conjecture.
  • A 2012 result disproved that conjecture in general by constructing deep holes whose interpolation polynomial has a degree-q−2q-2 monomial component.
  • A 2016 study proved the conjecture for k≥⌊(q−1)/2⌋k \ge \lfloor(q-1)/2\rfloor, apart from an even-field exception, while leaving k<(q−1)/2k < (q-1)/2 open.
  • A 2013 result classified deep holes for prime-field generalized codes in the range k≥(p−1)/2k \ge (p-1)/2, not for all parameters.

October 22, 2026 partial classification

Xiang Fan's paper reports complete classifications for five excess degrees and uniform no-deep-hole bounds for arbitrary mm under field-size conditions, with finite cases supported by certificates and deterministic programs. These are substantial advances, but the report does not claim the remaining arbitrary-mm cases are resolved; the result is treated here as unverified.

Current status (as of October 2026): Several parameter ranges and bounds are claimed, while the complete classification for arbitrary mm remains open.

Sources

Solutions 0

No solutions have been posted yet.