|
The central intrinsic attempts to construct an automatic structure in
the form of finite state automata for a given finitely presented group.
Subsequent sections describe operations with elements including arithmetic,
element enumeration and the construction of a growth function.
The words in an automatic group G are ordered using the short-lex
ordering on words. Under this ordering shorter words come before longer,
and for words of equal length lexicographical ordering is used, based on
the given ordering of the generators. Thus, a short-lex automatic
group is constructed.
The family of all automatic groups forms a category. The objects are the
automatic groups and the morphisms are group homomorphisms. The Magma
designation for this category of groups is GrpAtc. Elements of a
automatic group are designated as GrpAtcElt.
Much of the material in this section is based on the KBMAG documentation
[Hol97]. Some familiarity with the Knuth--Bendix completion procedure
and the automata associated with a short-lex automatic group is assumed.
An automatic group G is constructed in a three-step process:
- (i)
- We construct a free group FG.
- (ii)
- We construct a quotient F of FG.
- (iii)
- We create a monoid presentation for F and then run
procedures which attempt to construct the automata associated with G
and to prove them correct.
These procedures may or may not succeed. Of course, if G is not an
automatic group then they have no chance of succeeding.
IsAutomaticGroup(F: parameters) : GrpFP -> BoolElt, GrpAtc
Internally a monoid presentation P of the group F is constructed. By
default the generators of P are taken to be
g1, (g1) - 1, ..., gn, (gn) - 1 where g1, ..., gn are
the generators of F. The relations of
P are taken to be the relations of F. The trivial
relations between the generators and their inverses are also added.
The word ordering is the short-lex ordering.
The Knuth--Bendix completion procedure for monoids is now run on P
to calculate the word difference automata corresponding to the generated
equations, which are then used to calculate the finite state automata
associated with a short-lex automatic group. In successful cases these
automata are proved correct in the final step.
If the procedure succeeds the result will be an automatic group, G,
containing four automata. These are the first and second word-difference
machines, the word acceptor, and the word multiplier. The form
AutomaticGroup returns an automatic group while the form
IsAutomaticGroup returns the boolean value true and
the automatic group. If the procedure fails, the first form does
not return a value while the second returns the boolean value false.
For simple examples, the algorithms work quickly, and do not require
much space. For more difficult examples, the algorithms are often capable of
completing successfully, but they can sometimes be expensive in terms of
time and space requirements.
Another point to be borne in mind is that the algorithms sometimes produce
temporary disk files which the user does not normally see (because they are
automatically removed after use), but can occasionally be very large.
These files are stored in the /tmp directory. If you interrupt
a running automatic group calculation you must remove these temporary
files yourself.
As the Knuth--Bendix procedure will more often than not run forever,
some conditions must be specified under which it will stop. These take the
form of limits that are placed on certain variables, such as the number of
reduction relations. If any of these limits are exceeded during a run of the
completion procedure it will fail, returning a non-confluent automatic group.
The optimal values for these limits varies from example to example. Some
of these limits may be specified by setting parameters (see the next section).
In particular, if a first attempt to compute the automatic structure of a group
fails, it should be run again with the parameter Large (or Huge)
set to {true}.
We construct the automatic structure for the fundamental group of the torus.
Since a generator ordering is not specified, the default generator ordering,
[ a, a - 1, b, b - 1, c, c - 1, d, d - 1], is used.
> FG<a,b,c,d> := FreeGroup(4);
> F := quo< FG | a^-1*b^-1*a*b=d^-1*c^-1*d*c>;
> f, G := IsAutomaticGroup(F);
> f;
true
> G;
An automatic group.
Generator Ordering = [ a, a^-1, b, b^-1, c, c^-1, d, d^-1 ]
The second word difference machine has 33 states.
The word acceptor has 36 states.
We now do the same computation with a verbose flag (discussed later)
turned on to display some information.
> FG<a,b,c,d> := FreeGroup(4);
> F := quo< FG | a^-1*b^-1*a*b=d^-1*c^-1*d*c>;
> SetVerbose("KBMAG", 1);
> f, G := IsAutomaticGroup(F);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#Halting with 118 equations.
#First word-difference machine with 33 states computed.
#Second word-difference machine with 33 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 36 states computed.
#General multiplier with 104 states computed.
#Validity test on general multiplier succeeded.
#General length-2 multiplier with 220 states computed.
#Checking inverse and short relations.
#Checking relation: _8*_6*_7*_5 = _2*_4*_1*_3
#Axiom checking succeeded.
> G;
An automatic group.
Generator Ordering = [ a, a^-1, b, b^-1, c, c^-1, d, d^-1 ]
The second word difference machine has 33 states.
The word acceptor has 36 states.
In this section we describe the various parameters used to control the
execution of the procedures employed to determine the automatic structure.
IsAutomaticGroup(F: parameters) : GrpFP -> BoolElt, GrpAtc
Attempt to construct an automatic structure for the finitely presented
group F (see the main entry). We now present details of the various
parameters used to control the execution of the procedures.
Large: BoolElt Default: false
If Large is set to true large hash tables are used
internally. Also the Knuth--Bendix algorithm is run with larger
parameters, specifically TidyInt is set to 500, MaxRelations is set to 262144, MaxStates is set to unlimited, HaltingFactor is set to 100, MinTime is set to 20 and ConfNum is set to 0. It is advisable to use this option only after
having first tried without it, since it will result in much longer
execution times for easy examples.
Huge: BoolElt Default: false
Setting Huge to true doubles the size of the hash tables
and MaxRelations over the Large parameter.
As with the Large parameter, it is advisable to use this option
only after having first tried without it.
MaxRelations: RngIntElt Default: 200
Limit the maximum number of reduction equations to MaxRelations.
TidyInt: RngIntElt Default: 20
After finding n new reduction equations, the completion procedure
interrupts the main process of looking for overlaps, to tidy up the
existing set of equations. This will eliminate any redundant
equations performing some reductions on their left and right hand
sides to make the set as compact as possible. (The point is that
equations discovered later often make older equations redundant or
too long.) The word-differences arising from the equations are
calculated after each such tidying and the number reported if verbose
printing is on. The best strategy in general is to try a small value
of TidyInt first and, if that is not successful, try increasing
it. Large values such as 1000 work best in really difficult
examples.
GeneratorOrder: SeqEnum Default:
Give an ordering for the generators of P. This ordering affects the
ordering of words in the alphabet. If not specified, the ordering
defaults to [g1, (g1) - 1, ..., gn, (gn) - 1] where g1, ..., gn are the generators of F.
MaxWordDiffs: RngIntElt Default:
Limit the maximum number of word differences to MaxWordDiffs.
The default behaviour is to increase the number of allowed word
differences dynamically as required, and so usually one does not need
to set this option.
HaltingFactor: RngIntElt Default: 100
MinTime: RngIntElt Default: 5
These options are experimental halting options. HaltingFactor
is a positive integer representing a percentage. After each tidying
it is checked whether both the number of equations and the number of
states have increased by more than HaltingFactor percent since
the number of word-differences was last less than what it is now. If
so the program halts. A sensible value seems to be 100, but
occasionally a larger value is necessary. If the MinTime
option is also set then halting only occurs if at least MinTime
seconds of cpu-time have elapsed altogether. This is sometimes
necessary to prevent very early premature halting. It is not very
satisfactory, because of course the cpu-time depends heavily on the
particular computer being used, but no reasonable alternative has
been found yet.
Set the verbose printing level for the Knuth--Bendix completion algorithm.
Setting this level allows a user to control how much extra information on
the progress of the algorithm is printed.
Currently the legal values for v are 0 to 3 inclusive. Setting
v to 0 corresponds to the `-silent' option of KBMAG in which no extra output
is printed. Setting v to 2 corresponds to the `-v' (verbose) option of
KBMAG in which a small amount of extra output is printed.
Setting v to 3 corresponds to
the `-vv' (very verbose) option of KBMAG in which
a huge amount of diagnostic information is printed.
We attempt to construct an automatic structure for one of Listing's
knot groups.
> F := Group< d, f | f*d*f^-1*d*f*d^-1*f^-1*d*f^-1*d^-1 = 1 >;
> SetVerbose("KBMAG", 1);
> b, G := IsAutomaticGroup(F);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#Maximum number of equations exceeded.
#Halting with 195 equations.
#First word-difference machine with 45 states computed.
#Second word-difference machine with 53 states computed.
> b;
false;
So this attempt has failed. We run the IsAutomaticGroup function
again setting Large to true. This time we succeed.
> f, G := IsAutomaticGroup(F : Large := true);
Running Knuth-Bendix with the following parameter values
MaxRelations = 262144
MaxStates = 0
TidyInt = 500
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#Halting with 3055 equations.
#First word-difference machine with 49 states computed.
#Second word-difference machine with 61 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 101 states computed.
#General multiplier with 497 states computed.
#Multiplier incorrect with generator number 3.
#General multiplier with 509 states computed.
#Multiplier incorrect with generator number 3.
#General multiplier with 521 states computed.
#Multiplier incorrect with generator number 3.
#General multiplier with 525 states computed.
#Validity test on general multiplier succeeded.
#General length-2 multiplier with 835 states computed.
#Checking inverse and short relations.
#Checking relation: _3*_1*_4*_1*_3 = _1*_3*_2*_3*_1
#Axiom checking succeeded.
> G;
An automatic group.
Generator Ordering = [ d, d^-1, f, f^-1 ]
The second word difference machine has 89 states.
The word acceptor has 101 states.
We construct the automatic group corresponding to the fundamental
group of the trefoil knot. A generator order is specified.
> F<a, b> := Group< a, b | b*a^-1*b=a^-1*b*a^-1 >;
> SetVerbose("KBMAG", 1);
> f, G := IsAutomaticGroup(F: GeneratorOrder := [a,a^-1, b, b^-1]);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#Halting with 83 equations.
#First word-difference machine with 15 states computed.
#Second word-difference machine with 17 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 15 states computed.
#General multiplier with 67 states computed.
#Multiplier incorrect with generator number 4.
#General multiplier with 71 states computed.
#Validity test on general multiplier succeeded.
#General length-2 multiplier with 361 states computed.
#Checking inverse and short relations.
#Checking relation: _3*_2*_3 = _2*_3*_2
#Axiom checking succeeded.
> G;
An automatic group.
Generator Ordering = [ a, a^-1, b, b^-1 ]
The second word difference machine has 21 states.
The word acceptor has 15 states.
The functions in this section provide access to basic information stored for an
automatic group G.
The i-th defining generator for G. The integer i must lie in the
range [ - r, r], where r is the number of
group G.
A sequence containing the defining generators for G.
Ngens(G) : GrpRWS -> RngIntElt
The number of defining generators for G.
We illustrate the access operations using the
Von Dyck (2,3,5) group (isomorphic to A 5).
> F<a, b> := FreeGroup(2);
> Q := quo< F | a*a = 1, b*b = b^-1, a*b^-1*a*b^-1*a = b*a*b*a*b>;
> f, G<a, b> := IsAutomaticGroup(Q);
> G;
An automatic group.
Generator Ordering = [ a, a^-1, b, b^-1 ]
The second word difference machine has 33 states.
The word acceptor has 28 states.
> print G.1*G.2;
a * b
> print Generators(G);
[ a, b ]
> print Ngens(G);
2
> rels := Relations(G);
> print rels[1];
Q.2 * Q.2^-1 = Id(Q)
> print rels[2];
Q.2^-1 * Q.2 = Id(Q)
> print rels[3];
Q.1^2 = Id(Q)
> print rels[4];
Q.2^2 = Q.2^-1
> print Nrels(G);
18
> print Ordering(G);
ShortLex
Returns the finitely presented group F used in the construction of G,
and the isomorphism from F to G.
A record describing the word acceptor automaton stored in G.
The number of states of the word acceptor automaton stored in G, and
the size of the alphabet of this automaton.
A record describing the word difference automaton stored in G.
The number of states of the 2nd word difference automaton stored in G, and
the size of the alphabet of this automaton.
The labels of the states of the word difference automaton stored in G.
The result is a sequence of elements of the finitely presented group used
in the construction of G.
The value of the GeneratorOrder parameter used in the construction of G.
The result is a sequence of generators and their inverses from the
finitely presented group used in the construction of G.
Given an automatic group G return true if G has finite order
and false otherwise. If G does have finite order also return
the order of G.
# G : GrpRWS -> RngIntElt
The order of the group G as an integer. If the order of G is
known to be infinite, the symbol ∞ is returned.
We construct the group Z wreath C2 and compute its order.
The result of Infinity indicates that the group has
infinite order.
> F<a,b,t> := FreeGroup(3);
> Q := quo< F | t^2 = 1, b*a = a*b, t*a*t = b>;
> SetVerbose("KBMAG", 1);
> f, G := IsAutomaticGroup(Q);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#System is confluent.
#Halting with 14 equations.
#First word-difference machine with 14 states computed.
#Second word-difference machine with 14 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 6 states computed.
#General multiplier with 27 states computed.
#Validity test on general multiplier succeeded.
#Checking inverse and short relations.
#Axiom checking succeeded.
> Order(G);
Infinity
We construct a three fold cover of A 6 and check whether
it has finite order.
> FG<a,b> := FreeGroup(2);
> F := quo< FG | a^3 = 1, b^3 = 1, (a*b)^4 = 1, (a*b^-1)^5 = 1>;
> SetVerbose("KBMAG", 1);
> f, G := IsAutomaticGroup(F : GeneratorOrder := [a, b, a^-1, b^-1]);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#System is confluent.
#Halting with 183 equations.
#First word-difference machine with 289 states computed.
#Second word-difference machine with 360 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 314 states computed.
#General multiplier with 1638 states computed.
#Multiplier incorrect with generator number 4.
#General multiplier with 1958 states computed.
#Multiplier incorrect with generator number 2.
#General multiplier with 2020 states computed.
#Multiplier incorrect with generator number 1.
#General multiplier with 2038 states computed.
#Validity test on general multiplier succeeded.
#General length-2 multiplier with 4252 states computed.
#Checking inverse and short relations.
#Checking relation: _1*_2*_1*_2 = _4*_3*_4*_3
#Checking relation: _1*_4*_1*_4*_1 = _2*_3*_2*_3*_2
#Axiom checking succeeded.
> IsFinite(G);
true 1080
> isf, ord := IsFinite(G);
> isf, ord;
true 1080
Given an automatic group G defined on r generators and a sequence
[i1, ..., is] of integers lying in the range [ - r, r],
excluding 0, construct the word
G.|i1|ε1 * G.|i2|ε2 * ... * G.|is|εs
where εj is +1 if ij is positive, and -1 if ij is
negative. The word will be returned in reduced form.
Id(G) : GrpAtc -> GrpAtcElt
G ! 1 : GrpAtc, RngIntElt -> GrpAtcElt
Construct the identity word in the automatic group G.
The parent group G for the word w.
We construct some words in a two-generator two-relator group.
> F<a, b> := Group< a, b | a^2 = b^2, a*b*a = b*a*b >;
> f, G<a, b> := IsAutomaticGroup(F);
> G;
An automatic group.
Generator Ordering = [ $.1, $.1^-1, $.2, $.2^-1 ]
The second word difference machine has 11 states.
The word acceptor has 8 states.
> Id(G);
Id(G)
> print G!1;
Id(G)
> a*b*a*b^3;
a^4 * b * a
> G![1,2,1,2,2,2];
a^4 * b * a
Having constructed an automatic group G one can perform arithmetic with words
in G. Assuming we have u, v ∈G then the product u * v will be computed
as follows:
- (i)
- The product w = u * v is formed as a product in the appropriate
free group.
- (ii)
- w is reduced using the second word difference machine associated
with G.
Note that:
- (i)
- Reduction of w can cause an increase in the length of w. At
present there is an internal limit on the length of a word -- if this limit
is exceeded during reduction an error will be raised. Hence any word operation
involving reduction can fail.
- (ii)
- The implementation is designed more with speed of execution in
mind than with minimizing space requirements; thus, the reduction machine is
always used to carry out word reduction, which can be space-consuming,
particularly when the number of generators is large.
Given words w and v belonging to a common group,
return their product.
Given words w and v belonging to a common group,
return the product of the word u by the inverse of
the word v, i.e. the word u * v - 1.
The n-th power of the word w.
Given words w and v belonging to a common group,
return the conjugate of the word u by the word v,
i.e. the word v - 1 * u * v.
The inverse of the word w.
Given words w and v belonging to a common group,
return the commutator of the words u and v,
i.e., the word u - 1v - 1uv.
Given r words u1, ..., ur belonging to a common group,
return their commutator. Commutators are left-normed, so they are
evaluated from left to right.
Given words w and v belonging to the same group, return true
if w and v reduce to the same normal form, false otherwise. If G is
confluent this tests for equality. If G is non-confluent
then two words which are the same may not reduce to the same normal form.
Given words w and v belonging to the same group, return false
if w and v reduce to the same normal form, true otherwise. If G is
confluent this tests for non-equality. If G is non-confluent
then two words which are the same may reduce to different normal forms.
IsIdentity(w) : GrpRWSElt -> BoolElt
Returns true if the word w is the identity word.
The length of the word w.
Eltseq(u) : GrpRWSElt -> [ RngIntElt ]
The sequence Q obtained by decomposing the element u of a rewrite group
into its constituent
generators and generator inverses. Suppose u is a word in the rewrite
group G. Then, if u = G.i1e1 ... G.imem, with
each ei equaling plus or minus 1,
then Q[j] = ij if ej = + 1 and Q[j] = - ij if ej = (-1), for
j = 1, ..., m.
We illustrate the word operations by applying them to elements of the
fundamental group of a 3-manifold.
We illustrate the word operations by applying them to elements of a
free group of rank two (with lots of redundant generators).
> FG<a,b,c,d,e> := FreeGroup(5);
> F := quo< FG | a*d*d = 1, b*d*d*d = 1, c*d*d*d*d*d*e*e*e = 1>;
> f, G<a,b,c,d,e> := IsAutomaticGroup(F);
> G;
An automatic group.
Generator Ordering = [ a, a^-1, b, b^-1, c, c^-1, d, d^-1, e, e^-1 ]
The second word difference machine has 41 states.
The word acceptor has 42 states.
> print a*d;
d^-1
> print a/(d^-1);
d^-1
> print c*d^5*e^2;
e^-1
> print a^b, b^-1*a*b;
a a
> print (a*d)^-2, Inverse(a*d)^2;
a^-1 a^-1
> print c^-1*d^-1*c*d eq (c,d);
true
> print IsIdentity(b*d^3);
true
> print #(c*d*d*d*d*d*e*e);
1
In this section we describe functions which allow the user to enumerate
various sets of elements of an automatic group G.
A random word of length at most n in the generators of G.
A random word (of length at most the order of G) in the generators of G.
Rep(G) : GrpAtc -> GrpAtcElt
An element chosen from G.
Search: MonStgElt Default: "DFS"
Create the set of words, w, in G with a ≤ length(w) ≤b.
If Search is set to "DFS" (depth-first search) then words
are enumerated in lexicographical order. If Search is
set to "BFS" (breadth-first-search) then words are enumerated in
lexicographical order for each individual length
(i.e. in short-lex order). Depth-first-search is marginally quicker.
Since the result is a set the words may not appear in the resultant
set in the search order specified (although internally they
will be enumerated in this order).
Search: MonStgElt Default: "DFS"
Create the set of words that is the carrier set of G.
If Search is set to "DFS" (depth-first search) then words
are enumerated in lexicographical order. If Search is
set to "BFS" (breadth-first-search) then words are enumerated in
lexicographical order for each individual length
(i.e. in short-lex order). Depth-first-search is marginally quicker.
Since the result is a set the words may not appear in the resultant
set in the search order specified (although internally they
will be enumerated in this order).
Search: MonStgElt Default: "DFS"
Create the sequence S of words, w, in G with a ≤ length(w) ≤b.
If Search is set to "DFS" (depth-first search) then words
will appear in S in lexicographical order. If Search is
set to "BFS" (breadth-first-search) then words will appear in S in
lexicographical order for each individual length
(i.e. in short-lex order). Depth-first-search is marginally quicker.
Search: MonStgElt Default: "DFS"
Create a sequence S of words from the carrier set of G.
If Search is set to "DFS" (depth-first search) then words
will appear in S in lexicographical order. If Search is
set to "BFS" (breadth-first-search) then words will appear in S in
lexicographical order for each individual length
(i.e. in short-lex order). Depth-first-search is marginally quicker.
We construct the group D 22, together with a representative
word from the group, a random word and a random word of length at most 5
from the group, and the set of elements of the group.
> FG<a,b,c,d,e,f> := FreeGroup(6);
> F := quo< FG | a*c^-1*a^-1*d = 1, b*f*b^-1*e^-1 = 1,
> c*e*c^-1*d^-1 = 1, d*f^-1*d^-1*a = 1,
> e*b*e^-1*a^-1 = 1, f*c^-1*f^-1*b^-1 = 1 >;
> SetVerbose("KBMAG", 1);
> f, G<a,b,c,d,e,f> := IsAutomaticGroup(F);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#System is confluent.
#Halting with 41 equations.
#First word-difference machine with 16 states computed.
#Second word-difference machine with 17 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 6 states computed.
#General multiplier with 58 states computed.
#Validity test on general multiplier succeeded.
#Checking inverse and short relations.
#Axiom checking succeeded.
> Representative(G);
Id(G)
> Random(G);
a*c;
> Random(G, 5);
a * b
> Set(G);
{ a * d * b, a * b, a * b * e, a * c, a * d, d * b, b * e,
a * b * a, a * b * d, b * a, a * c * e, Id(G), b * d, c * e,
e, f, a, a * e, b, c, a * f, d }
> Seq(G : Search := "BFS");
[ Id(G), a, b, c, d, e, f, a * b, a * c, a * d, a * e, a * f,
b * a, b * d, b * e, c * e, d * b, a * b * a, a * b * d,
a * b * e, a * c * e, a * d * b ]
For a general description of homomorphisms, we refer to chapter MAPPINGS.
This section describes some special aspects of homomorphisms whose domain or
codomain is an automatic group.
Groups in the category GrpAtc currently are accepted as codomains only
in some special situations. The most important cases in which an automatic
group can be used as a codomain are group homomorphisms whose
domain is in one of the categories GrpFP, GrpGPC, GrpRWS
or GrpAtc.
Returns the homomorphism from the automatic group A to the group G defined
by the expression S which can be the one of the following:
- (i)
- A list, sequence or indexed set containing the images of the n
generators A.1, ..., A.n of A. Here, the i-th element of S is
interpreted as the image of A.i, that is, the order of the elements in S is
important.
- (ii)
- A list, sequence, enumerated set or indexed set, containing n
tuples < xi, yi > or arrow pairs xi -> yi,
where xi is a generator of A and yi∈G (i=1, ..., n) and the set
{x1, ..., xn} is the full set of generators of A. In this case,
yi is assigned as the image of xi, hence the order of the elements in
S is not important.
It is the user's responsibility to ensure that the provided generator images
actually give rise to a well-defined homomorphism. No checking is performed
by the constructor.
Note that it is currently not possible to define a homomorphism by assigning
images to the elements of an arbitrary generating set of A.
Primes: SeqEnum Default: [ ]
Compute the growth function of the word acceptor automaton associated
with G. The growth function of a DFA, A, is the quotient of
two integral polynomials in a single variable x. The coefficient of xn
in the Taylor expansion (about 0) of this quotient is equal to the number of
words of length n accepted by A. That is, the result is a closed form
for this generating function.
The algorithm is due to Derek Holt. The Primes parameter is no longer
used, but is kept for backward compatibility. It may be removed in future
releases.
We construct a dihedral group of order 10 and compute the
growth function of its word acceptor. As the group is finite, the
result will be a polynomial.
Note here that the R!f is
only necessary to get pretty printing, specifically to ensure that
f is printed in the variable x.
> R<x> := RationalFunctionField(Integers());
> FG<a,b> := FreeGroup(2);
> Q := quo< FG | a^5, b^2, a^b = a^-1>;
> G := AutomaticGroup(Q);
> f := GrowthFunction(G);
> R!f;
2*x^3 + 4*x^2 + 3*x + 1
Now we take as example an infinite dihedral group. The group is infinite,
so the result cannot be polynomial. We then extract the coefficients of the
growth function for word lengths 0 to 14.
> FG2<d,e> := FreeGroup(2);
> Q2 := quo<FG2| e^2, d^e = d^-1>;
> G2 := AutomaticGroup(Q2);
> f2 := GrowthFunction(G2);
> R!f2;
(-x^2 - 2*x - 1)/(x - 1)
> PSR := PowerSeriesRing(Integers():Precision := 15);
> Coefficients(PSR!f2);
[ 1, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|