Combinatorial Designs: Constructions and Analysis Douglas R. Stinson Springer Combinatorial Designs Douglas R. Stinson Combinatorial Designs Constructions and Analysis DouglasR.Stinson SchoolofComputerScience UniversityofWaterloo WaterlooONN2L3G1 Canada [email protected] LibraryofCongressCataloging-in-PublicationData Stinson,DouglasR.(DouglasRobert),1956– Combinatorialdesigns:constructionsandanalysis/DouglasR.Stinson. p.cm. Includesbibliographicalreferencesandindex. ISBN0-387-95487-2(acid-freepaper) 1.Combinatorialdesignsandconfigurations. I.Title QA166.25.S752003 511′.6—dc21 2003052964 ISBN0-387-95487-2 Printedonacid-freepaper. 2004Springer-VerlagNewYork,Inc. Allrightsreserved.Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewritten permissionofthepublisher(Springer-VerlagNewYork,Inc.,175FifthAvenue,NewYork,NY10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similarordissimilarmethodologynowknownorhereafterdevelopedisforbidden. Theuseinthispublicationoftradenames,trademarks,servicemarks,andsimilarterms,evenifthey arenotidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyare subjecttoproprietaryrights. PrintedintheUnitedStatesofAmerica. 9 8 7 6 5 4 3 2 1 SPIN10826487 Typesetting: Pages were created by the author using the Springer 2e with svmono and author macros. www.springer-ny.com Springer-Verlag NewYork Berlin Heidelberg AmemberofBertelsmannSpringerScience+BusinessMediaGmbH ToRon Mullin, whotaught medesign theory This page intentionally left blank Foreword The evolution of combinatorial design theory has been one of remarkable successes, unanticipated applications, deep connections with fundamental mathematics, and the desire to produce order from apparent chaos. While someofitscelebratedsuccessesdatefromtheeighteenthandnineteenthcen- turiesintheresearchofEuler,Kirkman,Cayley,Hamilton,Sylvester,Moore, and others, not until the twentieth century did the study of combinatorial designsemergeasanacademicsubjectinitsownright.WhenFisherandhis colleaguesdevelopedthe mathematicsof experimentaldesign inthe 1920s, combinatorial design theory was bornas a field intimately linked to its ap- plications.Beginninginthe1930s,Boseandhisschoollaidthefoundations, embeddingthenascentfieldfirmlyasamathematicaldisciplinebydevelop- ingdeepconnections withfinite geometry,number theory,finite fields,and grouptheory; however,Bose accomplished muchmore.Hisfoundationen- twined deep mathematics with its applications in experimental design and inrecreationalproblemsand anticipateditsfundamentalimportance inthe theoryoferror-correctingcodes. The rapid advances in design theory can be attributed in large degree to itsimpetus fromapplications incoding theoryand communications and itscontinueddeepinteractionswithgeometry,algebra,andnumber theory. The last fifty years have witnessed not only the emergence of certain com- binatorialdesigns(balancedincompleteblockdesigns,Hadamardmatrices, pairwise balanced designs, and orthogonal arrays, for example) as central, butalsopowerfulcombinatorialandcomputationaltechniquesfortheircon- struction.Indeedthefieldgrewsofarandsofastthatitshistoricalconnection toapplicationswasstrained. Yet, in the last twenty years, combinatorial design theory has emerged again as a field rich in currentand practicalapplications. The fundamental connections with algebra, number theory, and finite geometry remain and flourish. The applications in experimental design and coding theory have developed a breadthand depththat defybrief explanation. Yet combinato- rial design theory has matured into more than this through applications in VIII Foreword cryptography,opticalcommunications, storage systemdesign, communica- tionprotocols,algorithmdesignandanalysis,andwirelesscommunications, tomentionjustafewareas. Combinatorialdesigntheoryismatureandwidelyappliedtodaybecause ithasrespectedand advanceditsmathematicalheritagewhile finding gen- uinenewapplications.Iamhonoredtowritethisforewordfortworeasons. DougStinsonhasfortwenty-fiveyearsbeentheepitomeofaresearcherand expositor who has advanced combinatorial design theory as a marriage of mathematicsandapplications.Butmorethanthat,thebookyouholdinyour hands presents design theory as a seamless interaction of deep mathemat- icsandchallengingapplications.Byprovidinganaccessibleintroduction,it serves as an invitation to those in applications areasto appreciateand em- ploybeautifulmathematicsandconcurrentlyinvitesmathematicianstolearn fromtheapplicationsthemselves. In which directions will combinatorial design theory evolve in the next century? We cannotyetknow. We canknow, however,thatnewmathemat- icaltruthswillbefound andthatunanticipatedapplicationswillarise.Our challengeistoseekbothandtoknowthateachprofitsfromtheother. Phoenix,Arizona CharlesJ.Colbourn April,2003 Preface Overview and Goals Combinatorialdesigntheoryisoneofthemostbeautifulareasofmathemat- ics. Design theory has its roots in recreational mathematics, but it evolved inthetwentiethcenturyintoafull-fledgedmathematicaldisciplinewithdi- verseapplicationsinstatisticsandcomputerscience.Thefundamentalprob- lemsindesigntheoryaresimpleenoughthattheycanbeexplainedtonon- mathematicians, yet the solutions of those problems have involved the de- velopmentofinnovativenewcombinatorialtechniquesaswellasingenious applicationsofmethodsfromotherareasofmathematicssuchasalgebraand numbertheory.Manyclassicalproblemsremainunsolvedtothisdayaswell. This book is intended primarily to be a textbook for study at the senior undergraduateorbeginninggraduatelevel.Coursesinmathematicsorcom- puter science can be based on this book. Regardless of the audience, how- ever,itrequiresacertainamountof“mathematicalmaturity”tostudydesign theory. The main technicalprerequisitesaresome familiaritywith basic ab- stractalgebra(grouptheory,inparticular),linearalgebra(matricesandvec- tor spaces), and some number-theoretic fundamentals (e.g., modular arith- meticandcongruences). Topic Coverage and Organization The first seven chapters of this book provide a thorough treatment of the classicalcoreofthesubjectofcombinatorialdesigns.Thesechaptersconcern symmetric BIBDs, difference sets, Hadamard matrices, resolvable BIBDs, Latin squares, and pairwise balanced designs. A one-semester course can cover most of this material. For example, when I have taught courses on designs, I have based my lectures on material selected from the following chaptersandsections: