# Deep Holes of Twisted Reed-Solomon Codes

Weijun Fang, Jingke Xu, Ruiqi Zhu Weijun Fang and Ruiqi Zhu are with Key the
Laboratory of Cryptologic Technology and Information Security, Ministry of
Education, Shandong University, Qingdao, 266237, China, and School of Cyber
Science and Technology, Shandong University, Qingdao 266237, China, and
Quancheng Laboratory, Jinan 250103, China (emails<EMAIL_ADDRESS>zrq77772022@sina.com). Jingke Xu is with the School of Information Science and
Engineering, Shandong Agricultural University, Tai’an, China
(email:xujingke@sdau.edu.cn).The work of Weijun Fang and Ruiqi Zhu was
supported in part by the National Key Research and Development Program of
China under Grant Nos. 2022YFA1004900 and 2021YFA1001000, the National Natural
Science Foundation of China under Grant No. 62201322, and the Natural Science
Foundation of Shandong under Grant No. ZR2022QA031, and the Taishan Scholar
Program of Shandong Province. The work of Jingke Xu is supported in part by
the National Natural Science Foundation of China under Grant No. 12201362, and
the Natural Science Foundation of Shandong Province under Grant No.
ZR2021QA043. (Corresponding Author: Jingke Xu).Manuscript submitted

###### Abstract

The deep holes of a linear code are the vectors that achieve the maximum error
distance to the code. There has been extensive research on the topic of deep
holes in Reed-Solomon codes. As a generalization of Reed-Solomon codes, we
investigate the problem of deep holes of a class of twisted Reed-Solomon codes
in this paper. The covering radius and a standard class of deep holes of
twisted Reed-Solomon codes ${\rm TRS}_{k}(\mathcal{A},\theta)$ are obtained
for a general evaluation set $\mathcal{A}\subseteq\mathbb{F}_{q}$.
Furthermore, we consider the problem of determining all deep holes of the
full-length twisted Reed-Solomon codes ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.
Specifically, we prove that there are no other deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ for $\frac{3q-8}{4}\leq k\leq q-4$ when $q$
is even, and $\frac{3q+2\sqrt{q}-7}{4}\leq k\leq q-4$ when $q$ is odd. We also
completely determine their deep holes for $q-3\leq k\leq q-1$.

###### Index Terms:

Deep Holes, Twisted Reed-Solomon Codes, Annihilated Polynomial Method,
Character Sums, Gauss Sums

##  I Introduction

Let $\mathbb{F}_{q}$ be the finite field of $q$ elements with characteristic
$p$ and $\mathbb{F}^{n}_{q}$ be the vector space of dimension $n$ over
$\mathbb{F}_{q}$. The Hamming distance $d(\bm{u},\bm{v})$ of two vectors
$\bm{u}=(u_{0},u_{1},\cdots,u_{n-1}),\bm{v}=(v_{0},v_{1},\cdots,v_{n-1})\in\mathbb{F}^{n}_{q}$
is defined as $d(\bm{u},\bm{v})\triangleq\\{0\leq i\leq n-1:u_{i}\neq
v_{i}\\}.$

An $[n,k,d]_{q}$-linear code $C$ is just a $k$-dimensional subspace of
$\mathbb{F}^{n}_{q}$ with minimum distance $d=d(C)$, which is defined as
$d(C)\triangleq\\{d(\bm{u},\bm{v}):\bm{u}\neq\bm{v}\in C\\}.$ For any vector
$\bm{u}\in\mathbb{F}^{n}_{q}$, we define its error distance to the code $C$ as
$d(\bm{u},C)=\min\limits_{\bm{c}\in C}\\{d(\bm{u},\bm{c})\\}.$ Then the
covering radius $\rho(C)$ of $C$ is defined as the maximum error distance,
i.e., $\rho(C)=\max\limits_{\bm{u}\in\mathbb{F}^{n}_{q}}d(\bm{u},C).$ The
vectors achieving maximum error distance are called deep holes of the code.
The computation of the covering radius is a fundamental problem in coding
theory. However, McLoughlin[1] has proven that the computational difficulty of
determining the covering radius of random linear codes strictly exceeds NP-
completeness. There are few linear codes with known covering radii, and
examples include perfect codes [2], generalized Reed-Solomon codes[3], and
first-order Reed-Muller codes $RM(1,m)$ (where $m$ is even)[4], among others.
Therefore, it is very hard to determine the exact value of the covering radius
of a linear code, not to mention deciding its deep holes.

In recent years, the problem of determining the deep holes of Reed-Solomon
codes has attracted lots of attention in the literature [5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16].

###### Definition 1

Let
$\mathcal{A}=\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\\}\subseteq\mathbb{F}_{q}$
be the evaluation set, then the Reed-Solomon code ${\rm RS}_{k}(\mathcal{A})$
of length $n$ and dimension $k$, is defined as

${\rm
RS}_{k}(\mathcal{A})=\\{(f(\alpha_{1}),f(\alpha_{2}),\cdots,f(\alpha_{n})):f(x)\in\mathbb{F}_{q}[x],\deg(f)\leq
k-1\\}.$

It can be shown that the covering radius of ${\rm RS}_{k}(\mathcal{A})$ is
equal to $n-k$. It was shown in [17] that the problem of determining whether a
vector is a deep hole of a given Reed-Solomon code is NP-hard.

###### Definition 2

The generating polynomial of a vector $\bm{u}\in\mathbb{F}^{n}_{q}$ is defined
as the unique polynomial $u(x)\in\mathbb{F}_{q}[x]$ with $\deg(f)\leq n-1$ and
$f(\alpha_{i})=u_{i}$ for $i=1,2,\cdots,n$. Conversely, we denote
$\bm{u}_{f}=(f(\alpha_{1}),f(\alpha_{2}),\cdots,f(\alpha_{n}))\in\mathbb{F}^{n}_{q}$
for any polynomial $f(x)\in\mathbb{F}_{q}[x]$ with $\deg(f)\leq n-1$.

It can be verified that the vectors with generating polynomial of degree $k$
are deep holes of ${\rm RS}_{k}(\mathcal{A})$ [5]. There may be some other
deep holes of ${\rm RS}_{k}(\mathcal{A})$ for certain subset $\mathcal{A}$ of
$\mathbb{F}_{q}$. However, for the Reed-Solomon codes with full length, i.e.,
${\rm RS}_{k}(\mathbb{F}_{q})$, Cheng and Murray [5] conjectured that:

######  Conjecture 1 ([5])

For $2\leq k\leq q-2$, all deep holes of ${\rm RS}_{k}(\mathbb{F}_{q})$ have
generating polynomials of degree $k$, except when $q$ is even and $k=q-3$.

Significant research advances have been made regarding Conjecture 1. Li and
Wan [6](resp. Zhang et al. [12] ) proved that the vectors with generating
polynomials of degree $k+1$ (resp. $k+2$) are not deep holes of ${\rm
RS}_{k}(\mathbb{F}_{q})$. By employing techniques such as exponential sums,
algebraic geometry, and sieving methods, Li and Wan [7], Zhu and Wan [10],
Cafure[11] have provided estimates for the error distances of certain vectors,
thereby advancing Conjecture 1. When $2\leq k\leq p-2$ or $2\leq q-p\leq k\leq
q-3$, Zhuang et al. [14] proved that Conjecture 1 is true. In particular,
Conjecture 1 holds for prime fields. Applying Seroussi and Roth’s results on
the extension of RS codes [18], Kaipa [15] proved that Conjecture 1 holds for
$k\geq\lfloor\frac{q-1}{2}\rfloor$.

Since Beelen et al. first introduced twisted Reed-Solomon (TRS) codes in [19,
20], many coding scholars have studied TRS codes with good properties,
including TRS MDS codes, TRS self-dual codes, and TRS LCD codes [21, 22, 23,
24, 25]. Beelen et al. [26] proposed the application of TRS codes to the
McEliece PKC, suggesting that TRS codes with multiple twists could be used as
an alternative to Goppa codes. Lavauzelle et al. [27] presented an efficient
key-recovery attack on the McEliece-type cryptosystem based on TRS codes. TRS
codes have played an increasingly important role in coding theory. As a
generalization of Reed-Solomon codes, it is also difficult to determine the
covering radius and deep holes of twisted RS codes. Thus, as a preliminary
exploration, we mainly focus on the full-length twisted RS codes and obtain
some results on their covering radius and deep holes in this paper.

###  I-A Our Results

Suppose $2\leq k<n$ and
$\mathcal{A}=\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\\}\subseteq\mathbb{F}_{q}$.
Let $\theta\neq 0\in\mathbb{F}_{q}$ (when $\theta=0$, the TRS code defined
below is just the RS code) and

$\mathcal{S}_{k,\theta}\triangleq\\{f_{k,\theta}(x)\triangleq\sum_{i=0}^{k-2}f_{i}x^{i}+f_{k-1}(x^{k-1}+\theta
x^{k}):f_{0},f_{1},\cdots,f_{k-1}\in\mathbb{F}_{q}\\}.$ (1)

###### Definition 3

The TRS code ${\rm TRS}_{k}(\mathcal{A},\theta)$ is defined as

${\rm
TRS}_{k}(\mathcal{A},\theta)\triangleq\\{(f(\alpha_{1}),f(\alpha_{2}),\cdots,f(\alpha_{n})):f\in\mathcal{S}_{k,\theta}\\}.$

Firstly, we determine the covering radius and a standard class of deep holes
of ${\rm TRS}_{k}(\mathcal{A},\theta)$ for a subset
$\mathcal{A}\subseteq\mathbb{F}_{q}$.

###### Theorem 1

Suppose $\mathcal{A}\subseteq\mathbb{F}_{q}$ with $|\mathcal{A}|=n$ and
$1<k<n$. Then

(i)

The covering radius $\rho({\rm TRS}_{k}(\mathcal{A},\theta))$ of ${\rm
TRS}_{k}(\mathcal{A},\theta)$ is equal to $n-k$.

(ii)

Suppose $a\in\mathbb{F}^{*}_{q}$ , then the vector $\bm{u}_{f}$ with
generating polynomial $f(x)=ax^{k}+f_{k,\theta}(x)$, where
$f_{k,\theta}(x)\in\mathcal{S}_{k,\theta}$ given by Eq. (1), is a deep hole of
${\rm TRS}_{k}(\mathcal{A},\theta)$.

Furthermore, we are committed to completely determining the deep holes of the
full-length twisted RS code ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$. For $q$
being even or odd, we use different methods respectively to settle its deep
holes.

For even $q$, inspired by the methods outlined in [15, 28], we provide a
necessary condition for a vector to be a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$. Specifically, a deep hole corresponds to a
multivariate polynomial being zero on the set $\mathbb{F}_{q}$. When the
dimension $k$ satisfies $\frac{3q-8}{4}\leq k\leq q-4$, combined with the
Schwartz-Zippel Lemma, we can deduce that the polynomial is indeed the zero
polynomial. Thus we obtain the result that the standard deep holes given in
Theorem 1 are all the deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ for
$\frac{3q-8}{4}\leq k\leq q-4$. For the boundary cases $k=q-3,q-2$, and $q-1$,
by using some results on equations over finite fields and character sums, we
also completely determine the deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$. Precisely,

###### Theorem 2

Suppose $q\geq 8$ is even, $\bm{u}\in\mathbb{F}^{q}_{q}$ and ${\rm Tr}(\cdot)$
is the absolute trace function from $\mathbb{F}_{q}$ to $\mathbb{F}_{2}$.

(i)

If $\frac{3q-8}{4}\leq k\leq q-4$ or $k=q-1$, then $\bm{u}$ is a deep hole of
${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is generated by
Theorem 1.

(ii)

If $k=q-2$, then $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is generated by
$w_{0}x^{q-1}+w_{1}x^{q-2}+f_{q-2,\theta}(x)$ with $w_{0}=0,w_{1}\neq 0$ or
$w_{0}\neq 0$ and ${\rm Tr}(\frac{w_{1}\theta}{w_{0}})=1$, where
$f_{q-2,\theta}(x)\in\mathcal{S}_{q-2,\theta}$.

(iii)

If $k=q-3$, then $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is given by Theorem 1
or generated by $a(x^{q-2}+\theta^{-1}x^{q-3})+f_{q-3,\theta}(x)$ with $a\neq
0$, $f_{q-3,\theta}(x)\in\mathcal{S}_{q-3,\theta}$ and $2\nmid m$.

For odd $q$, we mainly use Seroussi and Roth’results for the MDS extensions of
RS codes [18] (which is also the key of the results on the Conjecture 1
obtained by Kaipa [15]). Through certain results concerning equations over
finite fields, we prove that the standard deep holes given in Theorem 1 are
all the deep holes of $\frac{3q+2\sqrt{q}-7}{4}\leq k\leq q-4$. The deep holes
of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ are also completely determined for
the boundary cases $k=q-3$, $q-2$, and $q-1$. Specifically,

###### Theorem 3

Suppose $q>16$ is odd, $\bm{u}\in\mathbb{F}^{q}_{q}$, and $\eta$ is the
quadratic character of $\mathbb{F}_{q}$.

(i)

If $\frac{3q+2\sqrt{q}-7}{4}\leq k\leq q-4$ or $k=q-1$, then $\bm{u}$ is a
deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is
generated by Theorem 1.

(ii)

If $k=q-2$, then $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is generated by
$w_{0}(1-x^{q-1})+w_{1}x^{q-2}+f_{q-2,\theta}(x)$ with $w_{0}=0,w_{1}\neq 0$
or $w_{0}\neq 0$ and $\eta(w_{0}^{2}-4w_{0}w_{1}\theta)=-1$.

(iii)

If $k=q-3$, then $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is given by Theorem 1
or generated by $a(x^{q-2}+\frac{1}{3\theta}x^{q-3})+f_{q-3,\theta}(x)$ with
$a\neq 0$, $f_{q-3,\theta}(x)\in\mathcal{S}_{q-3,\theta}$ and $\eta(-3)=-1$.

###  I-B Organization

The rest of this paper is organized as follows. In Section II, we present some
results on some determinants and character sums. In Section III, we determine
the covering radius and standard deep holes of twisted RS codes. In Section
IV, we present the results on the completeness of deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$. Section V concludes the paper and provides a
conjecture on the deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.

##  II Preliminaries

We first list some fixed notations that will be used throughout this paper.

  * •

${\rm Char}(\mathbb{F}_{q})$ is the characteristic of $\mathbb{F}_{q}$, and
$\mathbb{F}_{q}^{*}=\mathbb{F}_{q}\setminus\\{0\\}$.

  * •

For $\alpha\in\mathbb{F}_{q}$,
$\bm{c}_{n,\theta}(\alpha)=(1,\alpha,\cdots,\alpha^{n-2},\alpha^{n-1}-\theta\alpha^{n})^{\top}\in\mathbb{F}^{n}_{q}$.

  * •

For $\alpha\in\mathbb{F}_{q}$,
$\bm{c}_{n}(\alpha)=(1,\alpha,\cdots,\alpha^{n-1})^{\top}\in\mathbb{F}^{n}_{q}$;
$\bm{c}_{n}(\infty)=(0,0,\cdots,0,1)^{\top}\in\mathbb{F}^{n}_{q}$.

  * •

$V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})=\prod\limits_{1\leq i<j\leq
n}(\alpha_{j}-\alpha_{i})$, the determinant of the Vandermonde matrix defined
by $\alpha_{1},\alpha_{2},\cdots,\alpha_{n}$.

  * •

$\det({\bm{v}}_{1}|{\bm{v}}_{2}|\cdots|{\bm{v}}_{n})$, the determinant of the
matrix defined by $n$ column vectors
${\bm{v}}_{1},{\bm{v}}_{2},\cdots,{\bm{v}}_{n}$ in $\mathbb{F}_{q}^{n}$.

  * •

For $f\in\mathbb{F}_{q}[X_{1},X_{2},\cdots,X_{n}]$, ${\rm
N}(f)=|\\{(X_{1},\cdots,X_{n})\in\mathbb{F}_{q}^{n}:f(X_{1},\cdots,X_{n})=0\\}|$.

###  II-A Some Determinants

In this subsection, we present the calculations of some determinants, which
will be used in our proof of main theorems.

###### Lemma 1

For any $\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\in\mathbb{F}_{q}$,

$\det\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\alpha_{1}&\alpha_{2}&\cdots&\alpha_{n}\\\ \vdots&\vdots&\ddots&\vdots\\\
\alpha_{1}^{n-2}&\alpha_{2}^{n-2}&\cdots&\alpha_{n}^{n-2}\\\
\alpha_{1}^{n}&\alpha_{2}^{n}&\cdots&\alpha_{n}^{n}\\\
\end{array}\right)=V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})\sum_{i=1}^{n}\alpha_{i}.$

###### Proof:

The desired determinant is equal to $(-1)^{2n+1}$ times the coefficient of the
term $X^{n-1}$ in $V(\alpha_{1},\cdots,\alpha_{n},X)$. Note that
$V(\alpha_{1},\cdots,\alpha_{n},X)=V(\alpha_{1},\cdots,\alpha_{n})\prod\limits_{i=1}^{n}(X-\alpha_{i}).$
The lemma then follows. ∎

###### Lemma 2

For any $\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\in\mathbb{F}_{q}$,

$\det\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\alpha_{1}&\alpha_{2}&\cdots&\alpha_{n}\\\ \vdots&\vdots&\ddots&\vdots\\\
\alpha_{1}^{n-2}&\alpha_{2}^{n-2}&\cdots&\alpha_{n}^{n-2}\\\
\alpha_{1}^{n+1}&\alpha_{2}^{n+1}&\cdots&\alpha_{n}^{n+1}\\\
\end{array}\right)=V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})\sum_{1\leq i\leq
j\leq n}\alpha_{i}\alpha_{j}.$

###### Proof:

The desired determinant is equal to $(-1)^{2n+1}$ times the coefficient of the
term $X^{n-1}$ in

$\det\left(\begin{array}[]{cccc}1&\cdots&1&1\\\
\alpha_{1}&\cdots&\alpha_{n}&X\\\ \vdots&\ddots&\vdots&\vdots\\\
\alpha_{1}^{n-2}&\cdots&\alpha_{n}^{n-2}&X^{n-2}\\\
\alpha_{1}^{n-1}&\cdots&\alpha_{n}^{n-1}&X^{n-1}\\\
\alpha_{1}^{n+1}&\cdots&\alpha_{n}^{n+1}&X^{n+1}\\\ \end{array}\right).$

By Lemma 1, the above determinant is equal to

$V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n},X)(\sum_{i=1}^{n}\alpha_{i}+X)=V(\alpha_{1},\cdots,\alpha_{n})\prod_{i=1}^{n}(X-\alpha_{i})(\sum_{i=1}^{n}\alpha_{i}+X).$

Note that the coefficient of the term $X^{n-1}$ in
$\prod\limits_{i=1}^{n}(X-\alpha_{i})(\sum\limits_{i=1}^{n}\alpha_{i}+X)$ is
equal to

$-(\sum_{i=1}^{n}\alpha_{i})^{2}+\sum_{1\leq i<j\leq
n}\alpha_{i}\alpha_{j}=-\sum_{1\leq i\leq j\leq n}\alpha_{i}\alpha_{j}.$

The lemma then follows. ∎

###### Lemma 3

For any $\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\in\mathbb{F}_{q}$,

$\det\big{(}\bm{c}_{n,\theta}(\alpha_{1})|\bm{c}_{n,\theta}(\alpha_{2})|\cdots|\bm{c}_{n,\theta}(\alpha_{n})\big{)}\\\
=V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})\big{(}1-\theta\sum_{i=1}^{n}\alpha_{i}\big{)}.$

###### Proof:

By Lemma 1, we have

$\displaystyle\det\big{(}\bm{c}_{n,\theta}(\alpha_{1})|\bm{c}_{n,\theta}(\alpha_{2})|\cdots|\bm{c}_{n,\theta}(\alpha_{n})\big{)}$
$\displaystyle=$ $\displaystyle
V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})-\theta\det\left(\begin{array}[]{ccc}1&\cdots&1\\\
\alpha_{1}&\cdots&\alpha_{n}\\\ \vdots&\ddots&\vdots\\\
\alpha_{1}^{n-2}&\cdots&\alpha_{n}^{n-2}\\\
\alpha_{1}^{n}&\cdots&\alpha_{n}^{n}\\\ \end{array}\right)$ $\displaystyle=$
$\displaystyle
V(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})\big{(}1-\theta\sum_{i=1}^{n}\alpha_{i}\big{)}.$

∎

###  II-B Character Sums

In this subsection, we present some basic notations and results of group
characters and exponential sums [32]. Suppose $p={\rm Char}(\mathbb{F}_{q})$
and $q=p^{m}$, the absolute trace function ${\rm Tr}(x)$ is defined by

${\rm Tr}(x)=x+x^{p}+x^{p^{2}}+\cdots+x^{p^{m-1}}.$

An additive character $\chi$ of $\mathbb{F}_{q}$ is a homomorphism from
$\mathbb{F}_{q}$ into the multiplicative group $U$ of complex numbers of
absolute value 1. For any $a\in\mathbb{F}_{q}$, the function

$\chi_{a}(x)=\zeta_{p}^{{\rm Tr}(ax)},$

defines an additive character of $\mathbb{F}_{q}$, where
$\zeta_{p}=e^{\frac{2\pi\sqrt{-1}}{p}}$. For $a=0$, $\chi_{a}(x)$ is called
the trivial additive character of $\mathbb{F}_{q}$, for which $\chi_{0}(x)=1$
for all $x\in\mathbb{F}_{q}$. For $a=1$, $\chi_{1}(x)=\zeta_{p}^{{\rm Tr}(x)}$
is called the canonical additive character of $\mathbb{F}_{q}$.

Characters of the multiplicative group $\mathbb{F}_{q}^{*}$ of
$\mathbb{F}_{q}$ are called multiplicative characters of $\mathbb{F}_{q}$. It
is known that all characters of $\mathbb{F}_{q}^{*}$ are given by

$\psi_{i}\left(\pi^{j}\right)=\zeta_{q-1}^{ij}\text{ for }j=0,1,\ldots,q-2,$

where $0\leq i\leq q-2$ and $\pi$ is a primitive element of $\mathbb{F}_{q}$.
It is convenient to extend the definition of $\psi_{i}$ by setting
$\psi_{i}(0)=0$. For $i=0$, $\psi_{0}(x)=1$ for all $x\in\mathbb{F}^{*}_{q}$
is called the trivial multiplicative character of $\mathbb{F}_{q}$. For
$i=(q-1)/2$, the multiplicative character $\psi_{(q-1)/2}$ is called the
quadratic character of $\mathbb{F}_{q}$, and is denoted by $\eta$ in this
paper. That is $\eta(x)=1$ if $x\in\mathbb{F}_{q}^{*}$ is a square;
$\eta(x)=-1$ if $x\in\mathbb{F}_{q}^{*}$ is not a square.

Let $\psi$ be a multiplicative character and $\chi$ an additive character of
$\mathbb{F}_{q}$. The $\operatorname{Gauss}\operatorname{sum}G(\psi,\chi)$ is
defined by

$G(\psi,\chi)=\sum_{x\in\mathbb{F}_{q}^{*}}\psi(x)\chi(x).$

######  Proposition 1 ([32])

(i)

$G(\psi,\chi_{ab})=\overline{\psi(a)}G(\psi,\chi_{b})$, for any
$a\in\mathbb{F}_{q}^{*}$ and $b\in\mathbb{F}_{q}$.

(ii)

If $\psi\neq\psi_{0}$ and $\chi\neq\chi_{0}$, then $|G(\psi,\chi)|=\sqrt{q}$.

######  Proposition 2 ([32], Theorems 5.32, 5.33 and 5.34)

Let $\chi\neq\chi_{0}$ be a nontrivial additive character of $\mathbb{F}_{q}$.

(i)

Suppose $n\in\mathbb{N}$, and $d=\operatorname{gcd}(n,q-1)$. Then

$\left|\sum_{c\in\mathbb{F}_{q}}\chi\left(ac^{n}+b\right)\right|\leqslant(d-1)q^{1/2}$

for any $a,b\in\mathbb{F}_{q}$ with $a\neq 0$.

(ii)

Suppose $q$ odd, let $f(x)=a_{2}x^{2}+a_{1}x+a_{0}\in\mathbb{F}_{q}[x]$ with
$a_{2}\neq 0$. Then

$\sum_{c\in\mathbb{F}_{q}}\chi(f(c))=\chi\left(a_{0}-a_{1}^{2}\left(4a_{2}\right)^{-1}\right)\eta\left(a_{2}\right)G(\eta,\chi),$

where $\eta$ is the quadratic character of $\mathbb{F}_{q}$.

(iii)

Suppose $q$ even and $b\in\mathbb{F}_{q}^{*}$. Let
$f(x)=a_{2}x^{2}+a_{1}x+a_{0}\in\mathbb{F}_{q}[x]$ with $a_{2}\neq 0$. Then

$\sum_{c\in\mathbb{F}_{q}}\chi_{b}(f(c))=\begin{cases}\chi_{b}(a_{0})q&{\rm
if~{}}ba_{2}+b^{2}a_{1}^{2}=0,\\\ 0&{\rm otherwise}.\end{cases}$

######  Proposition 3 ([32], Theorem 5.41)

Let $\psi$ be a multiplicative character of $\mathbb{F}_{q}$ of order $m>1$
and let $f\in\mathbb{F}_{q}[x]$ be a monic polynomial of positive degree that
is not an $m$-th power of a polynomial. Let $d$ be the number of distinct
roots of $f$ in its splitting field over $\mathbb{F}_{q}$. Then for every
$a\in\mathbb{F}_{q}$, we have

$\left|\sum_{c\in\mathbb{F}_{q}}\psi(af(c))\right|\leqslant(d-1)q^{1/2}.$

######  Proposition 4 ([32], Lemma 6.24)

For odd $q$, let $b\in\mathbb{F}_{q},a_{1},a_{2}\in\mathbb{F}^{*}_{q}$, and
$\eta$ be the quadratic character of $\mathbb{F}_{q}$. Then ${\rm
N}(a_{1}X^{2}+a_{2}Y^{2}-b)=q+v(b)\eta(-a_{1}a_{2}),$ where $v(0)=q-1$ and
$v(b)=-1$ for $b\in\mathbb{F}^{*}_{q}$.

##  III Covering Radius and Standard Deep Holes of ${\rm
TRS}_{k}(\mathcal{A},\theta)$

In this section, we determine the covering radius and a class of deep holes of
${\rm TRS}_{k}(\mathcal{A},\theta)$ by using the redundancy bound and
generator matrix of the code.

Suppose $\mathcal{A}\subseteq\mathbb{F}_{q}$ with $|\mathcal{A}|=n$ and
$1<k<n$. It is obvious that the dimension of ${\rm
TRS}_{k}(\mathcal{A},\theta)$ is $k$. Note that ${\rm
TRS}_{k}(\mathcal{A},\theta)$ is contained in the Reed-Solomon code ${\rm
RS}_{k+1}(A)$, thus the minimum distance

$d({\rm TRS}_{k}(\mathcal{A},\theta))\geq d({\rm RS}_{k+1}(A))=n-k.$

From the definition, ${\rm TRS}_{k}(\mathcal{A},\theta)$ has a generator
matrix

$G=\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\alpha_{1}&\alpha_{2}&\cdots&\alpha_{n}\\\ \vdots&\vdots&\ddots&\vdots\\\
\alpha_{1}^{k-2}&\alpha_{2}^{k-2}&\cdots&\alpha_{n}^{k-2}\\\
\alpha_{1}^{k-1}+\theta\alpha_{1}^{k}&\alpha_{2}^{k-1}+\theta\alpha_{2}^{k}&\cdots&\alpha_{n}^{k-1}+\theta\alpha_{n}^{k}\\\
\end{array}\right).$

The covering radius of ${\rm TRS}_{k}(\mathcal{A},\theta)$ then can be easily
determined.

###### Theorem 4

The covering radius $\rho({\rm TRS}_{k}(\mathcal{A},\theta))$ of ${\rm
TRS}_{k}(\mathcal{A},\theta)$ is equal to $n-k$.

###### Proof:

Since $\dim_{\mathbb{F}_{q}}({\rm TRS}_{k}(\mathcal{A},\theta))=k$, by the
redundancy bound [2, Corollary 11.1.3], we have $\rho({\rm
TRS}_{k}(\mathcal{A},\theta))\leq n-k$. Note that ${\rm
TRS}_{k}(\mathcal{A},\theta)$ is a subcode of the Reed-Solomon code ${\rm
RS}_{k+1}(\mathcal{A})$, then by the supercode lemma [2, Lemma 11.1.5], we
have $\rho({\rm TRS}_{k}(\mathcal{A},\theta))\geq d({\rm
RS}_{k+1}(\mathcal{A}))=n-k$. The conclusion follows. ∎

An equivalent condition under which a vector is a deep hole of ${\rm
TRS}_{k}(\mathcal{A},\theta)$ is given as follows.

###### Proposition 5

Suppose $G$ is ae generator matrix of ${\rm TRS}_{k}(\mathcal{A},\theta)$ and
$\bm{u}\in\mathbb{F}^{n}_{q}$, then $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathcal{A},\theta)$ if and only if the matrix
$G^{\prime}=\left(\begin{array}[]{c}G\\\ \bm{u}\end{array}\right)$ generates
an $[n,k+1]$-MDS code over $\mathbb{F}_{q}$.

###### Proof:

For convenience, denote $C={\rm TRS}_{k}(\mathcal{A},\theta)$ and $C^{\prime}$
as the code generated by $G^{\prime}$. Then,
$d(C^{\prime})=\min\\{d(C),d(\bm{u},C)\\}$. By Theorem 4, it has $d(C)\geq
n-k=\rho(C)\geq d(\bm{u},C)$, hence $d(C^{\prime})=d(\bm{u},C)$. So,
$C^{\prime}$ is an $[n,k+1]$-MDS code over $\mathbb{F}_{q}$ if and only if
$d(\bm{u},C)=d(C^{\prime})=n-k$, which is equivalent to ${\bm{u}}$ is a deep
hole of $C$. ∎

By Proposition 5, we can obtain a class of deep holes of ${\rm
TRS}_{k}(\mathcal{A},\theta)$, which we call standard deep holes.

######  Theorem 5 (Standard Deep Holes)

Suppose $a\in\mathbb{F}^{*}_{q}$ , then the vector $\bm{u}_{f}$ with
generating polynomial $f(x)=ax^{k}+f_{k,\theta}(x)$, where
$f_{k,\theta}(x)\in\mathcal{S}_{k,\theta}$ given by Eq. (1), is a deep hole of
${\rm TRS}_{k}(\mathcal{A},\theta)$.

###### Proof:

By the definition of ${\rm TRS}_{k}(\mathcal{A},\theta)$, the vector with
generating polynomial $f_{k,\theta}(x)$ is a codeword of ${\rm
TRS}_{k}(\mathcal{A},\theta)$. Thus we only need to prove the theorem for the
case of $f(x)=ax^{k}$. At this moment, it is easy to see that
$\left(\begin{array}[]{c}G\\\ \bm{u}_{f}\end{array}\right)$ is row equivalent
to

$\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\alpha_{1}&\alpha_{2}&\cdots&\alpha_{n}\\\ \vdots&\vdots&\ddots&\vdots\\\
\alpha_{1}^{k-1}&\alpha_{2}^{k-1}&\cdots&\alpha_{n}^{k-1}\\\
\alpha_{1}^{k}&\alpha_{2}^{k}&\cdots&\alpha_{n}^{k}\\\ \end{array}\right),$

which generates the RS code ${\rm RS}_{k+1}(\mathcal{A})$. The conclusion then
follows from Proposition 5.

∎

##  IV On the completeness of Deep Holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$

In this section, we devote to presenting our main theorems on the completeness
of deep holes of ${\rm TRS}k(\mathbb{F}{q},\theta)$. The results will be
divided into two cases: when $q$ is even and when $q$ is odd. Before that, we
demonstrate a criterion for a vector to be a deep hole of a linear code.

###  IV-A The relation between deep hole and its syndrome

Firstly, we give some results on the deep hole of a linear code and its
syndrome. If $\bm{u}$ is a deep hole of a linear code $C$, then for any
$a\in\mathbb{F}^{*}_{q}$ and $\bm{c}\in C$, both of $a\bm{u}$ and
$\bm{u}+\bm{c}$ are deep holes. Suppose $H$ is a parity-check matrix of $C$.
Then $H\cdot(a\bm{u})^{\top}=aH\cdot\bm{u}^{\top}$ and
$H\cdot(\bm{u}+\bm{c})=H\cdot\bm{u}^{\top}$.

###### Proposition 6

Let $C$ be an $[n,k]$-linear code with a parity-check matrix $H$ and covering
radius $\rho(C)$. Suppose $\bm{u}\in\mathbb{F}^{n}_{q}$, then $\bm{u}$ is a
deep hole of $C$ if and only if $H\cdot\bm{u}^{\top}$ can not be expressed as
a linear combination of any $\rho(C)-1$ columns of $H$ over $\mathbb{F}_{q}$.

###### Proof:

$\bm{u}$ is not a deep hole if and only if $d(\bm{u},\bm{c})\leq\rho(C)-1$ for
some $\bm{c}\in C$. Denote $\bm{v}=\bm{u}-\bm{c}$. Since
$H\cdot\bm{c}=\bm{0}$, this is equivalent to
$H\cdot\bm{u}^{\top}=H\cdot\bm{v}^{\top}$ for some vector
$\bm{v}\in\mathbb{F}^{n}_{q}$ with $wt(\bm{v})\leq\rho(C)-1$, i.e.,
$H\cdot\bm{u}^{\top}$ is a linear combination of some $\rho(C)-1$ columns of
$H$ over $\mathbb{F}_{q}$. ∎

Suppose $\mathbb{F}_{q}=\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{q}\\}$. It is
easy to verify that ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ has a parity-check
matrix

$H=\left(\begin{array}[]{ccc}1&\cdots&1\\\ \alpha_{1}&\cdots&\alpha_{q}\\\
\vdots&\ddots&\vdots\\\ \alpha_{1}^{q-k-2}&\cdots&\alpha_{q}^{q-k-2}\\\
\alpha_{1}^{q-k-1}-\theta\alpha_{1}^{q-k}&\cdots&\alpha_{q}^{q-k-1}-\theta\alpha_{q}^{q-k}\\\
\end{array}\right).$ (3)

The following proposition will be utilized to determine the generating
polynomials of deep holes from their syndromes in our main theorems.

###### Proposition 7

Suppose ${\bm{w}}=(w_{0},w_{1},\cdots,w_{r-1})\in\mathbb{F}_{q}^{r}$ and $H$
is given by Eq. (3). Then, the solutions of the linear system
$H\cdot\bm{u}^{\top}=\bm{w}^{\top}$ are the vectors $\bm{u}_{f}$ generated by
$f(x)=\sum_{i=0}^{r-1}w_{i}x^{q-1-i}+f_{k,\theta}(x)$, where
$f_{k,\theta}(x)\in\mathcal{S}_{k,\theta}(x)$.

###### Proof:

It is sufficient to show $H\bm{u}^{\top}_{f}=\bm{w}^{\top}$ for
$f(x)=\sum_{i=0}^{r-1}w_{i}x^{q-1-i}$. This follows from the fact that for all
positive integer $j$, $\sum^{q}_{i=1}\alpha_{i}^{j}=1$ if $q-1\mid j$;
otherwise, it is equal to 0. ∎

###### Remark 1

From Proposition 7, determining the deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ is equivalent to determining their syndromes.

Throughout this paper, we denote $r=q-k$. In the following, we provide an
equivalent characterization of the deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ from the perspective of its syndrome.

###### Proposition 8

Suppose $\bm{u}\in\mathbb{F}^{q}_{q}$, then $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if
$\bm{c}_{r,\theta}(\alpha_{1}),\bm{c}_{r,\theta}(\alpha_{2}),\cdots,\bm{c}_{r,\theta}(\alpha_{r-1})$
and $H\cdot\bm{u}^{\top}$ are $\mathbb{F}_{q}$-linearly independent for any
distinct elements
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r-1}\in\mathbb{F}_{q}$.

###### Proof:

Note that the minimum distance $d({\rm TRS}_{k}(\mathbb{F}_{q}))\geq
q-k=\rho({\rm TRS}_{k}(\mathbb{F}_{q}))$. Thus any $\rho({\rm
TRS}_{k}(\mathbb{F}_{q}))-1=r-1$ columns of $H$ are linearly independent. Then
the conclusion immediately follows from Proposition 6. ∎

###  IV-B Deep Holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ for Even $q$

Inspired by the polynomial method proposed in [28], in this subsection, for
$q$ is even, we determine all deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ when $\frac{3q-8}{4}\leq k\leq q-1$.

For any $x_{1},x_{2},\cdots,x_{n}\in\mathbb{F}_{q}$, denote

$\prod\limits_{i=1}^{r-2}(X-x_{i})=\sum\limits_{i=0}^{n}S_{i}(x_{1},x_{2},\cdots,x_{n})X^{i},$

where $S_{i}(x_{1},\cdots,x_{n})=(-1)^{n-i}\sum\limits_{1\leq
j_{1}<j_{2}<\cdots<j_{n-i}\leq n}\prod\limits_{\ell=1}^{n-i}x_{j_{\ell}}$ for
all $0\leq i\leq n$.

Let $\bm{w}=(w_{0},w_{1},\cdots,w_{r-1})\in\mathbb{F}^{r}_{q}$. Denote

$f=f(x_{1},\cdots,x_{r-2})=\sum\limits_{i=0}^{r-2}w_{i}S_{i}(x_{1},\cdots,x_{r-2}),$
$g=g(x_{1},\cdots,x_{r-2})=\sum\limits_{i=1}^{r-2}w_{i}S_{i-1}(x_{1},\cdots,x_{r-2}),$

and

$h=h(x_{1},\dots,x_{r-2})=\sum_{i=2}^{r-2}w_{i}S_{i-2}(x_{1},\cdots,x_{r-2})+\theta^{-1}w_{r-1}.$

From Proposition 8, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if
$\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r-1})|\bm{w}^{\top}\big{)}\neq
0$ for any distinct elements
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r-1}\in\mathbb{F}_{q}$, where
$\bm{w}^{\top}=H\cdot\bm{u}^{\top}$. Thus we will regard these elements
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r-1}$ as variables
$x_{1},x_{2},\cdots,x_{r-1}$, and give a formula of
$\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}$
as follows.

###### Lemma 4

With the notations above, we have

$\frac{\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}}{\theta
V(x_{1},x_{2},\cdots,x_{r-1})}=f\cdot
x^{2}_{r-1}+\big{(}\theta^{-1}+\sum_{i=1}^{r-2}x_{i}\big{)}f\cdot
x_{r-1}+\big{(}\theta^{-1}+\sum_{i=1}^{r-2}x_{i}\big{)}g+h.$

###### Proof:

By Lemma 3 and ${\rm Char}(\mathbb{F}_{q})=2$,

$\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{c}_{r,\theta}(X)\big{)}\\\
=V(x_{1},x_{2},\cdots,x_{r-1})\prod_{j=1}^{r-1}(X+x_{j})\big{(}1+\theta(X+\sum_{i=1}^{r-1}x_{i})\big{)}.$

For convenience, denote $S_{i,n}=S_{i}(x_{1},\cdots,x_{n})$. Then we have

$\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2}),|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}=\theta
V(x_{1},x_{2},\cdots,x_{r-1})\big{(}\sum_{i=0}^{r-2}w_{i}D_{i}+\theta^{-1}w_{r-1}\big{)},$

where $D_{i}$ is the coefficient of $X^{i}$ in
$\prod\limits_{j=1}^{r-1}(X+x_{j})\big{(}X+\sum\limits_{t=1}^{r-1}x_{t}+\theta^{-1}\big{)}$,
i.e.,
$D_{i}=S_{i,r-1}\big{(}\theta^{-1}+\sum\limits_{t=1}^{r-1}x_{t}\big{)}+S_{i-1,r-1}.$
Note that

$S_{\ell,r-1}=x_{r-1}S_{\ell,r-2}+S_{\ell-1,r-2}.$

Thus

$\displaystyle D_{i}$ $\displaystyle=$
$\displaystyle(x_{r-1}S_{i,r-2}+S_{i-1,r-2})\big{(}x_{r-1}+\sum_{t=1}^{r-2}x_{t}+\theta^{-1}\big{)}+(x_{r-1}S_{i-1,r-2}+S_{i-2,r-2})$
$\displaystyle=$ $\displaystyle
S_{i,r-2}x^{2}_{r-1}+(\theta^{-1}+\sum_{t=1}^{r-2}x_{t})S_{i,r-2}x_{r-1}+S_{i-1,r-2}(\theta^{-1}+\sum_{t=1}^{r-2}x_{t})+S_{i-2,r-2}.$

Therefore,

$\displaystyle\frac{\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}}{\theta
V(x_{1},x_{2},\cdots,x_{r-1})}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{r-2}w_{i}\big{(}S_{i,r-2}x^{2}_{r-1}+(\theta^{-1}+\sum_{t=1}^{r-2}x_{t})S_{i,r-2}x_{r-1}+S_{i-1,r-2}(\theta^{-1}+\sum_{i=t}^{r-2}x_{t})+S_{i-2,r-2}\big{)}+\theta^{-1}w_{r-1}$
$\displaystyle=$ $\displaystyle
fx^{2}_{r-1}+(\theta^{-1}+\sum_{i=1}^{r-2}x_{i})(fx_{r-1}+g)+h.$

∎

From Lemma 4 and Proposition 8, we provide a necessary condition under which
$\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.

Denote
$\tilde{f}=f(x_{1},\cdots,x_{r-3},\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1}),\tilde{h}=h(x_{1},\cdots,x_{r-3},\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})$.

###### Lemma 5

Suppose $r-3\geq 1$, i.e., $k\leq q-4$. Let $\bm{u}\in\mathbb{F}^{n}_{q}$ and
$\bm{w}^{\top}=(w_{0},w_{1},\cdots,w_{r-1})^{\top}=H\cdot\bm{u}^{\top}\in\mathbb{F}^{r}_{q}$.
If $\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$, then the
polynomial

$P(x_{1},\cdots,x_{r-3})=V(x_{1},\cdots,x_{r-3})\cdot\prod_{t=1}^{r-3}\big{(}\sum_{j=1}^{r-3}x_{j}+\theta^{-1}+x_{t}\big{)}\cdot\tilde{f}\cdot\prod_{i=1}^{r-3}\big{(}\tilde{f}x_{i}^{2}+\tilde{h}\big{)}\cdot\big{(}\tilde{f}(\sum_{j=1}^{r-3}x_{j}+\theta^{-1})^{2}+\tilde{h}\big{)}\in\mathbb{F}_{q}[x_{1},x_{2},\cdots,x_{r-3}]$

vanishes on
$\underbrace{\mathbb{F}_{q}\times\mathbb{F}_{q}\times\cdots\times\mathbb{F}_{q}}_{r-3}.$

###### Proof:

For any $x_{1},\cdots,x_{r-3}\in\mathbb{F}_{q}$, if $x_{i}=x_{j}$ for some
$1\leq i<j\leq r-3$, then $V(x_{1},x_{2},\cdots,x_{r-3})=0$. If
$\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1}+x_{t}=0$ for some $1\leq t\leq r-3$,
then
$\prod\limits_{t=1}^{r-3}(\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1}+x_{t})=0$.
Thus we let

$x_{r-2}=\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1},$

and we may suppose $x_{1},x_{2},\cdots,x_{r-2}$ are pairwise distinct. If
$\tilde{f}=0$, we are done. So we assume that $\tilde{f}\neq 0$. Since
$\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$, by
Proposition 8, we have
$\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}\neq
0$ for any distinct elements $x_{1},x_{2},\cdots,x_{r-1}\in\mathbb{F}_{q}$.
From $\sum\limits_{j=1}^{r-2}x_{j}+\theta^{-1}=0$ and Lemma 4, we obtain that

$\frac{\det\big{(}\bm{c}_{r,\theta}(x_{1})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}}{\theta
V(x_{1},x_{2},\cdots,x_{r-1})}=\tilde{f}x^{2}_{r-1}+\tilde{h}.$

Thus $\tilde{f}x^{2}_{r-1}+\tilde{h}\neq 0$ for any
$x_{r-1}\in\mathbb{F}_{q}\backslash\\{x_{1},x_{2},\cdots,x_{r-2}\\}$. Since
$\mathbb{F}_{q}$ has characteristic 2, the equation
$\tilde{f}X^{2}+\tilde{h}=0$ has a unique solution $X\in\mathbb{F}_{q}$. Thus
we can deduce that the solution can only be one of $x_{1},\cdots,x_{r-2}$,
i.e., $\tilde{f}x_{i}^{2}+\tilde{h}=0$ for some $1\leq i\leq r-2$, that is,

$\prod_{i=1}^{r-3}(\tilde{f}x_{i}^{2}+\tilde{h})\big{(}\tilde{f}(\sum_{j=1}^{r-3}x_{j}+\theta^{-1})^{2}+\tilde{h}\big{)}=0.$

∎

The following lemma will be used in the discussion of the proof of Theorem 7.

###### Lemma 6

Suppose $q=2^{m}\geq 8$ and $\frac{3q-8}{4}\leq k\leq q-4$. Let
$\bm{u}\in\mathbb{F}^{q}_{q}$,

$\bm{w}^{\top}=H\cdot\bm{u}^{\top}=(0,\cdots,0,w_{r-3},w_{r-2},w_{r-1})$

with $w_{r-3}\neq 0$ and $w_{r-3}\theta+w_{r-2}=0$, then $\bm{u}$ is not a
deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.

###### Proof:

The proof please refer to Appendix A. ∎

The following is the well-known Schwartz-Zippel Lemma [29, 30, 31].

######  Lemma 7 (Schwartz-Zippel Lemma [29, 30, 31])

Let $F(x_{1},\cdots,x_{n})$ be a polynomial over $\mathbb{F}_{q}$. If
$\deg_{x_{i}}(F)<q$, for any $1\leq i\leq n$, then there exists
$\alpha_{1},\cdots,\alpha_{n}\in\mathbb{F}_{q}$ such that
$F(\alpha_{1},\cdots,\alpha_{n})=0$.

By the Lemmas 5 and 6, the Schwartz-Zippel Lemma, we can obtain our main
result as follows.

###### Theorem 6

Suppose $q=2^{m}\geq 8$. If $\frac{3q-8}{4}\leq k\leq q-4$, then Theorem 5
provides all deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.

###### Proof:

Suppose $\bm{u}\in\mathbb{F}^{q}_{q}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$. Denote $\bm{w}^{\top}=H\cdot\bm{u}^{\top}$,
where $H$ is the parity-check matrix of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
given in Eq. (3). By Lemma 5, the polynomial
$P(x_{1},\cdots,x_{r-3})\in\mathbb{F}_{q}[x_{1},x_{2},\cdots,x_{r-3}]$
vanishes on
$\underbrace{\mathbb{F}_{q}\times\mathbb{F}_{q}\times\cdots\times\mathbb{F}_{q}}_{r-3}.$
Note that $\deg_{x_{i}}(P)=(r-4)+2+(r-4)+(4+2(r-4))+4=4(q-k)-10<q$. By the
Schwartz-Zippel Lemma, we have $P(x_{1},\cdots,x_{r-3})\equiv 0$. We divide
our discussion into 3 cases.

_Case 1_ : $\tilde{f}\equiv 0$, i.e.,
$\sum\limits_{i=0}^{r-2}w_{i}S_{i}(x_{1},\cdots,x_{r-3},\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})\equiv
0$. For each $0\leq i\leq r-4$, the coefficient of the term
$x_{1}\prod\limits_{j=1}^{r-3-i}x_{j}$ in
$\sum\limits_{i=0}^{r-2}w_{i}S_{i}(x_{1},\cdots,x_{r-3},\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})$
is equal to $w_{i}$, which implies that $w_{0}=w_{1}=\cdots=w_{r-4}=0$ and
$w_{r-3}\theta^{-1}+w_{r-2}=0$.

If $w_{r-3}=0$, then $w_{r-2}=0$. We deduce that $w_{r-1}\neq 0,$ otherwise,
we have $\bm{w}=\bm{0}$, which implies that $\bm{u}\in{\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$, not a deep hole. Thus
$\bm{w}=(0,0,\cdots,0,w_{r-1})$ with $w_{r-1}\in\mathbb{F}^{*}_{q}$.

If $w_{r-3}\neq 0,$ by Lemma 6, $\bm{u}$ cannot be a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$.

_Case 2_ : $\tilde{f}x_{i}^{2}+\tilde{h}\equiv 0$ for some $1\leq i\leq r-3$.
Note that $\tilde{f}$ and $\tilde{h}$ are symmetric polynomials. Thus
$\tilde{f}=\tilde{h}\equiv 0$ or $r-3=1$. If $\tilde{f}=\tilde{h}\equiv 0$,
then from Case 1, we have $w_{0}=w_{1}=\cdots=w_{r-4}=0$. Similarly,
$\tilde{h}\equiv 0$ implies that $w_{2}=w_{3}=\cdots=w_{r-1}=0$. Thus
$\bm{w}=\bm{0}$; If $r-3=1$, we have

$\tilde{f}=w_{0}S_{0}(x_{1},x_{1}+\theta^{-1})+w_{1}S_{1}(x_{1},x_{1}+\theta^{-1})+w_{2}S_{2}(x_{1},x_{1}+\theta^{-1})=w_{0}x^{2}_{1}+\theta^{-1}w_{0}x_{1}+\theta^{-1}w_{1}+w_{2},$
$\tilde{h}=w_{2}x^{2}_{1}+\theta^{-1}w_{2}x_{1}+w_{3}\text{ and
}\tilde{f}x_{1}^{2}+\tilde{h}\equiv 0.$

It deduces that $w_{0}=w_{1}=w_{2}=w_{3}=0$. So, in this case, we have
$\bm{w}=\bm{0}$. i.e., $\bm{u}\in{\rm TRS}_{k}(\mathbb{F}_{q},\theta)$, which
is not a deep hole.

_Case 3_ :
$\tilde{f}(\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})^{2}+\tilde{h}\equiv 0.$
Note that for $0\leq j\leq r-4$, the coefficient of the term
$x_{1}^{2}\cdot(\prod\limits_{\ell=1}^{r-3-j}x_{\ell})\cdot x_{1}$ in
$\tilde{f}(\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})^{2}+\tilde{h}$ is
$w_{j}$, thus $w_{j}=0$ for $j=0,1,\cdots,r-4$. Combining with the definitions
of $\tilde{f}$ and $\tilde{h}$, it has that

$(\sum\limits_{j=1}^{r-3}x^{2}_{j}+\theta^{-2})(w_{r-3}\theta^{-1}+w_{r-2})+w_{r-3}S_{r-5}(x_{1},\cdots,x_{r-3},\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})+w_{r-2}S_{r-4}(x_{1},\cdots,x_{r-3},\sum\limits_{j=1}^{r-3}x_{j}+\theta^{-1})+w_{r-1}\equiv
0.$

As a result, the coefficient of $x_{1}^{2}$ is $w_{r-3}\theta^{-1}$, which
implies that $w_{r-3}=0$. Then it can easily deduce that $w_{r-2}=w_{r-1}=0$.
Hence we obtain that $\bm{w}=\bm{0}$, i.e., $\bm{u}$ is a codeword, not a deep
hole.

In a word, we deduce that
$\bm{w}^{\top}=H\cdot\bm{u}^{\top}=a(0,0,\cdots,0,1)^{\top}$ with
$a\in\mathbb{F}^{*}_{q}$. The conclusion then follows by Proposition 7. ∎

Finally, we determine all deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
for even $q\geq 8$ and $q-3\leq k\leq q-1$.

###### Theorem 7

Suppose $q=2^{m}\geq 8$. Let $\bm{u}\in\mathbb{F}^{q}_{q}$ and
$\bm{w}=H\cdot\bm{u}^{\top}=(w_{0},w_{1},\cdots,w_{q-k-1})^{\top}$, where $H$
is the parity-check matrix of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ given in
Eq. (3).

(i) For $k=q-1$, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is generated by
Theorem 5.

(ii) For $k=q-2$, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is generated by
$w_{0}x^{q-1}+w_{1}x^{q-2}+f_{q-2,\theta}(x)$ with $w_{0}=0,w_{1}\neq 0$ or
$w_{0}\neq 0$ and ${\rm Tr}(\frac{w_{1}\theta}{w_{0}})=1$, where ${\rm Tr}(x)$
is the trace function from $\mathbb{F}_{q}$ to $\mathbb{F}_{2}$.

(iii) For $k=q-3$, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if $\bm{u}$ is given by Theorem 5
or generated by $a(x^{q-2}+\theta^{-1}x^{q-3})+f_{q-3,\theta}(x)$ with $a\neq
0$, $f_{q-3,\theta}(x)\in\mathcal{S}_{q-3,\theta}$ and $2\nmid m$.

###### Proof:

(i): For $k=q-1$, then $\rho({\rm TRS}_{k}(\mathbb{F}_{q},\theta))=q-k=1$.
Thus every non-codeword is a deep hole. The conclusion can be easily verified.

(ii): For $k=q-2$, then by Proposition 8, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if for any
$\alpha\in\mathbb{F}_{q}$.

$\det\left(\begin{array}[]{cc}1&w_{0}\\\ \alpha+\theta\alpha^{2}&w_{1}\\\
\end{array}\right)=\theta w_{0}\alpha^{2}+w_{0}\alpha+w_{1}\neq 0,$ (4)

where $(w_{0},w_{1})^{\top}=H{\bm{u}}^{\top}$. Hence, Eq. (4) holds
$\Longleftrightarrow w_{0}=0,w_{1}\neq 0$, or, $w_{0}\neq 0$ and $\theta
w_{0}x^{2}+w_{0}x+w_{1}=0$ has no roots in $\mathbb{F}_{q}$. By [32, Corollary
3.79], the latter one is equivalent to ${\rm
Tr}(\frac{w_{1}\theta}{w_{0}})=1$.

Furthermore, given $w_{0},w_{1}$ with $w_{0}=0,w_{1}\neq 0$ or $w_{0}\neq 0$
and ${\rm Tr}(\frac{w_{1}\theta}{w_{0}})=1$, it can be verified that the
vector $\bm{u}_{f}$ generated by
$f(x)=w_{0}x^{q-1}+w_{1}x^{q-2}+f_{q-2,\theta}(x)$ satisfies
$H\cdot\bm{u}^{\top}_{f}=(w_{0},w_{1})$. Thus such vectors are all deep holes
of ${\rm TRS}_{q-2}(\mathbb{F}_{q},\theta)$.

(iii):  For $k=q-3$, then by Proposition 8, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if

$D(\alpha,\beta)=\frac{\det\left(\begin{array}[]{ccc}1&1&w_{0}\\\
\alpha&\beta&w_{1}\\\
\alpha^{2}+\theta\alpha^{3}&\beta^{2}+\theta\beta^{3}&w_{2}\\\
\end{array}\right)}{\alpha+\beta}\neq 0,$

for any $\alpha\neq\beta\in\mathbb{F}_{q}$, where
$\bm{w}=(w_{0},w_{1},w_{2})^{\top}=H{\bm{u}}^{\top}$. W.l.o.g., we suppose
$\alpha\neq 0$ and $\beta=\lambda\alpha$, then for any $\alpha\neq
0\in\mathbb{F}_{q}$ and $\lambda\neq 1\in\mathbb{F}_{q}$,

$\tilde{D}(\alpha,\lambda)\triangleq
D(\alpha,\lambda\alpha)=(w_{0}\alpha+w_{1})\theta\alpha^{2}\lambda^{2}+(w_{0}\alpha+w_{1})\cdot\alpha(1+\theta\alpha)\lambda+w_{1}\alpha(1+\theta\alpha)+w_{2}\neq
0.$ (5)

Next, we determine all vectors
$\bm{w}^{\top}\in\mathbb{F}_{q}^{3}\setminus\\{\bm{0}\\}$ that satisfy (5).

_Case 1_ : $w_{0}=0$ and $w_{1}=0$. Then $\tilde{D}(\alpha,\lambda)=w_{2}\neq
0$, i.e., (5) holds.

_Case 2_ : $w_{0}=0$ and $w_{1}\neq 0$, then (5) holds if and only if
$w_{2}=\theta^{-1}w_{1}$ with $2\nmid m$.

When $w_{2}=0$, it has $w_{2}=\tilde{D}(\theta^{-1},0)=0$. When $w_{2}\neq 0$
and $2\mid m$, then $\tilde{D}(\frac{w_{2}\omega}{w_{1}},\omega)=0$, where
$\omega$ is the primitive cubic root of unity. When $w_{2}\neq 0$ and $2\nmid
m$, (5) holds if and only if
$\frac{w_{2}}{w_{1}}\neq\theta\alpha^{2}\lambda^{2}+\alpha(1+\theta\alpha)(\lambda+1)$
for any $\alpha\neq 0$ and $\lambda\neq 1$. Let $\alpha=\theta^{-1}$, then
$\frac{w_{2}}{w_{1}}\neq\frac{\lambda^{2}}{\theta}$ for any $\lambda\neq 1$.
Thus (5) holds implies that $\frac{w_{2}}{w_{1}}=\theta^{-1}$. Conversely, let
$\frac{w_{2}}{w_{1}}=\theta^{-1}$, we show that for any $\alpha\neq 0$ and
$\lambda\neq 1$,
$\theta\alpha^{2}\lambda^{2}+\alpha(1+\theta\alpha)(\lambda+1)\neq\theta^{-1}$.
By contradiction, if
$\theta\alpha^{2}\lambda^{2}+\alpha(1+\theta\alpha)(\lambda+1)=\theta^{-1}$
for some $\alpha\neq 0$ and $\lambda\neq 1$. Then $1+\theta\alpha\neq 0$,
otherwise, we can deduce from the equation that $\lambda=1$. Then we obtain
that

$\theta^{2}\alpha^{2}\lambda^{2}+\theta\alpha(1+\theta\alpha)\lambda+\theta\alpha(1+\theta\alpha)+1=0,$

i.e.,

$(\frac{\theta\alpha\lambda}{1+\theta\alpha})^{2}+\frac{\theta\alpha\lambda}{1+\theta\alpha}+\frac{1+\theta\alpha+\theta^{2}\alpha^{2}}{1+\theta^{2}\alpha^{2}}=0.$

Hence ${\rm
Tr}(\frac{1+\theta\alpha+\theta^{2}\alpha^{2}}{1+\theta^{2}\alpha^{2}})={\rm
Tr}(1+\frac{\theta\alpha}{1+\theta^{2}\alpha^{2}})=0.$ Note that ${\rm
Tr}(1)=1$ and ${\rm Tr}(\frac{\theta\alpha}{1+\theta^{2}\alpha^{2}})={\rm
Tr}(\frac{1}{1+\theta\alpha}+\frac{1}{(1+\theta\alpha)^{2}})=0$, which is a
contradiction.

_Case 3_ : $w_{0}\neq 0$ and $w_{1}=0$, then (5) doesn’t hold.

Otherwise,
$\frac{w_{2}}{w_{0}}\neq\lambda\alpha^{2}(1+\theta\alpha(1+\lambda))$ for any
$\alpha\neq 0$ and $\lambda\neq 1$. Choose $\alpha=\theta^{-1}$, then
$\frac{w_{2}}{w_{0}}\neq\frac{\lambda^{2}}{\theta^{2}}$ for any $\lambda\neq
1$. Thus $\frac{w_{2}}{w_{0}}=\frac{1}{\theta^{2}}$. Next we will show that
there exist $\alpha\neq 0$ and $\lambda\neq 1$ such that
$\lambda\alpha^{2}(1+\theta\alpha(1+\lambda))=\frac{1}{\theta^{2}}$ which
leads to a contradiction. Note that the above equation is equivalent to
$(\theta\alpha\lambda)^{2}+(\theta\alpha\lambda)+\frac{1}{(1+\theta\alpha)^{2}\theta\alpha}=0.$
By [32, Corollary 3.79], it is equivalent to ${\rm
Tr}(\frac{1}{(1+\theta\alpha)^{2}\theta\alpha})=0$. Note that

${\rm Tr}(\frac{1}{(1+\theta\alpha)^{2}\theta\alpha})={\rm
Tr}(\frac{1}{\theta\alpha}+\frac{1}{1+\theta\alpha}+(\frac{1}{1+\theta\alpha})^{2})={\rm
Tr}(\frac{1}{\theta\alpha}).$

Thus when $q\geq 8$, we can always choose
$\alpha\in\mathbb{F}_{q}\backslash\\{0,\theta^{-1}\\}$ such that ${\rm
Tr}(\frac{1}{\theta\alpha})=0$.

_Case 4_ : $w_{0}\neq 0$ and $w_{2}=0$, then (5) doesn’t hold.

Otherwise,
$\frac{w_{1}}{w_{0}}\neq\frac{1+\lambda+\theta\alpha(1+\lambda+\lambda^{2})}{\lambda\alpha(1+\theta\alpha(1+\lambda))}$
for any $\alpha\neq 0$ and $\lambda\neq 1$. Take $\theta\alpha\lambda=1$
($\alpha\in\mathbb{F}_{q}\backslash\\{0,\theta^{-1}\\}$, then
$\frac{w_{1}}{w_{0}}\neq\frac{1}{\theta\alpha^{2}}$. Thus
$\frac{w_{1}}{w_{0}}=\theta$. On the other hand, take $\alpha=\theta^{-1}$,
then $\frac{w_{1}}{w_{0}}\neq\frac{1}{\alpha}=\theta$, which is a
contradiction.

_Case 5_ : $w_{0},w_{1},w_{2}\neq 0$, then (5) doesn’t hold.

W.l.o.g., we suppose $w_{0}=1$. We will show that there always exists
$\alpha\neq 0$ and $\lambda\neq 1$ such that $\tilde{D}(\alpha,\lambda)=0$.

If $w_{1}\neq\theta^{-1}$ and $w_{2}\neq\theta^{-1}(w_{1}+\theta^{-1})$, we
choose $\alpha=\theta^{-1}$, then
$\tilde{D}(\alpha,\lambda)=\theta^{-1}(w_{1}+\theta^{-1})\lambda^{2}+w_{2}$.
Obviously, there exists $\lambda\neq 1\in\mathbb{F}_{q}$ such that
$\tilde{D}(\alpha,\lambda)=0$.

If $w_{1}\neq\theta^{-1}$ and $w_{2}=\theta^{-1}(w_{1}+\theta^{-1})$, then
$\tilde{D}(\alpha,\lambda)=(\alpha+w_{1})\theta\alpha^{2}\lambda^{2}+(\alpha+w_{1})\alpha(1+\theta\alpha)\lambda+w_{1}\alpha(1+\theta\alpha)+\theta^{-1}(w_{1}+\theta^{-1}).$
We suppose $\alpha\neq 0,w_{1},\theta^{-1}$, then by [32, Corollary 3.79],
$\tilde{D}(\alpha,\lambda)=0$ has a solution $\lambda\neq 1\in\mathbb{F}_{q}$
if and only if

$\displaystyle{\rm
Tr}(\frac{w_{1}\alpha(1+\theta\alpha)+\theta^{-1}(w_{1}+\theta^{-1})}{(\alpha+w_{1})(1+\theta\alpha)^{2}})$
$\displaystyle=$ $\displaystyle{\rm
Tr}(\frac{\theta^{-1}(1+w_{1}\theta)(1+\theta^{2}\alpha^{2})+\theta\alpha(w_{1}+\alpha)}{(\alpha+w_{1})(1+\theta\alpha)^{2}})$
$\displaystyle=$ $\displaystyle{\rm
Tr}(\frac{1+w_{1}\theta}{\theta(\alpha+w_{1})})+{\rm
Tr}(\frac{1}{1+\theta\alpha})+{\rm Tr}(\frac{1}{(1+\theta\alpha)^{2}})$
$\displaystyle=$ $\displaystyle{\rm
Tr}(\frac{1+w_{1}\theta}{\theta(\alpha+w_{1})})=0.$

When $q\geq 8$, we can choose
$\alpha\in\mathbb{F}_{q}\backslash\\{0,u_{1},\theta^{-1}\\}$ such that ${\rm
Tr}(\frac{1+w_{1}\theta}{\theta(\alpha+w_{1})})=0$.

If $w_{1}=\theta^{-1}$, then
$\tilde{D}(\alpha,\lambda)=\alpha^{2}(1+\theta\alpha)\lambda^{2}+\frac{\alpha(1+\theta\alpha)^{2}}{\theta}\lambda+\frac{\alpha(1+\theta\alpha)}{\theta}+w_{2}$.
When ${\rm Tr}(w_{2}\theta^{2})=0$, then we can choose
$\alpha\in\mathbb{F}_{q}$ such that
$\frac{\alpha(1+\theta\alpha)}{\theta}+w_{2}=0$ and $\tilde{D}(\alpha,0)=0$.
When ${\rm Tr}(w_{2}\theta)=1$, we suppose $\alpha\neq 0,\theta^{-1}$, then
$\tilde{D}(\alpha,\lambda)=0$ has a solution $\lambda\neq 1\in\mathbb{F}_{q}$
if and only if

${\rm
Tr}(\frac{\alpha\theta(1+\theta\alpha)+w_{2}\theta^{2}}{(1+\theta\alpha)^{3}})={\rm
Tr}(\frac{\theta\alpha}{(1+\theta\alpha)^{2}})+{\rm
Tr}(\frac{w_{2}\theta^{2}}{(1+\theta\alpha)^{3}})={\rm
Tr}(\frac{w_{2}\theta^{2}}{(1+\theta\alpha)^{3}})=0.$

Let $\gamma=\frac{1}{1+\theta\alpha}$, then
$\gamma\in\mathbb{F}_{q}\backslash\\{0,1\\}$. If $3\nmid q-1$, then $x^{3}$ is
a permutation polynomial of $\mathbb{F}_{q}$. Thus we can always choose
$\gamma\in\mathbb{F}_{q}\backslash\\{0,1\\}$ such that ${\rm
Tr}(w_{2}\theta^{2}\gamma^{3})=0$ for $q\geq 8$. If $3\mid q-1$, to obtain a
contradiction, we suppose ${\rm Tr}(w_{2}\theta^{2}\gamma^{3})=1$ for any
$\gamma\in\mathbb{F}_{q}\backslash\\{0,1\\}$. Then

$\displaystyle-(q-2)$ $\displaystyle=$
$\displaystyle\sum_{\gamma\in\mathbb{F}_{q}\backslash\\{0,1\\}}(-1)^{{\rm
Tr}(w_{2}\theta\gamma^{3})}$ $\displaystyle=$
$\displaystyle\sum_{\gamma\in\mathbb{F}_{q}}(-1)^{{\rm
Tr}(w_{2}\theta\gamma^{3})}-1-(-1)^{{\rm Tr}(w_{2}\theta)}$ $\displaystyle=$
$\displaystyle\sum_{\gamma\in\mathbb{F}_{q}}(-1)^{{\rm
Tr}(w_{2}\theta\gamma^{3})}.$

By Proposition 2, we have $|\sum\limits_{\gamma\in\mathbb{F}_{q}}(-1)^{{\rm
Tr}(w_{2}\theta\gamma^{3})}|\leq 2\sqrt{q}$, which leads to $q-2\leq
2\sqrt{q}\Longrightarrow q<8$, contradiction.

In short, $\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ if
and only if $\bm{w}=a(0,0,1)$ or $\bm{w}=a(0,1,\theta^{-1})$ when $2\mid m$,
where $a\in\mathbb{F}^{*}_{q}$. Then the conclusion follows by Proposition 7.
∎

###  IV-C Deep Holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ for Odd $q$

In Subsection IV-B, a key point of our proof was that the determinant
$\frac{\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}}{\theta
V(x_{1},x_{2},\cdots,x_{r-1})}$ can be viewed as a quadratic polynomial in
$x_{r-1}$, which has a solution under certain conditions when $q$ is even.
However, this approach does not apply to the case where $q$ is odd. Therefore,
in this subsection, we will adopt a different method to handle it. For $q$ is
odd, we will determine all deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ when $\frac{3q+2\sqrt{q}-7}{4}\leq k\leq
q-1$.

Firstly, we treat it with the case $\frac{3q+2\sqrt{q}-7}{4}\leq k\leq q-4$.
We start with two lemmas which will be used in the proof of our main theorem.

###### Lemma 8

Suppose $q$ is odd and $4\leq r\leq\frac{q+8}{4}$. For any
$\lambda\in\mathbb{F}_{q}$, denote
$\bm{v}=(0,0,\cdots,0,1,\lambda)\in\mathbb{F}^{r}_{q}$. Then there exist
pairwise distinct elements
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r-1}\in\mathbb{F}_{q}$ such that

$\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r-1})|\bm{v}^{\top}\big{)}=0.$

###### Proof:

By Lemmas 2 and 3, we have

$\displaystyle\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r-1})|\bm{v}\big{)}$
$\displaystyle=$
$\displaystyle\lambda\det\left(\begin{array}[]{ccc}1&\cdots&1\\\
\alpha_{1}&\cdots&\alpha_{r-1}\\\ \vdots&\ddots&\vdots\\\
\alpha_{1}^{r-2}&\cdots&\alpha_{r-1}^{r-2}\\\
\end{array}\right)-\det\left(\begin{array}[]{ccc}1&\cdots&1\\\
\alpha_{1}&\cdots&\alpha_{r-1}\\\ \vdots&\ddots&\vdots\\\
\alpha_{1}^{r-3}&\cdots&\alpha_{r-1}^{r-3}\\\
\alpha_{1}^{r-1}&\cdots&\alpha_{r-1}^{r-1}\\\
\end{array}\right)+\theta\cdot\det\left(\begin{array}[]{ccc}1&\cdots&1\\\
\alpha_{1}&\cdots&\alpha_{r-1}\\\ \vdots&\ddots&\vdots\\\
\alpha_{1}^{r-3}&\cdots&\alpha_{r-1}^{r-3}\\\
\alpha_{1}^{r}&\cdots&\alpha_{r-1}^{r}\\\ \end{array}\right)$ $\displaystyle=$
$\displaystyle\theta
V(\alpha_{1},\cdots,\alpha_{r-1})\big{(}\theta^{-1}\lambda+\sum\limits_{1\leq
i\leq j\leq
r-1}\alpha_{i}\alpha_{j}-\theta^{-1}\sum\limits_{i=1}^{r-1}\alpha_{i}\big{)}.$

Denote $\beta_{0}=\sum\limits_{1\leq i\leq j\leq
r-4}\alpha_{i}\alpha_{j},\beta_{1}=\sum\limits_{i=1}^{r-4}\alpha_{i},b=-\alpha^{2}_{r-3}+(\theta^{-1}-\beta_{1})\alpha_{r-3}+(\theta^{-1}\beta_{1}-\theta^{-1}\lambda-\beta_{0}),X=\frac{\alpha_{r-2}+\alpha_{r-1}}{2},$
and $Y=\frac{\alpha_{r-2}-\alpha_{r-1}}{2}$. Then

$\theta^{-1}\lambda+\sum\limits_{1\leq i\leq j\leq
r-1}\alpha_{i}\alpha_{j}-\theta^{-1}\sum\limits_{i=1}^{r-1}\alpha_{i}=3X^{2}+Y^{2}-2(\theta^{-1}-\beta_{1}-\alpha_{r-3})X-b.$

Thus it is sufficient to show that there exists
$\alpha_{r-3}\in\mathbb{F}_{q}\setminus\\{\alpha_{1},\cdots,\alpha_{r-4}\\}$
such that the equation

$F(X,Y)=3X^{2}+Y^{2}-2(\theta^{-1}-\beta_{1}-\alpha_{r-3})X-b=0$ (7)

has a solution $(X,Y)\in\mathbb{F}_{q}^{2}$ and
$\\{\alpha_{1},\cdots,\alpha_{r-4},\alpha_{r-3},X+Y,X-Y\\}$ are all distinct.

Note that ${\rm N}(F(X,X-\alpha_{i}))\leq 2,{\rm N}(F(X,\alpha_{i}-X))\leq 2$
for all $1\leq i\leq r-3$ and ${\rm N}(F(X,0))\leq 2$, so we only need to show
that there exists
$\alpha_{r-3}\in\mathbb{F}_{q}\setminus\\{\alpha_{1},\cdots,\alpha_{r-4}\\}$
such that ${\rm N}(F(X,Y))>4(r-3)+2=4r-10$.

When $\rm Char({\mathbb{F}_{q}})=3$, since $q>r-3$, we choose
$\alpha_{r-3}\in\mathbb{F}_{q}\setminus\\{\alpha_{1},\cdots,\alpha_{r-4},\theta^{-1}-\beta_{1}\\}$.
Combining with (7), it has ${\rm N}(F(X,Y))=q\geq 4r-8>4r-10$. When $\rm
Char({\mathbb{F}_{q}})>3$,
$|\mathbb{F}_{q}\setminus\\{\alpha_{1},\cdots,\alpha_{r-4}\\}|=q-r+4>2$, so we
may choose
$\alpha_{r-3}\in\mathbb{F}_{q}\setminus\\{\alpha_{1},\cdots,\alpha_{r-4}\\}$
such that $\tilde{b}\triangleq
b+\frac{(\theta^{-1}-\beta_{1}-\alpha_{r-3})^{2}}{3}\neq 0$. Moreover,
$F(X,Y)$ in equation (7) can be rewritten as

$F(X,Y)=3(X-\frac{\theta^{-1}-\beta_{1}-\alpha_{r-3}}{3})^{2}+Y^{2}-\tilde{b}.$

By Proposition 4, it has that ${\rm N}(F(X,Y))\geq q-1\geq 4r-9>4r-10$.∎

###### Lemma 9

Suppose $3\leq r\leq\frac{q-2\sqrt{q}+7}{4}$. Given any subset
$\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{r-2}\\}\subseteq\mathbb{F}_{q}$ and
$b\in\mathbb{F}_{q}$, there exist
$\alpha_{r-1}\neq\alpha_{r}\in\mathbb{F}_{q}\backslash\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{r-2}\\}$
such that

$\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})+b\bm{c}_{r}(\infty)|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r})\big{)}=0.$

###### Proof:

By Lemma 3, we have

$\displaystyle\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})+b\bm{c}_{r}(\infty)|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r})\big{)}$
$\displaystyle=$
$\displaystyle\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r})\big{)}+b\det\big{(}\bm{c}_{r}(\infty)|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r})\big{)}$
$\displaystyle=$ $\displaystyle
V(\alpha_{1},\alpha_{2},\cdots,\alpha_{r})(1-\theta\sum_{i=1}^{r}\alpha_{i})+bV(\alpha_{2},\alpha_{3},\cdots,\alpha_{r})$
$\displaystyle=$ $\displaystyle
V(\alpha_{2},\alpha_{3},\cdots,\alpha_{r})((1-\theta\sum_{i=1}^{r}\alpha_{i})\prod_{j=2}^{r}(\alpha_{j}-\alpha_{1})+b).$

Denote $\beta_{0}=\prod\limits_{i=2}^{r-2}(\alpha_{i}-\alpha_{1})$,
$\xi=1-\theta\sum\limits_{i=2}^{r-2}\alpha_{i}-2\theta\alpha_{1}$,
$X=\alpha_{r-1}-\alpha_{1}$, and $Y=\alpha_{r}-\alpha_{1}$. Then we only need
to show that the equation

$F(X,Y)\triangleq\beta_{0}XY(\xi-\theta(X+Y))+b=0,$ (8)

has a solution $(X,Y)\in\mathbb{F}^{2}_{q}$ with $X\neq
Y\in\mathbb{F}_{q}\backslash\mathcal{S}$, where
$\mathcal{S}=\\{0,\alpha_{2}-\alpha_{1},\cdots,\alpha_{r-2}-\alpha_{1}\\}$.

If $b=0$, then it is equivalent to show that
$F_{0}(X,Y)\triangleq\theta(X+Y)-\xi=0$ has a solution
$(X,Y)\in\mathbb{F}^{2}_{q}$ with $X\neq
Y\in\mathbb{F}_{q}\backslash\mathcal{S}$. Note that ${\rm
N}(F_{0}(X,Y))=|\\{(X,Y)\in\mathbb{F}^{2}_{q}:F_{0}(X,Y)=0\\}|=q$. Given
$X\in\mathcal{S}$, then $|\\{Y\in\mathbb{F}_{q}:F_{0}(X,Y)=0\\}|=1$ and
$|\\{(X,Y)\in\mathbb{F}^{2}_{q}:F_{0}(X,Y)=0\textnormal{ and }X=Y\\}|=1$. The
conclusion then follows by $N_{0}=q>2\times|\mathcal{S}|+1=2r-1$.

For $b\neq 0$, then the solution of Eq. (8) satisfies that
$(X,Y)\in(\mathbb{F}^{*}_{q})^{2}$. For each
$\beta\in\mathcal{S}\backslash\\{0\\}$, ${\rm N}(F(X,\beta))={\rm
N}(F(\beta,X))\leq 2$. In addition, ${\rm N}(F(X,X))\leq 3$. Thus we only need
to show that ${\rm N}(F(X,Y))>2\times 2\times(|\mathcal{S}|-1)+3=4r-9$, i.e.,
${\rm N}(F(X,Y))\geq 4r-8$. Next, we use character sums to estimate the value
of ${\rm N}(F(X,Y))$.

Let $\chi(x)$ be the canonical additive character of $\mathbb{F}_{q}$ and
$\eta$ be the quadratic character of $\mathbb{F}_{q}$. Then

$\displaystyle{\rm N}(F(X,Y))$ $\displaystyle=$
$\displaystyle\frac{1}{q}\sum_{X,Y\in\mathbb{F}_{q}}\sum_{z\in\mathbb{F}_{q}}\chi(zF(X,Y))$
$\displaystyle=$ $\displaystyle
q-1+\frac{1}{q}\sum_{z\in\mathbb{F}^{*}_{q}}\sum_{Y\in\mathbb{F}^{*}_{q}}\sum_{X\in\mathbb{F}_{q}}\chi(z\beta_{0}\theta
YX^{2}+z\beta_{0}Y(-\xi+\theta Y)X-zb)$
$\displaystyle\stackrel{{\scriptstyle\rm(a)}}{{=}}$ $\displaystyle
q-1+\frac{1}{q}\sum_{Y,z\in\mathbb{F}^{*}_{q}}\chi(zb+\frac{z\beta_{0}Y(\theta
Y-\xi)^{2}}{4\theta})\eta(-z\beta_{0}\theta Y)G(\eta,\chi)$
$\displaystyle\stackrel{{\scriptstyle\rm(b)}}{{=}}$ $\displaystyle
q-1+\frac{G(\eta,\chi)}{q}\sum_{W\in\mathbb{F}^{*}_{q}}\eta(W)\sum_{z\in\mathbb{F}^{*}_{q}}\chi(zf(W))\eta(z),$

where (a) follows from Proposition 2 (ii), (b) is because that
$\beta_{0}\theta\neq 0$ and
$f(W)=b-\frac{W(\beta_{0}\xi+W)^{2}}{4\theta^{2}\beta^{2}_{0}}$ with
$W=-\beta_{0}\theta Y$.

Denote $\mathcal{Z}_{0}=\\{W\in\mathbb{F}_{q}^{*}:f(W)=0\\}$, then by
Proposition 1 and $\sum\limits_{z\in\mathbb{F}^{*}_{q}}\eta(z)=0$, we have

$\displaystyle{\rm N}(F(X,Y))$ $\displaystyle=$ $\displaystyle
q-1+\frac{G(\eta,\chi)}{q}\big{(}\sum_{W\in\mathcal{Z}_{0}}\eta(W)\sum_{z\in\mathbb{F}^{*}_{q}}\eta(z)+\sum_{W\in\mathbb{F}^{*}_{q}\backslash\mathcal{Z}_{0}}\sum_{z\in\mathbb{F}^{*}_{q}}\chi(zf(W))\eta(z)\big{)}$
$\displaystyle=$ $\displaystyle
q-1+\frac{G^{2}(\eta,\chi)}{q}\sum_{W\in\mathbb{F}^{*}_{q}\setminus\mathcal{Z}_{0}}\eta(Wf(W))$
$\displaystyle=$ $\displaystyle
q-1+\frac{G^{2}(\eta,\chi)}{q}\sum_{W\in\mathbb{F}^{*}_{q}}\eta(Wf(W)),$

If $Wf(W)=g^{2}(W)$ for some nonzero polynomial $g(W)\in\mathbb{F}_{q}[W]$,
then $g(0)=0$, write $g(W)=W\cdot h(W)$ for some nonzero polynomial
$h(W)\in\mathbb{F}_{q}[W]$. Then $f(W)=Wh^{2}(W)$, which implies that
$b=f(0)=0$, a contradiction. Thus we have that $Wf(W)$ can not be a square of
some polynomial in $\mathbb{F}_{q}[W]$. By Proposition 3, it has

$\left|\sum_{W\in\mathbb{F}^{*}_{q}}\eta(Wf(W))\right|\leq 2\sqrt{q}.$

Therefore, ${\rm N}(F(X,Y))\geq
q-1-\frac{|G(\eta,\chi)|^{2}}{q}|\sum\limits_{Y\in\mathbb{F}^{*}_{q}}\eta(Wf(W))|\geq
q-1-2\sqrt{q}$. Since $r\leq\frac{q-2\sqrt{q}+7}{4}$, we can deduce that ${\rm
N}(F(X,Y))\geq q-1-2\sqrt{q}\geq 4r-8$. The proof is completed.∎

Seroussi and Roth [18] proved the following nice result for the MDS extensions
of RS codes.

######  Theorem 8 (Seroussi and Roth [18], Theorem 1)

Suppose
$\mathcal{A}=\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\\}\subseteq\mathbb{F}_{q}$
and $2\leq r\leq n-\frac{q-1}{2}$. Let
$G_{r}=\big{(}\bm{c}_{r}(\alpha_{1})|\bm{c}_{r}(\alpha_{2})|\cdots|\bm{c}_{r}(\alpha_{n})\big{)}$
be the generator matrix of the Reed-Solomon code ${\rm RS}_{r}(\mathcal{A})$.
Suppose $\bm{w}\in\mathbb{F}_{q}^{r}$ be a vector. Then the augmented matrix
$\big{(}G_{r}|\bm{w}^{\top}\big{)}$ generates an $[n+1,r]_{q}$ MDS code if and
only if:

1) ( for $q$ odd ) $\bm{w}^{\top}=a\bm{c}_{r}(\delta)$ for some
$\delta\in(\mathbb{F}_{q}\cup\infty)\backslash\mathcal{A}$ and
$a\in\mathbb{F}^{*}_{q}$;

2) (for $q$ even) $\bm{w}$ is either as above, or additionally in case
$r=3,\bm{w}=(0,0,a)$ for some $a\in\mathbb{F}^{*}_{q}$.

Applying the above lemmas and Seroussi and Roth’s result, we determine the
deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ for odd $q$.

###### Theorem 9

Suppose $q$ is odd. If $\frac{3q+2\sqrt{q}-7}{4}\leq k\leq q-4$, then Theorem
5 provides all deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.

###### Proof:

Denote $r=q-k$, then $3\leq r\leq\frac{q-2\sqrt{q}+7}{4}$. Suppose $\bm{u}$ is
a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ and
$\bm{w}^{\top}=H\cdot\bm{u}^{\top}$. Write $\bm{w}=(\bm{w}^{\prime},\lambda),$
where $\bm{w}^{\prime}\in\mathbb{F}^{r-1}_{q}$.

(i): If $\bm{w}^{\prime\top}=a\bm{c}_{r-1}(\infty)$ for some
$a\in\mathbb{F}^{*}_{q}$, then by Lemma 8, there exist distinct elements
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r-1}\in\mathbb{F}_{q}$ such that
$\bm{c}_{r,\theta}(\alpha_{1}),\bm{c}_{r,\theta}(\alpha_{2}),\cdots,\bm{c}_{r,\theta}(\alpha_{r-1})$
and $H\cdot\bm{u}^{\top}$ are $\mathbb{F}_{q}$-linearly dependent, which
contradicts to Proposition 8.

(ii): If $\bm{w}^{\prime\top}\neq a\bm{c}_{r-1}(\infty)$ for any
$a\in\mathbb{F}_{q}$, by Theorem 8, there exist distinct elements
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r-2}\in\mathbb{F}_{q}$ such that
$\bm{c}_{r-1}(\alpha_{1}),\bm{c}_{r-1}(\alpha_{2}),\cdots,\bm{c}_{r-1}(\alpha_{r-2})$
and $\bm{w}^{\prime\top}$ are linearly dependent, i.e., there exist not all
zero elements $a_{1},\cdots,a_{r-2}\in\mathbb{F}_{q}$, such that
$\bm{w}^{\prime}=\sum_{i=1}^{r-2}a_{i}\bm{c}_{r-1}(\alpha_{i}).$ Thus

$\displaystyle\bm{w}^{\top}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{c}\sum\limits_{i=1}^{r-2}a_{i}\bm{c}_{r-1}(\alpha_{i})\\\
0\end{array}\right)+\lambda\bm{c}_{r}(\infty)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{r-2}a_{i}\left(\begin{array}[]{c}\bm{c}_{r-1}(\alpha_{i})\\\
0\end{array}\right)+\lambda\bm{c}_{r}(\infty)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{r-2}a_{i}\bm{c}_{r,\theta}(\alpha_{i})+b\bm{c}_{r}(\infty),$

where
$b=-\sum_{i=1}^{r-2}a_{i}(\alpha^{r-1}_{i}+\theta\alpha^{r}_{i})+\lambda$.
Without loss of generality, we suppose $a_{1}=1$. Then by Lemma 9, there exist
not all zero elements $b_{1},\cdots,b_{r-2}\in\mathbb{F}_{q}$ and
$\alpha_{r-1}\neq\alpha_{r}\in\mathbb{F}_{q}\backslash\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{r-2}\\}$
, such that

$\bm{c}_{r,\theta}(\alpha_{1})+b\bm{c}_{r}(\infty)=\sum_{i=2}^{r}b_{i}\bm{c}_{r,\theta}(\alpha_{i}).$

Hence
$\bm{w}^{\top}=\sum\limits_{i=2}^{r}(a_{i}+b_{i})\bm{c}_{r,\theta}(\alpha_{i})$,
which contradicts to Proposition 8.

Therefore, we deduce that $\bm{w}^{\prime}=\bm{0}$, i.e.,
$\bm{w}=(0,0,\cdots,0,1)$. Then the conclusion follows by Proposition 7. ∎

Finally, we determine all deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
for odd $q>16$ and $k\in\\{q-3,q-2,q-1\\}$.

###### Theorem 10

Suppose odd $q>16$. Let $\bm{u}\in\mathbb{F}^{q}_{q}$ and
$\bm{w}=H\cdot\bm{u}^{\top}=(w_{0},w_{1},\cdots,w_{q-k-1})^{\top}$, where $H$
is the parity-check matrix of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ given in
Eq. (3).

  * (i)

For $k=q-1$, $\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
if and only if $\bm{u}$ is generated by Theorem 5.

  * (ii)

For $k=q-2$, $\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
if and only if $\bm{u}$ is generated by
$w_{0}(1-x^{q-1})+w_{1}x^{q-2}+f_{q-2,\theta}(x)$ with $w_{0}=0,w_{1}\neq 0$
or $w_{0}\neq 0$ and $\eta(w_{0}^{2}-4w_{0}w_{1}\theta)=-1$.

  * (iii)

For $k=q-3$, $\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
if and only if $\bm{u}$ is given by Theorem 5 or generated by
$a(x^{q-2}+\frac{1}{3\theta}x^{q-3})+f_{q-3,\theta}(x)$ with $a\neq 0$,
$f_{q-3,\theta}(x)\in\mathcal{S}_{q-3,\theta}$ and $\eta(-3)=-1$.

###### Proof:

(i): For $k=q-1$, then $\rho({\rm TRS}_{k}(\mathbb{F}_{q},\theta))=q-k=1$.
Thus every non-codeword is a deep hole. The conclusion can be easily verified.

(ii): For $k=q-2$, then by Proposition 8, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if for any
$\alpha\in\mathbb{F}_{q}$.

$\det\left(\begin{array}[]{cc}1&w_{0}\\\ \alpha-\theta\alpha^{2}&w_{1}\\\
\end{array}\right)=\theta w_{0}\alpha^{2}-w_{0}\alpha+w_{1}\neq 0.$ (11)

Hence, Eq. (11) holds $\Longleftrightarrow w_{0}=0,w_{1}\neq 0$, or,
$w_{0}\neq 0$ and $\theta w_{0}x^{2}+w_{0}x+w_{1}=0$ has no roots in
$\mathbb{F}_{q}$. One can easily verify that the latter one is equivalent to
$\eta(w^{2}_{0}-4w_{1}w_{0}\theta)=-1$ and the vector $\bm{u}_{f}$ generated
by $f(x)=w_{0}x^{q-1}+w_{1}x^{q-2}+f_{q-2,\theta}(x)$ satisfies
$H\cdot\bm{u}^{\top}_{f}=(w_{0},w_{1})$. Thus such vectors are all deep holes
of ${\rm TRS}_{q-2}(\mathbb{F}_{q},\theta)$.

(iii):  For $k=q-3$, then by Proposition 8, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if for any
$\alpha\neq\beta\in\mathbb{F}_{q}$,

$D(\alpha,\beta)=\frac{\det\left(\begin{array}[]{ccc}1&1&w_{0}\\\
\alpha&\beta&w_{1}\\\
\alpha^{2}-\theta\alpha^{3}&\beta^{2}-\theta\beta^{3}&w_{2}\\\
\end{array}\right)}{\beta-\alpha}\neq 0,$

which is equivalent to that for any $Z_{2}\in\mathbb{F}_{q}^{*}$ and
$Z_{1}\in\mathbb{F}_{q}$,

$g(Z_{1},Z_{2})=D(Z_{1}+Z_{2},Z_{1}-Z_{2})=(\theta w_{1}-w_{0}+2\theta
w_{0}Z_{1})Z_{2}^{2}-(2\theta w_{0}Z_{1}^{3}-(3\theta
w_{1}+w_{0})Z_{1}^{2}+2w_{1}Z_{1}-w_{2})\neq 0.$ (12)

In other word, $\bm{u}$ is a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ if and only if ${\rm N}(g(Z_{1},Z_{2}))={\rm
N}(g(Z_{1},0))$.

Next, we determine all such vectors
$\bm{w}^{\top}\in\mathbb{F}_{q}^{3}\setminus\\{\bm{0}\\}$ such that $\bm{u}$
is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$.

_Case 1_ : $w_{0}=0$ and $w_{1}=0$. Then $g(Z_{1},Z_{2})=w_{2}\neq 0$, i.e.,
Eq. (12) holds.

_Case 2_ : $w_{0}=0$ and $w_{1}\neq 0$. Then $g(Z_{1},Z_{2})=\theta
w_{1}(Z_{2}^{2}+3(Z_{1}-\frac{1}{3\theta})^{2}-b),$ where
$b=\frac{w_{1}-3\theta w_{2}}{3\theta^{2}w_{1}}$. By Proposition 4, it has
that

${\rm N}(g(Z_{1},Z_{2}))=q+v(b)\eta(-3)=\begin{cases}1&{\rm
if~{}}w_{1}=3\theta w_{2}\text{~{}and~{}}\eta(-3)=-1,\\\ 2q-1&{\rm
if~{}}w_{1}=3\theta w_{2}\text{~{}and~{}}\eta(-3)=1,\\\ q-\eta(-3)&{\rm
otherwise}.\end{cases}$

Moreover, it has that ${\rm N}(g(Z_{1},0))=1$ when $w_{1}=3\theta w_{2},$ and
$\eta(-3)=-1$ and ${\rm N}(g(Z_{1},0))\leq 2$ in other cases. Hence,
$\bm{w}=w_{1}(0,1,\frac{1}{3\theta})$ for $w_{1}\neq 0$ is a desired vector.

_Case 3_ : $w_{0}\neq 0$. We claim that $g(Z_{1},Z_{2})$ at least has a
solution $(Z_{1},Z_{2})$ with $Z_{2}\neq 0$ in this case.

Suppose $b(Z_{1})=(\theta w_{1}-w_{0}+2\theta w_{0}Z_{1})(2\theta
w_{0}Z_{1}^{3}-(3\theta w_{1}+w_{0})Z_{1}^{2}+2w_{1}Z_{1}-w_{2})$,
$\mathcal{Z}_{0}=\\{Z_{1}\in\mathbb{F}_{q}:b(Z_{1})=0\\}$,
$\mathcal{Z}_{+}=\\{Z_{1}\in\mathbb{F}_{q}\setminus\mathcal{Z}_{0}:\eta(b(Z_{1}))=1\\}$,
and
$\mathcal{Z}_{-}=\\{Z_{1}\in\mathbb{F}_{q}\setminus\mathcal{Z}_{0}:\eta(b(Z_{1}))=-1\\}$.
Note that ${\rm N}(b(Z_{1}))\leq\deg(b(Z_{1}))=4$, and $(\theta
w_{1}-w_{0}+2\theta w_{0}Z_{1})g(Z_{1},Z_{2})=((\theta w_{1}-w_{0}+2\theta
w_{0}Z_{1})Z_{2})^{2}-b(Z_{1})$, then it has that

  * 1)

$|\mathcal{Z}_{0}|={\rm N}(b(Z_{1}))\leq 4$;

  * 2)

${\rm N}(g(Z_{1},Z_{2}))\geq 2|\mathcal{Z}_{+}|$, this is because that for any
$Z_{1}\in\mathcal{Z}_{+}$, $g(Z_{1},\frac{\mp\sqrt{b(Z_{1})}}{\theta
w_{1}-w_{0}+2\theta w_{0}Z_{1}})=0$;

  * 3)

$q=|\mathcal{Z}_{0}|+|\mathcal{Z}_{+}|+|\mathcal{Z}_{-}|$;

  * 4)

$\sum_{Z_{1}\in\mathbb{F}_{q}}\eta(b(Z_{1}))=|\mathcal{Z}_{+}|-|\mathcal{Z}_{-}|=2|\mathcal{Z}_{+}|+|\mathcal{Z}_{0}|-q\leq
2|\mathcal{Z}_{+}4-q$.

If $b(Z_{1})$ is a square of some polynomial in $\mathbb{F}_{q}[Z_{1}]$, that
is, $|\mathcal{Z}_{-}|=0$, then ${\rm N}(g(Z_{1},Z_{2}))\geq
2|\mathcal{Z}_{+}|\geq 2(q-4)>4\geq{\rm N}(g(Z_{1},0))$. If $b(Z_{1})$ isn’t a
square of some polynomial in $\mathbb{F}_{q}[Z_{1}]$, then it follows from
Proposition 3 and $q>16$ that $2|\mathcal{Z}_{+}|\geq
q-4-3\sqrt{q}=(\sqrt{q}-4)(\sqrt{q}+1)>0$. Hence, there exists
$Z_{1}\in\mathcal{Z}_{+}$ such that $Z_{2}=\frac{\mp\sqrt{b(Z_{1})}}{\theta
w_{1}-w_{0}+2\theta w_{0}Z_{1}}\neq 0$ and $g(Z_{1},Z_{2})=0$.

In a word, $\bm{u}$ is a deep hole of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$
if and only if $\bm{w}=a(0,0,1)$ or $\bm{w}=a(0,1,\frac{1}{3\theta})$ when
$\eta(-3)=-1$, where $a\in\mathbb{F}^{*}_{q}$. The conclusion then follows by
Proposition 7.

∎

##  V Conclusion

Due to its crucial role in decoding, determining the deep holes of Reed-
Solomon codes is of great significance. As a generalization of Reed-Solomon
codes, Twisted Reed-Solomon codes have received increasing attention from
scholars in recent years and have important applications in coding theory and
cryptography. In this paper, we focus on the problem of deep holes of twisted
RS codes. For a general evaluation set $\mathcal{A}\subseteq\mathbb{F}_{q}$,
we determine the covering radius and obtain a standard class of deep holes of
twisted RS codes ${\rm TRS}_{k}(\mathcal{A},\theta)$. Furthermore, we
investigate the classification of deep holes the twisted RS code ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ with full length. We prove that there are no
other deep holes of ${\rm TRS}_{k}(\mathbb{F}_{q},\theta)$ for
$\frac{3q-8}{4}\leq k\leq q-4$ when $q\geq 8$ is even, and
$\frac{3q+2\sqrt{q}-7}{4}\leq k\leq q-4$ when $q>16$ is odd. We also
completely determine their deep holes for $q-3\leq k\leq q-1$. For odd $q$,
our results have a narrower range of values for the dimension $k$ compared to
the case when $q$ is even. One reason for this is that in the proof of Lemma
9, we utilized the following estimate:

$\left|\sum_{W\in\mathbb{F}^{*}_{q}}\eta(Wf(W))\right|\leq 2\sqrt{q}.$

Improving the estimate of the absolute value of this character sum will yield
better results for odd $q$. Furthermore, based on our results and the
conjecture 1 for RS codes, we present the following conjecture on the
completeness of deep holes for TRS codes.

###### Conjecture 2

For $2\leq k\leq q-4$, all deep holes of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$ have generating polynomials
$f(x)=ax^{k}+f_{k,\theta}(x)$ with $a\neq 0$ and
$f_{k,\theta}(x)\in\mathcal{S}_{k,\theta}$.

It is also interesting to study the deep holes of ${\rm
TRS}_{k}(\mathcal{A},\theta)$ for more general evaluation set
$\mathcal{A}\subseteq\mathbb{F}_{q}$ and other twisted Reed-Solomon codes.

##  Appendix A  Proof of Lemma 6

Before proving Lemma 6, we need some notions and auxiliary lemmas. Suppose
$q=2^{m}$, and $\chi$ is the canonical additive character of $\mathbb{F}_{q}$.
Let $\lambda$ be the multiplicative character of $\mathbb{F}_{q}$ of order 3
when $m$ is even, and $\pi$ be a primitive element of $\mathbb{F}_{q}$.

###### Lemma 10

For $a\in\mathbb{F}^{*}_{q}$,

$\sum_{X\in\mathbb{F}_{q}}\chi(aX^{3})=\begin{cases}0&\text{ if }m\text{ is
odd},\\\ (\bar{\lambda}(a)+\bar{\lambda}^{2}(a))\sqrt{q}&\text{ if
}\frac{m}{2}\text{ is odd},\\\
-(\bar{\lambda}(a)+\bar{\lambda}^{2}(a))\sqrt{q}&\text{ if }\frac{m}{2}\text{
is even}.\end{cases}$

###### Proof:

By [33], it has that

$G(\lambda,\chi)=\begin{cases}\sqrt{q}&\text{ if }\frac{m}{2}\text{ is
odd},\\\ -\sqrt{q}&\text{ if }\frac{m}{2}\text{ is even}.\end{cases}$

By Theorem 5.30 in [32], we obtain that for any $a\in\mathbb{F}^{*}_{q}$,

$\sum_{X\in\mathbb{F}_{q}}\chi(aX^{3})=\begin{cases}0&\text{ if }m\text{ is
odd},\\\
\bar{\lambda}(a)G(\lambda,\chi)+\bar{\lambda}^{2}(a)G(\lambda^{2},\chi)&\text{
if }m\text{ is even}.\end{cases}$

Then the conclusion follows by above two identities. ∎

###### Lemma 11

Suppose $q=2^{m}$ and $a\in\mathbb{F}^{*}_{q}$, then

${\rm N}(XY(X+Y)+a)=\begin{cases}q-2&\text{ if }m\text{ is odd},\\\
q-2+2\sqrt{q}&\text{ if }\frac{m}{2}\text{ is odd and }\lambda(a)=1,\\\
q-2+\sqrt{q}&\text{ if }\frac{m}{2}\text{ is even and }\lambda(a)\neq
1.\end{cases}$

###### Proof:

$\displaystyle{\rm N}(XY(X+Y)+a)$ $\displaystyle=$
$\displaystyle\frac{1}{q}\sum_{X,Y\in\mathbb{F}_{q}}\sum_{z\in\mathbb{F}_{q}}\chi(z(XY(X+Y)+a))$
$\displaystyle=$ $\displaystyle
q-1+\frac{1}{q}\sum_{z\in\mathbb{F}^{*}_{q}}\sum_{Y\in\mathbb{F}^{*}_{q}}\sum_{X\in\mathbb{F}_{q}}\chi(zYX^{2}+zY^{2}X+za)$
$\displaystyle\stackrel{{\scriptstyle\rm(a)}}{{=}}$ $\displaystyle
q-1+\sum_{Y\in\mathbb{F}^{*}_{q}}\chi(\frac{a}{Y^{3}})=q-1+\sum_{Y\in\mathbb{F}^{*}_{q}}\chi(aY^{3})$
$\displaystyle=$ $\displaystyle q-2+\sum_{Y\in\mathbb{F}_{q}}\chi(aY^{3}),$

where Eq. (a) follows from Proposition 2 (iii). The conclusion then follows
from Lemma 10 and the fact that $\bar{\lambda}(a)+\bar{\lambda}^{2}(a)+1=0$
when $\lambda(a)\neq 1$ ∎

######  Lemma 12 ([32], Example 6.38)

For any $b\in\mathbb{F}_{q}$, ${\rm N}(X^{3}+Y^{3}-b)\geq q-2\sqrt{q}-2.$
Consequently, when $q\geq 16$, there exist $x,y\in\mathbb{F}^{*}_{q}$, such
that $b=x^{3}+y^{3}$.

###### Lemma 13

Suppose $q=2^{m}\geq 16$, and $1\leq n\leq\frac{q}{4}$. Let $\pi$ be a
primitive element of $\mathbb{F}_{q}$. For $w\in\mathbb{F}_{q}$, denote
$Q(x_{1},\cdots,x_{n})=\sum\limits_{i=1}^{n}x^{3}_{i}+\theta^{-3}+(\sum\limits_{i=1}^{n}x_{i}+\theta^{-1})^{3}+\theta^{-1}w$.
Then there exist pairwise distinct elements
$\alpha_{1},\cdots,\alpha_{n}\in\mathbb{F}_{q}$ and $c\in\mathbb{F}_{q}^{*}$,
such that

$Q(\alpha_{1},\cdots,\alpha_{n})=g(c)\triangleq\begin{cases}c&{\rm
if~{}}2\nmid m,\\\ c^{3}&{\rm if~{}}2\mid m\text{ and }2\nmid\frac{m}{2},\\\
\pi c^{3}&{\rm if~{}}2\mid m\text{ and }2\mid\frac{m}{2}.\end{cases}$

###### Proof:

For $n=1$, note that
$Q(x_{1})=\theta^{-1}x_{1}(x_{1}+\theta^{-1})+\theta^{-1}w$. Then ${\rm
N}\big{(}Q(x_{1})+g(c)\big{)}>0$ for some $c\in\mathbb{F}_{q}^{*}$ if and only
if ${\rm Tr}\big{(}\theta^{2}w+\theta^{3}g(x)\big{)}=0$ has a solution
$x\in\mathbb{F}_{q}^{*}$. This is equivalent to $1<{\rm N}\big{(}{\rm
Tr}(\theta^{3}g(x))\big{)}<q$. Since ${\rm N}\big{(}{\rm
Tr}(\theta^{3}g(x))+1\big{)}+{\rm N}\big{(}{\rm Tr}(\theta^{3}g(x))\big{)}=q$
and $\sum\limits_{x\in\mathbb{F}_{q}}\chi(\theta^{3}g(x))={\rm N}\big{(}{\rm
Tr}(\theta^{3}g(x))\big{)}-{\rm N}\big{(}{\rm Tr}(\theta^{3}g(x))+1\big{)}$,
hence ${\rm N}\big{(}{\rm
Tr}(\theta^{3}g(x))\big{)}=\frac{q}{2}+\frac{1}{2}\sum_{x\in\mathbb{F}_{q}}\chi(\theta^{3}g(x))$.
By Lemma 10, it has that $|{\rm N}\big{(}{\rm
Tr}(\theta^{3}g(x))\big{)}-\frac{q}{2}|\leq\sqrt{q}$, which implies that

$2<\frac{q}{2}-\sqrt{q}\leq{\rm N}\big{(}{\rm
Tr}(\theta^{3}g(x))\big{)}\leq\frac{q}{2}+\sqrt{q}<q.$

When $n\geq 2$, $Q(x_{1},\cdots,x_{n-1},x_{n}=0)=Q(x_{1},\cdots,x_{n-1})$,
thus we may assume that $n$ is even and prove that there exist pairwise
distinct elements $\alpha_{1},\cdots,\alpha_{n}\in\mathbb{F}^{*}_{q}$ such
that the conclusion holds. Calculating yields the recursion relation

$Q(x_{1},\cdots,x_{n})=(x_{n-1}+\sum_{i=1}^{n-2}x_{i}+\theta^{-1})(x_{n}+\sum_{i=1}^{n-2}x_{i}+\theta^{-1})(x_{n-1}+x_{n})+Q(x_{1},\cdots,x_{n-2}).$

Thus we will prove the conclusion by induction on $n\geq 2$.

Case (i): $2\nmid m$. For $n=2$, then
$Q(x_{1},x_{2})=(x_{1}+\theta^{-1})(x_{2}+\theta^{-1})(x_{1}+x_{2})+\theta^{-1}wXY(X+Y)+\theta^{-1}w$,
where $X=x_{1}+\theta^{-1}$ and $Y=x_{2}+\theta^{-1}$. Choose
$c\in\mathbb{F}_{q}^{*}\backslash\\{\theta^{-1}w_{r-1}\\}$, by Lemma 11, ${\rm
N}(Q(x_{1},x_{2})+c)={\rm N}(XY(X+Y)+\theta^{-1}w+c)=q-2$. Note that
$Q(x_{1},x_{2})+c=0$ implies that $x_{1}\neq x_{2}$. In addition, ${\rm
N}(Q(0,x_{2})+c)\leq 2$ and ${\rm N}(Q(x_{1},0)+c)\leq 2$. Then from
$q-2>2+2=4$, we deduce that there exist
$\alpha_{1}\neq\alpha_{2}\in\mathbb{F}^{*}_{q}$ such that
$Q(\alpha_{1},\alpha_{2})+c=0$. Now suppose there exist pairwise distinct
elements $\alpha_{1},\cdots,\alpha_{n-2}\in\mathbb{F}^{*}_{q}$ such that
$Q(\alpha_{1},\cdots,\alpha_{n-2})=c^{\prime}$ for some
$c^{\prime}\in\mathbb{F}_{q}^{*}$. Denote
$X=x_{n-1}+\sum_{i=1}^{n-2}\alpha_{i}+\theta^{-1}$ and
$Y=x_{n}+\sum_{i=1}^{n-2}\alpha_{i}+\theta^{-1}$, then

$Q(\alpha_{1},\cdots,\alpha_{n-2},x_{n-1,}x_{n})=XY(X+Y)+c^{\prime}.$

Choose $c\in\mathbb{F}_{q}^{*}\backslash\\{c^{\prime}\\}$, then by Lemma 11
again, ${\rm N}(Q(\alpha_{1},\cdots,\alpha_{n-2},x_{n-1,}x_{n})+c)={\rm
N}(XY(X+Y)+c^{\prime}+c)=q-2.$ Since $c\neq c^{\prime}$,
$Q(\alpha_{1},\cdots,\alpha_{n-2},x_{n-1,}x_{n})=c$ implies that $x_{n-1}\neq
x_{n}$. Given $x_{n-1}$ (resp. $x_{n}$)
$\in\\{0,\alpha_{1},\cdots,\alpha_{n-2}\\}$, there exist at most two $x_{n}$’s
(resp. $x_{n-1}$’s), such that $XY(X+Y)+c^{\prime}+c=0$. Thus from
$q-2>4(n-1)$, we obtain that there exist $x_{n-1}\neq
x_{n}\in\mathbb{F}_{q}^{*}\backslash\\{\alpha_{1},\cdots,\alpha_{n-2}\\}$ such
that $Q(\alpha_{1},\cdots,\alpha_{n})=\alpha$.

Case (ii): $2\mid m$ and $2\nmid\frac{m}{2}$. By Lemma 12,
$\theta^{-1}w_{r-1}=c_{1}^{3}+d_{1}^{3}$ for some
$c_{1},d_{1}\in\mathbb{F}_{q}^{*}$. For $n=2$, then
$Q(x_{1},x_{2})=XY(X+Y)+\theta^{-1}w_{r-1}=XY(X+Y)+c_{1}^{3}+d_{1}^{3}$, where
$X=x_{1}+\theta^{-1}$ and $Y=x_{2}+\theta^{-1}$. Then by Lemma 11, ${\rm
N}(Q(x_{1},x_{2})+c_{1}^{3})={\rm N}(XY(X+Y)+\beta_{1}^{3})=q-2+2\sqrt{q}.$
Similar to the proof of (i), by $q-2+2\sqrt{q}>4$, we deduce that there exist
$\alpha_{1}\neq\alpha_{2}\in\mathbb{F}^{*}_{q}$ such that
$Q(\alpha_{1},\alpha_{2})=c_{1}^{3}$. Now suppose there exist pairwise
distinct elements $\alpha_{1},\cdots,\alpha_{n-2}\in\mathbb{F}^{*}_{q}$ such
that $Q(\alpha_{1},\cdots,\alpha_{n-2})=c^{\prime 3}$ for some
$c^{\prime}\in\mathbb{F}_{q}^{*}$. By Lemma 12 again, $c^{\prime
3}=c^{3}+d^{3}$ for some $c,d\in\mathbb{F}_{q}^{*}$. Denote
$X=x_{n-1}+\sum_{i=1}^{n-2}\alpha_{i}+\theta^{-1}$ and
$Y=x_{n}+\sum_{i=1}^{n-2}\alpha_{i}+\theta^{-1}$, then

$Q(\alpha_{1},\cdots,\alpha_{n-2},x_{n-1,}x_{n})=XY(X+Y)+c^{\prime 3}.$

By Lemma 11 again, ${\rm
N}(Q(\alpha_{1},\cdots,\alpha_{n-2},x_{n-1,}x_{n})+c^{3})={\rm
N}(XY(X+Y)+d^{3})=q-2+2\sqrt{q}.$ Since $d\neq 0$, $X+Y\neq 0$, which implies
that $x_{n-1}\neq x_{n}$. Given $x_{n-1}$ (resp. $x_{n}$)
$\in\\{0,\alpha_{1},\cdots,\alpha_{n-2}\\}$, there exist at most two $x_{n}$’s
(resp. $x_{n-1}$’s), such that
$Q(\alpha_{1},\cdots,\alpha_{n-2},x_{n-1,}x_{n})+c^{3}=0$. Thus from
$q-1+2\sqrt{q}>4(n-1)$, we obtain that there exist
$\alpha_{n-1}\neq\alpha_{n}\in\mathbb{F}_{q}^{*}\backslash\\{\alpha_{1},\cdots,\alpha_{n-2}\\}$
such that $Q(\alpha_{1},\cdots,\alpha_{n})+c^{3}=0$.

Case (iii) $4\mid m$. By Lemma 12,
$\pi^{-1}\theta^{-1}w_{r-1}=c_{1}^{3}+d_{1}^{3}$ i.e., $\theta^{-1}w_{r-1}=\pi
c_{1}^{3}+\pi d_{1}^{3}$ for some $c_{1},d_{1}\in\mathbb{F}_{q}^{*}$. Note
that $\lambda(\pi c_{1}^{3})\neq 1$. The remainder proof is then similar to
the case (ii) by using Lemmas 11 and 12. ∎

Now, we are going to prove Lemma 6.

Proof of Lemma 6: Without loss of generality, we suppose $w_{r-3}=1$, then
$w_{r-2}=\theta^{-1}$. By the proof process of Lemma 4 (or the conclusion of
Lemma 4), we have

$\displaystyle\frac{\det\big{(}\bm{c}_{r,\theta}(x_{1})|\bm{c}_{r,\theta}(x_{2})|\cdots|\bm{c}_{r,\theta}(x_{r-1})|\bm{w}^{\top}\big{)}}{\theta
V(x_{1},x_{2},\cdots,x_{r-1})}$ $\displaystyle=$ $\displaystyle
S_{r-3}(x_{1},\cdots,x_{r-1})(\theta^{-1}+\sum\limits_{t=1}^{r-1}x_{t})+S_{r-4}(x_{1},\cdots,x_{r-1})$
$\displaystyle+\theta^{-1}(S_{r-2}(x_{1},\cdots,x_{r-1})(\theta^{-1}+\sum\limits_{t=1}^{r-1}x_{t})+S_{r-3}(x_{1},\cdots,x_{r-1})\big{)}+\theta^{-1}w_{r-1}$
$\displaystyle=$ $\displaystyle
S_{r-4}(x_{1},\cdots,x_{r-1})+S_{r-3}(x_{1},\cdots,x_{r-1})S_{r-2}(x_{1},\cdots,x_{r-1})+\theta^{-1}S^{2}_{r-2}(x_{1},\cdots,x_{r-1})$
$\displaystyle+\theta^{-2}S_{r-2}(x_{1},\cdots,x_{r-1})+\theta^{-1}w_{r-1}$
$\displaystyle=$ $\displaystyle\sum_{1\leq i<j<\ell\leq
r-1}x_{i}x_{j}x_{\ell}+\sum_{1\leq i<j\leq
r-1}x_{i}x_{j}\sum_{i=1}^{r-1}x_{i}+\theta^{-1}(\sum_{i=1}^{r-1}x_{i})^{2}+\theta^{-2}\sum_{i=1}^{r-1}x_{i}+\theta^{-1}w_{r-1}$
$\displaystyle=$ $\displaystyle Q(x_{1},\cdots,x_{r-1}),$

where $Q(x_{1},\cdots,x_{r-1})$ is given as in Lemma 13. Since
$\frac{3q-8}{4}\leq k\leq q-4$, $1\leq r-3\leq\frac{q-4}{4}<\frac{q}{4}$. By
Lemma 13, there exist pairwise distinct elements
$\alpha_{1},\cdots,\alpha_{r-3}\in\mathbb{F}_{q}$ and
$c\in\mathbb{F}_{q}^{*}$, such that

$Q(\alpha_{1},\cdots,\alpha_{r-3})=g(c),$

where $g(c)$ is defined as in Lemma 13. Note that

$\displaystyle Q(\alpha_{1},\cdots,\alpha_{r-3},x_{r-2},x_{r-1})$
$\displaystyle=$
$\displaystyle(x_{r-2}+\sum_{i=1}^{r-3}\alpha_{i}+\theta^{-1})(x_{r-1}+\sum_{i=1}^{r-3}\alpha_{i}+\theta^{-1})(x_{r-2}+x_{r-1})+Q(\alpha_{1},\cdots,\alpha_{r-3})$
$\displaystyle=$ $\displaystyle XY(X+Y)+g(c),$

where $X=x_{r-2}+\sum_{i=1}^{r-3}\alpha_{i}+\theta^{-1}$ and
$Y=x_{r-1}+\sum_{i=1}^{r-3}\alpha_{i}+\theta^{-1}$. By Lemma 11, ${\rm
N}(Q(\alpha_{1},\cdots,\alpha_{r-3},x_{r-2},x_{r-1}))={\rm
N}(XY(X+Y)+g(c))\geq q-2.$ Since $g(c)\neq 0$,
$Q(\alpha_{1},\cdots,\alpha_{n-2},x_{r-2,}x_{r-1})=0$ implies that
$x_{n-1}\neq x_{n}$. Given $x_{r-2}$ (resp. $x_{r-1}$)
$\in\\{\alpha_{1},\cdots,\alpha_{r-3}\\}$, there exist at most two $x_{r-1}$’s
(resp. $x_{r-2}$’s), such that
$Q(\alpha_{1},\cdots,\alpha_{r-3},x_{r-2},x_{r-1})=0$. Thus from $q-2>4(r-3)$,
we obtain that there exist
$\alpha_{r-2}\neq\alpha_{r-1}\in\mathbb{F}_{q}^{*}\backslash\\{\alpha_{1},\cdots,\alpha_{r-3}\\}$
such that $Q(\alpha_{1},\cdots,\alpha_{r-1})=0$, i.e., there exist pairwise
distinct elements $\alpha_{1},\cdots,\alpha_{r-1}\in\mathbb{F}_{q}$, such that
$\det\big{(}\bm{c}_{r,\theta}(\alpha_{1})|\bm{c}_{r,\theta}(\alpha_{2})|\cdots|\bm{c}_{r,\theta}(\alpha_{r-1})|\bm{w}^{\top}\big{)}=0$.
By Proposition 8, $\bm{u}$ is not a deep hole of ${\rm
TRS}_{k}(\mathbb{F}_{q},\theta)$.

## References

  * [1] A. McLoughlin, “The complexity of computing the covering radius of a code,” _IEEE Trans. Inf. Theory_ , vol. IT-30, no. 6, pp. 800–804, Nov. 1984.
  * [2] W. C. Huffman and V. Pless, _Fundamentals of Error-Correcting Codes. Cambridge_ , U.K.: Cambridge Univ. Press, 2003.
  * [3] A. Dur, “On the covering radius of Reed-Solomon codes,” _Discrete Math._ , vol. 126, pp. 99–105, 1994.
  * [4] O.S. Rothaus, “On ‘bent’ functions,” _J. Combin. Theory Ser. A_ , vol. 20, pp. 300–305, 1976.
  * [5] Q. Cheng and E. Murray, “On deciding deep holes of Reed–Solomon codes,” in _Theory and Applications of Models of Computation_ (Lecture Notes in Computer Science), vol. 4484. Berlin, Germany: Springer, pp. 296–305, 2007.
  * [6] J. Li and D. Wan, “On the subset sum problem over finite fields,” _Finite Fields Appl._ , vol. 14, no. 4, pp. 911–929, 2008.
  * [7] Y. Li and D. Wan, “On error distance of Reed–Solomon codes,” _Sci. China A, Math._ , vol. 51, no. 11, pp. 1982–1988, 2008.
  * [8] J. Li and D. Wan, “A new sieve for distinct coordinate counting,” _Sci. China Math._ , vol. 53, no. 9, pp. 2351–2362, 2010.
  * [9] R. Wu and S. Hong, “On deep holes of standard Reed–Solomon codes,” _Sci. China Math._ , vol. 55, no. 12, pp. 2447–2455, 2012.
  * [10] G. Zhu and D. Wan, “Computing error distance of Reed–Solomon codes,” in _Theory and Applications of Models of Computation_ (Lecture Notes in Computer Science), vol. 7287. Berlin, Germany: Springer-Verlag, pp. 214–224.
  * [11] A. Cafure, G. Matera, and M. Privitelli, “Singularities of symmetric hypersurfaces and an application to Reed–Solomon codes,” _Adv. Math. Commun._ , vol. 6, no. 1, pp. 69–94, 2012.
  * [12] J. Zhang, F.-W. Fu, and Q.-Y. Liao, “New deep holes of generalized Reed–Solomon codes,” _Sci. Sin. Math._ , vol. 43, no. 7, pp. 727–740, 2013\.
  * [13] M. Keti and D. Wan, “Deep holes in Reed–Solomon codes based on Dickson polynomials,” _Finite Fields Their Appl._ , vol. 40, pp. 110–125, Jul. 2016.
  * [14] J. Zhuang, Q. Cheng, and J. Li, “On determining deep holes of generalized Reed–Solomon codes,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 1, pp. 199–207, Jan. 2016.
  * [15] K. Kaipa, “Deep holes and MDS extensions of Reed–Solomon codes,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 8, pp. 4940–4948, Aug. 2017.
  * [16] J. Zhang, D. Wan, and K. Kaipa, “Deep holes of projective Reed–Solomon codes,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 4, pp. 2392–2401, Apr. 2020.
  * [17] V. Guruswami and A. Vardy, “Maximum-likelihood decoding of Reed–Solomon codes is NP-hard,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 7, pp. 2249–2256, Jul. 2005.
  * [18] G. Seroussi and R. M. Roth, “On MDS extensions of generalized Reed–Solomon codes,” _IEEE Trans. Inf. Theory_ , vol. 32, no. 3, pp. 349–354, May 1986.
  * [19] P. Beelen, S. Puchinger, and J. R. N. Nielsen, “Twisted Reed–Solomon codes,” in _Proc. IEEE Int. Symp. Inf. Theory_ (ISIT), Jun. 2017, pp. 1–15.
  * [20] P. Beelen, S. Puchinger, and J. Rosenkilde, “Twisted Reed–Solomon codes,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 5, pp. 3047–3061, May 2022.
  * [21] D. Huang, Q. Yue, Y. Niu, and X. Li, “MDS or NMDS self-dual codes from twisted generalized Reed–Solomon codes,” _Des., Codes Cryptogr._ , vol. 89, no. 9, pp. 2195–2209, Sep. 2021.
  * [22] H. Liu and S. Liu, “Construction of MDS twisted Reed–Solomon codes and LCD MDS codes,” _Des., Codes Cryptogr._ , vol. 89, no. 9, pp. 2051–2065, Sep. 2021.
  * [23] J. Sui, Q. Yue, X. Li, and D. Huang, “MDS, Near-MDS or 2-MDS Self-Dual Codes via Twisted Generalized Reed-Solomon Codes,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 12, pp. 7832-7841, Dec. 2022.
  * [24] J. Zhang, Z. Zhou, and C. Tang, “A class of twisted generalized Reed–Solomon codes,” _Des., Codes Cryptogr._ , vol. 90, no. 7, pp. 1649–1658, Jul. 2022.
  * [25] J. Sui, Q. Yue, X. Li, and D. Huang, “MDS, near-MDS or 2-MDS self-dual codes via twisted generalized Reed–Solomon codes,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 12, pp. 7832–7841, Dec. 2022.
  * [26] P. Beelen, M. Bossert, S. Puchinger, and J. Rosenkilde, “Structural properties of twisted Reed–Solomon codes with applications to cryptography,” in _Proc. IEEE Int. Symp. Inf. Theory_ (ISIT), Jun. 2018, pp. 946–950.
  * [27] J. Lavauzelle and J. Renner, “Cryptanalysis of a system based on twisted Reed–Solomon codes,” _Des., Codes Cryptogr._ , vol. 88, no. 7, pp. 1285–1300, Jul. 2020.
  * [28] D. Hiren, “The MDS Conjecture and related questions in finite geometry,” Master Thesis, 2019.
  * [29] J. T. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities,” _J. ACM_ , vol. 27, no. 4, pp.701–717, 1980.
  * [30] R. Zippel, “Probabilistic algorithms for sparse polynomials,” In _Proceedings of the International Symposium on Symbolic and Algebraic Computation_ , Springer-Verlag, pp. 216–226, 1979
  * [31] T. Ho et al., “A random linear network coding approach to multicast,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 10, pp. 4413–4430, Oct. 2006.
  * [32] R. Lidl and H. Niederreiter, _Finite Fields_. Cambridge, U.K.: Cambridge Univ. Press, 1997.
  * [33] D. Schipani and M. Elia, “Gauss sums of the cubic character over $GF(2^{m})$: an elementary derivation,” Bull. Pol. Acad. Sci. Math. vol. 59, pp. 11–18, 2011.