Back to search

University of Waterloo

Algorithms for Analytic Combinatorics: Positivity Bounds and D-finite Operators

Abstract

dc:description.abstract

Analytic combinatorics is concerned with describing limiting behavior of families of combinatorial structures. While this is well-studied in the univariate case, the last two decades have seen the development of analytic combinatorics in several variables (ACSV) treating the same problem in the multivariate case. One advantage of the way ACSV is formulated is that, at least in the simplest cases, its methods are amenable to explicit computation. This thesis contributes to an ongoing effort to automate the results of ACSV by providing developments in two related areas: computing D-finite operators for diagonals of rational functions, and computing explicit error bounds for ACSV in the so-called smooth rational case. First, we provide a SageMath implementation of an algorithm of Lairez for computing periods of rational integrals. Since diagonals of rational functions are rational periods, computing operators of periods is of great importance to practitioners of algebraic and analytic combinatorics. While Lairez gave a MAGMA implementation of his algorithm, our implementation provides full-fledged documentation, robustness, and feature enhancements aimed at combinatorialists -- such as computing diagonal operators for arbitrary directions. Second, we discuss how to find explicit error bounds for asymptotics of rational diagonals, as opposed to the Big-O asymptotics typically provided by ACSV. One motivation for this is the coefficient positivity problem; having explicit bounds allows one to reduce positivity of coefficient sequences to checking asymptotic positivity and finitely many initial sequence terms. We provide fully constructive versions of ACSV arguments in the simplest case, then use these to derive an index N so that positivity of our asymptotic implies positivity of our diagonal for all larger index values, under some small additional assumptions about the form of our asymptotic. We then explore the consequences and caveats of this reduction, exhibiting some classes of functions where asymptotic positivity can be known a priori.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Smith, John

Subjects

dc:subject × 27

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/24017

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Smith, John. Algorithms for Analytic Combinatorics: Positivity Bounds and D-finite Operators. University of Waterloo, 2026. https://hdl.handle.net/10012/24017