%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W basics.tex ACE documentation - basics Alexander Hulpke
%W Joachim Neub"user
%W Greg Gamble
%%
%H $Id: basics.tex,v 1.15 2006/01/26 16:15:05 gap Exp $
%%
%Y Copyright (C) 2000 Centre for Discrete Mathematics and Computing
%Y Department of Information Tech. & Electrical Eng.
%Y University of Queensland, Australia.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Some Basics}
\index{strategy}\atindex{Felsch strategy}{@Felsch strategy}
\atindex{HLT strategy}{@HLT strategy}
Throughout this manual for the use of {\ACE} as a {\GAP} package, we
shall assume that the reader already knows the basic ideas of coset
enumeration, as can be found for example in~\cite{Neu82}. There, a
simple proof is given for the fact that a coset enumeration for a
subgroup of finite index in a finitely presented group must eventually
terminate with the correct result, provided the enumeration process
obeys a simple condition (Mendelsohn's condition) formulated in
Lemma~1 and Theorem~2 of~\cite{Neu82}. This basic condition leaves
room for a great variety of *strategies* for coset enumeration; two
``classical'' ones have been known for a long time as the *Felsch
strategy* and the *HLT strategy* (for Haselgrove, Leech and Trotter).
Extensive experimental studies on many strategies can be found
in~\cite{CDHW73}, \cite{Hav91}, \cite{HR99a}, and \cite{HR01}, in
particular.
A few basic points should be particularly understood:
\beginlist%unordered
\item{--} ``Subgroup (generator) and relator tables'' that are used in
the description of coset enumeration in \cite{Neu82}, and to which we
will also occasionally refer in this manual, do *not* physically exist
in the implementation of coset enumeration in {\ACE}. For a
terminology that is closer to the actual implementation and also to
the formulations in the manual for the {\ACE} standalone see
\cite{CDHW73} and \cite{Hav91}.
\index{cosets!coset numbers}\index{cosets!coset table}\index{holes}
\item{--} Coset enumeration proceeds by defining *coset numbers* that
really denote possible representatives for cosets written as words in
the generators of the group. At the time of their generation it is not
guaranteed that any two of these words do indeed represent different
cosets. The state of an enumeration at any time is stored in a
2-dimensional array known as a *coset table* whose rows are indexed by
coset numbers and whose columns are indexed by the group generators
and their inverses. Entries of the coset table that are not yet
defined are known as *holes* (typically they are filled with 0,
i.e.~an invalid coset number).
\index{cosets}\index{cosets!coset application}\index{cosets!coset numbers}
\item{--} It is customary in talking about coset enumeration to speak
of *cosets* when really coset numbers are meant. While we try to avoid
this in this interface manual, in certain word combinations such as
*coset application* we will follow this custom.
\index{deduction}\index{deduction!deduction stack}
\item{--} The definition of a coset number may lead to *deductions*
from the ``closing of rows in subgroup or relator tables''. These are
kept in a *deduction stack*.
\index{coincidence}\index{coincidence!coincidence queue}
\item{--} Also it may be found that (different) words in the
generators defining different coset numbers really lie in the same
coset of the given subgroup. This is called a *coincidence* and will
eventually lead to the elimination of the larger of the two coset
numbers. Until this elimination has been performed pending
coincidences are kept in a *queue of coincidences*.
\index{preferred definition}\index{definition!preferred}
\index{preferred definition!preferred definition stack}
\item{--} A definition that will actually close a row in a subgroup or
relator table will immediately yield twice as many entries in the
coset table as other definitions. Such definitions are called
*preferred definitions*, the places in rows of a subgroup or relator
table that they close are also referred to as ``gaps of length one''
or minimal gaps. Such gaps can be found at little extra cost when
``relators are traced from a given coset number''. {\ACE} keeps a
selection of them in a *preferred definition stack* for use in some
definition strategies (see~\cite{Hav91}).
\endlist
It will also be necessary to understand some further basic features of
the implementation and the corresponding terminology which we will
explain in the sequel.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Enumeration Style}
The first main decision for any coset enumeration is in which sequence
to make definitions. When a new coset number has to be defined, in
{\ACE} there are basically three possible methods to choose from:
\beginlist%unordered
\atindex{C style}{@C style!definition}
\item{--} One may fill the next empty entry in the coset table by
scanning from the left/top of the coset table towards the right/bottom
-- that is, in order row by row. This is called *C style definition*
(for *C*oset Table Based definition) of coset numbers. In fact a
procedure needs to follow a method like this to some extent for the
proofs that coset enumeration eventually terminates in the case of
finite index (see~\cite{Neu82}).
\atindex{R style}{@R style!definition}
\item{--} For an *R style definition* (for *R*elator Based
definition), the order in which coset numbers are defined is
explicitly prescribed by the order in which rows of (the subgroup
generator tables and) the relator tables are filled by making
definitions.
\index{preferred definition}
\index{preferred definition!preferred definition stack}
\index{strategy!minimal gaps}
\item{--} One may choose definitions from a *Preferred Definition
Stack*. In this stack possibilities for definition of coset numbers
are stored that will close a certain row of a relator table. Using
these *preferred definitions* is sometimes also referred to as a
*minimal gaps strategy*. The idea of using these is that by closing a
row in a relator table, thus, one will immediately get a consequence.
We will come back to the obvious question of where one obtains this
``preferred definition stack''.
\endlist
The *enumeration style* is mainly determined by the balance between
C style and R style definitions, which is controlled by the values of
the `ct' and `rt' options (see~"option ct" and~"option rt").
However this still leaves us with plenty of freedom for the design of
definition strategies, freedom which can, for example, be used to
great advantage in Felsch-type strategies. Though it is not strictly
necessary, before embarking on further enumeration, Felsch-type
programs generally start off by ensuring that each of the given
subgroup generators produces a cycle of coset numbers at coset 1. To
explain the idea, an example may help. Suppose $a,b$ are the group
generators and $w=Abab$ is a subgroup generator, where $A$ represents
the inverse of $a$; then to say that ``$(1,i,j,k)$ is a cycle of
coset numbers produced at coset 1 by $w$'' means that the successive
application of the ``letters'' $A,b,a,b$ of $w$ takes one
successively from coset 1, through cosets $i$, $j$ and $k$, and back
to coset 1, i.e.~$A$ applied to coset 1 results in coset $i$, $b$
applied to coset $i$ results in coset $j$, $a$ applied to coset $j$
results in coset $k$, and finally $b$ applied to coset $k$ takes us
back to coset $1$. In this way, a hypothetical subgroup table is
filled first. The use of this and other possibilities leads to the
following table of *enumeration styles*.
% \begin{table}
% \hrule
% \caption{The styles}
% \label{tab:sty}
% \smallskip
% \renewcommand{\arraystretch}{0.875}
% \begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}crrlc}
% \hline\hline
% & \ttt{Rt} value & \ttt{Ct} value & style name & \\
% \hline
% & $<\!0$ & $<\!0$ & R/C & \\
% & $<\!0$ & $0$ & R* & \\
% & $<\!0$ & $>\!0$ & Cr & \\
% & $0$ & $<\!0$ & C & \\
% & $0$ & $0$ & R/C (defaulted) & \\
% & $0$ & $>\!0$ & C & \\
% & $>\!0$ & $<\!0$ & Rc & \\
% & $>\!0$ & $0$ & R & \\
% & $>\!0$ & $>\!0$ & CR & \\
% \hline\hline
% \end{tabular*}
% \end{table}
\begintt
Rt value Ct value style name
-----------------------------------------
0 >0 C
<0 >0 Cr
>0 >0 CR
>0 0 R
<0 0 R*
>0 <0 Rc
<0 <0 R/C
0 0 R/C (defaulted)
-----------------------------------------
\endtt
\beginitems
\atindex{C style}{@C style}
*C style* &
In this style, most definitions are made in the next empty coset table
slot and are (in principle) tested in all essentially different
positions in the relators; i.e.~this is a Felsch-like style.
However, in C style, some definitions may be made following a
preferred definition strategy, controlled by the `pmode' and `psize'
options (see~"option pmode" and~"option psize").
\atindex{Cr style}{@Cr style}
*Cr style* &
is like C style except that a single R style pass is done after the
initial C style pass.
\atindex{CR style}{@CR style}
*CR style* &
In this style, alternate passes of C style and R style are performed.
\atindex{R style}{@R style}
*R style* &
In this style, all the definitions are made via relator scans;
i.e.~this is an HLT-like style.
\atindex{R\* style}{@R\* style}
*R\* style* &
makes definitions the same as R style, but tests all definitions as
for C style.
\atindex{Rc style}{@Rc style}
*Rc style* &
is like R style, except that a single C style pass is done after the
initial R style pass.
\atindex{R/C style}{@R/C style}
*R/C style* &
In this style, we run in R style until an overflow, perform a
lookahead on the entire table, and then switch to CR style.
\atindex{Defaulted R/C style}{@Defaulted R/C style}
\atindex{R/C (defaulted) style}{@R/C (defaulted) style}
*Defaulted R/C* ($={}$*R/C (defaulted)* $\,$) *style* &
is the default style used if you call {\ACE} without specifying
options. In it, we use R/C style with `ct' set to 1000 and `rt' set to
approximately $2000$ divided by the total length of the relators in an
attempt to balance R style and C style definitions when we switch to
CR style.
\enditems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Finding Deductions, Coincidences, and Preferred Definitions}
\index{definition}
First, let us broadly discuss strategies and how they influence
``definitions''. By *definition* we mean the allocation of a coset
number. In a complete coset table each group relator produces a cycle
of cosets numbers at each coset number, in particular, at coset 1;
i.e.~for each relator $w$, and for each coset number $i$, successive
application of the letters of $w$ trace through a sequence of coset
numbers that begins and ends in $i$ (see Section~"Enumeration Style"
for an example). It has been found to be a good general rule to use
the given group relators as subgroup generators. This ensures the
early definition of some useful coset numbers, and is the basis of the
`default' strategy (see~"option default"). The number of group
relators included as subgroup generators is determined by the `no'
option (see~"option no"). Over a wide range of examples the use of
group relators in this way has been shown to produce generally
beneficial results in terms of the maximum number of cosets numbers
defined at any one time and the total number of coset numbers defined.
In~\cite{CDHW73}, it was reported that for some Macdonald group
$G(\alpha,\beta)$ examples, (pure) Felsch-type strategies (that don't
include the given group relators as subgroup generators) e.g.~the
`felsch := 0' strategy (see~"option felsch") defined significantly
more coset numbers than HLT-type (e.g.~the `hlt' strategy, see~"option
hlt") strategies. The comparison of these strategies in terms of total
number of coset numbers defined, in~\cite{Hav91}, for the enumeration
of the cosets of a certain index 40 subgroup of the $G(3,21)$
Macdonald group were 91 for HLT versus 16067 for a pure Felsch-type
strategy. For the Felsch strategy with the group relators included as
subgroup generators, as for the `felsch := 1' strategy (see~"option
felsch") the total number of coset numbers defined reduced markedly to
59.
\index{deduction}
A *deduction* occurs when the scanning of a relator results in the
assignment of a coset table body entry. A completed table is only
valid if every table entry has been tested in all essentially
different positions in all relators. This testing can either be done
directly (Felsch strategy) or via relator scanning (HLT strategy). If
it is done directly, then more than one deduction can be waiting to be
processed at any one time. The untested deductions are stored in a
stack. How this stack is managed is determined by the `dmode' option
(see~"option dmode"), and its size is controlled by the `dsize' option
(see~"option dsize").
\index{coincidence}\index{dead coset (number)}
As already mentioned a *coincidence* occurs when it is determined that
two coset numbers in fact represent the same coset. When this occurs
the larger coset number becomes a *dead coset number* and the
coincidence is placed in a queue. When and how these dead coset
numbers are eventually eliminated is controlled by the options
`dmode', `path' and `compaction' (see~"option dmode", "option path"
and~"option compaction"). The user may also force coincidences to
occur (see Section~"Finding Subgroups"), which, however, may change
the subgroup whose cosets are enumerated.
\index{preferred definition!preferred definition stack}
The key to performance of coset enumeration procedures is good
selection of the next coset number to be defined. Leech
in~\cite{Lee77} and~\cite{Lee84} showed how a number of coset
enumerations could be simplified by removing coset numbers needlessly
defined by computer implementations. Human enumerators intelligently
choose which coset number should be defined next, based on the value
of each potential definition. In particular, definitions which close
relator cycles (or at least shorten gaps in cycles) are favoured. A
definition which actually closes a relator cycle immediately yields
twice as many table entries (deductions) as other definitions. The
value of the `pmode' option (see~"option pmode") determines which
definitions are *preferred*; if the value of the `pmode' option is
non-zero, depending on the `pmode' value, gaps of length one found
during relator C style (i.e.~Felsch-like) scans are either filled
immediately (subject to the value of `fill') or noted in the
*preferred definition stack*. The preferred definition stack is
implemented as a ring of size determined by the `psize' option
(see~"option psize"). However, making preferred definitions carelessly
can violate the conditions required for guaranteed termination of the
coset enumeration procedure in the case of finite index. To avoid such
a violation {\ACE} ensures a fraction of the coset table is filled
before a preferred definition is made; the reciprocal of this
fraction, the `fill factor', is manipulated via the `fill' option
(see~"option fill"). In~\cite{Hav91}, the `felsch := 1' type
enumeration of the cosets of the certain index 40 subgroup of the
$G(3,21)$ Macdonald group was further improved to require a total
number of coset numbers of just 43 by incorporating the use of
preferred definitions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Finding Subgroups}
\index{coincidence}
The {\ACE} package, via its interactive {\ACE} interface functions
(described in Chapter~"Functions for Using ACE Interactively"),
provides the possibility of searching for subgroups. To do this one
starts at a known subgroup (possibly the trivial subgroup). Then one
may augment it by adding new subgroup generators either explicitly via
`ACEAddSubgroupGenerators' (see~"ACEAddSubgroupGenerators") or
implicitly by introducing *coincidences* (see `ACECosetCoincidence':
"ACECosetCoincidence", or `ACERandomCoincidences':
"ACERandomCoincidences"). Also, one may descend to smaller subgroups
by deleting subgroup generators via `ACEDeleteSubgroupGenerators'
(see~"ACEDeleteSubgroupGenerators").
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Coset Table Standardisation Schemes}
\atindex{lenlex standardisation scheme}{@\noexpand`lenlex' %
standardisation scheme}
The default standardisation scheme for {\GAP} from {\GAP}~4.3 and the
standardisation scheme provided by {\ACE} is the `lenlex' scheme, of
Charles Sims~\cite{Sim94}. This scheme numbers cosets first according
to word-length and then according to a lexical ordering of coset
representatives. Each coset representative is a word in an alphabet
consisting of the user-supplied generators and their inverses, and the
lexical ordering of `lenlex' is that implied by ordering that alphabet
so that each generator is followed by its inverse, and the generators
appear in user-supplied order. See below for an example which gives
the first 20 lines of the `lenlex' standard coset table of the
(infinite) group with presentation $\langle x, y, a, b \mid x^2, y^3,
a^4, b^2\rangle$.
In the table each inverse of a generator is represented by the
corresponding uppercase letter ($X$ represents the inverse of $x$
etc.), and the lexical ordering of the representatives is that implied
by defining an ordering of the alphabet of user-supplied generators
and their inverses to be $x\<X\<y\<Y\<a\<A\<b\<B$.
A `lenlex' standard coset table whose columns correspond, in order, to
the already-described alphabet, of generators and their inverses, has
an important property: a scan of the body of the table row by row from
left to right, encounters new coset numbers in numeric order. Observe
that the table below has this property: the definition of coset 1 is
implicit; the first coset number we encounter in the table body is 2,
then 2 again, 3, 4, 5, 6, 7, then 7 again, etc.
With the `lenlex' option (see~"option lenlex"), the coset table output
by `ACECosetTable' or `ACECosetTableFromGensAndRels' is standardised
according to the `lenlex' scheme.
\begintt
coset no. || x X y Y a A b B rep've
-----------+------------------------------------------------------------------
1 || 2 2 3 4 5 6 7 7
2 || 1 1 8 9 10 11 12 12 x
3 || 13 13 4 1 14 15 16 16 y
4 || 17 17 1 3 18 19 20 20 Y
5 || 21 21 22 23 24 1 25 25 a
6 || 26 26 27 28 1 24 29 29 A
7 || 30 30 31 32 33 34 1 1 b
8 || 35 35 9 2 36 37 38 38 xy
9 || 39 39 2 8 40 41 42 42 xY
10 || 43 43 44 45 46 2 47 47 xa
11 || 48 48 49 50 2 46 51 51 xA
12 || 52 52 53 54 55 56 2 2 xb
13 || 3 3 57 58 59 60 61 61 yx
14 || 62 62 63 64 65 3 66 66 ya
15 || 67 67 68 69 3 65 70 70 yA
16 || 71 71 72 73 74 75 3 3 yb
17 || 4 4 76 77 78 79 80 80 Yx
18 || 81 81 82 83 84 4 85 85 Ya
19 || 86 86 87 88 4 84 89 89 YA
20 || 90 90 91 92 93 94 4 4 Yb
\endtt
\atindex{semilenlex standardisation scheme}{@\noexpand`semilenlex' %
standardisation scheme}
Another standardisation scheme for coset tables (the default scheme of
versions of {\GAP} up to {\GAP}~4.2), numbers cosets according to
coset representative word-length in the group generators and lexical
ordering imposed by the user-supplied ordering of the group
generators; it is known as `semilenlex' since though like `lenlex',
generator inverses do not feature. Here again is 20 lines of the coset
table of the group with presentation $\langle x, y, a, b \mid x^2,
y^3, a^4, b^2\rangle$, this time `semilenlex' standardised.
\begintt
coset no. || x y a b rep've
-----------+--------------------------------------
1 || 2 3 4 5
2 || 1 6 7 8 x
3 || 9 10 11 12 y
4 || 13 14 15 16 a
5 || 17 18 19 1 b
6 || 20 21 22 23 xy
7 || 24 25 2 26 xa
8 || 27 28 29 2 xb
9 || 3 30 31 32 yx
10 || 33 1 34 35 yy
11 || 36 37 38 39 ya
12 || 40 41 42 3 yb
13 || 4 43 44 45 ax
14 || 46 47 48 49 ay
15 || 50 51 52 53 aa
16 || 54 55 56 4 ab
17 || 5 57 58 59 bx
18 || 60 61 62 63 by
19 || 64 65 66 67 ba
20 || 6 68 69 70 xyx
\endtt
The term `semilenlex' was coined by Edmund Robertson and Joachim
Neub{\accent127u}ser, for the scheme's applicability to semigroups
where generator inverses need not exist. This scheme ensures that as
one scans the columns corresponding to the group generators (in
user-supplied order) row by row, one encounters new coset numbers in
numeric order.
Observe that the representatives are ordered according to length and
then the lexical ordering implied by defining $x\<y\<a\<b$ (with some
words omitted due to their equivalence to words that precede them in
the ordering). Also observe that as one scans the body of the table
row by row from left to right new coset numbers appear in numeric
order without gaps (2, 3, 4, 5, then 1 which we have implicitly
already seen, 6, 7, etc.).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Coset Statistics Terminology}
\indextt{activecosets}\indextt{maxcosets}\indextt{totcosets}
\index{coincidence}\index{dead coset (number)}\index{alive coset number}
There are three statistics involved in the counting of coset number
definitions: `activecosets', `maxcosets' and `totcosets'; these are
three of the fields of the record returned by `ACEStats' (see
Section~"Using ACE Directly to Test whether a Coset Enumeration
Terminates"), and they correspond to the `a', `m' and `t' statistics
of an {\ACE} ``results message'' (see Appendix~"The Meanings of ACE's
Output Messages"). As already described, coset enumeration proceeds by
defining coset numbers; `totcosets' counts *all* such definitions made
during an enumeration. During the coset enumeration process,
*coincidences* usually occur, resulting in the larger of each
coincident pair becoming a *dead coset number*. The statistic
`activecosets' is the count of coset numbers left *alive* (i.e.~not
dead) at the end of an enumeration; and `maxcosets' is the maximum
number of *alive* cosets at any point of an enumeration.
In practice, the statistics `maxcosets' and `totcosets' tend to be of
a similar order, though, of course, `maxcosets' can never be more than
`totcosets'.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Other Terminology}
\index{loop}\index{pass}\index{state (machine)}
In various places in this manual, we will refer to a (main) *loop* or
a *pass* through such a loop. We don't intend to give a precise
meaning to these terms. The reader will need to forgive us for giving
somewhat circular definitions in our attempt to make these terms less
nebulous. It is sufficient to appreciate that the {\ACE} enumerator is
organised as a state machine, where each *state* is a value of the
coset table held internally by {\ACE} at the end of each ``main
loop''. Each step from one state to the next (i.e.~each passage
through the main loop) performs an ``action'' (i.e., `lookahead',
`compaction'; see~"option lookahead" and~"option compaction") or a
block of actions (i.e., `|ct|' coset number definitions, `|rt|' coset
number applications). {\ACE} counts the number of passes through the
main loop; if the option `loop' (see~"option loop") is set to a
positive integer, {\ACE} makes an early return when the loop count
hits the value of `loop'.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
601
