Applied Abstract Algebra

There is at present a growing body of opinion that in the decades ahead discrete mathematics (that is, "noncontinuous mathematics"), and therefore parts of applicable modern algebra, will be of increasing importance. Cer tainly, one reason for this opinion is the rapid development of computer science, and the use of discrete mathematics as one of its major tools. The purpose of this book is to convey to graduate students or to final-year undergraduate students the fact that the abstract algebra encountered pre viously in a first algebra course can be used in many areas of applied mathematics. It is often the case that students who have studied mathematics go into postgraduate work without any knowledge of the applicability of the structures they have studied in an algebra course. In recent years there have emerged courses and texts on discrete mathe matics and applied algebra. The present text is meant to add to what is available, by focusing on three subject areas. The contents of this book can be described as dealing with the following major themes: Applications of Boolean algebras (Chapters 1 and 2). Applications of finite fields (Chapters 3 to 5). Applications of semigroups (Chapters 6 and 7).

1 Lattices.- § 1. Properties of Lattices.- A. Lattice Definitions.- B. Modular and Distributive Lattices.- §2. Boolean Algebras.- A. Basic Properties.- B. Boolean Polynomials, Ideals.- §3. Minimal Forms of Boolean Polynomials.- Notes.- 2 Applications of Lattices.- §1. Switching Circuits.- A. Basic Definitions.- B. Applications of Switching Circuits.- §2. Propositional Logic.- §3. Further Applications.- Notes.- 3 Finite Fields and Polynomials.- §1. Rings and Fields.- A. Rings, Ideals, Homomorphisms.- B. Polynomials.- C. Fields.- D. Algebraic Extensions.- §2. Finite Fields.- §3. Irreducible Polynomials over Finite Fields.- §4. Factorization of Polynomials over Finite Fields.- §5. The Nullspace of a Matrix (Appendix to §4).- Notes.- 4 Coding Theory.- §1. Linear Codes.- §2. Cyclic Codes.- §3. Special Cyclic Codes.- Notes.- 5 Further Applications of Fields and Groups.- §1. Combinatorial Applications.- A. Hadamard Matrices.- B. Balanced Incomplete Block Designs.- C. Steiner Systems, Difference Sets and Latin Squares.- §2. Algebraic Cryptography.- A. Single Key (Symmetric) Cryptosystems.- B. Public-Key Cryptosystems.- §3. Linear Recurring Sequences.- §4. Fast Adding.- §5. Polya s Theory of Enumeration.- Notes.- 6 Automata.- § 1. Semiautomata and Automata.- §2. Description of Automata; Examples.- §3. Semigroups.- A. Fundamental Concepts.- B. Subsemigroups, Homomorphisms.- C. Free Semigroups.- §4. Input Sequences.- §5. The Monoid of a (Semi-) Automaton and the (Semi-) Automaton of a Monoid.- §6. Composition and Decomposition.- A. Elementary Constructions of Automata.- B. Cascades.- §7. Minimal Automata.- Notes.- 7 Further Applications of Semigroups.- §1. Formal Languages.- A. Approach via Grammar.- B. Approach via Automata and Semigroups.- C. Connections Between the Different Approaches.- §2. Semigroups in Biology.- §3. Semigroups in Sociology.- A. Kinship Systems.- B. Social Networks 400 Notes.- 8 Solutions to the Exercises.- 1.- 2.- 3.- 4.- 5.- 6.- 7.- A. Some Fundamental Concepts.- B. Computer Programs.- Author Index.