Should all polynomial functions from F to F (F is a field) have coefficients in F?

Solution 1:

The main difference between polynomial and polynomial functions is that a polynomial is an algebraic expression, while a polynomial function is the function.

Over infinite fields, the polynomial function uniquely identifies the polynomial. But in finite fields (and this is exactly what the problem expects you to identify), you could find different polynomials with exactly the same function.

For example, in $\mathbb Z/2 \mathbb Z$ the polynomial function corresponding to $P(X)=X^2-X$ is $P(0)=0$ and $P(1)=0$...But this is also the function corresponding to many other polynomials.

Note also that over a finite field, there are only finitely many functions, but infinitely many polynomials....

Solution 2:

The example $ax^2-ax$ that you give, considered as a function from the $2$-element field to itself, is the same function as $x^2-x$, or indeed, as you point out, it is the same as the identically $0$ function.

In general, for any function $g$ from the finite field $F$ to itself, we can produce a polynomial $P_g$, with coefficients in $F$, such that $g(x)=P_g(x)$ for all $x$ in $F$. This can be done explicitly by using essentially the Lagrange interpolation process. Thus allowing coefficients to range over some proper extension field $K$ of $F$ cannot increase the number of polynomial functions from $F$ to $F$.

A stronger result holds for infinite fields. Let $F$ be an infinite subfield of $K$, and let $P$ be a polynomial with coefficients in $K$. If for all $x \in F$, we have $P(x)\in F$, then the coefficients of $P$ are in $F$.

Solution 3:

As other answers have indicated, a polynomial function over a finite field is not associated to a unique polynomial, so while you have found an example of a polynomial function $\Bbb F_2\to\Bbb F_2$ that is associated to a polynomial with coefficients in $\Bbb F_4$ (not in $\Bbb F_2$), it is also associated to the zero polynomial (or to $X^2-X$) which does have coefficients in $\Bbb F_2$.

If your goal is just to prove that the ring of polynomial functions over a finite field $F$ is never isomorphic to $F[X]$, then there are easy solutions. Most obviously, a set of functions from a finite set to itself is always finite (it has at most $n^n$ elements if the set has $n$ elements) while $F[X]$ is never finite: the set of monomials $\{\,X^i\mid i\in\Bbb N\}$ is an infinite subset (and an infinite basis of $F[X]$ as vector space ofver $F$). In fact it is easy to see that the set of polynomial functions over a finite field $F$ is equal to the set of all functions $F\to F$ (it suffices to produce polynomials that have roots in all points of $F$ but one, and then take linear combinations to produce any function). It is noteworthy that, unlike $F[X]$, the set of polynomial functions $F\to F$ is not an integral domain when $F$ is finite: any nonzero polynomial $P$ with at least one root has an associated polynomial function that is a zero divisor, as it can be multiplied by the product of factors $X-a$ where $a$ runs through the non-roots of $P$ to produce a polynomial whose polynomial function vanishes everywhere.

However the question in your title deserves an answer: given a field $F$ and a function $F\to F$ that is obtained from a polynomial but with coefficients in an extension of $F$, can it always (also) be obtained from a polynomial in $F[X]$? If $F$ is finite this is trivially so because every function $F\to F$ can be so obtained, so the question is essentially about infinite $F$. Here the answers is still affirmative (and since the polynomial to which the function is associated is unique here, one may conclude that in this case the "coefficients in an extension of $F$" must have been in $F$ in the first place). A proof follows from the formula for Lagrange interpolation: if $f$ is a polynomial function for a polynomial of degree $d$ with coefficients in any field, then the values of $f$ in $d+1$ distinct points permit constructing a polynomial of degree $d$ whose polynomial function agrees with $f$ in those points, and which must therefore be the original polynomial (since a polynomial of degree $d$ can have at most $d$ roots). If those points are chosen in a (sub-)field $F$ and the corresponding $d+1$ values of $f$ lie in $F$, then so do the coefficients of the Lagrange interpolation polynomial: one gets a polynomial in $F[X]$.

In case $F$ is a finite field $\Bbb F_q$, this shows that although (polynomial) functions $F\to F$ are associated to (infinitely) many polynomials, they are are associated to a unique polynomial of degree strictly less than $q$.