The goal of this post is to collect a list of applications of the following theorem, which is perhaps the simplest example of a fixed point theorem.
Theorem: Let be a finite -group acting on a finite set . Let denote the subset of consisting of those elements fixed by . Then ; in particular, if then has a fixed point.
Although this theorem is an elementary exercise, it has a surprising number of fundamental corollaries.
Proof
is a disjoint union of orbits for the action of , all of which have the form and hence all of which have cardinality divisible by except for the trivial orbits corresponding to fixed points.
Some group-theoretic applications
Theorem: Let be a finite -group. Then its center is nontrivial.
Corollary: Every finite -group is nilpotent.
Proof. acts by conjugation on . If , this set has cardinality , which is not divisible by . Hence has a fixed point, which is precisely a nontrivial central element.
Cauchy’s theorem: Let be a finite group. Suppose is a prime dividing . Then has an element of order .
Proof. acts by cyclic shifts on the set
since if then . This set has cardinality , which is not divisible by , hence has a fixed point, which is precisely a nontrivial element such that .
Some number-theoretic applications
Fermat’s little theorem: Let be a non-negative integer and be a prime. Then .
Proof. acts by cyclic shifts on the set , where ; equivalently, on the set of strings of length on letters. (Orbits of this group action are sometimes called necklaces; see, for example, this previous blog post.) This set has cardinality and its fixed point set has cardinality , since a function is fixed if and only if it is constant.
Fermat’s little theorem for matrices: Let be a square matrix of non-negative integers and let be a prime. Then .
This result also appeared in this previous blog post.
Proof. Interpret as the adjacency matrix of a graph. acts by cyclic shifts on the set of closed walks of length on this graph. This set has cardinality and its fixed point set has cardinality , since a closed walk is fixed if and only if it consists of repetitions of the same loop at a vertex.
In the same way that Fermat’s little theorem can be used to construct a primality test, the Fermat primality test, Fermat’s little theorem for matrices can also be used to construct a primality test, which doesn’t seem to have a name. For example, the Perrin pseudoprimes are the numbers that pass this test when
.
More generally, a stronger version of this test gives rise to the notion of Frobenius pseudoprime.
Wilson’s theorem: Let be a prime. Then .
Proof. Consider the set of total orderings of the numbers modulo addition ; that is, we identify the total ordering
with the total ordering
where the addition occurs .
acts by cyclic shifts on this set. It has cardinality and its fixed point set has cardinality , since the fixed orderings are precisely the ones such that for some .
Lucas’ theorem: Let be non-negative integers and be a prime. Suppose the base- expansions of are
respectively. Then
.
Proof. It suffices to show that
where , and then the desired result follows by induction. To see this, consider a set of size , and partition it into a block of size together with blocks of size . Identify all of the blocks of size with each other in some way. Then acts by cyclic shift on these blocks. This action extends to an action on the set of subsets of of size . A fixed point of this action consists of a subset of the block of size together with copies of a subset of any block of size . Since the union of the copies has size divisible by , and since , it follows that there must be elements in the block of size and elements in each of the blocks. Thus the set of subsets has cardinality , and its fixed point set has cardinality .
(It is also possible to prove this result directly by considering a more complicated -group action. The relevant -group is the Sylow -subgroup of the symmetric group of . It is an iterated wreath product of the cyclic groups , and describing how it acts on requires recursively partitioning blocks in a way that is somewhat tedious to describe.)
The following proof is due to Don Zagier.
Fermat’s two-square theorem: Every prime is the sum of two squares.
Proof. Let be the set of all solutions in the positive integers of the equation . The involution has the property that its fixed points correspond to solutions to the equation . We will show that such fixed points exist by showing that there are an odd number of them; to do so, it suffices to show that is odd, and to show that is odd it suffices to exhibit any other involution on which has an odd number of fixed points. (Notice that this is two applications of the -group fixed point theorem.) We claim that
is an involution on with exactly one fixed point, which suffices to prove the desired claim. Verifying that it sends to is straightforward. If is a fixed point, then since are all assumed to be positive integers we cannot have , so we are not in the first case. If we are in the second case, we conclude that , but then , and since we conclude that , which gives . If we are in the third case, we conclude that , then that , but this contradicts . Hence is the unique fixed point as desired.
The following proof is due to V. Lebesgue.
Quadratic reciprocity: Let be odd primes. Let denote the Legendre symbol. Then
.
Proof. Let be an odd prime and consider the set
.
For an odd prime, we will compute in two different ways. The first way is to observe that acts by cyclic shifts on . The number of fixed points is the number of such that , hence
.
The second way is to find a recursive formula for which will end up being expressed in terms of . The details are as follows.
First, it is clear that . For nonzero, we claim that is independent of . First, observe that by the pigeonhole principle (there are possible values of and possible values of , hence at least one common value) we always have . Second, observe that the map is the norm map from to ; in particular, it restricts to a homomorphism from the unit group of the former ring to the unit group of the latter ring, and we know that this homomorphism is surjective, so each fiber has the same size. The unit group of has size if (since then we are looking at ) and size if (since then we are looking at ). Hence
for any nonzero . When , the equation always has the solution . There are no nonzero solutions if (since does not have a square root) and nonzero solutions if (since for each of the possible values of there are possible values of ). Hence
.
We will now compute inductively by rewriting as
.
From this it follows that
.
We know that takes the value for possible values of and takes any particular other value for possible values of . Hence we can write
But it’s clear that
since this is just the number of possible tuples . Hence
.
This gives a recursion which we can unwind into an explicit formula for as follows. Substituting the recursion into itself and canceling terms gives
.
This pattern continues, and by induction we can show that
.
Hence if is odd, we conclude that
.
Now let be an odd prime. Then by Fermat’s little theorem and by Euler’s criterion, so we we find that
.
On the other hand, we know that . We conclude that
and since the LHS and RHS are both equal to this equality holds on the nose.
This proof is in some sense a proof via Gauss sums in disguise; the numbers are closely related to Jacobi sums, which can be written in terms of Gauss sums. More generally, various kinds of exponential sums can be related to counting points on varieties over finite fields. The Weil conjectures give bounds on the latter which translate into bounds on the former, and this has various applications, for example the original proof of Zhang’s theorem on bounded gaps between primes (although my understanding is that this step is unnecessary just to establish the theorem).
Similar methods can be used to prove the second supplementary law, although strictly speaking we will use more than the -group fixed point theorem.
Quadratic reciprocity, second supplement: . Equivalently, iff .
Proof. We will compute in two different ways. The first is using the formula we found earlier, which gives
.
The second is to observe that the dihedral group of order acts on by rotation and reflection (thinking of the points as being on the “circle” defined by ). Most orbits of this action have size and hence are invisible . The ones that are not invisible correspond to points with some nontrivial stabilizer. Any stabilizer contains an element of order , and there are five such elements in , so the remaining possible orbits are as follows:
- Points stable under . These are precisely the points such that , hence there are of them.
- Points stable under . These are precisely the points such that , hence there are of them.
- Points stable under . These are precisely the points such that , hence there are of them.
- Points stable under . There are no such points.
- Points stable under . These are precisely the points such that , hence there are of them.
In total, we conclude that
and the conclusion follows.
A general lesson of the above proofs is that it is a good idea to replace integers with sets because sets can be equipped with more structure, such as group actions, than integers. This is a simple form of categorification.
[…] -group fixed point theorem (PGFPT): If is a finite -group and is a finite set on which acts, then the subset of fixed […]
Here is one I like to use when I prove the Sylow theorems via Wielandt’s proof. If , then . The proof is let be the subgroup of of order and have it act on the subsets of size of by translations. Then clearly the fixed points are the cosets of . The fixed point theorem gives the desired conclusion.
Now to get the Sylow theorems let be a group of order with . Then acts on the set of its subsets of order by translation. By the above paragraph, does not divide the size of and so not all stabilizers have index divisible by . Let be a subset of size whose stabilizer has index prime to . Since acts freely on it follows the order of is a -power so we conclude is a -Sylow subgroup.
Can you explain why the last sentence implies the claim?
The last sentence of the proof of Wilson’s theorem? Apply the fixed point theorem.
for wilson theorem proof, why does cardinality of fixed point set equal cardinality of set itself?
It doesn’t. The claim is just that they’re equivalent .
Perhaps the following deserves a mention? P.G. Anderson, A.T. Benjamin and J.A. Rouse “, ‘Combinatorial Proofs of Fermat’s, Lucas’s, and Wilson’s Theorems”, American Mathematical Monthly, 115, 2005, 266–268.
Thanks for the reference! I wasn’t aware of it. My understanding is that the Lucas proof is well-known (at least, it’s on the Wikipedia article) but I didn’t know a reference for the Fermat or Wilson proofs.
Since the application to the main law of quadratic reciprocity only requires the case of $S_n(a,p)$ for odd $n$, I think you should work out that case first and separately from the case of even $n$. After proving the main law of QR, come back and work out the formula for even $n$.
But don’t I need to get the induction to work?
Yes, just $S_2$ among even-indexed cases is needed. You don’t need $S_n$ for even $n > 2$. I meant to suggest delaying the even case for $n > 2$.
also: mod p irreps of p-groups can only be trivial
Yes, this is a nice application too (the set of nonzero vectors in a finite-dimensional vector space over has cardinality not divisible by so any -group representation on such a vector space has a fixed point, hence an eigenvector), and draws attention to an interesting analogy between finite -groups and solvable linear algebraic groups in light of the Lie-Kolchin theorem.