Implementing mathematical concepts in Mathematica: 
Quotients in permutation groups.

Ivan Cnop
Vrije Universiteit Brussell
Pleinlaan 2, B 1050 Brussels, Belgium
icnop @ vnet3.vub.ac.be
Presented at the Koblenz  ICTMT3 Conference,1997

Introduction

Understanding quotients poses problems for the average student. This is the case even for discrete and finite structures. A quotient is a set of equivalence classes under some equivalence relation. In some cases the quotient inherits the operations on the original structure and the properties thereof. Here color coding can help understanding how quotients work. Such color codings are quite natural and readily available in the  Mathematica  documentation. The Color wheel is the most obvious example: its Hues correspond to equal arguments and saturation corresponds to moduli. Coloring polar coordinates is the simplest example of coloring in the ComplexMap Package. Along the same idea, a ContourPlot or DensityPlot of a function shows the equivalence relating points with nearby values by coloring or shades of grey. In this case little algebraic or geometric structure is involved, except for some very special functions.

In other cases, it is possible to get useful information by coloring objects in the right way. Coloring a sphere or a torus according to meridians (longitude) and latitudes explains how they relate to rectangles in the plane. These colorings are done using the parameters in the ParmetricPlot command. Spherical coordinates blow up near the poles on a sphere. They do not blow up on  a torus. Thus we find that identifying opposite sides of a rectangle with periodic coloring, this rectangle can be rolled into a tube which can then be turned into a torus. Rolling first in either direction gives the same final result. If one tries to do a similar coloring on the Klein Bottle according to the longitude and latitude parameters it will lead to the surprising result that in one direction the coloring must be symmetric around the axis. The portion next to this axis is turned into a Mobius strip.

Substantial information about finite groups can be derived from appropriate colorings of the geometric objects under consideration. Choosing an appropriate coloring of the Dodecahedron exhibits an inscribed cube (or an inscribed tetrahedron) and enables us to investigate which rotations of the Dodecahedron preserve the inscribed cube (or the inscribed tetrahedron), showing interesting subgroups. Rotations or order five preserve neither of these. Coloring the four diagonals of the cube will then show that mappings of a cube onto itself are all permutations on four elements. This brings us to the abstract setting of permutation groups.

Abstract groups require some care. Here is a setup of input lines for obtaining quotients by a subgroup in the group of permutations on a set of n elements. In this text user-defined functions are not capitalised.

Permutation subgroups

Lists of permutations [includes package, objects, perms, comp]

<<DiscreteMath`Permutations`

In this example, we consider permutations on a set with four elements

n=4;
objects=Table[j,{j,n}];

perms=Permutations[objects];

Each permutation is given by listing the images of 1,2,3,4 . This group can be visualised by numbering from 1 to 4 the diagonals of a cube (or a octahedron) and following the positions of the diagonals after rotating the cube in all possible ways. But this will not be done here since it is not the purpose of this lesson, and it is not easy to visualise permutation groups for bigger  n  by some geometric action. Permutations are automatically ordered and can be recalled by the index [[ ]] . For viewing the lexicographic ordering of permutations, leave out the last semicolon.  Here is one permutation:

perms[[9]]

The composition law for permutations is given by indirect adressing of images

comp[perm2_,perm1_]:=
		Table[perm2[[perm1[[j]]]],{j,n}]

comp[perms[[7]],perms[[7]]]

control if subset is subgroup [includes sub, subGroupQ, gener1, generated, subg]

Selecting a nonempty set of elements in the permutation group

indices={1,8,17,24}

sub=Table[perms[[indices[[j]]]],{j,Length[indices]}]

one has to verify that these permutations form a subgroup by checking that the composition law is internal (unit element and inverses come for free in the case of finite groups):

subGroupQ[sub_]:= 
		Union[
			Flatten[
				Outer[
					comp,sub,sub,1
					]
				,1]
			]	==sub

The Flatten operation has its level specified since permutations are themselves lists (with four elements each). 
The Union operation filters out doubles.
The  above choice of sub is indeed a subgroup:

subGroupQ[sub]

If this returns False, one can look for the subgroup generated by the subset by Nesting Outer[comp[	]]   or finding its  FixedPoint :

\(gener1[sub_] := 
      Union[sub, 
				Flatten[Outer[comp, sub, sub, 1]
					, 
          1]
				]
\)
generated[sub_] := FixedPoint[gener1, sub]

and replacing sub by this  generated[sub]

subg =  If[subGroupQ[sub], sub, generated[sub]]

finding cosets and ordering along this partition  [includes coset, add, l, ordering]

It is now possible to find all left cosets of this subgroup (if it is a subgroup!)

coset[j_]:=Flatten[
			Outer[comp,{perms[[j]]},subg,1]
			,1]

which may be repeated to form a table of all cosets. The problem is that these are not disjoint. Some cosets contain elements from other cosets, but listed in a different order. 
Therefore, one has to consider only new cosets, which can be added one by one by

add[j_]:=
	Sort[
		Flatten[
			Table[
				Position[perms,coset[j][[k]]]
				,{k,Length[subg]}
				]
			]
		]

after the original subgroup. Try this out by performing:

add[7]

perms[[add[7]]]

Repeating this step, we obtain an ordering of the elements in the group which reflects the partition into cosets. We start with the original subgroup

l=Flatten[
		Table[Position[perms,subg[[k]]]
				,{k,Length[subg]}
		]]

and add new cosets

ordering=
	Do[
		l=If[   
			Union[Join[l,add[j]]]==Union[l],l,Join[l,add[j]]   
			]
		,{j,Factorial[n]}
	];l

This is somewhat tricky since checking equality of cosets requires sorting elements, and the elements in the final list should never be sorted by the lexicographic ordering built into Mathematica™.

Colorcoding cosets [includes: colors, mult, m, g, grid]

Now the coloring of elements is straightforward:

colors[m_]:=Hue[
	N[
	Floor[(m-1)/Length[subg]]/Length[perms] Length[subg]
	]
	]

if the order of elements is taken to be that of the list  l  :

mult[pos1_,pos2_]:=
	First[First[Position[perms,
		comp[ perms[[l[[pos1]]]],perms[[l[[pos2]]]] ] 
					]]]

m[pos1_,pos2_]:=
	First[
		First[
			Position[l,mult[pos1,pos2]]
		]
	]

Finally all elements are colored

g=Table[colors[m[pos1,pos2]],{pos1,Length[l]},{pos2,Length[l]}];

Show[Graphics[
	RasterArray[g]]
	,AspectRatio->Automatic
	,GridLines->None]

It may be surprising that we did not check the normality of the subgroup. If the subgroup is not normal this RasterArray is messy since multiplication of the cosets is not independent of their representing elements. The subgroup is normal if and only if the RasterArray shows a neat square block structure. In many cases it will be easy to recognise the structure of the quotient group by this pattern. The above 6 by 6 block table is the multiplication table of permutations on 3 elements.

Getting back to the nice case of the 24 permutations on n=4 objects, with the Klein four-group its subgroup, all elements are ordered and colored into 6 colors by the raster above. The Klein four-group is the single red (Hue zero) block in the lower left hand corner. The whole table is really a 24 by 24 square table. This fact can be made clear by adding some options while rendering the Graphics: first define a ticks grid and then add the following options in Show:

grid = Table[i, {i, 0, Length[perms]}];

\(Show[Graphics[RasterArray[g]]
		, 
      GridLines -> {grid, grid}
		, 
      AspectRatio -> Automatic]\)

Another striking result is obtained if one makes a coloring for the elements in "perms" according to their position in the list "  l  " , by replacing Length[subg]  by  1  in the coloring function: this means that we take a quotient by the one-element subgroup. It is then possible to toggle between this 24 by 24 coloring and the quotient blocks obtained above, and one sees even better how the elements get grouped into cosets: reddish elements in the red coset, yellowish elements in the yellow coset, and so on.

Original colorcoding elements [ ]

Programming

originalcolors[m_]:=Hue[(m-1)/Length[perms]]

The order of elements is again taken to be that of the list  l  :

mult[pos1_,pos2_]:=
	First[First[Position[perms,
		comp[ perms[[l[[pos1]]]],perms[[l[[pos2]]]] ] 
					]]]

m[pos1_,pos2_]:=
	First[
		First[
			Position[l,mult[pos1,pos2]]
		]
	]

Finally all elements are colored individually

g1=Table[
	originalcolors[m[pos1,pos2]]
	,{pos1,Length[l]},{pos2,Length[l]}
	];

Show[Graphics[
	RasterArray[g1]]
	,AspectRatio->Automatic
	,GridLines->{grid,grid}]

The best result is seen when we toggle between this last picture and the one with the quotient: it is clear which elements fall in which coset.

g=Table[colors[m[pos1,pos2]],{pos1,1},{pos2,Length[l]}];

Show[Graphics[
	RasterArray[g]]
	,AspectRatio->Automatic
	,GridLines->None]

A subgroup which is not normal [ ]

That we do not get a neat block structure for all choices of subgroups is shown by trying out the above inputs starting with

indices = {1, 2, 7, 8}

sub=Table[perms[[indices[[j]]]],{j,Length[indices]}]

subg =  If[subGroupQ[sub], sub, generated[sub]]

which defines a subgroup which is not normal. The block structure gets ruined in the sense that some square 4 x 4 blocks are replaced by four line stripes.

l=Flatten[
		Table[Position[perms,subg[[k]]]
				,{k,Length[subg]}
		]]

ordering=
	Do[
		l=If[   
			Union[Join[l,add[j]]]==Union[l],l,Join[l,add[j]]   
			]
		,{j,Factorial[n]}
	];l

g1=Table[
	originalcolors[m[pos1,pos2]]
	,{pos1,Length[l]},{pos2,Length[l]}
	];

Show[Graphics[
	RasterArray[g1]]
	,AspectRatio->Automatic
	,GridLines->{grid,grid}]

This reflects that multiplication is faithful on cosets only in one of the two possible orders, depending on which way cosets were defined: as left cosets or as right cosets. The theory of these homogeneous spaces is not standard in the algebra curriculum.

Grayscoding [includes: colors, gbw]

On a black and white screen or for the sake of printing purposes, the colors can be replaced by corresponding GrayLevel[ ] s) .

Clear[colors];
colors[m_]:=GrayLevel[
	N[
	Floor[(m-1)/Length[subg]]/Length[perms] Length[subg]
	]
	]

Multiplication is then done according to the following table. The subgroup is the darkest block in the lower left corner:

gbw=Table[
	colors[m[pos1,pos2]],{pos1,Length[l]},{pos2,Length[l]}
	];

Show[Graphics[
	RasterArray[gbw]]
	,AspectRatio->Automatic
	,GridLines->{grid,grid}]

It is also possible to make up a multiplication table with all group elements named (with colored text) in a similar way according to the same partition into cosets. This however will put restrictions on the size of the groups under consideration and a lot of formatting has to be done to avoid misaligned tables. Misaligned tables are likely to occur if different string lengths are involved in the naming of group elements.

Recognition of this quotient [includes: order]

The above reasoning can handle rather large groups. If the subgroup is sufficiently large the quotient has a small number of elements and brute application of all possible permutations on the elements of known groups will yield a group that is similar to the one obtained above. But this is certainly not the fastest way to proceed in all cases.

It may not be easy to see what the structure of a quotient is in the case of a large group with a small subgroup.  Pictures get bad if the size of the blocks gets down to a few pixels. The number of blocks will be large and the coloring will be somewhat hazy. Different techniques will be necessary to recognize the structure of the quotient. 

One technique is to consider the order of the elements. The order of an element in a group is defined by the number of elements in the subgroup generated by it:

order[element_] :=  Length[generated[{element} ]]

If the orders of elements do not agree with the order of the elements a known group it is impossible that this known  group is isomorphic to the quotient obtained above. If permutations are applied to the elements, it will be faster to apply only those permutations that mix the elements of same order.

One more possibility is to take a subgroup of the quotient and try to get some information by repeating the quotient operation, thus mimicking the theory of solvable groups. A cascade of quotients may give the Jordan decomposition. One has to be careful to start building cosets from the smallest subgroup on. An animation running over successive quotients is very instructive.

Dihedral and other groups

If we want to consider a quotient of a subgroup of all permutations it is sufficient to replace “perms” by permsNew which denotes a selection of it according to some Boolean condition, before repeating the above inputs.

permsNew =  Select[perms, condition ]

If we have a group defined in another way it is sufficient to replace in the above input lines “perms” by the list of elements in the group and “comp” by the law of composition under consideration. For instance we can take a dihedral group, i.e. the group of mappings of a regular n -gon generated by its rotations and a reflection, together with its composition law:

\(diGroup[n_] := 
      Flatten[Table[{j, refl}, {j, 0, n - 1}, {refl, 0, 1}], 1]
\)\(comp[{j_, refl1_}, {k_, refl2_}] := 
				
      If[refl1 == 0, {Mod[j + k, n], refl2}

        						, {Mod[j - k, n], Mod[refl1 + refl2, 2]}
				]\)

In case we have all movements of a regular octogon, we specify

\(n = 8; \ 
perms = diGroup[n]; \)

together with some subset

sub = {{4, 0}, {4, 1}}

and continue inputs to generate a (hopefully normal) subgroup and obtain the quotient.

It is even easier if we have a commutative group such  as the group of units (invertible elements) modulo some fixed positive number  n . This is easy to write down since Mathematica has very fast computations modulo  n built-in.
The only change in the above inputs will be that the Flatten operations are not restricted to first level since the elements of the group correspond to atoms and no double bracketing is necessary  for writing objects such as sub, coset[ ], etc.

Conclusions

The set of inputs developed in the examples above could be organised into a Package form if sufficient interest develops. Here we begin by grouping inputs as separate functions, such as

subgroup[group_, indices_]:=
or		subgroup[group_, subset_] :=

ordering[group_, subset_] :=

in an appropriate context format.

It can further be extended into a full electronic abstract algebra course, but I would prefer such a project to be realised by specialists in the field. They have at their disposal a lot of theorems which can be implemented. 
If such a project gets under way, the authors will find hints for programming in the above input lines.

Personally, I would refrain from starting such a program for several reasons. First, special-purpose packages for doing abstract algebra in groups already exist and it is not easy to surpass their quality without sustained input of manpower over a longer period of time. Secondly, creating too many special purpose packages may end up hiding the main advantage of Mathematica™ , i.e. its universal usability. A package may be very useful, but in many cases is optimization makes it rigid and less straightforward to understand and to modify than would be a step-by-step developed lesson such as the one above.  Last but not least: most of the fun resides in doing the exercise of getting mathematical ideas organised in the right way so that Mathematica™  can handle them. 

This is also what we finally hope to achieve with our students: that they understand the mathematics sufficiently well in order to develop the setup and make discoveries for themselves, rather than substituting variables for blank spaces in some ready-made function or package.

The unifying idea behind the implementations of different mathematical concepts is to offer to the mathematics learners an environment which is highly visual, but which does not hide the mathematical content of what is presented. Having at our disposal such techniques will
• enhance interest in mathematics as a topic
• improve retention, and speed up the learning curve
• facilitate the task of the teacher.
It seems essential to realise this in a short term given the increasingly difficult situation of mathematics in education in many countries.