MODERN ALGEBRA WITH APPLICATIONS PURE AND APPLIED MATHEMATICS A Wiley-Interscience Series of Texts, Monograph, and Tracts Founded by RICHARD COURANT Editors: MYRON B. ALLEN III, DAVID A. COX, PETER LAX Editors Emeriti: PETER HILTON, HARRY HOCHSTADT, JOHN TOLAND A complete list of the titles in this series appears at the end of this volume. MODERN ALGEBRA WITH APPLICATIONS Second Edition WILLIAM J. GILBERT University of Waterloo Department ofPure Mathematics Waterloo, Ontario, Canada W. KEITH NICHOLSON University of Calgary Department ofMathematics and Statistics Calgary, Alberta, Canada A JOHN WILEY & SONS, INC., PUBLICATION Cover:StillimagefromtheappletKaleidoHedron,Copyright2000byGregEgan,fromhis websitehttp://www.netspace.net.au/∼gregegan/. Thepatternhasthesymmetryoftheicosahedral group. Copyright2004byJohnWiley&Sons,Inc.Allrightsreserved. PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey. PublishedsimultaneouslyinCanada. Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinany formorbyanymeans,electronic,mechanical,photocopying,recording,scanning,orotherwise, exceptaspermittedunderSection107or108ofthe1976UnitedStatesCopyrightAct,without eitherthepriorwrittenpermissionofthePublisher,orauthorizationthroughpaymentofthe appropriateper-copyfeetotheCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers, MA01923,978-750-8400,fax978-750-4470,oronthewebatwww.copyright.com.Requeststo thePublisherforpermissionshouldbeaddressedtothePermissionsDepartment,JohnWiley& Sons,Inc.,111RiverStreet,Hoboken,NJ07030,(201)748-6011,fax(201)748-6008,e-mail: [email protected]. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbest effortsinpreparingthisbook,theymakenorepresentationsorwarrantieswithrespecttothe accuracyorcompletenessofthecontentsofthisbookandspecificallydisclaimanyimplied warrantiesofmerchantabilityorfitnessforaparticularpurpose.Nowarrantymaybecreatedor extendedbysalesrepresentativesorwrittensalesmaterials.Theadviceandstrategiescontained hereinmaynotbesuitableforyoursituation.Youshouldconsultwithaprofessionalwhere appropriate.Neitherthepublishernorauthorshallbeliableforanylossofprofitoranyother commercialdamages,includingbutnotlimitedtospecial,incidental,consequential,orother damages. ForgeneralinformationonourotherproductsandservicespleasecontactourCustomerCare DepartmentwithintheU.S.at877-762-2974,outsidetheU.S.at317-572-3993or fax317-572-4002. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsin print,however,maynotbeavailableinelectronicformat. LibraryofCongressCataloging-in-PublicationData: Gilbert,WilliamJ.,1941– Modernalgebrawithapplications/WilliamJ.Gilbert,W.KeithNicholson.—2nded. p.cm.—(Pureandappliedmathematics) Includesbibliographicalreferencesandindex. ISBN0-471-41451-4(cloth) 1.Algebra,Abstract.I.Nicholson,W.Keith.II.Title.III.Pureandapplied mathematics(JohnWiley&Sons:Unnumbered) QA162.G532003 512—dc21 2003049734 PrintedintheUnitedStatesofAmerica. 10987654321 CONTENTS Preface to the First Edition ix Preface to the Second Edition xiii List of Symbols xv 1 Introduction 1 Classical Algebra, 1 Modern Algebra, 2 Binary Operations, 2 Algebraic Structures, 4 Extending Number Systems, 5 2 Boolean Algebras 7 Algebra of Sets, 7 Number of Elements in a Set, 11 Boolean Algebras, 13 Propositional Logic, 16 Switching Circuits, 19 Divisors, 21 Posets and Lattices, 23 Normal Forms and Simplification of Circuits, 26 Transistor Gates, 36 Representation Theorem, 39 Exercises, 41 3 Groups 47 Groups and Symmetries, 48 Subgroups, 54 v vi CONTENTS Cyclic Groups and Dihedral Groups, 56 Morphisms, 60 Permutation Groups, 63 Even and Odd Permutations, 67 Cayley’s Representation Theorem, 71 Exercises, 71 4 Quotient Groups 76 Equivalence Relations, 76 Cosets and Lagrange’s Theorem, 78 Normal Subgroups and Quotient Groups, 82 Morphism Theorem, 86 Direct Products, 91 Groups of Low Order, 94 Action of a Group on a Set, 96 Exercises, 99 5 Symmetry Groups in Three Dimensions 104 Translations and the Euclidean Group, 104 Matrix Groups, 107 Finite Groups in Two Dimensions, 109 Proper Rotations of Regular Solids, 111 Finite Rotation Groups in Three Dimensions, 116 Crystallographic Groups, 120 Exercises, 121 6 Po´lya–Burnside Method of Enumeration 124 Burnside’s Theorem, 124 Necklace Problems, 126 Coloring Polyhedra, 128 Counting Switching Circuits, 130 Exercises, 134 7 Monoids and Machines 137 Monoids and Semigroups, 137 Finite-State Machines, 142 Quotient Monoids and the Monoid of a Machine, 144 Exercises, 149 8 Rings and Fields 155 Rings, 155 Integral Domains and Fields, 159 Subrings and Morphisms of Rings, 161 CONTENTS vii New Rings from Old, 164 Field of Fractions, 170 Convolution Fractions, 172 Exercises, 176 9 Polynomial and Euclidean Rings 180 Euclidean Rings, 180 Euclidean Algorithm, 184 Unique Factorization, 187 Factoring Real and Complex Polynomials, 190 Factoring Rational and Integral Polynomials, 192 Factoring Polynomials over Finite Fields, 195 Linear Congruences and the Chinese Remainder Theorem, 197 Exercises, 201 10 Quotient Rings 204 Ideals and Quotient Rings, 204 Computations in Quotient Rings, 207 Morphism Theorem, 209 Quotient Polynomial Rings That Are Fields, 210 Exercises, 214 11 Field Extensions 218 Field Extensions, 218 Algebraic Numbers, 221 Galois Fields, 225 Primitive Elements, 228 Exercises, 232 12 Latin Squares 236 Latin Squares, 236 Orthogonal Latin Squares, 238 Finite Geometries, 242 Magic Squares, 245 Exercises, 249 13 Geometrical Constructions 251 Constructible Numbers, 251 Duplicating a Cube, 256 Trisecting an Angle, 257 Squaring the Circle, 259 Constructing Regular Polygons, 259 viii CONTENTS Nonconstructible Number of Degree 4, 260 Exercises, 262 14 Error-Correcting Codes 264 The Coding Problem, 266 Simple Codes, 267 Polynomial Representation, 270 Matrix Representation, 276 Error Correcting and Decoding, 280 BCH Codes, 284 Exercises, 288 Appendix 1: Proofs 293 Appendix 2: Integers 296 Bibliography and References 306 Answers to Odd-Numbered Exercises 309 Index 323 PREFACE TO THE FIRST EDITION Until recently the applications of modern algebra were mainly confined to other branches of mathematics. However, the importance of modern algebra and dis- cretestructurestomanyareasofscienceandtechnologyisnowgrowingrapidly. It is being used extensively in computing science, physics, chemistry, and data communication as well as in new areas of mathematics such as combinatorics. We believe that the fundamentals of these applications can now be taught at the junior level.This bookthereforeconstitutes aone-yearcourseinmodernalgebra for those students who have been exposed to some linear algebra. It contains the essentials of a first course in modern algebra together with a wide variety of applications. Modern algebra is usually taught from the point of view of its intrinsic inter- est, and students are told that applications will appear in later courses. Many students loseinterestwhentheydonotseethe relevanceofthe subjectandoften becomeskepticaloftheperennialexplanationthatthematerialwillbeusedlater. However, we believe that by providing interesting and nontrivial applications as we proceed, the student will better appreciate and understand the subject. We cover all the group, ring, and field theory that is usually contained in a standard modern algebra course; the exact sections containing this material are indicatedinthetableofcontents.WestopshortoftheSylowtheoremsandGalois theory. These topics could only be touched on in a first course, and we feel that more time should be spent on them if they are to be appreciated. In Chapter 2 we discuss boolean algebras and their application to switching circuits. These provide a good example of algebraic structures whose elements arenonnumerical.However,manyinstructorsmayprefertopostponeoromitthis chapter and start with the group theory in Chapters 3 and 4. Groups are viewed asdescribingsymmetriesinnatureandinmathematics.Inkeepingwiththisview, therotationgroupsoftheregularsolidsareinvestigatedinChapter 5.Thismate- rialprovidesagoodstartingpointforstudentsinterestedinapplyinggrouptheory to physics and chemistry. Chapter 6 introduces the Po´lya–Burnside method of enumerating equivalence classesof sets of symmetries and provides a very prac- tical application of group theory to combinatorics. Monoids are becoming more ix x PREFACETOTHEFIRSTEDITION important algebraic structures today; these are discussed in Chapter 7 and are applied to finite-state machines. TheringandfieldtheoryiscoveredinChapters 8–11.Thistheoryismotivated bythedesiretoextendthefamiliarnumbersystemstoobtaintheGaloisfieldsand to discover the structure of various subfields of the real and complex numbers. GroupsareusedinChapter 12toconstructlatinsquares,whereasGaloisfieldsare usedtoconstructorthogonallatinsquares.Thesecanbeusedtodesignstatistical experiments. We also indicate the close relationship between orthogonal latin squares and finite geometries. In Chapter 13 field extensions are used to show that some famous geometrical constructions, such as the trisection of an angle andthesquaringofthecircle,areimpossibletoperformusingonlyastraightedge and compass. Finally, Chapter 14 gives an introduction to coding theory using polynomial and matrix techniques. Wedonotgiveexhaustivetreatmentsofanyoftheapplications.Weonlygoso farastogivetheflavorwithoutbecomingtooinvolvedintechnicalcomplications. 1 Introduction 2 3 8 Boolean Groups Rings Algebras and Fields 4 7 9 Quotient Monoids Polynomial Groups and and Euclidean Machines Rings 6 5 10 Pólya–Burnside Symmetry Quotient Method of Groups in Three Rings Enumeration Dimensions 11 Field Extensions 12 13 Latin Geometrical Squares Constructions 14 Error-Correcting Codes FigureP.1. Structureofthechapters.