8. More Algebraic Structures

For Emmy Noether, relationships among numbers, functions, and operations became transparent, amenable to generalization, and productive only after they have been dissociated from any particular objects and have been reduced to general conceptual relationships.
B. L. van der Waerden

When we first introduced Euclid’s algorithm in Chapter 4, it was for computing the greatest common measure of line segments. Then we showed how to extend it to work for integers. Does it work for other kinds of mathematical entities? This is the question we’ll be investigating in this chapter. As we’ll see, attempts to answer it led to important developments in abstract algebra. We’ll also show how some of these new algebraic structures enable new programming applications.

[With] one stroke, the classical restrictions of “numbers” to integers or to rational fractions was eliminated. [Stevin’s] general notion of a real number was accepted by all later scientists.

In his 1585 pamphlet De Thiende (“The Tenth”), published in English as Disme: The Art of Tenths, or, Decimall Arithmetike, Stevin introduces and explains the use of decimal fractions. This was the first time anyone in Europe proposed using positional notation in the other direction—for tenths, hundredths, and so on. Disme (pronounced “dime”) was one of the most widely read books in the history of mathematics. It was one of Thomas Jefferson’s favorites, and is the reason why U.S. currency has a coin called a “dime” and uses decimal coinage rather than the British pounds, shillings, and pence in use at the time.

In Disme, Stevin expands the notion of numbers from integers and fractions to “that which expresseth the quantitie of each thing” (as an English translation at the time put it). Essentially, Stevin invented the entire concept of real numbers and the number line. Any quantity could go on the number line, including negative numbers, irrational numbers, and what he called “inexplicable” numbers (by which he may have meant transcendental numbers). Of course, Stevin’s decimal representations had their own drawbacks, particularly the need to write an infinite number of digits to express a simple value, such as

Stevin’s representation enabled the solution of previously unsolvable problems. For example, he showed how to compute cube roots, which had given the Greeks so much trouble. His reasoning was similar to what eventually became known as the Intermediate Value Theorem (see the “Origins of Binary Search” sidebar in Section 10.8), which says that if a continuous function is negative at one point and positive at another, then there must be an intermediate point where its value is zero. Stevin’s idea was to find the interval between two consecutive integers where the function goes from negative to positive, then divide that interval into tenths, and repeat the process with the tenths, hundredths, and so on. He realized that by “zooming in,” any such problem could be solved to whatever degree of accuracy was needed, or as he put it, “one may obtain as many decimals of [the true value] as one may wish and come indefinitely near to it.”

Although Stevin saw how to represent any number as a point along a line, he did not make the leap to showing pairs of numbers as points on a plane. That invention—what we now call Cartesian coordinates—came from the great French philosopher and mathematician René Descartes (Renatus Cartesius in Latin).

* * *

Stevin’s next great achievement was the invention of (univariate¹) polynomials, also introduced in 1585, in a book called Arithmétique. Consider this expression:

4x⁴ + 7x³ – x² + 27x – 3

¹ Univariate polynomials are polynomials with a single variable. For the rest of this chapter, we will assume “polynomial” means univariate polynomial.

Prior to Stevin’s work, the only way to construct such a number was by performing an algorithm: Take a number, raise it to the 4th power, multiply it by 4, and so on. In, fact, one would need a different algorithm for every polynomial. Stevin realized that a polynomial is simply a finite sequence of numbers: {4, 7, –1, 27, –3} for the preceding example. In modern computer science terms, we might say that Stevin was the first to realize that code could be treated as data.

With Stevin’s insight, we can pass polynomials as data to a generic evaluation function. We’ll write one that takes advantage of Horner’s rule, which uses associativity to ensure that we never have to multiply powers of x higher than 1:

4x⁴ + 7x³ – x² + 27x – 3 = (((4x + 7)x – 1)x + 27)x – 3

For a polynomial of degree n, we need n multiplications and n – m additions, where m is the number of coefficients equal to zero. Usually we will settle for doing n additions, since checking whether each addition is needed is more expensive than just doing the addition. Using this rule, we can implement a polynomial evaluation function like this, where the arguments first and last specify the bounds of a sequence of coefficients of the polynomial:

Click here to view code image

template <InputIterator I, Semiring R>
R polynomial_value(I first, I last, R x) {
    if (first == last) return R(0);
    R sum(*first);
    while (++first != last) {
        sum *= x;
        sum += *first;
    }
    return sum;
}

Let’s think about the requirements on the types satisfying I and R. I is an iterator, because we want to iterate over the sequence of coefficients.² But the value type of the iterator (the type of the coefficients of the polynomial) does not have to be equal to the semiring³ R (the type of the variable x in the polynomial). For example, if we have a polynomial like ax² + b where the coefficients are real numbers, that doesn’t mean x has to be a real number; in fact, it could be something completely different, like a matrix.

² We’ll explain iterators more formally in Chapter 10, but for now we can think of them as generalized pointers.

³ A semiring is an algebraic structure whose elements can be added and multiplied and has distributivity. We will give its formal definition in Section 8.5.

Exercise 8.1. What are the requirements on R and the value type of the iterator? In other words, what are the requirements on coefficients of polynomials and on their values?

Stevin’s breakthrough allowed polynomials to be treated as numbers and to participate in normal arithmetic operations. To add or subtract polynomials, we simply add or subtract their corresponding coefficients. To multiply, we compute the product of every pair consisting of one coefficient from each polynomial. That is, if a_i and b_i are the ith coefficients of the polynomials being multiplied (starting from the lowest-order term) and c_i is the ith coefficient of the result, then

To divide polynomials, we need the notion of degree.

Definition 8.1. The degree of a polynomial deg(p) is the index of the highest nonzero coefficient (or equivalently, the highest power of the variable).

For example:

deg(5) = 0

deg(x + 3) = 1

deg(x³ + x – 7) = 3

Now we can define division with remainder:

Definition 8.2. Polynomial a is divisible by polynomial b with remainder r if there are polynomials q and r such that

a = bq + r ∧ deg(r) < deg(b)

(In this equation, q represents the quotient of a ÷ b.)

Doing polynomial division with remainder is just like doing long division of numbers:

Exercise 8.2. Prove that for any two polynomials p(x) and q(x):

1. p(x) = q(x) · (x – x₀) + r p(x₀) = r

2. p(x₀) = 0 p(x) = q(x) · (x – x₀)

* * *

Stevin realized that he could use the same Euclidean algorithm (the one we looked at in the end of Section 4.6) to compute the GCD of two polynomials; all we really need to do is change the types:

Click here to view code image

polynomial<real> gcd(polynomial<real> a, polynomial<real> b) {
    while (b != polynomial<real>(0)) {
        a = remainder(a, b);
        std::swap(a, b);
    }
    return a;
}

The remainder function that we use implements the algorithm for polynomial division, although we do not care about the quotient. The polynomial GCD is used extensively in computer algebra for tasks such as symbolic integration.

Stevin’s realization is the essence of generic programming: an algorithm in one domain can be applied in another similar domain.

Just as in Section 4.7, we need to show that the algorithm works—specifically, that it terminates and computes the GCD.

To show that the algorithm terminates, we need to show that it computes the GCD in a finite number of steps. Since it repeatedly performs polynomial remainder, we know by Definition 8.2 that

deg(r) < deg(b)

So at every step, the degree of r is reduced. Since degree is a non-negative integer, the decreasing sequence must be finite.

To show the algorithm computes the GCD, we can use the same argument from Section 4.7; it applies to polynomials as well as integers.

Exercise 8.3 (from Chrystal, Algebra). Find the GCD of the following polynomials:

Perhaps the most important mathematician to come out of Göttingen was Carl Friedrich Gauss, who was the founder of German mathematics in the modern sense. Among his many accomplishments was his seminal work on number theory, described in his 1801 book Disquisitiones Arithmeticae (“Investigations of Arithmetic”). Gauss’s book is to number theory what Euclid’s Elements is to geometry—the foundation on which all later work in the field is based. Among other results, it includes the Fundamental Theorem of Arithmetic, which states that every integer has a unique prime factorization.

Another of Gauss’s innovations was the notion of complex numbers. Mathematicians had used imaginary numbers (xi where i² = – 1) for over 200 years, but these numbers were not well understood and were usually avoided. The same was true for the first 30 years of Gauss’s career; we have evidence from his notebooks that he used imaginary numbers to derive some of his results, but then he reconstructed the proofs so the published versions would not mention i. (“The metaphysics of i is very complicated,” he wrote in a letter.)

But in 1831, Gauss had a profound insight: he realized that numbers of the form z = x + yi could be viewed as points (x, y) on a Cartesian plane. These complex numbers, he saw, were just as legitimate and self-consistent as any other numbers.

Here are a few definitions and properties we’ll use for complex numbers:

The absolute value of a complex number z is the length of the vector z on the complex plane, while the argument is the angle between the real axis and the vector z. For example, |i| = 1 and arg (i) = 90°.

Just as Stevin did for polynomials, Gauss demonstrated that complex numbers were in fact full-fledged numbers capable of supporting ordinary arithmetic operations:

Multiplying two complex numbers can also be done by adding the arguments and multiplying the absolute values. For example, if we want to find , we know it will also have an absolute value of 1 and an argument of 45° (since 1 · 1 = 1 and 45 + 45 = 90).

* * *

Gauss also discovered what are now called Gaussian integers, which are complex numbers with integer coefficients. Gaussian integers have some interesting properties. For example, the Gaussian integer 2 is not prime, since it can be expressed as the product of two other Gaussian integers, 1 + i and 1 – i.

We can’t do full division with Gaussian integers, but we can do division with remainder. To compute the remainder of z₁ and z₂, Gauss proposed the following procedure:

1. Construct a grid on the complex plane generated by z₂, iz₂, −iz₂, and −z₂.

2. Find a square in the grid containing z₁.

3. Find a vertex w of the grid square closest to z₁.

4. z₁ – w is the remainder.

Gauss realized that with this remainder function, he could apply Euclid’s GCD algorithm to complex integers, as we’ve done here:

Click here to view code image

complex<integer> gcd(complex<integer> a, complex<integer> b) {
    while (b != complex<integer>(0)) {
        a = remainder(a, b);
        std::swap(a, b);
    }
    return a;
}

The only thing we’ve changed are the types.

* * *

Gauss’s work was extended by another Göttingen professor, Peter Gustav Lejeune-Dirichlet. While Gauss’s complex numbers were of the form (in Dirichlet’s terminology) , Dirichlet realized that this was a special case of where a did not have to be 1, and that different properties followed from the use of different values. For example, the standard GCD algorithm works on numbers of this form when a = 1, but it fails when a = 5 since there end up being numbers that don’t have a unique factorization. For example:

It turns out that if Euclid’s algorithm works, then there is a unique factorization. Since we have no unique factorization here, then Euclid’s algorithm doesn’t work in this case.

Dirichlet’s greatest result was his proof that if a and b are coprime (that is, if gcd(a,b) = 1), then there are infinitely many primes of the form ak + b.

Most of Dirichlet’s results were described in the second great book on number theory, appropriately called Vorlesungen über Zahlentheorie (“Lectures on Number Theory”). The book contains the following important insight, which we used in our epigraph for Chapter 4:

[T]he whole structure of number theory rests on a single foundation, namely the algorithm for finding the greatest common divisor of two numbers.

All the subsequent theorems ... are still only simple consequences of the result of this initial investigation....

The book was actually written and published after Dirichlet’s death by his younger Göttingen colleague, Richard Dedekind, based on Dedekind’s notes from Dirichlet’s lectures. Dedekind was so modest that he published the book under Dirichlet’s name, even after adding many additional results of his own in later editions. Unfortunately, Dedekind’s modesty hurt his career; he failed to get tenure at Göttingen and ended up on the faculty of a minor technical university.

Dedekind observed that Gaussian integers and Dirichlet’s extensions of them were special cases of a more general concept of algebraic integers, which are linear integral combinations of roots of monic polynomials (polynomials where the coefficient of the highest-order term is 1) with integer coefficients. We say that these polynomials generate these sets of algebraic integers. For example:

Dedekind’s work on algebraic integers contained almost all the fundamental building blocks of modern abstract algebra. But it would take another great Göttingen mathematician, Emmy Noether, to make the breakthrough to full abstraction.

Noether was well known for her willingness to help students and give them her ideas to publish, but she published relatively little herself. Fortunately, a young Dutch mathematician, Bartel van der Waerden, audited her course and wrote a book based on her lectures (which he credits on the title page). Called Modern Algebra, it was the first book to describe the abstract approach she had developed.

This book, Modern Algebra, led to a fundamental rethinking of the way modern mathematics is presented. Its revolutionary approach—the idea that you express your theorems in the most abstract terms—is Noether’s creation. Most of mathematics—not just algebra—changed as a result of her work; she taught people to think differently.

⁴ The term “ring,” coined by Hilbert, was intended to use the metaphor of a bunch of people involved in a common enterprise, like a criminal ring. It has nothing to do with jewelry rings.

Definition 8.3. A ring is a set on which the following are defined:

operations : x + y, –x, xy

constants : 0_R, 1_R

and on which the following axioms hold:

Rings⁵ have the properties we associate with integer arithmetic—operators that act like addition and multiplication, where addition is commutative and multiplication distributes over addition. Indeed, rings may be thought of as an abstraction of integers, and the canonical example of a ring is the set of integers, . Also observe that every ring is an additive group and therefore an abelian group. The “addition” operator is required to have an inverse, but the “multiplication” operator is not.

⁵ Some mathematicians define rings without the multiplicative identity 1 and its axioms, and call rings that include them unitary rings; we do not make that distinction here.

In practice, mathematicians write the zeroes without their subscripts, just as we’ve done in the axioms. For example, in discussing a ring of matrices, “0” refers not to the single integer zero but to the additive identity matrix.

Besides integers, other examples of rings include the following sets:

• n × n matrices with real coefficients

• Gaussian integers

• Polynomials with integer coefficients

We say that a ring is commutative if xy = yx. Noncommutative rings usually come from the realm of linear algebra where matrix multiplication does not commute. In contrast, polynomial rings and rings of algebraic integers do commute. These two types of rings lead to two branches of abstract algebra, known as commutative algebra and noncommutative algebra. Rings are often not explicitly labeled as “commutative” or “noncommutative”; instead, one type of ring or the other is assumed from the branch of algebra. With the exception of Sections 8.5 and 8.6, the rest of this book will deal with commutative algebra—the kind that Dedekind, Hilbert, and Noether worked on—so from then on we will assume our rings are commutative.

Definition 8.4. An element x of a ring is called invertible if there is an element x^–1 such that

xx^–1 = x^–1x = 1

Every ring contains at least one invertible element: 1. There may be more than one; for example, in the ring of integers , both 1 and –1 are invertible.

Definition 8.5. An invertible element of a ring is called a unit of that ring.

Exercise 8.4 (very easy). Which ring contains exactly one invertible element? What are units in the ring of Gaussian integers?

Theorem 8.1: Units are closed under multiplication (i.e., a product of units is a unit).

Proof. Suppose a is a unit and b is a unit. Then (by definition of units) aa^–1 = 1 and bb^–1 = 1. So

1 = aa^–1 = a · 1 · a^–1 = a(bb^–1)a^–1 = (ab)(b^–1a^–1)

Similarly, a^–1a = 1 and b^–1b = 1, so

1 = b^–1b = b^–1 · 1 · b = b^–1(a^–1a)b = (b^–1a^–1)(ab)

We now have a term that, when multiplied by ab from either side, gives 1; that term is the inverse of ab:

(ab)^–1 = b^–1a^–1

So ab is a unit.

Exercise 8.5. Prove that:

• 1 is a unit.

• The inverse of a unit is a unit.

Definition 8.6. An element x of a ring is called a zero divisor if:

1. x ≠ 0

2. There exists a y ≠ 0, xy = 0

For example, in the ring of remainders modulo 6, 2 and 3 are zero divisors.

Definition 8.7. A commutative ring is called an integral domain if it has no zero divisors.

It’s called “integral” because its elements act like integers—you don’t get zero when you multiply two nonzero things. Here are some examples of integral domains:

• Integers

• Gaussian integers

• Polynomials over integers

• Rational functions over integers, such as (A rational function is the ratio of two polynomials.)

The ring of remainders modulo 6 is not an integral domain. (Whether a ring of remainders is integral depends on whether the modulus is prime.)

Exercise 8.6 (very easy). Prove that a zero divisor is not a unit.

In the previous chapter, we combined power with matrix multiplication to compute linear recurrences. It turns out that we can use this technique for many other algorithms if we use a more general notion of matrix multiplication.

Just as we generalized our power function to work with any operation, we can now generalize the notion of matrix multiplication. Normally we think of matrix multiplication as consisting of a series of sums of products, as shown in the earlier formula. But what’s mathematically essential is actually that there be two operations, a “plus-like” one that is associative and commutative (denoted by ⊕) and a “times-like” one that is associative (denoted by ⊗), where the latter operation distributes over the first:

a ⊗ (b ⊕ c) = a ⊗ b ⊕ a ⊗ c

(b ⊕ c) ⊗ a = b ⊗ a ⊕ c ⊗ a

We’ve just seen an algebraic structure that has operations like this, a ring. However, rings have a few requirements we don’t need, specifically those involving the additive inverse operation. Instead, what we want is a semiring, a ring without minus (–).

Definition 8.8. A semiring is a set on which the following are defined:

operations : x + y, xy

constants : 0_R, 1_R

and on which the following axioms hold:

Our definition follows the mathematical convention of referring to the operations as + and × rather than ⊕ and ⊗. But as with all the algebraic structures we’ve been discussing, the symbols refer to any two operations that behave in the manner specified by the axioms.

The canonical example of a semiring is the set of natural numbers . While natural numbers do not have additive inverses, you can easily perform matrix multiplication on matrices with non-negative integer coefficients. (In fact, we could relax the requirements further by removing the additive identity 0 and the multiplicative identity 1, as well as their corresponding axioms; matrix multiplication⁶ would still work. We might refer to a semiring without 0 and 1 as a weak semiring.)

⁶ Here we are assuming the straightforward algorithm for matrix multiplication; faster algorithms require stronger theories.

Finding all such paths is known as finding the transitive closure of the graph. To compute the transitive closure, we take an n × n Boolean matrix where entry x_ij is 1 if the relation holds between i and j (in this case, if person i is friends with person j), and 0 otherwise; we’ll also assume people are friends with themselves. Here’s a small example:

The matrix tells us who each person’s friends are. We can apply generalized matrix multiplication where we replace ⊕ by Boolean OR (∨) and ⊗ by Boolean AND (∧). We say this is the matrix multiplication generated by a Boolean or {∨, ∧}-semiring. Multiplying the matrix by itself using these operations tells us who the friends of our friends are. Doing this multiplication n – 1 times will eventually find all the people in each network of friends. Since multiplying the matrix by itself several times is just raising it to a power, we can use our existing power algorithm to do the computation efficiently. Of course, we can use this idea to compute the transitive closure of any relation.

Exercise 8.7. Using the power algorithm from Chapter 7 with matrix multiplication on Boolean semirings, write a program for finding transitive closure of a graph. Apply this function to find the social networks of each person in the preceding table.

Another example of a classic problem we can solve this way is finding the shortest path between any two nodes in a directed graph like this one:

As before, we can represent the graph as an n × n matrix—this time one whose values a_ij represent the distance from node i to node j. If there is no edge from one node to another, we’ll initially list the distance as infinity.

This time, we use matrix multiplication generated by a tropical or {min, +}-semiring:

That is, the ⊕ operation is min, and the ⊗ operation is +. Again, we raise the resulting matrix to the n – 1 power. The result tells us the shortest path of any length up to n – 1 steps.

Exercise 8.8. Using the power algorithm from Chapter 7 with matrix multiplication on tropical semirings, write a program for finding the length of the shortest path in a graph.

Exercise 8.9. Modify the program from Exercise 8.8 to return not just the shortest distance but the shortest path (a sequence of edges).

Definition 8.9. E is a Euclidean domain if:

• E is an integral domain

• E has operations quotient and remainder such that

b ≠ 0 a = quotient(a, b) · b + remainder(a, b)

• E has a non-negative norm ||x||: E → satisfying

The term “norm” here is a measure of magnitude, but it should not be confused with the Euclidean norm you may be familiar with from linear algebra. For integers, the norm is their absolute value; for polynomials, it is the degree of the polynomial; for Gaussian integers, it is the complex norm. The important idea is that when you compute the remainder, the norm decreases and eventually goes to zero, since it maps into natural numbers. We need this property to guarantee that Euclid’s algorithm terminates.

* * *

Now we can write the fully generic version of the GCD algorithm:

Click here to view code image

template <EuclideanDomain E>
E gcd(E a, E b) {
    while (b != E(0)) {
        a = remainder(a, b);
        std::swap(a, b);
    }
    return a;
}

The process we’ve gone through in transforming the GCD algorithm from something that works only on line segments to something that works on very different types illustrates the following important principle:

To make something generic, you don’t add extra mechanisms. Rather, you remove constraints and strip down the algorithm to its essentials.

⁷ The term “field” relies on the metaphor of a field of study, not a field of wheat.

Definition 8.10. An integral domain where every nonzero element is invertible is called a field.

Just as integers are the canonical example of rings, so rational numbers () are the canonical example of fields. Other important examples of fields are as follows:

• Real numbers

• Prime remainder fields

• Complex numbers

A prime field is a field that does not have a proper subfield (a subfield different from itself). It turns out that every field has one of two kinds of prime subfields: or . The characteristic of a field is p if its prime subfield is (the field of integer remainders modulo p), and 0 if its prime subfield is .

* * *

All fields can be obtained by starting with a prime field and adding elements that still satisfy the field properties. This is called extending the field.

In particular, we can extend a field algebraically by adding an extra element that is a root of a polynomial. For example, we can extend with , which is not a rational number, since it is the root of the polynomial x² – 2.

We can also extend a field topologically by “filling in the holes.” Rational numbers leave gaps in the number line, but real numbers have no gaps, so the field of real numbers is a topological extension of the field of rational numbers. We can also extend the field to two dimensions with complex numbers. Surprisingly, there are no other finite dimensional fields containing reals.⁸

⁸ There are four- and eight-dimensional field-like structures called quaternions and octonions. These are not quite fields, because they are missing certain axioms; both quaternions and octonions lack commutativity of multiplication, and octonions also lack associativity of multiplication. There are no other finite-dimensional extensions of real numbers.

Up to now, every algebraic structure we’ve introduced in this book has operated on a single set of values. But there are also structures that are defined in terms of more than one set. For example, an important structure called a module contains a primary set (an additive group G) and a secondary set (a ring of coefficients R), with an additional multiplication operation R × G → G that obeys the following axioms:

If ring R is also a field, then the structure is called a vector space.

A good example of a vector space is two-dimensional Euclidean space, where the vectors are the additive group and the real coefficients are the field.

Let’s extend our table from Section 6.8 to include the new structures we introduced in this chapter. Note that every row of the table includes all the axioms from earlier rows. (In the case of semirings and rings, the “times” operation inherits all the axioms from monoids, while the “plus” operation inherits the axioms from abelian groups.) To illustrate this, we’ve grayed out operations, elements, and axioms that appeared previously in the table.

As we did before, we can also define some other structures more concisely in terms of others:

This diagram shows the relationships between some of the most important structures discussed in this chapter:

The first time you encounter algebraic structures, it might seem as if there are so many varieties that it’s hard to keep track of their properties. However, they fit into a manageable taxonomy that makes their relationships clear—a taxonomy that has enabled great progress in mathematics over the last hundred years.