6
$\begingroup$

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?

1 Answers 1

7

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$.

  • 0
    Thanks, I didn't see the involution result as special case of this.2011-05-19
  • 0
    Are there any long proofs of FlT? (Anyway, +1.)2011-05-19
  • 2
    @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!)2011-05-19
  • 1
    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, ...)2011-05-19
  • 2
    @myself: that is the famous McKay proof of Cauchy's theorem. I like it too...2011-05-19