# Seminars at SpecFun

Starting in 2021, our seminar is a Joint PolSysSpecFun Seminar. It will be run online. To get the proper links, subscribe to the announcements (just click and fill the form). (We will announce to the lists PolSys, SpecFun, and GT Calcul Formel.)

Since September 2021, the organizers are Jérémy Berthomieu, Pierre Lairez, and Rémi Prébet.

Until September 2021, the organizers were Alin Bostan, Frédéric Chyzak, Huu Phuoc Le, and Mohab Safey El Din.

From 2012 to 2020, we ran a former seminar, “Computations and Proofs”.

## Talks to come:

• 2021-10-15: 11:00: Antonio Jiménez-Pastor (École polytechnique, LIX), C2-finite sequences.
Holonomic sequences are widely studied as many objects interesting to mathematicians and computer scientists are in this class. In the univariate case, these are the sequences satisfying linear recurrences with polynomial coefficients and also referred to as P-finite sequences. A subclass are C-finite sequences satisfying a linear recurrence with constant coefficients. We'll see in this talk a natural extension of this set of sequences: which satisfy linear recurrence equations with coefficients that are C-finite sequences. We will show that C2-finite sequences form a difference ring and provide methods to compute in this ring.
In-person
at Inria Saclay Île-de-France, bâtiment Turing, amphithéâtre Sophie-Germain
Remotely
on Zoom (link in the announcement email, or contact the organizers)

## Past talks:

• 2021-09-24: 11:00: Georgy Scholten (Sorbonne Univ., LIP6), Truncated Moment Cone and Connections to the Coalescence Manifold.
We study the univariate moment problem of piecewise-constant density functions on the interval $[0, 1]$ and its consequences for an inference problem in population genetics. We show that, up to closure, any collection of n moments is achieved by a step function with at most $n-1$ breakpoints and that this bound is tight. We use this to show that any point in the $n$-th coalescence manifold in population genetics can be attained by a piecewise constant population history with at most $n-2$ changes. We give a semi-algebraic description of the n-th coalescence manifold as a projected spectrahedron.
• 2021-06-18: 11:00: Bruno Salvy (Inria, LIP, ENS-Lyon), Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems, slides.
The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables. This is joint work with Stephen Melczer.
• 2021-05-21: 11:00: Didier Henrion (LAAS-CNRS Toulouse and Czech Tech. Univ. Prague), Accelerating the moment-SOS hierarchy for volume approximation, slides.
The moment-SOS hierarchy can be used to approximate numerically the volume of a semialgebraic set $X$ at the price of solving increasingly large convex optimization problems. In its original form, the dual SOS problem in the hierarchy consists of approximating from above the indicator function of $X$ with a polynomial of increasing degree, thereby suffering from the Gibbs effect (large overshoots near the discontinuity points). In this talk we explain how to suppress this effect by adding redundant linear constraints in the primal moment problem. These constraints are a consequence of Stokes' theorem. This results in a significant acceleration of the hierarchy. This is joint work with Matteo Tacchi and Jean Bernard Lasserre, see arXiv:2009.12139 or hal:02947268.
• 2021-05-07: 11:00: Pierre Vanhove (CEA, France, and HSE University, Moscow, Russia), Picard-Fuchs equations for Feynman integrals, slides.
In this talk we will present various methods for computing the Picard-Fuchs equations for Feynman integrals that arise in quantum field theory. After reviewing the main properties of Feynman integrals, we will discuss two methods for deriving their ideal of differential equations, a first one using the Gel'fand-Kapranov-Zelevinsky construction and the other one using the creative telescoping. In this talk we will compare the two approaches and give a physical intepretation of the certificate.
This based on some work done in collaboration with Charles Doran and Andrey Novoseltsev.
• 2021-04-09: 16:00: Virginia Vassilevska Williams (MIT, USA), A refined laser method and faster matrix multiplication, slides.
The complexity of matrix multiplication is measured in terms of $\omega$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n^{\omega+\epsilon})$ field operations for all $\epsilon>0$; the best bound until now is $\omega<2.37287$ [Le Gall'14]. All bounds on $\omega$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the “value” of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $\omega$, and we indeed obtain the best bound on $\omega$ to date: $\omega<2.37286$. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity. (Joint work with Josh Alman.)
• 2021-04-02: 11:00: Manfred Buchacher (Johannes Kepler Universität, Linz), Separating variables in bivariate polynomial ideals, slides.
We present an algorithm which for any given ideal $I \subseteq \mathbb{K}[x,y]$ computes $I \cap (\mathbb{K}[x] + \mathbb{K}[y])$. Our motivation for looking at the problem came from enumerative combinatorics in the context of lattice walks: an elimination of this kind appears in Bousquet-Mélou’s proof of the algebraicity of the generating function of Gessel’s walks. The problem also arises when one wants to compute the intersection of two $\mathbb {K}$-algebras. This is joint work with Manuel Kauers and Gleb Pogudin.
• 2021-03-12: 15:00: Bernd Sturmfels (UC Berkerley, USA, and MPI Leipzig, Germany), Linear PDE with constant coefficients, slides.
We discuss algebraic methods for solving systems of homogeneous linear partial differential equations with constant coefficients. The setting is the Fundamental Principle established by Ehrenpreis and Palamodov in the 1960’s. Our approach rests on recent advances in commutative algebra, and it offers new vistas on schemes and coherent sheaves in computational algebraic geometry.
• 2021-02-26: 11:00: Philippe Moustrou (University of Tromsø, Norway), Symmetric situations in polynomial optimization, slides.
In the first part of the talk, we will discuss symmetric polynomial ideals, namely ideals of polynomials closed under permutations of variables. The Specht polynomials are fundamental in the understanding of the representations of the symmetric group. We show a connection between the leading monomials of polynomials in a symmetric ideal and the Specht polynomials contained in the ideal. This provides applications in several contexts, in particular for algorithmic purposes. Most notably, this connection gives information about the points in the corresponding algebraic variety. From another perspective, it restricts the isotypic decomposition of the ideal viewed as a representation of the symmetric group.This allows further algorithmic consequences, in particular for non-negativity certifications of symmetric polynomials on symmetric variety via sums of squares.
Besides sums of squares, alternative methods have been recently introduced to certify the non-negaitivity of polynomials. The second part of the talk will focus on methods based on Sums of Arithmetic-Geometric Exponentials (SAGE) and Sums Of Non-negative Circuit polynomials (SONC) for symmetric polynomials. We will discuss the theoretical aspects such as the comparison between these cones and the cone of non-negative symmetric polynomials, as well as symmetry-reduction techniques for the corresponding algorithms.
Based on joint works with Helen Naumann, Cordian Riener, Thorsten Theobald and Hugues Verdure.
• 2021-02-19: 11:00: Ilaria Zappatore (INRIA Saclay). Simultaneous rational function reconstruction and applications to algebraic coding theory, slides.
The simultaneous rational function reconstruction (SRFR) is the problem of reconstructing a vector of rational functions with the same denominator given its evaluations (or more generally given its remainders modulo different polynomials).
The peculiarity of this problem consists in the fact that the common denominator constraint reduces the number of evaluation points needed to guarantee the existence of a solution, possibly losing the uniqueness.
One of the main contributions presented in this talk consists in the proof that uniqueness is guaranteed for almost all instances of this problem.
This result was obtained by elaborating some other contributions and techniques derived by the applications of SRFR, from the polynomial linear system solving to the decoding of Interleaved Reed-Solomon codes.
In this talk it is also presented another application of the SRFR problem, concerning the problem of constructing fault-tolerant algorithms: algorithms resilients to computational errors.
These algorithms are constructed by introducing redundancy and using error correcting codes tools to detect and possibly correct errors which occur during computations. In this application context, we improve an existing fault-tolerant technique for polynomial linear system solving by interpolation-evaluation, by focusing on the related SRFR.
Contains joint works with Eleonora Guerrini and Romain Lebreton.
• 2021-02-12: 11:00: Thibaut Verron (Johannes Kepler Universität, Linz, Austria), Gröbner bases in Tate algebras, slides.
Tate series are a generalization of polynomials introduced by John Tate in 1962, when defining a $p$-adic analogue of the correspondence between algebraic geometry and analytic geometry. This $p$-adic analogue is called rigid geometry, and Tate series, similar to analytic functions in the complex case, are its fundamental objects. Tate series are defined as multivariate formal power series over a $p$-adic ring or field, with a convergence condition on a closed ball.
Tate series are naturally approximated by multivariate polynomials over $\mathbb{F}_p$ or $\mathbb{Z}/p^n \mathbb{Z}$, and it is possible to define a theory of Gröbner bases for ideals of Tate series, which opens the way towards effective rigid geometry. In this talk, I will present those definitions, as well as different algorithms to compute Gröbner bases for Tate series.
Joint work with Xavier Caruso and Tristan Vaccon.
• 2021-02-04: 14:00: Simon Abelard (LIX, École polytechnique), Structured algorithms for algebraic curves, slides.
In this talk we will discuss two different algorithmic problems related to algebraic curves : counting points and computing Riemann-Roch spaces, both of them having applications in various fields of computer science such as cryptography and coding theory. These tasks are actually closely related to well-known problems from computer algebra.
The first problem mostly boils down to solving polynomial systems. We will see how the underlying structure of these systems helps to derive better complexity bounds and to perform practical computations.
For the second problem, previous algorithms (Khuri-Makdisi in 2007, Le Gluher and Spaenlehauer in 2018) compute Riemann-Roch spaces through the use of linear algebra. The main novelty of our work is to rely on a $K[X]$-module structure instead so that we can replace linear algebra by faster algorithms for computing interpolation bases (such as the one of Neiger in 2016), thus deriving a subquadratic complexity bound. We will also talk about the ongoing implementation of this algorithm.
The first part of the talk contains joint work with P. Gaudry and P.-J. Spaenlehauer, the second part is joint work with A. Couvreur and G. Lecerf.
• 2021-01-22: Rémi Imbach (Courant Institute, New York University, USA), Complex roots clustering.
We are interested in computing clusters of complex roots of polynomials and square polynomials systems. Root clustering differs of root isolation in that it can be performed softly, i.e. avoiding some decisions of zero. This allows clustering algorithms to be robust to multiple roots and to accept inputs given by black boxes for approximation, for instance polynomials which coefficients are in towers of field extensions. The starting point of our talk is the existence of a clustering algorithm for roots of univariate polynomials. We will show how this algorithm can be embedded in an algorithm for computing clusters of roots of triangular systems of polynomials resulting in particular of a symbolic step to process non-triangular systems. We will also present recent practical improvements for the univariate case.