## Joint MATHEXP–PolSys Seminar. (Archive)

This seminar focuses mainly on computer algebra algorithms and implementations for solving mathematical problems exactly, with a special focus on polynomial system solving and its broad range of applications.

Among others, topics which are covered are:
• Foundational computer algebra algorithms for polynomials, series and matrices
• Polynomial system solving with algebraic and/or certified numerical methods
• Applications of non-linear algebra algorithms such as cryptography, polynomial optimization, and computational geometry
We also organize reading groups on important computer algebra algorithms.
Location
LIP6 (UMR CNRS 7606)
Campus Pierre-et-Marie-Curie
Sorbonne Université
4 place Jussieu
75005 Paris, France
or
Inria Saclay – Île-de-France
Bâtiment Alan Turing
Campus de l'École polytechnique
1 rue Honoré d'Estienne d'Orves
91120 Palaiseau, France
Organizers
Former Organizers
2020/09/01 – 2021/08/31

To receive further anouncements, register for the mailing list here:

https://listes.lip6.fr/sympa/subscribe/polsys-seminar

## Upcoming seminars and events

• 25th Nov. 2022,
LIP6 11:00
seminar with GT TC

Guessing with Little Data
Christoph Koutschan
Johann Radon Institute for Computational and Applied Mathematics

• 25th Nov. 2022,
LIP6 14:00
seminar with GT TC

Gerrymandering
Manuel Kauers
Institut für Algebra, Johannes Kepler Universität Linz

• 25th Nov. 2022,
LIP6 15:30
seminar with GT TC

Vector Spaces of Generalized Euler Integrals
Claudia Fevola
Max-Planck-Institut für Mathematik in den Naturwissenschaften

• 9th Dec. 2022,
IHP 14:30
seminar with GT TC

What do we know about the cogrowth sequence?
Igor Pak
Mathematics Department, University of California, Los Angeles

• Sept. – Dec. 2023
conference

Thematic program at Institut Henri Poincaré on Recent Trends in Computer Algebra.
See here for the program and here (IHP page).

• 2024
conference

## Next seminars

### Guessing with Little Data

25th Nov. 2022

11:00

LIP6 25-26/105 & online

Co-organized with Groupe de travail « Transcendance et combinatoire »

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.

Christoph Koutschan

Johann Radon Institute for Computational and Applied Mathematics

### Gerrymandering

25th Nov. 2022

14:00

LIP6 25-26/105 & online

Co-organized with Groupe de travail « Transcendance et combinatoire »

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, arXiv:2209.01787.

Manuel Kauers

Institut für Algebra, Johannes Kepler Universität Linz

### Vector Spaces of Generalized Euler Integrals

25th Nov. 2022

15:30

LIP6 25-26/105 & online

Co-organized with Groupe de travail « Transcendance et combinatoire »

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. F inally, I will discuss relations between these approaches. This is a joint project with Daniele Agostini, Anna-Laura Sattelberger, and Simon Telen.

Claudia Fevola

Max-Planck-Institut für Mathematik in den Naturwissenschaften

### What do we know about the cogrowth sequence?

9th Dec. 2022

14:30

IHP Amphithéâtre Darboux

Co-organized with Groupe de travail « Transcendance et combinatoire »

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.

Igor Pak

Mathematics Department, University of California, Los Angeles

### TBA

13th Jan. 2023

11:00

LIP6 25-26/105 & online

TBA

Simone Naldi

Computer Algebra team, Xlim, Université de Limoges

### TBA

27th Jan. 2023

11:00

Inria Saclay, amphithéâtre Sophie-Germain & online

TBA

Fredrik Johansson

LFANT, IMB, Centre Inria de Bordeaux

### TBA

10th Feb. 2023

11:00

Inria Saclay, amphithéâtre Sophie-Germain & online

TBA

Anna-Laura Sattelberger

KTH Royal Institute of Technology, Stockholm

## Past seminars

### Sylvester forms and elimination matrices

18th Nov. 2022

11:00

LIP6 25-26/105 & online

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.

Laurent Busé

Team Aromath, Centre Inria d'Université Côte d'Azur

### Walks avoiding a quadrant and the reflection principle

14th Oct. 2022

11:00

Inria Saclay, amphithéâtre Sophie-Germain & online

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.

Michael Wallner

Institute of Discrete Mathematics and Geometry, TU Wien

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

1st July 2022

11:00

LIP6 25-26/105 & online

Co-organized with Groupe de travail « Transcendance et combinatoire »

Apéry's proof of the irrationality of $\zeta(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.

Armin Straub

Department of Mathematics and Statistics, University of South Alabama

### Sparse polynomial interpolation and exact division over $\mathbb{Z}$

10 June 2022

11:00

LIP6 25-26/105 & online

We present a new Monte Carlo randomized algorithm to recover an integer polynomial $f(x)$ given a way to evaluate $f(a) \bmod 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.

Armelle Perret du Cray

Team ECO, LIRMM
Université de Montpellier

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

13 May 2022

11:00

Inria Saclay, amphithéâtre Sophie-Germain & online

Validated Numerics and Formal Proof for Computer-Aided Proofs in Mathematics: A Case Study on Abelian Integrals 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.

Florent Bréhard

Centre de Recherche en Informatique, Signal et Automatique de Lille

### Modeling piecewise polynomial functions with polynomial minimizers

22 April 2022

11:00

LIP6 25-26/105 & online

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.

Didier Henrion

LAAS-CNRS Univ. Toulouse and Czech Tech. Univ. Prague

### $p$-adic Algorithm to Find a Basis of Bivariate Primary Components

25 February 2022

15:00

Online

Inspired by the characterization of a Gröbner cell from Conca and Valla [2007], we will present a quadratic convergent $p$-adic algorithm that we developed to find a basis of a primary component of a zero-dimensional ideal $I \subset \mathbb{K}[x,y]$, where $\mathbb{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 the coefficients in a basis.

Catherine St-Pierre,

University of Waterloo.

### On Finite Convergence and Convergence Rates in Polynomial Optimization

18 February 2022

11:00

Online

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

Lorenzo Baldi,

Team AROMATH, Inria Sophia Antipolis-Méditerranée.

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

21 January 2022

11:00

Online

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.

Guillaume Moroz,

Team Gamble, Inria Nancy – Grand Est.

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

10 December 2021

10:30

LIP6 25-26/105 & online

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.

Bastien Pacifico,

I2M, Aix Marseille Université.

### Fast list decoding of algebraic geometry codes

22 November 2021

14:00

LIP6 24-25/509 & online

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.

Grigory Solomatov,

Department of Applied Mathematics and Computer Science Mathematics, Danmarks Tekniske Universitet.

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

19 November 2021

11:00

LIP6 25-26/105 & online

The Smith normal form of an $n \times n$ matrix $A$of integers or polynomials is a diagonal matrix S$= \operatorname{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

George Labahn,

Cheriton School of Computer Science, University of Waterloo.

### C2-finite sequences

15 October 2021

11:00

Inria Saclay, amphithéâtre Sophie-Germain & online

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.

Antonio Jiménez-Pastor,

LIX, École polytechnique.

### Truncated Moment Cone and Connections to the Coalescence Manifold

24 September 2021

11:00

LIP6 25-26/105 & online

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.

Georgy Scholten,

PolSys, LIP6, Sorbonne Université.