1.29 About Defining New Parametrized Domains

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.

Previous Up Top Next
Index

GAP 3.4.4
April 1997