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.
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.
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
Explain why its characteristic polynomial ramifies at . Can you predict, without any explicitly Galois-theoretic machinery, whether the Galois group contains a transposition?