## Joint PolSys–SpecFun 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
Laboratoire d'Informatique de Paris 6 (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://tibre.lip6.fr/wws/info/polsys-seminar

## Upcoming seminars and events

• 10 Dec. 2021, 10:30
seminar

Multiplication in finite fields with Chudnovsky-type algorithms over the projective line,
Bastien Pacifico,

I2M, Aix Marseille Université.

• 21 Jan. 2022, 11:00
seminar

TBD,
Erik Panzer,

Mathematical Institute, University of Oxford.

• Sep. to Dec. 2023
conference

Thematic program on Recent Trends in Computer Algebra.

• Sep. to Dec. 2021 POSTPONED to 2024
conference

Thematic program at Institut Henri Poincaré on post-quantum algebraic cryptography.

## Next seminars

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

10 December 2021

10:30

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

### TBD

21 January 2022

11:00

Inria Saclay, room TBD & online

TBD

Erik Panzer,

Mathematical Institute, University of Oxford.

## Past seminars

### Fast list decoding of algebraic geometry codes

22 November 2021

14:00

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

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, amphitheatre 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

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