Dear Forum members,
In a mail to 'gap-trouble' Bruce Coletti (bcolletti@mail.utexas.edu)
asked:
Does a GAP3.4.4 function find the representatives mentioned below
(P. Hall, 1935)?"If H is a subgroup of a finite group G with [G:H] = n, then there exist representives {t(i): i=1..n} in G so that { t(i)*H } is the set of all left cosets of H in G and { H*t(i) } is the set of all right cosets."Where would I look in the manual for such a function, if it exists?
The answer is that there is no such function in GAP yet.
However - as some of you will know from previous e-mail from me -
during the last year two students of mine, Patrick Biemans and Ludger
Hippe, working for her Staatsexamen (i.e. the examen that qualifies
them for teaching in a German highschool) have built up a collection
of exercises for the use of GAP with courses in Algebra and Group
Theory. This collection has still to be checked and the translatioin
to English polished, so it may still take some time until we can make
it publically available. However among the exercises is a sequence
that answers Bruce's request. Sine this may be interesting to further
people I append a TEX file with the respetive excercises and
solutions that Thomas Breuer helped me to prepare.
Please note that the solutions are by students, so no claim for
special efficiency is made. Also, before sending them off today, I
have not checked for correctness again. Please inform me if you
detect errors or can improve efficiency.
Let me finally make three remarks:
- The standard proof of the existence of such common systems of
representatives in principle is constructive (and used in the appended
program).
- I am not aware of applications of these systems of common right and
left representatives in further theory or computations. To my
knowledge their existence stands alone as a rather isolated and
unconnected result. If anyone is aware of connections, please let me
know.
- I know no answer to the problem raised at the end of the sequence of
exercises, namely to give some connection of the number of such
systems to other group invariants. Again I would appreciate comments.
Kind regards Joachim Neubueser
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[a4]{report}
\setlength{\oddsidemargin}{1cm}
\setlength{\topmargin}{0,5cm}
\setlength{\textwidth}{15cm}
\setlength{\headheight}{0,5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0cm}
\setlength{\headsep}{2cm}
\begin{document}
% \pagestyle{myheadings}
\large
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Exercise:}\\
Find a common left and right transversal of
$U=\langle (2,3,4),(2,3)\rangle \leq S_4$.
{\bf Solution:}
We consider all right transversals and find out whether they are also a left
transversal. It is sufficient to examine representatives of the non-trivial
cosets.
\begin{verbatim}
gap> g:=SymmetricGroup(4);;
gap> u:=Subgroup(g,[(2,3,4),(2,3)]);;
gap> r:=RightCosets(g,u);;
\end{verbatim}
The first coset in the list of all cosets is always the trivial one.
\begin{verbatim}
gap> Unbind(r[1]);;
gap> r:=Flat(r);;
gap> r:=List(r,Elements);;
gap> c:=Cartesian(r[1],r[2],r[3]);;
gap> e:=[];;
gap> for i in c do
> l:=List(i,x->LeftCoset(u,x));
> l:=Set(l);
> if Length(l)=3 then Add(e,i); fi; od;
gap> Length(e);
48
\end{verbatim}
In the {\tt for}-loop we checked if the representatives of the non-trivial
right cosets lie in three different left cosets.
One such common transversal is {\tt [(1,4),(1,3),(1,2]} and altogether
there are $48\cdot|U|=48\cdot 6=288$ common transversals.\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Exercise:}\\
This exercise deals with an algorithm to compute one common left and right
transversal. Look at theorem $4$ in [Zassenhaus, The Theory of Groups, 1958,
p.12].
Follow the proof of this theorem and write a function to compute one common
transversal.
{\bf Solution:}
We have to simplify the incidence matrix as explained in [Zassenhaus].
This can be done by operations on
the columns and rows. For the results of the function that we will
write it is necessary to name these rows and columns with right and left
transversals, respectively.
The function starts with creating the incidence $n+1\times n+1$- matrix where
$n$ is the index of the considered subgroup.
\begin{verbatim}
rep:=function(g,u)
local a,b,c,e,i,j,k,l,r,h,n;
l:=LeftCosets(g,u);
r:=RightCosets(g,u);
l:=List(l,Elements);
r:=List(r,Elements);
n:=Index(g,u);
h:=[];
for i in [1..n+1] do
Add(h,[]);
od;
for a in [2..n+1] do
for b in [2..n+1] do
if Length(Intersection(l[a-1],r[b-1]))=0 then h[a][b]:=0;
else h[a][b]:=1;
fi;
od;
od;
for a in [1..n] do
h[a+1][1]:=l[a][1];
od;
for b in [1..n] do
h[1][b+1]:=r[b][1];
od;
\end{verbatim}
Now the matrix is created. The entry {\tt h[1][1]} is set to one because of
programming reasons. Now we transform this matrix.
\begin{verbatim}
h[1][1]:=1;
repeat
for i in [1..n+1] do
if h[i][i]=0 then
k:=Copy(h[i]);
if ForAny([i+1..n+1],x->h[x][i]=1) then
e:=First([i+1..n+1],x->h[x][i]=1);
h[i]:=Copy(h[e]); h[e]:=k;
else
if ForAny([i+1..n+1],x->h[i][x]=1) then
e:=First([i+1..n+1],x->h[i][x]=1);
else e:=First([2..i],x->h[i][x]=1);
fi;
for j in [1..n+1] do
c:=Copy(h[j][i]);
h[j][i]:=h[j][e]; h[j][e]:=c; od;
fi;
fi;
od;
until ForAll([1..n+1],x->h[x][x]=1);
k:=[];
for i in [1..n] do
Add(k,Intersection(Elements(LeftCoset(u,h[i+1][1])),
Elements(RightCoset(u,h[1][i+1]))));
od;
return k;
end;
\end{verbatim}
In this function a lot of lists are used. It is more efficient to work
with Boolean lists. We modify our function from above using
Boolean lists.
\begin{verbatim}
rep:=function(g,u)
local a,b,c,e,i,j,k,l,r,h,n;
l:=LeftCosets(g,u);
r:=RightCosets(g,u);
l:=List(l,x->BlistList(Elements(g),Elements(x)));
r:=List(r,x->BlistList(Elements(g),Elements(x)));
h:=[];
n:=Index(g,u);
for i in [1..n+1] do
Add(h,[]);
od;
h[1][1]:=1;
for a in [2..n+1] do
for b in [2..n+1] do
k:=[];
for i in [1..Size(g)] do
if l[a-1][i] and r[b-1][i] then k[i]:=true;
fi;
od;
if Length(k)=0 then h[a][b]:=0;
else h[a][b]:=1;
fi;
od;
od;
for a in [1..n] do
h[a+1][1]:=a;
od;
for b in [1..n] do
h[1][b+1]:=b;
od;
repeat
for i in [1..n+1] do
if h[i][i]=0 then
k:=Copy(h[i]);
if ForAny([i+1..n+1],x->h[x][i]=1) then
e:=First([i+1..n+1],x->h[x][i]=1);
h[i]:=Copy(h[e]); h[e]:=k;
else
if ForAny([i+1..n+1],x->h[i][x]=1) then
e:=First([i+1..n+1],x->h[i][x]=1);
else e:=First([2..i],x->h[i][x]=1);
fi;
for j in [1..n+1] do
c:=Copy(h[j][i]);
h[j][i]:=h[j][e]; h[j][e]:=c; od;
fi;
fi;
od;
until ForAll([1..n+1],x->h[x][x]=1);
k:=[];
for i in [1..n] do
e:=[];
a:=l[h[i+1][1]]; b:=r[h[1][i+1]];
for j in [1..Size(g)] do
if a[j] and b[j] then Add(e,Elements(g)[j]);
fi;
od;
Add(k,e);
od;
return k;
end;
\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Exercise:}\\
Use the function from above with the groups $SL(2,13)$ and
$S_6\times D_{24}$ , both given as permutation groups below.
\begin{enumerate}
\item
\[ G = \langle (2,3,5,6,8,12)(7,10,9,14,11,13),
(1,2,4)(5,7,11)(6,9,10)(8,13,14) \rangle \]
is $SL(2,13)$ of order $1092$.
Find a common transversal for the subgroup
\[ U = \langle (1,5,2,14,3,13,8)(4,11,6,10,12,9,7) \rangle \]
of index $156$.
\item
\[ H = \langle (1,2,3,4,5,6),(1,2),(7,8,9,10,11,12,13,14,15,16,17,18),\]
\[ (8,18)(9,17)(10,16)(11,15)(12,14)\rangle \]
is $S_6\times D_{24}$ of order $17280$.
Find a common transversal for the subgroup
\[ U = \langle (1,3,2,4,6,5),(1,3)(2,5,6,4)\rangle \]
of index $240$.
\end{enumerate}
{\bf Solution:}
We use our function and {\tt Runtime} to get the times of computation.
\begin{verbatim}
gap> g:=Group((2,3,5,6,8,12)(7,10,9,14,11,13),
> (1,2,4)(5,7,11)(6,9,10)(8,13,14));;
gap> u:=Subgroup(g,[(1,5,2,14,3,13,8)(4,11,6,10,12,9,7)]);;
gap> Size(g);
1092
gap> Index(g,u);
156
gap> t:=Runtime();;
gap> r:=rep(g,u);;
gap> Runtime()-t;
1920
gap> Length(r);
156
gap> h:=Group((1,2,3,4,5,6),(1,2),(7,8,9,10,11,12,13,14,15,16,17,18),
> (8,18)(9,17)(10,16)(11,15)(12,14));;
gap> u:=Subgroup(h,[(1,3,2,4,6,5),(1,3)(2,5,6,4)]);;
gap> Size(h);
17280
gap> Index(h,u);
240
gap> t:=Runtime();;
gap> r:=rep(h,u);;
gap> Runtime()-t;
16880
gap> Length(r);
240
\end{verbatim}
Because of the large indices it would not make any sense to print the
results. In this exercise the times of computation are more important and we
can see that a larger index leads to a longer computation.\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Exercise:}\\
We wrote a function that computes {\it one} common transversal for a given
subgroup.
Use the theory of double cosets to write a function that computes the number
of {\em all} common transversals.
{\em Hints:}
\begin{itemize}
\item
Let $UgU$ be a double coset.
Find a common transversal for the left and right cosets contained in this
double coset.
\item
The command {\tt CanonicalCosetElement} returns a unique transversal
element of a right coset.
\item
Observe that each double coset is a fusion of left and right cosets.
\end{itemize}
{\bf Solution:}
Each double coset is a fusion of left cosets and of right cosets. The
part of a common transversal of all left and right cosets that is
contained in a certain double coset is a common transversal of those left
and right cosets contained in this double coset. Therefore, it is
sufficient to consider the double cosets step by step.
\begin{verbatim}
doubleReps:=function(g,u)
local dc, i ,l;
dc:=DoubleCosets(g,u,u);
dc:=List(dc,Representative);
l:=[];
for i in dc do
Add(l,Length(testInDoubleCoset(u,i)));
od;
return l;
end;
\end{verbatim}
In each double coset we search for a common transversal of the cosets
contained in it.
\begin{verbatim}
testInDoubleCoset:=function(u, rep)
local l,t;
t:=Orbit(u,CanonicalCosetElement(u,rep),
OnCanonicalCosetElements(Parent(u),u));
\end{verbatim}
The list {\tt t} is a right transversal in one double coset.
We multiply these representatives with all elements of the subgroup
and get all right transversals.
Then we find out which of them are also left transversals in the
double cosets.
To do this we check
whether the representatives lie in distinct left cosets.
\begin{verbatim}
l:=List(t,i->Elements(u)*i);
l:=List(l,i->List(i,j->LeftCoset(u,j)));
l:=Cartesian(l);
t:=Length(t);
l:=Filtered(l,i->Length(Set(i))=t);
return l;
end;
\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Exercise:}\\
Determine the number of common transversals and compare them for
subgroups of the same size. Check if the subgroups are normal and if
not, relate the number of common transversals to the size of the
normalizer of the subgroup for the following examples:
\begin{verbatim}
gap> g:=Group((1,2)(4,5),(2,3)(4,5),(1,2,3)(5,7));;
gap> Size(g);
36
gap> u1:=Subgroup(g,[(1,2,3)(4,5,7)]);;
gap> u2:=Subgroup(g,[(4,5,7),(2,3)(5,7)]);;
gap> u3:=Subgroup(g,[(5,7),(4,7)]);;
gap> u4:=Subgroup(g,[(1,2,3)]);;
{\bf Solution:}
gap> Size(u1);
3
gap> IsNormal(g,u1);
false
gap> Product(doubleReps(g,u1));
26244
gap> Size(u2);
6
gap> IsNormal(g,u2);
false
gap> Product(doubleReps(g,u2));
11664
gap> Size(u3);
6
gap> IsNormal(g,u3);
true
gap> Product(doubleReps(g,u3));
46656
gap> Size(u4);
3
gap> IsNormal(g,u4);
true
gap> Product(doubleReps(g,u4));
531441
\end{verbatim}
As you can see, the number of common transversals is small if the ``degree of
normality'' is low and that it is a large number if the subgroups are normal.
In the next exercise we try to find out if this is a general fact.\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\bf Exercise:}\\
In the following group collect subgroups of the same size and compute
the normalizers.
Determine the number of common transversals and compare them
with the size of the normalizers.
\begin{verbatim}
gap> g:=Group((1,3,4)(2,5), (1,3,7)(6,2));;
gap> Size(g);
72
gap> u1:=Subgroup(g,[(1,3)(4,7)]);;
gap> u2:=Subgroup(g,[(1,3)(4,7)(5,6)]);;
gap> u3:=Subgroup(g,[(3,4,7)]);;
gap> u4:=Subgroup(g,[(2,5,6)(3,4,7)]);;
gap> u5:=Subgroup(g,[(2,5,6),(1,3)(4,7),(1,4)(3,7)(5,6)]);;
gap> u6:=Subgroup(g,[(1,3)(4,7),(1,4)(3,7),(2,5,6)(3,4,7)]);;
gap> u7:=Subgroup(g,[(2,5,6)]);;
gap> u8:=Subgroup(g,[(3,4,7),(1,7,4)]);;
gap> u9:=Subgroup(g,[(2,5,6),(1,3)(4,7),(1,4)(3,7)]);;
{\bf Solution:}
gap> l:=[u1,u2,u3,u4,u5,u6,u7,u8,u9];;
gap> List(l,Size);
[ 2, 2, 3, 3, 12, 12, 3, 12, 12 ]
gap> v2:=Filtered(l,x->Size(x)=2);;
gap> v3:=Filtered(l,x->Size(x)=3);;
gap> v12:=Filtered(l,x->Size(x)=12);;
gap> v2:=List(v2,x->[x,Normalizer(g,x)]);;
gap> v3:=List(v3,x->[x,Normalizer(g,x)]);;
gap> v12:=List(v12,x->[x,Normalizer(g,x)]);;
\end{verbatim}
We determine the size of each normalizer.
\begin{verbatim}
gap> List(v2,x->List(x,Size));
[ [ 2, 24 ], [ 2, 8 ] ]
gap> List(v3,x->List(x,Size));
[ [ 3, 18 ], [ 3, 9 ], [ 3, 72 ] ]
gap> List(v12,x->List(x,Size));
[ [ 12, 24 ], [ 12, 36 ], [ 12, 72 ], [ 12, 72 ] ]
\end{verbatim}
The numbers of common transversals are interesting.
\begin{verbatim}
gap> List(v2,x->[List(x,Size),Product(doubleReps(g,x[1]))]);
[ [ [ 2, 24 ], 16777216 ], [ [ 2, 8 ], 1048576 ] ]
gap> List(v3,x->[List(x,Size),Product(doubleReps(g,x[1]))]);
[ [ [ 3, 18 ], 34012224 ], [ [ 3, 9 ], 7558272 ],
[ [ 3, 72 ], 282429536481 ] ]
gap> List(v12,x->[List(x,Size),Product(doubleReps(g,x[1]))]);
[ [ [ 12, 24 ], 746496 ], [ [ 12, 36 ], 663552 ],
[ [ 12, 72 ], 2985984], [ [ 12, 72 ], 2985984 ] ]
\end{verbatim}
Although the last exercise seemed to indicate a connection, the
results show that there seems to be no easy correspondence between
the size of the normalizer and the number of common transversals.
\end{document}