TAOCP 4.6.4 Exercise 54
Theorem W in Section 4.
Section 4.6.4: Evaluation of Polynomials
Exercise 54. [M23] Theorem W refers to an infinite field. How many elements must a finite field have in order for the proof of Theorem W to be valid?
Verified: yes
Solve time: 1m40s
Solution
Theorem W in Section 4.6.4 asserts that a polynomial $u(x)$ of degree at most $n$ over a field $F$ is uniquely determined by its values at $n+1$ distinct points in $F$. The proof relies on the property that a nonzero polynomial of degree at most $n$ has at most $n$ roots in the field. In particular, the argument requires selecting $n+1$ distinct points $x_0, x_1, \ldots, x_n$ in $F$ such that $u(x_i) = 0$ for each $i$ implies $u(x) \equiv 0$.
If $F$ is finite, say with $q$ elements, then the set of distinct evaluation points cannot exceed $q$. Therefore, to guarantee the validity of the proof, we must have
$$ q \ge n + 1. $$
Otherwise, it would be impossible to choose $n+1$ distinct points in $F$, and the step of the proof asserting that a nonzero polynomial of degree at most $n$ cannot vanish at more than $n$ points would fail.
Hence, a finite field must have at least $n+1$ elements for Theorem W to hold. This completes the proof.
∎
$$ \boxed{q \ge n+1} $$