From cohenj02 at tartarus.uwa.edu.au Sat Jan 1 07:34:58 2005 From: cohenj02 at tartarus.uwa.edu.au (Jonathan Cohen) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Metrics for large and small permutation groups. In-Reply-To: References: Message-ID: Hi Javaid and Forum, > So what is the interpretation of "large groups"? This requires a bit of terminology. Let G be a permutation group acting on a set X. A *base* for G is a finite sequence of points from X whose stabiliser in G is trivial. An *infinite family* of permutation groups is called *small base* if the minimal length of a base is polylogarithmic in the degree. What this means is that there are positive constants a and b such that each group G in the family of degree n admits a base of length a*log^b(n). If not, then the family is called *large base*. Examples: -- The symmetric groups are large base, since the minimal base length is n-1 -- The cyclic groups are small base, since every cyclic groups admits a bse of length 1 -- The non-alternating finite simple groups are small base (this follows from a result of cameron) The *primitive* large base groups are the subgroups of wreath products S_n wr S_m which contain (A_n)^m, where the wreath product is in its product action and the action of S_n is on k-element subsets of {1,2,...,n} - this follows from cameron's result. Liebeck later sharpened the result to show that every other primitive group admits a base of length at 9log(n). Praeger and Shalev have lifted this result to *qusiprimitive groups*, that is, groups all of whose minimal normal subgroups are transitive. Bamberg has lifted it to *innately transitive* groups, that is, groups which have at least one transitive minimal normal subgroup. As far as I am aware, the question for transitive groups (or broader classes) remains open. *Large* means *large base* and *small* means *small base*. One often abuses the definition and refers to individual groups as small/large when it is clear what infinite family they belong to. References: Peter J. cameron Finite permutation groups and finite simple groups. Bull. London Math. Soc. 13(1)1--22, 1981 Martin W. Liebeck. On minimal degrees and base sizes of primitive permutation groups. Arch. Math (basel), 43(1):11-15, 1984 Cheryl E. Praeger and Aner Shalev. Bounds on finite quasiprimitive permutation groups. J. Aust. Math. Soc., 71(2):243-258, 2001 John Bamberg. Bounds and quotient actions of innately transitive groups, to appear in the J. Aust. Math. Soc. Available from: http://www.maths.uwa.edu.au/~john.bam/research/inntrans.html Jon -- http://www.maths.uwa.edu.au/~cohenj02 From dfh at maths.warwick.ac.uk Sat Jan 1 11:49:52 2005 From: dfh at maths.warwick.ac.uk (Derek Holt) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Metrics for large and small permutation groups. In-Reply-To: References: Message-ID: <20050101114952.GA1225@maths.warwick.ac.uk> Dear GAP Forum Jonathan Cohen has helpfully provided a helpful and informative description of small and large base groups. But, since today is a holiday for the New Year, let me append a couple of quibbles! On Sat, Jan 01, 2005 at 03:34:58PM +0800, Jonathan Cohen wrote: > Hi Javaid and Forum, > > > So what is the interpretation of "large groups"? > > This requires a bit of terminology. Let G be a permutation group > acting on a set X. A *base* for G is a finite sequence of points from > X whose stabiliser in G is trivial. An *infinite family* of > permutation groups is called *small base* if the minimal length of a > base is polylogarithmic in the degree. What this means is that there > are positive constants a and b such that each group G in the > family of degree n admits a base of length a*log^b(n). If not, then > the family is called *large base*. > > Examples: > -- The symmetric groups are large base, since the minimal base length is > n-1 You have just said that "large base" applies to families of permutation groups rather than to individual groups, so presumably you mean that the family of symmetric groups { S_n | n in N } *is* small base. > -- The cyclic groups are small base, since every cyclic groups admits > a base of length 1 You have not specified a family of permutation groups here. The cyclic group generated by (1,2)(3,4,5) has no base of length 1 . > -- The non-alternating finite simple groups are small base (this > follows from a result of cameron) The non-alternating finite simple groups form a family of (isomorphism classes of) abstract groups rather than a family of permutation groups. Presumably you are saying here that the family of all equivalence classes of permutation representations of all non-alternating finite simple groups is a small base family? > The *primitive* large base groups are the subgroups of wreath products > S_n wr S_m which contain (A_n)^m, where the wreath product is in its > product action and the action of S_n is on k-element subsets of > {1,2,...,n} - this follows from cameron's result. Again, it is not immediately clear how to formulate the above statement in terms of families of groups. > Liebeck later sharpened the result to show that every other primitive > group admits a base of length at 9log(n). Praeger and Shalev have > lifted this result to *qusiprimitive groups*, that is, groups all of whose > minimal normal subgroups are transitive. Bamberg has lifted it to > *innately transitive* groups, that is, groups which have at least one > transitive minimal normal subgroup. > > As far as I am aware, the question for transitive groups (or broader > classes) remains open. *Large* means *large base* and *small* means > *small base*. One often abuses the definition and refers to individual > groups as small/large when it is clear what infinite family they > belong to. It seems to me, on balance, that this particular abuse is a bad idea and leads to confusion. Happy New Year, Derek Holt. > References: > > Peter J. cameron Finite permutation groups and finite simple groups. > Bull. London Math. Soc. 13(1)1--22, 1981 > > Martin W. Liebeck. On minimal degrees and base sizes of primitive > permutation groups. Arch. Math (basel), 43(1):11-15, 1984 > > Cheryl E. Praeger and Aner Shalev. Bounds on finite quasiprimitive > permutation groups. J. Aust. Math. Soc., 71(2):243-258, 2001 > > John Bamberg. Bounds and quotient actions of innately transitive > groups, to appear in the J. Aust. Math. Soc. Available from: > http://www.maths.uwa.edu.au/~john.bam/research/inntrans.html > > Jon > > -- > http://www.maths.uwa.edu.au/~cohenj02 > > > > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum From cohenj02 at tartarus.uwa.edu.au Sat Jan 1 19:52:25 2005 From: cohenj02 at tartarus.uwa.edu.au (Jonathan Cohen) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Metrics for large and small permutation groups. In-Reply-To: <20050101114952.GA1225@maths.warwick.ac.uk> References: <20050101114952.GA1225@maths.warwick.ac.uk> Message-ID: Hi Forum, Let me try and clear up some of Derek Holt's concerns, now that I am over my "holiday cheer" :) > You have just said that "large base" applies to families of permutation groups > rather than to individual groups, Yes, sorry, I had slipped into abusing the definition already. >so presumably you mean that the family of > symmetric groups { S_n | n in N } *is* small base. It is large base. > > -- The cyclic groups are small base, since every cyclic groups admits > > a base of length 1 > > You have not specified a family of permutation groups here. > The cyclic group generated by (1,2)(3,4,5) has no base of length 1 . Yes, a silly slip on my part, I should have specified the cyclic groups that act regularly (or all semiregular groups for that matter). > > -- The non-alternating finite simple groups are small base (this > > follows from a result of cameron) > > The non-alternating finite simple groups form a family of (isomorphism > classes of) abstract groups rather than a family of permutation groups. > Presumably you are saying here that the family of all equivalence classes of > permutation representations of all non-alternating finite simple groups > is a small base family? I mean the family of all permutation representations of all non-alternating finite simple groups. I am not quite sure how you are taking the equivalence classes. The reading {G | G is a permutation representation of H} could lead to trouble, since the minimal base length of a member of the class will most likely vary according to the representation. > > The *primitive* large base groups are the subgroups of wreath products > > S_n wr S_m which contain (A_n)^m, where the wreath product is in its > > product action and the action of S_n is on k-element subsets of > > {1,2,...,n} - this follows from cameron's result. > > Again, it is not immediately clear how to formulate the above statement > in terms of families of groups. One way is to generate lots of families by fixing k and letting n and m vary (so one family for each choice of k). One can show that such a family is large base. However, I cannot see how to do it without fixing k since, in that case, we may pick (for example) the subfamily where k=n-1. I omitted an interesting sidenote in my previous message. All of the cited results require CFSG, however, Pyber provided a completely elementary proof for the case of doubly transitive permutation groups. His paper is: L. Pyber. On the orders of doubly transitive permutation groups, elementary estimates. J. Combin. Theory Ser. A, 62(2):361-366, 1993. Jon -- http://www.maths.uwa.edu.au/~cohenj02 From Dursun.Bulutoglu at afit.edu Sun Jan 2 02:38:59 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] An Equation over a finite filed involving one of the primitive elements. Message-ID: <039A0DCC3D66EE4AB9AF11E119287F150183F2@ms-afit-04.afit.edu> Dear Gap Forum, I would like to first thank you for your help before. Now I am trying to solve the following problem: Let x be a primitive element of GF(p^n) for n>=0. Then x can not satisfy an equation of the form: x^r-A((p^n-1)/4)x+A((p^n-1)/4)-1=0 where 0= > Dear Gap Forum, > I would like to first thank you for your help before. > Now I am trying to solve the following problem: > > Let x be a primitive element of GF(p^n) for n>=0. > Then x can not satisfy an equation of the form: > >x^r-A((p^n-1)/4)x+A((p^n-1)/4)-1=0 where 0=A is a non-zero constant in GF(p^n). > > Is c=A((p^n-1)/4) a constant, so you are trying to solve x^r-c*x+c-1=0 in GF(p^n)? That is right. I should have stated the problem like that as A can be any constant. Sorry about that. So now the problem is: If x is a primitive element in GF(p^n) it can not solve an equation of the form x^r-c*x+c-1=0 in GF(p^n) for any non-zero constant c. Dursun. >Observe that r=0 or r=p^n-1 implies x=1. I would greatly appreciate it >if someone could give me an insight how this problem could be solved. >Dursun. >_______________________________________________ >Forum mailing list >Forum@mail.gap-system.org >http://mail.gap-system.org/mailman/listinfo/forum > > > From LindnerW at t-online.de Sun Jan 2 10:44:16 2005 From: LindnerW at t-online.de (Wolfgang Lindner) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] graph-theoretic routines References: <039A0DCC3D66EE4AB9AF11E119287F150183F2@ms-afit-04.afit.edu> Message-ID: <1Cl3Dc-0wGRUm0@fwd00.sul.t-online.com> Dear GAP-list, I think about to use GAP for teaching some graph-theoretic algorithms like Dijkstra, Prim or Ford-Fulkerson. In Leonard H. Soicher's GRAPE I found appropriate data structures/constructors for graphs, but (as far as I could see) no code for those algos. Im use WinXP, so I can't use xgap for graphical representations, too. Instead I will use the attached Java-applett. (The data structure there is Mathematica code compatible. I know about Skiena's Combinatorica.m but it is not possible for me to use Mathematica in class.) My question is: are there some experiences or small prototypical GAP-code available for some of the algo's above? Any hints would be very welcome. Sincerly with best whishes for 2005 Wolfgang Lindner -- Staedtisches Gymnasium, Stockhauserstr. 13, D-42929 Wermelskirchen Homepage: http://www.lo-net.de/home/wolfgangLindner -------------- next part -------------- From mschaps at macs.biu.ac.il Sun Jan 2 11:08:03 2005 From: mschaps at macs.biu.ac.il (Malka Schaps) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] hypertext index to group presentations and char. tables Message-ID: An index to the 1000 solvable groups of order up to 100 is available at: http://www.cs.biu.ac.il/~mschaps/DATA/database.html. Mary Schaps From Guillermo.Moreno-Socias at math.uvsq.fr Sun Jan 2 16:50:51 2005 From: Guillermo.Moreno-Socias at math.uvsq.fr (Guillermo MORENO-SOCIAS) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Galois group In-Reply-To: <20041206102010.GA92696@math.uvsq.fr> References: <20041206102010.GA92696@math.uvsq.fr> Message-ID: <20050102165051.GA34242@math.uvsq.fr> On Mon, Dec 06, 2004 at 11:20:10AM +0100, Guillermo MORENO-SOCIAS wrote: > I am not (yet) familiar with Gap4. I have the following question > from a friend: How to compute the Galois group of X^8-2? It seems to > be an order 16 group, but which one? It is not D_8. Although rather late, I wish to thank all those who kindly answered this question. Happy New Year! Guillermo Moreno-Socias From vdabbagh at math.carleton.ca Tue Jan 4 07:36:03 2005 From: vdabbagh at math.carleton.ca (Vahid Dabbaghian-Abdoly) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Character values on Sylow subgroups Message-ID: Dear Gap Forum, Using the Gap character table library, is it possible to compute character values of a group G on a Sylow subgroup of G? In particular I am looking for character values of the groups "L4(4)" and "L4(5)" on Sylow 2-subgroup and Sylow 5-subgroup, respectively. Regards, Vahid From Dursun.Bulutoglu at afit.edu Tue Jan 4 22:56:23 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Frequencies in a list Message-ID: <039A0DCC3D66EE4AB9AF11E119287F15193A1F@ms-afit-04.afit.edu> A non-text attachment was scrubbed... Name: not available Type: multipart/alternative Size: 245 bytes Desc: not available Url : http://mail.gap-system.org/pipermail/forum/attachments/20050104/4f9fcaed/attachment.bin From rm43 at evansville.edu Wed Jan 5 00:23:38 2005 From: rm43 at evansville.edu (Robert F. Morse) Date: Fri Apr 8 15:25:46 2005 Subject: [GAP Forum] Frequencies in a list In-Reply-To: <039A0DCC3D66EE4AB9AF11E119287F15193A1F@ms-afit-04.afit.edu> References: <039A0DCC3D66EE4AB9AF11E119287F15193A1F@ms-afit-04.afit.edu> Message-ID: <41DB338A.8040805@evansville.edu> Bulutoglu Dursun A Civ AFIT/ENC wrote: > Dear Gap Forum; > I was wondering whether there is a function in GAP that does the > following: > > Input: a list of numbers > Output: the numbers in the list sorted from small to large and > the frequencies at which they appear in the list. > Dursun. Dear Dursun, Use the Collected command (see, Chapter 21.20 of the reference manual). Example: gap> Collected([1,1,1,1,1,1,2,2,-1,-1]); [ [ -1, 2 ], [ 1, 6 ], [ 2, 2 ] ] Regards, Robert F. Morse From thomas.breuer at math.rwth-aachen.de Thu Jan 6 08:58:23 2005 From: thomas.breuer at math.rwth-aachen.de (Thomas Breuer) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Character values on Sylow subgroups Message-ID: Dear GAP Forum, Vahid Dabbaghian-Abdoly wrote > Using the Gap character table library, is it possible to > compute character values of a group G on a Sylow subgroup of G? > In particular I am looking for character values of the groups > "L4(4)" and "L4(5)" on Sylow 2-subgroup and Sylow 5-subgroup, > respectively. If I understand the question right then the aim is to restrict characters of G to the character table of a Sylow p-subgroup P of G. If the character table of P is needed but not available in the GAP Character Table Library --which is the case for the two groups G in question-- then first one has to produce the character table of P, presumably from a representation of P. As has been mentioned in the answer by Mowsey to the GAP Forum, computing the character table of a moderately sized p-group with GAP's standard methods is easy. The problem is then to determine the class fusion between the table that was computed from P and the library table of G. The combinatorial approach used by the GAP function `PossibleClassFusions' is not suitable for this situation, and as far as I know, no description of the class representatives in the library table of G in terms of standard generators of G is available. What one can try in this situation is either to compute the character table of G from the group (which in this case requires extensions of the standard methods for being efficient) or to divide the problem into smaller problems. If one is interested in restricting characters of G = L4(4) to its Sylow 2-subgroup P then using the intermediate group N_G(P) solves the problem. Here is a GAP session for this example (which needed less than a minute on my computer). gap> g:= PSL(4,4);; gap> s:= SylowSubgroup( g, 2 );; gap> n:= Normalizer( g, s );; gap> tg:= CharacterTable( "L4(4)" );; gap> ts:= CharacterTable( s );; gap> tn:= CharacterTable( n );; gap> sfusn:= FusionConjugacyClasses( ts, tn );; gap> nfusg:= PossibleClassFusions( tn, tg );; gap> sfusg:= Set( List( nfusg, map -> map{ sfusn } ) );; gap> Length( sfusg ); 1 Now for example the decomposition of the first nontrivial irreducible character of G into irreducibles of P can be computed as follows. gap> chi:= Irr( tg )[2]; Character( CharacterTable( "L4(4)" ), [ 84, 20, 4, 21, 21, 9, 6, 4, 0, -1, -1, 4, 4, -1, 5, 5, 5, 5, 1, 2, 0, 0, 0, 0, -1, -1, 0, 0, 1, 1, 4, 4, 4, 4, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 ] ) gap> rest:= chi{ sfusg[1] }; [ 84, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 4, 4, 4, 4, 4, 4, 20, 4, 4, 4, 4, 4, 4, 20, 4, 4, 4, 4, 4, 4, 20, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 20, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 20, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 20, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 20, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 20, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0 ] gap> MatScalarProducts( ts, Irr( ts ), [ rest ] ); [ [ 3, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 ] ] (For G = L4(5) and p = 5, the only difference is that the class fusion is not uniquely determined but only unique up to table automorphisms of the character tables in question; one ends up with a list of 16 equivalent possibilities.) All the best, Thomas From joyner.david at comcast.net Thu Jan 6 13:43:01 2005 From: joyner.david at comcast.net (joyner.david@comcast.net) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Finding roots of a polynomial Message-ID: <010620051343.20217.41DD40650001D8EA00004EF922070032010B07900E0BD29D0A02970106@comcast.net> ++++++++++++++++++++++++++++++++++++++++++++++++++ Here's an example p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2; x:=X(F,1); f:=x^r-c*x+c-1; F_f:=FieldExtension( F, f ); alpha:=RootOfDefiningPolynomial(F_f); #alpha is the desired root. ########## Another solution: RootOfPolynomial:=function(f,R) local F0,Ff,a; F0:=CoefficientsRing(R); Ff:=FieldExtension(F0,f); a:=RootOfDefiningPolynomial(Ff); return a; end; # example: p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2; x:=X(F,1); f:=x^r-c*x+c-1; R:=PolynomialRing( F, [ x ]); a:=RootOfPolynomial(f,R); # check: Value(f,[x],[a]); Hope this helps. +++++++++++++++++++++++++++++++++++++++++++++++++++ Bulutoglu Dursun A Civ AFIT/ENC wrote: > Dear Gap Forum, > I would like to first thank you for your help before. > Now I am trying to solve the following problem: > Solve an equation of the form x^r-c*x+c-1=0 in GF(p^n) for any non-zero constant c. > > Dursun. > Dear Gap Forum; > I was wondering whether there is a function in GAP that does the > following: > > Input: a list of numbers > Output: the numbers in the list sorted from small to large and > the frequencies at which they appear in the list. > Dursun. > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum From mmarco at unizar.es Thu Jan 6 13:58:43 2005 From: mmarco at unizar.es (mmarco@unizar.es) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] check ideal membership through singular interface Message-ID: <1105019923.41dd44139ddfa@webmail.unizar.es> We need to check if certains polynomials (that we construct with gap) are in a given ideal or not. So i used the singular interface to compute groebner basis of the ideal and the normal form of these ideals with respect to it. But the problems when i need to study the output back in gap: i am unable to check if the output is zero or not. Even when the result is zero, (and gap shows it as zero), it still considers it as a diferent object. Is there any way to convert this output to regular gap polynomials? From frank.luebeck at math.rwth-aachen.de Thu Jan 6 16:09:27 2005 From: frank.luebeck at math.rwth-aachen.de (Frank Luebeck) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] An Equation over a finite field involving one of the primitive elements. Message-ID: On Sat, 1 Jan 2005, Bulutoglu Dursun A Civ AFIT/ENC wrote: >> x^r-A((p^n-1)/4)x+A((p^n-1)/4)-1=0 where 0=> A is a non-zero constant in GF(p^n). >> >> > Is c=A((p^n-1)/4) a constant, so you are trying to solve x^r-c*x+c-1=0 > in GF(p^n)? > > That is right. I should have stated the problem like that as A can be > any constant. Sorry about that. > So now the problem is: If x is a primitive element in GF(p^n) it can not > solve an equation of the form x^r-c*x+c-1=0 in GF(p^n) for any non-zero > constant c. Dear Dursun, This statement is not true. Try the following in GAP: x := Z(3^2); Order(x); c := Z(3^2)^3; x^7 - c*x + c-1; You could use GAP for checking such statements in some examples. Here the function findexample := function(p, n) local y, primelts, z, i, r, c, pol, test; y := Indeterminate(GF(p^n), 1); primelts := Filtered(GF(p^n), x-> Order(x)=p^n-1);; for r in [0..p^n-1] do z := Z(p^n); for i in [0..p^n-2] do c := z^i; pol := y^r - c*y +(c-1); test := Filtered(primelts, a-> IsZero(Value(pol, a))); if Length(test) > 0 then Print("r=",r," c=",c," #solutions=",Length(test), "(",test,")\n"); fi; od; od; end; gives you plenty of further counterexamples to your statement. Best regards, Frank /// Dr. Frank L?beck, Lehrstuhl D f?r Mathematik, Templergraben 64, /// \\\ 52062 Aachen, Germany \\\ /// E-mail: Frank.Luebeck@Math.RWTH-Aachen.De /// \\\ WWW: http://www.math.rwth-aachen.de/~Frank.Luebeck/ \\\ -------------- next part -------------- From joyner.david at comcast.net Fri Jan 7 11:35:48 2005 From: joyner.david at comcast.net (joyner.david@comcast.net) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Finding roots of a polynomial Message-ID: <010720051135.10007.41DE74140003B26C0000271722058844840B07900E0BD29D0A02970106@comcast.net> Dear GAP Forum: Frank Luebeck gave one answer to Dursun's question. Here is an answer to a related, more general question. ++++++++++++++++++++++++++++++++++++++++++++++++++ Here's an example p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2; x:=X(F,1); f:=x^r-c*x+c-1; F_f:=FieldExtension( F, f ); alpha:=RootOfDefiningPolynomial(F_f); #alpha is the desired root. ########## Another solution: RootOfPolynomial:=function(f,R) local F0,Ff,a; F0:=CoefficientsRing(R); Ff:=FieldExtension(F0,f); a:=RootOfDefiningPolynomial(Ff); return a; end; # example: p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2; x:=X(F,1); f:=x^r-c*x+c-1; R:=PolynomialRing( F, [ x ]); a:=RootOfPolynomial(f,R); # check: Value(f,[x],[a]); # example where F is not finite: F:=Rationals; x:=X(F,1); f:=x^2+x+1; R:=PolynomialRing( F, [ x ]); a:=RootOfPolynomial(f,R); # check: Value(f,[x],[a]); Hope this helps. +++++++++++++++++++++++++++++++++++++++++++++++++++ Bulutoglu Dursun A Civ AFIT/ENC wrote: > Dear Gap Forum, > I would like to first thank you for your help before. > Now I am trying to solve the following problem: > Solve an equation of the form x^r-c*x+c-1=0 in GF(p^n) for any non-zero constant c. > > Dursun. > Dear Gap Forum; > I was wondering whether there is a function in GAP that does the > following: > > Input: a list of numbers > Output: the numbers in the list sorted from small to large and > the frequencies at which they appear in the list. > Dursun. > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum From Dursun.Bulutoglu at afit.edu Mon Jan 10 02:04:14 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem Message-ID: <039A0DCC3D66EE4AB9AF11E119287F15193CFE@ms-afit-04.afit.edu> A non-text attachment was scrubbed... Name: not available Type: multipart/alternative Size: 668 bytes Desc: not available Url : http://mail.gap-system.org/pipermail/forum/attachments/20050109/e103bf21/attachment.bin From beick at tu-bs.de Mon Jan 10 16:18:55 2005 From: beick at tu-bs.de (Bettina Eick) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] reza orfi-p group with some propertise In-Reply-To: <20041231175912.69255.qmail@web53402.mail.yahoo.com> Message-ID: Dear GAP Forum, Dear Reza Orfi, the group enclosed below is of the type you want to have, I think. Also enclosed below is a short GAP programm which can be used to find groups of your desired type. It is based on the ANUPQ share package which can be used to list p-groups systematically. Best wishes, Bettina ############################################################################# A group of order 3^7 with the following polycyclic presentation: g1 ^ 3 = id g2 ^ 3 = id g3 ^ 3 = g6^2*g7^2 g4 ^ 3 = g7^2 g5 ^ 3 = g7 g6 ^ 3 = id g7 ^ 3 = id g2 ^ g1 = g2*g3 g3 ^ g1 = g3*g4 g3 ^ g2 = g3*g5 g4 ^ g1 = g4*g6 g4 ^ g2 = g4*g6 g4 ^ g3 = g4*g7^2 g5 ^ g1 = g5*g6*g7 g5 ^ g2 = g5*g6*g7^2 g5 ^ g3 = g5*g7^2 g6 ^ g1 = g6*g7 g6 ^ g2 = g6*g7^2 Then G' = Phi(G) = < g3, .., g7 >, Z(G) = < g4 g5^2 g6 > is cyclic of order 9, and the coclass of G is 2. ############################################################################# RequirePackage("anupq"); CoclassPGroup := function( G ) return Length(Factors(Size(G))) - Length(LowerCentralSeries(G))+1; end; TryPrime := function(p) local i, todo, news, H, desc, K; todo := [AbelianGroup([p,p])]; i := 2; while true do i := i+1; Print("start layer ",i," with ",Length(todo)," groups \n"); news := []; for H in todo do if CoclassPGroup(H) = 1 then desc := PqDescendants( H : Stepsize := [1,2] ); desc := Filtered(desc,x->Index(x,DerivedSubgroup(x))=p^2); for K in desc do if AbelianInvariants(Center(K)) = [p^2] and CoclassPGroup(K) = 2 then return K; fi; od; Append(news, Filtered( desc, IsCapable )); Print("\n"); fi; if CoclassPGroup(H) = 2 then desc := PqDescendants( H : Stepsize := 1 ); desc := Filtered(desc, x->Index(x,DerivedSubgroup(x))=p^2); for K in desc do if AbelianInvariants(Center(K)) = [p^2] then return K; fi; od; Append(news, Filtered( desc, IsCapable )); Print("\n"); fi; od; todo := StructuralCopy(news); if Length(todo) = 0 then return; fi; od; end; From Dursun.Bulutoglu at afit.edu Mon Jan 10 18:50:19 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem Message-ID: <039A0DCC3D66EE4AB9AF11E119287F152380CD@ms-afit-04.afit.edu> Dear GAP Forum: In the below problem there was an error in the statement The following is the corrected version of the problem: Let Z_p be the finite field with p>7 elements. Let A be a subset of Z_p^*={1,2,3,...p-1} with (p-1)/2 elements. Let A=A_1UA_2 and the intersection between A_1 and A_2 be the empty set. Furthermore A_1={y_1, y_1+1, y_1+2 ... y_1+s_1} A_2={y_2, y_2+1, y_2+2 ... y_2+s_2} where s_1+s_2+2=(p-1)/2 For any non-zero constant c in Z_p let cA={c*a_1,c*a_2, ..., c*a_(p-1)/2} where A={a_1,a_2,...a_(p-1)/2}=A_1UA_2 Assume that for some nonzero c' (p-1)/2>=|c'A intersect A|>=(p-3)/2 then show that c' has to be +1 or -1 in Z_p. I thank you for your attention. Dursun. _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum From Dursun.Bulutoglu at afit.edu Tue Jan 11 20:43:10 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem simplified Message-ID: <039A0DCC3D66EE4AB9AF11E119287F152381E0@ms-afit-04.afit.edu> Dear Gap Forum: Dear GAP Forum; I reduced my problem to the following simpler problem: Let Z_p={0,1,2,...p-1} be the finite field with p elements and x be a primitive element. Also let A={1,2,3,...,(p-1)/2} and B={1,x,x^2,...,x^(p-3)/2} be subsets of Z_p^* then A can not be equal to B for p>7. I was wondering if you have any ideas how this could be solved. Thanks in advance. Dursun. From jdixon at math.carleton.ca Tue Jan 11 22:15:50 2005 From: jdixon at math.carleton.ca (John Dixon) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum]re: A problem simplified In-Reply-To: <039A0DCC3D66EE4AB9AF11E119287F152381E0@ms-afit-04.afit.edu> References: <039A0DCC3D66EE4AB9AF11E119287F152381E0@ms-afit-04.afit.edu> Message-ID: <41E45016.1010808@math.carleton.ca> Bulutoglu Dursun A Civ AFIT/ENC wrote: > Dear GAP Forum; > I reduced my problem to the following simpler problem: > Let Z_p={0,1,2,...p-1} be the finite field with p elements and x > be a primitive element. > Also let A={1,2,3,...,(p-1)/2} and B={1,x,x^2,...,x^(p-3)/2} be > subsets of Z_p^* then A can not be equal to B for p>7. > I was wondering if you have any ideas how this could be solved. Summing the elements in A gives (p^2-1)/4 = -1/4 and summing the elements in B gives (x^((p-1)/2)-1)/(x-1) = -2/(x-1) since x is a quadratic nonresidue. Thus A = B would imply x = 9 which is impossible since a primitive root (for p > 2) cannot be a square. John D. Dixon From costanti at science.unitn.it Tue Jan 11 22:26:25 2005 From: costanti at science.unitn.it (Marco Costantini) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem simplified In-Reply-To: <039A0DCC3D66EE4AB9AF11E119287F152381E0@ms-afit-04.afit.edu> References: <039A0DCC3D66EE4AB9AF11E119287F152381E0@ms-afit-04.afit.edu> Message-ID: <200501112326.25224.costanti@science.unitn.it> Dear Dursun Bulutoglu, try the following code: for p in [ 3, 5, 7, 11, 13, 17, 19, 23, 29 ] do F := GaloisField( p ); x := PrimitiveRoot( F ); u := One( F ); A := List( [1..(p-1)/2], a -> u*a ); B := List( [0..(p-3)/2], a -> x^a ); Print (p, " ", Set(A) = Set(B), "\n" ); od; It produces: 3 true 5 true 7 true 11 false 13 false 17 false 19 false 23 false 29 false Best regards, Marco Costantini On Tuesday 11 January 2005 21:43, Bulutoglu Dursun A Civ AFIT/ENC wrote: > I reduced my problem to the following simpler problem: > Let Z_p={0,1,2,...p-1} be the finite field with p elements and x > be a primitive element. > Also let A={1,2,3,...,(p-1)/2} and B={1,x,x^2,...,x^(p-3)/2} be > subsets of Z_p^* then A can not be equal to B for p>7. > I was wondering if you have any ideas how this could be solved. From gapforum at mowsey.org Tue Jan 11 23:52:31 2005 From: gapforum at mowsey.org (Mowsey) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem simplified Message-ID: <200501112357.j0BNvYxt017851@gap-system.org> I looked over John D. Dixon's solution and Marco Costantini's code, and noticed that the solution suggested p=7 should not work while the code indicated it did. There was a tiny error in the solution, but it can be easily fixed: For A={1,2,3,...,(p-1)/2}, Sum(A) = ( (1 + (p-1)/2)*(p-1)/2 ) / 2 = (p^2-1)/8. Previously the result was reported as (p^2-1)/4. When the sum is taken mod p, one gets Sum(A) = -1/8. The argument continues then as Sum(B) = (x^( (p-3)/2 + 1) - 1) / (x-1) = ( x^( (p-1)/2 ) - 1 ) / ( x - 1 ) and since x has order p-1, this is = (-1 - 1)/(x-1) = -2/(x-1). If A=B, then Sum(A)=Sum(B) and -1/8 = -2/(x-1), so x-1=16 and x=17. Previosuly the conclusion had been x=9 which was a contradiction, but no longer. The method can be continued however to finish. We consider Sum(A^3) = 1^3 + 2^3 + ... + ((p-1)/2)^3 = (p^2-1)^2/64 = 1/64 mod p. Sum(B^3) = 1^3 + x^3 + x^6 + ... x^(((p-3)/2)^3) = ( (x^3)^((p-1)/2) - 1 ) / (x^3 - 1) = ((-1)^3 - 1)/(x^3 - 1) = -2/(x^3-1). Equating Sum(A^3)=Sum(B^3), we get 1/64 = -2/(x^3-1) and x^3 - 1 = -128 and x^3 = -127. Hence if p is such that A = B, then x = 17 mod p and x^3 = -127 mod p. This just says 17^3 = -127 mod p, so p divides 5040 = 2^4*3^2*5*7, and p can only be 2, 3, 5, or 7. > I reduced my problem to the following simpler problem: > Let Z_p={0,1,2,...p-1} be the finite field with p elements and x > be a primitive element. > Also let A={1,2,3,...,(p-1)/2} and B={1,x,x^2,...,x^(p-3)/2} be > subsets of Z_p^* then A can not be equal to B for p>7. > I was wondering if you have any ideas how this could be solved. From Dursun.Bulutoglu at afit.edu Wed Jan 12 18:38:24 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem simplified Message-ID: <039A0DCC3D66EE4AB9AF11E119287F152382A6@ms-afit-04.afit.edu> Thank you very much for this solution. I thought about summing the elements in A and B and taking the products of elements in A and B but not summing the cubes of the elements in A and B. Dursun. -----Original Message----- From: forum-bounces@gap-system.org [mailto:forum-bounces@gap-system.org] On Behalf Of Mowsey Sent: Tuesday, January 11, 2005 6:53 PM To: Bulutoglu Dursun A Civ AFIT/ENC; forum@gap-system.org Subject: Re: [GAP Forum] A problem simplified I looked over John D. Dixon's solution and Marco Costantini's code, and noticed that the solution suggested p=7 should not work while the code indicated it did. There was a tiny error in the solution, but it can be easily fixed: For A={1,2,3,...,(p-1)/2}, Sum(A) = ( (1 + (p-1)/2)*(p-1)/2 ) / 2 = (p^2-1)/8. Previously the result was reported as (p^2-1)/4. When the sum is taken mod p, one gets Sum(A) = -1/8. The argument continues then as Sum(B) = (x^( (p-3)/2 + 1) - 1) / (x-1) = ( x^( (p-1)/2 ) - 1 ) / ( x - 1 ) and since x has order p-1, this is = (-1 - 1)/(x-1) = -2/(x-1). If A=B, then Sum(A)=Sum(B) and -1/8 = -2/(x-1), so x-1=16 and x=17. Previosuly the conclusion had been x=9 which was a contradiction, but no longer. The method can be continued however to finish. We consider Sum(A^3) = 1^3 + 2^3 + ... + ((p-1)/2)^3 = (p^2-1)^2/64 = 1/64 mod p. Sum(B^3) = 1^3 + x^3 + x^6 + ... x^(((p-3)/2)^3) = ( (x^3)^((p-1)/2) - 1 ) / (x^3 - 1) = ((-1)^3 - 1)/(x^3 - 1) = -2/(x^3-1). Equating Sum(A^3)=Sum(B^3), we get 1/64 = -2/(x^3-1) and x^3 - 1 = -128 and x^3 = -127. Hence if p is such that A = B, then x = 17 mod p and x^3 = -127 mod p. This just says 17^3 = -127 mod p, so p divides 5040 = 2^4*3^2*5*7, and p can only be 2, 3, 5, or 7. > I reduced my problem to the following simpler problem: > Let Z_p={0,1,2,...p-1} be the finite field with p elements and x > be a primitive element. > Also let A={1,2,3,...,(p-1)/2} and B={1,x,x^2,...,x^(p-3)/2} be > subsets of Z_p^* then A can not be equal to B for p>7. > I was wondering if you have any ideas how this could be solved. _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum From laurent.bartholdi at epfl.ch Wed Jan 12 18:56:20 2005 From: laurent.bartholdi at epfl.ch (Laurent Bartholdi) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Post-doctoral position in group theory/algebra at EPFL Message-ID: Dear Collegues, Would you be so kind as to diffuse the following job offer? --------------------------------------------------------------------- The Chair of Algebra and Discrete Mathematics of the Swiss Institute of Technology at Lausanne (EPFL) invites applications for a full-time postdoctoral position. It would start on September 1st, 2005 and last 1 year, with the possibility of extending it for a second year. In addition to research, duties include teaching within the framework of the Mathematics Section of the EPFL. The salary class is 18, i.e. approximately 75k CHF/year (65k US$/year). Candidates must have completed their PhD within the last four years, and have shown promise of excellence in research in group theory or algebra. In particular, candidates interested in computational algebra (GAP, MAGMA, ...) are welcome. Applications, including curriculum vitae, statement of teaching experience, publication list, and research plan, must be submitted, either in paper or in electronic format (postscript, PDF), by February 28th, to Professor Laurent Bartholdi EPFL, B?timent BCH, CH-1015 Lausanne, Switzerland laurent.bartholdi@epfl.ch For further information concerning EPFL, see http://mad.epfl.ch/ http://igat.epfl.ch/ http://sma.epfl.ch/ http://www.epfl.ch/ -- Laurent Bartholdi \ laurent.bartholdiepflch EPFL, IGAT, B?timent BCH \ T?l?phone: +41 21-6930380 CH-1015 Lausanne, Switzerland \ Fax: +41 21-6930385 From Dursun.Bulutoglu at afit.edu Fri Jan 14 01:37:05 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem simplified generalization Message-ID: <039A0DCC3D66EE4AB9AF11E119287F152383DA@ms-afit-04.afit.edu> Dear GAP Forum; I am trying to generalize the result I stated before as follows: Let Z_p={0,1,2,...p-1} be the finite field with p elements and x be a primitive element. Let r be some positive integer. Also let A={1,2,3,...,(p-1)/2} and B={x^r,x^(r+1),x^(r+2),...,x^(r+(p-3)/2)} be subsets of Z_p^* then A can not be equal to B for p>7. Using the equations Sum(A)=Sum(B) and Sum(A^3)=Sum(B^3) I was able to show that x has to satisfy 11x^2+10x+11=0 in Z_p Using the equation Sum(A^5)=Sum(B^5) with the above two equations I got (Assuming that I did not make an algebra mistake) the equation: (3*2^12+1)+(3*2^12-4)x+(3*2^12+6)x^2+(3*2^12-4)x^3+(3*2^12+1)x^4=0 in Z_p. The proof should come from equalities of the form Sum(A^k)=Sum(B^k) as the values of Sum(A^k),Sum(B^k) for k=1,2,3...p-2 completely determine the distribution of the elements of A and B respectively. (For k=2 and 4 I get Sum(A^k)=Sum(B^k)=0 which are not useful). I was wondering what your ideas are on this. Thanks in advance, your ideas have been very helpful. Dursun. -----Original Message----- From: forum-bounces@gap-system.org [mailto:forum-bounces@gap-system.org] On Behalf Of Mowsey Sent: Tuesday, January 11, 2005 6:53 PM To: Bulutoglu Dursun A Civ AFIT/ENC; forum@gap-system.org Subject: Re: [GAP Forum] A problem simplified I looked over John D. Dixon's solution and Marco Costantini's code, and noticed that the solution suggested p=7 should not work while the code indicated it did. There was a tiny error in the solution, but it can be easily fixed: For A={1,2,3,...,(p-1)/2}, Sum(A) = ( (1 + (p-1)/2)*(p-1)/2 ) / 2 = (p^2-1)/8. Previously the result was reported as (p^2-1)/4. When the sum is taken mod p, one gets Sum(A) = -1/8. The argument continues then as Sum(B) = (x^( (p-3)/2 + 1) - 1) / (x-1) = ( x^( (p-1)/2 ) - 1 ) / ( x - 1 ) and since x has order p-1, this is = (-1 - 1)/(x-1) = -2/(x-1). If A=B, then Sum(A)=Sum(B) and -1/8 = -2/(x-1), so x-1=16 and x=17. Previosuly the conclusion had been x=9 which was a contradiction, but no longer. The method can be continued however to finish. We consider Sum(A^3) = 1^3 + 2^3 + ... + ((p-1)/2)^3 = (p^2-1)^2/64 = 1/64 mod p. Sum(B^3) = 1^3 + x^3 + x^6 + ... x^(((p-3)/2)^3) = ( (x^3)^((p-1)/2) - 1 ) / (x^3 - 1) = ((-1)^3 - 1)/(x^3 - 1) = -2/(x^3-1). Equating Sum(A^3)=Sum(B^3), we get 1/64 = -2/(x^3-1) and x^3 - 1 = -128 and x^3 = -127. Hence if p is such that A = B, then x = 17 mod p and x^3 = -127 mod p. This just says 17^3 = -127 mod p, so p divides 5040 = 2^4*3^2*5*7, and p can only be 2, 3, 5, or 7. > I reduced my problem to the following simpler problem: > Let Z_p={0,1,2,...p-1} be the finite field with p elements and x > be a primitive element. > Also let A={1,2,3,...,(p-1)/2} and B={1,x,x^2,...,x^(p-3)/2} be > subsets of Z_p^* then A can not be equal to B for p>7. > I was wondering if you have any ideas how this could be solved. _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum From wdj at usna.edu Sun Jan 16 14:29:47 2005 From: wdj at usna.edu (David Joyner) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] GUAVA 2.0 patch Message-ID: <41EA7A5B.4020809@usna.edu> Hello GAP Forum: In a posting to this Forum last month I announced a new version of the GAP error-correcting codes package, GUAVA 2.0. It was pointed out by Bjoern Assmann that it only works under the development version of GAP, whose release date is some ways away. This posting is to announce a patched version of GUAVA 2.0 which should work under the current version of GAP. It is posted on the GUAVA web page http://cadigweb.ew.usna.edu/~wdj/gap/GUAVA/ In the "patch", all GUAVA 1.9 functions work and all the new GUAVA 2.0 functions work, except for MinimumDistanceRandom. The small number of people who want that function should try to get the CVS version of GAP http://www.math.rwth-aachen.de/homes/GAP/Info4/cvs.html (If that is not possible, please contact me and I will try to supply the necessary GAP kernel functions which you can use to recompile GAP.) My apologies for any inconvenience. If there are any problems, please let me know. - David Joyner From Michael.Hartley at nottingham.edu.my Fri Jan 14 02:36:39 2005 From: Michael.Hartley at nottingham.edu.my (Michael Hartley) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Tietze Message-ID: [**** EDIT -- FORUM ADMINISTRATOR ****] Subject was "Re: Forum Digest, Vol 14, Issue 4". Changed above for clarity. [END] I've looked through the functions relating to relations and Tietze Transformations. However, I can't find anything that will take a presentation object and give GAP the actual relators within it (TzPrintRelators() gives *me* the relators, but not GAP). I have a large list of permutation groups, and I want to do the following for each group (actually, each generating set) in the list : grp := Group(gens); pres := PresentationViaCosetTable(grp); rels := GetRelatorsSomehow(pres); <-- need help here if (MyTest(rels)) then Print("the group generated by ",gens," passes my test \n"); fi; Any advice? Does the function I want actually exist? Specifically, I want to check that there doesn't exist a relator using all the generators of the group. Yours, Mike H... [*** MESSAGE EDITED TO REMOVE FORUM DIGEST BELOW THIS POINT -- FORUM ADMINISTRATOR ****] From hulpke at math.colostate.edu Fri Jan 14 18:09:26 2005 From: hulpke at math.colostate.edu (Alexander Hulpke) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Re: Tietze Message-ID: <200501141809.j0EI9QtM013088@schur.math.colostate.edu> Dear GAP-Forum, Michael Hartley wrote: > I've looked through the functions relating to relations and Tietze > Transformations. However, I can't find anything that will take a > presentation object and give GAP the actual relators within it > (TzPrintRelators() gives *me* the relators, but not GAP). I have a large > list of permutation groups, and I want to do the following for each group > (actually, each generating set) in the list : > grp := Group(gens); > pres := PresentationViaCosetTable(grp); > rels := GetRelatorsSomehow(pres); <-- need help here > if (MyTest(rels)) then > Print("the group generated by ",gens," passes my test \n"); > fi; > > Any advice? Does the function I want actually exist? Specifically, I want > to check that there doesn't exist a relator using all the generators of the > group. You could use: grp2:=FpGroupPresentation(pres); rels:=RelatorsOfFpGroup(grp2); Note that the free generators are FreeGeneratorsOfGroup(grp2); Alternatively, you could use hom:=IsomorphismFpGroupByGenerators(grp,gens); grp2:=Image(grp); which does a slightly different kind of rewriting in one call. I hope this is of help, Alexander Hulpke PS: Given that the Forum email goes to hundreds of people I would suggest that when replying to a ``digest'' mail to delete the irrelevant contents of the digest as well as changing the subject line. _______________________________________________ Support mailing list Support@gap-system.org http://mail.gap-system.org/mailman/listinfo/support From Dursun.Bulutoglu at afit.edu Tue Jan 18 16:57:50 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] A problem simplified Message-ID: <039A0DCC3D66EE4AB9AF11E119287F15238531@ms-afit-04.afit.edu> Dear Gap Forum; I further reduced my problem to the following problem: Let Z_p be the finite field with p elements then there exists some N such that for all p>N the interval [-(p+1)/4, (p-1)/4] contains a generator of Z_p^*. I was wondering if anybody knows a result like this in number theory either in the form of a conjecture or a Theorem. Thank you very much. Dursun. From wdj at usna.edu Wed Jan 19 12:14:59 2005 From: wdj at usna.edu (David Joyner) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] GAP and emacs Message-ID: <41EE4F43.7040504@usna.edu> Hello GAP Forum: Is there anyone who runs GAP in emacs on this list? If so, please respond off-list. The emacs mode in the cvs version seems to be out-of-date and I have some questions about it. - David From wh at icparc.ic.ac.uk Sun Jan 23 08:16:21 2005 From: wh at icparc.ic.ac.uk (wh@icparc.ic.ac.uk) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Local search? Message-ID: <20050123081621.GA14728@tempest.icparc.ic.ac.uk> Dear GAP Forum, Are any of you aware of any software (GAP or otherwise) or literature regarding using local search to find a group element with certain properties? I am interested in using such techniques, so any such software or literature would be useful to me. By local search I mean techniques along the lines of starting with a more-or-less random element that does not have the desired properties, moving to a "nearby"/similar element that might be closer to having the desired properties, and repeating until one either finds an element that meets the requirements or gives up. (Examples of such techniques include hill climbing, tabu search, greedy randomised adaptive search procedures (GRASPs), and possibly simulated annealing and genetic algorithms.) Basically, I want to do a relatively quick check to see whether I can find such an element, but I don't care too much if I fail to find one, even if one exists. Cheers, Warwick From wdj at usna.edu Tue Jan 25 20:38:31 2005 From: wdj at usna.edu (David Joyner) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] GAP interface program web pages Message-ID: <41F6AE47.8080906@usna.edu> Hello GAP Forum: 2. I've written up some web pages which I think explain in simple terms how to use some of the programs useful for making GAP easier and/or nicer to interface. If they are useful, great. If you have comments, I'd be happy to hear them. 2. The new web pages: (a) Frank Luebeck's ReadNC GAP program allows the reading into GAP of programs with multi-line comments: http://cadigweb.ew.usna.edu/~wdj/gap/read_no_comments.html (b) To run gap in emacs or xemacs (linux/unix only) see: http://cadigweb.ew.usna.edu/~wdj/gap/gap_emacs.html (c) To run GAP in color, see: http://cadigweb.ew.usna.edu/~wdj/gap/gap_colors.html 3. I'd be interested to know if anyone gets GAP to run in emacs in windows using intructions analogous to 2(b). - David Joyner From s.delossantos at amena.com Sun Jan 30 16:33:20 2005 From: s.delossantos at amena.com (Sergio De Los Santos) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Compiling GAP under Windows 2000 and mingw. Message-ID: <48ca3460c1.460c148ca3@amena.com> Hello all. My intention is to build a Visual Basic Interface mainly to pacakage GUAVA. I'm not any expert in programming, but my idea is to build some DLL with C source and call functions from Visual Basic. Is it possible? I have researched for a while and found this: http://www.gap-system.org/ForumArchive/Pasechni.1/Dmitrii.1/using_GA.1/1.html that says it is not "easy" or mainly impossible to use C source as a C library. Should I try? I can't even compile it under Windows 2000 using mingw. I get lots of errors. Basicly, I'm trying to follow this pages way: http://www.gap-system.org/ForumArchive/Hirbawi.1/Jacob.1/RE__Trou.1/1.html of course the program has changed a lot since 1993, and it is not that way anymore. I use it as an "idea". Some files, like c_oper1.c, just shows lots of errors... Even if I fix some of then, and using a "hand edited" config.h, there are always missing symbols or even syntax errors on this and other file compilations. I would appreciate some indications about compiling under Windows 2000 using mingw. By the way, while compiling system.c, I always get this error: d:\Tools\mingw\bin>gcc -c .\src\system.c src/system.c:136: parse error before '=' token wich is this line. const Char * SyArchitecture = SYS_ARCH; I don't know why. I think once i get some dll files with the importan functions, to build an interface is not difficult at all. If it is impossible I would use pipes to pass parameters to gap.exe, but, first of all I would like to be able to build my own exe file. Any kind of advise or indication would be considered and appreciated. Thanks a lot. From d.v.pasechnik at uvt.nl Sun Jan 30 18:43:09 2005 From: d.v.pasechnik at uvt.nl (Dima Pasechnik) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Compiling GAP under Windows 2000 and mingw. In-Reply-To: <48ca3460c1.460c148ca3@amena.com> References: <48ca3460c1.460c148ca3@amena.com> Message-ID: <20050130184309.GA1482@babbage.lan> Dear Forum, On Sun, Jan 30, 2005 at 05:33:20PM +0100, Sergio De Los Santos wrote: > My intention is to build a Visual Basic Interface mainly to pacakage GUAVA. I'm not any expert in programming, but my idea is to build some DLL with C source and call functions from Visual Basic. [...] > I can't even compile it under Windows 2000 using mingw. I get lots of errors. Certainly. Compiling with mingw will not differ from compiling using a native Windows C compiler. Mingw does not know Posix, and GAP does not know anything about Win32 system calls; it runs under Windows using Cygwin (not to be confused with mingw). Cygwin takes the job of translating Posix system calls made by GAP into Win32 calls. While porting GAP to use native Win32 calls is doable, basically src/system.c is the only place that needs lots of changes, it is certainly a nontrivial and time-consuming task. (and one needs to be a bit of an expert in programming to do this, IMHO) Perhaps easier is to build GAP as a DLL, using Cygwin, and call this DLL from VB. Why would you insist on VB? Can you use something like XGAP instead? It should be easier, and will run not only on Windows... > I think once i get some dll files with the importan functions, to build an interface is not difficult at all. If it is impossible I would use pipes to pass parameters to gap.exe, but, first of all I would like to be able to build my own exe file. > use Cygwin for this. After running configure, edit Makefile to replace ocurrences of "strip gap" with "strip gap.exe". Then make will run without errors. HTH, Dmitrii From gzabl at yahoo.com Wed Feb 2 19:24:26 2005 From: gzabl at yahoo.com (Gary Zablackis) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] GAP interface program web pages In-Reply-To: <41F6AE47.8080906@usna.edu> Message-ID: <20050202192426.36076.qmail@web53007.mail.yahoo.com> Hello, David I was able to run GAP in emacs and in xemacs using the instructions in 2(b). I have the CYGWIN development environment installed on my machine and used the (x)emacs that comes with that. I have not used emacs before, so I have not done much with it, yet. I hope to spend some time with the docs next week to see how it works. I will be downloading NTEmacs today to see how that works. The only problem I had was in attempting to use colors.gap with (x)emacs (both are X programs in the CYGWIN distribution). The default terminal settings used by X under CYGWIN do not process the escape sequences (although they are handled properly under normal Windows and non-X CYGWIN). If I have the time, I will attempt to get that working soon, too. If you have any questions about my setup, please feel free to ask. Gary Zablackis David Joyner wrote: ... (b) To run gap in emacs or xemacs (linux/unix only) see: http://cadigweb.ew.usna.edu/~wdj/gap/gap_emacs.html ... 3. I'd be interested to know if anyone gets GAP to run in emacs in windows using intructions analogous to 2(b). - David Joyner _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum --------------------------------- Do you Yahoo!? Yahoo! Search presents - Jib Jab's 'Second Term' From sal at dcs.st-and.ac.uk Fri Feb 4 14:01:14 2005 From: sal at dcs.st-and.ac.uk (Steve Linton) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Local search? In-Reply-To: <20050123081621.GA14728@tempest.icparc.ic.ac.uk> References: <20050123081621.GA14728@tempest.icparc.ic.ac.uk> Message-ID: <20050204140114.7e8ab400@localhost.localdomain> Dear GAP Forum, On Sun, 23 Jan 2005 09:16:21 +0100 wh@icparc.ic.ac.uk wrote: > Dear GAP Forum, > > Are any of you aware of any software (GAP or otherwise) or literature > regarding using local search to find a group element with certain properties? > I am interested in using such techniques, so any such software or literature > would be useful to me. > > By local search I mean techniques along the lines of starting with a > more-or-less random element that does not have the desired properties, > moving to a "nearby"/similar element that might be closer to having the > desired properties, and repeating until one either finds an element that > meets the requirements or gives up. (Examples of such techniques include > hill climbing, tabu search, greedy randomised adaptive search procedures > (GRASPs), and possibly simulated annealing and genetic algorithms.) > > Basically, I want to do a relatively quick check to see whether I can find > such an element, but I don't care too much if I fail to find one, even if > one exists. > The only work anyone has been able to think of in this direction is some work by the Magnus group in New York on using genetic algorithms to do computations with finitely-presented groups. A. D. Miasnikov\ and\ A. G. Myasnikov, in {\it Computational and experimental group theory}, 89--114, Contemp. Math., 349, Amer. Math. Soc., Providence, RI, 2004; MR2077761 A. D. Miasnikov, Internat. J. Algebra Comput. {\bf 9} (1999), no.~6, 671--686; MR1727164 (2001k:20067) I have been involved in some discussions of this idea with Warwick on another mailing list. For the interest if the forum, and in case anyone else can contribute, we're interested in methods that attempt to solve problems in permutation groups that would normally require a backtrack search, such as "is there a g \in G which maps a set S of points into another set T (possibly larger)". We're interested in methods that have a reasonable chance of returning a positive solution quickly, if there is one, but we can tolerate some chance of error. Steve Linton -- Steve Linton School of Computer Science & Centre for Interdisciplinary Research in Computational Algebra University of St Andrews Tel +44 (1334) 463269 http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278 From gzabl at yahoo.com Fri Feb 4 20:18:20 2005 From: gzabl at yahoo.com (Gary Zablackis) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Fwd: Re: GAP and (x)emacs (for Dr Joyner) Message-ID: <20050204201821.2765.qmail@web53002.mail.yahoo.com> David, Messages FROM yahoo addresses are also being blocked, so I am forwarding this to the forum to allow it to reach you. Gary Zablackis wrote: Date: Fri, 4 Feb 2005 12:12:15 -0800 (PST) From: Gary Zablackis Subject: Re: To: William Joyner David, I will be checking out NTEmacs this weekend. I have not had time yet to check out how to get the colors to work in the Cygwin (x)emacs programs; that may take a little longer to determine. A desktop icon linking to a .bat (or .cmd) file can be created in Windows by right-clicking on the desktop and selecting "new->shortcut" and then pointing to the location of the file. It is also possible to create a link programmatically. If you like, I can send you the code (in the form of a script or in the form of a c++ source file). Sincerely, Gary Zablackis William Joyner wrote: Hope this works - something is blocking email to yahoo addresses. First, thanks very much! ... Before adding anything to the web pages I'm curious how NTemacs does or if you discover any changes which need to be made to get it to work. I'm also wondering if a windows desktop icon linking to a bat file can be created, analogously to linux, which launches gap within NTemacs after a double mouse click. I'm also curious if colors.gap works in NTemacs. --------------------------------- Do you Yahoo!? Yahoo! Search presents - Jib Jab's 'Second Term' __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com From gurican at dcs.fmph.uniba.sk Mon Feb 7 16:04:10 2005 From: gurican at dcs.fmph.uniba.sk (Jaroslav Gurican) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Article f C.C.Sims Message-ID: <200502071604.j17G4CU24379@alpha.dcs.fmph.uniba.sk> Dear GAP forum, I would like to have a copy of original article of C.C.Sims: Computational methods in the study of permutation groups. In John Leech, editor, Computational Problems in Abstract Algebra, Proc. Conf. Oxford, 1967, pages 169--183. Pergamon Press, Oxford, 1970. I cannot find it in local and nearby libraries. Can some good soul send me (maybe scanned gifs) a copy of this article? If yes, please respond to my direct mail address: gurican@fmph.uniba.sk not to GAP-Forum. Thanks in advance. Jaroslav Gurican -- From wdj at usna.edu Wed Feb 9 17:00:13 2005 From: wdj at usna.edu (David Joyner) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] gap2latex parser Message-ID: <420A419D.2020109@usna.edu> Hi GAP Forum: I've written a very simple python program which takes a file obtained from the GAP LogTo command and converts into a latex file. You must have the python binary installed in \usr\bin (on a linux/unix setup). However, if you have the windows version of python then it presumably works with some editing. The file with an example in on the page http://cadigweb.ew.usna.edu/~wdj/gap/ if you are interested. If there are any comments, please email me at wdj@usna.edu. Thanks. - David Joyner From laurent.bartholdi at epfl.ch Thu Feb 10 22:52:07 2005 From: laurent.bartholdi at epfl.ch (Laurent Bartholdi) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] bugs? Message-ID: hi y'all, a bunch of strange things happened to me these last days when i played around with gap. i use a fairly recent version from cvs (don't remember when i updated it last): gap> A := GroupRing(GF(5),SymmetricGroup(4)); gap> 3*A.1; (Z(5)^3)*(1,2,3,4) gap> 3/4*A.1; Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for `PROD' on 2 arguments called from gap> 3*A.1/4; Z(5)*(1,2,3,4) gap> A.1*3/4; Z(5)*(1,2,3,4) --------------------------------------------------- gap> L := LeftIdeal(A,[A.1+A.1^2+A.1^3+A.1^4]);; B := Basis(L);; gap> IsList(B); true gap> Concatenation([A.1],B); AppendList: must be a small list (not a object (component)) at Append( res, arg[i] ); called from ( ) called from read-eval-loop ... gap> Concatenation([A.1],Elements(B)); [ (Z(241)^0)*(1,2,3,4), ... ] gap> Concatenation([A.1],B); [ (Z(241)^0)*(1,2,3,4), ... ] gap> -- -- Laurent Bartholdi \ laurent.bartholdiepflch EPFL, IGAT, B?timent BCH \ T?l?phone: +41 21-6930380 CH-1015 Lausanne, Switzerland \ Fax: +41 21-6930385 -------------- next part -------------- From nea at diamond.boisestate.edu Sun Feb 13 03:27:16 2005 From: nea at diamond.boisestate.edu (Nikos Apostolakis) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Running gap in emacs Message-ID: <20050213032716.GA30990@hypathia.boisestate.edu> Hello, I tried to run gap in an emacs buffer and I came across the following problem. The help function is not working. Instead I get the error "Buffer *Help* is read only". I get a similar method when I try to use ( M- ) in a buffer in gap-mode, namely "Buffer *Completions* is read only". Completion is working in the gap-process buffer so I think that the problem is in the function "gap-completions-filter" defined in the file gap-process.el. Is anybody else having the same problems? Any fixes? Thanks for any help Nikos -- 1 2 2 3 1 2 2 3 \ / \ / \ \ / Nikos Apostolakis / \ <------> / Visiting Professor \ / / \ Department of Mathematics \ / \ Boise State University / \ / \ 2 3 1 3 2 3 1 3 From cbr773 at yahoo.com Sun Feb 13 08:17:37 2005 From: cbr773 at yahoo.com (comptel) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Finite fields Message-ID: <20050213081738.65912.qmail@web50208.mail.yahoo.com> hi, I I have some doubts on finite fields. Can anyone answer the following question? we wish to encode the message using F32... Define the cumulative degree of a polynomial to be the sum of degrees of its monomials. a)How many irreducible polynomials of degree 5 over Z/2Z are there? what are they? b) Let Y be a root of the irreducible polynomial of degree 5 of lowest cumulative degree. Then { 1,Y,Y^2,Y^3,Y^4} forms a basis for F32 over Z/2Z. Writing each element of F32 as a 5 tuple with respect to this basis, find all the powers of Y. c) We encode message (numbers between 0 and 31) by raising it Y to that power and then returning the five-bit binary representation we get when writing this element as a 5-tuple with respect to {1,Y,Y^2,Y^3,Y^4}.If 19 is the result m then what number was initially sent?. can anyone help ?. --------------------------------- Do you Yahoo!? Yahoo! Search presents - Jib Jab's 'Second Term' From gzabl at yahoo.com Mon Feb 14 17:25:55 2005 From: gzabl at yahoo.com (Gary Zablackis) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Running gap in emacs In-Reply-To: <20050213032716.GA30990@hypathia.boisestate.edu> Message-ID: <20050214172555.5502.qmail@web53003.mail.yahoo.com> Dear Nikos, I ran into the same problem with the help buffer the other day and was able to fix it by using the mouse on the bar that separates the help window from the window above (or below) it. I do not have emacs on the machine that I am working on at the moment, but if you need further information, I will check this out at home this evening and email you more complete instructions. I will also look into the gap*.el files to see if there is a fix possible there. Sincerely, Gary Zablackis Nikos Apostolakis wrote: Hello, I tried to run gap in an emacs buffer and I came across the following problem. The help function is not working. Instead I get the error "Buffer *Help* is read only". I get a similar method when I try to use ( M- ) in a buffer in gap-mode, namely "Buffer *Completions* is read only". Completion is working in the gap-process buffer so I think that the problem is in the function "gap-completions-filter" defined in the file gap-process.el. Is anybody else having the same problems? Any fixes? Thanks for any help Nikos -- 1 2 2 3 1 2 2 3 \ / \ / \ \ / Nikos Apostolakis / \ <------> / Visiting Professor \ / / \ Department of Mathematics \ / \ Boise State University / \ / \ 2 3 1 3 2 3 1 3 --------------------------------- Do you Yahoo!? Yahoo! Search presents - Jib Jab's 'Second Term' From nea at diamond.boisestate.edu Tue Feb 15 07:37:54 2005 From: nea at diamond.boisestate.edu (Nikos Apostolakis) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Running gap in emacs In-Reply-To: <20050214172555.5502.qmail@web53003.mail.yahoo.com> References: <20050213032716.GA30990@hypathia.boisestate.edu> <20050214172555.5502.qmail@web53003.mail.yahoo.com> Message-ID: <20050215073754.GC30990@hypathia.boisestate.edu> On Mon, Feb 14, 2005 at 09:25:55AM -0800, Gary Zablackis wrote: > Dear Nikos, > > I ran into the same problem with the help buffer the other day and was able to fix it by using the mouse on the bar that separates the help window from the window above (or below) it. I do not have emacs on the machine that I am working on at the moment, but if you need further information, I will check this out at home this evening and email you more complete instructions. > I will also look into the gap*.el files to see if there is a fix possible there. Thanks for your replay. Yes please do email me your solution to this problem. By searching some more I found that this problem is rather old. There is question about it posted in the GAP forum in 1998: http://www.gap-system.org/ForumArchive/Rickard.1/Jeremy.1/gap-proc.1/1.html By playing some with emacs (including editing the file gap-process.el) I *once* managed to convince emacs to let gap write into buffer *Help*, however since I wasn't very systematic about it I am not sure how to repeat this. In any case, in the next help command the problem did reappear so whatever I did wsa not the solution. > > Sincerely, > Gary Zablackis > -- 1 2 2 3 1 2 2 3 \ / \ / \ \ / Nikos Apostolakis / \ <------> / Visiting Professor \ / / \ Department of Mathematics \ / \ Boise State University / \ / \ 2 3 1 3 2 3 1 3 From barracrw at for.mat.bham.ac.uk Tue Feb 15 13:41:49 2005 From: barracrw at for.mat.bham.ac.uk (Richard Barraclough) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Finite fields In-Reply-To: <20050213081738.65912.qmail@web50208.mail.yahoo.com> Message-ID: > hi, > I > I have some doubts on finite fields. Can anyone answer the following question? > > we wish to encode the message using F32... Define the cumulative degree of a > polynomial to be the sum of degrees of its monomials. > > a)How many irreducible polynomials of degree 5 over Z/2Z are there? > what are they? You can use GAP to find this out easily, F := FiniteField(2); x := Indeterminate(F); V := FullRowSpace(F,5); for v in V do f := x^5; for i in [1..5] do f := f + v[i]*x^(i-1); od; if IsIrreducible(f) then Print(f,"\n"); fi; od; > > > b) > Let Y be a root of the irreducible polynomial of degree 5 of lowest cumulative > degree. Then { 1,Y,Y^2,Y^3,Y^4} forms a basis for F32 over Z/2Z. Writing each > element of F32 as a 5 tuple with respect to this basis, find all the powers > of Y. Lets say our polynomial is x^5 + x^3 + 1 So 1 -> 10000 Y -> 01000 Y^4 -> 00001 Y^5 -> 10010 Let A := [[0,0,0,0,0],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0]]*Z(2); When we multiply a vector by A it shifts all co-ordinates to the right and fills the left with zeros, i.e., bit shift. So multiplying a vector by A is the same as multiplying the corresponding F32 number by Y except that we have to sort out what happens when our vectors overflow at the right. If the 5th co-ordinate (the one corresponding to Y^4) is 1, then we shall add 10010 after bit shifting, because 10010 corresponds to Y^5. So, Y^6 = (Y^5)A = 01001 Y^7 = (Y^6)A + 10010 = 10110 Y^8 = (Y^7)A = 01011 Y^9 = (Y^8)A + 10010 = 10111 Y^10 = (Y^9)A + 10010 = 11001 etc. This is an easy way to build a lookup table for encoding/decoding. > c) We encode message (numbers between 0 and 31) by raising it Y to that power > and then returning the five-bit binary representation we get when writing this > element as a 5-tuple with respect to {1,Y,Y^2,Y^3,Y^4}.If 19 is the result > then what number was initially sent?. 19 -> 11001 which happens to correspond to Y^10. Wouldn't it be OK just to send the un-encoded message? I can't see how this coding can correct any errors. Regards, Richard Barraclough From Dursun.Bulutoglu at afit.edu Wed Feb 16 19:43:29 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Speed of GAP Message-ID: <039A0DCC3D66EE4AB9AF11E119287F154E61BE@ms-afit-04.afit.edu> Dear Gap Forum, I was wondering how GAP compares to C in terms of speed. Is GAP slower processing through large loops? Is there a programming style in GAP that can improve the speed at which jobs are done? For example in some high level programming languages avoiding loops as much as possible is recommended to boost speed. Is GAP much slower when the data it processes through is large? I have a GAP code running for a week now and it still has not finished. I have a feeling that it would have run much faster with C. Dursun. From justpasha at gmail.com Fri Feb 18 08:44:13 2005 From: justpasha at gmail.com (Pasha Zusmanovich) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] addition of linear mappings Message-ID: <4215AADD.12CCF5EB@gmail.com> Dear people, I am trying to add two linear mappings. gap> GAPInfo.Version; "4.4.4" gap> V := VectorSpace (Rationals, [[1,0],[0,1]]); gap> A := LeftModuleHomomorphismByImagesNC (V, V, Basis(V), [[1,0],[0,0]]); SemiEchelonBasis( , [ [ 1, 0 ], [ 0, 1 ] ] ) -> [ [ 1, 0 ], [ 0, 0 ] ] gap> B := LeftModuleHomomorphismByImagesNC (V, V, Basis(V), [[0,0],[0,1]]); SemiEchelonBasis( , [ [ 1, 0 ], [ 0, 1 ] ] ) -> [ [ 0, 0 ], [ 0, 1 ] ] So far, so good. gap> A + B; Error, and must have same (pre)image called from ( ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> Indeed, Image(A) does not coincide with Image(B), but is it needed to be able to add two mappings? Image(A) and Image(B) are guaranteed to be subspaces of V, so their elements can be added safely. If one removes the corresponding checks from lib/vspchom.gi (lines with ImagesSource( map1 ) <> ImagesSource( map2 ) in two places), everything works like a charm: gap> A + B; SemiEchelonBasis( , [ [ 1, 0 ], [ 0, 1 ] ] ) -> [ [ 1, 0 ], [ 0, 1 ] ] Am I missing something? Thanks, Pasha. From hebert at csd.uo.edu.cu Fri Feb 18 16:18:02 2005 From: hebert at csd.uo.edu.cu (hebert@csd.uo.edu.cu) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Speed of GAP In-Reply-To: <039A0DCC3D66EE4AB9AF11E119287F154E61BE@ms-afit-04.afit.edu> References: <039A0DCC3D66EE4AB9AF11E119287F154E61BE@ms-afit-04.afit.edu> Message-ID: <1090.172.16.151.81.1108743482.squirrel@server> > Dear Gap Forum, > I was wondering how GAP compares to C in terms of speed. > Is GAP slower processing through large loops? > Is there a programming style in GAP that can improve the speed at which > jobs are done? For example in some high level programming languages > avoiding loops as much as possible is recommended to boost speed. > Is GAP much slower when the data it processes through is large? > I have a GAP code running for a week now and it still has not finished. > I have a feeling that it would have run much faster with C. > Dursun. I don't know about your particular situation, but usually when such problems arise, they simply cannot be solved by changing the programming language. If you're lucky you could slice the running time of your program by a constant factor. Your description reveals that either your problem is essentially intractable or you must look for a better algorithm. A personal anecdote: I had a GAP program that computed the number of elements of a finitely presented monoids in several hours; after careful considerations I found a better algorithm that could do the same work in milliseconds. Good luck, Hebert. > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum From gzabl at yahoo.com Fri Feb 18 17:07:14 2005 From: gzabl at yahoo.com (Gary Zablackis) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Running gap in emacs In-Reply-To: <20050215073754.GC30990@hypathia.boisestate.edu> Message-ID: <20050218170714.24795.qmail@web53004.mail.yahoo.com> Dear Nikos, I will be looking into this problem over the weekend. Would you let me know what version of emacs your are using and on which operating system you are running? Thank you, Gary Zablackis Nikos Apostolakis wrote: Thanks for your replay. Yes please do email me your solution to this problem. By searching some more I found that this problem is rather old. There is question about it posted in the GAP forum in 1998: http://www.gap-system.org/ForumArchive/Rickard.1/Jeremy.1/gap-proc.1/1.html By playing some with emacs (including editing the file gap-process.el) I *once* managed to convince emacs to let gap write into buffer *Help*, however since I wasn't very systematic about it I am not sure how to repeat this. In any case, in the next help command the problem did reappear so whatever I did wsa not the solution. > > Sincerely, > Gary Zablackis > -- 1 2 2 3 1 2 2 3 \ / \ / \ \ / Nikos Apostolakis / \ <------> / Visiting Professor \ / / \ Department of Mathematics \ / \ Boise State University / \ / \ 2 3 1 3 2 3 1 3 __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com From Dursun.Bulutoglu at afit.edu Fri Feb 18 19:21:21 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:47 2005 Subject: [GAP Forum] Speed of GAP Message-ID: <039A0DCC3D66EE4AB9AF11E119287F154E63C7@ms-afit-04.afit.edu> My experience is that MATLAB is slower than C by a factor of 2 or 3. Also R, (a statistical language) is 10 times slower than C. In general higher level languages (languages that have a lot of overhead) are slower than lower level languages like C or Fortran. My question was how GAP compares to C in terms of speed. I am assuming that GAP is a higher level language as one does not have to define everything like in C. Also programming style can make a difference in higher level languages. In R it is recommended that the user should avoid for loops as much as possible as for loops in R become intangible when they are large. Dursun. > Dear Gap Forum, > I was wondering how GAP compares to C in terms of speed. > Is GAP slower processing through large loops? > Is there a programming style in GAP that can improve the speed at which > jobs are done? For example in some high level programming languages > avoiding loops as much as possible is recommended to boost speed. > Is GAP much slower when the data it processes through is large? > I have a GAP code running for a week now and it still has not finished. > I have a feeling that it would have run much faster with C. > Dursun. I don't know about your particular situation, but usually when such problems arise, they simply cannot be solved by changing the programming language. If you're lucky you could slice the running time of your program by a constant factor. Your description reveals that either your problem is essentially intractable or you must look for a better algorithm. A personal anecdote: I had a GAP program that computed the number of elements of a finitely presented monoids in several hours; after careful considerations I found a better algorithm that could do the same work in milliseconds. Good luck, Hebert. > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum From nea at diamond.boisestate.edu Fri Feb 18 23:38:35 2005 From: nea at diamond.boisestate.edu (Nikos Apostolakis) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Running gap in emacs In-Reply-To: <20050218170714.24795.qmail@web53004.mail.yahoo.com> References: <20050215073754.GC30990@hypathia.boisestate.edu> <20050218170714.24795.qmail@web53004.mail.yahoo.com> Message-ID: <20050218233835.GF24259@hypathia.boisestate.edu> On Fri, Feb 18, 2005 at 09:07:14AM -0800, Gary Zablackis wrote: > Dear Nikos, > > I will be looking into this problem over the weekend. > Would you let me know what version of emacs your are using and on which operating system you are running? > Dear Gary, In my office I run GNU emacs 21.2.1 on a RedHat 9 and in my home I run GNU emacs 21.3.1 on a Debian testing/unstable. In both of these machines I get the same problem. Thanks again Nikos > Thank you, > Gary Zablackis > > > Nikos Apostolakis wrote: > Thanks for your replay. > > Yes please do email me your solution to this problem. By > searching some more I found that this problem is rather > old. There is question about it posted in the GAP forum in 1998: > > http://www.gap-system.org/ForumArchive/Rickard.1/Jeremy.1/gap-proc.1/1.html > > By playing some with emacs (including editing the file > gap-process.el) I *once* managed to convince emacs to let gap > write into buffer *Help*, however since I wasn't very systematic > about it I am not sure how to repeat this. In any case, in the > next help command the problem did reappear so whatever I did wsa > not the solution. > > > > > Sincerely, > > Gary Zablackis > > From sal at dcs.st-and.ac.uk Sat Feb 19 19:17:59 2005 From: sal at dcs.st-and.ac.uk (Steve Linton) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Re: Speed of GAP Message-ID: <20050219191759.6e5cc39a@localhost.localdomain> Dear GAP Forum, Dursun Bulutoglu asked: > I was wondering how GAP compares to C in terms of speed. > Is GAP slower processing through large loops? > Is there a programming style in GAP that can improve the speed at which > jobs are done? For example in some high level programming languages > avoiding loops as much as possible is recommended to boost speed. > Is GAP much slower when the data it processes through is large? > I have a GAP code running for a week now and it still has not finished. > I have a feeling that it would have run much faster with C. There is no really simple answer to this question, it depends very much on what you are doing. Code in which most the time is spent doing simple arithmetic, array accesses, data structure manipulation, and so on is perhaps 3 to 10 times slower in GAP than C, due mainly to the additional overheads from the memory management and the interpreter, but this is extremely variable. Code of this kind can benefit significantly from compilation using the "gac" GAP to C compiler (see section 3.7 of the reference manual). As soon as you do something which calls upon the slightly higher level capabilities of the GAP kernel, such as vector arithmetic, the overhead of using GAP drops away dramatically. The overhead of simple loops such as for i in [1..10000] do .... od is very small. Special code in the interpreter detects this case and essentially performs the equivalent C loop. On the other hand it will be quite a lot faster to do w := u+ v; than for i in [1..Length(u)] do w[i] := u[i]+ v[i]; od; since the former will use a kernel routine to do all the additions instead of interpreting each one separately. Without seeing your code it is difficult to say more. Steve Linton -- Steve Linton School of Computer Science & Centre for Interdisciplinary Research in Computational Algebra University of St Andrews Tel +44 (1334) 463269 http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278 From Dursun.Bulutoglu at afit.edu Sun Feb 20 17:28:11 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Re: Speed of GAP Message-ID: <039A0DCC3D66EE4AB9AF11E119287F154E6424@ms-afit-04.afit.edu> I was wondering, if I compiled my GAP code using GAC is there a guarantee that it will run as fast as the C version of my code? Dursun. Dear GAP Forum, Dursun Bulutoglu asked: > I was wondering how GAP compares to C in terms of speed. > Is GAP slower processing through large loops? > Is there a programming style in GAP that can improve the speed at which > jobs are done? For example in some high level programming languages > avoiding loops as much as possible is recommended to boost speed. > Is GAP much slower when the data it processes through is large? > I have a GAP code running for a week now and it still has not finished. > I have a feeling that it would have run much faster with C. There is no really simple answer to this question, it depends very much on what you are doing. Code in which most the time is spent doing simple arithmetic, array accesses, data structure manipulation, and so on is perhaps 3 to 10 times slower in GAP than C, due mainly to the additional overheads from the memory management and the interpreter, but this is extremely variable. Code of this kind can benefit significantly from compilation using the "gac" GAP to C compiler (see section 3.7 of the reference manual). As soon as you do something which calls upon the slightly higher level capabilities of the GAP kernel, such as vector arithmetic, the overhead of using GAP drops away dramatically. The overhead of simple loops such as for i in [1..10000] do .... od is very small. Special code in the interpreter detects this case and essentially performs the equivalent C loop. On the other hand it will be quite a lot faster to do w := u+ v; than for i in [1..Length(u)] do w[i] := u[i]+ v[i]; od; since the former will use a kernel routine to do all the additions instead of interpreting each one separately. Without seeing your code it is difficult to say more. Steve Linton -- Steve Linton School of Computer Science & Centre for Interdisciplinary Research in Computational Algebra University of St Andrews Tel +44 (1334) 463269 http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278 _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum From Dursun.Bulutoglu at afit.edu Sun Feb 20 18:03:10 2005 From: Dursun.Bulutoglu at afit.edu (Bulutoglu Dursun A Civ AFIT/ENC) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Speed of GAP Message-ID: <039A0DCC3D66EE4AB9AF11E119287F154E6425@ms-afit-04.afit.edu> I was wondering, if I compiled my GAP code using GAC is there a guarantee that it will run as fast as the C version of my code? Dursun. Dear GAP Forum, Dursun Bulutoglu asked: > I was wondering how GAP compares to C in terms of speed. > Is GAP slower processing through large loops? > Is there a programming style in GAP that can improve the speed at which > jobs are done? For example in some high level programming languages > avoiding loops as much as possible is recommended to boost speed. > Is GAP much slower when the data it processes through is large? > I have a GAP code running for a week now and it still has not finished. > I have a feeling that it would have run much faster with C. There is no really simple answer to this question, it depends very much on what you are doing. Code in which most the time is spent doing simple arithmetic, array accesses, data structure manipulation, and so on is perhaps 3 to 10 times slower in GAP than C, due mainly to the additional overheads from the memory management and the interpreter, but this is extremely variable. Code of this kind can benefit significantly from compilation using the "gac" GAP to C compiler (see section 3.7 of the reference manual). As soon as you do something which calls upon the slightly higher level capabilities of the GAP kernel, such as vector arithmetic, the overhead of using GAP drops away dramatically. The overhead of simple loops such as for i in [1..10000] do .... od is very small. Special code in the interpreter detects this case and essentially performs the equivalent C loop. On the other hand it will be quite a lot faster to do w := u+ v; than for i in [1..Length(u)] do w[i] := u[i]+ v[i]; od; since the former will use a kernel routine to do all the additions instead of interpreting each one separately. Without seeing your code it is difficult to say more. Steve Linton From thomas.breuer at math.rwth-aachen.de Wed Feb 23 12:21:12 2005 From: thomas.breuer at math.rwth-aachen.de (Thomas Breuer) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] bugs? Message-ID: Dear GAP Forum, Laurent Bartholdi has reported the following GAP bugs. > gap> A := GroupRing(GF(5),SymmetricGroup(4)); > > gap> 3*A.1; > (Z(5)^3)*(1,2,3,4) > gap> 3/4*A.1; > Error, no method found! For debugging hints type ?Recovery from NoMethodFou= > nd > Error, no 1st choice method found for `PROD' on 2 arguments called from > gap> 3*A.1/4; > Z(5)*(1,2,3,4) > gap> A.1*3/4; > Z(5)*(1,2,3,4) > --------------------------------------------------- > gap> L := LeftIdeal(A,[A.1+A.1^2+A.1^3+A.1^4]);; B := Basis(L);; > gap> IsList(B); > true > gap> Concatenation([A.1],B); > AppendList: must be a small list (not a object (component)) at > Append( res, arg[i] ); > called from > ( ) called from read-eval-loop > .. > gap> Concatenation([A.1],Elements(B)); > [ (Z(241)^0)*(1,2,3,4), ... ] > gap> Concatenation([A.1],B); > [ (Z(241)^0)*(1,2,3,4), ... ] The first problem is due to a missing method for multiplying group ring elements with rationals. As the example shows, multiplication and division by integers works, so there is clearly no reason why multiplication with rationals should not be supported. The necessary method installations for a quick fix are appended below. The second problem is due to a too restrictive method for `Append'. Fixing this will require a change to the GAP kernel, but a preliminary workaround for the example above (and others) is appended below. Thanks very much for the report. All the best, Thomas InstallMethod( \*, "for magma ring element, and rational", [ IsElementOfMagmaRingModuloRelations, IsRat ], ElmTimesRingElm ); InstallMethod( \*, "for rational, and magma ring element", [ IsRat, IsElementOfMagmaRingModuloRelations ], RingElmTimesElm ); InstallImmediateMethod( IsSmallList, IsBasis and HasBasisVectors and IsAttributeStoringRep, 0, function( B ) B:= BasisVectors( B ); if HasIsSmallList( B ) then return IsSmallList( B ); fi; TryNextMethod(); end ); InstallImmediateMethod( IsSmallList, IsBasis and HasUnderlyingLeftModule and IsAttributeStoringRep, 0, function( B ) B:= UnderlyingLeftModule( B ); if HasDimension( B ) then return Dimension( B ) <= MAX_SIZE_LIST_INTERNAL; fi; TryNextMethod(); end ); From thomas.breuer at math.rwth-aachen.de Wed Feb 23 12:24:07 2005 From: thomas.breuer at math.rwth-aachen.de (Thomas Breuer) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] addition of linear mappings Message-ID: Dear GAP Forum, Pasha Zusmanovich wrote > I am trying to add two linear mappings. > > gap> GAPInfo.Version; > "4.4.4" > gap> V := VectorSpace (Rationals, [[1,0],[0,1]]); > > gap> A := LeftModuleHomomorphismByImagesNC (V, V, Basis(V), > [[1,0],[0,0]]); > SemiEchelonBasis( , > [ [ 1, 0 ], [ 0, 1 ] ] ) -> [ [ 1, 0 ], [ 0, 0 ] ] > gap> B := LeftModuleHomomorphismByImagesNC (V, V, Basis(V), > [[0,0],[0,1]]); > SemiEchelonBasis( , > [ [ 1, 0 ], [ 0, 1 ] ] ) -> [ [ 0, 0 ], [ 0, 1 ] ] > > So far, so good. > > gap> A + B; > Error, and must have same (pre)image called from > ( ) called from read-eval-loop > Entering break read-eval-print loop ... > you can 'quit;' to quit to outer loop, or > you can 'return;' to continue > brk> > > Indeed, Image(A) does not coincide with Image(B), but is it needed to be > able to add two mappings? Image(A) and Image(B) are guaranteed to be > subspaces of V, so their elements can be added safely. If one removes > the corresponding checks from lib/vspchom.gi (lines with > > ImagesSource( map1 ) <> ImagesSource( map2 ) > > in two places), everything works like a charm: > > gap> A + B; > SemiEchelonBasis( , > [ [ 1, 0 ], [ 0, 1 ] ] ) -> [ [ 1, 0 ], [ 0, 1 ] ] > > Am I missing something? The observation is correct, the check for equal images is nonsense. (In fact other methods are installed for this situation which would return the mapping in question, but they are not called.) This problem will be fixed in the next version. Thanks very much for this report. All the best, Thomas From dutour at liga.ens.fr Thu Feb 24 11:38:07 2005 From: dutour at liga.ens.fr (Mathieu Dutour) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Stabilizer problem Message-ID: <20050224113807.GA52448@orge.ens.fr> Dear Gap Forum, I am computing with Integral Matrix Groups in GAP. The set on which those groups act is n-uples [x_1, ...., x_n] with 0<=x_i<1 The action of the matrix Group on this set is ActionMod1:=function(eVect, eMat) return List(OnPoints(eVect, eMat), x-> (NumeratorRat(x) mod DenominatorRat(x))/Denominator(x) ); end; Using that action, I want to use function Stabilizer and RepresentativeAction. Most of the time those functions works perfectly and I have no complaint. However, in some cases, the computation fails by lack of memory (for example in dimension 15 with the symmetry group of Lambda15 of order 41287680) Those cases arise when the stabilizer groups to be computed are small. What causes such problems? What possible solutions may be available? Mathieu -- Mathieu Dutour Sikiric Researcher in Math Tel. (+972)2 65 84 103 and Computer Science Fax. (+972)2 56 30 702 Einstein Institute of Mathematics E-mail: Mathieu.Dutour@ens.fr Hebrew University of Jerusalem http://www.liga.ens.fr/~dutour Israel From mjoao at classic.univ-ab.pt Fri Feb 25 14:35:54 2005 From: mjoao at classic.univ-ab.pt (Joao Araujo) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Direct product of semigroups In-Reply-To: <20050224113807.GA52448@orge.ens.fr> References: <20050224113807.GA52448@orge.ens.fr> Message-ID: I would like to compute the automorphism group of a direct product of (two) semigroups. Is it possible to do that with GAP? I thank in advance any help. Joao From laurent.bartholdi at epfl.ch Sun Feb 27 13:57:12 2005 From: laurent.bartholdi at epfl.ch (Laurent Bartholdi) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] performance of GAP Message-ID: hi there, prompted by a question on this forum [how does GAP perform compared to C code], i did the following experiment: gap> L := List([1..10^7],SignInt);; time; 4890 gap> L := List([1..10^7],i->SignInt(i));; time; 7330 gap> L := [];; for i in [1..10^7] do Add(L,SignInt(i)); od; time; 5480 I would naively have expected all 3 timings to be the same. is there a general rule of "fastest coding style": avoid creating function objects, but use the primitive "List()" as often as possible? be happy, laurent -- -- Laurent Bartholdi \ laurent.bartholdiepflch EPFL, IGAT, B?timent BCH \ T?l?phone: +41 21-6930380 CH-1015 Lausanne, Switzerland \ Fax: +41 21-6930385 From sal at dcs.st-and.ac.uk Sun Feb 27 15:39:39 2005 From: sal at dcs.st-and.ac.uk (Steve Linton) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Speed of GAP In-Reply-To: <039A0DCC3D66EE4AB9AF11E119287F154E6425@ms-afit-04.afit.edu> References: <039A0DCC3D66EE4AB9AF11E119287F154E6425@ms-afit-04.afit.edu> Message-ID: <20050227153939.227e3336@localhost.localdomain> Dear GAP Forum On Sun, 20 Feb 2005 13:03:10 -0500 "Bulutoglu Dursun A Civ AFIT/ENC" wrote: > I was wondering, if I compiled my GAP code using GAC is there a > guarantee that it will run as fast as the C version of my code? > Dursun. > No, I am afraid not. It is hard to be more precise without knowing what your code is doing, but in general GAC will no produce code that runs as fast as native C code. On the other hand, the compiled code can still draw on the full resources of the GAP kernel and library, which stand-alone C code cannot. Steve -- Steve Linton School of Computer Science & Centre for Interdisciplinary Research in Computational Algebra University of St Andrews Tel +44 (1334) 463269 http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278 From dutour at liga.ens.fr Mon Feb 28 08:01:20 2005 From: dutour at liga.ens.fr (Mathieu Dutour) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Cosets and intersection Message-ID: <20050228080120.GA82914@orge.ens.fr> Dear Gap forum, Suppose that xH is a right coset and G is a group. Then the intersection of xH and G is: --either emptyset [ ] --or a right coset of the form y (H inter G) One may want that the corresponding gap command take this into account, but this is not the case: V:=RightCoset(SymmetricGroup(4), (4,5)); Intersection(SymmetricGroup(5), V); returns a list of 24 elements. Is there a way to avoid the creation of a list? As a matter of fact, I just want to know if the intersection is empty or not and if not to have one element in the intersection. Mathieu -- Mathieu Dutour Sikiric Researcher in Math Tel. (+972)2 65 84 103 and Computer Science Fax. (+972)2 56 30 702 Einstein Institute of Mathematics E-mail: Mathieu.Dutour@ens.fr Hebrew University of Jerusalem http://www.liga.ens.fr/~dutour Israel From jjm at dcs.st-and.ac.uk Tue Mar 1 09:51:47 2005 From: jjm at dcs.st-and.ac.uk (John McDermott) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Fwd: Speed of GAP Message-ID: Begin forwarded message: > From: Alexander Hulpke > Date: 28 February 2005 17:27:25 GMT > To: gap-forum@gap-system.org > Subject: Re: Speed of GAP > > Dear GAP Forum, > > D. Bulutoglu asked: > >> I was wondering, if I compiled my GAP code using GAC is there a >> guarantee that it will run as fast as the C version of my code? > > There is no guarantee as you are comparing very different things. > (In particular it is often possible to improve runtime at the cost of > modularity or portability.) > > Not knowing your application also makes guessing hard, but here are > some > rules of thumb: > > If you can write everything you need in C (which in particular means > that > you have no need for the functionality provided by GAP beyond the basic > programming language, or that you are willing to recode all of this on > your > own in C) good C code is likely faster. In examples I have observed C > being > faster by a factor of between 10 and 1000 than pure GAP code. (As soon > as > notable time is spent in GAP kernel routines, such as matrix > multiplication or permutation multiplication the factor drops down to > under > 10.) > > Using the `gac' compiler will reduce this factor (again only > considering > code that does not use GAP kernel routines) to around 3 to 100. > > On the other hand coding in GAP is (at least for me) easily a similar > factor > faster than coding in C. > > If you need GAP functionality and you *must* have the speed of C your > best > bet is likely to have `gac' produce C code and then to hand > optimize/rewrite > this code. > > Finally I'd like to strongly second the opinion expressed already that > algorithmic improvements are likey to get you much further as any > programming tricks will ever do. > > All the best, > > Alexander Hulpke > > -- Colorado State University, Department of Mathematics, > Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA > email: hulpke@math.colostate.edu, Phone: ++1-970-4914288 > http://www.math.colostate.edu/~hulpke > > -- John McDermott Computing Officer & Purchase Officer School of Computer Science University of St Andrews North Haugh, St Andrews, Fife KY16 9SX tel +44 1334 463252 mob +44 7941 507531 From jjm at dcs.st-and.ac.uk Tue Mar 1 09:52:50 2005 From: jjm at dcs.st-and.ac.uk (John McDermott) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Fwd: stabilizer problem Message-ID: Begin forwarded message: > From: Alexander Hulpke > Date: 28 February 2005 18:30:42 GMT > To: gap-forum@gap-system.org > Subject: Re: stabilizer problem > > Dear Gap Forum, > > Mathieu Dutour wrote: > >> I am computing with Integral Matrix Groups in GAP. > >> The action of the matrix Group on this set is > [...] >> Using that action, I want to use function Stabilizer > [...] >> However, in some cases, the computation fails by lack of >> memory (for example in dimension 15 with the symmetry group >> of Lambda15 of order 41287680) Those cases arise when the >> stabilizer groups to be computed are small. > > Unless the group is a permutation group acting on points, sets, > elements or > subgroups (in which case a backtrack algorithm is used) the > calculation of a > stabilizer (or representative) usually works by enumerating the orbit. > > If the stabilizer is small this orbit is large and this can cause you > running out of memory. > > The only way around it (apart from getting more memory or recoding to > save > storage space) is to reduce the stabilizer computation into smaller > steps by > finding an intermediate subgroup U such that Stab > Typically such an U can be found as stabilizer under another > ``coarser'' > action. Sometimes it can be written down from the structure of the > domain > (say a subspace stabilizer in GL), sometimes it is found by > considering an > action that is not necessarily faithful (projective action, reduction > modulo > a prime or similar). Which action to use concretely will depend very > much on > the concrete case. > > In your situation, considering reduction modulo a prime that does not > occur > in the denominators might be a first approach. > > Best wishes, > > Alexander Hulpke > > -- Colorado State University, Department of Mathematics, > Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA > email: hulpke@math.colostate.edu, Phone: ++1-970-4914288 > http://www.math.colostate.edu/~hulpke > > -- John McDermott Computing Officer & Purchase Officer School of Computer Science University of St Andrews North Haugh, St Andrews, Fife KY16 9SX tel +44 1334 463252 mob +44 7941 507531 From wdj at usna.edu Tue Mar 1 14:57:21 2005 From: wdj at usna.edu (David Joyner) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Re: [GAP Support] using gap from another program In-Reply-To: References: Message-ID: <422482D1.2080101@usna.edu> Nicolas: A very simple example of a python-gap interface is at http://cadigweb.ew.usna.edu/~wdj/gap/ I don't know java, but perhaps that example will help you. I'm cross-posting to the Forum, in case there might be other GAP users interested as well. - David Joyner ++++++++++++++++++++++++++++ Nicolas Demoulin wrote: > Hi, > I am a student in computer science from University College Cork and I am > doing a project on Symmetry Breaking in CSP. I have already used gap but > what I would like to do know is to insert gap in my main program which > is written in Java. And I saw in the faq that : > > "What you can do is to run GAP in a child process and communicate with > it using pipes, pseudo-ttys, UNIX FIFOs or some similar device. We have > done this successfully in a number of projects, and you can contact the > support list for more detailed advice if you want to go down this route" > > So if you can give me advice or examples of communication between gap > and another program, it will help me very much. > > Thank you to have taken time to read me > Best Regards > > Nicolas Demoulin > > _________________________________________________________________ > Nouveau MSN Hotmail : cr?ez une adresse @hotmail.fr qui vous ressemble ! > http://www.msn.fr/newmsnhotmail > > _______________________________________________ > Support mailing list > Support@gap-system.org > http://mail.gap-system.org/mailman/listinfo/support From laurent.bartholdi at epfl.ch Tue Mar 1 15:43:52 2005 From: laurent.bartholdi at epfl.ch (Laurent Bartholdi) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] musings on the empty set Message-ID: hi, i'm writing some code which occasionally constructs vector spaces of dimension 0, and i'm a bit surprised to see that these have to be handled specially. to wit: gap> VectorSpace(GF(2),[]); Error, no method found! For debugging hints type ?Recovery from NoMethodFound ... gap> VectorSpace(GF(2),[Zero(r)]); # r is an (infinite-dimensional) ring over GF(2) now, a bit worse: gap> NullspaceMat([[0],[0]]); # zero map: Z^2 -> Z^1 [ [ 1, 0 ], [ 0, 1 ] ] gap> NullspaceMat([[],[]]); # zero map: Z^2 -> Z^0 Error, no method found! For debugging hints type ?Recovery from NoMethodFound i agree that there are simple workarounds for the above problems; it would just make my code shorter and simpler if they could be handled by GAP. best, laurent -- Laurent Bartholdi \ laurent.bartholdiepflch EPFL, IGAT, B?timent BCH \ T?l?phone: +41 21-6930380 CH-1015 Lausanne, Switzerland \ Fax: +41 21-6930385 From ally at dcs.gla.ac.uk Tue Mar 1 17:26:37 2005 From: ally at dcs.gla.ac.uk (Alastair Donaldson) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Re: [GAP Support] using gap from another program In-Reply-To: <422482D1.2080101@usna.edu> References: <422482D1.2080101@usna.edu> Message-ID: I use GAP from JAVA by launching GAP in quiet mode as a slave process, then communicating with GAP using a buffered writer (which GAP thinks is standard input) and a buffered reader (which is where GAP's standard output goes to). Here's a trivial bit of JAVA code which will print out the size of the group generated by (1,2)(3,4) and (5,6): try { // Launch GAP in 'quiet' mode Process p = Runtime.getRuntime().exec("/usr/local/data/group_files/newinstall/gap-linux -L gapworkspace -q"); BufferedReader br = new BufferedReader(new InputStreamReader(p.getInputStream())); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(p.getOutputStream())); // Send something to GAP bw.write("G := Group((1,2)(3,4),(5,6));;\n"; bw.write("Size(G);\n"); bw.flush(); // You need to do this before you can read anything back from GAP System.out.println("The size of the group is " + br.readLine()); } catch (Exception e) { System.out.println("Error executing GAP"); System.out.println(e); e.printStackTrace(); System.out.println(br.readLine()); System.exit(1); } } I have some more complex examples where my JAVA program does some real computation using GAP. I've found it really tricky to get GAP to synchronise with my programs since GAP can produce rather unpredictable output sometimes. -Alastair On Tue, 1 Mar 2005, David Joyner wrote: > Nicolas: > > A very simple example of a python-gap interface is at > http://cadigweb.ew.usna.edu/~wdj/gap/ > I don't know java, but perhaps that example will help you. > > I'm cross-posting to the Forum, in case there might be > other GAP users interested as well. > > - David Joyner > > ++++++++++++++++++++++++++++ > > > > Nicolas Demoulin wrote: > > Hi, > > I am a student in computer science from University College Cork and I am > > doing a project on Symmetry Breaking in CSP. I have already used gap but > > what I would like to do know is to insert gap in my main program which > > is written in Java. And I saw in the faq that : > > > > "What you can do is to run GAP in a child process and communicate with > > it using pipes, pseudo-ttys, UNIX FIFOs or some similar device. We have > > done this successfully in a number of projects, and you can contact the > > support list for more detailed advice if you want to go down this route" > > > > So if you can give me advice or examples of communication between gap > > and another program, it will help me very much. > > > > Thank you to have taken time to read me > > Best Regards > > > > Nicolas Demoulin > > > > _________________________________________________________________ > > Nouveau MSN Hotmail : cr?ez une adresse @hotmail.fr qui vous ressemble ! > > http://www.msn.fr/newmsnhotmail > > > > _______________________________________________ > > Support mailing list > > Support@gap-system.org > > http://mail.gap-system.org/mailman/listinfo/support > > > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum > From jalal_molavi at yahoo.com Wed Mar 2 12:59:15 2005 From: jalal_molavi at yahoo.com (jalal molavi) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] semigroup of some order Message-ID: <20050302125915.95262.qmail@web42107.mail.yahoo.com> Dear gap- forum. I have a question . Is there any classification about semigroup such as group. in the other hand how many semigroups are there of size n where n is natural number. i need all semigroups of size less than 10. if any one have usefull information i am very thankful to know that. Best regards. --------------------------------- Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now From costanti at science.unitn.it Wed Mar 2 14:40:13 2005 From: costanti at science.unitn.it (Marco Costantini) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] semigroup of some order In-Reply-To: <20050302125915.95262.qmail@web42107.mail.yahoo.com> References: <20050302125915.95262.qmail@web42107.mail.yahoo.com> Message-ID: <200503021540.13136.costanti@science.unitn.it> Dear jalal molav, there is some information and some links at http://mathworld.wolfram.com/Semigroup.html : "The numbers of nonisomorphic semigroups of orders 1, 2, ... are 1, 5, 24, 188, 1915, ... (Sloane's A027851)." Best regards, Marco Costantini On Wednesday 02 March 2005 13:59, jalal molavi wrote: > Is there any classification about semigroup such as group. > in the other hand how many semigroups are there of size n > where n is natural number. > i need all semigroups of size less than 10. > if any one have usefull information i am very thankful to know that. From Goetz.Pfeiffer at NUIGalway.ie Wed Mar 2 15:13:28 2005 From: Goetz.Pfeiffer at NUIGalway.ie (Goetz Pfeiffer) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] semigroup of some order In-Reply-To: <20050302125915.95262.qmail@web42107.mail.yahoo.com> References: <20050302125915.95262.qmail@web42107.mail.yahoo.com> Message-ID: <20050302151327.GA19383@congres-043.epfl.ch> Dear jalal molavi, dear GAP Forum, according to S. Satoh, K. Yama\ and\ M. Tokizawa, Semigroup Forum {\bf 49} (1994), no.~1, 7--29; MR1272859 (95i:20080) there are $1,843,120,128$ non-equivalent semigroups of order 8. Enjoy! Goetz Pfeiffer On Wed, Mar 02, 2005 at 12:59:15PM +0000, jalal molavi wrote: > Dear gap- forum. > I have a question . > Is there any classification about semigroup such as group. > in the other hand how many semigroups are there of size n > where n is natural number. > i need all semigroups of size less than 10. > if any one have usefull information i am very thankful to know that. > Best regards. > > > --------------------------------- > Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum ------------------------------------------------------------------------- Goetz.Pfeiffer@NUIGalway.ie http://schmidt.nuigalway.ie/~goetz/ National University of Ireland, Galway. phone +353-91-49-3591 From Jean-Eric.Pin at liafa.jussieu.fr Wed Mar 2 16:31:30 2005 From: Jean-Eric.Pin at liafa.jussieu.fr (Jean-Eric Pin) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] semigroup of some order In-Reply-To: <20050302125915.95262.qmail@web42107.mail.yahoo.com> References: <20050302125915.95262.qmail@web42107.mail.yahoo.com> Message-ID: Dear Jalal Molavi, To my knowledge, only the number of non-isomorphic commutative semigroups of order <= 10 is known. See Pierre Antoine Grillet, Computing Finite Commutative Semigroups: Part II Semigroup Forum 67, Number 2, 2003, 159-184 (and Part III, 185-204) For general semigroups, the larger known order seems to be 8 Semigroups of order 8, S. Satoh, K. Yama, and M. Tokizawa. Semigroup Forum 49, 1994, pages 7-29. Best regards, Jean-Eric Pin At 12:59 +0000 2/03/05, jalal molavi wrote: >Dear gap- forum. >I have a question . >Is there any classification about semigroup such as group. >in the other hand how many semigroups are there of size n >where n is natural number. >i need all semigroups of size less than 10. >if any one have usefull information i am very thankful to know that. >Best regards. From jmcd at dcs.st-and.ac.uk Fri Mar 4 10:16:41 2005 From: jmcd at dcs.st-and.ac.uk (John McDermott) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Fwd: [GAP Support] char Table and LLL Message-ID: <3070bc50cb92d1feb8c9e1e843069eac@dcs.st-and.ac.uk> This was sent to the Support list and was intended for the Forum as well, but was mis-addressed: Begin forwarded message: > From: "Previtali Andrea" > Date: 3 March 2005 18:16:15 GMT > To: , , > > Cc: Subject: [GAP Support] char Table and LLL > > Dear Thomas, > I'm trying to get the character table of PSp(4,9) using your > suggestions but > I get a weird answer: > > tbl:= rec();; > tbl.Size:=74;; > tbl.UnderlyingCharacteristic:= 0;; > tbl.SizesConjugacyClasses:= [ 1, 3321, 298890, 3280, 3280, 236160, > 295200, 597780, 597780, 26900100, 478224, 478224, 478224, 478224, > 34432128, > 265680, 265680, 5313600, 5313600, 10627200, > 23911200, 597780, 597780, 21520080, 21520080, 53800200, 21254400, > 21254400, > 478224, 478224, 17216064, 17216064, 21520080, 21520080, 34432128, > 23911200, > 23911200, > 47822400, 19128960, 19128960, 19128960, 19128960, 38257920, 38257920, > 43040160, 43040160, 43040160, 43040160, 23911200, 23911200, 23911200, > 23911200, 19128960, > 19128960, 19128960, 19128960, 43040160, 43040160, 43040160, 43040160, > 43040160, 43040160, 43040160, 43040160, 41990400, 41990400, 41990400, > 41990400, 41990400, > 41990400, 41990400, 41990400, 41990400, 41990400 ];; > tbl.OrdersClassRepresentatives:= [ 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, > 5, 5, 5, > 5, 5, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, > 10, 12, > 12, 12, 15, 15, 15, 15, 15, 15, 20, 20, 20, > 20, 24, 24, 24, 24, 30, 30, 30, 30, 40, 40, 40, 40, 40, 40, 40, 40, > 41, 41, > 41, 41, 41, 41, 41, 41, 41, 41 ];; > tbl.Identifier:= "PSp(4,9)";; # for printing > ConvertToLibraryCharacterTableNC( tbl );; > vecs:=[ > [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, 1, > 1, 1, 1, > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], > [ 369, -31, 9, 45, 45, 9, 0, 1, 9, 1, 9, -1, -1, 9, -1, 5, 5, -4, > -4, 5, > 0, 1, 1, -1, -1, 1, 0, 0, 9, 9, -1, -1, -1, -1, -1, 1, 1, 0, 0, 0, 0, > 0, -1, > -1, -1, > 1, -1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, -1, -1, -1, -1, 1, 0, > 0, 0, 0, > 0, 0, 0, 0, 0, 0 ], > [ 450, 50, 10, 45, 45, 0, 9, 10, 10, 2, 0, 0, 0, 0, 0, 5, 5, 5, 5, > -4, 1, > 10, 10, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, > 0, 0, > 0, 0, > 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, > -1, -1, > -1, -1, -1, -1 ] > > ] > ;; > LLL( tbl, vecs ); > > PRODUCES THIS ANSWER !!!!!!! > > rec( irreducibles := [ ], remainders := [ VirtualCharacter( > CharacterTable( > "PSp(4,9)" ), [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, > 1, > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, 1, > 1, > 1, 1, 1, 1 ] ), VirtualCharacter( CharacterTable( "PSp(4,9)" > ), [ > 369, -31, 9, 45, 45, 9, 0, 1, 9, 1, -1, 9, 9, -1, -1, 5, 5, -4, -4, 5, > 0, 1, > 1, > -1, -1, 1, 0, 0, 9, 9, -1, -1, -1, -1, -1, 1, 1, 0, 0, 0, 0, > 0, -1, > -1, 1, -1, 1, -1, 1, 1, 1, 1, 0, 0, 0, 0, -1, 1, 1, 1, -1, -1, 1, -1, > 0, 0, > 0, > 0, 0, 0, 0, 0, 0, 0 ] ), VirtualCharacter( CharacterTable( > "PSp(4,9)" ), [ 450, 50, 10, 45, 45, 0, 9, 10, 10, 2, 0, 0, 0, 0, 0, > 5, 5, 5, > 5, -4, 1, > 10, 10, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, > 0, 0, 0, > 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, > -1, > -1, > -1, -1, -1, -1, -1, -1 ] ), VirtualCharacter( CharacterTable( > "PSp(4,9)" ), [ 820, 20, -20, 91, 91, 10, 10, 8, 0, 0, 0, 10, 10, 0, > 0, 11, > 11, 2, 2, > 2, -2, 10, 10, 0, 0, -2, 1, 1, 10, 10, 0, 0, 0, 0, 0, -1, > -1, 0, 1, > 1, 1, 1, 0, 0, -2, 0, -2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, > 0, 0, > 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ) ], norms := [ 860803200/37, > 860803200/37, 860803200/37, 860803200/37 ] ) > > WHILE > > > List([1..3],x->List([1..3],y->Sum(List([1..74],i- > >SizesConjugacyClasses(tbl)[ > i]*vecs[x][i]*vecs[y][i])))); > > PRoVIDES > > > [ [ 1721606400, 0, 0 ], [ 0, 1721606400, 0 ], [ 0, 0, 1721606400 ] ] > > proving that vecs is a piece of an orthonormal basis for class > functions of > PSp(4,9) (whose order is 1721606400) > > I'm really puzzled by the norm assigned to all v in vecs, in > particular to > the one correspondign to the trivial character of G. > > > If you have any hint why this happens, please let me know. > > bye > > > > _______________________________________________ > Support mailing list > Support@gap-system.org > http://mail.gap-system.org/mailman/listinfo/support > > -- John McDermott Computing Officer & Purchase Officer School of Computer Science University of St Andrews North Haugh, St Andrews, Fife KY16 9SX tel +44 1334 463252 mob +44 7941 507531 From l.h.soicher at qmul.ac.uk Fri Mar 4 11:36:35 2005 From: l.h.soicher at qmul.ac.uk (Leonard Soicher) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Maths/CS/EE Academic Felowships at QMUL Message-ID: <20050304113635.GA17104@mrcpc02.maths.qmul.ac.uk> Dear GAP-Forum, The following jobs may be of interest to you, especially if you are on the Maths/CS interface. Note that the closing date is very soon. Best wishes, Leonard Academic fellowships at Queen Mary, University of London -------------------------------------------------------- The College has just advertised three inter-disciplinary academic fellowships in Mathematics, Computer Science and Electrical Engineering. These are positions which would normally lead to permanent appointments. The advertisement, posted in 16 February, can be found at http://www.admin.qmul.ac.uk/humanresources/vacancies/academic/ The closing date is 9 March, and the salary in the range GBP 25777-38017. Please circulate this announcement! From sal at dcs.st-and.ac.uk Fri Mar 4 14:34:18 2005 From: sal at dcs.st-and.ac.uk (Steve Linton) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] GAP Headquarters replaced by four GAP Centres Message-ID: <20050304143418.377b6696@localhost.localdomain> Dear GAP Forum, The GAP Council and the GAP developers have agreed that status and responsibilities of "GAP Headquarters" should be passed to an equal collaboration of a number of " Centres", where there is permanent staff involvement and an element of collective or organisational commitment; while fully recognising the vital contributions of many individuals outside those Centres. The Centres will work together, with outside individuals, to sustain and develop GAP, concentrating in particular on coordination and on those tasks which are not naturally a part of anyone's research programme, but are needed "for the general good". To these ends, the Centres may set up Working Groups, made up as appropriate of Centre representatives and/or invited individuals, to perform particular tasks and reach decisions on particular questions. At the present time (February 2005), Centres in the following places have agreed to cooperate in this way: * Aachen, * Braunschweig, * Fort Collins, and * St Andrews. This list may change, if new Centres emerge, or existing ones withdraw. Representatives of all the Centres can be contacted via the usual support email address support@gap-system.org. Some further details, including links to Centres' web sites and some of the types of activities the Centres expect to undertake will appear on the GAP web site shortly. Steve Linton Edmund Robertson -- Steve Linton School of Computer Science & Centre for Interdisciplinary Research in Computational Algebra University of St Andrews Tel +44 (1334) 463269 http://www.dcs.st-and.ac.uk/~sal Fax +44 (1334) 463278 From thomas.breuer at math.rwth-aachen.de Tue Mar 8 09:32:31 2005 From: thomas.breuer at math.rwth-aachen.de (Thomas Breuer) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Fwd: [GAP Support] char Table and LLL Message-ID: Dear GAP Forum, Andrea Previtali wrote > I'm trying to get the character table of PSp(4,9) using your > suggestions but > I get a weird answer: > > tbl:= rec();; > tbl.Size:=74;; > tbl.UnderlyingCharacteristic:= 0;; > tbl.SizesConjugacyClasses:= [ 1, 3321, 298890, 3280, 3280, 236160, > [...] > ConvertToLibraryCharacterTableNC( tbl );; > vecs:=[ > [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > [...] > ] > ;; > LLL( tbl, vecs ); > > PRODUCES THIS ANSWER !!!!!!! > > rec( irreducibles := [ ], remainders := [ VirtualCharacter( > [...] > 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ) ], norms := [ 860803200/37, > 860803200/37, 860803200/37, 860803200/37 ] ) The problem is that the `Size' attribute of a character table refers to the order of the underlying group and not to the dimension of the matrix of irreducible characters; the value is used in the computations of scalar products of characters for this table. In fact, many of those attributes and properties of groups for which the value can be computed from the information in the character table object are defined also for character tables. (See the chapter "Character Tables" in the GAP Reference Manual, in particular the section "Attributes and Properties of Character Tables".) All the best, Thomas From danaf at fea.st Tue Mar 8 16:13:32 2005 From: danaf at fea.st (Dan Rossul) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Urgent Issue on GAP... Message-ID: <1110298412.1969.217837658@webmail.messagingengine.com> Dear all, When I try the command: gap> g:=Group((1)(2)(3,4)); Syntax error: ) expected I suppose GAP should understand (1)(2)(3,4) = (3,4) Of course if gap> gap> g:=Group((3,4)); Group([ (3,4) ]) It is prefectly fine..... I am not sure if GAP doesn't understand (1)(2)(3,4) = (3,4) or it is a real Syntax error: ) expected, if Syntax error where should I add the )? Thanks all Best Regards, Dan From justin at mac.com Tue Mar 8 16:45:31 2005 From: justin at mac.com (Justin Walker) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Urgent Issue on GAP... In-Reply-To: <1110298412.1969.217837658@webmail.messagingengine.com> References: <1110298412.1969.217837658@webmail.messagingengine.com> Message-ID: Hi, all, On Mar 8, 2005, at 8:13, Dan Rossul wrote: > When I try the command: > > gap> g:=Group((1)(2)(3,4)); > Syntax error: ) expected On input, "(1)(2)..." is invalid. The parser expects a '*' to be used; juxtaposition does not mean "group operation". In addition, it appears that the GAP engine would prefer that you not mention "1"-cycles (your example with inserted '*'s causes more serious complaints). Regards, Justin -- Justin C. Walker, Curmudgeon-At-Large * Institute for General Semantics | If you're not confused, | You're not paying attention *--------------------------------------*-------------------------------* From Sergei.Haller at math.uni-giessen.de Tue Mar 8 17:19:46 2005 From: Sergei.Haller at math.uni-giessen.de (Sergei Haller) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Urgent Issue on GAP... In-Reply-To: <1110298412.1969.217837658@webmail.messagingengine.com> References: <1110298412.1969.217837658@webmail.messagingengine.com> Message-ID: On Tue, 8 Mar 2005, Dan Rossul (DR) wrote: DR> gap> g:=Group((1)(2)(3,4)); DR> Syntax error: ) expected DR> DR> I suppose GAP should understand (1)(2)(3,4) = (3,4) seems that GAP interprets (1) as the integer 1 in parenthesis: gap> (1) in Integers; true gap> (1) in SymmetricGroup(4); false on the other hand, an expression like "(3,4)(1)" is interpreted in the way you expect it. for your purpose, you might try something like "PermList([1,2,4,3]);" DR> [...] if Syntax error where should I add the )? if you read the full error message: gap> g:=Group((1)(2)(3,4)); Syntax error: ) expected g:=Group((1)(2)(3,4)); ^ gap> then you can see an arrow pointing to the expected position. Sergei -- -------------------------------------------------------------------- -?) eMail: Sergei.Haller@math.uni-giessen.de /\\ -------------------------------------------------------------------- _\_V Be careful of reading health books, you might die of a misprint. -- Mark Twain From danaf at fea.st Tue Mar 8 17:40:37 2005 From: danaf at fea.st (Dan Rossul) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Urgent Issue on GAP... In-Reply-To: References: <1110298412.1969.217837658@webmail.messagingengine.com> Message-ID: <1110303637.10931.217846200@webmail.messagingengine.com> Yes I dont understand why (3,4)(1) would be fine not (1)(3,4) Is there any method to make (1)(3,4) executable, no error in GAP? thanks! ----- Original message ----- From: "Sergei Haller" To: forum@gap-system.org Date: Tue, 8 Mar 2005 18:19:46 +0100 (CET) Subject: Re: [GAP Forum] Urgent Issue on GAP... On Tue, 8 Mar 2005, Dan Rossul (DR) wrote: DR> gap> g:=Group((1)(2)(3,4)); DR> Syntax error: ) expected DR> DR> I suppose GAP should understand (1)(2)(3,4) = (3,4) seems that GAP interprets (1) as the integer 1 in parenthesis: gap> (1) in Integers; true gap> (1) in SymmetricGroup(4); false on the other hand, an expression like "(3,4)(1)" is interpreted in the way you expect it. for your purpose, you might try something like "PermList([1,2,4,3]);" DR> [...] if Syntax error where should I add the )? if you read the full error message: gap> g:=Group((1)(2)(3,4)); Syntax error: ) expected g:=Group((1)(2)(3,4)); ^ gap> then you can see an arrow pointing to the expected position. Sergei -- -------------------------------------------------------------------- -?) eMail: Sergei.Haller@math.uni-giessen.de /\\ -------------------------------------------------------------------- _\_V Be careful of reading health books, you might die of a misprint. -- Mark Twain _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum From Sergei.Haller at math.uni-giessen.de Tue Mar 8 18:10:42 2005 From: Sergei.Haller at math.uni-giessen.de (Sergei Haller) Date: Fri Apr 8 15:25:48 2005 Subject: [GAP Forum] Urgent Issue on GAP... In-Reply-To: References: <1110298412.1969.217837658@webmail.messagingengine.com> Message-ID: On Tue, 8 Mar 2005, Justin Walker (JW) wrote: JW> On Mar 8, 2005, at 8:13, Dan Rossul wrote: JW> JW> > When I try the command: JW> > JW> > gap> g:=Group((1)(2)(3,4)); JW> > Syntax error: ) expected JW> JW> On input, "(1)(2)..." is invalid. The parser expects a '*' to be used; JW> juxtaposition does not mean "group operation". well, it does for permutations, so (3,4)(5,6) or (3,4)(2) are perfectly valid. The thing is that GAP s