Staircase Polygons, Elliptic Integrals and Heun Functions

Anthony Guttmann

Department of Mathematics, University of Melbourne, Australia

Algorithms Seminar

December 2, 1996

[summary by Dominique Gouyou-Beauchamps]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
We discuss the perimeter generating function of d-dimensional staircase polygons and relate these to the generating function of the square of the d-dimensional multinomial coefficients. These are found to satisfy differential equations of order d-1. The equations are solved for d<5, and the singularity structure deduced for all values of d. The connection with complete elliptic integrals, Heun functions and lattice Green functions is also found. The original article by A. J. Guttmann and T. Prellberg can be found in [4].



1   Staircase polygons

Any d-dimensional staircase polygon [3, 6] of perimeter 2n may be considered as made up of two paths, each of length n, with common origin and end point, and with successive steps joining neighbouring points on the lattice Zd. The two paths are constrained to have no point in common other than the origin and the end point, and successive steps must be in the positive direction in all d coordinates. The number of paths of length n having ki steps in direction i (1£ i£ d) is (
k1+... +kd
k1,... ,kd
) with k1+... +kd=n. Then the number of pairs of such paths is (
n
k1,... ,kd
)2. The generating function Zd(x1,... ,xd) for these pairs of paths, including a walk of zero length for later convenience, is
Zd(x1,... ,xd)=
¥
å
k1,... ,kd=0
æ
è
k1+... +kd
k1,... ,kd
ö
ø
2 x
2k1
 
1
··· x
2kd
 
d
.
This generating function produces a chain of staircase polygons, each links of which comprises either a staircase polygon or a double bond. The generating function for double bonds is åi=1dxi2 and we denote the generating function of staircase polygons in d dimensions by Gd(x1,... ,xd). Let H(x1,... ,xd) be the generating function for a link
H(x1,... ,xd)=
d
å
i=1
xi2+2Gd(x1,... ,xd).
Due to the orientability of walks, each staircase polygon is produced twice in the definition of H(x1,... ,xd). We set x1=... =xd=x. The construction ``chain of'' corresponds to the functional relation
Z(x)=
1
1-H(x)
.
Hence, by inspection
Gd(x) =
1
2
æ
ç
ç
è		 1-dx2-
1
Zd(x)
ö
÷
÷
ø		 =
1
2
æ
ç
ç
ç
ç
ç
è		 1-dx2- æ
ç
ç
è
¥
å
n=0
Sn(d)x2n ö
÷
÷
ø
-1



 
ö
÷
÷
÷
÷
÷
ø		     (1)
with
Sn(d)=
 
å
k1+... +kd=n
æ
è
n
k1,... ,kd
ö
ø
2.
For d=1 we get Sn(1)=1 and G1(x2)=0. For d=2 from the identity åk=0n(
n
k
)2=(
2n
n
) we find
G2(x2)=
1
2
( 1-2x2-(1-4x2)1/2 ) .
For d>2 we observe the recursion
Sn(d)=
n
å
m=0
æ
è
n
m
ö
ø
2Sm(d-1).
By expansion and inspection (aided by computer algebra), we get
nSn(2)=2(2n-1)Sn-1(2),     n2Sn(3)=(10n2-10n+3)Sn-1(3)-9(n-1)2Sn-2(3).
These recurrences can be reexpressed as differential equations
Z2'(x)-
2
1-4x
Z2(x)=0 ,
Z3''(x)+
1-20x+27x2
x(1-x)(1-9x)
Z3'(x) -
3(1-3x)
x(1-x)(1-9x)
Z3(x)=0 ,
Z4'''(x)+
3(1-30x+128x2)
x(1-4x)(1-16x)
Z4''(x)+
1-68x+448x2
x2(1-4x)(1-16x)
Z4'(x)-
4
x2(1-4x)
Z4(x)=0.
These differential equations are all Fuchsian, with regular singular points at the origin, at infinity, and at x=1/d2, 1/(d-2)2, 1/(d-4)2,..., the sequence of singular points terminating at x=1 (d odd) or x=1/4 (d even). Moreover, the solutions that are regular in the neighbourhood of x=0 have singularities with exponents (d-3)/2 at the other regular singular points, so that, in particular, the dominant singular behaviour is given by
Zd(x2)~
ì
í
î
Bd(1-d2x2)(d-3)/2, d even,
Bd(1-d2x2)(d-3)/2ln (1-d2x2), d odd.
where Bd is a constant whose amplitude can be calculated.

2   Heun functions and lattice Green Functions

For d=3 the differential equation can be rewritten as Heun's equation [7], a generalization of the 2F1 hypergeometric equation to the case of four, rather than three, regular points. We denote the solution as
Z3(x2)=F æ
ç
ç
è
1
9
,-
1
3
;1,1,1,1;x2 ö
÷
÷
ø		 =
1
1-9x2
F æ
ç
ç
è
9
8
,-
3
4
;1,1,1,1;
x2
x2-1/9
ö
÷
÷
ø		 .
Joyce [5] (and Watson for P3(1)) has shown that this Heun function is related to the simple-cubic lattice Green function
P3(z)=
1
p 3
ó
õó
õó
õ
p
 
0
dx1dx2dx3
1-
z
3
(cos x1+cos x2+cos x3)
    (2)
through
F æ
ç
ç
è
9
8
,-
3
4
;1,1,1,1;x3 ö
÷
÷
ø		 = ( P3(t) )
1
2
 
 
æ
ç
ç
è		 1-
3
4
x1 ö
÷
÷
ø
-
1
4



 
( 1-x1 )
1
2
 
 
æ
ç
ç
è		 1-
8
9
x3 ö
÷
÷
ø
-
1
2
 
,
x3
=
1
2
+
x2
4
-
1
2
((1-x2)(1-x2/4))1/2=
9w 2
9w 2-1
,
     x2
=
x1
x1-1
,
x1
=
1
2
+
x
6
-
1
2
((1-x)(1-x/9))1/2,
     x =t2.
Further
P3(t)= æ
ç
ç
è		 1-
3
4
x1 ö
÷
÷
ø
1
2



 
(1-x1)-1 æ
ç
ç
è
2
p
ö
÷
÷
ø
2



 
K(k+)K(k-)
where
k
2
 
±
=
1
2
±
x2
4
( 4-x2 )
1
2
 
 
-
1
4
(2-x2)(1-x2)
1
2
 
,
and K(k) is the complete elliptic integral of the first kind. Hence we conclude that
Z32(w 2)= æ
ç
ç
è
2
p
ö
÷
÷
ø
2



 
(1-9w 2)-1 (1-w 2)-1K(k+)K(k-)     (3)
where the argument of the complete elliptic integral is given implicitly as a function of w through equations (2), (3) and (4), and so G3(x2) follows immediately from (5) and (1).

Similarly, for d=4, the Heun function can also be transformed [1, 7] to give
Z4(x2)
= æ
ç
ç
è		 F æ
ç
ç
è
1
4
,-
1
8
;
1
2
,
1
2
,1,
1
2
;4x2 ö
÷
÷
ø		 ö
÷
÷
ø
2



 
= æ
ç
ç
è		 F æ
ç
ç
è		 4,-
1
2
;
1
2
,
1
2
,1,
1
2
;16x2 ö
÷
÷
ø		 ö
÷
÷
ø
2



 
 
=
4
p 2
K(k+)K(k-).
    (4)
where
k
2
 
±
=
1
2
±8x2 ( 1-4x2 )
1
2
 
 
-
1
2
(1-8x2)(1-16x2)
1
2
 
.

Note that Z4(x2) is simply related to the lattice Green function  [5] for the face-centered-cubic lattice as
Pf.c.c.(z)=
3
3+z
æ
ç
ç
è		 F æ
ç
ç
è		 4,-
1
2
;
1
2
,
1
2
,1,
1
2
;
4z
3+z
ö
÷
÷
ø		 ö
÷
÷
ø
2



 
and for the diamond lattice as
Pdiam(z)= æ
ç
ç
è		 F æ
ç
ç
è		 4,-
1
2
;
1
2
,
1
2
,1,
1
2
;z2 ö
÷
÷
ø		 ö
÷
÷
ø
2



 
.
Finally, G4(x2) follows from (1) and (6).

For d>4 the theory of generalized hypergeometric functions with five or more regular singular point is not known to us, though the full singularity structure of the differential equations is given for d=5 and d=6, and is readily constructible for other values of d.

3   Bessel functions

Bessel functions [8] are the solutions of the differential equations
z2f''(z)+zf'(z)+(z2-n 2)f(z)=0.    (5)
Let Jn(z) be a solution of (7) which is analytic near the origin. Then we have
J
 
n
(z)=
¥
å
m=0
(-1)m æ
ç
ç
è
1
2
z ö
÷
÷
ø
n+2m



 
m!G (n +m+1)
when 2n is not an integer. J-n(z) is also such a solution. The first of the two series defines a function called a Bessel function of order n and argument z, of the first kind. When n is an integer, the function
Yn(z)=
 
lim
n ® n
J
 
n
(z)-(-1)nJ
 
-n
(z)
n -n
is called a Bessel function of the second kind of order n. Note that
Yn(z)= é
ê
ê
ë
J
 
n
(z)
n
-(-1)n
J
 
-n
(z)
n
ù
ú
ú
û
 



n =n
.
It has seemed desirable to Nielsen to regard the pair of the functions Jn(z)± iYn(z) as standard solutions of Bessel's equation (7). In honour of Hankel, Nielsen denotes them by the symbol H
H
(1)
 
n
=J
 
n
(z)+iY
 
n
(z),     H
(2)
 
n
=J
 
n
(z)-iY
 
n
(z).
Physicists consider the equation
z2f''(z)+zf'(z)-(z2+n 2)f(z)=0.    (6)
The solutions of this equation are called modified Bessel functions. It is usually desirable to present the solution of (8) in a real form, and the fundamental systems Jn(iz) and J-n(iz) or Jn(iz) and Yn(iz) are unsuited for this purpose. The function e-1/2n ip Jn(iz) is real in z and is a solution of (8). It is customary to denote the modified Bessel function of the first kind by In(z) so that
I
 
n
(z)=
¥
å
m=0
æ
ç
ç
è
1
2
z ö
÷
÷
ø
n+2m



 
m!G (n +m+1)
.
The modified Bessel function of the second kind is
Kn(z)=
 
lim
n ® n
(-1)n
2
æ
ç
ç
è
I
 
n
(z) -I
 
-n
(z)
n -n
ö
÷
÷
ø		 .
Note that
K
 
n
(z)=
p
2
æ
ç
ç
è
I
 
-n
(z)-I
 
n
(z)
sin (np)
ö
÷
÷
ø		 .
The following formulæ are valid:
(m!)2
= ó
õ
¥


0
t(t/2)2mK0(t) dt ,
     e-s
=
2s
p
ó
õ
1


0
K0(s/u)
u2(1-u2)1/2
 du,
I0(z)
=
¥
å
n=0
z/2)2n
(n!)2
=
1
p
ó
õ
¥


0
e
zcos q
 
 dq ,
    
1
z
= ó
õ
¥


0
e-sz ds.

Philippe Flajolet remarks that a natural tool to attack the calculation of Gd(z) are Bessel generating functions [2]. The Bessel generating function of a sequence sn of numbers is defined as the sum
¥
å
n=0
snzn
(n!)2
.
For instance, the Bessel generating function of the constant sequence sn=1 is given by the modified Bessel function
j(z):=I0 ( 2(z)1/2 ) =
¥
å
n=0
zn
(n!)2
.
The Bessel generating function of the number of pairs of paths with same origin and end and positive steps in a d-dimensional lattice is given by the product
d
Õ
i=1
j(xi) ,
where xi marks the steps in dimension i. It follows that the Bessel generating function of the numbers Sn(d) with respect to the length n of the paths is j(x)d. In dimension 2, the generating function Z2(x) is algebraic. In higher dimension, Zd(x) belongs to the larger class of holonomic functions. This class is closed under sum, product, Borel and inverse Borel transforms. The Borel transform is related to the inverse Laplace transform and is defined by
Borel æ
ç
ç
è
¥
å
n=0
snxn ö
÷
÷
ø		 =
¥
å
n=0
snxn
n!
.
We proceed to get Zd(x) by the formula
Zd(x)= ( Borel(-2) ) ( j(x)d ) .

4   The 4D simple-cubic lattice Green function

This section is due to the help of L. Glasser. The 4D simple-cubic lattice Green function is
P4(z)
=
1
p 4
ó
õó
õó
õó
õ
p
 
0
dx1dx2dx3dx4
1-
z
4
(cos x1+cos x2+cos x3+cos x4)
 
=
1
p 4
ó
õ
¥


0
e-s æ
ç
ç
ç
ç
è		 ó
õ
p


0
e
zscos k
 
 dk ö
÷
÷
÷
÷
ø
4





 
 ds = ó
õ
¥


0
e-sI04(sz) ds.
From (9)
P4(z)
=
¥
å
n1,n2,n3,n4=0
(z/2)
2(n1+n2+n3+n4)
 
(n1!n2!n3!n4)2
ó
õ
¥


0
e-ss
2(n1+n2+n3+n4)
 
 ds
 
= å{ni}
2 ( å ni ) !
(n1!n2!n3!n4)2
(z/2)
2å ni
 
=
¥
å
n=0
An(z/2)2n ,
where An=ån1+n2+n3+n4=n(2n)!/(n1!n2!n3!n4)2. But if we remark that
 
å
n1+n2+n3+n4=n
(n1!n2!n3!n4)-2=22n
 
å
n1+n2=n
(1/2)
 
n1
(1/2)
 
n2
(n1!n2!)3
=22nSn
where (1/2)n1=G(n1+1/2)/G(1/2), then we have
P4(z) = ó
õ
¥


0
e-sI04(sz) ds =
¥
å
n=0
z2n(2n)!
 
å
n1+n2=n
(1/2)
 
n1
(1/2)
 
n2
(n1!n2!)3
.
Using the following identities
(1/2)n-k=G(n-k+1/2)/G(1/2)=
(-1)n-kp
G(1/2)G(1/2-n)(1/2-n)k
and (n-k)!=
(-1)kn!
(-n)k
we obtain
Sn=
(-1)np 1/2
G(1/2-n)(n!)3
å
(1/2)k (-n)k(-n)k(-n)k
(1)k(1)k(1/2-n)kk!
=
(-1)np 1/2
G(1/2-n)(n!)3
 4F3 é
ë
1/2, -n, -n, -n;
1, 1, 1/2-n;
1 ù
û
and
An=
4n(2n)!(1/2)n
(n!)3
 4F3 é
ë
1/2, -n, -n, -n;
1, 1, 1/2-n;
1 ù
û		 .
We can also solve the fourth order differential equation with 4 regular singular points (0, 1/16, 1/4, ¥). An indirect method leads to an integral representation whereas a direct method leads to Kampé de Fériet functions.

For d>4, we have
Pd(z)=
1
p d
ó
õ		 ··· ó
õ
p


0
dx1··· dxd
1-
z
d
(cos x1+... +cos xd)
= ó
õ
¥


0
e-sI0(sz/d) ds=
2
p
ó
õ
1


0
Zd(u2z2/d2)
(1-u2)1/2
 du
with Zd(x)= ó
õ
¥


0
tK0(t)I0d(xt) dt.

References

[1]
Appell (M.). -- Comptes-Rendus de l'Académie des Sciences, vol. 91, 1880, pp. 211--214.

[2]
Chyzak (Frédéric). -- Staircase polygons, a simplified model for self-avoiding walks. -- 1997. Available at the URL
http://www-rocq.inria.fr/algo/libraries/autocomb/autocomb.html.

[3]
Flajolet (Philippe). -- Pólya Festoons. -- Research report, INRIA, July 1991. 7 pages.

[4]
Guttmann (A. J.) and Prellberg (T.). -- Staircase polygons, elliptic integrals, Heun functions, and lattice Green functions. Physical Review E, vol. 47, n°4, April 1993, pp. 2233--2236.

[5]
Joyce (G. S.). -- On the simple cubic lattice Green function. Philosophical Transactions of the Royal Society of London. Series A., vol. 273, n°1236, 1973, pp. 583--610.

[6]
Pólya (G.). -- On the number of certain lattice polygons. Journal of Combinatorial Theory, Series A, vol. 6, 1969, pp. 102--105.

[7]
Snow (Chester). -- Hypergeometric and Legendre functions with applications to integral equations of potential theory. -- U.S. Government Printing Office, Washington, D. C., 1952, National Bureau of Standards Applied Mathematics Series, vol. 19.

[8]
Watson (G. N.). -- A Treatise on the Theory of Bessel Functions, Chapter 2. -- Cambridge University Press, Cambridge, 1944, 2nd edition.
This document was translated from LATEX by HEVEA.