1% Twelve point font 2\font\twelverm=cmr12 3\font\twelvei=cmmi12 4\font\twelvesy=cmsy10 scaled \magstep1 5\font\twelveex=cmex10 scaled \magstep1 6\font\twelvebf=cmbx12 7\font\twelvesl=cmsl12 8\font\twelvett=cmtt12 9\font\twelveit=cmti12 10\font\ninerm=cmr9 11\font\ninei=cmmi9 12\font\ninesy=cmsy9 13\font\ninebf=cmbx9 14\font\sevenrm=cmr7 15\font\seveni=cmmi7 16\font\sevensy=cmsy7 17\font\sevenbf=cmbx7 18\def\twelvepoint{\def\rm{\fam0\twelverm} 19 \textfont0=\twelverm \scriptfont0=\ninerm \scriptscriptfont0=\sevenrm 20 \textfont1=\twelvei \scriptfont1=\ninei \scriptscriptfont1=\seveni 21 \textfont2=\twelvesy \scriptfont2=\ninesy \scriptscriptfont2=\sevensy 22 \textfont3=\twelveex \scriptfont3=\twelveex\scriptscriptfont3=\twelveex 23 \textfont\itfam=\twelveit \def\it{\fam\itfam\twelveit}% 24 \textfont\slfam=\twelvesl \def\sl{\fam\slfam\twelvesl}% 25 \textfont\ttfam=\twelvett \def\tt{\fam\ttfam\twelvett}% 26 \textfont\bffam=\twelvebf \scriptfont\bffam=\ninebf 27 \scriptscriptfont\bffam=\sevenbf \def\bf{\fam\bffam\twelvebf}% 28 \normalbaselineskip=14pt 29 \setbox\strutbox=\hbox{\vrule height9.5pt depth4.5pt width0pt}% 30 \normalbaselines\rm} 31% 32% 11 point font 33\font\elevenrm=cmr10 scaled \magstephalf 34\font\eleveni=cmmi10 scaled \magstephalf 35\font\elevensy=cmsy10 scaled \magstephalf 36\font\elevenex=cmex10 scaled \magstephalf 37\font\elevenbf=cmbx10 scaled \magstephalf 38\font\elevensl=cmsl10 scaled \magstephalf 39\font\eleventt=cmtt10 scaled \magstephalf 40\font\elevenit=cmti10 scaled \magstephalf 41\font\eightrm=cmr8 42\font\eighti=cmmi8 43\font\eightsy=cmsy8 44\font\eightbf=cmbx8 45\font\sixrm=cmr6 46\font\sixi=cmmi6 47\font\sixsy=cmsy6 48\font\sixbf=cmbx6 49\def\elevenpoint{\def\rm{\fam0\elevenrm}% switch to 11-point type 50 \textfont0=\elevenrm \scriptfont0=\eightrm \scriptscriptfont0=\sixrm 51 \textfont1=\eleveni \scriptfont1=\eighti \scriptscriptfont1=\sixi 52 \textfont2=\elevensy \scriptfont2=\eightsy \scriptscriptfont2=\sixsy 53 \textfont3=\elevenex \scriptfont3=\elevenex\scriptscriptfont3=\elevenex 54 \textfont\itfam=\elevenit \def\it{\fam\itfam\elevenit}% 55 \textfont\slfam=\elevensl \def\sl{\fam\slfam\elevensl}% 56 \textfont\ttfam=\eleventt \def\tt{\fam\ttfam\eleventt}% 57 \textfont\bffam=\elevenbf \scriptfont\bffam=\eightbf 58 \scriptscriptfont\bffam=\sixbf \def\bf{\fam\bffam\elevenbf}% 59 \normalbaselineskip=13pt 60 \setbox\strutbox=\hbox{\vrule height9pt depth4pt width0pt}% 61 \normalbaselines\rm} 62% 63\twelvepoint 64\parindent=0pt 65\raggedbottom 66 67% Make headline containing the date of the license agreement (see COPYING.guava) 68\def\makeheadline{\vbox to 0pt{\vskip-45pt 69 \line{\vbox to 8.5pt{}\hskip-40pt\fiverm{04}/{17}/{2007}\hfil}\vss} 70 \nointerlineskip} 71% 72\def\makeactive#1{\catcode`#1 = \active \ignorespaces}% 73\chardef\letter = 11 \chardef\other = 12 74\catcode`@=\letter 75\def\alwaysspace{\hglue\fontdimen2\the\font \relax}% 76{\makeactive\^^M \makeactive\ % 77\gdef\obeywhitespace{% 78\makeactive\^^M\def^^M{\par\indent}% 79\aftergroup\@removebox% 80\makeactive\ \let =\alwaysspace}}% 81\def\@removebox{\setbox0=\lastbox} 82% 83\font\titlefont=cmbx10 scaled\magstep4 84\font\authorfont=cmr12 scaled\magstep1 85\font\sectionheaderfont=cmbx12 scaled\magstep1 86\font\subsectionheaderfont=cmbx12 87\def\filenamefont{\tt} 88% 89\long\def\section#1{\bigbigbreak{\sectionheaderfont #1}\nobreak\medskip\nobreak} 90\long\def\subsection#1{\bigbreak{\subsectionheaderfont #1}\hskip0.75em} 91\def\twocols#1#2{\hskip0.45truein\hbox to 3.0truein{#1\hfil}\hskip0.4truein\relax 92 \hbox to 2.45truein{#2\hfil}\hfil} 93\long\def\objectfile#1{{\elevenpoint\obeylines\obeyspaces\tt\ttraggedright 94 #1\vskip0pt}} 95\newdimen\optionIndent\optionIndent=1.1in 96\long\def\defoption#1#2{{\advance\leftskip by1em\advance\leftskip by\optionIndent 97 \noindent\llap{\hbox to\optionIndent{\tt #1\hfil}}#2\vskip0pt}} 98% 99\def\germR{\underline{{\rm R}}} 100\def\bfgermR{\underline{{\bf R}}} 101% 102\def\options{{\rm [}{\it options\/}{\rm ]}} 103% 104\newskip\bigbigskipamount \bigbigskipamount=20pt plus 7pt minus 5pt 105\def\bigbigskip{\vskip\bigbigskipamount} 106\def\bigbigbreak{\par\ifdim\lastskip<\bigbigskipamount 107 \removelastskip\penalty-300\bigbigskip\fi} 108\multiply\smallskipamount by4\divide\smallskipamount by3 109\multiply\medskipamount by4\divide\medskipamount by3 110\multiply\bigskipamount by4\divide\bigskipamount by3 111\multiply\bigbigskipamount by4\divide\bigbigskipamount by3 112% 113\pageno=1 114\centerline{{\titlefont PARTITION BACKTRACK PROGRAMS:}} 115\vskip10pt 116\centerline{{\titlefont USER'S MANUAL}} 117\vskip35pt 118\centerline{{\authorfont JEFFREY S. LEON}} 119\vskip6pt 120\centerline{Mathmatics Dept, m/c 249} 121\centerline{University of Illinois at Chicago} 122\centerline{Box 4348} 123\centerline{Chicago, IL 60680} 124\vskip40pt 125% 126\section{I.\quad INTRODUCTION} 127% 128This document describes a collection of programs for permutation group 129computations employing the partition backtrack method, as described in a 130recent article by the author (Leon, 1991). At present, these programs 131perform the following computations: 132\medskip 133\twocols{set stabilizers,}{set images (see below),} 134\vskip4pt 135\twocols{ordered partition stabilizers,}{ordered partition images,} 136\vskip4pt 137\twocols{intersections,}{} 138\vskip4pt 139\twocols{centralizers (of elements),}{conjugacy (of elements),} 140\vskip4pt 141\twocols{centralizers (of subgroups),}{} 142\vskip4pt 143\twocols{automorphism groups of designs,}{isomorphism of designs,} 144\vskip4pt 145\twocols{automorphism groups of matrices,}{isomorphism of matrices,} 146\vskip4pt 147\twocols{monomial automorphism groups of}{monomial isomorphism of matrices} 148\vskip-1.5pt 149\twocols{matrices over small fields,}{over small fields,} 150\vskip4pt 151\twocols{automorphism groups of linear codes,}{isomorphism of linear codes.} 152\medbreak 153The term {\it set image} problem is used here to refer to the following 154problem: Given a permutation group 155$G$ and subsets $\Lambda$ and $\Phi$ of the domain, determine if there exists 156$g \in G$ such that $\Lambda^g = \Phi$. The ordered partition image problem is 157defined analogously. The term {\it design\/} is used here to refer to any 158collection of points and blocks. An automorphism of a matrix is any permutation 159of the rows and columns that leaves the matrix invariant; two matrices are 160isomorphic if one may be transformed to the other by permutation of rows and 161columns. For monomial automorphism groups and monomial isomorphism, the matrix entries 162must be taken from a finite field; in addition to permutation of rows and 163columns, we allow each row and each column to be multiplied by a nonzero 164field element. 165% 166\medbreak 167Note that each of the problems in the first column above involves 168computation of a subgroup; these problems will be referred to 169as {\it subgroup computations}. For each problem 170in the second column, the set of permutations having the desired property 171either is empty or forms a right coset of an appropriate subgroup; we are 172seeking one coset representative (if it exists). These problems 173will be referred to as {\it coset representative computations}. 174% 175\medbreak 176Some of the programs described here can be used to compute in groups of 177relatively high degree, considerably higher than those that can be 178handled by programs based on conventional algorithms. 179However, it should be kept mind that the programs are new. 180All appear to work correctly, but most have not 181been thoroughly tested, especially on intransitive groups. (The set 182stabilizer program has been tested the most thoroughly, and in general those 183for subgroup computations have received more testing than those for coset 184representative calculations.) The author would appreciate any reports of errors; they 185may be sent to {\tt leon@turing.math.uic.edu}. 186\medbreak 187Work on programs for the following computations is in progress: 188\medskip 189\twocols{unordered partition stabilizers,}{unordered partition images,} 190\vskip4pt 191\twocols{normalizers,}{conjugacy (of subgroups),} 192\vskip4pt 193\twocols{}{coset intersections,} 194\medbreak 195In the course of constructing test cases for the partition backtrack programs 196and verifying their output, 197the author has developed several other programs, not based on backtrack search. 198These programs are described briefly in Section~IX. Many of these programs 199were put together quickly, with a view toward simplicity rather than 200efficiency and ease of use. 201\medbreak 202At present, the programs run on the following machines: The Sun/3, the Sun/4, 203the IBM~3090, and the IBM~PC. Two versions are available for the IBM~PC: a standard version, 204which is limited to groups of degree no more than 1000 (roughly) due 205to the 640K memory limitation, and a 386/486 version using a DOS extender, that 206can handle larger groups. The source code for all programs is written 207entirely in C and, with very minor exceptions, conforms to the ANSI 208standard. The programs should compile, with minimal changes, with 209any C compiler fully supporting the ANSI standard. The Sun/3 and Sun/4 210versions have been compiled with the GNU C compiler, the IBM~3090 version with the 211Waterloo~C compiler, and the IBM/PC versions with the Borland C++ and 212Zortech C++ compilers (both configured as C compilers). 213% 214% 215\section{II.\quad OBJECTS AND FILE FORMATS} 216% 217At present, the programs compute with objects of seven types: Permutation 218groups, permutations, point sets, partitions (ordered or unordered), 219block designs, matrices, and linear codes. Each object used as 220input by the programs is read from a file. Likewise, each object constructed 221by the programs is written to a file. All of these files 222are ordinary text files. The format of the files is designed for 223compatibility with Cayley (Cannon, 1984); it is that of a Cayley library, 224with certain restrictions added. Essentially, the restrictions say that 225the library may contain only statements defining the object, and (at present) 226that only certain attributes of the object may specified in the library. 227(Many of the permutation group libraries distributed with Cayley conform 228to these restrictions.) Thus objects constructed by these programs 229described here may be read into Cayley for further investigation. 230Likewise, objects defined in existing Cayley libraries may, in many cases, 231be used as input to the programs described here. An alternative format, 232compatible with Gap, may be added at a later date. 233\medbreak 234The examples which follow illustrate the correct format for these object files. 235Note that the contents of the files is case--insensitive; upper and lower case 236letters may be used interchangeably. (However, the names of the files may 237be case--sensitive, depending on the operating system.) Also, the 238use of white space (blanks, tabs, newline characters) is optional: Except 239within integers and identifiers, any number of whitespace characters may 240occur. Text enclosed by ampersands or quotation marks is treated as a comment. 241% 242\subsection{a)\enskip Permutation groups:}The format for permutation group files 243is illustrated by following file, named {\filenamefont psp62}, which defines 244${\rm PSp}_6(2)$ as a permutation group 245on nonzero vectors (degree 63). 246\medbreak 247\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 248LIBRARY psp62; 249" PSp(6,2) acting on nonzero vectors, degree 63." 250psp62: permutation group(63); 251psp62.forder: 2^9 * 3^4 * 5 * 7; 252psp62.generators: 253 a = (1,2)(3,5)(4,7)(8,12)(11,16)(13,19)(17,18)(20,26)(21,28)(23,30)(24,32) 254 (25,34)(29,37)(31,40)(33,43)(36,46)(38,41)(39,49)(42,44)(45,52)(48,51) 255 (53,58)(57,62)(59,61), 256 b = (1,3,6,10,15,22)(2,4,8,13,20,27)(5,9,14,21,29,38)(7,11,17,23,31,41) 257 (12,18,24,33,44,34)(16,19,25)(26,35,45,53,32,42)(28,36,47)(30,39,50, 258 56,61,58)(37,48)(40,51,46,54,59,62)(49,55,60,63,52,57); 259FINISH;\vskip0pt}} 260\medbreak 261The line specifying the factored group order may be omitted; however, since the 262random Schreier method is currently used to construct a base and strong 263generating set for the group, there is a possibility (probably small) that 264the group may be generated incorrectly if this line is removed. 265When generators are written in cycle format, as above, inclusion of cycles 266of length one is optional. (For compatibility with Cayley, they should be 267omitted.) 268It is also 269possible to write the generators in image (rather than cycle) format; in 270this case, the file shown above would become: 271\medbreak 272\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 273LIBRARY psp62; 274" PSp(6,2) acting on nonzero vectors, degree 63." 275psp62: permutation group(63); 276psp62.forder: 2^9 * 3^4 * 5 * 7; 277psp62.generators: 278 a = /2,1,5,7,3,6,4,12,9,10,16,8,19,14,15,11,18,17,13,26,28,22,30, 279 32,34,20,27,21,37,23,40,24,43,25,35,46,29,41,49,31,38,44,33,42, 280 52,36,47,51,39,50,48,45,58,54,55,56,62,53,61,60,59,57,63/, 281 b = /3,4,6,8,9,10,11,13,14,15,17,18,20,21,22,19,23,24,25,27,29,1, 282 31,33,16,35,2,36,38,39,41,42,44,12,45,47,48,5,50,51,7,26,43,34, 283 53,54,28,37,55,56,46,57,32,59,60,61,49,30,62,63,58,40,52/; 284FINISH;\vskip0pt}} 285\medbreak 286Finally, if a base and strong generating set for the group are already 287known, they may be included in the file. This eliminates the need for 288the programs to first construct a base and strong generating set for 289the input group. The file format is then as follows. 290\nobreak\medskip\nobreak 291\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 292LIBRARY psp62; 293" PSp(6,2) acting on nonzero vectors, degree 63." 294psp62: permutation group(63); 295psp62.forder: 2^9 * 3^4 * 5 * 7; 296psp62.base: seq(1,3,6,2,4,5); 297psp62.strong generators: [ 298 x01 = (1,3)(4,27)(5,9)(7,45)(10,48)(11,17)(12,34)(13,20)(14,25)(15, 299 39)(16,63)(19,60)(21,55)(22,58)(23,28)(24,37)(31,53)(32,47)(33, 300 61)(36,42)(38,49)(44,50)(51,62)(54,59), 301 x02 = (2,16)(3,6)(5,55)(8,21)(9,40)(13,51)(14,46)(15,47)(17,44)(19, 302 59)(20,29)(22,36)(23,58)(24,61)(25,63)(26,37)(27,60)(31,50)(32, 303 48)(33,41)(34,56)(38,57)(43,45)(52,62), 304 . 305 . 306 307 x12 = (5,51)(7,12)(8,29)(9,62)(10,42)(13,55)(15,23)(18,35)(20,21) 308 (22,32)(28,39)(34,45)(36,48)(40,52)(43,56)(47,58)]; 309FINISH;\vskip0pt}} 310\medbreak 311(The vertical dots indicated that part of the file has been omitted.) 312When a base and strong generating set are given, inclusion of the factored 313order of the group is purely optional. 314At present it is {\it not} possible to specify both generators and a base and 315strong generating set for a group. (This obviously undesirable restriction 316will be removed eventually.) 317% 318\subsection{b)\enskip Permutations:}The format for permutation files 319is illustrated by following file, named {\filenamefont g}, which defines a permutation of 320$g$ of degree 63 and order 4, which turns out to lie in the group 321${\rm PSp}_6(2)$ given above. 322\medbreak 323\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 324LIBRARY g; 325" An element of order 4 in the group psp62 above." 326g = (1,40,50,6)(2,58,18,34)(3,8,44,30)(4,10,15,48)(5,11)(7,60,38,32) 327 (12,46,22,56)(13,62,20,61)(16,42,36,63)(19,49,47,45)(21,53,31, 328 55)(24,33,37,51)(25,28)(26,52)(27,59,39,54)(29,41); 329FINISH;\vskip0pt}} 330\medbreak 331As with generators for permutation groups, permutations may be written in 332image format, rather than cycle format. Note that, when cycle format is used, 333the file contains no explicit indication of the degree of the permutation. 334Thus, for example, the permutation {\tt g} above could be used wherever a 335permutation of degree 63 (the largest point appearing explicitly) or greater 336is expected. 337\medbreak 338Given the files above, the centralizer in ${\rm PSp}_6(2)$ of $g$ could be 339computed by the command 340\smallskip 341\hskip0.45truein{\tt cent\quad psp62\quad g\quad C} 342\smallskip 343which would save the centralizer (in the format described in part~(a) above) 344in the file {\filenamefont C}. 345% 346\subsection{c)\enskip Point sets:}The format for point sets is illustrated 347by following file, named {\filenamefont lambda}, which defines a subset $\Lambda$ of 348$\{1,\ldots,63\}$. 349\medbreak 350\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 351LIBRARY lambda; 352" A subset of {1,...,63} of size 31." 353lambda = [10,16,44,3,5,33,48,63,56,50,6,52,55,19,34,25,2,35,17,40,21, 354 58,49,36,39,12,60,30,15,29,37]; 355FINISH;\vskip0pt}} 356\medbreak 357Note that there is no explicit indication of the size 358of the base set. Thus the set {\tt lambda} above could be used wherever 359a subset of $\{1,\ldots,m\}$ is expected for any $m$ with $m \geq 63$ 360(the largest point appearing explicitly). 361\medbreak 362The set stabilizer in ${\rm PSp}_6(2)$ of $\Lambda$ could be computed 363by the command 364\smallskip 365\hskip0.45truein{\tt setstab\quad psp62\quad lambda\quad S} 366\smallskip 367which would save the stabilizer in the file {\filenamefont S}. 368% 369\subsection{d)\enskip Partitions:}The format for partitions (ordered or 370unordered) is illustrated 371by following file, named {\filenamefont pi}, which defines a partition 372$\Pi$ of $\{1,\ldots,63\}$. 373\medbreak 374\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 375LIBRARY pi; 376" An (ordered or unordered) partition of 1,...,63 having four " 377" cells of sizes 15, 20, 13, and 15. respectively." 378pi = seq([1,34,28,48,37,41,13,54,57,51,4,38,8,46,16],[2,40,21, 379 18,6,53,30,56,42,12,3,11,33,15,32,5,60,31,55,63],[7, 380 36,25,29,35,9,26,49,14,47,10,24,43],[17,58,52,50,59, 381 45,20,61,23,39,44,19,22,62,27]); 382FINISH;\vskip0pt}} 383\medbreak 384Note that the individual cells are delimited by square brackets. 385Note also that the file contains no indication whether the partition is ordered 386or unordered; rather each program operating on partitions interprets the 387partition as ordered or unordered, whichever is appropriate for the the 388program. 389\medbreak 390The stabilizer in ${\rm PSp}_6(2)$ of $\Pi$, interpreted as an ordered 391partition, could be computed by the command 392\smallskip 393\hskip0.45truein{\tt parstab\quad psp62\quad pi\quad T} 394\smallskip 395which saves the stabilizer in the file {\filenamefont T}. 396% 397\subsection{e)\enskip Block designs:}Here a block design refers to any 398collection of subsets of $\{1,\ldots,n\}$; it is even possible to have 399repeated blocks, i.e., two different blocks containing exactly the same points. 400(If repeated blocks occur, we require that an automorphism preserve 401multiplicities.) The file format for block designs 402is illustrated by following file, named {\filenamefont d17}, which defines 403a block design $D_{17}$ with 17 points and with 34 blocks, each of size 5. 404\medbreak 405\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 406LIBRARY d17; 407" The design with 17 points and 34 blocks, each containing " 408" 5 points, obtained from the codewords of weight 5 in the " 409" quadratic residue code of length 17 and dimension 9." 410d17 = seq( 17, 34, 411 [3,6,8,15,17], [1,4,7,9,16], [1,4,5,11,17], 412 [2,5,8,10,17], [3,4,7,8,14], [1,2,5,6,12], 413 [1,4,6,13,15], [1,3,6,9,11], [1,3,10,12,15], 414 [3,5,8,11,13], [2,8,9,12,13], [1,7,13,14,17], 415 [6,8,11,14,16], [4,5,8,9,15], [2,5,7,14,16], 416 [2,3,6,7,13], [3,4,10,16,17], [3,5,12,14,17], 417 [1,7,8,11,12], [5,7,10,13,15], [6,12,13,16,17], 418 [2,4,7,10,12], [2,9,11,14,17], [2,3,9,15,16], 419 [2,4,11,13,16], [6,7,10,11,17], [4,6,9,12,14], 420 [5,11,12,15,16], [1,8,10,13,16], [1,2,8,14,15], 421 [5,6,9,10,16], [4,10,11,14,15], [7,9,12,15,17], 422 [3,9,10,13,14] ); 423FINISH;\vskip0pt}} 424\medbreak 425Note that the file contains the number of points, followed by the number 426of blocks, followed by a listing of the blocks. Each block is delimited 427by square brackets. 428\medbreak 429The automorphism group of this block design could be computed by the command 430\smallskip 431\hskip0.45truein{\tt desauto\quad d17\quad A} 432\smallskip 433which saves the automorphism group in the file {\filenamefont A}. 434% 435\subsection{f)\enskip Matrices:}Here a matrix is merely a $k\times n$ 436array of integers, each in the set $\{0,\ldots,q-1\}$ for some $k$, $n$, and 437$q$. (At present, $q$ cannot exceed 256; this limit could be raised, at the 438cost of additional space, by minor changes to the source code.) 439The file format for matrices is 440illustrated by following file, named {\filenamefont m17}, 441which represents incidence matrix $M_{17}$ for the block design $D_{17}$ 442in part~(e) above. (In the incidence matrix, rows correspond to points and 443columns to blocks.) 444\medbreak 445\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 446LIBRARY m17; 447" The incidence matrix of d17." 448m17 = seq( 2, 17, 34, seq( 449 0,1,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0, 450 0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0, 451 1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1, 452 0,1,1,0,1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0, 453 0,0,1,1,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0, 454 1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0, 455 0,1,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,0, 456 1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0, 457 0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,0,1,1, 458 0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1, 459 0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0, 460 0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0, 461 0,0,0,0,0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,1,1,0,0,0,1,0,0,0,1,0,0,0,0,1, 462 0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,1, 463 1,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,1,0, 464 0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,0, 465 1,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,1,0 466 )); 467FINISH;\vskip0pt}} 468\medbreak 469Note that the file contains the set size $q$, followed by the number $k$ of rows, 470followed by the number $n$ of columns, followed by the entries of the matrix 471listed in row--major order. Note that matrix entries are not, in general, 472limited to 0 and 1; if $q$ is the set size, matrix entries may be integers 473in the range 0 through $q-1$. 474\medbreak 475The automorphism group of this matrix could be computed by the command 476\smallskip 477\hskip0.45truein{\tt matauto\quad m17\quad B} 478\smallskip 479which saves the automorphism group in the file {\filenamefont B}. 480\medbreak 481Matrices may also be specified using an alternate format, which is not 482compatible with Cayley, but which saves considerable space for large 483matrices.\footnote{${}^{\dag}$}{\elevenpoint At time of writing, the alternate format does not work 484correctly on some machines.} This alternate format is available only when the set size $q$ is 485at most 9. Using the alternate format, the matrix $M_{17}$ would be 486specified by a file as follows: 487\medbreak 488\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 489m17 4902 17 34 4910110011110010000001000000000110000 4920001010000100011000001111000010000 4931000100111000001110000010000000001 4940110101000000100100001001010000100 4950011010001000110010100000001001000 4961000011100001001000010000110001000 4970100100000010011001101000100000010 4981001100001101100001000000000110000 4990100000100100100000000110010001011 5000001000010000000100101000100101101 5010010000101001000001000101101000100 5020000010010100000011011000011000010 5030000001001110001000110001000100001 5040000100000011010010000100010010101 5051000001010000100000100010001010110 5060100000000001010100010011001101000 5071011000000010000110010100100000010 508\vskip0pt}} 509\medbreak 510With the alternate format, blanks may occur between matrix entries, but 511are not required. The first line of the file is reserved for the matrix 512name; nothing else may be placed on this line. 513% 514\subsection{g)\enskip Linear codes:} 515The file format for lines codes is 516illustrated by following file, named {\filenamefont q17}, which represents the 517binary (17,9)--quadratic residue code $Q_{17}$ mentioned in part~(e) above. 518This file gives a generator matrix for the code, in the format of 519part~(f) above. 520\medbreak 521\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 522LIBRARY q17; 523" The (17,9) binary quadratic residue code." 524q17 = seq( 2, 9, 17, seq( 525 1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1, 526 1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1, 527 1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0, 528 0,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1, 529 1,0,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0, 530 0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,0,0, 531 0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,0, 532 0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1, 533 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 534 )); 535FINISH;\vskip0pt}} 536\medbreak 537Note that the file contains the size of the field for the code, followed by the 538dimension of the code, followed by the 539length of the code, followed by a generator matrix whose entries are 540listed in row--major order. At present, the field size is restricted to 541a prime integer (less than 255) or to 4; automorphism group and isomorphism 542calculations are practical only when the field size is quite small. 543 In the case of a prime, the field 544is taken as the integers modulo that prime. 545\medbreak 546The automorphism group of this code could be computed by the command 547\smallskip 548\hskip0.45truein{\tt codeauto\quad q17\quad v17\quad H} 549\smallskip 550which saves the automorphism group as the group {\filenamefont H}. 551(Here file {\filenamefont v17} defines a matrix $V_{17}$ which is the 552transpose of the matrix $M_{17}$ of part~(f) above; the role of 553$V_{17}$ will be explained later.) 554\medbreak 555As with matrices, an alternate (not Cayley--compatible) format is provided 556for codes over field of size at most 9.\footnote{${}^{\dag}$}{\elevenpoint As with matrices, this 557alternate format at present fails to work correctly on some machines.} 558With the alternate format, the file defining the code $Q_{17}$ 559would be as follows: 560\medbreak 561\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 562q17 5632 9 17 56411101000110001011 56511110100011000101 56611111010001100010 56701111101000110001 56810111110100011000 56901011111010001100 57000101111101000110 57100010111110100011 57211111111111111111 573\vskip0pt}} 574\bigbreak 575\hrule 576\bigbigbreak 577In the examples above, it was assumed that the name of file matched the 578name of the Cayley library that it contained. Although this is 579recommended for simplicity, it need not be the case. When the names 580do not match, an object is specified using the format 581\hbox{{\it fileName\/}{\tt ::}{\it libraryName\/}}. For example, if the file 582{\filenamefont psp62} in part~(a) above were renamed {\filenamefont psp} 583and the file {\filenamefont g} in part~(b) were named {\filenamefont pspx4}, 584but if the contents of both files remained unchanged, the command to 585compute the centralizer in ${\rm PSp}_6(2)$ of $g$ might be 586\smallskip 587\hskip0.45truein{\tt cent\quad psp::psp62\quad pspx4::g\quad gCentr::C} 588\smallskip 589where now the centralizer is saved in the file {\filenamefont gCentr}, but in a 590Cayley library named {\tt C}. A path may also be specified, for example, 591\smallskip 592\hskip0.45in{\tt cent\quad ../groups/psp::psp62\quad ../groups/pspx4::g\quad gCentr::C} 593\smallskip 594in Unix. (In MS~DOS on the IBM~PC, the forward slash must be replaced 595by a backslash. Under CMS on the IBM~370, the file name and file type must 596be separated by a period, rather than the blank normally used under CMS.) 597If however, the file name and the library name for input files 598differ only in that the file name contains path information, the 599{\tt -p} option (discussed later) may be useful. 600% 601\medbreak 602In the examples above, not only did the file name and the Cayley library 603name match, but both matched the actual name for the object appearing in 604the Cayley library. Actually, the name for the object need not be 605related to the name of the Cayley library. For example, the following 606is acceptable. 607\medbreak 608\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 609LIBRARY psp62; 610" PSp(6,2) acting on nonzero vectors, degree 63." 611G: permutation group(63); 612G.forder: 2^9 * 3^4 * 5 * 7; 613G.generators: 614 a = (1,2)(3,5)(4,7)(8,12)(11,16)(13,19)(17,18)(20,26)(21,28)(23,30)(24,32) 615 (25,34)(29,37)(31,40)(33,43)(36,46)(38,41)(39,49)(42,44)(45,52)(48,51) 616 (53,58)(57,62)(59,61), 617 b = (1,3,6,10,15,22)(2,4,8,13,20,27)(5,9,14,21,29,38)(7,11,17,23,31,41) 618 (12,18,24,33,44,34)(16,19,25)(26,35,45,53,32,42)(28,36,47)(30,39,50, 619 56,61,58)(37,48)(40,51,46,54,59,62)(49,55,60,63,52,57); 620FINISH;\vskip0pt}} 621\medbreak 622In this situation, the command line must still specify the Cayley library name 623(and file name, if different), but informative messages printed as the 624command executes use the object name ({\tt G}, in this case). For 625objects created by commands, an object name different from the Cayley 626library name may be specified by means of the {\tt -n} option, discussed 627later. 628% 629% 630\section{III.\quad\kern-3pt FIELDS, MONOMIAL PERMUTATIONS, AND MATRICES\kern-2pt} 631% 632This section treats several topics that arise primarily in connection 633with computations involving combinatorial structures -- designs, matrices, 634and codes. 635% 636\subsection{i)\enskip Finite fields:}Finite fields arise when computing with 637codes, or with matrices whose entries belong to the field. At present, only 638fields ${\rm GF}(q)$ whose order $q$ is either 4 or a prime integer are 639supported; moreover, we must have $q\leq 255$. (For automorphism 640group and isomorphism calculations, time and space considerations generally 641dictate a practical limit on $q$ that is far lower.) Field elements are 642numbered $0,1,\ldots,q-1$. When $q$ is prime, the field is taken as the 643integers modulo $q$. When $q=4$, there is an essentially unique way to 644number the field elements. 645\smallbreak 646We denote the set of nonzero elements of 647${\rm GF}(q)$ by ${\rm GF}(q)^{\#}$. 648\bigbreak 649\subsection{ii)\enskip Monomial permutations:}Given a fixed field 650${\rm GF}(q)$, a monomial permutation of monomial degree $n$ over 651${\rm GF}(q)$ is essentially a permutation $s$ on 652${\rm GF}(q)^{\#} \times \{1,\ldots,n\}$ which satisfies the following property, 653henceforth referred to as the {\it monomial property:\/} 654$$\displaylines{(\alpha,i)^s = (\beta,j)\quad {\rm implies}\quad 655 (\gamma\alpha,i)^s = (\gamma\beta,j)\kern40pt\cr\kern40pt 656 {\rm \hbox{for all}}\enskip 657 \alpha,\beta,\gamma\in {\rm GF}(q)^{\#}\enskip {\rm and}\enskip 658 i,j\in\{1,\ldots,n\}.\cr}$$ 659Note that $s$ is determined completely by its action on the points $(1,i)$, 660$1\leq i\leq n$; note also that the actual degree of $s$ is $(q-1)n$. 661\smallbreak 662For purposes of actual computation, however, we want 663a representation of $s$ as a 664permutation on $\{1,\ldots,(q-1)n\}$; to obtain this, 665we number the pair $(\alpha,i)$ by 666$(q-1)(i-1)+\overline{\alpha}$, where $\overline{\alpha}$ denotes the integer 667representing $\alpha$. Then the monomial property becomes 668$$\displaylines{\bigl((q-1)(i-1)+\overline{\alpha}\bigr)^s = 669(q-1)(j-1)+\overline{\beta}\quad{\rm implies}\kern40pt\cr 670 \kern40pt\bigl((q-1)(i-1)+\overline{\gamma\alpha}\bigr)^s = 671(q-1)(j-1)+\overline{\gamma\beta}.\cr}$$ 672\medbreak 673For example, over the field ${\rm GF}(4)$, the monomial permutation $s$ on 674${\rm GF}(4) \times \{1,2,3,4\}$ determined by 675$$ (1,1)^s = (3,2),\quad (1,2)^s = (2,4),\quad (1,3)^s = (1,1),\quad 676 (1,4)^s = (2,3)$$ 677is represented as a permutation on $\{1,\ldots,12\}$ as follows: 678$$(1,6,10,8,2,4,11,9,3,5,12,7).$$ 679% 680\bigbreak 681\subsection{iii)\enskip Permutations acting on matrices:}Let 682$A = (a_{ij})$ be an $r \times c$ matrix with entries from an arbitrary set. 683A permutation $s$ of degree $r+c$ which fixes $\{1,\ldots,r\}$ setwise 684induces an action on $A$ as follows: Row $i$ of $A$ is moved to row position $i^s$\enskip 685$(1\leq i\leq r)$ and column $j$ of $A$ is moved to column position 686$(r+j)^s-r$\enskip $(1\leq j\leq c)$. Thus 687$$A^s = (b_{ij}),\quad {\rm where}\quad 688 b_{ij} = a_{i^\prime j^\prime},\enskip {\rm with}\enskip 689 i^\prime = i^{s^{-1}}\enskip {\rm and}\enskip 690 j^\prime = (r+j)^{s^{-1}}-r.$$ 691If $A^s = B$, we say that $s$ is an {\it isomorphism\/} of $A$ to $B$. When 692$A^s=A$,\enskip $s$ is called an {\it automorphism\/} of $A$. The group formed by 693the automorphisms is called the {\it automorphism group\/} of $A$, and denoted 694${\rm AUT}(A)$. 695\medbreak 696For example, the action of a permutation $s$ of degree 7 on a $3\times 4$ 697matrix $A$ is illustrated by the following. 698$$s = (1,3,2)(4,7,5),\qquad 699 A = \pmatrix{8&0&4&3\cr 700 2&9&3&0\cr 701 0&1&7&5\cr},\qquad 702 A^s = \pmatrix{9&0&3&2\cr 703 1&5&7&0\cr 704 0&3&4&8\cr}.$$ 705% 706\bigbreak 707\subsection{iv)\enskip Monomial permutations acting on matrices:}Now let 708$A = (a_{ij})$ be an $r \times c$ matrix with entries from a field 709${\rm GF}(q)$. A monomial permutation $s$ of monomial degree $r+c\kern3pt$ 710(actual degree $(q-1)(r+c)\kern2pt)$ which fixes $\{1,\ldots,(q-1)r\}$ setwise 711induces an action on $A$. This action is most easily described if we think of $s$ as 712a permutation on ${\rm GF}(q)^{\#} \times \{1,\ldots,n\}$, as in~(ii) above; 713then $s$ fixes $\{(\alpha,i)\vert \alpha\in{\rm GF}(q)^{\#},1\leq i\leq r\}$ 714setwise. If $(1,i)^s = (\alpha,k)$ and $(1,r+j)^s = (\beta,r+m)$, 715then row $i$ of $A$ is multiplied by $\alpha$ and moved to row position $k$,\enskip 716and column $j$ of $A$ is multiplied by $\beta$ and moved to column position 717$m$. Thus 718$$ A^s = (b_{ij}),\quad {\rm where}\quad 719 b_{ij} = \lambda^{-1}\mu^{-1}a_{i^\prime j^\prime},$$ 720with $\lambda$, $\mu$, $i^\prime$, and $j^\prime$ determined by 721$$ (\lambda,i^\prime) = (1,i)^{s^{-1}}\quad {\rm and}\quad 722 (\mu,r+j^\prime) = (1,r+j)^{s^{-1}}.$$ 723If $A^s = B$, we say that $s$ is an {\it monomial isomorphism\/} of $A$ to $B$. When 724$A^s=A$,\enskip $s$ is called a {\it monomial automorphism\/} of $A$. The group 725formed by the automorphisms is called the {\it monomial automorphism group\/} of $A$, and denoted 726${\rm AUT}^*(A)$. 727\medbreak 728For example, over the field ${\rm GF}(4)$, the action of a 729monomial permutation $s$ of monomial degree 5 (actual degree 15) 730on a $2\times 3$ matrix $A$ is illustrated by the following. 731$$\displaylines{(1,1)^s = (3,2),\enskip\kern2pt (1,2)^s = (1,1),\enskip\kern2pt 732 (1,3)^s = (2,5),\enskip\kern2pt (1,4)^s = (3,3),\enskip\kern2pt (1,5)^s = (2,4),\cr 733 s = (1,6,3,5,2,4)(7,14,12,8,15,10,9,13,11),\quad\enskip 734 A = \pmatrix{2&0&3\cr 735 0&3&1\cr},\quad\enskip 736 A^s = \pmatrix{2&2&0\cr 737 0&3&2\cr}.\cr}$$ 738% 739% 740% 741% 742\section{IV.\quad PARTITION BACKTRACK COMMANDS} 743% 744The commands employing the partition backtrack method that are currently 745available are described below. Note material 746in square brackets is optional. (The brackets themselves are not to be 747typed.) Discussion of most of the available options will be 748deferred to Section~V; only those unique to a specific command will be 749mentioned here. 750\medskip 751Options are never required, but they may prove 752useful in controlling the format of the output or the procedures used in the 753computation. For example, certain options allow for a time versus space 754tradeoff. For some ``unusual'' groups (e.g., very dense imprimitive groups), 755it may be necessary to specify nonstandard options in order to obtain 756acceptable performance. 757\medskip 758The partition backtrack programs described here represent full implementations 759of the partition backtrack method, as set forth in (Leon, 1991), with 760two exceptions. 761{\smallskip\advance\leftskip by 0.45in\relax 762 \item{i)}The criterion in Prop.~8(iii) is not checked. 763 \smallskip 764 \item{ii)}In coset--type computations, the refinement $\germR^+$ of Figure~8 is 765 always taken as $\germR$\footnote{${}^{\dag}$}{\elevenpoint In order to allow 766 this manual to be printed without special AMS~TeX fonts, underlined 767 letters (e.g., $\germR$) are used here as a substitute for 768 letters appearing in the Euler Fraktur (German) font in (Leon, 1991).} 769\smallskip} 770% 771% 772\subsection{Set stabilizers:}Set stabilizers may be computed 773by the {\tt setstab} command. The format is 774\smallskip 775\hskip0.45truein{\tt setstab}\quad \options\quad {\it permGroup\quad pointSet\quad 776 stabilizerSubgroup} 777\smallskip 778This command computes the set stabilizer in the permutation group {\it permGroup\/} 779of the set {\it pointSet\/} and saves the result (in Cayley library format) 780as the permutation group {\it stabilizerSubgroup}. 781\medbreak 782At present, the set stabilizer program sometimes 783run slowly in doubly transitive groups, and often runs very slowly in groups 784that are triply transitive or ``almost'' triply transitive (e.g., 785${\rm SL}_n(2)$\kern2pt), especially when both the point set and its complement 786are large and when the set stabilizer turns out to be small. Imprimitive 787groups closely related to doubly transitive groups may also cause 788difficulty. Modifications to alleviate this difficulty, at least in part, 789will be added eventually. 790% 791% 792\subsection{Set images:}Given a permutation group $G$ on $\{1,\ldots,n\}$ 793and subsets $\Lambda$ and $\Phi$ of $\{1,\ldots,n\}$, the {\tt setimage} 794command may be used to determine if there exists an element $g$ of $G$ such 795that $\Lambda^g = \Phi$. The format is 796\smallskip 797\hskip0.45truein{\tt setimage}\quad \options\quad {\it permGroup\quad pointSet1\quad 798 pointSet2\quad groupElement} 799\smallskip 800where {\it permGroup}, {\it pointSet1}, {\it pointSet2}, and {\it groupElement} 801play the role of $G$, $\Lambda$, $\Phi$, and $g$, respectively. That is, 802the command determines whether there exists an element of {\it permGroup\/} 803mapping {\it pointSet1\/} to {\it pointSet2\/} and, if so, saves one such 804element as the permutation {\it groupElement}. 805Note that {\it groupElement\/} will not be created if $\Phi\notin\Lambda^G$. 806(Unless the {\tt -q} option is specified, a message indicating whether 807$\Phi\in\Lambda^G$ will be written to the standard output.) 808The potential difficulties with doubly and triply transitive groups mentioned 809for set stabilizer computations apply here also. 810% 811% 812\subsection{Ordered partition stabilizers:}Stabilizers of ordered partitions 813may be computed by the {\tt parstab} command. The format is 814\smallskip 815\hskip0.45truein{\tt parstab}\quad \options\quad {\it permGroup\quad ordPartition\quad 816 stabilizerSubgroup} 817\smallskip 818This command computes the stabilizer in the permutation group {\it permGroup\/} 819of the ordered partition {\it ordPartition\/} and saves the result as the 820permutation group {\it stabilizerSubgroup}. The remarks about performance 821on doubly and triply transitive groups for set stabilizer computations 822apply here also. 823% 824% 825\subsection{Ordered partition images:}Given a permutation group $G$ on 826$\{1,\ldots,n\}$ and ordered partitions $\Pi$ and $\Sigma$ of $\{1,\ldots,n\}$, 827the {\tt parimage} command may be used to determine if there exists an 828element $g$ of $G$ such that $\Pi^g = \Sigma$. The format is 829\smallskip 830\hskip0.45truein{\tt parimage}\quad \options\quad {\it permGroup\quad ordPartition1\quad 831 ordPartition2\quad groupElement} 832\smallskip 833where {\it permGroup}, {\it ordPartition1}, {\it ordPartition2}, and {\it groupElement} 834play the role of $G$, $\Pi$, $\Sigma$, and $g$, respectively. 835That is, 836the command determines whether there exists an element of {\it permGroup\/} 837mapping {\it ordPartition1\/} to {\it ordPartition2\/} and, if so, saves one 838such element as the permutation {\it groupElement}. 839The permutation {\it groupElement\/} is created only if $\Sigma\in\Pi^G$. 840The remarks about performance on doubly and triply 841transitive groups given above for 842set stabilizer computations apply here also. 843% 844% 845\subsection{Group intersections:}Given permutation groups $G$ and $H$ on 846$\{1,\ldots,n\}$, the {\tt inter} command may be used compute the 847intersection $G\cap H$. The format is 848\smallskip 849\hskip0.45truein{\tt inter}\quad \options\quad {\it permGroup1\quad permGroup2\quad 850 interGroup} 851\smallskip 852This command computes the intersection of groups {\it permGroup1\/} and {\it permGroup2\/} 853and saves the result as the group {\it interGroup\/}. The potential 854difficulty with doubly and triply transitive groups discussed above for set 855stabilizer computations applies here also when both groups are doubly 856or triply transitive. 857% 858% 859\subsection{Centralizers of elements:}Given a permutation group $G$ and 860a permutation $x$ (not necessarily contained in $G$), the 861{\tt cent} command may be used compute $C_G(x)$, the centralizer in $G$ of $x$. 862The format is 863\smallskip 864\hskip0.45truein{\tt cent}\quad \options\quad {\it permGroup\quad permutation\quad 865 centralizerSubgroup} 866\smallskip 867Here {\it permGroup}, {\it permutation}, and {\it centralizerSubgroup\/} 868play the role of $G$, $x$, and $C_G(x)$ above. That is, the command computes 869the centralizer in the group {\it permGroup\/} of 870the permutation {\it permutation\/} 871and saves the result as the group {\it centralizerSubgroup}. 872\medbreak 873For this command, it is permissible to specify 874{\it permGroup\/} as {\tt \#}{\it n}, where {\it n\/} 875is an integer at least 2, in which case {\it permGroup\/} is taken as the symmetric 876group of degree {\it n}; in this situation, the normal restrictions on 877base size (discussed later) do not apply to {\it permGroup}, although they do apply to 878{\it centralizerSubgroup}. 879\medbreak 880The {\tt cent} command accepts an option {\tt -np} which can have an effect 881(often small) on performance. If this option is specified, a refinement 882process based on the cycle structure of $x$ will not be used. The effect is 883to reduce memory requirements a bit. In many cases, the running time does 884not change significantly, but in some cases it does increase a great deal. 885\medbreak 886It should be noted that in many cases, perhaps most 887cases arising in practice, centralizer computations are fairly easy 888even for conventional algorithms, and the partition backtrack 889program may perform no better than, and perhaps not even as well as, 890programs based on conventional techniques, such as those in 891Cayley. (Note, however, that, unlike Cayley, the program here does not require 892that the permutation to be centralized lie in the group.) 893% 894% 895\subsection{Conjugacy of elements:}Given a permutation group $G$ and 896permutations $x$ and $y$ (not necessarily contained in $G$), the 897{\tt conj} command may be used to determine if $x$ and $y$ are conjugate 898under $G$ and, if so, to find $g$ in $G$ with $x^g = y$. The format is 899\smallskip 900\hskip0.45truein{\tt conj}\quad \options\quad {\it permGroup\quad permutation1\quad 901 permutation2\quad conjugatingElement} 902\smallskip 903Here {\it permGroup}, {\it permutation1}, {\it permutation2}, and 904{\it conjugatingElement\/} play the role of $G$, $x$, $y$, and $g$ above. 905That is, the command determines if there exists an element of 906{\it permGroup\/} conjugating 907{\it permutation1\/} to {\it permutation2\/} and, if so, it saves one such 908element as the permutation {\it conjugatingElement}. If the two permutations 909are not conjugate in {\it permGroup}, then {\it conjugatingElement} is not 910created. In any case, a message indicating the result is written to the 911standard output (unless the {\tt -q} option is specified). 912\medbreak 913As with the {\tt cent} command, {\it permGroup\/} may be specified 914as {\tt \#}{\it n}, in which case conjugacy in the symmetric group of 915degree {\it n} is checked. (In this case, the program merely checks that 916the two permutations have the same cycle structure.) Also, the {\tt -np} 917option is accepted, and it works as described above for the {\tt cent} 918command. 919\medbreak 920As with centralizer computations, conjugacy calculations are usually 921easy with conventional algorithms, and the partition backtrack method 922may not yield an improvement. 923% 924% 925\subsection{Centralizers of groups:}Given a permutation groups $G$ and 926a second permutation group $E$ (not necessarily contained in $G$), the 927{\tt gcent} command may be used compute $C_G(E)$, the centralizer in 928$G$ of $E$. The format is 929\smallskip 930\hskip0.45truein{\tt gcent}\quad \options\quad {\it permGroup1\quad permGroup2\quad 931 centralizerSubgroup} 932\smallskip 933Here {\it permGroup1}, {\it permGroup2}, and {\it centralizerSubgroup\/} 934play the role of $G$, $E$, and $C_G(E)$ above. That is, the command computes 935the centralizer in the group {\it permGroup1\/} of 936the group {\it permGroup2\/} 937and saves the result as the group {\it centralizerSubgroup}. 938\medbreak 939As with the element centralizer command ({\tt cent}), 940it is permissible to specify {\it permGroup1\/} as {\tt \#}{\it n}, 941indicating the symmetric group of degree {\it n}. 942\medbreak 943To an even greater extent than element centralizer 944calculations, group centralizer calculations tend to 945be easy ones for conventional algorithms; the full power of the 946partition method is not needed, and perhaps not even desirable. For this 947reason, little effort has gone into development of the {\tt gcent} command; 948its implementation is fairly crude, and it is included primarily 949for completeness. There are two options, {\tt -cg:}{\it m} and 950{\tt -cp:}{\it p}, which affect its performance; for some groups $G$, 951it may be necessary to assign them values different from the defaults 952(current 3 and 10, respectively). A full description of the significance 953of {\it m\/} and {\it p\/} will not be given here; however, we note that 954higher values (especially for {\it m}) increase 955memory requirements, and often increase execution time as well, but may be 956needed if the group $E$ fails to have a small generating set (e.g., if E is 957a large elementary abelian group). 958\medbreak 959By specifying {\it permGroup1\/} and {\it permGroup2\/} as the same group, 960the {\tt gcent} command may be used to compute the center of a group; note, 961however, that it represents an exceptionally inefficient algorithm for 962this purpose. 963% 964% 965% 966\subsection{Automorphism groups of designs:}The 967{\tt desauto} command may be used to compute the 968automorphism group of a design. Here a {\it design\/} means any set 969of points (numbered $1,\ldots,n$ for some $n$) and any collection of subsets 970of the point set. The format of the design automorphism group command is: 971\smallskip 972\hskip0.45truein{\tt desauto}\quad \options\quad {\it design\quad autoGroup} 973\smallskip 974and the command sets {\it autoGroup} to the automorphism group of the 975design {\it design\/}. 976\medbreak 977The interpretation of the group {\it autoGroup\/} that is created depends 978on whether the {\tt -pb} (points and blocks) option is specified. 979Let $p$ and $b$ denote the number of points and blocks, respectively, of 980the design. 981\smallskip 982{\advance\leftskip by0.70truein 983\noindent\llap{i)\enspace}If the option {\tt -pb} is specified, then {\it autoGroup} is constructed as 984a group of degree $p+b$, in which the action on $1,\ldots,p$ is the action 985on points and in which the action on $p+1,\ldots,p+b$ is the 986action on blocks, the $j$\kern1ptth block being 987represented by $p+j$. 988\smallskip\vskip2pt 989\noindent\llap{ii)\enspace}If the {\tt -pb} option is omitted, then 990{\it autoGroup} is constructed as a group of degree $p$, representing the 991action on points only. 992In this case, if there are repeated blocks, the group acting on 993points only has lower 994order than the group acting on points and blocks). 995When this situation arises, the group saved as {\it autoGroup} represents 996the group on points 997only, but the information written to the standard output during the computation 998refers to the group acting on points and blocks. (This occurs because the 999computation is carried out on points and blocks; restriction to points 1000is performed only at the end; note also, for this reason, restriction to 1001points only does not save time or memory.)\vskip0pt} 1002\medbreak 1003% 1004% 1005% 1006\subsection{Isomorphism of designs:}The 1007{\tt desiso} command may be used to check 1008isomorphism of designs. The format is 1009\smallskip 1010\hskip0.45truein{\tt desiso}\quad \options\quad {\it design1\quad 1011 design2\quad isoPerm} 1012\smallskip 1013and the command sets {\it isoPerm} to an isomorphism from 1014design {\it design1\/} to design {\it design2}, provided the designs 1015are isomorphic. (If not, the permutation {\it isoPerm\/} is 1016not created. In any case, a message indicating the result is written to 1017the standard output, unless the {\tt -q} option is specified.) 1018\medbreak 1019As in the case of the {\tt desauto} command, described 1020above, the presence or absence of the {\tt -pb} option determines whether 1021{\it isoPerm\/} is constructed as a permutation on points and blocks, 1022or on points only (the default). When the action on blocks is included, 1023the $j$\kern1ptth block is represented by $p+j$. 1024% 1025% 1026% 1027% 1028\subsection{Automorphism groups and monomial groups of matrices:}The 1029{\tt matauto} command may be used to compute the 1030automorphism group of a matrix. If the matrix elements are taken from a 1031small finite field ${\rm GF}(q)$, then optionally the monomial automorphism group may 1032be computed. (See Section~III for definitions.) 1033The command format is: 1034\smallskip 1035\hskip0.45truein{\tt matauto}\quad \options\quad {\it matrix\quad autoGroup} 1036\smallskip 1037and the command sets {\it autoGroup} to the automorphism group of the 1038matrix {\it matrix\/} or, if the {\tt -mm} option is specified, to the 1039monomial automorphism group of {\it matrix\/}. 1040\medbreak 1041If the {\tt -tr} option is specified, the matrix is transposed after it is 1042read in, and all computations apply to the transposed matrix. 1043\medbreak 1044Let $r$ and $c$ denote the number of rows and columns, respectively, of 1045the matrix $A = (a_{ij})$ whose group is to be constructed. Normally 1046the automorphism group has degree $r+c$ and the monomial automorphism group 1047has degree $(q-1)(r+c)$; the interpretation of these groups is described 1048in Section~III. However, if the {\tt -ro} (rows only) option is specified, 1049the degree will be $r$ or $(q-1)r$, and the group will represent the action 1050on rows only. Note that restriction to rows only may reduce the order of 1051the group, just as in the case of designs restriction to points only may 1052reduce the order of the group. When this occurs, the remarks above for 1053design groups apply here also. 1054\medbreak 1055At present, the program for computing monomial groups of matrices is a very 1056crude one. As a result, although it works reasonably for many matrices of 1057fairly large size, it can fail to run in acceptable time even for very small 1058matrices, e.g., matrices of all 0s. Sometimes use of the {\tt -tr} option 1059can get around this difficulty (which will be fixed eventually). 1060% 1061% 1062% 1063\subsection{Isomorphism and monomial isomorphism of matrices:}The 1064{\tt matiso} command may be used to check 1065if two matrices are isomorphic or, if the matrix elements are from a 1066finite field ${\rm GF}(q)$, monomially isomorphic. (See Section~III for 1067definitions.) The command format is 1068\smallskip 1069\hskip0.45truein{\tt matiso}\quad \options\quad {\it matrix1\quad 1070 matrix2\quad isoPerm} 1071\smallskip 1072In the absence of the {\tt -mm} option, the command sets {\it isoPerm} to an 1073isomorphism from matrix {\it matrix1\/} to matrix {\it matrix2}, provided the matrices 1074are isomorphic. (If not, the permutation {\it isoPerm\/} is 1075not created). If the {\tt -mm} option is specified, the command sets 1076{\it isoPerm} to a monomial isomorphism from matrix {\it matrix1\/} to matrix {\it matrix2}, 1077provided the matrices are monomially isomorphic. (In this case, the matrix 1078entries should be field elements.) The effect of the {\tt -ro} option is as 1079described above for matrix automorphism group calculations. 1080\medbreak 1081Currently the monomial isomorphism program suffers from the same limitations 1082as the monomial automorphism group program, as mentioned above. 1083\medbreak 1084% 1085% 1086\subsection{Automorphism groups of linear codes:}The 1087{\tt codeauto} command may be used to compute the 1088automorphism group of a linear code over a small field ${\rm GF}(q)$. 1089However, before the automorphism group of a code $C$ may be computed, 1090it is necessary to have a set $V$ of vectors (not necessarily codewords) 1091such that the following conditions hold. In these conditions, $V^*$ 1092denotes the set of all nonzero scalar multiples of vectors in $V$. 1093\smallbreak 1094{\advance\leftskip by1em\parindent=1em\relax 1095\item{i)} No vector in $V$ is a scalar multiple of any other vector in $V$. 1096(In particular, $\vert V^*\vert = (q-1)\vert V\vert$.) 1097\smallbreak 1098\item{ii)} $V$ is ``reasonably small''. (With a very large memory, 1099 ``reasonably small'' might mean 100,000 or more.) 1100\smallbreak 1101\item{iii)} $V^*$ is invariant under ${\rm AUT}(C)$\enskip (the automorphism 1102 group of $C$), 1103\smallbreak 1104\item{iv)} $\bigl\vert{\rm AUT}(V^*):{\rm AUT}(C)\bigr\vert$ is very small. 1105 (The running time rises very rapidly as a function of this 1106 index. Note that, if $V$ spans $C$, the index is 1.) 1107\smallbreak} 1108Often the set of minimal weight vectors of the code (scalar multiples 1109removed if $q > 2$) make a suitable choice for $V$; minimum weight vectors 1110of the dual code may also be used. This choice for $V$ certainly 1111satisfies~(i) and~(iii), 1112may well satisfy~(ii), and in many cases satisfies~(iv). The author has available 1113programs for computing the set of minimum weight vectors (or vectors of 1114any specified weight.) 1115\medbreak 1116The format of the code automorphism group command is 1117\smallskip 1118\hskip0.45truein{\tt codeauto}\quad \options\quad {\it code\quad 1119 invarVectors\quad autoGroup} 1120\smallskip 1121where {\it invarVectors\/} is the set $V$ of vectors described above 1122(in the format of a matrix, whose rows are the vectors). The command 1123sets {\it autoGroup} to the automorphism group of the 1124code {\it code}. 1125\medbreak 1126The {\tt -cv} (coordinates and vectors) option for codes 1127has essentially the same effect as the 1128{\tt -pb} option for designs. With this option, the automorphism 1129group is saved in {\it autoGroup\/} as a permutation group 1130of degree $\bigl(q-1)(n+\vert V\vert\bigr)$\enskip ($n =$ length of code), 1131representing the action on (monomial) coordinates 1132and invariant vectors; without the {\tt -cv} option, it is saved as a permutation group 1133acting of degree $(q-1)n$, representing the action on (monomial) 1134coordinates only. (However, restriction to coordinates only can never lead to a reduction 1135in the group order, as occurred with restriction to points or rows for 1136designs or matrices.) For an explanation of the format of monomial 1137permutations, see Section~III. 1138\medbreak 1139At present, the program for computing groups of non--binary codes is a very 1140crude one; sometimes it can fail to run in reasonable time even on small 1141codes. Eventually this program will be improved. 1142\medbreak 1143% 1144% 1145% 1146\subsection{Isomorphism of linear codes:}The 1147{\tt codeiso} command may be used to check isomorphism 1148of linear codes. However, before isomorphism of two codes 1149$C_1$ and $C_2$ may be checked, it is necessary to have a sets $V_1$ 1150and $V_2$ of vectors (not necessarily codewords of the two codes) 1151such that $V_1$ and $V_2$ satisfy conditions~(i), (ii), (iii), and~(iv) above 1152relative to $C_1$ and $C_2$, respectively, and in addition such that 1153any isomorphism of $C_1$ to $C_2$ must map $V_1^*$ to $V_2^*$. (As with 1154code automorphism groups, $V_1^*$ and $V_2^*$ denote the sets of nonzero scalar 1155multiples of vectors in $V_1$ and $V_2$, respectively. 1156Often suitable choices for $V_1$ and $V_2$ are the minimal weight vectors 1157of $C_1$ and $C_2$, respectively (scalar multiples removed.); minimal weight vectors of the duals 1158of the two codes also could be used. 1159\medbreak 1160The format of the code isomorphism command is 1161\smallskip 1162\hskip0.45truein{\tt codeiso}\quad \options\quad {\it code1\quad 1163 code2\quad invarVectors1\quad invarVectors2\quad 1164 isoPerm} 1165\smallskip 1166where {\it invarVectors1\/} and {\it invarVectors2\/} 1167are the sets $V_1$ and $V_2$, respectively, of vectors described above 1168(each in the format of a matrix, whose rows are the vectors). The command 1169sets {\it isoPerm} to an isomorphism from {\it code1\/} to {\it code2}, 1170if the codes are isomorphic; if not, {\it isoPerm\/} is not created. 1171\medbreak 1172As in the case of the {\tt codeauto} command, described 1173above, the presence or absence of the {\tt -cv} option determines whether 1174{\it isoPerm\/} is a permutation on (monomial) coordinates and invariant vectors, 1175or on (monomial) coordinates only. The interpretation of monomial permutations 1176is described in Section~III.. 1177% 1178% 1179\vskip10pt 1180\bigbigbreak 1181Note that a number of the commands above are implemented as shell 1182files (under Unix), batch files (under MS~DOS), or exec files 1183(under CMS). The commands that are implemented in this manner, and the 1184contents of the Unix shell files, are as follows. (The list includes a few 1185commands to be discussed in Section~IX.) 1186\bigskip 1187\long\def\shellfile#1#2{\noindent\hskip0.45truein\hbox to1.0truein{#1\hfil}\relax 1188 \hbox to4.0truein{#2\hfil}\vskip2.0pt}\relax 1189\vbox{{\it 1190\shellfile{command}{contents of shell file} 1191\vskip6pt 1192\elevenpoint\tt 1193\shellfile{setimage}{setstab -image \$*} 1194\shellfile{parstab} {setstab -partn \$*} 1195\shellfile{parimage}{setstab -image -partn \$*} 1196\shellfile{conj} {cent -conj \$*} 1197\shellfile{gcent} {cent -group \$*} 1198\shellfile{desiso} {desauto -iso \$*} 1199\shellfile{matauto} {desauto -matrix \$*} 1200\shellfile{matiso} {desauto -iso -matrix \$*} 1201\shellfile{codeauto}{desauto -code \$*} 1202\shellfile{codeiso} {desauto -iso -code \$*} 1203\shellfile{cjper} {cjrndper -perm \$*} 1204\shellfile{ncl} {commut -ncl \$*} 1205\shellfile{compper} {compgrp -perm:\$1 \$2 \$3} 1206\shellfile{compset} {compgrp -set:\$1 \$2 \$3} 1207\shellfile{chbase} {orblist -chbase \$*} 1208\shellfile{ptstab} {orblist -ptstab \$*} 1209\vskip0pt}} 1210% 1211% 1212% 1213\section{V.\quad OPTIONS} 1214% 1215A partial description of the options that are currently available 1216follows. Most of the options are available with all of 1217the commands described in Section~IV. A few options apply only to 1218subgroup computations, or only to coset--representative computations; 1219these restrictions are noted below. Options applicable only to a single command 1220are discussed with that command in Section~IV. 1221\medbreak 1222In general, options may be specified in any order. However, if 1223conflicting options are specified, the one specified last is 1224the one that is used. (In some cases, conflicting options are treated 1225as an error. Also, the {\tt -l} and {\tt -v} options, discussed later, 1226are an exception to the general rule that options may be specified in 1227any order; these options, if present, must come first, and the remainder 1228of the command line is ignored.) 1229\medbreak 1230Entering any command with no options or arguments causes a brief 1231summary of the command format to be displayed. 1232\bigbreak 1233\subsection{Options affecting file handling:} 1234\nobreak\medskip\nobreak 1235% 1236\defoption{-a}{Normally, if a file name is specified for an object 1237 to be constructed, and if a file by that name already 1238 exists, the programs overwrite the existing file. With 1239 the {\tt -a} option, they append to the existing file, 1240 rather than overwriting it.} 1241\medbreak 1242\defoption{-p:{\it path}}{Here {\it path\/} is a string. 1243 The string {\it path\/} is concatenated to 1244 the file name of every input file. This option can be useful 1245 if all the input files are in another directory. 1246 For example, 1247 \smallskip 1248 \hskip0.15truein{\tt setstab\quad\kern-1pt ../groups/psp62::psp62\quad\kern-1pt 1249 ../groups/lambda::lambda\quad\kern-2pt S} 1250 \smallskip 1251 may be written more compactly as 1252 \smallskip 1253 \hskip0.15truein{\tt setstab\quad -p:../groups/\quad 1254 psp62\quad lambda\quad S} 1255 \smallskip 1256 (Note the final slash following {\tt groups} is required.). 1257 The {\tt -p} option has no effect on output files.} 1258% 1259\bigbreak 1260\subsection{Options affecting output format:} 1261\nobreak\medskip\nobreak 1262% 1263\medbreak 1264\defoption{-i}{This option applies to commands that construct and write out 1265 either a permutation or a permutation group. It causes 1266 permutations to be written in image format, rather 1267 than in cycle format (the default).} 1268% 1269\medbreak 1270\defoption{-n:{\it name}}{Here {\it name\/} is a string. The object created 1271 by the command will be named {\it name}. By 1272 default, the name assigned to the object will be 1273 the name of the Cayley library containing its 1274 definition. Note this option affects only the 1275 name of the object, not that of the file or the 1276 Cayley library.} 1277% 1278\medbreak 1279\defoption{-q}{Suppresses informative messages on the state of the 1280 computation, normally written to the standard output during 1281 the computation.} 1282% 1283\medbreak 1284\defoption{-s}{Causes statistics on the pruning of the backtrack 1285 search tree to be written out to the standard output. 1286 These statistics relate to the backtrack search tree 1287 defined in the author's paper (Leon, 1991), and are 1288 likely to be meaningful only to users familiar with that 1289 paper.} 1290% 1291\medbreak 1292\defoption{-w:{\it n}}{Here {\it n\/} should be a nonnegative integer. 1293 This option applies only to coset representative 1294 computations. If the degree is less 1295 than or equal to {\it n}, and if a coset representative 1296 is found, it will be included in the informative 1297 messages written to the standard output. (In any case, 1298 the coset representative will be written to a file in 1299 Cayley library format.) The default value of {\it n} 1300 is currently 300.} 1301\bigbreak 1302% 1303\subsection{Options affecting performance of the algorithm:} 1304\nobreak\medskip\nobreak 1305\defoption{-b:{\it k}}{Here {\it k\/} is a nonnegative integer which 1306 determines the extent to which base changes are performed 1307 in an attempt to 1308 improve pruning of the backtrack search tree using 1309 tests on double--coset minimality (Leon, 1991, Prop~8). 1310 When {\it k}~=~0, 1311 base change is never performed (except during $\bfgermR$--base 1312 construction, when it is used for a different purpose). 1313 As {\it k\/} increases, the number of base change operations 1314 performed increases; however, 1315 increasing {\it k\/} beyond the base size produces no 1316 further increase in the number of base change operations. 1317 Designating {\it k}~=~0 reduces memory requirements and often 1318 produces the best running times as well. On the other 1319 hand, some high--density groups seem to require a higher 1320 value of {\it k\/} in order to obtain acceptable performance. 1321 By default, the program chooses a value of {\it k\/} based 1322 on the density and degree of transitivity of the group; 1323 quite often, this default value is 0. 1324 \smallskip 1325 {\it Note:}\enskip For coset representative computations, 1326 this option has no effect unless known subgroups of the two 1327 associated groups are specified; see discussion of the 1328 {\tt -kL} and {\tt -kR} options below.} 1329% 1330\medbreak 1331\defoption{-g:$m$}{Here $m$ should be a nonnegative integer. 1332 This is one of several parameters providing a 1333 time vs.\ space tradeoff. 1334 Small values of $m$, say 10 or less, minimize memory 1335 requirements, while large values of $m$, say 100 or 1336 greater, reduce the running time moderately for most 1337 difficult groups. Use of a high value is recommended 1338 for multiply transitive groups. 1339 \smallskip 1340 After $\bfgermR$--base construction, the program attempts to 1341 reduce the height of the Schreier trees for the 1342 containing group by adding new strong generators. However, 1343 it will never add generators for this purpose if doing 1344 so would cause the total number of strong generators to 1345 exceed $m$. (It will also stop adding generators if the height 1346 falls below certain goals currently fixed in the program.)} 1347% 1348\medbreak 1349\defoption{-k:$H$}{Here $H$ specifies a permutation group (in the format 1350 {\it cayleyLibraryName\/} or 1351 {\it fileName}\kern1pt::\kern1pt{\it cayleyLibraryName}). 1352 This option applies only to subgroup 1353 calculations. The group $H$ must 1354 be a known subgroup of the group being computed. In 1355 principle, this option allows one to take advantage 1356 of any subgroup of the group being computed that happens 1357 to be known in advance. In practice, however, it seldom 1358 appears to speed up the computation by very much, 1359 and it increases memory requirements.} 1360% 1361\medbreak 1362\newdimen\optionWidth \optionWidth=\hsize \advance\optionWidth by-1em\relax 1363 \advance\optionWidth by-\optionIndent 1364{\advance\leftskip by1em\noindent\vtop{\hsize=\optionIndent\parindent=0pt\tt\noindent 1365 -kL:$J$\vskip1pt\noindent -kR:$M$}\relax 1366 \vtop{\hsize=\optionWidth\parindent=0pt 1367 Here $J$ and $M$ must specify permutation groups (each in the 1368 format {\it cayleyLibraryName\/} or 1369 {\it fileName}\kern1pt::\kern1pt{\it cayleyLibraryName}). These options 1370 apply only to coset representative calculations. Either or 1371 both may be specified. Associated with every coset 1372 representative computation, there are ``left'' and ``right'' 1373 groups, as explained in Section~2 of (Leon, 1991). 1374 The groups $J$ and $M$ must be known subgroups of these 1375 left and right groups, respectively. Specifying $J$ and/or $M$, 1376 if known, increases memory requirements, but in some cases 1377 it may improve the running time. For some very dense groups, 1378 one or both of these options may be needed in order to allow 1379 the computation to finish in an acceptable amount of time.}\vskip0pt} 1380% 1381\medbreak 1382\defoption{-mb:$k$}{Here $k$ should be a nonnegative integer. This integer 1383 represents an upper bound on the size of the base for a 1384 permutation group. The default value of $k$ is 62, which is 1385 more than adequate for many groups. For further discussion of 1386 the {\tt -mb} option, see Section~VII.} 1387% 1388\medbreak 1389\defoption{-mw:$\ell$}{Here $\ell$ should be a nonnegative integer whose value 1390 is at least several hundred. This integer represents an upper 1391 bound on the length of any word in the generators of any 1392 permutation group. For further discussion, see Section~VII.} 1393% 1394\medbreak 1395\defoption{-r:$p$}{Here $p$ should be a nonnegative integer, normally smaller 1396 than the integer $m$ specified for the {\tt -g} option 1397 described above. This is another option providing for a 1398 time versus space 1399 tradeoff. Small values of $p$, say less than 10, minimize 1400 memory requirements, while larger values, say 50 or higher, 1401 {\it may\/} reducing the running time, although usually not 1402 a great deal. 1403 \smallskip 1404 Whenever the number of strong generators for the containing 1405 group exceeds $p$, redundant strong generators are eliminated, 1406 using a procedure originally due to Sims (1971).} 1407\bigbreak 1408\subsection{Special options:} 1409\nobreak\medskip\nobreak 1410\defoption{-l}{This option, if present, must be the first option on the 1411 command line, and the remainder of the command line is 1412 ignored. (It may be omitted.) The {\tt -l} option merely 1413 prints out limits on the default maximum base size, 1414 default maximum word length, degree, and other 1415 quantities with which this version of the program has been 1416 compiled. (See Section~VII for discussion of these limits.)} 1417\medbreak 1418\defoption{-v}{This option, if present, must be the first option on the 1419 command line, and the remainder of the command line is 1420 ignored. (It may be omitted.) The {\tt -v} option is 1421 intended to be used once following compilation of the program. 1422 It attempts to check that all the source files for the 1423 program were compiled with the same options and size limits. 1424 (See Section~VII for discussion of size limits.)} 1425% 1426% 1427% 1428\section{VI.\quad OUTPUT AND RETURN CODES} 1429% 1430All programs for subgroup computations return a value of 0 if the 1431computation is completed successfully and a nonzero value (currently 15) if 1432the computation terminates due to an error (input file not found, incorrect 1433format in input file, memory exhausted, size limit in program exceeded, etc.) 1434All programs for coset representative 1435computations return a value of 0 if the computation is completed 1436successfully and a coset representative exists, 1 if it is 1437completed but a coset representative does {\it not\/} exist, and a value different from 14380 and 1 (currently 15) if the computation terminates due to an error. 1439\medbreak 1440% 1441Unless the {\tt -q} option is specified, all of the programs write 1442information about the progress of the computation to the standard output. 1443Some of this information, most notably that relating to the 1444$\bfgermR$--base and the backtrack search tree (the latter 1445given only if {\tt -s} is specified) 1446will probably be meaningful primarily to users familiar with the 1447author's paper (Leon, 1991). Information of more general interest 1448includes: 1449\smallskip 1450{\advance\leftskip by0.45truein\noindent 1451\item{i)}The order of the containing group (unless it is the symmetric 1452group). Note that this order is determined by computing a base and strong 1453generating set for the containing group when it is read in, unless they are 1454supplied in the input file. 1455\smallskip 1456\item{ii)}The new (changed) base and strong generating set for the 1457containing group computed during $\bfgermR$--base construction, and the corresponding 1458basic orbit lengths. In the notation of (Leon, 1991), this is the 1459base $(\alpha_1,\ldots,\alpha_k)$ associated with the $\bfgermR$--base. 1460\smallskip 1461\item{iii)}A base for the subgroup to be computed (subgroup computations) 1462or for the subgroup associated with the right coset whose representative 1463is to be computed (coset representative computations). 1464This is the subgroup base associated 1465with the $\bfgermR$--base; in the notation of (Leon, 1991), it is 1466$(\hat{\alpha}_1,\ldots,\hat{\alpha}_{\ell})$. Note that this base is a 1467subsequence of the base for the containing group in~(ii) above. 1468\smallskip 1469\item{iv)}The basic cell sizes corresponding to the subgroup base in~(iii) 1470above (for definitions, see (Leon, 1991)). Note that each basic 1471cell size provides an upper bound for the corresponding basic orbit length of the 1472subgroup to be computed (subgroup--type computations). 1473(Usually the bound is not sharp). 1474\smallskip 1475\item{v)}The number of strong generators for the containing group and the 1476mean node depths in the Schreier trees for the basic orbits of the containing 1477group. Depending on the {\tt -g} and {\tt -r} options, following $\bfgermR$--base 1478construction, additional strong generators may be added in an attempt to 1479reduce the height of the Schreier trees. Figures are provided both before 1480and after additional strong generators are added. 1481\smallskip 1482\item{vi)}[subgroup computations only]\enskip A message for each strong 1483generator that is found for the subgroup. The message gives the level and the basic 1484orbit lengths for the subgroup constructed thus far. (A generator will 1485be said to be at level $i$ if it fixes the first $i-1$ base points but 1486moves the $i$\kern1ptth.) 1487\smallskip 1488\item{vii)}[subgroup computations only]\enskip The order of the subgroup that was 1489computed. 1490\smallskip 1491\item{viii)}[subgroup computations only]\enskip The base (same as in~(iii) above) 1492and basic orbit lengths for the subgroup that was computed. 1493\smallskip 1494\item{ix)}[coset representative computations only]\enskip A message indicating whether a coset 1495representative exists. 1496\smallskip 1497\item{x)}[coset representative computations only]\enskip If a coset representative exists and the degree is sufficiently 1498low (depending on the {\tt -w} option), the coset representative that was 1499found. 1500\smallskip 1501\item{xi)}The time required for the computation. Note that the time to 1502read in the containing group from a file, construct the initial base and 1503strong generating set for the containing group (if not present in the input 1504file), and to write out the subgroup or coset representative to a file is 1505not included in this time. All computations relating to calculation of 1506the subgroup or coset representative (including base changes in the containing 1507group) are included. 1508\medbreak} 1509% 1510Note that, in subgroup computations, the actual strong generators for the 1511subgroup are not written to standard output, and in coset computations, 1512the actual coset representative found may not (depending on the degree and 1513{\tt -w} option) be written to the standard output. However, both may be 1514found (in Cayley library format) in the output file that is created. 1515\medbreak 1516For design, matrix, or code isomorphism computations, the isomorphism that 1517is constructed is written to the standard output (assuming that the degree 1518is sufficiently low) in a more easily readable 1519(but not Cayley compatible) format than that described in Sections~II 1520and~III. For designs with the {\tt -pb} option, 1521the action on points and blocks is given separately. For matrices, the 1522action on rows and columns is given separately. For monomial isomorphism of 1523matrices for non--binary codes, the monomial 1524isomorphism is written in the following format: 1525$$\bigl(\kern1pt[\lambda_1]i_1,[\lambda_2]i_2,\ldots,[\lambda_k]i_k\kern1pt\bigr)$$ 1526This denotes the monomial permutation mapping 1 to $\lambda_1i_1$, 15272 to $\lambda_2i_2$, etc. For example, to apply this monomial permutation 1528to the rows of an $r$ by $c$ matrix, row $j$ is multiplied by $\lambda_j$ 1529and the result is moved to row position $i_j$. 1530 1531% 1532\medbreak 1533% 1534% 1535% 1536\section{VII.\quad SIZE LIMITS} 1537% 1538There are a few fixed limits on the sizes of objects that the programs can 1539handle. These limits can be changed only by recompiling the programs. 1540The order of any group may have at most 30 distinct prime divisors. The 1541name of any file may have at most 60 characters (including path information 1542supplied with the {\tt -p} option). The name of any object may have at 1543most 16 characters. 1544Most importantly, if the program is compiled using 16--bit integers, 1545the maximum degree of any permutation group is limited to slightly less 1546than $2^{16}$ (about 65000). If it is compiled using 32--bit integers, 1547there is, for practical purposes, no fixed limit. 1548Note, however, that use of 16--bit 1549integers reduces memory requirements substantially, and it is recommended 1550unless groups of degree greater than 65000 (approx) are to be used. 1551Only machines having at least 20 to 25 megabytes of memory are 1552likely to be able to handle groups of degree high enough to require 155332--bit integers. Currently both 16--bit and 32--bit compiled versions 1554of the programs are available. 1555\medbreak 1556Although there is no fixed limit on the base size for a permutation group, 1557a limit must be established at the time that the program is initiated, and 1558this limit remains fixed during that run. 1559This limit may be set at $k$ by means of the {\tt -mb:$k$} option, or it 1560may be allowed to default to 62. Note that large values of $k$ increase 1561running times and memory requirements slightly even if the actual base size 1562turns out to be much less than $k$. 1563\medbreak 1564For the most part, the amount of memory (real and virtual) available 1565determines the sizes of objects that can be handled by the programs. 1566Memory requirements depend heavily on the degree of the group, and 1567to a somewhat lesser extent on the base size. 1568The programs can use virtual memory to some extent; however, if 1569virtual memory used exceeds real memory by a factor of more than 1.6 to 1.8, 1570excessive paging is likely to occur. The following steps may be taken 1571to reduce memory requirements; the steps are listed in order of decreasing 1572benefit. 1573\medskip{\advance\leftskip by0.45in\noindent 1574\item{i)}If the degree of the group is less than 65000 (approx), use a 1575 16--bit version of the program rather than a 32--bit version. 1576 The 16--bit version is likely to run about as fast as the 32--bit 1577 version, and it requires a great deal less memory. 1578\smallskip 1579\item{ii)}Specify options of {\tt -g:1} and {\tt -r:1}. These options 1580 are likely to increase the execution time substantially, but 1581 they often save a good deal of memory. As a compromise, 1582 values greater than 1 but less than the defaults may be 1583 specified, e.g., {\tt -g:20} and {\tt -r:15} 1584\smallskip 1585\item{iii)}Specify the option {\tt -b:0} if it is not already the default. 1586 In the majority of cases, this option will not increase 1587 execution time, and it reduces memory requirements considerably. 1588 However, in a great many cases, {\tt -b:0} 1589 will already be the default. (The value for this and other 1590 options is displayed on the standard output when the program is 1591 is run.) 1592\smallskip 1593\item{iv)}For (element) centralizer and conjugacy calculations, specify the 1594 {\tt -np} option. This saves a modest amount of memory. The 1595 effect on execution time is hard to predict; in some cases, it 1596 may lead to a major increase. For group centralizer calculations, 1597 options of {\tt -cg:2} and {\tt -cp:$i$}, where $i$ is 3 to 5, 1598 may be tried, although on some groups they may raise the 1599 running time to unacceptable levels. 1600\smallskip 1601\item{v)}Specify the option {\tt -mb:$k$} for a value of $k$ less than 1602 the default of 62. The {\tt -mb:$k$} options sets a limit of $k$ 1603 on the base size for the group; often a value considerably less 1604 than 62 (e.g., 15 or 20) will be adequate. However, the amount of 1605 memory saved is relatively small. 1606\vskip0pt} 1607\medbreak 1608In the author's experience, the programs can often handle groups of degree 1609as high as 2000$m$ to 3000$m$, where $m$ is the number of megabytes of 1610{\it real\/} memory available. However, for groups lacking a relatively 1611small base, the limit on the degree is much lower. Also, this limit 1612applies only to memory requirements; depending on the type of computation 1613and the specific groups, it may or may not be possible to perform 1614computations in groups this large in an acceptable amount of time. 1615% 1616% 1617\section{VIII.\quad EXAMPLES} 1618% 1619The author has prepared a number of sample objects that may be used to 1620test the programs. In the Unix distribution, these objects 1621appear in various subdirectories of the directory {\tt partn/examples}. 1622% 1623\medbreak 1624The subdirectories {\tt psp62}, {\tt psp82}, {\tt psu72}, 1625{\tt omg84}, {\tt fi23}, {\tt ahs2}, {\tt rubik4}, and 1626{\tt syl128} of directory {\tt partn/examples} contain 1627examples for computation in the groups ${\rm PSp}_6(2)$ of degree 63, 1628${\rm PSp}_8(2)$ of degree 255, ${\rm PSU}_7(2)$ of degree 2709, 1629$\Omega^+_8(4)$ of degree 5525, ${\rm Fi}_{23}$ of degree 31671, 1630${\rm AUT(HS)}\times {\rm AUT(HS)}$ of degree 200, 1631the group of a $4\times 4$ Rubik's cube (degree 96), and a Sylow 2--subgroup 1632of the symmetric group {\it Sym\/}(128)\enskip of degree 128, respectively. 1633Note that, for the last two groups, any base will be large, and the 1634{\tt -mb} option (e.g., {\tt -mb:75}) will need to be specified. 1635Each of the directories contains files as follows, where {\it grp\/} is 1636to be replaced by the actual name of the directory. 1637\medbreak 1638{\advance\leftskip by 1.0truein\relax 1639 \noindent\llap{\hbox to0.75in{{\it grp}\hfil}}The permutation group mentioned above. 1640 \medbreak 1641 \noindent\llap{\hbox to0.75in{{\it grp\/}{\tt\kern1ptx}\hfil}}A group permutation isomorphic to the 1642 group {\it grp\/} and having a small but nontrivial intersection with 1643 {\it grp}. The intersection of {\it grp\/} and {\it grp\/}{\tt x} may 1644 be computed by the command 1645 \smallskip 1646 \hskip0.4in{\tt inter\quad {\it grp\/}\quad {\it grp\/}x\quad int} 1647 \smallskip 1648 which saves the intersection as the group {\tt int}. The file 1649 {\it grp\/}{\tt x} contains a comment giving the order of the 1650 intersection. 1651 \medbreak 1652 \noindent\llap{\hbox to0.75in{\tt set1\hfil}}A random point set of size half the degree 1653 of {\it grp}. Except in the case of {\tt rubik4} 1654 and {\tt syl128}, the set stabilizer of 1655 {\tt set1} in the group {\it grp\/} turns out to be trivial. This 1656 set stabilizer may be computed by the command 1657 \smallskip 1658 \hskip0.4in{\tt setstab\quad {\it grp\/}\quad set1\quad stab1} 1659 \smallskip 1660 which saves the set stabilizer as the group {\tt stab1}. 1661 \medbreak 1662 \noindent\llap{\hbox to0.75in{\tt set2\hfil}}A point set of size approximately 1663 half the degree whose set stabilizer in {\it grp\/} 1664 is a dihedral group of low order, except in the case 1665 of {\tt rubik4} and 1666 {\tt syl128}. This set stabilizer may be computed by the command 1667 \smallskip 1668 \hskip0.4in{\tt setstab\quad {\it grp\/}\quad set2\quad stab2} 1669 \smallskip 1670 which saves the set stabilizer as the group {\tt stab2}. 1671 The file {\tt set2} contains a comment indicating the order of the 1672 stabilizer. 1673 \medbreak 1674 \noindent\llap{\hbox to0.75in{\tt set3\hfil}}A point set of size roughly 1675 half the degree (in most cases ) whose set stabilizer in {\it grp\/} is a 1676 group of high order. This set stabilizer may be 1677 computed by the command 1678 \smallskip 1679 \hskip0.4in{\tt setstab\quad {\it grp\/}\quad set3\quad stab3} 1680 \smallskip 1681 which saves the set stabilizer as the group {\tt stab3}. 1682 The file {\tt set3} contains a comment indicating the order of the 1683 stabilizer. 1684 \medbreak 1685 \noindent\llap{\hbox to0.75in{\tt set1x\hfil}}A point set obtained by applying a 1686 randomly--chosen element of the group {\it grp\/} to {\tt set1}. 1687 The command 1688 \smallskip 1689 \hskip0.4in{\tt setimage\quad {\it grp\/}\quad set1\quad set1x\quad g} 1690 \smallskip 1691 may be used to find an element {\tt g} of the group {\it grp\/} mapping 1692 {\tt set1} to {\tt set1x}. 1693 \medbreak 1694 \noindent\llap{\hbox to0.75in{\tt set1y\hfil}}A point set having the same cardinality 1695 as {\tt set1} but not equal to the image of {\tt set1} 1696 under any element of {\it grp\/}. The command 1697 \smallskip 1698 \hskip0.4in{\tt setimage\quad {\it grp\/}\quad set1\quad set1y\quad h} 1699 \smallskip 1700 may be used to determine that {\tt set1y} is not in fact an 1701 image of {\tt set1} under the group. (The permutation $h$ will 1702 {\it not\/} be created. 1703 \medbreak 1704 \noindent\llap{\hbox to0.75in{\tt par1\hfil}}A partition of the set $\{1,\ldots,n\}$, where 1705 $n$ is the degree of group {\it grp}. (The file contains 1706 a comment indicating the number of cells and cell sizes.) 1707 The stabilizer in {\it grp\/} of 1708 {\tt par1}, treated as an ordered partition, may be computed by the 1709 command 1710 \smallskip 1711 \hskip0.4in{\tt parstab\quad {\it grp\/}\quad par1\quad pstab1} 1712 \smallskip 1713 which saves the ordered partition stabilizer as the group {\tt pstab1}. 1714 The file {\tt par1} contains a comment giving the order of the 1715 stabilizer. 1716 \medbreak 1717 \noindent\llap{\hbox to0.75in{\tt par1x\hfil}}A partition obtained by applying a 1718 randomly--chosen element of the group {\it grp\/} to {\tt par1}. 1719 The command 1720 \smallskip 1721 \hskip0.4in{\tt parimage\quad {\it grp\/}\quad par1\quad par1x\quad i} 1722 \smallskip 1723 may be used to find an element {\tt i} of the group {\it grp\/} mapping 1724 {\tt par1} to {\tt par1x}. 1725 \medbreak 1726 \noindent\llap{\hbox to0.75in{\tt par1y\hfil}}A partition in which the sizes of the 1727 cells match those in {\tt par1}, but which is not the 1728 image of {\tt par1} under any element of the group {\it grp\/}. 1729 The command 1730 \smallskip 1731 \hskip0.4in{\tt parimage\quad {\it grp\/}\quad par1\quad par1y\quad j} 1732 \smallskip 1733 may be used to demonstrate that {\tt par1y} is not an image of 1734 {\tt par1} under any group element. 1735 \medbreak 1736 \noindent\llap{\hbox to0.75in{\tt elt1\hfil}}An element of the group {\it grp\/} 1737 having a fairly 1738 large centralizer in {\it grp\/}. This centralizer may be 1739 computed by the command 1740 \smallskip 1741 \hskip0.4in{\tt cent\quad {\it grp\/}\quad elt1\quad cent1} 1742 \smallskip 1743 which saves the centralizer as the group {\tt cent1}. 1744 The file {\tt elt1} contains a comment stating the order of the 1745 centralizer. 1746 \medbreak 1747 \noindent\llap{\hbox to0.75in{\tt elt1x\hfil}}An element conjugate 1748 under the group {\it grp\/} 1749 to {\tt elt1}. An element of {\it grp\/} conjugating {\tt elt1} 1750 to {\tt elt1x} may be found by the command 1751 \smallskip 1752 \hskip0.4in{\tt conj\quad {\it grp\/}\quad elt1\quad elt1x\quad c1} 1753 \smallskip 1754 which sets {\tt c1} to such a conjugating element. 1755 \medbreak 1756 \noindent\llap{\hbox to0.75in{\tt elt2\hfil}}An permutation {\it not\/} 1757 in the group {\it grp\/} having a nontrivial 1758 centralizer in {\it grp}. This centralizer may be 1759 computed by the command 1760 \smallskip 1761 \hskip0.4in{\tt cent\quad {\it grp\/}\quad elt2\quad cent2} 1762 \smallskip 1763 which saves the centralizer as the group {\tt cent2}. 1764 The file {\tt cent2} contains a comment indicating the order of the 1765 centralizer. 1766 \medbreak 1767 \noindent\llap{\hbox to0.75in{\tt elt2x\hfil}}A permutation (not in {\it grp\/}) 1768 conjugate under {\it grp\/} 1769 to {\tt elt2}. An element of {\it grp\/} conjugating {\tt elt2} 1770 to {\tt elt2x} may be found by the command 1771 \smallskip 1772 \hskip0.4in{\tt conj\quad {\it grp\/}\quad elt2\quad elt2x\quad c2} 1773 \smallskip 1774 which sets {\tt c2} to such an element. 1775 \medbreak 1776 \noindent\llap{\hbox to0.75in{\tt elt2y\hfil}}A permutation not in {\it grp\/} 1777 having the same cycle structure as {\tt elt2} but not 1778 conjugate under {\it grp\/} to {\tt elt2}. Non--conjugacy may 1779 be demonstrated by the command 1780 \smallskip 1781 \hskip0.4in{\tt conj\quad {\it grp\/}\quad elt2\quad elt2y\quad d} 1782 \smallskip 1783 which does {\it not} create a permutation {\tt d}. 1784\vskip0pt} 1785\medbreak 1786Note that, in the case of the group {\tt fi23}, about 16 megabytes of real 1787memory may be needed to perform the calculations above. 1788\bigbreak 1789The subdirectories {\tt q17} and {\tt q32} contain designs, (0,1)--matrices, 1790and codes based on the quadratic residue code $Q_{17}$ of length 17 and 1791on the extended quadratic residue code $Q_{32}$ of length 32, respectively. 1792The contents of these directories are as follows, where $i$ denotes either 179317 or 32. 1794\medbreak 1795{\advance\leftskip by 1.0truein\relax 1796 \noindent\llap{\hbox to0.75in{\tt q\kern1pt$i$\hfil}}The quadratic or extended 1797 quadratic residue code. 1798 \medbreak 1799 \noindent\llap{\hbox to0.75in{\tt v\kern1pt$i$\hfil}}The matrix whose rows are 1800 the weight 5 ($i = 17$) or weight 8 ($i = 32$) codewords 1801 of the code {\tt q}\kern1pt$i$. The automorphism group of the code 1802 {\tt q}\kern1pt$i$ may be computed by the command 1803 \smallskip 1804 \hskip0.4in{\tt codeauto\quad q\kern1pt$i$\quad v\kern1pt$i$\quad A} 1805 \smallskip 1806 or 1807 \smallskip 1808 \hskip0.4in{\tt codeauto\quad -cv\quad q\kern1pt$i$\quad v\kern1pt$i$\quad A} 1809 \smallskip 1810 which saves the automorphism group as the group {\tt A}, 1811 either as a group of degree $i$ or as a group of degree 1812 $i+k$, where $k$ is the number of codewords in the set {\tt v}\kern1pt$i$. 1813 \medbreak 1814 \noindent\llap{\hbox to0.75in{\tt q\kern1pt$i$\kern1ptx\hfil}}Another quadratic residue 1815 code obtained from 1816 {\tt q}\kern1pt$i$ by applying a random permutation to the 1817 coordinates.. 1818 \medbreak 1819 \noindent\llap{\hbox to0.75in{\tt v\kern1pt$i$\kern1ptx\hfil}}The matrix whose rows are 1820 the weight 5 ($i = 17$) or weight 8 ($i = 32$) codewords 1821 of the code {\tt q}\kern1pt$i$\kern1pt{\tt x}. An isomorphism from 1822 {\tt q}\kern1pt$i$ to {\tt q\kern1pt$i$\kern1ptx} 1823 may be found by the command 1824 \smallskip 1825 \hskip0.4in{\tt codeiso\quad q\kern1pt$i$\quad q\kern1pt$i$\kern1ptx\quad 1826 v\kern1pt$i$\quad v\kern1pt$i$\kern1ptx\quad s} 1827 \smallskip 1828 which saves the isomorphism found as the permutation {\tt s}. 1829 \medbreak 1830 \noindent\llap{\hbox to0.75in{\tt d\kern1pt$i$\hfil}}The design on $\{1,\ldots,i\}$ 1831 whose blocks correspond to the codewords of 1832 weight 5 ($i = 17$) or weight 8 ($i = 32$) in {\tt q}\kern1pt$i$. 1833 The automorphism group of this design (which must 1834 contain the group of the corresponding code, and which 1835 in fact equals it) may be computed by the command 1836 \smallskip 1837 \hskip0.4in{\tt desauto\quad d\kern1pt$i$\quad B} 1838 \smallskip 1839 or 1840 \smallskip 1841 \hskip0.4in{\tt desauto\quad -pb\quad d\kern1pt$i$\quad B} 1842 \smallskip 1843 which saves the automorphism group as the group {\tt B}, either as a 1844 group on points only, or as a group on points and blocks. Note 1845 that the incidence matrix of the design {\tt d}\kern1pt$i$ is the 1846 transpose of the matrix {\tt v}\kern1pt$i$, so the same automorphism 1847 group could be computed by the command 1848 \smallskip 1849 \hskip0.4in{\tt matauto\quad -tr\quad v\kern1pt$i$\quad A} 1850 \medbreak 1851 \noindent\llap{\hbox to0.75in{\tt d\kern1pt$i$\kern1ptx\hfil}}A design obtained from 1852 {\tt d}\kern1pt$i$ by applying a random permutation to the 1853 points. (The order of the blocks is also permuted 1854 randomly.) An isomorphism from {\tt d}\kern1pt$i$ to 1855 {\tt d\kern1pt$i$\kern1ptx} may be found by the command 1856 \smallskip 1857 \hskip0.4in{\tt desiso\quad d\kern1pt$i$\quad d\kern1pt$i$x t} 1858 \smallskip 1859 which sets {\tt t} to one such isomorphism. 1860\vskip0pt} 1861\bigbreak 1862The subdirectory {\tt dmcl} contains a design based on 1863the sporadic simple group of McLaughlin (McL, degree 275). In this group, 1864a point stabilizer has orbits of length 1, 112, and 162. The design 1865{\tt dmcl} on $\{1,\ldots,275\}$ has 275 blocks, each of size 112; the 1866blocks are the orbits of length 112 in the 275 point stabilizers. 1867The group of this design, which must contain AUT(McL) and turns out to 1868equal to AUT(McL), may be computed by the command 1869\smallskip 1870\hskip0.4in{\tt desauto\quad dmcl\quad Y} 1871\smallskip 1872which saves the group as {\tt Y}. (Note that we are computing the group 1873of the design, not the group of the graph associated with the orbit of 1874length 112; in general, the design group is larger than the graph group, 1875although in this case they are the equal.) The directory also contains a 1876second design {\tt dmclx}, isomorphic to {\tt dmcl}. An isomorphism may 1877be found by the command 1878\smallskip 1879\hskip0.4in{\tt desiso\quad dmcl\quad dmclx\quad s} 1880\smallskip 1881which sets {\tt s} to an isomorphism from {\tt dmcl} to {\tt dmclx}. 1882\bigbreak 1883Finally, the subdirectories {\tt had32} and {\tt had104} 1884contains $32\times32$ and $104\times104$ matrices 1885over ${\rm GF}(3)$, respectively, which are 1886essentially the Paley--Hadamard matrices. 1887(The entries of -1 have been changed to 2.) The (monomial) automorphism 1888group of either of these Hadamard matrices may be computed by the command 1889\smallskip 1890\hskip0.4in{\tt matauto\quad -mm\quad had\kern1pt$i$\quad Z} 1891\smallskip 1892($i = 32{\rm\ or\ }104$), 1893which sets {\tt Z} to the automorphism group. This subdirectories also 1894contain matrices {\tt had\kern1pt$i$\kern1ptx} obtained by 1895applying random monomial 1896permutations to the rows and columns of {\tt had\kern1pt$i$}. Equivalence of 1897{\tt had\kern1pt$i$} and {\tt had\kern1pt$i$\kern1ptx} may be 1898established by the command 1899\smallskip 1900\hskip0.4in{\tt matiso\quad -mm\quad had\kern1pt$i$\quad had\kern1pt$i$\kern1ptx\quad w} 1901\smallskip 1902which sets {\tt w} to an monomial isomorphism 1903from {\tt had\kern1pt$i$} to {\tt had\kern1pt$i$\kern1ptx}. 1904Finally, the subdirectories contain Hadamard designs {\tt dhad\kern1pt$i$}\kern3pt\ 1905($i = 32{\rm\ or\ }104$) and equivalent designs {\tt dhad\kern1pt$i$\kern1ptx}, 1906whose groups may be computed using the {\tt desauto} command, and whose 1907equivalence may be established with the {\tt desiso} command. 1908% 1909% 1910\section{IX.\quad OTHER COMMANDS} 1911% 1912In the course of testing and benchmarking the partition backtrack 1913algorithms described in Section~IV, the author developed a number of other 1914programs. Most of these programs were put 1915together quickly, with a view toward simplicity rather than efficiency; 1916in some cases, they are very inefficient. Also, some of them perform 1917only minimal error checking. Nonetheless, they may prove useful since they 1918operate on objects specified in the format described in Section~II. 1919\medbreak 1920All of these programs accept the {\tt -a}, {\tt -i}, {\tt -mb:$k$}, {\tt -mw:$w$}, 1921{\tt -n:}{\it name}, {\tt -p:}{\it path}, and {\tt -q} options, as described 1922in Section~V, whenever they would be meaningful. (For example, the {\tt -i} 1923option is meaningful only if the command creates a permutation or 1924permutation group.) Other options vary by command, and are discussed separately 1925for each command below. 1926% 1927\subsection{Base and strong generating set construction:}The {\tt generate} 1928command may be used to construct a probable base and strong generating set 1929for the permutation group generated by specified permutations. The random 1930Schreier method (Leon, 1980) is used. If the group order is known in advance, 1931this method always produces a correct base and strong generating set, although 1932there is no bound on the time required to do so. Otherwise, 1933there is no guarantee that the method will produce a correct result. However, 1934in the author's experience, it nearly always does give a correct result, and 1935it runs far more quickly than alternative methods, such as the Schreier--Sims 1936or Schreier--Todd-Coxeter--Sims algorithms. 1937\medbreak 1938The format for the command is 1939% 1940\smallskip 1941\centerline{{\tt generate}\quad {\it options\/}\quad {\it inputGroup\/}\quad 1942 {\it outputGroup}} 1943% 1944\smallskip 1945where {\it options\/} denotes 1946\smallskip 1947\centerline{ 1948 [{\tt -a}]\kern-1pt\enskip 1949 [{\tt -i}]\kern-1pt\enskip 1950 [{\tt -mb:}$k$]\kern-1pt\enskip 1951 [{\tt -mw:}$w$]\kern-1pt\enskip 1952 [{\tt -n:}{\it name\/}]\kern-1pt\enskip 1953 [{\tt -nro}]\kern-1pt\enskip 1954 [{\tt -p:}{\it path\/}]\kern-1pt\enskip 1955 [{\tt -q}]\kern-1pt\enskip 1956 [{\tt -s:}{\it seed\/}]\kern-1pt\enskip 1957 [{\tt -ti:}$i$]\kern-1pt\enskip 1958 [{\tt -tr:}$m$]\kern-1pt\enskip 1959 [{\tt -z}]} 1960\smallskip 1961Here {\it inputGroup\/} denotes the original permutation group, for which 1962a base and strong generating set are not yet available. 1963The factored group order for {\it inputGroup\/} may or may not be present. 1964The random Schreier method is used to construct a probable base and strong 1965generating set for {\it inputGroup},, and the result is saved as the 1966permutation group {\it outputGroup}. 1967If the factored group order is present, the computation will continue until 1968a base and strong generating set has been found. Otherwise it continues until 1969{\it m\/} consecutive quasi--random elements of the group factor in terms of the 1970possible base and strong generating set, where {\it m\/} is the integer 1971specified in the {\tt -tr:}$m$ option (default 40). High values of 1972{\it m} may be specified to reduce the chance of an incorrect result, at the 1973cost of slowing down the computation. 1974\medbreak 1975Normally, before a new strong generator is added to the strong generating 1976set, an attempt is made to replace the new generator by a power of it, in 1977order to obtain generators of low order. (This may be desirable later on if the 1978Schreier--Todd--Coxeter--Sims method is used to verify the base and strong 1979generating set; in addition, it saves space whenever a non--involutory 1980generator is converted to an involution.) This attempt may be suppressed 1981by the {\tt -nro} option. Note, however, that replacement of generators 1982by powers is relatively inexpensive, so the {\tt -nro} option saves little time. 1983The {\tt -ti:}$i$ option may be specified in order to have the program 1984try harder to find involutory generators. Up to $i$ consecutive generators that 1985cannot be converted to involutory generators will be rejected. The default 1986for $i$ is 0; higher values often increase the execution time a good 1987deal. 1988\medbreak 1989If the {\tt -z} option is specified, the program will make some attempt 1990to remove certain redundant strong generators from the strong generating set for 1991{\it outputGroup}. 1992% 1993\subsection{Base change:}The {\tt chbase} 1994command may be used to change the base in a permutation group. The 1995command format is 1996% 1997\smallskip 1998\centerline{{\tt chbase}\quad {\it inputGroup\/}\quad 1999 $p_1,p_2,\ldots,p_k$\quad {\it outputGroup}} 2000\smallskip 2001where {\it options\/} denotes 2002\smallskip 2003\centerline{ 2004 [{\tt -a}]\enskip 2005 [{\tt -i}]\enskip 2006 [{\tt -mb:}$k$]\enskip 2007 [{\tt -mw:}$w$]\enskip 2008 [{\tt -n:}{\it name\/}]\enskip 2009 [{\tt -p:}{\it path\/}]\enskip 2010 [{\tt -q}]\enskip 2011 [{\tt -z}]} 2012\smallskip 2013The base for permutation group {\it inputGroup\/} is 2014changed, if necessary, so that it begins with $p_1,p_2,\ldots,p_k$, 2015and the group with this new base is saved as {\it outputGroup}. Note 2016that, in the list $p_1,p_2,\ldots,p_k$ of points, individual points 2017are separated by commas but {\it not\/} by blanks. Note also that the 2018points $p_1,p_2,\ldots,p_k$ are included in the new base even if 2019they are redundant as base points. However, no other redundant base points 2020will appear in the new base. If the {\tt -z} option is specified, certain 2021redundant strong generators will be removed following the base change. 2022% 2023% 2024\subsection{Conjugation by a specified permutation:}The {\tt cjper} 2025command may be used to conjugate an object (group, permutation, point set, 2026partition, design, matrix, or code) by a specified permutation. The command 2027format is 2028% 2029\smallskip 2030\centerline{{\tt cjper}\quad {\it options\quad type\quad object\quad 2031 conjugateObject\quad conjugatingPerm}} 2032\smallskip 2033where {\it options\/} denotes 2034\smallskip 2035\centerline{ 2036 [{\tt -a}]\enskip 2037 [{\tt -b}]\enskip 2038 [{\tt -d:}{\it deg\/}]\enskip 2039 [{\tt -i}]\enskip 2040 [{\tt -mb:}$k$]\enskip 2041 [{\tt -mm}]\enskip 2042 [{\tt -mw:}$w$]\enskip 2043 [{\tt -n:}{\it name\/}]\enskip 2044 [{\tt -p:}{\it path\/}]\enskip 2045 [{\tt -q}]\enskip} 2046\smallskip 2047Here {\it type\/} must be one of the keywords {\tt group}, {\tt perm}, 2048{\tt set}, {\tt partition}, {\tt design}, {\tt matrix}, or {\tt code},\enskip 2049{\it object\/} must be an object of the type designated by {\it type},\enskip 2050and {\it conjugatingPerm\/} must be a permutation. In the event that {\it object\/} 2051is a permutation, set, or partition, the {\tt -d:}{\it deg} option {\it must\/} 2052be used to specify the degree {\it deg}. The program sets 2053{\it conjugateObject\/} to the object obtained by conjugating {\it object\/} 2054by {\it conjugatingPerm\/}, in the case that {\it object\/} is a group 2055or permutation, or to the object obtained by 2056applying {\it conjugatingPerm\/} to {\it object}, if {\it object} is a 2057point set, partition, design, matrix, or code. In the event that 2058{\it object\/} is a group, the {\tt -b} option forces the program to 2059compute a base and strong generating set for {\it conjugateObject\/}; by 2060default, {\it conjugateObject\/} will have a base and strong generating 2061set only if {\it object\/} does. 2062\medbreak 2063In the event that {\it object\/} is a design or matrix, the degree 2064is treated as the number of points plus the number of blocks, or the 2065number of rows plus the number of columns, respectively. 2066Blocks or columns are permuted as well as points or rows. However, 2067since the input format for permutations permits a permutation of degree $n$ 2068to be treated as a permutation of any higher degree, this represents no 2069real restriction. 2070\medbreak 2071If {\it object\/} is a matrix over a finite field ${\rm GF}(q)$, the {\tt -mm} 2072option may be specified. Then {\it conjugatingPerm\/} must have degree 2073$(q-1)(r+c)$, where $r$ and $c$ are the number of rows and columns, and 2074must satisfy the ``monomial property'', as described in Section~III. 2075 2076% 2077\subsection{Conjugation by a random permutation:}The {\tt cjrndper} 2078command may be used to conjugate an object by a either a random permutation, 2079or by a permutation chosen at random from a specified permutation group. The command 2080format is 2081% 2082\smallskip 2083\centerline{{\tt cjrndper}\quad {\it options\quad type\quad object\quad 2084 conjugateObject}\quad [{\it conjugatingPerm\/}]} 2085\smallskip 2086where {\it options\/} denotes 2087\smallskip 2088\centerline{ 2089 [{\tt -a}]\kern-1pt\enskip 2090 [{\tt -b}]\kern-1pt\enskip 2091 [{\tt -d:}{\it deg\/}]\kern-1pt\enskip 2092 [{\tt -g:}{\it grp\/}]\kern-1pt\enskip 2093 [{\tt -i}]\kern-1pt\enskip 2094 [{\tt -mb:}$k$]\kern-1pt\enskip 2095 [{\tt -mm}]\kern-1pt\enskip 2096 [{\tt -mw:}$w$]\kern-1pt\enskip 2097 [{\tt -n:}{\it name}]\kern-1pt\enskip 2098 [{\tt -p:}{\it path\/}]\kern-1pt\enskip 2099 [{\tt -s:}{\it seed\/}]\kern-1pt\enskip 2100 [{\tt -q}]} 2101\smallskip 2102Here {\it type\/} must be one of the keywords {\tt group}, {\tt perm}, 2103{\tt set}, {\tt partition}, {\tt design}, {\tt matrix}, or {\tt code},\enskip 2104and {\it object\/} must be an object of the type designated by {\it type}. 2105In the event that {\it object\/} 2106is a permutation, set, or partition, the {\tt -d:}{\it deg} option {\it must} 2107be used to specify the degree {\it deg}. If {\it object\/} is a permutation 2108or permutation group, the program sets 2109{\it conjugateObject\/} to the object obtained by conjugating {\it object\/} 2110by a certain permutation $x$; if {\it object\/} is a point set, partition, 2111design, matrix, or code, it sets {\it conjugateObject\/} to the 2112object obtained by applying a certain permutation $x$ to {\it object}. 2113In either case, the permutation $x$ is 2114chosen at random from the group {\it grp}, if the {\tt -g:}{\it grp} option 2115is specified, or at random from the symmetric group, if the 2116{\tt -g:}{\it grp} option is omitted. If {\it conjugatingPerm\/} is specified, 2117the permutation $x$ is saved as {\it conjugatingPerm}. 2118The {\tt -s:}{\it seed} option may be used to specify 2119a specific seed for the random number generator that is used internally. 2120In the event that {\it object\/} is a group, the {\tt -b} option forces the 2121program to compute a base and strong generating set for {\it conjObject}, even 2122when one is not available for {\it object}. 2123\medbreak 2124In the event that {\it object\/} is a design (or matrix), both points 2125and blocks (or both rows and columns) are permuted. 2126\medbreak 2127If {\it object\/} is a matrix over a finite field ${\rm GF}(q)$, the {\tt -mm} 2128option may be specified. Then a random monomial permutation is applied 2129to the rows and columns of the input matrix. 2130% 2131% 2132% 2133\subsection{Commutator groups and lower central series:}The {\tt commut} 2134command may be used to compute commutator groups. Repeated application of 2135the command may be used to compute lower central series. Specifically, given 2136a group $G$ and a (not necessarily normal) subgroup $H$ of $G$, the command 2137computes the commutator group $C = [G,H]$. The command format is 2138% 2139\smallskip 2140\centerline{{\tt commut}\quad {\it options}\quad {\it permGroup}\quad 2141 [{\it subgroup\/}]\quad {\it commutatorGroup}} 2142\smallskip 2143where {\it options\/} denotes 2144\smallskip 2145\centerline{ 2146 [{\tt -a}]\enskip 2147 [{\tt -i}]\enskip 2148 [{\tt -mb:}$k$]\enskip 2149 [{\tt -mw:}$w$]\enskip 2150 [{\tt -n:}{\it name}]\enskip 2151 [{\tt -p:}{\it path\/}]\enskip 2152 [{\tt -q}]} 2153\smallskip 2154Here, {\it permGroup\/}, {\it subgroup\/}, and {\it commutatorGroup\/} 2155play the role of $G$, $H$, and $C$ above, respectively. 2156If {\it subgroup\/} is specified, it must be a subgroup of {\it permGroup\/} 2157(not checked); the command sets {\it commutatorGroup\/} 2158to the commutator of {\it permGroup\/} and {\it subgroup}. If subgroup is 2159omitted, the command sets {\it commutatorGroup\/} to the commutator of 2160{\it permGroup\/} with itself (the derived group). 2161\medbreak 2162At present, the strong generating set for the commutator group is 2163constructed only by the random Schreier method. Thus there is a 2164(probably small) possibility that the base and strong generating set 2165constructed for the commutator group will be incorrect. (If this 2166occurs, the generators constructed will generate the commutator group, but 2167not strongly. This undesirable feature will be fixed eventually.) 2168\medbreak 2169The return code from the {\tt commut} command will 0 if the commutator group 2170has order 1. 2171Otherwise the return code will depend on whether the order of $H$ (i.e., 2172{\it subgroup\/}) 2173is known in advance. If so, the return code will 1 if $\vert C\vert \neq 2174\vert H\vert$ and 2 otherwise. (If $H$ is normal in $G$, these correspond 2175to the cases $H \subset G$ and $H = G$, respectively.) If not, the return 2176code will be 3. 2177% 2178% 2179% 2180\subsection{Comparison of groups, normality, and centralization:}The {\tt compgrp} command may be 2181used to check if either of two permutation groups is contained 2182in the other, or normalizes the other, or whether the two groups 2183centralize each other. The command format is 2184% 2185\smallskip 2186\centerline{{\tt compgrp}\quad [{\tt -c}] \enskip[{\tt -n}]\enskip 2187 [{\tt -mb:}$k$]\enskip [{\tt -mw:}$w$]\enskip 2188 [{\tt -p:}{\it path\/}]\quad {\it permGroup1\quad permGroup2}} 2189\smallskip 2190This command checks if either of {\it permGroup1\/} or {\it permGroup2\/} is contained 2191in the other. If the {\tt -n} option is specified, it also checks if 2192either group normalizes the other. (Note here the {\tt -n} option is used 2193for a different purpose that that described in Section~V.) If the {\tt -c} option is given, it 2194checks whether the two groups centralize each other. Messages indicating the result are 2195written to the standard output. The return code is 0 if the two groups 2196are equal, 1 if {\it permGroup1\/} is a proper subgroup of {\it permGroup2\/}, 21972 if {\it permGroup2\/} is a proper subgroup of {\it permGroup1\/}, and 3 2198otherwise.\quad Note: The procedure for checking normality 2199is, at present, extremely inefficient in many cases. 2200% 2201% 2202% 2203\subsection{Comparison of permutations:}The {\tt compper} command may be 2204used to check if two permutations are equal, or if a permutation is the 2205identity. The command format is 2206% 2207\smallskip 2208\centerline{{\tt compper}\quad {\it degree\quad permutation1}\quad 2209 {\tt [}{\it permutation2\/}{\tt ]}} 2210\smallskip 2211This command checks if {\it permutation1\/} and {\it permutation2}, both of 2212which must be permutations of degree {\it degree}, are equal. It prints a 2213message indicating whether the permutations are equal, and gives a return 2214code of 0 if they are equal and 1 otherwise. If {\it permutation2\/} is 2215omitted, it is taken as the identity; thus the command checks if 2216{\it permutation1\/} is the identity. 2217% 2218% 2219% 2220\subsection{Comparison of point sets:}The {\tt compset} command may be 2221used to check if two point sets are equal. The command format is 2222% 2223\smallskip 2224\centerline{{\tt compset}\quad {\it degree\quad set1}\quad 2225 {\tt [}{\it set2\/}{\tt ]}} 2226\smallskip 2227This command checks if {\it set1\/} and {\it set2}, both of 2228which must be points sets of degree {\it degree}, are equal, or if either 2229is contained in the other. if {\it set2\/} is omitted, it is taken to be 2230the empty set, and the command checks if {\it set1\/} is empty. It prints a 2231message indicating the result. If {\it set2\/} is specified, the return code is 0 if 2232the two sets are equal, 1 if {\it set1\/} is properly contained in {\it set2\/}, 22332 if {\it set1\/} properly contains {\it set2\/}, and 3 otherwise. 2234If {\it set2\/} is omitted, the return code is 0 if {\it set1\/} is empty 2235and 1 otherwise. 2236% 2237% 2238\subsection{Coset weight distributions of codes:}The {\tt cwtdist} 2239command\footnote{${}^{\dag}$}{\elevenpoint At time of writing, this command 2240was not complete. It should be available shortly.} 2241may be used to compute the coset weight distribution of a linear code. 2242At present, the program is restricted to binary codes of codimension at 2243most 32. The program is highly optimized; nonetheless, time and space 2244requirements may restrict the codimension to values less than its maximum 2245of 32. The command format is 2246% 2247\smallskip 2248\centerline{{\tt cwtdist}\quad {\it options}\quad {\it code}\quad 2249 [{\it maxCosWeight\/}\quad [{\it matrix\/}]]} 2250\smallskip 2251where {\it options\/} denotes 2252\smallskip 2253\centerline{ 2254 [{\tt -a}]\enskip 2255 [{\tt -n:}{\it name\/}]\enskip 2256 [{\tt -p:}{\it path\/}]\enskip 2257 [{\tt -q}]} 2258\smallskip 2259The program computes the coset weight distribution of the code 2260{\it code\/}, that is, for each $d$, it determines the number of cosets of 2261the code having minimum weight $d$. If {\it maxCosWeight\/} is specified 2262(It should be an integer.), the computation is performed only for 2263$d \leq {\it maxCosWeight}$. If {\it matrix\/} is given, a coset representative 2264is saved for one coset whose minimum weight is the minimum of the covering 2265radius and {\it maxCosetWeight\/}. {\it Note:\/} It is not possible to 2266specify {\it matrix\/} without specifying {\it maxCosWeight\/}; however, 2267an artificially large value of {\it maxCosWeight\/} may be given instead. 2268% 2269% 2270% 2271\subsection{Designs from groups:}The {\tt orbdes} command may be used to 2272construct a block design $D$ from a permutation group $G$, which normally 2273should be transitive. The design $D$ will have $n$ points and $n$ blocks, each 2274having the same number of points, where $n$ is the degree. The automorphism 2275group ${\rm AUT}(D)$ will contain the group $G$ (perhaps properly). 2276For a specified point $\gamma$, let $\Gamma$ denote the orbit of $\gamma$ 2277under the point stabilizer $G_1$. The blocks of $D$ are exactly 2278$\Gamma^{u_1},\ldots,\Gamma^{u_k}$, where $k$ is the size of the $G$--orbit 2279of 1, and $u_1,\ldots,u_k$ map 1 to the different points of the $G$--orbit 2280of 1. The command format is 2281% 2282\smallskip 2283\centerline{{\tt orbdes}\quad [{\tt -a}]\enskip[{\tt -m}]\enskip 2284 [{\tt -mb:}$k$]\enskip [{\tt -mw:}$w$]\enskip 2285 [{\tt -p:}{\it path\/}]\quad 2286 {\it permGroup}\quad {\it point}\quad {\it design}} 2287\smallskip 2288Here {\it permGroup}, {\it point}, and {\it design\/} play the role of 2289$G$, $\gamma$, and $D$ above, respectively. If the {\tt -m} option is 2290given, the incidence matrix of the design is written out as a matrix; 2291otherwise the design is written in the standard format for designs. 2292% 2293% 2294% 2295\subsection{Finding group elements of specified order:}The {\tt fndelt} 2296command may be used to locate group elements of specified order, using 2297a quasi-random search process. (Random group elements are examined in 2298searching for ones whose order is a multiple of the specified order.) 2299The command format is 2300% 2301\smallskip 2302\centerline{{\tt fndelt}\quad {\it options}\quad {\it permGroup} \quad 2303 $n$\quad $k_1$\quad $k_2$\quad$\ldots$} 2304\smallskip 2305where {\it options\/} denotes 2306\smallskip 2307\centerline{ 2308 [{\tt -a}]\enskip 2309 [{\tt -f}]\enskip 2310 [{\tt -i}]\enskip 2311 [{\tt -m:}{\it trials}]\enskip 2312 [{\tt -mb:}$k$]\enskip 2313 [{\tt -mw:}$w$]\enskip 2314 [{\tt -n:}{\it name}]} 2315\vskip2pt 2316\centerline{ 2317 [{\tt -o:}{\it ord\/}]\enskip 2318 [{\tt -p:}{\it path\/}]\enskip 2319 [{\tt -po}]\enskip 2320 [{\tt -s:}{\it seed\/}]\enskip 2321 [{\tt -wg:}{\it grp\/}]\enskip 2322 [{\tt -wp:}{\it perm\/}]} 2323\smallskip 2324By default, the command searches quasi--randomly 2325until it finds $n$ involutions in the 2326group {\it permGroup\/}, and 2327if $k_1,\,k_2,\,\ldots$ are specified, it saves the $k_1$\kern1ptst, 2328$k_2$\kern1ptnd, $\ldots$ elements found. (See discussion of the 2329{\tt -wp} and {\tt -wg} options below.) The value of $n$ may be at 2330most 99. The seed used in the random number generator may be specified 2331by the {\tt -s:}{\it seed\/} option; two invocations with the same 2332(default or specified) seed should produce identical results. 2333If the {\tt -o:}{\it ord\/} 2334option is given, the command searches for elements of order {\it ord}, rather 2335than for involutions. If the {\tt -f} option is specified, it prints 2336the number of fixed points of each element found. If the {\tt -po} option 2337is specified, it prints the orders of all products of the elements found. 2338If the {\tt -wp:}{\it perm\/} option is given and $k_1$ is specified, 2339the $k_1$\kern1ptst element found is saved as the permutation {\it perm}. 2340If the {\tt -wg:}{\it grp\/} is given and at least $k_1$ is specified, 2341a group {\it grp\/} is created using the $k_1$\kern1ptst, 2342$k_2$\kern1ptnd, $\ldots$ elements found as generators. 2343\medbreak 2344% 2345In some groups, elements of a specified order may be very difficult 2346to find using the quasi--random search technique employed by {\tt fndelt}. 2347For example, it is very difficult to find involutions in ${\rm PGL}_2(2^k)$ 2348if $k$ is fairly high (say 10 to 15). The {\tt -m:}{\it trials\/} option 2349may be used to terminate the command after {\it trials\/} random 2350group elements have been generated, regardless of how many elements of 2351the desired order have been found. By default, {\it trials\/} is 2352essentially infinite. 2353\medbreak 2354% 2355% 2356% 2357\subsection{Normal closures:}The {\tt ncl} 2358command may be used to compute normal closures of subgroups. Specifically, 2359given a group $G$ and a subgroup $H$ of $G$, the command 2360computes the normal closure $H^G$ of $H$ in $G$. The command format is 2361% 2362\smallskip 2363\centerline{{\tt ncl}\quad {\it options}\quad {\it permGroup}\quad 2364 {\it subgroup\/}\quad {\it normal closure}} 2365\smallskip 2366where {\it options\/} denotes 2367\smallskip 2368\centerline{ 2369 [{\tt -a}]\enskip 2370 [{\tt -i}]\enskip 2371 [{\tt -mb:}$k$]\enskip 2372 [{\tt -mw:}$w$]\enskip 2373 [{\tt -n:}{\it name}]\enskip 2374 [{\tt -p:}{\it path\/}]\enskip 2375 [{\tt -q}]} 2376\smallskip 2377The command sets {\it normalClosure\/} 2378to the normal closure in {\it permGroup\/} of {\it subgroup}. (Note that 2379{\it subgroup\/} must be a subgroup of {\it permGroup\/}; this is not checked.) 2380\medbreak 2381At present, the strong generating set for the normal closure is 2382constructed only by the random Schreier method. Thus there is a 2383(probably small) possibility that the strong generating set 2384may be incorrect. (This will 2385be fixed eventually; if it occurs, the generators obtained will generate 2386the normal closure, but not strongly.) 2387% 2388% 2389% 2390\subsection{Orbit structure:}The {\tt orblist} command performs various 2391calculations relating to the orbit structure of a specified group, or to the 2392orbit structure of point stabilizers within the group. The command format 2393% 2394\smallskip 2395\centerline{{\tt orblist}\quad {\it options}\quad {\it permGroup}\quad 2396 [\kern1pt$p_1,p_2,\ldots,p_k$\quad[{\it ptStabGroup\/}]\kern1pt]} 2397\smallskip 2398where {\it options\/} denotes 2399\smallskip 2400\centerline{ 2401 [{\tt -a}]\enskip 2402 [{\tt -i}]\enskip 2403 [{\tt -len}]\enskip 2404 [{\tt -lr}]\enskip 2405 [{\tt -mb:}$k$]\enskip 2406 [{\tt -mw:}$w$]\enskip 2407 [{\tt -n:}{\it name\/}]\enskip 2408 [{\tt -p:}{\it path\/}]} 2409\vskip2pt 2410\centerline{ 2411 [{\tt -ps:}{\it set\/}]\enskip 2412 [{\tt -q}]\enskip 2413 [{\tt -r}]\enskip 2414 [{\tt -s:}{\it seed\/}]\enskip 2415 [{\tt -wno:}{\it $k$}]\enskip 2416 [{\tt -wo:}{\it $p_1,p_2,\ldots$}]\enskip 2417 [{\tt -wp:}{\it partn\/}]\enskip 2418 [{\tt -z}]} 2419\smallskip 2420In the absence of any options, and with only one non--option parameter, 2421the command writes (to standard output) 2422the orbits of the group {\it permGroup}. For each orbit, the orbit 2423representative, the orbit length, and the list of points in the orbit 2424are written. If the {\tt -r} option is given, the order in which the 2425orbits are listed is randomized; the seed for the random number generator 2426that is used may be specified by means of the {\tt -s:}{\it seed\/} option. 2427(Note that the {\tt -r} option is ignored if the {\tt -len} or {\tt -lr} options are 2428specified.) 2429\medbreak 2430If the {\tt -len} option is specified, only the orbit lengths are 2431written. If the {\tt -lr} option is given, only the 2432orbit representatives and orbit lengths are given; the output consists of 2433a list of pairs {\it rep\/}{\tt :}{\it len}, where {\it rep\/} is an 2434orbit representative and {\it len\/} is the length of the corresponding 2435orbit. 2436\medbreak 2437The {\tt -wp:}{\it partn} may be used save the orbit partition of the 2438group as the partition {\it partn}. 2439The {\tt -wo:}{\it $p_1,p_2,\ldots$} option may be used to save the 2440union of the orbits of points $p_1,p_2,\ldots$ as a point set; the 2441name of the point set is the string {\it set\/} given by 2442the {\tt -ps:}{\it set\/} option. 2443Alternatively, the {\tt -wno:}{\it $k$} option causes the union of 2444the first $k$ orbits to be saved as a point set, whose name again 2445is specified by the {\tt -ps:}{\it set\/} option. 2446\medbreak 2447If a second non--option parameter $p_1,p_2,\ldots,p_k$ is specified, 2448all orbit calculations are carried out in the stabilizer in ${\it permGroup\/}$ 2449of the point sequence $p_1,p_2,\ldots,p_k$, rather than in {\it permGroup\/} 2450itself. Note that this entails a base change for the group {\it permGroup}. 2451The {\tt -z} option causes redundant strong generators for {\it permGroup} 2452to be removed following this base change. 2453Specifying a third non--option parameter {\it ptStabGroup\/} option causes 2454point stabilizer of $p_1,p_2,\ldots,p_k$ to be saved 2455as the permutation group {\it ptStab}. 2456% 2457% 2458\subsection{Point stabilizers:}The {\tt ptstab} 2459command may be used to compute point stabilizers in permutation groups. The 2460command format is 2461% 2462\smallskip 2463\centerline{{\tt ptstab}\quad {\it options}\quad {\it permGroup}\quad 2464 $p_1,p_2,\ldots,p_k$\quad {\it ptStabGroup\/}} 2465\smallskip 2466where {\it options\/} denotes 2467\smallskip 2468\centerline{ 2469 [{\tt -a}]\enskip 2470 [{\tt -i}]\enskip 2471 [{\tt -mb:}$k$]\enskip 2472 [{\tt -mw:}$w$]\enskip 2473 [{\tt -n:}{\it name\/}]\enskip 2474 [{\tt -p:}{\it path\/}]\enskip 2475 [{\tt -q}]\enskip 2476 [{\tt -z}]} 2477\smallskip 2478The point stabilizer in the group {\it permGroup\/} of the list 2479$p_1,p_2,\ldots,p_k$ is computed and saved as the permutation group 2480{\it ptStabGroup}. Note that, in the list $p_1,p_2,\ldots,p_k$, individual 2481points are separated by commas but {\it not\/} by blanks. 2482The {\tt -z} option causes certain redundant strong generators for {\it ptStabGroup} 2483to be removed before the group is saved. 2484% 2485% 2486% 2487% 2488\subsection{Random point sets and partitions:}The {\tt randobj} 2489command may be used to construct a random $k$--element subset of 2490$\{1,\ldots,n\}$ for specified $n$ and $k$, or to construct a partition 2491of $\{1,\ldots,n\}$ that is random subject to the cells having specified 2492sizes. The command format 2493% 2494\smallskip 2495\centerline{{\tt randobj}\quad {\it options}\quad {\it type}\quad $n$\quad 2496 $k_1,k_2,\ldots,k_p$\quad {\it newObject}} 2497\smallskip 2498where {\it options\/} denotes 2499\smallskip 2500\centerline{ 2501 [{\tt -a}]\enskip 2502 [{\tt -e}]\enskip 2503 [{\tt -n:}{\it name\/}]\enskip 2504 [{\tt -s:}{\it seed\/}]} 2505\smallskip 2506Here {\it type\/} must be either {\tt set} or {\tt partition}; it indicates 2507whether a point set or partition is to be constructed. For a point set, 2508$p$ must be 1; a random $k_1$--element subset of $\{1,\ldots,n\}$ is constructed. 2509For a partition, in the absence of the {\tt -e} option, 2510$k_1 + k_2 + \ldots + k_p$ must equal $n$; a partition of $\{1,\ldots,n\}$ 2511random subject to having cell sizes $k_1$,~$k_2$,...,~$k_p$ is constructed. 2512However, if the {\tt -e} option is specified, then $p$ must equal 1, and 2513a random partition having $k_1$ cells of equal size (as closely as possible) 2514is constructed. In any case, the point set or partition constructed is saved 2515as the object {\it newObject}. 2516\medbreak 2517The {\tt -s:}{\it seed} option may be used to specify an initial seed for 2518the random number generator that is used. 2519% 2520% 2521\subsection{Weight distributions of codes:}The {\tt wtdist} 2522command may be used to compute the weight distribution of a linear code. 2523The program is highly optimized, both for binary and nonbinary codes. 2524The command format is 2525% 2526\smallskip 2527\centerline{{\tt wtdist}\quad {\it options}\quad {\it code}\quad 2528 [{\it saveWeight\/}\quad {\it matrix\/}]} 2529\smallskip 2530where {\it options\/} denotes 2531\smallskip 2532\centerline{ 2533 [{\tt -a}]\enskip 2534 [{\tt -b}]\enskip 2535 [{\tt -g}]\enskip 2536 [{\tt -n:}{\it name\/}]\enskip 2537 [{\tt -p:}{\it path\/}]\enskip 2538 [{\tt -pf:}$p$]\enskip 2539 [{\tt -s:}$m$]\enskip 2540 [{\tt -q}]\enskip 2541 [{\tt -1}]} 2542\smallskip 2543The weight distribution of the code {\it code\/} is computed and written to 2544the standard output. If {\it saveWeight\/} (which should be a positive 2545integer) and {\it matrix\/} are specified, the codewords of weight 2546{\it saveWeight\/} are saved; specifically, a new matrix {\it matrix\/} is 2547created whose rows are the vectors of weight {\it saveWeight\/} in the 2548code {\it code}. However, for nonbinary fields, only one codeword from 2549each one-dimensional subspace is saved. (Thus, for a code over 2550${\rm GF}(q)$ with $k$ vectors of weight {\it saveWeight}, {\it matrix\/} will 2551have $k/(q-1)$ rows.) Also, if the {\tt -1} option is specified, only one 2552codeword of weight {\it saveWeight\/} will be saved, and thus {\it matrix\/} 2553will have only one row. In the event that the code has no codewords of the 2554specified weight, the matrix is not created. 2555\medbreak 2556Four options, {\tt -b}, {\tt -g}, {\tt pf:}$p$, and {\tt s:}$m$, are never 2557necessary but may be used to optimize performance. The {\tt -s:}$m$ 2558option may be coded if codewords of weight {\it saveWeight\/} are to be 2559saved, and if the number of such codewords is known in advance; the value 2560of $m$ should be the number of such codewords (excluding scalar multiples, 2561for nonbinary fields). Use of this option saves some time and space. (If 2562an incorrect value of $m$ is specified, the savings in time and space may 2563be lost, but the results will still be correct.) 2564\medbreak 2565To understand the other optimization options, 2566it is necessary to understand that the {\tt wtdist} command invokes one of 2567two programs: a considerably optimized program for codes over any field, or 2568an even more highly optimized one for binary codes meeting certain 2569constraints on length and dimension. The binary code program requires a fixed 2570amount of time (several seconds or more on a micro or workstation) to 2571construct a certain table of size 65536, even if the 2572dimension of the code is small. Accordingly, the {\tt wtdist} command 2573invokes the general code program for binary codes of low dimension; however, 2574the criteria for choosing the cutoff point is relatively crude, and often 2575a nonoptimal choice may be made. The {\tt -g} option forces the general 2576code program to be used, even if the binary one would be chosen by default. 2577The {\tt -b} option forces the binary code program to be used, provided the 2578code is binary, provided its length is at most 128, and provided its 2579dimension is at most 3. (If any of these conditions fail, the binary 2580program cannot be used.) 2581\medbreak 2582The {\tt -pf:}$p$ option is applicable only if 2583the general code program is employed. The value of $p$, which is referred 2584to as the {\it packing factor}, should be a positive integer such that 2585$q^p\leq 65535$. (Here $q$ is the field size.) Internally, the program will pack 2586$p$ coordinates of each codeword into a single 16--bit word. Higher values 2587of $p$ improve performance on codes of high dimension. On the other hand, 2588the size of the internal tables that must be allocated and initialized 2589rise very rapidly as a function of $p$, and in particular, a value of 2590$p$ maximal subject to $q^p\leq 65535$ will be practical only with a 2591rather large memory, and will be optimal with respect to time 2592only for codes of quite high dimension, because of the large amount of time 2593spent initializing the tables. (The size in bytes of the largest single 2594table used internally is roughly $q^p e k \lceil n/p\rceil$, where $n$ is 2595the length, $k$ is the dimension, and $e$ is the exponent of the field.) 2596The program will choose a packing factor by default, but at present the 2597procedure for making this choice is crude. In particular, if the program 2598runs out of memory, a smaller packing pactor should be specified. 2599% 2600% 2601\section{X.\quad THE UNIX DISTRIBUTION} 2602% 2603On Unix, the programs, documentation, and examples will be available 2604by anonymous ftp from {\tt math.uic.edu}. The 2605directory {\tt pub/leon/partn} should contain the following files, 2606where {\it r} denotes the release number, e.g. {\tt 1.00}: 2607\vskip1pt 2608\smallskip 2609\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 2610doc-\kern-1pt{\it r}.tar.Z 2611examples-\kern-1pt{\it r}.tar.Z 2612src-\kern-1pt{\it r}.tar.Z 2613bin16-\kern-1pt{\it r}.sun4.tar.Z 2614bin16-\kern-1pt{\it r}.sun3.tar.Z 2615\vskip-2pt 2616bin32-\kern-1pt{\it r}.sun4.tar.Z 2617bin32-\kern-1pt{\it r}.sun3.tar.Z 2618\vskip0pt}} 2619\vskip-2pt 2620(The last two files may be omitted to conserve disk space, but can be made 2621available on request; contact the author at {\tt leon@turing.math.uic.edu}.) 2622Users with a Sun/4 should obtain the files {\tt doc.tar.Z}, 2623{\tt examples.tar.Z}, and {\tt bin16.sun4.tar.Z}, which contain, respectively, 2624the documentation, the examples, and 16-bit executables for the Sun/4. 2625Users desiring the C language source code (of limited use, due to inadequate 2626documentation) should obtain the file {\tt src.tar.Z}. Note that source code 2627is not required since binary executables for the programs are supplied. 2628Users needing 2629to compute with groups of degree greater that 65000 (approximate) should 2630obtain the file {\tt bin32.sun4.tar.Z}, which contains 32-bit executables. 2631Users with a Sun/3 merely substitute ``{\tt sun3}'' for ``{\tt sun4}'' in 2632the preceding instructions. Other users should obtain only the files 2633{\tt doc.tar.Z}, {\tt examples.tar.Z}, and {\tt src.tar.Z}. It will be 2634necessary to compile the source; a make file is provided for this purpose 2635(See Section~XI). 2636\smallskip 2637A directory, say {\tt partn}, should be created, and all the files should 2638be downloaded or moved to this directory. They should then be uncompressed 2639and extracted by commands such as 2640\smallskip 2641\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 2642uncompress -v doc.tar.Z 2643tar xvf doc.tar 2644\vskip0pt}} 2645\smallskip 2646(Repeat the above for each of the files.) 2647The result should be subdirectories of {\tt partn} as follows: 2648\medbreak 2649\hskip0.45truein\hbox to 0.85truein{\tt doc\hfil}{Documentation for the programs -- 2650 primarily this manual.} 2651\vskip2pt 2652\hskip0.45truein\hbox to 0.85truein{\tt examples\hfil}{The subdirectories of this 2653 directory contain examples. See Section~VIII.} 2654\vskip2pt 2655\hskip0.45truein\hbox to 0.85truein{\tt test\hfil}{Unix shell scripts to test 2656 the partition backtrack programs, using some of the examples provided 2657 in the {\tt examples} subdirectory.} 2658\vskip2pt 2659\hskip0.45truein\hbox to 0.85truein{\tt src\hfil}\vtop{\hsize=5.2truein\relax 2660 Source code and a make file, 2661 to allow compilation of the programs on machines other than the 2662 Sun/3 and Sun/4.} 2663\vskip2pt 2664\hskip0.45truein\hbox to 0.85truein{\tt bin16\hfil}{executable programs for the Sun/3 2665 or Sun/4, using 16--bit integers.} 2666\vskip2pt 2667\hskip0.45truein\hbox to 0.85truein{\tt bin32\hfil}{executable programs for the Sun/3 2668 or Sun/4, using 32--bit integers.} 2669\smallskip 2670For the Sun/3 or Sun/4, the appropriate directory {\tt partn/bin16} or 2671{\tt partn/bin32} should be added to the path, or the files from one of 2672those directories should be copied to a directory on the path. For other 2673Unix machines, it will be necessary to recompile the source; see Section~XI. 2674% 2675\medbreak 2676Once installation is complete, the programs may be tested using the 2677shell scripts in the subdirectory {\tt test}. Specifically, the following 2678shell scripts, written for the Bourne shell, are provided: 2679\smallskip 2680\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 2681test\_setstab 2682test\_cent 2683test\_inter 2684test\_desauto 2685test\_setimage 2686test\_conj 2687test\_desiso 2688\vskip0pt}} 2689Each of the above shell files may be run, without options or parameters. 2690When {\tt test\_setstab} is run, the output is collected in a file named 2691{\tt setstab.output}, as well as appearing on the screen. This file 2692may be compared to the file {\tt setstab.correct}, supplied in the subdirectory 2693{\tt tests}, which contains the correct output. The files should match 2694exactly. The comparison may be performed, for example, with the command 2695\smallskip 2696\vskip2pt 2697\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 2698diff setstab.output setstab.correct 2699\vskip0pt}} 2700The other shell files work in an analogous manner. 2701\medbreak 2702The tests above may take a number of hours, depending on the speed of the 2703machine. In addition, they require several megabytes of memory. Each of 2704the shell files accepts an option {\tt -s}, which runs a much less time--taking 2705series of tests, requiring less memory. When this option is used with 2706{\tt test\_setstab}, the output in file {\tt setstab.output} should be 2707compared to the file {\tt setstab-s.correct}, rather than to 2708{\tt setstab.correct}. A similar remark applies to the other tests. 2709\medbreak 2710The programs described in this manual are also available, in binary form, 2711for the IBM~PC and compatibles, under MS~DOS, and for the IBM~370 2712family of machines, under CMS. For details, please contact the author. 2713% 2714% 2715\section{XI.\quad COMPILING THE SOURCE CODE} 2716% 2717As mentioned earlier, compiled versions of the programs described here are 2718available for the IBM~PC (DOS), the Sun/3 and Sun/4 (Unix), and the 2719IBM~370 (CMS). For other systems, it will be necessary to compile the 2720C source code. The information in this section is intended for users 2721intending to compile the source code. 2722\medbreak 2723To compile the C source code, a compiler that supports ANSI Standard C is 2724required. 2725With very minor exceptions, the source code conforms to the ANSI standard 2726for C; it does, however, make use of a number of features not present in 2727most pre--ANSI versions of C. The code was written under the assumption 2728that it would be compiled with optimization turned on, so it is important 2729to enable optimization, as the programs tend to run quite slowly if 2730compiled with optimization disabled.\footnote{${}^{\dag}$}{\elevenpoint However, some compilers 2731fail to optimize the code correctly. GNU~C~1.39 and~2.1 (Sun/3, Sun/4) and 2732Waterloo~C 3.2 (IBM~370) optimize it correctly; at present, 2733Borland~C++~3.0 and Microsoft~C~5.1 do not. 2734Microsoft~C~6.0/7.0 and Borland~C++~3.1 have not been 2735tested.} At present large sections of the source code 2736are not commented or are commented incorrectly. Accordingly, the source 2737is provided primarily so that users may compile the programs on other 2738machines, rather than modify them. Eventually the author hopes to 2739distribute adequately documented source code. 2740\medbreak 2741Prior to compiling the source, it is necessary to determine whether a 2742special timing function needs to be supplied. By default the programs 2743use the C standard library function {\tt clock()} to measure execution 2744times. This is adequate on many systems. However, on some systems (e.g., 2745Sun/3 and Sun/4 Unix), a problem arises because the {\tt clock()} function returns a 2746result with a resolution of one microsecond and thus ``wraps around'' in about 274736 minutes. Unless the user is content with timing statistics correct modulo 2748$2^{32}$ microseconds (about 71.58 minutes), an alternate timing function 2749must be supplied in a file which should be named {\tt cputime.c}; 2750this function must return a value of type {\tt long} 2751which represents the elapsed CPU time, and C macros 2752{\tt CPU\_TIME} and {\tt TICK} must be 2753defined to specify the name of this special 2754function (e.g., {\tt cpuTime}) and the resolution 2755of the function (in clock ticks per second), respectively. 2756In addition, a make file macro {\tt CPUTIME} must be defined to have 2757the value {\tt cputime.o} (assuming object code files have suffix {\tt o}). 2758These macros are discussed in more detail below. 2759For the Sun/3 and Sun/4, source code for such a function 2760{\tt cpuTime()} is supplied in the file {\tt cputime.c}; perhaps this function 2761will work on other Unix systems as well. In the remainder of this section, 2762it is assumed that such a function, if needed, has already been written. 2763\medbreak 2764A make file (named {\tt Makefile}) is provided with the source. This make file 2765is designed for the GNU~C compiler, version 2, on the Sun/3 and Sun/4, but with some 2766other compilers and systems, only simple editting of the first few lines of the make file 2767should be needed; the purpose of these lines is to define appropriate 2768make file macros. For some compilers, more extensive editting of the 2769make file may be 2770required. Note that the make file assumes that all source code and include 2771files (except system include files) are in the currect directory, and that 2772all object and executable files are to be placed in this directory. 2773\medbreak 2774The make file provided with the source begins as follows: 2775\medbreak 2776\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 2777COMPILE = gcc 2778DEFINES = -DSUN\_UNIX\_GCC -DINT\_SIZE=32 -DCPU\_TIME=cpuTime -DTICK=1000 2779 -DLONG\_EXTERNAL\_NAMES -Dclock\_t=long 2780INCLUDES = 2781COMPOPT = -c -O2 -Wall 2782LINKNAME = -o 2783LINKOPT = -v 2784OBJ = o 2785CPUTIME = cputime.o 2786BOUNDS = 2787}} 2788\medbreak 2789The purpose of the make file macros defined here is as follows: 2790\smallbreak 2791{\advance\leftskip by 0.3in\noindent 2792 {\tt COMPILE}:\quad This macro specifies the command to invoke the C compiler; 2793 it may include path information. 2794\smallbreak 2795 {\tt DEFINES}:\quad This make file macro specifies C macros to be defined 2796 for the compilation; these are discussed below. 2797\smallbreak 2798 {\tt INCLUDES}:\quad This macro is used to tell the compiler where 2799 to search for include files, if they are located 2800 other than in the standard location. 2801\smallbreak 2802 {\tt COMPOPT}:\quad This macro is used to specify compile--time options, 2803 other than those given by means of the 2804 {\tt DEFINES} and {\tt INCLUDES} macros. These 2805 options should include code optimization and 2806 compile--only (no linking) if these are not 2807 defaults. For the IBM~PC, an option specifying the 2808 large memory model should be given. 2809\smallbreak 2810 {\tt LINKNAME}:\quad This macro is used to specify the linker option 2811 used to give the name of the executable file 2812 to be created. 2813\smallbreak 2814 {\tt LINKOPT}:\quad This macro is used to specify linker options, other 2815 than that given by the {\tt LINKNAME} macro above. 2816\smallbreak 2817 {\tt OBJ}:\quad This macro is used to specify the suffix (file type) 2818 for object files. Normally this would be {\tt o} 2819 on Unix and {\tt obj} on MS~DOS. 2820\smallbreak 2821 {\tt CPUTIME}:\quad Unless a special timing function is to be supplied 2822 (see discussion above), this value of this macro should 2823 be the null string. If a special timing function is 2824 supplied, the value of the {\tt CPUTIME} macro should 2825 be {\tt cputime.o}, assuming object files have suffix 2826 {\tt o}. 2827\smallbreak 2828 {\tt BOUNDS}:\quad This macro is present for use on MS~DOS with Bounds Checker, 2829 a debugging product published by Nu-Mega Technologies 2830 and used heavily by the author in debugging the programs. 2831 Normally its value should be the null string. 2832\medbreak} 2833It remains to discuss the C language macros that must, or may, be defined 2834by the make macro {\tt DEFINES}. One of these C macros, {\tt INT\_SIZE}, always 2835must be defined; the others are optional, or are required only in 2836certain circumstances. The C language macros are as follows: 2837\smallbreak 2838{\advance\leftskip by 0.3in\noindent 2839 {\tt INT\_SIZE}:\quad This macro is always required. Its value must 2840 be the number of bits in the C data type {\tt int}, usually 2841 16 or 32. (The programs have never been adapted to a system 2842 in which the integer size is other than 16 or 32, although 2843 it should not be difficult to do so.) 2844 {\it Note:\/}\enskip This macro only specifies the size of the 2845 C data type {\tt int}; it does {\it not\/} determine whether 2846 the programs are compiled to use 16 or 32 bit integers. 2847\smallbreak 2848 {\tt EXTRA\_LARGE}:\quad If this macro is defined, and {\tt INT\_SIZE} 2849 above is 32, the programs will be compiled using 32--bit integers; 2850 that is, points will be represented using the C data type 2851 {\tt unsigned}. Otherwise, if {\tt INT\_SIZE} is 32, the programs 2852 will be compiled using 16--bit integers (with most compilers), 2853 as points will be represented using the C data type 2854 {\tt unsigned short}. Note {\tt EXTRA\_LARGE} should not be 2855 defined when {\tt INT\_SIZE} is 16. Care must be taken, of 2856 course, not to link object files compiled with {\tt EXTRA\_LARGE} 2857 defined with those compiled without it defined, as the make file 2858 cannot protect against this error. (However, running the programs 2859 with the {\tt -v} option will reveal this error.) 2860 2861\smallbreak 2862 {\tt LONG\_EXTERNAL\_NAMES}:\quad This macro should (but need not) be defined 2863 if the linker supports long external names (up to 31 characters). 2864 If defined, its value is irrelevent. 2865\smallbreak 2866 {\tt CPU\_TIME}:\quad This macro must be defined if a special timing function 2867 is supplied, and its value must be the name of that function. 2868 If the standard C function {\tt clock()} is to be used, the 2869 macro must not be defined (not even as the null string). 2870\smallbreak 2871 {\tt NOFLOAT}:\quad This macro probably should be defined on a system 2872 lacking floating point hardware support. (If defined, its 2873 value is irrelevant.) Normally, the programs perform a 2874 small amount of floating point arithmetic in attempting to 2875 produce a good $\bfgermR$--base; with software emulation of floating 2876 point instructions, the cost of this use of floating point 2877 arithmetic probably exceeds its benefit. If the 2878 {\tt NOFLOAT} macro is defined, no floating point arithmetic 2879 is used. (In this case, it may be advantageous to add a 2880 compiler option telling the compiler not to incorporate 2881 floating--point support into the executable program. For 2882 example, under Borland C++, the {\tt -f-} option has this 2883 effect.) 2884\smallbreak 2885 {\tt TICK}:\quad This macro should be defined in two situations: (1) 2886 If a special CPU time function is supplied, {\tt TICK} 2887 should be defined to be the resolution (in clock ticks per 2888 second) of that function, and (2) if the 2889 {\tt NOFLOAT} macro is defined and if the compiler--supplied 2890 definition of the standard C macro {\tt CLK\_TCK} is a 2891 floating point constant (as occurs with Borland~C++), 2892 {\tt TICK} should be defined to be the nearest integer 2893 approximation to the value of {\tt CLK\_TCK}, e.g., 18 for 2894 Borland~C++. 2895\smallbreak 2896 {\tt HUGE}:\quad This macro must be defined for the IBM PC (unless a 2897 DOS extender is being used). It simply causes a few pointers 2898 to be declared as {\tt huge}. Only one program, the 2899 weight distribution program, uses huge pointers. 2900\medbreak} 2901In addition, the author recommends defining a symbol unique to the system 2902and compiler, e.g., {\tt SUN\_UNIX\_GCC} above. Then any code modifications 2903unique to this system and compiler can be bracketed as follows: 2904\medbreak 2905\vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other 2906\#ifdef SUN\_UNIX\_GCC 2907 /* Code modifications for Sun Unix, GNU C compiler. */ 2908\#endif 2909}} 2910\medbreak 2911Once the make file has been editted appropriately, all of the programs 2912may be compiled at once by the command 2913\smallskip 2914\hskip0.45truein\relax {\tt make all} 2915\smallskip 2916or, alternatively, individual programs may be compiled by the commands 2917\smallskip 2918\hskip0.45truein\relax \hbox to1.5truein{\tt make setstab\hfil}for 2919 {\tt setstab}, {\tt setimage}, {\tt parstab}, and {\tt parimage}, 2920\vskip1pt\noindent 2921\hskip0.45truein\relax \hbox to1.5truein{\tt make cent\hfil}for 2922 {\tt cent}, {\tt conj}, {\tt gcent}, 2923\vskip1pt\noindent 2924\hskip0.45truein\relax \hbox to1.5truein{\tt make inter\hfil}for 2925 {\tt inter}, 2926\vskip1pt\noindent 2927\hskip0.45truein\relax \hbox to1.5truein{\tt make desauto\hfil}for 2928 {\tt desauto}, {\tt desiso}, {\tt matauto}, {\tt matiso}, 2929 {\tt codeauto}, and {\tt codeiso}, 2930\vskip1pt\noindent 2931\hskip0.45truein\relax \hbox to1.5truein{\tt make cjrndper\hfil}for 2932 {\tt cjrndper} and {\tt cjper}, 2933\vskip1pt\noindent 2934\hskip0.45truein\relax \hbox to1.5truein{\tt make commut\hfil}for 2935 {\tt commut} and {\tt ncl}, 2936\vskip1pt\noindent 2937\hskip0.45truein\relax \hbox to1.5truein{\tt make compgrp\hfil}for 2938 {\tt compgrp}, 2939\vskip1pt\noindent 2940\hskip0.45truein\relax \hbox to1.5truein{\tt make fndelt\hfil}for 2941 {\tt fndelt}, 2942\vskip1pt\noindent 2943\hskip0.45truein\relax \hbox to1.5truein{\tt make generate\hfil}for 2944 {\tt generate}, 2945\vskip1pt\noindent 2946\hskip0.45truein\relax \hbox to1.5truein{\tt make orblist\hfil}for 2947 {\tt orblist}, {\tt chbase}, and {\tt ptstab}, 2948\vskip1pt\noindent 2949\hskip0.45truein\relax \hbox to1.5truein{\tt make randobj\hfil}for 2950 {\tt randobj}, 2951\vskip1pt\noindent 2952\hskip0.45truein\relax \hbox to1.5truein{\tt make wtdist\hfil}for 2953 {\tt wtdist} and {\tt cwtdist}. 2954\smallskip 2955Ideally, there should be no errors in compilation. However, with some 2956compilers (e.g., Zortech~C++), it is necessary to define {\tt const} to 2957be a null string in order to avoid compile--time errors. Typically 2958compilers will generate a number of warnings; a number of them involve 2959implicit conversion between pointers to constant and non--constant types. 2960\medbreak 2961The above commands place the executable programs in the current directory 2962(that containing the source). The final step is to move the executables 2963to the directory in which they should reside, preferably one on the current 2964path. A shell file named {\tt install} is provided for this purpose. 2965The command 2966\vskip2pt 2967\hskip0.45in\relax {\tt sh install\ }{\it bindir} 2968\vskip2pt 2969should be issued, where {\it bindir\/} is the name of the directory in 2970which the binary files should be placed, e.g., {\tt ../bin}. Note that 2971this command also copies certain shell files from the source directory 2972to the binary directory, renaming them by dropping the {\tt sh} suffix 2973in the process. 2974% 2975\bigbreak 2976\vskip15pt 2977\centerline{\sectionheaderfont REFERENCES} 2978\nobreak\medskip\nobreak 2979Leon, J.\enskip (1980a),\enskip 2980On an algorithm for finding a base and a strong generating set 2981for a group given by generating permutations,\enskip 2982{\it Math.\ Comp.} 2983{\bf 35}, 2984941--974. 2985\medbreak 2986Leon, J.\enskip(1991),\enskip 2987Permutation group algorithms based on partitions, I: Theory and algorithms,\enskip 2988{\it J. Symbolic Comp.} 2989{\bf 12}, 2990533--583. 2991\medbreak 2992Cannon, J.\enskip (1984),\enskip 2993{\it A language for group theory,}\enskip 2994Dept.\ of Pure Mathematics, University of Sydney, Australia. 2995\medbreak 2996Sims, C.~C.\enskip (1971),\enskip 2997Computation with permutation groups,\enskip 2998In (Petrick, S.~R., ed.),\enskip 2999{\it Proc.\ of the Second Symposium on Symbolic and 3000Algebraic Manipulation,}\enskip 3001New York: Assoc.\ for Computing Mach. 3002\bye 3003