Dates: November 27 – December 1 (Special week), December 4–8 (Workshop), December 11 (Topical day)
Place: Amphitheater Hermite at the IHP
Live stream
How to come to IHP
Some restaurants close to IHP


Workshop: Computer Algebra for Functional Equations in Combinatorics and Physics

December 4 to 8, 2023 (Amphitheater Hermite)

Organizers: A. Bostan, J. Bouttier, T. Cluzeau, L. Di Vizio, C. Krattenthaler, P. Lairez, J.-M. Maillard

In many areas of pure and applied mathematics, as well as in computer science and in theoretical physics, functional equations form either the object of study or important tools for applications. We are currently experiencing increasingly strong interactions between theory and applications, many common actions having taken place over the past ten years. By functional equations, we mean mainly ordinary differential equations, with differences, with $q$-differences, Mahlerian, linear or algebraic, possibly multivariate. For instance, nonlinear algebraic differential equations emerge naturally in integrable models in physics (Painlevé equations, Schlesinger systems, KdV equations, etc., associated with Lax pairs, Yang-Baxter equations,…). All these types of functional equations have been and are still very actively studied from many points of view, using algebraic, arithmetic and geometric tools. A recent trend is that computer algebra algorithms are more and more used to solve functional equations arising in enumerative combinatorics and in statistical physics. Notable examples come from questions related to lattice walks. In combinatorics, basic objects like trees, maps, permutations, and Young tableaux can be represented by models of walks confined to cones. In physics, many objects, including polymers and queueing models, are accurately modeled by walks on lattices, particularly those evolving in cones with several boundaries. This workshop brings together representatives from the three different communities (computer algebra, combinatorics and theoretical physics) to discuss longstanding conjectures, to learn each other’s techniques and to plan the directions for the future.

Invited speakers

Program of the workshop - All talks in Amphitheater Hermite

Live stream

    Monday December 4th, 2023
9:30-10:00 Welcome coffee
Chair: Thomas Cluzeau
10:00-11:00 Kilian Raschel
Persistence for a class of order-one autoregressive processes and Mallows-Riordan polynomials
Abstract. We establish exact formulae for the (positivity) persistence probabilities of an autoregressive sequence with symmetric uniform innovations in terms of certain families of polynomials, most notably a family introduced by Mallows and Riordan as enumerators of finite labeled trees when ordered by inversions. The connection of these polynomials with the volumes of certain polytopes is also discussed. Two further results provide factorizations of general autoregressive models, one for negative drifts with continuous innovations, and one for positive drifts with continuous and symmetric innovations. The second factorization extends a classical universal formula of Sparre Andersen for symmetric random walks. Our results also lead to explicit asymptotic estimates for the persistence probabilities. This is a joint work with Gerold Alsmeyer, Alin Bostan and Thomas Simon (Adv. Appl. Math., 2023).
11:00-12:00 Michael Wallner
Stretched exponentials and beyond
Abstract. The appearance of a stretched exponential term \[\mu^{n^{\sigma}}\] with $\mu>0$ and $\sigma \in (0,1)$ in a counting sequence $(c_n)_{n\geq0}$ is not common, although more and more examples are appearing lately. Proving that a sequence has a stretched exponential is often quite difficult. This is in part because such a sequence cannot be "very nice": its generating function cannot be algebraic, and it can only be D-finite if it has an irregular singularity. Previously, the saddle-point method was the only generic method for proving such a phenomenon, but it requires detailed information about the generating function. Recently, together with Andrew Elvey Price and Wenjie Fang, we have developed a new method at the level of recurrences to prove stretched exponentials. I will introduce the basics of this method and show how it can be extended to other problems. Then I will summarize recent progress (new bijections, limit laws, etc.) in the study of compacted trees, a subclass of directed acyclic graphs. Finally, I will give an outlook on how these results now allow an in-depth study of limit shapes and open many new avenues for further research.
12:00-15:00 Lunch break
Chair: Christian Krattenthaler
15:00-16:00 Carsten Schneider
Summation Tools for Combinatorics and Elementary Particle Physics
Abstract. The summation theory of difference rings provides general and efficient tools to derive linear recurrences for definite sums based on parameterized telescoping and to solve recurrences within the class of indefinite nested sums defined over hypergeometric products, q-hypergeometric products and more generally, mixed hypergeometric products and their nested versions. In particular, one can use these techniques to simplify definite multi-sums to representations in terms of the class indefinite nested sums defined over indefinite nested products. A special feature is that the representation of the arising sums and products are optimal in the sense that the objects interpreted as sequences (except root of unity products) do not satisfy any algebraic relations among each other. This leads not only to compact expressions in the final output, but also speeds up significantly the underlying summation algorithms. In particular, one gains a general (Galois) machinery to prove algorithmically algebraic independence of big classes of sums and products. We will illustrate this algorithmic difference ring toolbox by non-trivial applications coming from enumerative combinatorics and elementary particle physics.
16:00-16:30 Coffee break
16:30-17:30 Igor Pak
What is beyond D-finite
Abstract. I will review some classes of GFs that are of interest in Enumerative Combinatorics but remain understudied. This talk will be accessible to the general audience.
    Tuesday December 5th, 2023
9:30-10:00 Welcome coffee
Chair: Lucia Di Vizio
10:00-11:00 Charlotte Hardouin
Galois group for large steps walks
Abstract. In this talk, we will present some Galois theoretic tools to study large steps walks confined in the quadrant. We generalize in particular the notion of group of the walk introduced by Bousquet-Mélou and Mishna for small steps walk to the large steps framework. This allows to develop algorithms and criteria to test the existence of invariants and decoupling functions. This is a collaboration with Pierre Bonnet (Labri).
11:00-12:00 Gleb Pogudin
Quadratizations of differential equations
Abstract. Quadratization problem is, given a system of ODEs with polynomial right-hand side, transform the system to a system with quadratic right-hand side by introducing new variables. Such transformations have been used, for example, as a preprocessing step by model order reduction methods and for transforming chemical reaction networks. We will present a recent algorithm for computing such transformations and its extensions including systems with control and of varying dimension. The talk is based on joint works with Andrey Bychkov, Opal Issan, and Boris Kramer.
12:00-15:00 Lunch break
Chair: Pierre Lairez
15:00-16:00 Stephen Melczer
New Software for Analytic Combinatorics
Abstract. This talk surveys some recently developed software for analytic combinatorics, including an extension to the Sage ore_algebra package for the asymptotics of P-recursive sequences with explicit error terms (used for certifying sequence positivity), and the new sage_acsv package for rigorous multivariate asymptotics using the tools of Analytic Combinatorics in Several Variables (ACSV).
16:00-16:30 Coffee break
16:30-17:30 Mark van Hoeij
Submodule approach to creative telescoping
Abstract. This talk proposes ideas to speed up the process of creative telescoping, particularly when the telescoper is reducible. One can interpret telescoping as computing an annihilator $L$ in $D$ for an element $H$ in a D-module $M$. The main idea is to look for submodules of $M$. For a non-trivial submodule $N$, constructing the minimal operator $R$ of the image of $H$ in $M/N$ gives a right-factor of $L$ in $D$. Then $L = L' R$ where $L'$ is the telescoper of $R(H)$. To expedite computing $L'$, compute the action of $D$ on a natural basis of $N$, then obtain the telescoper $L'$ for $R(H)$ with a cyclic vector computation. The next main idea is that when $N$ has automorphisms, use them to construct submodules. An automorphism with distinct eigenvalues can be used to decompose $N$ as a direct sum of submodules $N_1, \ldots, N_k$. Then $L' = \text{LCLM}(L_1, \ldots, L_k)$ where $L_i$ is the telescoper of the projection of $R(H)$ on $N_i$. An LCLM can greatly increase the degrees of the coefficients, so $L'$ and hence $L$ can be much larger than the factors $L_1, \ldots, L_k$ and $R$. Examples show that computing each factor $L_i$ and $R$ separately can save a lot of CPU time compared to computing the full telescoper $L$ all at once with standard creative telescoping.
Slides   Maple demo
    Wednesday December 6th, 2023
9:30-10:00 Welcome coffee
Chair: Jérémie Bouttier
10:00-11:00 Alan Sokal
Some problems I’d like solved, from a user of computer algebra
Abstract. A matrix $M$ of real numbers is called {\em totally positive}\/ if every minor of $M$ is nonnegative. Gantmakher and Krein showed in 1937 that a Hankel matrix $H = (a_{i+j})_{i,j \ge 0}$ of real numbers is totally positive if and only if the underlying sequence $(a_n)_{n \ge 0}$ is a Stieltjes moment sequence, i.e.~the moments of a positive measure on $[0,\infty)$. Moreover, this holds if and only if the ordinary generating function $\sum_{n=0}^\infty a_n t^n$ can be expanded as a Stieltjes-type continued fraction with nonnegative coefficients. So totally positive Hankel matrices are closely connected with the Stieltjes moment problem and with continued fractions. Here I will introduce a generalization: a matrix $M$ of polynomials (in some set of indeterminates) will be called {\em coefficientwise totally positive}\/ if every minor of $M$ is a polynomial with nonnegative coefficients. And a sequence $(a_n)_{n \ge 0}$ of polynomials will be called {\em coefficientwise Hankel-totally positive}\/ if the Hankel matrix $H = (a_{i+j})_{i,j \ge 0}$ associated to $(a_n)$ is coefficientwise totally positive. It turns out that many sequences of polynomials arising naturally in enumerative combinatorics are (empirically) coefficientwise Hankel-totally positive. In some cases this can be proven using continued fractions, by either combinatorial or algebraic methods; in other cases this can be done using a more general algebraic method called {\em production matrices}\/. However, in a very large number of other cases it remains an open problem. Along the way I will mention some problems in computer algebra, the solution of which would be helpful to this research.
11:00-12:00 Pierre Vanhove
Efficient algorithms for differential equations satisfied by Feynman integrals
Abstract. Feynman integrals are a type of mathematical function that are important for precision measurements in physics. They are notoriously difficult to evaluate, and a lot of effort has been devoted to developing efficient analytic and numerical methods for doing so. In this talk, we will present a new algorithm for determining the minimal order Picard-Fuchs operator associated with a given Feynman integral. This operator is a differential operator that governs the analytic behavior of the Feynman integral. We will first discuss an implementation of the Griffiths-Dwork algorithm for the case of Feynman integrals in integer spacetime dimension. In that case, the integrand of the Feynman integral is a rational differential form to which the Griffiths-Dwork reduction is applied for determining the Picard-Fuchs operator. We will then extend this algorithm to the case of generic spacetime dimension. In this case, one needs to consider twisted cohomology. We will show how the knowledge of the Picard-Fuchs operator can be deduced by Hodge theoretic considerations on the variation of the mixed Hodge structure associated to the Feynman integral. This talk is based on work with Pierre Lairez, Eric Pichon-Pharabod, Charles Doran, and Andrew Harder.
Free afternoon
18:30 Reception. Emmy Noether reception room located at the second floor of the Perrin building (IHP). We'll need to have a precise list of participants at the entrance to the building. If you were not registered before December or if you have any doubts, please register or contact the organizers.
    Thursday December 7th, 2023
    Special Day, joint with the Flajolet Seminar
9:30-10:00 Welcome coffee
Chair: Frédérique Bassino
10:00-11:00 Mireille Bousquet-Mélou
Computer algebra in my combinatorics life
Abstract. Many of my papers would just not exist without computer algebra. I will describe how CA has become an essential tool in my research in enumerative combinatorics. The point of view will be that of a (sometimes naive) user, not of an expert. Many examples and questions will be taken from a joint paper with Michael Wallner dealing with the enumeration of king walks avoiding a quadrant (arXiv 2021, to appear). My hope is that some of the questions that I will raise will have an immediate answer ("yes, this is done") and/or that some people in the audience will find a question interesting enough to take it back home.
11:00-12:00 Tony Guttmann
Self-avoiding walks in a square and the gerrymander sequence
Abstract. We give an improved algorithm for the enumeration of self-avoiding walks and polygons within an $N \times N$ square as well as SAWs crossing a square. We present some proofs of the expected asymptotic behaviour as the size $N$ of the square grows, and then show how one can numerically estimate the parameters in the asymptotic expression. We then show how the improved algorithm can be adapted to count gerrymander sequences (OEIS A348456), and prove that the asymptotics of the gerrymander sequence is similar to that of SAWs crossing a square. This work has been done in collaboration with Iwan Jensen, and in part with Aleks Owczarek.
12:00 Group photo (1)   Group photo (2)
12:00-15:00 Lunch break
Chair: Guillaume Chapuy
15:00-16:00 Arvind Ayyer
Computer algebra for the study of two-dimensional exclusion processes
Abstract. We define a new disordered asymmetric simple exclusion process (ASEP) with two species of particles, first-class and second-class, on a two-dimensional toroidal lattice. The dynamics is controlled by first-class particles, which only move horizontally, with forward and backward hopping rates $p_i$ and $q_i$ respectively if the particle is on row $i$. The motion of second-class particles depends on the relative position of these with respect to the first-class ones, and can be both horizontal and vertical. In the first part of my talk, I will illustrate how we used computer algebra software, specifically Mathematica and SageMath, to understand the stationary distribution of this process. We computed the partition function, as well as densities and currents of all particles in the steady state. We observed a novel mechanism we call the Scott Russell phenomenon: the current of second class particles in the vertical direction is the same as that of first-class particles in the horizontal direction. In the second part of my talk, I will show how we simulated the process and realized that the Scott Russell phenomenon also holds out of equilibrium. This is partly joint work with P. Nadeau (European Journal of Combinatorics, 2022).
Slides   Demo
16:00-16:30 Coffee break
16:30-17:30 Dan Romik
A new proof of Viazovska's modular form inequalities for sphere packing in dimension 8
Maryna Viazovska in 2016 found a remarkable application of the theory of modular forms to a fundamental problem in geometry, obtaining a solution to the sphere packing problem in dimension 8 through an explicit construction of a so-called "magic function" that she defined in terms of classical functions, the Eisenstein series and Jacobi thetanull functions. The same method also led shortly afterwards to the solution of the sphere packing in dimension 24 by her and several collaborators. One component of Viazovska's proof consisted of proving a pair of inequalities satisfied by the modular forms she constructed. Viazovska gave a proof of these inequalities that relied in an essential way on computer calculations. In this talk I will present a new proof of Viazovska's inequalities that uses only elementary arguments that can be easily checked by a human.
    Friday December 8th, 2023
9:30-10:00 Welcome coffee
Chair: Jean-Marie Maillard
10:00-11:00 Jehanne Dousse
Partition identities, functional equations and computer algebra
A partition of a positive integer $n$ is a non-increasing sequence of positive integers whose sum is $n$. A partition identity is a theorem stating that for all $n$, the number of partitions of $n$ satisfying some conditions equals the number of partitions of $n$ satisfying some other conditions. In this talk, we will show how functional equations and computer algebra can be used to prove such identities. In particular we will discuss a semi-automatic method using recurrences and $q$-difference equations, and what would be needed to make it fully automatic.
11:00-12:00 Nicholas Witte
Beyond Painlevé: The need for computational tools to reveal hidden structure
Abstract. The simplest examples of integrability in mathematical physics - spectral distributions of fundamental random matrix ensembles or the diagonal spin-spin correlations of the square lattice Ising model - to give just two examples, reveal the importance and practical utility of the six Painlevé equations in our understanding of these models. Few aspects of this understanding escape the presence of these equations, whether it is the application of Riemann-Hilbert methods to the asymptotic limits as matrix ranks or spin separations tend to infinity or the relationships inherited from the affine Weyl group symmetries of the Painlevé equations. This understanding operates in both directions: fundamental understanding of the Painlevé equations provides the most powerful and rigorous tools to characterise a variety of statistics applied to the models, and these applications are driving and motivating a lot of studies into the pure mathematics at the core of these equations. However today we coming up against numerous examples where one can pose questions just outside the simplest models: e.g. the singular value distribution of a product of two Ginibre random matrices, or the diagonal correlations of the triangular Ising model or even the off-diagonal correlations of the square lattice model, and one is beyond the six Painlevé set or even the discrete Sakai scheme. Integrability is still present and some of this territory - the Garnier, Fuji-Suzuki, Sasano and matrix-Painlevé systems - has been sketched out but there are gaps in our understanding and our tool-box is missing critical tools that one needs. In some senses the complexity has grown and it is often impractical to do hand-calculations and when computer-assisted systems are employed our best results so far cannot be analysed by hand. There are hints that simplicity is achievable yet the standard computer assisted algorithms do not find them. So the challenge is to develop some flexible, model-adapted algorithms for doing what are essentially algebraic geometry calculations. A number of examples, including those mentioned previously, will illustrate this state of affairs.
End of the workshop

Special week

November 27 to December 1, 2023 (Amphitheater Hermite)

Topical day: Elimination for Functional Equations

December 11, 2023 (Amphitheater Darboux)

Organizer: G. Pogudin

Speakers: Hadrien Notarantonio, André Platzer, Daniel Robertz, Sonia Rueda, Alexandros Singh, Nathalie Verdière


Code of Conduct