1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2%% 3%W guide.tex ANUPQ standalone documentation Eamonn O'Brien 4%% 5%% 6%W Greg Gamble made a number of modifications: updated it for LaTeX2e; 7%W added a table of contents, cross-references and an examples appendix; 8%W updated the bibliography and Eamonn's address, improved some of the 9%W descriptions, re-arranged it slightly and updated it for changes made 10%W for Versions 1.5 and 1.6. The file needs to be latex-ed three times 11%W to obtain a correct `.dvi' file. 12%% 13\documentclass[12pt]{article} 14% 15%page layout - A4 paper is 210mm by 297mm. 16% 17\hoffset -25truemm 18\oddsidemargin=30truemm % 19\evensidemargin=25truemm % inner margin of 30mm, outer 25mm 20\textwidth=155truemm % 21\voffset -25truemm 22\topmargin=22truemm % top margin of 25mm 23\headheight=0truemm % no head 24\headsep=0truemm % no head 25\textheight=246truemm % bottom margin of 25mm, page nos. inside 26% 27\def\pq{the $p$-quotient implementation} 28\begin{document} 29\title{A guide to the ANU {\it p}-Quotient Program\\Version 1.9} 30\author{Eamonn O'Brien} 31\date{January 2012} 32\maketitle 33\tableofcontents 34\pagebreak 35 36\begin{abstract} 37\addcontentsline{toc}{section}{\numberline{}Abstract} 38The ANU {\it p}-Quotient Program (pq) provides access to implementations 39of an algorithm to construct a power-commutator presentation (pcp) for 40a {\it p}-group and of an algorithm to generate descriptions of 41{\it p}-groups. It also allows access to an implementation 42of an algorithm which can be used to construct a ``canonical" 43pcp for a $p$-group and via this construction it allows a user 44to determine whether two $p$-groups are isomorphic. The latter 45can be used to generate a description of its automorphism group. 46\end{abstract} 47 48\section{Program content}\label{sec:prog-content} 49The ANU {\it p}-Quotient Program (pq) is named for the $p$-quotient algorithm 50that it first implemented. Now, via menus it provides access to implementations 51of all the following algorithms: 52 53\begin{enumerate} 54\item 55A \emph{$p$-quotient algorithm} to compute a power-commutator presentation 56for a $p$-group. The algorithm implemented here is based on that 57described in Newman and O'Brien (1996), Havas and Newman (1980), 58and papers referred to there. 59 60Another description of the algorithm appears in Vaughan-Lee (1990b). 61A FORTRAN implementation of this algorithm was programmed by 62Alford \& Havas. The basic data structures of that implementation 63are retained. 64 65The current implementation incorporates the following features: 66 67\begin{enumerate} 68\item[a.] 69 collection from the left (see Vaughan-Lee, 1990b); 70 Vaughan-Lee's implementation of this collection 71 algorithm is used in the program; 72 73\item[b.] 74 an improved consistency algorithm (see Vaughan-Lee, 1982); 75 76\item[c.] 77 new exponent law enforcement and power routines; 78 79\item[d.] 80 closing of relations under the action of automorphisms; 81 82\item[e.] 83 some formula evaluation. 84\end{enumerate} 85 86\item 87A \emph{$p$-group generation algorithm} to generate descriptions of $p$-groups. 88The algorithm implemented here is based on the algorithms described in 89Newman (1977) and O'Brien (1990). A FORTRAN implementation of this 90algorithm was earlier developed by Newman \& O'Brien. 91 92\item 93A \emph{standard presentation algorithm} used to compute a canonical 94power-commutator presentation of a $p$-group. The algorithm 95implemented here is described in O'Brien (1994). 96 97\item 98An algorithm which can be used to compute the \emph{automorphism group} of 99a $p$-group. The algorithm implemented here is described in O'Brien (1995). 100\end{enumerate} 101 102The pq program is written in traditional C and contains about 10322000 lines of code. 104It was developed in a SUN OS environment and has been ported successfully 105to each of Solaris, AIX and Ultrix environments. The interface and 106input/output facilities of the program are rudimentary. Interfaces 107have been developed which allow parts of this program to be called 108from within the computational group theory system {\sf GAP}. 109This program is supplied as a package within {\sf GAP}. 110The link from {\sf GAP} to pq is described in the manual 111for {\sf GAP} 3.4 or in the manual found in the \texttt{doc} directory 112in the case of the {\sf GAP}~4 package {\sf ANUPQ}; all of the 113necessary code can be found in the \texttt{gap} directory of these 114distributions. 115The program is also distributed as part of Quotpic. 116 117Version 1.9 of the pq program (i.e.~the version you are currently reading 118the documentation for) is configured to call {\sf GAP}, at least version 1194.5, to compute stabilisers when needed. 120 121The FORTRAN version of this program was known as the 122Nilpotent Quotient Program. 123 124\section{Installing pq}\label{sec:pq-install} 125 126To install pq just follow the instructions for installing the {\sf ANUPQ} 127package, i.e. in the directory above, do: 128 129\begin{quote} 130\verb|./configure|\\ 131\verb|make| \textit{TARGET} \verb|GAP=|\textit{GAPPATH} 132\end{quote} 133 134If you are running Linux you may omit \textit{TARGET}. The path 135\textit{GAPPATH} should be the path of a \emph{shell script} that runs 136{\sf GAP} 4 with packages {\sf AutPGrp} (at least version 1.5) and 137{\sf ANUPQ} (at least version 3.1) 138installed. If the {\sf ANUPQ} and/or {\sf AutPGrp} packages are not installed 139in the \texttt{pkg} directory of the {\sf GAP} 4 distribution, then 140the \texttt{-l} option (last line of the \emph{shell script} previously 141mentioned) \emph{must} be set to be a semicolon-separated list of 142paths of the main {\sf GAP} directory and the path of the \texttt{pkg} 143directory containing those packages of {\sf ANUPQ} and {\sf AutPGrp} 144that are missing from the {\sf GAP} 4 distribution \texttt{pkg} directory. 145 146The pq program only needs {\sf GAP} for computing stabilisers when you 147answer ``No'' (\texttt{0}) to the question 148``\texttt{PAG-generating sequence for automorphism group?}''. 149If you neglect to add: ``\verb|GAP=|\textit{GAPPATH}'' to the \verb|make| 150command, never mind; the pq program first checks to see if the environment 151variable \verb|ANUPQ_GAP_EXEC| is set. For \texttt{csh} doing: 152 153\begin{quote} 154\verb|setenv ANUPQ_GAP_EXEC| \textit{GAPPATH} 155\end{quote} 156% 157is essentially equivalent to including: \verb|GAP=|\textit{GAPPATH} 158in the \verb|make| command. If you use a different shell just use the 159appropriate syntax for setting environment variables for your shell. 160 161A good test for checking that you have installed pq correctly is to try 162the example in Appendix~\ref{sec:pgrp-gen-eg}. 163 164\section{Organisation} 165Access to the implementations of each algorithm mentioned in 166Section~\ref{sec:prog-content} is provided via menus. 167The \emph{$p$-quotient algorithm} machinery is provided by the 168``Basic Menu for {\it p}-Quotient Program" and 169the ``Advanced {\it p}-Quotient Menu"; 170access to the \emph{$p$-group generation algorithm} implementation is 171provided via the main ``Menu for {\it p}-Group Generation'' and the 172``Advanced Menu for {\it p}-Group Generation"; and finally the 173\emph{standard presentation algorithm} and \emph{automorphism group algorithm} 174implementations may be accessed via the ``Standard Presentation Menu". 175 176By default, the pq program opens with the Basic Menu [for {\it p}-Quotient 177Program] (see~\ref{sec:basic-menu}), which provides ``basic'' options for 178the {\it p}-Quotient algorithm and via options \texttt{8} and \texttt{9} 179gives (immediate) access to two further menus, 180namely the Advanced {\it p}-Quotient Menu 181(see~\ref{sec:advanced-pq-menu}) and the (main) 182Menu for {\it p}-Group Generation (see~\ref{sec:pgrp-gen-main-menu}), 183respectively. The main Menu for {\it p}-Group Generation provides 184access to a further menu: the Advanced Menu for {\it p}-Group Generation 185(see~\ref{sec:pgrp-gen-advanced-menu}). 186 187If the pq program is invoked with the \texttt{-i} switch (see 188Section~\ref{sec:runtime}), the program opens with the 189Standard Presentation Menu (see Section~\ref{sec:stnd-pres-menu}) 190which gives one immediate access to the 191standard presentation and automorphism group machinery 192and via option \texttt{7} access to the Basic Menu 193and hence the other menus. 194 195To cleanly exit the pq program one must retrace one's path through the menus 196(by typing the number of the option that exits each menu or \texttt{0}). 197Exiting the menu that the pq program opened with (either the Basic Menu 198or the Standard Presentation Menu), exits the pq program. 199 200The Basic Menu, the main Menu for {\it p}-Group Generation and 201the Standard Presentation Menu 202are designed particularly for the new or occasional user; 203levels of control by the user are low, but there is little 204attendant risk of obtaining inaccurate information. The Advanced menus 205are designed for the knowledgeable user with specialised needs; they 206allow the user to make almost all decisions, provide little protection 207and if pre-requisite information for an option to succeed 208(e.g. a pc presentation for the group) is not in place, the pq will 209invariably exit horribly. 210 211Each menu is discussed in more detail later. See 212Section~\ref{sec:conventions} for the conventions 213that apply to these menus. 214 215\pagebreak 216\section{Runtime parameters}\label{sec:runtime} 217The program may be invoked with the following runtime parameters: 218 219\enlargethispage*{1\baselineskip} 220\begin{description} 221 222% An idea which may or may not be implemented 223%\item[\texttt{-2}\hspace*{1em}] 224% Gives the experimental Level 2 (non-menu) interface, which is 225% being designed to supersede the usage of the other runtime parameter 226% switches (except for \texttt{-v}) when pq is used with {\sf GAP} 4. 227 228\item[\texttt{-b}\hspace*{1em}] 229 A ``basic" format can be used to input a group presentation. 230 See~\ref{sec:basic-fmt}. 231 232\item[\texttt{-G}\hspace*{1em}] 233 This option is used by {\sf GAP} 4. It is essentially equivalent 234 to setting the switches \texttt{-g -i -k} simultaneously, except 235 that it uses {\sf GAP}'s iostream to direct requests to {\sf GAP} 236 to compute stabilisers when necessary. 237 238\item[\texttt{-g}\hspace*{1em}] 239 If groups are generated using $p$-group generation, then 240 their presentations are written to a file 241 in a {\sf GAP} compatible format. 242 The name of the file may be selected using the \texttt{-w} option; 243 the default is \texttt{GAP\_library}. 244 245\item[\texttt{-i}\hspace*{1em}] 246 This provides access to the Standard Presentation Menu, 247 which can be used to construct the standard presentation 248 of a given $p$-group. 249 250\item[\texttt{-k}\hspace*{1em}] 251 The presentation may be defined and supplied using certain 252 key words. Examples of this format can be found in those 253 files in the \texttt{examples} directory whose names commence with 254 \texttt{keywords\_}. This option cannot be used with \texttt{-b}. 255 256\item[\texttt{-s} {\it integer}]\ \\ 257 All computations of power-commutator presentations occur 258 in an integer array, $y$ -- the space of this array, by 259 default 1000000, is set to {\em integer}. See the discussion 260 on strategies to minimise time and space later in this document. 261 262\item[\texttt{-v}\hspace*{1em}] 263 Gives the version of the ANU {\it p}-Quotient program and exits. 264 265\item[\texttt{-w} {\it file}]\ \\ 266 Group descriptions are written in {\sf GAP} 267 format to {\em file}. \texttt{-g} 268 must be used in conjunction with this parameter. 269 270\end{description} 271 272If the program is compiled using the \texttt{RUN\_TIME} option, then 273there are two additional runtime options: 274 275\begin{description} 276 277\item[\texttt{-c}\hspace*{1em}] 278The maximum exponent-$p$ class to be considered. 279 280\item[\texttt{-d}\hspace*{1em}] 281A bound on the number of defining generators. 282 283\end{description} 284 285\pagebreak 286\section{Conventions}\label{sec:conventions} 287\subsection{Menu Conventions} 288 289The following conventions apply for all menus. 290\begin{itemize} 291\item 292Typing the integer identifying an option selects that option. 293 294\item 295At a number of points in running the program, you will 296be asked questions or prompted for input. A non-zero integer response 297signifies a positive response to the question; a response of \texttt{0} (zero) 298is a negative response. 299In this guide, a ``Yes" means a non-zero integer response; 300a ``No" is a zero response. 301 302\item 303For each menu, the option \texttt{-1} lists the menu, 304and \texttt{0} exits the menu. 305To cleanly exit the pq program one must retrace one's path through the menus 306(by typing the number of the option that exits each menu or \texttt{0}). 307Exiting the menu that the pq program opened with (either the Basic Menu 308or the Standard Presentation Menu), exits the pq program. 309 310\item If the program cannot open a file for any reason, it simply 311reports this and if not running interactively exits. 312 313\item Input from the first occurrence of a ``\texttt{\#}" symbol to the 314 end of that line is interpreted as a comment and is ignored. 315\end{itemize} 316 317Language used in the menus for the construction of the pcp 318follows that used in Havas \& Newman (1980) and 319Newman \& O'Brien (1996); 320that in the {\it p}-group generation menus follows O'Brien (1990); 321that in the standard presentation menu follows O'Brien (1994). 322 323\subsection{Word input}\label{sec:word-input} 324 325The performance of the program is significantly enhanced if 326it can store the defining relations in their unexpanded form. 327It is currently only possible to store a supplied relation in its 328unexpanded form if the relation is either a power OR a commutator, 329and the components of the power or commutator are only 330defining generators or their inverses. Hence, it is frequently 331appropriate for the user to introduce redundant generators into 332the supplied presentation. 333 334There are two formats available for supplying 335generators and relations: the ``default format'' 336(see Section~\ref{sec:def-fmt}) and the ``basic format'' 337(see Section~\ref{sec:basic-fmt}). Examples of the usage of both formats 338can be found in the \texttt{examples} directory. 339 340\subsubsection{The default format for word input}\label{sec:def-fmt} 341Under the default format, a user is prompted for a list of 342generators, which must be supplied as a set. 343The user is then prompted for a defining set of relations, 344again supplied as a set. 345 346Any combination of relations and relators may be supplied. 347Note, however, you may NOT use relations of the form $u = v = w$. 348Relations are separated by commas, $\wedge$ is used for powers and 349conjugation, \texttt{[} and \texttt{]} are used to indicate the beginning 350and end of a commutator, and \texttt{1} is the identity of the group. 351The following are examples of valid input for relations: 352\newcommand{\wedg}{$\mathtt{\wedge}$} 353\begin{flushleft} 354\quad\verb|{x |{\wedg}\verb| 5 = [x, y, y], z |{\wedg}\verb| x = 1, z * y * x * z |{\wedg}\verb| -1 = 1}|\\ 355\quad\verb|{a3 * [a2, a1], a4 |{\wedg}\verb| a1 * a3 |{\wedg}\verb| a2 * [a2, a1 |{\wedg}\verb| -1, a4, a1 |{\wedg}\verb| 7] = 1}| 356\end{flushleft} 357 358\subsubsection{The basic format for word input}\label{sec:basic-fmt} 359The basic format is selected at start-up via the \texttt{-b} switch 360(see Section~\ref{sec:runtime}). 361In the pcp, the defining generators and the pcp generators are 362labeled as positive integers; in each case they commence at 1. 363Inverses of generators are labelled by the corresponding negative number. 364 365The format for word input is the following: 366\begin{displaymath} 367\textit{Exp}\; \textit{Gen}_1\; \textit{Gen}_2 \ldots \mathtt{;} 368\end{displaymath} 369where ``\textit{Exp}" is the exponent; 370if $\textit{Gen}_i$ is a positive integer, it represents the corresponding 371generator of the group; if it is a negative integer, it represents 372the inverse of that generator. Word input is terminated by a ``\texttt{;}". 373Entries in the word can be separated by any positive 374number of spaces. 375 376Defining relations may only be supplied as relations -- not as relators. 377Each side of the relation is supplied as a word using the above 378format. Where the input is a power of a left-normed commutator, the 379following simpler format may be used 380\begin{displaymath} 381\textit{Exp}\; \texttt{[} \textit{Gen}_1\; \textit{Gen}_2 \ldots \texttt{];} 382\end{displaymath} 383where \texttt{[} and \texttt{]} are used to indicate the beginning and end 384of the commutator. As for the default format, entries in the commutator can 385be separated by an optional number of spaces. 386The identity word is indicated by supplying a word with exponent \texttt{0} 387-- ``\texttt{0;}" is sufficient. 388 389Examples of acceptable input are the following: 390\begin{itemize} 391\item The input ``\texttt{5 2 1 -3 4;}" 392represents the word $(2 \times 1 \times 3^{-1} \times 4)^5$. 393\item The input ``\texttt{3 [2 1 1 3];}" represents 394the commutator power $[2,\; 1,\; 1,\; 3]^3$. 395\end{itemize} 396Under the basic format, the program only accepts input of 397either type in a word; you may not combine them. This may affect 398how you supply the defining relations for the presentation. 399 400\subsubsection{Advanced menu word input} 401Words are supplied as input to options to the Advanced menus 402on a number of occasions. Usually, 403these are words in the pcp generators of the group. 404 405Under the default format, the $n$ pcp generators of the group 406are, for convenience, automatically labelled as 407$\mathtt{x1, x2, \ldots, x}n$. 408All words in the pcp generators are then supplied as words 409in $\mathtt{x1, \ldots, x}n$, using the format prescribed above 410for the defining relators. Word input is terminated by a ``\texttt{;}". 411 412A few options allow input involving the defining generators. 413The $m$ defining generators of the group are also automatically 414labelled as $\mathtt{x1, x2, \ldots, x}m$. All words in the defining 415generators are then supplied as words in $\mathtt{x1, \ldots, x}m$, 416using the format prescribed above for the defining relators. 417As before, word input is terminated by a ``\texttt{;}". 418 419If you use the basic input format, then all words are 420supplied as specified in the basic format discussion. 421 422\subsection{Input and output facilities} 423Currently, facilities exist to save the computed presentation to file 424and to later restore and restart the computation. The files are saved and 425restored using the ``\texttt{fread}" and ``\texttt{fwrite}" facilities, 426respectively. 427For both save and restore, the user supplies a name for the file, 428which can be any valid (UNIX or VMS) name. In the case of writing to file, 429the program does not query the user before overwriting 430an existing file -- it is the user's responsibility to prevent 431such situations from occurring. 432 433\section{The {\it p}-Quotient implementation} 434 435\subsection{Basic Menu for {\it p}-Quotient Program}\label{sec:basic-menu} 436The default opening menu obtained on running the program is listed below. 437\begin{verbatim} 438Basic Menu for p-Quotient Program 439---------------------------------- 4401. Compute pc presentation 4412. Save presentation to file 4423. Restore presentation from file 4434. Display presentation of group 4445. Set print level 4456. Calculate next class 4467. Compute p-covering group 4478. Advanced p-quotient menu 4489. (Main) menu for p-group generation 44910. Exit from p-quotient program 450\end{verbatim} 451We now discuss each of these options. 452\begin{description} 453\item[\texttt{1.\ Compute pc presentation}]\ \\ 454 When you select this option, you will be given the following sequence 455 of prompts for input. [If you start the pq program with the \texttt{-k} 456 switch (see Section~\ref{sec:runtime}), you will not be prompted; 457 instead you must supply input in the form: 458 \begin{quote} 459 \textit{keyword} \textit{value} 460 \end{quote} 461 where \textit{value} is the input you would otherwise have been prompted 462 for. The last input for this option must also be terminated by a semicolon 463 (\texttt{;}). Some data have default values if omitted, and there is no 464 restriction on the order in which the data are supplied. The keyword 465 \textit{keyword} needed and default value if there is one, for the 466 corresponding \texttt{-k} input is given in square brackets after describing 467 each prompt (but not after describing the prompts obtained when the pq 468 program is called with \texttt{-b} --- the \texttt{-k} and \texttt{-b} 469 switches cannot be used together). Actually, only the first 3 letters 470 of each keyword are significant; so, in fact, \texttt{prime}, for example, 471 may be abbreviated to \texttt{pri}.] 472 % 473 \begin{description} 474 \item[\texttt{Input group identifier:}]\ \\ 475 you may supply any sequence of characters, 476 excluding spaces, as a valid identifier for the group. 477 [keyword: \texttt{name}, default: \texttt{G}.] 478 \item[\texttt{Input prime:}]\ \\ 479 supply the prime $p$ used in computing the {\it p}-quotient. 480 [keyword: \texttt{prime}.] 481 \item[\texttt{Input maximum class:}]\ \\ 482 supply the maximum exponent-{\it p} class of the quotient to be constructed. 483 [keyword: \texttt{classbound}, default: \texttt{10}.] 484 \item[\texttt{Input print level:}]\ \\ 485 see option \texttt{5} below. 486 [keyword: \texttt{outputlevel}, default: \texttt{1}.] 487 \end{description} 488 % 489 If the default format is used (i.e.\ pq was not called with the \texttt{-b} 490 switch) then you will be prompted as follows. 491 % 492 \begin{description} 493 \item[\texttt{Input generating set}]\hspace*{-0.5em}\verb| (in { }):|\\ 494 supply generating set. 495 [keyword: \texttt{generators}.] 496 \item[\texttt{Input defining set of relations}]\hspace*{-0.5em}\verb| (in { }):|\\ 497 supply defining set of relations. 498 [keyword: \texttt{relators}, default: \verb|{}|.] 499 \end{description} 500 % 501 Otherwise, if the basic format is used (i.e.\ pq was called with the 502 \texttt{-b} switch; see Section~\ref{sec:runtime}), you will not be 503 prompted; instead you must supply input in the) then you will be given the 504 following prompts. 505 % 506 \begin{description} 507 \item[\texttt{Input number of generators:}]\ \\ 508 supply number of defining generators. 509 \item[\texttt{Input number of relations:}]\ \\ 510 supply number of defining relations. 511 \end{description} 512 % 513 Then (i.e.\ with or without the \texttt{-b} switch) you will be prompted 514 % 515 \enlargethispage*{1\baselineskip} 516 \begin{description} 517 \item[\texttt{Input exponent law (0 if none):}]\ \\ 518 if the group is to satisfy a particular exponent law, supply a positive 519 value for that exponent. 520 [keyword: \texttt{exponentlaw}, default: \texttt{0}.] 521 \end{description} 522 % 523 In the basic format case, you will finally also be prompted to input each 524 relation for the group (if any). 525 526\item[\texttt{2.\ Save presentation to file}]\ \\ 527 prompts for file name, saves group presentation to file. 528 529\item[\texttt{3.\ Restore presentation from file}]\ \\ 530 prompts for file name, restores group presentation from that file if it exists. 531 532\item[\texttt{4.\ Display presentation of group}]\ \\ 533 displays group presentation; 534 detail depends on print level; if level is one, then display order 535 of group, otherwise display full pcp. 536 537\item[\texttt{5.\ Set print level}]\ \\ 538 ranges from 0, providing no output, to 3; 539 1, the default, provides minimal output. 540 541\item[\texttt{6.\ Calculate next class}]\ \\ 542 calculates pcp for quotient having one class greater than the 543 class of the existing group. 544 545\item[\texttt{7.\ Compute p-covering group}]\ \\ 546 547\item[\texttt{8.\ Advanced p-quotient menu}]\ \\ 548 provides access to the ``Advanced Menu" (intended for experts) 549 for user manipulation of the presentation. 550 551\item[\texttt{9.\ (Main) menu for p-group generation}]\ \\ 552 provides access to the main menu for {\it p}-group generation. 553 554\item[\texttt{10.\ Exit from p-quotient program}]\ \\ 555 causes the pq program to exit, or if pq was called with the \texttt{-i} 556 switch (see Section~\ref{sec:runtime}) exits to the Standard Presentation 557 Menu. Selecting option \texttt{0} performs the same function. 558 559\end{description} 560 561\subsection{Advanced {\it p}-Quotient Menu}\label{sec:advanced-pq-menu} 562The advanced {\it p}-quotient menu, given below, is selected by 563choosing option \texttt{8} from the Basic Menu (see~\ref{sec:basic-menu}). 564 565\begin{verbatim} 566Advanced p-Quotient Menu 567------------------------- 5681. Do individual collection 5692. Solve the equation ax = b for x 5703. Calculate commutator 5714. Display group presentation 5725. Set print level 5736. Set up tables for next class 5747. Insert tails for some or all classes 5758. Check consistency for some or all classes 5769. Collect defining relations 57710. Carry out exponent checks 57811. Eliminate redundant generators 57912. Revert to presentation for previous class 58013. Set maximal occurrences for pcp generators 58114. Set metabelian flag 58215. Carry out an individual consistency calculation 58316. Carry out compaction 58417. Carry out echelonisation 58518. Supply and/or extend automorphisms 58619. Close relations under automorphism actions 58720. Print structure of a range of pcp generators 58821. Display automorphism actions on generators 58923. Collect word in defining generators 59024. Compute commutator of defining generators 59125. Write presentation to file in GAP format 59226. Write compact description of group to file 59327. Evaluate certain formulae 59428. Evaluate action specified on defining generators 59529. Evaluate Engel (p - 1)-identity 59630. Process contents of relation file 59731. Exit to basic menu 598\end{verbatim} 599 600\section{The {\it p}-Group Generation implementation} 601\subsection{Required input} 602The required input is the {\it p}-covering group of the starting group, 603together with a description of the automorphism group of the {\it p}-covering 604group. 605Before you commence to construct descendants, 606you should construct or restore its {\it p}-covering group, 607using the appropriate options of the Basic Menu (see~\ref{sec:basic-menu}). 608It is the user's responsibility to do this -- no check is performed. 609 610\subsection{The automorphism group description}\label{sec:autgp-desc} 611You must also supply a description of its automorphism group, 612which is done by selecting option \texttt{1} of either 613of the menus for {\it p}-group generation 614(see~\ref{sec:pgrp-gen-main-menu} or~\ref{sec:pgrp-gen-advanced-menu}). 615This description is the action of each automorphism on each of the 616pcp generators of the Frattini quotient of the group. 617The action is described by a vector of exponents -- the length 618of the vector is the number of pcp generators of the group, 619its entries are the powers of each of these generators 620which occur in the image. 621 622Where the automorphism group is soluble, a PAG-generating system should 623be supplied which works up a composition series for the group via 624cyclic factors of prime order. In such cases, the calculations may be 625carried out completely within pq. If the soluble 626group machinery is selected by the user, but a PAG-generating system is 627not supplied, then the program will give wrong information. 628 629If the automorphism group is insoluble or a PAG-generating sequence 630is not supplied, a call is made by the program to one {\sf GAP}, 631which computes stabilisers of particular orbit representatives. 632If the automorphism group of any of the intermediate (reduced) 633{\it p}-covering groups is found to be soluble, a PAG-generating sequence 634is computed by {\sf GAP} and handed back to pq. The soluble machinery 635is now automatically invoked for the rest of the computation. 636 637\subsection{Saving group descriptions} 638The constructed groups of a particular class, $c$, are saved to a file, 639whose name is obtained by concatenating: 640\textit{starting-group-identifier} and $c$, where 641\textit{starting-group-identifier} is the group identifier defined at option 642\texttt{1} of the Basic Menu (see Section~\ref{sec:basic-menu}) 643e.g.~if you use the \texttt{-k} switch (see Section~\ref{sec:runtime}) 644when you started the pq program and settled for the default group identifier 645\texttt{G} then for class 2, the groups will be saved to a file with name: 646\texttt{G\_class2}. As before, the 647program does not query the user before overwriting an existing file. 648 649\subsection{The (Main) Menu for {\it p}-Group Generation} 650\label{sec:pgrp-gen-main-menu} 651The main Menu for {\it p}-Group Generation, given below, is selected by 652choosing option \texttt{9} from the Basic Menu (see~\ref{sec:basic-menu}). 653\pagebreak 654\begin{verbatim} 655Menu for p-Group Generation 656----------------------------- 6571. Read automorphism information for starting group 6582. Extend and display automorphisms 6593. Specify input file and group number 6604. List group presentation 6615. Construct descendants 6626. Advanced p-group generation menu 6637. Exit to basic menu 664\end{verbatim} 665 666We now describe the options given by this menu. 667 668\begin{description} 669\item[\texttt{1.\ Read automorphism information for starting group}]\ \\ 670 first prompts for the following: 671 \begin{description} 672 \item[\texttt{Input the number of automorphisms:}]\ \\ 673 You must provide the number of automorphisms generating the automorphism 674 group of the starting group. Then you will be prompted for the action 675 of each automorphism on the pcp generators of the Frattini quotient of the 676 group, after which you will be prompted: 677 \item[\texttt{Input number of soluble generators for automorphism group:}]\ \\ 678 If you enter a positive integer $n$ you will then be prompted for the 679 relative order of each of those $n$ automorphisms. 680 \end{description} 681 % 682 683\item[\texttt{2.\ Extend and display automorphisms}]\ \\ 684 compute the extensions of these automorphisms to act on the pcp generators 685 of the {\it p}-covering group and display the results. 686 687\item[\texttt{3.\ Specify input file and group number}]\ \\ 688 prompts for the input file name and the group number. 689 690\item[\texttt{4.\ List group presentation}]\ \\ 691 display at output level 3 the presentation for the group. 692 693\item[\texttt{5.\ Construct descendants}]\ \\ 694 we discuss this option in detail in Section~\ref{sec:constr-desc}. 695 696\item[\texttt{6.\ Advanced p-group generation menu}]\ \\ 697 provides access to the ``Advanced Menu" 698 for user-controlled construction and manipulation. 699 700\item[\texttt{7.\ Exit to basic menu}]\ \\ 701 returns the user to the Basic Menu (see~\ref{sec:basic-menu}). 702 Selecting option \texttt{0} performs the same function. 703 704\end{description} 705 706\subsection{Construct descendants option}\label{sec:constr-desc} 707Here we discuss option \texttt{5} of the (main) {\it p}-group generation 708menu (see~\ref{sec:pgrp-gen-main-menu}). 709If you select this option you receive a number of questions or prompts 710for input. Those prompts/questions are as follows. 711\begin{description} 712\item[\texttt{Input class bound on descendants:}]\ \\ 713 you must supply a positive integer greater than the class 714 of the starting group, and which is an upper bound 715 on the class of the descendants constructed. 716 717\item[\texttt{Construct all descendants?}]\ \\ 718 If you enter a ``Yes" response (by entering a non-zero integer) 719 you are asked: 720 \begin{description} 721 \item[\texttt{Set an order bound for descendants?}]\ \\ 722 If you answer ``Yes" you are further prompted (if you answer 723 ``No" (i.e.\ \texttt{0}) you are not so prompted): 724 \begin{description} 725 \item[\texttt{Input order bound on descendants:}]\ \\ 726 and the integer order bound you input will apply in addition to 727 the class bound selected. 728 \end{description} 729 \end{description} 730 If you responded ``No" to the ``\texttt{Construct all descendants?}'' query 731 and the class increase is one you are prompted: 732 \begin{description} 733 \item[\texttt{Input step size:}]\ \\ 734 and a positive integer is expected. 735 \end{description} 736 If you responded ``No" to the ``\texttt{Construct all descendants?}'' query 737 and the class increase is greater than one you are prompted as follows: 738 \begin{description} 739 \item[\texttt{Constant step size?}]\ \\ 740 If you answer ``Yes" you are prompted: 741 \begin{description} 742 \item[\texttt{Input step size:}]\ \\ 743 and a positive integer is expected. 744 \end{description} 745 If you answer ``No" to ``\texttt{Constant step size?}'' you are prompted: 746 \begin{description} 747 \item[\texttt{Input $n$ step sizes:}]\ \\ 748 for some integer $n$, and you must enter $n$ positive 749 integers separated by spaces. 750 \end{description} 751 \end{description} 752 753\item[\texttt{PAG-generating sequence for automorphism group?}]\ \\ 754 This determines the algorithm used in constructing the orbits 755 and stabilisers of representative allowable subgroups 756 (see~\ref{sec:min-time-space}). 757 Whether you answer ``Yes" or ``No" you are then asked: 758 759\item[\texttt{Default algorithm?}]\ \\ 760 A ``Yes" here constructs immediate descendants using the smallest possible 761 characteristic initial segment subgroups in the {\it p}-multiplicator. 762 This minimises the degree of the permutation group constructed. 763 764 If you answer ``No", then you will be prompted/asked: 765 \begin{description} 766 \item[\texttt{Rank of the initial segment subgroup?}]\ \\ 767 If you want to proceed as in the default, respond ``\texttt{0}"; 768 otherwise any positive value is accepted. If the value is 769 larger than the rank of the {\it p}-multiplicator, the program 770 takes this upper bound as the selected value. The initial segment 771 subgroup determined by this response is characteristically 772 closed by the program. 773 774 If your answer to 775 ``\texttt{PAG-generating sequence for automorphism group?}" 776 was a ``Yes", then 777 you will receive the following further question. 778 779 \begin{description} 780 \item[\texttt{Space efficient computation?}]\ \\ 781 By default, all of the permutations constructed are stored. 782 If you answer ``Yes", at any one time only one permutation is 783 stored, consequently reducing the amount of space significantly. 784 However, the time taken in computing the automorphism group 785 of each descendant is also significantly increased. 786 \end{description} 787 788 Then you will prompted/asked the following: 789 790 \begin{description} 791 \item[\texttt{Completely process terminal descendants?}]\ \\ 792 By default, automorphism groups are computed for and descriptions of 793 capable groups only are saved to file. 794 If you wish to compute automorphism groups and save descriptions of 795 all descendants to file, then answer ``Yes". In this case, 796 for both terminal and capable groups, the automorphism group is 797 saved to file; if capable, the pcp of the {\it p}-covering group 798 is saved; if terminal, the pcp for the group. 799 800 \item[\texttt{Input exponent law (0 if none):}]\ \\ 801 If you wish to construct only those immediate descendants 802 which satisfy a particular exponent law, supply that exponent; if 803 you do not wish to enforce an exponent law, supply \texttt{0}. 804 805 \item[\texttt{Enforce metabelian law?}]\ \\ 806 If you answer ``Yes", you seek to ensure that all of the immediate 807 descendants constructed have the following property -- if any one of them 808 is used as a starting group to a later iteration, only the metabelian 809 immediate descendants (if any) of this group are constructed. 810 For this requirement to be enforceable, the starting group for 811 this iteration must also have that property. To ensure that the 812 starting group has that property, construct its $p$-covering group 813 after having first set the metabelian flag via option \texttt{14} of 814 the Advanced $p$-Quotient Menu (see~\ref{sec:advanced-pq-menu}). 815 \end{description} 816 \end{description} 817 818\item[\texttt{Do you want default output?}]\ \\ 819If you answer ``Yes", minimal output is displayed for each group: 820its identifier, the ranks of its {\it p}-multiplicator and nucleus, 821the number of its immediate descendants of each order, and, if there are any, 822the number of its capable immediate descendants. 823 824For many applications, the default output obtained by ``Yes" is sufficient. 825If not, then by answering ``No" you are asked whether you want the 826default output for each of the following categories: 827permutation group, orbits, group descriptions, automorphism group 828descriptions, or if you want an algorithm trace. Answering ``No" to 829any of these questions (except for the last) 830leads to further questions, each requiring a ``Yes"/``No" answer, 831about what additional information you desire 832(or don't want) for the category. The following are the questions that 833result from a ``No" response to ``\texttt{Do you want default output?}": 834 835 \enlargethispage*{1\baselineskip} 836 \begin{description} 837 \item[\texttt{Do you want default permutation group output?}]\ \\ 838 A ``No" leads to the further questions: 839 \begin{description} 840 \item[\texttt{Print degree of permutation group?}] 841 \item[\texttt{Print extended automorphisms?}] 842 \item[\texttt{Print automorphism matrices?}] 843 \item[\texttt{Print permutations?}] 844 \end{description} 845 \item[\texttt{Do you want default orbit output?}]\ \\ 846 A ``No" leads to the further questions: 847 \begin{description} 848 \item[\texttt{Summary of orbit information?}] 849 \item[\texttt{Complete listing of orbits?}] 850 \end{description} 851 \item[\texttt{Do you want default group output?}]\ \\ 852 A ``No" leads to the further questions: 853 \begin{description} 854 \item[\texttt{Print standard matrix of allowable subgroup?}] 855 \item[\texttt{Presentation of reduced p-covering groups?}] 856 \item[\texttt{Presentation of immediate descendants?}] 857 \item[\texttt{Print nuclear rank of descendants?}] 858 \item[\texttt{Print p-multiplicator rank of descendants?}] 859 \end{description} 860 \item[\texttt{Do you want default automorphism group output?}]\ \\ 861 A ``No" leads to the further questions: 862 \begin{description} 863 \item[\texttt{Print commutator matrix?}] 864 \item[\texttt{Automorphism group description of descendants?}] 865 \item[\texttt{Automorphism group order of descendants?}] 866 \end{description} 867 \item[\texttt{Do you want algorithm trace output?}]\ \\ 868 This last question is designed to permit 869 one to trace the intermediate stages of the algorithm. 870 \end{description} 871\end{description} 872 873After the above dialogue, the pq binary will commence constructing 874descendants. At the commencement of the application, each starting group 875is checked to determine whether it meets the selected step size 876order, and class criteria. If it does not, a message is displayed 877stating that this starting group is invalid. 878 879%\newpage 880\enlargethispage*{2\baselineskip} 881\subsection{Advanced Menu for {\it p}-Group Generation} 882\label{sec:pgrp-gen-advanced-menu} 883\begin{verbatim} 884Advanced Menu for p-Group Generation 885------------------------------------- 8861. Read automorphism information for starting group 8872. Extend and display automorphisms 8883. Specify input file and group number 8894. List group presentation 8905. Carry out intermediate stage calculation 8916. Compute definition sets & find degree 8927. Construct permutations of subgroups under automorphisms 8938. Compute and list orbit information 8949. Process all orbit representatives 89510. Process individual orbit representative 89611. Compute label for standard matrix of subgroup 89712. Compute standard matrix for subgroup from label 89813. Find image of allowable subgroup under automorphism 89914. Find rank of closure of initial segment subgroup 90015. List representative and orbit for supplied label 90116. Write compact descriptions of generated groups to file 90217. Find automorphism classes of elements of vector space 90318. Exit to main p-group generation menu 904\end{verbatim} 905 906\subsection{Strategies to minimise time and space}\label{sec:min-time-space} 907Where a PAG-generating sequence is supplied (i.e.\ the question 908``\texttt{PAG-generating sequence for automorphism group?}" is answered with 909a ``Yes"; see~\ref{sec:constr-desc}), the minimum space 910requirement is achieved by supplying ``\texttt{0}" and ``Yes", 911respectively, to the questions: 912``\texttt{Rank of the initial segment subgroup?}" and 913``\texttt{Space efficient computation?}". 914This space efficiency is achieved at the cost of some additional 915time in computing the stabilisers of orbit representatives. 916However, if you simply wish to compute orbits, it is the 917best overall strategy, both from space and time considerations. 918The ``efficient space" option is currently available only 919where a PAG-generating sequence is supplied. 920 921In general, the most efficient time performance is obtained by 922taking the default algorithm (answering ``Yes" to 923``\texttt{Default algorithm?}; see~\ref{sec:constr-desc}). This also 924gives significant space saving over most other strategies. 925 926As mentioned earlier, the workspace size used in computing pcps -- 927that is, the size of the array $y$ -- may be passed as a command 928line argument to the program at invocation. Much of the storage used in the 929implementation of {\it p}-group generation is separate from that 930allocated for $y$. Hence, if the program is to be used to 931generate group descriptions, it is probably sensible 932to invoke the program with a workspace size of no more than 933$100\;000$ rather than its default value, \texttt{PQSPACE} 934(which is defined in the header file, \texttt{constants.h}). 935See also the discussion on this point in the \texttt{README} file. 936 937\section{The Standard Presentation and\\ Automorphism Group implementation} 938\label{sec:stnd-pres-menu} 939The Standard Presentation Menu allows a user 940to input a finite presentation for a group, to construct 941a ``standard" presentation for a specified $p$-quotient of the group, 942and also to construct a description of the automorphism group of the $p$-group. 943To access this menu, you need to run the pq program 944with the \texttt{-i} run-time parameter switch (see~\ref{sec:runtime}). 945 946The appropriate way to view the standard presentation algorithm is the 947following. 948The pcp constructed by supplying a finite presentation to 949the $p$-quotient algorithm depends on the supplied presentation. 950The standard presentation of a $p$-group obtained using 951the standard presentation algorithm is independent of the 952supplied presentation. Hence it allows us to determine whether 953two $p$-groups are isomorphic. 954 955In its most general form, the ``standard" presentation 956of a $p$-group is obtained by constructing a description of this 957group using the $p$-group generation algorithm. 958 959The standard presentation of a class 1 $p$-quotient 960is identical to that obtained from the $p$-quotient. 961A user can choose to take the presentation returned 962from the $p$-quotient implementation to class $k$ 963as an acceptable ``standard" presentation up to that 964class and then proceed to standardise the presentation 965from class $k + 1$ to some desired later class. 966This is particularly relevant if the user is seeking 967to verify that two groups are isomorphic. 968It may turn out that the two pcps 969constructed by \pq\ are identical up to class $k$. 970Since the standardisation procedure is significantly more 971expensive than a call to \pq, it makes sense in such 972situations to begin to standardise only from class $k + 1$ onwards. 973However, the user must supply as input a description 974of the automorphism group of the class $k$ $p$-quotient 975-- which may be more difficult to obtain for larger $k$. 976 977In checking for isomorphism, it also makes sense 978to standardise each of the presentations, 979class by class. The standard presentations 980at the end of each class should be compared -- 981if they are distinct, then the groups are non-isomorphic. 982In order to facilitate this, the program writes a 983file containing necessary details of the standard presentation and the 984automorphism group of the group up to the end of the specified class 985-- this file can be used as input to the program later to 986continue the standardisation procedure. 987A generating set for a supplement to the inner automorphisms of the 988group is stored there; each generator is described by an $n \times n$ 989 matrix whose exponents represent the image of each of the $n$ 990pcp generators of the standard presentation. 991 992\begin{verbatim} 993Standard Presentation Menu 994----------------------------- 9951. Supply start information 9962. Compute standard presentation to supplied class 9973. Save presentation to file 9984. Display presentation 9995. Set print level for construction 10006. Compare two presentations stored in files 10017. Call basic menu for p-Quotient program 10028. Compute the isomorphism 10039. Exit from program 1004\end{verbatim} 1005 1006We now describe each of these options. 1007 1008\begin{description} 1009\item[\texttt{1.\ Supply start information}]\ \\ 1010 you must supply a finite presentation 1011 for the $p$-group; the queries are identical to that used in 1012 option \texttt{1} of the Basic Menu [for $p$-Quotient Program] 1013 (see~\ref{sec:basic-menu}). All of the valid formats for 1014 supplying a presentation can be accessed, 1015 using the \texttt{-b} or \texttt{-k} run-time switches 1016 (see Section~\ref{sec:runtime}). 1017 If the class supplied is $c$, then standardisation 1018 (selected under option \texttt{2}) begins at class $c + 1$ only. 1019 In general the supplied value for the class will be one -- 1020 however, see the preceding discussion. 1021 A pcp for the class $c$ $p$-quotient of the group 1022 is now computed using the \pq. 1023 1024\item[\texttt{2.\ Compute standard presentation to supplied class}]\ \\ 1025 If, when selecting this option, you haven't previously selected 1026 option \texttt{1} to supply a finite presentation, then 1027 you will be prompted: 1028 % 1029 \begin{description} 1030 \item[\texttt{Enter input file name for group information:}]\ \\ 1031 The assumption is that such a file containing the presentation and 1032 automorphism information for the $p$-group was generated from a previous 1033 run of the Standard Presentation algorithm. If you don't supply a 1034 valid filename the pq program bails out of option \texttt{2}. 1035 \end{description} 1036 % 1037 Whether or not you have previously selected option \texttt{1}, 1038 you will then be prompted: 1039 \begin{description} 1040 \item[\texttt{Enter output file name for group information:}]\ \\ 1041 The file whose name you choose can be used as input 1042 later to continue the construction of the standard pcp. 1043 Then you will be asked: 1044 \item[\texttt{Standardise presentation to what class?}]\ \\ 1045 The start class is one greater than the class of the $p$-quotient 1046 selected using option \texttt{1} or that stored on the input file. 1047 Here you should specify the end class for the standardisation procedure. 1048 \end{description} 1049 If you selected option \texttt{1} to supply a finite presentation, 1050 you will now be prompted for automorphism information -- 1051 in exactly the same manner as under option \texttt{1} of 1052 the main Menu for $p$-Group Generation (see~\ref{sec:pgrp-gen-main-menu}), 1053 and then also asked whether the supplied description 1054 is a PAG-generating sequence or not: 1055 \begin{description} 1056 \item[\texttt{PAG-generating sequence for automorphism group?}] 1057 \end{description} 1058\item[\texttt{3.\ Save presentation to file}]\ \\ 1059\item[\texttt{4.\ Display presentation}]\ \\ 1060 print out the standard presentation to the current class. 1061 1062\item[\texttt{5.\ Set print level for construction}]\ \\ 1063 ranges from 0 to 2. 1064 At print level 0, only timing information is printed. 1065 At print level 1, the standard presentation at the end 1066 of each class is also printed. 1067 At print level 2, full detail of the construction is 1068 reported. The default print level is 1. 1069 1070\item[\texttt{6.\ Compare two presentations stored in files}]\ \\ 1071 supply the names of two data files containing these 1072 presentations; a check will be run to determine if the 1073 presentations are identical. 1074 This comparison facility may be applied to any two 1075 pcps -- not just standard ones. 1076 1077\item[\texttt{7.\ Call basic menu for p-Quotient program}]\ \\ 1078 provides access to the Basic Menu for $p$-Quotient program 1079 (see~\ref{sec:basic-menu}). 1080 1081\item[\texttt{8.\ Compute the isomorphism}]\ \\ 1082 computes the mapping from the user-supplied generators 1083 to the generators for the standard presentation. 1084 1085\item[\texttt{9.\ Exit from program}]\ \\ 1086 causes the pq program to exit. 1087 Selecting option \texttt{0} performs the same function. 1088 1089\end{description} 1090 1091Various files, all having prefixes ``\texttt{ISOM\_}", are first created and 1092then deleted by pq while executing the standard presentation algorithm. 1093\section{Warning} 1094Pay attention to the results, and where possible confirm 1095their correctness with other established sources. 1096 1097\pagebreak 1098\appendix 1099\section{Examples} 1100\subsection{A Basic Menu example} 1101The following example exercises options within the Basic Menu 1102(see~\ref{sec:basic-menu}). When the pq program is used without any switches 1103(see Section~\ref{sec:runtime}), it opens with the Basic Menu. 1104\begin{verbatim} 1105Basic Menu for p-Quotient Program 1106---------------------------------- 11071. Compute pc presentation 11082. Save presentation to file 11093. Restore presentation from file 11104. Display presentation of group 11115. Set print level 11126. Calculate next class 11137. Compute p-covering group 11148. Advanced p-quotient menu 11159. (Main) menu for p-group generation 111610. Exit from p-quotient program 1117 1118Select option: 1 #we want to enter a pc presentation 1119Input group identifier: 2gp #something meaningful 1120Input prime: 2 #it's a 2-group 1121Input maximum class: 6 1122Input print level (0-3): 1 #minimal output 1123Input generating set (in { }): {a, b} 1124Input defining set of relations (in { }): { [b, a, a], (a * b * a)^4 } 1125Input exponent law (0 if none): 0 1126 1127Lower exponent-2 central series for 2gp 1128 1129Group: 2gp to lower exponent-2 central class 1 has order 2^2 1130 1131Group: 2gp to lower exponent-2 central class 2 has order 2^5 1132 1133Group: 2gp to lower exponent-2 central class 3 has order 2^8 1134 1135Group: 2gp to lower exponent-2 central class 4 has order 2^11 1136 1137Group: 2gp to lower exponent-2 central class 5 has order 2^15 1138 1139Group: 2gp to lower exponent-2 central class 6 has order 2^19 1140Computation of presentation took 0.02 seconds 1141 1142Select option: 2 #save option 1143Enter output file name: 2GP #file name 1144Presentation written to file 1145 1146Select option: 0 #exit 1147Exiting from ANU p-Quotient Program 1148Total user time in seconds is 0.02 1149\end{verbatim} 1150 1151This is essentially example \texttt{2gp} in the \texttt{examples} directory 1152(except some of our \texttt{\#}\textit{comment}s are different). 1153If the binary for the pq program is \texttt{pq}, then 1154\begin{quote} 1155 \verb|pq < 2gp| 1156\end{quote} 1157executes the example non-interactively, with something similar to the above 1158output to the screen, minus the menu. Note that 1159the menus from the pq program are only displayed when it is used interactively. 1160A script file for the pq program (like \texttt{2gp}) should contain the 1161responses that the pq program will expect, in the correct sequence. 1162 1163\subsection{A {\it p}-Group Generation example}\label{sec:pgrp-gen-eg} 1164 1165The following example is essentially \verb|pga_3gp| from the 1166\texttt{examples} directory, except again we have modified the comments, 1167and we have also answered ``No'' to the ``PAG-generating sequence'' question, 1168so that {\sf GAP} is called to compute stabilisers. If the pq binary is 1169unable to find {\sf GAP} or finds {\sf GAP 3} instead of {\sf GAP} 4 the 1170program will die horribly at this point. (See Section~\ref{sec:pq-install} 1171if you run into problemsm, at this point.) 1172 1173For this example (which generates all groups with lower exponent-3 series of 1174shape 2-2-3-1), the pq program is invoked without any of the switches 1175of Section~\ref{sec:runtime}. 1176 1177\begin{verbatim} 1178[..Basic Menu omitted here..] 1179Select option: 1 #set up group presentation 1180Input group identifier: c3c3 1181Input prime: 3 1182Input maximum class: 1 1183Input print level (0-3): 1 1184Input generating set (in { }): {a, b} 1185Input defining set of relations (in { }): {} 1186Input exponent law (0 if none): 0 1187 1188Lower exponent-3 central series for c3c3 1189 1190Group: c3c3 to lower exponent-3 central class 1 has order 3^2 1191Computation of presentation took 0.00 seconds 1192 1193Select option: 7 #compute its 3-covering group 1194 1195Group: c3c3 to lower exponent-3 central class 2 has order 3^5 1196Computation of 3-covering group took 0.00 seconds 1197 1198Select option: 9 #enter p-group generation 1199 1200Menu for p-Group Generation 1201----------------------------- 12021. Read automorphism information for starting group 12032. Extend and display automorphisms 12043. Specify input file and group number 12054. List group presentation 12065. Construct descendants 12076. Advanced p-group generation menu 12087. Exit to basic menu 1209 1210Select option: 1 #to supply automorphisms 1211Input the number of automorphisms: 5 1212Now enter the data for automorphism 1 1213Input 2 exponents for image of pcp generator 1: 2 0 1214Input 2 exponents for image of pcp generator 2: 0 2 1215Now enter the data for automorphism 2 1216Input 2 exponents for image of pcp generator 1: 0 2 1217Input 2 exponents for image of pcp generator 2: 1 0 1218Now enter the data for automorphism 3 1219Input 2 exponents for image of pcp generator 1: 1 2 1220Input 2 exponents for image of pcp generator 2: 2 2 1221Now enter the data for automorphism 4 1222Input 2 exponents for image of pcp generator 1: 1 0 1223Input 2 exponents for image of pcp generator 2: 2 1 1224Now enter the data for automorphism 5 1225Input 2 exponents for image of pcp generator 1: 2 0 1226Input 2 exponents for image of pcp generator 2: 0 1 1227Input number of soluble generators for automorphism group: 0 1228 1229Select option: 5 #to construct descendants 1230Input class bound on descendants: 4 1231Construct all descendants? 0 #i.e. ``No'' 1232Constant step size? 0 #i.e. ``No'' 1233Input 3 step sizes: 2 3 1 1234PAG-generating sequence for automorphism group? 0 #i.e. ``No'' 1235Do you want default algorithm? 1 #i.e. ``Yes'' 1236Do you want default output? 1 #i.e. ``Yes'' 1237 1238************************************************** 1239Starting group: c3c3 1240Order: 3^2 1241Nuclear rank: 3 12423-multiplicator rank: 3 1243Now calling GAP to compute stabiliser... 1244true 1245#I Order of GL subgroup is 48 1246#I No. of soluble autos is 0 1247#I dim U = 1 dim N = 3 dim M = 3 1248#I nice stabilizer with perm rep 1249Now calling GAP to compute stabiliser... 1250true 1251#I Order of GL subgroup is 48 1252#I No. of soluble autos is 0 1253#I dim U = 1 dim N = 3 dim M = 3 1254#I nice stabilizer with perm rep 1255# of immediate descendants of order 3^4 is 3 1256# of capable immediate descendants is 3 1257 1258************************************************** 12593 capable groups saved on file c3c3_class2 1260 1261************************************************** 1262Starting group: c3c3 #1;2 1263Order: 3^4 1264Nuclear rank: 2 12653-multiplicator rank: 3 1266Group c3c3 #1;2 is an invalid starting group 1267 1268************************************************** 1269Starting group: c3c3 #2;2 1270Order: 3^4 1271Nuclear rank: 3 12723-multiplicator rank: 4 1273# of immediate descendants of order 3^7 is 4 1274# of capable immediate descendants is 4 1275 1276************************************************** 1277Starting group: c3c3 #3;2 1278Order: 3^4 1279Nuclear rank: 2 12803-multiplicator rank: 3 1281Group c3c3 #3;2 is an invalid starting group 1282 1283************************************************** 12844 capable groups saved on file c3c3_class3 1285 1286************************************************** 1287Starting group: c3c3 #2;2 #1;3 1288Order: 3^7 1289Nuclear rank: 4 12903-multiplicator rank: 5 1291# of immediate descendants of order 3^8 is 16 1292# of capable immediate descendants is 11 1293 1294************************************************** 1295Starting group: c3c3 #2;2 #2;3 1296Order: 3^7 1297Nuclear rank: 3 12983-multiplicator rank: 4 1299# of immediate descendants of order 3^8 is 13 1300# of capable immediate descendants is 9 1301 1302************************************************** 1303Starting group: c3c3 #2;2 #3;3 1304Order: 3^7 1305Nuclear rank: 3 13063-multiplicator rank: 4 1307# of immediate descendants of order 3^8 is 13 1308# of capable immediate descendants is 9 1309 1310************************************************** 1311Starting group: c3c3 #2;2 #4;3 1312Order: 3^7 1313Nuclear rank: 3 13143-multiplicator rank: 4 1315# of immediate descendants of order 3^8 is 7 1316# of capable immediate descendants is 5 1317 1318************************************************** 131934 capable groups saved on file c3c3_class4 1320Construction of descendants took 69.95 seconds 1321 1322Select option: 0 #exit to basic menu (same as option 7) 1323Exiting from p-group generation 1324 1325Select option: 0 #exit program (same as option 9) 1326Exiting from ANU p-Quotient Program 1327Total user time in seconds is 69.95 1328\end{verbatim} 1329 1330\subsection{A Standard Presentation Menu example} 1331 1332The following example is similar to what is provided by the file \verb|2gp| 1333in the \texttt{isom} directory, except we have added comments, we 1334have not used the \texttt{-k} (keywords) runtime switch and to reduce the 1335output we have only computed the standard presentation to class 3 (instead 1336of class 10, as in the \verb|2gp| example). 1337For this example, the pq program is invoked with the \texttt{-i} runtime 1338switch (see Section~\ref{sec:runtime}), which gives us access to the 1339Standard Presentation Menu (see Section~\ref{sec:stnd-pres-menu}). 1340 1341\begin{verbatim} 1342Standard Presentation Menu 1343----------------------------- 13441. Supply start information 13452. Compute standard presentation to supplied class 13463. Save presentation to file 13474. Display presentation 13485. Set print level for construction 13496. Compare two presentations stored in files 13507. Call p-Quotient menu 13518. Compute the isomorphism 13529. Exit from program 1353 1354Select option: 1 #input group info. 1355Input group identifier: G 1356Input prime: 2 1357Input maximum class: 1 1358Input print level (0-3): 1 #just minimal output 1359Input generating set (in { }): {a, b} 1360Input defining set of relations (in { }): {a^4, b^4 = [b, a, a]} 1361Input exponent law (0 if none): 0 1362 1363Lower exponent-2 central series for G 1364 1365Group: G to lower exponent-2 central class 1 has order 2^2 1366Class 1 2-quotient and its 2-covering group computed in 0.02 seconds 1367 1368Select option: 2 #for standard presentation 1369Enter output file name for group information: 2gp-st 1370Standardise presentation to what class? 3 1371Input the number of automorphisms: 2 1372Now enter the data for automorphism 1 1373Input 2 exponents for image of pcp generator 1: 0 1 1374Input 2 exponents for image of pcp generator 2: 1 1 1375Now enter the data for automorphism 2 1376Input 2 exponents for image of pcp generator 1: 0 1 1377Input 2 exponents for image of pcp generator 2: 1 0 1378PAG-generating sequence for automorphism group? 1 #i.e. ``Yes'' 1379Starting group has order 2^2; its automorphism group order is 6 1380 1381The standard presentation for the class 2 2-quotient is 1382 1383Group: G #1;3 to lower exponent-2 central class 2 has order 2^5 1384 1385Non-trivial powers: 1386 .1^2 = .4 1387 .2^2 = .5 1388 1389Non-trivial commutators: 1390[ .2, .1 ] = .3 1391Its automorphism group has order 384 1392Computing standard presentation for class 2 took 0.08 seconds 1393 1394The standard presentation for the class 3 2-quotient is 1395 1396Group: G #1;3 to lower exponent-2 central class 3 has order 2^8 1397 1398Non-trivial powers: 1399 .1^2 = .4 1400 .2^2 = .5 1401 .3^2 = .6 .8 1402 .5^2 = .6 1403 1404Non-trivial commutators: 1405[ .2, .1 ] = .3 1406[ .3, .1 ] = .6 1407[ .3, .2 ] = .7 1408[ .4, .2 ] = .8 1409[ .5, .1 ] = .6 .7 .8 1410Its automorphism group has order 4096 1411Computing standard presentation for class 3 took 0.12 seconds 1412 1413Select option: 0 #exit (option 9 does this also) 1414\end{verbatim} 1415 1416\subsection{A keywords example} 1417 1418To use keywords you must use the \texttt{-k} runtime switch 1419(see Section~\ref{sec:runtime}). For this example we are again 1420using the Standard Presentation Menu; so we also use the \texttt{-i} runtime 1421switch. The example is \verb|2gp.com| from the \texttt{isom} directory. 1422If the binary for the pq program is \texttt{pq}, then 1423\begin{quote} 1424 \verb|pq -i -k < 2gp.com| 1425\end{quote} 1426in the \texttt{isom} directory yields something like the following output. 1427(The keywords are used in option \texttt{1}; note the ``\texttt{;}'' 1428indicating all remaining data for that option should take default values.) 1429 1430\begin{verbatim} 1431[..Standard Presentation Menu omitted here..] 1432 1433Select option: 1 #set up start information 1434prime 2 #keyword `prime' 1435class 2 #keyword `class' 1436generators {a, b} #keyword `generators' 1437relations {a^4, b^2 = [b, a, b]}; #keyword `relations' (NB: closing `;') 1438 1439Lower exponent-2 central series for G 1440 1441Group: G to lower exponent-2 central class 1 has order 2^2 1442 1443Group: G to lower exponent-2 central class 2 has order 2^4 1444Class 2 2-quotient and its 2-covering group computed in 0.00 seconds 1445 1446Select option: 2 #standardise presentation 1447Enter output file name for group information: Standard 1448Standardise presentation to what class? 10 1449Input the number of automorphisms: 3 1450Now enter the data for automorphism 1 1451Input 4 exponents for image of pcp generator 1: 1 0 0 1 1452Input 4 exponents for image of pcp generator 2: 0 1 0 0 1453Now enter the data for automorphism 2 1454Input 4 exponents for image of pcp generator 1: 1 0 0 0 1455Input 4 exponents for image of pcp generator 2: 0 1 0 1 1456Now enter the data for automorphism 3 1457Input 4 exponents for image of pcp generator 1: 1 1 1 0 1458Input 4 exponents for image of pcp generator 2: 0 1 1 1 1459PAG-generating sequence for automorphism group? 1 1460Starting group has order 2^4; its automorphism group order is at most 96 1461 1462The standard presentation for the class 3 2-quotient is 1463 1464Group: G #1;2 to lower exponent-2 central class 3 has order 2^6 1465 1466Non-trivial powers: 1467 .1^2 = .4 1468 .2^2 = .5 1469 .3^2 = .6 1470 1471Non-trivial commutators: 1472[ .2, .1 ] = .3 1473[ .3, .1 ] = .5 1474[ .3, .2 ] = .6 1475[ .4, .2 ] = .5 .6 1476Its automorphism group has order at most 384 1477Computing standard presentation for class 3 took 0.05 seconds 1478 1479The standard presentation for the class 4 2-quotient is 1480 1481Group: G #1;1 to lower exponent-2 central class 4 has order 2^7 1482[..265 lines omitted here..] 1483 1484The standard presentation for the class 10 2-quotient is 1485 1486Group: G #1;4 to lower exponent-2 central class 10 has order 2^24 1487[..93 lines omitted here..] 1488 1489Its automorphism group has order at most 25769803776 1490Computing standard presentation for class 10 took 0.27 seconds 1491 1492Select option: 4 #display standard presentation for class 10 2-quotient 1493 1494Group: G #1;4 to lower exponent-2 central class 10 has order 2^24 1495 1496Non-trivial powers: 1497 .1^2 = .4 1498 .2^2 = .5 .11 .13 .17 .24 1499 .3^2 = .6 .7 .10 .11 .12 .13 .14 .17 .20 .21 .22 1500 .5^2 = .8 .11 .19 .20 .21 1501 .6^2 = .10 .14 .16 .18 .22 .23 .24 1502 .7^2 = .10 .12 .21 .22 .24 1503 .8^2 = .12 .15 1504 .9^2 = .12 .17 .20 .22 .23 1505 .10^2 = .15 .18 1506 .11^2 = .15 .20 .24 1507 .12^2 = .18 .21 1508 .13^2 = .18 .24 1509 .14^2 = .18 .23 1510 .15^2 = .21 1511 .17^2 = .21 1512 1513Non-trivial commutators: 1514[ .2, .1 ] = .3 1515[ .3, .1 ] = .5 1516[ .3, .2 ] = .6 1517[..71 lines omitted here..] 1518[ .20, .2 ] = .23 1519 1520Select option: 0 #exit 1521Exiting from ANU p-Quotient Program 1522Total user time in seconds is 1.13 1523\end{verbatim} 1524 1525\subsection{A basic format Advanced {\it p}-Group Generation example} 1526 1527With the following example we demonstrate both the use of the \texttt{-b} 1528runtime switch (see Section~\ref{sec:runtime}) and we exercise an 1529Advanced menu. To do something equivalent to what we give below, 1530(assuming the pq binary is \texttt{pq}) do: 1531\begin{quote} 1532 \verb|pq -b < pga_interactive| 1533\end{quote} 1534in the \texttt{examples} directory. 1535 1536\begin{verbatim} 1537[..Basic Menu omitted here..] 1538Select option: 1 #set up group presentation 1539Input group identifier: Nott #our group will be the Nottingham group 1540Input prime: 5 1541Input maximum class: 3 1542Input print level (0-3): 1 #minimal output 1543Input number of generators: 2 #this is the prompt we get with -b 1544Input number of relations: 3 #(ditto) 1545Input exponent law (0 if none): 0 15465 1; #this is the ``basic format'' (-b switch) 1547The input word is 5 1 1548Input right-hand side of relation: 15490; 1550The input word is 0 1551Input left-hand side of relation: 15525 2; 1553The input word is 5 2 1554Input right-hand side of relation: 15550; 1556The input word is 0 1557Input left-hand side of relation: 15581 [2 1 2]; 1559The input word is 1 [ 2 1 2 ] 1560Input right-hand side of relation: 15610; #the final ``basic format'' input needed 1562The input word is 0 1563 1564Lower exponent-5 central series for Nott 1565 1566Group: Nott to lower exponent-5 central class 1 has order 5^2 1567 1568Group: Nott to lower exponent-5 central class 2 has order 5^3 1569 1570Group: Nott to lower exponent-5 central class 3 has order 5^4 1571Computation of presentation took 0.00 seconds 1572 1573Select option: 7 #compute 5-covering group 1574 1575Group: Nott to lower exponent-5 central class 4 has order 5^8 1576Computation of 5-covering group took 0.00 seconds 1577 1578Select option: 2 #save presentation 1579Enter output file name: Nott 1580Presentation written to file 1581 1582Select option: 9 #to (Main) p-Group Generation Menu 1583 1584Menu for p-Group Generation 1585----------------------------- 15861. Read automorphism information for starting group 15872. Extend and display automorphisms 15883. Specify input file and group number 15894. List group presentation 15905. Construct descendants 15916. Advanced p-group generation menu 15927. Exit to basic menu 1593 1594Select option: 1 #define aut. group 1595Input the number of automorphisms: 6 1596Now enter the data for automorphism 1 1597Input 4 exponents for image of pcp generator 1: 1 0 0 0 1598Input 4 exponents for image of pcp generator 2: 0 1 0 1 1599Now enter the data for automorphism 2 1600Input 4 exponents for image of pcp generator 1: 1 1 0 0 1601Input 4 exponents for image of pcp generator 2: 0 1 0 0 1602Now enter the data for automorphism 3 1603Input 4 exponents for image of pcp generator 1: 1 0 0 0 1604Input 4 exponents for image of pcp generator 2: 0 4 0 0 1605Now enter the data for automorphism 4 1606Input 4 exponents for image of pcp generator 1: 1 0 0 0 1607Input 4 exponents for image of pcp generator 2: 0 2 0 0 1608Now enter the data for automorphism 5 1609Input 4 exponents for image of pcp generator 1: 4 0 0 0 1610Input 4 exponents for image of pcp generator 2: 0 1 0 0 1611Now enter the data for automorphism 6 1612Input 4 exponents for image of pcp generator 1: 2 0 0 0 1613Input 4 exponents for image of pcp generator 2: 0 1 0 0 1614Input number of soluble generators for automorphism group: 0 1615 1616Select option: 5 #construct descendants 1617Input class bound on descendants: 4 1618Construct all descendants? 0 #i.e. ``No'' 1619Input step size: 1 1620PAG-generating sequence for automorphism group? 1 #``Yes'' 1621Do you want default algorithm? 0 #``No'' 1622Rank of the initial segment subgroup? 4 1623Space efficient computation? 0 #``No'' 1624Completely process terminal descendants? 0 #``No'' 1625Input exponent law (0 if none): 0 1626Enforce metabelian law? 0 #``No'' 1627Do you want default output? 1 #``Yes'' 1628 1629************************************************** 1630Starting group: Nott 1631Order: 5^4 1632Nuclear rank: 1 16335-multiplicator rank: 4 1634# of immediate descendants of order 5^5 is 9 1635# of capable immediate descendants is 2 1636 1637************************************************** 16382 capable groups saved on file Nott_class4 1639Construction of descendants took 0.02 seconds 1640 1641Select option: 3 #restore group 1642Enter input file name: Nott_class4 1643Which group? 1 1644 1645Select option: 6 #get Advanced p-Group Gen'n Menu 1646 1647Advanced Menu for p-Group Generation 1648------------------------------------- 16491. Read automorphism information for starting group 16502. Extend and display automorphisms 16513. Specify input file and group number 16524. List group presentation 16535. Carry out intermediate stage calculation 16546. Compute definition sets & find degree 16557. Construct permutations of subgroups under automorphisms 16568. Compute and list orbit information 16579. Process all orbit representatives 165810. Process individual orbit representative 165911. Compute label for standard matrix of subgroup 166012. Compute standard matrix for subgroup from label 166113. Find image of allowable subgroup under automorphism 166214. Find rank of closure of initial segment subgroup 166315. List representative and orbit for supplied label 166416. Write compact descriptions of generated groups to file 166517. Find automorphism classes of elements of vector space 166618. Exit to main p-group generation menu 1667 1668Select option: 6 #find degree 1669Input step size: 2 1670Rank of the initial segment subgroup? 3 1671Input exponent law (0 if none): 0 1672Degree of permutation group is 25 1673 1674Select option: 7 #compute permutations 1675PAG-generating sequence for automorphism group? 1 1676Space efficient computation? 0 1677Print automorphism matrices? 0 1678Print permutations? 0 1679Time to compute permutations is 0.00 seconds 1680 1681Select option: 8 #compute orbits 1682PAG-generating sequence for automorphism group? 1 #``Yes'' 1683Space efficient computation? 0 #``No'' 1684Summary of orbit information? 1 #``Yes'' 1685Complete listing of orbits? 0 #``No'' 1686Time to compute orbits is 0.00 seconds 1687 1688 Orbit Length Representative 1689 1 5 1 1690 2 20 2 1691 1692 1693Select option: 9 #compute stabilisers 1694PAG-generating sequence for automorphism group? 1 #``Yes'' 1695Space efficient computation? 0 #``No'' 1696Completely process terminal descendants? 0 #``No'' 1697Input exponent law (0 if none): 0 1698Enforce metabelian law? 0 #``No'' 1699Print standard matrix of allowable subgroup? 0 #``No'' 1700Presentation of reduced p-covering groups? 0 #``No'' 1701Presentation of immediate descendants? 0 #``No'' 1702Print nuclear rank of descendants? 0 #``No'' 1703Print p-multiplicator rank of descendants? 0 #``No'' 1704Print commutator matrix? 0 #``No'' 1705Automorphism group description of descendants? 0 #``No'' 1706Automorphism group order of descendants? 0 #``No'' 1707Enter output file name: X 1708Time to process representative is 0.02 seconds 1709 1710Select option: 3 #restore reduced p-covering group 1711Enter input file name: X 1712Which group? 1 1713 1714Select option: 4 #display presentation 1715 1716Group: Nott #1;1 to lower exponent-5 central class 5 has order 5^9 1717Class 1 17181 is defined on image of defining generator 1 17192 is defined on image of defining generator 2 1720Class 2 17213 is defined on [2, 1] = 2 1 1722Class 3 17234 is defined on [3, 1] = 2 1 1 1724Class 4 17255 is defined on [4, 1] = 2 1 1 1 1726Class 5 17276 is defined on [5, 1] = 2 1 1 1 1 17287 is defined on [5, 2] = 2 1 1 1 2 17298 is defined on 1^5 = 1 1 17309 is defined on 2^5 = 2 2 1731 1732Non-trivial powers: 1733 .1^5 = .8 1734 .2^5 = .9 1735 1736Non-trivial commutators: 1737[ .2, .1 ] = .3 1738[ .3, .1 ] = .4 1739[ .4, .1 ] = .5 1740[ .4, .2 ] = .7 1741[ .4, .3 ] = .7^4 1742[ .5, .1 ] = .6 1743[ .5, .2 ] = .7 1744 1745Select option: 5 #intermediate stage computation 1746Input step size: 2 1747PAG-generating sequence for automorphism group? 1 #``Yes'' 1748Do you want default algorithm? 1 #``Yes'' 1749Do you want default output? 1 #``Yes'' 1750Input output file name: XX 1751 1752************************************************** 1753Starting group: Nott #1;1 1754Order: 5^5 1755Nuclear rank: 2 17565-multiplicator rank: 4 1757# of immediate descendants of order 5^7 is 40 1758# of capable immediate descendants is 5 1759Time for intermediate stage is 0.07 seconds 1760 1761Select option: 0 #exit through 3 levels of menus 1762Exiting from advanced p-group generation menu 1763 1764Select option: 0 1765Exiting from p-group generation 1766 1767Select option: 0 1768Exiting from ANU p-Quotient Program 1769Total user time in seconds is 0.10 1770\end{verbatim} 1771 1772\section{Changes} 1773\begin{description} 1774 \item[\texttt{Version 1.9}]\ \\ 1775 Fixes made to warnings in C code by Max Horn. 1776 \item[\texttt{Version 1.8}]\ \\ 1777 \textsf{GAP} link code updated for \textsf{GAP} 4.4. 1778 \item[\texttt{Version 1.7}]\ \\ 1779 Binomial coefficient algorithm modified to avoid overflow. 1780 \item[\texttt{Version 1.6}]\ \\ 1781 In main Menu for {\it p}-Group Generation, when asking for 1782 automorphisms, now ask for the number of soluble automorphisms 1783 and their relative orders when there are any. 1784 \item[\texttt{Version 1.5}]\ \\ 1785 Added the \texttt{-G} option for use with \textsf{GAP} and the 1786 \texttt{-v} option. 1787\end{description} 1788\pagebreak 1789\section*{\centering References} 1790\addcontentsline{toc}{section}{\numberline{}References} 1791 1792\begin{description} 1793\item George Havas and M.F.\ Newman (1980), ``Application of computers to 1794questions like those of Burnside", {\it Burnside Groups} (Bielefeld, 1977), 1795{\it Lecture Notes in Math.\ }{\bf 806}, pp.\ 211-230. 1796Springer-Verlag, Berlin, Heidelberg, New York. 1797 1798\item M.F.\ Newman (1977), ``Determination of groups of prime-power order", 1799{\it Group Theory} (Canberra, 1975). {\it Lecture Notes in Math.\ }{\bf 573}, 1800pp.\ 73--84. 1801Springer-Verlag. 1802 1803\item M.F.\ Newman and E.A. O'Brien (1996), 1804``Application of computers to questions like those of Burnside, {II}", 1805{\it Internat.\ J.\ Algebra Comput}. {\bf 6}, 593-605. 1806 1807\item E.A.\ O'Brien (1990), ``The {\it p}-group generation 1808algorithm", {\it J.\ Symbolic Comput.} {\bf 9}, 677-698. 1809 1810\item E.A.\ O'Brien (1994), ``Isomorphism testing 1811for \mbox{{\it p}-groups}", {\it J. Symbolic Comput.} {\bf 17}, 1812133--147. 1813 1814\item E.A.\ O'Brien (1995), ``Computing automorphism groups for 1815{\it p}-groups", {\it Computational Algebra and Number Theory} 1816(Sydney, 1992), pp.\ 83--90. Kluwer Academic Publishers, Dordrecht. 1817 1818\item M.R. Vaughan-Lee (1982), ``An Aspect of the Nilpotent 1819Quotient Algorithm", {\it Computational Group Theory} 1820(Durham, 1982), pp. 76--83. Academic Press. 1821 1822\item Michael Vaughan-Lee (1990a), ``The Restricted Burnside Problem", 1823{\it London Mathematical Society monographs (New Ser.)} {\bf 5}. 1824Clarendon Press, New York, Oxford. 1825 1826\item M.R. Vaughan-Lee (1990b), ``Collection from the left", 1827{\it J. Symbolic Comput.} {\bf 9}, 725--733. 1828 1829\end{description} 1830 1831%\vspace*{0.5cm} 1832\noindent 1833Eamonn A.\ O'Brien \\ 1834Department of Mathematics \\ 1835University of Auckland \\ 1836Private Bag 92019, Auckland, New Zealand 1837 1838\vspace*{0.25cm} 1839\noindent 1840E-mail address: obrien@math.auckland.ac.nz 1841 1842\vspace*{0.35cm} 1843\noindent 1844Last revised by Eamonn O'Brien: August 2001\hfil\break\noindent 1845Revised February 2002 (v1.5 GG), February 2004 (v1.6 GG),\hfil\break 1846\hspace*{2em}November 2011 (v1.9 MH), January 2012 (v1.9 GG) 1847\end{document} 1848