The ANU Nilpotent Quotient Program

• Nilpotent quotients
• About this version
• How to install the ANU NQ
• How to use the ANU NQ
• The input format for presentations
• An example
• Some remarks about the algorithm
• Improvements planned for further versions
• Acknowledgments

Nilpotent quotients

The lower central series of a group G can be defined inductively as

G is said to have nilpotency class c if c is the smallest non-zero integer such that G_c+1 = 1. If N is a normal subgroup of G and G/N is nilpotent, then N contains G _i for some positive integer i. G has infinite nilpotent quotients if and only if G/G₂, the largest abelian factor group of G, is infinite. The i-th factor G_i/G _i+1 of the lower central series is generated by the elements [g,h]G_i+1, where g runs through a set of representatives of G/G₂ and h runs through a set of representatives of G_i-1/G_i.

Any finitely generated nilpotent group is polycyclic and, therefore, has a subnormal series with cyclic factors. Such a subnormal series can be used to represent the group in terms of a polycyclic presentation. The ANU NQ computes successively the factor groups modulo the terms of the lower central series. Each factor group is represented by a special form of polycyclic presentation, a nilpotent presentation, that makes use of the nilpotent structure of the factor group. Chapters 9 and 11 of the book by C.C. Sims, "Computing with finitely presented groups", discuss polycyclic presentations and a nilpotent quotient algorithm. A description of this implementation is contained in

Werner Nickel
"Computing Nilpotent Quotients of Finitely Presented Groups"
Dimacs Series in Discrete Mathematics and Theoretical Computer Science, Volume 25, pp 175-191, 1996.
Back to the top

About this version

This directory contains Version 1.2 of the Australian National University Nilpotent Quotient Program (ANU NQ), an implementation of a nilpotent quotient algorithm in C. This implementation has been developed in a Unix environment and Unix is currently the only operating system supported. It runs on a number of different Unix versions, e.g. SunOS and Ultrix. An earlier version of the ANU NQ is also available as part of quotpic (Derek F. Holt, Sarah Rees: A graphics system for displaying finite quotients of finitely presented groups. DIMACS Workshop on Groups and Computation, AMS-ACM 1991).

This directory contains the following directories and files:

• README
• History
• RCS
• examples
• gap
• src
• testNq

The file `README' is (what a surprise!) this file. The directory `examples' contains a collection of example input files for the nilpotent quotient program. The directory `gap' contains the GAP interface to the ANU NQ. The program system GAP was developed by Martin Schoenert et al. at the RWTH Aachen, Germany, until July 1997. It is now looked after by the School of Mathematical and Computational Sciences at the University of St Andrews. The directory `src' contains the source code for the ANU NQ and the file `testNq' can be run to test if the installation of the ANU NQ is working properly (see next section). It uses the groups in the directory `examples'.
Back to the top

How to install the ANU NQ

The installation of the program is easy. However, it requires the Berkeley compatible interface of the GNU multiple precision library (GNU MP). GNU is the Free Software Foundation's collection of UNIX compatible software. If this library is not available on your system, it has to be installed first. A copy of GNU MP can be obtained via anonymous ftp from many file servers around the world.

Once GNU MP has been installed, go into the directory `src' and edit the file `Makefile'. It contains the following lines:

##    The   following  two lines   define  the directory with  the GNU
##    multiple  precision   library (GNULIB)   and  the directory that
##    contains the corresponding include files (GNUINC).
GNULIB = /usr/local/lib/
GNUINC = /usr/local/include

The definition of `GNULIB' has to be changed to the directory where the GNU MP library is on your system. The definition of `GNUINC' has to be changed to the directory on your system that contains the corresponding include files.

After this change you start the compilation of the ANU NQ by typing make.

A compiled version of the program named `nq' is then placed into the directory `src'. If there are any warnings or even fatal error messages during the compilation process, please send a copy to the address at the end of this document together with information about your operating system, the compiler you used and any changes you might have made to the source code. I will have a look at your problems and try to fix them.

After the compilation is finished you can check if the ANU NQ is running properly on your system. Go back to the parent directory and type testNq

The file testNq runs some computations and compares their output with the output files in the directory `examples'. If testNq reports any errors, please follow the instruction that testNq prints out.
Back to the top

How to use the ANU NQ

If you start the ANU NQ by typing nq -X

you will get the following message:

    unknown option: -X
    usage: nq [-a] [-M] [-d] [-g] [-v] [-s] [-f] [-c] [-m]
              [-t <n>] [-l <n>] [-r <n>] [-n <n>] [-e <n>]
              [-y] [-o] [-p] [-E] [<presentation>] [<class>]

All parameters in square brackets are optional. The parameter <presentation> has to be the name of a file that contains a finite group presentation for which a nilpotent quotient is to be calculated. This file name must not start with a digit. If it is not present, nq will read the presentation from standard input. The parameter <class⁢ restricts the computation of the nilpotent quotient to at most that (nilpotency) class, i.e. the program calculates the quotient group of the (c+1)-th term of the lower central series. If <class> is omitted, the program computes successively the factor groups of the lower central series of the given group. If there is a largest nilpotent quotient, i.e., if the lower central series becomes constant, the program will eventually terminate with the largest nilpotent quotient. If there is no largest nilpotent quotient, the program will run forever (or more precisely will run out of resources). On termination the program prints a nilpotent presentation for the nilpotent quotient it has computed.

The options -l, -r and -e can be used to enforce Engel conditions on the nilpotent quotient to be calculated. All these options have to be followed by a positive integer <n>. Their meaning is the following:

-n <k>

This option forces the first k generators to be left or right Engel element if also the option -l or -r (or both) is present. Otherwise it is ignored.

-l <n>

This forces the first k generators g_1,...,g_k of the nilpotent quotient Q to be left n-Engel elements, i.e., they satisfy [x,...,x,g_i] = 1 (x occurring n-times) for all x in Q and 1 <= i <= k. If the option -n is not used, then k = 1.

-r <n>

This forces the first k generators g_1,...,g_k of the nilpotent quotient Q to be right n-Engel elements,i.e., they satisfy [g_i,x,..,x] = 1 (x occurring n-times) for all x in Q and 1 <= i <= k. If the option -n is not used, then k = 1.

-e <n>

This enforces the n-th Engel law on Q, i.e., [x,y,..,y] = 1 (y occurring n-times) for all x,y in Q.

-t <n>

This option specifies how much CPU time the program is allowed to use. It will terminate after <n> seconds of CPU time. If <n> is followed (without space) by one of the letters m, h or d, <n> specifies the time in minutes, hours or days, respectively.

The other options have the following meaning. Care has to be taken when the options -s or -c are used since the resulting nilpotent quotient need NOT satisfy the required Engel condition. The reason for this is that a smaller set of test words is used if one of these two options are present. Although this smaller set of test words seems to be sufficient to enforce the required Engel condition, this fact has not been proven.

-a

For each factor of the lower central series a file is created in the current directory that contains an integer matrix describing the factor as abelian group. The first number in that file is the number of columns of the matrix. Then the matrix follows in row major order. The matrix for the i-th factor is put into the file <presentation>.abinv.<i>.

-p

toggles printing of the pc presentation for the nilpotent quotient at the end of a calculation.

-s

This option causes the program to check only semigroup words in the generating set of the nilpotent quotient when an Engel condition is enforced. If none of the options -l, -r or -e are present, it is ignored.

-f

This option causes to check semigroup words in the generating set of the nilpotent quotient first and then all other words that need to be checked. It is ignored if the option -s is used or none of the options -l, -r or -e are present.

-c

This option stops checking the Engel law at each class if all the checks of a certain weight did not yield any non-trivial instances of the law.

-d

Switch on debug mode and perform checks during the computation. Not yet implemented.

-o

In checking Engel identities, instances are process in the order of increased weight. This flag reverses the order.

-y

Enforce the identities x^8 and [ [x1,x2,x3], [x4,x5,x6] ] on the nilpotent quotient.

-v

Switch on verbose mode.

-g

Produce GAP output. Presently the GAP output consists only of a sequence of integer matrices whose rows are relations of the factors of the lower central series as abelian groups. This will change as soon as GAP can handle infinite polycyclic groups.

-E

the *last* n generators are Engel generators. This works in conjunction with option -n.

-m

output the relation matrix for each factor of the lower central series. The matrices are written to files with the names 'matrix.' where <cl> is replaced by the number of the factor in the lower central series. Each file contains first the number of columns of the matrix and then the rows of the matrix. The matrix is written as each relation is produced and is not in upper triangular form.

-M

output the relation matrix before and after relations have been enforced. This results in two groups of files with names '<pres>.nilp.<cl>' and '<pres>.mult.<cl>' where <pres> is the name of the input files and <cl> is the class. The matrices are in upper triangular form.

The input format for presentations

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 | [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
    >

A presentation starts with '<' followed be 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 '|'. 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.
Back to the top

An example

Let G be the free group on two generators x and y. The input file (called free2.fp here) contains the following:

        < x, y | >

#
#    The ANU Nilpotent Quotient Program (Version 1.1d, 18 May 1994)
#    Calculating a nilpotent quotient
#    Input: free2.fp
#    Nilpotency class: 3
#    Program: nq     Machine: astoria
#
#    Calculating the abelian quotient ...
#    The abelian quotient has 2 generators
#        with the following exponents: 0 0
#
#    Calculating the class 2 quotient ...
#    Layer 2 of the lower central series has 1 generators
#          with the following exponents: 0
#
#    Calculating the class 3 quotient ...
#    Layer 3 of the lower central series has 2 generators
#          with the following exponents: 0 0
#


#    The epimorphism :
#    a|---> A
#    b|---> B


#    The nilpotent quotient :
    

#    Class : 3
#    Nr of generators of each class : 2 1 2

#    total runtime : 0 msec
#    total size    : 35900 byte

Most of the comments are fairly self-explanatory. One note of caution is necessary: The number of generators for each factor of the lower central series is not the minimal number possible but is the number of generators that the ANU NQ chose to use. This will be improved in one of the future version of the program. The epimorphism from the original group onto the nilpotent quotient is printed in a somewhat confusing way. The generators on the left hand side of the arrows correspond to the generators in the original presentation but are printed with different names. This will be fixed in one of the next version.
Back to the top

Some remarks about the algorithm

The implementation of the algorithm is fairly straight forward. The program uses a weighted nilpotent presentation with definitions to represent a nilpotent group. Calculations in the nilpotent group are done using a collector from the left without combinatorial collection. Generators for the c-th lower central factor are defined as commutators of the form [y,x], where x is a generator of weight 1 and y is a generator of weight c-1. Then the program calculates the necessary changes (tails) for all relations which are not definitions, runs through the consistency check and evaluates the original relations on the polycyclic presentation. This gives a list of words, which have to be made trivial in order to obtain a consistent polycyclic presentation representing a nilpotent quotient of the given finitely presented group. This list is converted into a integer matrix, which is transformed into upper triangular form using the Kannan-Bachem algorithm. The GNU multiple precision package is used for this.
Back to the top

Some improvements planned for further versions

On the agenda for future versions of the program are the following items :

• Use combinatorial collection
• Improve the speed of checking the Engel conditions
• Avoid consistency tests used for tail computations
• Speed up elimination of generators and extending the pc pres
• Use column permutations in the Kannan-Bachem algorithm
• Add more comments to the code
• Use the mpz-interface of the GNU multiple precision package
• Find a more satisfying solution for generating sets for each central factor.
• Multiple precision integers as exponents of generators
• Better control over the output
• Output computed nilpotent quotient if the program times out

Acknowledgments

Further development of this program was done while the author was supported by the DFG-Schwerpunkt-Projekt "`Algorithmische Zahlentheorie und Algebra"'.