(We also list here our PhD/HDR defenses, even when they don't take place
in our main building.)
- 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:
- 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;
- derandomizing Hermite form computation;
- 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:
-
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.
-
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.
-
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.
- 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.
- 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é.
- 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
- 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)})$ ;
- 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 :
- des algorithmes de multiplication et de division rapide (de type
Karatsuba ou FFT),
- 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.