The Involution PrincipleThe involution principleSelfcomplementary graphsInvolutions

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.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

The Involution PrincipleThe involution principleSelfcomplementary graphsInvolutions