Representing complex numbers exactly on a computer
2020-06-03
There are a lot of ways to represent numerical values on a computer, you've got the various fixed-size integer types and floating point types, but you also have arbitrary precision arithmetic, where the size of the number is limited only by the memory of the machine.
To represent the real numbers, $\mathbb{R}$, programmers often choose floating point numbers. But of course, floating point is terrible: multiplication isn't associative or commutative, neither is addition, you don't really have reciprocals, and so on. Useless for exact arithmetic of the kind you need when doing algebra.
This blog post is about a way to represent cyclotomic fields, which provide (among other things):
All rational numbers
$\sqrt{m}$ for any integer $m$
All of the field axioms: multiplication and addition with proper associativity, commutativity, and invertibility
Enough numbers to represent any finite group
They're still a bit tricky to represent on a computer though, as you'll see.
What is a cyclotomic field?
I refer to $K$ as a cyclotomic field if there exists some $n > 0$ such that $K = \mathbb{Q}(\zeta_n)$. That is, $K$ is the rational numbers with one primitive nth root of unity added. Essentially, that means that we have $\mathbb{Q}$ plus all solutions to the equation $x^n - 1 = 0$, and we take the closure under all field operations (addition, multiplication, inversion).
Why is this a field? The proof of this requires a bit of mathematical knowledge, but it's because our definition of $K$ was a bit non rigorous. In fact, $K$ is the splitting field of $x^n - 1$ over $\mathbb{Q}$. There's a decent amount of Galois theory machinery you need to build up before it becomes clear why $K$ should exist, but essentially you just factor $x^n - 1$ into irreducible factors and, at each stage, add a root to $K_i$ by constructing $K_{i+1} = K_i[x]/(f_i(x))$. The details aren't as important as the result, which is that $K$ exists and is a field.
At this point, we can prove that we have all of the field axioms. Great! We also have all roots of rationals by the Kronecker-Weber theorem (non-trivial to prove, but a nice result). What do I mean by "we have enough numbers to represent any finite group"?
If you read my other blog post or know a thing or two about representation theory, you'll know what a representation is. The cool thing is that you can represent any finite group with coefficients in some cyclotomic field $K$.
More specifically, if $G$ is a finite group with elements whose order have least common multiple $m$, then if $K$ contains the $m$th roots of unity, we can realise all representations of $G$ using coefficients from $K$. This is a theorem due to Brauer which I saw in a textbook on representation theory by Serre.
How do you represent one in a computer?
The answer to this is simple, you just represent it the same way as you do on paper - as a sum of powers of $\zeta_n$ with coefficients from $\mathbb{Q}$. So if we have $z \in K$, we can represent an element as:
$$z = \sum_{i=0}^{n-1} q_i \zeta_n^i$$
where $q_i \in \mathbb{Q}$. So we can just store a vector of the coefficients $q_i$, right?
WRONG! If you did this, the representations of elements would not be unique, so you wouldn't be able to check equality. The problem is that ${ \zeta_n^i : 0 \leq i < n }$ isn't a basis for $K$ as a $\mathbb{Q}$-vector space. This is obvious if you factor the polynomial defining $K$ a bit:
$$\frac{x^n - 1}{x-1} = 1 + x + \ldots + x^{n-1}$$
So we have a linear dependency: $-1 = x + \ldots + x^{n-1}$. We can we can try to fix this by seeing if ${ \zeta_n^i : 0 < i < n }$ is a basis. Since we got rid of the constant term, that's it, this is a basis now, right?
WRONG! Well, wrong in all except one case. If $n=p$ prime, then this actually is a basis. This is because all of the roots are primitive, $p$ is coprime to all smaller numbers (except 1), and thus $K/\mathbb{Q}$ is a degree $p-1$ extension i.e. a dimension $p-1$ vector space over $\mathbb{Q}$. That's not exactly rigorous, but you get the idea.
From this point, we assume $n=p$ prime, so this basis is actually a basis. Otherwise we have to choose a better basis and things get complicated.
Operating in the field
It's clear how to compute $z + z'$ and $-z$, you just add the list of coefficients in $\mathbb{Q}$. $zz'$ isn't much more difficult, you just write out the sums and multiply them:
$$ \begin{align} zz' &= \left(\sum_{i=1}^{p-1} q_i \zeta_p^i\right)\left(\sum_{i=1}^{p-1} q_i' \zeta_p^i\right) \\ &= \sum_{i, j} q_i q_j' \zeta_p^{i + j} \\ \end{align} $$
After computing this, you just reduce all of the $i + j$ modulo $p$, and get rid of any constant terms produced using the $-1 = x + \ldots + x^{p-1}$ relation.
The only kind of tricky operation is multiplicative inversion, that is, computing $1/z$. At this point we must rely on some Galois theory. The Galois group $G = \text{Gal}(K/\mathbb{Q})$ is, in this case, the group $\mathbb{Z}_p^\times$ of multiplicative units of the integers modulo $p$, or the additive group of the integers modulo $p-1$.
$G$ is generated by any nontrivial field automorphism. We can determine a field automorphism by saying where $\zeta_p$ goes, and it can go to any other nontrivial root. Since $p$ is prime, all of the maps given by $\zeta_p \mapsto \zeta_p^i$ for $1 \leq i \leq p-1$ are invertible field automorphisms. Let's just pick $f \in G$ to be $\zeta_p \mapsto \zeta_p^2$, although we could pick any nontrivial image.
If we just multiply all elements in the $G$-orbit of $z$, then we get something that's fixed by all of $G$, so must live in $\mathbb{Q}$. Let $g \in G$, then:
$$g\left(\prod_{h \in G}h(z)\right) = \prod_{h \in G}gh(z) = \prod_{h \in G}h(z)$$
where the last equality is just a relabelling of the elements of $G$.
Thus $\prod_{i=0}^{p-2}f^i(z) = q \in \mathbb{Q}$. And now we have a formula for the inverse of $z$, since:
$$q^{-1}\prod_{i=0}^{p-2}f^i(z) = q^{-1}q = 1$$
But also:
$$q^{-1}\prod_{i=0}^{p-2}f^i(z) = z\left(q^{-1}\prod_{i=1}^{p-2}f^i(z)\right)$$
So finally, in terms of only taking reciprocals of rationals, multiplication, and addition:
$$z^{-1} = q^{-1}\prod_{i=1}^{p-2}f^i(z)$$
Nice! Now we have all of the field axioms.
Other things to explore
How do we represent the list of coefficients? Sparsely with a hash map, densely with an array, maybe sorted with respect to the exponents using a heap?
And how can this work for non-prime $n$? Like I said earlier, the key is to pick a good basis. The obvious one is ${ \zeta_n^i : 0 < i < n, \text{gcd}(n, i) = 1}$, but there is a much nicer basis we can choose, see if you can work it out. I definitely couldn't, but I'll write another blog post about it at some point.
There is a lot of existing work in this field (haha) out there, but particular thanks go to the authors of the GAP computer algebra system for providing an open source implementation of cyclotomic fields.