This file contains the mails sent to the GAP forum in January-March 1994. Name Email address Mails Lines Steve Linton sl25@cus.cam.ac.uk 11 256 Joachim Neubueser Joachim.Neubueser@Math.RWTH-Aachen.DE 10 715 Martin Schoenert Martin.Schoenert@Math.RWTH-Aachen.DE 8 402 Frank Celler Frank.Celler@Math.RWTH-Aachen.DE 8 372 Alexander Hulpke Alexander.Hulpke@Math.RWTH-Aachen.DE 6 397 Jacob Hirbawi jcbhrb@cerf.net 5 152 Volkmar Felsch Volkmar.Felsch@Math.RWTH-Aachen.DE 3 265 Dima Pasechnik dima@maths.uwa.edu.au 3 225 Harald Boegeholz hwblist@machnix.mathematik.uni-stuttgart.de 3 93 Thomas Breuer Thomas.Breuer@Math.RWTH-Aachen.DE 3 73 Philip Osterlund osterlu@s5.math.umn.edu 2 110 Derek Holt dfh@maths.warwick.ac.uk 2 75 Robert Beals beals@sisters.cs.uoregon.edu 2 54 Michael Cherkassoff mikec@math.ubc.ca 2 46 Gap Students studgap@twi.tudelft.nl 2 44 John R. Neil neil@dehn.mth.pdx.edu 1 88 Larsonstolafedu larson@stolaf.edu 1 67 Steve Fisk fisk@polar.bowdoin.edu 1 63 Paul Igodt paul.igodt@kulak.ac.be 1 59 Meinolf Geck Meinolf.Geck@Math.RWTH-Aachen.DE 1 58 M Taoufik Karkar karkar@tnearn.bitnet 1 50 Goetz Pfeiffer Goetz.Pfeiffer@Math.RWTH-Aachen.DE 1 41 Imre Simon is@ime.usp.br 1 36 A E Caranti caranti@volterra.science.unitn.it 1 34 D. Paul Benjamin dpb@a.cs.okstate.edu 1 30 Mark Short short@jordan.murdoch.edu.au 1 17 Thomas D Bending t.d.bending@qmw.ac.uk 1 16 Jie Wang wang@maths.uwa.edu.au 1 9 Michael J. Falk mjf@odin.math.nau.edu 1 7 Catherine Greenhill greenhil@maths.ox.ac.uk 1 6 Said Najati Sidki sidki@alpha.mat.unb.br 1 4 This file is in Berkeley mail drop format, which means you can read this file with 'mail -f ' or 'mailx -f '. It is also possible however to read this file with any text editor. From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 6 10:36:00 1994 From: "Joachim Neubueser" Date: Thu, 06 Jan 94 10:36 +0100 Subject: New attempt Dear forum members, Let me first apologise that without prior warning the forum has not been working properly for a few weeks. In the course of some reconfiguration of our computers and service software the mailer for the forum has been replaced in order to get better protection against unwanted bouncing of mail etc. . However it has taken more time than anticipated to get over some difficulties with the new mailer. As a result of this some incoming mail for the forum has waited some time until it is sent round now and also a letter of mine has reached some of you more than once and in truncated form. I append this letter again and hope that it will now reach all in full. We hope that now the forum is back to order. We think that no mail to the forum has got lost in this process, but if this should be the case with some letter of yours would you please be so kind to send it in again now. Let me also answer in public and again with apologies some questions and (quite justified) complaints that have been sent a few times to gap-trouble: There has been no send-out of patches for GAP 3.3 so far, the first one will come only after the end of this month. It always takes some time until a new GAP version or a patch is available from all servers listed in the GAP-Announcement. This is not completely under our control but needs the help of the local adminstrators of these servers. We apologize for inconvenience caused by trying without success to obtain announced releases from some servers, on which it became available only later. Please try to obtain the software in such cases from the Aachen server. For some of the ports to other computers we rely on the generous help of colleagues since we do not have these computers easily available to us here. This is in particular so with the port to MAC's. Please understand that these therefore will as a rule become available only with a certain delay, since the port has to be done by these third parties after the release of the new version and they may well be occupied with more urgent own work just at that moment. Wishing you a good 1994 and in spite of all listed above some further fun with GAP Joachim Neubueser Here then once more and hopefully finally my letter ====================================================================== In his letter to the GAP-forum of Dec. 13, Jeffrey Hsu asked: > I'm interested in teaching abstract algebra with GAP. Are there any > course material available for this purpose. I read in manual.dvi > that there were several in preperation. What's the status of these > efforts and has students found them helpful as supplementary > exercises? The short passage in the preface of the manual, which Jeffrey Hsu is quoting, refers to a discussion in the GAP-forum in 1992, when Michael K. Johnson and Donald L. Kreher reported about plans to develop course material for the use of GAP for teaching abstract algebra. I have also given a description of the situation in Aachen in the GAP-forum at that time. For convenience I append the three letters to this one. (Please note at this occasion that all non-trivial correspondance in the GAP-forum is available in the GAP-distribution in the 'etc' subdirectory.) In the meantime we have held the workshop on Computational Group Theory during the Groups '93 conference in Galway this August and this included 'practical exercises' using GAP, for which we had prepared a set of problems and solutions. We intend to supplement this by further problems, organise these problems and solutions in a standard form and make the whole file available through ftp together with GAP eventually; at present, if somebody wants to have it, we can send this collection in its not completely well-organised form without warranty. I would very much welcome if Michael K. Johnson and Donald L. Kreher as well as others who might have used GAP in teaching could tell us in the GAP-forum about their experience and in fact, if such exists meanwhile, could make course material available. Kind regards Joachim Neubueser ================================================================== Michel K. Johnson's letter: Date: Sat, 31 Oct 92 00:37:32 +01 From: johnsonm@stolaf.edu (Michael K Johnson) Subject: Teaching Abstract Algebra with GAP A few of us at St. Olaf are writing a Laboratory Manual for GAP which is intended to complement (although it does not /require/) Joseph Gallian's text Contemporary_Abstract_Algebra. We would like to know if anyone else is using GAP to teach undergraduate abstract algebra, and if so, what pedagogical materials you use or have developed. If anyone is using GAP in this way, please contact me. michaelkjohnson ===================================================================== Donald L. Kreher's letter: Date: Mon, 2 Nov 92 13:35:49 +0100 From: kreher@math.mtu.edu (Donald L. Kreher) Subject: Re: Teaching Abstract Algebra with GAP > A few of us at St. Olaf are writing a Laboratory Manual for GAP which > is intended to complement (although it does not /require/) Joseph > Gallian's text Contemporary_Abstract_Algebra. We would like to know > if anyone else is using GAP to teach undergraduate abstract algebra, > and if so, what pedagogical materials you use or have developed. > If anyone is using GAP in this way, please contact me. > michaelkjohnson I was hoping to do rougghly the same, but with Rotman's Group Theory Text. I would be very interested in seeing your Lab Manual. Also in particular I would be interested in any other recomendations from persons using GAP in Graduate Group Theory, Algebra or Discrete Mathematics Courses. Don Kreher Kreher@math.mtu.edu ======================================================================== My letter: Subject: Use of GAP in teaching Date: Mon, 2 Nov 92 17:05:28 MET Michael K. Johnson and Don Kreher report that they are working on the development of course material using GAP and ask where else work of this kind is done. It will be no surprise that we do use GAP in teaching in Aachen, although we have not written a laboratory manual or systematic course material. In order to explain the situation it should perhaps first be explained that the contents of courses is less fixed in German universities than it usually seems to be in the US, that is, each of us rather goes his own way in teaching a course on group theory, say, and may also change his course from one year to another. With this reservation made, one can say that we have perhaps two main lines in integrating algorithmic methods and the use of a system such as GAP into such a course. In one line, which I have followed two years ago, I gave a course that was entitled "Groups, theory and algorithms" parts I and II over a full year, in which algorithmic aspects and methods were closely knit into the theory, e.g. the course - that assumed a course on Algebra I which gave the basics up to Jordan-Hoelder and Sylow - started with free groups and presentations and alongside with the theory introduced computational methods such as Todd-Coxeter, Reidemeister-Schreier, Low-index and IMD. These then were treated through easy hand-calculations as well as examples using programs in the exercises ( at that time we had partially to resort to SPAS because the algorithms were not all in GAP yet, but they will be in GAP 3.2 to be released soon ). In a similar way then permutation groups, soluble groups and p-groups were treated. This course was followed by a further year on representation theory, of which I gave the first semester on ordinary representation theory, again interlacing theory with computational methods mainly for charactertheory, again using GAP, which provides quite a lot of possibilities in this field. For these courses we have files with the weekly exercises given to the students and some percentage of these involve the use of GAP. If somebody is interested to get these ( in German and not specially organized for export ) we will be happy to send them. In another setup, which we follow this year, my colleague, Prof. Pahlings will give a more traditional one-semester course on group theory, in which again GAP may be used occasionally, but more as a black box, while most of the algorithmic aspects will be treated in a separate course by me next summer, in which GAP will naturally play a more central role. Prof Pahlings meanwhile will already go on to representation theory next summer. We have followed that line also some years ago, both seem to have advantages and drawbacks and I really cannot say that I recommend one of them as the better setup. Generally we tend to allow or even recommend the use of GAP also in other courses such as the introductory algebra course. We hope that for students, who nowadays tend to come being pretty well used to PASCAL or the like, using GAP is not so difficult, so in these courses usually we have made no attempt with a systematic introduction to GAP but rather have "let things happen" and this is perhaps even so with the above-mentioned courses. But I am sure we could do better than that and hence I would be very interested to get whatever course material is developed. I would also very much welcome if such material - perhaps after some test with students - could be made generally available alongside with GAP. Joachim Neubueser From larson@stolaf.edu Thu Jan 6 16:54:00 1994 From: "Larsonstolafedu" Date: Thu, 06 Jan 94 16:54 -0600 Subject: Computing in Beginning Undergraduate Algebra We have been experimenting with using computer software in almost all of our undergraduate mathematics courses. In particular, I have focused on using GAP in our beginning course in abstract algebra. As a preface to explaining what we have settled on, let me begin by describing our beginning our algebra course. All mathematics majors are required to take one term of abstract algebra. One reason for this is that it is one of only two courses in which primary emphasis is placed on developing "mathematical maturity." That is to say, we have regarded our beginning undergraduate algebra course as a theoretical course where students are expected to learn to write proofs precisely and accurately, to think and reason logically, and to gain an appreciation for generalization and abstraction. The course introduces groups, rings, and fields, with lots of examples, and covers the standard theorems (e.g., Lagrange's Theorem, Fundamental Homomorphism Theorem for groups and rings, Fundamental Theorem of Field Theory). The content is a slightly abridged version of the first 25 chapters of Joseph A. Gallian's ``Contemporary Abstract Algebra'', Third Edition, 1994, D. C. Heath and Company, Lexingon, Massachusetts. Such a full agenda leaves little time for extended computer projects. Nevertheless, with careful planning we have supplemented this theoretical approach with four computer projects, using GAP (for groups) and MAPLE (for rings and fields). About one class period is devoted to each project. These examples show the value of the computer in pedagogy, understanding, research, and application. In the first project the computer is used to solve various sliding block puzzles. Specifically, students specify sets of generators and the computer calculates their subgroups. Students might wonder how the computer is able to do this, and it could lead, although not in this course, to further study of generators and relations, and the Todd-Coxeter algorithm. The second project helps students understand the Fundamental Theorem of Finite Abelian Groups. Specifically, for arbitrary $n$, students use the computer to help them identify the group of units modulo $n$ as a direct sum of cyclic groups of prime power order, and to construct its cycle graph. In the third project, students ask questions such as ``What proportion of the elements of a group have property $P$?'' The computer grinds out data and calculates the proportion for any desired group. This, in turn, leads to conjectures and possible proofs. The fourth project uses the computer to calculate ``encoding'' polynomials for multiple error correcting BCH codes. The computer is also used to detect and correct errors in received messages. Among other things, this project reinforces the importance of finite field algebra. These projects show students the scope and power of computer software, and hopefully motivates them to want to continue their studies in mathematics and algebra in particular. I am currently preparing versions of these projects for distribution by e-mail (in plain TEX). If interested in getting a copy by e-mail, my address is larson@stolaf.edu From jcbhrb@cerf.net Thu Jan 6 15:27:00 1994 From: "Jacob Hirbawi" Date: Thu, 06 Jan 94 15:27 -0800 Subject: expressions involving roots of unity Suppose I have an expression involving roots of unity, such as : x := [ 0, 1, -3/5*E(20)+3/5*E(20)^9+1/5*E(20)^13-1/5*E(20)^17, 0 ]; is it possible to substitute every instance of E(n) in x with some other function f(n) and have the new expression automatically evaluated? Thanks. Jacob Hirbawi Jcbhrb@CERF.net From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 7 09:29:00 1994 From: "Frank Celler" Date: Fri, 07 Jan 94 09:29 +0100 Subject: RE: AddSet etc. Dear Dima Pasechnik, you wrote in your letter Some time ago we noticed that the function Orbit(G,S,OnSets) can be hopelessly slow when |S| and in particular the length of the resulting orbit are big enough. yes, that is true, however we found that the largest amount of CPU time is consumed by AddSet. One may see looking at the appropriate C code that the time taken by AddSet to add a new element to the set of length N is proportional to N. if you will take a closer look (actually you will find a comment "perform the binary search"), you will see that 'AddSet' uses a binary search, *but* it has to ensure that the list is indeed a set. To the inexperienced user a simple solution to the problem is It is not quite clear why faster ways to handle sets, such that the addition of a new element takes only O(log(N)) operations, are not used in the GAP implementation. but this naive approach has a drawback, namely that sets in this proposal could only contain unchangeable data structures like integers or permutations but not changeable like lists or records without introducing some amount of overhead for *all* list/record assignments. To illustrate the point, consider the following examples: gap> l := [ 1, 2, 5, 6 ];; gap> TYPE(l); "list" gap> AddSet( l, 3 ); gap> l; [ 1, 2, 3, 5, 6 ] gap> TYPE(l); "set" gap> AddSet( l, 0 ); gap> l; [ 0, 1, 2, 3, 5, 6 ] the first call to 'AddSet' checks that is indeed a set and then uses a binary search to add the '0'. The function 'IsSet' (which is used in 'AddSet') attaches a "flag" to , which shows that is indeed a set. The second call to 'AddSet' will not check again. So, when dealing with lists containing integers, permutations, etc 'AddSet' will always (with the exception of the first call) use a binary search. So what *is* the problem: gap> l := [ [1,2], [2,3] ]; [ [ 1, 2 ], [ 2, 3 ] ] gap> TYPE(l); "list" gap> a := [1,3]; gap> AddSet( l, a ); gap> l; [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] gap> TYPE(l); "list" gap> IsSet(l); true Why hasn't GAP attached is magic flag to ? Well, if GAP would have marked the list as set, then each assignment into a list must check if this particular list is *contained* in a set, in our example : gap> a[1] := 2; gap> IsSet(l); false The assignment to has changed the set-feature of ! There are several solutions to the problem, each has its advantages *and* disadvantages: (a) Create unchangeable counterparts to lists and records, once created they cannot be changed anymore or (b) Create sets which only allow to test membership. (a) and (b) both have the drawback (which showed heavily in GAP 2.4), that you have to convert between different representations, creating an immense amount of garbage. (c) While making an assignment check if this particular list is an element of a set. This would introduce overhead for *all* list operations. (d) the Magma solution, which seems to be a mix of (a) and (b). (e) Use knowledge about the algorithm *inside* your algorithm, not inside the kernel of GAP. In my opinion one should use (e). For instance, an orbit algorithm can (hopefully) *guarantee* that it will not destroy the property that the list of points computed so far is already sorted. So it should look like: OrbitTest := function ( G, d, opr ) local orb, # orbit, result set, # orbit as set for faster membership test gen, # generator of the group pnt, # point in the orbit img; # image of the point under the generator orb := [ d ]; set := [ d ]; for pnt in orb do for gen in G.generators do img := opr( pnt, gen ); if not img in set then Add( orb, img ); AddSetNC( set, img ); # <-- instead of 'AddSet' fi; od; od; # return the orbit return orb; end; where 'AddSetNC' would be a function, that does no checks at all and assumes that the list is already sorted. One could easily write such a function and careful analysis will show that there is still room for improvments, one should use 'PositionSorted' in order to get ride of the 'in' avoiding doing a binary (or worse a linear) search twice (once in 'in' and once in 'AddSetNC'), but our experiments never ran into problems with the current orbit algorithm and because of the lack of time and manpower we didn't check what the fastest possible algorithm would be for all possible problems/experiments. You are more than welcome to send a list of functions in which you think such improvements are worthwhile. best wishes Frank From Alexander.Hulpke@Math.RWTH-Aachen.DE Fri Jan 7 10:36:00 1994 From: "Alexander Hulpke" Date: Fri, 07 Jan 94 10:36 +0100 Subject: Re: expressions involving roots of unity Dear Forum. In his message, Jakob Hirbawi asked: > Suppose I have an expression involving roots of unity, such as : > > x := [ 0, 1, -3/5*E(20)+3/5*E(20)^9+1/5*E(20)^13-1/5*E(20)^17, 0 ]; > > is it possible to substitute every instance of E(n) in x with some other > function f(n) and have the new expression automatically evaluated? Thanks. The following function should do the work: # replace all instances of E(n) in by (n). TransformedCyclotomics:=function(list,func) local n,i,l; l:=[]; for i in list do if IsRat(i) then Add(l,i); else n:=NofCyc(i); # the cyclotomic field used Add(l,ValuePol(CoeffsCyc(i,n),func(n))); # replace E(n) by func(n) fi; od; return l; end; This function really ''replaces'' each 'E' by . I don't know, which use you have in mind, but probably (if your f is somehow ''compatible'' with the Galois group) you might want to do all calculations in the same cycloctomic field, containing all cyclotomics in the list. If you want this function to simulate Galois mappings, you should also look up GaloisCyc in the manual, which is designed to apply Galois maps. Hope that helps, Alexander -- Alexander Hulpke, Lehrstuhl D f"ur |Ce po`eme est, en effet, divis'e en Mathematik, RWTH Aachen |cinq strophes successivement et respec- |tivement compos'ees de 3-1-4-1-5 vers, ahulpke@math.rwth-aachen.de | Jacques Bens: Le sonnet irrationnel From sl25@cus.cam.ac.uk Fri Jan 7 09:58:00 1994 From: "Steve Linton" Date: Fri, 07 Jan 94 09:58 +0000 Subject: Re: AddSet etc. > > if you will take a closer look (actually you will find a comment > "perform the binary search"), you will see that 'AddSet' uses a binary > search, *but* it has to ensure that the list is indeed a set. To the > inexperienced user a simple solution to the problem is > > It is not quite clear why faster ways to handle sets, such that the > addition of a new element takes only O(log(N)) operations, are not used > in the GAP implementation. > > but this naive approach has a drawback, namely that sets in this > proposal could only contain unchangeable data structures like integers > or permutations but not changeable like lists or records without > introducing some amount of overhead for *all* list/record assignments. > To illustrate the point, consider the following examples: There is another problem, which I outlined to Martin a while ago. Once it has decided where in the set the new entry is to be added, AddSet then has to do O(N) work to make room for it by moving half the set. The constant is pretty low, but it's still O(N). My solution to this is to use blists rather than sets whenever possible, and I have functions FastOrbit and FastOrbits which do this, and differ from Orbit only in that they require the domain to be given in full. Ideally functions like the Random Schreier-Sims should use these techniques also. Steve From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 7 13:04:00 1994 From: "Frank Celler" Date: Fri, 07 Jan 94 13:04 +0100 Subject: Re: AddSet etc. Dear Steve, There is another problem, which I outlined to Martin a while ago. Once it has decided where in the set the new entry is to be added, AddSet then has to do O(N) work to make room for it by moving half the set. The constant is pretty low, but it's still O(N). yes, that is true. And again for the same reasons there is no easy way to get rid of the problem, once you decided that sets should (regarding access and assignment) behave like lists. My solution to this is to use blists rather than sets whenever possible, and I have functions FastOrbit and FastOrbits which do this, and differ from Orbit only in that they require the domain to be given in full. Ideally functions like the Random Schreier-Sims should use these techniques also. yes, that is a very good idea if your domain is small enough. One could also try to write GAP functions for BTrees or other more advances techniques. I would love to hear if anybody has already done experiments into this direction. This raises another point, maybe we should set up a directory where we can collect small functions which are not large enough to qualify as a share library but useful enough to be of interest for other people? For instances, I think, your 'FastOrbit(s)' would be such a function. best wishes Frank From dima@maths.uwa.edu.au Fri Jan 7 20:44:00 1994 From: "Dima Pasechnik" Date: Fri, 07 Jan 94 20:44 +1000 Subject: RE: AddSet etc. Dear Frank Cellar, > Some time ago we noticed that the function Orbit(G,S,OnSets) can > be hopelessly slow when |S| and in particular the length of the > resulting orbit are big enough. > > yes, that is true, however > > we found that the largest amount of CPU time is consumed by > AddSet. One may see looking at the appropriate C code that the > time taken by AddSet to add a new element to the set of length N > is proportional to N. > > if you will take a closer look (actually you will find a comment > "perform the binary search"), you will see that 'AddSet' uses a binary > search, *but* it has to ensure that the list is indeed a set. To the Sorry, the whole point is about the *addition* of elements rather than *search*. Indeed AddSet is pretty fast if it does not need to add the particular element. Again, the trouble in this case is with the handling of the set as a whole rather than with the handling of its elements. Here follows an extract from the file set.c, function AddSet. (My own comments are marked by ***). /* perform the binary search to find the position */ len = LEN_PLIST( hdSet ); *** it is the length of the set. i = 0; k = len+1; while ( i+1 < k ) { /* set[i] < elm && elm <= set[k] */ j = (i + k) / 2; /* i < j < k */ if ( LT( ELM_PLIST(hdSet,j), hdObj ) == HdTrue ) i = j; else k = j; } /* add the element to the set if it is not already there */ if ( len < k || EQ( ELM_PLIST(hdSet,k), hdObj ) != HdTrue ) { if ( SIZE(hdSet) < SIZE_PLEN_PLIST( len+1 ) ) Resize( hdSet, SIZE_PLEN_PLIST( len + len/8 + 4 ) ); SET_LEN_PLIST( hdSet, len+1 ); for ( i = len+1; k < i; i-- ) *** the troube is here *** this loop can be executed O(len) times SET_ELM_PLIST( hdSet, i, ELM_PLIST(hdSet,i-1) ); *** moving len-th elt to the position len+1, *** (len-1)th elt to the position len, etc *** to make room for the new elt. SET_ELM_PLIST( hdSet, k, hdObj ); *** add new elt. } > inexperienced user a simple solution to the problem is > > It is not quite clear why faster ways to handle sets, such that the > addition of a new element takes only O(log(N)) operations, are not used > in the GAP implementation. > > but this naive approach has a drawback, namely that sets in this > proposal could only contain unchangeable data structures like integers > or permutations but not changeable like lists or records without > introducing some amount of overhead for *all* list/record assignments. > To illustrate the point, consider the following examples: [...] The example is rather strange, since it's more or less clear that any set can be treated as a list with an ordering attached. The example in question seems to violate this, i.e. make some elements of the set incomparable. I doubt that in any serious computation one would make things like that: a:=5; l:=Set([a,2,3]); a:=(1,2); > The assignment to has changed the set-feature of ! There are > several solutions to the problem, each has its advantages *and* > disadvantages: > > (a) Create unchangeable counterparts to lists and records, once created > they cannot be changed anymore or > > (b) Create sets which only allow to test membership. > > (a) and (b) both have the drawback (which showed heavily in GAP 2.4), > that you have to convert between different representations, creating > an immense amount of garbage. > > (c) While making an assignment check if this particular list is an element > of a set. This would introduce overhead for *all* list operations. But the example I deleted shows that this this the option already chosen in GAP, isn't it? > > (d) the Magma solution, which seems to be a mix of (a) and (b). > > (e) Use knowledge about the algorithm *inside* your algorithm, not inside > the kernel of GAP. It's not quite clear why the following option is not OK. Certainly (c) is bad. But what about making the user responsible for the upgrading of sets, if necessary. Say, after a:=1; l:=Set([a,2,3]); a:=10; call a function (say) Upgrade(l). One could suggest even better ways, by taking some extra care *before* changing a. > In my opinion one should use (e). For instance, an orbit algorithm > can (hopefully) *guarantee* that it will not destroy the property that > the list of points computed so far is already sorted. So it should > look like: > od; > od; > > # return the orbit > return orb; > end; > > where 'AddSetNC' would be a function, that does no checks at all and > assumes that the list is already sorted. One could easily write such > a function and careful analysis will show that there is still room for To be efficient, this function must involve the machinery for efficient addition of elements in the set, e.g. AVL-trees etc. It's not so *easy*. Best regards, Dima Pasechnik, Dept. of Mathematics, Univ. of Western Australia, Nedlands WA 6009, Australia e-mail:dima@maths.uwa.edu.au From Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Jan 10 10:10:00 1994 From: "Joachim Neubueser" Date: Mon, 10 Jan 94 10:10 +0100 Subject: AddSet again Forwarded message: >From math.rwth-aachen.de!fceller Mon Jan 10 09:04:51 1994 Message-Id: Date: Mon, 10 Jan 94 09:00 +0100 From: Frank.Celler@math.rwth-aachen.de To: J.Neubueser@math.rwth-aachen.de In-reply-to: Dima Pasechnik's message of 7 Jan 94 20:44 WST Subject: Meine Antwort Content-Type: text Dear Dima Pasechnik, To be efficient, this function must involve the machinery for efficient addition of elements in the set, e.g. AVL-trees etc. yes, I completely agree with you on that point, unfortunately, as I tried to explain, this is of little help with your orignal question: Some time ago we noticed that the function Orbit(G,S,OnSets) can be hopelessly slow when |S| and in particular the length of the resulting orbit are big enough. if is a big set the comparison between sets will be relative expensive, together with the fact that 'AddSet' has to check all elements this is taking the time. A short example: Take a set of 4000 vectors of length 450 and sort them in reversed order. Now start with the first vector and build up a new set using 'AddSet'. The insertion process during the addition of elements is as bad as can be. On a NeXT this process will indeed be incredibly slow taking nearly an hour to complete. However, if your remove the test in 'AddSet' that the first argument is really a set, it will take 20sec, 10 of those - I would guess - being used in the insertion process. Using Trees, hashing or whatever will reduce this 10sec to maybe less than 1sec. So you have a gain of 10sec in an 1 hour procedure. If on the other hand you simply drop the test, you will speed up the whole thing by a factor of 200. Once you have decided that sets are sorted lists without holes (I explained why we didn't choose the other options, in this situation things would have been different), your suggestion call a function (say) Upgrade(l). One could suggest even better ways, by taking some extra care *before* changing .... will create dangerous traps. If one is purely thinking in the context of orbits, I agree that The example is rather strange, since it's more or less clear that any set can be treated as a list with an ordering attached. The example in question seems to violate this, i.e. make some elements of the set incomparable. I doubt that in any serious computation one would make things like that: But unfortunately that point of view can only be taken in standalone programs but not in a system like GAP. The example I gave you is not a wild construct, it is a simplification of a real bug. When changing from GAP 2.4 to 3.0 we experimented for a while with that. And because of the tempting example above we tried if we can do without the test in 'AddSet'. But this created a bug in one of the representation theory programs, where sets were used in a completely different seting (and sets there are very small). It took the programmer a long time to find this really nasty bug. That was the reason why we decided against a faster but insecure 'AddSet' and are now using a slow but stable one. On the other hand, and that was the point (e) I tried to explain, this does not mean that one has to live with an (in some cases slow) implementation of 'Orbit' (even now, where in most cases the operation is costly, it is not too bad). But the example above shows that with very little work involved one can easily speed up things, in that example it does not even seem necessary to use trees or other techniques. But in a situtation as Steve has described, which is in some sense the other extreme because comparison and operation is very cheap, 4-3-trees, red/black-trees, avl-trees, hashing, or bit-lists could and should be used. But doing this in 'AddSet' will not help in your sitution. So one has to do it in 'Orbit' (in which it will work for both your and Steve's situation). This does not mean that one has to do it in such a way that it can only be used in 'Orbit'. For instance, if one would write a small package implementing functions to create a tree structure, to add a new element, to test membership, and to test and add, this could easily be used in various places. Presumably all of this can be done with the existing datastructures lists and records. But as I said, at the moment none of us here in Aachen has the time to do it, so experiments/comments (like Steve's 'FastOrbit') from elsewhere are more than welcome. Wouldn't you like to write such a package that would perform optimally for applications like yours? We would surely appreaciate that. best wishes Frank Celler and Joachim Neubueser ^ ^ From Joachim.Neubueser@Math.RWTH-Aachen.DE Wed Jan 12 20:13:00 1994 From: "Joachim Neubueser" Date: Wed, 12 Jan 94 20:13 +0100 Subject: re GAP for undergraduates In his letter to the forum of Dec. 31, Bill Haloupek asked for suggestions with respect to the use of GAP in teaching undergraduates and raised some questions that I think are important. I am grateful for the report about the use of GAP at St. Olaf that was sent to the GAP-forum a few days later providing some such suggestions. I have already talked about our (rather less systematic) use of GAP in teaching; today, rather belatedly, I would like to comment in a more general way on a couple of points in Bill Haloupeks letter: >I think the GAP manual is pretty intimidating to undergraduates. Yes, I completely agree that it must be intimidating to the vast majority of the students. We intend (but do not ask when) to split the manual into three parts, the first an extended version of the first chapter 'About GAP', the second the reference part to the functions in the main body of GAP and the third about the share libraries. This will hopefully make use easier but still would only marginally reduce the intimidation of undergraduates. For these indeed an easy introduction to the easy parts of GAP should be written, leaving out character tables and similar 'horrors'. However I had to say above that I can't promise a date when we will have been able to split the manual, I can say rather safely that we simply will not have the time in any foreseeable future for writing such an undergraduate introduction, which after all should be based on some experiments with students, and should introduce concepts together with their exploration using GAP. Being a small department with rather high teaching duties, we will be glad if we reasonably manage the maintenance and improvement of GAP. I would therefore highly welcome if somebody undertook that task, which indeed I think would be most worthwhile. >There is a much more user-friendly and simple program...It does > calculations in S4 mainly. I do not know this program and certainly would not at all want to question its helpfulness. However I would like to make some points both from my own experience as a student and from my experience with my students. I do not believe that one should introduce programs that replace hand calculations too early. I think in a group of the size of S4 everything can still rather well be done by hand and indeed writing down by hand all cosets of the Klein-Four-Group on one hand and a Three-cycle on the other and trying to form a group from either set is a useful experience. Even though we have GAP and tell students early how to use it, we do require some such hand calculations. When I was a student and my teacher Wolfgang Gaschuetz proved all those wonderful theorems about existence of complements while I just knew S3, S4, and D8, I sat down and worked out all groups up to order 30 and their subgroup lattices just to see what he was talking about. I am not recommending that every undergraduate should do that, but a little of that kind, yes, I certainly learned a lot about group theory doing that. However, when I had done that, one equally important benefit for me was that I started to believe that all these difficult concepts and wonderful theorems were about *something at all* and that it might be fun to know more about these so simply defined and yet so complex structures, called groups. I think it is this point even more than the help with the understanding of the meaning of basic concepts were GAP (and other systems) can help. Another help that systems can give is to show rather different situations in which a theorem applies and also situations which are similar but not quite and where the theorem does not hold any more, i.e.systems can help to understand (the scope of) a theorem through an understanding of its limitations. E.g. in a finite abelian group A there is a subgroup of each order dividing the order of A. In A4 there isn't! Oh! So Sylow's theorem is something after all! That you will probably still do by hand but for bigger ones use GAP. Coming back to my collection of drawings of subgroup lattices, you may have noticed that GAP 3.3 comes with a (still very rudimentary) X-GAP which works under X-windows and allows to obtain such drawings on the screen. This will be extended also to incorporate features that have been developed in Derek Holt's and Sarah Rees' beautiful system QUOTPIC for the investigation of a finitely presented group drawing parts of its normal subgroup lattice, i.e. depicting certain factorgroups. I think such visualisations will lend themselves rather well to teaching even undergraduates, giving them a "picture" of the group. >A manual should include a section telling us mathematicians how to >evaluate computer homework. Well, maybe it is, since I (still) hope to be a mathematician, too, that I do not know what to write into such a section! But seriously: What we do is the following: In an Algebra course (at present I give a course Algebra I, the usual 'Groups, Rings, Fields' up to Galois Theory for first term, second year students), most of the exercises are to be done by hand. Some with computations are "either by hand or by GAP" and what counts is if the result has been achieved. If GAP is used, a print of what has been done should be provided in much the same way as the hand computations should be shown. In addition there are a few problems which really can only be done with GAP and in most cases these are "extra credit" as in your class. That is, the ability to use GAP very efficiently is *not* the criterion for passing the course. Rather the students should gradually learn to appreciate that indeed GAP may help them dealing with more complicated concrete problems. (In fact in the written test at the end of the course which mainly decides about passing it there is no GAP at all!) In a general group theory course there will be a little more "pressure" in the direction of using GAP. The kind of philosophy is: Well, a prerequisite of saying that you mastered the course is not only that you learned some facts and understood some concepts but definitely also that you learned some techniques to prove certain statements, another (complementing, not at all replacing it) is that you learnt some techniques to work in concrete groups - by hand and argument as well as using algorithmic methods in a system. Finally, in a course on Computational Group Theory naturally the second aspect dominates. However in neither of the different courses have I ever felt a need for a special evaluation method. None of the courses is about techniques for writing programs, none of them is a computer science course. Neither is any of them a course for living in a group theoretical fool's paradise in which black boxes spit out charatertables. Also in the CGT course the understanding of the group theory that lends itself to developing an algorithm is the aim, hence it is all the time the ability to do something using the understanding of it that should be tested. As I have said in another letter, we intend (again do not ask dates) to provide at least a set of worked out examples of the use of GAP that may be used in class, some coming from our courses in Aachen, some from the CGT workshop at Galway, but also, with his kind permission, including those that Peter Webb offered. Maybe others could do the same? Joachim Neubueser From dima@maths.uwa.edu.au Thu Jan 13 22:34:00 1994 From: "Dima Pasechnik" Date: Thu, 13 Jan 94 22:34 +1000 Subject: Re: AddSet again Dear Forum, > Some time ago we noticed that the function Orbit(G,S,OnSets) can be > hopelessly slow when |S| and in particular the length of the resulting > orbit are big enough. > > if is a big set the comparison between sets will be relative > expensive, together with the fact that 'AddSet' has to check all > elements this is taking the time. A short example: Take a set of 4000 > vectors of length 450 and sort them in reversed order. Now start with > the first vector and build up a new set using 'AddSet'. The insertion > process during the addition of elements is as bad as can be. On a > NeXT this process will indeed be incredibly slow taking nearly an hour > to complete. However, if your remove the test in 'AddSet' that the > first argument is really a set, it will take 20sec, 10 of those - I > would guess - being used in the insertion process. Using Trees, > hashing or whatever will reduce this 10sec to maybe less than 1sec. > So you have a gain of 10sec in an 1 hour procedure. If on the other > hand you simply drop the test, you will speed up the whole thing by a > factor of 200. Yes, I see now that the main problem is that AddSet calls IsSet rather than it spends lots of time for actual rewriting of the set. However, looking at IsSet, one sees that first of all it tests whether it is already known that the argument is a set by checking certain flag in its record. In the best of my knowledge, it is really fast providing this flag is set to `yes`. Note that the sets in question are generated as the images of the original set S. The image of S is a set, so the corresponding function which computes the image of a set under a permutation (see the module permutat.c) should set , I believe, the abovementioned flag to `yes`. (In other words there might be a bug) Otherwise I fail to understand why the removal of the call to IsSet can improve performance of Orbit(,,OnSets) so dramatically. Best regards, Dima Pasechnik From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994 From: "Joachim Neubueser" Date: Thu, 13 Jan 94 16:37 +0100 Subject: More GAP for undergraduates Rereading what I have written yesterday in answer to Bill Haloupek's letter, I realize that I have perhaps not taken enough notice of his last and most direct question: >There is a saying, "you can lead a student to a computer, but you can't make him think." Can we? At the undergraduate level? And with non-math majors? Well, here is a suggestion that one might try, though I must admit that I haven't. Give them the task to compute all subgroups of a permutation group that is given by a set of generators (i.e. to compute the subgroup lattice, but that concept need not be mentioned at that level). That is very concrete and does so far only need the notion of a group, a subgroup, and of a generating set. Prove to them the criterion that a subset of a group is a subgroup iff with any two elements a and b it contains a*b^-1 and let them write a program just using that. This will be hopelessly inefficient ( of course - but it is what once upon a time a very renowned group theorist suggested to me as much simpler than what I had done!) Next prove to them Lagrange's theorem. So we need not check all subsets! Progress! Unfortunately still very inefficient. Remind of the concept of generating sets and apply it to finding subgroups. We will need a fast way to generate a subgroup. Invent Dimino's algorithm (this brings you close to the idea of an orbit, maybe this is a nice point for a little deviation about that concept). Next: How to store a subgroup. List of all elements? Long! Moreover membership test if used more often is a problem. Invent the idea of storing by a characteristic function, that is by a bitstring! On the set of all elements of the whole group? Possible! Better: On the set of cyclic subgroups of prime power order. By now you will have needed some idea of how a cyclic subgroup works. However by now you have already arrived at the data structure that is actually used in GAP (and Cayley). Then return to the idea of using generating sets. Maybe using lexicographical order? Not so bad, has been a serious and published proposal in the early sixties, write some programs. Trouble is that so many subgroups are found over and over again, and this is noticed only after a good chunk of them has been regenerated. Really one should know beforehand which to generate. Now you need a bit more theory: normal subgroups, normalizer, factor groups, (composition series), soluble groups, not really Jordan Hoelder, although having it does not hurt, but you may also first have the program and then use it to 'observe' the truth of JH. Having these concepts, now invent the 'cyclic extension method' for soluble groups and actually implement it, using either a brute force method for the normalizer or (maybe after that) a much more efficient black box for it that you find in GAP. Maybe you now want to ask if all finite groups are soluble, perhaps you can prove the simplicity of A5 or even An, n>4. This will now have a very concrete meaning to the students. All this can be done using the commodities of a system like GAP, i.e. not worrying about storage management, having arithmetic for integers and also for permutations and even lists and bitlists ready to use. What you reach is pretty close to the actual implementation of the subgroup lattice in GAP, which still follows in many ways the idea of my own very first program of 1959 except that it is now so much easier to write it. The philosophy of the whole proposal is to let the students *experience* that group theoretical concepts are not there to annoy them but to make concrete complex structures accessible. "Think before programming!" Perhaps even computer science majors may get the message. And at the end they can throw a pair of generators for M11 into GAP and have some idea how it works that the subgroup lattice comes out. The first chapters of Greg Butler's book "Fundamental Agorithms for Permutation Groups" contain descriptions of all the methods that occur above. However: I have used the book in a proseminar last year, i.e. I let the (first year-) students give talks on its content. That was a flop. Reporting about all the (sometimes over-) explicit countings of operations in algorithms got very boring. I do not recommend to try that. Rather use the book yourself but hide it from the students (at least until the end of the course) and let them 'invent' these ideas (of course you will have to drop a suggestion now and then and have to prove some theorems) and let them *do* the algorithms rather than speak about them. I would be most interested to hear if somebody tries something like that. Apologises to those of you who would like to see other things discussed in the forum. This will be my last on the topic for a while. Joachim Neubueser From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994 From: "Steve Linton" Date: Thu, 13 Jan 94 15:55 +0100 Subject: Re: AddSet again in > > Dear Forum, > > Some time ago we noticed that the function Orbit(G,S,OnSets) can be > > hopelessly slow when |S| and in particular the length of the resulting > > orbit are big enough. > > > > if is a big set the comparison between sets will be relative > > expensive, together with the fact that 'AddSet' has to check all > > elements this is taking the time. A short example: Take a set of 4000 > > vectors of length 450 and sort them in reversed order. Now start with > > the first vector and build up a new set using 'AddSet'. The insertion > > process during the addition of elements is as bad as can be. On a > > NeXT this process will indeed be incredibly slow taking nearly an hour > > to complete. However, if your remove the test in 'AddSet' that the > > first argument is really a set, it will take 20sec, 10 of those - I > > would guess - being used in the insertion process. Using Trees, > > hashing or whatever will reduce this 10sec to maybe less than 1sec. > > So you have a gain of 10sec in an 1 hour procedure. If on the other > > hand you simply drop the test, you will speed up the whole thing by a > > factor of 200. > > Yes, I see now that the main problem is that AddSet calls IsSet rather > than it spends lots of time for actual rewriting of the set. > However, looking at IsSet, one sees that first of all it tests > whether it is already known that the argument is a set by checking > certain flag in its record. In the best of my knowledge, > it is really fast providing this flag is set to `yes`. > > Note that the sets in question are generated as the images of the > original set S. The image of S is a set, so the corresponding > function which computes the image of a set under a permutation (see the > module permutat.c) should set , I believe, the abovementioned flag to `yes`. > (In other words there might be a bug) > > Otherwise I fail to understand why > the removal of the call to IsSet can improve performance of > Orbit(,,OnSets) so dramatically. Is this a set of numbers, or a set of (for example) vectors? It makes a difference, for the reason that Frank was talking about before, namely that a vector in the set might be altered (by assigning to one of its entries). A set of vectors can thus NOT be guaranteed to stay sorted, even if no changes are made to the set itself, only changes to the elements. Steve From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994 From: "Dima Pasechnik" Date: Fri, 14 Jan 94 08:46 +1000 Subject: Re: AddSet again > > > > Yes, I see now that the main problem is that AddSet calls IsSet rather > > than it spends lots of time for actual rewriting of the set. > > However, looking at IsSet, one sees that first of all it tests > > whether it is already known that the argument is a set by checking > > certain flag in its record. In the best of my knowledge, > > it is really fast providing this flag is set to `yes`. > > > > Note that the sets in question are generated as the images of the > > original set S. The image of S is a set, so the corresponding > > function which computes the image of a set under a permutation (see the > > module permutat.c) should set , I believe, the abovementioned flag to `yes`. > > (In other words there might be a bug) > > > > Otherwise I fail to understand why > > the removal of the call to IsSet can improve performance of > > Orbit(,,OnSets) so dramatically. > > Is this a set of numbers, or a set of (for example) vectors? > > It makes a difference, for the reason that Frank was talking about > before, namely that a vector in the set might be altered (by > assigning to one of its entries). A set of vectors can thus NOT be > guaranteed to stay sorted, even if no changes are made to the set > itself, only changes to the elements. > > Steve It seems still unclear. If g is a permutation of a set X of whatever nature, S a subset of X, then S^g is a set, otherwise one would expect a message like "Error, must be a set in ...OnSets". That is, S^g is uniquely defined. That is , S^g should be a set, so the appropriate flag of it is 'yes'. Certainly I agree that there are operations which can disrupt the order of S, say as it was pointed out by making changes to elements, but S^g should be exempt from this list. Dima -- Dima Pasechnik, Dept. of Mathematics, Univ. of Western Australia, Nedlands WA 6009, Australia e-mail:dima@maths.uwa.edu.au From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994 From: "Steve Linton" Date: Fri, 14 Jan 94 10:42 +0100 Subject: Re: AddSet again > > It seems still unclear. If g is a permutation of a set X of whatever nature, > S a subset of X, then S^g is a set, otherwise one would expect a message > like "Error, must be a set in ...OnSets". > That is, S^g is uniquely defined. That is , S^g should be a set, so > the appropriate flag of it is 'yes'. > > Certainly I agree that there are operations which can disrupt the order of > S, say as it was pointed out by making changes to elements, > but S^g should be exempt from this list. > The problem is that the 'set' object cannot know whether one of its memebrs has been altered. Accordingly, the flag can NEVER be used on a list containing changeable objects. Steve From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994 From: "Frank Celler" Date: Fri, 14 Jan 94 14:44 +0100 Subject: Re: AddSet again and again Dear Dima Pasechnik, It seems still unclear. If g is a permutation of a set X of whatever nature, S a subset of X, then S^g is a set, otherwise one would expect a message like "Error, must be a set in ...OnSets". That is, S^g is uniquely defined. That is , S^g should be a set, so the appropriate flag of it is 'yes'. sorry, now I am I bit confused. You were asking about sets in general and in particular, why 'AddSet' has some problems with sets of mutable objects and insertion. I think we now all more or less agree how to solve these kinds of problems. But 'OnSets' does not use 'AddSet', it will apply to all elements of and then sort the resulting list. Again for the same reasons that 'AddSet' cannot flag this list as set, if X contains mutable objects, 'OnSets' will not do it either. Surely, we can do without the 'IsSet' test but again we decided to play it safe in order to avoid traps for others, even if this means that GAP will be slower than possible without these tests. If however your set X contains unchangeable objects like integers, yes, one could try a bit harder to keep the information that 'OnSets' returns a set. It is not clear to what amount this will speed up things, because the test requires only ||-1 comparisons while the sort needs something like O(||*log||) and one has to check if the image of in under is again unchangeable. In the very special case of a list/set of integers and permutation one could do without tests. I will try to do this in the next version but the speedup - I guess - will not be dramatical, presumably much smaller than a factor of 2. I hope we all now understand the problems with sets, but if there are any further questions, I think we should discuss them in "gap-trouble". So if anyone wants more information about the internal structure of sets, simply send a mail to "gap-trouble@math.rwth-aachen.de" (there is no need to subscribe to it). If any new insight will come out of further discussion, we will report this to the gap-forum. best wishes Frank Celler From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994 From: "M Taoufik Karkar" Date: Fri, 14 Jan 94 21:36 N Subject: undergraduate lectures Dear Gap-Forum@RWTH-Aachen.de I had some experience of teaching group theory that I like to tell you about it. I used to give to my students to compute (even by hand when no computer was possible) concrete examples (full computations): I think that this is the right way to make them ASSIMILATE the theoretical concepts. But, of course, the task is horrible when the groups have order about (more or less) than 30 elements, while many elementary concepts cannot be illustrated by so small groups. More over, I found that the students are really exited if they have to "guess" what group they have while this group is defined by an abstract presentation. The only thing that they discourage them to continue investigations is of course a long, perhaps endless, hand calculus. That is why I made a few years ago (before finding GAP or handling any symbolic system) a "small" program for investigation "small groups" (I call it Hijara=little stones, to make people remember they learned the first things in arithmetics with little stones). These groups may be permutation groups, abstract groups, "modular groups" (=units of Z/nZ) or matrix groups with coefficients in some Z/nZ (matrices are not yet implemented). Now with such system, one can do elementary investigations in reasonable time, on groups with some hundred elements and main elementary concepts may be illustrated. For bigger groups, the program take a very long time (some hours for groups of order = some thousands ). The membership test is very expensive...and my implementation is not optimized at all. The fact that some groups to investigate are abstract make them return to the theory for solving problem of how to handle that group. For them, it is an "open question". There is no standard way to solve problems of this nature, and all theoretical tools are potentially useful for solving that problem. The solution may be given later by the professor who is assumed to know what group it is. So the philosophy is that the computer as well as the book have the same chance to make students thinking about what they are studying. We have only to find the adequate pedagogy for using computer and any other tool for communication. More over, the students need always at some moments... professors...and this is not a discovery. best regards M. Taoufik Karkar From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 21 09:02:00 1994 From: "Frank Celler" Date: Fri, 21 Jan 94 09:02 +0100 Subject: [no subject] From: michael.smith@maths.anu.edu.au Subject: Calling functions, printing records and matrix calculations To: gap-forum@math.rwth-aachen.de ----------------------------------------------------------------------------- A couple of suggestions, and a question. LISP 'apply function: Since LISP seems to have been an influence in the design of the GAP language, I wondering whether there might be a (hidden?) function equivalent to the LISP 'apply function. This function takes as arguments a function F and a list L and its evaluation is equivalent to a call to F with arguments given by the elements of L. i.e. ApplyFunction(F,[a,b,c]) is equivalent to F(a,b,c) It is useful in the following situation. Assume that I wish to break whenever the Print function is called. Now I would like to set PrintOriginal to Print and then redefine Print to be an Error() statement follwed by a call to PrintOriginal. The problem is, since Print takes a variable number of arguments, I cannot write a call to PrintOriginal that duplicates the original call to Print. It is trivial to do this with LISP's 'apply function. Nonrecursive PrintRec: Any chance of including a non-recursive PrintRec in future? When trying to find out what the fields of a record are there can be an *enormous* amount of output to wade through (try a GroupHomormorphismByImages sometime). Matrix calculations: I need to calculate a number of products of some matrices and add these products together. What is the best way of doing this? The simplest method, Sum([1..n], i -> A[i]*B[i]), uses much more space than necessary. It should be possible to do all this using only two extra matrices, one to accumulate the sum, the other to store each product. Can this be done? Thanks, Michael. ------------------------------/|-|--|-|--|----Michael-Smith------------------- smith@maths.anu.edu.au /-| |\ | | | Mathematics (CMA) ----------------------------/--|-|-\|-|_/|----Australian-National-University-- From Alexander.Hulpke@Math.RWTH-Aachen.DE Fri Jan 21 11:09:00 1994 From: "Alexander Hulpke" Date: Fri, 21 Jan 94 11:09 +0100 Subject: Re: Diverse questions Dear Forum, in his message, Michael smith asked: > Subject: Calling functions, printing records and matrix calculations > ----------------------------------------------------------------------------- > A couple of suggestions, and a question. > > LISP 'apply function: > > Since LISP seems to have been an influence in the design of the GAP > language, I wondering whether there might be a (hidden?) function > equivalent to the LISP 'apply function. This function takes as arguments > a function F and a list L and its evaluation is equivalent to a call to F > with arguments given by the elements of L. > > i.e. ApplyFunction(F,[a,b,c]) is equivalent to F(a,b,c) Supposing, that there always is an fixed upper limit to the number of arguments, one could use a hack like : ApplyFunction := function( func, list ) local l; l:=Length(list); if l=0 then func(); if l=1 then func(l[1]); elif l=2 then func(l[1],l[2]); . . . fi; end; He continues: > I need to calculate a number of products of some matrices and add these > products together. What is the best way of doing this? The simplest > method, Sum([1..n], i -> A[i]*B[i]), uses much more space than necessary. > It should be possible to do all this using only two extra matrices, one > to accumulate the sum, the other to store each product. Can this be done? When looking at the code of 'Sum', it seems, that indeed only two intermediate matrices should be needed, as basically a loop evaluates sum:=sum+func(i); Are you sure, that GAP *needs* the additional memory, or that this memory only gets allocated? (The memory manager tends to allocate more memory than actually needed.) If this is the case, starting GAP with option -m limit, where limit is a bound for the necessary memory should do the task. Alexander Hulpke From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 21 13:26:00 1994 From: "Frank Celler" Date: Fri, 21 Jan 94 13:26 +0100 Subject: [no subject] Date: Fri, 21 Jan 1994 12:06:46 +0100 From: Steve Linton Message-ID: <8104.9401211106@keith.cs.st-andrews.ac.uk> To: GAP Forum In-Reply-To: Subject: Re: [no subject] > LISP 'apply function: > > Since LISP seems to have been an influence in the design of the GAP > language, I wondering whether there might be a (hidden?) function > equivalent to the LISP 'apply function. This function takes as arguments > a function F and a list L and its evaluation is equivalent to a call to F > with arguments given by the elements of L. > > i.e. ApplyFunction(F,[a,b,c]) is equivalent to F(a,b,c) Hear, hear. I have wanted this too and it must be easy to implement. > Nonrecursive PrintRec: > > Any chance of including a non-recursive PrintRec in future? When trying > to find out what the fields of a record are there can be an *enormous* > amount of output to wade through (try a GroupHomormorphismByImages > sometime). Do you know about RecFields? > > Matrix calculations: > > I need to calculate a number of products of some matrices and add these > products together. What is the best way of doing this? The simplest > method, Sum([1..n], i -> A[i]*B[i]), uses much more space than necessary. > It should be possible to do all this using only two extra matrices, one > to accumulate the sum, the other to store each product. Can this be done? > Trivial with a loop, but Sum ought to get this right as well. ie Sum(l,f) should be more efficient than Sum(List(l,f)) Steve From fisk@polar.bowdoin.edu Tue Feb 1 13:09:00 1994 From: "Steve Fisk" Date: Tue, 01 Feb 94 13:09 -0500 Subject: a question about fp groups Dear Gap-forum, If I have a group with three generators gap> g := FreeGroup(3,"g"); and the relations gap> g.relators := [g.1*g.2*g.3]; and I simplify the presentation gap> h := SimplifiedFpGroup(g); then GAP tells me that there are two generators, and no relations. gap> h.generators; [ g.1, g.2 ] gap> h.relators; [ IdWord ] I have four questions: 1) How can I find an expression for the generator g.3 in terms of g.1 and g.2? (In practice, there might be 20 relators; this is just a simple example.) 2) How can I tell if an expression is the identity? e.g. g.1*g.2*g.3 (Well, this is the word problem, so can I control the time that GAP devotes to this question - i.e. if more than 30 seconds, then return "unknown".) 3) Similarly, can I ask for Size(g) to return "unknown" if it has to spend more than 30 seconds on it (or perhaps 10M of memory instead of time).? 4) I asked for the size of h, and got the following. Is this a bug or a feature? gap> g := FreeGroup(3,"g"); Group( g.1, g.2, g.3 ) gap> g.relators := [g.1*g.2*g.3]; [ g.1*g.2*g.3 ] gap> h := SimplifiedFpGroup(g); Group( g.1, g.2 ) gap> Size(h); Error, Subword: illegal value at while LengthWord( rel ^ Subword( rel, 1, 1 ) ) < LengthWord( rel ) ... in RelatorRepresentatives( G.relators ) called from RelsSortedByStartGen( G, table ) called from AugmentedCosetTableMtc( G, H, 1, "_x" ) called from D.operations.Size( D ) called from Size( h ) called from main loop brk> thanks, steve From greenhil@maths.ox.ac.uk Wed Feb 2 10:48:00 1994 From: "Catherine Greenhill tel 2-73564" Date: Wed, 02 Feb 94 10:48 +0000 Subject: Integer multiplication in GAP I was wondering how integer multiplication is implemented in the GAP core, and whether anything like the Schoenhage-Strassen algorithm is used in the implementation... Catherine Greenhill From neil@dehn.mth.pdx.edu Fri Feb 4 09:13:00 1994 From: "John R. Neil" Date: Fri, 04 Feb 94 09:13 -0800 Subject: Re: a question about fp groups In message <9402011809.AA09333@medved.bowdoin.edu> you write: >Dear Gap-forum, > >If I have a group with three generators > >gap> g := FreeGroup(3,"g"); > >and the relations > >gap> g.relators := [g.1*g.2*g.3]; > >and I simplify the presentation > >gap> h := SimplifiedFpGroup(g); > >then GAP tells me that there are two generators, and no relations. > >gap> h.generators; >[ g.1, g.2 ] > >gap> h.relators; >[ IdWord ] > >I have four questions: > 1) How can I find an expression for the generator > g.3 in terms of g.1 and g.2? (In practice, there might be 20 relators; > this is just a simple example.) The transformation which GAP has made in this case is the obvious one: g.1*g.2*g.3 = 1 => g.3 = (g.1*g.2)^-1 After it makes this assumption, it no longer needs either g.3 or the relator. Thus, you have taken a 3 generator group with 1 relator and turned it into the free group on 2 generators. > > 2) How can I tell if an expression is the identity? e.g. g.1*g.2*g.3 > (Well, this is the word problem, so can I control the time > that GAP devotes to this question - i.e. if more than 30 > seconds, then return "unknown".) I think you made this problem much harder than it needed to be. > > 3) Similarly, can I ask for Size(g) to return "unknown" if it has > to spend more than 30 seconds on it (or perhaps 10M of memory > instead of time).? A free group is going to be of infinite order so you would expect the error response you got in number 4 below. > > 4) I asked for the size of h, and got the following. Is this a bug > or a feature? > >gap> g := FreeGroup(3,"g"); >Group( g.1, g.2, g.3 ) > >gap> g.relators := [g.1*g.2*g.3]; >[ g.1*g.2*g.3 ] > >gap> h := SimplifiedFpGroup(g); >Group( g.1, g.2 ) > >gap> Size(h); >Error, Subword: illegal value at >while LengthWord( rel ^ Subword( rel, 1, 1 ) ) < LengthWord( rel ) ... in >RelatorRepresentatives( G.relators ) called from >RelsSortedByStartGen( G, table ) called from >AugmentedCosetTableMtc( G, H, 1, "_x" ) called from >D.operations.Size( D ) called from >Size( h ) called from >main loop >brk> > > > > thanks, steve > =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= John Neil e-mail: neil@math.mth.pdx.edu Director of Computer Labs and UNIX System Administrator Portland State University Mathematics Department =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Feb 4 22:20:00 1994 From: "Martin Schoenert" Date: Fri, 04 Feb 94 22:20 +0100 Subject: Re: Integer multiplication in GAP Catherine Greenhill writes in her e-mail message of 1994/02/02 I was wondering how integer multiplication is implemented in the GAP core, and whether anything like the Schoenhage-Strassen algorithm is used in the implementation... Sch"onhage-Stra\3en? Are you kidding? GAP only uses the scool method, and even that is not implemented very efficiently. We never do more than is necessary. Seriously. The scool method, if implemented efficiently, is quite fast. Karatsuba begins to pay of at about 100 decimal digits (on a mips R3000). FFT begins to pay of at about 1000 decimal digits. Nu\3baum's method may or may not be a bit faster than FFT in practice. Sch"onhage-Stra\3en is never the fastest method. The next version of the integer arithmetic will implement the Karatsuba method, but none of the other methods. I wonder why you wonder how ... Care to comment? 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 Feb 7 14:51:00 1994 From: "Martin Schoenert" Date: Mon, 07 Feb 94 14:51 +0100 Subject: Re: Re: Integer multiplication in GAP Eggs in my face. In my e-mail message of 1994/02/04 I compared FFT with Sch"onhage-Strassen, arguing that the former is faster. This is of course ridiculous, since FFT *is* the Sch"onhage-Strassen algorithm. I had a modular method by Sch"onhage in mind, which is indeed always slower than Sch"onhage-Strassen. Also the other method which seems to be a little bit faster in practice is due to Nussbaumer (not Nu\3baum). But the general method remains. For small numbers the ordinary scool method (of order ^2) is best. For numbers with 100 decimal digits one should use Karatsuba's trick. And only for numbers with more than 1000 decimal digits it is worth to use FFT or Nussbaumer's method. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Feb 7 16:17:00 1994 From: "Volkmar Felsch" Date: Mon, 07 Feb 94 16:17 +0100 Subject: Re: a question about fp groups Steve Fisk writes: > If I have a group with three generators > > gap> g := FreeGroup(3,"g"); > > and the relations > > gap> g.relators := [g.1*g.2*g.3]; > > and I simplify the presentation > > gap> h := SimplifiedFpGroup(g); > > then GAP tells me that there are two generators, and no relations. > > gap> h.generators; > [ g.1, g.2 ] > > gap> h.relators; > [ IdWord ] Note that since version 3.3 the appropriate way to create f.p. groups is as follows; gap> f := FreeGroup(3,"f"); gap> g := f / [f1*f2*f3]; > I have four questions: > 1) How can I find an expression for the generator > g.3 in terms of g.1 and g.2? (In practice, there might be 20 relators; > this is just a simple example.) > > 2) How can I tell if an expression is the identity? e.g. g.1*g.2*g.3 > (Well, this is the word problem, so can I control the time > that GAP devotes to this question - i.e. if more than 30 > seconds, then return "unknown".) There are no GAP functions for this purpose. In particular, the SimplifiedFpGroup function does not trace the substitutions it performs. Indeed, there is a possibility to force GAP to at least print out all substitutions made by the SimplifiedFpGroup function: If you replace your statement h := SimplifiedFpGroup(g); by p := PresentationFpGroup( g, 2 ); SimplifyPresentation( p ); h := FpGroupPresentation( p ); thus increasing the default print level value to 2, then you will get some additional output which, in particular, lists all substitutions made. However, I would like to warn you that this output enforced by print level 2 may be very voluminous. So it might be a better idea, just to comment out the relevant checks of the print level in the code of the Tietze transformation routines in the GAP library "fptietze.g" instead of enlarging the print level. This would have to affect the TzEliminate and TzSubstitute routines (in your case the routine "TzEliminateGen1") and should not be too difficult as all routines in question are written in the GAP language. Moreover, instead of just printing some information by commenting out the corresponding print level checks, you could save a list of whatever data you like for later use. > 3) Similarly, can I ask for Size(g) to return "unknown" if it has > to spend more than 30 seconds on it (or perhaps 10M of memory > instead of time).? There is a global variable CosetTableFpGroupDefaultMaxLimit which is set to a value of 64000 by GAP if you don't define it differently. This global variable defines the maximal number of cosets to be defined in an call of the ordinary CosetTableFpGroup function before it is aborted. A similar variable for the AugmentedCosetTableMtc function which is called by the Size function for f.p. groups has not yet been introduced. We will introduce it in the next release. > 4) I asked for the size of h, and got the following. Is this a bug > or a feature? > > gap> g := FreeGroup(3,"g"); > Group( g.1, g.2, g.3 ) > > gap> g.relators := [g.1*g.2*g.3]; > [ g.1*g.2*g.3 ] > > gap> h := SimplifiedFpGroup(g); > Group( g.1, g.2 ) > > gap> Size(h); > Error, Subword: illegal value at > while LengthWord( rel ^ Subword( rel, 1, 1 ) ) < LengthWord( rel ) ... in > RelatorRepresentatives( G.relators ) called from > RelsSortedByStartGen( G, table ) called from > AugmentedCosetTableMtc( G, H, 1, "_x" ) called from > D.operations.Size( D ) called from > Size( h ) called from > main loop > brk> Of course, you should not have got this error message. This is a bug, and we will correct it properly in the next release. For the moment you may fix it by the following change in the code of function "FpGroupPresentation" in the GAP library file "fptietze.g". Please replace the statements numrels := tietze[TZ_NUMRELS]; grels := 0 + [ 1 .. numrels ]; for i in [ 1 .. numrels ] do grels[i] := TzWord( tietze, rels[i] ); od; by grels := []; for i in rels do if i <> [] then Add( grels, TzWord( tietze, i ) ); fi; od; Then your above example should work properly. Volkmar Felsch, Aachen From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Feb 7 16:19:00 1994 From: "Volkmar Felsch" Date: Mon, 07 Feb 94 16:19 +0100 Subject: The PresentationNormalClosure function Recently I had a correspondence concerning the PresentationNormalClosure function which might be of interest for other GAP users, too. Warren Dicks from Barcelona wrote: > Can you tell me to whom I can write to ask the following question? > How can I find expressions for the generators of > PresentationNormalClosureRrs(G,H) in terms of the original > generators of G? I answered: Unfortunately, the program does not return a list of these expressions though it definitely needs them during the computation. In fact, it establishes an intermediate list of the definitions of the so called "primary subgroup generators" (see for the manual) in the resulting presentation. I think that you can get access to this list by just including one additional statement in the function "PresentationAugmentedCosetTable" in the GAP library file "fpsgpres.g". I am not enough familiar any more with the code to guarantee that this works properly, but I think it is worth while to have a try. So I would recommend thatyou to do the following. (1) Extract a copy of the function "PresentationAugmentedCosetTable" from the GAP library file "fpsgpres.g" and write it into a local file "pact", say. (2) Insert in this file the statement T.definitions := aug.primaryGeneratorWords; immediately before the return statement at the end. (3) Start your GAP session with the commands ReadLib( "fpgrp" ); ReadLib( "fptietze" ); ReadLib( "fpsgpres" ); Read( "pact" ); to load the GAP library "fpsgpres.g" and then to overwrite the original version of the above function by the altered one. (4) Then start your computation. After calling the command P := PresentationNormalClosureRrs( G, H ); you should end up with a presentation record which has an additional component P.definitions which hopefully contains the definitions of the primary subgroup generators as words in the original generators of G. Note that you can use the "DecodeTree" command to reduce the list of all subgroup generators to the list of primary subgroup generators. Warren Dicks replied: > Thank you for your message. Yes, it works exactly as you say, so I > will modify the file fpsgpres . > > Would it be too much trouble to ask what code I should add so that > I can trace the generators for the unTreeDecoded presentation, and > and the Simplifyed presentation? TreeDecode, in my case, gives one more > relation than Simplify does, and many many applications of the simplifying > procedure don't seem to get rid of it. I answered: As for your question for words for the unTreeDecoded generators: There is a good reason not to provide these words: They tend to be of enormous length, at least in general. Of course, this may be different for your concrete examples, hence you should have a look at them. Using your modified version of "fpsgpres,g", you may extend the list "P.definitions" to a list of words for all generators using the following (hopefully correct) code. P := PresentationNormalClosureRrs( G, H ); numgens := Length( P.generators ); defs := P.definitions; numprim := Length( defs ); tree := P.tree; treelength := Length( tree[1] ); defs2 := Copy( defs ); for i in [ numprim + 1 .. treelength ] do j := tree[1][i]; if j > 0 then left := defs2[j]; else left := defs2[-j]^-1; fi; j := tree[2][i]; if j > 0 then right := defs2[j]; else right := defs2[-j]^-1; fi; defs2[i] := left * right; od; for i in [ numprim + 1 .. numgens ] do defs[i] := defs2[tree[5][i]]; od; As for your question for words for the generators in an simplified presentation: The "SimplifyPresentation" command does not trace the substitutions it performs. Volkmar Felsch, Aachen From t.d.bending@qmw.ac.uk Tue Feb 8 10:30:00 1994 From: "Thomas D Bending" Date: Tue, 08 Feb 94 10:30 +0100 Subject: Range limits There seems to be an upper limit on the integers that can form the end of a Range - 10^8 works but 10^9 doesn't. Furthermore I think the error message this causes is rather misleading: gap> Length([1..10^9]); Error, Range: must be an integer gap> Length([10^9..10^9+1]); Error, Range: must be an integer gap> IsInt(10^9); true I can't find any documentation on this - am I missing something? Thanks, Thomas Bending From sl25@cus.cam.ac.uk Tue Feb 8 10:31:00 1994 From: "Steve Linton" Date: Tue, 08 Feb 94 10:31 +0100 Subject: Re: Range limits > There seems to be an upper limit on the integers that can form the end > of a Range - 10^8 works but 10^9 doesn't. Furthermore I think the > error message this causes is rather misleading: > > gap> Length([1..10^9]); > Error, Range: must be an integer > gap> Length([10^9..10^9+1]); > Error, Range: must be an integer > gap> IsInt(10^9); > true > > I can't find any documentation on this - am I missing something? I don't think it's documented but: GAP stores integers less than 2^28 (in absolute magnitude) in a special format for speed. Larger integers are stored in an extended format. Range limits (and a few other things) have to be in the 'small' format. Steve From paul.igodt@kulak.ac.be Mon Feb 7 08:53:00 1994 From: "Paul Igodt" Date: Mon, 07 Feb 94 08:53 +0100 Subject: on permutation group "transversals". We are initiating ourselves in the use of GAP. The following question arises in looking at what GAP does to permutation groups. It looks like if the man-page is not fully clear on this neither. When one looks at the output of gp.stabilizer if gp is a well defined permutation group, than one finds a record containing many "transversals". How should these transversals be understood? E.g. they contain often many "extra comma's". As an example consider the following output: Group( (1,2,3,4)(5,6,7,8), (1,2,3), (1,3,5), (1,2)(3,4,7) ) gp.transversal := [ (), (1,2)(3,4,7), (1,2,3), (1,2,3,4)(5,6,7,8), (1,3,5), (1,2,3,4)(5,6,7,8), (1,2)(3,4,7), (1,2,3,4)(5,6,7,8) ] gp.stabilizer := rec( identity := (), generators := [ (2,4,3,5,7)(6,8), (3,5,7), (2,6,7) ], orbit := [ 2, 7, 5, 3, 4, 6, 8 ], transversal := [ , (), (2,4,3,5,7)(6,8), (2,4,3,5,7)(6,8), (2,4,3,5,7)(6,8), (2,6,7), (2,4,3,5,7)(6,8), (2,4,3,5,7)(6,8) ], stabilizer := rec( identity := (), generators := [ (6,8), (3,5,7), (3,4,5), (5,8,7) ], orbit := [ 3, 7, 5, 4, 8, 6 ], transversal := [ ,, (), (3,4,5), (3,5,7), (6,8), (3,5,7), (5,8,7) ], stabilizer := rec( identity := (), generators := [ (6,8), (4,5,7), (5,8,7) ], orbit := [ 4, 7, 5, 8, 6 ], transversal := [ ,,, (), (4,5,7), (6,8), (4,5,7), (5,8,7) ], stabilizer := rec( identity := (), generators := [ (6,8), (5,8,7) ], orbit := [ 5, 7, 8, 6 ], transversal := [ ,,,, (), (6,8), (5,8,7), (5,8,7) ], stabilizer := rec( identity := (), generators := [ (6,8), (6,7,8) ], orbit := [ 6, 8, 7 ], transversal := [ ,,,,, (), (6,7,8), (6,8) ], stabilizer := rec( identity := (), generators := [ (7,8) ], orbit := [ 7, 8 ], transversal := [ ,,,,,, (), (7,8) ], stabilizer := rec( identity := (), generators := [ ] ) ) ) ) ) ) ) Thanks a lot. Is there a procedure in GAP to solve the "word"-problem for permutation groups? E.g. something like "wordsolve(element, group, group.generators)" ? Paul Igodt From sl25@cus.cam.ac.uk Tue Feb 8 16:58:00 1994 From: "Steve Linton" Date: Tue, 08 Feb 94 16:58 +0100 Subject: Re: on permutation group "transversals". > When one looks at the output of > gp.stabilizer > if gp is a well defined permutation group, than one finds a record containing > many "transversals". How should these transversals be understood? E.g. they con > tain > often many "extra comma's". The transversal is realy what is known as a Schreier vector. The extra commas come from the fact that S.transversal[x] is only bound if x lies in S.orbit. If so, then while x <> S.orbit[1] do x/S.transversal[x]; od; will always terminate (and reasonably quickly). To put it another way, from S.transversal you can compute, efficiently an element s in S such that S.orbit[1]^s = x, for any x in S.orbit. > Is there a procedure in GAP to solve the "word"-problem for permutation groups? > E.g. something like "wordsolve(element, group, group.generators)" ? Not as far as I know, though it might be possible (I'm guessing) to do something by defining a homomorphism from a free group to your permutation group and the looking for a pre-image representative of the element in question. Steve From hwblist@machnix.mathematik.uni-stuttgart.de Tue Feb 8 17:10:00 1994 From: "Harald Boegeholz" Date: Tue, 08 Feb 94 17:10 +0100 Subject: Re: on permutation group "transversals". > Date: 07 Feb 94 08:53 +0100 > From: Paul Igodt > > When one looks at the output of > gp.stabilizer > if gp is a well defined permutation group, than one finds a record containing > many "transversals". How should these transversals be understood? E.g. they contain > often many "extra comma's". > These transversals are needed by the algorithm that generates the stabilizer chain (Schreier/Sims). You have to understand that algorithm to take any advantage of them, I think. > Is there a procedure in GAP to solve the "word"-problem for permutation groups? > E.g. something like "wordsolve(element, group, group.generators)" ? I don't think so. I once wrote such a program (by modifying MakeStabStrong etc. in such a way that it records how new generators were constructed out of the old generators). Unfortunately, it was not very useful for "practical" purposes :-): For Rubik's Cube it produced words with an average length of about 500,000. It also needed quite some memory to compute those. But it did produce solutions in finite time ;-). If you are interested in the code (it will probably work better for smaller groups), I can dig it out and mail it to you. hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From dfh@maths.warwick.ac.uk Tue Feb 8 17:33:00 1994 From: "Derek Holt" Date: Tue, 08 Feb 94 17:33 +0000 Subject: Re: on permutation group "transversals". > > > Is there a procedure in GAP to solve the "word"-problem for permutation groups? > > E.g. something like "wordsolve(element, group, group.generators)" ? > > I don't think so. I once wrote such a program (by modifying > MakeStabStrong etc. in such a way that it records how new generators > were constructed out of the old generators). > > Unfortunately, it was not very useful for "practical" purposes :-): > For Rubik's Cube it produced words with an average length of about > 500,000. It also needed quite some memory to compute those. But it > did produce solutions in finite time ;-). > > If you are interested in the code (it will probably work better for > smaller groups), I can dig it out and mail it to you. > > > hwb > -- > Harald Boegeholz | hwb@mathematik.uni-stuttgart.de > | os2a@info2.rus.uni-stuttgart.de > Yes, I have also done something similar. I have often found myself in the situation of having some sort of homomorphism phi:G -> H, where G is a permutation group, and phi is defined by its images on the generators. But then you want to be able to calculate phi on an arbitrary element of G. The last time I tried this naively in GAP, it took ages, even on what I consider to be moderately small groups like M12. I suspect it was calculating the whole Cayley graph of the group to do the calculation. To do this efficiently, you do not need to express an element g as a word in the original generators (which, as was observed by Harald Boegeholz above, would result in extremely long words). The obvious way is to calculate phi on the strong generators, and then express your g as a word in the strong generators, which can be done very quickly. It is easy to calculate phi on the strong generators, provided you do it as you calculate them, since the new strong generators appear as words in the existing ones. The problem is that these words are not remembered by GAP, and so you need to recalculate the strong generators for every homomorphism that you want to define. It would be more satisfactory if there were a built-in method for remembering and reconstructing these words. The particular situation in which I needed this was to calculate induced representations from a subgroup H of G to G. The representation of H is likely to be given on the generators of H, but to calculate the induced representation, you need to be able to calculate its value on lots of arbitrary elements of H. I solved this also by modifying MakeStabStrong. Now it works very quickly for quite large examples. I can supply the GAP functions to anyone who is interested. (I happen also to know that Peter Webb did something similar for the identical problem.) Derek Holt. From sl25@cus.cam.ac.uk Tue Feb 8 20:06:00 1994 From: "Steve Linton" Date: Tue, 08 Feb 94 20:06 +0100 Subject: Backtrack. A slight but significant speed up of the backtrack functions in permbckt.g is possible: replace Subgroup by G.operations.Subgroup (or similar) wherever it is called inside the recursion. I am doing some backtracking in a rather large degree (306936) permutation group, and it is spending an irritatingly large amount of time checking that elements passed to Subgroup are actually in the parent group. Actually I think this check should be disablable anyway, as it can force construction of a Stabiliser chain where none is really needed. Steve From Alexander.Hulpke@Math.RWTH-Aachen.DE Wed Feb 9 10:23:00 1994 From: "Alexander Hulpke" Date: Wed, 09 Feb 94 10:23 +0100 Subject: Re: on permutation group "transversals". Dear Forum, In his letter, Derek Holt wrote: > > > > > > Is there a procedure in GAP to solve the "word"-problem for permutation groups? > > > E.g. something like "wordsolve(element, group, group.generators)" ? > > > > I don't think so. I once wrote such a program (by modifying > > MakeStabStrong etc. in such a way that it records how new generators > > were constructed out of the old generators). > > Yes, I have also done something similar. > I have often found myself in the situation of having some sort of > homomorphism phi:G -> H, where G is a permutation group, and > phi is defined by its images on the generators. > But then you want to be able to calculate phi on an arbitrary element > of G. The last time I tried this naively in GAP, it took ages, even > on what I consider to be moderately small groups like M12. I suspect it > was calculating the whole Cayley graph of the group to do the calculation. If you define the Homomorphism by GroupHomomorphismByImages (which is probably the procedure most useful for this task), you should also set h.isMapping:=true; and h.isHomomorphism:=true; The reason is, that GAP will otherwise try to check, whether the mapping really is an homomorphism, a task which might lead to partial computation of the Cayley graph and takes abominably long. > To do this efficiently, you do not need to express an element g as a > word in the original generators (which, as was observed by Harald Boegeholz > above, would result in extremely long words). The obvious way is to > calculate phi on the strong generators, and then express your g as a > word in the strong generators, which can be done very quickly. > It is easy to calculate phi on the strong generators, provided you do it > as you calculate them, since the new strong generators appear as words > in the existing ones. The problem is that these words are not remembered > by GAP, and so you need to recalculate the strong generators for every > homomorphism that you want to define. It would be more satisfactory if there > were a built-in method for remembering and reconstructing these words. If GAP knows, that the object you defined is indeed an homomorphism, it basically does the suggested procedure: It will construct a new stabilizer chain for this homomorphism and represent the strong generators as words in the given preimages. Applying the homomorphism should be fast afterwards, I would suppose applying it to an element of M12 (unless the range involves very hard computations) should take not more than a few seconds (at least these are my experiences with groups that are even significantely larger than M12). If you set .isMapping and .isHomomorphism to true, GAP will just do this evaluation process. Thus the easiest way to decompose a group element is generator words via the stabilizer chain, probably is (in an abuse of Homomorphisms: f:=FreeGroup(n); h:=GroupHomomorphismByGenerators(g,f,g.generators,f.generators); h.idMapping:=true;h.isHomomorphism:=true; # this is not really true Image(h,el); #yields word in generators Strangely enough, the other --- proper --- way (i.e. mapping from the free group to the group) seems to take longer (most likely, because it starts computing the kernel first). Also GAP has quite difficulties in that case to prove, that the mapping is an homomorphism if you don't tell it so (though it is one by definition of a free group). I should add one further observation to ease working with homomorphisms: If your homomorphism corresponds to an operation, which is not obvious (i.e. operation on an orbit), it may be helpful to use GroupHomomorphismByImages instead of OperationHomomorphism, especially when computing preimages, because running through a stabilizer chain is in general much faster, than operation or even finding an element, that will yield the desired operation. Alexander Hulpke From dfh@maths.warwick.ac.uk Wed Feb 9 11:22:00 1994 From: "Derek Holt" Date: Wed, 09 Feb 94 11:22 +0000 Subject: Re: on permutation group "transversals". > > f:=FreeGroup(n); > h:=GroupHomomorphismByGenerators(g,f,g.generators,f.generators); > h.isMapping:=true;h.isHomomorphism:=true; # this is not really true > Image(h,el); #yields word in generators > > Alexander Hulpke > Oh well, thanks for the helpful information on defining homomorphisms from permutation groups; I would certainly never have thought os applying the trick in the example above (although I have checked now that there is a reference to it in the manual). But this is all a bit sneaky isn't it? I'm quite shocked at the idea that someone would tell a poor innocent computer that a map was a homorphism when it wasn't, just to trick it into answering a question. Derek Holt. From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Feb 9 14:24:00 1994 From: "Martin Schoenert" Date: Wed, 09 Feb 94 14:24 +0100 Subject: Re: Range limits Thomas Bending writes in his e-mail message of 1994/02/08 There seems to be an upper limit on the integers that can form the end of a Range - 10^8 works but 10^9 doesn't. Furthermore I think the error message this causes is rather misleading: gap> Length([1..10^9]); Error, Range: must be an integer gap> Length([10^9..10^9+1]); Error, Range: must be an integer gap> IsInt(10^9); true I can't find any documentation on this - am I missing something? Internally GAP distinguishes between three types of integers. Integers between -2^28 and 2^28-1 called *small integers*, integers larger than 2^28-1 called *large positive integers*, and integers less than -2^28 called *large negative integers*. Large integers are represented by a pointer to a block of memory (called a bag) where the individual digits (in base 2^16) are stored. For small integers no pointer is used. Instead the value is stored immediatly (after shifting it two bits to the left and adding one, so that it is possible to distinguish between immediate integers and pointers). In certain places GAP needs immediate integers. One place are ranges, i.e., in [..] and must be small integers. This may get fixed in the near future. Another place are indices into lists, i.e., in '[]' must be a small integer. To fix this one would first have to implement a sparse representation for lists where the amount of memory allocated for a list depends on the number of assigned entries. With the current dense representation the amount of memory depends on the largest position of any assigned entry. So the list 'l := []; l[10^9] := 1;' would need '4*10^9' bytes, clearly more than most machines have. To implement such a sparse representation and then allow large integers as indices is not among our immediate plans. Cleary a better error message would be desirable. And, I agree, it would also be nice if the documentation mentioned this problem. 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 osterlu@s5.math.umn.edu Wed Feb 9 09:11:00 1994 From: "Philip Osterlund" Date: Wed, 09 Feb 94 09:11 -0600 Subject: Re: on permutation group "transversals". I have worked on some functions that, given a permutation group G, and an element r of G, the functions produce an abstract word such that I have worked on some functions that work with the word problem for permutation groups. The functions are elaborations on things written by Peter Webb. The idea of my functions is this: Let G be a permutation group generated by [p1..pn]. Define G.abstractGenerators to be a list [a1..an] of abstract generators Create something like the stabilizer chain, that is actually a chain of stabilizer subgroups. To make sure that the generators do not grow exponentially in length, make preferences in the choice of generators to those of shortest lengths. Given an element r of G, produce a word r1 in [p1..pn], using the stabilizer chain in much the same way that "in" works, but keeping track of what left transversals are multiplied together. As a sample run, I show an example from Rubik's cube: gap> Read("abgens2"); gap> Read("cube"); The group 'cube' represents the operations of the Rubik's cube: +----------+ | 1 2 3 | | 4 R 5 | | 6 7 8 | +----------+----------+----------+----------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 W 13 | 20 Y 21 | 28 B 29 | 36 G 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +----------+----------+----------+----------+ | 41 42 43 | | 44 O 45 | | 46 47 48 | +----------+ To draw the cube at any time, type 'drawcube()'. To draw a particular permutation g, type 'DrawCube(g)'. The cube is generated by the clockwise rotations of the sides, R, W, Y, B, G, O for Red, White, Yellow, Blue, Green, and Orange. They may also be referred to respectively as top, left, front, right, rear, bottom gap> l := [18,20,17,4,21,19,5,23,22,15,24,31,36,34,33,37,35,39,38,40]; [ 18, 20, 17, 4, 21, 19, 5, 23, 22, 15, 24, 31, 36, 34, 33, 37, 35, 39, 38, 40 ] gap> qube := ShallowCopy(cube); cube gap> qube.name := "qube"; "qube" gap> s := Runtime();MakeAbStabChain(cube);e := Runtime();e-s;MakeAbStabChain(qube,l); Runtime()-e; 5100 53733 48633 43333 gap> ### 48.633 seconds to make the stabilizer chain for cube gap> ### 43.333 seconds to make the stabilizer chain for qube gap> r := Random(cube); ( 1,22,38, 9,41,48,35,16,32)( 2, 5,28,18,42,44,12,47,10,45,34,26,21, 7,23,15, 37,39, 4,31)( 3,40,24,11,33,14,30, 6,27,46,43,17)( 8,25,19)(13,20) gap> s := Runtime();rc := FactorPermGroupElement(cube,r);;e := Runtime();e-s; 97166 97166 0 gap> s := Runtime();rq := FactorPermGroupElement(qube,r);;e := Runtime();e-s; 97216 97216 0 gap> LengthWord(rc); 1219 gap> LengthWord(rq); 781 gap> s := Runtime();rc1 := Shrink(cube,rc);e := Runtime();e-s; 97350 G^-1*W*G^-1*O*R*O*B*G*R^-1*G^-1*O^-2*G*R*G^-1*B^-1*O^2*W*O*W^-1*R^-1*Y^-1*B*Y*\ B^-1*Y*O^-1*Y^-1*B*Y^-1*B^-1*Y*O*Y*O^-1*Y^-1*O*R*W*R^-1*Y^-1*R*W*R^-1*Y^-1*B*Y\ *B^-1*O^-1*G*R*Y*R^-1*G^-1*Y*B*G*R^-1*G^-1*Y^-1*R*W*R^-1*B*G*R*G^-1*Y^-1*W*G*W\ ^-1*R*W^-1*R^-1*G^-2*O^-1*R^-1*G*R*Y*R^-1*G^-1*Y^-1*R*W^-1*R^-1*B*G*R^-1*G^-1*\ B*Y*B^-1*O^-1*B^-1*R*W*R^-1*W*G^-1*W^-1*G^-2*O^-1*Y*R^-1*Y*R*G^-1*B^-1*G*R*G^-\ 1*B^-1*R*W^-1*R^-1*B^-1*G*R^-2*G^-1*W*G*W^-1*R*W^-1*R^-1*G*Y^-1*O^-2*W^-1 130833 33483 gap> ### 33.483 seconds to "Shrink" rc using cube gap> LengthWord(rc1); 135 gap> s := Runtime();rq1 := Shrink(qube,rq);e:=Runtime();e-s;LengthWord(rq1); 130950 G^-2*O*G^-1*O^-1*B*O^-1*B^-1*O*G^-1*O^-1*B*O*B^-1*O*G*O^-2*B*O*B^-1*O*G*O^-1*B\ *O^-1*B^-1*G*B*O*B^-1*O^-1*G^-2*O*G*O^-1*G*O*G^-1*O^-1*G*B*O^-1*B^-1*G*B*O*B^-\ 1*O^-1*G^-2*B*O*B^-1*O^-1*G*O*G^-1*O^-1*G*O^2*B*G^-1*B^-1*O*B*G*B^-1*O*B*O*B^-\ 1*G^-1*O*B*G^-1*B^-1*O^-1*G^-1*B*O^-1*B*G^-1*O^-2*W^-1*G*W*O*W^-1*G^-2*W*B*O*W\ *O^-1*G*B*O^-1*Y*B^-1*Y^-1*O^-1*W^-1 151366 20416 107 gap> ### 20.416 seconds to "Shrink" rq using qube You may email me for the files. -Philip Osterlund From mikec@math.ubc.ca Wed Feb 9 17:14:00 1994 From: "Michael B. Cherkassoff" Date: Wed, 09 Feb 94 17:14 -0800 Subject: Involutions in PSLs Dear GAP-Forum. I have some problems with (I guess) implementation of GAP. I do work with finite Projective Special Linear Groups. At the moment they are being represented as some permutation groups (namely, the action of SLs on lines). (I very much appreciate the help of Alexander Hulpke, who provided me with the text of GAP procedure for this). This works OK (much faster than calculations with matrices for SL) until the order of the group goes to several billions. (like PSL(3,17) or PSL(3,19) or PSL(4,5)). For these cases GAP can construct the group, calculate the size, construct conjugacy classes, but it can't calculate centralizer of the element. I did the job in background with redirecting of input-output and GAP would just stop working without any error message. So is it a bug in GAP (I can provide exact text of the program to nail it) or is it just natural restriction of the size? Also I would appreciate very much the help on how to collect all involutions in the group. Now I'm doing by computation of all conjgacy classes (which I don't need) and then picking ones with elements of order 2. Thank you very much, Michael. From Alexander.Hulpke@Math.RWTH-Aachen.DE Thu Feb 10 17:59:00 1994 From: "Alexander Hulpke" Date: Thu, 10 Feb 94 17:59 +0100 Subject: Re: Involutions in PSLs Dear GAP-Forum. In his letter, Michael Cherkassoff wrote: > I have some problems with (I guess) implementation of GAP. > > I do work with finite Projective Special Linear Groups. At the > moment they are being represented as some permutation groups > > [...] > > For these cases GAP can construct the group, > calculate the size, > construct conjugacy classes, > but it can't calculate centralizer of the element. If you get the conjugacy classes, each class has an entry .centralizer, which contains the centralizer of the class representative. > I did the job in background with redirecting of input-output and > GAP would just stop working without any error message. In this case, the job grew too large for the system, and thus died. > So is it a bug in GAP (I can provide exact text of the program to nail it) or > is it just natural restriction of the size? The restriction is by the size, the operating system allows for GAP. > Also I would appreciate very much the help on how to collect all > involutions in the group. Now I'm doing by computation of all > conjgacy classes (which I don't need) and then picking ones with > elements of order 2. I don't think, this is the way one should do it. First, all these groups have relatively few classes of involutions. The character table will show you how many classes of involutions exist. Then searching for random elements of even order and powering them should yield you representatives for the classes easily. (By creating the corresponding ConjugacyClass es, one can check for conjugacy using the 'in' command.) However, it should be also possible to obtain these representatives by using the normal form of matrices, as L(n,q) does not differ too much from GL(n,q). Alexander Hulpke From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Feb 10 19:55:00 1994 From: "Joachim Neubueser" Date: Thu, 10 Feb 94 19:55 +0100 Subject: Collecting GAP programs Dear Forum members, In the discussion in the GAP-forum over the last days several colleagues have offered programs written in GAP that either complement or improve functions available in the library of GAP functions of release 3.3. This is a most welcome development that GAP, as an open system, has been meant to trigger from the beginning. However such offers made just once in the GAP forum will reach only some of those who might be interested. Therefore we are offering a further possibility. On the same server in Aachen from which you can obtain GAP and a number of share libraries we have established a directory in which you can deposit programs that you offer for everybody's use. You can do this by 'ftp samson.math.rwth-aachen.de' login as 'ftp' the directory is '/pub/incoming' into which you can deposit your file(s) with 'put'. We suggest that your file should have a suggestive name, that it should start with a comment with your name, postal and e-mail address and a description of what the program(s) are supposed to do and then of course the code. If you are sending several files belonging together we suggest that you should also provide a file giving an overview. We emphasize that we will not do any editing, checking or anything else to these files, which remain completely under the responsibility of the sender. So in particular we do not assume any responsibility for them and any questions or comments should go to the authors (or into the GAP-forum). All we will try to do from time to time is to create an index of these files which we will likewise deposit in this directory and also publish in the GAP-forum. Obviously we do not have any experience how well this will work, and in the light of experience we may have to modify the setup later, but I hope that it will grow into a useful service for the communication of colleagues working with GAP and I invite and ask you to use it. With kind regards Joachim Neubueser From beals@sisters.cs.uoregon.edu Thu Feb 10 23:19:00 1994 From: "Robert Beals" Date: Thu, 10 Feb 94 23:19 -0800 Subject: possible problem with Domain() Hello, I'm having a problem finding the minimal polynomial of a rational matrix A. MinimalPolynomial(A) first finds D = Domain([A]), and then applies D.operations.MinimalPolynomial. Unfortunately, if A is a rational matrix, then Domain([A]) returns Matrices, and Matrices.operations.MinimalPolynomial is unbound. Is there any reason why for a rational matrix A, Domain([A]) doesn't return FieldMatrices? (FieldMatrices.operations.MinimalPolynomial exists.) I tried to get around this by simply setting Matrices.operations.MinimalPolynomial := FieldMatrices.operations.MinimalPolynomial; This seems to work for rational matrices A, and indeed there is nothing in the code for FieldMatrices.operations.MinimalPolynomial that makes any assumptions about the field. However, I also tested matrices over cyclotomic fields, and ran into difficulties, because for a cyclotomic field F GAP seems to be unable to compute Euclidean quotients in F[x] (that is, the ring of polynomials in x over the field F, not the xth element of the list F). This is puzzling, but since I'm mainly interested in rational matrices I didn't chase it down any further. Any help or advice would be greatly appreciated. -- Robert Beals P.S. I'm using version 3 release 3. From Frank.Celler@Math.RWTH-Aachen.DE Fri Feb 11 14:00:00 1994 From: "Frank Celler" Date: Fri, 11 Feb 94 14:00 +0100 Subject: Re: possible problem with Domain() Dear Robert Beals, Matrices.operations.MinimalPolynomial is unbound. Is there any reason why for a rational matrix A, Domain([A]) doesn't return FieldMatrices? (FieldMatrices.operations.MinimalPolynomial exists.) the reason is, that we plan to use 'MatrixAlgebra( K, n )' as result of a 'Domain' call as soon as there are matrix algebras in GAP (which will be in the near future). At the moment you should call 'MinimalPolynomial' with the additional first parameter 'FieldMatrices' (or 'FiniteFieldMatrices' depending on your problem). gap> MinimalPolynomial( FieldMatrices, [ [1,2], [3,4] ] ); X(Rationals)^2 - 5*X(Rationals) - 2 The problem with this solution is that you cannot force your matrices to be interpreted as matrices over a given field. for a cyclotomic field F GAP seems to be unable to compute Euclidean quotients in F[x] (that is, the ring of polynomials in x over the there was indeed a problem in GAP 3r3, this is fixed in 3r4. best wishes Frank From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Feb 11 15:12:00 1994 From: "Martin Schoenert" Date: Fri, 11 Feb 94 15:12 +0100 Subject: Re: on permutation group "transversals". Paul Igodt asks in his e-mail message of 1994/02/07 When one looks at the output of 'gp.stabilizer'. If 'gp' is a well defined permutation group, than one finds a record containing many "transversals". How should these transversals be understood? E.g. they contain often many "extra comma's". The entries 'gp.orbit' and 'gp.transversal' belong together. The point 'gp.orbit[1]' is called the basepoint 'bpt'. For each 'i' in 'gp.orbit' there is an entry 'gp.transversal[i]'. This is the reason why there can be ``extra commas'' in 'gp.transversal'. E.g., if 'gp.orbit' is '[1,3,5,7]', then only the entries at positions 1, 3, 5, and 7 have assigned values in 'gp.transversal'. The entry 'gp.transversal[i]' is a permutation 'p' that takes 'i' to a point earlier in the orbit, i.e., 'Position( gp.orbit, i ) > Position( gp.orbit, i^p )'. Actually this is only true if 'i' is not 'bpt', 'gp.transversal[bpt]' is always the identity '()'. So for example assume that 'gp.orbit' is '[ 3, 7, 5, 4, 8, 6 ]' and 'gp.transversal' is '[,,(),(3,4,5),(3,5,7),(6,8),(3,5,7),(5,8,7)]'. 'gp.transversal[1]' and 'gp.transversal[2]' are unbound because 1 and 2 are not in 'gp.orbit'. We can picture the structure represented by 'gp.orbit' and 'gp.transversal' as follows. (3,5,7) (3,4,5) .--<---- 5 ----<---- 4 (3,5,7) / 3 ----<---- 7 \ `--<---- 8 ----<---- 6 (5,8,7) (6,8) To compute a representative for a point 'i' we start with that point and follow the path to the basepoint 'bpt' multiplying the permutations along the edges as we go along. The result is a permuation mapping 'i' to 'bpt', so to get a representative we have to invert this. For example, suppose we start with the point '6'. Then we multiply the permutations along the edges '(6,8) * (5,8,7) * (3,5,7) = (3,5,8,6)'. To get a representative we invert this '(3,6,8,5)'. In GAP code this looks as follows # we want to compute a representative for 'i' r := (); while i <> gp.orbit[1] do i := i ^ gp.transversal[i]; r := r * gp.transversal[i]; od; r := r^-1; One can avoid the extra inversion as follows # we want to compute a representative for 'i' r := (); while i <> gp.orbit[1] do i := i ^ gp.transversal[i]; r := LeftQuotient( gp.transversal[i], r ); od; Note that 'LeftQuotient(,)' means '^-1 * ', is sometimes written as ' mod ', and is for permutations just as fast as an ordinary multiplication. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Feb 11 16:07:00 1994 From: "Martin Schoenert" Date: Fri, 11 Feb 94 16:07 +0100 Subject: Re: on permutation group "transversals". Paul Igodt asks in his e-mail message of 1994/02/07 Is there a procedure in GAP to solve the "word"-problem for permutation groups? E.g. something like "wordsolve(element,group,group.generators)"? Steve Linton answers in his e-mail message of 1994/02/08 Not as far as I know [...] Harald Boegeholz answers in his e-mail message of 1994/02/08 I don't think so. I once wrote such a program (by modifying MakeStabStrong etc. in such a way that it records how new generators were constructed out of the old generators). Derek Holt answers in his e-mail message of 1994/02/08 Yes, I have also done something similar. It is in fact possible to do this in GAP, but appearantly this is one of the best kept secrets in GAP :-(. Here is how to do it. gap> m12 := Group( (1,12,6,8,9,2)(3,7,4,10,11,5), > (1,4,5,3,11)(2,12,7,6,9) );; gap> Size( m12 ); 95040 gap> f2 := FreeGroup( 2, "f2" ); Group( f2.1, f2.2 ) gap> h := GroupHomomorphismByImages(f2,m12,f2.generators,m12.generators);; gap> r := Random(m12);; w := PreImagesRepresentative(h,r);; time; 3089 gap> r := Random(m12);; w := PreImagesRepresentative(h,r);; time; 4 gap> LengthWord( w ); 510 The first call to 'PreImagesRepresentative' takes about 3 seconds, because it constructs the extended stabilizer chain. All subsequent calls then take only a couple of milliseconds. It is important to use 'PreImagesRepresentative', instead of 'PreImage'. 'PreImage' can only be used if each image has a unique preimage, i.e., is if the kernel of the homomorphism is trivial, which is clearly not the case with 'h' (actually GAP 3.3 fails with the message 'index of in is infinite', which is a bug). To compute images under 'h', one should either use 'ImagesRepresentative', or set 'h.isHomomorphism := true;' and 'h.isMapping := true;' and use 'Image' (yes, it is a bug in GAP that declaring 'h' to be a homorphism is necessary in this case). It is also possible to do this as follows. gap> x := GroupHomomorphismByImages(m12,f2,m12.generators,f2.generators);; gap> r := Random(m12);; w := ImagesRepresentative(h,r);; time; 4152 gap> r := Random(m12);; w := ImagesRepresentative(h,r);; time; 4 gap> LengthWord( w ); 415 Note, however that 'x' is not a homorphism, in fact it is not even a single valued mapping. In GAP 3.3 this is not a problem (but in GAP 4.0 we will probably disallow the construction of such multivalued mappings). But one must use 'ImagesRepresentative' of course. Telling GAP that it is a homomorphism, so that one can use 'Image', is indeed a shocking suggestion. Anyhow, the problem with this approach is however the length of the words produced by this method. In the above example the words are of length 510 and 415 respectively. The methods used by Philip Osterlund to shorten the words seem very interesting. 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 osterlu@s5.math.umn.edu Fri Feb 11 16:23:00 1994 From: "Philip Osterlund" Date: Fri, 11 Feb 94 16:23 -0600 Subject: The word problem for permutation groups I have submitted my functions that deal with the word problem. The files are AbStab.doc AbStab.g and they are stored at samson.math.rwth-aachen.de in the directory /pub/incoming I realize that the file names (Abstract Stabilzer Chains) aren't too sugestive as they are, and suggestions for better names would be welcome. The functions also contain a few redundancies, and some things may be implemented better in GAP already. I also have some files dealing with group rings, however I have not worked on the documentation. -Philip Osterlund From Frank.Celler@Math.RWTH-Aachen.DE Thu Feb 17 13:02:00 1994 From: "Frank Celler" Date: Thu, 17 Feb 94 13:02 +0100 Subject: Gap on the Macintosh Dear Prof. David Bayer, I have got the following question from M.Jiang: ----------------------------------------------------------------------------- I tried to compile GAP under Macintosh Programmers' Workshop with MPW C version 3.2 without success. First, the gap.make file gives "undefined objects" errors. After I changed the order of a few lines in the file, MPW complained that it could not find the sysmac.c or sysmac.h file. I changed the file names to system.c and system.h as I saw that there are MPW specific lines there. Then the compiler complained about some interrupt handling routines in system.c (confused by the signal() function). I tried to comment out the line temporarily. The compiler then ran without complaining, but the linker failed miserably (something about the global data size, or heap size, or the like). I wonder if the file gap.make was not intended to be used yet. I would appreciate it if a ready-to-run tool be made available if the problem I had was due to my setup. Thanks a lot for your time. Mingchang Jiang ----------------------------------------------------------------------------- as the "make_mpw" is written by you, I assume that it should be possible to compile GAP using the MPW C. But which version is necessary to compile and link it? many thanks in advance Frank Celler From Thomas.Breuer@Math.RWTH-Aachen.DE Fri Feb 18 14:16:00 1994 From: "Thomas Breuer" Date: Fri, 18 Feb 94 14:16 +0100 Subject: bug reports Dear Mrs. and Mr. Forum, yesterday Akihiro Munemasa sent two bug reports to 'gap-trouble'. The first was about an error message that occurs in some cases in the computation of (rational) conjugacy classes. For example, 'ConjugacyClasses( GU(2,5) )' will produce this. The second was about the groups 'GU(2,q)' and 'SU(2,q)'. Here one gets no error message. But the groups one gets with these commands are not the required unitary groups. Two other bugs in GAP-3.3 should be mentioned which meanwhile were found in Aachen. The first is in the new implementation of the LLL algorithm; in some cases the computed basis is not LLL-reduced, or it contains zero vectors. The other bug is in one of the programs that are used to compute the canonical representative of conjugacy classes in Ag groups; in some cases the question whether two elements are conjugate is answered ``no'' although in fact the elements are conjugate. All these bugs will be fixed in the next version of GAP. Kindest regards Thomas Breuer From Frank.Celler@Math.RWTH-Aachen.DE Fri Feb 18 17:39:00 1994 From: "Frank Celler" Date: Fri, 18 Feb 94 17:39 +0100 Subject: Gap for Macintosh To all people who are waiting for a Macintosh port of Gap 3.3, I got the following information from Prof. Bayer: ----------------------------------------------------------------------------- From: dab@entwood.math.columbia.edu Hi. Martin and I recently redid the GAP port to Macintosh, using MPW 3.2 because of a hideous failure to comply with a little known ANSI convention in MPW 3.3. This is a better port, using current GAP source. We will make the compiled file available. Dave From Thomas.Breuer@Math.RWTH-Aachen.DE Mon Feb 21 16:19:00 1994 From: "Thomas Breuer" Date: Mon, 21 Feb 94 16:19 +0100 Subject: bug in cosets of factor groups Dear Mrs. and Mr. Forum, today Charles Wright sent a bug report to 'gap-trouble' in which he points out the following. If you are computing with cosets in factor groups that are not represented as Ag groups then you might get an error message. Here is a possibility to produce this. g:= SL(2,2); h:= SylowSubgroup( g, 3 ); f:= g / h; Cosets( f, f ); As usual, this bug will be fixed in the next version of GAP. Kind regards Thomas Breuer From jcbhrb@cerf.net Mon Feb 21 16:09:00 1994 From: "Jacob Hirbawi" Date: Mon, 21 Feb 94 16:09 -0800 Subject: a group action question I'd like to solicit the forum's help in a group action problem that I'm looking at : start with a permutation group G and let one of its subgroups act by conjugation on one of its (G's) conjugacy classes. I'd like to get representatives of the orbits of this action. For the particluar case that I need now, G is the symmetric group of degree 2n, the subgroup is the cyclic group of the same degree, and the conjugacy class corresponds to the partition [2,2,...,2] of 2n. I wrote the function below to do this but it doesn't seem to handle the n>5 cases very well, so it seems that I need something more efficient -- I'd like to look at the 1x+Mod(x,2)-Mod(x+1,2))); # conjugacy class of Sym(2n) corresponding to permutation class := ConjugacyClass(SymmetricGroup(2*n),permutation); Print("size of class : ",Size(class),"\n"); # cyclic permutation (1,2,3,...,2n) generator := PermList(List([1..2*n],x->Mod(x,2*n)+1)); # cyclic group of order 2n group := Group( generator ); # orbits of group on class orbits := Orbits(group, Elements(class),function(d,g) return d^g; end); Print("number of orbits : ",Size(orbits),"\n"); representatives := List(orbits,x->x[1]); return representatives; end; Any suggestions are greatly appreciated. Jacob Hirbawi JcbHrb@CERF.net From Alexander.Hulpke@Math.RWTH-Aachen.DE Tue Feb 22 12:51:00 1994 From: "Alexander Hulpke" Date: Tue, 22 Feb 94 12:51 +0100 Subject: Re: a group action question Dear Gap-Forum. Jakob Hirbawi asked: > I'd like to solicit the forum's help in a group action problem that I'm > looking at : start with a permutation group G and let one of its subgroups > act by conjugation on one of its (G's) conjugacy classes. I'd like to get > representatives of the orbits of this action. > > For the particluar case that I need now, G is the symmetric group of degree 2n, > the subgroup is the cyclic group of the same degree, and the conjugacy class > corresponds to the partition [2,2,...,2] of 2n. I wrote the function below to > do this but it doesn't seem to handle the n>5 cases very well, so it seems > that I need something more efficient -- I'd like to look at the 1 > Is there a better way to do this? > I think there is. Four comments to your problem: [ original procedure nearly almost ommitted ] > orbits := Orbits(group, Elements(class),function(d,g) return d^g; end); since you are operating in the 'natural' way, you dont have to give a special operation function, but can use 'OnPoints' or even leave it out. GAP will then use the internal 'OnPoints', which is faster. However, for n>6 or so, the class becomes too big, to write down all elements. A 'generic' way to cope with it, is trying to find enough class elements by random, as does the following procedure: GenerateOrbits := function(n) local permutation,class,generator,group,orbits,lengthsum,orb,r; # permutation corresponding to partition [2,2,...,2] of 2n permutation := PermList(List([1..2*n],x->x+Mod(x,2)-Mod(x+1,2))); # conjugacy class of Sym(2n) corresponding to permutation class := ConjugacyClass(SymmetricGroup(2*n),permutation); Print("size of class : ",Size(class),"\n"); # cyclic permutation (1,2,3,...,2n) generator := PermList(List([1..2*n],x->Mod(x,2*n)+1)); # cyclic group of order 2n group := Group( generator ); # orbits of group on class orbits:=[]; lengthsum:=0; repeat r:=Random(class); # we suppose, that the subgroup is small. So writing down one orbit, is # actually no problem. If the subgroup is larger, One should use # RepresentativeOperation to test for conjugacy instead orb:=Orbit(group,r); if Length(Intersection(orb,orbits))=0 then # we have found a new one Add(orbits,r); lengthsum:=lengthsum+Length(orb); Print("#I Length ",Length(orb)," found, total ",lengthsum," \n"); fi; until lengthsum=Size(class); Print("number of orbits : ",Length(orbits),"\n"); return orbits; end; However, this routine still takes too long, though it does not waste memory. The next possibility would be to compute double cosets U\S_2n/Centralizer and conjugate with representatives, but in your example, this seems to be no advantage. Up to this point, we have not utilized the specific structure, i.e. that we have the full symmetric group. We may use this, by running in a special loop through all elements of the specified class, and check again, whether they are conjugated under the action of U. As we get the elements in lexicographic order, they are mostly non conjugate, and we get enough orbit representatievs fairly quick. The work is done by the following routine: GenerateOrbits1 := function(n) local ran,p,pw,orb,orbits,l,sel,i,j,e,a,b,lengthsum,pl,generator,group, permutation,class; # permutation corresponding to partition [2,2,...,2] of 2n permutation := PermList(List([1..2*n],x->x+Mod(x,2)-Mod(x+1,2))); # conjugacy class of Sym(2n) corresponding to permutation class := ConjugacyClass(SymmetricGroup(2*n),permutation); class:=Size(class); # cyclic permutation (1,2,3,...,2n) generator := PermList(List([1..2*n],x->Mod(x,2*n)+1)); # cyclic group of order 2n group := Group( generator ); ran:=[1..2*n]; # the class, which is a power of is found last after some # search in vain. So we start with it. orbits:=[permutation^n]; lengthsum:=1; # now run through the class of multiple transpositions l:=List([1..2*n],i->1); p:=[1]; sel:=[]; for i in [1..n] do sel[2*i]:=Filtered(ran,j->j>=2*i); od; sel[2*n]:=[]; i:=2; pl:=[]; repeat while i<2*n do p[i]:=sel[i][l[i]]; # next lexicographic point as start point of next transposition pw:=p{[1..i]}; p[i+1]:=First(ran,j->not j in pw); i:=i+2; if i<2*n then sel[i]:=Difference(ran,p{[1..i-1]}); l[i]:=1; fi; od; pw:=p{[1..2*n-1]}; p[2*n]:=First(ran,i->not i in pw); # now translate p to permutation for j in [1..n] do a:=p[2*j-1]; b:=p[2*j]; pl[a]:=b; pl[b]:=a; od; e:=PermList(pl); orb:=Orbit(group,e); if Length(Intersection(orb,orbits))=0 then # we have found a new one AddSet(orbits,e); lengthsum:=lengthsum+Length(orb); Print("#I Length ",Length(orb)," found, total ",lengthsum," \n"); fi; while i>2 and l[i]>Length(sel[i]) do i:=i-2; l[i]:=l[i]+1; od; until l[i]>Length(sel[i]) or lengthsum=class; Print("#I class constructed up to ",e,"\n"); Print("number of orbits : ",Length(orbits),"\n"); return orbits; end; For curiosity, I used both routines for n=6 on a DECstation 5000. The first routine took 1700 seconds, while the second one finished after about 105 seconds. (Both routines ran in the initial 3MB memory). I hope this helps, Alexander Hulpke -- Alexander Hulpke, Lehrstuhl D f"ur |Ce po`eme est, en effet, divis'e en Mathematik, RWTH Aachen |cinq strophes successivement et respec- |tivement compos'ees de 3-1-4-1-5 vers, ahulpke@math.rwth-aachen.de | Jacques Bens: Le sonnet irrationnel From Joachim.Neubueser@Math.RWTH-Aachen.DE Tue Feb 22 15:00:00 1994 From: "Joachim Neubueser" Date: Tue, 22 Feb 94 15:00 +0100 Subject: Re: Computing in Beginning Undergraduate Algebra Dear Dr. Larson, Thank you for the paper copy of the notes for your students which I obtained a while ago. I also got hold of a copy of Gallian's book. Both address students at an earlier mathematical age, than our students are when entering our algebra course, but both impress me as carefully thought over. There are several details in your note, that I will remember for my teaching. e.g. the nice way to introduce the idea of conjugation as well as that of even and odd permutations by the sliding puzzles right at the beginning. Nevertheless I would like to comment on the GAP notes and suggest additions and/or alternatives. 1. My first observation is that you let the students use GAP only in strictly interactive mode. You provide even absolutely straightforward code as the one for finding the commutativity index as an appendix. I do not know what the situation with your students is, but here I would take it almost for granted that they all had some private encounter with some computing language, like Pascal or even Basic and hence they could write such a little double loop themselves. After all, the GAP language is so simple and so similar to Pascal - at least for this kind of level. But of course in a more general way , I would leave it to their own initiative to learn to do it if they do not know how to do it and I would at best offer a couple of extra instruction hours. Very bluntly, I would tell them that after all I also assume that they can hold a pencil, that they can read a textbook in English (or can even give a seminar talk in (some) English if necessary). I would object to spoonfeed them too much. 2. In detail then with just this question: The little routine simply runs through all pairs and tests commutativety. Of course introducing the notion of the centralizer and noting that conjugate elements have centralizers of the same order could be used to shorten the computation. Could one not use just this nice idea of looking at the commutativety index to motivate such notions? Or would this already go beyond the time you have for the course? 3. What I would try to do is to use GAP to introduce a greater variety of groups. I think one of the most important insights that a program system like GAP can help to give the student is that the theory of groups really is a theory about a vast set of different objects. There are the libraries of groups that come with the GAP system. Just letting the students look at some of these might be worthwhile, looking at the differences of the groups of the same order, i.e. to ask them how they could distinguish isomorphism types or e.g. ask for the different commutativity index of the different groups of order 60 or... . For this purpose it may be necessary to transform the list of AG - groups into a list of permutation groups, since the idea of a polycyclic presentation is too difficult at this level, but then this could be done by adding another appendix. I would be most interested to hear about any further teaching experiments that you will make, I think there is a lot to do in this line. With kind regards Joachim Neubueser From Volkmar.Felsch@Math.RWTH-Aachen.DE Thu Feb 24 16:55:00 1994 From: "Volkmar Felsch" Date: Thu, 24 Feb 94 16:55 +0100 Subject: Serious bug in Size function The purpose of this note is to warn you of a serious bug in the Size function which has been introduced in GAP 3.3. Because of a possible overflow in an uncontrolled variable of some C routine in the GAP kernel the Size function may return a wrong value for a finitely presented group (without any warning or evidence). Eamonn O'Brien from Canberra has sent us an example. We have no reason to believe that the Size function is faulty for any other kind of group. I have unfortunately introduced this bug when we tried to speed up the Size function for finitely presented groups and to extend the range of its applicability in version 3 release 3 of GAP. To the best of our knowledge, the Size function has been correct also for finitely presented groups for the releases of GAP preceding release 3 of version 3. The bug will be fixed in the next patch or release. For the time being you can use the the function Index( G, TrivialSubgroup( G ) ); which will practically do what the Size function for finitely presented groups did in version 3.3 (and hence be as efficient as that function was). Volkmar Felsch, Aachen From mikec@math.ubc.ca Mon Mar 7 16:48:00 1994 From: "Michael B. Cherkassoff" Date: Mon, 07 Mar 94 16:48 -0800 Subject: How to cite GAP? Hello. Can anybody advise me how to cite GAP in the paper. The best answer would be database entry for LaTex. Thank you. Michael. From Martin.Schoenert@Math.RWTH-Aachen.DE Tue Mar 8 08:12:00 1994 From: "Martin Schoenert" Date: Tue, 08 Mar 94 08:12 +0100 Subject: Re: How to cite GAP? Michael B. Cherkassoff wrote in his e-mail message of 1994/03/07 Can anybody advise me how to cite GAP in the paper. The best answer would be database entry for LaTex. Citing the manual is the right way to go. Here is an entry. [S+ 93] Martin Sch"onert et.al. GAP -- Groups, Algorithms, and Programming. Lehrstuhl D f"ur Mathematik, Rheinisch Westf"alische Technische Hochschule, Aachen, Germany, third edition, 1993. So a BibTeX entry for a quotation of the GAP manual should read: @string{ RWTH = "Rheinisch Westf{\accent127 a}lische Technische Hoch\-schule" } @string{ RWTHLDFM = "Lehrstuhl D f{\accent127 u}r Mathematik, Rheinisch Westf{\accent127 a}lische Technische Hoch\-schule" } @string{ RWTH-A = "Aachen, Germany" } @manual{Sch93, author = "Martin Sch{\accent127 o}nert and others", title = "{GAP} -- {Groups}, {Algorithms}, and {Programming}", year = "1993", edition = "third", organization = RWTHLDFM, address = RWTH-A, notes = "PAGES: 900", keywords = "groups; *; gap; manual" } If you are not using BibTeX, here is the bibliography entry produced by BibTeX. You can use this inside the bibliography environment of LaTeX. \newcommand{\etalchar}[1]{$^{#1}$} \bibitem[S{\etalchar{+}}93]{Sch93} Martin Sch{\accent127 o}nert et~al. \newblock {\em {GAP} -- {Groups}, {Algorithms}, and {Programming}}. \newblock Lehrstuhl D f{\accent127 u}r Mathematik, Rheinisch Westf{\accent127 a}lische Technische Hoch\-schule, Aachen, Germany, third edition, 1993. 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 jcbhrb@cerf.net Tue Mar 8 00:11:00 1994 From: "Jacob Hirbawi" Date: Tue, 08 Mar 94 00:11 -0800 Subject: possible bug in Eigenvalues(...) I may have run into a bug in calculating the eigenvalues of a representation. Here's what I was trying : -------------------------------------------------------------------------------- gap> data := CharTable("SL",2,13);; gap> rep := data.irreducibles[14]; [ 6, -6, E(13)+E(13)^3+E(13)^4+E(13)^9+E(13)^10+E(13)^12, E(13)^2+E(13)^5+E(13)^6+E(13)^7+E(13)^8+E(13)^11, -E(13)-E(13)^3-E(13)^4-E(13)^9-E(13)^10-E(13)^12, -2*E(13)-E(13)^2-2*E(13)^3-2*E(13)^4-E(13)^5-E(13)^6-E(13)^7-E(13)^8 -2*E(13)^9-2*E(13)^10-E(13)^11-2*E(13)^12, 0, 0, 0, 0, 0, 1, -1, 1, -1, 1, -1 ] #no problems for this class gap> Eigenvalues(data,rep,5); [ 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0 ] #this one has the problem; shouldn't the result be integers? gap> Eigenvalues(data,rep,6); [ 7/13, -7/13, 7/13, 6/13, 7/13, -7/13, 7/13, -7/13, 7/13, 6/13, 7/13, 6/13, -6/13, 6/13, 7/13, 6/13, 7/13, -7/13, 7/13, -7/13, 7/13, 6/13, 7/13, -7/13, 7/13, 6/13 ] #no problems for this class either gap> Eigenvalues(data,rep,7); [ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 ] -------------------------------------------------------------------------------- Jacob Hirbawi JcbHrb@CERF.net From Thomas.Breuer@Math.RWTH-Aachen.DE Tue Mar 8 09:36:00 1994 From: "Thomas Breuer" Date: Tue, 08 Mar 94 09:36 +0100 Subject: Re: possible bug in Eigenvalues(...) Dear Mrs. Forum, Jacob Hirbawi sent you a bug report today. > gap> data := CharTable("SL",2,13);; > gap> rep := data.irreducibles[14];; > gap> Eigenvalues(data,rep,6); > [ 7/13, -7/13, 7/13, 6/13, 7/13, -7/13, 7/13, -7/13, 7/13, 6/13, 7/13, 6/13, > -6/13, 6/13, 7/13, 6/13, 7/13, -7/13, 7/13, -7/13, 7/13, 6/13, 7/13, -7/13, > 7/13, 6/13 ] > > #this one has the problem; shouldn't the result be integers? Of course the multiplicities of eigenvalues should be integers. The problem here is a bug in the generic table of 'SL(2,q)' for odd 'q'. This will be fixed in the next version of GAP. For 'q' not too big, the tables of 'SL(2,q)' are also available as library tables (in ATLAS format), for example 'CharTable( "2.L2(13)" )' is the (correct) table of 'SL(2,13)'. Kind regards, and thanks to Jacob Hirbawi. Thomas Breuer (sam@math.rwth-aachen.de) From sl25@cus.cam.ac.uk Thu Mar 10 18:56:00 1994 From: "Steve Linton" Date: Thu, 10 Mar 94 18:56 +0100 Subject: Testing for the Symmetric (Alternating) group Has anyone implemented the standard algorithms for testing whether a permutation group is the full symmetric or alternating group? Or are they in the library somewhere I have't thought to look? Steve From dpb@a.cs.okstate.edu Thu Mar 17 09:09:00 1994 From: "D. Paul Benjamin" Date: Thu, 17 Mar 94 09:09 -0600 Subject: semigroups Hello. I have just acquired GAP, and apologize if this question has been dealt with previously. I need to compute structures on semigroups of partial 1-1 functions, e.g., Green's relations. GAP does not seem to have any of the relevant things I need for this. Has anyone implemented anything that would help, such as partial functions? If not, I'd like some feedback on my initial ideas for implementing this. At first reading, it appears that partial functions should be implemented as lists with holes, and a new domain type, something like "semigroups of partial 1-1 functions" needs to be constructed as a set of these lists, together with operations that compose partial functions, compute Green's relations, etc. I'll need to build several new domains, such as "Brandt semigroups" and "inverse semigroups". Once the semigroup stuff is implemented, then I can take advantage of GAP's group-theoretic abilities, as I am computing symmetries of various structures in Green's relations. Thanks in advance, Paul Benjamin From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Mar 18 11:11:00 1994 From: "Joachim Neubueser" Date: Fri, 18 Mar 94 11:11 +0100 Subject: semigroups Paul Benjamin asked about semigroups of partial 1-1 functions in GAP. It is correct that the present release (3.3) of GAP does not provide specific support for such structures, and I want to add that the plans for the next release do not include anything for such structures either. Therefore we see the plan, to use the possibilities of creating new domains using records as described in section 1.28 of ("About Defining New Domains") of the manual, as the only realistic present possibility. We have been asked several times in the GAP-forum, but also privately if we have plans to extend GAP to support structures that in one way or other generalize the notion of groups. Therefore I would like to use this letter in the GAP-forum to state clearly that in Aachen (for lack of manpower as much as for any other reason) we have no such plans in the foreseeable future. At the same time we will be open for discussing inclusion of such structures if other groups would do the work and we suggest that those, who consider any such ideas, use the GAP-forum to make contacts. In particular it might be discussed to which level of generality of such structures one should go. Joachim Neubueser From hwblist@machnix.mathematik.uni-stuttgart.de Sun Mar 20 19:07:00 1994 From: "Harald Boegeholz" Date: Sun, 20 Mar 94 19:07 +0100 Subject: How do I save variables in GAP? Hello, I'd like to know if there is a way to save the current state of GAP in a file, i.e., the contents of some or all variables. I am doing some lengthy calculations and would like to save the results for later use. Unfortunately, the printed representation of most objects is not enough to recreate the object. There already seems to be a function called Save which does what I want for the special case of a PQp record. How difficult would it be to implement a generic "Save" function? Thanks for any help. hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From sidki@alpha.mat.unb.br Fri Mar 18 12:03:00 1994 From: "Said Najati Sidki" Date: Fri, 18 Mar 94 12:03 -0300 Subject: algebra enumeration I would like to now about programs for enumeration of noncommutative algebras in finite characteristic. Thanks, Said Sidki From is@ime.usp.br Sat Mar 19 13:43:00 1994 From: "Imre Simon" Date: Sat, 19 Mar 94 13:43 -0300 Subject: RE: semigroups Dear Forum, Paul Benjamin asked about computing the Green relations for semigroups of partial 1-1 functions in gap. As far as I know there is no such package, but there are several softwares computing Green relations of semigroups of functions, none of them in gap. I can cite four such programs: automat - developed by Hansel and Champarnaud in Paris, they published a paper about it. Contact Georges Hansel for more details. tor - a program written by myself. It is in Turbo Pascal (it has been translated to C with the help of a utility program). Unfortunately, the program is written in Portuguese, the documentation is VERY scarce and also in portuguese. In any case it is available from me (AS IS). amore - a system developed in Aachen and Kiel. Contact Wolfgang Thomas for more information. automata - a Mathematica package developed by Klaus Stutner; the package is available from mathsource.wri.com in the Applications/Complexity directory, as item 0205-197 "Automata". There is also a version of tor, called lim, which computes the Green relations for semigroups of matrices over a particular finite semiring. Yours, Imre Simon From Martin.Schoenert@Math.RWTH-Aachen.DE Mon Mar 21 11:33:00 1994 From: "Martin Schoenert" Date: Mon, 21 Mar 94 11:33 +0100 Subject: Re: How do I save variables in GAP? Harald Boegeholz writes in his e-mail message of 1994/03/20 I'd like to know if there is a way to save the current state of GAP in a file, i.e., the contents of some or all variables. I am doing some lengthy calculations and would like to save the results for later use. Unfortunately, the printed representation of most objects is not enough to recreate the object. Unfortunately this is impossible right now. Only for some very special objects, such as PQp records. A generic save function is planned. It is moderately difficult, and needs support both from the kernel (to find all objects and save arbitrary objects) and from the library (to save complex objects, such as domains without saving their operations record). Hope you can wait till then. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From sl25@cus.cam.ac.uk Mon Mar 21 11:41:00 1994 From: "Steve Linton" Date: Mon, 21 Mar 94 11:41 +0100 Subject: Re: algebra enumeration > I would like to now about programs for enumeration of noncommutative > algebras in finite characteristic. > Thanks, Said Sidki > I don't know exactly what you want, but I have a program (the vector enumerator) which constructs matrix representations of finitely-presented algebras over GF(p) fro various p. It will be appearing as a share library in GAP 3.4 (out soon) and is incorporated into the MAGMA system recently released from Sydney. Contact me directly if yoiu want more details. Steve From caranti@volterra.science.unitn.it Mon Mar 21 15:49:00 1994 From: "A E Caranti" Date: Mon, 21 Mar 94 15:49 +0100 Subject: Saving a session Dear gap-forum, Harald Boegeholz writes: > I'd like to know if there is a way to save the current state of GAP in > a file, i.e., the contents of some or all variables. I am doing some > lengthy calculations and would like to save the results for later use. > Unfortunately, the printed representation of most objects is not > enough to recreate the object. Actually, this question arose in the forum already some time ago, and Martin gave a similar answer. There was something in the ensuing discussion (I cannot remember whether it was Werner Nickel or Joachim Neubueser who mentioned it) that I found very useful. Namely, one can use GNU 'screen' utility to save (screen's word for it is 'detach') a GAP session, say, and resume it exactly as it was later, even having logged out. This solution is not (power failure)- or (machine reboot)-proof, but it's a very useful tool and it's the best approximation I am aware of to a solution to Boegeholz's problem. All the best, Andreas Caranti --------------------------------------------------------------------------- A Caranti Office Phone ++39 461 881618 Dipartimento di Matematica Office Fax ++39 461 881624 Universit\`a degli Studi di Trento Home Phone (with answering machine) I-38050 Povo (Trento) ++39 461 916087 Italia Email (please UPDATE if necessary): caranti@science.unitn.it or: caranti@volterra.science.unitn.it From hwblist@machnix.mathematik.uni-stuttgart.de Tue Mar 22 00:33:00 1994 From: "Harald Boegeholz" Date: Tue, 22 Mar 94 00:33 +0100 Subject: Re: Saving a session > Date: 21 Mar 94 15:49 +0100 > From: A E Caranti > > Dear gap-forum, > > Harald Boegeholz writes: > > > I'd like to know if there is a way to save the current state of GAP in > > a file, i.e., the contents of some or all variables. I am doing some > > lengthy calculations and would like to save the results for later use. > > Unfortunately, the printed representation of most objects is not > > enough to recreate the object. > > Actually, this question arose in the forum already some time ago, and > Martin gave a similar answer. There was something in the ensuing > discussion (I cannot remember whether it was Werner Nickel or Joachim > Neubueser who mentioned it) that I found very useful. Namely, one can > use GNU 'screen' utility to save (screen's word for it is 'detach') a > GAP session, say, and resume it exactly as it was later, even having > logged out. Yes, thanks. I am already using screen. The problem is that we do have occasional power failures (once a month?). Another problem is that playing around with GAP can corrupt data structures. If you interrupt a lengthy calculation you can not be sure that the data structures are still consistent. So for playing around it would be very useful to be able to save the current state of GAP. I am looking forward to seeing the implementation of this in a future version of GAP. hwb -- Harald Boegeholz | hwb@mathematik.uni-stuttgart.de | os2a@info2.rus.uni-stuttgart.de From mjf@odin.math.nau.edu Tue Mar 22 09:51:00 1994 From: "Michael J. Falk" Date: Tue, 22 Mar 94 09:51 -0700 Subject: [no subject] Dear Friends: Does anyone on this list know of a facility for computation in a finite-dimensional Lie algebra, i.e. a subalgebra of gl(n,C)? Does gap have such capabilities? (To start with, how about finding (a basis for) the solvable radical of L?) Thanks in advance for your kind assistance! Yours truly, Mike Falk. From studgap@twi.tudelft.nl Wed Mar 23 11:54:00 1994 From: "Gap Students" Date: Wed, 23 Mar 94 11:54 +0100 Subject: AppendTo Dear Gap Forum, To be able to call an external executable, it's necessary to write information to a file. As far as I know, GAP offers the functions PrintTo and AppendTo. These functions both open a file, write the information and close it again (am I right?) So when the function AppendTo is used within a loop, writing in each cycle a small amount of information, the file is opened and closed again very often, consuming a huge amount of time. Is there a way to open a file once, write all the information using a loop, and close it again? I have thought of using strings. First, all the information is stored in a string (using Concatenation), after which the whole string is written to a file using PrintTo. It turns out that, at least when working under DOS, this is even slower than the first option. Erik Roijackers / Gap Students From Joachim.Neubueser@Math.RWTH-Aachen.DE Wed Mar 23 17:05:00 1994 From: "Joachim Neubueser" Date: Wed, 23 Mar 94 17:05 +0100 Subject: Re: Testing for the Symmetric (Alternating) group Steve Linton asked (already on March 10 - sorry): > Has anyone implemented the standard algorithms for testing whether a > permutation group is the full symmetric or alternating group? > Or are they in the library somewhere I have't thought to look? They are not in the library, sorry again. If somebody has implemented, them could you please tell, so that they might get included? Joachim Neubueser From jcbhrb@cerf.net Tue Mar 22 19:18:00 1994 From: "Jacob Hirbawi" Date: Tue, 22 Mar 94 19:18 -0800 Subject: Re: Lie algebras This may not be relevant to what you're trying to calculate, but I did write some GAP code to work with semisimple Lie algebras and their representations. The code is, to some extent, also setup to deal with Kak-Moody algebras; although I haven't pursued that too far yet. Here's a brief desciption: (1) The starting point is the Killing form matrix - same as Cartan matrix for ADE algebras, slightly different for the others. The code includes routines to generate these matrices for An,Bn,Cn,Dn,G2,F4,E6,E7,E8 as well as the affine and "twisted" versions of these. (2) From the matrix in (1) the Cartan matrix, root system, half of positive roots, adjoint rep, basic reps, ... and other standard structures derived. (For infinite root systems the calculations are stopped after a certain point). (3) For Lie algebras, the Weyl dimension formula is provided. (4) For Lie algebras, the weights and multiplicities of a represntation are calculated given its highest weight. (this uses Freudenthal's recursive formula). There is a slight amount of overlap of this code with parts of the Weyl package; the code is not well documented but it should make sense (I hope) to those familiar with the subject. I can e-mail it to anyone intereted. Jacob Hirbawi JcbHrb@CERF.net Below is a sample session : -------------------------------------------------------------------------------- # look at the Lie algebra g2 gap> G2 := WeylModule( Sg(2) ); # some info printed by the routine, can be disabled. (1) Killing Matrix [ [ 2, -3 ], [ -3, 6 ] ] (2) Cartan Matrix [ [ 2, -3 ], [ -1, 2 ] ] (3) Det of Cartan Matrix 1 (4) Positive Roots 6 (5) Coxeter Number 5 (6) Highest Root [ 3, 2 ] (7) Adjoint Rep [ 0, 1 ] (8) Rho [ 5, 3 ] true (9) Simple Dimensions [ 7, 14 ] true # output record rec( Rho := [ 5, 3 ], SimpleWeights := [ [ 2, 1 ], [ 3, 2 ] ], Dimension := function ( rep ) ... end, Weights := function ( rep ) ... end ) # find the dimeniosn of rep with highest weight [4,2] gap> G2.Dimension([4,2]); 2926 # find the weight and multiplicities of the rep highest weight [2,0] gap> G2.Weights([2,0]); Dimension 27 true rec( Weight := [ [ 4, 2 ], [ 3, 2 ], [ 2, 2 ], [ 3, 1 ], [ 2, 1 ], [ 1, 1 ], [ 2, 0 ], [ 0, 1 ], [ 1, 0 ], [ 0, 0 ], [ -1, 0 ], [ 0, -1 ], [ -2, 0 ], [ -1, -1 ], [ -2, -1 ], [ -3, -1 ], [ -2, -2 ], [ -3, -2 ], [ -4, -2 ] ], Multiplicity := [ 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 1, 1, 1, 1 ] ) -------------------------------------------------------------------------------- From short@jordan.murdoch.edu.au Thu Mar 24 15:46:00 1994 From: "Mark Short" Date: Thu, 24 Mar 94 15:46 +1000 Subject: Re: Lie algebras Mike Falk writes: > Does anyone on this list know of a facility for computation in a > finite-dimensional Lie algebra, i.e. a subalgebra of gl(n,C)? Does gap > have such capabilities? (To start with, how about finding (a basis for) > the solvable radical of L? I don't think GAP does any Lie algebra directly. However, I have written GAP code which can do a little bit of Lie algebra. The code does a very narrow range of things, and works only on free Lie algebras (of finite rank) over either a finite prime field, or the ring of integers. The only parts of the code that might be relevant to Mike are the function that constructs the Hall basis vectors of a given weight, and the collector (which is of limited capability). If you want to know more and/or see the code, write to me direct. Mark Short From Meinolf.Geck@Math.RWTH-Aachen.DE Wed Mar 23 18:25:00 1994 From: "Meinolf Geck" Date: Wed, 23 Mar 94 18:25 +0100 Subject: Re: Lie algebras Dear Forum, Mike Falk asked in an email, > Does anyone on this list know of a facility for computation in a > finite-dimensional Lie algebra, i.e. a subalgebra of gl(n,C)? Does gap > have such capabilities? (To start with, how about finding (a basis for) > the solvable radical of L?) Thanks. > I haven't checked this, but maybe the system LIE has already some built-in functions for working with Lie algebras? I myself have written a collection of programs in GAP for working with finite Weyl groups and Iwahori-Hecke algebras. Maybe I may add some more general comments based on the experience I made with those programs: The first question is the following: In which form to you want to enter your Lie algebra into the computer? Is it a list of n by n matrices which generate the algebra (as a Lie algebra)? If so, which fields of entries do you allow? You mention the complex numbers. How do you want to represent them? As a+bi where a,b are reals?; and then, what about the reals? In GAP there are the rationals and cyclotomic extensions of them, as well as all the finite fields. Maybe this is already sufficient for you. If so, then you can build up matrices from them and apply all the general operations for matrices. (The same question arose for the Weyl groups: In books they are either defined via a presentation or as a reflection group. But eventually, I chose to represent them as a permutation group on the root system because this made certain operations, like computing the length of an element, extremely efficient.) The second question is about the specific problem you mention (computing the solvable radical): Suppose you are given your Lie algebra in terms of generating matrices as above. Do you have, at least theoretically, an algorithm which does the job, taking those matrices as input? I don't remember exactly but I think the solvable radical is the radical of the Killing form. So, one could form various products of the generating matrices, thus building a vector space basis of the Lie algebra. Then one could set up the Gram matrix of the Killing form and compute its null space. (This will not be the best possible algorithm but it is one.) (Again, an example taken from the Weyl groups: There is a partial order on the elements of the group called the Bruhat order. An element w is bigger than an element v if you can find a reduced expression for w, as a word in the standard generators, such that v is obtained by omitting some factors in this expression. This definition is not suitable at all for computational purposes. So, one first has to look for better ways to decide this, and then the implementation as a program was easy.) The point that I am trying to make is the following: I am quite certain that it is possible to use GAP (or any other computer algebra system) to work with Lie algebras and write programs which solve specific problems. But one main problem, as it seems to me, is that of a good representation of the algebra (''good'' with respect to computational approaches); another problem is that of efficient algorithms. Best regards, Meinolf Geck From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Mar 24 13:19:00 1994 From: "Joachim Neubueser" Date: Thu, 24 Mar 94 13:19 +0100 Subject: INCOMING LIE? I am pleased to see Mike Falks question concerning Lie algebras in GAP answered from three sides in the forum. What about making some of the "private" routines generally available in the directory "incoming" that has been created for that purpose recently. (Apologies to those that have answered, I do not want to discourage answering in the GAP-forum by then *requesting* to do further work, it is just a *question*). Joachim Neubueser From sl25@cus.cam.ac.uk Thu Mar 24 11:50:00 1994 From: "Steve Linton" Date: Thu, 24 Mar 94 11:50 +0100 Subject: Multiplying transformations I have discoverd a useful trick for multiplying transformation represented as image liists in GAP. Since a number of people have been enquiring about this and related subjects I thought it might be appropriate to mention it here. The obvious way to multiply lits images1 and images2, returning a list imagesProd is something like imagesProd := []; for i in images1 do Add(imagesProd,images2[i]); od; However the same result can be achieved rather faster by imagesProd := images2{images1}; where the loop is provided by the kernel. Steve From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Mar 24 17:55:00 1994 From: "Joachim Neubueser" Date: Thu, 24 Mar 94 17:55 +0100 Subject: Re: Liealgebras (fwd) I have forwarded Mike Falk's question also to Arjeh Cohen at Eindhoven who is'nt a member of the GAP-forum. He sent me the appended interesting reply, which he allowed me to put into the GAP-forum. So here is some further information about computing in Lie algebras with GAP. Joachim Neubueser ====================================================================== > Date: Thu, 24 Mar 1994 15:33:32 +0100 > From: amc@win.tue.nl (Arjeh Cohen) > Dear Joachim, > > Here is my answer to Mike Falk's query: > > The kind of algorithms asked for are not in LiE, > BUT, as a start of the algorithms part of the ACELA > project, we are busy implementing the kind of algorithms > Mike Falk asked for. > > We know how to implement the solvable radical of a subalgebra > of gl(n,k). > If the underlying field has characteristic 0, then it is already done > in GAP: we just compute the radical of the Killing form. > We are busy implementing the general algorithm in GAP as well, > this is more work. > Willem de Graaf, at Eindhoven, is working on it, > and expects to have it ready within a few weeks from now. > > Thanks for keeping posting me the interesting GAP query. > > Arjeh M. Cohen From jcbhrb@cerf.net Thu Mar 24 21:09:00 1994 From: "Jacob Hirbawi" Date: Thu, 24 Mar 94 21:09 -0800 Subject: Re: INCOMING LIE? I've uploaded some of what I wrote. Hopefully some will find it helpful. Jacob Hirbawi JcbHrb@CERF.net From sl25@cus.cam.ac.uk Thu Mar 24 17:44:00 1994 From: "Steve Linton" Date: Thu, 24 Mar 94 17:44 +0100 Subject: Re: AppendTo > > To be able to call an external executable, it's necessary to write > information to a file. As far as I know, GAP offers the functions > PrintTo and AppendTo. These functions both open a file, write the > information and close it again (am I right?) So when the function > AppendTo is used within a loop, writing in each cycle a small amount > of information, the file is opened and closed again very often, > consuming a huge amount of time. > This is an especially bad problem under DOS, as UNIX gains the benefit of disk caching. > Is there a way to open a file once, write all the information using > a loop, and close it again? I don't believe so. > > I have thought of using strings. First, all the information is stored > in a string (using Concatenation), after which the whole string is > written to a file using PrintTo. It turns out that, at least when > working under DOS, this is even slower than the first option. > Better is to put all the information into a GAP list and then write it out in one go. If your external program can't handle the resulting [] and ,s then you may have to write a little filter to strip them out. Another trick is to put the file on a RAM disk. Steve From Martin.Schoenert@Math.RWTH-Aachen.DE Fri Mar 25 11:03:00 1994 From: "Martin Schoenert" Date: Fri, 25 Mar 94 11:03 +0100 Subject: Re: AppendTo Erik Roijackers writes in his e-mail message of 1994/03/23 To be able to call an external executable, it's necessary to write information to a file. As far as I know, GAP offers the functions PrintTo and AppendTo. These functions both open a file, write the information and close it again (am I right?) So when the function AppendTo is used within a loop, writing in each cycle a small amount of information, the file is opened and closed again very often, consuming a huge amount of time. This is correct. It is just barely tolerable under UNIX. Under TOS (on the Atari ST), it was impossible, because seeking to the end of the file took time proportional to the size of a file. So writing a file with lines took time ^2. I don't now whether this is true under DOS. He continues Is there a way to open a file once, write all the information using a loop, and close it again? Hmm, yes and no. In C you open a file, obtain a file pointer, and then use this to write to the file. Something like this is not possible in GAP. That means you *cannot* write something like file := OutputFile( "erwin" ); for i in [1..100] do PrintTo( file, Size( group[i] ), "\n" ); od; CloseFile( file ); We plan something like this, but not for the immediate future. But there is a hack, which may solve your problem. What you can do, is to put your loop in a simple function. Then you call this function from 'PrintTo'. I.e., do the following Dummy := function () for i in [1..100] do Print( Size( group[i] ), "\n" ); od; end; PrintTo( "erwin", Dummy() ); This makes use of the fact that when the arguments to 'PrintTo' are evaluated the current output file is the one opened by 'PrintTo', so everything that would usually go to '*stdout*' (i.e., the screen) is written to the file. This doesn't solve all problems, because you cannot interact with GAP while the output is computed and written to the file, but in many cases this is sufficient. He continues I have thought of using strings. First, all the information is stored in a string (using Concatenation), after which the whole string is written to a file using PrintTo. It turns out that, at least when working under DOS, this is even slower than the first option. In GAP 3.3 'Concatenation' has a ``small'' problem. It creates the output list as a list of characters (with each character taking 4 bytes) instead of as a string. So the reason why this is slower is probably because the string becomes so large that GAP has to do many garbage collections. You might want to try something like the following code. cache := ""; for i in [1..100] do Append( cache, String( Size( group[i] ) ), "\n" ); if 8192 < Length(cache) then AppendTo( "erwin", cache ); cache := ""; fi; od; Hope this helps, Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- 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 Mar 25 18:13:00 1994 From: "Steve Linton" Date: Fri, 25 Mar 94 18:13 +0100 Subject: Programs for LARGE permutation groups I have uploaded a file stamp.g (and covering note stamp.doc) to the pub/incoming directory on samson.math.rwth-aachen.de. They contain some routines for computing with large degree permutation groups. They should be usable up to degree 5 million or so with care (and enough RAM). The general idea is to avoid making a stabchain at all costs, and to avoid multiplying permutations whenever possible. They don't do anything incredibly clever, and they are not very polished, but I thought someone might have a use for them. Steve From studgap@twi.tudelft.nl Mon Mar 28 16:23:00 1994 From: "Gap Students" Date: Mon, 28 Mar 94 16:23 +0100 Subject: FiniteField limitations and [-operator Dear GAP-forum, We have come across the following limitation of GAP. We want to construct BCH codes. To do that, we need to compute in a finite field. For example, to construct a binary BCH code, with wordlength 19, GAP must find a primitive 19th root of unity, which is an element of GF(2^18), 18 being the multiplicative order of 2 modulo 19. But GAP limits the size of a finite field to 2^16. Will this limitation be removed in the near future, or is there another way to solve the problem? Secondly we would like to know if the "[" operator could be redefined for records, like "+", "-" and "^". It would be very useful if we could use commands like: word := Code[4]; # Where "Code" is a record containing a code. # "word" would become the fourth codeword We hope you can help. Erik Roijackers, Jasper Cramwinckel and Reinald Baart From Goetz.Pfeiffer@Math.RWTH-Aachen.DE Mon Mar 28 16:41:00 1994 From: "Goetz Pfeiffer" Date: Mon, 28 Mar 94 16:41 +0100 Subject: Re: FiniteField limitations and [-operator The Gap Students wrote in their letter of 28-Mar-94: > > Secondly we would like to know if the "[" operator could be redefined for > records, like "+", "-" and "^". It would be very useful if we could use > commands like: > > word := Code[4]; # Where "Code" is a record containing a code. > # "word" would become the fourth codeword > > We hope you can help. Record fields in GAP can be accessed via the '.' operator. This operator takes as his right operand the name of a record field. The name of the field can also be a parenthesized string, e.g, obj.("operations"); is a valid way to ask for the record field 'operations' of a record 'obj'. So it is possible to work with variable record filed names. Moreover, record field names can be numbers. A group 'g' with 4 generators, for instance, often has the record components 1 to 4 which contain the generators. So it is possible to get the second generator by the simple construction 'g.2'. The final point: if the name of the record field is a (small) integer then this integer can used as parenthesized recor field name - without transforming it into a string. So, if in you example, 'Code' is a record, containing the code words in the fields 1 to n, say, the it is for example possible to have constructions like the following, for i in [1..n] do Print(Code.(i), "\n"); od; which will print each word of the code on a single line. Goetz Pfeiffer. From Alexander.Hulpke@Math.RWTH-Aachen.DE Mon Mar 28 17:27:00 1994 From: "Alexander Hulpke" Date: Mon, 28 Mar 94 17:27 +0200 Subject: Re: FiniteField limitations and [-operator Dear GAP-Forum. Erik Roijackers, Jasper Cramwinckel and Reinald Baart asked: > GAP must find a primitive 19th root of unity, which is an element of > GF(2^18), 18 being the multiplicative order of 2 modulo 19. But GAP limits > the size of a finite field to 2^16. > Will this limitation be removed in the near future, or is there another > way to solve the problem? The next version of GAP will include code for arbitrary finite algebraic extensions of fields. This should solve your problem. Alexander Hulpke From wang@maths.uwa.edu.au Tue Mar 29 18:41:00 1994 From: "Jie Wang" Date: Tue, 29 Mar 94 18:41 +1000 Subject: GAP-Grape Limit for graphs Dear GAP-forum, I constructed a graph "gamma" with 1170 vertices, which is the Sp(4,8)-graph with 1-subspaces and isotropic 2-subspaces as its vertices and (a,b) is an edge iff IsSubspace(b,a) or IsSubspace(a,b). But when I calculate 'AutGroupGraph(gamma)', GAP showed that "n can't be less than 1 or more than 1024", and followed with many many error messages. I guess "n" is the number of the vertices of the graph. However, how can I get this automorphism group of the graph? Jie Wang From beals@sisters.cs.uoregon.edu Tue Mar 29 14:23:00 1994 From: "Robert Beals" Date: Tue, 29 Mar 94 14:23 -0800 Subject: IsFinite for matrix groups Dear Gap community, I have been working on a GAP implementation of an algorithm for testing whether or not a matrix group, given by a list of generators, is finite. The algorithm is described in ``Deciding finiteness of matrix groups in deterministic polynomial time,'' Laszlo Babai, Robert Beals, and Daniel Rockmore, Proceedings of ISSAC'93. I would like very much to test this program on some ``practical'' inputs. Unfortunately, while I have encountered many people who think that testing finiteness of a matrix group is a nice thing to be able to do, I know of nobody who actually wants it done. I urge anyone who has a use for testing matrix groups for finiteness to contact me. Sincerely, Robert Beals Dept. of Computer and Info. Science University of Oregon Eugene, OR 97403 beals@cs.uoregon.edu