Abstract Algebra and Discrete Mathematics

By Karl Dahlke, Copyright © 2017

Chapter 0, Prolog

Mathematics, like music, has a beauty all its own. The classification of semisimple rings is as lovely as Beethoven's 7th symphony. That is my opinion of course, and in the parlance of mathematics, it isn't even well defined. So this is an unusual opening for a book that is, we hope, guided by logic and formal proofs. Still, it is my reason for writing the book, so I may as well state it up front.

Like music, math is meant to be shared - not just within an inner circle of experts, but across a wide audience. The intrepid explorer on Rush 2112 felt the same way when he discovered a guitar. He brought his treasure to the priests of the temple. "Listen to my music, and see what it can do. There's something here that's as strong as life, I know that it will reach you." My task then is to play the music well, with chords that are pleasing to a wide range of listeners. I hope I am at least partially successful in this endeavor.

Abstract algebra is the study of discrete mathematical structures that are, well, abstract. Some would say contrived, and perhaps so - but beauty is where you find it, and one can never rule out practical applications in the future. After all, prime numbers were merely a curiosity for 2,000 years, until cryptography came along; now they are at the heart of Internet security.

We'll start with the integers and the real numbers of course, but there are many more systems to consider. There are times when xy is not the same as yx, and some of the algebraic shorthand you learned in high school flies out the window. For instance, (x+y)2 is x2 + xy + yx + y2. It is no longer x2 + 2xy + y2, because xy and yx are not the same. Things happen here that you just don't see every day. And there are worlds where an element can factor into primes in many different ways. In the integers, 21 is 3 times 7, and that's the end of it, but there are factorization domains that are not this rigid. As Milo discovered in The Phantom Tollbooth, there are many lands to explore.

This book is copyright © Karl Dahlke, 2017. It may not be reproduced or retransmitted, or used in an educational setting, without permission. It can however be read for personal enjoyment, as long as it remains on this website.

It is my intention to develop a printer friendly (pdf) version of this book, which will be available for purchase through Amazon.com. If you have any questions please contact the author.

When I first envisioned this book I was tempted to jump right into groups, rings, and fields. This is a group, this is a simple group, this is a ring, this is a principal ideal domain, and so on. A bottom up approach. However, the first thing you want to see is some examples, and that requires a foundation that may be lacking. Sure, square matrices form a noncommutative ring, but what if you've never worked with matrices before? Permutations form a nonabelian group, but what if you've never worked with permutations before? Without some concrete examples all you can do is shake your head. So I am taking a different tack. The first chapter now describes an assortment of data structures such as matrices, polynomials, quaternions, and the like. Then, as we move through groups, rings, and fields, we'll have plenty of examples to draw upon.

The next few chapters present some basic theorems on sets, combinatorics, and number theory. These are concepts that we just can't do without, such as cardinality, countable sets, the binomial theorem, Euclid's gcd algorithm, and the fundamental theorem of arithmetic, which states that every number is a unique product of primes. A simple group is a bit like a prime number, and Jordan Holder decomposition is a lot like unique factorization, so we need an understanding of prime numbers before groups take center stage.

Chapter 5 extends the concept of unique factorization to other domains, such as the Gaussian integers, the Eisenstein integers, the quaternions, and the integer polynomials. (Integer polynomials are polynomials with integer coefficients.) Yes, x2+3x+5 is prime within the ring of polynomials, just as 23 is prime within the integers. And every polynomial factors into a unique product of prime polynomials. For instance, x3+1 is x+1 times x2-x+1, and nothing else. Unique factorization is at the heart of so many theorems!

Finally we are ready for groups, rings, and fields. Any one of these topics has enough material for an entire course at the undergraduate or graduate level, so you may want to step through this book and present a section here and a section there to provide a broad view, Or you may want to develop a more in-depth course that focuses specifically on one topic. Walk through my forest and pick the fruit you like along the way.

This book jumps around from topic to topic to topic, rather like a professor with ADHD. It is not, for example, an in-depth treatise on group theory. There are several reasons to cast my net far and wide.

  1. I remember being so excited about a math course at the beginning of September, but by the end of the year, and sometimes by the end of the semester, I was ready to focus on something else. This may be a deficiency of my mind, but if so, I don't think it is uncommon. There are many people who want to learn a little of this and a little of that, switching from topic to topic. Thus this book is more like Sesame Street than Mr. Rogers.

  2. Branches of mathematics are not really independent of one another. Number theory, linear algebra, fields, groups, rings, modules; they all draw upon one another. You need to know a little about all of these before diving very deeply into any one of them. Thus I believe a breadth-first approach is appropriate, especially if you are not sure which area of math piques your interest.

  3. A wide array of topics can be presented using the same notation, format, and style. (This is also a goal of wikipedia.) In every chapter, Z is the integers, Q is the rationals, F[x] is the polynomials in x with coefficients in F, iff means if and only if, and the word "suppose" begins a proof by contradiction. "Suppose p is not prime … then such and so goes wrong."

  4. In an electronic format, chapters can link back to relevant sections in previous chapters to maintain a context or remind you of a theorem or definition that is essential for the current topic. Click on a link if you need to review that theorem or its proof. Easy navigation is another goal of wikipedia, though they sometimes have so many hyperlinks it's hard to read the text.

Though not strictly necessary, it is helpful if you are familiar with introductory calculus on real and complex variables. Yes, this book addresses discrete mathematics, but it is surprising how discrete and continuous math can support each other. In fact an entire branch of mathematics, analytic number theory, answers questions in number theory using analytic functions on the complex plane. Closer to home, chapter 1 will describe formal derivatives, the differentiation of polynomials for algebraic purposes. These polynomials might be restricted to the inntegers mod 7, and yet the derivative of p(x) still makes sense. Thus a background in calculus is helpful from time to time, but not vital. If you have never seen a derivative or an integral before, you will still be able to follow 95% of this book.

This book includes blocks of pseudocode to describe simple algorithms, blocks of C code to implement simple programs, and blocks of pbc code to verify certain algebraic relationships. pbc is a program I wrote myself, a variation on bc that includes polynomials, modular mathematics, and a few number theory functions. The program is open source; you can get it from eklhad.net/pbc.zip. Type make to build the program. It requires the gmp library and development headers.

At present this is an E-book, with one chapter per html file. Each chapter is further divided into sections which are listed at the top of the file in a mini table of contents. Click on any of these links to jump straight to that section. Each section begins with a centered heading, and a link Start of chapter that takes you back up to the beginning of the current chapter, and another link Contents that takes you off the page and back to the table of contents. Other links within the text will reference specific theorems in previous chapters, in case you need to review those theorems to proceed with the material. Forward references are rare, but they do happen from time to time. Thus it is best to read this book in order, since each chapter builds on the material that has come before.

If you are curious about any of the following questions, then this is the book for you. These are in no particular order.

Go to Contents Next