A New Algorithm for the Computation of Logarithmic

A New Algorithm for the Computation of Logarithmic

-Class Groups of Number Fields

Francisco Diaz y Diaz, Jean-François Jaulent, Sebastian Pauli, Michael Pohst, and Florence Soriano-Gafiuk

CONTENTS 1. Introduction

2. The Theoretical Background 3. The Algorithms

4. Examples References

2000 AMS Subject Classification:Primary 11Y40; Secondary 11R70 Keywords: K-theory, wild kernel, logarithmic class group, computation

We present an algorithm for the computation of logarithmic- class groups of number fields. Our principal motivation is the effective determination of the -rank of the wild kernel in the K-theory of number fields.

1. INTRODUCTION

A new invariant of number fields, called group of loga- rithmic classes, was introduced by J. -F. Jaulent in 1994 [Jaulent 94]. The interest in the arithmetic of logarithmic classes comes from its applicability inK-Theory. Indeed, this new group of classes is revealed to be mysteriously re- lated to the wild kernel in theK-Theory of number fields.

The new approach to the wild kernel is very attractive since the arithmetic of logarithmic classes is very effi- cient. Thus it provides an algorithmic and original study of the wild kernel. An early algorithm for the compu- tation of the group of logarithmic classes of a number field F was developed by F. Diaz y Diaz and F. Soriano in 1999 [Diaz y Diaz and Soriano 99]. We present a new and significantly better performing algorithm, which also eliminates the restriction to Galois extensions.

Letbe a prime number. If a number fieldF contains the 2th roots of unity, then the wild kernel ofF and its logarithmic-class group have the same-rank. IfF does not contain the 2th roots of unity, the arithmetic of the logarithmic classes still yields the-rank of the the wild kernel. More precisely:

• If is odd [Jaulent and Soriano 01, Soriano 00] we consider F := F(ζ), where ζ is the th root of unity, and use classic techniques from the theory of semisimple algebras.

• If = 2 [Jaulent and Soriano-Gafiuk 04] we intro- duce a new group, which we call the -group of the

c A K Peters, Ltd.

1058-6458/2005$0.50 per page Experimental Mathematics14:1, page 65

positive divisor classes and which can be constructed from the-group of logarithmic classes.

In the present article we consider the general situation where F is a number field which does not necessarily contain the 2th roots of unity.

2. THE THEORETICAL BACKGROUND

This section is devoted to the introduction of the main notions of logarithmic arithmetic. We also review the facts that are of interest for our purpose. We do not attempt to give a fully detailed account of the logarithmic language. Most proofs may be found in [Jaulent 94, pages 303–313].

2.1 Review of the Main Logarithmic Objects

For any number fieldF, letJF be the-adified group of id`elesofF, i.e., the restricted product

JF = res

p

Rp

of the -adic compactifications Rp = lim←− F_p^×/F_p^×

n

of the multiplicative groups of the completions ofF at each p. For each finite place p the subgroup Up ofRp of the cyclotomic norms (that is to say the elements ofR_pwhich are norms at any finite step of the local cyclotomic Z- extension F_p^c/F_p) will be calledthe group of logarithmic unitsofF_p. The product

UF =

p

U_p

is called thegroup of idelic logarithmic units; it happens to be the kernel of the logarithmic valuations

v_p |x → −Log(N_Fp/Qp(x)) deg_Fp ,

defined on the R_p and Z-valued. These are obtained by taking the Iwasawa logarithm of the norm ofxin the local extensionF_p/Qpwith a normalization factor deg_F p whose precise definition is given in the next subsection.

The quotient DF = JF/UF is the -group of loga- rithmic divisors ofF; via the logarithmic valuations v_p, it may be identified with the free Z-module generated by the prime ideals ofF

DF = JF/UF = ⊕_p Zp.

Thedegreeof a logarithmic divisord=

pn_ppis then defined by

deg_F(

p

n_pp) =

p

n_pdeg_F p,

inducing aZ-valuedZ-linear map on the class group of logarithmic divisors. The logarithmic divisors of degree zero form a subgroup ofD_F denoted by

D_F = {d∈ D_F|deg_F d = 0}.

The image of the mapdiv_F defined via the set of log- arithmic valuations from the principal id`ele subgroup

RF = Z⊗ZF^×

ofJF to D_F is a subgroup denoted byP_F, which will be referred to as the subgroup of principal logarithmic divisors. The quotient

C_F = D_F/P_F

is, by definition, the-group of logarithmic classesof F.

And the kernel

EF = RF ∩UF

of the morphismdiv_F from RF in D_F is the group of globallogarithmic units.

2.2 Logarithmic Ramification and-adic Degrees Next we review the basic notions of the logarithmic ram- ification, which mimic, as a rule, the classical ones.

LetL/F be any finite extension of number fields. Let pbe a prime number. Denote by Q^cp the cyclotomic Z- extensions of Qp, that is to say the compositum of all cyclotomic Zq-extensions of Qp on all prime numbersq.

Let p be a prime of F above (p) and P a prime of L abovep. The logarithmic ramification (respectively iner- tia) index e(L_P/F_p) (respectively f(L_P/F_p)) is defined to be the relative degree

e(L_P/F_p) = [L_P:L_P∩Q^cpF_p] (respectively f(L_P/F_p) = [L_P∩Q^c_pF_p:F_p]).

As a consequence, L/F is logarithmically unramified at P, that is to say e(L_P/F_p) = 1, if and only if L_P is contained in the cyclotomic extension of F_p. Moreover, for any q = pthe classical and the logarithmic indexes have the sameq-part (see Proposition 3.2). Hence they are equal as soon asp[F_p:Qp].

As usual, in the special caseL/F =K/Q, the absolute logarithmic indexes of a finite placepofKover the prime

pare just denoted bye_p and f_p. With these notations, the-adic degree of pis defined by the formula:

deg_Kp=f_pdegp with

degp=







Logp forp=; forp== 2;

4 forp== 2.

The extension and norm maps between groups of divi- sors, denoted by ι_L/F and N_L/F respectively, have their logarithmic counterparts, ι_L/F and N_L/F respectively.

To be more explicit,ι_L/F is defined on every finite place pofF by

ι_L/F(p) =

P|p

e_LP/FpP,

whileN_L/F is defined on allPlying abovep by N_L/F(P) =f_LP/Fp p.

These applications are compatible with the usual exten- sion and norm maps defined betweenRL andRF, in the sense that they sit inside the commutative diagrams.

RL divL

−−−−→ DL deg_L

−−−−→ Z



^NL/F ^NL/F and RF

div_F

−−−−→ DF deg_F

−−−−→ Z

RL div_L

−−−−→ DL deg_L

−−−−→ Z



^ιL/F ^ιL/F ^[L:F]

RF div_F

−−−−→ DF deg_F

−−−−→ Z

When L/F is a Galois extension with Galois group Gal(L/F), one deduces from the very definitions the un- surprising and obvious properties:

N_L/F◦ι_L/F = [L:F] and ι_L/F ◦N_L/F =

σ∈Gal(L/F)

σ.

2.3 Ideal Theoretic Description of Logarithmic Classes By the weak density theorem every class in JF/UFRF

may be represented by an id`ele with trivial components at the -adic places, that is to say that every class in DF/PF comes from a-divisord=

p α_p p.

The canonical map fromRF toD_F mapsa∈ RF to divF(a) =

pv_p(a)p. Now for each finite placep, the

quotient e_p/e_p =f_p/f_p of the classical and logarithmi- cal indexes associated with p is a -adic unit (Proposi- tion 3.2), say λ_p (which is 1 for almost all p), and one has the identity,

v_p=λ_pv_p

between the logarithmic and the classical valuations. So every-divisord comes from a-idealaby the formula

a=

p

p^αp →d_F(a) =

p

λ_p α_p p.

This gives the following ideal theoretic description of logarithmic classes.

Definition and Proposition 2.1. Let IdF ={a=

p

p^αp}

be the group of -ideals,

IdF ={a∈ IdF|deg_Fd_F(a) = 0}

be the subgroup of-ideals of degree 0, and PrF ={

p

p^vp(a)|v_p(a) = 0∀p|}

the subgroup of principal -ideals generated by principal id`eles a having logarithmic valuations 0 at every -adic place. Then one has

CF IdF/PrF.

Proof: As explained above, the surjectivity follows from the weak approximation theorem. So let us consider the kernel of the canonical map φ_F : Id_F →C_F. Clearly, we have kerφF = {a ∈ IdF | ∃a ∈ RF d_F(a) = divF(a)}. The conditiond_F(a) =divF(a) with a∈IdF

impliesv_p(a) = 0∀p|; and thus (a)∈Pr_F as expected.

The generalized Gross conjecture (for the fieldF and the prime) asserts that the logarithmic class groupC_F is finite (cf. [Jaulent 94]). This conjecture, which is a consequence of the p-adic Schanuel conjecture was only proved in the abelian case and a few others (cf. [Federer and Gross 81, Jaulent 02b]). Nevertheless, since CF is a Z-module of finite type (by the-adic class field the- ory), the Gross conjecture just claims the existence of an integermsuch that^m kills the logarithmic class group.

In practice it is rather easy to compute such an exponent

m (when the classical invariants of the number field are known); this gives rise to a more suitable description of CF in order to carry out numerical computations.

Proposition 2.2.Assume the integermto be large enough such that the logarithmic class group C_F is annihilated by ^m. Thus introduce the group

Id⁽

m)

F ={a∈ Id_F|deg_Fd_F(a)∈^mdeg_FD_F}

=IdF Id_F^m. Thus, denoting Pr⁽

m)

F = PrF Id_F^m, one has: CF Id⁽

m) F /Pr⁽

m) F .

Proof: The hypothesis gives Id_F^m ⊂ Pr_F and by a straightforward calculation we have

Id⁽

m)

F /Pr⁽_F^m)=IdFId^m/PrFId^m IdF/(IdF∩PrFId^m) IdF/Pr_FId_F^m

=IdF/PrF CF.

Remark 2.3.A lower bound formwhich will be required for a sufficient precision of thep-adic calculations will be given after Lemma 3.9.

3. THE ALGORITHMS

Throughout this section a finite abelian group Gis pre- sented by a column vector g ∈G^m, whose entries form a system of generators for G, and by a matrix of re- lations M ∈ Z^n×m of rank m, such that v^Tg = 0 for v∈Z^mif and only ifv^T is an integral linear combination of the rows of M. We note that for everya ∈ G there is a v ∈ Z^m satisfyinga= v^Tg. If g₁, . . . , g_m is a basis of G, M is usually a diagonal matrix. Algorithms for calculations with finite abelian groups can be found in [Cohen 00]. If Gis a multiplicative abelian group, then v^Tgis an abbreviation forg^v₁¹· · ·g_m^vm.

One of the steps in the computation of the logarithmic class group is the computation of the ideal class group of a number field. Algorithms for this can be found in [Cohen 93, Hess 96, Pohst and Zassenhaus 89]. One tool used in these algorithms is thes-units, which we will also use directly in our algorithm.

Definition 3.1. (s-units.) Letsbe an ideal of a number fieldF. We call the group

α∈F^×|v_p(α) = 0 for allps

thes-units of F.

For this section let F be a fixed number field. We denote the ideal class group ofF byC=CF. We also writeCforCF,D forDF, and so on.

3.1 Computingdeg_F(p)andv_p(·)

We describe how invariants of the logarithmic objects can be computed. Some of the tools presented here also are applied directly in the computation of the logarithmic class group.

Definition and Proposition 3.2.Letpbe a prime number.

LetF be a number field. Letp be a prime ideal ofF over p. Fora∈Q^×_p ∼=p^Z×F^×_p ×(1 + 2pZp)denote byathe projection of a to (1 + 2pZp). Let F_p be the completion ofF with respect to p. Forα∈F define

h_p(α) := Log_pN_Fp/Qp(α) [F_p:Qp]·deg_pp.

The p-part of the logarithmic ramification index e_p is [h_p(F_p^×) : Zp]. For all primes q with q = p the q-part ofe_p is theq-part of the ramification index e_p ofp.

For a proof see [Jaulent 94].

In Section 2.2 we have seen that the degree deg_F(p) of a placepcan be computed as deg_F(p) =f_pdegp. From Section 2.3 we know thate_pf_p=e_pf_p. We have

v_p(x) =−Log(NF_p/Qp(x)) deg_F(p) .

Thus we can concentrate on the computation of e_p for which we need the completionF_pofFatpand generators of the unit groupF_p^×.

The Round Four Algorithm was originally conceived as an algorithm for computing integral bases of num- ber fields. It can be applied in three different ways in the computation of logarithmic classgroups. Firstly, it is used for factoring ideals over number fields; secondly, it returns generating polynomials of completions of number fields; and thirdly, it can be used for determining integral bases of maximal orders.

Let Φ(x) be a monic, squarefree polynomial overZp. The algorithm for factoring polynomials over local fields as described in [Pauli 01] returns:

• a factorization Φ(x) = Φ₁(x)·· · ··Φ_s(x) of Φ(x) into irreducible factors Φi(x) (1≤i≤s) overZp,

• the inertia degreese_i and ramification indexes f_i of the extensions ofQp given by the Φi(x) (1≤i≤s), and

• two element certificates (Γi(x),Πi(x)) with Γ_i(x),Π_i(x) ∈ F[x] such that v_i

Π_i(α_i)

= 1/e_i and [Fp(Γi(αi)) : Fp] = fi where αi is a root of Φ_i(x) inF[x]/(Φ_i(x)), andv_i is an extension of the exponential valuation vp of Qp to Qp[x]/(Φi(x)) withvi|_Qp=vp.

The factorization algorithm in [Ford et al. 02] returns the certificates combined in one polynomial for each ir- reducible factor. The data returned by these algorithms can be applied in several ways.

• An integral basis of the extension of Qp generated by a root αi of Φi(x) is given by the elements Γ_i(α_i)^hΠ_i(α_i)^j with 0 ≤ h ≤ f_i and 0 ≤ j ≤ e_i. The local integral bases can be combined to a global integral basis for the extension of Q generated by Φ(x).

• For the computation ofv_p we need to compute the norm of an element in the completions of F. The completions ofF are given by the irreducible factors of the generating polynomial ofF overQ.

Lemma 3.3. (Ideal Factorization.) Let Φ(x) ∈ Zp[x]

be irreducible over Q. Let Φ1(x), . . . ,Φs(x) ∈ Zp[x] be the irreducible factors of Φ(x) with two element certifi- cates (Γ_i(x),Π_i(x)). Denote by e_i the ramification in- dexes of the extensions ofQpgiven by theΦi(x) (1≤i≤ s). The Chinese Remainder Theorem gives polynomials Θ1(x), . . . ,Θs(x)∈Qp[x]with

Θ_i(x) ≡ Π_i(x) mod Φ_i(x), Θ_i(x) ≡ 1 mod

j=iΦ_j(x).

LetL:=Q(α)whereαis a root ofΦ(x)in C. Then (p) =

p,Θ₁(α)e₁

· · · · ·

p,Θ_s(α)e_s

is a factorization of(p)into prime ideals.

In order to compute [h_p(F_p^×) : Zp] it is sufficient to compute the image of a set of generators of F_p^×. Algo- rithms for this task were recently developed with respect to the computation of ray class groups of number fields

and function fields [Cohen 00, Hess et al. 03], also see [Hasse 80, Chapter 15].

Proposition 3.4.F_p^× ∼=π^Z×(Op/p)^××(1 +p).

Letp be the prime ideal over the prime number pin O_p. Let e_p be the ramification index andf_p the inertia degree ofp. We define the set of fundamental levels

Fe:=

ν |0< ν <_p−1^pep, pν

and let ε ∈ O_p^× such that p = −π^eε. Furthermore we define the map

h₂:a+p−→a^p−εa+p.

Theorem 3.5. (Basis of(1 +p).) Let ω1, . . . , ωf ∈ O_p be a fixed set of representatives of aFp-basis of Op/p. If (p−1) does not divide e orh2 is an isomorphism, then the elements

1 +ωiπ^ν whereν ∈ Fe,1≤i≤f are a basis of the group of principal units 1 +p.

Theorem 3.6. (Generators of (1 +p).) Assume that (p−1) | e and h₂ is not an isomorphism. Choose e₀ andµ0 such that pdoes not dividee0 and such thate= p^µ0−1(p−1)e₀. Let ω₁, . . . , ω_f ∈ Op be a fixed set of representatives of a Fp-basis of O_p/p subject to ω₁^pµ0 − εω₁^pµ0−1 ≡0 modp. Chooseω_∗∈ Op such thatx^p−εx≡ ω_∗modp has no solution. Then the group of principal units1 +p is generated by

1 +ω_∗π^pµ0e0 and1 +ωiπ^ν whereν ∈ Fe,1≤i≤f.

3.2 Computing a Bound for the Exponent ofC Let F be a number field and a prime number. Let C=CF ∼=Id/ Prbe the-group of logarithmic divisor classes. Letp₁, . . . ,p_sbe the-adic places ofF.

We describe an algorithm which returns an upper bound ^m of the exponent of C (see Proposition 2.2).

We denote by

• C() the group of logarithmic divisor classes of degree zero:

C() :=

[a]∈C

a=s

i=1aip_i with deg_F(a) = 0

,

• C the-group of the-ideal classes,i.e., the-part ofC/[p1], . . . ,[ps].

Remark 3.7. If () =p^e where p is a prime ideal of OK

then the group C() is trivial.

Lemma 3.8. [Diaz y Diaz and Soriano 99]Let θ:C−→ C,

pm_pp−→

pp^(1/λp)mp.

The sequence

0−→C()−→C−→ C^θ −→Cokerθ−→0 is exact.

Proof: Recall that, if p , v_p = λ_pv_p. Denote by p₁, . . . ,p_s the-adic places ofF. Let

a=

q

a_qq

=div(α)

=

p

v_p(α)p

=

p

λ_pv_p(α)p+ s i=1

v_pi(α)pi

be a principal logarithmic divisor. A representative of the image ofa underθ in terms of ideals is of the form

a=

q()

q^vq(α)= (αOK)× s i=1

p⁻_i^vpi(α).

This shows that the homomorphismθ is well defined. It follows immediately that Kerθ=C().

Lemma 3.9. Set^m = expC and^m = expC(). Then ^m+ma≡0 modP for alla∈D.

Proof: It follows from the exact sequence in Lemma 3.8 that for all a∈D the congruence^mθ(a)≡1 holds in C. Thus^ma∈Kerθ=C() and^m+ma≡0 modP.

Lemma 3.9 suggests setting the precision for the com- putation ofCtom:=m+m -adic digits. If the ideal class groupCis known we can easily computem. In or- der to findm we compute a matrix of relations forC().

Lemma 3.10. (Generators and Relations of C().) Let p₁, . . . ,p_s be the -adic places of F. Assume that s > 1. Reorder the p_i such that v(deg(p1)) =

min_1≤i≤sv(deg(p_i)). Let γ₁, . . . , γ_r be a basis of the - units of F. Then the group C() is given by the gener- ators[g_i] :=

p_i−_deg(^deg(p_p1ⁱ⁾₎p₁

(i= 2, . . . , s)with relations s

i=2v_pi(γ_j)[g_i] = [0].

Proof: We consider a logarithmic divisora =_s

i=1a_ip_i of degree zero over F that is constructed from the - adic places. By the choice of p₁ and as deg(a) = deg(s

i=1aip_i) =s

i=1aideg(pi) = 0 the coefficient a1

is given by the other s−1 coefficients. Thus the [gi] generateC().

The relations between the classes of C() are of the form_s

i=2b_i[g_i] = [0]. That is, there existsβ ∈ RF such

that s

i=2

big_i= s j=1

ajp_j=div(β),

withv_q(β) = 0 for allq(). Thusβis an element of the group of-units{α∈ RF |v_q(α) = 0}ofRF. Hence we obtain the relations given above.

A version of this lemma for the case thatF is Galois can be found in [Diaz y Diaz and Soriano 99].

Algorithm 3.11. (Precision.)

Input: a number field F and a prime number , the-adic placesp₁, . . . ,p_sofF, and a basis γ1, . . . , γr of the-units ofF.

Output: an upper bound for the exponent ofC. Set^m ←expC, setm←max{m,4}.

Ifs= 1 then return^m. [Remark 3.7]

Repeat

Setm←m+ 2

Set [Lemma 3.10]

A←





v_p2(γ1) . . . v_ps(γ1) ... . .. ...

v_p2(γr) . . . v_ps(γr)



mod^m.

LetHbe the Hermite normal form ofAmodulo ^m.

Until rank(H) =s−1.

Let S = (Si,j)i,j be the Smith normal form of A modulo^m.

Setm ←max1≤i≤s−1

v(Si,i)

, return^m+m.

Remark 3.12.In general, Algorithm 3.11 does not termi- nate if Gross’s conjecture is false.

3.3 ComputingC

We use the ideal theoretic description from Section 2.3 for the computation of C ∼= Id/ Pr. In the previous section we have seen how we can compute a bound for the exponent ofC. It is clear that this bound also gives a lower bound for the precision in our calculations.

Theorem 3.13. (Generators of C.) Let a₁, . . . ,a_t be a basis of the ideal classgroup ofF with gcd(a_i, ) = 1 for all 1 ≤i ≤ t. Denote by p₁, . . . ,p_s the -adic places of F. Letα₁, . . . , α_s be elements of RF withv_pi(α_j) =δ_i,j (i, j = 1, . . . , s) and gcd((αi), ) = 1 for all 1 ≤ i ≤ s.

Seta_t+i:= (α_i)for1≤i≤s. For an idealaofF denote by a the projection of a from

pp^Z to

p()p^Z. We distinguish two cases:

(i) Ifdeg(a_i) = 0for all1≤i≤t+sthen setb_i:=a_i. The group CF is generated by b₁, . . . ,b_t+s.

(ii) Otherwise let1≤j ≤t+ssuch thatv(deg(a_j)) = min1≤i≤t+sv(deg(ai)). Set b_i := a_i/a^d_j with d ≡

deg(ai)

deg(aj) mod^m where ^m > exp(C). The group CF is generated byb₁, . . . ,b_j−1,b_j+1, . . . ,b_t+s.

Proof: Leta∈Id. There exist γ∈ RF and a1, . . . , at∈ Z such that a = t

i=1a^a_iⁱ ·(γ). Set g_i := v_pi(γ) for 1≤i≤s. Now

a=_s

i=1a^a_iⁱ·

(γ)·_s

j=1(α_i)^−gi

·_s

j=1(α_i)^gi . By the definition ofId(Definition and Proposition 2.1) we have

a=a=t

i=1a^a_iⁱ·

(γ)·s

j=1(α_j)^−gj

·s

j=1(α_j)^gj . Asv_pi

(γ)·s

j=1(αj)^−gj

= 0 fori= 1, . . . , swe obtain a≡t

i=1a^a_iⁱ·s

j=1(αj)^gj

modPr.

Thus all elements of C can be represented by a₁, . . . ,a_t,a_t+1 = (α₁), . . . ,a_t+s = (α_s). For the two cases we obtain:

(i) It follows immediately that b₁, . . . ,b_t+sare genera- tors ofC.

(ii) If we have a ≡ a^a₁¹ · · · · · a^a_t+s^t+smodPr for an ideal a ∈ Id then 0 = deg(a) = t+s

i=1aideg(ai).

Thus −aj = _s

i=ja_ideg(a_i)/deg(a_j). Hence, b₁, . . . ,b_j−1,b_j+1, . . . ,b_t+sare generators ofC.

We continue to use the notation from Theorem 3.13.

SetC:=C/p₁, . . . ,p_s.

Remark 3.14. The definition of C in this section and the previous section, where we considered the -part of C/p₁, . . . ,p_s, differ. The definition we chose here makes the description of the algorithm easier. In the al- gorithm we make sure that only the -part of the group appears in the result by computing the -adic Hermite normal form of the relation matrix.

The relations between the generators a₁, . . . ,a_t of the group C are of the form t

i=1a^a_iⁱ = (α) with α ∈ RF. There exist integers c1, . . . , cn such that (α) ≡ _s

i=1(α_i)^cimodPr. This yields the relation t

i=1a^a_iⁱ ≡ s

i=1(α_i)^ci modPr in C. We can derive all relations involving the generators a_i+Prfrom their relations as generators of the groupC in this way.

The other relations between the generators of C are obtained as follows. A relation between the generatorsαi

is of the form _s

i=1(αi)^vi ≡(1) modPr or equivalently s

i=1(αi)^vi·s

i=1p^w_iⁱ = (α) for someα∈ RF. The last equality is fulfilled if and only if_s

i=1p^w_iⁱis principal,i.e., ifs

i=1p^w_iⁱ is an ()-unit. Assume thats

i=1p^w_iⁱ = (γ) for some γ ∈ RF. As v_pj(α) = 0 for all (α) ∈ Pr and p_j|() the equationv_pjs

i=1α^v_iⁱ·γ

= 0 must hold. By the definition ofβ_iwe obtainv_i=−v_pi(γ) for 1≤i≤s.

Corollary 3.15. (Relations ofC.) Let (a₁, . . . ,a_t),(a_i,j)i,j∈{1,...,t}

be a basis and a relation matrix ofC :=C/p₁, . . . ,p_s. Let a_t+1 = (α1), . . . ,a_t+s = (αs) be as above. For each 1 ≤ k ≤ t we find ck,2, . . . , ck,s such that _t

i=1b^a_i^k,i = _s

i=2(αi)^ck,i. Letγ1, . . . , γr be a basis of the()-units of RF. Setv_i,j:=v_pj(γ_i) (1≤i≤r,2≤j≤s). Set

M :=













b_1,1 . . . b_1,t −c_1,2 . . . −c_1,s ... . .. ... ... . .. ... b_t,1 . . . b_t,t −c_t,2 . . . −c_t,s

0 . . . 0 v_1,2 . . . v_1,s ... . .. ... ... . .. ... 0 . . . 0 vr,2 . . . vr,s











 .

For the two cases we obtain:

(i) ((b1, . . .b_t+s), M)are generators and relations ofC.

(ii) Let j be chosen as in Theorem 3.13. Denote by N the matrix obtained by removing thejth column from

F C Gal () C ^m C Q(√

−521951) [1024] S(2) 2 p₁p₂ [4] 8 [2,4]

Q(i,√

11) [1] E(4) 5 p₁· · ·p₄ [1] 5 [5]

Q(i,√

78) [2,2] E(4) 2 p⁴₁ [2] 2 [1]

Q(i,√

455) [2,2,10] E(4) 2 p²₁p²₂ [2,2] 512 [2,512]

Q(i,√

1173) [2,2,6] E(4) 2 p²₁ [2,2,2] 2 [2,2,2]

Q(i,√

1227) [4,4] E(4) 613 p₁· · ·p₄ [4,4] 613 [613]

Q(α) [14] D(4) 2 p²₁p²₂ [1] 1 [1]

χα(x) =x⁴+ 13x²−12x+ 52 3 p²₁p²₂ [1] 3 [3]

7 p₁ [14] 7 [7]

Q(√

1234577,√

−3) [273] E(4) 2 p₁p₂ [273] 4 [4,4]

3 p²₁ [273] 3 [3]

13 p₁p₂ [273] 169 [13,13]

Q(ζ3,√

303) [14] E(4) 2 p²₁ [14] 2 [2]

3 p²₁p²₂ [1] 9 [9]

7 p₁· · ·p₄ [1] 1 [1]

Q(β) [2,6,6] S(5) 2 p₁p₂ [2,2,6] 2 [2,2,2]

χβ(x) =x⁵+2x⁴+18x³+34x²+17x+3¹⁰ 3 p₁· · ·p₄ [6] 3 [3]

Q(ζ5,√

5029) [15,150] [2,4] 2 p₁p₂ [3,150] 4 [2,2]

3 p₁p₂ [15,150] 3 [3,3]

5 p₁p₂ [3,150] 25 [5,25]

Q(i,√ 11,√

−499) [3,105] E(8) 5 p₁· · ·p₈ [3] 25 [5,5,25]

Q(i,√

11, γ) [2,2,2,6] S(3)× 2 p²₁ [2,2,2,6] 2 [2,2,2,2]

χγ(x) =x³+ 3x²+ 2x+ 125 E(4) 3 p₁p₂ [2,2,2,6] 9 [3,3]

5 p₁· · ·p₁₂[2] 5 [5,5]

TABLE 1.

M. Then((b₁, . . . ,b_j−1,b_j+1, . . . ,b_t+s), N)are gen- erators and relations ofC.

Now we only need to find the elementsα1, . . . , αswith

v_pi(α_j) =δ_i,j. Letη_i,1, . . . , η_i,ribe a system of generators ofO_p^× for 1≤i≤s. Let

M :=















v_p1(η_1,1) . . . v_ps(η_1,1) ... . .. ...

v_p1(η_1,r1) . . . v_ps(η_1,r1) ... ... ...

v_p1(ηs,1) . . . v_ps(ηs,1) ... . .. ...

v_p1(ηs,r_s) . . . v_ps(ηs,r_s)













 .

Let S = LM R be the -adic Smith normal form of M with transformation matricesL and R. Application of the left transformation matrix L to the generators η1,1, . . . , ηs,r_s yields elementsα1, . . . , αswith the desired properties.

Algorithm 3.16. (Logarithmic Classgroup.)

Input: a number fieldF and a prime number. Output: generators g and and a relation matrix H

forCl_F.

Determine a bound^mfor the exponent ofClF and use it as the precision for the rest of the algorithm.

[Algorithm 3.11]

Compute generators a₁, . . . ,a_t ofC =C/p₁, . . . , p_s, where p₁, . . . ,p_sare the ideals ofF over.

Determine a_t+1 = (α₁), . . . ,a_t+s = (α_s) with

v_pi(αj) =δi,j.

Compute generators g := (b₁, . . . ,b_t+s)^T with deg(bi) = 0 froma₁, . . . ,a_t+s. [Theorem 3.13]

Compute a relation matrix M between the genera-

torsg. [Corollary 3.15]

In case (ii) remove the jth column fromM and the jth generator fromg.

Compute the-adic Hermite normal formH ofM. Return (g, H).

4. EXAMPLES

All methods presented here have been implemented in the computer algebra system Magma [Canon et al. 03].

We recomputed the logarithmic class groups from [Diaz y Diaz and Soriano 99, Section 6] with our new al- gorithm. Our results differ in one example. For the field F=Q(i,√

1173) and= 2 we obtainC_F ∼=C₂×C₂×C₂ instead ofCF ∼=C2×C2×C2×C2. AsF contains the 4th roots of unity, the 2-rank of the wild kernel ofF is 3.

Table 1 contains examples of logarithmic -class groupsCof selected number fieldsF together with their class groupsC, Galois groups Gal, and the factorization of the ideals (). χα(x) denotes the minimal polynomial of α and i denotes a root of x²+ 1. The class groups are presented as a list of the orders of their cyclic fac- tors,C =C/p₁, . . . ,p_s, and ^m is the bound for the exponent ofCas obtained by Algorithm 3.11.

The logarithmic 2-class group of Q(i,√

78) is an ex- ample of the fact that the cokernel ofθ in the exact se- quence in Lemma 3.8 is not trivial in general. Indeed one can show [Dubois and Soriano-Gafiuk 04] that for F=Q(i,√

d) withd= 2 and dsquarefree Coker(θ)∼=

C2 ifd≡ ±2 mod 16, C1 otherwise.

REFERENCES

[Canon et al. 03] J. J. Canon et al. “The Computer Alge- bra System Magma.” Available from World Wide Web (http://magma.maths.usyd.edu.au/magma/), 2003.

[Cohen 93] H. Cohen.A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.

[Cohen 00] H. Cohen. Advanced Topics in Computational Number Theory. New York: Springer-Verlag, 2000.

[Diaz y Diaz and Soriano 99] F. Diaz y Diaz and F. Soriano.

“Approche algorithmique du groupe des classes logarith- miques.”J. Number Theory76 (1999), 1–15.

[Dubois and Soriano-Gafiuk 04] I. Dubois and F. Soriano- Gafiuk. “Un nouveau re´gulateur de type Gross.” Abh.

Math. Sem. Univ. Hamburg74 (2004), 1–11.

[Federer and Gross 81] L. J. Federer and B. H. Gross (with an appendix by W. Sinnot). “Regulators and Iwasawa Modules.”Invent. Math.62 (1981), 443–457.

[Ford et al. 02] D. Ford, S. Pauli, and X. -F. Roblot. “A Fast Algorithm for Polynomial Factorization Over Qp.” J.

Th´eor. Nombres Bordeaux14 (2002), 151–170.

[Gras 03] G. Gras.Class Field Theory, Springer Monographs in Mathematics. New York: Springer-Verlag, 2003.

[Hasse 80] H. Hasse. Number Theory. Berlin: Springer Ver- lag, 1980.

[Hess 96] F. Hess. “Zur Klassengruppenberechnung in algebraischen Zahlk¨orpern.” Available from World Wide Web (http://www.math.TU-Berlin.DE/∼kant/

publications/diplom/hess.ps.gz), 1996.

[Hess et al. 03] F. Hess, S. Pauli, and M. E. Pohst. “Comput- ing the Multiplicative Group of Residue Class Rings.”

Mathematics of Computation72 (2003), 1531–1548.

[Jaulent 94] J. -F. Jaulent. “Classes logarithmiques des corps de nombres.”J. Th´eor. Nombres Bordeaux6 (1994), 301–

325.

[Jaulent 98] J. -F. Jaulent. “Th´eorie -adique du corps de classes.” J. Th´eor. Nombres Bordeaux 10 (1998), 355–

397.

[Jaulent 00] J. -F. Jaulent. “Classes logarithmiques sign´ees des corps de nombres.”J. Th´eor. Nombres Bordeaux12 (2000), 455–474.

[Jaulent 02a] J. -F. Jaulent. “Corrigendum `a classes logarith- miques sign´ees des corps de nombres.”J. Th´eor. Nom- bres Bordeaux14 (2002), 1–5.

[Jaulent 02b] J. -F. Jaulent. “Classes logarithmiques des corps totalement r´eels.” Acta Arithmetica 103 (2002), 1–7.

[Jaulent and Soriano 01] J. -F. Jaulent and F. Soriano. “Sur le noyau sauvage des corps de nombres et le groupe des classes logarithmiques.”Math. Z.238 (2001), 335–354.

[Jaulent and Soriano-Gafiuk 04] J. -F. Jaulent and F.

Soriano-Gafiuk. “2-groupe des classes positives d’un corps de nombres et noyau sauvage de la K-Th´eorie.”J.

Number Theory108 (2004), 187–208.

[Pauli 01] S. Pauli. “Factoring Polynomials over Local Fields.”J. Symb. Comp.32 (2001), 533–547.

[Pohst and Zassenhaus 89] M. E. Pohst and H. Zassenhaus.

Algorithmic Algebraic Number Theory. Cambridge, UK:

Cambridge University Press, 1989.

[Soriano 00] F. Soriano. “Sur le noyau hilbertien d’un corps de nombres.”C. R. Acad. Sci., S´erie I330 (2000), 863–

866.

Francisco Diaz y Diaz, Universit´e Bordeaux I, Laboratoire A2X, 351 Cours de la Lib´eration, 33405 Talence Cedex, France ([email protected])

Jean-Fran¸cois Jaulent, Universit´e Bordeaux I, Institut des Math´ematiques de Bordeaux, 351 Cours de la Lib´eration, 33405 Talence Cedex, France ([email protected])

Florence Soriano-Gafiuk, Universit´e de Metz, D´epartement de Math´ematiques, Ile du Saulcy, 57045 Metz, France ([email protected])

Sebastian Pauli, Technische Universit¨at Berlin, Institut f¨ur Mathematik - MA 8-1, Straße des 17. Juni 136, 10623 Berlin, Germany ([email protected])

Michael E. Pohst, Technische Universit¨at Berlin, Institut f¨ur Mathematik - MA 8-1, Straße des 17. Juni 136, 10623 Berlin, Germany ([email protected])

Received December 23, 2003; accepted August 18, 2004.