[GAP Forum] Construction of a group

[Max Horn]

Dear Stefanos,

you asked about constructing the (normalizer of) the 2-Sylow subgroup of the Suzuki groups without first constructing the Suzuki groups. Moreover, you expressed interest in counting their (classes of) subgroups. I will try to address both below.


On 14.02.2013, at 17:56, Stefanos Aivazidis wrote:

> Dear Forum,
> 
> I wish to construct a family of groups parametrised by a variable n, to be
> specified by the user. Let me describe the steps:
> 
> 0) Specify a value for n,
> 
> 1) construct the finite field F=F_q with q=2^(2n+1) elements,
> 
> 2) construct the automorphism f of F mapping each element x to x^(2^a),
> where a=n+1,

Let's record what we have so far:

n := 4;   # later you mention n=4, but other values work, too
q := 2^(2*n+1);
F := GF(q);
a := n+1;
f := x -> x^(2^a);


> 
> 3) define an operation * on FxF (as a set) via the rule:
> (x,y)*(x',y')=(x+x',y+y'+xf(x')), where the operations on the
> right-hand-side are those of the underlying field F,
> 
> Now P=(FxF,*) is a group, but I don't know if I can assure GAP this is the
> case. Perhaps I can ask her to test this somehow (GAP is a woman in my
> world).

The above group (the root group of a Moufang set in my world ;-) is a
p-group, hence polycyclic. And thus a natural way to construct it is as
a pc group (or, in my case, as a "pcp group", which is what the
"polycyclic" package for GAP provides). For large p-groups, permutation
representations (at least as computed by GAP) tend to have huge degree
and working with them quickly becomes problematic. But pc presentations
don't suffer from that problem (they have other computation drawbacks,
though).

Anyway, let's first collect some basic observations about this product:

 (a) (0,y)*(0,y') = (0,y+y')
     => 0xF is a subgroup isomorphic to (F,+)
 (b) (x,0)*(0,y') = (x,y') = (0,y')*(0,x)
     => 0xF is in fact central.
 (c) (x,0)*(x',0) = (x+x', xf(x')) 
     => the factor group FxF/0xF is abelian.
 (d) (x,0)^2 = (0,xf(x))
     => the relative order of (x,0) is 2
 (e) (x,0)^-1 = (x,xf(x))
 (f) (x,0)^(x',0) = (x',0)^-1*(x,0)*(x',0)
          = (x',x'f(x'))*(x+x', xf(x'))
          = (x, x'f(x+x')+x'f(x')+xf(x'))
          = (x, x'f(x)+xf(x'))

The last two relations tell us how conjugation between element of Fx0
looks like. Next, choose a basis b_1,...b_{2n+1} of F viewed as
GF(2)-vector space, and let x_1,...,x_{2n+1} be the corresponding basis
of Fx0, and let y_1,...,y_{2n+1} be the corresponding basis of 0xF.


We are now equipped with everything to construct a polycyclic presentation for
the group P. But wait, you want more:

> 
> 4) assuming that GAP now knows P is a group, define the semi-direct product
> S=P]C, where C is the multiplicative group of F and acts on P (via
> automorphisms) by the rule:c.(x,y)=(cx,cf(c)y), where f is as in 2) and
> concatenation on the right-hand-side is just multiplication in F.

We could try to construct P first and then use GAP's SemidirectProduct(),
but that would be very expensive, and in fact, unnecessary. After all, the
unit group F^* of F is cyclic (in particular, poly-cyclic ;-) and Z(q) is
a generator for it in GAP. Semidirect products of finite polycyclic groups
are again finite polycyclic.


So let's get busy:

LoadPackage("polycyclic");
b:=Basis(F);

# Helper taking a pair (x,y) in FxF and, using the basis b, mapping it to a
# generator-exponent vector.
F_to_genexp := function(x,y)
    local ge, k;
    ge:=[];
    x := Coefficients(b,x);
    y := Coefficients(b,y);
    for k in [1..2*n+1] do
        if not IsZero(x[k]) then Append(ge, [k+1, IntFFE(x[k])]); fi;
    od;
    for k in [1..2*n+1] do
        if not IsZero(y[k]) then Append(ge, [k+2*n+2, IntFFE(y[k])]); fi;
    od;
    return ge;
end;

# We need 1 + 2*dim(F) = 4*n+3 generators
coll:=FromTheLeftCollector(1 + 4*n+2);

# First comes the generator of the cyclic group F^*.
# It has order |F|-1, and acts as you described.
SetRelativeOrder(coll, 1, Size(F)-1);
for j in [1..2*n+1] do
    # action on x_j
    exp := F_to_genexp( Z(q)*b[j], Zero(F) );
    SetConjugate(coll, j+1, 1, exp);

    # action on y_j
    exp := F_to_genexp( Zero(F), Z(q)*f(Z(q))*b[j] );
    SetConjugate(coll, j+2*n+2, 1, exp);
od;

# Next, the "upper" part Fx0: x_i acts on x_j non-trivially,
# but centralizes the y_k (since the default is that a generator
# centralizes another, we don't need to tell GAP what y_k^x_i is)
for i in [1..2*n+1] do
    # relative order of x_i is 2, and (x,0)^2=(0,xf(x))
    SetRelativeOrder(coll, i+1, 2);
    exp := F_to_genexp(Zero(F), b[i] * f(b[i]));
    SetPower(coll, i+1, exp);
    # (x_j,0)^(x_i,0) = ...
    for j in [i+1..2*n+1] do
        exp := F_to_genexp(b[j], b[i] * f(b[j]) + b[j] * f(b[i]));
        SetConjugate(coll, j+1, i+1, exp);
    od;
od;

# Finally the "lower" and central part 0xF
for i in [2*n+2..4*n+2] do
    SetRelativeOrder(coll, i+1, 2);
od;

# Now we can construct the group S
S := PcpGroupByCollector(coll);
#S := PcpGroupByCollectorNC(coll); # For large n this is faster by skipping checks

# P is the subgroup of S on the generators 2 .. 4*n+3:
P := Subgroup(S,GeneratorsOfGroup(S){[2..4*n+3]});

# And C is generated by the first generator
C := Subgroup(S,[S.1]);


> 
> To give some motivation for the above construction, P thus constructed is
> the Sylow 2-subgroup of Sz(q), while S is its normaliser in Sz(q). Of
> course I can access both P and S via P:=SylowSubgroup(Sz(q),2) and
> S:=Normaliser(Sz(q),P) respectively, but I would prefer to work with P and
> S constructed as per the above "algorithm". The reason is that I mainly
> want to count subgroups and conjugacy classes of subgroups of P and S for
> (at least) n=4, since for smaller values of n, the order of C is a prime
> (thus C uninteresting), but GAP is unable to handle this in terms of memory.
> 
> I have serious doubts that constructing P and S as above will be more
> memory-efficient than the permutation representation already in
> Sz(IsPermGroup,q), but I can't decide this issue in advance.

The polycyclic presentation constructed above should be a lot more
efficient. However, constructing all (classes of) subgroup is still a
difficult business, as there simply are so many of them, at least for P.
After all, 0xY is a central elementary abelian subgroup of order q =
2^(2*n+1). For n=4 it has size 2^9=512; and each subspace corresponds to
a normal subgroup of P. But there are 8283458 subspaces, each yielding a
subgroup conjugacy class in P. The situation should be somewhat better
in S, at least in the sense that there are fewer conjugacy classes (e.g.
all 1-dimensional subspaces of 0xY are conjugate in S; in general, .

Similarly, the factor group P/0xY has 8283458 normal subgroups. Each
lifts to at least one conjugacy class in P. In other words, GAP will
have to compute in excess of 16 million subgroups, together with their
normalizers, and will have to store them all in memory. Hence I do not
expect ConjugacyClassesSubgroups(P) or ConjugacyClassesSubgroups(S) to
work "out of the box", no matter how you present P and S to GAP. But if
you just want to take specific subgroups and look at them to, say you
want to compute their normalizes, check if a few of them are conjugate
etc., the above can still be helpful.

If you truly want to count the (classes of) subgroups, and indeed only
need the count, then it might still be possible to achieve that by
taking the special structure of the group into account. The first thing
I would try: For each subgroup A of P/0xY, identify all subgroups U of P
for which U/0xY = A holds. The fact that the map F\to F : c \mapsto c
f(c) is bijective and non-linear, plus that we have (x,y)^2 = (0,xf(x)),
should help with that. And of course if you work inside S (where you
have fewer conjugacy classes overall, I guess), things should get a bit
better, too.



Hope that helps,
Max

> 
> If it is indeed non-trivial to decide beforehand, I would appreciate any
> help in how to write the code for the construction as explained above.
> 
> Many thanks,
> Stefanos
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>