GAP 
Main BranchesDownloads Installation Overview Data Libraries Packages Documentation Contacts FAQ GAP 3 

SitemapNavigation 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 nonabelian 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 nonabelian 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 nonabelian simple groups. The output given here has been produced by GAP 4.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  x^{2}, y^{p}, w_{1}(x,y) , ... , w_{k}(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  x^{2}, y^{p}, 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  x^{2}, y^{p}, 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 bisyllabic length to mean the number of bisyllables of form xy^{k} in such a relator. First note that since x^{2} is a relator we need only consider relators that are the products of bisyllables of form xy^{k}, for some integer k in the range [1 .. p1]. Since the relators x^{2}, y^{p}, w(x,y) must define a perfect group, the number of bisyllables 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 bisyllabic length, and 'tail' is also of even bisyllabic 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, y^{5} is a relator. Also remember that x^{2} is our first relator. gap> p := 5; 5Set the number of exponents of y to nexpts gap> nexpts := p1; 4The possible exponents of y (we assume p is odd) are [1, 2, ... , (p1)/2, (p1)/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 bisyllables 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 bisyllables and set up a list c of length 6 to contain the exponents of y. The eventual aim will be to run through all (p1)^{6} words with 6 bisyllables 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 bisyllables 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 = p1 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"); trueLikewise, in order to suppress output, we temporarily change the print level. gap> SetInfoLevel(InfoACE,0); gap> ReadPackage("ace","resexamples/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); 504We want to use PGRelFind to find a presentation with 3 relators, the first two being x^{2}, y^{3}. 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); 504By 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 x^{2}, y^{3} by the single relator x^{2}∗y^{3}. 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 x^{2}, y^{3} by the single relator x^{2}∗y^{3} we replace w(x,y) by w(x,y)∗x^{16} (which is equivalent since x^{2} 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); 504In 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 nonabelian simple groups of order < 10^{5} have balanced presentations. Bibliography


The GAP Group Last updated: Thu Jun 14 14:55:54 2012 