An analytic-flavoured proof of an algebraic result

It is often suggested that algebra and analysis, as subdisciplines of mathematics, are in some sense opposing schools of thought—perhaps even ideologies. ‘algebraists like equalities; analysts like inequalities’, I’ve heard people say. An amusing and thought-provoking shibboleth, no doubt. However, I would argue straight away that, to be precise, algebra is more akin to the study of isomorphisms or congruences… but perhaps that is to take the comparison too seriously.

Putting such superficial differences aside for a moment, it seems to me that typical algebraic proofs tend to consist of sequences of manipulations, each of which is aimed at proving that some set of axioms holds in order to deduce ever more powerful and wide-ranging truths about the objects at hand. The results are exact and often demonstrate a one-to-one correspondence between the objects, or perhaps even show us a new way of viewing something unfamiliar in terms of something more well understood.

Analytic proofs, on the other hand, have a more ‘approximate’ flavour. They make use of limiting processes, inequalities and usually aim to establish the existence of objects satisfying some property that is ‘good enough’ for the result to hold. That’s not to say analytic proofs aren’t beautiful—they absolutely are. But to my eyes, they seem almost apologetic in tone. There is a notion of ‘sufficiency’ that is less common in algebraic proofs.

It’s not very often (at least in fairly elementary mathematics) that the two flavours combine. But here is one place where they do.

The Gaussian integers are the complex numbers with integer real and imaginary part. Formally, we denote the set of Gaussian integers $\mathbb{Z}[i]$ and define it by

$$\mathbb{Z}[i] := \{ s + ti : s, t \in \mathbb{Z} \}$$

The square bracket notation is used because in general $R[x]$ denotes the ring of polynomials with coefficients in a ring $R$. So, sort of by analogy, $\mathbb{Z}[i]$ is the ring of polynomials with integer coefficients and ‘indeterminate’ $i$. Each element of the Gaussian integers is therefore of the form

$$\begin{aligned}

\sum_{n=0}^{m} k_n i^{n} &= k_0 i^0 + k_1 i^1 + k_2 i^2 + k_3 i^3 + k_4 i^4 + \dots + k_m i^m \\
&= k_0 (1) + k_1 (i) + k_2 (-1) + k_3 (-i) + k_4 (1) + \dots \\[1em]
&= \underbrace{(k_0 + k_4 – k_2 + \dots)}_{\in \mathbb{Z}} 1 + \underbrace{(k_1 – k_i + \dots)}_{\in \mathbb{Z}} i \\[1em]
&= s + ti, \; s, t \in \mathbb{Z} \end{aligned}$$

Another way of thinking about $R[x]$ is that it is the smallest ring containing all the elements of $R$, and the element $x$. If we add $x$ into a ring, the ring axioms (like closure under the two operations) force us to admit all possible polynomials in $x$ into the ring too.

…so the notation is consistent. But that’s not really relevant.

It can be shown that the set $\mathbb{Z}[i]$, with the standard operations of complex addition and multiplication, obeys certain rules: it’s an abelian group under addition, it’s closed under multiplication, multiplication is associative, and multiplication distributes over addition. That is to say, it forms a ring.

But in fact the Gaussian integers are a little bit more special.

Let $R$ be a commutative ring. An element $r \in R \setminus \{0\}$ is said to be a zero divisor if there is an element $s \in R \setminus \{0\}$ such that $rs = 0$. Intuitively, the zero divisors are the elements that can be reduced to zero by multiplication with another nonzero element.

Of course, in the integers there are no zero divisors. If $a$ and $b$ are both nonzero, $ab$ cannot possibly be zero. Equivalently (using the contrapositive), if we at some point find out that that $ab = 0$, we can instantly deduce that either $a = 0$ or $b = 0$. We’ve been assuming this property of the integers without thinking since we were little to solve quadratics by factorisation.

In a general ring, however, we cannot make this assumption. For example, in $\mathbb{Z} / 4 \mathbb{Z}$ (the integers modulo $4$) $2$ is a zero divisor since $2 \neq 0$ but $2 \cdot 2 \equiv 0 \pmod 4$. (If you’re wondering, it’s not too hard to show that $\mathbb{Z} / n \mathbb{Z}$ contains zero divisors if and only if $n$ is prime. Think about why $2$ worked in this case…)

But the Gaussian integers don’t have this kind of weirdness. Just like the usual integers, they have no zero divisors. We have a special name for rings like this.

A ring $R$ is said to be an integral domain if it has a $1$ (a multiplicative identity), $1_R \neq 0_R$ (it is non trivial), it is commutative, and it has no zero divisors.

We can be sure that $\mathbb{Z}[i]$ is an integral domain because it is a subring of $\mathbb{C}$, which is itself an integral domain because it is a field.

To see this, take $a, b$ in some field $\mathbb{F}$ and suppose that $a \neq 0$ and $ab = 0$. Since $a$ is nonzero we may multiply by its inverse in $\mathbb{F}$ to get $a^{-1}ab = a^{-1} 0$ which implies that $b = 0$. So either of $a$ or $b$ (or both) are zero.

Something I think is worth noting here is the fact that ‘sub-objects’ automatically inherit some, but not all, properties from their parent. In this particular case, the implication $a,b \neq 0 \implies ab \neq 0$ is true for all $a,b$ in $\mathbb{C}$ and hence must be true for all $a,b$ in $\mathbb{Z}[i] \subseteq \mathbb{C}$. Whether an operation commutes is another example of a property that is preserved in subsets, and in general any statement purely consisting of universal quantifiers will be. Statements that include existential quantifiers, though, like the existence of an identity or inverses for a certain operation, will not be inherited—at least a priori. This is the reason we really have no need to check associativity in verifying that a given subset of a group is a subgroup, for example.

But wait—there’s more! The Gaussian integers have another nice property in common with the usual integers: we can perform Euclidean division.

In a field, of course, we can divide things perfectly. Given any two numbers we can write one as the product of the other with something else. In the integers though, we can’t necessarily do this (there is no such $x \in \mathbb{Z}$ such that $2x = 5$, for example), but we can at least divide a number into another to a small degree of error. In my example before, $\frac{5}{2}$ could be said to equal $2$ remainder $1$. It’s probably exactly how you learnt to do division before you knew what fractions were.

It may seem obvious that the integers have this property, but for a general ring it is not obvious and in fact not necessarily true! In the integers the fact that we can do this is referred to as the ‘division theorem’.

Anyway, the Gaussian integers do have this property—and that’s what we’ll show now.

Let’s define some more stuff first.

An integral domain $R$ is said to be a Euclidean domain if there is a map $V: R \setminus \{0\} \to \mathbb{Z}_{\geq 0}$, known as the valuation, satisfying:

[1] $V(a) \leq V(ab) \; \; \forall a, b \in R \setminus \{0\}$

[2] Given $a, b \in R$ with $b \neq 0$, there are elements $q, r \in R$ such that $a = qb + r$ and either $r = 0$ or $V(r) < V(b)$.

The valuation can be thought of as a generalisation of the absolute value in the case of the usual integers. It is the function that effectively measures how small our remainder is when we do the Euclidean division.

The first condition says that the valuation should never decrease when we multiply two elements of the ring together, and the second condition is just the statement that Euclidean division is possible (using the valuation in place of the absolute value in the integers).

In the case of the integers, then, we can obviously use the absolute value as the valuation, which will satisfy both conditions. So the integers are a Euclidean domain.

The function $N: \mathbb{Z}[i] \setminus \{0\} \to \mathbb{Z}_{\geq 0}, s + ti \mapsto |s + ti|^2 = s^2 + t^2$ is called the norm on $\mathbb{Z}[i]$.

We will prove the following statement:

The ring $\mathbb{Z}[i]$ is a Euclidean domain with valuation $N$.

First, we will note that $N(a) \geq 1$ for all $a \in \mathbb{Z}[i]\setminus \{0\}$.

This should be obvious because integer lattice points in the complex plane (excluding the origin itself) are at least $1$ unit away from the origin, and so the minimum norm is the square of this—which is of course $1$. Alternatively, we can just see algebraically that a sum of two squared integers can only be less than $1$ if it is zero, in which case both $a$ and $b$ must be zero, which is not allowed. So the norm is always at least $1$.

From this it is also clear that for $a,b, \in \mathbb{Z}[i] \setminus \{0\}$, $N(ab) = |ab|^2 = |a|^2 |b|^2 \geq |a|^2 = N(a)$, so the first condition is satisfied.

Let $a,b \in \mathbb{Z}[i]$ with $b \neq 0$. Write $a = s + ti$ and $b = u + vi$ with $s,t,u,v \in \mathbb{Z}$. We aim to show that the second condition is satisfied: that we can write $a$ as $b$ multiplied by some other element of $\mathbb{Z}[i]$, plus another element with valuation either zero or strictly less than that of $b$.

Well, we can’t necessarily just divide $a$ by $b$ as usual in the Gaussian integers because they’re not a field. But the Gaussian integers are embedded in the complex numbers, so if we shut our eyes, zoom out, and imagine we’re in that perfect world just for a moment, we can divide $a$ by $b$ exactly.

Form the quotient $\frac{a}{b} = l + mi \in \mathbb{C}$, where $l,m \in \mathbb{R}$.

This isn’t quite what we wanted, but maybe we can approximate this quotient by an element of the Gaussian integers, and then add on a little bit extra to get us all the way there.

Let $L, M \in \mathbb{Z}$ be such that $|l – L| \leq \frac{1}{2}$ and $|m – M| \leq \frac{1}{2}$.

It is obvious that such an $L, M$ can always be found, since every real number lies at most $\frac{1}{2}$ away from an integer. To be pedantic, it follows from the Archimedean property of $\mathbb{R}$, which itself can be deduced from the standard properties of $\mathbb{R}$ including, most crucially, completeness.

Then $\frac{a}{b} = L + Mi + (l-L) + (m-M)i$. This is easily seen algebraically, but intuitively it just says that the quotient $\frac{a}{b} \in \mathbb{C}$ is equal to our nearest Gaussian integer $L + Mi$ plus the ‘error term’ $(l-L) + (m-M)i$ which is the difference between the approximation and the exact quotient.

Multiplying by $b$, we have

$$a = (L+Mi)b + ((l-L) + (m-M)i)b$$

Since $a – (L+Mi)b$ is in $\mathbb{Z}[i]$ (because of closure), the term $((l – L) + (m-M)i)b$ must be in $\mathbb{Z}[i]$ too. If it is zero, we can choose $q = L + Mi$ and $r = 0$ and we are done. If this is the case then we didn’t actually need to imagine we were in the complex numbers because $b$ did divide $a$ exactly.

If it isn’t zero, we want to show that it at least has valuation less than that of $b$.

So assume it is nonzero, so that $((l – L) + (m-M)i) \neq 0$. Then we have

$$\begin{aligned}
N(l-L + (m-M)i)b) &= |(l – L) + (m-M)i|^2 |b|^2 \\
&\leq \left( (\frac{1}{2})^2 + (\frac{1}{2})^2) \right) |b|^2 \\
&= \frac{1}{2} |b|^2 \\
&= \frac{1}{2} N(b) < N(b).
\end{aligned}$$

If we then choose $q = L + Mi$ and $r = ((l-L) + (m-M)i)b$, the second condition holds since we have shown $N(r) < N(b)$.

Therefore $\mathbb{Z}[i]$ is a Euclidean domain.

What we have shown seems to be a thoroughly algebraic result—that a particular ring defined in a certain way is actually part of another class of even more special rings. But the proof of this is not typical of a proof in elementary algebra, and maybe that’s because this ring is made up of elements from a more ‘complete’ ring of the kind that are studied in analysis.

From the fact that $\mathbb{Z}[i]$ is a Euclidean domain we can deduce that it is a PID (principal ideal domain), and from this it follows that (among many other things) every element of $\mathbb{Z}[i]$ can be factored uniquely into irreducible elements, much like fundamental theorem of arithmetic for the integers.

If we tried to prove this fact directly, I think we’d probably flounder around endlessly, wondering where to even start. But though the graceful, unhurried steps of algebra and abstraction, we can get there—and uncover some more general truths on the way.