Every Function in a Finite Field is a Polynomial Function

Question

From a bank of past master's exams I am going through:

Let $F$ be a finite field. Show that any function from $F$ to $F$ is a polynomial function.

I know that finite fields are fields of $p$ elements for $p$ prime [EDIT: It's actually $p^n$ for $p$ prime; see comment below]. Since I have $p$ choices for the $p$ elements to map to, then I have $p^p$ distinct functions. I think every function can be written in the form $f(x) = a_{p-1}x^{p-1} + \dots + a_0x^0$. For then given the values $f(0), f(1), \ldots f(p-1)$, I can solve for the coefficents by the linear system of equations

$$ a_0 + \sum_{i=1}^{p-1} n^i a_i = f(n).$$

This then gives me a $p-1 \times p-1$ square matrix over the field $\mathbb{F}_p$:

$$\left( \begin{array}{ccccc} 1& 0 & 0 & \ldots & 0 \\ 1& 1 & 1 & \dots & 1 \\ 1& 2 & 4 & \dots & 2^{p-1} \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & p-1 & (p-1)^2 & \dots & (p-1)^{p-1} \end{array} \right) \left( \begin{array}{c} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{p-1} \end{array}\right) = \left( \begin{array}{c} f(0) \\ f(1) \\ f(2) \\ \vdots \\ f(p-1) \end{array} \right)$$

If I can show this matrix is invertible, then I can always find the $a_i$. But I am a bit stumped on how to show this (partially because I don't think I've ever done linear algebra in a vector space over a finite field). It does not seem easy to show linear independence, or nonzero determinant, or full row rank.

---

Alternatively (I just thought of this), can I show this is true by arguing that the map between the two sets (the set of polynomials of degree $p-1$; and the set of functions $F \to F$) is injective, and that it must be a bijection because the sets have the same cardinality $p^p$?

Answer 1

First off, a finite field doesn't necessarily have $p$ elements for $p$ prime. For every prime $p$ and natural number $m>0$ there is a finite field with $p^m$ elements.

Second, your approach is sound - the only piece you're missing is that your matrix is a Vandermonde matrix which, over any field, has a simple expression for its determinant.

Answer 2

Hint: Vandermonde matrix.

Answer 3

Yes, your second method works and indeed generalizes nicely to functions in $n$ variables.

A similar method to show that every function $f: \mathbb{F}_q^n \rightarrow \mathbb{F}_q$ is given by a polynomial in which the degree in each variable is at most $q-1$ is to give an explicit polynomial formula for the "Dirac delta function" $\mathbb{1}_0(x)$ which is equal to $1$ if $x = (0,\ldots,0)$ and $0$ otherwise. Indeed, we have

$\mathbb{1}_0(x_1,\ldots,x_n) = \prod_{i=1}^n (1-x_i^{q-1})$

as it is a pleasant and easy exercise to check.

Again a cardinality argument shows that any such function $f$ has a unique representation by a reduced polynomial, i.e., by a polynomial whose degree in each variable is at most $q-1$. These observations lead quickly to a proof of the celebrated Chevalley-Warning Theorem: see these notes for a treatment of all these topics.

Answer 4

It might be interesting to you to look up the Lagrange Interpolation Formula. Given a function $f$ from the finite field to itself, it will give you an explicit polynomial $P$ such that the associated polynomial function is equal to $f$.