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

  • 3
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Apr 8 '11 at 6:38
  • $\begingroup$ @user6312 - oops, I did not know that. Now I am a bit wiser. $\endgroup$ – Michael Chen Apr 10 '11 at 20:47
  • $\begingroup$ This was actually a near duplicate of math.stackexchange.com/questions/25309/…. $\endgroup$ – joriki Jul 16 '11 at 7:22
  • $\begingroup$ @joriki: Oh, whoops. $\endgroup$ – 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.

  • $\begingroup$ 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". $\endgroup$ – Olórin Jan 24 '15 at 18:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Alon Amit Jan 26 '15 at 1:42
  • $\begingroup$ But usually when it is the case, some ambient alg closure of the finite field with p elements has been fixed before etc. Anyway... $\endgroup$ – Olórin Jan 26 '15 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$.

  • $\begingroup$ Interesting! This is useful, and quick - it turns out that a friend in my study group came up with this when we met. $\endgroup$ – 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.

  • 2
    $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.