The magic of the Frobenius map
by t0rajir0u, Oct 4, 2008, 12:36 AM
On the Putnam problem sets I have recently had to make repeated use of a straightforward but very useful tool usually first encountered during a thorough study of the theory of finite fields. Really, though, its motivation is quite elementary: one can begin with the following proof of Fermat's little theorem.
Given
, introduce the function
. It is clear that
and that
. It should also be clear that
. In other words,
respects multiplication and takes the additive (resp. multiplicative) identity to itself. What is surprising (and important) is that
also respects addition: it turns out that
.
Why? Well, in the binomial expansion of
every term except the first and last is of the form
, and it is easy to see that each of these binomial coefficients is divisible by
. One can either notice that the numerator contains
and the denominator doesn't or reason combinatorially: one can group the subsets of size
of a set of size
into groups of
subsets by "rotating" them (adding
if we imagine the set of size
to be the residues
), and we know that because
is prime a rotation of a subset is never itself unless that set is empty or the entire set. In either case, one immediately sees that these two properties tell us that


and so forth. In other words,
for all
.
This proof is sometimes referred to as the inductive proof, but that hides its elegance: what the properties we proved above tell us is that
is a (ring) endomorphism of
and that it fixes
. This tells us immediately that it fixes the subring generated by
, which is the entire ring, so in fact
is the identity, which is the statement of Fermat's little theorem.
This particular endomorphism is so nice that it is given a special name: it is called the Frobenius endomorphism. One might wonder why, seeing as how it's the identity here. But note that nowhere in establishing the properties of the Frobenius map did we use any properties of
other than the fact that multiples of
are zero. This suggests that it might be possible to define the Frobenius map in a more general context.
The key word here is characteristic. The rings and fields most students first encounter - real polynomials, the reals, the complex numbers - have characteristic
, which means that if we add
to itself repeatedly (or any other nonzero element) we never reach zero. On the other hand, rings like
have the property that if we add any element to itself
times, we will get zero. The smallest
for which this is true is called the characteristic of the ring.
The characteristic of a field is always prime (why?), and in a field with characteristic
the Frobenius endomorphism is a field endomorphism, so it still respects addition and multiplication and even respects inverses - but now it is not necessarily the identity.
What fields of characteristic
are there? Well, perhaps it would be easier to take about rings first. The ring of polynomials with coefficients in
(which is the notation I will switch to now as it is easier to type than
) is such a ring (in fact an integral domain). What does the Frobenius map do here? Well, since it respects addition as well as multiplication, and since it's the identity on
, it does this:

In other words, it multiplies each exponent by
. (Doing this in reverse gives the answer to Practice Problem 3 here.) So here although the Frobenius map is not the identity, it restricts to the identity on the constant polynomials and has a very straightforward effect on the rest of them.
How does this tie into the formal derivative? Well, notice that the derivative of any polynomial of the above form (that is, one raised to the
power) is of the form

In other words, any such polynomial
satisfies
and therefore has (many) repeated roots. For example, the polynomial
is really the polynomial
, which has a single root
with multiplicity
.
Why do we care? To avoid going too far afield, here is another keyword: separable extension.
First, an example of how the Frobenius map is used to deal with polynomials.
Problem 1 (Putnam 1983): Let
be an odd prime and define
.
Prove that if
and
are distinct integers in
then
and
are not congruent modulo
.
Solution. Thinking about formal derivatives leads us to the following idea:
is the formal derivative of
. Thinking about the Frobenius map leads us to the following idea:
, so
.
Simple polynomial division has led us to a nontrivial statement: what we have proven is that
. The above is a polynomial identity in
, since it only uses the properties of the Frobenius map. Now taking formal derivatives again gives us
.
Again we have a nontrivial statement:
(if I haven't messed up the signs). More importantly, we now know the following: if
then
. Otherwise,

by Fermat's Little Theorem - and this is not a polynomial identity. Since the multiplicative inverse is unique,
is a bijection on
as desired.
How about polynomials in more than one variable?
Problem 2 (Putnam 2002/B6): Show that the determinant

is congruent modulo
to a product of polynomials of the form
for some integers
.
Solution. Denote the above matrix by
and its determinant by
, which is a polynomial. If
are chosen to be arbitrary integers, it is clear that each column consists of identical entries and therefore that determinant is equal to
. It is tempting to conclude, by some sort of handwaving about division with multivariate polynomials, that divisibility follows. But of course this is far from rigorous. Rather, note that the successive rows appear to be successive applications of the Frobenius map.
This leads to the following idea: suppose
are integers such that
over a field of characteristic
. (We will be vague about what field this is for now.) Then it follows immediately that

and that

by the properties of the Frobenius map. (Remember that
are fixed under this map.) What these three relations tell us is that
is in the nullspace of
, and if we assume that
are not all zero, this tells us that
.
This is starting to look promising. Geometrically, what we showed was that if a point
over some field of characteristic
lies on the plane
, it also lies on the surface
. That is, one variety contains another. What we want to show is that this implies that
is a multiple of
. In other words, one ideal contains another.
An "elementary" approach to showing that this is true is to consider both polynomials as polynomials in
only. Upon performing the division algorithm, we get
where
with the property that
whenever
. Does it follow that
is the zero polynomial?
Well, not necessarily. A polynomial like
is also zero whenever
are elements of
, but it isn't the zero polynomial. What's missing here?
Earlier I didn't specify what field
were in. If they are just in the finite field
, then we can't conclude anything. What we really need is for this field to be large - really, infinite. One candidate for such a field is the algebraic closure
of
- the field that contains
and all the roots of polynomials with coefficients in
.
We can now proceed like this:
is zero whenever
. So fix
and let
vary. For any choice of
we can let
, so
is zero for infinitely many values of
(keeping
fixed) - but a polynomial in one variable cannot have infinitely many roots. It follows that
is the zero polynomial.
Of course, we are not restricted to single-variable division. What if we don't actually require that
take values in a concrete field at all? What if we only require that
abstractly? In other words, there is nothing stopping us from building the quotient ring
and arguing that what we just showed implies that
is zero in this ring, which implies that it lies in the ideal generated by
, and we are done. (
is shorthand for "the ideal consisting of the multiples of
."')
This is perfectly valid here, and it is a much more symmetric way of approaching the problem than one-variable division, but it is instructive to note that in general if we are given that a polynomial vanishes on a variety we cannot immediately conclude something about ideals. The connection between polynomials, the varieties they generate, and the ideals they generate is the subject of algebraic geometry (which I have discussed here before, but in less detail), and the relevant theorem here that allows us to make very general statements is the Nullstellensatz. For an accessible introduction to the theory, I highly recommend Cox, Little, and O'Shea.
So what does
actually look like? Well, we didn't put any conditions on
, so we don't need the product over all triples since any scalar multiple of a given factor is the same factor again.
is, by inspection, a polynomial of degree
, and that suggests that the correct thing to do is to take
to be elements of the projective plane
! This has precisely the two properties we want - invariance under scalar multiplication and ignoring
. We can therefore write, very succinctly,
.
Concretely, if we wanted to take some affine slices, we might write something like
.
Since the two polynomials have the same degree, we have accounted for all of the factors of
as desired.
I've hesitated to talk about finite fields in detail before, but I thought I'd take this opportunity to demonstrate how they can be relevant in solving a problem posed in the integers.
Problem 3: Let
be the usual Fibonacci sequence. Show that for every prime
either
or
. Which one?
Solution. The first strange thing to notice about this problem is that it contains the special condition that
is not equal to
. Why would there be any reason that the Fibonacci sequence behaves differently
than it behaves modulo other primes? Well, recalling that
and that
, we might have some vague notion about
behaving in odd ways
, whatever it means to take an irrational number mod a prime.
This notion can be made extremely precise. The basic problem here is that we want to prove something about the integers, but we want to do it by working with two kinds of "new" numbers: the integers
and the powers of
and
. How do we combine these two approaches?
The key word is splitting field. Whatever calculations we do in this problem, they should ideally take place in a field of characteristic
, and we can imagine doing all our computations here - calculating the Fibonacci sequence, etc. Now, Binet's formula is derived from solving the polynomial
. How does this polynomial behave modulo various primes?
The answer is provided by the fact that the quadratic formula works in any field (not of characteristic
). This is because completing the square only relies on field operations. What this tells us is the following:
- if
is a quadratic residue
and
, then the roots of
are
, which are actual residues
.
- Otherwise, no residue
is a solution.
There are two exceptional cases:
we must simply check that no solutions exist, and
the "square root" of
is
, so
contains a root of multiplicity two (which is
). What we said above is that if
(where I have used the Legendre symbol) then the splitting field of
over
is
; otherwise, the splitting field is
.
We'll get to what that second statement means soon, but back to solving the problem. In the first case that the splitting field is
, the problem is very easy: Fermat's Little Theorem tells us that
, therefore that
. Done!
So what does "the splitting field is
" mean in the second case? Well, it means that there exists a field which we can describe as
or, if you prefer, as
- the integers
together with some
satisfying
- such that the polynomial
splits completely into linear factors (which is true: it's equal to
). By the way, because the splitting field construction does in fact always produce a field out of an irreducible polynomial we have proven indirectly that
is prime in
, and the same proof can be applied to the splitting fields of
, respectively, over
to describe the Gaussian and Eisenstein primes.
Now, I wrote
as an abstract way of describing a very concrete field - we started with
and adjoined the root of an irreducible polynomial. It turns out that every finite field arises as part of such a construction and, even more amazingly, that a finite field is uniquely defined by its cardinality. (In other words, two finite fields of the same cardinality are isomorphic.) This field has
elements (which, concretely, are of the form
where
), of which all but the zero element are invertible. Moreover, this field has characteristic
, so the Frobenius map is a ring endomorphism (in fact a field homomorphism). It is even a surjection (hence an automorphism): if
then
. Finally, we know that it fixes the subfield generated by
, which here is
(the elements of the form
). So what does it do to the other elements?
Well, we know that the polynomial
has roots which are the elements of the prime subfield, and we know that the Factor Theorem is true over any field (prove this!), so no other elements of
are fixed by the Frobenius map. Furthermore, if we stop being abstract and use the concrete representation of
we can see that
, so the behavior of the Frobenius map on the other elements of
is determined by what
is. But because the Frobenius map is an automorphism, we know that
, so if
then
must be equal to
! In other words, on
the Frobenius map is conjugation.
Now that we have all this technical machinery, there's not much left to do. If
then
and the same is true of
, so
and
as desired. (Alternately, if the Frobenius map is conjugation then applying it twice gives the identity, so
. Now
and
must both have order
, but the roots of
are in the prime subfield, and since conjugation fixes the prime subfield we reach the same conclusion.)
The second argument I just made could also have been phrased in group-theoretic terms as follows: since
is a finite field, its
nonzero elements form a multiplicative group, so every element has order dividing
. The distinction between this idea and the Frobenius map is the distinction between two different proofs of Fermat's Little Theorem. Generalized, the first proof tells you that
in
(did I mention that these are the only possible cardinalities of a finite field?), while the second proof tells you that the Frobenius map is an element of the automorphism group of
, and so... what?
I mentioned that every finite field
can be constructed as the splitting field of an irreducible polynomial of degree
over
. Once we know this, we can see that if this polynomial is
and it has a root
then
, so the Frobenius map permutes the roots of
(think Galois group) and moreover has order
, which does tell us that
, but with a lot of other information besides! This is possibly the main reason why the Frobenius map is foundational to the theory of finite fields.
By the way, the fact that it is possible to argue combinatorially that
should suggest to you that it is possible to prove Fermat's Little Theorem by a combinatorial argument alone, and you would be right. This possibly constitutes a third distinct proof, although the similarity between the combinatorial argument you need here and the one we used already - and the group-theoretic link between this proof and the first - suggests that these may be one proof under three different guises.
Whew! That may have been a difficult argument to follow, but I hope you understand the gist of what's happening: in
, the behavior of the Fibonacci sequence is determined by the behavior of the roots of
. This connection continues to hold
as long as you move out of
and consider the behavior of the roots of
in
instead. We have not, by the way, discussed the solutions when
here; this is because what we have been doing is using Binet's formula over
, but Binet's formula fails
because
has repeated roots, so the actual formula looks different: we actually have

which should look familiar from our discussion of the solutions of linear recurrences where the characteristic polynomial has repeated roots.
I have neglected to tell you how to actually characterize the primes with quadratic residue
. The answer, given by quadratic reciprocity, is that

.
This tells us what the answer is when
even though we can't explicitly resort to the quadratic formula in that case. Abstractly, everything depends on whether
divides the discriminant of
. Now, it took us a lot of theory to get here. There are definitely approaches to this problem that require less technical machinery, but in the end we have an absolutely clear picture of why the different cases of the problem work out the way they do.
Practice Problem 1: Show that
for every prime
. Hint: look at the generating function
. Can you show that this congruence also holds
? (For
, how about
?)
Practice Problem 2: Show that for a prime
not equal to
, one has
. Hint:
.
Practice Problem 3: Show that the multiplicative group of a finite field
is cyclic. What are the elements of order
?
Practice Problem 4: Show that a finite field cannot be algebraically closed. (This justifies the assertion I made that the algebraic closure of
is infinite.) Hint: count irreducible polynomials.
Given








Why? Well, in the binomial expansion of













and so forth. In other words,


This proof is sometimes referred to as the inductive proof, but that hides its elegance: what the properties we proved above tell us is that





This particular endomorphism is so nice that it is given a special name: it is called the Frobenius endomorphism. One might wonder why, seeing as how it's the identity here. But note that nowhere in establishing the properties of the Frobenius map did we use any properties of


The key word here is characteristic. The rings and fields most students first encounter - real polynomials, the reals, the complex numbers - have characteristic





The characteristic of a field is always prime (why?), and in a field with characteristic

What fields of characteristic





In other words, it multiplies each exponent by

How does this tie into the formal derivative? Well, notice that the derivative of any polynomial of the above form (that is, one raised to the


In other words, any such polynomial






Why do we care? To avoid going too far afield, here is another keyword: separable extension.
First, an example of how the Frobenius map is used to deal with polynomials.
Problem 1 (Putnam 1983): Let


Prove that if






Solution. Thinking about formal derivatives leads us to the following idea:




Simple polynomial division has led us to a nontrivial statement: what we have proven is that

![$ \mathbb{F}_p[x]$](http://latex.artofproblemsolving.com/9/d/d/9dde639e1060a18820992b68150e46ca7a628995.png)

Again we have a nontrivial statement:




by Fermat's Little Theorem - and this is not a polynomial identity. Since the multiplicative inverse is unique,


How about polynomials in more than one variable?
Problem 2 (Putnam 2002/B6): Show that the determinant

is congruent modulo



Solution. Denote the above matrix by




This leads to the following idea: suppose




and that

by the properties of the Frobenius map. (Remember that

![$ \left[ \begin{array}{ccc} a \\
b \\
c \end{array} \right]$](http://latex.artofproblemsolving.com/d/1/c/d1c11a5ac15ce0aa21cf355cda538500b8e5ad62.png)



This is starting to look promising. Geometrically, what we showed was that if a point






An "elementary" approach to showing that this is true is to consider both polynomials as polynomials in


![$ R(y, z) \in \mathbb{F}_p[y, z]$](http://latex.artofproblemsolving.com/a/4/0/a40ed3f0e36a6f095fb02b0a124080cca5c684ea.png)



Well, not necessarily. A polynomial like



Earlier I didn't specify what field






We can now proceed like this:










Of course, we are not restricted to single-variable division. What if we don't actually require that


![$ \mathbb{F}_p[x, y, z]/(ax + by + cz)$](http://latex.artofproblemsolving.com/a/8/5/a85e9802be46f5a468e223e8421f91f5f6580655.png)




This is perfectly valid here, and it is a much more symmetric way of approaching the problem than one-variable division, but it is instructive to note that in general if we are given that a polynomial vanishes on a variety we cannot immediately conclude something about ideals. The connection between polynomials, the varieties they generate, and the ideals they generate is the subject of algebraic geometry (which I have discussed here before, but in less detail), and the relevant theorem here that allows us to make very general statements is the Nullstellensatz. For an accessible introduction to the theory, I highly recommend Cox, Little, and O'Shea.
So what does








Concretely, if we wanted to take some affine slices, we might write something like

Since the two polynomials have the same degree, we have accounted for all of the factors of

I've hesitated to talk about finite fields in detail before, but I thought I'd take this opportunity to demonstrate how they can be relevant in solving a problem posed in the integers.
Problem 3: Let




Solution. The first strange thing to notice about this problem is that it contains the special condition that







This notion can be made extremely precise. The basic problem here is that we want to prove something about the integers, but we want to do it by working with two kinds of "new" numbers: the integers



The key word is splitting field. Whatever calculations we do in this problem, they should ideally take place in a field of characteristic


The answer is provided by the fact that the quadratic formula works in any field (not of characteristic

- if






- Otherwise, no residue

There are two exceptional cases:











We'll get to what that second statement means soon, but back to solving the problem. In the first case that the splitting field is



So what does "the splitting field is

![$ \mathbb{Z}[x]/(p, x^2 - x - 1)$](http://latex.artofproblemsolving.com/6/9/8/698d6d29b23f19875ae06d29f9f52640526dc990.png)
![$ \mathbb{Z}/p\mathbb{Z}[\phi]$](http://latex.artofproblemsolving.com/1/d/4/1d455323711a8e6e99e56f39a78a82f24b75bc38.png)






![$ \mathbb{Z}[\phi]$](http://latex.artofproblemsolving.com/6/5/8/65864f2e0b24ca2e4d77df533c12f6d85383bab3.png)


Now, I wrote











Well, we know that the polynomial











Now that we have all this technical machinery, there's not much left to do. If










The second argument I just made could also have been phrased in group-theoretic terms as follows: since






I mentioned that every finite field









By the way, the fact that it is possible to argue combinatorially that

Whew! That may have been a difficult argument to follow, but I hope you understand the gist of what's happening: in











which should look familiar from our discussion of the solutions of linear recurrences where the characteristic polynomial has repeated roots.
I have neglected to tell you how to actually characterize the primes with quadratic residue



This tells us what the answer is when



Practice Problem 1: Show that






Practice Problem 2: Show that for a prime




Practice Problem 3: Show that the multiplicative group of a finite field


Practice Problem 4: Show that a finite field cannot be algebraically closed. (This justifies the assertion I made that the algebraic closure of
