Colourings of the n Gon

Colourings of the n Gon

Example: Let C_p denote the following cyclic subgroup of sup:

C_p:= á(1 ...p) ñ <= S _p.

It acts on the set X:= p= {1, ...,p } and hence, see the paragigmatic examples, also on the set Y^X:= m ^p, which can be considered as the set of all the colourings of the regular p-gon in m colours. For example, in the case when p:=5 and m=2, C ₅ acts on the set 2 ⁵, consisting of all the 32 colourings of the regular pentagon with two colours (black and white), some of which are shown in the figure below.

 

Three colourings of the regular 5-gon.

We now assume that p is a prime. The Lemma shows that C _p contains, besides the identity element, p-cycles only. The identity element of C _p keeps each f Î m ^p fixed, while each p-cycle fixes the m monochromatic colourings only (notice that (1 ...p) acts as a clockwise rotation of the p-gon after having numbered the vertices of the p-gon from 1 to p, counterclockwise). Hence we obtain from the Cauchy-Frobenius Lemma that

| C_p\\m^p | = (1)/(p)(m^p+(p-1)m),

provided that p is a prime number. This implies that m^p+(p-1)m, and hence also m^p-m, is congruent zero modulo p, for each positive integer m. It is clear that this is then also true for any integer z. In the case when z is not divisible by p, we may even divide the difference z^p-z by z, obtaining

Fermat's Congruence If p is a prime number and z an integer which is prime to p, then

z^p-1 º1 (p).

This shows that group actions can also be useful in elementary number theory, and it seems appropriate to emphasize the following immediate implication of the Cauchy-Frobenius Lemma:

Corollary: For any action of a finite group G on a finite set X we have the congruence

å_{g ÎG} | X_g | º0 ( | G | ).

Colourings of the n Gon