I understand that part of this question has been addressed before (here), but I am confused about the uniqueness of a Lagrange interpolant.
Given any field $F$, I am trying to prove the existence and uniqueness of a Lagrange interpolant in $F[x]$ for any function $f$ from $F$ to itself over a set of distinct $n$ points :$(x_1,f(x_1)) \dots (x_n,f(x_n))$, where each $x_1 \dots x_n$ is unique. Following the proof outlined here, I see that it says the proof for both the existence and uniqueness of a Lagrange interpolant is satisfied for any given field, which implies that it also satisfied for finite fields. However, there are finitely many functions from $F$ to itself and there are infinitely many polynomials in $F[x]$. I also see that from this post, a polynomial function in a finite field can be given by multiple polynomials. Would this not imply that the uniqueness of a Lagrange interpolant need not hold over a finite field?
Any clarification about how the proof of uniqueness for a Lagrange interpolant over a finite field would be much appreciated!
Best Answer
You are missing the issue that the interpolation polynomial for $n$ points has degree less than $n$ (or is the zero polynomial, but I won't keep repeating this). That makes the polynomial unique even if the field $F$ is finite. What keeps things unique given the restriction on the degree being less than $n$ is that polynomials of the form $c_0 + c_1x + \cdots + c_{n-1}x^{n-1}$ and $c_0' + c_1'x + \cdots + c_{n-1}'x^{n-1}$ in $F[x]$ that are equal at $n$ different numbers in $F$ must have $c_i = c_i'$ for all $i$. This is true for all fields, and notice that when $F$ is finite such a result only makes sense when $n \leq |F|$ since $F$ has at most $|F|$ distinct elements. For instance, you can't find a polynomial in $\mathbf F_3[x]$ taking specified values at $5$ different elements of $\mathbf F_3$ since there aren't $5$ different elements of $\mathbf F_3$. (You could look for a polynomial in $\mathbf F_9[x]$ taking specified values at 5 different elements of $\mathbf F_9$, but not at 14 different elements of $\mathbf F_9$, and so on.)
You have concern about losing uniqueness over a finite field, but even over an infinite field you would lose uniqueness without restricting the degree of the interpolation polynomial to have degree less than $n$: if the distinct points in $F$ are $a_1, \ldots, a_n$ then you can add to an interpolating polynomial an arbitrary polynomial multiple of $(x-a_1)\cdots(x-a_n)$ without changing the values of the polynomial at $a_1,\ldots,a_n$. You don't lose uniqueness as long as you require the interpolation polynomial at $n$ different numbers in $F$ to have degree less than $n$.
Here is a correct theorem: for a field $F$, distinct $a_1, \ldots, a_n$ in $F$, and arbitrary $b_1, \ldots, b_n$ in $F$, there is a unique polynomial $f(x) \in F[x]$ of degree less than $n$ such that $f(a_i) = b_i$ for $i = 1, \ldots, n$.