> < ^ From:

^ Subject:

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}

> < [top]