© Wuhan University 2023

0 Introduction

In 1960, Reed and Solomon^[1] presented an important error correcting code, that is the so-called Reed-Solomon code. In 1987, Dur^[2] defined a double extended Reed-Solomon code, which was later called projective Reed-Solomon code. He further studied the covering radius, decoding problem and the deep holes of projective Reed-Solomon codes in Refs.[3-5].

Now, we first recall the following definition of projective Reed-Solomon codes.

Definition 1^[2]Let ${\mathbb{F}}_q$ be a finite field and let ${\mathbb{F}}_q=\{{\alpha }_{\mathrm{1}},\cdots ,{\alpha }_q=\mathrm{0}\}$. Then the projective Reed-Solomon codes of length $q+\mathrm{1}$ with dimension $k$ over ${\mathbb{F}}_q$ can defined as

$\begin{array}{l}\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k):=\{(f({\alpha }_{\mathrm{1}}),f({\alpha }_{\mathrm{2}}),\cdots ,f({\alpha }_q),c_{k-\mathrm{1}}(f))\\ \in {\mathbb{F}}_q^{q+\mathrm{1}}\mid f(x)\in {\mathbb{F}}_q[x],\mathrm{d}\mathrm{e}\mathrm{g}f(x)\le k-\mathrm{1}\}\end{array}$(1)

where $c_{k-\mathrm{1}}(f)$ is the coefficient of $x^{k-\mathrm{1}}$ in $f(x)$.

Subsequently, we give the definition of deep holes of linear code $C$. To do this, for a received vector $\mathit{u}$, we first define the error distance $d(\mathit{u},C)$ and the covering radius $\rho (C)$ of linear code $C$.

Definition 2^[5] Let $C$ be an $[n,k]$ linear code over ${\mathbb{F}}_q$. The error distance of a received vector $\mathit{u}\in {\mathbb{F}}_q^n$ to code $C$ is defined by

$d(\mathit{u},C):=\underset{\mathit{v}\in C}{\mathrm{m}\mathrm{i}\mathrm{n}}\{d(\mathit{u},\mathit{v})\},$

where $d(\mathit{u},\mathit{v})$ is the Hamming distance of $\mathit{u}$ and $\mathit{v}$.

Clearly, $d(\mathit{u},C)=\mathrm{0}$ if and only if $\mathit{u}\in C$ .

For a given projective Reed-Solomon code $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k),$ we define the Lagrange interpolation polynomial $u(x)$ of the first $q$ components of received vector $\mathit{u}=(u_{\mathrm{1}},\cdots ,u_q,u_{q+\mathrm{1}})\in {\mathbb{F}}_q^{q+\mathrm{1}}$ by

$u(x):={\displaystyle \sum _{i=\mathrm{1}}^q}{u}_i\stackrel{q}{\prod _{\begin{array}{c}j=\mathrm{1}\\ j\ne i\end{array}}}\frac{x-{\alpha }_j}{{\alpha }_i-{\alpha }_j}$(2)

Obviously, one has $u({\alpha }_i)=u_i$ for $\mathrm{1}\le i\le q$ and further $d(\mathit{u},\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k))=\mathrm{0}$ if and only if $\mathrm{d}\mathrm{e}\mathrm{g}u(x)\le k-\mathrm{1},c_{k-\mathrm{1}}(u(x))=u_{q+\mathrm{1}}.$

Definition 3 ^[5]Let $C$ be an $[n,k]$ linear code over ${\mathbb{F}}_q$. Then

$\rho (C):=\mathrm{m}\mathrm{a}\mathrm{x}\{d(\mathit{u},C)\mid \mathit{u}\in {\mathbb{F}}_q^n\}$

is called as the covering radius of $C$.

In fact, there is a well known conjecture on the covering radius of projective Reed-Solomon codes.

Conjecture 1^[6] Let $k$ be an integer with $\mathrm{2}\le k\le q-\mathrm{2}.$ Suppose $\mathrm{2}\mid q,k\in \{\mathrm{2},q-\mathrm{2}\}$, then

$\rho (\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k))=q-k+\mathrm{1}.$

otherwise, $\rho (\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k))=q-k.$

Now we can propose the definition of deep holes of linear code as follows.

Definition 4 ^[7] Let $C$ be a $[n,k]$ linear code over ${\mathbb{F}}_q$. If the received vector $\mathit{u}$ such that $d(\mathit{u},C)=\rho (C)$, then $\mathit{u}$ is called a deep hole of $C$.

In 2016, Zhang et al^[8] proved that $(u({\alpha }_{\mathrm{1}}),\cdots ,$$u({\alpha }_q),\mathrm{0})+\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$ is a deep hole of projective Reed-Solomon codes $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$ by solving the subset problem over finite field ${\mathbb{F}}_q$ , where $u(x)=a{x}^k+f_{\le k-\mathrm{1}}(x)$, $a\in {\mathbb{F}}_q^{\mathrm{*}}$ , and $f_{\le k-\mathrm{1}}(x)$ is a polynomial over ${\mathbb{F}}_q$ with degree no more than $k-\mathrm{1}$. Then, in 2017, Kaipa ^[9] studied the deep holes of projective Reed-Solomon codes $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,q-\mathrm{2})$ over ${\mathbb{F}}_q$ with odd characteristic. In 2018, Xu et al^[10] proved that $(u({\alpha }_{\mathrm{1}}),\cdots ,u({\alpha }_{q-\mathrm{1}}),\mathrm{0})+\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q^{\mathrm{*}},k)$ is a deep hole of $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q^{\mathrm{*}},k)$, where $u(x)=a{x}^{q-\mathrm{2}}+f_{\le k-\mathrm{2}}(x)$ with $a\in {\mathbb{F}}_q^{\mathrm{*}}$ and $f_{\le k-\mathrm{2}}(x)$ being a polynomial over ${\mathbb{F}}_q$ whose degree not exceed $k-\mathrm{2}$. In 2020, Zhang et al^[6] completely determined all the deep holes of projective Reed-Solomon codes $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,q-\mathrm{3})$ by using the polynomial theory over finite fields and applying the finite geometry method. Meanwhile, they raised the following open problem.

Problem 1^[6] For a given projective Reed-Solomon code $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$, how to determine all its deep holes?

More results on deep holes of Reed-Solomon codes, one can see Refs.[11-15].

The main purpose of this paper is to study problem 1 over finite fields with even characteristic. Now, we describe the main theorem of this paper as following.

Theorem 1   Let ${\mathbb{F}}_q$ be finite field with even characteristic, $k\in \{\mathrm{2},q-\mathrm{2}\}$. Let $u(x)$ be the Lagrange interpolation polynomial of the first $q$ components of the received vector $\mathit{u}\in {\mathbb{F}}_q^{q+\mathrm{1}}$ . Suppose that the $(q+\mathrm{1})$-th component of $\mathit{u}$ is 0, and

$u(x)=\lambda x^k+f_{\le k-\mathrm{2}}(x)$

or

$u(x)=\lambda x^{q-\mathrm{2}}+f_{\le k-\mathrm{2}}(x),$

where $\lambda \in {\mathbb{F}}_q^{\mathrm{*}}$ , and $f_{\le k-\mathrm{2}}(x)$ is a polynomial over ${\mathbb{F}}_q$ with degree no more than $k-\mathrm{2}$. Then the received vector $\mathit{u}$ is a deep hole of $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$.

Actually, Theorem 1 partially solved Problem 1 raised by Ref.[6]. This paper is organized as follows. In Section 1, we supply some preliminary lemmas that are needed in the proof of Theorem 1. Then in Section 2, we present the proof of Theorem 1.

1 Preliminary Lemmas

In this section, we give some lemmas needed in the proof of Theorem 1. First, a formula of a special determinant over finite fields given as follows.

Lemma 1   Let $\{{\beta }_{\mathrm{1}},\cdots ,{\beta }_n\}\subset {\mathbb{F}}_q^{\mathrm{*}}$.Then

$\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\\ {\beta }_{\mathrm{1}}^{\mathrm{2}}& {\beta }_{\mathrm{2}}^{\mathrm{2}}& \cdots & {\beta }_n^{\mathrm{2}}\\ ⋮& ⋮& ⋮& ⋮\\ {\beta }_{\mathrm{1}}^n& {\beta }_{\mathrm{2}}^n& \cdots & {\beta }_n^n\end{array}\right)=\left({\displaystyle \sum _{i=\mathrm{1}}^n}{\beta }_i^{-\mathrm{1}}\right)\left({\displaystyle \prod _{i=\mathrm{1}}^n}{\beta }_i\right)\prod _{\mathrm{1}\le i<j\le n}({\beta }_j-{\beta }_i).$

Proof   Noticed that

$\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{1}\\ {\beta }_{\mathrm{1}}& {\beta }_{\mathrm{2}}& \cdots & {\beta }_n& x\\ {\beta }_{\mathrm{1}}^{\mathrm{2}}& {\beta }_{\mathrm{2}}^{\mathrm{2}}& \cdots & {\beta }_n^{\mathrm{2}}& x^{\mathrm{2}}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ {\beta }_{\mathrm{1}}^n& {\beta }_{\mathrm{2}}^n& \cdots & {\beta }_n^n& x^n\end{array}\right)=\left({\displaystyle \prod _{i=\mathrm{1}}^n}(x-{\beta }_i)\right)\prod _{\mathrm{1}\le i<j\le n}({\beta }_j-{\beta }_i).$

Then, one can immediately get Lemma 1 by comparing the coefficients of $x$ on both sides of the above equality. This completes the proof of Lemma 1.

Next, we prove the following result on subset sum over finite fields with even characteristic.

Lemma 2   Let ${\mathbb{F}}_q$ be finite field with even characteristic. If $l\in \{\mathrm{1,2},q-\mathrm{3},q-\mathrm{2}\}$, then the sum of any $l$ different elements in ${\mathbb{F}}_q^{\mathrm{*}}$ is nonzero.

Proof   The Lemma 2 obviously holds when $l=\mathrm{1}$. Put ${\mathbb{F}}_q^{\mathrm{*}}=\{{\gamma }_{\mathrm{1}},\cdots ,{\gamma }_{q-\mathrm{1}}\}.$ Now we give the proof for $l=\mathrm{2},q-\mathrm{3},q-\mathrm{2}$, respectively.

Case 1. $l=\mathrm{2}$. Without loss of generality, one can take two distinct elements of ${\mathbb{F}}_q^{\mathrm{*}}$ as ${\gamma }_{\mathrm{1}},{\gamma }_{\mathrm{2}}$. Since ${\mathbb{F}}_q$ is a finite filed with characteristic 2, hence one can get

${\gamma }_{\mathrm{1}}+{\gamma }_{\mathrm{2}}={\gamma }_{\mathrm{1}}-{\gamma }_{\mathrm{2}}\ne \mathrm{0}.$

Case 2. $l=q-\mathrm{3}$. Without loss of generality, one can also choose $q-\mathrm{3}$ distinct elements of ${\mathbb{F}}_q^{\mathrm{*}}$ as ${\gamma }_{\mathrm{1}},\cdots ,{\gamma }_{q-\mathrm{3}}$. Notice that ${\mathbb{F}}_q$ is a finite filed with characteristic 2, therefore

${\displaystyle \sum _{i=\mathrm{1}}^{q-\mathrm{3}}}{\gamma }_i={\displaystyle \sum _{i=\mathrm{1}}^{q-\mathrm{1}}}{\gamma }_i-{\gamma }_{q-\mathrm{2}}-{\gamma }_{q-\mathrm{1}}={\gamma }_{q-\mathrm{2}}-{\gamma }_{q-\mathrm{1}},$

and also ${\gamma }_{q-\mathrm{2}}\ne {\gamma }_{q-\mathrm{1}}$, thus ${\displaystyle \sum _{i=\mathrm{1}}^{q-\mathrm{3}}}{\gamma }_i\ne \mathrm{0}.$

Case 3. $l=q-\mathrm{2}$. Without loss of generality, one can pick $q-\mathrm{2}$ distinct elements ${\gamma }_{\mathrm{1}},\cdots ,{\gamma }_{q-\mathrm{2}}\in {\mathbb{F}}_q^{\mathrm{*}}$. The character of ${\mathbb{F}}_q$ is 2 can tell us that

${\displaystyle \sum _{i=\mathrm{1}}^{q-\mathrm{2}}}{\gamma }_i={\displaystyle \sum _{i=\mathrm{1}}^{q-\mathrm{1}}}{\gamma }_i-{\gamma }_{q-\mathrm{1}}={\gamma }_{q-\mathrm{1}}\ne \mathrm{0}.$

The proof of Lemma 2 is complete.

In 1991, Dur^[3] had given the following result on covering radius of projective Reed-Solomon codes over finite fields with even characteristic by using the finite geometry method.

Lemma 3^[3]Let $\mathrm{2}\mid q$, $k\in \{\mathrm{2},q-\mathrm{2}\}$. Then

$\rho (\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k))=q-k+\mathrm{1}.$

Finally, we recall a theorem on the received vector $\mathit{u}$ is whether or not a deep hole of maximal distance separable code $C$.

Lemma 4^[16] Let $C$ be $[n,k]$ maximal distance separable code over finite field ${\mathbb{F}}_q$. If the covering radius $\rho (C)$ of code $C$ is $n-k$, then the received vector $\mathit{u}\in {\mathbb{F}}_q^n$ is a deep hole of $C$ if and only if any $k+\mathrm{1}$ columns of the $(k+\mathrm{1})\times n$ matrix $\left(\begin{array}{c}\mathit{G}\\ \mathit{u}\end{array}\right)$ is linearly independent, where $\mathit{G}$ is the generator matrix of code $C$.

2 Proof of Theorem 1

In this section, we use the lemmas presented in Section 1 to give the proof of Theorem 1.

Proof   Let ${\mathbb{F}}_q=\{x_{\mathrm{1}},\cdots ,x_q=\mathrm{0}\}$. By (1) and (2), one can immediately get that

$\begin{array}{l}\left(\begin{array}{c}\mathit{G}\\ \mathit{u}\end{array}\right)=\left(\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{0}\\ x_{\mathrm{1}}& x_{\mathrm{2}}& \cdots & x_q& \mathrm{0}\\ x_{\mathrm{1}}^{\mathrm{2}}& x_{\mathrm{2}}^{\mathrm{2}}& \cdots & x_q^{\mathrm{2}}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{\mathrm{1}}^{k-\mathrm{1}}& x_{\mathrm{2}}^{k-\mathrm{1}}& \cdots & x_q^{k-\mathrm{1}}& \mathrm{1}\\ u(x_{\mathrm{1}})& u(x_{\mathrm{2}})& \cdots & u(x_q)& \mathrm{0}\end{array}\right)\\ :=({\overline{\mathit{G}}}_{\mathrm{1}},{\overline{\mathit{G}}}_{\mathrm{2}},\cdots ,{\overline{\mathit{G}}}_{q+\mathrm{1}}).\end{array}$

Assume that ${\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}}$ are any $k+\mathrm{1}$ columns of $\left(\begin{array}{c}\mathit{G}\\ \mathit{u}\end{array}\right),$ where $j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_{k+\mathrm{1}}$ are arbitrary $k+\mathrm{1}$ integers with $\mathrm{1}\le j_{\mathrm{1}}<j_{\mathrm{2}}<\cdots <j_{k+\mathrm{1}}\le q+\mathrm{1}.$ To complete the proof of the Theorem, it suffices to show

$\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\ne \mathrm{0}$(3)

To do so, we give the proof as the following eight cases.

Case 1. $u(x)=\lambda x^k+f_{\le k-\mathrm{2}}(x)$. The four cases are considered as follows.

Case 1-1. $j_{k+\mathrm{1}}<q$. At this time, one has

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})=\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_{k+\mathrm{1}}}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_{k+\mathrm{1}}}^{\mathrm{2}}\\ ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_{k+\mathrm{1}}}^{k-\mathrm{1}}\\ u(x_{j_{\mathrm{1}}})& u(x_{j_{\mathrm{2}}})& \cdots & u(x_{j_{k+\mathrm{1}}})\end{array}\right)\\ [=\lambda \mathrm{1}\le s<t\le k+\mathrm{1}(xjt-xjs)\ne \mathrm{0}]\end{array}$(4)

Case 1-2. $j_{k+\mathrm{1}}=q$. By $x_q=\mathrm{0}$, one can know that

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})=\lambda \mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{1}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_k}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_k}^{\mathrm{2}}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_k}^{k-\mathrm{1}}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^k& x_{j_{\mathrm{2}}}^k& \cdots & x_{j_k}^k& \mathrm{0}\end{array}\right)\\ ={(-\mathrm{1})}^{k+\mathrm{2}}\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^k}{x}_{j_i}\right)\prod _{\mathrm{1}\le s<t\le k}(x_{j_t}-x_{j_s})\ne \mathrm{0}\end{array}$(5)

Case 1-3. $j_k\le q-\mathrm{1},j_{k+\mathrm{1}}=q+\mathrm{1}$. One can deduce that

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})=\lambda \mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{0}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_k}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_k}^{\mathrm{2}}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_k}^{k-\mathrm{1}}& \mathrm{1}\\ x_{j_{\mathrm{1}}}^k& x_{j_{\mathrm{2}}}^k& \cdots & x_{j_k}^k& \mathrm{0}\end{array}\right)\\ ={(-\mathrm{1})}^{\mathrm{2}k+\mathrm{1}}\lambda \left({\displaystyle \sum _{i=\mathrm{1}}^k}{x}_{j_i}\right)\prod _{\mathrm{1}\le s<t\le k}(x_{j_t}-x_{j_s}).\end{array}$

And also $\mathrm{2}|q,k\in \{\mathrm{2},q-\mathrm{2}\}$, it follows from Lemma 2 that ${\displaystyle \sum _{i=\mathrm{1}}^k}{x}_{j_i}\ne \mathrm{0}.$ Then one can derive that

$\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\ne \mathrm{0}$(6)

Case 1-4. $j_k=q,j_{k+\mathrm{1}}=q+\mathrm{1}$. By $x_q=\mathrm{0}$, one can derive that

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\\ \left(\begin{array}{cccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{1}& \mathrm{0}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_{k-\mathrm{1}}}& \mathrm{0}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_{k-\mathrm{1}}}^{\mathrm{2}}& \mathrm{0}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_{k-\mathrm{1}}}^{k-\mathrm{1}}& \mathrm{0}& \mathrm{1}\\ x_{j_{\mathrm{1}}}^k& x_{j_{\mathrm{2}}}^k& \cdots & x_{j_{k-\mathrm{1}}}^k& \mathrm{0}& \mathrm{0}\end{array}\right)\\ =\lambda \mathrm{d}\mathrm{e}\mathrm{t}={(-\mathrm{1})}^{\mathrm{3}k+\mathrm{2}}\lambda \left({\displaystyle \sum _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}\right)\left({\displaystyle \prod _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}\right)\prod _{\mathrm{1}\le s<t\le k-\mathrm{1}}(x_{j_t}-x_{j_s})\end{array}$

Notice that $k-\mathrm{1}=\mathrm{1},q-\mathrm{3}$, by Lemma 2, one can get ${\displaystyle \sum _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}\ne \mathrm{0}$. It follows that

$\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\ne \mathrm{0}$(7)

Case 2.$v(x)=\lambda x^{q-\mathrm{2}}+f_{\le k-\mathrm{2}}(x)$. One only need to deal with the four cases as follows.

Case 2-1. $j_{k+\mathrm{1}}<q$. Notice that for any integer $i$ with $\mathrm{1}\le i\le k+\mathrm{1}$, one has $x_{j_i}^{q-\mathrm{2}}=x_{j_i}^{-\mathrm{1}}$. It then follows that

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})=\lambda \mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_{k+\mathrm{1}}}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_{k+\mathrm{1}}}^{\mathrm{2}}\\ ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_{k+\mathrm{1}}}^{k-\mathrm{1}}\\ x_{j_{\mathrm{1}}}^{-\mathrm{1}}& x_{j_{\mathrm{2}}}^{-\mathrm{1}}& \cdots & x_{j_{k+\mathrm{1}}}^{-\mathrm{1}}\end{array}\right)\\ ={(-\mathrm{1})}^k\lambda ({\displaystyle \prod _{i=\mathrm{1}}^{k+\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}})\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_{k+\mathrm{1}}}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_{k+\mathrm{1}}}^{\mathrm{2}}\\ ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^k& x_{j_{\mathrm{2}}}^k& \cdots & x_{j_{k+\mathrm{1}}}^k\end{array}\right)\\ ={(-\mathrm{1})}^k\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^{k+\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\right)\prod _{\mathrm{1}\le s<t\le k+\mathrm{1}}(x_{j_t}-x_{j_s})\ne \mathrm{0}\end{array}$(8)

Case 2-2. $j_{k+\mathrm{1}}=q$. Since $x_{j_i}^{q-\mathrm{2}}=x_{j_i}^{-\mathrm{1}}(\mathrm{1}\le i\le k)$ and $x_q=\mathrm{0}$, so

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})=\lambda \mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{1}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_k}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_k}^{\mathrm{2}}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_k}^{k-\mathrm{1}}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{-\mathrm{1}}& x_{j_{\mathrm{2}}}^{-\mathrm{1}}& \cdots & x_{j_k}^{-\mathrm{1}}& \mathrm{0}\end{array}\right)\\ ={(-\mathrm{1})}^{k+\mathrm{2}}\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^k}{x}_{j_i}^{-\mathrm{1}}\right)\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}{x}_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_k}^{\mathrm{2}}\\ x_{j_{\mathrm{1}}}^{\mathrm{3}}& x_{j_{\mathrm{2}}}^{\mathrm{3}}& \cdots & x_{j_k}^{\mathrm{3}}\\ ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^k& x_{j_{\mathrm{2}}}^k& \cdots & x_{j_k}^k\\ \mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\end{array}\right)\end{array}$

Then by Lemma 1, one can derive that

$\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})={(-\mathrm{1})}^{\mathrm{2}k+\mathrm{1}}\lambda \left({\displaystyle \sum _{i=\mathrm{1}}^k}{x}_{{}_{j_i}}^{-\mathrm{1}}\right)\prod _{\mathrm{1}\le s<t\le k}(x_{j_t}-x_{j_s}).$

Now note that $k\in \{\mathrm{2},q-\mathrm{2}\}$ and $x_{j_i}^{-\mathrm{1}}\in {\mathbb{F}}_q^{\mathrm{*}}$. Then Lemma 2 can tell us that ${\displaystyle \sum _{i=\mathrm{1}}^k}{x}_{j_i}^{-\mathrm{1}}\ne \mathrm{0}.$ This implies

$\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\ne \mathrm{0}$(9)

Case 2-3. $j_k\le q-\mathrm{1},j_{k+\mathrm{1}}=q+\mathrm{1}.$ Since $x_{j_i}^{q-\mathrm{2}}=x_{j_i}^{-\mathrm{1}}(\mathrm{1}\le i\le k),$ one then can deduce that

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})=\lambda \mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{0}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_k}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_k}^{\mathrm{2}}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_k}^{k-\mathrm{1}}& \mathrm{1}\\ x_{j_{\mathrm{1}}}^{-\mathrm{1}}& x_{j_{\mathrm{2}}}^{-\mathrm{1}}& \cdots & x_{j_k}^{-\mathrm{1}}& \mathrm{0}\end{array}\right)\\ ={(-\mathrm{1})}^{\mathrm{2}k+\mathrm{1}}\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^k}{x}_{j_i}^{-\mathrm{1}}\right)\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}{x}_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_k}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_k}^{\mathrm{2}}\\ ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_k}^{k-\mathrm{1}}\\ \mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\end{array}\right)\\ ={(-\mathrm{1})}^{\mathrm{3}k}\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^k}{x}_{j_i}^{-\mathrm{1}}\right)\prod _{\mathrm{1}\le s<t\le k}(x_{j_t}-x_{j_s})\ne \mathrm{0}\end{array}$(10)

Case 2-4. $j_k=q,j_{k+\mathrm{1}}=q+\mathrm{1}.$ Owing to $x_{j_i}^{q-\mathrm{2}}=x_{j_i}^{-\mathrm{1}}(\mathrm{1}\le i\le k-\mathrm{1})$ and $x_q=\mathrm{0},$ one then can get

$\begin{array}{l}=\lambda \mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccccc}\mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}& \mathrm{1}& \mathrm{0}\\ x_{j_{\mathrm{1}}}& x_{j_{\mathrm{2}}}& \cdots & x_{j_{k-\mathrm{1}}}& \mathrm{0}& \mathrm{0}\\ x_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_{k-\mathrm{1}}}^{\mathrm{2}}& \mathrm{0}& \mathrm{0}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_{k-\mathrm{1}}}^{k-\mathrm{1}}& \mathrm{0}& \mathrm{1}\\ x_{j_{\mathrm{1}}}^{-\mathrm{1}}& x_{j_{\mathrm{2}}}^{-\mathrm{1}}& \cdots & x_{j_{k-\mathrm{1}}}^{-\mathrm{1}}& \mathrm{0}& \mathrm{0}\end{array}\right)\\ ={(-\mathrm{1})}^{\mathrm{3}k+\mathrm{2}}\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\right)\mathrm{d}\mathrm{e}\mathrm{t}\left(\begin{array}{cccc}{x}_{j_{\mathrm{1}}}^{\mathrm{2}}& x_{j_{\mathrm{2}}}^{\mathrm{2}}& \cdots & x_{j_{k-\mathrm{1}}}^{\mathrm{2}}\\ x_{j_{\mathrm{1}}}^{\mathrm{3}}& x_{j_{\mathrm{2}}}^{\mathrm{3}}& \cdots & x_{j_{k-\mathrm{1}}}^{\mathrm{3}}\\ ⋮& ⋮& ⋮& ⋮\\ x_{j_{\mathrm{1}}}^{k-\mathrm{1}}& x_{j_{\mathrm{2}}}^{k-\mathrm{1}}& \cdots & x_{j_{k-\mathrm{1}}}^{k-\mathrm{1}}\\ \mathrm{1}& \mathrm{1}& \cdots & \mathrm{1}\end{array}\right)\end{array}$

By Lemma 1, one can deduce that

$\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\\ ={(-\mathrm{1})}^{\mathrm{4}k}\lambda \left({\displaystyle \prod _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\right)\left({\displaystyle \sum _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\right)\left({\displaystyle \prod _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\right)\prod _{\mathrm{1}\le s<t\le k-\mathrm{1}}(x_{j_t}-x_{j_s})\\ =\lambda \left({\displaystyle \sum _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\right)\prod _{\mathrm{1}\le s<t\le k-\mathrm{1}}(x_{j_t}-x_{j_s})\end{array}$

Notice that $k-\mathrm{1}=\mathrm{1},q-\mathrm{3}$ and $x_{j_i}^{-\mathrm{1}}\in {\mathbb{F}}_q^{\mathrm{*}}$. Applying Lemma 2, one can obtain ${\displaystyle \sum _{i=\mathrm{1}}^{k-\mathrm{1}}}{x}_{j_i}^{-\mathrm{1}}\ne \mathrm{0}.$ It yields that

$\mathrm{d}\mathrm{e}\mathrm{t}({\overline{\mathit{G}}}_{j_{\mathrm{1}}},{\overline{\mathit{G}}}_{j_{\mathrm{2}}},\cdots ,{\overline{\mathit{G}}}_{j_{k+\mathrm{1}}})\ne \mathrm{0}$(11)

Thus, (3) can be immediately obtained from (4)-(11), that is, any $k+\mathrm{1}$columns of $\left(\begin{array}{c}\mathit{G}\\ \mathit{u}\end{array}\right)$ are linearly independent. On the other hand, $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$ is a maximal distance separable code and Lemma 3 also tell us that the covering radius of $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$ is

$\rho (\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k))=q-k+\mathrm{1}=n-k.$

Therefore, by Lemma 4, one can know that $\mathit{u}$ is a deep hole of projective Reed-Solomon codes $\mathrm{P}\mathrm{R}\mathrm{S}({\mathbb{F}}_q,k)$. This finish the proof of Theorem 1.

References