Involutions

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₂ ´G on 2^X gives rise to an action of S₂ 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²=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₂ 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². 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^*)³ | x²+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²+4y², a sum of two squares.

Involutions