RANDOM WALK IN A WEYL CHAMBER ^{1}

Ira M. Gessel ^{2} and Doron Zeilberger^{3}

Appeared in: Proc. Amer. Math. Soc. 115 (1992), 27-31.

Abstract: The classical Ballot problem that counts the number of ways of walking from the origin and staying within the wedge x_{1} ≥ x_{2} ≥ ... ≥ x_{n} (which is a Weyl chamber for the symmetric group), using positive unit steps, is generalized to general Weyl groups and general sets of steps.

0. Introduction

To any simple and natural proof, one can ask the question: How far can it be generalized? We will attempt to give one possible answer to this question for Andre”s[A] celebrated solution of the two-candidate ballot problem. Andre’s proof uses a reflection argument, and we will show that it can be naturally generalized to the context of Coxeter-Weyl ([Co], [H], [H1], [BG]) general finite reflection groups.

Random and lattice walks form a venerable part of probability theory and combinatorics. In a typical problem, a walker is allowed to perform a certain number of given fundamental steps, and must remain in a certain region of the lattice. It is then required to find the number of ways, or probability, of getting from an initial point to a final point. The oldest such problem is the celebrated ballot problem in which it is required to find the number of ways of walking from the origin to a typical point (m_{1}, ..., m_{n}) , performing positive unit steps, such that the walk remains in the region x_{1} ≥ ... ≥ x_{n}. More recently Fisher [Fis] and Huse and Fisher [HF] used reflection arguments to consider other such problems.

A beautiful combinatorial proof of the 2-dimensional ballot problem was given by Andre’ [A], using reflection. Andre”s elegant argument is extended to 3 dimensions in [G], to n dimensions in [Z] and [WM], and it was q-analogized by Krattenthaler [K] and Krattenthaler and Mohanty[KM], who gave many far-reaching applications.

In this paper we will show that Andre”s idea extends naturally to the wider context of root systems and Weyl groups. After the first version of this paper was written, Proctor[P] used our method to give new proofs of Cauchy-type symmetric functions identities. We would like to thank Bob Proctor and the referee for many helpful suggestions.

1. Root Systems and their Weyl groups

A root system ([H], [B], [Ca]) is a finite set of vectors in Euclidean n-space such that the reflection of any root with respect to any hyperplane that is perpendicular to a root is yet another root, and such that the difference between any such root and its mirror image with respect to any such hyperplane is an integer multiple of the root corresponding to the hyperplane. If we allow affine hyperplanes and affine vectors, we get affine root systems ([M1]). A root system is called reduced if for any root α, kα can’t be a root unless k = ±1. The set of linear (affine-linear) transformations generated by all the reflections with respect to the hyperplanes perpendicular to the roots is called

1 AMS Subject Classification. Primary: 05A15, 60J15. 2 Department of Mathematics, Brandeis University, Waltham, MA 02254-9110. Supported in part

by NSF grant DMS-8902666. 3 Department of Mathematics, Temple University, Philadelphia, PA 19122. Supported in part by

NSF grant DMS-8800663. the Weyl group.

Both finite and affine root systems have been completely characterized ([B] and [M1] respectively). Every root system is a direct sum of irreducible root systems. There are five infinite families of irreducible finite root systems, four of which are reduced (A_{n}, B_{n}, C_{n}, D_{n}), and one of which is not (BC_{n}), and five exceptional cases (G_{2}, F_{4}, E_{6}, E_{7}, E_{8}) all of which are reduced ([B]). The irreducible, reduced, affine root systems fall into seven infinite families (A_{n}, B_{n}, B_{n}^{v}, C_{n}, C_{n}^{v}, D_{n}, BC_{n}), and seven exceptional cases (G_{2}, G_{2}^{v}, F_{4}, F_{4}^{v}, E_{6}, E_{7}, E_{8} ([M1]).) We refer the reader to the comprehensive planches of [B] and the appendix of [M1] for a description of these root systems. For example the finite root system A_{n} consists of the n(n − 1) vectors e_{i} − e_{j}, 1 ≤ i ≠ j ≤ n, where e_{i} is the unit vector with all zeroes except the i^{th} component which is 1, and its Weyl group is the symmetric group acting by permuting the coordinates.

The Weyl group of a finite root system is a finite group, and that of an affine root system is a discrete group acting locally finitely. The complement of the union of all the hyperplanes is an open set, and its connected components are called Weyl chambers. It is easy to see that any Weyl chamber is a fundamental region for the action of the Weyl group.

2. The Fundamental Formula

We will use the notation of [H] and [M1]. Let R be a finite or affine root system, let W be its Weyl group, and let Δ be any of its bases. The length of an element w of the Weyl group, l(w), is the least number of terms possible to express w as a product of fundamental reflections σ_{α}, αϵΔ. We will consider random walk in a lattice L embedded in the euclidean space in which R resides, with inner product inherited from it, and which is invariant under the action of the Weyl group: gL = L for every g in W. We fix a set of allowable steps S, that is a finite subset of L which is also invariant under the Weyl group:W S = S. We will also assume that for any α in Δ, the non-zero values of (α, s), as s ranges over S, are ±k(α), where k(α) is a fixed number that depends only on α. Now, for any positive integer m, and any two lattice points a and b, let

W ALK_{m}(a → b)

be the number of walks from a to b, using exactly m steps drawn from the set S.

Let a and b be two lattice points that belong to the fundamental Weyl chamber

C := {xϵL : (x, α) > 0 for every alpha}

and such that for every α in Δ, (a, α) and (b, α) are integral multiples of k(α). We are interested in

W ALK_{m}^{G}(a → b) ,

the number of walks from a to b that always stay strictly within the Weyl chamber C. The fundamental result of our paper is the following theorem.

Theorem 1: With the above notation and assumptions, we have

W ALK_{m}^{G}(a → b) = ∑_{wϵW}(−1)^{l(w)}W ALK_{m}(w(a) → b) .  (1)

Proof: The proof is modeled after [Z], (where as Krattenthaler [K] observed, ”first” should be replaced by ”last”). Totally order the roots of Δ by some arbitrary but fixed order. Let W ALK_{m}^{B}(a → b) be the number of bad walks from a to b, i.e., walks that bump into at least one of the walls of C, x : (x, α) = 0 for some α in Δ. The assumption on S, that the absolute value of (α, s) is either zero or a constant that only depends on α, guarantees that every walk that crosses a wall must touch it, i.e., it is not possible to get from inside C to outside C and vice versa, without pausing on some wall. Thus

W ALK_{m}^{G}(a → b) = W ALK_{m}(a → b) − W ALK_{m}^{B}(a → b).  (2)

We now claim that

∑_{wϵW}(−1)^{l(w)}W ALK_{m}^{B}(w(a) → b) = 0.  (3)

Indeed, let walk := (s_{1}, ..., s_{n}) be a typical bad walk from, say, w(a) to b. This means that the walker bumps into at least one wall (x, α) = 0, αϵΔ. Let α be the fundamental root corresponding to the last visit to a wall. In case of a ”tie”, in which that last visit takes place on more than one wall, let α be the ”largest” such root in the above mentioned total order. We pair to this walk the walk from w_{α}w(a) to b obtained by reflecting, with respect to (x, α) = 0, that portion of the walk until the last visit to the wall (x, α) = 0. In symbols, if the last visit to a wall was at the r^{th} step, and the walk from w(a) to b was (s_{1}, ..., s_{m}), then the paired walk, from w_{α}w(a) to b is (w_{α}(s_{1}), ..., w_{α}(s_{r}), s_{r+1}, ..., s_{m}). This pairing of walks is clearly an involution, since w_{α} is an involution. It is sign reversing, since the length of w and w_{α}w have opposite parity. It follows that all the terms in (3) can be arranged in mutually canceling pairs, and thus the sum total is zero.

Now, if w is not the identity, w(a) is outside C, since C is a fundamental region, and so every walk from w(a) to b must cross a wall, and hence is bad, so

W ALK_{m}^{B}(w(a) → b) = W ALK_{m}(w(a) → b), w ≠ identity .  (4)

Combining (2), (3), and (4) yields (1). QED

In the affine case, the Weyl group is infinite, but since it is discrete, the sum in (1) is always finite. It is readily seen that for the affine root system S(A_{n}), (1) reduces to Filaseta’s theorem ([Fil], p. 103), since the Weyl group of S(A_{n}) is the semi-direct product of the symmetric group and the group of translations on the lattice M, described in [M1], p. 92.

3. Constant Term and Integral Representation Formulas

We will now derive some constant term and integral representation formulas for W ALK_{m}(a → b) and W ALK_{m}^{G}(a → b), for finite root-systems. First we will deal with the simple case of unrestricted walks. If the walk takes place in Z^{n}, then let x_{1}, ..., x_{n} be indeterminates. For any vector of integers a = (a_{1}, ..., a_{n}), let

x^{a} := x_{1}^{a_{1}}...x_{i}^{a_{i}}...x_{n}^{a_{n}},

otherwise, we think of x^{a} as ”formal exponetial”. For our set of steps S, let

Φ(x) := ∑_{sϵS} x^{s} .

Recall that a Laurent polynomial is a linear combination of exponents x^{a}. The constant term of a Laurent polynomial f, denoted by CT f, is the coefficient of x^{0}. The following theorem is almost trivial:

Theorem 2:

W ALK_{m}(a → b) = CT Φ(x)^{m}/x^{b−a} .  (5)

Proof: Obviously W ALK_{m}(a → b) = W ALK_{m}(0 → b − a), so without loss of generality, we can assume that a = 0, since every step is independent of the others. When we multiply out Φ(x)^{m}, every term, before simplification, corresponds to a walk with m steps, and those terms that evaluate to x^{b} correspond to walks that end at b, so the coefficient of x^{b} gives exactly W ALK_{m}(0 → b). QED

Combining Theorems 1 and 2, we have

Theorem 3:

W ALK_{m}^{G}(a → b) = CT [ Φ(x)^{m}x^{−b} ∑_{wϵW}(−1)^{l(w)}x^{w(a) ]} .  (6)

For special values of a, the sum on the right side of (6) factorizes nicely, thanks to the celebrated Weyl denominator formula ([H], p. 138; [Ca], p. 149), which we now recall. Let δ be one half of the sum of all the positive roots:

δ := (1/2) ∑_{αϵR^{+}} α .

Then we have

The Weyl Denominator Formula

∑_{wϵW}(−1)^{l(w)}x^{w(δ)} = x^{−δ} ∏_{αϵR^{+}}(x^{α} − 1) .

Plugging this into Theorem 3 we have:

Theorem 4: For any scalar c such that cδ is a lattice point, and for any lattice vector λ that is invariant under the Weyl group (i.e., w(λ) = λ for every w in W), and such that (λ + cδ, α) is an integral multiple of k(α) for every α in Δ, we have

W ALK_{m}^{G}( λ + cδ → b) = CT [Φ(x)^{m}x^{−b+λ−cδ} ∏_{αϵR^{+}}(x^{cα} − 1) ] .  (7)

If we replace each x_{j} with e^{iθ_{j}}, j = 1, ..., n, and replace the operator ”constant term” with that of integration over the torus [0, 2π]^{n}, Theorems 3 and 4 become integral representation formulas, from which it is possible, in many cases, to obtain asymptotic formulas, generalizing the formulas on p. 676 of Fisher [Fis]. Let us mention that the constant A_{p} appearing in formulas (4.9) and (4.10) of [Fis] can be evaluated explicitly by Mehta’s [M2] integral, and its analogs for the other rootsystems follow from the Macdonald-Mehta conjectures, proved for the infinite families by Regev and Beckner (see [M2]), for F_{4} by Garvan [Ga], and for all root systems by Opdam[O]. REFERENCES

[A] André, D., Solution directe du problème résolu par M. Bertrand, C. R. Acad. Sci. Paris 105 (1887), 436-437.

[BG] Benson, C. T., and Grove, L. C., ”Finite Reflection Groups”, Bogden & Quigley, Terrytownon-Hudson, NY, 1971.

[B] Bourbaki. N., ”Groupes et algèbres de Lie”, chaps. 4, 5, and 6, Hermann, Paris, 1968.

[Ca] Carter, R. W., ”Simple Groups of Lie Type”, John Wiley, London, 1972.

[Co] Coxeter, H. S. M., Discrete groups generated by reflections, Ann. Math. 35 (1934), 588-621.

[Fil] Filaseta, M., A new method for solving a class of ballot problems, J. Combin. Theory Ser. A 39 (1985), 102-111.

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

[Ga] Garvan, F., Some Macdonald-Mehta integrals by brute force, in ”q-Series and Partitions”, D. Stanton, editor, IMA Volumes in Mathematics and its Applications, Springer, New York, 1989.

[Gr] Grossman, H. D., Fun with lattice points, Scripta Math. 16 (1950), 206-212.

[H] Humphreys, J. E., ”Introduction to Lie Algebras and Representation Theory”, Springer, New York, 1972.

[H1] Humphreys, J. E., ”Reflection Groups and Coxeter Groups”, Cambridge University Press, Cambridge, 1990.

[HF] Huse, D., and Fisher, M. E., Commensurate melting, domain walls, and dislocations, Physical Review B 29 (1984), 239-270.

[K] Krattenthaler, C., Enumeration of lattice paths and generating functions for skew plane partitions, Manuscripta Math. 63 (1989), 129-155.

[KM] Krattenthaler, C., and Mohanty, S. G., q-Generalizations of a ballot problem, preprint.

[M1] Macdonald, I. G., Affine root systems and Dedekind’s eta-function, Inv. Math. 15 (1972), 91-143.

[M2] Macdonald, I. G., Some conjectures for root systems and finite reflection groups, SIAM J.

Math. Anal., 13 (1982), 988-1007.

[O] Opdam, E., Some applications of hypergeometric shift operators, Inv. Math. 98 (1989), 1-18.

[P] Proctor, R. A., Reflection and algorithm proofs of some more Lie group dual pair identities, preprint.

[WM] Watanabe, T., and Mohanty, S. G., On an inclusion-exclusion formula based on the reflection principle, Discrete Math. 64 (1987), 281-288.

[Z] Zeilberger, D., André’s reflection proof generalized to the many-candidate ballot problem, Discrete Math. 44 (1983), 325-326.