The ANU Nilpotent Quotient Program ================================== Table of contents ----------------- 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 Some improvements planned for further versions Acknowledgements Contact addresses Nilpotent quotients ------------------- The lower central series G_i of a group G can be defined inductively as G_0 = G, G_i = [G_(i-1),G]. G is said to have nilpotency class c if c is the smallest non-zero integer such that G_c = 1. If N is a normal subgroup of G and G/N is nilpotent, then N contains G_i for some non-negative integer i. G has infinite nilpotent quotients if and only if G/G_1 is infinite. The i-th (i > 1) factor G_(i-1)/G_i of the lower central series is generated by the elements [g,h]G_i, where g runs through a set of representatives of G/G_1 and h runs through a set of representatives of G_(i-2)/G_(i-1). 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", discusses polycyclic presentations and a nilpotent quotient algorithm. A description of this implementation is contained in Werner Nickel (1996) "Computing Nilpotent Quotients of Finitely Presented Groups" in Dimacs Series in Discrete Mathematics and Theoretical Computer Science, Volume 25, pp 175-191. About this version ------------------ This directory contains Version 1.3 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 this file History a history of changes to the program ToDo what else needs to be done configure run this to compile NQ and then run `make' configure.in configure was made from this file by autoconf Makefile.in a Makefile is created from this when you run configure cnf/ scripts used by configure examples/ a suite of test examples src/ the source code gap/ the GAP interface doc/ documentation of the GAP interface init.g part of the GAP interface read.g part of the GAP interface testNq a shell script to test the compiled program How to install the ANU NQ ------------------------- The installation of the program is easy. However, it requires 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, for example: prep.ai.mit.edu:/pub/gnu/gmp-2.0.2.tar.gz It is likely that there is an ftp server closer to you that carries GNU MP. You start compiling NQ by running the configure script: ./configure Among other things it will tell you whether it succeeded in locating the GNU MP library and the corresponding include files. If configure reports no problems, you prcoeed by typing make If it tells you that it could not find the GNU MP include files or the GNU MP libraries, you have to run make with additional parameters. For example, if you have installed GNU MP yourself in your home directory, you would type something like the following make GNU_MP_INC=/home/me/gmp-2.0.2 GNU_MP_LIB=/home/me/gmp-2.0.2 A compiled version of the program named `nq' is then placed into the directory `bin/<complicated name>'. The <complicated name> component encodes the operating system and the compiler used. This allows you to compile NQ on several architectures sharing the same files system. 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. Simply 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. 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 semiwords 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.<cl>' 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. 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 | > Computing the class 3 quotient with the ANU NQ by typing nq free2.fp 3 produces the following output: # # 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 : <A,B,C,D,E | B^A =: B*C, B^(A^-1) = B*C^-1*D, C^A =: C*D, C^(A^-1) = C*D^-1, C^B =: C*E, C^(B^-1) = C*E^-1 > # 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. 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. 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 Acknowledgements ---------------- The development of this program was started while the author was supported by an Australian National University PhD scholarship and an Overseas Postgraduate Research Scholarship. Further development of this program was done while the author was supported by the DFG-Schwerpunkt-Projekt "`Algorithmische Zahlentheorie und Algebra"'. Contact addresses ----------------- Comments and suggestions are very welcome, my email address is nickel@mathematik.tu-darmstadt.de Werner Nickel Fachbereich Mathematik, AG 2 TU Darmstadt Schlossgartenstr. 7 64289 Darmstadt Germany