%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  examples.tex           GAP documentation            Joachim Neub"user
%%
%H  $Id: examples.tex,v 1.13 2001/03/23 14:58:17 gap Exp $
%%
%Y  Copyright (C) 1999, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Examples}

Here we give a number of examples to illustrate various features of
{\ITC}. Please note that input files for all these are contained with
the distribution of {\ITC}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{A Presentation by A. Cavicchioli}

The presentation used in this section as a first example of the use of
{\ITC} stems from a paper by A. Cavicchioli (see~\cite{Cav86}). We
use it here because it has also been used to explain CE in an easy
introduction to computational methods for finitely presented groups by
the third author and Said Sidki, of which an English translation is
available on the {\GAP} Web Pages,
see~\URL{http://www-history.mcs.st-and.ac.uk/~gap/Info/talks.html}.

The {\GAP} input to this group will be

\begintt
F := FreeGroup( "a", "b" );
a := F.1; b := F.2;
rels := [ a^-2*b*a*b^-1*a*b, a^3*b^-1*a^-2*b^-1 ];
G := F / rels;
a := G.1; b := G.2;
H := Subgroup( G, [ a ] );
InteractiveTC( G, H );
\endtt

This can be replaced by reading the input file for this presentation:

\begintt
ItcExample( "cav" );
\endtt

Note that, since the generators of the free group were called $a$ and
$b$, these names will be used by {\ITC}.

The {\ITC} Coset Table shown in the Coset Table Window has already
entries for $1*a$ and $1*a^{-1}$ which stem from the fact that the
subgroup is automatically given coset number $1$ at the beginning and
consequences of this definition, here via the fact that the subgroup
is generated by $a$, are inserted into the Coset Table. You can
inspect the Subgroup Table (in this case only one) by clicking the
only subgroup generator in the List of Subgroup Generators which you
can get by clicking `show subgrp'.

We first try the simplest solution: we click the top button
`Close', and select `close table by Felsch' from its menu. This does
indeed work, filling the table with 12 rows. We can read from the
Information Line that no coincidences were encountered in this CE (the
number `Deleted' is given as 0).

We want to try different strategies next. Rather than starting from
scratch, we clear the table of all entries created by the last CE by
just clicking the (red) bottom button `clear'.

Without explicitly mentioning this each time we will do the same, or
use `reset' (depending whether we also want to keep settings or not)
whenever we want to reuse the definition of the group.

Also the three ``gaps of length 1'' strategies offered in the menu of
the top button `Close' will close the table without encountering
coincidences. We remember, however, that these really invoke Felsch
steps if no gaps of length 1 are available and we want in a moment
to investigate if this was the case here.

The ``HLT'' strategy, however, (even though it uses consequences) needs
13 definitions, i.~e. produces one coincidence.

That is, we have in this case ended with a slightly non-optimal
definition sequence (which we can inspect either in a separate window
or by marking the definitions green in the Coset Table by clicking
the (white) `show defs' bottom button with the left or the right mouse
button, respectively). We try next, if the Short-cut method will be
able to improve this definition sequence. Pressing the (green)
`short-cut' bottom button and not restricting the number of loops in
the query window does in fact produce in five loops a definition
sequence in which no coset has to be removed.

Prescribing in a repetition of the previous experiment in the
Short-cut query window only one loop shows us that already this one
loop suffices to produce a definition sequence closing the tables
without coincidences.

We next want to follow some of these computations stepwise.

First we try the Felsch method stepwise. Clicking the (green) bottom
button `Felsch' opens a query window, in which we can enter how many
Felsch steps we want to perform. The value 1 is offered, and we
should in fact use this to watch how by repeated call of one Felsch
step at a time the tables close. It will be informative, not only to
watch what happens in the Coset Table, but also to watch what happens
in the Relation Tables. For this purpose we first click the (white)
bottom button `show rels' which opens a window showing the two
relators. Clicking these opens two more windows displaying the
Relation Tables. After each step the new entries will be shown in
red. While after each of the definitions of coset number $2$ and $3$
just two new entries in the coset table are made, e.~g. in the first
case corresponding to the definition $2 = 1*b$ and the trivial
consequence $2*b^{-1} = 1$, after definition of coset number 4 we
observe that for the first time rows in the relation tables close and
yield further consequences and hence entries into the coset
table. Again after having defined coset number $12$ the tables will be
closed without a coincidence having occurred (and this is indicated in
the Information Line).

We may repeat a Felsch strategy but with larger steps, that we enter
into the field of the query window that opens after clicking the green
bottom button `Felsch'.

We now want to return to the question what really happens when we use
a ``gaps of length 1'' strategy offered for closing a table:

If at the start we click `show gaps', we get the message `There are no
gaps of length 1' and if we like, we can (partially, compare "show
gaps"!) confirm this by looking at the Subgroup Table via the bottom
button `show subgrp' (which turns out to be closed already) and the
two Relation Tables via the bottom button `show rels' which in fact
each have only one row yet with gaps of length 4 and 3,
respectively.

After performing a first Felsch step (using the bottom button
`Felsch') the situation has not improved, there are still no gaps of
length 1, however after a further Felsch step a first gap of length
1 turns up. After filling this, no new gap of length 1 turns up,
so we again resort to a Felsch step, after which we can again fill a
gap of length 1. One more Felsch step then allows us to use gap
of length 1 filling four times after which a last Felsch step is
needed to close the table.

We will now try what happens if we follow a Haselgrove-Leech-Trotter
kind of strategy. We can do this in two ways:

We can use the bottom button `HLT' to make a number of definitions
(that we can prescribe) following the HLT strategy. If we do this,
and make one definition at a time, we observe that with defining coset
number $5$ we have produced a coincidence and coset number $4$ will
get eliminated.

We can also close rows one by one. For this we press the (green)
bottom button `fill rows'. In a query window we are asked which row we
want to fill (in all -- in this case, two -- Relation Tables). We choose
the proposed default value, in the first instance, so closing the first
rows. This already defines five coset numbers. However, if we watch
the Information Line carefully, it tells us that in fact one of these
five defined coset numbers has already been eliminated again by a
coincidence. The Coset Table shows that this has been coset $4$ (and
no wonder, we have followed the same definition sequence as in our last
experiment).

If we apply a few more steps of a strategy which consists of just
clicking the button `fill rows' and then accepting the row number
proposed by the {\ITC}, the next proposal will be to close row $2$ in
each table. Doing this brings us already to coset number $10$. Then,
as expected, we are offered to fill the third rows. This step does not
only lead to another definition, namely of coset number $11$, but also
implies that all rows up to the seventh are already closed (you may
easily check this by looking at the Relation Tables). Hence, in the
next step the proposal is to fill the eighth rows and doing this
closes the tables. In these tables no coset number $4$ occurs, the
coset numbers run from $1$ to $13$ with that omission.

We may next want to see a bit closer what happens with that
coincidence, and we can do so by pulling down the `Settings' menu from
the top button `Settings' and releasing the mouse button on the menu
entry `coincidence handling off'. If now we repeat the same procedure
as last time, namely calling `fill rows', the process will come to a
halt, while the coset number $4$ is still ``alive''. {\ITC} warns us in
the Information Line that coincidences are pending and offers to open
a window showing the coincidence(s) pending, in this case $4 = 3$. We
can eliminate coset number $4$ by clicking this equation in the
window, after which the warning vanishes and we have the state that in
the previous run we had after the first `fill rows' command. We can
get to the end in the same way again.


We could vary the HLT procedure by not always filling a particular row
in both Relation Tables simultaneously, but in only one of these
tables. This we can achieve by clicking the first or last entry in
the chosen row of that Relation Table. In fact, if we just proceed by
closing rows of the first Relation Table we will again get closure
after one coincidence has occurred, which however can again be
elimintated by the Short-cut method, while proceeding by only closing
rows in the second Relation Table, we even arrive at the result
without coincidences.

We have seen at the beginning that a Felsch strategy brought us to the
end without having encountered coincidences. Next we show how delicate
all these statements are. We pretend that the columns of the Coset
Table have been reordered so that first both generators and then their
inverses head the columns of the Coset Table. Since we cannot change
the program to follow a Felsch strategy with this arrangement of
columns, we do it by hand clicking consecutively the following points
after having switched coincidence handling off:

$$
  1*b,
  1*b^{-1},
  2*a,
  2*b,
  2*a^{-1},
  3*a,
  3*b^{-1},
  5*a,
  5*b,
  5*a^{-1}.
$$

After this one we get a coincidence $9 = 8$; we remove $9$ by clicking
this equation in the window displaying it, but this produces
immediately a further coincidence $10 = 8$, only after also removing
$10$ we can continue

$$
  7*b^{-1},
  11*b,
  11*a^{-1}
$$

which leads to closure of the tables. Thus we have encountered even
two coincidences and at a different place. `short-cut' will again
yield a definition sequence without coincidences in only one loop.

Next let us just observe that we can in fact produce even more
coincidences by using a ``stupid'' definition sequence. We may e.~g.
first define consecutively 10 images under $b$ and then 10 further
ones under $a$, without any indication of the table closing. If we
next perform 3 Felsch steps, we get a first coincidence. Eliminating
this will produce a further one and so on, and if we continue (always
clicking the first one of the displayed coincidences) we will see
that at certain points half a dozen coincidences are pending
simultaneously. Working these off, we will eventually arrive at a
table with no further coincidences pending, but which will still not
have closed. After two more Felsch steps we reach closure again, but
the definition sequence will list 26 coset numbers. Short-cut will
again reduce this to a definition sequence of 12 coset numbers but
if we follow what happens loop by loop, we see that only the fifth
loop brings a reduction to 20 coset numbers, while only the eighth
(and last) loop brings the reduction to a definition sequence without
coincidences.

Finally we give an example in which `short-cut' will not completely
succeed. We first define ``by hand'' four images under $b^{-1}$:

$$
  1*b^{-1},
  2*b^{-1},
  3*b^{-1},
  4*b^{-1},
$$

and then close the table using the Felsch strategy. The table will
close after having gone through two coincidences. If we now invoke the
Short-cut method, it will reduce the definition sequence from 14 to
13 definitions, but not to 12. However in this case `sort defs'
will bring us down to a definition sequence of 12 definitions either
applied to the definition sequence of 14 definitions obtained
originally or to the ``pruned'' definition sequence of 13 definitions.

In this first example we have already seen some of the multitude of
ways in which we can modify the basic idea of CE. In order to
demonstrate more of the functionality of {\ITC}, we will study further
examples.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The Fibonacci Group F(2,7)}

The Fibonacci Group F(2,7) is cyclic of order 29, but this result is
not easily obtained. The first and crucial step is to establish that
the group is in fact cyclic by showing with the help of coset
enumeration that one of the cyclic subgroups generated by one of the
generators has index 1 in F(2,7). In her beautifully written
Master's thesis \cite{Ede89} Margaret Edeson describes the history of
that proof and uses it to discuss in detail approaches to the problem
of finding a short definition sequence that will lead to the result
that this index is trivial.

In fact she documents carefully correspondence around that problem,
involving in particular John Leech and George Havas. By 1984 John
Leech actually had obtained a definition sequence of 55 definitions by
a posteriori pruning (by hand) much longer definition sequences
determined a priori. Again by elaborate hand work in 1989 Margaret
Edeson was able to get this number down to 53. To read her comments
about at various stages feeling unsafe whether to continue
enumerations because of the fear of already having made a mistake is
not only amusing but an encouragement for developing programs such as
{\ITC}.

The {\GAP} input for the enumeration of the cosets of the cyclic
subgroup generated by the third generator reads:

\begintt
F := FreeGroup( "a", "b", "c", "d", "e", "f", "g" );
a := F.1; b := F.2; c := F.3; d := F.4; e := F.5; f := F.6; g := F.7;
rels := [
  a*b*c^-1,
  b*c*d^-1,
  c*d*e^-1,
  d*e*f^-1,
  e*f*g^-1,
  f*g*a^-1,
  g*a*b^-1
];
G := F / rels;
c := G.3;
H := Subgroup( G, [ c ] );
InteractiveTC( G, H );
\endtt

This can be replaced by reading the input file for this presentation:

\begintt
ItcExample( "f27" );
\endtt

Note that again {\ITC} will print the generators of the free group
using their names $a$, $b$, etc.

The Coset Table shown by {\ITC} has already the entries for $1*c$ and
$1*c^{-1}$. Moreover we note that it already indicates gaps of length
1 by (red - meaning new) dots in the Coset Table which stem from the
fact that the relations are very short.

We first click the top button `Close' and choose the menu entry `close
table by Felsch'. Rather quickly we get closure with index 1 after
332 definitions. `Deleted: 331' confirms that in fact 331
coincidences have been removed. It will be instructive to follow this
coincidence handling step by step for a few steps.

We can do this by returning to the beginning using the bottom button
`clear' and then selecting the menu entry `coincidence handling off'
in the menu of the top button `Settings'. Starting now `close table
by Felsch' again, the enumeration will stop with 332 coset numbers
defined and the warning `Pending coincidences' in the Information
Line. At the same time a window for the Table of Pending Coincidences
is offered and this informs us that at present just one coincidence,
namely $226 = 106$ has been found.

We can use the scroll buttons to inspect the row $226$ that will be
removed by handling this coincidence. We click the bottom button
`scroll to' and write $226$ instead of the number of the last row
($332$) into the field offered, then clicking `ok' scrolls the
Coset Table Window such that row $226$ occurs in the middle of the
window. We see that row $226$ is coloured red (while row $106$
remains black).

We can now click, in the List of Pending Coincidences, on that
coincidence $226 = 106$ and this will be eliminated. Looking again for
row $226$ in the Coset table (or any of the Relation Tables) we will
not find it any more, it has got suppressed, but no renumbering has
taken place, row $227$ now follows immediately after row $225$.

However the warning `Pending coincidences' has not vanished and indeed
the window with the List of Pending Coincidences now shows us two new
coincidences: $124 = 43$ and $229 = 21$ that have now been
detected. We can repeat the same game and see that for some time the
List of Pending Coincidences grows longer and longer until (if we have
the patience to follow that game to its end instead of just switching
on the automatic coincidence handling again) indeed all coincidences
are worked off and index 1 is obtained. That is, we see in this
case how one single coincidence triggers the ``collapse'' of the Coset
Table.

Invoking now the Short-cut method for the definition sequence of
length 332 not prescribing the number of loops, after 33 loops it
stops with a definition sequence of 54 definitions (already one better
than Leech's result by hand). The Short-cut method is slow enough to
be able to see in the Information Line how the number of definitions
is brought down in several of the loops of the Short-cut method. It
will be instructive to do the 33 loops one by one, to see that not all
of them really improve the definition sequence. In fact at first there
are some dramatic improvements of the original number of 332
definitions as shown by the number of definitions obtained in the
first six loops: 327, 251, 226, 145, 132, 127. But then
the next loop brings no improvement, and later on there are six
consecutive loops during which the number of definitions stays at 64
definitions. By the way, if you do this interactively step by step,
watch the counter for the number of loops, if this does not rise any
more, the method will have come to its natural end. Also the displayed
text changes: While it says $i$ `Short-cut loops' as long as the
Short-cut method works, it changes to `Short-cut' ($i$ `loops') after
the Short-cut method has stopped.

We next choose the `use gaps strategy 2 (first rep of max weight)'
entry in the menu of the top button `Close'. We are rewarded by
obtaining a priori (!) a definition sequence of only 126 definitions
leading to collapse of the table (which is better than anything Leech
had at his disposal). But if we expected that now also `short-cut'
would beat records, we are disappointed, it stops after 35 loops but
still with a definition sequence of length 57.

So finally we choose the `use gaps strategy 3 (last rep of max
weight)'. This closes after only 79 cosets defined, `short-cut' gets
down to 54 in only 29 loops. However if we first perform three
Felsch steps (using the bottom Button `Felsch' and prescribing 3 in
the field provided in the query window) and then close again by `use
gaps strategy 3' we get once more closure after 79 definitions, but
this time `short-cut' brings us down to a definition sequence of
length 50 (breaking all presently known records).

Of course this has not been our main goal, but rather to demonstrate
the flexibility of using {\ITC}. In fact for somebody interested in CE
it will be very fascinating to study this example further: if you use
$n$ Felsch steps and then close by `use gaps strategy 3' and follow
this by the Short-cut method, the series of results will be most
puzzling. We do not want to betray it completely here - just try it out -
but we mention that for $n =$ 20 we obtained an enumeration that we
did not even finish because it went on and on (we did follow it until
it had defined more than 10000 coset numbers), while for $n =$ 40
we were at that very good situation of definition sequence length 79 a
priori and 50 a posteriori again.

Just for comparison: `close table by HLT with consequences' needs
2276 definitions.

Finally we mention that there are simple {\ITC} strategies to find
definition sequences of length 50 also if we replace the subgroup
$H = \langle c \rangle$ by any of the other cyclic subgroups generated
by the generators of $G$. In each of these cases it suffices to start
with one or two suitable {\ITC} commands and then again to close the
tables via `use gaps strategy 3' and to apply `short-cut'. An
appropriate start may e.~g. consist of doing 10, 1, 13, or 10
Felsch steps in case $H = \langle a \rangle$, $H = \langle d \rangle$,
$H = \langle f \rangle$, or $H = \langle g \rangle$, respectively, or
of clicking $1*f$ or $1*a$ and $1*b$ in the Coset Table for
$H = \langle b \rangle$ or $H = \langle e \rangle$, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{A Presentation by B.H. Neumann}

Bernhard Neumann (see e.~g. \cite{Neu79}) has discussed a famous
sequence of presentations of the trivial group of increasing
difficulty for any CE method. In fact for a long time the only one
that could be done was the first of them that we consider here,
(called $e1$ here), the next one was only recently ``cracked'' by George
Havas' and Colin Ramsey's program ACE.

The {\GAP} input for the presentation is


\begintt
F := FreeGroup( "a", "b", "c" );
a := F.1; b := F.2; c := F.3;
rels := [ c^-1*a*c*a^-2, a^-1*b*a*b^-2, b^-1*c*b*c^-2 ];
G := F / rels;
H := TrivialSubgroup( G );
InteractiveTC( G, H );
\endtt

This can be replaced by the input file for this presentation:

\begintt
ItcExample( "e1" );
\endtt

We just mention a few results, but mainly suggest this presentation
for further exercises:

`close table by Felsch' needs 588 definitions, `short-cut' reduces
to 68 in 31 loops.

`use gaps strategy 1' needs 119 definitions, `short-cut' reduces to
68 again this time in 33 loops.

`use gaps strategy 2' needs 116 definitions, `short-cut' reduces to
68 again in 33 loops.

`use gaps strategy 3' needs 119 definitions, but `short-cut' reduces
to 64 in 27 loops, which coincides with what Havas and Ramsey got
by hand pruning a somewhat better a priori enumeration with only 81
definitions obtained by experimenting with ACE (see \cite{HR99b}).

However using 13 Felsch steps followed by closing by `use gaps
strategy 1' yields a definition sequence of length 134 that is
reduced to only 61 by the Short-cut method in 30 loops. The same
procedure with 196 Felsch steps and closing by `use gaps strategy 3'
gets even down to a sequence of 60 definitions.

By the way this presentation also provides an example of a rather
strong reduction of the definition sequence by `sort defs': Using
`close table by HLT with consequences' produces a definition sequence
of 672 coset numbers that reduces to 279 under `sort defs'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The Group (8,7;2,3)}

As a final example we take the presentation and subgroup described by
the {\GAP} input:

\begintt
F := FreeGroup( "a", "b" );
a := F.1; b := F.2;
rels := [ a^8, b^7, (a*b)^2, (a^-1*b)^3 ];
G := F / rels;
a := G.1; b := G.2;
H := Subgroup( G, [ a^2, a^-1*b ] );
InteractiveTC( G, H );
\endtt

This can again be replaced by reading it from a file:

\begintt
ItcExample( "g8723" );
\endtt

This presentation has also been used frequently for comparisons of CE
strategies, e.~g. in \cite{CDHW73}.

If we start with all parameters at default values and choose `close
table by Felsch' the coset enumeration will be interrupted after the
definition of 1000 coset numbers and a window springs up in which it
is offered to `extend table size from 1000 to' and then in a field the
number 2000 is proposed (that can be changed). After clicking `ok'
the requested extension of the table size is done and the enumeration
resumed. If one clicks `cancel' instead, thus rejecting the offer, one
gets the warning `Insufficient table size' in red below the Coset
Table, and then has to decide if one wants to extend the table size
(now using the menu entry of the top button `Settings') or to give up
this enumeration.

The enumeration stops having defined 1306 coset numbers, but the
index has turned out to be 448. `short-cut' reduces this rather
redundant sequence of coset numbers to 472 in 140 loops (but this
already takes a little while).

Choosing `use gaps strategy 1' from the menu of `Close' needs 825
definitions which boil down to 470 under `short-cut' in 141 loops.

For comparison we mention that the shortest definition sequence found
by George Havas and Colin Ramsay experimenting with *a priori*
methods using ACE has length 662 (see \cite{HR99a}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E