This file contains the mails sent to the GAP forum in July-September 1994. Name Email address Mails Lines Martin Schoenert Martin.Schoenert@Math.RWTH-Aachen.DE 22 995 Frank Celler Frank.Celler@Math.RWTH-Aachen.DE 19 1053 Joachim Neubueser Joachim.Neubueser@Math.RWTH-Aachen.DE 10 387 Alexander Hulpke Alexander.Hulpke@Math.RWTH-Aachen.DE 9 479 Steve Linton sl25@cus.cam.ac.uk 9 259 Leonard Soicher leonard@qmw.ac.uk 9 155 Roger A Fenn r.a.fenn@sussex.ac.uk 5 153 Thomas Breuer Thomas.Breuer@Math.RWTH-Aachen.DE 5 134 Lewis McCarthy lmccarth@klingon.cs.umass.edu 5 96 Steve Fisk fisk@polar.bowdoin.edu 4 752 Tim Boykett tim@bruckner.stoch.uni-linz.ac.at 3 270 Jacob Hirbawi jcbhrb@cerf.net 3 212 Harald Boegeholz hwblist@machnix.mathematik.uni-stuttgart.de 3 167 Eamonn O'Brien eamonn.obrien@maths.anu.edu.au 3 131 Derek Holt dfh@maths.warwick.ac.uk 3 111 Andrew Mathas a.mathas@ic.ac.uk 3 101 Dima Pasechnik dima@maths.uwa.edu.au 3 64 Chris Charnes charnes@osiris.cs.uow.edu.au 3 19 Franz Gaehler gaehler@msc.cornell.edu 2 255 Volkmar Felsch Volkmar.Felsch@Math.RWTH-Aachen.DE 2 194 Werner Nickel Werner.Nickel@Math.RWTH-Aachen.DE 2 112 Chris Wensley mas023@bangor.ac.uk 2 58 Charles.Wright wright@bright.uoregon.edu 2 41 David Sibley sibley@math.psu.edu 2 33 Allan Adler ara@altdorf.ai.mit.edu 2 25 Peter F. Blanchard pfb3h@weyl.math.virginia.edu 1 89 Ottokar Kulendik kulendor@machnix.mathematik.uni-stuttgart.d 1 40 Daniel Ruberman ruberman@max.math.brandeis.edu 1 22 Tim Hsu timhsu@math.princeton.edu 1 21 Bruce Kaskel kaskel@math.berkeley.edu 1 19 Mark Edwin Hall fscimeh@chulkn.chula.ac.th 1 18 NIPSY_RUSSELL satterfieldj@alpha.hendrix.edu 1 17 Jan Andersen jaa@nov.cri.dk 1 17 David Rowe rowe@twain.ee.cornell.edu 1 16 Noah Dana-Picard dana@brachot.jct.ac.il 1 14 Lewis McCarthy lmccarth%klingon@cs.umass.edu 1 12 Jaroslav Gurican jaroslav.gurican@mff.uniba.cs 1 12 Carl A. LaCombe clacombe@jade.tufts.edu 1 11 Dennis Drapeau t9xu@math.unb.ca 1 5 Akos Seress akos@math.ohio-state.edu 1 5 Josep M. Arques arques@melq.uab.es 1 4 This file is in Berkeley mail drop format, which means you can read this file with 'mail -f ' or 'mailx -f '. It is also possible however to read this file with any text editor. From charnes@osiris.cs.uow.edu.au Mon Jul 04 10:36:00 1994 From: "Chris Charnes" Date: Mon, 04 Jul 94 10:36 +1000 Subject: no subject (file transmission) Dear Gap-forum, I need a routine that returns a polynomial of say degree 100 over GF(2) of the form: x^100 + x^a + x^b + ... + 1, where each component of (a,b,c,...) is < 100. Yours C.Charnes From Alexander.Hulpke@Math.RWTH-Aachen.DE Mon Jul 04 08:52:00 1994 From: "Alexander Hulpke" Date: Mon, 04 Jul 94 08:52 +0200 Subject: Re: random polynomials Dear GAP-Forum, Chris Charnes asked: > I need > a routine that returns a polynomial of say degree 100 over GF(2) of the > form: x^100 + x^a + x^b + ... + 1, where each component of (a,b,c,...) is > < 100. Taking the following routine: # RandomNormedPol(,) RandomNormedPol := function ( r, deg ) local f; f := r.operations.Random; if not IsField( r ) then r := Field( r ); fi; return Polynomial( r, Concatenation( List( [ 1 .. RandomList( deg ) ], function ( i ) return f( r ); end ), [ r.one ] ) ); end; This will do the job: gap> k:=GF(2);; gap> RandomNormedPol(k,[100]); Alexander Hulpke -- Lehrstuhl D fuer Mathematik, RWTH, Templergraben 64, 52056 Aachen, Germany, eMail: Alexander.Hulpke@math.rwth-aachen.de From sl25@cus.cam.ac.uk Mon Jul 04 11:23:00 1994 From: "Steve Linton" Date: Mon, 04 Jul 94 11:23 +0200 Subject: Re: no subject (file transmission) This appears easy - l := [a,b,c,...]; f := GF(2); Add(l,100); l := Set(l); v := List([0..100],function(i) if i in l then return f.one; else return f.zero; fi; end); Polynomial(f,v); Have I misunderstodd what you are looking for? Steve From kulendor@machnix.mathematik.uni-stuttgart.de Mon Jul 04 15:43:00 1994 From: "Ottokar Kulendik" Date: Mon, 04 Jul 94 15:43 +0200 Subject: Re: Bug in 'SubdirectProduct' when using the projection Dear forum, I have another problem using 'Projection()' from the 'SubdirectProduct()': an error occurs when I try to use 'PreImagesRepresentative(): # again the example usage of 'SubdirectProduct()' from the GAP manual s3 := Group( (1,2,3), (1,2) );; c3 := Subgroup( s3, [ (1,2,3) ] );; x1 := Operation( s3, Cosets( s3, c3 ), OnRight );; h1 := OperationHomomorphism( s3, x1 );; d8 := Group( (1,2,3,4), (2,4) );; c4 := Subgroup( d8, [ (1,2,3,4) ] );; x2 := Operation( d8, Cosets( d8, c4 ), OnRight );; h2 := OperationHomomorphism( d8, x2 );; s := SubdirectProduct( s3, d8, h1, h2 ); # compute the projection and copy entries from the direct product # to fix the bug earlier mentioned p1_s := Projection(s, s3, 1); d12 := DirectProduct(s3, d8); s.news := d12.news; s.perms := d12.perms; s.olds := d12.olds; # try to use 'PreImagesReresentative()' on an arbitrary element of # the image of the projection x := Random(Image(p1_s, p1_s.source)); PreImagesRepresentative( p1_s, x ); GAP responds: Error, Record: element 'perms' must have an assigned value at elm := img ^ prj.range.perms[prj.component] ... in map.operations.PreImagesRepresentative( map, img ) called from PreImagesRepresentative( p1_s, x ) called from main loop brk> Ottokar Kulendik From Alexander.Hulpke@Math.RWTH-Aachen.DE Mon Jul 04 17:34:00 1994 From: "Alexander Hulpke" Date: Mon, 04 Jul 94 17:34 +0200 Subject: Re: Bug in 'SubdirectProduct' when using the projection Dear GAP-forum, Ottokar Kulendik wrote: > I have another problem using 'Projection()' from the 'SubdirectProduct()': > an error occurs when I try to use 'PreImagesRepresentative(): > PreImagesRepresentative( p1_s, x ); > GAP responds: > Error, Record: element 'perms' must have an assigned value at Obviously, this function has never been used by anybody... The error has been fixed in version 3.4, however it involves substancially more, that just adding some record components. Sorry for the inconveniences, Alexander Hulpke From ara@altdorf.ai.mit.edu Mon Jul 04 12:23:00 1994 From: "Allan Adler" Date: Mon, 04 Jul 94 12:23 -0400 Subject: Adding Online Documentation (2) I have applied the suggestions of Martin Sch"onert for adding online documentation. They work. ON the other hand, there are a few drawbacks: (1) One has to recompile the entire manual, which is time consuming. (2) One has to use Latex, whereas I would prefer to use Plain TeX (3) The formatting of the manual is itself unfamiliar. For example, one has sections and chapters, but it is not clear how to create subsections, subsubsections, etc. With more understanding of the formatting, one could make one's own modifications to the code. WIthout it, there are just chapters and sections. (4) One really should not hack the manual. It seems that there are various ways to solve these problems. One would be to make additional options available to the online help command such as to look in other places for TeX files, to accept Plain TeX, etc. Allan Adler ara@altdorf.ai.mit.edu From ruberman@max.math.brandeis.edu Tue Jul 05 10:30:00 1994 From: "Daniel Ruberman" Date: Tue, 05 Jul 94 10:30 +0100 (MET) Subject: Two questions on Fp groups Dear Gap-Forum: I have the following sort of computation which I would like to do using GAP: I am given a finitely presented group P, a surjective homomorphism f from P to a finite group G (given, as, say a subgroup of a permutation group), and a subgroup H of G. I would like to compute the abelianization of the inverse image of H under f. I realize that this could be done using the command `AbelianInvariantsSubgroupFpGroup', once generators have been chosen for the subgroup f^-1(H). Finding generators is easy `by hand' starting from a transversal of f^-1(H) in P; the question is how to find such transversal using GAP. The key point seems to be pulling back a transversal of H in G to P. Does anyone have any pointers on how this can be done in GAP? My second question is related: has the Fox free calculus been implemented in GAP (or something whose output is accessible to GAP)? From a computational standpoint, would it be better to use the command AbelianInvariants... (assuming that the question in the previous paragraph has a reasonable answer)? Thanks for any input. Daniel Ruberman ruberman@max.math.brandeis.edu ruberman@binah.cc.brandeis.edu From Thomas.Breuer@Math.RWTH-Aachen.DE Tue Jul 05 16:22:00 1994 From: "Thomas Breuer" Date: Tue, 05 Jul 94 16:22 WET Subject: Re: Can GAP do group rings? Dear Mrs. and Mr. Forum, recently Evelyn Hart asked you whether GAP can handle group rings. She told > I'm interested in the group ring Z[\pi] where Z is the integers > and \pi is the group on four generators, a,b,c,d with one relation > a b 1/a 1/b c d 1/c 1/d. At the moment GAP has no facilities to do computations with group rings. In the near future we will introduce group ring data structures. But there is no aim to deal with group rings of finitely presented groups, since for arithmetic calculations with group ring elements it is necessary to decide at least whether or not two group elements are equal, for which there is no general algorithmic method with finitely presented groups. Sorry that GAP does not provide the expected tools in any straightforward way. However, does anybody have ideas how to attack problems of this kind algorithmically? Kind regards Thomas Breuer (sam@math.rwth-aachen.de) From r.a.fenn@sussex.ac.uk Tue Jul 05 17:10:00 1994 From: "Roger A Fenn" Date: Tue, 05 Jul 94 17:10 +0200 Subject: Re: Can GAP do group rings? > > Dear Mrs. and Mr. Forum, > > recently Evelyn Hart asked you whether GAP can handle group rings. > She told > > > I'm interested in the group ring Z[\pi] where Z is the integers > > and \pi is the group on four generators, a,b,c,d with one relation > > a b 1/a 1/b c d 1/c 1/d. > > At the moment GAP has no facilities to do computations with > group rings. In the near future we will introduce group ring > data structures. But there is no aim to deal with group rings > of finitely presented groups, since for arithmetic calculations > with group ring elements it is necessary to decide at least > whether or not two group elements are equal, for which there is > no general algorithmic method with finitely presented groups. > > Sorry that GAP does not provide the expected tools in any > straightforward way. However, does anybody have ideas how > to attack problems of this kind algorithmically? > > Kind regards > Thomas Breuer > (sam@math.rwth-aachen.de) > > How about working with the group ring over a finitely generated free (non) abelian group? Roger Fenn. From charnes@osiris.cs.uow.edu.au Wed Jul 06 14:20:00 1994 From: "Chris Charnes" Date: Wed, 06 Jul 94 14:20 +1000 Subject: GF(2)_polynomials Dear Gap-Forum, I would like a routine that does the following: f, g are polynomials over GF(2), deg(f) >> deg(g), I require the remainder when g divides f; i.e. f=h*g + r, where deg(r) < deg(g). (The Euc. Algorithm). Yours C. Charnes From Joachim.Neubueser@Math.RWTH-Aachen.DE Wed Jul 06 09:43:00 1994 From: "Joachim Neubueser" Date: Wed, 06 Jul 94 09:43 +0200 Subject: Re: GF(2)_polynomials Chris Charnes writes: > I would like a routine that does the following: f, g are polynomials > over GF(2), deg(f) >> deg(g), I require the remainder when g divides > f; i.e. f=h*g + r, where deg(r) < deg(g). (The Euc. Algorithm). There is in fact a GAP function 'EucledianRemainder' in the manual which does exactly what you require: gap> p := Z(2)^0*(X(GF(2))^4 + X(GF(2))^2 + X(GF(2)) + 1);; gap> q := Z(2)^0*(X(GF(2))^2 + 1);; gap> EuclideanRemainder( PolynomialRing( GF( 2 ) ), p, q ); Z(2)^0*(X(GF(2)) + 1) If you find the input of polynomials of high degree over GF(2) too clumsy in this form there is a trick to save some writing: gap> p := Polynomial( GF( 2 ), [ 1, 1, 1, 0, 1 ] * GF( 2 ).one ); Z(2)^0*(X(GF(2))^4 + X(GF(2))^2 + X(GF(2)) + 1) gap> q := Polynomial( GF( 2 ), [ 1, 0, 1, ] * GF( 2 ).one ); Z(2)^0*(X(GF(2))^2 + 1) gap> EuclideanRemainder( PolynomialRing( GF( 2 ) ), p, q ); Z(2)^0*(X(GF(2)) + 1) Please excuse me however for suggesting first to look up the manual before writing to 260 members of the GAP forum. Even though the manual is long it has an index which in this case gives: EuclideanRemainder . . . for polynomials 392 Polynomials 383 Field . . . finite 375 Kind regards, Joachim Neubueser From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Jul 06 17:24:00 1994 From: "Martin Schoenert" Date: Wed, 06 Jul 94 17:24 +0100 (MET) Subject: Re: Adding Online Documentation (2) Allan Adler writes in his e-mail message of 1994/07/04 I have applied the suggestions of Martin Sch"onert for adding online documentation. They work. ON the other hand, there are a few drawbacks: (1) One has to recompile the entire manual, which is time consuming. You can use the line '\includeonly{,...}' at the top of 'manual.tex' to tell LaTeX which chapters to process. For the other chapters only the '.aux' files are read. This is quite a bit faster. The line numbers in the table of contents and the index wont be correct, but that doesn't bother the online help at all. Allan Adler continues (2) One has to use Latex, whereas I would prefer to use Plain TeX This is very easy to fix. Write a Plain TeX to LaTeX converter. This will even be usefull for other tasks, not only for the GAP online help. But seriously. In the manual (at least in those parts that can be read in the online help), we use so few formatting commands (even lists are forbidden), that it doesn't make a big difference whether we use LaTeX or Plain TeX. Allan Adler continues (3) The formatting of the manual is itself unfamiliar. For example, one has sections and chapters, but it is not clear how to create subsections, subsubsections, etc. With more understanding of the formatting, one could make one's own modifications to the code. WIthout it, there are just chapters and sections. What is unfamiliar about chapters and sections? There is no *technical* reason to allow only chapters and sections, and no subsections or subsubsections. However, I think that two levels are enough in online documentation. I often get lost in TeXinfo documentation (e.g., the on for Emacs), because I don't know how far away from the top I am, whether I want to go to the next node or up and then to the next, etc. Allan Adler continues (4) One really should not hack the manual. Well, if you want GAP to automatically find your documentation you have to change some file. As it happens this file is 'manual.tex'. And I really don't see that adding a few lines to this file can be called ``hacking''. Allan Adler continues It seems that there are various ways to solve these problems. One would be to make additional options available to the online help command such as to look in other places for TeX files, to accept Plain TeX, etc. Yes, there are lots of nice things one could add to the online help. I'll do them all in our copious free time ;-) Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Volkmar.Felsch@Math.RWTH-Aachen.DE Wed Jul 06 18:04:00 1994 From: "Volkmar Felsch" Date: Wed, 06 Jul 94 18:04 +0200 Subject: Re: Two questions on Fp groups Daniel Ruberman writes: > Dear Gap-Forum: I have the following sort of computation which I would like > to do using GAP: I am given a finitely presented group P, a surjective > homomorphism f from P to a finite group G (given, as, say a subgroup of > a permutation group), and a subgroup H of G. I would like to compute the > abelianization of the inverse image of H under f. I realize that this > could be done using the command `AbelianInvariantsSubgroupFpGroup', once > generators have been chosen for the subgroup f^-1(H). Finding > generators is easy `by hand' starting from a transversal of f^-1(H) in P; > the question is how to find such transversal using GAP. The key point > seems to be pulling back a transversal of H in G to P. Does anyone have > any pointers on how this can be done in GAP? Here is an example which demonstrates how you can compute the abelian invariants of the commutator factor group of the inverse image of H under f: gap> # Let P be a product of a free group on 1 generator and a cyclic group gap> # of order 2. gap> P := FreeGroup( 2 ); Group( f.1, f.2 ) gap> P.relators := [ P.2^2 ];; gap> gap> # Let G be the symmetric group of degree 3. gap> G := SymmetricGroup( 3 ); Group( (1,3), (2,3) ) gap> # Ensure that G has 2 generators. gap> Length( G.generators ); 2 gap> gap> # Get in G a subgroup H of order 2. gap> H := Subgroup( G, [ (1,2) ] ); Subgroup( Group( (1,3), (2,3) ), [ (1,2) ] ) gap> gap> # Compute the permutation group PG induced by G acting on the right gap> # costets of H. gap> PG := Operation( G, Cosets( G, H ), OnRight ); Group( (1,3), (1,2) ) gap> gap> # Construct a coset table of H in G from the generators of PG which gap> # respects square relators of P. gap> T := [ ];; gap> D := [ 1 .. Maximum( List( PG.generators, LargestMovedPointPerm ) ) ]; [ 1 .. 3 ] gap> for i in [ 1 .. Length( P.generators ) ] do > g := PG.generators[i]; > T[2*i-1] := OnTuples( D, g ); > p := P.generators[i]; > if p^2 in P.relators or p^-2 in P.relators then > T[2*i] := T[2*i-1]; > else > T[2*i] := OnTuples( D, g^-1 ); > fi; > od; gap> StandardizeTable( T ); gap> Print( T, "\n" ); [ [ 2, 1, 3 ], [ 2, 1, 3 ], [ 3, 2, 1 ], [ 3, 2, 1 ] ] gap> gap> # Get a subgroup S of P, enter the coset table into its group record. gap> # and compute the abelian invariants of S/S'. gap> S := ShallowCopy( Subgroup( P, [ ] ) );; gap> S.cosetTable := T;; gap> A := AbelianInvariantsSubgroupFpGroupRrs( P, S ); [ 2, 0, 0 ] Note that what we are doing here is not quite legal: In general, the subgroup S which is defined by its generators is not consistent with the coset table T associated to it (in fact, in our example S is the trivial subgroup of P, that's why we are cautious and use the ShallowCopy command). In deed, we make use of the fact that the 'AbelianInvariantsSubgroupFpGroup' command ignores the rest of S if a record component S.cosetTable is given. You should use this only as a kind of intermediate solution for your problem. In the next patch of GAP I will change the command such that it allows the second argument to be a coset table instead of a subgroup. Unfortunately, it is to late to insert this change into the current release of GAP 3.4. I would like to add another hint: Werner Nickel at Aachen is just finishing a file 'ctpg.g' containing some functions which are useful in the situation described above. He will put it into the directory ~ftp/pub/incoming on samson.math.rwth-aachen.de within the next couple of days. For further details you should look into the comments of that file. Volkmar Felsch, Aachen From charnes@osiris.cs.uow.edu.au Thu Jul 07 10:14:00 1994 From: "Chris Charnes" Date: Thu, 07 Jul 94 10:14 +1000 Subject: Re: GF(2)_polynomials Dear Joachim, my version of the manual (3.3) has on p 392: IsLaurentPolynomialRing. I couldn't find any reference to the Euclidean algorithm. Yet now that you mention it I find it the on line manual. Can I get a more up to date manual? Yours Chris Charnes From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jul 07 09:32:00 1994 From: "Joachim Neubueser" Date: Thu, 07 Jul 94 09:32 +0200 Subject: Re: GF(2)_polynomials > Dear Joachim, my version of the manual (3.3) has on p 392: > IsLaurentPolynomialRing. I couldn't find any reference to the > Euclidean algorithm. Yet now that you mention it I find it the > on line manual. Can I get a more up to date manual? > Yours Chris Charnes The reference 'EuclideanRemainder' *is* further down the page! There is no manual entry 'Euclidean algorithm' since the function names in general try to reflect what the function returns, not by which algorithm the result is obtained. By the way, I think that the general usage of the term 'Euclidean algorithm' means the algorithm for the computation of the gcd by repeated use of division with remainder, not just the division with remainder. There is also a function Gcd for the computation of the gcd.For polynomials it is descibed on p. 393 (in the middle of it!). Please note that the index gives p. 392 for it. This is because page numbers in the index mostly refer to the beginning of the section in which the function is described, which in this case is section 18.16 'Ring Functions for Polynomial Rings'. I think it is not too difficult to glance through such a section. But really please let us now stop now to bother other members of the GAP-forum with this discussion. If you want to continue discussion how to find a reference please write directly to me. As to versions of the manual, we are obviously both using the manual for GAP 3.3, which today is still the latest, however will be replaced by a new, extended one with the release of version 3.4., which will be available with the program via ftp as before. Joachim Neubueser From sl25@cus.cam.ac.uk Thu Jul 07 16:07:00 1994 From: "Steve Linton" Date: Thu, 07 Jul 94 16:07 +0200 Subject: Re: Can GAP do group rings? > Dear Mrs. and Mr. Forum, > > recently Evelyn Hart asked you whether GAP can handle group rings. > She told > > > I'm interested in the group ring Z[\pi] where Z is the integers > > and \pi is the group on four generators, a,b,c,d with one relation > > a b 1/a 1/b c d 1/c 1/d. > > At the moment GAP has no facilities to do computations with > group rings. In the near future we will introduce group ring > data structures. But there is no aim to deal with group rings > of finitely presented groups, since for arithmetic calculations > with group ring elements it is necessary to decide at least > whether or not two group elements are equal, for which there is > no general algorithmic method with finitely presented groups. > > Sorry that GAP does not provide the expected tools in any > straightforward way. However, does anybody have ideas how > to attack problems of this kind algorithmically? The group in question appears to admit a finite confluent rewriting system (with the RPO, according to Derek Holt's Knuth-Bendix program). If this is true (ie if I haven't made a typing mistake) then the word problem is easily solvable and so computation in the group ring should be feasible. As yet GAP has neither group rings nor groups given by confluent rewriting systems (except AG groups) , but they could be added within the domain system. Steve Linton From dfh@maths.warwick.ac.uk Thu Jul 07 15:35:00 1994 From: "Derek Holt" Date: Thu, 07 Jul 94 15:35 +0100 Subject: Re: Can GAP do group rings? > > recently Evelyn Hart asked you whether GAP can handle group rings. > > She told > > > > > I'm interested in the group ring Z[\pi] where Z is the integers > > > and \pi is the group on four generators, a,b,c,d with one relation > > > a b 1/a 1/b c d 1/c 1/d. > > > > At the moment GAP has no facilities to do computations with > > group rings. In the near future we will introduce group ring > > data structures. But there is no aim to deal with group rings > > of finitely presented groups, since for arithmetic calculations > > with group ring elements it is necessary to decide at least > > whether or not two group elements are equal, for which there is > > no general algorithmic method with finitely presented groups. > > > > Sorry that GAP does not provide the expected tools in any > > straightforward way. However, does anybody have ideas how > > to attack problems of this kind algorithmically? > > The group in question appears to admit a finite confluent rewriting > system (with the RPO, according to Derek Holt's Knuth-Bendix > program). If this is true (ie if I haven't made a typing mistake) > then the word problem is easily solvable and so computation in the > group ring should be feasible. As yet GAP has neither group rings > nor groups given by confluent rewriting systems (except AG groups) , > but they could be added within the domain system. > > Steve Linton There are some tentative plans to add groups given by confluent rewriting systems to GAP. The group in question is a two-dimensional surface group, and LeChenadec proved that all such groups have confluent rewriting systems with respect to a short-lex ordering (which is preferable to RPO, because words are reduced to their shortest possible forms). The snag is that the ordering of the generators that you need for this is not the obvious one. In this example, the ordering a < c < b < d works, but a < b < c < d does not. The complete rewriting system is a*a^-1 > 1 a^-1*a > 1 c*c^-1 > 1 c^-1*c > 1 b*b^-1 > 1 b^-1*b > 1 d*d^-1 > 1 d^-1*d > 1 b*a*b^-1*a^-1 > c*d*c^-1*d^-1 b^-1*c*d*c^-1 > a*b^-1*a^-1*d b^-1*a^-1*d*c > a^-1*b^-1*c*d b*a^-1*b^-1*c > a^-1*d*c*d^-1 d*c*d^-1*c^-1 > a*b*a^-1*b^-1 d*c^-1*d^-1*a > c^-1*b*a*b^-1 d^-1*a*b*a^-1 > c*d^-1*c^-1*b Derek Holt. From timhsu@math.princeton.edu Tue Jul 12 18:08:00 1994 From: "Tim Hsu" Date: Tue, 12 Jul 94 18:08 -0400 (EDT) Subject: Words for secondary generators I've been trying to set up a calculation using AugmentedCosetTableRrs. Now, when you have the statement aug := AugmentedCosetTableRrs(G,ct,2,"_q"); (ct is the coset table for a subgroup S in G), aug.primaryGeneratorWords contains descriptions of the primary generators of S in terms of words in the generators of G. According to the GAP manual, aug.tree, (in some form) contains a description of the secondary generators of S in terms of the primary relators, so in theory, you should be able to obtain the secondary generators of S in terms of words in G. Could someone tell me how to get this from the tree? My next question is, do RewriteSubgroupRelators, PresentationAugmentedCosetTable, TzGo, or FpGroupPresentation change the ordering of the generators in any way, other than eliminating generators? Thanks very much. Tim Hsu From gaehler@msc.cornell.edu Wed Jul 20 13:31:00 1994 From: "Franz Gaehler" Date: Wed, 20 Jul 94 13:31 -0400 Subject: space groups, and a bug Der GAPers, I have been trying to do some space group computations with GAP, and ran into what seems to be a bug (gap3r3p0 on IBM RS/6000). Since infinite matrix groups are not supported, the only way to deal with space groups seemed to be to represent them as finitely presented groups. I was interested in the subgroup structure of some 6D space group, whose point group is isomorphic to A5. In order to make the problem simpler, I have divided all groups by a translation sublattice common to all space groups I wanted to consider. Here is the session: gap> f := FreeGroup("A","B","t1","t2","t3","t4","t5","t6");; gap> gap> A :=f.1;; B := f.2;; gap> t1:=f.3;; t2:=f.4;; t3:=f.5;; t4:=f.6;; t5:=f.7;; t6:=f.8;; gap> gap> # relators between rotations gap> gap> rel:=[ A^5, B^3, (A*B)^2 ];; gap> gap> # add relators between translations gap> gap> Append(rel, > [(t1*t2)/(t2*t1), (t1*t3)/(t3*t1), (t1*t4)/(t4*t1), > (t1*t5)/(t5*t1), (t1*t6)/(t6*t1), > (t2*t3)/(t3*t2), (t2*t4)/(t4*t2), > (t2*t5)/(t5*t2), (t2*t6)/(t6*t2), > (t3*t4)/(t4*t3), (t3*t5)/(t5*t3), (t3*t6)/(t6*t3), > (t4*t5)/(t5*t4), (t4*t6)/(t6*t4), (t5*t6)/(t6*t5)]);; gap> gap> # add relators beween rotations and translations gap> gap> Append(rel, > [(A*t1)/(t1*A), (A*t2)/(t3*A), (A*t3)/(t4*A), > (A*t4)/(t5*A), (A*t5)/(t6*A), (A*t6)/(t2*A), > (B*t1)/(t2*B), (B*t2)/(t3*B), (B*t3)/(t1*B), > (B*t4)/(t6*B), (t4*B*t5)/(B), (t5*B*t6)/(B)]);; gap> gap> # divide by sublattice gap> gap> Append(rel, > [t2*t3*t4*t5*t6, (t1*t3*t6)/(t4*t5), (t1*t4*t2)/(t5*t6), > (t1*t5*t3)/(t6*t2), (t1*t6*t4)/(t2*t3), (t1*t2*t5)/(t3*t4)]);; gap> gap> # define the big, symmorphic space group gap> gap> spg:=f/rel;; gap> gap> A :=spg.1;; B :=spg.2;; gap> t1:=spg.3;; t2:=spg.4;; t3:=spg.5;; t4:=spg.6;; t5:=spg.7;; t6:=spg.8;; gap> gap> # here are some (sub-) space groups having the translation sublattice gap> # divided out above gap> gap> ug0:=Subgroup(spg, [A, B]);; gap> ug1:=Subgroup(spg, [t1*t3^-1*t5*A, B]);; gap> ug2:=Subgroup(spg, [t1^2*t3^-2*t5^2*A, B]);; gap> ug3:=Subgroup(spg, [t1^3*t3^-3*t5^3*A, B]);; gap> ug4:=Subgroup(spg, [t1^4*t3^-4*t5^4*A, B]);; gap> gap> # all these subgroups have index 125 in spg gap> gap> Index(spg, ug0); 125 gap> gap> # are there any groups between spg and ug0 ? gap> gap> lst:=LowIndexSubgroupsFpGroup(spg, ug0, 25); [ Subgroup( Group( A, B, t1, t2, t3, t4, t5, t6 ), [ A, t1 ] ) ] gap> gap> # this is wrong, as is the following result! gap> gap> List(lst,h->Index(spg,h)); [ 1 ] gap> gap> # correct is: gap> gap> Index(spg, Subgroup(spg, [ A, t1 ]) ); 300 gap> gap> Size(spg); Size(ug0); Size( Subgroup(spg, [ A, t1 ])); 7500 60 25 Anyone know what's going on here? I had been asking for subgroups of index (at most) 25 in spg, not of order 25! How do other people deal with space groups? Finitely presented groups do not seem to be ideal. When I do something like LowIndexSubgroupsFpGroup(spg, TrivialSubgroup(spg), 125); it takes ages (after some 30 hours (on an IBM RS/6000) it was still not finished, so I stopped it). Another option would be to represent space group elements by augmented matrices. The problem of infinite matrix groups could be circumvented by dividing out a suitable sublattice. The translation part of augmented matrices then would have to be taken modulo a lattice. If matrices are expressed with respect to a lattice basis of that lattice, the translation components had to be taken modulo 1, at least when comparing matrices, possibly also in matrix multiplication, in order to prevent elements from growing indefinitely. Perhaps even better would be to set up a group of translations as Z^n modulo some sublattice L of Z^n (possibly with L=m*Z^n). If representatives of such equivalence classes could be represented as integral vectors modulo L, one would have a natural action of a matrix point group on such translation vectors. One could then build a semi-direct product of a finite matrix (point) group with such a finite translation group, and consider suitable subgroups thereof. What would be involved in using such a scheme? Implementation of a new domain of 'augmented matrices modulo a lattice', or a new domain of translations in 'Z^n modulo L'? Would this be feasible? How could this be implemented? And would it be efficient? Thanks for any suggestions. Best regards, Franz Gaehler From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Jul 20 22:53:00 1994 From: "Martin Schoenert" Date: Wed, 20 Jul 94 22:53 +0100 (MET) Subject: 'samson' died Monday 11th our central server 'samson' died. Since neither Frank nor I were in Aachen for that week, the broken machine could not be replaced until Saturday 16th. E-mail messages mailed between Monday evening and Wednesday noon bounced back to the originator. Later E-mail messages might have been lost. So if you mailed an e-mail message last week to one of us here in Aachen and are still waiting for a response, you should send that e-mail message again. Other services, e.g., 'ftp' were also unavailable during this week. By now everything should be back to normal. Sorry for any inconveniences. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From gaehler@msc.cornell.edu Wed Jul 20 13:31:00 1994 From: "Franz Gaehler" Date: Wed, 20 Jul 94 13:31 -0400 Subject: space groups, and a bug [Almost all mailer daemons rejected this message originally, because the 'From:' line contained a single unbalanced '"'. Apologies to those who have more forgiving mailer daemons, and see this message now for the second time. mS] Der GAPers, I have been trying to do some space group computations with GAP, and ran into what seems to be a bug (gap3r3p0 on IBM RS/6000). Since infinite matrix groups are not supported, the only way to deal with space groups seemed to be to represent them as finitely presented groups. I was interested in the subgroup structure of some 6D space group, whose point group is isomorphic to A5. In order to make the problem simpler, I have divided all groups by a translation sublattice common to all space groups I wanted to consider. Here is the session: gap> f := FreeGroup("A","B","t1","t2","t3","t4","t5","t6");; gap> gap> A :=f.1;; B := f.2;; gap> t1:=f.3;; t2:=f.4;; t3:=f.5;; t4:=f.6;; t5:=f.7;; t6:=f.8;; gap> gap> # relators between rotations gap> gap> rel:=[ A^5, B^3, (A*B)^2 ];; gap> gap> # add relators between translations gap> gap> Append(rel, > [(t1*t2)/(t2*t1), (t1*t3)/(t3*t1), (t1*t4)/(t4*t1), > (t1*t5)/(t5*t1), (t1*t6)/(t6*t1), > (t2*t3)/(t3*t2), (t2*t4)/(t4*t2), > (t2*t5)/(t5*t2), (t2*t6)/(t6*t2), > (t3*t4)/(t4*t3), (t3*t5)/(t5*t3), (t3*t6)/(t6*t3), > (t4*t5)/(t5*t4), (t4*t6)/(t6*t4), (t5*t6)/(t6*t5)]);; gap> gap> # add relators beween rotations and translations gap> gap> Append(rel, > [(A*t1)/(t1*A), (A*t2)/(t3*A), (A*t3)/(t4*A), > (A*t4)/(t5*A), (A*t5)/(t6*A), (A*t6)/(t2*A), > (B*t1)/(t2*B), (B*t2)/(t3*B), (B*t3)/(t1*B), > (B*t4)/(t6*B), (t4*B*t5)/(B), (t5*B*t6)/(B)]);; gap> gap> # divide by sublattice gap> gap> Append(rel, > [t2*t3*t4*t5*t6, (t1*t3*t6)/(t4*t5), (t1*t4*t2)/(t5*t6), > (t1*t5*t3)/(t6*t2), (t1*t6*t4)/(t2*t3), (t1*t2*t5)/(t3*t4)]);; gap> gap> # define the big, symmorphic space group gap> gap> spg:=f/rel;; gap> gap> A :=spg.1;; B :=spg.2;; gap> t1:=spg.3;; t2:=spg.4;; t3:=spg.5;; t4:=spg.6;; t5:=spg.7;; t6:=spg.8;; gap> gap> # here are some (sub-) space groups having the translation sublattice gap> # divided out above gap> gap> ug0:=Subgroup(spg, [A, B]);; gap> ug1:=Subgroup(spg, [t1*t3^-1*t5*A, B]);; gap> ug2:=Subgroup(spg, [t1^2*t3^-2*t5^2*A, B]);; gap> ug3:=Subgroup(spg, [t1^3*t3^-3*t5^3*A, B]);; gap> ug4:=Subgroup(spg, [t1^4*t3^-4*t5^4*A, B]);; gap> gap> # all these subgroups have index 125 in spg gap> gap> Index(spg, ug0); 125 gap> gap> # are there any groups between spg and ug0 ? gap> gap> lst:=LowIndexSubgroupsFpGroup(spg, ug0, 25); [ Subgroup( Group( A, B, t1, t2, t3, t4, t5, t6 ), [ A, t1 ] ) ] gap> gap> # this is wrong, as is the following result! gap> gap> List(lst,h->Index(spg,h)); [ 1 ] gap> gap> # correct is: gap> gap> Index(spg, Subgroup(spg, [ A, t1 ]) ); 300 gap> gap> Size(spg); Size(ug0); Size( Subgroup(spg, [ A, t1 ])); 7500 60 25 Anyone know what's going on here? I had been asking for subgroups of index (at most) 25 in spg, not of order 25! How do other people deal with space groups? Finitely presented groups do not seem to be ideal. When I do something like LowIndexSubgroupsFpGroup(spg, TrivialSubgroup(spg), 125); it takes ages (after some 30 hours (on an IBM RS/6000) it was still not finished, so I stopped it). Another option would be to represent space group elements by augmented matrices. The problem of infinite matrix groups could be circumvented by dividing out a suitable sublattice. The translation part of augmented matrices then would have to be taken modulo a lattice. If matrices are expressed with respect to a lattice basis of that lattice, the translation components had to be taken modulo 1, at least when comparing matrices, possibly also in matrix multiplication, in order to prevent elements from growing indefinitely. Perhaps even better would be to set up a group of translations as Z^n modulo some sublattice L of Z^n (possibly with L=m*Z^n). If representatives of such equivalence classes could be represented as integral vectors modulo L, one would have a natural action of a matrix point group on such translation vectors. One could then build a semi-direct product of a finite matrix (point) group with such a finite translation group, and consider suitable subgroups thereof. What would be involved in using such a scheme? Implementation of a new domain of 'augmented matrices modulo a lattice', or a new domain of translations in 'Z^n modulo L'? Would this be feasible? How could this be implemented? And would it be efficient? Thanks for any suggestions. Best regards, Franz Gaehler From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Jul 20 23:54:00 1994 From: "Martin Schoenert" Date: Wed, 20 Jul 94 23:54 +0100 (MET) Subject: GAP version 3 release 4 finally release Lehrstuhl D f"ur Mathematik is pleased to announce the availability of GAP version 3 release 4. GAP 3.4 contains many new functions. The following lists only the highlights, not the many improvments throughout the library. GAP now supports algebras, modules, and character functions. GAP now contains functions to compute Galois groups and field extensions. GAP now contains functions for the determination of ``special ag systems'' of solvable groups, which e.g. allow the determination of all maximal subgroups, pre-Frattini groups, and Eulerian functions. GAP contains new data libraries of transitive permutation groups and crystallographic groups. The Meataxe, Vector Enumerator, Smash, and ANU SQ packages are new. Currently GAP 3.4 can only be found on 'ftp.math.rwth-aachen.de', but it should make its way to the other 'ftp' servers soon. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Werner.Nickel@Math.RWTH-Aachen.DE Fri Jul 22 09:29:00 1994 From: "Werner Nickel" Date: Fri, 22 Jul 94 09:29 WET Subject: Re: space groups and a bug Dear Forum, Franz G"ahler reported in the GAP-Forum about a bug he observed with the command LowIndexSubgroupsFpGroup() and, moreover, raised some general questions about handling space groups in GAP. Let us answer these in turn. 1. There is indeed a bug in LowIndexSubgroupsFpGroup(). However, it is easily corrected. What happens is the following. Let as a second argument of that command a non-trivial subgroup U be given and therefore, subgroups V containing U be sought. Then the command produces all these subgroups but gives as output only sets of elements that together with generating elements of U will generate the subgroups V. Of course, what should have been done is to give as output a full generating set for each V which can easily be obtained. Otherwise, the command seems to work correctly and indeed in the case investigated by Franz G"ahler the only subgroup properly containing ug0 is the full group. GAP knows in addition to the generating sets for the subgroups V also their coset tables and that is why it reports correctly from this knowledge that the only subgroup V, it found, has index 1. Unfortunately, the bug is still in GAP 3.4 that has just been released. It will be corrected in the first patch. 2. Using the command LowIndexSubgroupsFpGroup() on this group with a presentation on 8 generators and asking for subgroups of index up to 125 is indeed hopeless. Please note that this command works by searching in a backtrack fashion for homomorphic images of the finitely presented group in the symmetric group on 125 letters. Even though that backtrack is rather clever, this is hopeless. Generally, it should be understood that this command has reasonable chances only for rather small numbers of generators (2 or 3 say) and that `low index' is better understood even in most such cases to be well under 100. 3. We do not have special routines for investigating space groups in GAP as yet. But even though this is not at the top of our priority list, there are intentions to implement such. Please note that GAP 3.4 provides for the first time the library of all space groups up to dimension 4 from Brown et al. One way to get certain information is certainly to follow the suggestion of Franz G"ahler to calculate modulo certain invariant sublattices of the translation lattice. For such finite factor groups of the space group one can, for instance, use faithful permutation representations. In the case of the factor group of the space group that Franz G"ahler investigates such a faithful permutation representation can be obtained on the 125 cosets of the subgroup ug0. A permutation group of degree 125 can, of course, be very well handled in GAP: gap> T := CosetTableFpGroup( spg, ug0 );; #I CosetTableFpGroup called: #I defined deleted alive maximal #I 127 2 125 127 gap> Pspg := Group( List( T{[1,3..15]}, t->PermList(t) ), () );; gap> Size( Pspg ); 7500 However, eventually it would indeed be better to create a new kind of group elements calculating with affine matrices modulo certain translations as Franz G"ahler suggests. We would like to mention in this context that at present with some students we are looking at the task of finding the (Wyckoff classes of) special positions for a given space group. However, it may take some time until such functions will be available. Joachim Neub"user, Werner Nickel. From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Jul 22 10:07:00 1994 From: "Joachim Neubueser" Date: Fri, 22 Jul 94 10:07 +0200 Subject: Re: Words for secondary generators Tim Hsu asked in the forum: > I've been trying to set up a calculation using AugmentedCosetTableRrs. > Now, when you have the statement > > aug := AugmentedCosetTableRrs(G,ct,2,"_q"); > > (ct is the coset table for a subgroup S in G), > aug.primaryGeneratorWords contains descriptions of the primary > generators of S in terms of words in the generators of G. According > to the GAP manual, aug.tree, (in some form) contains a description of > the secondary generators of S in terms of the primary relators, so in > theory, you should be able to obtain the secondary generators of S in > terms of words in G. Could someone tell me how to get this from the > tree? > > My next question is, do RewriteSubgroupRelators, > PresentationAugmentedCosetTable, TzGo, or FpGroupPresentation change > the ordering of the generators in any way, other than eliminating > generators? Thanks very much. I just want to acknowledge that the message has been read. The person who has implemented these routines, and therefore probably can best answer these questions, is Volkmar Felsch, who at present is on holidays. We will come back to the question whatever the exact answer will be, please excuse the delay. Joachim Neubueser From leonard@qmw.ac.uk Fri Jul 22 15:04:00 1994 From: "Leonard Soicher" Date: Fri, 22 Jul 94 15:04 BST Subject: Gap 3.4 Dear Forum, Yesterday, I ftp'd Gap 3.4, and it set up effortlessly on my IBM PC (after I deleted Gap 3.3 to make room). Of course I immediately wanted to check out GRAPE 2.2 (the Gap-only functions should work under MS-DOS). When I did RequirePackage("grape"); I got a message that grape was not installed. The problem was solved by changing certain "/" to "\\" in gap3r4p0\lib\abattoir.g, so that the pathnames would work with MS-DOS. Is there any way to code the path construction so that the same library functions work under both Unix and MS-DOS? But anyway, I look forward to exercising many of the new features in 3.4. Best regards, Leonard. From leonard@qmw.ac.uk Fri Jul 22 15:32:00 1994 From: "Leonard Soicher" Date: Fri, 22 Jul 94 15:32 BST Subject: Grape 2.2 in Gap 3.4 Dear Grape Users, The new release of Gap 3.4 contains the new release of Grape 2.2. Few changes have been made, but the user is warned that the Grape function Components is now called ConnectedComponents, the function Component is now called ConnectedComponent, and requires the input graph to be simple. Also, the default MAXN for nauty is now set to 8192. Have fun. Leonard Soicher From dima@maths.uwa.edu.au Sat Jul 23 21:52:00 1994 From: "Dima Pasechnik" Date: Sat, 23 Jul 94 21:52 WST Subject: Read() Dear Forum, I encountered a problem with the function Read. Namely, if I have a file in which a BIG permutation group, as well as its subgroup is stored in the format I give below, GAP starts MakeStabChain, which in my case is unnecessary and takes forever to complete (I discovered this by pressing ^C after waiting for a while for the prompt to appear.) The format is as follows: g:=Group();; g.name:="g";; h:=Subgroup(g,[]);; This does NOT happen if the group isn't too big (in my case g is of degree about 1500 and the number of generators is about 15 for both g and h). (I can supply the file with it upon request.) This happens equally for versions 3.3 and 3.4. (There is a certain way around it, I can keep generators as single permutations and recreate the group after entering them.) Regards, Dima From Alexander.Hulpke@Math.RWTH-Aachen.DE Sun Jul 24 15:44:00 1994 From: "Alexander Hulpke" Date: Sun, 24 Jul 94 15:44 +0200 Subject: Re: Read() (Rather: 'Subgroup') Dear Forum, Dima Pasechnik asked: > > I encountered a problem with the function Read. > Namely, if I have a file in which a BIG permutation group, as well as > its subgroup is stored in the format I give below, GAP starts > MakeStabChain, which in my case is unnecessary and takes forever to > complete (I discovered this by pressing ^C after waiting for a while for > the prompt to appear.) The problem is not due to 'Read' but due to 'Subgroup'. 'Subgroup' will check in general, whether the elements given as generators are indeed elements of the group. To test this, it has to create a stabilizer chain (unless the generators are a subset of the groups generators). > g:=Group();; > g.name:="g";; > h:=Subgroup(g,[]);; > > This does NOT happen if the group isn't too big According to my knowledge, this should as well happen if the group is small (you may check with 'RecFields(g)' that indeed a stabilizer chain is bound after loading and creating a subgroup). However for smaller groups this process is substancially faster and may go unnoticed. If you really want 'h' to be a 'Subgroup', you could proceed as follows: As the file you're loading did not fall from the sky, you will probably know already the size of g. Telling this to GAP will enourmously increase the speed of creating the stabilizer chain. You can do this, for example by inserting one line in your file: > g:=Group();; > g.name:="g";; g.size:=xxxxx; # whatever it is > h:=Subgroup(g,[]);; In this case, a random Schreier/Sims algorithm gets called, which is safe as the size is already known. In this situation, the random algorithm still guarantees that the stabilizer chain is correct. The time of computing the stabilizer chain then should be almost insignificant compared to loading the file. This feature is new to version 3.4. I would like to take the opportunity and remark that by the new command 'StabChain' you can also force a random Schreier/Sims algorithm to be used even if the groups size is not yet known. In many other cases of large permutation groups this might be quite helpful. Alexander Hulpke From dima@maths.uwa.edu.au Mon Jul 25 08:41:00 1994 From: "Dima Pasechnik" Date: Mon, 25 Jul 94 08:41 WST Subject: Re: Read() (Rather Subgroup(... Dear Forum, Let g:=Group(....). Is there any natural way to avoid calling a procedure checking whether h:=Subgroup(g,[...]) is indeed a subgroup in the moment of creating h? As we were told, this checking might be rather expensive if the generators of h does not form a subset of g.generators. Suppose one knows that the generators of h are words in g.generators. Then a strange way to create h fast is to add these words into g.generators. Can it be avoided? For instance, if g is a matrix group, there are no efficient ways to check that h<=g, so in fact I several times ran into this problem, when I created a subgroup of a matrix group, and gave up without understanding what went wrong. Regards, Dima From Frank.Celler@Math.RWTH-Aachen.DE Mon Jul 25 10:02:00 1994 From: "Frank Celler" Date: Mon, 25 Jul 94 10:02 WET Subject: Re: Read() (Rather Subgroup(... Dear Dima, >> Let g:=Group(....). Is there any natural way to avoid calling a procedure >> checking whether h:=Subgroup(g,[...]) is indeed a subgroup in the >> moment of creating h? in most cases avoiding the dispatcher will disable all test, eg, in order to create a subgroup without checking the generators one can use 'h := g.operations.Subgroup( Parent(g), [ ] )'. However, if are not elements of computations with might give wrong result without warning. best wishes Frank From a.mathas@ic.ac.uk Mon Jul 25 11:43:00 1994 From: "Andrew Mathas" Date: Mon, 25 Jul 94 11:43 +0100 Subject: operations query Here is a simple question which must have a simple answer. I have defined a record which has the form: rec (elt := a list, operations := Ops, ...) where Ops := rec (...). Inside the operations are various functions defining printing for the record, addition, and so on. I wanted to add a Length function for these elements so I wrote a Ops.Length function which of course doesn not work. Evidiently functions like "Print", "+" and so on are handled differently than other functions. So how do I add a Length function to this record? Incidently, unless I have missed it the description of such things does not appear to be in the manual. Similarly for the use of "arg" in function definitions. Are these documented anywhere? Thanks for your help, Andrew Mathas From fisk@polar.bowdoin.edu Mon Jul 25 11:52:00 1994 From: "Steve Fisk" Date: Mon, 25 Jul 94 11:52 -0400 Subject: gap 3.4 under emacs Dear gap forum, If I use the -n option in gap to prevent echoing in my emacs shell window, then I can not access the help system. Here is what happens: (using emacs 19.22) [gap3r4p0]< 14 > bin/gap -b -m 4 -l lib/ -h doc/ gap> ? ? Welcome to GAP ___________________________________________ Welcome to GAP Welcome to GAP. GAP is a system for computational group theory. Enter '?About GAP' for a step by step introduction to GAP. Enter '?Help' for information how to use the GAP help system. Enter '?Chapters' for a list of the chapters of the GAP help system. Enter '?Copyright' for the terms under which you can use and copy GAP. In each case do *not* enter the single quotes(') , they are used in help sections only to delimit text that you actually enter. gap> [gap3r4p0]< 15 > bin/gap -b -n -m 4 -l lib/ -h doc/ gap> ? Syntax error: expression expected ? ^ > ----------- Another question - with the manual growing several hundred pages every release, it's getting hard to even know what is even available. Has anyone written a converter to info? Such a format would make it easy to browse the manual. -- Steve Fisk Department of Mathematics 207-725-3574 Bowdoin College fisk@bowdoin.edu Brunswick, Me. 04011 USA From eamonn.obrien@maths.anu.edu.au Tue Jul 26 23:21:00 1994 From: "Eamonn O'Brien" Date: Tue, 26 Jul 94 23:21 +1000 Subject: MeatAxe package of GAP 3.4 I'm using the MeatAxe package in GAP 3.4 and have computed a submodule lattice using the Lattice command. I now use the following command to see the basis for one of the submodules computed: gap> B := GeneratorsSubmodule (L, 6); MeatAxeMat( "/usr/tmp/aaaa09933/c/g.s5", GF(5^2), [ 4, 16 ] ) gap> Display (B); MeatAxe.Matrix := [ [0*Z(25),0*Z(25),0*Z(25),0*Z(25),0*Z(25),0*Z(25),0*Z(25),0*Z(25),0*Z(25),0*Z(25), 0*Z(25),0*Z(25),Z(25)^24,0*Z(25),0*Z(25),0*Z(25)] ]; I can display the basis using the Display function. However, I want to assign the basis to a variable back within GAP and work with its vectors. Can anyone advise me how to do this? I'm sure it's trivial and present in the documentation but I can't seem to find it. Thanks, Eamonn From Alexander.Hulpke@Math.RWTH-Aachen.DE Tue Jul 26 16:06:00 1994 From: "Alexander Hulpke" Date: Tue, 26 Jul 94 16:06 +0200 Subject: Missing documentation in GAP 3r4p0 Dear GAP-Forum, due to an error for which I unfortunately cannot blame a computer, part of the new documentation for GAP 3.4 has not been included in the release (while the corresponding code is included). This documentation covers: o The library of transitive groups, o Generic algebraic extensions of fields and o Computation of (isomorphism types) of Galois groups. This documentation will be included in the next patch, that is to be released in the near future. I apologize for this mistake. If anyone is in urgent need of the documentation, I can provide him the corresponding files already now. Alexander Hulpke (Alexander.Hulpke@math.rwth-aachen.de) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In short, the new commands include: TransitiveGroup(deg,nr); Creates a transitive permutation group of the isomorphy type given in Butler/McKay: the transitive groups of degree up to 11, CommAlg 11(1983), 863--911 TransitiveIdentification(grp); if grp is a transitive permutation group of degree d<=11, then this command yields the number of the permutation isomorphy type of grp, i.e. grp ~= TransitiveGroup(d,TransitiveIdentification(grp)). if f is a polynomial over the rationals, then Galois(f); yields the number of the isomorphism type of the corresponding Galois group. (This might take substantial time). ProbabilityShapes(f); return a list of guesses for the isomorphism type of the Galois group. It is much faster, but might be wrong. If f is any polynomial, then AlgebraicExtension(f); creates the corresponding algebraic extension, RootOf(f); the generating element. The base field is naturally embedded. Multiple algebraic extensions are not supported. Polynomial factorization is possible over Algebraic extensions of finite fields or the rationals (as well as over these ground fields themselves)\ by specifying a polynomial over this field and using 'Factor'. Polynomial factorization over the rationals has been possible (but undocumented) already in version 3.3, but this algorithm has been improved significantly in 3.4. From leonard@qmw.ac.uk Tue Jul 26 15:47:00 1994 From: "Leonard Soicher" Date: Tue, 26 Jul 94 15:47 BST Subject: StabChain Dear Forum, Why does Gap feel it is necessary to compute a stabilizer chain for G in order to compute RepresentativeOperation(G,1,pt) ? Regards, Leonard. From dima@maths.uwa.edu.au Tue Jul 26 23:07:00 1994 From: "Dima Pasechnik" Date: Tue, 26 Jul 94 23:07 WST Subject: Re: StabChain > > Dear Forum, > > Why does Gap feel it is necessary to compute a stabilizer chain for G in > order to compute RepresentativeOperation(G,1,pt) ? Most probably, it does not store words in generators of G when it computes Orbit(G,1). Knowing these words would be the way around computing StabChain. Regards, Dima From Frank.Celler@Math.RWTH-Aachen.DE Wed Jul 27 09:30:00 1994 From: "Frank Celler" Date: Wed, 27 Jul 94 09:30 WET Subject: Re: gap 3.4 under emacs Dear Steve, If I use the -n option in gap to prevent echoing in my emacs shell window, then I can not access the help system. Here is what happens: (using emacs 19.22) yes, this is correct. "-n" will prevent all line editing features including history and help. However, there is an EMACS mode "gap-process", written by Michael Smith (Michael.Smith@Pell.ANU.Edu.AU), which might help (the el file is in gap3r4p0/etc). This mode implements "?" with output redirection into another buffer, but there are problems with large help sections. I will try to find out if Michael has already updated his mode. Another question - with the manual growing several hundred pages every release, it's getting hard to even know what is even available. Has anyone written a converter to info? Such a format would make it easy to browse the manual. There was a discussion on that subject some time ago, I will append the relevant mail. It should not be too hard to write such a convert, but at the moment no one in Aachen has enough time to do so. If anyone has already written a convert, please upload it into our incoming directory. If anyone needs information about the structure of the latex files, please contact "Gap-Trouble@Math.RWTH-Aachen.DE". best wishes Frank ============================================================================= Date: Fri, 12 Mar 93 17:18:13 +0100 Comment: GAP Forum Originator: gap-forum@samson.math.rwth-aachen.de Errors-To: martin@samson Reply-To: Sender: gap-forum@samson Version: 5.31 -- Copyright (c) 1991, Anastasios Kotsikonas From: martin@bert.math.rwth-aachen.de ( Martin Schoenert) To: Multiple recipients of list Subject: Re: RE: new GAP for OS/2 with hypertext documentation Arnaldo Mandel writes in his e-mail message of 1993/03/11 One of the things I miss on GAP is good online documentation, fur the unix environment implementation. My favorite choice would be an Emacs info document, although I can survive other formats which allow fast online search (thus, havin the manual online as a .dvi or .ps file will not cut it). Is there any hope that such a thing will ever appear? Maybe this IPF hypertext can be ported. I would like to know which features of GNU EMACS' info mode you miss in GAP's on-line help. I think that both allow roughly the same. 1) You know exactly what you are looking for: In EMACS you use 'g '. In GAP you use '?'. 2) You know roughly what you are looking for: In EMACS you go to one of the indices (say with 'g concept index'), find the most likely candidate and with 'm ' you go there. In GAP you use '??', select the most likely candidate and with '?' you go there. 3) You want to browse around in the manual: In EMACS you go to the top node, select a section and go there with 'm
'. In the section you again use 'm ' to go to the next subsection. In GAP you say '?chapters', select a chapter and go there with '?'. Then you read the first section of the chapter and find references (of the form (see "
")) to all the sections in this chapter. Then you again use '?
' to go to the section you are interested in. 4) You want to go to the next or previous node/section: In EMACS you use 'n' and 'p'. In GAP you use '?>' and '?<'. 5) You want to go from a subsection to a section: In EMACS you use 'u'. In GAP you use '?<<'. 6) You want to go from a subsection to the next node section: In EMACS you use 'u' and 'n'. In GAP you use '?>>'. 7) You want to follow a cross reference. In EMACS you use 'f '. In GAP cross references are again of the form (see "
") and you use '?
'. 8) You want to go to the last section that you visited before the current one: In EMACS you use 'l'. In GAP you use '?-'. One feature I like in David Gillespie's enhanced EMACS's info mode (it is not in the standard info mode) that is missing in GAP is the function ','. With 'i' you first specify an pattern. Then ',' lets you visit in turn all nodes that have index entries that match this pattern. One feature I dislike in EMACS' info mode is that I still find it difficult to decipher the information at the top of each node which should tell me where I am. I find GAP's top line much easier to read. David Sibley replied in his e-mail message of 1993/03/11 Eh? I find the GAP online documentation to be excellent. It's much faster and more efficient than anything I ever experienced with EMACS info files, where you have to know where an item is in the heirarchy. "excellent": why, thank you. "faster": I don't think so. In EMACS a special file (info-file) is generated from the TeX manual. This file contains information that allows EMACS' info mode to go very fast from node to node. In GAP the online help always works from the original LaTeX files. To find a node it has to search the 'manual.toc' file, open the chapter file, search linearly to the section, etc. It seems to be fast enough though. Lee Schumacher replied in his e-mail message of 1993/03/11 The ? and ?? are quite useful, its true, but hardly a substitute for a real structured info tree. The problem with the GAP facilities is that you need to know the NAME of the function or concept before you can find it. Of course the topic of discourse in GAP is sufficiently narrow that this is not a problem in general. However I did read the manual off line first and now ? is useful more as a memory jogger. Note that emacs info files are intended more for learing new concepts and groups of commands or functions. If you just want to find a command and you have a pretty good idea what the name is then you use apropos, which provides all of the functionality of ? and ??. I argue that the GAP manual is tree structured (into chapters and sections), and that the online help allows you to search through this structure. In the online help the top node is '?chapters', with references to the first sections of all chapters. And the first section of each chapter contains references (of the form (see "
")) of all the sections of this chapter. So the tree is quite shallow (of depth 2, except in "Group", where it has depth 3), but it's a tree nevertheless. The chapter that you get with '?About GAP' is certainly not a reference manual. It's main purpose is to learn about the (new) concepts in GAP. I know that not all sections of this chapter are easily read online, but the first few certainly are. Arnaldo Mandel replied in his email of 1993/03/11 I don't [find GAP's online help more convenient than EMACS' info]. But the whole discussion is boiling down to a matter of personal preferences. Since I live most of the time within emacs, and maintain it here, it is perhaps natural that I have become addicted to info. On the other hand, I will retract my complaints about lack of "good online documentation" (I had no intention of putting down ? and ??), and qualify it instead as a "lack of an online manual of the kind *I* find convenient". Now, perhaps I would have kept to myself about info, if it wasn't for the circunstance that a hypertext version of GAP documentation had been created, for another plataform. The source code for GAP shows that emacs was a heavily used tool for development; maybe the developers of GAP would have something to say on this matter. I havn't ever used OS/2's IPF. Also Hypertext is such a buzzword. Could somebody enligthen me about IPF's features? I use EMACS a lot. Actually I probably would be lost without EMACS.I don't think it would be too difficult to make a TeXinfo manual for GAP, but we are certainly not considering it in the moment. (I don't miss a GAP info-file for EMACS, but then I probably have to use the manual less often than others ;-). Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany From leonard@qmw.ac.uk Wed Jul 27 08:52:00 1994 From: "Leonard Soicher" Date: Wed, 27 Jul 94 08:52 BST Subject: RepresentativeOperation suggestion Dear Forum, I suggest the following default strategy for calculating RepresentativeOperation(G,x,y,action); The idea is to build up two partial Schreier trees Tx, Ty (w.r.t. G.generators), rooted at x and y, respectively. One alternately adds nodes to Tx and Ty until they have a node z, say, in common (if one of the trees is completed and there is no such node then return false). Given such a z, one uses Tx,Ty in the usual way to get elements gx,gy such that z=action(x,gx)=action(y,gy), and so the required element taking x to y is gx/gy. If x and y are in the same G-orbit, then this approach should be much faster than computing an orbit for x until y is found, and much much faster than trying to compute a StabChain if the action is OnPoints. Regards, Leonard Soicher. From Frank.Celler@Math.RWTH-Aachen.DE Wed Jul 27 09:58:00 1994 From: "Frank Celler" Date: Wed, 27 Jul 94 09:58 WET Subject: Re: MeatAxe package of GAP 3.4 Dear Eamonn, However, I want to assign the basis to a variable back within GAP and work with its vectors. is the function 'GapObject' for MeatAxe objects what you need? For example: gap> mat1 := MeatAxeMat( PermutationMat( (1,2,3), 3, GF(2) ), GF(2) );; gap> mat2 := MeatAxeMat( PermutationMat( (1,2), 3, GF(2) ), GF(2) );; gap> m := NaturalModule( Algebra( GF(2), [ mat1, mat2 ] ) );; gap> l := Lattice(m);; gap> b := GeneratorsSubmodule( l, 3 ); MeatAxeMat( "/var/tmp/tmp.014092/o/g.s2", GF(2), [ 2, 3 ] ) gap> Display(b); MeatAxe.Matrix := [ [1,0,1], [0,1,1] ]*Z(2); gap> GapObject(b); [ [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ 0*Z(2), Z(2)^0, Z(2)^0 ] ] best wishes Frank From Frank.Celler@Math.RWTH-Aachen.DE Wed Jul 27 10:32:00 1994 From: "Frank Celler" Date: Wed, 27 Jul 94 10:32 WET Subject: Re: operations query Dear Andrew, Here is a simple question which must have a simple answer. I have defined FLT seems to prove the opposite. Unfortunately the same is true for your problem. function for these elements so I wrote a Ops.Length function which of course doesn not work. Evidiently functions like "Print", "+" and so on 'Length' only works for GAP lists, there is no way (*, at the moment) to use it together with records. This behaviour might be considered a bug or an annoying feature and it is possible that this will be changed in future releases (GAP 4.0). Do you want to create a new type of lists or just a new type of objects? In the latter case it might help to use 'Size' instead of 'Length'. Incidently, unless I have missed it the description of such The description is in "Operations for Records" and the following sections. things does not appear to be in the manual. Similarly for the use of "arg" in function definitions. Are these documented anywhere? See "Function Calls". But yes, it is easy to miss something in >1000 pages. We try to reorganise the manual, but this is a *major* project. best wishes Frank == * = short of defining a dispatcher for Length in GAP, which will slow down almost all computations. From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Jul 27 11:12:00 1994 From: "Martin Schoenert" Date: Wed, 27 Jul 94 11:12 +0100 (MET) Subject: Re: operations query Andrew Mathas writes in his e-mail message of 1995/07/25 Here is a simple question which must have a simple answer. What makes you think that a simple question must have a simple answer? After all there are lots of simple questions in mathematics that don't seem to have simple answers. And we try to model mathematics as close as possible with GAP ;-) He continues I have defined a record which has the form: rec (elt := a list, operations := Ops, ...) where Ops := rec (...). Inside the operations are various functions defining printing for the record, addition, and so on. I wanted to add a Length function for these elements so I wrote a Ops.Length function which of course doesn not work. Evidiently functions like "Print", "+" and so on are handled differently than other functions. So how do I add a Length function to this record? That is true. Only functions and operations that are generally applied to domains use the dispatching mechanism through the operations record. Functions that are usually applied to one (or more) of the basic types (as provided by the kernel), e.g., integers, lists, permutations, etc., are not dispatched. Luckily it is not difficult to work around this. Simply write OLDLength := Length; Length := function ( obj ) if IsList( obj ) then return OLDLength( obj ); else return obj.operations.Length( obj ); fi; end; The problem of course is that this makes 'Length' slower for ``standard'' case. Since 'Length' is used quite a lot in the library, this will slow down everything. I can't say how much, but if you try it, I'd like to see your results. He continues Incidently, unless I have missed it the description of such things does not appear to be in the manual. Similarly for the use of "arg" in function definitions. Are these documented anywhere? The general description is in the section "Dispatchers". The sections for the dispatchers contain paragraphs like the following 'Orbit' calls \\ '.operations.Orbit( , , )' \\ and returns the value. Note that the third argument is not optional for functions called this way. But this is not done consistently in the manual, so if you find a section without such a paragraph, it doesn't mean that the function is not a dispatcher. In section "Function Calls" you will find An exception again occurs if the function has only one formal argument with the name 'arg'. In this case the values of all the actual arguments are stored in a list and this list is assigned to the new variable corresponding to the formal argument 'arg'. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Jul 27 11:36:00 1994 From: "Martin Schoenert" Date: Wed, 27 Jul 94 11:36 +0100 (MET) Subject: Re: gap 3.4 under emacs Steve Fisk writes in his e-mail message of 1994/07/25 If I use the -n option in gap to prevent echoing in my emacs shell window, then I can not access the help system. Here is what happens: (using emacs 19.22) The option '-n' tells GAP that the standard input 'stdin' is not a terminal, and that GAP cannot switch it to raw mode. This is necessary, because otherwise EMACS and GAP both echo all the input characters. However GAP needs the input in raw mode for the help, because it expects the raw as answer to '-- for more --'. It would be possible to fix that, but the easiest solution for now is probably the GAP mode for EMACS that comes with the standard distribution in 'gap3r4p0/etc/'. He continues Another question - with the manual growing several hundred pages every release, it's getting hard to even know what is even available. Has anyone written a converter to info? Such a format would make it easy to browse the manual. It would probably not be too difficult to write such a converted. But the real problem is, I think, not the mechanism to read the manual. It is the manual itself. The size of the manual is simply ridiculous. We are planning a major rewrite for GAP 4, which hopefully will make the manual much more accessible. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From leonard@qmw.ac.uk Thu Jul 28 12:45:00 1994 From: "Leonard Soicher" Date: Thu, 28 Jul 94 12:45 BST Subject: the StabChain function Dear Forum, The new StabChain function in Gap 3.4 is very useful for my work on graphs and geometries, since I often know the size of a given group acting on a graph. However, sometimes I only know an upper bound, and was pleased to see that StabChain offers the option of specifying this upper bound through the limit parameter. I was disappointed, however, to find that with this option, StabChain appears to take as long as when given no extra information, even when this upper bound is achieved. Please tell me how to fix this! Best regards, Leonard Soicher. P.S. Log file illustrating this. Timings are for a Sparc 2. [... stuff deleted ...] gap> C:=Combinations([1..12],4);; gap> G:=Operation(SymmetricGroup(12),C,OnSets);; gap> Length(C); 495 gap> H:=Copy(G);; gap> Runtime(); 275433 gap> StabChain(H);; gap> Runtime(); 390066 gap> H:=Copy(G);; gap> Runtime(); 390133 gap> StabChain(H,rec(size:=Factorial(12)));; gap> Runtime(); 397816 gap> H:=Copy(G);; gap> Runtime(); 397866 gap> StabChain(H,rec(limit:=Factorial(12)));; gap> Runtime(); 514183 gap> quit; From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Jul 28 14:33:00 1994 From: "Martin Schoenert" Date: Thu, 28 Jul 94 14:33 +0100 (MET) Subject: Re: the StabChain function Leonard Soicher writes in his e-mail message of 1994/07/28 The new StabChain function in Gap 3.4 is very useful for my work on graphs and geometries, since I often know the size of a given group acting on a graph. However, sometimes I only know an upper bound, and was pleased to see that StabChain offers the option of specifying this upper bound through the limit parameter. I was disappointed, however, to find that with this option, StabChain appears to take as long as when given no extra information, even when this upper bound is achieved. Please tell me how to fix this! The 'limit' option is currently only honoured by the random method. The default however is the deterministic method. The easiest solution is to force using the random method. You do this with the 'random' option, using any value less than 1000. gap> C := Combinations( [1..12], 4 );; gap> G := Operation( SymmetricGroup(12), C, OnSets );; gap> StabChain( Copy(G), rec( random := 1000, limit := Factorial(12) );; gap> time; 62353 gap> StabChain( Copy(G), rec( random := 999, limit := Factorial(12) );; gap> time; 4867 gap> StabChain( Copy(G), rec( random := 1000, limit := Factorial(13) );; gap> time; 62524 gap> StabChain( Copy(G), rec( random := 999, limit := Factorial(13) );; gap> time; 64566 Of course there is a small chance that the random method will fail. But with 'random := 999', it is extremly small. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Jul 28 15:37:00 1994 From: "Martin Schoenert" Date: Thu, 28 Jul 94 15:37 +0100 (MET) Subject: Re: StabChain Leonard Soicher writes in his e-mail message of 1994/07/26 Why does Gap feel it is necessary to compute a stabilizer chain for G in order to compute RepresentativeOperation(G,1,pt) ? I just looked at the code. Superficially it appears to be the result of a mixture of stupidity and laziness. In truth however, I used the most stupid and wastefull method I could think of, to see how long it would go undetected ;-). Leonard continues in his e-mail message of 1994/07/27 I suggest the following default strategy for calculating RepresentativeOperation(G,x,y,action); The idea is to build up two partial Schreier trees Tx, Ty (w.r.t. G.generators), rooted at x and y, respectively. One alternately adds nodes to Tx and Ty until they have a node z, say, in common (if one of the trees is completed and there is no such node then return false). Given such a z, one uses Tx,Ty in the usual way to get elements gx,gy such that z=action(x,gx)=action(y,gy), and so the required element taking x to y is gx/gy. If x and y are in the same G-orbit, then this approach should be much faster than computing an orbit for x until y is found, and much much faster than trying to compute a StabChain if the action is OnPoints. It is not clear to me that this is indeed a win. Let us assume that the group operates transitively on $n$ points and that it has only a small number $k$ of generators. Then computing the entire orbit an the corresponding Schreier tree takes time $O( n k )$. Your method on the other hand would usually take time $O( n^(1/2) k )$ (the worst case is of course also $O( n k )$. However, I think that in most cases the total time will anyhow be dominated by the time it takes to multiply together the representative. Namely, under favourable conditions the pathlength from $x$ to $y$ in this tree will be $O( log(n) )$, so the cost of computing the representative is $O( n log(n) )$. So your method would not be faster unless $k >> log(n)$. This is only theory of course, and I haven't yet investigated this in practice. It might well be that the constant for the orbit computation is so much higher that the constant for the representative computation (most of which is multiplying permutations, and this is done in the kernel), that your method is still practically better. However, there is even a practical argument against your method. Namely assume that a user makes multiple calls to 'RepresentativeOperation', maybe with fixed 'x' but varying 'y'. With the straightforward orbit computation one could compute the orbit once and then remember it, so that subsequent calls to 'RepresentativeOperation' do not have to recompute it. With your method it is not clear how to do this, so that the total time for all tree computations never exceeds $O( n k )$. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From sl25@cus.cam.ac.uk Thu Jul 28 15:50:00 1994 From: "Steve Linton" Date: Thu, 28 Jul 94 15:50 +0200 Subject: Re: StabChain > Leonard continues in his e-mail message of 1994/07/27 > > I suggest the following default strategy for calculating > > RepresentativeOperation(G,x,y,action); > > The idea is to build up two partial Schreier trees Tx, Ty (w.r.t. > G.generators), rooted at x and y, respectively. One alternately > adds nodes to Tx and Ty until they have a node z, say, in common (if > one of the trees is completed and there is no such node then return > false). Given such a z, one uses Tx,Ty in the usual way to > get elements gx,gy such that z=action(x,gx)=action(y,gy), > and so the required element taking x to y is gx/gy. > > If x and y are in the same G-orbit, then this approach should be > much faster than computing an orbit for x until y is found, and > much much faster than trying to compute a StabChain if the action is > OnPoints. > > It is not clear to me that this is indeed a win. Let us assume that the > group operates transitively on $n$ points and that it has only a small > number $k$ of generators. > > Then computing the entire orbit an the corresponding Schreier tree takes > time $O( n k )$. Your method on the other hand would usually take time > $O( n^(1/2) k )$ (the worst case is of course also $O( n k )$. > > However, I think that in most cases the total time will anyhow be > dominated by the time it takes to multiply together the representative. > Namely, under favourable conditions the pathlength from $x$ to $y$ in > this tree will be $O( log(n) )$, so the cost of computing the > representative is $O( n log(n) )$. > This is only so if the action is on points. Suppose that we consider a permutation group of small degree acting on a large orbit of sets or tuples, or a matrix group of small degree acting on vectors or subspaces. Then the time for a multiplication is much less than n. > > However, there is even a practical argument against your method. Namely > assume that a user makes multiple calls to 'RepresentativeOperation', > maybe with fixed 'x' but varying 'y'. With the straightforward orbit > computation one could compute the orbit once and then remember it, so > that subsequent calls to 'RepresentativeOperation' do not have to > recompute it. With your method it is not clear how to do this, so that > the total time for all tree computations never exceeds $O( n k )$. > I suggest using Leonard's method for all actions except 'OnPoints'. For OnPoints the long-term advantage of computing and remembering a Schreier tree for an entire orbit makes it worthwhile doing so. Steve From leonard@qmw.ac.uk Thu Jul 28 15:14:00 1994 From: "Leonard Soicher" Date: Thu, 28 Jul 94 15:14 BST Subject: Re: the StabChain function Many thanks for the quick reply, Martin. Will the following work if I want a provably correct result (when mylimit is a proven upper bound on the size of G)? H:=ShallowCopy(G); StabChain(H,rec(random:=800; # or whatever limit:=mylimit); if Size(H) = mylimit then G := H; else StabChain(G); fi; Does StabChain ever change an existing component of the group record; that is, should I make a Copy instead of a ShallowCopy in the first line? Regards, Leonard. From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Jul 28 16:11:00 1994 From: "Martin Schoenert" Date: Thu, 28 Jul 94 16:11 +0100 (MET) Subject: Re: Re: the StabChain function Leonard Soicher writes in his e-mail message of 1994/07/28 Many thanks for the quick reply, Martin. My pleasure. He continues Will the following work if I want a provably correct result (when mylimit is a proven upper bound on the size of G)? H:=ShallowCopy(G); StabChain(H,rec(random:=800; # or whatever limit:=mylimit); if Size(H) = mylimit then G := H; else StabChain(G); fi; Assuming that either 'G' has no stabilizer chain at the beginning or a provable correct one. If 'G' has an incorrect stabilizer chain at the beginning all the calls to 'StabChain' wont change it. So in this case the result will also be incorrect. Otherwise this is fine. He continues Does StabChain ever change an existing component of the group record; that is, should I make a Copy instead of a ShallowCopy in the first line? 'StabChain' only touches 'G.stabChain', 'G.orbit', 'G.stabilizer', and 'G.transversal'. If 'G' has no stabilizer chain initially, then using 'ShallowCopy' is save. If 'G' has a stabilizer chain, the best is to use 'ShallowCopy' and then to 'Unbind' the above four entries. There is even a function for this, namely 'ShallowCopyNoSC', but this function is not likely to survive for long. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Frank.Celler@Math.RWTH-Aachen.DE Thu Jul 28 19:12:00 1994 From: "Frank Celler" Date: Thu, 28 Jul 94 19:12 WET Subject: various installation problems Dear Forum, the following list describes possible solutions to various problems which might occur while installing GAP 3.4 Patchlevel 0. Please send any further questions to "Gap-Trouble@Math.RWTH-Aachen.DE". Problem 1: ibm pc, ms-dos, share libraries ------------------------------------------ 'RequirePackage' reports "Error, share library is not installed" but I have installed the corresponding share library in "gap3r4p0/pkg". Solution 'ReadPkg' has a problem with the directory separators '\\' used in MS-DOS. In order to fix this problem change the start up script "gap.bat". Replace the last line ... -m %GAP_MEM% -l %GAP_DIR%\lib\ -h %GAP_DIR%\doc\ %1 ... by ... -m %GAP_MEM% -l %GAP_DIR%/lib/; -h %GAP_DIR%\doc\ %1 ... The C-Compiler DJGPP used to compile GAP under MS-DOS automatically translates '/' to '\\' in path names. Problem 2: dec alpha, osf1, gap ------------------------------- My compiled version of GAP does not run correctly on a DEC Alpha. Solution The version of GASMAN, the GAP storage mananger, used for GAP 3.4 is not 64bit safe. In order to use GAP on a DEC Alpha you have to translate a DEC Ultrix executable using mx. A translated executable can be found in "ftp.math.rwth-aachen.de:/pub/gap/bin/bin3r4p0-dec-alpha-osf1.zoo". Problem 3: dec alpha, osf1, xgap -------------------------------- I cannot compile XGAP on a DEC Alpha because make reports "Don't know how to make xcmds.c. Stop." but "xcmds.c" is there. I cannot compile XGAP because there is no target for DEC Alpha in the makefile. Solution Use gnumake. The following command will compile XGAP gnumake xgap CC=cc CFLAGS="-I/usr/include -O -DSYS_HAS_UNISTD \ -DSYS_HAS_STDARG" LDFLAGS=" -L/usr/lib" Alternatively you can get XGAP from our ftp server. An executable can be found in "ftp.math.rwth-aachen.de:/pub/gap/bin/xgap1r2-dec-alpha-osf1.zoo". Problem 4: any unix, anu sq --------------------------- I can compile the ANU Sq but the linker complains about a missing '_RunTime'. Solution Unfortunately the GAP archive contains an old Makefile for the ANU Sq. Try the following commands to compile the Sq under Berkeley UNIX: make bsd-gcc COPTS=-DSYS_BSD make bsd-cc COPTS=-DSYS_BSD To compile the Sq under System V UNIX try: make usg-gcc COPTS=-DSYS_USG make usg-cc COPTS=-DSYS_USG best wishes Frank From clacombe@jade.tufts.edu Fri Jul 29 10:40:00 1994 From: "Carl A. LaCombe" Date: Fri, 29 Jul 94 10:40 -0400 Subject: Re: GAP version 3 release 4 finally release Hi, I have been wondering what the status of the stand-alone version of GAP for the Mac is? My department will be getting a DEC Alpha soon so I'll be able to use GAP on that (I hope), but up to now I have been using MacGAP, which is only updated to version 3.2. This is just a request for information. I know that everyone has been busy developing 3.4. -cal From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Jul 29 18:01:00 1994 From: "Martin Schoenert" Date: Fri, 29 Jul 94 18:01 +0100 (MET) Subject: Re: Re: StabChain I wrote in my e-mail message of 1994/07/28 ...about computing a representative that takes x to y... However, I think that in most cases the total time will anyhow be dominated by the time it takes to multiply together the representative. Namely, under favourable conditions the pathlength from $x$ to $y$ in this tree will be $O( log(n) )$, so the cost of computing the representative is $O( n log(n) )$. Steve Linton answered in his e-mail message of 1994/07/28 This is only so if the action is on points. Suppose that we consider a permutation group of small degree acting on a large orbit of sets or tuples, or a matrix group of small degree acting on vectors or subspaces. Then the time for a multiplication is much less than n. For the operation on tuples you use a stabilizer chain. That is you first find a representative r_1 that moves x[1] to y[1]. In the stabilizer of x[1] you then look for a representative r_2 that moves x[2] to y[2]^(r_1^-1). Then the product r_2 r_1 takes x[1] to y[1] and x[2] to y[2]. Iterate and serve. Ignoring the time to compute a stabilizer chain this has cost $O( n l )$, where l is the number of points in the tuples. The running time for Leonard's method depends on the length of the orbit that G makes on the tuples, but in the worst case the length could be $O( n ^ l )$ and the average running time would be $O( n ^ (l/2) )$. For the operation on sets you use backtrack. It is not so easy to estimate the running time for this backtrack. But Leonard's method has again a pretty bad worst case estimate. Of course the general comment is true. My analysis was only valid under the assumption that the operation is one of a permutation group on points. If the length of the orbit is not bound by n or the time to compute one image is not constant, Leonard's method will probably be superior. However, as the above shows, for some other operations one can do even better, if one is willing to compute a stabilizer chain. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Jul 29 20:35:00 1994 From: "Martin Schoenert" Date: Fri, 29 Jul 94 20:35 +0100 (MET) Subject: Re: Re: GAP version 3 release 4 finally release Carl A. LaCombe writes in his e-mail message of 1994/07/29 I have been wondering what the status of the stand-alone version of GAP for the Mac is? My department will be getting a DEC Alpha soon so I'll be able to use GAP on that (I hope), but up to now I have been using MacGAP, which is only updated to version 3.2. We finally have a working stand-alone version of the 3.3 kernel. Over the next few days we will make the appropriate changes to 3.4. Since very little has changed between 3.3 and 3.4 in the kernel, this should not pose any difficulties. So hopefully a standalone version of 3.4 will be available in a week. I will keep everybody informed. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Jul 29 20:53:00 1994 From: "Martin Schoenert" Date: Fri, 29 Jul 94 20:53 +0100 (MET) Subject: Re: various installation problems Frank Celler writes in his e-mail message of 1994/07/29 Problem 3: dec alpha, osf1, xgap -------------------------------- I cannot compile XGAP on a DEC Alpha because make reports "Don't know how to make xcmds.c. Stop." but "xcmds.c" is there. I cannot compile XGAP because there is no target for DEC Alpha in the makefile. Solution Use gnumake. The following command will compile XGAP gnumake xgap CC=cc CFLAGS="-I/usr/include -O -DSYS_HAS_UNISTD \ -DSYS_HAS_STDARG" LDFLAGS=" -L/usr/lib" Alternatively you can get XGAP from our ftp server. An executable can be found in "ftp.math.rwth-aachen.de:/pub/gap/bin/xgap1r2-dec-alpha-osf1.zoo". The first problem is that 'unzoo' unpacks all the files with the strange date '1969/12/31'. 'make' thinks that this is so old, the files could not possible exist. 'touch'-ing all the files in the source directory should solve that problem. Then you can use 'make' instead of 'gnumake'. You still have to explicitly specify 'CC', 'CFLAGS', and 'LDFLAGS' tough. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Aug 01 14:08:00 1994 From: "Volkmar Felsch" Date: Mon, 01 Aug 94 14:08 +0200 Subject: Re: Words for secondary generators Tim Hsu writes: > I've been trying to set up a calculation using AugmentedCosetTableRrs. > Now, when you have the statement > > aug := AugmentedCosetTableRrs(G,ct,2,"_q"); > > (ct is the coset table for a subgroup S in G), > aug.primaryGeneratorWords contains descriptions of the primary > generators of S in terms of words in the generators of G. According > to the GAP manual, aug.tree, (in some form) contains a description of > the secondary generators of S in terms of the primary relators, so in > theory, you should be able to obtain the secondary generators of S in > terms of words in G. Could someone tell me how to get this from the > tree? Whenever you call the command aug := AugmentedCosetTableRrs( G, ct, 2, string ); it will return a record with a component "aug.tree" which is a list of length 5. (Note that the structure represented by that list is not a tree in mathematical sense; the name has historical reasons.) The entries of this list are tree[1] = tree1 (a list of length treelength), tree[2] = tree2 (a list of length treelength), tree[3] = treelength = total number of all generators, tree[4] = numgens = number of primary generators, tree[5] = type = 2. The two lists "tree1" and "tree2" are in parallel to the list "gen", say, of all generators which is ordered such that gen[1] to gen[numgens] are the primary generators whereas gen[numgens+1] to gen[treelength] are the secondary generators. Each of the secondary generators has originally been defined as a product of two preceding generators (with respect to that list) or their inverses. The purpose of the tree is to save these definitions. For numgens < i <= treelength, we have gen[i] = factor(tree1[i]) * factor(tree2[i]) where factor(j) = gen[j] for j > 0, factor(j) = gen[-j]^-1 for j < 0. You may use the tree to recursively express each secondary generator as a word in the preceding ones and finally in the primary generators, but I would like to warn you of the fact that the length of these words tends to become very huge so that they soon may get unhandable. > My next question is, do RewriteSubgroupRelators, > PresentationAugmentedCosetTable, TzGo, or FpGroupPresentation change > the ordering of the generators in any way, other than eliminating > generators? Thanks very much. I think that none of these commands will reorder the list of subgroup generators by swapping any pair of generators. This answer is to the best of my recollection, but as it is long ago that I wrote the programs I would not like to swear on it. If you want to be absolutely sure, please check the code which for such purposes is given in full source. Moreover, I would not like to guarantee this for all future. We may at some time have reasons to change this. This is, in fact, the reason why no guarantee of this kind has been made in the manual. What frequently happens in the present program, is that the subgroup generators are internally renumbered after elimination processes in order to get rid of the gaps in the numbering. The names of the generators are not changed by this process. Example: gap> F := FreeGroup( "a", "b" );; gap> a := F.1;; b := F.2;; gap> G := F / [ a^2, b^4, (a*b)^7, Comm(a,b)^5, (a*b*a*b^2*a*b^-1)^3 ];; gap> H := Subgroup ( G, [ G.1^G.2, G.2^(G.1*G.2^-1*G.1) ] );; gap> T := PresentationSubgroupRrs( G, H ); << presentation with 5 gens and 12 rels of total length 64 >> gap> TzPrintGenerators( T ); #I 1. _x1 11 occurrences involution #I 2. _x2 12 occurrences involution #I 3. _x3 16 occurrences involution #I 4. _x4 11 occurrences #I 5. _x5 14 occurrences involution gap> TzGo( T ); #I there are 3 generators and 8 relators of total length 94 gap> TzPrintGenerators( T ); #I 1. _x2 26 occurrences involution #I 2. _x4 43 occurrences #I 3. _x5 25 occurrences involution If you have questions about still more technical details, please feel free to ask, but perhaps we should then discuss this privately, not in the forum. Volkmar Felsch (Aachen) From leonard@qmw.ac.uk Wed Aug 03 13:03:00 1994 From: "Leonard Soicher" Date: Wed, 03 Aug 94 13:03 BST Subject: Re: Re: the StabChain function Martin Schoenert writes: > >'StabChain' only touches 'G.stabChain', 'G.orbit', 'G.stabilizer', and >'G.transversal'. > What about 'G.stabChainOptions'? Regards, Leonard. From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Aug 04 12:57:00 1994 From: "Martin Schoenert" Date: Thu, 04 Aug 94 12:57 +0100 (MET) Subject: Re: Re: Re: the StabChain function 'StabChain' looks at 'G.stabChainOptions', but doesn't modify this record. But since it is one of the records, which are explicitly made public, and may be changed by the user, it is probably best to unbind that too. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From sl25@cus.cam.ac.uk Thu Aug 04 13:02:00 1994 From: "Steve Linton" Date: Thu, 04 Aug 94 13:02 +0200 Subject: From sci.math.symbolic -------------------- As requested I am reposting this in the interest of (a) broader distribution and (b) making sure that the computational pure mathematicians get heard. Steve [I am posting this in the interest of broader distribution. Please send any responses to math-sw-survey@gnu.ai.mit.edu, NOT to me.] ---------------------------------------------------------------------------- [ Please repost this wherever you think is appropriate! ] Project GNU of the Free Software Foundation is conducting a survey to determine the kinds of mathematical software commonly utilized by scientists and mathematicians. Your answers will help us to determine the programming tasks we present to our volunteers. This will ultimately result in a more complete set of math programs and subroutines available as free software. Please answer the following questions with regard to scientific, mathematical, and/or statistical software: 1. What packages are commonly used? 2. What programs and subroutines are desired, but not available? 3. What freeware currently exists? 4. Where else can we ask these questions? Please give as much detail as you can, including package name, author, language, and where it can be found. Send responses to math-sw-survey@gnu.ai.mit.edu Thank you! ---------------------------------------------------------------------------- From leonard@qmw.ac.uk Thu Aug 04 16:08:00 1994 From: "Leonard Soicher" Date: Thu, 04 Aug 94 16:08 BST Subject: Re: Re: Re: the StabChain function > >'StabChain' looks at 'G.stabChainOptions', but doesn't modify this record. This was not so according to my experiments, but perhaps I was doing something illegal. >But since it is one of the records, which are explicitly made public, and >may be changed by the user, it is probably best to unbind that too. > I think I will just make a proper copy of the group. I don't really like tinkering with record fields of GAP objects anyway. Is it possible in future patches/releases of GAP that if StabChain(G,rec(limit:=mylimit)) is called then the function tries a random method for a while, and then if mylimit is not achieved, switches to a deterministic method ? Best regards, Leonard. From akos@math.ohio-state.edu Thu Aug 04 11:24:00 1994 From: "Akos Seress" Date: Thu, 04 Aug 94 11:24 -0400 Subject: Re: Re: Re: the StabChain function `StabChain' may modify the record element grp.stabChainOptions: namely, grp.stabChainOptions.random and grp.stabChainOptions.knownBase . -- Akos From r.a.fenn@sussex.ac.uk Fri Aug 05 12:03:00 1994 From: "Roger A Fenn" Date: Fri, 05 Aug 94 12:03 +0200 Subject: Re: From sci.math.symbolic > > -------------------- > > As requested I am reposting this in the interest of (a) broader > distribution and (b) making sure that the computational pure > mathematicians get heard. > > Steve > > > > > [I am posting this in the interest of broader distribution. Please send > any responses to math-sw-survey@gnu.ai.mit.edu, NOT to me.] > > ---------------------------------------------------------------------------- > [ Please repost this wherever you think is appropriate! ] > > Project GNU of the Free Software Foundation is conducting a survey to > determine the kinds of mathematical software commonly utilized by scientists > and mathematicians. Your answers will help us to determine the programming > tasks we present to our volunteers. This will ultimately result in a more > complete set of math programs and subroutines available as free software. > > Please answer the following questions with regard to scientific, > mathematical, and/or statistical software: > > 1. What packages are commonly used? I use plain TeX all the time, microemacs as an editor, linnux, postsript, xfig, (does e-mail count?), maple sometimes and I plan to use GAP when I can get round to it. > > 2. What programs and subroutines are desired, but not available? > A better interface of microemacs with linnux, at least I dont know where to get one. A user friendly interface with musicTeX!!!??? > 3. What freeware currently exists? Bernhard Rauscher has written a beautiful package to do commuting diagrams in TeX. > > 4. Where else can we ask these questions? Dunno. Dunno who youve asked already. > > Please give as much detail as you can, including package name, author, > language, and where it can be found. > > Send responses to math-sw-survey@gnu.ai.mit.edu > > Thank you! > ---------------------------------------------------------------------------- > > > > > > > > From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Aug 05 12:47:00 1994 From: "Joachim Neubueser" Date: Fri, 05 Aug 94 12:47 +0200 Subject: Re: From sci.math.symbolic Dear GAP forum members, Roger Fenn has just sent a reply to the request of the GNU group for information about the use of mathematical software to the GAP-forum. That is not the place where such replies should go. Please send them to the address math-sw-survey@gnu.ai.mit.edu as explained in the request (I have forwarded Roger Fenn's answer there). Generally however I want to encourage to support that survey. Joachim Neubueser From r.a.fenn@sussex.ac.uk Fri Aug 05 15:55:00 1994 From: "Roger A Fenn" Date: Fri, 05 Aug 94 15:55 +0200 Subject: Re: From sci.math.symbolic > > Dear GAP forum members, > > Roger Fenn has just sent a reply to the request of the GNU group for > information about the use of mathematical software to the GAP-forum. > That is not the place where such replies should go. Please send them > to the address > > math-sw-survey@gnu.ai.mit.edu > > as explained in the request (I have forwarded Roger Fenn's answer > there). Generally however I want to encourage to support that survey. > > Joachim Neubueser > Sorry about that but I assumed it was just something we replied to. User psychology? Roger Fenn From mas023@bangor.ac.uk Mon Aug 08 12:39:00 1994 From: "Chris Wensley" Date: Mon, 08 Aug 94 12:39 +0000 (GMT) Subject: Group recognition I would welcome information on methods which have been found efficient for recognising groups of small order. I am assuming that some construction has produced a finitely presented group G of order at most 100 (say). The question to be answered is: "which group" is it? It appears that the GAP group libraries do not include a library of groups of small order. If there were such a library, then a selection function of the type OneLibraryGroup(isIsomorphic,G) would do. Is this possible for the 2-Groups library? A permutation representation of minimal degree would be helpful, but this appears to require computation of the subgroup lattice, which may be time-consuming. A list of the normal subgroups is available speedily, so an IsDirectSummand(G,N) function would be helpful. Chris Wensley (UWB, Bangor) From eamonn.obrien@maths.anu.edu.au Mon Aug 08 22:20:00 1994 From: "Eamonn O'Brien" Date: Mon, 08 Aug 94 22:20 +1000 Subject: Re: Group recognition Chris Wensley asks about recognition of small groups. The function "GroupId" present in GAP 3.4 essentially returns the identifier of a group of small order wrt some catalogue. In particular, for a 2-group or 3-group of relevant order, it returns its identifier in the 2- or 3-group library supplied with GAP. Eamonn O'Brien From Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Aug 08 16:40:00 1994 From: "Joachim Neubueser" Date: Mon, 08 Aug 94 16:40 +0200 Subject: Re: Group recognition Chris Wensley wrote: > I would welcome information on methods which have been found efficient > for recognising groups of small order. > > I am assuming that some construction has produced a finitely presented > group G of order at most 100 (say). The question to be answered is: > "which group" is it? > > It appears that the GAP group libraries do not include a library of > groups of small order. They do, see below! Note first that if you really have obtained your group as a finitely presented group, you cannot do many computations with it (cf. section 22.3), you first have to get a faithful permutation representation (e.g. by TC - cf. section 22.5), or a faithful representation as an AG group (e.g. by pQ in case of a p-group, cf. 24.36 or Chapter 56, or some SQ in case of a soluble group of non-p-power order, cf. 55.4) before you can work with it. This assumed, Eamonn O'Brien has already answered your question in particular for the libraries of p-groups (cf. sections 36.7, 36.8 of the manual). There is also a library containing all soluble groups of order up to 100 (cf. section 36.6 of the manual). In Gap 3.4 there is a function identifying the isomorphism type of a given soluble group of order up to 100 by referring to that library. These small groups are simply identified by easily computed invariants, such as the numbers of elements of a given order etc. >If there were such a library, then a selection function of the type > OneLibraryGroup(isIsomorphic,G) > would do. Is this possible for the 2-Groups library? The name of the function is GroupId See 7.62 in the manual, p. 271. > A permutation representation of minimal degree would be helpful, > but this appears to require computation of the subgroup lattice, > which may be time-consuming. Since except for the alternating group all the groups of order less than 100 are soluble it is easier to use the methods that determine the maximal subgroups of soluble groups. For these you have to transform the group into an AG group (cf. 24.26) and thereafter into a 'special AG group' (cf. 25.2) for which the method for finding all maximal subgroups works. The name of the function is 'MaximalSubgroups' It is in 3.4, but not yet in the manual. > A list of the normal subgroups is available speedily, so an > IsDirectSummand(G,N) > function would be helpful. Again for soluble groups it is easier to use the methods for finding all complements: cf. 24.90, function 'Complementclasses', from which you can easily see if there is a normal complement. Hope that answers your questions. Joachim Neubueser From lmccarth%klingon@cs.umass.edu Mon Aug 08 16:44:00 1994 From: "Lewis McCarthy" Date: Mon, 08 Aug 94 16:44 -0400 Subject: Polynomial Factoring / Resultants I'm new to GAP (v3r4) and I have a couple of initial questions which I haven't been able to answer with the manual thus far: (1) Is there any built-in way to compute the resultant of two polynomials ? Judging from the manual, there doesn't appear to be, but I just want to make sure I haven't missed something. Otherwise I'll be coding my own. (2) What algorithms are used to factor polynomials over number fields in GAP ? Thanks for your help -Lewis McCarthy From wright@bright.uoregon.edu Tue Aug 09 10:56:00 1994 From: "Charles.Wright" Date: Tue, 09 Aug 94 10:56 -0500 (EST) Subject: Direct factors and Complementclasses Chris Wensley asked about an "IsDirectSummand" function, and Joachim Neubueser called attention to the Complementclasses function as a way to deal with the question. If I understand correctly, Wensley would like to test whether a given normal subgroup H is a direct factor of G, and if it is, to find at least one direct complement. For small groups, checking the complements to H to see to see if any (or several) are normal is perhaps feasible. For somewhat larger groups, say of order prime^small, one may have a large number of nonnormal complements to contend with. In such a case it may be consider- ably faster to use Complementclasses ( Centralizer (G,H) , Centre (H) ), which produces a list of all direct complements to H in G by looking in the smaller group Centralizer (G,H). To get just one complement, replace Complementclasses by Complement. If only the existence of a direct complement is required, it seems that one has to weigh the cost of computing the Centralizer and Center against the likelihood of hitting a normal complement fairly quickly in a list of all classes of complements to H. Checking whether a given normal subgroup is a direct factor is straight- forward. The question of determining whether G itself is a direct product appears to be considerably more difficult. -- _--_|\ C.R.B. Wright / \ Charles.Wright@maths.anu.edu.au \_.--._/ wright@math.uoregon.edu v From Alexander.Hulpke@Math.RWTH-Aachen.DE Tue Aug 09 11:35:00 1994 From: "Alexander Hulpke" Date: Tue, 09 Aug 94 11:35 +0200 Subject: Re: Polynomial Factoring / Resultants Dear Forum, Lewis McCarthy asked: > I'm new to GAP (v3r4) and I have a couple of initial questions which I > haven't been able to answer with the manual thus far: Unfortunately the manual is (yet) very short-spoken about these subjects, particularly, since the part about algebraic extensions of fields is missing (see my mail in the forum two weeks ago). > (1) Is there any built-in way to compute the resultant of two polynomials ? > Judging from the manual, there doesn't appear to be, but I just want to > make sure I haven't missed something. Otherwise I'll be coding my own. There is a command 'Resultant' that computes the resultant of two polynomials in the same polynomial ring by eliminating the indeterminate of this ring. I.e.: Resultant(f,g) is res_x(f(x),g(x)). For computing resultants of multivariate polynomials, one can use iteraded polynomial ring extensions, however (at the moment) the indeterminate to eliminate must be the "topmost" indeterminate. Also computations in multiple polynomial rings tend to be quite slow. > (2) What algorithms are used to factor polynomials over number fields in GAP ? Since you asked this question, I suppose, you are familiar with the algorithms. Therefore I will keep this description rather short. Feel free to contaxct me personally, if you have further questions, that might be too special for the general audience. Let f be the minimal polynomial for the number field Q(alpha) and g\in Q(alpha)[x] the polynomial to factor. If deg f<=4 and degf*deg g<=20, then Trager's method will be used (factoring the norm). otherwise a Hensel approach is used. For tehse, the methods of Weinberger and Lenstra (the '82 article which is in practice preferable to the method suggested in the '83 article though theoretical complexity bounds might tell something else) are used: If a prime can be found (so far, 6 proimes are tested), modulo which f remains irreducible, then Weinberger's method is used. If not, and the coefficients coefficient bound is less then 10^400, then Lenstras Approach is used. However, if coefficients become even larger, then the LLL will choke on the coefficients (note that Lenstra requires a significant higher bound than ~Weinberger); so Weinbergers methos is used then again (i.e. simultaneous Henmsel lifting for all factors of f and final recombination by Chinese Remainder methods). I have not yet found much references in the literature about how to decide, which methods to use (or how many primes to check). As computations become extremely hard if f will split for al primes it is possibly worth event to try to compute the galois group of f partially to see, whether there is a chance to find a prime, modulo which f will remain irreducible. Th heuristics are based on observations I made with polynomial factorizations needed for identification of galois groups. Those factorizations seem to be quite nasty in general, thus I think the algorithm used should not perform too worse, however I have not yet made sufficient observations to give even a hint, whether these heuristics are well chosen. If you have specific problems on which GAPs algorithmm fails, I can send you some further internal information on how to change the algorithm selection. This text has been written over a rather slow telnet line, so please excuse any typos. > Thanks for your help You're welcome. Alexander Hulpke -- Lehrstuhl D fuer Mathematik, RWTH, Templergraben 64, 52056 Aachen, Germany, eMail: Alexander.Hulpke@math.rwth-aachen.de From t9xu@math.unb.ca Mon Aug 08 12:50:00 1994 From: "Dennis Drapeau, Summer Research Stdnt." Date: Mon, 08 Aug 94 12:50 ADT Subject: [no subject] I would like to know how to save(to disk) the groups that GAP creates so that I do not have to wait for GAP to redo any lengthy computations everytime I start up the program. thank you for your help Dennis Drapeau From sl25@cus.cam.ac.uk Wed Aug 10 11:07:00 1994 From: "Steve Linton" Date: Wed, 10 Aug 94 11:07 +0200 Subject: Re: [no subject] Dennis Drapeau asks: > I would like to know how to save(to disk) the groups that GAP creates so that I > do not have to wait for GAP to redo any lengthy computations everytime I start u > p the program. The simplest thing you can do is use the PrintTo() and AppendTo() functions to print the group to a file. For example: gap> g := Group((1,2)(3,4),(1,3)(2,4)); Group( (1,2)(3,4), (1,3)(2,4) ) gap> PrintTo("filename","g := ",g,";\n"); gap> Unbind(g); gap> g; Error, Variable: 'g' must have a value gap> Read("filename"); gap> g; Group( (1,2)(3,4), (1,3)(2,4) ) gap> quit; 11.820u 2.690s 1:24.83 17.1% 0+3865k 85+4io 83pf+0w {keith:584} cat filename g := Group( (1,2)(3,4), (1,3)(2,4) ); {keith:585} This will work for permutation groups or matrix groups, for example, but not so well for finitely-presented groups. You also lose some of the extra information that GAP can store in the group record, which can take time to recover. Steve From rowe@twain.ee.cornell.edu Wed Aug 10 09:03:00 1994 From: "David Rowe" Date: Wed, 10 Aug 94 09:03 -0400 (EDT) Subject: Re: [no subject] >I would like to know how to save(to disk) the groups that GAP creates so that I >do not have to wait for GAP to redo any lengthy computations everytime I start >up the program. What I've found that works is to take a look at the PrintRec function and the PrintTo function and write a PrintRecTo function by replacing the Print function with the PrintTo function. You will have to adjust the file so when it is read in the record will be set equal to some variable, and the .operations section should be set equal to the proper set of operations. i.e. GraphOps. This can really use up disk space if you have large groups however. Hope this helps, Dave Rowe rowe@ee.cornell.edu From wright@bright.uoregon.edu Thu Aug 11 09:28:00 1994 From: "Charles.Wright" Date: Thu, 11 Aug 94 09:28 -0500 (EST) Subject: Direct Factors -- Addendum I lied slightly in my recent note about direct factors. To determine whether a subgroup H of G is a direct factor, one should, of course, first check that = G before looking for comple- mentary direct factors with Complement(Centralizer(G,H),Centre(H)). -- _--_|\ C.R.B. Wright / \ Charles.Wright@maths.anu.edu.au \_.--._/ wright@math.uoregon.edu v From arques@melq.uab.es Fri Aug 12 10:29:00 1994 From: "Josep M. Arques" Date: Fri, 12 Aug 94 10:29 +0100 Subject: Galois Field I am new to GAP and I am interested in using it to compute in Galois's Fields with a large number of elements. I have found that GAP has te limit of 2^16 elements and I would like to know if there is a way to expand this capability. Also, I would like to know if it is possible to call functions in GAP from other languages (for instance, C). Thank you very much From Frank.Celler@Math.RWTH-Aachen.DE Fri Aug 12 10:58:00 1994 From: "Frank Celler" Date: Fri, 12 Aug 94 10:58 -0700 (PDT) Subject: Re: Galois Field Dear Josep M. Arques, Also, I would like to know if it is possible to call functions in GAP from other languages (for instance, C). do you want to call a GAP function from a C program or a C function from a GAP program? There is no *direct* support for either. The communication between stand-alone programs and GAP uses either files or pipes. The ANU PQ is an example of a stand-alone program which does both: GAP is used to construct a presentation, this presentation is then writen to a file and used as input for a ANU PQ run. During this run the ANU PQ calls GAP (in order to compute orbits) using pipes. The output of the ANU PQ is writen to file and read back into GAP. best wishes Frank From Thomas.Breuer@Math.RWTH-Aachen.DE Fri Aug 12 11:33:00 1994 From: "Thomas Breuer" Date: Fri, 12 Aug 94 11:33 WET Subject: Re: Galois Field Dear Mrs. and Mr. Forum, in his message of today Josep M. Arques writes > I am new to GAP and I am interested in using it to compute in Galois's > Fields with a large number of elements. > I have found that GAP has te limit of 2^16 elements and I would like > to know if there is a way to expand this capability. The limit of 2^16 results from the internal representation of finite field elements in GAP, so there is no trick to construct bigger finite fields. Of course it is possible to choose an irreducible polynomial f of degree n over the field GF(q), say, and then use the polynomials over GF(q) modulo f as elements of the field GF( q^n ). But this is not really a realization of big finite fields in GAP, since there are up to now no data structures such as ideals and cosets that would allow to regard an object g + (f) as element of GF(q)[X] / (f) and thus as a field element. Consequently for this construction one cannot use GAP functions for fields (such as for the computation of a basis, a primitive root, or the Galois group) or their elements (such as for the computation of trace or norm). In other words, up to now there is no support by data structures and functions in GAP for handling finite fields of size bigger than 2^16, or for handling their elements. In the (not too near) future, however, the limit of 2^16 will be extended. Kind regards Thomas Breuer From Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Aug 15 09:05:00 1994 From: "Joachim Neubueser" Date: Mon, 15 Aug 94 09:05 +0200 Subject: new algebraic number theory preprint server Dear Forum members, I am forwarding an announcement that may be interesting to some of you. Joachim Neubueser ---------------------------------------------------------------------- > Date: Fri, 12 Aug 1994 12:30:26 -0500 > From: Nigel Boston > Subject: new algebraic number theory preprint server > Status: RO > > > We hereby announce a new archive for the the temporary storage of electronic > preprints in algebraic number theory. The archive is located at the > University of Illinois at Urbana-Champaign. The preferred form for the > papers is in TeX dvi format. This allows the papers to be viewed > immediately. > > The procedure for submission of new preprints to the archives is simple. The > author prepares a short ascii file containing the title, author's name and > email address, and an abstract of the paper. This file and the file (or > files) constituting the paper itself are then uploaded to our server using > anonymous ftp. > > ----------------------------------------------------------------------------- > > The best way to view the preprints and the instructions for authors is with > a world wide web client. A file explaining such things is available by > anonymous ftp from math.uiuc.edu in > pub/papers/Algebraic-Number-Theory/aux/www-faq. It will > tell you to obtain one if one doesn't exist on your system. The one we > prefer is called Mosaic. > > Using your world wide web client you may open the URL named > "http://www.math.uiuc.edu/Algebraic-Number-Theory". > The associated dvi files are present, and can be viewed immediately > on your screen. > > The preprint files are also accessible via anonymous ftp, on the machine > math.uiuc.edu. The files associated with paper number 11, say, will be found > in the directory pub/papers/Algebraic-Number-Theory/0011. The instructions > for authors are in the file pub/papers/Algebraic-Number-Theory/aux/instructions. > ----------------------------------------------------------------------------- > > There is a mailing list whose members receive announcements via email of > additions to the archives. To join, simply send an email message to > majordomo@ux1.cso.uiuc.edu which contains the following line in its body. > > subscribe algebraic-number-theory > > ----------------------------------------------------------------------------- > > Nigel Boston > Dan Grayson From a.mathas@ic.ac.uk Mon Aug 15 15:58:00 1994 From: "Andrew Mathas" Date: Mon, 15 Aug 94 15:58 +0100 Subject: Re: operations query Martin Schoenert writes: #The general description is in the section "Dispatchers". The sections #for the dispatchers contain paragraphs like the following # # 'Orbit' calls \\ # '.operations.Orbit( , , )' \\ # and returns the value. Note that the third argument is not optional for # functions called this way. # #But this is not done consistently in the manual, so if you find a section #without such a paragraph, it doesn't mean that the function is not a #dispatcher. # #In section "Function Calls" you will find # # An exception again occurs if the function has only one formal argument # with the name 'arg'. In this case the values of all the actual arguments # are stored in a list and this list is assigned to the new variable # corresponding to the formal argument 'arg'. # Thanks for these references and your hepl about dispatchers in general. Perhaps the index in the GAP manual should be updated so as to point to these things? On another note, a long while ago I wrote a Sublist routine to give all in the sublists in a list and afterwards I discovered that there is a SubList function in the GAP libraries. Mine is significantly faster on large lists; if you want me to send you a copy let me know (the difference is that the GAP version uses recursion whereas mine uses boolean arithmetic). Regards, Andrew From Martin.Schoenert@Math.RWTH-Aachen.DE Tue Aug 16 11:32:00 1994 From: "Martin Schoenert" Date: Tue, 16 Aug 94 11:32 -0700 (PDT) Subject: Re: Re: operations query Andrew Mathas writes in his e-mail message of 1994/08/15 On another note, a long while ago I wrote a Sublist routine to give all in the sublists in a list and afterwards I discovered that there is a SubList function in the GAP libraries. Mine is significantly faster on large lists; if you want me to send you a copy let me know (the difference is that the GAP version uses recursion whereas mine uses boolean arithmetic). I am quite interested in your function. Why don't you put it on our 'ftp' server into the directory 'pub/incoming'? Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From kaskel@math.berkeley.edu Wed Aug 17 00:18:00 1994 From: "Bruce Kaskel" Date: Wed, 17 Aug 94 00:18 -0700 Subject: some group theoretic questions Dear GAP Forum, Here are some (finite) group theoretic questions and I hope they are not beyond the bounds of this forum. Certainly, I would expect that GAP could help (or has already helped) provide some of the answers to these questions. Also, I believe this forum to be the best location to find those who might know the answers. Please direct e-mail responses to Ruvain Gittelman at: gittelma@math.berkeley.edu +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1) What is the largest integer n such that ALL groups of order less than n are known? Where is this information to be found? n 2) What is the largest n such that all groups of order 2 are known? Same for odd primes. 3) What is known about the automorphism group towers of finite groups which may have nontrivial center? Are groups whose tower terminates in {e} known? +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ From sl25@cus.cam.ac.uk Wed Aug 17 12:34:00 1994 From: "Steve Linton" Date: Wed, 17 Aug 94 12:34 +0200 Subject: Normalizer Can I suggest a minor improvement to Normalizer, especially for permutation groups. I recently did Normalizer(g,h) where h was, in fact a subgroup of g, although actually represented as a parent group in its own right. This ended up in GroupOps.Normalizer and showed no sign of returning (g was S10, h was D10 in regular representation). on the other hand doing h := AsSubgroup(g,h); Normalizer(g,h); produced the required result reasonably quickly. Perhaps this situation could be checked for somewhere and the quicker algorithm used in that case. Even better, h & g could be embedded in the group they both generate. Steve From tim@bruckner.stoch.uni-linz.ac.at Wed Aug 17 18:15:00 1994 From: "Tim Boykett" Date: Wed, 17 Aug 94 18:15 +0200 Subject: semigroups Hello Gap users. as a part of a degree, one of the students here has written a collection of semigroup functions for Gap. I will include the readme below, anyone can mail me for a copy, or I will upload it somewhere if there is some interest. Of course, we would be interested in any failings in the code :-) Regs Tim Boykett ----------------------------------------------------------------------------- ****************************************************************************** *** SEMIGROUP FUNCTIONS FOR GAP *** V 1.25 25.07.1994 *** (c) Widi Marcel Oliver *** ******************************************************************************* >Semigroup( l1, l2 ); * defines a semigroup; SYNTAX 1 arguments : l1 ... set of abstract generators l2 ... set of defining relations SYNTAX 2 arguments : l1 ... the semigroup table l2 ... the elements of the semigroup >IsSemigroup( g ); checks if g is defined as a semigroup >DefSgCommutative( g ); *NEW* define a semigroup presentation as commutative >DefAsNeutral( g, x ); *NEW* define the abstract generator x to be the neutral element of g >SgTable( g {,"v"} {,order} ); *IMPROVED* computes the table of the semigroup g using some improved Knuth-Bendix algorithm "v" (optional) ... display progress of computation order (optional) ... length-lexicographic order : 1 lexicographic order : 2 power-lexicographic order : 3 >MinGens( g {,"v"} {,order} ); *NEW* try to minimize the generators in the semigroup g optional parameters : see SgTable >Size( g ); computes the number of elements of g >Elements( g ); *FIXED* computes the elements of g >SgP( g, x, y ); computes the product of x and y in the semigroup g >IsSgMonoid( g ); checks if the semigroup g is a monoid >IsSgGroup( g ); *NEW* checks if the semigroup g is a group >SgNeutral( g ); computes neutral element if g is a monoid; returns false otherwise >IsSgCommutative( g ); *IMPROVED* checks if the semigroup g is commutative >SgIdempotents( g ); computes the idempotent elements of g >IsGroupInvertible( g, x ); checks, if the element x of g is (group-)invertible >SgGroupKernel( g ); computes the group kernel of a semigroup >SgCentralizer( g, s ); computes centralizer of the subset s of the semigroup g >SgCenter( g ); computes the center of the semigroup g >IsSgIdempotent( g ); checks if the semigroup g is idempotent >SgRegulars( g ); computes the regular elements of g >IsSgRegular( g ); checks if the semigroup g is regular >SgCompletelyRegulars( g ); computes the completely regular elements of g >IsSgCompletelyRegular( g ); checks if the semigroup g is completely regular >IsSgInverse( g ); checks if the semigroup g is inverse >IsCliffordSg( g ); checks if the semigroup g is a Clifford semigroup >SubSemigroup( g, s ); computes the subsemigroup of g generated by the subset s of g >IsSubSemigroup( g, s ); *NEW* checks if s is a subsemigroup of g >SubSemigroups( g ); *NEW* computes all subsemigroups of g >SgOrder( g, a ); computes the order of the element a in the semigroup g >SgDistance( g1, g2 ); *MODIFIED* computes the distance between semigroups g1 and g2 where there must be standard-epimorphism between g1 and g2 >SgD( g1, g2 ); computes the distance between semigroups g1 and g2 where g1 and g2 only must have same set of generators >SgGCD( g1, g2 ); computes the greatest common divisor of semigroups g1,g2 >SgLeftIdeal( g, s ); *NEW* computes left ideal generated by s in semigroup g >SgRightIdeal( g, s ); *NEW* computes right ideal generated by s in semigroup g >SgIdeal( g, s ); *NEW* computes ideal generated by s in semigroup g >IsSgLeftIdeal( g, s ); *NEW* checks if s is a left ideal in g >SgRightIdeal( g, s ); *NEW* checks if s is a right ideal in g >IsSgIdeal( g, s ); *NEW* checks if s is an ideal in g >SgEpi( g, h ); *NEW* computes all epimorphisms from g in h >SgMono( g, h ); *NEW* computes all monomorphisms from g in h >SgIso( g, h ); *NEW* computes all isomorphisms from g in h >SgHomo( g, h ); *NEW* computes all homomorphisms from g in h >SgEndo( g ); *NEW* computes all endomorphism on g >SgAuto( g ); *NEW* computes all automorphisms on g ********************************************************************************watch this board for news ! NEW since V 1.16 : * The function SgTable has been modified to compute the operation table for commutative semigroups using Groebner Bases. * The function SgTable can now be called with three different orders. * A minor bug in the SgTable function has been removed. * The function IsSgCommutative has been completely rewritten. * The function DefSgCommutative has been added. * The function DefAsNeutral has been added. * The function IsSgGroup has been added. * The function MinGens has been added. * The function SgDistance has been modified. * The functions IsSubsemigroup and SubSemigroups have been added. * The functions SgEpi, SgMono, SgIso, SgEndo, SgAuto and SgHomo have been added. * The functions SgRightIdeal, SgLeftIdeal and SgIdeal have been added. * The functions IsSgRightIdeal, IsSgLeftIdeal and IsSgIdeal have been added. * The function Elements has been fixed. ******************************************************************************** From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Aug 18 14:21:00 1994 From: "Martin Schoenert" Date: Thu, 18 Aug 94 14:21 -0700 (PDT) Subject: Re: semigroups Tim Boykett writes in his e-mail message of 1994/08/17 as a part of a degree, one of the students here has written a collection of semigroup functions for Gap. I will include the readme below, anyone can mail me for a copy, or I will upload it somewhere if there is some interest. I suggest that you upload the code together with the readme file to 'ftp://ftp.math.rwth-aachen.de/pub/incoming/'. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From fisk@polar.bowdoin.edu Thu Aug 18 10:13:00 1994 From: "Steve Fisk" Date: Thu, 18 Aug 94 10:13 -0400 Subject: info files for gap Dear Gap Forum, The documentation is getting so large that it it is hard to comprehend. The online help is useful, but does not enable browsing. I therefore wrote a conversion program from the tex files to EMACS info format. It's the biggest info file I've ever seen (57 files)! Directions: 0) Create a directory to hold the info files. 1) Save the shar portion of this message in a file INFO-GAP in this directory 2) Type "unshar INFO-GAP" (or if you do not have unshar, change INFO-GAP to executable, and type "INFO-GAP". 3) Read the file README, and make a few changes in "info.pl". 4) Type "info.pl", and wait 30 minutes (or so). 5) Fix up the index, and you're done! I hope that you find this useful. It is easy to change this to include new documentation. It's almost, but not quite, automatic. -- Steve Fisk Department of Mathematics 207-725-3574 Bowdoin College fisk@bowdoin.edu Brunswick, Me. 04011 USA #!/bin/sh # This is a shell archive (produced by shar 3.52.3) # To extract the files from this archive, save it to a file, remove # everything above the "!/bin/sh" line above, and type "sh file_name". # # made 08/18/1994 13:25 UTC by fisk@bruin.bowdoin.edu # Source directory /people/faculty/math/fisk/tmp/GAP-texi # # existing files will NOT be overwritten unless -c is specified # # This shar contains: # length mode name # ------ ---------- ------------------------------------------ # 2093 -rw------- README # 75 -rw-r--r-- GAP-INDEX.texi # 104 -rw-r--r-- GAP-emacs.el # 4366 -rw-r--r-- GAP.texi-orig # 5885 -rwxr--r-- info.pl # touch -am 1231235999 $$.touch >/dev/null 2>&1 if test ! -f 1231235999 && test -f $$.touch; then shar_touch=touch else shar_touch=: echo 'WARNING: not restoring timestamps' fi rm -f 1231235999 $$.touch # # ============= README ============== if test -f 'README' && test X"$1" != X"-c"; then echo 'x - skipping README (File already exists)' else echo 'x - extracting README (Text)' sed 's/^X//' << 'SHAR_EOF' > 'README' && Preliminary changes: X X I was amazed how well the documentation followed its rules. Creating X the info file was not hard (although I had to learn perl to do it). X I only found one syntactic mistake in the info files that needed X changing: in install.tex, there are many references to |c:\|; these X should be changed to |c:|. I think that there might also be one X occurrence of |grp\| there (change it to |grp|, but my notes are X not clear about that. X X How to create the info files. X X 1) make a new directory to hold the info files X X 2) copy info.pl, GAP-emacs.el, and GAP-texi.orig to this directory. X X 3) edit info.pl - there are two directories that must be specified. X Also, check if the pathname to perl (first line) is correct. X X 4) run info.pl - this takes a while (10 minutes to 30 minutes for me) X it produces lots of messages! X X 5) If all goes well, at the very end you should get the message X X Removing temp files and emacs backups Making info file `GAP.info' from `GAP.texi'. /people/faculty/math/fisk/tmp/GAP-texi/algebra.texi:1982: X This `example' doesn't have a matching `@end example'. X X X (I don't understand this error.) X X 6) The result of the computation is: X X GAP.info X GAP.info-1 ... GAP.info-57 X algebra.texi algebra-menu.texi ... (two for each chapter) X X All the files except the files GAP.info* can be removed X if you are satisfied with the outcome. X X 6) For some reason, the index file is not correct. For me, X the index is located in GAP.info-57. Find the two lines X X Command Index ************* X X All the menu items have several leading spaces. So, instead of X X * Menu: X X * AbelianGroup: The Basic Groups Library. X * AbelianInvariantsNormalClosureFpGroup: Group Functions for Finitely Presented Groups. X (etc) X X you should remove the leading spaces to create X X * Menu: X * AbelianGroup: The Basic Groups Library. * AbelianInvariantsNormalClosureFpGroup: Group Functions for Finitely Presented Groups. X (etc) X X X 7) With these changes, you should have an info file for GAP! X SHAR_EOF $shar_touch -am 0818092294 'README' && chmod 0600 'README' || echo 'restore of README failed' shar_count="`wc -c < 'README'`" test 2093 -eq "$shar_count" || echo "README: original size 2093, current size $shar_count" fi # ============= GAP-INDEX.texi ============== if test -f 'GAP-INDEX.texi' && test X"$1" != X"-c"; then echo 'x - skipping GAP-INDEX.texi (File already exists)' else echo 'x - extracting GAP-INDEX.texi (Text)' sed 's/^X//' << 'SHAR_EOF' > 'GAP-INDEX.texi' && @node Command Index, , weyl, Top @chapter Command Index X @printindex cm X SHAR_EOF $shar_touch -am 0818090894 'GAP-INDEX.texi' && chmod 0644 'GAP-INDEX.texi' || echo 'restore of GAP-INDEX.texi failed' shar_count="`wc -c < 'GAP-INDEX.texi'`" test 75 -eq "$shar_count" || echo "GAP-INDEX.texi: original size 75, current size $shar_count" fi # ============= GAP-emacs.el ============== if test -f 'GAP-emacs.el' && test X"$1" != X"-c"; then echo 'x - skipping GAP-emacs.el (File already exists)' else echo 'x - extracting GAP-emacs.el (Text)' sed 's/^X//' << 'SHAR_EOF' > 'GAP-emacs.el' && (load-library "texnfo-upd") (texinfo-multiple-files-update "GAP.texi" t t) (save-buffers-kill-emacs t) SHAR_EOF $shar_touch -am 0729104094 'GAP-emacs.el' && chmod 0644 'GAP-emacs.el' || echo 'restore of GAP-emacs.el failed' shar_count="`wc -c < 'GAP-emacs.el'`" test 104 -eq "$shar_count" || echo "GAP-emacs.el: original size 104, current size $shar_count" fi # ============= GAP.texi-orig ============== if test -f 'GAP.texi-orig' && test X"$1" != X"-c"; then echo 'x - skipping GAP.texi-orig (File already exists)' else echo 'x - extracting GAP.texi-orig (Text)' sed 's/^X//' << 'SHAR_EOF' > 'GAP.texi-orig' && \input texinfo @c -*- texinfo -*- @c %**start of header @setfilename GAP.info @settitle GAP @value{version} @c make a command index: @defcodeindex cm @c %**end of header X @set version 1.5 @set update-date 2 Feb 1994 @set update-month Feb 1994 X @clear smallbook X @c Play with some whitespace settings: @tex \global\chapheadingskip = 15pt plus 4pt minus 2pt \global\secheadingskip = 12pt plus 3pt minus 2pt \global\subsecheadingskip = 9pt plus 2pt minus 2pt @end tex X @c Use smaller whitespace between paragraphs in the 8.5x11 format: @ifclear smallbook @tex \global\parskip 6pt plus 1pt @end tex @end ifclear X @finalout X @ifinfo X @end ifinfo X @setchapternewpage odd @titlepage @title GAP X X @c The following two commands start the copyright page. @c Put it inside the titlepage to turn off headings: @page @vskip 0pt plus 1filll X @end titlepage X @node Top, aboutgap, (dir), (dir) @top GAP X @menu * aboutgap::About GAP * language::The Programming Language * environm::Environment * domain::Domains * ring::Rings * field::Fields * group::Groups * operatio::Operations of Groups * vecspace::Vector Spaces * integer::Integers * numtheor::Number Theory * rational::Rationals * cyclotom::Cyclotomics * gaussian::Gaussians * numfield::Subfields of Cyclotomic Fields * unknown::Unknowns * finfield::Finite Fields * polynom::Polynomials * permutat::Permutations * permgrp::Permutation Groups * word::Words in Abstract Generators * fpgrp::Finitely Presented Groups * agwords::Words in Finite Polycyclic Groups * aggroup::Finite Polycyclic Groups * saggroup::Special Ag Groups * list::Lists * set::Sets * blister::Boolean Lists * string::Strings and Characters * range::Ranges * vector::Vectors * rowspace::Row Spaces * matrix::Matrices * matring::Matrix Rings * matgrp::Matrix Groups * grplib::Group Libraries * algebra::Algebras * algfp::Finitely Presented Algebras * algmat::Matrix Algebras * module::Modules * mapping::Mappings * homomorp::Homomorphisms * boolean::Booleans * record::Records * combinat::Combinatorics * tom::Tables of Marks * chartabl::Character Tables * gentable::Generic Character Tables * characte::Characters * paramaps::Maps and Parametrized Maps * gettable::Character Table Libraries * classfun::Class Functions * monomial::Monomiality Questions * install::Getting and Installing GAP * share::Share Libraries * anupq::ANU Pq * grape::Grape * mtx::The MeatAxe * sisyphos::Sisyphos * smash::Smash, Matrix Groups and $G$-Modules * ve::Vector Enumeration * weyl::Weyl Groups and Hecke Algebras * aboutgap::About GAP * language::The Programming Language * environm::Environment * domain::Domains * ring::Rings * field::Fields * group::Groups * operatio::Operations of Groups * vecspace::Vector Spaces * integer::Integers * numtheor::Number Theory * rational::Rationals * cyclotom::Cyclotomics * gaussian::Gaussians * numfield::Subfields of Cyclotomic Fields * unknown::Unknowns * finfield::Finite Fields * polynom::Polynomials * permutat::Permutations * permgrp::Permutation Groups * word::Words in Abstract Generators * fpgrp::Finitely Presented Groups * agwords::Words in Finite Polycyclic Groups * aggroup::Finite Polycyclic Groups * saggroup::Special Ag Groups * list::Lists * set::Sets * blister::Boolean Lists * string::Strings and Characters * range::Ranges * vector::Vectors * rowspace::Row Spaces * matrix::Matrices * matring::Matrix Rings * matgrp::Matrix Groups * grplib::Group Libraries * algebra::Algebras * algfp::Finitely Presented Algebras * algmat::Matrix Algebras * module::Modules * mapping::Mappings * homomorp::Homomorphisms * boolean::Booleans * record::Records * combinat::Combinatorics * tom::Tables of Marks * chartabl::Character Tables * gentable::Generic Character Tables * characte::Characters * paramaps::Maps and Parametrized Maps * gettable::Character Table Libraries * classfun::Class Functions * monomial::Monomiality Questions * install::Getting and Installing GAP * share::Share Libraries * anupq::ANU Pq * grape::Grape * mtx::The MeatAxe * sisyphos::Sisyphos * smash::Smash, Matrix Groups and $G$-Modules * ve::Vector Enumeration * weyl::Weyl Groups and Hecke Algebras * Comamnd Index::Index of Commands @end menu X XXXXXXinclude-hereXXXXX X @page X @include GAP-INDEX.texi X @contents @bye X X X SHAR_EOF $shar_touch -am 0817154294 'GAP.texi-orig' && chmod 0644 'GAP.texi-orig' || echo 'restore of GAP.texi-orig failed' shar_count="`wc -c < 'GAP.texi-orig'`" test 4366 -eq "$shar_count" || echo "GAP.texi-orig: original size 4366, current size $shar_count" fi # ============= info.pl ============== if test -f 'info.pl' && test X"$1" != X"-c"; then echo 'x - skipping info.pl (File already exists)' else echo 'x - extracting info.pl (Text)' sed 's/^X//' << 'SHAR_EOF' > 'info.pl' && #!/usr/local/bin/perl X # An overview of the files X # Original Files X # GAP-emacs.el Used to update all the nodes in the texinfo file # GAP.texi-orig Skeleton used to create main texinfo file # GAP-INDEX.texi Read in to input the index X # Created Files X # GAPinclude.texi List of texinfo files to be included; it is # inserted into GAP.texi-orig to make GAP.texi # GAP.texi main texinfo file # ?.texi one file for each chapter # GAPmainmenu.texi If you want, you could replace (by hand!) the # menu in GAP.texi by this one - # it has the section names X # # Set the following to the GAP home directory # X $GAPdir = "/people/faculty/math/fisk/usr/local/src/gap3r4p0"; X # # Where the info files should be (and the file GAP.info is) # X $GAPinfodir = "/people/faculty/math/fisk/tmp/GAP-texi"; X ############################################################### # # Nothing more to change # ############################################################### X # # test to see that the files and directories are there # X chdir($GAPinfodir) || die("please make the info directory\n"); $tmpfile = $GAPinfodir . "/TEMP"; X if (!(-e "GAP.texi-orig")) {die("file GAP.texi-orig not found")}; if (!(-e "GAP-emacs.el")) {die("file GAP-emacs.el not found")}; if (!(-w $GAPdir)) {die("directory for GAP not writable")}; X X # # files included in top info file # X open(GAPinclude, ">GAPinclude.texi"); open(GAPmainmenu, ">GAPmainmenu.texi"); open(GAPtexinfo, ">GAP.texi"); open(GAPtexinfoXX, "GAP.texi-orig"); X # # the list of all chapters, in order from manual.tex # X @GAPlist = ("aboutgap","language","environm", "domain", "ring", "field", "group","operatio","vecspace","integer","numtheor","rational","cyclotom", "gaussian","numfield","unknown","finfield","polynom","permutat","permgrp", "word","fpgrp","agwords","aggroup","saggroup","list","set","blister","string", "range","vector","rowspace","matrix","matring","matgrp","grplib","algebra", "algfp","algmat","module","mapping","homomorp","boolean","record","combinat", "tom","chartabl","gentable","characte","paramaps","gettable","classfun", "monomial","install","share","anupq","grape","mtx","sisyphos","smash","ve", "weyl"); X #@GAPlist = ("aboutgap","language"); #@GAPlist = ("install"); X # # convert each chapter # X foreach $GAPchapter (@GAPlist) { X X X $current = $GAPdir . "/doc/" . $GAPchapter . ".tex"; X $texinfo = $GAPinfodir . "/" . $GAPchapter . ".texi"; X $texmenu = $GAPinfodir . "/" . $GAPchapter . "-menu.texi"; X X $parity_of_bar = 0; # reset at beginning of each chapter X X print "Processing $current\n"; X print GAPinclude "@include $texinfo\n"; X X open(GAPfile,$current) || die "can't open $current"; X open(GAPtexi, ">" . $texinfo) || die("can't open $texinfo\n"); X open(GAPmenu, ">" . $texmenu) || die("can't open $texmenu\n"); X X X X Main: X while() { X chop($_); X $name = $_; # # skip comments # X if(substr($_,0,1) eq "%") { X next Main; X } X X s/@/@@/g; # fix @'s X s/\\\\{}/@*/g; # break lines X s/\\\\/@*/g; X s/\\vspace{[\d\w]*}//g; # no vspace X s/\\index{(\w*)}/\n@cmindex \1 \n/g; # fix index X s/\\index{(\w*!\w*)}/\n@cmindex \1 \n/g; X s/{/ @{/g; # protect { and } X s/}/ @}/g; X # # worry about literals # X s/\|\\\|/BARSLASHBAR/g; X s/\\\|/BBAARR/g; # temporarily change literal bars X $number_of_bars=0; # count bars (page 155, perl book) X $pos = 0; X while (( $pos = index($_,"|",$pos)) >= 0) { X $pos++; X $number_of_bars++; X } # # skip if an even number of bars # X if( ($number_of_bars % 2) == 1) { X $parity_of_bar = 1 - $parity_of_bar; X if($parity_of_bar == 1) X {s/\|/\n@example\n/;} X else X {s/\|/\n@end example\n/;} X }; X s/BBAARR/\\\|/g; # restore literal bars X s/BARSLASHBAR/\|\\\|/g; # # Write # X $writeout = 1; X if(/\\Chapter|\\Section/) { X $writeout = 0; X $name =~ s/\\Chapter{//g; X $name =~ s/\\Section{//g; X $name =~ s/}//g; X $name =~ s/}//g; X $name =~ s/%//g; X $name =~ s/\\index.*//g; X }; X if(/\\Chapter/) { X print GAPmenu "@node $GAPchapter,Top,Top,Top\n"; X print GAPmenu "@chapter $name\n"; X print GAPmenu "@menu \n"; X print GAPmainmenu "* $GAPchapter::$name \n"; X }; X if(/\\Section/){ X print GAPtexi "@node $name\n"; X print GAPtexi "@section $name\n"; X print GAPmenu "* $name:: \n"; X }; X if($writeout == 1) { # write out X print GAPtexi "$_\n"; X }; X } X # # Close files # X print GAPmenu "@end menu \n"; X close(GAPfile); X close(GAPtexi); X close(GAPmenu); X # # copy the menu to the beginning of the file, and then remove it # X system("mv $texinfo $tmpfile"); X system("cat $texmenu $tmpfile > $texinfo"); # unlink($texmenu); } X X X X X # # copy the include files to the main texinfo file # X close(GAPinclude); open(GAPinclude, "GAPinclude.texi"); X while() { X if(index($_,"XXXXXinclude-hereXXXXX") == -1){ X print GAPtexinfo; } else { X while() { X print GAPtexinfo; X } }} X close(GAPtexinfo); X X # # update the new texinfo file # X X print " updating nodes - this takes a long time \n"; X system("emacs -batch -q -l GAP-emacs.el "); X X # # all done - remove temp file and backups created by emacs # X print "\nRemoving temp files and emacs backups\n"; close(GAPmainmenu); unlink($tmpfile); X foreach $GAPchapter (@GAPlist) { X $texinfo_back = $GAPinfodir . "/" . $GAPchapter . ".texi~"; X unlink($texinfo_back); } X X # # run makeinfo and create the info files # X X system("makeinfo GAP.texi"); X X X X SHAR_EOF $shar_touch -am 0817145794 'info.pl' && chmod 0744 'info.pl' || echo 'restore of info.pl failed' shar_count="`wc -c < 'info.pl'`" test 5885 -eq "$shar_count" || echo "info.pl: original size 5885, current size $shar_count" fi exit 0 From Frank.Celler@Math.RWTH-Aachen.DE Thu Aug 18 17:58:00 1994 From: "Frank Celler" Date: Thu, 18 Aug 94 17:58 -0700 (PDT) Subject: Re: info files for gap Dear Steve Fisk, I hope that you find this useful. It is easy to change this to many thanks for your nice converter, I have copied a zoo archive of your program to "ftp.math.rwth-aachen.de:/pub/incoming/fisk.zoo". best wishes Frank From sl25@cus.cam.ac.uk Fri Aug 19 11:21:00 1994 From: "Steve Linton" Date: Fri, 19 Aug 94 11:21 +0200 Subject: On-line manual Using Steve Fisk's converter, and the CERN texi2html converter, I have produced an on-line hypertext GAP (3.4) manual, available for inspection at http://www-theory.cs.st-and.ac.uk/~sal/GAP I would appreciate comments. I know that the command index is missing. This seems to be a deficiency of the CERN converter. I will zoo up the HTML and upload it to samson shortly in case people want to establish local copies, alternatively the two stage conversion is fairly painless. Steve Linton From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Aug 19 11:50:00 1994 From: "Martin Schoenert" Date: Fri, 19 Aug 94 11:50 -0700 (PDT) Subject: Re: On-line manual I am currently working on a direct translation of the LaTeX subset the GAP manual is using to HTML. Should produce nicer results than the GAP-LaTeX -> TeXinfo -> HTML translation. For example it uses proper fonts. It would also like to hear comments about Steve's HTML document. For example, is it better to have one document per section or is it better to have one document per chapter and each section has its own label? Note that Steve Fisk's converter has problems with some features and inconsistencies in the GAP manual. For example it keeps the index entries. Also his handling of '\' is not quite correct, e.g., '\' has no special meaning in the example environment (|example|). Also it would be nice if the crossreferences (see "somewhere") where mapped to references in the TeXinfo manual. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From fisk@polar.bowdoin.edu Fri Aug 19 08:15:00 1994 From: "Steve Fisk" Date: Fri, 19 Aug 94 08:15 -0400 Subject: Re: On-line manual Steve It's nice! I noticed that not only is the command index missing, but the top level menu in the first page is missing. This is also useful, since it gives the names of all the chapters. Indeed, I wonder if it is a good idea to include all the chapter headings in the main menu - it makes it very big (60K I think). Perhaps it would be better if there were a "GAP home page" with the banner and the chapter titles. -- Steve Fisk Department of Mathematics 207-725-3574 Bowdoin College fisk@bowdoin.edu Brunswick, Me. 04011 USA From fisk@polar.bowdoin.edu Fri Aug 19 08:30:00 1994 From: "Steve Fisk" Date: Fri, 19 Aug 94 08:30 -0400 Subject: Re: On-line manual >>>> "Martin" == Martin Schoenert writes: Martin> I am currently working on a direct translation of the LaTeX Martin> subset the GAP manual is using to HTML. Should produce nicer Martin> results than the GAP-LaTeX -> TeXinfo -> HTML translation. Martin> For example it uses proper fonts. Martin> It would also like to hear comments about Steve's HTML Martin> document. For example, is it better to have one document per Martin> section or is it better to have one document per chapter and Martin> each section has its own label? My view Home Page - telling about GAP All Chapter titles, plus pointer to listing of all nodes and index Chapter 1 (Aboutgap) first section ... Chapter 2 first section ... ... Index Is this what your question meant? Martin> Note that Steve Fisk's converter has problems with some Martin> features and inconsistencies in the GAP manual. For example Martin> it keeps the index entries. Also his handling of '\' is not Martin> quite correct, e.g., '\' has no special meaning in the Martin> example environment (|example|). Also it would be nice if Martin> the crossreferences (see "somewhere") where mapped to Martin> references in the TeXinfo manual. I'm not surprised that it doesn't get all these features correct. I was very impressed with the organization of the manual that allowed almost 1000 pages to become a "nearly correct" info document. I attempted a minimal conversion - I know there are problems with references, fonts, index entries, |'s (and I spend more time with | than with everything else combined). I think that for someone who knows perl, these are not too hard to do. However, the direct creation of the HTML document - by the creator - is clearly the best way to proceed. I only hope that my effort proves useful in the short run. Anyway, I enjoyed learning perl. Once again, thanks for GAP! Steve Fisk Department of Mathematics 207-725-3574 Bowdoin College fisk@bowdoin.edu Brunswick, Me. 04011 USA From sl25@cus.cam.ac.uk Fri Aug 19 15:19:00 1994 From: "Steve Linton" Date: Fri, 19 Aug 94 15:19 +0200 Subject: Re: On-line manual Steve Fisk wrote: > Martin> It would also like to hear comments about Steve's HTML > Martin> document. For example, is it better to have one document per > Martin> section or is it better to have one document per chapter and > Martin> each section has its own label? > > My view > > Home Page - telling about GAP > All Chapter titles, plus pointer to listing of all nodes and index > Chapter 1 (Aboutgap) > first section > ... > Chapter 2 > first section > ... > ... > Index > > > Is this what your question meant? > > I think he is referring to the way that the HTML manual is split up into 1317 separate files, one for each section. HTML (and texi2html) would also allow fewer longer files with internal references to the sections as part of the files. Given that my copy is local, so that bringing up a new section is virtually instant, I like the split version, but for remote use fewer larger files might make more sense. Steve From tim@bruckner.stoch.uni-linz.ac.at Fri Aug 19 18:03:00 1994 From: "Tim Boykett" Date: Fri, 19 Aug 94 18:03 +0200 Subject: Re: semigroups Hi, i have uploaded the semigroup.g file to the samson ftp site, but i could not upload the semigroup.doc file that explains it all. Unfortunately it is also not tex'ed (some students ARE slack :-). Could someone from the GaP group tell me how to upload the documentation? tim From Martin.Schoenert@Math.RWTH-Aachen.DE Sat Aug 20 02:07:00 1994 From: "Martin Schoenert" Date: Sat, 20 Aug 94 02:07 +0100 (MET) Subject: Re: Re: On-line manual I am going to violate one of my principles, namely ``never underestimate your users'', but I still think that a few explanations are in order to help those who have never heard of HTML or 'texi2html' before. A lot of people are currently interested in documents on Networks. Such documents should be easily available to everyone, it should be easy to reference one document from within another, and should be possibly contain pictures, movies, and sound. The most popular system is the World Wide Web (WWW). It originated at Cern, and is likely to become the most important consumer of Internet bandwidth in the near future. The most popular browser (computer program that allows you to read documents in the WWW, follow their links to other documents, and display embedded pictures, movies, and sound) for the WWW is called Mosaic and available for UNIX, MS-DOS, and Macs from NCSA-UIUC. The most important format for WWW is called HTML, which is short for Hyper Text Markup Language. Hyper Text refers to the fact that such documents can contain links to other documents. Markup Language refers to the format in which such links and other formatting information are represented in the source of such documents. Another Markup Language is TeX. However, TeX is not Hyper Text, because it doesn't allow you to create links to other documents that a program could automatically follow. The links in an HTML documents are given in a format that is called Universal Resource Locator (URL). An example of a URL is in Steve's e-mail message. 'http://www-theory.cs.st-and.ac.uk/~sal/GAP'. This means that the document is on the computer 'www-theory.cs.st-and.ac.uk', it is in Steve's WWW home directory '~sal', is called 'GAP', and can be retrived using the Hyper Text Transfer Protocol (http). HTML is just one format for textual information that can be browsed. Here ``browsed'' basically means that there is no predefined path through the document. Instead a reader can choose different routes depending on what information he or she seeks. Another example is TeXinfo, which is the format used by the GNU project. In this case the browser is the EMACS editor. Pictures and sound are not supported in this format, but the basic browsing is fairly convenient. The TeXinfo format is also interesting for another reason. It is possible to take a TeXinfo document and run it through TeX to produce a hardcopy version of the document. For this to work the entire TeXinfo document is structured in a book like fashion, with chapters, sections, subsections, subsubsections, etc. A sidenote. So TeXinfo documents are basically a tree with a few extra references. General HTML documents can be arbitrary graphs, but it is recommended that they also have a basically tree like structure. I don't find this surprising. Would you rather visit a museum with a long corridor and rooms that branch of from this corridor, or a museum that is a complex maze where you are never certain whether you visited all rooms? Another system similar to TeXinfo is the format in which the GAP manual is written. It contains references in form of (see "
"). You can browse that document using the GAP help functionality. Not very fancy, but it works (actually I prefer it over EMACS info mode, but that is cleary a matter of personal taste). One advantage of our format is that the source can be directly be used by the browser, no further preprocessing is needed. As soon as there are several formats with the same purpose, it makes sense to think about conversions between them. One such converted is 'texi2html' (pronounced TeXinfo too HTML), which converts between the TeXinfo to HTML. Another is the one Steve Fisk write, betwenn GAP's manual format and TeXinfo. This finally takes us back to the basic topic of this discussion. It would be nice if everybody could read the GAP manual using his or her favorite browser, be it the GAP help function, the EMACS info mode, Mosaic, the OS/2 help system, or the Windows help system (and yes, I agree, Mosaic is much more sexy than the GAP help function). For this to work the GAP manual must be converted to the format supported by those browsers. That is, we need a GAP -> HTML converter, a GAP -> TeXinfo converter, etc. This is of course where the work begins. We have to think about how the mapping is supposed to work. E.g., to what is mapped by the GAP -> TeXinfo translation. It may be even necessary to think about needed changes to the GAP format, so that the mappings are possible (but I hope no big change is necessary). The concrete topic that I asked about is the question how the GAP manual should be split in the GAP -> HTML translation. In HTML a document is a single item that you see at once. There can be links between documents or more generally from one document to a certain (labelled) position in another document. There are three possibilities. First the entire manual could be one document, and there could be one (large) document with a label for each section. Second there could be one document for each chapter of the manual and for each section within a document there could be a label. And third there could be one document for each (of the 1317) sections. There s a pragmatic argument that speaks against the first approach. Everyone would have to load the entire manual (all 4 MBytest) into his or her browser, even if he or she wants only to read a single section. The problem with the third approach is that one needs a lot of clicks to go somewhere. It is much easier to read an entire chapter by scrolling than to jump back and forth using links. The problem with the second solution is that at least Mosaic's handling of documents with labels seems unnatural to me. Anyhow, I would appreciate your comments and suggestions what you would like to see in a HTML document of the GAP manual. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany PS. In case the first paragraphs got you wondering. Yes I also got a principle ``never overestimate your users''. This is why I try to make installation, etc. as foolproof as possible. From dfh@maths.warwick.ac.uk Sat Aug 20 21:28:00 1994 From: "Derek Holt" Date: Sat, 20 Aug 94 21:28 +0100 Subject: Making words into strings. gap> a:=AbstractGenerator("a"); gap> String(a); Error, String: cannot convert a into a string in String( a ) called from main loop That is annoying! Is there any reason why the String function shouldn't convert the abstract generator into the supplied string? That ought to be exactly what the string is there for. And similarly for words in abstract generators. Is there any other way of getting the printing string for a word, other than by doing something silly like writing to a file enclosed in quotes, and reading back in? Best wishes, Derek Holt. From Martin.Schoenert@Math.RWTH-Aachen.DE Sat Aug 20 23:12:00 1994 From: "Martin Schoenert" Date: Sat, 20 Aug 94 23:12 +0100 (MET) Subject: Re: Making words into strings. Derek Holt writes in his e-mail message of 1994/08/20 gap> a:=AbstractGenerator("a"); gap> String(a); Error, String: cannot convert a into a string in String( a ) called from main loop That is annoying! Is there any reason why the String function shouldn't convert the abstract generator into the supplied string? That ought to be exactly what the string is there for. No, the *real* reason that 'AbstractGenerator' takes a string is different. I forbade global functions that don't take any arguments in GAP. And since nobody could think of something useful to pass to 'AbstractGenerator' we selected a string. Boy, that came in handy when we finally came around to implement printing of objects ;-). He continues And similarly for words in abstract generators. Is there any other way of getting the printing string for a word, other than by doing something silly like writing to a file enclosed in quotes, and reading back in? As far as I can tell this is the only way, because only 'Print' and relatives looks at the string. Of course once you can handle generators there are lots of options to handle words. This is sad, because otherwise we could start a competition to find the most silly way. I guess what annoys you most is the realization that a kernel function that maps generators to strings would only be a couple of lines long, but that it is impossible to do it with a library function. Unfortunately I cannot fix it in the upcoming update 3r4p1, because we decided that we don't want any kernel changes in this update. But I shall send you a patch which will than later become part of the second update (whenever that might come). Others that are also interested in such a function should write to 'GAP-Trouble'. Take it easy, Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From hwblist@machnix.mathematik.uni-stuttgart.de Sun Aug 21 18:09:00 1994 From: "Harald Boegeholz" Date: Sun, 21 Aug 94 18:09 +0200 Subject: a little bug in RingOps.PolynomialRing Hello! I have discovered a little bug in GAP 3.4PL0: gap> q := Indeterminate(Integers); X(Integers) gap> IsUnit(q^0); false The problem turns out to be that PolynomialRing(Integers).units gets assigned the integers 1 and -1, not the polynomials 1*q^0, (-1)*q^0. I therefore propose the following fix: *** ring.g 1994/08/21 16:29:53 1.1 --- ring.g 1994/08/21 16:31:08 *************** *** 297,303 **** # add known units if IsBound(R.units) then ! P.units := Copy(R.units); fi; # set one and zero --- 297,303 ---- # add known units if IsBound(R.units) then ! P.units := List(R.units, u -> Polynomial( R, [u] )); fi; # set one and zero Harald -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@ftp.uni-stuttgart.de From r.a.fenn@sussex.ac.uk Mon Aug 22 10:30:00 1994 From: "Roger A Fenn" Date: Mon, 22 Aug 94 10:30 +0200 Subject: Re: Re: On-line manual > Dear Martin, I would like to thank you for making up this document. No one else in the department seems interested in these things such as mosaic so this is the only way a mere mathematician can learn. I dont have time or energy to read books on computer science which in any case seem as though they are written by computers themselves. Thanks again, Roger Fenn. From Frank.Celler@Math.RWTH-Aachen.DE Mon Aug 22 11:25:00 1994 From: "Frank Celler" Date: Mon, 22 Aug 94 11:25 -0700 (PDT) Subject: Re: a little bug in RingOps.PolynomialRing Dear Harald, I have discovered a little bug in GAP 3.4PL0: we will fix this bug in PL1, many thanks Frank From eamonn.obrien@maths.anu.edu.au Tue Aug 23 22:09:00 1994 From: "Eamonn O'Brien" Date: Tue, 23 Aug 94 22:09 +1000 Subject: some group theoretic questions I write in response to the following: > From: Bruce Kaskel > > Please direct e-mail responses to Ruvain Gittelman at: > gittelma@math.berkeley.edu > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1) What is the largest integer n such that ALL groups of order less than n > are known? Where is this information to be found? > n > 2) What is the largest n such that all groups of order 2 are known? > Same for odd primes. > > 3) What is known about the automorphism group towers of finite groups > which may have nontrivial center? Are groups whose tower terminates > in {e} known? > +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1. I believe that all groups of orders at most 256 are determined, apart from those of order 192. Presentations for the groups of order at most 100 are distributed with each of GAP and Magma. These are distilled from various sources, two primary ones being: Joachim Neub\"{u}ser (1967), ``Die Untergruppenverb\"{a}nde der Gruppen der Ordnungen $\leq 100$ mit Ausnahme der Ordnungen $64$ und $96$", Habilitationsschrift, Kiel. R. Laue (1982), ``Zur Konstruktion und Klassifikation endlicher aufl\"{o}sbarer Gruppen". Bayreuth. Math. Schr. No. 9. In addition, presentation for the groups of orders dividing 256 and 729 are supplied as part of the group libraries of both systems. Groups whose order involves certain numbers of prime factors are known in various cases: for example, the groups of order p^2*q, where p and q are distinct primes. In the introduction to a 1990 paper of James, Newman & O'Brien [see full reference details below], we mention a few references which you may wish to follow up. Also Mark Short (at Murdoch University, Western Australia) and I prepared a bibliography in the late 1980s on the history of group determinations. I am happy to supply it to you on request. 2. The 2-groups of order dividing 256 and the 3-groups of order dividing 729 have been completely determined (and, as mentioned above, are supplied as part of the GAP library). Details of the results and methods can be found in the following papers: Marshall Hall, Jr., & James K. Senior (1964), The Groups of Order $2^n$ (n$\leq6$). Macmillan, New York. Rodney James, M.F. Newman & E.A. O'Brien (1990), ``The groups of order 128", J. Algebra 129, 136-158. E.A. O'Brien (1991), ``The groups of order 256", J. Algebra 143, 219-235. E.A. O'Brien (1990), ``The p-group generation algorithm", J. Symbolic Comput. 9, 677-698. Various results on the groups of order p^6 (for odd p) are in the literature. A modern determination of the groups of order dividing p^6 is presented in the following paper: Rodney James (1980), ``The Groups of Order $p^6$ ($p$ an Odd Prime)", Math. Comp. 34, 613-637. This list seems reliable for the groups of order dividing p^5. However, M.F. Newman and I are aware of a number of errors in this list for groups of order p^6 and plan -- at some point -- to prepare a corrected version. Again, we are happy to supply our corrections on request, but we make no claims on its completeness. A determination of the groups of exponent p and order p^7 can be found in a paper by Wilkinson which appeared in the J. Algebra in 1988. [I don't have full reference details handy.] Of course, in some sense, the computational tools to carry out the determination of particular classes of p-groups are now available -- via the p-group generation algorithm [see O'Brien, 1990, above for full details]. The implementation of this algorithm is available as a package in GAP and, while limited in the range of application, it can be used in certain cases to determine certain classes of p-groups. For example, in its current form, it could be used to determine most of the approximately *10 million* groups of order 512, or most of the groups of order 3^7. However, one might wish to think carefully before embarking on either project. Eamonn O'Brien obrien@maths.anu.edu.au From hwblist@machnix.mathematik.uni-stuttgart.de Tue Aug 23 21:49:00 1994 From: "Harald Boegeholz" Date: Tue, 23 Aug 94 21:49 +0200 Subject: a suggestion about printing objects in GAP Hello! During my recent work with GAP I have been using polynomials and Laurent polynomials a lot, and I often found the output of GAP somewhat difficult to read. This is particularly true if finite fields are involved. Since no single way of printing things can be correct for all applications, I suggest that different ways of printing objects be implemented in GAP. This could for instance be done by means of a global variable PrintLevel that controls the "exactness" of the output. For example, consider how gap outputs various polynomials: gap> x := Indeterminate(Integers); X(Integers) gap> x.name := "x"; "x" gap> v := [0*x, x^0, x, x^2 + x + 1]; [ 0*x^0, x^0, x, x^2 + x + 1 ] Let's call this PrintLevel=2. At PrintLevel=1, I could imagine the following output: gap> v; [ 0, 1, x, x^2 + x + 1 ] This would be more readable than the output above but would of course not clearly show the fact that "0" and "1" are not integers but polynomials over integers. I'd nevertheless much prefer this output when dealing with matrices of polynomials, since the zeros and ones would be a lot easier to see. On the other hand, at PrintLevel=3, I'd like to see the following output: gap> v; [Polynomial(Integers,[]), Polynomial(Integers,[1]), Polynomial(Integers,[0,1]), Polynomial(Integers,[1,1,1])] This could be useful for saving things in files and reading them back into GAP. I have found that reading polynomials represented this way is much more efficient than reading the current output of GAP. Furthermore, this representation is independent from the name of the indeterminate. I can think of similar examples for elements of finite fields. At PrintLevel=1, elements of prime fields could simply be output as integers in the range 0..p-1. Instead of GAP's current (a little inconsistent) output: gap> x := Indeterminate(GF(17)); X(GF(17)) gap> x.name := "x"; "x" gap> x+x; Z(17)^14*x gap> x+x+x^2; Z(17)^0*(x^2 + 2*x) I would like to see this at PrintLevel=2: gap> x+x; Z(17)^14*x gap> x+x+x^2; x^2 + Z(17)^14*x gap> 20*x; Z(17)*x and this at PrintLevel=1: gap> x+x; 2*x gap> x+x+x^2; x^2 + 2*x gap> 20*x; 3*x Maybe the designers of GAP can think of a more elegant way for selecting the desired type of output (instead of a global variable). Thanks for taking the time to read this longish suggestion. hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@ftp.uni-stuttgart.de From Frank.Celler@Math.RWTH-Aachen.DE Wed Aug 24 11:15:00 1994 From: "Frank Celler" Date: Wed, 24 Aug 94 11:15 -0700 (PDT) Subject: Re: a suggestion about printing objects in GAP Dear Harald, Since no single way of printing things can be correct for all applications, I suggest that different ways of printing objects be implemented in GAP. This could for instance be done by means of a global variable PrintLevel that controls the "exactness" of the output. yes, however this is (unfortunately) a more general problem, which occurs for various objects, some of which are internal. For instance, for finite field elements in a prime field some people prefer n*Z(p)^0 or just n, for abstract words one might consider "*" superfluous, there are various ways to print a matrix, etc. At the moment there are some ad hoc solutions, but we are looking for a unified one. Maybe the designers of GAP can think of a more elegant way for selecting the desired type of output (instead of a global variable). We are discussing ways to print/display/show/save objects, one idea is that there might be a print function to get a representation which can be read back, display and show functions for the user (whatever the distinction between display and show is), and save functions to save an object in a compact form. There is no finished concept at the moment, and even if we agree on one it might take a while (GAP 4.x) before it is implemented. suggestions, ideas, comments welcome, Frank From lmccarth@klingon.cs.umass.edu Thu Aug 25 22:50:00 1994 From: "Lewis McCarthy" Date: Thu, 25 Aug 94 22:50 -0400 Subject: Finite Algebraic Field Extensions I've just noticed that GAP currently only handles finite fields, the field of rationals, and cyclotomic extensions of the rationals. Are there any plans to support arbitrary finite algebraic extensions of the rationals ? This is probably crucial to the project for which I'm considering GAP. -Lewis McCarthy (lmccarth@klingon.cs.umass.edu) From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Aug 26 11:49:00 1994 From: "Martin Schoenert" Date: Fri, 26 Aug 94 11:49 -0700 (PDT) Subject: bug reports It has been mentioned here and in private e-mail messages repeatedly, but the following exchange makes me think that it might be a good idea to state it again. Please inform us of any problem that you find. Just because you find a problem doesn't mean that we will find it too (and how can we fix problems that we don't now). Just because you find a workaround doesn't mean that others will too. Most helpful are reports that allows us easily to repeat the problem (the report below was very good). If you think that this problem might happen to other users too, please report the problem to 'GAP-Forum'. Installation problems and other problems that you think are not appropriate for the GAP forum should be reported to 'GAP-Trouble'. Thank you in advance. Martin. Here is the exchange Dietmar Koenig wrote in his e-mail message of 1994/08/24 A very curious problem occurs when running the following program in `gap': [program deleted] This program computes a presentation record for a finitely presented group depending on two distinct odd primes p,q. The occuring error looks like this: gap> nprec(3,5); Bus error (core dumped) pell:nquot-44> The same error occurs on any other machine available. It occurs when trying to execute the line r := PresentationFpGroup(FreeGroup(Length(gen))/[]); (rem.: Length(gen) at that stage is 80) and neither occurs with different primes (at least I did not find anymore) nor when preceeded by a successful run of a previous version of the same program nor if the command is divided into two parts. I do not necessarily need an answer to this problem since there is the easy solution of splitting the line, but people here asked me to report the error. Regards, Dietmar. I answered in my e-mail message of 1994/08/24 You have indeed found a genuine bug in the GAP kernel. It is very difficult to hit this problem, which is why it only happens for those two numbers and no others. Also note that it has been in the kernel since GAP 3.1, and it appears that you are the first to stumble over it. The problem is indeed in the function call PresentationFpGroup( FreeGroup(Length(gens))/[] ); When this is evaluated the following things happen 1) First 'PresentationFpGroup' is evaluated, which causes reading of the file "fptietze.g". 2) 'EvFunCall' remembers the definition of this function in a local variable 'hdDef'. 3) The argument is evaluated, causing evaluation of 'FreeGroup', which in turn causes reading of the file "fpgroup.g", which causes "fptietze.g" to be read again (this probably shouldn't happen in the first place). 4) This second reading of "fptietze.g" causes a redefinition of 'PresentationFpGroup', so that the old definition is now obsolete (of course both definitions are equal). 5) Creating the free group causes a garbage collection, which deallocates the old definition of 'PresentationFpGroup'. 6) So 'hdDef' now points to a deallocated function bag, and from then on things get progressively worse. If you call 'nprec' with different arguments, the problem does not appear, probably because no garbage collection happens between steps 4) and 6). If you split the statement into two statements, the problem does not appear, because "fpgroup.g" is read first and when the time comes to evaluate 'PresentationFpGroup' it is already known and "fptietze.g" is not read again. If you preceed the computation with a sucessful run of 'nprec', the problem does not appear, because the first run already reads all the appropriate files, so on redefinition of 'PresentationFpGroup' happens. A patch to the kernel that fixes this problem will be made available with the second upgrade. Thanks for your bug report. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From lmccarth@klingon.cs.umass.edu Fri Aug 26 15:10:00 1994 From: "Lewis McCarthy" Date: Fri, 26 Aug 94 15:10 -0400 Subject: Factoring over GaussianRationals Dear GAP Forum, I've been trying to factor in the polynomial ring over the Gaussian rationals without success. Could someone explain what I'm doing wrong in the following example ? Also, what syntax do I need to use to factor over other finite field extensions ? gap> x := Indeterminate(GaussianRationals); X(GaussianRationals) gap> x.name := "x"; "x" gap> f := Polynomial(GaussianRationals,[7 - 2 * E(4),5,4 + E(4)]); (4+E(4))*x^2 + 5*x + (7-2*E(4)) gap> Factors(PolynomialRing(f.baseRing),f); Error, sorry, can not factor in the ring in R.operations.Factors( R, r ) called from Factors( PolynomialRing( f.baseRing ), f ) called from main loop brk> f in PolynomialRing(f.baseRing); true Many thanks for everyone's time...specific RTFM pointers gratefully accepted -Lewis McCarthy (lmccarth@klingon.cs.umass.edu) From Alexander.Hulpke@Math.RWTH-Aachen.DE Sat Aug 27 14:17:00 1994 From: "Alexander Hulpke" Date: Sat, 27 Aug 94 14:17 +0200 Subject: Re: Factoring over GaussianRationals Dear GAP Forum, Lewis McCarthy asked: > I've been trying to factor in the polynomial ring over the Gaussian rationals > without success. Could someone explain what I'm doing wrong in the following > example ? Also, what syntax do I need to use to factor over other finite > field extensions ? Concerning general finite field extensions (and Your question in a previous mail) I will post a more general answer on Monday. > gap> x := Indeterminate(GaussianRationals); > X(GaussianRationals) > gap> x.name := "x"; > "x" > gap> f := Polynomial(GaussianRationals,[7 - 2 * E(4),5,4 + E(4)]); > (4+E(4))*x^2 + 5*x + (7-2*E(4)) > gap> Factors(PolynomialRing(f.baseRing),f); > Error, sorry, can not factor in the ring in > R.operations.Factors( R, r ) called from > Factors( PolynomialRing( f.baseRing ), f ) called from > main loop > brk> f in PolynomialRing(f.baseRing); > true This would be indeed the correct syntax. Unfortunately polynomial factorization over algebraic extensions is at the moment only available for generic algebraic extensions (created with 'AlgebraicExtension') and not for the special cyclotomic fields (like 'GaussianRationals'). >From an algorithmic point of view, it would be quite easy to adapt those algorithms for use also over cyclotomic fields, the problem is mainly fitting different data structures together. This has not been done yet (mainly because I was too lazy to add routines that no one needed at the point of writing the code). However, it is quite easy to circumvent this problem, the following code in GAP 3.4 does exactly what you want: gap> x:=X(Rationals);;x.name:="x";; gap> m:=x^2+1; # the minimal polynomial for Q(E(4)) x^2 + 1 Now construct a general algebraic extension isomorphic to GaussianRationals gap> GR:=AlgebraicExtension(m); AlgebraicExtension(Rationals,x^2 + 1) gap> e4:=RootOf(m); # the replacement to E(4) RootOf(x^2 + 1) gap> e4.name:="I";; Now construct the polynomial gap> y:=X(GR);y.name:="y";; X(AlgebraicExtension(Rationals,x^2 + 1)) gap> f:=Polynomial(GR,[7-2*e4,5,4+e4]); (I+4)*y^2 + 5*y + (-2*I+7) Factorize ... gap> Factors(f); [ I+4, y^2 + (-5/17*I+20/17)*y + (-15/17*I+26/17) ] (Note: The 'factor' I+4 is doe to the factoring process that requires monic polynomials and splits off leading coefficients initially.) Just another example to show factorization: gap> f:=y^2+9; y^2 + 9 gap> Factors(f); [ y + (-3*I), y + (3*I) ] > Many thanks for everyone's time... You're welcome. > specific RTFM pointers gratefully accepted Unfortunately the manual part about algebraic extensions has been forgotten to include. It will be added in the first patch (due in the next few days). If you are in urgent need of the documentation or have further questions feel free to contact me directly. Alexander Hulpke From Martin.Schoenert@Math.RWTH-Aachen.DE Sat Aug 27 16:58:00 1994 From: "Martin Schoenert" Date: Sat, 27 Aug 94 16:58 -0700 (PDT) Subject: Re: Factoring over GaussianRationals Lewis McCarthy writes in his e-mail message of 1994/08/27 I've been trying to factor in the polynomial ring over the Gaussian rationals without success. Could someone explain what I'm doing wrong in the following example ? Also, what syntax do I need to use to factor over other finite field extensions ? gap> x := Indeterminate(GaussianRationals); X(GaussianRationals) gap> x.name := "x"; "x" gap> f := Polynomial(GaussianRationals,[7 - 2 * E(4),5,4 + E(4)]); (4+E(4))*x^2 + 5*x + (7-2*E(4)) gap> Factors(PolynomialRing(f.baseRing),f); Error, sorry, can not factor in the ring in R.operations.Factors( R, r ) called from Factors( PolynomialRing( f.baseRing ), f ) called from main loop brk> f in PolynomialRing(f.baseRing); true Alexander Hulpke answered this question rather thoroughly. I would just like to make one small additional point. Whenever a GAP error messages reads 'Error, sorry, can not' (or if it has already been corrected 'Error, sorry, cannot' ;-), it means that you have come upon a limitation of GAP. I.e., you have asked a meaningfull question, and you have asked it in the correct way, but GAP has no method to do what you asked for. This ``has no method'' can mean different thing. In this particular case, as Alexander pointed out, the code is there, but the code that would connect this particular extension to the general case has not yet been written. Another meaning might be ``there is a well known algorithm for that problem, but have not yet implemented it''. A final meaning might be ``there is no known algorithm to solve this problem'' or even stronger ``there can be no algorithm to solve this problem'' (e.g. the word problem in general finitely presented groups). So if you see 'sorry', it is rather unlikely that you have done something wrong (or you have done something very wrong, like trying to factor over 'GaussianRationals', when you really wanted to factor over the 'Rationals' ;-). Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Alexander.Hulpke@Math.RWTH-Aachen.DE Mon Aug 29 12:30:00 1994 From: "Alexander Hulpke" Date: Mon, 29 Aug 94 12:30 +0200 Subject: Re: Finite Algebraic Field Extensions Dear GAP-Forum, In his mail, Lewis McCarthy wrote > I've just noticed that GAP currently only handles > finite fields, the field of rationals, and cyclotomic > extensions of the rationals. Are there any plans to > support arbitrary finite algebraic extensions of the > rationals ? This is probably crucial to the project > for which I'm considering GAP. I would like to make a few remarks on the status of algebraic field extensions in GAP: At the moment (this means GAP 3.4) GAP supports a basic implemen- tation of simple algebraic extensions for the rationals as well as finite fields. This is done by representing the extension as a factor of the polynomial ring modulo the ideal generated by an irreducible polynomial. These fields can be constructed by the command 'AlgebraicExtension'. Basic arithmetic as well as polyno- mial arithmetic and factorization is available for these fields. Unfortunately, the corresponding documentation has been forgotten in the distribution, it will be added in the first patch, which is due in the next few days (the patch will be announced in the GAP-Forum). However the file forum94b.txt (which is in the 'etc' directory of the GAP distribution) contains some example calcula- tions in a letter I wrote to the forum (dated 14. Jun 1994). Representation of algebraic elements is required to be as a poly- nomial in the primitive element, a change of the basis (which might be desirable for some computations in algebraic number theory) is not supported. At present time these routines do not allow multiple algebraic extensions. If needed field towers could be implemented easily. However, due to the method of representation, no assumptions can be made about embeddings of the algebraic extensions into other fields (i.e. the complex numbers). This means as well, that no assumption about which root of the minimal polynomial is taken as primitive element can be made (i.e. 2^(1/2) or - 2^(1/2) are both possible). With some basic algebraic number theory, it is possible to avoid some of those drawbacks by 'hand calculations', but necessary computations might become quite tedious. At present time, we have no plans to expand those features, as the current aviabilities are sufficient for our uses in group theory and its related areas and significant problems will arise when trying to overcome the mentioned drawbacks. Alexander Hulpke From lmccarth@klingon.cs.umass.edu Mon Aug 29 15:00:00 1994 From: "Lewis McCarthy" Date: Mon, 29 Aug 94 15:00 -0400 Subject: Substitutions in Polynomials Dear GAP Forum, I think this will be an easy question to answer. I'm looking for the GAP equivalent of e.g. Maple's 'subs' procedure, which performs substitutions of variables, expressions, etc. in expressions. In particular, I'd like to substitute a variable for an expression in a polynomial. I know I could write a routine using Position and the list accessing functions, but matters become complicated when it comes to, for example, exponents of the expression to be replaced. Is there an easier way ? Thanks -Lewis McCarthy (lmccarth@klingon.cs.umass.edu) From dfh@maths.warwick.ac.uk Wed Aug 31 16:34:00 1994 From: "Derek Holt" Date: Wed, 31 Aug 94 16:34 +0100 Subject: monoid presentation I have been trying to figure out a convenient way to convert a group presentation into a monoid presentation in GAP (so that inverses can be regarded as separate generators). The session below demonstrates that things can go wrong when you do unexpected things - not surprising really? Derek Holt. gap> a:=AbstractGenerator("a"); a gap> G:=Group(a,a^-1); Group( a, a^-1 ) gap> G.relators:=[a^3]; [ a^3 ] gap> Size(G); Error, the coset enumeration has defined more than 64000 cosets: etc. gap> Add(G.relators,a*a^-1); gap> G.relators; [ a^3, IdWord ] gap> Size(G); Error, Subword: illegal value at while LengthWord( rel ^ Subword( rel, 1, 1 ) ) < LengthWord( rel ) ... in RelatorRepresentatives( G.relators ) called from RelsSortedByStartGen( G, table ) called from AugmentedCosetTableMtc( G, H, -1, "_x" ) called from D.operations.Size( D ) called from Size( G ) called from main loop brk> Comments: 1) I suspect "a^-1" should not be allowed as a parameter to Group(..). 2) The fp-group functions clearly don't like having the empty word as a relator. One might reasonably call that a bug. From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Sep 01 01:36:00 1994 From: "Martin Schoenert" Date: Thu, 01 Sep 94 01:36 -0700 (PDT) Subject: Upgrade for GAP 3.4 patchlevel 0 (V3R4P0) to patchlevel 1 (V3R4P1) This is to announce the availability of the first upgrade for GAP 3.4. This upgrade brings version 3 release 4 patchlevel 0 (V3R4P0) to version 3 release 4 patchlevel 1 (V3R4P1). The priority of this upgrade is low. This upgrade adds the documentation for 'MaximalSubgroups', 'FrattiniSubgroup', 'SystemNormalizer', for the Transitive Groups Library, and for Algebraic Extensions of Fields to the manual. The functions were always there, but not documented. This upgrade fixes various small problems in the library, such as the bug in 'LowIndexSubgroupsFpGroup', which forgot to add the subgroup generators. This upgrade adds the character table of the 8th maximal subgroup in HN to the library of character tables. This upgrade fixes the ``recognition'' of groups the size of which is a product of at most three primes and provides the appropriate addition to the manual. This upgrade fixes a few problems related to the installation of the share packages ANU-Sq and MeatAxe. This upgrade does *not* change the kernel, i.e., you do not have to recompile. This also means that those problems that were in the kernel, i.e., not being able to apply 'String' to an abstract word, are not addressed by this upgrade. This will be left to the next upgrade. The upgrade is available as file 'upg3r4p1.dif.gz' on the 'ftp' server 'ftp.math.rwth-aachen.de'. It should be available on the other 'ftp' servers soon. This time I do not send out this upgrade as e-mail, it is simply too large. First unpack the upgrade with 'gunzip upg3r4p1.dif.gz'. Then read the instructions of the unpacked file 'upg3r4p1.dif', which contains instructions how to apply this upgrade. Enjoy, Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Sep 01 02:05:00 1994 From: "Martin Schoenert" Date: Thu, 01 Sep 94 02:05 -0700 (PDT) Subject: GAP Manual on the World Wide Web My first attempt at the GAP Manual in HTML format is now available on 'http://www.math.rwth-aachen.de/~mschoene/GAP-Manual/'. Each section is a single document, so that all documents are rather small. Be careful however with the index, it is 150 KByte large (and certainly needs to be split). All in all it is not (yet ;-) very fancy, but I think it is nonetheless rather useful. I invite you to try it out and e-mail me your suggestions, criticisms, etc. Note however, that I'm away for holidays for two weeks, so don't expect an answer before then. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Frank.Celler@Math.RWTH-Aachen.DE Thu Sep 01 09:58:00 1994 From: "Frank Celler" Date: Thu, 01 Sep 94 09:58 -0700 (PDT) Subject: Re: monoid presentation Dear Derek, I have been trying to figure out a convenient way to convert a group presentation into a monoid presentation in GAP (so that inverses can be regarded as separate generators). The session below demonstrates that wouldn't it be possible to simply double the number of generators? For example, one could call the generators "a", "b", ... and "ai", "bi", ... for the inverses. Or did I missunderstand your question? gap> f := FreeGroup( "a", "ai" ); Group( a, ai ) gap> f := f / [ f.1^3, f.1*f.2 ]; Group( a, ai ) gap> Size(f); 3 However, GAP will treat f as group and some functions might use inverses of the generators. So maybe this is not exactly what you need. What kind of GAP library functions do you have in mind that you want to apply to this "monoid"? gap> Add(G.relators,a*a^-1); GAP will always reduce abstract words, so that a*a^-1 (for an abstract generator a) will be the identity. At the moment, there is no way short of defining two abstract generators to persuade GAP not to reduce a*a^-1. 2) The fp-group functions clearly don't like having the empty word as a relator. One might reasonably call that a bug. Yes. best wishes Frank From fscimeh@chulkn.chula.ac.th Thu Sep 01 16:02:00 1994 From: "Mark Edwin Hall" Date: Thu, 01 Sep 94 16:02 +0700 Subject: PhD studies in computational algebra I hope this is an appropriate message for the GAP forum. A former MSc. student of mine is interested in working on a PhD in computational algebra, but neither she nor I have any idea of which universities offer a chance to work in this area. She would prefer to go to an English-speaking country, and is more interested in the mathematical side than the computer science side (i.e., she would definitely not be interested in working on something like the GAP kernel, but writing library functions would be O.K.). Can anyone give us some suggestions? Thanks. Mark ________________________________________________________________________ Mark E. Hall, Department of Mathematics, Chulalongkorn University Bangkok 10330, Thailand, fscimeh@chulkn.chula.ac.th From Alexander.Hulpke@Math.RWTH-Aachen.DE Thu Sep 01 11:52:00 1994 From: "Alexander Hulpke" Date: Thu, 01 Sep 94 11:52 +0200 Subject: Re: Substitutions in Polynomials Dear GAP Forum, Lewis McCarthy asked: > I'm looking for the GAP > equivalent of e.g. Maple's 'subs' procedure, which performs substitutions of > variables, expressions, etc. in expressions. GAP has (and will hardly ever get) a command of the 'universality' of the 'subs' command in Maple. The reason is (among others) the way of representing objects: Each GAP object is converted immediately to some kind of 'normal form' (it is evaluated immediately) while Maple deals with some kind of "expression sequence" (I do not have enough knowledge of Maple's internal workings to be more specific here). As a result, GAP does not need commands like 'collect', 'simplify' or 'normal'. (To be honest, this philosophy would break down when trying to allow function fields like in Maple.) On the other hand, this makes a generic "substitution" command unfeasible, as objects might have completely different internal representations (The way an object is printed out can be completely different from its internal representation). > In particular, I'd like to > substitute a variable for an expression in a polynomial. I know I could > write a routine using Position and the list accessing functions, but matters > become complicated when it comes to, for example, exponents of the expression > to be replaced. Is there an easier way ? You can use 'Value' to specialize the indeterminate to a value in the base ring. The replacement value might contain the indeterminate again, i.e. Value(f,x+1) would apply a Tschirnhaus transformation. Replacements in the coefficients will require some user function to work on the coefficients. However - unless you have a polynomial ring over a polynomial ring - the coefficients will be evaluated expressions already. Probably I have not understood completely what you want to do (after all, 'subs' is a very 'universal' command). If you are stuck with your problem after all, can you probably give a more specific description of the transformation(s) you want to apply. Alexander Hulpke From r.a.fenn@sussex.ac.uk Thu Sep 01 12:24:00 1994 From: "Roger A Fenn" Date: Thu, 01 Sep 94 12:24 +0200 Subject: Re: PhD studies in computational algebra > > I hope this is an appropriate message for the GAP forum. > > A former MSc. student of mine is interested in working on a PhD > in computational algebra, but neither she nor I have any idea of > which universities offer a chance to work in this area. She would > prefer to go to an English-speaking country, and is more interested > in the mathematical side than the computer science side (i.e., she > would definitely not be interested in working on something like > the GAP kernel, but writing library functions would be O.K.). Can > anyone give us some suggestions? Thanks. > > Mark > > ________________________________________________________________________ > > Mark E. Hall, Department of Mathematics, Chulalongkorn University > Bangkok 10330, Thailand, fscimeh@chulkn.chula.ac.th > > Dear Mark, although I am not a computer algebraist as such but a topologists she might be able to work at Sussex England. Get her to apply for a prospectus if interested. Roger Fenn From Frank.Celler@Math.RWTH-Aachen.DE Thu Sep 01 15:05:00 1994 From: "Frank Celler" Date: Thu, 01 Sep 94 15:05 -0700 (PDT) Subject: "incoming" Dear Gap Forum, the following exercises, programs, functions and utilities were sent to us and made available on our ftp server "ftp.math.rwth-aachen.de" (137.226.152.6). We emphasise once more that they are made available as sent without *any* warranty from us. Please mail any questions to the respective originators whose email addresses are given below. Further such submissions are welcome, best wishes Frank Celler and Joachim Neubueser +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ /tmp ---- exercises.zoo - unsorted Galway exercises, email - exercises from Peter Webb /pub/incoming ------------- AbStab.g,AbStab.doc - for representing elements of a permutation group in terms of its generators - written by Philip Osterlund GAP_html.zoo - GAP manual in HMTL format WeylMod.g,WeylMod.doc - WeylMod.g is a small collection of routines that work with representations of simple complex Lie algebras. It provides the following: - (1) definitions of Killing form for all finite simple Lie algebras, and all affine Lie algebras (Kak-Moody algebras) -- both direct and twisted. - (2) Weyl's equation for the dimension of a representation given its highest weight. - (3) Freudenthal's recursive algorithm to generate all weights and multiplicities of a representation given its highest weight. - written by Jacob Hirbawi ctpg.g,ctpgexam.g - This file contains a couple of GAP (version 3.3) functions that help in the following situation: Input: G a finitely presented group, H a homomorphic image of G and U a subgroup of H. Output: The abelian invariants of the complete preimage of U in G. - written by Werner Nickel fisk.zoo - GAP manual to EMACS info format translator - written by Steve Fisk gap.m,math.g,gapmath.doc - GAP to Mathematica, Mathematica to GAP translator - written by Sebastian Egner guave.tgz,guave.doc - Version 0.99 of GUAVA: a coding theory extension for GAP - written by Erik Roijackers, Jasper Cramwinckel, Reinald Baart stamp.g,stamp.doc - stamp.g -- Routines for computing in very large permutation groups - written by Steve Linton semigroup.g - functions for semi groups - semigroup.doc is at present still missing, but promised to be sent - written by Marcel Widi, email Tim Boykett From pfb3h@weyl.math.virginia.edu Thu Sep 01 12:43:00 1994 From: "Peter Floodstrand Blanchard" Date: Thu, 01 Sep 94 12:43 -0400 Subject: some bugs in DisplayCharTable Dear Mr. and Mrs. GAP, I just want to let you know about a few bugs in the function DisplayCharTable(). I have not yet installed the latest version of gap, so perhaps you have already fixed them. I have found three bugs: 1. Some tables cause alignment problems in output. I believe this is because widths are not computed correctly. The follwing commands will exhibit this bug in the third page out the displayed character table: gap> grp :=CyclicGroup(AgWords,48); Group( c48_1, c48_2, c48_3, c48_4, c48_5 ) gap> tbl := CharTablePGroup(grp);; gap> DisplayCharTable(tbl); 2. Not all of the features work. The manual page claims that one may select certain characters or a character to display. I have found that this only works for a list which begins with 1. I have illustrated this twice in the follwing session. gap> arec := rec( chars:= 5); DisplayCharTable(tbl,arec); rec( chars := 5 ) Error, List Element: [5] must have a value at charvals[i][cc] := stringEntry( chars[i][cc] ) ... in DisplayCharTable( tbl, arec ) called from main loop brk> quit; gap> arec := rec( chars:= [5]); DisplayCharTable(tbl,arec); rec( chars := [ 5 ] ) Error, List Element: [5] must have a value at charvals[i][cc] := stringEntry( chars[i][cc] ) ... in DisplayCharTable( tbl, arec ) called from main loop brk> quit; ---But this works: gap> arec := rec( chars:= [1..5]); DisplayCharTable(tbl,arec); 3. The same errors occur when one trys to select particular classes as the manual claims you should be able to. Illustrated below: gap> arec := rec( chars:= [2..5]); DisplayCharTable(tbl,arec); rec( chars := [ 2 .. 5 ] ) Error, List Element: [5] must have a value at charvals[i][cc] := stringEntry( chars[i][cc] ) ... in DisplayCharTable( tbl, arec ) called from main loop brk> quit; gap> arec := rec( classes := 2); DisplayCharTable(tbl,arec); rec( classes := 2 ) Error, Length: must be a list at ncols := Length( classes ) + 1 ... in DisplayCharTable( tbl, arec ) called from main loop brk> quit; gap> arec := rec( classes := [2..4]); DisplayCharTable(tbl,arec); rec( classes := [ 2 .. 4 ] ) Error, List Element: [2] must have a value at len := Length( charvals[i][col] ) ... in colWidth( classes[col + acol - 1] ) called from DisplayCharTable( tbl, arec ) called from main loop brk> quit; ------ But this works: gap> arec := rec( classes := [1..4]); DisplayCharTable(tbl,arec); I hope this helps. I use gap all the time, and really appreciate the work you folks are doing. I'm sorry I am unable to provide fixes for these bugs. Peter Blanchard From dana@brachot.jct.ac.il Fri Sep 02 07:56:00 1994 From: "Noah Dana-Picard" Date: Fri, 02 Sep 94 07:56 IST Subject: Re: PhD studies in computational algebra Your student can have a look in "Computational Algebraic Geometry and Computational Algebra" edited by David Eisenbud and Lorenzo Robbiano (Symposia Math. XXXIV), for example. There he can find what interests whom and where. Among other people, there are Bayer and Stillman (Macaulay), Giovini and Niesi (CoCoA). The first two in USA, the last two in Italy (Trieste I think). For CoCoa you can mail to cocoa@igecuniv.bitnet . At the same university in Genova you can contact Lorenzo Robbiano. I know about other people in France (A. Galligo in Nice, M. Chardin in Paris, ...) You can look also in the MEGA'92 volume (Birkhauser). Good luck, Thierry Dana-Picard From Thomas.Breuer@Math.RWTH-Aachen.DE Fri Sep 02 10:16:00 1994 From: "Thomas Breuer" Date: Fri, 02 Sep 94 10:16 WET Subject: Re: some bugs in DisplayCharTable Dear Mrs. and Mr. Forum, yesterday Peter Blanchard told about several problems with the 'DisplayCharTable' command. > 1. Some tables cause alignment problems in output. I tried Peter's example with versions 3.2, 3.3 and 3.4 of GAP, and could not reproduce a strange behaviour. For finding out what went wrong, it would be nice if Peter could send me the output he got. > 2. Not all of the features work. The manual page claims that one > may select certain characters or a character to display. I have > found that this only works for a list which begins with 1. > I have illustrated this twice in the follwing session. > > gap> arec := rec( chars:= 5); DisplayCharTable(tbl,arec); This did not work in GAP-3.3 but is fixed in GAP-3.4. > 3. The same errors occur when one trys to select particular > classes as the manual claims you should be able to. Illustrated > below: > > gap> arec := rec( classes := 2); DisplayCharTable(tbl,arec); This is indeed a bug that still exists in GAP-3.4. It will be fixed with the next upgrade. For the moment, one can get around it using gap> arec:= rec( classes:= [2] ); DisplayCharTable( tbl, arec ); Thanks for the nice bug report, Thomas Breuer (sam@math.rwth-aachen.de) From leonard@qmw.ac.uk Fri Sep 02 10:49:00 1994 From: "Leonard Soicher" Date: Fri, 02 Sep 94 10:49 BST Subject: Re: PhD studies in computational algebra The School of Mathematical Sciences, Queen Mary and Westfield College, (University of London), London E1 4NS, U.K., can provide Ph.D. opportunities in computational group and graph theory, as well as more traditional computer algebra applied to areas such as relativity theory. Any students who are interested in postgraduate work in computer algebra and algorithms are most welcome to contact Mrs. A. Cook at the above address, for more information. From ara@altdorf.ai.mit.edu Fri Sep 02 12:49:00 1994 From: "Allan Adler" Date: Fri, 02 Sep 94 12:49 +0200 Subject: Re: PhD studies in computational algebra I think you sent your message to the wrong person. I didn't ask about PhD studies in computer algebra. Allan Adler adler@ihes.fr From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Sep 02 12:53:00 1994 From: "Joachim Neubueser" Date: Fri, 02 Sep 94 12:53 +0200 Subject: Re: PhD studies in computational algebra Dear GAP-forum members, Mark E. Hall had in a letter to this forum asked which universities might offer a former student of his an opportunity to work on computational algebra for a PhD and had started his letter by saying > I hope this is an appropriate message for the GAP forum. Three answers have already been given in this forum, I have myself in a private letter pointed out a further good place to go to and maybe others have done the same. Much as I welcome this sense of helpfulness in the forum, and much as I hope that the student will now make a good choice between the various opportunities offered, I think we should keep the forum to its purpose of discussing GAP related matters. It was not clear to me from the letter of Mark E. Hall if the student wanted to work in CGT at all, let alone with GAP, (in which case I think there is a case for sending this letter to the GAP-forum) and in fact the answers point out a broad spectrum of other possibilities. I think there are other fora for the discussion of matters of Computer Algebra in general or such opportunity seeking and the members of this forum should not be overwhelmed with too many letters that at best are loosely connected with the reason for which they registered with this forum. Let me clarify this point further: I think that the forum is for *discussions*, that is, questions asked in the forum should also be answered in the forum. I have tried to see that this happened even in cases where the answers are likely to be not really of wide interest, but this means that also the questions to the forum should be of a kind that makes the answers likely to be interesting to more than the one who asked the question. It is for this reason that we have arranged the 'gap' address for reporting installations and asking about availability of GAP and the 'gap-trouble' address for installation and other rather local technical problems in addition to the gap-forum, and in fact the number of letters to gap-trouble that we also try to answer more or less by return mail, now is at least twice the number of letters to the gap-forum. I therefore ask your understanding for the attempt made above to keep the GAP-forum to its purpose. Thanks for your attention Joachim Neubueser From a.mathas@ic.ac.uk Mon Sep 05 12:30:00 1994 From: "Andrew Mathas" Date: Mon, 05 Sep 94 12:30 +0100 Subject: a suggestion and a question A suggestion: Shouldn't gap have a runtime option, -rc say, which turns off the automatic reading of the .gaprc file? I tend to put initialisation commands into the .gaprc file which set up the current project I am interested in; however sometimes I want to use "plain GAP" (not that it is really a problem to run the .gaprc file in these cases just unnecessary). A question on using AppendTo: I have a function which takes an optional argument of a filename and when this filename is given all output is dumped to this file. The way I have done this is as follows: fn := function(arg) local fnPrint, file, ... ; if IsString(arg[1]) then file := arg[1]; fnPrint := function(arg) local a; for a in arg do AppendTo(file, a); od; end; else fnPrint := Print; fi; ... end; and, of course, fnPrint is used throughout fn rather than Print. Now this works however when a filename is given as an argument to this function it is significantly slower than when the output goes to the screen. Is there anyway that I can improve this? It seems to me that the problem with how I have done this is that AppendTo gets called too often. This suggests creating a string from arg and then giving it to AppendTo; however, this doesn't work because most of my objects are records (with specialised printing instructions), which the String function can't handle. Any suggestions? Andrew Mathas specialised print formats -- Many years ago you told me that until you were forty you were very concerned about what people thought of you. Then you decided to be concerned about what you thought of other people instead. Vickram Seth, "A suitable boy" From Frank.Celler@Math.RWTH-Aachen.DE Mon Sep 05 13:53:00 1994 From: "Frank Celler" Date: Mon, 05 Sep 94 13:53 -0700 (PDT) Subject: Re: a suggestion and a question Dear Andrew, Shouldn't gap have a runtime option, -rc say, which turns off the automatic reading of the .gaprc file? I tend to put initialisation yes, this would be handy. A question on using AppendTo: ... Any suggestions? yes, there was a discussion about this subject in the GAP forum earlier this year, I append the three relevant emails. best wishes Frank +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ From: Gap Students Dear Gap Forum, To be able to call an external executable, it's necessary to write information to a file. As far as I know, GAP offers the functions PrintTo and AppendTo. These functions both open a file, write the information and close it again (am I right?) So when the function AppendTo is used within a loop, writing in each cycle a small amount of information, the file is opened and closed again very often, consuming a huge amount of time. Is there a way to open a file once, write all the information using a loop, and close it again? I have thought of using strings. First, all the information is stored in a string (using Concatenation), after which the whole string is written to a file using PrintTo. It turns out that, at least when working under DOS, this is even slower than the first option. Erik Roijackers / Gap Students +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ From: Steve Linton > > To be able to call an external executable, it's necessary to write > information to a file. As far as I know, GAP offers the functions > PrintTo and AppendTo. These functions both open a file, write the > information and close it again (am I right?) So when the function > AppendTo is used within a loop, writing in each cycle a small amount > of information, the file is opened and closed again very often, > consuming a huge amount of time. > This is an especially bad problem under DOS, as UNIX gains the benefit of disk caching. > Is there a way to open a file once, write all the information using > a loop, and close it again? I don't believe so. > > I have thought of using strings. First, all the information is stored > in a string (using Concatenation), after which the whole string is > written to a file using PrintTo. It turns out that, at least when > working under DOS, this is even slower than the first option. > Better is to put all the information into a GAP list and then write it out in one go. If your external program can't handle the resulting [] and ,s then you may have to write a little filter to strip them out. Another trick is to put the file on a RAM disk. Steve +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ From: Martin Schoenert Erik Roijackers writes in his e-mail message of 1994/03/23 To be able to call an external executable, it's necessary to write information to a file. As far as I know, GAP offers the functions PrintTo and AppendTo. These functions both open a file, write the information and close it again (am I right?) So when the function AppendTo is used within a loop, writing in each cycle a small amount of information, the file is opened and closed again very often, consuming a huge amount of time. This is correct. It is just barely tolerable under UNIX. Under TOS (on the Atari ST), it was impossible, because seeking to the end of the file took time proportional to the size of a file. So writing a file with lines took time ^2. I don't now whether this is true under DOS. He continues Is there a way to open a file once, write all the information using a loop, and close it again? Hmm, yes and no. In C you open a file, obtain a file pointer, and then use this to write to the file. Something like this is not possible in GAP. That means you *cannot* write something like file := OutputFile( "erwin" ); for i in [1..100] do PrintTo( file, Size( group[i] ), "\n" ); od; CloseFile( file ); We plan something like this, but not for the immediate future. But there is a hack, which may solve your problem. What you can do, is to put your loop in a simple function. Then you call this function from 'PrintTo'. I.e., do the following Dummy := function () for i in [1..100] do Print( Size( group[i] ), "\n" ); od; end; PrintTo( "erwin", Dummy() ); This makes use of the fact that when the arguments to 'PrintTo' are evaluated the current output file is the one opened by 'PrintTo', so everything that would usually go to '*stdout*' (i.e., the screen) is written to the file. This doesn't solve all problems, because you cannot interact with GAP while the output is computed and written to the file, but in many cases this is sufficient. He continues I have thought of using strings. First, all the information is stored in a string (using Concatenation), after which the whole string is written to a file using PrintTo. It turns out that, at least when working under DOS, this is even slower than the first option. In GAP 3.3 'Concatenation' has a ``small'' problem. It creates the output list as a list of characters (with each character taking 4 bytes) instead of as a string. So the reason why this is slower is probably because the string becomes so large that GAP has to do many garbage collections. You might want to try something like the following code. cache := ""; for i in [1..100] do Append( cache, String( Size( group[i] ) ), "\n" ); if 8192 < Length(cache) then AppendTo( "erwin", cache ); cache := ""; fi; od; Hope this helps, Martin. From Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Sep 05 14:43:00 1994 From: "Joachim Neubueser" Date: Mon, 05 Sep 94 14:43 +0200 Subject: Re: a suggestion and a question Dear Gap-forum, Frank Celler, who is not only one of those here who know about all the technicalities of GAP and even remember which have been explained and discussed in the GAP-forum not so long ago, but also is a kind soul and tries to give answers by return mail, has already answered the points raised in the letter of Andrew Mathas. However > Many years ago you told me that until you were forty you were very > concerned about what people thought of you. Then you decided to be > concerned about what you thought of other people instead. > Vickram Seth, "A suitable boy" and since I am over forty, do allow me a general remark. Of the many letters in the GAP-forum and even more in gap-trouble quite a few deal with problems that just concern the commodity of using GAP. Almost all of them are justified: yes, GAP could provide still more and better facilities of handling than it does at present. However, please do not forget when coming with such suggestions that we are just a small group of people in *mathematics*. There are of course questions and requests like the one to provide means of writing a GAP session that is interrupted to a file in such a way that it can be started again next day, the importance of which we fully see and even though that request is not as easily fulfilled as asked, we think about it and have it on the list of problems for which something or other must be done with a fairly high priority, since we know that it is essential for being able to do certain large tasks in GAP. However, may I ask that before suggesting something more that we could do to increase just the commodity of using GAP (not its real functionality), to ask yourself seriously, if the absence of this commodity really stops you from doing something. Please consider that we try to answer all such questions and requests, if possible at all even fast, and that already this takes a very big (and in fact increasing) part of our time. Nobody's perfect, GAP isn't, we aren't, still we like to survive, even while providing GAP and still trying to stay mathematicians. Thanks for your understanding. Joachim Neubueser From sibley@math.psu.edu Mon Sep 05 11:15:00 1994 From: "David Sibley" Date: Mon, 05 Sep 94 11:15 -0400 Subject: Re: a suggestion and a question Andrew Mathas wrote: >A suggestion: >Shouldn't gap have a runtime option, -rc say, which turns off >the automatic reading of the .gaprc file? I tend to put initialisation >commands into the .gaprc file which set up the current project I am >interested in; however sometimes I want to use "plain GAP" (not that it is >really a problem to run the .gaprc file in these cases just unnecessary). I agree this would be a useful option. But there is a nice way to organize gap usage into projects. Keep different projects in different directories, each such directory containing its own .gaprc. When you want to work on a particular project, change to the appropriate directory and start gap. That runs the .gaprc in the current directory and makes the files in that directory easily available -- no path prefix is needed to Read them. Of course, you can also write a script that changes to the appropriate directory before it starts gap, thus making everything automatic. With the above scheme you can get "plain gap" with no .gaprc by starting gap from some directory that doesn't have a .gaprc in it. I don't know how a .gaprc file in the home directory interacts with one in the current directory, as I don't have one in my home directory. From sibley@math.psu.edu Mon Sep 05 11:29:00 1994 From: "David Sibley" Date: Mon, 05 Sep 94 11:29 -0400 Subject: Re: a suggestion and a question Rereading the message I just submitted here, I realized it could easily be misinterpreted. It's meant as yet another suggestion, not a description of how things work. I'm sorry for not being clear about that. Also, just after sending it I got the message from Joachim Neubueser asking that we consider a bit more carefully before making such suggestions. Probably I should have done that, too. From Frank.Celler@Math.RWTH-Aachen.DE Tue Sep 06 10:08:00 1994 From: "Frank Celler" Date: Tue, 06 Sep 94 10:08 -0700 (PDT) Subject: Re: a suggestion and a question Dear Gap Forum, Rereading the message I just submitted here, I realized it could easily be misinterpreted. It's meant as yet another suggestion, not a description of how things work. I'm sorry for not being clear about that. one could realize such project files using a shell script similar to the following: #!/bin/sh gap=/usr/local/bin/gap-3.4 lib="/usd/gap/3.4/lib/;/usd/fceller/gap/lib/" mem="8m" if [ -e .gaprc -a `pwd` != '/usd1/fceller' ]; then exec /usr/local/bin/gap-3.4 -b -m $mem -l $lib .gaprc $* else exec /usr/local/bin/gap-3.4 -b -m $mem -l $lib $* fi One would need to set the paths correctly and the `pwd` test needs to be replaced if the script should be global one for all users, but I hope the idea is clear. best wishes Frank PS: We might provide a "-r" option to avoid reading the global ".gaprc" in the next kernel patch. From jcbhrb@cerf.net Tue Sep 06 14:06:00 1994 From: "Jacob Hirbawi" Date: Tue, 06 Sep 94 14:06 -0700 Subject: possible bug in square roots -- ER(N) This is either a bug in the function ER(N) ("square root of N") or I might be using the function outside its defined domain : for N = -n^2 when n is even the results don't look right : gap> ER(-4); 2 gap> ER(-36); 6 Jacob Hirbawi From Frank.Celler@Math.RWTH-Aachen.DE Wed Sep 07 09:56:00 1994 From: "Frank Celler" Date: Wed, 07 Sep 94 09:56 -0700 (PDT) Subject: Re: possible bug in square roots -- ER(N) Dear Jacob, This is either a bug in the function ER(N) ("square root of N") or I might be using the function outside its defined domain : the manual requires that N is a positive integer (see "ATALS irrationalities"), but I agree 'ER' should either signal an error or give the expected result or the manual should be even more definite in restricting the domain. However, one could write a square root function as SquareRootInt := function(N) if N < 0 then return EI(-N); elif 0 < N then return ER(N); else return 0; fi; end; best wishes Frank From lmccarth@klingon.cs.umass.edu Wed Sep 07 12:17:00 1994 From: "Lewis McCarthy" Date: Wed, 07 Sep 94 12:17 -0400 Subject: Re: possible bug in square roots -- ER(N) Jacob Kirbawi writes: > This is either a bug in the function ER(N) ("square root of N") > or I might be using the function outside its defined domain : Frank Celler writes: > the manual requires that N is a positive integer (see "ATALS > irrationalities"), but I agree 'ER' should either signal an error or > give the expected result or the manual should be even more definite in > restricting the domain. I started to write a reply just along these lines, but one thing stopped me short. At the end of 13.12 -- ATLAS irrationalities in the manual, there's an example which looks like this: gap> EW(16,3); EW(17,2); ER(3); ER(-3); EY(5); EB(9); 0 E(17)+E(17)^4+E(17)^13+E(17)^16 -E(12)^7+E(12)^11 E(3)-E(3)^2 E(5)+E(5)^4 1 where ER(-3) supposedly returns E(3)-E(3)^2. Either someone's got a fancy unreleased version of GAP, or they cheated a bit with the examples ;) -Lewis (lmccarth@klingon.cs.umass.edu) From Frank.Celler@Math.RWTH-Aachen.DE Thu Sep 08 10:09:00 1994 From: "Frank Celler" Date: Thu, 08 Sep 94 10:09 -0700 (PDT) Subject: Re: possible bug in square roots -- ER(N) Dear Lewis, Either someone's got a fancy unreleased version of GAP, or they cheated a bit with the examples ;) the manual just doesn't specify what will happen if one uses 'ER' with a negative integer. At the moment the function returns the correct result for odd, negative integers but this is indeed an undocumented feature and will either be documented in the next patch or the function will be changed to produce an error message and one has to use 'EI'. best wishes Frank From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Sep 08 10:11:00 1994 From: "Joachim Neubueser" Date: Thu, 08 Sep 94 10:11 +0200 Subject: Re: possible bug in square roots -- ER(N) In GAP Forum article 356 Lewis McCarthy writes > where ER(-3) supposedly returns E(3)-E(3)^2. > > Either someone's got a fancy unreleased version of GAP, or they > cheated a bit with the examples ;) Sorry, but this is neither a fancy unreleased version of GAP nor cheated. All versions GAP 3.2, 3.3, 3.4 do produce this answer, as you could easily have seen before writing. I am a little bit embarrassed about this unjustified supposition of cheating, in fact we do spend quite a bit of time with releases trying to make sure that examples given in the manual are what the respective version of GAP does produce. (It is such unnoticed work of several days that sometimes adds to releases coming late). All that is the case - as Frank has said - is that the manual first restricts N to be positive , but that among the examples ER is applied to an odd negative number, which according to the above restriction should not be done. In fact ER produces correct results for *some* negative N but not for all and this is not a desirable state of affairs. Thomas Breuer, who is looking at this part of GAP is not at Aachen at the moment, when he returns he will decide if the definition domain of N will be extended to all integers (with correct answers) or if the definition domain will be kept restricted to the positive integers (or some other subset of the integers) and an error message issued if the function is applied to illegal arguments, or some other totally consistent regulation. Perhaps we should have used the ATLAS formulation: 'Then for suitable integers N we define ...' , (ATLAS, p. xvii)! This way we could never be blamed for cheating. Joachim Neubueser From jaa@nov.cri.dk Thu Sep 08 11:45:00 1994 From: "Jan Andersen" Date: Thu, 08 Sep 94 11:45 +0100 Subject: .zoo file Hi. I've dowloaded the two .zoo files (bin3r4p1.zoo and gap3r4p1.zoo) and I'd like to put them on diskettes; but gap3r4p1.zoo is far too big, of course. Where would I find a set of .zoo files that will fit on HD PC-diskettes (1.4 Mbyte)? Also it seems that some of the filenames are too long for my DOS and OS/2 to handle, so I probably lose some of the files when I expand the file; is it possible to give those files shorter names? Thanks for your help. Jan Andersen (jaa@nov.cri.dk) From Frank.Celler@Math.RWTH-Aachen.DE Thu Sep 08 12:14:00 1994 From: "Frank Celler" Date: Thu, 08 Sep 94 12:14 -0700 (PDT) Subject: Re: .zoo file Dear Jan, I've dowloaded the two .zoo files (bin3r4p1.zoo and gap3r4p1.zoo) and I'd like to put them on diskettes; but gap3r4p1.zoo is far too big, of course. Where would I find a set of .zoo files that will fit on HD PC-diskettes (1.4 Mbyte)? for Patchlevel 0 there is shell script in "ftp.math.rwth-aachen.de:/tmp/PACKIT", it should be easy to change it to Patchlevel 1. Also it seems that some of the filenames are too long for my DOS and OS/2 to handle, so I probably lose some of the files when I expand the file; is it possible to give those files shorter names? The longer file names are in some share library packages which don't run under DOS (1), so you can just ignore these files, best wishes Frank (1) in order to avoid misunderstandings: share libaries written completely in GAP work well under any operating system (smash, grape without nauty and weyl), the filenames in these packages are DOS conform. The packages which use standalone C programs might or might not work under DOS but we haven't test this. If you find out that such a share library works under DOS or OS/2, it is good idea to tell the *author* which changes are necessary, the author of each package is given in chapter "Share Libraries". If no changes are necessary, send a notice to "gap-trouble" and we will put a short note into the manual that this package was test (and runs) under DOS or OS/2. XGAP requires X-Windows, however the libary part, for example the lattice drawing program, will work as soon as someone writes a DOS kernel. From sl25@cus.cam.ac.uk Thu Sep 08 12:48:00 1994 From: "Steve Linton" Date: Thu, 08 Sep 94 12:48 +0200 Subject: Re: .zoo file > > I've dowloaded the two .zoo files (bin3r4p1.zoo and gap3r4p1.zoo) > and I'd like to put them on diskettes; but gap3r4p1.zoo is far > too big, of course. Where would I find a set of .zoo files that > will fit on HD PC-diskettes (1.4 Mbyte)? > I've uploaded to samson.math.rwth-aachen.de:/pub/incoming sources and MS-DOS executables for a couple of little programs which I find very useful for this sort of thing. The programs are called split and merge, the files are split.c and merge.c (sources) and split.exe and merge.exe (DOS). There is a cover note in split-merge.doc. Steve From lmccarth@klingon.cs.umass.edu Thu Sep 08 17:13:00 1994 From: "Lewis McCarthy" Date: Thu, 08 Sep 94 17:13 -0400 Subject: Re: possible bug in square roots -- ER(N) Dear GAP Forum: Joachim Neubueser writes: > In GAP Forum article 356 Lewis McCarthy writes > > Either someone's got a fancy unreleased version of GAP, or they > > cheated a bit with the examples ;) > Sorry, but this is neither a fancy unreleased version of GAP nor > cheated. All versions GAP 3.2, 3.3, 3.4 do produce this answer, as > you could easily have seen before writing. I am a little bit > embarrassed about this unjustified supposition of cheating, in fact we > do spend quite a bit of time with releases trying to make sure that > examples given in the manual are what the respective version of GAP > does produce. (It is such unnoticed work of several days that > sometimes adds to releases coming late). I'm truly sorry, I didn't mean to offend anyone (that's why I used the ";)" ). I believed the example had really been run on a version of GAP, but Frank seemed to be saying that the function just wouldn't work on negative numbers --> contradiction. I never meant to suggest that anyone was making false claims about GAP's capabilities. -Lewis McCarthy (lmccarth@klingon.cs.umass.edu) From satterfieldj@alpha.hendrix.edu Sat Sep 10 11:06:00 1994 From: "NIPSY_RUSSELL" Date: Sat, 10 Sep 94 11:06 -0500 (CDT) Subject: GAP / Mathematica ...? Does there exist a "link," of sorts, between MacGAP and Mathematica? Or between GAP and Mathematica for PC's, for that matter? We are wanting to use GAP for calculations, and pipeline the results to Mathematica for graphical analysis. I am getting ready to begin working on this, and just wanted to see if it wasn't already out there somewhere. If there exist any other "linking" programs for GAP and other applications, that would be helpful also. Thanks in advance... Wade Satterfield Hendrix College satterfieldj@alpha.hendrix.edu From hwblist@machnix.mathematik.uni-stuttgart.de Sun Sep 11 14:40:00 1994 From: "Harald Boegeholz" Date: Sun, 11 Sep 94 14:40 +0200 Subject: Re: GAP / Mathematica ...? > Date: 10 Sep 94 11:06 -0500 (CDT) > From: NIPSY_RUSSELL > > We are wanting to use GAP for calculations, and pipeline the results to > Mathematica for graphical analysis. I am getting ready to begin working on > this, and just wanted to see if it wasn't already out there somewhere. > > If there exist any other "linking" programs for GAP and other applications, > that would be helpful also. I have recently been doing some calculations with GAP in conjunction with Maple V. I did this by running GAP under Emacs under OS/2 and the Windows version of Maple V at the same time (OS/2 can run Windows programs). I then used the clipboard to cut/paste any relevant data between GAP and Maple. The trick here is running GAP under Emacs. That way I have all GAP output in an Emacs buffer and can transfer large regions (greater than a screenful) to the clipboard. I know this procedure is not quite as automatic as you might like, but it'll get you going. hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From Werner.Nickel@Math.RWTH-Aachen.DE Mon Sep 12 11:44:00 1994 From: "Werner Nickel" Date: Mon, 12 Sep 94 11:44 WET Subject: Re: a suggestion and a question Dear GAP forum, David Sibley writes: > But there is a nice way to > organize gap usage into projects. Keep different projects in different > directories, each such directory containing its own .gaprc. When you > want to work on a particular project, change to the appropriate > directory and start gap. That runs the .gaprc in the current directory > and makes the files in that directory easily available -- no path > prefix is needed to Read them. Frank already posted one way to implement the suggestion above. Here is another solution. Change the .gaprc file in your home directory (the `global' .gaprc file) to the following. ## Beginning of .gaprc ## We have to be careful not to run into an infinite recursion if ## GAP is started in the home directory. That is the reason why ## the whole (global) .gaprc file has to be enclosed in the ## following if-statement. if not IsBound( HomeDirReadAlready ) then HomeDirReadAlready := true; ## ## Put the contents of your .gaprc here ## ## Read local .gaprc. if READ( ".gaprc" ) then Print( "#I Read local .gaprc\n" ); # Just a reminder fi; fi; When GAP (after the change has been made) is started, it first executes the code that used to be in your global .gaprc file and then reads the `local' .gaprc file in the current directory (if it exists). This allows you to put everything specific to your project into the local .gaprc file and to overwrite settings in the global .gaprc file. Settings that you want to use regardless where you start GAP should go into your global .gaprc file. All the best, Werner Nickel. From Thomas.Breuer@Math.RWTH-Aachen.DE Mon Sep 12 12:58:00 1994 From: "Thomas Breuer" Date: Mon, 12 Sep 94 12:58 WET Subject: Re: error in ER Dear Mrs. and Mr. GAP, sorry for the confusion about 'ER()' for negative integers . There was indeed a bug in the program which will be fixed in the next upgrade. Also the manual will tell about the possibility of negative arguments for 'ER'. Kind regards Thomas Breuer (sam@math.rwth-aachen.de) From Frank.Celler@Math.RWTH-Aachen.DE Mon Sep 12 13:01:00 1994 From: "Frank Celler" Date: Mon, 12 Sep 94 13:01 -0700 (PDT) Subject: Re: GAP / Mathematica ...? Dear Wade Satterfield, Does there exist a "link," of sorts, between MacGAP and Mathematica? Or between GAP and Mathematica for PC's, for that matter? our incoming directory contains the following: gap.m,math.g,gapmath.doc - GAP to Mathematica, Mathematica to GAP translator - written by Sebastian Egner we don't have Mathematica here, so I don't know, if this does exactly what you want, but it should be worthwhile to check if you can use it. best wishes Frank From jcbhrb@cerf.net Mon Sep 12 20:51:00 1994 From: "Jacob Hirbawi" Date: Mon, 12 Sep 94 20:51 -0700 Subject: IT type tables for space groups I am glad to see that the new release of GAP has tables of crystallographic groups and associated structures. Thanks to the developers for a great piece of work. The manual also mentions that further functions may be added at a later time. Here are a couple of items that would be nice to have : (1) A function that for a given space group gives an IT type table for the fixed points, symmetry operation types, ... . (2) A list of centering matrices. The second item might already exist in this release, but I couldn't find it. The first is outlined in the book "Crystallographic Groups in Four Dimensional Space". I actually tried to follow this outline but stumbled at the last, and probably trickiest, step. I can get the equations for the fixed points and determine the ones in the unit cell; but collecting this data into IT type format seems a bit more involved. In case anyone's interested here's the code I tried along with the example described in the above book : ################################################################################ FixedPoints:=function(sgrp) local data,type,dim,pgrp,elms,mats,invs,nmats,m,v,umats,points,u,w; data:=rec(); type:=sgrp.crSpaceGroupType; dim:=type[1]; # presentation and elements of the (finite) point group pgrp:=FpGroupQClass(type[1],type[2],type[3]); elms:=Elements(pgrp); # representatives of space group operations m:=Length(sgrp.generators); elms:=List(elms,x->MappedWord(x,pgrp.generators,sgrp.generators{[1..m-dim]})); # non-translation part of space group operations mats:=List(elms,mat->mat{[1..dim]}{[1..dim]}); # invariants of the operations : order,trace, determinant, ... # these can be used to get the Hermann symbol,IT symbol, ... of the operation invs:=List(mats, s->[OrderMat(s), TraceMat(s), DeterminantMat(s), Sum(Combinations([1..dim],2), x->s[x[1]][x[1]]*s[x[2]][x[2]]-s[x[1]][x[2]]*s[x[2]][x[1]])]); data.invariants:=invs; # normalize translation part to be in unit cell 0 <= ti < 1 nmats:=Copy(elms); for m in nmats do for v in m{[1..dim]} do w:=v[dim+1]-Int(v[dim+1]); if w<0 then w:=w+1; fi; if IsInt(w) then w:=0; fi; v[dim+1]:=w; od; od; # solve m*x + u = x for x; this is done by using 2*dim + 1 variables # {x1,...,xdim,t,u1,...,udim}; the result "umats" is a dim x dim+1 matrix # with the i-th row expressing xi as a linear combinations of t,u1,...,udim. umats:=[]; for m in nmats do v:=TransposedMat(Concatenation(TransposedMat(m-m^0),TransposedMat(m^0))); TriangulizeMat(v); Add(umats,-v{[1..dim]}{[dim+1..2*dim+1]}); od; data.equations:=umats; # generate fixed points in unit cell. # This uses the above equations and by trial an error on a set of ui's # in the range -2 <= ui <= 2 finds which points are in the unit cell. # this approach is probably not the best, but it does seem to work for # the examples I tried. points:=[]; for m in umats do w:=[]; for u in Tuples([-2..2],dim) do v:=m*Concatenation([1],u); if ForAll(v,x-> 0<=x and x<1) then AddSet(w,v);fi; od; Add(points,w); od; data.points:=points; return data; end; ################################################################################ ################################################################################ gap> example4:=FixedPoints( SpaceGroup(4,32,1,2,2) );; # the "invariants" here correspond to the order of the matrix,its trace, # its determinant,and one more invariant needed for n>3 gap> PrintArray( example4.invariants ); [ [ 1, 4, 1, 6 ], # identity 1111 [ 4, 0, 1, 2 ], # 44 [ 4, 0, 1, 2 ], # 44 [ 2, -4, 1, 6 ], # inversion 2222 [ 4, 0, 1, 2 ], # 44 [ 4, 0, 1, 2 ], # 44 [ 4, 0, 1, 2 ], # 44 [ 4, 0, 1, 2 ] ] # 44 # this corresponds to the equations for the fixed points of (S2,s2) in the book gap> PrintArray( example4.equations[3] ); [ [ -1/2, 0, -1/2, -1/2, 1 ], # x = -1/2 - u2/2 - u3/2 + u4 [ 1/2, 0, 1/2, 1/2, 0 ], # y = 1/2 + u2/2 + u3/2 [ 0, 0, -1/2, 1/2, 0 ], # z = -u2/2 + u3/2 [ -1/2, -1/2, -1/2, 0, 1 ] ] # w = -1/2 - u1/2 - u2/2 + u4 # this corresponds to the fixed points in the unit cell of (S2,s2) in the book gap> PrintArray( example4.points[3] ); [ [ 0, 0, 1/2, 0 ], [ 0, 0, 1/2, 1/2 ], [ 1/2, 1/2, 0, 0 ], [ 1/2, 1/2, 0, 1/2 ] ] # the equations for the centers of inversion -- (S3,s3) in the book gap> PrintArray( example4.equations[4] ); [ [ 0, 1/2, 0, 0, 0 ], [ 0, 0, 1/2, 0, 0 ], [ 0, 0, 0, 1/2, 0 ], [ 0, 0, 0, 0, 1/2 ] ] # the fixed points in the unit cell for the point inversion (S3,s3) # 12 of these 16 are fixed by other ("larger") operations gap> PrintArray( example4.points[4] ); [ [ 0, 0, 0, 0 ], [ 0, 0, 0, 1/2 ], [ 0, 0, 1/2, 0 ], [ 0, 0, 1/2, 1/2 ], [ 0, 1/2, 0, 0 ], [ 0, 1/2, 0, 1/2 ], [ 0, 1/2, 1/2, 0 ], [ 0, 1/2, 1/2, 1/2 ], [ 1/2, 0, 0, 0 ], [ 1/2, 0, 0, 1/2 ], [ 1/2, 0, 1/2, 0 ], [ 1/2, 0, 1/2, 1/2 ], [ 1/2, 1/2, 0, 0 ], [ 1/2, 1/2, 0, 1/2 ], [ 1/2, 1/2, 1/2, 0 ], [ 1/2, 1/2, 1/2, 1/2 ] ] # of the 8 operations in the group there are only 5 distinct fixed point sets: # this is consistent with S1,S2=S4,S3,S5=S7,S6=S8 in the book. gap> Length(Set(example4.points)); 5 ################################################################################ Jacob Hirbawi From Joachim.Neubueser@Math.RWTH-Aachen.DE Wed Sep 14 14:48:00 1994 From: "Joachim Neubueser" Date: Wed, 14 Sep 94 14:48 +0200 Subject: Example (fwd) Dear Gap Forum, Mike Newman has sent us a very nice example of the detailed investigation, using GAP, of the structure of a finite soluble group, given originally only by a (deficiency zero) presentation. With his permission, we have made this available on our ftp server "ftp.math.rwth-aachen.de" (137.226.152.6). Although hardly necessary this time, we emphasise also in this case that it is made available, as sent, without *any* warranty from us. Please mail any questions to the originator whose email address is given below. /pub/incoming ------------- ... minnesota.exa - this is an analysis, using GAP, of a deficiency zero presentation .... - by Mike F. Newman Frank Celler and Joachim Neubueser From tim@bruckner.stoch.uni-linz.ac.at Thu Sep 15 10:13:00 1994 From: "Tim Boykett" Date: Thu, 15 Sep 94 10:13 +0200 Subject: Re: semigroups I have just been told there was an ugly bug in the semigroup.g file, so I will upload the improved version right now It will be in the incoming directory Apologies to anyone who has had trouble with the routines, apparently everything to do with homomorphisms. "mea culpa" comes from a strange man behind me :-) Regards Tim Boykett From jcbhrb@cerf.net Sat Sep 17 21:16:00 1994 From: "Jacob Hirbawi" Date: Sat, 17 Sep 94 21:16 -0700 Subject: a problem with factoring polynomials I am having this problem with factoring polynomials : the product of the factors doesn't match the original polynomial. I am using GAP 3.4 and I am fairly sure this example used to work in the previous release. ################################################################################ t:=Indeterminate(Rationals); t.name:="t"; p:=t^35 - 3*t^33 - t^32 + 3*t^31 + 3*t^30 - 2*t^29 - 4*t^28 + 3*t^27 + 5*t^26 - 2*t^25 - 6*t^24 - 2*t^23 + 4*t^22 + 3*t^21 - t^20 - t^19 + t^16 + t^15 - 3*t^14 - 4*t^13 + 2*t^12 + 6*t^11 + 2*t^10 - 5*t^9 - 3*t^8 + 4*t^7 + 2*t^6 - 3*t^5 - 3*t^4 + t^3 + 3*t^2 - 1; gap> p; t^35 - 3*t^33 - t^32 + 3*t^31 + 3*t^30 - 2*t^29 - 4*t^28 + 3*t^27 + 5*t^26 - 2*t^25 - 6*t^24 - 2*t^23 + 4*t^22 + 3*t^21 - t^20 - t^19 + t^16 + t^15 - 3*t^ 14 - 4*t^13 + 2*t^12 + 6*t^11 + 2*t^10 - 5*t^9 - 3*t^8 + 4*t^7 + 2*t^6 - 3*t^ 5 - 3*t^4 + t^3 + 3*t^2 - 1 gap> f:=Factors(p); [ t - 1, t - 1, t - 1, t - 1, t - 1, t - 1, t - 1, t + 1, t + 1, t + 1, t + 1, t^2 - t + 1, t^2 + t + 1, t^6 + t^5 + t^4 + t^3 + t^2 + t + 1, t^12 + t^11 + t^10 + t^9 + t^8 + t^7 + t^6 + t^5 + t^4 + t^3 + t^2 + t + 1 ] gap> Product(f); t^33 - t^32 - 3*t^31 + 3*t^30 + 3*t^29 - 3*t^28 - 2*t^27 + t^26 + 4*t^25 - 6*t^23 + 4*t^21 - t^19 + t^14 - 4*t^12 + 6*t^10 - 4*t^8 - t^7 + 2*t^6 + 3*t^ 5 - 3*t^4 - 3*t^3 + 3*t^2 + t - 1 gap> p=Product(f); false ################################################################################ I also have this minor question that is unrelated to the above but isn't worth a seperate post : The internal routine "AddCoeffs" behaves differently in the new release; the trailing zeros are not truncated. I have been using this function in some code I wrote because of its speed; is it bad practice to use internal functions? Jacob Hirbawi From Frank.Celler@Math.RWTH-Aachen.DE Mon Sep 19 10:10:00 1994 From: "Frank Celler" Date: Mon, 19 Sep 94 10:10 -0700 (PDT) Subject: Re: a problem with factoring polynomials Dear Jacob Hirbawi, I also have this minor question that is unrelated to the above but isn't worth a seperate post : The internal routine "AddCoeffs" behaves differently in the new release; the trailing zeros are not truncated. I have been using this function in some code I wrote because of its speed; is it bad practice to use internal functions? I wouldn't say, that it is bad pratice to use undocumented functions, for a particular applictation some of the these functions are indeed much faster, but in this case one should be prepared that the functions are changed *without* notice. We promised to avoid changes for documented functions and if such changes are necessary we will announce them or even do an opion poll (e.g. stab chains for permutation). But auxillary (internal or external) functions might be changes without warning, although we try to avoid even this, but sometimes it is necessary, e.g., 'AddCoeffs' was changed because the function is now also used in other contexts than polynomials. best wishes Frank From Alexander.Hulpke@Math.RWTH-Aachen.DE Mon Sep 19 10:53:00 1994 From: "Alexander Hulpke" Date: Mon, 19 Sep 94 10:53 +0200 Subject: Re: a problem with factoring polynomials Dear GAP-Forum, Jacob Hirbawi asked: > I am having this problem with factoring polynomials : the product of the > factors doesn't match the original polynomial. [example deleted] This is indeed an error. Mea culpa (I should have learned in the meantime to check also seemingly trivial cases). > I am using GAP 3.4 and I > am fairly sure this example used to work in the previous release. In the progress of 3.3 to 3.4 the factorization routines were rewritten (actually, we did not even tell the user about them be- fore) to enhance performance. (So you got the wrong result much faster...) Unfortunately, the part of the routine, which deals with non- squarefree polynomials got an error and stupidly I only checked the algorithm with squarefree polynomials (after all, this is the interesting part of the routine). This bug will be fixed in the next patch. If you need this fix urgent, you can (but please note, that this might get you in trouble when applying the next fix!) edit the library file polyrat.g and replace Degree(g) mod Degree(r) = 0 by Degree(g) >= Degree(r) in lines 1629 and 1634. With this fix, the polynomial is factorized correctly. Alternatively, you could call Factors only for squarefree polynomials and handle the square part yourself in the meantime. Please excuse my short-sightedness, Alexander Hulpke From jaroslav.gurican@mff.uniba.cs Fri Sep 16 17:10:00 1994 From: "Jaroslav Gurican" Date: Fri, 16 Sep 94 17:10 +0200 Subject: [no subject] Dear GAP forum, does LLL-algorithm (or some of modifications) offer possibility to decide memebship (of some element in Z^n in the given lattice? I need some bibliography on this topic, if possible. (I would like to avoid excursions to Preburger arithmetic). Jaroslav Gurican P.S.: The answers (if any) should go to my own address, I think. gurican@fmph.uniba.sk From Thomas.Breuer@Math.RWTH-Aachen.DE Tue Sep 20 15:12:00 1994 From: "Thomas Breuer" Date: Tue, 20 Sep 94 15:12 WET Subject: LLL {{Subject}} membership Dear Mrs. and Mr. Forum, Jaroslav Gurican writes > does LLL-algorithm (or some of modifications) offer possibility to > decide memebship (of some element in Z^n in the given lattice? > I need some bibliography on this topic, if possible. > (I would like to avoid excursions to Preburger arithmetic). I do not see that the LLL algorithm can be used as a general method to decide membership in lattices. One could think of adding the element in question to a lattice basis, reduce the vectors using the LLL algorithm, and then look at the transformation matrix whether the new vector has been expressed in terms of the old basis. But if this is not the case then of course this doesn't prove that the vector is not contained in the lattice. (On the other hand, I cannot prove that the LLL algorithm cannot be used to decide membership.) A possibility of testing membership would be to transform the matrix whose rows form a lattice basis into diagonal form, and to apply the column transformations to the element in question; then membership can be read off easily. The problem with this is the ``entry explosion'' during the process of diagonalizing the matrix. Kind regards Thomas Breuer (sam@math.rwth-aachen.de) From mas023@bangor.ac.uk Tue Sep 20 14:30:00 1994 From: "Chris Wensley" Date: Tue, 20 Sep 94 14:30 +0000 (GMT) Subject: MapByFunction Dear GAP Forum It seems reasonable to hope that MappingByFunction can be used inside a loop to produce a list of homomorphisms. However, it appears that the definition of f(x) may depend only on x and constants, and not the loop variable or associated parameters. Is there a way round this? The following listing illustrates the problem. ---------------------------------------------------------------- gap> c6 := Group( (1,2,3,4,5,6) );; gap> c6.name := "c6";; gap> pow := 0 * [1..6];; gap> for i in [1..6] do pow[i] := MappingByFunction( c6, c6, x->x^i ); od; gap> pow; [ MappingByFunction( c6, c6, function ( x ) return x ^ i; | | (6 times --- all using "i") | end ), MappingByFunction( c6, c6, function ( x ) return x ^ i; end ) ] gap> g:=(1,2,3,4,5,6);; gap> for i in [1..6] do Print( g^pow[i],", "); od; Print("\n"); (1,2,3,4,5,6), (1,3,5)(2,4,6), (1,4)(2,5)(3,6), (1,5,3)(2,6,4), (1,6,5,4,3,2), (), gap> # Note: "i" now has value 6 gap> for j in [1..6] do Print( g^pow[j],", "); od; Print("\n"); (), (), (), (), (), (), gap> LogTo(); --------------------------------------------------------------- Chris Wensley University of Wales at Bangor Email: mas023@bangor.ac.uk From Frank.Celler@Math.RWTH-Aachen.DE Tue Sep 20 17:10:00 1994 From: "Frank Celler" Date: Tue, 20 Sep 94 17:10 -0700 (PDT) Subject: Re: MapByFunction Dear Chris Wensley, The following listing illustrates the problem. yes, this behaviour is correct, a smaller example is gap> i := 10; 10 gap> f := x -> x+i; function ( x ) ... end gap> f(10); 20 gap> i := 20; 20 gap> f(10); 30 there was a discussion about a similar subject some time ago, I will append the relevant mail, the question was a completely different one, but the mail explains a few things about GAP variables and identifiers (and a few more things), together with the chapter "The Programming Language" from the GAP manual this should explain why this behaviour was chosen. The short version is: If you write "x -> x^i" then "i" still refers to the globale variable "i", the expression is not expanded to "x -> x^6". You have various ways to solve your problem: - create a "creator" function: f := function(i) return x -> x^i; end; l := List( [1..10], i -> f(i) ); now l[n] will be the function x -> x^n. - if the mapping is always a group *homomorphism* it might be better to use 'GroupHomomorphismByImages', i.e., l := List( [1..10], i -> GroupHomomorphismByImages( c6, c6, c6.generators, OnTuples(c6.generators,i) ) ); which solution will be faster depends on the kind of mapping and type of group you have. best wishes Frank ----------------------------------------------------------------------------- From: Martin.Schoenert@Maths.RWTH-Aachen.DE Eamonn O'Brien writes in his e-mail message of 2-Nov-92 Why does the following piece of code not work? It generates an error message Error, Variable 'G' must have a value at .. I know that by not declaring G locally within the procedure I can persuade it to work OK -- but if I do that, it overwrites whatever existing value G had. This may have serious side effects -- where for example I have a group G defined in Gap, and I now want to read another group called G defined in "file.g" and return it from ReadFromFile to the main level under some other name. Is there any sensible way to achieve this without wiping out my existing G? I guess that I can encase the definition of G in the file within a function and call that function. But are there other approaches? Is this problem something which is intended /unavoidable / or a bug? Thanks, Eamonn O'Brien obrien@pell.anu.edu.au ################################################## #code to read value from file and return it ReadFromFile := function () local exist, G; exist := READ("file.g"); return G; end; #ReadFromFile l := ReadFromFile (); Print ("The value returned from the function is ", l, "\n"); ############################################################ #contents of file.g G := 5; Let me try to explain why this works this way. I make this fairly long because most descriptions of programming languages are quite brief in this regard (in fact most fail to describe the difference between identifiers and variables). On the one hand there are *variables*. A variable is an abstract entity. Variables are either global variables, formal argument variables of functions, or local variables of functions. Global variables are created on demand. With each function call GAP creates one variable for each formal argument (i.e., for each identifier that appears in the parenthesis following the 'function' keyword in the function's definition), and one variable for each local (i.e., for each identifier that follows the 'local' keyword in the function's definition). On the other hand there are *identifiers*. They are just strings of characters that appear in GAP's input (there are certain rules which rule what is considered an identifier as opposed to an integer or a keyword, but this does not interest us here). Each variable has a unique identifier, which is usually called its *name*. The interesting connection is the one that goes from identifiers to variables. So for example in the following piece of code there are three variables whose name is 'a' and we must define to which such variable the identifier 'a' in the 'Print' statement is referring to. a := "global a"; f := function () local a; a := "a of f"; h(); end; g := function () local a; a := "a of g"; h := function () Print( a, "\n" ); end; f(); end; g(); There are three variables called 'a', so there are three different possibilities. The first is to argue that the function 'h' has no local variable called 'a', so the identifier 'a' must refer to the global variable (and 'Print' should print "global a"). Another interpretation is that when the 'Print' statement is executed the last *dynamically* created variable called 'a' is the one of 'f', so the identifier 'a' in the 'Print' statement should refer to this variable (and 'Print' should print "a of f"). This point of view is usually called *dynamical scoping*. The last interpretation is that when one reads the text the last variable that was introduced before the 'Print' statement is that of the function 'g', so the identifier 'a' in the 'Print' statement should refer to this variable (and 'Print' should print "a of g"). This point of view is usually called *lexical scoping*. If you try this example in GAP you will see that the last interpretation is the one adopted in GAP. Lexical scoping is considered a *good thing* (by the Lisp community, which initially tried dynamical scoping), because it has the following property (usually called *alpha-renaming*): If one replaces the identifier of an argument or a local variable of a function with another identifier that is not used within the functions body, the behavior of any program that calls this function does not change. For example assume for the moment that GAP uses dynamical scoping. Then the above example would print "a of f". If we now change the name of the local variable of 'f' from 'a' to 'aa', calling 'g' would suddenly print "a of g" (because this becomes the dynamically innermost instance of a variable called 'a'). Thus lexical scoping confines the scope where the name of a variable makes any difference to a lexically apparent part of the source text (hence the name). The philosophy behind this is the idea that a programming language should be as little surprising as possible. And having a program's behavior changed simply by renaming a local variable 'i' to 'ThisIsALoopVariable' is surprising. If we look at Eamonn's code fragment, we see that what he asks for would violate this property. Suppose for the moment that the definition of the local variable called 'G' would indeed capture the assignment in 'file.g'. If we now would change the name of this local variable from 'G' to 'H' in the function 'ReadFromFile' but not in 'file.g', then suddenly the program would (mysteriously) behave different, because now the assignment in 'file.g' would assign to the global variable with the name 'G' (or a local variable of the name 'G' that happens to be active when we execute 'ReadFromFile'). I hope that this rather long explanation impressed you above on the virtues of lexical scoping that you don't actually want to use the following hack ;-) ReadFromFile := function ( name ) local oldG, newG, exists; if IsBound( G ) then oldG := G; fi; exists := READ( name ); newG := G; if IsBound( oldG ) then G := oldG; else Unbind( G ); fi; return newG; end; Martin. From Martin.Schoenert@Math.RWTH-Aachen.DE Tue Sep 20 22:17:00 1994 From: "Martin Schoenert" Date: Tue, 20 Sep 94 22:17 -0700 (PDT) Subject: Re: MapByFunction Chris Wensley writes in his e-mail message of 1994/09/20 It seems reasonable to hope that MappingByFunction can be used inside a loop to produce a list of homomorphisms. However, it appears that the definition of f(x) may depend only on x and constants, and not the loop variable or associated parameters. Is there a way round this? The following listing illustrates the problem. ---------------------------------------------------------------- gap> c6 := Group( (1,2,3,4,5,6) );; gap> c6.name := "c6";; gap> pow := 0 * [1..6];; gap> for i in [1..6] do pow[i] := MappingByFunction( c6, c6, x->x^i ); od; ['pow' now contains 6 mappings that all raise the argument to the same power 'i'] This is a tricky issue, so pardon me if I write something about it, even Frank already answered it. You write ``... depends ... not on the loop variable''. In the fact the problem is that all function depend on the loop variable, with the emphasize being on the *variable*. There is only one variable, which may refer to different values over the time, but it is always the same variable. And since there is only one variable, all six functions are equal (even though GAP's '=' operator does not see this). Put in another way. When the function 'x->x^i' is evaluated, which happens once for every iteration through the loop, the *identifier* 'i' is mapped to the global variable with that identifier, since the statement does not appear in a function definition with a local variable with identifier 'i'. But the body of the function 'x->x^i' then refers to that variable, which is the same variable on each iteration, not to its current value, which is different for each iteration. (Dangerous Bend! Actually the mapping from identifier to variable happens when the function literal is read, and the function creation during evaluation augments the reference to the variable with a so called *context*, but this is only of technical interest). Later when such a function is called, e.g., when one of the mappings is applied, the value of that the global variable with identifier 'i' refers to *at this moment* is used. How can we solve your problem. First we must somehow force evaluation of the loop variable 'i'. Second because we want 6 different functions, we need 6 different *variables*, which we must somehow create dynamically. Fortunately this is possible, because each function call creates a new variable for each formal argument and each formal local variable. gap> PowerFunction := function ( p ) return x -> x^p; end; gap> for i in [1..6] do > pow[i] := MappingByFunction( PowerFunction(i) ); > od; Lets take a look at what happens during each loop iteration. 1) the global variable 'i' is evaluated to its value. 2) a new variable for the formal argument 'p' of 'PowerFunction' is created. 3) the value computed in step 1) is assigned to this variable. 4) the function 'x->x^p' is created, it refers to the newly created variable, which refers to the current value of the loop variable (and will so forever). 5) this function is passed to 'MappingByFunction', which creates the corresponding mapping. I hope this helps somewhat. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany