This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
O)I/N) of R in terms of an algebraically ordered field such that the non-zero values of
. Hence' = 0 if and only if A.I = ... = A. n = 0, and the elements 1,~, ... , ~n- I are linearly 0 independent over F. An application of the Eisenstein lemma (4.11) yields another proof of the irreducibility of the pVth cyclotomic polynomials over Z(v ~ 0). We observe that the index of the value group of cp in the value group of
g(t) =
n(t
d - 1)It(gld)Eif[t]
(4.3)
dig
of degree
1(t) = t - 1. We give a list ofcJ>m(t) for even m, m,,;; 24 and m = 30 which can be easily computed from (4.3).
m 2
t2 - 1 --=t+ 1 t- 1
4
t4 - 1 _ _ =t 2 t2 _ I
+I
6 8
10
(t I O-I)(t-1) 4 3 2 (t5_1)(t 2 _1)=t - t +t -t+l
Computation of roots of unity
345
12
14
16
(16 _ I -8--1 =(8 ( -
18
((18_1)((3_1) _ 6 3 (t9 _ 1)((6 _ I) - t - t + I
20
(t2°_1)((2_1) 8 6 (tiO _ l)(t 4 _ I) = t - t
22
(t22 I)(t I) = (til - l)(t 2 - I)
24
((24 - l)(t 4 - 1) 8 4 (t12 _1)(t8 _ I) = t - t
30
(t 30 - l)(t 5 - l)(t 3 - 1)((2 - 1) _ 8 7 5 4 3 (t15 _ 1)((10 _ l)(t6 _ I)(t _ 1) - t + t - ( - t - ( + (+ 1
+I
t lO -
+t
4
2
- (
t9 + t8
-
+I
t7
+ t 6 - t 5 + t4
-
t3
+ t2 - t + I
+1
To determine TU(R) it therefore suffices to compute m with tp(m) maximal such that $m(t) has a root, in R. This means' generates a subfield of F, hence we need to determine those mEN, m even, for which tp(m)ln. Since tp is multiplicative (see exercise 5) this is very easy, of course.
List of even mEN satisfying tp(m)lnfor given nE{2,4,6,8, 1O}. The corresponding polynomials $m(t) where listed in (4.4).
n
2
4
6
8
10
m
2,4,6
2,4,6, 8,10,12
2,4,6, 14,18
2,4,6, 8,10,12, 16,20,24,30
2,4,6,22
(4.5)
For n odd we have m = 2, since tp(pk) is even in case pk> 2. Now, the determination of TU(R) is no longer a problem, whence we know how to decide whether $m(t) splits in R[t] for the finitely many possible values of m for which tp(m)ln. This can, for example, be done by p-adic methods (see [12]). We present a different approach which is in general very
346
Units in algebraic number fields
efficient and gives a complete factorization of a polynomial of Z[t] in F[t], F a finite extension field of 10. We note that F[t] is still Euclidean whereas R[t] is usually not even a unique factorization domain. Of course, we must test afterwards whether the obtained factors in F[t] are already contained in R[t]. The idea of this method goes back to van der Waerden. It was subsequently improved by B. Trager [10]. We present it in a version refined for our purposes. To factor a polynomial get) of F[t] we make use of the fact that it is easy to compute greatest common divisors in F[t]. We use this to make g(t) square-free (by computing g(t)/gcd(g(t), g'(t))) and then to compute its irreducible factors by computation of gcds of get) with suitable polynomials of iQ[t]. Also a transition from polynomials of F[t] to ones of iQ[t] via the norm is needed. In iQ[t] it is no problem to factor polynomials applying Berlekamp's method which is implemented in many higher-level program packages like SAC-2 or MACSYMA (compare chapter 3 (3.43) IT.).
Definition (4.6) Let g(t)EF[t] and gU)(t)EFU)[t] (1 ~j ~ n) be the corresponding polynomials over the conjugate fields obtained by applying conjugation to the coefficients of get) only. Then the norm of get) is defined by N(g(t)) = nj= ,g(j)(t). We note that N(g(t))EiQ[t] and that
Lemma (4.8) Let g(t)EF[t] be irreducible. Then N(g(t)) is the power of an irreducible polynomial oj iQ[t].
Proof Let c(t) be the irreducibe factor of N(g(t)) in iQ[t] for which g(t)J c(t) in F[t]. This implies g(j)(t)Jc(t) in F(j)[t] (1 ~j ~ n) and therefore N(g(t))Jc(t)" in iQ[t].
o (4.9) Lemma Let g(t)EF[t] and N(g(t)) both be square-free. Let q 1 (t), ... , qk(t) be the irreducible Jactors of N(g(t)) in iQ[t]. Then n~=, gcd(g(t), qj(t)) is a factorization of get) into irreducible factors in F[t].
Proof Let g, (t), ... , g,(t) be the irreducible factors of get) in F[t]. Since N(g(t)) is square-free we have N(gj(t)) = qj(t) (l ~ i ~ I and suitable j = j(i), 1 ~j ~ k) according to (4.8). An assumption N(gj(t)) = N(gj(t)) for I ~ i <j ~ I yields a
Computation of roots of unity
347
contradiction because of N(gi(t)) N(git)) = N(gi(t)gj(t))IN(g(t)) and N(g(t)) is square-free. Hence, we obtain qi(t) = N(gi(t)) (1 ~ i ~ I) by reordering the factors of N(g(t)), if necessary. Finally, (4.7) yields k = I and we are done because of gcd(git)), N(gi(t)) = 1 for i =1= j. D We have already noted that it is no problem to make g(t)EF[t] square-free. But even then, N(g(t)) is in general not square-free, take for example g(t)EO[t]. Therefore we substitute t by t - krx in get), rxER a generating element for F, k a suitable rational integer.
Lemma (4.10) Let g(t)EF[t] be square-free and F = O(rx). Then there exists kE"Z such that N(g(t - krx)) is square-free. Proof Let PF) (l ~j ~ II, 1 ~ i ~ m = deg(g(t))) be the zeros of gU)(t). Then the zeros of gU)(t - ka(j)) are fJIi) + krxU). Hence, N(g(t - krx)) has multiple roots if for some indices (i I,j I)' (i 2,j2),j 1 =1= j2: m{1l + krx(j,) = Pi2 (h) + krx(h), or
P.
(h) -
p.
Ull
k ='2aU Il _ a(h) " .
(4.11)
Obviously, there are only finitely many possibilities for k such that N(g(t - krx)) is not square-free. D In practice a few trials k = ± I, ± 2, ... suffice to obtain a polynomial get - krx) with square-free norm. Then we can factor this norm in O[t] and obtain the irreducible factors of get - krx) by calculating polynomial gcds in F[t]. This splits get - ka) into irreducible factors in F[t], and, finally, by the reverse substitution t t--t t + ka we obtain the desired factorization of get). So we are done except for two things. One is the computation of the norm of a polynomial. It can be obtained by calculating Res (M.(x), gAt)) with respect to x, where M.(x) denotes the minimal polynomial of a and gx(t) is obtained from get) by substituting x for a (see exercise 2). There is a modular version for the computation of resultants by Collins (see [I] of chapter 4) which is very fast. However, we suggest a different method. For the computation of U(R) it turns out to be of advantage to compute all conjugates of rx up to machine precision (compare also section 5 of this chapter). Then the norm of g(t)ER[t] is calculated by floating point operations, and since we know N(g(t))E"Z[t] the result is obtained by choosing the nearest integers for the coefficients. (For error estimates see section 8.) This is very easy and has the additional advantage that we need only one substitution t t--t t - krx. Namely, from the proof of (4.10) we know that it suffices to choose k different from all possible quotients (4.11), where the numerator is the difference of roots of conjugates of get) and the denominator is the difference of conjugates of a. A lower bound for the absolute value of
348
Units in algebraic number fields
the denominator is easily obtained once we have computed all conjugates of a. An upper bound for the absolute value of the numerator is also easily derived from the coefficients of the polynomials g(j)(t) (1 ~j ~ n) (compare exercise 4). Hence, for g(j)(t) = "L7'= 0 gj(j)t m - j we compute
2max{lgjUlIgo(j)1 + III ~ i ~ m, I ~j ~ n} min {Ia(i) - a(j)111 ~ i <j ~ n}
T'.-
(4.12)
Then every kEN greater than T does the job. The second remark is that we only obtain a factorization of m(t) over F, the factors need not be in R[t]. That we must check in each case separately. Before we give an algorithm for the computation of TU(R) a simple example is given to illustrate the method. Example (4.13) Let F = 10(( - 3)t). Here we already know TU(R) in case R is the maximal order of F from (2.7). (4.5) yields #TU(R)E{2,4,6}. We already computed 6(t) = t 2 - t + 1 in (4.4). Hence, let g(t) = 6(t), 1'1.= ( - 3)i. From (4.11) we conclude k = 1 and compute
g(t - a) = t 2
2at + 1'1. 2
-
=t2 N(g(t - a)) = (t 2
=
-
t4 -
= (t 2
- t +a + I + 2a)t + (ex - 2), (I + 2a)t + (a - 2))(t 2 2t 3 + 9t 2 - 8t + 7 t + I )(t 2 - ( + 7),
(l
-
(I
+ 21i)t + (Ii -
gcd (g(t - a), t 2
-
1+ (- 3)t t + 1) = t - --2--'
gcd (g(t - a), (2
-
(
2))
1+ 3(-3)i
+ 7) = t - ---2---'
Therefore 6(t) splits in F, but - for example - not in £'[( # TU(OF) = 6,#TU(£'[( -3)i]) = 2.
W].
Hence,
Remarks (4.14) In case R is the maximal order of F, a splitting of m(t) over F is also one over OF' since the roots of
Algorithm for the computation of TU( R)
Input. The rank n of RI£', a generating equation f(t)
=0
with root aER
349
Computation of roots of unity
such that .Q(R) = iQ(IX), and a module basis WI"'" W of Rover 71.. n splits into n = s + 2t, the number of real, respectively complex, II
conjugates of IX. Output. mE Nand ",(t) such that TU(R) is generated by the primitive mth roots of unity ( with m{O = O. Step 1. (R not totally complex). For s > 0 set m <- 2, 2(t) <- t + I and terminate, else go to 2. Step 2. (Determine possible m). Compute a complete list l! of candidates for m (see exercise 6). Step 3. (Computation of TU(R)). Determine mEl! maximal such that m(t) has a linear factor in R[t] and terminate. (4.16)
Remarks
(i) For s > 0 we must necessarily have m = 2, since any primitive mth root of unity is not in IR in case m> 2. (ii) The successive powers of a primitive mth root of unity ( form an integral basis for the ring of integers in iQ((). That was shown in chapter 4 (5.10). Hence, in many cases the discriminant composition formula, chapter 2 (9.29a), can be used to remove some elements m of l! from the list of candidates in addition to step 2. (iii) The tools for step 3 were developed in (4.6)-(4.14).
Exercises I. Prove lemma (4.1). 2. Let F = O(ex) be an algebraic number field of degree n, and let M .(t)EO[t] be the minimal polynomial of ex. Then there are three different methods for the computation of the norm of
'" Y= Lyjex",-j
(m";;n-I,{/iEO,O";;i";;m).
;=0
Set y(I):= I,7'=ogjt m - j and let Mg be the right regular representation of Y with respect to the basis I, ex, ... , exn - I of F. Using N(g) = nj= I g(j) as definition prove N(y) = det Mg = Res (M.(t), {J(t)). Convince yourself that this result remains valid if y = y(y) is a polynomial of F[y]. 3. Compute TU(R) with both methods of this section for R = J::[p], P a zero of fIt) = t 4 + 4t 3 + 5t 2 + 2t + I. (For example, p = (- 2 + 3! + (-I)t)/2 is a zero off.) 4. Let fIt) = t n + a1t n- 1 + ... + anEC[t]. The companion matrix M f = (mij)EC" X " of f is defined via mij =
I [ - an + I
o
for j= i-I - j
for j = n otherwise
n)}
(2,,;; i,,;; (I,,;; i";; n)
.
350
Units in algebraic n.umber fields
Prove: (a) det(t1 n - M f) = f(t). (b) The eigenvalues of M f are precisely the zeros of f(t). (c) Any zero x off(t) satisfies the estimate Ixl ~ max {Iail + I - !5 in l1 ~ i ~ n}. 5. Prove: (a) cp(pk) = pk - pk-I for kEN, p a prime number. (b) cp(apk) = cp(a)cp(pk) for a, kEN, p a prime number with pIa. (Hint: The natural numbers x subject to I ~ x ~ pka which are prime to a and divisible by pare in I-I-correspondence to the natural numbers y subject to 1 ~ y ~ pk - I a which are prime to a.) (c) cp(ab) = cp(a)cp(b) for a, bE N subject to gcd (a, b) = I. Hence, cp is said to be multiplicative. 6. Use the result of exercise 5 to develop an algorithm which determines for given XEN all mEN subject to m even and cp(m)lx. 7. Develop an algorithm to decide whether two algebraic number fields F I , F2 are isomorphic. (Hint: Try to factorize a generating polynomial for F2 over Fd
5.5. Computation of independent units In this section we describe procedures for computing a maximal set of = s + t - 1 independent units in R. We derive them from lattice points in suitable convex regions of IRn. This process is similar to the one which we used to prove the existence of r independent units in section 2. But Minkowski's Convex Body Theorem (and - as a consequence - chapter 3, theorem (4.6)) just guarantees the existence of non-trivial Jattice points and does not yield an efficient method of computation. For the latter we must choose the convex point sets in an appropriate way. We suggest consideration of special parallelotopes or ellipsoids centered at the origin. This also guarantees that the lattice points found in this way correspond to elements of R of bounded norm. Performing division on these elements in R whenever possible we get elements of small absolute norm very rapidly and thus necessarily associate elements among them. These provide units which then need to be tested for independency. In the sequel we fix a Z-basis WI'"'' Wn of R. Then there is the bijective mapping r
(5.1) It can be extended to an injective mapping of F into IR n, if necessary. We discuss the cases of parallelotopes and of ellipsoids as suitable point sets separately.
351
Computation of independent units
Method I: parallelotopes. The basic parallelotope
Il:= {x =(x
l , ..
·,xnYEIR"I-1 ~ Xi ~ 1, 1 ~ i ~ n}
(5.2)
obviously contains non-trivial lattice points of lL n and also satisfies the premises of Minkowski's Convex Body Theorem. For each xElL" n n we have
B is the upper bound for the absolute norms of all elements of R which will be constructed. Usually q> - I (n n lL") will not provide a maximal set of
independent units. (But compare example (5.11) and exercise 3 of section 6.) Therefore we also consider suitable transforms of n. The transformations 'I' have to be chosen in a way such that the image 'I'(n) still satisfies the premises of Minkowski's Convex Body Theorem, that 'I'(n)n lL" can easily be computed, and that the absolute norms of elements of q> - I ('I'(n) n lL") stay bounded. To satisfy the first two conditions we choose 'I' to be linear of determinant ± 1. To fulfill the third we take 'I' as the regular representation matrix M ro of an element wER\lL multiplied by a suitable constant. Namely, for WER its right regular representation M ",ElL'lX" is defined by (WI'"'' w")w
= (WI'"'' w")M w (compare chapter 2 (3.25a».
(5.4)
As a trivial consequence we obtain (see exercise 2 of section 4)
(5.5)
N(w)=detM w'
The linear transformation 'I' = 'I' w is then given by IN(w)l- II" M w with respect to the basis WI>'''' w .. Obviously, 'I'w satisfies the first property required, i.e. '1'", is linear of det 'I' w = ± 1, hence 'I' w(n) is an O-symmetric parallelotope of volume 2". Also the absolute norms of elements <XEq> - 1('1'w(n) n lLn) are bounded by B because of
n(w):= 'I'w(n) = {IN(w)I-I/" MroXEIR"I- 1 ~ Xi ~ 1, 1 ~ i ~ n},
(5.6)
and
n (IN(wWl/nl(wV), ... ,w~j)Mwx)1 n
j= 1
=IN(wWl
n"
Iw(j)(wY), .. ·,w~)xl
j= I n
=nlx'(wy>, ... ,w~),I~B
for-l~xi~l,
l~i~n.
j= I
It remains to show how we can easily determine 'I' w(II)nlLn. By chapter 3
352
Units in algebraic number fields
(2.7) we compute unimodular matrices U""U;;,I such that M~Uw=:N,. is in Hermite normal form. We recall that Nco is a lower triangular matrix, hence the product of its diagonal elements nii (I ~ i ~ n) is - up to sign - N(w). Elementary integral calculations yield a lower triangular matrix B,.EZ'/xII such that (5.7) M~U ",B", = diag(IN(w)I, ... , IN(w)l). Namely, if we denote the entries of N "" B", by nij, bjj, respectively, (5.7) is equivalent to
L: k= "
JijIN(w)l=
L: njkbkj k=j j
njkb kj =
I
(I ~i,j~n).
(5.8)
Let us assume that we have already computed bij subject to (0;: =jo+ I nkk)lbjoj for fixed ioEZ""o and 1 ~j ~ n. Then (5.8) yields in case i = io + I ~ n: for j = i:b jj = IN(w)l/njjEZ\{O}, for j < i:
for j > i: b jj
= 0; .
hence, we can compute bij subject to bij(O;:=j+ I nkk)-I EZ for i = io + I, 1 ~j ~ n. Thus B",EZ" X " is obtained successively. Let C =(cl"'" e,,)' be a lattice point ofO(w). Then there is x =(Xl>'" ,X")'EIR" subject to -I ~Xi~ 1 (I ~i~n) such that c=IN(w)I-I/IIMwx, and also d = U~c is in Z". Multiplication by B!. yields B~d = IN(w)IC"-I)f"X, hence each cEO(w)nZ" is obtained upon multiplication by (U.;;I)' from a solution dEZ" of II
-IN(w)IC"-I)/"~
L djbjj~IN(w)IC"-l)/"
(i= I, ... ,n).
(5.9)
j=j
Since the ith inequality of (5.9) contains only the coordinates d j , ••• , d", all integral solutions of (5.9) can easily be computed by determining all integers dj solving the ith inequality for each (n - i) - tuple (d j + 1"'" d") already obtained (i = n, n - I, ... , I). Each solution d of (5.9) then is multiplied by (U;;,I)' to obtain all lattice points c ofO(w)nZ": c = (U';; I )'d.
(5.10)
Before we discuss the processing of the integers cp -1(O(w)n Z") we should consider the preceding computations more thoroughly. Let us remember that we started fixing an integral basis WI>""W" of R. The choice of WI, .•• ,W" is of strong influence on the amount of necessary computations, since the size of B of (5.3) is directly affected by it. Let us demonstrate this by a simple but impressive example.
Example (5.11) t t Let R = Z[6 ]. For WI = 1, W 2 = 6 we easily compute B= 6 (see also exercise 5).
Computation of independent units
353
But if we choose WI = 1, W 2 = 2 + 6 t , we obtain B = 5. The corresponding parallelotope contains the lattice point (3, 1)'. We fix W 2 and take cp - 1 «3, 1)') = 3 + 6 t as new basis element W l ' This not only yields B = 3, a much better bound, but also the new basic parallelotope contains cp(e) = CP(WI + w 2) = cp(5 + 2(6)t) as a lattice point, e being the fundamental unit of R. Of course, we would like to choose WI'"'' WII to make B as small as possible. Unfortunately there is no solution for that task as far as we know. Even for the easiest case of a real quadratic number field that problem is about as difficult as solving Pell's equation directly which just means determining the fundamental unit (see exercise 5). From that result we conclude that it will be rather hopeless to look for an optimal ~-basis of R such that B of (5.3) is minimal. On the other hand it suggests to search for basis elements Wi (1 ~ i ~ n) of small norm. Since such a basis is also difficult to determine we instead take a reduced ~-basis of R with respect to the length
(5.12) Because of the inequality between arithmetic and geometric means we obtain (5.13) from which we conclude that elements rt.ER of small length also have small norm. We note that a ~-basis of R which is only pairwise or LLL-reduced (see chapter 3) in general suffices for our purposes. Such a basis can be computed very quickly starting from an arbitrary ~-basis of R. The use of such bases was of great advantage in [6]. Not only was the amount of computation time drastically reduced but also the coefficients of the obtained fundamental units became much smaller, sometimes by several powers of ten. Even for some totally real sextic fields we obtained all five fundamental units from the basis parallelotope II when we used a reduced basis (compare table 6.1 of the appendix). Another comment must be made about the choice of the transforming element WER. It is clear that WE~ would yield Mw=diag(w, ... ,w) and therefore ll(w) = ll. But within R\~ the choice of W is completely free. We would like to choose W such that ll(w) contains many new lattice points. Unfortunately we don't know how to determine w for that purpose. From our experience in computing units we suggest the choice of an element w of small absolute norm and then a few consecutive powers of that element for transforming II and then to switch to another w. Jhis method has several advantages. Elements w of small absolute norm are stored anyway and are therefore always at hand. If w is of small absolute norm, usually the entries of M ware small, too, and the entries of the first few powers of M w still fit
354
Units in algebraic number fields
into one computer word. Also the use of powers M~d = Mrok diminishes the calculations necessary for computing U wk, BWk (see [5]). We note that the choice of transforming elements w should still be investigated in greater detail. See also exercise 6. A final remark concerns the computation of n(w)n ~ •. The method discussed in (5.5)-(5.10) is indeed very simple. All computations (except for 1N(w)l<· - 1)/.) are done in the rational integers and are easily programmable. However, solving (5.9) recursively is not always optimal. In many cases the matrix M~U wand therefore Bro are sparse matrices. Namely, quite often we find for N w: njj = 1 (1 :::;:; i < n), n.n = 1N(w)1 and therefore the entries of N w ofT the diagonal are zero except for the last row. It is easy to see that the same holds for the matrix Bro. Hence, in this case (5.9) becomes
-IN(w)I<·-I)/.:::;:; ddN(w)1 + d.b.!:::;:; IN(w)I(·-I)/. -I N(w)I<· -1)/· :::;:; dn :::;:; IN(w)I<·-I)/..
(1:::;:; i <
n),}
5.14 (
)
In case IN(w)1 is large the recursive solution of (5.14) requires a lot of computation time since only very few ofthe d. in the interval [O,IN(w)I(·-I)/.] can be extended to a vector d satisfying all inequalities. We set k:= 1N(w)I<·-I)/. and note that we can assume d. ~ 0 since we need consider only one solution vector of each pair ± d.
Straightforward algorithm for solving (5.14)
(5.15)
Input. k, b. j (1 :::;:; i :::;:; n). Output. All solutions dE~· of (5.14) with d. ~ O. Step 1. (Initialization). Set d.+-O, L+- - k/IN(w)l, U +- - L, E+-b •• _I/IN(w)l. Step 2. (Does solution d. _ I exist?). In case LU J ~ L go to 4. Step 3. (Increase d.). Set d. +- d. + 1. For d. > k terminate, else set L +- L - E, U +- U - E and go to 2. Step 4. ((dIlA,_I) extendable?). For i= I, ... ,n-l, compute L j+-( -k-d.b.j)/IN(w)l, Uj+-(k -d.bnj)/IN(w)1 and for LUd
r
Remark Algorithm (5.15) requires about 3LkJ arithmetic operations (in steps 3,4) if (5.14) has few solutions and k is much larger than n.
However, for large k we can do better. To solve (5.14) efficiently in that case we transform the problem , suitably. The crucial part is of course calculating the solutions of one pair of inequalities, for example the possibilities for (d._I,d.) corresponding to steps 1-3 of algorithm (5.15). We therefore fix
355
Computation of independent units
the index i (1 ~ i ~ n - 1) in the sequel. We note that bnj ~ 0 because of the matrix N w being in Hermite normal form. Our assumption d" ~ 0 also yields dj ~ O. Setting ko:= II N(w)l(n - 1)/" j, y:= ko - dn we obtain the equivalent inequalities (lbn;!-I)ko~IN(w)ldj+lb,,;!y~(lbn;!+
I)ko,
O~y~ko.
(5.16)
Without loss of generality we can assume Ibn;! > 0 since the case of Beo being a diagonal matrix is trivial and occurs rarely. (But see exercise \.) Because of dj ~ 0 we can drop the condition y ~ ko in case Ib,,;! > ko' Finally, for Ibn;! ~ 2ko all solutions of (5.16) are given explicitly in the following lemma.
Lemma (5,\7) Let (5.16) be given with Ibn;! ~ 2k o. For each djEZ"o with dj ~ (Ibn;! + I)ko/I N(w)1 there are solutions y subject to (5.\6) and all solutions of (5.16) are obtained in this way. The proof is straightforward and left as an exercise to the reader. It remains to solve a pair of inequalities of type j ~ ax
+ by ~ k
(5.18)
for given a,b,j,kEZ"O subject to a>b>k-j~O in X,YEZ"o. Obviously, x, y are bounded from above by Lk/aj, Lk/b j, respectively. We can divide a by b to obtain analogous inequalities with smaller coefficients:
We do this until one of the coefficients becomes less than or equal to k - j. Then the solutions of the last pair of inequalities are computed as in (5.17). The following two lemmata show that this process is correct, i.e. the solutions of the different inequalities are in I-I-correspondence. The underlying idea for this is to consider the range for possible solutions x.
Lemma (5.\9) Letj,k,a,b,s,tEZ"o, a>b, r:=a-La/bJb, s~t~Lk/aJ, r>k-j~O. Then the solutions (x, y)' E(Z "0)2 of j ~ ax + by ~ k subject to s ~ x ~ t and the -rt)/bl ~ u ~ Uk -rs)/bj solutions (u, V)'E(Z"~2 ofj ~ bu + rv~ k subject to are in I-I-correspondence.
ru
Proof It is easily seen that each solution (x, y) with s ~ x ~ t yields a solution (u, v) with 0 ~ S':= rt)/bl ~ u ~ Uk - rs)/bj =:t upon setting u = y + La/bjx, v = x. If, on the other hand, (U,V)'E(Z,,0)2 satisfies j ~ bu + rv ~ k and
ru -
356
Units in algebraic number fields
s ~ u ~ t, we set x = v, y = u -
La/bJv and get
o Therefore we can apply Euclid's algorithm to the pair (a, b) of (5.18) as long as the remainder is larger than the difference k - j. What happens when it finally becomes smaller? ~mma
(~~
°
Let a> b > 0, k ~ j ~ 0, t ~ s ~ be integers subject to l(j - at)!bJ ~ 0, b > k - j, and r:= a -la/bJb ~ k - j. Then for each UE~ satisfying rt)/bl ~ u ~ Uk - rs)/bJ there is a VE~;'o subject to j ~ bu + rv ~ k, s ~ v ~ t, and each such pair (u, v) yields a solution x = v, y = u -la/bJv ~ of j ~ ax + by ~ k satisfying s ~ x ~ t.
ru -
°
Proof
ru -
Because of k - bL(k - rs)/b] ~ rs, j - b rt)/b1 ~ rt, we obtain for every u in the interval [r U- rt)/b 1, L(k - rs)/b J]: k ~ bu + rs, bu + rt ~ j, and because of r ~ k - j for each such u there exists (at least one) v, s ~ v ~ t, satisfying j ~ bu + rv ~ k. The rest of the proof is by similar arguments as in (5.19).
o Before we now develop an algorithm solving (5.18) we need to be a little more explicit about the necessary computations. At each step i we assume to have an inequality j ~ ajXj + bjYj ~ k together with bounds Sj, t j, Sj ~ Xj ~ tj ~ Lk/ad. According to (5.19) we compute qj:= La;/b;J, rj:= aj - qjb j,
aj+ 1 =bj, bj + 1 =rj, ( Xj+I)=(qj Yj+
I
1
°1)(Xj), Yj
Finally, if b. ~ k - j for the first time we must compute XI' YI for all solutions
357
Computation of independent units
Xm
Vj:= (1' ~) Vk - 2 • ••• 'V I = U nG:). For
YII' This is done efficiently in the following way. We set
(I ~i~n-I) for abbreviation and define U k := Vk (2 ~ k ~ n). Obviously, Un is unimodular and satisfies (;~)
Un = (~~
I
~!) we have
Algorithm solving j ~ ax + by ~ k for x, YElL"o
(5.21)
Input: Integers a, b, j, k satisfying k ~ j ~ 0, a> b > O. Output: All pairs (x, y)'E(lL"of satisfying j ~ ax + by ~ k, respectively, 'No solution' if none exists. Step I: (Initialization). Set i +-- I, aj +-- a, bj +-- b, Sj +-- 0, tj +-- Lk/a J, U j +-- (~ ?). Step 2: (bj > k - j?). In case bj ~ k - j go to 4. Step 3: (Long division of a, b). Set qj +-- Laib;J, rj +-- aj - qjb j. Set i +-- i + I, aj+--b j _ l , bj+--rj_ 1 Uj+--(qiil ~)Uj_I' Sj+--rU-bjtj_I)/ajl, t j+-- Uk - bjsj_I)/a;j. In case Sj> tj terminate with 'No solution', otherwise go to 2. Step 4: (Print solutions). For each uElL, Sj ~ U ~ tj compute all vElL such that Sj_1 ~ v ~ t j_ 1 andj ~ aju + bjV ~ k. For each such pair (~) print solution G) = Uj-I(~). Remarks (5.22) (i) In step 4 solutions always exist according to (5.17) and (5.20). (ii) This algorithm is an improvement of the one given in [5]. It requires only one-third of the arithmetic operations of the latter to proceed from level i to i + 1. (iii) To exclude the superfluous solution (0, k o) of (5.16) it is advisable to consider the case So = 0 in step 1 separately and then to proceed with So = 1. Method II: ellipsoids Again we apply (3.8) in the case A = RA = R, k = I. However, there is the problem that we do not know realistic bounds (3.3) for the conjugates of the elements of bounded norm which we are looking for. Hence, we omit (3.8d) and modify (3.8g) to:
Irjl ~ m
Irjol = m, (5.23) positive integer. The initial value is m = 1 of course. If all
(1 ~j ~ n)
and there is an indexjo such that
where m denotes a lattice points of all ellipsoids (3.8e) have been determined for a fixed value of m, then we increase m by 1 and proceed until a maximal set of independent units has been determined. We remark that the condition hoi = m guarantees that no ellipsoid is considered twice. From (3. lOb) we know that the norms ofthe elements found
358
Units in algebraic number fields
as lattice points are bounded by 1 + y in absolute value. The appropriate choice of y was discussed at the end of section 3. On the other hand, we can also choose y in such a way that the obtained ellipsoids always contain non-zero lattice points. By Minkowski's Convex Body Theorem we find by an easy calculation that a choice of (nI2)!
y
{ ~ -1 + (~)'" Idll (l~\ nn 2" _n_
2
) I
.
for n even for n odd
(5.24)
is sufficient for that purpose (see exercise 4). Of course, this can not be recommended if the absolute value of the discriminant of R is large. Method II has the advantage that it proceeds in a systematic way. Hence, it is guaranteed to provide a maximal set of independent units. Moreover, the procedure of increasing m makes it likely that not only independent but fundamental units are detected. After we showed how to produce sufficiently many elements of R of bounded norm we need to consider the processing of such elements once they have been computed. Let xER be the last element obtained from the parallelotope under consideration. We assume that the elements determined earlier are stored in some array X which contains nx elements of R of bounded norm at the moment. The corresponding norms - respectively their absolute values - are stored in an array X N • Moreover, we need auxiliary arrays i, iN of fix elements each. The initial values are nx = fix = 0, of course. Algorithmfor comparing x with stored elements of small absolute norm (5.25) Input. xER of absolute norm N x> 1, arrays X, X Noflength nx as described above. Output. X, X N, nx and/or units B 1 , ... , Bp. Step 1. (Initialization). Set fix +- 0, k +- 0, p +- 0. Step 2. (X completely searched?). Set k +- k + 1. For k > nx go to 6. Step 3. (Next element of X). Set a+- X(k), N« +- X N(k). For N« > N x go to 5. Step 4. (Compare X(k), x for XN(k) ~ N x ). For m:= N)NAlL go to 2. For p:= x/a¢R go to 2. For m = 1 set p+- p + 1, Bp+- Pand go to 7. For m > 1 set x +- p, N x+- m, k +- and go to 2. Step 5. (Compare X(k), x for X N(k) > N x). For m:= N IN All go to 2. For p:=a/x¢R go to 2. For i=k, ... ,n x -1 set X(l)+-X(l+ 1), X N(l) +- X N(l + 1), nx +- nx - 1. Then set fix +- fix + 1, i(fi x ) +- p, i N(fix) +- m, and go to 4. Step 6. (Insert x into X). Set nx+-nx+ 1, X(nx)+-x, XN(nx)+-N x .
°
Regulator bounds and index estimates
359
Step 7. (Decrease X) For fix =0 terminate. Else set x <- X(tl x ), N x <- X N(fi X )' fix<-fix-l, k<-O and go to 2. The processing of the units obtained from (5.25) will be discussed in section 7 of this chapter. At this stage it is enough to know that we can produce as many units as we may need by this method. Of course, all units of the output belonging to TU(R) will be eliminated. Extensive computations have shown that it is not recommendable to process all x found via the parallelotopes to (5.25) but only those among them whose absolute norm is less than 10000. (The bound B of (5.3) can of course be much larger.) More advanced techniques also involving the ideal factorization of the involved algebraic integers are generally too complicated for unit computations. They are recommended of course, if also the class number of F is to be determined. These refined methods will be discussed in chapter 6.
1.
2.
Exercises Compute n(w)n£:" in R = £:[a] for w = a6 and a a zero of t 3 -7t -7 = O. Let a be a zero of t 3 - t - 1 = 0 and R = £:[a]. Compute n(w)n £:" for w = (a + 2)5
with algorithms (5.15) and (5.21) and compare the number of arithmetic operations of both methods. (It cannot be recommended to do this exercise without a pocket calculator - preferably a programmable one.) 3. Compute an independent unit in R = £:[14t] with the methods of this section. 4. Prove that a choice of y according to (5.24) guarantees that each ellipsoid (J.8e) contains a non-zero lattice point. 5. Let R = £: + £:mt, mE£:,,2 square-free. To choose a basis WI = a + bmt, W 2 =e+dm t for R which minimizes B of (5.3) means to solve min {max {I(xI(a + bmt) + x 2(e
+ dmt))(xI(a - bmt) + x 2(e - dmt)) II
-I ~Xj~ I, i= 1,2}la,b,e,dE£:, ad-be= ±I}. Show that this requires us to solve min {max {I( - a + e)2 - m( -b + d)21, I(a
+ ef - m(b + d)21, K I, K 2}1
a,b,e,dE£:, ad - be =
± I}
K j := {I- m/(N(wj))I I
in case.l(ae - mbd)/N(wj)l ~ I, otherWise
for
i = \,2.
6. Show that for any BE U(R) there is an element WER such that "'(el) = epee), i.e. epee) is in the transformed parallelotope. Hence, in principle each unit can be obtained as a lattice point in a suitable transform of the basic parallelotope.
5.6. Regulator bounds and index estimates In order to obtain an upper bound for the index of the computed subgroup U.(R) in the whole unit group U(R) we interpret this index as a ,"l-module
Units in algebraic number fields
360
index. Namely, by taking logarithms the multiplicative structure of U(R) becomes an additive one. This obvious procedure is used in most textbooks already in the course of the proof of Dirichlet's Theorem. We consider two mappings of U(R) into logarithmic space: L 1: U(R)~lRs+t: el-+(CIIOgle(1ll, ... ,Cs+tIOgle(s+t)I)',} L 2: U(R)~lRr : el-+(c l logle(l)l, ... ,cr logle(rl l)t,
wherec.={' J 2
forl""j""s
else
(6.1 )
•
The following properties of L j (i = 1,2) are obvious: (a) L j(el1) = Lj(E) + L j(l1) for all e, I1E U(R), (b) Ker(Lj(U(R))) = TU(R),
(6.2)
r
(c) cs+tlogle(s+tll = -
L cjlogle(jll
j= 1
for the coordinates of
L1(E) (eEU(R».
The next result is not quite so obvious but it will turn out to be of great use later on. Lemma (6.3) Let U.(R):= TU(R) x <e l >x ... X <Er >be a subgroup offinite index in U(R). Then Lj(ej) (1 ~j ~ r) are IR-linearly independent (i = 1,2). LI(el)t, ... , L1(e r)' and (cl, ... ,cs+t)' form a basis oflR s+t. Proof Let E1, ... ,Er be a system of fundamental units of U(R). There is MEN and al'vE71. (1 ~ Ii, v ~ r) such that IE~I = In~= 1e~'I. Obviously, the matrix A:= (1/ M)(a".)1 ""P.'' ' , is invertible. On the other hand U(R) contains (independent) units 11 I' ... , I1r for which II1~Vll < 1, 111::'ll> 1 (1 ~ v ~ s + t, 1 ~ Ii ~ r,li"# v). Analogously there is a matrix BEGL(r,71.) transforming E1, ... ,Er into 111, ... ,l1r up to roots of unity. Therefore we obtain (
L2(:I1I)') = BA Lil1r)'
(L2~Edt)
=:c
L 2(e r)'
with a regular matrix BA. Hence, it suffices to show that L 2(11 1), ... , L 2(l1r) are IR-linearly independent which is equivalent to det (C) "# O. Let us assume that the columns of C are linearly dependent. Then there exist t 1"'" trEIR subject to tk:= max {t;l 1 ~ i ~ r} > 0 and LJ= 1ticjlogll1!ill). ""i"", = O. Considering the kth coordinate we get the contradiction r
0=
r
L tjcj logll1Vll = j=1 L t j c logll1Vl l + tkck logl'1kkl l j=1 j
Hk
Regulator bounds and index estimates
~
tkCk log 1'1~k)1
+
'361
r
L tkCj log I'1~j)1 = t k( -cs+,log I'1~S+I)1) > O. j= I
Uk
Therefore L 2 ('1 d, ... , L 2 ('1r) are IR-linearly independent implying that L 2 (e 1 ), ... , L 2 (e r ) and also L1(ed, ... , LI (e r ) are IR-linearly independent. To prove the second statement of the lemma it suffices to show that the vector (c I' ... , CS + IYis IR-linearly independent from LI (e 1), ... , Ll (e r ). If it were not, there would bea presentation (c I, .. "CS+1t = Ll= I tjLI(ej)(tjEIR, 1 ~ i ~ r, max {Itj 111 ~ i ~ r} > 0). But then addition of the coordinates yields the contradiction s+t
s+2t=
s+t
r
L Cj= j=lj=1 L L tjcjlogleF)1 j=1
o Corollary 1 (6.4) Let U,(R) be a subgroup of U(R) of finite index. Then Lj(U,(R» is a free ~ -module of rank r (i = 1, 2). Corollary 2 Let U,(R) be a subgroup of U(R) of finite index. Then (U(R): U,(R» = d(L 2(U,(R»)/d(L 2(U(R»).
(6.5)
Proof (6.4) is obvious. For the proof of (6.5) we note that (L 2 (U(R»:L 2 (U,(R))) = (U(R): U.(R» follows from the homomorphism theorems of group theory. 0 Then chapter 3 (3.6) is applied. Definition (6.6) Let U,(R):= TU(R) x <e l >x ... x <er >be a subgroup of U(R) offinite index. Then the mesh d(L 2(U,(R») is called the regulator Reg (Ut(R» of Ut(R). In case R = CI(~, .Q(R» the regulator of U(R) is also called the regulator of the field F = .Q(R). We denote it by Reg F , or in short by R F •
At the present state of our computations of U(R) we assume that we already calculated independent units e l , ... , er generating a subgroup Ut(R) of finite index up to roots of unity. Now we can calculate Reg(U,(R» from Reg (U.(R» = abs(det(cjlogleF)I)I';i,j.;r) and obtain an upper bound for the index
(U(R)' U (R» = Reg (U.(R» " Reg(U(R»
U nits in algebraic number fields
362
once we know a lower bound for Reg(U(R)). To derive such a lower bound is the goal of the rest of this section. We apply the tools of chapter 3, namely, following Remak [7] we consider n
L (logleUll)2 j~
(eEU(R)).
(6.7)
I
Representing e by fundamental units this becomes a positive definite quadratic form. The determinant of this quadratic form is essentially Reg (U(R)). Thus we get a lower bound for the regulator of U(R) by chapter 3 (3.34), as soon as we have derived a lower bound for (6.7). Let us fix a system of fundamental units E I , ... , E, of U(R). Each eE U(R) then has a (unique) representation by E I, ... , E, and some element of TU(R). Hence, for le(j)1 (1 ~j ~ n) we obtain
,
L xjlogIE/j)1
10gle(j)I=
Using the constants cj (1 n
s+t
j=1
j~1
(XjE~, 1 ~i~,., 1 ~j~n).
(6.8)
I
j=
~j~s+t)
of(6.1) we convert (6.7):
L (logle(j)1)2 = L cilogle(j)1)2 ,
=
L j.j~
(cs-+\cjcj+bijc)logle(i)llogle(j)1 I
,
-. L
"'V~ I
q"vx"xv'
This shows that (6.7) is indeed a quadratic form. It is positive definite since (6.7) is always non-negative and becomes zero only in case all conjugates of e are of absolute value 1. But then e is in TU(R) because of (2.5), hence (6.7) vanishes only in case of XI = ... = x, = O. The next step will be the computation of the determinant of the quadratic form. It is easily seen that the matrix equation (q"v)1 .;".\..;, =
(Ck
log IE~k) 1)1 .;".k.;,(dj.j)1 ';;j.;,(c,log IE~)I)I .;,.• .;,
is satisfied for 1: -1 d jj = cs-+,I + uijcj
(1
..
)
~ l,j ~,. .
The evaluation of the corresponding determinants yields det (qj) = Reg (U(R))22 -'n because ofLI=1 Cj=n-c s +" ni~~ Cj-I =2-' and exercise 1.
(6.9)
363
Regulator bounds and index estimates
In view of chapter 3 (3.34) it remains to give a lower bound for (6.7) in case BEU(R)\TU(R). This will be done by analytic methods. We set (6.1 0) and then minimize II
I. xJ
j~
(6.11a)
1
subject to suitable side conditions coming from the properties of B of U(R). Obviously, we can require (6.11 b) because of IN(B)I = 1. But then a criterion which excludes the solution = 0 is most important. The image of R under the mapping
XI = ... = XII
t/I: R -t 1R": Wf-+(w(1), ... ,w(S),
} 21 Rew(s+ 1), 21 Imw(s+1), ... ,21 Rew(s+/), 21 1m
W(S+/»)'
(6.12) is a lattice t/I(R) of mesh Id(R)I. For the lattice vectors t/I(w) the usual Euclidean norm in 1R" is (6.13)
It is no problem to compute the successive minima of t/I(R) with respect to II II by chapter 3 (3.36). Usually it suffices to calculate only M I ' M 2, M 3 which coincide with 1It/I(wdIl 2, II t/I(w 2 ) 11 2, 11t/I(w3)11 2 for a reduced basis t/I(w l ), ••• , t/I(w ll ) of t/I(R) (compare chapter 3 (3.32)). And a reduced basis for R was already used in the preceding section. It is easily seen that MI
=n
for t/I(1).
(6.14)
Namely, every wER, w #- 0, satisfies IN(w)1 ~ 1, hence T 2(w) ~ n by the inequality between arithmetic and geometric means. The same argument yields
II t/I(w) II = n1¢>wETU(R).
(6.15)
This implies that a basis of R consisting of roots of unity WI' •.• , WII satisfies I t/I(w j ) 112 = M j = n (1 ~ i ~ n). And this happens in all cyclotomic fields. On the other hand, for TU(R) = {± I} we get M 2 > n and for n = s we even have M 2 ~ (3j2)n [8] (note that T 2 (w) = Tr (W 2)EZ in this case).
Remark (6.16) For BE U(R)\ TU(R) we always have II t/I(B) 112 ~ M 2. However, in case (1 + 51)j2E U(R), for example, M 2 ~ 3(nj2) independently of the discriminant of R. Therefore, in case of .Q(R) having proper subfields, higher
364
Units in algebraic number fields
successive minima usually must be taken into consideration to obtain a good lower bound for (6.7).
Theorem Let M*:= min {T2(w)lwEU(R)\TU(R)} eE U(R)\ TU(R) satisfies
= Tz(w*).
Then
(6.17) M* > nand
Proof We set x/= log le(j) I (I ~j ~ n) and minimize. II
f(x):=
L1 xJ
j=
subject to 2,'1= 1 Xj = 0 and 2,'1= 1 e2xj ~ M*. A vector XEIR which satisfies both side conditions is called a feasible solution. Obviously, there are feasible solutions x, for example those corresponding to units eER\ TU(R). Now (6.15) implies M* > n. Hence, each feasible x must have positive and negative coordinates. Let YEIR" be feasible. Then each xEIR" withf(x) ~f(Y) necessarily satisfies - f(y)t ~ Xj ~f(y)t (I ~j ~ n). Hence, the existence of a global minimum is guaranteed. If the minimum is attained, let us say for the vector Z, the second side condition must be active, i.e. 2,'J= 1 e 2zJ = M*. Otherwise we could decrease the maximal coordinate of Z by a very small constant b and increase the minimal coordinate of z by b to obtain a new feasible solution Z6 with f(Z6)
2xj + A + 2/le 2Xj = 0 (l ~j ~ n),
L"
e2xJ
= M*.
j= 1
For fixed /l the function g(x):= X + /le 2x with derivative g'(x) = 1 + 2/le 2x is strictly increasing for /l > O. But then g(x) = - AI2 cannot have different solutions for X < 0 and x> 0, a contradiction to our conclusion from above. Hence, /l must be negative and we get exactly two solutions u > 0, v < of g(x) = - A12. This means that we must minimize su 2 + (n - S)V2 for u > 0, v < 0 and sE{I, .. . ,n -I} subject to su+(n-s)v=O and se 2"+(n-s)e 2v =M*. Since e and e- 1 yield the same valuef(x) we can assume s ~ n12. We substitute v=sul(s-n) and u=«n-s)/2)logy (YEIR>l) and obtain the equivalent problem: Minimize tns(n - s) (log y)2 subject to G(s, y):= sy" - M* yS + n - s = 0
°
for
(s,Y)E[nI2,n-l] x(l,oo).
Because
of
Gy(s'Y)=>(Syll-~SM*Ys)
the function G(s, y) has exactly one minimum for fixed s. Hence, G(s, 1) = n - M* < yields exactly one solution y:= h(s) of G(s, y) = for fixed
°
°
Regulator bounds and index estimates
s. We shall prove that F(s):= s(n - s) (Iogy)2 increasing in s. Namely,
= s(n -
365
s) (Iogh(S))2 is strictly
F'(s) = (log h(s))2(n - 2s) + s(n - s)2 10g h(s) h'(s) h(s)
= log h(S)((n _ 2s) log h(s) + 2s(n -
h(s)
s) (_ Gis, y))) Gy(s, y)
I (( n- 2s)1 ogy- 2(n - s)(y"- I -IOgYM*YS) . =ogy ny" - M*yS Because of y > I, G(s, y) = 0 and the denominator in the last term being positive we obtain the following chain of equivalent inequalities F'(s) > 0,
(n - 2s) log y(ny" - M*yS) > 2(n - s)(y" - I -logyM*y'), logy(n(n - 2s)y" + nM*yS) > 2(n - s)(y" - I), log y,,/2 > (y"- 1)/(y" + I). Setting z = y" we need to prove t log z > (z - 1)/(z + I) for z > I. But this last inequality follows from 1/(2t) > 2/(1 + t)2 (t> I) by integrating both sides from 1 to z. Thus we have shown that (n/4)s(n - s) (log h(S))2 is strongly increasing (even for 1 ~ s ~ n - 1 (!)). Because of our assumption s ~ n/2 the minimum is attained for s = n/2. But then G(s, y) = 0 implies 2 y" _ -- M* y,,/2 + 1 = 0, n i.e. M* (M*2 )1/2 y"/2 =--+ - 2 - - 1 , n n
o
and the theorem is proved.
Remarks
(6.18)
(i) M* can be easily calculated by chapter 3 (3.15). (ii) In case n is odd the estimate of (6.17) can be slightly improved by computing y> I from G((n+ 1)/2,y)=0 and then (n/4)F((n+ 1)/2) as a lower bound for Ii=1 (Iogle(jlI)2. (iii) It seems somewhat puzzling that we can stipulate s = n/2 even though F(s) is strictly increasing in [I, n - I]. The reason for this is that e and e- 1 yield the same value Ii = 1 (log Ie(jl If but I tjJ(e) II and II tjJ(e - I) II can differ substantially. Corollary The regulator Reg(U(R)) of R satisfies the inequality
Reg (U(R))
~
(MoYr-r2'n-I)I/2.
(6.19)
Units in algebraic number fields
366
Proof By (6.7), (6.9), chapter 3 (3.34), (6.17).
o (6.20)
Examples
(i) Let R = £'[p], p a zero of t 3 + (2 - 2t - I = O. The conjugates of p are p = p(I) = 1.247,p(2) = -0.445, p(3) = -1.802 and the discriminant of R is dR = 49. A reduced basis is WI = I, W2 = p, W3 = p2 - 2 yielding the successive minima M I = 3, M 2 = M 3 = 5. These data yield a lower regulator bound Reg (U(R)) ~ 0.45 which is very close to the real value Reg(U(R)) = 0.53. (ii) Let R = £'[p], p a zero of t 4 - 2t 2 - I = O. A reduced basis of R is WI = I, W2 = p, W3 = p3 - 2p, W4 = p2 - I providing M 1= 4, M 2 = M 3 = 4(2)t, M 4 = 8. Hence, we obtain 0.48 as a lower regulator bound whereas Reg(U(R)) = 1.35. If O(R) contains proper subfields then the estimate (6.19) for Reg (U(R)) may be too weak. In that case we need to take into consideration higher successive minima of (6.7). Let M1EIR>o be minimal such that there are independent units el, ... ,e; in U(R) satisfying lIej112::;;M1 (I ::;;j::;;i) for some natural number i. As in (6.17) we set Mo;:=(n/4)(log((MNn)+((M12/n2)-1)1/2))2 and obtain
(6.21)
Theorem
The proof hinges essentially on chapter 3 (3.34) and is left as an easy exercise to the reader. Though (6.21) yields the best lower bound for Reg(U(R)) which we know so far we also present some other explicit bounds at the end of this section. From the results of [3], [4] we excerpt Reg(U(R))
~
((
3(1og(ld(R)l/n"))2 (n - I)n(n + I) - 6t
)r -2'
ny~
)1/2
(6.22)
in case O(R) is primitive over iQ and Id(R)1 > n°. Moreover, for t = 0 and n::;; II the constant n" in (6.22) can be replaced by 41"/21. If R contains proper subrings, the units of those subrings must be taken into consideration (compare Satz XII of [3]). The results in [3], [4] were stated only for maximal orders R but the methods also apply to non-maximal orders. Lower regulator bounds can also be obtained by means of Analytic Number Theory. The best known result is due to Zimmert [14]. Satz 3 of
Computation of fundamental units
367
his paper states for arbitrary l' > 0 and a maximal order R of a field F of degree n = s + 2t: Re g (U(R)):>-(I+1')(1+2 1' )r(I+ )'+'r(~+ )'2- S - ' -,/2 # TU(R) 7 2 l' 2 l' n
(I
r' -2+ 1') +ty r' ( xexp ( (-1-1') ( (s+t)r
2 1)).
1+21') +:Y+l+1'
(6.23)
This estimate yields good results for n ~ 6 and small discriminants. Optimal values for l' are in the interval (0, I). Unfortunately Zimmert's result does not depend on specific data of the field F, e.g. its discriminant. We close this section by presenting also an upper estimate for the regulator of a field F of degree n = s + 2t and discriminant dF • Using an idea of Landau Siegel [9] proved by analytic methods
< 2 -S4(2n)-,(be log IdFI)n-lldFI-l:
Reg F for b = (I
(6.24)
n-l
#TU(F)
+ log nl2 + (tin) log 2) - I. Exercises
I. Let IX, (J I' ... ,firE fR and
n~ ~
I
Pi # o.
2. Let R be totally real. Then for all
Prove
eE U(R)\ TU(R)
L (log le(})lf ~ 11 n
j~1
(
we have
1+ 5 log-t
2
)2 .
(This result is obtained in [4] in a completely different way.) 3. Let p be a zero of t4 + t 3 - 3t 2 - t + 1 = o. Show that p, p + 1, p - 1 are a system offundamental units in l'[p]. (On the other hand, the iQ-rank of "'(1), "'(p), "'(p + I), "'(p - 1) is only two.) 4. Compute a lower regulator bound for R = l'[PJ, p a zero of t 4 + 2t 2 + 2 = 0, and compare it to Reg(U(R)). 5. Show II "'(ek ) II :S.:; 1I!/J(eH')1I for eEU(R) and kEl'''o.
6. Prove (6.21) and apply it to example (6.20) (ii) for i = 2.
5.7. Computation of fundamental units From the two previous sections we assume that we can determine as many units EE U(R) as will be needed and that we know a lower regulator bound for Reg(U(R)). The computation of fundamental units will then be carried out in three steps. In step I we produce r independent units 'It, ... , fir of R.
368
Units in algebraic number lields
In step II we use additional units for a potential enlarging of the subgroup V~:= TV(R) x ('II) x ... x ('1r) of V(R). Finally, in step III we determine V(R) from V,,. Because of step II the last step will usually be a verification of V(R) = V~. In extensive calculations of fundamental units the groups V" and V(R) turned out to be different after step II only in about 3% of all cases.
Step I: construction of r independent units
°
assume that we know already ~ m < ,. independent units '1j(1 ~ i ~ m; mEZ"o), hence also b j := L 2 ('1j) and the corresponding orthogonal vectors bt (compare (6.1), chapter 3 (3.24». Each time a new unit 'IE V(R)\ TV(R) is found by (5.25) we set bm + 1= L 2 ('1) and compute b!+ I' In case ofb!+ 1= 0 we increase m by 1. In this way we proceed until m = ,. is obtained. Then we
We
easily calculate r
Reg(V~(R»=
n IIbtll
j=
I
for V~(R)= (TV(R),IJI,""'1,).
We note that it can be difficult to check whether the (floating point) vector b!+ I is zero. Because of n~= III bt II ;:;, Reg(V(R» (for which we know a positive lower bound) the II bt II cannot be too small in general. If we must assume a linear dependence, however, we either search for another unit IJ or we proceed as in step II.
Step II: enla,.ging of Vq(R) After the computation of a subgroup V,,(R) = (TV(R), '11, ... ,llr) of V(R) of finite index we try to enlarge this subgroup by additional units '1r+ I in case the quotient of Reg(V~(R» and of a lower bound for Reg(V(R» obtained by the methods of section 6 is still ~ 2. Applying chapter 3 (3.48) to L 2 (lJj) (\ ~ i ~,. + \) we get integers m l , ... , mr+ I subject to L~;!": Imd > 0, L~;!": "jL 2 (1J;) = 0 and units iii"'" iir such that V,lR) = (TV(R), iii"'" iir)3lJj (\ ~ i ~ r + \). If V q is not enlarged for - let us say - five more units we assume V q (R) = V(R) and proceed to step III.
Step III: computation of a system of fundamental units As an easy consequence of the fundamental theorem on finitely generated abelian groups we obtain:
Theorem (7.\) Let '1 I"'" IJk (0 ~ k < ,.) be part of a system of fundamental units of R. Then IJk + I E V(R) also belongs to that system, if and only if the equation '1k+ I = ('IT'" ... '1J':"w m
((E TV(R); mj, mEZ, \ ~ i ~ k; WE R)
(7.2)
is unsolvable for Im I ;:;, 2. A proof is easily derived from the elementary divisor theorem and chapter
369
Computation of fundamental units
3 (2.9) (see exercise 1). We note that for k = 0 the theorem gives a criterion, whether '11 is a fundamental unit. The theorem will be suited for constructive purposes only if we can test the solvability of (7.2) in finitely many steps. If (7.2) is solvable, then W is clearly a unit. Therefore we can assume m > 0 without loss of generality. Next we can choose the mj to be non-positive and greater than - m by replacing the solution W by W
n '1/ m;/ml n '1/ mdm1 . k
k
j= I mi>O
mj
j= I
Thus the solvability of (7.2) is closely related to the solvability of
Iw(jl"'I=lj~ ('1jil)-m;'1PLI
(1
~j~n)
(mEN, m ~ 2; mjE7L.<>.o,-m<mj; I ~i~k).
(7.3)
Namely, if(7.3) is not solvable for WER then (7.2) is insolvable, too. A solution of (7.3) does not necessarily imply that (7.2) is solvable, however w m might differ from the power product of the units on the right by a root of unity not contained in TU(R). Of course, this can be easily checked. As a consequence the solvability of (7.2) can be checked in finitely many steps since m can be bounded by (7.4)
m~q,
q the quotient of the regulator of the computed unit group U ~ and the lower
bound of Reg(U(R» derived in section 6. We present three different methods for testing the solvability of(7.3) under the restriction (7.4) for k = 0,1, ... , r - 1. Their application either proves that the computed unit group U ~ already coincides with U(R) or it produces larger subgroups U~ of U(R), until the whole unit group is obtained. It is clear that the tests need to be done only for prime numbers p ~ 4. Namely, a solution of (7.2) provides also a solution for each divisor mof m. Method 1. In case q, r are small we recommend a straightforward attack on the problem. Any potential solution WER of (7.2) has a presentation (7.5)
where WI"'" Wn denote a 7L.-basis of R. As in section 3 we compute the corresponding dual basis WI *, ... , W.* defined by Tr(wjw/)
= bij
(1
~
i, j
~
n).
(7.6)
Then (7.2) yields n
e/ = Tr(ww/*) =
L (C'1Vl- m,..... '1~l-m.'1~~ dl/mwj*(j)
(1 ~ i ~ n). (7.7)
j= I
Here the right-hand side is to be calculated numerically for all possibilities
370
Units in algebraic number fields
°-
(ETU(R), ~ mj < m (l ~ i ~ k), m a prime number below q. If the (floating point) calculation yields ejE~ (I ~ i ~ n), then the corresponding w is a solution of (7.2) which again can be checked by integral computations. Since we have to compute mth roots this procedure can usually be recommended only for totally real fields and m #- 2. For totally real fields and m = 2, the insolvability of (7.2) can in general be decided upon considering the signs of IljUJ. Since mjE{O, I} in that case we can easily check whether the products []~= ,Illi)"" can be all negative or all positive (1 ~j ~ n). Method 2. In more complicated cases we suggest applying the following method. Instead of computing the coefficients ej of a possible solution w for all possibilities of m, mj, ( (l ~ i ~ k, (E TU(R» we give worst case upper bounds for the conjugates of w. Obviously,
R/=
min
Ii min(l, leP)I("'-I)lm») ~ Iw(j) I
(leVt ,I '1m
2~m~tJ
~
max 2~m~ll
i::;;:.l
(leVLll/mIi max(1,le P)I(m-1) /m») 1=1
=:Sj (1 ~j ~ n), (7.8) and we can apply (3.8). The units obtained still need to be tested whether they indeed satisfy (7.3) and finally (7.2). But this again is easy. We take logarithms on both sides of (7.3) and obtain the following system of linear equations k
mL 2 (w)
+
L1 mjL 2 (IlJ = L 2 ('Ik+ d
(7.9)
j=
in the unknowns m, m 1, ... , mk. If (7.9) is unsolvable over ~ for all obtained units w, then (7.2) is unsolvable also and we can increase k, repeating this process until we have obtained r independent units. If (7.9) has a solution (m, m" ... ,mSE~k+ 1 with Iml ~ 2, then we need to check whether
Ilk+ 1
CG
'Ij-m)w-mETU(R).
(7.10)
If this is the case, we replace 'I k + l ' Uq' Reg (U q) by
'Ik+ 1 ...... w,
Uq...... TU(R) x <'11)
X .••
x <'I,),
Reg(U q ) ...... ~eg(Uq)/lml. (7.11)
If Reg( U q) does not increase any more we replace k by k + 1. This procedure has the additional advantage that we need not carry it out for each prime number p ~ q separately but only for the worst bounds (7.8) obtained for m = q. Once we have checked that our units '11' ... ' 'Ik are not powers themselves, i.e. 'Ij #- (w m (WE U(R), (E TU(R), 1 ~ m ~ q), we can even handle the tests for all k (1 ~ k < r) simultaneously by noting that the worst bounds (7.8) result for k = r - 1. This is of course due to the fact that
371
Computation of fundamental units
the method of section 3 for solving (7.8) is so efficient that larger bounds Rj,Sil <j < n) barely increase the computation time. In spite of that fact it is of course always recommendable to start with units '11' ... ' 'Ir whose conjugates are close to I in absolute value. This can usually be obtained by applying reduction to L 2(1/t), ... ,L 2(llr). M etlzod 3. Though we believe that the method just described is best suited for testing the solvability of (7.2) (mainly because of the fast procedure of section 3) we conclude this section presenting a p-adic method which is first of all of theoretical interest but also seems to be very promising from the computational viewpoint. However, to our knowledge it has not been tested numerically so far. Let PI> ... ' Ps be all odd rational prime numbers below q. (The case of 2 dividing (V(R): V,,) can be easily treated with one of the first two methods.) Then V(R) is generated by V" and those units f. of R for which some power I;h of the form Iz = ni~ I P;'" < q (l'jEl';;'o, I < i < s) belongs to V,,. Again we discuss the solvability of (7.2) starting with k = 0, i.e. we try to solve 1:( = w'" ((ETV(R), wER,m
~
2)
(7.12a)
for I: = 'II. For the coefficients e j of the presentation (7.9a) of W we obtain the bounds (7.10) with k = O. Then we determine a rational prime number
p>max{2max{Tdl
(7.12b)
such that the order lip of the prime residue class group (RlpRr is not divisible by PI' ... ' Ps. Hence, there exist positive rational integers qi (I < i < s) such that Piqi == I mod hp • If WE R solves (7.12a) for m = Pi (I < i < s), then (I:(jq, = wp,q,
== w mod pR.
(7.12c)
Because of (7.12b) we just need to compute the congruence solutions w of (7.12c) with the coefficients e,. satisfying - pI2 < e,. < pI2 (I < I' < n) for I < i < s and then check, whether one of them satisfies (7. I 2a). This has to be done for each Pi (I < i < s) and each possibility for (ETV(R). If we obtain a solution of (7.12a) in this way, then f. = I] I is replaced by w thus enlarging V~.
From now on we assume that (7.12a) has no solution. Then .Q(R)(I] :IPJ) :::> .Q(R) and the polynomial t Pi - I] I ER[t] is irreducible (I <j < s). By Tschebotareff [II] there exists a prime ideal Pi~d(R) such that (Pi - I ] I remains irreducible in Rlplt] and therefore pjl(N(p) - I). (Namely, for
pjJ(N(pj) - 1) there is qjEN subject to Pjqj == 1 mod(N(pj) - 1) and ~:= I]ii satisfies ~Pi = I]':Jqj == 1]1 mod Pj in contradiction to the irreducibility of (Pi -I]I in Rlpj[t].) Since (Rlp)X is cyclic with pjl#(RlpY and '11 is not a p}h power in (Rlp)X the order of 1]1 is divisible by Pj. Hence, for every unit I]i (I < i < r) there is precisely one rational integer Vi (0 < Vi < Pj) such that 1J~'lJi is congruent to a p}h power modulo Pj. Since this was derived for
372
Units in algebraic number fields
arbitrary j (1 ~j ~ s) we can now apply the Chinese remainder theorem to obtain units ~2"'" ~r (~i = '1I;'1i' 2 ~ i ~ r) such that <'11> x ... x = <'11> x <~2> x ... X <~r> and every element of <~2> x ... X <~r> is a pjth power modulo Pj (I ~j ~ r). Therefore every WE U(R) satisfying WPiE U q is the product of some root of unity, some power of 'll and a p}h power (PiE <~2 X ... X <~r> =: U~2). Repeating this process we finally end up with a unit group U~) with one generator. But we already considered the task of computing pjth roots of a single unit. Hence, we obtain a system of independent units inductively such that it already contains all p}h powers of units of U(R) (\ ~j ~ r), hence a system of fundamental units.
<'1r>
>
Exercises I. Use the fundamental theorem on finitely generated abelian groups and chapter 3 (2.9) to prove theorem (7.1). 2. Let R = I [ex] and ex a root of t J + t 2 - 2t - I. Compute a system of fundamental units of R starting from f. J = 2ex 2 + Sex + 2, f.2 = 2ex 2 + 3ex + 1E U(R). 3. Let F = Q(ex), CI. a root of t4 + t J - 3t 2 - t + 1. Compute a system of fundamental units for OF'
5.8. Remarks on computerization. For computing a system of fundamental units of R we need the characteristic properties of R as input data. In general we assume the knowledge of an irreducible polynomial
f(t)
= t" + a l t"-I + ... + a"E~[t],
(8.1)
represented by a l , ... , a"E~, such that F = O(R) = iQ(p) for a zero p of f. For the computations in R - especially the many norm computations of(5.23) - it is advantageous to compute the roots
(8.2) of f up to machine precision by the IMSL - subroutine ZPOLR, available at most computer centers nowadays. We order the zeros in the usual way such that
(8.3) and
P(S+I+i)
= p(S+i)
(1./'./ """ "'" t) ,
n =s + 2t .
A basis of R usually belongs to the input data, in case of R = OF it can be computed by the methods of chapter 4 within the program. In any case we
Remarks on computerization
373
assume
+ ... + ZWI/
R = ZW I
(S.4a)
for I /I Wi - --" L. mijP j - I , m j= I
(S.4b)
i.e. the knowledge of
(S.4c) The importance of having the basis reduced was already pointed out in section 5. The implementation of the methods of sections 3-7 for the computation of U(R) should be no problem. We therefore consider only a few necessary subroutines and make some remarks on potential difficulties. Addition of numbers of R is done componentwise. For multiplication, however, we need the multiplication constants Yijk of /I
wiwj =
L YijkWk'
(S.5)
k=1
To obtain them we first calculate the coefficients Pi + j.k of /I
pi+j=pipj=
L
{Ji+j,kpk-I
(S.6)
k=1
via reducing powers pm (m Pi+j.k
and for i
+j
~
~
II) by means of f(p) = O. Namely,
= bi+j,k-I
(0:::; i
Pm+ l,k = Pm,k-l fJm+ 1,1 = II, II
(S.7a)
II we compute successively {In,k= -a n+ 1 - k
for m =
+ j:::; 11- 1),
+ I, ... , 211 -
(1 :::;k:::;II),
+ Pmman+ 1-k
(2:::; k:::; II),}
f3 mm Q n,
(S.7b) (S.7c)
3. Then
/I
=
m- 2
~
/1,"=
=m- 2
m. m.J\' pll-Ip"-l
"
I
/I
k= 1
II!
I (
In
m i/lm j"p/I+ .. -2,k ) pk-l
11,"= 1
and we denote the coefficient of pk - 1 by A.ijk' From (W 1, ... , Wn) = (1, p",., pn-I )M'(l/m) we obtain (l,p, .. " pn-I) = (WI"'" wn)(M')-l m and therefore
Units in algebraic number fields
374
Mainly for the norm calculations it is useful also to know the wF) (I ~ i, j ~ n) as floating point numbers. But this can be easily done by (8.3) and (8.4b). Having stored the values of w/ j ) a norm computation of rxER via N(rx) = nj= 1 rx(j) then requires 0(n2) multiplications instead of 0(n 3 ), if we use the regular representation matrix M. of rx and compute its determinant by pure integral calculations. We note that we do not need to use complex numbers but rather work with the real numbers w/j) for I ~j ~ s D(i,j):= { RewY) for s+ I ~j~s+t (I 1m w/ J ) for s + t + I ~j ~ II.
~
i ~ n).
(8.9)
= L;'= 1rxjWj (rxjEl') becomes
Then the absolute norm of rx
(8.10) The result will be correct if the round-off errors are less than 0.5. An error estimate will be given below. The processing of the algebraic integers of (5.23) requires to compute rxlf3 for rx, f3E R, f3 i= 0, whenever the quotient belongs to R. This can be done by solving the following system of linear equations in the unknowns XI"'" XII: rx1W 1 + ...
+ rxllw" = (f3lwl + ... + f3"w = L" f3 Xj W Wj j
lI
)(x 1w 1 +
... + x"wll )
j
j.j= 1 "
=
L
k= 1
n
(Jh
L
(8.11)
f3jYijk Xj'
j.j= 1
At first we calculate a solution by floating point arithmetic. Such a solution always exists because of rxlf3EQ(R). If we assume that the coordinates of the solution vector are integers, we can check our result using integer arithmetic by just calculating the right hand side of (8.11) again. Another possibility requiring only integral arithmetic is to apply chapter 3 (3.48). For many computations - see sections 3,4,7 - a dual basis is useful. A dual basis wf, . .. , w~ of R is obtained upon solving the matrix equation (
Wi
(j))
(*(i))
I~I,J~II Wj
- I
I~I.)~II-
'"
(8.12)
Concerning the occurrence of round-off errors we just discuss the norm computation since it is most important. We assume that the zeros of J are calculated up to machine precision and therefore affected with an error e (which is less than 10- 14 for a CDC Cyber 76, for example). Then the error
375
Remarks on computerization
for the D(i, j) of (8.9) is roughly estimated by II
e
L (k -
1)lp(j)l k -
(I ~j ~ II).
2
(8.13a)
k=2
For x = ~IWl
+ ... + ~lIwIIER
the error in computing
" 1(1 L " (k - 1)lp(j)l k J j := e L i=2
2
x(j)
is at most
(I ~j ~ II).
(8.13b)
k=2
The absolute value of the norm of x (assumed to be derived from some transformation of the fundamental parallelotope) is bounded by B of (5.3). Hence, the total error in computing N(x) is roughly bounded by II
J.
J:= B j=L1 /)1' I x J
(8.13c)
It is clear that the coefficients of x must be bounded to obtain J < 0.5. On the other hand, we cannot expect to compute a unit whose coefficients are huge by single precision arithmetic. We note that the choice of a reduced basis of R usually helps to keep the coefficients of the fundamental units small.
6
The class group of algebraic number fields
6.1. Introduction The fundamental differences between the arithmetic in Q and that in finite algebraic extensions F of Q are described by the unit group VI' and the class group elF of F. While we saw in the last chapter that algebraic number fields usually contain units other than ± I (the only units of .l) we now discuss the deviation of the ring of integers OF of F from being a factorial ring. Again this is extremely important for solving non-linear Diophantine equations. As we already mentioned in chapter 4, section 5 Kummer believed that he had established a proof of Fermat's last theorem that (1.1)
is insolvable for any tnE.l ;'3, until Dirichlet pointed out to him that his proof was based on the (wrong) premise that OF is factorial for all cyclotomic fields. Kummer's struggle to save his 'proof' accelerated the beneficial development of algebraic number theory in the second half of the past century. We will demonstrate the importance of the question whether OF is factorial or not by a much simpler example. Let us consider the equation 2y 3 = x 2
+ 5 (x, YE.l).
(1.2)
It can also be written as
2y 3=(X+(-5)1)(X_(-5)1),
(1.3)
i.e. we obtain an equation in .l[( - 5)1]. Let us assume that OF = .l[( - 5)t] is a factorial ring of F = 5)1). Which consequences does this have for solving (1.3)? Let (t,1lEO F and - denote the usual complex conjugation. Obviously, 1l1(t¢>itla, and for YE.l this means 1lly¢>itly. Now assume that 1l is an irreducible element of OF and that 1l kly, 1l k+ 11 y for some kEN implying 1l 3k l(ta for a solution y, (t = x + ( - 5)1 of (1.3). If 1l = it then k must be even and we can set ji~ Y1l- k, a.~(t1l-3kI2 yielding another solution of (1.3) for which y is not
Q« -
378
The class group of algebraic number fields
divisible by n any more. For n -# ji there are integers II, I'El;'o such that nllla, jivla and J1. + v = 3k for a solution of (1.3). Hence we can replace y by yn-kji-k and a by an-Ilji-v, obtaining another solution of (1.3) for which
y is not divisible by n anymore. Hence, if(1.3) is solvable at all the assumption of OF being factorial yields the solvability of 2 = a 2 + 5b 2 which is clearly impossible. Thus either (1.3) is not solvable or l[( - 5)1] cannot be factorial. But (1.3) obviously has the solution y = 3, x = ± 7 and we shall see later that this is indeed the only solution (compare exercise 2 of section 2). Thus 0" is certainly not a factorial ring. As a kind of a substitute for the decomposition of each element into a unique power product of irreducible elements times a unit we find that in 0" every non-zero ideal is a unique power product of prime ideals. This is the concept of Dedekind rings which we developed in chapter 4, section 5. As a special case the ring of integers Of' of an algebraic number field F is considered as a Dedekind ring in section 2. The essential facts are among others that OF is factorial if and only if every ideal of OF is principal (see (1.13». If not every ideal of OF is principal then the equivalence relation on the set of all non-zero ideals of OF defined by 0-
b:
= {Jb
( 1.4)
for suitable a, {JEOf' \ {O} and 0, b non-zero ideals of OF yields hF > 1 equivalence classes. The number of equivalence classes is called the class /lumber of F. The number hF measures the deviation of OF from being factorial (see also (1.13», Moreover, the equivalence classes with respect to - form a finite abelian multiplicative group CIF' where the multiplication is defined on the representatives. The computation of this group (respectively its order) - via suitable representatives of the ideal classes - is the main goal of this chapter. As in the computation of the unit group Minkowski's number geometric ideas form the basis. Namely, they imply that those representatives can be chosen from a finite set of ideals 0 of OF characterized by the fact that the index (OF:O) is less than a certain bound depending only on the field degree 11 = S + 2t and the discriminant dF of F - the so-called Minkowski bound. Moreover, that finite set can be effectively constructed from the prime ideals occurring in the (unique) prime ideal factorization of POF where P runs through all rational prime numbers below the Minkowski bound. This theory is treated as part of the ideal theory of Of' in section 2. The three remaining sections deal with the task of turning that effective procedure of determining Clf' into an efficient one. Section 3 contains the fundamentals about ideal arithmetic in Of" As if-modules of finite index in OF the non-zero ideals of OF also have a l-basis, a useful fact for most computational problems concerning ideals. However, non-zero ideals 0 of OF can also be presented in the form 0 = aO F + aO F (aEN,aEo F ). This is
Introduction
379
obviously of advantage for storing ideals (only n + 1 instead of n2 respectively n(n + 1)/2 (compare chapter 3 (2.10)) - rational integers are needed for each ideal). Beyond that we develop some canonical representation of ideals by two elements which allows ideal multiplication via their generators: nb = aboF + (X/Jo F for n = aO F + (X0F'
b = bOF + {J0F'
(1.5)
Since we are dealing with the multiplicative structure of the non-zero ideals of Of' this is clearly a big advantage. It is also a great help in factoring POF' p a rational prime number, into prime ideals of OF' Section 4 discusses the task how to decide whether two given ideals are equivalent in the sense of (1.4). The well-known methods for this are indeed effective but not very efficient. We make instead use of an idea of K. Mahler which enables us to transfer the problem of determining whether kE I\J is a product of n linear forms (tantamount to the norm of a certain ideal element) to the computation of certain values of a finite number of positive definite quadratic forms via chapter 3 (3.10). (Parts of that concept were already considered in chapter 5, section 3.) A complexity analysis shows that the number of arithmetical operations needed by our new method is only about the square root of the number of operations required by the old one. Finally, in section 5 we develop an algorithm for the computation of CIF using the results of the earlier sections. The remaining difficulty is to build up CIF as a direct product of cyclic subgroups. Beginning with a finite number of generators our information is in general not complete, i.e. there can and often will exist equivalence relations between the generating ideals which are not implied by the ones we know. Testing for those relations becomes much easier by the methods of section 4 but still consumes a lot of computation time. Hence, those tests should be kept to a minimum. How to do this is the essential content of section 5. Once the class group has been established those tests become quite easy as is shown at the end of that section. From the theory of Dedekind rings developed in chapter 4, section 5 we shortly recall the following important results. Dedekind rings R were characterized in chapter 4 (5.6) as entire rings
IVhich are N oelherian and illtegrally closed and in IVhich every non-zero prime ideal is maximal;
(1.6)
ill IVhich the nOll-zero R-fracliollal ideals form a group, the so-called ideal group I R of R;
(1.7)
ill IVhich every ideal is a (unique) product of prime ideals.
(1.8)
In this chapter we denote the subgroup of I R consisting of all principal
380
The class group of algebraic number fields
ideals by HR' In case the ideal class group CI R := I R/ H R is finite its order is said to be the class number hR of R. In case of R = OF (see (2.1) we also write CIF, hf · instead of CI R , hR in general. The following useful properties of nonzero ideals a, b of a Dedekind ring R are easy consequences of (\.8). a ~ b if and only if R contains an ideal e sati.ifying a = be (\.9) (compare chapter 4 (5.2». In that case we also write b Ia, respectively b Ia a is the principal ideal aR.
gcd(a, b) = a + b.
(1.10)
n is the greatest common divisor of two principal ideals. The generating element of one of them can be chosen arbitrarily from a\{O} (compare chapter 4 (5.39)d).
(1.11)
There exist an element w of R and an ideal e of R such that b + e = Rand ne = Rw.
(1.12)
Pro(~r (~r
(1.12) Let PI'"'' P, be all prime ideals of R which divide either a or b. Then a has a presentation a = ni = I pr' (aiE~ ;'0, 1 ~ i ~ 1'), and we set
,
0i:=
n pjJ+
1
(I ~ i ~ 1').
j=l
iti
(In case I' = 1 obviously 0 1 = R.) Clearly, R = 0 1 + ... + 0, = gcd(OI'''''O,). Hence, there exist elements biEO i (I ~ i ~ r) satisfying 1 = b l + ... + b,. Also there exist elements {JiEpf'\pr'+ I (I ~ i ~ r), because of (\.8) for example. We set w:= 'Li = I{Jibi and obtain pf' II Rw because of pf' + II Rb j (I ~ j ~ r, j -:f. i) and PiX Rbi' Hence n~= I pi:klRw and Rw = ae for some ideal e of R which is not divisible by any of the Pi (I ~ i ~ r). Since b is a power product of PI'"'' P, by assumption we obtain b + e = R according to (1.10). 0 The following theorem shows that CI R and hR describe how much the structure of the Dedekind ring R deviates from a factorial ring.
Theorem The class number hR of a Dedekind ring R is one
(1.13)
if and only if R is factorial.
Proof In case hR = I, every ideal of R is principal and R is therefore a unique factorization ring. On the other hand, if R is a factorial Dedekind ring it suffices to show that every prime ideal of R is principal. Let p be a non-zero prime ideal of
The ring
381
(it·
R. Because of (\.8) there exists an element [J of p\p 2 , i.e. Rf/ ~ p, R[J $: p2. The ideal R[J has a unique presentation as a product of prime ideals, say Rf/ = Pi'" (Pi distinct prime id~als, lIIiEN, I ~ i ~ II). Reordering the Pi' if necessary, we obtain p, ~ p and therefore p, = p because of (\.6). Since R[l is not contained in p2 we must have In, = \. In the factorial ring R the element [J has a presentation as a product of irreducible elements, say [J = f. 7l~J (71j distinct irreducible elements of R, kjE N, I ~ j ~ S, SE N, cEU(R)). But then R71i(1 ~ i ~ s) isa prime ideal of R and from nj~ ,(R71i = RfJ = pn~ = 2 pi"' we obtain p = R71 j for a suitable index j (I ~.i ~ s) by (\.8).
ni'=,
nj=,
J
o 6.2. The ring
0,..
of algebraic integers as a Dedekind ring
In this section we consider the maximal order of an algebraic number field and discuss the most important consequences which follow from the fact of it being a Dedekind ring. In the sequel F always denotes an algebraic number field of degree II and OF the integral closure of 11. in F. A subring of OF which is also a free 11.-module of rank II (order of F) is denoted by R. From (\.6) it is clear that R can be a Dedekind ring only in case R = OF' Again from chapter 4 we recall (chapter 4 (5.9)): The maximal order Dedekind ring.
OF
of an algebraic lIumber field F is a
(2.1 )
We note that every (fractional) ideal of an order R of F is a free 11.-module of rank II. Hence, every order R is Noetherian and each non-zero prime ideal of R is a maximal ideal. But in case R C OF the ring R is not integrally closed and therefore J R not a group (see also exercise 4). For any non-zero R-ideal a the number of residue classes of Ria equals the absolute value of the determinant of a transition matrix from a 11.-basis of R to a 11.-basis of a (compare chapter 3 (2.9)) and is therefore finite. This plays an important role in proving that -- in case R = OF - the group J R/ H R is finite. The following definition is a special case of chapter 4 (5.44). Definition
(2.2)
Let R be all order of the algebraic lIumber field F and a a nOll-zero ideal of R. Then N(a):= #Rla is called the norm of the ideal o. As in chapter 4 the ideal norm is a natural generalization of the norm of an element. Proposition For {JE R\ {O} we have N(RfJ) = I N({J)I.
(2.3)
382
The class group
or algebraic number fields
Proof Let M pE7LII x" be the regular representation of {l with respect to a iE-basis WI"'" W" of R: (WI"'" w,,){l = (WI"'" w,,)M p. Then chapter 3 (2.9) and chapter 5 (5.5) yield #(R/RfJ) = Idet Mpl = IN(fJ)I·
o
In the most important case R = OF the ideal norm is shown to be a multiplicative function by the next two lemmata. (Compare also exercises 29-33 of chapter 4, section 5.) (2.4) Lemma Let R = OF' a a non-zero ideal of R and a, {l be arbitrary elements of R. The congruence ax == {l mod a is solvable in R if and only if P== 0 mod gcd (a, aR). If it is solvable, then it has modulo a exactly N(gcd(a, aR)) different solutions. Any solution x is uniquely determined modulo a(gcd(a,aR))-I.
Proof Let b:= gcd(a,aR) and c = ab-I. If the congruence is solvable, there is an liEa such that ax - Ii = P and b divides Rax, Rli and therefore R{l, i.e. {lEb. On the other hand, if P is in b = a + aR, then there are liEO, xER such that ax + Ii = {l, i.e. ax == (l mod a. Now let x, y be both solutions of the congruence. This implies a(x - Y)E 0= cb, hence Ra R(x - y) = cbn for some ideal n of R. Comparing the prime ideal factorizations on both sides we obtain R(x - y) £ c because of b = gcd(a, Ra). Therefore any solution x of the congruence is uniquely determined modulo C. (For YEC obviously a(x + y) == ax mod a because of aYEbc = a.) In the case of solvability of the congruence the number of modulo a incongruent solutions is equal to the number of residue classes of c/a. So, it remains to construct a bijection between c/a and R/b. For this purpose choose WE R satisfying gcd (Rw, bc) = c by (1.12). Then we map c/a = {¢w
+ al¢ER} onto Rib = {¢ + bl¢ER}
via ¢W
+ a f-4 ¢ + b.
Clearly, WEC and therefore ¢WEC for every ¢ER. On the other hand, let yEC, then ¢w == y mod a is solvable in R because of Rw + a = C. Therefore the map ¢w + a f-4 ¢ + b is independent from the representative ¢w. Namely, for ¢w + a = ~w + a we obtain (¢ - ~)wEa, hence ¢ - ~Eb because of Rw + a = C. The map is clearly bijective, hence #c/a = N(b). 0 Lemma Let a, b be non-zero ideals of R =
(2.5) OF'
Then N(ab) = N(o)N(b).
The ring
o~·
383
Proof According to (1.12) we choose WER satisfying ab + Rw = a. For r:= N(a), s:= N(b) let I " " , e,ER and 111"'" lisE R be a full set of representatives for Ria, R/b, respectively. We set 'ij:= + Wl1j (1,,;; i,,;; r, I ,,;;j";; s) and show that they form a full set of representatives for Rlab. In case of ' i j == 'kl mod ab (1 ,,;; i, k ,,;; r, I ,,;; j, I ,,;; s) we obtain successively
e
ei
ei == e mod a,
hence i
k
= k,
Wl1j == Wil, mod ab,
I1j == 111 mod b (because of (2.4)), i.e. j
= I.
ei
On the other hand, let IXE R. Then IX == mod a for some i (I ,,;; i ,,;; r), == I1W mod ab is solvable, and therefore 11 uniquely determined modulo b according to (2.4). Hence, 11 = I1j for a suitable index j (I ,,;; j ,,;; s) and IX == + wlJj mod abo 0 The last lemma enables us to prove the finiteness of I RI H R in case R = OF' In addition to OF being a Dedekind ring, we need the finiteness of 0F/a for non-zero ideals a of OF for the proof. We apply Minkowski's Convex Body Theorem chapter 3 (4.2), to the set C of chapter 3 (4.6). Namely, the Minkowski IX -
ei ei
mapping
maps OF onto an n-dimensional lattice with d(lp(OF)) = 2 -, IdFI I /2. If we restrict lp to a non-zero ideal a of 0F' we obviously obtain d(lp(a)) = 2-'N(a)ld FI I / 2 for the sublattice lp(a) by chapter 3 (3.6). Then the set S of chapter 3 (4.5) (and therefore of course C of chapter 3 (4.6)) does not contain a vector XEIR", x :I 0, such that lp - I(X) is a non-zero element of 0F' a, respectively. But the set Cs.,(A) (see chapter 3 (4.8)) for A" = (2"- S n!(2/n),d(A)) contains a non-zero XEE" because of its compactness and V(Cs,,(A)) = 2"d(A) by chapter 3 (4.2). This x satisfies IN(lp -1(x))1
=
n
n
S
j=
11-
Ix(iJl
1
(X(i)2
+ x(i+t)')
i=s+ I
I
i-.",odd
,,;;
(8)'
n' ~ ( ~.1.)/1 = n~
d(A).
Thus we have proved the following lemma. (2.7) Lemma Let a be a non-zero ideal of Of· Then a contains a non-zero element x sati.~ryillg
(4)'
n! I N(x)I";;n/l
n
N(a)ldFI 1/2 .
384
The class group of algebraic number fields
Corollary Every ideal class C of I d H f' contains an ideal
(2.8) 0
of Of' satisfying
N(o):< n! (~)'Id F 11/2 ='M "" nil 1! • F M F is called Minkowski's constant of F.
Proof Let C be any ideal class of I F/ H F and c an integral ideal of C - I. We choose XEC subject to (2.7). By (1.9) there is an integral ideal 0 (necessarily in C) satisfying xO F = oc. Hence, we obtain
N( )=!N(x)1 :
o
We note that there are better bounds than (2.8) which were obtained by analytic methods (see [14] of chapter 5). Those should be used for class group computations in number fields of degree /l ~ 4.
Corollary The class /lumber hF of F is .finite.
(2.9)
Proof Because of (2.8), OF being a Dedekind ring, and the multiplicativity of the ideal norm it suffices to show that there are at most finitely many prime ideals in OF whose norms are less than M F' Let p be a non-zero prime ideal of OF' Since odp is an additive group of order N(p) and 1!fP, we get N(p)(1 + p) = p, hence N(p) is a natural number contained in p. Obviously, N(p) ~ 2 and p occurs in the prime ideal factorjzation of N(P)OF' Therefore p divides POF for some rational prime number p and p is uniquely determined by p (see exercise 5). But this implies N(p)lp" by (2.5), hence N(p) = pI for some fEN, 1 ~ f ~ n. Again, by (2.5) there can be only finitely many prime ideals p containing POF' Since there are only finitely many prime numbers p with p ~ M F this concludes the proof. 0 For later applications we note part of the results of the last proof separately:
Lemma (2.10) Every non-zero ideal 0 of OF satisfies N(O)EO. If 0 is a prime ideal, then OF/O is a field with pI elements, where fEN, 1 ~f ~ n, and p is the unique prime number contained ill 0. We note that there are algebraic number fields for which the class number is arbitrarily large. For example, if d runs through the squarefree natural numbers the class numbers hF of the fields F = Q( - d)! satisfy limd~oo(loghF/logdt)= 1 [6]. On the other hand it is an open question, if infinitely many algebraic number fields have class number one. For real quadratic fields C.F. Gauss conjecturea that hF = 1 for infinitely many F, and
The ring
Of'
385
extensive computer calculations seem to support this conjecture. If the Minkowski constant of(2.8) is less than 2, the corresponding algebraic number field F necessarily has class number hI' = I. The following examples illustrate this.
Examples
(2.11 )
(i) Let F = Q(d!), d == 2, 3 mod 4, dE"l. square-free. Then hI' = 1, if (2!/22)(4/n)'(4Idl)l/2 < 2. For t = 0 this is fulfilled by d = 2,3, for t = I in case of d = - I, - 2. (ii) F = Q(e 2ni /S ) is totally complex of degree n = 4 = 2t. Because of chapter 2 (11.12) and chapter 4 (6.10) the discriminant is dF = 53. Hence, M I' = 15(5)1/(2n2) < 2 and hI' = I.
In order to determine hI' and IF/HI' lemma (2.8) suggests to consider the factorization of all rational prime numbers p ~ M I' into prime ideals of F. And we are about to develop the tools for this task. We start with a slightly more general situation. Namely, we consider a relative finite algebraic extension G of an algebraic number field F. The rings of algebraic integers of F, G are denoted by R, S respectively. The degree [G:F] is denoted by II, as usual. If p is a prime ideal of R, then Sp:= {L;'~ 1 SiPilsiES, PiE~l, mEN} is obviously an ideal of S. Because of (2.1) S is a Dedekind ring and there exists a prime ideal factorization Sp = \.l3';' ..... \.l3~. of Sp into a power product of prime ideals of S. Hence, we need to determine the prime ideals l.l3i' the exponents Ci and the natural number r.
Lemma
(2.12)
Let p, I.l3 be 1I01l-zero prime ideals of R, S respectively. Theil the followiny cOllditiolls are equivalellt (i) I.l3ISp, (ii) I.l3 ;2Sp, (iii) 1.l3;2 p, (iv) I.J3nR = p, (v) I.J3nF=p.
Proof The equivalence of (i) and (ii) is just (1.9). (ii)=>(iii) is obvious since 1ES and therefore Sp;2 p. (iii) => (iv): I t is clear that \.l3 n R ;2 p. On the other hand, I.l3 n R is an ideal properly contained in R. Hence, I.l3 n R = P because of the maximality of p.
386
The class group of algebraic number fields
(iv)=>(v): ~nF = (~nS)nF = ~n(SnF) = ~nR = p. (v) =>(ii): Clearly ~ 2 P and therefore ~ = S~ 2 Sp.
Definition If one of the conditions (2.12) (i)-(v) is satisfied, we say
o (2.13)
~
lies over p, or plies
under ~. The following corollary is obvious.
Corollary (2.14) Let p be a non-zero pl'ime ideal of Rand Sp = ~~, ... :~;. the prime ideal factorization of Sp in S. Then ~1"'" ~r are exactly the prime ideals of S lying over p. Definition (2.15) Let p be a non-zero prime ideal of R and ~ a prime ideal ofS such that ~eISp, ~e+ IISp. Then the exponent e = e(~lp) is called the ramification index of~ over p. The prime ideal p is called ramified in G, if there is a prime ideal ~ of S lying over p with e(~lp) > 1, otherwise unramified. For the determination of the number I' of prime ideals of S lying over a non-zero prime ideal p of R we shall need a further invariant which compares the residue class fields Rip and S/~. Since Rip is a priori not necessarily contained in S/~ we construct a natural embedding.
Lemma (2.16) Let p be a non-zero prime ideal of R and ~ a prime ideal of S lying over p. Then K: Rip -. S/~: r + pM I' + ~ is a ring-monomorphism which embeds Rip in S/~. In the sequel we can therefore identify Rip and K(Rlp)· Proof
o
Apply (2.12).
Definition (2.17) Let p be a non-zero prime ideal of R and ~ a prime ideal of S lying over p. Then f= f(~lp):= [S/~:Rlp] is called the degree of inertia of ~ over p. This definition clearly implies
Theorem Let ~, p be as in (2.17). Then N(~)
(2.18)
= #S/~ = N(p)f(·IlIPI.
The ring
387
Of'
This enables us to prove a first major result on the prime ideal factorization in S. Theorem Let p be a Iloll-zero prime ideal of R alld Sp prime ideal factorizatioll ill S. Theil
(2.19)
= 1.13~1 ' ... '1.13:'
the correspollding
r
II
=
L e;/j = L
j~'
e(l.13lp)f(l.13lp).
(2.20)
'Il2p
Proof Because of N(Sp) = N(p)e,/1 + ... +e,J, it suffices to show N(Sp) = N(p)". If hF is the class number of F, then phf' = AR for some AER. Hence, N(pS)"f' = N«pS)"f') = N(p"f'S) = N(AS)
= 1NG/O(A) 1 = INF/O(NG/F(A))I (by exercise 8 of chapter 2, section 3)
= 1NF/O(A") 1= 1NF/O(A) 1" = N(p"f')" = N(pi1f'"
which concludes the proof. 0 Having established (2.20) we need a method for constructing all prime ideals 1.13 lying over p. Before we attack this problem we shortly discuss the influence of automorphisms on ideal factorizations. Lemma Let 1.13, p as in (2.17) alld O'EAut(G/F). Then
(i) (ii) (iii) (iv)
(2.21)
0'(1.13) is a prime ideal of S, 0'(1.13);2 p, f(1.131 p) = f( 0'(1.13) 1p), e(1.131 p) = e(O'(I.13) 1pl.
Proof (i) and (ii) are obvious. For (iii) we note that 0' implies a vector space isomorphism
a: S/1.13 O'(S)/O'(I.13) = S/O'(I.13), -4
where S/I.13, S/O'(I.13) are considered as R/p vector spaces. Finally, to show (iv) we apply 0' to the factorization Sp = 1.13~t. ... '1.13:' to obtain Sp = O'(Sp) = O'(I.13,)e l . . . . ·O'(l.13r)e,. 0 In particular, for a Galois extension G/F we get
388
The class group of algebraic number fields
(2.22)
Theorem
Let G/F be a Galois extension and p a non-zero prime ideal of F. Then the Galois group H = Gal (G/F) operates trallsitively 011 the prime ideals l.l3i (I ~ i ~ 1') which lie over p. Proof We assume that there are indices I ~i<j~r such that {a(l.l3i)!aEH}n {a(l.l3 j )!aEH} = 0. By the Chinese remainder theorem, chapter 2 (2.17), we construct SES subject to s =: I mod a(l.l3i) for all aEH, s=:Omoda(l.l3 j ) for all aEH. For this element s we obtain NG/F(s)
=
n a-
l
(s)El.l3 j nR=p,
(JEll
and on the other hand NG/F(S)
= fI
a-l(s)¢~i;2 p,
ClEIl
clearly a contradiction. Hence, the assumption was false.
o
As an easy con seq uence of (2.21) and (2.22) we obtain
(2.23) Let G, F, p as in (2.22). Then the prime ideal factorization of p in S is of the form Sp = (~I· .. . ·~r)e, the ramification indices e = e(~!p), respectively the degrees of inertiaf = f(~! p) coincide for all ~ lying over p implying n = efr. Corollary
The determination of the prime ideals ~ of S lying over the non-zero prime ideal p of R is always a little complicated. The main reason for this is that we usually know G only as G = F(p) for some PES and in general there is not even a basis of S over R. Hence, we have direct access only to the ideal theory of R[p] and not of S = Cl(R, F). The transition from R[p] to S is then possible via the so-called conductor:
(2.24)
Definition
Let 0 be any order of G. Then in S.
tv:= {x EO! xS £; o} is called the conductor of 0
It is easily seen that tv is an ideal of 0 as well as of S. Also we note tv;2 mS for m:= (S:o). Before we state the general result we need two preparatory lemmata. (2.25)
Lemma
Let
0
be an order of S of conductor
tv.
Then
The ring
389
Of'
Ds:= {o ~ Sio a nOll-zero ideal of S such that 0 + 3' = S} alld Do:= {o ~ 010 a Iloll-zero ideal 40 such that 0 + 3' = o} are lIIultiplicative lIlolloids lVith callcel/atioll lalV. Proof All 0, bEDs satisfy
+ 3')(b + m= ob + 3'(0 + b + m ob + 3'S = ob + 3',
S = SS = (0 =
hence Ds is a monoid with unit clement S. Analogously we show that D. is a monoid. In Ds common factors can be divided out because of Ds ~ Is. The proof 0 of this property for Do is contained in the proof of the next lemma. Lemma Let 0 be
(2.26) all
order (!f G (!f cOllductor
3' alld Do, Ds as
ill
(2.25).
D. -> Ds: 0 M So is {lIl isomorphism with ill verse 1(-1: Ds-> Do: OM OliO. (ii) For oEDs lVe have S/o ~ 0/0 II o. (iii) Every ideal 0 (!f Do has ill 0 a unique presentation liS a product
1(:
We note that (2.26) (iii) proves the statement of (2.25) about the cancellation law for Do' Pro(if (i) For oED. we obtain S ~ K(O) + 3' = So
+ 3' =
So
+ S3' =
S(o
+ m=
So = S,
hence II.' is a homomorphism of D. into Ds. (The homomorphy of I( is obvious.) For the injectivity of K it suffices to prove 0 = So II 0 (OE Do) since then So = Sb implies 0 = b. We conclude as follows: o ~ SOIlO
= SOIl(O + m = 0 + So II 3' = 0 + So3'
(S 0 and 3' are comaximal)
= 0 + 03' =0. To prove the surjectivity of I( we choose an arbitrary oED s. Then S = 0 + 3' implies O:=OIlOEDo.1t therefore remains to show S(OIlO) = 0: 0= 00 =0(0110
+m
= 0(0110) + 3'0
The class group of algebraic number fields
390 =
o(ono) + mono)
=
(because of trO S(ono)
= trno = trn(ono) = mono»
= So. (ii) We consider the residue class mapping q>: 0 ...... S/o: n-+r + o. Because of the homomorphism theorem for rings we need to show: (a) Ker q> = 0 n 0, (b) q> is surjective. Part (a) is obvious. For (b) let r be any element of S. Because of S = 0 + !j there exist rEO and f E!j such that r = r + f· Since f is in 0 we obtain q>(f) = r + o. (iii) Let oED. and K(O) = So = oED s . Then 0 has a unique presentation of prime ideals of S:
o=
'1.'~I.
.... '1.'~'.
Since the '1.'i (1 ~ i ~ r) contain 0 they must also belong to Ds. Therefore we obtain a factorization in 0: 0 = K - 1 ('1.' ttl. .... K - 1 ('1.'r)e,. Because of (ii) all o/('1.'i n 0) are fields, hence K - 1('1.'i) = '1.'i n 0 maximal ideals of o. The presentation of i'i as product of maximal ideals is unique, since S is a Dedekind ring and K an isomorphism. 0 In the following principal theorem we obtain the prime ideals '1.' of S which lie over a non-zero prime ideal p of R from the factors of the minimal polynomial of p (G = F(p» modulo p. Theorem
(2.27)
(Decomposition of prime ideals). Let G, F be algebraic number fields with maximal orders S, R respectively. Let G = F(p), PES, andf(t)ER[t] the minimal polynomial of p. Finally, let !j denote the conductor of R[p] in S. Then the decomposition of prime ideals p of R satisfying Sp + tr = S into prime ideals of S is the following: Let ](t) = 11 (tt'· ... Ir(t)e, be the decomposition off(t) into distinct monic irreducible polynomials over Rlp[t], and let fi(t)E R[t] be distinct monic irreducible polynomials which are mapped onto J:(t) under the residue class mapping R[t] -+ Rlp[t] (1 ~ i ~ r). Then Sp has a unique presentation Sp = '1.'~' ..... '1.'~' as a power product of prime ideals in S, where
'1.'i = pS + fi(p )S, e('1.'d p) = e;, f('1.'i!p) = deg(f;) (l
~i~
r).
Proof The underlying idea is to study the prime ideals of R[p] which lie over a given non-zero prime ideal p of R subject to Sp + tr = S. The transition from R[p] to S is then via (2.26). For abbreviation we denote the images under the residue class mapping R -+ Rip, respectively, R[t] -+ R[t]/pR[t], by -, i.e.
The ring
391
OF
Li~oajtjf-+ Li~oiijti. We start by showing
(2.28a) R[p ]/pR[p] ~ R[t]/J(t)R[t]. This result is obtained by applying the ring homomorphism theorem to the mapping <1>: R[p] -4 R[t]/ J(t)R[t]: h(p) f-+ h(t) +J(t)R[t], where h is an arbitrary polynomial of R[t]. We have to show that <1> is a well-defined homomorphism, that ker <1> = pR[p] and that <1> is surjective. The latter is, of course, obvious as well as the fact that <1> is a homomorphism. To show that <1> is well defined we take hi, h2ER[t] such that hl(p) = h2(P). This implies in R[t]: hl(t) - h2(t) = q(t)f(t) + r(t) with deg(r) < deg(f) sincef was monic. The specialization tf-+ p yields r(p) = 0 and therefore r = 0 because of the irreducibility off. Applying - to the equation above we obtain in R[t]: hl(t) - h2(t) = q(t)J(t), hence <1> (hl(p)) = <1> (hAp)). To determine ker<1> let h(p)ER[p] such that <1>(h(p)) = O. This implies h(t) = ij(t)J(t) for some polynomial ij(t)E R[t], hence h(t) = q(t)f(t) + r(t) with r(t)EpR[t] in R[t]. The specialization t f-+ P then yields h(p) = r(p)EpR[p]. On the other hand, for h(p)EpR[p] we have h(t)EpR[t] and therefore h(t) = OER[t]. Because of (2.28a) it suffices to determine the prime ideals of R[t]/ J(t)R[t]. But R[t] is a principal ideal ring and the only irreducible elements of R[t] dividing J(t) are !I (t), .. . ,J,(t). Hence, /;(t)R[t] are the only prime ideals of R[t] lying over J(t)R[t] implying that /;(t)/ J(t)R(t) generate exactly the non-zero prime ideals of R[t]/ J(t)R[t] (\ ~ i ~ r). Let us denote the isomorphism of(2.28a) by <1>. Then obviously <1> - I (/;(t)/ J(t)R[t]) generate all non-zero prime ideals of R[p]/pR[p]; they are of the form fj(p)R[p ]/pR[p]' Hence, we obtain that all prime ideals of R[p] which contain p R[p] are fj(p)R[p] + pR[p] (I ~ i ~ r). Now our premise Sp + Ij = Sand (2.26) imply that all prime ideals of S lying over Sp are given by (2.28b) It remains to show
f(ll3;1 p) = deg (j~), e(Il3;1p) = ej (\
~; ~
(2.28c)
r).
(2.28d)
The proof of (2.28c) is as follows: N(p)f('llM
= IR/pl(s/'ll;R/p) = IS/ll3il = IR[p]/ll3jnR[p]1 (by (2.26)) =
I(R[p ]/pR[p ])/((ll3i n R[p] )/pR[p ])1
= I(R[t]/!(t)R[t])/(/;(t)R[t]/J(t)R[t])1 = 1R[t]//;(t)R[t] 1 = IR/pldegU;).
(by (2.28a))
The class group of algebraic number fields
392
For the proof of (2.28d) we show ei ~ e('l3ilp) at first. Namely, we have r
r
n 'l3f' = n (pS + fi(P)St' ~ pS + fl(p)e
i~
I
i~
<:;
t ...
·"i~(pt'S
I
pS
+ pR[p]S ~ pS =
r
Il 'l3ii 'l"IP) i~
I
because of f(t) - fl (t)e t •••• ·f..(t)e'EpR[t] and therefore fl(p)e t •••• 'fr(p)e'EpR[p]. On the other hand, (2.20) yields r
n=
r
L e('l3ilp)f('l3ilp) = L e('l3dp)deg(fJ
i~
I
i~
I
r
~
L eidegU;) = i~
deg(f) = n.
I
Since all constants involved are positive this implies ei = e('l3dp) for all i (I ~ i ~r). 0 Before we give some applications of this theorem let us consider how we can check for a given non-zero prime ideal p of R whether Sp + 0: = S is satisfied. A direct attack of this problem is not very promising because of the definition of 0:. However, in most cases the following lemma does the job.
Lemma Let R, S, p,
(2.29)
0:
be as ill (2.27). Then sufficient conditions for Sp
+ ~ = S are:
(a) p+RIIl=Rform=(S:R[p]),or (b) p does not divide d(f)R, d(f) the discriminant of f(t).
Proof Since the prime ideal p is also maximal (Rip is finite) it suffices to show that m = (S:R[p]) and d(f) are in 0:. Namely, this at once implies S = SR = Sp + Sk ~ Sp + S~ ~ S for kE {m, d(f)}. But III is in ty per definition. For d( f) we conclude as follows. As previously shown S <:; _1_ R[p] and this
.
d(f)
yields d(f)S <:; R[p] and therefore d(f)EO:, too. 0 As a consequence of this lemma all but a finite number of prime ideals satisfy the conditions of (2.27). From (2.27) we derive
Corollary (2.30) Let F, G, R, S, f, p as ill (2.27). lfp does not divide d(f), then p is unramified in G. Proof Because of (2.27), (2.29) it suffices to show that f(t)E R(t) remains separable in Rlp[t]. Let K be the splitting ring of f and q a prime ideal of K lying over p. We denote the residue class mapping of K[t] into Klq[t] by <1>.
The ring
393
0"
Then for J(t) = 0:'= I (t - ~i) in K[t] we obtain <1>(/) = 0:'= I (t - <1>(~i)) in K/q[t]. If there were indices i, j (l ~ i < j ~ /I) such that <1>(~i) = <1>(~), this would imply q I(~i - () and therefore q Id(/) in K. But then also d(f)Eq n F = p contrary to the premise pld(f). Hence, the <1>(0 (l ~ i ~ /I) must be pairwise 0 distinct and J therefore remains separable in R/p [t].
Example
(2.31) As a consequence of (2.28) we obtain the factorization of rational numbers p into prime ideals in quadratic fields G = Q(mt), mElL square-free. For the application of (2.27) we note that F = Q, R = lL, J(t) = t 2 - m, and
lL[mt] for S=
{
/II
== 2,3 mod 4, therefore
~
= S,
lL ['- +ml] 2for m == , mod 4, therefore
~=
2S.
We discuss several cases for p. (a) Let p divide m. Then Sp + ~ = S is satisfied. The polynomial J(t) = t 2 - m splits in lL/plL[t] into t 2 yielding pS = (mtS + psf. (b) Let m be odd and p = 2. For m == 3 mod 4 we obtain thatf(t) = t 2 - m splits in lL/plL[t] into (t + 1)2 yielding 2S = ((mt + l)S + 2S)2. However, for m == 1 mod 4 we cannot directly apply (2.27). Therefore we choose a different polynomiall(t) = t 2 - t - (m - 1)/4 for generating Gover Q. Then we obtain S = lL[p] for the root p = (l + /II t )/2 of 1 again. Now l(t) splits in lL/2lL[t] into t(t - I) for m == 1 mod 8 and remains irreducible for m == 5 mod 8, yielding 2S = {(
I +mt
2- S + 2S
t )(I-m ) --2- S + 2S
2S
for m == 1 mod8 for m == 5mod8
by (2.27). (c) Let p be odd and plm. Again (2.27) can be applied. J(t) = t 2 - m splits in lL/plL[t] into (t - n)(t + n) for m == n 2 mod p and remains irreducible if m is not a square modulo p. Hence, (2.27) yields
((n + mt)S + pS)(( - n + mt)S + pS) { pS = pS
for m == n 2 mod p for m¢(lL/plL)2 .
Using the Legendre symbol, the results (a)-(c) together yield the decomposition behavior of rational prime numbers p in quadratic number fields as follows:
Proposition (2.32) Let G = Q(m l ), 0 i= m a square-free rational integer, and dG the discriminant oJG.
The class group of algebraic number fields
394
With respect to S = CI(.£', G) the prime number p is said to be {. 1<=;>dG E(.£'lp.£')2 decomposed } { ramified G <=;>( d ) = O<=;>pld G un decomposed p - I <=;>dG¢(.£'lp.£')2. At the end of this section we consider the powers of rational prime numbers dividing the discriminant of an algebraic number field in dependence of the decomposition behavior of that prime number.
Lemma (2.33) Let G, F be algebraic number fields with maximal orders S, R respectively. Let [G:F] = nand p a non-zero prime ideal of R which decomposes in S into Sp = ~~" ... .~:r. Furthermore let {Jik (1 :::; k :::; f(~Jp), 1 :::; i :::; r) be a basis of SN\ over Rip and CtijE(~t l\~{)n(n~= l.v*i~:') (l:::;j:::; eJ Then the elements Ctij{Jik (1 :::; j :::; ei, I :::; k :::; fi = f(~d p); I :::; i :::; r) form a basis of SipS over Rip. Proof First we show (SipS: Rip) = n. Namely, if hF denotes the class number of F, then p"f = ).R for suitable AER and this implies N(pS)"f· = N(AS) = NF/O(NGIF(A»I
= INF10(A) I" = N(p)"f
ll
= INF/O(A") I
•
For an ideal p of R let Cl>ps: S --. SipS denote the corresponding residue class mapping. A subset M of S is called modulo p independent, if {Cl>ps(m)lmEM} is linearly independent over Rip. For i = 1, ... , r we choose subsets Mi = {{Ji\, ... ,{JifJ of S such that Cl>
0;..= 0iv
-Yijmod~~,
=0 mod ~ii
(1 :::;v:::;r, v#i)
by the Chinese remainder theorem, chapter 2 (2.17) (1 :::; i :::; r). Then the Ctij=Oij+Yij are in (~tl\~{)n(n~=l.Vfi~~') (1 :::;j:::;e i ; 1 :::;i:::;r) and it remains to show that the Ctij{Jik (1 :::; j :::; ei, 1 :::; k :::; fi; I :::; i :::; r) are linearly independent elements of SipS over Rip. Any relation
of course implies ej
I~
I 1 kI 1 YijkCtij{Jik = 0 mod ~ii
j=
=
(1:::; i :::; r).
The ring
395
Of"
We fix the index i and carry out induction over j. f;
j = I: k
f;
L= YilklXilfJ ik == 0 mod \.l3i implies L I
YildJik == 0 mod \.l3i
k= 1
because of the choice of the a li' hence Yilk == 0 mod p because of the choice of the {Jik (I ~ k ~ fJ j~1
j - I ~ j:
~
~
L L YiKklXiK/Jik + L YijklXij/Jik == 0 mod \.l3{ with the double
K=lk=1
k=1
f,
sum being congruent 0 modulo p. Then
L YijklXij{Jik == 0 mod \.l3f
k= I f;
and
L YijdJik == 0 mod 'l3i' Yijk == 0 mod p (I ~ k ~ fi) as above.
k= I
We apply (2.33) in the case F
= 0.
o
Lemma (2.34) Let G be an algebraic number field of degree nand S = CI(.£', G). Let p be a rational prime number and a I' ... ,IX" elements of S such that the canonical images IXI, ... ,IX" of al, ... ,a" in SipS form a basis of SipS over .£'/p.£'. Then the index of the .£'-order 0 generated by IX I , ... , a" in S is not divisible by p. Proof We assume pl(S:o). Then there is {JES\O such that p{JEO and p{J = O. Hence, p{J = 'L7 = I milX i , not all mi == 0 mod p, yielding a non-trivial presentation of 0 by 1X 1 , ••. , IX" of SipS, certainly a contradiction. 0 An easy application of chapter 3 (2.9) yields
Corollary (2.35) 7he discriminants d(S), d(o) of the .£'-modules S,o of(2.34) satisfy d(o) = a 2 d(S) (aEN, pIa).
Lemma Let YI"'" y" be the elements lXijPik of (2.33) i/l the case F pkl(det(yjj))I';;',},;;,,f for k = L:r= I (e i - l)fi = n - 'Lr= .Ii'
(2.36) = 0, P = p.£'. Theil
Proof Let Yv be of the form lXij{Jik with j ;;::: 2. Then Yv is contained in every prime ideal \.l3" of G (I ~ p. ~ r). Let L be the normal extension of G/O and q be a prime ideal of L lying over p.£'. Then q n S is a prime ideal of S containing p and therefore Yv' Hence, Yv lies in all prime ideals q of L which contain p.£'. If is the extension of a O-isomorphism ¢ of G to L, then (Yv)Eq for a fixed prime ideal q of L lying over p.£' (namely, -I(Yv)E-I(q) which itself
The class group of algebraic number fields
396
is a prime ideal of L lying over pZ and therefore containing y..). Thus we obtain /I
Tr(yvY/,) =
L hv)h/.)EqnZ =
pZ.
i= 1
Therefore all rows v of the determinant det (Tr (YvY/.)I';; ,. /.,;;,,), which do not correspond to indices (ii, ik) of aJJ;y are divisible by p. 0 (2.37)
Corollary p" -~i= Ihld(S). As another corollary we again obtain (2.30).
Exercises 1. Let p be a non-zero prime ideal in OF' Prove that the least natural number contained in p is a prime number. What about the reversion? If n is a non-zero ideal of OF for which the least natural number contained in n is a prime number, is n necessarily a prime ideal? 2. Using(2.31) and the product formula of the norm show that hF = 2 for F = Q( - 5)!. Then prove that 2y 3 = x 2 + 5 has only the solutions x = ± 7, y = 3 over 71. 3. Let f(t) = L7=oQ j tn -;E7L[t] be monic and irreducible. Let p be a rational prime number such that prl an , pr+ Ifa n,pr la; (l ~; ~ 11- I) for some rEN. Let p be a zero of f and F = Q(p).
(a) Prove that for R = CI(7L, F) the ideal prR is the 11th power of an integral ideal. (b) Determine mEN maximal such that pm divides the discriminant df • of F. (Note: For r = 1 the polynomial f is an Eisenstein polynomial and therefore necessarily irreducible.) 4. Let R = 7L[2;] = 7L + 2;7L, i 2 = - I. Give straightforward proofs of (a) (b) (c) (d)
R is not integrally closed; IRis not a group; R is Noetherian, every non-zero prime ideal of R is maximal.
5. Let R be a Dedekind ring containing 71. Prove: (a) For any non-zero prime ideal p of R there is exactly one prime number p subject to p;2 Rp. (b) For U(R)n7L = {± 1} the ring R contains infinitely many prime ideals.
6.3. Ideal calculus To determine the ideal class group CI F := lo/H of. of an algebraic number field F it suffices to know a representing element of each ideal class. The appropriate choice is an integral ideal a of norm N(a) ~ M f', where M F is the Minkowski constant for F. Each such ideal a has a presentation
Ideal calculus
397
nr=
a= I pfi (pj distinct prime ideals, ejEN, 1 ~ i ~ r, rEN). Because of the multiplicativity of the ideal norm each Pi also satisfies N(Pi)~MF
(I
~i~r).
Each prime ideal Pi divides exactly one rational prime number P = P(Pi) and N(Pi) is a power of p. Hence, it suffices to consider all rational prime numbers (3.1)
such that PI = 2, P2 = 3, P3 = 5, ... , and Ps ~ M F < Ps+ t. For each Pi (I ~ i ~ s) we need the prime ideal factorization of PiOF in F: PiOF =
tI pfF
(riE N; eijE N; 1 ~j
~ ri; 1 ~ i ~ s),
(3.2)
j= I
to obtain a full set of representing elements for CI F among those ideals (3.3) satisfying (3.4)
This process will become efficient after some additional considerations with which we shall deal in section 5. One of the greatest difficulties in this context is to develop a method for testing whether two ideals are equivalent. This will be done in section 4. In this section we shall mainly be concerned with the task of developing methods permitting efficient operation with (integral) ideals. I t is clear that the abstract definition of an ideal is not useful for constructive purposes. However, we already know that the ideals a of OF can be presented in two ways:
via a 'l-basis a = 'la l + ... + 'lan,
(3.5a)
by two generating elements, one of which is arbitrary in a and usually chosen from anN (for example, N(a) will do).
(3.5b)
This was shown in the two preceding sections. Clearly, the second presentation is less storage consuming. For [F:Qi] = n the presentation of an integer of OF via a fixed integral basis W t , ••• , Wn requires n rational integers. Therefore a presentation of an integral ideal a according to (3.5b) only takes n + 1 rational integers compared to n2 (respectively n(n + 1)/2 as shown below) using (3.5a). This clearly favors (3.5b). However, fundamental problems - for example, the computation of the norm of the ideal a - can hardly be solved with this method of presentation. So we are bound to use both possibilities of representing a by rational integers. In the
398
or algebraic number fields
The class group
sequel we shall consider in detail for which problems either one of those presentations should be used. We remark that the presentation of a fractional ideal a just requires the storage of an additional positive integer b such that ba is integral. First we shall discuss ideal presentations of the form (3.Sa) in case the integral ideal a is given in the form a = aO F + ao F. We easily derive a l'-basis of a as follows. Let Ma, Ma be the regular representation matrices of a,a, respectively. The composite matrix M.:=(M a :M a )El'n x 2n is reduced into its Hermite normal form H(M.) for which the last n columns are all O. By HM. we denote the n x n matrix consisting of the first n columns of H(M .). We claim that (WI'"'' wn)H M. is a l'-basis of a, hence a can be represented by n(n + 1)/2 rational integers. To prove this we note that aWl,,,,, aw", aWl"", aw" is a system of generating elements of a over 1'. But the transformation to the 2n elements consisting of the inner products of (WI"'" w,,) with the columns of H(M.) was by a unimodular (hence invertible) matrix. Similarly we obtain a l'-basis for any ideal a given by a finite number of generators a l , ... , akEo F (kEN). Therefore we can consider integral ideals a presented by a l'-basis of the form a j = " hjjwj
L
(1 ~ i ~ n; HM. = (h jj)).
(3.6a)
j=j
Because of chapter 3 (2.9) we obtain for the norm of a n
N(a) = (oF:a) = det(HM.) =
fl h
jj •
(3.6b)
j= I
An element fJ = L'J= I bjwj of XI, ... ,XnEl' satisfying
OF
is contained in a, if and only if there are
Hence, (3.6c) where the terms on the right-hand side are computed recursively. Another useful application of that presentation is the determination of the smallest natural number x contained in a. If we choose the integral basis WI""'Wn in such a way that W,,= 1, then we have b l =b 2 = ... =b,,_1 =0 in the presentation x = biwi + ... + b"w" and (3.6c) implies that Xl = X2 = ... =X,,_I = 0 and x = b" = h""x". Hence, min anN = h"" for this choice of an integral basis
WI"'"
w" of OF'
(3.7)
399
Ideal calculus
We proceed to a 2-element presentation (3.5b) of an ideal o. Again we consider the problem to decide whether P= 'Lj= I bjWjEO F is contained in a. For a = aO F + O:0F (aEN,o: = aiw i + ... + a"wIIEo F) we have pEa, if and only if there exist elements = 'LJ= I XjWj' 11 = 'L'J= I YjWj of OF satisfying
e
P=
a¢
+ 0:11.
(3.8a)
We transform (3.8a) into a system of linear equations by setting WjWj
" = L
mjjkw k (mjjkEZ),
(3.8b)
k=1
bk/=
L" mjjka j
j=
(1 ~k,j~lI; B:=(bkj »·
I
(3.8c)
Then (3.8a) is equivalent to (3.9)
Therefore (3.8a) is solvable precisely if the system of linear congruences b== Bymoda
(3.l0a)
has a solution YEZ". For a=
n" p~i
(U,kjEN, pj distinct prime numbers, 1 ~ i ~ u),
(3.10b)
j= I
the solvability of (3. lOa) is tantamount to the one of b ==
By(i)
mod p~i
(1 ~ i ~ u).
(3.10c)
But the solutions of (3.l0c) (if there are any) are easily calculated for each i (1 ~ i ~ u) by a Gaussian type algorithm. If we indeed obtain a solution y(i) for each i, then we compute ml , ... , muEZ subject to
" m;(apj-k i ), 1= L j=
(3.lOd)
I
and thus, finally, a solution y of (3.l0a) via y = " mj(apj-k')y(i).
L
j=
(3.l0e)
I
This method has the advantage that all numbers occurring during the calculations have an absolute value bounded by a. It is especially favorable for our considerations, since the natural numbers a which have to be discussed in connection with class group computations usually contain very few prime divisors (compare section 5).
The class group of algebraic number fields
400
As already mentioned in the introduction we are first of all interested in special 2-e1ement presentations of ideals which allow to multiply the ideals in terms of their generators. Indeed, it turns out that we can present a, b by (a, a), (b, {J), respectively, such that ab is presented by (ab, af3). Let PI'" ., Pm be all prime ideals of OF dividing a, a, b, f3 such that we have presentations aO F = Ilr= 1 p{,(a), and so on. Then ab = (ab, afJ) holds if we require min (vj(a) + vj(b), vj(a) + vj(fJ), vj(a) + vj(b), vj(a) + vM1))
= min (vj(a) + vj(b), vj(a) + vMJ»
(l ~ i ~ m).
(3.11)
In the sequel we denote by P the set of all prime numbers and by P a (possibly empty) subset of P. Furthermore, let PF := {pEfFlp a prime ideal, P divides POF for some pEP}
(3.12)
be a set of prime ideals of OF' each prime ideal of PF lying over some prime number p of P. If P is finite, then there is a natural number a (a = I for P = 0) such that a is exactly divisible by the prime numbers pEP. In that case we also write P(a)
instead of P.
(3.13) (3.14)
Definition
Let P ~ P and aEfF' A couple (a, a)EN x r is called a P-normal presentation of a, if the following four conditions are satisfied: (i) a = aO F + ao F , (ii) a = IlpEPFP·p(Q) (vp(a)EZ), (iii) aO F = IlpEPf.p·p(a) (vp(a)EZ;>o), (iv) NOPE PF occurs in the prime ideal presentation of aa - 1.
This definition seems to be somewhat artificial, but the connection to (3.11) will be immediate via the following criterion. Also we note that a P-normal presentation in the sense of (3.14) need not even exist. Its existence will be proved only under additional restrictions on P (see theorem (3.21)). For example, a P-normal presentation in case of P = 0 implies a = OF' a = I and a arbitrary in OF' This also follows from Lemma (3.15) Let P ~ P and a E f F' Then (a, alE N x F x is a P-normal presentation of a, if and only if the following three conditions are satisfied: (i) a = IlpEPf. p"p(O) (vp(a)EZ), (ii) aO F = IlpEP F p"p(a) (Via)E£';>o, via) ~ vp(a» (iii) ao F = Il PEP p"p(O)Il qE(P\P)f' q"q(') (v q(a)EZ;>o) • F
401
Ideal calculus
Proof F x satisfy (i)-(iii) of the lemma. Clearly, aD F + ao p = a, and (i)-(iii) of (3.14) are fulfilled. Furthermore, aa - 1 = rIqE(I'\PI .. 'l,·,(a l, hence
"<=" Let (a, a)E N x
also (iv) of (3.14) is satisfied. "~"
According to (3.14) we at once obtain (i), (ii) of the lemma. We note that (iv) of (3.14) implies
n
aa - I =
-I
q"q(a"
I (vq(aa-I)E£').
qE(P\PI..
Because of
a = ao p + ao p = ao p + aa - 1 a = =
n PEP..
pmin(".(tll,,'.(a))
n
n
p"p(tl i
pEP..
+
n qE(I'\PI"
- I
q"q(a"
I
n
p"p(a l
PEP"
qmin(O"'q(aa - '))
qE(P\PI"
and (ii) of(3.15) already being established we must necessarily have vq(aa -I) ~ 0
0 for all qEW\P)p. We note that this criterion is not suitable for practical computations since it requires full knowledge of the prime ideal factorization of a, ao p , ao p , However, it is a very useful tool for developing ideal arithmetics in the sequel. Proposition (3.16) Let Pc;;;, IP' and a, bE I p. If (a, a), (b, {J) are P-normal presentations of a,b, respectively, then (ab, a{1) is a P-normal presentation of abo The proof is straightforward using (3.11) and (3.15) (see exercise I). A special case of multiplication is forming powers of an ideal.
Corollary (3.17) Under the premises of(3.16) the couple (alii, am) is a P-normal presentation of am (mEN). We note, however, that for any presentation a = ao p + rxo p we obtain the powers alii in the form am = amop + amo p (see exercise 2). We proceed to compute the inverse of a normally presented integral ideal.
Proposition (3.18) Let P ~ I? and aEI F be integral with P-normal presentation (a, rx). Then each
402
The class group of algebraic number fields
bE N n aOF is the product of two natural numbers c, d such that
n
cO F=
p"p(c),
and (1, da -
I)
n
dO F=
PEPf
q",(el),
qE(P\P)f'
is a P-normal presentation of a -
I,
Proof For bEN nao F we set
c:=
n
pVp(bl,
d:=
n
pVp(b)
pEP\P
PEP
and the first statement of the proposition is immediate. For a = npEPfP'P(O) obviously a -I = npEPfP -1'p(O) with - vp(a)E.£'",,0 since a was integral. Therefore
1EO F with 10 f · = OPEPFP o satisfying (ii) of (3.15). Finally, da - 10 F =
n
P - "p(O)
PEPF
n
q"
I'.(.H I'.rel )
qE(P\P),
and the exponents - via) + Vq(d) are non-negative because of dEao F. Hence, the conditions of (3.15) are satisfied, and (1, dex - I) is a P-normal presentation of a-I. 0 If the natural number a in a P-normal presentation (a, a) of an integral ideal a has specific properties, it yields the decomposition of a into a product of two ideals.
Proposition (3.19) Let a E J F be an integral ideal with P(a)-normal presentation (a, a). Any factorization a = bc (b, CE N, gcd (b, c) = I) then implies a factorization of a via a = be for b = bO F+ aOF' e = cO F + ao F, and (b, a) is a P(b)-normal presentation of b, (c, a) a P(c)-normal presentation of c. Proof The case b = 1 (or c = 1) is trivial. For b> 1, c> 1 we split the set P(a) into P(a) = P(b)u P(c) and obtain
bO F=
n pEP(h),
p,'.(h),
cO F=
n
p",.(e).
PEI'(c)f
Clearly, (b, a) and (c, a) are normal presentations of b, e, respectively, since a was integral. Also be = b n e ;2 (bc, ex) and on the other hand, obviously, be = (bc, ba, ca, ( 2 ) ~ (bc, a). 0 The normal presentations also allow us to compute quotients of suitable integral ideals very easily. This will be used later on. Let a, be non-zero integral ideals of F with P(a)-normal presentations (a, a), (a, a), respectively. Let min (&oFn N) = cd such that C = OpEP(a)PVp(C), d = OpE"\P(a)pVp(d).
a
Ideal calculus
403
According to (3.18) we have (3.20a)
(1, d& - I) is a P(a)-normal presentation of a-I, hence by (3.16) (a, IXd&- I) is a P(a)-normal presentation of
ao. - I,
and, of course,
(3.20b) (3.20c)
Before we consider the application of normal presentations to the task of factoring an ideal into prime ideals we certainly must prove the existence of such presentations under suitable conditions.
(3.21 )
Theorem Let a, bEN, IXEO F, IX i: 0, and a P(ab)-normal presentation.
= aOF + b-1IXOF
an ideal of F. Then a has a
Proof
Let aO F =
n
p,.(a),
n
bO F =
pEP(ab)F
p,.(b),
IXOF =
pEP(ab)F
n
p,.(a)
pEP(ab)F
n
q'q(a).
qE(P\P(ab))F
Firstly, we show the existence of a !(ab)-normal presentation of the integral ideal ba
= abo F + ao F =
n
pmin(,.(a) + ,.(b).,·.(a)).
pEP(ab)F
For each pEP(ab)F choose PpEP min(,.(a)+ ,.(b). ,.(a)) \
p min(v.(a) +v.(b), vp(a)) + I.
Then by the Chinese remainder theorem, chapter 2 (2.17), we obtain PEOF satisfying P == Pp mod pmin('p(a)+ v.(b)"p(a))+ I for all pEP(ab)F' hence POF =
n
pmin(I'p(a)+'p(b)"p(a))
pEP(ab)F
n
q'q(/l),
qE(P\p(ab))F
(Vq(P>EZ~o, viP> = 0 for all but a finite number of q). Therefore (ab,p) is a P(ab)-normal presentation of ba. In the second part of the proof we show that P(ab)-normal presentations (ab, P> of aboF + POF and (a, b- ' P> of aOF + b - I POF (a, bEN, PEO F, Pi: 0) are
in I-I-correspondence. Using (3.15) we obtain the following chain of equivalences: b - 1 a:= aO F + b - 1 POF has P(ab)-normal presentation (a, b -I p)
¢>vp(P> - vp(b) = vp(b-'a):>( vp(a) ¢>vp(P} = vp(a):>( vp(a)
+ vp(b)
VpEP(ab)F
VpEP(ab)F
¢>a = aboF + POF has P(ab)-normal presentation (ab, Pl.
0
We note that the underlying set P of prime numbers - P(ab) in (3.21) - has
404
The class group of algebraic number fields
to be finite for the application of the Chinese remainder theorem. Hence, P-normal presentations in the generality of definition (3.14) need not always exist. Unfortunately the proof of (3.21) is not suitable for constructive purposes, either, since it makes use of prime ideal factorizations which are difficult to obtain in general. In the sequel we therefore develop other methods of determining normal presentations of ideals. A first step into this direction is the following criterion. (3.22) Lemma Let aE N, rxEO F, II. =1= 0, and a = aO F + rxo F. Then (a, 11.) is a P(a)-normal presentation of a, if and only if
gc
d(
min(rxoFIIN»)_ - 1. gcd(mm(rxoFII N), a)
a,.
(3.23)
Proof
We note that condition (3.23) means that for every prime number p which divides a and for which pk divides min (rxOF II N) also pk divides a, i.e. the exponent of p has to be larger for a than for min (rxOFII N). Using (1.11) we obtain for m:= min (rxo FII N): mO F
=
n
n
p"p(m)
pEP(a)f'
q"q(m),
(3.24)
qE(P\P(a))F
with vp(m)
~
vp(rx),
vq(m) ~ vq(rx) ~ O.
Hence, if (3.23) is satisfied, we have 0= min (vp(a), vp(m) - min (vp(m), vp(a»)
for all pEP(a)
and therefore vp(m):S;; vp(a) because of vp(a) > 0 for all pEP(a)F' This yields vp(rx):s;; vp(a) for all pEP(a)F' and (a, 11.) is a P(a)-normal presentation of a. On the other hand, let (a, 11.) be a P(a)-normal presentation of a and let us again assume (3.24). For qE(p\P(a»F clearly via) = 0, hence min (vq(a), vq(m) - min (vq(m), vq(a») = O. To establish (3.23) it therefore remains to show that min (vp(m), vp(a» = vp(m) for all pEP(a)F' For this purpose we factorize minto m = bd such that
bOF --
n
p"p(m) ,
dO F
np
pEP(a)F
q"q(m), I
qE(P\p(a))F
and gcd(b, d) = 1. Then we obtain ado F =
n
=
pEP(a)F
"p(a)
n
q "q(m) £; 11.0 F
qE{P\P(a))F
because of vp(a) ~ vp(rx), vq(m) ~ Vq(rx). But m = min (rxo F II N) implies mlad (otherwise ad = Q(ad,m)m + R(ad,m) and R(ad,m) would be a smaller natural
Ideal calculus
405
number than m in OW F). This of course yields bla and therefore vp(m)::::; vp(a) for all pEP(a)F· 0 This criterion is very useful for a normalization procedure. Because of the second part of the proof of (3.21) it suffices to develop such a procedure for integral ideals a = aO F + (X0F (aE N, (xEO F, (X i= 0). We remark that the trivial cases a = 0 or (X = 0 have obvious normalizations: a = aOf" has the P(a)-normal presentation (a, a); a
= (x0f"
has the P(I N((X) I)-normal presentation
(3.25a)
(I N((X)I, (X).
(3.25b)
In the general case we know that a has a P(a)-normal presentation, i.e. only the generator (X must be changed appropriately. We already noted that the straightforward method of the proof of (3.21) is not to be recommended. Instead we use a probabilistic approach which turned out to be highly successful in actual calculations. To obtain an appropriate element (x' from (X such that (a, (X') is a P(a)-normal presentation of a = aOf" + (X0F it suffices to consider elements (3.26a)
e e
Hence, we just search for potential candidates among those elements of Of" whose coordinates in the given integral basis are small, i.e. we choose bounds SjEN (I::::; i::::; n) such that the coefficients of in (3.26b) satisfy
Ixd ::::; Sj
(I::::; i ::::; n).
(3.26c)
This yields the following 'heuristic' algorithm.
Algorithm for the computation of a normal presentation of an ideal
(3.27)
Input. An integral basis WI' .•• ' Wn of OF' (xEO F, aEN, bounds Sj (1 ~ i ::::; n). Output. Either a P(a)-normal presentation (a, (X') of a = ao f · + (x0f" or 'No normal presentation found'. Step 1. (Initialization). Set Vj~ - Sj - 1 (I ~ i ~ n). Step 2. (Change of v-coordinates). Set i ~ n. Step 3. (Increase vJ Set vj . - Vj + I. For vj > Sj go to 5. Step 4. (Construct (X'). Set (X' ~ (X + aI:7= I VjWj and check, whether (3.23) holds for (a, (X'). If this is the case, print solution (a, (X') and terminate. Else go to 2. Step 5. (Decrease i). For i = 1 print 'No normal presentation found' and terminate. Else set Vj ~ - Sj - I, i ~ i - I and go to 3. Remarks
The algorithm should be carried out only if (a, (X) is not yet a P(a)-normal
406
The class group of algebraic number fields
presentation. In case of (l/a)exEo F we obviously have the solution ex' = a (see (3.25a)) and should therefore not use the algorithm. The bounds Si should be less than a of course. Making use of the second part of the proof of (3.21) the algorithm can also be used to compute a normal presentation of a fractional ideal. Generally the computation of 2-element respectively 2-element-normal presentations of ideals in connection with class group computations is much easier. Namely, for those prime numbers p not dividing the index (OF:Z[P]) theorem (2.27) yields a 2-element presentation for those prime ideals p containing PDF in the form p = PDF + exo F, ex = g(p), where g(t)EZ[t] is a monic polynomial dividing the minimal polynomial of pin pZ[t]. Clearly, (p, g(p)) is a P(p)-normal presentation of p, if the ramification index e = ep of p is greater than one. For e = 1 it is still a P(p)-normal presentation in case of g(p)¢p2. The latter can be easily tested. Finally, for e = 1 and g(p)Ep2 a P(p)-normal presentation of p is given by (p, g(p) ± p). Prime numbers p subject to pl(OF:Z[P]) are somewhat more difficult to deal with. Similarly to (2.27) we obtain a factorization of PDF into ideals ai (1 ~ i ~ k) of the form ai
= PDF + fi(p)OF
(flt)EZ[t] monic and non-constant).
(3.28)
Then we need to test whether those ideals a i are prime ideals. Since the non-zero prime ideals of OF are maximal the following proposition is immediate.
Proposition For any non-zero proper ideal a of OF we have
(3.29)
(i) a is a prime ideal, if and only if a + xO F = OF for all XEO F\ a. (ii) All y, ZEO F subject to y - ZEa satisfy YOF + a = ZOF + a. (iii) YOF + a = - YOF + a for all YEO F. Because of (3.29) (ii) it suffices to check all x of a complete residue system of 0F/a in (i), whether XO F+ a = OF' and (iii) further restricts the number of elements x to be tested. A complete residue system of 0F/a is given by the elements of (compare (3.6a))
h..
-~<
2
h .. .~~ y, '" 2 '
(3.30)
This follows from the construction of H M n and chapter 3 (2.9). Because of (3.29) (iii) we can restrict possible candidates to the set R + of those elements
407
Ideal calculus
of R for which the non-vanishing coefficient of lowest index i is positive. If YOF
+ 0 = OF for all
(3.31a)
YER +,
respectively (3.31 b) then
0
is a prime ideal according to (3.29). Otherwise we obtain an element
YER+ such that
(3.32) If 0 is represented by two elements a, a, however, we still need to construct a 2-element presentation for O. As a first generator for 0 we choose ii:= P since PDF c 0 yields P = min 0 n N = min 0 n N. A second generator fi subject to a = iioF + fio F can be chosen from finitely many appropriate elements of OF (see exercise 4). Extensive calculations showed that a suitable element fi is very likely contained in the set {P=jtlkjfidPt:O,
j
= min {ilk
j
kj E{-I,O,I},
l:::;i:::;n;
kj =1
for
(3.33)
t: O} },
where fi1, ... ,fin is a Z-basis of a being calculated from the representation matrices of a, a, y. If 0 is a prime ideal lying over PDF' we obtain from its two generators ii, fi a P(p)-normal presentation as before for those prime ideals q lying over qOF for qf(0F:Z[P]). Using (3.20) it is then easy to determine the exact power m of 0 dividing PDF and to reduce the task of factoring PDF into prime ideals to the factorization of po -m. Finally, we must discuss how to multiply ideals 0 = aOF + ao F, b = bO F + PDF in P(a)-, P(b)-normal presentations, respectively, where P(a) t: P(b). Then (3.16) can be applied only after we have computed P(ab)-normal presentations for both ideals. The latter is done inductively by calculating P(aq)-normal presentations for P(a)-normally presented ideals 0= aOF + aO F and q a prime number not dividing a. For the following construction we additionally require vp(a) ~ 1 for all pEP(a)F' In the beginning, when a is a prime number, this is obviously satisfied. If no prime ideal qEIP'F subject to qlqOF divides aOF, i.e. qlN(a), then (aq,Q:) is already a P(aq)-normal presentation of o. This is because q does not divide o. In case of q IN(a) we order the set P(q)F = {q 1"'" qk, qk + 1"", qm} of prime ideals lying over qOF such that aEqj (1 :::; i :::; k), a¢qj (k + 1 :::;j:::; m). Using the P(q)-normal presentations qj = qOF + PjOF (1 :::; i :::; m) we compute (3.34)
408
The class group of algebraic number fields
and obtain (aq, a) as P(aq)-normal presentation of a. Namely, for pEP(a)F the exponents vp(a) and vp(O() are equal and the exponents vp(a) satisfy vp(a) ~ max {vp(O(), I} according to our assumption, hence aEp Vp(Q\ pVp(Q)+ 1. For 1 ~ i ~ k we have a¢qj because of PH!· ... · Pma2¢qj and, finally, for k + 1 ~j:::; m the relations O(¢qj, Pk+ !· ... ·Pma2Eqj yield &¢qj' However, during class group computations it will usually be faster to test a few elements kEf 1, 2, ... , q -l}, whether qIN(O( + ka 2 ), since in that case (a,O( + ka 2 ) as well as (aq,O( + ka 2 ) are P(aq)-normal presentations of a.
Exercises 1. Prove proposition (3.16). 2. Let a = aO F + exo F (aEN, exEO F) be an integral ideal. Show that a" = a"oF + ex"OF' 3. Compute the prime ideal decomposition of POF for those prime numbers dividing d(f) for f(t) = t 3 - m and mE {3, 5, 6, 7} by the method of this section. 4. Let a = aO F + exo F + POF be an integral ideal. Using the results of the next section determine a finite set of elements of OF which is guaranteed to contain an element Y satisfying a = aO F + YOF'
6.4. On solving norm equations II As already noted at the beginning of the preceding section one of the main subtasks for the construction of the class group of an algebraic number field F is to decide whether two given ideals are equivalent. This is tantamount to the decision, whether a given ideal a of F is a principal ideal. It is clear that it suffices to solve this taks for integral ideals since the presentations (3.Sa), (3.Sb) for fractional ideals contain bEN such that ba C OF' Therefore a always denotes a non-zero integral ideal of F in the sequel. The following criterion is quite obvious: Lemma A non-zero ideal a of OF is a principal ideal, 0( such that IN(O()I = N(a).
(4.1)
if and only if a contains an element
Proof Let o(Ea. Then O(0F £;; a and there exists a non-zero integral ideal b of OF such that ab = O(0F by (1.9). Hence, N(a) = N(o(OF) is equivalent to N(b) = 1. But the latter holds precisely for b = OF because of N(b) = (OF: b). 0 For a given non-zero integral ideal a its norm is easily calculated as det (H M.) from the presentation (3.5a) of a. Therefore the task of deciding whether a is principal is essentially the task of deciding whether an element o(Ea C OF with IN(O() I = N(a) exists. This task is in principle solved by the following theorem.
409
On solving norm equations II
Theorem (4.2) For given aE N there are only finitely many non-associate elements a of OF such that IN(a)1 = a; those can be effectively computed. Proof The existence was already shown in chapter 5 (2.3). For computation let L: OF\{O} --> IR s +I: ef--.(cllogle(l)I"",cs+,logle(S+I)I)', where c- = J
{I2
1
for :!!;.j:!!;. S otherwise '
i.e. Llu f . = LI of chapter 5 (6.\). It was shown in chapter 5, section 6 that for independent units fJ I ' " . , fJr (r = s + t - 1) of OF the vectors c:= (c I" .. , Cs+ ,)', L(fJI)" ... ,L(fJS form a basis of IR s + I • Hence, for eEO F, e #0, there are x1"",Xs+IEIR such that r
L(e) =
L xiL(fJi) +
(4.3a)
XS+IC.
i= 1
Adding up the coordinates of the vectors on both sides of (4.3a) we obtain 10giNWI =
JI cjlogleUlI = JI JI xicjlogllllj)1 + S+I
S+I (
s+t
r
=
r
L Xi L Cj log IfJi(j) I + X i=1 j=1
)
xs+lc j
8+1 S+I
L
j=1
Cj (4.3b)
We set (4.3c) such that IA;I:!!;. t (I:!!;. i:!!;. r) and then :;:'= S',l i'., -ml, • .,-mr S, ... 'Ir ,
(4.3d)
~ being associate to e, yielding
10gl~(j)1 =
t Ai log IfJi(j) I + logl nNWI
i= 1
(1:!!;.j:!!;. s + t)
(4.3e)
for conjugates of ~ because of (4.3b). Therefore the ~(j) satisfy
1~(j)l:!!;. expO
JI
1I0glfJF)11
+ 10gl:WI) =:S(j),
1~(j)1 ~ exp ( - ~ itl IloglfJi(j)11 + 10gl:WI) =:R(j)
(1:!!;.j:!!;. n).
(4.3f) (4.3g)
Hence, a complete set of non-associate solutions aEo F subject to IN(a)1 = a can be easily computed by chapter 5 (3.8), with k = a. D
410
The class group of algebraic number fields
Remarks Using the ideas of (4.2) the amount of computations for solving IN(a)1 = a strongly depends on the bounds R(j), S(j) of (4.3f, g) (1 ~ j ~ n). Hence, the absolute values of the conjugates of '71'" ., '7, should be close to I which can often be achieved by applying reduction to L('7I), ... ,L('7,). If we search for an element 0( of an ideal a solving IN(O()I = a we just need to replace the basis co I, ... , COn of OF by a ;l-basis ai' ... , an of n, i.e. we replace R=OF by R=n. The advantage of solving norm equations by chapter 5 (3.8) rather than by the old standard method described in chapter 5 (3.5-6) is very well demonstrated by the following example from [I]. Example (4.4) 4 3 Let F be generated by a root p of the polynomial f(t) = t - 32t + 154t 2 + 1632t - 44. In OF we want to solve IN(O()I = k for kE{2,25, 100,257,295,512}. In tl seconds of computation time a program using chapter 5 (3.8) could show that no solution exists, whereas the old enumeration strategy would have needed t2 seconds:
k
t2
2
100
257
512
0.362
0.851
1.545
2.541
7600
385000
963000
20000000
The new ellipsoid method found a solution for k = 25,295 in about 0.08 seconds in each case, but the box enumeration strategy did not succeed in determining one in a reasonable amount of time (28 seconds). All CPU-times refer to a CDC Cyber 76. As already mentioned in chapter 5, section 3, we shall use the rest of this section to show how the new idea for solving norm equations originated from K. Mahler's paper [3]. For his concept of ceilings we need to introduce normalized valuations on the algebraic number field F. Clearly, voo.j(x):= Ix(j)1
(I ~j ~ n) with voo .j = Voo,j+t (s + I ~j ~ s + t) (4.5)
are archimedean valuations of F. Non-archimedean valuations of Fare obtained via the prime ideals. Let p be a non-zero prime ideal of F, and for each xEF x XO F
=
n
p"p(,)
(vp(x)E;l)
(4.6)
PEP f ,
be the prime ideal factorization of XO F• Then we define v = vp for all pEiFD F via (4.7)
On solving norm equations II
411
It is easily seen that the vp are non-archimedian valuations of F. We leave this 3S exercise 2. They are normalized valuations with respect to PEiP'F' The normalization effect is expressed in the product formula:
nE91 vp(x) n voo.j(x) n
1=
(xEF X),
(4.8)
j = 1
vp
where we denoted by 91 the set of all valuations vp of (4.7) for PEiP'F' The proof of (4.8) is straightforward:
npE91 vp(x) n VOO,j(x) = pEPn N(p)-v'<X)IN(x)1 n
v
j= 1
n N(p)-"l<) n N(p)'p(x) F
=
(because of IN(x)1 = N(XOF)) =1. Having established the product formula for normalized valuations it is now easy to introduce ceilings in a similar way as K. Mahler did in his 1964 paper 'Inequalities for ideal bases in algebraic number fields' [3]. It is convenient to set m:=91u{voo)1 ~j~n}.
Definition A ceiling is a function A: m-IR> 0 with the properties
(4.9)
(i) A(V p) = N(p)-Irp (hpE:l), (ii) A(V p ) = 1 for almost all VpE91, (iii) nVE~A(V) = 1. The connection between ideals and ceilings can be easily described. For an arbitrary ceiling A we set
n n
Q;.:=
A(Voo,j),
j= 1
R;.:=
n
A(Vp)'
(4.l0a)
vpE9l
Then the foIlowing properties are immediate:
Q;.,R;.EIR>o,
Q;.R;. = 1.
(4.l0b)
If we define the ideal a;. via (4.lOc)
(hpE:l, compare (4.9) (i)), then a;. is clearly in f F and satisfies N(a;.) =
n N(p/lp) = ~ = Q;.. R;.
(4.l0d)
PEP F
On the other hand, for every ideal aEfF we have a = npEPFphp
(hpE:l)
412
The class group of algebraic number fields
and obtain a (in general infinitely many) ceiling(s) A as in (4.9), since we have the freedom of choosing the values A(V) for vEID\91 arbitrarily with (4.9) (iii) as only side condition. (But compare (4.12).) Similar to principal ideals we can define principal ceilings: Definition A ceiling A is called a principal ceiling, A(V)h = v(x) for all vElD.
if there exist xEF'
(4.11) and hEN such that
Lemma (4.12) Let F be an imaginary quadratic number field. Then every ceiling of F is principal. Proof Since F has exactly one archimedean valuation v'" the value A(V",) of any ceiling A is completely determined by A(V p ) for all PEP F because of (4.9) (iii). Let hF be the class number of F. Then for all PEP F we have p"F = XpOF for and obtain a suitable xpEFx. Hence, we set x:=
nPEPFx:·
A(Vp )"F = N(pr hFhp = v~(x)
Especially, A(V",)2hF = IxI2 by (4.9) (iii).
for all vp E91. 0
Corollary (4.13) Let F be an algebraic number field properly containing iQ and F not an imaginary quadratic field. Then there exist non-principal ceilings for F.
Ceilings have the advantage that they allow us to transform the task of deciding whether an integral ideal 0 is principal - i.e. a decision, whether the equation (4.14)
is solvable for eEO - into a decision, whether a suitable positive definite quadratic form has minimum n = [F:iQ]. Namely, let A be a ceiling of the algebraic number field F under consideration which corresponds to the ideal a in the sense of (4.lOc). For a (fixed) basis lX" ••• , lXn of a we set (4.15)
Clearly, <1>). is a positive definite quadratic form which of course depends on the parameters A(V",) (l ~j ~ n). The inequality between arithmetic and geometric means yields
Computation of the class group
413
(4.17) Theorem Let a be an integral ideal of the algebraic number field F of degree n. Then a is principal, if and only if there is a ceiling A of F such that min {
(4.18)
Proof We note that equality in (4.16) is tantamount to A(Voo,j) = vw)a) for a = ao F , a = I:7= I xja j (1 ~j ~ n).
D The remaining difficulty in using (4.17) constructively is of course, that <1>). depends on s + t positive real parameters A(Voo,j) (1 ~j ~ s + t). Hence, we use a discretization method developed in [2J to obtain the result of S (3.8). A complexity analysis of this method shows that the number of arithmetic operations used by the new method is at most the square root of the number of operations of the old one provided that the box to be covered is large enough.
Exercises I. Show that the vp of (4.7) are non-archimedean valuations. 2. With respect to the use of chapter 3 (3.10-12) for solving chapter 5 (3.8e) develop an appropriate order for the vectors rEZ" of 5 (3.8f-h). (Compare exercise I of chapter 5 section 3.) 3. Write a program for solving norm equations.
6.5. Computation of the class group In the two preceding sections we developed the appropriate means to attack the problem of computing the ideal class group elF = IF/HF of an algebraic number field F = iQ(p). By computing we understand the determination of
structure constants n l , ••• , nu EZ;.2(UEZ;'o) such that n;lnj+ I (1 ~ i < u) and elF is isomorphic to the direct product ofu cyclic groups enj of order nj (l ~j ~ u), and of ideals a 1 , •.. , au of IF such that Then (S.la, b) yield
n (ajH
e = (ajH F)·
(S.1a)
(S.1 b)
nj
u
elF =
j=
F ),
1
(I'; j "
uJ
(S.2)
414
The class group of algebraic number fields
By (2.8) we know that the a j can be chosen integrally with norm below the Minkowski bound:
(5.3) As was discussed already at the beginning of section 3 we generate a list PF of all rational prime numbers P subject to the restriction P :::; M F' By (2.27) - or in case of P dividing (OF:Z[P]) by the methods of section 3 - we compute the prime ideal factorization of PDF for each pEPF. This produces a second list P F of all non-zero prime ideals P of OF dividing some pEPF • Obviously, we can eliminate those P from P F of which we know that they are principal ideals or that N(p) > M F • But for practical reasons it is recommended to remove only those p from P F for which all prime ideals q dividing the same rational prime number P have N(q) > M F • Hence, we assume that we have a list P F = {PI""'PV} (VEZ;><) of prime ideals such that (i) all non-zero prime ideals P of F with N(p):::; MF are contained in P F in case P #- PDF (pEP F), (ii) whenever PEP F is divisible by a non-principal prime ideal p with N(p):::; M F, then all prime ideals dividing PDF are contained in P F. It remains to determine the ideals a j and their orders nj of (5.1) from P F (1 :::; i :::; u) in an efficient way. A straightforward attack of this problem - i.e. choosing PI from P F computing its order ord(p,H F ) in ClF, doing the same for P2 and then constructing the subgroup
P F #- 0· Firstly, we construct a class-group-matrix C = (Cij)EZ VXV which sums up our information about equivalence relations among the ideals of P F. The row index i refers to the ith prime ideal pj in IfDF and the column index j to an element PjEF x (usually an integer) for which the prime ideal decomposition of P jOF is a power product of PI' ... , Pv the exponents just being the entries Cij (1 :::; i :::; v): v
PjOF
=
n pi'j
j=
(cijEZ).
(5.4)
I
Of course we shall choose Pi = Plj(l ~j ~ k) where Plj denotes the jth prime number of P F for which all prime ideal divisors are contained in P F. Clearly,
k < v.
(5.5)
Hence there arises the subtask of computing further elements PH I"'" PvEFx
Computation of the class group
415
subject to (5.4). That will be considered separately following algorithm (5.18). Here we just note that we know how to construct elements of small absolute norm of OF (and similarly of some Pi(l ::::;; i ::::;; from chapter 5, section 5. Usually they are still at hand from the computation of independent units of F and just need to be tested whether their norm is a power product of the Pij(l ::::;;j::::;; k). Having determined PI"'" Pv and the corresponding exponents cij (1 ::::;; i,j::::;; v) we apply column reduction to C and compute its Hermite normal form H(C). Let us denote the entries of H(C) by cij' The operations carried out correspond to the construction of elements PI' P2"" of F X which are power products of the Pi (1 ::::;;j::::;; v) with exponents in lL. Clearly, is divisible at most by prime ideals Pi with i ~ j. In case C is regular we know that P divides pjOF with cjj > O. If C is not regular then H(C) contains v - w zero columns for w = rank (C). Then we will produce new elements of r of the type (5.4) and insert the corresponding exponents into the columns w + 1, ... , v of H(C). Then we replace C by H(C) and start again computing the Hermite normal form of the new matrix. Thus we finally end up with a class-group-matrix C = (cij) which is regular and in Hermite normal form, i.e. a regular lower triangular matrix. Then det(C) = I Cii is already an upper bound for hF and C contains essential information about CI F. These remarks are summarized and extended by the following theorem.
v»
Pi
/ii
PI"" ,Pv-w
nr=
Theorem
(5.6)
Let I K denote the set oj all ideals oj F which are power products oj prime ideals oj iP'F = {PI"'" Pv}. Let HK be the set of all principal ideals contained in I K· Let A be the sublattice oJ !Lv consisting oj all cElL v such that I p/;EH K • Finally, let the class-group-matrix C Jor iP' F be regular. Then we have
nr=
(i) CI F ':!!.IK/HK' (ii) IK/HK ':!!. lLv/A, (iii) hFlldet(c)I. ProoJ (i) We consider the map
(1: IF/HF--+IK/HK: aHF ...... aH K, where aE/K is chosen such that aHF = aH F • This is possible since IK contains representatives of all ideal classes of F as is guaranteed by the Minkowski bound. We must show that (1 is a group isomorphism. We start to prove that (1 is well defined. Let a, bE/F with aHF = bH F and a, bEl K such that (1(aH F) = aH K , (1(bH F) = bHK • This implies
416
The class group of algebraic number fields
aHF=aHF=bHF=bH F and ab-1EH F. But then ab-1EHFnIK=H K and
aH K = bH K follows. Now, a is clearly a surjective group homomorphism and it remains to show that it is also injective. Let a, bEIF with a(aHF) = aHK = bH K = a(bH F). We conclude that ab-1EH K ~ HF implying aHf' = aHF = bH F = bH F. (ii) We consider the map v
r: I K -+7lv /A:
fl
P/il-+(C1,,,,,cv)'+A.
i= 1
Obviously, r is a group epimorphism with kernel H K' Hence, the isomorphism theorem for groups yields IK/HK ~ 7Lv/A. (iii) The columns C 1 , ... , Cv of the class-group-matrix C generate a sublattice A of A of equal rank. Hence, A is of finite index in A and we obtain hF = (7Lv: A) = (7Lv:A)!(A :A) because of (i) and (ii). But (7Lv:A) is just the absolute value of the determinant of the transition matrix of the standard basis of 7L v to the basis of A consisting of the columns of C (chapter 3 (2.9)). We note that (7Lv:A) = det(C) if C is in Hermite normal form. D Remark (5.7) For Idet(C)1 = 1 we get hF = 1 even without having to know any units of F.
In the sequel we therefore assume C = (cij) in Hermite normal form and det(C) > 1. In this case the information contained in C will in general not be complete. Any column j (1 ";;'j";;' v) of C with eJ) = 1 is superfluous for further considerations since Cjy = 0 (1 ,,;;, v <j) and the ideal class of Pj is representable by the prime ideals Pit (J-l > j) because of PjH F = (U:=j+ 1 Pit -c.i)H F • By deleting all such columns and the corresponding rows from C we obtain a matrix RC = (bij) of much smaller dimension, say w. Again RC is in Hermite normal form and det(RC)=det(C). Let Pit, ... , Pi w be the prime ideals corresponding to the rows I, ... , w of RC and {Ji. (1 ,,;;, v,,;;, w) be the elements of F corresponding to the columns of RC. For simplicity's sake we again denote them by PI"'" Pw, {J I,,,,, {Jw in the sequel. (This corresponds to a permutation of the rows and columns of C.) Before we continue to discuss the processing of RC a simple example will illustrate our reductions. X
Example (5.8) Let F = 4Jl(p) for p2 - 243p - 1 = O. We compute dF = 59053, n = s = 2,
M F = 121.5, and obtain 36 prime ideals in PF from the prime numbers 109, 103,83, 79, 73, 67, 61, 59, 53,47,43, 37, 29, 23, 19, 11, 7, 3. For C in Hermite normal form we obtain
417
Computation of the class group
PI
0
133
* ...
*
5
0
0
0
0
*
I
I I
*
... ...
0 0 5
and thus for RC
PI P2 PI
!sOl '
P2~
where P1170 F, P2130F' Hence, hFE{1,5,25}. Next we convince ourselves that IN(~)I = 3 is not solvable in OF' Therefore the smallest power of P2 belonging to HI' is 5, p~ = ((245 + 59053 t )/2)oF' But then pi (and thus PI itself) cannot be a principal ideal and we conclude hF = 25, Clf' =
(5.9) Remark It may give a little surprise that the prime ideals dividing larger prime numbers correspond to smaller indices. This is due to the following heuristic argument. Since the norms of the Pj (I ~j ~ v) are of small absolute value it is unlikely that for prime ideals pj with N(pj) big all entries cij (I ~j ~ v) of the ith row of the class-group-matrix have a common divisor greater than one. Hence, in the Hermite normal form H(C) of C the diagonal elements in the upper left hand corner will usually be I which makes it a little easier to construct RC from H(C). Also during the computation of H(C) from C the elements of the rows of higher index tend to grow. So we will usually find the biggest diagonal entries of H(C) in the lower right-hand corner. But those entries will then correspond to prime ideals of smaller norm, therefore such tests as will be needed for the solvability of norm equations will be less time consuming. So far we have only applied column operations to the c1ass-group-matrix. From now on we also use row operations. Then the columns of the truncated cIass-group-matrix RC do not correspond to prime ideals PI"'" Pw any longer but to possibly fractional ideals 1 " " , Ow for which we keep stored the exponents of their presentations by the Pi
°
n pt;j w
OJ:=
(mijE~;
I ~ i ~ w).
(5.10)
j: I
Our goal is to transform RC into a diagonal matrix diag(nl , ... , n.) (u ~ w) such that the ideal OJ corresponding to row i is of order nj in ClF and
The class group of algebraic number fields
418
or <
CIF = ~ I aiH F). The information contained in RC will in general not be sufficient for this purpose, i.e. the Smith normal form of RC can look quite different from diag(n l , ... , nul. Thus we need to construct CIF from RC under possibly existing hidden additional side conditions. Instead of trying to exhibit all of those - which is obviously not very efficient - we use as additional information that we can decide whether a given ideal is principal or not. We note that PI , ... ,Pw should be given in P(p)-normal presentation from now on. The matrix diag(n l , ... , nJ will be constructed from RC starting in the last row. Our essential information about a w:= Pw is (5.1la) In the usual way (compare chapter 2 (5.2, 3)) we compute
ord(pwHF) = :sw
(5.11 b)
by the methods of section 4. Clearly Sw is a natural number dividing bwW" In case of I < Sw < b ww we reduce the elements bWj (j < w) of the last row of RC modulo Sw and obtain
(5.llc) Then we set (5.lld) For Sw = I we delete line w from RC, replace w by w - I and carry out (5.llb-d) anew. In this way we either get w = 0 in which case we terminate with hF= I, CI F =
(I ~ i ~ w - p)
(5.12a) p-I
ord (ajH F) = bjj
=
TI
jH F ),
(5.12b)
(w - p + 1 ~j ~ w),
(5.l2c)
j~O
tlsw- p+ 21·· ·Isw, bi) = 0 (w - p + 1 ~j ~ w, i > j). sw-p+
w-
(5.12d) (5.12e)
The computation of Sw in (5.11) is therefore tantamount to the step p = 1. In the sequel we assume I ~ P < w. In each succeeding step we then need to determine the minimal exponent m such that P:_pEGp:= 01:J
Computation of the class group
419
Hence, we search for a minimal mEN such that
n aj_jE H
p-I m Pw-p
h·
F
(S.13)
j=O
for suitable hjEl. subject to 0 ~ hj < of m are immediate:
Sw- j'
0 ~j < p. The following properties
mlb w _ p.w - P ' PW-P' P:- p, p:~-rw-prlHF' if there is an index j, 0 ~j < p, such that bw- j.w-p > 0,
n
p-I
Pbw-p.w-P w-p
abw-~.w-PEHF W-) •
(S.14a) (S.14b)
(S.14c)
j=O
As we already saw in example (S.8) the occurrence of an entry bw- j.w-P > 0 for an index j with 0 ~j < p can be of advantage. Indeed, for bw-p,w-p = mk according to (S.14a) we obtain from (S.13), (S.14c) the conditions (S.1Sa)
If the entries bw- j,w-p do not vanish for all j (0 ~j < p), those conditions usually diminish the number of possibilities for m drastically. For example, if bw-p,w-p is a prime number and there is an index j (0 ~j < p) such that bw-p,w-plsw-j, bw-j,w_p¢Omodbw_p,w-p then m is different from 1 implying m = bw-p,w-p, hv = bw-v,w-p (0 ~ v < p), as in example (S,8). For all solutions of the system of congruences (S.1Sa) we need to test (S.13) with the methods of the preceding section. Since we usually expect m = bw-p,w-p we choose the order of the candidates for m to be tested again as in chapter 2 (S.2, 3). After those tests we know a solution of (S.13) and replace column w - p of RC via (S.1Sb)
Then we apply the elementary divisor theorem to the free l.-modules M = l.P+ 1 = EBr:ll.ej and its submodule T = EBr:ll.tj given by tl =(bw-p,w-p" .. ,bw,w-p)', tj=sw_p+j_1ej (2~i~p+ 1). This means to transform the matrix A satisfying (S.l6a) into its Smith normal form by unimodular row and column operations. Hence, we compute unimodular matrices U, VEl.(p+l)x(p+l) (as well as U- 1 ) subject to UAV=diag(dl, ... ,dp+ l ) (dp+l> djEN, dMi+l> 1 ~i~p)
as shown in chapter 3. The entries
iii)
(S.l6b)
(1 ~ i,j ~ P + 1) of U- 1 are then used
420
The class group of algebraic number fields
to replace Pw-p' aw-p+1,···,aw by b1, ... ,b p + 1 via
na
p/ll.i
bi·'-
p
w-p
ll ]+ I.i
w-p+j"
(5.l6c)
j= 1
Following that we must update the matrix RC. We begin by setting (5.l7a) The new (partial) columns cj := (b w - p •j , " " bw•j )' (1 ~ i ~ w - p) are obtained from the old ones upon multiplication by U: Cj+-UC j
(1 ~i<w-p).
(5.l7b)
Afterwards the new elements bw- j.j still need to be reduced modulo Sw- j so that they again satisfy
o~ bw- j .j < Sw-j
(l ~ i < w - p, 0 ~j ~ p).
(5.17c)
The new column w - p is to contain zeros below its diagonal entry: bj.w-p+-O
(w - P < i
~ w).
(5.l7d)
For sw-p = 1 we then eliminate row w - p and column w - p from RC: bij+- bj+ l.j
for i = w - p, w - p + 1, .. , w - 1, (5.l7e)
(l ~j < w - p), b jj +- bj+ l.j+ 1
and w+-w-l,
p+-p-l.
(5.17f)
Now we have again the possibilities of bw - p •w - P being equal to or greater than one. For bw- p.w- P = 1 we carry out (5.l7e, f) anew. For bw-p,w-p > 1 we increase p by one and proceed to the next step unless w - p becomes zero in which case we terminate. If the criterion of termination w - p = 0 is obtained, the last matrix RC yields the structure of the class group of F. To get (5.la, b) we just need to replace u by wand nj by Sj (l ~ i ~ u). The class number of F is given by w
hF=
n
j=
(5.18)
Sj.
1
As stated in connection with (5.5) we still must discuss the subtask of constructing elements f3 j EF X (k + 1 ~j ~ v) subject to (5.4) which are needed to get a regular c1ass-group-matrix C. Clearly, f3 j satisfies (5.4) if and only if
Er
IN(f3j)1
=
n qmq
(mqEif),
(5.19)
q€p~
where P~ denotes the subset of P F consisting of those prime numbers p of PF the prime ideal divisors of which are in IP>F' In an initial step we consider the elements of small (absolute) norm constructed for the determination of a system of independent (or fundamental)
Computation of the class group
421
units of F. Then we compute H(C) of the class-group-matrix e by factoring the elements considered initially. Either H(C) is already regular, or we are in need of special elements PEF x divisible by certain prime ideals p of IPF which can be read off from H( C). Then we apply the process of constructing integers of F of small absolute norm of chapter 5, section 5, but with a basis n I, ... , nn ofp instead of WI"'" Wn of OF' Thus all obtained elements are at least divisible by p and we choose those which pass the norm test (5.19). The determination of a factorization (5.4) is then obtained by the methods of (4.S-1 0), respectively
(3.20c). (5.20)
Remark
Since we cannot assume that the information about elF contained in e is complete even if H(C) becomes regular it is recommended to construct a few more elements PjEF X subject to (5.4) and to check whether adding the corresponding cij of (5.4) as additional columns to e decreases det(H(C)). If this is not the case for about five consecutive P/s we would expect that the information obtained on elF is 'nearly complete' and go on to compute Re, etc. Since the development of the means for computing elF and hF took place throughout several sections (sections 1-5) of this chapter we now present a summarization of all necessary steps. The whole procedure is split into four major subtasks.
I. Input and preparations The following data are INPUT:
N - degree of the field F under consideration; F(1)(1 ~ I ~ N) - the coefficients of a generating polynomial f(t) = t N +
N
L F(1)t
N- 1
for F, i.e. F = iQI(p)
1=1
for a zero p of f. From those all other pieces of F which are needed can be either computed by subroutines or by different programs and then also be added to the input. We especially need:
ZEC N - zeros of f(t), i.e. f(Z(1))
=0
(1 ~ I ~ N);
S, TElL~o - the number of real respectively complex conjugates of F,
N=S+2T; MDEN, M ElL NxN
-
coefficients of an integral basis WI"'" 1
N
L
i.e,wI=M(1,J)pJ-I MDJ=I (compare chapter 5 (S.4b)); in general
WI>""
WN
WN
(l~I~N)
of F,
.
should be reduced;
422
The class group of algebraic number fields
dF
-
the discriminant of F;
nEc NxN - n(l,J) contains the Jth conjugate of WI (\ ~ I,J ~ N); rE"lNxNxN _ r contains the multiplication constants for N
WIWJ
=
I r(l,J, K)WK K;I
(compare chapter 5 (8.5));
EE7LR xN_ coefficients of a maximal set {e l , ... , eR} of independent (or even fundamental) units of F, i.e. N
el =
I
E(l, J)WJ
(\ ~ I ~ R; R = S + T - I);
J;I
usually we assume that the vectors Lie l ) (\ ~ I ~ R) are reduced so that the conjugates of 8 1 will be of absolute value close to 1 (see chapter 5 (6.\) and the remark after chapter 6 (4.3)). We note that Z, n can be chosen in ~N, ~N xN, respectively, if we sepffrate the real and imaginary parts of complex conjugates of p (compare chapter 5 (8.9)). To calculate the coefficients of an element of OF given as a sum of powers of p in the integral basis we also need M - I. We further stipulate the existence of subroutines for computing norms of elements and a dual basis with respect to a basis of an order or of an ideal of Of"
//. Ideal factorization The Minkowski bound MF is computed from dF,N, T ((2.8)). Then we construct a list PF of all prime numbers p ~ M F (P F can also be obtained as part of a list of sufficiently many prime numbers contained among the input data). From PF we obtain a list P F of prime ideals p as described at the beginning of this section. We list those p in their representation by two generators together with their norm, their ramification index e p and their degree of inertia fp. (Though the first generator for p will usually be the prime number p divisible by p and N(p) is therefore determined by p and f p ' the storing offp is usually easier than to compute it anew when it will be needed in the program.) We also establish a subroutine which computes a 7L-basis for an integral ideal given by two generators. This itself needs a subroutine for the computation of the Hermite normal form of a matrix. Finally, we use a subroutine for factoring polynomials in 7L/p7L[t].
I II. Computation of the class-group-matrix C The class group matrix C is computed as described in the current section. Besides the entries corresponding to prime numbers p of PF we need subroutines for: (i) determining elements of small norm in OF or some integral ideal given by its 7L-basis; (ii) checking whether some integer {3 of OF whose norm is divisible by N(a)
423
Computation of the class group
is contained in that integral ideal a (here a is some power pk of a prime ideal p, and pk is obtained from p = POF + lW F as pk = pkOF + n;koF , see exercise 2 of section 3 and of this section). I V. Computation of CIF This was discussed in detail in this section. From C in Hermite normal form we compute RC and obtain hFldet(RC). Especially we need subroutines for the computation of the Smith normal form of a matrix and for solving norm equations (compare chapter 3, section 2 and chapter 6, section 4).
Let us finally remark that not all required subroutines are mentioned in detail. For example we need a subroutine for computing the Hermite normal form of a matrix, preferably also one using modular arithmetic. Also we did not go into detail about the construction of two generators of those ideals dividing (OF:~[P]) since this was already done in section 3. Of course the principal ideal test of section 4 is needed as most important subroutine. Once we know generators a l , ... , au of CIF subject to (S.la, b) the usually difficult problem of deciding whether two given ideals a, bEIF are equivalent can easily be solved. This will be discussed in the remainder of this section. Let a be a non-zero ideal of OF with ~-basis 1X1, ••• ,lX n. Then each eEa has a representation n
e=
L XjlXj j=
(XjE~)
(S.21)
1
and
(S.22) is a positive definite quadraticform of determinant N(a)2Id FI· Let such that
e= Lt= XjlXj
Q.(i) = min {Q.(X)IXE~n, x:;i: o}.
1
(S.23)
By chapter 3 (3.34a), (3.3Sa, b) we get Q.(i)" ~ y:N(a)2Id F I
(S.24)
and the inequality between arithmetic and geometric means yields
(S.2S) implying
(S.26) for
(S.27)
424
The class group of algebraic number fields
Hence, every integral ideal 0 of IF contains an element a such that IN(a)/N(o)J is bounded by ME' a constant only depending on F but not on o. Analogously as in the beginning of this section we determine a list IP E of non-zero prime ideals VI"'" VE of OF satisfying IN(Vj)J ~ ME (1 ~ i ~ E) and then a list of presentations
VjH F =
(.Il
O/U)HF (kijE'l.;>O,0
)=1
~ kij < lIj' 1 ~j ~ u, 1 ~ i ~ E)
(5.28)
together with non-zero elements n j , ii j of OF such that (5.29) For the OJ (I ~j ~ u) we assume (5.2). Then we can easily solve the following two problems for integral ideals a, bE IF:
Procedure for determining whether 0 is principal (5.30) Compute ~EO subject to (5.23) by chapter 3 (3.15). Compute the prime ideal factorization (5.31) Then
0
is principal if and only if E
L v kij=Omodll j
(I ~j~u)
j
(5.32)
j= I
because of (5.28). In case 0 is principal there hold equations If= 1 vjkij = /ljllj with nonnegative rational integers /lj (1 ~j ~ u). Hence we obtain (
n n";
E)
n ii "; n E
10 - I -
."
j=1
-
1/
j
j=1
j=1
0
j
ku,,; --
n n- "; n a E
1/
j
j=1
j=1
o
I' J jF
by (5.29), (5.31), (5.32) and (5.2). But the latter implies o= ~
E
II
j= 1
j= I
n (nj/ii j),,; n
aj-I'Jo F
(5.33)
and establishes a generating element for o.
Procedure for deciding equivalence of two ideals 0, b. We compute aEo F, c a non-zero ideal of OF such that ob- I =a-Ic
(5.34) (5.35)
by the methods of section 3. Then the equivalence of a and b is tantamount to c being a principal ideal. This is then tested by (5.30). If the outcome of the test is positive we also obtain {lEaF subject to c = {l0F by (5.33). But then obviously
aa = pb.
(5.36)
Computation of the class group
425
We note that (5.30), (5.34) can also be applied to fractional ideals n, b since there are integers a, bEO F such that an, bb are integral. This was already pointed out at the beginning of section 3. FinalIy, it is of some interest by how much the constants M F and M Ii differ since that is a measure for the amount of computations which are necessary to establish (5.28). Since the f" can be given explicitly only for n ~ 8 we present a list for M d M F for those n.
List of ME/MF for n ~ 8 n
S
2
2 0 3
3 4
5
6
7
8
4 2 0 5 3 1 6 4 2 0 7 5 3 1 8 6 4 2 0
(5.37)
ME/MF 0 I 0 \ 0 1 2 0 1 2 0 2 3 0 2 3 0 1 2 3
4
1.15 0.9\ 1.22 0.96 1.33 1.05 0.82 1.32 1.03 0.81 1.39 1.09 0.85 0.67 1.44 1.13 0.89 0.70 1.63 1.28 1.00 0.79 0.62
The list (5.37) seems to suggest that the bounds M F and M Ii don't differ by much for small field degrees and smalI absolute values of the discriminants. Thus the folIowing result is somewhat surprising. Proposition ME/MF ...... Ofor n ...... oo.
(5.38)
426
The class group of algebraic number lields
Proof Instead of Hermite's constants (3.3Sb), and obtain
y~
we use the upper bounds of chapter 3
ME/MF ~ (nn(~ yyl2
rO
+ 2 )2- '(nl)-I.
(S.39a)
Then the application of Stirling's formula yields for n ~ SO: log (ME/M F) ~!(nlogn + slog2 - slogn) +
(~+ 2)
(~+~) 10g(~ + 2) + tlog(2n) -
t log2
- t log (2n) - (n + !) log n + n
~
= ( log
(~ + 2 ) -
+ ! log
(~ + 2 ) -
log
n) + ~ + ~ (log 2 - log
n) - t log 2
! log n - 2
n+4 1) +2(log2-logn)-tlog2+t s log =2n( log~+
0+ r 2
n
2
8) -2
n2 ~O.l92n-0.22Ss-0.7t+!log ( 8+3n+6+~
n < - 0.033n - 0.2St + log 2 - 2.
(S.39b)
We note that 10g(ME/MF) is less than -1.38, -28.78 for n = 100, 1000, ~~~
0
Thus for large n the list of prime ideals needed to establish ideal equivalence is much shorter than the one actually needed for the computation of the class group.
Exercises
n,=
1. Let a be a fractional ideal with prime ideal decomposition a = I pj} (mJeZ) and assume N(pJ) = pI} (1 ~j ~ k). Determine meN (as small as possible) such that ma is an integral ideal. 2. Let a = Zcx l + ... + Zcx n be a non-zero prime ideal of OF and WI' ... ' Wn an integral basis such that CX i = r.J= I ail»} (1 ~ i ~ n). Develop an algorithm which determines for peFx the exact power of a dividing POF. 3. Compute hF and CI F for F = Q(mt), me{ - 21, - 14,79, 223}. 4. Compute hF and CI F for F = Q(m~, me{3,5,6, 7}.
APPENDIX: NUMERICAL TABLES
1 Permutation groups 1.1 Primitive groups of degree n:::; 12 1.2 Transitive groups of degree n :::; 7 as Galois groups 1.3 Diagrams of transitive permutation groups (4:::; n :::; 7) 2 Fundamental units and class numbers 2.1 Real quadratic fields F = O(m t ), m < 300 Explanation of tables 3.1-7.1 3.1 Real cubic fields with dF < 1000 3.2 Complex cubic fields with IdFI < 300 4.1 Totally real quartic fields with dF < 5000 4.2 Quartic fields with s = 2 and IdFI < 1300 4.3 Totally complex quartic fields with dF < 600 5.1 Totally real quintic fields with dF < 102000 5.2 Quintic fields with s = 3 and IdFI < 10000 5.3 Quintic fields with s = 1 and dF < 4000 6.1 Totally real sex tic fields with dF < 1 229000 6.2 Sex tic field with s = 4 and minimum discriminant 6.3 Sextic field with s = 2 and minimum discriminant 6.4 Totally complex sex tic fields with IdFI < 23100 7.1 Totally real seventh degree field with minimal dF 8 Integral bases Permutation groups 1.1 Table o/the primitive groups 0/ degree n:::; 12 Column 1 contains the degree n and its number k with respect to the degree in the form o.k, i.e. 7.4 means the fourth primitive group of degree 7. Column 2 contains the order of the group, column 3 gives the notation or a description as used in chapter 2, section 9. In column 4 we list the transitivity t of the group followed by a letter p, if the group is t-fold primitive. Whenever the group is doubly primitive so that the subgroup fixing the last integer on which the group acts is a primitive group
Appendix: Numerical tables
428
of degree n - I, this subgroup G._I occurs in column 5 by its degree and number. A .. +" sign in the last column means that the group consists of even permutations. (Reference: Charles C. Sims, Computational methods in the study of permutation groups, in Computational Problems in Abstract Algebra (pp. 169-83), J. Leech (editor), Pergamon Press, Oxford and New York, 1970.)
degree no. 2.1 3.1 3.2 4.1 4.2 5.1 5.2 5.3 5.4 5.5 6.1 6.2 6.3 6.4 7.1 7.2 7.3 7.4 7.5 7.6 7.7 8.1 8.2 8.3 8.4 8.5 8.6 8.7 9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10 9.11 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 11.1
order 2 3 6 12 24 5 10 20 60 120 60
120 360 720 7 14 21 42 168 2520 5040 56 168 168 336 1344 20160 40320 36 72 72 72 144 216 432 504 1512 !'9! 9! 60
120 360 720 720 720 1440 !'IO! IO! 11
notation or description 62 91 3 63 \114 64
G._I 2 3 2p 4
2.1 3.1 3.2
Hol(C s) 91 s 6s PSL(2,5) PGL(2,5)
91 6 66 C, 0 14 Hoi (C,)n9I, Ho.l(C,) PSL(3,2)
91, 6, {z --+az + blO # aelF a, belF a} {z --+az 2" + bla, belFa,a # O,k = 0, 1,2} PSL(2,7) PGL(2,7)
Hol(C 2 x C2 x C 2) \II a 6a
{z--+az + blaelF~,beIF9} {z--+az 3" + blaelF~,beIF9,k =0,1} {z--+az + bla,belF 9 ,a # O}
(9.1, {z --+ pz 31PeIF 9\IF~} >
+ bla,belF 9 ,a #O,k =O,I}
Hol(C 3 x C3)n\l19 Hol(C 3 x C3 ) PGL(2,8)
Hoi (9.8) 91 9 69 91 s 6s PSL(2,9)
66 PGL(2,9) (PSL(2, 9), {z --+ pz3lPelF~, zeIF9u {oo} }> Hoi (PSL(2, 9»
91 10 6 10 CII
+ + +
Cs 0 10
{z--+az 3"
+
2 3p 5 2p 3 4p 6
+ 4.1 4.2 5.2 5.3 5.4 5.5
+ + + +
2 2 5p 7 2p 2p 2p 3 3 6p 8 2 2 2 2 2 3p 3p 7p 9
+ 6.3 6.4 7.1 7.3 7.3 7.4 7.5 7.6 7.7
+ + + + + + +
+ 8.1 8.2 8.6 8.7
+ + + + +
2p 2p 3 3 3 8p 10
9.1 + 9.2 + 9.3 9.4 + 9.5 9.10 + 9.11
+ (Contd.)
Appendix: Numerical tables
degree no.
order
11.2 11.3 11.4 11.5 11.6 11.7 11.8 12.1 12.2 12.3 12.4 12.5 12.6
22 55 110 660 7920 t·ll! II! 660 1320 7920 95040 t·12! 12!
429
notation or description
Gn - I
+
D22
Hol(CII)n~11
+
Hol(C II )
2
PSL(2,11)
2p
MIl
4
~II
6
9p
II
11
PSL(2,11) PGL(2,11)
2p
Mil Mil
3p
3 5
~12
lOp
6 12
12
10.1 10.6 10.8 10.9 11.3 11.4 11.5 11.6 11.7 11.8
+ + + + + + +
1.2 Table of transitille permutation groups of degree n ~ 7 as Galois groups As in Table 1.1 we list in columns 1-3 the degree, the order and the notation of the groups, respectively. Column 4 contains the corresponding indicator function which is used to determine for a given monic irreducible polynomial of Z[t] of that degree, whether its Galois group is contained in the group of that row (compare chapter 2, section 10). An example of a suitable polynomial !(t)eZ[t] whose Galois group is exactly the one of column 3 is given in column 5. Finally, column 6 contains the discriminant of that polynomial. For the computation of the Galois group of a given monic irreducible nth degree polynomial!(t)eZ[t] (3 ~ n ~ 7) using Table 1.2 we refer to chapter 2, section 10. For the choice of the appropriate indicator function Table 1.3 is useful. (References: L. Soicher & J. McKay, Computing Galois groups over the rationals, J. Number Theory, 20 (1985),273-81. R.P. Stauduhar, The determination of Galois groups, Math. Camp., 27 (1973), 981-96,) 1.3 Diagrams of transitille permutation groups of degree 4 ~ n ~ 7
0." .. 4
0." .. S
0." .. 1
e'I\~~'
0." .. 6
DIN c.
!lJ4 Hol(C,1
C, C,
DIl C,
degree 3 4
5
6
order 3 6 4 4 8 12 24 5 10 20 60 120 6 6 12 12 18 24
notation
indicator function
polynomial of discriminant
21 3 63 C4 !ll4
d(f) XIX~ + X2X~ +
D8
X I X3
21 4 64 Cs
d(f)
+
xs)(xs -
X 6 )(X 6 -
x 6 )(X S -
X6 -XI -
X6)
X6 -
X2)
t 6 _ 4t 2 -1 26229 2 t 6 _ 3t S + 6t4 - 7t 3 + 2t 2 + t - 4 229 3
x3xi
+
x 4xI
x3xi
+
X4X;
X 2X 4
XIX~ + X2X~ +
+
xsxi
DIO
Hol(C s) 21s 6s C6 63
(X I X 2
DI2
X I X4
21 4 G I8 64f'«(12).(34»
(XI -
+
X2X3
2l~ x C2 64f'C4
+
X3X4
+
X 4 X S + XSXI -
XIX3 -
X2XS -
XSX2 -
d(f) XIX~ + X I X4
(XI
+
+ ' X 2X6 + + X 2X S + X2X;
X 2 )(X2 x 2 -
X (x I -
24 24
+ (X4 -
X 4 -xs -
t 3 + t 2 - 2t-1 t 3 +2 t4 + t 3 + t 2 + t + I t4 + 1 t4 _ 2 t4 + 8t + 12 t4+t+ I t S + t4 _ 4t 3 - 3t 2 + 3t + I t S - 5t + 12 t S +2 t S +20t + 16 t S -t+ 1 t 6 + t S + t4 + t 3 + t 2 + t + 1 t 6 + 108 t6 + 2 t 6 -3t 2 -1 t 6 + 3t3 + 3 t 6 _ 3t 2 + I
(XI
+
X2 -
+ X4X~ +
X3X;
+ X6X~
X3X 6 X 3 )(X3 -
X3 - X4 )(X3 X 2 )(X3 X3 -
xsxI
X3 X S
XI)
+
x 4 )(xs -
X 4 )(X3
+
X4 -
x 4)
x 6) Xs -
x 6 )(X S
+
XI -
X 2X 4 -
x 4 xtl 2
72 _223 3 53 28 -211 2 12 34 229 114 2 12 56 24 5s 2 16 56 19-151 _7s
_2 16 3 21 _2113 6 2638 -3 11 _2 638
6
36 36 48 60
G~6 G~6 G. 8 PSU.2,5)
72 120
Gn PGU.2,5)
(x t x
360 720 7
~6
d(f)
14 21 42
Dt•
X2)(X 2 - X3)(X 3 t x 2 + X3X. + XSX6
(x t x
168 2520 5040
xs)(xs - x 6)(X6 - x.)
+ X.X SX6 2 + X3 XS + x.X 6)(X t X3 + x.xs + X2X6)(X 3X. + x (xtX S + x 2x. + X3X6)(X t X. + X2X 3 + XSx 6)
X t X 2X 3 x
7
xt)(x. -
tx 6
+ x 2XS)
66 C7 x tx
2 + X2X3 + x 3x. + x.xs
+ xSX6 + X6X7 + X7Xt
Hol(C7)("\~7 Hol(C 7)
PSL(3,2) ~7
67
+ X t X 2X 6 + x t x 3 x. + X t X 3 X 7 + x t XSx 6 + Xt XSX7 + X2X3XS + X2X3X7 + X2X.XS + X2X6X7 + X3X.X6 + X3XSX6 + X4 XSX7 + X.X 6X7 X t X 2X. + X t X 3X 7 + x t X Sx 6 + X2X3XS + X2X6X7 + X3X.X6 + X.XSX7 X t X 2X.
d(f)
t 6 +2t 3 -2 t 6 + 6t· + 2t 3 + 9t 2 + 6t - 4 t 6 +2t 2 +2 t 6 + lOtS + 55t· + 14Ot 3 + 175t 2 + 170t + 25 t 6 + 2t· + 2t 3 + t 2 + 2t + 2 t 6 + lOtS + 55t· + 14Ot 3 + 175t 2 - 3019t + 25 t 6 + 24t-20 t 6 + t+ 1 t 7 + t 6 - 12t S -7t· + 28t 3 +14t 2 -9t+ 1 t 7 + 7t 3 + 7t 2 + 7t - 1 t 7 -14t S + 56t 3 - 56t + 22 t7 + 2
2 8 39 2 t 03 6 5· _2 tt 5 272 2 36 58
t 7 -7t 3 + 14t 2 -7t + 1 t 7 +7t·+14t+3 t 7 + t+ 1
7 8 17 2 36 78 - 11·239· 331
-2 8 733 5 2°19 3 5 2 °19 3 151 3 2 t6 36 56 -101·431 17 229 6 _3 6 79 26 7 tO _2 6 7 7
432
Appendix: Numerical tables Fundamental units and class numbers
2.1 Fundamental units e > 1 and class numbers h of real quadratic number fields F= Q(m t ), m <300 Column I contains the discriminant d F of F which is III in case III == I mod4, 4m otherwise. Column 2 gives the coefficients a, b, cEN of the fundamental unit e = (a of F, c being listed only for c
+ bmt)/c > 1
> I.
Column 3 contains the class number h of F and column 4 the structure of the class group CI F , if h is greater than one and CI F not cyclic.
fundamental unit e + bmt)/c c listed only if c i' I
discriminant df · dF =m or d F =4m
a, b, c of e = (a
4·2 4·3 5 4·6 4·7 4·\0 4·11 13 4'14 4·15 17 4-19 21 4·22 4·23 4·26 29 4'30 4·31 33 4·34 4·35 37 4·38 4'39 41 4·42 4·43 4·46 4·47 4·51 53 4·55 57 4·58 4·59 61 4·62 65 4·66
I 2 I 5 8 3 10 3 15 4 4 170 5 197 24 5 5 II 1520 23 35 6 6 37 25 32 13 3482 24335 48 50 7 89 151 99 530 39 63 8 65
class number II I I I 2 3 I 3 I 4 I I 39 I 42 5 1 1 2 273 4 6 I I 6 4 5 2 531 3588 7 7 I 12 20 13 69 5 8 I 8
2
2
2
2
2
type of class group if not cyclic
I I I I I 2 I I 1 2 I I 1 I 1 2 I 2 I I 2 2 1 1 2 I 2 I 1 1 2 I
2
2
I 2 1 1 I 2 2
(Contd.)
Appendix: Numerical tables
discriminant d,. df - = III or df =4111 4-67 69 4-70 4-71 73 4-74 77 4-78 4-79 4-82 4-83 85 4-86 4-87 89 4-91 93 4-94 4-95 97 101 4-102 4-103 105 4-106 4-107 109 4-110 4-111 113 4-114 4-115 4-118 4-119 4-122 4-123 4-127 129 4-130 4-131 133 4-134 137 4-138 4-139 141 4-142 4-143 145 4-146 149 4-151 4-154 4-155 157
fundamental unit a, b, c of E = (a
E
+ bllll)/c
class number II
c listed only if c of. I 48842 25 251 3480 1068 43 9 53 80 9 82 9 10405 28 500 1574 29 2143295 39 5604
433
10
5967 3 30 413 125 5 1 6 9 1 9 1 1122 3 53 165 3 221064 4 569 1
101 227528 41 4005 962 261 21 295 776 1025 1126 306917 120 11 122 4730624 16855 57 10610 173 145925 1744 47 77 563 250 95 143 12 12 145 61 1728148040 21295 249 213
22419 4 389 93 25 2 28 73 96 105 28254 11 1 11 419775 1484 5 927 15 12606 149 4 6578829 8 12 1 1 12 5 140634693 1716 20 17
2
2
2
2
10
2
2
2
2
1 1 2 1 1 2 1 2 3 4 1 2 1 2 1 2 1 1 2 1 1 2 1 2 2 1 1 2 2 1 2 2 1 2 2 2 1 1 4 1 1 1 1 2 1 1 3 2 4 2 1 1 2 2 1
type of class group if not cyclic
C2
X
C2
(Contd.)
434
discriminant dF dF=m or
dF=4m 4·158 4·159 161 4·163 165 4·166 4·167 4·170 173 4·174 177 4·178 4·179 181 4·182 4·183 185 4·186 4·187 4·190 4'191 193 4'194 4·195 197 4'199 201 4·202 4·203 205 4·206 209 4·210 4·211 213 4·214 4·215 217 4·218 4·219 221 4·222 4·223 4·226 4·227 229 4·230 4·231 233 4·235 237 4·238 4·239 241 4·246
Appendix: Numerical tables
fundamental unit e a, b, c of e = (a + bmt)jc c listed only if c '# I 7743 1324 II 775 64080026 13 1700902565 168 13 13 1451 62423 1601 4190210 1305 27 487 68 7501 1682 52021 8994000 1764132 195 14 14 16266196520 515095 3141 57 43 59535 46551 29 278354373650 73 695359189925 44 3844063 251 74 15 149 224 15 226 15 91 76 23156 46 77 11663 6195120 71011068 88805
616 105 928 5019135 I 132015642 13 I I 110 4692 120 313191 97 2 36 5 550 123 3774 650783 126985 14 I I 1153080099 36332 221 4 3 4148 3220 2 19162705353 5 47533775646 3 260952 17 5 I 10 15 I 15 I 6 5 1517 3 5 756 400729 4574225 5662
class number h
2
2
2
2
2
2
2
2
I 2 I I 2 I I 4 I 2 I 2 I I 2 2 2 2 2 2 I I 2 4 I I I 2 2 2 I I 4 I I I 2 I 2 4 2 2 3 8 I 3 2 4 I 6 I 2 I I 2
type of class group if not cyclic
C2
X
C2
C2
X
C2
C2
X
C2
C2
X
C2
•
(Contd.)
435
Appendix: Numerical tables
discriminant dF dF=m or dF=4m 4·247 249 4·251 253 4·254 4·255 257 4·258 4·259 4·262 4·263 265 4·266 4·267 269 4·271 273 4·274 277 4·278 281 4·282 4·283 285 4·286 4·287 4·290 4·291 293 4·295 4·298 4·299
fundamental unit E a, b, c of e = (a + bmi)/c c listed only if c oF I 85292 8553815 3674890 1861 255 16 16 257 847225 104980517 139128 6072 685 2402 82 115974983600 727 1407 2613 2501 1063532 2351 138274082 17 561835 288 17 290 17 2024999 409557 415
5427 542076 231957 117 16 1 1 16 52644 6485718 8579 373 42 147 5 7044978537 44 85 157 150 63445 140 8219541 I 33222 17 1 17 I 117900 23725 24
class number h
2
2
2
2
2 I I I 3 4 3 2 2 1 I 2 2 2 1 1 2 4 1 1 1 2 1 2 2 2 4 4 1 2 2 2
type of class group if not cyclic
C2
X
C2
C2
X
C2
3.1-7.1. Tables of fundamental units and class numbers of algebraic number fields F of small absolute discriminant and degree n = s + 2t, 3 ~ n ~ 7 Column 1 contains the discriminant of F. Column 2 contains the coefficients a(l), ... , a(n) of a generating polynomial f(t) = t n + Li':J a(n - i)t!, i.e. F = O(p) for a zero pEe of f(t). Column 3 contains a pairwise reduced d::-basis WI'.'" Wn of OF = CI(d::, F). The Wi are given as O-linear combinations of I, p, ... , pn-I. Column 4 contains the coefficients of the r = s + t - 1 fundamental units of F with respect to their presentation by Wi' ... ' Wn> i.e. one row of entries e(l), ... , e(n) represents the fundamental unit e = e(l)w I + ... + e(n)wn' Column 5 contains the regulator of F rounded to two decimal places. The class numbers of all those fields are one except for the complex cubic field of discriminant - 283 which has hF = 2. Therefore the class number hF is not listed separately. For fourth degree fields the Galois groups are also listed in an additional column.
436
Appendix: Numerical tables
3.1 Table of fundamental units of totally real cubic fields with d F < /000 coelT. of gen. polyn. discriminant dF
two fund. units
a(i).i=I ..... 3
in!. basis
e(i).i= 1, ... ,3
49
1.-2.-1
81
0.-3.1
I,p. _2+p2 I.p, _ 2 + p + p2 I,p. - 2 + 2p + p2 I.p, _ 3 + p + p2 I,p. -3 + p2 I,p, _I + 3p + p2 I.p, -3 + p2 I,p, _ 3 + p + p2
0.53 0.1.0 1.1.0 0,1,0 0.85 -1.1.0 0,1.0 1.66 4.2.1 0,1.0 1.37 -1,1.0 2.36 0.1.0 2.1,0 1.97 0,1,0 -1,1,0 -2,1,1 3.91 -26,11,21 0.1,0 2.57 0,-1,1 0,1,0 1.95 1.1,0 0,1,0 3.76 2,-2,1 0,1,0 3.85 10,3,4 2.84 0.1,0 -2,1,0 -8,2.5 5.40 -3,1,0 1,0,2 6.09 1,1.-1 -1,1,0 5.40 9,2,-4 0,1,0 2.71 -1,1,0 0,1,0 5.31 8,-4,3 1,0,-1 5.69 17, - 3,-9 0,1,0 3.53 3,1,0 0,1,0 4.10 -1,1,1 2,-1,0 5.99 9,2,-4 0,1,0 6.80 21,14,6 35,-8,9 8.32 -7,2,2 14,4,3 8.91 10,2,- 5 11,6,4 12.18 5345.1244, - 3162 0,1,0 3.72 3,1,0 1,0,-1 5.55 -9,2,4
148
3,-1.-1
169
1,-4.1
229
0,-4.1
257
3.-2,-1
316
1,-4,-2
321
1,-4,-1
361
-2,- 5,-1
I,p, - 3 - 2p + p2
404
1,-5,1
I.p,
469
4,-2,-1
473
0,- 5,1
564
-2,-4,2
568
1,-6.2
621
3. - 3,-2
697
3,-4,-1
733
-2.-6,-1
756
0,-6,2
761
1,-6,1
785
-2,- 5,1
788
1,-7,3
837
0,-6,1
892
- 2, -7. - 2
940
3,-4,-2
961
-2,-9,2
985
1,-6.-1
993
1,-6,-3
_ 3 + p + p2 I.p, - I +4p+p2 I,p. -3 + p2 I,p, - 3 - 2p + p2 I,p, -4 + 2p + p2 I,p, - 2 + 3p + p2 I,p, - 3 + 3p + p2 I.p, -4 - 2p + p2 I,p. -4+ p2 I,p, -4 + p + p2 I,p. - 3 - 2p + p2 I,p, -4 + 2p + p2 I,p, -4 +p2 I,p, -4 - 3p + p2 I,p, - 3 + 3p + p2 I,p, t(- 6 - p + p2) I,p, -4 +p+p2 I,p, -4 +p2
RF
437
Appendix: Numerical tables
3.2 Table of fundamental units of complex cubic fields with Id,,1 < 300
discriminant d•.
coefT. of gen. pol yn. a(i).i= 1•...• 3
-23
0.-1.1
- 31
0.1.1
-44
1.-1.1
-59
0.2.1
-76
3.1.1
-83
1.1.2
-87
-2.-1.-1
-104
3.2.2
-107
1.3.2
-108
0.0.2
-116
1.0.2
-135
3.0.1
-139
4.6.1
-140
0.2.2
-152
4.3.2
-172
-2.0.-2
-175
1.2.3
-199
4.1.1
-200
1.2.-2
-204
1.1.3
-211
3.1.2
-212
1.4.2
-216
0.3.2
-231
1.0.-3
-239
3.2.3
-243
3.3,4
-244
-5,4. -2
I fund. unit
in!. basis
e(i).i= 1•...• 3
R •.
I.p. -I + p2 I.p. p2 I.p. -I +p +p2 I.p. 1 +p2 I.p. -I + 2p + p2 I.p. p+p2 I.p. -1- 2p + p2 I.p. 2p+ p2 I.p. I +p2 I.p. p2 I.p. p+ p2 I.p. - 2 + 2p + p2 I.p. 1+ 2p + p2 I.p. I +p2 I.p. - 2 + 2p + p2 I.p. -2p + p2 I.p. p2 I.p. -I + 3p + p2 I.p. p2 I.p. p2 I.p. _I + 2p + p2 I.p. 2 + p + p2 I.p. p2 I.p. p2 I.p. 2p+p2 I.p. 2p+ p2 I.p. 1-4p + p2
0.1.0
0.28
0.1.0
0.38
0.1.0
0.61
0.1.0
0.79
0.1.0
1.02
1.1.0
1.04
0.1.0
0.93
1.-1.1
1.58
1.1.0
1.26
1.-1.1
1.35
1.-2.1
1.72
0.1.0
1.13
0.1.0
1.66
1.1.0
1.47
1.1.1
2.13
1.0.-1
1.88
1.1.0
1.29
0.1.0
1.34
-1.1.1
2.60
-1.1.1
2.35
3.1.0
2.24
7. - 2,4
2.71
1.1.-1
3.02
2.2.1
1.75
1.1.1
2.10
1.0.-1
2.52
5.-2.2
3.30
(Contd.)
438
Appendix: Numerical tables
3.2 (Contd.), coefT. of gen. polyn.
I fund. unit
discriminant dp
a(i).i=I •...• 3
in!. basis
e(i).i=I •...• 3
R f·
- 247
0.1.3
1.1.0
1.54
-255
1.0.3
2.1.0
1.99
-268
-2.-2.-2
3.-1.0
2.52
-283
0,4.1
0.1.0
1.40
- 300
4.2.2
I.p. p2 I.p. p +p2 I.p. - 2 -2p +p2 I.p. 2+p2 I.p. -1 + 3p + p2
6.2.1
3.15
4.1 Table of fundamental units of totally real quartic fields with dF < 5000 coefT. of gen. polyn. i= 1•...• 4
in!. basis
three fund. units eli). i= 1•...• 4
725
1.-3.-1.1
1125
I. -4. -4.1
1600
-4.0.8. -I
1957
O. -4.1.1
2000
-4.1.6.1
2048
-4.2,4 - I
2225
5,4. - 5.-1
2304
O. -4.0.1
2525
6.8. - 3.-1
2624
2. - 3. - 2.1
2777
2. - 3. - 5.1
I.p. _I +p+p2. _ I - 2p + p2 + p3 I.p. -2 +p2 _I - 3p + p3 I.p. i( - I - 2p + p2). to - p - 3p2 + p3) I.p. _ 2 + p2. 1- 3p + p3 I.p. _I - 2p + p2. 2 _ 3p2 + p3 I.p. -1-2p+p2. 2- 3p2 + p3 I.p. - 2 + 2p + p2. i( - I + 2p + 4p2 + p3) I.p. _ 2 + p2. _ 3p + p3 I.p. 3p + p2. _ I + 2p + 4p2 + p3 I.p. _I + 2p + p2. _ I - 2p + 2p2 + p3 I.p. _ 2 + p + p2. _ I - 3p + p2 + pJ
0.1.0.0 -1.1.0.0 1.1.0.0 0.1.0.0 1.1.0.0 -1.0.1.0 0.1.0.0 0.1.0. -I 1.0. -1.0 0.1.0.0 1.-1.0.0 0.0.1. -I 0.1.0.0 1.1.0.0 1.0. -1.0 0.1.0.0 0.1.0.-1 1.0. -1.0 0.1.0.0 4.2.1.1 9.4.2.2 0.1.0.0 0.0.1.1 1.1.-1.-1 0.1.0.0 1.1. -1.0 1.0. -1.0 0.1.0.0 I. -1.0.0 1.1.0.0 0.1.0.0 2.-1.-1.2 1.0.0. -I
discriminant df ·
ali).
Rf·
Galois group
0.83
DB
1.17
C4
1.54
!!.l4
1.92
64
1.85
C4
2.44
C4
2.06
DB
2.66
!!.l4
2.09
Ds
2.19
DB
3.04
64
(Conti.)
439
Appendix: Numerical tables
4.1 (Contd.) coefT. of gen. polyn. discriminant df"
ali),
3600
-4, - 3,14,1
3981
4205 4225 4352 4400 4525 4752 4913
i= 1, ... ,4
into basis
I,p, t( - 2 - 2p + p2), t(5 - 3p - 3p2 + p3) I,p, I, -4, -2,1 _2+p+p2, _ I _ 3p + p2 + p3 I,p, I, - 5,1,1 - 2 + 2p + p2, 1_ 5p + p2 + p3 - 4, - 3,14, - 4 I,p, 1( - 4 - p + p2), *(4 - 4p - 3p2 + p3) 0, -8,8,1 I,p, _ 4 + p + p2, - 2 - 5p + 2p2 + p3 -8,17, -4,-1 I,p, I -4p + p2, - 2 + 9p - 6p2 + p3 5,2, -10,1 I,p, - 3 + 2p + p2, !( _ 5 + P + 4p2 + p3) 2,-3,-4,1 I,p, _ 2+p + p2, _ I - 3p + p2 + p3 I, -6,-1,1 I,p, _ 3 + P + p2, W-6p+p3)
three fund. units eli), i= 1, ... ,4 0,1,0,0 1,0, -1,0 2,0,0,1 0,1,0,0 1,1,0,0 1,1, -1,0 0,1,0,0 1,-1,0,0 1,-1,1,0 1,1,-1,-1 2, -1,0,3 3, -1,0,3 0,1,0,0 1,0,0,-1 1,0, -1,0 0,1,0,0 1,-1,1,0 1,0,-1,0 0,1,0,0 1,-1,0,0 0,0,0,1 0,1,0,0 1,1,0,0 0, -1,1,0 0,1,0,0 0,0,1,1 5,3,3,2
Rf"
Galois group
2.62
'U 4
3.19
64
2.82
Ds
3.19
'U 4
4.18
Ds
3.29
Ds
3.06
Ds
3.71
Ds
3.46
C4
4.2 Table of fundamental units of quartic fields with two complex conjugates and IdFI < 300 discriminant d•.
coelT. of gen. polyn. a(i), i= 1, ... ,4
- 275
1,0,-2,-1
-283
0,-2,1,1
-331
0,- 2,3,- I
-400
0,-1,0,-1
-448
2,1,2,1
-475
1,-2,2,-1
int. basis I,p, p2, p3 I,p, p2, p3 I,p, p2, p3 I,p, p2, p3 I,p, p2, p3 I,p, p2, p3
two fund. units e(i), i= 1, ... ,4
RF
Galois group
0,1,0,0 1,1,0,0
0.37
Ds
1,1,0,0 1,-1,0,0
0.38
64
0,1,0,0 1,-1,0,0
0.43
64
0,1,0,0 I, -1,0,0
0.51
Ds
0,1,0,0 1,1,0,0
0.56
Ds
0,1,0,0 1,-1,0,0
0.58
Ds (Contd.)
440
Appendix: Numerical tables
4.2 (Contd.) discriminant df ·
-491
two fund. units e(i),
coelT. of gen. polyn. a(i), i= 1, ... ,4
1,-1,-3,-1
- 507
1,-1,1,1
- 563
1,-1,1,-1
-643
1,0,2,1
-688
0,0,2,-1
-731
0,-2,1,-1
-751
1,-1,2,-1
-775
1,0,3,-1
-848
0,-1,2,1
-976
0,- 3,2,-1
-1024
0, -2,0,-1
-1099
0,-4,3,-1
in!. basis
i= 1, ... ,4
R f•
Galois group
I,p,
0,1,0,0 1,1,0,0
0.63
64
0,1,0,0 1,1,0,0
0.65
Os
0,1,0,0 1,-1,0,0
0.70
64
0,1,0,0 1,1,0,0
0.72
64
0,1,0,0 1,0,1,1
1.00
64
0,1,0,0 1,-1,0,0
0.87
64
0,1,0,0 2,1,0,0
1.07
64
0,1,0,0 1,1,0,1
0.87
Ds
0,1,0,0 1,1,0,0
0.99
64
0,1,0,0 1,-1,0,0
0.99
64
0,1,0,0 1,1,1,1
1.35
Ds
0,1,0,0 1,-1,0,0
1.01
64
0,1,0,0 1,1,-1,0
1.29
64
I,p, _ I
0,1,0,0 1,1,1,1
1.53
Ds
_ I,p, p2,
0,1,0,0 3,2,1,1
1.57
64
0,1,0,0 1,-1,1,2
1.58
64
p2, p' I,p, p2, p' I,p, p2, p' I,p, p2, p' I,p, p+ p2, 1+ p' I,p, p2, p' I,p, p2, p' I,p, p +p2, W + 2p2 + p') I,p, p2, p' I,p, p2, p' I,p, _I + p2, _ 2p + p3 I,p,
p2, p3 -1107
2,0,1,-1
I,p,
2p+ p2 1+ 2p2 + p3 -1156
1,-2,1,1
-1192
1,2,-1,-1
-1255
0,-1,3,-1
+ P + p2, 2p + p2 + p3
_ I I,p,
+ 2p + p2 + p'
+ p+ p2, 1_ P + p' _I
441
Appendix: Numerical tables
4.3 Table offundamental units of totally complex quartic fields with dF < 600 discriminant df"
coefT. of gen. polyn. a(i), i= 1, ... ,4
117
0,2,3,1
125
1,1,1,1'"'
one fund. unit e(i), i= 1, ... ,4
RF
Galois group
I,p, 1+ p2, 2 + 2p + pJ
0,1,-1,1
0.54
Ds
I,p,
1,1,0,0
0.96
C.
1,-1,0,0
1.32
C.
0,1,0,0
0.86
Ds
0,1,0,0
0.96
'8.
0,1,0,0
0.34
6.
0,1,0,1
1.76
'8.
0,1,0,0
0.44
6.
0,1,0,0
0.73
Ds
0,1,0,0
1.06
Ds
1.46
Ds
0.63
Ds
0.96
'8.
0,1,0,0
1.66
Ds
0,1,0,0
1.57
'8.
0,1,-1,0
1.53
C.
1,0,-1,0
1.96
Ds
0,1,0,0
2.11
Ds
int. basis
p2,
pJ 144
0,-1,0,1
189
2,0,-1,1
225
1,2,-1,1
229
0,0,1,1
256
0,2,4,2
257
0,1,1,1
272
0,1,2,1
320
2,0,-2,1
333
5,7,3,3
392
2,6,-2,1
400
0,3,0,1
432
-4,3,2,1
441
0,5,0,1
512
0,2,0,2
513
4,9,16,13
549
6,10,3,1
I,p, p2,
pJ I,p, p2,
pJ I,p, 1+ p + p2, + 2p + 2p2 + pJ) I,p, p2,
W pJ
I,p, p2,
W +p2 +pJ) I,p, p2,
pJ I,p p2,
pJ I,p, p2,
pJ I,p, 1,0,-1,0 2p + p2, I + 2p + 3p2 + pJ I,p, 0,0,1,1 1(3+2p+p2), ~(_ 3 + 5p + p2 + pJ) I,p 0,1,0,0 p2,
pJ I,p, _ 2p + p2, 2p _ 3p2 + pJ I,p, 1(3+p+p2), HI +4p+pJ) I,p, 1 + p2, p+ pJ I,p, HI +p+p2), 1(5 + 4p + 2p2 + pJ) I,p, _ I + 2p + p2, 3p + 4p2 + pJ
(Contd.)
442
Appendix: Numerical tables
4.3 (Contd.) one fund. unit e(i),
coefT. of gen. polyn. a(i),
discriminantd..
i=I,,,.,4
576
0, - 2,0,4
int. basis
i= 1,,,.,4
Rf ·
Galois group
I,p,
1,1,1,0
2.29
~4
0,1,1,1
7.76
~14
0,1,0,0,
0.92
64
tp2,
!pl 576
0,2,0,4
592
0,2,2,1
I,p, !p2,
!pl I,p, p2,
pl
5.1 Table of fundamental units of totally real quintic fields with dF < 102000 coefT. of gen. polyn.
four fund. units e(i), i = I,. ",5
discriminant dF
a(i),i= 1,,,.,5
int. basis
14641
I, - 4, - 3,3,1
24217
0, - 5, - 1,3,1
36497
I, - 5, - 3,2,1
38569
I, - 5, - 1,4, - 1
65657
I, - 5, - 2,5, - I
70601
I, - 5, - 2,3,1
81509
2, - 4, - 6,4,1
81589
2, - 4, - 8,0,1
89417
2, - 4, - 7,2,1
0,1,0,0,0 _ 2 + p2, 1,-1,0,0,0 _ 3p + pl, 1,1,0,0,0 I - 2p _ 3p2 + pl + p4 1,0,-1,0,0 0,1,0,0,0 I,p, _ 2 + p2, 1,-1,0,0,0 1,1,0,0,0 -1-4p +pl, 2 _ 5p2 + p4 1,-1,1,0,0 0,1,0,0,0 I,p, _ 2 + p2, 1,1,0,0,0 _ 2 - 4p + p2 + pl, 1,2,1, - 4, - 2 3,4,2, - 5, - 3 I + 2p - 5p2 + p4 0,1,0,0,0 I,p, 1,-1,0,0,0 _2+p+p2, _ 3p + p2 + pl, 1,1,0,0,0 3 - 2p - 5p2 + pl + p4 1,0,1,0,0 0,1,0,0,0 I,p, 1,-1,0,0,0 -2 + p+ p2, _ I - 3p + p2 + pl, 1,1,-1,0,0 2 - 2p _ 4p2 + pl + p4 1,0,1,0,0 0,1,0,0,0 I,p, _2+p+p2, 1,-1,0,0,0 _ I - 4p + p2 + pl, 1,1,0,0,0 2 - 2p - 5p2 + pl + p4 0,-1,1,0,1 0,1,0,0,0 I,p, 6,3,0, - 2, - 3 -2 +p +p2, _I - 3p + p2 + pl, 2,1,-1,-1,-1 I - 5p - 3p2 + 2pl + p4 1,0, - 1,0,0 0,1,0,0,0 I,p, 1,2, - 2,0,3 -2 + p2, -4p + pl, 3,1,-2,1,3 _ 4p _ 4p2 + pl + p4 2,0,-1,0,1 0,1,0,0,0 I,p, _ 2 + p + p2, 1,1,-1,0,0 2,1,0,0,0 I -4p + pl, I - 3p _ 4p2 + pl + p4 1,0,1,0,0 I,p,
Rf ·
1.64
2.40
3.55
3.16
5.50
4.61
7.63
7.61
6.74
(Contd.)
443
Appendix: Numerical tables
5.1 (Contd.)
discriminant df" -~.-
...- .
codT. of gen. polyn. a(i). i = 1....• 5
----~-.----~.-~
101833
....
four fund. units in!. basis
-----
2. - 5. - 5.1.1
e(i). i = 1•...• 5
RF
0.1.0.0.0 1.1.0.0.0 130. - 228.110. -27.13 1.1.0. -1.0
6.33
--------
I.p. _ 2 + P + p2. - 3 - 4p + 2p2 + pl.
5.2 Table of fundamental units of quintic fields with two complex conjugates and
IdFI < 10000 coefT. of gen. polyn. discriminant d F
a(i). i=
-4511
O. - 2.- 1.0.1
-4903
1.- 3.- 1.2.-1
-5519
0.-3.-1.1.1
- 5783
0.- 2.3,4.1
-7031
0.-1.-1.-1.1
-7367
0.- 4.- 1.2.1
-7463
O. - 4. - 1.4.1
-8519
1.0.1.-1.-1
-8647
O. - 3. - 2.2.1
-9439
O. - 3. - 2,4.1
1..... 5
three fund. units in!. basis
e(i). i = 1..... 5
RF
I.p. _I +p2. _ 2p + pl. _ P _ 2p2 + p4 I.p. -I +p+ p2. 1- 2p + p3, 2 - p - 3p2 + pl + p4 I.p. -I + p2. -2p + p3. 1- p - 3p2 + p4 I.p. -I + p2. I-p +pl. 3 + 3p - 2p2 + p4 I.p. _I + p2. _ P + p3. _1_p_ p 2 + p4 I.p. _ 2 + p2. _ 3p + p3. 2 _ P _4p2 + p4 I.p. - 2 + pl. -1-2p +pl. 2 - P - 3p2 + p4 I.p. -I + p2. p2 + pl. -I + p + pl + p4 I.p _1_p+p2. -1-2p+p3. 1- P _ 3p2 + p4 I.p. -I +p2. _1_p+p3. 2- p-2p2 + p4
0.1.0.0.0 1.-1.0.0.0 1.1.0.0.0
0.63
0.1.0.0.0 0.0.1.0.0 1.1.0.0.0
0.67
0.1.0.0.0 1.-1.0.0.0 1.1.0.0.0
0.73
0.1.0.0.0 1.1.0.0.0 0.1.1.-1.2
0.76
0.1.0.0.0 1.-1.0.0.0 1.1.0.0.0
0.89
0.1.0.0.0 1.-1.0.0.0 1.1.0.0.0
0.90
0.1.0.0.0 1.-1.1.0.0 1.1.0.0.0
0.93
0.1.0.0.0 1.-1.0.0.0 1.1.0.0.0
1.00
0.1.0.0.0 1.-1.0.0.0 1.1.0.0.0
1.03
0.1.0.0.0 1.-1.0.0.0 1.0.-1.0.0
1.21
444
Appendix: Numerical tables
5.2 (Contd.)
discriminant d F
coefT. of gen. polyn. a(;),;= 1, ... ,5
in!. basis
e(i), i= 1, ... ,5
three fund. units
-9759
1,-3,-2,1,-1
I,p,
0,1,0,0,0 1,1,0,0,0 1,0,2,1,1
_ 2 + p2,
- 2p
+ p3,
I - 2p - 3p2
+ pl + p'
1.24
5.3 Table of fundamental units of quintic fields with four complex conjugates and dF < 4000 discriminant dF
coefT. of gen. polyn. ali), i= 1, ... ,5
1609
0, - 3,0,2,1
1649
0, - 3, - 1,3,1
1777
0, - 2, - 1,2,1
2209
0, - 1,2, - 2,1
2297
0,1,1,1,1
2617
0, - 2,3, - 2,1
2665
0,1,0,-2,1
2869
0,-2,0,1,1
3017
0,-1,0,0,1
3089
0,-1,0,2,1
in!. basis
two fund. units e(i),;= I , ... ,5
0,0,0,1,0 I,p, _I +p2, 0,0,1,1,0 _ 2p + pl, P _ 2p2 + p' 1,1,0,0,0 I,p, _I +p2, 1,-1,0,0,0 - I - p +pl, 1- 2p2 + p' 1,0,-1,0,1 I,p, _I +p2, 1,1,0,0,0 - I - p +pl, 1- P _ p2 + p' 0,1,0,0,0 I,p, _I + p+ p2, 1,-1,0,0,0 l_p+p2 +p\ _ 2 + 2p _ p2 + p' 0,1,0,0,0 I,p, p2, 1,1,0,0,0 1+ p + pl, p+p' 0,1,0,0,0 I,p, _I +p+p2, 1,0,-1,0,0 I - 2p + p2 + pl, _ I + 2p - 3p2 + p' 0,1,0,0,0 I,p, p2, 1,-1,0,0,0 1+ p + p2 + pl, _ I + P + 2p2 + pl + p' I,p, 1,1,0,0,0 _I +p2, 1,-1,0,0,0 _ p + pl, 1_ 2p2 + p' 0,1,0,0,0 I,p, _I +p2, 1,-1,0,0,0 _p+pl, _ p2 + p' 0,1,0,0,0 I,p, p2, 1,1,0,0,0 _p2 + pl, _ p2 + p'
R f·
0.27
0.27
0.29
0.35
0.36
0.39
0.40
0.43
0.44
0.49
6.1 Table offundamental units of totally real sexticfields with dF < 1229000 discriminant dF
coetT. of gen. polyn. a(i), i = 1 , ... ,6
in!. basis
five fund. units e(i), i = 1, ... ,6
300 125
1,-7,-2,7,2,-1
371293
1, - 5, -4,6,3,-1
l,p, -2+p+ p2, _ 1 - 5p + p2 + p3, 2 - p - 6p2 + p3 + p4, _ 4 + 3p + 6p2 _ 7p3 + pS l,p, _2+p2, _ 3p + p3, 2-4p2 +p\ 1 + 3p - 3p2 _ 4p3 + p4 + pS l,p, _ 3 + p2, 3 - 5p _ p2 + p3, 3 - 2p - 6p2 + p4, _ 3 + 7p - p2 _ 7 p3 + pS l,p, _ 2 + p2, _ 3p + p3, 2 + 3p _ 4p2 _ p3 + p4, 2 + 5p _ p2 _ 5p 3 + pS l,p, _2+p2, _2_3p+p2+p3, 2 + p - 4p2 + p4, 3 + 5p - 4p2 _ 5p3 + p4 + pS l,p, _3_p+p2, 2 - 2p - 2p2 + p3, 2+ 7p-2p2 _3 p3 +p4, 6p + 8p2 _ 3p3 _ 3p4 + pS
0,1,0,0,0,0 1, - 1,0,0,0,0 1,1,0,0,0,0 0,1,1,1,0,0 1,0, - 1, - 1,0,0 0,1,0,0,0,0 1, - 1,0,0,0,0 1,1,0,0,0,0 1, - 1,1,0,0,0 1,0,-1,0,0,0 0,1,0,0,0,0 1, - 1,0,0,0,0 1,0,0,1,0,0 2,1,0,0,0,0 1,1,0, - 1,0,0 0,1,0,0,0,0 1,1,0,0,0,0 0,0,1,0,0,0 1, - 1,1,0,0,0 1,0, - 1,0,0,0 0,1,0,0,0,0 - 1,1,0,0,0,0 1,1,0,0,0,0 1, - 1,1,0,0,0 0,1,1,0,0,0 0,1,0,0,0,0 1,1,0,0,0,0 1,0, - 1,1,0,0 1,0, - 1,0,0,0 1,0,1,0,0,0
434581
453789
0, - 8,0,12, - 7,1
1,- 6,- 6,- 8,8,1
485125
2, - 4, - 8,2,5,1
592661
- 5,2,18, - 11, - 19,1
RF
3.28
3.78 ~
4.19
"""""::>
Q. ~.
Z c: 3
(l
4.40
1)'
eo. ;:;
0-
~
4.53
5.23
(Contd.)
.j:>. .j:>.
V>
""" 0"""
6.1 (Contd.) discriminant dF
coeff. of gen. polyn. a(i), i = 1 , ... ,6
int. basis
five fund. units e(i), i = 1, ... ,6
703493
1, - 7, - 2,14, - 5, - 1
722000
1,- 6,-7,4,5,1
l,p, _2+p+p2, -3p + p2 + p3, 2 - 4p - 3p2 + 2p3 + p4, _ J + 5p - 5p2 _ 4p3 + 2p4 + p5 l,p, _ 2 + p2, -1-4p + p3, 2 - p - 5p2 + p4, 3 + 6p - 2p2 _ 6p3 + p5 J,p, _2+p+p2, _ 1 _ 3p + p2 + p3, _ 3p - 2p2 + 2p3 + p4, 2 +4p - 6p2 _4p3 + 2p4 + p5 l,p, _3+p+p2, _ J - 6p + p2 + p3, 3 + 4p - 8p2 + p4, #11- 36p - 39p2 + 2p3 + 7p4 + p5) l,p, _2+p2, 1_4p_p2+p3, 3 + p - 5p2 - p3 + p4, _ 2 + 7 p + 3p2 _ 6 p 3 _ p4 + p5 l,p, -2+p +p2, - 2 - 2p + 2p2 + p3 _ 5p _ p2 + 3p3 + p4, _ 1 + 5p - 3p2 _ 4p3 + 2p4 + p5
0,1,0,0,0,0 1, - 1,0,0,0,0 0,1, - 1,0,0,0 1,0, - 1,0,0,0 0,0,1,0,0,0 0,1,0,0,0,0 1, - 1,0,0,0,0 1,1,0,0,0,0 1,1,0, - 1,0,0 0,1,1,0,0,0 0,1,0,0,0,0 1, - 1,0,0,0,0 1,1,0,0,0,0 0,1,0, - 1,0,0 0,0,1,0,0,0 0,1,0,0,0,0 1, - 1,0,0,0,0 23, - 23,7,28,17, - 50 -16,13, - 5, - 9, - 6,19 1,1,0,0,0, -1 0,1,0,0,0,0 1, - 1,0,0,0,0 1,1,0,0,0,0 1,1, - 1,0,0,0 1,1,1,0,0,0 0,1,0,0,0,0 1, - 1,0,0,0,0 1,1,0,0,0,0 0,1, - 1,0,0,0 1,0, - 1,0,0,0
810448
820125
3,- 2, - 9,0,5,1
0, -9,4,9,- 3,-1
905177
1, -7, -9,7,9,-1
966125
3,- 3,-10,3,8,-1
RF
5.71
6.41
»-
'0 '0
6.89
'"c.. = ~.
Z c: 3 ~
6.28
n' ~
;; a"
if 6.91
7.43
980125
0, - 9,9,4, - 3, - 1
1075648
6,8, - 8, - 13,6,1
1081856
1134389
1202933
0,-6,2,7,-2,-1
I, - 6, - 7,5,6,1
I, - 6, - 2,6,0,-1
l,p, -3 +p+p2, - 2 - 5p + 2p2 + p3, 1 + 3p _7p2 + p3 + p4, - 1 - 3p + 10p2 _ 8p3 + p5 l,p, -1 +2p+p2, -2+ 3p2 + p3, - 1 - 4p + 2p2 + 4p3 + p4, 1 - 5p - 5p2 + 5p3 + 5p4 + p5 l,p, _2+p2, _ 1 _ 3p + p2 + p3, 2 - 2p _ 4p2 + p3 + p4, 5p _ 2p2 _ 5p 3 + p4 + p5 l,p, _2+p2, _1_4p+p2+ p3, 4 + 3p - 5p2 - p3 + p4, 3 + 7 p - 2p2 _ 6p3 + p5 l,p, _2+p+p2, _1_4p+p2+p3, 2 - p - 5p2 + p3 + p4, 6p _ 2p2 _ 6p 3 + p" + p5
0,1,0,0,0,0 I, - 1,0,0,0,0 4,3,1,1,2,1 0,0,0,1,0,0 8,17,10, - 36,22,30 0,1,0,0,0,0 I, -1,0,0,0,0 1,1,-1,0,0,0 0,1,-1,0,0,0 1,0, - 1,0,0,0 0,1,0,0,0,0 I, - 1,0,0,0,0 1,1,0,0,0,0 I, - 1,1,0,0,0 1,0, - 1,0,0,0 0,1,0,0,0,0 I, - 1,0,0,0,0 1,1,0,0,0,0 1,1,1,0,0,0 I, - 1,1,0,0,0 0,1,0,0,0,0 I, - 1,0,0,0,0 1,1,0,0,0,0 1,0,1,0,0,0 0,1,1,0,0,0
7.12
7.70
>-
"0 "0
'"c..
::I
7.76
..;;.
Z c: 3 ~
('i.
2:-
7.82
0;; (J
if 8.74
t .....
448
Appendix: Numerical tables
6.1 Fundamental units of the sextic field with two complex conjugates and minimum discriminant coefT. or gen. polyn. a(i). i= 1•...• 6
-92779
1.-2.-3.-1.2.1
rour rund. units in!. basis
e(i). i= 1•...• 6
I.p. _I +p2. _ 2p + pl. _ 2p2 + p4. 2 + P _ p2 _ 3pl + p'
0.1.0.0.0.0 I. - 1.0.0,0,0 1.1.0.0.0,0 0,1, - 1,0.0,0
1.26
6.3 Fundamental units of the sextic field with four complex conjugates and minimum discriminant coefT. or gen. polyn.
28037
three rund. units
a(i), i= 1, ... ,6
int. basis
e(i), i= 1, ...• 6
Rf
2,0, - 3,0,2. - I
I.p. p+ p2. _ I + P + 2p2 + pl. _ P + p2 + 2pl + p4. I - 2p - 2p2 + 2pl + 3p4 + p'
1.0. -1.0.0.0 I. - 1,0,0,0,0 1.1.0.0,0.0
0.48
6.4 Fundamental units of totally complex sexticfields with Idfl < 13100 two rund. units
coefT. or gen. polyn.
Rf
discriminant df
a(i). i= 1, ... ,6
int. basis
e(i). i= 1•... ,6
-9747
0.1,1,-2.-1,1
0,0.0.0,0.1 1,1.-1.1.2.3
0.60
-10051
1.2.2,2,2.1
0,1.0.0,0.0 1.1,0.0,0,0
0.21
-10571
2.2.1.2,2.1
0.0,- 1.0.1,0 0.0,-1.0,1,1
0.21
-10816
2.0. - 2. - 1,0.1 1,-1,0,0,-1,1
0, I,0,0,0.0 1,1,0,0,0,0 0,1,0,0,0,0 I, - 1,0,0,0,0
0.43
-11691
I,p. p2. P + pl. _ I + p + 2p2 + p4. _ I _ 2p + p2 + pl +p' I.p, p2. p + p" p2 + p4. pl + p5 I.p, p2, p2 + pl, I + p2 + pl + p4, 1+ 2f + p4 + p' I,p.p. pl.p4,p' I,p, p+p2, p2 + pl, pl + p4, _ I + p2 + p4 + p'
0.69
(Contd.)
449
Appendix: Numerical tables
6.4 (Contd.) cocO'. of gcn. polyn. discriminant tiF
a(i). i= 1•...• 6
-12167
3.5.5.5.3.1
-14283
1.1.2.1.0.1
-14731
1.0.-1.-1.0.1
-16551
2.2.3.3.1.1
-16807
1.1.1.1.1.1
-18515
0.2.1.2.0.1
-19683
0.0.1.0.0.1
- 20627
1.1.2.2.1.1
-21168
I. - 2. -1,4. - 3.1
int. basis
I.p. 1+ P + p2. p+p2+p3. I + P + 2p2 + 2p3 +p4. 2p + 2p2 + 3p3 +2p4+p5 I.p. p2. 1+ p3, p+p\ p + p2 + p3 + p4 + p5 I.p. p2. p3. p3 + p4. _I _ P + p3 + p4 +p5 I.p. p+p2. 1+ p2 + p3. 2 + 2p + 2p2 + 2p3 +p4. _I + p + p2 + p4 +p5 I.p. p2. p3. p4. p5 I.p. 1+ p2. P +p3. 1+ p + p2 + p4. P + p2 + 2p3 + p5 I.p. p2. p3. p4. p5 I.p. p2. 1+ p3. p+p4. P + p2 + p4 + p5 I.p. -I +p +p2. -I + 2p2 + p3. 2 - 2p + 2p3 + p4. - 2 + 4p _ p2 _ 2p 3 + p4 + p5
two fund. units e(i). i= 1•...• 6
RF
0.1.0.-1.0.1 0.0.0.0.0.1
0.24
0.1.0.0.0.0 1.1.0.0.0.0
0.80
0.1.0.0.0.0 1.1.0.0.0.0
0.28
0.1.0.0.0.0 1.1.0.0.0.0
0.93
1.1.0.0.0.0 1.-1.1.0.0.0.
2.10
0.1.0.0.0.0 0.0.1.0.0.0
0.33
1.1.0.0.0.0 1.0.1.0.0.0
3.40
0.1.0.0.0.0 1.0.1.0.0.0
0.39
0.1.0.0.0.0 I. - 1.0.0.0.0
1.12
(Contd.)
450
Appendix: Numerical tables
6.4 (Contd.)
discriminant d,
coelT. of gen. polyn. a(i), i = 1, ... ,6
-21296
1,2,3,2,1,1
two fund. units in!. basis
e(i), i = 1, ... ,6
R,
I,p,
-1,-1,0,1,1,1 0,1,0,0,0,0
0.31
0,1,0,0,0,0 1,1,0,0,0,0
0.31
0,1,0,0,0,0 1,1,0,0,0,0
0.15
I,p, I +p2,
0,1,0,0,0,0 0,0,1,0,0,0
1.26
If'
I, - 1,1,0,0,0 1,1,0,0,0,0
0.39
0,1,0,0,0,0 1,0,1,0,0,0
1.19
p2, l+p+p3, p + p2 + p4, p2 + p3 + p5, - 22291
1,0,1,1,0,1
I,p,
p2, I +p3, 1+ p + p3 + p4, p+ p2 + p4 + p5 -22592
0, -1,0,2,2,1
I,p,
p2, _p2+p3, 1+ p- p3 + p4, 2+ 2p _ p3 + p5 -22101
1,4,4,5,3,1
2p + p3, 2 + p + 3p2 + p4, 1+ 2p + p2 + 3p3 + p5 -22141
1,0,2,1,-1,1
p, 1+ p2 + p3, -I +p+p4, - I +p+p2+ p4 +p5 -23031
0,1,1,1,2,1
I,p,
e
2,
p3, p+p4, 1+ p2 + p5
7.1 Fundamental units ofthe totally real seventh degreefield with minimum discriminant coelT. of gen. polyn. a(i),i= 1, ... ,1
20134393
in!. basis
I, - 6, - 5,8,5, - 2,-1
six fund. units e(i), i= 1, ... ,1 - 2, - 4,4,5, - I, - 1,0 - 2,1,8,- 4,- 6,1,1 -3,2,15,-4,-12,1,2 0, I,0,0,0,0,0 - 2,0,1,0,0,0,0 2,2, - 8, - 1,6,0, - I
R, 14.45
8 Integral bases We present two examples for the computation of the maximal order of an equation order by the embedding algorithm of chapter 4, section 6. 1. For Itt) = til + 10It i0 + 4151t 9 + 81851t B + 916826t 7 + 4621826t 6 - 5948614t 5 - 1131 11614t4 - I 2236299t 3 + 1119536201t 2 -1660153125t - 332150625
451
Appendix: Integral bases we obtain the reduced discriminant
d,(f) = 81025653391191575101440000 = 212 x 3 12 X 54 X 29 4 x 82231 and the discriminant
d(f) = 2 130
X
3 12
X
5 12
X
29 18
X
82231 6
The algorithm produces: p=2
idempolellls
-1421478951492431/256~IO +86970691 5501 33/32C +959425090967179f128~8 -140484061 157699/32C - 654028913747701/128~6 - 139900389254233/32~5 - 3264518827489/4~4 - 234oo5131717649/32~J - 650184017173519f256~2 + 33744914112585/4~ - 333711335100551/128
1421478951492431/256~1 0
- 86970691550133/32~9 - 959425090967179/128~8 + 140484061 157699/32C + 654028913747701/128~6 + 139900389254233/32~5 + 3264518827489f4~4 + 234oo5131717649/32~J + 650184017173519/256e - 33744914112585/4~ + 333711335100679/128
lire faclorization 17 + 8511627172651 6 + 143296653482851 5 + 23221573318851 4 + 1082290121011I J + 31967940825951 2 + 21006435379991 + 15204983818911. 14 + 167410233272521 J + 29829686280061 2 + 84805826600201 + 809919201793.
furllrer idempolellls 390730948745463/128~6 - 1974053779852231/64~5 - 746745761669899f128~4 -191811737241957/32~J - 1004454580604047/128~2 - 179581618641623/64~
- 433530700975229/128. - 390730948745463/128~6 + 197405377985231/64~5 + 746745761669899/128~4 + 191811737241957/32~J + 1004454580604047/128~2 + 179581618641623/64~ + 433530700975357/128.
a furllrer faclorizalion 16 + 51964051707341' + 141488314476671 4 + 161092285670281 J + 85079323537511 2 + 11870227502526/ + 10540983492437 1+ 13246943590947.
lire 2-minimai basis WII
WlO
= 1/2048~IO + 1/1024~9 + 1/2048~B + 1/256C + 1/1024~6 - 11/256~J - 99/2048~2 + 25/1024~ + 53/2048 = 1/512~9
+ 1/512~B -
3/256~' - 3/256~4 + 1/64~J
W9
= 1/256~B - 3/128~4 + 1/32~2 - 3/256
+ 1/128~6 +
= 1/128C
= 1/64~6 + 1/64~4 - 5/64~2 + 3/64
W6
= 1/32~' 1/16~4
+ 1/64~2 -
+ 1/32~4 + 1/16~J + + 1/8~2 - 3/16
1/16~2 - 3/32~ - 3/32
w4=1~~J+I~~2_1~~-I~ Wj
= 1/4~2 - 1/4
W2
= 1/2~ + 1/2
WI =
3/512~ - 3/512
1/128~' + 1/128~4 - 5/128~J - 5/128~2 + 3/128~ + 3/128
WB
W7
w, =
+ 7/512~5 + 21/1024~4
1.
p=3 faclors mod 3 16 +1' + 21 3 + 12 + 21 + 1 13 + 12 + I + 2 I.
452
Appendix: Numerical tables
factorizatioll mod 3 24 t 6 + 120783431803t' + 8973604878t 4 + 61904146670t 3 + 31825819645t 2 + 183824600885t + 30301271638 t 3 + 156274299151t 2 + 97643734609t + 173505680846 t 2 + 5371805628t + 22263657813, 3-millimal basis WI I
= 1/729~IO
+ 101/729~9 - 223/729~8 - 358/729C - 34/729~6 - 34/729~' - 34/729~4 - 34/729~3 - 34/nn 2 - 34/n9~
WIO
= ~9
W9 =
~8
W8=C W7
= ~6
W6
=~'
W,
= ~4
W4=~3 W3=e W2
= ~
w l =1
p=5 factors mod 5 t+4 t+I factorizatioll mod 58 t4 + 187926t 3 + 272826t 2 + 260801t + 308101 + 336550t 4 + 176650t 3 + 80725t 2 + 165425t + 246226 t 2 + 256875t + 161875,
I'
idempotellls - 52091/5~4 - 884924/5~J - 871611/5e + 16121/5~ + 278999/5 52091/5~4 + 884924/5~3 + 871611/5~2 - 16121/5~ - 278994/5,
factorizatioll t 4 + 309039t J + 157846/ 2 + 157544t + 347441 t + 27511, idempolelllS - 4543197/25~ - 49587 4543197/25~ + 49588,
factorizatioll 1+725 1+256150,
5-millimal basis WII
WIO
= 1/25~IO + 1/25~9 + 1/25~8 + 1/25C + 1/25~6 + 1/25~' + 1/25~4 + 1/25~3 + 1/25~2 + 1/25~ = 1/5~9
w9 = ~8 W8=C W 7 = ~6
+ 1/5C + 1/5~' + 1/5e + 1/5~
Appendix: Integral bases
(1)6
453
= ~s
Ws =
~4
(1)4
= ~3
(1)3
=~'
W, =~ W, =
I.
p=19
jactors mod 29 /4 + 27/ 3 + 9/' / +28 / + 12,
+ 10/ + 24
jac/oriza/ioll mod 29 8 /4 + 50605465738/ 3 + 52694279576/' + 495928586992/ + 216188927047 /3 + 179037728472/ 2 + 480036204243/ + 194325614858 /4
+ 270603218852/ 3 + 311400732346/ 2 + 383680458976/ + 294504268343,
idempo/elllS 170950383710294/84W - 124930383118041/841~ -170950383710294/841~2
+ 116845930821609/841
+ 124930383118041/841~ - 116845930820768/841,
jac/oriza/ioll /2
+ 235370557884/ + 112494502447
/ + 443913583549, idempo/ellls 3441901651958/29~
- 5081864234391/29, -
3441901651958/29~
+ 5081864234420/29,
jac/oriza/ioll
/ + 300710030106
/ + 434906940739 29-millil1lal has is
w,' =
1/24389~' 0 + 2/24389~9 + 9/24389~8 + 279/24389C + 325/24389~6 - 11199/24389~s - 11647/24389~4 + 9277/24389~3 + 1911/24389~2 + 1329/24389~ 9713/24389
+
w,o = 1/841~9 + 10/841 C - 11/841 ~6 - 153/841~ - 129/841 0)9
+ 90/841 ~s -
1/29~4
+ 379/841 ~3 - 158/841 ~2
- 9/841C + 4/841~6 + 330/841~s - 357/841~4 -- 383/841~3 + 259/841~2 + 5/841~ + 150/841
= 1/841~8
W8 =
1/29C + 10/29~s
tv7 = 1/29~6 W6
=~'
tv,
= ~4
w4
=C
+ 1O/29~4 - 11/29~3 - 3/29~2 + 11/29~ + 11/29 + 9/29~s + 4/29~4 - 12/29~3 - 3/29~2 - 1/29~ + 2/29
tv3 = ~2
tv, = ~
w, = I
llllegral hasis
(~ =
/If )
W,' = 1/910314547200~'0 -
85607/455157273600C + 1352801/910314547200~8 - 921683/1 137893 I 8400C - 84877487/455157273600~6 + 507753959/227578636800~' + 7760693413/455157273600~4 - 741690983/113789318400~J - 19749911299/910314547200~' + 40692408193/455157273600~ - 4064571/49948672
454
Appendix: Numerical tables
ill I0 = 1/2152960~9 + 1/430592~8 - 1/33640C + 7/26912~6 - 223/37120~' + 2533/215296~4 - 8863/269120~3 + 3963/53824~2 + 115901/2152960~ - 43283/430592 ill9 = 1/215296~s + 5/53824C + 1/53824~6 + 155/53824~' + 387/107648~4 - 1437/53824~3 + 5089/53824e 2 + 10173/53824~ - 56719/215296 Ws = 1/3712C + 1/3712e 6 - 39/3712e' - 15/3712e 4 - 197/3712e' + 139/3712~2 + 619/3712~ - 509/3712 ill7 = 1/1856~6 - 5/464~'
+ 1/32~4 +
+ 33/1856~4 + 13/232~3 + 171/1856~2 -109/464~ +
W6
= 1/32~'
W,
= 1/16~4 + 1/8e - 3/16
147/1856
1/16e + 1/16e - 3/32~ - 3/32
w4=1~~3+1~~2_1~~-I~ W3
= 1/4e - 1/4
W2
= 1/2~
+ 1/2
wl=1 The index of the equation order in its maximal order is 2'6 x 36 X 53 X 29 9,
2, For fIt) = d,(f) = = d(f) =
t" - 3080t + 3024 we obtain the reduced discriminant 9147600 24 x 33 X 52 X 7 X 112 and the discriminant 2216 X 3 162 X 5'6 X 7'4 X 11'6,
The algorithm produces:
p=2 idempotents 11/4C 4 + 111/2C 3 + 3~'2 + 14~'1 - 20e'o - 8~49 + 48~48 - 32~47 _ 64~46 + 128e4' - 235/4~36 - 69~35 + 73e 4 - 48C 3 + 8~32 - 96e'1 + 32C o + 64e 2S + 53/2~IS - 101~17 + 84~16 _ 8~I' - 88~14 + 48~13 _11/4~'4
_
111/2~53
_
3~'2
_
14~'1
+
+ 235/4e 6 + 69~35 -73C4 + 48e 33 -84~16+8~I'+88eI4-48~\3+
factorization mod
20~'o
+
8~32
8~49
_
48~4S
+ 96e 31 -
+ 32~47 + 64~46 + 128~4' 32Co - 64e 28 - 53/2~18 + 101e 17
I
28
148t 34 + 64t H + 160t 32 + 128t 31 + 128t 30 + 661 18 + 1881 17 + 16t l6 + 961 1' + 321 14 + 1921 13 + 4 t l9 + 1961 18 + 124t l7 + 961 16 + 481 1' + 641 14 + 641 13 + 1901 + 52,
t 36
+ 60t 35 +
idempotents 97/2~18 _17~17
-97/2~18
+
+ 4~16 -104~I' -
17~17 _4~16
+
104~I'
120~14
-
+ 120~14+
16~\3
16~13
+
+
128~12
128~12
factorizalion
liS + 158t l7 + 8t l6 + 48t l ' t + 38
+ 161 14 + 2241 13 +
Inlegral basis W"
= 1/8~'4
W'4 =
W'3
1/4~53
= 1/4~'2
ill37 = 1/4C 6 ill36 = 1/2~35 ill 3, = 1/~~34
190
+ I,
Appendix: Algorithms
CO IS CO l7
455
=e e
17
l6
=
CO 2 =
e
COl =
I
The index of the equation order in its maximal order is 2S7 Both examples were computed by R. Boffgen of Saarbriicken, who implemented an earlier version of the embedding algorithm on a Siemens 7560 computer. The CUP times were 73 and 1192 seconds. The first polynomial has Galois group M II the second ~ISS' The polynomials were found by B.H. Matzat of Karlsruhe. (References: R. Boffgen, Der Algorithmus von Ford/Zassenhaus zur Berechnung von Ganzheitsbasen in Polynomalgebren, Ann. Vniv. Saraviensis, Ser. Math., 1,3 (1987), 60--129; B. H. Matzat, Konstruktion von Zahl-und Funktionenkorpern mit vorgegebener Galoisgruppe, J. Reine AngelY. M~th. 399 (1984), 179-220).
Algorithms Berlekamp's Comparing elements of small absolute norm with stored ones Computation of class group normal presentation of an ideal resultants successive minima torsion subgroup TV(R) of the unit group VCR) vectors of bounded norm in a lattice all x, yeZ subject to - k ~ ax + by ~ k,lyl ~ k all x, yeZ~O salisfyingj ~ ax + by ~ k Diophant Divisor cascading Equal degree factorization in IF q[t] Embedding an equation order into its maximal order Enlarging sublattices Euclid's (in Z) with presentation of the greatest common divisor Gauss' determining a primitive root General reduction Hermite normal form Horner's LLL-reduction MLLL-reduction Quadratic supplement Symmetric functions
page
85 358 421 405 60
199 348 190 354 357 5 25 81 313 211 3
70 194 180 5
201 209 188 50
REFERENCES
Chapter 1 D.E. Knuth, The Art of Computer Programming, vol. 2, 2nd edn, AddisonWesley, 1981. 2 S. Lang, Algebra, Addison-Wesley, 1971.
Chapter 2 I JR. Bastida, Field extensions and Galois theory. Eneycl. of Math. 22, AddisonWesley, 1984. 2 D. Cantor & H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp., 36 (1981), 58792. 3 N. TschebotarefT, Die Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionsklasse gehoren, Math. Ann., 95 (1926), 191228. 4 E. Galois, Oeuvres, v-x and 1-61, Paris, 1897. 5 C.F. Gauss, Werke, vol. 1 (Disquisitiones Arithmeticae), vol. 2 (Seetio Oetava), Gouingen, 1876. 6 D. Hilbert, Gesammelte Abhandlungen, Band 2, 393-400, Springer Verlag, Berlin, 1933. 7 F. Klein, Vorlesungen iiber das Ikosaeder, Teubner Verlag, Leipzig, 1884. 8 D.E. Knuth, The Art of Computer Pro· gramming, vol. 2, sec. edn, Addison- Wesley 1981. 9 R. Land, Computation of P61ya polynomials of primitive permutation groups, Math. Comp., 36 (1981),267-78. 10 S. Lang, Algebra, Addison-Wesley, 1971.
II R. Lidl & H. Niederreiter. Finite Fields. Eneyc/. of Math. 20. Addison-Wesley. 1983. 12 H. Niederreiter. Quasi-Monte Carlo methods and pseudo-random numbers. Bull. of tile AMS, 84 (1978), 957-1041. 13 St. Schwarz, Contribution ala n:ductibilite des polynomes dans la theorie des congruences, Ceska Spolecniet Nauk Prague. Trida Mathematicka Prirodovedecka Vestnik (1939). 1-7. 14 St. Schwarz, Sur Ie nombre des racines et des facteurs irreductibles d'une congruence don nee, Casopis Pro Pestovani Matematiky A Fysiky, Prague V. 69 (1940). 128-45. 15 St. Schwarz, On the reducibility of polynomials over a finite field. Quart. J. Math. Oxford Ser. (2), 7 (1956). 110-24. 16 W. Trinks, Ein Beispiel eines Zahlkorpers mit der Galoisgruppe PSL(3, F 2) iiber C, Manuscript, Univ. Karlsruhe, WestGermany, 1968. 17 H. Wielandt. Finite Permllfation Groups, Academic Press, New York. London. 1964. 18 H. Zassenhaus, The Theory of Groups. sec. edn, Chelsea. 1958.
Chapter 3. I A. Bachem & R. Kannan, Lattices and the Basis Reduction Algorithm, Report 84, 6, Mathematisches Institut, Universitiit zu Koln,1984. 2 H.F. Blichfeldt. A new principle in the geometry of numbers. with some applications. Transa~tions Amer. Math. Soc .• 15 (1914).227-35.
References 3 J.W.S. Cassels, An IlIIroduction ro rhe Geomerry of Numbers, 2nd edn, Springer Verlag, Berlin, Heidelberg, New York, 1971. 4 U. Fincke & M. Pohst, Improved methods for calculating vectors of short length in a lallice, including a complexity analysis, Math. Comp., 44 (1985), 463-71. 5 O. Havas & L. Sterling, Integer matrices and abelian groups; p. 431-56 in Symbolic and Algebraic Compurarion. Lecrure Nores in Compurer Science. 72, Springer Verlag, Berlin, Heidelberg, New York, 1979. 6 R. Kannan & A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, Siam J. Comput., 8 (1979), 499-507. 7 D.E. Knuth, The Art of Computer Programming. vol. 2, sec. edn, AddisonWesley, 1981. 8 S. Lang, Algebra, Addison-Wesley, 1971. 9 CO. Lekkerkerker, Geometry of Numbers, Wolters-Noordhoff Publishing, Oroningen, and North-Holland Publishing Company, Amsterdam, 1969. 10 A.K. Lenstra, H.W. Lenstra, Jr., & L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-34. II M. Mignolle, An inequality about factors. of polynomials, Math. Comp., 28 (1974), 1153-7. 12 D.R. Musser, Multivariate polynomial factorization, JACM, 22, no. 2 (1975), 291308. 13 M. Pohst, On computing isomorphisms of equation orders, Math. Compo 48 (1987), 309-14. 14 J. Renus, Gitterreduktionsverfahren mit Anwendungen auf lineare diophalllische Gleichungssysteme, Diplomarbeit, Universitiit Diisseldorf, 1986.
Chapter 4 I O.E. Collins, The calculation of multivariate polynomial resultants, JACM, 18 (1971),515-32. 2 E. Noether, Abstrakter Aufbau der Idealtheorie in algebraischen Zahl - und Funktionenkiirpern, Math. Ann., 96 (1927), 26-61. 3 M. Pohst, On the computation of number fields of small discriminants including the minimum discriminants of sixth degree fields, J. Number Theory, 14 (1982),99-117.
457
4 M. Pohst, P. Weiler & H. Zassenhaus, On effective computation offundamental units II, Math. Comp., 38 (1982),293-329. 5 H. Zassenhaus, On an embedding algorithm of an equation order into its maximal order for algebraic function fields. To appear in Monatshefte fiir Mathemarik.
ChapterS I U. Fincke, Ein Ellipsoidverfahren zur Liisung von Normgleichungen in algebraischen Zahlkiirpern, Thesis, Dusseldorf 1984. 2 K. Mahler, Inequalities for ideal bases in algebraic number fields, J. Austral. Marh. Soc., 4 (1964), 425-47. 3 M. Pohst, Regulatorabschiitzungen fUr total reelle algebraische Zahlkiirper, J. Number Theory, 9 (1977), 459-92. 4 M. Pohst, Eine Regulatorabschiitzung, Abh. Math. Sem. Univ. Hamburg, 47 (1978), 221-31. 5 M. Pohst & H. Zassenhaus, On effective computation of fundamental units I, Marh. Comp., 38 (1982), 275-91. 6 M. Pohst, P. Weiler & H. Zassenhaus, On effective computation offundamental units II, Marh. Comp., 38 (1982), 293-329. 7. R. Remak, Uber die Abschiitzung des absoluten Betrages des Regulators eines algebraischen Zahlkiirpers nach unten, J. Reine Angew. Marh., 167 (1932),360-78. 8 CL. Siegel, The trace of totally positive and real algebraic integers, Annals of Math., 46 (1945),302-12. 9 CL. Siegel, Abschiitzung von Einheiten, Nachr. Akad. Wiss. Gottingen Marh. Phys. KI. (1969), 71-86. 10 B.M. Trager, Algebraic Factoring and Rational Function Integration, Proc. of the 1976 ACM Symposium on Symbolic and Algebraic Compurarion rSYMSAC 76') pp.219-26. II N. Tschebotareff, Die Bestimmung der Dichtigkeit einer Menge von Primzahlen, we1che zu einer gegebenen Substitutionsklasse gehiiren, Marh. Ann., 9S (1926), 191228. 12 H. Zassenhaus, On Hensel Factorization I, J. Number Theory, I (1969), 291-311. 13 H. Zassenhaus, On the units of orders, J. Algebra, 20 (1972), 368-95. 14 R. Zimmert, Ideale kleiner Norm in Idealklassen und eine Regulatorabschiitzung, Invenr. Math., 62 (1981), 367-80.
458
References
Additional references 15 1. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm, J. Numher Theor'y, 26 (1987), 8-30. 16 J. Buchmann, Generalized continued fractions and number theoretic computations, Bericht Nr. 269 der math.-stat. Sektion in der Forschllll{jsf/esellsc!wjt Joanneum, Graz, 1986. 17 B.N. Delone & D.K. Fadev, The theory of irrationalities of the third degree, Amer. Math. Soc. TrallSl. of Math. Monographs 10, 1964. 18 V. Ennola & R. Turunen, On totally real cubic fields, Math. Comp., 44 (1985), 495519. 19 E.L. Ince, Cycles of reduced ideals in quadratic fields, reissued by Cambridge University Press, London 1968. 20 H.W. Lenstra Jr., On the calculation of class numbers and regulators of quadratic fields, Lond. Math. Soc. Lect. Note Ser. 56 (1982), 123-50. 21 D. Shanks, The infrastructure of real quadratic fields and its applications, Proc.1972 Numh. Th. COIlf., Boulder (1972),217-24. 22 R.P. Steiner, On the units in algebraic number fields, Proc. 6th Manitoha CO'lf., Num. Math. (1976), 415-35.
23 H.C. Williams, Continued fractions and number theoretic computations, Rocky Mountain J. Math., 15 (1985), 621-55. 24 H.G. Zimmer, Computational problems, methods and results in algebraic number theory, Springer Lect. Notes ill Math. 262 (1972).
Chapter 6 I U. Fincke, Ein Ellipsoidverfahren zur Losung von Normgleichungen in algebraischen Zahlkorpern, Thesis, Diisseldorf 1984. 2 U. Fincke & M. Pohst, A procedure for determining algebraic integers of given norm, Proc. Eurosam 83, Sprillger Lecture Notes ill Computer Science 162 (1983), 194-202. 3 K. Mahler, Inequalities for ideal bases in algebraic number fields, J. Austral. Math. Soc., 4 (1964), 425-47. 4 D.A. Marcus, Number Fields, Universitext, Springer Verlag, New York, Heidelberg, Berlin, 1977. 5 M. Pohst & H. Zassenhaus, Ober die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlkorper, J. Reine Angew. Math., 361 (1985), 50-72. 6 c.L. Siegel, Ober die Klassenzahl quadratischer Zahlkorper, Acta Arithmetica, 1 (1935), 83-6.
INDEX
Abel, N.H., 38 absolute valuation, 234 active (side condition), 364 aleatoric (construction of finite fields), 73 algebraic equation, I integers, 22, 246 number field, 327 numbers, I ordering, 232 of a group, 235 sum, 42 algebraically decomposed, 36 ordered group, 235 ring, 230 semiring, 232 algorithm, I amalgamation (of R-bases), 305 a-maximal, 304 antisymmetric see skew symmetric a-overorder, 303 archimedian ordered, 249 valuation, 231 arithmetic radical, 292 Artin, E., 87, 97 Artin-Schreier, 104 generators, 106 normal form, 39 theorem of, 79 associate, 20, 24, 330 automorphism, 16 Banach, St., 255 basic parallelotope, 351 symmetric functions, 30, 48, 50
basis, 9 normalized, 237 of a free module, 177 of a subset of a factorial monoid, 24 theorem for finite abelian groups, 285 Bastida, 1. R., 87 Berlekamp's method, 83-5 Bernstein, L., 329 bilinear form, 308 Blichfeldt, H.F., 199 blocks of imprimitivity, 144 Boifgen, R., 455 Bring-Jerrard normal form, 39 Buchmann, J., 329 Cantor, D., 83 Cayley matrix representation, 163 tebotarev see TschebotarefT ceiling, 411 principal, 412 central idempotent, 41 centralizer, 170 characteristic, 225 equation, 34 polynomial, 17, 34, 55 Chevalley's lemma, 241 theorem, 243 Chinese remainder theorem, 45 Cholesky, 188 decomposition, 189 class group, 287 matrix, 414 computation procedure, 421-3 number, 378, 380, 384 semigroup, 289 Collins, G.E., 319, 325, 347 comaximal, 306
460 common divisor, 27 inessential discriminant divisor, 318 multiple, 27 commutative ring, 6 constructively given, 6 companion matrix, 349 comparable, 248 complex quadratic field, 329 conductor, 388 conjugate, 19, 329 connecting R-module, 170 constant polynomial, 10 convex, 212 body theorem of Minkowski, 213 core algorithm, 323, 324 cyclic module, 309 cyclotomic . equation, 157 field, 159 polynomial, 159 units, 160 Dade, E.C., 291, 313 decomposed, 36 Dedekind, R., 221, 253, 273 criterion, 295 domain see ring ring, 221, 253, 265-278 test, 316, 317 decomposition of prime ideals, 390 in quadratic fields, 393, 394 degree of an algebraic number field, 327 of a polynomial, 10 of inertia, 386 theorem, 13 valuation, 248 .5-element, 322 .5-split, 320 .5-uniform, 321 dependent (units), 331 derivation (of a ring), 26,91-3 deterministic methods (for constructing finite fields), 77-80 Deuring, M., 171 dimension (of a lattice), 187 Diophantine analysis, 4 direct sum (of modules), 8 Dirichlet, P.G.L., 273, 377 (Unit) Theorem, 334 discrete valuation, 251 discriminant composition formula, 122 ideal, 121, 292 of an algebraic number field, 329 of a lattice, 187 of a module, 122 of a polynomial, 34,49,61, 62
Index of cyclotomic polynomials, 161 divisible group, 243 divisibility, 20, 23 division ring, 235 with remainder of integers, 2 of polynomials, 10, II divisor cascade, 24 domain of rationality, 29 dual basis, 281, 337 -index rule, 292 Eisenstein, G., 221, 258 extension, 260 polynomial, 258 element = .5-element, 322 elementary changes, 310 divisor, 184 form presentation, 284 ideal,284 normal form, 184 ideals, 282 matrices, 178 equal degree factorization, 81 equivalence, 20, 23 of matrix representations, 165 of permutation representations, 142 equivalent pseudo valuations, 235 Euclidean algorithm, 3, 4 ring, 21 Euler
Index fundamental parallelotope, 187 unit, 328, 334 Galois, E., 29, 38, 40, 69, 219 correspondence, 19, 90 fields, 70 Gauss, CF., 15,20,29,44,46,69,70,71, 172, 173, 384 integer ring, 15-22 period, 20, 172 general linear group, 165, 311 reduction algorithm, 194, 195 generalized pseudo valuation, 235 generator system of invariants, 146 generic argument, 55 element, 52 polynomial, 48, 56 Godwin, H.J., 329 grading, 309 Gras, M.N., 329 greatest common divisor, 3, 27 group general linear, 165, 311 special linear, 166, 311 unimodular, 311 group of an equation, 108 of permutation automorphisms, 32 of the cyclotomic equation, 157, 158 of units, 329 half module, 143 ring, 233 Hamilton-Cayley equation, 22 Hasse diagram, 19 height function, 21 Hensel, K., 221, 325 lemma, 301 Hermite constants, 198 normal form, 179, 311 (column, row) reduction, 179 Hilbert, D., 39, 309 theorem, 79, 90 Holder, 0., 255 holomorph of a group, 133 Huppert, 8., 141 hypercube, 174 ideal class group, 380 elementary, 282 equivalence procedure, 424 fractional, 264, 265 group, 379
461
large, 229 normal presentation of, 400 numbers, 221 presentation, 397 prime elements, 221 idempotents, 40 central,41 orthogonal, 42 primitive, 42 central,43 identity mapping, 16 imprimitive permutation representation, 144 inclusion of normally presented ideals, 403 indecomposable representation, 143 splitting rings, 63-9 independence of valuations, 251 independent units, 331 index, 72 discriminant rule, 292 ideal, 286, 290 multiplicativity, 292 of a lattice, 187 table, 72 infinitely larger, 248 inseparable equation, 35 polynomial, 35, 49 integral basis, 314 of quadratic fields, 317, 318 of cyclotomic fields, 318 integral closure, 245-8 element, 246 integrally closed, 246 intransitive representation, 143 invariant, 16 inverse of a normally presented ideal, 401, 402 invertible R-fractional ideal, 264 involutory mapping, 16 rule, 292 Jacobson radical, 307 Jordan, C, 119, 141 Klein Four Group 'B 4 , 8, 18 Knuth, D.E., 4, 85, 183 Krasner, M., 325 Kronecker criterion, 247 symbol,lO theorem, 157 Krull, W., 274 exponential valuation, 249 p-adic, 268 valuation, 235, 239 ring, 239
462 Kuershak, 221 Kummer, E.E., 220, 253, 273, 377 ex tension, 104 Lagrange, J.L., 97, 104 operator, 97-9 Lambek, 1., 229 Lambek-Ushida quotient ring, 230 Land, R., 296, Landau, E., 287, 367 Lang, S., 6, 7, 8, 10,24,45,87,91 large ideal, 229 Lasker, E., 309 lattice, 187 leading coefficient, 10 least common multiple, 27 left module, 7 regular matrix representation, 163 unital module, 8 Lenstra, H.W.Jr., 329 Lenstra, Lenstra and Lovasz, 177, 200 reduction = LLL reduction, 200-202 Lidl, R., 70, lifting of idem po tents, 115-17 list of cyclotomic polynomials, 344, 345 LLL reduction see Lenstra, Lenstra and Lovasz reduction local domain, 227 ring, 227 localization, 220, 226-9, 303-5 logarithmic space, 360 long division see division with remainder lying (over, under) of ideals, 386 Mahler, K., 338, 379, 410, 411 Miiki, S., 329 main theorem of Galois theory, 87 matrix representation, 164-9, faithful, 165 improper, 168 null,I68 proper, 168 regular, 164 sum of, 168 Matusita, 274 Matzat, B.H., 455 maximal a-, 304 order, 22, 278 purely inseparable extension, 96 subfield, 119 R-order, 278 separable overring, 94 McCauley, 309 McKay, 1. see Soicher, L. minimal basis see integral basis
Index
equation, 17 polynomial, 17 splitting ring, 30 Minkowski, H., 177, 378 bound = constant 384 convex body theorem, 213 mapping, 383 reduction, 191 MLLL reduction 209 Mobius inversion formula, 76 II-function, 76 modified division with remainder see pseudo-division module connecting R-, 170 cyclic, 309 discriminant of, 122 free R-, 9 half, 143 left, 7 left unital, 8 Noetherian, 309 null,7 rank of, 9 relation, 282 representation, 166 row, 282 syzygy, 282 modulo p independent, 394 monic,lO equation, 13 multi modular calculus, 46 multiplicative character of a group, 98 valuation, 231 multiplier = 1fI- multiplier, 239 Newton, I., 257 polygon, 258 relations, 51 Niederreiter, H., 70, 73 nil ideal, 115 nilradical, 115 Noether, E., 171,274,307 Noetherian, 309 non-archimedean pseudo valuation, 231 non-degenerate, 308 norm, 16, 34, 53, 55 of a polynomial, 346 of an ideal, 291, 381 normal basis, 19, 163 extension, 68 presentation of ideals, 400 normal form elementary divisor, 184 of Hermite, 179, 311 of monic quadratic equations over Z, 40 of Smith, 184
Index
normalized basis, 237 element, 322 valuations, 411 null module, 7 number of monic irreducible III-th degree polynomials in 11'.[1], 76, 77 orbit, 143 order, 22, 278 of an algebraic number field, 327 ideal, 285 rank,249 orthogonal (left, right) B-complement, 308 idempotents, 42 Ostrowski, A., 221, 255 overorder see o-overorder overring see R-ring p-adic valuation, 231 p-adic Krull exponential valuation, 268 pairwise reduced, 211 parallelotope basic, 351 fundamental, 187 partial endomorphism, 229 Peacock,6 Peirce decomposition, 40, 41 Pell's equation, 328 perfect, 26, 119 permanence principle, 6 permutation automorphism, 32 matrix, 169 representation, 142 rp-multiplier see multiplier Ill-unit see unit PID see principal ideal domain polynomial characteristic, 17, 34, 55 constant, 10 cyclotomic, 159 degree of a, 10 discriminant of a, 34, 49, 61, 62 Eisenstein, 258 generic, 48, 56 inseparable, 35, 49 minimal,I7 primitive, 86 principal, 55 pseudo Eisenstein, 263 separable, 49 potential list, 70 power sum, 51 p-power characteristic, 117 presentation of gcd, 3 of ideals, 397 prime
element, 21 ring, 48, 57, 78 primitive central idempotent, 43 element, 140, 173-6 extension, 139 idempotent, 42 permutation groups, 141 permutation representation, 144 polynomial, 86 root, 70 root of unity, 344 principal ceiling, 412 equation, 52 ideal domain = PID, 266 ideal procedure, 424 ideal ring, 21 polynomial, 55 product formula for valuations, 235, 411 of normally presented ideals, 401 valuation, 237 proper unimodular matrix, 165 Priifer ring, 284 pseudo division, II Eisenstein polynomial, 263 valuations, 231 purely inseparable element, 117 equation, 118 extension, 95 pure quadratic equation, 34 quadratic supplement, 188 quotient, 2 ring, 7, 222-5 radical element, 98 ramification index of ideals, 386 of valuations, 275 ramified, 386 rank of a lattice, 187 of a module, 9 rational, 254 real quadratic field, 329 reduced discriminant ideal, 292 computation, 296 integer, polynomial, 314 reduction, 191-202 of Lenstra, Lenstra and Lovasz = LLL, 200-202 modified = MLLL, 209 of Minkowski, 191 pairwise, 211 total, 192-5
463
464 of Hermite see Hermite (column, row) reduction regular matrix representation, 164 permutation representation, 144 representation, 55 trace, 280 regulator, 361 relation matrix, 282 module, 282 relative norm, 18 remainder, 2 Remak, R., 362 representation module, 166 space, 167 resultant, 49, 57-61 R-fractional ideal see fractional ideal ring algebraically ordered, 230 commutative, 6 constructively given, 6 Dedekind, 221, 253, 265-78 division, 235 Euclidean, 21 factorial, 21 half,233 Krull valuation, 239 Lambek-Ushida quotient, 230 local,227 of an equation, 13, 14 of Gaussian integers, 15-22 prime, 48, 57, 78 principal ideal, 21 Priifer, 284 quotient, 7, 222-5 R-,9 semilocal, 228 semisimple, 307 simple, 307 splitting, 30 unital,6 universal splitting, 30 valuation, 236 root, 10 estimates, 151, 152 finder, 135 R-order see order row equivalence, 283 module, 282 Ruffini, P., 38 Schreier see Artin-Schreier Schwarz, St., 81 semidirect product, 133 semigroup ring, 167 semilocal ring, 228 semiring, 232
Index semisimple, 307 separability, 92 separable, 35, 49, 93-5 Shanks, D., 329 s-hypercube, 174 Siegel, c.L., 367 simple, 307 Sims, Ch. C., 428 skew symmetric, 308 Smith normal form, 184 Soicher, L. and McKay, 1., 429 solution ring, 14 Sonn, J., 173 specialization, II special linear group, 166, 311 split = c5-split, 320 splitting field,36 ring, 30 sta bilizer, 144 standard basis, 30 generators, 136 Stauduhar, R.P., 429 Steinitz, 287 class, 288 Stender, H.J., 329 Stirling's formula, 37 strong independence of valuations, 251 structural stability, 297-9 Study numbers, 23 sublattice, 187 successive minima, 195 sum of matrix representations, 168 of permutation representations, 142 symmetric, 308 functions, theorem on, 50 polynomials, 48 system of imprimitivity, 144 syzygy module, 282 Taussky, 0., 167,291, 313 torsion element, 22 free, 228 subgroup (of unit group), 330 submodule, 229 total reduction, 192 totally complex algebraic number field, 329 ramified valuation, 260 real algebraic number field, 329 trace, 16, 34, 53, 55 bilinear form, 54 radical, 123 regular, 280 Trager, B., 346 transitive permutation representation, 143 Trinks, W.,
Index equation, 155, 156 trivial permutation representation, 144 TschebotarefT, N. 130,371 density theorem, 130 Tschirnhausen transformation, 38 uniform = (i-uniform, 321 unimodular group, 311 matrices, 165 un!que factorization ring see factorial ring umt group, 329 matrix 1", 178 CPO, 238 unital,6 overring, 10 universal splitting ring, 30 unramified, 386 valuation, 231 absolute, 234 archimedean, 231 degree, 248 discrete, 251 exponential, 248 generalized pseudo-, 235 Krull, 235, 239 exponential, 249 p-adic, 268
module, 236 multiplicative, 231 non archimedean pseudo, 231 normalized,411 p-adic, 231 product, 237 pseudo, 231 ring, 236 Krull,239 totally ramified, 260 valuations independence of, 251 product formula for, 235,411 ramification index of, 275 strong independence of, 251 weak independence of, 276 Vandermonde's determinant, 54 van der Waerden, B.L., 346 criterion, 127-9 Vieta equations, 30 weak independence (of valuations), 276 Weierstrass mapping, 78 Wielandt, H., 141 Williams, H.C., 329 Wilson's theorem, 107 Zassenhaus, H., 83,141,173,291,313 zero, 4, 12 Zimmer!, R., 366
465