AlgoL: Algorithmics of L-functions (2007-2011)

Project Goals

• I. Reinforcement of links and collaborations
• II. Explicit p-adic arithmetic
  1. Computations in p-adic fields
  2. p-adic zeta functions
  3. Explicit arithmetic of infinite extensions of number fields
• III. Explicit methods in arithmetic geometry
  1. Computations related with curves
  2. L-functions for arithmetic geometry
  3. Algorithmic aspect of Jacobians and computation of Galois representations

I. Reinforcement of links and collaborations

The first objective is to establish concrete synergies between various small teams in Bordeaux, Lyon, Montpellier, and Toulouse, all interested in algorithmic or effective aspects in number theory. To achieve this goal, workshops between the team members and some invited mathematicians will be organized every six months. Research talks will take place during these workshops presenting the latest theoretical progresses, as well as short courses. These meetings will also be used to follow the development of the research program and to ensure the cohesion of the project team.

A second objective is to hold several mini-conferences, bringing together algorithmic number theorists with number theorists who do not normally use computations. The goal is to create and facilitate new interactions between the two groups, and to help make more parts of number theory explicit by trying to answer to their computational needs. This approach should open new ways of research and will enable the development of algorithms responding to precise requests, hopefully providing the mathematical community with new usable tools to experiment with. These will be provided as new or improved modules for the PARI/GP free computer algebra system.

Finally, the team will organize an international conference on computational number theory. This conference will help establish algorithmic number theory as an active area of research in France.

II. Explicit p-adic arithmetic

II.1 Computations in p-adic fields

Local fields play a crucial role in algebraic number theory. First developed as a tool to study number fields, they have now developed in a wide and rich domain of research of their own. One of the goals of this project is to develop the explicit theory of p-adic extensions and obtain actual computer programs. At the moment, the algorithmic study of these fields is primarily developed with the goal of obtaining results for number fields. Breaking the "artificial" link with number fields will allow more flexibility and hopefully improve effectiveness.

For example, consider polynomial factorization over p-adic fields: the problem is satisfactorily solved from the theoretical point of view, but a concrete and effective version is still missing. We will design and program algorithms for computing extensions of a given degree of a p-adic field - which we believe will be most valuable in extensive studies of p-adic fields -; theoretical methods on how to do this have been obtained but almost no computational results. Another natural direction of research is to develop algorithmic local class field theory, in the same vein as effective global class field theory, which resulted in several beautiful and efficient algorithms.

II.2 p-adic zeta functions

Zeta and L-functions gather arithmetic properties of an object in functions of analytical nature. Initially defined as complex functions of one variable, these functions and their values have been extensively studied both from a theoretical and computational point of view. There are currently a few satisfactory implementations that enable one to compute values of these functions to great precision.

Later on, it was found out that the values of these functions could be interpolated to construct p-adic functions. At present, little is proved about these functions but many conjectures have been made. For example, the p-adic Stark conjectures predict that the values of p-adic zeta functions at s=0 or 1, are related to to p-adic regulators of certain unit subgroups possessing a very rich Galois structure. Zagier's conjecture gives a relation between the values of p-adic zeta functions at general integers and values of Borel regulators coming from algebraic K-theory. Another example is the equivariant Iwasawa conjecture, which, although not yet completely formalized, predicts strong arithmetic relations between successive values of p-adic L-functions. Some of these conjectures were proved in certain cases, but much remains open.

It is thus useful to be able to compute the values of these p-adic functions to confirm or contradict these conjectures, and to lead to more precise or more relevant versions. The explicit construction of p-adic zeta and L-functions of totally real number fields yields many theoretical and algorithmic problems that we will need to solve. For instance, one must construct a system of representatives of the totally positive elements of an ideal modulo the action of a certain subgroup of the units of the field. This is done thanks to a cone decomposition which must be optimal in a certain way to reduce the amount of computations. Over real quadratic fields, this decomposition is obtained with continued fractions. But for higher degree fields, many geometrical and combinatorial difficulties appear when one tries to construct similar cone decompositions. Solving these difficulties will enable us, for instance, to compute values of p-adic zeta function of totally real number fields that are not abelian over the field of rational numbers or a quadratic real field which will be, as far as we know, the first computations of this kind.

II.3 Explicit arithmetic of infinite extensions of number fields

Thanks to the main conjecture of Iwasawa theory, the p-adic functions are related to the Iwasawa modules, and then to Leopoldt's conjecture. This conjecture is fundamental in the study of the arithmetic of the pro-p-extensions of number fields but, in this case, the extensions for which information is obtained are wildly ramified. Recently, using the theory of Lie algebras, Labute has given a method to obtain information about maximal pro-p-extensions of number fields when the ramification is tame. His method is quite interesting. In particular he gives an explicit formula for the order of certain ray class groups along an infinite extension.

A first challenge is to give a description by generators and relations of such extensions. To do this, one must compute the first terms of the central descending series of the groups in question and then use intensive p-adic arithmetic. In particular, it would be interesting to control the torsion part of these groups. Typically, after a few experiments, Boston predicted that these groups are potentially without torsion. This question is directly connected to the tame version of a conjecture of Fontaine-Mazur.

Another challenge is to compare the formulas obtained by Labute's method and the Iwasawa generalized formulas due to Ozaki. In particular, one should be able to compute the first terms of the sequence of the Λ-invariants introduced by Ozaki.

III. Explicit methods in arithmetic geometry

III.1 Computations related with curves

Explicit methods in arithmetic geometry have made remarkable progress within the last few years. We shall study existing ones to turn them into efficient implementations, and try to develop new ones.

Some examples of missing algorithms that we plan to design and add to the PARI/GP system are: given an elliptic curve over a number field, estimate the height of a point, compute all integral points, compute the modular degree of the curve, compute rational Heegner points. Another line of work is to adaptat these methods, or develop new methods, for the study of natural families of elliptic curves, such as families of quadratic twists and elliptic surfaces. We plan to conduct a theoretical and computationally intensive study on the size of the generators of the Mordell-Weil groups of families of quadratic twists.

We will also work on algorithmic problems related to the arithmetic properties of curves of higher genus and their Jacobians, e.g. the enumeration of all rational points or the numerical verification of the Birch and Swinnerton-Dyer conjecture for modular curves.

III.2 L-functions for arithmetic geometry

This field of research is in great development but again not from the algorithmic point of view. Thus there is an important gap between the theoretical results and the tools available for numerical computations. In this project, we will concentrate our effort on the developments of tools to compute special values of modular forms of large levels. This can be used, for instance, to test the random matrices models or to verify the Birch and Swinnerton-Dyer conjecture for modular curves in higher genus. In these computations, we will use modular symbols to compute central values of the standard L-functions and the exact formulae of Waldspurger, Gross and Zhang to compute central values of Rankin-Selberg L-functions associated to a modular form (of large level) and a class group character of a (fixed) quadratic number field. In the latter case such formulas are also useful to compute central values of Rankin-Selberg L-functions as above when the modular form is fixed and the discriminant of the quadratic field is large.

III.3 Algorithmic aspect of Jacobians and computation of Galois representations

Bas Edixhoven has designed a program toward the computation of coefficients of modular forms. To this end, Couveignes studied Jacobi's inversion problem in two very different settings: complex tori associated to Jacobians of modular curves on the one hand, and Tate modules associated to the same Jacobians on the other hand. The methods obtained are both polynomial-time with respect to the genus of the curve although they are of a quite different nature (one being discrete and probabilistic, the other one being continuous and deterministic).

Results obtained on the complex analytic side concern the curve X₀(p) and it is now necessary to adapt them at least to the curve X₁(5p) for example. Results obtained on the finite fields side raise a number of interesting questions: is there a polynomial-time probabilistic algorithm to construct a system of generators of the Picard group of a curve over a finite field (polynomial-time with respect to the genus and the logarithm of the finite field size)? What is the precise complexity of all the algorithms already designed: we know they are polynomial-time but what degree can we expect? Is an efficient implementation of these algorithms possible? (The Dutch part of this project is supported by the NWO Vici program Arithmetic geometry, motives: computational aspects.)