10:00am - 12:00pmSymbolic Combinatorics
Chair(s): Shaoshi Chen (Chinese Academy of Sciences), Manuel Kauers (Johannes Kepler University, Linz, Austria), Stephen Melczer (University of Pennsylvania)
In recent years algorithms and software have been developed that allow researchers to discover and verify combinatorial identities as well as understand analytic and algebraic properties of generating functions. The interaction of combinatorics and symbolic computation has had a beneficial impact on both fields. This minisymposium will feature 12 speakers describing recent research combining these areas.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Mahlerian analogues of Riccati equations and proofs of hypertranscendence
Frederic Chyzak
INRIA
A Mahler function~$f(x)$ is a function whose evaluations at iterated $b$th powers of the variable, $f(x)$, $f(x^b)$, $f(x^{b^2})$, $f(x^{b^3})$, etc, are linearly dependent. The interest in them was recently renewed, when a difference-Galois-theoretic approach was developed to determine whether a Mahler function is hypertranscendental, that is, whether $f(x)$~and all its derivatives are algebraically independent. For Mahler functions defined by a linear equation of order~2, a criterion was given by Dreyfus, Hardouin, and Roques: $f(x)$~is hypertranscendental if and only if two auxiliary non-linear equations have no rational solutions. These equations are Mahlerian analogues of Riccati equations, as they encode the right-hand factors of corresponding linear Mahler equations. I will present preliminary results of a joint work with Dreyfus, Dumas, and Mezzarobba in which we develop an algorithm to solve Riccati equations for their rational solutions.
Walk in the quarter plain and differential Galois theory
Thomas Dreyfus
Université de Strasbourg
The determination of the nature of the generating series of walks in the quarter plain is a very vivid topic. Recently, differential Galois theory gave tools to understand what are the algebraic and differential equations satisfied by the latter. In practice, we are reduced to determine whether a telescoper relation exists or not. The latter problem may be treated with computer algebra in many situation.
Systems of equations for sets of permutations and limit shapes
Valentin FĂ©ray
Universitaet Zuerich
Enumerating and analyzing sets of permutations avoiding some patterns (permutation classes) is a standard question in enumerative combinatorics. One method is to use the so-called substitution operation to decompose recursively the objects: in particular, when the permutation class contains finitely many indecomposable permutations (called simple permutations), one can obtain in an automatic way a system of combinatorial equations describing the class. This system allows to sample large uniform permutation in the class and to try and describe their limit shape. We will explain how this limit shape is related to combinatorial and analytic properties of the system.
Joint work with Frédérique Bassino (Paris-Nord), Mathilde Bouvel (Zurich), Lucas Gerin (École Polytechnique), Mickaël Maazoun (ENS Lyon) and Adeline Pierrot (Orsay).
The location of variables in lambda-terms with bounded De Bruijn levels
Bernhard Gittenberger
TU Wien
We consider lambda-terms with a bounded number of De Bruijn levels, say bounded by $k$, and are interested in the shape of such a term, if it is chosen uniformly at random from all such terms of a given size. The number of such terms of given is known asymptotically, and moreover that the asymptotic expression behave in a very strange way: The subexponential term in the asymptotics is different if $k$ belongs to a certain doubly exponentially growing sequence. It is conjectured that the reason lies in the distribution of the variables within a term.
Under some technical condition we first show that the number of variables is asymptotically normally distributed with mean and variance asymptotically proportional to the size. Then, we investigate the number of variables in the different De Bruijn levels and thereby exhibit a so-called ``unary profile'' of a random lambda term. It turns out that almost all the variables are located in the last De Bruijn levels and the number of these levels is proportional to $loglog k$.
This is joint work with Isabella Larcher.