The joint MATHEXP-Polsys seminar

Since 2021 the Specfun seminar has merged with the Polsys seminar. In 2022, Specfun becomes MATHEXP. The joint seminar is held in Paris or Palaiseau and broadcasted online.

2022

PAST Sums of powers of binomials, their Apéry limits, and Franel's suspicions

speaker
Armin Straub, University of South Alabama (USA)
date
Friday, 1 July 2022 at 11:00
location
Paris, Jussieu, couloir 25-26, salle 105 + online
abstract

Apéry's proof of the irrationality of ζ(3) relies on representing that value as the limit of the quotient of two rational solutions to a three-term recurrence. We review such Apéry limits and explore a particularly simple instance. We then explicitly determine the Apéry limits attached to sums of powers of binomial coefficients. As an application, we prove a weak version of Franel's conjecture on the order of the recurrences for these sequences. This is based on joint work with Wadim Zudilin.

This session is jointly organized with the “Groupe de travail Transcendance et combinatoire”.

PAST Sparse polynomial interpolation and exact division over ℤ

speaker
Armelle Perret du Cray, LIRMM, University of Montpellier (France)
date
Friday, 10 June 2022 at 11:00
location
Paris, Jussieu + online
abstract

We present a new Monte Carlo randomized algorithm to recover an integer polynomial \(f(x)\) given a way to evaluate \(f(a) \mod m\) for any chosen integers \(a\) and \(m\). This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. The best previously known results have at least a cubic dependency on the bit-length of the exponents.

This is a joint work with Pascal Giorgi, Bruno Grenet and Daniel S. Roche.

PAST Validated Numerics and Formal Proof for Computer-Aided Proofs in Mathematics: A Case Study on Abelian Integrals

speaker
Florent Bréhard, CNRS, University of Lille (France)
date
Friday, 13 May 2022 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
abstract

Last decades saw the emergence of validated numerics (i.e., numerical computations with rigorous error bounds) in computer-aided proofs for mathematics, with major achievements notably in analysis and dynamical systems. This raises questions and challenges which computer scientists are familiar with, such as complexity (how long does is take to compute N correct digits?) and reliability (can we trust an implementation the same way we do for pen-and-paper mathematics?).

In this talk, we will illustrate these challenges with a concrete problem, namely the rigorous numerical evaluation of Abelian integrals. These functions play an essential role in Hilbert's sixteenth problem, since their zeros are connected to the limit cycles of perturbed planar Hamiltonian vector fields. Using truncated Fourier series and rigorous error bounds obtained via fixed- point theorems, we design an efficient algorithm that is also suitable for a formal proof implementation in the Coq theorem prover. Also, we will discuss strategies to compute continuous representations (Taylor, Chebyshev…) of such functions via the associated Picard-Fuchs ODE, and the perspectives of formalizing them in Coq.

This is a joint work with Nicolas Brisebarre, Mioara Joldes and Warwick Tucker.

This session has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101040794, project 10000 DIGITS)

PAST Modeling piecewise polynomial functions with polynomial minimizers

speaker
Didier Henrion, LAAS-CNRS, University of Toulouse (France) and Czech Techncal University in Prague (Czech Republic)
date
Friday, 22 April 2022 at 11:00
location
Paris, Jussieu, salle 25-26/105
abstract
In data science, the quantity to be approximated numerically can be a discontinuous function, e.g. the solution of a nonlinear PDE with shocks, or a bang-bang optimal control. Numerical algorithms may face troubles when approximating such functions, e.g. standard polynomial approximations suffer from the Gibbs phenomenon, namely large oscillations near the discontinuity points that do not vanish when the polynomial degree goes to infinity. In this talk, we introduce a new family of functions designed to deal with such discontinuities. We propose to model or approximate a function of a vector \(x\) by the minimizer with respect to additional (lifting) variables \(y\) of a polynomial of \(x\) and \(y\). We show that piecewise polynomial functions can be modeled exactly this way. For any Lebesgue measurable function, we describe a systematic method to construct a family of approximants of increasing degree such that their minimizers converge to the function pointwise almost everywhere and in the Lebesgue one norm. These approximants are polynomial sums of squares generated from the moments or the samples of the function.

PAST P-adic algorithm to find a basis of pivariate primary components

speaker
Catherine St-Pierre, University of Waterloo (France)
date
Friday, 25 February 2022 at 15:00
location
online only (zoom)
abstract
Inspired by the characterization of a Gröbner cell from Conca and Valla (2007), we will present a quadratically convergent \(p\)-adic algorithm that we developed to find a basis of the primary component of zero dimensional ideal \(I \subset K[x,y]\), where \(K\) is a rational function field (or the rationals). We will also discuss the probability of finding a good prime for the \(p\)-adic expansion and bound the growth of coefficients in a basis.

PAST On finite convergence and convergence rates in polynomial optimization

speaker
Lorenzo Baldi, Inria (France)
date
Friday, 18 February 2022 at 11:00
location
online only (zoom)
abstract

In Polynomial Optimization, finite convergence of the Lasserre's Moment and Sums of Squares hierarchies is often observed in applications, but it is less understood theoretically. We show that finite convergence happens under the so-called Boundary Hessian Conditions at the minimizers, and that this degree is related to the Castelnuovo-Mumford regulaty of the ideal they define. On the contrary, the general, theoretical convergence rate is not well understood, and is deduced from effective versions of Putinar's Positvstellensatz. We give new polynomial bounds for this theorem: these bounds involve a Łojasiewicz exponent associated to the description of the semialgebraic set and, under regularity conditions, to the conditioning number of the Jacobian matrix of the defining inequalities.

Based on joint works with Bernard Mourrain.

PAST New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems

speaker
Guillaume Moroz, Inria (France)
date
Friday, 21 January 2022 at 11:00
location
online only (zoom)
extra
slides + paper
abstract
We present a new data structure to approximate accurately and efficiently a polynomial \(f\) of degree \(d\) given as a list of coefficients. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multipoint evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than 1/2 or greater than 2.

2021

PAST Multiplication in finite fields with Chudnovsky-type algorithms over the projective line

speaker
Bastien Pacifico, I2M, Aix-Marseille Université (France)
date
Friday, 10 December 2021 at 10:30
location
Paris, Jussieu, salle 25-26/105
abstract
We propose a generic construction of interpolation algorithms over the projective line for the multiplication in any finite extension of finite fields. This is a specialization of the method of interpolation on algebraic curves introduced by David and Gregory Chudnovsky. We will use generalizations of this method, in particular the evaluation at places of arbitrary degrees. Our algorithms correspond to usual techniques of polynomial interpolation in small extensions and are defined recursively as the degree of the extension increases. We show that their bilinear complexity is competitive and that they can be constructed in polynomial time.

PAST Fast list decoding of algebraic geometry codes

speaker
Grigory Solomatov, Danmarks Tekniske Universitet
date
Monday, 22 November 2021 at 14:00
location
Paris, Jussieu, salle 24-25/509
abstract

In this talk, we present an efficient list decoding algorithm for algebraic geometry (AG) codes. They are a natural generalization of Reed-Solomon codes and include some of the best codes in terms of robustness to errors. The proposed decoder follows the Guruswami-Sudan paradigm and is the fastest of its kind, generalizing the decoder for one-point Hermitian codes by J. Rosenkilde and P. Beelen to arbitrary AG codes. In this fully general setting, our decoder achieves the complexity \(\widetilde{\mathcal{O}}(s \ell^{\omega}\mu^{\omega - 1}(n+g))\), where \(n\) is the code length, \(g\) is the genus, \(\ell\) is the list size, \(s\) is the multiplicity and \(\mu\) is the smallest nonzero element of the Weierstrass semigroup at some special place.

Joint work with J. Rosenkilde and P. Beelen.

PAST Computing the Smith normal form and multipliers of a nonsingular integer matrix

speaker
George Labahn, Cheriton School of Computer Science, University of Waterloo (Canada)
date
Friday, 19 November 2021 at 11:00
location
Paris, Jussieu, salle 25-26/105
extra
slides
abstract

The Smith normal form of an \(n \times n\) matrix \(A\) of integers or polynomials is a diagonal matrix \(S = diag(s_1, s_2, … , s_n)\) satisfying \(s_1 | s_2 | .. | s_n\) with \(A V = U S\), where \(U\) and \(V\) are unimodular matrices (i.e. det \(U\) = det \(V\) = \(\pm 1\) (integers) or a constant (polynomials). The \(U\) and \(V\) matrices represent row and column operations converting \(A\) into \(S\).

In this talk we give a Las Vegas randomized algorithm for computing \(S, U, V\) in the case where the matrix \(A\) is a nonsingular integer matrix. The expected running time of our algorithm is about the same as the cost required to multiply two matrices of the same dimension and size of entries of \(A\). We also give explicit bounds on the sizes of the entries of our unimodular multipliers. The main tool used in our construction is the so called Smith massager, a relaxed version of our column multiplier \(V\).

This is joint work with Stavros Birmpilis and Arne Storjohann

PAST C2-finite sequences

speaker
Antonio Jiménez-Pastor, École polytechnique, LIX (France)
date
Friday, 15 October 2021 at 11:00
location
Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain
extra
slides
abstract
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 \(C^2\)-finite sequences form a difference ring and provide methods to compute in this ring.

PAST Truncated Moment Cone and Connections to the Coalescence Manifold

speaker
Georgy Scholten, Sorbonne Université, LIP6 (France)
date
Friday, 24 September 2021 at 11:00
location
Paris, Jussieu, salle 25-26/105
extra
slides
abstract
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.

PAST Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems

speaker
Bruno Salvy, Inria, LIP, ENS Lyon (France)
date
Friday, 18 June 2021 at 11:00
extra
slides + paper
abstract

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.

PAST Accelerating the moment-SOS hierarchy for volume approximation

speaker
Didier Henrion, CNRS, LAAS (Toulouse, France), Czech technical university in Prague
date
Friday, 21 May 2021 at 11:00
extra
slides + paper
abstract

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.

PAST Picard-Fuchs equations for Feynman integrals

speaker
Pierre Vanhove, CEA (France), HSE University (Moscow, Russia)
date
Friday, 7 May 2021 at 11:00
extra
slides
abstract

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.

PAST A refined laser method and faster matrix multiplication

speaker
Virginia Vassilevska Williams, MIT (USA)
date
Friday, 9 April 2021 at 16:00
extra
slides
abstract

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.)

PAST Separating variables in bivariate polynomial ideals

speaker
Manfred Buchacher, Johannes Kepler Universität, Linz (Austria)
date
Friday, 2 April 2021 at 11:00
extra
slides
abstract
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.

PAST Linear PDE with constant coefficients

speaker
Bernd Sturmfels, UC Berkerley (USA), MPI Leipzig (Germany)
date
Friday, 12 March 2021 at 15:00
extra
slides
abstract
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.

PAST Symmetric situations in polynomial optimization,

speaker
Philippe Moustrou, University of Tromsø (Norway)
date
Friday, 26 February 2021 at 11:00
extra
slides
abstract

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.

PAST Simultaneous rational function reconstruction and applications to algebraic coding theory

date
Friday, 19 February 2021 at 11:00
speaker
Ilaria Zappatore, INRIA Saclay (France)
extra
slides
abstract

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.

PAST Gröbner bases in Tate algebras

speaker
Thibaut Verron, Johannes Kepler Universität, (Linz, Austria)
date
Friday, 12 February 2021 at 11:00
extra
slides
abstract

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.

PAST Structured algorithms for algebraic curves

speaker
Simon Abelard, École polytechnique, LIX (Palaiseau, France)
date
Thursday, 4 February 2021 at 14:00
extra
slides
abstract

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 Pierrick Gaudry and Pierre-Jean Spaenlehauer, the second part is joint work with Alain Couvreur and Grégoire Lecerf.

PAST Complex roots clustering

speaker
Rémi Imbach, Courant Institute, New York University (USA)
date
Friday, 22 January 2021
abstract
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.

2020 and before

Until 2020, Specfun, ancestor of MATHEXP, held the seminar “Computations and proofs”.

Organizers

current
Jérémy Berthomieu
Pierre Lairez
Hadrien Notarantonio
Rémi Prébet
former
Alin Bostan
Frédéric Chyzak
Huu Phuoc Le
Mohab Safey El Din

Announcements

Announcements are sent to the following mailing lists: