%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %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