Example: A Generic Groups Implementation Using Generic Programming - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Applications and Example Worksheets : Language and System : examples/GenericGroups

Example: A Generic Groups Implementation Using Generic Programming

Introduction

  

These examples illustrate how to develop a moderately complex software system by using features of the Maple module system. Generic programming is at the heart of the design. Only a fraction of the complete system from which the examples are taken is shown.

  

A system for computing with finite groups comprises the examples that follow. Recall that a group is a set of objects together with an associative binary operation, for which there is a unique two-sided identity element and every element has a unique inverse within the underlying set. Examples of groups include:

• 

Systems of numbers, using addition

• 

Closed sets of invertible matrices (all of the same size, with a common ground field), using multiplication (linear groups)

• 

Closed sets of permutations (bijective mappings on a set), using composition (permutation groups)

• 

Groups of points on elliptic curves

  

Only finite groups are discussed.

An Interface for Finite Groups

  

First, you must decide how to represent the generic group interface. This is determined by the proposed use of the group objects. Once again, the design takes a group to be a repository of data and computational services that you can query or invoke.

  

The Group signature used in the examples describes a computational model of abstract groups that supports the methods in the following table.

id

Returns the group identity

`.`

Performs the binary operation on the group

mul

n-ary version of `.`

inv

Performs the unary inversion operation

pow

Computes integral powers of group elements

eq

Tests whether two group elements are equal

member

Tests membership in the group and in sets

gens

Returns a generating set for the group

order

Returns the order of the group

elements

Returns an enumeration of the group's members

`type/GroupType` := '`module`(
    id, `.`, mul, inv,
    eq, member,
    gens,
    order, elements
)':

  

A corresponding constructor for groups is easily written using the Record constructor introduced earlier. For the examples in this section, no default methods are introduced.

Group := proc()
    Record( op( `type/GroupType` ) );
end proc:

  

This constructor does very little work on its own. It relies on more specialized constructors to establish useful values or defaults for the methods exported.

  

You can write generic algorithms using this interface immediately. A few simple examples are these routines for computing conjugates and commutators of group elements. The conjugate of a group member a by a group member b is b-1ab. This routine computes the conjugate of an element a by an element b in a group G.

Conjugate := proc( G, a, b )
    description "compute the conjugate of a "
                "group element by another";
    use `/` = G:-inv, `.` = G:-`.` in
       b^(-1) . a . b;
    end use;
end proc:

  

Since the group operations `.` and inv in a generic group remain unassigned, the following computation is done symbolically.

Conjugate( Group(), 'x', 'y' );

`.`invy,x,y

(1)
  

Similarly, you can compute the commutator a,b=a-1b-1ab, generically, as follows.

Commutator := proc( G, a, b )
    description "compute the commutator of "
                "two group elements";
    use `/` = G:-inv, mul = G:-mul in
        mul( inv( a ), inv( b ), a, b );
    end use;
end proc:

  

Again, this computation is done symbolically, so the group operations return unevaluated.

Commutator( Group(), 'x', 'y' );

mulinvx,invy,x,y

(2)
  

The ability to write generic algorithms over a given interface is important for the management of large software projects involving many developers. One developer can be assigned the task of implementing particular group constructors along with the attendant arithmetic, while another developer can begin coding generic routines. The two developers can work independently, provided each ensures that the work conforms to some agreed-upon interface and semantics.

Permutation Groups

  

Before attempting to develop any complicated algorithms, it is helpful to have a few constructors for specific kinds of groups. These can then be used to validate generic algorithms in specific instances. For this reason, we will develop a straightforward implementation of permutation groups.

  

Permutations are represented using Maple lists. For example, the list [2,1,3] represents the permutation that maps 1 -> 2, maps 2 -> 1, and leaves 3 fixed. (In cycle notation, this is written as the transposition (12).) The constructor takes a positive integer as its first argument, indicating the degree of the permutation group. The remaining arguments are expected to be permutations (represented as lists) of the stated degree. These are used to form the generating set of the group returned by the constructor.

PermutationGroup := proc( deg::posint )
    description "permutation group constructor";
    local G, gens;
    gens := { args[ 2 .. -1 ] };
    G := Group();
    G:-id := [ $ 1 .. deg ];
    G:-`.` := proc( a, b )
        local i;
        [ seq( b[ i ], i = a ) ];
    end proc;
    G:-mul := () -> foldl( G:-`.`, G:-id, args );
    G:-inv := proc( g )
        local i, a;
        a := array( 1 .. deg );
        for i from 1 to deg do
            a[ g[ i ] ] := i;
        end do;
        [ seq( a[ i ], i = 1 .. deg ) ];
    end proc;
    G:-member := proc( g, S, pos::name )
        if nargs = 1 then
            type( g, 'list( posint )' )
              and { op( g ) } = { $ 1 .. deg };
        else
            :-member( args );
        end if;
    end proc;
    G:-eq := ( a, b ) -> evalb( a = b );
    G:-gens := gens;
    eval( G, 1 );
end proc:

  

For example, to construct the group 12,123 in the symmetric group S4, use the PermutationGroup constructor as follows.

G := PermutationGroup( 4, { [2,1,3,4], [2,3,1,4] } );

GRecordid=1,2,3,4,`.`=proca,blocali;seqb[i],i=aend proc,mul=foldlG:−`.`,G:−id,args,inv=procglocali,a;a:=array1..4;forito4doa[g[i]]:=iend do;seqa[i],i=1..4end proc,eq=a,bevalba=b,member=procg,S,pos::nameifnargs=1thentypeg,'listposint'andopg=`$`1..4else:-memberargsend ifend proc,gens=2,1,3,4,2,3,1,4,order,elements

(3)
  

To compute with its elements, use the methods exported by the instantiated group G.

use G in
    inv( [ 2,1,3,4 ] ) . [2,3,1,4];
end use;

3,2,1,4

(4)
  

It is useful to provide more specialized permutation group constructors for special kinds of groups. Using the general constructor PermutationGroup, and overriding some of the exported methods, you can define several of these specialized constructors as follows.

  

The full symmetric group Sn on the n points { 1, 2, 3, ... , n } is produced by specifying a particular set of generators for a given degree (which must be specified as an argument to the constructor).

Symmetric := proc( n::posint )
    description "symmetric group constructor";
    if n < 2 then
        error "argument must be an integer larger than 1";
    elif n = 2 then
        PermutationGroup( 2, [ 2, 1 ] );
    else
        PermutationGroup( n, [ 2, 1, $ 3 .. n ], [ $ 2 .. n, 1 ] );
    end if;
end proc:

  

This uses the fact that Sn is the two-generator group

Sn=12,123n

  

for any integer 3n.

  

A second special case is the class of dihedral groups. Think of these as the groups of symmetries of regular plane polygons. The symmetry group of the regular n-gon is the dihedral group of degree n and order 2n; it is denoted by Dn.

  

Use the following utility for reversing the order of a list.

lreverse := proc( L::list )
    description "reverse a list";
    option inline;
    [ seq( L[ -i ], i = 1 .. nops( L ) ) ];
end proc:

Dihedral := proc( n::posint )
    description "dihedral group constructor";
    local a, b, D;
    if n = 2 or n = 3 then
        return Symmetric( n );
    end if;
    a := [ $ 2 .. n, 1 ];
    b := [ 1, op( lreverse( [ $ 2 .. n ] ) ) ];
    D := PermutationGroup( n, { a, b } );
    D:-order := () -> 2*n;
    eval( D, 1 );
end proc:

Exercises

1. 

Use the fact that the alternating group An of degree 3n is generated by the set123,234,345,,n2,n1,n of 3-cycles to write a constructor Alternating for this class of groups.

Dimino's Algorithm

  

Dimino's algorithm is used to compute a complete enumeration of the elements of a finite group, given a generating set for the group. Suppose that you are given a generating set g1,g2,,gn for a finite group G. The idea behind Dimino's algorithm is to enumerate, successively, the elements of each of the subgroups

Gk=g1,g2,,gk

  

of G, which form a chain

g1=G1G2GkGn=G

  

These elements can be enumerated by forming products of the generators g1, g2, ... , gn in all possible ways, until all the elements of G have been found. Dimino's algorithm does this in a careful way, avoiding unnecessary product computations.

  

Use the following utility routine to determine the entries assigned to a table. It can be used when you are certain no entry is a non-NULL expression sequence. Since it is sufficiently simple, it is defined with option inline;.

Entries := proc( T )
    description "return a set of simple table entries";
    option inline;
    map( op, { entries( T ) } );
end proc:

  

Here is the code for Dimino's algorithm.

Dimino := proc( G::GroupType )
    description "enumerate the elements of a finite group";
    local s, g, ord, elements, i, j, prev_ord, rep_pos,
          elt, addElt, gens;

    if nargs > 1 then
        gens := args[ 2 ];
    else
        gens := G:-gens;
    end if;

    if not type( gens, '{ set, list }' ) then
        error "no generating set specified";
    end if;

    if nops( gens ) = 0 then
        # trivial group
        return { G:-id };
    end if;

    addElt := proc( h )
        ord := 1 + ord;
        elements[ ord ] := h;
    end proc;

    elements := table();
    ord := 0;
    addElt( G:-id );

    # Handle the first cyclic subgroup
    s := gens[ 1 ];
    g := s;
    while not G:-eq( g, G:-id ) do
        addElt( g );
        g := G:-`.`( g, s );
    end do;
    userinfo( 1, 'Dimino', "finished first cycle; order is:", ord );

    for i from 2 to nops( gens ) do
        userinfo( 1, 'Dimino', "Adding generator number:", i );
        s := gens[ i ];
        if not G:-member( s, Entries( elements ) ) then
            prev_ord := ord;
            addElt( s );
            for j from 2 to prev_ord do
                addElt( G:-`.`( elements[ j ], s ) );
            end do;
            rep_pos := 1 + prev_ord;
            do
                for s in gens[ 1 .. i ] do
                    elt := G:-mul( elements[ rep_pos ], s );
                    if not G:-member( elt, Entries( elements ) ) then
                        addElt( elt );
                        for j from 2 to prev_ord do
                            addElt( G:-`.`( elements[ j ], elt ) );
                        end do;
                    end if;
                end do;
                rep_pos := rep_pos + prev_ord;
                if rep_pos > ord then
                    break;
                end if;
            end do;
        end if;
    end do;
    Entries( elements );
end proc:

  

The coding of this algorithm is generic. The exported members of the group object G are used to effect computations within the procedure. Even comparisons of equality use the export eq instead of the built-in comparison operator `=`. (The need for this is illustrated below.)

  

Using the Symmetric constructor previously defined, you can compute the elements of the symmetric group S4, using Dimino's algorithm, as follows.

G := Symmetric( 4 );

GRecordid=1&comma;2&comma;3&comma;4&comma;`.`=proca&comma;blocali&semi;seqb&lsqb;i&rsqb;&comma;i&equals;aend proc&comma;mul=foldlG:−`.`&comma;G:−id&comma;args&comma;inv=procglocali&comma;a&semi;a:=array1..4&semi;forito4doa&lsqb;g&lsqb;i&rsqb;&rsqb;:=iend do&semi;seqa&lsqb;i&rsqb;&comma;i&equals;1..4end proc&comma;eq=a&comma;bevalba=b&comma;member=procg&comma;S&comma;pos::nameifnargs&equals;1thentypeg&comma;&apos;listposint&apos;andopg&equals;`$`1..4else:-memberargsend ifend proc&comma;gens=2&comma;1&comma;3&comma;4&comma;2&comma;3&comma;4&comma;1&comma;order&comma;elements

(5)

Dimino( G );

1&comma;2&comma;3&comma;4&comma;1&comma;2&comma;4&comma;3&comma;1&comma;3&comma;2&comma;4&comma;1&comma;3&comma;4&comma;2&comma;1&comma;4&comma;2&comma;3&comma;1&comma;4&comma;3&comma;2&comma;2&comma;1&comma;3&comma;4&comma;2&comma;1&comma;4&comma;3&comma;2&comma;3&comma;1&comma;4&comma;2&comma;3&comma;4&comma;1&comma;2&comma;4&comma;1&comma;3&comma;2&comma;4&comma;3&comma;1&comma;3&comma;1&comma;2&comma;4&comma;3&comma;1&comma;4&comma;2&comma;3&comma;2&comma;1&comma;4&comma;3&comma;2&comma;4&comma;1&comma;3&comma;4&comma;1&comma;2&comma;3&comma;4&comma;2&comma;1&comma;4&comma;1&comma;2&comma;3&comma;4&comma;1&comma;3&comma;2&comma;4&comma;2&comma;1&comma;3&comma;4&comma;2&comma;3&comma;1&comma;4&comma;3&comma;1&comma;2&comma;4&comma;3&comma;2&comma;1

(6)
  

Anticipating later developments, the procedure Dimino has been coded to accept a second, optional argument that specifies an alternate set of generators to use. Thus, you could compute the same set using the set12,23,,(n1,n) of transpositions instead.

Dimino( G, { [2,1,3,4], [1,3,2,4], [1,2,4,3] } );

1&comma;2&comma;3&comma;4&comma;1&comma;2&comma;4&comma;3&comma;1&comma;3&comma;2&comma;4&comma;1&comma;3&comma;4&comma;2&comma;1&comma;4&comma;2&comma;3&comma;1&comma;4&comma;3&comma;2&comma;2&comma;1&comma;3&comma;4&comma;2&comma;1&comma;4&comma;3&comma;2&comma;3&comma;1&comma;4&comma;2&comma;3&comma;4&comma;1&comma;2&comma;4&comma;1&comma;3&comma;2&comma;4&comma;3&comma;1&comma;3&comma;1&comma;2&comma;4&comma;3&comma;1&comma;4&comma;2&comma;3&comma;2&comma;1&comma;4&comma;3&comma;2&comma;4&comma;1&comma;3&comma;4&comma;1&comma;2&comma;3&comma;4&comma;2&comma;1&comma;4&comma;1&comma;2&comma;3&comma;4&comma;1&comma;3&comma;2&comma;4&comma;2&comma;1&comma;3&comma;4&comma;2&comma;3&comma;1&comma;4&comma;3&comma;1&comma;2&comma;4&comma;3&comma;2&comma;1

(7)
  

You still need to pass the group object G for Dimino to access its operations.

  

Dimino's algorithm is a useful fallback algorithm, but many finite groups of interest can be enumerated more efficiently using specific knowledge of their structure. For small examples, the implementation presented here suffices, but a well-optimized implementation that takes advantage of fast arithmetic for group elements is required.

Representing Subgroups

  

A subset of a group that forms a group for larger groups (using the operations inherited from the group, by restriction) is called a subgroup. For example, the 3-member set { (123), (132), (1) } is a subgroup of the full symmetric group S3 of degree 3 (which has 6 members). There are many approaches for the representation of subgroups. One way is to represent a subgroup H of a known group G by specifying a generating set for H and copying the computational services from the representation of G to the representation of H. Thus, the Maple representations G and H of G and H would both be of type GroupType.

  

There is a different approach that is better suited to implicit representations of subgroups. This design can be extended to allow implicit representations of subgroups that you do not need to compute with directly. The idea is to represent a subgroup by a simpler structure that maintains a link to its parent group and an indication of how it is defined in terms of its parent group. Thus, a subgroup is represented by a module with an export parent that is assigned the group in which the subgroup is contained. A second export has a name depending upon the way in which the subgroup is defined. One way to define a subgroup in terms of its parent is to specify a generating set. Subgroups defined in this way are represented by a module having the export gens of type set. A second way to define a subgroup is by a property. For example, the center of a group is defined by the property that all its members commute with every element of the group (or, equivalently, that each member of the subgroup commutes with all the generators of the parent group). You can specify properties by using a procedure that tests for membership in the subgroup. Thus, subgroups can be described by either of the following interfaces.

parent

Parent group

test

Membership test (a procedure)

gens

Set of generators

  

Only one of the methods test and gens need be present. A Maple implementation of this interface is as follows.

`type/SubGroup` := '{
    `module`( parent::GroupType, gens::set ),
    `module`( parent::GroupType, test::procedure )
}':

  

The SubGroup constructor must dispatch on the type of its second argument to determine which kind of record to create to model the subgroup.

SubGroup := proc( G::{GroupType,SubGroup}, how::{set,procedure} )
    description "subgroup constructor";
    local S;
    if type( how, 'procedure' ) then
        S:= Record( 'parent', 'test' = eval( how, 1 ) );
    else
        S := Record( 'parent', 'gens' = how );
    end if;
    S:-parent := G;
    eval( S, 1 );
end proc:

  

For example, the center of the symmetric group S3 can be defined as follows.

S3 := Symmetric( 3 ):
Z := SubGroup( S3, proc( z )
    local g;
    use S3 in
        for g in gens do
            if not eq( mul( inv( g ), inv( z ), g ), z ) then
                return false;
            end if;
        end do;
    end use;
    true;
end proc );

ZRecordparent=S3&comma;test=proczlocalg&semi;forginS3:-gensdoifnotS3:-eqS3:-mulS3:-invg&comma;S3:-invz&comma;g&comma;zthenreturnfalseend ifend do&semi;trueend proc

(8)

Z:-test( [2,1,3] );

false

(9)

Z:-test( [2,3,1] );

false

(10)

Z:-test( [1,2,3] );

true

(11)
  

Similarly, you can write a constructor for the centralizer of an element in a group.

Centralizer := proc( G, g )
    SubGroup( G, proc( s )
                   use `.` = G:-`.`, `=` = G:-eq in
                       s . g = g . s;
                   end use; end proc );
end proc:

Generic Interfaces

  

Dimino's algorithm is relatively slow. For many classes of groups, there are better alternatives for enumerating group elements. Use Dimino's algorithm only as a last resort. The advantage of Dimino's algorithm is that it works for any finite group. To provide a clean and uniform interface to the enumeration functionality, you can develop a front-end procedure, which hides the details, to choose the best available algorithm.

GroupElements := proc( G )
    description "enumerate the elements of a finite group";
    if type( G, 'GroupType' ) then
        if type( G:-elements, 'set' ) then
            G:-elements;
        elif type( G:-elements, 'procedure' ) then
            G:-procedure();
        else
            G:-elements := Dimino( G );
        end if;
    else
        'procname'( args );
    end if;
end proc:

  

Several elements of the design allow you to take advantage of structural knowledge to improve efficiency. This routine first checks whether the export elements of its input group is of type set. If it is, then it is taken to be a stored enumeration of the group elements and is simply returned. Otherwise, if the export elements is a procedure, then it is taken to be a (perhaps specialized) routine for computing the requested enumeration. Finally, Dimino's algorithm is used as a last resort if no better alternative is provided. As a simple optimization, the result of Dimino's algorithm is stored as a new value for the elements export so that it need only be computed once.

  

Providing the GroupElements interface shields the user from needing to know what the available alternatives are and how to use them. An additional benefit of the design is that it allows you to change the algorithm selection criteria at any time (to correct software faults, or make functional or performance improvements). Code using this interface need not be modified, provided that the routine continues to honor its contract.

Enumerating Elements in Subgroups

  

Once the elements of the parent group are known, the members of the subgroup can be computed using a call to the built-in Maple command select:

  

select( C:-test, Dimino( G ) );

  

How best to enumerate the elements of a subgroup depends upon how it is defined and what is known about the parent group. The procedure SubGroupElements that follows takes a subgroup as argument and attempts to find the optimal way to compute the elements of the subgroup from among the available methods.

SubGroupElements := proc( S )
    description "enumerate the elements of "
                "a subgroup of a group";
    local P;
    P := S;
    while type( P, 'SubGroup' ) do
        P := P:-parent;
    end do;
    if type( P, 'GroupType' ) then
        if member( :-test, S ) then
            select( S:-test, GroupElements( P ) );
        else
            ASSERT( member( :-gens, S ) );
            Dimino( P, S:-gens );
        end if;
    else
        'procname'( args );
    end if;
end proc:

G := Symmetric( 4 );

GRecordid=1&comma;2&comma;3&comma;4&comma;`.`=proca&comma;blocali&semi;seqb&lsqb;i&rsqb;&comma;i&equals;aend proc&comma;mul=foldlG:−`.`&comma;G:−id&comma;args&comma;inv=procglocali&comma;a&semi;a:=array1..4&semi;forito4doa&lsqb;g&lsqb;i&rsqb;&rsqb;:=iend do&semi;seqa&lsqb;i&rsqb;&comma;i&equals;1..4end proc&comma;eq=a&comma;bevalba=b&comma;member=procg&comma;S&comma;pos::nameifnargs&equals;1thentypeg&comma;&apos;listposint&apos;andopg&equals;`$`1..4else:-memberargsend ifend proc&comma;gens=2&comma;1&comma;3&comma;4&comma;2&comma;3&comma;4&comma;1&comma;order&comma;elements

(12)

SubGroupElements( Centralizer( G, [ 1, 3, 2, 4 ] ) );

1&comma;2&comma;3&comma;4&comma;1&comma;3&comma;2&comma;4&comma;4&comma;2&comma;3&comma;1&comma;4&comma;3&comma;2&comma;1

(13)
  

With SubGroupElements implemented, it is a good idea to extend GroupElements to accept subgroups also, thus providing a common interface.

GroupElements := proc( G )
    description "enumerate the elements of a "
                "group or subgroup";
    if type( G, 'SubGroup' ) then
        SubGroupElements( G );
    elif type( G, 'GroupType' ) then
        if type( G:-elements, 'set' ) then
            G:-elements;
        elif type( G:-elements, 'procedure' ) then
            G:-elements();
        else
            G:-elements := Dimino( G );
        end if;
    else
        'procname'( args );
    end if;
end proc:

Computing the Order of a Group

  

As you can enumerate all of a group's elements, it is always possible to determine its order. (Note that this is rarely the best way to do this, however.) In many cases, it is possible to provide much better ways to compute the order of a group. For instance, the symmetric group of degree n has order equal to n!, so its order export could be redefined to compute this number instead.

  

A generic interface to computing group orders, in the same spirit as GroupElements can be written as follows.

GroupOrder := proc( G )
    description "compute the order of a finite group";
    if type( G, 'SubGroup' ) then
        nops( GroupElements( G ) );
    elif type( G, 'GroupType' ) then
        if type( G:-order, 'posint' ) then
            G:-order;
        elif type( G:-elements, 'set' ) then
            G:-order := nops( G:-elements );
        elif type( G:-order, 'procedure' ) then
            G:-order();
        else
            nops( GroupElements( G ) );
        end if;
    else
        'procname'( args );
    end if;
end proc:

  

As with GroupElements, this routine checks the possible shortcuts that might be available for a group. It begins with those that are likely to involve the least computation and progresses through more costly alternatives. Only as a last resort does the procedure call GroupElements to compute a full enumeration of the group elements only to return their number.

G := Symmetric( 4 );

GRecordid=1&comma;2&comma;3&comma;4&comma;`.`=proca&comma;blocali&semi;seqb&lsqb;i&rsqb;&comma;i&equals;aend proc&comma;mul=foldlG:−`.`&comma;G:−id&comma;args&comma;inv=procglocali&comma;a&semi;a:=array1..4&semi;forito4doa&lsqb;g&lsqb;i&rsqb;&rsqb;:=iend do&semi;seqa&lsqb;i&rsqb;&comma;i&equals;1..4end proc&comma;eq=a&comma;bevalba=b&comma;member=procg&comma;S&comma;pos::nameifnargs&equals;1thentypeg&comma;&apos;listposint&apos;andopg&equals;`$`1..4else:-memberargsend ifend proc&comma;gens=2&comma;1&comma;3&comma;4&comma;2&comma;3&comma;4&comma;1&comma;order&comma;elements

(14)

C := Centralizer( G, [ 1, 3, 2, 4 ] );

CRecordparent=G&comma;test=procsG:-eqG:-