MATHEMATICS OF COMPUTATION
S0025-5718(99)01111-4
Article electronically published on March10,1999
COMPUTING THE HILBERT CLASS FIELD
OF REAL QUADRATIC FIELDS
HENRI COHEN AND XAVIER-FRANC?OIS ROBLOT
https://www.doczj.com/doc/1f4868672.html,ing the units appearing in Stark’s conjectures on the values of
L-functions at s=0,we give a complete algorithm for computing an explicit
generator of the Hilbert class?eld of a real quadratic?eld.
√Let k be a real quadratic?eld of discriminant d k,so that k=Q(
Received by the editor January19,1998and,in revised form,September10,1998.
1991Mathematics Subject Classi?cation.Primary11R37,11R42;Secondary11Y35.
c 1999American Mathematical Society
1
2HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT
algorithm,and Section4to the veri?cation of the result.Section5deals with an example.
We end the paper with an Appendix giving a table of Hilbert class?elds of real quadratic?elds of discriminant less than2000.
1.Construction when the class number is equal to2
We assume in this section that h k=2.As we already said,in this case there are two powerful methods to compute H k,and we quote them without proof.
The?rst uses Kummer theory,which states that when the ground?eld contains the n-roots of unity,every Abelian extension of exponent dividing n can be obtained by taking n-th roots of elements of the ground?eld.From this,one easily obtains Proposition1.1.Let k be a real quadratic?eld of class number2,let v be a real embedding of k,letηdenote the fundamental unit of k such that v(η)>1,and let A be a non-principal integral ideal of k.Letαbe one of the generators of A2chosen
√
so that v(α)>0.Then H k=k(
d).
Hence the determination of H k in this case boils down to a?nite number of easy tests.
2.A special case of Stark’s conjectures
We now assume only that h k>1.We keep the same notations,we let v be one of the real embeddings of k and we denote byˉthe action of the non-trivial element of the Galois group of k/Q.We will identify k with its embedded image v(k)into R.Let K be a quadratic extension of H k such that K/k is Abelian and v stays real in this extension but
COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS3 for anyσ∈G.Furthermore,if we setα:=ε+ε?1,we have H k=k(α)and |α|w≤2for any in?nite place w of H k which does not divide v.
We refer to[22]for this conjecture and a more general statement of Stark’s conjectures,and to[17]for a proof of this result.
In the next section,we will explain how to computeζ′K/k(0,σ)forσ∈G,and how to?nd the elementαas an algebraic number,if it exists.
3.Description of the algorithm
The?rst task is to?nd the?eld K.An easy way is to construct an element δ∈O k such thatδ>0andδ).Another way is to construct the?eld K using class?eld theory.Such a?eld has conductor A
v,where A runs through the integral ideals A,by increasing norm,then compute ker(Cl k(f)?Cl k)and check if it contains a subgroup of index 2whose conductor is A
v becomes complex.This algorithm uses the tools of[6].
1.Set n←
2.
https://www.doczj.com/doc/1f4868672.html,pute the integral ideals A1,...,A m of norm n.Set c←1.
3.If c>m then set n←n+1and go back to step2.Otherwise,set f←A c
4HENRI COHEN AND XA VIER-FRANC ?OIS ROBLOT
complex plane and are related to the partial zeta functions by the formula
ζK/k (s,σ)=1
χ(σ),(?)where the sum is taken over all characters of G .
Let χbe a character of G and let τdenote the non-trivial automorphism of the quadratic extension K/H k .If χ(τ)=1,the functional equation implies that
L ′K/k (0,χ)=0;hence χwill not contribute to the value of ζ′
K/k (0,σ)in (?).Thus from now on we assume that χ(τ)=?1.We extend χto all ideals of k by setting χ(a )=0if a is not coprime with the conductor f χof χ.To each character χis associated a canonical L -function de?ned for s ∈C with Re(s )>1by
L (s,χ):=
p
(1?χ(p )N p ?s )?1,
where the product is taken over all prime ideals of k .
Lemma 3.2.Let χbe a character such that χ(τ)=?1.Then f χ=f .In particular,
L K/k (s,χ)=L (s,χ).
Proof.Let K χbe the sub?eld of K ?xed by the kernel of χ.By de?nition the conductor of K χis equal to f χ.It is clear that the conductor of H k K χis also equal to f χ,and moreover H k K χ=K since K χis not included in H k ;thus f χ=f .We set
Λ(s,χ):=C s Γ(s/2)Γ
s +1
d k N f and Γ(z )is th
e classical gamma function.This function
satis?es the fundamental functional equation
Λ(1?s,χ)=W (χ)Λ(s,
2
.
De?ne the following two quantities:
T (χ):=
N
n =1
a n (
2e
?2/x
and f 2(x ):=Ei (2/x ),where Ei (x )= +∞
x
e ?t dt/t is the
exponential integral function.Then
L ′(0,χ)=S (χ)+W (χ)T (χ)+κ,
where the error term κis smaller than κ.
COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS 5
Proof.Letting s tend to 1in the functional equation gives
L ′(0,χ)=W (χ)Λ(1,
2
√χ)=
n ≥1
W (χ)a n (χ)f (C/n,0)
,
where the function f is de?ned by
f (x,s ):=
1
2
π
x ?z
Γ(z )
π
x
?z
Γ(z )dz +sf (x,s ).
We solve the di?erential equation and ?nd that
f (x,s )=x s +∞
1/x
t s ?1F (t )dt,
where
F (t ):=
2
√2iπ σ+i ∞
σ?i ∞
(2t )?z Γ(z )dz.But the theory of Mellin transforms (see for example [20],Chapter 4)tells us that F (t )=2
√
πf 1(x )and f (x,0)=2√
6HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT 3c.If p splits:write p O k=p p),set
φ(m)=χ(p)m+1?χ(
χ(p)?χ(
2n
e?2n/C,the algorithm is very simple.
Algorithm3.5.Let A>0be a real number and let N≥1be an integer.This algorithm computes the values of f1(A/n)for1≤n≤N.
1.Set V←e?2/A,V1←AV/2,U1←V1and n←
2.
2.While n≤N,set
U n←U n?1·V,V n←U n
x
e?xA,and more generally for all m≥1we have the induction formula φ(m+1)(x)=?1
2!φ′′(N)?
1
4!
φ(4)(N)?...
where the derivativesφ(m)(N)can be computed by the previous lemma.Moreover, since(?1)m1
COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS7
3.If|s|>κthen set F n?1←F n?1+s,s←d f1,f0←?Af0,
f1←?1
v for odd characters.
The following result is a special case of a theorem due to Landau. Proposition3.8.Letχbe an odd character of G.Choose an elementλ∈f0such that
μ>0and the integral ideal h=μg?1is coprime to f0.De?ne the Gauss sum
G(χ)=χ
β>0.Then
W(χ)=?i G(χ) N f0.
This yields the following algorithm.
Algorithm3.9.Letχbe an odd character of G.This algorithm computes the Artin root number W(χ)attached to this character.
https://www.doczj.com/doc/1f4868672.html,pute an elementλ∈f0such that
μ>0andμ+ν=1(note that g and f0are coprime by construction).Set h←(μ)g?1.
3.Let{α1,...,αr}be elements of O k,and let d r|d r?1|···|d1be positive integers such that
8HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT
4.For all tuples(i1,...,i r)such that0≤i1 √√ 5.Let W←(?i)χ(h d k N f,N← ?C logκ h j . βj|≤2j We use the following algorithm to recover an integer of k given by an approximation and a bound for its conjugate(recall that?x?,?x?and?x?denote respectively the ?oor,the ceiling and the closest integer to x∈R). Algorithm3.11.Let βbe a real number and letκ>0and B>0be two positive real numbers.This algorithm?nds,if it exists,aβ∈O k such that| β?β|<κand | ωand set?←ω?? and b max←b+2 B+κ COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS9 3.Setβ←a+bω,if| β?β|<κand| ω We are now able to give the complete algorithm. Algorithm3.12.Let k be a quadratic real number?eld.Under the hypothesis of Theorem2.1,this algorithm computes the irreducible polynomial over k of a generating element of H k. https://www.doczj.com/doc/1f4868672.html,ing Algorithm3.1,?nd a modulus f and a congruence group H of conductor f such that the corresponding?eld K veri?es the hypothesis of Section2. 2.Setκ←10?20·e??√ βj|≤2j h j .If it is possible then return the polynomial X h+βh?1X h?1+...+β0 and terminate the algorithm.Otherwise,increase the precision by setting for ex-ampleκ←κ2,and go back to step3. Remark.As we said above,heuristics show that the conjugates ofαare mostly of the size of exp √ 10HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT only linear factors if H/k is Galois.Since every such linear factor corresponds to a k-automorphism of H,we can check if the extension is Abelian by proving that they commute with each other. However,once we have proved that the extension H/k is a Galois extension,it is possible to be more e?cient for small values of h k,since there are only a few possibilities for the Galois group Gal( H/k).Another possibility is to use a result of Bach and Sorenson[1]which gives under GRH an upper bound for the norm of the prime ideals generating the norm group of an Abelian extension.Indeed,this result enables one to write an algorithm which,under GRH,does prove that an extension is Abelian(without having to prove?rst that it is Galois)and computes at the same time its norm group(see[17]for details). We now give an algorithm using the?rst method described above,which does not use GRH. Algorithm4.1.Let P(X)be a polynomial of degree h k and with coe?cients in O k.This algorithm proves(or disproves)that a root of P(X)generates the Hilbert class?eld of k. 1.Check if P(X)is irreducible over k[X].If this is not the case then output a message saying that P does not generate an extension of degree h k of k and terminate the algorithm. 2.Letθbe a root of P and let H denote the?eld k(θ).Compute the minimal polynomial ofθover Q and check if H is totally real using Sturm’s algorithm(see [3],Algorithm4.1.11).If this is not the case then return a message saying that H/k is rami?ed at the in?nite places and terminate the algorithm. https://www.doczj.com/doc/1f4868672.html,pute the relative discriminant of H/k using the algorithm given in[5]. If it is di?erent from O k,then output a message saying that H/k is rami?ed at the?nite places and terminate the algorithm.Otherwise,if h k=2or3return a message saying that H=H k and terminate the algorithm. https://www.doczj.com/doc/1f4868672.html,pute the factorization of P(X)in H[X].If P does not admit only linear factors then output a message saying that H/k is not a Galois extension and terminate the algorithm.Otherwise,if h k=4or h k is a prime number return a message saying that H=H k and terminate the algorithm. 5.Let X?S j(Y)∈k[X,Y]be such that P(X)= 1≤j≤h k(X?S j(θ)) is the factorization of P in H[X].For all1≤i 5.An example The algorithm presented in this paper has been implemented as part of the new version of the PARI/GP[2]package.The quadhilbert function uses complex multiplication to compute the Hilbert class?eld of complex quadratic?elds,and the present algorithm for real quadratic?elds.The following example was treated using this implementation. COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS11 √ Let k be the real quadratic?eld generated byω:= ψ=ψ7, S(ψ),T(ψ7)=S(ψ3),T(ψ5)= W(ψ), W(ψ5)=W(ψ).So we compute the corresponding L-functions,and obtain ζ′K/k(0,σ)≈7.25654406363900,ζ′K/k(0,σ5)=?ζ′K/k(0,σ), ζ′K/k(0,σ2)≈?0.944193530444349,ζ′K/k(0,σ6)=?ζ′K/k(0,σ2), ζ′K/k(0,σ3)≈2.94813989197904,ζ′K/k(0,σ7)=?ζ′K/k(0,σ3), ζ′K/k(0,σ4)≈1.92921444495667,ζ′K/k(0,1)=?ζ′K/k(0,σ4). We then compute the values of the conjugates ofαover k,and we form its irreducible polynomial X4?2009298.2915480506125X3+839444123.58478759370X2 ?40221955871.313705629X+234161017552.69584759 which,using Algorithm3.11,is seen to be very close to the polynomial √438+419722059)X2 X4+(?48004 √438+117080508780). +(?960939696 A relative reduction process gives the following simpler polynomial de?ning the same?eld extension: √438+22)X+(?3√ X4+2X3+( 12HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT Finally,since k/Q is a cyclic extension,it is possible to?nd a?eld L of degree4 such that k∩L=Q and kL=H k(see[7]).In fact,any sub?eld L of H k of degree h k over Q and disjoint from k will work.In order to?nd such a?eld,one can use the algorithm for sub?eld computation given in[12],or use the method explained in[4],which gives only some sub?elds.In our example,we?nd that such a?eld is generated by a root of X4?2X3?5X2+6X+3. Appendix.Tables of Hilbert class fields For each of the607real quadratic?eld k of discriminant less than2000,we give a polynomial de?ning a?eld L k over Q such that the Hilbert class?eld of k is the compositum of k and L k.For the sake of completeness,we recall the list of the319?elds k with class number equal to1,for which trivially L k=Q. Discriminant of the?elds with h k=1 813212833 4456617377 9297109124133 149157172177184 197209217236241 253269281293309 329337344353376 393409413421433 453461489501509 524537553557573 593601613632641 653664669677701 716721749757769 789797813824844 856869881893913 929937953973989 10131033104810521061 10811097111211211133 11491169118112011213 12371249127312891301 13241333133713571381 13971409143314411457 14731481149715161529 15491561157715921609 16331657166916761689 17091721173317531777 17931801181718291841 18611873188919091913 19411949196919771993 COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS13 First,there are70real quadratic?elds k of discriminant less than2000with class number2and such that L k=Q( √ 4065105140185 265285345380440 460485565645685 7608608859651065 10851180120512451285 14051465154515801605 16451685186519051965 2). Discriminant of the?elds k such that h k=2and d L k =8 136232296456552616 712776872106411921416 15761672183218961992 There are14real quadratic?elds k of discriminant less than2000with class number2and such that L k=Q( √ 156348492732 1068130816441884 There are26real quadratic?elds k of discriminant less than2000with class number2and such that L k=Q( √ 221312377481572 728949100111571209 1261146917291833 There are21real quadratic?elds k of discriminant less than2000with class number2and such that L k=Q( √ 3574765617489691173 12411496156416491853 There remains29?elds k with class number2and such that the discriminant d L k is larger than17.We give them in a single table containing?rst the discriminant of k,and then the discriminant of d L k ,ordered by increasing value of d L k . Discriminant and d L k for the?elds k such that h k=2and d L k >17 21861211281211869 2488824127224812 28114828957291189 291537291653291353 33151737196141 14HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT polynomial de?ning the?eld L k. Discriminants of the?elds K such that h K=3and polynomials for L K X3?4X?1257 X3?X2?4X+2321 X3?X2?5X+4473 X3?X2?6X?2733 X3?X2?6X?1892 X3?X2?6X+31016 X3?X2?9X+121229 X3?X2?8X+91304 X3?8X?51436 X3?X2?10X?71509 X3?X2?12X+81901 X3?X2?10X+131957 145X4?2X3?3X2+2X+1 445X4?2X3?4X2+5X+5 520X4?6X2+4 689X4?2X3?4X2+5X+1 780X4?X3?6X2+8X?1 840X4?7X2?6X+1 897X4?2X3?4X2+5X+2 905X4?5X2+1 1020X4?X3?8X2+X+11 1096X4?9X2+4 1145X4?6X2+4 1164X4?X3?10X2+X+1 1288X4?X3?11X2+12X+8 1313X4?6X2+4 1365X4?6X2+4 1560X4?6X2+4 1677X4?2X3?7X2+6X+9 1740X4?X3?10X2+2X+19 1752X4?9X2+4 1848X4?9X2+4 1932 Finally,there are29real quadratic?elds with class number ranging from5to11 and discriminant less than2000.In the following table,we give their discriminants COMPUTING THE HILBERT CLASS FIELD OF REAL QUADRATIC FIELDS15 together with a polynomial de?ning the?eld L k. Discriminants of the?elds K such that h K≥5and polynomials for L K X5?X4?5X3+4X2+3X?1 577 X6?3X5?3X4+11X3?X2?5X+1 785 X5?X4?6X3+5X2+3X?1 904 X6?3X5?5X4+14X3+9X2?15X?5 985 X7?X6?9X5+2X4+21X3+X2?13X?1 1093 X9?3X8?10X7+38X6+5X5?107X4+58X3+78X2 X11?5X10?4X9+54X8?53X7?127X6+208X5+69X4 X6?3X5?8X4+16X3+24X2?5 1384 X5?X4?7X3+6X2+3X?1 1429 X8?2X7?13X6+16X5+43X4?10X3?34X2?4X+4 1601 X5?X4?10X3+X2+21X+9 1705 X6?3X5?8X4+21X3?6X2?5X+1 1756 X7?2X6?14X5+14X4+50X3?22X2?51X?3 1765 X8?4X7?6X6+32X5?5X4?48X3+14X2+16X?4 1785 X5?X4?13X3+8X2+27X+1 1937 X5?9X3?4X2+10X+4 These computations were done on a Pentium Pro200with256Mb of RAM.The total computation time(including class group computations,computations of the generating element,reduction of the result and computation of the?eld L k)took about21minutes.Note that actually the last two steps(reduction and computation of the?eld L k)represented more than70%of the whole computation time. All these?elds have of course been veri?ed using Algorithm4.1. References 1.E.Bach,J.Sorenson,Explicit Bounds for Primes in Residue Classes,https://www.doczj.com/doc/1f4868672.html,p.65(1996), 1717–1735MR97a:11143 2.C.Batut,K.Belabas,D.Bernardi,H.Cohen,M.Olivier,User Guide to PARI/GP version 2.0.1,1997 3.H.Cohen,A Course in Computational Number Theory,GTM138,Springer-Verlag,1993 MR94i:11105 4.H.Cohen,F.Diaz y Diaz,A Polynomial Reduction Algorithm,S′e m.Th.Nombres de Bordeaux (S′e rie2)3(1991),351–360MR93a:11107 16HENRI COHEN AND XA VIER-FRANC?OIS ROBLOT 5.H.Cohen,F.Diaz y Diaz,M.Olivier,Algorithmic Techniques for Relative Extensions of Number Fields,preprint A2X(1997) 6.H.Cohen,F.Diaz y Diaz,M.Olivier,Computing Ray Class Groups,Conductors and Dis- criminants,https://www.doczj.com/doc/1f4868672.html,p.67(1998),773–795MR98g:11128 7.G.Cornell,M.Rosen,A Note on the Splitting of the Hilbert Class Fields,J.Number Theory 28(1988),152–158MR89f:11156 8.D.Dummit,B.Tangedal,Computing the Leading Term of an Abelian L-function,ANTS III (Buhler Ed.),Lecture Notes in Computer Sci.1423(1998),p.400–411 9.C.Fieker,Computing Class Fields via the Artin Map,preprint,1997 10.E.Friedman,Hecke’s Integral Formula,S′e m.Th.Nombres de Bordeaux,Expos′e No.5(1987- 1988)MR90i:11136 11.M.Ishida,The Genus Fields of Algebraic Number Fields,LN in Math.555,Springer-Verlag, 1976MR55:7990 12.J.Kl¨u ners,M.Pohst,On Computing Sub?elds,J.Symbolic Comp.24(1997),385–397MR 98k:11161 13.J.Martinet,Character Theory and Artin L-functions,in Algebraic Number Fields(A. Fr¨o hlich,ed.),Academic Press,London,1977,1–87MR56:5502 14.J.Neukirch,Algebraische Zahlentheorie,Springer-Verlag,Berlin,1992 15.M.Daberkow,M.Pohst,Computations with Relative Extensions of Number Fields with an Application to the Construction of Hilbert Class Fields,Proc.ISAAC’95,ACM Press,New-York1995,68–76 16.M.Pohst,H.Zassenhaus,Algorithmic Algebraic Number Theory,Cambridge University Press, Cambridge,1989MR92b:11074 17.X.-F.Roblot,Stark’s Conjectures and Hilbert’s Twelfth Problem,preprint;Algorithmes de Factorisation dans les Extensions Relatives et Applications de la Conjecture de Stark`a la Construction des Corps de Classes de Rayon,Thesis,Universit′e Bordeaux I(1997) 18.R.Schertz,Probl`e mes de Construction en Multiplication Complexe,S′e m.Th.Nombres Bor- deaux(1992),239–262MR94c:11051 19.R.Sharma and B.Zohuri,A General Method for an Accurate Evaluation of Exponential Integrals E1(x),x>0,https://www.doczj.com/doc/1f4868672.html,put.Phys.25(1977),199–204MR57:14339 20.I.N.Sneddon,The Use of Integral Transforms,Mc Graw-Hill,New York,1972 21.H.M.Stark,Values of L-functions at s=1.I.L-functions for quadratic forms,Advances in Math.7(1971),301–343;II.Artin L-functions with Rational Characters,ibid.17(1975),60–92;III.Totally Real Fields and Hilbert’s Twelfth Problem,ibid.22(1976),64–84;IV.First Derivatives at s=0,ibid.35(1980),197–235MR44:6620;MR52:3082;MR55:10427; MR81f:10054 22.J.T.Tate,Les Conjectures de Stark sur les Fonctions L d’Artin en s=0,Progress in Math. 47,Birkha¨u ser,Boston,1984MR86e:11112 23.R.Terras,The Determination of Incomplete Gamma Functions through Analytic Integration, https://www.doczj.com/doc/1f4868672.html,put.Phys.31(1979),146–151MR81d:65010 24.R.Terras,Generalized Exponential Operators in the Continuation of the Con?uent Hyperge- ometric Functions,https://www.doczj.com/doc/1f4868672.html,put.Phys.44(1981),156–166MR82m:33003 Laboratoire A2X,Universit′e Bordeaux I,351cours de la Lib′e ration,33405Talence Cedex,France E-mail address:cohen@math.u-bordeaux.fr Laboratoire A2X,Universit′e Bordeaux I,351cours de la Lib′e ration,33405Talence Cedex,France Current address:Department of Computer Science,Concordia University,1455de Maison-neuve Blvd West,Montreal,Quebec,H3G1M8 E-mail address:roblot@cs.concordia.ca
相关主题
文本预览