Journal de Théorie des Nombres de Bordeaux

Kevin Keating

Wintenberger’s functor for abelian extensions

Jouni Parkkonen

Frédéric Paulin

On the closedness of approximation spectra

Mark Kisin

Integral canonical models of Shimura varieties

Ritabrata Munshi

Density of rational points on cyclic covers of $\mathbb{P}^n$

Frédéric A. B. Edoukou

The weight distribution of the functional codes defined by forms of degree 2 on Hermitian surfaces

Joël Rivat

Joël RIVAT
On Gelfond’s conjecture about the sum of digits of prime numbers
Tome 21, no 2 (2009), p. 415-422.
<http://jtnb.cedram.org/item?id=JTNB_2009__21_2_415_0>
© Université Bordeaux 1, 2009, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir la
présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 21 (2009), 415-422
On Gelfond’s conjecture about
the sum of digits of prime numbers
par Joël RIVAT
Résumé. Dans cet article nous exposons les étapes importantes
de la preuve de la conjecture de Gelfond [6] (1968) dans un travail
récent en collaboration avec Christian Mauduit [11] concernant
la somme des chiffres des nombres premiers, dans l’esprit de l’ex-
posé donné à Edimbourg dans le cadre des Journées Arithmétiques
2007.
Abstract. The goal of this paper is to outline the proof of a
conjecture of Gelfond [6] (1968) in a recent work in collaboration
with Christian Mauduit [11] concerning the sum of digits of prime
numbers, reflecting the lecture given in Edinburgh at the Journées
Arithmétiques 2007.
1. The sum of digits function
Let q ∈ N with q > 2. All n ∈ N can be written uniquely in basis q:
n =
∑
k>0
nkq
k where nk ∈ {0, . . . , q − 1}
and the sum of digits function is defined by:
s(n) =
∑
k>0
nk.
The sum of digits function has many aspects that have been studied, for
instance ergodicity, finite automata, dynamical systems, number theory.
Mahler introduced this function in the context of harmonic analysis:
Theorem A (Mahler [10], 1927). For q = 2, the sequence(
1
N
∑
n<N
(−1)s(n) (−1)s(n+k)
)
N>1
converges for all k ∈ N and its limit is different from zero for infinitely
many k’s.
The origin of our work is the following result of Gelfond:
416 Joël Rivat
Theorem B (Gelfond [6], 1968). Let m > 2, (m, q − 1) = 1. Then there
exists λ < 1 such that for all d ∈ N∗, a, r ∈ Z,∑
n<N
n≡r mod d
s(n)≡a mod m
1 =
N
md
+ O(Nλ).
In the same paper Gelfond pose the following problem:
Problem A (Gelfond [6], 1968).
Il serait aussi intéressant de trouver le nombre des nombres
premiers p 6 x tels que s(p) ≡ a mod m.
(the letter p always denotes a prime number).
2. Prime numbers
The prime numbers constitute a fascinating sequence which poses many
difficult questions. Let us mention some open problems:
• are there infinitely many primes of the form p + 2 (prime twins)?
• are there infinitely many primes of the form n2 + 1?
• are there infinitely many primes of the form 2n − 1 (Mersenne
primes)?
• are there infinitely many primes of the form 22n+1 (Fermat primes)?
and some answers:
• primes of the form an + b (Dirichlet theorem),
• primes such that αp belongs to some prescribed interval I ⊂ [0, 1],
for α ∈ R \Q (Vinogradov theorem [15]),
• primes of the form bncc where 1 < c < c0 ≈ 1.1 (Piatetski-Shapiro
theorem [12]),
• primes of the form a2 + b4 (Friedlander-Iwaniec theorem [4, 5]),
• primes of the form a3 + 2b3 (Heath-Brown theorem [9]),
• primes such that ap(E)/(2
√
p) belongs to some prescribed interval
I ⊂ [0, 1] (Sato-Tate conjecture for a very large class of elliptic
curves E over Q, recently proved by several authors).
3. Historical background
Until recently, very little was known concerning the digits of prime num-
bers. We can mention a result of Sierpiński [13] (1959), recently generalized
by Wolke [16] (2005) and then by Harman [7] (2006), on prime numbers
with some prescribed digits.
Concerning Gelfond’s question, no progress was made in its original form.
Let us mention the two following variants:
The sum of digits of prime numbers 417
Theorem C (Fouvry–Mauduit [2, 3], 1996). For m > 2 such that
(m, q − 1) = 1, there exists C(q, m) > 0 such that for all a ∈ Z and x > 0,∑
n6x
n=p or n=p1p2
s(n)≡a mod m
1 >
C(q, m)
log log x
∑
n6x
n=p or n=p1p2
1.
Theorem D (Dartyge–Tenenbaum [1], 2005). For m > 2 with (m, q−1) =
1 and r > 2, there exists C(q, m, r) > 0 such that for all a ∈ Z and x > 0,∑
n6x
n=p1...pr
s(n)≡a mod m
1 >
C(q, m, r)
log log x log log log x
∑
n6x
n=p1...pr
1.
4. Results
Theorem 1 (Mauduit-Rivat). For α ∈ R such that (q− 1)α ∈ R \Z, there
exists C(q, α) > 0 and σq(α) > 0,∣∣∣∣∣∣
∑
p6x
e(α s(p))
∣∣∣∣∣∣ 6 C(q, α) x1−σq(α)
where e(t) = exp(2iπt).
Corollary 1. The sequence (α s(pn))n>1 is equidistributed modulo 1 if and
only if α ∈ R \Q (here (pn)n>1 denotes the sequence of prime numbers).
Corollary 2. For m > 2 such that (m, q − 1) = 1 and a ∈ Z,∑
p6x
s(p)≡a mod m
1 ∼ 1
m
∑
p6x
1 (x → +∞).
5. Sum over prime numbers
We want to estimate a sum of the form∑
p6x
g(p)
where the function g detects the property under consideration. A classical
process (Vinogradov [15], Vaughan [14], Heath-Brown [8]) remains (using
some more technical details), for some 0 < β1 < 1/3 and 1/2 < β2 < 1, to
estimate uniformly the sums
SI :=
∑
m∼M
∣∣∣∣∣∑
n∼N
g(mn)
∣∣∣∣∣ for M 6 xβ1 (type I)
418 Joël Rivat
where MN = x (which implies that the “easy” sum over n is long) and for
all complex numbers am, bn with |am| 6 1, |bn| 6 1 the sums
SII :=
∑
m∼M
∑
n∼N
ambn g(mn) for xβ1 < M 6 xβ2 (type II),
(which implies that both sums have a significant length).
6. Sums of type I
For the sums of type I we might expect that the knowledge of the function
g permits to get a satisfactory estimate of the sum∑
n∼N
g(mn).
Indeed in our case where g(n) = e(α s(n)) we were able to adapt success-
fully arguments from Fouvry and Mauduit [2, 3] (1996).
7. Sums of type II
7.1. Smoothing the sums.
By Cauchy-Schwarz inequality:
|SII |2 6 M
∑
m∼M
∣∣∣∣∣∑
n∼N
bn e(α s(mn))
∣∣∣∣∣
2
.
Here, expanding the square and exchanging the summations, we would get
a smooth sum over m, but also two free variables n1 and n2. However, we
can get a useful control by using van der Corput’s inequality:
Lemma 1. Let z1, . . . , zL ∈ C. For all R ∈ N∗ we have∣∣∣∣∣∣
∑
16`6L
z`
∣∣∣∣∣∣
2
6
L + R− 1
R
∑
|r|<R
(
1− |r|
R
) ∑
16`6L
16`+r6L
z`+rz`.
The interest of this inequality is that now we have n1 = n+r and n2 = n
so that the size of n1 − n2 = r is under control.
Now in fact we can take M = qµ, N = qν and R = qρ where µ, ν and ρ
are integers such that ρ/(µ + ν) is “very small”. It remains for 1 6 |r| < qρ
to prove the estimate∣∣∣∣∣∣
∑
qν−1<n6qν
bn+r bn
∑
qµ−1<m6qµ
e(α s(m(n + r))− α s(mn))
∣∣∣∣∣∣ = O(qµ+ν−ρ).
The sum of digits of prime numbers 419
7.2. Truncated sum of digits function.
We want to take advantage of the fact that in the difference
s(m(n + r)) − s(mn), the product mr is much smaller that mn. In the
example:
mn =
µ+ν︷ ︸︸ ︷
35116790780999806546523475473462336857643565,
mr = 396576345354568797095646467570︸ ︷︷ ︸
µ+ρ
,
we see that in the sum mn + mr the digits after index µ + ρ may change
only by carry propagation.
Proving that the number of pairs (m,n) for which the carry propagation
exceeds
λ := µ + 2ρ
is bounded by O(qµ+ν−ρ), we can ignore them and replace s(m(n + r)) −
s(mn) by sλ(m(n + r)) − sλ(mn) where sλ is the truncated sum of digits
function
sλ(n) :=
∑
k<λ
nk,
which is periodic of period qλ.
7.3. Fourier analysis.
The periodicity of sλ enables us to write∑
qµ−1<m6qµ
e(α sλ(m(n + r))− α sλ(mn))
=
∑
06u<qλ
∑
06v<qλ
e(α sλ(u)− α sλ(v))
∑
qµ−1<m6qµ
m(n+r)≡u mod qλ
mn≡v mod qλ
1.
The orthogonality formula
1
qλ
∑
06h<qλ
e
(
h`
qλ
)
=
{
1 if ` ≡ 0 mod qλ,
0 if ` 6≡ 0 mod qλ,
leads us to introduce the discrete Fourier transform of u 7→ e(α sλ(u)):
Fλ(h) = q−λ
∑
06u<qλ
e
(
α sλ(u)−
hu
qλ
)
,
420 Joël Rivat
and summing over n and taking absolute values we must show that∑
06h<qλ
∑
06k<qλ
∣∣∣Fλ(h) Fλ(−k)∣∣∣
∑
qν−1<n6qν
∣∣∣∣∣∣
∑
qµ−1<m6qµ
e
(
hm(n + r) + kmn
qλ
)∣∣∣∣∣∣ = O(qµ+ν−ρ).
Here we observe that the summations over m (geometric sum !) and n can
be handled by classical arguments from analytic number theory, while we
hope that the digital structure hidden in Fλ will produce a huge saving.
7.4. Heuristic end of the proof.
On average, for fixed (h, k), the geometric sum over m is small so that
the sum over n should be O(qν+ε). Hence after many technical steps to
handle the exceptions, we will need to get the crucial upper bound∑
06h<qλ
|Fλ(h)| = O
(
qηλ
)
with η < 1/2,
which means that we need an upper bound sharper than the square root
of the trivial estimate.
Indeed suppose this has been done, then we get∑
h
∑
k
∑
n
∑
m
· · · = O(q2ηλ+ν+ε),
and since λ = µ + 2ρ, we have
2ηλ + ν + ε 6 µ + ν − ρ
for µ, ν large enough.
8. The discrete Fourier transform
Let us take q = 2 to simplify all formulas.
It follows from the definition of Fλ that
F0(h) = 1,
and that for λ > 1,
Fλ(h) =
1
2λ
∑
06u<2λ
e
(
α s(u)− uh
2λ
)
so that
Fλ(h) =
1
2λ
∑
06u<2λ−1
(
e
(
α s(2u)− 2uh
2λ
)
+ e
(
α s(2u+1)− (2u+1)h
2λ
))
.
We have
s(2u) = s(u) and s(2u + 1) = s(u) + 1,
The sum of digits of prime numbers 421
hence
Fλ(h) =
1
2
(
1 + e
(
α− h
2λ
))
Fλ−1(h)
thus
|Fλ(h)| =
λ∏
i=1
∣∣∣∣cos π (α− h2i
)∣∣∣∣ .
We recall that we want to prove that∑
06h<2λ
|Fλ(h)| = O(2ηλ) with η < 12 .
9. Norm 1 of the discrete Fourier transform
Let the transfer operator
Φ0(x) = 1
Φi(x) =
∣∣cos π(α− x2 )∣∣Φi−1(x2 ) + ∣∣sinπ(α− x2 )∣∣Φi−1(x+12 ).
We write∑
06h<2λ
|Fλ(h)| =
∑
06h<2λ−1
(
|Fλ(h)|+
∣∣∣Fλ(h + 2λ−1)∣∣∣)
=
∑
06h<2λ−1
|Fλ−1(h)|
(∣∣∣cos π(α− h
2λ
)
∣∣∣+ ∣∣∣sinπ(α− h
2λ
)
∣∣∣)
=
∑
06h<2λ−1
|Fλ−1(h)| Φ1
(
h
2λ−1
)
.
We can repeat this process and get∑
06h<2λ
|Fλ(h)| =
∑
06h<2λ−2
|Fλ−2(h)| Φ2
(
h
2λ−2
)
.
Now
Φ21(x) =
(∣∣cos π(α− x2 )∣∣+ ∣∣sinπ(α− x2 )∣∣)2 = 1 + ∣∣sin 2π(α− x2 )∣∣ ,
and
Φ22(x) 6 Φ
2
1(
x
2 ) + Φ
2
1(
x+1
2 )
= 2 +
∣∣sin 2π(α− x4 )∣∣+ ∣∣∣sin 2π(α− x+14 )∣∣∣
= 2 +
∣∣sin 2π(α− x4 )∣∣+ ∣∣cos 2π(α− x4 )∣∣ ,
6 2 +
√
2.
Hence ∑
06h<2λ
|Fλ(h)| 6 (2 +
√
2)1/2
∑
06h<2λ−2
|Fλ−2(h)| ,
422 Joël Rivat
and finally ∑
06h<2λ
|Fλ(h)| = O
(
(2 +
√
2)λ/4
)
.
Since
(2 +
√
2)1/4 < 41/4 =
√
2,
we indeed have ∑
06h<2λ
|Fλ(h)| = O
(
2ηλ
)
for some η < 1/2.
References
[1] C. Dartyge and G. Tenenbaum, Sommes des chiffres de multiples d’entiers. Ann. Inst.
Fourier (Grenoble) 55 (2005), 2423–2474.
[2] E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presques premiers. Mathe-
matische Annalen 305 (1996), 571–599.
[3] E. Fouvry and C. Mauduit, Méthodes de crible et fonctions sommes des chiffres. Acta
Arithmetica 77 (1996), 339–351.
[4] J. Friedlander and H. Iwaniec, The polynomial X2 + Y 4 captures its primes. Ann. of
Math. (2) 148 (1998), 945–1040.
[5] J. Friedlander and H. Iwaniec, Asymptotic sieve for primes. Ann. of Math. (2) 148
(1998), 1041–1065.
[6] A. O. Gelfond, Sur les nombres qui ont des propriétés additives et multiplicatives données.
Acta Arithmetica 13 (1968), 259–265.
[7] G. Harman, Primes with preassigned digits. Acta Arith. 125 (2006), 179–185.
[8] D. R. Heath-Brown, Prime numbers in short intervals and a generalized Vaughan identity.
Can. J. Math. 34 (1982), 1365–1377.
[9] D. R. Heath-Brown, Primes represented by x3 + 2y3. Acta Math. 186 (2001), 1–84.
[10] K. Mahler, The Spectrum of an Array and Its Application to the Study of the Translation
Properties of a Simple Class of Arithmetical Functions. II: On the Translation Properties
of a Simple Class of Arithmetical Functions. J. of Math. Phys. Mass. Inst. Techn. 6 (1927),
158–163.
[11] C. Mauduit, J. Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres
premiers. Annals of Mathematics, à paraître.
[12] I. I. Piatetski-Shapiro, On the distribution of prime numbers in sequences of the form
[f(n)]. Mat. Sbornik N.S. 33(75) (1953), 559–566.
[13] W. Sierpiński, Sur les nombres premiers ayant des chiffres initiaux et finals donnés. Acta
Arith. 5 (1959), 265–266.
[14] R. C. Vaughan, An elementary method in prime number theory. Acta Arithmetica 37
(1980), 111–115.
[15] I. M. Vinogradov, The method of Trigonometrical Sums in the Theory of Numbers, trans-
lated from the Russian, revised and annotated by K.F. Roth and A. Davenport. Interscience,
London, 1954.
[16] D. Wolke, Primes with preassigned digits. Acta Arith. 119 (2005), 201–209.
Joël Rivat
Institut de Mathématiques de Luminy
CNRS-UMR 6206
163 avenue de Luminy
Case 907
13288 Marseille Cedex 9, France.
E-mail : rivat@iml.univ-mrs.fr


On Gelfond’s conjecture about the sum of digits of prime numbers

Stéphane Vinatier

Permuting the partitions of a prime

Guillaume Ricotta

Nicolas Templier

Comportement asympotique des hauteurs des points de Heegner

Lionel Dorat

Tore de l’inertie modérée

Loïc Grenié

Loïc GRENIÉ
Fast computation of class fields given their norm group
Tome 20, no 3 (2008), p. 707-714.
<http://jtnb.cedram.org/item?id=JTNB_2008__20_3_707_0>
© Université Bordeaux 1, 2008, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir la
présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 20 (2008), 707-714
Fast computation of class fields given
their norm group
par Loïc GRENIÉ
Résumé. Soit K un corps de nombres contenant, pour un nombre
premier `, les racines `-ièmes de l’unité. Soit L une extension de
Kummer de degré ` de K, caractérisée par son module m et son
groupe de normes. Soit Km le compositum des extensions de degré
` de K de module divisant m. En utilisant la structure d’espace
vectoriel de Gal(Km/K), nous proposons une amélioration pour
la fonction rnfkummer de PARI/GP qui permet de ramener la
complexité du calcul d’une équation de L sur K d’exponentielle à
linéaire.
Abstract. Let K be a number field containing, for some prime
`, the `-th roots of unity. Let L be a Kummer extension of degree
` of K characterized by its modulus m and its norm group. Let
Km be the compositum of degree ` extensions of K of conductor
dividing m. Using the vector-space structure of Gal(Km/K), we
suggest a modification of the rnfkummer function of PARI/GP
which brings the complexity of the computation of an equation of
L over K from exponential to linear.
1. Introduction
Let K be a number field and let ` be a prime such that K contains the
`-th roots of unity. The algorithm [Coh, Algorithm 5.2.14, p239] gives the
list of extensions of K with degree ` and conductor m. Let Clm(K) be the
ray class group of conductor m. Among the extensions with conductor m,
one might be interested in finding the specific one with norm group equal to
a specific subgroup N of Clm(K). Computing this extension can be easily
done by testing the norm group of each of the extensions computed by the
preceding algorithm, and is indeed implemented that way in PARI/GP.
However, it can be faster to use the vector space structure of the quotient
G = Clm(K)/̀ Clm(K): we know, by Galois and Kummer theory, that the
set of degree ` extensions of K of conductor dividing m are in bĳection with
the set of hyperplanes of G. An hyperplane of G is the kernel of a linear form
Manuscrit reçu le 20 décembre 2006.
708 Loïc Grenié
over G so that finding L is equivalent to finding a linear form with kernel
the hyperplane HL corresponding to L. Finding a linear form is equivalent
to finding its coordinates in the dual of G and while the hyperplanes of G
are `
dim G−1
`−1 , there are only dim G vectors in the base of a dual of G. We
can thus bring the complexity of the problem from exponential to linear.
We recall that the exponent of a group G is the minimum positive k such
that ∀g ∈ G, gk is the unity of G.
2. The ray class group and the Kummer compositum
2.1. The situation. We fix an algebraic closure Q of Q, a prime number
` and a primitive `-th root of unity ζ` ∈ Q. Let K ⊂ Q be a number field
containing ζ`. We fix a conductor m = (m0,m∞) with m0 an ideal of OK and
m∞ a subset of the set of real embeddings of K in C. We are interested
in the compositum Km of the Kummer extensions of K contained in Q
which have degree ` and conductor dividing m. Then G = Gal(Km/K) is an
abelian group of exponent ` which means that it is an F`-vector space. By
class field theory, we can identify G with Clm(K)/̀ Clm(K).
Any extension L ⊂ Km of degree ` over K is characterized by the sub-
group HL = Gal(Km/L) which has index ` in G. Such a subgroup is an
hyperplane of G, when G is seen as a vector space over F`. This means
that it is the kernel of a linear form, i.e. that it is the orthogonal of a line
of the F`-dual of G.
Let (K×)` =
{
x`/x ∈ K×
}
. Then there is a perfect F`-pairing between
G and the subgroup G∗ of K×/(K×)` of classes of elements of
OK,m =
{
x ∈ K×/(x) ⊆ m0 and ∀σ 6∈ m∞, σ(x) 6∈ R−
}
.
Such a pairing can easily be made explicit by
G×G∗ −→ µ`
(σ , x) 7−→ σ(
√̀
x)√̀
x
with µ` = {ζ i` , i ∈ Z} the group of `-th root of unity in K and for any
choice of an `-th root of x in Km.
A degree ` extension L of K inside Km is K(
√̀
x) for some x ∈ G∗ and
x is dual to HL. Obviously all the powers xi for 1 6 i < ` lead to the
same extension, i.e. to the same subgroup HL; from the point of view of
F`-vector spaces, they are linear forms over G which are proportional and
thus have the same kernel.
2.2. Identifying vectors in the dual. We can compute the norm group
NL for the extension L given by an equation of the form X`−x. Such norm
group is in Clm(K), but its image HL in G also has index `. The perfect
pairing above provides an isomorphism between G and G∗. Suppose that
Fast computation of class fields 709
we know how to compute the equation of the norm group in a basis of G.
If we do not explicit the pairing above, computing the norm group allows
us to identify the line [x] directed by the image f(x) of x in a vector space
V = Fn` isomorphic to G
∗ but the equation of the norm group alone cannot
identify f(x) itself (except if ` = 2). If x and y are elements of OK,m (such
that ∀0 6 i, j < `, xi 6= yj), the three elements
√̀
x, √̀y and √̀xy generate
three extensions of K of degree `. The norm groups of those extensions
allows us to identify the three lines [x], [y] and [xy] directed by f(x), f(y)
and f(xy); now if we know the value x0 of f(x) inside [x], we can identify
y0 = f(y) ∈ [y] because all the lines [x0t], t ∈ [y] are distinct and exactly
one of them is [xy]. Let λ ∈ F ×` . If we take λx0 instead of x0, then we will
get λy0 instead of y0. It follows that the choice of x0 is irrelevant, up to
multiplication by a scalar in V .
It follows that, once we fix a value f(x) for an x ∈ OK,m\(K×)` in V ,
by computing two norm groups, we can compute the value of f(y) for any
y ∈ OK,m which is not a power of x times an `-th power.
3. Algorithm
We provide the following modification of [Coh, Algorithm 5.2.14, p239].
The nine first steps are unchanged, so we do not rewrite them. Instead of
looking for all cyclic extensions of given conductor, we look for a specific
one with given relative norm group N . All matrices and vectors in the
following algorithms are taken in F`. If M is a matrix, Mi will denote its
i-th column.
Algorithm 3.1. Compute the extension of K of degree ` with given norm
group N given in SNF form.
Recall that c = dK is the dimension of the kernel K of the matrix M .
10. [Equation of norm group] Set EN to be the column vector obtained from
N by applying only step 2 of subalgorithm 3.2.
11. [Initialize backtracking] (In what follows, c ≤ 1 and y will be a row
vector with c− 1 components, and Y (y) will be a column vector with rw
components, the rw − c first ones equal to (0, ..., 0)t, then a single 1 and
the components of yt.) Set y ← (0, ..., 0) (vector with c−1 components).
Set D and G to be matrices with 0 columns and rw rows.
12. [Check linear independence] If Y (y) is in the image of D, then go to step
19
13. [Compute trial vector] Let X ← Kc +
∑
1≤j<c yjKj . Apply subalgo-
rithm [Coh, 5.2.15, p240] to see if X corresponds to a suitable Abelian
extension. If it does, set α =
∏
1≤j≤rw v
xj
j (where X = (x1, ..., xrw)
t).
Set T ← X` − α. Let L = K[
√̀
α]. Compute the matrix M of the
710 Loïc Grenié
norm group for the extension L/K using [Coh, Algorithm 4.4.3, p215]. If
M = N output the polynomial T and terminate the algorithm.
14. [Update dependency matrix] Set D ← (D|Y (y)), concatenation of Y (y)
at the right of D.
15. [Norm group equation] If either G is empty or ` = 2, compute accord-
ing to subalgorithm 3.2 an equation E for the norm group of extension
L/K and set α1 ← α and E1 ← E, otherwise compute the equation E
according to subalgorithm 3.3. Set G← (G|E).
16. [Test computability] If EN is in the image of G, let (xi) be the vector of
coordinates: EN =
∑
i xiGi. Set Y0 ←
∑
i xiLi. Set y to be the last c− 1
elements of Y0 and go to step 13.
17. [Backtracking I] Set i← c.
18. [Backtracking II] Set i← i− 1. If i = 0 set c← c− 1 and go to step 11.
19. [Backtracking III] Set yi ← yi +1, and if i < c−1, set yi+1 ← 0. If yi ≥ `,
go to step 18; otherwise go to step 13.
Subalgorithm 3.2. Compute an equation for the norm group of a Kummer
extension L/K.
1. Compute SNF matrix M of the norm group of the extension L/K ac-
cording to [Coh, Algorithm 4.4.3, p215].
2. Let i be the index such that Mii 6= 1. Set E to be the transpose of the
i-th row of M . Change the i-th element of E in −1.
3. Output E and terminate the subalgorithm.
Subalgorithm 3.3. Compute an equation for the norm group of a Kum-
mer extension K(
√̀
α)/K, coherent with a given equation E1 for a given
extension K(
√̀
α1)/K. We suppose the images of α and α1 generate two
distinct cyclic groups of order ` in K×/(K×)`.
1. Compute equation E2 of extension K(
√̀
α)/K according to subalgorithm
3.2.
2. Compute equation E3 of extension K(
√̀
αα1)/K according to subalgo-
rithm 3.2.
3. Find non-zero coefficients λ1, λ2 and λ3 such that λ1E1 +λ2E2 +λ3E3 =
0.
4. Output −λ2λ1 E2 and terminate the subalgorithm.
Remark 1. This algorithm is very similar to [Coh, Algorithm 5.2.14, p239],
and is very easy to implement in a single function. The relevant differences
are: the algorithm stops as soon as the correct equation is found and we
do not test for equations which are linearly dependant in G∗; using linear
algebra, we deduce an equation for the searched field using equations for a
basis of G∗.
Fast computation of class fields 711
Remark 2. In step 4 of subalgorithm 3.3, all three coefficients λi are
non-zero because the elements α and α1 generate different cyclic groups in
F×/(F×)`. Otherwise, one would have to compute k such that α and α k1
have same class in that group and output kE1.
Remark 3. If y is computed at step 4, one can omit the check of norm
group group at step 13 of algorithm 3.1 : it has to be N .
Theorem 4. Algorithm 3.1 computes the extension with at most 2dK (resp.
dK + 1 if ` = 2) computations of norm groups.
Proof: The proof is now obvious. We compute the norm group once for
each α at step 13. Thanks to D we take care to study only linearly in-
dependent vectors in G∗. This makes dK computations of norm groups. If
` 6= 2, for each α starting at the second we need an additional computation
of the norm group for x` − αα1 in subalgorithm 3.3, which brings us to
2dK − 1 norm groups. For the final element we compute the norm group
in step 13 (but as observed in remark 3, this computation is not neces-
sary). 
4. Further improving efficiency
As written above, the algorithm enumerates the non-zero lines of K,
checking at each step whether they correspond to a suitable abelian exten-
sion. The non-zero elements are the elements of a family of subspaces of
G∗. As observed in [Coh, top of p241], this is not linear algebra.
However we can try to improve the situation by computing as good a
basis of K as possible. Let Bi be the family of subspaces of K which provides
unsuitable extensions, ordered by increasing codimension. Let Ei be an
equation of Bi, i.e. a morphism from K to Fcodim Bi` such that Bi = kerEi.
Let n be the maximum i such that codim Bi = 1. Let (vj)16i6dK be a
basis of K. Using Gauss elimination technique, we can try to find a basis
(wj)16j6dK such that Ei(wj) = δij for 1 6 i 6 n. This is indeed possible if
all Ei are linearly independent. Assume such a basis (wj) has been found.
Create a basis (Ki) for K using the following algorithm,
1. Set i← 1, d← min(n, dK), and Km ← wm (for all d < m ≤ dK).
2. Set Kd ←
∑
1≤j≤d wj .
3. Set Ki ← Kd + wi
4. Set i← i + 1. If i < d go to step 3 otherwise stop the algorithm.
If n 6 dK and ` > 2, this algorithm provides a basis of K which is such that
∀i, j ≤ n, Bi(Kj) 6= 0.
If all Bi are of codimension 1 and all Ei are linearly independent, it is
possible to reduce the number of tests at step 13 of algorithm 3.1 to dK.
712 Loïc Grenié
To do that, insert after 16 a step
16.5. Set c← c− 1 and go to step 11.
If the above conditions are not met, the improvement is not correct: it
can fail to compute a basis of G∗. This improvement can be done anyway,
but as a first try, i.e. by repeating twice the step from step 11 to step 19,
once with this test enabled and, if needed, once with it disabled.
5. Speed gains
We show on an example of the speed gain that can be obtained from those
methods. The author implemented algorithm 3.1 and the technique outlined
in section 4. As a base field we took K = Q[
√
5, ζ12], ` = 3 and we selected
modulus m = (23.33.52.112). We then have G ' F 143 and we chose as L the
extension whose norm group is the kernel of the projection of G on its ninth
factor group. Note that the generators are not canonical but there is a way
to choose them unambiguously in PARI. The classical algorithm of PARI
has computed an equation for L in two minutes; the algorithm suggested
here has computed it in two seconds. Note that a part of those two seconds
is spent by both algorithms on common computations, in particular to
compute the modulus of the extension L/K, which is smaller than m. The
commands used to compute this extension are shown in appendix.
6. Other uses of linear independence of fields
This technique can be used to compute extensions that satisfy linear
conditions in the subspace G∗.
6.1. Extensions with limited residual extensions. In [Gre], we need
to compute a Galois extension L of K ramified over a given set of primes
and such that Gal(L/K) is an `-group of exponent dividing `k for a given
k.
The condition on the exponent is easy to test at the residual level. Indeed
let P be a prime of L over a prime p of K, non ramified in L/K. If the
residual field of LP has Q elements while the residual field of Kp has q
elements, then Gal(L/K) will have a cyclic subgroup of order Q/q because
extensions of finite fields are cyclic.
Since Gal(L/K) is an `-group, To compute L it is sufficient to compute
a tower of extensions Ki such that Ki+1/Ki is a compositum of Kummer
extensions. If, for a prime pi of Ki over the prime p of K, the residual ex-
tension has already degree `k, we cannot have additional residual extension
over pi; on the other hand, if the degree of the residual extension is lower
that `k, having residual extension over pi is irrelevant. This construction
Fast computation of class fields 713
can be done with the function rnfkummer of PARI/GP, by checking the
residual extensions for a predetermined set of primes.
It is possible to improve the speed of the algorithm. We limit ourselves
to identifying the maximal compositum of Kummer extensions that has
trivial residual extensions over a finite set of primes {p1, ..., pn}. If L/K is
a Kummer extension, we have L = K(
√̀
α) for some α ∈ OK . If we reduce
modulo pi, there will be residual extension if and only if the reduction of α
is not an `-th power. Denote kpi the residual field of K modulo pi. Consider
the quotient k(`) of k×pi by its `-th power. We have that L/K has no residual
extension over pi if and only if the image of α in k(`) is trivial. But the
application fi from G∗ to k(`) which associates to the class of α (in G∗)
the class of the image of α (in k(`)) is F`-linear. This means that we are
looking for the kernel of the morphism (f1, ..., fn). Finding a kernel can be
done using a basis of G∗ and standard algorithms.
For this reason, we provided rnfkummer a mean to output a list of linearly
independent (in G∗) equations of fields. This is a minor modification of the
algorithm above.
6.2. General cyclic extensions of prime degree. Suppose we want to
compute the Galois extension of degree ` with given conductor and norm
group even when ζ` 6∈ K. The method is to compute Kummer extensions
Lz of the compositum Kz = K(ζ`) and choose those which are of the form
L(ζ`) for some cyclic extension L of K of degree `. Those extensions are
those of the form Lz = Kz(
√̀
α) for α in an eigenspace W1 of G∗ for an
endomorphism τ of G∗. To find the extension we look for, we can proceed
with the same method, by computing a basis (wi) of the eigenspace W1 and
computing the extension by using linear algebra and the norm groups of
the extensions corresponding to each wi.
Appendix: timing in PARI
Here are the exact commands used to compute the equation of the field
L alluded to in section 5.
gp > setrand(1);
gp > P=polredabs(polcompositum(polcyclo(12, ’y), ’y∧2-5)[1],
16)
%1 = y∧8 - 3*y∧6 + 8*y∧4 - 3*y∧2 + 1
gp > bnf=bnfinit(P);
gp > bnr=bnrinit(bnf, 8*27*25*121, 1);
gp > default(timer, 1);
gp > rnfkummer(bnr, matdiagonal(vector(#bnr.cyc, i,
1+2*(i==9))))
time = 1mn, 58,814 ms.
714 Loïc Grenié
%4 = x∧3 + Mod(1737/4*y∧7 - 450*y∧6 - 1062*y∧5 + 1008*y∧4 +
3213*y∧3 - 3177*y∧2 + 225/4*y + 423, y∧8 - 3*y∧6 + 8*y∧4 -
3*y∧2 + 1)
gp > rnfkummer(bnr, matdiagonal(vector(#bnr.cyc, i,
1+2*(i==9))), -1)
time = 1,952 ms.
%5 = x∧3 + Mod(1737/4*y∧7 - 450*y∧6 - 1062*y∧5 + 1008*y∧4 +
3213*y∧3 - 3177*y∧2 + 225/4*y + 423, y∧8 - 3*y∧6 + 8*y∧4 -
3*y∧2 + 1)
The −1 as last argument of rnfkummer chooses algorithm 3.1 instead of
the standard one (without argument).
References
[Coh] Henri Cohen, Advanced Topics in Computational Number Theory, volume 193 of Grad-
uate Texts in Mathematics. Springer-Verlag, New York, 2000.
[Gre] Loïc Grenié, Comparison of semi-simplifications of Galois representations. J. Algebra
316 (2) (2007), 608–618.
[PAR] The PARI Group, Bordeaux. PARI/GP, version 2.4.1, 2006. Available from http://
pari.math.u-bordeaux.fr/.
Loïc Grenié
Università degli Studi di Bergamo
Facoltà di Ingegneria
viale Marconi 5
24044 Dalmine, ITALY
E-mail : loic.grenie@gmail.com


Fast computation of class fields given their norm group

Not a member yet