We will now show you how to write a GAP function, which computes the normal closure of an ag group. Such a function already exists in the library (see NormalClosure), but this should be an example on how to put functions together. You should at least be familiar with the basic More about Ag Groups for the definitions of finite polycyclic groups and its subgroups, see Generating Systems of Ag Groups for information about calculating induced or canonical generating system for subgroups.
Let U and S be subgroups of a group G. Then the normal closure N of U under S is the smallest subgroup in G, which contains U and is invariant under conjugation with elements of S. It is clear that N is invariant under conjugating with generators of S if and only if it is invariant under conjugating with all elements of S.
So in order to compute the normal closure of U, we can start with N:= U, conjugate N with a generator s of S and set N to the subgroup generated by N and N^s. Then we take the next generator of S. The whole process is repeated until N is stable. A GAP function doing this looks like
NormalClosure := function( S, U )local G, # the common supergroup of <S> and <U> N, # closure computed so far M, # next closure under generators of <S> s; # one generator of <S>
G := Parent( S, U ); M := U; repeat N := M; for s in Igs( S ) do M := MergedCgs( G, [ M ^ s, M ] ); od; until M = N; return N;
end;
Let S = G be the wreath product of the symmetric group on four points with itself using the natural permutation representation. Let U be a randomly chosen subgroup of order 12. The above functions needs, say, 100 time units to compute the normal closure of U under S, which is a subgroup N of index 2 in G.
gap> prms := [ (1,2), (1,2,3), (1,3)(2,4), (1,2)(3,4) ];
[ (1,2), (1,2,3), (1,3)(2,4), (1,2)(3,4) ]
gap> f := GroupHomomorphismByImages( s4, Group( prms, () ),
> s4.generators, prms );;
gap> G := WreathProduct( s4, s4, f );
Group( h1, h2, h3, h4, n1_1, n1_2, n1_3, n1_4, n2_1, n2_2, n2_3,
n2_4, n3_1, n3_2, n3_3, n3_4, n4_1, n4_2, n4_3, n4_4 )
gap> G.name := "G";;
gap> u := Random( G );
h1*h3*h4*n1_1*n1_3*n1_4*n2_1*n2_2*n2_3*n2_4*n3_2*n3_3*n4_1*n4_3*n4_4
gap> U := MergedCgs( G, [ u ] );
Subgroup( G,
[ h1*h3*n1_2^2*n1_3*n1_4*n2_1*n2_3*n3_1*n3_2*n3_4*n4_1*n4_3,
h4*n1_4*n2_1*n2_4*n3_1*n3_2*n4_2^2*n4_4,
n1_1*n2_1*n3_1*n3_2^2*n3_3*n3_4*n4_1*n4_4 ] )
gap> Size( U );
8
Now we can ask to speed up things. The first observation is that computing a canonical generating system is usablely a more time consuming task than computing a conjugate subgroup. So we form a canonical generating system after we have computed all conjugate subgroups, although now an additional repeat-until loop could be necessary.
NormalClosure := function( S, U )
local G, N, M, s, gens;
G := Parent( S, U );
M := U;
repeat
N := M;
gens := [ M ];
for s in Igs( S ) do
Add( gens, M ^ s );
od;
M := MergedCgs( G, gens );
until M = N;
return N;
end;
If we now test this new normal closure function with the above groups,
we see that the running time has decreased to 48 time units. The
canonical generating system algorithm is faster if it knows a large
subgroup of the group which should be generated but it does not gain
speed if it knows several of them. A canonical generating system for the
conjugated subgroup M^s is computed, although we only need generators
for this subgroup. So we can rewrite our algorithm.
NormalClosure := function( S, U )local G, # the common supergroup of <S> and <U> N, # closure computed so far M, # next closure under generators of <S> gensS, # generators of <S> gens; # generators of next step
G := Parent( S, U ); M := U; gens := Igs( S ); repeat N := M; gens := Concatenation( [ M ], Concatenation( List( S, s -> List( Igs( M ), m -> m ^ s ) ) ) ); M := MergedCgs( G, gens ); until M = N; return N;
end;
Now a canonical generating system is generated only once per
repeat-until loop. This reduces the running time to 33 time units. Let
m in M and s in S. Then < M, m^s > = < M,
m^{-1} m^s > . So we can substitute m^s by Comm( m, s ). If
m is invariant under s the new generator would be 1 instead of
m. With this modification the running times drops to 23 time units.
As next step we can try to compute induced generating systems instead of
canonical ones. In that case we cannot compare aggroups by =, but as
N is a subgroup M it is sufficient to compare the composition
lengths.
NormalClosure := function( S, U )local G, # the common supergroup of <S> and <U> N, # closure computed so far M, # next closure under generators of <S> gensS, # generators of <S> gens; # generators of next step
G := Parent( S, U ); M := U; gens := Igs( S ); repeat N := M; gens := Concatenation( List( S, s -> List( Igs( M ), m -> Comm( m, s ) ) ) ); M := MergedIgs( G, N, gens, false ); until Length( Igs( M ) ) = Length( Igs( M ) ); Normalize( N ); return N;
end;
But if we try the example above the running time has increased to 31.
As the normal closure has index 2 in G the agwords involved in a
canonical generating system are of length one or two. But agwords of
induced generating system may have much large length. So we have avoided
some collections but made the collection process itself much more
complicated. Nevertheless in examples with subgroups of greater index
the last function is slightly faster.
Previous Up Top
Index
GAP 3.4.4