# Seminar “Computations and Proofs” at SpecFun

Subscribe to the announcements (just click) and to the agenda (copy the link to your calendar application).

Note to potential attendees (and speakers!): In view of the security measures enforced by the current level of the Vigipirate alert system, make sure you visit our Alan Turing building with a proper ID. You will need one of us go and pick you up from the front desk.

(We also list here our PhD/HDR defenses, even when they don't take place in our main building.)

At the beginning of 2021, this seminar has paused, becoming a joint PolSys-SpecFun seminar.

## Past talks:

• 2020-12-04: 11:00-12:00 (room: online), organized jointly with the PolSys team and the working group on Transcendence and Combinatorics: Gleb Pogudin (LIX, École polytechnique), Elimination problem for ODE systems and parameter identifiability.
Elimination of unknowns in systems of polynomial equations is a standard tool of computational algebra and algebraic geometry going back to the pioneers of the subject. An analogous question of elimination of unknowns in differential-algebraic equations can be stated as follows: given a system of nonlinear differential equations in two groups of variables, $x$'s and $y$'s, describe all the consequences of the system depending solely on $x$'s. Such a differential elimination problem has been studied already by Joseph Ritt, the founder of differential algebra, who proposed the first algorithm for solving it in 1930's. Collective effort of many researchers in the field aimed at understanding and improving this algorithm culminated in modern differential elimination algorithms such as the Rosenfeld-Gröbner algorithm which is now a part of the Maple standard library.
I will talk about differential elimination from the point of view of applications to modeling. Differential elimination is the key step in one of the approaches to the parameter identifiability problem (to decide whether or not parameters can in principle be recovered from the observations). A big portion of dynamical models used in sciences are ODE system, that is, are of the form $x' = f(x)$. General algorithms like the Rosenfeld-Gröbner algorithm are applicable in this situation but there is a price to pay for their generality and versatility: many interesting instances cannot be tackled by them in reasonable time. I will describe a new projection-based elimination algorithm tailored to ODE systems which allows to perform elimination (and then assess parameter identifiability) for systems that could not be tackled before. I will conclude by speculating about potential applications of this algorithm in other domains where ODE systems often appear, for example, for computations with differential-algebraic functions.
This is based on joint work in progress with Ruiwen Dong, Emilie Dufresne, Christian Goodbrake, and Heather Harrington.
• 2020-02-24: 10:30-11:30 (room: Amphithéâtre Sophie Germain), part of a meeting of the De rerum natura project: Andrew Elvey Price, Counting lattice walks by winding angle using Jacobi theta functions, slides.
I will describe our solution to the problem of counting lattice walks by winding angle around the origin on four different lattices including the square lattice and the triangular lattice. The method uses a new decomposition of each lattice, which allows us to write functional equations characterising generating functions of these walks. We then solve these equations in terms of Jacobi theta functions, allowing us to extract information about the (differential) algebraicity and asymptotics of these generating functions. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.
• 2020-02-24: 14:15-15:15 (room: Amphithéâtre Sophie Germain), part of a meeting of the De rerum natura project: Stéphane Fischler, Indépendance algébrique effective de valeurs de E-fonctions.
Les E-fonctions ont été introduites par Siegel en 1929 : il s'agit d'une classe de fonctions qui englobe notamment la fonction exponentielle et les fonctions de Bessel. Étant donné une famille finie de E-fonctions algébriquement indépendantes, on considère l'ensemble $S$ des points algébriques en lesquels leurs valeurs sont algébriquement dépendantes. Le théorème de Siegel-Shidlovskii (démontré en 1955 et raffiné depuis par plusieurs auteurs) permet de montrer que $S$ est fini. Le but de cet exposé est de donner un algorithme permettant de déterminer cet ensemble $S$. Il s'agit d'un travail en commun avec Tanguy Rivoal.
• 2020-02-24: 16:00-17:00 (room: Amphithéâtre Sophie Germain), part of a meeting of the De rerum natura project: Pierre Lairez, Périodes : calcul numérique et applications, slides.
Grâce aux algorithmes d'intégration symbolique et de prolongement analytique numérique, on peut calculer les périodes à très grande précision. Je montrerai comment utiliser ces outils pour calculer le volume d'un ensemble semialgébrique (selon un travail commun avec Marc Mezzarobba et Mohab Safey El Din). Je montrerai aussi comment la grande précision trouve des applications au calcul de certains invariants de surfaces algébriques (selon un travail commun avec Emre Sertöz). Enfin, je montrerais quelques idées pour obtenir des bornes de séparations effectives entre les périodes et ainsi garantir le résultat de calculs numériques.
• 2020-01-20: 10:00 (room: Amphithéâtre Sophie Germain), organized as a 1-day meeting on moments: Florent Bréhard (Uppsala Universitet, Sweden), On moment problems with holonomic functions, slides.
Reconstruction methods for inverse moment problems are extensively used in many fields such as signal processing, tomography or gravimetry. We propose an algorithm that reconstructs the semi-algebraic support and the D-finite density of a measure from sufficiently many moments. Based on the framework of holonomic distributions combined with Stokes' theorem in vector calculus, our approach computes recurrences for the moments which stay linear w.r.t the coefficients of the polynomial vanishing over the support boundary. This crucial property that cannot be achieved using traditional creative telescoping algorithms, allows for an efficient reconstruction of the polynomial boundary and a holonomic system of PDEs for the density, by solving linear systems only. This is a joint work with Mioara Joldes and Jean-Bernard Lasserre.
• 2020-01-20: 11:30 (room: Amphithéâtre Sophie Germain), organized as a 1-day meeting on moments: Karol A. Penson (Sorbonne Université), Stieltjes moment problem: constructive approach towards unique and non-unique solutions, slides.
In this expository talk we present a constructive approach to generate exact solutions of the one-dimensional Stieltjes moment problem, with moments expressible via factorials and/or gamma functions. We will mainly concentrate on continuous solutions. The main ingredient of this method is a systematic use of the inverse Mellin transform and of a generalization of hypergeometric function called the Meijer G function, fully implemented in computer algebra systems. The essential property inherent in these tools is the Mellin (i.e. multiplicative) convolution. It allows one to produce exact solutions for a large family of various moment sets, especially especially those being combinatorial sequences. We enumerate various, older and more recent, criteria for positivity as well as for the uniqueness of so obtained solutions. Our method permits one to bypass (in many cases) an involved question of verifications of these criteria. Amongst concrete exemples reviewed here we mention the explicit construction of the so called Stieltjes classes of non-unique solutions via polynomial killers, the problem of non-unique Lévy stable distributions and the construction of moment filters. Finally, a possible application of this methodology to purely discrete distributions will be briefly exposed.
• 2020-01-20: 14:30 (room: Amphithéâtre Sophie Germain), organized as a 1-day meeting on moments: Jean-Bernard Lasserre (CNRS, LAAS, emeritus), Connecting optimization with spectral analysis of tri-diagonal (univariate) moment matrices, slides.
We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of $r \times r$ tri-diagonal univariate moment matrix of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of a certain univariate degree-$r$ orthonormal polynomial. This provides a strong connection between the fields of optimization, orthogonal polynomials, numerical analysis and linear algebra, via asymptotic spectral analysis of tri-diagonal symmetric matrices.
• 2020-01-20: 16:00 (room: Amphithéâtre Sophie Germain), organized as a 1-day meeting on moments: Andrew Elvey Price (LaBRI), When counting sequences are Stieltjes moment sequences, slides.
In recent years a number of authors have studied the questions of what counting sequences arising in combinatorics are Stieltjes moment sequences. I will describe a number of methods which have been used to prove this in different contexts, such as the continued fraction approach employed by Alan Sokal and a specific approach that applies to excursions on a graph. Finally I will talk about the method of constructing the associated probability measure exactly using the Stieltjes transform which we have used to for a number of principle permutation classes. Despite the existence of these methods, there are many counting sequences arising in combinatorics which are conjectured to be Stieltjes moment sequences, but for which this hasn't been proven. In particular, we make this conjecture for 1324-avoiding permutations. This talk is (mostly) joint work with Alin Bostan, Tony Guttmann and Jean-Marie Maillard. This project has received funding from the European Research Council (ERC) under the EuropeanUnion’s Horizon 2020 research and innovation programme under the Grant Agreement No. 759702.
• 2019-11-25: 10:30 (room: Henri Poincaré): Gabriel Lepetit (Institut Fourier, Grenoble), G-opérateurs au sens large et application à un théorème d'André sur les E-fonctions au sens large, script.
J'exposerai les principaux résultats connus sur la structure de l'espace des solutions d'une équation différentielle satisfaite par une G-fonction de Siegel au sens strict, et montrerai comment ils peuvent être partiellement généralisés aux G-fonctions au sens large. Ceci permet d'obtenir des résultats diophantiens sur les valeurs des E-fonctions.
• 2019-10-28: 10:30 (room: Henri Poincaré): Xavier Caruso (CNRS, Bordeaux), Residues of skew rational functions and linearized Goppa codes, slides.
Extending Gabidulin codes, Martinez-Penas recently defined linearized Reed-Solomon codes and proved that these codes exhibit an optimal minimal distance for the sum-rank metric. Martinez-Penas' construction is based on Ore's skew polynomials. The aim of this talk is to introduce a linearized version of geometric Goppa codes in the spirit of Martinez-Penas' construction. Precisely, I will first give a meaning to the notion skew rational functions and outline a theory of residues for them. This will eventually be the key for adapting the definition of classical Goppa codes in the skew setting (at least over the projective line) and showing that linearized Goppa codes are duals of Martinez-Penas' linearized Reed-Solomod codes.
• 2019-10-07: 10:30 (room: Henri Poincaré): Aude Le Gluher (LORIA, Nancy), Une approche géométrique efficace pour le calcul d'espaces de Riemann–Roch : algorithme et complexité, slides.
Le calcul effectif de bases d'espaces de Riemann–Roch intervient dans de nombreux domaines pratiques, notamment pour l'arithmétique dans les jacobiennes de courbes ou dans des codes correcteurs d'erreurs algébrico-géométriques. Nous proposons une variante probabiliste de l'algorithme de Brill et Noether décrit par Goppa pour le calcul d'une base de l'espace de Riemann–Roch $L(D)$ associé à un diviseur $D$ d'une courbe projective plane nodale $C$ sur un corps parfait $k$ suffisamment grand.

On prouve que sa complexité (estimée par le nombre d'opérations arithmétiques dans le corps $k$) est en $O(\operatorname{max}(\operatorname{deg}(C)^{2\omega}, \operatorname{deg}(D_+)^\omega))$ où $\omega \leq 2,38$ est la constante de l'algèbre linéaire et $D_+$ est le plus petit diviseur effectif vérifiant $D_+ \geq D$. Cet algorithme probabiliste peut échouer, mais sous quelques conditions, on prouve que sa probabilité d'échec est bornée par $O(\operatorname{max}(\operatorname{deg}(C)^4, \operatorname{deg}(D_+)^2)/|E|)$ où $E$ est un sous ensemble fini de $k$ dans lequel on peut choisir des éléments uniformément aléatoirement.

À notre connaissance cette borne sur la complexité est la meilleure obtenue jusqu'alors pour le calcul d'espaces de Riemann-Roch dans un cadre général. Dans le contexte du calcul de la loi de groupe dans la jacobienne d'une courbe lisse, notre borne améliore aussi la meilleure borne connue à ce jour, due à Khuri-Makdisi. Notre algorithme jouit également du fait que son efficacité repose sur deux blocs pour lesquels des algorithmes efficaces existent : algèbre linéaire et arithmétique des polynômes univariés. Nous avons implémenté cet algorithme en C++/NTL. Les résultats expérimentaux obtenus via cette implémentation semblent indiquer une amélioration des temps de calcul par rapport à l'implémentation dans le logiciel de calcul formel Magma (jusqu'à 200 fois plus rapide sur certaines instances sur de grands corps finis).

(Travaux joints avec Pierre-Jean Spaenlehauer.)
• 2019-06-17: 10:30 (room: Henri Poincaré): Julien Roques (Univ. Lyon 1), À propos des équations de Mahler.
Dans cet exposé, je montrerai que les équations de Mahler ont une structure très simple sur le corps des séries de Hahn. En guise d'application, je donnerai une démonstration de l'analogue de la conjecture de Grothendieck pour les équations de Mahler.
• 2019-05-06: 10:30 (room: Henri Poincaré): Pierre Lairez (Inria), Périodes numériques et géométrie algébrique effective, script, demo.
Grâce à des progrès récents en calcul formel (notamment par Mezzarobba et Sertöz), on peut maintenant calculer les périodes des hypersurfaces projectives lisses à très grande précision, typiquement 500 chiffres. Appliqué aux surfaces algébriques, cela permet par exemple de calculer le groupe de Picard. Pour les surfaces quartiques, on peut aussi compter les courbes rationnelles lisses incluses dans la surface. Cet exposé sera une démonstration pratique des outils utilisés, de leurs possibilités et des résultats obtenus en construisant une base de données de 180000 surfaces quartiques.
(Travail en commun avec Emre Sertöz.)
• 2019-04-08: 10:30 (room: Henri Poincaré): Gilles Villard (CNRS, ENS Lyon), On computing the determinant of generic polynomial structured matrices: univariate resultant and modular composition, slides.
We describe an approach that leads to improved complexity bounds for computing determinants of sufficiently generic structured polynomial matrices, such as univariate Toeplitz-like ones. A first application is presented for computing the resultant of two generic bivariate polynomials over a field $𝕂$. For such $p$ and $q$ in $𝕂[x,y]$ of degree $d$ in $x$ and $n$ in $y$, the algorithm computes the resultant with respect to $y$ using $(n^{2 - 1/ω}d)^{1+o(1)}$ arithmetic operations, where two $n×n$ matrices are multiplied using $O(n^ω)$ operations. Previous algorithms from the early 1970’s required time $(n^2d)^{1+o(1)}$. Another application, by handling an appropriate multiplication matrix, is modular composition of univariate polynomials. Given sufficiently generic polynomials $a$ and $g$, and given $h$, the problem is to compute $h(a) \bmod g$. If the degrees are at most $n$ then the composition is computed using $(n^{(ω +2)/3})^{1+o(1)}$ arithmetic operations, which improves upon algorithms based on Brent and Kung’s 1978 results. We use a blocking technique, exploit the structure for computing specific bases of bivariate ideals, and take advantage of fast algorithms for dense polynomial matrices. We note that the new bounds are subquadratic even when cubic matrix multiplication is used. Work done in part with Vincent Neiger (U. Limoges), Bruno Salvy (Inria, U. Lyon), and Éric Schost (U. Waterloo).
• 2019-03-11: 10:30 (room: Henri Poincaré): François Morain (LIX, École polytechnique), Fractions continues, algorithme d'Euclide rapide.
Les fractions continues sont un outil très important pour l'approximation des nombres réels, avec de nombreuses applications en théorie algorithmique des nombres ainsi qu'en cryptanalyse. Une des applications importantes est l'algorithme de Cornacchia qui résout élégamment le problème de la représentation des nombres premiers sous la forme $p = x^2 + d y^2$ avec $d > 0$. Cet exposé présentera l'application des algorithmes rapides de pgcd d'entiers à l'élaboration d'une version rapide de l'algorithme de Cornacchia.
• 2019-01-14: 10:30 (room: Henri Poincaré): Kilian Raschel (CNRS & Univ. Tours), Marches aléatoires positives en dimension trois et triangles sphériques, slides.
Lorsqu'on cherche à décrire le comportement asymptotique de marches aléatoires positives en dimension trois (par exemple pour établir un théorème limite local, aussi pour calculer la probabilité de survie ou encore pour des questions plus combinatoires de comptage de chemins), des triangles sphériques apparaissent naturellement et jouent un rôle crucial (à titre d'exemple, l'exposant critique s'exprime en termes de la valeur propre principale de ces domaines sphériques pour le problème de Dirichlet).
L'objectif de l'exposé est de présenter des liens (et leurs conséquences) entre certaines propriétés du triangle sphérique (angles remarquables, propriétés de pavage, existence d'une formule close pour la valeur propre principale) et l'étude combinatoire des marches (structure d'un groupe de réflexions lié à la marche, existence d'une factorisation dite de Hadamard, existence encore d'équations différentielles vérifiées par les fonctions génératrices comptant les marches).
Il s'agit d'un travail en cours, en commun avec Beniamin Bogosel (CMAP), Vincent Perrollaz (Tours) et Amélie Trotignon (Simon Fraser University et Tours).
• 2018-11-26: 10:30 (room: Henri Poincaré): Marni Mishna (SFU, Burnaby, Canada; CNRS & Univ. Tours), Analytic Algebraic Combinatorics, slides.
A theme in algebraic combinatorics is to find natural interpretations for quantities that come from representation theory. The Kronecker coefficients are an important example, as they remain mysterious despite study since the 1930s. This talk will connect the computation of dilated Kronecker coefficients and dilated polytope point enumeration. This offers an elementary explanation for the piecewise quasi-polynomiality of the Kronecker coefficients. Next, we will use techniques from analytic combinatorics in several variables to compute asymptotic expressions. The process is automatable and will discuss some of the associated computational challenges in addition to the results that we have already obtained. Work in collaboration with Mercedes Rosas and Sheila Sundaram.
• 2018-11-05: 14:00 (room: Thomas Flowers): Gwladys Fernandes (Univ. Lyon 1), Fonctions mahlériennes sur des corps de fonctions en caractéristique non nulle et relations algébriques.
Soit $\mathbb{K}$ un corps de fonctions en caractéristique non nulle. Le but de cet exposé est de présenter le résultat selon lequel toute relation algébrique sur $\overline{\mathbb{K}}$ entre les valeurs, en un point algébrique régulier non nul $\alpha$, de fonctions $f_{1}(z), \ldots, f_{n}(z)$ solutions d'un système mahlérien linéaire, provient de la spécialisation en $\alpha$ d'une relation algébrique sur $\overline{\mathbb{K}}(z)$ entre ces fonctions elles-mêmes. Ceci, sous l'hypothèse que l'extension $\overline{\mathbb{K}}(z)(f_{1}(z), \ldots, f_{n}(z))$ soit régulière. Nous discuterons et illustrerons cette hypothèse au cours de l'exposé. Lorsque $\mathbb{K}$ est un corps de nombres, ce résultat a été établi par B. Adamczewski et C. Faverjon à partir d'un théorème récent de P. Philippon. Dans ce cas, la condition de régularité de l'extension mahlérienne est toujours vérifiée.
• 2018-10-15: 10:30 (room: Henri Poincaré): Anand Kumar Narayanan (LIP6, Paris), Drinfeld Modules, Hasse Invariants and Factoring Polynomials over Finite Fields, slides.
We outline three novel algorithms to factor polynomials over finite fields using the arithmetic of Drinfeld modules. The first algorithm estimates the degree of an irreducible factor of a polynomial from Euler–Poincaré characteristics of random Drinfeld modules. Knowledge of a factor degree allows one to rapidly extract all factors. The second algorithm is a random Drinfeld module analogue of Berlekamp's algorithm, partly inspired by Lenstra's elliptic curve method for integer factorization. The third algorithm employs Drinfeld modules with complex multiplication and will be the primary focus of the talk. The main idea is to compute a lift of the Hasse invariant with Deligne's congruence playing a critical role. We will discuss practical implementations and complexity theoretic implications of the algorithms. The talk will be based on the papers https://arxiv.org/abs/1712.00669 and https://arxiv.org/abs/1504.07697.
• 2018-09-24: 10:30 (room: Henri Poincaré): Nicholas Coxon (Inria Saclay), Fast interpolation, evaluation and change of basis for polynomials over finite fields of characteristic two, slides.
An additive fast Fourier transform over a finite field of characteristic two efficiently evaluates polynomials at every element of an $\mathbb{F}_2$-linear subspace of the field. We view these transforms as performing a change of basis from the monomial basis to the associated Lagrange basis, and consider the problem of performing the various conversions between these two bases, the associated Newton basis, and the "novel" basis of Lin, Chung and Han (FOCS 2014). Existing algorithms are divided between two families, those designed for arbitrary subspaces and more efficient algorithms designed for specially constructed subspaces of fields with degree equal to a power of two. In the first part of this talk, we generalise techniques from both families to provide new conversion algorithms that may be applied to arbitrary subspaces, but which benefit equally from the specially constructed subspaces. We then construct subspaces of fields with smooth degree for which our algorithms provide better performance than existing algorithms. In the second part of the talk, we describe new fast algorithms for solving certain Hermite interpolation and evaluation problems over finite fields of characteristic two. The algorithms are recursive in nature, requiring standard multipoint interpolation and evaluation to be performed in the base case. Here, algorithms from the first part of the talk may be used. When not in the base case, the algorithms perform only recursive calls and some additions, allowing low overall multiplicative complexities to be obtained.
• 2018-06-11: 14:00 (room: Henri Poincaré): Antonio Jiménez-Pastor (RISC, Johannes Kepler Universität, Linz), DD-finite functions: extension of algorithms for D-finite functions.
D-finite (or holonomic) functions have been studied since the last century and an algorithmic approach was successfully developed. This talk presents a wider class built as a natural extension of the D-finite class: the DD-finite functions. These functions are defined via a linear differential equation with D-finite coefficients. In this talk, we will see closure properties of this bigger class and algorithms developed to apply those properties using a computer (and the Computer Algebra System SAGE), as well as limits of the approach.
• 2018-05-07: 14:00 (room: Henri Poincaré): Timothée Pecatte (LIP, ENS Lyon), Reconstruction algorithms for sums of affine powers, slides.
A sum of affine powers is an expression of the form $$f(x) = \sum_{i=1}^s \alpha_i (x - a_i)^{e_i}.$$ Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and Sparsest Shift. We propose algorithms that find the smallest decomposition of $f$ in the first model (sums of affine powers) for an input polynomial $f$ given in dense representation. Our algorithms only work in situations where the smallest decomposition is unique, and we provide conditions that guarantee the uniqueness of the smallest decomposition. We also consider the natural multivariate extension and propose polynomial time black-box algorithms that find the decomposition with the smallest value of $s$ for an input polynomial $f$. Our multivariate algorithms work in situations where $s$ is small enough compared to the number of variables or to the exponents $e_i$. This talk is based on two joint works with Pascal Koiran and Ignacio Garcia-Marco, accepted at ISSAC '17 & '18.
• 2018-04-23: 10:30 (room: “Henri Poincaré”): Florian Luca (U. Witwatersrand, Johannesburg, South Africa), Facteurs cyclotomiques des polynômes de Serre, slides.
On considère la famille des polynômes $P_m(X)\in {\mathbb Q}[X]$ donnée par $$\prod_{m\ge 1} (1-q^m)^{-z}=\sum_{m\ge 0} P_m(z) q^m.$$ Ces polynômes ont des connexions profondes avec la théorie des nombres, des partitions et avec la fonction $\tau$ de Ramanujan. Ils sont apparus pour la première fois dans des travaux de Newman de 1955, et ont été utilisés par Serre dans son travail de 1985 sur la lacunarité des puissances de la fonction $\eta$ de Dedekind. Ils peuvent être donnés aussi par $P_0(X)=1$ et $$P_m(X)=\frac{X}{m}\left(\sum_{k=1}^m \sigma(k) P_{m-k}(X)\right)\qquad {\text{pour}}\qquad m\ge 1,$$ où $\sigma(k)$ est la somme des diviseurs entiers positifs de $k$. Il est facile de voir que $P_m(X)$ n'a aucune racine positive. De plus, par la formule pentagonale d'Euler, on déduit que $X+1\mid P_m(X)$ pour une infinité de $m$. On se pose la question si $P_m(X)$ peut avoir comme zéros des racines de l'unité différentes de $-1$. On montre que ceci n'est jamais le cas, c'est-à-dire que si $\zeta$ est une racine de l'unité d'ordre $N\ge 3$ et si $m\ge 1$, alors $P_m(\zeta)\ne 0$. La preuve utilise des résultats classiques sur les corps finis, et un petit peu de théorie analytique des nombres. Travail en commun avec Bernhard Heim (German University of Technology, Oman) et Markus Neuhauser (RWTH, Aachen University).
• 2018-04-23: 14:00 (room: “Henri Poincaré”): Florian Luca (U. Witwatersrand, Johannesburg, South Africa), La suite des multiples d'un point d'ordre infini sur une courbe elliptique, slides.
Soit $E$ use courbe elliptique donnée par l'équation $y^2=x^3+Ax+B$ avec $A,B\in {\mathbb Z}$, et soit $P=(x_1/z_1^2,y_1/z_1^3)$ un point rationnel d'ordre infini sur $E$, où $x_1,y_1,z_1$ sont trois entiers premiers entre eux. On écrit $nP=(x_n/z_n^2,y_n/z_n^3)$ pour tous les $n\ge 1$. Dans cet exposé je présenterai deux démonstrations du fait que la suite $\{z_n\}_{n\ge 1}$ ne coïncide pas ultimement avec $\{u_{n^2}\}_{n\ge 1}$, pour aucune suite $\{u_n\}_{n\ge 1}$ vérifiant une récurrence linéaire à coefficients constants. Travail en commun avec Tom Ward (Leeds).
• 2018-03-05: 10:30 (room: “Grace Hopper”): Mohab Safey El Din (Sorbonne Univ., CNRS, Inria, LIP6), On symbolic homotopy algorithms and solving structured polynomial systems.
Polynomial systems which arise in many applications often enjoy structural properties. In this talk, we focus on multi-homogeneous systems and provide bit complexity estimates for solving them which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system, under some genericity assumptions. The assumptions essentially imply that the Jacobian matrix of the system under study has maximal rank at the solution set and that this solution set is finite. The algorithm is probabilistic and a probability analysis is provided. Next, we apply these results to the problem of optimizing a linear map on the real trace of an algebraic set. Under some genericity assumptions, we provide bit complexity estimates for solving this polynomial minimization problem. Joint work with E. Schost (U. Waterloo Canada).
• 2018-02-26: 10:30 (room: “Henri Poincaré”): Svyatoslav Covanov (INRIA), Multiplication algorithms for integers, polynomial and matrices, slides.
Various problems of symbolic computation use the multiplication as a building block. For example, problems in algorithmic number theory, such as the search of large primes or the computation of digits of $\pi$, often require fast multiplication of large integers. Efficient algorithms to multiply polynomials are also needed in the computation of resultants or gcd of polynomials. The algorithms solving these problems can be decomposed into two families: algorithms that are asymptotically fast and algorithms that are efficient for small sizes. This presentation will describe an algorithm using fast Fourier transform and generalized Fermat primes to multiply large integers, which falls in the first family of algorithms, and a method to search, over finite fields, optimal algorithms in the second family.
• 2018-01-17: 16:00 caution, not a Monday! (room: “Grace Hopper”): Tanay Wakhare (U. Maryland), Finite generating functions for the sum of digits sequence.
I will show some results about finite generating functions associated with the sequence $(s_b(n))$, where $s_b(n)$ is the sum of the digits of the representation in base $b$ of the integer $n$. This sequence was extensively studied by J.-P. Allouche and J. Shallit — see for example their book “Automatic Sequences, Theory, Applications, Generalizations”. Our generalizations include some Lambert series and infinite products related to the sequence $s_b(n)$. This is joint work with C. Vignat.
• 2017-12-15: 11:00 (salle B 107, salle de séminaires du LIPN, Université Paris 13): Alin Bostan (Inria), Calcul formel pour la combinatoire des marches, slides.
Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra has been used to explore and to solve a number of difficult questions related to lattice walks. We give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.
• 2017-12-11: 14:30 (room: “Robin Milner”): Michael Wallner (Université Paris 13), Asymptotic Enumeration of Compacted Binary Trees with Height Restrictions, slides.
When storing rooted trees it is useful to consider compression techniques. A simple idea is to store isomorphic subtrees only once and mark repeated occurrences with a pointer. A classical algorithm to establish such a compaction was analyzed by Flajolet, Sipala, and Steyaert. The resulting structure is called a compacted tree, being in fact no more a tree but a directed acyclic graph. Our goal is the enumeration of such structures. Since the enumeration turns out to be extremely difficult, we restrict it to a subproblem by imposing a bound on the so-called right height. We solve this enumeration problem with the help of generating functions. Due to the superexponential growth of the counting sequence we use exponential generating function despite the fact that these objects are unlabeled. We first derive a calculus on exponential generating function capturing their recursive nature. This leads to a sequence of differential equations for the generating functions (also implying their D-finiteness) for which a singularity analysis is carried out. This work is based on joint work with Antoine Genitrini, Bernhard Gittenberger, and Manuel Kauers.
• 2017-12-04: 14:00 (room: “Sophie Germain”): Thomas Sibut-Pinote (PhD at INRIA, currently post-doc at UCL), PhD defense: Investigations en Mathématiques Assistées par Ordinateur: Expérimentation, Calcul et Certification.
This thesis presents three contributions to the topic of computer-assisted proofs: both in the case of proofs relying on computations and of formal proofs produced and verified using a piece of software called a proof assistant. We first illustrate the theme of experimentation at the service of proofs by programming a symbolic manipulation tool and using it to find and demonstrate a result about matrix multiplications. In a second part, we use a proof assistant to write a proof of Apéry's theorem, which is based on complex computations. These computations are performed by an efficient external program and are then verified by this proof software. In the third contribution, we propose a program which computes integrals and simultaneously builds proof that the result is correct. We use this program to find errors in published results. Manuscript.
• 2017-11-28 caution, not a Monday! 10:30 (room: “Henri Poincaré”): Jean-Paul Allouche (Institut Mathématique de Jussieu), Transcendance et algébricité : pourquoi et comment ?
Que signifie au fond le symbole √2  qui désigne ce qu'on pense être historiquement le premier nombre « irrationnel » ? Et pourquoi s'intéresser aux équations résolubles par radicaux ? Qu'est-ce qu'un nombre constructible à la règle et au compas ? Pourquoi s'intéresser aux nombres algébriques ? aux nombres transcendants ? Comment montrer l'algébricité ou la transcendance d'un nombre réel ? Peut-on détecter la transcendance ou l'algébricité d'un réel à partir de son développement ? par exemple si « l'un de ses développements » est une suite automatique — i. e. engendrée par automate ?
Nous essaierons d'aborder ces questions aussi bien pour les nombres réels que pour d'autres types de « nombres » : en caractéristique positive, pour des séries formelles, pour des fractions continuées. Nous rappellerons aussi des conjectures célèbres toujours ouvertes, par exemple la transcendance de la constante d'Euler, des valeurs de la fonction zêta aux entiers impairs, de la constante de Catalan, etc.
• 2017-11-28 caution, not a Monday! 14:00 (room: “Henri Poincaré”): Guoniu Han (Institut de Recherche Mathématique Avancée, Strasbourg), Irrationality exponents and Hankel determinants, slides.
In 1998, Allouche, Peyriere, Wen and Wen established a congruence relation between the Hankel determinants of the Thue-Morse sequence, and proved that all the Hankel determinants of the Thue-Morse sequence are nonzero. This property allowed Bugeaud to prove that the irrationality exponents of the Thue-Morse-Mahler numbers are exactly 2. Similar properties for other sequences were derived by Coons, Guo, Wu, Wen by using the same method. In this talk, we present several other proofs and methods. In particular, a one-page proof and a computer assisted proof. We show that the irrationality exponents of large classes of automatic numbers and Mahler numbers are exactly equal to 2.
• 2017-11-20: 10:30 (room: “Henri Poincaré”): Emre Sertöz (Max-Planck-Institute MiS, Leipzig), Computing periods of hypersurfaces.
Given a complex manifold $X$, the periods of $X$ are complex numbers which describe the complex structure of $X$ upon the underlying topological manifold. For instance in dimension 1, the Abel-Jacobi map associates to each genus-$g$ curve its $(g\times2g)$-matrix of periods, which completely determines the curve. In dimension 2, the periods of $K3$ surfaces can be stored in a vector of length 22 and this vector will determine the $K3$ surface.
In this talk, we will cover the basics on periods and then demonstrate an algorithm for computing the periods of smooth hypersurfaces in projective space. Our computer program takes as input the equations of a smooth hypersurface and outputs the periods numerically. We do this by computing the periods of a fixed hypersurface explicitly and computing the system of ODEs (the Picard-Fuchs equations) which describe the change of periods as we deform the fixed hypersurface to the one given.
• 2017-11-20: 14:00 (room: “Henri Poincaré”): Michael Coons (University of Newcastle, Australia), $2$-automatic sequences, Lyapunov exponents and a dynamical analogue of Lehmer's Mahler measure problem, slides.
We show that the Mahler measure of every height-one polynomial can be expressed as the maximal Lyapunov exponent of a matrix cocycle that arises in the spectral theory of $2$-automatic sequences. In this way, one comes up with a sort of dynamical analogue of Lehmer's problem on minimal Mahler measures. This is joint work with Michael Baake and Neil Manibo (University of Bielefeld, Germany).
• 2017-10-27: 10:30 caution, not a Monday! (room: “Henri Poincaré”): Lawrence Paulson (University of Cambridge), Proof Assistants: From Symbolic Logic To Real Mathematics?
Mathematicians have always been prone to error. As proofs get longer and more complicated, the question of correctness looms ever larger. Meanwhile, proof assistants — formal tools originally developed in order to verify hardware and software — are growing in sophistication and are being applied more and more to mathematics itself. When will proof assistants finally become useful to working mathematicians? Mathematicians have used computers in the past, for example in the 1976 proof of the four colour theorem, and through computer algebra systems such as Mathematica. However, many mathematicians regard such proofs as suspect. Proof assistants (e.g. Coq, HOL and Isabelle/HOL) are implementations of symbolic logic and were originally primitive, covering only tiny fragments of mathematical knowledge. But over the decades, they have grown in capability, and in 2005, Gonthier used Coq to create a completely formal proof of the four colour theorem. More recently, substantial bodies of mathematics have been formalised. But there are few signs of mathematicians adopting this technology in their research. Today's proof assistants offer expressive formalisms and impressive automation, with growing libraries of mathematical knowledge. More however must be done to make them useful to mathematicians. Formal proofs need to be legible with a clear connection to the underlying mathematical ideas.
• 2017-10-16: 10:30 (room: “Henri Poincaré”): Xavier Allamigeon (INRIA, CMAP, X), Log-barrier interior point methods are not strongly polynomial.
We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with $3r+1$ inequalities in dimension $2r$ for which the number of iterations performed is in $\Omega(2^r)$. The total curvature of the central path of these linear programs is also exponential in $r$, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko. Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature, in a general setting. (Joint work with P. Benchimol, S. Gaubert, and M. Joswig.)
• 2017-06-08: 14:00 (room: “Henri Poincaré”; this session is organized jointly with the Max seminar): Manuel Eberl (Technische Universität München), Automatic asymptotics in Isabelle/HOL, slides.
Isabelle/HOL is an interactive theorem prover (also called “proof assistant”). It provides a logical environment in which mathematical concepts can be defined and theorems about them can be proven. The system guides and assists the user in writing formal proofs, while every step of the proof is computer-checked, which minimises the possibility of mistakes.
This talk will give a brief overview of Isabelle/HOL, followed by a more detailed excursion into my project of bringing more tools for asymptotic analysis into Isabelle/HOL; in particular, this includes a procedure to automatically prove limits and “Big-O” estimates of real-valued functions similarly to computer algebra systems like Mathematica and Maple—but simultaneously proving every step of the process correct.
• 2017-06-06: 10:30 (room: “Henri Poincaré”): Timothy Budd (CEA, Université Paris-Saclay), Elliptic functions count walks on the square lattice with winding, slides.
I'll discuss the combinatorics of simple walks on ${\mathbb Z}^2$ when keeping track of the winding angle around the origin. This problem turns out to be closely related to a combinatorial problem for planar maps that has been solved before in the literature. I'll explain the relations and the role of elliptic functions. Several applications will be presented, including a new way to count Gessel-type walks in the quadrant (OEIS A135404).
• 2017-04-10: 10:30 (room: “Grace Hopper”): Georges Gonthier (INRIA), Formalising mathematical conventions.
One major difficulty in the computer formalisation of mathematical material is that much of it relies on conventions that are not explicitly described by the definitions and theorems that comprise the visible, formally rigorous part of the material. Examples of such conventions include the interpretation of new notation, the expected implicit usage pattern of definitions and theorems, and specific lines of arguments that depart from traditional logical deduction rules. These conventions are rarely described explicitly, and are usually acquired by going through examples and exercises. Nevertheless, conventions are essential to the correct formal interpretation of definitions and theorems, and computer formalisations must largely support them in order to be at all relevant or even feasible. While the informality with which conventions are usually described would suggest using artificial intelligence methods to implement this support, many if not most can be successfully captured with the appropriate use of software engineering and programming techniques. This talk will cover a series of examples of such techniques, drawn from our experience with the proofs of the Four Colour and Odd Order theorems.
• 2017-04-10: 14:00 (room: “Henri Poincaré”): Alin Bostan (Inria), Algorithmic proof for the transcendence of D-finite power series, slides.
Given a sequence represented by a linear recurrence with polynomial coefficients and sufficiently many initial terms, a natural question is whether the transcendence of its generating function can be decided algorithmically. The question is non trivial even for sequences satisfying a recurrence of first order. An algorithm due to Michael Singer is sufficient, in principle, to answer the general case. However, this algorithm suffers from too high a complexity to be effective in practice. We will present a recent method that we have used to treat a non-trivial combinatorial example. It reduces the question of transcendence to a (structured) linear algebra problem.
• 2017-03-09: 11:00 (room: “Gilles Kahn”): Henk Barendregt (Radboud University Nijmegen), Axiomatizing consciousness, with cognitive and soteriological applications.
Despite millenia of efforts in philosophy, science, and phenomenology, a satisfactory scientific definition and explanation of consciousness is still lacking. This talk proposes a description of consciousness based on the axiomatic method of Aristotle, by axioms that are inspired by classical Buddhist psychology, computer science, and cognitive neuroscience.
Consciousness is defined as a stream of configurations that consist of three components: object, state, and action. The configurations change in discrete moments in time, while their three components influence each other recurrently, depending on the situation in the world. Mindfulness enables modifying the stream of configurations by taking states as objects of consciousness, on which an influence can be exerted.
Several mental mechanisms can be understood by the axiomatic theory. 1. Memory, learning and deconditioning. 2. Worldly and existential (mental) suffering, including clinical phenomena. 3. The Church-Turing thesis on human computability. Applications of the understanding of mental suffering can be found in clinical practice and meditation towards the attenuation and dissolution of existential suffering. The validity of these practices are increasingly investigated in cognitive (neuro)psychology.
• 2017-03-06: 10:30 (room: “Grace Hopper”): Damien Rouhling (INRIA), Refinement: a reflection on proofs and computations, slides.
Modern proof assistants have to deal with problems of increasing complexity and rely more and more on computation to automate proofs. However, efficient algorithms are usually complex and the proof of their soundness often requires the formalization of advanced mathematics. This creates a tension between efficiency and ease of proof.
We will present a framework originally designed for algebra and allowing to deal with both aspects separately. This framework makes it possible both to prove more easily the soundness of complex algorithms and to use them to automate proofs. We will then focus on insights this framework gave us into the design of computation-based proof procedures.
• 2017-02-20: 10:30 (room: “Grace Hopper”): Dorian Nogneng (LIX), Sur la complexité de semi-anneau des polynômes de Schur, slides.
La complexité de semi-anneau est la version de la complexité de circuit arithmétique qui n'autorise que deux opérations : l'addition et la multiplication. On montre que la complexité de semi-anneau d'un polynôme de Schur indexé par une partition $\lambda = (\lambda_1 \geq \lambda_2 \geq ...)$ est bornée par $O(\log(\lambda_1))$ si le nombre de variables, $k$, est fixé.
• 2017-02-20: 14:00 (room: “Grace Hopper”): Joris van der Hoeven (CNRS, LIX), Évaluation uniformément rapide de fonctions holonomes, slides.
Etant donnée une fonction holonome $f$ et un point d'évaluation fixe $z$, il est connu que l'évaluation de $f$ en $z$ peut se faire asymptotiquement rapidement en fonction du nombre de chiffres souhaités. Dans notre exposé, nous montrons que ce résultat de complexité vaut uniformément en $z$ sous quelques restrictions naturelles.
• 2017-01-30: 10:30 (room: “Henri Poincaré”): Stéphane Fischler (Université Paris-Sud), Lemme de Shidlovsky et irrationalité de valeurs de zêta, script.
Le lemme de Shidlovsky est une majoration de l'ordre d'annulation en 0 d'une combinaison linéaire, à coefficients polynomiaux, de fonctions holonomes. En suivant des travaux de Bertrand-Beukers et Bertrand, on peut le généraliser pour qu'il s'applique aux solutions de problèmes d'approximation de Padé en plusieurs points (y compris éventuellement à l'infini). Cela permet d'obtenir une nouvelle preuve du théorème de Ball-Rivoal sur l'irrationalité d'une infinité de valeurs de la fonction zêta de Riemann aux entiers impairs, dans laquelle le critère d'indépendance linéaire de Nesterenko est remplacé par celui de Siegel. La même approche fournit aussi une nouvelle preuve, et un raffinement, du théorème de Nishimoto sur les valeurs de fonctions L de caractères de Dirichlet.
• 2017-01-30: 14:00 (room: “Philippe Flajolet”): Tanguy Rivoal (CNRS and Université Grenoble Alpes), Indépendence linéaire de valeurs de $G$-fonctions.
Les très classiques fonctions polylogarithmes sont définies par $\operatorname{Li}_s(z):=\sum_{k=0}^\infty \frac{z^{k+1}}{(k+1)^s}$. En 2001, j'ai montré que pour tout nombre algébrique réel $\alpha$ tel que $0<\vert \alpha\vert<1$ et pour tout entier $S$ assez grand, la dimension du $\mathbb Q(\alpha)$-espace engendré par $1, \operatorname{Li}_1(\alpha), \operatorname{Li}_2(\alpha), \ldots, \operatorname{Li}_S(\alpha)$ est supérieure ou égale à $c \log(S)$, où $c>0$ est une constante qui dépend seulement de $[\mathbb Q(\alpha):\mathbb Q]$. Ceci a été étendu en 2006 par R. Marcovecchio à tous les nombres algébriques $\alpha$ tels que $0<\vert \alpha \vert<1$.
Le but de mon exposé est de présenter une généralisation de ce résultat. Considérons une $G$-fonction $\sum_{k=0}^\infty A_k z^k\in \bar{\mathbb Q}[[z]]$ de rayon de convergence $R>0$, dont on demande seulement qu'elle soit non polynomiale. Soit $\mathbb K$ un corps de nombres contenant tous les $A_k$. Fixons un nombre algébrique $\alpha \in \mathbb K$ tel que $0<\vert \alpha \vert < R$ et soit $\Phi_{\alpha, S}$ le $\mathbb K$-espace vectoriel engendré par toutes les valeurs de $G$-fonctions $F^{[s]}_n(\alpha):=\sum_{k=0}^\infty A_k \frac{\alpha^{k+n}}{(k+n)^s}$, où $s=0, \ldots, S$ et $n\ge 1$.
Théorème (Fischler–Rivoal, 2017). Dans ces conditions, il existe des constantes effectives $u_{\mathbb K, F}>0$ et $v_F>0$ telles que $u_{\mathbb K, F} \log(S) \le \dim_{\mathbb K} \Phi_{\alpha, S} \le v_F S$ lorsque $S$ est assez grand. L'ensemble $\{F^{[s]}_n(\alpha), \; 1\le n\le v_F, s\ge 0\}$ contient une infinité de valeurs irrationnelles.
J'esquisserai la démontration de ce théorème, qui est beaucoup plus compliquée que dans le cas des polylogarithmes. Elle utilise des propriétés fines des $G$-fonctions (en particulier les résultats d'André, Chudnovsky et Katz), l'analyse de singularités et la méthode du col pour estimer précisément le comportement asymptotique d'une série « auxiliaire » ainsi qu'un nouveau critère d'indépendence linéaire à la Nesterenko.
(Travail en commun avec Stéphane Fischler.)
• 2017-01-09: 11:00 (room: “Philippe Flajolet”): Marni Mishna (Simon Fraser University), Universality classes for weighted lattice paths: where probability and ACSV meet, slides.
Lattice paths are very classic objects in both probability theory and enumerative combinatorics. In particular, weighted models bridge the gap between the two approaches very neatly. We consider an example, the Gouyou-Beauchamps model of lattice walks in the first quadrant, and discuss how to determine asymptotic enumeration formulas parameterized by the weights. The major tool is the theory of analytic combinatorics in several variables (ACSV) and we identify six different kinds of asymptotic regimes (called universality classes) which arise according to the values of the weights. Because we are able to explicitly and generically compute the constants of the asymptotic formula, we can determine a formula for a family of discrete harmonic functions. Furthermore, we are able to demonstrate an infinite class of models for which the counting generating function is not D-finite. (Work in collaboration with Julien Courtiel, Stephen Melczer and Kilian Raschel.)
• 2017-01-09: 14:00 (room: “Philippe Flajolet”): Guy Fayolle (INRIA, emeritus), Random walks in the quarter-plane: explicit criterions for the finiteness of the associated group in the genus 1 case, slides.
In the Small Yellow Book (FIM, 1999), original methods were proposed to determine the invariant measure of random walks in the quarter plane with small jumps, the general solution being obtained via reduction to boundary value problems. An important quantity, the so-called group of the walk, allows to deduce theoretical features about the nature of the solutions. When its order is finite, necessary and sufficient conditions have been given for the solution to be rational or algebraic. Assuming the underlying algebraic curve is of genus 1, we propose a concrete criterion allowing to decide whether or not the group has a finite prescribed order $n$. It turns out that this criterion is always tantamount to the cancellation of a single constant, which can be expressed as the determinant of a matrix of order 3 or 4, whose entries depends in a polynomial way on the coefficients of the walk.
(This is a joint work with Roudolf Iasnogorodski.)
• 2016-12-12: 10:30 (room: “Grace Hopper”): Guillaume Moroz (INRIA), Un algorithme rapide pour le calcul du résultant tronqué, slides.
Soient $P$ et $Q$ deux polynômes de $K[x][y]$, de degrés au plus $d$, et à coefficients dans l'anneau $K[x]$, où $K$ est un corps. Le résultant de $P$ et $Q$ est un polynôme $R ∈ K[x]$ de degré au plus $2d²$. Le meilleur algorithme connu pour calculer $R$ requiert $Õ(d^3)$ opérations arithmétiques dans $K$, où la notation $Õ$ signifie que nous omettons les facteurs poly-logarithmiques. Nous montrerons que si l'on s'intéresse uniquement à calculer les $k$ premiers coefficients de $R$, il existe un algorithme permettant de calculer $R \bmod x^k$ en $Õ(kd)$ opérations dans $K$.
• 2016-12-05: 14:30 (room: “Sophie Germain”): Louis Dumont (INRIA), PhD defense: Algorithmes rapides pour le calcul symbolique de certaines intégrales de contour à paramètre.
Cette thèse traite de problèmes d'intégration symbolique en calcul formel. L'objectif principal est de mettre au point des algorithmes permettant de calculer rapidement des fonctions qui sont présentées sous la forme d'intégrales de contour dépendant d'un paramètre. On commence par aborder le problème du calcul de l'intégrale d'une fraction rationnelle bivariée par rapport à l'une de ses variables. Le résultat est alors une fonction algébrique qui s'exprime comme une somme de résidus de l'intégrande. On met au point deux algorithmes qui calculent efficacement un polynôme annulateur pour chacun des résidus, et ensuite pour la somme, ce qui donne accès à un polynôme annulateur pour l'intégrale elle-même. Ces algorithmes s'appliquent presque directement au calcul d'un polynôme annulateur pour la diagonale d'une fraction rationnelle bivariée, c'est-à-dire la série univariée obtenue à partir du développement en série d'une fraction rationnelle bivariée en ne gardant que les coefficients diagonaux. En effet, ces diagonales peuvent s'écrire comme des intégrales de fractions rationnelles. Dans une autre application, on donne un nouvel algorithme pour le développement des séries génératrices de plusieurs familles de marches unidimensionnelles sur les entiers. Il repose sur une analyse fine des tailles des équations algébriques et différentielles satisfaites par ces séries. Dans un second temps, on s'intéresse au calcul de l'intégrale d'un terme mixte hypergéométrique et hyperexponentiel. Cette fois-ci le résultat est une suite polynomialement récursive. On élabore une méthode pour mettre sous forme normale les divers décalages d'un terme donné. Ceci permet d'appliquer la méthode du télescopage créatif par réductions pour calculer efficacement une récurrence à coefficients polynomiaux satisfaite par l'intégrale.
• 2016-11-28: 10:30 (room: “Grace Hopper”): Boris Adamczewski (CNRS et Institut Camille Jordan, Lyon), Résultats récents en méthode de Mahler.
La méthode de Mahler vise en premier lieu à obtenir des résultats de transcendance et d'indépendance algébrique pour les valeurs, aux points algébriques, de fonctions analytiques satisfaisant à certaines équations fonctionnelles. Introduite par le mathématicien éponyme à la fin des années vingt, elle fut longtemps négligée avant de connaître un renouveau à partir des années soixante-dix. Plusieurs progrès importants ont été réalisés récemment. Dans cet exposé, je discuterai de ces avancées et en particulier de leur lien avec la théorie des automates finis.
• 2016-11-14: 10:30 (room: 2017, “Philippe Flajolet”): Jérémy Berthomieu (Université Paris 6), Guessing linear recurrence relations of sequence tuples and P-recursive sequences with linear algebra, slides.
Given several $n$-dimensional sequences, we first present an algorithm for computing the Gröbner basis of their module of linear recurrence relations. For a sequence $(u_i)_{i\in\mathbb{N}^n}$, we then deal with computing the linear recurrence relations with polynomial coefficients in $i$ satisfied by the sequence. Calling directly the aforementioned algorithm on the tuple of sequences $\left((i^j\,u_i)_{i\in\mathbb{N}^n}\right)_j$ for retrieving the relations yields redundant relations. When the module of relations of a such a sequence has an extra structure of a $0$-dimensional right ideal of an Ore algebra, we design a more efficient algorithm that takes advantage of this extra structure for computing the relations. Finally, we show how to incorporate Gröbner bases computations in an Ore algebra $\mathbb{K}\langle t_1,\ldots,t_n,x_1,\ldots,x_n\rangle$, with commutators $x_k\,x_l-x_l\,x_k=t_k\,t_l-t_l\,t_k= t_k\,x_l-x_l\,t_k=0$ for $k\neq l$ and $t_k\,x_k-x_k\,t_k=x_k$, into this algorithm. This allows us to compute faster the Gröbner basis of the ideal spanned by the first relations, such as in 2D- or 3D-space walks examples. This is a joint work with Jean-Charles Faugère.
• 2016-11-14: 14:00 (room: 2017, “Philippe Flajolet”): Suzy Maddah (INRIA), On generalized hypergeometric solutions of linear differential systems of the first order, slides and a Maple worksheet (pdf).
In this talk, we consider linear differential systems of the first order (equivalently linear differential equations of arbitrary order), and we question whether they can be solved in terms of generalized hypergeometric functions. This question is motivated by the many properties of the latter, which arise in physics and combinatorics. The problem has been tackled in the literature for certain second-order differential equations, namely Bessel's, Whittaker's, Kummer's, and Gauss's. We propose a new algorithm that surpasses the restrictions on the dimension of the system, and equivalently on the order of the equation. This is ongoing joint work with Frédéric Chyzak.
• 2016-11-07: 10:30 (room: “Grace Hopper”): Valérie Berthé (CNRS, IRIF), Analyse de l’algorithme de pgcd de Brun, slides.
Nous étudions un algorithme de calcul du pgcd multiple, dérivé de l’algorithme de fractions continues multidimensionnel de Brun. Cet algorithme exécute la division euclidienne de la plus grand entrée par la seconde plus grande entrée. Nous considérons les analyses dans le pire cas et en moyenne. Nous montrons en particulier que le nombre d’étapes est linéaire par rapport à la taille des entrées. Les méthodes employées ici relèvent de l’analyse dynamique d’algorithmes. Nous comparons également cet algorithme avec l’algorithme de pgcd de Knuth. Il s’agit d'un travail en collaboration avec L. Lhote et B. Vallée.
• 2016-11-07: 14:00 (room: “Grace Hopper”): Vincent Neiger (ENS de Lyon, LIP), Fast computation of normal forms of polynomial matrices, slides.
In this talk, we present recent results about fast algorithms for fundamental operations for matrices over the ring $K[X]$ of univariate polynomials. We mainly focus on the computation of normal forms, obtained by transforming the input matrix via elementary row operations. Depending on a degree measure specified by a “shift”, these normal forms range from the Hermite form, which is triangular, to the Popov form, which minimizes the degrees of the rows.
For Popov or Hermite forms of $m\times m$ nonsingular matrices with entries of degree less than $d$, the previous fastest algorithms use $\operatorname{\tilde O}(m^w d)$ operations, where $w$ is the exponent of $K$-linear algebra. We will discuss improvements in three directions:
1. improving the cost bound to $\operatorname{\tilde O}(m^w D/m)$, where $D/m$ is a type of average degree of the input matrix;
2. derandomizing Hermite form computation;
3. achieving fast computation for arbitrary shifts. The last point will lead us to consider the problem of solving systems of linear modular equations over $K[X]$, which generalizes Hermite–Padé approximation and rational reconstruction.
The second direction is joint work with George Labahn and Wei Zhou (U. Waterloo, ON, Canada).
• 2016-10-24: 10:30 (room: “Grace Hopper”): Pierre Lairez (Inria), Étude de la stabilité numérique de la résolution des équations différentielles $p$-adiques.
Les nombres $p$-adiques apparaissent en calcul formel comme un intermédiaire pratique entre les nombres entiers (ou rationnels) et les entiers modulo $p$. Il permettent de maitriser la croissance des coefficients tout en restant dans un cadre de caractéristique nulle. Cependant, et c'est le revers de la médaille, les nombres $p$-adiques ne se manipulent que de manière approchée et pour garantir la pertinence du résultat il faut analyser la stabilité numérique des calculs effectués.
Dans « On $p$-adic differential equations with separation of variables », avec Tristan Vaccon, nous étudions le calcul du développement en série des solutions de certaines équations différentielles. C'est un problème qui intervient lors du calcul avec des nombres algébriques en caractéristique positive, ou lors du calcul d'isogénies entre courbes elliptiques. Nous montrons que la stabilité de l'itération de Newton est optimale.
• 2016-10-10: 10:30 (room: “Philippe Flajolet”): Suzy Maddah (INRIA), Maple packages for linear differential systems with singularities, slides.
In this talk, we give an overview of our Maple packages which treat and compute formal solutions of certain classes of ordinary (perturbed) and partial linear differential systems.
• 2016-06-27: 10:30 (room: “Grace Hopper”): Philippe Dumas (INRIA), Fast computation of the $N$th term of an algebraic series over a finite prime field, slides.
We address the question of computing one selected term of an algebraic power series. In characteristic zero, the best algorithm currently known for computing the $N$th coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in $\sqrt{N}$. We show that over a prime field of positive characteristic $p$, the complexity can be lowered to $O(\log N)$. The mathematical basis for this dramatic improvement is a classical theorem stating that a formal power series with coefficients in a finite field is algebraic if and only if the sequence of its coefficients can be generated by an automaton. We revisit and enhance two constructive proofs of this result for finite prime fields. The first proof uses Mahler equations, whose sizes appear to be prohibitively large. The second proof relies on diagonals of rational functions; we turn it into an efficient algorithm, of complexity linear in $\log N$ and quasi-linear in $p$.
• 2016-06-27: 11:00 (room: “Grace Hopper”): Louis Dumont (INRIA), Efficient algorithms for mixed creative telescoping.
Creative Telescoping is a powerful computer algebra paradigm—initiated by Doron Zeilberger in the 90s—for dealing with definite integrals and sums with parameters. We address the mixed continuous-discrete case, and focus on the integration of bivariate hypergeometric/hyperexponential terms. We design a new creative telescoping algorithm operating on this class of inputs. The new algorithm, as other most recent creative telescoping algorithms, relies on a reduction strategy. This approach is efficient and avoids the costly computation of the normalized certificate. Its analysis reveals tight bounds on the size of the telescoper.
• 2016-06-06: 10:30 (room: “Grace Hopper”): Stephen Melczer (University of Waterloo and ENS Lyon), Symbolic-numeric tools for analytic combinatorics in several variables.
Analytic combinatorics studies the asymptotic behaviour of sequences through the analytic properties of their generating functions. In addition to the (now classical) univariate theory, recent work in the study of analytic combinatorics in several variables has shown how to derive asymptotics for the coefficients of certain D-finite functions by representing them as diagonals of multivariate rational functions. This talk examines the problem from the point of view of computer algebra: given a multivariate rational function $G/H$ whose Taylor expansion in an open domain of convergence around the origin has all non-negative coefficients (known as the ‘combinatorial case’) we determine, under certain generic conditions, dominant asymptotics for the diagonal coefficient sequence in bit complexity singly exponential in the total degree of the denominator $H$. This provides, to our knowledge, the first complexity estimates for the theoretical work of Pemantle and Wilson, and their collaborators, on analytic combinatorics in several variables. Several applications to different areas of combinatorics and number theory will be discussed.
• 2016-06-06: 14:00 (room: “Grace Hopper”): Jacques-Arthur Weil (ESPE, Limoges), Computing the Lie algebra of the differential Galois group of irreducible linear differential systems.
We consider a linear differential system $[A] : y'=A \, y$ with coefficients in $\mathbb C(x)$. The differential Galois group $G$ of $[A]$ is a linear algebraic group which measures the algebraic relations among solutions. Although there exist general algorithms to compute $G$, none of them is either practical or implemented. We will present an algorithm to compute the Lie algebra $\mathfrak{g}$ of $G$ (without a priori computing $G$) when $[A]$ is absolutely irreducible. This work is part of a more general program which may be discussed in the end of the talk. The algorithm is implemented in Maple.
This is joint work with M. Barkatou, T. Cluzeau (XLIM, Université de Limoges) and L. Di Vizio (CNRS, Université de Versailles-St Quentin).
• 2016-05-30: 10:30 (room: “Grace Hopper”): Nicolas Thiéry (Université Paris Sud), Infrastructure pour du code générique dans SageMath (Catégories, axiomes, constructions, ...), slides and SageMath notebook.
Le logiciel libre SageMath permet de manipuler des milliers d'objets mathématiques différents avec des dizaines de milliers de fonctions. Un système de cette taille requiert une infrastructure permettant l'écriture et l'organisation de code, de documentation et de tests génériques s'appliquant uniformément à tous les objets satisfaisant certaines propriétés. Dans cet exposé, nous décrirons l'infrastructure implantée dans SageMath — qui s'appuie sur la programmation objet classique en Python, avec des mécanismes pour passer à l'échelle (classes dynamiques, mixins, ...) s'appuyant sur la forte sémantique disponible (catégories, axiomes, constructions) — et la comparerons avec ce qui est fait dans d'autres systèmes.
• 2016-05-30: 14:00 (room: “Grace Hopper”): Frédéric Chyzak (Inria), Computing solutions of linear Mahler equations, slides.
Mahler equations relate evaluations of the same function f at iterated bth powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present and analyze polynomial-time algorithms for solving linear Mahler equations for series, polynomials, and rational functions. (Joint work with Th. Dreyfus, Ph. Dumas, and M. Mezzarobba.)
• 2016-04-25: 10:30 (room: “Grace Hopper”): Jehanne Dousse (Universität Zürich), Identités de partitions et résolution d'équations aux $q$-différences, slides.
Une partition d'un entier $n$ est une suite décroissante d'entiers positifs (appelés parts) dont la somme est égale à $n$. Les identités de Rogers-Ramanujan établissent que pour tout $n$, le nombre de partitions de $n$ telles que la différence entre deux parts consécutives est au moins 2 est égal au nombre de partitions de $n$ en parts congrues à 1 ou 4 modulo 5. Plus généralement, les identités du type Rogers-Ramanujan établissent des égalités entre certains types de partitions avec des conditions de différence et des partitions avec des conditions de congruence. Les preuves combinatoires de ces identités reposent le plus souvent sur l'utilisation de récurrences et d'équations aux $q$-différences.
Dans cet exposé, je présenterai une nouvelle méthode pour résoudre certaines équations aux $q$-différences qui permet de prouver plusieurs identités du type Rogers-Ramanujan généralisant le théorème de Schur (le nombre de partitions de $n$ en parts distinctes congrues à 1 ou 2 modulo 3 est égal au nombre de partitions de $n$ telles qu'il y a une différence d'au moins 3 entre deux parts consécutives et telles que deux multiples de 3 consécutifs ne peuvent être des parts).
• 2016-04-25: 14:00 (room: “Grace Hopper”): Mioara Joldeş (LAAS-CNRS), Validated linear impulsive spacecraft rendezvous.
The rendezvous (RdV) problem consists in designing a plan of maneuvers which takes one active spacecraft, originally moving on an initial orbit, to the final reference orbit of a passive target spacecraft (e.g. International Space Station). Since the '60s many ideas were developed, and today, we are interested in successful RdV which minimizes fuel consumption, with increased autonomy (no human operator). This implies that validation of computations and solutions is at stake. In this talk we discuss the fixed-time minimum-fuel rendezvous between close elliptic orbits, assuming a linear impulsive setting and a Keplerian relative motion.
Firstly, the optimal velocity increments and impulses locations are numerically obtained with a new iterative algorithm with proven convergence. This is based on discretizing a semi-infinite convex optimization problem. It is also shown that this problem has an analytical solution for the out-of-plane RdV.
Secondly, the obtained numerical solutions are validated by propagating the trajectories solutions of the linear differential equations of the dynamics. These are computed as truncated Chebyshev series together with rigorously computed error bounds. Different realistic numerical examples illustrate these results.
This is joint work with D. Arzelier, F. Bréhard, C. Louembet, A. Rondepierre, R. Serra.
• 2016-04-11: 10:30 (room: “Grace Hopper”): Svyatoslav Covanov (INRIA), Multiplication rapide d'entiers utilisant des nombres généralisés de Fermat premiers, slides.
Pendant plus de 35 ans, la meilleure complexité connue pour multiplier des entiers était donnée par l'algorithme de Schönhage-Strassen : la complexité était alors en $O(n \cdot \log n \cdot \log \log n)$ pour multiplier des entiers de $n$ bits. Cependant, dès 1989, Fürer a effectué une première tentative pour battre cette complexité en employant des nombres premiers de Fermat. Il obtenait alors une complexité en $O(n \cdot \log n \cdot K^{\log^* n})$ sous l'hypothèse de l'existence d'une infinité de nombres premiers de Fermat. En 2007, il arrive à une complexité ayant la même forme mais en utilisant un anneau de polynômes et donc en s'affranchissant de l'aspect conjectural. Plus récemment, Harvey, van der Hoeven, et Lecerf ont amélioré le facteur $K$ : ils obtiennent $K = 8$ sans utiliser de conjecture et $K = 4$ en effectuant une hypothèse sur la répartition des nombres premiers de Mersenne. Cette présentation traitera d'un algorithme employant des nombres généralisés de Fermat premiers. Cet algorithme semble plus simple que celui basé sur les nombres de Mersenne et peut être vu comme un correctif à l'approche de Fürer de 1989.
• 2016-04-11: 14:00 (room: “Grace Hopper”): Emilio Jesús Gallego Arias (Mines ParisTech, PSL Research University), Experiments in certified digital audio processing, slides.
We will present recent developments in Wagner, a functional programming language geared towards real-time digital audio processing with formal, machine-checkable semantics.
The current system has three components:
1. A Coq library with some facts about the Discrete Fourier Transform and unitary transforms. The formalization is constructive and heavily relies on the Mathematical Components library.
2. A stream-oriented lambda calculus allowing the access to the previous values of variables. This language admits a coeffect based type-system for history tracking, and enables easy coding of filters and digital waveguide oscillators.
We embed the language in Coq using step indexing, crucially allowing a lightweight mechanization style as we can reuse most of MathComp's linear algebra libraries.
We showcase the verification of our examples and the use of state-space representations in this framework.
3. A call-by-value abstract machine provides the efficient execution model. Programs and buffers are typed for this machine using ideas from the focusing literature distinguishing “positive” and “negative” types. We finally embed the machine in Coq using the standard monadic CBV translation.
• 2016-03-14: 10:30 (room: “Grace Hopper”): Pierre Boutry (Université de Strasbourg), On the formalization of foundations of Tarski's system of geometry, slides.
In 1948, Alfred Tarski established the decidability of the full first-order theory of any instance of Tarski's system of geometry. One part of his proof is based on the introduction of a one-to-one correspondence between the points of Tarski's system of geometry and the points of cartesian spaces over real closed field and algebraic characterizations of the predicates of the theory in terms of the coordinates of the involved points. This was systematically verified by Szmielew and Schwabhäuser in their 1983 book Metamathematische Methoden in der Geometrie. In this talk, we will present the formalization of this book as well as additional results obtained along the mechanization process.
We will start by describing Tarski's system of geometry. We will then focus on some results on the parallel postulates, including some independence properties along with a new classification of these postulates. Finally, we will report on the formalization of the culminating result of this book: the arithmetization of geometry which allows to produce proofs by algebraic computation.
• 2016-03-14: 14:00 (room: “Grace Hopper”): Suzy Maddah (INRIA), Algorithms for singularly-perturbed linear differential systems.
In this talk, we discuss a general class of singularly-perturbed linear differential systems. The first study of such systems dates back to the work of the astronomer Carlini in the year 1817. Since then, they have occurred in a myriad of problems within diverse disciplines including astronomy, hydraulics, and quantum physics. They can manifest a behaviour far more complicated than that of their unperturbed counterparts due to the phenomenon of turning points. We address this phenomenon and we give algorithms to treat such systems locally. The talk is based on a joint work with Moulay Barkatou.
• 2016-03-01 caution, not a Monday! 10:30 (room: “Grace Hopper”): Xavier Caruso (Université de Rennes 1), Factorisation par les pentes de polynômes de Ore, slides.
Les polynômes de Ore sont une version non commutative des polynômes usuels qui interviennent en algèbre semi-linéaire ou dans la théorie des équations différentielles linéaires. Notamment, leurs propriétés de factorisation sont étroitement liés à des théorèmes de structure portant sur les opérateurs semi-linéaires ainsi que sur les modules à connexion.
Dans cet exposé, je m'intéresserai aux polynômes de Ore définis sur des corps ultramétriques complets (e.g. ${\mathbb Q}_p$ ou $k((x)))$. Je définirai pour ces polynômes une notion de polygone de Newton puis donnerai un théorème — ainsi qu'un algorithme — de factorisation par les pentes. Je discuterai également rapidement des applications de ce résultat.
• 2016-02-08: 10:30 (room: “Grace Hopper”): Thomas Sibut-Pinote (INRIA), Produits de matrices rapides : de la théorie à la pratique, slides.
La complexité optimale du produit matriciel, opération élémentaire fondamentale du calcul formel, est une question cruciale pour des raisons tant pratiques que théoriques. Pourtant, elle reste à ce jour un problème ouvert. Strassen ('69) fut le premier à introduire un algorithme sous-cubique, qui motiva l'introduction de la constante ${\omega}$, exposant de faisabilité du produit de matrices. De nombreux travaux donnent des bornes supérieures sur $\omega$, la meilleure étant actuellement celle de Le Gall ('14) : $\omega < 2.3728639$. Les algorithmes correspondants ne sont pas considérés comme utilisables en pratique : rarement implémentés, ils ne sont parfois pas complètement explicités, voire proviennent d'un argument d'existence non effectif.
Notre contribution dans ce travail est de deux natures :
• en manipulant certaines familles d'algorithmes de produits de matrices proposées par Pan ('84) et en utilisant de manière effective le $\tau$-théorème de Schönhage ('74), nous avons découvert un moyen de produire des algorithmes plus effectifs, dans le sens où leur complexité n'est pas seulement asymptotique ;
• cela nous a mené à développer une bibliothèque logicielle en Ocaml pour effectuer ces manipulations et les exporter comme des programmes (C++ ou Maple par exemple).
• 2016-02-01: 10:30 (room: “Grace Hopper”): Tillmann Weisser (LAAS-CNRS, Toulouse), NLverify: Non linear verification, a Coq tactic, slides.
Within the last decade the computer science community's attention has been drawn to automatically proving non-linear inequalities within a proof assistant. The driving project for this development was the formal proof of the Kepler Conjecture by Thomas Hales, which was completed in August 2014. Nowadays, automated verification of inequalities finds its applications in software verification and system control. Proving inequalities is equivalent to showing non negativity of an objective function. With NLverify we propose a Coq tactic to attack such goals by using a Sums of Squares (SOS) method. However, in contrast to other SOS approaches, NLverify does not use the SOS certificate as a representation of the objective function but to build a tight interval enclosure. An SOS certificate can be found by using semi-definite programming (SDP) solvers. From the formal point of view, this certificate can be built by any unsafe tools. The interval enclosure however, needs to be build inside Coq. We use the interval library and verified floating points (Flocq) to do this. For the moment, NLverify only solves polynomial goals. Work on semi-algebraic and univariate transcendental functions (tan, cos, ...) is in progress and expected to be implemented soon. (Joint work with Victor Magron and Benjamin Werner.)
• 2016-01-25: 10:30 (room: “Gilles Kahn”): Pierre Lairez (TU Berlin), Représentations des sommes binomiales, slides.
La manipulation algorithmique des suites discrète soulève le problème de leur représentation. Dans l'approche classique de la création télescopique, on représente une suite par des récurrences linéaires qu'elle satisfait. C'est très général mais le suivi des conditions initiales complique beaucoup les choses, surtout en plusieurs variables. Dans le cas des sommes binomiales, il y a des alternatives : représentations intégrales des séries génératrices et représentations mixtes. Nous verrons ce qu'elles permettent de représenter et comment calculer avec.
• 2016-01-06: 10:30 (room: “Gilles Kahn”): Christophe Vignat (Université d'Orsay and Tulane University), Narayana polynomials and random walks in space, slides.
The Narayana numbers and polynomials will be introduced, and their connection with moments of Pearson random walks in space will be described. A generalization of the Narayana polynomials will be given and related to the classical Gegenbauer polynomials: the probabilistic interpretation of a sequence related to the Narayana numbers will be used to prove some results first introduced by M. Lassalle.
• 2016-01-06: 14:00 (room: “Gilles Kahn”): James Wan (Singapore University of Technology and Design), Some recent advances in Ramanujan-type series for $1/\pi$, slides.
Ramanujan discovered truly innovative ways to express the transcendental constant $1/\pi$ as a hypergeometric sum of the form \begin{equation*} \sum_{n=0}^\infty \frac{(s)_n (1/2)_n (1-s)_n}{n!^3} (a + bn)z^n = \frac1\pi , \end{equation*} where $a$, $b$ and $z$ are algebraic (sometimes rational) numbers. Much study has been devoted to such series for a variety of theoretical and even practical reasons; one research direction being to replace the summand with more complicated functions. Typically, proofs of Ramanujan-type series exploit properties of modular forms, and in particular, of complete elliptic integrals. This talk will summarize a few recent advances in this area, and highlight the increasingly larger role played by computer algebra in generating and proving related series. Examples that are not modular in nature will be exhibited, and some open problems will be put forward.
• 2015-11-16: 10:30 (room: “Marcel-Paul Schützenberger”): Clément Pernet (CNRS, INRIA, Université de Lyon), Computing the rank profile matrix, slides.
The row (resp. column) rank profile of a matrix describes the stair case shape of its row (resp. column) echelon form. We propose the definition of a new matrix invariant, the rank profile matrix, summarizing all information on the row and column rank profiles of a matrix of all its leading sub-matrices. We also explore the conditions for a Gaussian elimination algorithm to compute all or part of this invariant, through the corresponding PLUQ decomposition. As a consequence, we first propose a tile recursive Gaussian elimination algorithm that can compute simultaneously the row and column rank profiles of a matrix, as well as those of all of its leading sub-matrices, in the same time as state of the art Gaussian elimination algorithms. We then show how the classical iterative CUP decomposition algorithm can actually be adapted to compute the rank profile matrix. Used, in a Crout variant, as a base-case to the recursive algorithm, it delivers a significant improvement in efficiency. The row (resp. column) echelon form of a matrix are usually computed via various dedicated triangular decompositions. We show here that, from some PLUQ decompositions, it is possible to recover the row and column echelon forms of a matrix and of any of its leading sub-matrices thanks to an elementary post-processing algorithm. Lastly, we will make connections with the recent algorithmic improvements of Storjohann and Yang [ISSAC'14, ISSAC'15] for the computation of the rank profiles of matrices with small ranks, leading to an $\operatorname{\tilde O}(r^\omega+mn)$ algorithm computing the rank profile matrix.
Joint work with Jean-Guillaume Dumas and Ziad Sultan.
• 2015-11-09: 10:30 (room: “Marcel-Paul Schützenberger”): Grégoire Lecerf (CNRS, LIX), De nouveaux algorithmes asymptotiquement rapides pour multiplier des polynômes à coefficients dans un corps fini.
La complexité du produit des polynômes est toujours une question ouverte d'un intérêt pratique majeur pour la plupart des applications de l'algèbre. Nous présenterons les résultats récents obtenus en collaboration avec David Harvey et Joris van der Hoeven, accessibles à http://arxiv.org/abs/1407.3361.
• 2015-10-12: 10:30 (room: “Philippe Flajolet”): Thomas Dreyfus (Université de Lyon 1), Équations de Mahler et transcendance, slides.
Les équations de Mahler sont les équations faisant intervenir l'opérateur $y(z)\mapsto y(z^p)$, où $p$ est un entier. Les séries génératrices de suites automatiques sont notamment solutions de telles équations. Dans cet exposé nous montrerons comment la théorie de Galois à paramètre permet de déterminer si une série formelle solution d'une équation de Mahler est transcendante ou non.
(Travail en commun avec C. Hardouin et J. Roques.)
• 2015-06-15: 14:00 (room: “Grace Hopper”): Alban Quadrat (INRIA), A constructive study of the module structure of rings of partial differential operators, slides.
The purpose of this talk is to develop constructive versions of Stafford's theorems on the module structure of Weyl algebras $A_n(k)$ (i.e., the rings of partial differential operators with polynomial coefficients) over a base field of characteristic 0 [1]. Using the very simplicity of the ring $A_n(k)$, we show how to explicitly compute a unimodular element of a finitely generated left $A_n(k)$-module of rank at least 2. This result is used to constructively decompose any finitely generated left $A_n(k)$-module into a direct sum of a free left $A_n(k)$-module and a left $A_n(k)$-module of rank at most 1. If the latter is torsion-free, then we explicitly show that it is isomorphic to a left ideal of $A_n(k)$ which can be generated by 2 elements. Then, we give an algorithm which reduces the number of generators of a finitely presented left $A_n(k)$-module having a module of relations of rank at least 2 to 2. In particular, any finitely generated torsion left $A_n(k)$-module can always be generated by at most 2 generators and is the image of a projective ideal. Moreover, a non-torsion left $A_n(k)$-module of rank $r$, which is not free, can be generated by $r+1$ elements but no fewer. These results are implemented in the Stafford package [2], and their system-theoretical interpretations are given within an algebraic analysis (D-module) approach [3]. Using a result due to Caro and Levcovitz [4], we show that the above results also hold for the ring of partial differential operators with coefficients in the field of fractions of the ring of formal power series/locally convergent power series, or for the ring of ordinary differential operators with either formal power series or locally convergent power series coefficients. For more details on these results, see [2,5].

[1] J. T. Stafford. Module structure of Weyl algebras. J. London Math. Soc., 18 (1978), 429-442.

[2] A. Quadrat, D. Robertz. Computation of bases of free modules over the Weyl algebras. J. Symbolic Comput., 42 (2007), 1113-1141. Stafford project: http://wwwb.math.rwth-aachen.de/OreModules

[3] J. E. Björk. Rings of Differential Operators. North Holland, 1979.

[4] N. Caro, D. Levcovitz. On a Theorem of Stafford. Cadernos de Mathemática, 11 (2010), 63-70.

[5] A. Quadrat, D. Robertz. A constructive study of the module structure of rings of partial differential operators. Acta Appl. Math., 133 (2014), 187-234.
• 2015-05-11: 10:30 (room: “Grace Hopper”): Wenjie Fang (LIAFA), Constellations : mise en équation, résolution, rationalité, slides.
Dans l'étude des cartes combinatoires, les constellations possèdent une position particulière. Elles sont à la fois un modèle spécial et une généralisation des cartes biparties, et elles sont aussi reliées aux problèmes de factorisation dans le groupe symétrique. Même si les constellations sont bien comprises combinatoirement grâce aux bijections, leur équation fonctionnelle a résisté à toutes les attaques récentes. En genre supérieur, elles sont encore beaucoup moins bien comprises. Dans cet exposé, nous verrons la mise en équation des constellations dans le cas planaire et en genre supérieur, la résolution dans le cas planaire, et la rationalité en genre supérieur pour le cas biparti.
• 2015-05-11: 14:00 (room: “Grace Hopper”): Louis Dumont (INRIA), Efficient algebraic diagonals and walks, slides.
The diagonal of a multivariate power series $F$ is the univariate power series Diag $F$ generated by the diagonal terms of $F$. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where $F$ is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag $F$ is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag $F$. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. Throughout the talk, we use a common problem of counting certain lattice walks to illustrate the capacities and limits of our tools.
• 2015-04-27: 10:30 (room: “Grace Hopper”): Gilles Christol (IMJ), Diagonales de fractions rationnelles, slides.
Malgré leur définition apparemment artificielle, les diagonales de fractions rationnelles forment une classe de fonctions stable par beaucoup d'opérations. Le but de cet exposé est de montrer qu'elles partagent la plupart des propriétés des fonctions algébriques. Ceci nous conduira à une promenade (*) en géométrie algébrique, quelque part entre les conjectures de Weil et la théorie des motifs.

[(*): ne nécessitant donc aucune compétence technique.]
• 2015-04-27: 14:00 (room: “Grace Hopper”): Frédéric Chyzak (Inria), Explicit generating series for small-step walks in the quarter plane, slides.
Lattice walks occur frequently in discrete mathematics, statistical physics, probability theory, or operational research. The algebraic properties of their enumeration generating series vary greatly according to the family of admissible steps chosen to define them: their generating series are sometimes rational, algebraic, or D-finite, or sometimes they possess no apparent equation. This has recently motivated a large classification effort. Interestingly, the equations involved often have degrees, orders, and sizes, making calculations an interesting challenge for computer algebra.

In this talk, we study nearest-neighbours walks on the square lattice, that is, models of walks on the square lattice, defined by a fixed step set that is a subset of the 8 non-zero vectors with coordinates 0 or ±1. We concern ourselves with the counting of walks constrained to remain in the quarter plane, counted by length. In the past, Bousquet-Mélou and Mishna showed only 19 essentially different models of walks possess a non-algebraic D-finite generating series; the linear differential equations have then been guessed by Bostan and Kauers. In this work in progress, we give the first proof that these equations are satisfied by the corresponding generating series. This allows to derive nice formulas for the generating series, expressed in terms of Gauss' hypergeometric series, to decide their algebraicity or transcendence, and to extract asymptotic formulas for the number of walks counted by lengths.

(Joint work with A. Bostan, M. van Hoeij, M. Kauers, and L. Pech.)
• 2015-03-02: 10:30 (room: “Grace Hopper”): Fredrik Johansson (LFANT, INRIA, IMB), Special functions in the Arb library, slides.
We discuss methods used for rigorous evaluation of special functions in Arb, a C library for arbitrary-precision real and complex ball (interval) arithmetic. We have implemented many of the familiar special functions such as erf, gamma, zeta, polylogarithms, generalized exponential integrals, Bessel functions, theta and elliptic functions. In most cases, we support complex values of all inputs as well as computation of power series expansions (high-order derivatives). Our implementations are competitive with existing non-interval high-precision software, and often significantly faster. One highlight is a new algorithm for elementary functions, giving up to an order of magnitude speedup at "medium" precision (approximately 200-2000 bits).
• 2015-03-02: 14:00 (room: “Gilles Kahn”): Florent Hivert (LRI), A formal proof of the Littlewood-Richardson Rule, slides.
A symmetric polynomial is a polynomial in several variables which is invariant under any permutation of those variables. The most important basis of symmetric polynomials is the so-called Schur basis. It has indeed numerous applications ranging from computer algebra to group theory and quantum physics and even possibly complexity theory. The Littlewood-Richardson coefficients are the coefficients of the expansion in the Schur basis of the product of two Schur polynomials. They are non-negative integers and in general, the most efficient way to compute them is to count the number of certain combinatorial objects called L-R tableaux. The algorithm enumerating those objects and counting them is called the Littlewood-Richardson Rule.

The combinatorial object appearing here are some kind of two dimensional arrays filled with numbers called Young tableaux. In algorithmics, those tableaux are used in Schensted's algorithm to compute the longest length of a non-decreassing subsequence of a finite sequence. This algorithm defines a bijection between finite sequences and pairs of tableaux of the same shape. Schützenberger proof of the LR-rule needs a very fine analysis of this algorithms. In particular, a crucial ingredient is a remark due to Knuth that two sequences give the same tableau under Schensted algorithm if they are connected under a specific rewriting rule. As a consequence, the algorithms has a certain associativity property leading to the definition of a monoid called the plactic monoid.

In the talk, I'll try to present my development in Coq/SSReflect of a formal proof of the L-R rule. I'll focus in particular on the algorithmic and combinatorial part. Here are the steps:
• Schensted's algorithms and its specification;
• the Robinson-Schensted is a bijection;
• Green's invariants: given a sequence $w$, the Robinson-Schensted algorithm actually compute the maximum sum of the length of $k$ disjoint non-decreassing subsequences of $w$;
• Knuth relations and the plactic monoid.
• 2015-01-26: 14:00 (room: “Grace Hopper”): Maxime Dénès (Inria Paris-Rocquencourt), Towards verified computer algebra in Coq, slides.
Formal methods have reached a degree of maturity leading to the design of general-purpose proof systems, enabling both to verify the correctness of complex software systems and to formalize advanced mathematics. However, the ease of reasoning on programs is often emphasized more than their efficient execution. The antagonism between these two aspects is particularly significant for computer algebra algorithms, whose correctness usually relies on elaborate mathematical concepts, but whose practical efficiency is an important matter of concern.

I will present an ongoing effort to formalize data structures useful for computer algebra with proofs of correctness, and new technologies for the efficient execution of programs using them.
• 2014-12-08: 10:30 (room: “Grace Hopper”): Fabian Immler (TU München), Formal verification of rigorous ODE solvers, slides.
Ordinary differential equations (ODEs) are ubiquitous when modeling continuous dynamics. Classical numerical methods compute approximations. Here we present an algorithm that computes enclosures of the solution and which is mechanically verified with respect to the formalization of ODEs in Isabelle/HOL. We use the data structure of affine forms to perform the rigorous numerical computations, i.e., to enclose round-off and discretization errors. The algorithm is based on adaptive Runge-Kutta methods. We present optimizations like splitting, intersecting, and reducing reachable sets, which are important for analyzing chaotic systems.

One such chaotic system is given by the Lorenz equations. A long-standing conjecture concerning the existence of a strange attractor for those equations could be confirmed by Warwick Tucker in 1999. His proof relies on rigorous numerical computations and therefore on the correctness of algorithms. We use our verified algorithm to certify (parts of) Warwick Tucker's computer aided proof.
• 2014-12-08: 14:00 (room: “Marcel-Paul Schützenberger”): Guénaël Renault (INRIA, CNRS, LIP6), Algorithme de changement d'ordre de complexité sous-cubique, slides.
L'algorithme classique utilisant des bases de Gröbner pour la résolution d'un système algébrique ayant un nombre fini de solutions (problème PoSSo) consiste en deux étapes. La première calcule une base de Gröbner pour l'ordre DRL du système donné en entrée. La seconde repose sur un algorithme de changement d'ordre pour déduire de la première étape une base de Gröbner pour l'ordre LEX et ainsi une représentation effective des solutions du système.

L'algorithme FGLM utilisé depuis une vingtaine d'année pour la seconde étape a une complexité cubique en le nombre de solutions. Lorsque F5 est utilisé pour la première étape et que la borne de Bézout est atteinte, c'est le changement d'ordre qui domine l'ensemble du calcul.

Dans cet exposé, nous présentons un nouvel algorithme de résolution de PoSSo de type Las Vegas pour lequel le changement d'ordre a une complexité sous-cubique. Plus exactement, la complexité de la seconde étape est polynomiale en le nombre de solutions de degré l'exposant de l'algèbre linéaire (complexité de multiplier deux matrices denses). C'est alors la complexité de F5 qui domine l'ensemble de la résolution. Si le temps le permet, nous présenterons une version déterministe de cet algorithme et conservant la même complexité.

Travail en collaboration avec Jean-Charles Faugère, Pierrick Gaudry et Louise Huot.
• 2014-12-01: 10:30 (room: “Grace Hopper”): Marc Mezzarobba (CNRS, LIP6), Calcul de facteurs d'ordre 1 d'opérateurs différentiels et de récurrence par évaluation numérique, slides.
Cet exposé présentera un nouvel algorithme pour calculer les solutions hyperexponentielles, ou, de façon équivalente, les facteurs droits d'ordre 1, d'opérateurs différentiels linéaires à coefficients polynomiaux. L'idée est d'interpréter les solutions formelles aux singularités comme des fonctions analytiques que l'on évalue ensuite en un même point. Cela fournit une méthode de recombinaison de ces solutions qui évite le pire cas exponentiel des méthodes existantes. Il s'agit d'un travail en commun avec Fredrik Johansson et Manuel Kauers. J'évoquerai aussi un travail en cours avec Manuel Kauers sur l'intrigante question d'étendre cette idée au cas des opérateurs de récurrence, pour lesquels la notion de solution locale n'est pas aussi claire …
• 2014-10-20: 14:00 (room: “Grace Hopper”): Noam Zeilberger (MSR-INRIA), A link between lambda calculus and maps, part II, slides.
The pure lambda calculus is a universal programming language based entirely on two primitive operations: function application and function abstraction. Within this language sit various relatively well-studied fragments, including the simply-typed terms (which correspond to proofs in intuitionistic propositional logic), the (beta-)normal terms (which are fully evaluated), and the linear terms (wherein every variable is used exactly once, either as a function or as an argument). In the talk, I will report on a surprising connection (originally discovered through the OEIS, and which Alain Giorgetti and I described in the recent paper A correspondence between rooted planar maps and normal planar lambda terms) between a simple fragment of the lambda calculus and so-called rooted planar maps. The talk will begin with a basic review of lambda calculus, including a graphical representation of linear lambda terms by standard string diagram techniques. Then I will describe how to enumerate the normal planar lambda terms and how this recovers OEIS sequence A000168, which counts rooted planar maps by number of edges. Finally, I will recall Tutte's analysis of rooted planar maps (On the enumeration of planar maps, Bulletin of the AMS, 74:64-74, 1968) and explain how an analogous decomposition may be performed on normal planar lambda terms to establish a bijection.
• 2014-10-06: 10:30 (room: “Grace Hopper”): Ali Eshragh (University of Newcastle, Australia), Computational complexity of the Fisher information, slides.
In this presentation, we deliver our theoretical and numerical results on the Fisher Information for the birth rate of a partially-observable simple birth process involving $n$ observations. Our goal is to estimate the rate of growth, λ, of a population governed by a simple birth process. We may choose $n$ time points at which to count the number of individuals present, but due to detection difficulties, or constraints on resources, we are able only to observe each individual independently with fixed probability $p$. We discuss the optimal times at which to make our $n$ observations in order to maximise the Fisher Information for the birth rate λ. Finding an analytical form of the Fisher Information in general appears intractable. Nonetheless, we find a very good approximation for the Fisher Information by exploiting the probabilistic properties of the underlying stochastic process. Both numerical and theoretical results strongly support the latter approximation and confirm its high level of accuracy.
• 2014-09-29: 10:30 (room: “Grace Hopper”): Thomas Sibut-Pinote (INRIA Saclay), Towards a formal certification of approximations of solutions of ODEs in Coq.
Approximating solutions of ODEs numerically is a vital part of the work of both the engineer and the mathematician. Methods in use have a variable level of rigor, which can be problematic when we want high confidence in the result. In this talk, we present the first steps towards a full certification of approximations in the Coq theorem prover using interval arithmetic and building on some recent Coq libraries allowing for efficient manipulation of floats and intervals.
• 2014-09-29: 14:00 (room: “Grace Hopper”): Noam Zeilberger (MSR-INRIA), A link between lambda calculus and maps, part I, slides.
The pure lambda calculus is a universal programming language based entirely on two primitive operations: function application and function abstraction. Within this language sit various relatively well-studied fragments, including the simply-typed terms (which correspond to proofs in intuitionistic propositional logic), the (beta-)normal terms (which are fully evaluated), and the linear terms (wherein every variable is used exactly once, either as a function or as an argument). In the talk, I will report on a surprising connection (originally discovered through the OEIS, and which Alain Giorgetti and I described in the recent paper A correspondence between rooted planar maps and normal planar lambda terms) between a simple fragment of the lambda calculus and so-called rooted planar maps. The talk will begin with a basic review of lambda calculus, including a graphical representation of linear lambda terms by standard string diagram techniques. Then I will describe how to enumerate the normal planar lambda terms and how this recovers OEIS sequence A000168, which counts rooted planar maps by number of edges. Finally, I will recall Tutte's analysis of rooted planar maps (On the enumeration of planar maps, Bulletin of the AMS, 74:64-74, 1968) and explain how an analogous decomposition may be performed on normal planar lambda terms to establish a bijection.
• 2014-07-07: 10:30 (room: “Grace Hopper”): Sébastien Maulat (ENS, Lyon), Des fractions continues pour les fonctions spéciales : une approche « deviner pour prouver », slides and a demo.
Les fractions continues sont étudiées depuis l'époque d'Euler pour leurs remarquables propriétés de convergence. Si ces objets paraissent plus complexes à manipuler que les développements de Taylor, leur forme rationnelle permet notamment d'épouser les singularités des fonctions d'une variable complexe. Si de nombreuses formules de développements (infinis) en fractions continues sont connues, leurs preuves sont souvent indirectes et créatives. On s'intéresse ici à deviner puis prouver automatiquement ces formules, dans le cadre holonome — des fonctions satisfaisant une équation différentielle linéaire à coefficients polynomiaux. En cours de route, la démarche de mathématique expérimentale « deviner pour prouver » vient permettre des preuves directes, et accélérer les calculs.
• 2014-07-07: 14:00 (room: “Grace Hopper”): Pierre Lairez (Inria), Représentation intégrales des sommes binomiales.
De nombreuses suites combinatoires admettent des représentations sous forme d'intégrale multiple et paramétrée de fraction rationnelle. Ces suites peuvent être manipulées par leur représentation intégrale, permettant ainsi de prouver des identités, de calculer des récurrences, des asymptotiques, etc. La méthode procède en deux temps. Premièrement, il s'agit de trouver cette représentation intégrale. Deuxièmement, il faut calculer une équation différentielle satisfaite par l'intégrale. C'est l'objet d'un nouvel algorithme que j'expliquerai brièvement.
• 2014-05-12: 10:30 (room: “Marcel-Paul Schützenberger”): Suzy S. Maddah (XLIM-DMI, University of Limoges), On the formal reduction of singularly-perturbed linear differential systems.
Singularly-perturbed linear differential systems have countless applications which are traced back to the year 1817 and their study encompasses a vast body of literature (see, e.g. Chen (1990), Wasow (1985), and references therein). However, their symbolic resolution is still open to investigation. The methods proposed in the literature either exclude their turning points or are not algorithmic throughout. Moreover, they make an essential use of the so-called Arnold-Wasow form. On the other hand, for their unperturbed counterparts, the research advanced profoundly in the last two decades making use of methods of modern algebra. The classical approach is substituted by efficient algorithms (see, e.g., ISOLDE). Wasow hoped, in his treatise summing up contemporary research directions and results on perturbed systems, that techniques developed for unperturbed systems be generalized to tackle the problems of the former. This generalization is the interest of this talk.
• 2014-04-28: 10:30 (room: “Grace Hopper”): Guillaume Cano (Marelle, INRIA Sophia Antipolis Méditerranée), Sur la formalisation du théorème de Perron-Frobenius.
C'est en voulant formaliser des algorithmes utilisés en robotique que l'on a été amené à s'intéresser au théorème de Perron-Frobenius. Ce théorème porte sur les propriétés du rayon spectral d'une matrice dont les coefficients sont positifs ou nuls. La preuve de ce théorème fait intervenir des résultats d'algèbre linéaire comme la forme normale de Jordan d'une matrice, mais aussi des résultats de topologie générale comme la notion de convergence d'une suite ou le théorème de Bolzano-Weierstrass. La définition de la forme normale de Jordan fait intervenir la notion de matrices diagonales par blocs que nous verrons donc dans une première partie. Nous verrons ensuite comment sont définies les structures topologiques, ainsi que certains résultats sur ces structures comme par exemple le théorème de Bolzano-Weierstrass, et nous verrons enfin comment nous réutilisons ce travail dans la formalisation du théorème de Perron-Frobenius.
• 2014-04-15: 10:30 (room: “Grace Hopper”): Jules Svartz (PolSys, INRIA/Univ. Paris 6), Résolution de systèmes zéro-dimensionnels avec symétries, slides.
La résolution de systèmes polynomiaux présentant des symétries est un problème naturel qui apparaît dans plusieurs contextes applicatifs (cryptographie, robotique, biologie, physique, codes correcteurs d'erreurs, ...) Les algorithmes usuels de calcul de bases de Gröbner détruisent en général ces symétries. Dans cet exposé, je présenterai les avancées sur ce sujet obtenues lors de ma thèse sous la direction de Jean-Charles Faugère. Dans l'étude générale d'un système polynomial présentant des symétries, le cadre algébrique sous-jacent est celui d'un idéal globalement invariant sous l'action d'un groupe.
1. Si ce groupe est le groupe symétrique, on peut se ramener par différences divisées à un système d'équations individuellement invariantes sous l'action du groupe symétrique, et reformuler le système à l'aide des fonctions symétriques élémentaires. Je montrerai comment appliquer cette approche à un problème de physique des fluides.
2. Cette reformulation en fonction d'invariants est possible dès que le système est d'équations individuellement invariantes sous l'action du groupe. Cette approche est classique en théorie des invariants, mais n'est vraiment efficace qu'avec des groupes ayant peu d'invariants fondamentaux. Dans le cas contraire, une approche par base SAGBI a été proposée en 2009 par Jean-Charles Faugère et Sajjad Rahmany pour les sous-groupes du groupe des permutations. J'expliquerai comment étendre cette approche à d'autres groupes et donnerai une estimation du gain en complexité.
3. Enfin, si le groupe est abélien, le groupe induit une structure additionnelle sur l'algèbre des polynômes, qu'il est possible d'exploiter pour donner des variantes des algorithmes de résolution classiques que sont F5 et FGLM faisant intervenir des matrices de taille réduite d'un facteur correspondant au cardinal du groupe.
• 2014-04-14: 14:30 (PCRI, bâtiment 650, salle 435, Université Paris-Sud, rue Noetzlin 91190, Gif-sur-Yvette): Frédéric Chyzak (INRIA, Saclay), Habilitation defense (HDR): L'ABC du télescopage créatif — Algorithmes, bornes, complexité, slides.
Le télescopage créatif est un principe algorithmique développé depuis les années 1990 en combinatoire et en calcul formel, notamment depuis les travaux de Doron Zeilberger, pour calculer avec des sommes et intégrales paramétrées, que ce soit pour trouver des formes explicites ou pour justifier des identités intégrales ou sommatoires. Le procédé est particulièrement adapté à une grande famille de fonctions et suites données par des équations linéaires différentielles et de récurrences, que ce soient des fonctions spéciales de l'analyse, des suites de la combinatoire, ou des familles de polynômes orthogonaux.

Dans cet exposé, je retracerai l'évolution des algorithmes et de mes contributions pour adapter le procédé à des classes de fonctions de plus en plus générales, du cadre initial des suites hypergéométriques, données par des récurrences d'ordre 1, aux cas de fonctions données par des équations d'ordre supérieur, ceci jusqu'aux fonctions données par des idéaux non zéro-dimensionnels.

La difficulté d'obtenir des implantations rapides dans tous ces cas repose sur le calcul d'un certificat justifiant l'application du télescopage créatif, ce certificat étant par nature de grande taille. Ceci m'a motivé dans l'étude de la complexité du procédé. Plusieurs pistes d'amélioration ont été explorées, d'abord en essayant de maintenir compact ce certificat, puis en obtenant des algorithmes validés sans passer par son calcul. Comme souvent, l'estimation des tailles arithmétiques des objets intervenant dans le telescopage créatif a à la fois guidé le développement de nouveaux algorithmes plus efficaces et permis leur estimation théorique de complexité. Pour finir, j'indiquerai brièvement la direction qu'a prise mes travaux récents sur le sujet, vers la preuve formelle, et qui font ressortir des pistes pour une meilleure justification de l'application du télescopage créatif.
• 2014-03-24: 10:30 (room: “Marcel-Paul Schützenberger”): Tristan Vaccon (IRMAR, Rennes), $p$-adic precision, differentials and the example of Gröbner bases, slides.
The last two decades have seen the rise of $p$-adic methods, either to solve problems over rationals, over finite fields, or even of purely $p$-adic nature. Yet, $p$-adic numbers can only be handled with finite precision, which yields the problems of determining the smallest precision needed or the loss of precision per operation. With X. Caruso and D. Roe, we provide a new method to handle precision over $p$-adics that relies on differentials. We shall compare this method with the classical "step-by-step" analysis over the special example of Gröbner bases computation.
• 2014-03-03: 10:30 (room: “Marcel-Paul Schützenberger”): Pierre-Jean Spaenlehauer (CARAMEL, LORIA), A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation, slides.
Given an linear/affine space of matrices E with real entries, a data matrix U in E and a target rank r, the Structured Low-Rank Approximation Problem consists in computing a matrix M in E which is close to U (with respect to the Frobenius norm) and has rank at most r. This problem appears with different flavors in a wide range of applications in Engineering Sciences and symbolic/numeric computations. We propose an SVD-based numerical iterative method which converges locally towards such a matrix M. This iteration combines features of the alternating projections algorithm and of Newton's method, leading to a proven local quadratic rate of convergence under mild transversality assumptions. We also present experimental results which indicate that, for some range of parameters, this general algorithm is competitive with numerical methods for approximate univariate GCDs and low-rank matrix completion (which are instances of Structured Low-Rank Approximation). In a second part of the talk, we focus on the algebraic structure and on exact methods to compute symbolically the nearest structured low-rank matrix M to a given matrix U in E with rational entries. We propose several ways to compute the algebraic degree of the problem and to recast it as a system of polynomial equations in order to solve it with algebraic methods. The first part of the talk is a joint work with Eric Schost, the second part is a joint work with Giorgio Ottaviani and Bernd Sturmfels.
• 2013-12-08: 10:30 (room: “Grace Hopper”): François Ollivier (Max, LIX), Endogène = exogène : une version faible du théorème de Lüroth différentiel.
Nous achèverons d'abord l'exposé des principaux critères de platitude selon (Cartan 1913), (Charlet et al. 1989), etc, illustrés par quelques exemples concrets. Ainsi, ceux qui n'étaient pas là à l'exposé précédent auront une chance de rattrapper l'essentiel pour la suite.

Le théorème de Lüroth (1876) affirme que si une courbe algébrique admet un paramétrage rationnel, alors il existe un paramétrage qui ne passe qu'une seule fois en un point générique. Une généralisation au cas des courbes a été donnée par Castelnuovo en 1894 pour un corps algébriquement clos. Mais il n'existe plus d'analogue en dimension 3.

Ritt a donné en 1932 un analogue du théorème de Lüroth pour des extensions de corps différentiels. Mais il n'existe pas d'analogue différentiel en dimension différentielle 2 (FO 1998). En revanche, en dimension 1, ces deux résultats (algébrique et différentiel) admettent une version étendue : si $K/k$ est une extension de corps (différentiel ordinaire) de dimension (différentielle) 1 et $K$ est inclus dans une extension (différentiellement) transcendante pure, alors $K$ est une extension différentiellement transcendante pure (Gordan 1887, FO et Sadik 2013 en différentiel).

En définissant une extension plate comme une extension différentielle $K/k$ telle que la clôture algébrique de $K$ est isomorphe à la clôture algébrique d'une extension différentiellement transcendante pure de $k$, le théorème « endogène = exogène » s'énonce comme suit : Si $K/k$ est plate et $K_2$ est une extension de $k$ contenue dans $K$, alors $K_2/k$ est plate.

Nous donnerons les grandes lignes d'une démonstration obtenue en collaboration avec Brahim Sadik.
• 2013-11-25: 10:30 (room: “Grace Hopper”): François Ollivier (Max, LIX), Systèmes plats : du problème de Monge à l'automatique non linéaire.
La notion de système plat (Fliess, Lévine, Martin, Rouchon 1991) s'est imposée comme un outil efficace pour résoudre les problèmes de planification de trajectoire en automatique non linéaire. Un système différentiel ordinaire $P_i(x, x', t) = 0$ est plat si
1. ses solutions peuvent être paramétrées par la donnée de fonctions arbitraires $z_k(t)$, dites sorties linéarisantes : $x_j = X_j(z, z', \dots, z^{(r)})$ ;
2. les $z_k$ sont elles-mêmes exprimables en fonction des $x_j$ et de leurs dérivées.
Monge fut en 1784 le premier qui ait considéré de tels systèmes, mais sans imposer la seconde condition, introduite par Hilbert en 1912.

Au cours de l'exposé, nous donneront un aperçu des principaux critères de platitude : Cartan 1913, Charlet et al. 1989, etc. illustrés par quelques exemples concrets (grues, camions à remorques, ...) On abordera aussi les deux principaux formalismes permettant d'aborder cette notion : théorie des diffiétés et algèbre différentielle.

On ne sait toujours pas décider dans le cas général si un système est paramétrable au sens de Monge, ni s'il est plat. L'équivalence de ces deux notions, est une conjecture appelée en automatique « endogène = exogène », qui fera l'objet de l'exposé suivant.
• 2013-10-28: 14:00 (room: “Grace Hopper”): Bruno Grenet (Max, LIX), Autour des polynômes de type creux, slides.
Dans ce troisième exposé, il sera question de polynômes de type creux. La représentation lacunaire (ou supercreuse) d'un polynôme consiste à ne représenter que ses monômes non nuls : un aspect important est que les paramètres de taille seront alors le nombre de monômes, la taille des coefficients et le logarithme du degré (et non plus le degré comme dans la représentation la plus classique).

J'aborderais deux thèmes dans mon exposé : le premier thème est plutôt mathématique. Il sera question de borner le nombre de racines réelles de polynômes de type creux, à savoir des sommes de produits de polynômes lacunaires. On parlera aussi du nombre de leurs racines p-adiques ou du nombre de segment dans leur polygone de Newton, et on verra les liens qu'entretiennent ces questions avec la question « VP = VNP ? ». Le deuxième thème sera la factorisation de polynômes lacunaires. On verra ce qu'il est possible et ce qu'il n'est pas possible de faire dans ce cadre, et je présenterai un nouvelle méthode qui simplifie les algorithmes connus pour ce problème.
• 2013-10-07: 14:00 (room: “Grace Hopper”): Bruno Grenet (Max, LIX), Représentations déterminantielles de polynômes, slides.
Une représentation déterminantielle d'un polynôme $p$ sur un corps $k$ est une matrice $M$ dont chaque coefficient est soit une variable soit un élément de $k$, et telle que $\det(M)=P$. Les représentations déterminantielles sont un objet central en complexité algébrique pour l'étude de la complexité relative de certaines familles de polynômes par rapport au déterminant (ou de manière équivalente pour l'étude de la complexité du déterminant). Mon exposé présentera différents résultats concernant ces représentations déterminantielles, en lien avec la théorie de la complexité à la Valiant. Il sera en particulier question de représentations déterminantielles minimales pour le permanent (et de la version algébrique de la question « P = NP ? »), d'algorithmes sans division pour le déterminant, mais aussi de représentations déterminantielles symétriques que j'ai plus spécifiquement étudiées dans ma thèse.
• 2013-09-19: 14:00 (room: “Gilles Kahn”): Bruno Grenet (Max, LIX), Complexité du résultant, slides.
On considère un système polynomial homogène sur un corps $k$. S'il possède autant de polynômes que de variables, on peut définir son résultant qui est un polynôme en les coefficients du système qui est identiquement nul si et seulement si le système admet une racine dans la clôture algébrique de $k$. On s'intéresse ici à la complexité du calcul de ce résultant, dans le pire cas. Dans mon exposé je présenterai différents résultats, certains classiques et d'autres obtenus pendant ma thèse, montrant que le résultant est NP-difficile à calculer, en toute caractéristique. Je parlerai également des bornes supérieures connues pour ce problème, très différentes selon que la caractéristique de $k$ est nulle ou non.
• 2013-05-30: 14:00 (room: “Grace Hopper”): Xavier Caruso (CNRS, IRMAR), Quelques algorithmes pour les polynômes tordus sur les corps finis, slides.
Dans cet exposé, je présenterai un certain nombre d'algorithmes pour la manipulation des polynômes tordus sur les corps finis. Cela inclut :
1. des algorithmes de multiplication et de division rapide (de type Karatsuba ou FFT),
2. un algorithme de factorisation qui améliore en plusieurs points l'algorithme classique de Giesbrecht (ainsi que, si le temps le permet, quelques variantes résolvant des questions annexes).
Je montrerai également une implémentation de ces algorithmes en Sage.
• 2013-02-21: 14:00: Marc Mezzarobba (INRIA [AriC], LIP, ENS de Lyon), Évaluation de Ai(x) : cancellation catastrophique et comment y échapper, slides.
Le développement de Taylor à l'origine de la fonction d'Airy $Ai$ converge sur tout le plan complexe, mais sa sommation numérique pour $x>0$ est un problème extrêmement mal conditionné. En effet, les coefficients non nuls sont de signe alterné et se compensent presque, de sorte que, lorsque l'on calcule la somme à précision finie pour $x$ modérément grand, toute l'information significative est perdue dans les erreurs d'arrondi. Ce phénomène appelé cancellation catastrophique est fréquent dans l'évaluation des développements de Taylor de fonctions entières usuelles.

Dans cet exposé, je présenterai une méthode due à Gawronski, Müller et Reinhard [1, 2] qui, à partir d'une étude asymptotique d'une série entière $y(z)$, aide à trouver deux fonctions auxiliaires $F$ et $G$ bien conditionnées vis-à-vis de la sommation et telles que $y(z)=G(z)/F(z)$. Je montrerai comment une petite extension de cette méthode la rend applicable au cas de $Ai$. J'expliquerai ensuite comment l'on construit à partir de la formule obtenue un algorithme garanti d'évaluation en virgule flottante à précision arbitraire dans lequel la précision de travail reste toujours du même ordre de grandeur que la précision cible. L'algorithme fait appel à la méthode de récurrence arrière de Miller pour le calcul des coefficients de la série $G(z)$, et son analyse (pour borner les erreurs commises) fait appel notamment à l'encadrement des coefficients de $G(z)$ par la méthode du col.

Il s'agit d'un travail en commun avec Sylvain Chevillard (APICS, Inria).

Références :

[1] W. Gawronski, J. Müller, and M. Reinhard, Reduced cancellation in the evaluation of entire functions and applications to the error function, SIAM Journal on Numerical Analysis 45 (2007), no. 6, 2564– 2576.

[2] M. Reinhard, Reduced cancellation in the evaluation of entire functions and applications to certain special functions, Ph.D. thesis, Universität Trier, 2008.

[3] S. Chevillard and Marc Mezzarobba, Multiple-precision evaluation of the Airy Ai function with reduced cancellation, 21st IEEE Symposium on Computer Arithmetic, Austin, TX, US, 2013 (to appear).
• 2013-02-21: 15:30: Élie de Panafieu (LIAFA), Complexity estimates for two uncoupling algorithms, slides.
Uncoupling is the transformation of a differential system Y' = M Y into one or several differential equations. We present three classical uncoupling algorithms: the cyclic vector method, the Danilevski-Barkatou-Zürcher algorithm and the Abramov-Zima algorithm. The naive complexity analysis of those last two algorithms produces exponential bounds, far from the experimental observations. To improve those, we switch to an algebraic analysis of the matrices computed. It reveals a common core, from which a precise complexity analysis for generic input is derived. Another contribution is the conception of a fast algorithm for the cyclic vector method, together with a magma implementation and benchmarks.
• 2012-11-22, 10:00: Stephen Melczer (SFU, Vancouver, Canada), Classifying restricted lattice walks, slides.
The enumeration of lattice walks in restricted regions is an elegant problem which has been the subject of much attention. In this talk we survey recent results on lattice walks in the quarter plane, regarding the analytic properties of their generating functions. Specifically, we discuss the classification of walks whose generating functions satisfy linear differential equations, and why this property is desirable.
• 2012-11-08, 14:00: Carsten Schneider (RISC, Johannes Kepler Universität, Linz), Multi-summation in refined difference fields, slides.
M. Karr (1981) developed a difference field algorithm for summation in finite terms. In this talk we present a refined difference field theory that gives rise to improved difference field algorithms for the summation paradigms of telescoping, creative telescoping and recurrence solving. Applying these techniques recursively, one can hunt for simplifications of multi-sums to expressions in terms of indefinite nested sums and products with minimal nesting depth. We will demonstrate the underlying algorithms by concrete examples from number theory and Quantum Field Theory, e.g., the evaluation of 3-loop Feynman integrals in terms of harmonic sums and multiple zeta values. Special emphasis will be put on the verification of such identities.