In this chapter we define notation used throughout this manual and recollect basic facts about nilpotent groups. We also provide some background information about the functionality implemented in this package.
The commutator of two elements h_1 and h_2 of a group G is the element h_1^-1h_2^-1h_1h_2 and is denoted by [h_1,h_2]. It satisfies the equation h_1h_2 = h_2h_1[h_1,h_2] and can be interpreted as the correction term that has to be introduced into a word if two elements of a group are interchanged. Iterated commutators are written in left-normed fashion: [h_1,h_2,...,h_n-1,h_n]=[[h_1,h_2,...,h_n-1],h_n].
The lower central series of G is defined inductively as gamma_1(G) = G, gamma_i(G) = [gamma_i-1(G),G] for i ge 2. Each term in the lower central series is a normal (even fully invariant) subgroup of G. The factors of the lower central series are abelian groups. On each factor the induced action of G via conjugation is the trivial action.
The factor gamma_k(G)/gamma_k+1(G) is generated by the elements [g,h]gamma_k+1(G), where g runs through a set of (representatives of) generators for G/gamma_2(G) and h runs through a set of (representatives of) generators for gamma_k-1(G)/gamma_k(G). Therefore, each factor of the lower central series is finitely generated if G is finitely generated.
If one factor of the lower central series is finite, then all subsequent factors are finite. Then the exponent of the k+1-th factor is a divisor of the exponent of the k-th factor of the lower central series. In particular, the exponents of all factors of the lower central series are bounded by the exponent of the first finite factor of the lower central series.
A group G is called nilpotent if there is a positive integer c such that all (c+1)-fold commutators are trivial in G. The smallest integer with this property is called the nilpotency class of G. In terms of the lower central series a group G not= 1 has nilpotency class c if and only if gamma_c(G) not= 1 and gamma_c+1(G) = 1.
Examples of nilpotent groups are finite p-groups, the group of unitriangular matrices over a ring with one and the factor groups of a free group modulo the terms of its lower central series.
Finiteness of a nilpotent group can be decided by the group's commutator factor group. A nilpotent group is finite if and only if its commutator factor group is finite. A group whose commutator factor group is finite can only have finite nilpotent quotient groups.
By refining the lower central series of a finitely generated nilpotent group one can obtain a (sub)normal series G_1>G_2>...>G_k+1=1 with cyclic (central) factors. Therefore, every finitely generated nilpotent group is polycyclic. Such a polycyclic series gives rise to a polycyclic generating sequence by choosing a generator a_i for each cyclic factor G_i/G_i+1. Let I be the set of indices such that G_i/G_i+1 is finite. A simple induction argument shows that every element of the group can be written uniquely as a normal word a_1^e_1... a_n^e_n with integers e_i and 0<= e_i<m_i for iin I.
From a polycyclic generating sequence one can obtain a polycyclic presentation for the group. The following set of power and commutator relations is a defining set of relations. The power relations express a_i^m_i in terms of the generators a_i+1,...,a_n whenever G_i/G_i+1 is finite with order m_i. The commutator relations are obtained by expressing [a_j,a_i] for j>i as a word in the generators a_i+1,...,a_n. If the polycyclic series is obtained from refining the lower central series, then [a_j,a_i] is even a word in a_j+1,...,a_n. In this case we obtain a nilpotent presentation.
To be more precise, a nilpotent presentation is given on a finite number of generators a_1,...,a_n. Let I be the set of indices such that G_i/G_i+1 is finite. Let m_i be the order of G_i/G_i+1 for iin I. Then a nilpotent presentation has the form
\[ \langle a,\ldots,a_n | a_i^{m_i} = w_{ii}(a_{i+1},\ldots,a_n) \mbox{ for } i\in I;\; [a_j,a_i] = w_{ij}(a_{j+1},\ldots,a_n) \mbox{ for } 1\leq i < j\leq n\rangle \]
Here, w_ij(a_k,...,a_n) denotes a group word in the generators a_k,...,a_n.
In a group given by a polycyclic presentation each element in the group can be written as a normal word a_1^e_1... a_n^e_n with e_i in Z and 0 <= e_i < m_i for i in I. A procedure called collection can be used to convert an arbitrary word in the generators into an equivalent normal word. In general, the resulting normal word need not be unique. The result of collecting a word may depend on the steps chosen during the collection procedure. A polycyclic presentation with the property that two different normal words are never equivalent is called consistent. A polycyclic presentation derived from a polycyclic series as above is consistent. The following example shows an inconsistent polycyclic presentation
\[\langle a,b\mid a^2, b^a = b^2 \rangle \]
as b = baa = ab^2a = a^2b^4 = b^4 which implies b^3=1. Here we have the equivalent normal words b^3 and the empty word. It can be proved that consistency can be checked by collecting a finite number of words in the given generating set in two essentially different ways and checking if the resulting normal forms are the same in both cases. See Chapter 9 of the book [C94] for an introduction to polycyclic groups and polycyclic presentations.
For computations in a polycyclic group one chooses a consistent polycyclic presentation as it offers a simple solution to the word problem: Equality between two words is decided by collecting both words to their respective normal forms and comparing the normal forms. Nilpotent groups and nilpotent presentations are special cases of polycyclic groups and polycyclic presentations. Nilpotent presentations allow specially efficient collection methods. The package Polycyclic provides algorithms to compute with polycyclic groups given by a polycyclic presentation.
However, inconsistent nilpotent presentations arise naturally in the nilpotent quotient algorithm. There is an algorithm based on the test words for consistency mentioned above to modify the arising inconsistent presentations suitably to obtain a consistent one for the same group.
The input for the ANU NQ in its simplest form is a finite presentation < X|R> for a group G. The first step of the algorithm determines a nilpotent presentation for the commutator quotient of G. This is a presentation of the class-1 quotient of G. Call its generators a_1,...,a_d. It also determines a homomorphism of G onto the commutator quotient and describes it by specifying the image of each generator in X as a word in the a_i.
For the general step assume that the algorithm has computed a nilpotent presentation for the class-c quotient of G and that a_1,...,a_d are the generators introduced in the first step of the algorithm. Furthermore, there is a map from X into the class-c quotient describing the epimorphism from G onto G/gamma_c+1(G).
Let b_1,...b_k be the generators from the last step of the algorithm, the computation of gamma_c(G)/gamma_c+1(G). This means that b_1,...b_k generate gamma_c(G)/gamma_c+1(G). Then the commutators [b_j,a_i] generate gamma_c+1(G)/gamma_c+2(G). The algorithm introduces new, central generators c_ij into the presentation, adds the relations [b_j,a_i] = c_ij and modifies the existing relations by appending suitable words in the c_ij, called tails, to the right hand sides of the power and commutator relations. The resulting presentation is a nilpotent presentation for the nilpotent cover of G/gamma_c+1(G). The nilpotent cover is the largest central extension of G/gamma_c+1(G) generated by d elements. It is is uniquely determined up to isomorphism.
The resulting presentation of the nilpotent cover is in general inconsistent. Consistency is achieved by running the consistency test. This results in relations among the generators c_ij which can be used to eliminate some of those generators or introduce power relations. After this has been done we have a consistent nilpotent presentation for the nilpotent cover of G/gamma_c+1(G).
Furthermore, the nilpotent cover need not satisfy the relations of G. In other words, the epimorphism from G onto G/gamma_c+1(G) cannot be lifted to an epimorphism onto the nilpotent cover. Applying the epimorphism to each relator of G and collecting the resulting words of the nilpotent cover yields a set of words in the c_ij. This gives further relations between the c_ij which leads to further eliminations or modifications of the power relations for the c_ij.
After this, the inductive step of the ANU NQ is complete and a consistent nilpotent presentation for G/gamma_c+2(G) is obtained together with an epimorphism from G onto the class-(c+1) quotient.
Chapter 11 of the book [C94] discusses a nilpotent quotient algorithm. A description of the implementation in the ANU NQ is contained in [N96]
Let w be a word in free generators x_1,...,x_n. A group G satisfies the relation w=1 identically if each map from x_1,...,x_n into G maps w to the identity element of G. We also say that G satisfies the identical relation w=1 or satisfies the law w=1. In slight abuse of notation, we call the elements x_1,...,x_n identical generators.
Common examples of identical relations are: A group of nilpotency class at most c satisfies the law [x_1,...,x_c+1]=1. A group that satisfies the law [x,y,...,y]=1 where y occurs n-times, is called an n-Engel group. A group that satisfies the law x^d=1 is a group of exponent d.
To describe finitely presented groups that satisfy one or more laws, we extend a common notation for finitely presented groups by specifying the identical generators as part of the generator list, separated from the group generators by a semicolon: For example
\[ \langle a,b,c; x,y | x^5, [x,y,y,y]\rangle \]
is a group on 3 generators a,b,c of exponent 5 satisfying the 3rd Engel law. The presentation above is equivalent to a presentation on 3 generators with an infinite set of relators, where the set of relators consists of all fifth powers of words in the generators and all commutators [x,y,y,y] where x and y run through all words in the generators a,b,c. The standalone programme accepts the notation introduced above as a description of its input. In GAP 4 finitely presented groups are specified in a different way, see NilpotentQuotient (3.1-1) for a description.
This notation can also be used in words that mix group and identical generators as in the following example:
\[ \langle a,b,c; x | [x,c], [a,x,x,x] \rangle \]
The first relator specifies a law which says that c commutes with all elements of the group. The second turns a into a third right Engel element.
An element a is called a right n-th Engel element or a right n-Engel element if it satisfies the commutator law [a,x,...,x]=1 where the identical generator x occurs n-times. Likewise, an element b is called an left n-th Engel element or left n-Engel element if it satisfies the commutator law [x,b,b,...b]=1.
Let G be a nilpotent group. Then G satisfies a given law if the law is satisfied by a certain finite set of instances given by Higman's Lemma, see [G59]. The ANU NQ uses Higman's Lemma to obtain a finite presentation for groups that satisfy one or several identical relations.
Expressions involving commutators play an important role in the context of nilpotent groups. Expanding an iterated commutator produces a complicated and long expression. For example,
\[ [x,y,z] = y^{-1}x^{-1}yxz^{-1}x^{-1}y^{-1}xyz. \]
Evaluating a commutator [a,b] is done efficiently by computing the equation (ba)^-1ab. Therefore, for each commutator we need to perform two multiplications and one inversion. Evaluating [x,y,z] needs four multiplications and two inversions. Evaluation of an iterated commutator with n components takes 2n-1 multiplications and n-1 inversions. The expression on the right hand side above needs 9 multiplications and 5 inversions which is clearly much more expensive than evaluating the commutator directly.
Assuming that no cancellations occur, expanding an iterated commutator with n components produces a word with 2^n+1-2^n-1-2 factors half of which are inverses. A similar effect occurs whenever a compact expression is expanded into a word in generators and inverses, for example (ab)^49.
Therefore, it is important not to expand expressions into a word in generators and inverses. For this purpose we provide a mechanism which we call here expression trees. An expression tree preserves the structure of a given expression. It is a (binary) tree in which each node is assigned an operation and whose leaves are generators of a free group or integers. For example, the expression [(xy)^2, z] is stored as a tree whose top node is a commutator node. The right subtree is just a generator node (corresponding to z). The left subtree is a power node whose subtrees are a product node on the left and an integer node on the right. An expression tree can involve products, powers, conjugates and commutators. However, the list of available operations can be extended.
Evaluation of an expression tree is done recursively and requires as many operations as there are nodes in the tree. An expression tree can be evaluated in a specific group by the function EvaluateExpTree (3.2-2).
A presentation specified by expression trees is a record with the components .generators and .relations. See section 3.2 for a description of the functions that produce and manipulate expression trees.
gap> RequirePackage( "nq" ); true gap> gens := ExpressionTrees( 2 ); [ x1, x2 ] gap> r1 := LeftNormedComm( [gens[1],gens[2],gens[2]] ); Comm( x1, x2, x2 ) gap> r2 := LeftNormedComm( [gens[1],gens[2],gens[2],gens[1]] ); Comm( x1, x2, x2, x1 ) gap> pres := rec( generators := gens, relations := [r1,r2] ); rec( generators := [ x1, x2 ], relations := [ Comm( x1, x2, x2 ), Comm( x1, x2, x2, x1 ) ] ) |
The ANU NQ is written in C, but not in ANSI C. I hope to make one of the next versions ANSI compliable. However, it uses a fairly restricted subset of the language so that it should be easy to compile it in new environments. The code is 64-bit clean. If you have difficulties with porting it to a new environment, let me know and I'll be happy to assist if time permits.
The program has two collectors: a simple collector from the left as described in [LS90] and a combinatorial from the left collector as described in [V90]. The combinatorial collector is always faster than the simple collector, therefore, it is the collector used by this package by default. This can be changed by modifying the global variable NqDefaultOptions (3.4-2).
In a polycyclic group with generators that do not have power relations, exponents may become arbitrarily large. Experience shows that this happens rarely in the computations done by the ANU NQ. Exponents are represented by 32-bit integers. The collectors perform an overflow check and abort the computation if an overflow occurred. In a GNU environment the program can be compiled using the `long long' 64-bit integer type. For this uncomment the relevant line in src/Makefile and recompile the program.
As part of the step that enforces consistency and the relations of the group, the ANU NQ performs computations with integer matrices and converts them to Hermite Normal Form. The algorithm used here is a variation of the Kanan-Bachem algorithm based on the GNU multiple precision package GNU MP [xxx]. Experience shows that the integer matrices are usually fairly sparse and Kanan-Bachem seems to be sufficient in this context. However, the implementation might benefit from a more efficient strategy for computing Hermite Normal Forms. This is a topic for further investigations.
As the program does not compute the Smith Normal Form for each factor of the lower central series but the Hermite Normal Form, it does not necessarily obtain a minimal generating set for each factor of the lower central series. The following is a simple example of this behaviour. We take the presentation
\[ \langle x, y | x^2 = y \rangle \]
The group is clearly isomorphic to the additive group of the integers. Applying the ANU NQ to this presentation gives the following nilpotent presentation:
\[ \langle A,B | A^2 = B, [B,A] \rangle \]
A nilpotent presentation on a minimal generating set would be the presentation of the free group on one generator:
\[ \langle A | \; \rangle \]
The input format for finite presentations resembles the way many people write down a presentation on paper. Here are some examples of presentations that the ANU NQ accepts:
< a, b | > # free group of rank 2
< a, b, c; x, y |
[a,b,c], # a left normed commutator
[b,c,c,c]^6, # another one raised to a power
a^2 = c^-3*a^2*c^3, # a relation
a^(b*c) = a, # a conjugate relation
(a*[b,(a*c)])^6, # something that looks complicated
[x,y,y,y,y], # an identical relation
[c,x,x,x,x,x] # c is a fifth right Engel element
>
A presentation starts with '<' followed by a list of generators separated by commas. Generator names are strings that contain only upper and lower case letters, digits, dots and underscores and that do not start with a digit. The list of generator names is separated from the list of relators/relations by the symbol '|'. The list of generators can be followed by a list of identical generators separated by a semicolon. Relators and relations are separated by commas and can be mixed arbitrarily. Parentheses can be used in order to group subexpressions together. Square brackets can be used in order to form left normed commutators. The symbols '*' and '^' can be used to form products and powers, respectively. The presentation finishes with the symbol '>'. A comment starts with the symbol '#' and finishes at the end of the line. The file src/presentation.c contains a complete grammar for the presentations accepted by the ANU NQ.
Typically, the input for the standalone is put into a file by using a standard text editor. The file can be passed as an argument to the function NilpotentQuotient (3.1-1). It is also possible to put a presentation in the standalone's input format into a string and use the string as argument for NilpotentQuotient (3.1-1).
generated by GAPDoc2HTML