|
GAP
|
Main BranchesDownloads Installation Overview Data Libraries Packages Documentation Contacts FAQ GAP 3 |
Find us on GitHubNavigation Tree |
Balanced presentations for covering groups of simple groupsA finite presentation is said to be balanced if the number of generators is equal to the number of relators. If a finite group G has a balanced presentation, the Schur multiplier of G is trivial. The converse is false in general but in the case of covering groups of finite non-abelian simple groups (which always have a trivial multiplier) the question remains open. Examples are given in [Kovacs95], however, of perfect groups with trivial multiplier which do not have balanced presentations. Question. Does the covering group of a finite non-abelian simple group necessarily have a balanced presentation? The purpose of this example is to demonstrate use of a program PGRelFind to find a balanced presentation for certain finite non-abelian simple groups. The output given here has been produced by GAP 4, the input is available in form of a plain GAP 4 input file. The following Lemma from [CHHR03] is helpful (a stronger version appears in [CHRR]).
Lemma. Applying it to a simple group with trivial multiplier the lemma can be used to find a balanced presentation for the simple group itself. The program PGRelFind uses the ACE coset enumerator. For difficult examples we expect the coset enumerations to be hard so for such examples it is necessary to assign ACE a large workspace. We give PGRelFind a presentation for a finite simple group G of the form ⟨ x, y | x2, yp, w1(x,y) , ... , wk(x,y) ⟩ Note that every finite simple group has such a presentation. We also give PGRelFind words sgens in the generators x, y which generate a subgroup H = <sgens> of small index n, say, in G. The program PGRelFind first finds a permutation representation of G of degree n with permutations X and Y corresponding to x and y respectively. It then looks for a word w(x,y) so that G is presented by ⟨ x, y | x2, yp, w(x,y) ⟩ The word w(x,y) must have the property that it reduces to the identity when we substitute the permutations X and Y. so that P = ⟨ x, y | x2, yp, w(x,y) ⟩ is a preimage of G. We look later at how such words w(x,y) are generated, but first we explain the tests PGRelFind applies to decide whether G is isomorphic to P.
if P is not perfect
then find next w(x,y)
else if Index(P,⟨sgens⟩) does not complete or Index(P,⟨sgens⟩) ≠ n
then find next w(x,y)
else if Index(P,⟨y⟩) does not complete or Index(P,⟨y⟩) ≠ Size(G)/p
then find next w(x,y)
else a suitable w(x,y) has been found.
Let us now say a little about how the words w(x,y) are generated. We will
use the term bi-syllabic length to mean the number of bi-syllables of form
xyk in such a relator. First note that since x2 is
a relator we need only consider relators that are the products of
bi-syllables of form xyk, for some integer k in the range
[1 .. p-1]. Since the relators x2, yp,
w(x,y) must define a perfect group, the number of bi-syllables in w(x,y)
must be odd (and coprime to p but we ignore this).
Furthermore, w(x,y) can be assumed to have the prefix xyxyxy-1
if p = 3 (use the fact that w(x,y) cannot be a proper power to
see this), or xy otherwise.
For efficiency, the word w(x,y) is broken into three parts,
w(x,y) = 'head' ∗ 'middle' ∗ 'tail'.
Here 'head' is the prefix described above, 'middle' always has even
bi-syllabic length, and 'tail' is also of even bi-syllabic length.
It is possible to conduct a systematic search starting at the shortest
possible words w(x,y) (where initially 'middle' is empty). It is also
possible to randomly select 'middle' and systematically generate 'tail's.
A list of the options which can be set in this searching process are
found in GAP by typing '?Using ACEReadResearchExample'
after loading the Package
ACE.
We now show how to generate possible words w(x,y) to test. Note that
the program shown here for demonstration differs slightly from the
actual code in PGRelFind.
We set up a free group F and generate words w(x,y) in F.
gap> F := FreeGroup("x","y");;
gap> x := F.1;; y := F.2;;
We will look at the case p = 5, that is, y5 is a
relator. Also remember that x2 is our first relator.
gap> p := 5; 5Set the number of exponents of y to nexpts gap> nexpts := p-1; 4The possible exponents of y (we assume p is odd) are [1, 2, ... , (p-1)/2, -(p-1)/2, ... , -2, -1] gap> expts := Concatenation([1 .. Int(p/2)], > [-Int(p/2) .. -1]); [ 1, 2, -2, -1 ]Set up a list sylls of possible bi-syllables gap> sylls := List(expts, i -> x*y^i); [ x*y, x*y^2, x*y^-2, x*y^-1 ]We will look at the case of 6 bi-syllables and set up a list c of length 6 to contain the exponents of y. The eventual aim will be to run through all (p-1)6 words with 6 bi-syllables gap> cLength := 6; 6The simplest exponent vector is: gap> c := ListWithIdenticalEntries(cLength, expts[1]); [ 1, 1, 1, 1, 1, 1 ]We define a function that will generate a word in x, y bi-syllables corresponding to any such exponent vector and apply it to c. gap> word := vec -> Product(vec, veci -> x*y^expts[veci], One(x)); function( vec ) ... end gap> word(c); x*y*x*y*x*y*x*y*x*y*x*yFurther we define a function which replaces a given exponent vector by its successor with respect to a certain lexicographical order. gap> getNext := function(vec) > local i; > i := 1; > while i <= cLength and vec[i] mod p = p-1 do > vec[i] := 1; > i := i + 1; > od; > if i <= cLength then > vec[i] := vec[i] + 1; > else > vec := fail; > fi; > end; function( vec ) ... endWe use this in a little program that allows us to construct and print a list of lexicographically ordered exponent vectors and their corresponding words starting from a given exponent vector. gap> printVecWord := function(vec, num) > local i; > Print(vec, " ", word(vec), "\n"); > i := 1;; > while i < num and vec <> fail do > i := i + 1; > getNext(vec); > Print(vec, " ", word(vec), "\n"); > od; > end; function( vec, num ) ... endWe apply this function, prescribing a start vector and asking for the first 20 words. gap> printVecWord( [1,1,1,1,1,1], 20); [ 1, 1, 1, 1, 1, 1 ] x*y*x*y*x*y*x*y*x*y*x*y [ 2, 1, 1, 1, 1, 1 ] x*y^2*x*y*x*y*x*y*x*y*x*y [ 3, 1, 1, 1, 1, 1 ] x*y^-2*x*y*x*y*x*y*x*y*x*y [ 4, 1, 1, 1, 1, 1 ] x*y^-1*x*y*x*y*x*y*x*y*x*y [ 1, 2, 1, 1, 1, 1 ] x*y*x*y^2*x*y*x*y*x*y*x*y [ 2, 2, 1, 1, 1, 1 ] x*y^2*x*y^2*x*y*x*y*x*y*x*y [ 3, 2, 1, 1, 1, 1 ] x*y^-2*x*y^2*x*y*x*y*x*y*x*y [ 4, 2, 1, 1, 1, 1 ] x*y^-1*x*y^2*x*y*x*y*x*y*x*y [ 1, 3, 1, 1, 1, 1 ] x*y*x*y^-2*x*y*x*y*x*y*x*y [ 2, 3, 1, 1, 1, 1 ] x*y^2*x*y^-2*x*y*x*y*x*y*x*y [ 3, 3, 1, 1, 1, 1 ] x*y^-2*x*y^-2*x*y*x*y*x*y*x*y [ 4, 3, 1, 1, 1, 1 ] x*y^-1*x*y^-2*x*y*x*y*x*y*x*y [ 1, 4, 1, 1, 1, 1 ] x*y*x*y^-1*x*y*x*y*x*y*x*y [ 2, 4, 1, 1, 1, 1 ] x*y^2*x*y^-1*x*y*x*y*x*y*x*y [ 3, 4, 1, 1, 1, 1 ] x*y^-2*x*y^-1*x*y*x*y*x*y*x*y [ 4, 4, 1, 1, 1, 1 ] x*y^-1*x*y^-1*x*y*x*y*x*y*x*y [ 1, 1, 2, 1, 1, 1 ] x*y*x*y*x*y^2*x*y*x*y*x*y [ 2, 1, 2, 1, 1, 1 ] x*y^2*x*y*x*y^2*x*y*x*y*x*y [ 3, 1, 2, 1, 1, 1 ] x*y^-2*x*y*x*y^2*x*y*x*y*x*y [ 4, 1, 2, 1, 1, 1 ] x*y^-1*x*y*x*y^2*x*y*x*y*x*yWe have now shown how to systematically generate possible words to test. As an example, we use PGRelFind to find a balanced presentation for the covering group of SL(2,8). Since SL(2,8) has trivial multiplier, this computation finds a balanced presentation for SL(2,8). First we read the package ACE including the function PGRelFind into GAP. When loading packages in general a banner is printed. This can be suppressed by starting GAP with option '-b'. We do this here to shorten the output.
gap> LoadPackage("ace");
true
Likewise, in order to suppress output, we temporarily change the print
level.
gap> SetInfoLevel(InfoACE,0);
gap> ReadPackage("ace","res-examples/pgrelfind.g");
true
gap> SetInfoLevel(InfoACE,1);
Here is a presentation for SL(2,8) with 4 relators.
gap> f:= FreeGroup("x","y");;
gap> x:= f.1;; y:= f.2;;
gap> rels:=[ x^2, y^3,
> y^(-1)*x*y^(-1)*x*y^(-1)*x*y^(-1)*x*y^(-1)*x*y^(-1)*x*y^(-1)*x,
> x*y^(-1)*x*y*x*y^(-1)*x*y*x*y^(-1)*x*y*x*y^(-1)*x*y*x*y*x*
> y^(-1)*x*y*x*y^(-1)*x*y*x*y^(-1)*x*y*x*y^(-1)*x*y*x*y ];;
gap> G:=f/rels;
<fp group on the generators [ x, y ]>
gap> Size(G);
504
We want to use PGRelFind to find a presentation with 3 relators, the
first two being x2, y3. First we find a subgroup
of small index to use to compute a small degree faithful permutation
representation of SL(2,8). We use the "low index" method to find suitable
subgroup generators.
gap> l:=LowIndexSubgroupsFpGroup( G, TrivialSubgroup( G),10); [ Group(<fp, no generators known>), Group(<fp, no generators known>) ] gap> sgens:=GeneratorsOfGroup(l[2]); [ x, y*x*y*x*y*x^-1*y^-1 ]We need to translate these generators back into words in the free generators x, y. Use UnderlyingElement to do this. gap> sgens:=List(sgens,UnderlyingElement); [ x, y*x*y*x*y*x^-1*y^-1 ]We need to input three things to PGRelFind. The first the list of free generators gap> fgens := [ x, y ]; [ x, y ]The second is the list of relators (as words in fgens), the first two relators of which have the correct form. Note that rels is already in the right form. Third we need generators (as words in fgens) for a subgroup of small index. In fact we have found generators for a subgroup of minimal index and sgens has already been set up in the correct form. gap> PGRelFind(fgens, rels, sgens ); GroupOrder=504 SubgroupIndex=9 #bisyllables in head = 3 head: x*y*x*y*x*y^-1 Max #bisyllables in tail = 10 (granularity = 10) #bisyllables in middle = 0 #bisyllables in middle = 12 Candidate relator: x*y*x*y*x*y^ -1*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y^ -1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1 #bisyllables = 25 (#bisyllables in tail = 10) #words tested: 1This is the first word w(x,y) examined which has the property that it reduces to the identity on substituting the permutations X and Y. ACEStats: index=9 cputime=0 ms maxcosets=509 totcosets=513 Large subgroup index OK ACEStats for cyclic subgroup: index=0 cputime=1640 ms maxcosets=645658 totcosets=666664This means that the first attempt of PGRelFind has been unsuccessful, so that the program automatically continues with another relator. Candidate relator: x*y*x*y*x*y^-1*x*y^ -1*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y^-1*x*y*x*y^-1*x*y^ -1*x*y*x*y*x*y^-1*x*y*x*y^-1*x*y #bisyllables = 25 (#bisyllables in tail = 10) #words tested: 2 ACEStats: index=9 cputime=0 ms maxcosets=555 totcosets=557 Large subgroup index OK ACEStats for cyclic subgroup: index=168 cputime=630 ms maxcosets=227917 totcosets=240311 Cyclic subgroup index OK Success! ... new relator: x*y*x*y*x*y^-1*x*y^-1*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y^ -1*x*y*x*y^-1*x*y^-1*x*y*x*y*x*y^-1*x*y*x*y^-1*x*ySo a first possible relator has been found, however the program will continue as above since there may be a shorter relator.
... continuing (there may be a shorter relator).
Candidate relator: x*y*x*y*x*y^-1*x*y^
-1*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y*x*y^-1*x*y*x*y*x*y^-1*x*y*x*y^
-1*x*y*x*y*x*y^-1*x*y^-1
[ ... 87 lines deleted ... ]
... continuing (there may be a shorter relator).
Candidate relator: x*y*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y^
-1*x*y^-1*x*y*x*y^-1*x*y
#bisyllables = 15 (#bisyllables in tail = 0) #words tested: 1460
ACEStats:
index=9 cputime=0 ms maxcosets=121 totcosets=133
Large subgroup index OK
ACEStats for cyclic subgroup:
index=168 cputime=0 ms maxcosets=170 totcosets=226
Cyclic subgroup index OK
Success! ... new relator:
x*y*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y^-1*x*y^
-1*x*y*x*y^-1*x*y
Relator found is shortest possible.
rec( gens := [ x, y ],
rels := [ x^2, y^3, x*y*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*x*y^-1*x*y^
-1*x*y*x*y^-1*x*y^-1*x*y*x*y^-1*x*y ],
sgens := [ x, y*x*y*x*y*x^-1*y^-1 ] )
This now gives a presentation in the correct form to apply the Lemma to
find a two generator two relator presentation for the covering group of
SL(2,8). Since SL(2,8) has trivial multiplier, this will be a two relator
presentation for SL(2,8). Let us check that we have indeed found a
presentation with three relators of the form that we were looking for.
gap> newrels := [ x^2, y^3, x*y*x*y*x*y^(-1)*x*y^(-1)*x*y^(-1)*x*y*x*
> y*x*y^(-1)*x*y^(-1)*x*y*x*y^(-1)*x*y^(-1)*x*y*x*y^(-1)*x*y ];
[ x^2, y^3, x*y*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y^-1*x*y^
-1*x*y*x*y^-1*x*y ]
gap> ge:=f/newrels;
<fp group on the generators [ x, y ]>
gap> Size(ge);
504
By the Lemma quoted at the beginning of this example we can deduce from
this presentation that SL(2,8) also has a balanced presentation. The
proof of the lemma is constructive and we finally demonstrate how in
this case we can actually find a balanced presentation.
We replace the two relators x2, y3 by the single
relator x2∗y3. However before doing so we
need to adjust w(x,y) so that the group remains perfect.
gap> ExponentSumWord(newrels[3],x); 15 gap> ExponentSumWord(newrels[3],y); -1The new first relator will have exponent sums 2 and 3, respectively, so we will have a perfect group if w(x,y) is replaced by an equivalent relator with exponent sums -1, -1. Hence, before replacing x2, y3 by the single relator x2∗y3 we replace w(x,y) by w(x,y)∗x-16 (which is equivalent since x2 is a relator).
gap> balancedrels := [x^2*y^3, newrels[3]*x^-16];
[ x^2*y^3, x*y*x*y*x*y^-1*x*y^-1*x*y^-1*x*y*x*y*x*y^-1*x*y^-1*x*y*x*y^-1*x*y^
-1*x*y*x*y^-1*x*y*x^-16 ]
gap> gb := f/balancedrels;
<fp group on the generators [ x, y ]>
gap> Size(gb);
504
In general it may be harder to apply the Lemma than it was in this special
case. Details are given in [CHHR03] (and for the
more general result in [CHRR]).
The program PGRelFind was used in [CHHR03]
to prove that L_3(5) has a balanced presentation (it has trivial multiplier).
The program was also used in [CHRR] to show that the
covering group of M_12 has a balanced presentation. These results complete
the proof that the covering groups of all non-abelian simple groups of
order < 105 have balanced presentations.
Bibliography
|