\usepackageamsmath

Polynomials over a finite field vs polynomial functions on a finite field

Polynomials are formal sums. So in particular, K[x] is infinite-dimensional over K, even if e.g. K=F2, the field with two elements. This is true even though e.g. x2x is the zero function on F2, as you can check by substituting 0 and 1 for x.

Polynomial functions are functions e.g. on the field itself (or, more generally, on some object that can be locally parameterized by the field). But let’s simply consider Poly(K), the set of polynomial functions from the field to itself. Poly(K) is a ring with addition and multiplication given point-wise on function values. Any polynomial can be considered a polynomial function in the obvious manner, and this defines a surjection of rings:
π:K[x]Poly(K).
In the case where K is a finite field, Poly(K) is a proper quotient of K[x] i.e. kerπ0. To see this, consider the multiplicative group K×. Then |K×|=q1, where q=|K|. Therefore aq1=1 for any aK×, and so aqa=0 for any aK=K×0. We’ve shown therefore that the non-zero polynomial xqx is in kerπ, since it is maps to the zero function on K. This is just the generalization of our observation for F2, above.

In fact, we’ve found a generator for the kernel, i.e. kerπ=xqx. One way to see this is to check that the polynomial functions defined by first q1 monomials are linearly independent as functions on K, which can be done using the Vandermonde matrix and the q1 distinct non-zero field elements at your disposal. Another way to see this, since we are working over a finite field, is to simply count the elements of the quotient K[x]/xqx and of Poly(K). There are clearly qq elements in the quotient, but what about Poly(K)? It turns out that Poly(K) consists of all functions KK. To see this, given any function on K, just use Lagrange interpolation to build yourself a polynomial of degree <q that matches the function at all points. There are qq functions KK, and so that’s the size of Poly(K).
Thus the quotient K[x]/xqx has the same number of elements as Poly(K). But we have a chain of surjections
K[x]/xqxK[x]/kerπPoly(K),
so kerπ=xqx.

On the other hand, if the field K is infinite, then kerπ is zero, i.e. polynomials over K and polynomial functions on K are isomorphic. To see this just show that the set of all monomials is linearly independent, using the Vandermonde matrix and the endless supply of distinct non-zero elements of K.

The multivariate case is entirely analogous

All functions KnK are polynomial functions. To see this, just mimic the Lagrange interpolation of the univariate case (it’s sufficient to convince yourself that, given any point in Kn, you can write down a polynomial function that takes the value 1 there, and the value 0 everywhere else). Thus, since there are qqn functions KnK, this is the size of Polyn(K), the ring of polynomial functions on Kn.

Now write π:K[x1,,xn]Polyn(K) for the obvious surjection of rings. Then it follows immediately from the univariate case that we have an inclusion of ideals xiqxi|i=1,,nkerπ. Now notice that the quotient K[x1,,xn]/xiqxi|i=1,,n has qqn elements. This is the same number as above, and so we conclude that we’ve already found the full kernel, i.e. kerπ=xiqxi|i=1,,n.



One Reply to “Polynomials over a finite field vs polynomial functions on a finite field”

Leave a Reply

Your email address will not be published. Required fields are marked *