In this section we will show you an example that is slightly more complex than the example in the previous section. Namely we will demonstrate how one can implement parametrized domains. As an example we will implement symmetric permutation groups. This works similar to the implementation of a single domain. Therefore we can be very brief. Of course you should have read the previous section.
Note that everything defined here is already in the file
GRPNAME/"permgrp.grp", so there is no need for you to type it in.
You may however like to make a copy of this file and modify it.
In the example of the previous section we simply had a variable
(GaussianIntegers), whose value was the domain. This can not work in
this example, because there is not one symmetric permutation group.
The solution is obvious. We simply define a function that takes the
degree and returns the symmetric permutation group of this degree (as a
domain).
gap> SymmetricPermGroup := function ( n )
> local G; # symmetric group on <n> points, result
>
> # make the group generated by (1,n), (2,n), .., (n-1,n)
> G := Group( List( [1..n-1], i -> (i,n) ), () );
> G.degree := n;
>
> # give it the correct operations record
> G.operations := SymmetricPermGroupOps;
>
> # return the symmetric group
> return G;
> end;;
The key is of course to give the domains returned by SymmetricPermGroup
a new operations record. This operations record will hold functions that
are written especially for symmetric permutation groups. Note that all
symmetric groups created by SymmetricPermGroup share one operations
record.
Just as we inherited in the example in the previous section from the
operations record RingOps, here we can inherit from the operations
record PermGroupOps (after all, each symmetric permutation group is
also a permutation group).
gap> SymmetricPermGroupOps := Copy( PermGroupOps );
We will now overlay some of the functions in this operations record with new functions that make use of the fact that the domain is a full symmetric permutation group. The first function that does this is the membership test function.
gap> SymmetricPermGroupOps.\in := function ( g, G )
> return IsPerm( g )
> and ( g = ()
> or LargestMovedPointPerm( g ) <= G.degree);
> end;;
The most important knowledge for a permutation group is a base and a strong generating set with respect to that base. It is not important that you understand at this point what this is mathematically. The important point here is that such a strong generating set with respect to an appropriate base is used by many generic permutation group functions, most of which we inherit for symmetric permutation groups. Therefore it is important that we are able to compute a strong generating set as fast as possible. Luckily it is possible to simply write down such a strong generating set for a full symmetric group. This is done by the following function.
gap> SymmetricPermGroupOps.MakeStabChain := function ( G, base )
> local sgs, # strong generating system of G wrt. base
> last; # last point of the base
>
> # remove all unwanted points from the base
> base := Filtered( base, i -> i <= G.degree );
>
> # extend the base with those points not already in the base
> base := Concatenation( base, Difference( [1..G.degree], base ) );
>
> # take the last point
> last := base[ Length(base) ];
>
> # make the strong generating set
> sgs := List( [1..Length(base)-1], i -> ( base[i], last ) );
>
> # make the stabilizer chain
> MakeStabChainStrongGenerators( G, base, sgs );
> end;;
One of the things that are very easy for symmetric groups is the computation of centralizers of elements. The next function does this. Again it is not important that you understand this mathematically. The centralizer of an element g in the symmetric group is generated by the cycles c of g and an element x for each pair of cycles of g of the same length that maps one cycle to the other.
gap> SymmetricPermGroupOps.Centralizer := function ( G, g )
> local C, # centralizer of g in G, result
> sgs, # strong generating set of C
> gen, # one generator in sgs
> cycles, # cycles of g
> cycle, # one cycle from cycles
> lasts, # lasts[l] is the last cycle of length l
> last, # one cycle from lasts
> i; # loop variable
>
> # handle special case
> if IsPerm( g ) and g in G then
>
> # start with the empty strong generating system
> sgs := [];
>
> # compute the cycles and find for each length the last one
> cycles := Cycles( g, [1..G.degree] );
> lasts := [];
> for cycle in cycles do
> lasts[Length(cycle)] := cycle;
> od;
>
> # loop over the cycles
> for cycle in cycles do
>
> # add that cycle itself to the strong generators
> if Length( cycle ) <> 1 then
> gen := [1..G.degree];
> for i in [1..Length(cycle)-1] do
> gen[cycle[i]] := cycle[i+1];
> od;
> gen[cycle[Length(cycle)]] := cycle[1];
> gen := PermList( gen );
> Add( sgs, gen );
> fi;
>
> # and it can be mapped to the last cycle of this length
> if cycle <> lasts[ Length(cycle) ] then
> last := lasts[ Length(cycle) ];
> gen := [1..G.degree];
> for i in [1..Length(cycle)] do
> gen[cycle[i]] := last[i];
> gen[last[i]] := cycle[i];
> od;
> gen := PermList( gen );
> Add( sgs, gen );
> fi;
>
> od;
>
> # make the centralizer
> C := Subgroup( G, sgs );
>
> # make the stabilizer chain
> MakeStabChainStrongGenerators( C, [1..G.degree], sgs );
>
> # delegate general case
> else
> C := PermGroupOps.Centralizer( G, g );
> fi;
>
> # return the centralizer
> return C;
> end;;
Note that the definition C := Subgroup( G, sgs ); defines a subgroup
of a symmetric permutation group. But this subgroup is usually not a
full symmetric permutation group itself. Thus C must not have the
operations record SymmetricPermGroupOps, instead it should have the
operations record PermGroupOps. And indeed C will have this
operations record. This is because Subgroup calls
G.operations.Subgroup, and we inherited this function from
PermGroupOps.
Note also that we only handle one special case in the function above.
Namely the computation of a centralizer of a single element. This
function can also be called to compute the centralizer of a whole
subgroup. In this case SymmetricPermGroupOps.Centralizer simply
delegates the problem by calling PermGroupOps.Centralizer.
The next function computes the conjugacy classes of elements in a symmetric group. This is very easy, because two elements are conjugated in a symmetric group when they have the same cycle structure. Thus we can simply compute the partitions of the degree, and for each degree we get one conjugacy class.
gap> SymmetricPermGroupOps.ConjugacyClasses := function ( G )
> local classes, # conjugacy classes of G, result
> prt, # partition of G
> sum, # partial sum of the entries in prt
> rep, # representative of a conjugacy class of G
> i; # loop variable
>
> # loop over the partitions
> classes := [];
> for prt in Partitions( G.degree ) do
>
> # compute the representative of the conjugacy class
> rep := [2..G.degree];
> sum := 1;
> for i in prt do
> rep[sum+i-1] := sum;
> sum := sum + i;
> od;
> rep := PermList( rep );
>
> # add the new class to the list of classes
> Add( classes, ConjugacyClass( G, rep ) );
>
> od;
>
> # return the classes
> return classes;
> end;;
This concludes this example. You have seen that the implementation of a parametrized domain is not much more difficult than the implementation of a single domain. You have also seen how functions that overlay generic functions may delegate problems back to the generic function. The library file for symmetric permutation groups contain some more functions for symmetric permutation groups.
GAP 3.4.4