Cheng–Murray conjecture on deep holes of full-length Reed–Solomon codes

Let qq be a prime power, let θ\theta be a primitive element when relevant, and let RSk(Fq){\rm RS}_k(\mathbb{F}_q) denote the full-length Reed–Solomon code of dimension kk. For a vector in Fqq\mathbb{F}_q^q, its generating polynomial is the unique polynomial of degree at most q1q-1 agreeing with the vector on all elements of Fq\mathbb{F}_q; a deep hole is a vector at covering-radius distance from the code. Cheng–Murray conjecture. For 2kq22 \leq k \leq q-2, all deep holes of RSk(Fq){\rm RS}_k(\mathbb{F}_q) have generating polynomials of degree kk, except when qq is even and k=q3k=q-3. This conjecture characterizes the deep holes of full-length Reed–Solomon codes, extending the known fact that generating polynomials of degree kk produce deep holes. Its status is not resolved by the supplied source.

Sources & referencesView supporting material

Primary source

Weijun Fang, Jingke Xu and Ruiqi Zhu, “Deep Holes of Twisted Reed-Solomon Codes”, arXiv:2403.11436 (2025).

Additional references

4 papers in this index state this conjecture (2016–2024). The statement above is taken from the most recent of them; the others are arXiv:2205.02277, arXiv:1806.00152, arXiv:1612.05447.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.