The magic of the Frobenius map II
June 9, 2009 by Qiaochu Yuan
Once upon a time I discussed some interesting uses of the Frobenius map to solve some Putnam-style problems. Unfortunately, I wrote that post before becoming really interested in combinatorics, so I neglected to develop that particular side of the story, which I’d like to do now.
The beginning of this story is the folklore combinatorial proof of Fermat’s little theorem: for any positive integer 
and prime 
, we have
.
The proof is simple but powerful. Consider the set of possible ways to color beads with colors. The cyclic group 
acts on this set in the obvious way. (One says that the beads are “on a necklace.”) The great thing about actions of a prime cyclic group is that elements arrange themselves into two kinds of orbits: fixed points and orbits of size . (This is just a special case of the orbit-stabilizer theorem.) The total number of colorings is 
, but if we only want to work 
it suffices to count the number of fixed points under the action of . These are precisely the colorings using only one color, of which there are , and the result follows.
The standard generalization of this result to finite fields is as follows: 
and is generated by the Frobenius map 
. Does this result also have a combinatorial proof?
What I can say with certainty is that certain consequences of this result are “visible” combinatorially. Here’s a fairly general situation in which this is true. Take a finite directed graph 
, pick a prime , and consider the set (if you prefer, species) of closed walks on ; let 
denote the number of closed walks of length 
. If 
are the roots of the characteristic polynomial 
of the adjacency matrix 
, i.e. the eigenvalues of the graph, then adjoining these roots to 
generates a finite field 
. Now, recalling that 
(and in fact this continues to hold over ), our Galois machinery tells us the following.
Proposition: 
.
This follows because is a permutation of the eigenvalues. But this result has a combinatorial proof along exactly the same lines as the FLT proof. (In fact, one recovers FLT by considering a graph consisting of a single vertex and self-loops.) There is a natural action of on the closed walks of length , and the only fixed points of this action are those involving copies of the same edge. The number of such walks is precisely the number of self-loops, i.e. the number of closed walks of length 
.
For example, applying this result to what I call the “Fibonacci graph” (two vertices, one edge between the two vertices, one self-loop) tells us that the Lucas numbers have this property; one usually says that the Lucas numbers count “circular arrangements” of tiles of size 
. What other consequences of the Galois theory of finite fields are “visible” combinatorially?
For the Fibonacci graph, we would need a way to “see” that either 
or 
, and the same for the conjugate. More precisely, this needs to be true in the finite field 
, which will have order either or 
depending on how the polynomial 
splits. Because of the identity
this will follow if we can give certain divisibility proofs about the Fibonacci, rather than the Lucas, numbers. But the corresponding paths aren’t acted on by in an obvious way. I do know that a combinatorial proof of the appropriate identities are possible (I believe they’re in Proofs that Really Count), but I don’t see a general framework here.
So what else can we say? Well, any sequence of the form 
is a sum of linear combinations of powers of the eigenvalues, so it has a period under the Frobenius map: there is some least 
such that 
. The curious thing is that depends on the factorization of the characteristic polynomial , so using combinatorial data alone it might be possible to determine the form of the factorization of the characteristic polynomial by using a sufficiently generic prime.
What is also interesting is that for values of such that irreducible factors of the characteristic polynomial ramify, the number of closed walks continues to only depend on an unweighted sum of eigenvalues, but other entries of the powers of the adjacency matrix may acquire a Jordan block structure and their periods would be different, so combinatorial data may also reveal such primes.
Questions
How much Galois theory can we develop in this way? Can we distinguish between the Galois groups of different irreducible polynomials of the same degree using combinatorial data alone?
To be more specific, is it possible to compute the primes dividing the discriminant of the characteristic polynomial from combinatorial considerations alone? (Again, Proofs that Really Count contains a combinatorial proof of an identity that “explains” that the characteristic polynomial of the Fibonacci numbers ramifies at 
, but I don’t see a general framework.)
To be even more specific, consider the graph with adjacency matrix
![\left[ \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{array} \right].](https://s0.wp.com/latex.php?latex=%5Cleft%5B+%5Cbegin%7Barray%7D%7Bccc%7D+0+%26+1+%26+0+%5C%5C+1+%26+0+%26+1+%5C%5C+1+%26+0+%26+0+%5Cend%7Barray%7D+%5Cright%5D.&bg=ffffff&fg=333333&s=0&c=20201002)
Explain why its characteristic polynomial ramifies at 
. Can you predict, without any explicitly Galois-theoretic machinery, whether the Galois group contains a transposition?
Like this:
Like Loading...
Related
Annoying Precision 
[…] This result also appeared in this previous blog post. […]
[…] of a homomorphismSquare roots have no unexpected linear relationshipsIMO 2009 and proof systemsThe magic of the Frobenius map IISome examples of graded […]
“How much Galois theory can we develop in this way? Can we distinguish between the Galois groups of different irreducible polynomials of the same degree using combinatorial data alone?”
Let f be a polynomial with integer coefficients, and no repeated roots, of degree n. For every prime p, we can consider F_p[roots of f]. For almost every p, f will have n distinct roots modulo p. We can compute how the Frobenius acts on these roots. The obvious combinatorial data here is the sizes of the orbits, which I can think of as a partition of n, or as a conjugacy class in S_n. This is easy to compute; you just factor f modulo p and look at the degrees of the factors. I talked about this here
In particular, we can ask whether the Frobenius fixes all the roots of f modulo p. We say that these are the primes for which f splits.
Theorem: Let f and g be two polynomials with integer coefficients. Then f and g have the same splitting field if and only if, except for possibly finitely many exceptions, f and g split for the same primes.
See, for example, Corollary 5.5 of Jansuz’s book on Algebraic Number Fields. It is true, but not obvious, that his definition of splitting matches the combinatorial one above.
Counterexample: It is possible that, for all primes, the Frobenius has the same combinatorial action on F_p[roots of f] and on F_p[roots of g], and yet Q[x]/f(x) and Q[x]/g(x) are not isomorphic.
Details of the counterexample: It is easiest to construct such an example with f and g reducible. For example, let f have roots
, 1 and 2 and let g have roots 
, 
and 
.
It is more difficult to construct examples with f and g irreducible, but it can be done. Hint: the Galois group should be S_6, and the stabilizer groups of Q[x]/f(x) and Q[x]/g(x) should be related by the outer automorphism of S_6.
[…] The magic of the Frobenius map II […]