Domains and number systems

A large part of number theory is built around generalizing the machinery of number systems. That is, any structure that we could reasonably call "numbers". It seems that this category should be rather limited. After all, the four most well-known number systems, integers, rational numbers (fractions), real numbers, and complex numbers, are similar enough to each other that many people just think of them as a single system. Mathematically, any one from the list can be considered a substructure of the next one. Are there other number systems out there? And if so, are they different to the familiar ones in any significant ways?

It wasn't until the 18th century that mathematicians began to run into these new number systems, many of which were minimalist chimeras of integers, $\mathbb{Z}$, and complex numbers, $\mathbb{C}$. More on that later. They had initially assumed that these number systems behaved like their parent systems, even leading a high-profile mathematician to a mistaken proof of Fermat's Last Theorem. Unfortunately, many hidden assumptions about how numbers behave weren't valid in these systems. Fortunately, this was ripe ground for generalizations that eventually led to abstract algebra and ring theory.

The approach taken by abstract algebra is to highlight the common properties of closed structures in mathematics.

Closure is a key property in structures like monoids and groups. Monoids are sets of objects with an intrinsic operation, some way of combining two elements together into another element. Closure ensures that this operation combines two elements in a way that their combination is also in the monoid. An easy example of a monoid is all the powers of 2: $2, 4, 8, 16, \dots$ under the operation of multiplication. To see that it's closed, take two arbitrary elements $2^n$ and $2^m$. Multiplying gives $2^{n+m}$ which is also in the monoid.

Groups add an additional constraint to monoids: not only does the operation have to be closed, but it also needs to be reversibe (equivalently, there are "inverse" elements). In a loose sense, this means that all the mathematics that takes place in a group stays isolated within that group. The same logic works for rings and fields, though now with a second operation.

Rings capture most of what we consider to be number systems. Take $\mathbb{Z}$ for example: this is just the set of integers (negative and positive whole numbers). Addition, subtraction, and multiplication of integers yields more integers, and addition of $0$ and multiplication by $1$ effectively do nothing. Both addition and multiplication are associative, and when they are mixed together they follow another ring requirement: the distributive property:

$a (b + c) = ab + ac$

While rings formalize the general idea of a number system, they are general enough to include objects that wouldn't be considered typical numbers. An example is the ring of polynomials with integer coefficients $\mathbb{Z}[x]$, whose elements can be written as

$a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1}x + a_n \in \mathbb{Z}[x] \: \: a_{*} \in \mathbb{Z}$

Adding/subtracting polynomials to each other gives you another polynomial, and the same can be said for multiplication. In this ring, the $0$ and $1$ elements are exactly what you'd expect.

In the abstract, rings are considered groups over addition and monoids over multiplication. Being a group under addition means that the inverse operation, subtraction, is always defined. Being a monoid under multiplication, however, means that division isn't always defined. Some rings, such as $\mathbb{Z}$, have enough structure to them that we can create fields, another ring-like structure which has division defined for every element. The procedure of turning a ring into a field is really simple: any two elements $a$ and $b$ from a ring correspond to an element $a/b$ its corresponding field. For example, the rational numbers $\mathbb{Q}$ are the field obtained from $\mathbb{Z}$ by this process.

This isn't always possible to do, though. An example is the ring of 2x2 matrices with integer entries:

$M_2(\mathbb{Z}) = \{ \left( \begin{matrix} w & x \\ y & z \end{matrix} \right): w, x, y, z \in \mathbb{Z}\}$

This ring has all the ring properties, it has a "zero" element, a matrix of all 0's, and a "1" element, the 2x2 identity matrix. but it's impossible to create a field of elements $a/b$ with $a, b \in M_2(\mathbb{Z})$. This isn't because $a/b$ itself is impossible to construct, but that multiplication is no longer well-defined. To see why, multiply two elements $a/b$ and $c/d$ to get $ac/bd$. If $bd = 0$, then the product $ac/bd$ doesn't exist, violating the requirements to be a field. Two elements that have this property are

$a = \left( \begin{matrix} 0 & 1 \\ 0 & 0\end{matrix} \right) , \: b = \left( \begin{matrix} 0 & 2 \\ 0 & 0 \end{matrix}\right)$

Not only is $ab = 0$, but $a^2 = 0$ and $b^2 = 0$, despite neither of the two being $0$ themselves. These elements, known as zero divisors, are what prevent the ring from ever being extended into a field. It's not just these two that are problematic, either, there are infinitely many zero divisors in $M_2 (\mathbb{Z})$. To distinguish rings like this one from rings like $\mathbb{Z}$ that have no zero divisors, we introduce a class of rings known as integral domains.

Integral domains are rings without zero divisors. As a result, they are integer-like in the sense that they can be extended to a field of fractions. The ring of polynomials from earlier, $\mathbb{Z}[x]$, is also an example of an integral domain. Its field of fractions is the field of rational functions. Since polynomials fit so well in with number systems might not be surprising: they can be thought of as representing indexed lists of numbers.

Before you get the sense that nothing interesting can really be happening between the jump from integral domain to field, let's lay out what mathematics in $\mathbb{Z}$ is actually like. Despite division not always being defined, divisibility can still be talked about. For example, 1, 2, and 3 divide 6. Any number can be written as a product of its divisors, such as $30 = 10 \times 3$. If a number only has 1 as a divisor, then it's known as a prime number. In general rings, this is known as a prime element instead. In $\mathbb{Z}$, every number can be written uniquely as a product of primes; this is the fundamental theorem of arithmetic. In the example above, the unique factorization of $30$ into primes is $2*3*5$.

Another key property of $\mathbb{Z}$ is the ability to efficiently find the greatest common divisor (GCD) of two numbers. This is simply a matter of finding all of the common prime factors between two numbers. The most straightforward approach is to simply factor both numbers to find the GCD. This turns out being very slow since factorization comes down to brute force (guessing). In $\mathbb{Z}$, however, there is a shortcut known as the Euclidean algorithm. Only a subset of domains known as Euclidean domains have this property.

$\text{Euclidean algorithm to find the GCD of 1014 and 182}$ $1014 = 5 \times \underline{182 + 104}$ $\underline{182}= 1 \times \underline{104} + 78$ $104= 1 \times \underline{78 + 26}$ $\underline{78} = 3 \times \underline{26} + 0 \: *$ $\text{GCD(1014, 182) = 26}$

In $\mathbb{Z}$, to find the GCD of $p$ and $q$ where $q < p$, write $p = nq + r$ for some $n$ and $r$. There are many ways to do this, but forcing $r < q$ will always lead to just one. This is the same as "dividing" $p$ by $q$ to get a remainder $r$. In the Euclidean algorithm, simply take $q$ and $r$, where $r < q$, and repeat this process (notice that $q$ is now in $p$'s place and $r$ is now in $q$'s place ). This will go on until reaching either $0$ or $1$, where the algorithm stops. If it reaches $1$, then $GCD(p, q) = 1$. Otherwise, the algorithm returns with the $q$ from the last step. See above for an example.

Unique factorization and the existence of the Euclidean algorithm are both ancient theorems in number theory. However, they break down in some domains. To actually construct one, we can start with $\mathbb{Z}$ and add an element from $\mathbb{C}$, say $\sqrt{-5}$ to it. This means that we have a number system, $\mathbb{Z}[\sqrt{-5}]$, with elements

$a + b \sqrt{-5} \: \: a, b \in \mathbb{Z}$

Not only is this a ring, but also an integral domain just as $\mathbb{Z}$ is. However, number theory in $\mathbb{Z}[\sqrt{-5}]$ is different. For example, unique factorization no longer holds:

$6 = 2 \times 3 = (1 + \sqrt{-5} )(1 - \sqrt{-5})$

Domains with unique factorization are called UFDs. While $\mathbb{Z}$ is a UFD, $\mathbb{Z}[\sqrt{-5}]$ isn't.

One consequence of unique factorization failing is that the Euclidean algorithm doesn't exist in this domain either. In fact, the existence of the Euclidean algorithm implies unique factorization (so all Euclidean domains are UFDs) even though unique factorization doesn't guarantee the Euclidean algorithm's existence. An example is $\mathbb{Z}[ \frac{1 + \sqrt{-19}}{2} ]$, which is a UFD but not a Euclidean domain. The proof is here. In fact, $-19, -43, -67, \text{and} -163$ are the only numbers which generate non-Euclidean UFDs in the same form as $\mathbb{Z}[ \frac{1 + \sqrt{-19}}{2} ]$. This is deeply related to the following near-integer approximations:

$e^{\pi \sqrt{43}} \approx 960^3 + 744$ $e^{\pi \sqrt{67}} \approx 5280^3 + 744$ $e^{\pi \sqrt{163}} \approx 640320^3 + 744$

In $\mathbb{Z}[\sqrt{-5}]$, the concept of a prime number also subtly breaks down to be replaced by the concept of an irreducible number (or atom). Primes and atoms both share the feature that they are only divisible by $1$, but primes are defined by the additional property that whenever a prime $p$ divides $ab$, or $p | ab$, then either $p | a$ or $p | b$. In the example above, $2, 3, 1 + \sqrt{-5}, \text{and} 1 - \sqrt{-5}$ are all irreducible, but none of them are prime.

To see why $2$ isn't prime, note that $2 | (1 + \sqrt{-5} )(1 - \sqrt{-5})$, but neither $2 |(1 + \sqrt{-5})$ nor $2|(1 - \sqrt{-5})$ are true. This applies to the other three as well.

The distinction between prime and atomic elements doesn't exist in UFDs. In fact, they coincide in a slightly larger class of domains known as GCD domains, in which greatest common divisors always exist. The difference between UFD domains and GCD domains is small, but comes about from the fact that unique factorization always has to have finitely many factors. As a result, the ring of holomorphic functions is an example of a non-UFD GCD. First, it's an integral domain since two holomorphic functions cannot multiply to 0. The GCD between two functions can be defined as the zeroes they have in common, so it's a GCD domain. However, factorization of holomorphic functions is not always finite:

$sin(z) = z \displaystyle \prod_{k=1}^{\infty} \left( 1 - \frac{z^2}{\pi^2 k ^2} \right)$

A different situation where prime numbers start to break down is in $\mathbb{Z}[i]$, but in a more literal sense. In this domain, $5$ is no longer prime since $5 = (2 + i)(2 - i) = (1 + 2i)(1 - 2i)$. $13, 17, \text{and } 29$ are some other primes which break down in this domain. How can we know exactly what primes lost? An element $s$ in $\mathbb{Z}[i]$ can be written as $s = a + ib$. Multiplying by its conjugate gives

$s^* s = p = a^2 + b^2$

So all the primes that are split are the ones that can be written as the sum of two squares. Fermat proved that this happens for a prime $p$ iff $p \equiv 1 \: mod \: 4$. However, this was in the context of classical number theory long before domains were known about. For a general domain $\mathbb{Z}[\sqrt{-n}]$, the primes that split are just those of the form $p = a^2 + n b^2$.

Since $5 = (2 + i)(2 - i) = (1 + 2i)(1 - 2i)$, this should immediately imply that unique factorization breaks down. But it doesn't; thanks to the notion of a "unit," these two factorizations are actually the same. A unit of a ring is any element with an inverse. This makes it similar to the identity element, $1$, in the sense that multiplication with units can be effectively ignored. In $\mathbb{Z}[i]$, the units are $1, -1, i, -i$. The two factorizations, $(2 + i)(2 - i) = i(1 - 2i) \times (-i) (1 + 2i)$, can then be considered the same since they only differ by multiplication of units.

Since $\mathbb{Z}[i]$ is a UFD, it has it's own set of prime numbers. Here's what they look like on the complex plane:

Just as above for primes, in the ring $\mathbb{Z}[\sqrt{n}]$ all units $u = a + b\sqrt{n}$ can be found from the solutions of $\pm 1 = a^2 - n b^2$. For example, the units in $\mathbb{Z}[\sqrt{2}]$ are generated by $\pm 1 = a^2 - 2 b^2$. The first nontrivial solution is $a=1, b=1$ or $u = 1 + \sqrt{2}$. You can take powers of this solution to find the others:

$( 1 + \sqrt{2})^2 = 3 + 2 \sqrt{2}$ $( 1 + \sqrt{2})^3 = 7 + 5 \sqrt{2}$ $( 1 + \sqrt{2})^4 = 17 + 12 \sqrt{2}$ $( 1 + \sqrt{2})^n = \displaystyle \sum_{k \equiv 0 \: mod \: 2}^n \dbinom{n}{k} 2^{k/2} + \sqrt{2} \displaystyle \sum_{k \equiv 1 \: mod \: 2}^n \dbinom{n}{k} 2^{(k-1)/2}$

Without using binomial coefficients, the unit's components follow the recursion:

$u_n = a_n + b_n \sqrt{2} \: \: a_1 = 1, b_1 = 1$ $a_{n+1} = a_n + 2 b_n$ $b_{n+1} = a_n + b_n$

Another cool property is that the ratio $a_n / b_n$ approaches $\sqrt{2}$. Since $a_n$ and $b_n$ become larger as n grows, the equation $\pm 1 = a^2 - 2 b^2$ can be approximated by

$0 \approx a^2 - 2 b^2$ $a/b \approx \sqrt{2}$

In general, finding the units of $\mathbb{Z}[\sqrt{n}]$ reduces to another problem from classical number theory: Pell's equation. This equation is also well-studied in classical number theory since it can generate rational approximations of square roots.