%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %A design.tex DESIGN documentation Leonard Soicher % % % \def\GRAPE{\sf GRAPE} \def\DESIGN{\sf DESIGN} \def\GAPDoc{\sf GAPDoc} \def\nauty{\it nauty} \def\Aut{{\rm Aut}\,} \Chapter{Design} This manual describes the {\DESIGN}~1.3 package for {\GAP} (version at least 4.4). The {\DESIGN} package is for constructing, classifying, partitioning and studying block designs. All {\DESIGN} functions are written entirely in the {\GAP} language. However, {\DESIGN} requires the {\GRAPE} package \cite{Grape} (version at least 4.2) to be installed, and makes use of certain {\GRAPE} functions, some of which make use of B.~D.~McKay{\pif}s {\nauty} package \cite{Nauty}. These {\GRAPE} functions can only be used on a fully installed version of {\GRAPE} in a UNIX environment. {\DESIGN} also requires the {\GAPDoc} package \cite{GAPDoc} (version at least 0.99), if you want to read lists of designs in the \URL{http://designtheory.org} external representation format (see \cite{Extrep}). The {\DESIGN} package is Copyright {\copyright} Leonard H. Soicher 2003--2006. {\DESIGN} is part of a wider project, which received EPSRC funding under grant GR/R29659/01, to provide a web-based resource for design theory; see \URL{http://designtheory.org} and \cite{Dotw}. {\DESIGN} is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. For details, see \URL{http://www.gnu.org/licenses/gpl.html} If you use {\DESIGN} to solve a problem then please send a short email about it to \Mailto{L.H.Soicher@qmul.ac.uk}, and reference the {\DESIGN} package as follows: L.~H. Soicher, The {DESIGN} package for {GAP}, Version~1.3, 2006, \URL{http://designtheory.org/software/gap_design/}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Installing the DESIGN Package} The {\DESIGN} package has complete functionality only in a UNIX environment in which the {\GRAPE} and {\GAPDoc} packages are fully installed. To install {\DESIGN}~1.3 (on a UNIX system, after installing {\GAP}, {\GRAPE} and {\GAPDoc}), first obtain the {\DESIGN} archive file `design1r3.tar.gz', available from \URL{http://designtheory.org/software/gap_design/} and then copy this archive file into the `pkg' directory of the {\GAP} root directory. Actually, it is possible to have several {\GAP} root directories, and so it is easy to install {\DESIGN} locally even if you have no permission to add files to the main {\GAP} installation (see the {\GAP} reference manual section "ref:GAP Root Directory"). Now go to the appropriate `pkg' directory containing `design1r3.tar.gz', and then run \begintt gunzip design1r3.tar.gz tar -xf design1r3.tar \endtt That's all there is to do. Both dvi and pdf versions of the {\DESIGN} manual are available (as `manual.dvi' and `manual.pdf' respectively) in the `doc' directory of the home directory of {\DESIGN}. If you install {\DESIGN}, then please tell \Mailto{L.H.Soicher@qmul.ac.uk}, where you should also send any comments or bug reports. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Loading DESIGN} Before using {\DESIGN} you must load the package within {\GAP} by calling the statement \begintt gap> LoadPackage("design"); true \endtt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The structure of a block design in DESIGN} A *block design* is a pair $(X,B)$, where $X$ is a non-empty finite set whose elements are called *points*, and $B$ is a non-empty finite multiset whose elements are called *blocks*, such that each block is a non-empty finite multiset of points. {\DESIGN} deals with arbitrary block designs. However, at present, some {\DESIGN} functions only work for *binary* block designs (i.e. those with no repeated element in any block of the design), but these functions will check if an input block design is binary. In {\DESIGN}, a block design <D> is stored as a record, with mandatory components `isBlockDesign', `v', and `blocks'. The points of a block design <D> are always 1,2,...,`<D>.v', but they may also be given *names* in the optional component `pointNames', with `<D>.pointNames[<i>]' the name of point <i>. The `blocks' component must be a sorted list of the blocks of <D> (including any repeats), with each block being a sorted list of points (including any repeats). A block design record may also have some optional components which store information about the design. At present these optional components include `isSimple', `isBinary', `isConnected', `r', `blockSizes', `blockNumbers', `resolutions', `autGroup', `autSubgroup', `tSubsetStructure', `allTDesignLambdas', and `pointNames'. A non-expert user should only use functions in the {\DESIGN} package to create block design records and their components. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Example of the use of DESIGN} To give you an idea of the capabilities of this package, we now give an extended example of an application of the {\DESIGN} package, in which a nearly resolvable non-simple 2-(21,4,3) design is constructed (for Donald Preece) via a pairwise-balanced design. All the {\DESIGN} functions used here are described in this manual. The program first discovers the unique (up to isomorphism) pairwise-balanced 2-(21,$\{4,5\}$,1) design $D$ invariant under $H=\langle (1,2,\ldots,20)\rangle$, and then applies the $\*$-construction of \cite{McSo} to this design $D$ to obtain a non-simple 2-(21,4,3) design $Dstar$ with automorphism group of order 80. The program then classifies the near-resolutions of $Dstar$ invariant under the subgroup of order 5 of $H$, and finds exactly two such (up to the action of $\Aut(Dstar)$). Finally, $Dstar$ is printed. \beginexample gap> H:=CyclicGroup(IsPermGroup,20); Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) ]) gap> D:=BlockDesigns(rec(v:=21,blockSizes:=[4,5], > tSubsetStructure:=rec(t:=2,lambdas:=[1]), > requiredAutSubgroup:=H ));; gap> Length(D); 1 gap> D:=D[1];; gap> BlockSizes(D); [ 4, 5 ] gap> BlockNumbers(D); [ 20, 9 ] gap> Size(AutGroupBlockDesign(D)); 80 gap> Dstar:=TDesignFromTBD(D,2,4);; gap> AllTDesignLambdas(Dstar); [ 105, 20, 3 ] gap> IsSimpleBlockDesign(Dstar); false gap> Size(AutGroupBlockDesign(Dstar)); 80 gap> near_resolutions:=PartitionsIntoBlockDesigns(rec( > blockDesign:=Dstar, > v:=21,blockSizes:=[4], > tSubsetStructure:=rec(t:=0,lambdas:=[5]), > blockIntersectionNumbers:=[[ [0] ]], > requiredAutSubgroup:=SylowSubgroup(H,5) ));; gap> Length(near_resolutions); 2 gap> List(near_resolutions,x->Size(x.autGroup)); [ 5, 20 ] gap> Print(Dstar,"\n"); rec( isBlockDesign := true, v := 21, blocks := [ [ 1, 2, 4, 15 ], [ 1, 2, 4, 15 ], [ 1, 2, 4, 15 ], [ 1, 3, 14, 20 ], [ 1, 3, 14, 20 ], [ 1, 3, 14, 20 ], [ 1, 5, 9, 13 ], [ 1, 5, 9, 17 ], [ 1, 5, 13, 17 ], [ 1, 6, 11, 16 ], [ 1, 6, 11, 21 ], [ 1, 6, 16, 21 ], [ 1, 7, 8, 10 ], [ 1, 7, 8, 10 ], [ 1, 7, 8, 10 ], [ 1, 9, 13, 17 ], [ 1, 11, 16, 21 ], [ 1, 12, 18, 19 ], [ 1, 12, 18, 19 ], [ 1, 12, 18, 19 ], [ 2, 3, 5, 16 ], [ 2, 3, 5, 16 ], [ 2, 3, 5, 16 ], [ 2, 6, 10, 14 ], [ 2, 6, 10, 18 ], [ 2, 6, 14, 18 ], [ 2, 7, 12, 17 ], [ 2, 7, 12, 21 ], [ 2, 7, 17, 21 ], [ 2, 8, 9, 11 ], [ 2, 8, 9, 11 ], [ 2, 8, 9, 11 ], [ 2, 10, 14, 18 ], [ 2, 12, 17, 21 ], [ 2, 13, 19, 20 ], [ 2, 13, 19, 20 ], [ 2, 13, 19, 20 ], [ 3, 4, 6, 17 ], [ 3, 4, 6, 17 ], [ 3, 4, 6, 17 ], [ 3, 7, 11, 15 ], [ 3, 7, 11, 19 ], [ 3, 7, 15, 19 ], [ 3, 8, 13, 18 ], [ 3, 8, 13, 21 ], [ 3, 8, 18, 21 ], [ 3, 9, 10, 12 ], [ 3, 9, 10, 12 ], [ 3, 9, 10, 12 ], [ 3, 11, 15, 19 ], [ 3, 13, 18, 21 ], [ 4, 5, 7, 18 ], [ 4, 5, 7, 18 ], [ 4, 5, 7, 18 ], [ 4, 8, 12, 16 ], [ 4, 8, 12, 20 ], [ 4, 8, 16, 20 ], [ 4, 9, 14, 19 ], [ 4, 9, 14, 21 ], [ 4, 9, 19, 21 ], [ 4, 10, 11, 13 ], [ 4, 10, 11, 13 ], [ 4, 10, 11, 13 ], [ 4, 12, 16, 20 ], [ 4, 14, 19, 21 ], [ 5, 6, 8, 19 ], [ 5, 6, 8, 19 ], [ 5, 6, 8, 19 ], [ 5, 9, 13, 17 ], [ 5, 10, 15, 20 ], [ 5, 10, 15, 21 ], [ 5, 10, 20, 21 ], [ 5, 11, 12, 14 ], [ 5, 11, 12, 14 ], [ 5, 11, 12, 14 ], [ 5, 15, 20, 21 ], [ 6, 7, 9, 20 ], [ 6, 7, 9, 20 ], [ 6, 7, 9, 20 ], [ 6, 10, 14, 18 ], [ 6, 11, 16, 21 ], [ 6, 12, 13, 15 ], [ 6, 12, 13, 15 ], [ 6, 12, 13, 15 ], [ 7, 11, 15, 19 ], [ 7, 12, 17, 21 ], [ 7, 13, 14, 16 ], [ 7, 13, 14, 16 ], [ 7, 13, 14, 16 ], [ 8, 12, 16, 20 ], [ 8, 13, 18, 21 ], [ 8, 14, 15, 17 ], [ 8, 14, 15, 17 ], [ 8, 14, 15, 17 ], [ 9, 14, 19, 21 ], [ 9, 15, 16, 18 ], [ 9, 15, 16, 18 ], [ 9, 15, 16, 18 ], [ 10, 15, 20, 21 ], [ 10, 16, 17, 19 ], [ 10, 16, 17, 19 ], [ 10, 16, 17, 19 ], [ 11, 17, 18, 20 ], [ 11, 17, 18, 20 ], [ 11, 17, 18, 20 ] ], autGroup := Group( [ ( 2,14,10,18)( 3, 7,19,15)( 4,20, 8,12)( 5,13,17, 9), ( 1,17, 5, 9)( 2,10,14, 6)( 4,16,12,20)( 7,15,19,11), ( 1,18,19,12)( 2,11, 8, 9)( 3, 4,17, 6)( 5,10,15,20)( 7,16,13,14) ] ), blockSizes := [ 4 ], isBinary := true, allTDesignLambdas := [ 105, 20, 3 ], isSimple := false ) \endexample