Vicious walkers, friendly walkers and Young tableaux III: Between two walls

Christian Krattenthaler^{∗}

Institut für Mathematik, Universität Wien Strudlhofgasse 4, A-1090 Vienna, Austria,

Anthony J. Guttmann ^{†}^{‡}

Department of Mathematics and Statistics, The University of Melbourne Victoria 3010, Australia and Xavier G. Viennot^{∗}

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France.

Running Head: Vicious walkers between two walls.

November 18, 2002

∗Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272.

†Research supported by the Australian Research Council.

‡Author for communication. Phone (03)-8344-5550, fax (03)-8344-4599, tonyg@ms.unimelb.edu.au.

Abstract

We derive exact and asymptotic results for the number of star and watermelon configurations of vicious walkers confined to lie between two impenetrable walls, as well as corresponding results for the analogous problem of ∞-friendly walkers. Our proofs make use of results from symmetric function theory and the theory of basic hypergeometric series. Keywords; Vicious walkers, friendly walkers, symmetric functions, affine Weyl groups.

1 Introduction

This is the third paper in a series studying vicious and friendly walkers. In the first paper [10] it was shown how certain results from the theory of Young tableaux, and related results in algebraic combinatorics enabled one to readily prove closed form expressions for the number of star and watermelon configurations of vicious walkers on a d-dimensional lattice.

In the second paper [14], we showed how some results from the theory of symmetric functions could be used to prove analogous results for the more difficult problem of walkers in the presence of an impenetrable wall. We also gave rigorous asymptotic results.

In that paper we also developed the theory of n-friendly walkers, introduced in [11] and [13]. The two models differ slightly. In [11], the “vicious” constraint is systematically relaxed, so that any two walks (but not more than two) may stay together for up to n lattice sites in a row, but may never swap sides. We refer to this as the n-friendly walker model. In the limit as n → ∞ we obtain the ∞-friendly walker model in which two walkers may share an arbitrary number of steps. The Tsuchiya-Katori model [13], by contrast, corresponds to a variant of the ∞-friendly walker model which allows any number of walkers to share any number of lattice sites, whereas in the Guttmann-Vöge definition [11], only two walkers may share a lattice site. We subsequently refer to these two models as the TK and GV models respectively. Thus the number of TK friendly walk configurations gives an upper bound on the number of ∞-friendly walk configurations in the definition of GV. We make use of this observation in subsequent proofs.

In this, the final paper in the series, we address the problem of vicious and friendly walkers confined to a finite strip — or, equivalently, confined to lie between two parallel walls. A star configuration in a strip of width 11 is shown in Figure 1.

Vicious walkers describes the situation in which two or more walkers arriving at the same lattice site annihilate one another. Accordingly, the only configurations we consider in that case are those in which such contacts are forbidden. Alternatively expressed, we consider mutually self-avoiding networks of lattice walks which also model directed polymer networks. The connection of these vicious walker problems to the 5 and 6 vertex model of statistical mechanics was also discussed in [10].

The problem, together with a number of physical applications, was first introduced by Fisher [3]. Physical applications include models of wetting, and Fisher’s original

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{1}; A_{2}; A_{3}; A_{4}; E_{1}; E_{2}; E_{3}; E_{4}]

Figure 1: A star of p = 4 vicious walkers, of length m = 6, confined to a strip of width h = 11.

articles already raised the physical interesting consequences of the introduction of geometrical constraints in the form of walls. Very recently, it was shown in [2] that the problem of vicious walkers in a (periodic) strip involves precisely the same combinatorics as arises in three-dimensional Lorentzian quantum gravity. The general model is one of p random walkers on a d-dimensional lattice who at regular time intervals simultaneously take one step with equal probability in the direction of one of the allowed lattice vectors such that at no time do two walkers occupy the same lattice site.

Very recently, a number of authors [15, 22, 23, 1] have made fascinating connections between certain properties of two-dimensional vicious walkers and the eigenvalue distribution of certain random matrix ensembles. In [15] a model is introduced which can be considered as a randomly growing Young diagram, or a totally asymmetric one-dimensional exclusion process. (This could be interpreted in the vicious walker model where at each time unit exactly one of the walkers moves. This model occurs already in [3].) It is shown that the appropriately scaled shape fluctuations converge in distribution to the Tracy-Widom distribution [27] of the largest eigenvalue of the Gaussian Unitary Ensemble (GUE). Similarly, in [1] a vicious walker model is considered in which the end-point fluctuations of the top-most walker (in our notation) are considered. In that case the appropriately scaled limiting distribution is that of the largest eigenvalue of another distribution, the Gaussian Orthogonal Ensemble (GOE) [28]. Finally in [22, 23] the height distribution of a given point in the substrate of a one-dimensional growth process is considered, and this is generalised to models in the Kardar-Parisi-Zhang (KPZ) universality class [16]. The configurations considered again appear like vicious walkers. Again fluctuations and other properties of the models are found that follow GOE or GUE distributions.

The two standard topologies of interest are that of a star and a watermelon. Consider a directed square lattice, rotated 45^{∘} and augmented by a factor of \sqrt{2}, so that the “unit” vectors on the lattice are (1, 1) and (1, −1). Both configurations consist of p branches of length m (the lattice paths along which the walkers proceed) which start at (0, 0), (0, 2), (0, 4), …, (0, 2p − 2). The watermelon configurations end at (m, k), (m, 2 + k), (m, 4 + k), …, (m, k + 2p − 2), for some k. For stars, the end points of the branches all have x-coordinate equal to m, but the y coordinates are unconstrained, apart from the ordering imposed by the non-touching condition. Thus if the end points are (m, e_{1}), (m, e_{2}), (m, e_{3}), ⋯, (m, e_{p}), then e_{1} < e_{2} < e_{3} < ⋯ < e_{p} ≤ 2p − 2 + m. In the problem considered here, the additional constraint of impenetrable walls imposes the conditions that at no stage may any walker step to a point with negative y-coordinate, or to a point with y-cordinate greater than the strip width, h. We can also consider displaced configurations, in which the starting points are (0, a), (0, a + 2), (0, a + 4), …, (0, a + 2p − 2).

Vicious walkers confined to lie between two walls can be alternatively viewed as random walks in an alcove of an affine Weyl group of type C if the set of allowed steps is appropriately chosen. In this form they are considered by Grabiner in [9, Sec. 5]. The topic of the paper [9] is the exact enumeration of random walks in alcoves of affine Weyl groups of types A, C and D. One of the problems posed in [9] is to find asymptotic formulae for these random walks (when the length of the walks goes to infinity). We solve this problem for the random walks in an alcove of type C that correspond to our vicious walkers between two walls. Asymptotic results for the other enumeration problems considered in [9] will appear in the forthcoming paper [18]. An earlier, related paper [4] contains partial results for vicious walkers on a cylinder in the case of an odd number of walkers (which are equivalent to random walkers in an alcove of type A).

It is intuitively clear that the asymptotic growth of the number of vicious walkers within a strip must be exponential, with the base of the exponential depending on both the width of the strip and the number of walkers, but not on the starting and end points of the walkers. This is confirmed by our results. (The same must of course be true for n-friendly walkers, although we are only able to rigorously confirm this for ∞- friendly walkers in the TK model, by deriving explicit formulae.) Thus, for example, the asymptotics of stars and watermelons in the same strip will be exponential with the same base, and will only differ in the constant by which the exponential is multiplied. In the cases of walks with only one wall, or no walls [10, 14], the asymptotic growth factor is just 2^{p}, where p is the number of walkers.

Our results explicitly establish these intuitive results. Furthermore, in proving these results we present a variety of mathematical techniques and results which are likely to be of value in the study of related problems in the mathematical physics literature, a number of which are discussed above.

Our paper is organised as follows. In Section 2 we provide exact formulas for the number of vicious walkers between two walls with arbitrary starting and end points.

With the exception of one, these appear already in [9], in equivalent forms. These results follow from the Lindström–Gessel–Viennot theorem on nonintersecting lattice paths and known results for lattice paths between two parallel lines. They express the number of vicious walkers within a strip as determinants. In Section 3 we address the asymptotics of these formulas when the length of the branches of the vicious walkers goes to infinity. In Theorem 4 we give the asymptotics for vicious walkers within a strip for arbitrary (but fixed) starting and end points. By specializing the starting and end points, we obtain asymptotic results for watermelons within a strip, see Corollary 5. In order to obtain asymptotic results for stars within a strip, the formula in Theorem 4 has to be summed over all possible end points. To carry out this summation is a highly nontrivial task. It requires some symmetric function theory, in particular certain relations between Schur functions and symplectic and orthogonal characters, and a summation theorem for a basic hypergeometric series. The final result is given in Theorem 6. This theorem is then specialized to obtain the asymptotics for stars within a strip, see Corollaries 7 and 8.

2 The number of vicious walker configurations with arbitrary fixed starting and end points

The Lindström–Gessel–Viennot determinant [19, 8] in the case of the presence of two walls yields the following result. It appears already in [9, (13)], in an equivalent form.

Theorem 1. Let 0 ≤ a_{1} < a_{2} < ⋯ < a_{p} ≤ h, all a_{i}’s of the same parity, and 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h, all e_{i}’s of the same parity, such that a_{i} + e_{i} ≡ m (mod 2), i = 1, 2, …, p. The number of vicious walkers with p branches of length m, the i-th branch running from A_{i} = (0, a_{i}) to E_{i} = (m, e_{i}), i = 1, 2, …, p, which do not go below the x-axis nor above the line y = h, is given by

det_{1≤s,t≤p} ( ∑_{k=−∞}^{∞} (\binom{m}{\frac{m+e_{t}−a_{s}}{2} + k(h + 2)} − \binom{m}{\frac{m+e_{t}+a_{s}}{2} + k(h + 2) + 1})) .  (2.1)

Proof. According to the main theorem of non-intersecting lattice paths [8, Cor. 2] (see [25, Theorem 1.2]), the number of vicious walkers in question equals

det_{1≤s,t≤p} ( |P^{++}(A_{t} → E_{s})| ),  (2.2)

where P^{++}(A → E) denotes the set of all lattice paths from A to E which do not go below the x-axis nor above the line y = h. There is a well-known formula (see [21, (1.7)]) for the latter number, which is obtained by an iterated reflection principle. Substitution of this formula into (2.2) immediately gives (2.1).

By bringing the sums in (2.1) outside the determinant (using the multi-linearity of the determinant), the number of these vicious walkers can be described as a multiple sum of determinants. In some cases, such as for certain watermelons and stars, the determinants can be evaluated. In those cases, a multiple hypergeometric sum is obtained.

Theorem 2. Let 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h with e_{i} ≡ m (mod 2), i = 1, 2, …, p. The number of vicious walkers with p branches of length m, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), which do not go below the x-axis nor above the line y = h, i = 1, 2, …, p, is given by

∑_{k_{1},...,k_{p}=−∞}^{∞} 2^{p−p^{2}} ∏_{s=1}^{p} \frac{(e_{s} + 2k_{s}(h + 2) + 1) (m + 2s − 2)!}{(\frac{m+e_{s}}{2} + k_{s}(h + 2) + p)! (\frac{m−e_{s}}{2} − k_{s}(h + 2) + p − 1)!}

× ∏_{1≤s<t≤p}(e_{t} − e_{s} + 2(h + 2)(k_{t} − k_{s}))(e_{t} + e_{s} + 2(h + 2)(k_{t} + k_{s}) + 2). (2.3)

Proof. As described above the statement of the theorem, we first write the expression (2.1), with a_{i} = 2i − 2, as a sum of determinants,

∑_{k_{1},...,k_{p}=−∞}^{∞} det_{1≤s,t≤p} (\binom{m}{\frac{m+e_{t}}{2} + k_{t}(h + 2) − s + 1} − \binom{m}{\frac{m+e_{t}}{2} + k_{t}(h + 2) + s}) . (2.4)

Suppose that, initially, we disregard the terms k_{t}(h + 2) in the determinant, then it simplifies to

det_{1≤s,t≤p} (\binom{m}{\frac{m+e_{t}}{2} − s + 1} − \binom{m}{\frac{m+e_{t}}{2} + s}) .  (2.5)

Gessel–Viennot theory (again) says that this determinant counts vicious walkers with p branches of length m, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), which do not go below the x-axis. By Theorem 6 of [14], the number of these vicious walkers is given by

2^{−p^{2}+p} ∏_{s=1}^{p} \frac{(e_{s} + 1) (m + 2s − 2)!}{(\frac{m+e_{s}}{2} + p)! (\frac{m−e_{s}}{2} + p − 1)!} ∏_{1≤s<t≤p}(e_{t} − e_{s})(e_{s} + e_{t} + 2).  (2.6)

Hence, the determinant in (2.5) must equal the expression (2.6). In fact, as the equality between (2.5) and (2.6) can be reduced to an equation which is polynomial in e_{1}, e_{2} …, e_{p}, the equality is true for any choice of e_{1}, e_{2}, …, e_{p}. In particular, it remains true if we replace e_{i} by e_{i} + 2k_{i}(h + 2), i = 1, 2, …, p. However, the determinant in (2.5) under these replacements becomes the determinant in (2.4). Thus, if we substitute the expression (2.6), with these replacements, into (2.4), we immediately obtain (2.3).

For the subsequent asymptotic calculations, however, we need a different type of expression for the number of vicious walkers under consideration. This expression can be easily derived by a combination of the Lindström–Gessel–Viennot theorem and an alternative expression for the number of lattice paths between two parallel boundaries in terms of sines and cosines. It appears already in [9, (18)], in an equivalent form.

Theorem 3. Let 0 ≤ a_{1} < a_{2} < ⋯ < a_{p} ≤ h, all a_{i}’s of the same parity, and 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h, all e_{i}’s of the same parity, such that a_{i} + e_{i} ≡ m (mod 2), i = 1, 2, …, p. The number of vicious walkers with p branches of length m, the i-th branch running from A_{i} = (0, a_{i}) to E_{i} = (m, e_{i}), i = 1, 2, …, p, which do not go below the x-axis and not above the line y = h, is given by

\frac{2^{p}}{(h + 2)^{p}} ∑_{k_{1},...,k_{p}=1}^{h+1} (2^{p} ∏_{s=1}^{p} cos \frac{k_{s}π}{h + 2})^{m} ∏_{t=1}^{p} sin \frac{πk_{t}(e_{t} + 1)}{h + 2} det_{1≤s,t≤p} (sin \frac{πk_{t}(a_{s} + 1)}{h + 2}) .

(2.7)

Proof. We already know that, by the Lindström–Gessel–Viennot theorem, the number in question is given by (2.2). Instead of using the iterated reflection formula for |P^{++}(A → E)|, we now apply the (equally well-known) alternative formula (see [12, §184, Ex. 1, Eq. (9)])

|P^{++}(A → E)| = \frac{2}{h + 2} ∑_{k=1}^{h+1} (2 cos \frac{πk}{h + 2})^{m} sin \frac{πk(a + 1)}{h + 2} · sin \frac{πk(e + 1)}{h + 2},

given that A = (0, a) and E = (m, e). Substituting this into (2.2), and bringing the summations and a few factors outside of the determinant utilising the multi-linearity of the determinant, we get (2.7).

3 The asymptotics of vicious walkers between two walls

We shall now use the exact formulae from the previous section to derive asymptotic formulae for vicious walkers between two walls. In the first subsection, we address the case where the end points of the vicious walkers are kept fixed. By summing over all possible end points, we shall then obtain asymptotic formulae for stars in the second subsection.

3.1 Vicious walkers with fixed end points

Theorem 3 enables us to derive asymptotic formulae for the number of vicious walkers between two walls, for arbitrary starting and end points.

Theorem 4. Let 0 ≤ a_{1} < a_{2} < ⋯ < a_{p} ≤ h, all a_{i}’s of the same parity, and 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h, all e_{i}’s of the same parity, such that a_{i} + e_{i} ≡ m (mod 2), i = 1, 2, …, p. The number of vicious walkers with p branches of length m, the i-th branch running from A_{i} = (0, a_{i}) to E_{i} = (m, e_{i}), i = 1, 2, …, p, which do not go below the x-axis nor above the line y = h, is asymptotically

\frac{4^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin \frac{π(a_{t} − a_{s})}{2(h + 2)} · sin \frac{π(e_{t} − e_{s})}{2(h + 2)}

× ∏_{1≤s≤t≤p} sin \frac{π(a_{t} + a_{s} + 2)}{2(h + 2)} · sin \frac{π(e_{t} + e_{s} + 2)}{2(h + 2)}. (3.1)

Remark. What this theorem says is that vicious walkers in a strip of width h grow exponentially like (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h+2})^{m}, everything else is just the multiplicative constant. In particular, specialising either to watermelons or stars leads to the same dominant asymptotic behaviour, with only a multiplicative constant changing as the configurations change.

Proof. Theorem 3 tells us that the number of vicious walkers that we wish to estimate can be written in the form of a finite sum ∑_{ℓ} c_{ℓ}b_{ℓ}^{m}, where the c_{ℓ}’s and b_{ℓ}’s are independent of m. Hence, what we have to find is b = max_{ℓ} |b_{ℓ}|. Then, asymptotically, the number of vicious walkers is b^{m} ∑_{ℓ: |b_{ℓ}|=b} c_{ℓ} if m is even, with a similar statement in the case that m is odd.

The b_{ℓ}’s have the form

2^{p} ∏_{s=1}^{p} cos (k_{s}π/(h + 2)).  (3.2)

To find the largest among these, we have to choose k_{s} close to the lower limit of the summation in (2.7), which is 1, or close to the upper limit, h + 1. However, we are not allowed to make a choice such that k_{s} = k_{t} for some s ≠ t, because in that case the determinant in (2.7) vanishes. For the same reason a choice such that k_{s} = h + 2 − k_{t} for some s and t is forbidden. Therefore the expression (3.2) will be maximal if the set {k_{1}, k_{2} …, k_{p}} is chosen from {1, 2, …, p, h + 2 − p, …, h, h + 1}, subject to the two restrictions mentioned above. These conditions give exactly 2^{p} different choices. As a short calculation shows, the sum of the corresponding summands in (2.7) equals

\frac{4^{p}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} det_{1≤s,t≤p} (sin \frac{πt(a_{s} + 1)}{h + 2}) det_{1≤s,t≤p} (sin \frac{πt(e_{s} + 1)}{h + 2}) ,

or, equivalently,

\frac{(−1)^{p}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} det_{1≤s,t≤p} (e^{\frac{πit}{h+2} (a_{s}+1)} − e^{− \frac{πit}{h+2} (a_{s}+1)})

× det_{1≤s,t≤p} (e^{\frac{πit}{h+2} (e_{s}+1)} − e^{− \frac{πit}{h+2} (e_{s}+1)}) . (3.3)

Both determinants are easily evaluated by means of the determinant identity

det_{1≤i,j≤N} (x_{i}^{j} − x_{i}^{−j}) = (x_{1}x_{2} ⋯ x_{N})^{−N} ∏_{1≤i<j≤N}(x_{i} − x_{j})(1 − x_{i}x_{j}) ∏_{i=1}^{N}(x_{i}^{2} − 1), (3.4)

which may be readily proved by the standard argument that proves Vandermonde-type determinant identities.

A little manipulation then leads to (3.1).

If we now specialize a_{i} to a + 2i − 2 and e_{i} to e + 2i − 2 in Theorem 4, we then obtain the asymptotics for watermelons between two walls.

Corollary 5. Let a and e be integers with 0 ≤ a, e ≤ h − 2p + 2 and a + e ≡ m (mod 2). The number of watermelons with p branches of length m, in which the lowest branch starts at height a and terminates at height e, which do not go below the x-axis nor above the line y = h, is asymptotically

\frac{4^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin^{2} \frac{π(t − s)}{(h + 2)}

× ∏_{1≤s≤t≤p} sin \frac{π(a + t + s − 1)}{(h + 2)} · sin \frac{π(e + t + s − 1)}{(h + 2)}. (3.5)

Let a and e be integers with 0 ≤ a, e ≤ h − 2p + 2 and a + e ≡ m (mod 2). The number of ∞-friendly watermelons in the TK model with p branches of length m, in which the lowest branch starts at height a and terminates at height e, which do not go below the x-axis nor above the line y = h, is asymptotically

\frac{4^{p^{2}}}{(h + 2p)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2p})^{m} ∏_{1≤s<t≤p} sin^{2} \frac{2π(t − s)}{(h + 2p)}

× ∏_{1≤s≤t≤p} sin \frac{π(a + 2t + 2s − 3)}{(h + 2p)} · sin \frac{π(e + 2t + 2s − 3)}{(h + 2p)}. (3.6)

Proof. There is nothing to say about the first claim, which follows immediately from the theorem. To establish the second claim, we shift the i-th branch of the ∞-friendly watermelon by 2(i − 1) units up, as in the proof of Theorem 4 of [14]. We transform ∞-friendly watermelons into families of lattice paths which do not touch one another by shifting the i-th path up by 2(i − 1) units. Thus we obtain a set of vicious walkers with p branches of length m, the i-th branch starting from A_{i} = (0, a + 4i − 4) and terminating at E_{i} = (m, e + 4i − 4), i = 1, 2, …, p, which do not go below the x-axis and not above the line y = h + 2p − 2 (!). Hence, Theorem 4 with a_{i} = a + 4i − 4, e_{i} = e + 4i − 4, i = 1, 2, …, p, and h replaced by h + 2p − 2 immediately gives the desired asymptotics.

Clearly, by performing the obvious summations of (3.5) over e, respectively a, we could also obtain the asymptotics for watermelons of arbitrary deviation. The resulting sums do not appear to simplify however. Nevertheless, since the summations are over finite sets (depending only on the width h of the strip and the number p of walkers), it is obvious that the order of the asymptotic growth is again (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h+2})^{m} for vicious walkers and (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h+2p})^{m} for ∞-friendly walkers in the TK model.

It should be noted, however, that in contrast to watermelons without restriction and with the restriction of one wall, as considered in our previous papers, the situation considered here, that is in the presence of the restriction of two walls, the asymptotics of (ordinary) watermelons and ∞-friendly watermelons (compare the bases of the exponentials in the two statements in Corollary 5) is of a different order of magnitude (except in the case of single branch watermelons, of course). Hence, from these considerations, it is impossible to conclude whether n-friendly watermelons restricted by two walls will have the same order of magnitude as (ordinary) watermelons, or not.

3.2 Asymptotics for stars

Let us turn now to the asymptotics for stars. We begin with a general theorem, which solves the problem, posed in [9], of computing the asymptotics for the number of random walks in an alcove of an affine Weyl group of type C if the allowed steps are of the form \frac{1}{2}(±1, ±1, …, ±1).

Theorem 6. Let 0 ≤ a_{1} < a_{2} < ⋯ < a_{p} ≤ h be integers, all of the same parity. The number of vicious walkers with p branches of length m, the i-th branch starting from A_{i} = (0, a_{i}), i = 1, 2, …, p, which do not go below the x-axis nor above the line y = h, is asymptotically

\frac{4^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin \frac{π(a_{t} − a_{s})}{2(h + 2)} · sin \frac{π(t − s)}{h + 2}

× ∏_{1≤s≤t≤p} sin \frac{π(a_{t} + a_{s} + 2)}{2(h + 2)} · sin \frac{π(t + s)}{h + 2} ∏_{s=0}^{p} ∏_{t=1}^{p} \begin{matrix}sin & \frac{π(t−s+⌊(h+2)/2⌋)}{h+2} \\ sin & \frac{π(t−s+p)}{h+2} \end{matrix}

× ∏_{s=1}^{p} \begin{matrix}sin & \frac{(s+⌊(h+2)/2⌋−p)π}{h+2} \\ sin & \frac{(2s+⌊(h+2)/2⌋−p)π}{h+2} \end{matrix} , (3.7)

if m + a_{i} is even, and

\frac{4^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin \frac{π(a_{t} − a_{s})}{2(h + 2)} · sin \frac{π(t − s)}{h + 2}

× ∏_{1≤s≤t≤p} sin \frac{π(a_{t} + a_{s} + 2)}{2(h + 2)} · sin \frac{π(t + s)}{h + 2} ∏_{s=0}^{p} ∏_{t=1}^{p} \begin{matrix}sin & \frac{π(t−s+⌊(h+1)/2⌋)}{h+2} \\ sin & \frac{π(t−s+p)}{h+2} \end{matrix} , (3.8)

if m + a_{i} is odd.

Proof. It is obvious that, in view of Theorem 4, we have to compute the sum of (3.1) over all possible choices of e_{1} < e_{2} < ⋯ < e_{p}. Here we have to distinguish between two cases, depending on whether m + a_{i} is even or odd.

First let m+a_{i} be odd. This implies that all the e_{i}’s are odd as well, so that we have to compute the sum of (3.1) over all possible choices of 1 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h, with e_{i} = 2e′_{i} − 1 for some integer e′_{i}, i = 1, 2, …, p. If we remember that expression (3.1) came from (3.3), we see that this is

\frac{2^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin \frac{π(a_{t} − a_{s})}{2(h + 2)} ∏_{1≤s≤t≤p} sin \frac{π(a_{t} + a_{s} + 2)}{2(h + 2)}

× (−i)^{p} ∑_{1≤e′_{1}<···<e′_{p}≤⌊(h+1)/2⌋} det_{1≤s,t≤p} (e^{\frac{2πit}{h+2} e′_{s}} − e^{− \frac{2πit}{h+2} e′_{s}}) . (3.9)

In order to evaluate the sum in the last line, we rewrite it in terms of symplectic characters sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{p}^{±1}), which are defined by (see [5, (24.18)])

sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{p}^{±1}) = \frac{det_{1≤s,t≤p}(x_{t}^{λ_{s}+p−s+1} − x_{t}^{−(λ_{s}+p−s+1)})}{det_{1≤s,t≤p}(x_{t}^{p−s+1} − x_{t}^{−(p−s+1)})}.  (3.10)

Therefore, writing q for e^{2πi/(h+2)} and H for ⌊(h + 1)/2⌋, the sum in the last line of (3.9) equals

det_{1≤s,t≤p} (q^{st} − q^{−st}) ∑_{1≤e′_{1}<···<e′_{p}≤H} sp_{(e′_{p}−p,...,e′_{1}−1)}(q^{±1}, q^{±2}, …, q^{±p})

= det_{1≤s,t≤p} (q^{st} − q^{−st}) ∑_{ν⊆((H−p)^{p})} sp_{ν}(q^{±1}, q^{±2}, …, q^{±p}). (3.11)

Now we appeal to the formula (see [17, (3.4)]),

s_{(c^{r})}(x_{1}, x_{1}^{−1}, …, x_{p}, x_{p}^{−1}, 1) = ∑_{ν⊆(c^{r})} sp_{ν}(x_{1}^{±1}, …, x_{p}^{±1}).  (3.12)

Use of this formula in (3.11) gives

det_{1≤s,t≤p} (q^{st} − q^{−st}) s_{((H−p)^{p})}(q^{−p}, …, q^{−1}, 1, q, …, q^{p}).  (3.13)

Clearly, the determinant is easily evaluated by means of (3.4), whereas the specialized Schur function can be evaluated by means of the hook-content formula (see [20, I, Sec. 3, Ex. 1], [5, Ex. A.30, (ii)])

s_{λ}(q^{−L}, q^{−L+1}, …, q^{−L+P}) = q^{∑_{l≥1}(l−L−1)λ_{l}} ∏_{ρ∈λ} \frac{1 − q^{P +c_{ρ}}}{1 − q^{h_{ρ}}} ,  (3.14)

where c_{ρ} and h_{ρ} are the content and the hook length of the cell ρ. Substitution of all this in (3.9) and some manipulation then leads to (3.8).

Now let m+a_{i} be even. This implies that all the e_{i}’s are even as well, so that we have to compute the sum of (3.1) over all possible choices of 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h, with e_{i} = 2e′_{i} − 2 for some integer e′_{i}, i = 1, 2, …, p. Again, if we remember that expression (3.1) came from (3.3), we see that this is

\frac{2^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin \frac{π(a_{t} − a_{s})}{2(h + 2)} ∏_{1≤s≤t≤p} sin \frac{π(a_{t} + a_{s} + 2)}{2(h + 2)}

× (−i)^{p} ∑_{1≤e′_{1}<···<e′_{p}≤⌊(h+2)/2⌋} det_{1≤s,t≤p} (e^{\frac{2πit}{h+2} (e′_{s}− \frac{1}{2} )} − e^{− \frac{2πit}{h+2} (e′_{s}− \frac{1}{2} )}) . (3.15)

This time, it is possible to rewrite the sum in the last line in terms of odd orthogonal characters. The odd orthogonal characters so_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1) where x_{1}^{±1} is a shorthand notation for x_{1}, x_{1}^{−1}, etc., and λ is an m-tuple (λ_{1}, λ_{2}, …, λ_{m}) of integers, or of half-integers, are defined by

so_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1) = \frac{det_{1≤i,j≤m}(x_{j}^{λ_{i}+m−i+1/2} − x_{j}^{−(λ_{i}+m−i+1/2)})}{det_{1≤i,j≤m}(x_{j}^{m−i+1/2} − x_{j}^{−(m−i+1/2)})}.  (3.16)

While Schur functions are polynomials in x_{1}, x_{2}, …, x_{m}, odd orthogonal characters so_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1) are polynomials in x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{m}, x_{m}^{−1}, 1. They have combinatorial descriptions in terms of certain tableaux as well, see [6, Sec. 2], [24, Sec. 6–8], [26, Theorem 2.3].

Now, writing q for e^{2πi/(h+2)} and H for ⌊(h + 2)/2⌋, the sum in the last line of (3.15) equals

det_{1≤s,t≤p} (q^{(s− \frac{1}{2} )t} − q^{−(s− \frac{1}{2} )t}) ∑_{1≤e′_{1}<···<e′_{p}≤H} so_{(e′_{p}−p,...,e′_{1}−1)}(q^{±1}, q^{±2}, …, q^{±p}, 1)

= det_{1≤s,t≤p} (q^{(s− \frac{1}{2} )t} − q^{−(s− \frac{1}{2} )t}) ∑_{ν⊆((H−p)^{p})} so_{ν}(q^{±1}, q^{±2}, …, q^{±p}, 1). (3.17)

Again there is a formula which allows us to evaluate the sum in the last line (see [17, (3.2)]),

s_{((c^{r−ℓ},(c−1)^{ℓ})}(x_{1}, x_{1}^{−1}, …, x_{p}, x_{p}^{−1}, 1) = _{∑_{ν⊆(c^{r})} ; oddrows((c^{r})/ν)=ℓ} so_{ν}(x_{1}^{±1}, …, x_{p}^{±1}, 1), (3.18)

where oddrows((c^{r})/ν) = ℓ means that the number of rows of odd length in the skew shape (c^{r})/ν equals exactly ℓ. Use of this formula in (3.17) gives

det_{1≤s,t≤p} (q^{(s− \frac{1}{2} )t} − q^{−(s− \frac{1}{2} )t}) ∑_{ℓ=0}^{p} s_{((H−p)^{p−ℓ},(H−p−1)^{ℓ})}(q^{−p}, …, q^{−1}, 1, q, …, q^{p}). (3.19)

Again, the hook-content formula (3.14) applies and yields

det_{1≤s,t≤p} (q^{(s− \frac{1}{2} )t} − q^{−(s− \frac{1}{2} )t}) ∑_{ℓ=0}^{p} q^{−(H−p)\binom{p+1}{2}+\binom{ℓ+1}{2}} \frac{∏_{s=1}^{H−p−1}(q^{p+s+1}; q)_{p}}{∏_{s=1}^{H−p}(q^{s}; q)_{p}}

× \frac{(q^{H+ℓ+1}; q)_{p−ℓ} (q^{ℓ+1}; q)_{p−ℓ} (q^{H−p}; q)_{ℓ}}{(q; q)_{p−ℓ}}

for the expression (3.19). Here we used the standard notation for shifted q-factorials, (a; q)_{k} := (1 − a)(1 − aq) ⋯ (1 − aq^{k−1}), k ≥ 1, (a; q)_{0} := 1. In terms of the standard basic hypergeometric notation

rϕ_{s}[\begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix}; q, z] = ∑_{ℓ=0}^{∞} \frac{(a_{1}; q)_{ℓ} ⋯ (a_{r}; q)_{ℓ}}{(q; q)_{ℓ}(b_{1}; q)_{ℓ} ⋯ (b_{s}; q)_{ℓ}} ((−1)^{ℓ}q^{\binom{ℓ}{2}})^{s−r+1} z^{ℓ} ,

this can be written in the form

det_{1≤s,t≤p} (q^{(s− \frac{1}{2} )t} − q^{−(s− \frac{1}{2} )t}) q^{−(H−p)\binom{p+1}{2}}( ∏_{s=1}^{H−p} \frac{(q^{p+s+1}; q)_{p}}{(q^{s}; q)_{p}} )_{2}ϕ_{1}[\begin{matrix}q^{H−p}, q^{−p} \\ q^{H+1} \end{matrix}; q, −q^{p+1}] .

The determinant is again easily evaluated by means of (3.4). On the other hand, the 2ϕ_{1}-series in the above expression can be summed with the help of the q-analogue of Kummer’s summation (see [7, Appendix (II.9)]),

2ϕ_{1}[\begin{matrix}a, b \\ aq/b \end{matrix}; q, −q/b] = \frac{(−q; q)_{∞} (aq; q^{2})_{∞} (aq^{2}/b^{2}; q^{2})_{∞}}{(−q/b; q)_{∞} (aq/b; q)_{∞}} .

Thus we have finally evaluated the sum in (3.15). From there, it is then routine to arrive at the expression (3.7).

Clearly, if we specialize Theorem 6 to a_{i} = a + 2i − 2, i = 1, 2, …, p, we obtain the asymptotics for stars between two walls.

Corollary 7. Let a be an integer with 0 ≤ a ≤ h − 2p + 2. The number of stars with p branches of length m, the i-th branch starting from A_{i} = (0, a + 2i − 2), i = 1, 2, …, p, which do not go below the x-axis nor above the line y = h, is asymptotically

\frac{4^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin^{2} \frac{π(t − s)}{h + 2}

× ∏_{1≤s≤t≤p} sin \frac{π(a + t + s − 1)}{h + 2} · sin \frac{π(t + s)}{h + 2} ∏_{s=0}^{p} ∏_{t=1}^{p} \begin{matrix}sin & \frac{π(t−s+⌊(h+2)/2⌋)}{h+2} \\ sin & \frac{π(t−s+p)}{h+2} \end{matrix}

× ∏_{s=1}^{p} \begin{matrix}sin & \frac{π(s+⌊(h+2)/2⌋−p)}{h+2} \\ sin & \frac{π(2s+⌊(h+2)/2⌋−p)}{h+2} \end{matrix} , (3.20)

if m + a is even, and

\frac{4^{p^{2}}}{(h + 2)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2})^{m} ∏_{1≤s<t≤p} sin^{2} \frac{π(t − s)}{h + 2}

× ∏_{1≤s≤t≤p} sin \frac{π(a + t + s − 1)}{h + 2} · sin \frac{π(t + s)}{h + 2} ∏_{s=0}^{p} ∏_{t=1}^{p} \begin{matrix}sin & \frac{π(t−s+⌊(h+1)/2⌋)}{h+2} \\ sin & \frac{π(t−s+p)}{h+2} \end{matrix} , (3.21)

if m + a is odd.

A different specialization yields the asymptotics for ∞-friendly stars between two walls.

Corollary 8. Let a be an integer with 0 ≤ a ≤ h − 2p + 2. The number of ∞- friendly stars in the TK model with p branches of length m, the i-th branch starting from A_{i} = (0, a + 2i − 2), i = 1, 2, …, p, which do not go below the x-axis nor above the line y = h, is asymptotically

\frac{4^{p^{2}}}{(h + 2p)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2p})^{m} ∏_{1≤s<t≤p} sin \frac{2π(t − s)}{h + 2p} · sin \frac{π(t − s)}{h + 2p}

× ∏_{1≤s≤t≤p} sin \frac{π(a + 2t + 2s − 3)}{h + 2p} · sin \frac{π(t + s)}{h + 2p} ∏_{s=0}^{p} ∏_{t=1}^{p} \begin{matrix}sin & \frac{π(t−s+⌊(h+2p)/2⌋)}{h+2p} \\ sin & \frac{π(t−s+p)}{h+2p} \end{matrix}

× ∏_{s=1}^{p} \begin{matrix}sin & \frac{π(s+⌊(h+2p)/2⌋−p)}{h+2p} \\ sin & \frac{π(2s+⌊(h+2p)/2⌋−p)}{h+2p} \end{matrix} , (3.22)

if m + a is even, and

\frac{4^{p^{2}}}{(h + 2p)^{p}} (2^{p} ∏_{s=1}^{p} cos \frac{sπ}{h + 2p})^{m} ∏_{1≤s<t≤p} sin \frac{2π(t − s)}{h + 2p} · sin \frac{π(t − s)}{h + 2p}

× ∏_{1≤s≤t≤p} sin \frac{π(a + 2t + 2s − 3)}{h + 2p} · sin \frac{π(t + s)}{h + 2p} ∏_{s=0}^{p} ∏_{t=1}^{p} \begin{matrix}sin & \frac{π(t−s+⌊(h+1)/2⌋)}{h+2p} \\ sin & \frac{π(t−s+p)}{h+2p} \end{matrix} , (3.23)

if m + a is odd.

Proof. As in the proof of equation (3.6), we shift the i-th branch up by 2(i − 1) units. Thus we obtain a set of vicious walkers with p branches of length m, the i-th branch starting from A_{i} = (0, a + 4i − 4), i = 1, 2, …, p, which do not go below the x-axis nor above the line y = h + 2p − 2. Hence, Theorem 6 with a_{i} = a + 4i − 4, i = 1, 2, …, p, and h replaced by h + 2p − 2 immediately gives the desired asymptotics.

As we noted in the case of watermelons, the restriction to stars confined between two walls, in contrast to stars without restriction and with the restriction of one wall, the asymptotics of (ordinary) stars and ∞-friendly stars (compare the bases of the exponentials in Corollaries 7 and 8) is of a different order of magnitude (except in the case of single branch stars, of course). Hence, again, from these considerations, it is impossible to conclude whether n-friendly stars restricted by two walls will have the same order of magnitude as (ordinary) stars, or not.

As a final remark we mention that we could also have stated an asymptotic formula the number of all possible vicious walkers between two walls (i.e., with arbitrary starting and end points). One would have to sum up the expression in Theorem 6 over all 0 ≤ a_{1} < a_{2} < ⋯ < a_{p} ≤ h, which can be accomplished in the same way as the summation over 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ h of the expression (3.1) in the proof of Theorem 6. We omit an explicit statement for the sake of brevity.

References

[1] J. Baik, Random vicious walks and random matrices, Commun. Pure Appl. Math. 53 (2000), 1385-1410.

[2] B. Dittrich and R. Loll, A Hexagon model for 3D Lorentzian Quantum Cosmology, Phys. Rev. D66 (2002), 084016.

[3] M. E. Fisher, Walks, walls, wetting and melting, J. Stat. Phys. 34 (1984), 667-729.

[4] P. J. Forrester, Exact solution of the lock step model of vicious walkers J. Phys. A.: Math. Gen., 23 (1990) 1259–73.

[5] W. Fulton and J. Harris, Representation Theory, Springer–Verlag, New York, 1991.

[6] M. Fulmek and C. Krattenthaler, Lattice path proofs for determinant formulas for symplectic and orthogonal characters, J. Combin. Theory Ser. A 77 (1998), 3–50.

[7] G. Gasper and M. Rahman, Basic Hypergeometric Series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, Cambridge, 1990.

[8] I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint,

1989; available at http://www.cs.brandeis.edu/~ira.

[9] D. J. Grabiner, Random walk in an alcove of an affine Weyl group, and noncolliding random walks on an interval, J. Combin. Theory Ser. A 97 (2002), 285– 306.

[10] A. J. Guttmann, A. L. Owczarek and X. G. Viennot, Vicious walkers and Young tableaux I: without walls. J. Phys. A: Math. Gen. 31 (1998), 8123–8135.

[11] A. J. Guttmann and M. Vöge, Lattice paths: vicious walkers and friendly walkers, J. Statistical Plann. Inf. 101 (2002), 107–131.

[12] C. Jordan, Calculus of finite differences, 3rd edition, Chelsea Publ. Comp., New York, 1965.

[13] T. Tsuchiya and M. Katori, Chiral Potts models, Friendly Walkers and Directed Percolation Problem, J. Phys. Soc. Japan 67 (1988), 1655–1666.

[14] C. Krattenthaler, A. J. Guttmann and X. G. Viennot, Vicious walkers, friendly walkers and Young tableaux: II With a wall, J. Phys. A: Math. Gen. 33 (2000), 8835–8866.

[15] K. Johansson, Shape fluctuations and random matrices, Commun. Math. Phys. 209 (2) (2000), 437–476.

[16] M. Kardar, G. Parisi and Y.-Z. Zhang, Dynamic scaling of growing interfaces, Phys Rev. Letts. 56 (1986), 889–892.

[17] C. Krattenthaler, Identities for classical group characters of nearly rectangular shape, J. Algebra 209 (1998), 1–64.

[18] C. Krattenthaler, Asymptotics for random walks in Weyl chambers, in preparation.

[19] B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

[20] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, New York/London, 1995.

[21] S. G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

[22] M. Prähofer and H. Spohn, Statistical Self-similarity of One-dimensional Growth Processes, Physica A 279 (2000), 342–360.

[23] M. Prähofer and H. Spohn, Universal distributions for Growth Processes in 1+1 dimensions and random matrices, Phys. Rev. Letts., 84, (2000), 4882-5.

[24] R. A. Proctor, Young tableaux, Gelfand patterns, and branching rules for classical groups, J. Algebra 164 (1994), 299–360.

[25] J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96–131.

[26] S. Sundaram, Tableaux in the representation theory of the classical Lie groups, in: “Invariant theory and tableaux”, D. Stanton, ed., The IMA Volumes in Math. And Its Appl., Vol. 19, Springer–Verlag, New York, Berlin, Heidelberg, 1989, 191–225.

[27] C. A. Tracy and H. Widom, Level-spacing distributions and the Airy kernel, Commun. Math. Phys. 159 (1994), 151–174.

[28] C. A. Tracy and H. Widom, On orthogonal and symplectic matrix ensembles, Commun. Math. Phys. 177 (1996), 727–754.