\chapter{The Deep Hole Problem of Generalized Reed-Solomon Codes}

\section{Statement of the problem}
\begin{definition}
Given a generalized Reed-Solomon code $RS_q(D,k)$ with $|D|=n$, deep holes of $RS_q(D,k)$ are vectors in $\F_q^n$
whose distance with the code is $n-k$. The deep hole problem is to determine all the deep holes.
\end{definition}

\begin{remark}
The problem of deciding whether a received word is a deep hole
for generalized Reed-Solomon codes is co-NP-complete \cite{CM07, GV05}.
\end{remark}

\begin{definition}
Given a word $\u=(u_1,u_2,\ldots,u_n)\in \F_q^n$, the Lagrange interpolating polynomial of $\u$ is defined as:
$$u(x)=\sum_{i=1}^nu_i\frac{\prod_{j\neq i}(x-\alpha_j)}{\prod_{j\neq i}(\alpha_i-\alpha_j)}\in \F_q[x],$$
where $D=\{\alpha_1,\ldots,\alpha_n\}$ is the evaluation set. 
\end{definition}

\begin{remark} 
The Lagrange interpolating polynomial is the only polynomial in $\F_q[x]$ of
degree less than $n$ that satisfies $u(\alpha_i)=u_i,1\leqslant i
\leqslant n.$
\end{remark} 

\begin{definition}
We say that a function \textit{$u(x)$ generates} a vector $\u\in\F_q^n$ if
\[
\u=(u(\alpha_1),u(\alpha_2),\ldots,u(\alpha_n)).
\]
\end{definition}

We have the following conclusions:
\begin{enumerate}
\item If $deg(u)\leqslant k-1$, then $\u\in RS_q(D,k)$ by definition and
$d(\u,RS_q(D,k))=0$.
\item If $deg(u)=k$, then it can be shown that $\u$ is a deep hole by the following proposition \cite{lw08},
i.e., $d(\u, RS_q(D,k))=n-k$.
\end{enumerate}

\begin{proposition} \cite{lw08}
For $k \leqslant deg(u) \leqslant n-1$, we have the inequality
$$n-deg(u)\leqslant d(u, RS_q(D,k)) \leqslant n-k.$$
\end{proposition}

When the degree of $u(x)$ becomes larger than $k$, the situation
becomes complicated for GRS codes. However, in
the case of singly-extended GRS codes defined over fields with odd characteristic, the situation seems to
be much simpler. Cheng and Murray \cite{CM07} conjectured in 2007
that the vectors generated by polynomial of degree $k$ are the only
possible deep holes.

\begin{conjecture}\label{conj1} \cite{CM07}
Let $q$ be an odd prime power. A word $\u$ is a deep hole of $RS_q(\F_q, k)$ if and only if $\deg(u)=k$.
\end{conjecture}

There is an analogous conjecture for deep holes of primitive Reed-Solomon codes by Wu and Hong \cite{WH12}.
\begin{conjecture}\label{conj2} \cite{WH12}
Let $q$ be an odd prime power. A word $\u$ is a deep hole of $RS_q(\F_q^*, k)$ if and only if it satisfies one
of the following conditions:
\begin{enumerate}
\item $u(x)=ax^k+f_{\leqslant k-1}(x), a\neq 0,$
\item $u(x)=bx^{q-2}+f_{\leqslant k-1}(x), b\neq 0,$
\end{enumerate}
where $f_{\leqslant k-1}(x)$ denotes a polynomial with degree not larger
than $k-1$.
\end{conjecture}

\begin{remark}
Parts of the content in this chapter are joint work with Qi Cheng and Jiyou Li and previously appeared in \cite{CLZ13}.
\end{remark}

\section{Related work}
Cheng and Murray \cite{CM07} got the first result related to Conjecture \ref{conj1} by reducing the problem to the existence of rational points on a hypersurface over $\F_q$.
\begin{theorem} \cite{CM07} \label{CM}
Let $\u\in \F_q^{q}$ such that $1\leqslant \delta:=\deg(u)-k\leqslant q-1-k$. If $q\geqslant \max(k^{7+\epsilon},\delta^{\frac{13}{3}+\epsilon})$
for some constant $\epsilon>0$, then $\u$ is not a deep hole.
\end{theorem}

Following an approach similar to one in Cheng and Wan \cite{CW07}, Li and Wan \cite{LJW08} improved Theorem \ref{CM} with Weil's character sum estimate.
\begin{theorem} \cite{LJW08}
Let $\u\in \F_q^q$ such that $1\leqslant \delta:=\deg(u)-k\leqslant q-1-k$. If
\[
q>\max((k+1)^2,\delta^{2+\epsilon}),k>(\frac{2}{\epsilon}+1)\delta+\frac{8}{\epsilon}+2
\]
for some constant $\epsilon>0$, then $\u$ is not a deep hole.
\end{theorem}

Liao \cite{Liao11} established the following result:
\begin{theorem} \cite{Liao11}
Let $r\geqslant 1$ be an integer. For any received word $\u\in \F_q^q, r\leqslant \delta:=\deg(u)-k\leqslant q-1-k$, if
$$
q>\max(2\binom{k+r}{2}+\delta,d^{2+\epsilon}),k>(\frac{2}{\epsilon}+1)\delta+\frac{2r+4}{\epsilon}+2
$$
for some constant $\epsilon>0$, then $d(\u,RS_q(\F_q,k))\leqslant q-k-r$, which implies that $\u$ is not a deep hole.
\end{theorem}

Cafure, Matera, and Privitelli \cite{CMP12} proved the following result with tools of algebraic geometry:
\begin{theorem}\cite{CMP12}
Let $\u\in \F_q^q$ such that $1\leqslant \delta:=\deg(u)-k\leqslant q-1-k$. If
\[
q>\max((k+1)^2,14\delta^{2+\epsilon}),k>(\frac{2}{\epsilon}+1)\delta,
\]
for some constant $\epsilon>0$, then $\u$ is not a deep hole.
\end{theorem}

Using Weil's character sum estimate and Li-Wan's new sieve \cite{LW10} for distinct coordinates counting, Zhu and Wan \cite{ZW12}
showed the following result:
\begin{theorem} \cite{ZW12}
Let $r\geqslant 1$ be an integer. For any received word $\u\in \F_q^q, r\leqslant \delta:=\deg(u)-k\leqslant q-1-k$, there are positive
constants $c_1$ and $c_2$ such that if
$$
\delta<c_1q^{1/2},(\frac{\delta+r}{2}+1)\log_2(q)<k<c_2q,
$$
then $d(\u,RS_q(\F_q,k))\leqslant q-k-r$, which implies that $\u$ is not a deep hole.
\end{theorem}





%This paper is organized as follows: Section 2 presents some preliminaries; 
%Section 3 describes the idea of the deep hole tree; Section 4 demonstrates 
%the proof of Theorem \ref{mainthm}. 
% The proof of some lemmas and Theorem 
% \ref{geometrythm} are included in the appendices.


\section{A criterion for deep holes of MDS codes}
By definition, deep holes of a linear code are words that have a maximum distance to the code.
In the case of MDS codes, there is another way to characterize the deep hole,
which connects the concept of deep holes with the MDS codes.
The following is well known:
\begin{proposition}\label{prop}
Let $\F_q$ be a finite field with characteristic $p$. Suppose $G$ is
a generator matrix for an MDS code $C=[n,k]_q$ with covering radius $\rho=n-k$, then $\u\in \F_q^n$ is a deep hole of $C$ if and only if
$$
G'=\left[
\begin{array}{c}
 G\\ \hline
 \u
\end{array}\right]
$$
generates another MDS code.
\end{proposition}

We give a proof below for the sake of completeness.

\begin{proof}
$\Rightarrow$ Suppose $\u$ is a deep hole of $C=[n,k]_q$. We show that $G'$ is a generator matrix for another MDS code.
Equivalently, we show that any $k+1$ columns of $G'$ are linearly independent.

Assume there exist $k+1$ columns of $G'$ which are linearly dependent.  Without loss of generality, 
we assume that the first $k+1$ columns of $G'$ are linear dependent. Consider the submatrix consisting of the intersection 
elements of the first $k+1$ rows and the first $k+1$ columns of $G'$. Hence there exist $a_1,\ldots,a_k\in\F_q$, not all zero, such that
$$(u_1,\ldots,u_{k+1})=a_1\r_{1,k+1}+\cdots+a_k\r_{k,k+1},$$
where $\r_{i,k+1}$ is the vector consisting of the first $k+1$ elements of the $i$-th row of $G$ 
for $1\leqslant i \leqslant k$. Let $\v=a_1\r_1+\cdots+a_k\r_k\in C$, where $\r_i$ is the $i$-th row of $G$ for $1\leqslant i \leqslant k$. We have
$$d(\u,\v)\leqslant n-(k+1)<\rho,$$
which is a contradiction to the assumption that $u$ is a deep hole of $C$.

$\Leftarrow$ Now suppose $G'$ is a generator matrix for an MDS code, i.e., any $k+1$ columns of $G'$ are linearly independent.
We show that $d(\u,C)=n-k$.

Assume that $d(\u,C)<n-k.$ Equivalently, there exist $a_1,\ldots,a_k\in\F_q$ such that $\u$ and $\v=a_1\r_1+\cdots+a_k\r_k$ have
more than $k$ common coordinates, where $\r_i$ is the $i$-th row of $G$ for $1\leqslant i \leqslant k$. Without loss of generality, 
we assume that the first $k+1$ coordinates of $\u$ and $\v$ are the same. Consider the submatrix consisting of the first $k+1$ columns of $G'$. 
Since the rank of the matrix is less than $k+1$,
thus the first $k+1$ columns of $G'$ are linearly dependent, which contradicts to the assumption.
\end{proof}


\section{Classifying deep holes using deep hole trees}

\subsection{Construction of the deep hole tree}
Let $\F_q = \{ \alpha_1, \alpha_2, \cdots, \alpha_{q}=0\} $.
The polynomials in $\F_q [x]$ of degree less than $q$ form a $\F_q$-linear
space,
% Given a polynomial $f(x)\in \F_q[x]$ with degree $q-1$, we can write
% \[
% f(x)=h(x)+l(x),
% \]
% where $h(x)$ is the part of $f(x)$ with degree greater than or equal to $k$ and $l(x)$ is the part of $f(x)$ with degree less than $k$. Expanding $h(x)$ 
with a basis
\[
\{1,x,\ldots,x^{k-1},\prod_{i=1}^{k}(x-\alpha_i),\ldots,\prod_{i=1}^{q-1}(x-\alpha_i)\}. 
\]
Given a polynomial $f(x)\in \F_q[x]$ with degree $q-1$
we have
\[
f(x)=l(x)+c_1\prod_{i=1}^{k}(x-\alpha_i)+\cdots+c_{q-k}\prod_{i=1}^{q-1}(x-\alpha_i),
\]
where $l(x)$ is of degree less than $k$. We want to determine when $f(x)$ generates a deep hole of $RS_q(\F_q,k)$. By Proposition \ref{prop}, $f(x)$ generates a deep hole if and only if
$$
G'=\left[
\begin{array}{c}
 G\\ \hline
 \u
\end{array}\right]
$$
generates an MDS code, where $G$ is the generator matrix of $RS_q(\F_q,k)$, and $\u=(f(\alpha_1),\ldots,f(\alpha_q))$.
%, where $\alpha_q=0$.

Observe that the function, which generates a deep hole for $RS_q(D_2,k)$, also generates a deep hole for $RS_q(D_1,k)$ if $D_1\subset D_2$.
Instead of considering the deep holes for $RS_q(\F_q,k)$ at the first step, we propose to consider a smaller evaluation set at the beginning and make it increase gradually.
To be more precise,
firstly we determine $c_1$ over $D_1=\{\alpha_1,\ldots,\alpha_{k+1}\}$, then we determine $c_2$ over $D_2=\{\alpha_1,\ldots,\alpha_{k+2}\}$  based on the knowledge of $c_1$, so on and so forth. We present the result as a tree, which we shall call a \textit{deep hole tree}.

\iffalse
We construct the deep hole tree as follows:
\begin{itemize}
\item The root node is $1$ without loss of generality, i.e., $c_1=1$.
\item The children $\{c_{i+1}\}$ of a node $c_i,1\leqslant i \leqslant q-k-1$ are defined as follows: given the ancestors $(c_1,\ldots,c_i)$, for $\gamma\in \F_q$, if
\[
c_1\prod_{i=1}^{k}(x-\alpha_i)+\cdots+c_{i}\prod_{i=1}^{k+i-1}(x-\alpha_i)+\gamma\prod_{i=1}^{k+i}(x-\alpha_i)
\]
satisfies the property of the function which generates a deep hole as in Proposition \ref{prop}, then $\gamma$ is a child of $c_i$.
\end{itemize}
\fi

% \begin{remark}
% The problem of counting the number $n_1$ of deep holes of $RS_q(D,k)$, where $D=\{\alpha_1,\ldots,\alpha_l\}, k+1\leqslant l \leqslant q$, is reduced to the one of counting the number $n_2$ of the nodes in the deep hole tree with depth $l-k$ by the relation
% $$n_1=n_2(q-1)q^k.$$
% \end{remark}

\begin{remark} \label{expdeep}
Wu and Hong \cite{WHarx12} showed that if $D=\F_q\setminus\{\gamma_1,\ldots,\gamma_r\}$ then $f_{\gamma_i}(x)=\frac{1}{x-\gamma_i}$ generates a deep hole for $RS_q(D,k)$, where $1\leqslant i \leqslant r$. 
\end{remark}

\begin{definition}
Let $RS_q(D,k)$ be a given code with $D=\F_q\setminus\{\gamma_1,\ldots,\gamma_r\}$. We will call  deep holes
generated by $f(x)=x^k$ and $f_{\gamma_i}(x)=\frac{1}{x-\gamma_i}$,$1\leqslant i \leqslant r$, \textit{expected deep holes}.
\end{definition}

We can also obtain the expected deep holes from Proposition \ref{prop}.
\begin{proposition} \label{expdeephole}
Let $RS_q(D,k)$ be a given code with $D=\{\alpha_1,\ldots,\alpha_n\}$. We have
\begin{enumerate}
\item If $f(x)=x^k\in\F_q[x]$, then $f(x)$ generates a deep hole. 
\item If $f(x)=\frac{1}{x-\gamma}$, $\gamma\in \F_q\setminus D$, then $f(x)$ generates a deep hole.
\end{enumerate}
\end{proposition}

\begin{proof}
Let the generator matrix of $RS_q(D,k)$ be
\[
G=
\begin{bmatrix}
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} 
\end{bmatrix}.
\]

\textbf{Case 1.} Let $f(x)=x^k$. Consider the matrix
\[
G'=
\begin{bmatrix}
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{bmatrix}.
 \]
For any subset $\{\beta_1,\ldots,\beta_{k+1}\}\subset D$, the submatrix of $G'$ corresponding 
to the subset is given by
\[
M =
\begin{bmatrix}
1           & 1          & \cdots      & 1         \\
\beta_1    & \beta_2   & \cdots      & \beta_{k+1}  \\
\vdots      & \vdots     & \ddots      & \vdots  \\
\beta_1^{k-1} & \beta_2^{k-1} & \cdots & \beta_{k+1}^{k-1} \\
\beta_1^k    & \beta_2^k  & \cdots   & \beta_{k+1}^k 
\end{bmatrix}.
 \]
Since $\det(M)=\prod_{1\leqslant i < j\leqslant k+1}(\beta_j-\beta_i)\neq 0$, any $k+1$ columns
of $G'$ are linearly independent. From Proposition \ref{prop}, $f(x)=x^k$ generates a deep hole.

\textbf{Case 2.} Let $f(x)=\frac{1}{x-\gamma}$, where $\gamma\in \F_q\setminus D$.
Consider the matrix
\[
G'=
\begin{bmatrix}
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} \\
\frac{1}{\alpha_1-\gamma}    & \frac{1}{\alpha_2-\gamma}  & \cdots   & \frac{1}{\alpha_n-\gamma} 
\end{bmatrix}.
\] 
For any subset $\{\beta_1,\ldots,\beta_{k+1}\}\subset D$, the submatrix of $G'$ corresponding 
to the subset is given by
\[
M =
\begin{bmatrix}
1           & 1          & \cdots      & 1         \\
\beta_1    & \beta_2   & \cdots      & \beta_{k+1}  \\
\vdots      & \vdots     & \ddots      & \vdots  \\
\beta_1^{k-1} & \beta_2^{k-1} & \cdots & \beta_{k+1}^{k-1} \\
\frac{1}{\beta_1-\gamma}    &\frac{1}{\beta_2-\gamma}  & \cdots   & \frac{1}{\beta_{k+1}-\gamma} 
\end{bmatrix}.
\]
Since $\prod_{i=1}^{k+1}(\beta_i-\gamma)\det(M)=(-1)^k\prod_{1\leqslant i < j\leqslant k+1}(\beta_j-\beta_i)$,
we deduce $\det(M)\neq 0$. From Proposition \ref{prop}, $f(x)=\frac{1}{x-\gamma}$ generates a deep hole.

\end{proof}



Motivated by Proposition \ref{expdeephole}, we construct the \textit{expected deep hole tree} as follows:
\begin{enumerate}
\item The root node is $1$ without loss of generality, i.e., $c_1=1$.
\item There are $p-k-1$ branches of the tree, each with distinct length in $[2,p-k]$. And we designate the sequence of nodes in a branch with length $l$ as $\mathbf{b}_l$.
    \begin{itemize}
    \item If $l=p-k$, then $\mathbf{b}_{p-k}=(0,\ldots,0)$.
%    \item If $2\leqslant l \leqslant p-k-1$, then $b_l=(c_1,\ldots,c_l)$, where $c_1=1,c_{i+1}=\frac{c_i}{l-i},1\leqslant i \leqslant l-1$.
    \item If $2\leqslant l \leqslant p-k-1$, then $\mathbf{b}_l=(c_1,\ldots,c_l)$, where $f=\frac{1}{x-\alpha_{l+1}}$ is equivalent to $c_1\prod_{i=1}^{k}(x-\alpha_i)+\cdots+c_{l}\prod_{i=1}^{k+l-1}(x-\alpha_{i})$.
    \end{itemize}
\end{enumerate}

\begin{proposition}\label{exptree}
The expected deep hole tree is a subtree of the full deep hole tree.
%The branch $b_{p-k}$ is equivalent to the function $x^k$, and the branch $b_l$ is equivalent to the function $\frac{1}{x-(l+k+1)}$ over the evaluation set $D=\{1,2,\ldots,k+l\}$, %where the equivalence is up to a constant multiplication and an addition of a function with degree less than $k$.
\end{proposition}
\begin{proof}
This follows from Remark \ref{expdeep}.
\end{proof}

Now we can construct the full deep hole tree based on the expected deep hole tree.
\begin{enumerate}
\item The root node is $1$ without loss of generality, i.e., $c_1=1$.
\item The children $\{c_{i+1}\}$ of a node $c_i,1\leqslant i \leqslant q-k-1$ are defined as follows: given the ancestors $(c_1,\ldots,c_i)$, for $\gamma\in \F_q$, if $\gamma$ is the
child of $c_i$ in the expected deep hole tree, then keep it; otherwise, if
\[
c_1\prod_{i=1}^{k}(x-\alpha_i)+\cdots+c_{i}\prod_{i=1}^{k+i-1}(x-\alpha_i)+\gamma\prod_{i=1}^{k+i}(x-\alpha_i)
\]
satisfies the property of the function which generates a deep hole as in Proposition \ref{prop}, then $\gamma$ is a child of $c_i$.
\end{enumerate}
That is, we keep the nodes of the expected deep hole tree and add additional ones if necessary. Now we illustrate the procedure to construct the deep hole tree by some examples.

% Ref: http://www.texample.net/tikz/examples/merge-sort-recursion-tree/
\begin{example}
Let $p=7,k=2$. The evaluation set is ordered such that $\alpha_i=i,1\leqslant i \leqslant 7$.
The expected deep hole tree is shown in Figure \ref{fig:p7k2}.


\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture}[every tree node/.style={draw,circle},edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},sibling distance=1 cm]
\Tree [.\node (1) {1};
        [.1 ] % leave a space before ] 
        [.4 [.4 ] ]
        [.5 [.6 [.6 ]]] 
        [.0 [.0 [.0 [.0 ]]]]
      ]


\begin{scope}[xshift=2in,every tree node/.style={},edge from parent path={}]
\Tree [.{$\Leftarrow c_1,\{1,2,3\}$} [.{$\Leftarrow c_2,\{1,2,3,4\}$} [.{$\Leftarrow c_3,\{1,2,3,4,5\}$} [.{$\Leftarrow c_4,\{1,2,3,4,5,6\}$} [.{$\Leftarrow c_5,\{1,2,3,4,5,6,7\}$} ] ] ] ] ]
\end{scope}
\end{tikzpicture}
\caption{Expected deep hole tree for $p=7,k=2$} \label{fig:p7k2}
\end{figure}
\vspace{5 mm} 

\end{example}

\begin{remark} We notice the following in Figure \ref{fig:p7k2}:
\begin{enumerate}
\item The root corresponds to the evaluation set $D_1=\{1,2,3\}$. The expected deep holes are generated by functions equivalent to
$\prod_{i=1}^{2}(x-i)$. 
\item In depth 2, the evaluation set is $D_2=\{1,2,3,4\}$. One of the expected deep holes is generated by the function $\prod_{i=1}^{2}(x-i)+\prod_{i=1}^{3}(x-i)$,
which is equivalent to $f_5=\frac{1}{x-5}$. 
\item In depth 3, the evaluation set is $D_3=\{1,2,3,4,5\}$. One of the expected deep holes is generated by the function $\prod_{i=1}^{2}(x-i)+4\prod_{i=1}^{3}(x-i)+4\prod_{i=1}^{4}(x-i)$, which is equivalent to $f_6=\frac{1}{x-6}$. 
\item In depth 4, the evaluation set is $D_4=\{1,2,3,4,5,6\}$. One of the expected deep holes is generated by the function $\prod_{i=1}^{2}(x-i)+5\prod_{i=1}^{3}(x-i)+6\prod_{i=1}^{4}(x-i)+6\prod_{i=1}^{5}(x-i)$, which is equivalent to $f_0=\frac{1}{x}$. 
\item In depth 5, the evaluation set is $D_5=\{1,2,3,4,5,6,7\}$. One of the expected deep holes is generated by the function $\prod_{i=1}^{2}(x-i)$.
\end{enumerate}
\end{remark}

\begin{example} Let $p=7,k=2$. The evaluation set is ordered such that $\alpha_i=i,1\leqslant i \leqslant 7$.
The full deep hole tree is shown in Figure \ref{fig:fullp7k2}.

\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture}[every tree node/.style={draw,circle},edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},sibling distance=.5cm]
\Tree [.\node (1) {1};
        [.\node (1) {1}; \edge[dashed];[.\node (3) {3}; ] \edge[dashed];[.\node (6) {6}; ]] 
        [.4 [.4 ] ]
        [.\node (5) {5}; \edge[dashed];[.\node (1) {1}; ] \edge[dashed];[.\node (3) {3}; ][.\node (6) {6}; [.\node (6) {6};]]] 
        [.0 [.0 [.0 [.0 ]]]]
      ]


\begin{scope}[xshift=3in,every tree node/.style={},edge from parent path={}]
\Tree [.{$\Leftarrow c_1,\{1,2,3\}$} [.{$\Leftarrow c_2,\{1,2,3,4\}$} [.{$\Leftarrow c_3,\{1,2,3,4,5\}$} [.{$\Leftarrow c_4,\{1,2,3,4,5,6\}$} [.{$\Leftarrow c_5,\{1,2,3,4,5,6,7\}$} ] ] ] ] ]
\end{scope}
\end{tikzpicture}
\caption{Full deep hole tree for $p=7,k=2$} \label{fig:fullp7k2}
\end{figure}
\vspace{5 mm} 

\end{example}

\begin{remark}
There are four more nodes here than the expected deep hole tree. They are all in depth three.  
\begin{enumerate}
\item The first additional deep hole is generated by the function $\prod_{i=1}^{2}(x-i)+\prod_{i=1}^{3}(x-i)+3\prod_{i=1}^{4}(x-i)$. 
\item The second additional deep hole is generated by the function $\prod_{i=1}^{2}(x-i)+\prod_{i=1}^{3}(x-i)+6\prod_{i=1}^{4}(x-i)$.
\item The third additional deep hole is generated by the function $\prod_{i=1}^{2}(x-i)+5\prod_{i=1}^{3}(x-i)+\prod_{i=1}^{4}(x-i)$.
\item The fourth additional deep hole is generated by the function $\prod_{i=1}^{2}(x-i)+5\prod_{i=1}^{3}(x-i)+3\prod_{i=1}^{4}(x-i)$.
\end{enumerate}
\end{remark}


\begin{example}
Let $p=11,k=5$.  The evaluation set is ordered such that $\alpha_i=i,1\leqslant i \leqslant 11$.
The expected deep hole tree and full deep hole tree are shown in Figure \ref{fig:p11k5}.

\vspace{10 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture}[every tree node/.style={draw,circle},edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},sibling distance=.5cm]
\Tree [.\node (1) {1};
        [.1 ] 
        [.6 [.6 ] ]
        [.4 [.2 [.2 ] ] ] 
        [.3 [.1 [.6 [.6 ] ] ] ] 
        [.0 [.0 [.0 [.0 [.0 ] ] ] ] ]
      ]


\begin{scope}[xshift=3in,every tree node/.style={},edge from parent path={}]
\Tree [.{$\Leftarrow c_1,\{1,2,\ldots,6\}$} [.{$\Leftarrow c_2,\{1,2,\ldots,7\}$} [.{$\Leftarrow c_3,\{1,2,\ldots,8\}$} [.{$\Leftarrow c_4,\{1,2,\ldots,9\}$} [.{$\Leftarrow c_5,\{1,2,\ldots,10\}$} [.{$\Leftarrow c_6,\{1,2,\ldots,11\}$} ] ] ] ] ] ]
\end{scope}
\end{tikzpicture}
\caption{Expected and full deep hole tree for $p=11,k=5$} \label{fig:p11k5}
\end{figure}
\vspace{5 mm} 
\end{example}



\begin{example}
Let $p=13,k=7$. The evaluation set is ordered such that $\alpha_i=i,1\leqslant i \leqslant 13$.
The expected and full deep hole trees are shown in Figure \ref{fig:p13k7}.
% scale of a tikz picture
% http://tex.stackexchange.com/questions/26846/how-to-scale-a-tikzpicture-including-texts
%\ovalbox{
\vspace{5 mm}
\begin{figure}[h]
\centering
\begin{tikzpicture}[every tree node/.style={draw,circle},edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},sibling distance=.5cm]
\Tree [.\node (1) {1};
        [.1 ] 
        [.7 [.7 ] ]
        [.9 [.11 [.11 ] ] ] 
        [.10 [.12 [.6 [.6 ] ] ] ] 
        [.0 [.0 [.0 [.0 [.0 ] ] ] ] ]
      ]


\begin{scope}[xshift=3in,every tree node/.style={},edge from parent path={}]
\Tree [.{$\Leftarrow c_1,\{1,2,\ldots,8\}$} [.{$\Leftarrow c_2,\{1,2,\ldots,9\}$} [.{$\Leftarrow c_3,\{1,2,\ldots,10\}$} [.{$\Leftarrow c_4,\{1,2,\ldots,11\}$} [.{$\Leftarrow c_5,\{1,2,\ldots,12\}$} [.{$\Leftarrow c_6,\{1,2,\ldots,13\}$} ] ] ] ] ] ]
\end{scope}

\end{tikzpicture}
\caption{Expected and full deep hole tree for $p=13,k=7$} \label{fig:p13k7}
\end{figure}
\vspace{5 mm} 
\end{example}





\subsection{Some lemmas}
\begin{lemma} \label{basis}
In depth $d=2$, the nodes are the same in both the expected deep hole tree and full deep hole tree.
\end{lemma}
%The proof of Lemma \ref{basis} is in Appendix C.
\begin{proof}
We show that in depth $d=2$, the nodes are the same in both the expected deep hole tree and full deep hole tree.

In depth $d=2$, the evaluation set is $D=\{\alpha_1,\alpha_2,\ldots,\alpha_{k+2}\}$. 
Designate the set of nodes in depth $2$ of the expected deep hole tree as $S$.
Firstly, we show that $|S|=p-(k+1)$. This follows from the fact that the equivalent functions of the form 
\[f(x)=\prod_{i=1}^{k}(x-\alpha_i)+c_2\prod_{i=1}^{k+1}(x-\alpha_i),\quad c_2\in \F_p,\]
for $f(x)=x^k$ and $f_{\delta}(x)=\frac{1}{x-\delta}$
take the same value at $\beta \in D\setminus\{\alpha_{k+2}\}$ but pairwise different values at $\alpha_{k+2}$,
where $\delta\in \F_p\setminus D$.

\iffalse
% the following is to show c_2 are pairwise distinct
% the above is a simpler argument
Considering the following square matrix
\[
G=
\begin{bmatrix}
1           & 1          & \cdots      & 1         \\
\vdots      & \vdots     & \ddots      & \vdots  \\
\alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_{k+2}^{k-1} \\
\frac{1}{\alpha_1-\delta_1}   & \frac{1}{\alpha_2-\delta_1}   & \cdots      & \frac{1}{\alpha_{k+2}-\delta_1} \\
\frac{1}{\alpha_1-\delta_2}   & \frac{1}{\alpha_2-\delta_2}   & \cdots      & \frac{1}{\alpha_{k+2}-\delta_2}
\end{bmatrix},
 \]
we compute
\[
\prod_{i=1}^{k+2}(\alpha_i-\delta_1)\det(G) =
\begin{vmatrix}
\alpha_1-\delta_1                             & \cdots        & \alpha_{k+2}-\delta_1                               \\
\alpha_1*(\alpha_1-\delta_1)                  & \cdots        & \alpha_{k+2}*(\alpha_{k+2}-\delta_1)                   \\
\vdots                                        & \ddots        & \vdots                                           \\
\alpha_1^{k-1}*(\alpha_1-\delta_1)            & \cdots        & \alpha_{k+2}^{k-1}*(\alpha_{k+2}-\delta_1)                \\
1                                             & \cdots        & 1                                               \\
\frac{\alpha_1-\delta_1}{\alpha_1-\delta_2}   & \cdots        & \frac{\alpha_{k+2}-\delta_1}{\alpha_{k+2}-\delta_2}
\end{vmatrix}
\]
\[
=
\begin{vmatrix}
\alpha_1                                      & \cdots        & \alpha_{k+2}                              \\
\alpha_1^2                                    & \cdots        & \alpha_{k+2}^2                  \\
\vdots                                        & \ddots        & \vdots                                           \\
\alpha_1^k                             & \cdots        & \alpha_{k+2}^k                \\
1                                             & \cdots        & 1                                               \\
\frac{\alpha_1-\delta_1}{\alpha_1-\delta_2}   & \cdots        & \frac{\alpha_{k+2}-\delta_1}{\alpha_{k+2}-\delta_2}
\end{vmatrix}
\]
\[
\qquad \quad =
(-1)^k
\begin{vmatrix}
1                                             & \cdots        & 1                                               \\
\alpha_1                                      & \cdots        & \alpha_{k+2}                              \\
\alpha_1^2                                    & \cdots        & \alpha_{k+2}^2                  \\
\vdots                                        & \ddots        & \vdots                                           \\
\alpha_1^k                             & \cdots        & \alpha_{k+2}^k                \\
\frac{\alpha_1-\delta_1}{\alpha_1-\delta_2}   & \cdots        & \frac{\alpha_{k+2}-\delta_1}{\alpha_{k+2}-\delta_2}
\end{vmatrix}
\]
\[
\qquad \qquad \qquad  =
(-1)^k
\begin{vmatrix}
1                                             & \cdots        & 1                                               \\
\alpha_1                                      & \cdots        & \alpha_{k+2}                              \\
\alpha_1^2                                    & \cdots        & \alpha_{k+2}^2                  \\
\vdots                                        & \ddots        & \vdots                                           \\
\alpha_1^k                                    & \cdots        & \alpha_{k+2}^k                \\
1+\frac{\delta_2-\delta_1}{\alpha_1-\delta_2} & \cdots        & 1+\frac{\delta_{2}-\delta_1}{\alpha_{k+2}-\delta_2}
\end{vmatrix}
\]
\[
\qquad \qquad \qquad \qquad  =
(-1)^k(\delta_2-\delta_1)
\begin{vmatrix}
1                                             & \cdots        & 1                                               \\
\alpha_1                                      & \cdots        & \alpha_{k+2}                              \\
\alpha_1^2                                    & \cdots        & \alpha_{k+2}^2                  \\
\vdots                                        & \ddots        & \vdots                                           \\
\alpha_1^k                                    & \cdots        & \alpha_{k+2}^k                \\
\frac{1}{\alpha_1-\delta_2}                   & \cdots        & \frac{1}{\alpha_{k+2}-\delta_2}
\end{vmatrix}
\neq 0.
\]
The last step follows from the same argument as above. Hence we prove that $c_2$ are different for $f_1=\frac{1}{x-\delta_1}$ and $f_2=\frac{1}{x-\delta_2}$.
\fi

Next, we show that if $c_2\notin S$ then $f(x)=\prod_{i=1}^{k}(x-\alpha_i)+c_2\prod_{i=1}^{k+1}(x-\alpha_i)$ 
does not generate a deep hole. Consider the following matrix
$$
G=
\begin{bmatrix}
1                            & 1                 & \cdots                       & 1  \\
\alpha_1                     & \alpha_2          & \cdots                       & \alpha_{k+2}\\
\vdots                       & \vdots            & \ddots                       & \vdots   \\
\alpha_1^{k-1}               & \alpha_2^{k-1}    & \cdots                       & \alpha_{k+2}^{k-1} \\
f(\alpha_1)                  & f(\alpha_2)       & \cdots                       & f(\alpha_{k+2})
\end{bmatrix},
$$
where $f(i)=0,1\leqslant i\leqslant k, f(\alpha_{k+1})=\prod_{i=1}^{k}(\alpha_{k+1}-\alpha_i), f(\alpha_{k+2})=\prod_{i=1}^{k}(\alpha_{k+2}-\alpha_i)+c_{2}\prod_{i=1}^{k+1}(\alpha_{k+2}-\alpha_i) $.

\noindent
\textbf{Case 1.} If
\[
\begin{aligned}
f(\alpha_{k+2}) &= \prod_{i=1}^{k}(\alpha_{k+2}-\alpha_i)+c_2\prod_{i=1}^{k+1}(\alpha_{k+2}-\alpha_i) \\
                &= \prod_{i=1}^{k}(\alpha_{k+2}-\alpha_i)[1+c_2(\alpha_{k+2}-\alpha_{k+1})] \\
                &= 0,
\end{aligned}
\]
i.e., $c_2=\frac{1}{\alpha_{k+1}-\alpha_{k+2}}$, then there are $k+1$ columns of $G$, namely, the first
$k$ columns and the last column, which are linearly dependent.
Thus $f(x)$ does not generate a deep hole in this case.

\noindent
\textbf{Case 2.} Suppose $f(\alpha_{k+2})\neq 0$. For any $k-1$ elements $\{\beta_1,\ldots,\beta_{k-1}\}\subset \{\alpha_1,\ldots,\alpha_k\}$, consider the submatrix
$$
G'=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1                    & 1  \\
\beta_1                      & \cdots            & \beta_{k-1}                  & \alpha_{k+1}          & \alpha_{k+2}  \\
\vdots                       & \ddots            & \vdots                       & \vdots               & \vdots         \\
\beta_1^{k-1}                & \cdots            & \beta_{k-1}^{k-1}            & \alpha_{k+1}^{k-1}   & \alpha_{k+2}^{k-1} \\
0                            & \cdots            & 0                            & f(\alpha_{k+1})      & f(\alpha_{k+2})
\end{bmatrix}.
$$
Thus $\det(G')=0$ is equivalent to
\[
f(\alpha_{k+1})\prod_{i=1}^{k-1}(\alpha_{k+2}-\beta_i)=f(\alpha_{k+2})\prod_{i=1}^{k-1}(\alpha_{k+1}-\beta_i),
\]
that is,
\[
\begin{aligned}
\frac{f(\alpha_{k+2})}{f(\alpha_{k+1})} &= \prod_{i=1}^{k-1}\frac{\alpha_{k+2}-\beta_i}{\alpha_{k+1}-\beta_i} \\
&= \prod_{i=1}^{k-1}(1+\frac{\alpha_{k+2}-\alpha_{k+1}}{\alpha_{k+1}-\beta_i}).
\end{aligned}
\]
Hence for each subset $\{\beta_1,\ldots,\beta_{k-1}\}\subset \{\alpha_1,\ldots,\alpha_k\}$, there is a unique $c_2$ such that $\det(G')=0$.

In total, there are $k+1$ elements of candidate $c_2$ such that the corresponding $f(x)$ does not generate a deep hole. This implies that if $c_2\notin S$ then $f(x)$ does not generate a deep hole.

In conclusion, in depth $d=2$, the nodes in the full deep hole tree are exactly those in the expected deep hole tree.
\end{proof}



\begin{lemma} \label{case_1}
Let $p$ be an odd prime, $k\geqslant \frac{p-1}{2}, d\geqslant 2$ be a positive integer and $D_d=\{\alpha_1,\ldots,\alpha_{k+d}\}\subset\F_p, \delta \in \F_p\setminus D_d$.
For any $\gamma\in \F_p$, there exists a subset $\{\beta_1,\ldots,\beta_k\}\subset D_d$ such that the matrix
\[
A=
\begin{bmatrix}
1                           & \cdots            & 1                            & 1  \\
\beta_1                     & \cdots            & \beta_k                      & \delta\\
\vdots                      & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}               & \cdots            &  \beta_{k}^{k-1}             & \delta^{k-1} \\
\frac{1}{\beta_1-\delta}    & \cdots            & \frac{1}{\beta_k-\delta}     & \gamma
\end{bmatrix}
\]
is singular.
\end{lemma}
%The proof of Lemma \ref{case_1} is in Appendix D.
\begin{proof}
Note that $\det(A)=\det(A')+\det(A'')$, where
\[
A'=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\frac{1}{\beta_1-\delta}     & \cdots            & \frac{1}{\beta_k-\delta}     & 0
\end{bmatrix},
A''=
\begin{bmatrix}
1                            & \cdots            & 1                            & 0 \\
\beta_1                      & \cdots            & \beta_k                      & 0 \\
\vdots                       & \ddots            & \vdots                       & 0 \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & 0 \\
\frac{1}{\beta_1-\delta}     & \cdots            & \frac{1}{\beta_k-\delta}     & \gamma
\end{bmatrix}.
\]
Since
\[
\prod_{i=1}^k(\beta_i-\delta)\det(A') =
\begin{vmatrix}
\beta_1-\delta                                  & \cdots            & \beta_k-\delta                              & 1  \\
\beta_1(\beta_1-\delta)                         & \cdots            & \beta_k(\beta_k-\delta)                     & \delta\\
\vdots                                          & \ddots            & \vdots                                      & \vdots   \\
\beta_1^{k-1}(\beta_1-\delta)                   & \cdots            & \beta_{k}^{k-1}(\beta_k-\delta)             & \delta^{k-1} \\
1                                               & \cdots            & 1                                           & 0 \notag
\end{vmatrix}
\]
\[
=
\begin{vmatrix}
\beta_1                             & \cdots            & \beta_k                         & 1  \\
\beta_1^2                           & \cdots            & \beta_k^2                       & 2\delta \\
\vdots                              & \ddots            & \vdots                          & \vdots   \\
\beta_1^k                           & \cdots            & \beta_{k}^k                     & k\delta^{k-1} \\
1                                   & \cdots            & 1                               & 0 \notag
\end{vmatrix}
\]
\[
\qquad =(-1)^k
\begin{vmatrix}
1                                  & \cdots            & 1                               & 0 \\
\beta_1                            & \cdots            & \beta_k                         & 1  \\
\beta_1^2                          & \cdots            & \beta_k^2                       & 2\delta \\
\vdots                             & \ddots            & \vdots                          & \vdots   \\
\beta_1^k                          & \cdots            & \beta_{k}^k                     & k\delta^{k-1} \notag
\end{vmatrix}
\]
\[
\qquad\quad =(-1)^k
\begin{vmatrix}
1                                  & \cdots            & 1                               & \frac{d}{dx}1\bigg|_{x=\delta} \\
\beta_1                            & \cdots            & \beta_k                         & \frac{d}{dx}x\bigg|_{x=\delta}  \\
\beta_1^2                          & \cdots            & \beta_k^2                       & \frac{d}{dx}x^2\bigg|_{x=\delta} \\
\vdots                             & \ddots            & \vdots                          &  \vdots   \\
\beta_1^k                          & \cdots            & \beta_{k}^k                     & \frac{d}{dx}x^k\bigg|_{x=\delta} \notag
\end{vmatrix}
\]
\[
\qquad\qquad  =(-1)^k\frac{d}{dx}
\begin{vmatrix}
1                                 & \cdots            & 1                               & 1 \\
\beta_1                           & \cdots            & \beta_k                         & x  \\
\beta_1^2                         & \cdots            & \beta_k^2                       & x^2 \\
\vdots                            & \ddots            & \vdots                          & \vdots   \\
\beta_1^k                         & \cdots            & \beta_{k}^k                     & x^k \notag
\end{vmatrix}
\bigg|_{x=\delta}
\]
\[
\qquad \qquad \qquad \qquad\qquad  = (-1)^k\frac{d}{dx}\left[\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i)\prod_{i=1}^k(x-\beta_i)\right]\bigg|_{x=\delta},
\]
thus
\[
\begin{aligned}
\det(A') &= \frac{(-1)^k}{\prod_{i=1}^k(\beta_i-\delta)}\prod_{1\leqslant i<j\leqslant k}(\beta_j-\beta_i)\frac{d}{dx}\left[\prod_{i=1}^k(x-\beta_i)\right]\bigg|_{x=\delta}\\
         &= \frac{(-1)^k}{\prod_{i=1}^k(\beta_i-\delta)}\prod_{1\leqslant i<j\leqslant k}(\beta_j-\beta_i)\prod_{i=1}^k(\delta-\beta_i)\sum_{i=1}^k\frac{1}{\delta-\beta_i}\\
         &= \prod_{1\leqslant i<j\leqslant k}(\beta_j-\beta_i)\sum_{i=1}^k\frac{1}{\delta-\beta_i}.
\end{aligned}
\]
It follows that
\[
\begin{aligned}
\det(A) & = \det(A') + \det(A'') \\
        & = \prod_{1\leqslant i<j\leqslant k}(\beta_j-\beta_i)\sum_{i=1}^k\frac{1}{\delta-\beta_i}+\gamma\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i).
\end{aligned}
\]
Hence $\det(A)=0$ is equivalent to
\[
\sum_{i=1}^k\frac{1}{\delta-\beta_i}+\gamma=0.
\]


Designate the set $\{\frac{1}{\delta-\beta_i} \mid i\in D_{d}\}$ as $S_1$ with cardinality $k+d$. Since $\frac{p-1}{2}\leqslant k,2\leqslant d,$ from Theorem \ref{SH}, we conclude that
\[
\begin{aligned}
|k ^\wedge S_1| &\geqslant \min\{p,k|S_1|-k^2+1\} \\
                &=p,
\end{aligned}
\]
which implies that for each $\gamma \in \F_p$, there exists a subset $\{\beta_1,\ldots,\beta_k\}\subset D_{k}$ such that $\sum_{i=1}^k\frac{1}{\delta-\beta_i}+\gamma=0.$
\end{proof}




\begin{lemma} \label{case_2}
Let $p$ be an odd prime, $k\geqslant \frac{p-1}{2}, d\geqslant 2$ be a positive integer and $D_{d+1}=\{\alpha_1,\ldots,\alpha_{k+d+1}=\delta\}\subset\F_p$.
For any $\delta'\in\F_p,\delta'\notin D_{d+1},\gamma\in\F_p,\gamma\neq \frac{1}{\delta-\delta'}$, there exists a subset $\{\beta_1,\ldots,\beta_k\}\subset D_{d+1}\setminus\{\delta\}$ such that the matrix
\[
B=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\frac{1}{\beta_1-\delta'}    & \cdots            & \frac{1}{\beta_k-\delta'}    & \gamma
\end{bmatrix}
\]
is singular.
\end{lemma}
%The proof of Lemma \ref{case_2} is in Appendix E.
\begin{proof}
Note that $\det(B)=\det(B')+\det(B'')$, where
\[
B'=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\frac{1}{\beta_1-\delta'}    & \cdots            & \frac{1}{\beta_k-\delta'}    & \frac{1}{\delta-\delta'}
\end{bmatrix},
B''=
\begin{bmatrix}
1                            & \cdots            & 1                            & 0 \\
\beta_1                      & \cdots            & \beta_k                      & 0 \\
\vdots                       & \ddots            & \vdots                       & 0 \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & 0 \\
\frac{1}{\beta_1-\delta'}    & \cdots            & \frac{1}{\beta_k-\delta'}    & \gamma-\frac{1}{\delta-\delta'}
\end{bmatrix}.
\]
Since
\[
\qquad \qquad \quad (\delta-\delta')\prod_{i=1}^k(\beta_i-\delta')\det(B') =
\begin{vmatrix}
\beta_1-\delta'                                  & \cdots            & \beta_k-\delta'                                  & \delta-\delta'  \\
\beta_1(\beta_1-\delta')                         & \cdots            & \beta_k(\beta_k-\delta')                         & \delta(\delta-\delta')\\
\vdots                                           & \ddots            & \vdots                                           & \vdots   \\
\beta_1^{k-1}(\beta_1-\delta')                   & \cdots            & \beta_{k}^{k-1}(\beta_k-\delta')                 & \delta^{k-1}(\delta-\delta') \\
1                                                & \cdots            & 1                                                & 1 \notag
\end{vmatrix}
\]
\[
=
\begin{vmatrix}
\beta_1                             & \cdots            & \beta_k                         & \delta   \\
\beta_1^2                           & \cdots            & \beta_k^2                       & \delta^2 \\
\vdots                              & \ddots            & \vdots                          & \vdots   \\
\beta_1^k                           & \cdots            & \beta_{k}^k                     & \delta^{k} \\
1                                   & \cdots            & 1                               & 1 \notag
\end{vmatrix}
\]
\[
\qquad =(-1)^k
\begin{vmatrix}
1                               & \cdots                & 1                         & 1       \\
\beta_1                         & \cdots                & \beta_k                   & \delta  \\
\beta_1^2                       & \cdots                & \beta_k^2                 & \delta^2 \\
\vdots                          & \ddots                & \vdots                    & \vdots   \\
\beta_1^k                       & \cdots                & \beta_{k}^k               & \delta^{k} \notag
\end{vmatrix}
\]
\[
\qquad \qquad \qquad \qquad =(-1)^k\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i)\prod_{i=1}^k(\delta-\beta_i),
\]
we have
\[
\begin{aligned}
\det(B') &= \frac{(-1)^k}{(\delta-\delta')\prod_{i=1}^{k}(\beta_i-\delta')}\prod_{1\leqslant i < j \leqslant j}(\beta_j-\beta_i)\prod_{i=1}^{k}(\delta-\beta_i) \\
         &= \frac{1}{\delta-\delta'}\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i)\prod_{i=1}^{k}\frac{\beta_i-\delta}{\beta_i-\delta'},
\end{aligned}
\]
and
\[
\det(B'')=(\gamma-\frac{1}{\delta-\delta'})\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i).
\]
Hence
\[
\begin{aligned}
\det(B)  &= \frac{1}{\delta-\delta'}\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i)\prod_{i=1}^{k}\frac{\beta_i-\delta}{\beta_i-\delta'}+(\gamma-\frac{1}{\delta-\delta'})\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i) \\
         &= \prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i)\left[\frac{1}{\delta-\delta'}\prod_{i=1}^{k}\frac{\beta_i-\delta}{\beta_i-\delta'}+\frac{\gamma(\delta-\delta')-1}{\delta-\delta'}\right] \\
         &= \frac{\prod_{1\leqslant i<j \leqslant k}(\beta_j-\beta_i)}{\delta-\delta'}\left[\prod_{i=1}^{k}\frac{\beta_i-\delta}{\beta_i-\delta'}+\gamma(\delta-\delta')-1\right].
\end{aligned}
\]


It follows that $\det(B)=0$ is equivalent to
\[
\prod_{i=1}^{k}(1+\frac{\delta'-\delta}{\beta_i-\delta'})=1-\gamma(\delta-\delta').
\]

If $|D_d|=k+2$, we consider the dual version of the equality.
From Corollary \ref{2product}, there exist two distinct elements $x,y\in D_{d}$ such that $(1+\frac{\delta'-\delta}{x-\delta'})(1+\frac{\delta'-\delta}{y-\delta'})=\theta$
for any $\theta\in \F_p^*$, hence there exist $k$ distinct elements in $D_{d}$ such that
\[
\prod_{i=1}^{k}(1+\frac{\delta'-\delta}{\alpha_i-\delta'})=1-\gamma(\delta-\delta'),
\]
for any $\gamma\neq \frac{1}{\delta-\delta'}$.

If $|D_{d}|>k+2$, we select a subset $D'\subset D_{d}$ such that $|D'|=k+2$, then apply the same argument as above.
\end{proof}

\begin{lemma} \label{case_3}
Let $p$ be an odd prime, $k\geqslant \frac{p-1}{2}, d\geqslant 2$ be a positive integer and $D_{d+1}=\{\alpha_1,\ldots,\alpha_{k+d+1}=\delta\}\subset\F_p$.
For any $\gamma\in\F_p,\gamma\neq \delta^k$, there exists a subset $\{\beta_1,\ldots,\beta_k\}\subset D_{d+1}\setminus\{\delta\}$ such that the matrix
\[
C=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\beta_1^k				     & \cdots            & \beta_k^k    & \gamma
\end{bmatrix}
\]
is singular.
\end{lemma}
\begin{proof}
Note that $\det(C)=\det(C')+\det(C'')$, where
\[
C'=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\beta_1^k				     & \cdots            & \beta_k^k				    & \delta^k
\end{bmatrix},
C''=
\begin{bmatrix}
1                            & \cdots            & 1                            & 0 \\
\beta_1                      & \cdots            & \beta_k                      & 0 \\
\vdots                       & \ddots            & \vdots                       & 0 \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & 0 \\
\beta_1^k				     & \cdots            & \beta_k^k				    & \gamma-\delta^k
\end{bmatrix}.
\]
Since
\[
\det(C') = \prod_{1\leqslant i < j \leqslant k}(\beta_j-\beta_i)\prod_{i=1}^{k}(\delta-\beta_i),
\]
\[
\det(C'')= \prod_{1\leqslant i < j \leqslant k}(\beta_j-\beta_i)(\gamma-\delta^k),
\]
we have
\[
\frac{1}{\prod_{1\leqslant i < j \leqslant k}(\beta_j-\beta_i)}\det(C) =  \prod_{i=1}^{k}(\delta-\beta_i) + \gamma-\delta^k.
\]
Thus $\det(C)=0$ is equivalent to
\[
\prod_{i=1}^{k}(\delta-\beta_i) = \delta^k - \gamma.
\]
Denote $S=\{\delta-\alpha \mid \alpha\in D\}$. If $|D_d|=k+2$, we consider the dual version of the equality.
From Corollary \ref{2product}, there exist two distinct elements $x,y\in S$ such that $xy=\theta$
for any $\theta\in \F_p^*$, hence there exist $k$ distinct elements in $S$ such that
\[
\prod_{i=1}^{k}(\delta-\beta_i) = \delta^k - \gamma,
\]
for any $\gamma\neq \delta^k$.

If $|D_{d}|>k+2$, we select a subset $S'\subset S$ such that $S=k+2$, then apply the same argument as above. 
\end{proof}

\subsection{The main theorem and the proof}
In this section, we establish the following theorem:
\begin{theorem}\label{mainthm}
Let $p>2$ be a prime number, $k\geqslant\frac{p-1}{2}, D=\{\alpha_1,\alpha_2,\ldots,\alpha_n\}$ with $k < n\leqslant p$.
The only deep holes of $RS_p(D,k)$ are generated by functions which are equivalent to the following:
\[
f(x)=x^k,\quad f_{\delta}(x)=\frac{1}{x-\delta},
\]
where $\delta\in \F_p\setminus D$. Here two  functions $f(x)$ and
$g(x)$ are equivalent if and only if there exists $a\in \F_p^*$ and
$h(x)\in \F_p[x]$ with degree less than $k$ such that
\[
g(x)=af(x)+h(x).
\]
\end{theorem}

The basic idea of the proof of Theorem \ref{mainthm} is reducing the problem to some additive number theory problems. 

\begin{proof} Proceed by induction on the depth of the full deep hole tree.

\noindent
\textbf{Basis case.} This follows from Lemma \ref{basis}.

\noindent
\textbf{Inductive step.}
We show that if the set of nodes of the full deep hole tree coincide with the nodes of the expected deep hole tree in the same depth $d \geqslant 2$, then there are no additional nodes in depth $d+1$ except the expected ones. Denote the corresponding evaluation set by $D_{d}=\{\alpha_1,\ldots,\alpha_{k+d}\}$ in depth $d$ and $D_{d+1}=\{\alpha_1,\ldots,\alpha_{k+d},\alpha_{k+d+1}=\delta \}$ in depth $d+1$. In order to show there are no new nodes in depth $d+1$, there are three cases to consider.

\noindent
\textbf{Case 1:} We show the branch, which corresponds to the function $f=\frac{1}{x-\delta}$, will not grow in depth $d+1$.
It suffices to show that there exists $\{\beta_1,\ldots,\beta_k\}\subset \{\alpha_1,\ldots,\alpha_{k+d}\}$ such that for any $\gamma\in \F_p$ and matrix
\[
A=
\begin{bmatrix}
1                           & \cdots            & 1                            & 1  \\
\beta_1                     & \cdots            & \beta_k                      & \delta\\
\vdots                      & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}               & \cdots            &  \beta_{k}^{k-1}             & \delta^{k-1} \\
\frac{1}{\beta_1-\delta}    & \cdots            & \frac{1}{\beta_k-\delta}     & \gamma
\end{bmatrix},
\]
we have $\det(A)=0$. This follows from Lemma \ref{case_1}.

\noindent
\textbf{Case 2:} We show that the branch, which corresponds to the function $f=\frac{1}{x-\delta'}$, where $\delta' \notin D_{k+1}$, has only one child in depth $d+1$.
It suffices to show that there exists $\{\beta_1,\ldots,\beta_k\}\subset D_{d}$ such that for any $\delta'\notin D_{d+1},\gamma\in\F_p,\gamma\neq \frac{1}{\delta-\delta'}$ and matrix
\[
B=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\frac{1}{\beta_1-\delta'}    & \cdots            & \frac{1}{\beta_k-\delta'}    & \gamma
\end{bmatrix},
\]
we have $\det(B)=0$. This follows from Lemma \ref{case_2}.

\noindent
\textbf{Case 3:} We show that the branch, which corresponds to the function $f=x^k$ has only one child in depth $d+1$.
It suffices to show that there exists $\{\beta_1,\ldots,\beta_k\}\subset D_{d}$ such that for any $\gamma\neq \delta^k$ and matrix
\[
C=
\begin{bmatrix}
1                            & \cdots            & 1                            & 1  \\
\beta_1                      & \cdots            & \beta_k                      & \delta\\
\vdots                       & \ddots            & \vdots                       & \vdots   \\
\beta_1^{k-1}                & \cdots            & \beta_{k}^{k-1}              & \delta^{k-1} \\
\beta_1^k			         & \cdots            & \beta_k^k				    & \gamma
\end{bmatrix}
\]
we have $\det(C)=0$. This follows from Lemma \ref{case_3}.

From the principle of induction, the theorem is proved.
\end{proof}

\iffalse
\section{Determining deep holes using finite geometry results}
In this section, we show the following theorem:
\begin{theorem}\label{geometrythm}
Given a finite filed $\F_q$ with characteristic $p>2$, we have
\begin{enumerate}
\item If $k+1\leqslant p$ or $3\leqslant q-p+1\leqslant k+1\leqslant q-2$, then Conjecture \ref{conj1} is true.
\item If $3\leqslant k < \dfrac{\sqrt{q}+1}{4}$, then Conjecture \ref{conj2} is true.
\item If $3\leqslant k < \dfrac{p}{45}$, where $q=p$ is prime, then Conjecture \ref{conj2} is true.
\end{enumerate}
\end{theorem}

\begin{proof} There are 3 cases to prove.

\noindent
\textbf{Case 1.} Let $RS_q(\F_q, k)$ be an extended GRS code over the finite
field $\F_q$ whose characteristic $p$ is odd. Let one of its generator matrix be
$$
G=
\begin{bmatrix}
1           & 1          & \cdots & 1 \\
\alpha_1    & \alpha_2   & \cdots & \alpha_q\\
\alpha_1^2  & \alpha_2^2 & \cdots & \alpha_q^2\\
\vdots      & \vdots     & \ddots & \vdots \\
\alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_q^{k-1}
\end{bmatrix},
$$
where $\alpha_1,\ldots,\alpha_q$ are distinct element of  $\F_q$.

Suppose a word $\u\in \F_q^q$ is a deep hole of $RS_q(F_q, k)$. From proposition \ref{prop}, this is equivalent to the fact that
$$
G'=\left[
\begin{array}{c}
 G\\ \hline
 \u
\end{array}\right]
$$
generates another linear MDS code, where 
\[
\u=(u_1,u_2,\ldots,u_q).
\]
Thus the set
\[
S=\{\mathbf{c}_1,\ldots,\mathbf{c}_q\}\cup\{(0,\ldots,0,1)\},
\]
where $\mathbf{c}_i$ is the $i$-th column of $G'$ for $1\leqslant i \leqslant q$, has size $q+1$ and has the property that every subset of $S$ of size $k+1$ is a basis.

Since $k+1\leqslant p$ or $3\leqslant q-p+1\leqslant k+1\leqslant q-2$, by Theorem \ref{Simeon}, we deduce that $S$ is equivalent to the set
$$\{(1,\alpha,\alpha^2,\ldots,\alpha^k)\mid \alpha\in \F_q\}\cup\{(0,\ldots,0,1)\}.$$

Thus we conclude that
$$u(x)=ax^k+f_{\leqslant k-1}(x), a\neq 0;$$
where $f_{\leqslant k-1}(x)$ denotes a polynomial with degree not larger
than $k-1$.

\noindent
\textbf{Case 2.} Firstly, we get an estimation of $N_{min}(k,q)$. Combining Theorem \ref{B.Segre} and Lemma \ref{RL}, we conclude that
$$
\begin{aligned}
N_{min}(k,q) &\leqslant N_{min}(3,q)+k-3\\
             &\leqslant \lceil{q-\dfrac{\sqrt{q}-7}{4}}\rceil +k-3 \\
             &\leqslant q-1.
\end{aligned}
$$

Now let $G$ be a generator matrix of $RS_q(\F_q^*,k)$ of the following form
$$
G=
\begin{bmatrix}
1           & 1          & \cdots & 1 \\
\alpha_1    & \alpha_2   & \cdots & \alpha_{q-1}\\
\alpha_1^2  & \alpha_2^2 & \cdots & \alpha_{q-1}^2\\
\vdots      & \vdots     & \ddots & \vdots \\
\alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_{q-1}^{k-1}
\end{bmatrix},
$$
where $\alpha_1,\ldots,\alpha_{q-1}$ are distinct element of  $\F_q^*$.
From proposition \ref{prop}, a word $\u\in \F_q^{q-1}$ is a deep hole of $RS_q(\F_q^*, k)$ if and only if
$$
G'=\left[
\begin{array}{c}
 G\\ \hline
 \u
\end{array}\right]
$$
generates another linear MDS code $C_2$, where
\[
\u=(u_1,u_2,\ldots,u_{q-1}).
\]
Since $C_2$ is of length $q-1$, thus the matrix $G'$ is equivalent to a Vandermonde matrix of rank $k$.
Notice that $G$ is the given Vandermonde matrix of rank $k-1$. Thus there are two possibilities of $\u$, i.e., its Lagrange interpolation
polynomial satisfies the following conditions:
$$u(x)=ax^k+f_{\leqslant k-1}(x), a\neq 0;$$
or
$$u(x)=bx^{q-2}+f_{\leqslant k-1}(x), b\neq 0;$$
where $f_{\leqslant k-1}(x)$ denotes a polynomial with degree not larger
than $k-1$.

\noindent
\textbf{Case 3.} This is similar with the proof of case 2 and we will make use of Theorem \ref{Voloch}.
\end{proof}
\fi
%\section{Generalization to $\F_q$}


%\section{Application to the subset sum problem}

