Preface
This book is based on courses taught by the authors over many years at universities in Dortmund, Hamburg, Munich, and Stuttgart. Two textbooks emerged from the German lecture notes, Elemente der diskreten Mathematik [28] and Diskrete algebraische Methoden [27].While the first book has a strong emphasis on combinatorial topics, the second book focuses on algebraic ideas. This English edition is a revised and extended version of the second book.
Essentially, no knowledge beyond high school mathematics is required for reading this book. However, the density of the presentation suggests a certain amount of mathematical maturity, as, for example, required from students in computer science or mathematics studying for a master’s degree. Every mathematically inclined reader should be able to follow the topics, but the effort might vary.
Contents. Discrete algebraic methods are a future-oriented topic and its fundamentals are becoming increasingly significant. The selection of the material is also influenced by the authors’ personal affinities. We begin with a general chapter on algebraic structures, providing the foundation for the rest of the book. Each of the subsequent chapters can be read independently, but there are various connections. For example, the chapter on elliptic curves is motivated by applications in cryptography. Algebraic cryptography is actually a guiding theme, given that cryptography is ubiquitous in modern society. Our focus is on asymmetric cryptographic methods. They are mathematically more interesting and challenging than symmetric procedures, which are designed to optimize performance. We also present Shamir’s attack on the Merkle–Hellman scheme. Due to this attack, the Merkle–Hellman scheme no longer has any practical use. However, the Merkle–Hellman method serves as a lesson on how skeptical we should be regarding unproven security claims. Also, the general question, whether it makes sense to build cryptosystems on NP-hard problems, remains topical. The purely speculative answer we tend to give to this question is “no,” but the margin here is too narrow to include our justification.
The chapter on number theoretic algorithms is central. For example, large random prime numbers are needed in cryptosystems such as Rivest–Shamir–Adleman (RSA). So the method relies on the ability to efficiently generate primes. To date, RSA is the most popular asymmetric cryptographic method. It is named after Rivest, Shamir, and Adleman, who were the first to publish the algorithm in 1977 (although it seems that the scheme was known to British intelligence much earlier). We also study alternatives for RSA, such as the Diffie–Hellman procedure for secure key exchange. If we rely on this procedure, it might be reassuring to understand why known algorithms are unable to compute discrete logarithms on moderate input sizes. For calculations with large numbers, the analysis is often based on the fact that numbers can be multiplied in nearly linear time. We discuss Schönhage and Strassen’s algorithm for integer multiplication, which achieves this time bound.
In the chapter on the recognition of primes, we present the deterministic polynomial time test by Agrawal, Kayal, and Saxena. It is called the AKS test after its inventors. Even though it was only discovered in 2002, it is the archetypical application of discrete algebraic methods. Our presentation of the AKS test follows the exposition of the original article to a large extent. Nevertheless,we incorporate some simplifications compared to the original paper. In particular, we do not use cyclotomic polynomials. All we need is the basic fact that splitting fields exist. This refurbishment makes it possible to discuss the AKS test in a high school study group with a committed teacher and motivated students. We strongly encourage school teachers to undertake such a project.
The chapter on elliptic curves is mainly dedicated to number theoretic and cryptographic applications. Cryptography based on elliptic curves is well established in practice; and this area will be of growing importance in the near future. We provide all the necessary mathematics for this purpose. One big problem for the understanding of elliptic curves is that a great portion of users have no idea why computations should lead to correct results. This applies to a lesser extent to RSA-based methods, because computing modulo n is easily comprehensible. In comparison, elliptic curves constitute inherently complex mathematical objects. A user might easily be able to implement the needed operations on elliptic curves, needing only basic arithmetic operations. The formalism thus is available in the form of recipes, but usually the recipes (and also the books containing them) do not reveal why they are working correctly. This leads to justified skepticism towards elliptic curves. We counter this skepticism by not avoiding the difficult part. The proof of the group structure is presented in full detail and is based entirely upon the chapter on algebraic structures. In particular, we do not expect the reader to have previous knowledge from algebraic geometry or from complex analysis.
Combinatorics on words studies structural properties of sequences, such as repetitions. Motivated by Higman’s lemma on subsequences, we give a concise introduction to Ramsey theory and well-quasi-orderings. The chapter culminates in a proof of Kruskal’s tree theorem.
The chapter on automata leads us to an area of theoretical computer science, in which the theory of semigroups plays a central role. We deal with regular languages in a general context, which is crucial for understanding deterministic and nondeterministic automata. Two key results in this area are the characterization of star-free languages by Schützenberger and the decomposition theorem of Krohn and Rhodes. For both results, we present new and simplified proofs. We also give a recent interpretation of Green’s relations in terms of local divisors. The above-mentioned results concern languages over finite words. However, the need for formal methods in hardware and software verification makes it necessary to analyze systems that do not intend to terminate, leading to the study of infinite words and the connection between logic and automata on infinite objects. Examples of such systems are operating systems, embedded systems in cars, planes, etc. Here, we deal with Büchi automata. In the 1960s, Büchi showed that monadic second-order logic over infinite words is decidable; we give a detailed proof of this result. Two more applications of automata theory follow: decidability of Presburger arithmetic and a simple automata theoretic proof that there is an effective description for the solution set of linear Diophantine systems.
The final chapter is devoted to discrete infinite groups. The chosen topics belong to the algorithmic branch of combinatorial group theory, as developed in the classic book by Lyndon and Schupp. We chose to explain standard constructions using confluent term rewriting systems. This leads to mathematically precise statements and in many cases directly to corresponding algorithms. In the section on free groups, the influence of Serre and Stallings on modern group theory becomes obvious. A particularly nice application of Stallings’ ideas is the geometric proof for the fact that the automorphism group of finitely generated free groups is generated by (finitely many) Whitehead automorphisms.
Authors. Volker Diekert holds the chair of Theoretical Computer Science at the University of Stuttgart. He studied in Hamburg and Montpellier, completing a Diplôme des Études Supérieures with Alexander Grothendieck. He graduated in mathematics in Hamburg and regularly attended seminars offered by Ernst Witt. He earned his PhD with Jürgen Neukirch in Regensburg. These late mathematicians and truly impressive personalities have had an enduring influence in his life.
Manfred Kufleitner studied computer science with a minor in mathematics, and then earned his PhD in computer science in Stuttgart under the supervision of the first author. Shortly after, he spent one year in Bordeaux. He has been a guest professor at Technische Universität München and an acting professor at the University of Hamburg.
Gerhard Rosenberger comes with the greatest life experience among the authors. He has a strong background in teaching mathematics and much experience in writing textbooks. His research work has been enriched by extended stays in Russia and in the United States. In his scientific collaboration, he has co-authors from more than 25 different countries. Currently, he teaches at the University of Hamburg.
Ulrich Hertrampf started his career in pure mathematics. After his diploma thesis in the area of group representations, he earned his PhD in the area of practical computer science, but returned to theoretical research when he completed his habilitation in the structural complexity theory group of Klaus Wagner in Würzburg.
Cover. The title of the book is Discrete Algebraic Methods, or DAM for short; and the book’s cover page shows the Hoover Dam. It is a concrete construction to gather a huge pool of water. The purpose is not to block it, but to provide a continuous stream of water and hydroelectric power. Having this interpretation in mind, we are glad that we are permitted to reproduce the picture by John Phelan.
Miscellaneous. We believe that combining exercises with the study of advanced material deepens the understanding of the subject matter. Exercises can be found at the end of each chapter and complete solutions are given in the appendix. The exercises are of variable difficulty; their order corresponds to the presentation of the topics within a chapter. All chapters end with short summaries to reinforce learning.
We prefer succinct explanations over verbose ones, thus leaving free space for the reader’s own considerations. Throughout, we give complete proofs. Most chapters end with topics which lie beyond standard contents.
For aesthetic reasons, we have intentionally omitted punctuation marks at the end of displayed formulas. Our style of writing is motivated by gender-free mathematics. The use of gender is purely grammatical. Thus, if we speak of “she” or “he” we intend no preference to women or men. If “Alice” and “Bob” appear occasionally, we mean “Person A” and “Person B.” Ifmathematicians are mentioned by name, we include biographical details, whenever it appears appropriate and if publicly available. In some cases, we obtained permission to mention years of birth. In other words, these details are partly missing.
Acknowledgments
A successful realization of this book would have been impossible without support from the Theoretical Computer Science department at the University of Stuttgart. The entire team was heavily involved in the preparation of the manuscript. Their dedicated participation in proofreading and their help in writing solutions to the exercises are gratefully acknowledged. In particular, the following former and present members made numerous contributions to the completion of the German and English editions of the book: Lukas Fleischer, Jonathan Kausch, Jürn Laun, Alexander Lauser, Jan Philipp Wächter, Tobias Walter, and Armin Weiß. Helpful technical support also came from Heike Photien, Horst Prote, and Martin Seybold as well as from Steven Kerns at the Language Center of the University of Stuttgart. During fall 2015, visiting researchers at the University of Stuttgart read parts of the book and provided helpful comments. This includes Jorge Almeida (Universidade do Porto, Porto), Murray Elder (The University of Newcastle, Australia), Théo Pierron (LaBRI, Bordeaux), M. Hossein Shahzamanian (Universidade do Porto, Porto), and Marc Zeitoun (LaBRI, Bordeaux). Those mathematical, stylistic, and orthographic errors that undoubtedly remain shall be charged to the authors. Last but not least, we thank DeGruyter for publishing our book.
Stuttgart and Hamburg, January 2016
VD, MK, GR, UH