| Contents |
Software: (a free computer algebra system)
| Preprints |
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..
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].
| Research Papers |
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..
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 .
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).
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.
We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials Phi_d(a) for rational a and positive integer d.
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.
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.
A mistake in K. Belabas, Compositio Mathematica 118 (1999), 1-9 ([06]), is here corrected.
«Habilitation à diriger les recherches» (détails).
A general presentation of my research work from 1997 to 2003.
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.
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.
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.
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.
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..
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.
Comment: Obsolete, see [11] instead.
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.
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 [P4].
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.
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.
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].
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.
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..
| Expository Papers |
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.
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.
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).
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 |
talk for «Comité d'évaluation de l'IMB» (12/01/2006).
talk at the 14th Rencontres arithmétiques de Caen (june 2003). See [14] for details.
talk for a general audience at the «Fête de la Science» (2003).
| Karim Belabas |
|
| 2011-09-05 22:41:33 |