Staircase Polygons, Elliptic Integrals and Heun Functions (original) (raw)

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].

Any d_-dimensional staircase polygon [3, 6] of perimeter 2_n 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_k_ i steps in direction i (1� _i_� d) is () with _k_1+... +k _d_=n. Then the number of pairs of such paths is ()2. The generating function Z d(_x_1,... ,x d) for these pairs of paths, including a walk of zero length for later convenience, is

| Z d(_x_1,... ,x d)= | | 2 x | ��� x | . | | --------------------------- | | ----- | ------- | - |

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_=1_d x _i_2and we denote the generating function of staircase polygons in _d_dimensions by G d(_x_1,... ,x d). Let H(_x_1,... ,x d) be the generating function for a link

Due to the orientability of walks, each staircase polygon is produced twice in the definition of H(_x_1,... ,x d). We set_x_1=... =x _d_=x. The construction ``chain of'' corresponds to the functional relation Hence, by inspection

with For _d_=1 we get S n(1)=1 and _G_1(_x_2)=0. For d_=2 from the identity �_k_=0_n()2=() we find

For _d_>2 we observe the recursion By expansion and inspection (aided by computer algebra), we get

nS n(2)=2(2_n_-1)S n_-1(2), n_2_S n(3)=(10_n_2-10_n+3)S _n_-1(3)-9(n_-1)2_S _n_-2(3).

These recurrences can be reexpressed as differential equations

These differential equations are all Fuchsian, with regular singular points at the origin, at infinity, and at _x_=1/_d_2, 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

where B d 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 2_F_1 hypergeometric equation to the case of four, rather than three, regular points. We denote the solution as

Joyce [5] (and Watson for _P_3(1)) has shown that this Heun function is related to the simple-cubic lattice Green function

through

Further

where

and K(k) is the complete elliptic integral of the first kind. Hence we conclude that

where the argument of the complete elliptic integral is given implicitly as a function of w through equations (2), (3) and (4), and so _G_3(_x_2) follows immediately from (5) and (1).

Similarly, for _d_=4, the Heun function can also be transformed [1, 7] to give

where

Note that _Z_4(_x_2) is simply related to the lattice Green function [5] for the face-centered-cubic lattice as

and for the diamond lattice as

Finally, _G_4(_x_2) 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

z_2_f''(z)+zf'(z)+(_z_2-n 2)f(z)=0. (5)

Let _J_n(z) be a solution of (7) which is analytic near the origin. Then we have 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 is called a Bessel function of the second kind of order n. Note that

| Y n(z)= | ���� | | -(-1)n | ���� | . | | ------------- | ---- | | --------- | ---- | - |

It has seemed desirable to Nielsen to regard the pair of the functions _J_n(z)� _iY_n(z) as standard solutions of Bessel's equation (7). In honour of Hankel, Nielsen denotes them by the symbol H

Physicists consider the equation

z_2_f''(z)+zf'(z)-(_z_2+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 _J_n(iz) and _J_-n(iz) or _J_n(iz) and_Y_n(iz) are unsuited for this purpose. The function_e_-1/2n _i_p _J_n(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 _I_n(z) so that The modified Bessel function of the second kind is Note that The following formul� are valid:
Philippe Flajolet remarks that a natural tool to attack the calculation of G d(z) are Bessel generating functions [2]. The Bessel generating function of a sequence s n of numbers is defined as the sum For instance, the Bessel generating function of the constant sequence s _n_=1 is given by the modified Bessel function 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 where x i marks the steps in dimension i. It follows that the Bessel generating function of the numbers S n(d) with respect to the length n of the paths is j(x)d. In dimension 2, the generating function _Z_2(x) is algebraic. In higher dimension, Z d(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 We proceed to get Z d(x) by the formula

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

From (9)

where A _n_=�_n_1+_n_2+_n_3+n_4=n(2_n)!/(_n_1!_n_2!_n_3!_n_4)2. But if we remark that

| | (_n_1!_n_2!n_3!n_4)-2=22_n | | =22_n S n | | ---------------------------------- | | --------------- |

where (1/2)_n_1=G(_n_1+1/2)/G(1/2), then we have

Using the following identities

we obtain

| S _n_= | � | (1/2)k(-n)k(-n)k(-n)k (1)k(1)k(1/2-n)k k! | = | 4_F_3 | �� | | 1/2, -n, -n, -n; 1, 1, 1/2-n; | 1 | �� | | --------- | - | ----------------------------------------------------------------- | -- | ----- | -- | | ------------------------------------- | - | -- |

and

| A _n_= | 4_F_3 | �� | | 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

| P d(z)= | �� | ��� | �� | | = | �� | _e_-s _I_0(sz/d) _ds_= | �� | du | | ------------- | -- | --- | -- | | -- | -- | ------------------------------ | -- | ---- |

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, S eries A, vol. 6, 1969, pp. 102--105.

[7]

Snow (Chester). --Hypergeometric and L egendre 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 B essel Functions, Chapter 2. -- Cambridge University Press, Cambridge, 1944, 2nd edition.

This document was translated from LATEX byH E V E A.