# Examples for existence proofs using the parity of fixed points of involutions

On Wikipedia, I have seen a nice proof of Zagier for the existence of representations of primes as sum of two squares:

http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier.27s_.22one-sentence_proof.22

The proof uses the (trivial) fact that the number of fixed points of an involution of a finite set has the same parity as the cardinality of the set itself.

Do you know any other examples for existence proofs using the parity of fixed points of involutions?

-

A more general fact is that the number of fixed points of the action of a finite $p$-group on a finite set has the same cardinality $\bmod p$ as the set itself. This is used, for example, to prove that finite $p$-groups have nontrivial center and it is also part of the proof of the Sylow theorems.
While this isn't an existence proof, it can also be used to give a short proof of Fermat's little theorem: given a positive integer $a$, consider the action of $\mathbb{Z}/p\mathbb{Z}$ by cyclic permutation on the set of words of length $p$ on an alphabet of size $a$. There are $a$ fixed points and $a^p$ words, hence $a^p \equiv a \bmod p$.
@Pete: I confess my affection for this proof has less to do with how short it is and more to do with the fact that it does not naturally generalize to Euler's totient theorem. Instead, it naturally generalizes to the statement that $n | \sum_{d | n} \mu(d) a^{n/d}$. (It also generalizes to integer matrices!) –  Qiaochu Yuan May 19 '11 at 16:08
There is an exercise in M. Isaac's Finite Group Theory that uses this idea to prove Cauchy's theorem. For group $G$ Let Z/pZ work on sequences $(a_1,...,a_p)$ that in addition satisfy $a_1\cdots a_p = 1$. (Since there are $|G|^{p-1} \equiv 0 \pmod p$ such sequences and (1,...,1) is a fixpoint, ...) –  Myself May 19 '11 at 16:27