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. 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