Schedule for: 17w5090 - Lattice walks at the Interface of Algebra, Analysis and Combinatorics

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

The field of computer algebra can be divided into several mutually related subfields. Some of these are more relevant to combinatorialists than others, but we believe that there are some which should be known better. Therefore, for this overview talk, we have decided not only to discuss the most natural topics forming the subfield sometimes called symbolic combinatorics (featuring algorithms for recurrences and differential equations) but also discuss some of the techniques belonging to two other subfields that may be less known: exact arithmetic (with fast multiplication and working with homomorphic images) and Groebner basis (with techniques for reasoning about polynomial ideals). These topics are at the heart of computer algebra, and we believe that it will be handy for a computationally oriented combinatorialist to know about them.

The kernel method has become one of the standard tools for solving lattice path enumeration problems. I will start by introducing the method in the context of constrained 1-dimensional random walks and simple polymer models. When we move up to 2 dimensions, the generating functions of random walk models can display a very broad range of analytic properties. In this context the kernel method becomes much richer and I will demonstrate a few of the ways in which it may be applied. Along the way I will give a few "warm-up" exercises and finish with a few open problems concerning more interacting boundary conditions.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

When studying special functions of the complex variable, one would like to determine whether a function is algebraic over the field of rational functions or not. To refine this classification, one could also be interested in the differential dependence of the function. Starting from the holonomic or D-finite functions, that is the ones that satisfy a linear differential equation, we consider a new class of complexity, called differential transcendence, that corresponds to the functions that do not satisfy a polynomial relation with their derivatives. A celebrated example is the Gamma function, which is differentially transcendental by a result of Hölder. When the special function is given by a linear functional equation, the difference Galois theory provides powerful and systematic tools that allows to determine such kind of relations. In this talk, I will try to give an overview of this Galois theory by focusing on examples and applications.

In this lecture we will focus on techniques coming from probability theory and analysis to study models of walks confined to multidimensional cones, with arbitrary big steps and possibly with weights. To give an example of the fruitful interaction between the above domains, we will restrict our attention to the computation of critical exponents which appear in the asymptotic behavior of confined walks. For instance, what is the asymptotic behavior of the number of excursions, i.e., of the number of walks starting and ending at given points, remaining in a fixed cone, as the number of steps goes to infinity ? In a first part, using an approximation of random walks by Brownian motion, we will present the seminal work of Denisov and Wachtel providing a solution to the above problem in the case of excursions. We shall also present partial results and conjectures related to the total number of walks confined to a cone. We will show new results concerning the non-D-finiteness of some series counting walks in the quarter plane. In a second part we shall be interested in discrete harmonic functions in cones. The generating function of these harmonic functions satisfies a functional equation, which happens to be closely related to the well-known functional equation that appears in the context of enumeration of confined walks. We shall explain the link between these harmonic functions and a one-parameter family of conformal mappings. These harmonic functions provide a second way to compute the critical exponents. We will present several conjectures.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

TBA

Given a sequence represented by a linear recurrence with polynomial coefficients and sufficiently many initial terms, a natural question is whether the transcendence of its generating function can be decided algorithmically. The question is non trivial even for sequences satisfying a recurrence of first order. An algorithm due to Michael Singer is sufficient, in principle, to answer the general case. However, this algorithm suffers from too high a complexity to be effective in practice. We will present a recent method that we have used to treat a non-trivial combinatorial example. It reduces the question of transcendence to a (structured) linear algebra problem.

Creative telescoping is a powerful technique to tackle summation and integration problems symbolically, but it can be computationally very costly. Many existing algorithms compute two objects, called telescoper and certificate, but in many applications only the first one is of interest, while typically the second one is larger in size. In the past few years a new direction of research was initiated, namely to develop creative telescoping algorithms that are based on Hermite-type reductions, which avoid the computation of the certificate and therefore can be more efficient in practice. In our 2016 ISSAC paper, we have developed an algorithm for constructing minimal-order telescopers for algebraic functions, based on Trager's reduction and on a so-called polynomial reduction. Later we have extended this algorithm to fuchsian D-finite functions. This is joint work with Shaoshi Chen, Mark van Hoeij, and Manuel Kauers.

This talk focusses on the interaction between the kernel method, a powerful collection of techniques used extensively in the enumeration of lattice walks in restricted regions, and the relatively new field of analytic combinatorics in several variables (ACSV). In particular, the kernel method often allows one to write the generating function for the number of lattice walks restricted to certain regions as the diagonal of an explicit multivariate rational function, which can then be analyzed using the methods of ACSV. This pairing is powerful and flexible, allowing for results which can be generalized to high (or even arbitrary) dimensions, weighted step sets, and the enumeration of walks returning to certain boundary regions of the domains under consideration. Several problems will be discussed, including joint work with Alin Bostan, Mireille Bousquet-Mélou, Julien Courtiel, Marni Mishna, Kilian Raschel, and Mark Wilson.

A very rich interplay between arithmetic, geometry, transcendence and combinatorics arises in the study of homogeneous linear differential equations and especially of those that “come from geometry” and the related study of Siegel G-functions. A remarkable result is that, by adding variables, we can see many transcendental G-functions (and thus many generating series) as arising in a natural way from much more elementary function, namely rational functions. This process, called diagonalization, can be thought of as a formal integration. I will discuss some properties enjoy by diagonals of rational functions and connect them with Lucas'congruences for binomial coefficients and algebraic independence of power series. This corresponds to some joint works with Jason Bell and Eric Delaygue.

Let $K$ be a field of characteristic zero and let $G$ be a finitely generated subgroup of $K^*$. Given a $P$-recursive sequence $f(n)$ taking values in $K$, we study the problem of when $f(n)$ takes values in $G$. We show that this problem can be interpreted purely dynamically and, when one does so, one can prove a much more general result about algebraic dynamical systems. Using this framework, we can then show that the set of $n$ for which $f(n)\in G$ is a finite union of infinite arithmetic progressions along with a set of zero Banach density, which simultaneously generalizes a result of Methfessel and a separate result due to Bezivin.

A D-finite power series satisfies a system of linear partial differential equations with polynomial coefficients of special type. This class of power series has been systematically investigated by Stanley in his book Enumerative Combinatorics (Volume II). We prove that a multivariate D-finite power series with coefficients from a finite set is rational. This generalizes a rationality theorem of van der Poorten and Shparlinski in 1996. As an application, we will show how this result can be used to study the nonnegative integer points on algebraic varieties. This is a joint work with Jason P. Bell.

We find a formula for the asymptotics of the coefficients of a generating function of the form, $H(z_1, z_1, ..., z_d)^{-\beta}$, as the indices approach infinity in a fixed ratio. Then, we look at how this formula can be applied to generating functions that enumerate the possible structures into which RNA sequences can fold. This work relies on the techniques in multivariate analytic combinatorics developed by Pemantle and Wilson. We combine the multivariate Cauchy integral formula with explicit contour deformations to compute the asymptotic formula. A challenge of using the formula is correctly identifying the points which contribute to asymptotics.

Participants are welcome to present open problems.

A method will be described to determine generating functions for certain classes of simple walks on the square lattice, while keeping track of their winding angle around the origin. Together with a reflection principle the method can be used to count certain simple walks in wedges of various opening angles, and this is shown to lead in particular to a new proof of the counting of Gessel excursions. If time permits, I'll discuss a connection with the enumeration of planar maps and O(n) loop models.

I will discuss proofs of the algebraicity of generating functions for walks on the half-line with an arbitrary set of integer steps, with emphasis on Paul Monsky's approach that reduces the problem to the case of Motzkin walks with noncommuting weights.

Several combinatorial objects (including several types of random walks) have a recursive combinatorial description that leads to a (system of) functional equation(s) for the corresponding counting generating function, where the right hand side of the equation has non-negative coefficients; sometimes there also appears a catalytic variable, for example for random walks restricted to some region or for the enumeration of planar maps. The purpose of this talk to show that the positivity condition leads to universal asymptotic properties of the underlying counting problem.

Assigning weights to steps is a natural way to extend the usual questions that concern lattice walks enumeration, like finding asymptotic estimates or the D-finiteness of the generating function. The assignments of weights we consider in this talk are not arbitrary, but still give enough generalization to cover all sorts of behavior. More precisely, we are going to introduce what we call central weightings, namely an assignment of weights such that all paths with the same start point, end point, and length, share the same weight. After explaining why central weighting constitute a "good" study framework for lattice walks enumeration, we present some conjectures about these central weightings, which may require your help. This is a joint work with Steve Melczer, Marni Mishna, and Kilian Raschel.

In the recent years, the nature of the generating series of the walks in the quarter plane has attracted the attention of many authors. The main questions are: are they algebraic, holonomic (solutions of linear differential equations) or at least hyperalgebraic (solutions of algebraic differential equations)?

I will describe an algorithm (implemented in Maple) that produces a system of generators of the Lie algebra of an absolutely irreducible linear differential equation over the rational functions with complex coefficients. This is a joint work with M. Barkatou, T. Cuzeau et J.-A. Weil.

In this talk, we consider the simple walk ($\textit{i.e.}$ walk with a set of steps {$\mathcal{S}=\{\text{W, N, E, S}\}$}) in the lattice plane. We constrain the walk to avoid the negative quadrant. The objective is to compute the number of paths $c(i,j;n)$ of length $n$, starting at $(0,0)$ and ending at $(i,j)$, with $\left(i\geq 0 \text{ or } j\geq 0\right)$ and $n\geq 0$. A way to achieve this goal is to cut the three quarters of the plane into two convex symmetric parts which will be three octants of the plane.

We will survey a series of intriguing conjectures about log-concavity and t-stack sortable permutations, as well as some recent enumeration results. Connections to lattice paths and labeled plan trees will also be discussed.

We study the enumeration of three friendly directed walks on the square lattice. We show how one can count different types of shared sites (interactions) by solving the associated functional equations using the obstinate kernel method. However, we also highlight that the introduction of finer counting problems that introduce asymmetry can lead to as yet unsolvable functional equations. We survey related results over the past few years counting extra features in multiple path problems.

Inspired by the paper of Bonichon, Bousquet-M\'elou, Dorbec and Pennarun, we give a system of functional equations for the ogfs for the number of planar Eulerian orientations counted by the edges, $U(x),$ and the number of 4-valent planar Eulerian orientations counted by the number of vertices, $A(x)$. The latter problem is equivalent to the 6-vertex problem on a random lattice, widely studied in mathematical physics. While unable to solve these functional equations, they immediately provide polynomial-time algorithms for the coefficients of the generating function. From these algorithms we have obtained 100 terms for $U(x)$ and 90 terms for $A(x).$ Analysis of these series suggests that they both behave as $ \cdot (1 - \mu x)^2/\log(1 - \mu x),$ where we make the confident conjectures that $\mu = 4\pi$ for Eulerian orientations counted by edges and $\mu=4\sqrt{3}\pi$ for 4-valent Eulerian orientations counted by vertices. (Joint work with Andrew Elvey Price).

We introduce a deformed version of Dyck paths (DDP), where additional to the steps allowed for Dyck paths, ‘jumps’ orthogonal to the preferred direction of the path are permitted. We consider the generating function of DDP, weighted with respect to their half length, area and number of jumps. This represents the first example of a hierarchy of exactly solvable two-dimensional lattice vesicle models showing higher-order multi-critical points with scaling functions expressible via generalized Airy functions, as conjectured by John Cardy.

I will give a broad review of classes of integer sequences arising in combinatorics. Beside the more traditional asymptotic results, I will also emphasize the complexity aspects. Many examples will be presented. Some recent results will be mentioned as well.

I shall present a curious factorisation theorem for the number of rhombus tilings of a hexagon with vertical and horizontal symmetry axis, with triangular holes along the latter axis. Its proof is essentially based on (non-intersecting) lattice paths. This is joint work with Mihai Ciucu.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.