EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

arXiv:1711.02292v1 [] 7 Nov 2017

JUN ZHANG AND DAQING WAN
Abstract. In this paper, deep holes of Reed-Solomon (RS) codes
are studied. A new class of deep holes for generalized affine RS
codes is given if the evaluation set satisfies certain combinatorial
structure. Three classes of deep holes for projective Reed-Solomon
(PRS) codes are constructed explicitly. In particular, deep holes of
PRS codes with redundancy three are completely obtained when
the characteristic of the finite field is odd. Most (asymptotically
of ratio 1) of the deep holes of PRS codes with redundancy four
are also obtained.

1. Introduction
Let Fnq be the n-dimensional vector space over the finite field Fq of
q elements with characteristic p. For any vector (also, called word )
x = (x1 , x2 , · · · , xn ) ∈ Fnq , the Hamming weight Wt(x) of x is defined
to be the number of non-zero coordinates, i.e.,
Wt(x) = | {i | 1 6 i 6 n, xi 6= 0} |.
For integers 0 ≤ k ≤ n, a linear [n, k] code C is a k-dimensional linear
subspace of Fnq . The minimum distance d(C) of C is the minimum
Hamming weight among all non-zero vectors in C, i.e.,
d(C) = min{Wt(c) | c ∈ C \ {0}}.

A linear [n, k] code C ⊆ Fnq is called an [n, k, d] linear code if C has
minimum distance d. A well-known trade-off between the parameters
of a linear [n, k, d] code is the Singleton bound which states that
d 6 n − k + 1.
Key words and phrases. Reed-Solomon codes, covering radius, deep holes.
The research of Jun Zhang was supported by the National Natural Science Foundation of China under Grant No. 11601350, by Scientific Research Project of Beijing
Municipal Education Commission under Grant No. KM201710028001, and by Beijing outstanding talent training program under Grant No. 2014000020124G140.
Jun Zhang is supported by Chinese Scholarship Council for his visit at the University of Oklahoma, USA. The research of Daqing Wan was supported by National
Science Foundation.
1

2

JUN ZHANG AND DAQING WAN

An [n, k, d] code is called a maximum distance separable (MDS) code
if d = n − k + 1. An important class of MDS codes are affine ReedSolomon codes and projective Reed-Solomon codes, which will be our
main object of study in this paper.
Let C be an [n, k, d] linear code over Fq . The error distance of any
word u ∈ Fnq to C is defined to be
where

d(u, C) = min{d(u, v) | v ∈ C},

d(u, v) = |{i | ui 6= vi , 1 ≤ i ≤ n}|
is the Hamming distance between words u and v. The error distance
plays an important role in the decoding of the code. The maximum
error distance
ρ(C) = max{d(u, C) | u ∈ Fnq }
is called the covering radius of C.
Covering radius of codes was studied extensively [4, 5, 11, 13, 20, 21].
For MDS codes, the covering radius is known to be either d − 1 or
d − 2 [10]. For a general MDS code, determining the exact covering
radius is difficult. We shall see below that affine Reed-Solomon codes
have covering radius d−1. In contrast, the covering radius of projective
Reed-Solomon codes is unknown in general but is conjectured to be d−2
(except when q is even and k = 2, q − 2 in which case the covering
radius is d − 1). We now recall the definition of affine and projective
Reed-Solomon codes.
Definition 1.1. Fix a subset D = {x1 , . . . , xn } ⊆ Fq , which is called
the evaluation set. Let v1 , v2 , · · · , vn ∈ F∗q . For any integer 0 < k < n,
the generalized (affine) RS code C = RS(D, k) of length n, dimension
k and scale vector v = (v1 , v2 , · · · , vn ) over Fq is defined to be

RSv (D, k) = {(v1 f (x1 ), . . . , vn f (xn )) ∈ Fnq | f (x) ∈ Fq [x], deg f (x) ≤ k − 1}.
It is easy to check that the minimal distance of this code is n − k + 1,
and thus RSv (D, k) is an MDS code. For the case v = (1, 1, · · · , 1), we
write RS(D, k) for short. For any v ∈ (F∗q )n , the RS code RSv (D, k) is
equivalent to RS(D, k). Thus, we only consider RS(D, k) throughout
this paper. When D = Fq , we write RS(q, k) for short.
For any word u ∈ Fnq , by the Lagrange interpolation, there is a unique
polynomial f of degree ≤ n − 1 such that
u = uf = (f (x1 ), f (x2 ), · · · , f (xn )).

Clearly, uf ∈ RS(D, k) if and only if deg(f ) ≤ k − 1. We also say that
uf is defined by the polynomial f (x). One can easily show (see [16]):

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

3

for any k 6 deg(f ) 6 n − 1, we have the inequality
n − deg(f ) 6 d(uf , RS(D, k)) 6 n − k.
It follows that if deg(f ) = k, then d(uf , RS(D, k)) = n − k. One
deduces the covering radius of all affine RS codes.
Proposition 1.2. The covering radius of all affine RS codes with parameters [n, k, d = n − k + 1] is n − k = d − 1.
If the distance from a word to the code achieves the covering radius
of the code, then the word is called a deep hole of the code. Deciding
deep holes of a given code is much harder than the covering radius
problem, even for affine RS codes. The deep hole problem for affine RS
codes was studied in [1, 2, 15, 16, 18, 19, 17, 24, 25]. As noted above,
words uf with deg(f ) = k are deep holes of affine RS(D, k). Based on
numerical computations, Cheng and Murray [2] conjectured that the
converse is also true if D = Fq .
Conjecture 1.3 ([2]). For 2 ≤ k ≤ q − 2 (and k 6= q − 3 if q is even),
a word uf is a deep hole of RS(q, k) if and only if deg(f ) = k.
This conjecture remains open, but has been proved if either k +1 ≤ p
by [28] or k ≥ (q − 1)/2 by [14]. In particular, the conjecture is true
for prime fields.
In an opposite direction, Wu and Hong [24] found a new class of deep
holes for RS(F∗q , k) working on cyclic codes via Fourier transformation.
Note that here the evaluation set F∗q is a proper subset of Fq . Then
Zhang, Fu and Liao [25] realized the essence of the new deep holes and
generalized it to all affine RS codes RS(D, k) for any proper subset
D ⊂ Fq .
Proposition 1.4 ([25]). For any proper subset D ⊂ Fq , the polynomials
{a(x − δ)q−2 + f≤k−1 (x) | a 6= 0, δ ∈ Fq \ D}

define deep holes of RS code RS(D, k), where f≤k−1(x) runs all polynomials of degree ≤ k − 1.
The essence of this class of deep holes is the equality
1
on D.
x−δ
It makes the exponent set of the defining Laurent monomials of the
new code
C = RS(D, k) ⊕ Fq · u(x−δ)q−2
(x − δ)q−2 =

4

JUN ZHANG AND DAQING WAN

to form consecutive integers {−1, 0, 1, · · · , k − 1}. So the new code C
is indeed a generalized RS code with the scale vector
1
1
1
v=(
,
,··· ,
),
x1 − δ x2 − δ
xn − δ

which is MDS. And hence, the vectors defined by (x − δ)q−2 is a deep
hole of RS(D, k). Note that the deep holes defined by polynomials of
degree k have the same essence, i.e., the exponent set {0, 1, · · · , k} is
consecutive. For exponents consisting of consecutive integers, the full
rank submatrices are Vandermonde matrices whose determinant are
easy to compute. However, there is no uniform formula of determinant
for general exponent sets. This is one reason why it is difficult to find
other new deep holes.
For a general evaluation set D, Zhuang, Cheng and Li in [28] proved
that for prime q > 2 and k ≥ ⌊ q−1
⌋, the polynomials in the above
2
proposition together with polynomials of degree k define all the deep
holes of RS code RS(D, k). And it is very recently proved by Kaipa
[14] that the same statement is true for all odd prime power q under
⌋. Note that these results are true for all
the same assumption k ≥ ⌊ q−1
2
⌋ and q
subsets D of Fq under the assumption that |D| = n > k ≥ ⌊ q−1
2
odd. One might conjecture it holds for all odd prime power q and for
D with |D| > k > 2. In Section 2, we will show that this conjecture is
⌋.
false for k < ⌊ q−1
2
The aim of this paper is to construct new deep holes of projective
Reed-Solomon codes. This turns out to be significantly more difficult.
Definition 1.5. The projective Reed-Solomon (PRS) code is defined
to be
P RS(q + 1, k) = {(f (α1), · · · , f (αq ), ck−1(f )) | f (x) ∈ Fq , deg(f (x)) < k}
where Fq = {α1 , α2 , · · · , αq = 0} and ck−1 (f ) is the coefficient of the
term of degree k − 1 of f (x).
In the literature, it is also called doubly extended RS code. As above,
we introduce more notations. As the first q coordinates of P RS(q+1, k)
corresponds to an affine part of the projective line, we represent a vector
in Fq+1
by (uf , v) where uf ∈ Fqq is defined by a polynomial f of degree
q
≤ q − 1:
uf = (f (α1 ), · · · , f (αq ))
and v ∈ Fq is arbitrary. It is easy to see that (uf , v) ∈ Fq+1
represents
q
a codeword of P RS(q + 1, k) if and only if
deg(f ) ≤ k − 1 and v = ck−1 (f ).

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

5

It turns out affine RS codes are affine parts of the PRS code. Although they look very similar, the PRS code is much more difficult.
For instance, the covering radius of the PRS code is already unknown.
A consequence [8] of the MDS conjecture implies the following covering
radius conjecture for projective Reed-Solomon codes.
Conjecture 1.6. For 2 ≤ k ≤ q − 2, the covering radius of P RS(q +
1, k) is q − k except when q is even, k = 2, q − 2 in which case the
covering radius is q − k + 1.

It is shown in [26][14] that the deep hole Conjecture 1.3 also implies
the above covering radius conjecture. Since the deep hole conjecture is
known to be true if k + 1 ≤ p by [28] or q is an odd prime power and
k ≥ (q − 1)/2 by [14], we deduce that the covering radius conjecture is
true if k + 1 ≤ p or if q is an odd prime power and k ≥ (q − 1)/2. There
are many other cases that the covering radius conjecture is known to
be true, see [14], including the two simplest non-trivial cases k = q − 2
and k = q − 3 which will be used later in this paper. The next major
problem is the deep hole problem for P RS(q + 1, k).

Problem 1.7. Let 2 ≤ k ≤ q − 2. Assume that the covering radius
conjecture is true. Construct all deep holes of P RS(q + 1, k).
This problem is very difficult and wide open. As shown in [14], classifying deep holes of P RS(q + 1, 2) for q even is equivalent to the difficult
problem of classifying hyperovals of P G(2, q). In [26], we obtained a
class of deep holes of P RS(q + 1, k) which are defined by polynomials
of degree k, if ρ(P RS(q + 1, k)) = q − k.

Theorem 1.8 (Deep holes of degree k [26]). Let q be a prime power
and let k be an integer such that 2 ≤ k ≤ q−2 if 2 ∤ q or 3 ≤ k ≤ q−3 if
2 | q. Suppose ρ(P RS(q + 1, k)) = q − k. The words {(uf , v) | deg(f ) =
k, v ∈ Fq } are deep holes of P RS(q + 1, k).
The reason why it is difficult to find deep holes of a given linear
code is that it is generally NP-hard to compute the error distance of a
given word. In this paper, we give a simple but very effective method,
embedding the code P RS(q + 1, k) to MDS supercodes, to control the
error distance so that two new classes of deep holes of P RS(q + 1, k)
are constructed explicitly.

Theorem 1.9 (Construction from irreducible quadratic polynomials).
Let q be a prime power and let k be an integer such that 2 ≤ k ≤ q −2 if
2 ∤ q or 3 ≤ k ≤ q − 3 if 2 | q. Let C = P RS(q + 1, k). Suppose ρ(C) =
q − k. Let p(x) = x2 + αx + β ∈ Fq [x] be a monic irreducible quadratic
polynomial. For any a, b ∈ Fq which are not zero simultaneously, the

6

JUN ZHANG AND DAQING WAN

rational function a+bx
defines the following coset of deep holes of the
p(x)
PRS code P RS(q + 1, k):


a + bα1 a + bα2
a + bαq
,
,··· ,
, 0 + C.
p(α1 )
p(α2 )
p(αq )
Theorem 1.10 (Construction from irreducible cubic polynomials). Let
q be a prime power. Let C = P RS(q + 1, q − 3). Let p(x) ∈ Fq [x] be a
monic irreducible cubic polynomial. Besides the deep holes in the above
theorems, there are new cosets of deep holes of C of the form


a + bαq + cαq2
a + bα1 + cα12 a + bα2 + cα22
,
,··· ,
,0 + C
p(α1 )
p(α2 )
p(αq )
for some non-zero polynomial a + bx + cx2 ∈ Fq [x].
In particular, for the case q is odd and k = q − 2 the covering radius
of the code P RS(q+1, q−2) is known to be q−k = 2. Kaipa [14] gave a
classification of the deep holes of P RS(q + 1, q −2) using the P GL(2, q)
group action on the projective space P G(2, q) of the syndromes. Under
the group action, the syndrome space P G(2, q) is divided into 3 orbits:
one is the orbit of syndromes of non-deep-holes, the other two are orbits
of syndromes of deep holes. But he did not give the explicit deep holes.
In this paper, we will show that if p(x) runs over all the monic irreducible quadratic polynomials, the explicit deep holes in Theorem 1.9
form all the deep holes of P RS(q + 1, q − 2). The difficulty here is to
distinguish the deep holes for different irreducible quadratic polynomials. To overcome the difficulty, we construct a hypergraph related to
the distribution of irreducible quadratic polynomials and investigate
the properties of the hypergraph in detail.
Theorem 1.11. Let q be an odd prime power. When p(x) runs over
all the monic irreducible polynomials of degree 2 over Fq , the deep holes
in Theorem 1.9 are all the deep holes of P RS(q + 1, q − 2).
The rest of this paper is organized as follows. In Section 2, we give
a new class of deep holes of affine RS code RS(D, k) besides the deep
holes defined by polynomials of degree k and the deep holes in Proposition 1.4. In Section 3, we prove Theorem 1.9. We also investigate the
relationship between the deep holes in Theorem 1.8 and the deep holes
in Theorem 1.9. In Section 4, we prove Theorem 1.11. In Section 5,
we prove Theorem 1.10 and show that the deep holes in Theorems 1.8
and 1.9 (k = q − 3) are contained in the deep holes in Theorem 1.10
where the L-function theory of exponential sums is applied.

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

7

2. New Deep Holes of Generalized RS Codes
In this section, we show that if the evaluation set of the generalized RS Code is zero-sum-free (a combinatorial structure, see Definition 2.7), then new deep holes of the RS code are obtained.
We first review some results about deep holes of RS codes RS(D, k).
Recall that all deep holes of RS(q, k) were conjectured to be defined by
polynomials of degree k (Conjecture 1.3). The same conjecture is false
for general evaluation set D, see [24, 25]. To support Conjecture 1.3,
the easiest case is to determine whether a polynomial of degree k + 1
defines a deep hole of RS(q, k). Li and Wan [16] interpreted it as a
subset sum problem (SSP).
Definition 2.1. Let G be a finite abelian group and D a subset of G.
The k-SSP over D consists in determining
P for any g ∈ G, if there is
a subset S ⊂ D such that |S| = k and s∈S s = g. And denote the
number of solutions by
)
(
X
s=g .
N(k, g, D) = S ⊂ D |S| = k,
s∈S

Lemma 2.2 ([16]). For any polynomial f≤k−1(x) of degree ≤ k − 1,
the polynomial xk+1 − axk + f≤k−1(x) does not define a deep hole of the
RS code RS(D, k) if and only if N(k + 1, a, D) > 0.

For general D, solving k-SSP is an NP-hard problem. But for the
case D = G = Fq , the k-SSP is easy.
Proposition 2.3 ([16]). If D = G = Fq , then for any g ∈ Fq and for
any 1 ≤ k ≤ q − 1 if 2 ∤ q or for any 3 ≤ k ≤ q − 3 if 2 | q, the k-SSP
over D always has solutions.
The above proposition is applied to decide deep holes of RS(q, k).
Proposition 2.4 ([16]). For any 2 ≤ k ≤ q − 4, the vectors defined by
polynomials of degree k + 1 are not deep holes of RS(q, k).
For degree k + 2 and odd q, a complete classification of deep holes
for RS(q, k) is obtained by Zhang, Fu and Liao [25], and detailed error
distances are computed by Li and Zhu [18].
Proposition 2.5 ([25, 18]). For any 2 ≤ k ≤ q − 3, the vectors defined
by polynomials of degree k + 2 are not deep holes of RS(q, k).
For general degrees, the authors in [2] got the first result by reducing
the conjecture to the existence of rational points on a hypersurface over
Fq . Following a similar approach of Cheng-Wan [3], Li and Wan [17]

8

JUN ZHANG AND DAQING WAN

improved the result in [2] with Weil’s character sum estimate. Later,
Cafure et.al. [1] improved the result in [17] a little bit by using tools of
algebraic geometry. Liao [19] gave a tighter estimation of error distance,
which was improved by Zhu and Wan [27].
A major progress in proving Conjecture 1.3 is the recent result:
Proposition 2.6 ([28][14]). If k + 1 ≤ p or k ≥ (q − 1)/2, Conjecture 1.3 is true. In particular, the conjecture is true if q is a prime.
With the preparation above, we now give our new deep holes for
some generalized RS codes, which can be viewed as a generalization of
the new deep holes found for even characteristic case in [25]. We define
Definition 2.7. We call a subset D ⊂ Fq an r-zero-sum-free set in the
finite field Fq if for any r-subset S of D,
X
s 6= 0.
s∈S

Zero-sum-free sets are extensively studied in combinatorics and number theory (see [9, 22]).
Example 2.8. Let p be a prime number and r be an integer such that
1 < r < p. Then the set
n
o
p
0, 1, 2, · · · , ⌊ ⌋ + r − 1
r
is an r-zero-sum-free set in the prime field Fp .
Example 2.9. Let q be an odd prime power and let the evaluation set
D ⊂ Fq be such that
s ∈ D, s 6= 0 ⇒ −s ∈
/ D.

That is, D ∩ {−D} ⊆ {0}. Then D is a 2-zero-sum-free set.
Example 2.10. Let q be a power of 2 and let the evaluation set D ⊂ Fq
be arbitrary. Then D is a 2-zero-sum-free set.
Using the relationship between subset sum problem and deep holes
defined by polynomials of degree k + 1, we obtain the following new
deep holes for generalized RS codes.
Theorem 2.11. Suppose the evaluation set D ⊂ Fq is r-zero-sum-free
(r ≥ 2). Let k = |D| − r − 1.P
For any polynomial f≤k−1 (x) of degree
k+1
≤ k−1, the polynomial x −( s∈D s)xk +f≤k−1 (x) defines a new class
of deep holes of RS(D, k) besides deep holes defined by polynomials of
degree k and polynomials in Proposition 1.4.

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

9

P
Proof. First, we show that the word xk+1 − ( s∈D s)xk + f≤k−1 (x)
really
a deep hole of RS(D, k). By lemma 2.2, the word xk+1 −
P defines
k
( s∈D s)x + f≤k−1 (x) does not define a deep holeP
of RS(D, k) if and
only if there is a k + 1-subset of D whose sum is s∈D s. The latter
is equivalent to that the r leftover elements in DPhave sum 0 which is
impossible by the assumption on D. So xk+1 − ( s∈D s)xk + f≤k−1 (x)
defines a deep hole of RS(D, k).
Second, we show the deep holes are new.
• (Differ from polynomials of degree k.) If there exist some a ∈ F∗q
and some polynomial g≤k−1 (x) of degree ≤ k − 1 such that
X
s)xk + f≤k−1(x) = axk + g≤k−1 (x)
xk+1 − (
s∈D

on D, then the polynomial of degree k + 1
X
s)xk + f≤k−1 (x) − axk − g≤k−1 (x)
xk+1 − (
s∈D

has at least |D| = k + r + 1 distinct zeros, which implies it must
be 0. This contradicts to non-zero coefficients of the term xk+1 .
• (Differ from polynomials in Proposition 1.4.) If there exist some
a ∈ F∗q , δ ∈
/ D and some polynomial g≤k−1 (x) of degree ≤ k − 1
such that
X
a
xk+1 − (
s)xk + f≤k−1 (x) =
+ g≤k−1(x)
x
−
δ
s∈D
on D. As x − δ is non-zero everywhere on D, we multiply x − δ
on the equality to get
X
(xk+1 − (
s)xk + f≤k−1(x))(x − δ) = a + (x − δ)g≤k−1 (x)
s∈D

on D. So the polynomial of degree k + 2
X
(xk+1 − (
s)xk + f≤k−1 (x))(x − δ) − a − (x − δ)g≤k−1 (x)
s∈D

has at least k + r + 1 distinct zeros, which implies that it must
be 0. By the same reason above, we obtain a contradiction.
So the deep holes are new.


10

JUN ZHANG AND DAQING WAN

3. Covering Radii and Deep Holes for PRS codes
In this section, we study the covering radii and deep holes for PRS
codes. Recall that the PRS code P RS(q + 1, k) has one generator
matrix of the form


1
1
···
1
0
 α1
α2 · · · αq 0 


..
..
.. 
 ..
..
.
 .
.
.
. .

 k−2
k−2
k−2
 α1
α2
· · · αq
0 
α1k−1 α2k−1 · · · αqk−1 1

It is easy to check that the PRS code has minimum distance q + 2 − k
and thus it is also an MDS code.
For the case k = 1, the PRS code P RS(q + 1, 1) is nothing but the
repeating code generated by (1, 1, · · · , 1). In this case, one can easily
show that the covering radius is d − 2 = q − 1 and the deep holes are
permutations of the (q + 1)-element multi-set Fq ∪ {α}, where α ∈ Fq
is arbitrary.
For the case k = q − 1, the proof of Theorem 3.2 in [26] shows that
the covering radius of P RS(q + 1, k) is d − 2 = 1 and the deep holes are
(a, · · · , a, 0, v) + P RS(q + 1, k), where a ∈ F∗q , and v ∈ Fq are arbitrary.
For the case k = q, one can show that the covering radius of P RS(q+
1, k) is d − 1 = 1 and the deep holes are w + P RS(q + 1, k) for all
w ∈ Fq+1
of weight 1.
q
With the boundary cases removed, we can then assume that 2 ≤ k ≤
q − 2.
3.1. Covering radii of PRS codes. Although the covering radius of
RS codes is always d − 1, it seems a little surprising that the covering
radius of PRS codes is unknown in general. The above boundary cases
suggest that the covering radius of P RS(q + 1, k) can have two possibilities q − k, q − k + 1, which is indeed the case. Another example
in [4] is the PRS code C over F5 with generator matrix


1 1 1 1 1 0
 1 2 3 4 0 0 


 1 22 32 42 0 0  .
1 23 33 43 0 1
The code C has minimum distance 3 and covering radius 1. This example suggests P RS(q + 1, k) may have covering radius q − k, two smaller
than the minimum distance q + 2 − k. This leads to Conjecture 1.6.
In [8], Dür proved

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

11
√

q

39
Proposition 3.1 ([8]). If q is an odd prime power and 2 ≤ k < √4 + 16
√
q
or 6 q ln q − 2 ≤ k ≤ q − 2; or if q is a power of 2 and 5 ≤ k < 2 − 11
4
√
or 6 q ln q − 2 ≤ k ≤ q − 3, then the covering radius of P RS(q + 1, k)
is
ρ(P RS(q + 1, k)) = q − k.

In [26] we studied the relationship between the covering radius Conjecture 1.6 for PRS codes and the deep hole Conjecture 1.3.
Theorem 3.2 ([26]). Let q be an odd prime power. Assume that Conjecture 1.3 is true. Then the covering radius of P RS(q + 1, k) is q − k.
Note that the above theorem holds for even q: if Conjecture 1.3 is
true, then the covering radius of P RS(q + 1, k) is q − k for all 3 ≤ k ≤
q − 3. The proof is the same as the proof in [26].
Using recent results on Conjecture 1.3 [14], we can deduce
Corollary 3.3 ([26]). Let q be a power of the prime p. Assume either
3 ≤ k + 1 ≤ p or k ≥ (q − 1)/2 (and k 6= q − 2 if p = 2). Then the
covering radius of P RS(q + 1, k) is q − k.
It is natural to ask if the converse holds. We only have partial result.
Theorem 3.4. Let q be a prime power and let k be an integer such
that 2 ≤ k ≤ q − 2 if 2 ∤ q or 3 ≤ k ≤ q − 3 if 2 | q. If Conjecture 1.6
holds, deep holes of RS(q, k) are not deep hole of RS(q, k − 1).
Proof. Consider the word (uf , v), where uf is a deep hole of RS(q, k)
and v ∈ Fq is arbitrary. By the assumption ρ(P RS(q + 1, k)) = q − k,
we get
d((uf , v), P RS(q + 1, k)) ≤ q − k.
That is, there is a codeword (uh , ck−1 (h)) ∈ P RS(q + 1, k) such that
d((uf , v), (uh, ck−1 (h))) ≤ q − k.

On the other hand, we have

d((uf , v), (uh, ck−1 (h))) = d(uf , uh ) + d(v, ck−1(h))
≥ q − k + d(v, ck−1(h)),

since d(uf , RS(q, k)) = q − k and uh ∈ RS(q, k). It forces
d(uf , uh ) = q − k,

So
k−1

As h − vx

and

ck−1 (h) = v.

d(uf −vxk−1 , uh−vxk−1 ) = d(uf , uh ) = q − k.
is a polynomial of degree ≤ k − 2, it follows
d(uf −vxk−1 , RS(q, k − 1)) ≤ q − k.

12

JUN ZHANG AND DAQING WAN

Because ρ(RS(q, k − 1)) = q − k + 1, uf −vxk−1 is not a deep hole of
RS(q, k − 1). In particular, taking v = 0 we prove the lemma.

3.2. Deep holes of PRS codes. A further question is to find all the
deep holes of the PRS codes. On the opposite side, the following result
shows that a large class of vectors are not deep holes.
Theorem 3.5 ([26]). If deg(f ) ≥ k + 1, denote s = deg(f ) − k + 1.
There are positive constants c1 and c2 such that if

√ s
s < c1 q,
+ 2 log2 (q) < k < c2 q,
2
then for any v ∈ Fq , (uf , v) is not a deep hole of P RS(q + 1, k).
On the positive side, we have the following construction of deep holes
of PRS codes.
Theorem 3.6 (Construction from irreducible quadratic polynomials).
Let q be a prime power and let k be an integer such that 2 ≤ k ≤ q − 2
if 2 ∤ q or 3 ≤ k ≤ q − 3 if 2 | q. Suppose ρ(P RS(q + 1, k)) = q − k.
Let p(x) = x2 + αx + β ∈ Fq [x] be a monic irreducible polynomial over
Fq . For any a, b ∈ Fq which are not zero simultaneously, the rational
defines the following coset of deep holes of the PRS code
function a+bx
p(x)
P RS(q + 1, k):


a + bα1 a + bα2
a + bαq
,
,··· ,
, 0 + C.
p(α1 )
p(α2 )
p(αq )
Proof. We will define a new MDS code C ′ with parameters [q + 1, k + 2]
which contains C = P RS(q + 1, k) as a subcode. So all the words in
C ′ \ C are deep holes of C.
The code C ′ is generated by the generator matrix
 1

1
· · · p(α1 q ) 0
p(α1 )
p(α2 )
αq
 α1

α
 p(α1 ) p(α22 ) · · · p(αq ) 0 
 .
..
..
.. 
..
 ..
.
.
.
. 

.
 αk1

αkq
αk2
 p(α ) p(α ) · · · p(α ) 0 
q
1
2
 k+1

αk+1
α1
αk+1
q
2
·
·
·
1
p(α1 )
p(α2 )
p(αq )

From the definition, it is easy to see that C ′ is equivalent to the PRS
code [q + 1, k + 2] code with the scale vector


1
1
1
,
,··· ,
,1 .
p(α1 ) p(α2 )
p(αq )

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

So C ′ is an MDS code with parameters [q + 1, k + 2].
The PRS code C = P RS(q + 1, k) is a subcode of the
as


1
1
···
1
0

β α 1 0 ···
 α1

α
·
·
·
α
0
2
q

  0 β α 1 ···
 ..
..
..
..  
..
.
 .
.
.
.  =  .. .. .. .. . .
 k−2

.
. . . .
k−2
k−2
 α1
α2
· · · αq
0 
0
0
0
0
·
·
·
α1k−1 α2k−1 · · · αqk−1 1
 1
1
···
p(α1 )
p(α2 )
 α1
α2
 p(α1 ) p(α2 ) · · ·
 .
..
..

.
.
×  ..
k
 αk1
α2
 p(α ) p(α
···
1
2)
 k+1
k+1
α2
α1
···
p(α1 )
p(α2 )
For any non-zero vector c′ ∈ C ′ \ C, we have

13

new code C ′ ,

0 0 0
0 0 0 
.. .. .. 
. . . 
β α 1
1
p(αq )
αq
p(αq )

..
.

αkq
p(αq )
αk+1
q
p(αq )

0
0
..
.







.

0 

1

q − k = d(C ′ ) ≤ d(c′ , C) ≤ ρ(C) = q − k,

so
d(c′ , C) = ρ(C) = q − k.

Note that any non-zero vector c′ ∈ C ′ \ C has the form


a + bα1 a + bα2
a + bαq
′
c =
,
,··· ,
,0 + c
p(α1 )
p(α2 )
p(αq )

for some a, b ∈ Fq which are not zero simultaneously and some c ∈ C.
So for any a, b ∈ Fq which are not zero simultaneously, the vectors


a + bα1 a + bα2
a + bαq
,
,··· ,
,0 + C
p(α1 )
p(α2 )
p(αq )
are deep holes of the PRS code P RS(q + 1, k).



We study the relationship between deep holes constructed from monic
irreducible polynomials of degree 2 in the above theorem and the deep
holes defined by polynomials of degree k in Theorem 1.8.
Theorem 3.7. Let q be a prime power and let k be an integer such
that 2 ≤ k ≤ q − 2 if 2 ∤ q or 3 ≤ k ≤ q − 3 if 2 | q. Suppose
ρ(P RS(q+1, k)) = q−k. If k ≤ q−3, the deep holes {(uf , v) | deg(f ) =
k, v ∈ Fq } are different from the deep holes in Theorem 3.6. If q is
odd and k = q − 2, the deep holes {(uf , v) | deg(f ) = k, v ∈ Fq } are
contained in the deep holes in Theorem 3.6.

14

JUN ZHANG AND DAQING WAN

Proof. Wlog, we may assume f (x) = xk −wxk−1 , as (uxi , 0) ∈ P RS(q +
1, k) for all 0 ≤ i ≤ k − 2 and any non-zero scale multiple of a deep
hole is still a deep hole. Let
Then we have

g(x) = f (x) − vxk−1 = xk − (w + v)xk−1 .

d((ug , 0), P RS(q + 1, k)) = d((uf , v), P RS(q + 1, k)).
For the case k ≤ q − 3, suppose there are some monic irreducible
polynomial p(x) ∈ Fq [x] of degree 2, some non-zero polynomial a+bx ∈
Fq [x] and some polynomial h(x) ∈ Fq [x] of degree ≤ k − 2 such that
g(x) =

a + bx
+ h(x)
p(x)

∀x ∈ Fq .

Then the polynomial of degree k + 2 ≤ q − 1

(g(x) − h(x))p(x) − (a + bx)

has q different zeros (as it is zero on Fq ), which is impossible. So in this
case, the deep holes {(uf , v) | deg(f ) = k, v ∈ Fq } are different from
the deep holes in Theorem 3.6.
For the case k = q − 2, let p(x) = x2 + αx + β ∈ Fq [x] be any monic
irreducible polynomial over Fq . Let
a + bx ≡ −(xq − x)

mod p(x).

Since xq − x is coprime to p(x), the polynomial a + bx is non-zero.
There exists some polynomial h(x) ∈ Fq [x] of degree ≤ k − 2 such that
(xk − αxk−1 − h(x))p(x) = a + bx + xq − x.

Hence by choosing a monic irreducible polynomial1

p(x) = x2 + (w + v)x + β ∈ Fq [x],

there is some polynomial h(x) ∈ Fq [x] of degree ≤ k − 2 such that
(g(x) − h(x))p(x) = a + bx + xq − x,

1If

q is odd (or q is even and w + v = 0), one can always use the discriminant to
determine if p(x) is irreducible. That is, if (w + v)2 − 4β is a non-square in Fq , then
p(x) is irreducible over Fq . So in this case, there are q−1
2 many of β ∈ Fq making
(w + v)2 − 4β a non-square for given w + v. However the discriminant method is
invalid for even q and w + v 6= 0. We show the existence of β by contradiction.
Suppose for all β ∈ Fq , the quadratic polynomial p(x) = x2 + (w + v)x + β is
reducible over Fq . So p(x) has two roots in Fq , saying γ1 , γ2 . Then γ1 6= γ2 , as
γ1 + γ2 = w + v 6= 0. On the other hand, for any γ ∈ Fq there is at most one β ∈ Fq
such that p(γ) = 0. So when β runs over Fq there are totally 2q pairwise distinct
roots in Fq which is impossible.

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

15

which is also equivalent to
g(x) =

a + bx
+ h(x)
p(x)

∀x ∈ Fq .

So in this case, the deep holes {(uf , v) | deg(f ) = k, v ∈ Fq } are contained in the deep holes in Theorem 3.6.

The following lemma shows that deep holes in Theorem 3.6 are disjoint for different monic irreducible polynomials of degree 2 in the case
≤ q − 3. And the case k = q − 2 will be studied in detail in Section 4.
Lemma 3.8. Suppose 2 ≤ k ≤ q − 3. For any non-zero polynomials a1 + b1 x, a2 + b2 x ∈ Fq [x] and any two different monic irreducible
polynomials p1 (x), p2 (x) ∈ Fq [x] of degree 2, there is no polynomial
f (x) ∈ Fq [x] of degree ≤ k − 2 such that
a1 + b1 x
a2 + b2 x
=
+ f (x)
p1 (x)
p2 (x)

∀x ∈ Fq .

Proof. Suppose there is a polynomial f (x) ∈ Fq [x] of degree ≤ k − 2
such that
a2 + b2 x
a1 + b1 x
=
+ f (x)
∀x ∈ Fq .
p1 (x)
p2 (x)
Denote the polynomial
g(x) = (a1 + b1 x)p2 (x) − (a2 + b2 x)p1 (x) + f (x)p1 (x)p2 (x).
Then we have
deg(g(x)) = deg(f (x)) + 4 ≤ k + 2 ≤ q − 1
and
xq − x | g(x).
So g(x) must be the zero polynomial. It enforces f (x) = 0 and
(a1 + b1 x)p2 (x) = (a2 + b2 x)p1 (x)
which is impossible under our assumption.



3.3. The number of deep holes of PRS codes. A classification
result of Kaipa [14] about deep holes of P RS(q + 1, k), if ρ(P RS(q +
1, k)) = q − k, could allow us to count the number of cosets of deep

16

JUN ZHANG AND DAQING WAN

holes. Consider the syndrome of the received word
follows:

1
1
···
1
 α1
α
·
·
·
α
2
q

..
..
..

..
T
.
Hu = 
.
.
.
 q−k−1 q−k−1
q−k−1
 α1
α2
· · · αq
q−k
q−k
α1
α2
· · · αqq−k

u ∈ Fq+1
defined as
q
0
0
..
.





 T
u .

0 
1

If ρ(P RS(q + 1, k)) = q − k, the coset u + P RS(q + 1, k) is a coset of
deep holes of P RS(q + 1, k) if and only if the syndrome HuT is not in
the span of any q − k − 1 vectors in the normal rational curve
NRC = {(1, x, · · · , xq−k ) | x ∈ Fq } ∪ {(0, · · · , 0, 1)}.

Theorem 3.9 ([14]). Let q be an odd prime power and k = q − 2.
There are (q − 1)q 2 cosets of deep holes of P RS(q + 1, k).
Theorem
 3 3.10. Let
 q be a prime power and k = q − 3. There are
q
q
(q − 1) 2 + q 2 + 2 cosets of deep holes of P RS(q + 1, k).

Proof. Since any 4 vectors in

1
 α1
 2
 α1
α13

the NRC
1
α2
α22
α23

··· 1
· · · αq
· · · αq2
· · · αq3


0
0 

0 
1

are linearly independent over Fq , the union of all the span of 2 vectors
in NRC has cardinality


q+1
(q − 1)2 + (q + 1)(q − 1) + 1.
2
So the number of cosets of deep holes is



 3

q
q
q+1
2
2
4
.
+q +
(q − 1) + (q + 1)(q − 1) + 1 = (q−1)
q −
2
2
2

4. Complete deep holes of P RS(q + 1, q − 2)

In this section, we focus on the case q is odd and k = q − 2. In
this case, the covering radius of P RS(q + 1, q − 2) is deterministic,
saying ρ(P RS(q + 1, q − 2)) = 2. In [14], Kaipa gave a classification of
the syndromes of deep holes of P RS(q + 1, q − 2) using the P GL(2, q)
group action on the projective space P G(2, q), but without explicit
construction of the deep holes. In this section, we will show that deep

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

17

holes in Theorem 3.6 are all the deep holes of P RS(q + 1, q − 2). So
all the deep holes of P RS(q + 1, q − 2) are constructed explicitly.
We first give some facts about the deep holes found in Theorem 3.6.
For any monic irreducible quadratic polynomial p(x) ∈ Fq [x] we denote


a + bx
| a, b ∈ Fq are not zero simultaneously .
DH(p(x)) =
p(x)
As there is one-to-one correspondence between rational functions in
DH(p(x)) and the cosets of deep holes of the form


a + bα1 a + bα2
a + bαq
,
,··· ,
, 0 + C,
p(α1 )
p(α2 )
p(αq )

we also denote by DH(p(x)) the cosets of deep holes of the above form
defined by p(x).
Fact 1. We have
|DH(p(x))| = q 2 − 1,
and
|DH(p1(x)) ∩ DH(p2 (x))| = q − 1
for any two distinct p1 (x), p2 (x).
Proof. It is obvious that
|DH(p(x))| = q 2 − 1.

The same argument in the proof of Lemma 3.8 shows that the only
possibility for
a2 + b2 x
a1 + b1 x
=
+ f (x)
∀x ∈ Fq .
p1 (x)
p2 (x)
is that deg(f (x)) = k − 2 = q − 4 and
for some a ∈ F∗q . So

g(x) = a(xq − x)

p1 (x)p2 (x) | a(xq − x) − (a1 + b1 x)p2 (x) + (a2 + b2 x)p1 (x).

Since p1 (x), and p2 (x) are two distinct monic irreducible polynomial
over Fq , the condition above is equivalent to
(
p1 (x) | a(xq − x) − (a1 + b1 x)p2 (x),
p2 (x) | a(xq − x) + (a2 + b2 x)p1 (x),
which has solution as follows
(
q −x)
a1 + b1 x ≡ a(x
mod p1 (x),
p2 (x)
a(xq −x)
mod p2 (x).
a2 + b2 x ≡ − p1 (x)

18

JUN ZHANG AND DAQING WAN

So when a runs over F∗q , it gives the q − 1 elements of DH(p1(x)) ∩
DH(p2(x)). And hence,
|DH(p1 (x)) ∩ DH(p2(x))| = q − 1.

Fact 2. For any three monic irreducible polynomials p1 (x), p2 (x), p3 (x)
of degree 2, the condition
DH(p1 (x)) ∩ DH(p2(x)) ∩ DH(p3 (x)) 6= ∅

if and only if p1 (x), p2 (x), p3 (x) are linearly dependent, i.e., there is
unique c ∈ Fq \ {0, 1} such that
p1 (x) = cp2 (x) + (1 − c)p3 (x).

Proof. Suppose
a1 + b1 x
∈ DH(p1 (x)) ∩ DH(p2 (x)) ∩ DH(p3 (x)).
p1 (x)
Then there are c1 , c2 ∈ F∗q such that

c1 (xq − x)
p2 (x)

mod p1 (x),

c2 (xq − x)
a1 + b1 x ≡
p3 (x)

mod p1 (x).

a1 + b1 x ≡
and

So

c2 (xq − x)
c1 (xq − x)
≡
p3 (x)
p2 (x)

or

mod p1 (x)

p1 (x) | (c2 p2 (x) − c1 p3 (x))(xq − x).
Since xq − x is coprime to p1 (x), we have
So c1 6= c2 and
Let c =

c2
.
c2 −c1

p1 (x) | c2p2 (x) − c1 p3 (x).

(c2 − c1 )p1 (x) = c2 p2 (x) − c1 p3 (x).

Then

c ∈ Fq \ {0, 1},

and

p1 (x) = cp2 (x) + (1 − c)p3 (x).
If there is another c ∈ Fq \ {0, 1} such that
′

p1 (x) = c′ p2 (x) + (1 − c′ )p3 (x).

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

19

Then
cp2 (x) + (1 − c)p3 (x) = c′ p2 (x) + (1 − c′ )p3 (x)
which is impossible unless c′ = c. So c is unique.
Conversely, if there is c ∈ Fq \ {0, 1} such that
then
Let

p1 (x) = cp2 (x) + (1 − c)p3 (x),

DH(p1(x)) ∩ DH(p2 (x)) ∩ DH(p3(x)) 6= ∅.
a1 + b1 x ≡

xq − x
p2 (x)

mod p1 (x).

Then

a1 + b1 x
∈ DH(p1 (x)) ∩ DH(p2(x))
p1 (x)
By the assumption, we have
xq − x
c xq − x
≡
mod p1 (x).
p2 (x)
c − 1 p3 (x)
So
c xq − x
mod p1 (x),
a1 + b1 x ≡
c − 1 p3 (x)
which implies
a1 + b1 x
∈ DH(p1 (x)) ∩ DH(p3(x))
p1 (x)
Hence,
a1 + b1 x
∈ DH(p1 (x)) ∩ DH(p2 (x)) ∩ DH(p3 (x)).
p1 (x)

Fact 3. For any pairwise distinct monic irreducible quadratic polynomials p1 (x), p2 (x), · · · , pj (x) if
then

|DH(p1(x)) ∩ DH(p2 (x)) ∩ · · · ∩ DH(pj (x))| =
6 ∅,

|DH(p1(x)) ∩ DH(p2 (x)) ∩ · · · ∩ DH(pj (x))| = q − 1.

Based on the above facts, we construct a hypergraph concerning of
the distribution of irreducible quadratic polynomials, which makes the
picture of deep holes more clear. Since DH(p(x)) is closed under any
non-zero scaling, we consider two polynomials
a + bx
a + bx
and
c
, c ∈ F∗q
p(x)
p(x)

20

JUN ZHANG AND DAQING WAN

as the same vertex in the hypergraph G = (V, E). So the vertices V of
the hypergraph are defined to be
[
DH(p(x))/F∗q
p(x)

where p(x) runs through all monic irreducible polynomials of degree 2.
Any edge e ∈ E is defined to be
e = DH(p(x))/F∗q

for some monic irreducible polynomial p(x) of degree 2. By Fact 1,
any edge has q + 1 vertices and any two edges intersects with 1 vertex.
Facts 2 tells that any vertex has degree about q−1
, as there are about
2
half c ∈ Fq making p1 (x) irreducible if given p2 (x) and p3 (x).
Lemma 4.1. Any vertex v in the hypergraph G has degree

q−1
2

or

q+1
.
2

1x
Proof. For any fixed vertex v = ap11+b
∈ DH(p1 (x)) (p1 (x) = x2 +α1 x+
(x)
β1 ), we need to count the number of monic irreducible polynomials
p2 (x) = x2 + α2 x + β2 (p2 (x) 6= p1 (x)) such that

(*)

a1 + b1 x ≡

c(xq − x)
p2 (x)

mod p1 (x)

for some c ∈ F∗q .
Because a1 +b1 x is coprime to p1 (x), let f (x) be the inverse of a1 +b1 x
modulo p1 (x), i.e.,
(a1 + b1 x)f (x) ≡ 1

mod p1 (x).

Since f (x) and p2 (x) are coprime to p1 (x), we multiply f (x)p2 (x) on
both sides of the equation (*) and obtain
Denote

p2 (x) ≡ c(xq − x)f (x)

mod p1 (x).

e1 x + e2 ≡ c(xq − x)f (x) mod p1 (x).
Then e1 , e2 are non-zero simultaneously. The condition (*) is equivalent
to
p2 (x) ≡ c(e1 x + e2 ) mod p1 (x).
So the existence of p2 (x) and c ∈ F∗q is equivalent to that the discriminant
∆ = (α1 + e1 c)2 − 4(β1 + e2 c)

= e21 c2 + (2α1 e1 − 4e2 )c + (α12 − 4β1 )

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

21

is a non-square for some c ∈ F∗q . Hence the degree of the vertex v is
deg(v) = |{c ∈ F∗q | ∆ is a non-square}| + 1.
Since c = 0 makes ∆ a non-square, we have
deg(v) = |{c ∈ Fq | ∆ is a non-square}|.
• If e1 = 0, then e2 6= 0 and there are q−1
many of c ∈ Fq such
2
that ∆ is a non-square. So in this case,
q−1
2
• If e1 =
6 0, then the discriminant
deg(v) =

∆ = e21 c + (2α1 e1 − 4e2 )c + (α12 − 4β1 )

2
2

α1 e1 − 2e2
α1 e1 − 2e2
2
= e1 c +
+ (α1 − 4β1 ) −
e1
e1
Denote
δ=

(α12

− 4β1 ) −



α1 e1 − 2e2
e1

2

.

Then after a linear transformation of Fq ,
deg(v) = |{c ∈ Fq | c2 − δ is a non-square in Fq }|.
Since α12 − 4β1 is a non-square, the constant term is non-zero,
i.e.,
δ 6= 0.

Next, we count the number of c ∈ Fq that makes c2 −δ a square.
Suppose
c2 − δ = y 2

for some y ∈ Fq . Then

δ = (c − y)(c + y).
It is easy to see that the above equation has solutions
c=

δ/l − l
δ/l + l
,y =
, ∀l ∈ F∗q .
2
2

So
2

|{c ∈ Fq | c − δ is a square in Fq }| =



δ/l + l
| l ∈ F∗q
2



.

22

JUN ZHANG AND DAQING WAN

Hence,
deg(v) = |{c ∈ Fq | c2 − δ is a non-square in Fq }|


δ/l + l
∗
| l ∈ Fq
=q−
2
(
q−1
if δ is a square;
2
= q+1
if δ is a non-square.
2

Lemma 4.2. In any edge of the hypergraph G, half of the vertices have
degree q+1
, and the other half of the vertices have degree q−1
.
2
2
Proof. Let e = DH(p(x))/F∗q be an edge of G. Suppose there are m
vertices in e of degree q−1
and n vertices in e of degree q+1
. There are
2
2
q 2 −q
totally 2 edges in G. By Fact 1 besides the edge e, any of the other
q 2 −q
− 1 edges intersects with e. So
2




q+1
q2 − q
q−1
−1 +n
−1 =
− 1.
m
2
2
2
By Lemma 4.1, we have

m + n = q + 1.
So
m=n=

q+1
.
2


Theorem 4.3. The hypergraph G has |V | = q 2 vertices.
Proof. As a multi-set, the union of all the edges has cardinality
q2 − q
(q + 1).
2
By Lemma 4.2, half of the elements in the multi-set have multiplicity
q+1
, and the other half elements in the multi-set have multiplicity q−1
.
2
2
So the hypergraph has
|{monic irreducible polynomials of degree 2}|(q + 1) =

q 2 −q
(q+1)
2

q 2 −q
(q+1)
2

|V | =
vertices.

2
q+1
2

+

2
q−1
2

= q2


With the preparation above, we now turn to our main result of this
section.

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

23

Theorem 4.4. Let q be an odd prime power. When p(x) runs over all
the monic irreducible polynomials of degree 2 over Fq , the deep holes in
Theorem 3.6 are all the deep holes of P RS(q + 1, q − 2).
Proof. By Theorem 4.3, there are
|V |(q − 1) = q 2 (q − 1)
cosets of deep holes found in Theorem 3.6.
On the other hand, by Theorem 3.9 there are totally q 2 (q − 1) cosets
of deep holes. So the deep holes in Theorem 3.6 are all the deep holes of
P RS(q +1, q −2) if p(x) runs over all the monic irreducible polynomials
of degree 2.

5. Deep holes of P RS(q + 1, q − 3)
In this section, we extend the construction using irreducible quadratic polynomials to irreducible cubic polynomials for the code P RS(q+
1, q − 3). More deep holes of P RS(q + 1, q − 3) are obtained.
In Section 4 it is proved that for odd q and k = q −2 there are totally
q 2 (q − 1) cosets of deep holes constructed in Theorem 3.6 which form
all the deep holes of the PRS code P RS(q + 1, q − 2). But for the code
P RS(q + 1, q − 3), by Lemma 3.8 the total number of cosets of deep
holes in Theorems 3.6 and 1.8 is

 3
q2 − q 2
q
q
.
(q − 1) + q(q − 1) = (q − 1)
+
2
2
2
By Theorem 3.10 the exact number of cosets of deep holes of P RS(q +
1, q − 3) is
 3

q
q
2
(q − 1)
.
+q +
2
2
Hence there are other deep holes!
Theorem 5.1 (Construction from irreducible cubic polynomials). Let
q be a prime power and let k = q − 3. Let C = P RS(q + 1, k). Let
p(x) ∈ Fq [x] be a monic irreducible polynomial of degree 3.
(1) There are totally
q2 + q + 2
2
cosets of deep holes of the form
(q − 1)

(uf , 0) + C

24

JUN ZHANG AND DAQING WAN
2

where f (x) = a+bx+cx
for some non-zero polynomial a + bx +
p(x)
2
cx ∈ Fq [x].
(2) There are new cosets of deep holes of C of the form above besides
the deep holes in Theorem 3.6 and Theorem 1.8.
Proof. We have seen that in this case the covering radius ρ(P RS(q + 1, k)) =
q − k. Similarly to Theorem 3.6, we construct a supercode C ′ using the
irreducible polynomial p(x). Then C ′ is an MDS code with parameters
2
[q + 1, k + 3]. So for any rational function f (x) = a+bx+cx
where a, b, c
p(x)
are not zero simultaneously, we have
q − k − 1 = d(C ′ ) ≤ d((uf , 0), C) ≤ ρ(P RS(q + 1, k)) = q − k.
The error distance d((uf , 0), C) = q − k − 1 if and only if there is
h(x) ∈ Fq [x] of degree k − 2 such that
a + bx + cx2 − h(x)p(x)

splits as k + 1 = q − 2 linear factors, or

a + bx + cx2 − (dxk−1 + h(x))p(x)

splits as k + 2 = q − 1 linear factors for some d ∈ F∗q . Moreover, for
fixed a + bx + cx2 if there is h(x) ∈ Fq [x] of degree k − 2 such that
a + bx + cx2 − h(x)p(x)

splits as k + 1 = q − 2 linear factors, then such h(x) is unique. If not,
suppose there is another h1 (x) ∈ Fq [x] of degree k − 2 such that
a + bx + cx2 − h(x)p(x)

splits as k + 1 = q − 2 linear factors. Let S and T be (q − 2)-subsets
of Fq such that
Y
a + bx + cx2 − h(x)p(x) = d (x − s)
s∈S

and

a + bx + cx2 − h1 (x)p(x) = d1
for some d, d1 ∈

F∗q .

Then

(h(x) − h1 (x))p(x) = d1
Note that

Y
t∈T

(x − t)

Y
Y
(x − t) − d (x − s).
t∈T

|S ∩ T | ≥ q − 4.

s∈S

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

25

So the polynomial (h(x) − h1 (x))p(x) has at least q − 4 linear factors.
Since the polynomial h(x) − h1 (x) has degree
deg(h(x) − h1 (x)) ≤ q − 5,

the polynomial p(x) has at least 1 linear factor, which contradicts to
the irreducibility of p(x). So for a + bx + cx2 if there is h(x) ∈ Fq [x] of
degree k − 2 such that a + bx + cx2 − h(x)p(x) splits as k + 1 = q − 2
linear factors, then the factorization is unique. On the other hand, any
(q − 2)-subset S of Fq contributes q − 1 polynomials a + bx + cx2 in the
following way
Y
a + bx + cx2 ≡ d (x − s) mod p(x)
s∈S

where d ∈

F∗q

is arbitrary. Hence, the number of such a + bx + cx2 is


q
.
(q − 1)
q−2

Similarly, the number of polynomials a + bx + cx2 such that a + bx +
cx2 − h(x)p(x) splits as k + 2 = q − 1 linear factors for some h(x) of
degree k − 1 is


q
.
(q − 1)
q−1
By the same argument again, there is no a + bx + cx2 satisfying the
two splitting conditions at the same time. So the total number of f
satisfying d((uf , 0), C) = q − k − 1 is

 

q
q
.
+
(q − 1)
q−1
q−2


Hence the number of cosets of deep holes of C of the form u a+bx+cx2 , 0 +
p(x)

C is

3

q − 1 − (q − 1)




 
q2 + q + 2
q
q
= (q − 1)
+
.
q−1
q−2
2

This proves the first statement.
Next we show that there are NEW deep holes besides the deep holes
in Theorems 3.6 and 1.8.
FIX p(x) = x3 + αx2 + βx + γ a monic irreducible polynomial. Suppose there are a monic irreducible polynomial q(x) of degree 2 and a
polynomial f (x) ∈ Fq [x] of degree ≤ k − 2 such that
a + bx + cx2
d + ex
=
+ f (x)
p(x)
q(x)

∀x ∈ Fq .

26

JUN ZHANG AND DAQING WAN

Then one can solve to get
a + bx + cx2 ≡

l(xq − x)
q(x)

mod p(x)

and

−l(xq − x)
mod q(x)
p(x)
for some l ∈ F∗q . So running over all monic irreducible polynomial of
degree 2 and l ∈ F∗q , they contribute at most
d + ex ≡

q2 − q
(q − 1)
2
cosets of deep holes of the form in the lemma. So besides the deep
holes in Theorem 3.6, there are at least
q2 + q + 2 q2 − q
−
(q − 1) = (q − 1)(q + 1)
2
2


cosets of deep holes of the form u a+bx+cx2 , 0 + C.
(q − 1)

p(x)

We have already seen that the number2 of cosets of deep holes in
Theorem 1.8
|{(uf , v) + C | deg(f ) = k, v ∈ Fq }| = q(q − 1).
So there are at least
(q − 1)(q + 1) − (q − 1)q = q − 1


cosets of deep holes of the form u a+bx+cx2 , 0 + C besides the deep
p(x)

holes in Theorem 3.6 and Theorem 1.8.


Next we study the relationship between deep holes in Theorem 5.1
and the deep holes in Theorems 3.6 for k = q − 3. This problem is
related to the distribution problem of irreducible polynomials which
has been studied extensively in number theory (see [23] and [6]). However, the lower bound in the references is vacuous in our situation. To
overcome the difficulty, we use the method in [23] to give an explicit
formula for the distribution of irreducible cubic polynomials.
2Indeed,

for fixed p(x) = x3 +αx2 + βx + γ one can show only (uexk −eαxk−1 , 0) +

C, e ∈ F∗q can be represented by
mod p(x).

u a+bx+cx2 , 0 +C where a+bx+cx2 ≡ −e(xq −x)
p(x)

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

27

Lemma 5.2 (Distribution of irreducible cubic polynomials). For any
non-zero polynomial a + bx ∈ Fq [x] and any monic irreducible polynomial q(x) ∈ Fq [x] of degree 2, there exists a monic irreducible polynomial p(x) ∈ Fq [x] of degree 3 such that
for some l ∈ F∗q .

p(x) ≡ l(a + bx)

mod q(x)

Proof. Let G = (Fq [x]/(q(x)))∗ . This is just the multiplicative group
of the quadratic extension of the field Fq . For α ∈ G, let N3 (α) denote
the number of pairs (p(x), l) such that p(x) ∈ Fq [x] is monic irreducible
of degree 3, l ∈ F∗q and p(x) ≡ lα mod q(x). We want to show that
N3 (α) > 0. In fact, we will give a simple explicit formula for N3 (α)
which immediately imply that N3 (α) > 0.
Let Ĝ be the complex character group of G, which is the cyclic group
of order q 2 − 1. Let Ĝ1 denote the subgroup of Ĝ consisting of those
characters whose restriction to F∗q is trivial. It is clear that Ĝ1 is a
cyclic group of order q + 1. Let πk denote the set of monic irreducible
polynomials of degree k in Fq [x]. A standard character sum argument
shows that
1 X X X p(x)
N3 (α) = 2
χ(
).
q −1
lα
∗
l∈F
p(x)∈π
3
q
χ∈Ĝ
P
−1
If χ 6∈ Ĝ1 , then l∈F∗q χ(l ) = 0. It follows that
p(x)
q−1 X X
χ(
)
2
q −1 ˆ
α
p(x)∈π
3
χ∈G1


3
X
X
1 q − q
χ(p(x)) .
+
χ−1 (α)
=
q+1
3
ˆ

N3 (α) =

χ∈G1 \{1}

p(x)∈π3

Now χ is a nontrivial character of G which is trivial on F∗q . For
positive integers k, consider the character sums and their L-function
∞
X
X X
Sk (χ) k
k/d
dχ(p(x) ), L(χ, T ) = exp(
Sk (χ) =
T ).
k
k=1

d|k p(x)∈πd

By [23], the L-function L(χ, T ) of χ is a polynomial of degree 1 with
the trivial factor 1 − T . This can also be proved directly. It follows
that L(χ, T ) = 1 − T and Sk (χ) = −1 for all k. Taking k = 3, we
obtain
X
χ(p(x)) + S1 (χ3 ).
−1 = S3 (χ) = 3
p(x)∈π3

28

JUN ZHANG AND DAQING WAN

If χ3 6= 1, then S1 (χ3 ) = −1 and we deduce
X
χ(p(x)) = 0
p(x)∈π3

If χ3 = 1, then χ = χ3 is a primitive character of order 3 trivial on Fq
(necessarily q ≡ 2 mod 3), then S1 (χ3 ) = q and
X
q+1
.
χ(p(x)) = −
3
p(x)∈π3

Putting the above together, we deduce the following result. If q 6≡ 2
mod 3, then N3 (α) = q(q − 1)/3. If q ≡ 2 mod 3, then
1
N3 (α) = (q(q − 1) − (χ3 (α) + χ−1
3 (α))).
3
In summary, we have
1
N3 (α) = (q(q − 1) − r3 (α)),
3
where r3 (α) = 0 if q 6≡ 2 mod 3, r3 (α) = −1 if q ≡ 2 mod 3 and
χ3 (α) 6= 1, and r3 (α) = 2 if q ≡ 2 mod 3 and χ3 (α) = 1.

Theorem 5.3. Let q be a prime power and let k = q − 3. The deep
holes in Theorem 3.6 are contained in deep holes in Theorem 5.1.
Proof. Let C = P RS(q + 1, k). For any coset of deep holes in Theorem 3.6


u d+ex , 0 + C
q(x)

where q(x) is a monic irreducible quadratic polynomial and d + ex is
non-zero, by Lemma 5.2 there is a monic irreducible polynomial p(x)
of degree 3 such that
l(xq − x)
mod q(x)
p(x) ≡
d + ex
for some l ∈ F∗q . Let

−l(xq − x)
mod p(x).
q(x)
Then one can show that there is a polynomial f (x) ∈ Fq [x] of degree
≤ k − 2 such that
d + ex
a + bx + cx2
=
+ f (x)
∀x ∈ Fq .
p(x)
q(x)
So




a + bx + cx2 ≡

u d+ex , 0 + C =
q(x)

u a+bx+cx2 , 0 + C.
p(x)

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

29


The theorem below shows that the deep holes constructed from
monic irreducible cubic polynomials contain the deep holes of degree
k.
Theorem 5.4. Let q be a prime power and let k = q − 3. The deep
holes in Theorem 1.8 are contained in deep holes in Theorem 5.1.
Proof. Let C = P RS(q + 1, k). For any coset of deep holes (uf , v) + C
in Theorem 1.8, wlog, we may assume f (x) = xk − wxk−1 , as (uxi , 0) ∈
P RS(q + 1, k) for all 0 ≤ i ≤ k − 2 and any non-zero scale multiple of
a deep hole is still a deep hole. Let
Then we have

g(x) = f (x) − vxk−1 = xk − (w + v)xk−1 .

d((ug , 0), P RS(q + 1, k)) = d((uf , v), P RS(q + 1, k)).
By theorems in [23] and [12] (also see [6, Theorem 2.7]), there exists
a monic irreducible polynomial p(x) ∈ Fq [x] with x2 -coefficient w + v.
Since xq − x is coprime to p(x), we have
a + bx + cx2 ≡ −(xq − x)

mod p(x)

is non-zero. So there exists some polynomial h(x) ∈ Fq [x] of degree
≤ k − 2 such that
(g(x) − h(x))p(x) = a + bx + cx2 + xq − x,

which is also equivalent to
a + bx + cx2
+ h(x)
g(x) =
p(x)

∀x ∈ Fq .

So any coset in {(uf , v) + C | deg(f ) = k, v ∈ Fq } can be written as


u a+bx+cx2 , 0 + C
p(x)

for some monic irreducible polynomial p(x) ∈ Fq [x] of degree 3 and
some non-zero polynomial a + bx + cx2 ∈ Fq [x].

Remark 5.5.
(1) It is natural to ask that in the case k = q − 3 if
deep holes constructed from all irreducible polynomials of degree
3 are all the deep holes of P RS(q + 1, q − 3). For small q, using
mathematical software, e.g., SageMath [7], one could count the
number of cosets of deep holes constructed from irreducible
poly 3

q
2
nomials of degree 3 and verify if it equals (q − 1) 2 + q + 2q .

30

JUN ZHANG AND DAQING WAN

The experiment result would suggest that the deep holes constructed from irreducible polynomials of degree 3 are not complete for prime power q ≥ 8.
(2) An open problem is to count the number of cosets of deep holes
constructed in Theorem 5.1 when the construction runs over all
the irreducible polynomials of degree 3 and find all the deep holes
of P RS(q + 1, q − 3).
Acknowledgement
Part of this paper was written when the two authors were visiting Beijing International Center for Mathematical Research (BICMR).
The authors would like to thank Prof. Ruochuan Liu for his hospitality. Part of this paper was written when the first author was visiting
University of Oklahoma. He would like to thank Prof. Qi Cheng for
his hospitality.
References
[1] A. Cafure, G. Matera, and M. Privitelli, “Singularities of symmetric hypersurfaces and an application to Reed-Solomon codes,” Advances in Mathematics
of Communications, vol. 6, no. 1, 2011.
[2] Q. Cheng and E. Murray, “On deciding deep holes of Reed-Solomon codes,”
Lecture Notes in Computer Science, vol. 4484, pp. 296–305, 2007.
[3] Q. Cheng and D. Wan, “On the list and bounded distance decodability of
Reed-Solomon codes,” SIAM Journal on Computing, vol. 37, no. 1, pp. 195–
209, 2007.
[4] G. Cohen, M. Karpovsky, H. Mattson, and J. Schatz, “Covering radius—survey
and recent results,” IEEE Transactions on Information Theory, vol. 31, no. 3,
pp. 328–343, 1985.
[5] G. Cohen, A. C. Lobstein, and N. Sloane, “Further results on the covering
radius of codes,” IEEE Transactions on Information Theory, vol. 32, no. 5,
pp. 680–694, 1986.
[6] S. D. Cohen, “Explicit theorems on generator polynomials,” Finite Fields and Their Applications, vol. 11, no. 3, pp. 337–
357, 2005, ten Year Anniversary Edition!
[Online]. Available:
http://www.sciencedirect.com/science/article/pii/S107157970500033X
[7] T. S. Developers, SageMath, the Sage Mathematics Software System (Version
v8.0), 2017, http://www.sagemath.org.
[8] A. Dür, “On the covering radius of Reed-Solomon codes,” Discrete Mathematics, vol. 126, no. 1-3, pp. 99–105, 1994.
[9] P. Erdös, “Extremal problems in number theory,” Proceedings of the Symp.
Pure Math. VIII AMS, pp. 181–189, 1965.
[10] E. M. Gabidulin and T. Klove, “The Newton radius of MDS codes,” in Information Theory Workshop, 1998, 1998, pp. 50–51.
[11] R. Graham and N. Sloane, “On the covering radius of codes,” IEEE Transactions on Information Theory, vol. 31, no. 3, pp. 385–401, 1985.

EXPLICIT DEEP HOLES OF REED-SOLOMON CODES

31

[12] K. H. Ham and G. L. Mullen, “Distribution of irreducible polynomials of small
degrees overn finite fields,” Mathematics of Computation, vol. 67, no. 221, pp.
337–341, 1998.
[13] T. Helleseth, T. Klove, and J. Mykkeltveit, “On the covering radius of binary
codes (corresp.),” IEEE Transactions on Information Theory, vol. 24, no. 5,
pp. 627–628, 1978.
[14] K. Kaipa, “Deep holes and MDS extensions of Reed-Solomon codes.” IEEE
Transactions on Information Theory, vol. PP, no. 99, pp. 1–1, 2017.
[15] M. Keti and D. Wan, “Deep holes in Reed-Solomon codes based on Dickson
polynomials,” Finite Fields and Their Applications, vol. 40, no. C, pp. 110–125,
Jul. 2016.
[16] J. Li and D. Wan, “On the subset sum problem over finite fields,” Finite Fields
and Their Applications, vol. 14, no. 4, pp. 911–929, 2008.
[17] Y. Li and D. Wan, “On error distance of Reed-Solomon codes,” Science in
China, vol. 51, no. 11, pp. 1982–1988, 2008.
[18] Y. Li and G. Zhu, “On the error distance of extended Reed-Solomon codes.”
Advances in Mathematics of Communications, vol. 10, no. 2, 2016.
[19] Q. Liao, “On Reed-Solomon codes,” Chinese Annals of Mathematics, no. 1,
pp. 89–98, 2011.
[20] A. McLoughlin, “The complexity of computing the covering radius of a code,”
IEEE Transactions on Information Theory, vol. 30, no. 6, pp. 800–804, 1984.
[21] P. R. J. Östergård, “New constructions for q-ary covering codes,” Ars Combinatoria -Waterloo then Winnipeg-, vol. 52, pp. 51–63, 1999.
[22] T. Tao and V. Vu, “Sum-avoiding sets in groups,” arXiv preprint
arXiv:1603.03068, 2016.
[23] D. Wan, “Generators and irreducible polynomials over finite fields,” Mathematics of Computation, vol. 66, no. 219, pp. 1195–1212, 1997.
[24] R. Wu and S. Hong, “On deep holes of standard Reed-Solomon codes,” Science
China Mathematics, vol. 55, no. 12, pp. 2447–2455, 2012.
[25] J. Zhang, F.-W. Fu, and Q. Liao, “New deep holes of generalized
Reed-Solomon codes,” Scientia Sinica, vol. 43, no. 7, pp. 727–740, 2013.
[Online]. Available: http://arxiv.org/abs/1205.6593
[26] J. Zhang and D. Wan, “On deep holes of projective reed-solomon codes,” 2016
IEEE International Symposium on Information Theory (ISIT), pp. 925–929,
2016.
[27] G. Zhu and D. Wan, “Computing error distance of Reed-Solomon codes,”
Lecture Notes in Computer Science, vol. 7287, pp. 214–224, 2012.
[28] J. Zhuang, Q. Cheng, and J. Li, “On determining deep holes of generalized
Reed-Solomon codes,” IEEE Transactions on Information Theory, vol. 62,
no. 1, pp. 199–207, Jan 2016.
Jun Zhang, School of Mathematical Sciences, Capital Normal University, Beijing 100048, P.R. China.
E-mail address: junz@cnu.edu.cn
Daqing Wan is with Department of Mathematics, University of California, Irvine, CA 92697, USA.
E-mail address: dwan@math.uci.edu

