Hilbert Class Field Computations¶
Example Hilbert Class Field Computations using Shimura’s Reciprocity Law
Chapter 9 of [Her2021] describes the computation of Hilbert class fields of quadratic imaginary number fields using Shimura’s reciprocity law. This file contains three detailed examples of such computations.
Each of these three examples also features in [GS1998]. That paper performs a
very similar computation, except that it translates the idèlic results from
Shimura to statements about ideals, in order to perform their computations using
ideals. In contrast, we will perform the computation using idèles directly,
namely using Ideles and the related adèlic classes
Adeles and
ProfiniteNumbers.
REFERENCES:
[Her2021] Mathé Hertogh, Computing with adèles and idèles, master’s thesis, Leiden University, 2021.
[GS1998] Alice Gee, Peter Stevenhagen, Generating class fields using Shimura reciprocity, 1998. In: Buhler J.P. (eds) Algorithmic Number Theory. ANTS 1998. Lecture Notes in Computer Science, vol 1423. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054883
Example 1¶
The first example will be the computation of the Hilbert class field \(H\) of \(K = \QQ(\sqrt{-71})\), using the cube root \(\gamma_2\) of the \(j\)-invariant with \(\gamma_2(i) = 12\) as our modular function. The ring of integers \(O\) of \(K\) is generated by \(\theta = -\frac{1}{2} + \frac{1}{2}\sqrt{-71}\), which has minimal polynomial \(X^2+X+18\).
We start with loading our code and initilizing our quadratic imaginary number field together with its idèle group. We embed \(K\) in \(\CC\) such that \(\theta\) lies in the upper half plane.
sage: from adeles.all import *
sage: R = ZZ['X']; X = R.gen()
sage: K.<theta> = NumberField(X**2+X+18, embedding=-0.5+4.2*I)
sage: K.discriminant() # Check that we have the correct field QQ(sqrt(-71))
-71
sage: O = K.maximal_order()
sage: O.basis() # Check that theta indeed generates the ring of integers
[1, theta]
sage: J = Ideles(K)
Finding a class invariant¶
Now we want to compute our class invariant. As \(\gamma_2\) is a modular function of level \(3\) that does not have a pole at \(\theta\), the theory of complex multiplication tells us that \(\gamma_2(\theta) \in H_3\), where \(H_3\) is the ray class field of \(K\) modulo \(3\). By explicitly computing the action of \(Gal(H_3/H)\) on \(\gamma_2(\theta)\), we will try to find a class invariant of small height.
The Artin map induces an isomorphism \((O/3O)^*/O^* \to Gal(H_3/H)\). So we compute generators of \((O/3O)^*/O^*\):
sage: Omod3 = O.quotient_ring(3, 'b')
sage: Omod3star = K.ideal(3).idealstar(flag=2) # flag=2 means compute generators
sage: Omod3star.gens_values()
(-theta + 1, theta - 1)
We see that \((O/3O)^*/O^*\) is generated by (the image of) \(\theta-1\). Hence the action of \(Gal(H_3/H)\) is determined by the action of the idèle corresponding to \(\theta-1 \mod 3\). Let us create this idèle.
sage: u = J(Omod3(theta-1)); u
Idèle with values:
infinity_0: CC^*
(3, theta): -1 * U(1)
(3, theta + 1): -theta * U(1)
other primes: 1 * U(0)
Write \(R_0(u)\) for the finite represented subset of u. By Shimura’s
reciprocity law we now have for any \(x \in R_0(u)\) that \(\gamma_2(\theta)^x =
\gamma_2^{g_\theta(x)^{-1}}(\theta)\), where \(x\) acts via the Artin map and
\(g_\theta: \hat{K}^* \to GL_2(\hat{\QQ})\) denotes Shimura’s connecting
homomorphism.
We compute an \(A \in GL_2^+(\QQ)\) and an approximation to a \(B \in GL_2(\hat{\ZZ})\) such that there exists an \(x \in R_0(u)\) with \(g_\theta(x)^{-1} = BA\).
sage: B, A = factored_shimura_connecting_homomorphism(u.inverse(), 3); B, A
(
[ 1 mod 3 36 mod 54] [1 0]
[ 1 mod 3 17 mod 54], [0 1]
)
As \(A\) is the identity matrix, it acts trivially on \(\gamma_2\). The action of \(B\) on \(\gamma_2\) depends only on the reduction \(B_3\) of \(B\) modulo \(3\).
sage: B_3 = matrix_modulo(B, 3); B_3
[1 0]
[1 2]
We factor \(B_3\) as \(B_3 = (1, 0; 0, d) \cdot U\) for some \(U \in SL_2(\ZZ/3\ZZ)\) and then write \(U\) in terms of the standard generators \(S = (0, -1; -1, 0)\) and \(T = (1, 1; 0, 1)\) of \(SL_2(\ZZ)\).
sage: d = det(B_3); d
2
sage: U = diagonal_matrix([1, 1/d]) * B_3; U
[1 0]
[2 1]
sage: STs = ST_factor(U); STs
(S^3*T^-1*S)^2
Now \((1, 0; 0, d)\) acts as \(d \in (\ZZ/3\ZZ)^*\) on the Fourier coefficients of \(\gamma_2\) and one can check that this action is trivial. One can also check that the action of the standard generators \(S\) and \(T\) by linear fractional transformations is given by \(\gamma_2^S = \gamma_2\) and \(\gamma_2^T = \zeta_3^{-1} \gamma_2\), with \(\zeta_3 = \exp(2 \pi i/3)\).
Putting this all together we optain the action of \(B_3\) on \(\gamma_2\).
sage: print_action_on_gamma_2(B_3)
gamma_2 ]--> zeta_3^2 * gamma_2
As \(\det(B_3) = 2 \in (\ZZ/3\ZZ)^*\), we also have \(\zeta_3^{B_3} = \zeta_3^2\). It follows that \(\zeta_3 \gamma_2\) is left invariant under \(B_3\) and hence, by the considerations above, \(\alpha := \zeta_3 \gamma_2(\theta)\) is left invariant under \(Gal(H_3/H)\), i.e. \(\alpha \in H\). This is are candidate class invariant.
Computing the minimal polynomial¶
We want to compute the minimal polynomial \(h \in K[X]\) of \(\alpha\). This will tell us whether or not \(\alpha\) is a class invariant and if so, give us a (hopefully small) defining equation for the Hilbert class field \(H\) of \(K\).
Write \(C\) for the set of conjugates of \(\alpha\) over \(K\). Then we have \(h = \prod_{\beta \in C} (X - \beta)\), so we want to compute \(C\). We have \(C = \{\alpha^\sigma \mid \sigma \in Gal(H/K)\}\). The Artin map induces an isomorphism \(Cl \to Gal(H/K)\) for \(Cl\) the ray class group modulo \(1\). Hence we first compute \(Cl\).
sage: Cl = ray_class_group(K, Modulus(K.ideal(1), [])); Cl
Narrow class group of order 7 with structure C7 of Number Field in theta with defining polynomial X^2 + X + 18
sage: Cl.gen().ideal()
Fractional ideal (2, theta)
We see that \(Cl\) is generated by the class \([p_2]\) of the prime ideal \(p_2 = 2 O + \theta O\). We construct the idèle \(v\) corresponding to \([p_2]\), which satisfies that the image in \(Cl\) of the represented subset of \(v\) is \(\{[p_2]\}\).
sage: v = J(Cl.gen()); v
Idèle with values:
infinity_0: CC^*
(2, theta): theta * U(0)
other primes: 1 * U(0)
Now for every \(y \in R_0(v)\) we have \(\alpha^{[p_2]} = \alpha^y\), both acting via the Artin map. By Shimura’s reciprocity law, we have \(\alpha^y = (\zeta_3 \gamma_2)^{g_\theta(y)^{-1}}(\theta)\). Hence similar to before we compute:
sage: B, A = factored_shimura_connecting_homomorphism(J(1)/v, 3); B, A
(
[8 mod 12 5 mod 6] [1/2 1/2]
[3 mod 12 4 mod 6], [ 0 1]
)
sage: B_3 = matrix_modulo(B, 3); B_3
[2 2]
[0 1]
sage: d = det(B_3); d
2
sage: U = diagonal_matrix([1, 1/d]) * B_3; U
[2 2]
[0 2]
sage: U_lift = SL2Z(lift_matrix_to_sl2z(U.list(), 3)); U_lift
[-1 -1]
[ 0 -1]
sage: V = U_lift * A; V
[-1/2 -3/2]
[ 0 -1]
Now we have \(\alpha^{[p_2]} = \zeta_3^d \gamma_2(V \theta)\) where \(V\) acts by fractional linear transformations. As we know \(d\) and \(V\) explicitly, we can numerically evaluate this expression.
sage: tau = apply_fractional_linear_transformation(V, theta)
sage: beta = CC.zeta(3)**d.lift() * gamma_2(tau); beta
-0.0365010349950268 + 82.4277120032277*I
This provides us our first conjugate of \(\alpha\). Of course another one is obtained easily as well, namely \(\alpha\) itself:
sage: alpha = CC.zeta(3) * gamma_2(theta); alpha
-6794.32787938645 - 3.18323145620525e-12*I
sage: C = set([alpha, beta])
Note that these two approximations already tell us that \(\alpha\) is indeed a class invariant: we have \(K \subset K(\alpha) \subset H\) and \(H/K\) is of degree \(7\), so the fact that \(\alpha\) has two distinct conjugates over \(K\) implies \(K(\alpha) = H\).
To compute the minimal polynomial \(h\) of \(\alpha\) over \(K\) we need approximations to the other conjugates of \(\alpha\) as well. We compute them the same way as we did above.
sage: for n in range(2, 7):
....: v = J(Cl.gen()**n)
....: B, A = factored_shimura_connecting_homomorphism(J(1)/v, 3)
....: B_3 = matrix_modulo(B, 3)
....: d = det(B_3)
....: U = diagonal_matrix([1, 1/d]) * B_3
....: U_lift = SL2Z(lift_matrix_to_sl2z(U.list(), 3))
....: V = U_lift * A
....: tau = apply_fractional_linear_transformation(V, theta)
....: C.add(CC.zeta(3)**d.lift() * gamma_2(tau))
....:
sage: C
{-6794.32787938645 - 3.18323145620525e-12*I,
-0.0365010349950410 - 82.4277120032278*I,
-0.0365010349950268 + 82.4277120032277*I,
6.37327655672568 - 3.45837454755243*I,
6.37327655672568 + 3.45837454755240*I,
18.3271641714828 - 6.03184683115439*I,
18.3271641714828 + 6.03184683115437*I}
From these approximations we compute an approximation to \(h\):
sage: h_approx = prod([(X - conjugate) for conjugate in C]); h_approx
X^7 + (6745.00000000003 + 3.32534000335727e-12*I)*X^6 + (-327467.000000002 + 9.31322574615479e-10*I)*X^5 + (5.18571150000002e7 - 2.98023223876953e-8*I)*X^4 + (-2.31929975100002e9 + 2.35438346862793e-6*I)*X^3 + (4.12645825130003e10 - 0.0000805854797363281*I)*X^2 + (-3.07873876442003e11 + 0.00102996826171875*I)*X + 9.03568991567007e11 - 0.00415039062500000*I
From these coefficients we clearly recognize an integral polynomial, with entries in \(\ZZ\) even; the imaginary parts of \(h_{approx}\) are almost zero:
sage: all([c.imag().abs() < 0.01 for c in h_approx])
True
The corresponding integral polynomial is:
sage: h = R([ZZ(c.real().round()) for c in h_approx]); h
X^7 + 6745*X^6 - 327467*X^5 + 51857115*X^4 - 2319299751*X^3 + 41264582513*X^2 - 307873876442*X + 903568991567
We conclude that for the polynomial \(h\) above, we have \(H \cong K[X]/(f)\). Note that this polynomial is significantly smaller than the “standard” Hilbert class polynomial:
sage: K.hilbert_class_polynomial()
x^7 + 313645809715*x^6 - 3091990138604570*x^5 + 98394038810047812049302*x^4 - 823534263439730779968091389*x^3 + 5138800366453976780323726329446*x^2 - 425319473946139603274605151187659*x + 737707086760731113357714241006081263
The above polynomial is obtained as the minimial polynomial of \(j(\theta)\) for \(j\) the \(j\)-invariant.
Note
Our polynomial \(h\) above is equal to the one in [GS1998], except for the sign at \(X^3\), indicating a typo in [GS1998].
Example 2¶
Our second example involves the same field \(K = \QQ(\sqrt{-71})\), but a
different modular function: we take Weber’s \(\mathfrak{f}_2\) modular function of
level \(48\) (cf. modular.weber_f2()).
Because \(\mathfrak{f}_2\) is of level \(48\), we compute generators of \((O/48O)^*/O^*\).
sage: Omod48 = O.quotient_ring(48, 'b')
sage: Omod48star = K.ideal(48).idealstar(flag=2)
sage: Omod48star.gens_values()
(-12*theta + 13,
12*theta - 23,
6*theta + 19,
-6*theta + 13,
-16*theta + 1,
16*theta + 17)
For each of these generators, we construct the corresponding idèle and compute its action on \(\mathfrak{f}_2\) and \(\zeta_{48} = \exp(2 \pi i / 48)\) via Shimura’s connecting homomorphism.
sage: for x in Omod48star.gens_values():
....: u = J(Omod48(x))
....: B, A = factored_shimura_connecting_homomorphism(J(1)/u, 48)
....: B_48 = matrix_modulo(B, 48)
....: C_48 = B_48 * A.change_ring(ZZ)
....: print("Action of {}:".format(x))
....: print_action_on_weber_f2(C_48)
....: print(" zeta_48 ]--> zeta_48^{}".format(det(B_48)))
....:
Action of -12*theta + 13:
f2 ]--> zeta48^84*f2
zeta_48 ]--> zeta_48^13
Action of 12*theta - 23:
f2 ]--> zeta48^84*f2
zeta_48 ]--> zeta_48^13
Action of 6*theta + 19:
f2 ]--> zeta48^66*f2
zeta_48 ]--> zeta_48^31
Action of -6*theta + 13:
f2 ]--> zeta48^18*f2
zeta_48 ]--> zeta_48^31
Action of -16*theta + 1:
f2 ]--> zeta48^80*f2
zeta_48 ]--> zeta_48^17
Action of 16*theta + 17:
f2 ]--> zeta48^32*f2
zeta_48 ]--> zeta_48^17
Above we use the fact that the computed matrices \(A\) all lie in \(SL_2(\ZZ)\), because Shimura’s connecting homomorphism maps \(\hat{O}^*\) to \(GL_2(\hat{\ZZ})\). Let us display the computed action above a bit more clearly in the following table. For \(k \in \ZZ_{>0}\), we write \(\zeta_k = \exp(2 \pi i / k)\).
\(x\) |
\(\zeta_{48}^x/\zeta_{48}\) |
\(\mathfrak{f}_2^x/\mathfrak{f}_2\) |
|---|---|---|
\(-12 \theta + 13\) |
\(\zeta_4^3\) |
\(\zeta_4\) |
\(12 \theta - 23\) |
\(\zeta_4^3\) |
\(\zeta_4\) |
\(6 \theta + 19\) |
\(\zeta_8^3\) |
\(\zeta_8^5\) |
\(-6 \theta + 13\) |
\(\zeta_8^3\) |
\(\zeta_8^5\) |
\(-16 \theta + 1\) |
\(\zeta_3^2\) |
\(\zeta_3\) |
\(16 \theta + 17\) |
\(\zeta_3^2\) |
\(\zeta_3\) |
We see that \(\zeta_{48} \mathfrak{f}_2\) is left invariant under all generators. Hence \(\alpha = \zeta_{48} \mathfrak{f}_2(\theta)\) is left invariant under \(Gal(H_{48}/H)\) and so \(\alpha \in H\).
We compute numerical approximations to the conjugates of \(\alpha\) over \(K\) and construct an approximation \(h_{approx}\) to the minimal polynomial \(h\) of \(\alpha\) over \(K\). This time we need more than the standard \(53\)-bits of precision and so we use \(100\) bits.
sage: CC = ComplexField(prec=100)
sage: C = set()
sage: for a in Cl:
....: B, A = factored_shimura_connecting_homomorphism(J(a), 48)
....: B_48 = matrix_modulo(B, 48)
....: d = det(B_48)
....: U = diagonal_matrix([1, 1/d]) * B_48
....: U_lift = SL2Z(lift_matrix_to_sl2z(U.list(), 48))
....: V = U_lift * A
....: tau = apply_fractional_linear_transformation(V, theta)
....: sign_f2 = -1 if d.lift() % 8 in [3, 5] else 1
....: C.add(CC.zeta(48)**d.lift() * sign_f2*weber_f2(tau, prec=100))
sage: h_approx = prod([(X - conjugate) for conjugate in C])
Again the coefficients of \(h_{approx}\) all have imaginary part allmost zero:
sage: all([c.imag().abs() < 1e-20 for c in h_approx])
True
We recognize the (very small) minimal polynomial \(h \in \ZZ[X]\) of \(\alpha\) over \(K\) as:
sage: h = R([ZZ(c.real().round()) for c in h_approx]); h
X^7 + X^6 - X^5 - X^4 - X^3 + X^2 + 2*X - 1
This is the same polynomial found in [GS1998].
Example 3¶
Our third and last example involves the field \(K = \QQ(\sqrt{-471})\) whose ring
of integers is generated by \(\theta = -\frac{1}{2} + \frac{1}{2}\sqrt{-471}\),
which has minimial polynomial \(X^2 + X + 118\). This example uses Weber’s modular
function \(\mathfrak{f}_2\) (cf. modular.weber_f2()).
We start by constructing \(K\) (embedded into \(\CC\) with \(\theta\) on the positive
imaginary axis) and its idèle group.
sage: K.<theta> = NumberField(X^2 + X + 118, embedding=-0.5+10.9*I)
sage: K.discriminant()
-471
sage: O = K.maximal_order()
sage: O.basis()
[1, theta]
sage: J = Ideles(K)
Next we compute the action of \(Gal(H_{48}/H)\) on \(\mathfrak{f}\) and \(\zeta_{48}\).
sage: Omod48 = O.quotient(48, 'b')
sage: Omod48star = K.ideal(48).idealstar(flag=2)
sage: for x in Omod48star.gens_values():
....: u = J(Omod48(x))
....: B, A = factored_shimura_connecting_homomorphism(J(1)/u, 48)
....: B_48 = matrix_modulo(B, 48)
....: C_48 = B_48 * A.change_ring(ZZ)
....: print("Action of {}:".format(x))
....: print_action_on_weber_f2(C_48)
....: print(" zeta_48 ]--> zeta_48^{}".format(det(B_48)))
....:
Action of 4*theta - 23:
f2 ]--> zeta48^124*f2
zeta_48 ]--> zeta_48^37
Action of -12*theta + 13:
f2 ]--> zeta48^84*f2
zeta_48 ]--> zeta_48^13
Action of -24*theta + 17:
f2 ]--> zeta48^24*f2
zeta_48 ]--> zeta_48^25
Action of 6*theta - 5:
f2 ]--> zeta48^18*f2
zeta_48 ]--> zeta_48^31
Action of -6*theta - 11:
f2 ]--> zeta48^66*f2
zeta_48 ]--> zeta_48^31
We summarize these results in the following table.
\(x\) |
\(\zeta_{48}^x/\zeta_{48}\) |
\(\mathfrak{f}_2^x/\mathfrak{f}_2\) |
|---|---|---|
\(4 \theta - 23\) |
\(\zeta_{12}^{31}\) |
\(\zeta_4^3\) |
\(-12 \theta - 13\) |
\(\zeta_4^3\) |
\(\zeta_4\) |
\(-24 \theta + 17\) |
\(\zeta_2\) |
\(\zeta_2\) |
\(-6 \theta - 11\) |
\(\zeta_8^3\) |
\(\zeta_8^5\) |
We see that \(\zeta_{16} \mathfrak{f}_2^3\) is left invariant under all generators. Hence \(\alpha = \zeta_{16} \mathfrak{f}_2^3(\theta) \in H\), as it is left invariant under \(Gal(H_{48}/H)\).
We compute the minimal polynomial of \(\alpha\) over \(K\) as before.
sage: Cl = ray_class_group(K, Modulus(K.ideal(1), []))
sage: C = set()
sage: for a in Cl:
....: B, A = factored_shimura_connecting_homomorphism(J(a), 48)
....: B_48 = matrix_modulo(B, 48)
....: d = det(B_48)
....: U = diagonal_matrix([1, 1/d]) * B_48
....: U_lift = SL2Z(lift_matrix_to_sl2z(U.list(), 48))
....: V = U_lift * A
....: tau = apply_fractional_linear_transformation(V, theta)
....: sign_f2 = -1 if d.lift() % 8 in [3, 5] else 1
....: C.add(CC.zeta(16)**d.lift() * sign_f2*weber_f2(tau, prec=100)**3)
....:
sage: h_approx = prod([(X - conjugate) for conjugate in C])
Again the imaginary parts of the coefficients of \(h_{approx}\) lie near zero:
sage: all([c.imag().abs() < 1e-8 for c in h_approx])
True
And we obtain the polynomial
sage: h = R([ZZ(c.real().round()) for c in h_approx]); h
X^16 + 6*X^15 + 62*X^14 - 106*X^13 + 382*X^12 - 942*X^11 + 4756*X^10 - 9629*X^9 + 18987*X^8 - 22281*X^7 + 36601*X^6 - 44222*X^5 + 60470*X^4 - 29217*X^3 + 4085*X^2 + 1775*X - 1
for which we have \(H \cong K[X]/(h)\). Again this polynomial is a lot smaller than the one obtained from the \(j\)-invariant:
sage: K.hilbert_class_polynomial()
x^16 + 407778921764211975870138302520*x^15 + 3038670026466389034174375356410562377980*x^14 + 166283649035293163892223950995038214787614607187102726207320*x^13 + 1239105834253481690958131671057246233275628887838001822867346860887030*x^12 + 44797353340751299573712910256682503747536265367214881959872320870897863091154*x^11 + 810567263265620329576875533282472560320845728181072489292583387055671192443893737892*x^10 + 428763471339093213649510095829304307139166477766352360735556993753303248962236501430574245*x^9 + 551473043901993149280796896099822581402624627798883643717202518930460973073901757847470313386009*x^8 - 2173004307152659310409985921885398494009923550238354733945001965717708945263362426633491401144494415*x^7 + 4082391158364853819568696794182067917024971322990393222310715567465711801418257301213552484408773408627183*x^6 - 33809233950512659615781751039981915421672207004165577744326580464904519862900013603681132637581479960297858710*x^5 + 192318969548058851552756744664691959935081474974687796736508706834400679745833139489829884550400808870445882886914*x^4 - 412114501584451807406990682227863134909939929331144168823710914342965136030803289793803741657821243637047663904695587*x^3 + 380823091101794086983979218290110745354995985354657257935542041508354314680412729764091385489540085125805257839099389531*x^2 - 169796844561266720706774333605228207016816015396255852564580389382199302145429348975497662909496897082101714028727358256787*x + 91940638625558460160208745666251339633209006005918537611868314018544115192949608574570709846273095191663462730164649941895793
Note
In our examples it was the case that the obtained polynomial actually lied
in \(\ZZ[X]\). In general one can recognize polynomials in \(K[X]\) from
numerical appoximations using the LLL-algorithm. One can for example use
the function recognize_polynomial() in polynomials.sage at
https://github.com/mstreng/recip/blob/master/recip/polynomials.sage.