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 $\exp_p$. 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.

Kontsevich's deformations of Poisson structures using directed graphs (1996) were a precursor and by-product of deformation quantisation of the associative product in the algebras of functions on affine finite-dimensional Poisson manifolds (1997). Key to the universal (over manifolds) scheme of infinitesimally deforming the brackets – in such a way that they stay Poisson – is the explicit correspondence between suitable cocycles $\gamma$ in the graph complex (e.g., the tetrahedron $\gamma_3$, pentagon-wheel cocycle $\gamma_5$, their Lie bracket $[\gamma_3,\gamma_5]$, and so on) and Poisson $2$-cocycles $Q_\gamma(P)$ for the deformations $d/d\varepsilon(P)=Q_\gamma(P)$. The enigma of Kontsevich's deformations, observed since 1996, is that for all the examples of Poisson brackets $P$ taken so far and for all the graph cocycles $\gamma$ such that the deformations $Q_\gamma(P)$ can be calculated and tested for (non)triviality, the deformations appear to be trivial, $Q_\gamma(P)=[\![ P,\vec{X} ]\!]$, that is amount to a change of coordinates along integral trajectories of some vector field~$\vec{X}$. We narrow the class of Poisson brackets at hand and refine the calculus of graphs. Namely, to study the mechanism(s) of this `spontaneous' trivialisation for the class of Nambu-determinant Poisson brackets $P(\varrho,[\boldsymbol{a}])$ with $d-2$ global Casimirs $\boldsymbol{a}=(a_1,\ \ldots,\ a_{d-2})$ over dimension $d$, we use a magnifying glass that resolves vertices with $P$ in Kontsevich's graphs to micro-graphs where the Casimirs are distinct as vertices from the Levi--Civita symbols of Jacobian determinants in $P(\varrho,[\boldsymbol{a}])$. We thus detect the (uniqueness of) trivialisation of Kontsevich's tetrahedral flow $Q^{\gamma_3}_d$ over $\mathbb{R}^2$, $\mathbb{R}^3$, and $\mathbb{R}^4$ by $1$-vectors $X^{\gamma_3}_d$ modulo Hamiltonian vector fields. Using the micro-graph calculus, we explore (obstructions to) the dimensional step $d\mapsto d+1$. We conclude that the trivialisation, $Q^\gamma_d=[\![ P, X^\gamma_d ]\!]$, for Nambu–Poisson brackets and graph cocycles $\gamma_3$, $\gamma_5$, $\gamma_7$, etc., is due to mechanism(s) which are different from the combinatorial topology that worked in deformation quantisation.
Joint work in progress with F. M. Schipper, M. S. Jagoe Brown, and R. Buring.
Pdf support file

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.

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 mod 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. The corresponding article may be found at: [DOI | ArXiv] Contains joint work with Seung Gyu Hyun, Bruno Salvy, Éric Schost, Gilles Villard.

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.

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.

Let $G\subseteq\operatorname{SL}_2(\mathbb{C})$ 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\subset\operatorname{SL}_n(\mathbb{C})$ 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 $\operatorname{SL}_3(\mathbb{C})$ can be exploited to aim for an efficient implementation of this generalization for $n=3$.

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

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.

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.

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.

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 (aka 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.