Math 129: Algebraic Number Theory Lecture 6

William Stein

Tuesday, February 24, 2004

First we will learn how, if p ∈ Z is a prime and O_{K} is the ring of integers of a number field, to write pO_{K} as a product of primes of O_{K}. Then I will sketch the main results and definitions that we will study in detail during the next 2 or 3 lectures. We will cover discriminants and norms of ideals, define the class group of O_{K} and prove that it is finite and computable, and define the group of units of O_{K}, determine its structure, and prove that it is also computable.

1 Factoring Primes

A diagram from [LL93].

“The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.”

–Bill Gates, The Road Ahead, pg. 265

Let K = Q(α) be a number field, and let O_{K} be the ring of integers of K. To employ our geometric intuition, as the Lenstras did on the cover of [LL93], it is helpful to view O_{K} as a one-dimensional scheme

X = Spec(O_{K}) = { all prime ideals of O_{K} }

over

Y = Spec(Z) = {(0)} ∪ {pZ : p ∈ Z is prime }.

There is a natural map π : X → Y that sends a prime ideal 𝔭 ∈ X to 𝔭 ∩ Z ∈ Y. For much more on this point of view, see [EH00, Ch. 2].

Ideals were originally introduced by Kummer because, as we proved last Tuesday, in rings of integers of number fields ideals factor uniquely as products of primes ideals, which is something that is not true for general algebraic integers. (The failure of unique factorization for algebraic integers was used by Liouville to destroy Lamé’s purported 1847 “proof” of Fermat’s Last Theorem.)

If p ∈ Z is a prime number, then the ideal pO_{K} of O_{K} factors uniquely as a product ∏ 𝔭_{i}^{e_{i}}, where the 𝔭_{i} are maximal ideals of O_{K}. We may imagine the decomposition of pO_{K} into prime ideals geometrically as the fiber π^{−1}(pZ) (with multiplicities).

How can we compute π^{−1}(pZ) in practice?

Example 1.1. The following Magma session shows the commands needed to compute the factorization of pO_{K} in Magma for K the number field defined by a root of x^{5} + 7x^{4} + 3x^{2} − x + 1.

> R<x> := PolynomialRing(RationalField());
> K<a> := NumberField(x^5 + 7*x^4 + 3*x^2 - x + 1);
> OK := MaximalOrder(K);
> I := 2*OK;
> Factorization(I);
[
<Principal Prime Ideal of OK
Generator:
[2, 0, 0, 0, 0], 1>
]
> J := 5*OK;
> Factorization(J);
[
<Prime Ideal of OK
Two element generators:
[5, 0, 0, 0, 0]
[2, 1, 0, 0, 0], 1>,
<Prime Ideal of OK
Two element generators:
[5, 0, 0, 0, 0]

[3, 1, 0, 0, 0], 2>,
<Prime Ideal of OK
Two element generators:
[5, 0, 0, 0, 0]
[2, 4, 1, 0, 0], 1>
]
> [K!OK.i : i in [1..5]];
[ 1, a, a^2, a^3, a^4 ]

Thus 2O_{K} is already a prime ideal, and

5O_{K} = (5, 2 + a) · (5, 3 + a)^{2} · (5, 2 + 4a + a^{2}).

Notice that in this example O_{K} = Z[a]. (Warning: There are examples of O_{K} such that O_{K} ≠ Z[a] for any a ∈ O_{K}, as Example 1.6 below illustrates.) When O_{K} = Z[a] it is very easy to factor pO_{K}, as we will see below. The following factorization gives a hint as to why:

x^{5} + 7x^{4} + 3x^{2} − x + 1 ≡ (x + 2) · (x + 3)^{2} · (x^{2} + 4x + 2) (mod 5).

The exponent 2 of (5, 3 + a)^{2} in the factorization of 5O_{K} above suggests “ramification”, in the sense that the cover X → Y has less points (counting their “size”, i.e., their residue class degree) in its fiber over 5 than it has generically. Here’s a suggestive picture:

PSfrag replacements

(5, 2 + 4a + a^{2}) (5, 3 + a)^{2} (5, 2 + a)

5Z 2O_{K} 2Z (0) 3Z 7Z 11Z

Diagram of Spec(O_{K}) → Spec(Z)

1.1 A Method for Factoring that Often Works

Suppose a ∈ O_{K} is such that K = Q(a), and let g(x) be the minimal polynomial of a. Then Z[a] ⊂ O_{K}, and we have a diagram of schemes

\xymatrix{(??) \ar@{^{(}->}[r] \ar[d] & Spec(O_{K}) \ar[d] \\ ⋃ Spec(F_{p}[x]/(\overline{g}_{i}^{e_{i}})) \ar@{^{(}->}[r] \ar[d] & Spec(Z[a]) \ar[d] \\ Spec(F_{p}) \ar@{^{(}->}[r] & Spec(Z)}

where \overline{g} = ∏_{i} \overline{g}_{i}^{e_{i}} is the factorization of the image of g in F_{p}[x].

The cover π : Spec(Z[a]) → Spec(Z) is easy to understand because it is defined by the single equation g(x). To give a maximal ideal 𝔭 of Z[a] such that π(𝔭) = pZ is the same as giving a homomorphism φ : Z[x]/(g) → \overline{F}_{p} (up to automorphisms of the image), which is in turn the same as giving a root of g in \overline{F}_{p} (up to automorphism), which is the same as giving an irreducible factor of the reduction of g modulo p.

Lemma 1.2. Suppose the index of Z[a] in O_{K} is coprime to p. Then the primes 𝔭_{i} in the factorization of pZ[a] do not decompose further going from Z[a] to O_{K}, so finding the prime ideals of Z[a] that contain p yields the factorization of pO_{K}.

Proof. The inclusion map Z[a] ↪ O_{K} is defined by a matrix over Z that has determinant ±[O_{K} : Z[a]], which is coprime to p. The reduction of this matrix modulo p is invertible, so it defines an isomorphism Z[a] ⊗ F_{p} → O_{K} ⊗ F_{p}. Any homomorphism O_{K} → \overline{F}_{p} is the composition of a homomorphism O_{K} → O_{K} ⊗ F_{p} with a homomorphism O_{K} ⊗ F_{p} → \overline{F}_{p}. Since O_{K} ⊗ F_{p} ≅ Z[a] ⊗ F_{p}, the homomorphisms O_{K} → \overline{F}_{p} are in bijection with the homomorphisms Z[a] → \overline{F}_{p}, which proves the lemma.

As suggested in the proof of the lemma, we find all homomorphisms O_{K} → \overline{F}_{p} by finding all homomorphism Z[a] → \overline{F}_{p}. In terms of ideals, if 𝔭 = (g(a), p)Z[a] is a maximal ideal of Z[a], then the ideal 𝔭′ = (g(a), p)O_{K} of O_{K} is also maximal, since

O_{K}/𝔭′ ≅ (O_{K} ⊗ F_{p})/(g(ã)) ≅ (Z[a] ⊗ F_{p})/(g(ã)) ⊂ \overline{F}_{p}.

We formalize the above discussion in the following theorem:

Theorem 1.3. Let f(x) denote the minimal polynomial of a over Q. Suppose that p ∤ [O_{K} : Z[a]] is a prime. Let

\overline{f} = ∏_{i=1}^{t} \overline{f}_{i}^{e_{i}} ∈ F_{p}[x]

where the \overline{f}_{i} are distinct monic irreducible polynomials. Let 𝔭_{i} = (p, f_{i}(a)) where f_{i} ∈ Z[x] is a lift of \overline{f}_{i} in F_{p}[X]. Then

pO_{K} = ∏_{i=1}^{t} 𝔭_{i}^{e_{i}}.

We return to the example from above, in which K = Q(a), where a is a root of x^{5}+7x^{4}+3x^{2}−x+1. According to MAGMA, the maximal order O_{K} has discriminant 2945785:

> Discriminant(MaximalOrder(K));
2945785

The order Z[a] has the same discriminant as O_{K}, so Z[a] = O_{K} and we can apply the above theorem.

> Discriminant(x^5 + 7*x^4 + 3*x^2 - x + 1);
2945785

We have

x^{5} + 7x^{4} + 3x^{2} − x + 1 ≡ (x + 2) · (x + 3)^{2} · (x^{2} + 4x + 2) (mod 5),

which yields the factorization of 5O_{K} given before the theorem.

If we replace a by b = 7a, then the index of Z[b] in O_{K} will be a power of 7, which is coprime to 5, so the above method will still work.

> f:=MinimalPolynomial(7*a);
> f;
x^5 + 49*x^4 + 1029*x^2 - 2401*x + 16807
> Discriminant(f);
235050861175510968365785
> Discriminant(f)/Discriminant(MaximalOrder(K));
79792266297612001    // coprime to 5
> S<t> := PolynomialRing(GF(5));
> Factorization(S!f);
[
    <t + 1, 2>,
    <t + 4, 1>,
    <t^2 + 3*t + 3, 1>
]

Thus 5 factors in O_{K} as

5O_{K} = (5, 7a + 1)^{2} · (5, 7a + 4) · (5, (7a)^{2} + 3(7a) + 3).

If we replace a by b = 5a and try the above algorithm with Z[b], then the method fails because the index of Z[b] in O_{K} is divisible by 5.

   > f:=MinimalPolynomial(5*a);
   > f;
   x^5 + 35*x^4 + 375*x^2 - 625*x + 3125
   > Discriminant(f) / Discriminant(MaximalOrder(K));
   95367431640625    // divisible by 5
   > Factorization(S!f);
   [
       <t, 5>
   ]

1.2 A Method for Factoring that Always Works

There are numbers fields K such that O_{K} is not of the form Z[a] for any a ∈ K. Even worse, Dedekind found a field K such that 2 | [O_{K} : Z[a]] for all a ∈ O_{K}, so there is no choice of a such that Theorem 1.3 can be used to factor 2 for K (see Example 1.6 below).

Most algebraic number theory books do not describe an algorithm for decomposing primes in the general case. Fortunately, Cohen’s book [Coh93, §6.2]) describes how to solve the general problem. The solutions are somewhat surprising, since the algorithms are much more sophisticated than the one suggested by Theorem 1.3. However, these complicated algorithms all run very quickly in practice, even without assuming the maximal order is already known.

For simplicity we consider the following slightly easier problem whose solution contains the key ideas: Let O be any order in O_{K} and let p be a prime of Z. Find the prime ideals of O that contain p.

To go from this special case to the general case, given a prime p that we wish to factor in O_{K}, we find a p-maximal order O, i.e., an order O such that [O_{K} : O] is coprime to p. A p-maximal order can be found very quickly in practice using the “round 2” or “round 4” algorithms. (Remark: Later we will see that to compute O_{K}, we take the sum of p-maximal orders, one for every p such that p^{2} divides Disc(O_{K}). The time-consuming part of this computation of O_{K} is finding the primes p such that p^{2} | Disc(O_{K}), not finding the p-maximal orders. Thus a fast algorithm for factoring integers would not only break many cryptosystems, but would massively speed up computation of the ring of integers of a number field.)

Algorithm 1.4. Suppose O is an order in the ring O_{K} of integers of a number field K. For any prime p ∈ Z, the following (sketch of an) algorithm computes the set of maximal ideals of O that contain p.

Sketch of algorithm. Let K = Q(a) be a number field given by an algebraic integer a as a root of its minimal monic polynomial f of degree n. We assume that an order O has been given by a basis w_{1}, …, w_{n} and that O that contains Z[a]. Each of the following steps can be carried out efficiently using little more than linear algebra over F_{p}. The details are in [Coh93, §6.2.5].

1. [Check if easy] If p ∤ disc(Z[a])/ disc(O) (so p ∤ [O : Z[a]]), then by a slight modification of Theorem 1.3, we easily factor pO.

2. [Compute radical] Let I be the radical of pO, which is the ideal of elements x ∈ O such that x^{m} ∈ pO for some positive integer m. Using linear algebra over the finite field F_{p}, we can quickly compute a basis for I/pO. (We never compute I ⊂ O.)

3. [Compute quotient by radical] Compute an F_{p} basis for

A = O/I = (O/pO)/(I/pO).

The second equality comes from the fact that pO ⊂ I, which is clear by definition. Note that O/pO ≅ O ⊗ F_{p} is obtained by simply reducing the basis w_{1}, …, w_{n} modulo p.

4. [Decompose quotient] The ring A is a finite Artin ring with no nilpotents, so it decomposes as a product A ≅ ∏ F_{p}[x]/g_{i}(x) of fields. We can quickly find such a decomposition explicitly, as described in [Coh93, §6.2.5].

5. [Compute the maximal ideals over p] Each maximal ideal 𝔭_{i} lying over p is the kernel of O → A → F_{p}[x]/g_{i}(x).

The algorithm finds all primes of O that contain the radical I of pO. Every such prime clearly contains p, so to see that the algorithm is correct, we must prove that the primes 𝔭 of O that contain p also contain I. If 𝔭 is a prime of O that contains p, then pO ⊂ 𝔭. If x ∈ I then x^{m} ∈ pO for some m, so x^{m} ∈ 𝔭 which implies that x ∈ 𝔭 by primality of 𝔭. Thus 𝔭 contains I, as required.

1.3 Essential Discriminant Divisors

Definition 1.5. A prime p is an essential discriminant divisor if p | [O_{K} : Z[a]] for every a ∈ O_{K}.

Since [O_{K} : Z[a]] is the absolute value of Disc(f(x))/ Disc(O_{K}), where f(x) is the characteristic polynomial of f(x), an essential discriminant divisor divides the discriminant of the characteristic polynomial of any element of O_{K}.

Example 1.6 (Dedekind). Let K = Q(a) be the cubic field defined by a root a of the polynomial f = x^{3} + x^{2} − 2x + 8. We will use MAGMA, which implements the algorithm described in the previous section, to show that 2 is an essential discriminant divisor for K.

   > K<a> := NumberField(x^3 + x^2 - 2*x + 8);
   > OK := MaximalOrder(K);
   > Factorization(2*OK);
   [
   <Prime Ideal of OK

Basis:
[2 0 0]
[0 1 0]
[0 0 1], 1>,
<Prime Ideal of OK
Basis:
[1 0 1]
[0 1 0]
[0 0 2], 1>,
<Prime Ideal of OK
Basis:
[1 0 1]
[0 1 1]
[0 0 2], 1>
]

Thus 2O_{K} = 𝔭_{1}𝔭_{2}𝔭_{3}, with the 𝔭_{i} distinct. Moreover, one can check that O_{K}/𝔭_{i} ≅ F_{2}. If O_{K} = Z[a] for some a ∈ O_{K} with minimal polynomial g, then \overline{g}(x) ∈ F_{2}[x] must be a product of three distinct linear factors, which is impossible.

2 The Chinese Remainder Theorem

Let O_{K} be the ring of integers of a number field.

Theorem 2.1 (Chinese Remainder Theorem). Suppose I_{1}, …, I_{n} are ideals of O_{K} such that I_{j} + I_{k} = (1) for any i ≠ j. Then the natural map O_{K} → ∏ O_{K}/I_{j} induces an isomorphism

O_{K}/ (∏ I_{j}) → ∏ O_{K}/I_{j}.

Thus if we choose a_{j} ∈ I_{j} then there exists a ∈ O_{K} such that a ≡ a_{j} (mod I_{j}) for j = 1, …, n.

Lemma 2.2. Suppose I, J are nonzero integral ideals in O_{K}. Then there exists a ∈ I such that (a)/I is coprime to J.

The next proposition asserts that every ideal of the ring of integers of a number field can be generated, as an ideal, by two elements.

Proposition 2.3. Suppose I is called an ideal in the ring O_{K} of integers of a number field. Then there exist a, b ∈ O_{K} such that I = (a, b).

3 Discriminants

Let K be a number field of degree n. Then there are n embeddings

σ_{1}, …, σ_{n} : K → C.

Reorder these embeddings so the first r have image R and the remaining s = n − r have image C. Let σ by the product map a ↦ (σ_{1}(a), …, σ_{n}(a)).

Definition 3.1 (Discriminant). Suppose a_{1}, …, a_{n} is a Q-basis of K. The discriminant of a_{1}, …, a_{n} is

Disc(a_{1}, …, a_{n}) = det(Tr(a_{i}a_{j})_{i,j=1,n}).

4 Norms of Ideals

Definition 4.1 (Norm of Fractional Ideal). Suppose I is a fractional ideal of O_{K}. The norm of I is the lattice index

Norm(I) = [O_{K} : I] ∈ Q_{≥0}.

This lattice index is by definition the absolute value of the determinant of any Qlinear automorphism of K that sends O_{K} onto I, or 0 if I = (0).

Proposition 4.2. If I and J are fractional ideals, then

Norm(IJ) = Norm(I) Norm(J).

5 The Class Group

Definition 5.1 (Class Group). Let O_{K} be the ring of integers of a number field K. The class group C_{K} of K is the group of nonzero fractional ideals modulo the sugroup of principal fractional ideals (a), for a ∈ K.

If we let Div(K) denote the group of nonzero fractional ideals, then there is an exact sequence

0 → O_{K}^{∗} → K^{∗} → Div(K) → C_{K} → 0.

Theorem 5.2 (Finiteness of the Class Group). Every ideal class in C_{K} contains an integral ideal of norm at most

\sqrt{| Disc(K)|} · (\frac{4}{π} )^{s} \frac{n!}{n^{n}} ,

where s is the number of complex conjugate embeddings of K. Thus the class group C_{K} of any number field K is finite.

The bound in the theorem is called the Minkowski bound, and I think it is the best known unconditional general bound (though there are better bounds in certain special cases).

5.1 The Group of Units

Definition 5.3 (Unit Group). The group of units U_{K} associated to a number field K is the group of elements of O_{K} that have an inverse in O_{K}.

Proposition 5.4. An element a ∈ K is a unit if and only if Norm(a) = ±1.

Theorem 5.5. The group U_{K} of units of O_{K} is the product of a finite cyclic group of roots of unity with a free abelian group of rank r + s − 1, where r is the number of real embeddings of K and s is the number of complex conjugate pairs of embeddings.

Example 5.6 (Pell’s Equation). The classical Pell’s equation is, given square-free d > 0, to find all positive integer solutions (x, y) to the equation x^{2} − dy^{2} = 1. Note that if x + y\sqrt{d} ∈ Q(\sqrt{d}), then

Norm(x + y\sqrt{d}) = (x + y\sqrt{d})(x − y\sqrt{d}) = x^{2} − dy^{2}.

The solutions to Pell’s equation thus form a finite-index subgroup of the group of units in the ring of integers of Q(\sqrt{d}). Theorem 5.5 implies that for any d the solutions to Pell’s equation form an infinite cyclic group, a fact that takes substantial work to prove using only elementary number theory (for example, using continued fractions).

References

[Coh93] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. MR 94i:11105

[EH00] D. Eisenbud and J. Harris, The geometry of schemes, Springer-Verlag, New York, 2000. MR 2001d:14002

[LL93] A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The development of the number field sieve, Springer-Verlag, Berlin, 1993. MR 96m:11116