This file contains the mails sent to the GAP forum in April-June 1994.

Name                Email address                           Mails   Lines
Joachim Neubueser   Joachim.Neubueser@Math.RWTH-Aachen.DE       8     229
Martin Schoenert    Martin.Schoenert@Math.RWTH-Aachen.DE        7     239
Alexander Hulpke    Alexander.Hulpke@Math.RWTH-Aachen.DE        6     273
Leonard Soicher     leonard@qmw.ac.uk                           5      73
Harald Boegeholz    hwblist@machnix.mathematik.uni-stuttgart.de 4     137
Chris Wensley       mas023@bangor.ac.uk                         3     193
Allan Adler         ara@altdorf.ai.mit.edu                      3      55
Chris Charnes       charnes@osiris.cs.uow.edu.au                3      12
Volkmar Felsch      Volkmar.Felsch@Math.RWTH-Aachen.DE          2     412
Eamonn O'Brien      eamonn.obrien@maths.anu.edu.au              2     151
Sebastian Egner     egner@hermes.zkm.de                         2     110
Peter Mueller       mueller@mi.uni-erlangen.de                  2      87
Frank Celler        Frank.Celler@Math.RWTH-Aachen.DE            2      83
BARTHOLDI Laurent   lbartho@scsun.unige.ch                      2      44
Jacob Hirbawi       jcbhrb@cerf.net                             2      40
Steve Linton        sl25@cus.cam.ac.uk                          2      34
Nishit Kumar        kumar@cs.ucf.edu                            2      30
Jasper Cramwinckel  j.cramwinckel@twi.tudelft.nl                1     115
Akos Seress         akos@math.ohio-state.edu                    1      47
Tomaz Pisanski      tomo.pisanski@uni-lj.si                     1      41
Jens Baek Joergensen jbj@daimi.aau.dk                           1      39
Kenneth H. Simpson  ken@poincare.arc.nasa.gov                   1      37
Wettl Ferenc        wettl@erie.vma.bme.hu                       1      36
Derek Holt          dfh@maths.warwick.ac.uk                     1      35
Thomas Breuer       Thomas.Breuer@Math.RWTH-Aachen.DE           1      25
Martin Wursthorn    pluto@machnix.mathematik.uni-stuttgart.de   1      19
Evelyn Hart"        "agnesi::hart"@physics.hope.edu             1      18
Dima Pasechnik      dima@maths.uwa.edu.au                       1      17
Gap Students        studgap@twi.tudelft.nl                      1      13
Alice Niemeyer      alice@maths.uwa.edu.au                      1      13
Catherine Greenhill greenhil@maths.ox.ac.uk                     1      12
William Kocay       william_kocay@macmail.cs.umanitoba.ca       1      11
Gerald Cliff        gcliff@vega.math.ualberta.ca                1       9
Tim Hsu             timhsu@math.princeton.edu                   1       9
Wang                wang@maths.uwa.edu.au                       1       8
Peter Jipsen        pjipsen@iastate.edu                         1       6
Dana-Picard Noah    dana@bimacs.cs.biu.ac.il                    1       5

This  file is in Berkeley mail drop format, which means you can read this
file with 'mail -f <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 leonard@qmw.ac.uk Sun Apr  3 20:31:00 1994
From:           "Leonard Soicher" <leonard@qmw.ac.uk>
Date:           Sun, 03 Apr 94 20:31 +0200
Subject:        AutGroupGraph limits in GRAPE

Dear Forum,

Recently there was a question about the limits on graph size for
AutGroupGraph, but I appear to have lost the original email.

The nauty 1.7 package (used by GRAPE 2.1 to calculate the automorphism
group of a graph) requires the maximum number of vertices of a graph to
be set at compile time.  The default for  GRAPE 2.1 is 1024.  You can
change this by editing  gap-directory/pkg/grape/nauty17/Makefile and
changing  1024  to  2048  (say),  and then completely re-installing the
GRAPE package.

Regards,   Leonard Soicher.



From dana@bimacs.cs.biu.ac.il Wed Apr  6 14:59:00 1994
From:           "Dana-Picard Noah" <dana@bimacs.cs.biu.ac.il>
Date:           Wed, 06 Apr 94 14:59 +0200
Subject:        gap 3.4

In a recent letter to the forum was announced that "soon" will be
released GAP's next version. Is there already a time range?
Thanks,
Th. Dana-Picard



From jbj@daimi.aau.dk Fri Apr  8 12:43:00 1994
From:           "Jens Baek Joergensen" <jbj@daimi.aau.dk>
Date:           Fri, 08 Apr 94 12:43 +0000
Subject:        PermGroupOps.SubgroupProperty - Complexity?

Dear Gap forum.


I am interested in the computational complexity of the GAP-function

PermGroupOps.SubgroupProperty.

Consider the call:

PermGroupOps.SubgroupProperty(G, P);

where G is some permutation group and P:G->Bool is some property. If every
element in G satisfies P, it seems to me like this function call terminates
very quickly - even when G is large. Is this observation correct and can it
be justified be referring to some general property of the backtrack
algorithm? (I assume that PermGroupOps.SubgroupProperty is the
GAP-implementation of the backtrack algorithm described, e.g., in Butler's
book "Fundamental Algorithms for Permutation Groups").

If G is the symmetrical group for some natural number n, I think I can
prove that the backtrack algorithm terminates after having tested exactly
n-1 permutations. Does this result generalize to all kinds of permutation
groups? Perhaps the number of permutations to test is equal to the number
of elements in the considered base for G?

I am definitely not an expert in the field of computational group theory
(or group theory for that matter), so it might be a quite well-known result
I am looking for.

Any help and/or references will be greatly appreciated.


Thanks,
Jens Baek Joergensen
Computer Science Department, Aarhus University
Ny Munkegade, Bldg. 540
DK-8000 Aarhus C
Denmark



From Joachim.Neubueser@Math.RWTH-Aachen.DE Fri Apr  8 13:33:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Fri, 08 Apr 94 13:33 +0200
Subject:        Re: gap 3.4

>  Wed Apr  6 14:04:56 1994

> In a recent letter to the forum was announced that "soon" will be
> released GAP's next version. Is there already a time range?
> Thanks,
> Th. Dana-Picard

The next version, GAP  3.4 is presently being  put together.  It  will
contain several new components. In  particular for this reason testing
it,  extending the manual,  etc will take  some time, hence  we do not
want to  make definite promises,  but we hope that  we can release GAP
3.4 in the second half of May.

Joachim Neubueser



From akos@math.ohio-state.edu Fri Apr  8 11:40:00 1994
From:           "Akos Seress" <akos@math.ohio-state.edu>
Date:           Fri, 08 Apr 94 11:40 -0400
Subject:        Re: PermGroupOps.SubgroupProperty - Complexity?


Dear GAP forum,

Jens Baek Joergensen <jbj@daimi.aau.dk> asks:
> Consider the call:
> 
> PermGroupOps.SubgroupProperty(G, P);
> 
> where G is some permutation group and P:G->Bool is some property. If every
> element in G satisfies P, it seems to me like this function call terminates
> very quickly - even when G is large. Is this observation correct and can it
> be justified be referring to some general property of the backtrack
> algorithm? (I assume that PermGroupOps.SubgroupProperty is the
> GAP-implementation of the backtrack algorithm described, e.g., in Butler's
> book "Fundamental Algorithms for Permutation Groups").
> 
> If G is the symmetrical group for some natural number n, I think I can
> prove that the backtrack algorithm terminates after having tested exactly
> n-1 permutations. Does this result generalize to all kinds of permutation
> groups? Perhaps the number of permutations to test is equal to the number
> of elements in the considered base for G?

The backtrack algorithm maintains a subgroup K, which contains the
elements of G which are already known to satisfy property P. 
If all elements of G satisfy P then K increases each time when a 
permutation is tested; consequently, the maximal length of subgroup chains 
in G is an upper bound for the number of elements tested. 

Slightly more precisely, consider the point stabilizer chain

G=G_1 > G_2 > ... > G_m > G_{m+1}=1.

The backtrack algorithm works in a ``bottom-up'' manner, first 
determining the subgroup of G_{i+1} satisfying P, before considering
the elements of G_i \setminus G_{i+1}. If G_{i+1} is always a 
maximal subgroup of G_i (1 \le i \le m) then the first element of
G_i \setminus G_{i+1} which we test increases K to G_i. 
So, the total number of elements tested is indeed the number of 
base points. This happens e.g. in the case of the symmetric group.

In general, it may be possible that more elements are
added to K=G_{i+1} before it reaches K=G_i, corresponding to a 
subgroup chain between G_i and G_{i+1}. 

Best regards,
Akos Seress



From wettl@erie.vma.bme.hu Tue Apr 12 10:04:00 1994
From:           "Wettl Ferenc" <wettl@erie.vma.bme.hu>
Date:           Tue, 12 Apr 94 10:04 +0100
Subject:        to finite geometers


Dear IntersectSet( GapUsers, FiniteGeometers );

I wrote some programs for handling finite Galois geometries. In the first
step I generated difference sets for PG(2,q) (q<500), difference families
for PG(3,p) (p<85), and studied the orbits of Singer group in PG(2,q). Next,
I plan to improve them for a program, which offers an environment for
studying problems in finite geometries. If 

 - you are interested in such a program, or
 - you have some ideas, how to do it, and what to do, or
 - you made or plan to make something similar, or
 - you have a problem, which needs this approach,

then please, write me, either through this forum, or directly to my address:

   wettl@euromath.vma.bme.hu

If you are interested in my outputs and programs (versions under
preparation), then you can read them on the machine

   euromath.vma.bme.hu

using anonymous ftp. The path to the files is

   pub/papers/wettl/gap

In this directory you can find a report (report.tex) written in LaTeX,
the difference sets (182KB), difference families (795KB), and some programs
and output files with the types of orbits. The programs use the package
MeatAxe. 

Best regards, 

Ferenc Wettl (wettl@euromath.vma.bme.hu)



From mas023@bangor.ac.uk Wed Apr 13 13:05:00 1994
From:           "Chris Wensley" <mas023@bangor.ac.uk>
Date:           Wed, 13 Apr 94 13:05 +0000 (GMT)
Subject:        GpHomByImages

I have a query about how GroupHomomorphismByImages works.
In the listing below  Q,P  are copies of D4 with  Q  an fp-group
and  P  a permutation group.  When mapping  Q  to  P  there is only
one way to express the images of the generators.  In the reverse
direction the image of generator   (1,2,3,4)   is listed 
(surprisingly to me) as   f.2^-1*f.1^-2*f.2^-1   rather than   f.1
(although, of course, these are equal).

(Sorry if this is a trivial query, but I am a new user.)

Chris Wensley

----------------------------- GAP listing ----------------------------------
LogTo("invmap.log");
Print("Isomorphisms between copies of dihedral D4\n\n");
f := FreeGroup(2, "f");
relQ := [ f.1^4, f.2^2, (f.1*f.2)^2 ];
Q := f/relQ;
genQ := Q.generators;
oQ := Size(Q);
elQ := Elements(Q);
Print("Q has generators:  ", genQ, "   and elements:\n", elQ, "\n\n");
P := Group( (1,2,3,4), (1,3) );
genP := P.generators;
P.name := "P";
oP := Size(P);
elP := Elements(P);
Print("P has generators:  ", genP, "   and elements:\n", elP, "\n\n");
isoQP := GroupHomomorphismByImages(Q,P,genQ,genP);
Print("   x             isoQP(x) \n");
Print("---------      ---------- \n");
for j in [1..oQ] do
  x := elQ[j];
  Print(x, "           ", Image(isoQP,x), "\n");
  od;
invPQ := InverseMapping(isoQP);
Print("\n   x             invPQ(x) \n");
Print("--------      ---------- \n");
for j in [1..oP] do
  x := elP[j];
  Print(x, "           ", Image(invPQ,x), "\n");
  od;

---------------------------- Output ------------------------------------

Isomorphisms between copies of dihedral D4

Q has generators:  [ f.1, f.2 ]   and elements:
[ IdWord, f.1, f.2, f.1^2, f.1*f.2, f.2*f.1, f.1^3, f.1^2*f.2 ]

P has generators:  [ (1,2,3,4), (1,3) ]   and elements:
[ (), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3) ]

   x             isoQP(x) 
---------      ---------- 
IdWord           ()
f.1           (1,2,3,4)
f.2           (1,3)
f.1^2           (1,3)(2,4)
f.1*f.2           (1,2)(3,4)
f.2*f.1           (1,4)(2,3)
f.1^3           (1,4,3,2)
f.1^2*f.2           (2,4)

   x             invPQ(x) 
--------      ---------- 
()           IdWord
(2,4)           f.2^-1*f.1^-2
(1,2)(3,4)           f.2^-1*f.1^-1
(1,2,3,4)           f.2^-1*f.1^-2*f.2^-1*f.1^-1
(1,3)           f.2^-1
(1,3)(2,4)           f.2^-1*f.1^-2*f.2^-1
(1,4,3,2)           f.1^-1
(1,4)(2,3)           f.2^-1*f.1^-3



From Martin.Schoenert@Math.RWTH-Aachen.DE Wed Apr 13 20:07:00 1994
From:           "Martin Schoenert" <Martin.Schoenert@Math.RWTH-Aachen.DE>
Date:           Wed, 13 Apr 94 20:07 +0100 (MET)
Subject:        Re: GpHomByImages

Chris Wensley writes in his e-mail message of 1994/04/13

    I have a query about how GroupHomomorphismByImages works.
    In the listing below  Q,P  are copies of D4 with  Q  an fp-group
    and  P  a permutation group.  When mapping  Q  to  P  there is only
    one way to express the images of the generators.  In the reverse
    direction the image of generator   (1,2,3,4)   is listed 
    (surprisingly to me) as   f.2^-1*f.1^-2*f.2^-1   rather than   f.1
    (although, of course, these are equal).

Here is what happens if you have a 'GroupHomomorphismByImages' from a
permutation group $P$.  First GAP computes the size of $P$.  Then it
constructs a (second) stabilizer chain for $P$, which is stored in the
record that represents the homomorphism (see "Stabilizer Chains" in the
manual for a explanation of what a stabilizer chain is).

Each computation is performed in parallel also with the images of the
generators.  That means that the stabilizer chain contains for each
strong generator $s_i$ also its image under the homomorphism $t_i$.

To compute the image of an arbitrary element $p$ in the permutation
group, this element is divided through the stabilizer chain, i.e.,
'Image' computes a word $w$ in the strong generators $s_i$, such that
$p w(s_i) = ()$.  In parallel we perform the same computation with the
images of the strong generators, i.e., we compute $w(t_i)$, which is
the inverse of the image.

Now when 'GroupHomomorphismByImages' constructs the stabilizer chain
it works essentially random.  That is, it constructs random elements
and builds the stabilizer chain from those.  It stops when the chain
is complete, i.e., when the product of the indices in the stabilizer
chain is equal to the size of the group $P$.

This helps to keep down the length of the words somewhat (but not enough
in most cases).  On the other hand it makes it impossible to predict what
word you get when you map from $P$ into the free group $F$ (or a factor
thereof, but the words are actually always in $F$).

He continues

    (Sorry if this is a trivial query, but I am a new user.)

There would be no need to apologize even if the question was trivial,
which it is not.

Hope this helps (if not, don't hesitate to ask again).

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany



From timhsu@math.princeton.edu Wed Apr 13 15:09:00 1994
From:           "Tim Hsu" <timhsu@math.princeton.edu>
Date:           Wed, 13 Apr 94 15:09 -0400 (EDT)
Subject:        Rewriting trivial words in relators

Hi.  I would like to be able to do the following thing: I have a
presentation of a finite group G, and I would like to be able to know,
say, the 100 "shortest" ways of expressing a word in the generators
which represents the identity in G as a product of conjugates of
relators.  Is this easy to do in GAP?  If not, do you know of another
program which does this?

Tim Hsu



From alice@maths.uwa.edu.au Thu Apr 14 16:57:00 1994
From:           "Alice Niemeyer" <alice@maths.uwa.edu.au>
Date:           Thu, 14 Apr 94 16:57 WST
Subject:        matrices


I am currently working with matrices over finite fields in GAP.
In my code I use the product A * Transposed(B). I was wondering
whether it might be possible to have an internal function for
this product avoiding the extra storage required for creating 
Transposed(B). 

Alice Niemeyer.

===========================================================================
Alice C Niemeyer,  Phone: (w) +61-9-380 3890, Email: alice@maths.uwa.edu.au
       Department of Mathematics, UWA, Nedlands WA 6009, Australia.



From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Apr 14 12:08:00 1994
From:           "Martin Schoenert" <Martin.Schoenert@Math.RWTH-Aachen.DE>
Date:           Thu, 14 Apr 94 12:08 +0100 (MET)
Subject:        Re: matrices

Alice Niemeyer writes in her e-mail message of 1994/04/14

    I am currently working with matrices over finite fields in GAP.
    In my code I use the product A * Transposed(B). I was wondering
    whether it might be possible to have an internal function for
    this product avoiding the extra storage required for creating 
    Transposed(B). 

Maybe I don't fully understand your problem, but wouldn't the following
function do?

    ProductMatTransposedMat := function ( A, B )
        local  P, i, k;
        P := [];
        for i  in [1..Length(A)]  do
            P[i] := [];
            for k  in [1..Length(B)]  do
                P[i][k] := A[i] * B[k];
            od;
        od;
        return P;
    end;

No extra storage required, and it should be reasonably fast, since most
of the time should be spent in the 'A[i] * B[k]' calculations, which is
handled in the kernel.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany



From Martin.Schoenert@Math.RWTH-Aachen.DE Thu Apr 14 12:51:00 1994
From:           "Martin Schoenert" <Martin.Schoenert@Math.RWTH-Aachen.DE>
Date:           Thu, 14 Apr 94 12:51 +0100 (MET)
Subject:        Re: Rewriting trivial words in relators

Tim Hsu writes in his e-mail article of 1994/04/13

    Hi.  I would like to be able to do the following thing: I have a
    presentation of a finite group G, and I would like to be able to know,
    say, the 100 "shortest" ways of expressing a word in the generators
    which represents the identity in G as a product of conjugates of
    relators.  Is this easy to do in GAP?  If not, do you know of another
    program which does this?

This is similar to the word problem, so I very much doubt that a good
deterministic algorithm exists.  What you could do is to systematically
enumerate the words in the relators and just check whether or not such a
word simplifies in the free group to the given word.  Obviously this
will only work if the given word has a rather short representation as
word in the relators.

Another possibility might be to add the given word to the generators, and
then to use Tietze transformations to get rid of the word again.  If one
keeps track of the transformations, this could be used to write the given
word in the original relators.  This is, however, not very likely to
give the shortest such representation.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany



From dfh@maths.warwick.ac.uk Thu Apr 14 12:35:00 1994
From:           "Derek Holt" <dfh@maths.warwick.ac.uk>
Date:           Thu, 14 Apr 94 12:35 +0100
Subject:        Re:  Rewriting trivial words in relators

> 
> Hi.  I would like to be able to do the following thing: I have a
> presentation of a finite group G, and I would like to be able to know,
> say, the 100 "shortest" ways of expressing a word in the generators
> which represents the identity in G as a product of conjugates of
> relators.  Is this easy to do in GAP?  If not, do you know of another
> program which does this?
> 
> Tim Hsu
> 

I think that is an extremely difficult problem, and I have never heard of
any kind of reasonable algorithmic approach to it. It is probably even
harder than Martin suggested in his reply, because one is not looking for
an expression of the trivial word as a product of relators, but as a product
of conjugates of relators.

In principal, the Knuth-Bendix algorithm, which systematically generates
consequences of the defining relations can be used to produce a machine
derivation of the triviality of any word in the generators which maps
onto the identity, and this could, theoretically, be used to express the
word as a product of conjugates of defining relators, but the result would
typically be a very long word indeed!

I know the question was about finite groups, but there are some theoretical
results of a more general nature that are related to this question. If
f(n) is the largest number of conjugates of defining relators that are
required to express any trivial word of length  n, then f(n) is called
the isoperimetric function for the group (more precisely for the presentation).
For finite groups, f(n) will have a maximal value, but infinite hyperbolic
groups have a linear isoperimetric function, automatic groups have a
quadratic, nilpotent groups have a polynomial, etc. 

Derek Holt.



From dima@maths.uwa.edu.au Thu Apr 14 20:15:00 1994
From:           "Dima Pasechnik" <dima@maths.uwa.edu.au>
Date:           Thu, 14 Apr 94 20:15 WST
Subject:        Re: Rewriting trivial words in relators

> 
> Tim Hsu writes in his e-mail article of 1994/04/13
> 
>     Hi.  I would like to be able to do the following thing: I have a
>     presentation of a finite group G, and I would like to be able to know,
>     say, the 100 "shortest" ways of expressing a word in the generators
>     which represents the identity in G as a product of conjugates of
>     relators.  Is this easy to do in GAP?  If not, do you know of another
>     program which does this?
> 
I'd guess that one has to measure that length as the number of relators
involved, is it correct?
I believe there are efficient algorithms which solve a simpler "abelianized"
problem, i.e. giving the answers modulo $G'$.

Dima



From mas023@bangor.ac.uk Fri Apr 15 14:22:00 1994
From:           "Chris Wensley" <mas023@bangor.ac.uk>
Date:           Fri, 15 Apr 94 14:22 +0000 (GMT)
Subject:        keeping track of the transformations


Martin Sch"onert, in his reply to Tim Hsu, writes:

" ..use Tietze transformations..  If one keeps track of the transformations.."

Since this is precisely what I want to do, I am asking how!
Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
is reduced, using  TzGo , to a presentation with generating set
  [ _x3, _x12, _x24 ] ,I want to remember expressions for the
21 eliminated generators as words in the three remaining ones.

I have not been able to discover a solution in the manual but 3 possible
methods suggest themselves.  Guidance as to which way to go would be much
appreciated.

1.  Avoid using the high-level  TzGo  and use the low-level commands
so that at each elimination the required formula can be saved.  Surely
this would amount to rewriting  TzGo ?

2.  Edit appropriate parts of the file  "fptietze.g" .
    This file is 40 pages long, with many interdependant functions,
so I should probably create a host of bugs?
    In any case, the functions use the  <Tietze record>  type, which
appears to be defined elsewhere, possibly in the kernel?

3.  Start a  LOG  file before using  TzGo  and so produce a file
containing messages of the form:
        #I  eliminating _x7 = _x18^5*_x5*_x4
As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
would be possible to write some utility to convert the LOG file into
a GAP file,  Exec  this utility, and  Read  the resulting GAP file?

Chris Wensley



From hwblist@machnix.mathematik.uni-stuttgart.de Sun Apr 17 20:34:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Sun, 17 Apr 94 20:34 +0200
Subject:        suggestion: fix for Gcd(0*q,0*q)

Hello!


While computing some Gcds in LaurentPolynomialRing(Rationals) I
noticed that Gcd(0*q,0*q) (where q=Indeterminate(Rationals) causes an
error. The reason is that
FieldLaurentPolynomialRingOps.StandardAssociate doesn't work for the 0
polynomial.

I therefore suggest the following changes to gap/lib/polyfld.g
(analogous to PolynomialRingOps.StandardAssociate):


*** polyfld.g	Tue Nov 09 00:54:00 1993
--- ../polyfld.g	Sun Apr 17 17:53:12 1994
***************
*** 53,59 ****
  #F  FieldPolynomialRingOps.StandardAssociate( <R>, <f> )  . . . .  normed pol
  ##
  FieldPolynomialRingOps.StandardAssociate := function( R, f )
!     return f * f.coefficients[ Length( f.coefficients ) ]^-1;
  end;


--- 53,63 ----
  #F  FieldPolynomialRingOps.StandardAssociate( <R>, <f> )  . . . .  normed pol
  ##
  FieldPolynomialRingOps.StandardAssociate := function( R, f )
!     if 0 < Length( f.coefficients ) then
!         return f * f.coefficients[ Length( f.coefficients ) ]^-1;
!     else
!         return f;
!     fi;
  end;


***************
*** 228,236 ****
  ##
  FieldLaurentPolynomialRingOps.StandardAssociate := function( R, f )
      local   l;
!
!     l := f.coefficients[Length(f.coefficients)];
!     return Polynomial( R.baseRing, f.coefficients*l^-1 );
  end;


--- 232,244 ----
  ##
  FieldLaurentPolynomialRingOps.StandardAssociate := function( R, f )
      local   l;
!
!     if 0 < Length( f.coefficients ) then
!         l := f.coefficients[Length(f.coefficients)];
!         return Polynomial( R.baseRing, f.coefficients*l^-1 );
!     else
!         return f;
!     fi;
  end;





--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From wang@maths.uwa.edu.au Mon Apr 18 11:38:00 1994
From:           "Wang" <wang@maths.uwa.edu.au>
Date:           Mon, 18 Apr 94 11:38 WST
Subject:        subgroup of large index

Hi Forum,
Given a finite group G and one of its maximal subgroup M. I want to know the lengths
of the M-orbits on the set {Mx | x in G}. The moset simple way I know is
List(DoubleCosets(G,M,M),x->Size(x)/Size(M));
However, while the index |G:M| is quite large, say 10^6, the above method failed.
Are there any other methods to get the lengths of M-orbits?
I also tried to calculate the cosets set of M in G, but it didn't work either.



From Martin.Schoenert@Math.RWTH-Aachen.DE Mon Apr 18 09:55:00 1994
From:           "Martin Schoenert" <Martin.Schoenert@Math.RWTH-Aachen.DE>
Date:           Mon, 18 Apr 94 09:55 +0100 (MET)
Subject:        Re: suggestion: fix for Gcd(0*q,0*q)

Thank you very much for your fix.  We will add this to GAP.  Have you
checked that those are the only places where this is done wrong?

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany



From Joachim.Neubueser@Math.RWTH-Aachen.DE Mon Apr 18 10:01:00 1994
From:           "Joachim Neubueser" <Joachim.Neubueser@Math.RWTH-Aachen.DE>
Date:           Mon, 18 Apr 94 10:01 +0200
Subject:        Re: subgroup of large index

? Wang asked: 
> Hi Forum,
> Given a finite group G and one of its maximal subgroup M. I want
> to know the lengths of the M-orbits on the set {Mx | x in G}. 
> The moset simple way I know is
> List(DoubleCosets(G,M,M),x->Size(x)/Size(M));
> However, while the index |G:M| is quite large, say 10^6, the above 
> method failed. Are there any other methods to get the lengths of 
> M-orbits? I also tried to calculate the cosets set of M in G, but 
> it didn't work either.

I am afraid the chances  are not very  good for any *general*  methods
that do not depend on the way, the group is given, and may not be very
good anyhow.  But could  you   just tell  how   your  group  is  given
(permutation,  matrix, fp group, character  table?).  Maybe in certain
cases somebody has an idea.

Joachim Neubueser



From hwblist@machnix.mathematik.uni-stuttgart.de Mon Apr 18 14:19:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Mon, 18 Apr 94 14:19 +0200
Subject:        Re: suggestion: fix for Gcd(0*q,0*q)

>   Date:           18 Apr 94 09:55 +0100 (MET)
>   From: Martin Schoenert  <martin.schoenert@math.rwth-aachen.de>
>
>   Thank you very much for your fix.  We will add this to GAP.  Have you
>   checked that those are the only places where this is done wrong?

No I haven't. I grepped the library for StandardAssociate and found
several definitions. Since I only needed
LaurentPolynomialRing(Rationals) at the moment, I didn't check any
other routines. Shouldn't be too difficult, though...


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Thu Apr 21 11:05:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Thu, 21 Apr 94 11:05 +0200
Subject:        Re: keeping track of the transformations

Chris Wensley writes:

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

As the discussion on keeping track of Tietze transformations is too
technical to be continued in the GAP forum, I have sent my answer to
the above letter directly to Chris Wensley. However, I would like to
encourage all those forum members who are interested in that question
to ask me for a copy of that correspondence.

Volkmar Felsch, Aachen



From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Fri, 22 Apr 94 18:14 +0200
Subject:        Re: keeping track of the transformations

>   Date:           21 Apr 94 11:05 +0200
>   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>

>   As the discussion on keeping track of Tietze transformations is too
>   technical to be continued in the GAP forum, I have sent my answer to
>   the above letter directly to Chris Wensley. 

Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.

So why not continue this discussion in public, i.e., in the forum?


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Mon, 25 Apr 94 09:28 +0200
Subject:        Re: keeping track of the transformations

Harald Boegeholz writes:

> 
> >   Date:           21 Apr 94 11:05 +0200
> >   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>
> 
> >   As the discussion on keeping track of Tietze transformations is too
> >   technical to be continued in the GAP forum, I have sent my answer to
> >   the above letter directly to Chris Wensley. 
> 
> Can any discussion about GAP be too technical to be continued in the
> GAP forum? I for one don't think so (except maybe if we are talking
> about machine specific implementation details); the traffic in the GAP
> forum is so low that I can easily ignore any messages I don't
> understand.
> 
> So why not continue this discussion in public, i.e., in the forum?
> 


In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.

In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.

Volkmar Felsch, Aachen


==============================================================================

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

Dear Dr. Wensley,

I will try to answer your above letter to the GAP forum.

The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.

I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.

Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form

        if T.printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, "\n" );
            else  Print( TzWord( tietze, word ), "\n" );  fi;
        fi;

and in each case you should duplicate them by adding something like

        if IsBound( P.keepTrack ) and P.keepTrack then
            Print( gens[num], " := " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, ";\n" );
            else  Print( TzWord( tietze, word ), ";\n" );  fi;
        fi;

(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like

        P.keepTrack := true;

before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)

Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)

I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.

Please feel free to contact me again if you have further questions.

Volkmar Felsch, Aachen

-----------------------------------------------------------------------------

#############################################################################
##
#F  TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators
##
##  'TzHandleLength1Or2Relators'  searches for  relators of length 1 or 2 and
##  performs suitable Tietze transformations for each of them:
##
##  Generators occurring in relators of length 1 are eliminated.
##
##  Generators  occurring  in square relators  of length 2  are marked  to be
##  involutions.
##
##  If a relator  of length 2  involves two  different  generators,  then the
##  generator with the  larger number is substituted  by the other one in all
##  relators and finally eliminated from the set of generators.
##
TzHandleLength1Or2Relators := function ( T )

    local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens,
          numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep,
          rep1, rep2, tietze, tree, treelength, treeNums;

    if T.printLevel >= 3 then  Print( "#I  handling short relators\n" );  fi;

    # check the given argument to be a Tietze record.
    if not ( IsBound( T.isTietze ) and T.isTietze ) then
        Error( "argument must be a Tietze record" );
    fi;
    tietze := T.tietze;

    gens := tietze[TZ_GENERATORS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    lengths := tietze[TZ_LENGTHS];
    flags := tietze[TZ_FLAGS];
    numgens := tietze[TZ_NUMGENS];
    numrels := tietze[TZ_NUMRELS];
    redunds := tietze[TZ_NUMREDUNDS];
    numgens1 := numgens + 1;
    done := false;

    tree := 0;
    if IsBound( T.tree ) then
        tree := T.tree;
        treelength := tree[TR_TREELENGTH];
        pointers := tree[TR_TREEPOINTERS];
        treeNums := tree[TR_TREENUMS];
    fi;

    while not done do

        done := true;

        # loop over all relators and find those of length 1 or 2.
        for i in [ 1 .. numrels ] do
            length := lengths[i];
            if length <= 2 and length > 0 and flags[i] <= 2 then

                done := false;

                # find the current representative of the first factor.
                rep1 := rels[i][1];
                while invs[numgens1-rep1] <> rep1 do
                    rep1 := invs[numgens1-rep1];
                od;

                if length = 1 then

                    # handle a relator of length 1.
                    if rep1 <> 0 then
                        rep1 := AbsInt( rep1 );
                        invs[numgens1-rep1] := 0;
                        invs[numgens1+rep1] := 0;
                        if tree <> 0 then
                            ptr1 := AbsInt( treeNums[rep1] );
                            pointers[ptr1] := 0;
                            treeNums[rep1] := 0;
                        fi;
                        if T.printLevel >= 2 then
                            Print( "#I  eliminating ", gens[rep1],
                                " = IdWord\n" );
                        fi;
###                     if IsBound( T.keepTrack ) and T.keepTrack then
###                         Print( gens[rep1], " := IdWord;\n" );
###                     fi;
                        redunds := redunds + 1;
                    fi;
                else

                    # find the current representative of the second factor.
                    rep2 := rels[i][2];
                    while invs[numgens1-rep2] <> rep2 do
                        rep2 := invs[numgens1-rep2];
                    od;

                    # handle a relator of length 2.
                    if AbsInt( rep2 ) < AbsInt( rep1 ) then
                        rep := rep1;  rep1 := rep2;  rep2 := rep;
                    fi;
                    if rep1 < 0 then  rep1 := - rep1;  rep2 := - rep2;  fi;
                    if rep1 = 0 then

                        # the relator is in fact of length at most 1.
                        if rep2 <> 0 then
                            rep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := 0;
                            invs[numgens1+rep2] := 0;
                            if tree <> 0 then
                                ptr2 := AbsInt( treeNums[rep2] );
                                pointers[ptr2] := 0;
                                treeNums[rep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[rep2],
                                    " = IdWord\n" );
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[rep2], " := IdWord;\n" );
###                         fi;
                            redunds := redunds + 1;
                        fi;

                    elif rep1 <> - rep2 then

                        if invs[numgens1+rep1] < 0 and ( rep1 = rep2 or
                            invs[numgens1-rep2] = invs[numgens1+rep2] ) then
                            # make the relator a square relator, ...
                            rels[i][1] := rep1;  rels[i][2] := rep1;
                            # ... mark it appropriately, ...
                            flags[i] := 3;
                            # ... and mark rep1 to be an involution.
                            invs[numgens1+rep1] := rep1;
                        fi;

                        # handle a non-square relator of length 2.
                        if rep1 <> rep2 then
                            absrep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := invs[numgens1+rep1];
                            invs[numgens1+rep2] := rep1;
                            if tree <> 0 then

                                ptr1 := AbsInt( treeNums[rep1] );
                                ptr2 := AbsInt( treeNums[absrep2] );
                                if ptr2 < ptr1 then
                                    ptr := ptr2;
                                    if treeNums[rep1] * treeNums[absrep2]
                                        * rep2 > 0 then
                                        ptr := - ptr;
                                        treeNums[rep1] := ptr;
                                        pointers[ptr1] := treelength + rep1;
                                    fi;
                                    ptr2 := ptr1;
                                    ptr1 := AbsInt( ptr );
                                fi;
                                if rep2 > 0 then
                                    ptr1 := - ptr1;
                                fi;
                                pointers[ptr2] := ptr1;
                                treeNums[absrep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[absrep2],
                                    " = " );
                                if rep2 > 0 then
                                    Print( TzWord( tietze,
                                        [ invs[numgens1+rep1] ] ), "\n" );
                                else
                                    Print( gens[rep1], "\n" );
                                fi;
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[absrep2], " := " );
###                             if rep2 > 0 then
###                                 Print( TzWord( tietze,
###                                     [ invs[numgens1+rep1] ] ), ";\n" );
###                             else
###                                 Print( gens[rep1], ";\n" );
###                             fi;
###                         fi;
                            redunds := redunds + 1;

                        fi;
                    fi;
                fi;
            fi;
        od;

        if not done then

            # for each generator determine its current representative.
            for i in [ 1 .. numgens ] do
                if invs[numgens1-i] <> i then
                    rep := invs[numgens1-i];
                    invs[numgens1-i] := invs[numgens1-rep];
                    invs[numgens1+i] := invs[numgens1+rep];
                fi;
            od;

            # perform the replacements.
            TzReplaceGens( tietze );
        fi;
    od;

    # tidy up the Tietze generators.
    tietze[TZ_NUMREDUNDS] := redunds;
    if redunds > 0 then  TzRemoveGenerators( T );  fi;

    # Print( "#I  total length = ", tietze[TZ_TOTAL], "\n" );
end;


==============================================================================


Dear Dr. Felsch,

Thank you for your very helpful message yesterday.

The significant part of the reply was:
     "Here I assume that 'P.keepTrack' is a new component ...
      ..... to be introduced by a statement like
                  P.keepTrack := true;

I was amazed and delighted to discover that new components can be added
to a record so easily.  (I must admit that, until today, I had only glanced
briefly at the chapter on records in the manual.)

So I propose to add a new component to a presentation record, initiallytion
to ask me for a copy of that correspondence.

Volkmar Felsch, Aachen



From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Fri, 22 Apr 94 18:14 +0200
Subject:        Re: keeping track of the transformations

>   Date:           21 Apr 94 11:05 +0200
>   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>

>   As the discussion on keeping track of Tietze transformations is too
>   technical to be continued in the GAP forum, I have sent my answer to
>   the above letter directly to Chris Wensley. 

Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.

So why not continue this discussion in public, i.e., in the forum?


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Mon, 25 Apr 94 09:28 +0200
Subject:        Re: keeping track of the transformations

Harald Boegeholz writes:

> 
> >   Date:           21 Apr 94 11:05 +0200
> >   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>
> 
> >   As the discussion on keeping track of Tietze transformations is too
> >   technical to be continued in the GAP forum, I have sent my answer to
> >   the above letter directly to Chris Wensley. 
> 
> Can any discussion about GAP be too technical to be continued in the
> GAP forum? I for one don't think so (except maybe if we are talking
> about machine specific implementation details); the traffic in the GAP
> forum is so low that I can easily ignore any messages I don't
> understand.
> 
> So why not continue this discussion in public, i.e., in the forum?
> 


In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.

In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.

Volkmar Felsch, Aachen


==============================================================================

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

Dear Dr. Wensley,

I will try to answer your above letter to the GAP forum.

The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.

I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.

Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form

        if T.printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, "\n" );
            else  Print( TzWord( tietze, word ), "\n" );  fi;
        fi;

and in each case you should duplicate them by adding something like

        if IsBound( P.keepTrack ) and P.keepTrack then
            Print( gens[num], " := " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, ";\n" );
            else  Print( TzWord( tietze, word ), ";\n" );  fi;
        fi;

(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like

        P.keepTrack := true;

before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)

Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)

I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.

Please feel free to contact me again if you have further questions.

Volkmar Felsch, Aachen

-----------------------------------------------------------------------------

#############################################################################
##
#F  TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators
##
##  'TzHandleLength1Or2Relators'  searches for  relators of length 1 or 2 and
##  performs suitable Tietze transformations for each of them:
##
##  Generators occurring in relators of length 1 are eliminated.
##
##  Generators  occurring  in square relators  of length 2  are marked  to be
##  involutions.
##
##  If a relator  of length 2  involves two  different  generators,  then the
##  generator with the  larger number is substituted  by the other one in all
##  relators and finally eliminated from the set of generators.
##
TzHandleLength1Or2Relators := function ( T )

    local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens,
          numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep,
          rep1, rep2, tietze, tree, treelength, treeNums;

    if T.printLevel >= 3 then  Print( "#I  handling short relators\n" );  fi;

    # check the given argument to be a Tietze record.
    if not ( IsBound( T.isTietze ) and T.isTietze ) then
        Error( "argument must be a Tietze record" );
    fi;
    tietze := T.tietze;

    gens := tietze[TZ_GENERATORS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    lengths := tietze[TZ_LENGTHS];
    flags := tietze[TZ_FLAGS];
    numgens := tietze[TZ_NUMGENS];
    numrels := tietze[TZ_NUMRELS];
    redunds := tietze[TZ_NUMREDUNDS];
    numgens1 := numgens + 1;
    done := false;

    tree := 0;
    if IsBound( T.tree ) then
        tree := T.tree;
        treelength := tree[TR_TREELENGTH];
        pointers := tree[TR_TREEPOINTERS];
        treeNums := tree[TR_TREENUMS];
    fi;

    while not done do

        done := true;

        # loop over all relators and find those of length 1 or 2.
        for i in [ 1 .. numrels ] do
            length := lengths[i];
            if length <= 2 and length > 0 and flags[i] <= 2 then

                done := false;

                # find the current representative of the first factor.
                rep1 := rels[i][1];
                while invs[numgens1-rep1] <> rep1 do
                    rep1 := invs[numgens1-rep1];
                od;

                if length = 1 then

                    # handle a relator of length 1.
                    if rep1 <> 0 then
                        rep1 := AbsInt( rep1 );
                        invs[numgens1-rep1] := 0;
                        invs[numgens1+rep1] := 0;
                        if tree <> 0 then
                            ptr1 := AbsInt( treeNums[rep1] );
                            pointers[ptr1] := 0;
                            treeNums[rep1] := 0;
                        fi;
                        if T.printLevel >= 2 then
                            Print( "#I  eliminating ", gens[rep1],
                                " = IdWord\n" );
                        fi;
###                     if IsBound( T.keepTrack ) and T.keepTrack then
###                         Print( gens[rep1], " := IdWord;\n" );
###                     fi;
                        redunds := redunds + 1;
                    fi;
                else

                    # find the current representative of the second factor.
                    rep2 := rels[i][2];
                    while invs[numgens1-rep2] <> rep2 do
                        rep2 := invs[numgens1-rep2];
                    od;

                    # handle a relator of length 2.
                    if AbsInt( rep2 ) < AbsInt( rep1 ) then
                        rep := rep1;  rep1 := rep2;  rep2 := rep;
                    fi;
                    if rep1 < 0 then  rep1 := - rep1;  rep2 := - rep2;  fi;
                    if rep1 = 0 then

                        # the relator is in fact of length at most 1.
                        if rep2 <> 0 then
                            rep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := 0;
                            invs[numgens1+rep2] := 0;
                            if tree <> 0 then
                                ptr2 := AbsInt( treeNums[rep2] );
                                pointers[ptr2] := 0;
                                treeNums[rep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[rep2],
                                    " = IdWord\n" );
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[rep2], " := IdWord;\n" );
###                         fi;
                            redunds := redunds + 1;
                        fi;

                    elif rep1 <> - rep2 then

                        if invs[numgens1+rep1] < 0 and ( rep1 = rep2 or
                            invs[numgens1-rep2] = invs[numgens1+rep2] ) then
                            # make the relator a square relator, ...
                            rels[i][1] := rep1;  rels[i][2] := rep1;
                            # ... mark it appropriately, ...
                            flags[i] := 3;
                            # ... and mark rep1 to be an involution.
                            invs[numgens1+rep1] := rep1;
                        fi;

                        # handle a non-square relator of length 2.
                        if rep1 <> rep2 then
                            absrep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := invs[numgens1+rep1];
                            invs[numgens1+rep2] := rep1;
                            if tree <> 0 then

                                ptr1 := AbsInt( treeNums[rep1] );
                                ptr2 := AbsInt( treeNums[absrep2] );
                                if ptr2 < ptr1 then
                                    ptr := ptr2;
                                    if treeNums[rep1] * treeNums[absrep2]
                                        * rep2 > 0 then
                                        ptr := - ptr;
                                        treeNums[rep1] := ptr;
                                        pointers[ptr1] := treelength + rep1;
                                    fi;
                                    ptr2 := ptr1;
                                    ptr1 := AbsInt( ptr );
                                fi;
                                if rep2 > 0 then
                                    ptr1 := - ptr1;
                                fi;
                                pointers[ptr2] := ptr1;
                                treeNums[absrep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[absrep2],
                                    " = " );
                                if rep2 > 0 then
                                    Print( TzWord( tietze,
                                        [ invs[numgens1+rep1] ] ), "\n" );
                                else
                                    Print( gens[rep1], "\n" );
                                fi;
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[absrep2], " := " );
###                             if rep2 > 0 then
###                                 Print( TzWord( tietze,
###                                     [ invs[numgens1+rep1] ] ), ";\n" );
###                             else
###                                 Print( gens[rep1], ";\n" );
###                             fi;
###                         fi;
                            redunds := redunds + 1;

                        fi;
                    fi;
                fi;
            fi;
        od;

        if not done then

            # for each generator determine its current representative.
            for i in [ 1 .. numgens ] do
                if invs[numgens1-i] <> i then
                    rep := invs[numgens1-i];
                    invs[numgens1-i] := invs[numgens1-rep];
                    invs[numgens1+i] := invs[numgens1+rep];
                fi;
            od;

            # perform the replacements.
            TzReplaceGens( tietze );
        fi;
    od;

    # tidy up the Tietze generators.
    tietze[TZ_NUMREDUNDS] := redunds;
    if redunds > 0 then  TzRemoveGenerators( T );  fi;

    # Print( "#I  total length = ", tietze[TZ_TOTAL], "\n" );
end;


==============================================================================


Dear Dr. Felsch,

Thank you for your very helpful message yesterday.

The significant part of the reply was:
     "Here I assume that 'P.keepTrack' is a new component ...
      ..... to be introduced by a statement like
                  P.keepTrack := true;

I was amazed and delighted to discover that new components can be added
to a record so easily.  (I must admit that, until today, I had only glanced
briefly at the chapter on records in the manual.)

So I propose to add a new component to a presentation record, initiallytion
to ask me for a copy of that correspondence.

Volkmar Felsch, Aachen



From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Fri, 22 Apr 94 18:14 +0200
Subject:        Re: keeping track of the transformations

>   Date:           21 Apr 94 11:05 +0200
>   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>

>   As the discussion on keeping track of Tietze transformations is too
>   technical to be continued in the GAP forum, I have sent my answer to
>   the above letter directly to Chris Wensley. 

Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.

So why not continue this discussion in public, i.e., in the forum?


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Mon, 25 Apr 94 09:28 +0200
Subject:        Re: keeping track of the transformations

Harald Boegeholz writes:

> 
> >   Date:           21 Apr 94 11:05 +0200
> >   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>
> 
> >   As the discussion on keeping track of Tietze transformations is too
> >   technical to be continued in the GAP forum, I have sent my answer to
> >   the above letter directly to Chris Wensley. 
> 
> Can any discussion about GAP be too technical to be continued in the
> GAP forum? I for one don't think so (except maybe if we are talking
> about machine specific implementation details); the traffic in the GAP
> forum is so low that I can easily ignore any messages I don't
> understand.
> 
> So why not continue this discussion in public, i.e., in the forum?
> 


In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.

In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.

Volkmar Felsch, Aachen


==============================================================================

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

Dear Dr. Wensley,

I will try to answer your above letter to the GAP forum.

The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.

I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.

Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form

        if T.printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, "\n" );
            else  Print( TzWord( tietze, word ), "\n" );  fi;
        fi;

and in each case you should duplicate them by adding something like

        if IsBound( P.keepTrack ) and P.keepTrack then
            Print( gens[num], " := " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, ";\n" );
            else  Print( TzWord( tietze, word ), ";\n" );  fi;
        fi;

(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like

        P.keepTrack := true;

before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)

Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)

I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.

Please feel free to contact me again if you have further questions.

Volkmar Felsch, Aachen

-----------------------------------------------------------------------------

#############################################################################
##
#F  TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators
##
##  'TzHandleLength1Or2Relators'  searches for  relators of length 1 or 2 and
##  performs suitable Tietze transformations for each of them:
##
##  Generators occurring in relators of length 1 are eliminated.
##
##  Generators  occurring  in square relators  of length 2  are marked  to be
##  involutions.
##
##  If a relator  of length 2  involves two  different  generators,  then the
##  generator with the  larger number is substituted  by the other one in all
##  relators and finally eliminated from the set of generators.
##
TzHandleLength1Or2Relators := function ( T )

    local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens,
          numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep,
          rep1, rep2, tietze, tree, treelength, treeNums;

    if T.printLevel >= 3 then  Print( "#I  handling short relators\n" );  fi;

    # check the given argument to be a Tietze record.
    if not ( IsBound( T.isTietze ) and T.isTietze ) then
        Error( "argument must be a Tietze record" );
    fi;
    tietze := T.tietze;

    gens := tietze[TZ_GENERATORS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    lengths := tietze[TZ_LENGTHS];
    flags := tietze[TZ_FLAGS];
    numgens := tietze[TZ_NUMGENS];
    numrels := tietze[TZ_NUMRELS];
    redunds := tietze[TZ_NUMREDUNDS];
    numgens1 := numgens + 1;
    done := false;

    tree := 0;
    if IsBound( T.tree ) then
        tree := T.tree;
        treelength := tree[TR_TREELENGTH];
        pointers := tree[TR_TREEPOINTERS];
        treeNums := tree[TR_TREENUMS];
    fi;

    while not done do

        done := true;

        # loop over all relators and find those of length 1 or 2.
        for i in [ 1 .. numrels ] do
            length := lengths[i];
            if length <= 2 and length > 0 and flags[i] <= 2 then

                done := false;

                # find the current representative of the first factor.
                rep1 := rels[i][1];
                while invs[numgens1-rep1] <> rep1 do
                    rep1 := invs[numgens1-rep1];
                od;

                if length = 1 then

                    # handle a relator of length 1.
                    if rep1 <> 0 then
                        rep1 := AbsInt( rep1 );
                        invs[numgens1-rep1] := 0;
                        invs[numgens1+rep1] := 0;
                        if tree <> 0 then
                            ptr1 := AbsInt( treeNums[rep1] );
                            pointers[ptr1] := 0;
                            treeNums[rep1] := 0;
                        fi;
                        if T.printLevel >= 2 then
                            Print( "#I  eliminating ", gens[rep1],
                                " = IdWord\n" );
                        fi;
###                     if IsBound( T.keepTrack ) and T.keepTrack then
###                         Print( gens[rep1], " := IdWord;\n" );
###                     fi;
                        redunds := redunds + 1;
                    fi;
                else

                    # find the current representative of the second factor.
                    rep2 := rels[i][2];
                    while invs[numgens1-rep2] <> rep2 do
                        rep2 := invs[numgens1-rep2];
                    od;

                    # handle a relator of length 2.
                    if AbsInt( rep2 ) < AbsInt( rep1 ) then
                        rep := rep1;  rep1 := rep2;  rep2 := rep;
                    fi;
                    if rep1 < 0 then  rep1 := - rep1;  rep2 := - rep2;  fi;
                    if rep1 = 0 then

                        # the relator is in fact of length at most 1.
                        if rep2 <> 0 then
                            rep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := 0;
                            invs[numgens1+rep2] := 0;
                            if tree <> 0 then
                                ptr2 := AbsInt( treeNums[rep2] );
                                pointers[ptr2] := 0;
                                treeNums[rep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[rep2],
                                    " = IdWord\n" );
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[rep2], " := IdWord;\n" );
###                         fi;
                            redunds := redunds + 1;
                        fi;

                    elif rep1 <> - rep2 then

                        if invs[numgens1+rep1] < 0 and ( rep1 = rep2 or
                            invs[numgens1-rep2] = invs[numgens1+rep2] ) then
                            # make the relator a square relator, ...
                            rels[i][1] := rep1;  rels[i][2] := rep1;
                            # ... mark it appropriately, ...
                            flags[i] := 3;
                            # ... and mark rep1 to be an involution.
                            invs[numgens1+rep1] := rep1;
                        fi;

                        # handle a non-square relator of length 2.
                        if rep1 <> rep2 then
                            absrep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := invs[numgens1+rep1];
                            invs[numgens1+rep2] := rep1;
                            if tree <> 0 then

                                ptr1 := AbsInt( treeNums[rep1] );
                                ptr2 := AbsInt( treeNums[absrep2] );
                                if ptr2 < ptr1 then
                                    ptr := ptr2;
                                    if treeNums[rep1] * treeNums[absrep2]
                                        * rep2 > 0 then
                                        ptr := - ptr;
                                        treeNums[rep1] := ptr;
                                        pointers[ptr1] := treelength + rep1;
                                    fi;
                                    ptr2 := ptr1;
                                    ptr1 := AbsInt( ptr );
                                fi;
                                if rep2 > 0 then
                                    ptr1 := - ptr1;
                                fi;
                                pointers[ptr2] := ptr1;
                                treeNums[absrep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[absrep2],
                                    " = " );
                                if rep2 > 0 then
                                    Print( TzWord( tietze,
                                        [ invs[numgens1+rep1] ] ), "\n" );
                                else
                                    Print( gens[rep1], "\n" );
                                fi;
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[absrep2], " := " );
###                             if rep2 > 0 then
###                                 Print( TzWord( tietze,
###                                     [ invs[numgens1+rep1] ] ), ";\n" );
###                             else
###                                 Print( gens[rep1], ";\n" );
###                             fi;
###                         fi;
                            redunds := redunds + 1;

                        fi;
                    fi;
                fi;
            fi;
        od;

        if not done then

            # for each generator determine its current representative.
            for i in [ 1 .. numgens ] do
                if invs[numgens1-i] <> i then
                    rep := invs[numgens1-i];
                    invs[numgens1-i] := invs[numgens1-rep];
                    invs[numgens1+i] := invs[numgens1+rep];
                fi;
            od;

            # perform the replacements.
            TzReplaceGens( tietze );
        fi;
    od;

    # tidy up the Tietze generators.
    tietze[TZ_NUMREDUNDS] := redunds;
    if redunds > 0 then  TzRemoveGenerators( T );  fi;

    # Print( "#I  total length = ", tietze[TZ_TOTAL], "\n" );
end;


==============================================================================


Dear Dr. Felsch,

Thank you for your very helpful message yesterday.

The significant part of the reply was:
     "Here I assume that 'P.keepTrack' is a new component ...
      ..... to be introduced by a statement like
                  P.keepTrack := true;

I was amazed and delighted to discover that new components can be added
to a record so easily.  (I must admit that, until today, I had only glanced
briefly at the chapter on records in the manual.)

So I propose to add a new component to a presentation record, initiallytion
to ask me for a copy of that correspondence.

Volkmar Felsch, Aachen



From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Fri, 22 Apr 94 18:14 +0200
Subject:        Re: keeping track of the transformations

>   Date:           21 Apr 94 11:05 +0200
>   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>

>   As the discussion on keeping track of Tietze transformations is too
>   technical to be continued in the GAP forum, I have sent my answer to
>   the above letter directly to Chris Wensley. 

Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.

So why not continue this discussion in public, i.e., in the forum?


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Mon, 25 Apr 94 09:28 +0200
Subject:        Re: keeping track of the transformations

Harald Boegeholz writes:

> 
> >   Date:           21 Apr 94 11:05 +0200
> >   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>
> 
> >   As the discussion on keeping track of Tietze transformations is too
> >   technical to be continued in the GAP forum, I have sent my answer to
> >   the above letter directly to Chris Wensley. 
> 
> Can any discussion about GAP be too technical to be continued in the
> GAP forum? I for one don't think so (except maybe if we are talking
> about machine specific implementation details); the traffic in the GAP
> forum is so low that I can easily ignore any messages I don't
> understand.
> 
> So why not continue this discussion in public, i.e., in the forum?
> 


In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.

In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.

Volkmar Felsch, Aachen


==============================================================================

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

Dear Dr. Wensley,

I will try to answer your above letter to the GAP forum.

The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.

I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.

Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form

        if T.printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, "\n" );
            else  Print( TzWord( tietze, word ), "\n" );  fi;
        fi;

and in each case you should duplicate them by adding something like

        if IsBound( P.keepTrack ) and P.keepTrack then
            Print( gens[num], " := " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, ";\n" );
            else  Print( TzWord( tietze, word ), ";\n" );  fi;
        fi;

(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like

        P.keepTrack := true;

before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)

Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)

I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.

Please feel free to contact me again if you have further questions.

Volkmar Felsch, Aachen

-----------------------------------------------------------------------------

#############################################################################
##
#F  TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators
##
##  'TzHandleLength1Or2Relators'  searches for  relators of length 1 or 2 and
##  performs suitable Tietze transformations for each of them:
##
##  Generators occurring in relators of length 1 are eliminated.
##
##  Generators  occurring  in square relators  of length 2  are marked  to be
##  involutions.
##
##  If a relator  of length 2  involves two  different  generators,  then the
##  generator with the  larger number is substituted  by the other one in all
##  relators and finally eliminated from the set of generators.
##
TzHandleLength1Or2Relators := function ( T )

    local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens,
          numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep,
          rep1, rep2, tietze, tree, treelength, treeNums;

    if T.printLevel >= 3 then  Print( "#I  handling short relators\n" );  fi;

    # check the given argument to be a Tietze record.
    if not ( IsBound( T.isTietze ) and T.isTietze ) then
        Error( "argument must be a Tietze record" );
    fi;
    tietze := T.tietze;

    gens := tietze[TZ_GENERATORS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    lengths := tietze[TZ_LENGTHS];
    flags := tietze[TZ_FLAGS];
    numgens := tietze[TZ_NUMGENS];
    numrels := tietze[TZ_NUMRELS];
    redunds := tietze[TZ_NUMREDUNDS];
    numgens1 := numgens + 1;
    done := false;

    tree := 0;
    if IsBound( T.tree ) then
        tree := T.tree;
        treelength := tree[TR_TREELENGTH];
        pointers := tree[TR_TREEPOINTERS];
        treeNums := tree[TR_TREENUMS];
    fi;

    while not done do

        done := true;

        # loop over all relators and find those of length 1 or 2.
        for i in [ 1 .. numrels ] do
            length := lengths[i];
            if length <= 2 and length > 0 and flags[i] <= 2 then

                done := false;

                # find the current representative of the first factor.
                rep1 := rels[i][1];
                while invs[numgens1-rep1] <> rep1 do
                    rep1 := invs[numgens1-rep1];
                od;

                if length = 1 then

                    # handle a relator of length 1.
                    if rep1 <> 0 then
                        rep1 := AbsInt( rep1 );
                        invs[numgens1-rep1] := 0;
                        invs[numgens1+rep1] := 0;
                        if tree <> 0 then
                            ptr1 := AbsInt( treeNums[rep1] );
                            pointers[ptr1] := 0;
                            treeNums[rep1] := 0;
                        fi;
                        if T.printLevel >= 2 then
                            Print( "#I  eliminating ", gens[rep1],
                                " = IdWord\n" );
                        fi;
###                     if IsBound( T.keepTrack ) and T.keepTrack then
###                         Print( gens[rep1], " := IdWord;\n" );
###                     fi;
                        redunds := redunds + 1;
                    fi;
                else

                    # find the current representative of the second factor.
                    rep2 := rels[i][2];
                    while invs[numgens1-rep2] <> rep2 do
                        rep2 := invs[numgens1-rep2];
                    od;

                    # handle a relator of length 2.
                    if AbsInt( rep2 ) < AbsInt( rep1 ) then
                        rep := rep1;  rep1 := rep2;  rep2 := rep;
                    fi;
                    if rep1 < 0 then  rep1 := - rep1;  rep2 := - rep2;  fi;
                    if rep1 = 0 then

                        # the relator is in fact of length at most 1.
                        if rep2 <> 0 then
                            rep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := 0;
                            invs[numgens1+rep2] := 0;
                            if tree <> 0 then
                                ptr2 := AbsInt( treeNums[rep2] );
                                pointers[ptr2] := 0;
                                treeNums[rep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[rep2],
                                    " = IdWord\n" );
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[rep2], " := IdWord;\n" );
###                         fi;
                            redunds := redunds + 1;
                        fi;

                    elif rep1 <> - rep2 then

                        if invs[numgens1+rep1] < 0 and ( rep1 = rep2 or
                            invs[numgens1-rep2] = invs[numgens1+rep2] ) then
                            # make the relator a square relator, ...
                            rels[i][1] := rep1;  rels[i][2] := rep1;
                            # ... mark it appropriately, ...
                            flags[i] := 3;
                            # ... and mark rep1 to be an involution.
                            invs[numgens1+rep1] := rep1;
                        fi;

                        # handle a non-square relator of length 2.
                        if rep1 <> rep2 then
                            absrep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := invs[numgens1+rep1];
                            invs[numgens1+rep2] := rep1;
                            if tree <> 0 then

                                ptr1 := AbsInt( treeNums[rep1] );
                                ptr2 := AbsInt( treeNums[absrep2] );
                                if ptr2 < ptr1 then
                                    ptr := ptr2;
                                    if treeNums[rep1] * treeNums[absrep2]
                                        * rep2 > 0 then
                                        ptr := - ptr;
                                        treeNums[rep1] := ptr;
                                        pointers[ptr1] := treelength + rep1;
                                    fi;
                                    ptr2 := ptr1;
                                    ptr1 := AbsInt( ptr );
                                fi;
                                if rep2 > 0 then
                                    ptr1 := - ptr1;
                                fi;
                                pointers[ptr2] := ptr1;
                                treeNums[absrep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[absrep2],
                                    " = " );
                                if rep2 > 0 then
                                    Print( TzWord( tietze,
                                        [ invs[numgens1+rep1] ] ), "\n" );
                                else
                                    Print( gens[rep1], "\n" );
                                fi;
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[absrep2], " := " );
###                             if rep2 > 0 then
###                                 Print( TzWord( tietze,
###                                     [ invs[numgens1+rep1] ] ), ";\n" );
###                             else
###                                 Print( gens[rep1], ";\n" );
###                             fi;
###                         fi;
                            redunds := redunds + 1;

                        fi;
                    fi;
                fi;
            fi;
        od;

        if not done then

            # for each generator determine its current representative.
            for i in [ 1 .. numgens ] do
                if invs[numgens1-i] <> i then
                    rep := invs[numgens1-i];
                    invs[numgens1-i] := invs[numgens1-rep];
                    invs[numgens1+i] := invs[numgens1+rep];
                fi;
            od;

            # perform the replacements.
            TzReplaceGens( tietze );
        fi;
    od;

    # tidy up the Tietze generators.
    tietze[TZ_NUMREDUNDS] := redunds;
    if redunds > 0 then  TzRemoveGenerators( T );  fi;

    # Print( "#I  total length = ", tietze[TZ_TOTAL], "\n" );
end;


==============================================================================


Dear Dr. Felsch,

Thank you for your very helpful message yesterday.

The significant part of the reply was:
     "Here I assume that 'P.keepTrack' is a new component ...
      ..... to be introduced by a statement like
                  P.keepTrack := true;

I was amazed and delighted to discover that new components can be added
to a record so easily.  (I must admit that, until today, I had only glanced
briefly at the chapter on records in the manual.)

So I propose to add a new component to a presentation record, initiallytion
to ask me for a copy of that correspondence.

Volkmar Felsch, Aachen



From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Fri, 22 Apr 94 18:14 +0200
Subject:        Re: keeping track of the transformations

>   Date:           21 Apr 94 11:05 +0200
>   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>

>   As the discussion on keeping track of Tietze transformations is too
>   technical to be continued in the GAP forum, I have sent my answer to
>   the above letter directly to Chris Wensley. 

Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.

So why not continue this discussion in public, i.e., in the forum?


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Mon, 25 Apr 94 09:28 +0200
Subject:        Re: keeping track of the transformations

Harald Boegeholz writes:

> 
> >   Date:           21 Apr 94 11:05 +0200
> >   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>
> 
> >   As the discussion on keeping track of Tietze transformations is too
> >   technical to be continued in the GAP forum, I have sent my answer to
> >   the above letter directly to Chris Wensley. 
> 
> Can any discussion about GAP be too technical to be continued in the
> GAP forum? I for one don't think so (except maybe if we are talking
> about machine specific implementation details); the traffic in the GAP
> forum is so low that I can easily ignore any messages I don't
> understand.
> 
> So why not continue this discussion in public, i.e., in the forum?
> 


In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.

In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.

Volkmar Felsch, Aachen


==============================================================================

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

Dear Dr. Wensley,

I will try to answer your above letter to the GAP forum.

The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.

I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.

Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form

        if T.printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, "\n" );
            else  Print( TzWord( tietze, word ), "\n" );  fi;
        fi;

and in each case you should duplicate them by adding something like

        if IsBound( P.keepTrack ) and P.keepTrack then
            Print( gens[num], " := " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, ";\n" );
            else  Print( TzWord( tietze, word ), ";\n" );  fi;
        fi;

(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like

        P.keepTrack := true;

before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)

Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)

I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.

Please feel free to contact me again if you have further questions.

Volkmar Felsch, Aachen

-----------------------------------------------------------------------------

#############################################################################
##
#F  TzHandleLength1Or2Relators( <Tietze record> ) . . . handle short relators
##
##  'TzHandleLength1Or2Relators'  searches for  relators of length 1 or 2 and
##  performs suitable Tietze transformations for each of them:
##
##  Generators occurring in relators of length 1 are eliminated.
##
##  Generators  occurring  in square relators  of length 2  are marked  to be
##  involutions.
##
##  If a relator  of length 2  involves two  different  generators,  then the
##  generator with the  larger number is substituted  by the other one in all
##  relators and finally eliminated from the set of generators.
##
TzHandleLength1Or2Relators := function ( T )

    local absrep2, done, flags, gens, i, invs, j, length, lengths, numgens,
          numgens1, numrels, pointers, ptr, ptr1, ptr2, redunds, rels, rep,
          rep1, rep2, tietze, tree, treelength, treeNums;

    if T.printLevel >= 3 then  Print( "#I  handling short relators\n" );  fi;

    # check the given argument to be a Tietze record.
    if not ( IsBound( T.isTietze ) and T.isTietze ) then
        Error( "argument must be a Tietze record" );
    fi;
    tietze := T.tietze;

    gens := tietze[TZ_GENERATORS];
    invs := tietze[TZ_INVERSES];
    rels := tietze[TZ_RELATORS];
    lengths := tietze[TZ_LENGTHS];
    flags := tietze[TZ_FLAGS];
    numgens := tietze[TZ_NUMGENS];
    numrels := tietze[TZ_NUMRELS];
    redunds := tietze[TZ_NUMREDUNDS];
    numgens1 := numgens + 1;
    done := false;

    tree := 0;
    if IsBound( T.tree ) then
        tree := T.tree;
        treelength := tree[TR_TREELENGTH];
        pointers := tree[TR_TREEPOINTERS];
        treeNums := tree[TR_TREENUMS];
    fi;

    while not done do

        done := true;

        # loop over all relators and find those of length 1 or 2.
        for i in [ 1 .. numrels ] do
            length := lengths[i];
            if length <= 2 and length > 0 and flags[i] <= 2 then

                done := false;

                # find the current representative of the first factor.
                rep1 := rels[i][1];
                while invs[numgens1-rep1] <> rep1 do
                    rep1 := invs[numgens1-rep1];
                od;

                if length = 1 then

                    # handle a relator of length 1.
                    if rep1 <> 0 then
                        rep1 := AbsInt( rep1 );
                        invs[numgens1-rep1] := 0;
                        invs[numgens1+rep1] := 0;
                        if tree <> 0 then
                            ptr1 := AbsInt( treeNums[rep1] );
                            pointers[ptr1] := 0;
                            treeNums[rep1] := 0;
                        fi;
                        if T.printLevel >= 2 then
                            Print( "#I  eliminating ", gens[rep1],
                                " = IdWord\n" );
                        fi;
###                     if IsBound( T.keepTrack ) and T.keepTrack then
###                         Print( gens[rep1], " := IdWord;\n" );
###                     fi;
                        redunds := redunds + 1;
                    fi;
                else

                    # find the current representative of the second factor.
                    rep2 := rels[i][2];
                    while invs[numgens1-rep2] <> rep2 do
                        rep2 := invs[numgens1-rep2];
                    od;

                    # handle a relator of length 2.
                    if AbsInt( rep2 ) < AbsInt( rep1 ) then
                        rep := rep1;  rep1 := rep2;  rep2 := rep;
                    fi;
                    if rep1 < 0 then  rep1 := - rep1;  rep2 := - rep2;  fi;
                    if rep1 = 0 then

                        # the relator is in fact of length at most 1.
                        if rep2 <> 0 then
                            rep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := 0;
                            invs[numgens1+rep2] := 0;
                            if tree <> 0 then
                                ptr2 := AbsInt( treeNums[rep2] );
                                pointers[ptr2] := 0;
                                treeNums[rep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[rep2],
                                    " = IdWord\n" );
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[rep2], " := IdWord;\n" );
###                         fi;
                            redunds := redunds + 1;
                        fi;

                    elif rep1 <> - rep2 then

                        if invs[numgens1+rep1] < 0 and ( rep1 = rep2 or
                            invs[numgens1-rep2] = invs[numgens1+rep2] ) then
                            # make the relator a square relator, ...
                            rels[i][1] := rep1;  rels[i][2] := rep1;
                            # ... mark it appropriately, ...
                            flags[i] := 3;
                            # ... and mark rep1 to be an involution.
                            invs[numgens1+rep1] := rep1;
                        fi;

                        # handle a non-square relator of length 2.
                        if rep1 <> rep2 then
                            absrep2 := AbsInt( rep2 );
                            invs[numgens1-rep2] := invs[numgens1+rep1];
                            invs[numgens1+rep2] := rep1;
                            if tree <> 0 then

                                ptr1 := AbsInt( treeNums[rep1] );
                                ptr2 := AbsInt( treeNums[absrep2] );
                                if ptr2 < ptr1 then
                                    ptr := ptr2;
                                    if treeNums[rep1] * treeNums[absrep2]
                                        * rep2 > 0 then
                                        ptr := - ptr;
                                        treeNums[rep1] := ptr;
                                        pointers[ptr1] := treelength + rep1;
                                    fi;
                                    ptr2 := ptr1;
                                    ptr1 := AbsInt( ptr );
                                fi;
                                if rep2 > 0 then
                                    ptr1 := - ptr1;
                                fi;
                                pointers[ptr2] := ptr1;
                                treeNums[absrep2] := 0;
                            fi;
                            if T.printLevel >= 2 then
                                Print( "#I  eliminating ", gens[absrep2],
                                    " = " );
                                if rep2 > 0 then
                                    Print( TzWord( tietze,
                                        [ invs[numgens1+rep1] ] ), "\n" );
                                else
                                    Print( gens[rep1], "\n" );
                                fi;
                            fi;
###                         if IsBound( T.keepTrack ) and T.keepTrack then
###                             Print( gens[absrep2], " := " );
###                             if rep2 > 0 then
###                                 Print( TzWord( tietze,
###                                     [ invs[numgens1+rep1] ] ), ";\n" );
###                             else
###                                 Print( gens[rep1], ";\n" );
###                             fi;
###                         fi;
                            redunds := redunds + 1;

                        fi;
                    fi;
                fi;
            fi;
        od;

        if not done then

            # for each generator determine its current representative.
            for i in [ 1 .. numgens ] do
                if invs[numgens1-i] <> i then
                    rep := invs[numgens1-i];
                    invs[numgens1-i] := invs[numgens1-rep];
                    invs[numgens1+i] := invs[numgens1+rep];
                fi;
            od;

            # perform the replacements.
            TzReplaceGens( tietze );
        fi;
    od;

    # tidy up the Tietze generators.
    tietze[TZ_NUMREDUNDS] := redunds;
    if redunds > 0 then  TzRemoveGenerators( T );  fi;

    # Print( "#I  total length = ", tietze[TZ_TOTAL], "\n" );
end;


==============================================================================


Dear Dr. Felsch,

Thank you for your very helpful message yesterday.

The significant part of the reply was:
     "Here I assume that 'P.keepTrack' is a new component ...
      ..... to be introduced by a statement like
                  P.keepTrack := true;

I was amazed and delighted to discover that new components can be added
to a record so easily.  (I must admit that, until today, I had only glanced
briefly at the chapter on records in the manual.)

So I propose to add a new component to a presentation record, initiallytion
to ask me for a copy of that correspondence.

Volkmar Felsch, Aachen



From hwblist@machnix.mathematik.uni-stuttgart.de Fri Apr 22 18:14:00 1994
From:           "Harald Boegeholz" <hwblist@machnix.mathematik.uni-stuttgart.de>
Date:           Fri, 22 Apr 94 18:14 +0200
Subject:        Re: keeping track of the transformations

>   Date:           21 Apr 94 11:05 +0200
>   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>

>   As the discussion on keeping track of Tietze transformations is too
>   technical to be continued in the GAP forum, I have sent my answer to
>   the above letter directly to Chris Wensley. 

Can any discussion about GAP be too technical to be continued in the
GAP forum? I for one don't think so (except maybe if we are talking
about machine specific implementation details); the traffic in the GAP
forum is so low that I can easily ignore any messages I don't
understand.

So why not continue this discussion in public, i.e., in the forum?


hwb
--
Harald Boegeholz |   hwb@mathematik.uni-stuttgart.de
                 |   os2a@info2.rus.uni-stuttgart.de



From Volkmar.Felsch@Math.RWTH-Aachen.DE Mon Apr 25 09:28:00 1994
From:           "Volkmar Felsch" <Volkmar.Felsch@Math.RWTH-Aachen.DE>
Date:           Mon, 25 Apr 94 09:28 +0200
Subject:        Re: keeping track of the transformations

Harald Boegeholz writes:

> 
> >   Date:           21 Apr 94 11:05 +0200
> >   From: Volkmar Felsch  <volkmar.felsch@math.rwth-aachen.de>
> 
> >   As the discussion on keeping track of Tietze transformations is too
> >   technical to be continued in the GAP forum, I have sent my answer to
> >   the above letter directly to Chris Wensley. 
> 
> Can any discussion about GAP be too technical to be continued in the
> GAP forum? I for one don't think so (except maybe if we are talking
> about machine specific implementation details); the traffic in the GAP
> forum is so low that I can easily ignore any messages I don't
> understand.
> 
> So why not continue this discussion in public, i.e., in the forum?
> 


In the past we have got several comments by GAP forum members asking
us not to overwhelm the forum by too technical discussions. That is the
reason why I hesitated to continue a public discussion on Chris Wensley's
contribution and why I sent only a short statement to the forum which
offered copies of that discussion to all who might be interested in it
only on special request.

In the meantime, I have got about half a dozen reactions to that statement
asking me for a copy of our correspondence or for a public continuation
of the discussion. I think that justifies now to provide my letter to Chris
Wensley and his reply in the forum.

Volkmar Felsch, Aachen


==============================================================================

>
> Martin Sch"onert, in his reply to Tim Hsu, writes:
>
> " ..use Tietze transformations.. If one keeps track of the transformations.."
>
> Since this is precisely what I want to do, I am asking how!
> Specifically, if a messy presentation with generators  _x1 .. _x20 (say)
> is reduced, using  TzGo , to a presentation with generating set
>   [ _x3, _x12, _x24 ] ,I want to remember expressions for the
> 21 eliminated generators as words in the three remaining ones.
>
> I have not been able to discover a solution in the manual but 3 possible
> methods suggest themselves.  Guidance as to which way to go would be much
> appreciated.
>
> 1.  Avoid using the high-level  TzGo  and use the low-level commands
> so that at each elimination the required formula can be saved.  Surely
> this would amount to rewriting  TzGo ?
>
> 2.  Edit appropriate parts of the file  "fptietze.g" .
>     This file is 40 pages long, with many interdependant functions,
> so I should probably create a host of bugs?
>     In any case, the functions use the  <Tietze record>  type, which
> appears to be defined elsewhere, possibly in the kernel?
>
> 3.  Start a  LOG  file before using  TzGo  and so produce a file
> containing messages of the form:
>         #I  eliminating _x7 = _x18^5*_x5*_x4
> As far as I can tell, GAP cannot  Read  this LOG file, but perhaps it
> would be possible to write some utility to convert the LOG file into
> a GAP file,  Exec  this utility, and  Read  the resulting GAP file?
>

Dear Dr. Wensley,

I will try to answer your above letter to the GAP forum.

The GAP Tietze transformations functions have not bee designed to keep
track of the eliminations. So, in fact, you get only the messages
which you quote in point 3 of your letter.

I must confess that I do not really understand what kind of GAP readable
output you would like to get instead, but if you just want to get the
same information in some different, GAP readable format, then, as you
said that you are prepared to do at least some small amount of editing
file 'fptietze.g', there is a reasonably simple way of inserting some
appropriate print statements for this purpose.

Essentially, what you have to do is to find the three places in file
'fptietze.g' where the above messages are printed. They are in the
functions 'TzEliminateFromTree', 'TzEliminateGen', and 'TzEliminateGen1',
and you will find them by searching for occurrences of the string
'eliminating "'. The respective statements are of the form

        if T.printLevel >= 2 then
            Print( "#I  eliminating ", gens[num], " = " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, "\n" );
            else  Print( TzWord( tietze, word ), "\n" );  fi;
        fi;

and in each case you should duplicate them by adding something like

        if IsBound( P.keepTrack ) and P.keepTrack then
            Print( gens[num], " := " );
            if gen > 0 then  Print( TzWord( tietze, word )^-1, ";\n" );
            else  Print( TzWord( tietze, word ), ";\n" );  fi;
        fi;

(or whatever you want to print). Here I assume that 'P.keepTrack' is a
new component of your current presentation record 'P', say, which has
to be introduced by a statement like

        P.keepTrack := true;

before calling the 'GoTo' command. (An alternative to such an individual
variable for each presentation record would be some global variable
'keepTrack' which you initialize at the beginning of your session.)

Note, however, that the messages printed by the three functions mentioned
above do not cover all eliminations which may be performed during a Tietze
transformations run. In general, further eliminations will be performed
by the function 'TzHandleLength1Or2Relators'. Because of your request,
I now have extended this function by some additional print statements.
(The extended version will go into the next release of GAP.)

I am sending you a copy of the new version in this letter. Again, you
will have to duplicate the print statements appropriately. To make things
easier for you, I have already added a sample of such duplications (in the
form of comments). As above, you should change these additional statements
according to your needs.

Please feel free to contact me again if you have further questions.

Volkmar Felsch, Aachen

-----------------------------------------------------------------------------

#############################################################################
##