# Séminaire de géométrie et algèbre effectives

Le séminaire est organisé par Xavier Caruso et Elisa Lorenzo García.

Les exposés ont lieu le vendredi à 10h30 dans la salle 016 du bâtiment 22-23.

## Exposés à venir

• Vendredi 15 décembre 2017
A dichotomic Newton-Puiseux algorithm using dynamic evaluation.
Puiseux series (generalisation of Taylor series above critical points) are a fundamental object in the theory of plane algebraic curves. This talk will focus on the arithmetic complexity of the well-known Newton Puiseux algorithm and its variants. Denoted $$D$$ the total degree of the input bivariate polynomial, Duval proved a $$O(D^8)$$ complexity result. This has been improved to $$\tilde O(D^5)$$ by truncating powers of $$X$$ during the computation and introducing fast multiplication.
After providing the tools of the Newton-Puiseux algorithm, we will first present some results that enable to reduce the total number of recursive calls of the algorithm from $$O(D^2)$$ to $$\tilde O(D)$$, leading to a complexity in $$\tilde O(D^4)$$. Finally, we will present a new divide and conquer algorithm that reduces the complexity to $$\tilde O(D^3)$$.
This work begun during my PhD, under the supervision of Marc Rybowicz; the recent ameliorations started from a collaboration with Marc in 2011. The new divide and conquer algorithm is a collaboration with Martin Weimann. This paper is dedicated to Marc Rybowicz, who sadly passed away in November 2016.
• Vendredi 19 janvier 2018
Growth of torsion of elliptic curves.
One of the main goals in the theory of elliptic curves is to characterize the possible torsion structures over a given number field, or over all number fields of a given degree. One of the milestone in this subject was the characterization of the rational case given by Mazur in 1978. Later, the quadratic case was obtained by Kamienny, Kenku and Momose in 1992. For greater degree a complete answer for this problem is still open, although there have been some advances in the last years.
The purpose of this talk is to shed light on how the torsion group of an elliptic curve defi ned over the rationals grows upon base change.
This is an ongoing project partially joint with A. Lozano-Robledo, F. Najman and J. M. Tornero.
• Vendredi 26 janvier 2018
Chloe Martindale (Technical University of Eindhoven)
Isogeny graphs of abelian varieties and applications to the discrete logarithm problem.
An isogeny graph is a graph whose vertices correspond to abelian varieties (with some structure) and whose edges correspond to isogenies of a certain degree. The structure of isogeny graphs for elliptic curves was first studied by David Kohel in his PhD thesis and has since been an essential tool in algorithmic number theory (for example to compute the endomorphism ring of an ordinary elliptic curve over a finite field) and cryptography (for example in the post-quantum cryptographic protocol SIDH). We present a structure theorem for isogeny graphs of ordinary abelian varieties, and explain how, under some heuristic assumptions, this can be applied to attacking the discrete logarithm problem for genus 3 curves and possibly some families of elliptic curves.
• Vendredi 2 février 2018
Marius Vuille (École Polythecnique Fédéral de Lausanne)
• Vendredi 9 février 2018
Frédéric Bihan (Université de Savoie)
• Vendredi 16 février 2018
Fabien Pazuky (Université de Copenhagen)
• Du lundi 19 au vendredi 23 février 2018
Conférence : Méthodes numériques pour les courbes algébriques
• Vendredi 16 mars 2018
• Vendredi 13 avril 2018
Jade Nardi (Institut de Mathématiques de Toulouse)

## Exposés passés

• Vendredi 15 septembre 2017
Victor Cauchois (IRMAR)
• Vendredi 6 octobre 2017
Journée de rentrée de l'équipe
10h45 – 11h30, Codes correcteurs d'erreur (par P. Loidreau)
13h15 – 14h00, Géométrie algébrique réelle (par M.-F. Roy)
14h15 – 15h00, Courbes algébriques (par C. Ritzenthaler)
15h15 – 16h00, Précision p-adique (par X. Caruso)
• Vendredi 13 octobre 2017
Johannes Hoffmann (RWTH Aachen University)
A Constructive Approach to Arithmetics in Ore Localizations
Classical results of Ore from the 1930's tell, that for a domain R, a localization with respect to a multiplicatively closed set S exists if S satisfies left Ore property. We investigate the arithmetics of the localized ring S^{-1}R from both theoretical and practical points of view. We show that effective computations in S^{-1}R require a specialization of the type of S and distill three most frequently occuring types of Ore sets. We provide an implementation of arithmetics over ubiquitous G-algebras in Singular:Plural and discuss algorithmic and theoretic questions in this context.
• Vendredi 20 octobre 2017
Peter Stevenhagen (Université de Leiden)
Ellpitic primitive Roots
• Vendredi 27 octobre 2017
Vincent Neiger (Université de Limoges)
Efficient algorithms for computing univariate relations
In this talk, we will present recent results about the fast computation of univariate relations, including in particular rational interpolants and Hermite-Padé approximants. Such relations are a central tool in computer algebra, arising in situations such as the guessing of linear differential equations, the list-decoding of Reed-Solomon codes, or the computation of normal forms of polynomial matrices. After giving an overview of the problem and of existing fast algorithms, the emphasis will be placed on the main ideas behind the recent algorithmic improvements.
This talk involves joint work with Claude-Pierre Jeannerod, Johan Rosenkilde, Eric Schost, Grigory Solomatov, Gilles Villard, and Vu Thi Xuan.
• Vendredi 10 novembre 2017
Everett Howe (Center for Communications Research)
Constructions of curves of medium genus over F_q with many points
• Vendredi 17 novembre 2017
André Leroy (Université d'Artois)
Sur les factorisations dans les extensions de Ore
On commencera par définir une notion d'évaluation pour les polynômes de Ore à coefficients dans un anneau. On introduira ensuite les transformations pseudo linéaires et on définira les notions de polynômes de Wedderburn et de polynômes complètement réductibles. Après avoir donné plusieurs caractérisations de ces polynômes on s'intéressera à leurs factorisations en particulier dans le cas ou l'anneau de base est un anneau à division. On présentera aussi le comptage des racines généralisant et précisant le résultat de Gordon-Motzkin. On abordera la question de factorisation dans des anneaux généraux et on introduira la notion d'anneaux de polynômes de Ore libre qui semble être le bon moyen d'aborder l'évaluation à plusieurs variables gauches.
• Vendredi 24 novembre 2017
Let $$R := K[x_1,\ldots,x_n]$$ be a polynomial ring over an infinite field $$K$$, and let $$I \subset R$$ be a graded ideal. We say that $$A := K[x_1,\ldots,x_d]$$ is a Noether normalization of $$R/I$$ if $$A \hookrightarrow R/I$$ is an integral extension. Whenever $$A$$ is a Noether normalization of $$R/I$$, then $$R/I$$ is a finitely generated $$A$$-module and, thus, it has a finite minimal graded free resolution as $$A$$-module. In this talk we will study this resolution, which we call the Noether resolution of $$R/I$$. When the Krull dimension of $$R/I$$ is 1 or 2 we provide an algorithm for obtaining this resolution that involves the computation of a particular Gröbner basis of $$I$$. When $$R/I$$ is a semigroup ring we will also explain how one can replace the Gröbner basis computation by computations in the underlying semigroup.