1###############################################################################
2#
3# Australian National University p-Quotient Program
4#
5# Version 1.9
6#
7# June 2001, February 2002, February 2004, July 2005, January 2006,
8# November 2011, January 2012
9#
10###############################################################################
11
12This implementation was developed in C by
13
14 Eamonn O'Brien
15 Department of Mathematics
16 University of Auckland
17 Private Bag 92019, Auckland, New Zealand
18
19 E-mail: obrien@math.auckland.ac.nz
20
21 WWW http://www.math.auckland.ac.nz/~obrien
22
23and some minor changes made in 2011-2019 by
24
25 Max Horn
26 Department Mathematik
27 Universität Siegen
28 Walter-Flex-Straße 3, 57072 Siegen, Germany
29
30 E-mail: max.horn@uni-siegen.de
31 WWW http://www.quendi.de/math
32
33###############################################################################
34#
35# Program content
36#
37###############################################################################
38
39The program provides access to implementations of the following algorithms:
40
411. A p-quotient algorithm to compute a power-commutator presentation
42for a p-group. The algorithm implemented here is based on that
43described in Newman and O'Brien (1996), Havas and Newman (1980),
44and papers referred to there.
45
46Another description of the algorithm appears in Vaughan-Lee (1990b).
47A FORTRAN implementation of this algorithm was programmed by
48Alford & Havas. The basic data structures of that implementation
49are retained.
50
51The current implementation incorporates the following features:
52
53a. collection from the left (see Vaughan-Lee, 1990b);
54 Vaughan-Lee's implementation of this collection
55 algorithm is used in the program;
56
57b. an improved consistency algorithm (see Vaughan-Lee, 1982);
58
59c. new exponent law enforcement and power routines;
60
61d. closing of relations under the action of automorphisms;
62
63e. some formula evaluation.
64
652. A p-group generation algorithm to generate descriptions of p-groups.
66The algorithm implemented here is based on the algorithms described in
67Newman (1977) and O'Brien (1990). A FORTRAN implementation of this
68algorithm was earlier developed by Newman & O'Brien.
69
703. A standard presentation algorithm used to compute a canonical
71power-commutator presentation of a p-group. The algorithm
72implemented here is described in O'Brien (1994).
73
744. An algorithm which can be used to compute the automorphism group of
75a p-group. The algorithm implemented here is described in O'Brien (1995).
76
77
78###############################################################################
79#
80#Access via other programs
81#
82###############################################################################
83
84Access to parts of this program is provided via GAP.
85
86This program is supplied as a package within GAP, both GAP 3.4 and GAP4.
87The link from GAP to pq is described in the manual for GAP 3.4, and is
88described in a separate manual supplied with the ANUPQ package anupq.zoo
89archive for GAP4.
90
91###############################################################################
92#
93#References
94#
95###############################################################################
96
97George Havas and M.F. Newman (1980), "Application of computers
98to questions like those of Burnside", Burnside Groups (Bielefeld, 1977),
99Lecture Notes in Math. 806, pp. 211-230. Springer-Verlag.
100
101M.F. Newman and E.A. O'Brien (1996), "Application of computers to
102questions like those of Burnside II",
103Internat. J. Algebra Comput. 6, 593-605.
104
105M.F. Newman (1977), "Determination of groups of prime-power order",
106Group Theory (Canberra, 1975). Lecture Notes in Math. 573, pp. 73-84.
107Springer-Verlag.
108
109E.A. O'Brien (1990), "The p-group generation algorithm",
110J. Symbolic Comput. 9, 677-698.
111
112E.A. O'Brien (1994), ``Isomorphism testing for p-groups",
113J. Symbolic Comput. 17, 133-147.
114
115E.A. O'Brien (1995), ``Computing automorphism groups of p-groups",
116Computational Algebra and Number Theory, (Sydney, 1992), pp. 83--90.
117Kluwer Academic Publishers, Dordrecht.
118
119M.R. Vaughan-Lee (1982), "An Aspect of the Nilpotent Quotient Algorithm",
120Computational Group Theory (Durham, 1982), pp. 76-83. Academic Press.
121
122Michael Vaughan-Lee (1990a), The Restricted Burnside Problem,
123London Mathematical Society monographs (New Ser.) #5.
124Clarendon Press, New York, Oxford.
125
126M.R. Vaughan-Lee (1990b), "Collection from the left",
127J. Symbolic Comput. 9, 725-733.
128
129###############################################################################
130#
131# Installation procedure
132#
133###############################################################################
134
1351. For installation for use with GAP4 please go to the README in the
136 main directory. The directory mapping of the anupq directory derived
137 from anupq.zoo is as follows:
138
139 doc -- manual for the GAP4 package that interfaces with pq
140 standalone-doc -- documentation on use of the pq standalone program
141 standalone -- contains the pq standalone TEST, examples, isom directories
142 include -- C header files
143 src -- C source files and a Makefile
144 lib -- GAP library files
145 tst -- GAP test files
146 examples -- GAP examples
147
148 After doing `make restoredirs' in the anupq directory, the anupq sub-
149 directories are remapped to the way they are in the distribution found at:
150
151 http://www.math.auckland.ac.nz/~obrien
152
153 namely the GAP4 doc directory, main directory README and a number of
154 other files there are moved to the directory doc; standalone-doc
155 is renamed doc; the examples, lib and tst directories are moved into
156 the gap directory; the examples, isom and TEST subdirectories of
157 standalone are moved to be in the main directory; and this README is
158 moved to be in the main directory.
159
160 Doing `make GAP4remapdirs' establishes the directory structure above.
161
1622. The file, guide.tex, in the standalone-doc (or doc) directory is a
163 LaTeX file. It is a basic guide to the use of the p-Quotient Program.
164
1653. By default, the program has the following limits:
166 the maximum number of pc generators is 2^16 - 1 = 65535;
167 the maximum number of defining generators is 2^9 - 1 = 511;
168 the maximum class is 2^6 - 1 = 63.
169
170 The data structures require that the following holds:
171 the sums of the exponents of 2 from the above three quantities
172 is at most (the number of bytes in a word) - 1.
173 Hence the sum is usually 31.
174
175 The program can be compiled in two modes; in fixed mode
176 the above limits are enforced; in runtime mode, these are
177 also the default; however, the limit on the number of defining
178 generators and the class can be altered by the user via
179 on-line options "-c" and "-d"; if such selections are made,
180 the maximum number of pc generators is consequently altered;
181 a user must decide the limit on *each* of the number of
182 defining generators and the class.
183
184 The default limits are set in the header files:
185 storage_fixed.h (for fixed version)
186 runtime.h (for runtime version)
187
188 On average, the fixed mode version performs 5-10% more
189 efficiently than the runtime version.
190
191 If you wish to compile the runtime mode version, then set
192 -DRUN_TIME as a compiler flag in the Makefile.
193
1944. The README in the main directory explains how to install the
195 GAP4 package ANUPQ together with the pq binary.
196
197 *Otherwise*, to create the pq binary --
198 a. change to the src directory;
199 b. ensure that the conditional compilation flags in the
200 Makefile are set correctly; the -DLARGE_INT flag controls
201 the storage and display of automorphism group orders;
202 if you want to use this flag, you must have an up-to-date
203 copy of the GNU MP procedures on your machine;
204 c. system dependent features are collected in system.c;
205 in particular, you may wish to look at the run time function
206 to ensure that the CPU time reported by the program is correct;
207 d. type make pq
208 e. to remove all of the object files, type make clean
209
210 A binary file, pq, will be placed in a subdirectory of bin which
211 is created when configure and make are run in the main directory.
212
2135. The total space requirements for this directory (including
214 the binary but excluding the object files) is about 3 MB.
215
2166. In p-group generation, if the automorphism group of the
217 starting group is insoluble, then pq calls GAP to perform
218 particular stabiliser computations
219 (see the User Guide for more details).
220 The user of pq may choose which of these systems is to
221 be called -- however, the choice for this link MUST be
222 made by the user at compilation time by setting the
223 GAP_LINK flag in the Makefile.
224 Points 7 and 8 below discuss each of these links in turn.
225
2267. The link from pq to GAP assumes that you use GAP 3.4 or GAP4
227 *with* the *ANUPQ package* installed.
228
229 If the binary for GAP 3.4 or GAP4 is called gap and is in your
230 default path, you need do no more; if it is not in your path,
231 you must set an environment variable ANUPQ_EXEC_GAP to
232 point to the GAP executable.
233
2348. The TEST subdirectory of standalone contains a number of log files,
235 with extension .orig, together with a cshell file called TEST.
236 This test program runs through a number of the examples
237 in the examples directory and compares the results generated with
238 those listed in the .orig files of this directory. If the
239 p-quotient program is running correctly, the TEST program
240 should report only differences in the date, name of machines
241 and times taken. If there are other significant differences,
242 please report.
243
244 Execute the test program by typing TEST
245 (If your pq directory structure is different, you may need to alter
246 the relative paths in TEST for both binary and command files.)
247
248 The total time taken for the test on a SPARCstation 10/51 is
249 about 30 seconds of user time.
250
2519. See the documentation for information on run-time parameters.
252
25310. Please report bugs/problems/feedback to obrien@math.auckland.ac.nz
254 and/or max.horn@uni-siegen.de
255