This file contains the mails sent to the GAP forum in January-March 1994.

Name                Email address                           Mails   Lines
Steve Linton        sl25@cus.cam.ac.uk                         11     256
Joachim Neubueser   Joachim.Neubueser@Math.RWTH-Aachen.DE      10     715
Martin Schoenert    Martin.Schoenert@Math.RWTH-Aachen.DE        8     402
Frank Celler        Frank.Celler@Math.RWTH-Aachen.DE            8     372
Alexander Hulpke    Alexander.Hulpke@Math.RWTH-Aachen.DE        6     397
Jacob Hirbawi       jcbhrb@cerf.net                             5     152
Volkmar Felsch      Volkmar.Felsch@Math.RWTH-Aachen.DE          3     265
Dima Pasechnik      dima@maths.uwa.edu.au                       3     225
Harald Boegeholz    hwblist@machnix.mathematik.uni-stuttgart.de 3      93
Thomas Breuer       Thomas.Breuer@Math.RWTH-Aachen.DE           3      73
Philip Osterlund    osterlu@s5.math.umn.edu                     2     110
Derek Holt          dfh@maths.warwick.ac.uk                     2      75
Robert Beals        beals@sisters.cs.uoregon.edu                2      54
Michael Cherkassoff mikec@math.ubc.ca                           2      46
Gap Students        studgap@twi.tudelft.nl                      2      44
John R. Neil        neil@dehn.mth.pdx.edu                       1      88
Larsonstolafedu     larson@stolaf.edu                           1      67
Steve Fisk          fisk@polar.bowdoin.edu                      1      63
Paul Igodt          paul.igodt@kulak.ac.be                      1      59
Meinolf Geck        Meinolf.Geck@Math.RWTH-Aachen.DE            1      58
M Taoufik Karkar    karkar@tnearn.bitnet                        1      50
Goetz Pfeiffer      Goetz.Pfeiffer@Math.RWTH-Aachen.DE          1      41
Imre Simon          is@ime.usp.br                               1      36
A E Caranti         caranti@volterra.science.unitn.it           1      34
D. Paul Benjamin    dpb@a.cs.okstate.edu                        1      30
Mark Short          short@jordan.murdoch.edu.au                 1      17
Thomas D Bending    t.d.bending@qmw.ac.uk                       1      16
Jie Wang            wang@maths.uwa.edu.au                       1       9
Michael J. Falk     mjf@odin.math.nau.edu                       1       7
Catherine Greenhill greenhil@maths.ox.ac.uk                     1       6
Said Najati Sidki   sidki@alpha.mat.unb.br                      1       4

This  file is in Berkeley mail drop format, which means you can read this
file with 'mail -f <name-of-the-file>'  or 'mailx -f <name-of-the-file>'.
It is also possible however to read this file with any text editor.



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan  6 10:36:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 06 Jan 94 10:36 +0100
Subject:        New attempt

Dear forum members,      

Let me first apologise  that without prior  warning the forum has  not
been working  properly  for  a few weeks.     In the course   of  some
reconfiguration of  our computers and service  software the mailer for
the forum has been replaced in  order to get better protection against
unwanted bouncing of mail etc. .  However it has  taken more time than
anticipated to  get over some difficulties with  the new  mailer. As a
result of this some incoming  mail for the forum  has waited some time
until it is sent round now and also a  letter of mine has reached some
of you more than  once and in truncated  form.   I append this  letter
again and hope that it will  now reach all  in full.  We hope that now
the forum is back to order. We think that no mail to the forum has got
lost in this process, but if this should  be the case with some letter
of yours would you please be so kind to send it in again now.

Let me also answer in  public and again  with apologies some questions
and  (quite justified) complaints  that have been sent  a few times to
gap-trouble:

There  has been no send-out of  patches for GAP  3.3 so far, the first
one will come only after the end of this month.

It always  takes  some time until  a new  GAP  version or a   patch is
available from all servers listed in the GAP-Announcement. This is not
completely  under  our  control   but needs  the    help of  the local
adminstrators of these servers.  We apologize for inconvenience caused
by trying without   success  to obtain  announced  releases  from some
servers, on which it became available only later. Please try to obtain
the software in such cases from the Aachen server.

For some of the ports to other computers we rely  on the generous help
of colleagues since we do not have these computers easily available to
us here.   This  is in particular  so with  the port  to MAC's. Please
understand that these  therefore will as  a rule become available only
with  a certain delay, since  the port has  to be done  by these third
parties after the  release  of the new  version  and they may well  be
occupied with more urgent own work just at that moment.

Wishing you a good 1994 and in spite of  all listed above some further
fun with GAP    
                       Joachim Neubueser

Here then once more and hopefully finally my letter

======================================================================
In his letter to the GAP-forum of Dec. 13, Jeffrey Hsu asked:
 
> I'm interested in teaching abstract algebra with GAP.  Are there any
> course  material available for  this purpose.   I read in manual.dvi
> that there were several in preperation.   What's the status of these
> efforts    and has  students  found   them  helpful as supplementary
> exercises?

The short passage  in the preface of the  manual, which Jeffrey Hsu is
quoting, refers to a discussion in the GAP-forum in 1992, when Michael
K. Johnson and Donald L. Kreher reported about plans to develop course
material for  the use of GAP  for  teaching abstract algebra.   I have
also given  a description of the situation  in Aachen in the GAP-forum
at that time. For convenience I append the  three letters to this one.
(Please note  at this occasion that  all non-trivial correspondance in
the  GAP-forum is  available  in the   GAP-distribution  in the  'etc'
subdirectory.)

In the   meantime  we have held the    workshop on Computational Group
Theory during the Groups '93 conference in Galway this August and this
included 'practical exercises' using GAP, for  which we had prepared a
set of problems and solutions. We intend to supplement this by further
problems, organise these problems and solutions in a standard form and
make   the  whole   file   available through  ftp   together with  GAP
eventually; at present, if somebody wants to have it, we can send this
collection in its not completely well-organised form without warranty.

I would very much  welcome if Michael K. Johnson  and Donald L. Kreher
as well as others who might have used GAP in teaching could tell us in
the GAP-forum about  their experience   and in  fact, if  such  exists
meanwhile, could make course material available.

Kind regards     Joachim Neubueser
==================================================================
Michel K. Johnson's letter:

Date: Sat, 31 Oct 92 00:37:32 +01
From: johnsonm@stolaf.edu (Michael K Johnson)
Subject: Teaching Abstract Algebra with GAP


A few of us at St. Olaf are writing a  Laboratory Manual for GAP which
is intended   to complement (although  it does  not  /require/) Joseph
Gallian's  text Contemporary_Abstract_Algebra.  We  would like to know
if anyone  else is using  GAP to teach undergraduate abstract algebra,
and if so, what pedagogical materials you use or have developed.

If anyone is using GAP in this way, please contact me.

michaelkjohnson

=====================================================================
Donald L. Kreher's letter:

Date: Mon, 2 Nov 92 13:35:49 +0100
From: kreher@math.mtu.edu (Donald L. Kreher)
Subject: Re: Teaching Abstract Algebra with GAP

> A few of us at St. Olaf are writing a Laboratory Manual for GAP which
> is intended to complement (although it does not /require/) Joseph
> Gallian's text Contemporary_Abstract_Algebra.  We would like to know
> if anyone else is using GAP to teach undergraduate abstract algebra,
> and if so, what pedagogical materials you use or have developed.
> If anyone is using GAP in this way, please contact me. 
> michaelkjohnson

I was hoping to  do rougghly the same,  but with Rotman's Group Theory
Text.  I would be very  interested in seeing  your Lab Manual. Also in
particular  I would  be  interested in  any  other recomendations from
persons  using  GAP  in Graduate   Group Theory,  Algebra  or Discrete
Mathematics Courses.

Don Kreher
Kreher@math.mtu.edu

========================================================================
My letter:

Subject: Use of GAP in teaching
Date: Mon, 2 Nov 92 17:05:28 MET

Michael K. Johnson and Don Kreher report  that they are working on the
development  of course  material using GAP and ask where else  work of
this kind is done.

It will be  no  surprise that  we do use GAP  in  teaching  in Aachen,
although we have not written a laboratory  manual or systematic course
material. In order to explain the situation it should perhaps first be
explained  that  the contents  of  courses  is less  fixed  in  German
universities than it usually seems to be in  the US, that  is, each of
us rather goes his own way in teaching a  course on group theory, say,
and may also  change  his course from one  year to another. With  this
reservation made, one can say  that we have perhaps  two main lines in
integrating algorithmic  methods and the  use  of a system such as GAP
into such a course.

In one line, which I have followed two years ago, I gave a course that
was entitled  "Groups,  theory and algorithms"  parts I  and II over a
full  year, in which algorithmic aspects and methods were closely knit
into the theory, e.g. the course - that assumed a course on Algebra I
which gave the basics up to  Jordan-Hoelder  and Sylow -  started with
free groups and presentations and alongside with the theory introduced
computational  methods  such  as  Todd-Coxeter, Reidemeister-Schreier,
Low-index  and   IMD.    These   then  were   treated   through   easy
hand-calculations as well  as examples using programs in the exercises
( at  that  time  we  had partially  to  resort to  SPAS  because  the
algorithms were not all in GAP yet, but they will be in GAP 3.2  to be
released soon ).  In a  similar way  then permutation  groups, soluble
groups  and  p-groups  were  treated.  This course was  followed  by a
further year on  representation  theory,  of which I  gave  the  first
semester  on ordinary representation theory, again interlacing  theory
with computational  methods mainly for  charactertheory,  again  using
GAP, which provides quite a lot of possibilities in this field.

For  these  courses we have files  with the weekly exercises given  to
the students and some percentage of these involve the use of  GAP.  If
somebody is interested  to  get these  ( in German  and not  specially
organized for export ) we will be happy to send them.

In another  setup,  which  we follow this  year,  my colleague,  Prof.
Pahlings  will  give a more  traditional  one-semester course on group
theory,  in  which  again GAP may be used occasionally,  but more as a
black box, while most of the algorithmic  aspects will be treated in a
separate course by me next  summer, in which GAP will naturally play a
more central  role.  Prof  Pahlings  meanwhile will  already  go on to
representation theory next summer.

We have  followed that line also some  years ago,  both  seem  to have
advantages and  drawbacks and I really cannot say that I recommend one
of them as the better setup.

Generally we tend to allow or even  recommend the use  of GAP also  in
other  courses such as the introductory  algebra course.  We hope that
for  students, who  nowadays tend to  come being pretty  well used  to
PASCAL or the like, using GAP is not so difficult, so in these courses
usually  we have made no attempt with a systematic introduction to GAP
but  rather have "let things happen" and  this is perhaps even so with
the above-mentioned courses.  But  I am sure  we  could do better than
that and  hence I would  be  very interested  to  get whatever  course
material is developed. I would also very much welcome if such material
- perhaps  after  some test  with students - could be  made  generally
available alongside with GAP.

Joachim Neubueser



From larson@stolaf.edu Thu Jan  6 16:54:00 1994
From:           "Larsonstolafedu" <larson@stolaf.edu>
Date:           Thu, 06 Jan 94 16:54 -0600
Subject:        Computing in Beginning Undergraduate Algebra

We have been experimenting with using computer software in
almost all of our undergraduate mathematics courses.  In particular,
I have focused on using GAP in our beginning course in abstract
algebra.  As a preface to explaining what we have settled on,
let me begin by describing our beginning our algebra course.

All mathematics majors are required to take one term of abstract
algebra.  One reason for this is that it is one of only two
courses in which primary emphasis is placed on developing
"mathematical maturity."  That is to say, we have
regarded our beginning undergraduate algebra course as
a theoretical course where students are expected to learn
to write proofs precisely and accurately, to think and reason
logically, and to gain an appreciation for generalization and
abstraction.

The course introduces groups, rings, and fields, with lots of
examples, and covers the standard theorems (e.g., Lagrange's Theorem,
Fundamental Homomorphism Theorem for groups and rings, Fundamental
Theorem of Field Theory).  The content is a slightly abridged
version of the first 25 chapters of Joseph A. Gallian's
``Contemporary Abstract Algebra'', Third Edition, 1994,
D. C. Heath and Company, Lexingon, Massachusetts.

Such a full agenda leaves little time for extended computer
projects.  Nevertheless, with careful planning we
have supplemented this theoretical approach with
four computer projects, using GAP (for groups) and MAPLE (for
rings and fields).  About one class period is devoted to each
project.  These examples show the value of the
computer in pedagogy, understanding, research, and application.

In the first project the computer is used to solve various sliding
block puzzles.  Specifically, students specify sets of generators
and the computer calculates their subgroups.  Students might wonder
how the computer is able to do this, and it could lead,
although not in this course, to further study of generators and
relations, and the Todd-Coxeter algorithm.

The second project helps students understand the Fundamental Theorem
of Finite Abelian Groups.  Specifically, for arbitrary $n$, students
use the computer to help them identify the group of units
modulo $n$ as a direct sum of cyclic groups of prime power order,
and to construct its cycle graph.

In the third project, students ask questions such as ``What
proportion of the elements of a group have property $P$?''
The computer grinds out data and calculates the proportion for
any desired group.  This, in turn, leads to conjectures and
possible proofs.

The fourth project uses the computer to calculate
``encoding'' polynomials for multiple error correcting BCH codes.
The computer is also used to detect and correct
errors in received messages.  Among other things, this project
reinforces the importance of finite field algebra.

These projects show students the scope and power of computer
software, and hopefully motivates them to want to continue
their studies in mathematics and algebra in particular.

I am currently preparing versions of these projects for
distribution by e-mail (in plain TEX).  If interested in
getting a copy by e-mail, my address is

            larson@stolaf.edu



From jcbhrb@cerf.net Thu Jan  6 15:27:00 1994
From:           "Jacob Hirbawi" <jcbhrb@cerf.net>
Date:           Thu, 06 Jan 94 15:27 -0800
Subject:        expressions involving roots of unity

Suppose I have an expression involving roots of unity, such as :

   x := [ 0, 1, -3/5*E(20)+3/5*E(20)^9+1/5*E(20)^13-1/5*E(20)^17, 0 ];

is it possible to substitute every instance of E(n) in x with some other 
function f(n) and have the new expression automatically evaluated? Thanks.

Jacob Hirbawi
Jcbhrb@CERF.net



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan  7 09:29:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 07 Jan 94 09:29 +0100
Subject:        RE: AddSet etc.

Dear Dima Pasechnik,

you wrote in your letter

    Some time ago we noticed  that the function Orbit(G,S,OnSets)  can
    be hopelessly  slow when |S| and  in particular the  length of the
    resulting orbit are big enough.

yes,  that is true,  however

    we found that the largest amount of CPU time is consumed by
    AddSet.  One may see looking at the appropriate C code that the
    time taken by AddSet to add a new element to the set of length N
    is proportional to N.

if   you will take a   closer look (actually  you  will find a comment
"perform the binary search"), you will see that 'AddSet' uses a binary
search, *but* it has to ensure that the list  is indeed a set.  To the
inexperienced user a simple solution to the problem is

    It is not quite clear why faster ways to handle sets, such that the
    addition of a new element takes only O(log(N)) operations, are not used
    in the GAP implementation.

but  this naive approach  has  a drawback, namely   that sets  in this
proposal could only contain unchangeable data structures like integers
or permutations  but not changeable    like lists or  records  without
introducing some amount of overhead for *all* list/record assignments.
To illustrate the point, consider the following examples:

  gap> l := [ 1, 2, 5, 6 ];;
  gap> TYPE(l);
  "list"
  gap> AddSet( l, 3 );
  gap> l;
  [ 1, 2, 3, 5, 6 ]
  gap> TYPE(l);
  "set"
  gap> AddSet( l, 0 );
  gap> l;
  [ 0, 1, 2, 3, 5, 6 ]

the  first call to 'AddSet'  checks that <l> is indeed  a set and then
uses a binary search to add  the '0'.  The  function 'IsSet' (which is
used in 'AddSet') attaches  a "flag" to <l>, which  shows that  <l> is
indeed a set.  The second call to 'AddSet'  will not check again.  So,
when  dealing  with   lists containing   integers,  permutations,  etc
'AddSet' will always   (with the exception   of the first call) use  a
binary search.  So what *is* the problem:

  gap> l := [ [1,2], [2,3] ];
  [ [ 1, 2 ], [ 2, 3 ] ]
  gap> TYPE(l);
  "list"
  gap> a := [1,3];
  gap> AddSet( l, a );
  gap> l;
  [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
  gap> TYPE(l);
  "list"
  gap> IsSet(l);
  true

Why hasn't GAP attached is magic flag to <l>?  Well, if GAP would have
marked the  list <l> as set,  then  each assignment  into a  list must
check if this particular list is *contained* in a  set, in our example
<l>:

  gap> a[1] := 2;
  gap> IsSet(l);
  false

The  assignment to <a> has changed  the set-feature of <l>!  There are
several solutions   to  the problem,  each  has its  advantages *and*
disadvantages:

(a) Create unchangeable counterparts to lists and records,  once created
    they cannot be changed anymore or

(b) Create sets which only allow to test membership. 

(a) and (b) both have the drawback (which showed  heavily in GAP 2.4),
that you have to convert  between different representations,  creating
an immense amount of garbage.

(c) While making an assignment check if this particular list is an element
    of a set.  This would introduce overhead for *all* list operations.

(d) the Magma solution, which seems to be a mix of (a) and (b).

(e) Use knowledge about the algorithm *inside* your algorithm, not inside
    the kernel of GAP.

In my opinion  one should use  (e).  For instance,  an orbit algorithm
can (hopefully) *guarantee* that it will not destroy the property that
the  list of points  computed so far is already  sorted.  So it should
look like:

  OrbitTest := function ( G, d, opr )
      local   orb,        # orbit, result
              set,        # orbit <orb> as set for faster membership test
              gen,        # generator of the group <G>
              pnt,        # point in the orbit <orb>
              img;        # image of the point <pnt> under the generator <gen>

      orb := [ d ];
      set := [ d ];
      for pnt  in orb  do
          for gen  in G.generators  do
              img := opr( pnt, gen );
              if not img in set  then
                  Add( orb, img );
                  AddSetNC( set, img ); # <-- instead of 'AddSet'
              fi;
          od;
      od;

      # return the orbit <orb>
      return orb;
  end;

where 'AddSetNC' would be  a function, that  does no checks at all and
assumes that the list is already sorted.   One could easily write such
a function and careful analysis will show that there is still room for
improvments, one should  use 'PositionSorted' in  order to get ride of
the 'in'  avoiding  doing a  binary (or  worse a linear)  search twice
(once in 'in' and once  in 'AddSetNC'), but  our experiments never ran
into problems with the current orbit algorithm and because of the lack
of time   and  manpower we  didn't  check  what the  fastest  possible
algorithm would be for   all possible problems/experiments.   You  are
more than welcome to send a list of  functions in which you think such
improvements are worthwhile.

best wishes
  Frank



From Alexander.Hulpke@Math.RWTH-Aachen.DE Fri Jan  7 10:36:00 1994
From:           "Alexander Hulpke" <Alexander.Hulpke@Math.RWTH-Aachen.DE>
Date:           Fri, 07 Jan 94 10:36 +0100
Subject:        Re: expressions involving roots of unity

Dear Forum.

In his message, Jakob Hirbawi asked:

> Suppose I have an expression involving roots of unity, such as :
> 
>    x := [ 0, 1, -3/5*E(20)+3/5*E(20)^9+1/5*E(20)^13-1/5*E(20)^17, 0 ];
> 
> is it possible to substitute every instance of E(n) in x with some other 
> function f(n) and have the new expression automatically evaluated? Thanks.

The following function should do the work:

# replace all instances of E(n) in <list> by <func>(n). 
TransformedCyclotomics:=function(list,func)
local n,i,l;
  l:=[];
  for i in list do
    if IsRat(i) then
      Add(l,i);
    else
      n:=NofCyc(i); # the cyclotomic field used
      Add(l,ValuePol(CoeffsCyc(i,n),func(n))); # replace E(n) by func(n)
    fi;
  od;
  return l;
end;

This function really ''replaces'' each 'E' by <func>. I don't know, which
use you have in mind, but probably (if your f is somehow ''compatible'' with
the Galois group) you might want to do all calculations in the same
cycloctomic field, containing all cyclotomics in the list.
If you want this function to simulate Galois mappings, you should also look
up GaloisCyc in the manual, which is designed to apply Galois maps.

Hope that helps,

Alexander

-- Alexander Hulpke, Lehrstuhl D f"ur |Ce po`eme est, en effet, divis'e en
   Mathematik, RWTH Aachen            |cinq strophes successivement et respec-
                                      |tivement compos'ees de 3-1-4-1-5 vers,
  ahulpke@math.rwth-aachen.de         |   Jacques Bens:  Le sonnet irrationnel



From sl25@cus.cam.ac.uk Fri Jan  7 09:58:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 07 Jan 94 09:58 +0000
Subject:        Re: AddSet etc. 

> 
> if   you will take a   closer look (actually  you  will find a comment
> "perform the binary search"), you will see that 'AddSet' uses a binary
> search, *but* it has to ensure that the list  is indeed a set.  To the
> inexperienced user a simple solution to the problem is
> 
>     It is not quite clear why faster ways to handle sets, such that the
>     addition of a new element takes only O(log(N)) operations, are not used
>     in the GAP implementation.
> 
> but  this naive approach  has  a drawback, namely   that sets  in this
> proposal could only contain unchangeable data structures like integers
> or permutations  but not changeable    like lists or  records  without
> introducing some amount of overhead for *all* list/record assignments.
> To illustrate the point, consider the following examples:

There is another problem, which I outlined to Martin a while ago.
Once it has decided where in the set the new entry is to be added,
AddSet then has to do O(N) work to make room for it by moving half
the set. The constant is pretty low, but it's still O(N).


My solution to this is to use blists rather than sets whenever
possible, and I have functions FastOrbit and FastOrbits which do
this, and differ from Orbit only in that they require the domain to
be given in full. Ideally functions like the Random Schreier-Sims
should use these techniques also.  

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan  7 13:04:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 07 Jan 94 13:04 +0100
Subject:        Re: AddSet etc.

Dear Steve,

    There is another problem, which I outlined to Martin a while ago.
    Once it has decided where in the set the new entry is to be added,
    AddSet then has to do O(N) work to make room for it by moving half
    the set. The constant is pretty low, but it's still O(N).

yes, that is true.  And  again for the same  reasons there is no easy way
to get rid of  the problem, once you decided  that sets should (regarding
access and assignment) behave like lists.

    My solution to this is to use blists rather than sets whenever
    possible, and I have functions FastOrbit and FastOrbits which do
    this, and differ from Orbit only in that they require the domain to
    be given in full. Ideally functions like the Random Schreier-Sims
    should use these techniques also.

yes,  that is a very good idea if your domain is small enough.
One could also try to write GAP functions for BTrees or other more
advances techniques.  I would love to hear if anybody has already
done experiments into this direction.

This raises another point,  maybe we should set up a directory
where we can collect small functions which are not large
enough to qualify as a share library but useful enough to be
of interest for other people?  For instances, I think, 
your 'FastOrbit(s)' would be such a function.

best wishes
  Frank



From dima@maths.uwa.edu.au Fri Jan  7 20:44:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 07 Jan 94 20:44 +1000
Subject:        RE: AddSet etc.

Dear Frank Cellar,

>     Some time ago we noticed  that the function Orbit(G,S,OnSets)  can
>     be hopelessly  slow when |S| and  in particular the  length of the
>     resulting orbit are big enough.
> 
> yes,  that is true,  however
> 
>     we found that the largest amount of CPU time is consumed by
>     AddSet.  One may see looking at the appropriate C code that the
>     time taken by AddSet to add a new element to the set of length N
>     is proportional to N.
> 
> if   you will take a   closer look (actually  you  will find a comment
> "perform the binary search"), you will see that 'AddSet' uses a binary
> search, *but* it has to ensure that the list  is indeed a set.  To the

Sorry, the whole point is about the *addition* of elements rather than
*search*. Indeed AddSet is pretty fast if it does not need to add the
particular element. Again, the trouble in this case is with the handling of
the set as a whole rather than with the handling of its elements.
Here follows an extract from the file set.c, function
AddSet. (My own comments are marked by ***).
    
    /* perform the binary search to find the position                      */
    len   = LEN_PLIST( hdSet ); 
				*** it is the length of the set.

    i = 0;  k = len+1;
    while ( i+1 < k ) {                 /* set[i] < elm && elm <= set[k]   */
        j = (i + k) / 2;                /* i < j < k                       */
        if ( LT( ELM_PLIST(hdSet,j), hdObj ) == HdTrue )  i = j;
        else                                              k = j;
    }

    /* add the element to the set if it is not already there               */
    if ( len < k || EQ( ELM_PLIST(hdSet,k), hdObj ) != HdTrue ) {
        if ( SIZE(hdSet) < SIZE_PLEN_PLIST( len+1 ) )
            Resize( hdSet, SIZE_PLEN_PLIST( len + len/8 + 4 ) );
        SET_LEN_PLIST( hdSet, len+1 );
        for ( i = len+1; k < i; i-- ) *** the troube is here
				*** this loop can be executed O(len) times

            SET_ELM_PLIST( hdSet, i, ELM_PLIST(hdSet,i-1) );
				*** moving len-th elt to the position len+1,
				*** (len-1)th elt to the position len, etc
				*** to make room for the new elt.

        SET_ELM_PLIST( hdSet, k, hdObj ); *** add new elt.
    }

> inexperienced user a simple solution to the problem is
> 
>     It is not quite clear why faster ways to handle sets, such that the
>     addition of a new element takes only O(log(N)) operations, are not used
>     in the GAP implementation.
> 
> but  this naive approach  has  a drawback, namely   that sets  in this
> proposal could only contain unchangeable data structures like integers
> or permutations  but not changeable    like lists or  records  without
> introducing some amount of overhead for *all* list/record assignments.
> To illustrate the point, consider the following examples:
[...]

The example is rather strange, since it's more or less clear that any set
can be treated as a list with an ordering attached. The example in question
seems to violate this, i.e. make some elements of the set incomparable.
I doubt that in any serious computation one would make things like that:

a:=5;
l:=Set([a,2,3]);
a:=(1,2);

> The  assignment to <a> has changed  the set-feature of <l>!  There are
> several solutions   to  the problem,  each  has its  advantages *and*
> disadvantages:
> 
> (a) Create unchangeable counterparts to lists and records,  once created
>     they cannot be changed anymore or
> 
> (b) Create sets which only allow to test membership. 
> 
> (a) and (b) both have the drawback (which showed  heavily in GAP 2.4),
> that you have to convert  between different representations,  creating
> an immense amount of garbage.
> 
> (c) While making an assignment check if this particular list is an element
>     of a set.  This would introduce overhead for *all* list operations.

But the example I deleted shows that this this the option already 
chosen in GAP, isn't it?

> 
> (d) the Magma solution, which seems to be a mix of (a) and (b).
> 
> (e) Use knowledge about the algorithm *inside* your algorithm, not inside
>     the kernel of GAP.

It's not quite clear why the following option is not OK. Certainly (c) is
bad. But what about making the user responsible for the upgrading of sets,
if necessary. Say, after 
a:=1;
l:=Set([a,2,3]);
a:=10;

call a function (say)   Upgrade(l). One could suggest even better ways, by
taking some extra care *before* changing a.



> In my opinion  one should use  (e).  For instance,  an orbit algorithm
> can (hopefully) *guarantee* that it will not destroy the property that
> the  list of points  computed so far is already  sorted.  So it should
> look like:
>           od;
>       od;
> 
>       # return the orbit <orb>
>       return orb;
>   end;
> 
> where 'AddSetNC' would be  a function, that  does no checks at all and
> assumes that the list is already sorted.   One could easily write such
> a function and careful analysis will show that there is still room for

To be efficient, this function must involve the machinery for efficient
addition of elements in the set, e.g. AVL-trees etc.
It's not so *easy*.

Best regards,
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Jan 10 10:10:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Mon, 10 Jan 94 10:10 +0100
Subject:        AddSet again

Forwarded message:
>From math.rwth-aachen.de!fceller Mon Jan 10 09:04:51 1994
Message-Id: <m0pJHYi-0000UKC@rowlf.Math.RWTH-Aachen.DE>
Date: Mon, 10 Jan 94 09:00 +0100
From: Frank.Celler@math.rwth-aachen.de
To: J.Neubueser@math.rwth-aachen.de
In-reply-to: Dima Pasechnik's message of 7 Jan 94 20:44 WST <m0pIHQC-000LsCC@samson.Math.RWTH-Aachen.DE>
Subject: Meine Antwort
Content-Type: text

Dear Dima Pasechnik,

    To be efficient, this function must involve the machinery for efficient
    addition of elements in the set, e.g. AVL-trees etc.

yes, I completely  agree with you  on that point, unfortunately,  as I
tried to explain, this is of little help with your orignal question:

    Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
    hopelessly slow when |S| and in particular  the length of the resulting
    orbit are big enough.

if <S>  is  a big  set the  comparison between  sets will be  relative
expensive, together with   the fact that  'AddSet'  has  to check  all
elements this is taking the time.  A short example: Take a set of 4000
vectors of length 450 and sort them in reversed order.  Now start with
the first vector and build up a  new set using 'AddSet'. The insertion
process  during the addition of elements  is as bad  as  can be.  On a
NeXT this process will indeed be incredibly slow taking nearly an hour
to complete.  However,  if your remove the test  in 'AddSet'  that the
first argument is  really a set, it will  take 20sec, 10  of those - I
would guess  - being  used  in  the  insertion process.   Using Trees,
hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
So you have  a gain of 10sec  in an 1  hour procedure. If on the other
hand you simply drop the test, you will speed up  the whole thing by a
factor of 200.

Once  you  have decided that  sets are  sorted lists without  holes (I
explained why we didn't choose  the other  options, in this  situation
things would have been different), your suggestion

    call a function (say)  Upgrade(l). One could  suggest even better
    ways, by taking some extra care *before* changing ....

will create dangerous traps.  If one is purely thinking in the context
of orbits, I agree that

    The example is rather strange,  since it's more or  less clear that any
    set can be treated as a list with  an ordering attached. The example in
    question  seems to  violate  this, i.e. make   some elements of the set
    incomparable.  I doubt that  in any serious  computation one would make
    things like that:

But unfortunately that point of  view can only  be taken in standalone
programs but not in a system like GAP.  The example I  gave you is not
a wild construct, it is a simplification of a real bug.  When changing
from   GAP 2.4 to  3.0 we  experimented for a   while  with that.  And
because of the  tempting example above we tried  if we can  do without
the test    in 'AddSet'.  But   this   created a bug    in one  of the
representation theory programs, where  sets were used in  a completely
different  seting   (and sets there   are very  small).  It   took the
programmer  a long time  to find this  really nasty bug.  That was the
reason why  we decided against a faster  but insecure 'AddSet' and are
now using a slow but stable one.

On the other hand, and that was the point (e) I tried to explain, this
does  not  mean that one has  to  live with an   (in  some cases slow)
implementation of 'Orbit' (even now, where in most cases the operation
is costly, it is not too bad).  But  the example above shows that with
very  little  work involved one  can  easily speed  up things, in that
example  it  does  not even  seem  necessary to  use    trees or other
techniques.   But in a situtation as  Steve has described, which is in
some sense the other extreme because comparison  and operation is very
cheap,  4-3-trees, red/black-trees,  avl-trees, hashing, or  bit-lists
could and should be used.  But doing this in 'AddSet' will not help in
your sitution.  So one has to do it in 'Orbit' (in  which it will work
for both your and Steve's situation). This does  not mean that one has
to do  it in such  a way that  it  can only  be used  in 'Orbit'.  For
instance, if one would write a small package implementing functions to
create a tree structure, to add a new element, to test membership, and
to test and  add,  this  could easily  be   used in   various  places.
Presumably all  of this can be  done  with the existing datastructures
lists  and records.  But as I  said, at the  moment none of us here in
Aachen  has the time to  do  it, so experiments/comments (like Steve's
'FastOrbit')  from elsewhere are more than  welcome. Wouldn't you like
to write such a package that would  perform optimally for applications
like yours? We would surely appreaciate that.

best wishes
  Frank Celler and Joachim Neubueser
            ^
            ^



From Joachim.Neubueser@Math.RWTH-Aachen.DE Wed Jan 12 20:13:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Wed, 12 Jan 94 20:13 +0100
Subject:        re GAP for undergraduates

In   his letter to the    forum of Dec.   31,  Bill Haloupek asked for
suggestions with respect to the use of GAP in teaching undergraduates
and raised some  questions that I think are important.

I am grateful for the report about the use of GAP at St. Olaf that was
sent    to the  GAP-forum   a  few  days    later providing  some such
suggestions.  I have already talked about our (rather less systematic)
use of  GAP in  teaching; today,  rather belatedly,  I would   like to
comment in a more general way on a couple of  points in Bill Haloupeks
letter:

   >I think the GAP manual is pretty intimidating to undergraduates.

Yes, I  completely agree  that it  must  be intimidating  to the  vast
majority of the students. We intend (but do not ask when) to split the
manual into three  parts, the first an  extended version of the  first
chapter 'About GAP', the second the reference part to the functions in
the main body of GAP  and the third  about the share libraries.   This
will hopefully make use easier but still  would only marginally reduce
the intimidation of  undergraduates.    For   these indeed  an    easy
introduction to  the easy parts of  GAP should be written, leaving out
character tables  and similar 'horrors'.  However I  had to  say above
that I can't promise a  date when we will  have been able to split the
manual, I can say rather safely that we simply  will not have the time
in   any   foreseeable future   for    writing such  an  undergraduate
introduction, which after all should be based on some experiments with
students, and     should introduce    concepts  together  with   their
exploration  using  GAP.  Being a   small department with  rather high
teaching   duties,  we will be   glad   if  we  reasonably manage  the
maintenance and  improvement of GAP.  I would therefore highly welcome
if somebody undertook  that task, which  indeed I think would  be most
worthwhile.

   >There is a much more user-friendly and simple program...It does 
   > calculations in S4 mainly. 

I do not  know this program  and certainly  would  not at all want  to
question its helpfulness.  However  I would like  to make  some points
both from  my own experience as a  student and from my experience with
my students.

I do not believe that one  should introduce programs that replace hand
calculations  too   early.  I think  in   a group of  the  size  of S4
everything can  still rather well be done  by hand and  indeed writing
down by hand   all cosets of the Klein-Four-Group   on one hand and  a
Three-cycle on the other and trying to form a group from either set is
a useful experience. Even  though we have  GAP and tell students early
how to use it, we do require some such hand calculations.

When I   was a student and  my  teacher Wolfgang Gaschuetz  proved all
those  wonderful theorems about existence  of complements while I just
knew S3, S4, and D8, I sat down and worked  out all groups up to order
30 and their subgroup lattices just to see what  he was talking about.
I am not recommending that  every undergraduate should  do that, but a
little of that kind, yes, I certainly learned a lot about group theory
doing that.

However, when I had done  that, one equally  important benefit for  me
was that I  started to believe that  all these difficult  concepts and
wonderful theorems were about *something at  all* and that it might be
fun to  know more about these  so simply  defined  and yet  so complex
structures, called groups.   I think it is this  point even more  than
the help with the understanding of the  meaning of basic concepts were
GAP (and other systems) can help.

Another help  that   systems can give  is  to   show rather  different
situations in which a theorem   applies and also situations which  are
similar  but not quite and where  the theorem does  not hold any more,
i.e.systems can help to understand (the scope of) a theorem through an
understanding of its  limitations.  E.g. in a  finite  abelian group A
there is a subgroup of each order dividing the order of A. In A4 there
isn't! Oh! So  Sylow's theorem is  something after all! That  you will
probably still do by hand but for bigger ones use GAP.

Coming back to my collection of drawings of subgroup lattices, you may
have noticed that GAP 3.3 comes  with a (still very rudimentary) X-GAP
which works under X-windows and allows to obtain  such drawings on the
screen. This will  be extended also  to incorporate features that have
been  developed in  Derek   Holt's and  Sarah  Rees'  beautiful system
QUOTPIC for  the investigation of a  finitely presented  group drawing
parts   of its   normal  subgroup  lattice,   i.e.   depicting certain
factorgroups.  I think such visualisations will lend themselves rather
well to teaching even  undergraduates, giving them  a "picture" of the
group.

   >A manual should include a section telling us mathematicians how to
   >evaluate computer homework.

Well, maybe  it is, since I (still)  hope to be a  mathematician, too,
that I do not know what to write  into such a section!  But seriously:
What we do is the following: In an Algebra course (at present I give a
course Algebra  I, the   usual 'Groups,  Rings, Fields' up   to Galois
Theory  for first term,  second year students),  most of the exercises
are to be done by hand.  Some with computations are "either by hand or
by GAP" and what counts is if the result has been achieved.  If GAP is
used,  a print of  what has been done  should  be provided in much the
same way as the hand computations should  be shown.  In addition there
are a few problems which really can only be  done with GAP and in most
cases these are "extra credit" as in your class.  That is, the ability
to use  GAP very efficiently  is *not*  the criterion for  passing the
course. Rather the students should  gradually learn to appreciate that
indeed  GAP  may  help them  dealing   with more  complicated concrete
problems. (In fact in the written test at the end  of the course which
mainly decides about passing it there is no GAP at all!)

In  a general  group  theory  course   there  will be a   little  more
"pressure" in the direction of using GAP.   The kind of philosophy is:
Well, a prerequisite of  saying that  you mastered  the course  is not
only that you  learned  some facts and  understood  some  concepts but
definitely  also that you  learned some  techniques  to  prove certain
statements, another  (complementing, not at all  replacing it) is that
you learnt some techniques to  work in concrete groups  - by hand  and
argument as well as using algorithmic methods in a system.

Finally,  in  a course  on Computational   Group Theory naturally  the
second  aspect dominates.

However in neither  of the different courses  have I ever  felt a need
for  a  special  evaluation method.   None   of the   courses is about
techniques for writing programs,  none of them  is a  computer science
course.   Neither  is any  of them   a course  for  living in  a group
theoretical  fool's  paradise   in   which   black   boxes spit    out
charatertables.  Also in the CGT course the understanding of the group
theory that lends itself to developing an algorithm  is the aim, hence
it is all the time the ability to do something using the understanding
of it that should be tested.

As I have said in  another letter, we intend  (again do not ask dates)
to  provide at least  a set of worked out  examples of the  use of GAP
that may be used in  class, some  coming  from our courses in  Aachen,
some from  the   CGT workshop  at  Galway,  but  also,  with  his kind
permission,  including  those that Peter   Webb offered.  Maybe others
could do the same?

Joachim Neubueser



From dima@maths.uwa.edu.au Thu Jan 13 22:34:00 1994
From:		"Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Thu, 13 Jan 94 22:34 +1000
Subject:        Re: AddSet again

Dear Forum,
>     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
>     hopelessly slow when |S| and in particular  the length of the resulting
>     orbit are big enough.
> 
> if <S>  is  a big  set the  comparison between  sets will be  relative
> expensive, together with   the fact that  'AddSet'  has  to check  all
> elements this is taking the time.  A short example: Take a set of 4000
> vectors of length 450 and sort them in reversed order.  Now start with
> the first vector and build up a  new set using 'AddSet'. The insertion
> process  during the addition of elements  is as bad  as  can be.  On a
> NeXT this process will indeed be incredibly slow taking nearly an hour
> to complete.  However,  if your remove the test  in 'AddSet'  that the
> first argument is  really a set, it will  take 20sec, 10  of those - I
> would guess  - being  used  in  the  insertion process.   Using Trees,
> hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given by  a set of  generators (i.e.  to compute  the subgroup
lattice, but that concept  need not be  mentioned at that level). That
is very concrete and  does so far  only need the notion  of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains  a*b^-1 and let them write a
program just  using  that.  This will be   hopelessly inefficient ( of
course - but it  is  what once  upon  a time   a very renowned   group
theorist suggested  to me as  much simpler than  what I  had done!)

Next  prove  to them  Lagrange's  theorem.  So we need  not  check all
subsets!  Progress! Unfortunately still very inefficient.

Remind  of the  concept of generating   sets  and apply it to  finding
subgroups.  We will  need a fast  way to  generate a subgroup.  Invent
Dimino's algorithm (this  brings  you close to  the idea  of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List  of all elements?  Long!  Moreover
membership test if used more often  is a problem.   Invent the idea of
storing by a characteristic function,  that is by  a bitstring! On the
set of all elements of the whole group?   Possible! Better: On the set
of cyclic subgroups of prime power order.  By now you will have needed
some idea  of  how a cyclic subgroup  works.  However by now  you have
already arrived  at the data  structure  that is actually used  in GAP
(and Cayley).

Then  return  to the idea  of   using  generating sets.   Maybe  using
lexicographical order? Not so bad,  has been  a serious and  published
proposal in  the early sixties,  write some programs.  Trouble is that
so many subgroups are  found over and over again,  and this is noticed
only  after a  good chunk  of them  has been   regenerated. Really one
should know beforehand which to generate.

Now  you need a bit  more theory: normal subgroups, normalizer, factor
groups,  (composition  series),  soluble  groups,   not really  Jordan
Hoelder, although having it does not hurt, but you may also first have
the program  and then use it  to 'observe'  the truth  of  JH.  Having
these  concepts, now invent the 'cyclic  extension method' for soluble
groups and actually  implement it, using either  a brute  force method
for the  normalizer or (maybe after that)  a much more efficient black
box for it that you find in GAP.

Maybe you  now want to ask if  all finite  groups are soluble, perhaps
you can  prove the simplicity  of A5 or  even An,  n>4.  This will now
have a very concrete meaning to the students.

All this can be done using the commodities  of a system like GAP, i.e.
not worrying about storage  management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach  is pretty close to  the  actual implementation  of the
subgroup lattice in GAP, which still follows in many  ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The   philosophy of  the whole    proposal  is to   let the   students
*experience* that  group theoretical concepts are   not there to annoy
them but to  make  concrete  complex  structures accessible.    "Think
before programming!"  Perhaps even computer science majors may get the
message. And  at the end they  can throw a  pair of generators for M11
into GAP and  have some idea  how it  works that the  subgroup lattice
comes out.

The  first chapters of Greg Butler's   book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students  give talks on  its content. That was a
flop.  Reporting about all the (sometimes over-) explicit countings of
operations  in algorithms got  very boring. I do  not recommend to try
that.  Rather use the book yourself but hide  it from the students (at
least until the end  of the course) and let  them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some   theorems) and let  them *do*  the  algorithms rather than
speak about them.

I  would be most  interested to hear  if somebody tries something like
that.

Apologises  to those  of  you who  would    like to see  other  things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser



From sl25@cus.cam.ac.uk Thu Jan 13 15:55:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Thu, 13 Jan 94 15:55 +0100
Subject:        Re: AddSet again

in
> 
> Dear Forum,
> >     Some  time ago we  noticed that the  function  Orbit(G,S,OnSets) can be
> >     hopelessly slow when |S| and in particular  the length of the resulting
> >     orbit are big enough.
> > 
> > if <S>  is  a big  set the  comparison between  sets will be  relative
> > expensive, together with   the fact that  'AddSet'  has  to check  all
> > elements this is taking the time.  A short example: Take a set of 4000
> > vectors of length 450 and sort them in reversed order.  Now start with
> > the first vector and build up a  new set using 'AddSet'. The insertion
> > process  during the addition of elements  is as bad  as  can be.  On a
> > NeXT this process will indeed be incredibly slow taking nearly an hour
> > to complete.  However,  if your remove the test  in 'AddSet'  that the
> > first argument is  really a set, it will  take 20sec, 10  of those - I
> > would guess  - being  used  in  the  insertion process.   Using Trees,
> > hashing or whatever  will reduce this 10sec to  maybe less than  1sec.
> > So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> > hand you simply drop the test, you will speed up  the whole thing by a
> > factor of 200.
> 
> Yes, I see now that the main problem is that AddSet calls IsSet rather
> than it spends lots of time for actual rewriting of the set.
> However, looking at IsSet, one sees that first of all it tests
> whether it is already known that the argument is a set  by checking
> certain flag in its record. In the best of my knowledge,
> it is really fast providing this flag is set to `yes`.
> 
> Note that the sets in question are generated as the images of the
> original set S. The image of S is a set, so the corresponding
> function which computes the image of a set under a permutation (see the
> module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> (In other words there might be a bug)
> 
> Otherwise I fail to understand why 
> the removal of the call to IsSet can improve performance of
> Orbit(,,OnSets) so dramatically.

Is this a set of numbers, or a set of (for example) vectors?

It makes a difference, for the reason that Frank was talking about
before, namely that a vector in the set might be altered (by
assigning to one of its entries). A set of vectors can thus NOT be
guaranteed to stay sorted, even if no changes are made to the set
itself, only changes to the elements.

	Steve



From dima@maths.uwa.edu.au Fri Jan 14 08:46:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Fri, 14 Jan 94 08:46 +1000
Subject:        Re: AddSet again

> > 
> > Yes, I see now that the main problem is that AddSet calls IsSet rather
> > than it spends lots of time for actual rewriting of the set.
> > However, looking at IsSet, one sees that first of all it tests
> > whether it is already known that the argument is a set  by checking
> > certain flag in its record. In the best of my knowledge,
> > it is really fast providing this flag is set to `yes`.
> > 
> > Note that the sets in question are generated as the images of the
> > original set S. The image of S is a set, so the corresponding
> > function which computes the image of a set under a permutation (see the
> > module permutat.c) should set , I believe, the abovementioned flag to `yes`.
> > (In other words there might be a bug)
> > 
> > Otherwise I fail to understand why 
> > the removal of the call to IsSet can improve performance of
> > Orbit(,,OnSets) so dramatically.
> 
> Is this a set of numbers, or a set of (for example) vectors?
> 
> It makes a difference, for the reason that Frank was talking about
> before, namely that a vector in the set might be altered (by
> assigning to one of its entries). A set of vectors can thus NOT be
> guaranteed to stay sorted, even if no changes are made to the set
> itself, only changes to the elements.
> 
> 	Steve



It seems still unclear. If g is a permutation of a set X of whatever nature,
S a subset of X, then S^g is a set, otherwise one would expect a message
like "Error, <set> must be a set in ...OnSets".
That is, S^g is uniquely defined. That is , S^g should be a set,  so
the appropriate flag of it is 'yes'.

Certainly I agree that there are operations which can disrupt the order of
S,  say as it was pointed out by making changes to elements,
but S^g should be exempt from this list.

	Dima


-- 
Dima Pasechnik, 
Dept. of Mathematics, 
Univ. of Western Australia, Nedlands WA 6009, Australia
e-mail:dima@maths.uwa.edu.au



From sl25@cus.cam.ac.uk Fri Jan 14 10:42:00 1994
From:           "Steve Linton" <sl25@cus.cam.ac.uk>
Date:           Fri, 14 Jan 94 10:42 +0100
Subject:        Re: AddSet again

> 
> It seems still unclear. If g is a permutation of a set X of whatever nature,
> S a subset of X, then S^g is a set, otherwise one would expect a message
> like "Error, <set> must be a set in ...OnSets".
> That is, S^g is uniquely defined. That is , S^g should be a set,  so
> the appropriate flag of it is 'yes'.
> 
> Certainly I agree that there are operations which can disrupt the order of
> S,  say as it was pointed out by making changes to elements,
> but S^g should be exempt from this list.
> 

The problem is that the 'set' object cannot know whether one of its
memebrs has been altered. Accordingly, the flag can NEVER be used on
a list containing changeable objects.

	Steve



From Frank.Celler@Math.RWTH-Aachen.DE Fri Jan 14 14:44:00 1994
From:           "Frank Celler" <Frank.Celler@Math.RWTH-Aachen.DE>
Date:           Fri, 14 Jan 94 14:44 +0100
Subject:        Re: AddSet again and again

Dear Dima Pasechnik,

    It  seems still unclear.   If g is  a permutation  of a  set X  of
    whatever nature, S a subset of X, then S^g is a set, otherwise one
    would  expect  a message like   "Error, <set>  must  be a  set  in
    ...OnSets".  That is,   S^g is uniquely  defined.  That is  ,  S^g
    should be a set, so the appropriate flag of it is 'yes'.

sorry, now  I  am I  bit confused.  You   were  asking about  sets  in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion.  I think we  now all more or less agree
how  to solve  these kinds of  problems.    But 'OnSets' does  not use
'AddSet', it will apply <g>  to all elements of  <S> and then sort the
resulting list.  Again for the  same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable  objects, 'OnSets' will not do
it either.  Surely,  we can do  without the 'IsSet'  test but again we
decided  to play it safe  in order to avoid traps  for others, even if
this means that GAP will be  slower than possible without these tests.
If however your set   X contains unchangeable objects like   integers,
yes, one could try a bit harder  to keep the information that 'OnSets'
returns a set.  It  is not clear  to what  amount  this will speed  up
things,  because the test requires  only |<S>|-1 comparisons while the
sort needs something  like O(|<S>|*log|<S>|) and one  has to check  if
the image of <s> in <S> under <g> is again  unchangeable.  In the very
special case of a list/set  of integers  <S>  and permutation <g>  one
could do without tests. I will try to do this  in the next version but
the  speedup - I  guess -   will  not be  dramatical, presumably  much
smaller than a factor of 2.

I hope we all now understand the problems with sets,  but if there are
any    further questions,  I  think    we   should  discuss  them   in
"gap-trouble".  So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de" 

(there is  no need to  subscribe to it). If  any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
  Frank Celler



From karkar@tnearn.bitnet Fri Jan 14 21:36:00 1994
From:           "M Taoufik Karkar" <karkar@tnearn.bitnet>
Date:           Fri, 14 Jan 94 21:36 N
Subject:        undergraduate lectures

Dear Gap-Forum@RWTH-Aachen.de

I had some experience of teaching group theory that I like to tell you
about it.

I used to give to my students to compute (even by hand when no computer was
possible) concrete examples (full computations): I think that this is the
right way to make them ASSIMILATE the theoretical concepts. But, of course,
the task is horrible when the groups have order about (more or less) than
30 elements, while many elementary concepts cannot be illustrated by
so small groups.

More over, I found that the students are really exited if they have to
"guess" what group they  have while this group is defined by an abstract
presentation. The only thing that they discourage them to continue
investigations is of course a long, perhaps endless, hand calculus.

That is why I made a few years ago (before finding  GAP or handling
any symbolic system) a "small" program  for investigation "small groups"
(I call it Hijara=little stones, to make people remember they learned
the first things in arithmetics with little stones). These groups may be
permutation groups, abstract groups, "modular groups" (=units of Z/nZ)
or matrix groups with coefficients in some Z/nZ (matrices are not yet
implemented).

Now with such system, one can do elementary investigations in reasonable
time, on groups with some hundred elements and main elementary concepts
may be illustrated. For bigger groups, the program take a very long time
(some hours for groups of order = some thousands ).
The membership test is very expensive...and my implementation is
not optimized at all.

The fact that some groups to investigate are abstract make them return to
the theory for solving problem of how to handle that group. For them,
it is an "open question". There is no standard way to solve problems of
this nature, and all theoretical tools are potentially useful for
solving that problem.
The solution may be given later by the professto  maybe less than  1sec.
> So you have  a gain of 10sec  in an 1  hour procedure. If on the other
> hand you simply drop the test, you will speed up  the whole thing by a
> factor of 200.

Yes, I see now that the main problem is that AddSet calls IsSet rather
than it spends lots of time for actual rewriting of the set.
However, looking at IsSet, one sees that first of all it tests
whether it is already known that the argument is a set  by checking
certain flag in its record. In the best of my knowledge,
it is really fast providing this flag is set to `yes`.

Note that the sets in question are generated as the images of the
original set S. The image of S is a set, so the corresponding
function which computes the image of a set under a permutation (see the
module permutat.c) should set , I believe, the abovementioned flag to `yes`.
(In other words there might be a bug)

Otherwise I fail to understand why 
the removal of the call to IsSet can improve performance of
Orbit(,,OnSets) so dramatically.

Best regards,
Dima Pasechnik



From Joachim.Neubueser@Math.RWTH-Aachen.DE Thu Jan 13 16:37:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Thu, 13 Jan 94 16:37 +0100
Subject:        More GAP for undergraduates

Rereading what  I have written yesterday in  answer to Bill Haloupek's
letter, I realize that I  have perhaps not  taken enough notice of his
last and most direct question:

   >There is a saying, "you can lead a student to a computer, but you 
    can't make him think." Can we? At the undergraduate level? And with 
    non-math majors?

Well, here is a  suggestion that one  might  try, though I  must admit
that I haven't.

Give them the  task to compute all subgroups   of a permutation  group
that is given