Vector Enumeration Programs, Version 3.04

Copyright © 1993 Steve Linton

Vector Enumeration
******************

This is the manual for version 3.04 of my vector enumeration programs me, qme and zme. These programs are distributed free of charge for non-commercial use, and there is NO WARRANTY WHATSOEVER.

This document does not describe the underlying mathematics, which are described in the papers referred to later, but describes the operation of the programs.

Introduction
************

The vector enumeration algorithm for fields is described in the papers Constructing Matrix Representations of Finitely Presented Groups (J. Symbolic Computation (12) 1991) and On Vector Enumeration (to appear in the Journal of Linear Algebra and Applications). The me and qme programs implement this algorithm, me for prime fields of order less than 256 and qme for the rational numbers. The zme program implements an extended algorithm which works over principle ideal rings, for the special case of the integers. The extended algorithm will be described in a future publication.

This document describes the installation and use of these three programs, the formats of input and output files and the various options which control the execution. Some notes on the structure of the programs is also included.

In On Vector Enumeration, an application of the algorithm to constructing quotients of algebra representations is described. These programs include a special option -Q to read an input format suited to that application and proceed accordingly.

What's New
==========

What's New in Version 3.04
--------------------------

There are a number of changes in version 3.04. Several bugs were fixed, in particular one relating to meat-axe format output. Thanks to Jurgen Mueller for spotting this one and to Thomas Breuer for reporting it.

The -L command line option was added at this release, to allow logging information to be preceded by a comment designator.

The runtime in milliseconds was added to the output in several of the formats. This change should not break any reasonable program using the output.

Finally, a new Makefile is added, suitable for most make programs. This supllies standard options for building the system in a range of environments. The old Makefile, which retains some advantages for development (well I like it anyway), is renamed GNUmakefile.

What's New in Versions 3.02 and 3.03
------------------------------------

These versions (3.02 was never released) contain bug fixes relating to the integer vector enumeration program zme and changes to some undocumented features relating to the forthcoming GAP interface.

The zme bugs could cause a crash or improper non-termination.

What's New in Version 3.01
--------------------------

This version is a bug-fix version. The main bug fixed at this release is that under certain circumstances information could be lost during look-ahead, resulting in the output module being a proper pre-image of the correct module.

The fix for this problem involves allowing some definitions to be made, even during look-ahead. When the -t option see Limit Options is used to limit the total number of dimensions, a proportion of the limit is allocated for these critical definitions. This proportion can be changed by a new form of the -t option.

What's New in Version 3
-----------------------

  * The zme program is completely new in this version.

  * The quot quotient-constructing program has been merged with me and corresponding functionality added to qme and zme. See Input File Options and Input for Quotient Construction.

  * A number of internal changes have improved performance for most examples, sometimes dramatically.

  * The input format has been enriched in a number of ways see Input Formats and the error handling and reporting in the parser has been greatly enhanced see Logging and Error Message Options.

  * Three new output formats have been added: one for output to be read into AXIOM and two formats intended to be simply and quickly read by special-purpose programs. See Output Formats and Output Options.

  * A special option has been added to indicate that all the generators commute with one another, so that the module constructed will be a quotient of a polynomial ring. See Input File Options.

  * All the programs have been combined into a single set of sources. See The Source Code.

  * A number of new options have been added to control execution and limit the module dimension and the run time. See Limit Options

  * A new option has been added to override the characteristic given in the presentation file. See Input File Options.

  * A new options has been added to suppress the automatically generated relations for non-invertible generators.

  * Early-closing is now disabled by default, in the interests of mathematical accuracy. It can be re-enabled using the -e option. See Strategic Options.

Installation
************

Installation Procedure
======================

Since you're reading this manual you have probably already obtained the vector enumeration package and unpacked it from the compressed distribution.  Just for completeness, or for getting a later version, the software is available from me, Steve Linton (sal@cs.stand.ac.uk), or by anonymous FTP from galois.maths.qmw.ac.uk. It consists of just one file nme.tar.Z (there may also be nme.tar.z and/or nme.zoo). The file nme.README is a copy of the README file contained in the distribution.

You should create a new directory the nme home directory into which to unpack the distribution which will then create subdirectories ./ve, ./rat, ./int, ./docs and ./examples. The first three contain only GNUmakefiles, ./docs contains this TeXInfo file and ./examples contains some input files for testing. The current directory contains the C and Bison source files, the master Makefile and GNUmakefile and the shell script build.sh.

There are three alternative ways of compiling the programs. Simple compilation should suffice for most users.

Simple Compilation
------------------

Users not intending to modify the programs or to compile them for multiple architectures in the same directory hierarchy should use simple compilation. Simply change to the nme home directory and:

 1. Edit the shell script build.sh to:

       * Set the correct name for the C compiler (probably cc or gcc).

       * Set the system flags to avoid problems with you compiler library and header files. See Makefile for details of this.

       * Set the compiler, pre-processor and linker flags so that the compiler will find the GMP libraries and include files see Pre-requisites and will suitably optimize the programs.

       * Include the C version of alloca if it is not provided by your system (most BSD systems provide it, most System V systems do not).

       * Comment out appropriate sections of the script if you do not need all of the programs me, qme and zme. If you need only me, then you needn't worry about GMP.

 2. Type ./build.sh.

 3. Cross your fingers.

Assuming everything works, you will end up with the three executable programs in the bin subdirectory of the nme home directory. They may be moved to any convenient location.

General Installation
--------------------

If you plan to develop enhancements to the programs, or wish to compile them for multiple architectures then you will need to install the package completely. You can do this either using the Makefile, mainly prepared for when the package is installed as a GAP share library, or using the GNUmakefile. For the latter you will need version 3.63 or later of GNU make. It will also be simpler if you have a C compiler with the -M option to prepare dependency lists automatically.

General installation and simple installation should not be done in the same directory, as they use subdirectories differently.

Using GNU Make
..............

For general installation with GNU make you will need to arrange to have an environment variable ARCH set to some convenient name for the current hardware architecture. I do this with a line

     setenv ARCH `arch`

in my .cshrc file, and a small shell script arch that uses the hostname to decide what type of computer I am using. On Sun systems arch is a system command.

You should then create a subdirectory bin of the nme home directory. For each architecture XXX that is likely to be of interest you should also create subdirectories XXX of the bin, ve, rat and int subdirectories of the nme home directory.

You should then edit the file Makefile.inc in the nme home directory and set the C compiler, and compiler, linker and pre-processor flags suitably.

Assuming that your command to call GNU make is gmake, running gmake in the nme home directory should make all three programs, while running it in ve will make me, in rat will make qme and running it in int will make zme. The binaries will be stored in bin/$ARCH, which can conveniently be included in your path, and separate directories will be used for the object files for each architecture, so that they can be kept independently up to date.

Using the GAP Makefile
......................

To use Martin Schoenert's ingenious Makefile to build the package, edit Makefile in the nme home directory and set the variables INCDIRGMP and LIBDIRGMP appropriately for your system. Then type make <option>, where OPTION is made up in the usual GAP way. For a list of options just type make.  By default this Makefile only makes me and qme, as zme is not used in the GAP share library. To make zme as well, edit the dependencies of the target all.

This will make the executables as bin/me.exe, bin/qme.exe and (if you edited the makefile appropriately) bin/zme.exe. These will be invoked by the scripts which are supplied as bin/me, bin/qme and bin/zme. If you wish to install the package for use on multiple hardware architectures, you should move the executables to (for example) bin/me.sun and replace the script with one that decides which executable to use.

Note that apart from choosing a C compiler, the choice of OPTION to make only affects compilation of one function: RunTime, in the file me.c. If you are compiling the software on some system not catered for in the Makefile, you should only need to tweak this function to make everything work.

Compile-time options
--------------------

There are three compile-time options which can be controlled by editing the file me.h in the distribution. They are

DEBUG
     When the symbol DEBUG is defined many additional consistency checks and validations are included in the code. Also, the memory allocation routines in myalloc.c, which check for freeing pointers not allocated, overwrite freed memory to prevent access to it and so on, are used. Setting DEBUG slows the program down substantially and increases the size of the compiled code.

SCRUT
     This controls compilation of the scrutinize feature. If SCRUT is selected and enabled with the -s option on the command line then the calculation performed will be checked frequently against a correct answer read in. See Debugging Options. If SCRUT is specified at compile-time but not enabled from the command line there is a small loss of performance as the checks must be bypassed at run-time.

LOGGING
     This controls compilation of the code to produce logging and diagnostic messages. If LOGGING is defined at compile-time, then messages reporting progress will be output, under the control of the options described in Logging and Error Message Options. If logging messages are not needed a small gain in speed, and a rather larger reduction in code size can be achieved by not defining LOGGING at compile-time.

By default, LOGGING is defined, but DEBUG and SCRUT are not.

Pre-requisites
==============

The me program is self-contained, but qme and zme require the GMP multiple-precision arithmetic library. Specifically, they require version 1.2.99 or later of the library. This is available by anonymous FTP from sics.se.

The makefiles supplied with the programs make use of non-standard features of GNU make version 3.63 and will not work with most other make programs or with earlier versions of GNU make. Scripts are supplied to build the programs from scratch see Simple Compilation, but anyone wishing to work on these programs will probably need GNU make see General Installation.

The input parser input.tab.c is prepared using the GNU parser generator bison from the grammar file input.y. If you wish to change the parser in any way you will need to obtain bison. The supplied parser was prepared with bison version 1.18.

In order to format and read this manual you will need version 2.16 of the TeXInfo package and either TeX or GNU emacs. Alternatively contact me and I will send you a DVI or PostScript file.

Input Formats
*************

A Presentation File
===================

The basic format of the presentation file is

     CHARACTERISTIC . GENERATORS . GENERATORS NOT KNOWN TO BE INVERTIBLE . GENERATORS NOT KNOWN TO BE INVOLUTIONS . SUBMODULE GENERATORS . RELATIONS .

Anything after the final . is not read in by the program. Accordingly comments may appear here.

Characteristic
--------------

The characteristic is a non-negative integer and must always be present. For me it must be a prime number less than 256, and indicates the characteristic of the prime field over which the calculation will be performed. For qme or zme the characteristic must be 0.

The -C option may be used to override the characteristic specified in the presentation file (which must still be given, but will not be checked). See Input File Options.

Generators
----------

The GENERATORS part of the presentation defines the names which will be used for the generators of the algebra being constructed. These names must each be of one of two types:

  * Single capital letters such as A.

  * Strings of one or more lower-case letters such as a or xyz.

Lower-case generator names must be separated by a comma, a semi-colon or whitespace.

The following specifications all define three generators A, B and C:

     ABC
     A,B,C
     A B;C,
     AB C

On the other hand, the specification abc defines one generator called abc. To define three generators a, b and c a specification such as a b c, a,b,c or a b;c is needed.

Once the generators are defined a longest-match scanner is constructed to read strings of generator names. This is then used to read the GENERATORS NOT KNOWN TO BE INVERTIBLE and GENERATORS NOT KNOWN TO BE INVOLUTIONS sections of the presentation (and also used while reading the submodule generators and relations).

Providing no generator is an initial substring of another (which is very bad practice) no separators should be needed in GENERATORS NOT KNOWN TO BE INVERTIBLE or GENERATORS NOT KNOWN TO BE INVOLUTIONS, although they might add readability.

By default every generator is assumed to be an involution, that is for a generator X, the relation XX = 1 is assumed. This assumption can be overridden by including the generator in one of the lists GENERATORS NOT KNOWN TO BE INVERTIBLE or GENERATORS NOT KNOWN TO BE INVOLUTIONS. If a generator X is included in the first list then the program will make no assumptions about a multiplicative inverse of X. If a generator X is included in the second list then the program will add an extra generator X^-1 and assume the relation XX^-1 = 1.

It is an error for a generator to appear in both lists.

Either of these lists may have the special form *, which indicates that all generators are non-invertible or not involutions.

Thus, for example a module for the free algebra on generators a, b and c would be specified by:

     CHARACTERISTIC. a,b,c.abc..SUBMODULE GENERATORS.RELATIONS.

or

     CHARACTERISTIC. a,b,c.*..SUBMODULE GENERATORS.RELATIONS.

while a module for the free group on the same generators would be given by:

     CHARACTERISTIC. a,b,c..*.SUBMODULE GENERATORS.RELATIONS.

and a module for the free product of three copies of the cyclic group of order two by:

     CHARACTERISTIC. a,b,c...SUBMODULE GENERATORS.RELATIONS.

Relations
---------

The RELATIONS section of the presentation contains the relations of the algebra to be constructed (apart from any relations implied by the generators being invertible of involutions). It may be empty; if not then it consists of two parts, separated by a colon.

Group Type Relations
....................

The first part contains ``group type'' relators. These are products of invertible generators which are equal to 1 in the algebra to be constructed. These can be handled more efficiently than general (algebra) relations, so relations that are of this kind should be given in this section. It is an error for non-invertible generators to appear in this section.

The following constructions are available to write these products (called GROUP WORDS)

  * W1 [WHITESPACE] W2 denotes the product of group word W1 and group word W2. The WHITESPACE is only needed if there is ambiguity in parsing the generator names. For example if a, b and ab were all generators then ab would represent the generator ab, while a b represented the product of a and b.

  * W1*W2 is equivalent to the product W1W2.

  * W~ denotes the inverse of group word W.

  * WN denotes the Nth power of group word W. N must be a positive integer.

  * W1^W2 denotes the conjugate of group word W1 by W2.

  * [W1,W2] denotes the commutator of group words W1 and W2.

Conjugation, inversion and powering bind more tightly than multiplication, but parentheses may be used. Thus AB3 denotes the word ABBB, while (AB)3 denotes ABABAB.

Algebra Relations
.................

The second part of the relations section of the presentation contains more general relations.  These may be either elements of the free algebra generated by the generators, which are equal to 1 in the algebra being constructed, or equations between elements of the free algebra which are true in the algebra being constructed.

Any group word (see above) may be given as an element of the free algebra, as can an element of the underlying field given as an integer (or quotient of integers for qme). Elements of the free algebra can be combined by addition with +, subtraction (-) or multiplication (*). The usual rules of precedence apply and parentheses may be used to override them.

Weight Specifications
.....................

Any relator or relation in either part of the relations section may be followed by a weight specification. This takes the form <w> or <w1,w2> and affects the order in which the relations are used by the program, higher weights meaning that the relation will be used less or later. See Strategy for details of how the weights are applied.

In the first form w should be a positive integer and will be the weight used for that relation in both define and lookahead modes. In the second form w1 and w2 should both be positive integers. w1 will be the weight used in define mode and w2 in lookahead mode. For details of lookahead see Strategy.

Submodule Generators
--------------------

The submodule generator section may be of one of two forms. The simpler form may only be used when the module to be constructed is cyclic (more accurately when its presentation has just one generator). In this case the submodule generator section may take the same form as the relations section, consisting of group-type relators and algebra relations. Weight specifications may be present, but will be ignored.

Note that in this case the submodule generators will actually be forced to fix a vector in the module constructed, rather then annihilate it. Mathematically, the ``real'' submodule generators are obtained from those input by subtracting 1.

If the module is not cyclic then the more general form must be used. This begins with the number S of module generators enclosed in curly brackets {} followed by zero or more submodule generator entries. Each such entry may be of one of three forms:

Submodule Generators in Packed Form
...................................

A submodule generator in packed form consists of an S-tuple of elements of the free algebra, each given in the format specified in Algebra Relations, enclosed in parentheses and separated by commas.

Thus for example, the following presentation specifies the representation of the symmetric group S_3 obtained by identifying the fixed vectors of two copies of the natural permutation representation.

     0.AB..B.{2}(A-1,0),(0,A-1),(1+B+B2,-1-B-B2).B3,(AB)2:.

Submodule Generators in Sparse Form
...................................

For brevity, when there are many submodule generators, a generator may be given in sparse form. This consists of one or more pairs:

     MODULE GENERATOR NUMBER , FREE ALGEBRA ELEMENT

enclosed in square brackets. The MODULE GENERATOR NUMBER must be between 1 and S, and the pairs within a sparse form submodule generator must be given in order of MODULE GENERATOR NUMBER. Thus the first submodule generator in the above example could be rewritten [1,A-1].

Universal Submodule Generators
..............................

Finally, a series of submodule generators such as the first two in the example above may be abbreviated as a universal submodule generator. This takes the form [FIRST-LAST,X], where X is a free algebra element in the usual form, and represents the LAST - FIRST + 1 separate submodule generators [FIRST,X] through [LAST,X] inclusive. Equivalently, the universal submodule generator [FIRST-LAST,X] can be read as indicating that the free algebra element X annihilates module generators FIRST through LAST. The special case [1-S,X] can be further abbreviated to [*,X].

Thus the example can be abbreviated to

     0.AB..B.{2}[*,A-1],(1+B+B2,-1-B-B2).B3,(AB)2:.

Input for Quotient Construction
===============================

When the -Q option is given to me, qme or zme, the extension for input files changes from .pres to .qin and a completely different format of input is expected.

The input essentially specifies two things:

  * A vector space V and a set of matrices, which together specify a representation of a free algebra.

  * A set of vectors in V which generate a sub-module W under the action of the algebra. That is a set of vectors whose (iterated) images under the matrices span a subspace W of V.

This is achieved by an input file consisting six parts separated by whitespace:

 1. a specification of the characteristic as described in Characteristic;

 2. the dimension of the vector space V as an unsigned decimal integer;

 3. a string giving the generator names (used for printing and in some of the output formats). The names must be single characters, unseparated and terminated by whitespace;

 4. an unsigned integer giving the number of generators of W;

 5. the vectors which generate W;

 6. the matrices giving the action of the free algebra on V. For each basis vector B of V all the images of B under the matrices (ie the appropriate rows of all the matrices) are given, followed by all the images of the next basis vector.

The last two sections involve giving vectors as part of the input. These are normally given is a sparse format, consisting of zero or more pairs I, X(I) separated by commas and enclosed in square brackets. The indices I must be strictly increasing within a vector and the pair I, X(I) denotes that the Ith coefficient of the vector is X(I). Unspecified coefficients are taken as zero. Thus in a 5 dimensional space V, [1,1] denotes the vector (1,0,0,0,0), [5,-1] denotes (0,0,0,0,-1) and [1,1,2,2,3,3,4,4,5,5] denotes (1,2,3,4,5).

For me only, a packed format is also available for these vectors (this feature should be available in all three programs, and hopefully will be in some future release). This is given as a series of field elements separated by commas and enclosed in parentheses. There must be exactly as many field elements as the specified dimension of V.

Command Line Options
********************

The programs are controlled at run-time by options on the command line. There are no command line parameters except options. Options which do not take arguments may be combined, and, with a few exceptions, options may appear in any order. Thus me -g -i is equivalent to me -gi and to me -ig.

Strategic Options
=================

The vector enumeration algorithm has some intrinsic flexibility. The exact algorithm used is controlled by these options. These options have no effect when -Q is also present. See Strategy.

 -- Option: -a +|-|amount
     The -a option controls the amount of lookahead which takes place. The arguments + and - enable and disable lookahead (respectively), while a numeric argument AMOUNT specifies the how far ahead to look (in weights). See Strategy for the exact details of when lookahead takes place. The default is to look ahead 2 weights.

 -- Option: -e + | - | dim | min:max
     The option -e controls Early Closing. Early closing is said to occur when there are no blank entries in the program's table, so that the table represents a representation of the free algebra. In this situation the table is usually, though not always, correct, and it can be beneficial to stop the program and check correctness by other means.

     If the table is incorrect, one of the relations will fail to hold on it, and the correct table will be of smaller dimension.

     The argument + enables early-closing at any dimension.  The argument - disables early-closing completely. A single numeric argument DIM allows early-closing only at that dimension, while a pair of numeric arguments MIN and MAX separated by a colon, but not by any whitespace, allows early-closing between dimensions MIN and MAX inclusive.

Output Options
==============

On successful completion the programs may output their results in various formats, and with various details included or not. This group of options deals with selecting what information will be output, in what formats and to what files.

Options to control what information is output
---------------------------------------------

 -- Option: -P
 -- Option: -b
     The -P options controls the recording of pre-images.If this flag is present the program will keep track of the basis elements in terms of the module generators and words in the group (or algebra) generators. This information is printed out when the table is printed (ie when -vs2 is present) and in appropriately formatted output. This option has no effect when -Q is also present.

     The alternative name -b for this option is obsolete and is retained for compatibility.

 -- Option: -i
     The option enables output of Images. If this flag is present then the images of the module generators in the output module are included in the output.  This is only really relevant for non-cyclic modules as otherwise the generator is the first basis vector and can only be deleted if the output module is zero.

Options for Output Formats
--------------------------

These options control For the exact specification of the various output formats see Output Formats. The names of the files to which the variously formatted outputs are written are derived from a common STEM set with the -o option. Output File Names.

 -- Option: -c
     Enables Cayley format output. If this option is present a Cayley library containing the information will be written to STEM. At present the pre-image information will not be written even if -P is present. This may be fixed in a future release.

 -- Option: -g
     Enables GAP format output. If this option is present a file STEM.g will be written, suitable for reading by GAP version 3.1 or later.

 -- Option: -m
     Enables Meataxe format output.  This output is written into a series of files whose names are obtained by appending '.' and the generator names to STEM. The images, if -i was present, are written to STEM.IM. This option is only available for me as there is no Meataxe format for integers or rationals.

 -- Option: -q
     Enables plain ASCII  output format. The output filename is STEM.pa. This format is designed to be portable and simple to parse (for a computer).

 -- Option: -B
     Enables plain binary  output format. This is written to STEM.pb and is essentially just the binary version of the output generated when -q is selected. It is not likely to be portable between different hardware architectures or different versions of the software, but should be very fast to read and write.

 -- Option: -x
     Enables AXIOM output format. The output file-name is STEM.input.

Output File Names
-----------------

 -- Option: -o
     Sets the output file stem STEM. This is used to construct the names of the various differently formatted output files (see above). The default is meout, unless the -Q option is present, in which case the default is qout.

Logging and Error Message Options
=================================

As the program runs it prints various messages indicating progress and/or reporting errors. The level of detail reported, and the destination of these messages can be controlled by the options in this section. All of the progress messages can be suppressed by removing the compile-time option LOGGING, reducing the program size and speeding it up slightly. If this is done then the -v, -l and -L options will be ignored with an error message.

 -- Option: -l file
     Sets the Logging file. This FILE argument is a compulsory path name and logging output is directed to that file. The default is to send logging output to standard output.

 -- Option: -v 0 | + | ( type level ) ...
     This option controls the Verbosity of logging.

     The argument may take one of the special forms 0 or +. The option -v0 turns off all logging. No output should then be sent to the log file (unless further -v options are given). The options -v+ turns on all possible logging messages, producing extremely copious details of all stages of the calculation.

     Otherwise the argument is a series of TYPE LEVEL pairs (no whitespace may appear within the argument).  Each TYPE is a single letter, selecting a category of event to be logged, the LEVEL is an unsigned integer indicating how detailed a log is required. At LEVEL 0 no events are logged. The following types are defined:

     a
          Controls logging of group and algebra Actions as they are computed. The default level is 0. All higher levels are equivalent and produce a lot of output.

     c
          Controls logging of Coincidence processing. The default level is 0.  At levels greater than 0 all coincidences are logged as they are stacked and processed and all equations are logged as they are processed.  At level 2 or higher the vroot subroutine which replaces a vector by its undeleted image is also logged.

     i
          Controls logging of Initialisation of new basis vectors. The default level is 0.  At level 1 each new basis vector defined is logged.  At levels 2 and higher the full details of the definition are given.

     k
          Controls logging of pacKs of the coset table. The default level is 1. At levels greater than 0 each pack is logged. At levels greater than 1 each basis vector relocated during a pack is logged.

     l
          Controls logging of Lattice operations (zme only). The default level is 1. At this level and higher packing of the lattice and pushes of the lattice are logged. At levels greater than 1 each vector added to the lattice and other substantial changes, and each vector pushed are logged. At level 3 or higher the Gauss-Jordan processing that happens as each vector is added and the effect of coincidences on the lattice are logged.

     m
          Controls logging of memory allocated by the routines in allocs.c This is only permitted when DEBUG was defined at compile time. At all levels greater than 0 the allocation is logged after submodule generators are pushed. At level 2 or higher it is also logged after every weight increase. Whenever the allocation is logged certain consistency checks are also performed and any anomalies are reported.

     p
          Controls logging of relators Pushed. The default level is 0.  At level 1 or higher it logs each relator pushed from a basis element.  At level 2 or higher it also logs the image of each algebra relator (which will then be forced to zero).

     s
          Controls logging of Stages in the progress of the program. The default level is 1. At level 1 or higher the program prints brief messages at major stages in the progress of the program: after the input file is read; after the submodule generators are processed and at the end of the run. At level 2 or higher the program also prints the relators as they are read in, and the whole table at completion. At level 3 or higher the table is also printed after the submodule generators have been processed.

          When the -Q option is also present see Input File Options this suboption has a different effect. At level 1 a message is printed after the submodule generators have been read in and another on completion. A level 2 or higher messages are also printed after every hundred sets of images have been read in.

     w
          Controls logging of Weight changes. The default level is 1.  At any level greater than zero it logs every change of weight (see Strategy).

 -- Option: -L Prefix
     Use of this option causes the argument string to be printed at the start of every line of logging output. It can be used if the log information is later to be read into another program, to cause the messages to be treated as comments.

     Note that no space is inserted after the prefix string. If one is needed it should be supplied as part of the string. For example -L'#I '.

 -- Option: -W Warnlevel
     This option controls the level of detail in the warning messages produced by the input parser in response to incorrect input file syntax.

     Whatever the value, the parser will attempt to recover and read the rest of the file in order to report any further errors. Some errors (such as a repeated generator name) are ignorable, but most will prevent the actual calculation taking place. After reading the whole input file the program will continue with the calculation only if no non-ignorable errors occurred.

     At a WARNLEVEL of 0 no messages are produced. The program will either run or stop with a non-zero return code.

     At a WARNLEVEL of 1 a message describing each error is printed.

     At a WARNLEVEL of 2 the approximate line number and position of the error is also reported.

     At higher levels the offending line is printed, together with an indication of the location of the error.

     The default level is 2.

Input File Options
==================

These options specify, or alter the meaning of, the main input file read by the program.

 -- Option: -p Presentation
     This option specifies the name of the main input file (the presentation). The PRESENTATION is extended to a pathname by adjoining .pres, unless the -Q option appears before the -p, in which case .qin will be adjoined instead (and the input file will be expected to be in a different format). By default input is read from standard input. See Input Formats for details of the format of the input files.

 -- Option: -A
     This option indicates that the generators may be assumed to commute with one another (so that computations are taking place in a polynomial ring). Relations of the form XY = YX will be added for every pair of generators.

 -- Option: -C Characteristic
     This option overrides the characteristic specified in the input file. The argument CHARACTERISTIC is the new characteristic, which must be 0 for zme or qme and a prime between 2 and 251 inclusive for me.

 -- Option: -Q
     This option switches the program from the default behaviour of reading a .pres presentation file and constructing the module presented to reading a .qin quotient specification and constructing the quotient action. It should appear before -p if both are present.

 -- Option: -n

     Normally the programs generate the extra relation x=x, for each non-invertible generator x. This is to ensure that all definitions will be made eventually, so that the table will close. Otherwise, inputting the natural presentation for the free algebra would cause no action.

     This option suppresses these relations. It is only safe to use when you are sure that every generator appears as the first letter of (a term of) a relation.

Debugging Options
=================

Most users should not need these options, and indeed will have compiled the programs so that they are not available. They have no effect if -Q was specified.

 -- Option: -s + | - | Filename Stem
     This option controls the Scrutinize feature. This is only available if the compile-time option SCRUT was set and is never available for zme. The scrutinize system maintains a homomorphism from the module under construction to one read in at the beginning (which should be the correct module). This is used to check all deductions and coincidences. Any discrepancies found are reported.

     The + argument turns scrutinize on, the - argument turns it off (the default). A FILENAME STEM argument turns it on and selects the module to be read in. The STEM defaults to meout. The actual filename is obtained by adjoining .pb to the stem, and the module is read in in the plain binary format described in Options for Output Formats.

 -- Option: -y
     This option turns on Bison's own debugging for the input parser. It is only available when DEBUG was specified at compile-time. Rather copious information is output on the behaviour of the push-down automaton that parses the presentation.

Limit Options
=============

This group of options imposes limits of time, space or weights on the program. If a limit is exceeded the program will exit with a non-zero return code and write no output.

 -- Option: -w MaxWeight
     This option imposes a limit on the maximum weight of basis element that can be defined. The default limit is 100. See Strategy for details of the use of weights. This option has no effect when the -Q option is also given as weights are not used in that case.

 -- Option: -T Time Limit
     This option imposes a limit on the CPU time used by the program. The program will stop soon after the TIME LIMIT CPU seconds have been used (TIME LIMIT is given in floating point). The CPU time is not checked as often as it might be. The default is to have no limit.

 -- Option: -t Max Dimension | Max Dimension:Reserved Percentage
     The option limits the dimension of the module being constructed. The program will attempt to complete the calculation in a smaller space, but may not succeed. The default limit is very large indeed. This option has no effect when -Q is also given, as the table size never increases.

     By default 5% of the dimension limit is reserved for certain critical definitions (occuring during coincidence processing). If there is no space for a critical definition when one is needed the program exits with an error. The proportion of reserved space can be altered using the second form of this option.

Output Formats
**************

On successful completion the programs may write out the results in various ways. Which format(s) are used, and what filenames the output is written to are controlled by various command line options. Output Options.

This chapter describes the format of the files which are written. There are four formats intended to be read into other systems and two formats intended to be easy for special purpose programs to read.

Cayley Format
=============

This format is intended for reading by version 3 of the Cayley computational algebra system produced by John Cannon and associates at the Department of Pure Mathematics, Sydney University, Sydney, NSW, AUSTRALIA. Contact john@maths.su.oz.au for details.

The output file is a Cayley library and sets the following variables:

fld
     This is set to be the field (or, in the case of zme, ring) over which calculations have been performed.

vs
     This is set to be a vector space (or module) over fld, of the same dimension as the module constructed by the program.

grp
     This is matrix group over vs. Its generators have the same names as the generators specified for the vector enumerator, and their actions on vs are those computed by the program.

Images
     This is a matrix with as many rows as there were module generators input to the enumerator and as many columns as the dimension of the module constructed. It gives the images in the module constructed of the original module generators. It is only present if the -i option was selected at run-time.

Lattice
     This is only present for zme and describes the torsion of the module constructed. It is a matrix with as many columns as the dimension of the module and a row for each lattice generator.

VEruntime
     This is the CPU time used in vector enumeration, in milliseconds.

This output format has not been tested much except with group algebra presentations over finite fields. It may not work in other situations. The -P option to write out preimages has no effect on this output format.

GAP format
==========

This format produces a file intended to be read by the GAP system, version 3.1 or later. This system is produced by Lehrstuhl D fur Mathematik, RWTH-Aachen, Aachen, GERMANY and is available for anonymous FTP from samson.math.rwth-aachen.de.

The output file is a GAP source file which defines the following global variables:

field
     The field (or ring) over which the enumeration was performed.

VErunTime
     The CPU time in milliseconds used by the enumeration.

images_mat
     This item is only present if the -i option was given.  It consists of a matrix of field entries with as many columns as the dimension of the module constructed and a row for each module generator specified in the input file, giving the image of that generator in the final module.

gGEN
     This item is only present if the -P (or -b) option was given at run-time.  For each generator GEN specified in the presentation a global GAP variable gGEN is given the value AbstractGenerator("GEN").

preImages
     This item is only present if the -P (or -b) option was given at run-time. It consists of a list of records, one for each basis vector in (dimension of) the module constructed. Each such basis vector is the image of one of the free module generators by a product of generators, and each record has two fields modGen, which contains the number of the free module generator (starting at 1) and word which contains a word (given in terms of IdWord, the gGEN and their inverses) giving the appropriate product of generators.

gen_GEN
     For each generator GEN of the presentation, a global variable gen_GEN is set to the matrix giving the action of GEN on the module constructed.

gens
     The list gens is a list of all the gen_GEN.

lattice_mat
     This is only produced by zme and contains the lattice that describes the torsion of the constructed module.

Meataxe Format
==============

This format is only available with me, as the Meataxe has no facilities for handling integers or rationals. It is intended to produce input suitable for reading into the Meataxe programs of R.A. Parker.

In this output format the action of each generator, and the images if -i was given, is written to separate file. The generator name is appended to the file name stem. See Output Options for more details.

Each matrix is ready to be read in by the meataxe program cv.

The -P option to record pre-images has no effect on this output format.

AXIOM format
============

This format produces output suitable for reading into the AXIOM computer algebra system distributed by NAG, Ltd..

The file produced assigns to the following variables:

fld
     This is set to be the field or ring over which the enumeration was performed.

VErunTime
     This is the CPU time in milliseconds used by the enumeration.

images_mat
     This is set to be a matrix of field entries giving the images in the module constructed of the original free module generators.

rec
     This is only set if the -P option is given, when it is set to be the type

          Record(modGen : PositiveInteger, word : Polynomial Integer).

gen_names
     This is only set when the -P option is given.  It is of type LIST Symbol and contains the names of the generators from the presentation file.

preImagesL
     This is only set when the -P option is given. It is of type LIST LIST Any and is used only to set:

preImages
     This is only set when the -P option is given and the preImagesL coerced to type LIST rec. It has a member for each basis vector (dimension) of the module constructed.  Each such basis vector is the image of one of the original free module generators under a product of algebra generators. The modGen field of the record specifies the free module generator (starting at 1), which the word field is the appropriate monomial in the symbols corresponding to the generators.

gen_GEN
     For each generator GEN given in the presentation, an AXIOM variable gen_GEN is set equal to the matrix (with entries in fld) giving the action of the generator on the module constructed.

gens
     This list contains all the gen_GEN.

lattice_mat
     This is only produced by zme.  It is a matrix giving the torsion of the module constructed.

Plain ASCII format
==================

This format is an unadorned ASCII format intended to be machine read. It consists of ASCII numbers separated by whitespace.

The first line is a header, consisting of four or five numbers

  * The dimension of the constructed module

  * The number of algebra generators (not included inverses). That is the number of generators whose actions appear in this file.

  * The number of free module generator images in the file. This will be 0 is the -i option was not given at run-time, and will otherwise be the number of free module generators in the presentation.

  * A boolean (C style, so 1 for true and 0 for false) entry indicating whether pre-image information appears in the file (ie whether the -P option was given at run-time).

  * For zme only, the number of generators if the torsion lattice.

The next part of the file gives the images of the free module generators, and is only present if the -i option was given at run-time. If it is present then there is a line for each module generator giving its image in the module constructed.

These vectors, and others later in the file are given as field elements separated by spaces. There is no terminator, but the number of field elements expected can be deduced from the header information. Finite field elements are given as integers between 0 and CHARACTERISTIC-1.  Rational numbers are given as NUMERATOR/DENOMINATOR.  Integers and numerators and denominators of rationals may be too large to read into any fixed-size type.

The next section, which will only be present if the -P option was given at run-time (which can be deduced from the header information), gives the pre-images of the basis of the module constructed in the free module. For each basis vector there is a line giving the free module generator and a word in the algebra generators. The free module generator is given as an integer (they start at 1), the algebra generators as integers, in the order in which they are defined in the presentation, starting at 1, with a negative number denoting the multiplicative inverse of its absolute value. The words are terminated by a zero.

The next section gives the matrices for the action of the generators. The rows are given as vectors in the format described above, and the matrices are not separated.

For zme only, the lattice generators are given as a series of vectors.

Finally, the CPU time used, in milliseconds appears on a line by itself.

Plain Binary Format
===================

This format is essentially identical to the Plain ASCII format described in Plain ASCII format, except that the individual entries, instead of being whitespace separated decimal numbers are fixed-length binary numbers. All numbers are written as unsigned int or int (for generator numbers in pre-images), except that for qme and zme, the rational numbers and integers are written using the mpz_out_raw function of GMP.

Strategy
********

The vector enumeration algorithm, as described in On Vector Enumeration, for instance, leaves unanswered a number of practically important questions about the order in which relations and submodule generators are used. A set of answers to these questions is known as an enumeration strategy.

The strategy used by these programs is based on the coset enumeration strategy defined in Double Coset Enumeration, Journal of Symbolic Computation (12) 1991. This is an HLT-based strategy (something about which we have no choice for vector enumeration) based on two key ideas, lookahead, originally due to M.J.T. Guy, and weights due to R.A. Parker.

Weights
=======

In this approach, every relation of the presentation, every basis vector in the module constructed and (for zme) every vector in the lattice and every generator, has a weight, which is a positive integer.

The weights of the relations may be given in the presentation file see Weight Specifications. Otherwise they are given default values. For a group-type relator, see Group Type Relations the default weight is half the length of the relator. For an algebra relation, see Algebra Relations the default weight is 3.

For zme the weights of the generators are currently fixed at 2. A mechanism for setting them will be added to a future release.

The weight of a basis vector or lattice vector created during submodule processing is 1. After that, there is a current weight, which begins at 2 and increases steadily. At current weight W, all (BASIS VECTOR,RELATION) pairs whose weights total W (or less, if somehow they have not been processed already) will be processed. New basis vectors and lattice vectors created during this processing will be assigned weight W.

In zme, there is additional processing, because, as well as the (BASIS VECTOR, RELATION) pairs, the image of every lattice vector under every generator must be computed and forced to lie in the lattice. At current weight W, every (LATTICE VECTOR, GENERATOR) pair whose weights sum to W (or less) is processed.

There is a maximum weight, and if the current weight reaches the maximum weight without the calculation being complete then the program stops. The maximum weight is 99 by default, and can be set from the command line Strategic Options.

The art of setting weights to obtain optimum performance is, unfortunately, just that: an art. All I can suggest is experimentation, possibly with related, but smaller presentations.  Very complex algebra relations should probably have their weight increased from the default.

Certain relations are adjoined automatically to the presentation. These are given standard weights. The relations xx=1, xx~=1 or x=x adjoined for involutary, invertible or arbitrary generators x have weight 3. The relations xy=yx adjoined for each pair of generators x and y when the -A flag is present see Input File Options have weight 2.

Lookahead
=========

The idea of lookahead is to detect in advance coincidences which can be proved without further definitions. From time to time, the program shifts into lookahead mode, and attempts to process some further relations without defining new basis vectors. It then shifts back to the normal state, called define mode and resumes processing from where it left off.

The program will only change modes when the current weight is about the change. It goes into lookahead mode if the number of basis vectors has doubled since it last entered define mode (or since the end of submodule processing if this is the first lookahead). It looks ahead a number of weights controlled by the command line option -a see Strategic Options, or 2 weights by default.

A relation may have a different weight in lookahead mode from its weight in define mode. Indeed the relations xx=1, xx~=1 or x=x, adjoined automatically to the presentation, have weight 6 in lookahead mode, (rather than 3) as their main function is to make sure that all entries in the table are filled eventually.

The Source Code
***************

This chapter is provides a little information about the arrangement and operation of my source code. It is intended only for those trying to fix local compilation problems or to make small changes or additions. If you are interested in getting more deeply involved with the innards of the program please feel free to get in touch with me.

Generalities
============

Important macros
----------------

The file meint.h contains both the external declarations for most of the functions in the programs and a large number of critical macros. The macros are crucial to the way in which the three programs are generated from one set of sources, and to the operation of the DEBUG, SCRUT and LOGGING compile-time flags.  Among the more significant ones are:

DIE()
     In DEBUG mode (when the pre-processor symbol DEBUG) is defined) DIE() prints an error message indicating the file and line number and calls abort() generating a core dump. In non-DEBUG mode it simply exits with a non-zero return code.

ASSERT(CONDITION)
     In DEBUG mode this macro checks whether CONDITION is true and calls DIE() if it is not. In non-DEBUG mode it generates no code (in particular CONDITION is not evaluated). This is the principle method of including consistency checks in the debugging version of the program.

IFDEBUG(CODE FRAGMENT)
     Simply executes CODE FRAGMENT only in DEBUG mode. For example after de-allocating the contents of a pointer it is good practice to put a NULL in it to avoid referencing the freed memory.

LOG(CONDITION,CODE FRAGMENT)
     This macro generates no code unless the LOGGING pre-processor symbol is defined, in which case it executes CODE FRAGMENT if CONDITION is true. Typically CONDITION checks one of the global variables such as logcoin that control the verbosity of logging see Logging and Error Message Options.

SC(CODE FRAGMENT)
     Executes CODE FRAGMENT only if the SCRUT pre-processor symbol is defined and the global variable scrut (set by the -s command-line option Debugging Options) is true.

PS(VECTOR, CODE FOR PACKED, CODE FOR SPARSE)
     In me, but not in the other programs, a vector in the module under construction can be represented in one of two forms (packed and sparse, see Constructing Matrix Representations of Finitely Presented Groups). It is often necessary to use separate pieces of code to deal with the two cases.

     When me is being compiled, this macro expands to an if ... else ... statement that executes the appropriate code in each case. When the other programs are being compiled it expands to CODE FOR SPARSE.

Arithmetic
----------

Arithmetic in the underlying field (ring) is provided by macros such as Fadd, Fmul, FOne which enable much of the coding to be independent of the underlying arithmetic. In some places (mainly in vector.c) explicit #if ...#endif structures are used where speed requires special code for the different programs.

Pre-processor symbols ME, QME and ZME, indicate which programs are being compiled, but in the interest of flexibility, a separate set GFP, RATIONAL and INTEGRAL are used to indicate which arithmetic is being used.  For the GFP case many of the macros (those dealing with allocating space, for example) expand to no code, and they all expand to inline code fragments. For the other arithmetics almost all the macros expand to calls to GMP routines.

Prototyping and Other Language Issues
-------------------------------------

The file global.h attempts to make the code compatible with both ANSI and traditional C compilers, based on whether the pre-processor symbol __STDC__ is defined. In particular, the macro PT is defined to either return or ignore its argument, so as to provide proto-typing when it is allowed. The type pointer is also defined to be either char * or void * as appropriate.

The Source Files
================

alloca.c
     This is taken from a GNU source, and emulates the BSD library function alloca on systems where it is not provided. alloca is used only by the parser, so speed is not critical. On BSD systems use the library function instead.

allocs.c
     This file contains subroutines to allocate certain types of objects quickly (by allocating space for them in large groups and then maintaining a free queue). It is used for vector headers and (except in me) for small blocks requested by GMP.

coin.c
     This file contains the code that maintains the coincidence stacks and processes coincidences. Coincidence processing has changed a little from earlier releases and the published descriptions in that a coincidences is simply stored as a vector to set equal to 0, and the choice of which (if any) basis vector to delete is deferred until the coincidence is destacked. This is principally for the benefit of zme, but seems beneficial in general.

     The important vroot subroutine that replaces a vector by its undeleted image is also here.

comline.c
     This file processes the options on the command line see Command Line Options and sets global variables appropriately

ilatt.h
     This file contains macros and declarations used only by lattice.c. Declarations for routines exported from lattice.c are in latt.h. This file is only part of zme.

input.c
     This file contains functions called by the input parser (and a driving routine to call the parser and tidy the presentation afterwards).

input.h
     A number of functions and macros are used only at the input end of the program, by input.c, input.tab.c and scanner.c. They are declared here to avoid further complicating meint.h.

input.tab.c
     This file contains the parser produced by bison from input.y. It is called inputtab.c under MS-DOS.

input.y
     This file is the bison grammar file which produces input.tab.c. It is called inputtab.y under MS-DOS.

latt.h
     This file contains the declarations of functions and globals exported by lattice.c the routines that manage the torsion lattice in zme.

lattice.c
     This file contains the code that manages the torsion lattice used in zme. The exact role of this lattice will be described in a future publication on the integer vector enumeration algorithm. In a future release this file may be replaced by one using R.A.Parker's p-adic methods to manipulate the lattice.

me.c
     This file contains a lot of global variables and some miscellaneous subroutines. It is mostly a graveyard for functions with no other natural home. The routine SetDefaults which sets default values for many run-time options is here.

me.h
     This header file contains features which users might which to change, such as the compile-time parameters see Compile-time options and some type declarations and limits.

meint.h
     This file is the main header file of the entire system. Everything starts from here.

memain.c
     This file contains main() and other outer-level routines. The basic sequence of operations is controlled from here.

myalloc.c
     This file provides a debugging version of malloc, free and realloc, and a routine DumpHeap to report the current state of heap allocation. It records the file and line from which each block was allocated, pre-loads each allocated block with a nonsense value (hex E6), and tests freed blocks for consistency. It greatly slows down the program and is used only is DEBUG mode.

myalloc.h
     This is the header file associated with myalloc.c.

out.c
     This file contains the output routines, both those used to output the results of a successful run and those used to output logging information during a run. The output routines have been extensively revised since the last release and each output format is now described by a large data structure and some associated static subroutines. Hopefully this will make it easier to add new output formats.

pack.c
     This file simply contains the subroutine to pack the table and recover the space occupied by deleted rows.

push.c
     This file contains the routines that compute the action of the algebra on the table, and so the routines used to process the relations. Definition of new basis vectors is also handled here.

scanner.c
     This file contains the lexical analyser which tokenises the input.  This cannot be done with (f)lex, as the analyser has to be changed after reading the initial list of generators. This file also contains the code that keeps track of the lines of input so as to be able to report syntax errors properly.

scrut.c
     This file contains the code implementing the SCRUT feature. No code from this file is compiled unless the SCRUT pre-processor symbol is defined (in me.h).

vector.c
     This file contains the basic vector allocation, deallocation and arithmetic subroutines. It is speed critical.

Examples
********

Finally we consider a number of simple examples. The presentation files used for these examples are in the ./examples subdirectory of the distribution, as are a number of others.

The natural permutation representation of S_3
=============================================

The symmetric group S3 is also the dihedral group D6, and so is presented by two involutions with product of order 3. Taking the permutation action on the cosets of the cyclic group generated by one of the involutions we obtain the following presentation file (s3.pres).

     0.AB...A:.(AB)3:.

Here 0 is the characteristic; AB specifies two generators A and B (note that ab would specify one generator ab). The two empty sections ... indicate that both generators are involutions. There is one ``submodule generator'' A (actually A-1 is the submodule generator) and one relation (AB)3 = 1.

It is of course, much more sensible to use a normal Todd-Coxeter program to perform this calculation, as the representation being constructed is a permutation representation.

Running qme -vs2 -ps3 to process this file (the -vs2 simply causes the presentation to be printed once it has been read) we get:

     %qme -vs2 -ps3
     Submodule gens
     Weight  1 group type    A
     Relator
     Weight  3 group type    BB
     Weight  3 group type    AA
     Weight  3 group type    ABABAB
     Done submodule generators
     Starting weight 2 in define mode, 1 alive out of 1
     Starting weight 3 in define mode, 1 alive out of 1
     Starting weight 4 in define mode, 1 alive out of 1
     Looking ahead ...
     Starting weight 5 in lookahead mode, 3 alive out of 4
     Starting weight 6 in lookahead mode, 3 alive out of 4
       ...done
     Packing 4 to 3
     Starting weight 5 in define mode, 3 alive out of 3
     Starting weight 6 in define mode, 3 alive out of 3
     Starting weight 7 in define mode, 3 alive out of 3
     Closed, 3 rows defined
     3 live dimensions

If we also add the -g option to get GAP format output then the program writes a file meout.g containing:

     field := Rationals;
     VErunTime := 16;
     gen_A := field.one*[[1,0,0],
     [0,0,1],
     [0,1,0]];
     gen_B := field.one*[[0,1,0],
     [1,0,0],
     [0,0,1]];
     gens := [gen_A,gen_B];

A Quotient of a Permutation Representation
==========================================

The permutation representation constructed in A permutation representation fixes the all-ones vector (as do all permutation representations). We see easily enough that this is 1+B+BA times the module generator (the vector (0,0,0)). Accordingly we can write down the following presentation for the quotient module (s3a.pres):

     0.AB...A:0=1+B+BA.(AB)3:.

Knowing that we want a dimension 2 module we can turn on early-closing see Strategic Options and run qme -ps3a -e2 -c (we will take Cayley output this time) with the following result:

     %qme -ps3a -e2 -c
     Read Input
     Done submodule generators
     Starting weight 2 in define mode, 2 alive out of 3
     Packing 3 to 2
     Early Closing
     Closed, 2 rows defined
     2 live dimensions

Here we see the advantage of early-closing when the final dimension is known. The output file in this case is meout:

     LIBRARY meout;
     fld : rationals;
     vs : vector space (2,fld);
     grp : matrix group (vs);
     grp.generators :
             A = MAT(
                     1,0:
                     -1,-1),
             B = MAT(
                     0,1:
                     1,0);
     VEruntime = 16;

A Non-cyclic Module
===================

If we take the direct product of two copies of the permutation representation constructed in A permutation representation, we can identify the fixed vectors in the two copies in the following presentation:

     0.AB...{2}[*,A-1],[1,1+B+BA] = [2,1+B+BA].(AB)3:.

which we can run with qme -ps3b to get

     qme -ps3b
     Read Input
     Done submodule generators
     Starting weight 2 in define mode, 5 alive out of 7
     Starting weight 3 in define mode, 5 alive out of 7
     Starting weight 4 in define mode, 5 alive out of 7
     Starting weight 5 in define mode, 5 alive out of 7
     Closed, 7 rows defined
     Packing 7 to 5
     5 live dimensions

In this case it is interesting to look at the images of the module generators and pre-images of the basis vectors. We choose AXIOM format and rerun the program with qme -v0 -Pix -e5 -ps3b. This produces nothing on the standard output, but writes the file meout.input as follows (some indentation and spacing has been added for ease of reading):

     fld := FRAC INT
     VErunTime := 16
     images_mat := matrix([[1,0,0,0,0],_
             [0,1,0,0,0]]) :: MATRIX fld

     rec := Record(modGen : PositiveInteger, word : Polynomial Integer)
     gen_names : LIST Symbol := [A,B]

     preImagesL : LIST LIST Any := [_
             [ 1, 1],_
             [ 2, 1],_
             [ 1, B],_
             [ 1, B*A],_
             [ 2, B]]
     preImages := preImagesL :: LIST rec

     gen_A := matrix([[1,0,0,0,0],_
             [0,1,0,0,0],_
             [0,0,0,1,0],_
             [0,0,1,0,0],_
             [1,-1,1,1,-1]]) :: MATRIX fld
     gen_B := matrix([[0,0,1,0,0],_
             [0,0,0,0,1],_
             [1,0,0,0,0],_
             [0,0,0,1,0],_
             [0,1,0,0,0]]) :: MATRIX fld

     gens := [gen_A,gen_B]

From the images_mat section of this file we see that the two module generators are just the first and second basis vectors.

From the preImages section we see that the five basis vectors are images of the following elements of the free two-generator module for the free two-generator algebra: (1,0), (0,1), (B,0), (BA,0) and (0,B).

A Monoid Representation
=======================

The Coxeter monoid of type B_2 has a transformation representation on four points. This can be constructed as a matrix representation over GF(3), from the following presentation (mond8.pres):

     3.gena genb.*..:gena = 1 .
     : genagena = gena , genbgenb = genb,
     (genagenb)2 = (genbgena)2.

This presentation uses lower-case generator names, so there are two generators gena and genb. The space separating them in the initial list of generators is needed to prevent them being read as one generator genagenb. The * on the first line indicates that both generators are not (known to be) invertible. Indeed, we go on to specify that they are idempotents.

In the relations no space between generator names is needed as the longest-match scanner can always sort out what we mean. Some space might have improved readability however.

We can process this with me (since we are in positive characteristic):

     %me -vs2 -pmond8 -g -e4
     Submodule gens
     Weight  3 algebra type  gena=1
     Relator
     Weight  3 algebra type  genb=genb
     Weight  3 algebra type  gena=gena
     Weight  3 algebra type  gena*genb*gena*genb=genb*gena*genb*gena
     Weight  3 algebra type  genb*genb=genb
     Weight  3 algebra type  gena*gena=gena
     Done submodule generators
     Starting weight 2 in define mode, 1 alive out of 2
     Starting weight 3 in define mode, 1 alive out of 2
     Starting weight 4 in define mode, 1 alive out of 2
     Looking ahead ...
     Starting weight 5 in lookahead mode, 4 alive out of 7
     Starting weight 6 in lookahead mode, 4 alive out of 7
       ...done
     Packing 7 to 4
     Starting weight 5 in define mode, 4 alive out of 4
     Starting weight 6 in define mode, 4 alive out of 4
     Starting weight 7 in define mode, 4 alive out of 4
     Starting weight 8 in define mode, 4 alive out of 9
     Starting weight 9 in define mode, 4 alive out of 9
     Starting weight 10 in define mode, 4 alive out of 9
     Closed, 9 rows defined
     Packing 9 to 4
     4 live dimensions

It is clear that the relations  genb=genb and gena=gena have no effect, since other relations will force the table to be completed. We could therefore have used the -n option see Input File Options, to save a small amount of effort.

The output file from this calculation is:

     field := GF(3);
     VErunTime := 16;
     gen_gena := field.one*[[1,0,0,0],
     [0,0,1,0],
     [0,0,1,0],
     [0,0,0,1]];
     gen_genb := field.one*[[0,1,0,0],
     [0,1,0,0],
     [0,0,0,1],
     [0,0,0,1]];
     gens := [gen_gena,gen_genb];

and the matrices are clearly non-invertible.

An Integer Module with Torsion
==============================

The algorithm for integer module enumeration will be described fully in a forthcoming paper, however one problem which arises is dealing with the information that a generator takes a basis vector to a non-integer multiple of itself. This implies (if the result is to be finite dimensional) that the basis vector is a torsion vector, but does not exactly define the torsion. A further relation is needed to resolve the problem. As an example, consider the presentation (in tors.pres):

     0.X.*..:2*X = 1.:X7=1.

Here the submodule generator implies that X acts as 1/2 on the module generator (the first basis vector). This leads to an extending lattice which is finally terminated by the relation. The module then collapses and is seen to be one-dimensional with 127-torsion.

The output from the run is:

     zme -ptors -g
     Read Input
     Done submodule generators
     Starting weight 2 in define mode, 2 alive out of 2
     Pushing lattice at weight 2
     Starting weight 3 in define mode, 2 alive out of 2
     Pushing lattice at weight 3
     Starting weight 4 in define mode, 2 alive out of 2
     Pushing lattice at weight 4
     Starting weight 5 in define mode, 1 alive out of 8
     Pushing lattice at weight 5
     Starting weight 6 in define mode, 1 alive out of 8
     Pushing lattice at weight 6
     Starting weight 7 in define mode, 1 alive out of 8
     Pushing lattice at weight 7
     Closed, 8 rows defined
     Packing 8 to 1
     Packed lattice from 8 to 1
     1 live dimensions

and the output file meout.g contains:

     field := Integers;
     VErunTime := 16;
     gen_X := field.one*[[64]];
     gens := [gen_X];
     lattice_mat := field.one*[[127]];

So that we our module has 127-torsion and X acts on it as 64 (which is 1/2 mod 127).

Quotient Construction Example
=============================

Finally, we look at an example of the use of the program with the -Q option to construct quotients of representations. As our input we take the deleted permutation representation of the alternating group A6, which has degree 5. The matrices giving the action are:

     A = (0,0,1,0,0)         B = (1,0,0,0,0)
         (1,0,0,0,0)             (0,0,0,0,1)
         (0,1,0,0,0)             (0,1,0,0,0)
         (0,0,0,1,0)             (0,0,1,0,0)
         (0,0,0,0,1)             (1,1,1,1,1)

The submodule is generated by such vectors as (1,1,0,0,0). We can write this information into an input file a6.qin (it is envisaged that these files would normally be machine generated) as follows:

     2 5 AB
     3
     [1,1,2,1]
     [1,1,3,1]
     [2,1,4,1]
     [2,1]
     [0,1]
     [0,1]
     [4,1]
     [1,1]
     [1,1]
     [3,1]
     [2,1]
     [4,1]
     (1,1,1,1,1)

Here the first two lines are header information, the next three are submodule generators, and the remainder are the rows of the matrices (suitable formatted). This can be read by me -Q -vs2 and produces the following output:

     %me -Q -pa6 -vs2
     Read submodule generators 2 live dimensions
     Read 0 sets of images
                 2 alive     2 blanks
     All read in 1 alive

With -ig as well the output file qout.g is:

     field := GF(2);
     VErunTime := 16;
     images_mat := field.one*[[1],
     [1],
     [1],
     [1],
     [1]];
     gen_A := field.one*[[1]];
     gen_B := field.one*[[1]];
     gens := [gen_A,gen_B];

Note that the images_mat section contains non-trivial information (that all the basis vectors in the original presentation have image 1 in the quotient.

A Quotient of a Polynomial Ring
===============================

The quotient of a polynomial ring by the ideal generated by some polynomials will be finite-dimensional just when the polynomials have finitely many common roots in the algebraic closure of the ground ring. For example, three polynomials in three variables give us the following presentation for the quotient of their ideal (poly.pres):

     0.ABC.*..:
     A+B+C=0,
     AB+BC+CA = 0,
     ABC=1..

We run this with the -A option to indicate that all the generators commute. We obtain:

     % qme -A -ppoly -vs2
     Submodule gens
     Weight  3 algebra type  ABC=1
     Weight  3 algebra type  AB+BC+CA=0
     Weight  3 algebra type  A+B+C=0
     Relator
     Weight  2 algebra type  BC=CB
     Weight  2 algebra type  AC=CA
     Weight  2 algebra type  AB=BA
     Done submodule generators
     Starting weight 2 in define mode, 6 alive out of 9
     Starting weight 3 in define mode, 6 alive out of 9
     Starting weight 4 in define mode, 5 alive out of 11
     Starting weight 5 in define mode, 6 alive out of 20
     Starting weight 6 in define mode, 6 alive out of 20
     Closed, 20 rows defined
     Packing 20 to 6
     6 live dimensions

Thus we see that these polynomials have six common roots. We could determine them by simultaneously diagonalising the matrices giving the action of the generators on the quotient.