Back to main (Karim Belabas)

Contents

Software:

Book:

Research Papers:

Preprints:

Expository Papers:

Slides:

Book

Explicit methods in number theory. Rational points and Diophantine equations (Ed.), with Frits Beukers, Pierrick Gaudry, William McCallum, Bjorn Poonen, Samir Siksek, Michael Stoll and Mark Watkins.
Panoramas et Synthèses, Vol. 36 (2012), xxii + 179 pages, sur le site de la SMF.

This volume contains a selection of seven short courses in number theory taught during a special trimester at Institut Henri Poincaré (from September to December 2004), centered on Diophantine equations and how to effectively solve them. The lectures, targeted at second year graduate students, display an attractive panorama of mathematical ideas and tools, that can be used to reach this goal.

Research Papers

pdf

The logarithmic class group package in PARI/GP, with Jean-François Jaulent.
Publications Mathématiques de Besançon (2017).

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.


pdf

Computing the residue of the Dedekind zeta function, with Eduardo Friedman.
Mathematics of Computation, Vol. 84/291 (2015), pp. 357-369, MR3266965.

Assuming the Generalized Riemann Hypothesis, Bach has shown that one can calculate the residue of the Dedekind zeta function of a number field K by a clever use of the splitting of primes p≤X, with an error asymptotically bounded by 8.33 log ΔK / (sqrt(X) log X), where ΔK is the absolute value of the discriminant of K. Guided by Weil's explicit formula and still assuming GRH, we make a different use of the splitting of primes and thereby improve Bach's constant to 2.33. This results in substantial speeding of one part of Buchmann's class group algorithm.


pdf

Discriminants cubiques et progressions arithmétiques, avec Étienne Fouvry.
International Journal of Number Theory, Vol. 6 (2010), pp. 1491-1529, MR2740719.

We compute the density of discriminants of Galois sextic fields with group S3, thereby proving a new case of Malle's conjecture as well as a special case of its generalization by Ellenberg and Venkatesh. Further, we study the density of cubic discriminants in an arithmetic progression, in the largest possible uniformity with respect to the modulus.


pdf

Error estimates for the Davenport-Heilbronn theorems, with Manjul Bhargava and Carl Pomerance.
Duke Mathematical Journal, Vol. 153 (2010), pp. 173-210, MR2641942.

We obtain the first known power-saving remainder terms for the theorems of Davenport and Heilbronn on the density of discriminants of cubic fields and the mean number of 3-torsion elements in the class groups of quadratic fields. In addition, we prove analogous error terms for the density of discriminants of quartic fields and the mean number of 2-torsion elements in the class groups of cubic fields. These results prove analytic continuation of the related Dirichlet series to the left of the line Re(s)= 1 .


pdf

L'analyse logique des probabilités selon Waismann, avec Layla Raïd.
Cahiers de philosophie du Langage, Vol. 6 (2009), pp. 235-260.

Dans une perspective d'histoire des sciences, nous présentons l'ébauche d'axiomatique pour les probabilités proposée en 1929 par le philosophe du Cercle de Vienne Friedrich Waismann, tant dans ce qu'elle anticipe des développements futurs - comment elle se fonde à juste titre sur la donation d'une mesure arbitraire -, que dans ce qu'elle laisse inachevé. Dans une optique philosophique, nous montrons comment Waismann défend, contre toute interprétation empirique, l'aprioricité du calcul des probabilités dans une perspective tractatuséenne. Dans ce cadre, il s'élève en particulier contre les définitions de la probabilité comme limite d'une fréquence relative (von Mises).


pdf

Factoring polynomials over global fields, with Mark van Hoeij, Jürgen Klüners, and Allan Steel.
J. Théor. Nombres Bordeaux, Vol. 21 (2009), pp. 15-39, MR2537701.

In this paper we prove polynomial time complexity for a now widely used factorization algorithm for polynomials over the rationals. Our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.


pdf

Practical Aurifeuillian factorization, with Bill Allombert.
J. Théor. Nombres Bordeaux, Vol. 16 (2008), pp. 543-553, MR2523308.

We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials Phi_d(a) for rational a and positive integer d.


pdf

Small generators of the ideal class group, with Francisco Diaz y Diaz, and Eduardo Friedman.
Mathematics of Computation, Vol. 77/262 (2008), pp. 1185-1197, MR 2373197.

Assuming the Generalized Riemann Hypothesis, Bach has shown that the ideal class group ClK of a number field K can be generated by the prime ideals of K having norm smaller than 12 log2|disc(K)|. This result is essential for the computation of the class group and units of K by Buchmann's algorithm, currently the fastest known. However, once ClK has been computed, one notices that this bound could have been replaced by a much smaller value, and so much work could have been saved. We introduce here a short algorithm which allows us to reduce Bach's bound substantially, usually by a factor 20 or so. The bound produced by the algorithm is asymptotically worse than Bach's, but favorable constants make it useful in practice.


pdf

Paramétrisation de structures algébriques et densité de discriminants [d'après Bhargava]
Astérisque, Vol. 299 (2005), Exp. No. 935, pp. 267-299, Séminaire Bourbaki. Vol. 2003/2004, MR 2167210.

La composition de Gauss donne une structure de groupe aux orbites de formes quadratiques binaires entières de discriminant D, sous l'action de SL2 par changement de variable, essentiellement le groupe des classes de l'ordre quadratique de discriminant D. Les domaines fondamentaux associés permettent calculs explicites et évaluation d'ordres moyens. Je présente les lois de composition supérieures découvertes par M. Bhargava à partir de la classification des espaces vectoriels préhomogènes réguliers, ainsi que les résultats de densité qu'il obtient ou conjecture, en particulier sur les discriminants de corps de nombres.


pdf

Corrigendum: "On the mean 3-rank of quadratic fields"
Compositio Mathematica, Vol. 140 (2004), p 1221, MR 2081161.

A mistake in K. Belabas, Compositio Mathematica 118 (1999), 1-9 ([06]), is here corrected.


pdf

Contributions à l'algorithmique des corps de nombres (HDR) (French, survey).
Université Paris 11

«Habilitation à diriger les recherches» (détails).

A general presentation of my research work from 1997 to 2003.


pdf

Topics in computational algebraic number theory
J. Théor. Nombres Bordeaux, Vol. 16 (2004), pp. 19-63, MR 2145572.

We describe efficient variants of standard tools from computational algebraic number theory, with applications to class field theory, in particular the construction of class fields. These include basic arithmetic, approximation and uniformizers, discrete logarithms and computation of class fields, as implemented in the PARI/GP system.


pdf

On quadratic fields with large 3-rank
Mathematics of Computation, Vol. 73 (2004), pp. 2061-2074, MR 2059751.

Davenport and Heilbronn defined a bijection between classes of binary cubic forms and classes of cubic fields, which has been used to tabulate the latter. We give a new, simpler, proof of their theorem, then analyze and improve the table-building algorithm. It computes the multiplicities of the O(X) general cubic discriminants (real or imaginary) up to X in time O(X) and space O(X3/4), or more generally in time O(X + X7/4 / M) and space O(M + X1/2) for a freely chosen positive M. A variant computes the 3-ranks of all quadratic fields of discriminant up to X with the same time complexity, but using only M + O(1) units of storage. As an application, we obtain the first 1618 real quadratic fields with r3(D) > 3, and prove that Q(sqrt(-5393946914743)) is the smallest imaginary quadratic field with 3-rank equal to 5.

Comment: Supersedes [1], [4], [5].


pdf

A relative van Hoeij algorithm over number fields
J. Symbolic Computation, Vol. 37 (2004), no. 5, pp. 641-668, [ScienceDirect access], MR 2094619.

Van Hoeij's algorithm for factoring polynomials over the rational integers rests on the same principle as Berlekamp-Zassenhaus, but uses lattice basis reduction to improve drastically on the recombination phase. His ideas give rise to a collection of algorithms, differing greatly in their efficiency. We present two deterministic variants, one of which achieves excellent overall performance. We then generalize these ideas to factor polynomials over number fields.

Comment: Supersedes [P2]; see also [20].


pdf

Generators and relations for K2 OF, with Herbert Gangl.
K-Theory, Vol. 31 (2004), no. 3, pp. 195-231, MR 2067570.

We adapt Tate's algorithm for computing the tame kernel of number fields, which gives explicit generators for the group and sharp bounds on their order. The latter, together with structural results on the p-primary part of K2 OF due to Tate and Keune gives a proof of its structure for many number fields of small discriminant, confirming earlier heuristic results obtained assuming Lichtenbaum conjecture. In particular, we compute the tame kernels of some non-Galois fields.

(earlier version, obsoleted).


pdf

Quine critique de Peirce : vérité et convergence, avec Layla Raïd.
Philosophia Scientiae - Public@tions Électroniques, Vol. 1 (2001).

Nous proposons une analyse de certains arguments opposés par Quine dans Le mot et la chose à la conception de la vérité de Peirce. A l'idée que la vérité pourrait être comprise comme l'opinion ultime soutenue par la communauté scientifique sur une question donnée, il faut opposer la difficulté à concevoir une topologie raisonnable sur l'ensemble des opinions (ou des énoncés). Nous développons l'analogie mathématique présente dans cette image d'une vérité-convergence, et montrons qu'elle ne peut rendre compte de certains phénomènes cruciaux, notamment l'évolution des formes du discours scientifique.


ps.gz

Counting horoballs and rational geodesics, with Frédéric Paulin and Saar Hersonsky.
Bull. London. Math. Society, Vol. 33 (2001), pp. 606-612, MR 1844559.

Let M be a geometrically finite pinched negatively curved Riemannian manifold with at least one cusp. We study the asymptotics of the number of geodesics of M starting from and returning to a given cusp, and of the number of horoballs at parabolic fixed points in the universal cover of M. The case of SL(2,Z) and of Bianchi groups is developped.


Determining K2 OQ(d1/2) for 0 > d > -152, with H. Gangl.
Mathematics of Computation, Vol. 69 (2000), pp. 1681-1683, appendix to Computing the tame kernel of quadratic imaginary fields, by J. Browkin, MR 1681124.

Comment: Obsolete, see [11] instead.


pdf

Sur le 3-rang des corps quadratiques de discriminant premier ou pseudo-premier, with Étienne Fouvry. (French).
Duke Mathematical Journal, Vol. 98 (1999), pp. 217-268, MR 1695199.

The main result of this paper is the following statement: there exists a positive density of primes p (that can be chosen to be congruent to 1 or 3 mod 4, at will), such that the ideal class group of the real quadratic field Q(sqrt(p)) has no elements of order 3.

Analogous but weaker statements hold for imaginary quadratic fields: one obtains pseudo primes, not primes. If we insist on the 2-rank being 0, we only get r_3(Q(sqrt(-p)) less or equal to 1.

The result is obtained by combining sieve methods with Davenport and Heilbronn's theory. This improves on the first author's earlier results by a careful estimate of exponential sums, treating various error terms on average, and considering «quasi-fundamental» discriminants instead of sieving for squarefree numbers.


pdf

On the mean 3-rank of quadratic fields
Compositio Mathematica, Vol. 118 (1999), pp. 1-9, MR 1705974.

The Cohen-Lenstra-Martinet heuristics give precise predictions about the class groups of a «random» number field. The 3-rank of quadratic fields is one of the few instances where these have been proven. In the present paper, we prove that, in this case, the rate of convergence is at least sub-exponential. In addition, we show that the defect appearing in Scholz's mirror theorem is equidistributed with respect to a twisted Cohen-Lenstra density.

Corrigendum: In Theorem 1.2 and its proof, the constant 1/2 should be replaced by 1/4., see [16].

Simpler proofs and better remainder terms are given in [22].


ps.gz

Binary cubic formes and cubic number fields, with Henri Cohen.
Computational perspectives in Number Theory (Chicago 1995), 1998, pp. 175-204, Eds. D. Buell et J. Teitelbaum, MR 1483919.

The aim of this paper is to present in a naïve manner a small part of the theory of binary cubic forms and in particular its application to cubic number fields. Most of the results are due to Davenport-Heilbronn, but the algorithmic applications seem to be new.


pdf

A fast algorithm to compute cubic fields
Mathematics of Computation, Vol. 66 (1997), pp. 1213-1237, MR 1415795.

We present a very fast algorithm to build up tables of cubic fields. Real cubic fields with discriminant up to 1011 and complex cubic fields down to -1011 have been computed.


pdf

Crible et 3-rang des corps quadratiques (French).
Annales de l'Institut Fourier, Vol. 46 (1996), pp. 909-949, R 1415952.

Call h(D) the number of cube roots of unity in the class group of Q(sqrt(D)), where D is a fundamental discriminant. Davenport and Heilbronn computed the mean value of these numbers when D tends to ±oo. The author gives a general geometric argument yielding an explicit bound for the error term, with the additional possibility of restricting D to arithmetic progressions. Sieve techniques then produce results about the 3-parts of the groups Cl(Q(sqrt(±P_k))), where P_k is an almost-prime of order k. In this way, one controls simultaneously both the 2-rank and the 3-rank of the class group Cl(Q(sqrt(D))). As a special case, the author gives a bound for the mean 3-rank of the Q(sqrt(±p)), where p is prime.

Comment: Results later improved in [7].


pdf

Variations sur un Thème de Davenport et Heilbronn (PhD) (French).
Thèse, Université Bordeaux I (1996)

We refine a construction, due to Davenport and Heilbronn, which enables us to explicitly manipulate arbitrary families of cubic fields, as well as their simple invariants. We build large tables and give density results about the 3-part of quadratic fields, with effective error terms. Almost-primes discriminants are of particular interest. We then study the p-rank of quadratic fields in the same context, and the 3-rank of general number fields, under the Cohen-Lenstra-Martinet heuristics.


pdf

Computing cubic fields in quasi-linear time
Algorithmic Number Theory (Talence 1995), 1996, pp. 17-25, LNCS, no. 1122, Springer-Verlag, MR 1446494.

We owe to Davenport and Heilbronn an explicit correspondence between cubic fields and classes of integral binary cubic forms. Elementary reduction theory, implicit in their work, enables us to single out a «reduced» cubic form in each class and thus to quickly compute large tables of cubic fields (in the discriminant range |D| < 1011), each field being given by a canonical equation.

Comment: Obsolete, see [13] instead..

Preprints

ps.gz

Tuning and generalizing van Hoeij algorithm [1 February 2001], with Guillaume Hanrot and Paul Zimmermann. (INRIA research report 4124).

Van Hoeij's algorithm for factoring polynomials over the rational integers rests on the same principle as Berlekamp-Zassenhaus, but uses lattice basis reduction to improve drastically on the recombination phase. The efficiency of the LLL algorithm is very dependent on fine tuning; in this paper we present such tuning to achieve better performance. Simultaneously, we describe a generalization of van Hoeij's algorithm to factor polynomials over number fields.

Corrigendum: the proposed generalization does not work as stated, and the implementation over Q used an incorrect bound invalidating the timings. See [11] instead..


pdf

Variations sur un théorème de Davenport et Heilbronn [1997] (French, survey).

Write-up for a talk at IHP in 1996, final form. Refereed and accepted for publication in Séminaire de Théorie des Nombres in 1997, but never appeared following the disappearance of the collection. A survey of what I had understood at the time of Davenport and Heilbronn's theory, relating cubic forms, cubic fields, and 3-ranks of quadratic fields.

Corrigendum: In Théorème 5.2 and its proof, the constant 1/2 should be replaced by 1/4., see [15].

Expository Papers

pdf

Les travaux de Manjul Bhargava, avec Christophe Delaunay. (French).
Gazette des Mathématiciens, Vol. 143 (2015), pp. 6-15.

Manjul Bhargava a reçu la médaille Fields au congrès international de Séoul «pour avoir développé de nouvelles méthodes en géométrie des nombres, qu'il a appliquées au comptage des anneaux de petit rang et pour borner le rang moyen de courbes elliptiques». Cet article est un survol d'une partie de ses travaux.


pdf

L'arithmétique de la théorie algébrique des nombres (French, survey).
Théorie algorithmique des nombres et équations diophantiennes, (N. Berline, A. Plagne, C. Sabbah, eds.). Éditions de l'École Polytechnique, Palaiseau, pp. 85-153, 2005, MR 2224342.

Ce texte est une version développée de [E3], écrit pour deux conférences aux journées X-UPS 2005. Dans ce survol, j'examine une (petite) partie de la théorie algébrique des nombres élémentaire (anneaux d'entiers, groupes de classes, unités) d'un point de vue algorithmique, en me restreignant au cas des corps de nombres.


pdf

(Quelques) aspects algorithmiques de la théorie algébrique des nombres (French, informal course notes not intended for publication).

Dans ce survol, j'examine une (petite) partie de la théorie algébrique des nombres élémentaire (anneaux d'entiers, groupes de classes, unités) d'un point de vue algorithmique, en me restreignant au cas des corps de nombres. On suppose connues les bases de la théorie (anneaux de Dedekind, un minimum d'algèbre commutative), mais la plupart des démonstrations associées à un algorithme sont données.

(cours de 3h donné à Luminy en Septembre 2003.) Cf [E4] pour une rédaction plus détaillée.


pdf

Invitation à l'arithmétique des courbes elliptiques (French, informal course notes not intended for publication).

Une introduction élémentaire à l'arithmétique des courbes elliptiques, avec quelques applications frappantes (Fermat-Wiles, nombres congruents, factorisation et preuve de primalité). Lisible au niveau L3/M1.

(cours de 3h donné à Amiens en 2001 dans le cadre de la formation continue pour les professeurs du secondaire).


Fermat et son Théorème, avec Catherine Goldstein. (French).

Version préliminaire d'un texte publié dans Orsay-Infos 57 (Novembre 1999), autour du célèbre théorème. Une page tout publics.

Slides

pdf

Algorithmics of L-functions

talk for «Comité d'évaluation de l'IMB» (12/01/2006).


pdf

Elementary topics in computational algebraic number theory

talk at the 14th Rencontres arithmétiques de Caen (june 2003). See [14] for details.


pdf

Arithmétique et Cryptologie

talk for a general audience at the «Fête de la Science» (2003).


Karim Belabas
Valid HTML 4.01
2018-03-01 10:02:55