The logarithmic class group package in PARI/GP^{∗}

Karim Belabas and Jean-François Jaulent

Abstract. This note presents our implementation in the PARI/GP system of the various arithmetic invariants attached to logarithmic classes and units of number fields. Our algorithms simplify and improve on works of Diaz y Diaz, Pauli, Pohst, Soriano and the second author.

Résumé. (Le groupe des classes logarithmiques dans PARI/GP) Cette note présente notre implantation dans le système PARI/GP du calcul des invariants arithmétiques liés aux classes et unités logarithmiques des corps de nombres. Nos algorithmes prolongent et simplifient ceux introduits par Diaz y Diaz, Pauli, Pohst, Soriano et le second auteur.

Contents

1 Introduction 2

2 Algorithmic preliminaries 4 2.1 The Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Computational algebraic number theory . . . . . . . . . . . . . . . . . . 5 2.3 Local norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 The main algorithm 6 3.1 Computing ẽ(𝔭/p), f̃(𝔭/p) and ṽ_{𝔭}(·) . . . . . . . . . . . . . . . . . . . . 7 3.2 The group Cl′ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 The group C̃l(ℓ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4 The logarithmic class group . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 The bnflog package 12 4.1 The PARI/GP interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

∗Pub. Math. Besançon 2016, 5–18.

1 Introduction

Classically the class group and unit group of a number field F are defined using the canonical factorization of principal fractional ideals into prime ideals of the ring of integers ℤ_{F}:

(x) = ∏_{𝔭} 𝔭^{v_{𝔭}(x)}, x ∈ F^{×} .

The family of valuations (v_{𝔭})_{𝔭} determines a natural morphism from the multiplicative groupe F^{×} into the free abelian group generated by the prime ideals I_{F} = ⊕_{𝔭} ℤ 𝔭 whose kernel and cokernel are respectively the units E_{F} = ℤ_{F}^{×} and the ideal class group Cl_{F} attached to F; this yields the standard exact sequence

1 −−⟶ E_{F} −−⟶ F^{×} −−⟶^{div} I_{F} = ⊕_{𝔭} ℤ 𝔭 −−⟶ Cl_{F} −−⟶ 1,

where div(x) = (v_{𝔭}(x))_{𝔭}. Geometry of numbers then shows on the one hand that the ideal class group is finite and on the other hand that the unit group E_{F} is the direct product of the cyclic subgroup μ_{F} of roots of unity contained in F and a free ℤ-module of rank r_{F} +c_{F} −1, where r_{F} are c_{F} denote respectively the number of real and complex places of F.

The logarithmic class group and units are defined in an analogous way, by replacing the classical valuations (v_{𝔭})_{𝔭} by an ad hoc familly (ṽ_{𝔭})_{𝔭} taking other arithmetic parameters into account. Before introducing them, let us fix an arbitrary prime number ℓ and tensor the above sequence by ℤ_{ℓ}, which is flat over ℤ:

1 −−⟶ ℤ_{ℓ} ⊗_{ℤ} E_{F} −−⟶ ℤ_{ℓ} ⊗_{ℤ} F^{×} −−⟶^{div} ⊕_{𝔭} ℤ_{ℓ}𝔭 −−⟶ ℤ_{ℓ} ⊗_{ℤ} Cl_{F} −−⟶ 1,

where ℤ_{ℓ} ⊗_{ℤ} Cl_{F} is nothing else than the ℓ-Sylow subgroup of the class group and the kernel ℤ_{ℓ} ⊗ E_{F} is the direct product of the ℓ-group μ_{F}^{(ℓ)} of ℓ-primary roots of unity in F and a free ℤ_{ℓ}-module of rank r_{F} + c_{F} − 1.

We now define the ℓ-adic logarithmic valuations by keeping the ordinary definition ṽ_{𝔭} = v_{𝔭} at places 𝔭 ∤ ℓ, but we modify them at places 𝔭 above ℓ [16]:

ṽ_{𝔭}(x) = −\frac{Log_{ℓ}(N_{K_{𝔭}/ℚ_{ℓ}} (x))}{deg𝔭} ,

where Log_{ℓ} is the Iwasawa logarithm, N_{K_{𝔭}/ℚ_{ℓ}} is the norm operator attached to the local field extension K_{𝔭}/ℚ_{ℓ} and deg𝔭 is a normalization factor chosen so as to yield the local Hilbert symbol [14]:

( \frac{ζ, x}{𝔭}) = ζ^{_{v_{𝔭}}(x)}

for ζ ∈ μ_{F}^{(ℓ)} and x ∈ F^{×} , for all finite places 𝔭 of F. (We shall give an explicit definition for deg𝔭 in the next section together with an algorithm to approximate it.) We finally replace in the last exact sequence the classical valuations v_{𝔭} and the div map by a new d̃iv = (ṽ_{𝔭})_{𝔭}, thereby defining the group of logarithmic units Ẽ_{F} and the logarithmic class group C̃l_{F} for the prime ℓ:

1 −−⟶ Ẽ_{F} −−⟶ ℤ_{ℓ} ⊗_{ℤ} F^{×} \underrightarrow{_{div}} ⊕_{𝔭} ℤ_{ℓ}𝔭 −−⟶ C̃l_{F} −−⟶ 1.

Just as the image P_{F} = div(F^{×} ) in I_{F} yields the subgroup of principal ideals, the image P_{F} of d̃iv defines the subgroup of principal logarithmic divisors.

At this point appears an essential difference compared to the classical case, akin to what happens in the function field case: if we define the degree of a logarithmic divisor 𝔡 = ∑ _{𝔭} α_{𝔭}𝔭 in ⊕_{𝔭} ℤ_{ℓ}𝔭 additively,

deg( ∑_{𝔭} α_{𝔭} 𝔭) = ∑_{𝔭} α_{𝔭} deg𝔭,

then the product formula for absolute values shows that principal logarithmic divisors have degree 0; in other words,

P_{F} ⊂ {𝔡 ∈ ⊕_{𝔭} ℤ_{ℓ}𝔭: deg𝔡 = 0 }.

It is then natural to consider the quotient group, i.e. the subgroup C̃l_{F}^{0} ⊂ C̃l_{F} formed by the classes of degree 0.

By ℓ-adic class field theory (cf. [15, 8]), the group C̃l_{F}^{0} appears as a canonical quotient of a standard Iwasawa module and the group of logarithmic units Ẽ_{F} as the subgroup of norms in the cyclotomic ℤ_{ℓ}-extension of F. It would follow from a conjecture of Kuz’min (also known as “generalized Gross conjecture”) that the group C̃l_{F}^{0} is finite, or equivalently that the group Ẽ_{F} of logarithmic units is the direct product of the cyclic ℓ-groupe μ_{F}^{(ℓ)} and a free ℤ_{ℓ}-module of rank r_{F} + c_{F}; and the Gross-Kuz’min conjecture is equivalent to these statements. The Baker-Brumer independence theorem shows that those assertions are true when the number field F is abelian over ℚ. More generally, they hold when there exist a subfield K of F, abelian over ℚ, such that there is a single place 𝔭_{F} of F above each ℓ-adic place 𝔭_{K} of K, see [10].

Moreover, as suggested by the explicit expression of the Hilbert symbol above, the group C̃l_{F}^{0} is closely related to the wild kernels of K-theory. Precisely, if s ⩾ 1 is such that the field F contains the 2ℓ^{s}-th roots of unity, then the finite group WK_{2}(F) and the quotient C̃l_{F}^{0} ⊗_{ℤ} ℤ/ℓ^{s}ℤ have the same ℓ^{s}-rank (cf. [19]). A similar result holds for the higher étale kernels WK_{2i}(K), i ⩾ 1 (cf. [17]).

Last, as for ideals, transition morphisms (norm and extension) attached to a number field extension K/F lead to the definition of logarithmic inertia degrees f̃(𝔭_{K}/𝔭_{F}) and ramification indices ẽ(𝔭_{K}/𝔭_{F}) for 𝔭_{K} ⊂ ℤ_{K} dividing 𝔭_{F} ⊂ ℤ_{F}, with formal properties analogous to the classical indices e(𝔭_{K}/𝔭_{F}) and f(𝔭_{K}/𝔭_{F}), without coinciding with them. These local indices are multiplicative and satisfy the product formula

ẽ(𝔭_{K}/𝔭_{F})f̃(𝔭_{K}/𝔭_{F}) = e(𝔭_{K}/𝔭_{F})f(𝔭_{K}/𝔭_{F}) = [K_{𝔭} : F_{𝔭}].

They are introduced as follows: by multiplicativity, it suffices to define f̃(𝔭_{F}/p) since f̃(𝔭_{K}/𝔭_{F}) = f̃(𝔭_{K}/p) / f̃(𝔭_{F}/p). Now let F_{𝔭}^{ab} be the maximal subextension of the local field F_{𝔭} which is abelian over ℚ_{p}. The classical inertia degree f(𝔭/p) is the degree [F_{𝔭}^{ab} ∩ ℚ_{p}^{unr} : ℚ_{p}], where ℚ_{p}^{unr} denotes the unramified ℤ̂-extension of ℚ_{p}. The logarithmic inertia degree is the degree [F_{𝔭}^{ab} ∩ ℚ_{p}^{c} : ℚ_{p}], where ℚ_{p}^{c} is the cyclotomic ℤ̂-extension of ℚ_{p}. In particular the logarithmic indices do not depend on the choice of the prime ℓ.

One says that the extension K/F ramifies logarithmically at a finite prime 𝔭_{F} whenever ẽ(𝔭_{K}/𝔭_{F}) > 1 for some 𝔭_{K} | 𝔭_{F}. As in the classical case, an extension of number fields is unramified (in the logarithmic sense) except at a finite number of primes. However a logarithmically unramified extension may ramify in the ordinary sense. Such extensions play a crucial role in the capitulation for the Bertrandias-Payan module studied in the present volume (cf. [9, 11, 20]).

This note presents our implementation in the PARI/GP system of the various arithmetic invariants attached to logarithmic classes and units. The algorithms do not depend on any conjecture: if the program stops, its output is correct, and it in fact proves that the Gross-Kuz’min conjecture holds for that particular prime ℓ and number field F.

Acknowledgements: we thank Sebastian Pauli for sharing his Magma implementation, José Villanueva-Gutiérrez for feedback and examples, and Bill Allombert for many useful discussions.

2 Algorithmic preliminaries

We recall in this section well known facts from computational number theory, to fix notations. The next section will deal with the main algorithms, germane to the computation of logarithmic objects.

2.1 The Smith Normal Form

We say that a ℤ-module of finite type G is known if

• we have a Smith Normal Form description (SNF)

G = ⨁_{1⩽i⩽s} ℤ/(d_{i}) · g_{i},

for some generators g_{i}, where d_{s} | ⋯| d_{1} are the elementary divisors of G; if G has a free part of rank r, then d_{1} = ⋯= d_{r} = 0. If r = 0, then G is finite and its exponent e(G) is d_{1}.

• we can solve discrete logarithm problems in G, i.e. decompose elements x ∈ G as x = ∑ _{i⩽s} x_{i} · g_{i}, where x_{i} ∈ ℤ/(d_{i}).

More generally, let R be a matrix in M_{s×t} (ℤ). A ℤ-module of finite type G is given by generators (g_{1}, …, g_{s}) and relations R when (g_{1}, …, g_{s}) · X = 0_{G} holds for some X ∈ ℤ^{s} if and only if X = MY for some Y ∈ ℤ^{t}. In that case, there exist matrices U ∈ GL_{s}(ℤ) and V ∈ GL_{t}(ℤ) such that UMV is in Smith Normal Form (SNF), i.e.

UMV = (D | 0) when t ⩾ s or ( \begin{matrix}D \\ 0 \end{matrix}) when t ⩽ s,

where D is the diagonal matrix diag(d_{1}, …, d_{s}). In both cases, (g_{1}, …, g_{s}) · U^{−1} are SNF generators of order d_{s} | ⋯| d_{1}. The SNF algorithm applied to R produces U and V in polynomial time (in s, t and log∥R∥_{2}).

The same technique allows to handle ℤ_{ℓ}-modules: when R ∈ M_{s×t} (ℤ_{ℓ}), there exist U ∈ GL_{s}(ℤ_{ℓ}) and V ∈ GL_{t}(ℤ_{ℓ}) such that UMV is in SNF. Given M_{N} = M modℓ^{N}, the above algorithm applied to (M_{N} | ℓ^{N} Id_{s}) produces U and V modulo ℓ^{N} and the matrix U^{−1} modulo ℓ^{N} describing SNF generators for G ⊗_{ℤ} ℤ/(ℓ^{N}), the running time is now polynomial in s, t and N logℓ.

2.2 Computational algebraic number theory

The number field F of degree n is given by the minimal polynomial T ∈ ℤ[X] of an integral generating element, in other words F = ℚ[X]/(T). We write \overline{X} for the class of X modT; an element α ∈ F is given by a rational polynomial A ∈ ℚ[X] such that α = A(\overline{X}). For any α ∈ F we let ∥α∥ = ∏ _{v} max(1, |α|_{v}) where v runs through all places of F and |α|_{v} is the attached normalized absolute value. We assume given a ℤ-basis of its maximal order ℤ_{F}. This is in general an expensive invariant, not necessary for all our algorithms, for instance Algorithm 1 and Corollary 3.5; on the other hand current algorithms to compute the class group of F and the unit group ℤ_{F}^{×} require it.

We further assume that the class group Cl_{F} and unit group E_{F} are known in the sense of 2.1. In the context of the class group Cl_{F}, the discrete logarithm problem is solved in I_{F} in the following extended sense. The generators classes are represented by integral ideals g_{i}; given a fractional ideal 𝔞 in I_{F}, we can find α ∈ F^{×} so that our ideal decomposes as a product of the generators g_{i} multiplied by the principal ideal (α). We refer to [3] for how to handle these standard tasks. Practical algorithms to compute Cl_{F} and E_{F} require assuming the truth of the Generalized Riemann Hypothesis for the unramified Hecke L-functions L_{F}(χ, s), χ ∈ Ĉl_{F}, and for the Riemann ζ function. But this assumption can be lifted provided the discriminant discF is not too large. (The certification process requires time proportional to \sqrt{|discF|}.)

To each maximal ideal 𝔭 ⊂ ℤ_{F} above a rational prime p we attach the completed local field F_{𝔭}. There exist an irreducible monic divisor T_{𝔭} ∈ ℤ_{p}[X] of T, of degree n_{𝔭} = [K_{𝔭} : ℚ_{p}] = e(𝔭/p)f(𝔭/p), such that K_{𝔭} = ℚ_{p}[X]/(T_{𝔭}). Given T and a prime p, and for any given p-adic accuracy k, we can produce in polynomial time O(k logp·n log∥T ∥_{∞} )^{C}

• the prime ideals 𝔭_{i} = pℤ_{F} + π_{i}ℤ_{F} dividing p, together with their ramification indices and residue degrees, where v_{𝔭_{i}}(π_{i}) = 1 (this is automatic if e(𝔭_{i}/p) > 1 and one of π_{i} or π_{i} + p satisfy this condition in any case);

• for each 𝔭_{i}, a p-adic approximation T_{𝔭_{i},k} ∈ ℤ[X] such that T_{𝔭_{i},k} ≡ T_{𝔭_{i}} (mod p^{k});

see for instance the Round 4 algorithm as finalized in [7]. The older (and much simpler) Round 2 algorithm and Buchmann-Lenstra factorization would also achieve this result, see [2].

2.3 Local norms

We shall need to compute local norms and their Iwasawa logarithms. We can write any α ∈ F^{×} as A(\overline{X})/a for a ∈ ℤ_{>0} and A ∈ ℤ[X] and the representation is unique if a and the content of A are coprime. Since N_{F_{𝔭}/ℚ_{p}}(a) = a^{n_{𝔭}}, we may focus on α ∈ ℤ[\overline{X}].

Lemma 2.1. Let α = A(\overline{X}), α ≠ 0, where A ∈ ℤ[X]. For each integer k > v_{p} (N_{F_{𝔭}/ℚ_{p}}(α)), let N_{k} = Res(A, T_{𝔭,k}) modp^{k} ∈ ℤ then

N_{F_{𝔭}/ℚ_{p}}(α) ≡ N_{k} (mod p^{k}).

In particular, v_{p}(N_{k}) = v_{p} (N_{F_{𝔭}/ℚ_{p}}(α)) does not depend on k and

Log_{p}N_{F_{𝔭}/ℚ_{p}}(α) ≡ Log_{p}N_{k} (mod p^{k−v_{p}(N_{k})} ).

Note that if the size ∥α∥ of α is controlled, so is |N_{F/ℚ}(α) | ⩽ ∥α∥^{n}. Thus v_{p}(N_{k}) ⩽

v_{p} (N_{F/ℚ}(α)) is controlled and finally, any k > v_{p} (N_{F/ℚ}(α)) satisfies the condition in the lemma. This allows to approximate ṽ_{𝔭}(α) to any given accuracy from a sufficiently precise approximation T_{𝔭,k} of T_{𝔭}.

3 The main algorithm

We follow the general strategy of [6], while introducing numerous improvements and simplifications along the way. Let ℓ be a fixed prime number and denote S = {𝔭_{1}, …, 𝔭_{l}} the set of places of F above ℓ. We rely on the obvious exact sequence of pro-ℓ groups

0 −−⟶ C̃l(ℓ) −−⟶ C̃l −−⟶^{ψ} Cl′ −−⟶ 0

where C̃l(ℓ) is the subgroup generated by the logarithmic classes of the 𝔭_{i}, the group Cl′ is the ℓ-Sylow subgroup of the quotient of the ideal class group by the subgroup generated by the ideal classes of the 𝔭_{i}, and where

ψ : ∑_{𝔭} m_{𝔭}𝔭 ⟼→ ∏_{𝔭∤ℓ} 𝔭^{m_{𝔭}}.

We shall compute the groups C̃l(ℓ) and Cl′independently, by generators and relations, then build up C̃lusing the exact sequence.

Remark 3.1. We depart here from [5, 6] which use θ : ∑ _{𝔭} m_{𝔭}𝔭 ↦ ∏ _{𝔭∤ℓ}𝔭^{(_{f_{𝔭}} /f_{𝔭})m_{𝔭}} . The latter has good properties in extensions, which we will not need. When the field is fixed, it makes no difference: for 𝔭 ∤ ℓ, the factor f̃_{𝔭} /f_{𝔭} belongs to ℤ_{ℓ}^{×} so the kernel and cokernel of θ and ψ are the same. More substantially, we do not restrict to degree 0 divisors C̃l(ℓ)^{0} and C̃l^{0} at this stage, which would introduce a nontrivial cokernel (as some ideal classes might not be representable by degree 0 divisors). This avoids the technical difficulty of having to modify natural generators so that their degree become zero as in [6, Corollary 18]. This is not obvious and Corollary 18 is incorrect as stated.

3.1 Computing ẽ(𝔭/p), f̃(𝔭/p) and ṽ_{𝔭}(·)

We first explain how to compute the logarithmic inertia and residue degrees. The algorithm is a straightforward consequence of the following two lemmas:

Lemma 3.2. Let 𝔭 be a maximal ideal above a rational prime p. We write e, f, ẽ, f̃ respectively for e(𝔭/p) f(𝔭/p), ẽ(𝔭/p) and f̃(𝔭/p).

(1) We have ẽf̃ = n_{𝔭} = ef.

(2) The prime to p part of ẽ and e coincide, i.e. v_{q}(e) = v_{q}(ẽ) for all primes q ≠ p.

(3) The logarithmic ramification index ẽ and [h_{𝔭}(F_{𝔭}^{×} ) : ℤ_{p}] have the same valuation at p, where

h_{𝔭}(α) = \frac{Log_{p}N_{F_{𝔭}/ℚ_{p}}(α)}{n_{𝔭} · (2p)} .

Note that h_{𝔭}(ℚ_{p}^{×}) = ℤ_{p}.

(4) We have v_{p}(f̃) ⩽ v_{p}(e). In particular if p ∤ e, then v_{p}(ẽ) = v_{p}(f) and v_{p}(f̃) = 0.

Proof. The first three points are proved in [13]. The final one follows from a direct calculation using h_{𝔭} or using the abstract definition f̃(𝔭/p) = [F_{𝔭}^{ab} ∩ ℚ̂_{p}^{c}: ℚ_{p}], where ℚ̂_{p}^{c} is the compositum of all cyclotomic ℤ_{q} extensions of ℚ_{p} on all prime numbers q. Thus the p-primary part of f̃ is the degree over ℚ_{p} of the intersection L of F_{𝔭}^{ab} with the cyclotomic ℤ_{p}-extension of ℚ_{p}. The claim follows by multiplicativity of ramification indices in F_{𝔭}/L/ℚ_{p}.

Lemma 3.3. Let 𝔭 be a maximal ideal above the prime p with ramification index e = e(𝔭/p). Let D = D_{F_{𝔭}/ℚ_{p}} denote the local different and let k > e/(p − 1). Then Log_{p}N_{F_{𝔭}/ℚ_{p}}(1 + 𝔭^{k}) = p^{⌊v/e⌋}ℤ_{p}, where v = k + v_{𝔭}(D).

Proof. For k > e/(p − 1), we have 1 + 𝔭^{k} = exp(𝔭^{k}) and Log_{p}N_{F_{𝔭}/ℚ_{p}}(1 + 𝔭^{k}) = Tr_{F_{𝔭}/ℚ_{p}}(𝔭^{k}). We then use the equivalence Tr_{F_{𝔭}/ℚ_{p}} 𝔭^{k} ⊂ 𝔞 ⇔ 𝔭^{k}D ⊂ 𝔞 for any fractional ideal 𝔞 ⊂ ℚ_{p}.

Algorithm 1 Compute ẽ(𝔭/p), f̃(𝔭/𝔭) Input: A maximal ideal 𝔭 = pℤ_{F} + πℤ_{F}, v_{𝔭}(π) = 1 above some prime p of

ramification index e = e(𝔭/p) and residue degree f = f(𝔭/p). Output: ẽ = ẽ(𝔭/p) and f̃ = f̃(𝔭/p). 1: If v_{p}(e) = 0, set ẽ ← e · p^{v_{p}(f)} , f̃ ← f · p^{−v_{p}(f)} and stop. 2: Let n_{𝔭} ← ef and let k ← 1 + ⌊e/(p − 1)⌋ > 1. 3: Let g_{0} ← π and let (g_{1}, …, g_{s}) be independent generators for the finite abelian

group (1 + 𝔭)/(1 + 𝔭^{k}); see [4, §4.2.3]. 4: Let v ← min_{0⩽i⩽s} v_{p} (Log_{p}N_{F_{𝔭}/ℚ_{p}}(g_{i})), computed using Lemma 2.1.

5: Let v_{∞} = ⌊(k + v_{𝔭}(D_{F_{𝔭}/ℚ_{p}}))/e ⌋. If v_{∞} < v, let v ← v_{∞} . 6: Let v ← v − v_{p}(f · 2p). Set ẽ ← e · p^{−v} and f̃ ← f · p^{v}.

Proof. The problem boils down to computing the valuation at p of ẽ(𝔭/p). Using statement (3) in the lemma, this is the non-negative integer w such that h_{𝔭}(F_{𝔭}^{×} ) = p^{−w} ℤ_{p}. We decompose F_{𝔭}^{×} = π^{ℤ}×μ_{F_{𝔭}}×(1+𝔭ℤ_{F_{𝔭}}); since h_{𝔭} is additive and h_{𝔭}(μ_{F_{𝔭}}) = 0, it is enough to determine the valuation of h_{𝔭} evaluated at π and on multiplicative generators of 1 + 𝔭ℤ_{F_{𝔭}}, i.e. on generators of (1 + 𝔭)/(1 + 𝔭^{k}) and 1 + 𝔭^{k}; the latter are handled by Lemma 3.3 yielding the v_{∞} contribution.

Remark 3.4. By Lemma 3.3, if generator g = g_{i} of the p-group (1+𝔭)/(1+𝔭^{k}) has order d = d_{i}, then Log_{p}N(g^{d}) has valuation ⩾ v_{∞} . So, when we compute the minimum of the valuations incrementally for g_{1}, g_{2}, …, by decreasing order, we can stop as soon the lower bound v_{∞} −v_{p}(d_{i}) for the valuation of Log_{p}N(g_{i}) becomes larger than the current minimum. We can also restrict to the generators of (1+𝔭)/(1+𝔭^{k}) modulo the p-primary roots of unity in F_{𝔭}. Finally, we compute v_{p} (Log_{p}N_{F_{𝔭}/ℚ_{p}}(g_{i})) as v_{p} (N_{F_{𝔭}/ℚ_{p}}(g_{i}) − 1 ) for i > 0.

In comparison, the algorithms of [6, §3.1] need the full set of multiplicative generators of 1 + 𝔭ℤ_{F_{𝔭}}, whose description is complicated and uses the principal unit filtration up to k = pe/(p − 1). Introducing v_{∞} thus reduces the size of the generator system by a rough factor p; and we in fact expect to consider only g_{0} and g_{1} due to the a priori lower bound v_{∞} − v_{p}(d_{i}). The early abort when v_{p}(e) = 0 also skips the non-trivial part of the algorithm unless p belongs to the tiny set of (wildly ramified) prime divisors of [F : ℚ].

Corollary 3.5. Let ℓ be our fixed prime and 𝔭 be a maximal ideal above some prime p. Lemma 2.1 and Algorithm 1 allow to compute the following quantities to any desired ℓ-adic accuracy in time polynomial in logℓ, logp, n, log∥T ∥_{∞} and log∥x∥

(1) deg𝔭 = f̃(𝔭/p) deg_{ℓ}p, where deg_{ℓ}p = \{ \begin{matrix}Log_{ℓ}p & if p ≠ ℓ, \\ ℓ & if p = ℓ ≠ 2 , \\ 4 & if p = ℓ = 2 . \end{matrix}

(2) For x ∈ F^{×} , ṽ_{𝔭}(x) = \{ \begin{matrix}v_{𝔭}(x) & if p ≠ ℓ, \\ −\frac{Log_{p} ( N_{F_{𝔭}/ℚ_{p}}(x))}{deg𝔭} & if p = ℓ. \end{matrix}

Remark 3.6. The logarithmic degree deg_{ℓ}ℓ may be multiplied by an ℓ-adic unit without changing the structure of C̃l. In other contexts, defining respectively

deg_{ℓ}ℓ = Log_{ℓ}(1 + ℓ) and Log_{2}(1 + 4)

will be more convenient. Indeed, with the latter definition, the exponential of deg𝔭 would always be a natural number.

3.2 The group Cl′

Let S be the set of places above ℓ. We compute the S-class group

Cl_{F}/ ⟨S⟩ = ⨁_{1⩽i⩽s}(ℤ/d_{i}ℤ) · g_{i},

where each g_{i} has order d_{i} and d_{s} | ⋯| d_{1}, using the obvious definition by generators (the g_{i} generating the class group) and relations (the subgroup generated by the classes of elements of S) and computing the attached SNF, see [4, §7.4.2]. We obtain its ℓ-Sylow subgroup Cl′by raising each SNF generator g_{i} to the power d_{i}ℓ^{−v_{ℓ}(d_{i})} . Alternatively, we can first read off the exponent e = ℓ^{v_{ℓ}(d_{1})} of Cl′ from the SNF description of Cl_{F}/ ⟨S⟩, then compute its ℓ-adic SNF by adding g_{i}^{e} = 1, i ⩽ s, to the relations. The latter method is likely to yield smaller base change matrices, hence smaller generators. In any case, the generators of Cl′ are represented by integral ideals in ℤ_{F}, which we may assume to be coprime to ℓ. Indeed, if g ⊂ ℤ_{F} is an arbitrary generator and (g_{ℤ}) = g∩ℤ, we can replace g by

g + (g_{ℤ} · ℓ^{−v_{ℓ}(g_{ℤ})}) ℤ_{F} = g · ∏_{𝔭|ℓ} 𝔭^{−v_{𝔭}(g)} .

Solving the discrete logarithm problem is a standard extension, see [4, §4.1.3]. The only thing to note is that as described the algorithm will produce huge generators, as the initial class group generators are raised to huge powers through the necessary linear algebra. We use the “group ring representation” from [1, §7] keeping principal ideals in factored form, i.e. as elements in ℤ[ℤ_{F}], and LLL-reducing general ideals along the way; in this manner the principal parts, in class groups or S-class groups discrete logarithm decompositions, are obtained in the form α = ∏ _{i⩽r} α_{i}^{e_{i}}, where the α_{i} are small elements in F (∥α_{i} ∥ is controlled) and the e_{i} are possibly large integers.

Definition 3.7. For any α ∈ ℤ[ℤ_{F}] given in factored representation we write x ∈ Suppα when x belongs to the support of α, i.e. is one of the α_{i} ∈ ℤ_{F} occuring in the factored representation.

This factored representation of elements is quite suitable to compute multiplicative or additive functions such as local norms and their ℓ-adic logarithms, or standard and logarithmic valuations v_{𝔭} and ṽ_{𝔭}.

3.3 The group C̃l(ℓ)

We describe C̃l(ℓ) by generators (the classes of the ℓ-adic places S = {𝔭_{1}, …, 𝔭_{l}}) and relations (derived from d̃iv(u) = 0, u an S-unit). Thus the group is given by the ℓ-adic SNF of the matrix M = (ṽ_{𝔭_{i}}(u_{j})), where the (u_{j}), 1 ⩽ j ⩽ J = r_{F} +c_{F} +l −1, generate the free part of the S-unit group.

The (u_{j}) are computed as in [4, §7.4.2], again taking care to use factored representations. Let

δ(u_{1}, …, u_{J}) = max_{i} ( v_{ℓ}(deg𝔭_{i}) + max_{j, α∈Supp u_{j}} v_{ℓ}(N_{F_{𝔭_{i}} /ℚ_{ℓ}}(α)) ) ,

where Suppu_{j} was defined in the previous paragraph. This quantity accounts for the maximal loss of accuracy when approximating the ṽ_{𝔭_{i}}(u_{j}) by Lemma 2.1 and Corollary 3.5. For increasing N > log_{2} δ, we approximate the ṽ_{𝔭_{i}} modulo ℓ^{2^{N}} > δ and compute the SNF of M modulo L_{N} = ℓ^{2^{N} −δ} . We may stop as soon as the computed SNF has a single elementary divisor of largest valuation:

Lemma 3.8. If the computed SNF of the finite ℓ-group

C̃l(ℓ) / C̃l(ℓ)^{L_{N}} = ⨁_{i⩽s} ℤ/(ℓ^{v_{i}}) · g_{i}

has a single elementary divisor of largest valuation v_{1} > v_{2}, then the Gross-Kuz’min conjecture for the field F and the prime ℓ holds. Indeed, in this case, we have C̃l(ℓ) = ℤ_{ℓ} · g_{1} ⊕ C̃l(ℓ)^{0}, where C̃l(ℓ)^{0} = ⊕_{i>1} (ℤ/ℓ^{v_{i}}) · g_{i} has exponent ℓ^{v_{2}}.

Proof. C̃l(ℓ) has ℤ_{ℓ}-rank bigger than 1 due to the product formula:

∑_{i⩽l} deg𝔭_{i} · ṽ_{𝔭_{i}}(x) = 0,

for any S-unit x. The Gross-Kuz’min conjecture states that this rank is exactly 1.

Concretely, we apply the SNF algorithm to obtain matrices U ∈ GL_{l}(ℤ) and V ∈ GL_{r_{F} +c_{F} +2l−1} (ℤ) such that

U(M modℓ^{L_{N}} | ℓ^{L_{N}} · Id_{l} )V = ( diag(d_{i}) | 0)

is in rectangular Smith Normal Form, and stop when L_{N} = v_{ℓ}(d_{1}) > v_{ℓ}(d_{2}). The g_{i} are given in terms of the logarithmic classes of the 𝔭_{i} by

(g_{1}, …, g_{l}) = (𝔭_{1}, …, 𝔭_{l}) · U^{−1} .

We then delete the trivial g_{i}, s < i ⩽ l, such that d_{i} = 1. Of course, the algorithm will not stop if the conjecture is false and rk_{ℤ_{ℓ}} C̃l(ℓ) > 1. Remark 3.9. This is the equivalent of Algorithm 14 and Theorem 16 in [6], simplified by the fact that we do not need the generators to have degree 0. The system of ℓadic α_{j} ∈ F^{×} ⊗_{ℤ} ℤ_{ℓ} such that ṽ_{𝔭_{i}}(α_{j}) = δ_{i,j} are no longer needed. (Note that the construction given before [6, Algorithm 19] must be modified so that it guarantees that (α_{j}, ℓ) = 1.)

3.4 The logarithmic class group

We use [4, §4.1.4] to describe C̃l by generators and relations. The logarithmic classes of the ℓ-adic places {𝔭_{1}, …, 𝔭_{l}} generate C̃l(ℓ), with relations computed above. Let ⊕_{i⩽s}(ℤ/d_{i})·𝔞_{i} be the SNF of Cl′where we chose integral ideal representatives 𝔞_{i} coprime to ℓ for the generating ideal classes. Those generators lift naturally to divisors, still denoted 𝔞_{i}, in C̃lvia ∏ 𝔭^{e_{𝔭}} → ∑ e_{𝔭}𝔭. Then d_{i} · 𝔞_{i} belongs to Kerψ, hence to C̃l(ℓ) and we can write

(d_{1} · 𝔞_{1}, …, d_{s} · 𝔞_{s}) = (𝔭_{1}, …, 𝔭_{l}) · (−P)

in C̃lfor some matrix P ∈ M_{l×s} (ℤ_{ℓ}), from which we derive the ℓ-adic matrix of relations between the generators (𝔭_{1}, …, 𝔭_{l}, 𝔞_{1}, …, 𝔞_{s}):

( \begin{matrix}M & P \\ 0 & diag(d_{1}, …, d_{s}) \end{matrix})

We now need to determine the matrix P.

Lemma 3.10. For each 1 ⩽ i ⩽ s, write

𝔞_{i}^{d_{i}} = (α_{i}) ∏_{j⩽l} 𝔭_{j}^{∗_{i,j}}

for some principal ideal (α_{i}) and integral exponents ∗_{i,j} . Let P ∈ M_{s×l} (ℤ_{ℓ}) be the matrix (ṽ_{𝔭_{j}}(α_{i})). In the group C̃l, it holds

(d_{1} · 𝔞_{1}, …, d_{s} · 𝔞_{s}) = (𝔭_{1}, …, 𝔭_{l}) · (−P).

Proof. Since the ideal 𝔞_{i} is coprime to ℓ, it follows that ∏ _{𝔭∤ℓ}𝔭^{v_{𝔭}(α_{i})} = 𝔞_{i}^{d_{i}} and that, in C̃l, we have

0 = d̃iv(α_{i}) = ∑_{𝔭∤ℓ} v_{𝔭}(α_{i}) · 𝔭 + ∑_{j⩽l} ṽ_{𝔭_{j}}(α_{i}) · 𝔭_{j} = d_{i} · 𝔞_{i} + ∑_{j⩽l} ṽ_{𝔭_{j}}(α_{i}) · 𝔭_{j}.

Concretely, the decomposition

𝔞_{i}^{d_{i}} = (α_{i}) ∏_{j} 𝔭_{j}^{∗_{i,j}}

is computed by solving a discrete logarithm problem in Cl_{F} where, as usual, the (α_{i})_{i⩽s} are given in factored representation. As in §3.3, we bound the loss of accuracy when estimating the ṽ_{𝔭_{j}}(α_{i}) and set

L := max (δ(α_{1}, …, α_{l}), v_{ℓ}(e(Cl′)) + v_{ℓ}(e(C̃l(ℓ))) + 1 ) .

Then we compute the SNF of

( \begin{matrix}M modℓ^{L} & ℓ^{L} · Id_{l} & P modℓ^{L} \\ 0 & 0 & diag(d_{1}, …, d_{s}) \end{matrix}) .

Including the kernel and image exponents in the maximum guarantees that the SNF has a unique maximal elementary divisor, allowing to split off the rank 1 ℤ_{ℓ}-free part and the finite C̃l_{F}^{0}.

4 The bnflog package

4.1 The PARI/GP interface

In PARI/GP [21] version 2.8.1, the above algorithms are implemented as functions bnflogef and bnflog. All examples below are written in the GP scripting language.

• The function bnflogef takes as input a number field F and a prime ideal 𝔭 and returns the logarithmic indices ẽ(𝔭/p) and f̃(𝔭/p). This is an elementary function requiring only basic arithmetic invariants of F, hence the use of the simple nfinit to define the number field structure:

? T = x^6 - 3*x^5 + 5*x^3 - 3*x + 1;
? F = nfinit(T);  \\ the number field Q[x]/(T)
? P2 = idealprimedec(F,2)[1]; \\ a prime above 2
? [P2.e, P2.f]    \\ ramification index and residue degree
%3 = [3, 2]       \\ e(P/p) = 3, f(P,p) = 2
? bnflogef(F, P2)
%4 = [6, 1]       \\ etilde(P/p) = 6, ftilde(P/p) = 1

• The function bnflog takes as input a prime ℓ and a number field F. It returns a vector of three group structures, given by their elementary divisors: (C̃l_{F}^{0}, C̃l_{F}^{0}(ℓ), Cl′). This function requires the class group and units of F, hence the more involved initialization using bnfinit:

? T = x^4 + 13*x^2 - 12*x + 52;
? F = bnfinit(T); \\ F = Q[x]/(T), together with class group
? F.cyc
%3 = [14]            \\ Cl_F ~ Z/(14)]
? bnflog(F, 2)
%4 = [[], [], []]    \\ all 3 groups are trivial
? bnflog(F, 3)
%5 = [[3], [3], []]  \\ Cl^0 = Cl^0(3) ~ Z/(3)
? bnflog(F, 7)
%6 = [[7], [], [7]]  \\ Cl^0 ~ Cl' ~ Z/(7)

4.2 Examples

• The following two examples exhibit pathologies expected from the exact sequence relating C̃l_{F}^{0}, C̃l_{F}^{0}(ℓ) and Cl′:

? T = x^4 - 511*x^2 + 65536;
? bnflog(bnfinit(T),2)
%2 = [[128, 4], [64], [8]] \\ the sequence doesn't split
? T = x^4 - 26*x^2 + 225;
? bnflog(bnfinit(T),2)
%4 = [[], [], [2]]         \\ coker(psi) = Z/2

• This program fixes a misprint in [6, p. 12], which reports C̃l^{0} for F = ℚ(\sqrt{1234577}, \sqrt{−3} ) to be ℤ/4ℤ × ℤ/4ℤ (it is cyclic of order 4):

? T = polcompositum(x^2+3, x^2-1234577, 2);
? bnflog(bnfinit(T,1),2)
%2 = [[4], [4], []]

• The following program proves [12, Proposition 3.4]; the locally cyclotomic 2-tower of F = ℚ(\sqrt{−p}) is infinite:

? {
    forprime(p = 2, 5000,
      if (p%64 != 63, next);
      F = bnfinit(x^2+p);
      G = bnflog(F,2); Cl = G[1]; if(!Cl || Cl[1] % 16,next);
      print([p,G]))
  }
[3967, [[16], [16], []]]
[4159, [[32], [32], []]]

• The following program proves [12, Proposition 3.5]; the locally cyclotomic 2-tower of F = ℚ(\sqrt{pq}) is infinite:

? {
    forprime(p = 2, 2000,
      if (p % 64 != 1 && p % 64 != 63, next);
      forprime(q = p+1, 2000, if ((p*q)%64 != 1, next);
      F = bnfinit(x^2-p*q, 1);
      G = bnflog(F,2); C = G[1]; if (!C || C[1] % 16, next);
      print([p,q,G])))
  }
[127,  1151, [[32], [32], []]]

[193,  257,  [[32], [8], [4]]]
[193,  1217, [[16], [4], [4]]]
[449,  577,  [[256], [128], [2]]]
[577,  1601, [[64, 2], [16], [8]]]
[641,  769,  [[16, 2], [16], [2]]]
[1151, 1663, [[16], [16], []]]

• We now give two examples with large 3-rank (and large class group); factored representations must be used throughout to avoid catastrophic cancellation:

? F = bnfinit(x^2 + 5393946914743);
? bnflog(F, 3)
%2 = [[3, 3, 3, 3, 3], [], [3, 3, 3, 3, 3]]
\\ This assumes the truth of the GRH:
? F = bnfinit(x^2 + 14138863693162613823739799380212181908);
? F.cyc
%4 = [693468857222922, 6, 6, 6, 3]
? bnflog(F, 3)
%5 = [[3, 3, 3, 3, 3], [9], [3, 3, 3, 3]]

The final computation is conditional on the truth of the GRH, since it is not practical to certify the class group of a field F with such a large discriminant. The total running time for all the above computations is about 4 minutes, 99% of which are spent in the final example.

• This program prints the smallest real quadratic field whose C̃l^{0} has 2-rank equal to 5 (and its locally cyclotomic 2-tower is infinite). This fixes a misprint in [18] which erroneously reports F = ℚ(\sqrt{3 · 5 · 7 · 11 · 13 · 17} ) as the real quadratic field with smallest discriminant with this property (but its 2-rank is 4). This computation requires about 5 hours.

? D = 3*5*7*11*13*17*19;
? {
    for(d=2, D,
      if (!issquarefree(d),next);
      F = bnfinit(x^2-d, 1);
      G = bnflog(F,2); if (#G[1] >= 5, print([d,G])))
  }
[4849845, [[4, 2, 2, 2, 2], [], [4, 2, 2, 2, 2]]]
? bnflog(bnfinit(x^2-3*5*7*11*13*17), 2);
%3 = [[2, 2, 2, 2], [], [2, 2, 2, 2]]

References

[1] K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux 16 (2004), no. 1, pp. 19–63.

[2] J. Buchmann & H. W. Lenstra, Jr., Approximating rings of integers in number fields, J. Théor. Nombres Bordeaux 6 (1994), no. 2, pp. 221–260.

[3] H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993.

[4] H. Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000.

[5] F. Diaz y Diaz & F. Soriano, Approche algorithmique du groupe des classes logarithmiques, J. Number Theory 76 (1999), no. 1, pp. 1–15.

[6] F. Diaz y Diaz, J.-F. Jaulent, S. Pauli, M. Pohst, & F. Soriano-Gafiuk, A new algorithm for the computation of logarithmic l-class groups of number fields, Experiment. Math. 14 (2005), no. 1, pp. 65–74.

[7] D. Ford, S. Pauli, & X.-F. Roblot, A fast algorithm for polynomial factorization over ℚ_{p}, J. Théor. Nombres Bordeaux 14 (2002), no. 1, pp. 151–169.

[8] G. Gras, Class field theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003, From theory to practice, Translated from the French manuscript by Henri Cohen.

[9] T. Gras, Sur le module de Bertrandias-Payan – Noyau de capitulation, Pub. Math. Besançon, à paraître.

[10] J.-F. Jaulent, Normes cyclotomiques naïves et unités logarithmiques, preprint,

https://arxiv.org/abs/1609.01901.

[11] J.-F. Jaulent, Sur la capitulation pour le module de Bertrandias-Payan, Pub. Math. Besançon, à paraître.

[12] J.-F. Jaulent & C. Maire, À propos de la tour localement cyclotomique d’un corps de numbres, Abh. Math. Sem. Univ. Hamburg 70 (2000), pp. 239–250.

[13] J.-F. Jaulent, Classes logarithmiques des corps de nombres, J. Théor. Nombres Bordeaux 6 (1994), no. 2, pp. 301–325.

[14] J.-F. Jaulent, Sur le noyau sauvage des corps de nombres, Acta Arith. 67 (1994), no. 4, pp. 335–348.

[15] J.-F. Jaulent, Théorie ℓ-adique globale du corps de classes, J. Théor. Nombres Bordeaux 10 (1998), no. 2, pp. 355–397.

[16] J.-F. Jaulent, Classes logarithmiques signées des corps de nombres, J. Théor. Nombres Bordeaux 12 (2000), no. 2, pp. 455–474, Colloque International de Théorie des Nombres (Talence, 1999).

[17] J.-F. Jaulent & A. Michel, Approche logarithmique des noyaux étales sauvages des corps de nombres, J. Number Theory 120 (2006), no. 1, pp. 72–91.

[18] J.-F. Jaulent & F. Soriano, Sur les tours localement cyclotomiques, Arch. Math. (Basel) 73 (1999), no. 2, pp. 132–140.

[19] J.-F. Jaulent & F. Soriano, Sur le noyau sauvage des corps de nombres et le groupe des classes logarithmiques, Math. Z. 238 (2001), no. 2, pp. 335–354.

[20] T. Nguyen-Quang-Do, Descente galoisienne et capitulation pour le module de Bertrandias-Payan, Pub. Math. Besançon, à paraître.

[21] The PARI Group, Bordeaux, PARI/GP, version 2.8.1, 2016, http://pari.math.

    u-bordeaux.fr/.