> < ^ From:

< ^ Subject:

Dear gap forum:

As there has been discussion about the AbStab.g package, I need to respond.

I would like to describe some algorithms used in my package, AbStab.g, to

express an element of permutation group as a word in the generators.

We start by constructing a stabilizer chain in a manner similar to

MakeStabilizerChain. For each subgroup in the stabilizer chain, the generators

are stored both as permutations and as abstract words, derived from the

generators of the next larger stabilizer subgroup.

Let H represent a subgroup in the stabilizer chain, and K the next subgroup

in the chain. (K is the stabilizer in H of some point p.) Let the generators

of H be {g1, ..., gk}. The generators of K are found by first taking a left

Schreier transversal for the cosets of H in K with respect to these generators.

For each x in H, let \overbar{x} be the element of the Schreier transversal

which represents the same coset stabilizer. Then H may be generated by the

elements { u^-1 * gi * \overbar{u^-1 * gi} }, where u ranges over the elements

of the Schreier transversal, and gi ranges over the generators of H. (As p is

the point stabilized, u^-1 * gi * \overbar{u^-1 * gi} :p -> k -> q -> p, when

following the action of each element of the multiplication, i.e. p^u = k...)

(see D.L. Johnson, Presentations of groups (1990) )

This set of elements is often much larger than needed. We sort them

according to length. The function MinGenSet then adjoins these generators

one by one, in order of length, starting with the shortest. If the next

generator actually increases the size of the subgroup generated, it is retained,

otherwise it is discarded. We finish with a small list of short generators for

the stabilizer K. This is repeated to stabilize the next point, until the

trivial subgroup is obtained.

Once the abstract stabilizer chain has been found, it is fairly trivial to

take an element x of the group and find an expression for it as a word in the

generators of the group. Assume that G is a permutation group on { 1..n }.

For each point p let Gp represent the stabilizer of [1..p-1] in G. Let x_p

denote an element of Gp obtained inductively with p, starting with x_1=x. We

let x_{p+1} := x_p * s, where s is the element of the Schreier transversal of

the form (p^x_p, p, ....). Then x_{p+1} will fix the point p. This causes

x_n = (). (If x_n <> (), then x was not in the group to begin with.) This

results in an expression for x.

The function Shrink attempts to find a shorter representation for an

element of G. Let x be in G, and g*w represent x as a product of generators,

g a generator, and w a word. Then look for the shortest word in the following

lists: {w}, {FactorPermGroupElement(h*x) | h or h^-1 in G.generators},

{FactorPermGroupElement(x*h) | h or h^-1 in G.generators}.

Then replace g*w by g'*w' or w'*g', where w' is this shortest word, and

g' =g or h, as above. The is repeated with w', until w' is of length 1.

I now give an example of AbStab.g. Note the method used for choosing the

names of the abstract generators.

... gap> gen:=Set([f1,f2,f3,f4,r1,r2,r3,r4]); [ (25,26,27,28,29,30,31,32), (17,18,19,20,21,22,23,24), ( 9,10,11,12,13,14,15,16), ( 4,31)( 5,30)( 6,29)( 7,28)(12,23)(13,22)(14,21) (15,20), ( 3,30)( 4,29)( 5,28)( 6,27)(11,22)(12,21)(13,20)(14,19), ( 2,29)( 3,28)( 4,27)( 5,26)(10,21)(11,22)(12,23)(13,24), (1,2,3,4,5,6,7,8), ( 1,28)( 2,27)( 3,26)( 4,25)( 9,20)(10,19)(11,18)(12,17) ] gap> G := Group(gen,());; gap> G.abstractGenerators := Union(AbstractGenerators("f",4), > AbstractGenerators("r",4) ); [ f1, f2, f3, f4, r1, r2, r3, r4 ] gap> 2_cycle:=(1,2); (1,2) gap> cycle2a:=FactorPermGroupElement(G,2_cycle); f1^2*r1*r3* ... *r3^-1*r1^-1*f1^-2 << a word of length 409 >> gap> cycle2b:=Shrink(G,cycle2a); f1^-2*r1^-1*f1* ... *r1^-1*r3^-1*r1^-1 << a word of length 107 >> gap> cycle2d := Shrink(G,(1,2));; gap> cycle2d = cycle2c; true gap> map( G, cycle2a ); ( 1, 2) gap> map( G, cycle2b ); ( 1, 2) gap>

By no means does this package claim to give the shortest solution. It may

be observed that asking the points to be stabilized in a different order may

make a significant difference on the length of a solution given (both in length

of word and time.)

Finally I should note that there are a number of aspects of these routines

which ideally should be reworked to make them more efficient and robust.

There is a small change that should be made to one of the functions, due

to a change of the implementation of the function List. This suggestion was

made by Heiko Theissen:

--- AbStab.g.orig Fri Oct 28 21:34:03 1994 # GAP V3R4P2 (or earlier) +++ AbStab.g Wed Jan 31 10:41:19 1996 # GAP V3R4P3 @@ -210,8 +210,10 @@ lt:=LeftSchreier(arg); alt:= lt.ASchreier; lt := lt.Schreier; - rt:=List(lt,x->x^-1); - art:=List(alt,x->x^-1); + # rt:=List(lt,x->x^-1); + # art:=List(alt,x->x^-1); + rt:=[]; for x in lt do Add( rt, x^-1 ); od; + art:=[]; for x in alt do Add( art, x^-1 ); od; for g in G.generators do i:=Position(G.generators, g); ag := G.abstractGenerators[i];

This should fix any problems, as all other calls to the function "List" do

not implement a list with gaps in it.

Philip Osterlund

February 9, 1996

University of Minnesota

osterlu@math.umn.edu

> < [top]