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

About 10 years old · traced to

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 q−1q-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 2≤k≤q−22 \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=q−3k=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.

References

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.