GAP Manual: 4.4. An Example of a Computation in a Domain

This section contains an extended example to show you how a computation in a domain may use default and special functions to achieve its goal. Suppose you defined G, x, and y as follows. 

    gap> G := SymmetricGroup( 8 );;
    gap> x := [ (2,7,4)(3,5), (1,2,6)(4,8) ];;
    gap> y := [ (2,5,7)(4,6), (1,5)(3,8,7) ];;

Now you ask for an element of G that conjugates x to y, i.e., a permutation on 8 points that takes (2,7,4)(3,5) to (2,5,7)(4,6) and (1,2,6)(4,8) to (1,5)(3,8,7). This is done as follows (see RepresentativeOperation and Other Operations). 

    gap> RepresentativeOperation( G, x, y, OnTuples );
    (1,8)(2,7)(3,4,5,6)

Let us look at what happens step by step. First RepresentativeOperation is called. After checking the arguments it calls the function G.operations.RepresentativeOperation, which is the function SymmetricGroupOps.RepresentativeOperation, passing the arguments G, x, y, and OnTuples.

SymmetricGroupOps.RepresentativeOperation handles a lot of cases specially, but the operation on tuples of permutations is not among them. Therefore it delegates this problem to the function that it overlays, which is PermGroupOps.RepresentativeOperation.

PermGroupOps.RepresentativeOperation also does not handle this special case, and delegates the problem to the function that it overlays, which is the default function called GroupOps.RepresentativeOperation.

GroupOps.RepresentativeOperation views this problem as a general tuples problem, i.e., it does not care whether the points in the tuples are integers or permutations, and decides to solve it one step at a time. So first it looks for an element taking (2,7,4)(3,5) to (2,5,7)(4,6) by calling RepresentativeOperation( G, (2,7,4)(3,5), (2,5,7)(4,6) ).

RepresentativeOperation calls G.operations.RepresentativeOperation next, which is the function SymmetricGroupOps.RepresentativeOperation, passing the arguments G, (2,7,4)(3,5), and (2,5,7)(4,6).

SymmetricGroupOps.RepresentativeOperation can handle this case. It knows that G contains every permutation on 8 points, so it contains (3,4,7,5,6), which obviously does what we want, namely it takes x[1] to y[1]. We will call this element t.

Now GroupOps.RepresentativeOperation (see above) looks for an s in the stabilizer of x[1] taking x[2] to y[2]^(t^-1), since then for r=s*t we have x[1]^r = (x[1]^s)^t = x[1]^t = y[1] and also x[2]^r = (x[2]^s)^t = (y[2]^(t^-1))^t = y[2]. So the next step is to compute the stabilizer of x[1] in G. To do this it calls Stabilizer( G, (2,7,4)(3,5) ).

Stabilizer calls G.operations.Stabilizer, which is SymmetricGroupOps.Stabilizer, passing the arguments G and (2,7,4)(3,5). SymmetricGroupOps.Stabilizer detects that the second argument is a permutation, i.e., an element of the group, and calls Centralizer( G, (2,7,4)(3,5) ). Centralizer calls the function G.operations.Centralizer, which is SymmetricGroupOps.Centralizer, again passing the arguments G, (2,7,4)(3,5).

SymmetricGroupOps.Centralizer again knows how centralizers in symmetric groups look, and after looking at the permutation (2,7,4)(3,5) sharply for a short while returns the centralizer as Subgroup( G, [ (1,6), (1,6,8), (2,7,4), (3,5) ] ), which we will call S. Note that S is of course not a symmetric group, therefore SymmetricGroupOps.Subgroup gives it PermGroupOps as operations record and not SymmetricGroupOps.

As explained above GroupOps.RepresentativeOperation needs an element of S taking x[2] ((1,2,6)(4,8)) to y[2]^(t^-1) ((1,7)(4,6,8)). So RepresentativeOperation( S, (1,2,6)(4,8), (1,7)(4,6,8) ) is called. RepresentativeOperation in turn calls the function S.operations.RepresentativeOperation, which is, since S is a permutation group, the function PermGroupOps.RepresentativeOperation, passing the arguments S, (1,2,6)(4,8), and (1,7)(4,6,8).

PermGroupOps.RepresentativeOperation detects that the points are permutations and and performs a backtrack search through S. It finds and returns (1,8)(2,4,7)(3,5), which we call s.

Then GroupOps.RepresentativeOperation returns r = s*t = (1,8)(2,7)(3,6)(4,5), and we are done.

In this example you have seen how functions use the structure of their domain to solve a problem most efficiently, for example SymmetricGroupOps.RepresentativeOperation but also the backtrack search in PermGroupOps.RepresentativeOperation, how they use other functions, for example SymmetricGroupOps.Stabilizer called Centralizer, and how they delegate cases which they can not handle more efficiently back to the function they overlaid, for example SymmetricGroupOps.RepresentativeOperation delegated to PermGroupOps.RepresentativeOperation, which in turn delegated to to the function GroupOps.RepresentativeOperation.

[next] [prev] [up]