2. General remarks
  
  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.
  
  
  2.1 Commutators and the Lower Central Series
  
  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.
  
  
  2.2 Nilpotent groups
  
  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.
  
  
  2.3 Nilpotent presentations
  
  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.
  
  
  2.4 A sketch of the algorithm
  
  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]
  
  
  2.5 Identical Relations
  
  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.
  
  
  2.6 Expression Trees
  
  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.
  
  ---------------------------  Example  ----------------------------
    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 ) ] )
      
  ------------------------------------------------------------------
  
  
  2.7 A word about the implementation
  
  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
  \]
  
  
  2.8 The input format of the standalone
  
  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).