Involutions
Before we generalize this method of complementation we should recall
lemma.
It shows that each action of the form
H ´GYX can be considered as an action of H on G \\YX or
as an action of G on H \\YX. Hence each such action of
S2 ´G on 2X gives rise to an action of S2 on
G \\2X and leads us to the discussion of the Involution
Principle.
We call a group element t not = 1 an involution
if and only if t2=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 S2 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=d2.
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 | x2+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=x2+4y2, a sum of two
squares.
last changed: January 19, 2005