Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
    
Thanks, I didn't see the involution result as special case of this. –  Phira May 19 '11 at 16:05
    
Are there any long proofs of FlT? (Anyway, +1.) –  Pete L. Clark May 19 '11 at 16:06
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!) –  Qiaochu Yuan May 19 '11 at 16:08
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, ...) –  Myself May 19 '11 at 16:27
2  
@myself: that is the famous McKay proof of Cauchy's theorem. I like it too... –  Pete L. Clark May 19 '11 at 18:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.