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