<html><head><title>[ITC] 4 The Tables</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>4 The Tables</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP004.htm#SECT001">The Coset Table</a> <li> <A HREF="CHAP004.htm#SECT002">Warnings</a> <li> <A HREF="CHAP004.htm#SECT003">The Information Line</a> <li> <A HREF="CHAP004.htm#SECT004">The List of Relators</a> <li> <A HREF="CHAP004.htm#SECT005">The Relation Tables</a> <li> <A HREF="CHAP004.htm#SECT006">The List of Subgroup Generators</a> <li> <A HREF="CHAP004.htm#SECT007">The Subgroup Tables</a> <li> <A HREF="CHAP004.htm#SECT008">The Table of Definitions</a> <li> <A HREF="CHAP004.htm#SECT009">The List of Length 1 Gaps</a> <li> <A HREF="CHAP004.htm#SECT010">The List of Pending Coincidences</a> </ol><p> <p> Usually table entries in all tables are black. Red indicates that these entries were the result of the last step that has been performed by ITC. Coset numbers can also be coloured green using the <code>mark cosets</code> bottom button (see <a href="CHAP005.htm#SSEC002.15">mark cosets</a>) or the <code>show defs</code> bottom button (see <a href="CHAP005.htm#SSEC002.12">show defs</a>). In case of conflict green has preference to red. <p> As a general rule we state that clicking some place in one of the <strong>tables</strong> with the <strong>left</strong> mouse button will result in an action in the process of CE, e. g. in making a definition. <p> There are only very few cases where clicking with the <strong>right</strong> mouse button in a table will have an effect: <p> <dl compact> <p> <dt>--<dd> with clicking a coset number or a dot in the Coset Table (see Section <a href="CHAP004.htm#SECT001">The Coset Table</a>), <p> <dt>--<dd> with clicking on an entry of the Table of Definitions (see Section <a href="CHAP004.htm#SECT008">The Table of Definitions</a>), <p> <dt>--<dd> with clicking on an entry of the List of Length 1 Gaps (see Section <a href="CHAP004.htm#SECT009">The List of Length 1 Gaps</a> and <a href="CHAP005.htm#SSEC002.13">show gaps</a>), and <p> <dt>--<dd> with clicking on an entry of the List of Pending Coincidences (see Section <a href="CHAP004.htm#SECT010">The List of Pending Coincidences</a>). <p> </dl> <p> In each of these cases clicking with the right mouse button will result in ITC displaying further information in a new display window. <p> <p> <h2><a name="SECT001">4.1 The Coset Table</a></h2> <p><p> The main table in any coset enumeration is the coset table. Its rows are numbered by natural numbers, the ``coset numbers'', which are defined in the process of the coset enumeration. Remember that coset numbers denote cosets defined by representatives given by words in the generators, but until a coset enumeration is finished, different coset numbers may represent the same coset (by different words). <p> Note that ITC displays on the screen only rows for ``still alive'' coset numbers, that is coset numbers that have not been eliminated by coincidences. <p> So the first column of the ITC Coset Table displays the list of presently ``still alive'' coset numbers. The further columns of the ITC Coset Table are indexed by the generators of the finitely presented group <var>g</var> and their inverses. <p> Entries in an ITC Coset Table can either be empty, or a coset number, or a dot. An entry <i>j</i> in row <i>i</i> and column <i>k</i> means that the coset with number <i>i</i> multiplied by the generator or inverse generator heading column <i>k</i> yields the coset with number <i>j</i>. An empty entry indicates that nothing is yet known about the respective product. A dot as entry indicates that making a definition in this place will close at least one row in a subgroup or a relation table, i.e. it belongs to a ``gap of length 1'' (see Section <a href="CHAP003.htm#SECT002">Some Definition Strategies</a>). <p> Let <var>h</var> be the subgroup of the group <var>g</var> whose cosets are to be enumerated. At the beginning of an enumeration ITC fills automatically those entries of the Coset Table (as well as of Subgroup and Relation Tables) that are consequences of coset number 1 always being given to the subgroup <var>h</var>. <p> Clicking with the <strong>left</strong> mouse button an empty place or a place with a dot in the Coset Table will make a definition in this place. That is: Let <i>c</i> be the last coset number defined, then a click in the place in row <i>i</i> and column headed by generator or inverse generator <i>x</i> will define a coset number <i>c</i>+1 that represents the product of the coset with number <i>i</i> by <i>x</i>. See Section <a href="CHAP003.htm#SECT001">Making a Definition</a> for details of the changes (marked in red) in the tables caused by making such a definition. <p> At the same time new dots may occur in the coset table, representing places newly found to allow filling gaps of length 1 in one of the Relation Tables or Subgroup Tables. These new dots will also be coloured red. <p> Clicking with the <strong>right</strong> mouse button a dot will open a window which will show a list of all those definitions that are equivalent to the one belonging to this place in the sense that they will close the same length 1 gaps in Relation and Subgroup Tables. (Compare also <a href="CHAP003.htm#SECT002">Some Definition Strategies</a> and <a href="CHAP005.htm#SSEC002.13">show gaps</a>). <p> Clicking with the <strong>left</strong> mouse button the coset number at the beginning of a row of the Coset Table will result in closing this row by new definitions. (This way you can e. g. easily fulfill the Mendelsohn Condition for this row requesting that images of that coset under multiplication by all generators and their inverses must eventually get defined). <p> Clicking with the <strong>right</strong> mouse button the coset number at the beginning of a row of the Coset Table or any already defined coset number in the Coset Table will open a window in which a coset representative of the respective coset will be displayed as a word in the generators of <i>g</i> and their inverses. Clicking the same coset number once more (in the same or in another position of the Coset Table) will close the coset representative window again. (In Section <a href="CHAP004.htm#SECT008">The Table of Definitions</a> we will see that the same coset representative window can be switched on or off also by clicking the respective row in the Table of Definitions.) <p> Note that only up to 30 rows of the Coset Table are displayed simultaneously on the screen but that the Coset Table can be scrolled using the bottom buttons <code>scroll to</code> (see <a href="CHAP005.htm#SSEC002.1">scroll to</a>) and <code>scroll by</code> (see <a href="CHAP005.htm#SSEC002.2">scroll by</a>). <p> <p> <h2><a name="SECT002">4.2 Warnings</a></h2> <p><p> Directly below the Coset Table a row is left open in which warnings will flash up in red if the user is trying to start an action that is impossible or does not make sense in the present situation, so that e. g. certain buttons are disabled. These are: <p> <p> <dl compact> <p> <dt><code>There are no subgroup generators</code> <dd> if the user clicks the bottom button <code>show subgrp</code>, but there are no subgroup generators specified, i. e. one is performing a CE of the cosets of the trivial group. <p> <dt><code>There are no gaps of length 1</code> <dd> if the user tries to show or to fill gaps of length 1 using the bottom buttons <code>show gaps</code> or <code>fill gaps</code>, respectively, but no such gaps of length 1 exist in any of the Subgroup or Relation Tables. <p> <dt><code>There are no more gaps of length 1</code> <dd> if the user had requested to perform a prescribed number of steps filling gaps of length 1, but the supply of such gaps ran out before this number of steps had been performed. <p> <dt><code>There are no pending coincidences</code> <dd> if the user tries to see the list of coincidences while no such are known. <p> <dt><code>There are pending coincidences</code> <dd> if the user tries to make any definition while coincidences are still pending, which may be the case only if the automatic coincidence handling is switched off. (Note that the user is informed anyhow of the fact that coincidences are pending in the ``Information Line''). <p> <dt><code>The tables are closed</code> <dd> if the user tries to make any definition after the tables are closed already. <p> <dt><code>The tables are not closed</code> <dd> if the user tries to invoke the Short-cut method before the tables are closed. <p> <dt><code>Insufficient table size</code> <dd> if the coset enumeration comes to a halt without closing the tables because the size for the Coset Table was too small. In this case this size has to be extended using the menu entry <code>extend table size</code> in the menu popped up via the top button <code>Settings</code> (see <a href="CHAP005.htm#SSEC001.4">extend table size</a>). <p> <dt><code>Illegal argument</code> <dd> if an illegal answer has been typed into a query window, e. g. if the number of steps requested in the query window opened by clicking the bottom button <code>Felsch</code> is given as a negative integer. <p> <dt><code>Illegal coset number</code> <dd> <p> <dt><code>This command has no effect</code> <dd> <p> </dl> <p> The warning message will vanish as soon as the user performs the next allowed action. <p> <p> <h2><a name="SECT003">4.3 The Information Line</a></h2> <p><p> Underneath the Coset Table you see a line which will all the time display three numbers that characterize the present state of the coset enumeration: <p> <p> <dl compact> <p> <dt><code>Defined:</code> <i>i</i> <dd> means that so far <i>i</i> coset numbers have been defined altogether (some of which may already have been eliminated again by the coincidence routine). <p> <dt><code>Deleted:</code> <i>j</i> <dd> means that so far <i>j</i> of these coset numbers have been eliminated again through the handling of coincidences (see also Section <a href="CHAP003.htm#SECT003">Handling a Coincidence</a> and <a href="CHAP005.htm#SSEC002.14">show coincs</a>). <p> <dt><code>Alive:</code> <i>k</i> <dd> means that <i>k</i> coset numbers have survived the elimination process of the coincidence handling (if coincidences did occur at all). So obviously <i>k</i> = <i>i</i> <font face="symbol">-</font> <i>j</i>. Note that during a run of ITC there is no change (renumbering) of coset numbers after a coincidence has been handled, i. e. the sequence of coset numbers will always be an ordered sequence of natural numbers starting with 1, but if coincidences have been handled, it will have ``holes'', i. e. no longer be consecutive. While in fact in the internal data structure for the coset table these ``dead'' cosets still exist, in the Coset Table (and Relation Tables) occurring on the screen these lines will be suppressed, so that at any given moment the actual number of lines in the Coset Table and the Relation Tables that can be seen on the screen will be <i>k</i>, (not <i>i</i>). This has some impact on the scrolling of the Coset Table (compare <a href="CHAP005.htm#SSEC002.1">scroll to</a> and <a href="CHAP005.htm#SSEC002.2">scroll by</a>). <p> </dl> <p> Behind these three numbers the Information Line will at certain instances also display warnings: <p> <dl compact> <p> <dt>--<dd>When the CE has come to an end, that is, when all tables have been closed with no coincidences pending, the text <code>Tables Closed</code> is shown in red. <p> <dt>--<dd>If the handling of coincidences has been switched off using <code>coincidence handling off</code> (see <a href="CHAP005.htm#SSEC001.5">coincidence handling off</a>) in the menu of the top button <code>Settings</code> the text <code>Coincidence Handling OFF</code> is shown in red until a coincidence is really encountered (if any occur at all). Then the process will come to a halt and the text shown will change for the warning <code>Pending Coincidences</code>, again shown in red. Note that this in particular means that the tables will not have closed and the CE has not been finished yet. If the CE process is resumed after the pending coincidences have been worked off, also the text <code>Coincidence Handling OFF</code> will reappear as long as coincidence handling remains switched off and not all tables have closed. <p> <dt>--<dd>If the definition sequence has been changed using the Short-cut method (see <a href="CHAP005.htm#SSEC002.9">short-cut</a> as well as Section <a href="CHAP003.htm#SECT005">The Short-Cut Method</a>) this will be indicated by the text <code>Short-Cut</code> shown in red, followed by the number of ``loops'' that the Short-cut method has performed (see Section <a href="CHAP003.htm#SECT005">The Short-cut method</a>). Analogously <code>Tables sorted</code> is shown after <code>sort defs</code> (see <a href="CHAP005.htm#SSEC002.8">sort defs</a>) has been applied. <p> </dl> <p> <p> <h2><a name="SECT004">4.4 The List of Relators</a></h2> <p><p> The List of Relators is shown in a display window that pops up after clicking the (white) bottom button <code>show rels</code> (see <a href="CHAP005.htm#SSEC002.10">show rels</a>). <p> Clicking one of the relators opens a window for the respective Relation Table (see <a href="CHAP004.htm#SECT005">The Relation Tables</a>). <p> <p> <h2><a name="SECT005">4.5 The Relation Tables</a></h2> <p><p> For a relator that is the product of <i>n</i> generators or inverse generators the Relation Table is a table with <i>n</i>+1 columns. The vertical lines between the columns of the table are headed by the factors of the relator. Each row has in its first and last place the same coset number. Further entries can either be empty or be occupied by a coset number. <p> Assume that at a certain time coset numbers 1 to <i>c</i> have already been defined and consider an empty entry in a Relation Table that is either the first empty one or the last empty one in its row. Then clicking such an empty space defines coset number <i>c</i>+1 in this place. <p> To be more explicit: <p> Let <i>i</i> be the coset number standing before an empty place and <i>x</i> be the generator or inverse generator heading the vertical line in front of the empty place then by clicking this empty place <i>c</i>+1 is defined to be the coset number for the coset that is obtained as the product of the coset with coset number <i>i</i> by <i>x</i>. <p> Analogously let <i>i</i> be the coset number standing behind an empty place and <i>x</i> be the generator or inverse generator heading the vertical line behind the empty place then by clicking this empty place <i>c</i>+1 is defined as the coset number of the coset obtained as the product of the coset with coset number <i>i</i> by <i>x</i><sup><font face="symbol">-</font>1</sup>. <p> See Section <a href="CHAP003.htm#SECT001">Making a Definition</a> for more details on the resulting changes of the tables. <p> Clicking the <strong>first</strong> or the <strong>last</strong> entry of a row (that are always filled by the same coset number as soon as this row exists) will result in <strong>filling this whole row</strong> in an analogous manner starting from the left. The last coset number defined in this process (i.e. the rightmost one) and the consequences of its definition get marked in red. <p> For the possibility to fill <strong>all</strong> <i>i</i>th rows in all Relation Tables you can use the green bottom button <code>fill rows</code> (see <a href="CHAP005.htm#SSEC002.5">fill rows</a>). <p> Clicking on some other place already filled by a coset number will have no effect. Also clicking on an empty place that is neither the first nor the last empty one in its row will have no effect. <p> Unlike most of the other display windows, but in line with the Coset Table Window, the windows of the Relation Tables do not vanish when the contents of the Relation Tables changes but the tables change in their windows. Note that (as with the Coset Table) only up to 30 rows of the Relation Tables are displayed simultaneously on the screen but that the Relation Tables can be scrolled parallel to the Coset Table using the bottom buttons <code>scroll to</code> (see <a href="CHAP005.htm#SSEC002.1">scroll to</a>) and <code>scroll by</code> (see <a href="CHAP005.htm#SSEC002.2">scroll by</a>). <p> <p> <h2><a name="SECT006">4.6 The List of Subgroup Generators</a></h2> <p><p> The list of generators of the subgroup <var>h</var> is shown in a window that springs up after clicking the (white) bottom button <code>show subgrp</code> (see <a href="CHAP005.htm#SSEC002.11">show subgrp</a>). <p> Clicking one of the subgroup generators opens a window for the respective Subgroup Table (see <a href="CHAP004.htm#SECT007">The Subgroup Tables</a>). <p> <p> <h2><a name="SECT007">4.7 The Subgroup Tables</a></h2> <p><p> Except that they have only one row that begins and ends with the coset number 1, Subgroup Tables are exactly like Relation Tables. All that has been said about making definitions in Relation Tables holds for Subgroup Tables as well. Also unlike most of the other display windows, but in line with the Coset Table Window, the windows of the Subgroup Tables do not vanish when the contents of the Subgroup Tables changes but the tables change in their windows. <p> <p> <h2><a name="SECT008">4.8 The Table of Definitions</a></h2> <p><p> <a name = "I0"></a> Whenever the ITC performs a coset enumeration it saves the occurring sequence of definitions of coset numbers in a <strong>List of Definitions</strong>. This list is not affected by coincidence handling, however it is changed if you make new definitions or retrace to a previous state of the definition sequence using the <code>back to</code> bottom button (see <a href="CHAP005.htm#SSEC002.7">back to</a>) or call the Short-cut algorithm (see <a href="CHAP005.htm#SSEC002.9">short-cut</a>) or the ``Sorting Definitions'' (see <a href="CHAP005.htm#SSEC002.8">sort defs</a>). To some extent the List of Definitions reflects the history of the enumeration. It will probably be mainly of interest for use in further computations and can for that purpose be written to a file (see <code>write definitions to file</code>, <a href="CHAP005.htm#SSEC001.11">write definitions to file</a>, and <code>read definitions from file</code>, <a href="CHAP005.htm#SSEC001.10">read definitions from file</a>, of the top menu popped down by clicking the top button <code>File</code>). <p> The current state of the enumeration is reflected by a second list which we will call the <strong>Table of Definitions</strong>. It contains only the definitions of those coset numbers which are ``still alive'', i. e. which have not vanished by coincidences. and all coset numbers involved in these definitions which are not alive any more are replaced by their alive representatives. So the Table of Definitions also changes whenever a coincidence is handled. <p> Upon clicking with the <strong>left</strong> mouse button the (white) bottom button <code>show defs</code> (<a href="CHAP005.htm#SSEC002.12">show defs</a>) a window appears which displays the Table of Definitions or, to be more precise, an extract of that table consisting of the up to 30 lines corresponding to the cosets currently shown in the Coset Table Window. Like the Relation Tables (see Section <a href="CHAP004.htm#SECT005">The Relation Tables</a>) this window does not vanish when the contents of the Table of Definitions changes but the table changes in the window, and whenwever the Coset Table is scrolled using the bottom buttons <code>scroll to</code> (see <a href="CHAP005.htm#SSEC002.1">scroll to</a>) and <code>scroll by</code> (see <a href="CHAP005.htm#SSEC002.2">scroll by</a>) it will be scrolled in parallel. <p> Clicking with the <strong>left</strong> or with the <strong>right</strong> mouse button a definition <strong>in the Table of Definitions</strong> will open a window in which a coset representative of the coset defined here will be displayed as a word in the generators of <i>g</i> and their inverses. The coset representative displayed is the one that is obtained by retracing in the List (not the Table) of Definitions from this coset number to the coset number 1. A second click on the same definition will close the coset representative window again. Note that the coset representative windows can also be opened or closed by clicking a coset number in the Coset Table with the right mouse button (see Section <a href="CHAP004.htm#SECT001">The Coset Table</a>). <p> <p> <h2><a name="SECT009">4.9 The List of Length 1 Gaps</a></h2> <p><p> For some background definitions for ``gaps of length 1'' see Section <a href="CHAP003.htm#SECT002">Some Definition Strategies</a>. <p> On clicking the (white) bottom button <code>show gaps</code> (see <a href="CHAP005.htm#SSEC002.13">show gaps</a>), either, if no gaps of length 1 exist, only a warning <code>There are no gaps of length 1</code> appears in red below the Coset Table, or a window springs up that lists representatives of the equivalence classes of gaps of length 1 in Subgroup and Relation Tables. <p> A row in this list has the form <i>i</i>: <i>w</i> [ <i>l</i>, <i>x</i> ] or <i>i</i>: <i>w</i> [ <i>l</i>, <i>x</i><sup><font face="symbol">-</font>1</sup> ] respectively. Here <i>i</i> is just the number of the list entry in a consecutive numbering and <i>w</i> is the weight of the respective equivalence class of gaps of length 1. The remaining information describes the representative of that equivalence class (it indicates that defining a new coset as the product of the coset with number <i>l</i> and generator <i>x</i>, or <i>x</i><sup><font face="symbol">-</font>1</sup>, respectively, will close gaps of length 1 of weight <i>w</i> in Subgroup and Relation Tables). <p> The idea of giving this information is that the ``weight'' <i>w</i> may be a guide for the choice of definitions that have a strong influence on the progress of a CE. <p> By clicking on such a row with the <strong>left</strong> mouse button this definition will be made and together with its consequences inserted into all relevant places in the tables. See Section <a href="CHAP003.htm#SECT001">Making a Definition</a> for more details. <p> Clicking on one of the entries in this list with the <strong>right</strong> mouse button will open a further window in which all equivalent definitions are listed in the form [ <i>l</i>, <i>x</i> ] or [ <i>l</i>, <i>x</i><sup><font face="symbol">-</font>1</sup> ], respectively. <p> Clicking on any of these, again with the <strong>left</strong> mouse button, will result in making this definition. See again Section <a href="CHAP003.htm#SECT001">Making a Definition</a> for details. <p> <p> <h2><a name="SECT010">4.10 The List of Pending Coincidences</a></h2> <p><p> Clicking the (white) bottom button <code>show coincs</code> (<a href="CHAP005.htm#SSEC002.14">show coincs</a>) with the <strong>left</strong> mouse button you either get the warning <code>There are no pending coincidences</code> shown in red below the Coset Table, or a window springs up in which the list of all pending coincidences is shown. These appear in the form <i>i</i> = <i>j</i> meaning that the coset numbers <i>i</i> and <i>j</i> really denote the same coset. If <i>i</i> is the larger integer then clicking such a line in the List of Pending Coincidences will eliminate <i>i</i>, that is replace it by <i>j</i> in all occurrences in all tables and then suppress the <i>i</i>th lines in all tables. See also Section <a href="CHAP003.htm#SECT003">Handling a Coincidence</a>. <p> As a consequence, more coincidences may be found, so that the List of Pending Coincidences may have become longer. <p> In case coincidence handling is switched off (see <code>coincidence handling off</code>, <a href="CHAP005.htm#SSEC001.5">coincidence handling off</a> in the menu of the top button <code>Settings</code>), the CE process will stop automatically as soon as a coincidence is encountered and then the window for the List of Pending Coincidences will spring up automatically. <p> Since a coincidence really means that ITC has found two representatives, say <i>r</i> and <i>s</i>, of the same coset, given as words in the generators of the group, the quotient <i>r</i>*<i>s</i><sup><font face="symbol">-</font>1</sup> will be an element of the subgroup <i>h</i>. Clicking this coincidence with the <strong>right</strong> mouse button will open a window in which the subgroup element <i>r</i>*<i>s</i><sup><font face="symbol">-</font>1</sup> will be displayed as word in the generators of <i>g</i> and their inverses. <p> As in particular George Havas has pointed out in several papers (see for instance <a href="biblio.htm#HR99b"><cite>HR99b</cite></a>) it can be helpful in some ``hard'' coset enumerations to add subgroup words obtained in this way from coincidences to the subgroup generators in the <font face="Gill Sans,Helvetica,Arial">GAP</font> input of the given subgroup <i>h</i> and to restart ITC. <p> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <address>ITC manual<br>January 2004 </address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2052
