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.
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.
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.
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."
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
that takes you back up to the beginning of the current chapter,
and another link
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.
What are even and odd permutations?
How do I know that n factors into primes in only one way?
How can I demonstrate (computationally) that p is prime, even if p is very large?
How does a complex integer like 27+39i factor into primes? I know that 17 is no longer prime, being 4+i times 4-i. Is factorization still unique in complex numbers?
How does a polynomial factor into primes? I know that x2-1 is x+1 times x-1.
If p is prime, how can I quickly factor a polynomial mod p, even if p is large, and the polynomial has thousands of terms?
How does a quaternion factor into primes? I know that 7 is 2+i+j+k times 2-i-j-k. Does prime even have any meaning in a world where multiplication is not commutative?
If p is prime, there is only one solution to a2+b2 = p; how can I find it, even if p is large? Example: 62 + 312 = 997.
How are prime numbers used in cryptography and Internet security?
What are elliptic curves, and how are they used in factoring and cryptography?
Are there different flavors of infinity, some larger than others? How many flavors are there; do they go on forever?
How many ways can I put 29 marbles into a bucket, a drawer, and a box?
Why are two students, in a classroom of 28, likely to have the same birthday, even though there are 365 birthdays to choose from?
How many ways can I arrange 6 pairs of parentheses so they balance properly, e.g. ()(()(()()))?
How many ways can I triangulate a labeled octagon, and why is it the same answer as the 6 parentheses? How about an unlabeled octagon, free to spin around in the plane, or an unlabeled n-gon for that matter? I can triangulate a pentagon in one way: connect one vertex to the two on the other side. And a hexagon has 4 triangulations: connect one vertex to the other three, draw an equilateral triangle inside, or a Z, or a backwards Z.
I know about the 3 4 5 triangle, is there a formula for all the integer solutions to a2 + b2 = c2?
Do two cubes ever sum to a cube? How about fourth powers?
I know the sum of the first n integers is (n2+n)/2; is there a formula for the sum of the first n squares, or the first n cubes?
What is the golden ratio?
I have seen the Fibonacci sequence, wherein f(n) = f(n-2) + f(n-1); is there a simple formula for f(n), without having to step through all n values? How about other functions where f(n) is determined by prior values of f?
Is there really any difference between i and -i in the complex plane?
What is a simple group? Can they be classified? Does a group factor uniquely into simple groups, the way a number factors uniquely into primes?
How many necklaces can I make, with 30 beads, where beads can be red, yellow, or blue? Is there a general formula for k colors and n beads?
How many distinct cubes are there, where the faces can be colored red, yellow, blue, or green? Is there a general formula for k colors? How about larger shapes like the icosahedron, with 20 faces?
Why is every positive integer the sum of four squares? Example: 39 = 25 + 9 + 4 + 1.
The quadratic formula solves any quadratic equation; what are the cubic and quartic formulas for solving equations of degrees 3 and 4, and why is there no formula for equations of degree 5 and higher?
What shapes can be constructed using straightedge and compass? Why is it impossible to trisect the angle, or build a regular heptagon?
Why does every polynomial, such as x7 + 9x5 - πx4 + 23x - 79, have a solution somewhere in the complex plane?
When does x2+1 = 0 have six solutions?
What is the algorithm to solve the Rubik's Cube in a reasonable number of moves? Can it be generalized to other permutation puzzles? Can I take any of these puzzles off the shelf, enter the possible moves into a computer, mix it up, type in the scrambled configuration, and get a path back to start?
Why should two numbers,chosen at random, be relatively prime with a probability of 6/π2? How does π enter into it?
Why is it so difficult to count the representations of n as a sum of smaller numbers? Example: 25 = 11 + 5 + 5 + 3 + 1.
Can a matrix be infinite? How would you multiply two such matrices together?
Is there such a thing as infinite dimensional space?
What is the Cantor Set, and why is it the same as half of itself?
A curve such as y = x2 is infinitely thin. How then can a curve wiggle about to cover an entire region in the plane?
How does a parabolic mirror focus light from a distant object onto a point? How does an elliptical mirror focus light from one point to another?
Why does a planet travel in an ellipse around the sun?
What are continued fractions?