Introducing irrational enumeration: analytic combinatorics for objects of irrational size

David Bevan †, Julien Condé · 2024

Read Introducing irrational enumeration: analytic combinatorics for objects of irrational size by David Bevan †, Julien Condé (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14682.txt.

Introduction

Counts of built things rest on whole sizes, yet some things wear wild sizes, as tiles of wild breadth or walks by true span. David Bevan and Julien Condé stretch count craft to such wild wares in a 2024 study. Their count script is a power chain that lets its steps take wild marks.

A turn of the script then gives a spread chain from which the far counts can be read by crest tests. In most hands on cases, the far tale falls out of the first script in plain form. Tile, part, walk, and tree cases show the craft at work. Some wild flocks flip their far tale at a set mark, a turn the pair chart as well.

Catalog record

CREATORDavid Bevan †, Julien Condé
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14682

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Introducing irrational enumeration: analytic combinatorics for objects of irrational size David Bevan †, Julien Condé Abstract We extend the scope of analytic combinatorics to classes containing objects that have irrational sizes. The generating function for such a class is a power series that admits irrational exponents (which we call a Ribenboim series). A transformation then yields a generalised Dirichlet series from which the asymptotics of the coefficients can be extracted by singularity analysis using an appropriate Tauberian theorem. In practice, the asymptotics can often be determined directly from the original generating function. We illustrate the technique with a variety of applications, including tilings with tiles of irrational area, ordered integer factorizations, lattice walks enumerated by Euclidean length, and plane trees with vertices of irrational size. We also explore phase transitions in the asymptotics of families of irrational combinatorial classes. † † footnotetext: † Department of Mathematics and Statistics, The University of Strathclyde, Glasgow, Scotland. † † footnotetext: ‡ Institut Denis Poisson, L’Université d’Orléans, France. † † footnotetext: 2020 Mathematics Subject Classification: 05A15, 05A16, 13F25, 30B50. 1 Introduction At the root of the discipline of analytic combinatorics is the fact that if we consider a generating function analytically as a complex function, then the asymptotic behaviour of its coefficients can be determined from the singularities on its circle of convergence. Specifically (see [ 7 , Theorem VI.1] ), given a combinatorial class \mathcal{C} with ordinary generating function f_{\mathcal{C}}(z)\mathchoice{\;=\;}{=}{=}{=}\sum_{n\geqslant 0}|\mathcal{C}_{n}|z^{n}\mathchoice{\;=\;}{=}{=}{=}\sum_{\mathfrak{c}\in\mathcal{C}}z^{|\mathfrak{c}|}, where \mathcal{C}_{n} is the set of objects in \mathcal{C} of size n , suppose that f_{\mathcal{C}}(z) is (the Taylor series of) a complex function with unique dominant singularity \rho , such that f_{\mathcal{C}}(z)\mathchoice{\;=\;}{=}{=}{=}g(z)+\frac{h(z)}{(1-z/\rho)^{\alpha}}, where \alpha\notin-\mathbb{N} , and both g and h are analytic on the closed disk \overline{D}(0,\rho) . Then the asymptotic number of objects in \mathcal{C} of size n is given by |\mathcal{C}_{n}|\mathchoice{\;=\;}{=}{=}{=}\big[z^{n}\big]f_{\mathcal{C}}(z)\mathchoice{\;\sim\;}{\sim}{\sim}{\sim}\frac{h(\rho)}{\Gamma(\alpha)}\hskip 0.70007pt\rho^{-n}\hskip 0.70007ptn^{\alpha-1}, (1) where \big[z^{n}\big]f(z) is the coefficient of z^{n} in (the Taylor series of) f(z) . Rational and irrational classes 0 1 2 3 4 5 6 7 8 9 10 11 12 Figure 1: A tiling of a strip using seven tiles of length 1 and four of length \sqrt{2} In this paper, we establish analogous results when we remove the requirement that the size of a combinatorial object must be an integer. We require only that the set of sizes of objects in a combinatorial class has no accumulation point in \mathbb{R} . That is, objects in a class \mathcal{C} must take their sizes from some countable set \Lambda_{\mathcal{C}} consisting of a nonnegative increasing sequence of values that tends to infinity. It remains necessary that, for each \lambda\in\Lambda_{\mathcal{C}} , there are only finitely many objects of size \lambda in \mathcal{C} . We distinguish two cases. Firstly, if there exists some \omega>0 such that \Lambda_{\mathcal{C}}\subseteq\omega\mathbb{N} (that is, each object size is a multiple of \omega ), then we say that the class \mathcal{C} is rational . The sizes of objects in rational classes need not themselves be rational: every object in \mathcal{C} has a rational size if and only if \omega\in\mathbb{Q} . Rational classes are not our primary concern. We investigate their asymptotics in Section 2.4 . In contrast, if there is no positive \omega such that \Lambda_{\mathcal{C}}\subseteq\omega\mathbb{N} , then we say that \mathcal{C} is irrational . As a simple example, consider the class \mathcal{T}=\mathcal{T}^{(\beta)} of tilings of a strip of width one using two types of rectangular tile: a 1\times 1 square tile, and a tile with dimensions \beta\times 1 for some \beta>0 . The size of a tiling is the length of the tiled strip. If \beta is irrational, then so is \mathcal{T} , with the set of object sizes being \{k+\ell\beta:k,\ell\in\mathbb{N}\} . See Figure 1 for an illustration, with \beta=\sqrt{2} . Ribenboim series To record the sizes of objects in an irrational class, we use formal power series that admit irrational exponents. We call these Ribenboim series after Paulo Ribenboim, who, building on the earlier work of Levi-Civita [ 20 ] , Hahn [ 9 ] , Neumann [ 24 ] and Higman [ 11 ] , investigated their algebraic properties in a series of papers in the 1990s [ 5 , 27 , 28 , 29 , 30 , 31 ] . See [ 4 ] for a historical perspective, and [ 19 ] for a recent study. Formally, a Ribenboim series in z with coefficients in a commutative ring R is an element \sum_{\lambda}c_{\lambda}z^{\lambda} of the ring R[[z^{\mathbb{R}^{\geq 0}}]] of Hahn series with nonnegative exponents such that the support of the exponents \{\lambda:c_{\lambda}\neq 0\} contains no finite accumulation point. 1 1 1 In general, a Hahn series permits exponents whose support is any well-ordered subset of an ordered group. For enumeration, we take R=\mathbb{Z} . Thus, the generating function ( GF ) of an irrational class \mathcal{C} , which we call an irrational generating function ( IGF ), is the formal Ribenboim series f_{\mathcal{C}}(z)\mathchoice{\;=\;}{=}{=}{=}\sum_{i\geqslant 1}|\mathcal{C}_{\lambda_{i}}|z^{\lambda_{i}}\mathchoice{\;=\;}{=}{=}{=}\sum_{\lambda\in\Lambda_{\mathcal{C}}}|\mathcal{C}_{\lambda}|z^{\lambda}\mathchoice{\;=\;}{=}{=}{=}\sum_{\mathfrak{c}\in\mathcal{C}}z^{|\mathfrak{c}|}, where \mathcal{C}_{\lambda}\mathchoice{\;=\;}{=}{=}{=}\{\mathfrak{c}\in\mathcal{C}:|\mathfrak{c}|=\lambda\} is the set of objects in \mathcal{C} of size \lambda , and \lambda_{1}<\lambda_{2}<\ldots is the total ordering on the elements of \Lambda_{\mathcal{C}} . For example, the IGF for the class \mathcal{T} of strip tilings is f_{\mathcal{T}}(z)\mathchoice{\;=\;}{=}{=}{=}\frac{1}{1\mathchoice{\>-\>}{-}{-}{-}z\mathchoice{\>-\>}{-}{-}{-}z^{\beta}}\mathchoice{\;=\;}{=}{=}{=}\sum_{k,\ell\geqslant 0}\tbinom{k+\ell}{k}z^{k+\ell\beta}. Asymptotics of irrational classes In general, the coefficients in an IGF can fluctuate wildly. For example, here are seven consecutive terms in the GF for \mathcal{T}^{(\sqrt{2})} : 8\,z^{1+7\sqrt{2}},\quad\;z^{11},\quad\;126\,z^{4+5\sqrt{2}},\quad\;120\,z^{7+3\sqrt{2}},\quad\;z^{8\sqrt{2}},\quad\;11\,z^{10+\sqrt{2}},\quad\;84\,z^{3+6\sqrt{2}}. Thus it makes no sense to consider the asymptotics of the coefficients directly. Instead, we consider the number of objects in an irrational class of size at most a given value, which may exhibit smooth asymptotic behaviour. Given a class \mathcal{C} and any x\geqslant 0 , we use \mathcal{C}_{\leqslant x} to denote the set \{\mathfrak{c}\in\mathcal{C}:|\mathfrak{c}|\leqslant x\} of objects in \mathcal{C} of size at most x . Note that the structure required of \Lambda_{\mathcal{C}} is sufficient to ensure that each of these sets is finite. Similarly, if f(z)\mathchoice{\;=\;}{=}{=}{=}\sum_{\lambda\in\Lambda}c_{\lambda}z^{\lambda} is a Ribenboim series, then \big[z^{\leqslant x}\big]f(z)\mathchoice{\;=\;}{=}{=}{=}\sum_{\lambda\leqslant x}c_{\lambda} extracts the sum of the coefficients of those terms of the series with exponent at most x . Thus, \big[z^{\leqslant x}\big]f_{\mathcal{C}}(z)\mathchoice{\;=\;}{=}{=}{=}|\mathcal{C}_{\leqslant x}| . Analytically, a Ribenboim series has a radius of convergence in [0,\infty] and is analytic within its disk of convergence, except on the non-positive real axis, where there is a branch cut. Moreover, if it has nonnegative coefficients and a finite radius of convergence \rho , then it has a singularity at the point z=\rho . See Proposition 10 . In order to specify an additional condition that must be satisfied by an irrational class for our main theorem to apply, we introduce a transform that we apply to IGF s. Dirichlet generating functions If f(z)\mathchoice{\;=\;}{=}{=}{=}\sum_{\lambda\in\Lambda}c_{\lambda}z^{\lambda} is a Ribenboim series, then we define its exponential transform to be the generalised Dirichlet series F(s)\mathchoice{\;=\;}{=}{=}{=}\sum_{\lambda\in\Lambda}c_{\lambda}e^{-\lambda s}, in which e^{-s} has been substituted for z . 2 2 2 In the special case that \Lambda=\{\log n:n\geqslant 1\} , this is a standard Dirichlet series \sum_{n\geqslant 1}a_{n}\hskip 0.70007ptn^{-s} ; see Section 2.2.5 . The exponential transform of the IGF of a combinatorial class is its Dirichlet generating function ( DGF ). \rho z z\,\mapsto\,e^{-s} \log(1/z)\,\mapsfrom\,s -\pi i +\pi i \log(1/\rho) s Figure 2: The mapping of the region of convergence under the exponential transform If a Ribenboim series has radius of convergence \rho , then under

Read the complete text