Jump to ContentJump to Main Navigation
The Statistical Mechanics of Interacting Walks, Polygons, Animals and Vesicles$

E.J. Janse van Rensburg

Print publication date: 2015

Print ISBN-13: 9780199666577

Published to Oxford Scholarship Online: August 2015

DOI: 10.1093/acprof:oso/9780199666577.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 26 February 2017

(p.558) Appendix D Asymptotic approximations

(p.558) Appendix D Asymptotic approximations

Source:
The Statistical Mechanics of Interacting Walks, Polygons, Animals and Vesicles
Publisher:
Oxford University Press

The Stirling approximation for the factorial [187] is given by

(D.1)
n!=2πnnnen1+112n+1288n213951840n3+O1n4.

Lower and upper bounds on the factorial are

(D.2)
2πnnnene1/(12n+1)<n!<2πnnnene1/(12n)

(see references [187, 494]), while the approximation

(D.3)
n!2n+12πnnen

is from a numerical point of view very accurate.

Stirling’s approximation can also be stated as

(D.4)
11ek122πkkkk!11ek102πk,

from which it follows, for example,

(D.5)
nn(n)n722πn110nfor ,nN0, and 0n.

More on Stirling’s approximation may be found in reference [592].

Catalan numbers are defined by

(D.6)
Cn=1n+12nn.

By putting both n2n and =n in equation (D.5) and keeping more terms in the Stirling approximation, one finds that

(D.7)
πn34nCn(198n+145128n2)<1n3M

for some fixed M>0; see lemma 4.4 in reference [488].

(p.559) D.1 Approximation of the binomial coefficient

The binomial coefficient can be approximated using approximations for the factorial. A more interesting approach is to consider random walks in Z.

Consider a random walk from 0 in Z giving left or right steps. Assign a generating variable t with each right step so that tˉ1t represents a left step.

The generating function of walks of length n is (t+tˉ)n, and the coefficient of tk is the number of walks ending at kZ from the origin. Thus, by the binomial theorem, the number of walks ending at k is n(n+k)/2, since the walk ends at k if it gives 12(n+k) right steps (and 12(nk) left steps).

Assume that t(0,1) and suppose that the walk steps to the right with probability P+=tt+tˉ and to the left with probability P=tˉt+tˉ. Let Xk be the final position of the walk after k steps. Then X0=0.

Note that Xk is a random variable and that Xn=k for k[n,n] with probability

(D.8)
Pr(Xn=k)={(n12(n+k) )tk(t+t¯)n, if mod(n+k,2)=0;0,otherwise.

The value of Pr(Xn=k) is 0 if n and k do not have the same parity (are not both even, or not both odd).

Asymptotically, n and k have the same parity with probability 12, and the distribution of Xn is given by

(D.9)
EPrXn=k=12n12(n+k)tk(t+tˉ)n1+o(1).

By the central limit theorem, the random variable Xn is asymptotically normally distributed with mean μn and variance σ2n, where

μ=X1=ttˉt+tˉ,andσ2=X12X12=t+tˉt+tˉttˉt+tˉ2=4(t+tˉ)2.

Thus, it follows that

(D.10)
EPrXn=k=e(kμn)2/2nσ22πnσ21+o(1).

This is maximal when k=μn, with μ‎ given above. In particular, if k=an, then one may solve for t to obtain

(D.11)
ta=±n+annan.

Since t(0,1), select the positive root ta+. In this event, it follows that, if t=ta+, then μn=an+O(n). For this choice of k and with t=ta+, one may solve for the binomial coefficient in equation (D.9):

(p.560)

(D.12)
n12(n+an)=2EPrXn=an(t+tˉ)ntant=ta+1+o(1).

Substitute t=ta+ into equation (D.12) to obtain the following approximation for the binomial:

Theorem D.1

The binomial coefficient is approximated by

(n12(n+an))=2n+1(11nan)an(1+o(1))2πn(11n2an2)n+an+1.

Next, replace an=2bnn for b[0,1] and simplify to obtain

(D.13)
nbn=1+o(1)2πn1nbnbn+1/211nbnnbn+1/2.

For large values of n, the above can be approximated by

(D.14)
nbn=1+o(1)2πnbbn+1/2(1b)(1b)n+1/2.

Taking n gives Corollary D.2.

Corollary D.2

The rate of growth of binomial coefficients is given by

B(b)=limnnbn1/n=1bb(1b)1b,

for b[0,1]. The function B(b) has infinite right- and left-derivatives at b=0, and b=1, respectively. Moreover, B(0)=B(1)=1, and B(12)=2B(b).

One may replace an or bn by an or bn with few, if any changes, in Corollary D.2.

More generally, for a,X>0, and b[0,a], one may consider the function

(D.15)
B(a,b)=aaXbbb(ab)ab,

which has a maximum for fixed a>0 given by

(D.16)
maxb(0,a)B(a,b)=(1+x)a,realised when b=ax1+x.

Similar to B(b) in Corollary D.2, B(a,b) has infinite right- and left-derivatives at b=0, and b=a, for fixed a,x>0.

(p.561) The function for x>0, and a(0,1), defined by

(D.17)
C(a)=(1a)1axaaa(12a)12a,

similarly has the maximum

(D.18)
maxa(0,1)C(a)=121+1+4x,realised when a=1+4x121+4x

for fixed a>0. The function C(a) has infinite left- and right-derivatives at a=0, and a=1, respectively.

Lemma D.3

Let 0<q< and suppose γ[0,qq+1]. Then

lim supni=0γnniqi1/nqγγγ(1γ)1γ.

Proof

Let p=qq+1 so that 0γp<1. Then

i=0γnniqi=i=0γnnipi(1p)ni.

Consider p to be the probability that a biased tossed coin will land heads. Let η‎ be the number of heads in n tosses of the coin. Then the probability that there are at most γn heads in n tosses is

Pr(ηγn)=i=0γnnipi(1p)ni.

If ζ is a random variable equal to 1 if ηγn, and 0 otherwise, then the expectation of ζ is Eζ=Pr(ηγn. By Jensen’s inequality,

EζEet(γnη)=etγnEetη=etγnpet+(1p).

The right-hand side is a minimum when γn(1p)=p(nγn)et. Thus, substituting for t gives

(D.19)
i=0γnnipi(1p)nip1nγnγn1p11nγnnγn.

Substitute p=qq+1, take the power 1n and take n.

This completes the proof.

(p.562) D.2 Approximation of trinomial coefficients

Trinomial coefficients are defined by

(D.20)
(t+1+tˉ)n=j=nnnj2tj.

The term ‘trinomial coefficient’ is used as in reference [9]; that is, ‘trinomial coefficient’ is used synonymously with ‘central trinomial coefficient’.

Trinomial coefficients are given in terms of binomial coefficients by

(D.21)
nm2=nm2=k=0(nm)/2n!k!(m+k)!(nm2k)!.

The properties of a random walker in Z can be used to find approximations to trinomial coefficients. Let the position of the walker be xn and suppose it gives right or left unit length steps in Z, or a neutral step where it stays put at xn, so that xn+1=xn±1, or xn+1=xn.

Let x0=0 and suppose the random walker gives right, neutral and left steps with probabilities P+, P0 and P, respectively. Suppose t(0,1), let tˉ=1t and let

 P+=tt+1+tˉP0=1t+1+tˉ; and P=tˉt+1+tˉ .

The probability that xn=k for k[n,n] is given by

(D.22)
Prxn=k=nk2tk(t+1+tˉ)n,

since xn=k if the walk gives k+p right steps and p left steps, and since the number of walks ending at k is exactly given by the trinomial coefficient.

The central limit theorem states that the random variable xn is asymptotically normal with mean μn and variance σ2n, where

(D.23)
μ=x1=ttˉt+1+tˉ,

and

(D.24)
σ2=x12x12=t+tˉt+1+tˉttˉt+1+tˉ2=t+4+tˉ(t+1+tˉ)2.

Thus, it follows that

(D.25)
P(xn=k)=e(kμn)2/2nσ22πnσ21+o(1).

Substitute k=αn, substitute μ=ttˉt+1+tˉ and solve for t:

(p.563)

(D.26)
tα±=αn±4n23αn22(nαn).

Since t(0,1), select tα+ so that μn=αn+O(n) and solve for the trinomial coefficient in equation (D.22). If k=αn, and t=tα+, then this gives

(D.27)
nαn2=P(xn=αn)(tα++1+tα+ˉ)n(tα+)αn1+o(1).

Simplification gives theorem D.4.

Theorem D.4

The trinomial coefficient is approximated by

nαn2=2αn2πnAαn+1/2(1+o(1))Bαnαn+1/2Cα1/4Dαn+αn+1/2,

where

Aα =43n αn+43n2αn2;             Bα=11n αn;Cα =43n2 αn2;  and Dα=1n αn+43n2αn2.

For large values of n, one may use Corollary D.5.

Corollary D.5

The trinomial coefficient

nαn2=2αn2πn(1α)(1α)n+1/2(43α+β)n+1/2(1+o(1))β1/4(α+β)(1+α)n+1/2,

where β=43α2.

The rate of exponential growth of the trinomial coefficient is given by Corollary D.6.

Corollary D.6

The limit

  limn(nαn)21/n=2α(43α+43α2)(1α)1α(α+43α2)1+α =(2α2α43α2)α/2(139α2+(73α2)43α2)1/32α/2(1α)(1+α)1+α

The rate of growth of the generating function of trinomial coefficients is defined by

(D.28)
F(z)=limnj=0nnj2zj1/n.

Given an n, there is a value of j, say j=jn, which maximises the summand.

(p.564) Assuming that jn=ϵmn+o(n), where ϵm(0,1) is a function of z, it follows that

(D.29)
F(z)=limnnjn2zjn1/n.

By replacing jn in the above by ϵn+o(n) and then using equation (D.6) when taking n in equation (D.29), it follows that

(D.30)
F(z)=sup0<ϵ<1zϵ2ϵ43ϵ+43ϵ21ϵ1ϵϵ+43ϵ21+ϵ.

By differentiating and solving for ϵ, the supremum is realised when

(D.31)
ϵ=ϵm=zzˉz+1+zˉ=μ in equation (D.23).

It follows that ϵm(0,1) if z>1, and so the supremum is achieved when ϵm=0 when z1 at ϵm. These results show that, after simplification,

Theorem D.7

The function F(z) is given by

(D.32)
F(z)={z+1+zˉ,if z(1,);3,if z[0,1],

where zˉ=1z.

D.3 The Euler-Maclaurin formula

The Euler-Maclaurin formula (see for example [273]) is a useful method for approximating series by integrals. The formula is useful because it gives precise remainders, allowing estimates of the error in the approximation.

Theorem D.8 (Euler-Maclaurin)

If fC2m[0,N] for some m,NN, and both N>0 and m1, then

n=0Nf(n)=0Nf(x)dx+12f(0)+f(N)+n=1mB2n(2n)!f(2n1)(N)f(2n1)(0)+Rm

where the remainder term is given by

Rm=0NBn(xx)(2m)!f(2m)(x)dx.

The function Bn(x) is the n-th Bernoulli polynomial; Bn=Bn(0), and Bn(xx) is the n-th periodic Bernoulli polynomial.

(p.565) In some applications the remainder term Rm approaches 0 with m (derivatives of f exist to all orders), and one may able to show that the series is convergent.

The remainder term can be bounded by

Rm2ζ(2m)(2π)2m0Nf(2m)(x)dx.

The Bernoulli functions are defined by the recurrence ddxBn(x)=nBn1(x), with B0(x)=1, and 01Bn(x)dx=0, for n1. The first few are given by B1(x)=x12; B2(x)=x2x+16; B3(x)=x332x2+12x; and B4(x)=x42x3+x2130.

The Bernoulli numbers Bn are defined by the exponential generating function tet1=m=0Bmm!tm. Notably, B2n+1=0 if n1 (that is B3=B5=B7==0), and the first few non-zero Bernoullui numbers are B1=12; B2=16; B4=130; and B6=142.

The Stirling approximation for n! is obtained as follows. Consider the integral

01(z+x)2dx=1z.

Applying the Euler-Maclaurin formula to the integral on the left-hand side gives

1z=12z2+n=11(z+n)2n=1Bnz2n+1.

The infinite series in the above is a polygamma function and

n=11(z+n)2=d2dz2logz!=1z12z2+n=1B2nz2n+1.

Take the anti-derivative of this twice to obtain

logz!=C+z+12logzz+n=1B2n2n(2n1)z2n1.

The constant C is computed from the Legendre duplication formula

22z+1z!(z+12)!=π(2z+1)!.

This gives C=12log(2π). Finally,

(D.33)
logz!=12log(2π)+z+12logzz+n=1B2n2n(2n1)z2n1.

This is an asymptotic series approximating logz!. By truncating the infinite series, the error in the approximation is less than the magnitude of the first omitted term. If the series is discarded in its entirety, then the Stirling approximation in equation (D.1) is found.

(p.566) D.4 Saddle point approximations of the integral

Suppose that f is an analytic complex function of the complex variable z=x+iy. Then f=u+iv, and {u,v} satisfies the Cauchy-Riemann equations. Consequently, it may be shown that u satisfies the Laplace equation:

(D.34)
2x2u+2y2u=0.

At any stationary point of f, if 2x2u>0, then 2y2u<0. That is, if f is real valued, then its stationary points are necessarily saddle points.

The function f may be approximated in the vicinity of a saddle point z0 by

(D.35)
f(x)f(z0)+12f(z0)zz02.

This approximation of f near its saddle points allows the approximation of integrals of the form

(D.36)
I=abg(z)eNf(z)dz,

where N is large, and g(z) is slowly varying.

Insert the approximation of f in the above and replace g(z)g(z0). Deform the contour of integration from a to b into a contour C in the complex plane passing through z0. This gives

(D.37)
Ig(z0)eNf(z0)CeN2f(z0)zz02dz.

Put zz0=reiϕ and let f(z0)=f(z0)eiθ. The integration will be along r, with ϕ‎ fixed at a convenient value, namely, θ+2ϕ=π. The integration is approximated by integrating from r= to r=. These substitutions simplify the integral above into a Gaussian integral:

(D.38)
Ig(z0)eNf(z0)eiϕeN2f(z0)r2dr.

Evaluating the integral gives the saddle point approximation

(D.39)
I2πg(z0)eNf(z0)eiϕNf(z0).

The phase ϕ‎ is determined by solving for ϕ=πθ2.

It is possible to refine the above approximations by keeping more terms in the expansion (D.35). This approximation also has the implicit assumption that the only significant contribution to the integral along the contour C is from the vicinity of the saddle point (this means that u(z0)u(z) if |z0z| is ‘large’. This may not be necessarily the case. For more on this method, which is related to steepest descent methods, see, for example, reference [13].

(p.567) D.5 Asymptotic formulae for the q-factorial and related functions

The q-deformations of special functions are obtained from an arithmetic based on q-integers, and defined by

(D.40)
[n]q=1qn1q=1+q+q2++qn1

where qC. These q-integers retain many of the properties of the usual integers. A q-integer is sometimes called a q-bracket or a basic integer.

The q-Pochhammer function is a finite product formally defined by

(D.41)
(t;q)n=k=0n1(1tqk)=(1t)(1tq)(1tq2)(1tqn1)=(t;q)(tqn;q),

(t;q) is an infinite product.

The q-Pochhammer function (t;q) is an analytic function inside the unit disk in the q-plane. Euler’s function is defined by (q;q). Observe that (q)=(q;q) and

(D.42)
(q)n=k=1n(1qk)=k=11qk1qn+k=(q;q)(qn+1,q)=(1q)(1q2)(1qn).

Put n= in the above to find an infinite product representation of (q).

A partition identity (see for example reference [8]) shows that

(D.43)
e(t,q)=k=0tk(q)k=1(t;q).

Note that the usual factorial in the definition of the exponential is replaced by (q)k. For this reason, e(t,q) is sometimes called the q-exponential; however, see equation (D.46) below.

(p.568) The natural definition of the q-analogue of the factorial is in terms of q-integers:

(D.44)
[n]q!=(q;q)n(1q)n=(q;q)(1q)n(qn+1,q),

and these are also called basic factorials or Gaussian factorials. This gives rise to the q-analogue of the gamma function or the q-gamma function:

(D.45)
Γq(z)=(q;q)(1q)1z(qz;q)

which becomes Γq(k+1)=[k]q! if kN. Observe that, if q1 in each of the above, then the usual integers, factorials and gamma functions are recovered.

The natural definition of the q-exponential is

(D.46)
eqt=k=0tk[k]!=1((1q)t;q),

or, alternatively,

(D.47)
Eqt=k=0qk2tk[k]!=((1q)t;q).

Observe that Eqt=e1/qt=1/eqt.

These definitions of the exponential give rise to q-analogues of the trigonometric functions sine and cosine. There are also q-analogues of special functions. For example, q-deformed Bessel functions are defined by

(D.48)
J(p,q,t)=m=0qm2(t)m(p;q)m(q;q)m.

More on q-calculus can be found, for example, in reference [345].

D.5.1 The q-binomial coefficient

The above definitions extend to the q-binomial coefficient, defined by

(D.49)
nk=(q)n(q)k(q)nk,

and, if nN, and kN, then this becomes

(D.50)
nk=[n]q![k]q![nk]q!.

Observe that [n]q=n1 and that nk satisfies the following q-binomial identities:

(D.51)
nk=qkn1k+n1k1,andnk=n1k+qnrn1k1.

Lemma D.9 is not obvious.

Lemma D.9

If nN0, and kN0, then the Gaussian binomial coefficient is a polynomial of degree k(nk) with non-negative integer coefficients. In other words,

nk=α=0k(nk)Nnkiqα,

where NnkαN0.

(p.569)

Proof

Observe that n0=1 and is a polynomial of degree 0.

The proof proceeds by induction.

Suppose that mj is a polynomial with coefficients in N0 and with degree j(mj), where mn, and jk. By equation (D.51),

n+1k=qknk+nk1=α=0k(nk)Nnkαqα+k+α=0(k1)(nk+1)Nn(k1)αqα.

The largest power of q in the above is k+k(nk)=k(n+1k) as required, and the coefficients of qα on the right-hand side are sums over integers in N0.

Similarly, again by equation (D.51),

nk+1=n1k+qk+1n1k1.

Hence, if n1k+1 is a polynomial in q of degree (k+1)((n1)(k+1)) and with coefficients in N0, then nk+1 is a polynomial in q of degree (k+1)(n(k+1)) and with coefficients in N0. Notice that k+1k+1=1.

The q-binomial theorem is usually stated as

(D.52)
n=0(t;q)n(q;q)nzn=(tz;q)(z;q)

but it is also encountered as

(D.53)
(tq;q)n=k=0nnkqn+12tk.

The proof of the last equality proceeds by the counting of partitions.

The q-binomial theorem gives rise to the Jacobi triple product identity

(D.54)
(tq;q)(tˉ,q)(q;q)=n=qn+12tn,

where tˉ=1t.

The identity

(D.55)
1(t;q)n=k=0n1+kktk

is also useful [8]. By the q-binomial theorem in equation (D.53), it follows that

(D.56)
k=0n1+kk(tq)k1=k=0nnkqn+12tk.

D.5.2 Directed paths and the q-binomial coefficient

There is a close connection between Gaussian binomial coefficients and D.9 (see reference [467]). Consider the square lattice L2 and let L+2 be the positive half-lattice with the boundary L+2 as the x-axis. In figure D.1, directed paths from the origin in L+2 give only north and east steps. The path oversteps area α‎ in the first quadrant of L2 underneath the path and to the left of the endpoint of the path.

Then the number of such paths of length n is related to Nnki and Gaussian binomial coefficients (see lemma D.9) by the following lemma. (p.570)

Appendix D Asymptotic approximations

Fig. D.1 A staircase walk from the origin to the point (r,nr) overstepping an area α‎.

Lemma D.10

The number of square lattice directed paths in L2, of length n, from the origin to the point (r,nr), giving only north and east steps and which overstep an area of size α‎ in the first quadrant of L2 is Nnrα.

Proof

This is true for any α‎ if n=1, and 0r1. Suppose that the lemma is true for any mn.

Consider m=n+1. By equation (D.51),

α=0r(n+1r)N(n+1)rαqα=α=0r(nr)Nnrαqα+α=0(r1)(nr+1)Nn(r1)αqα+n+1r.

If coefficients of qα are compared, then

N(n+1)rα=Nnrα+Nn(r1)(α+rn1).

This result is interpreted in figure D.2. By the induction hypothesis, the term Nnrα counts the number of walks of length n, from (0,0) to (r,nr), and overstepping area α‎.

Appending a vertical step to paths turn these into walks of length n+1 which contribute towards N(n+1)rα

In a similar fashion, Nn(r1)(α+rn1) counts the number of walks from the origin to (r1,nr+1) and which enclose the area α+rn1. If a horizontal edge is appended from (r1,nr+1) to (r,nr+1), then it encloses area α‎. Thus, N(n+1)rα counts the number of walks from (0,0) to (r,nr+1) and which overstep area α‎.

(p.571)
Appendix D Asymptotic approximations

Fig. D.2 Any staircase walk of length n+1 from the origin to (r,n+1r) and which oversteps area α‎ has either a north step or an east step as its last step. If the last step was north, then it can be deleted to find Nnrα. If it was to the east, then deleting the last step also removes the last column, and this gives Nn(r1)(α+rn1).

Putting q=1 gives the corollary

(D.57)
nr=α=0r(nr)Nnrα.

Figure D.1 is also a Ferrer’s diagram of a partition. Thus, let the number of partitions of αN into r parts with largest part k be denoted ρk,r(α). Then ρk,r(α)=N(k+r)rα.

The generating function of ρk,r(α) for fixed k and r is

(D.58)
α=0krρk,r(α)qα=k+rr.

See reference [531] for a different proof of this result.

The generating function of partitions follows from this as

(D.59)
Vp(t,q)=k=1r=1k+rrt2(k+r)=k=1r=1k1krt2k,

where t is the generating variable conjugate to perimeter length.

D.5.3 Theta functions, and partial theta functions

The Jacobi θ‎-function is defined by

(D.60)
θ(t,q)=n=tnqn2;

(p.572) ϕ(q)=θ(1,q) is the Ramanujan θ‎-function. The Jacobi triple product identity may be cast as

(D.61)
(q2;q2)(tq;q2)(tˉq;q2)=n=tnqn2.

By expanding the second and third products on the left-hand side, this becomes

(D.62)
n=tnqn2=(q2;q2)k=11+(t+tˉ)q2k1+q4k2=(q2;q2)k=11+2cos(2πz)q2k1+q4k2,

where t=e2πiz. Putting t=1 gives

(D.63)
n=qn2=(q2;q2)(q;q2)2=(q)(q;q).

This last identity may also be obtained from the Ramanujan θ‎-function, which is defined as

(D.64)
f(a,b)=n=an(n+1)2bn(n1)2.

The Jacobi triple product becomes

(D.65)
(a;ab)(b;ab)(ab;ab)=n=an(n+1)2bn(n1)2.

By choosing a=b=q in the above, Ramanujan’s ϕ‎-function ϕ(q)=f(q,q) is recovered:

(D.66)
ϕ(q)=n=qn2=(q2;q2)(q;q2)2=(q;q2)(q2;q2)(q2;q2)(q;q2).

Other identities may be recovered; for example, if a=q, and b=q3, then

(D.67)
n=qn+12=n=qn(n+1)2=(q2;q2)(q;q2),

and, if a=q, and b=q2, then

(D.68)
n=(1)nqn(3n1)2=(q;q).

This identity is the famous pentagonal number theorem [184].

(p.573) The summation in the series definitions of θ‎-functions given above is over all of Z. It may in some instances be necessary to have to have the summation only over N. This restriction gives rise to partial θ-functions. An example is encountered in equation (D.63), which may be stated as

(D.69)
n=0qn2=121+ϕ(q)=121+(q2;q2)(q;q2)2.

This is related to Gauss’s formula (see for example [8]):

(D.70)
n=0qn+12=n=0qn(n+1)2=(q2;q2)(q;q2).

More generally, a partial θ‎-function has the form

(D.71)
θp(t,q)=n=0(1)ntnqn2.

Some identities for partial θ‎-functions are known. For example, in reference [10] it is shown that

(D.72)
θp(t,q)=(q)(t)n=0qn(t)n(q)n=(t)n=0tnqn2(t)n(q)n.

D.5.4 Asymptotics for (q;q)

A good starting point is the identity in equation (D.68). The left-hand side converges quickly if |q|1, but, when q is close to 1, another approach is necessary.

Theorem D.11 (Poisson’s sum formula)

Suppose that f is continuous for all tR, and k=f(t+k) is uniformly convergent for t[0,1]. Then

n=f(t+n)=n=e2πintf(x)e2πinxdx,

for all values of t where the right-hand side converges.

Proof

The function

h(t)=k=f(t+k)

is continuous and periodic with period T=1. In a Fourier expansion of h the coefficients would be

an=01h(s)e2πinsds.

Moreover, by Fejér’s theorem, n=ane2πint is Cesàro summable to h(t) for all t (since h is continuous and periodic).

(p.574) Hence, by replacing h in the last integral with the uniformly convergent series over f, one obtains

k=01f(s+k)e2πinsds=k=kk+1f(s)e2πinsds=f(s)e2πinsds.

The right-hand side evaluates to an, and therefore the Fourier series for h(t) is as claimed above.

Corollary D.12 (The θ‎-transformation formula)

For all values of t,sC, such that Re(s)>0,

n=eπs(n+t)2=1sn=eπn2s+2πint.

Proof

Put f(t)=eπst2 in theorem D.11. Then n=f(t+n) converges uniformly for t[0,1], and Re(s)>0. The Poisson sum formula gives

(D.73)
n=eπs(t+n)2=n=e2πinseπsx2+2πinxdx,

where the integral above gives the Fourier coefficients. It remains to evaluate these coefficients.

Assume that s>0 and substitute y=sx:

eπsx2+2πinxdx=eπn2sseπyins2dy=eπn2ssinsinseπy2dy.

The contour integral on the right evaluates as

insinseπy2dy=eπy2dy=1,

using Cauchy’s theorem. This completes the evaluation of the Fourier coefficients in equation (D.73).

Substitution of the result and replacing nn in the summation on the right-hand side of equation (D.73) completes the proof.

Corollary D.12 gives a suitable expansion for (q;q); see, for example, reference [359] for an expansive treatment.

Theorem D.13

For Euler’s function,

(q;q)=rq1242πlogqn=rn(6n+1)r(3n+1)(2n+1),

where r=e4π2logq. For q(0,1) the right-hand side converges quickly.

(p.575)

Proof

Put t=16+π3ilogq, put q3=e2πs and define r by (logr)(logq)=4π2. Substitute these variables in the left-hand side of Corollary D.12 and then simplify. This shows that

n=eπs(n+t)2=qr1/24eiπ/6n=(1)nq3n2/2+n/2.

Comparison to equation (D.68) gives

(q;q)=rq1/24eiπ/6sn=eπn2/s+2πint.

It remains to simplify the right-hand side.

Substitute t and s on the right-hand side and simplify:

n=eπn2/2+2πint=n=rn2/6+n/6e2πin/6.

The sum on the right-hand side is absolutely convergent if |r|<1. Collecting terms,

(q;q)=rq1/24eiπ/6sn=rn2/6+n/6e2πin/6.

The right-hand side is evaluated by summing along n in residue classes modulo 6: replace n6n+ and sum over ℓ from 3 to 2.

(q;q)=rq1/24eiπ/6sn==32r(6n+)2/6+(6n+)/6e2πi(n+/6).

Comparing the terms in the sum over ℓ shows that the terms for =2 and =1 cancel. The terms for both =3 and =2 are equal under the exchange of nn, up to phase factors. This is similarly the case for =1 and =0. This simplifies the expressions above to

(q;q)=(rq)1/242sn=(r(3n+1)(2n+1)cos(2π6(6n+52))                                             +rn(n+6)cos(2π6(6n+12))).

Evaluate the cosines and replace s=3logq2π to complete the proof.

Taking logarithms of the result in theorem D.13 and keeping the n=0 term gives the following asymptotic formula for (q;q) as q1:

Theorem D.14

The function log(q;q)=π26logq+12log2πlogq+O(logq).

(p.576) This gives the approximation

(D.74)
(q;q)=2πlogqeπ26|logq|+O(log(q))as q1.

For additional results, see, for example, the paper by Moak [425].

D.5.5 Asymptotics for (t;q)

First examine the limit limn(t;q)n for q(0,1) and assume that 0<tqk<1 for all k1.

Theorem D.15

If q<1, and 0<tqk<1 for all k1, then 0<(t;q)1.

Proof

Surely, 0(t;q)n1 for all n0, and (t;q)n is monotone decreasing, so the limit limn(t;q)n exists and is less than or equal to 1.

It remains to show that the limit is not 0.

For any positive p<1, log(1p)p1p. Moreover, for any small ϵ>0, there exists a N0N such that 0<1ϵ<1tqk if k>N0, since q<1 and since t0. Hence, log(1tqk)tqk1ϵ if k>N0.

Thus, assume that n>N0+1; then

(t;q)n=expk=0n1log(1tqk)expk=0N0log(1tqk)+t1ϵi=N0+1n1qk,if n>N0+1;=expk=0N0log(1tqk)+tq1ϵ1qnN011q.

Take n to obtain

limn(t;q)nexpk=0N0log(1tqk)+tq(1ϵ)(1q)

which is greater than 0.

Asymptotic approximations for the q-Pochhammer function (t;q)n can be determined using the Euler-Maclaurin theorem. This can be determined directly or indirectly by first determining an approximation for the q-gamma function (see, for example, references [425] and [468]).

Define Li2 to be the dilogarithm:

(D.75)
Li2=k=1zkk2=z01tlog(1t)dt.

(p.577) Theorem D.16

If 0<t<1, and 0<q<1, then

log(t;q)n=1logqLi2(t)Li2(tqn1)+12log(1t)log(1tqn1)+R1,

where

R143|t|2|logq|1qn1(1t)(1tqn1).

For fixed t<1, this term vanishes as q1.

Proof

The Euler-Maclaurin formula gives

log(t;q)n=0n1log(1tqx)dx+12log(1t)+log(1tqn1)+R1.

where

R1=120n1B2B2(xx)d2dx2log(1tqx)dx.

The integral over log(1tqx) can be done by expanding first the logarithm and then integrating term by term; the result is a sequence of terms giving rise to dilogarithms and logarithms.

It remains only to examine the remainder. Observe that

B2B2(xx)=13(xx)(xx)243if x[0,n1].

Next, consider the derivative in R1 above and compute it to see that

|R1|120n1B2B2(xx)tqx(logq)2(1tqx)2dx230n1tqx(logq)2(1tqx)2dx=23t2|logq|tqn1tdz(1z)2=23t2|logq|1qN(1t)(1tqN).

This completes the proof.

Taking n in theorem D.16 gives the following corollary:

Corollary D.17

If ϵ>0, and t[0,1ϵ], and if q(0,1), then

log(t;q)=1logq(Li2(t)π26)+12log(1t)+R1,

or if Li2(t)+Li2(1t)=π26log(t)log(1t) is used, then

log(t;q)=1logqLi2(1t)log(t)log(1t)+12log(1t)+R1,

where R1 approaches 0 uniformly as q1 for any t[0,1ϵ].

(p.578) By this corollary,

(D.76)
(t;q)=1te1|logq|Li2(t)π26+R1,

where R10 uniformly as q1. For example, if t=qn<q<1 for nN, then

(D.77)
(qn;q)=1qne1|logq|Li2(qn)π26+R1.

D.6 Asymptotics from the generating function

If the generating function g(t) of a function qn on N, defined by

(D.78)
g(t)=n=0qntn,

is known, then qn may in principle be found by using Darboux’s theorem. Darboux’s theorem has the following formulation (see, for example, reference [443]).

Theorem D.18 (Darboux’s theorem)

Let ψ(t) be an analytic function with Laurent expansion

ψ(t)=n=antn,

in the annulus 0<|t|<r.

Let χ(t) be a function which is analytic in 0<|t|<r and with Laurent expansion given by

χ(t)=n=bntn,

in 0<|t|<r.

Suppose that the difference of the m-th derivatives of ψ(t) and χ(t) has a finite number of singularities at t=tj such that

ψ(m)(t)χ(m)(t)=O([ttj]σj1),

for some positive constants σj, as ttj. Then

an=bn+o(rnnm)as n.

(p.579) D.7 Convergence of continued fractions

Finite fractions are denoted by

(D.79)
sn=Kk=1nakbk=a1b1+a2b2+a3b3+...bn.

(For example, S1=a1b1, and S2=a1b1+a2b2).

Taking n gives the infinite continued fraction S. The n-th approximation to S is Sn(s), obtained by truncating the fraction at n and putting bn=c:

(D.80)
sn(c)=Kk=1nakbk=a1b1+a2b2+a3b3+...c.

Useful theorems on the convergence of continued fractions are the following.

Theorem D.19

(Pringsheim [474]) Let an and bn be sequences in R such that |bn|>|an|+1. Then the continued fraction k=1akbk converges absolutely to fR with 0<|f|<1.

Theorem D.20

(Worpitzky [572]) Let an be a sequence in C and let K be a continued fraction given by

K=Kk=1ak1=a11+a21+a31+a41+....

If 0<|an|14 for all n2, then K converges absolutely and 0<|K|12. Moreover, if, in addition, Sn(b)=Kk=1nak1, where an=b and |b|12 is the n-th approximant of K, then 0<|Sn(b)|12.

Theorem D.21 (Van Vleck [554])

If rn>0, then a condition that is necessary for the continued fraction

(p.580)

K=Kk=1ak1=11+r2eiθ21+r3(1r2)eiθ31+r4(1r3)eiθ41+....

to converge for all values of θn is that the series

1+j=2=2jr1r

is convergent. This condition is also sufficient if rn<1 for all values of n.