> < ^ From:

> < ^ Subject:

Dear GAP-Forum,

Kaustuv Das asked about computing Sylow-3 subgroups of Sp(6,5),

and Frank Luebeck responded by sending some functions converting

matrix groups to permutation groups more cleverly than the

current GAP default. I'd like to add some comments on the topic.

In Version 3.4.4 of GAP, released probably at the end of this month,

there is a new share package "matrix". Among other things, it contains

a function

PermGroupRepresentation(G, n)

which tries to find a permutation representation of the matrix group G

acting on at most $n$ points. Of course, at the problem at hand, it

would not do better than Frank's functions, but at other examples

it may find significantly smaller permutation domains.

Computing the Sylow subgroups of a classical matrix group can, and

should, be done WITHOUT converting to a permutation representation.

We know that the Sylow-3 subgroup of Sp(6,5) is isomorphic to

$C_3 \wr C_3$, and we know generators for it; the only question

is how to make it consistent with the generators given by GAP.

###########################

gap> g:=SymplecticGroup(6,5);

SP(6,5)

# we need to find the alternating form of $g$; I use the package "matrix",

# but the functions are already available in the incoming directory,

# in the package "classic"

gap> RequirePackage("matrix");

Loading the "Matrix Package", Version 1.0, by

Frank Celler, Derek Holt, Charles Leedham-Green, Alice Niemeyer

Eamon O'Brien, Cheryl Praeger, Anthony Pye, Sarah Rees

gap> RecognizeClassical(g); rec( recognizeSL := << SL recognition record >>, dimension := 6, field := GF(5), isPossibleImprimitive := false, isPossibleTensorProduct := false, isPossibleTensorPower := false, recognizeSP := << SP recognition record >>, dualForm := [ [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3 ], [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3, 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3, 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ] ], type := "symplectic", containsSL := false, containsSP := true, containsSO := false, containsSU := false, possibleAlmostSimple := [ ], possibleAlternatingGroups := [ ], possibleChevalleyGroups := [ ] ) # we see that the form is the natural, anti-diagonal one # we write a permutation matrix for the top of the wreath product gap> syl1:= [ [ 0*Z(5), Z(5)^0, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), Z(5)^0, 0*Z(5), 0*Z(5), 0*Z(5) ], [ Z(5)^0, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0 ], [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, 0*Z(5) ] ];;

# for the bottom of the wreath product, we can work with 2x2 matrices

# these are so small that we can let the default functions do the work

# note that in dimension 2, symplectic = special linear

gap> gr:=SpecialLinearMatGroup(2,5); SL(2,5) gap> Syl:=SylowSubgroup(gr,3); Subgroup( SL(2,5), [ [ [ Z(5), Z(5)^0 ], [ Z(5)^3, Z(5) ] ] ] )

# copy the generator of Syl into an identity matrix, acting on the

# 3rd and 4th basis vectors

gap> syl2:= [ [ Z(5)^0, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), Z(5)^0, 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), Z(5), Z(5)^0, 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), Z(5)^3, Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0 ] ];;

# We are done, because syl1, syl2 generate a Sylow-3 subgroup,

# but we should NOT call Subgroup(g,[syl1,syl2]),

# because it would convert to permutation groups to check that

# syl1, syl2 are in $g$. Containment in $g$ can be tested using the form.

gap> form:=g.recognizeClassicalCLG.recognizeSP.symplecticForm; [ [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3 ], [ 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3, 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^3, 0*Z(5), 0*Z(5) ], [ 0*Z(5), 0*Z(5), Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ 0*Z(5), Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ], [ Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5), 0*Z(5) ] ] gap> TransposedMat(syl1)*form*syl1 = form; true gap> TransposedMat(syl2)*form*syl2 = form; true ########################

The computation was done in the default 4MB GAP session.

The most time consuming part of the computation is to type in the matrices

syl1, syl2, but of course they could have been generated by GAP as well.

The moral of the story is that it is possible to compute with matrix groups

in GAP, but programming requires more thought than in the case of

permutation or ag-groups. I'd like to call your attention to an

announcement following this message, about a workshop on permutation

and matrix group methods. The first half of the workshop is a

tutorial about GAP and, among other topics, we intend to cover

problems like the above.

Finally, a remark about Sylow subgroup computations in permutation groups.

The current GAP function uses backtrack; however, Bill Kantor has a polynomial

time algorithm, and recently Prabhav Morje designed a nearly linear time

version for groups without composition factors of exceptional Lie type.

The latter should be practical, and an implementation will sooner or

later find its way into GAP. The idea is to start with a composition

series, compute the natural matrix representation of the composition

factors, find Sylow subgroups in the factors as we did above in Sp(6,5),

and then paste together to a Sylow subgroup of the entire group.

When this will be programmed, there will be special functions for

computing Sylow subgroups of classical matrix groups.

Akos Seress

> < [top]