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.
The presentation used in this section as a first example of the use of ITC stems from a paper by A. Cavicchioli (see 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 http://www-history.mcs.st-and.ac.uk/~gap/Info/talks.html.
The GAP input to this group will be
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 );
This can be replaced by reading the input file for this presentation:
ItcExample( "cav" );
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:
|
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
|
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:
|
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.
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 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:
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 );
This can be replaced by reading the input file for this presentation:
ItcExample( "f27" );
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 = 〈c 〉 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 = 〈a 〉, H = 〈d 〉,
H = 〈f 〉, or H = 〈g 〉, respectively, or
of clicking 1*f or 1*a and 1*b in the Coset Table for
H = 〈b 〉 or H = 〈e 〉, respectively.
Bernhard Neumann (see e. g. 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
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 );
This can be replaced by the input file for this presentation:
ItcExample( "e1" );
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 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.
As a final example we take the presentation and subgroup described by the GAP input:
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 );
This can again be replaced by reading it from a file:
ItcExample( "g8723" );
This presentation has also been used frequently for comparisons of CE strategies, e. g. in 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 HR99a).
ITC manual