Workshop - Méthodes numériques pour les courbes algébriques

Jurgen Angst:
On the real zeros of random trigonometric polynomials

We first briefly recall some well-known facts concerning the set of real zeros of random algebraic polynomials and random real algebraic manifolds. We then focus on the case of random trigonometric polynomials. More precisely, we consider the volume of their nodal set. We show that its local and global asymptotics, as the degree of the polynomials tends to infinity, are universal i.e. do not depend on the particular choice of randomness involved.
Joint work with F. Dalmao, V-H. Pham and G. Poly.

Slides

Jennifer Balakrishnan:
Explicit Coleman integration for curves

I will describe an algorithm for explicit Coleman integration on curves, starting from the case of hyperelliptic curves. I will also present some examples (computed using our Magma implementation) using this algorithm to compute rational points on curves via the Chabauty-Coleman method. This is joint work with Jan Tuitman.

Saugata Basu:
On the intersection of a fixed definable manifold with real algebraic

hypersurfaces of growing degrees: deterministic vs random behavior.

In certain applications in incidence combinatorics, it would be useful to have good control over the Betti numbers of the intersection of any fixed definable subset of $\mathbb{P}^n$ with real algebraic hypersurfaces of growing degrees. Unfortunately, a construction due to Gwozdziewicz, Kurdyka and Parusinksi (Proc. of AMS, 1999) rules out any reasonable deterministic bound even for the case of definable curves in $\mathbb{P}^2$.

In contrast, if $\Gamma$ is any fixed algebraic subvariety of $\mathbb{P}^n$, there exists a constant $c_\Gamma$, such that for any form $P$ of degree $d$, $$ b(\Gamma \cap Z(P)) \leq c_\Gamma d^{n-1} $$ where $b(\cdot)$ denotes the sum of the Betti numbers, and $Z(P)$ the hypersurface defined by $P$ (B-Rizzie, 2017).

In the definable setting, we prove that for any $n > 0$, there exists a universal constant $c_{n} > 0$, such that for any smooth compact definable hypersurface $\Gamma$ of $\mathbb{P}^n$, and for a Kostlan-distributed form $P$ of degree $d$, $$ \mathbb{E}[b(\Gamma \cap Z(P))] \leq c_{n} |\Gamma| d^{(n-1)/2} +O_\Gamma(d^{(n-2)/2}, $$ where $|\Gamma|$ is the volume of $\Gamma$. (Joint work with Antonio Lerario and Abhiram Natarajan).

Paul Breiding:
Random Spectrahedra

Spectrahedra are a special class of convex sets. They are defined to be (affine) linear sections of the cone of positive definite matrices. If the linear section is chosen randomly, we speak of a random spectrahedron. In this talk we will discuss two natural models of randomness and explain why one should be preferred over the other. This is related to expected volume of the random spectrahedron.

The boundary of a spectrahedron is a semialgebraic subset of some corresponding determinantal variety, called symmetroid. It is known that, if the spectrahedron is defined by an intersection of dimension 4, both the symmetroid and the boundary of the spectrahedron have finitely many singularities (generically). We will also consider the expected number of those singularities. This will be related to the volume of matrices with double eigenvalues, for which we present an explicit formula. (joint work with Kazhgali Kozhasov and Antonio Lerario)

Elena Bunkova:
Differentiation of Hyperelliptic Functions

We consider hyperelliptic curves of genus $g$ in the model

$$\mathcal V_\lambda = \big\{(x,y)\in\mathbb{C}^2 \colon y^2 = x^{2g+1} + \lambda_4 x^{2 g - 1} + \lambda_6 x^{2 g - 2} + \ldots + \lambda_{4 g} x + \lambda_{4 g + 2}\big\}$$

with parameters $\lambda = (\lambda_4, \lambda_6, \ldots, \lambda_{4 g}, \lambda_{4 g + 2}) \in \mathbb{C}^{2 g}$.
Let $\mathcal{U}$ be the space of the fiber bundle $\pi: \mathcal{U} \to \mathcal{B}$ with fiber over $\lambda \in \mathcal{B}$ the Jacobian $\mathcal J_\lambda$ of the curve $\mathcal V_\lambda$. A hyperelliptic function is a fiberwise meromorphic function on $\mathcal{U}$. We denote the field of hyperelliptic functions by $\mathcal{F}$.
Our aim is to construct the Lie algebra of vector fields that give derivations of $\mathcal{F}$ for each $g$. The classical $g=1$ case was solved in [FS]. The $g=2$ case was solved in [B]. Our results solving the $g=3$ case are published in [A]. In the talk we will give an exposition to our method in all this three cases.
In [BL] the more general problem of differentiation of Abelian functions was described. It has deep relations [B] with KdV equations theory. Our method is based on the results of [BEL].
This work was supported in part by Young Russian Mathematics award and the RFBR project 17-01-00366 A.

Slides

Victor Enolski:
Curves and their Jacobians in the study of non-Abelian monopoles

In a series of papers H.W. Braden (University of Edinburgh) and the author have investigated the construction of non-Abelian monopoles. A number of beautiful problems about curves and their Jacobians have arisen in the course of this study, part of the renaissance of interest in the area noted by many modern researchers. Our approach is based upon the Atiyah-Drinfeld-Hitchin-Manin-Nahm construction which reduces solving the PDE's of the self-duality equations to an ODE, namely a Weyl equation, whose ``potentials'' are solutions to the Nahm equation. The latter are integrable in Riemann $\theta$-functions of an algebraic curve. A number of difficult problems arise and we will discuss them in this talk.
First the aforementioned curve, the monopole spectral curve, is subject to a number of constraints elucidated by Hitchin. Although there is a rather abundant class (moduli space) of such curves, concretely obtaining one is the crux problem for the whole construction.
Next, the usual algebro-geometric integration of the Lax problem is non-standard and a gauge transformation is required to express this in terms of a standard Baker-Akhiezer function. This gauge transform is defined by a differential equation involving the Baker-Akhiezer function: the solution of this is (as yet) not known in general.
Finally the analytic calculation of physical quantities such as the {\em Energy density} and the of the norm of the {\em Higgs field} requires expansion of the solution in terms of the curve. This requires expanding theta functions around points of the theta divisor.
Although these problems are significant we have shown how to solve the problem in terms of the spectral curve and done this explicitly for the case of two-monopoles and certain charge three monopoles. To do so various old results have been implemented and a number of new results obtained:

  • the Fay-Accola theorem on $\theta$-functional factorization of unramified covers was implemented to reduce higher genera $\theta$ to lower genera
  • Ramanujan hypergeometric equalities were implemented and their role in the derivation of the tetrahedrally symmetric monopole was elucidated
  • Modular representations for periods of first and second kind differentials of higher genera curves were found; in lower genera these are Rosenhain and Klein formulae correspondingly
  • Weierstrass $\theta$-trisecants and derivation of new $\theta(x)$ and $\theta(0)$-constant relations were found
  • Richelot AGM for numeric calculations was implemented and a new monopole curve found.

Slides, Movie

Yuri Fedorov:
Intersection of quadrics and 2-dimensional Abelian varieties, an experimental study.

Complex invariant manifolds of many classical and new finite-dimensional integrable systems are open subsets of 2-dimensional Abelian varieties, which can be realized as intersections of quadrics in ${\mathbb P}^N$.
Following the results of F. Kötter, W. Barth, M. Adler, P. van Moerbeke, we provide an explicit algorithm which allows
1) to check if the intersection of 4 given quadrics in ${\mathbb P}^6$ is an Abelian variety $\cal A$ with polarization (1,2) or not;
2) to represent such $\cal A$ as the Prym variety associated with a genus 3 curve covering an elliptic curve;
3) to parameterize $\cal A$ in terms of divisors of points on a genus 2 curve $\Gamma$, whose Jacobian is isogeneous to $\cal A$, and in terms of theta-functions of $\Gamma$.
A numerical example will be given.

Slides

David Harvey:
Counting points on curves in average polynomial time

Let $X$ be a curve over $Q$, let $X_p$ be the reduction modulo $p$ (this makes sense for all but finitely many primes), and let $Z_p(T)$ be the zeta function of $X_p$. In the last few years, several algorithms have been developed for efficiently computing $Z_p(T)$ simultaneously for all $p$ up to a prescribed bound $N$. I will explain some of the key ideas behind these algorithms.

Slides

Florian Hess:
Explicit isomorphisms and fields of definition of curves

We revisit my method for computing isomorphisms of curves and discuss how this can be applied to define isomorphism invariants and fields of definition of pointed curves.

Christian Klein:
Computational approach to compact Riemann surfaces

A purely numerical approach to compact Riemann surfaces starting from plane algebraic curves is presented. The critical points of the algebraic curve are computed via a two-dimensional Newton iteration. The starting values for this iteration are obtained from the resultants with respect to both coordinates of the algebraic curve and a suitable pairing of their zeros. A set of generators of the fundamental group for the complement of these critical points in the complex plane is constructed from circles around these points and connecting lines obtained from a minimal spanning tree. The monodromies are computed by solving the de ning equation of the algebraic curve on collocation points along these contours and by analytically continuing the roots. The collocation points are chosen to correspond to Chebychev collocation points for an ensuing Clenshaw–Curtis integration of the holomorphic differentials which gives the periods of the Riemann surface with spectral accuracy. At the singularities of the algebraic curve, Puiseux expansions computed by contour integration on the circles around the singularities are used to identify the holomorphic differentials. The Abel map is also computed with the Clenshaw–Curtis algorithm and contour integrals.

Slides

Mario Kummer:
Schottky Algorithms in Genus Four

The Schottky problem concerns the characterization of Jacobians of genus $g$ curves among all abelian varieties of dimension $g$. The latter are parametrized by the Siegel upper-half space, i.e. the set of complex symmetric matrices with positive definite imaginary part. In genus four, we implemented a computational soultion to the Schottky problem: Given a matrix from the Siegel upper-half space, we test whether it corresponds to the Jacobian of a curve, and if it does, we recover equations defining the canonical embedding of the curve. This is joint work with Lynn Chua and Bernd Sturmfels.

Antonio Lerario:
Random Algebraic Geometry: from topology to enumerative geometry

A program on random real algebraic geometry started in the 1990s with pioneer works of A. Edelman, E. Kostlan, M. Shub and S. Smale on random polynomial system solving, with a particular emphasis on asymptotic studies and complexity theory (there is a much influential sequence of papers by Shub and Smale named complexity of Bezout's theorem''). The motivation for a random study came from the necessity, often stimulated by applications, of having a global picture allowing to overcome the noise given by the fluctuations of possible outcomes: since over the real numbers there is in general nogeneric'' case, the attention was shifted to the random'' case. Under the influence of the Edelman-Kostlan-Shub-Smale model, this program has first seen a strong progress in the direction of the study of metric properties of random real algebraic sets (e.g. volume, curvature...) and polynomial system solving; in the last decade this program shifted in direction of the study of topological properties: motivated a letter of P. Sarnak, a random version of Hilbert's Sixteenth Problem was the topic of a recent intense activity (Gayet-Welschinger, Nazarov-Sodin, Fyodorov-Lerario-Lundberg). More recently the same random point of view has been adopted for the study of real enumerative problems (Bürgisser-Lerario, Basu-Lerario-Lundberg-Peterson). This research direction can be considered as a further step in the original Shub-Smale program: if thecomplexity of Bezout's theorem'' papers dealt with the basic problem of counting points in the intersection of random hypersurfaces in projective space, here we count solutions to more advanced intersection theory problem.
In this talk I will survey the main results and methods of this program and, time permitting, I will introduce some new questions related to random maps and tensor geometry.

Bernard Mourrain:
Approximation, certification and efficiency for real algebraic curves.

Computing an isotopic piecewise-linear approximation of an implicit curve is a problem, which appears in several domains such as geometric modeling, graphics, numerical simulations, etc. The challenge is to compute efficiently and robustly a mesh close to the curve with the same topology, from the (algebraic) equation defining the curve.
Several families of methods have been developed to tackle this problem, such as grid, subdivision or sweeping methods. We consider the first two types of methods, which are usually applied with finite precision arithmetic and show good performance in practice. Our aim is to analyze their ``unreasonable'' efficiency.
Grid methods evaluate the (polynomial) function at the points of a regular grid and deduce the topology of a level set of the function, from a local analysis. A very popular method is the so-called Marching Square algorithm. Such approaches can be certified, when the function is a polynomial. We provide bounds on their complexity.
Subdivision methods are based on an adaptive scheme, which subdivides the geometric domain and use local criteria to deduce the global topology of an algebraic set.
An important ingredient of these methods is an adaptive local representation of the equation, such as Bernstein basis representation. Exploiting interesting properties of this representation, the output size of subdivision methods can be controlled in terms of geometric characteristics of the curve.
Another ingredient is a regularity test, which verify when the topology of the curve in a cell can be determined locally. We describe some of these regularity tests for algebraic curves. They require to isolate singular or critical points from regular parts. The topology near singular points is guaranteed through topological degree computation. The topology inside a cell is recovered from information on its boundary.
We analyze the cost of these steps in terms of condition numbers of the polynomial systems involved in the problems.
A comparison of subdivision and grid methods will be developed. Some examples will illustrate their behavior.

Steffen Müller:
Quadratic Chabauty

I will discuss a method to compute the rational points on a curve $\mathbb{Q}$ whose Jacobian has Mordell-Weil rank equal to the genus of the curve, and which satisfies some additional conditions. This extends the method of Chabauty-Coleman by making certain aspects of Kim's non-abelian Chabauty-Kim program explicit for such curves using $p$-adic heights. I will then present an application of this technique to the split (and non-split) Cartan curve of level 13; this is joint work with J. Balakrishnan, N. Dogra, J. Tuitman and J. Vonk and completes the classification of non-CM elliptic curves over $\mathbb{Q}$ with split Cartan level structure due to Bilu–Parent and Bilu–Parent–Rebolledo.

Christian Neuhror:
Computing period matrices of algebraic curves

Explicit computations on the Jacobian variety of a smooth algebraic curve are of great interest in number theory and algebraic geometry. Over the complex numbers the (analytic) Jacobian has the structure of a complex torus which is, up to isomorpishm, determined by a period matrix of the corresponding compact Riemann surface.
Period matrices can be obtained through numerically integrating holomorphic differentials along the first integral homology group. For number-theoretic applications of period matrices it is often necessary to compute these integrals to high precision while using rigorous error bounds.
We implemented algorithms in magma that compute period matrices, reliably and fast, using several integration methods (in particular, Gauss-Legendre, Clenshaw-Curtis and double-exponential integration) to high precision.
In joint work with Pascal Molin, we developed a rigorous algorithm that achieves this goal for the special case of superelliptic curves and is much faster than the one for general curves. Our implementations in magma and arb vastly improve the existing implementation for hyperelliptic curves in terms of speed and numerical stability.
We also compute the Abel-Jacobi map which is closely related to period matrices. Other important applications include the computation of endomorphism rings and theta functions.

Slides

Damien Robert:
Efficient algorithms on Kummer varieties

Theta functions give a nice parametrisation of abelian varieties (and the Thetanullwerte a nice parametrisation of the moduli space of abelian varieties with a symmetric level $n$ theta structure.).
However, to get a projective embedding, we need to work with theta functions of level $n \geq 3$. For an abelian variety of dimension $g$, this means we need to work with $n^g$ coordinates, which get very large even for small dimension. When $n=2$, the theta functions only give (generically) an embedding of the Kummer variety $K=A/\{\pm 1\}$ associated to $A$.
There is no addition law on the Kummer variety $A$; but a lot of the arithmetic structure of $A$ still descends to $K$. In this talk I will give algorithms to work out the arithmetic of $K$ (scalar multiplication, pairings,...). I will also explain how to compress efficiently the theta functions of level $4$ on $A$ to $K$, compression which requires only $2^g+1$ coordinates instead of $4^g$, while still retaining fast arithmetic.

David Roe:
p-adic precision using lattices

I will demonstrate a method for tracking precision in p-adic computations that often yields more precise results, at the cost of increased time and memory usage. The method uses differentials applied to p-adic lattices to get the optimal possible precision. I will give examples using an implementation in Sage. This work is joint with Xavier Caruso and Tristan Vaccon.

Slides, Demo (.ipynb)

Nermin Salepci:
Asymptotic topology of random subcomplexes in a finite simplicial complex

We consider a finite simplicial complex $K$ together with its successive barycentric subdivisions ${Sd} ^d(K), d\geq0,$ and study the expected topology of a random subcomplex in ${Sd} ^d(K), d\gg0$. We will discuss asymptotic upper and lower bounds for the expected Betti numbers of those subcomplexes. This is a joint work with Jean-Yves Welschinger.

Michael Sagraloff:
On the Complexity of Computing the Topology of a Planar Algebraic Curve - An Overview

In this talk, I will give an overview on recent progress in computing the topology of a planar algebraic curve C. Here, the curve is implicitly given as the vanishing set of an integer polynomial f in two variables, and the task is to compute a planar straight line graph G with vertices on C that is isotopic to the curve. The best know worst case bound for the bit complexity of this problem is O˜(d^6+d^5L), where d is the degree of f and L an upper bound on the bitsize of its coefficients. One of the most crucial subroutines that is used in the corresponding algorithm is a fast method to compute the roots (real and complex) of a polynomial with algebraic coefficients. I will give an overview on such methods and show how they can be integrated in algorithms for computing a cylindrical algebraic decomposition. Finally, I will report on an actual implementation of one of our algorithms to compute the topology of a planar algebraic curve.
This is joint work with R. Becker, E. Berberich, D. N. Diatta, S. Diatta, P. Emeliyanenko, M. Kerber, A. Kobel, K. Mehlhorn, F. Rouillier, M.-F. Roy, and P. Wang.

Jeroen Sijsling:
Computing endomorphisms of Jacobians

Let $C$ be a curve over a number field. and let $J$ be its Jacobian. Consider the endomorphism ring $\mathrm{End} (J)$ of $J$. The ring $\mathrm{End} (J)$ is usually isomorphic to $\mathbb{Z}$, but the cases where it is larger are interesting for many reasons, most of all because the corresponding curves can then often be matched with relatively simple modular forms.
In this talk, we discuss the various way of representing and calculating with elements of the endomorphism ring $\mathrm{End} (J)$. We then give an algorithm that computes the endomorphism ring and its Galois structure explicitly. This algorithm follows an approach previously used by Lombardo; first, we bound $\mathrm{End} (J)$ from below by verifying the existence of enough elements, and after this we use $\ell$-adic methods to obtain an upper bound. Together, these methods make it possible to determine the endomorphism ring $\mathrm{End} (J)$ when given an equation for $C$. This algorithm has acceptable running time when the genus of $C$ is small, and we will demonstrate its implementation.
This is joint work with Edgar Costa, Nicolas Mascot, and John Voight.

Slides

Anna Somoza:
Reconstruction of cyclic plane quintic curves

We consider the problem of computing the equation of a curve with given analytic Jacobian, that is, with a certain period matrix.
In the case of genus one, this can be done by using the classical Weierstrass function, and it is a key step if one wants to write down equations of elliptic curves with complex multiplication (CM). Also in higher genus, the theory of CM gives us all period matrices of principally polarized abelian varieties with CM, among which the periods of the curves whose Jacobian has CM, and computing curve equations is the hardest part.
Beyond the classical case of elliptic curves, efficient solutions to this problem are now known for both genus 2 and genus 3. In this talk I will give a method that deals with the case $y^5 = a_5x^5 + \dots + a_1x + a_0$, inspired by some of the ideas present in the method for the genus-3 family of Picard curves $y^3 = x(x-1)(x-\lambda)(x-\mu)$.

Sébastien Tavenas:
Real Intersection Between a Low-degree Curve and a Sparse Hypersurface

Descartes’ rule of signs shows that a real univariate polynomial with t monomials has at most t-1 positive roots. It was shown in a succession of works (Khovanskii,Bihan-Sottile) that the number of real solutions of a system can be bounded by a value which does not depend on the degrees of the polynomials but only on the number of monomials which appear in the system. However, all these bounds are exponential in the number of monomials, and it is an open question to know the optimal one. On the other direction, bounds for small families of systems have also been studied. Several results (Li-Rojas-Wang,Avedao,Bihan-El Hilany) handle small cases (intersection between a sparse plane curve and a line or a trinomial curve). In a previous work, Koiran, Portier and Tavenas found a bound (polynomial in t and d) for the intersection between a sparse plane curve (defines by a t-monomials polynomial) and a degree-d plane curve. We want to generalize the last result in the n-dimensional case. We will show a (polynomial in t and d) upper bound for the number of real intersections between a degree-d curve and a t-sparse hypersurface. This is joint work with M. Safey El Din.

Jan Tuitman:
p-adic numerical methods in arithmetic geometry

We will give an introduction to the use of p-adic numerical methods in arithmetic geometry. More precisely, we will explain how to apply them to:
1) computing numbers of points and zeta functions of algebraic curves over finite fields using Kedlaya style algorithms and
2) finding the rational points of algebraic curves over the rationals using effective Chabauty methods.
This talk will focus more on ideas than technical details and should serve as an introduction to some of the other talks of the day.

Slides

Tristan Vaccon:
Differential precision and isogeny computation

Isogenies are morphisms between elliptic curves. Their computation is of importance for at least two reasons. Firstly, they can be used to count the number of points on elliptic curves, (which is used to discard some of them from cryptographic applications). Secondly, some propositions of quantum-resistant cryptosystems, following De Feo, Jao, and Plut's 2011 article, rely directly on isogenies.
To tackle this problem of isogeny computations, $p$-adic algorithms have been designed by Bostan, Morain, Salvy and Schost in 2008 and Lercier and Sirvent in 2008. With X. Caruso and D. Roe, we have provided a method in 2014 to handle precision over p-adics that relies on differentials and first-order approximation. In 2016, in a joint work with P.Lairez, we have applied this method to tackle the problem of the computation of isogenies between elliptic curves. We have shown some optimal results concerning the behaviour of the $p$-adic precision and improved the time-complexity.

Slides

Partenaires

Irmar LMJL ENS Rennes LMBA LAREMA

Tutelles

ANR CNRS Rennes 1 Rennes 2 Nantes INSA Rennes INRIA ENSRennes UBO UBS Angers UBL