The MATHEXP seminar
The MATHEXP seminar is held in Palaiseau and broadcasted online.
Upcoming talks
NEXT Some computations related to monodromy representations
- speaker
- Eric Pichon-Pharabod, MPI MiS, Leipzig (Germany)
- date
- location
- Inria Saclay, bâtiment Turing, salle Henri Poincaré
- abstract:
- I will present a method for computing monodromy representations associated to families of projective varieties relying on numerical evaluations of period matrices. I will discuss applications of these methods to various settings, namely families of cubic surfaces, families of Calabi-Yau threefold of type (1,1,1,1) (joint with Duco van Straten), and the study of degenerations of K3 surfaces in mirror symmetry (joint with Charles Doran and Alan Thompson).
UPCOMING TBA
- speaker
- Josué Moreau, LMF, Université Paris-Saclay (France)
- date
- location
- Inria Saclay, bâtiment Turing, salle Grace Hopper
2024
PAST Computer-assisted proofs and dynamics of delay maps
- speaker
- Olivier Hénot, École polytechnique (France)
- date
- location
- Inria Saclay, bâtiment Turing, salle Grace Hopper
- abstract
- Computer-assisted proofs (CAPs) have become an essential tool for rigorously validating mathematical results, particularly in fields where pen-and-paper analytical approaches alone prove challenging. In this talk, we will first discuss a posteriori validation methods; that is, CAP techniques designed to certify solutions and establish rigorous bounds on computational errors. Then, we will explore their application in the study of delay maps derived from delay differential equations (DDEs) of the form \(y′(t) = \alpha y(t) + g(y(t − \tau))\). DDEs are naturally set on infinite-dimensional spaces and as such, even scalar equations exhibit rich dynamics. The approach integrates Chebyshev series expansions to rigorously evaluate the delay map. Leveraging this rigorous evaluation, we develop a method to establish the existence of periodic orbits. We demonstrate the application of our framework using the Mackey-Glass equation as a case study. If time permits, we will further discuss how to determine the Morse index of periodic solutions, and how to this paves the way for proving the existence of chaotic dynamics
PAST Fast evaluation of Riemann theta functions in any dimension
- speaker
- Jean Kieffer, CNRS, Loria, Nancy (France)
- date
- location
- Inria Saclay, bâtiment Turing, salle Grace Hopper
- abstract
- The Riemann theta functions are multivariate complex-analytic functions with deep links to the theory of abelian varieties over the complex numbers. For applications in algorithmic number theory, one would like to efficiently evaluate them at a given point (a period matrix) to very large precision with certified error bounds. In this talk, I will present a new evaluation algorithm for theta functions in uniform quasi-linear time in the required precision, in any fixed dimension (joint work with Noam D. Elkies). I will also discuss its implementation in the FLINT number theory library.
PAST Bernstein—Sato polynomials of hyperplane arrangements in three variables.
- speaker
- Daniel Bath, KU Leuven (Belgium)
- date
- location
- Inria Saclay, bâtiment Turing, salle Henri Poincaré
- abstract
- The Bernstein–Sato polynomial is a famous singularity invariant of a hypersurface coming from the theory of D-modules. It is also famously hard to compute. For hyperplane arrangements (products of linear polynomials) in two variables there is a simple combinatorial formula for the roots of the Bernstein–Sato polynomial dating to the 1970s. However, there can be no such combinatorial formula for hyperplane arrangements in three variables: in 2015, Walther revealed two arrangements with the same combinatorics whose Bernstein–Sato polynomial root sets differ. We give a formula for the roots of the Bernstein–Sato polynomial of any hyperplane arrangement in three variables. It turns out there is only one candidate root that is not combinatorial: \(-2 + 2/\text{degree}\). However, its root-hood is characterized by a simple local cohomology condition on the Milnor algebra. This is the main prize in a larger study of Bernstein—Sato polynomials of locally quasihomogeneous polynomials in three variables.
- paper
- arxiv:2402.08342
PAST Computing class groups in presence of automorphisms
- speaker
- Aurel Page, Inria Bordeaux (France)
- date
- location
- Inria Saclay, bâtiment Turing, salle Henri Poincaré
- abstract
- The following algorithmic situation is common: given a certain object \(X\), we would like to compute a certain attached abelian group \(H(X)\). One number-theoretic example is where \(X\) is a number field and \(H(X)\) its class group, but there are also many geometric examples where \(H\) is a cohomology theory. In many interesting examples, the object \(X\) comes with the action of a finite group \(G\). Can we exploit this extra structure to speed up the computation of \(H(X)\)? I will present norm relations, a representation-theoretic method for this type of situation, and our algorithms applying it to computations of class groups, giving super-polynomial improvements (this is joint work with J.-F. Biasse, C. Fieker and T. Hofmann). Our implementation using PARI/GP yields speedups of several orders of magnitude. Time permitting, I will mention an extension of this method by Fabrice Etienne, that uses a weaker structure than actual automorphisms.
PAST Singular loci of hyperplane arrangements
- speaker
- Saiei-Jaeyeong MATSUBARA-HEO, Kobe University (Japan)
- date
- location
- Inria Saclay, bâtiment Turing, salle Carl Gauss
- abstract
We are interested in the singularities of the integral of powers of liner forms. There is an expectation of a connection with the drop in Euler characteristic. We study this in the case coefficients are sparse, and the case coefficients are restricted to a subspace of the parameter space.
This is a joint work with Claudia Fevola.
PAST Fuchs' theorem, an exponential function, and Abel's problem in positive characteristic
- speaker
- Florian Fürnsinn, University of Vienna, Vienna (Austria)
- date
- location
- Inria Saclay, bâtiment Turing, Salle Grace Hopper
- abstract
The local solution theory of regular singular ordinary linear differential equations over fields of characteristic zero was already developed in the 19th century by Fuchs and Frobenius. The Grothendieck $p$-curvature conjecture motivates the search for a similar theory for equations over fields of positive characteristic. In this talk I will define a differential extension of the power series over a field \(k\) of positive characteristic \(p\), making use of new variables that behave under differentiation like iterated logarithms in characteristic zero. It turns out that every regular singular ordinary linear differential equation with polynomial or power series coefficients over k admits a full basis of solutions in this extension. In particular, the exponential differential equation \(y′=y\) has a solution expp. Such solutions have remarking properties, which we will explore. For example, I will discuss an analogue of Abel's problem about the algebraicity of logarithmic integrals over k.
This talk is based on joint work with H. Hauser and H. Kawanoue.
PAST Calculations with Poisson brackets on \(\mathbb{R}^d\): some bases (of graphs) are more equal than others.
- speaker
- Arthemy Kiselev, University of Groningen, Netherlands
- date
- location
- Inria Saclay, bâtiment Turing, salle Grace Hoppen + online
- abstract
Suppose that some natural combinatorial structures – such as directed graphs – encode elements of some natural vector spaces – e.g., of differential polynomials on \(\mathbb{R}^d\), – yet it can be that two topologically non-isomorphic graphs encode the same formula. Will then all bases of linearly independent graphs be equal, or will some graph tuples be more equal than others?
We encounter this effect in the (non)triviality problem for infinitesimal deformations of Poisson brackets on \(\mathbb{R}^d\) by using Kontsevich's graph calculus (and its adaptation to the class of Nambu-determinant Poisson structures; both the standard calculus of graphs and its refined micro-graph version are implemented in software {gcaops} by R.Buring). For a chosen datum about the deformation, the problem under study gives us a sequence of overdetermined inhomogeneous linear algebraic systems (upon the undetermined coefficients of micro-graphs) over the spaces \(\mathbb{R}^d\), \(d\geqslant 2\), equipped with the Nambu–Poisson brackets. We detect that the linear systems are solvable if \(d=2,3,4\) and that the shifts along the respective affine spaces of solutions are purely Hamiltonian, hence not essential, at each \(d=2,3,4\). Yet we explore also whether (and why not always) solutions from lower dimension do or do not extend to solutions in higher dimension, depending on our choice of the micro-graphs, i.e. of the basis to encode the formula of solution in lower dimension.
The problem – whether there is a solution to the linear system that one would obtain over \(\mathbb{R}^d\) for \(d\gg 2\) – is open; we analyse obstructions in the bottom-up approach.
Work in progress, joint with R.Buring (INRIA) and M.S. Jagoe Brown and F.M. Schipper (Groningen).
- extra
- lecture notes
PAST D-Module Techniques for Solving Differential Equations in the Context of Feynman Integrals
- speaker
- Anna-Laura Sattelberger, KTH Royal Institute of Technology, Stockholm (Sweden)
- date
- location
- Inria Saclay, bâtiment Turing, salle Grace Hopper + online
- abstract
- I explain how to compute series solutions of regular holonomic D-ideals with Gröbner basis methods via an algorithm due to Saito, Sturmfels, and Takayama, which is a vast generalization of Frobenius’ method. As a point in case, I consider a D-ideal originating from a triangle Feynman diagram. This talk is based on the joint work arXiv:2303.11105 with Johannes Henn, Elizabeth Pratt, and Simone Zoia. Therein, we compare D-module techniques to dedicated methods developed for solving differential equations in the context of Feynman integrals.
PAST Faster modular composition of polynomials
- speaker
- Vincent Neiger, Sorbonne Université, Paris (France)
- date
- location
- Paris, Jussieu, corridor 26-00, room 428 + online
- abstract
- This talk is about algorithms for modular composition of univariate polynomials, and for computing minimal polynomials. For two univariate polynomials a and g over a commutative field, modular composition asks to compute h(a) mod g for some given h, while the minimal polynomial problem is to compute h of minimal degree such that \(h(a) = 0 \pmod g\). We propose algorithms whose complexity bound improves upon previous algorithms and in particular upon Brent and Kung's approach (1978); the new complexity bound is subquadratic in the degree of g and a even when using cubic-time matrix multiplication. Our improvement comes from the fast computation of specific bases of bivariate ideals, and from efficient operations with these bases thanks to fast univariate polynomial matrix algorithms. We will also report on experimental results using the Polynomial Matrix Library. Contains joint work with Seung Gyu Hyun, Bruno Salvy, Éric Schost, Gilles Villard.
PAST Studying nested binomial sums and their asymptotics using the RICA package
- speaker
- Nikolai Fadeev, Research Institute for Symbolic Computation, Linz (Austria)
- date
- location
- Inria Saclay, bâtiment Turing, room Grace Hopper
- abstract
- Nested binomial sums form a particular class of sums that appear in particle physics computations, in particular in quantum electrodynamics or quantum chromodynamics, but also in combinatorics in mathematics. While computing a closed form for those is not always possible, one can in particular try to study their asymptotics at infinity, for example to get analytical continuations. We will present our package RICA which implements and extends a method sketched in « Iterated Binomial Sums and their Associated Iterated Integrals » (J. Ablinger, J.Blümlein, J.C.Raab, C. Schneider) [arXiv:1407.1822] for computing Mellin representations and asymptotic expansions of such sums.
2023
PAST Pop-stack sorting and pattern-avoiding permutations
- speaker
- Emily Barnard, DePaul University, Chicago (USA)
- date
- location
- amphitheatre Darboux, Institut Henri Poincaré (Paris)
- abstract
- The pop-stack sorting method takes an ordered list or permutation and reverses each descending run without changing their relative positions. In this talk we will review recent combinatorial results on the pop-stack sorting method, and we will extend the pop-stack sorting method to certain pattern avoiding permutations. This talk will be accessible to all.
Joint event with RTCA
PAST Ordinary linear differential equations with algebraic solutions
- speaker
- Camilo Sanabria Malagón, Universidad de los Andes, Colombia
- date
- location
- amphitheatre Darboux, Institut Henri Poincaré (Paris)
- abstract
- Let G⊆SL2(ℂ) be a finite primitive group. A classical result of Klein states that there exists a hypergeometric equation such that any second order linear ordinary differential equation whose differential Galois group is G is projectively equivalent to the pullback by a rational map of this hypergeometric equation. In this talk I present a generalization of this result. Let G⊆SLn(ℂ) be a finite primitive group. I will show that there is a positive integer d=d(G) and a standard equation such that any linear ordinary differential equation whose differential Galois group is G is gauge equivalent over a field extension of degree d to an equation projectively equivalent to the pullback by a map of this standard equations. For n=3, the standard equations can be chosen so that they are hypergeometric. Implementations of Klein's result exist. If time permits, I will show how the properties of the invariants of the primitive subgroups of SL3(ℂ) can be exploited to aim for an efficient implementation of this generalization for n=3.
Joint event with RTCA
PAST Continued fraction expansions of algebraic power series over a finite field
- speaker
- Yann Bugeaud, IRMA, Université de Strasbourg (France)
- date
- location
- salle Pierre Grisvard, Institut Henri Poincaré (Paris)
- abstract
- Almost nothing is known on the continued fraction expansion of an algebraic real number of degree at least three. The situation is different over the field of power series \({{\mathbb F}}_p((x^{-1}))\), where \(p\) is a prime number. For instance, there are algebraic power series of degree at least three whose sequence of partial quotients have bounded degree. And there are as well algebraic power series of degree at least three which are very well approximable by rational fractions: the analogue of Liouville's theorem is best possible in \({{\mathbb F}}_p((x^{-1}))\). Recently, in a joint work with Han (built on a previous work by Han and Hu), we proved that, for any distinct nonconstant polynomials \(a, b\) in \({{\mathbb F}}_2 [x]\), the power series
\[ [a; b, b, a, b, a, a, b, \ldots ] = a + \frac{1}{b + \frac{1}{b + \cdots}},\] whose sequence of partial quotients is given by the Thue–Morse sequence, is algebraic of degree \(4\) over \({{\mathbb F}}_2 (x)\). We discuss this and related results. Furthermore, we give a complete description of the continued fraction expansion of the algebraic power series \((1 + x^{-1})^{j/d}\) in \({{\mathbb F}}_p((x^{-1}))\), where \(j, d\) are coprime integers with \(d \ge 3\), \(1 \le j < d/2\), and \(\gcd(p, jd) = 1\) (joint work with Han).
PAST Generating series and proofs of inherent ambiguity
- speaker
- Florent Koechlin, LORIA, Nancy (France)
- date
- location
- Inria Saclay, bâtiment Turing, room Grace Hopper + online
- abstract
- I will talk about the connection between inherent ambiguity of formal languages and the properties of their generating series. It is a classical result that regular languages have rational generating series and that the generating series of unambiguous context-free languages are algebraic. In the eighties, Philippe Flajolet developed several tools based on this connection to prove efficiently and easily the inherent ambiguity of many context-free languages, some of which resisted the historical methods based on iterations. In this talk I will present how these ideas relying on generating series can be extended to Parikh automata, and how they provide an algorithmic tool to decide the inclusion problem on unambiguous Parikh automata. This is a joint work with Alin Bostan, Arnaud Carayol and Cyril Nicaud.
PAST Differential and difference equations from linear fibrations
- speaker
- Erik Panzer, Mathematical Institute, University of Oxford (UK)
- date
- location
- Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
- abstract
- Integrals in many variables can be evaluated more efficiently if the dependence of the integrand on a suitable variable is particularly simple. I will talk about algorithms for hyperlogarithms, an old class of special functions which arise from iterating integrals of rational functions and have many applications. I will also discuss how to predict the singularities of many-variable integrals, which applies more generally, and is useful to pick an integration order. Finally, I will discuss applications to hypergeometric functions, that is, integrands with symbolic exponents, and applications to Feynman integrals.
PAST Toric varieties and Gibbs manifolds in convex optimization
- speaker
- Simon Telen, CWI, Amsterdam (Netherlands)
- date
- location
- Paris, Jussieu, couloir 25-26, salle 105 + online
- abstract
Entropic regularization for linear programming leads to intersecting a toric variety with the feasible polytope. In semidefinite programming, the toric variety is replaced by a new geometric object, called Gibbs manifold, and the feasible polytope becomes a spectrahedron. I will explain these concepts and present the example of (quantum) optimal transport.
This is based on joint work with Dmitrii Pavlov, Bernd Sturmfels, François-Xavier Vialard and Max von Renesse.
PAST The moment problem and convex hulls of semialgebraic sets
- speaker
- Simone Naldi, XLIM, université de Limoges (France)
- date
- location
- Paris, Jussieu, couloir 25-26, salle 105 + online
- abstract
- The duality between moments of measures with support contained in a semialgebraic set \(K\), and the cone of polynomials nonnegative on \(K\), is the context of the so-called Moment-SOS (a.k.a. Lasserre) hierarchy, for relaxing polynomial optimization problems to several semidefinite programs. In this talk I will discuss the problem of computing the convex hull of a compact semialgebraic set \(K\): geometrically, this corresponds to the intersection of all linear hyperspaces containing \(K\), and algebraically, it consists of representing all linear functions that are positive over \(K\) with weighted SOS certificates. I will present a recent new primal-dual certificate, based on a joint work with D. Henrion. In the last part of the talk, I will discuss algorithmic and complexity aspects of the so-called truncated moment problem for compact basic semialgebraic sets, based on joint work with D. Henrion and M. Safey El Din.
PAST Faster computation of elementary functions
- speaker
- Fredrik Johansson, Inria, IMB, université de Bordeaux (France)
- date
- location
- Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
- abstract
- Over a decade ago, Arnold Schönhage proposed a method to compute elementary functions (exp, log, sin, arctan, etc.) efficiently in “medium precision” (up to about 1000 digits) by reducing the argument using linear combinations of pairs of logarithms of primes or Gaussian primes. We generalize this approach to an arbitrary number of primes (which in practice may be 10-20 or more), using an efficient algorithm to solve the associated Diophantine approximation problem. Although theoretically slower than the arithmetic-geometric mean (AGM) by a logarithmic factor, this is now the fastest algorithm in practice to compute elementary functions from about 1000 digits up to millions of digits, giving roughly a factor-two speedup over previous methods. We also discuss the use of optimized Machin-like formulas for simultaneous computation of several logarithms or arctangents of rational numbers, which is required for precomputations.
PAST Generalized integral bases and applications in creative telescoping
- speaker
- Lixin Du, Johannes Kepler University, Linz (Austria)
- date
- location
- Inria Saclay, bâtiment Turing, salle Sofia Kovalevkaïa + online
- abstract
- In this talk, we explore the applications of integral bases in symbolic integration via creative telescoping. Trager’s Hermite reduction solves the integration problem for algebraic functions via integral bases, which was extended to Fuchsian D-finite functions. We remove the Fuchsian restriction and present Hermite reduction for general D-finite functions via integral bases. It reduces the pole orders of integrands at finite places. Combining Hermite reduction at finite places and at infinity, we obtain a new reduction-based telescoping algorithm for D-finite functions in two variables. This is the joint work with Shaoshi Chen and Manuel Kauers.
2022
PAST What do we know about the cogrowth sequence?
Jointly organized with the “Groupe de travail Transcendance et combinatoire”.
- speaker
- Igor Pak Mathematics Department, University of California, Los Angeles (USA)
- date
- location
- Paris, Institut Henri Poincaré, amphithéâtre Darboux + online
- abstract
- Take a group and a set of generators. Denote by \(a(n)\) the number of words in the generators with product 1 of length \(n\) (these are loops in the corresponding Cayley graph). The cogrowth sequence \(\{a(n)\}\) is the main object of our study. Turns out, it carries remarkably rich information about the group, as one considers arithmetic and asymptotic properties of \(a(n)\), as well as algebraic properties of the generating function for \(\{a(n)\}\). In the first half of the talk I will review what is known about the problem from different points of view: combinatorics, group theory and computational complexity. In the second half, I will present our recent work on the subject (joint with David Soukup), where we obtain the first negative result for the cogrowth sequence of nilpotent groups in the most unexpected way. This talk is aimed at the general audience and no background will be assumed.
PAST Special session on holonomy
Jointly organized with the “Groupe de travail Transcendance et combinatoire”.
Guessing with little data
- speaker
- Christoph Koutschan, RICAM, Linz (Austria)
- date
- location
- Paris, Jussieu, couloir 25-26, salle 105 + online
- abstract
Reconstructing a hypothetical recurrence equation from the first terms of an infinite sequence is a well-known technique in experimental mathematics, also referred to as “guessing”. We combine the classical linear-algebra approach to guessing with lattice reduction, which in many instances allows us to find the desired recurrence using fewer input terms. We have successfully applied our method to sequences from the OEIS and have identified several examples, for which it would have been very difficult to obtain the same result with the traditional approach.
This is joint work with Manuel Kauers.
- paper
- 2202.07966
- extra
- slides
Gerrymandering
- speaker
- Manuel Kauers, Johannes Kepler University, Linz (Austria)
- date
- location
- Paris, Jussieu, couloir 25-26, salle 105 + online
- abstract
We report on some efforts to compute the next few terms of the so-called gerrymandering sequence A348456 that counts the number of ways to dissect a square grid into two connected regions of the same size.
This is joint work with Christoph Koutschan and George Spahn.
- paper
- 2209.01787
- extra
- slides
Vector spaces of generalized Euler integrals
- speaker
- Claudia Fevola, MPI MiS, Leipzig (Germany)
- date
- location
- Paris, Jussieu, couloir 25-26, salle 105 + online
- abstract
We study vector spaces associated to a family of generalized Euler integrals. Their dimension is given by the Euler characteristic of a very affine variety. Motivated by Feynman integrals from particle physics, this has been investigated using tools from homological algebra and the theory of D-modules. In this talk, I will present an overview of the main tools needed to study these vector spaces, namely twisted de Rham cohomology and Mellin transform. Finally, I will discuss relations between these approaches.
This is a joint project with Daniele Agostini, Anna-Laura Sattelberger, and Simon Telen.
- paper
- 2208.08967
- extra
- slides
PAST Sylvester forms and elimination matrices
- speaker
- Laurent Busé, Inria, université Côte d'Azur (France)
- date
- location
- Paris, Jussieu, couloir 25-26, salle 105 + online
- abstract
- Sylvester forms of \(n\) homogeneous polynomials in \(n\) variables have been introduced by Jean-Pierre Jouanolou to make explicit a certain duality that unravel the structure of some graded components of elimination ideals. By definition, they are determinants that generalize the classical Jacobian determinant. In this talk, the construction and properties of Sylvester forms will be reviewed, with a particular focus on the construction of a family of “hybrid elimination matrices”, that can be seen as a generalization of the family of hybrid Bézout matrices for univariate polynomials. These matrices are more compact than the usual Macaulay matrices, but they can still be used to solve zero-dimensional polynomial systems by means of linear algebra methods. If time permits, extension of the theory of Sylvester forms to multi-projective spaces (joint work with Marc Chardin and Navid Nemati) and to toric varieties (joint work with Carles Checa) will be discussed.
PAST Walks avoiding a quadrant and the reflection principle
- speaker
- Michael Wallner, Institute of Discrete Mathematics and Geometry, TU Wien (Austria)
- date
- location
- Inria Saclay, bâtiment Turing, amphithéâtre Sophie-Germain + online
- abstract
We continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by Bousquet-Mélou in 2016. We solve in detail a new case, namely the king model where all eight nearest neighbour steps are allowed. The associated generating function satisfies an algebraicity pheonomeon: it is the sum of a simple, explicit D-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou, 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of degree up to 216. We expect a similar algebraicity phenomenon to hold for the seven Weyl step sets, which are those for which walks confined to the first quadrant can be counted using the reflection principle. This is now proved for three of them. For the remaining four, we predict the D-finite part of the solution, and in three of the four cases, give evidence for the algebraicity of the remaining part.
This is joint work with Mireille Bousquet-Mélou.
PAST Sums of powers of binomials, their Apéry limits, and Franel's suspicions
- speaker
- Armin Straub, University of South Alabama (USA)
- date
- 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
- 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
- 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.
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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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 \gt0\); the best bound until now is \(\omega\lt 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 \lt 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- The MATHEXP team
- former
- Alin Bostan
Frédéric Chyzak
Hadrien Notarantonio
Huu Phuoc Le
Jérémy Berthomieu
Mohab Safey El Din
Pierre Lairez
Rémi Prébet
Sriram Gopalakrishnan
During 2021–2024, the seminar was run jointly with the Polsys seminar.
This seminar receives 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).
Announcements
Announcements are sent to the following mailing lists:
- gt-cf@gdr-ifm.fr
- mathexp-seminar@inria.fr
You can subscribe to the latter by sending an email to sympa_inria@inria.fr with subscribe mathexp-seminar in the subject line.