We use a novel decomposition to create succinct data structures – supporting a wide range of operations on static trees in constant time – for a variety tree classes, extending results of Munro, Nicholson, Benkner, and Wild. Motivated by the class of AVL trees, we further derive asymptotics for the information-theoretic lower bound on the number of bits needed to store tree classes whose generating functions satisfy certain functional equations. In particular, we prove that AVL trees require approximately 0.938 bits per node to encode.

Analytic combinatorics in several variables is a branch of mathematics that deals with deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We study information-theoretic questions about sequences in a discrete noiseless channel under cost constraints. Our main contributions involve the relationship between the graph structure of the channel and the singularities of the bivariate generating function whose coefficients are the number of sequences satisfying the constraints. We use these new results to invoke theorems from multivariate analytic combinatorics to obtain the asymptotic behavior of the number of cost-limited strings that are admissible by the channel. This builds a new bridge between analytic combinatorics in several variables and labeled weighted graphs, bringing a new perspective and a set of powerful results to the literature of cost-constrained channels. Along the way, we show that the cost-constrained channel capacity is determined by a cost-dependent singularity of the bivariate generating function, generalizing Shannon’s classical result for unconstrained capacity, and provide a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity.

Analytic combinatorics in several variables (ACSV) is a powerful tool for deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We use ACSV to derive the first-order sub-exponential asymptotics of sequences generated by a discrete noiseless channel under an average cost constraint. As a by-product of the analysis, we obtain a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity.

We consider the number of partitions of $n$ whose Young diagrams fit inside an $m \times \ell$ rectangle; equivalently, we study the coefficients of the $q$-binomial coefficient $\binom{m+\ell}{m}_q$. We obtain sharp asymptotics throughout the regime $\ell = \Theta (m)$ and $n = \Theta (m^2)$, while previously sharp asymptotics were derived by Takács [ J. Statist. Plann. Inference, 14 (1986), pp. 123--142] only in the regime where $|n - \ell m /2| = O(\sqrt{\ell m (\ell + m)})$ using a local central limit theorem. Our approach is to solve a related large deviation problem: we describe the tilted measure that produces configurations whose bounding rectangle has the given aspect ratio and is filled to the given proportion. Our results are sufficiently sharp to yield the first asymptotic estimates on the consecutive differences of these numbers when $n$ is increased by one and $m, \ell$ remain the same, hence significantly refining Sylvester's unimodality theorem and giving effective asymptotic estimates for related Kronecker and plethysm coefficients from representation theory.

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear mappings, called untangling and \emphtangling by those authors, that arise in the context of computations with univariate polynomials. We give a slightly faster tangling algorithm and discuss new applications of these techniques. We show how to extend these ideas to bivariate settings, and use them to give bounds on the arithmetic complexity of certain algebras.

We consider the enumeration of walks on the nonnegative lattice $\mathbb{N}^{d},$ with steps defined by a set $\mathcal{S}\subset \{-1, 0, 1\}^d\backslash\{{0}\}$. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps $\mathcal{S}$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions having nonsmooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of ACSV. One application is a closed form for asymptotics of models defined by step sets that are symmetric over all but one axis. As a special case, we apply our results when $d=2$ to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given.

The field of analytic combinatorics, which studies the asymptotic behaviour of sequences through analytic properties of their generating functions, has led to the development of deep and powerful tools with applications across mathematics and the natural sciences. In addition to the now classical univariate theory, recent work in the study of analytic combinatorics in several variables (ACSV) has shown how to derive asymptotics for the coefficients of certain D-finite functions represented by diagonals of multivariate rational functions. We give a pedagogical introduction to the methods of ACSV from a computer algebra viewpoint, developing rigorous algorithms and giving the first complexity results in this area under conditions which are broadly satisfied. Furthermore, we give several new applications of ACSV to the enumeration of lattice walks restricted to certain regions. In addition to proving several open conjectures on the asymptotics of such walks, a detailed study of lattice walk models with weighted steps is undertaken.

Analytic combinatorics studies the asymptotic behavior of sequences through the analytic properties of their generating functions. This article provides effective algorithms required for the study of analytic combinatorics in several variables, together with their complexity analyses. Given a multivariate rational function we show how to compute its smooth isolated critical points, with respect to a polynomial map encoding asymptotic behaviour, in complexity singly exponential in the degree of its denominator. We introduce a numerical Kronecker representation for solutions of polynomial systems with rational coefficients and show that it can be used to decide several properties (0 coordinate, equal coordinates, sign conditions for real solutions, and vanishing of a polynomial) in good bit complexity. Among the critical points, those that are minimal---a property governed by inequalities on the moduli of the coordinates---typically determine the dominant asymptotics of the diagonal coefficient sequence. When the Taylor expansion at the origin has all non-negative coefficients (known as the 'combinatorial case') and under regularity conditions, we utilize this Kronecker representation to determine probabilistically the minimal critical points in complexity singly exponential in the degree of the denominator, with good control over the exponent in the bit complexity estimate. Generically in the combinatorial case, this allows one to automatically and rigorously determine asymptotics for the diagonal coefficient sequence. Examples obtained with a preliminary implementation show the wide applicability of this approach.