This book uses new mathematical tools to examine broad computability and complexity questions in enumerative combinatorics, with applications to other areas of mathematics, theoretical computer science, and physics. A focus on effective algorithms leads to the development of computer algebra software of use to researchers in these domains. After a survey of current results and open problems on decidability in enumerative combinatorics, the text shows how the cutting edge of this research is the new domain of Analytic Combinatorics in Several Variables (ACSV). The remaining chapters of the text alternate between a pedagogical development of the theory, applications (including the resolution by this author of conjectures in lattice path enumeration which resisted several other approaches), and the development of algorithms. The final chapters in the text show, through examples and general theory, how results from stratified Morse theory can help refine some of these computability questions. Complementing the written presentation are over 50 worksheets for the SageMath and Maple computer algebra systems working through examples in the text.
Author(s): Stephen Melczer
Series: Texts & Monographs in Symbolic Computation
Publisher: Springer
Year: 2021
Language: English
Pages: 300
City: Cham
Foreword
Preface
Contents
List of Symbols
Chapter 1 Introduction
1.1 Algorithmic Combinatorics
1.1.1 Analytic Methods for Asymptotics
1.1.2 Lattice Path Enumeration
1.2 Diagonals and Analytic Combinatorics in Several Variables
1.2.1 The Basics of Analytic Combinatorics in Several Variables
1.2.2 A History of Analytic Combinatorics in Several Variables
1.3 Organization
References
Part I Background and Motivation
Chapter 2 Generating Functions and Analytic Combinatorics
2.1 Analytic Combinatorics in One Variable
2.1.1 AWorked Example: Alternating Permutations
2.1.2 The Principles of Analytic Combinatorics
2.1.3 The Practice of Analytic Combinatorics
2.2 Rational Power Series
2.3 Algebraic Power Series
2.4 D-Finite Power Series
2.4.1 An Open Connection Problem
2.5 D-Algebraic Power Series
Appendix on Complex Analysis
Problems
References
Chapter 3 Multivariate Series and Diagonals
3.1 Complex Analysis in Several Variables
3.1.1 Singular Sets of Multivariate Functions
3.1.2 Domains of Convergence for Multivariate Power Series
3.2 Diagonals
3.2.1 Properties of Diagonals
3.2.2 Representing Series Using Diagonals
3.3 Multivariate Laurent Expansions and Other Series Operators
3.3.1 Convergent Laurent Series and Amoebas
3.3.2 Diagonals and Non-Negative Extractions of Laurent Series
3.4 Sources of Rational Diagonals
3.4.1 Binomial Sums
3.4.2 Irrational Tilings
3.4.3 Period Integrals
3.4.4 Kronecker Coefficients
3.4.5 Positivity Results and Special Functions
3.4.6 The Ising Model and Algebraic Diagonals
3.4.7 Other Sources of Examples
Problems
References
Chapter 4 Lattice Path Enumeration, the Kernel Method, and Diagonals
4.1 Walks in Cones and The Kernel Method
4.1.1 Unrestricted Walks
4.1.2 A Deeper Kernel Analysis: One-Dimensional Excursions
4.1.3 Walks in a Half-Space
4.1.4 Walks in the Quarter-plane
4.1.5 OrthantWalks Whose Step Sets Have Symmetries
4.2 Historical Perspective
4.2.1 The Kernel Method
4.2.2 Recent History of Lattice Paths in Orthants
Problems
References
Part II Smooth ACSV and Applications
Chapter 5 The Theory of ACSV for Smooth Points
5.1 Central Binomial Coefficient Asymptotics
5.1.1 Asymptotics in General Directions
5.1.2 Asymptotics of Laurent Coefficients
5.2 The Theory of Smooth ACSV
5.3 The Practice of Smooth ACSV
5.3.1 Existence of Minimal Critical Points
5.3.2 Dealing with Minimal Points that are not Critical
5.3.3 Perturbations of Direction and a Central Limit Theorem
5.3.4 Genericity of Assumptions
Problems
References
Chapter 6 Application: Lattice Walks and Smooth ACSV
6.1 Asymptotics of Highly Symmetric Orthant Walks
6.1.1 Asymptotics for All Walks in an Orthant
6.1.2 Asymptotics for Boundary Returns
6.1.3 Parameterizing the Starting Point
Problems
References
Chapter 7 Automated Analytic Combinatorics
7.1 An Overview of Results and Computations
7.1.1 Surveying the Computations
7.1.2 Minimal Critical Points in the Combinatorial Case
7.1.3 Minimal Critical Points in the General Case
7.2 ACSV Algorithms and Examples
7.2.1 Examples
7.3 Data Structures for Polynomial System Solving
7.3.1 Gröbner Bases and Triangular Systems
7.3.2 Univariate Representations
7.4 Algorithmic ACSV Correctness and Complexity
7.4.1 Polynomial Height Bounds
7.4.2 Polynomial Root Bounds
7.4.3 Resultant and GCD Bounds
7.4.4 Algorithms for Polynomial Solving and Evaluation
Problems
References
Part III Non-Smooth ACSV
Chapter 8 Beyond Smooth Points: Poles on a Hyperplane Arrangement
8.1 Setup and Definitions
8.2 Asymptotics in Generic Directions
8.2.1 Step 1: Express the Cauchy Integral as Sum of Imaginary Fibers
8.2.2 Step 2: Determine the Contributing Singularities
8.2.3 Step 3: Express the Cauchy Integral as Sum of Local Contributing Integrals
8.2.4 Step 4: Compute Residues
8.2.5 Step 5: Determine Asymptotics
8.2.6 Dealing with Non-Simple Arrangements
8.3 Asymptotics in Non-Generic Directions
Problems
References
Chapter 9 Multiple Points and Beyond
9.1 Local Geometry of Algebraic and Analytic Varieties
9.2 ACSV for Transverse Points
9.2.1 Critical Points and Stratifications
9.2.2 Asymptotics via Residue Forms
9.3 A Geometric Approach to ACSV
9.3.1 A Gradient Flow Interpretation for Analytic Combinatorics
9.3.2 Attacking the Connection Problem through ACSV and Numeric Analytic Continuation
9.3.3 The State of Analytic Combinatorics in Several Variables
Problems
References
Chapter 10 Application: Lattice Paths, Revisited
10.1 Mostly Symmetric Models in an Orthant
10.1.1 Diagonal Expressions and Contributing Points
10.1.2 Asymptotics for Positive Drift Models
10.1.3 Asymptotics for Negative Drift Models
10.2 Lattice Path Problems to Test Your Skills
Problems
References
Index
Author Index
