TOPICS
Search

Deep Hole


A deep hole of an error-correcting code is a word whose Hamming distance to its nearest codeword equals the code covering radius. For the full-length Reed-Solomon code of dimension k over F_q, this radius is q-k. Each word has a unique interpolation polynomial u(X) of polynomial degree at most q-1.

Chen and Huang (2026) report that, for odd q>19683 and 2<=k<=q-2, the deep holes are exactly the words with degu=k. For even q>19683 and 3<=k<=q-2, the same description holds except that k=q-3 has the additional family u(X)=lambdaX^(q-2)+f(X), where lambda!=0 and degf<q-3. Thus an arbitrary degree-(q-2) polynomial is not included in this extra family.

For even q>=4 with k=2, Chen and Huang (2026) instead parametrize the deep holes as u(X)=ah(X)+bX+c, with a in F_q^*, b,c in F_q, and h a normalized o-polynomial of polynomial degree at most q-1. This parametrization does not classify all hyperovals explicitly.

Fang (2026) reports that for every prime power q and 3<=k<=|_q/2_|, a word is a deep hole iff degu=k, where |_x_| is the floor function. Together with the previously known high-dimensional cases, this removes the restriction q>19683 for the nonexceptional cases 3<=k<=q-2. The exceptional even-characteristic case k=q-3 and the separate k=2 description above remain.

Fan (2026) also reports an exact classification when degu=k+m, m=3, 4, ..., 7, and 2<=k<=q-m-1. There are no deep holes in these ranges for odd m. The only exceptions for even m have k=2 and q=2^e: for m=4 they are u(X)=A(X+b)^6+BX+C with odd e, and for m=6 they are u(X)=AX^8+BX+C with gcd(3,e)=1. Here the coefficients belong to F_q and A!=0. Fang (2026) reports ChatGPT assistance with checking some main proofs. Fan (2026) reports ChatGPT assistance with exploratory proof development and computational checks. These reported classifications await further independent verification.


See also

Code Covering Radius, Reed-Solomon Code

Explore with Wolfram|Alpha

References

Chen, B. and Huang, J. "Deep Holes of Full-Length Reed-Solomon Codes." 21 Oct 2026. https://arxiv.org/abs/2610.29429.Fan, X. "Deep Holes of Full-Length Reed-Solomon Codes: Uniform Bounds and Exact Classifications." 22 Oct 2026. https://arxiv.org/abs/2610.31460.Fang, W. "The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes." 22 Oct 2026. https://arxiv.org/abs/2610.31531.

Cite this as:

Weisstein, Eric W. "Deep Hole." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DeepHole.html

Subject classifications