COMPUTATIONAL CLASS FIELD THEORY

H. Cohen

These notes are an expanded writeup of a course that I have given in Ankara, Turkey, in February 1997, at the invitation of the Middle-East Technical University (METU) and of the Institut Culturel Français d’Ankara, both institutions which I heartily thank here, as well as Professor Mehpare Bilhan who was the initiator of my invitation. It follows quite closely a few papers that I have written jointly with my colleagues F. Diaz y Diaz and M. Olivier (see [CoDiOl] and [CoDiOl2]), and hopefully will, much enlarged, be part of a future book.

The prerequisites for this course are a first course in Algebraic Number Theory, including the notions of discriminant, integral basis, Galois group, class group and units. In addition, some knowledge of basic algorithms on matrices is useful, although I have tried to be as self contained as possible. In any case, everything I will need on this and much more is contained in my book [Coh0].

On class field theory itself, the subject matter of these notes, I will assume that nothing is known, and I will present the results that I will need, without proof in general. This is only part of the subject, but since I will concentrate on its algorithmic aspects, I will not need so much. Although class field theory is a very old subject, I am not completely satisfied with the numerous books that I have seen which deal with it. Personally, the best texts I know, in addition to standard references such as Artin-Tate [Art-Tat], are graduate course notes by G. Gras [Gras] and by J. Martinet [Mart], unfortunately not easily available.

Let me give a summary of the contents. The aim of classical global class field theory is to classify Abelian extensions of global fields, in our case of number fields. For this, one defines the notion of ray class groups which are basic objects in class field theory, and we will want to compute explicitly these groups. This in turn leads to quite a number of subquestions which we will have to address first, such as algorithms on finite Abelian groups and the structure of the multiplicative group of elements of the ring of integers of a number field modulo an ideal. These problems and algorithms are interesting in themselves.

As mentioned, one of the remarkable applications of ray class groups is that they will allow us to predict the existence of new number fields from old ones as Abelian extensions. Once these fields are detected using ray class group constructions, the final task which remains is to find explicitly a (relative or absolute) equation for them. To date, the most successful method to do this (which is in fact the standard method also used to prove the existence theorems in global class field theory) is Kummer theory, which we will explain in great detail in its algorithmic aspects.

Any tool which allows explicit constructions of new interesting mathematical objects is extremely valuable, and this is the case here. Thus, we will for example be able to compute number fields with very small discriminants, and also tables of certain classes of number fields. Many examples will be given.

1. A review of results in algebraic number theory

In this section, we group the basic definitions and results that we need coming from algebraic number theory. However, if the reader is not familiar with these notions, he is urged to read in detail any good textbook on the subject.

Recall that a number field is a finite extension of the field ℚ of rational numbers. An algebraic number is a root of a non-zero polynomial with rational coefficients. The set of all such polynomials is an ideal in ℚ[X], thus is a principal ideal generated by a unique monic (i.e. with leading coefficient 1) polynomial, which we will call the minimal polynomial of the algebraic number.

Any element of a number field is an algebraic number, hence we will consider all our number fields to be subfields of some algebraic closure \overline{ℚ} of ℚ, and we will in practice choose \overline{ℚ} to be the algebraic closure of ℚ in ℂ, although other perfectly reasonable choices can be made, such as the algebraic closure of ℚ in ℂ_{p}, the completion of the algebraic closure of ℚ_{p}.

The degree of a number field K is the dimension of K as a ℚ-vector space, and is denoted by [K : ℚ]. A number field of degree n has n field embeddings into ℂ, r_{1} real ones and 2r_{2} non-real (or complex) ones, since one can compose any non-real embedding with complex conjugation to obtain another one. These embeddings will always be numbered σ_{1}, …, σ_{r_{1}} for the real embeddings, σ_{r_{1}+1}, …, σ_{r_{1}+r_{2}} for r_{2} non-real embeddings no two of which differ by complex conjugation, and finally σ_{r_{1}+r_{2}+1}, …, σ_{r_{1}+2r_{2}} with σ_{r_{1}+r_{2}+i} = \overline{σ_{r_{1}+i}}. The pair (r_{1}, r_{2}) will be called the signature of K.

If K is as above and if α ∈ K, the characteristic polynomial of α in K is the polynomial

C_{α}(X) = ∏_{i=1}^{n}(X − σ_{i}(α)) .

By Galois theory, this is a polynomial with rational coefficients, and it is a power (not only a multiple) of the minimal polynomial of α. In particular, if

C_{α}(X) = X^{n} − a_{1}X^{n−1} + ⋯ + (−1)^{n}a_{n} ,

then a_{1} = ∑_{1≤i≤n} σ_{i}(α) is called the trace of α in K and denoted by Tr_{K/ℚ}(α), and a_{n} = ∏_{1≤i≤n} σ_{i}(α) is called the norm of α in K and denoted N_{K/ℚ}(α). Note that these are related, but not equal in general, to the absolute trace and norm of α obained in the same way from the minimal polynomial of α instead of the characteristic polynomial.

An algebraic integer is an algebraic number which is a root of a polynomial with integer coefficients and which in addition is monic, in other words, an algebraic number whose minimal polynomial (which by definition is monic) has integer coefficients. The set of algebraic integers in a number field K is denoted by ℤ_{K}. The characteristic polynomial of an algebraic integer being a power of the minimal polynomial, also has integer coefficients.

The set ℤ_{K} is a (commutative) ring. This means in particular that the sum, difference and product of algebraic integers is again an algebraic integer. Note that, although easy, this result is not completely trivial.

Exercise. Using the notion of resultant (see [Coh0] and Definition 2.1 below), compute a monic polynomial whose root is the sum (resp. the product, resp. the quotient) of two algebraic numbers, knowing the minimal polynomials of these numbers. The solution will be given below.

Clearly, since ℤ_{K} ⊂ K, the ring ℤ_{K} is an integral domain. However, it is much more than that: it is a Dedekind domain.

Temporarily, let R be a commutative integral domain (we will specialize to R = ℤ_{K} later). Recall that an ideal 𝔭 is a prime ideal if 𝔭 is an ideal different from R such that R/𝔭 is an integral domain. Equivalently, 𝔭 is an ideal different from R such that the condition xy ∈ 𝔭 (for x and y in R) is equivalent to x ∈ 𝔭 or y ∈ 𝔭.

An ideal 𝔪 is a maximal ideal if 𝔪 is different from R and if R/𝔪 is a field. It is clear that every maximal ideal is a prime ideal. The converse is in general false. However, in a Dedekind domain, it is almost true: apart from the ideal (0), which will always be tacitly excluded, every prime ideal is a maximal ideal.

If 𝔞 and 𝔟 are two ideals, the ideal product is the smallest ideal containing all elements of the form ab with a ∈ 𝔞 and b ∈ 𝔟. Thus, it is the set of all elements of the form ∑_{i} a_{i}b_{i} (finite sum) with a_{i} ∈ 𝔞 and b_{i} ∈ 𝔟. The ideal R is the unit element for this multiplication. To be able to get a group (at least sometimes), we generalize the notion of ideal. Let K be the quotient field of R. We say that 𝔞 is a fractional ideal if 𝔞 ⊂ K and if there exists d ∈ R, d ≠ 0 such that d𝔞 is a non-zero ideal of R. To distinguish true ideals from fractional ideals, we call the former integral ideals. They are characterized by the possibility to take d = 1, i.e. by 𝔞 ⊂ R.

We say that an ideal 𝔞 (fractional or not) is invertible if there exists a (fractional) ideal 𝔟 such that 𝔞𝔟 = R. If 𝔞 is invertible, then its inverse 𝔟 is unique and necessarily equal to 𝔟 = {x ∈ K, x𝔞 ⊂ R}.

We can now come to the definition of Dedekind domains. We say that the domain R is a Dedekind domain if it is a Noetherian integrally closed domain in which every non-zero prime ideal is maximal (recall that a commutative ring is Noetherian if any ascending chain of ideals is finite, or equivalently if every ideal is finitely generated, and that a domain R with field of fractions K is integrally closed if any element of K which is the root of a monic polynomial with coefficients in R belongs in fact to R).

This definition may look rather abstract, but what we will need about Dedekind domains is entirely summarized in the perhaps more concrete theorem below.

Theorem 1.1. Let R be a Dedekind domain.

(1) Every (non-zero) prime ideal of R is maximal.

(2) Every fractional ideal of R is invertible.

(3) Any fractional ideal of R has a unique finite factorization into prime ideals (of course up to permutation of the terms)

I = ∏_{𝔭} 𝔭^{v_{𝔭}(I)}

and v_{𝔭}(I) ∈ ℤ is called the 𝔭-adic valuation of I at 𝔭.

(4) Let I be a fractional ideal of R and a ∈ I with a ≠ 0. There exists b ∈ I such that I = aR + bR (i.e. every ideal is in fact generated by at most two elements, and one can choose the first one arbitrarily as long as it is non-zero).

(5) (Approximation theorem). Let S be a finite family of prime ideals, and for each 𝔭 ∈ S let u_{𝔭} ∈ ℤ be an integer. There exists an element x ∈ K^{∗} such that v_{𝔭}(x) = u_{𝔭} for all 𝔭 ∈ S, and v_{𝔭}(x) ≥ 0 for all 𝔭 ∉ S (note that we write v_{𝔭}(x) for v_{𝔭}(xR) the principal ideal generated by x).

The special properties of the ring ℤ_{K} are summarized in the following proposition.

Proposition 1.2.

(1) The ring ℤ_{K} is a Dedekind domain (hence all the above properties apply).

(2) ℤ_{K} (and more generally any ideal of ℤ_{K}) is a free ℤ-module of rank equal to [K : ℚ] = n.

(3) All the non-zero integral ideals 𝔞 of ℤ_{K} (and in particular all the maximal ideals of ℤ_{K}) are of finite index in ℤ_{K} (i.e. ℤ_{K}/𝔞 is a finite ring). In particular all the residue fields ℤ_{K}/𝔭 are finite, for 𝔭 a non-zero prime ideal.

Remark. An order in K is a subring of K which is a free ℤ-module of rank [K : ℚ] = n. It is easy to show that any order of K is a subring of ℤ_{K} of finite index, hence that ℤ_{K} is the maximal order. An order R which is not maximal cannot be integrally closed by definition of ℤ_{K}, hence is not a Dedekind domain. Some properties are preserved. For instance, every non-zero prime ideal is maximal, the integral ideals of R are of finite index in R, and in particular the residue fields are finite. On the other hand, the crucial properties of invertibility and of decomposition into a product of prime ideals are definitely false if R is not the maximal order.

Exercise. Let R be an order, and set f = [ℤ_{K} : R].

(1) Show that if 𝔞 is an ideal of R coprime to f (i.e. 𝔞 + fR = R) then 𝔞 is invertible.

(2) Deduce from this that the set of ideals of the form 𝔞𝔟^{−1} with 𝔞 and 𝔟 coprime to f forms a group, and that every such ideal has a unique decomposition into prime ideals coprime to f.

(3) Show that if all ideals of R are invertible, then R = ℤ_{K}.

If 𝔞 is an integral ideal in ℤ_{K}, we define the norm N (𝔞) of 𝔞 by N (𝔞) = [ℤ_{K} : 𝔞], which is finite by the above proposition. We have the following result.

Proposition 1.3.

(1) If 𝔞 and 𝔟 are integral ideals of ℤ_{K}, then N (𝔞𝔟) = N (𝔞) N (𝔟).

(2) If α ∈ ℤ_{K}, then N (αℤ_{K}) = | N_{K/ℚ}(α)| (beware of this absolute value sign).

Note that this proposition is false if we consider ideals of an order R which is not maximal.

Using this proposition, we can now define the norm of a fractional ideal 𝔞 as follows. We write 𝔞 = 𝔟𝔠^{−1} with 𝔟 and 𝔠 integral, and we set N (𝔞) = N (𝔟)/ N (𝔠).

The above proposition shows that this is independent of the choice of the integral ideals 𝔟 and 𝔠, and the two statements of the proposition are now valid more generally for fractional ideals.

An integral basis of K is a ℤ-basis of ℤ_{K}, i.e. it is an n-tuple (ω_{1}, …, ω_{n}) of elements of ℤ_{K} such that any element x of ℤ_{K} (i.e. every algebraic integer of K) can be written in a unique way x = x_{1}ω_{1} + ⋯ + x_{n}ω_{n} with x_{i} ∈ ℤ. We will write this concisely as

ℤ_{K} = ⨁_{i=1}^{n} ℤω_{i} .

By the proposition above, an integral basis always exists. If (ω_{1}, …, ω_{n}) is an integral basis, then (ω′_{1}, …, ω′_{n}) is an integral basis if and only if the n × n matrix giving the ω′_{j} in terms of the ω_{i} is in GL_{n}(ℤ), i.e. has integer coefficients and determinant equal to ±1. From this, the following proposition easily follows.

Proposition 1.4. Let K be a number field of degree n, (ω_{1}, …, ω_{n}) an integral basis, and σ_{i} (1 ≤ i ≤ n) the n embeddings of K into ℂ. Let M = (m_{i,j}) be the n × n matrix defined by m_{i,j} = σ_{i}(ω_{j}), and let T = (t_{i,j}) be the n × n matrix defined by t_{i,j} = Tr_{K/ℚ}(ω_{i}ω_{j}). Then T = M^{t} · M, and

d(K) = det(T) = det(M)^{2}

is independent of the chosen integral basis, and called the discriminant of the number field K.

Note that, if the number field K is defined as K = ℚ(θ) where θ is an algebraic integer whose minimal polynomial is T (X) ∈ ℤ[X], then if we set f = [ℤ_{K} : ℤ[θ]], it is easy to show that disc(T) = d(K)f^{2}, which gives only a small number of possibilities for d(K) knowing disc(T) (for example d(K) = disc(T) if disc(T) is squarefree or equal to 4 times a squarefree number congruent to 2 or 3 modulo 4).

There are at least two reasons for the importance of the notion of discriminant. First, it is (together with the degree n and the signature (r_{1}, r_{2})) an invariant of the number field K, i.e. it does not depend on the way the field is represented up to isomorphism. Second, and much more importantly, very often it allows to distinguish (discriminate!) between non-isomorphic number fields. It does happen that non-isomorphic number fields may have the same discriminant, but this is rather rare. Along these lines, we have the following very important theorem.

Theorem 1.5.

(1) (Hermite) The number of isomorphism classes of number fields K such that |d(K)| ≤ x is finite.

(2) The field ℚ is the only number field such that |d(K)| ≤ 1.

Remark. Our knowledge on the number of isomorphism classes of number fields K such that |d(K)| ≤ x is very small. Call N(x) this number, and N_{r_{1},r_{2}}(x) when we restrict to a given signature (r_{1}, r_{2}). Then in degree 1, the theorem above says that N_{1,0}(x) = 1 for x ≥ 1. In degree 2, it is easily shown that

N_{2,0}(x) ∼ \frac{x}{2ζ(2)} and N_{0,1}(x) ∼ \frac{x}{2ζ(2)} .

In degree 3, it is a difficult theorem of Davenport-Heilbronn that

N_{3,0}(x) ∼ \frac{x}{12ζ(3)} and N_{1,1}(x) ∼ \frac{x}{4ζ(3)} .

Here ζ(s) is the Riemann ζ function, and we have of course ζ(2) = π^{2}/6.

In higher degrees, lower bounds are known, but the known upper bounds are certainly much too large. In fact, it is quite reasonable to conjecture that N_{r_{1},r_{2}}(x) ∼ C_{r_{1},r_{2}} · x for some positive constant C_{r_{1},r_{2}}, and it is even possible that N(x) ∼ C · x for some constant C.

We can also construct an infinite family of invariants of a number field K in the following way. Let p be an ordinary prime number. As any other ideal of K, the principal ideal pℤ_{K} has a canonical factorization into prime ideals

pℤ_{K} = ∏_{i=1}^{g} 𝔭_{i}^{e_{i}} .

The positive integer e_{i} is called the ramification index of the ideal 𝔭_{i} over p, and we say that 𝔭_{i} is ramified if e_{i} ≥ 2. The prime number p itself is said to ramify if at least one of the e_{i} is greater than or equal to 2. In addition, ℤ_{K}/𝔭_{i} is a ℤ/pℤ-vector space of finite dimension denoted by f_{i} and called the residual index of 𝔭_{i} over p. We have |ℤ_{K}/𝔭_{i}| = p^{f_{i}} and the formula

∑_{i=1}^{g} e_{i}f_{i} = n .

These integers (e_{i}, f_{i})_{1≤i≤g} give for all prime numbers p invariants of the number field K. They can conveniently be put together in an analytic function in the following way.

Proposition 1.6. Keep the notation above. Set

ζ_{K}(s) = ∑_{𝔞} N (𝔞)^{−s} .

where the sum is over all (non-zero) integral ideals of ℤ_{K}. Then this series converges absolutely for Re(s) > 1 and uniformly for Re(s) > 1 + ϵ (hence defines an analytic function for Re(s) > 1), and we have

ζ_{K}(s) = ∏_{𝔭}(1 − N (𝔭)^{−s})^{−1} = ∏_{p} ∏_{𝔭_{i}|p}(1 − p^{−f_{i}s})^{−1} ,

where the first product is over all non-zero prime ideals of ℤ_{K}, and the second is over all prime numbers p.

We will need this zeta function later, together with its analytic continuation, but for now we note that it groups a number of the invariants that we have studied. In fact, although apparently only the f_{i} are involved, it can be shown that it determines uniquely not only the f_{i}, but also the degree, the signature (r_{1}, r_{2}) and the discriminant d(K) as well as other quantities such as the product of the class number and the regulator (see below), but not the class number or the regulator individually.

Thus, this function is a very strong invariant of K, but it was proved in 1920 by Bauer that it still does not determine the number field K up to isomorphism, although it does up to degree 6. Many explicit families of examples are now known.

Although invariants such as the discriminant are not so well understood (see the conjectures mentioned above about N(x)), we now come to important invariants which are of a higher level of difficulty, and which are even less understood. These are invariants linked to ideal classes and units.

Let I be the set of all (non-zero) fractional ideals of K. By the results seen above, we know that I is a multiplicative group. The subset P of principal ideals, i.e. ideals of the form αℤ_{K} for α ∈ K^{∗}, is evidently a subgroup of I. The quotient group I/P is called the ideal class group, or simply the class group of K, and denoted Cl(K).

Two ideals 𝔞 and 𝔟 are thus in the same ideal class if and only if there exists α ∈ K^{∗} such that 𝔟 = α𝔞. In particular, the ring ℤ_{K} is a principal ideal domain (PID), i.e. every ideal is principal, if and only if the class group Cl(K) is trivial (reduced to the identity element). Every PID is a unique factorization domain (UFD), and one can show that, in the case of number fields, the converse is also true, so ℤ_{K} is a UFD if and only if its class group is trivial. In abstract terms, Cl(K) is the obstruction to unique factorization.

Now a generator of a principal ideal is not unique. We evidently have αℤ_{K} = βℤ_{K} if and only if β = uα with u ∈ ℤ_{K} such that u^{−1} ∈ ℤ_{K}. Such elements u ∈ ℤ_{K} which are invertible in ℤ_{K} are called units of ℤ_{K}. The set of units of ℤ_{K} forms a multiplicative group, which we denote by U(K), which we will call the unit group of K. An important characterization of units is that they are the elements of ℤ_{K} of norm equal to ±1, or in other words algebraic numbers whose minimal polynomial has integral coefficients, is monic and constant term equal to ±1.

It is convenient to put all these groups, as well as others, into diagrams involving exact sequences. For the sake of completeness, we give the definition (only in the case of Abelian groups, but it can be extended trivially to cases where images and kernels are well defined, i.e. to Abelian categories).

Definition 1.7. Let A, B, C be three Abelian groups, and let f (resp. g) be a group homomorphism from A to B (resp. from B to C). We say that the sequence

A ⟶^{f} B ⟶^{g} C

is an exact sequence if Ker(g) = Im(f) (which implies, but is stronger than, g ∘ f = 0). More generally, if A_{i} are Abelian groups and f_{i} group homomorphisms from A_{i} to A_{i+1}, we say that the sequence

… ⟶ A_{i−1} ⟶^{f_{i−1}} A_{i} ⟶^{f_{i}} A_{i+1} ⟶ …

is exact if Ker(f_{i}) = Im(f_{i−1}) for all i.

As important special cases, we remark that a sequence 0 ⟶ A ⟶^{f} B is exact if and only if f is injective (one to one), that a sequence B ⟶^{g} C ⟶ 0 is exact if and only if g is sujective (onto), and that a sequence

0 ⟶ A ⟶^{f} B ⟶^{g} C ⟶ 0

is exact if and only if the maps f and g induce an isomorphism from C to B/f(A).

To come back to our class group and unit group, we see that the definition of class group is embodied in the statement that the following sequence is exact:

1 ⟶ P ⟶ I ⟶ Cl(K) ⟶ 1 .

Note the use of 1 instead of 0 to denote the trivial group, since our groups are written multiplicatively.

Similarly, the definition of the unit group is embodied in the statement that the following sequence is exact:

1 ⟶ U(K) ⟶ K^{∗} ⟶ P ⟶ 1 .

These two exact sequences can be put together as two sides of a square (a 3 × 3 commutative diagram of exact sequences) involving generalizations to ideles of the above notions, but we will not need this, and refer only to [Lang] for the curious reader.

The main theorem concerning Cl(K) and U(K) (which should properly be viewed as a single theorem in the context of ideles), due to Dirichlet, is the following.

Theorem 1.8. Let K be a number field of signature (r_{1}, r_{2}), and as above let Cl(K) be its class group, and U(K) be its unit group.

(1) The group Cl(K) is a finite (Abelian) group, whose cardinality is denoted by h(K).

(2) The group U(K) is a finitely generated Abelian group of rank r = r_{1}+r_{2}−1. More precisely, U(K) = U_{tors} × U_{free} where U_{tors} is a finite cyclic group of a certain even order w(K) generated by a primitive w(K)-th root of unity in K, and U_{free} is a free Abelian group of rank r generated by certain units ϵ_{1}, …,ϵ_{r}.

Even though more than a century old, the proof of this theorem is quite difficult. In fact, if one replaces the complex embeddings by p-adic ones, the statement that the group of units has rank r_{1} + r_{2} − 1 is an important conjecture due to Leopoldt, which to this day is proved only in certain cases, for example when K/ℚ is an Abelian extension.

To reformulate the statement about U(K) even more explicitly, we can say that there exists a primitive w(K)-th root of unity ζ and units ϵ_{1}, …,ϵ_{r} (with r = r_{1} + r_{2} − 1) such that any unit u ∈ U(K) can be written in a unique way as

u = ζ^{x_{0}}ϵ_{1}^{x_{1}} … ϵ_{r}^{x_{r}}

with x_{i} ∈ ℤ and 0 ≤ x_{0} < w(K).

Note that w(K), which is equal to the number of roots of unity belonging to K, is a new invariant of K.

A system (ϵ_{1}, …, ϵ_{r}) of units as above is called a fundamental system of units. Exactly as for the definition of the discriminant as an invariant of integral bases, one can define an invariant attached to a fundamental system of units as follows. Let as usual σ_{i} be the embeddings of K into ℂ. Write n_{i} = 1 if i corresponds to a real embedding (i.e. 1 ≤ i ≤ r_{1} if we use the usual ordering), and n_{i} = 2 otherwise. Consider the r_{1}+r_{2} matrix Z = (z_{i,j}) defined as follows. For j < r_{1}+r_{2}, z_{i,j} = n_{i} log |σ_{i}(ϵ_{j})| while for j = r_{1} + r_{2}, z_{i,j} = n_{i}. Then R(K) = | det(Z)|/n is independent of the choice of fundamental units and of the ordering of the σ_{i}, and is called the regulator of the number field K. It measures the volume of the lattice spanned by the logarithmic embedding of the fundamental units, which we can call the logarithmic lattice of the fundamental units. Since the norm of a unit is equal to ±1, it follows that the sum of the rows of the matrix Z is equal to [0, …, 0, n], hence the regulator can also be defined as the absolute value of any r × r subdeterminant of Z obtained by taking the first r = r_{1} + r_{2} − 1 columns and any r rows.

Note that we can also define in the same way the regulator of any system of r_{1} + r_{2} − 1 units, and it is easy to see that such a regulator will always be an integral multiple of R(K), more precisely it will be equal to R(K) times the index of the logarithmic lattice formed by these units with respect to the logarithmic lattice formed by the fundamental units if the units are independent, and zero otherwise.

We can now state the main theorem that we will use about the Dedekind ζ function defined above.

Theorem 1.9. Let K be a number field of degree n and signature (r_{1}, r_{2}), and denote as usual by d(K), h(K), R(K) and w(K) the discriminant, class number, regulator and number of roots of unity of K.

(1) (Analytic continuation) The Dedekind ζ function ζ_{K}(s) has an analytic continuation to the whole complex plane, and it is a meromorphic function with a unique pole, at s = 1, which is simple.

(2) (Functional equation) We have the following functional equation. Set γ(s) = π^{−s/2}Γ(s/2) and

Λ(s) = |d(K)|^{s/2}γ(s)^{r_{1}+r_{2}}γ(s + 1)^{r_{2}}ζ_{K}(s) .

Then for all s,

Λ(1 − s) = Λ(s) .

(3) (Residue) The residue of ζ_{K}(s) at s = 1 is equal to

lim_{s→1}(s − 1)ζ_{K}(s) = 2^{r_{1}}(2π)^{r_{2}} \frac{h(K)R(K)}{w(K)\sqrt{|d(K)|}} .

Equivalently, by the functional equation, if r = r_{1} + r_{2} − 1 is the unit rank, then ζ_{K}(s) has a zero of order r at s = 0 and

lim_{s→0} s^{−r}ζ_{K}(s) = −h(K)R(K)/w(K) .

2. Computational aspects of basic algebraic number theory

The main references for this subject are [Coh0] and [Poh-Zas].

All the above notions and invariants must be put into an algorithmic setting and programmed. In this section, we will briefly explain the algorithmic methods which are used. As for the programs, we strongly urge the reader to get the only two programs which are tailor-made for number-theoretic applications, and which are free of charge. The first one is KANT, from the Pohst group in Berlin, available by anonymous ftp from

                        ftp.math.tu-berlin.de

The second one is PARI/GP, from the author’s group in Bordeaux, available by anonymous ftp for example from

                      megrez.math.u-bordeaux.fr

At both of these sites, a lot of additional number-theoretical information and large tables are also available.

We briefly describe in turn all the algorithms which are involved, with the corresponding reference in [Coh0].

2.1. Description of number fields

A number field K can be given in several ways. The most frequent is to give K as an extension of a smaller field, hence inductively as ℚ(θ_{1}, …, θ_{m}). By the primitive element theorem, there exists a ℤ-linear combination θ of the θ_{i} such that K = ℚ(θ). We will usually represent a number field in this manner. Note, however, that it is not always a good idea to do this, and evidently is a bad idea when dealing with relative extensions. In this last case, we consider instead that a base field k is given, and that K = k(θ).

How is θ itself given? The natural (but once again not always satisfactory) answer, is as a root of its minimal polynomial T (X) ∈ ℚ[X]. Replacing θ by some integer multiple of θ, we can in fact assume that θ is an algebraic integer, hence that T (X) ∈ ℤ[X] and monic. Let n be the degree of the polynomial T. Then the degree [K : ℚ] of K is equal to n since (1, θ, …, θ^{n−1}) is a ℚ-basis of K. But the polynomial T has n distinct roots in any algebraic closed field. Since we always consider our number fields to be embedded in ℂ, we thus have n roots in ℂ, any one of which can be chosen for θ.

We now have two options. Either we are content with dealing with number fields up to isomorphism. In this case, it is not necessary to specify which root of T is taken, since all the number fields ℚ(θ_{i}) for all the roots θ_{i} of T in ℂ are isomorphic (in fact conjugate by the embeddings σ_{i}). We will in this case simply say by abuse of language that the number field K is given by the polynomial T (abstractly K = ℚ[X]/T (X)ℚ[X] for example).

In certain cases, however, we cannot be content only with number fields up to isomorphism. Consider for example the case of the compositum of two number fields K_{1} and K_{2} considered as subfields of ℂ. By definition, this is the smallest subfield of ℂ containing K_{1} and K_{2}, and is denoted K_{1}K_{2} (as for ideal products, it is the set of linear combinations of products of an element of K_{1} by an element of K_{2}). Then this depends on the specific number fields K_{1} and K_{2}, and not only on their isomorphism class. To take a specific example, let K_{1} and K_{2} both be defined by the polynomial T (X) = X^{3} −2. Then if we choose θ_{1} = \sqrt[3]{2}, θ_{2} = \sqrt[3]{2}, we have trivially K_{1}K_{2} = K_{1} the same cubic field, while if we choose the same θ_{1} but θ_{2} = j\sqrt[3]{2} where j = exp(2iπ/3) is a primitive cube root of unity satisfying j^{2} + j + 1 = 0, then K = K_{1}K_{2} is a number field of degree 6, and a quick computation shows that U(X) = X^{6} − 3X^{5} + 5X^{3} − 3X + 1 is a defining equation.

In the situations considered in this course, the isomorphism class of the number field suffices, hence, although I repeat that it is has disadavantages, we will always represent a number field by a monic defining polynomial with coefficients in ℤ, or sometimes with coefficients in the ring of integers of a base field.

Now among all the polynomials (of course infinite in number) defining a given number field K, some are better than others. Evidently, we want to privilege a question of “size”, but it is not clear which size to take into account. For example, a natural size would be some norm (the L^{1}, L^{2} or L^{∞} norm) on the coefficients of the polynomial. Another size would be on the discriminant of the polynomial, since we know that the it is a square multiple of the discriminant of the field d(K).

These two examples are perfectly sensible choices in theory, but unfortunately there are no known efficient algorithmic methods leading to the computation of “small” polynomials for these sizes. Instead, one must take still another notion, the L^{2}-norm of the roots of the polynomial instead of the coefficients. This is because, as I will explain below, we do have in this case reasonably efficient algorithmic methods to find small polynomials.

Of course, intuitively all the different notions of sizes are related, so we can hope that a small polynomial for the roots will also be small for the coefficients and for the discriminant, although perhaps not as good as it could be. This is indeed the case, although the coefficients must be weighted in a suitable manner. More precisely, one can show (exercise) that if S is the square of the L^{2}-norm of the roots (i.e. the sum of the square of the norms of the roots), then if T (X) = ∑_{0≤k≤n} a_{k}X^{k}, we have

|a_{n−k}| ≤ \binom{n}{k} (\frac{S}{n} )^{k/2} .

The algorithm which reduces considerably the size of the polynomials in this sense has been nicknamed by us the Polred algorithm, and is based on one of the most important algorithms of all mathematics, which is used in many other branches than number theory, the LLL algorithm, named for its inventors A. K. Lenstra, H. W. Lenstra and L. Lovász. We will in fact see several applications of the LLL algorithm in the sequel.

Without giving any details (see [Coh0] Section 2.6, and in particular Algorithm 2.6.3) the LLL algorithm finds vectors in a lattice which are “small” with respect to a given positive definite quadratic form. It does not always find the smallest non-zero vectors (this problem is believed to be intractable, more precisely NPcomplete), but the quality of the vectors which are found is sufficient to make them very useful. In addition, and this is also one of its main features, the LLL algorithm runs in polynomial time, i.e. is quite fast (although not as fast as the Hermite and Smith algorithms which we will see below).

For our situation, we take as lattice the set ℤ_{K} of algebraic integers, and as quadratic form the sum of the squares of the norms of the embeddings by the σ_{i} (it is easy to see that it is indeed a quadratic form). This form is called the T_{2}-norm.

To give a (not quite random, but not contrived, either) example, let

T (X) = X^{5} + 3021X^{4} − 786303X^{3} − 6826636057X^{2} − 546603588746X + 3853890514072057 .

An application of the polred algorithm gives quite quickly that the number field defined by T (X) is also defined by

S(X) = X^{5} − 2X^{4} − 13X^{3} + 37X^{2} − 21X − 1 ,

and this is evidently a much better polynomial than T (X), whatever notion of size is chosen.

Another question can be raised at this point. Given two number fields K_{1} and K_{2} given by two polynomials T_{1} and T_{2}, how can we recognize whether these fields are isomorphic or not? A standard answer is to factor the polynomial T_{1}(X) in the ring K_{2}[X] (or conversely). Then the fields are isomorphic if and only if there exists a linear factor. However, factoring in number fields is a costly operation (see for example [Coh0] Algorithm 3.6.4). Another possibility, which is the best if the fieds are believed to be isomorphic, but which needs detailed error analysis to be used to prove that they are not, is once again to use the LLL algorithm. By looking at degree or discriminants, one can readily dispatch some impossibilities. If what remains seems compatible, then if θ_{1} (resp. θ_{2}) is a complex root of T_{1} (resp. T_{2}), then K_{1} and K_{2} are isomorphic if and only if there exists integers d and x_{i} not all zero such that

dθ_{2} = x_{0} + x_{1}θ_{1} ⋯ + x_{n−1}θ_{1}^{n−1}

where n is the common degree of K_{1} and K_{2} over ℚ. This is another very important application of the LLL algorithm: it allows quite rapidly to find integer relations between complex numbers (see [Coh0] Algorithm 2.7.4). For more details on the field isomorphism problem, see [Coh0], Section 4.5.

There is also the problem of computing the complex roots θ_{1} and θ_{2} to sufficient numerical accuracy. This is a very difficult problem of numerical analysis, which has recently been solved by A. Schönage and implemented by X. Gourdon. A simple-minded but quite reasonable method is given in [Coh0], Algorithm 3.6.6.

A related and in general better method is to use, instead of complex roots, p-adic roots in a suitable p-adic field ℚ_{p}. For this, the prime p must be such that p does not divide the discriminants of T_{1} and T_{2}, and such that T_{1} and T_{2} have a root modulo p. Such a p is easy to find in practice, and finding a root in ℚ_{p} to any desired approximation is then a simple Hensel lifting of the root modulo p. The LLL algorithm can easily be adapted to finding relations between p-adic numbers.

2.2. Representation and computation on algebraic numbers

Initially, before any number field is given, algebraic numbers are usually simply given by their minimal polynomial, and some way of determining which root of the polynomial one is dealing with (if necessary, it is often not necessary to do so). It is possible in this form to do the usual operations (addition/subtraction, multiplication/division) using the theory and practice of resultants.

Let A(X) and B(X) are two polynomials with coefficients in some integral domain D with field of fractions K. Write A(X) = ∑_{0≤i≤m} a_{i}X^{i} and B(X) = ∑_{0≤j≤n} b_{j}X^{j} with a_{m} and b_{n} not equal to zero. Then recall the following definition.

Definition 2.1. Keep the above notation, and let α_{i} (resp. β_{j}) be the roots of A (resp. B) in some algebraic closure of K. We define the resultant of A and B by the following equivalent formulas

R(A, B) = a_{m}^{n} ∏_{i} B(α_{i}) = (−1)^{mn}b_{n}^{m} ∏_{j} A(β_{j}) = a_{m}^{n}b_{n}^{m} ∏_{i,j}(α_{i} − β_{j})

where it is understood that the indices i go from 1 to m and the indices j from 1 to n. We also define the discriminant of the polynomial A by the following equivalent formulas

disc(A) = (−1)^{m(m−1)/2}R(A, A′)/a_{m} = a_{m}^{m−1+deg(A′)} ∏_{1≤i<j≤m}(α_{i} − α_{j})^{2}

where A′ is the derivative of A.

Note that deg(A′) is usually equal to m − 1, but it can be lower in positive characteristic.

It is not difficult to prove that R(A, B) and disc(A) still belong to the integral domain D. More importantly, they can be computed efficiently using methods very close to the Euclidean algorithm, either the subresultant algorithm (see [Coh0], Algorithm 3.3.7) or by using modular methods.

Coming back to elements of number fields, assume that the minimal polynomial of α is A(X) ∈ ℚ[X] and that of β is B(X) ∈ ℚ[X]. Consider the resultant R_{Y} (A(X − Y), B(Y)), where R_{Y} means that it is a resultant in Y, i.e. where the polynomials are considered to have coefficients in the ring ℚ[X], i.e. we consider X as a parameter in the computation of the resultant. Thus, the result is a polynomial S(X) in X, and the very definition of resultant shows that α + β is a root of S(X), from which it is not too difficult to obtain the minimal polynomial by factoring S. Incidentally, the factoring problem (in 𝔽_{q}[X] for a finite field 𝔽_{q}, in ℚ[X] or in K[X] for some number field K), is a highly non-trivial problem which is still actively being pursued. I refer for example to [Coh0], Sections 3.4, 3.5 and 3.6, but there are numerous other references.

Similar formulas exist for the difference of α and β (R_{Y} (A(X + Y), B(Y))), for the product (R_{Y} (Y^{m}A(X/Y), B(Y))) and for the quotient (R_{Y} (A(XY), B(Y))).

Usually, however, algebraic numbers are given as elements of a fixed number field K. Let K be defined as K = ℚ(θ) where the minimal polynomial of θ is T (X), a polynomial of degree n. Then an element α of K can be represented in the form α = A(θ) for some polynomial A(X) ∈ ℚ[X] of degree strictly less than n. Performing the standard operations on this representation corresponds to doing the same operations on the corresponding polynomials, as long as we do not forget to reduce modulo the polynomial T (X) to get back down to a polynomial of degree less than n. On the other hand, computing the minimal polynomial or the characteristic polynomial of α is slightly less trivial. Once again, it is a resultant computation. It is not difficult to show that the characteristic polynomial of α is equal to R_{Y} (T (Y), X − A(Y)). In other words, if σ_{i} are the embeddings of K into ℂ, then

C_{α}(X) = ∏_{1≤i≤n}(X − σ_{i}(α)) = R_{Y} (T (Y), X − A(Y)) .

An important special case of this formula is the formula for computing the norm of α, since the above gives

N_{K/ℚ}(α) = R(T (X), A(X)) .

Obtaining the minimal polynomial from the characteristic polynomial is easy once one remarks that the characteristic polynomial C(X) is a power of the minimal polynomial M(X), thus M(X) = C(X)/(C(X), C′(X)) where (C(X), C′(X)) denotes the monic GCD of C(X) with its derivative. Computing the trace Tr(α) can be done as above, but in a much simpler manner.

2.3. Computing the basic invariants

What I call the basic invariants are the signature, the discriminant and an integral basis, and the decomposition of prime numbers.

To compute the signature, i.e. the number of real and complex roots of the defining polynomial T (X), we could compute numerically the roots. This would have two disadvantages. First, it is very slow, and second, even once the roots computed to a given accuracy, we would have to prove that a given root is real and not only very close to the real line. This is something that, except in special circumstances, a computer cannot do: prove that an inexact number is exactly equal to zero.

In practice, we use a classical algorithm due to Sturm, which once again is similar to the Euclidean algorithm on T (X) and T′(X). See [Coh0] Algorithm 4.1.11 for an implementation.

Computing the discriminant and an integral basis is a much more difficult problem and was a very important problem in the early 1970’s. It has now been solved quite reasonably, thanks mainly to the efforts of Hans Zassenhaus.

Once proceeds as follows. We can of course assume that T (X) is a monic polynomial with integer coefficients, hence that, if K = ℚ(θ) where θ is a root of T, then θ is an algebraic integer so ℤ[θ] ⊂ ℤ_{K}. If we set f = [ℤ_{K} : ℤ[θ]], we have mentioned above that disc(T) = d(K)f^{2}. We start by computing disc(T) using resultant computations (see above). Then, we must find the largest square dividing disc(T). With our current knowledge, this cannot be done really much faster than by factoring disc(T), and this is where the main difficulty lies. There is a huge industry (in both the litteral and not litteral sense of the word) dealing with factoring, and in 1997, it is reasonable to factor an 80-digit number, perhaps 90, but to factor much larger numbers can be done only by harnessing a huge amount of computational power (and even this way the current records are only around 160 to 170 digits). However, this is outside the scope of our study, and furthermore we have two positive comments on this. First, in practice, it is quite rare that we deal with such huge discriminants. Second, in the cases we do deal with such discriminants, it is most frequently because they occur after a number of algebraic operations such as compositums, resultants or the like, and purely algebraic methods will give factors, and also there is a very good chance that the large factors are squares.

In any case, we have to assume that we have a black box doing the factoring for us (this is quite an independent problem occupying vast amounts of literature and computer time). Once this is done, we only have a limited number of choices for f, and it is not difficult to show that one can try a finite number of elements before computing the full ring of integers ℤ_{K}. However, there are more or less clever ways to do this. Done in a naive manner, it is difficult to deal with even moderately large examples. In the 1970’s, Zassenhaus gave a natural but more clever way of computing ℤ_{K} and the discriminant. This method, which is called the round 2 algorithm, is quite simple both to explain and to implement, and we refer for example to [Coh0] Section 6.1, in particular Algorithm 6.1.8.

However, this method is very slow on large examples (well, this is a tautology, but the meaning is clear). Later, Zassenhaus invented a much more sophisticated algorithm, the round 4 algorithm, which is very difficult both to explain and to implement. In fact, to my knowledge, if we do not count simple language translations, there have been only two implementations of this algorithm. However, it is definitely worthwhile for large examples, the gain being often of several orders of magnitude.

The remaining basic invariants are the decompositions of prime numbers. Keep the above notation. A very simple and classical result says that, if p is a prime not dividing the index f, then the decomposition of pℤ_{K} as a power product of prime ideals in ℤ_{K} mimics that of the decomposition of T (X) modulo p in the ring 𝔽_{p}[X], i.e. if

\overline{T (X)} = ∏_{1≤i≤g} \overline{T_{i}(X)}^{e_{i}}

with deg(T_{i}) = f_{i}, then

pℤ_{K} = ∏_{1≤i≤g} 𝔭_{i}^{e_{i}} with 𝔭_{i} = pℤ_{K} + T_{i}(θ)ℤ_{K} and f(𝔭_{i}/p) = f_{i} .

Thus, when p does not divide the index, the problem is easy. When p divides the index, one can try to change θ so as to have an index not divisible by p, but unfortunately this is not always possible, since there are fields where certain primes always divide the index (a famous example of Dedekind is T (X) = X^{3}+X^{2}−2X +8 where p = 2 always divides the index).

In case p divides the index, several methods have been suggested, but the one I prefer because it is simple and efficient, is due to Buchmann and Lenstra, who remark that we must perform two steps, one to remove ramification (a so-called squarefree decomposition), which is done by computing the p-radical (this is also done in the round 2 algorithm), the second to split separable algebras over 𝔽_{p} by means of idempotents. I refer to [Coh0] Section 6.2, and in particular Algorithm 6.2.9 for details.

Another important invariant of a number field which we have not mentioned, essentially because we will not use it, is the Galois group of the Galois closure. The computation of these groups is rather ad hoc, and has been implemented systematically only up to degree 11. In [Coh0] Section 6.3 some details and implementations are given up to degree 7.

2.4. Computing the class and unit group and the regulator This is a much harder subject, and has been in a satisfactory state only ap-

proximately since 1995, and here also, up to translations, there are only two rather different implementations, one in Kant, the other in Pari. Since the class group is basic to class field theory, and because of the importance of these computations, I give much more details here. Note that it is also historically important, since it solves a century old program initiated by Dedekind who asked to give efficient methods to compute these invariants. I refer to [Coh0], Section 6.5 for more details.

First, we can easily dispose of the roots of unity of K (the invariant w(K)) by using a well known theorem of Kronecker saying that they are characterized as algebraic integers such that all the conjugates have modulus 1. The inequality between arithmetic and geometric mean then shows that for any non-zero algebraic integer α ∈ ℤ_{K} we have

∑_{1≤i≤n} |σ_{i}(α)|^{2} ≥ n

with equality if and only if α is a root of unity. Since this is a quadratic form (the T_{2} form already used in the polred algorithm), the LLL algorithm followed by a systematic search for the smallest norms (which was not essential, although nice, in polred, but which is essential here) readily gives all the possible α, hence w(K) and a primitive w(K)-th root of unity.

For the other invariants, we employ a technique which has been inspired by the considerable efforts done on factoring algorithms in the 1970’s, the use of factor bases.

(A) Computing the class group

Consider first the computation of the class group Cl(K) (although, as we will see, it is impossible to compute it without computing also the unit group, or at least the regulator). Recall that Cl(K) is a finite Abelian group. Assume for the moment (we will of course come back to this in detail later) that we know a system of generators, which we will denote by \overline{g_{1}}, …,\overline{g_{k}}, where the g_{i} are fractional ideals of K and \overline{g_{i}} their ideal classes. This means that the natural Abelian group homomorphism ϕ from ℤ^{k} to Cl(K) sending (x_{1}, …, x_{k}) ∈ ℤ^{k} to ∏_{1≤i≤k} \overline{g_{i}}^{x_{i}} is surjective. Let Λ be the kernel of ϕ. Since ℤ is a principal ideal domain, any submodule of a finitely generated free module is free, thus Λ is a lattice, and since Cl(K) is a finite group, it is also of rank k. Thus, we have the exact sequence

0 ⟶ Λ ⟶ ℤ^{k} ⟶^{ϕ} Cl(K) ⟶ 1

An element of Λ is by definition a vector (x_{1}, …, x_{k}) such that ∏_{i} \overline{g_{i}}^{x_{i}} = \overline{1} in Cl(K) (or equivalently such that ∏_{i} g_{i}^{x_{i}} = αℤ_{K} is a principal ideal), hence is a relation in the class group, and we will call Λ the lattice of relations. Assume that we have some method to compute relations (we will of course explain in greater detail how this is done), and assume that we have computed m such. Call Λ′ the sub-module of ℤ^{k} generated by the m relations that we have found, so that Λ′ ⊂ Λ. Assume that we can compute enough relations so that Λ′ = Λ (once again, I will give details below, including the important question of how one checks that this equality is true). Then, it is now a matter of pure linear algebra over ℤ to compute the class group.

Let us see how this is done. We represent the m relations (x_{1}, …, x_{k}) that we have found as column vectors, and put them together in a k × m matrix M, where each column is a relation, then Λ′ is the image of M, considered as a ℤ-module.

We must do two things. First, find a ℤ-basis of Λ′ from the generating elements, and second find the structure of

Cl(K) ≃ ℤ^{k}/Λ = ℤ^{k}/Λ′

as a finite Abelian group. The first task is achieved using the Hermite Normal Form (HNF) algorithm, the second by using the Smith Normal Form (SNF) algorithm, which are classical and often taught in undergraduate courses (see [Coh0] Algorithm 2.4.4 and following, and Algorithm 2.4.14). Let me describe very sketchily these algorithms.

A matrix H is said to be in HNF if it is an upper triangular matrix (h_{i,j}) with positive (non-zero) diagonal entries h_{i,i}, and the additional requirement that, in a given row i, the off diagonal entries are in a fixed residue set modulo the diagonal element (one usually chooses 0 ≤ h_{i,j} < h_{i,i} for i ≠ j, but the choice is not important). Then, we have the following important theorem. Before stating it, we recall that a unimodular matrix is a matrix with entries in ℤ and determinant equal to ±1 (i.e. a matrix in GL_{m}(ℤ)). Further, if A and B are two matrices with the same number of rows, we will denote by (A|B) the horizontal concatenation of A and B.

Theorem 2.2. Let M be a k × m matrix of rank k (thus with m ≥ k) and integer coefficients. There exists a (non-unique in general) unimodular matrix U and a unique HNF matrix H such that

MU = (0|H) .

The columns of H form a ℤ-basis of the ℤ-module generated by the columns of M, and the columns of U corresponding to the 0 columns in the right hand side form a ℤ-basis of the kernel of the matrix M considered as an endomorphism of ℤ-modules (the integer kernel).

An important feature of this theorem is that there is an efficient algorithm to compute H (and U also if desired). Although the basic idea is simple, there are very dangerous pitfalls linked to the size of the coefficients which may occur during the computation, and the fact that H and U can indeed be computed in an efficient manner has been discovered rather recently.

Essentially, we want to copy the method of Gaussian pivoting used in linear algebra over fields. In that situation, we are dealing with a certain row i (say), we have a non-zero element a_{i,m} (for example) in this row, and some other element a_{i,j} which we want to set equal to zero by a column operation. Denoting by C_{m} and C_{j} the corresponding columns, the standard answer is to set

C_{j} ← C_{j} − (a_{i,j}/a_{i,m})C_{m} ,

which indeed does what is needed. One then progresses along the row until all the necessary elements have been set to zero, and we then go on to the next row.

This is correct for fields. But when dealing with rings such as ℤ (which of course should be integral domains, otherwise even worse things may occur), we must proceed differently since we are not allowed to do column operations with non-integral coefficients such as a_{i,j}/a_{i,m}. In ℤ, we use the nice fact that we have an extended Euclidean algorithm. In our example above, let d be the GCD of a_{i,m} and a_{i,j}, and let u and v be such that d = ua_{i,j} + va_{i,m}, all these quantities being found by the extended Euclidean algorithm. Then, instead of replacing the single column C_{j}, we replace simultaneously columns C_{j} and C_{m} by the formula

(C_{j}, C_{m}) ← (C_{j}, C_{m}) ( \begin{matrix}a_{i,m}/d & u \\ −a_{i,j}/d & v \end{matrix} )

in other words

(C_{j}, C_{m}) ← (a_{i,m}/dC_{j} − a_{i,j}/dC_{m}, uC_{j} + vC_{m}) .

The transforming 2 × 2 matrix has integer coefficients and determinant equal to 1 by assumption, hence it leads to an elementary transformation in GL_{m}(ℤ), and of course the desired coefficient a_{i,j} becomes equal to zero after the transformation. The algorithm then proceeds as in the case of Gaussian pivoting.

As mentioned above, if implemented too naively, this method will have huge intermediate coefficients and become desperately slow, so it must be modified cleverly. See the above mentioned Algorithms in [Coh0].

Note also that we have used in an essential way the fact that ℤ is a Euclidean domain, and even that it possesses an efficient extended Euclidean algorithm. However it has been realized only very recently (see [Coh1]) that it can be extended to any computable Dedekind domain, and in particular to rings of integers of number fields, and this is essential when dealing with relative extensions.

The second notion and corresponding algorithm that we will need is that of Smith Normal Form (SNF). Although it can easily be stated for non-square matrices and matrices not of maximal rank, we will restrict to this case since it is the only one we need.

We will say that a square matrix D is in SNF if D is a diagonal matrix and if the diagonal entries d_{i} are positive and satisfy d_{i} | d_{i−1} for 2 ≤ i ≤ k.

Theorem 2.3. Let M be a square k × k matrix of rank k with integer coefficients. There exist two (non-unique) unimodular matrices U and V and a unique matrix D in SNF such that

M = UDV .

If M is the matrix giving a basis of a sublattice Λ of ℤ^{k} in terms of the canonical basis (e_{i}) of ℤ^{k}, then we have

ℤ^{k}/Λ ≃ ⨁_{1≤i≤k}(ℤ/d_{i}ℤ) .

More precisely, let U_{j} be the j-th column of the matrix U considered as an element of ℤ^{k}, and denote by \overline{U_{j}} its class in ℤ^{k}/Λ. Then we have the equality

ℤ^{k}/Λ = ⨁_{1≤j≤k}(ℤ/d_{j}ℤ)\overline{U_{j}} .

Note that, in algorithmic applications, the usual theoretical statements such as this is isomorphic to that are insufficient in general. They must almost always be replaced by true equalities, which implies chasing through all the implicit isomorphisms or identifications. This can sometimes be slightly painful, but it is rewarding and essential.

As in the case of the HNF, we have an efficient algorithm to compute the SNF. The basic idea for introducing zeros is the same (the use of the extended Euclidean algorithm), and here we are allowed to do column and row operations (recall that right multiplication by a matrix corresponds to column operations, while left multiplication correspond to row operations).

We proceed as follows, from the lower right hand corner m_{k,k} going diagonally up. We want ultimately that this element divide everything above and to the the left of it (here the whole matrix, but after some steps, only part of it of course). We start by clearing the k-th column (except of course for the corner element m_{k,k}) by performing column operations as explained above. We then clear the k-th row by doing similar row operations. Unfortunately, in doing so, we have put garbage back in the k-th column, so we clear it again. Doing so, we have put back garbage in the k-th row, so we clear it, and so on. It is not difficult to prove that this process terminates, in fact after a rather small number of steps, and at the end both the k-th row and column will be zero, except for the diagonal element m_{k,k}. This is not sufficient, since we want m_{k,k} to divide the whole matrix above and to the left of it. If some element m_{i,j} is not divisible by m_{k,k}, by a column or row addition, we bring it down to the last column or row, and start cleaning up again. We do this as long as there exists some element m_{i,j} not divisible by m_{k,k}, and once again it can be shown that we will terminate rapidly. Once this is achieved, we leave step k and go to step k − 1 with a matrix smaller by one row and column.

We now come back to our class group computation. Applying the Hermite Normal Form algorithm to our matrix M of relations, we obtain an HNF matrix H whose columns form a basis of Λ. We can discard the unimodular matrix involved here. Applying now the Smith Normal Form algorithm to H, we obtain matrices U, D and V as above such that H = UDV. We discard V, but keep the two others. The above theorem tells us that

ℤ^{k}/Λ = ⨁_{1≤j≤k}(ℤ/d_{j}ℤ)\overline{U_{j}} .

This almost gives us the class group Cl(K) (it gives us its structure as an abstract Abelian group at least), but we only have Cl(K) ≃ ℤ^{k}/Λ and not equal to it, and as mentioned above, in algorithmic practice we must have equalities and not isomorphisms. In our case, the isomorphism between ℤ^{k}/Λ and Cl(K) is obtained by the reduction modulo Λ of the map ϕ such that ϕ((x_{1}, …, x_{k})) = ∏_{i} \overline{g_{i}}^{x_{i}}. Thus, if U = (u_{i,j}) and if we set

𝔞_{j} = ∏_{1≤i≤j} g_{i}^{u_{i,j}}

then we have the equality

Cl(K) = ⨁_{1≤j≤k}(ℤ/d_{j}ℤ)\overline{𝔞_{j}} .

Note that, when d_{j} = 1 the corresponding component is the trivial group, so of course we suppress it.

We have thus obtained completely the class group. There still remains a large amount of work to be done. We must explain how to find generators for the class group, how to find relations, and how to be sure that we have found sufficiently many so as to have Λ = Λ′. We then must also explain how to compute the unit group and the regulator. In fact, we will see that checking that Λ′ = Λ is almost impossible without at least having first computed the regulator, and we now consider this problem.

(B) Computing the regulator

We keep the above assumptions, in particular we have generators (\overline{g_{i}})_{1≤i≤k} of the class group and m relations forming a k × m matrix M = (m_{i,j}). The j-th such relation, forming the j-th column of M, is of the form

∏_{1≤i≤k} \overline{g_{i}}^{m_{i_{j}}} = \overline{1}

in the class group Cl(K). This means that

∏_{1≤i≤k} g_{i}^{m_{i,j}} = α_{j}ℤ_{K}

is a principal ideal, and we assume that, when computing the relation, we have kept track of the corresponding α_{j} (this is essential, otherwise the algorithm cannot work). We want to keep the α_{j} in some way. Keeping them as abstract algebraic numbers (i.e. as polynomials in the generating element of K/ℚ) is possible, but considering the work that has to be done to obtain them, and also the work that will be done afterwards, the coefficients of the polynomials in question will be absurdly large, hence this is impractical. Instead, we will keep suitably good approximations to the complex embeddings σ_{i}(α_{j}) for 1 ≤ i ≤ r_{1} + r_{2} (the last r_{2} embeddings being trivially obtained by complex conjugation). However, even this can get very large, so we will in fact keep logarithms of these embeddings. If we only want the regulator and the class group, we can keep only the real part of the logarithm, i.e. the logarithm of the absolute value, multiplied by 2 for the non-real embeddings (see the definition of the regulator above). However, we usually also want the units themselves, and since in any case it is barely more expensive, we will keep the complex logarithms of the σ_{i}(α_{j}), multiplied by 2 when r_{1} < i ≤ r_{2}. Putting this as a column vector (which we will call the complex logarithmic embedding of α_{j}), and putting these column vectors together, we obtain an (r + 1) × m complex matrix M_{C}, which we will call the Archimedean part of the relation matrix M, where r = r_{1} + r_{2} − 1 is the unit rank. It is often useful to consider these two

matrices M and MC one on top of the other as ( \begin{matrix}M \\ M_{C} \end{matrix} ) as a single (k + r + 1) × m

matrix, the first k rows having integral entries, and the last r + 1 having complex entries. The advantage of considering this as a single matrix is that a column of this matrix can now be considered as a relation between ideals and not only ideal classes.

We now first follow the procedure explained above for finding the class group. Using the HNF algorithm on the matrix M, we obtain a unimodular matrix U and a HNF matrix H such that MU = (0|H). We can now multiply the matrix U by the full matrix ( M M_{C} ), thus obtaining

( \begin{matrix}M \\ M_{C} \end{matrix} ) U = ( \begin{matrix}0 & H \\ Z_{C} & H_{C} \end{matrix} ) .

Now the whole point is that making linear combinations of relations gives again a relation. This was true in the class group, since the entries of the matrix M were the exponents entering in the relations, so adding relations corresponds to multiplying ideal classes. But it is also true for the ideals and elements themselves, since it is true for the exponents, and also for the Archimedean parts since we have taken logarithms, so multiplying ideals corresponds to adding logarithms. Thus, every column of the right hand side of our transformed relation matrix is still a relation

between ideals. This means that ( \begin{matrix}H \\ H_{C} \end{matrix} ) is a matrix of relations among ideals, but

the most important part for now is the left hand part which says that ( \begin{matrix}0 \\ Z_{C} \end{matrix} ) is a

matrix of relations among ideals. Let s = m − k be the number of columns of this matrix. For any j ≤ s, let u_{j} be the algebraic number whose complex logarithmic embedding is the j-th column of Z_{C}. Then the fact that the exponents in column j are equal to 0 means that ℤ_{K} = u_{j}ℤ_{K}, in other words that u_{j} is a unit of ℤ_{K}. Thus, by using the method for computing the class group, we automatically find at least some units.

Assume that we have found at least r = r_{1} + r_{2} − 1 units, i.e. that m ≥ k + r. Then, if we take any r columns of the real part of Z_{C}, this gives the usual matrix of the real logarithmic embeddings of the corresponding units, hence by adding the column of 1 and 2’s, taking the determinant and dividing by n (or extracting and r×r minor, it is the same), as remarked in the definition of the regulator, we obtain an integer multiple (perhaps equal to 0) of the regulator, where the integer is, as for the class group, a lattice index.

If m is larger than k + r (which it usually is, because otherwise we will probably fail in the sequel), then we will have several such multiples of the regulator (more precisely \binom{m−k}{r} of them), and we can obtain a better multiple by taking GCD’s (for example, if we have 4R(K), 0R(K) and 6R(K), the GCD would give 2R(K)). There are two problems with this. The first one, which is not very difficult to surmount, is that, if m is really much larger than k + r, we will have too many multiples of R(K), and it may take a long time both to compute them, and to get their GCD. This is not a real problem, since on probabilistic grounds one expects that if we choose the first r − 1 columns units to be independent, then taking these columns as fixed and only the last varying, will give much faster computations of determinants (since the first r − 1 pivoting steps can be done once and for all), and the final GCD will usually be equal to the GCD that we would have obtained if we had taken all the possibilities (if it is not, we lose a little time, but that is all).

A much more serious problem is, how does one compute the GCD of two (or more) real numbers? As a general question, this does not even make sense. However, here we know that all our numbers will be integer multiples of a fixed non-zero real number R(K). Thus, we can apply the usual Euclidean algorithm, replacing the usual stopping condition that some remainder vanishes, by the condition that the remainder should be very small, at least smaller than R(K)/2 to be safe. But the problem is that we do not know R(K) in advance, so where must we stop? We are saved by an important theorem due to Zimmert and improved by E. Friedmann (see [Frie]): regulators of number fields are bounded from below by a strictly positive constant. Friedman shows that this constant is larger than 0.2, and is attained for a sextic field. In any case, this means that we can use as our stopping criterion for our “real Euclidean algorithm” that the remainder be smaller than 0.1. I insist that this is not an arbitrary choice, but based on quite a difficult theorem.

Assuming that we have found enough relations so that one of our regulators is non-zero, performing the operations above we thus find a (hopefully small) integer multiple R′(K) of the regulator.

It remains to show that this is the true regulator (if it is not, as for the class group, we find some more relations and proceed as above).

(C) Checking that the class group and regulator are correct

Let us summarize what we really know at this stage. We have found a number m of relations giving a lattice Λ′, from which we have computed a tentative class group Cl′(K) ≃ ℤ^{k}/Λ, hence also a tentative class number h′(K) = |Cl′(K)|, and we know that h′(K) is an integer multiple of the true class number h(K), and we hope, but have not proved, that they are equal. Similarly we have a tentative regulator R′(K) which we know to be an integral multiple of the true regulator R(K), and we hope, but have not proved, that it is equal to R(K).

We are now going to check simultaneously that h′(K) = h(K) and R′(K) = R(K) or not. If this is not the case, we simply add more relations until the check turns out positive.

To do this, we use the analytic formula for the residue of the Dedekind ζ function given above (Theorem 1.9 (3)). It is easy to show using the above theorem that we have a convergent infinite product giving h(K)R(K), viz:

h(K)R(K) = w(K)\sqrt{|d(K)|}2^{−r_{1}}(2π)^{−r_{2}} ∏_{p} \frac{1 − 1/p}{∏_{𝔭|p}(1 − 1/p^{f(𝔭/p)})}

where as usual p runs over ordinary prime numbers and 𝔭 runs over the prime ideals above p, and f(𝔭/p) is the residual index.

Note that in practice, except for the few primes dividing the index as explained above, the quantities involved in the product above are very easy to compute. For example, the f(𝔭/p) are simply the degrees of the irreducible factors of T (X) modulo p when p does not divide the index, and these degrees can be found without even factoring completely by the so-called method of distinct-degree factorization.

The problem is elsewhere. This infinite product, although convergent, may converge very slowly. Although for our applications we only need quite a crude approximation (up to a factor of 2 on the result), if we do not make any assumption at this stage, we will have to take O(|d(K)|^{1/2}) terms of the product to be sure to have a correct result up to a constant factor. This is too slow for most applications.

Hence at this stage, we will make an important assumption (but see later on how to get rid of it). We assume the validity of the Generalized Riemann Hypothesis (GRH), which says that, apart from negative integer zeros, the Dedekind zeta functions have all their complex zeros on the line Re(s) = 1/2. This hypothesis is widely believed to be true, and has been extensively tested for the ordinary Riemann ζ function, and a little tested for the other functions.

In any case, thanks to this hypothesis, it is not too difficult to prove that to obtain the correct value of the Euler product up to a constant factor, it is now enough to take prime numbers up to O(log(|d(K)|)^{2}) only. However satisfactory this may be, it is not quite sufficient for our needs since we need a numerical upper bound. This was provided by several authors, the best being due to E. Bach who showed that if one takes the primes up to 12 log(|d(K)|)^{2}, then the product is off by a factor less than \sqrt{2}. In other words, we can compute a real number a such that

a/\sqrt{2} < h(K)R(K) < a\sqrt{2} .

It is now easy to see how we can apply this to the problem of determining whether our tentative values h′(K) and R′(K) are correct. We know that h′(K)R′(K) = c·h(K)R(K) for some integer c ≥ 1. I claim that c = 1 if and only if h′(K)R′(K) < a\sqrt{2}. Indeed, if c = 1, we evidently have h′(K)R′(K) = h(K)R(K) < a\sqrt{2}. Conversely, assume that h′(K)R′(K) < a\sqrt{2}. This implies that h(K)R(K) = h′(K)R′(K)/c < a\sqrt{2}/c. If we had c ≥ 2, then we would obtain h(K)R(K) < a/\sqrt{2}, contrary to our assumption, so c = 1 as claimed.

Thus, to terminate the algorithm, we compute the product a with the primes up to 12 log(|d(K)|)^{2}, and check whether h′(K)R′(K) < a\sqrt{2}. If this is the case, we have proved (under the assumption of the GRH) that h′(K) = h(K) (hence that our lattice Λ′ is equal to Λ), and that R′(K) = R(K) (hence that the units u_{j} that we have found generate the full unit group U(K)). If not, we find more relations. This will necessarily both decrease h′(K) and R′(K), and after a finite number of steps, we can hope (this is always true in practice) that the test h′(K)R′(K) < a\sqrt{2} will be satisfied.

(D) Computing the fundamental units

If we are not content with the regulator, but want a system of fundamental units, it is not difficult to see that it is enough to use an extended real Euclidean algorithm instead of the ordinary real Euclidean algorithm described above, and we will thus obtain explicitly the complex logarithmic embeddings of a system of units whose regulator will be equal to R′(K), hence to R(K) once one has obtained R′(K) = R(K), and so a fundamental system of units. We could then obtain the units themselves as polynomials on some integral basis by taking exponentials and then solving a simple linear system over ℂ (whose solution must be approximately integral since the units are in ℤ_{K}). Note that it would have been impossible to obtain the units if we had only kept the real logarithmic embeddings.

There are two closely related problems with this approach. First, the exponential may overflow the possibilities of the implementation. This is a very real problem, since one must not forget that the units have been obtained after rather complicated operations. Second, the units that we have found are probably badly skewed, i.e. are very far from being the smallest possible (in any sense).

As usual when the word “small” occurs in computational number theory, an excellent solution to these problems is once again the use of the LLL algorithm, one of whose purposes is exactly to unskew very badly skewed bases of lattices. After application of the LLL algorithm to the real part of the logarithmic matrix, the units that we obtain still form a fundamental system of units (their regulator R(K) has not changed) but in general is much less skewed. One can then exponentiate and solve the linear system. It may again be that the exponential overflows (there is little that can be done except implement differently so as to allow higher values), or that the linear system is unstable or gives solutions which are too far away to integers. In that case, one must restart the computation of M_{C}, H_{C} etc... to a greater accuracy, but note that the exponents giving the relations can be kept.

Finally, once the tentative units are obtained, we must check that they are correct, since we may have made numerical analysis errors. We already know that they are in ℤ_{K} (the linear system must have approximately integer solutions), so we now compute their norm exactly (algebraically, using resultants, to see that they are equal to ±1, and we compute their regulator, to check that it is approximately R(K).

(E) Finding generators and relations

We must now terminate by putting the “meat” in the algorithm, i.e. explain how the whole process is done, finding the generators \overline{g_{i}} and the relations in Λ.

It is easy to show that there exists an easily computable constant C depending on the number field K such that Cl(K) is generated by the ideal classes of all the prime ideals of norm less than C. The problem is that, without any assumption, we must take for C the so-called Minkowski constant or a later improvement of it, but in any case a C of size comparable to \sqrt{|d(K)|} which is not acceptable for moderately large fields.

Once again, we use the GRH (it does not cost more since had to assume its validity anyway in checking h′(K)R′(K) = h(K)R(K)). Then a closely related theorem of E. Bach also says that Cl(K) is generated by the ideal classes of prime ideals of norms less than 12 log(|d(K)|)^{2}. We can set g_{i} to be all such prime ideals, and take as generators the ideal classes \overline{g_{i}}.

In practice this gives too many generators, so we proceed as follows. We choose a much lower constant than 12, for example 0.3 or 0.1 and take as g_{i} only the prime ideals of norm less than this constant times log(|d(K)|)^{2}. Of course the \overline{g_{i}} may not generate Cl(K), but this is exceedingly rare. In any case, we can then show using one of the methods described below, that the \overline{g_{i}} which have been discarded up to norm 12 log(|d(K)|)^{2} are in the group generated by the \overline{g_{i}} with g_{i} of small norm. If it is not the case, we add them to the generating set, but as mentioned, in practice this never happens.

Thus, let P be the set of prime ideals of norm less than B = 0.3 log(|d(K)|)^{2} (say). We call this set our factor base, and the generators \overline{g_{i}} of the class group are the ideal classes of the elements of P.

To obtain the ideals in P, we factor prime numbers up to B into prime ideals of K as explained above, either easily if p does not divide the index, or with more effort using for example the Buchmann-Lenstra method if p divides the index. We also keep some additional information so as to be able to compute quickly 𝔭adic valuations, hence to perform prime ideal factorization of any ideal (see [Coh0] Algorithm 4.8.17). In this process, since we have found that

pℤ_{K} = ∏_{𝔭_{i}|p} 𝔭_{i}^{e_{i}} ,

we already have a few relations in Λ, the so-called trivial (although useful) relations, given by the exponents e_{i}.

To obtain relations in Λ is much more technical and difficult, and here I will be only very sketchy. In addition to the trivial relations, there are several methods to obtain relations, having relative advantages and disadvantages. A first method is to find elements of small norm either by a naive search, or by clever methods. If such elements are found, since their norm is small, it can be hoped that they will factor on our factor base P. If such an α does factor, we will have

αℤ_{K} = ∏_{𝔭∈P} 𝔭^{v_{𝔭}(α)}

giving immediately a relation in the class group. This method is quite fast (if implemented cleverly, since a naive search will rarely give elements of small norm), but has the disadvantage of giving many dependent relations.

Another method is the random reduction method. One can define the notion of reduction for an ideal. This is both a mathematical notion, i.e. in any ideal class there is at least one reduced ideal, and such an ideal has reasonably small norm, and an algorithmic notion, in that there exists an algorithm to find one (or many) reduced ideals in the same ideal class as a given ideal. Furthermore, it is a flexible notion, in that one can define reductions along several directions (more precisely, in a r_{1} + r_{2} − 1-dimensional vector space).

In any case, to find relations in Λ using this notion, we proceed as follows. Choose some random integer exponents x_{i}, preferably small and most of them equal to zero, but this is only for efficiency’s sake. Consider the ideal

I = ∏_{𝔭_{i}∈P} 𝔭_{i}^{x_{i}}

which by construction factors on our factor base P. Using a reduction algorithm, in a random direction, find a reduced ideal J which is in the same ideal class as I, i.e. find α ∈ K^{∗} such that J = αI. Since J is reduced, it has reasonably small norm, hence it can be hoped that it factors on our factor base P. If this is the case, then the equality αℤ_{K} = JI^{−1} gives rise to a relation in the class group.

Using reasonable heuristic assumptions, the running time of this algorithm can be analyzed. Essentially all the time is spent in the search for relations, and it is believed that by using the random relation method, the expected running time of the algorithm is O(L(|d(K)|)), where

L(x) = e^{\sqrt{log x log log x}}

is a function which occurs very frequently in problems involving factor bases such as factoring or class group computations. Note that this analysis implies an optimal choice of the size of the factor base, which may be different than the one used in practice. Indeed, the factor base must bot be too small, otherwise almost no ideals will factor, and it will be difficult to find relations. On the other hand the factor base must not be too large, because we will need to find too many relations and it will be expensive. In addition, the linear algebra (HNF essentially) will also start to be a problem in practice, although in theory it does not.

(F) The principal ideal problem

An important and perhaps somewhat unexpected side-benefit of the above algorithm is the possibility to solve the so-called principal ideal problem (this will be crucial in our applications to class fields). We assume computed the class group Cl(K) = ⨁_{i}(ℤ/d_{i}ℤ)\overline{𝔞_{i}}, and we give ourselves an ideal I. By definition, we can write the ideal class of I as a power product of the \overline{𝔞_{i}}. Lifting to ideals, this means that there exists integers x_{i} and α ∈ K such that

I = α ∏_{i} 𝔞_{i}^{x_{i}} with 0 ≤ x_{i} < d_{i} .

The problem is to find the x_{i} (i.e. the discrete logarithm of the ideal class of I in the class group), and also α if it is wanted. Note that, even if we know that our number field has trivial class group, so that every ideal is a principal ideal, the problem of finding α is highly non-trivial. Even recently, some experts went about finding α by brute-force methods.

However, if we keep the information that we have acquired while computing the class group and the regulator (including the Archimedean parts), this computation can be done quite easily as follows (see [Coh0] Algorithm 6.5.10). If I factors on our factor base P, good. Otherwise, multiply I by random elements of P and random reduce as above for finding random relations. We will thus have an equality of the form II_{1} = βJ where β ∈ K and J is a reduced ideal. If J factors on our factor base (it has a good chance since it is reduced), then I = βJI_{1}^{−1} is equal to β times an ideal which factors on our factor base, so we can reduce to this case (we work on JI_{1}^{−1} and multiply the final result by β).

Let I = ∏_{𝔭_{i}∈P} 𝔭_{i}^{x_{i}}, and let X be the column vector of the x_{i}. Since the columns of the HNF matrix H kept during the class group computation process form a basis of the relation matrix Λ, it is clear that I is a principal ideal if and only if X is a ℤ-linear combination of the columns of H, or in other words if and only if H^{−1}X is a vector with integer coefficients, and this can easily be computed and/or checked since H is a triangular matrix. If I is not a principal ideal, computing its discrete logarithm is very easy, since it will essentially be the fractional parts of the entries of H^{−1}X multiplied by the corresponding d_{i}. Finally, finding the element α (a generator of I if I is principal) can also easily be done using the Archmimedean data H_{C} and the x_{i}.

(G) Removing the GRH assumption

An unfortunate feature of the above algorithm is that it assumes the validity of an unproved conjecture, the GRH, and this assumption is essential both for the choice of generators, and for the accurate computation of the Euler product.

There are two ways around this. One is to refuse to use the GRH, and use much weaker bounds coming from the geometry of numbers or other means. This is of course much slower, but returns a proven result (assuming there are no bugs in the implementation of course!).

Another method, which is usually much faster, is to run the algorithm under the GRH, and then certify the result using methods which are independent of the GRH of course. Although the certification part is again very slow, in practice this technique performs much better than a direct algorithm not using GRH. The possibility of doing this certification is based on a number of quite classical but little known results, and we refer to [DiOl] for details.

(H) Practical performance

As mentioned, the above algorithm has been implemented in Kant and in Pari. It is now completely routine to compute class group and unit group for number fields of degree up to 12 (a few minutes at most), even with moderately large discriminants. In fact, in degree 2, specific implementations have even reached discriminants of 60 digits, which should be compared with the size of numbers which are factored (since the technology is somewhat similar), which is more around 80 or 100 digits. For number fields of intermediate degrees from 12 to 20, it is still quite easy, say 30 minutes at most. For very large degrees, it will take several days, but we have, for example, succeeded in computing the class group and unit group of a “random” number field of degree 40 in 2 days (it was not random of course, but it was not constructed so as to make the computation easier, as it would be for example for cyclotomic fields).

2.5. Computing tables of number fields

Computing tables of number fields means fixing the degree n, the signature (r_{1}, r_{2}), sometimes also the Galois group of the Galois closure, and finding all number fields up to isomorphism with discriminant up to a given bound. The general method for doing this is to use the geometry of numbers, and in particular theorems of Hunter and Martinet, which reduce the problem to searching through a finite family of polynomials. The enormous drawback to this problem is that it is very slow and inefficient. The amount of polynomials to be considered is huge (10^{10} is not uncommon) compared to the final amount of fields found (sometimes only 1 or 2!), and many expensive field discriminant computations or isomorphism computations have to be made. Unfortunately, apart from special cases, this is the only method known. Let me summarize the state of the art on this subject in early 1997.

In degree 2, the problem is equivalent to finding all squarefree numbers up to a given bound, hence can be considered as trivial.

In degree 3, until 1996, only the general method was used, and tables up to discriminants 10^{7} were built with many weeks of computer time. In 1996, K. Belabas, using an old idea of Davenport-Heilbronn, realized that one can do essentially as well as in the quadratic case, i.e. find all squarefree numbers up to a given bound, so computing tables up to 10^{7} can be done in a few seconds, and tables have been made up to 10^{11} (see [Bel]).

In higher degrees, only the general method is known. Quite extensive tables exist in degrees 4, 5 and 6. Rather small tables exist in degree 7, and no tables in degree 8, since for certain signatures one does not know (with a proof not relying on the GRH) even the smallest discriminant. Similarly in degree 9 or higher.

If, however, one restricts to imprimitive fields, i.e. fields containing a non-trivial proper subfield, the situation is better. For example, as an application of the theory and algorithms that we shall see below, one can construct efficiently very large tables of degree 8 fields containing a quartic subfield, which is equivalent to requiring that the Galois group of the Galois closure belongs to a certain subset of the set of all possible Galois groups in degree 8.

The same method will also allow us to construct number fields of rather large degree (we have chosen arbitrarily to stop at degree 80) which have rather small discriminants compared to their degree, so which may be not far from the beginning in their corresponding table (see below). This was in fact part of the motivation for our work.

3. A survey of global class field theory

In this brief survey, we give the main results of global class field theory for the case of number fields. We refer the reader to [Art-Tat], [Gras] or [Mart] for more detailed statements and proofs.

Class field theory is one of the most remarkable and important theories in number theory. In fact, a large part of the current trends in number theory (for example the Langlands program) can be thought of as an attempt at generalizations of class field theory.

One of its remarkable aspects is that it gives a canonical bijection between rather different objects. On the one hand classes of congruence subgroups (see definitions below), which are nothing more than certain sets of ideals in a base field K. On the other hand isomorphism classes of Abelian extensions of K. There are two parts to this theorem (in fact three as we shall see), the injectivity and the surjectivity, but what is most spectacular is certainly the surjectivity since it predicts a priori the existence of certain number fields, and it gives their discriminant and signature. Finding these number fields in practice is another matter (although in some sense we simply follow the proof of the theorem), and we will explain below how this is done.

3.1. Prologue: Hilbert class fields

Before starting on the general theory, we start with a special case which already embodies a large part of the theory. It will be generalized in the subsequent sections.

We will say that an extension L/K of number fields is unramified if there are no places of K which ramify in L. This means the following. For every prime ideal 𝔭 of K, we have a decomposition

𝔭ℤ_{L} = ∏_{𝔓_{i}|𝔭}𝔓_{i}^{e_{i}} ,

and we want that 𝔭 be unramified, i.e. that all of the e_{i} be equal to 1 (in other words that 𝔭ℤ_{L} is a “squarefree” ideal). This must be true for every prime ideal of K. In addition, we require that a similar statement hold for the embeddings σ_{i}. More precisely, if [L : K] = n, then it is not difficult to show that any embedding σ_{i} of K extends to exactly n embeddings of L. If σ_{i} was non-real, then all the extensions will evidently be non-real and there is nothing to say. On the other hand, if σ_{i} is a real embedding, then some of the extensions may be real and other complex. We say that σ_{i} is unramified if all its extensions are still real.

We are concerned with finite Abelian unramified extensions L of a fixed base field K. D. Hilbert showed that there is a maximal such extension (denoted by H) in a strong sense, i.e. every Abelian unramified extension is isomorphic to a subextension of H. Furthermore, H has remarkable properties. First and foremost, the Galois group of H/K is isomorphic to the class group Cl(K). This isomorphism is explicitly given (all this will be described in a more general setting below). Second, it possesses the capitulation property: every ideal of K becomes principal in L, i.e. if 𝔞 is an ideal of K, then 𝔞ℤ_{L} is a principal ideal of ℤ_{L} (this is a theorem of Furtwängler).

The field H is called the Hilbert class field of K. By Galois theory, the subextensions of H/K (and thus all unramified extensions of K up to isomorphism) correspond in a one-to-one way to subgroups of the Galois group, hence to subgroups of the class group Cl(K), or equivalently to subgroups of the group I(K) of fractional ideals of K containing the group of principal ideals of K.

When there is ramification, the situation is completely analogous, except that we must replace the ordinary class group by a more general class group called the ray class group which we now study.

3.2. Ray class groups

We say that 𝔪 is a modulus if it is a pair (𝔪_{0}, 𝔪_{∞}) where 𝔪_{0} is an integral ideal of K and 𝔪_{∞} is a subset of the set of real embeddings of K, i.e. of the σ_{i} for 1 ≤ i ≤ r_{1}. We will write this formally as 𝔪 = 𝔪_{0}𝔪_{∞}. We will write I_{𝔪}(K) (or simply I_{𝔪} when the field K is understood) for the fractional ideals of K coprime to 𝔪_{0} (we will also say simply coprime to 𝔪), i.e. whose 𝔭-adic valuation is equal to 0 for each prime ideal 𝔭 dividing 𝔪_{0}, or equivalently which can be written as 𝔞/𝔟 with 𝔞 and 𝔟 integral ideals coprime to 𝔪_{0} in the usual sense (𝔞 + 𝔪_{0} = 𝔟 + 𝔪_{0} = ℤ_{K}). It is clear that I_{𝔪}(K) forms a subgroup of the full group of fractional ideals.

Let 𝔪 be a modulus. If α ∈ K^{∗}, we say that

α ≡ 1 (mod ^{∗}𝔪)

if for all 𝔭 dividing 𝔪_{0} we have v_{𝔭}(α − 1) ≥ v_{𝔭}(𝔪_{0}), and if for all embeddings σ_{i} ∈ 𝔪_{∞} we have σ_{i}(α) > 0. We will write K_{𝔪} for the group of such α. If α and β are in K^{∗}, we also say that α ≡ β (mod ^{∗}𝔪) if α and β are coprime to 𝔪 and if α/β ≡ 1 (mod ^{∗}𝔪).

Note that α ≡ 1 (mod ^{∗}𝔪_{0}) is equivalent to α ≡ 1 (mod 𝔪_{0}) only if we restrict to α ∈ ℤ_{K}, which would not be usable for our needs.

We will write P_{𝔪}(K) (or P_{𝔪} if the field K is understood) for the set of all (fractional) principal ideals of ℤ_{K} which can be generated by an element α such that α ≡ 1 (mod ^{∗}𝔪), i.e. of the form αℤ_{K} for such an α. It is clear that P_{𝔪}(K) is a subgroup of I_{𝔪}(K), sometimes called the ray group of 𝔪.

Let 𝔞 ∈ P_{𝔪}(K). It is clear that 𝔞 = αℤ_{K} = βℤ_{K} with α and β in K_{𝔪} if and only if β/α is a unit u such that u ∈ K_{𝔪}. These units form a subgroup of the unit group which we will denote by U_{𝔪}(K) = U(K) ∩ K_{𝔪}. From the definitions, it is clear that we have the following exact sequence, which generalizes the corresponding exact sequence seen above for all fractional ideals (corresponding to the trivial modulus 𝔪 where 𝔪_{0} = ℤ_{K} and 𝔪_{∞} = ∅)

1 ⟶ U_{𝔪}(K) ⟶ K_{𝔪} ⟶ P_{𝔪}(K) ⟶ 1 .

Finally, we define the ray class group Cl_{𝔪}(K) by Cl_{𝔪}(K) = I_{𝔪}(K)/P_{𝔪}(K), so that we also have the exact sequence

1 ⟶ P_{𝔪}(K) ⟶ I_{𝔪}(K) ⟶ Cl_{𝔪}(K) ⟶ 1 .

To formulate the next result, we need to generalize to moduli the notion of quotient ring of a ring by an ideal. If 𝔪 = 𝔪_{0}𝔪_{∞} is a modulus, we set by definition

(ℤ_{K}/𝔪)^{∗} = (ℤ_{K}/𝔪_{0})^{∗} × (ℤ/2ℤ)^{𝔪_{∞}}

where (ℤ_{K}/𝔪_{0})^{∗} denotes as usual the set of invertible elements in the ring ℤ_{K}/𝔪_{0}, i.e. classes of elements of ℤ_{K} coprime to 𝔪_{0}, and (ℤ/2ℤ)^{𝔪_{∞}} is |𝔪_{∞}| copies of (ℤ/2ℤ) indexed by 𝔪_{∞}. We have a natural map ψ from the elements of K^{∗} coprime to 𝔪 into (ℤ_{K}/𝔪)^{∗} which sends α to its class in (ℤ_{K}/𝔪_{0})^{∗} and for each element σ_{i} of 𝔪_{∞}, we set the corresponding component in ℤ/2ℤ to be equal to the 0 or 1 modulo 2 according to whether σ_{i}(α) is positive or negative. The approximation theorem for Dedekind domains implies that ψ is surjective, in fact that every element of (ℤ_{K}/𝔪)^{∗} is of the form ψ(α) for some α ∈ ℤ_{K}. Note, however, that in algorithmic practice, it will usually be preferable to represent an element of (ℤ_{K}/𝔪)^{∗} as in the definition, i.e. as (\overline{α}, s_{1}, …, s_{𝔪_{∞}}), where \overline{α} is the class of α modulo 𝔪_{0}.

We then have the following (very easy) proposition, which however will be crucial for us in the sequel.

Proposition 3.1. We have the following 4-term exact sequence

U(K) ⟶^{ψ} (ℤ_{K}/𝔪)^{∗} ⟶ Cl_{𝔪}(K) ⟶ Cl(K) ⟶ 1 .

All the maps are essentially clear, except perhaps for the second one, which sends an element of the form ψ(α) to the ideal class of αℤ_{K} in Cl_{𝔪}(K) (which is not in general the trivial class, since α ∉ K_{𝔪} in general, and does not depend on the respresentative α). Note that it is not the map which sends (\overline{α}, s_{1}, …, s_{|𝔪_{∞}|}) to the ideal class of αℤ_{K}.

Exercise. Prove this proposition.

Corollary 3.2. The ray class group is finite. Its cardinality, which we will denote by h_{𝔪}(K) (or simply h_{𝔪} when the field is understood) satisfies

h(K) | h_{𝔪}(K) | h(K)ϕ(𝔪) ,

where ϕ(𝔪) = |(ℤ_{K}/𝔪)^{∗}| is the generalization to number fields of the ordinary ϕ function.

Note that, as in the usual case, if 𝔪_{0} = ∏_{𝔭} 𝔭^{a_{𝔭}}, then

ϕ(𝔪) = 2^{|𝔪_{∞}|} ∏_{𝔭} N (𝔭)^{a_{𝔭}−1}(N (p) − 1) .

This corollary can be seen as a first approach in computing the ray class group, but we shall see a method which gives the full result (including the structure, as we have done for the ordinary class group) later.

3.3. Congruence groups: one side of class field theory

In this section, the field K is fixed, so we write I_{𝔪} instead of I_{𝔪}(K), P_{𝔪} instead of P_{𝔪}(K), Cl_{𝔪} instead of Cl_{𝔪}(K) and so on.

Recall that we will ultimately want a bijection between two sets, the two “sides” of class field theory. We must describe both sets, and we start with the easy side. Recall that, to describe unramified extensions, we used subgroups of the group of fractional ideals containing the group of principal ideals. In our more general situation, we do exactly the same. We say that C is a congruence subgroup for the modulus 𝔪 if C is a group of fractional ideals such that

P_{𝔪} ⊂ C ⊂ I_{𝔪} .

We can also consider the set of classes \overline{C} = C/P_{𝔪} ⊂ Cl_{𝔪}, so if desired we can consider a congruence subgroup as a subgroup of the ray class group Cl_{𝔪}. To indicate the modulus to which C corresponds, we will always write (𝔪, C) for a congruence subgroup to indicate to which modulus C corresponds to.

Keeping in mind the example of Hilbert class fields, we want to introduce an equivalence relation between congruence subgroups, so that subgroups in the same equivalence class define the same number field. More precisely, we proceed as follows. Let (𝔪, C) be a congruence subgroup. Then, one of the main results of class field theory will tell us that, exactly as in the Hilbert class field situation, there exists a generalized Hilbert class field H_{𝔪} (which we will call the ray class field for the modulus 𝔪), such that, among other properties, Gal(H_{𝔪}/K) ≃ Cl_{𝔪}(K). Let L be the Abelian extension corresponding to (𝔪, C), i.e. L = H\overline{C} ; 𝔪 is the fixed field of H_{𝔪} by \overline{C}, so that

Gal(L/K) ≃ Cl_{𝔪}/\overline{C} ≃ I_{𝔪}/C .

Of course, the subextensions of H_{𝔪} are in one to one correspondence with the congruence groups C by the Galois correspondence.

If 𝔪 is a multiple of 𝔫, then class field theory tells us that H_{𝔫} can be considered as a subfield of H_{𝔪}. Thus, if 𝔪_{1} and 𝔪_{2} are any moduli, we can consider H_{𝔪_{1}} and H_{𝔪_{2}} as subfields of a single H_{𝔪}, for example with 𝔪 = 𝔪_{1}𝔪_{2} (in fact any common multiple of 𝔪_{1} and 𝔪_{2} will do). We can then say that two congruence subgroups (𝔪_{1}, C_{1}) and (𝔪_{2}, C_{2}) are equivalent if they define the same number field, i.e. if H\overline{C_{1}} ; 𝔪_{1} = H\overline{C_{2}} ; 𝔪_{2} considered as subfields of H_{𝔪}. Note that we ask that the fields be identical, not only isomorphic, and this is why we need to embed the whole situation in a single number field H_{𝔪}. From this definition, it is clear that it is an equivalence relation.

Let us transform this definition into one which does not involve the field H_{𝔪}, since after all, for now, we do not know the results of class field theory. Let L = H\overline{C_{1}} ; 𝔪_{1} = H\overline{C_{2}} ; 𝔪_{2}. By Galois theory, L = H\overline{C} ; 𝔪 for some congruence subgroup C of 𝔪. The equivalence relation means that the natural maps from Cl_{𝔪}/\overline{C} to Cl_{𝔪_{i}}/\overline{C_{i}} are isomorphisms for i = 1 and i = 2. It can easily be shown as a consequence of the approximation theorem for Dedekind domains that the maps in question are always surjective. Thus, we have (𝔪_{1}, C_{1}) ∼ (𝔪_{2}, C_{2}) if and only if the maps are injective, and this is easily seen to be equivalent to I_{𝔪} ∩ C_{i} = C for i = 1 and i = 2. Choose now 𝔪 = 𝔪_{1}𝔪_{2}. Then, since C_{i} ⊂ I_{𝔪_{i}}, we have clearly I_{𝔪_{1}𝔪_{2}} ∩ C_{1} = I_{𝔪_{2}} ∩ C_{1} and similarly for C_{2}. Thus, (𝔪_{1}, C_{1}) ∼ (𝔪_{2}, C_{2}) if and only if I_{𝔪_{2}} ∩ C_{1} = I_{𝔪_{1}} ∩ C_{2}, and this now does not involve any extraneous number fields or moduli.

We take this as the definition of equivalence relation between congruence subgroups. We forget about the motivation coming from class field theory, and we must prove that it is indeed an equivalence relation. The transitivity is not obvious, and is left as a (not completely trivial) exercise.

In the special case where 𝔪_{2} divides 𝔪_{1}, then from the definition, (𝔪_{1}, C_{1}) ∼ (𝔪_{2}, C_{2}) if and only if I_{𝔪_{1}} ∩ C_{2} = C_{1}. I claim that this is equivalent to I_{𝔪_{1}} ∩ P_{𝔪_{2}} ⊂ C_{1} and C_{2} = C_{1}P_{𝔪_{2}}. Indeed, since P_{𝔪_{2}} ⊂ C_{2}, I_{𝔪_{1}} ∩ C_{2} = C_{1} trivially implies I_{𝔪_{1}} ∩ P_{𝔪_{2}} ⊂ C_{1}, and also C_{1}P_{𝔪_{2}} ⊂ C_{2}. Set C′_{2} = C_{1}P_{𝔪_{2}}. Then I claim that (𝔪_{1}, C_{1}) ∼ (𝔪_{2}, C′_{2}). Indeed, this means that C_{1} = I_{𝔪_{2}} ∩ C_{1} = I_{𝔪_{1}} ∩ C_{1}P_{𝔪_{2}} or equivalently (since the inclusion ⊂ is obvious), that I_{𝔪_{1}} ∩ C_{1}P_{𝔪_{2}} ⊂ C_{1}. But this follows from the inclusion I_{𝔪_{1}} ∩ P_{𝔪_{2}} ⊂ C_{1} by multiplying both sides by the group C_{1}.

Thus, since our equivalence relation is transitive, we have (𝔪_{2}, C_{2}) ∼ (𝔪_{2}, C′_{2}), and this of course means that C_{2} = C′_{2}, i.e. C_{2} = C_{1}P_{𝔪_{2}} as claimed.

Conversely, if we assume I_{𝔪_{1}}∩P_{𝔪_{2}} ⊂ C_{1} and C_{2} = C_{1}P_{𝔪_{2}}, then by multiplication by C_{1} we get as above I_{𝔪_{1}} ∩ C_{2} ⊂ C_{1}, and since the reverse inclusion is trivial we have equality, proving my claim.

Thus, if (𝔪_{1}, C_{1}) is a congruence group and if 𝔪_{2} is a divisor of 𝔪_{1}, there exists a congruence group of the form (𝔪_{2}, C_{2}) which is equivalent to (𝔪_{1}, C_{1}) if and only if I_{𝔪_{1}} ∩ P_{𝔪_{2}} ⊂ C_{1}, and in that case C_{2} = C_{1}P_{𝔪_{2}}. In the other direction the result is trivial: if (𝔪_{2}, C_{2}) is a given congruence subgroup and 𝔪_{1} is a multiple of 𝔪_{2}, there exists a unique C_{1} such that (𝔪_{1}, C_{1}) is a congruence subgroup equivalent to (𝔪_{2}, C_{2}), and we have C_{1} = C_{2} ∩ I_{𝔪_{1}}.

Now let (𝔪_{1}, C_{1}) and (𝔪_{2}, C_{2}) be once again arbitrary, but such that (𝔪_{1}, C_{1}) ∼ (𝔪_{2}, C_{2}). Set 𝔫 = gcd(𝔪_{1}, 𝔪_{2}) (the notion of GCD between moduli makes evident sense). Then it can be shown that the above conditions I_{𝔪_{i}} ∩ P_{𝔫} ⊂ C_{i} are satisfied, hence if we set C = C_{1}P_{𝔫} = C_{2}P_{𝔫}, we have (𝔫, C) ∼ (𝔪_{1}, C_{1}) ∼ (𝔪_{2}, C_{2}) so we have defined a GCD (𝔫, C) for congruence subgroups. If we take the GCD of all the congruence subgroups in a given equivalence class, we obtain a congruence subgroup (𝔣, C_{𝔣}) called the conductor of the class, such that every congruence group belonging to the class is of the form (𝔪, C_{𝔣} ∩ I_{𝔪}) for any 𝔪 multiple of 𝔣.

This terminates the description of the “easy” side of class field theory. Note that, although we have used some results of class field theory to motivate the definition of equivalence, the definition itself as well as the proofs that we have omitted (of transitivity and existence of the GCD) are completely self-contained.

3.4. Abelian extensions: the other side of class field theory We now consider the other and most important side of class field theory, Abelian

extensions. Here, we also have an equivalence relation, but which is trivial to define. We will say that two extensions L/K and L′/K are equivalent (or Kisomorphic) if there exists a K-linear field isomorphism between L and L′, i.e. a field isomorphism from L to L′ which leaves K pointwise fixed. Note that if L and L′ are K-isomorphic, they are isomorphic as number fields over ℚ, but the converse is not necessarily true.

From now on, we let L/K be some (finite) Abelian extension of K of degree n and Abelian Galois group G, and we let 𝔪 be a modulus of K which is assumed always to contain the places of K which ramify, i.e. the prime ideals of K which are ramified in L/K as well as the real places of K which ramify (see definition in Section 3.1). We are going to define in two completely different ways TWO congruence subgroups attached to 𝔪 (and L of course, which for the moment is assumed to be fixed). One of the important theorems of class field theory is that these two groups are in fact equal.

(A) The Artin group A_{𝔪}(L/K)

Let 𝔭 be an unramified ideal of K. Then 𝔭 decomposes in L as a product of prime ideals

𝔭ℤ_{L} = ∏_{1≤i≤g} 𝔓_{i} with g = n/f(𝔓_{i}/𝔭) .

Since the extension is Abelian (Galois is sufficient), the 𝔓_{i} are permuted transitively by the Galois group and hence have all the same residual degree f = f(𝔓_{i}/𝔭), and more generally are completely undistinguishable.

Let 𝔓 be one of the ideals 𝔓_{i} above 𝔓. Since 𝔭 is unramified, one can prove that there exists an element σ_{𝔓} ∈ G, called the Frobenius homomorphism, and characterized by the congruence

σ_{𝔓}(x) ≡ x^{N (𝔭)} (mod 𝔓) for all x ∈ ℤ_{L} .

Note that N (𝔭) is the absolute norm of 𝔭 in K/ℚ, or equivalently the cardinality of ℤ_{K}/𝔭, which shows that σ_{𝔓} leaves K pointwise fixed. Furthermore, for a similar reason (but now in ℤ_{L}/𝔓), σ_{𝔓} can be seen to be an element of order exactly equal to f = f(𝔓/𝔭) in G.

Remark. In the case that 𝔭 is ramified, which we do not consider here, then σ_{𝔓} cannot be defined as an element of G, but only as an element of a quotient group D(𝔓)/I(𝔓) where D(𝔓) is the subgroup of elements γ ∈ G such that γ(𝔓) = 𝔓, (the decomposition group), and I(𝔓) the subgroup of elements γ ∈ G such that γ(x) ≡ x (mod 𝔓) for all x ∈ ℤ_{L} (the inertia group). This quotient group is cyclic of order f generated by σ_{𝔓}. In the case that 𝔭 is unramified, the inertia group is trivial, so we do not need to pass to quotients.

If 𝔓′ is another prime above 𝔭, by transitivity of the Galois group action we have 𝔓′ = γ(𝔓) for some γ ∈ G, and it is easy to see that σ_{𝔓′} = γσ_{𝔓}γ^{−1} is conjugate to σ_{𝔓}, thus the conjugacy class of σ_{𝔓} depends only on the base prime 𝔭. In our case, the situation is even simpler since the group G is Abelian, so σ_{𝔓} only depends on 𝔭, and will of course be denoted simply σ_{𝔭}. It is characterized by the congruence

σ_{𝔭}(x) ≡ x^{N (𝔭)} (mod 𝔭ℤ_{L}) for all x ∈ ℤ_{L} .

Recall that 𝔪 was a modulus of K chosen so as to contain all ramified places. We will now define a group homomorphism from I_{𝔪}, the group of fractional ideals coprime to 𝔪, into G, the Galois group of L/K. Let 𝔞 ∈ I_{𝔪}. We can write

𝔞 = ∏_{𝔭|a} 𝔭^{v_{𝔭}(𝔞)}

where the prime ideals 𝔭 do not divide 𝔪, and in particular are unramified in L/K. We set

Art(𝔞) = ∏_{𝔭|a} σ_{𝔭}^{v_{𝔭}(𝔞)}

where the right hand side product is of course taken in the group G. It is clear that this map is well defined and is a group homomorphism. This map is called the Artin map, and Art(𝔞) is often denoted by (\frac{L/K}{𝔞}). The first important theorem of class field theory is the following.

Theorem 3.3.

(1) The Artin map Art is a surjective group homomorphism from I_{𝔪} to G = Gal(L/K).

(2) The kernel of the Artin map is a congruence subgroup, in other words it contains P_{𝔪}.

We will denote by A_{𝔪}(L/K) the kernel of the Artin map, which, by this theorem, is a congruence subgroup modulo 𝔪.

(B) The norm group (or Takagi group) N_{𝔪}(L/K)

We now define another congruence group attached to 𝔪. This group can be defined simply as follows. Denote by I_{𝔪,L} the group of fractional ideals in L which are coprime to 𝔪, i.e. to the extended ideal 𝔪_{0}ℤ_{L} (in other words, I_{𝔪,L} = I_{𝔪ℤ_{L}}). The relative norm N_{L/K} of an ideal of I_{𝔪,L} is clearly an ideal of K coprime to 𝔪, i.e. belongs to I_{𝔪}. Thus, the image group N_{L/K}(I_{𝔪,L}) is a subgroup of I_{𝔪}. However, it is not necessarily a congruence subgroup since it does not always contain P_{𝔪}. Thus, we will set

T_{𝔪}(L/K) = P_{𝔪} N_{L/K}(I_{𝔪,L})

and this is now a congruence subgroup modulo 𝔪 which we will call the norm group (or Takagi group) for the modulus 𝔪 and the extension L/K.

The following proposition gives an easy way to compute the norm group.

Proposition 3.4. If 𝔭 is a prime ideal of K not dividing 𝔪, and if f = f(𝔓/p) is the residual index of a prime ideal above 𝔭 in L, then 𝔭^{f} = N_{L/K}(𝔓) is the smallest power of 𝔭 which belongs to T_{𝔪}(L/K), and T_{𝔪}(L/K) is generated by such ideals (in fact simply by the ideals of degree f equal to 1).

The second very important and difficult theorem of class field theory is the following theorem, called the Artin reciprocity law because it implies more or less easily all the usual reciprocity laws.

Theorem 3.5. Let 𝔪 be a modulus containing all the ramified places of K. Then we have

A_{𝔪}(L/K) = T_{𝔪}(L/K) .

The main point of this theorem (apart from its intrinsic beauty and interest, and the consequences that it has), is that the Artin group A_{𝔪}(L/K) is not easy to compute directly, while the norm group T_{𝔪}(L/K) is easy to compute.

We can also define the conductor of an Abelian extension L/K as follows (we must use some undefined p-adic terminology here). Let 𝔭 be a prime ideal of K and let 𝔓 be some prime ideal of L above 𝔭. We will say that an element x ∈ K_{𝔭}^{∗} is a local norm modulo 𝔭 if there exists y ∈ L_{𝔓}^{∗} such that x = N_{L_{𝔓}/K_{𝔭}}(y) (this does not depend on the chosen 𝔓 above 𝔭). If x ∈ K^{∗}, this is equivalent to requiring that for all n ≥ 0, there exists y_{n} ∈ L^{∗} such that x ≡ N_{L/K}(y_{n}) (mod 𝔭^{n}), or even x/ N_{L/K}(y_{n}) ≡ 1 (mod ^{∗}𝔭^{n}).

We define a non-negative integer k_{𝔭} to be the smallest k ≥ 0 such that any element x ≡ 1 (mod ^{∗}𝔭^{k}) coprime to 𝔭 (this is of course necessary only for k = 0) is a local norm modulo 𝔭. It can be shown that k_{𝔭} exists, and that k_{𝔭} = 0 if and only if 𝔭 is unramified in L/K. We then define

𝔣(L/K) = ∏_{𝔭} 𝔭^{k_{𝔭}}

which is a finite product, since k_{𝔭} ≠ 0 only for the ramified primes. We also include in 𝔣(L/K) all the ramified real places, and this modulus is then called the conductor of the Abelian extension L/K. The prime ideals that divide the conductor are the ramified primes.

Another (much easier) result is the following.

Proposition 3.6.

(1) Let 𝔪 and 𝔫 be moduli both containing the ramified places in L/K, then the congruence subgroups (𝔪, A_{𝔪}(L/K)) and (𝔫, A_{𝔫}(L/K)) are equivalent in the sense of Section 3.3.

(2) The conductor of the equivalence class of the family of congruence subgroups (𝔪, A_{𝔪}(L/K)) is equal to the conductor 𝔣(L/K) of the Abelian extension as defined above.

3.5. Putting both sides together: the Takagi existence theorem We now state the most important and most difficult theorem of class field theory,

due to Takagi.

Theorem 3.7. The map which sends an equivalence class of Abelian extensions L/K to the equivalence class of the congruence subgroup (𝔪, A_{𝔪}(L/K) for any modulus 𝔪 containing all the ramified places of L/K, is a bijection. More precisely, if (𝔪, A_{𝔪}(L/K)) is equivalent to (𝔪′, A_{𝔪′}(L′/K)) in the sense of Section 3.3, then the number fields L and L′ are K-isomorphic. Conversely, if (𝔪, C) is any congruence subgroup, there exists an Abelian extension L/K, unique up to K-isomorphism, such that 𝔪 is a multiple of the conductor of L/K and C = A_{𝔪}(L/K) = T_{𝔪}(L/K).

The proof that the map is injective is not very difficult. On the other hand, the proof of the surjectivity is an existence proof and is very hard, as almost all such existence proofs in mathematics. In fact, we will see that this phenomenon is reflected also in algorithmic practice. The difficulty with the proof mainly lies in the very few tools that we have available to construct Abelian extensions. The known proofs all rely on the method of Kummer extensions (see below), which is elementary but heavy to use, and we will do the same in algorithmic practice.

Thus, given a modulus 𝔪 and a congruence subgroup C modulo 𝔪, thanks to Takagi’s existence theorem, we know that there exists an Abelian extension L/K corresponding to (𝔪, C) under the Takagi map. More precisely, if 𝔪 has been chosen so that it is the conductor (in the sense of Section 3.3) for the equivalence class of (𝔪, C) (and this can easily be done), then there exists an Abelian extension L/K having the following properties (and uniquely characterized by the first two).

Proposition 3.8. With the above notations, we have.

(1) Gal(L/K) ≃ Cl_{𝔪}/\overline{C}, so in particular n = [L : K] = |Cl_{𝔪}/\overline{C}|.

(2) C = P_{𝔪} N_{L/K}(I_{m,L}).

(3) The places of K which ramify in L are exactly the divisors of 𝔪.

(4) If 𝔭 is an unramified prime ideal of K, then the residual index f(𝔓/𝔭) of any prime ideal 𝔓 above 𝔭 is equal to the smallest strictly positive integer f such that 𝔭^{f} ∈ C (hence 𝔭 splits into n/f prime ideals).

Another easy result which we will need is the behavior of class fields under extensions.

Proposition 3.9. As above, let L/K be the Abelian extension of K corresponding to the congruence subgroup (𝔪, C). Let K′ be any (finite) extension of K. Then LK′/K′ is an Abelian extension of K′ corresponding to the congruence subgroup (𝔪ℤ_{K′}, N _{K′/K}^{−1}(C)).

Note that it is false in general that, if 𝔣 is the conductor of L/K, then 𝔣ℤ′_{K} is the conductor of LK′/K′.

The signature (R_{1}, R_{2}) of the number field L can easily be computed simply by looking at the ramified primes. Assuming that 𝔪 is the conductor (it is easy to modify the formula to get a general statement), and denoting by m_{∞} the cardinality of 𝔪_{∞}, we have the formulas

R_{1} = (r_{1} − m_{∞})n and R_{2} = (r_{2} + m_{∞}/2)n .

Note that this implies that m_{∞} · n is always even when 𝔪 is a conductor, and this is not completely immediate, although easy.

In addition, and this is apparently not mentioned in the classical literature, we can also easily give a formula for the discriminant d(L) of L (in fact for a more precise notion called the ideal discriminant), see [CoDiOl], as follows.

For any divisor 𝔫 of 𝔪, let s be the canonical map (which is surjective by the approximation theorem) from Cl_{𝔪} to Cl_{𝔫}. Denote by h_{𝔫} the cardinality of the quotient group Cl_{𝔪}/s(\overline{C}), so that, for example, h_{𝔪} = n. Let v_{𝔭} = v_{𝔭}(𝔪) be the 𝔭-adic valuation of 𝔪. Then we have the following result.

Proposition 3.10. The discriminant of L is given by

d(L) = (−1)^{m_{∞}n/2}d(K)^{n} N (𝔡(L/K))

where 𝔡(L/K) is the ideal (the relative ideal discriminant) defined by 𝔡(L/K) = ∏_{𝔭|𝔪} 𝔭^{a_{𝔭}} with

a_{𝔭} = v_{𝔭}h_{𝔪} − ∑_{k=1}^{v_{𝔭}} h_{𝔪/𝔭^{k}} .

So finally, we have quite good control on the Abelian extension L, except that we do not know an explicit description of L, for example by a relative or absolute equation. This is, of course, the difficult part of Takagi’s theorem, so it is not surprising. We will see later how this problem is solved in algorithmic practice.

4. Computing ray class groups, conductors and discriminants

We stop studying the theory (we will come back to it briefly about Kummer theory later), and come to algorithmic practice.

We fix a base number field K, and we assume that all the invariants of K have been computed, using the method sketched above. In particular, we have computed explicitly the class group and unit group.

Let 𝔪 be a modulus of K. The ultimate goal is to obtain the Abelian extensions L of K of conductor 𝔪 (or dividing 𝔪 if we want). Thanks to the theorems of class field theory, the first, essential, step is to compute the ray class group Cl_{𝔪}(K), and in this section we explain how this is achieved.

Recall the exact sequence

U(K) ⟶ (ℤ_{K}/𝔪)^{∗} ⟶ Cl_{𝔪}(K) ⟶ Cl(K) ⟶ 1

where all the maps are completely explicit. We should be able to obtain the structure of Cl_{𝔪}(K) from this exact sequence, and this is indeed the case. However, for this, we need some preliminary definitions and algorithms on finite Abelian groups.

4.1. Algorithms for finite Abelian groups

We will represent an Abelian group A as we have described the class group Cl(K), i.e. as a pair (A, D_{A}) where A = (α_{i})_{1≤i≤k} is a family of elements of A, D_{A} is a diagonal matrix in SNF with diagonal entries, such that A = ⨁_{1≤i≤k}(ℤ/a_{i}ℤ)α_{i}, so that (A, D_{A}) is in fact a minimal system of generators and relations for A. We may also assume if desired that a_{i} > 1 for all i, since otherwise we can always remove the corresponding generators and entries.

We will say that we have computed the group A algorithmically if, not only we have found A in the form (A, D_{A}), but also if we have described a discrete logarithm algorithm in A which, given α ∈ A, finds the unique integers x_{i} modulo d_{i} such that α = ∏_{1≤i≤k} α_{i}^{x_{i}} in the group A. Of course this is not a mathematically precise definition, since we can always search systematically through all the |A| possibilities for the (x_{i}), but we assume that we have a faster algorithm than this. Recall that we have indeed done so for the class group Cl(K) as a consequence of the solution of the principal ideal problem, and in fact we have done even more since we have found generators of these principal ideals. We will need this also later.

The basic problem on Abelian groups is to compute kernels, images, quotients and group extensions of maps between algorithmically known Abelian groups, (assuming also that the maps are explicitly described of course, we do not need to give a formal definition of this, it will be clear in our appplications). We refer to [Co-DiOl2] for a detailed description of all the algorithms for doing this. To show how the algorithms are actually obtained, we describe in detail the algorithm for computing quotients, and then give briefly with no justification the other algorithms. Since this is not at all difficult, the reader is advised to prove the validity of the other algorithms.

(A) Computing quotients

Let A = (A, D_{A}) and B = (B, D_{B}) be two algorithmically known Abelian groups, and assume that we know an explicit exact sequence

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1

so that C is isomorphic to B/A. We want to compute algorithmically the group C. Let A = (α_{i})_{1≤i≤m}, D_{A} = diag(a_{i})_{1≤i≤m}, B = (β_{i})_{1≤i≤n}, D_{B} = diag(b_{i})_{1≤i≤n}. Since ϕ is surjective, it is clear that the elements C = ϕ(β_{i})_{1≤i≤n} form a gen-

erating set for C. We must find the complete matrix of relations for the set C. If X is a relation for C, we write X as a column vector, and to say that X is a relation can be written as CX = 1, understanding that we use the group operation in the product CX. This means that ϕ(BX) = 1 in C, hence, since the sequence is exact, that BX belongs to the image of ψ, so X is a relation of and only if there exists a vector Y with integer entries such that BX = ψ(AY) = ψ(A)Y. Since we have solved the discrete logarithm problem in B, we can compute an n × m integer matrix P such that ψ(A) = BP. Thus, our condition can be written BX = BP Y, in other words B(X − P Y) = 1. Thus the vector X − P Y is a vector of relations for B, and by definition this means that it is a linear combination of the columns of D_{B}, i.e. that there exists a vector Z with integer entries such that X −P Y = D_{B}Z, or equivalently X = P Y + D_{B}Z.

We have shown that X is a relation for C of and only if it is a ℤ-linear combination of the columns of P and D_{B}. Using the technology of HNF and SNF, it is now easy to terminate. We let M = (P |D_{B}) be the horizontal concatenation of P and D_{B}. By the HNF algorithm we can compute an HNF matrix H whose columns form a ℤ-basis of the ℤ-module generated by the columns of M, and H is still a complete set of relations of C. Applying the SNF algorithm to H, we obtain an SNF matrix D_{C} and unimodular matrices U and V such that H = UD_{C}V, and if we set C′ = CU, then (C′, D_{C}) is a SNF representation of the group C (we can of course as usual remove the components corresponding to 1’s in the diagonal of D_{C}).

It is now also an easy exercise to obtain a discrete logarithm for the group C. The reader will have noticed our constant use of matrix notation for these proofs.

It is extremely practical, although obscured by the fact that the Abelian group operations are denoted multiplicatively.

(B) Computing group extensions

Here we are given an exact sequence of Abelian groups

1 ⟶ A ⟶^{ψ} B ⟶^{ϕ} C ⟶ 1 ,

and we know algorithmically the groups A = (A, D_{A}) and C = (C, D_{C}), as well as the maps ψ and ϕ, and we want to compute algorithmically the group extension B. We proceed as follows (exercise). Let C′ be a set of lifts to B by ϕ of the elements of C, i.e. such that ϕ(C′) = C. Using the discrete logarithm algorithm in A, compute an integer matrix P such that C′D_{C} = ψ(AP). Let B = (ψ(A)|C′). Then B is a set of generators for B, and a complete set of relations for B is given by the columns of the matrix

( \begin{matrix}D_{A} & −P \\ 0 & D_{C} \end{matrix} ) .

We terminate as usual. Since this matrix is already in HNF (at least as far as the triangular form is concerned, we do not care about the off-diagonal entries), we directly apply the SNF algorithm to it, and we obtain algorithmically the group B as (B′, D_{B}) with B′ = BU for the unimodular matrix occuring on the left of the SNF transformation.

(C) Representing subgroups

Before going on to kernels and images, it is necessary to explain how to represent subgroups of a given group. Of course, a subgroup can be represented abstractly as (A, D_{A}) as for any other group, but this is not convenient since it forgets the subgroup structure. Instead, we will do as follows.

Proposition 4.1. Let B = (B, D_{B}) be an Abelian group. Subgroups A of B are in one-to-one correspondence with left divisors of D_{B} in Hermite Normal Form, i.e. with matrices H_{A} such that H_{A} is in HNF and H_{A}^{−1}D_{B} has integer entries. The group A corresponding to a matrix H_{A} is the subgroup of B generated by the elements BH_{A}, i.e. by the elements of B whose discrete logarithm on B are the columns of H_{A}. In particular, the determinant of H_{A} is equal to the index of A in B.

If we really want a Smith Normal Form for A, we note that (BH_{A}, H_{A}^{−1}D_{B}) is a complete system of generators and relations for A, so we apply the SNF algorithm to obtain the SNF form (A, D_{A}).

Conversely, if we are given a subgroup A by an SNF (A, D_{A}) together with an injective group homomorphism ψ from A to B, we can compute the HNF matrix H_{A} associated to ϕ(A) as follows. Using the discrete logarithm algorithm in B, we compute an integral matrix P such that ψ(A) = BP, and H_{A} is simply the Hermite Normal Form of the matrix (P |D_{B}).

(D) Computing images

Let B = (B, D_{B}) and C = (C, D_{C}) be two algorithmically given Abelian groups, let ϕ be a group homomorphism from B to C, and let A be a subgroup of B. We want to compute A′ = ϕ(A) as a subgroup of C. As explained above, A will be given by an HNF matrix H_{A} which is a left divisor of D_{B}. Using the discrete logarithm algorithm in C, we compute an integer matrix P such that ϕ(B) = CP. Then the HNF matrix H_{A′} giving the group A′ = ϕ(A) as a subgroup of C is simply the HNF of the matrix (P H_{A}|D_{B}) (here P H_{A} denotes the matrix product, and as usual | denotes horizontal concatenation). As explained above, if really desired, the SNF of A′ is obtained by applying the SNF algorithm to (CH_{A′}, H_{A′}^{−1}D_{C}).

(E) Computing inverse images and kernels

Let B = (B, D_{B}) and C = (C, D_{C}) be two algorithmically given Abelian groups, let ϕ be a group homomorphism from B to C, and let A be a subgroup of C represented by an HNF matrix H_{C} which is a left divisor of D_{C}, as explained in (C). We want to compute ϕ^{−1}(A) as a subgroup of B in the same representation. We proceed as follows. Using the discrete logarithm algorithm in C, we compute an integral matrix P such that ϕ(B) = CP. If we apply the HNF algorithm to the matrix (P |H_{C}), we obtain a unimodular matrix which we can write in block matrix

form as U = ( \begin{matrix}U_{1} & U_{2} \\ U_{3} & U_{4} \end{matrix} ), and an HNF matrix H which can be discarded, such that

(P |D_{C}) ( \begin{matrix}U_{1} & U_{2} \\ U_{3} & U_{4} \end{matrix} ) = (0|H) .

The desired matrix H_{B} which defines ϕ^{−1}(A) as a subgroup of B is the HNF of the matrix (U_{1}|D_{B}).

In the special case where we want to compute the kernel ϕ^{−1}(1) of ϕ, we apply the above method to H_{C} = D_{C}, which is the matrix representing the group (1) as a subgroup of C.

4.2. Computing (ℤ_{K}/𝔪)^{∗}

We now have tools for handling exact sequences, and in the basic exact sequence involving the ray class group above, we have already computed algorithmically the groups U(K) and Cl(K) (the group U(K) is not finite in general, but only finitely generated, but since it enters only through its image, which is finite, the algorithms that we have given are still valid). The remaining group is (ℤ_{K}/𝔪)^{∗}, which we consider in this section. Although it may look easy, it is in fact quite a hard problem, and I believe there is no formula giving this group algorithmically, but there does exist algorithms to compute it, and this is what we describe here. Note that, even in the case where K = ℚ, it is an elementary but not completely trivial exercise to find the structure of (ℤ/nℤ)^{∗}.

(A) Preliminary reductions

Let 𝔪 = 𝔪_{0}𝔪_{∞} with 𝔪_{0} = ∏_{𝔭} 𝔭^{v_{𝔭}}. An element of (ℤ_{K}/𝔪)^{∗} will be written as a pair (\overline{α}, w), where α ∈ ℤ_{K} is coprime to 𝔪_{0}, and w ∈ (ℤ/2ℤ)^{𝔪_{∞}}. Note that, although the natural map from the elements of ℤ_{K} coprime to 𝔪 into (ℤ_{K}/𝔪)^{∗} is surjective (this is a consequence of the approximation theorem), it is not a good idea to represent elements of (ℤ_{K}/𝔪)^{∗} as (\overline{α}, s(α)), where s(α) ∈ (ℤ/2ℤ)^{𝔪_{∞}} is the vector of signs of α at all the places of 𝔪_{∞}.

For each σ ∈ 𝔪_{∞}, let e_{σ} denote the corresponding canonical basis element of (ℤ/2ℤ)^{𝔪_{∞}} (i.e. all coordinates equal to 0 except at σ where it is equal to 1). By definition, we have

(ℤ_{K}/𝔪)^{∗} = (ℤ_{K}/𝔪_{0})^{∗} ⊕ ⨁_{σ∈𝔪_{∞}}(ℤ/2ℤ)e_{σ} ,

so we are reduced to computing (ℤ_{K}/𝔪_{0})^{∗}. The reader may wonder why I go to such pains in writing what is, after all, a trivial isomorphism, but I recall that isomorphisms must be proscribed in algorithmic practice.

In fact, we have now exactly the same problem. By the Chinese remainder theorem for ideals, we have

(ℤ_{K}/𝔪_{0})^{∗} ≃ ∏_{𝔭|𝔪_{0}}(ℤ_{K}/𝔭^{v_{𝔭}})^{∗} ,

but this is not an equality, so must be improved upon. For this, we need an algorithmic version of the Chinese remainder theorem. We state this as follows (see [CoDiOl]).

Proposition 4.2. Let 𝔞 and 𝔠 be two coprime integral ideals of K, and set 𝔟 = 𝔞𝔠.

(1) We can find algorithmically elements a ∈ 𝔞 and c ∈ 𝔠 such that a + c = 1.

(2) Set 𝔟 = 𝔞𝔠. We have a split exact sequence

1 ⟶ (ℤ_{K}/𝔞)^{∗} ⟶^{ψ} (ℤ_{K}/𝔟)^{∗} ⟶^{ϕ} (ℤ_{K}/𝔠)^{∗} ⟶ 1

where ψ(\overline{α}) = \overline{cα + a}, ϕ(\overline{β}) = \overline{β} and a section σ of ϕ is given by σ(\overline{γ}) = \overline{aγ + c}. (Here denotes the classes in the respective groups, but using the same notation for each will not lead to any confusion as long as we know in which group we work.)

(3) Assume that (ℤ_{K}/𝔞)^{∗} = ⨁(ℤ/a_{i}ℤ)\overline{α_{i}} and (ℤ_{K}/𝔠)^{∗} = ⨁(ℤ/c_{j}ℤ)\overline{γ_{j}}. Then

(ℤ_{K}/𝔟)^{∗} = ⨁(ℤ/a_{i}ℤ)(\overline{cα_{i} + a}) ⊕ ⨁(ℤ/c_{j}ℤ)(\overline{aγ_{j} + c}) .

(Note that this is not quite a representation in SNF, but can be easily transformed into one.)

Applying this proposition inductively, we see that we have reduced the algorithmic computation of (ℤ_{K}/𝔪)^{∗} to that of (ℤ_{K}/𝔭^{k})^{∗} for a positive integer k an a prime ideal 𝔭.

One last reduction can be made, as follows.

Proposition 4.3. Let 𝔭 be a prime ideal of degree f, and let q = p^{f} = |ℤ_{K}/𝔭|. Set G = (ℤ_{K}/𝔭^{k})^{∗}. Let

W = {x ∈ (ℤ_{K}/𝔭^{k})^{∗}/ x^{q−1} = 1} and G_{𝔭} = (1 + 𝔭)/(1 + 𝔭^{k})

(i.e. G_{𝔭} consists of classes of elements of 1+𝔭 modulo the equivalence relation x ∼ y if and only if x − y ∈ 𝔭^{k}. Although 1 + 𝔭 itself is not a group, G_{𝔭} is a group.) Then

(1) W ≃ (ℤ_{K}/𝔭)^{∗}, and in particular W is a cyclic subgroup of order q − 1 of G. More precisely, if \overline{g_{0}} is a generator of (ℤ_{K}/𝔭)^{∗}, then ⌈log_{2}(k)⌉ iterations of g ← g − (g^{q−1} − 1)/((q − 1)g^{q−2}) mod 𝔭^{k} applied to \overline{g_{0}} gives a generator \overline{g} of W.

(2) G_{𝔭} is a p-subgroup of G of order q^{k−1}.

(3) G = W × G_{𝔭}, or in additive notation

(ℤ_{K}/𝔭^{k})^{∗} = (ℤ/(p^{f} − 1)ℤ)\overline{g} ⊕ G_{𝔭} .

Thus, what remains to be done is to compute algorithmically the groups G_{𝔭}. (B) A first idea, the use of 𝔭-adic logarithms A natural idea is to try and convert the multiplicative structure of G_{𝔭} = (1 +

𝔭)/(1+𝔭^{k}) into an additive one by using 𝔭-adic logarithms. More precisely, set A_{p} = 𝔭/𝔭^{k} viewed as an additive group. Let log_{𝔭} be the map from 1 + 𝔭 into K_{𝔭} defined by the usual logarithmic series log_{𝔭}(1 + x) = ∑_{n≥1}(−1)^{n−1}x^{n}/n. Conversely, let exp_{𝔭} be the the map from 𝔭 into K_{𝔭} defined by the usual exponential series exp_{𝔭}(x) = ∑_{n≥0} x^{n}/n!. It can be hoped that, under suitable conditions, these maps are well defined (i.e. that the series converge), and induce inverse bijections from G_{𝔭} onto A_{p}. This is indeed the case, and it can be shown that, if the ramification index e = e(𝔭/p) satisfies e < p − 1, then everything works. We leave this as an excellent exercise for the reader wanting to get acquainted with 𝔭-adic power series.

Note that if p is unramified and larger than 2, the condition e < p−1 is satisfied, so the number of p which do not satisfy this condition is finite. However, they must also be dealt with, so we must use another idea in this case. When the condition is satisfied, we are reduced to the algorithmic computation of the additive group 𝔭/𝔭^{k}, and this can be done very easily (see below).

(C) Computing (ℤ_{K}/𝔭^{k})^{∗} by induction

The method that we will use in general is simple-minded, but works. Instead of considering the logarithm map from (1 + 𝔭)/(1 + 𝔭^{k}) to 𝔭/𝔭^{k}, we simply consider the map sending 1 + x to x. Note that this map is well defined and is a bijection, but the problem is that it is not a group homomorphism in general. However, it is clearly a group homomorphism if k = 2, since in this case

(1 + x)(1 + y) = 1 + x + y + xy ≡ 1 + x + y (mod 𝔭^{2}) .

More generally, if a and b are integers such that a < b ≤ 2a, then the map sending 1 + x to x induces a group isomorphism from (1 + 𝔭^{a})/(1 + 𝔭^{b}) to p^{a}/𝔭^{b}. To compute (1 + 𝔭)/(1 + 𝔭^{k}), we thus proceed by induction, using the technology for group extensions developped above. We compute (1+𝔭)/(1+𝔭^{2}), (1+𝔭^{2})/(1+𝔭^{4}), etc..., up to (1 + 𝔭^{2^{j}})/(1 + 𝔭^{k}) where j is the largest integer such that 2^{j} ≤ k. Now for 1 ≤ i ≤ j consider the exact sequence

1 ⟶ (1 + 𝔭^{2^{i−1}})/(1 + 𝔭^{2^{i}}) ⟶ (1 + 𝔭)/(1 + 𝔭^{2^{i}}) ⟶ (1 + 𝔭)/(1 + 𝔭^{2^{i−1}}) .

Then we may assume inductively that (1 + 𝔭)/(1 + 𝔭^{2^{i−1}}) is known, we compute (1+𝔭^{2^{i−1}})/(1+𝔭^{2^{i}}) as explained above, and hence the method that we have studied for computing group extensions gives us (1 + 𝔭)/(1 + 𝔭^{2^{i−1}}). We terminate by using the above exact sequence on the pair (2^{j}, k) instead of the pair (2^{i−1}, 2^{i}).

(D) Computing 𝔭^{a}/𝔭^{b}

We must finally explain how to compute the additive group 𝔭^{a}/𝔭^{b}. However, this is very easy, and done as follows. Let A (resp. B) be the matrix in HNF giving a ℤ-basis of 𝔭^{a} (resp. 𝔭^{b}) on a fixed integral basis. These matrices can easily be computed, for example by observing that if 𝔭 = pℤ_{K} +αℤ_{K} then 𝔭^{k} = p^{k}ℤ_{K} +α^{k}ℤ_{K} for all non-negative k (exercise). Since 𝔭^{b} ⊂ 𝔭^{a}, the matrix A^{−1}B is a triangular matrix with integer entries whose columns give the representation of elements of 𝔭^{b} as linear combinations of the elements of 𝔭^{a}. If we apply the Smith normal form algorithm to this matrix, we will find unimodular matrices U and V such that UA^{−1}BV = D_{C} is a diagonal matrix in Smith normal form. If (c_{i}) are the diagonal entries of D_{C} and if we set C = AU^{−1}, then the columns of C give the coordinates on the chosen integral basis of elements γ_{i} ∈ 𝔭^{a}, and we have 𝔭^{a}/𝔭^{b} = ⨁(ℤ/c_{i}ℤ)\overline{γ_{i}}, where \overline{γ} denotes the class of γ modulo 𝔭^{b}.

Exercise. Using one of the above methods, determine the structure of G_{𝔭} as an abstract Abelian group for k = 2, k = 3 and k = 4, depending on e = e(𝔭/p), f = f(𝔭/p), the prime p, and perhaps some other arithmetic condition in the number field K (which in the case k ≤ 4 will occur only for k = 4, p = 3 and e = 2).

Note that, if we refer to our algorithms for Abelian groups, it will also be necessary to have at our disposal discrete logarithm algorithms in (ℤ_{K}/𝔪)^{∗}. These can easily be found from the above constructions, except at one point. Given a generator \overline{g_{0}} of the multiplicative group (ℤ_{K}/𝔭)^{∗} of the finite field ℤ_{K}/𝔭, and an element x ∈ (ℤ_{K}/𝔭)^{∗}, find the discrete logarithm of x with respect to \overline{g_{0}}, i.e. an integer m such that x = \overline{g_{0}}^{m}. This is a famous and difficult problem, well studied in the litterature, and we will simply assume that the size of our finite field is not so large as to make the problem intractable in practice.

4.3. Basic computational class field theory

In this section, we explain how to compute ray class groups (for which essentially all the work has been done), congruence subgroups, discriminants and conductors of class fields. This is what I call basic computational class field theory. What will remain to be done, which is much more difficult, is the explicit computation of the class fields, for example by a relative or absolute equation.

(A) Computing the ray class group Cl_{𝔪}(K)

We recall the exact sequence

U(K) ⟶ (ℤ_{K}/𝔪)^{∗} ⟶ Cl_{𝔪}(K) ⟶ Cl(K) ⟶ 1 .

We have computed all the groups in the sequence except the desired group Cl_{𝔪}(K). We can now, either first compute the quotient group (ℤ_{K}/𝔪)^{∗}/ Im(U(K)) using the quotient technique explained above, and then use the 3-term exact sequence

1 ⟶ (ℤ_{K}/𝔪)^{∗}/ Im(U(K) ⟶ Cl_{𝔪}(K) ⟶ Cl(K) ⟶ 1

and the technique of group extensions, or else we can deal with the 4-term exact sequence directly. The fact that U(K) may be infinite is unimportant since it is finitely generated and enters the picture only through its image.

We give a few details, since they are instructive. We will treat the 4-term exact sequence directly. Let (Z_{K}/𝔪)^{∗} = (Z, D_{Z}), Cl(K) = (C, D_{C}), and let (u_{1}, u_{2}, …, u_{r_{1}+r_{2}}) be a generating system for U(K) (we can for example take (u_{1}, …, u_{r_{1}+r_{2}−1}) to be a system of fundamental units and u_{r_{1}+r_{2}} to be a primitive w(K)-th root of unity, but any other choice, or even more than r_{1} + r_{2} generating units, would be OK).

If C = (\overline{𝔞_{i}}), by the approximation theorem, we can find ideals 𝔟_{i} in the same ideal class as 𝔞_{i} and coprime to 𝔪 (this is the reason for the surjectivity of the map from Cl_{𝔪}(K) to Cl(K)). If D_{C} = diag(c_{i}), then 𝔟_{i}^{c_{i}} is a principal ideal. By the solution to the principal ideal problem in Cl(K) (which is stronger than simply the solution of the discrete logarithm problem), we can find α_{i} ∈ K^{∗} (which will be coprime to 𝔪) such that 𝔟_{i}^{c_{i}} = α_{i}ℤ_{K}. Let P be the matrix whose columns are the discrete logarithms in (ℤ_{K}/𝔪)^{∗} of the α_{i}. Finally, let U be the matrix whose ccolumns are the discrete logarithms in (ℤ_{K}/𝔪)^{∗} of the generating units u_{i}. Consider the matrix

M = ( \begin{matrix}U & D_{Z} & −P \\ 0 & 0 & D_{C} \end{matrix} ) .

If Z = (z_{i}) with z_{i} ∈ (ℤ_{K}/𝔪)^{∗} then M is a complete matrix of relations for the generators (\overline{z_{i}}, \overline{𝔟_{i}}) of Cl_{𝔪}(K), and we obtain the complete algorithmic description by performing first a HNF on the matrix M, and then a SNF on the HNF matrix, and obtaining a SNF (B, D_{B}) for the group Cl_{𝔪}(K). We can (and should) also solve the discrete logarithm problem in this way, and in fact as for Cl(K) solve more generally the principal ideal problem (i.e. find also the generators congruent to 1 (mod ^{∗}𝔪) of the ideals of P_{𝔪}).

(B) Computing congruence subgroups

A congruence subgroup C modulo 𝔪 is in natural one-to-one correspondence with its image \overline{C} in Cl_{𝔪}(K), so we want to describe subgroups of Cl_{𝔪}(K). If Cl_{𝔪}(K) = (G, D) where D = diag(d_{i}) with D in SNF, then the description that we have given of subgroups shows that finding subgroups of Cl_{𝔪}(K) is equivalent to finding left divisors H of D in HNF, i.e. HNF matrices H with integer entries such that H^{−1}D also has integer entries.

If we write H = (h_{i,j}) we have h_{i,j} = 0 for i > j, and h_{i,i} must be a positive divisor of d_{i} as can easily be seen. Since 0 ≤ h_{i,j} < h_{i,i} for i < j, we thus have only a finite number of matrices to test. I do not know of an efficient algorithm to find the suitable matrices H. Of course, similarly to the condition that we have given for the diagonal coefficients h_{i,i}, one can give (more and more complicated) conditions for the off-diagonal coefficients h_{i,i+k} for very small k. We leave this as an (uninteresting) exercise for the reader.

(C) Computing discriminants and conductors

Recall that, from Proposition 3.10, we know that if L is the class field corresponding to the equivalence class of the congruence subgroup (𝔪, C), then if n = h_{𝔪} we have

d(L) = (−1)^{m_{∞}n/2}d(K)^{n} N (𝔡(L/K))

where 𝔡(L/K) is the ideal (the relative ideal discriminant) defined by 𝔡(L/K) = ∏_{𝔭|𝔪} 𝔭^{a_{𝔭}} with

a_{𝔭} = v_{𝔭}h_{𝔪} − ∑_{k=1}^{v_{𝔭}} h_{𝔪/𝔭^{k}}

where for any divisor 𝔫 of 𝔪, h_{𝔫} denotes the cardinality of Cl_{𝔫}/s(\overline{C}). The group Cl_{𝔫} is computed as explained at length in the preceding sections. The image of the subgroup s(\overline{C}) is computed as explained above as a Hermite Normal Form matrix H_{𝔫} which left divides the SNF of Cl_{𝔫}, and the determinant of this matrix is equal to the index of s(\overline{C}) in Cl_{𝔫}, i.e. exactly to h_{𝔫}. Thus, it is easy to compute d(L) or the more precise invariant 𝔡(L/K).

Note that, in the special case where we know that 𝔪 is the conductor of the class and that the degree n = h_{𝔪} is a prime, then we must have h_{𝔪/𝔭^{k}} = 1 and so our formula simplifies considerably to give the (classical) formula 𝔡(L/K) = 𝔪^{n−1}.

To compute the conductor of the class of (𝔪, C) is also easy. Since we know that the conductor exists, is unique, and divides every modulus in the class, it follows that we must simply check for every place v in 𝔪 whether there exists a congruence subgroup of the form (𝔪/v, C′) equivalent to (𝔪, C) (the notation 𝔪/v is clear if v is a prime ideal, and of course means that we remove the real embedding v from 𝔪_{∞} if v is an embedding).

From our study of congruence subgroups, this is possible if and only if I_{𝔪}∩P_{𝔪/v} ⊂ C, and if this is true, then C′ is unique and C′ = CP_{𝔪/v}. It is an easy exercise to show that this is equivalent to saying that the canonical surjective map from Cl_{𝔪}/\overline{C} onto Cl_{𝔪/v}/\overline{CP_{𝔪/v}} is an isomorphism, or in other words that h_{𝔪/v} = h_{𝔪}.

Thus, we compute h_{𝔪/v} for each place dividing 𝔪. As soon as for some place v dividing 𝔪 we find that h_{𝔪/v} = h_{𝔪}, we know that 𝔪 is not the conductor, so we replace 𝔪 by 𝔪/v and C by CP_{𝔪/v}. Since in fact we do not really keep C but its image \overline{C} in Cl_{𝔪}, we will replace \overline{C} by s(\overline{C}) computed as explained above. If h_{𝔪/v} < h_{𝔪} for all places v dividing 𝔪, we have found the conductor of the class. In practice, this method is fast.

(D) Computing the Artin group of an Abelian extension

Even though we have not tackled the hard problem of finding an equation for the class field L, we now make an incursion on the difficult side of class field theory, i.e. we now assume given an Abelian extension L of K of degre n, a modulus 𝔪 containing all the ramified places, and we want to compute the Artin group A_{𝔪}(L/K) of the extension. We of course use the fundamental theorem (Artin reciprocity) telling us that A_{𝔪}(L/K) = T_{𝔪}(L/K) is the norm group.

A naive method would be to consider the modulus 𝔪ℤ_{L} of the field L, compute a system of generators of Cl_{𝔪ℤ_{L}}(L), take their norms. Then, up to principal ideals generated by elements congruent to 1 (mod ^{∗}𝔪), this will generate the group T_{𝔪}(L/K). Suitable use of Hermite and Smith normal forms will give the desired group. This method is correct, but has the big disadvantage that we must work in the large field L, compute its class group, unit group, ray class group, etc..., and this is very expensive, and very often impractical.

Luckily, it is not necessary to work in L, we can work essentially in K, as follows. By Proposition 3.4, we know that T_{𝔪}(L/K) is generated by the 𝔭^{f}, where f is the residual index of any prime ideal 𝔓 of L above 𝔭. In fact, although we have not stated it, the result is much stronger, and we can for example restrict to a subset of the prime ideals of density 1.

As in the absolute case, to find the decomposition of 𝔭 in L is easy if the prime ideal 𝔭 does not divide an ideal “index”. Indeed, in this case, we must simply factor a relative polynomial defining the relative extension L/K modulo the prime ideal 𝔭, i.e. in some finite field ℤ_{K}/𝔭, and there are well known methods for doing this.

We do not need to look at the prime ideals dividing the ideal index since this excludes a (small) finite number of prime ideals, so the remaining 𝔭^{f} will still generate T_{𝔪}(L/K).

Finally, we use an essential additional piece of information: we know that the degree of L/K is equal to n, so the index of T_{𝔪}(L/K) in Cl_{𝔪}(K) is n.

We then proceed as follows. Let (C, D_{C}) be the SNF of Cl_{𝔪}(K), and set H ← D_{C}. For each prime ideal 𝔭 which does not divide the index, factor the defining relative polynomial modulo 𝔭, and thus compute the residual degree f of any prime ideal 𝔓 above 𝔭. Let X be the column vector representing the discrete logarithm of 𝔭 on the generators C of Cl_{𝔪}(K). Replace the matrix H by the Hermite normal form of the matrix (H|fX). If the determinant of this new matrix H is equal to n, then H is the HNF representing the subgroup T_{𝔪}(L/K) as a left divisor of D_{C}. Otherwise (i.e. if it is a multiple of n strictly larger than n), go on with the next prime ideal. In this way, we obtain very rapidly the norm group T_{𝔪}(L/K), and hence the Artin group. On the other hand, the direct computation of the Artin group would have been very difficult.

(E) Computing the conductor of an Abelian extension

We stay on the difficult side of class field theory, and keep the same notations. We would now like to compute the conductor of the Abelian extension L/K, as defined in Section 3.4. The definition given there is quite difficult to handle. Luckily, by the main theorems of class field theory, we can instead compute the conductor of an equivalence class of congruence subgroups.

Let 𝔪 be a known multiple of the conductor. We can take for 𝔪 the relative ideal discriminant 𝔡(L/K), which we have not defined (the definition is a straightforward generalization of the absolute case). This discriminant can be computed by relative versions of the round 2 or round 4 algorithms. Using (D) above, compute the norm group T_{𝔪}(L/K) corresponding to this modulus. We thus have a congruence subgroup (𝔪, T_{𝔪}(L/K)) and, by one of the theorems that we have stated above, the conductor of the class of this congruence subgroup is equal to the conductor 𝔣 of the Abelian extension L/K. However, computing the conductor of a class of congruence subgroups is easy (see (C) above), and thus we obtain the conductor 𝔣 as well as the corresponding norm group T_{𝔣}(L/K).

5. Kummer theory

We come to the theoretically and algorithmically most difficult part of class field theory, the construction of the class field L. There are several methods known for doing this. When the base field K is ℚ, then L can always be constructed via cyclotomic fields (this is the Kronecker-Weber theorem, a very special case of the theorem of Takagi). When the base field is an imaginary quadratic field, L can be constructed by using the values of the elliptic j function at quadratic numbers, the function j replacing the exponential function used for ℚ. Both these methods are very efficient.

For a more general base field, the situation is much less satisfactory. To my knowledge, two approaches have been used. The classical one is Kummer theory, which we will describe here. A second, more recent, approach, is the use of Stark’s conjecture and Stark units (see [Rob] for details). I do not explain this, but notice that the use of a conjecture in the construction of L is completely unimportant since once a tentative L is found, it is very easy to show that it is the correct result, simply by computing its conductor and norm group as explained in Sections 4.3 (D) and (E) above, and using the uniqueness of L up to isomorphism.

5.1. The basic theorems of Kummer theory

For any integer n, we let ζ_{n} be any primitive n-th root of unity. We will start by assuming that ζ_{n} ∈ K, and then explain later what must be done when this is not the case. The basic theorem of Kummer theory is the following.

Theorem 5.1. Let n ≥ 1 be an integer, and let K be a number field such that ζ_{n} ∈ K. There is a natural bijection between finite subgroups of K^{∗}/(K^{∗})^{n} and Abelian extensions of K whose Galois group is of exponent dividing n. This bijection is obtained as follows. If B is a finite subgroup of K^{∗}/(K^{∗})^{n}, then the corresponding Abelian extension is obtained by adjoining to K all n-th roots of lifts of elements of B. If L is an Abelian extension of K whose Galois group is of exponent dividing n, then B = ((L^{∗})^{n} ∩ K^{∗})/(K^{∗})^{n}.

Corollary 5.2. Let K be a number field, and n ≥ 1 be an integer such that ζ_{n} ∈ K. Then an extension L/K is a cyclic extension of degree n if and only if there exists α ∈ K^{∗} such that \overline{α} is of order exactly n in K^{∗}/(K^{∗})^{n}, and such that L = K( \sqrt[n]{α}). Furthermore, K( \sqrt[n]{α}) = K( \sqrt[n]{β}) if and only if there exists an integer j coprime to n and γ ∈ K such that β = α^{j}γ^{n}.

Since any Abelian extension of K can be obtained as a compositum of cyclic extensions of prime power degree, to build Abelian extensions it suffices to build cyclic extensions of prime power degree. In turn, these extensions can be built as towers of extensions of prime degree ℓ (although this is not the nicest way to look at such extensions). Thus, we now consider in detail such extensions.

It will be essential to have good control on the ramification of prime ideals in the extension L/K, and in particular on the relative discriminant ideal 𝔡(L/K). The big advantage of Kummer extensions of prime degree is that this ramification can be described completely quite simply (the same thing could be done for prime powers, but the statements would be much more complicated).

Theorem 5.3. Let K be a number field, ℓ a prime number such that ζ_{ℓ} ∈ K, and L = K(\sqrt[ℓ]{α}), where α ∈ K^{∗} \ (K^{∗})^{ℓ}. Let 𝔭 be a prime ideal of ℤ_{K}. We set

e(𝔭/ℓ) = v_{𝔭}(ℓ) = (ℓ − 1)v_{𝔭}(1 − ζ_{ℓ}) ,

i.e. the absolute ramification index of 𝔭 if 𝔭 is above ℓ, and 0 otherwise. (1) Assume that ℓ ∤ v_{𝔭}(α). Then 𝔭 is totally ramified and

v_{𝔭}(𝔡(L/K)) = ℓ − 1 + ℓe(𝔭/ℓ) .

(Recall that e(𝔭/ℓ) = 0 if 𝔭 ∤ ℓ.)

(2) Assume that ℓ | v_{𝔭}(α) and that 𝔭 ∤ ℓ. Then 𝔭 is unramified, and hence v_{𝔭}(𝔡(L/K)) = 0. In addition, 𝔭 is totally split if and only if the congruence

x^{ℓ} ≡ α (mod 𝔭^{1+v_{𝔭}(α)})

has a solution in K, otherwise 𝔭 is inert.

(3) Assume finally that ℓ | v_{𝔭}(α) and that 𝔭 | ℓ. Let a be the largest (possibly infinite) exponent k such that the congruence

x^{ℓ} ≡ α (mod 𝔭^{k+v_{𝔭}(α)})

has a solution. Then:

(s) 𝔭 is totally split if and only if a > e(𝔭/ℓ)ℓ/(ℓ − 1), and in that case we have in fact a = ∞, i.e. the congruence is solvable for all k.

(i) 𝔭 is inert if and only if a = e(𝔭/ℓ)ℓ/(ℓ − 1).

(r) 𝔭 is totally ramified if and only if a < e(𝔭/ℓ)ℓ/(ℓ − 1). In that case, we have

v_{𝔭}(𝔡(L/K)) = ℓ − 1 + ℓe(𝔭/ℓ) − (ℓ − 1)a .

Corollary 5.4. Let K be a number field, ℓ a prime number such that ζ_{ℓ} ∈ K, and L = K(\sqrt[ℓ]{α}), where α ∈ K^{∗} \ (K^{∗})^{ℓ}. Let 𝔭 be a prime ideal of ℤ_{K}. Then

(1) The ideal 𝔭 is unramified in L/K if and only if ℓ | v_{𝔭}(α), and either 𝔭 ∤ ℓ or 𝔭 | ℓ and the congruence

(*)  x^{ℓ} ≡ α (mod 𝔭^{e(𝔭/ℓ)ℓ/(ℓ−1)+v_{𝔭}(α)})

has a solution in K.

(2) The ideal 𝔭 is ramified in L/K if and only if either ℓ ∤ v_{𝔭}(α), or if ℓ | v_{𝔭}(α) and the congruence (*) has no solution in K.

(3) We always have (ℓ − 1) | v_{𝔭}(𝔡(L/K)), and v_{𝔭}(𝔡(L/K)) = ℓ − 1 if and only if ℓ ∤ v_{𝔭}(α) and 𝔭 ∤ ℓ.

Theorem 5.3 and its corollary give complete control on the ramification of prime ideals in L/K, and on the relative discriminant ideal 𝔡(L/K).

5.2. Algorithmic Kummer theory when ζ_{ℓ} ∈ K

We will say two elements α and β belonging to K are Kummer-equivalent if K(\sqrt[ℓ]{α}) = K(\sqrt[ℓ]{β}). By Corollary 5.2, this is equivalent to β = α^{j}γ^{ℓ} for some j coprime to ℓ.

The main algorithmic result is that, up to this equivalence, there is only a finite number of possibilities to choose α such that L = K(\sqrt[ℓ]{α}) is the ray class field corresponding to a given congruence subgroup (𝔪, C). For this, we proceed as follows. Using the methods explained in Section 4, by finding a suitable divisor of 𝔪, we may assume without loss of generality that 𝔪 is the conductor of the extension L/K. Thus, the prime ideals dividing 𝔪 must be ramified in L/K, and the others must be unramified. In addition, recall that thanks to Proposition 3.10, we know the relative ideal discriminant 𝔡(L/K), which in our special case is simply equal to 𝔪^{ℓ−1}.

We divide the prime ideals of K in five sets S_{𝔪,ℓ,1}, S_{𝔪,ℓ,2}, S_{ℓ}, S_{𝔪} and S_{∅} as follows. The prime ideals 𝔭 of S_{𝔪,ℓ,1} (resp. S_{𝔪,ℓ,2}) are those dividing both 𝔪 and ℓ and which satisfy v_{𝔭}(𝔪) = ℓe(𝔭/ℓ)/(ℓ−1)+1 (resp. v_{𝔭}(𝔪) < ℓe(𝔭/ℓ)/(ℓ−1)+1), the prime ideals of S_{ℓ} (resp. S_{𝔪}) are those dividing ℓ but not 𝔪 (resp. 𝔪 but not ℓ), and the prime ideals of S_{∅} are those not dividing 𝔪 or ℓ. We will also set S = S_{𝔪}∪S_{𝔪,ℓ,1}, which is a subset of the set of prime ideals dividing 𝔪. Then, using Corollary 5.4, we get the following necessary conditions on α.

Corollary 5.5. Let K be a number field such that ζ_{ℓ} ∈ K, and let L/K be the ray class field corresponding to the congruence subgroup (𝔪, C), where we assume that 𝔪 is the conductor of L/K and that [L : K] = ℓ. Then, using the above notations, if L = K(\sqrt[ℓ]{α}), the following conditions must be satisfied.

(1) If 𝔭 ∈ S_{𝔪,ℓ,1} then we must have ℓ ∤ v_{𝔭}(α).

(2) If 𝔭 ∈ S_{𝔪,ℓ,2} then we must have ℓ | v_{𝔭}(α) and the largest k such that the

congruence

α ≡ x^{ℓ} (mod 𝔭^{v_{𝔭}(α)+k})

has a solution must be equal to

ℓe(𝔭/ℓ)/(ℓ − 1) + 1 − v_{𝔭}(𝔪) .

(3) If 𝔭 ∈ S_{ℓ}, then we must have ℓ | v_{𝔭}(α) and the congruence

α ≡ x^{ℓ} (mod 𝔭^{v_{𝔭}(α)+e(𝔭/ℓ)ℓ/(ℓ−1)})

has a solution.

(4) If 𝔭 ∈ S_{𝔪}, then we must have ℓ ∤ v_{𝔭}(α). In this case, we necessarily have v_{𝔭}(𝔪) = 1.

(5) If 𝔭 ∈ S_{∅}, then we must have ℓ | v_{𝔭}(α).

(6) If σ ∈ 𝔪_{∞}, then we must have σ(α) < 0.

(7) If σ is a real embedding which is not in 𝔪_{∞}, then we must have σ(α) > 0.

The last two conditions occur only if ℓ = 2, since otherwise the condition ζ_{ℓ} ∈ K implies that K is totally complex, so 𝔪_{∞} = ∅.

To use this corollary in practice, we let (𝔞_{i})_{1≤i≤g} be ideals of K and d_{i} be integers such that

Cl(K) = ⨁_{1≤i≤g}(ℤ/d_{i}ℤ)\overline{𝔞_{i}}

is the Smith normal form of the class group of K. Thanks to the approximation theorem in Dedekind domains, we may assume that the representatives 𝔞_{i} of the ideal classes \overline{𝔞_{i}} are chosen in such a way as to be coprime with anything in sight, here coprime to ℓ and 𝔪. We will make this assumption from now on.

We define non-zero elements α_{i}, β_{𝔭} of K and integers p_{i,𝔭} for 1 ≤ i ≤ g and 𝔭 ∈ S = S_{𝔪} ∪ S_{𝔪,ℓ,1} by the following formulas.

𝔞_{i}^{d_{i}} = α_{i}ℤ_{K} for 1 ≤ i ≤ g .

𝔭 = β_{𝔭} ∏_{1≤i≤g} 𝔞_{i}^{p_{i,𝔭}} for 𝔭 ∈ S .

Note that these elements α_{i} and β_{𝔭}, as well as the p_{i,𝔭}, can be found using the solution to the principal ideal problem. By the assumption made above, the α_{i} are coprime to 𝔪 and ℓ, and the β_{𝔭} are such that v_{𝔮}(β_{𝔭}) is equal to 0 for every 𝔮 | ℓ𝔪 except for 𝔮 = 𝔭 for which it is equal to 1.

Using this, we have:

Corollary 5.6. Keep the same notations as the preceding corollary, and recall that S = S_{𝔪} ∪ S_{𝔪,ℓ,1}. Then, up to Kummer-equivalence, we can choose α of the following form:

α = ϵ ∏_{𝔭∈S} β_{𝔭}^{x_{𝔭}} ∏_{i=1}^{g} α_{i}^{n_{i}} ,

where ϵ is a unit, and with the following additional conditions:

(1) 1 ≤ x_{𝔭} ≤ ℓ − 1, 0 ≤ n_{i} ≤ ℓ − 1.

(2) For 𝔭 ∈ S_{𝔪,ℓ,2}, the largest k such that the congruence α ≡ x^{ℓ} (mod 𝔭^{k}) has a solution must be equal to

ℓe(𝔭/ℓ)/(ℓ − 1) + 1 − v_{𝔭}(𝔪) .

(3) If S is not empty, we may fix any one (but only one) of the x_{𝔭} equal to 1.

(4) The congruence

α ≡ x^{ℓ} (mod ∏_{𝔭∈S_{ℓ}} 𝔭^{e(𝔭/ℓ)ℓ/(ℓ−1)})

has a solution.

(5) For each i such that ℓ | d_{i}, we must have

∑_{𝔭∈S} x_{𝔭}p_{i,𝔭} ≡ 0 (mod ℓ) .

(6) For each i such that ℓ ∤ d_{i}, we must have

n_{i} ≡ d_{i}^{−1} ∑_{𝔭∈S} x_{𝔭}p_{i,𝔭} (mod ℓ)

(which determines n_{i} uniquely since 0 ≤ n_{i} < ℓ).

(7) For each σ ∈ 𝔪_{∞}, σ(α) < 0, while for each real embedding σ ∉ 𝔪_{∞}, we have σ(α) > 0.

As mentioned, these are only necessary conditions on α. However, since up to Kummer-equivalence we can choose ϵ ∈ U(K)/U(K)^{ℓ}, they restrict α to a very small finite set. If α belongs to this finite set, we will know that L_{α} = K(\sqrt[ℓ]{α}) is a cyclic extension of degree ℓ, relative discriminant 𝔡(L/K), and correct signature. Of course there may be several fields L_{α} satisfying all these conditions. To terminate, we compute the conductor and the norm group for each of the possible α in our finite set, and exactly one will be equal to (𝔪, C).

In practice, to find a finite set of suitable α, we proceed as follows. Find all solutions to the linear system modulo ℓ

∑_{𝔭∈S} x_{𝔭}p_{i,𝔭} ≡ 0 (mod ℓ) for all i such that ℓ | d_{i} .

We then let the (x_{𝔭}) range through all the solutions of this system such that all the x_{𝔭} are non-zero, up to projective equivalence, i.e. identifying (x_{𝔭}) and (jx_{𝔭}) modulo ℓ if j is coprime to ℓ. For a given choice of (x_{𝔭}), we can write α = uγ where

γ = ∏_{𝔭∈S} β_{𝔭}^{x_{𝔭}} ∏_{i,ℓ∤d_{i}} α_{i}^{n_{i}}

and

n_{i} = d_{i}^{−1} ∑_{𝔭∈S} x_{𝔭}p_{i,𝔭} ,

d_{i}^{−1} being of course understood modulo ℓ, and where

u = ϵ ∏_{i,ℓ|d_{i}} α_{i}^{n_{i}} .

Let u_{1}, …, u_{r_{1}+r_{2}} be a generating system of units (we may take for example as usual (u_{1}, …, u_{r_{1}+r_{2}−1}) to be a system of fundamental units, and u_{r_{1}+r_{2}} equal to a primitive w(K)-th root of unity). Adjoin to these units what we could call virtual units, i.e. the numbers α_{i} for the i such that ℓ | d_{i}, i.e. set u_{r_{1}+r_{2}+i} = α_{i} for such i, and let s be the total number of u_{i}. All these elements are coprime to 𝔪 and ℓ by our fundamental assumption on the choice of the 𝔞_{i}.

We need to check whether certain congruences of the form x^{ℓ} ≡ α (mod 𝔞) are solvable or not for certain ideals 𝔞 whose prime ideal divisors are all in 𝔪 or ℓ, so are coprime to α. This is the same as x^{ℓ} ≡ uγ (mod 𝔞), where u belongs to the group generated by the u_{i}.

Since our u_{i} are coprime to 𝔪 and ℓ, hence to 𝔞, we can we can compute their discrete logarithm in (ℤ_{K}/𝔞)^{∗} using the methods described in Section 4.2. (As an interesting side remark, we note that the algorithm to compute the structure of (ℤ_{K}/𝔪)^{∗} is used, not only to compute the ray class group Cl_{𝔪}(K), but also to solve congruences necessary to build the associated ray class field, with slightly different ideals.) Putting all these discrete logarithms as columns of a single matrix, we obtain an m × s integer matrix M, where m is the size of the SNF of (ℤ_{K}/𝔞)^{∗}, i.e. the number of cyclic components. On the other hand, let B the column vector representing the discrete logarithm of the known number γ. Then, if u = ∏_{1≤i≤s} u_{i}^{x_{i}}, it is clear that x^{ℓ} ≡ uγ (mod 𝔞) if and only if MX + B ≡ 0 (mod ℓ). Since ℓ is a prime number, this is a linear system in the finite field 𝔽_{ℓ}, so it is easy to solve.

We thus have finished our description of algorithmic Kummer theory when ζ_{ℓ} ∈ K. We now study the general case.

5.3. Kummer theory when ζ_{ℓ} ∉ K

We must now explain what should be done when ζ_{ℓ} ∉ K. The first problem that we have is simply to be able to describe cyclic extensions of degree ℓ of K. Even after this problem is solved, we need to control ramification of prime ideals, and this is very difficult to do directly.

Thus, the only method used in practice is to adjoin to K the ℓ-th root of unity ζ_{ℓ}, thus obtaining a larger field K_{1} = K(ζ_{ℓ}). We will then apply Kummer theory to the field K_{1}, obtaining a cyclic extension L_{1} of K_{1}, of degree ℓ and having suitable properties, and we finally must go back down from L_{1} to the desired extension L. Let us study in detail how this is done.

The basic theorem that we use is the following.

Theorem 5.7. Let K be a number field, and let L be a cyclic extension of K of degree ℓ. Assume that K does not contain ζ_{ℓ}, and let K_{1} = K(ζ_{ℓ}) and L_{1} = L(ζ_{ℓ}). Let g be a primitive root modulo ℓ^{2}.

(1) The extension K_{1}/K is a cyclic extension of degree (ℓ−1)/d for some divisor d of ℓ − 1 different from ℓ − 1, generated by the K-automorphism of K_{1} of order (ℓ − 1)/d defined by τ(ζ_{ℓ}) = ζ_{ℓ}^{g^{d}}.

(2) There exists a β ∈ K_{1} such that if

α = ∏_{0≤a<(ℓ−1)/d} (τ^{a}(β))^{g^{ℓ−1−d(a+1)}} ,

we have L_{1} = K_{1}(θ) with θ = \sqrt[ℓ]{α}).

(3) If we define

τ(θ) = \frac{θ^{g^{d}}}{β^{(g^{ℓ−1}−1)/ℓ}} ,

then τ is a K-automorphism of L_{1} which extends the automorphism τ of K_{1}, and we have the formula

τ^{a}(θ) = θ^{g^{ad}}/ ∏_{i=0}^{a−1}(τ^{i}(β))^{(g^{ℓ−2+a−i}−g^{a−i−1})/ℓ} .

(4) Let

λ = Tr_{L_{1}/L}(θ) = ∑_{0≤a<(ℓ−1)/d} τ^{a}(θ)

where τ^{a}(θ) is given by the above formula. Then L = K(λ). In other words, a relative equation for L/K is given by the polynomial

P (X) = ∏_{0≤j<ℓ}(X − ζ_{ℓ}^{jg^{ad}}τ^{a}(θ)) ∈ K[X] .

For example, if ℓ = 3, d = 1, we take g = 2 and we have α = β^{2}τ(β),, τ(θ) = θ^{2}/β, λ = θ + θ^{2}/β and hence

P (X) = (X −(θ+θ^{2}/β))(X −(ζ_{3}θ+ζ_{3}^{2}θ^{2}/β))(X −(ζ_{3}^{2}θ+ζ_{3}^{4}θ^{2}/β)) = X^{3} −3eX −eu

with e = βτ(β) = N_{K_{1}/K}(β) and u = β + τ(β) = Tr_{K_{1}/K}(β).

Using the above theorem, we can apply algorithmic number theory as developped in the preceding section to find β (the preceding section showed how to find α, but the necessary modifications are straightforward). Note that we use Proposition 3.9 which tells us that the field extension L_{1}/K_{1} corresponds to the congruence subgroup (𝔪ℤ_{K_{1}}, N _{K_{1}/K}^{−1}(C)) if (𝔪, C) was the congruence subgroup corresponding to the extension L/K.

Using a symbolic algebra package, we then compute symbolically the equation P (X) in terms of β as we have just done for ℓ = 3, and we obtain the desired relative equation for L/K. We can then easily obtain the absolute equation using resultants once again (exercise), but this is not always a good idea.

This terminates the algorithmic description of class field theory that we will do here. We end this paper by giving examples and numerical results. To do the examples, we strongly advise the reader to get hold of a system like Pari, which allows to do all the necessary computations very easily.

6. Examples

We work out explicitly two examples, one in the case where ζ_{ℓ} ∈ K, and the other when ζ_{ℓ} ∉ K. Note that some results are not deterministic, thus the intermediate results will not necessarily be the same, although of course isomorphic in some sense. We give on purpose quite non-trivial examples, and in fact the number fields that we will obtain as Abelian extensions are world records for the small size of their discriminants. We terminate by giving an important table.

6.1. Example with ℓ = 2

For our first example, the base field K is defined by a root z of the polynomial x^{6} − x^{5} + 2x^{3} − 2x^{2} + 1. In this field, the prime number 41 splits as the product of three prime ideals of degree 1, and one prime ideal of degree 3. One of the prime ideals of degree 1 is equal to 𝔓_{41} = 41ℤ_{K} +(z +4)ℤ_{K}. The number field K has two real places v_{1} and v_{2}. We take as modulus 𝔪 = 𝔓_{41}v_{1}v_{2} and C = P_{𝔪} as congruence subgroup (i.e. we consider the full ray class field). Using the algorithms of Sections 2 and 4, we find that Cl_{𝔪}(K) is of order 2, hence by Takagi’s existence theorem, that there exists a quadratic extension L of K ramified only at primes above 𝔪, hence totally complex and ramified only at the finite prime 𝔓_{41}, and we compute its relative discriminant to be equal to 𝔓_{41} itself (in the present case, this is trivial). We now want a defining equation for L/K.

Since L/K is quadratic, we do not need to adjoin the ℓ-th roots of unity which are already in K, and hence we have L = K(\sqrt{α}) for some α ∈ ℤ_{K}. Using the algorithms of Section 2, we find (of course, this simplifies things considerably) that K has class number 1, and the solution to the principal ideal problem gives us 𝔓_{41} = βℤ_{K} with (for example) β = z^{5} + 2z^{2} − 2z. Applying Corollary 5.6, we see that α must be of the form α = ϵβ for some unit ϵ. Since we find that 2 is inert in K, the necessary conditions that α must satisfy are that α ≡ x^{2} (mod 2^{2}) has a solution, and v_{1}(α) < 0, v_{2}(α) < 0.

To satisfy the congruence condition, we apply the method explained after Corollary 5.6. Applying the algorithms of Section 2, we find that

(ℤ_{K}/4)^{∗} ≃ (ℤ/126ℤ) × (ℤ/2ℤ)^{5}

with generators (for example) −2z^{5} + z − 2, −1 and −2z^{i} + 1 for 1 ≤ i ≤ 4.

We can choose as generators of units u_{1} = −1, u_{2} = z, u_{3} = z^{3} + 1, u_{4} = z^{4} − z^{3} + z^{2} + z − 1. Using the discrete logarithm algorithm associated to our computation of (ℤ_{K}/4ℤ_{K})^{∗}, we find that the matrix M of discrete logarithms of the units is

M = ( \begin{matrix}0 & 64 & 97 & 11 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ) ,

while the column vector B of the discrete logarithm of β is equal to

B = [68, 0, 1, 1, 0, 0]^{t} .

By Gaussian elimination in ℤ/2ℤ, we see that the column vector X = [0, 0, 1, 1]^{t} is the unique solution modulo 2 to MX + B ≡ 0 (mod 2). Thus if we set

α = βu_{3}^{−1}u_{4}^{−1} = −z^{5} + 2z^{4} − 3z^{2} + 3z ,

the conditions at all the finite primes will be satisfied. The only freedom that we still have is to multiply by a square of a unit. In particular this does not change the signature, i.e. the ramification at infinity. One checks that indeed the real places are ramified, i.e. α satisfies v_{1}(α) < 0 and v_{2}(α) as desired.

Thus L can be defined over K by the equation

X^{2} − (−z^{5} + 2z^{4} − 3z^{2} + 3z) = 0 .

To get the absolute defining equation of L over ℚ, we simply compute the resultant with respect to z of X^{2} − (−z^{5} + 2z^{4} − 3z^{2} + 3z) with the defining polynomial z^{6} − z^{5} + 2z^{3} − 2z^{2} + 1, and we obtain

x^{12} − x^{10} + 2x^{8} + 28x^{6} − 23x^{4} − 47x^{2} + 41

as defining equation for our number field L.

Using polynomial reduction techniques already mentioned, we finally obtain the equation

x^{12} − 2x^{11} + 2x^{10} − x^{9} + 2x^{8} − 5x^{7} + 8x^{6} − 7x^{5} + 4x^{4} − 3x^{3} + 4x^{2} − 3x + 1 .

This example has been found by our group as explained above, and is currently the totally complex field of degree 12 of smallest known discriminant.

6.2. Example with ℓ = 3 and ζ_{ℓ} ∉ K

As a second example, we will take the case of a cubic extension. Here the base field K is defined by a root of the polynomial x^{6} − 2x^{5} + 3x^{4} + x^{2} + 3x + 1. This is a totally complex number field in which 2 is inert, and we choose as modulus 𝔪 the prime ideal 2ℤ_{K} alone, and C = P_{𝔪} (so once again we want the full ray class field). Using the algorithms of Sections 2 and 4, we find that the ordinary class group is trivial, that the ray class group is of order 3, hence that there exists a cubic extension L of K ramified only at 2, and we compute its relative discriminant to be equal to 4 = 2^{2}.

We now want a defining equation for L/K. Since ζ_{3} ∉ K, we must start by adjoining ζ_{3} to K. Thus we set K_{1} = K(ζ_{3}) and L_{1} = L(ζ_{3}). A straightforward computation, followed by polynomial reduction, shows that K_{1} can be defined by a root of the polynomial

P = x^{12} − 2x^{11} + x^{10} − 6x^{9} + 8x^{8} + 7x^{7} + 5x^{6} − 20x^{5} − 2x^{4} + 3x^{3} + 8x^{2} + 3x + 1 .

Applying Theorem 5.7, we see that there exists β ∈ K_{1} such that L_{1} = K_{1}(\sqrt[3]{α}) with α = β^{2}τ(β). In K_{1}, the prime 2 splits as the product of two prime ideals of degree 6, and since we check that K_{1} is principal, they are generated by elements β_{2} and β′_{2} = τ(β_{2}) respectively which can be found using the solution to the principal ideal problem (note that it is much simpler to choose here β′_{2} = τ(β_{2}) here and not any other generator, since we are looking for β and not for α). Since we need α to be of the form β^{2}τ(β) the method explained above shows that we can restrict to β = β_{2}ϵ for some unit ϵ.

We may still have ramification at 3. Thus, we look for a unit ϵ such that, if β = β_{2}ϵ, then α = β^{2}τ(β) is such that the congruence x^{3} ≡ α (mod 𝔞^{3}) has a solution, where 3ℤ_{K_{1}} = 𝔭^{2}𝔭′^{2} for prime ideals 𝔭 and 𝔭′ of degree 3 and 𝔞 = 𝔭𝔭′. Thus, we must find ϵ so that the congruence

x^{3} ≡ β_{2}^{2}τ(β_{2})ϵ^{2}τ(ϵ) (mod 𝔭^{3}𝔭′^{3})

has a solution. Using the algorithm of Section 2, we compute that

(ℤ_{K_{1}}/(𝔭^{3}𝔭′^{3}))^{∗} ≃ (ℤ/78ℤ)^{2} × (ℤ/3ℤ)^{10}

and the corresponding SNF generators. We can then easily find a desired unit ϵ, and one finds that it is unique up to multiplication by cubes of units.

Note that for doing these computations, we must find the action of τ explicitly on K_{1}, and this is easily done if we keep track of how the field K_{1} = K(ζ_{3}) was constructed.

To terminate, we take β = β_{2}ϵ and α = β^{2}τ(β). To find L, we apply the method explained above (where the explicit example of ℓ = 3 was given), i.e. L = K(λ) with λ = θ + θ^{2}/β, where θ is a root of x^{3} − α = 0. It is now easy to find a relative equation for L/K, and hence an absolute equation, which we can then reduce. We find as a reduced equation

x^{18} − x^{17} + 3x^{16} + 2x^{15} − x^{14} + 11x^{13} + 3x^{12} + 3x^{11} + 28x^{10}
− 18x^{9} + 47x^{8} − 27x^{7} + 45x^{6} − 23x^{5} + 27x^{4} − 11x^{3} + 9x^{2} − 2x + 1 .

Note that we have not given explicit values for the different numbers which are involved (the units, β_{2}, β, etc...) because they are not canonical and depend on the way the algorithms are programmed, so the reader will certainly have different values than ours. Only the final reduced equation given below should be similar.

This example has also been found by our group as explained above, and is currently the totally complex field of degree 18 of smallest known discriminant.

6.3. Numerical results

Using these techniques, we have made a large search for interesting number fields. For example, we now have large (more than 10000 fields per signature) tables of degree 8 fields containing a quartic subfield, and hence we know the minimum discriminant for most combinations of signature and Galois group. A more difficult search is to look for number field with the very smallest discriminants. We have seen at the beginning that the discriminant of number fields of degree n tend to infinity. In fact, the result is much stronger. For every signature (r_{1}, r_{2}), there exists a positive constant C(r_{1}, r_{2}) such that for every number field K of signature (r_{1}, r_{2}) we have |d(K)|^{1/n} ≥ C(r_{1}, r_{2}), where n = r_{1}+2r_{2} is the degree of K/ℚ. The early results of Minkowski and successors using the geometry of numbers gave weak results on this constant. Much more recently, using analytic techniques, people like H. Stark, A. Odlyzko and others have found much better values, and in particular very good values if we assume once again the GRH. In the table below, we see that most of the fields that we have found (in small degrees, because in higher degrees in does not make much sense for several reasons) have |d(K)|^{1/n} very close (1% is typical) to the analytic bound. This shows both that these bounds are excellent (assuming of course GRH, otherwise they may simply be too excellent, i.e. false), and that the fields that we have found are very close to optimal, so our technique is good.

In the following table, we give for each even degree up to 32, and each degree divisible by 4 afterwards, the smallest totally complex number field known for that degree (there is no reason to restrict to totally complex, except that it makes the table shorter, and it is also the easiest case). All the fields have been obtained using class field theory as we have explained. Ten of the fields (in degrees 12, 16, 18, 28, 32, 36, 40, 48, 52, 56) have been found only last year by our group (see [CoDiOl]).

From left to right, one finds the absolute degree of L/ℚ, the equation of the base field K, the modulus written as a product of places, where v denotes a real embedding, 𝔓_{p} (resp. 𝔭_{p}) denotes some prime ideal of degree 1 (resp. 2) above p. We then have the discriminant d(L) in factored form, the root discriminant |d(L)|^{1/n}, and finally the percentage over the analytic bounds. We have given equations in degrees 12 and 18, but we do not give the equations in general, since it would be quite unilluminating. Note that we have not succeeded in computing explicitly every equation (the only ones which are missing are in degree 68 and 76), since Kummer theory starts to become very costly when we must adjoin 17-th or 19-th roots of unity.

Degree 2: x, 𝔓_{3}: −3, 1.732, 0.558%. Degree 4: x^{2} − x + 1, 𝔓_{13}: 3^{2} · 13, 3.289, 0.685%. Degree 6: x^{2} − x + 1, 𝔓_{19}: −3^{3} · 19^{2}, 4.622, 0.576%. Degree 8: x^{2} + 1, 𝔓_{17}: 2^{8} · 17^{3}, 5.787, 0.856%. Degree 10: x^{5} − x^{2} + 1, 𝔓_{23}: −7^{2} · 23 · 431^{2}, 6.793, 0.939%. Degree 12: x^{6} − x^{5} + 2x^{3} − 2x^{2} + 1, 𝔓_{41}: 37^{2} · 41 · 857^{2}, 7.666, 0.843%. Degree 14: x^{2} − x + 18, (1): −71^{7}, 8.426, 0.581%. Degree 16: x^{4} − x − 1, 𝔓_{17}𝔓_{37}: 17^{2} · 37^{2} · 283^{4}, 9.179, 1.164%. Degree 18: x^{6} − 2x^{5} + 3x^{4} + x^{2} + 3x + 1, (2): −2^{12} · 23^{6} · 107^{3}, 9.836, 1.378%. Degree 20: x^{4} + 1, 𝔭_{11}: 2^{40} · 11^{8}, 10.438, 1.573%. Degree 22: x^{2} − x + 2, 𝔓_{23}: −7^{11} · 23^{10}, 11.003, 1.854%. Degree 24: x^{4} − x^{3} − x^{2} + x + 1, 𝔓_{397}: 3^{12} · 13^{6} · 397^{5}, 11.441, 1.349%. Degree 26: x^{2} + 1, 𝔓_{53}: −2^{26} · 53^{12}, 12.498, 6.468%. Degree 28: x^{4} + 2x^{2} − 2x + 1, 𝔓_{71}: 2^{28} · 37^{7} · 71^{6}, 12.296, 1.135%. Degree 30: x^{5} − x − 1, 𝔓_{307}: −19^{6} · 151^{6} · 307^{5}, 12.766, 1.721%. Degree 32: x^{4} − x^{3} + 2x + 1, 𝔓_{3}𝔭_{13}: 3^{28} · 7^{8} · 13^{14}, 13.065, 1.135%. Degree 36: x^{4} − x^{3} + 31x^{2} − 24x + 252, (1): 3^{18} · 4057^{9}, 13.823, 1.709%. Degree 40: x^{2} + 2, 𝔓_{3}𝔓′_{3}𝔓_{11}: 2^{60} · 3^{20} · 11^{18}, 14.412, 1.543%. Degree 44: x^{4} − x^{3} + 2x + 1, 𝔓_{463}: 3^{33} · 7^{11} · 463^{10}, 14.960, 1.511%. Degree 48: x^{4} − x^{3} + 4x^{2} + 3x + 9, 𝔭_{2}𝔭_{5}: 2^{16} · 3^{24} · 5^{20} · 13^{24}, 15.386, 1.006%. Degree 52: x^{4} − 2x^{3} + 21x^{2} − 20x + 68, (1): 2^{78} · 1009^{13}, 15.941, 1.626%. Degree 56: x^{4} − x^{3} − 2x + 8, 𝔓_{2}^{3}: 2^{49} · 3^{42} · 241^{14}, 16.472, 2.283%. Degree 60: x^{4} − x^{3} − 2x^{2} + 3, 𝔭_{19}: 3^{30} · 19^{28} · 37^{15}, 16.880, 2.352%. Degree 64: x^{4} − 2x^{3} − 2x + 5, 𝔓_{2}^{3}𝔭_{3}𝔭′_{3}: 2^{128} · 3^{48} · 13^{16}, 17.314, 2.738%. Degree 68: x^{4} − x + 1, 𝔓_{647}: 229^{17} · 647^{16}, 17.838, 3.777%. Degree 72: x^{4} + 1, 𝔓_{577}: 2^{144} · 577^{17}, 17.948, 2.531%. Degree 76: x^{4} − 2x^{3} + 21x^{2} − 20x + 32, (1): 17^{38} · 433^{19}, 18.808, 5.656%. Degree 80: x^{4} + x^{2} − x + 1, 𝔓_{641}: 257^{20} · 641^{19}, 18.583, 2.774%.

References

[Art-Tat] E. Artin and J. Tate, Class field theory, Benjamin, New-York, 1967.

[Bel] K. Belabas, A fast algorithm to compute cubic fields, Math. Comp. (to appear).

[Coh0] H. Cohen, A course in computational algebraic number theory, Graduate Texts in Math., vol. 138, Springer-Verlag, Berlin Heidelberg New-York, 1993.

[Coh1] H. Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. 65 (1996), 1681–1699.

[CoDiOl] H. Cohen, F. Diaz y Diaz and M. Olivier, Computing ray class groups, conductors and discriminants, submitted..

[CoDiOl2] H. Cohen, F. Diaz y Diaz and M. Olivier, Algorithmic methods for finitely generated Abelian groups, submitted..

[DiOl] F. Diaz y Diaz and M. Olivier, Algorithmique algébrique dans les corps de nombres, 53 pages, Etat de la recherche en algorithmique arithmétique, Laboratoire A2X, Talence, 1995.

[Frie] E. Friedman, Analytic formulas for the regulator of a number field, Invent. Math. 98 (1989), 599–622.

[Gras] G. Gras, Théorie du corps de classes global, Université de Besançon, 1973.

[Lang] S. Lang, Algebraic number theory, Addison-Wesley, Reading, 1970.

[Mart] J. Martinet et M. Olivier, Une introduction à la théorie du corps de classes, Ecole Doctorale de Mathématiques de Bordeaux, 1991.

[Poh-Zas] M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Cambridge Uni-

versity Press, Cambridge, 1989.

[Rob] X. Roblot, Unités de Stark et corps de classes de Hilbert, Comptes Rendus Acad. Sci. Paris 323 (1996), 1165–1168.