Polynomial interpolation over Finite Field

Question

Let $\mathbb{F}_p$ be a finite field (p is prime), and consider $V = \mathrm{Span}(\{1, x^2, x^3, x^5, x^6\}) \subset \mathbb{F}_p[x]$. What is the bound on $p$, such that there exists an interpolation set of size $5$ for $V$ in $\mathbb{F}_p$?

[Edit] An interpolation set is defined as a set of points in $\mathbb{F}_p$ so that any value of a poly in $V$ can be interpolated using its evaluations on those points. [/Edit]

My intuition is failing me on this one. say $p = 5$ then $x^6 = x$ so it means I can't interpolate the coefficient of $x^6$?

Answer 1

My understanding of the question is that it asks for a collection of five distinct elements $x_1,x_2,x_3,x_4,x_5\in\Bbb{F}_p$ such that for all $5$-tuples $(y_1,y_2,y_3,y_4,y_5)\in\Bbb{F}_p^5$ the system of equations $f(x_i)=y_i, i=1,2,3,4,5$, is satisfied by a unique polynomial $f(x)\in V$.

My understanding may be wrong for that variant turned out being a bit duller than I initially anticipated. Here comes anyway.

This is possible if and only if $p>5$.

The problem is equivalent to our ability to uniquely solve the coefficients $a_i\in\Bbb{F}_p, i=0,2,3,5,6,$ of the polynomial $$ f(x)=a_0+a_2x^2+a_3x^3+a_5x^5+a_6x^6 $$ subject to the linear system of five equations $$ f(x_i)=y_i, i=1,2,3,4,5. $$ The matrix of that system of equations is $$ M=\left(\begin{array}{ccccc} 1&x_1^2&x_1^3&x_1^5&x_1^6\\ 1&x_2^2&x_2^3&x_2^5&x_2^6\\ 1&x_3^2&x_3^3&x_3^5&x_3^6\\ 1&x_4^2&x_4^3&x_4^5&x_4^6\\ 1&x_5^2&x_5^3&x_5^5&x_5^6 \end{array}\right). $$ If we used terms of degrees $0,1,2,3,4$ instead of $0,2,3,5,6$, then

1. the answer would be given by the Lagrange interpolation formula,
2. the matrix of the system would be the familiar Vandermonde matrix with the well known determinant $$ \Delta=\left\vert\begin{array}{ccccc} 1&x_1&x_1^2&x_1^3&x_1^4\\ 1&x_2&x_2^2&x_2^3&x_2^4\\ 1&x_3&x_3^2&x_3^3&x_3^4\\ 1&x_4&x_4^2&x_4^3&x_4^4\\ 1&x_5&x_5^2&x_5^3&x_5^4 \end{array}\right\vert=\prod_{1\le i<j\le5}(x_i-x_j), $$
3. implying that any collection of five distinct elements $x_i, i=1,2,3,4,5$ will do.

The variant limiting the range of degrees of terms to a sequence other $0,1,2,3,4$ actually does not change the conclusion very much.

• The cases $p=2,3$ are obviously out for we don't have enough elbow room to pick five distinct elements $x_i$.
• The case $p=5$ fails for a slightly more interesting reason. By Little Fermat $x^6=x^2$ for every element $x\in\Bbb{F}_5$. Therefore the second and the last columns of $M$ coincide, implying that $\det M=0$. Less interestingly, the essentially only possibility $x_i=i-1,i=1,2,3,4,5,$ doesn't work.
• However, plugging in $x_1=0,x_2=1,x_3=2,x_4=3,x_5=4$ gives $$\det M=2^8\cdot 3^3\cdot5\cdot7,$$ implying that this choice works for every $p>7$.
• Instead, plugging in $x_1=0,x_2=1,x_3=2,x_4=3,x_5=5$ gives $$\det M=2^6\cdot3^3\cdot5^2\cdot41,$$ implying that this choice works for every $p>5$ other than $p=41$.

Together the last two bullets give the claim: one of them works for every prime $p>5$.

---

More interesting/general variants can possibly be handled by studying suitable Schur polynomials. We easily see that the Vandermonde determinant $\Delta$ is always a factor of $\det M$, no matter the choice of sequence of exponents. The Schur polynomials are exactly the quotients $\det M/\Delta$. The non-vanishing of the Schur polynomial tells us whether a given choice of $x_i$s works (in a more general version we may have more terms).