# Every Function in a Finite Field is a Polynomial Function

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$?

-
There are many possible approaches. But note that a finite field need not have $p$ elements, where $p$ is prime. There is in fact a finite field with $p^n$ elements, for any prime $p$, and any positive integer $n$. –  André Nicolas Apr 8 '11 at 6:38
@user6312 - oops, I did not know that. Now I am a bit wiser. –  Michael Chen Apr 10 '11 at 20:47
This was actually a near duplicate of math.stackexchange.com/questions/25309/…. –  joriki Jul 16 '11 at 7:22
@joriki: Oh, whoops. –  Michael Chen Jul 17 '11 at 15:47

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.

-
First, this is true for $m>0$ only. (I edited your answer) Second, if $m=1$, the finite field with $p$ elements is "unique" indeed, meaning by that it represents a functor, namely, it is the initial object of the category of rings of characteristic $p$. Finally, if $m>1$, there is no "unique" finite field with $p^n$ elements. It is nevertheless unique in an algebraic closure of $\mathbf{F}_p$, but this algebraic closure is also not "unique". –  user10000100_u Jan 24 at 18:23
Unique up to isomorphism. It is very common to speak of the existence and uniqueness of finite fields of order $p^m$ in this sense. –  Alon Amit Jan 26 at 1:42
But usually when it is the case, some ambient alg closure of the finite field with p elements has been fixed before etc. Anyway... –  user10000100_u Jan 26 at 1:46

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$.

-
Interesting! This is useful, and quick - it turns out that a friend in my study group came up with this when we met. –  Michael Chen Apr 10 '11 at 20:48

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.

-

Hint: Vandermonde matrix.

-
Wow. I don't think I could come up with that on an exam, but the proof of the determinant formula linked by Wikipedia here is quite beautiful. –  Michael Chen Apr 8 '11 at 6:33

There is a very simple argument based only on dimension and root counting. You want to show that the map$~g$ from the polynomials in $\def\Fq{{\Bbb F_q}}\Fq[X]$ to their polynomial functions in $\Fq^\Fq=\{\,f:\Fq\to\Fq\mid\,\}$ is surjective. It is easy to see the map is $\Fq$-linear and that $\dim(\Fq^\Fq)=q$. It is actually easier to show the stronger statement that the restriction$~\tilde g$ of$~g$ to the subspace $V=\{\,P\in\Fq[X]\mid\deg(P)<q\,\}$ is bijective (so in particular$~\tilde g$ is surjective, and a fortiori so is $g$).

Now $\dim(V)=q$ so$~\tilde g$ is a linear map between two vector spaces of the same dimension; such maps are bijective if and only if they are injective, i.e., have $\{0\}$ as kernel. Now $\ker(\tilde g)$ consists of those $P\in V$ whose polynomial function is the zero function. The part $P\in V$ means that $\deg(P)<q$, and the polynomial function being zero means that all $q$ elements of$~\Fq$ are roots of$~P$. It is well known that a nonzero polynomial over a field cannot have more roots than its degree. This shows that $\ker(\tilde g)=\{0\}$, so $\tilde g$ is bijective, as desired.

-