Some results on deep holes of generalized projective Reed-Solomon codes

1.   Introduction and the statements of the main results

Let ${\bf F}_q$ be the finite field of $q$ elements with $p$ as its characteristic. Let $n$ and $k$ be positive integers such that $k < n$. Let $D = \{x_1, \cdots, x_n\}$ be a subset of ${\bf F}_q$, which is called the evaluation set. The generalized Reed-Solomon code ${\rm GRS}_q(D, k)$ of length $n$ and dimension $k$ over ${\bf F}_q$ is defined by:

Moreover, the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ of length $n+1$ and dimension $k$ over ${\bf F}_q$ is defined as follows:

where $c_{k-1}(f(x))$ is the coefficient of $x^{k-1}$ of $f(x)$. If $D = {\bf F}_q^*$, then it is called primitive projective Reed-Solomon code, namely,

where $\alpha$ is a primitive element of ${\bf F}_q$. If $D = {\bf F}_q$, then it is called the extended projective Reed Solomon code. For $u = (u_1, \ldots, u_n)\in{\bf F}_q^n$, $v = (v_1, \ldots, v_n) \in{\bf F}_q^n$, the Hamming distance $d(u, v)$ is defined by

For any $[n, k]_q$ linear code $C$, the minimum distance $d(C)$ is defined by

where $d(\cdot, \cdot)$ denotes the Hamming distance of two codewords. A linear $[n, k, d]$ code is called maximum distance separable (MDS) code if $d = n-k+1$. The error distance to code $C$ of a received word $u \in {\bf F}_q^n$ is defined by

Clearly, $d(u, C) = 0$ if and only if $u \in C$. The maximum error distance

is called the covering radius of $C$.

The most important algorithmic problem in coding theory is the maximum likelihood decoding (MLD): Given a received word $u\in{\bf F}_q^n$, find a codeword $v \in C$ such that $d(u, v) = d(u, C)$, then we decode $u$ to $v$ ^[1]. Therefore, it is very crucial to decide $d(u, C)$ for the received word $u$. Guruswami and Sudan ^[2] provided a polynomial time list decoding algorithm for the decoding of $u$ when $d(u, C)\le {n-\sqrt{nk}}$. When the error distance increases, Guruswami and Vardy ^[3] showed that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We also notice that Dür ^[4] studied the Cauchy codes. In particular, Dür ^[4] got the relation between the covering radius and minimum distance of ${\rm GPRS}_q(D, k)$. When decoding the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$, for a received word $u = (u_1, \ldots, u_n, u_{n+1})\in {\bf F}_q^{n+1}$, we define the Lagrange interpolation polynomial $u(x)$ of the first $n$ components of $u$ by

i.e., $u(x)$ is the unique polynomial of degree $\deg u(x) \le n-1$ such that $u(x_i) = u_i$ for $1\leq i\leq n$. It is clear that $u\in {\rm GPRS}_q(D, k)$ if and only if $d(u, {\rm GPRS}_q(D, k)) = 0$ if and only if $\deg u(x)\leq {k-1}$ and $c_{k-1}(u(x)) = u_{n+1}$. Equivalently, $u\not \in {\rm GPRS}_q(D, k)$ if and only if $d(u, {\rm GPRS}_q(D, k))\ge 1$ if and only if $k\le \deg u(x)\le n-1$ or $c_{k-1}(u(x))\neq u_{n+1}$. Evidently, we have the following simple bounds of $d(u, {\rm GRS}_q(D, k))$ which are due to Li and Wan.

Theorem 1.1. ^[5] Let $u$ be a received word such that $u\not\in {\rm GRS}_q(D, k)$. Then

Let $u \in {\bf F}_q^n$. If $d(u, {\rm GRS}_q(D, k)) = \rho({\rm GRS}_q(D, k))$, then the received word $u$ is called a deep hole of ${\rm GRS}_q(D, k)$. From Theorem 1.1, one can easily see that the received word $u$ is a deep hole of ${\rm GRS}_q(D, k)$ if its Lagrange interpolation polynomial is of degree $k$. In 2012, Wu and Hong ^[6] found another class of deep holes for the standard Reed-Solomon code ${\rm GRS}_q({\bf F}_q^*, k)$. In fact, if $q\geq 4$ and $2\leq k\leq q-2$, then they showed that the received word $u$ is a deep hole if its Lagrange interpolation polynomial is of the form $ax^{q-2} +f_{\leq{k-1}}(x)$ with $a\in {\bf F}_q^*$ and $f_{\leq{k-1}}(x)\in{\bf F}_q[x]$ is a polynomial of degree at most $k-1$. In ^[7], Hong and Wu proved that the received word $u$ is a deep hole of the generalized Reed-Solomon code ${\rm GRS}_q(D, k)$ if its Lagrange interpolation polynomial is $\lambda(x-a_i)^{q-2}+f_{\leq{k-1}}(x)$, where $\lambda\in {\bf F}_q^*, a_i\in{\bf F}_q\backslash D$ and $f_{\leq{k-1}}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-1$. In ^[8], Zhuang, Lin and Lv investigated the deep hole trees of generalized Reed-Solomon codes.

In what follows, we let $l$ be a positive integer and $a_1, \ldots, a_l$ be any fixed $l$ distinct elements of ${\bf F}_q$. Let

We write

and for any $f(x)\in {\bf F}_q[x]$, we define

and use $c_{k-1}(f(x))$ to denote the coefficient of $x^{k-1}$ of $f(x)$. Then we can rewrite the generalized projective Reed-Solomon code ${\rm GPRS}(D, k)$ with evaluation set $D$ as

Let $u\notin {\rm GPRS}_q(D, k)$. If $d(u, {\rm GPRS}_q(D, k)) = \rho({\rm GPRS}_q(D, k))$, then $u$ is also called a deep hole of generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$. In 2016, Zhang and Wan ^[9] studied the deep holes of projective Reed-Solomon code ${\rm GPRS}({\bf F}_q, k)$. In fact, under the assumption that the only deep holes of ${\rm GRS}_q({\bf F}_q, k)$ are those received words whose Lagrange interpolation polynomials are of degree $k$, they proved the following results by solving a subset sum problem.

Theorem 1.2. ^[9] Let $q$ be an odd prime power. Assume that $3\leq k+1\leq p$ or $3\leq q-p+1\leq k+1\leq {q-2}$. Then the received word $(f({\bf F}_q), c_{k-1}(f(x)))$ with $\deg f(x) = k$ is a deep hole of ${\rm GPRS}({\bf F}_q, k)$.

Theorem 1.3. ^[9] Let $\deg f(x)\geq k+1$ and $s: = \deg f(x)-k+1$. If there are positive constants $c_1$ and $c_2$ such that $s < c_1\sqrt{q}, (\frac{s}{2}+2)\log_2(q) < k < c_2q$, then $(f({\bf F}_q), c_{k-1}(f(x)))$ is not a deep hole of ${\rm GPRS}({\bf F}_q, k)$.

In this paper, our main goal is to investigate the deep holes of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$. Actually, we will present characterizations for the received words of degrees $k$ and $q-2$ to be deep holes of generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$. The main results of this paper can be stated as follows.

Theorem 1.4. Let $q$ be a prime power and let $k, l$ be positive integers such that $q\geq 5$ and $2\leq k \leq \min(q-3, q-l-1)$. Let $u(x)\in {\bf F}_q[x]$ with $\deg u(x) = k$. Then the received word $(u(D), c_{k-1}(u(x)))$ is a deep hole of the generalized projective Reed-Solomon code ${\rm {\rm GPRS}}_q(D, k)$ if and only if $\sum\limits_{y\in I}y\ne 0$ for any subset $I\subseteq D$ with $\#(I) = k$.

Theorem 1.5. Let $q$ be a prime power and let $k, l$ be positive integers such that $q\geq 4$ and $2\leq k \leq {q-l-1}$. Let $j$ be an integer with $1\leq j\leq l$ and let $u_j(x): = \lambda_j(x-a_j)^{q-2}+\nu_j x^{k-1}+f_{\leq k-2}^{(j)}(x)$ with $\lambda_j\in {\bf F}_q^*$, $\nu_j\in {\bf F}_q$ and $f_{\leq{k-2}}^{(j)}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-2$. Then the received word $(u_j(D), c_{k-1}(u_j(x)))$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if $\binom{q-2}{k-1}a_j^{q-1-k}\prod\limits_{y\in I}(y-a_j)\ne -e$ for any subset $I\subseteq D$ with $\#(I) = k$, where $e$ is the identity of the multiplicative group ${\bf F}_q^*$.

From Theorems 1.4 and 1.5, we can deduce the following results on the deep holes of the primitive projective Reed-Solomon codes. Note that the proof of Corollary 1.6 relies also on a result about the zero subsets sum of the group ${\bf F}_q^*$ (see Lemma 2.8 below).

Corollary 1.6. Let $q$ be an odd prime power such that $q\geq 5$ and $2\leq k \leq {q-3}$. If $u(x) = \lambda x^k+\gamma x^{k-1}+f_{\leq{k-2}}(x)$ with $\lambda\in {\bf F}_q^*, \gamma\in {\bf F}_q$ and $f_{\leq{k-2}}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-2$, then the received word $(u({\bf F}_q^*), \gamma)$ is not a deep hole of the primitive projective Reed-Solomon code ${\rm PPRS}_q({\bf F}_q^*, k)$.

Corollary 1.7. Let $q\geq 4$ and $2\leq k \leq {q-2}$. If $u(x) = \lambda x^{q-2}+\delta x^{k-1}+f_{\leq{k-2}}(x)$ with $\lambda\in {\bf F}_q^*, \delta\in {\bf F}_q$ and $f_{\leq{k-2}}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-2$, then the received word $(u({\bf F}_q^*), \delta)$ is a deep hole of the primitive projective Reed-Solomon code ${\rm PPRS}_q({\bf F}_q^*, k)$.

Remark 1.8. Letting $\delta = 0$. Corollary 1.7 gives us the main result of ^[10].

In the proofs of Theorems 1.4 and 1.5, the basic tools are the MDS code and Vandemonde determinant. A key ingredient in these proofs is the so-called Dür's theorem on the relation between the covering radius and minimum distance of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ (see Lemma 2.6 below). Another important ingredient is a new result on the zero-sum problem in the finite field that we will prove in the next section.

This paper is organized as follows. First of all, in Section 2, we recall and prove several preliminary lemmas that are needed in the proofs of Theorems 1.4 and 1.5. Consequently, in Section 3, we use the lemmas presented in Section 2 to give the proofs of Theorem 1.4 and Corollary 1.6. Finally, by using the results given in Section 2, we supply in Section 4 the proofs of Theorem 1.5 and Corollary 1.7.

2.   Preliminary lemmas

In this section, our main goal is to prove several lemmas that are needed in the proof of Theorems 1.4 and 1.5. We begin with the following result on MDS codes.

Lemma 2.1. Let $C$ be a MDS code and $u_0\in C$ be a given codeword. Then the received word $u$ is a deep hole of $C$ if and only if the received word $u+u_0$ is a deep hole of $C$.

Proof. First of all, let $u$ be a received word. Then by the definition of deep hole, one knows that $u$ is a deep hole of $C$ if and only if $d(u, C) = \rho (C)$ with $\rho (C)$ being the covering radius of $C$, if and only if

Likewise, one has that the received word $u+u_0$ is a deep hole of $C$ if and only if

Since

it follows that

But $d(u+u_0, v+u_0) = d(u, v)$ for any codeword $u_0$. Hence (2.3) tells us that

Now from (2.1), (2.2) and (2.4), one can deduce that $u$ is a deep hole of $C$ if and only if $u+u_0$ is a deep hole of $C$ as one desires. So Lemma 2.1 is proved.

Remark 2.1. We should point out that if the word $u_0$ is not in $C$, then Lemma 2.1 is not true.

In what follows, we let

We have the following result.

Lemma 2.2. Let $\#(D) = q-l$ and let $u = (u_1, \cdots, u_{q-l}, u_{q-l+1})\in{\bf F}_q^{q-l+1}$ and $v = (v_1, \cdots, v_{q-l}, v_{q-l+1})\in{\bf F}_q^{q-l+1}$ be two received words with $u(x)$ and $v(x)$ being the Lagrange interpolation polynomial of the first $q-l$ components of $u$ and $v$. If $u(x) = \lambda v(x)+f_{\le{k-2}}(x), u_{q-l+1} = \lambda v_{q-l+1}$, where $\lambda\in{\bf F}_q^*$ and $f_{\le{k-2}}(x)\in {\bf F}_q[x]$ is a polynomial of degree at most $k-2$, then

Further, $u$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $v$ is a deep hole of ${\rm GPRS}_q(D, k).$

Proof. Since $u(x) = \lambda v(x)+f_{\leq k-2}(x)$, we have $u(D) = \lambda v(D)+f_{\leq k-2}(D)$. By the definition of Hamming distance, we know that for any code $C$ over ${\bf F}_q$, if $u$ and $v$ are two codewords of $C$, then

hold for any codeword $w$ of $C$ and any $\lambda \in {\bf F}_q^*$. Then from the definition of error distance and noticing that $u = (u(D), u_{q-l+1})$, we can deduce immediately that

as required. The proof of Lemma 2.2 is complete.

For a linear $[n, k]$ code $C$ with $n$ and $k$ being the length and dimension of $C$, respectively, we define the generator matrix, denoted by $G$, to be the $k\times n$ matrix of the form $G: = (g_1, \ldots, g_k)^T$, where $\{g_1, \ldots, g_k\}$ is a basis of $C$ as a vector space. Since $D = \{y_1, \ldots, y_{q-l}\}$, the following $k\times (q-l+1)$ matrix

forms a generator matrix of ${\rm GPRS}_q(D, k)$. For the purpose of this paper, we will choose the above matrix as the generator matrix of ${\rm GPRS}_q(D, k)$.

Lemma 2.3. ^[11] Let $C$ be an $[n, k]$ linear code and $G$ be the generator matrix of $C$. Then $C$ is a MDS code if and only if any $k$ distinct columns of $G$ are linear independent over finite field ${\bf F}_q$.

Throughout this paper, for any nonempty set $\{\gamma_1, \ldots, \gamma_n\}\subset{\bf F}_q$, the Vandermonde determinant, denoted by $V(\gamma_1, \ldots, \gamma_n)$, is defined as follows:

We have the following well-known result.

Lemma 2.4. ^[11] One has

In the following, we show that the generalized projective Reed-Solomon code is a MDS code.

Lemma 2.5. Let $D\subset{\bf F}_q$. Then ${\rm GPRS}_q(D, k)$ is a $[q-l+1, k]$ MDS code over finite field ${\bf F}_q$.

Proof. Let $G$ be the generator matrix of ${\rm GPRS}_q(D, k)$ given in (2.5). Write $G: = (G_1, \ldots, G_{q-l+1})$. Let $i_1, \ldots, i_k$ be arbitrary $k$ distinct integers such that $1\le i_1 < \cdots < i_k\leq q-l+1.$ We claim that $\det(G_{i_1}, \ldots, G_{i_k})\neq0$ which will be proved in what follows.

If $i_k\leq q-l$, then it follows that

The claim is true in this case.

If $i_k = q-l+1$, then by expanding the determinant according to the last column, we arrive at

The claim is proved in this case.

Now by the claim, we can derive that any $k$ columns of the generator matrix $G$ is linear independent. Then ${\rm GPRS}_q(D, k)$ is a MDS code by Lemma 2.3. This concludes the proof of Lemma 2.5.

The following result about the relation between the covering radius and minimum distance of ${\rm GPRS}_q(D, k)$ will play a key role in this paper which is due to Dür ^[4].

Lemma 2.6. ^[4] Let $D$ be a proper subset of ${\bf F}_q$. Then

Now we give a criterion to determine whether a received word is a deep hole of MDS code C.

Lemma 2.7. Let $G$ be a generator matrix of a MDS code $C = [n, k]$ over the finite field ${\bf F}_q$. If the covering radius $\rho(C) = n-k$, then a received word $u\in{\bf F}_q^n$ is a deep hole of $C$ if and only if the $(k+1)\times n$ matrix $\left(\begin{array}{c} {G}\\ {u} \end{array} \right)$ can be served as the generator matrix of another MDS code.

Proof. We first show the sufficient part. Let $C'$ be a $[n, k+1]$ MDS code with $\left(\begin{array}{c} {G}\\ {u} \end{array} \right)$ as its generator matrix. Since $u\in C'\backslash C$, one can derived that

It follows that

Therefore $u$ is a deep hole of $C$.

Now we turn to prove the necessity part. Assume that $\left(\begin{array}{c} {G}\\ {u} \end{array} \right)$ cannot be served as a generator matrix of any MDS code. By lemma 2.3, we known that there exist $k+1$ distinct columns of

are linear dependent over ${\bf F}_q$. Without loss of generality, we can suppose the first $k+1$ columns are linear dependent. Thus we have

On the other hand, since $G$ is a generator matrix of the $[n, k]$ MDS code $C$ over the finite field ${\bf F}_q$, one can obtain that

Hence there exist $k$ coefficients $a_1, \cdots, a_k\in{\bf F}_q$ that are not all zero such that $(u_1, \cdots, u_{k+1}) = \sum\limits_{i = 1}^ka_i(g_{i1}, \cdots, g_{i, {k+1}})$. Now let $v = \sum\limits_{i = 1}^ka_i(g_{i1}, \cdots, g_{in})\in C$. One can immediately deduce that

which is a contradiction with the hypothesis that $u$ is a deep hole of $C$. So Lemma 2.7 is proved.

In what follows, we show a result on the zero-sum problem in the finite field of odd characteristic.

Lemma 2.8. Let $q = p^s$ with $p$ being an odd prime number and $k$ be an integer with $2\leq k\leq {q-3}$. Then there exist a subset $I\subseteq {\bf F}_q^*$ with $\#(I) = k$ such that $\sum\limits_{z\in I}z = 0$.

Proof. Since $p$ is an odd prime number, it follows that for any $z\in {\bf F}_q^*$, one has $-z\in {\bf F}_q^*$ and $z\ne -z$ since $2z\ne 0$. But $|{\bf F}_q^*\setminus \{z, -z\}| = q-3\ge 2$ since $q\ge k+3\ge 5$. Now one can pick $z'\in {\bf F}_q^*\setminus \{z, -z\}$. Then $-z'\in {\bf F}_q^*\setminus \{z, -z, z'\}$ since $2z'\ne 0$. Continuing in this way, we finally arrive at

We consider the following cases.

Case 1. $2\mid k$. In this case, we let $I = \{z_1, -z_1, \cdots, z_{\frac{k}{2}}, -z_{\frac{k}{2}}\}$. Then $I\subset{\bf F}_q^*$ and we have

as desired. Lemma 2.8 holds if $2\mid k$.

Case 2. $2\nmid k$. Then $k\ge 3$ and so $q\ge 7$ since $2\leq k\leq {q-3}$. We claim that there are three distinct elements $z', z'', z'''\in {\bf F}_q^*$ such that $z'+z''+z''' = 0$, which will be proved by dividing into the following three subcases.

Case 2.1. $p = 3$. We pick a $z'\in {\bf F}_q^*$. Then $3z' = 0$, $-z'\ne 0$ and $2z'\ne 0$. The latter implies that $z'\ne -z'$. Since $p = 3$ and $q\ge 7$, we deduce that $q\ge 3^2 = 9$. Thus $|{\bf F}_q^*\setminus \{z', -z'\}| = q-3\ge 6$. So we can choose a $z''\in {\bf F}_q^*\setminus \{z', -z'\}$. But $2z''\ne 0$. Hence $-z''\in {\bf F}_q^*\setminus \{z', -z', z''\}$. It implies that $z'+z''\ne 0$, namely, $z'+z''\in {\bf F}_q^*$. Furthermore, we have that $z'+z''$ is not equal to anyone of the four elements $z', -z', z''$ and $-z''$. That is, $z'+z''\in {\bf F}_q^*\setminus \{z', -z', z'', -z''\}$. Hence $-(z'+z'')\in {\bf F}_q^*\setminus \{z', -z', z'', -z'', z'+z''\}$. Therefore there are three distinct elements $z', z''$ and $-(z'+z'')$ in ${\bf F}_q^*$ such that their sum equals zero. The claim holds in this case.

Case 2.2. $p = 5$. Take a $z'\in {\bf F}_q^*$. Then $5z' = 0$ and none of $z', 2z', 3z'$ and $4z'$ equals zero. It follows that the four elements $z', -z', 2z', -2z'$ are pairwise distinct. Since $q\ge 7 > 5$, one must have $q\ge 5^2 = 25$. Thus $|{\bf F}_q^*\setminus \{z', -z', 2z', -2z'\}| = q-5\ge 20$. So we can choose $z''\in {\bf F}_q^*\setminus \{z', -z', 2z', -2z'\}$. Then $-z''\in {\bf F}_q^*\setminus \{z', -z', 2z', -2z'\}$ and $z'+z''\ne 0$. The latter one tells us that $-(z'+z'')\in {\bf F}_q^*$. Obviously, $-z''\ne z''$ since $2z''\ne 0$. Hence $-z''\in {\bf F}_q^*\setminus \{z', -z', 2z', -2z', z''\}$.

Furthermore, we can deduce that $z'+z''$ is not equal to any of $z', -z', 2z', -2z', z''$ and $-z''$. This infers that $-(z'+z'')\in {\bf F}_q^*\setminus \{z', -z', 2z', -2z', z'', -z'', z'+z''\}$ since $2(z'+z'')\ne 0$. Therefore we can find three distinct elements $z', z''$ and $-(z'+z'')$ in ${\bf F}_q^*$ such that their sum equals zero. The claim holds in this case. The claim is proved in this case.

Case 2.3. $p\ge 7$. Then $le\ne 0$ for any integer $l$ with $1\le l\le 6$, where $e$ stands for the identity of the group ${\bf F}_q^*$. Since $e\ne 0, 4e\ne 0$ and $5e\ne 0$, we have $e\ne 2e, e\ne -3e$ and $2e\ne -3e$. So there are three different elements $e, 2e, -3e$ in ${\bf F}_q^*$ such that their sum is equal to zero as one desires. The claim is true in this case.

Now by the claim, we know that there are three integers $i_1, i_2$ and $i_3$ such that $1\le i_1 < i_2 < i_3\le \frac{q-1}{2}$ and $z_{i_1}+z_{i_2}+z_{i_3} = 0$.

If $q = 7$, then letting $I = \{z_{i_1}, z_{i_2}, z_{i_3}\}$ gives us the desired result.

If $q > 7$, then ${\bf F}_q^*\setminus\{\pm z_{i_1}, \pm z_{i_2}, \pm z_{i_3}\}$ is nonempty. By (2.6), we obtain that

Since $2\nmid k$, $k-3$ is even. Evidently, the sum of the first $k-3$ elements on the right hand side of (2.7) is equal to zero because $z_i+(-z_i) = 0$ for all integers $1\le i\le \frac{q-1}{2}$. Then the first $k-3$ elements on the right hand side of (2.7) together with the three elements $z_{i_1}, z_{i_2}, z_{i_3}$ gives us the desired result. Thus Lemma 2.8 is true if $2\nmid k$.

This completes the proof of Lemma 2.8.

3.   Proofs of Theorem 1.4 and Corollary 1.6

In this section, we use the lemmas presented in the previous to give the proofs of Theorem 1.4 and Corollary 1.6. At first, we show Theorem 1.4.

Proof of Theorem 1.4. Since $\deg u(x) = k$, one may let $u(x) = \lambda x^k+\nu x^{k-1}+f_{\leq{k-2}}(x)$ with $\lambda\in {\bf F}_q^*, \nu\in{\bf F}_q$ and $f_{\leq{k-2}}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-2$. Then $(u(D), c_{k-1}(u(x))) = (u(D), \nu)$. By Lemma 2.2, we have that $(u(D), \nu)$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if $(\lambda ^{-1}u(D), \lambda ^{-1}\nu)$ is a deep hole of ${\rm GPRS}_q(D, k)$. But $\lambda ^{-1}u(x) = w_k(x)+r_k(x),$ where $w_k(x): = x^k$ and

Then one has

Since $\deg r_k(x)\le k-1$, by the definition of ${\rm GPRS}_q(D, k)$ we have $(r_k(D), \lambda^{-1}\nu)\in {\rm GPRS}_q(D, k)$. Then it follows from Lemma 2.1 that $(\lambda ^{-1}u(D), \lambda ^{-1}\nu)$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $(w_k(D), 0)$ is a deep hole of ${\rm GPRS}_q(D, k)$. Then we can deduce that $(u(D), c_{k-1}(u(x)))$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $(w_k(D), 0)$ is a deep hole of ${\rm GPRS}_q(D, k)$.

We denote ${\bar w_k}: = (w_k(D), 0)$. Let $G$ be the generator matrix of ${\rm GPRS}_q(D, k)$ as given in (2.5). Then we have

Now we pick $k+1$ distinct integers with $1\leq j_1 < \cdots < j_{k+1}\leq{q-l+1}$.

Case 1. $j_{k+1}\leq{q-l}$. Then one has

Case 2. $j_{k+1} = {q-l+1}$. We can compute and get that

Now we introduce an auxiliary polynomial $g(y)$ as follows:

Then Lemma 2.4 tells us that

This infers that

But

Finally, (3.1) together with (3.2) and (3.3) gives us that

By Lemma 2.5, we know that ${\rm GPRS}_q(D, k)$ is a $[q-l+1, k]$ MDS code which implies that

Then by Lemma 2.6, one can deduce that

It then follows immediately from Lemma 2.7 that $\bar w_k = (w_k(D), 0)$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if the $(k+1)\times (q-l+1)$ matrix $\left(\begin{array}{c} G\\ {\bar w_k} \end{array} \right)$ can be served as the generator matrix of a MDS code, if and only if any $k+1$ columns of $\left(\begin{array}{c} G\\ {\bar w_k} \end{array} \right)$ are linear independent, if and only if for any $1\le j_1 < \cdots < j_{k+1}\le q-l+1$, one has

By the discussion in Cases 1 and 2, (3.4) tells us that (3.6) holds if and only if for any $1\le j_1 < \cdots < j_{k}\le q-l$, one has $\sum\limits_{i = 1}^ky_{j_i}\neq 0$. Hence we can derive that $(w_k(D), 0)$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if the sum $\sum\limits_{y\in I}y$ is nonzero for any subset $I\subseteq D$ with $\#(I) = k$ as desired.

Finally, we can conclude that $(u(D), c_{k-1}(u(x)))$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if the sum $\sum\limits_{y\in I}y$ is nonzero for any subset $I\subseteq D$ with $\#(I) = k$.

This finishes the proof of Theorem 1.4.

We can now use Theorem 1.4 to show Corollary 1.6.

Proof of Corollary 1.6. Let $l = 1$ and $a_1 = 0$. Then $D = {\bf F}_q^*$. By Lemma 2.8, there exist a subset $I\subseteq {\bf F}_q^*$ with $\#(I) = k$ such that $\sum\limits_{y\in I}y = 0$. It then follows from Theorem 1.4 that the received word $(u({\bf F}_q^*), c_{k-1}(u(x)))$ = $(u({\bf F}_q^*), \gamma)$ is not a deep hole of the primitive projective Reed-Solomon code ${\rm PPRS}_q({\bf F}_q^*, k)$. Therefore Corollary 1.6 is proved.

4.   Proofs of Theorem 1.5 and Corollary 1.7

In this section, we give the proofs of Theorem 1.5 and Corollary 1.7. We begin with the proof of Theorem 1.5.

Proof of Theorem 1.5. First of all, we note that $j$ is an integer with $1\leq j\leq l$. We introduce a polynomial $f_j(x)$ as follows:

and define a word ${\bar f_j}$ associated to $f_j(x)$ by

Then $u_j(x) = \lambda_j f_j(x)+\nu_jx^{k-1}+f_{\le k-2}^{(j)}(x)$ which implies that

It follows from (4.1) that

But

and

Hence

It follows from Lemmas 2.1 and 2.2 that the received word $(u_j(D), c_{k-1}(u_j(x)))$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if $\bar f_j$ is a deep hole of ${\rm GPRS}_q(D, k)$.

Let $G$ be the generator matrix of ${\rm GPRS}_q(D, k)$ as given in (2.5). Since $y_{i}\ne a_{j}$ for all integers $i$ with $1\leq i\leq q-l$, we have $(y_{i}-a_{j})^{q-2} = (y_{i}-a_{j})^{-1}$. It then follows that

On the other hand, from Lemma 2.7 we can deduce that $\bar f_j = (f_j(D), c_{k-1}(f_j(x)))$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$, if and only if $\left(\begin{array}{c} G\\ {\bar f_j} \end{array} \right)$ generates a MDS code, by Lemma 2.3, if and only if any $k+1$ columns of $\left(\begin{array}{c} G\\ {\bar f_j} \end{array} \right)$ are linear independent, if and only if for all $k+1$ integers $j_1, \ldots, j_{k+1}$ with $1\le j_1 < \cdots < j_{k+1}\le q-l+1$, one has

In what follows, we choose arbitrarily $k+1$ integers $j_1, \ldots, j_{k+1}$ such that $1\le j_1 < \cdots < j_{k+1}\leq q-l+1$. Consider the following two cases.

Case 1. $j_{k+1}\ne q-l+1$. Then $k+1\le j_{k+1}\le q-l$ and by (4.2), one has

Thus one can deduce that

since $y_{j_1}, \ldots, y_{j_{k+1}}$ are pairwise distinct.

Case 2. $j_{k+1} = q-l+1$. Then $1\le j_1 < \cdots < j_{k}\leq q-l$. From (4.2) and Lemma 2.4, we can deduce that

Now from Cases 1 and 2, we can deduce by (4.4) that (4.3) holds for all $k+1$ integers $j_1, \ldots, j_{k+1}$ with $1\le j_1 < \cdots < j_{k+1}\le q-l+1$ if and only if for all integers $j_1, \ldots, j_k$ with $1\le j_1 < \cdots < j_{k}\le q-l$, one has

which is equivalent to

Since $f_j(x) = (x-a_j)^{q-2}$, the binomial theorem gives us that

Then one derives that (4.5) holds for all integers $j_1, \ldots, j_k$ with $1\le j_1 < \cdots < j_{k}\le q-l$ if and only if the following is true:

or equivalently,

since $q$ is odd. In other words, $\bar f_j = (f_j(D), c_{k-1}(f_j(x)))$ is a deep hole of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$ if and only if the sum

is nonzero for any subset $I\subseteq D$ with $\#(I) = k$. Hence the desired result follows immediately. The proof of Theorem 1.5 is complete.

We can now present the proof of Corollary 1.7 as the conclusion of this paper.

Proof of Corollary 1.7. Letting $l = 1$ and $a_1 = 0$ gives us that $D = {\bf F}_q^*$. Then it follows from $a_1 = 0$ that

for any subset $I\subseteq D$ with $\#(I) = k$. Hence by Theorem 1.5, one can deduce that $(u_j(D), c_{k-1}(u_j(x))) = (u({\bf F}_q^*), \delta)$ is a deep hole of ${\rm PPRS}_q({\bf F}_q^*, k)$. This ends the proof of Corollary 1.7.

Acknowledgments

The authors would like to thank the anonymous referees for their very careful reading of the manuscript and helpful comments. This work was supported partially by National Science Foundation of China Grant #11771304, by the Fundamental Research Funds for the Central Universities and by Foundation of Sichuan Provincial Department of Education under Grant # 2016ZB0342.

Conflict of interest

We declare that we have no conflict of interest.