5 – Computing in number fields

(This is something of a computational aside in my series on algebraic number theory.)

Recall that a number field is a field of the form $\mathbf{Q}(\omega)$, where $\omega$ is a complex number which is algebraic over $\mathbf{Q}$ (that is, is a root of some polynomial in rational coefficients). Then the elements of $\mathbf{Q}(\omega)$ are of the form
\[ a_0 + a_1\omega + a_2\omega^2 + \dots + a_{n-1}\omega^{n-1}, \]
where $n$ is the degree of $\omega$ over $\mathbf{Q}$ (that is, the degree of a monic, irreducible polynomial in rational coefficients which has $\omega$ as a root).

What this means is that an element of a number field can essentially be viewed as a polynomial in rational coefficients, and in turn this means that we can easily perform the operations of addition and multiplication in any number field (indeed, in any field extension, provided we can easily compute in the base field). This post will demonstrate how this is done, both by hand when the number field is manageable, and with a computer using PARI/GP. The standard reference for computational matters in number fields (and many others) is the book by Cohen.

5.1 Field operations in quadratic number fields

Consider a simple number field, say $\mathbf{Q}(\sqrt{2})$. We know that the minimal polynomial of $\sqrt{2}$ over $\mathbf{Q}$ is $x^2-2$ (since it is monic and has $\sqrt{2}$ as a root, and since it is of degree $2$ and has no root in $\mathbf{Q}$, it is irreducible), and so $\mathbf{Q}(\sqrt{2})$ has degree $2$ over $\mathbf{Q}$. In general, an extension of degree $2$ of a field $F$ is called a quadratic extension of $F$, and a quadratic extension of $\mathbf{Q}$ is called a quadratic number field. Thus $\mathbf{Q}(\sqrt{2})$ is a quadratic number field, and its elements are of the form $a+b\sqrt{2}$, with $a, b \in \mathbf{Q}$. Of course, we can easily add or multiply elements of $\mathbf{Q}(\sqrt{2})$ using the usual addition and multiplication.

In PARI, a quadratic number field can be generated using the quadgen() function. This function takes as a parameter the discriminant of the quadratic number field we wish to create. The discriminant of a number field has a complicated form in general, but it is much simpler for quadratic number fields. Namely, the discriminant of $\mathbf{Q}(\sqrt{d})$ is simply $4d$ (yes, PARI uses a diferent form of the discriminant than the one in Wikipedia…), and so the discriminant of $\mathbf{Q}(\sqrt{2})$ is $8$. Also, the output of the function quadgen() which generates the field $\mathbf{Q}(\omega)$ is an object noted w which represents the element $\omega$ of the field. In our example, the output of quadgen() will thus be an exact representation of $\sqrt{2}$ (that is, an object which when squared will exactly equal $2$). Let’s try:

(13:21) gp > w = quadgen(8);
(13:21) gp > w^2

Compare with:

(13:22) gp > sqrt(2)^2

We can also perform all the other field operations, including substraction and division, with the usual notations:

(13:26) gp > (1+w)^50
6882627592338442563 + 4866752642924153522*w
(13:26) gp > 1/w
(13:26) gp > 1/(2+3*w)-25
-176/7 + 3/14*w

5.2 Field operations in general number fields

Of course in a general number field you can always perform the operations manually using the usual rules on the expression of its elements. However, this can quickly become unmanageable, and using a computer becomes necessary. Working with general number fields in PARI is not really complicated, but takes some time to get used to. In the words of Joe Silverman, “The good news about PARI is that it is free and very fast and powerful at doing number theoretic computations. The bad news is that it’s not tremendously user friendly.”

The first thing to do when working in a general number field in PARI is to initialise a nf object, which will represent our number field. This is done using the nfinit() function: it takes as input a polynomial in rational coefficients which is irreducible over $\mathbf{Q}$, and outputs a nf object representing the field $\mathbf{Q}(\omega)$, where $\omega$ is a root of the input polynomial. To continue with our previous example of $\mathbf{Q}(\sqrt{2})$, the command to create it is

(15:01) gp > F = nfinit(x^2-2);

We stored the object representing our field in a variable which we named F, because we will need it for basically anything which involves this field. Now how do we represent an element of the field ? The simplest way is as a polynomial, say 2*x+3, but there is a catch because x can then be either $\sqrt{2}$ or $-\sqrt{2}$. PARI is not concerned with this distinction, because all it needs to know is that $x^2 = 2$, but when you input an element of $F$ you need to decide for yourself whether x is $\sqrt{2}$ or $-\sqrt{2}$, and replace x with that same value in the answer PARI will give you. Now say I want to compute as above $(1+\sqrt{2})^{50}$. I decide that x is $\sqrt{2}$, and I use the function nfeltpow() like this (the function nfbasistoalg() is used only to obtain the result in a nicer form than the default one):

(16:24) gp > nfbasistoalg(F, nfeltpow(F, (1+x), 50))
Mod(4866752642924153522*x + 6882627592338442563, x^2 - 2)

And we do get the same element as above, again expressed as a polynomial in $x = \sqrt{2}$ (modulo $x^2-2$). The functions nfeltadd(), nfeltmul() and nfeltdiv() function in the obvious manner (there is no nfeltsub(), just add a minus sign to substract ^^).

5.3 Extending number fields, and primitive elements

The polynomial $x^2+1$ is certainly irreducible over the field $\mathbf{Q}(\sqrt{2})$ (it has no root in $\mathbf{Q}(\sqrt{2})$ because its roots in $\mathbf{C}$ are imaginary, but all the elements of $\mathbf{Q}(\sqrt{2})$ are real). Thus we can construct the field $(\mathbf{Q}(\sqrt{2}))(i) = \mathbf{Q}(\sqrt{2},i)$. Recall that the primitive element theorem says that there must be an element $\omega$ such that $\mathbf{Q}(\sqrt{2},i) = \mathbf{Q}(\omega)$. $\omega$ is called a primitive element, and surely it would be useful to find it, be it only to be able to give a more concise expression of our field.

It is a general fact that if $E$ is an extension of $F$ of degree $n$ and $F$ is an extension of $G$ of degree $m$, the degree of $E$ over $G$ is $mn$. In our case, this means that the degree of $\mathbf{Q}(\sqrt{2},i)$ over $\mathbf{Q}$ is $2\times 2 = 4$, and so the first thing we know about our primitive element $\omega$ is that it has degree $4$ over $\mathbf{Q}$ (that is, it is a root of an irreducible polynomial of degree $4$ in rational coefficients).

In this case, finding it manually is relatively easy: we notice that $(i+\sqrt{2})^2 = 2i\sqrt{2}+3$ and so $i+\sqrt{2}$ cannot be a root of a polynomial of degree $2$ in rational coefficients. Since certainly $i+\sqrt{2}$ must be in $\mathbf{Q}(i,\sqrt{2})$ (which is a field containing both $i$ and $\sqrt{2}$), we see that $\mathbf{Q}(i+\sqrt{2})$ is an extension of $\mathbf{Q}$ of degree $4$ which is contained in $\mathbf{Q}(i,\sqrt{2})$, and so it must be $\mathbf{Q}(i,\sqrt{2})$ itself, and $i+\sqrt{2}$ is our primitive element.

To find the primitive element using PARI, we have to create one of the “intermediate” fields first, say $\mathbf{Q}(\sqrt{2})$. We create it as above with nfinit() but we must not use the variable x, because we will use it later. So we use, say, t:

(16:10) gp > F = nfinit(t^2-2);

We first use rnfequation() to obtain the minimal polynomial of $\omega$ over $\mathbf{Q}$. rnfequation() takes a base number field $F$ and a polynomial $P$ with coefficients in $F$ which is irreducible over $F$, and returns the minimal polynomial over $\mathbf{Q}$ of a root of $P$:

(16:10) gp > rnfequation(F, x^2+1)
x^4 - 2*x^2 + 9

We can then find the roots of this polynomial in $\mathbf{C}$:

(16:12) gp > polroots(x^4-2*x^2+9)
[1.4142135623730950488016887242096980786 - 1.0000000000000000000000000000000000000*I, 1.4142135623730950488016887242096980786 + 1.0000000000000000000000000000000000000*I, -1.4142135623730950488016887242096980786 + 1.0000000000000000000000000000000000000*I, -1.4142135623730950488016887242096980786 - 1.0000000000000000000000000000000000000*I]~

Dirty, but it works. In general, the numeric value of $\omega$ is rarely needed, all we need is its minimal polynomial over $\mathbf{Q}$, and rnfequation() gives it exactly.

Next: Algebraic integers, unique factorisation, and Fermat’s last theorem

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.