This file contains the mails sent to the GAP forum in April-June 1994. Name Email address Mails Lines Joachim Neubueser Joachim.Neubueser@Math.RWTH-Aachen.DE 8 229 Martin Schoenert Martin.Schoenert@Math.RWTH-Aachen.DE 7 239 Alexander Hulpke Alexander.Hulpke@Math.RWTH-Aachen.DE 6 273 Leonard Soicher leonard@qmw.ac.uk 5 73 Harald Boegeholz hwblist@machnix.mathematik.uni-stuttgart.de 4 137 Chris Wensley mas023@bangor.ac.uk 3 193 Allan Adler ara@altdorf.ai.mit.edu 3 55 Chris Charnes charnes@osiris.cs.uow.edu.au 3 12 Volkmar Felsch Volkmar.Felsch@Math.RWTH-Aachen.DE 2 412 Eamonn O'Brien eamonn.obrien@maths.anu.edu.au 2 151 Sebastian Egner egner@hermes.zkm.de 2 110 Peter Mueller mueller@mi.uni-erlangen.de 2 87 Frank Celler Frank.Celler@Math.RWTH-Aachen.DE 2 83 BARTHOLDI Laurent lbartho@scsun.unige.ch 2 44 Jacob Hirbawi jcbhrb@cerf.net 2 40 Steve Linton sl25@cus.cam.ac.uk 2 34 Nishit Kumar kumar@cs.ucf.edu 2 30 Jasper Cramwinckel j.cramwinckel@twi.tudelft.nl 1 115 Akos Seress akos@math.ohio-state.edu 1 47 Tomaz Pisanski tomo.pisanski@uni-lj.si 1 41 Jens Baek Joergensen jbj@daimi.aau.dk 1 39 Kenneth H. Simpson ken@poincare.arc.nasa.gov 1 37 Wettl Ferenc wettl@erie.vma.bme.hu 1 36 Derek Holt dfh@maths.warwick.ac.uk 1 35 Thomas Breuer Thomas.Breuer@Math.RWTH-Aachen.DE 1 25 Martin Wursthorn pluto@machnix.mathematik.uni-stuttgart.de 1 19 Evelyn Hart" "agnesi::hart"@physics.hope.edu 1 18 Dima Pasechnik dima@maths.uwa.edu.au 1 17 Gap Students studgap@twi.tudelft.nl 1 13 Alice Niemeyer alice@maths.uwa.edu.au 1 13 Catherine Greenhill greenhil@maths.ox.ac.uk 1 12 William Kocay william_kocay@macmail.cs.umanitoba.ca 1 11 Gerald Cliff gcliff@vega.math.ualberta.ca 1 9 Tim Hsu timhsu@math.princeton.edu 1 9 Wang wang@maths.uwa.edu.au 1 8 Peter Jipsen pjipsen@iastate.edu 1 6 Dana-Picard Noah dana@bimacs.cs.biu.ac.il 1 5 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 leonard@qmw.ac.uk Sun Apr 3 20:31:00 1994 From: "Leonard Soicher" Date: Sun, 03 Apr 94 20:31 +0200 Subject: AutGroupGraph limits in GRAPE Dear Forum, Recently there was a question about the limits on graph size for AutGroupGraph, but I appear to have lost the original email. The nauty 1.7 package (used by GRAPE 2.1 to calculate the automorphism group of a graph) requires the maximum number of vertices of a graph to be set at compile time. The default for GRAPE 2.1 is 1024. You can change this by editing gap-directory/pkg/grape/nauty17/Makefile and changing 1024 to 2048 (say), and then completely re-installing the GRAPE package. Regards, Leonard Soicher. From dana@bimacs.cs.biu.ac.il Wed Apr 6 14:59:00 1994 From: "Dana-Picard Noah" Date: Wed, 06 Apr 94 14:59 +0200 Subject: gap 3.4 In a recent letter to the forum was announced that "soon" will be released GAP's next version. Is there already a time range? Thanks, Th. Dana-Picard From jbj@daimi.aau.dk Fri Apr 8 12:43:00 1994 From: "Jens Baek Joergensen" Date: Fri, 08 Apr 94 12:43 +0000 Subject: PermGroupOps.SubgroupProperty - Complexity? Dear Gap forum. I am interested in the computational complexity of the GAP-function PermGroupOps.SubgroupProperty. Consider the call: PermGroupOps.SubgroupProperty(G, P); where G is some permutation group and P:G->Bool is some property. If every element in G satisfies P, it seems to me like this function call terminates very quickly - even when G is large. Is this observation correct and can it be justified be referring to some general property of the backtrack algorithm? (I assume that PermGroupOps.SubgroupProperty is the GAP-implementation of the backtrack algorithm described, e.g., in Butler's book "Fundamental Algorithms for Permutation Groups"). If G is the symmetrical group for some natural number n, I think I can prove that the backtrack algorithm terminates after having tested exactly n-1 permutations. Does this result generalize to all kinds of permutation groups? Perhaps the number of permutations to test is equal to the number of elements in the considered base for G? I am definitely not an expert in the field of computational group theory (or group theory for that matter), so it might be a quite well-known result I am looking for. Any help and/or references will be greatly appreciated. Thanks, Jens Baek Joergensen Computer Science Department, Aarhus University Ny Munkegade, Bldg. 540 DK-8000 Aarhus C Denmark From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Apr 8 13:33:00 1994 From: "Joachim Neubueser" Date: Fri, 08 Apr 94 13:33 +0200 Subject: Re: gap 3.4 > Wed Apr 6 14:04:56 1994 > In a recent letter to the forum was announced that "soon" will be > released GAP's next version. Is there already a time range? > Thanks, > Th. Dana-Picard The next version, GAP 3.4 is presently being put together. It will contain several new components. In particular for this reason testing it, extending the manual, etc will take some time, hence we do not want to make definite promises, but we hope that we can release GAP 3.4 in the second half of May. Joachim Neubueser From akos@math.ohio-state.edu Fri Apr 8 11:40:00 1994 From: "Akos Seress" Date: Fri, 08 Apr 94 11:40 -0400 Subject: Re: PermGroupOps.SubgroupProperty - Complexity? Dear GAP forum, Jens Baek Joergensen asks: > Consider the call: > > PermGroupOps.SubgroupProperty(G, P); > > where G is some permutation group and P:G->Bool is some property. If every > element in G satisfies P, it seems to me like this function call terminates > very quickly - even when G is large. Is this observation correct and can it > be justified be referring to some general property of the backtrack > algorithm? (I assume that PermGroupOps.SubgroupProperty is the > GAP-implementation of the backtrack algorithm described, e.g., in Butler's > book "Fundamental Algorithms for Permutation Groups"). > > If G is the symmetrical group for some natural number n, I think I can > prove that the backtrack algorithm terminates after having tested exactly > n-1 permutations. Does this result generalize to all kinds of permutation > groups? Perhaps the number of permutations to test is equal to the number > of elements in the considered base for G? The backtrack algorithm maintains a subgroup K, which contains the elements of G which are already known to satisfy property P. If all elements of G satisfy P then K increases each time when a permutation is tested; consequently, the maximal length of subgroup chains in G is an upper bound for the number of elements tested. Slightly more precisely, consider the point stabilizer chain G=G_1 > G_2 > ... > G_m > G_{m+1}=1. The backtrack algorithm works in a ``bottom-up'' manner, first determining the subgroup of G_{i+1} satisfying P, before considering the elements of G_i \setminus G_{i+1}. If G_{i+1} is always a maximal subgroup of G_i (1 \le i \le m) then the first element of G_i \setminus G_{i+1} which we test increases K to G_i. So, the total number of elements tested is indeed the number of base points. This happens e.g. in the case of the symmetric group. In general, it may be possible that more elements are added to K=G_{i+1} before it reaches K=G_i, corresponding to a subgroup chain between G_i and G_{i+1}. Best regards, Akos Seress From wettl@erie.vma.bme.hu Tue Apr 12 10:04:00 1994 From: "Wettl Ferenc" Date: Tue, 12 Apr 94 10:04 +0100 Subject: to finite geometers Dear IntersectSet( GapUsers, FiniteGeometers ); I wrote some programs for handling finite Galois geometries. In the first step I generated difference sets for PG(2,q) (q<500), difference families for PG(3,p) (p<85), and studied the orbits of Singer group in PG(2,q). Next, I plan to improve them for a program, which offers an environment for studying problems in finite geometries. If - you are interested in such a program, or - you have some ideas, how to do it, and what to do, or - you made or plan to make something similar, or - you have a problem, which needs this approach, then please, write me, either through this forum, or directly to my address: wettl@euromath.vma.bme.hu If you are interested in my outputs and programs (versions under preparation), then you can read them on the machine euromath.vma.bme.hu using anonymous ftp. The path to the files is pub/papers/wettl/gap In this directory you can find a report (report.tex) written in LaTeX, the difference sets (182KB), difference families (795KB), and some programs and output files with the types of orbits. The programs use the package MeatAxe. Best regards, Ferenc Wettl (wettl@euromath.vma.bme.hu) From mas023@bangor.ac.uk Wed Apr 13 13:05:00 1994 From: "Chris Wensley" Date: Wed, 13 Apr 94 13:05 +0000 (GMT) Subject: GpHomByImages I have a query about how GroupHomomorphismByImages works. In the listing below Q,P are copies of D4 with Q an fp-group and P a permutation group. When mapping Q to P there is only one way to express the images of the generators. In the reverse direction the image of generator (1,2,3,4) is listed (surprisingly to me) as f.2^-1*f.1^-2*f.2^-1 rather than f.1 (although, of course, these are equal). (Sorry if this is a trivial query, but I am a new user.) Chris Wensley ----------------------------- GAP listing ---------------------------------- LogTo("invmap.log"); Print("Isomorphisms between copies of dihedral D4\n\n"); f := FreeGroup(2, "f"); relQ := [ f.1^4, f.2^2, (f.1*f.2)^2 ]; Q := f/relQ; genQ := Q.generators; oQ := Size(Q); elQ := Elements(Q); Print("Q has generators: ", genQ, " and elements:\n", elQ, "\n\n"); P := Group( (1,2,3,4), (1,3) ); genP := P.generators; P.name := "P"; oP := Size(P); elP := Elements(P); Print("P has generators: ", genP, " and elements:\n", elP, "\n\n"); isoQP := GroupHomomorphismByImages(Q,P,genQ,genP); Print(" x isoQP(x) \n"); Print("--------- ---------- \n"); for j in [1..oQ] do x := elQ[j]; Print(x, " ", Image(isoQP,x), "\n"); od; invPQ := InverseMapping(isoQP); Print("\n x invPQ(x) \n"); Print("-------- ---------- \n"); for j in [1..oP] do x := elP[j]; Print(x, " ", Image(invPQ,x), "\n"); od; ---------------------------- Output ------------------------------------ Isomorphisms between copies of dihedral D4 Q has generators: [ f.1, f.2 ] and elements: [ IdWord, f.1, f.2, f.1^2, f.1*f.2, f.2*f.1, f.1^3, f.1^2*f.2 ] P has generators: [ (1,2,3,4), (1,3) ] and elements: [ (), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3) ] x isoQP(x) --------- ---------- IdWord () f.1 (1,2,3,4) f.2 (1,3) f.1^2 (1,3)(2,4) f.1*f.2 (1,2)(3,4) f.2*f.1 (1,4)(2,3) f.1^3 (1,4,3,2) f.1^2*f.2 (2,4) x invPQ(x) -------- ---------- () IdWord (2,4) f.2^-1*f.1^-2 (1,2)(3,4) f.2^-1*f.1^-1 (1,2,3,4) f.2^-1*f.1^-2*f.2^-1*f.1^-1 (1,3) f.2^-1 (1,3)(2,4) f.2^-1*f.1^-2*f.2^-1 (1,4,3,2) f.1^-1 (1,4)(2,3) f.2^-1*f.1^-3 From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Apr 13 20:07:00 1994 From: "Martin Schoenert" Date: Wed, 13 Apr 94 20:07 +0100 (MET) Subject: Re: GpHomByImages Chris Wensley writes in his e-mail message of 1994/04/13 I have a query about how GroupHomomorphismByImages works. In the listing below Q,P are copies of D4 with Q an fp-group and P a permutation group. When mapping Q to P there is only one way to express the images of the generators. In the reverse direction the image of generator (1,2,3,4) is listed (surprisingly to me) as f.2^-1*f.1^-2*f.2^-1 rather than f.1 (although, of course, these are equal). Here is what happens if you have a 'GroupHomomorphismByImages' from a permutation group $P$. First GAP computes the size of $P$. Then it constructs a (second) stabilizer chain for $P$, which is stored in the record that represents the homomorphism (see "Stabilizer Chains" in the manual for a explanation of what a stabilizer chain is). Each computation is performed in parallel also with the images of the generators. That means that the stabilizer chain contains for each strong generator $s_i$ also its image under the homomorphism $t_i$. To compute the image of an arbitrary element $p$ in the permutation group, this element is divided through the stabilizer chain, i.e., 'Image' computes a word $w$ in the strong generators $s_i$, such that $p w(s_i) = ()$. In parallel we perform the same computation with the images of the strong generators, i.e., we compute $w(t_i)$, which is the inverse of the image. Now when 'GroupHomomorphismByImages' constructs the stabilizer chain it works essentially random. That is, it constructs random elements and builds the stabilizer chain from those. It stops when the chain is complete, i.e., when the product of the indices in the stabilizer chain is equal to the size of the group $P$. This helps to keep down the length of the words somewhat (but not enough in most cases). On the other hand it makes it impossible to predict what word you get when you map from $P$ into the free group $F$ (or a factor thereof, but the words are actually always in $F$). He continues (Sorry if this is a trivial query, but I am a new user.) There would be no need to apologize even if the question was trivial, which it is not. Hope this helps (if not, don't hesitate to ask again). 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 timhsu@math.princeton.edu Wed Apr 13 15:09:00 1994 From: "Tim Hsu" Date: Wed, 13 Apr 94 15:09 -0400 (EDT) Subject: Rewriting trivial words in relators Hi. I would like to be able to do the following thing: I have a presentation of a finite group G, and I would like to be able to know, say, the 100 "shortest" ways of expressing a word in the generators which represents the identity in G as a product of conjugates of relators. Is this easy to do in GAP? If not, do you know of another program which does this? Tim Hsu From alice@maths.uwa.edu.au Thu Apr 14 16:57:00 1994 From: "Alice Niemeyer" Date: Thu, 14 Apr 94 16:57 WST Subject: matrices I am currently working with matrices over finite fields in GAP. In my code I use the product A * Transposed(B). I was wondering whether it might be possible to have an internal function for this product avoiding the extra storage required for creating Transposed(B). Alice Niemeyer. =========================================================================== Alice C Niemeyer, Phone: (w) +61-9-380 3890, Email: alice@maths.uwa.edu.au Department of Mathematics, UWA, Nedlands WA 6009, Australia. From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Apr 14 12:08:00 1994 From: "Martin Schoenert" Date: Thu, 14 Apr 94 12:08 +0100 (MET) Subject: Re: matrices Alice Niemeyer writes in her e-mail message of 1994/04/14 I am currently working with matrices over finite fields in GAP. In my code I use the product A * Transposed(B). I was wondering whether it might be possible to have an internal function for this product avoiding the extra storage required for creating Transposed(B). Maybe I don't fully understand your problem, but wouldn't the following function do? ProductMatTransposedMat := function ( A, B ) local P, i, k; P := []; for i in [1..Length(A)] do P[i] := []; for k in [1..Length(B)] do P[i][k] := A[i] * B[k]; od; od; return P; end; No extra storage required, and it should be reasonably fast, since most of the time should be spent in the 'A[i] * B[k]' calculations, which is handled in the kernel. 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 Apr 14 12:51:00 1994 From: "Martin Schoenert" Date: Thu, 14 Apr 94 12:51 +0100 (MET) Subject: Re: Rewriting trivial words in relators Tim Hsu writes in his e-mail article of 1994/04/13 Hi. I would like to be able to do the following thing: I have a presentation of a finite group G, and I would like to be able to know, say, the 100 "shortest" ways of expressing a word in the generators which represents the identity in G as a product of conjugates of relators. Is this easy to do in GAP? If not, do you know of another program which does this? This is similar to the word problem, so I very much doubt that a good deterministic algorithm exists. What you could do is to systematically enumerate the words in the relators and just check whether or not such a word simplifies in the free group to the given word. Obviously this will only work if the given word has a rather short representation as word in the relators. Another possibility might be to add the given word to the generators, and then to use Tietze transformations to get rid of the word again. If one keeps track of the transformations, this could be used to write the given word in the original relators. This is, however, not very likely to give the shortest such representation. 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 dfh@maths.warwick.ac.uk Thu Apr 14 12:35:00 1994 From: "Derek Holt" Date: Thu, 14 Apr 94 12:35 +0100 Subject: Re: Rewriting trivial words in relators > > Hi. I would like to be able to do the following thing: I have a > presentation of a finite group G, and I would like to be able to know, > say, the 100 "shortest" ways of expressing a word in the generators > which represents the identity in G as a product of conjugates of > relators. Is this easy to do in GAP? If not, do you know of another > program which does this? > > Tim Hsu > I think that is an extremely difficult problem, and I have never heard of any kind of reasonable algorithmic approach to it. It is probably even harder than Martin suggested in his reply, because one is not looking for an expression of the trivial word as a product of relators, but as a product of conjugates of relators. In principal, the Knuth-Bendix algorithm, which systematically generates consequences of the defining relations can be used to produce a machine derivation of the triviality of any word in the generators which maps onto the identity, and this could, theoretically, be used to express the word as a product of conjugates of defining relators, but the result would typically be a very long word indeed! I know the question was about finite groups, but there are some theoretical results of a more general nature that are related to this question. If f(n) is the largest number of conjugates of defining relators that are required to express any trivial word of length n, then f(n) is called the isoperimetric function for the group (more precisely for the presentation). For finite groups, f(n) will have a maximal value, but infinite hyperbolic groups have a linear isoperimetric function, automatic groups have a quadratic, nilpotent groups have a polynomial, etc. Derek Holt. From dima@maths.uwa.edu.au Thu Apr 14 20:15:00 1994 From: "Dima Pasechnik" Date: Thu, 14 Apr 94 20:15 WST Subject: Re: Rewriting trivial words in relators > > Tim Hsu writes in his e-mail article of 1994/04/13 > > Hi. I would like to be able to do the following thing: I have a > presentation of a finite group G, and I would like to be able to know, > say, the 100 "shortest" ways of expressing a word in the generators > which represents the identity in G as a product of conjugates of > relators. Is this easy to do in GAP? If not, do you know of another > program which does this? > I'd guess that one has to measure that length as the number of relators involved, is it correct? I believe there are efficient algorithms which solve a simpler "abelianized" problem, i.e. giving the answers modulo $G'$. Dima From mas023@bangor.ac.uk Fri Apr 15 14:22:00 1994 From: "Chris Wensley" Date: Fri, 15 Apr 94 14:22 +0000 (GMT) Subject: keeping track of the transformations Martin Sch"onert, in his reply to Tim Hsu, writes: " ..use Tietze transformations.. If one keeps track of the transformations.." Since this is precisely what I want to do, I am asking how! Specifically, if a messy presentation with generators _x1 .. _x20 (say) is reduced, using TzGo , to a presentation with generating set [ _x3, _x12, _x24 ] ,I want to remember expressions for the 21 eliminated generators as words in the three remaining ones. I have not been able to discover a solution in the manual but 3 possible methods suggest themselves. Guidance as to which way to go would be much appreciated. 1. Avoid using the high-level TzGo and use the low-level commands so that at each elimination the required formula can be saved. Surely this would amount to rewriting TzGo ? 2. Edit appropriate parts of the file "fptietze.g" . This file is 40 pages long, with many interdependant functions, so I should probably create a host of bugs? In any case, the functions use the type, which appears to be defined elsewhere, possibly in the kernel? 3. Start a LOG file before using TzGo and so produce a file containing messages of the form: #I eliminating _x7 = _x18^5*_x5*_x4 As far as I can tell, GAP cannot Read this LOG file, but perhaps it would be possible to write some utility to convert the LOG file into a GAP file, Exec this utility, and Read the resulting GAP file? Chris Wensley From hwblist@machnix.mathematik.uni-stuttgart.de Sun Apr 17 20:34:00 1994 From: "Harald Boegeholz" Date: Sun, 17 Apr 94 20:34 +0200 Subject: suggestion: fix for Gcd(0*q,0*q) Hello! While computing some Gcds in LaurentPolynomialRing(Rationals) I noticed that Gcd(0*q,0*q) (where q=Indeterminate(Rationals) causes an error. The reason is that FieldLaurentPolynomialRingOps.StandardAssociate doesn't work for the 0 polynomial. I therefore suggest the following changes to gap/lib/polyfld.g (analogous to PolynomialRingOps.StandardAssociate): *** polyfld.g Tue Nov 09 00:54:00 1993 --- ../polyfld.g Sun Apr 17 17:53:12 1994 *************** *** 53,59 **** #F FieldPolynomialRingOps.StandardAssociate( , ) . . . . normed pol ## FieldPolynomialRingOps.StandardAssociate := function( R, f ) ! return f * f.coefficients[ Length( f.coefficients ) ]^-1; end; --- 53,63 ---- #F FieldPolynomialRingOps.StandardAssociate( , ) . . . . normed pol ## FieldPolynomialRingOps.StandardAssociate := function( R, f ) ! if 0 < Length( f.coefficients ) then ! return f * f.coefficients[ Length( f.coefficients ) ]^-1; ! else ! return f; ! fi; end; *************** *** 228,236 **** ## FieldLaurentPolynomialRingOps.StandardAssociate := function( R, f ) local l; ! ! l := f.coefficients[Length(f.coefficients)]; ! return Polynomial( R.baseRing, f.coefficients*l^-1 ); end; --- 232,244 ---- ## FieldLaurentPolynomialRingOps.StandardAssociate := function( R, f ) local l; ! ! if 0 < Length( f.coefficients ) then ! l := f.coefficients[Length(f.coefficients)]; ! return Polynomial( R.baseRing, f.coefficients*l^-1 ); ! else ! return f; ! fi; end; -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From wang@maths.uwa.edu.au Mon Apr 18 11:38:00 1994 From: "Wang" Date: Mon, 18 Apr 94 11:38 WST Subject: subgroup of large index Hi Forum, Given a finite group G and one of its maximal subgroup M. I want to know the lengths of the M-orbits on the set {Mx | x in G}. The moset simple way I know is List(DoubleCosets(G,M,M),x->Size(x)/Size(M)); However, while the index |G:M| is quite large, say 10^6, the above method failed. Are there any other methods to get the lengths of M-orbits? I also tried to calculate the cosets set of M in G, but it didn't work either. From Martin.Schoenert@Math.RWTH-Aachen.DE Mon Apr 18 09:55:00 1994 From: "Martin Schoenert" Date: Mon, 18 Apr 94 09:55 +0100 (MET) Subject: Re: suggestion: fix for Gcd(0*q,0*q) Thank you very much for your fix. We will add this to GAP. Have you checked that those are the only places where this is done wrong? 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 Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Apr 18 10:01:00 1994 From: "Joachim Neubueser" Date: Mon, 18 Apr 94 10:01 +0200 Subject: Re: subgroup of large index ? Wang asked: > Hi Forum, > Given a finite group G and one of its maximal subgroup M. I want > to know the lengths of the M-orbits on the set {Mx | x in G}. > The moset simple way I know is > List(DoubleCosets(G,M,M),x->Size(x)/Size(M)); > However, while the index |G:M| is quite large, say 10^6, the above > method failed. Are there any other methods to get the lengths of > M-orbits? I also tried to calculate the cosets set of M in G, but > it didn't work either. I am afraid the chances are not very good for any *general* methods that do not depend on the way, the group is given, and may not be very good anyhow. But could you just tell how your group is given (permutation, matrix, fp group, character table?). Maybe in certain cases somebody has an idea. Joachim Neubueser From hwblist@machnix.mathematik.uni-stuttgart.de Mon Apr 18 14:19:00 1994 From: "Harald Boegeholz" Date: Mon, 18 Apr 94 14:19 +0200 Subject: Re: suggestion: fix for Gcd(0*q,0*q) > Date: 18 Apr 94 09:55 +0100 (MET) > From: Martin Schoenert > > Thank you very much for your fix. We will add this to GAP. Have you > checked that those are the only places where this is done wrong? No I haven't. I grepped the library for StandardAssociate and found several definitions. Since I only needed LaurentPolynomialRing(Rationals) at the moment, I didn't check any other routines. Shouldn't be too difficult, though... hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From Volkmar.Felsch@Math.RWTH-Aachen.DE Thu Apr 21 11:05:00 1994 From: "Volkmar Felsch" Date: Thu, 21 Apr 94 11:05 +0200 Subject: Re: keeping track of the transformations Chris Wensley writes: > > Martin Sch"onert, in his reply to Tim Hsu, writes: > > " ..use Tietze transformations.. If one keeps track of the transformations.." > > Since this is precisely what I want to do, I am asking how! > Specifically, if a messy presentation with generators _x1 .. _x20 (say) > is reduced, using TzGo , to a presentation with generating set > [ _x3, _x12, _x24 ] ,I want to remember expressions for the > 21 eliminated generators as words in the three remaining ones. > > I have not been able to discover a solution in the manual but 3 possible > methods suggest themselves. Guidance as to which way to go would be much > appreciated. > > 1. Avoid using the high-level TzGo and use the low-level commands > so that at each elimination the required formula can be saved. Surely > this would amount to rewriting TzGo ? > > 2. Edit appropriate parts of the file "fptietze.g" . > This file is 40 pages long, with many interdependant functions, > so I should probably create a host of bugs? > In any case, the functions use the type, which > appears to be defined elsewhere, possibly in the kernel? > > 3. Start a LOG file before using TzGo and so produce a file > containing messages of the form: > #I eliminating _x7 = _x18^5*_x5*_x4 > As far as I can tell, GAP cannot Read this LOG file, but perhaps it > would be possible to write some utility to convert the LOG file into > a GAP file, Exec this utility, and Read the resulting GAP file? > As the discussion on keeping track of Tietze transformations is too technical to be continued in the GAP forum, I have sent my answer to the above letter directly to Chris Wensley. However, I would like to encourage all those forum members who are interested in that question to ask me for a copy of that correspondence. Volkmar Felsch, Aachen From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994 From: "Harald Boegeholz" Date: Fri, 22 Apr 94 18:14 +0200 Subject: Re: keeping track of the transformations > Date: 21 Apr 94 11:05 +0200 > From: Volkmar Felsch > As the discussion on keeping track of Tietze transformations is too > technical to be continued in the GAP forum, I have sent my answer to > the above letter directly to Chris Wensley. Can any discussion about GAP be too technical to be continued in the GAP forum? I for one don't think so (except maybe if we are talking about machine specific implementation details); the traffic in the GAP forum is so low that I can easily ignore any messages I don't understand. So why not continue this discussion in public, i.e., in the forum? hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994 From: "Volkmar Felsch" Date: Mon, 25 Apr 94 09:28 +0200 Subject: Re: keeping track of the transformations Harald Boegeholz writes: > > > Date: 21 Apr 94 11:05 +0200 > > From: Volkmar Felsch > > > As the discussion on keeping track of Tietze transformations is too > > technical to be continued in the GAP forum, I have sent my answer to > > the above letter directly to Chris Wensley. > > Can any discussion about GAP be too technical to be continued in the > GAP forum? I for one don't think so (except maybe if we are talking > about machine specific implementation details); the traffic in the GAP > forum is so low that I can easily ignore any messages I don't > understand. > > So why not continue this discussion in public, i.e., in the forum? > In the past we have got several comments by GAP forum members asking us not to overwhelm the forum by too technical discussions. That is the reason why I hesitated to continue a public discussion on Chris Wensley's contribution and why I sent only a short statement to the forum which offered copies of that discussion to all who might be interested in it only on special request. In the meantime, I have got about half a dozen reactions to that statement asking me for a copy of our correspondence or for a public continuation of the discussion. I think that justifies now to provide my letter to Chris Wensley and his reply in the forum. Volkmar Felsch, Aachen ============================================================================== > > Martin Sch"onert, in his reply to Tim Hsu, writes: > > " ..use Tietze transformations.. If one keeps track of the transformations.." > > Since this is precisely what I want to do, I am asking how! > Specifically, if a messy presentation with generators _x1 .. _x20 (say) > is reduced, using TzGo , to a presentation with generating set > [ _x3, _x12, _x24 ] ,I want to remember expressions for the > 21 eliminated generators as words in the three remaining ones. > > I have not been able to discover a solution in the manual but 3 possible > methods suggest themselves. Guidance as to which way to go would be much > appreciated. > > 1. Avoid using the high-level TzGo and use the low-level commands > so that at each elimination the required formula can be saved. Surely > this would amount to rewriting TzGo ? > > 2. Edit appropriate parts of the file "fptietze.g" . > This file is 40 pages long, with many interdependant functions, > so I should probably create a host of bugs? > In any case, the functions use the type, which > appears to be defined elsewhere, possibly in the kernel? > > 3. Start a LOG file before using TzGo and so produce a file > containing messages of the form: > #I eliminating _x7 = _x18^5*_x5*_x4 > As far as I can tell, GAP cannot Read this LOG file, but perhaps it > would be possible to write some utility to convert the LOG file into > a GAP file, Exec this utility, and Read the resulting GAP file? > Dear Dr. Wensley, I will try to answer your above letter to the GAP forum. The GAP Tietze transformations functions have not bee designed to keep track of the eliminations. So, in fact, you get only the messages which you quote in point 3 of your letter. I must confess that I do not really understand what kind of GAP readable output you would like to get instead, but if you just want to get the same information in some different, GAP readable format, then, as you said that you are prepared to do at least some small amount of editing file 'fptietze.g', there is a reasonably simple way of inserting some appropriate print statements for this purpose. Essentially, what you have to do is to find the three places in file 'fptietze.g' where the above messages are printed. They are in the functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1', and you will find them by searching for occurrences of the string 'eliminating "'. The respective statements are of the form if T.printLevel >= 2 then Print( "#I eliminating ", gens[num], " = " ); if gen > 0 then Print( TzWord( tietze, word )^-1, "\n" ); else Print( TzWord( tietze, word ), "\n" ); fi; fi; and in each case you should duplicate them by adding something like if IsBound( P.keepTrack ) and P.keepTrack then Print( gens[num], " := " ); if gen > 0 then Print( TzWord( tietze, word )^-1, ";\n" ); else Print( TzWord( tietze, word ), ";\n" ); fi; fi; (or whatever you want to print). Here I assume that 'P.keepTrack' is a new component of your current presentation record 'P', say, which has to be introduced by a statement like P.keepTrack := true; before calling the 'GoTo' command. (An alternative to such an individual variable for each presentation record would be some global variable 'keepTrack' which you initialize at the beginning of your session.) Note, however, that the messages printed by the three functions mentioned above do not cover all eliminations which may be performed during a Tietze transformations run. In general, further eliminations will be performed by the function 'TzHandleLength1Or2Relators'. Because of your request, I now have extended this function by some additional print statements. (The extended version will go into the next release of GAP.) I am sending you a copy of the new version in this letter. Again, you will have to duplicate the print statements appropriately. To make things easier for you, I have already added a sample of such duplications (in the form of comments). As above, you should change these additional statements according to your needs. Please feel free to contact me again if you have further questions. Volkmar Felsch, Aachen ----------------------------------------------------------------------------- ############################################################################# ## #F TzHandleLength1Or2Relators( ) . . . handle short relators ## ## 'TzHandleLength1Or2Relators' searches for relators of length 1 or 2 and ## performs suitable Tietze transformations for each of them: ## ## Generators occurring in relators of length 1 are eliminated. ## ## Generators occurring in square relators of length 2 are marked to be ## involutions. ## ## If a relator of length 2 involves two different generators, then the ## generator with the larger number is substituted by the other one in all ## relators and finally eliminated from the set of generators. ## TzHandleLength1Or2Relators := function ( T ) local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens, numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep, rep1, rep2, tietze, tree, treelength, treeNums; if T.printLevel >= 3 then Print( "#I handling short relators\n" ); fi; # check the given argument to be a Tietze record. if not ( IsBound( T.isTietze ) and T.isTietze ) then Error( "argument must be a Tietze record" ); fi; tietze := T.tietze; gens := tietze[TZ_GENERATORS]; invs := tietze[TZ_INVERSES]; rels := tietze[TZ_RELATORS]; lengths := tietze[TZ_LENGTHS]; flags := tietze[TZ_FLAGS]; numgens := tietze[TZ_NUMGENS]; numrels := tietze[TZ_NUMRELS]; redunds := tietze[TZ_NUMREDUNDS]; numgens1 := numgens + 1; done := false; tree := 0; if IsBound( T.tree ) then tree := T.tree; treelength := tree[TR_TREELENGTH]; pointers := tree[TR_TREEPOINTERS]; treeNums := tree[TR_TREENUMS]; fi; while not done do done := true; # loop over all relators and find those of length 1 or 2. for i in [ 1 .. numrels ] do length := lengths[i]; if length <= 2 and length > 0 and flags[i] <= 2 then done := false; # find the current representative of the first factor. rep1 := rels[i][1]; while invs[numgens1-rep1] <> rep1 do rep1 := invs[numgens1-rep1]; od; if length = 1 then # handle a relator of length 1. if rep1 <> 0 then rep1 := AbsInt( rep1 ); invs[numgens1-rep1] := 0; invs[numgens1+rep1] := 0; if tree <> 0 then ptr1 := AbsInt( treeNums[rep1] ); pointers[ptr1] := 0; treeNums[rep1] := 0; fi; if T.printLevel >= 2 then Print( "#I eliminating ", gens[rep1], " = IdWord\n" ); fi; ### if IsBound( T.keepTrack ) and T.keepTrack then ### Print( gens[rep1], " := IdWord;\n" ); ### fi; redunds := redunds + 1; fi; else # find the current representative of the second factor. rep2 := rels[i][2]; while invs[numgens1-rep2] <> rep2 do rep2 := invs[numgens1-rep2]; od; # handle a relator of length 2. if AbsInt( rep2 ) < AbsInt( rep1 ) then rep := rep1; rep1 := rep2; rep2 := rep; fi; if rep1 < 0 then rep1 := - rep1; rep2 := - rep2; fi; if rep1 = 0 then # the relator is in fact of length at most 1. if rep2 <> 0 then rep2 := AbsInt( rep2 ); invs[numgens1-rep2] := 0; invs[numgens1+rep2] := 0; if tree <> 0 then ptr2 := AbsInt( treeNums[rep2] ); pointers[ptr2] := 0; treeNums[rep2] := 0; fi; if T.printLevel >= 2 then Print( "#I eliminating ", gens[rep2], " = IdWord\n" ); fi; ### if IsBound( T.keepTrack ) and T.keepTrack then ### Print( gens[rep2], " := IdWord;\n" ); ### fi; redunds := redunds + 1; fi; elif rep1 <> - rep2 then if invs[numgens1+rep1] < 0 and ( rep1 = rep2 or invs[numgens1-rep2] = invs[numgens1+rep2] ) then # make the relator a square relator, ... rels[i][1] := rep1; rels[i][2] := rep1; # ... mark it appropriately, ... flags[i] := 3; # ... and mark rep1 to be an involution. invs[numgens1+rep1] := rep1; fi; # handle a non-square relator of length 2. if rep1 <> rep2 then absrep2 := AbsInt( rep2 ); invs[numgens1-rep2] := invs[numgens1+rep1]; invs[numgens1+rep2] := rep1; if tree <> 0 then ptr1 := AbsInt( treeNums[rep1] ); ptr2 := AbsInt( treeNums[absrep2] ); if ptr2 < ptr1 then ptr := ptr2; if treeNums[rep1] * treeNums[absrep2] * rep2 > 0 then ptr := - ptr; treeNums[rep1] := ptr; pointers[ptr1] := treelength + rep1; fi; ptr2 := ptr1; ptr1 := AbsInt( ptr ); fi; if rep2 > 0 then ptr1 := - ptr1; fi; pointers[ptr2] := ptr1; treeNums[absrep2] := 0; fi; if T.printLevel >= 2 then Print( "#I eliminating ", gens[absrep2], " = " ); if rep2 > 0 then Print( TzWord( tietze, [ invs[numgens1+rep1] ] ), "\n" ); else Print( gens[rep1], "\n" ); fi; fi; ### if IsBound( T.keepTrack ) and T.keepTrack then ### Print( gens[absrep2], " := " ); ### if rep2 > 0 then ### Print( TzWord( tietze, ### [ invs[numgens1+rep1] ] ), ";\n" ); ### else ### Print( gens[rep1], ";\n" ); ### fi; ### fi; redunds := redunds + 1; fi; fi; fi; fi; od; if not done then # for each generator determine its current representative. for i in [ 1 .. numgens ] do if invs[numgens1-i] <> i then rep := invs[numgens1-i]; invs[numgens1-i] := invs[numgens1-rep]; invs[numgens1+i] := invs[numgens1+rep]; fi; od; # perform the replacements. TzReplaceGens( tietze ); fi; od; # tidy up the Tietze generators. tietze[TZ_NUMREDUNDS] := redunds; if redunds > 0 then TzRemoveGenerators( T ); fi; # Print( "#I total length = ", tietze[TZ_TOTAL], "\n" ); end; ============================================================================== Dear Dr. Felsch, Thank you for your very helpful message yesterday. The significant part of the reply was: "Here I assume that 'P.keepTrack' is a new component ... ..... to be introduced by a statement like P.keepTrack := true; I was amazed and delighted to discover that new components can be added to a record so easily. (I must admit that, until today, I had only glanced briefly at the chapter on records in the manual.) So I propose to add a new component to a presentation record, initially a copy of the generators component, and update this within the various elimination functions. Chris Wensley, Bangor. ============================================================================== From studgap@twi.tudelft.nl Mon Apr 25 14:06:00 1994 From: "Gap Students" Date: Mon, 25 Apr 94 14:06 +0100 (MET) Subject: blistoperators Hi, We want to use blists as a representation for binary codewords because we hope it will be much faster than to use elements of GF(2). But we could not find a function for XOR(blist1, blist2) or for NOT(blist1) which would make the functions we need (like our function "distance") much faster. We now use BlistList(list1,[false]) instead of Not(blist1) but it is too slow. Are you implementing those functions in the near future? Erik, Jasper & Reinald From mas023@bangor.ac.uk Wed Apr 27 21:09:00 1994 From: "Chris Wensley" Date: Wed, 27 Apr 94 21:09 +0000 (GMT) Subject: Re: keeping track of the eliminations Further to last week's messages, here is a brief report on my attempts to edit the library file "fptietze.g" to keep track of eliminations. Two new functions have been added: TzInitRemember adds extra components T.genslist & T.remember to the TietzeRecord. They are initialised as copies of T.generators . T.genslist records all generators used: none deleted, T.remember records words used to eliminate generators. TzRememberGen is called by the TzElim.. functions and replaces every occurrence in T.remember of the generator being eliminated by the corresponding word. The following functions in fptietze.g have been modified as appropriate: AddGenerator, TzNewGenerator, PresentationFpGroup, TzEliminateGen, TzEliminateGen1, TzEliminateGens, TzHandleLength1Or2Relators I had to initialise the two new components within PresentationFpGroup becuase this function calls TzHandleLength1Or2Relators while it is creating the presentation. If I were using the PresentationSubgroup function, then that would require modification as well. The Log file listing below illustrates the results of these modifications using a rather contrived example. Chris Wensley, Bangor ========================================================================== f := FreeGroup(6, "f");; relQ := [ f.1^4, f.4^3, (f.1*f.4)^2, f.2^8, f.2*f.1*f.2, f.6*f.4*f.1, f.5*f.6*f.2, f.2*f.3*f.4 ];; Q := f / relQ;; P := PresentationFpGroup( Q,2 ); #I there are 6 generators and 8 relators of total length 31 #> Initialising: T.genslist = T.remember = [ f.1, f.2, f.3, f.4, f.5, f.6 ] gap> TzEliminate(P); #I eliminating f.5 = f.2^-1*f.6^-1 #I there are 5 generators and 7 relators of total length 28 gap> P.remember; [ f.1, f.2, f.3, f.4, f.2^-1*f.6^-1, f.6 ] gap> TzEliminate(P); #I eliminating f.6 = f.1^-1*f.4^-1 #I there are 4 generators and 6 relators of total length 25 gap> P.remember; [ f.1, f.2, f.3, f.4, f.2^-1*f.4*f.1, f.1^-1*f.4^-1 ] gap> TzGo(P); #I there are 4 generators and 6 relators of total length 21 #I there are 4 generators and 5 relators of total length 17 #I eliminating f.3 = f.2^-1*f.4^-1 #I eliminating f.1 = f.2^-2 #I there are 2 generators and 3 relators of total length 17 gap> P.remember; [ f.2^-2, f.2, f.2^-1*f.4^-1, f.4, f.2^-1*f.4*f.2^-2, f.2^2*f.4^-1 ] gap> TzPrintRelators(P); #I 1. f.4^3 #I 2. f.2^-2*f.4*f.2^-2*f.4 #I 3. f.2^8 gap> TzSubstitute(P); #I substituting new generator _x7 defined by f.2*f.4^-1 #I eliminating _x7 = f.2*f.4^-1 gap> TzSubstitute(P,1,2); #I substituting new generator _x8 defined by f.2*f.4^-1 #I eliminating f.4 = _x8^-1*f.2 #I there are 2 generators and 3 relators of total length 18 gap> P.genslist; [ f.1, f.2, f.3, f.4, f.5, f.6, _x7, _x8 ] gap> P.remember; [ f.2^-2, f.2, f.2^-2*_x8, _x8^-1*f.2, f.2^-1*_x8^-1*f.2^-1, f.2*_x8, _x8, _x8 ] gap> P.generators; [ f.2, _x8 ] gap> TzPrint(P); #I generators: [ f.2, _x8 ] #I relators: #I 1. 4 [ -1, -2, -1, -2 ] #I 2. 6 [ -2, 1, -2, 1, -2, 1 ] #I 3. 8 [ 1, 1, 1, 1, 1, 1, 1, 1 ] gap> quit; From greenhil@maths.ox.ac.uk Thu Apr 28 09:45:00 1994 From: "Catherine Greenhill" Date: Thu, 28 Apr 94 09:45 +0100 Subject: GAP for a DEC OS1 Alpha Dear GAP people, the system programmer here has had difficulties setting up GAP on a DEC OS1 Alpha --- is he doing something wrong or is there a special version which we should use or is it not possible?? Thanks in advance, Catherine Greenhill From Alexander.Hulpke@Math.RWTH-Aachen.DE Thu Apr 28 11:33:00 1994 From: "Alexander Hulpke" Date: Thu, 28 Apr 94 11:33 +0200 Subject: Re: GAP for a DEC OS1 Alpha Dear GAP forum, Catherine Greenhill asked about porting GAP to an Alpha/OS1 platform. Due to internal representations of objects as 32 bit words in the GAP kernel, it is not possible to compile the present version yourself. However, we do provide an executable for DEC alpha under OSF1, which can be found on our ftp server samson.math.rwth-aachen.de in the file pub/gap/bin/bin3r3p0-dec-axp-osf.zoo You will also find a version of unzoo for Dec AXP in the same directory to unpack the binary. May I just remind the members of the forum, that we have provided the address gap-trouble@samson.math.rwth-aachen.de for installation and other technical problems, which usually are not of interest to other members of the forum, working on different computers. Alexander Hulpke From eamonn.obrien@maths.anu.edu.au Thu Apr 28 12:15:00 1994 From: "Eamonn O'Brien" Date: Thu, 28 Apr 94 12:15 +1000 Subject: ANU PQ package Version 1.2 Version 1.2 of the ANU p-Quotient Program is now available by anonymous FTP. The Unix tar file, pq.v1-2.tar.Z, of the program may be fetched by anonymous ftp from pell.anu.edu.au (IP number 150.203.33.4) It is in the pub/PQ directory The file can be uncompressed using the command uncompress pq.v1-2.tar.Z Then the file can be unpacked using the command tar -xvf pq.v1-2.tar This will create a directory called pq and needs about 1.5 MB of free disk space. Please read the README file in the pq directory for all necessary compilation details. The program provides access to implementations of the following algorithms: -- p-quotient computations; -- p-group generation; -- a "standard presentation" algorithm which permits isomorphism testing for p-groups; -- an algorithm to compute a description of the automorphism group of a p-group. This version can be run as part of the share library of GAP 3.2 (and later versions). Much of it is also accessible via Magma and Quotpic. Version 1.2 will be distributed as a standard share package with GAP 3.4, when it is released. In the meantime, the existing Version 1.1 distributed with GAP 3.3 can be replaced by Version 1.2. Feedback and bug reports are welcomed. ++++++++++++++++++++++++++++++++++++ Eamonn O'Brien School of Mathematical Sciences Australian National University Canberra, 0200 e-mail obrien@maths.anu.edu.au ++++++++++++++++++++++++++++++++++++ April 1994 From Frank.Celler@Math.RWTH-Aachen.DE Thu Apr 28 12:58:00 1994 From: "Frank Celler" Date: Thu, 28 Apr 94 12:58 +0200 Subject: Blists Dear Erik, Jasper & Reinald, you wrote: We want to use blists as a representation for binary codewords because we hope it will be much faster than to use elements of GF(2). yes, at the moment this is most certainly true. But we could not find a function for XOR(blist1, blist2) or for NOT(blist1) which would make the functions we need (like our function "distance") much faster. We now use BlistList(list1,[false]) instead of Not(blist1) but it is too slow. Are you implementing those functions in the near future? Have you tried to use the functions 'SubtractBlist' or 'DifferenceBlist' (the latter is essentially "SubtractBlist( Copy(blist1), blist2 )")? The function 'DifferenceBlist( b1, b2 )' will return a boolean list such that "d[i] = b1[i] and not b2[i]". If you keep a copy of an all true boolean list, then "Not(b1) = DifferenceBlist( all_true, b1 )" and gap> XorBlist := function( b1, b2 ) return UnionBlist(DifferenceBlist(b1,b2), DifferenceBlist(b2,b1)); end; # or to avoid one copy and two functions calls gap> XorBlist := function( b1, b2 ) local r; r := Copy(b1); SubtractBlist( r, b2 ); b2 := Copy(b2); SubtractBlist( b2, b1 ); UniteBlist( r, b2 ); return r; end; gap> b1 := [ true, true, false, false ]; [ true, true, false, false ] gap> b2 := [ true, false, true, false ]; [ true, false, true, false ] gap> XorBlist( b1, b2 ); [ false, true, true, false ] I admit that this will be a bit slower than a genuine 'XorBlist' but it might be fast enough for your purpose. Please keep us informed. best wishes Frank From eamonn.obrien@maths.anu.edu.au Fri Apr 29 17:18:00 1994 From: "Eamonn O'Brien" Date: Fri, 29 Apr 94 17:18 +1000 Subject: GAP Matrix Group and G-Module library ############################################################################ # # Matrix Group and G-Module library # Version 1.0 # ############################################################################ We announce the availability by anonymous FTP of a matrix group and G-module library for use with GAP 3.3 (and later versions). A version of this code will be distributed as a package with GAP 3.4. ############################################################################ This library provides functions which may be used to construct and investigate the structure of matrix groups defined over finite fields. These functions permit the user to construct certain types of matrix groups and G-modules; to test whether a G-module is irreducible or absolutely irreducible; to decide whether a group is imprimitive or has certain decomposition with respect to a normal subgroup; and to select random elements with certain properties. The code was developed as part of the on-going project to "recognise" the Aschbacher categories of matrix groups defined over finite fields. ############################################################################# The interested reader is referred to the following papers for details of the algorithms used. Preprints of these papers are distributed with the package. Derek F. Holt and Sarah Rees, ``Testing modules for irreducibility'', J. Austral. Math. Soc. Ser. A, 57, 1994. Derek F. Holt, Charles R. Leedham-Green, E.A. O'Brien and Sarah Rees, ``Computing matrix group decompositions with respect to a normal subgroup'', submitted to London Math. Soc., 1994. Derek F. Holt, Charles R. Leedham-Green, E.A. O'Brien and Sarah Rees, ``Primitivity testing for matrix groups'', submitted to London Math. Soc., 1994. ############################################################################ The Unix tar file, matrix.v1-0.tar.Z, of the program may be fetched by anonymous ftp from pell.anu.edu.au (IP number 150.203.33.4) It is in the pub/matrix directory The file can be uncompressed using the command uncompress matrix.v1-0.tar.Z Then the file can be unpacked using the command tar -xvf matrix.v1-0.tar This will create a directory called matrix and needs about 1 MB of free disk space. Please read the README file in the matrix directory for all necessary details. ############################################################################ The library was developed by: Derek Holt, Mathematics Institute, Warwick dfh@maths.warwick.ac.uk Charles Leedham-Green, School of Mathematical Studies, QMW C.R.Leedham-Green@qmw.ac.uk Eamonn O'Brien, School of Mathematical Sciences, ANU Eamonn.OBrien@maths.anu.edu.au Sarah Rees, Department of Mathematics and Statistics, Newcastle Sarah.Rees@newcastle.ac.uk ############################################################################ Feedback, queries, and bug reports are welcome. Eamonn O'Brien School of Mathematical Sciences Australian National University Canberra, 0200 April 1994 From ara@altdorf.ai.mit.edu Tue May 10 12:58:00 1994 From: "Allan Adler" Date: Tue, 10 May 94 12:58 -0400 Subject: GAP under Linux I installed GAP on an 80386 with the Linux operating system (version 1.0). My machine has 8 MB of RAM, about 1 of which is taken up with Linux stuff. I find I can run GAP with 4.75 MB of RAM but no more (I get error messages when I try to run it with more). There seems to be something wrong with the momory management. For example, if I start up gap and execute the command 6suz:=CharTable("6.suz"); GAP says it runs out of memory and I get thrown back into the operating system. I don't think I should be having this problem. If anyone has installed GAP on Linux and knows how to deal with this, please let me know. For the record, I have about 16 MB of swap space and lots of room in my main partition. If necessary, I can alsopost on a linux group, but I think the GAP group is the [place to start. Allan Adler ara@altdorf.ai.mit.edu From mueller@mi.uni-erlangen.de Wed May 11 20:02:00 1994 From: "Peter Mueller" Date: Wed, 11 May 94 20:02 +0200 Subject: Trouble with IsSolvable Using the latest release 3.3 of GAP, the following weird phenomeneon occurs: gap> IsSolvable(Group((1,8,3,6),(1,2,3,4),(5,6,7,8))); true gap> # Now, switching the first two generators, yields: gap> IsSolvable(Group((1,2,3,4),(1,8,3,6),(5,6,7,8))); Error, RemoveSet: must be a proper set at RemoveSet( T, v ) ... in ExtendElementaryAbelianSeriesPermGroup( G, w, der - 1 ) called from ExtendElementaryAbelianSeriesPermGroup( G, w, der - 1 ) called from ExtendElementaryAbelianSeriesPermGroup( G, y, bound ) called from PermGroupOps.TryElementaryAbelianSeries( G ) called from G.operations.IsSolvable( G ) called from ... brk> quit; gap> quit; Peter From egner@hermes.zkm.de Sun May 8 19:43:00 1994 From: "Sebastian Egner" Date: Sun, 08 May 94 19:43 +0100 Subject: GAPstones-SGI 62949 GAPstones on a Silicon Graphics Indigo Elan: 1 50 MHZ IP20 Processor FPU: MIPS R4010 Floating Point Chip Revision: 0.0 CPU: MIPS R4000 Processor Chip Revision: 3.0 Data cache size: 8 Kbytes Instruction cache size: 8 Kbytes Secondary unified instruction/data cache size: 1 Mbyte Main memory size: 32 Mbytes 30864 GAPstones on Silicon Graphics Indigo: 1 33 MHZ IP12 Processor FPU: MIPS R2010A/R3010 VLSI Floating Point Chip Revision: 4.0 CPU: MIPS R2000A/R3000 Processor Chip Revision: 3.0 Data cache size: 32 Kbytes Instruction cache size: 32 Kbytes Main memory size: 48 Mbytes Compiler: gcc, version ca. v1.39 (an old one!) OS: IRIX v4.0.5 (*not* v5.xxx) Looks alright for graphics workstations. Sebastian. From Alexander.Hulpke@Math.RWTH-Aachen.DE Fri May 13 09:23:00 1994 From: "Alexander Hulpke" Date: Fri, 13 May 94 09:23 +0200 Subject: Re: Trouble with IsSolvable In his Article, Peter Mueller writes: > Using the latest release 3.3 of GAP, the following weird phenomeneon > occurs: > > gap> IsSolvable(Group((1,8,3,6),(1,2,3,4),(5,6,7,8))); > true > gap> # Now, switching the first two generators, yields: > gap> IsSolvable(Group((1,2,3,4),(1,8,3,6),(5,6,7,8))); > Error, RemoveSet: must be a proper set at [...] This error is fixed in version 3.4 (which hopefully will be released quite soon...) Alexander Hulpke From egner@hermes.zkm.de Fri May 13 11:53:00 1994 From: "Sebastian Egner" Date: Fri, 13 May 94 11:53 +0100 Subject: [no subject] Hallo GAP-world! I wrote a Mathematica/GAP-syntax interface which I have posted into ftp.math.rwth-aachen.de:/pub/incoming. It contains the files gapmath.doc, gap.m, math.g. The file gapmath.doc copied below: GAP/Mathematica-Interface ========================= Sebastian Egner (egner@zkm.de), 13. May 1994 in GAP v3.3, Mathematica v2.0 on IBM-PC, SGI Iris, Sun Sparc. files: gapmath.doc --- this file, general information math.g --- a GAP-library extension providing a function StringMathematica (and such) which constructs a GAP-string containing a GAP-object but written in Mathematica native syntax. gap.m --- a loose collection of functions to show how to use the Mathematica-expressions written via StringMathematica plus some function to convert a Mathematica-structure into GAP native syntax. comments: * The gap.m file is *not* implemented as a Package[] since it has to be extended quite a lot to be useful for a specific purpose. * The code ToCycles and FromCycles which comes in the packages with the Mathematica product are not very useful to compute with permutations. New functions are provided in gap.m * Make sure new structures do not clash with existing ones when extending math.g for more advanced structures. My design guideline was to output structures that are somewhat clumsy but which do not interfere with anything existing, for example cyc[3 e[7]^3 + e[7]^2] is an element of an extension field --- although it would be easier to leave out the "cyc". In a similar fashion I decided to represent GAP-records as rec[{t1 -> v1, .., tn -> vn}] instead of leaving away the {} or the "rec". It proved already useful to me. * Output of Mathematica-structures to GAP is difficult. The strategy is: Convert the Mathematica-structure into an output structures which prints as GAP-syntax when printed in OutputForm[]. Note however that it will not be printed correctly if it is output in InputForm[], for example with X >>> outputfilename Any suggestions how to solve the problem in a clean way? examples: * Mathematica to GAP: < True, "-" -> False, "IsGroup" -> False}]; s2 = {s1, s1, {1,2,3}}; out = OpenWrite["file.g", {FormatType -> OutputForm, PageWidth -> Infinity}]; Write[out, "x := ", formatGAP[s2], ";"]; creates `file.g' with contents x := [rec('+' := true,'-' := false,'IsGroup' := false),rec('+' := true,'-' := false,'IsGroup' := false),[1,2,3]]; If you forget to set OutputForm then the output will in fact contain things like Infix[], if you forget to set PageWidth to infinity then Mathematica will break lines an insert ">"-Characters to indicate continuation. This causes heavy digestive problems to GAP. If you forget to put a trailing ";" into the file then GAP will complain about a syntax error. * GAP to Mathematica: Read("math.g"); g1 := Group((1,2,3), (1,2)); PrintToMathematica("file.m"); # empty `file.m' AppendTo("file.m", "g1 = "); AppendToMathematica("file.m", g1); creates `file.m' containing g1 = rec[{ "isDomain" -> True, "isGroup" -> True, "identity" -> perm[{}], "generators" -> {perm[{{1,2,3}}], perm[{{1,2}}]}, "operations" -> Skeleton[151], "isPermGroup" -> True, "isFinite" -> True, "1" -> perm[{{1,2,3}}], "2" -> perm[{{1,2}}] }] have fun with it, Sebastian Egner. From Martin.Schoenert@Math.RWTH-Aachen.DE Fri May 13 14:44:00 1994 From: "Martin Schoenert" Date: Fri, 13 May 94 14:44 +0100 (MET) Subject: Re: GAP under Linux It sounds strange that GAP should not be able to get more than 4.75 MByte of memory. Could it be that you have a limit on the maximal process size? Try 'limit' or 'ulimit' (depending on which shell you use). But it is true, 'CharTable("6.suz")' does not fit into 4.75 MByte. It will barely fit into 5 Mbyte (leaving about 256k free). 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 Fri May 13 15:05:00 1994 From: "Steve Linton" Date: Fri, 13 May 94 15:05 +0200 Subject: Re: GAP under Linux > It sounds strange that GAP should not be able to get more than 4.75 MByte > of memory. Could it be that you have a limit on the maximal process > size? Try 'limit' or 'ulimit' (depending on which shell you use). > Could this be the contiguous memory problem again? GAP needs its workspace to be together in virtual memory. Is there something in Linux that could be preventing this? From pluto@machnix.mathematik.uni-stuttgart.de Fri May 13 15:27:00 1994 From: "Martin Wursthorn" Date: Fri, 13 May 94 15:27 +0200 Subject: Re: GAP under Linux > > > It sounds strange that GAP should not be able to get more than 4.75 MByte > > of memory. Could it be that you have a limit on the maximal process > > size? Try 'limit' or 'ulimit' (depending on which shell you use). > > > > Could this be the contiguous memory problem again? GAP needs its > workspace to be together in virtual memory. Is there something in > Linux that could be preventing this? I do not think so. On my Linux-486 (16 MByte memory, 16 MByte Swap, X, Emacs etc. running) I do not have any problems with the example and even larger ones. To get more information it may be useful to examine the output of the 'top' command. This command gives detailed informations about memory and swap space usage. Martin Wursthorn From ara@altdorf.ai.mit.edu Fri May 13 18:53:00 1994 From: "Allan Adler" Date: Fri, 13 May 94 18:53 +0200 Subject: Re: GAP under Linux I solved the problem. It was caused by the fact that no one ever told me that in order for Linux to be able to make use of the 16 MB of swap space I gave it, I have to explicitly add a line to /etc/fstab mentioning it. Allan From lbartho@scsun.unige.ch Tue May 24 16:05:00 1994 From: "BARTHOLDI Laurent" Date: Tue, 24 May 94 16:05 +0200 Subject: a bug in MatringOps.IsUnit Hello all, I found a small bug in MatringOps.Isunit, file matring.g: there is code ...if...DeterminantMat <> 0... which works only in characteristic 0. My solution is to replace `0' by `R.field.zero'. While we're at it, there's a thing I don't understand (yes, i read the manuals) which is how one defines quotient rings. Specifically, i want to do some computations in GF(2)[x]/(x^5+x+1), which abstractly is GF(4)+GF(8); and i want to be able to work directly with polynomials. The only solution i found is working with the companion matrix of this polynomial; but it certainly is inefficient and boring to type in. I also have a problem with the OS/2 version and emacs. the online help does not work, i think because of some redirections. as a simple proof of that, create a file named XXX: --------------------- ?Group quit; --------------------- and issue 'gapemx < XXX'. It displays a silly message about an invalid expression. anyways thanks to all those who did the good work. larry From hwblist@machnix.mathematik.uni-stuttgart.de Wed May 25 17:17:00 1994 From: "Harald Boegeholz" Date: Wed, 25 May 94 17:17 +0200 Subject: GAP online help under OS/2 > Date: 24 May 94 16:05 +0200 > From: BARTHOLDI Laurent > > I also have a problem with the OS/2 version and emacs. the online help does > not work, i think because of some redirections. as a simple proof of that, > create a file named XXX: > --------------------- > ?Group > quit; > --------------------- > and issue 'gapemx < XXX'. It displays a silly message about an invalid > expression. I'll check this as soon as I am at home at my OS/2 machine. But just in case you don't know: The INF version of the GAP documentation is much nicer under OS/2. It is a hypertext document that can be viewed with OS/2's view command. If you set the Emacs variable os2help correctly, you can invoke online help for GAP by pressing Ctrl+F1. I don't remember right now where I documented this, but it should be in the docs somewhere. Send me mail if you can't get it to work. mfg hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@ftp.uni-stuttgart.de From Thomas.Breuer@Math.RWTH-Aachen.DE Wed May 25 17:43:00 1994 From: "Thomas Breuer" Date: Wed, 25 May 94 17:43 WET Subject: Re: a bug in MatRingOps.IsUnit Dear Mrs. and Mr. Forum, yesterday Laurent Bartholdi wrote about three topics. The first was a bug report, concerning 'MatRingOps.IsUnit'. This bug will be fixed in GAP-3.4. Secondly, Laurent asked how to construct quotient rings. Unfortunately such structures are not supported in GAP-3.3, also GAP-3.4 will not yet contain the possibility to form ideals and quotient rings. Thirdly, Laurent told about the following problem. > I also have a problem with the OS/2 version and emacs. the online help does > not work, i think because of some redirections. The observation is right, both online help and command line editing do not work in the case that GAP recognizes that it does not get its input from a terminal, and such a case of input redirection occurs when GAP is started from within emacs under OS/2. Kind regards Thomas From j.cramwinckel@twi.tudelft.nl Fri May 27 14:35:00 1994 From: "Jasper Cramwinckel" Date: Fri, 27 May 94 14:35 +0100 (MET) Subject: Some homework Hi, we are three students who have been working on GAP for about half a year now. We came across some features which the programmers of GAP wanted to keep for themself. We think that is a shame because we use them a lot! NOTE: the things mentioned are not bugs, just 'funnies'. # Beautiful ############################################################## a:=[5,5,5,5]; b:=[4,4,4,4]; Maximum(a,b)[2]:=7; #And guess what a and b look like! # Dirty ################################################################# C := rec(); PrintRec(C); #Look who's coming to dinner! # Beautifully dirty ##################################################### C := rec( a := function (C) Unbind(C.a); Print("I'm still here, as long as you're reading it, am I? \n"); end); C.a(C); #And guess how long C.a exists! # to be or not to be ##################################################### IsMat(NullMat(3,0)); # rows and columns ####################################################### TransposedMat([[]]); #And look how many sleeves your shirt still has! # A rule of life ####################################################### for i in [1..10^4] do if 2^10 = 1024 and 1 = 0 then ; fi; od; time; for i in [1..10^4] do if 1 = 0 and 2^10 = 1024 then ; fi; od; time; #So check your gravy before you pour it on your fries! # The law of gravity ################################################### Permuted([1,2,3,4], 3); #And try to catch the ball! # I am not sure ######################################################## 1;;2;; last = last2; # Are you sure GAP? last = last2; # Okay, but what do you think of: last = last2; # Ah, I see, but what about: last = last2; # Please, GAP, make up your mind! # Keeping my condition ############################################# # The time Martin spend behind the computer needs to be compensated with # physical exercise. But how much exercise? Fortunately GAP can help him # calculate how many miles he has run. Suppose we give him three hours to run: time := 3;; # The first sign he sees says: "Aachen 200 miles". We enter this in GAP: first := 200;; # After three hours the roadsign says: "Aachen 170 miles". And we tell GAP: last := 170;; # To be sure, let's check if GAP got it right: last; first; # Now that looks good. So GAP, how many miles did Martin run: dist := last-first;; Print("Martin has run ", dist ," miles. Congratulations!\n"); Print("Oh, it took him ",time," hours to do it\n"); # Oops! I guess we need some more time behind the computer in stead of # running... The StudGAP's, Erik, Jasper & Reinald From kumar@cs.ucf.edu Fri May 27 16:04:00 1994 From: "Nishit Kumar" Date: Fri, 27 May 94 16:04 -0400 Subject: Math/Graph Theory packages ... Is anyone aware of a consolidated bibliography of s/w packages which have implemented graph algorithms/ combinatorial algorithms. Any help will be appreciated. Nishit Kumar Dept of Computer Science Univ. of Central Florida From leonard@qmw.ac.uk Tue May 31 12:49:00 1994 From: "Leonard Soicher" Date: Tue, 31 May 94 12:49 +0200 Subject: Re: Math/Graph Theory packages ... The published paper about the GRAPE package is: L.H. Soicher, GRAPE: a system for computing with graphs and groups, in "Groups and Computation" (L. Finkelstein and W.M. Kantor, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 11, American Mathematical Society, 1993, pp. 287-291. However, this reference describes GRAPE before it became an official GAP share library package, and the best documentation on GRAPE is now the chapter "Grape" in the GAP manual. This chapter is available online in GAP in the usual way. If you use GAP/GRAPE to solve a problem, then the above paper should be referenced, as well as the GAP manual. Regards, Leonard Soicher. From lbartho@scsun.unige.ch Thu Jun 2 12:56:00 1994 From: "BARTHOLDI Laurent" Date: Thu, 02 Jun 94 12:56 +0200 Subject: X11+Linux Hello GAPers, I'm setting up GAP on a Linux PC. The text version goes OK, but xgap doesn't work: gap starts and no input can be fed to the gap subprocess. Compilation had worked fine, though. just a minor change in undefined signals. To make it worse, I tried to compare that with xgap on a SUN and couldn't compile it. It ends with cc -L/usr/openwin/lib -o xgap xcmds.o utils.o gapgraph.o gaptext.o pty.o popdial.o main.o -lXmu -lXaw -lXt -lXext -lX11 -lm ld: Undefined symbol _get_wmShellWidgetClass _get_applicationShellWidgetClass *** Error code 2 If someone has a clue for any one of these problems (mostly for Linux), please help. larry lbartho@scsun.unige.ch From sl25@cus.cam.ac.uk Thu Jun 2 13:36:00 1994 From: "Steve Linton" Date: Thu, 02 Jun 94 13:36 +0200 Subject: Re: X11+Linux > I'm setting up GAP on a Linux PC. The text version goes OK, but xgap doesn't > work: gap starts and no input can be fed to the gap subprocess. > Compilation had worked fine, though. just a minor change in undefined > signals. > To make it worse, I tried to compare that with xgap on a SUN and couldn't > compile it. It ends with > > cc -L/usr/openwin/lib -o xgap xcmds.o utils.o gapgraph.o gaptext.o pty.o popdial > .o main.o -lXmu -lXaw -lXt -lXext -lX11 -lm > ld: Undefined symbol > _get_wmShellWidgetClass_get_wmShellWidgetClass > _get_applicationShellWidgetClass > *** Error code 2 > > If someone has a clue for any one of these problems (mostly for Linux), > please help. I too have had problems with xgap under OpenWindows. It seemed to spend all it's time flickering somehow, and never got any work done. Under X11R6 it works fine. To get it to compile try re-searching libXmu at the end of your list. From Frank.Celler@Math.RWTH-Aachen.DE Thu Jun 2 14:32:00 1994 From: "Frank Celler" Date: Thu, 02 Jun 94 14:32 +0200 Subject: Re: X11+Linux Dear Gap-Forum, To make it worse, I tried to compare that with xgap on a SUN and couldn't compile it. It ends with cc -L/usr/openwin/lib -o xgap xcmds.o utils.o gapgraph.o gaptext.o pty.o popdial.o main.o -lXmu -lXaw -lXt -lXext -lX11 -lm ld: Undefined symbol _get_wmShellWidgetClass _get_applicationShellWidgetClass *** Error code 2 XGAP really requires X11R5 (or 6), at least to compile. If you try to compile it using either X11R4 or OpenWin you *might* end up with some undefined symbols or possible with a version that is useless, as it starts flickering the cursor once every millisecond, because of some bug in the older X Versions. However, once compiled using X11R5 it should run under X11R4 or OpenWindows, there is a precompiled version on "ftp.math.rwth-aachen.de" in the directory "pub/gap/bin" for Suns. However, there is still another problem, some older version of GCC on Suns seem to have a problem with 'ioctl' so if in case one has the X11R5 library it is better to compile XGAP using the native CC. As for the Linux version: I don't have any access to a linux machine, but I was told that someone has compiled XGAP on such a machine, I will try to find out more details about it. best wishes Frank From ken@poincare.arc.nasa.gov Thu Jun 2 10:40:00 1994 From: "Kenneth H. Simpson" Date: Thu, 02 Jun 94 10:40 -0700 (PDT) Subject: Re: X11+Linux >>Dear Gap-Forum, >> >> To make it worse, I tried to compare that with xgap on a SUN and couldn't >> compile it. It ends with >> >> cc -L/usr/openwin/lib -o xgap xcmds.o utils.o gapgraph.o gaptext.o pty.o >> popdial.o main.o -lXmu -lXaw -lXt -lXext -lX11 -lm >> ld: Undefined symbol >> _get_wmShellWidgetClass >> _get_applicationShellWidgetClass >> *** Error code 2 >> >>XGAP really requires X11R5 (or 6), at least to compile. If you try to compile >>it using either X11R4 or OpenWin you *might* end up with some undefined >>symbols or possible with a version that is useless, as it starts >>flickering the cursor once every millisecond, because of some bug >>in the older X Versions. However, once compiled using X11R5 it should run >>under X11R4 or OpenWindows, there is a precompiled version on >>"ftp.math.rwth-aachen.de" in the directory "pub/gap/bin" for Suns. >> >>However, there is still another problem, some older version of >>GCC on Suns seem to have a problem with 'ioctl' so if in case one has >>the X11R5 library it is better to compile XGAP using the native CC. >> >>As for the Linux version: I don't have any access to a linux machine, >>but I was told that someone has compiled XGAP on such a machine, I >>will try to find out more details about it. >> >>best wishes >> Frank >> You should still have an executable which should work despite the ld errors. Try running it - it should work. (Those ld errors are from dummy routines.) -- Ken From tomo.pisanski@uni-lj.si Thu Jun 2 09:51:00 1994 From: "Tomaz Pisanski" Date: Thu, 02 Jun 94 09:51 +0200 Subject: Bibliography on Graph Algorithms Just before I managed to register to GAP-Forum the following question has been forwarded to me. > > Is anyone aware of a consolidated bibliography of s/w packages > which have implemented graph algorithms/ combinatorial > algorithms. Any help will be appreciated. > > > Nishit Kumar > Dept of Computer Science > Univ. of Central Florida > > The paper Algorithms for Drawing Graphs: an Annotated Bibliography by G. DiBattista, P. Eades, R. Tamassia and I.G. Tollis used to be available via ftp from wilma.cs.brown.edu as /pub/gdbiblio.tex.Z and /pub/gdbiblio.ps.Z It is possible to get more information by writing to redsoft@cs.brown.edu The book: Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, by Steven Skiena describes the package Combinatorica that comes with Mathematica. _______________________________________________________________________ Tomaz Pisanski +386-61-125-71-00/71 Univerza v Ljubljani +386-61-127-33-14(home) IMFM, odd. za teoreticno racunalnistvo +386-61-217-281(fax) Jadranska 19, SLO 61111 Ljubljana Slovenija Tomaz.Pisanski@uni-lj.si _______________________________________________________________________ From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Jun 3 10:56:00 1994 From: "Joachim Neubueser" Date: Fri, 03 Jun 94 10:56 +0200 Subject: Re: X11+Linux Dear Colleagues, This is clearly an installation problem that concerns only very few GAP users. Could we please shift its further discussion to 'gap-trouble' which has been organized for such cases. Generally, could questions of this kind please be sent to 'gap-trouble', where a group of rather experienced users of GAP in Aachen and abroad will read them and try to provide an answer. Only if this group does not know an answer or if the problem is likely to concern a greater number of users will we then post it to the forum. This way we try to save some 250 participants of the GAP-forum from mail that does not concern them. Thank you Joachim Neubueser From william_kocay@macmail.cs.umanitoba.ca Mon Jun 6 14:01:00 1994 From: "William Kocay" Date: Mon, 06 Jun 94 14:01 -0600 Subject: Re: Bibliography on Graph Al Reply to: RE>Bibliography on Graph Algor Groups & Graphs is a software package for graphs and their automorphism groups. It runs on a MacIntosh platform, and is available via anonymous ftp from ftp.cc.umanitoba.ca in the directory /pub/mac The current version is 2.1. A new version (2.2) will soon be released. Bill Kocay bkocay@cs.umanitoba.ca From leonard@qmw.ac.uk Tue Jun 7 14:18:00 1994 From: "Leonard Soicher" Date: Tue, 07 Jun 94 14:18 +0200 Subject: Re: Bibliography on Graph Al Re: Groups & Graphs. Please tell me more about what this package can do. Does it interface with GAP ? Regards, Leonard. From kumar@cs.ucf.edu Tue Jun 7 10:40:00 1994 From: "Nishit Kumar" Date: Tue, 07 Jun 94 10:40 -0400 Subject: Re: Bibliography on Graph Al For a journal paper see: Groups&Graphs, W.Kocay, A MacIntosh application for graph theory Jo. of Combinatorial Mathematics and Combinatorial Computing, 3:195-206, 1988. Groups & Graphs is a software package for graphs and their automorphism groups. It runs on a MacIntosh platform, and is available via anonymous ftp from ftp.cc.umanitoba.ca in the directory /pub/mac The current version is 2.1. A new version (2.2) will soon be released. Contact: bkocay@cs.umanitoba.ca I haven't yet got a chance to ftp the code and install it here on our machine. Luck, Nishit From mueller@mi.uni-erlangen.de Thu Jun 9 16:27:00 1994 From: "Peter Mueller" Date: Thu, 09 Jun 94 16:27 +0200 Subject: Weird message Dear Gap-forum, using the most recent version of GAP (under UNIX), the program below yields, after some successful runs even over the innermost `for'-loops, the following message I don't understand what it comes from and what it is supposed to tell me. By the way, I found no smaller group than the Mathieu group M_24 producing this phenomenon. Peter ---------------------------------------------------------------- OrbRep:=function(g,s) return List(Orbits(g,s),x->x[1]); end; g:=PrimitiveGroup(24,3);# M24 cg:=Filtered(ConjugacyClasses(g),x->Size(x)>1 and not IsAbelian(Centralizer(g,Representative(x)))); Sort(cg,function(v,w) return Size(v)>Size(w);end); Print(g,"\n"); for ca in cg do a:=Representative(ca); ca:=Centralizer(g,a); cca:=Filtered(ConjugacyClasses(ca),x->Size(x)>1 and not IsAbelian(Centralizer(g,Representative(x)))); Sort(cca,function(v,w) return Size(v)>Size(w);end); for cclass in cca do c:=Representative(cclass); if not c in Subgroup(g,[a]) then for d in Difference(OrbRep(Centralizer(ca,c),Elements(cclass)), Subgroup(g,[a,c])) do if c*d*c=d*c*d then h3:=Subgroup(g,[a,c,d]); for b in Difference(OrbRep(Centralizer(g,h3), Elements(ConjugacyClass(Centralizer(g,d),a))),h3) do if a*b*a=b*a*b and b*c*b*c=c*b*c*b then h:=Subgroup(g,[a,b,c,d]); Print(Order(g,a)," ",Order(g,c)," ",Size(h),"\n"); fi; od; fi; od; fi; od; od; ---------------------------------------------------------------- gap> Read("F4"); M(24) 7 2 1008 7 2 1008 5 3 720 ... (many lines deleted) 3 3 576 3 4 288 3 2 72 Error, Record: element 'fusingElement' must have an assigned value at fusingElement := power.fusingElement ^ (Size( power.galoisGroup ) / (sizeKnownPart * div[i])) ... in CompleteGaloisGroupPElement( G, rationalClasses[j], rationalClasses[j].powers[p], p ) called from RationalClassesPElements( G, p ) called from RationalClassesPermGroup( G ) called from G.operations.RationalClasses( G ) called from RationalClasses( G ) called from ... brk> quit; gap> quit; From Alexander.Hulpke@Math.RWTH-Aachen.DE Thu Jun 9 16:43:00 1994 From: "Alexander Hulpke" Date: Thu, 09 Jun 94 16:43 +0200 Subject: Re: Weird message Dear Gap-Forum, Peter Mueller wrote: > using the most recent version of GAP (under UNIX), the program below > yields [...] [an error]. This is a known bug in the routine for ConjugacyClasses in permutation groups, which was modified from 3.2 -> 3.3. It is fixed in GAP 3.4 (which should be out REALLY soon now :-) ). If you get an confusing error message from deep inside, ending with ..., you might try Backtrace() to see a longer call history. In this example you can see, that is was initiated by ConjugacyClasses. (This obviously does not fix the bug, but it might help seeing, what went wrong.) I would like to take the opportunity (for example this bug has been mentioned already several times in the Forum) to remind you of the adress gap-trouble@samson.math.rwth-aachen.de, which is designed specially for error reports: Save your co-Forum-readers from reading long error reports. Alexander Hulpke From charnes@osiris.cs.uow.edu.au Fri Jun 10 12:02:00 1994 From: "Chris Charnes" Date: Fri, 10 Jun 94 12:02 +1000 Subject: Re: Weird message How do we get version 3.4? Does it entail getting the whole system again? Chris Charnes From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Jun 10 14:25:00 1994 From: "Joachim Neubueser" Date: Fri, 10 Jun 94 14:25 +0200 Subject: Re: Weird message Dear Colleagues, Chris Charnes question > How do we get version 3.4? > Does it entail getting the whole system again? reflects some confusion that partially may have been caused by Alexander Hulpke's reply to the 'Weird message'. Let me just put facts straight: GAP 3.4 has not yet been released but indeed the release is close ahead. Even if nobody is prepared to bet for that, I hope for next week. Yes, getting 3.4 will entail getting the whole system again. The change from 3.3 to 3.4 will mean a growth of the code (and the manual - sorry!) by about 25%, so this cannot be done by patches. We will post an announcement with details in the gap-forum as soon as 3.4 can be ftp'd again from servers, please wait for that, but also look at the GAP-forum. As his last remark Alexander suggested sending error reports like the 'weird message' to gap-trouble rather than to gap-forum. I do not quite agree. It is true that the bug which was reported in the 'weird message' had been reported before, but it may have not even been obvious to many GAP users that this was indeed the same bug. Of course the bugs that by all means should be reported in the forum are those that produce a wrong result that cannot be recognised as being wrong at first sight. Bugs like the one reported in the 'weird message' producing a rather difficult error message, are annoying but not quite as dangerous. They may go to gap-trouble and after finding out what is the matter, we will report to the forum, if they are of the 'dangerous' species, but in my view there is nothing at all wrong in sending them to the forum directly. Problems that arise with the installation or use of GAP on a specific computer or with a specific operating system are clear candidates for gap-trouble but all that can happen to any gap user on any computer can and should in principle be communicated to the gap-forum. I hope that having to throw away some letters is not too high a price for being kept fully informed of whatever happens, good or bad, in the system that you are using. Experience with previous releases shows that after the forthcoming release we will have to expect some flood of both technical questions in gap-trouble and discussions in gap-forum. Therefore I thought that I should state (repeat) the above now. Also I want to ask your understanding if right after the release we may get a bit slow in answering. Nevertheless have fun with GAP 3.4 (when it is out). Joachim Neubueser From charnes@osiris.cs.uow.edu.au Tue Jun 14 11:10:00 1994 From: "Chris Charnes" Date: Tue, 14 Jun 94 11:10 +1000 Subject: Re: Weird message Looking forward to version 3.4. Chris Charnes From jcbhrb@cerf.net Tue Jun 14 00:18:00 1994 From: "Jacob Hirbawi" Date: Tue, 14 Jun 94 00:18 -0700 Subject: Quadratic subfields of Q(E(n)) Is there a way to tell GAP to do calculations in a field smaller than Q(E(n)) ? For example, if I have matrices over Q( sqrt(-7), sqrt(5) ), GAP translates all the entries to E(35) and that results in expressions that are much more complicated than they have to be; ER(-7) + ER(5) for example becomes 2*E(35)-2*E(35)^3+2*E(35)^4+2*E(35)^9+2*E(35)^11-2*E(35)^12-2*E(35)^13 +2*E(35)^16-2*E(35)^17-2*E(35)^27+2*E(35)^29-2*E(35)^33 I looked at "NumberField" which seems to set up such subfields, but I couldn't find anything that goes beyond this. Is what I am trying to do possible in 3.3? how about 3.4? Thanks. Jacob Hirbawi JcbHrb@CERF.net From Alexander.Hulpke@Math.RWTH-Aachen.DE Tue Jun 14 11:07:00 1994 From: "Alexander Hulpke" Date: Tue, 14 Jun 94 11:07 +0200 Subject: Re: Quadratic subfields of Q(E(n)) Dear Gap-forum, Jakob Hirbawi asked: > Is there a way to tell GAP to do calculations in a field smaller than > Q(E(n)) ? GAP will do computations in the smallest cyclotomic field. > For example, if I have matrices over Q( sqrt(-7), sqrt(5) ), GAP translates > all the entries to E(35) and that results in expressions that are much more > complicated than they have to be. However even if you specify subfields (by 'NumberField'), internal representation will be made using the smallest root of unity possible. In your example, this is E(35). > I looked at "NumberField" which seems to set up such subfields, but I couldn't > find anything that goes beyond this. Is what I am trying to do possible in > 3.3? how about 3.4? Thanks. Not in 3.3. Version 3.4 (I won't comment about release dates ...) will contain code for arbitrary algebraic extensions (Though up to now, only simple extensions, so you will still have to do some work by hand). In 3.4, your example would become (This example will not yet work in 3.3): # We set up both polynomials gap> x:=X(Rationals);;x.name:="x";; gap> f:=x^2-5;; gap> g:=x^2+7;; gap> R:=PolynomialRing(RationalsPolynomials);; gap> y:=X(RationalsPolynomials);;y.name:="y";; gap> Value(g,y); y^2 + (7*x^0) Now construct an extension containing roots of both polynomials: The polynomial Res_y(f(x-y),g(y)) has ER(5)+ER(-7) as a root. It is a good candidate for the extension spanned by both roots. gap> r:=-Resultant(Value(f,x-y),Value(g,y)); x^4 + 4*x^2 + 144 We check, whether it is indeed irreducible (then it must span the correct extension by degree arguments) gap> Factors(r); [ x^4 + 4*x^2 + 144 ] Now construct the extension. gap> e:=AlgebraicExtension(r);e.name:="e";; AlgebraicExtension(Rationals,x^4 + 4*x^2 + 144) And take a root of r (No selection which root to be taken will be made) gap> RootOf(r).name:="alpha";; Now identify the roots of both original polynomials gap> R:=PolynomialRing(e);; gap> f:=EmbeddedPolynomial(R,f); X(e)^2 - 5 gap> ff:=Factors(f); [ X(e) + (1/24*alpha^3-1/3*alpha), X(e) + (-1/24*alpha^3+1/3*alpha) ] gap> sqrfive:=-ff[2].coefficients[1]; 1/24*alpha^3-1/3*alpha It is indeed a root of 5. gap> sqrfive^2; 5 The same for ER(-7): gap> g:=EmbeddedPolynomial(R,g); X(e)^2 + 7 gap> gg:=Factors(g); [ X(e) + (-1/24*alpha^3-2/3*alpha), X(e) + (1/24*alpha^3+2/3*alpha) ] gap> isqrseven:=-gg[1].coefficients[1]; 1/24*alpha^3+2/3*alpha gap> isqrseven^2; -7 Now summation produces much nicer results, all computations will be done in this deg4 extension: gap> isqrseven+sqrfive; 1/12*alpha^3+1/3*alpha However, now representation is done using GAP-language level routines which are slower than the kernel routines for cyclotomics. I have made no experiments to check, where the 'break even' point would be. Up to now, there is also no facility, to allow using a different base for the specified algebraic extension. These drawbacks will hopefully be removed in the future. Alexander Hulpke From leonard@qmw.ac.uk Tue Jun 14 12:05:00 1994 From: "Leonard Soicher" Date: Tue, 14 Jun 94 12:05 BST Subject: Re: Quadratic subfields of Q(E(n)) Given generators a,b,c,... of a finite algebraic extension of the rationals, would it not be possible for Gap 3.4+epsilon to calculate a minimal polynomial for a single element t such that Q(t)=Q(a,b,c,...), by applying an algorithmic version of the primitive element theorem? It seems like most of what is necessary is already in Gap 3.4. Leonard Soicher. From Joachim.Neubueser@Math.RWTH-Aachen.DE Tue Jun 14 14:33:00 1994 From: "Joachim Neubueser" Date: Tue, 14 Jun 94 14:33 +0200 Subject: Re: Quadratic subfields of Q(E(n))u Dear Forum, Leonard Soicher writes: > Given generators a,b,c,... of a finite algebraic extension of the > rationals, would it not be possible for Gap 3.4+epsilon to calculate a > minimal polynomial for a single element t such that > Q(t)=Q(a,b,c,...), by applying an algorithmic version of the primitive > element theorem? It seems like most of what is necessary is already > in Gap 3.4. Yes, that should be possible, and it can be done completely in the GAP language. If somebody wants urgently to have such a function, and is willing to write it, we would welcome if he deposits it in 'incoming' directory on our server. We have plans to provide facilities for handling general field extensions, but then we would like to try to do this in a reasonably organized package rather than by providing a collection of patches. This however will take its time, i.e. epsilon is likely to be a positive integer. Kind regards Joachim Neubueser From Joachim.Neubueser@Math.RWTH-Aachen.DE Tue Jun 14 16:47:00 1994 From: "Joachim Neubueser" Date: Tue, 14 Jun 94 16:47 +0200 Subject: delay Dear Colleagues, With regret I have to tell you that I have mislead you again by my optimism, we will postpone the release of 3.4 by at least one week. The reason is that we want to use the opportunity of having Akos Seress here in Aachen to bind into GAP 3.4 some of his higly efficient random methods for permutation groups (in particular for high degrees), and to do this in a way that makes transparent to the user whether he uses deterministic or random methods. I hope that the gain of getting a better GAP will make good for any inconvenience I may have caused you if you relied on my predictions about the release date. With apologies Joachim Neubueser From charnes@osiris.cs.uow.edu.au Wed Jun 15 11:28:00 1994 From: "Chris Charnes" Date: Wed, 15 Jun 94 11:28 +1000 Subject: Re: delay Joachim, one or two or three weeks, it doesn't matter. I am using the current version and it's doing what I want. When 3.4 is ready I will get that. Yours Chris Charnes From leonard@qmw.ac.uk Thu Jun 16 13:38:00 1994 From: "Leonard Soicher" Date: Thu, 16 Jun 94 13:38 BST Subject: Random Algorithms Dear Gap-Forum, I very much look forward to the inclusion of Akos Seress' fast random algorithms for permutation groups into Gap 3.4, and can certainly wait a while in order to make sure they are smoothly integrated into the system. However, if these algorithms are going to run without the user being aware then they must provide a certain result when they return a result at all. If there is some probability of the answer being wrong then the user must be alerted to this fact, and hopefully also be provided with the probability of an error. For example, if the group order is said to be n, then for certain algorithms the order is at least n, but may be greater than n with a small probability. Such functions are very very useful when playing around in groups to, say, find a subgroup of a given order, but in the end we must have a proof. I expect these considerations have already been well thought out by the Gap designers, but I just wanted to make my concerns clear. When I use a function (such as the very useful but undocumented MakeStabChainRandom in Gap 3.3), I always want to know precisely to what extent the results are certain. Sincerely, Leonard Soicher. From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jun 16 15:05:00 1994 From: "Joachim Neubueser" Date: Thu, 16 Jun 94 15:05 +0200 Subject: Re: Random Algorithms Dear Forum members, > Dear Gap-Forum, > > I very much look forward to the inclusion of Akos Seress' fast random > algorithms for permutation groups into Gap 3.4, and can certainly wait > a while in order to make sure they are smoothly integrated into the > system. > > However, if these algorithms are going to run without the user being > aware then they must provide a certain result when they return a result > at all. If there is some probability of the answer being wrong then > the user must be alerted to this fact, and hopefully also be provided > with the probability of an error. For example, if the group order is > said to be n, then for certain algorithms the order is at least n, > but may be greater than n with a small probability. Such functions > are very very useful when playing around in groups to, say, find a > subgroup of a given order, but in the end we must have a proof. > > I expect these considerations have already been well thought out by > the Gap designers, but I just wanted to make my concerns clear. > When I use a function (such as the very useful but undocumented > MakeStabChainRandom in Gap 3.3), I always want to know precisely > to what extent the results are certain. > > Sincerely, Leonard Soicher. Thanks to the second user now assuring us of your patience. In return I can assure you that what you suggest to consider is exactly what is being done at present while keeping you waiting for 3.4. We certainly do not intend to hide any function which produces results fast but with a certain built-in error probability from the user. (S)he will have complete control of using these or (slower) deterministic functions. Kind regards Joachim Neubueser From jcbhrb@cerf.net Fri Jun 17 00:55:00 1994 From: "Jacob Hirbawi" Date: Fri, 17 Jun 94 00:55 -0700 Subject: order of conjugacy classes Does Dixon's algorithm for calculating character tables always order classes the same way that "ConjugacyClasses" does? Suppose I have a permutation representation of a group and I use "CharTable" to calculate the character table which GAP does using Dixon's algorithm. If I then use "ConjugacyClasses" to get (what else!) the conjugacy classes. Is it *guaranteed* that the classes are sorted in the same order in both cases. My guess, and my hope, is that they are. In fact I have been relying on this fact for some calculations, is this dangerous practice? My other question is a long shot but here it goes : I have a matrix group generated by M1,M2,M3,and M4. generate a subgroup for which I found a permutation representation . generate another subgroup for which I can also get a permutation reprersentation . The p's may or may not be of the same degree as the q's. I can't get a permutation rep for the entire group directly because it's a huge group, so I'm hoping to approach it using the reps of the two subgroups. Are there any facilities in GAP that can help? Thanks. Jacob Hirbawi Jcbhrb@CERF.net From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Jun 17 11:59:00 1994 From: "Joachim Neubueser" Date: Fri, 17 Jun 94 11:59 +0200 Subject: Re: order of conjugacy classes Dear Forum members, Jacob Hirbawi asked: > Does Dixon's algorithm for calculating character tables always order > classes the same way that "ConjugacyClasses" does? The answer is "yes". > Suppose I have a permutation representation of a group and I use "CharTable" > to calculate the character table which GAP does using Dixon's algorithm. > If I then use "ConjugacyClasses" to get (what else!) the conjugacy classes. > Is it *guaranteed* that the classes are sorted in the same order in both > cases. My guess, and my hope, is that they are. In fact I have been relying > on this fact for some calculations, is this dangerous practice? The answer is "no". > My other question is a long shot but here it goes : > > I have a matrix group generated by M1,M2,M3,and M4. generate > a subgroup for which I found a permutation representation . > generate another subgroup for which I can also get a > permutation reprersentation . The p's may or may not be of > the same degree as the q's. I can't get a permutation rep for the entire > group directly because it's a huge group, so I'm hoping to approach it > using the reps of the two subgroups. Are there any facilities in GAP that > can help? Thanks. There can't be such facilities: Take the symmetric group on 5 letters (in some matrixgroup representation if you like) and take the elements M1 = (1), M2 = (1,3)(2,4), M3 = (1,2)(3,4), M4 = (1,5). Then M1, M2, and M3 generate a Klein four group, while M1, M2, and M4 generate a dihedral group of order 12. But if you have just independent permutation representations of the Klein four group and a dihedral group of order 12 then you have no information into which group they embed; for all you know this constellation may come from the direct product of a dihedral group of order 12 with a cyclic group of order two, that is, you may have elements N1 = (1), N2 = (1,3)(2,4), N3 = (6,7), and N4 = (1,5) Then also N1, N2, and N3 generate a Klein four group and N1, N2, and N4 still generate a dihedral group of order 12, but all N's together generate the above claimed direct product. Kind regards Joachim Neubueser From ara@altdorf.ai.mit.edu Fri Jun 24 11:53:00 1994 From: "Allan Adler" Date: Fri, 24 Jun 94 11:53 -0400 Subject: Adding online documentation I have received and also written some GAP programs that I plan to use extensively. It would be convenient to be able to add some online documentaiton for them, such as already exists for the rest of GAP, for my private use. Please tell me in words of one syllable how to do this. I am pretty sure that the answer involves hacking the TeX files for the manual, but simply adding new sections or new entries to the table of contents doesn't seem to be enough. There may also be something involving the magic word "hashing", but I don't know how to work with that. I noticed that there are other tricks that are used on the .g files in the library, such as putting emacs in Outline mode when one looks at them in emacs. But I think that has nothing to do with the online documentation. Allan Adler ara@altdorf.ai.mit.edu From pjipsen@iastate.edu Fri Jun 24 13:54:00 1994 From: "Peter Jipsen" Date: Fri, 24 Jun 94 13:54 -0500 Subject: order of booleans in GAP Just an idle question: Is there a particular reason why GAP defines true < false ? I would have expected the opposite, probably because some languages identify false with 0. Peter Jipsen From Martin.Schoenert@Math.RWTH-Aachen.DE Mon Jun 27 13:39:00 1994 From: "Martin Schoenert" Date: Mon, 27 Jun 94 13:39 +0100 (MET) Subject: Re: order of booleans in GAP No, there is no particular reason. I seem to recall that in an intermediate version (between 2.4 and 3.1) 'true' was less than 'false' because the former was created before the latter. 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 Mon Jun 27 14:04:00 1994 From: "Martin Schoenert" Date: Mon, 27 Jun 94 14:04 +0100 (MET) Subject: Re: Adding online documentation Allan Adler writes in his e-mail message of 1994/06/24 I have received and also written some GAP programs that I plan to use extensively. It would be convenient to be able to add some online documentaiton for them, such as already exists for the rest of GAP, for my private use. Please tell me in words of one syllable how to do this. First make a '.tex' file for each chapter that you want to add and add a corresponding line \Include{} to 'manual.tex'. Note the capitalization. Also note that the name of the file must not contain more than 8 characters (excluding the '.tex' suffix) and must not contain any special characters. The file must begin with the line \Chapter{} (after optional comments). Again note the capitalization. The name of the chapter must be different from the names of the other chapters and their sections. Each section must begin with a line \Section{} (again after optional comments). The name of the section must be different from the names of the other sections. In the description use quotes for typewriter style text (e.g. 'MySpecialFunction'). Use angle brackets for italics (e.g. ). Use double quotes for references to other sections (e.g. see also "The New Chapter"). Use asterisks for bold text (e.g. do *not* call this function with an *infinite* group). Use pipes for examples, for example | gap> MySpecialFunction( 10 ); 10 | Run LaTeX on 'manual' often enough to create all crossreferences. Usually you must run LaTeX three times latex manual bibtex manual latex manual makeindex manual latex manual That should do the trick. Allan Adler continues I am pretty sure that the answer involves hacking the TeX files for the manual, but simply adding new sections or new entries to the table of contents doesn't seem to be enough. There may also be something involving the magic word "hashing", but I don't know how to work with that. As pointed out above it is important to capitalize the '\Chapter' and '\Section' LateX commands, because this is what the help function is looking for. Apart from that no special hacking is needed. Using instead of {\it italics} is simply used to make the result look nice on the screen. The hashing was used in an older version. We have lots of crossreferences, and they exhausted the small TeX that we were using at that time. By hashing the labels we used less of TeX's memory. But of course ultimately there was no way we could get the GAP manual through a small TeX. When we decided to require a big TeX there was no reason for hashing any more, and we dropped it. Writing this hashing code was probably the worst experience I ever had with TeX ;-). Allan Adler continues I noticed that there are other tricks that are used on the .g files in the library, such as putting emacs in Outline mode when one looks at them in emacs. But I think that has nothing to do with the online documentation. Correct, this is simply for our convenience. I hope this helps. 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 Tue Jun 28 13:16:00 1994 From: "Alexander Hulpke" Date: Tue, 28 Jun 94 13:16 +0200 Subject: Re: Bug in 'SubdirectProduct' when using the projection Dear Forum, In his message, Ottokar Kulendik intended to write (but some technical error dropped the content): > Hello forum, > > I think I have discovered a bug in the function 'SubdirectProduct()': the > call of 'Projection()' fails like in the following example: > > # example from the GAP manual entry 'Subdirect Product' > # computing a subdirect product > gap> s3 := Group( (1,2,3), (1,2) );; > gap> c3 := Subgroup( s3, [ (1,2,3) ] );; > gap> x1 := Operation( s3, Cosets( s3, c3 ), OnRight );; > gap> h1 := OperationHomomorphism( s3, x1 );; > gap> d8 := Group( (1,2,3,4), (2,4) );; > gap> c4 := Subgroup( d8, [ (1,2,3,4) ] );; > gap> x2 := Operation( d8, Cosets( d8, c4 ), OnRight );; > gap> h2 := OperationHomomorphism( d8, x2 );; > gap> s := SubdirectProduct( s3, d8, h1, h2 ); > Group( (1,2,3), (1,2)(5,7), (4,5,6,7) ) > > # now trying to use a projection on an arbitrary element of s > gap> x := Random(s); > (1,3)(4,6) > gap> projection := Projection(s, s3, 1); > Projection( Group( (1,2,3), (1,2)(5,7), (4,5,6,7) ), Group( (1,2,3), (1,2) ), 1 ) > gap> x in projection.source; > true > gap> x^projection; > Error, Record: element 'news' must have an assigned value at > img := RestrictedPerm( elm, prj.source.news[prj.component] ) > ^ (prj.source.perms[prj.component] ^ (-1 * 1)) ... in > rgt.operations.ImageElm( rgt, lft ) called from > ^ called from > main loop > brk> > > I am a new GAP user and reader of the forum, so I don't know whether this is > an already known bug. No, it is not known, but it is a bug, introduced because the subdirect product is again a permutation group and tries to be clever by using the projection routines also used for direct products of permutation groups. However, SudirectProduct forgets to copy some necessary components: > Is it okay to copy the entries 'projection.source.news' > and 'projection.source.perms' from the direct product projection? Exactly this is needed. This is fixed in GAP 3.4. > Ottokar Kulendik Sorry for the inconvenience, Alexander Hulpke From gcliff@vega.math.ualberta.ca Tue Jun 28 15:58:00 1994 From: "Gerald Cliff" Date: Tue, 28 Jun 94 15:58 -0600 (MDT) Subject: Semi-direct products Given a finite group G and an automorphism f of G, it would be nice if GAP would give an easy implementation of the semi-direct product G. of G by the cyclic group generated by f. Gerald Cliff University of Alberta gcliff@vega.math.ualberta.ca From Alexander.Hulpke@Math.RWTH-Aachen.DE Wed Jun 29 09:52:00 1994 From: "Alexander Hulpke" Date: Wed, 29 Jun 94 09:52 +0200 Subject: Re: Semi-direct products Dear GAP-Forum., Gerald Cliff asked: > Given a finite group G and an automorphism f of G, > it would be nice if GAP would give an easy implementation > of the semi-direct product G. of G by the cyclic > group generated by f. Does 'SemidirectProduct' not suit your needs? For example gap> g:=SymmetricGroup(6); gap> hom:=GroupHomomorphismByImages(g,g,g.generators,[(1,4)(2,3)(5,6), > (1,6)(2,5)(3,4),(1,3)(2,6)(4,5),(1,5)(2,4)(3,6),(1,2)(3,5)(4,6)]) gap> H:=Group(hom); Group( GroupHomomorphismByImages( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), [ (1,6), (2,6), (3,6), (4,6), (5,6) ], [ (1,4)(2,3)(5,6), (1,6)(2,5)(3,4), (1,3)(2,6)(4,5), (1,5)(2,4)(3,6), (1,2)(3,5)(4,6) ] ) ) gap> Size(H); 10 We will need a mapping from H onto a group of automorphisms. In this case, it is the identity: gap> sdp:=SemidirectProduct(H,IdentityMapping(H),g); Group( SemidirectProductElement( GroupHomomorphismByImages( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), [ (1,6), (2,6), (3,6), (4,6), (5,6) ], [ (1,4)(2,3)(5,6), (1,6)(2,5)(3,4), (1,3)(2,6)(4,5), (1,5)(2,4)(3,6), (1,2)(3,5)(4,6) ] ), GroupHomomorphismByImages( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), Group( (1,6), (2,6), (3,6), (4,6), (5,6) ), [ (1,6), (2,6), (3,6), (4,6), (5,6) ], [ (1,4)(2,3)(5,6), (1,6)(2,5)(3,4), (1,3)(2,6)(4,5), (1,5)(2,4)(3,6), (1,2)(3,5)(4,6) ] ), () ), SemidirectProductElement( IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), (1,6) ), SemidirectProductElement( IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), (2,6) ), SemidirectProductElement( IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), (3,6) ), SemidirectProductElement( IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), (4,6) ), SemidirectProductElement( IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), IdentityMapping( Group( (1,6), (2,6), (3,6), (4,6), (5,6) ) ), (5,6) ) ) gap> Size(sdp); 7200 Alexander Hulpke From "agnesi::hart"@physics.hope.edu Thu Jun 30 16:11:00 1994 From: "Evelyn Hart" <"agnesi::hart"@physics.hope.edu> Date: Thu, 30 Jun 94 16:11 -0400 Subject: can GAP do group rings? I don't have GAP, and I'm wondering whether to get it. I'm new to the forum, so you've heard this one before, be nice. Does GAP do calculations with group rings? 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. This is the fundamental group of the double torus. It is an ugly group, because it contains words of arbitrarily long length that can not be reduced. That's my question. If GAP can work with such a thing, I'll get GAP. Thanks, Evelyn Hart hart@math.hope.edu