Please note: This master’s thesis presentation will take place in DC 2306C and online.
John Smith, Master’s candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Stephen Melczer & Rafael Oliveira
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 Sage Math 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 constructivized 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 n larger than N. We then explore the consequences and caveats of this reduction, exhibiting some classes of functions where asymptotic positivity can be known a priori.
To attend this master’s thesis presentation in person, please go to DC 2306C. You can also attend virtually on Zoom