Limit distributions and scaling functions
Limit distributions and scaling functions
Christoph Richard
Fakultät für Mathematik, Universität Bielefeld,
Postfach 10 01 31, 33501 Bielefeld, Germany
May 27, 2018
Abstract
We discuss the asymptotic behaviour of models of lattice polygons, mainly on
the square lattice. In particular, we focus on limiting area laws in the uniform
perimeter ensemble where, for fixed perimeter, each polygon of a given area occurs
with the same probability. We relate limit distributions to the scaling behaviour of the
associated perimeter and area generating functions, thereby providing a geometric
interpretation of scaling functions. To a major extent, this article is a pedagogic
review of known results.
1 Introduction
For a given combinatorial class of objects, such as polygons or polyhedra, the most basic
question concerns the number of objects of a given size (always assumed to be finite), or
an asymptotic estimate thereof. Informally stated, in this overview we will analyse the
refined question:
What does a typical object look like?
In contrast to the combinatorial question about the number of objects of a given size, the
latter question is of a probabilistic nature. For counting parameters in addition to object
size, one asks for their (asymptotic) probability law. To give this question a meaning,
an underlying ensemble has to be specified. The simplest choice is the uniform ensemble,
where each object of a given size occurs with equal probability.
For self-avoiding polygons on the square lattice, size may be the number of edges of the
polygon, and an additional counting parameter may be the area enclosed by the polygon.
We will call this ensemble the fixed perimeter ensemble. For the uniform fixed perimeter
ensemble, one assumes that, for a fixed number of edges, each polygon occurs with the
same probability. Another ensemble, which we will call the fixed area ensemble, is obtained
with size being the polygon area, and the number of edges being an additional counting
http://arxiv.org/abs/0704.0716v4
parameter. For the uniform fixed area ensemble, one assumes that, for fixed area, each
polygon occurs with the same probability.
To be specific, let pm,n denote the number of square lattice self-avoiding polygons of
half-perimeter m and area n. Discrete random variables X̃m of area in the uniform fixed
perimeter ensemble and of perimeter Ỹn in the uniform fixed area ensemble are defined by
P(X̃m = n) =
pm,n∑
n pm,n
, P(Ỹn = m) =
pm,n∑
m pm,n
We are interested in an asymptotic description of these probability laws, in the limit of
infinite object size.
In statistical physics, certain non-uniform ensembles are important. For fixed object
size, the probability of an object with value n of the counting parameter (such as the area
of a polygon) may be proportional to an, for some non-negative parameter a = e−βE of
non-uniformity. Here E is the energy of the object, and β = 1/(kBT ), where T is the
temperature, and kB denotes Boltzmann’s constant. A qualitative change in the behaviour
of typical objects may then be reflected in a qualitative change in the probability law of
the counting parameter w.r.t. a. Such a change is an indication of a phase transition, i.e.,
a non-analyticity in the free energy of the corresponding ensemble.
For self-avoiding polygons in the fixed perimeter ensemble, let q denote the parameter
of non-uniformity,
P(X̃m(q) = n) =
pm,nq
n pm,nq
Polygons of large area are suppressed in probability for small values of q, such that one
expects a typical self-avoiding polygon to closely resemble a branched polymer. Likewise,
for large values of q, a typical polygon is expected to be inflated, closely resembling a ball
(or square) shape. Let us define the ball-shaped phase by the condition that the mean
area of a polygon grows quadratically with its perimeter. The ball-shaped phase occurs
for q > 1 [31]. Linear growth of the mean area w.r.t. perimeter is expected to occur
for all values 0 < q < 1. This phase called the branched polymer phase. Of particular
interest is the point q = 1, at which a phase transition occurs [31]. This transition is called
a collapse transition. Similar considerations apply for self-avoiding polygons in the fixed
area ensemble,
P(Ỹn(x) = m) =
pm,nx
pm,nxm
with parameter of non-uniformity x, where 0 < x < ∞.
For a given model, these effects may be studied using data from exact or Monte-Carlo
enumeration and series extrapolation techniques. Sometimes, the underlying model is
exactly solvable, i.e., it obeys a combinatorial decomposition, which leads to a recursion
for the counting parameter. In that case, its (asymptotic) behaviour may be extracted
from the recurrence.
A convenient tool is generating functions. The combinatorial information about the
number of objects of a given size is coded in a one-variable (ordinary) generating function,
typically of positive and finite radius of convergence. Given the generating function of the
counting problem, the asymptotic behaviour of its coefficients can be inferred from the
leading singular behaviour of the generating function. This is determined by the location
and nature of the singularity of the generating function closest to the origin. There are
elaborate techniques for studying this behaviour exactly [37] or numerically [43].
The case of additional counting parameters leads to a multivariate generating function.
For self-avoiding polygons, the half-perimeter and area generating function is
P (x, q) =
pm,nx
For a fixed value of a non-uniformity parameter q0, where 0 < q0 ≤ 1, let x0 be the radius
of convergence of P (x, q0). The asymptotic law of the counting parameter is encoded in the
singular behaviour of the generating function P (x, q) about (x0, q0). If locally about (x0, q0)
the nature of the singularity of P (x, q) does not change, then distributions are expected
to be concentrated, with a Gaussian limit law. This corresponds to the physical intuition
that fluctuations of macroscopic quantities are asymptotically negligible away from phase
transition points. If the nature of the singularity does change locally, we expect non-
concentrated distributions, resulting in non-Gaussian limit laws. This is expected to be
the case at phase transition points.
Qualitative information about the singularity structure is given by the singularity di-
agram (also called the phase diagram). It displays the region of convergence of the two-
variable generating function, i.e., the set of points (x, q) in the closed upper right quadrant
of the plane, such that the generating function P (x, q) converges. The set of boundary
points with positive coordinates is a set of singular points of P (x, q), called the critical
curve. See Figure 1 for a sketch of the singularity diagram of a typical polygon model
such as self-avoiding polygons, counted by half-perimeter and area, with generating func-
tion P (x, q) as above. There appear two lines of singularities, which intersect at the point
Figure 1: Singularity diagram of a typical polygon model counted by half-perimeter and area,
with x conjugate to half-perimeter and q conjugate to area.
(x, q) = (xc, 1). Here xc is the radius of convergence of the half-perimeter generating func-
tion P (x, 1), also called the critical point. The nature of a singularity does not change
along each of the two lines, and the intersection point (x, q) = (xc, 1) of the two lines is a
phase transition point. For 0 < q < 1 fixed, denote by xc(q) the radius of convergence of
P (x, q). The branched polymer phase for the fixed perimeter ensemble 0 < q < 1 (and also
for the corresponding fixed area ensemble) is asymptotically described by the singularity
of P (x, q) about (xc(q), q). In the ball-shaped phase q > 1 of the fixed perimeter ensemble,
the (ordinary) generating function does not seem the right object to study, since it has zero
radius of convergence for fixed q > 1. The singularity of P (x, q) about (x, 1) describes, for
0 < x < xc, a ball-shaped phase in the fixed area ensemble, with a finite average size of a
ball.
For points (x, q) within the region of convergence, both x and y positive, the generating
function P (x, q) is finite and positive. Thus, such points may be interpreted as parameters
in a mixed infinite ensemble
P(X̃(x, q) = (m,n)) =
pm,nx
m,n pm,nx
The limiting law of the counting parameter in the fixed area or fixed perimeter ensem-
ble can be extracted from the leading singular behaviour of the two-variable generating
function. There are two different approaches to the problem. The first one consists in
analysing, for fixed non-uniformity parameter a, the singular behaviour of the remaining
one-parameter generating function and its derivatives w.r.t. a. This method is also called
the method of moments. It can be successfully applied in the fixed perimeter ensemble at
the phase transition point. Typically, this results in non-concentrated distributions.
The second approach derives an asymptotic approximation of the two-variable generat-
ing function. Away from a phase transition point, such an approximation can be obtained
for some classes of models, typically resulting in concentrated distributions, with a Gaus-
sian law for the centred and normalised random variable. However, it is usually difficult to
extract such information at a phase transition point. The theory of tricritical scaling seeks
to fill this gap, by suggesting and justifying a particular ansatz for an approximation using
scaling functions. Knowledge of the approximation may imply knowledge of the quantities
analysed in the first approach.
In the following, we give an overview of these two approaches. For the first approach,
summarised by the title limit distributions , there are a number of rigorous results, which
we will discuss. The second approach, summarised by the title scaling functions , is less
developed. For that reason, our presentation will be more descriptive, stating important
open questions. We will stress connections between the two approaches, thereby providing
a probabilistic interpretation of scaling functions in terms of limit distributions.
2 Polygon models and generating functions
Models of polygons, polyominoes or polyhedra have been studied intensively on the square
and cubic lattices. It is believed that the leading asymptotic behaviour of such models,
such as the type of limit distribution or critical exponents, is independent of the underlying
lattice.
In two dimensions, a number of models of square lattice polygons have been enumerated
according to perimeter and area and other parameters, see [7] for a review of models with an
exact solution. The majority of such models has an algebraic perimeter generating function.
We mention prudent polygons [96, 22, 8] as a notable exception. Of particular importance
for polygon models is the fixed perimeter ensemble, since it models two-dimensional vesicle
collapse. Another important ensemble is the fixed area ensemble, which serves as a model of
ring polymers. The fixed area ensemble may also describe percolation and cluster growth.
For example, staircase polygons are models of directed compact percolation [26, 28, 29,
27, 12, 57]. This may be compared to the exactly solvable case of percolation on a tree
[42]. The model of self-avoiding polygons is conjectured to describe the hull of critical
percolation clusters [60].
In addition to perimeter, other counting parameters have been studied, such as width
and height, generalisations of area [89], radius of gyration [53, 64], number of nearest-
neighbour interactions [4], last column height [7], and site perimeter [20, 11]. Also, mo-
tivated by applications in chemistry, symmetry subclasses of polygon models have been
analysed [63, 62, 40, 95]. Whereas this gives rise to a number of different ensembles, only
a few of them have been asymptotically studied. Not all of them display phase transitions.
In three dimensions, models of polyhedra on the cubic lattice have been enumerated
according to perimeter, surface area and volume, see [74, 102, 3] and the discussion in
section 3.9. Various ensembles may be defined, such as the fixed surface area ensemble
and the fixed volume ensemble. The fixed surface area ensemble serves as a model of
three-dimensional vesicle collapse [104].
In this chapter, we will consider models of square lattice polygons, counted by half-
perimeter and area. Let pm,n denote the (finite) number of such polygons of half-perimeter
m and area n. The numbers pm,n will always satisfy the following assumption.
Assumption 1. For m,n ∈ N0, let non-negative integers pm,n ∈ N0 be given. The numbers
pm,n are assumed to satisfy the following properties.
i) There exist positive constants A,B > 0 such that pm,n = 0 if n ≤ Am or if n ≥ Bm2.
ii) The sequence (
n pm,n)m∈N0 has infinitely many positive elements and grows at most
exponentially.
Remarks. i) A sequence (an)n∈N0 is said to grow at most exponentially, if there are positive
constants C, µ such that |an| ≤ Cµn for all n.
ii) Condition i) reflects the geometric constraint that the area of a polygon grows at most
quadratically and at least linearly with its perimeter. For self-avoiding polygons, we have
n ≥ m − 1. Since pm,n = 0 if m < 2, we may choose A = 1/3. Since n ≤ m2/4 for
self-avoiding polygons, we may choose B = 1/3. Condition ii) is a natural condition on
the growth of the number of polygons of a given perimeter. For self-avoiding polygons, we
may choose C = 1 and µ = 16.
iii) For models with counting parameters different from area, or for models in higher
dimensions, a modified assumption holds, with the growth condition i) being replaced by
n ≤ Amk0 and n ≥ Bmk1 , for appropriate values of k0 and k1. Counting parameters
statisfying pm,n = 0 for n ≥ Bmk are called rank k parameters [25].
The above assumption imposes restrictions on the generating function of the numbers
pm,n. These explain the qualitative form of the singularity diagram Figure 1.
Proposition 1. For numbers pm,n, let Assumption 1 be satisfied. Then, the generating
function P (x, q) =
m,n pm,nx
mqn has the following properties.
i) The generating function P (x, q) satisfies for k ∈ N
P (x, q) ≪
P (x, q) ≪ Bk
P (x, q),
where ≪ denotes coefficient-wise domination.
ii) The evaluation P (x, 1) is a power series with radius of convergence xc, where 0 <
xc ≤ 1.
iii) The generating function P (x, q) diverges, if x 6= 0 and |q| > 1. It converges, if |q| < 1
and |x| < xcq−A. In particular, for k ∈ N0, the evaluations
P (x, q)
are power series with radius of convergence 1.
iv) For k ∈ N0, the evaluations
P (x, q)
are power series with radius of convergence xc. They satisfy, for |x| < xc,
P (x, q)
= lim
−1<q<1
P (x, q).
sketch. The domination formula follows immediately from condition i). The existence of
the evaluations at q = 1 and x = xc as formal power series also follows from condition i).
Condition ii) ensures that 0 < xc ≤ 1 for the radius of convergence of P (x, 1). Equality
of the radii of convergence for the derivatives follows from condition i) by elementary
estimates. The claimed analytic properties of P (x, q) follow from conditions i) and ii) by
elementary estimates. The claimed left-continuity of the derivatives in iv) is implied by
Abel’s continuity theorem for real power series.
Remarks. i) Proposition 1 implies that the critical curve xc(q) satisfies for 0 < q < 1 the
estimate xc(q) ≥ xcq−A. For self-avoiding polygons, the critical curve xc(q) is continuous
for 0 < q < 1. This follows from a certain supermultiplicative inequality for the numbers
pm,n by convexity arguments [48].
ii) Of central importance in the sequel will be the power series
gk(x) =
P (x, q)
. (1)
They are called factorial moment generating functions , for reasons which will become clear
later.
We continue studying analytic properties of the factorial moment generating functions.
In the following, the notation x ր x0 denotes the limit x → x0 for sequences (xn) satisfying
|xn| < x0. The notation f(x) ∼ g(x) as x ր x0 means that g(x) 6= 0 in a left neigbourhood
of x0 and that limxրx0 f(x)/g(x) = 1. Likewise, am ∼ bm as m → ∞ for sequences
(am), (bm) means that bm 6= 0 for almost all m and limm→∞ am/bm = 1. The following
lemma is a standard result.
Lemma 1. Let (am)m∈N0 be a sequence of real numbers, which asymptotically satisfy
am ∼ Ax−mc mγ−1 (m → ∞), (2)
for real numbers A, xc, γ, where A 6= 0 and xc > 0.
Then, the generating function g(x) =
m=0 amx
m has radius of convergence xc. If
γ /∈ {0,−1,−2, . . .}, then there exists a power series g(reg)(x) with radius of convergence
strictly larger than xc, such that g(x) satisfies
g(x)− g(reg)(x)
∼ AΓ(γ)
(1− x/xc)γ
(x ր xc), (3)
where Γ(z) denotes the Gamma function.
Remarks. i) The above lemma can be proved using the analytic properties of the polylog
function [32]. If γ ∈ {0,−1,−2, . . .}, an asymptotic form similar to Eq. (3) is valid, which
involves logarithms.
ii) The function g(reg)(x) in the above lemma is not unique. For example, if γ > 0, any
polynomial in x may be chosen. We demand g(reg)(x) ≡ 0 in that case. If γ < 0 and
g(reg)(x) is restricted to be a polynomial, it is uniquely defined. If −1 < γ < 0, we
have g(reg)(x) ≡ g(xc). In the general case, the polynomial has degree ⌊−γ⌋, compare
[32]. In the following, we will demand uniqueness by the above choice. The power series
g(sing)(x) :=
g(x)− g(reg)(x)
is then called the singular part of g(x).
Conversely, let a power series g(x) with radius of convergence xc be given. In order to
conclude from Eq. (3) the behaviour Eq. (2), certain additional analyticity assumptions
on g(x) have to be satisfied. To this end, a function g(x) is called ∆(xc, η, φ)-regular (or
simply ∆-regular) [30], if there is a positive real number xc > 0, such that g(x) is analytic
in the indented disc ∆(xc, η, φ) := {z ∈ C : |z| ≤ xc + η, |Arg(z − xc)| ≥ φ}, for some
η > 0 and some φ, where 0 < φ < π/2. Note that xc /∈ ∆, where we adopt the convention
Arg(0) = 0. The point x = xc is the only point for |x| ≤ xc, where g(x) may possess a
singularity.
Lemma 2 ([35]). Let the function g(x) be ∆-regular and assume that
g(x) ∼ 1
(1− x/xc)γ
(x → xc in ∆).
If γ /∈ {0,−1,−2, . . .}, we then have
[xm]g(x) ∼
x−mc m
γ−1 (m → ∞),
where [xm]g(x) denotes the Taylor coefficient of g(x) of order m about x = 0.
Remarks. i) Note that the coefficients of the function f(x) = (1 − x/xc)−γ with real
exponent γ /∈ {0,−1,−2, . . .} satisfy
[xm]f(x) ∼ 1
x−mc m
γ−1 (m → ∞). (4)
This may be seen by an application of the binomial series and Stirling’s formula. For
functions g(x) ∼ f(x), the assumption of ∆-regularity for g(x) ensures that the same
asymptotic estimate holds for the coefficients of g(x).
ii) Theorems of the above type are called transfer theorems [35, 37]. The set of ∆-regular
functions with singularities of the above form is closed under addition, multiplication,
differentiation, and integration [30].
iii) The case of a finite number of singularities on the circle of convergence can be treated
by a straightforward extension of the above result [35, 37].
Lemma 1 implies a particular singular behaviour of the factorial moment generating
functions, if the numbers pm,n satisfy certain typical asymptotic estimates. We write
(a)k = a · (a− 1) · . . . · (a− k + 1) to denote the lower factorial.
Proposition 2. For m,n ∈ N0, let real numbers pm,n be given. Assume that the numbers
pm,n asymptotically satisfy, for k ∈ N0,
(n)kpm,n ∼ Akx−mc mγk−1 (m → ∞), (5)
for real numbers Ak, xc, γk, where Ak > 0, xc > 0, and γk /∈ {0,−1,−2, . . .}.
Then, the factorial moment generating functions gk(x) satisfy
(sing)
k (x) ∼
(1− x/xc)γk
(x ր xc), (6)
where fk = Ak Γ(γk).
Model φ θ γ0 Area limit law
rectangles
convex polygons
−1 2 β1,1/2
Ferrers diagrams
stacks
1 Gaussian
staircase polygons
bargraph polygons
column-convex polygons
directed column-convex polygons
diagonally convex directed polygons
rooted self-avoiding polygons∗
directed convex polygons 2
meander
diagonally convex polygons∗ −1
three-choice polygons 0
Table 1: Exponents and area limit laws for prominent polygon models. An asterisk denotes a
numerical analysis.
Remarks. i) The above assumption on the growth of the coefficients in Eq. (5) is typical
for polygon models, with γk = (k − θ)/φ, and φ > 0.
ii) If the numbers pm,n satisfy, in addition to Eq.(5), Condition i) of Assumption 1, this
implies for exponents of the form γk = (k − θ)/φ, where φ > 0, the estimate 1/2 ≤ φ ≤ 1.
iii) The proposition implies that the singular part of the factorial moment generating
function gk(x) is asymptotically equal to the singular part of the corresponding (ordinary)
moment generating function,
P (x, q)
)(sing)
P (x, q)
∣∣∣∣∣
(sing)
(x ր xc).
We give a list of exponents and area limit distributions for a number of polygon models.
An asterisk denotes that corresponding results rely on a numerical analysis. It appears that
the value (θ, φ) = (1/3, 2/3) arises for a large number of models. Furthermore, the exponent
γ0 seems to determine the area limit law. These two observations will be explained in the
following section.
3 Limit distributions
In this section, we will concentrate on models of square lattice polygons in the fixed perime-
ter ensemble, and analyse their area law. The uniform ensemble is of particular interest,
since non-Gaussian limit laws usually appear, due to expected phase transitions at q = 1.
For non-uniform ensembles q 6= 1, Gaussian limit laws are expected, due to the absence of
phase transitions.
There are effective techniques for the uniform ensemble, since the relevant generating
functions are typically algebraic. This is different from the fixed area ensemble, where
singularities are more difficult to analyse. It will turn out that the dominant singularity of
the perimeter generating function determines the limiting area law of the model. We will
first discuss several examples with different type of singularity. Then, we will describe a
general result, by analysing classes of q-difference equations (see e.g. [103]), which exactly
solvable polygon models obey. Whereas in the case q 6= 1 their theory is developed to some
extent, the case q = 1 is more difficult to analyse. Motivated by the typical behaviour of
polygon models, we assume that a q-difference equation reduces to an algebraic equation
as q approaches unity, and then analyse the behaviour of its solution about q = 1.
Useful background concerning a probabilistic analysis of counting parameters of combi-
natorial structures can be found in [37, Ch IX]. See [80, Ch 1] and [5, Ch 1] for background
about asymptotic expansions. For properties of formal power series, see [39, Ch 1.1]. A
useful reference on the Laplace transform, which will appear below, is [23].
3.1 An illustrative example: Rectangles
3.1.1 Limit law of area
Let pm,n denote the number of rectangles of half-perimeter m and area n. Consider the
uniform fixed perimeter ensemble, with a discrete random variable of area X̃m defined by
P(X̃m = n) =
pm,n∑
n pm,n
. (7)
The k-th moments of X̃m are given explicitly by
E[X̃km] =
(l(m− l))k
∼ m2k
(x(1− x))kdx = (k!)
(2k + 1)!
m2k (m → ∞),
where we approximated the Riemann sum by an integral, using the Euler-MacLaurin sum-
mation formula. Thus, the random variable X̃m has mean µm ∼ m2/6 and variance
σ2m ∼ m4/180. Since the sequence of random variables (X̃m) does not satisfy the con-
centration property limm→∞ σm/µm = 0, we expect a non-trivial limiting distribution.
Consider the normalised random variable
. (8)
Since the moments ofXm converge asm → ∞, and the limit sequenceMk := limm→∞ E[Xkm]
satisfies the Carleman condition
k(M2k)
−1/(2k) = ∞, they define [17, Ch 4.5] a unique
random variable X with moments Mk. Its moment generating function M(t) = E[e
−tX ] is
readily obtained as
M(t) =
E[Xk]
(−t)k =
et erf
The corresponding probability distribution p(x) is obtained by an inverse Laplace trans-
form, and is given by
p(x) =
1−x 0 ≤ x ≤ 1
0 x > 1
. (9)
This distribution is known as the beta distribution β1,1/2. Together with [17, Thm 4.5.5],
we arrive at the following result.
Theorem 1. The area random variable X̃m of rectangles Eq. (7) has mean µm ∼ m2/6
and variance σ2m ∼ m4/180. The normalised random variables Xm Eq. (8) converge in
distribution to a continuous random variable with limit law β1,1/2 Eq. (9). We also have
moment convergence.
3.1.2 Limit law via generating functions
We now extract the limit distribution using generating functions. Whereas the derivation
is less direct than the previous approach, the method applies to a number of other cases,
where a direct approach fails. Consider the half-perimeter and area generating function
P (x, q) for rectangles,
P (x, q) =
pm,nx
The factorial moments of the area random variable X̃m Eq. (7) are obtained from the
generating function via
E[(X̃m)k] =
n(n)kpm,n∑
n pm,n
[xm] ∂
P (x, q)
[xm]P (x, 1)
where (a)k = a · (a − 1) · . . . · (a − k + 1) is the lower factorial. The generating function
P (x, q) satisfies [87, Eq. 5.1] the linear q-difference equation [103]
P (x, q) = x2qP (qx, q) +
x2q(1 + qx)
1− qx
. (10)
Due to the particular structure of the functional equation, the area moment generating
functions
gk(x) =
P (x, q)
are rational functions and can be computed recursively from the functional equation, by
repeated differentiation w.r.t. q and then setting q=1. (Such calculations are easily per-
formed with a computer algebra system.) This gives, in particular,
g0(x) =
(1− x)2
, g1(x) =
(1− x)4
g2(x) =
(1− x)6
, g3(x) =
(1− x)8
g4(x) =
x4(1 + 22x+ x2)
(1− x)10
, g5(x) =
12x5(1 + 8x+ x2)
(1− x)12
Whereas the exact expressions get messy for increasing k, their asymptotic form about
their singularity xc = 1 is simply given by
gk(x) ∼
(1− x)2k+2
(x → 1). (11)
The above result can be inferred from the functional equation, which induces a recursion
for the functions gk(x), which in turn can be asymptotically analysed. This method is
called moment pumping [36]. Below, we will extract the above asymptotic behaviour by
the method of dominant balance.
The asymptotic behaviour of the moments of X̃m can be obtained from singularity
analysis of generating functions, as described in Lemma 2. Using the functional equation,
it can be shown that all functions gk(x) are Laurent series about x = 1, with a finite number
of terms. Hence the remark following Lemma 2 implies for the (factorial) moments of the
random variable Xm Eq. (8) the expression
E[(Xm)
∼ E[(Xm)k]
Γ(2k + 2)
(2k + 1)!
(m → ∞),
in accordance with the previous derivation.
On the level of the moment generating function, an application of Watson’s lemma [5,
Sec 4.1] shows that the coefficients k! in Eq. (11) appear in the asymptotic expansion of a
certain Laplace transform of the (entire) moment generating function E[e−tX ],
E[Xk]
(−t2)k
t dt ∼
(−1)kk!s−(2k+2) (s → ∞).
Note that the r.h.s. is formally obtained by term-by-term integration of the l.h.s..
Using the arguments of [46, Ch 8.11], one concludes that there exists an s0 > 0, such
that there is a unique function F (s) analytic for ℜ(s) ≥ s0 with the above asymptotic
expansion. It is given by
F (s) = Ei(s2) es
, (12)
where Ei(z) =
e−tz /t dt is the exponential integral. The moment generating function
M(t) = E[e−tX ] of the random variable X is given by an inverse Laplace transform of F (s),
e−stM(t2)t dt = F (s).
Since there are effective methods for computing inverse Laplace transforms [23], the
question arises whether the function F (s) can be easily obtained. It turns out that the
functional equation Eq. (10) induces a differential equation for F (s). This equation can be
obtained in a mechanical way, using the method of dominant balance.
3.1.3 Dominant balance
For a given functional equation, the method of dominant balance consists of a certain
rescaling of the variables, such that the quantity of interest appears in the expansion of a
rescaled variable to leading order. The method was originally used as an heuristic tool in
order to extract the scaling function of a polygon model [84] (see the following section). In
the present framework, it is a rigorous method.
Consider the half-perimeter and area generating function P (x, q) as a formal power
series. The substitution q = 1− ǫ̃ is valid, since the coefficients of the power series P (x, q)
in x are polynomials in q. We get the power series in ǫ̃,
H(x, ǫ̃) =
(−1)kgk(x)ǫ̃k.
whose coefficients (−1)kgk(x) are power series in x. The functional equation Eq. (10)
induces an equation for H(x, ǫ̃), from which the factorial area moment generating functions
gk(x) may be computed recursively.
Now replace gk(x) by its expansion about x = 1,
gk(x) =
(1− x)2k+2−l
Introducing s̃ = 1− x, this leads to a power series E(s̃, ǫ̃) in ǫ̃,
E(s̃, ǫ̃) =
(−1)k
s̃2k+2−l
whose coefficients are Laurent series in s̃. As above, the functional equation induces an
equation for the power series E(s̃, ǫ̃) in ǫ̃, from which the expansion coefficients may be
computed recursively.
We infer from the previous equation that
E(sǫ, ǫ2) =
(−1)k fk,l
s2k+2−l
F (s, ǫ). (13)
Write F (s, ǫ) =
l≥0 Fl(s)ǫ
l. By construction, the (formal) series F0(s) = F (s, 0) coincides
with the asymptotic expansion of the desired function F (s) Eq. (12) about infinity.
The above example suggests a technique for computing F0(s). The functional equation
Eq. (10) for P (x, q) induces, after reparametrisation, differential equations for the functions
Fl(s), from which F0(s) may be obtained explicitly. These may be computed by first writing
P (x, q) =
(1− q)1/2
, (1− q)1/2
, (14)
and then introducing variables s and ǫ, by setting x = 1− sǫ and q = 1− ǫ2. Expand the
equation to leading order in ǫ. This yields, to order ǫ0, the first order differential equation
sF ′0(s) + 2− 2s2F0(s) = 0.
The above equation translates into a recursion for the coefficients fk,0, from which fk,0 = k!
can be deduced. In addition, the equation has a unique solution with the prescribed
asymptotic behaviour Eqn. (13), which is given by F0(s) = Ei(s
2) es
As we will argue in the next section, Eq. (14) is sometimes referred to as a scaling
Ansatz, the function F (s, 0) appears as a scaling function, the functions Fl(s), for l ≥ 1,
appear as correction-to-scaling functions . In our formal framework, where the series Fl(s)
are rescaled generating functions for the coefficients fk,l, their derivation is rigorous.
3.2 A general method
In the preceding two subsections, we described a method for obtaining limit laws of counting
parameters, via a generating function approach. Since this method will be important in
the remainder of this section, we summarise it here. Its first ingredient is based on the
so-called method of moments [17, Thm 4.5.5].
Proposition 3. For m,n ∈ N0, let real numbers pm,n be given. Assume that the numbers
pm,n asymptotically satisfy, for k ∈ N0,
(n)kpm,n ∼ Akx−mc mγk−1 (m → ∞), (15)
where Ak are positive numbers, and γk = (k − θ)/φ, with real constants θ and φ > 0.
Assume that the numbers Mk := Ak/A0 satisfy the Carleman condition
(M2k)
−1/(2k) = +∞. (16)
Then the following conclusions hold.
i) For almost all m, the random variables X̃m
P(X̃m = n) =
pm,n∑
n pm,n
are well defined. We have
Xm :=
d→ X, (18)
for a unique random variable X with moments Mk, where d denotes convergence in
distribution. We also have moment convergence.
ii) If the numbers Mk satisfy for all t ∈ R the estimate
= 0, (19)
then the moment generating function M(t) = E[e−tX ] of X is an entire function.
The coefficients AkΓ(γk) are related to M(t) by a Laplace transform which has, for
θ > 0, the asymptotic expansion
E[Xk]
(−t1/φ)k
t1−γ0
(−1)kAkΓ(γk)s−γk (s → ∞).
sketch. A straightforward calculation using Eq. (15) leads to
E[(X̃m)k]
mk/φ (m → ∞).
This implies that the same asymptotic form holds for the (ordinary) moments E[(X̃m)
Due to the growth condition Eq. (16), the sequence (Mk) defines a unique random variable
X with moments Mk. Also, moment convergence of the sequence (Xm) to X implies
convergence in distribution, see [17, Thm 4.5.5]. Due to the growth condition Eq. (19), the
function M(t) is entire. Hence the conditions of Watson’s Lemma [5, Sec 4.1] are satisfied,
and we obtain Eq. (20).
Remarks. i) The growth condition Eq. (19) implies the Carleman condition Eq. (16). All
examples below have entire moment generating functions M(t).
ii) If γ0 < 0, a modified version of Eq. (20) can be given, see for example staircase polygons
below.
Proposition 2 states that assumption Eq. (15) translates, at the level of the half-
perimeter and area generating function P (x, q) =
m,n pm,nx
mqn, to a certain asymptotic
expression for the factorial moment generating functions
gk(x) =
P (x, q)
Their asymptotic behaviour follows from Eq. (15), and is
(sing)
k (x) ∼
(1− x/xc)γk
(x ր xc),
where fk = AkΓ(γk). Adopting the generating function viewpoint, the amplitudes fk
determine the numbers Ak, hence the moments Mk = Ak/A0 of the limit distribution. The
series F (s) =
k≥0(−1)kfks−γk will be of central importance in the sequel.
Definition 1 (Area amplitude series). Let Assumption 1 be satisfied. Assume that the
generating function P (x, q) =
m,n pm,nx
mqn satisfies asymptotically
P (x, q)
)(sing)
(1− x/xc)γk
(x ր xc),
with exponents γk /∈ {0,−1,−2, . . .}. Then, the formal series
F (s) =
(−1)k fk
is called the area amplitude series.
Remarks. i) Proposition 3 states that the area amplitude series appears in the asymptotic
expansion about infinity of a Laplace transform of the moment generating function of the
area limit distribution. The probability distribution of the limiting area distribution is
related to F (s) by a double Laplace transform.
ii) For typical polygon models, all derivatives of P (x, q) w.r.t. q, evaluated at q = 1, exist
and have the same radius of convergence, see Proposition 1. Typical polygon models do
have factorial moment generating functions of the above form, see the examples below.
The second ingredient of the method consists in applying the method of dominant
balance. As described above, this may result in a differential equation (or in a difference
equation [90]) for the function F (s). Its applicability has to be tested for each given type
of functional equation. Typically, it can be applied if the factorial area moment generating
functions gk(x) Eq. (1) have, for values x < xc, a local expansion about x = xc of the form
(sing)
k (x) =
(1− x/xc)γk,l
where γk,l = (k − θl)/φ and θl+1 > θl. If a transfer theorem such as Lemma 2 applies,
then the differential equation for F (s) induces a recurrence for the moments of the limit
distribution. If the differential equation can be solved in closed form, inverse Laplace
transform techniques may be applied in order to obtain explicit expressions for the moment
generating function and the probability density. Also, higher order corrections to the
limiting behaviour may be analysed, by studying the functions Fl(s), for l ≥ 1. See [87]
for examples.
3.3 Further examples
Using the general method as described above, area limit laws for the other exactly solved
polygon models can be derived. A model with the same area limit law as rectangles
is convex polygons, compare [87]. We will discuss some classes of polygon models with
different area limit laws.
3.3.1 Ferrers diagrams
In contrast to the previous example, the limit distribution of area of Ferrers diagrams is
concentrated.
Proposition 4. The area random variable X̃m of Ferrers diagrams has mean µm ∼ m2/8.
The normalised random variablesXm Eq. (18) converge in distribution to a random variable
with density p(x) = δ(x− 1/8).
Remark. It should be noted that the above convergence statement already follows from
the concentration property limm→∞ σm/µm = 0, with σ
m ∼ m3/48 the variance of Xm, by
an explicit analysis of the first three factorial moment generating functions. (By Cheby-
shev’s inequality, the concentration property implies convergence in probability, which in
turn implies convergence in distribution.) For illustrative purposes, we follow a different
route via the moment method in the following proof.
Proof. Ferrers diagrams, counted by half-perimeter and area, satisfy the linear q-difference
equation [87, Eq (5.4)]
P (x, q) =
(1− qx)2
P (qx, q) +
(1− qx)2
The perimeter generating function g0(x) = x
2/(1 − 2x) is obtained by setting q = 1 in
the above equation. Hence xc = 1/2. Using the functional equation, it can be shown by
induction on k that all area moment generating functions gk(x) are rational in g0(x) and
its derivatives. Hence all gk(x) are rational functions. Since the area of a polygon grows
at most quadratically with the perimeter, we have a bound on the exponent, γk ≤ 2k + 1,
of the leading singular part of gk(x). Given this bound, the method of dominant balance
can be applied. We set
P (x, q) =
(1− q) 12
1− 2x
(1− q) 12
, (1− q)
and introduce new variables s and ǫ by q = 1 − ǫ2 and 2x = 1 − sǫ. Then an expansion
of the functional equation yields, to order ǫ0, the ODE of first order F ′(s) = 4sF (s)− 1,
whose unique solution with the prescribed asymptotic behaviour is
F (s) =
It can be inferred from the differential equation that all coefficients in the asymptotic
expansion of F (s) at infinity are nonzero. Hence, the above exponent bound is tight.
It can be inferred from the functional equation by induction on k that each gk(x) is a
Laurent polynomial about xc = 1/2. Thus, Lemma 2 applies, and we obtain the moment
generating function of the corresponding random variable Eq. (18) as M(s) = exp(−s/8).
This is readily recognised as the moment generating function of a probability distribution
concentrated at x = 1/8.
A sequence of random variables, which satisfies the concentration property, often leads
to a Gaussian limit law, after centering and suitable normalisation. This is also the case
for Ferrers diagrams.
Theorem 2 ([97]). The area random variable X̃m of Ferrers diagrams has mean µm ∼
m2/8 and variance σ2m ∼ m3/48. The centred and normalised random variables
X̃m − µm
, (21)
converge in distribution to a Gaussian random variable.
Remarks. i) It is possible to prove this result by the method of dominant balance. The
idea of proof consists in studying the functional equation of the generating function for the
“centred coefficients” pm,n − µm.
ii) The above arguments can also be applied to stack polygons to yield the concentration
property and a central limit theorem.
3.3.2 Staircase polygons
The limit law of area of staircase polygons is the Airy distribution. This distribution (see
[34] and the survey [52]) is conveniently defined via its moments.
Definition 2 (Airy distribution [34]). The random variable Y is said to be Airy distributed
E[Y k]
Γ(γ0)
Γ(γk)
where γk = 3k/2− 1/2, and the numbers φk satisfy, for k ≥ 1, the quadratic recurrence
γk−1φk−1 +
φlφk−l = 0,
with initial condition φ0 = −1.
Remarks ([34, 58]). i) The first moment is E[Y ] =
π. The sequence of moments can
be shown to satisfy the Carleman condition. Hence the distribution is uniquely determined
by its moments.
ii) The numbers φk appear in the asymptotic expansion of the logarithmic derivative of
the Airy function at infinity,
logAi(s) ∼
(−1)kφk
s−γk (s → ∞),
where Ai(x) = 1
cos(t3/3 + tx) dt is the Airy function.
iii) Explicit expressions for the numbers φk are known [58]. They are, for k ≥ 1, given by
φk = 2
k+1 3
x3(k−1)/2
Ai(x)2 + Bi(x)2
where Bi(z) is the second standard solution of the Airy differential equation f ′′(z)−zf(z) =
iv) The Airy distribution appears in a variety of contexts [34]. In particular, the random
variable Y/
8 describes the law of the area of a Brownian excursion. See also [76] for an
overview from a physical perspective.
Explicit expressions have been derived for the moment generating function of the Airy
distribution and for its density.
Fact 1 ([19, 66, 99, 34]). The moment generating function M(t) = E[e−tY ] of the Airy
distribution satisfies the modified Laplace transform
(e−st−1)M(2−3/2t3/2)
dt = 21/3
Ai′(21/3s)
Ai(21/3s)
Ai′(0)
Ai(0)
. (22)
The moment generating function M(t) is given explicitly by
M(2−3/2t) =
−βkt2/32−1/3
where the numbers −βk are the zeros of the Airy function. Its density p(x) is given explicitly
23/2p(23/2x) =
e−vk v
where vk = 2β
k/(27x
2) and U(a, b, z) is the confluent hypergeometric function.
Remarks. i) The confluent hypergeometric function U(a, b; z) is defined as [1]
U(a, b; z) =
sin πb
1F1[a, b; z]
Γ(1 + a− b)Γ(b)
1F1[1 + a− b, 2− b; z]
Γ(a)Γ(2− b)
where 1F1[a; b; z] is the hypergeometric function
1F1[a; b; z] = 1 +
a(a+ 1)
b(b+ 1)
+ . . .
ii) The moment generating function and its density are obtained by two consecutive inverse
Laplace transforms of Eq. (22), see [67, 68] and [99, 54].
iii) In the proof of the following theorem, we will derive Eq. (22) using the model of staircase
polygons. This shows, in particular, that the coefficients φk appear in the asymptotic
expansion of the Airy function.
Theorem 3. The normalised area random variables Xm of staircase polygons Eq. (18)
satisfy
d−→ Y√
(m → ∞),
where Y is Airy distributed according to Definition 2. We also have moment convergence.
Remark. Given the functional equation of the half-perimeter and area generating function
of staircase polygons,
P (x, q) =
1− 2xq − P (qx, q)
(see [88] for a recent derivation), this result is a special case of Theorem 4 below, which is
stated in [25].
Proof. We use the method of dominant balance. From the functional equation Eq. (23),
we infer g0(x) = 1/4 +
1− 4x/2 + (1 − 4x)/4. Hence xc = 1/4. The structure of the
functional equation implies that all functions gk(x) can be written as Laurent series in
1− 4x, see also Proposition 7 below. Explicitly, we get g1(x) = x2/(1 − 4x). This
suggests γk = (3k− 1)/2. An upper bound of this form on the exponent γk can be derived
without too much effort from the functional equation, by an application of Faa di Bruno’s
formula, see also [89, Prop (4.4)]. Thus, the method of dominant balance can be applied.
We set
P (x, q) =
+ (1− q)1/3F
1− 4x
(1− q)2/3
, (1− q)1/3
and introduce variables s, ǫ by 4x = 1 − sǫ2 and q = 1 − ǫ3. In the above equation,
we excluded the constant 1/4 =: P (reg)(x, q), since it does not contribute to the moment
asymptotics. Expanding the functional equation to order ǫ2 gives the Riccati equation
F ′(s) + 4F (s)2 − s = 0. (24)
It follows that the coefficients fk of F (s) satisfy, for k ≥ 1, the quadratic recursion
γk−1fk−1 + 4
flfk−l = 0,
with initial condition f0 = −1/2. A comparison with the definition of the Airy distribution
shows that φk = 2
2k+1fk. Using the closure properties of ∆-regular functions, it can be
inferred from the functional equation that (the analytic continuation of) each factorial
moment generating function gk(x) is ∆-regular, with xc = 1/4, see also Proposition 7
below. Hence the transfer theorem Lemma 2 can be applied. We obtain 4Xm
d→ Y in
distribution and for moments, where Y is Airy distributed.
Remarks. i) The unique solution F (s) of the differential equation in the above proof
Eq. (24), satisfying the prescribed asymptotic behaviour, is given by
F (s) =
logAi(41/3s). (25)
The moment generating function M(t) of the limiting random variable X = limm→∞Xm
is related to the function F (s) via the modified Laplace transform
(e−st−1)M(t3/2) 1
dt = 4
π(F (s)− F (0)),
where the modification has been introduced in order to ensure a finite integral about the
origin. This result relates the above proof to Proposition 1.
ii) The method of dominant balance can be used to obtain corrections Fl(s) to the limiting
behaviour [87].
The fact that the area law of staircase polygons is, up to normalisation, the same as
that of the area under a Brownian excursion, suggests that there might be a combinato-
rial explanation. Indeed, as is well known, there is a bijection [21, 98] between staircase
polygons and Dyck paths, a discrete version of Brownian excursions [2], see figure 2 [88].
Within this bijection, the polygon area corresponds to the sum of peak heights of the Dyck
path, but not to the area below the Dyck path. For more about this connection, see the
Figure 2: [88] A combinatorial bijection between staircase polygons and Dyck paths [21, 98].
Column heights of a polygon correspond to peak heights of a path.
remark at the end of the following subsection.
3.4 q-difference equations
All polygon models discussed above have an algebraic perimeter generating function. More-
over, their half-perimeter and area generating function satisfies a functional equation of
the form
P (x, q) = G(x, q, P (x, q), P (qx, q)),
for a real polynomial G(x, q, y0, y1). Since, under mild assumptions on G, the equation
reduces to an algebraic equation for P (x, 1) in the limit q → 1, it may be viewed as a
“deformation” of an algebraic equation. In this subsection, we will analyse equations of
this type at the special point (x, q) = (xc, 1), where xc is the radius of convergence of
P (x, 1). It will appear that the methods used in the above examples also can be applied
to this more general case.
The above equation falls into the class of q-difference equations [103]. While particular
examples appear in combinatorics in a number of places, see e.g. [37], the asymptotic
behaviour of equations of the above form seems to have been systematically studied initially
in [25, 87]. The study can be done in some generality, e.g., also for non-polynomial power
series G, for replacements more general than x 7→ qx, and for multivariate generalisations,
see [89] and [25]. For simplicity, we will concentrate on polynomial G, and then briefly
discuss generalisations. Our exposition closely follows [89, 87].
3.4.1 Algebraic q-difference equations
Definition 3 (Algebraic q-difference equation [25, 87]). An algebraic q-difference equation
is an equation of the form
P (x, q) = G(x, q, P (x, q), P (qx, q), . . . , P (qNx, q)), (26)
where G(x, q, y0, y1, . . . , yN) is a complex polynomial. We require that
G(0, q, 0, 0, . . . , 0) ≡ 0,
(0, q, 0, 0, . . . , 0) ≡ 0 (k = 0, 1, . . . , N).
Remarks. i) See [103] for an overview of the theory of q-difference equations. As q
approaches unity, the above equation reduces to an algebraic equation.
ii) Asymptotics for solutions of algebraic q-difference equations have been considered in
[25]. The above definition is a special case of [89, Def 2.4], where a multivariate extension
is considered, and where G may be non-polynomial. Also, replacements more general than
x 7→ f(q)x are allowed. Such equations are called q-functional equations in [89]. The
results presented below apply mutatis mutandis also to q-functional equations.
The algebraic q-difference equation in Definition 3 uniquely defines a (formal) power
series P (x, q) satisfying P (0, q) ≡ 0. This is shown by analysing the implied recurrence
for the coefficients pm(q) of P (x, q) =
m>0 pm(q)x
m, see also [89, Prop 2.5]. In fact,
pm(q) is a polynomial in q. The growth of its degree in m is not larger than cm
2 for some
positive constant c, hence the counting parameters are rank 2 parameters [25]. In our
situation, such a bound holds, since the area of a polygon grows at most quadratically
with its perimeter.
From the preceding discussion, it follows that the factorial moment generating functions
gk(x) =
P (x, q)
are well-defined as formal power series. In fact, they can be recursively determined from the
q-difference equation by implicit differentiation, as a consequence of the following proposi-
tion.
Proposition 5 ([87, 89]). Consider the derivative of order k > 0 of an algebraic q-
difference equation Eq. (26) w.r.t. q, evaluated at q = 1. It is linear in gk(x), and its
r.h.s. is a complex polynomial in the power series gl(x) and its derivatives up to order
k − l, where l = 0, . . . , k.
Remarks. i) This statement can be shown by analysing the k-th derivative of the q-
difference equation, using Faa di Bruno’s formula [18].
ii) It follows that every function gk(x) is rational in gl(x) and its derivatives up to order
k− l, where 0 ≤ l < k. Since G is a polynomial, gk(x) is algebraic, by the closure properties
of algebraic functions.
We discuss analytic properties of the (analytic continuations of the) factorial moment
generating functions gk(x). These are determined by the analytic properties of g0(x) =
P (x, 1). We discuss the case of a square-root singularity of P (x, 1), which often occurs
for combinatorial structures, and which is well studied, see e.g. [79, Thm 10.6] or [37,
Ch VII.4]. Other cases may be treated similarly. We make the following assumption:
Assumption 2. The q-difference equation in Definition 3 has the following properties:
i) All coefficients of the polynomial G(x, q, y0, y1, . . . , yN) are non-negative.
ii) The polynomial Q(x, y) := G(x, 1, y, y, . . . , y) satisfies Q(x, 0) 6≡ 0 and has degree at
least two in y.
iii) P (x, 1) =
m≥1 pmx
m is aperiodic, i.e., there exist indices 1 ≤ i < j < k such that
pipjpk 6= 0, while gcd(j − i, k − i) = 1.
Remarks. i) The positivity assumption is natural for combinatorial constructions. There
are, however, q-difference equations with negative coefficients, which arise from systems of
q-difference equations with non-negative coefficients by reduction. Examples are convex
polygons [87, Sec 5.4] and directed convex polygons, see below.
ii) Assumptions i) and ii) result in a square-root singularity as the dominant singularity
of P (x, 1).
iii) Assumption iii) implies that there is only one singularity of P (x, 1) on its circle of
convergence. Since P (x, 1) has non-negative coefficients only, it occurs on the positive real
half-line. The periodic case can be treated by a straightforward extension [37].
An application of the (complex) implicit function theorem ensures that P (x, 1) is an-
alytic at the origin. It can be analytically continued, as long as the defining algebraic
equation remains invertible. Together with the positivity assumption, one can conclude
that there is a number 0 < xc < ∞, such that the analytic continuation of P (x, 1) satisfies
yc = limxրxc P (x, 1) < ∞, with
Q(xc, yc) = yc,
Q(xc, y)
With the positivity assumption on the coefficients, it follows that
Q(xc, y)
> 0, C :=
Q(x, yc)
> 0. (27)
These conditions characterise the singularity of P (x, 1) at x = xc as a square-root. It
can be shown that there exists a locally convergent expansion of P (x, 1) about x = xc, and
that P (x, 1) is analytic for |x| < xc. We have the following result. Recall that a function
f(z) is ∆-regular if it is analytic in the indented disc ∆ = {z : |z| ≤ xc+η, |Arg(z−xc)| ≥
φ} for some η > 0 and some φ, where 0 < φ < π/2.
Proposition 6 ([79, 37, 89]). Given Assumption 2, the power series P (x, 1) is analytic
at x = 0, with radius of convergence xc. Its analytic continuation is ∆-regular, with a
square-root singularity at x = xc and a local Puiseux expansion
P (x, 1) = yc +
f0,l(1− x/xc)1/2+l/2,
where yc = limxրxc P (x, 1) < ∞ and f0,0 = −
xcC/B, for constants B > 0 and C >
0 as in Eq. (27). The numbers f0,l can be recursively determined from the q-difference
equation.
The asymptotic behaviour of P (x, 1) = g0(x) carries over to the factorial moment
generating functions gk(x).
Proposition 7 ([89]). Given Assumption 2, all factorial moment generating functions
gk(x) are, for k ≥ 1, analytic at x = 0, with radius of convergence xc. Their analytic
continuations are ∆-regular, with local Puiseux expansions
gk(x) =
fk,l(1− x/xc)−γk+l/2,
where γk = 3k/2 − 1/2. The numbers fk,0 = fk are, for k ≥ 2, characterised by the
recursion
γk−1fk−1 +
flfk−l = 0,
and the numbers f0 < 0 and f1 > 0 are given by
f0 = −
, 4f1 =
k=1 k
(xc, 1, yc, yc, . . . , yc)
, (28)
for constants B > 0 and C > 0 as in Eq. (27).
Remarks. i) This result can be obtained by a direct analysis of the q-difference equation,
applying Faa di Bruno’s formula, see also [87, Sec 2.2].
ii) Alternatively, it can be obtained by applying the method of dominant balance to the
q-difference equation. To this end, one notes that all functions gk(x) are Laurent series in√
1− x/xc, and that their leading exponents are bounded from above by γk. (An upper
bound on an exponent is usually easier to obtain than its exact value, since cancellations
can be ignored). With these two ingredients, the method of dominant balance, as described
above, can be applied. The differential equation of the function F (s) then translates, via
a transfer theorem, into the above recursion for the coefficients. See [89, Sec 5].
The above result can be used to infer the limit distribution of area, along the lines of
Section 3.2.
Theorem 4 ([25, 89]). Let Assumption 2 be satisfied. For the solution of an algebraic
q-difference equation P (x, q) =
m,n pm,nx
mqn, let X̃m denote the random variable
P(X̃m = n) =
pm,n∑
n pm,n
(which is well-defined for almost all m). The mean of X̃m is given by
E[X̃m] ∼ 2
m3/2 (m → ∞),
where the numbers f0 and f1 are given in Eq. (28). The sequence of normalised random
variables Xm converges in distribution,
E[X̃m]
d−→ Y√
(m → ∞),
where Y is Airy distributed according to Definition 2. We also have moment convergence.
Remarks. i) An explicit calculation shows that φk = |f0|−1
fk. Together with
Proposition 7, the claim of the proof follows by standard reasoning, as in the examples
above.
ii) The above theorem appears in [25, Thm 3.1], together with an indication of the ar-
guments of a proof. [There is a misprint in the definition of γ in [25, Thm 3.1]. In our
notation γ = 4Bf1.] Within the more general setup of q-functional equations, the theorem
is a special case of [89, Thm 1.5].
iii) The above theorem is a kind of central limit theorem for combinatorial constructions,
since the Airy distribution arises under natural assumptions for a large class of combina-
torial constructions. For a connection to certain Brownian motion functionals, see below.
3.4.2 q-functional equations and other extensions
We discuss extensions of the above result. Generically, the dominant singularity of P (x, 1)
is a square-root. The case of a simple pole as dominant singularity, which generalises
the example of Ferrers diagrams, has been discussed in [87]. Under weak assumptions,
the resulting limit distribution of area is concentrated. Other singularities can also be
analysed, as shown in the examples of rectangles above and of directed convex polygons in
the following subsection. Compare also [90].
The case of non-polynomial G can be discussed along the same lines, with certain
assumptions on the analyticity properties of the series G. In the undeformed case q = 1,
it is a classical result [37, Ch VII.3] that the generating function has a square-root as
dominant singularity, as in the polynomial case. One can then argue along the above
lines that an Airy distribution emerges as the limit law of the deformation variable [89,
Thm 1.5]. Such an extension is relevant, since prominent combinatorial models, such as the
Cayley tree generating function, fall into that class. See also the discussion of self-avoiding
polygons below.
The above statements also remain valid for more general classes of replacements x 7→ qx,
e.g., for replacements x 7→ f(q)x, where f(q) is analytic for 0 ≤ q ≤ 1, with non-negative
series coefficients about q = 0. More interestingly, the idea of introducing a q-deformation
may be iterated [25], leading to equations such as
P (x, q1, . . . , qM) = G(x, P (xq1 · . . . · qM , q1q2 · . . . · qM , q2q3 · . . . · qM , . . . , qM)). (29)
The counting parameters corresponding to qk are rank k + 1 parameters, and limit distri-
butions for such quantities have been derived for some types of singularities [77, 78, 88].
There is a central limit result for the generic case of a square-root singularity [89]. This
generalisation applies to counting parameters, which decompose linearly under a combina-
torial construction. These results can also be obtained by an alternative method, which
generalises to non-linear parameters, see [51].
The case where the limit q to unity in a q-difference equation is not algebraic, has not
been discussed. For example, if G(x, q, P (x, q), P (qx, q)) = 0 for some polynomial G, the
limit q to unity might lead to an algebraic differential equation for P (x, 1). This may be
seen by noting that
f(x)− f(qx)
(1− q)
= xf ′(x),
for f(x) differentiable at x. Such equations are possibly related to polygon models such as
three-choice polygons [44] or punctured staircase polygons [45]. Their perimeter generating
function is not algebraic, hence the models do not satisfy an algebraic q-difference equation
as in Definition 3.
3.4.3 A stochastic connection
Lastly, we indicate a link to Brownian motion, which appears in [99, 100] and was further
developed in [77, 78, 89, 88]. As we saw in Section 3.2, limit distributions can, under
certain conditions, be characterised by a certain Laplace transform of their moment gen-
erating functions. This approach, which arises naturally from the viewpoint of generating
functions, can be applied to discrete versions of Brownian motion, excursions, bridges or
meanders. Asymptotic results are results for the corresponding stochastic objects. In fact,
distributions of some functionals of Brownian motion have apparently first been obtained
using this approach [99, 100].
Interestingly, a similar characterisation appears in stochastics for functionals of Brow-
nian motion, via the Feynman-Kac formula. For example, Louchard’s formula [66] relates
the logarithmic derivate of the Airy function to a certain Laplace transform of the moment
generating function of the law of the Brownian excursion area. Distributions of functionals
of Brownian motion can also be obtained by a path integral approach, see [75] for a recent
overview.
The discrete approach provides an alternative method for obtaining information about
distributions of certain functionals of Brownian motion. For such functionals, it provides
an alternative proof of Louchard’s formula [77, 78]. It leads, via the method of dominant
balance, quite directly to moment recurrences for the underlying distribution. These have
been studied in the case of rank k parameters for discrete models of Brownian motion.
In particular, they characterise the distributions of integrals over (k − 1)-th powers of the
corresponding stochastic objects [77, 78, 89, 88]. Such results have apparently not been
previously derived using stochastic methods. The generating function approach can also be
applied to classes of q-functional equations with singularities different from those connected
to Brownian motion. For a related generalisation, see [10].
Vice versa, results and techniques from stochastics can be (and have been) analysed in
order to study asymptotic properties of polygons. An example is the contour process of
simply generated trees [38], which asymptotically describes the area of a staircase polygon.
See also [69, 70, 71, 59].
3.5 Directed convex polygons
We show that the limit law of area of directed convex polygons in the uniform fixed
perimeter ensemble is that of the area of the Brownian meander.
Fact 2 ([100, Thm 2]). The random variable Z of area of the Brownian meander is char-
acterised by
E[Zk]
Γ(α0)
Γ(αk)
where αk = 3k/2 + 1/2. The numbers ωk satisfy for k ≥ 1 the quadratic recurrence
αk−1ωk−1 +
−lωk−l = 0,
with initial condition ω0 = 1, where the numbers φk appear in the Airy distribution as in
Definition 2.
Remarks. i) This result has been derived using a discrete meander, whose length and
area generating function is described by a system of two algebraic q-difference equations,
see [77, Prop 1].
ii) We have E[Z] = 3
2π/8 for the mean of Z. The random variable Z is uniquely
determined by its moments. The numbers ωk appear in the asymptotic expansion [100,
Thm 3]
Ω(s) =
Ai(t) dt
3Ai(s)
(−1)kωks−αk (s → ∞),
where Ai(x) = 1
cos(t3/3 + tx) dt is the Airy function.
Explicit expressions have been derived for the moment generating function and for the
distribution function of Z.
Fact 3 ([100, Thm 5]). The moment generating function M(t) = E[e−tZ ] of Z satisfies the
Laplace transform ∫ ∞
e−stM(
2 t3/2)
πΩ(s). (30)
It is explicitly given by
M(t) = 2−1/6t1/3
Rk exp(−βkt2/32−1/3)
for ℜ(t) > 0, where the numbers −βk are the zeroes of the Airy function, and where
βk(1 + 3
Ai(−t) dt)
3Ai′(−βk)
The random variable Z has a continuous density p(y), with distribution function R(x) =∫ x
p(y) dy given by
R(x) =
(18)1/6x
−vk v
k Ai((3vk/2)
2/3),
where vk = (βk)
3/(27x2).
Remark. The moment generating function and the distribution function are obtained by
two consecutive inverse Laplace transforms of Eq. (30).
Theorem 5. The normalised area random variablesXm of directed convex polygons Eq. (18)
satisfy
d−→ 1
Z (m → ∞),
where Z is the area random variable of the Brownian meander as in Fact 2. We also have
moment convergence.
Proof. A system of q-difference equations for the generating function Q(x, y, q) of directed
convex polygons, counted by width, height and area, has been given in [9, Lemma 1.1]. It
can be reduced to a single equation,
q(qx− 1)Q(x, y, q) + ((1 + q)(P (x, y, q) + y))Q(qx, y, q)+
xyq − y2 + P (x, y, q)(qx− y − 1)
Q(q2x, y, q)
− q2xy (y + P (x, y, q)− 1) = 0,
where P (x, y, q) is the width, height and area generating function of staircase polygons.
Setting q=1 and x = y yields the half-perimeter generating function
g0(x) =
1− 4x
Hence xc = 1/4 for the radius of convergence of Q(x, x, 1).
It is possible to derive from Eq. (31) a q-difference equation for the (isotropic) half-
perimeter and area generating function Q(x, q) = Q(x, x, q) of directed convex polygons.
This is due to the symmetry Q(x, y, q) = Q(y, x, q), which results from invariance of the
set of directed convex polygons under reflection along the negative diagonal y = −x. Since
this equation is quite long, we do not give it here. By arguments analogous to those of the
previous subsection, it can be deduced from this equation that all area moment generating
functions gk(x) of Q(x, 1) are Laurent series in s =
1− 4x, see also [89, Prop (4.3)]. The
leading singular exponent of gk(x), defined by gk(x) ∼ hk(1− x/xc)−αk as x ր xc, can be
bounded from above by αk ≤ 3k/2 + 1/2, see also [89, Prop (4.4)] for the argument. We
apply the method of dominant balance, in order to prove that αk = 3k/2 + 1/2 and to
yield recurrences for the coefficients hk. We define
P (x, q) =
+ (1− q)1/3F
1− 4x
(1− q)2/3
, (1− q)1/3
Q(x, q) = (1− q)−1/3H
1− 4x
(1− q)2/3
, (1− q)1/3
where F (s) = F (s, 0) has already been determined in Eq. (25). We set 4x = 1 − sǫ2,
q = 1− ǫ3, and expand the q-difference equation to leading order in ǫ. We get for H(s) :=
H(s, 0) the inhomogeneous linear differential equation of first order
H ′(s) + 4H(s)F (s) +
This implies for the coefficients hk of H(s) =
k≥0 hks
−αk and fk of F (s) =
k≥0 fks
for k ≥ 1 the quadratic recursion
αk−1hk−1 + 4
flhk−l = 0,
where h0 = 1/16. Using fk = 2
−2k−1φk, we obtain the meander recursion in Fact 2 by
setting hk = 2
−k−4ωk. It can be inferred from the functional equation that (the analytic
continuations of) all factorial moment generating functions are ∆-regular, with xc = 1/4.
Thus Lemma 2 applies, and we conclude Xm
d→ Z/2.
Remarks. i) The above theorem states that the limit distribution of area of directed
convex polygons coincides, up to normalisation, with the area distribution of the Brownian
meander [100]. This suggests that there might exist a combinatorial bijection to discrete
meanders, in analogy to that between staircase polygons and Dyck paths. Up to now,
a “nice” bijection has not been found, see however [6, 72] for combinatorial bijections to
discrete bridges.
ii) The above proof relies on a q-difference equation for the isotropic generating function
Q(x, x, q). Up to normalisation, the meander distribution also appears for the anisotropic
model Q(x, y, q), where 0 < y < 1/2 is fixed, as can be shown by a considerably simpler
calculation. The normalisation constant coincides with that of the isotropic model for
y = 1/2. The latter statement is also a consequence of the fact that the height random
variable of directed polygons is asymptotically Gaussian, after centering and normalisation.
Analogous considerations apply to the relation between isotropic and anisotropic versions
of the other polygon classes.
3.6 Limit laws away from (xc, 1)
As motivated in the introduction, limit laws in the fixed perimeter ensemble for q 6= 1 are
expected to be Gaussian. The same remark holds for the fixed area ensemble for x 6= xc.
There are partial results for the model of staircase polygons. The fixed area ensemble can,
for x < xc and q near unity, be analysed using Fact 7 of the following section. For staircase
polygons in the uniform fixed area ensemble x = 1, the following result holds.
Fact 4 ([37, Prop IX.11]). Consider the perimeter random variable of staircase polygons
in the uniform fixed area ensemble,
P(Ỹn = m) =
pm,n∑
m pm,n
The variable Ỹn has mean µn ∼ µ ·n and standard deviation σn ∼ σ
n, where the numbers
µ and σ satisfy
µ = 0.8417620156 . . . , σ = 0.4242065326 . . .
The centred and normalised random variables
Ỹn − µn
converge in distribution to a Gaussian random variable.
Remark. The above result is proved using an explicit expression for the half-perimeter
and area generating function, as a ratio of two q-Bessel functions. It can be shown that this
expression is meromorphic about (x, q) = (1, qc) with a simple pole, where qc is the radius
of convergence of the generating function P (1, q). The explicit form of the singularity
about (1, qc) yields a Gaussian limit law.
There are a number of results for classes of column-convex polygons in the uniform
fixed area ensemble, typically leading to Gaussian limit laws. The upper and lower shape
of a polygon can be described by Brownian motions. See [69, 70, 71] for details. It would
be interesting to prove convergence to a Gaussian limit law within a more general frame-
work, such as q-difference equations. Analogous questions for other functional equations,
describing counting parameters such as horizontal width, have been studied in [24].
3.7 Self-avoiding polygons
A numerical analysis of self-avoiding polygons, using data from exact enumeration [91,
92], supports the conjecture that the limit law of area is, up to normalisation, the Airy
distribution.
Let pm,n denote the number of square lattice self-avoiding polygons of half-perimeter
m and area n. Exact enumeration techniques have been applied to obtain the numbers
pm,n for all values of n for given m ≤ 50. Numerical extrapolation techniques yield very
accurate estimates of the asymptotic behaviour of the coefficients of the factorial moment
generating functions. To leading order, these are given by
[xm]gk(x) =
(n)kpm,n ∼ Akx−mc m3k/2−3/2−1 (m → ∞), (32)
for positive amplitudes Ak. The above form has been numerically checked [91, 92] for values
k ≤ 10 and is conjectured to hold for arbitrary k. The value xc is the radius of convergence
of the half-perimeter generating function of self-avoiding polygons. The amplitudes Ak
have been extrapolated to at least five significant digits. In particular, we have
xc = 0.14368062927(2), A0 = 0.09940174(4), A1 = 0.0397886(1),
where the numbers in brackets denote the uncertainty in the last digit. An exact value of
the amplitude A1 = 1/(8π) has been predicted [15] using field-theoretic arguments.
The particular form of the exponent implies that the model of rooted self-avoiding poly-
gons p̃m,n = mpm,n has the same exponents φ = 2/3 and θ = 1/3 as staircase polygons. In
particular, it implies a square-root as dominant singularity of the half-perimeter generat-
ing function. Together with the above result for q-functional equations, this suggests that
(rooted) self-avoiding polygons might obey the Airy distribution as a limit law of area.
A natural method to test this conjecture consists in analysing ratios of moments, such
that a normalisation constant is eliminated. Such ratios are also called universal amplitude
ratios. If the conjecture were true, we would have asymptotically
E[X̃km]
E[X̃m]k
∼ k! Γ(γ1)
Γ(γk)Γ(γ0)k−1
(m → ∞),
for the area random variables X̃m as in Eq. (17). The numbers φk and exponents γk are
those of the Airy distribution as in Definition 2. The above form was numerically confirmed
for values of k ≤ 10 to a high level of numerical accuracy. The normalisation constant is
obtained by noting that E[Y ] =
Conjecture 1 (cf [91, 92]). Let pm,n denote the number of square lattice self-avoiding
polygons of half-perimeter m and area n. Let X̃m denote the random variable of area in
the uniform fixed perimeter ensemble,
P(X̃m = n) =
pm,n∑
n pm,n
We conjecture that
E[X̃m]
d−→ Y√
where Y is Airy distributed according to Definition 2.
Remarks. i) Field theoretic arguments [15] yield A1 = 1/(8π).
ii) References [91, 92] contain conjectures for the scaling function of self-avoiding polygons
and rooted self-avoiding polygons, see the following section. In fact, the numerical analysis
in [91, 92] mainly concerns the area amplitudes Ak, which determine the limit distribution
of area.
iii) The area law of self-avoiding polygons has also been studied [91, 92] on the triangular
and hexagonal lattices. As for the square lattice, the area limit law appears to be the Airy
distribution, up to normalisation.
iv) It is an open question whether there are non-trivial counting parameters other than the
area, whose limit law (in the fixed perimeter ensembles) coincides between self-avoiding
polygons and staircase polygons. See [88] for a negative example. This indicates that
underlying stochastic processes must be quite different.
v) A proof of the above conjecture is an outstanding open problem. It would be interest-
ing to analyse the emergence of the Airy distribution using stochastic Loewner evolution
[60]. Self-avoiding polygons at criticality are conjectured to describe the hull of critical
percolation clusters and the outer boundary of two-dimensional Brownian motion [60].
A numerical analysis of the fixed area ensemble along the above lines again shows
behaviour similar to that of staircase polygons. This supports the following conjecture.
Conjecture 2. Consider the perimeter random variable of self-avoiding polygons in the
uniform fixed area ensemble,
P(Ỹn = m) =
pm,n∑
m pm,n
The random variable Ỹn is conjectured to have mean µn ∼ µ · n and standard deviation
σn ∼ σ
n, where the numbers µ and σ satisfy
µ = 1.855217(1), σ2 = 0.3259(1),
where the number in brackets denotes the uncertainty in the last digit. The centred and
normalised random variables
Ỹn − µn
are conjectured to converge in distribution to a Gaussian random variable.
The above conjectures, together with the results of the previous subsection, also raise
the question whether rooted square-lattice self-avoiding polygons, counted by half-perimeter
and area, might satisfy a q-functional equation. In particular, it would be interesting to
consider whether rooted self-avoiding polygons might satisfy
P (x) = G(x, P (x)), (33)
for some power series G(x, y) in x, y. If the perimeter generating function P (x) is not
algebraic, this excludes polynomials G(x, y) in x and y. Note that the anisotropic perimeter
generating function of self-avoiding polygons is not D-finite [86]. It is thus unlikely that
the isotropic perimeter generating function is D-finite and, in particular, algebraic. On the
other hand, solutions of Eq. (33) need not be algebraic nor D-finite. An example is the
Cayley tree generating function T (x) satisfying T (x) = x exp(T (x)), see [33].
3.8 Punctured polygons
Punctured polygons are self-avoiding polygons with internal holes, which are also self-
avoiding polygons. The polygons are also mutually avoiding. The perimeter of a punctured
polygon is the sum of the lengths of its boundary curves, the area of a punctured polygon is
the area of the outer polygon minus the area of the holes. Apart from intrinsic combinato-
rial interest, models of punctured polygons may be viewed as arising from two-dimensional
sections of three-dimensional self-avoiding vesicles. Counted by area, they may serve as an
approximation to the polyomino model.
We consider, for a given subclass of self-avoiding polygons, punctured polygons with
holes from the same subclass. The case of a bounded number of punctures of bounded
size can be analysed in some generality. The case of a bounded number of punctures of
unbounded size leads to simple results if the critical perimeter generating function of the
model without punctures is finite.
For a given subclass of self-avoiding polygons, the number pm,n denotes the number
of polygons with half-perimeter m and area n. Let p
(r,s)
m,n denote the number of polygons
with r ≥ 1 punctures whose half-perimeter sum equals s. Let p(r)m,n denote the number of
polygons with r ≥ 1 punctures of arbitrary size.
Theorem 6 ([94, Thms 1,2]). Assume that, for a class of self-avoiding polygons with-
out punctures, the area moment coefficients p
n≥0 n
kpm,n have, for k ∈ N0, the
asymptotic form
p(k)m ∼ Akx−mc mγk−1 (m → ∞),
for numbers Ak > 0, for 0 < xc ≤ 1 and for γk = (k − θ)/φ, where 0 < φ < 1. Let
g0(x) =
m≥0 p
m denote the half-perimeter generating function.
Then, the area moment coefficient p
(r,k,s)
(r,s)
m,n of the polygon class with r ≥ 1
punctures whose half-perimeter sum equals s is, for k ∈ N0, asymptotically given by
p(r,k,s)m ∼ A
(r,s)
γk+r−1 (m → ∞),
where A
(r,s)
xsc[x
s](g0(x))
If θ > 0, the area moment coefficient p
(r,k)
m,n of the polygon class with r ≥ 1
punctures of arbitrary size satisfies, for k ∈ N0, asymptotically
p(r,k)m ∼ A
γk+r−1 (m → ∞),
where the amplitudes A
k are given by
Ak+r(g0(xc))
Remarks. i) The basic argument in the proof of the preceding result involves an estimate
of interactions of hole polygons with one another or with the boundary of the external
polygon, which are shown to be asymptotically irrelevant. This argument also applies in
higher dimensions, as long as the exponent φ satisfies 0 < φ < 1.
ii) In the case of an infinite critical perimeter generating function, such as for subclasses of
convex polygons, boundary effects are asymptotically relevant, if punctures of unbounded
size are considered. The case of an unbounded number of punctures, which approximates
the polyomino problem, is unsolved.
iii) The above result leads to new area limit distributions. For rectangles with r punctures
of bounded size, we get βr+1,1/2 as the limit distribution of area. For staircase polygons with
punctures, we obtain generalisations of the Airy distribution, which are discussed in [94].
In contrast, for Ferrers diagrams with punctures of bounded size, the limit distribution of
area stays concentrated.
iv) The theorem also applies to models of punctured polygons, which do not satisfy an
algebraic q-difference equation. An example is given by staircase polygons with a staircase
hole of unbounded size, whose perimeter generating function is not algebraic [45].
3.9 Models in three dimensions
There are very few results for models in higher dimensions, notably for models on the cubic
lattice. There are a number of natural counting parameters for such objects. We restrict
consideration to area and volume, which is the three-dimensional analogue of perimeter
and area of two-dimensional models.
One prominent model is self-avoiding surfaces on the cubic lattice, also studied as
a model of three-dimensional vesicle collapse. We follow the review in [102] (see also
the references therein) and consider closed orientable surfaces of genus zero, i.e., surfaces
homeomorphic to a sphere. Numerical studies indicate that the surface generating function
displays a square-root γ = −1/2 as the dominant singularity.
Consider the fixed surface area ensemble with weights proportional to qn, with n the
volume of the surface. One expects a deflated phase (branched polymer phase) for small
values of q and an inflated phase (spherical phase) for large values of q. In the deflated
phase, the mean volume of a surface should grow proportionally to the aream of the surface,
in the inflated phase the mean volume should grow like m3/2 with the surface. Numerical
simulations suggest a phase transition at q = 1 with exponent φ = 1. This indicates that
a typical surface resembles a branched polymer, and a concentrated distribution of volume
is expected. Note that this behaviour differs from that of the two-dimensional model of
self-avoiding polygons.
Even relatively simple subclasses of self-avoiding surfaces such as rectangular boxes [73]
and plane partition vesicles [50], generalising the two-dimensional models of rectangles and
Ferrers diagrams, display complicated behaviour. Let pm,n denote the number of surfaces of
area m and volume n and consider the generating function P (x, q) =
m,n pm,nx
mqn. For
rectangular box vesicles, we apparently have P (x, 1) ∼ A| log(1−x)|/(1−x)3/2 as x → 1−,
some some constant A > 0, see [73, Eq (35)]. In the fixed surface area ensemble, a linear
polymer phase 0 < q < 1 is separated from a cubic phase q > 1. At q = 1, we have φ = 2/3,
such that typical rectangular boxes are expected to attain a cubic shape. We expect a limit
distribution which is concentrated. For plane partition vesicles, it is conjectured on the
basis of numerical simulations [50, Sec 4.1.1] that P (x, 1) ∼ A exp(α/(xc−x)1/3)/(xc−x)γ ,
where γ ≈ 1.7 at xc = 0.8467(3), for non-vanishing constants A and α. It is expected that
φ = 1/2.
As in the previous subsection, three-dimensional models of punctured vesicles may
be considered. The above arguments hold, if the exponent φ satisfies 0 < φ < 1. A
corresponding result for punctures of unbounded size can be stated if the critical surface
area generating function is finite.
3.10 Summary
In this section, we described methods to extract asymptotic area laws for polygon models
on the square lattice, and we applied these to various classes of polygons. Some of the laws
were found to coincide with those of the (absolute) area under a Brownian excursion and a
Brownian meander. A combinatorial explanation for the latter result has not been given.
Is there a simple polygon model with the same area limit law as the area under a Brownian
bridge? The connection to stochastics deserves further investigation. In particular, it would
be interesting to identify underlying stochastic processes. For an approach to a number of
different random combinatorial structures starting from a probabilistic viewpoint, see [82].
Area laws of polygon models in the uniform fixed perimeter ensemble q = 1 have been
understood in some generality, by an analysis of the singular behaviour of q-functional
equations about the point (x, q) = (xc, 1). Essentially, the type of singularity of the
half-perimeter generating function determines the limit law. A refined analysis can be
done, leading to local limit laws and providing convergence rates. Also, limit distributions
describing corrections to the asymptotic behaviour can be derived. They seem to coincide
with distributions arising in models of punctured polygons, see [94].
For non-uniform ensembles, concentrated distributions are expected, but general re-
sults, e.g. for q-functional equations, are lacking. These may be obtained by multivariate
singularity analysis, see also [24, 65].
The underlying structure of q-functional equations appears in a number of other combi-
natorial models, such as models of two-dimensional directed walks, counted by length and
area between the walk and the x-axis, models of simply generated trees, counted by the
number of nodes and path length, and models which appear in the average case analysis
of algorithms, see [34, 37]. Thus, the above methods and results can be applied to such
models. In statistical physics, this mainly concerns models of (interacting) directed walks,
see [48] for a review. There is also an approach to the behaviour of such walks from a
stochastic viewpoint, see e.g. the review [101].
There are exactly solvable polygon models, which do not satisfy an algebraic q-difference
equation, such as three-choice polygons [44], punctured staircase polygons [45], prudent
polygon subclasses [96], and possibly diagonally convex polygons. For a rigorous analysis
of the above models, it may be necessary to understand q-difference equations with more
general holonomic solutions, as q approaches unity.
Focussing on self-avoiding polygons, it might be interesting to analyse whether the
perimeter generating function of rooted self-avoiding polygons might satisfy an implicit
equation Eq. (33). Asymptotic properties of the area can possibly be studied using stochas-
tic Loewner evolution [60]. Another open question concerns the area limit law for q 6= 1
or the perimeter limit law for x 6= xc, where Gaussian behaviour is expected. At present,
even the simpler question of analyticity of the critical curve xc(q) for 0 < q < 1 is open.
Most results of this section concerned area limit laws of polygon models. Similarly,
one can ask for perimeter laws in the fixed area ensemble. Results have been given for
the uniform ensemble. Generally, Gaussian limit laws are expected away from criticality,
i.e., away from x = xc. Perimeter laws are more difficult to extract from a q-functional
equation than area laws. We will however see in the following section that, surprisingly,
under certain conditions, knowledge of the area limit law can be used to infer the perimeter
limit law at criticality.
4 Scaling functions
From a technical perspective, the focus in the previous section was on the singular be-
haviour of the single-variable factorial moment generating function gk(x) Eq. (1), and on
the associated asymptotic behaviour of their coefficients. This yielded the limiting area
distribution of some polygon models.
In this section, we discuss the more general problem of the singular behaviour of the two-
variable perimeter and area generating function of a polygon model. Near the special point
(x, q) = (xc, 1), the perimeter and area generating function P (x, q) =
m≥0 pm(q)x
n≥0 an(x)q
n is expected to be approximated by a scaling function, and the correspond-
ing coefficient functions pm(q) and an(x) are expected to be approximated by finite size
scaling functions. As we will see, scaling functions encapsulate information about the limit
distributions discussed in the previous section, and thus have a probabilistic interpretation.
We will give a focussed review, guided by exactly solvable examples, since singularity
analysis of multivariate generating functions is, in contrast to the one-variable case, not
very well developed, see [81] for a recent overview. Methods of particular interest to poly-
gon models concern asymptotic expansions about multicritical points, which are discussed
for special examples in [80, 5]. Conjectures for the behaviour of polygon models about
multicritical points arise from the physical theory of tricritical scaling [41], see the review
[61], which has been adapted to polygon models [14, 13]. There are few rigorous results
about scaling behaviour of polygon models, which we will discuss. This will complement
the exposition in [47]. See also [42, Ch 9] for the related subject of scaling in percolation.
4.1 Scaling and finite size scaling
The half-perimeter and area generating function of a polygon model P (x, q) about (x, q) =
(xc, 1) is expected to be approximated by a scaling function. This is motivated by the
following heuristic argument. Assume that the factorial area moment generating functions
gk(x) Eq. (1) have, for values x < xc, a local expansion about x = xc of the form
gk(x) =
(1− x/xc)γk,l
where γk,l = (k − θl)/φ and θl+1 > θl. Disregarding questions of analyticity, we argue
P (x, q) ≈
(−1)k
(1− x/xc)γk,l
(1− q)k
(1− q)θl
(−1)kfk,l
1− x/xc
(1− q)φ
)−γk,l)
In the above calculation, we replaced P (x, q) by its Taylor series about q = 1, and then
replaced the Taylor coefficients by their expansion about x = xc. The preceding heuristic
calculation has, for some polygon models and on a formal level, a rigorous counterpart,
see the previous section. In the above expression, the r.h.s. depends on series Fl(s) =∑
k≥0(−1)kfk,ls−γk,l of a single variable of combined argument s = (1 − x/xc)/(1 − q)φ.
Restricting to the leading term l = 0, this motivates the following definition. For φ > 0
and xc > 0, we define for numbers s−, s+ ∈ [−∞,+∞] the domain
D(s−, s+) = {(x, q) ∈ (0,∞)× (0, 1) : s− < (1− x/xc)/(1− q)φ < s+)}.
Definition 4 (Scaling function). For numbers pm,n with generating function P (x, q) =∑
m,n pm,nx
mqn, let Assumption 1 be satisfied. Let 0 < xc ≤ 1 be the radius of convergence
of P (x, 1). Assume that there exist constants s−, s+ ∈ [−∞,+∞] satisfying s− < s+ and
a function F : (s−, s+) → R, such that P (x, q) satisfies, for real constants θ and φ > 0,
P (sing)(x, q) ∼ (1− q)θF
1− x/xc
(1− q)φ
(x, q) → (xc, 1) in D(s−, s+). (34)
Then, the function F(s) is called an (area) scaling function, and θ and φ are called critical
exponents.
Remarks. i) In analogy to the one-variable case, the above asymptotic equality means
that there exists a power series P (reg)(x, q) convergent for |x| < x1 and |q| < q1, where
x1 > xc and q1 > 1, such that the function P
(sing)(x, q) := P (x, q)− P (reg)(x, q) is asymp-
totically equal to the r.h.s..
ii) Due to the region D(s−, s+) where the limit (x, q) → (xc, 1) is taken, admissible values
(x, q) satisfy 0 < q < 1 and 0 < x < x0(q), where x0(q) = xc(1− s−(1− q)φ), if s− 6= −∞.
Thus, in this case, the critical curve xc(q) satisfies xc(q) ≥ x0(q) as q approaches unity.
Note that equality need not hold in general.
iii) The method of dominant balance was originally applied in order to obtain a defining
equation for a scaling function F(s) from a given functional equation of a polygon model.
This assumes the existence of a scaling function, together with additional analyticity prop-
erties. See [84, 91, 87].
iv) For particular examples, an analytic scaling function F(s) exists, with an asymptotic
expansion about infinity, and the area amplitude series F (s) agrees with the asymptotic
series, see below.
v) There is an alternative definition of a scaling function [31] by demanding
P (sing)(x, q) ∼ 1
(1− x/xc)−θ/φ
(1− x/xc)1/φ
(x, q) → (xc, 1) (35)
in a suited domain, for a functionH(t) of argument t = (1−q)/(1−x/xc)1/φ. Such a scaling
form is also motivated by the above argument. One may then call such a function H(t) a
perimeter scaling function. If F(s) is a scaling function, then a function H(t), satisfying
Eq. (35) in a suited domain, is given by
H(t) = tθF(t−φ).
If s− ≤ 0 and s+ = ∞, the particular scaling form Eq. (34) implies a certain asymptotic
behaviour of the critical area generating function and of the half-perimeter generating
function. The following lemma is a consequence of Definition 4.
Lemma 3. Let the assumptions of Definition 4 be satisfied.
i) If s+ = ∞ and if the scaling function F(s) has the asymptotic behaviour
F(s) ∼ f0s−γ0 (s → ∞),
then γ0 = − θφ , and the half-perimeter generating function P (x, 1) satisfies
P (sing)(x, 1) ∼ f0(1− x/xc)θ/φ (x ր xc).
ii) If s− ≤ 0 and if the scaling function F(s) has the asymptotic behaviour
F(s) ∼ h0sα0 (s ց 0),
then α0 = 0, and the critical area generating function P (xc, q) satisfies
P (sing)(xc, q) ∼ h0(1− q)θ (q ր 1).
A sufficient condition for equality of the area amplitude series and the scaling function
is stated in the following lemma, which is an extension of Lemma 3.
Lemma 4. Let the assumptions of Definition 4 be satisfied.
i) Assume that the relation Eq. (34) remains valid under arbitrary differentiation w.r.t.
q. If s+ = ∞, if the scaling function F(s) has an asymptotic expansion
F(s) ∼
(−1)kfks−γk (s → ∞),
and if an according asymptotic expansion is true for arbitrary derivatives, then the
following statements hold.
a) The exponent γk is, for k ∈ N0, given by
k − θ
b) The scaling function F(s) determines the asymptotic behaviour of the factorial
area moment generating functions via
P (x, q)
)(sing)
(1− x/xc)γk
(x ր xc).
ii) Assume that the relation Eq. (34) remains valid under arbitrary differentiation w.r.
to x. If s− ≤ 0, and if the scaling function F(s) has an asymptotic expansion
F(s) ∼
(−1)khksαk (s ց 0),
and if an according asymptotic expansion is true for arbitrary derivatives, then the
following statements hold.
a) The exponent αk is, for k ∈ N0, given by αk = k.
b) The scaling function determines the asymptotic behaviour of the factorial perime-
ter moment generating functions at x = xc via
P (x, q)
)(sing)
(1− q)βk
(q ր 1),
where βk = kφ− θ.
Remarks. Lemma 4 states conditions under which the area amplitude series coincides
with the scaling function. Given these conditions, the scaling function also determines the
perimeter law of the polygon model at criticality.
In the one-variable case, the singular behaviour of a generating function translates,
under suitable assumptions, to the asymptotic behaviour of its coefficients. We sketch
the analogous situation for the asymptotic behaviour of a generating function involving a
scaling function.
Definition 5 (Finite size scaling function). For numbers pm,n with generating function
P (x, q) =
m,n pm,nx
mqn, let Assumption 1 be satisfied. Let 0 < xc ≤ 1 be the radius of
convergence of the generating function P (x, 1).
i) Assume that there exist a number t+ ∈ (0,∞] and a function f : [0, t+] → R, such
that the perimeter coefficient function asymptotically satisfies, for real constants γ0
and φ > 0,
[xm]P (x, q) ∼ x−mc mγ0−1f(m1/φ(1− q)) (q,m) → (1,∞),
where the limit is taken for m a positive integer and for real q, such that m1/φ(1−q) ∈
[0, t+]. Then, the function f(t) is called a finite size (perimeter) scaling function.
ii) Assume that there exist constants t− ∈ [−∞, 0), t+ ∈ (0,∞], and a function h :
[t−, t+] → R, such that the area coefficient function asymptotically satisfies, for real
constants β0 and φ > 0,
[qn]P (x, q) ∼ nβ0−1h(nφ(1− x/xc)) (x, n) → (xc,∞),
where the limit is taken for n a positive integer and real x, such that nφ(1− x/xc) ∈
[t−, t+]. Then, the function h(t) is called a finite size (area) scaling function.
Remarks. i) The following heuristic calculation motivates the expectation that a finite
size scaling function approximates the coefficient function. For the perimeter coefficient
function, assume that the exponents γk of the factorial area moment generating functions
are of the special form γk = (k − θ)/φ. We argue
[xm]P (x, q) ≈ [xm]
(−1)k fk
(1− x/xc)γk
(1− q)k
≈ x−mc mγ0−1
(−1)k
Γ(γk)
m1/φ(1− q)
In the above expression, the r.h.s. depends on a function f(t) of a single variable of
combined argument t = m1/φ(1− q).
For the area coefficient function, we assume that βk = kφ− θ and argue as above,
[qn]P (x, q) ≈ [qn]
(−1)k hk
(1− q)βk
(1− x/xc)k
≈ nβ0−1
(−1)k hk
Γ(βk)
nφ(1− x/xc)
In the above expression, the r.h.s. depends on a function h(t) of a single variable of
combined argument t = nφ(1− x/xc).
ii) The above argument suggests that a scaling function and a finite size scaling function
may be related by a Laplace transformation. A comparison with Eq.(20) leads one to
expect that finite size scaling functions are moment generating functions of the limit laws
of area and perimeter.
iii) Sufficient conditions under which knowledge of a scaling function implies the existence
of a finite size scaling function have been given for the finite size area scaling function [13]
using Darboux’s theorem.
A scaling function describes the leading singular behaviour of the generating function
P (x, q) in some region about (x, q) = (xc, 1). A particular form of subsequent correction
terms has been argued for at the beginning of the section.
Definition 6 (Correction-to-scaling functions). For numbers pm,n with generating function
P (x, q) =
m,n pm,nx
mqn, let Assumption 1 be satisfied. Let 0 < xc ≤ 1 be the radius of
convergence of the generating function P (x, 1). Assume that there exist constants s−, s+ ∈
[−∞,+∞] satisfying s− < s+, and functions Fl : (s−, s+) → R for l ∈ N0, such that the
generating function P (x, q) satisfies, for real constants φ > 0 and θl, where θl+1 > θl,
P (sing)(x, q) ∼
(1− q)θlFl
1− x/xc
(1− q)φ
(x, q) → (xc, 1) in D(s−, s+).
Then, the function F0(s) is a scaling function, and for l ≤ 1, the functions Fl(s) are called
correction-to-scaling functions.
Remarks. i) In the above context, the symbol ∼ denotes a (generalised) asymptotic
expansion (see also [80, Ch 1]): Let (Gk(x))k∈N0 be a sequence of (multivariate) functions
satisfying for all k the estimate Gk+1(x) = o(Gk(x)) as x → xc in some prescribed region.
For a function G(x), we then write G(x) ∼
k=0Gk(x) as x → xc, if for all n we have
G(x) =
k=0 Gk(x) +O(Gn(x)) as x → xc.
ii) The previous section yielded effective methods for obtaining area amplitude functions.
These are candidates for correction-to-scaling functions, see also [87].
4.2 Squares and rectangles
We consider the models of squares and rectangles, whose scaling behaviour can be explicitly
computed. Their half-perimeter and area generating function can be written as a single
sum, to which the Euler-MacLaurin summation formula [80, Ch 8] can be applied. We
first discuss squares.
Fact 5 (cf [49, Thm 2.4]). For 0 < x, q < 1, the generating function P (x, q) =
m=0 x
of squares, counted by half-perimeter and area, is given by
P (x, q) =
| log q|
| log x|
| log q|
+R(x, q),
with F(s) =
erfc(s), where the remainder term R(x, q) is bounded by
|R(x, q)| ≤ 1
| log x|.
Remarks. i) The remainder term differs from that in [49, Thm 2.4], where it was estimated
by an integral with lower bound one instead of zero [49, Eq. (46)].
ii) With xc = 1, s− = 0 and s+ = ∞, the function F(s) is a scaling function according to the
above definition. The remainder term is uniformly bounded in any rectangle [x0, 1)× [q0, 1)
for 0 < x0, q0 < 1, and so the approximation is uniform in this rectangle.
iii) The generating function P (x, q) satisfies the quadratic q-difference equation P (x, q) =
1+xq1/4P (q1/2x, q). Using the methods of the previous section, the area amplitude series of
the model can be derived. It coincides with the above scaling function F(s). This particular
form is expected, since the distribution of area is concentrated, p(x) = δ(x−1/4), compare
also with Ferrers diagrams.
iv) It has not been studied whether the scaling region can be extended to values x > 1
near (x, q) = (1, 1). It can be checked that the scaling function F(s) also determines
the asymptotic behaviour of the perimeter moment generating functions, via its expansion
about the origin. As expected, they indicate a concentrated distribution.
The half-perimeter and area generating function of rectangles is given by
P (x, q) =
xr+sqrs =
x(qx)r
1− qrx
We have P (x, 1) = x2/(1− x)2, and it can be shown that P (1, q) ∼ − log(1−q)
1−q as q ր 1, see
[85, 49]. The latter result implies that a scaling form as in Definition 4, with s− ≤ 0, does
not exist for rectangles. We have the following result.
Fact 6 ([49, Thm 3.4]). For 0 < q < 1 and 0 < qx < 1, the generating function P (x, q) of
rectangles satisfies
P (x, q) =
| log q|
| log q|
| log x|
− LerchPhi
qx, 1,
| log x|
| log q|
+R(x, q),
with the Lerch Phi-function LerchPhi(z, a, v) =
(v+n)a
, where the remainder term
R(x, q) is bounded by
|R(x, q)| ≤
1− qx
| log x|
(1− qx)2
| log q|
Remarks. i) The theorem implies that, for every q0 ∈ (0, 1), the function (1−qx)2P (x, q)
is uniformly approximated for points (x, q) satisfying q0 < q < 1 and 0 < x < xc(q), where
xc(q) = 1/q is the critical curve.
ii) Rectangles cannot have a scaling function F(s) as in Definition 4 with s− ≤ 0, since
the area generating function diverges with a logarithmic singularity. This is reflected in
the above approximation.
iii) It has not been studied whether the area moments or the perimeter moments at criti-
cality can be extracted from the above approximation.
iv) The relation of the above approximation to the area amplitude series of rectangles of
the previous section, F (s) = Ei(s2) es
, is not understood. Interestingly, the expansion of
F (s) about s = 0 resembles a logarithmic divergence. It is not clear whether its expansion
at the origin is related to the asymptotic behaviour of the perimeter moment generating
functions.
4.3 Ferrers diagrams
The singularity diagram of Ferrers diagrams is special, since the value xc(1) := limqր1 xc(q)
does not coincide with the radius of convergence xc of the half-perimeter generating function
P (x, 1). (The function q 7→ xc(q) is continuous on (0, 1], as may be inferred from the
exact solution.) Thus, there are two special points in the singularity diagram, namely
(x, q) = (xc, 1) and (x, q) = (xc(1), 1). Scaling behaviour about the latter point has
apparently not been studied, see also [85].
About the former point (x, q) = (xc, 1), scaling behaviour is expected. The area ampli-
tude series F (s) of Ferrers diagrams is given by the entire function
F (s) =
A numerical analysis indicates that its Taylor coefficients about s = 0 coincide with the
perimeter moment amplitudes at criticality, which characterise a concentrated distribu-
tion. There is no singularity of F (s) on the negative real axis at any finite value of s, in
accordance with the fact that the critical line at q = 1 extends above x = xc.
It is not known whether a scaling function exists for Ferrers diagrams, or whether it
would coincide with the amplitude generating function, see also the recent discussion [50,
Sec 2.3]. An rigorous study may be possible, by first rewriting the half-perimeter and
area generating function as a contour integral. A further analysis then reveals a saddle
point coalescing with the integration boundary at criticality. For such phenomena, uniform
asymptotic expansions can be obtained by Bleistein’s method [80, Ch 9.9]. The approach
proposed above is similar to that for the staircase model [83] in the following subsection.
4.4 Staircase polygons
For staircase polygons, counted by width, height, and area with associated variables x, y, q,
the existence of an area scaling function has been proved. The derivation starts from an
exact expression for the generating function, which has then been written as a complex
contour integral. About the point (x, q) = (xc, 1), this led to a saddle-point evaluation
with the effect of two coalescing saddles.
Fact 7 (cf [83, Thm 5.3]). Consider 0 < x, y, q < 1 such that the generating function
P (x, y, q) of staircase polygons, counted by width, height and area, is convergent. Set
q = e−ǫ for ǫ > 0. Then, as ǫ ց 0, we have
P (x, y, q) =
1− x− y
+α−1/2ǫ1/3
Ai′(αǫ−2/3)
Ai(αǫ−2/3)
1− x− y
 (1 +O(ǫ))
uniformly in x, y, where α = α(x, y) satisfies the implicit equation
α3/2 = log(x)
log(zm −
log(zm +
+ 2 Li2(zm −
d)− 2 Li2(zm +
where zm = (1 + y − x)/2 and d = z2m − y, and Li2(t) = −
log(1−u)
du is the Euler
dilogarithm.
Remarks. i) The characterisation of α3/2 given in [83, Eq (4.21)] has been used.
ii) The above approximation defines an area scaling function. For x = y and xc = 1/4, we
obtain the approximation [83, Eq (1.14)]
P (x, q) ∼
+ 4−2/3ǫ1/3
Ai′(44/3(1/4− x)ǫ−2/3)
Ai(44/3(1/4− x)ǫ−2/3)
as (x, q) → (xc, 1) within the region of convergence of P (x, q). It follows by comparison
that the area amplitude series coincides with the area scaling function.
iii) An area amplitude series for the anisotropic model has been given in [56], by a suitable
refinement of the method of dominant balance.
iv) It is expected that the perimeter law at x = xc may be inferred from the Taylor ex-
pansion of the scaling function F(s) at s = 0. A closed form for the moment generating
function or the probability density has not been given. The right tail of the distribution
has been analysed via the asymptotic behaviour of the moments [57, 55]. See also the next
subsection.
v) The above expression gives the singular behaviour of P (x, q) as q approaches unity,
uniformly in x, y. Restricting to x = y, it describes the singular behaviour along the line
q = 1 for 0 < x < xc. In the compact percolation picture, this line describes compact per-
colation below criticality. Perimeter limit laws away from criticality may be inferred along
the above lines. (Asymptotic expansions which are uniform in an additional parameter
appear also for solutions of differential equations near singular points [80].)
vi) By analytic continuation, it follows that the critical curve xc(q) for P (x, x, q) coincides
near q = 1 with the upper boundary curve x0(q) = (1 − s−(1 − q)2/3)/4 of the scaling
domain, where the value s− is determined by the singularity of smallest modulus of the
scaling function on the negative real axis, hence by the first zero of the Airy function. This
leads to a simple pole singularity in the generating function, which describes the branched
polymer phase close to q = 1.
4.5 Self-avoiding polygons
In the previous section, a conjecture for the limit distribution of area for self-avoiding
polygons and rooted slef-avoiding polygons was stated. We further explain the underlying
numerical analysis, following [91, 92, 93]. The numerically established form Eq. (32) implies
for the area moment generating functions for k 6= 1 singular behaviour of the form
(sing)
k (x) ∼
(1− x/xc)γk
(x ր xc),
with critical point xc = 0.14368062927(2) and γk = 3k/2− 3/2, where the numbers fk are
related to the amplitudes Ak in Eq. (32) by
Γ(γk)
For k = 1, we have γk = 0, and a logarithmic singularity is expected, g1(x) ∼ f1 log(1 −
x/xc), with f1 = A1. Similar to Conjecture 1, this leads to a corresponding conjecture
for the area amplitude series of self-avoiding polygons. If the area amplitude series was
a scaling function, we would expect that it also describes the limit law of perimeter at
criticality x = xc, via its expansion about the origin. (Interestingly, these moments are
related to the moments of the Airy distribution of negative order, see [93, 34].) This
prediction was confirmed in [93], up to numerical accuracy, for the first ten perimeter
moments. Also, the crossover behaviour to the branched polymer phase has been found
to be consistent with the corresponding scaling function prediction. As was argued in the
previous subsection, the critical curve xc(q) close to unity should coincide with the upper
boundary curve x0(q) = xc(1 − s−(1 − q)2/3), where the point s− is related to the first
zero of the Airy function on the negative real axis, s− = −0.2608637(5). The latter two
observations support the following conjecture.
Conjecture 3 ([87, 93]). Let pm,n denote the number of self-avoiding polygons of half-
perimeter m and area n, with generating function P (x, q) =
m,n pm,nx
mqn. Let xc =
0.14368062927(2) be the radius of convergence of the half-perimeter generating function
P (x, 1). Assume that
pm,n ∼ A0x−mc m−5/2 (m → ∞),
where A0 is estimated by A0 = 0.09940174(4). Let the number s− be such that (4A0)
3 πs−
coincides with the zero of the Airy function on the negative real axis of smallest modulus.
We have s− = −0.2608637(5).
i) For rooted self-avoiding polygons with half-perimeter and area generating function
P (r)(x, q) = x d
P (x, q), the conjectured form of a scaling function F (r)(s) : (s−,∞) →
R as in Definition 4 is
F (r)(s) = xc
logAi
(4A0)
with critical exponents θ = 1/3 and φ = 2/3.
ii) The conjectured form of a scaling function F(s) : (s−,∞) → R for self-avoiding
polygons is obtained by integration,
F(s) = −
log Ai
(4A0)
(1− q) log(1− q), (36)
with critical exponents θ = 1 and φ = 2/3.
Remarks. i) The above conjecture is essentially based on the conjecture of the previous
section that both staircase polygons and rooted self-avoiding polygons have, up to normal-
isation constants, the same limiting distribution of area in the uniform ensemble q = 1.
For a numerical investigation of the implications of the scaling function conjecture, see the
preceding discussion.
ii) A field-theoretical justification of the above conjecture has been proposed [16]. Also,
the values of A1 = 1/(8π) and the prefactor 1/(12π) in Eq. (36) have been predicted using
field-theoretic methods [15], see also the discussion in [93].
4.6 Models in higher dimensions
Only very few models of vesicles have been studied in three dimensions. For the simple
model of cubes, the scaling behaviour in the perimeter-area ensemble is the same as for
squares [49, Thm 2.4]. The scaling form in the area-volume ensemble has been given [49,
Thm 2.8]. The asymptotic behaviour of rectangular box vesicles has been studied to some
extent [73]. Explicit expressions for scaling functions have not been derived.
4.7 Open questions
The mathematical problem of this section concerns the local behaviour of multivariate
generating functions about non-isolated singularities. If such behaviour is known, it may,
under appropriate conditions, be used to infer asymptotic properties such as limit distri-
butions. Along lines of the same singular behaviour in the singularity diagram, expressions
uniform in the parameters are expected. This may lead to Gaussian limit laws [37]. Parts
of the theory of such asymptotic expansions have been developed using methods of sev-
eral complex variables [81]. The case of several coalescing lines of different singularities
is more difficult. Non-Gaussian limit laws are expected, and this case is subject to recent
mathematical research [81].
Our approach is motivated by certain models of statistical physics. It relies on the
observation that the singular behaviour of their generating function is described by a
scaling function. There are major open questions concerning scaling functions. On a
conceptual level, the transfer problem [35] should be studied in more detail, i.e., conditions
under which the existence of a scaling function implies the existence of the finite-size scaling
function. Also, conditions have to be derived such that limit laws can be extracted from
scaling functions. This is related to the question when can an asymptotic relation be
differentiated. Real analytic methods, in conjunction with monotonicity properties of the
generating function, might prove useful [80].
For particular examples, such as models satisfying a linear q-difference equation or di-
rected convex polygons, scaling functions may be extracted explicitly. It would be interest-
ing to prove scaling behaviour for classes of polygon models from their defining functional
equation. Furthermore, the staircase polygon result indicates that some generating func-
tions may have in fact asymptotic expansions for q ր 1, which are valid uniformly in the
perimeter variable (i.e., not only in the limit x ր xc). Such expansions would yield scaling
functions and correction-to-scaling functions, thereby extending the formal results of the
previous section. This might be worked out for specific models, at least in the relevant
example of staircase polygons.
Acknowledgements
The author would like to thank Tony Guttmann and Iwan Jensen for comments on the
manuscript, and Nadine Eisner, Thomas Prellberg and Uwe Schwerdtfeger for helpful dis-
cussions. Financial support by the German Research Council (Deutsche Forschungsge-
meinschaft) within the CRC701 is gratefully acknowledged.
References
[1] M. Abramowitz and I.A. Stegun. Handbook of Mathematical Functions with Formu-
las, Graphs, and Mathematical Tables, volume 18. National Bureau of Standards
Applied Mathematics Series, 1964. Reprint Dover 1973.
[2] D.J. Aldous. The continuum random tree II: An overview. In M.T. Barlow and N.H.
Bingham, editors, Stochastic Analysis, pages 23–70. Cambridge University Press,
Cambridge, 1991.
[3] G. Aleksandrowicz and G. Barequet. Counting d-dimensional polycubes and nonrect-
angular planar polyominoes. In Proc. 12th Ann. Int. Computing and Combinatorics
Conf. (COCOON), Taipei, Taiwan, volume 4112 of Springer Lecture Notes in Com-
puter Science, pages 418–427. Springer, 2006.
[4] D. Bennett-Wood, I.G. Enting, D.S. Gaunt, A.J. Guttmann, J.L. Leask, A.L.
Owczarek, and S.G. Whittington. Exact enumeration study of free energies of inter-
acting polygons and walks in two dimensions. J. Phys. A: Math. Gen, 31:4725–4741,
1998.
[5] N. Bleistein and R.A. Handelsman. Asymptotic Expansions of Integrals. Holt, Rine-
hart and Winston, New York, 1975.
[6] M. Bousquet-Mélou. Une bijection entre les polyominos convexes dirigés et les mots
de Dyck bilatéres. RAIRO Inform. Théor. Appl., 26:205–219, 1992.
[7] M. Bousquet-Mélou. A method for the enumeration of various classes of column-
convex polygons. Discrete Math., 154:1–25, 1996.
[8] M. Bousquet-Mélou. Families of prudent self-avoiding walks. Preprint
arXiv:0804.4843, 2008.
[9] M. Bousquet-Mélou and J.-M. Fédou. The generating function of convex polyomi-
noes: the resolution of a q-differential system. Discr. Math., 137:53–75, 1995.
[10] M. Bousquet-Mélou and S. Janson. The density of the ISE and local limit laws for
embedded trees. Ann. Appl. Probab., 16:1597–1632, 2006.
[11] M. Bousquet-Mélou and A. Rechnitzer. The site-perimeter of bargraphs. Adv. in
Appl. Math., 31:86–112, 2003.
[12] R. Brak and J.W. Essam. Directed compact percolation near a wall. III. Exact results
for the mean length and number of contacts. J. Phys. A: Math. Gen., 32:355–367,
1999.
[13] R. Brak and A.L. Owczarek. On the analyticity properties of scaling functions in
models of polymer collapse. J. Phys. A: Math. Gen., 28:4709–4725, 1995.
[14] R. Brak, A.L. Owczarek, and T. Prellberg. A scaling theory of the collapse transi-
tion in geometric cluster models of polymers and vesicles. J. Phys. A: Math. Gen.,
26:4565–5479, 1993.
[15] J. Cardy. Mean area of self-avoiding loops. Phys. Rev. Lett., 72:1580–1583, 1994.
[16] J. Cardy. Exact scaling functions for self-avoiding loops and branched polymers.
J. Phys. A: Math. Gen., 34:L665–L672, 2001.
[17] K.L. Chung. A Course in Probability Theory. Academic Press, New York, 2nd
edition, 1974.
[18] G.M. Constantine and T.H. Savits. A multivariate Faa di Bruno formula with ap-
plications. Trans. Amer. Math. Soc., 348:503–520, 1996.
[19] D.A. Darling. On the supremum of a certain Gaussian process. Ann. Probab., 11:803–
806, 1983.
[20] M.-P. Delest, D. Gouyou-Beauchamps, and B. Vauquelin. Enumeration of parallelo-
gram polyominoes with given bond and site perimeter. Graphs Combin., 3:325–339,
1987.
[21] M.-P. Delest and X.G. Viennot. Algebraic languages and polyominoes enumeration.
Theor. Comput. Sci., 34:169–206, 1984.
[22] J.C. Dethridge, T.M. Garoni, A.J. Guttmann, and I. Jensen. Prudent walks and
polygons. Preprint arXiv:0810:3137, 2008.
[23] G. Doetsch. Introduction to the Theory and Application of the Laplace Transform.
Springer, New York, 1974.
[24] M. Drmota. Systems of functional equations. Random Structures Algorithms, 10:103–
124, 1997.
[25] P. Duchon. q-grammars and wall polyominoes. Ann. Comb., 3:311–321, 1999.
[26] J.W. Essam. Directed compact percolation: Cluster size and hyperscaling. J. Phys.
A: Math. Gen., 22:4927–4937, 1989.
[27] J.W. Essam and A.J. Guttmann. Directed compact percolation near a wall. II.
Cluster length and size. J. Phys. A: Math. Gen., 28:3591–3598, 1995.
[28] J.W. Essam and D. Tanlakishani. Directed compact percolation. II. Nodal points,
mass distribution, and scaling. In Disorder in physical systems, volume 67, pages
67–86. Oxford Univ. Press, New York, 1990.
[29] J.W. Essam and D. Tanlakishani. Directed compact percolation near a wall. I. Biased
growth. J. Phys. A: Math. Gen., 27:3743–3750, 1994.
[30] J.A. Fill, P. Flajolet, and N. Kapur. Singularity analysis, Hadamard products, and
tree recurrences. J. Comput. Appl. Math., 174:271–313, 2005.
[31] M.E. Fisher, A.J. Guttmann, and S.G. Whittington. Two-dimensional lattice vesicles
and polygons. J. Phys. A: Math. Gen., 24:3095–3106, 1991.
[32] P. Flajolet. Singularity analysis and asymptotics of Bernoulli sums. Theoret. Comput.
Sci., 215:371–381, 1999.
[33] P. Flajolet, S. Gerhold, and B. Salvy. On the non-holonomic character of logarithms,
powers, and the n-th prime function. Electronic Journal of Combinatorics, 11:A2:1–
16, 2005.
[34] P. Flajolet and G. Louchard. Analytic variations on the Airy distribution. Algorith-
mica, 31:361–377, 2001.
[35] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM
J. Discr. Math., 3:216–240, 1990.
[36] P. Flajolet, P. Poblete, and A. Viola. On the analysis of linear probing hashing.
Average-case analysis of algorithms. Algorithmica, 22:37–71, 1998.
[37] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Book in preparation, 2008.
[38] B. Gittenberger. On the contour of random trees. SIAM J. Discr. Math., 12:434–458,
1999.
[39] I.P. Goulden and D.M. Jackson. Combinatorial enumeration. John Wiley & Sons,
New York, 1983.
[40] D. Gouyou-Beauchamps and P. Leroux. Enumeration of symmetry classes of convex
polyominoes on the honeycomb lattice. Theoret. Comput. Sci., 346:307–334, 2005.
[41] R.B. Griffiths. Proposal for notation at tricritical points. Phys. Rev. B, 7:545–551,
1973.
[42] G. Grimmett. Percolation. Springer, Berlin, 1999. 2nd ed.
[43] A.J. Guttmann. Asymptotic analysis of power-series expansions. In C. Domb and
J.L. Lebowitz, editors, Phase Transitions and Critical Phenomena, volume 13, pages
1–234. Academic, New York, 1989.
[44] A.J. Guttmann and I. Jensen. Fuchsian differential equation for the perimeter gen-
erating function of three-choice polygons. Séminaire Lotharingien de Combinatoire,
54:B54c, 2006.
[45] A.J. Guttmann and I. Jensen. The perimeter generating function of punctured stair-
case polygons. J. Phys. A: Math. Gen., 39:3871–3882, 2006.
[46] G.H. Hardy. Divergent Series. Clarendon Press, Oxford, 1949.
[47] E.J. Janse van Rensburg. The Statistical Mechanics of Interacting Walks, Polygons,
Animals and Vesicles, volume 18 of Oxford Lecture Series in Mathematics and its
Applications. Oxford University Press, Oxford, 2000.
[48] E.J. Janse van Rensburg. Statistical mechanics of directed models of polymers in the
square lattice. J. Phys. A: Math. Gen., 36:R11–R61, 2003.
[49] E.J. Janse van Rensburg. Inflating square and rectangular lattice vesicles.
J. Phys. A: Math. Gen., 37:3903–3932, 2004.
[50] E.J. Janse van Rensburg and J. Ma. Plane partition vesicles. J. Phys. A: Math.
Gen., 39:11171–11192, 2006.
[51] S. Janson. The Wiener index of simply generated random trees. Random Structures
Algorithms, 22:337–358, 2003.
[52] S. Janson. Brownian excursion area, Wright’s constants in graph enumeration, and
other Brownian areas. Probab. Surv., 4:80–145, 2007.
[53] I. Jensen. Perimeter generating function for the mean-squared radius of gyration of
convex polygons. J. Phys. A: Math. Gen., 38:L769–775, 2005.
[54] B.McK. Johnson and T. Killeen. An explicit formula for the c.d.f. of the l1 norm of
the Brownian bridge. Ann. Prob., 11:807–808, 1983.
[55] J.M. Kearney. On a random area variable arising in discrete-time queues and compact
directed percolation. J. Phys. A: Math. Gen., 37:8421–8431, 2004.
[56] M.J. Kearney. Staircase polygons, scaling functions and asymmetric compact perco-
lation. J. Phys. A: Math. Gen., 35:L731–L735, 2002.
[57] M.J. Kearney. On the finite-size scaling of clusters in compact directed percolation.
J. Phys. A: Math. Gen., 36:6629–6633, 2003.
[58] M.J. Kearney, S.N. Majumdar, and R.J. Martin. The first-passage area for drifted
Brownian motion and the moments of the Airy distribution. J. Phys. A: Math.
Theor., 40:F863–F869, 2007.
[59] J.-M. Labarbe and J.-F. Marckert. Asymptotics of Bernoulli random walks, bridges,
excursions and meanders with a given number of peaks. Electronic J. Probab., 12:229–
261, 2007.
[60] G.F. Lawler, O. Schramm, and W. Werner. On the scaling limit of planar self-
avoiding walk. In Fractal Geometry and Applications: A Jubilee of Benôıt Man-
delbrot, Part 2, volume 72 of Proceedings of Symposia in Pure Mathematics, pages
339–364. Amer. Math. Soc., Providence, RI, 2004.
[61] I.D. Lawrie and S. Sarbach. Theory of tricritical points. In C. Domb and J.L.
Lebowitz, editors, Phase Transitions and Critical Phenomena, volume 9, pages 1–
161. Academic Press, London, 1984.
[62] P. Leroux and É. Rassart. Enumeration of symmetry classes of parallelogram poly-
ominoes. Ann. Sci. Math. Québec, 25:71–90, 2001.
[63] P. Leroux, É. Rassart, and A. Robitaille. Enumeration of symmetry classes of convex
polyominoes in the square lattice. Adv. in Appl. Math, 21:343–380, 1998.
[64] K.Y. Lin. Rigorous derivation of the perimeter generating functions for the mean-
squared radius of gyration of rectangular, Ferrers and pyramid polygons. J. Phys.
A: Math. Gen., 39:8741–8745, 2006.
[65] M. Lladser. Asymptotic enumeration via singularity analysis. PhD thesis, Ohio State
University, 2003. Doctoral dissertation.
[66] G. Louchard. Kac’s formula, Lévy’s local time and Brownian excursion.
J. Appl. Probab., 21:479–499, 1984.
[67] G. Louchard. The Brownian excursion area: A numerical analysis. Com-
put. Math. Appl., 10:413–417, 1985.
[68] G. Louchard. Erratum: ”The Brownian excursion area: A numerical analysis”.
Comput. Math. Appl., 12:375, 1986.
[69] G. Louchard. Probabilistic analysis of some (un)directed animals. Theoret. Comput.
Sci., 159:65–79, 1996.
[70] G. Louchard. Probabilistic analysis of column-convex and directed diagonally-convex
animals. Random Structures Algorithms, 11:151–178, 1997.
[71] G. Louchard. Probabilistic analysis of column-convex and directed diagonally-convex
animals. II. Trajectories and shapes. Random Structures Algorithms, 15:1–23, 1999.
[72] A. Del Lungo, M. Mirolli, R. Pinzani, and S. Rinaldi. A bijection for directed-convex
polyominoes. Discr. Math. Theo. Comput. Sci., AA (DM-CCG):133–144, 2001.
[73] J. Ma and E.J. Janse van Rensburg. Rectangular vesicles in three dimensions.
J. Phys. A: Math. Gen., 38:4115–4147, 2005.
[74] N. Madras and G. Slade. The Self-Avoiding Walk. Birkhäuser Boston, Boston, MA,
1993.
[75] S.N. Majumdar. Brownian functionals in physics and computer science. Current
Sci., 89:2076–2092, 2005.
[76] S.N. Majumdar and A. Comtet. Airy distribution function: From the area under a
Brownian excursion to the maximal height of fluctuating interfaces. J. Stat. Phys.,
119:777–826, 2005.
[77] M. Nguy˜̂en Th´̂e. Area of Brownian motion with generatingfunctionology. In C.
Banderier and C. Krattenthaler, editors, Discrete Random Walks, DRW’03, Discrete
Mathematics and Theoretical Computer Science Proceedings, AC, pages 229–242.
Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003.
[78] M. Nguy˜̂en Th´̂e. Area and inertial moment of Dyck paths. Combin. Probab. Comput.,
13:697–716, 2004.
[79] A.M. Odlyzko. Asymptotic enumeration methods. In R.L. Graham, M. Grötschel,
and L. Lovász, editors, Handbook of Combinatorics, volume 2, pages 1063–1229.
Elsevier, Amsterdam, 1995.
[80] F.W.J. Olver. Asymptotics and Special Functions. Academic Press, New York, 1974.
[81] R. Pemantle and M. Wilson. Twenty combinatorial examples of asymptotics derived
from multivariate generating functions. SIAM Rev., 50:199–272, 2008.
[82] J. Pitman. Combinatorial Stochastic Processes, volume 1875 of Lecture Notes in
Mathematics. Springer-Verlag, Berlin, 2006.
[83] T. Prellberg. Uniform q-series asymptotics for staircase polygons.
J. Phys. A: Math. Gen., 28:1289–1304, 1995.
[84] T. Prellberg and R. Brak. Critical exponents from nonlinear functional equations for
partially directed cluster models. J. Stat. Phys., 78:701–730, 1995.
[85] T. Prellberg and A.L. Owczarek. Stacking models of vesicles and compact clusters.
J. Stat. Phys., 80:755–779, 1995.
[86] A. Rechnitzer. Haruspicy 2: The anisotropic generating function of self-avoiding
polygons is not D-finite. J. Combin. Theory Ser. A, 113:520–546, 2006.
[87] C. Richard. Scaling behaviour of two-dimensional polygon models. J. Stat. Phys.,
108:459–493, 2002.
[88] C. Richard. Staircase polygons: Moments of diagonal lengths and column heights.
J. Phys.: Conf. Ser., 42:239–257, 2006.
[89] C. Richard. On q-functional equations and excursion moments. Discr. Math., in
press, 2008. math.CO/0503198.
[90] C. Richard and A.J. Guttmann. q-linear approximants: Scaling functions for polygon
models. J. Phys. A: Math. Gen., 34:4783–4796, 2001.
[91] C. Richard, A.J. Guttmann, and I. Jensen. Scaling function and universal amplitude
combinations for self-avoiding polygons. J. Phys. A: Math. Gen., 34:L495–L501,
2001.
[92] C. Richard, I. Jensen, and A.J. Guttmann. Scaling function for self-avoiding poly-
gons. In D. Iagolnitzer, V. Rivasseau, and J. Zinn-Justin, editors, Proceedings of the
International Congress on Theoretical Physics TH2002 (Paris), Supplement, pages
267–277. Birkhäuser, Basel, 2003.
[93] C. Richard, I. Jensen, and A.J. Guttmann. Scaling function for self-avoiding polygons
revisited. J. Stat. Mech.: Th. Exp., page P08007, 2004.
[94] C. Richard, I. Jensen, and A.J. Guttmann. Area distribution and scaling function
for punctured polygons. Electronic Journal of Combinatorics, 15:#R53, 2008.
[95] C. Richard, U. Schwerdtfeger, and B. Thatte. Area limit laws for symmetry classes
of staircase polygons. Preprint arXiv:0710:4041, 2007.
[96] U. Schwerdtfeger. Exact solution of two classes of prudent polygons. Preprint
arXiv:0809:5232, 2008.
[97] U. Schwerdtfeger. Volume laws for boxed plane partitions and area laws for Ferrers
diagrams. In Fifth Colloquium on Mathematics and Computer Science, Discrete
Mathematics and Theoretical Computer Science Proceedings, AG, pages 535–544.
Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008.
[98] R.P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press,
Cambridge, Cambridge.
[99] L. Takács. On a probability problem connected with railway traffic.
J. Appl. Math. Stochastic Anal., 4:1–27, 1991.
[100] L. Takács. Limit distributions for the Bernoulli meander. J. Appl. Prob., 32:375–395,
1995.
[101] R. van der Hofstad and W. König. A survey of one-dimensional random polymers.
J. Statist. Phys., 103:915–944, 2001.
[102] C. Vanderzande. Lattice Models of Polymers, volume 11 of Cambridge Lecture Notes
in Physics. Cambridge University Press, Cambridge, 1998.
[103] L. Di Vizio, J.-P. Ramis, J. Sauloy, and C. Zhang. Équations aux q-différences.
Gaz. Math., 96:20–49, 2003.
[104] S.G. Whittington. Statistical mechanics of three-dimensional vesicles.
J. Math. Chem., 14:103–110, 1993.
	Introduction
	Polygon models and generating functions
	Limit distributions
	An illustrative example: Rectangles
	Limit law of area
	Limit law via generating functions
	Dominant balance
	A general method
	Further examples
	Ferrers diagrams
	Staircase polygons
	q-difference equations
	Algebraic q-difference equations
	q-functional equations and other extensions
	A stochastic connection
	Directed convex polygons
	Limit laws away from (xc,1)
	Self-avoiding polygons
	Punctured polygons
	Models in three dimensions
	Summary
	Scaling functions
	Scaling and finite size scaling
	Squares and rectangles
	Ferrers diagrams
	Staircase polygons
	Self-avoiding polygons
	Models in higher dimensions
	Open questions
