### Involutions

Before we generalize this method of complementation we should recall
lemma.
It shows that each action of the form
_{H ´G}Y^{X} can be considered as an action of *H* on *G \\Y*^{X} or
as an action of *G* on *H \\Y*^{X}. Hence each such action of
*S*_{2} ´G on *2*^{X} gives rise to an action of *S*_{2} on
*G \\2*^{X} and leads us to the discussion of the Involution
Principle.
We call a group element * t not = 1* an *involution*
if and only if * t*^{2}=1. The Involution Principle is a method of counting objects by simply
defining a nice involution * t* on a suitably chosen set *M* and using
the fact that *S*_{2} simeq {1, t} has orbits of length 1 (the
selfenantiomeric orbits) and of length 2 (which form the enantiomeric pairs)
only. A typical example is the complementation * t* of graphs
which is, for *v >= 2*, an involution on the set of graphs on *v* vertices. An even easier case
is described in

**Examples: **
We wish to
prove that the number of divisors
of *n Î ***N**^{*} is odd if and only if *n* is a square. In order to do
this we consider the set *M:= {d Î ***N** | d divides n } of
these divisors and define
* t:M -> M :d -> n/d. *

This mapping
is an involution, if *n>1*, and obviously * | M | * is odd if and only if
* t*
has a fixed point, i.e. if and only if
there exists a divisor *d* such that *d=n/d*, or,
in other words, if and only if *n=d*^{2}.
A less trivial example is the following proof (due to D. Zagier) of the fact
that every prime number which is congruent 1 modulo 4 can be expressed as
a sum of two squares of positive natural numbers. Consider the set
*S:= {(x,y,z) Î( ***N**^{*})^{3} | x^{2}+4yz=p }.

The following map is an involution on *S* (exercise):
*t:(x,y,z) -> (x+2z,z,y-x-z) if x<y-z,*

*t:(x,y,z) -> (2y-x,y,x-y+z) if y-z<x<2y,*

*t:(x,y,z) -> (x-2y,x-y+z,y) if x>2y.*

This involution has exactly one fixed point, namely *(1,1,k)*, if *p=4k+1*,
therefore * | S | * must be odd, and consequently the involution
* s:(x,y,z) -> (x,z,y) *

possesses a fixed point, too, which shows that *p=x*^{2}+4y^{2}, a sum of two
squares.

last changed: January 19, 2005