> < ^ Date: Fri, 22 Dec 1995 15:31:00 +0100 (MET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Base of abelian permutation group
Sebastian Egner wrote in his e-mail message of 1995/12/18

We are interested in the following problem:

Decompose a finite *abelian permutation group* into
a direct product of cyclic p-groups.

Is there a way of avoiding the computation of an
Fp-representation for the permutation group in order
to compute the generators of cyclic p-groups?

There is no special function in GAP 3.4 for that purpose. As a christmas
present I include a function that does what you want (but you have to
wait until christmas before you may use it ;-).

If <G> is an abelian permutation group, then
'IndependentGeneratorsAbelianPermGroup( <G> )' will return a list of
elements of prime-power order, such that <G> is the direct product of the
cyclic groups generated by them. (You can also apply it to a nonabelian
permutation group, but I'm not certain what it returns in this case ;-).
This function is very fast.

IndependentGeneratorsAbelianPPermGroup := function ( P, p )
    local   inds,       # independent generators, result
            pows,       # their powers
            base,       # the base of the vectorspace
            size,       # the size of the group generated by <inds>
            orbs,       # orbits
            trns,       # transversal
            gens,       # remaining generators
            gens2,      # remaining generators for next round
            exp,        # exponent of <P>
            g,          # one generator from <gens>
            h,          # its power
            b,          # basepoint
            c,          # other point in orbit
            i, j, k;    # loop variables
# initialize the list of independent generators
inds := [];
pows := [];
base := [];
size := 1;
orbs := [];
trns := [];

# gens are the generators for the remaining group
gens := P.generators;

# loop over the exponents
exp := Maximum( List( P.generators, g -> LogInt( Order( P, g ), p ) ) );
for i  in [exp,exp-1..1]  do
# loop over the remaining generators
gens2 := [];
for j  in [1..Length(gens)]  do
    g := gens[j];
    h := g ^ (p^(i-1));
# reduce <g> and <h>
while h <> h^0
  and IsBound(trns[SmallestMovedPointPerm(h)^h])
do
    g := g / pows[ trns[SmallestMovedPointPerm(h)^h] ];
    h := h / base[ trns[SmallestMovedPointPerm(h)^h] ];
od;

# if this is linear indepenent, add it to the generators
if h <> h^0  then
    Add( inds, g );
    Add( pows, g );
    Add( base, h );
    size := size * p^i;
    b := SmallestMovedPointPerm(h);
    if not IsBound( orbs[b] )  then
        orbs[b] := [ b ];
        trns[b] := [ () ];
    fi;
    for c  in ShallowCopy(orbs[b])  do
        for k  in [1..p-1]  do
            Add( orbs[b], c ^ (h^k) );
            trns[c^(h^k)] := Length(base);
        od;
    od;

># otherwise reduce and add to gens2
>else
> Add( gens2, g );

fi;
od;

# prepare for the next round
gens := gens2;
pows := OnTuples( pows, p );

od;

# return the indepenent generators
return inds;
end;

IndependentGeneratorsAbelianPermGroup := function ( G )
    local   inds,       # independent generators, result
            p,          # prime factor of group size
            gens,       # generators of <p>-Sylowsubgroup
            g,          # one generator
            o;          # its order
# loop over all primes
inds := [];
for p  in Union( List( G.generators, g -> Factors(Order(G,g)) ) )  do
# compute the generators for the <p>-Sylowsubgroup
gens := [];
for g  in G.generators  do
    o := Order(G,g);
    while o mod p = 0  do o := o / p; od;
    if g^o <> g^0  then Add( gens, g^o );  fi;
od;

# append the independent generators for the <p>-Sylowsubgroup
Append( inds,
IndependentGeneratorsAbelianPPermGroup(Group(gens,()),p) );

od;

# return the independent generators
return inds;
end;

Regards, Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]