Commutative groups 1

Ivan Cnop, 
Vrije Universiteit Brussel
icnop@vub.ac.be

Addition modulo  n   in   (Subscript[Z, n])

Preliminary remarks:

It is recommended to start a new Kernel session to avoid interference by old definitions. 
Do not evaluate the full notebook unless you are working on a very fast computer.
The defintion of    Z   (for Z- transform) in  Mathematica  is different from the one below. 
Nevertheless we will use the capital   Z  for our definition of integers and rests by division modulo  n  since this will not lead to confusion.
To be able to work with any    n  we will place this integer between brackets  [  ]  since it is the argument of a function whose values are of type  "List"  . The usage of list programming is limited in this notebook to the very simple Range, Length and Select commands that perform exactly what their name suggests. No hidden programming is necessary.

Addition in    (Subscript[Z, n])

Integer division and rest modulo  n

Mod[129, 20]

Z[n_] := Range[n] - 1

Z[20]

Addition

add[k_, m_, n_]:=Mod[k +  m, n]

The result of this operation is not influenced by adding multiples of   n  since these divide out in the integer division by   n  :

add[4 +  n, 5  -  2 n, n]

The full set of all sums is given by the addition table :

\(addTable[n_] := 
      Table[add[\(Z[n]\)[\([i]\)], \(Z[n]\)[\([j]\)], n\ \ ]
			, {i, 
          Length[Z[n]]}, {j, Length[Z[n]]}
			]\)

which can be written in short form using the Outer command

add2Table[n_] := Outer[add[#1, #2, n] &, Z[n], Z[n]]

add2Table[17] // TableForm

Color representation

Coloring according to Hues is natural for a cyclic set of elements. 
The zero element is red if we define

colors[m_,n_]:=Hue[m/n]

and the full set of sums

a[n_]:=Table[
			colors[
					add[Z[n][[i]],Z[n][[j]],n]
				,n]
			,{i,Length[Z[n]]},{j,Length[Z[n]]}
		]

Show[Graphics[RasterArray[a[17]]], AspectRatio -> Automatic]

Show[Graphics[RasterArray[a[71]]], AspectRatio -> Automatic]

These are very regular diagrams. For larger values of   n   the graphics have to be stretched to exhibit the blocking in their colors.

Show[Graphics[RasterArray[a[125]]], 
      AspectRatio -> Automatic]

Questions

- wat is the negative of an elementin such a diagram?
    
- where do you locate the double of an element in such a diagram?

Multiplication in    (Subscript[Z, n])  does not yield a similar result

mult[k_, m_, n_]:=Mod[k m, n]

\(multTable[n_] := 
      Table[mult[\(Z[n]\)[\([i]\)], \(Z[n]\)[\([j]\)], n\ \ ]
			, {i, 
          Length[Z[n]]}, {j, Length[Z[n]]}
			]\)

Again, this can be written in   Mathematica   shorthand:

mult2Table[n_] := Outer[mult[#1, #2, n] &, Z[n], Z[n]]

The full multiplication table has zeroes at unexpected locations. Non-zero numbers with zero productare called divisors of zero.

multTable[6] // TableForm

mat[n_]:=Table[
				colors[
					mult[Z[n][[i]],Z[n][[j]],n  ]
					,n]
				,{i,Length[Z[n]]},{j,Length[Z[n]]}
			]

Z[12]

multTable[12] // TableForm

Naming the elements on the axes in a color diagram is useful to locate zero divisors. We want these marks in the middle of each colored interval

Clear[ticks]

ticks[n_] := {Transpose[{Range[n] -  .5, Z[n]}], 
        Transpose[{Range[n] -  .5, Z[n]}]}

n = 6; 
    Show[Graphics[RasterArray[mat[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 36; 
    Show[Graphics[RasterArray[mat[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Question

- Can you find a common property of these zero divisors? 

- For what values of   n   do we avoid having zero divisors?

The case   n = prime

n = 13; 
    Show[Graphics[RasterArray[mat[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

In such a graphic, we find multiplication inverses for all elements except zero.

These inverses multiply out to the element 1, which is the darkest orange in the color scheme. Such an orange field can be found in every line or column of the color graphic.
Their existence is the stated in a theorem by Bezout. 
In fact, such a result goes back to the ancient Chinese mathematics where it is known under the name "Chinese remainder theorem".

Discard the previous definitions

Clear[a, mat, add, mult, ticks]

Multiplicative groups of units in    (Subscript[Z, n])

We do not assume   n   prime any more. 
We will eliminate zero and all zero divisors from the previous graphics and keep only those elements that are relatively prime with  n  .

Definition of   (Subscript[U, n])

Selecting relatively prime elements

Z[n_] := Range[n]

Z[20]

relPrimeQ[k_, n_] := If[GCD[k, n] == 1, True, False]

relPrimeQ[14, 20]

U[n_] := Select[Range[n], relPrimeQ[#, n] &]

U[48]

Length[U[48]]

Euler Phi function

The number of integers up to   n   relatively prime with   n   is called the Euler   Phi   function

EulerPhi[48]

ϕ(48)

ListPlot[ Table[EulerPhi[n], {n, 48}] ]

Multiplication in   (Subscript[U, n])

Definition of multiplication

mult[k_, m_, n_]:=Mod[k m, n]

\(multTable[n_] := 
      Table[mult[\(U[n]\)[\([i]\)], \(U[n]\)[\([j]\)], n\ \ ]
			, {i, 
          Length[U[n]]}, {j, Length[U[n]]}
			]\)
\(			\)

multTable[48] // TableForm

Setting colors and values on the axes.

Since we know that for multiplication the   1   element will play a role similar to the zero in the addition case, we shift all colors

colors[m_,n_]:=Hue[(m-1)/n ]

g[n_]:=Table[colors[
					mult[U[n][[i]],U[n][[j]],n  ]
					,n]
				,{i,Length[U[n]]},{j,Length[U[n]]}
				]

ticks[n_] := {Transpose[{Range[Length[U[n]]] -  .5, U[n]}], 
        Transpose[{Range[Length[U[n]]] -  .5, U[n]}]}

n = 48; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 7; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Again, we have to stretch graphics for larger values of  n  to see all information:

n = 148; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Length[First[ticks[148]]]

Recognition of group structure

Question

- Where do you see the color of squares of the elements?

- What difference do you see about these squares in the following examples:

n = 8; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 10; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 12; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Question

Try this again for slightly larger values of   n  .

n = 24; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Recognition of subgroups

Question

- Can you identify subsquares by their color in the same examples?

n = 8; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 10; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 12; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Try this out again for slightly larger values of   n  .

n = 15; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 24; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 26; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 15; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 35; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 24; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

n = 26; 
    Show[Graphics[RasterArray[g[n]]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> ticks[n]]

Elements generated by an element in   (Subscript[U, n])

Powers of an element are obtained by frequent application of multiplication to it. 
This is written in  Mathematica  shorthand by NestList.

NestList[mult[U[n][[3]], #, n] &, 1, Length[U[n]]]

From this list we have to eliminate doubles:

\(generated[i_, n_] := 
	
      Union[NestList[mult[\(U[n]\)[\([i]\)], #, n] &, 1, 
          Length[U[n]]]]\)

generated[3, 48]

generated[2, 48]

The number of different powers we can build from a single element is called its order

order[i_, n_] := Length[generated[i, n]]

n = 48; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 20; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 24; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

Recognition of cyclic groups

\(We\ apply\ the\ previous\ scheme\ to\ check\ if\ there\ are\ elements\ that\ generate\ the\ full\ group\ \ U\_n . 
In\ this\ case\ we\ call\ the\ group\ cyclic\)

n = 10; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 26; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

Sort[%]

n = 35; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

Sort[%]

n = 31; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 17; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 19; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 23; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 29; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

All these are cyclic. This is no accident. But it is not always true, as we already have seen before:

n = 8; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 12; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

n = 36; EulerPhi[n]
Table[order[i, n], {i, Length[U[n]]}]

Question

Can you identify in the cases    n = p q   when  the group is cyclic? Hint: this will depend on the values of    p-1   en   q-1   .

This again is a consequence of the Chinese remainder theorem.

Caution: computation of the elements generated by a single element can take a long time.

PrimeQ[97]

PrimeQ[113]

n = 97 31; EulerPhi[n]

Compute the orders of a few elements

Table[order[i, n], {i, 15, 20}]

Sort[%]

2880/480

GCD[96, 30]

Again, this group is not cyclic because of the Chinese remainder theorem and so there are no elements of orderr   n   .

In some cases the use of the built-in command PowerMod will speed up such computations.

The following takes too much time and requires different programming to be executed

Table[order[i, n], {i, Length[U[n]]}]

?PowerMod

order2[i_, n_] := 
      Length[Union[
          Table[PowerMod[U[n][[i]], j, n], {j, n}]]]

n = 36; Table[order2[i, n], {i, Length[U[n]]}]

Clearly not cyclic (but all orders are divisors of the number of elements 12 )

n = 97; Table[order2[i, n], {i, Length[U[n]]}]

Is cyclic as expected.

We can now tackle some larger n:

n = 37 17
EulerPhi[n]

Permuting the elements to identify subgroups in the non-cyclic case.

Question

Can the blocking in subgroups be recovered if we permute the elements in U ?

Try this in the case n=10. 
We use new definitions independent of   n   so that   U   is not computed as  U[n]  before

n = 10; U = {1, 9, 7, 3}

g:=Table[colors[
					mult[U[[i]],U[[j]],n  ]
					,n]
				,{i,Length[U]},{j,Length[U]}
				]

Show[Graphics[RasterArray[g]], AspectRatio -> Automatic, 
      Axes -> True, Ticks -> None]

Try this again for subgroups generated by an element