27
$\begingroup$

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

  • 0
    @joriki: Oh, whoops.2011-07-17

5 Answers 5

7

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.

  • 0
    But usually when it is the case, some ambient alg closure of the finite field with$p$elements has been fixed before etc. Anyway...2015-01-26
14

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

  • 0
    Interesting! This is useful, and quick - it turns out that a friend in my study group came up with this when we met.2011-04-10
11

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.

8

Hint: Vandermonde matrix.

  • 2
    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](http://www.proofwiki.org/wiki/Vandermonde_Determinant) is quite beautiful.2011-04-08
8

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) 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), 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.