.EQ
delim $$
.EN
.nr Pi 10
.nr Pt 1

.LP
\fBRANDOM WALK IN A WEYL CHAMBER\*F
.FS
AMS Subject Classification. Primary: 05A15, 60J15.
.FE
\fR
.SP1
.LP
\fIIra M. Gessel*
.FS*
Department of Mathematics, Brandeis University, Waltham, MA 02254-9110.
Supported in part by NSF grant DMS-8902666.
.FE
and Doron Zeilberger**\fR
.FS**
Department of Mathematics, Temple University,
Philadelphia, PA 19122. Supported in part by NSF grant DMS-8800663.
.FE
.SP1
\fBAbstract:\fR The classical Ballot problem that counts  the number of
ways of walking from the origin and  staying within the wedge 
$x sub 1 >= x sub 2 >= ... >= x sub 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.
.SP1
\fB0. Introduction\fR
.SP1
.P
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.
.P
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 \fIgiven\fR 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 \fIballot problem\fR 
in which it is required to find the number of ways of walking
from the origin to a typical point 
$( m sub 1 , ... , m sub n )$ , performing positive unit steps,
such that the walk remains in the region
$x sub 1 >= ... >= x sub n$.  More recently Fisher [Fis] and
Huse and Fisher [HF] used reflection arguments to
consider other such problems.
.P
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.
.P
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.
.SP1
.LP
\fB1. Root Systems and their Weyl groups\fR
.SP1
.P
A \fIroot system\fR ([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 \fIinteger\fR multiple
of the root corresponding to the hyperplane. If we allow affine
hyperplanes and affine vectors, we get \fIaffine root systems\fR
([M1]). A root system is called \fIreduced\fR if for any root
$alpha$, $k alpha$ 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 the \fIWeyl group\fR.
.P
Both finite and affine root systems have been completely characterized
([B] and [M1] respectively). Every root system is a direct
sum of \fIirreducible\fR root systems. There are five infinite
families of irreducible finite root systems, four of which are
reduced ($A sub n$, $B sub n$, $C sub n$, $D sub n $), and
one of which is not ($BC sub n$), and five exceptional
cases ($G sub 2$, $F sub 4$, $E sub 6$, $E sub 7$, $E sub 8$) all
of which are reduced ([B]). The irreducible, reduced, affine
root systems fall into
seven  infinite families ($A sub n$, $B sub n$, ${B sub n} sup v$,
$C sub n$, ${C sub n} sup v$, $D sub n$, $BC sub n$), and
seven exceptional cases ($G sub 2$, 
${G sub 2} sup v$, $F sub 4$,
${F sub 4 } sup v$, $E sub 6$, $E sub 7$, $E sub 8 $ ([M1]).)
We refer the reader to the comprehensive \fIplanches\fR of
[B] and the appendix of [M1] for a description of these
root systems. For example the finite root system $A sub n$
consists of the $n(n-1)$ vectors 
{$ e sub i - e sub j ,~ 1 <= i != j <= n $}, 
where $e sub i$ is the unit vector with all zeroes except
the $i sup th$ component which is $1$, and its Weyl
group is the symmetric group acting by permuting the coordinates.
.P
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
\fIWeyl chambers\fR. It is easy to see that any Weyl chamber
is a fundamental region for the action of the Weyl group. 
.SP1
.LP
\fB 2. The Fundamental Formula\fR
.SP1
.P
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 $DELTA$ 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 
$sigma sub alpha$, $alpha epsilon DELTA$.
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: $ g L = 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:$WS=S$.
We will also assume that for any
$alpha$ in $DELTA$, the non-zero values of $( alpha , s )$, as
$s$ ranges over $S$, are $+- k( alpha )$, where $k ( alpha )$
is a fixed number that depends only on
$alpha$. Now, for any positive integer $m$, and any two lattice points
$a$ and $b$, let
.SP1
.EQ
WALK sub m ( a -> b )
.EN
.SP1
.LP
be the number of walks from $a$ to
$b$, using exactly $m$ steps
drawn from the set $S$.
.P
Let $a$ and $b$ be two lattice points that belong to
the fundamental Weyl chamber 
.SP1
.EQ
C:=~ "{" x epsilon L ~:~ (x , alpha ) > 0 ~for~every~alpha "}"
.EN
.SP1
and such that for every $alpha$ in $ DELTA$,
$(a, alpha )$ and  $(b, alpha )$ are integral multiples
of  $k ( alpha )$.
We are interested in 
.SP1
.EQ
WALK sub m sup G ( a -> b )~,
.EN
.SP1
.LP
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.
.SP1
.LP
\fBTheorem 1:\fR With the above notation and assumptions, we have
.SP1
.EQ(1)
WALK sub m sup G (a -> b ) ~=~
sum from { w epsilon W } (-1) sup l(w) WALK sub m (w(a) -> b )~.
.EN
.SP1
\fBProof\fR: The proof is modeled after [Z], (where as
Krattenthaler [K] observed, "first" should be replaced
by  "last").
Totally order the roots of $DELTA$ by some arbitrary but fixed
order.
Let $WALK sub m sup B (a -> b ) $ be the number of
\fIbad\fR walks from $a$ to $b$, i.e., walks that
bump into at least one of the walls of $C$, 
{ $x~:~(x, alpha )=0$ } for some $alpha$ in $DELTA$.
The assumption on
$S$, that the absolute value of $( alpha , s )$ is either
zero or a constant that only depends on $alpha$, 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
.SP1
.EQ(2)
WALK sub m sup G (a -> b ) ~=~
WALK sub m  (a -> b ) ~-~ WALK sub m sup B (a -> b ) .
.EN
.SP1
.LP
We now claim that
.SP1
.EQ(3)
sum from { w epsilon W } (-1) sup l(w) WALK sub m sup B (w(a) -> b )~=~0.
.EN
.SP1
.LP
Indeed, let $walk:=( s sub 1 , ... , s sub n )$ be a typical bad walk
from, say, $w(a)$ to $b$. This means that the walker bumps into
at least one wall $(x, alpha ) =0$, $alpha epsilon DELTA$. Let
$alpha$ 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 $alpha$ be the "largest" such
root in the above mentioned total order.
We pair to this walk the walk
from $w sub alpha w (a)$ to $b$ obtained by reflecting,
with respect to $(x, alpha )=0$, that portion
of the walk until the last visit to the wall $( x, alpha )=0$.
In symbols, if the last visit to a wall was at the $r sup th$
step, and the walk from $w(a)$ to $b$ was 
$( s sub 1 , ... , s sub m )$, then
the paired walk, from $w sub alpha w (a)$ to $b$ is
$ ( w sub alpha ( s sub 1 ) , ... , w sub alpha ( s sub r )  ,$
$s sub r+1 , ... , s sub m )$. This pairing of walks is clearly
an involution, since $w sub alpha$ is an involution. It is sign
reversing, since the length of $w$ and $w sub alpha 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.
.P
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 
.SP1
.EQ(4)
WALK sub m sup B ( w(a) -> b )~=~ WALK sub m  ( w(a) -> b ),~~ 
w != identity ~.
.EN
.SP1
.LP
Combining (2), (3),  and (4) yields (1). \(sq
.SP1
.P
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 sub n )$, (1) reduces to
Filaseta's theorem ([Fil], p. 103), since the Weyl group of 
$S( A sub n )$ is the semi-direct product of the symmetric group
and the group of translations on the lattice $M$, described in
[M1], p. 92.
.SP1
\fB3. Constant Term and Integral Representation Formulas\fR
.SP1
.P
We will now derive some constant term and integral representation
formulas for $WALK sub m (a -> b)$ and $WALK sub m sup 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 sup n$, then
let $x sub 1$, ..., $x sub n$ be indeterminates. For any vector
of integers $a= ( a sub 1 , ... , a sub n )$, let
.SP1
.EQ
x sup a := x sub 1 sup {a sub 1} ... x sub i sup {a sub i} ... x sub n 
sup {a sub n},~~~
.EN
.SP1
.LP
otherwise, we think of $x sup a$ as "formal exponetial".
For our set of steps $S$, let
.SP1
.EQ
PHI (x) :=   sum from { s epsilon S } x sup s~.
.EN
.SP1
.P
Recall that a \fILaurent polynomial\fR is a linear combination of
exponents $x sup a$. The \fIconstant term\fR of a Laurent polynomial
$f$, denoted by $CT^ f$, is the coefficient of $x sup 0$.
The following theorem is almost trivial:
.SP1
\fBTheorem 2\fR: 
.SP1
.EQ(5)
WALK sub m (a -> b) = CT ~ PHI (x) sup m / x sup {b-a} ~.
.EN
.SP1
.LP
\fBProof:\fR Obviously
$WALK sub m (a -> b) = WALK sub 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 $PHI (x) sup m$, every term, before
simplification, corresponds to a walk with $m$ steps, and those
terms that evaluate to $x sup b$ correspond to walks that end at $b$,
so the coefficient of $x sup b$ gives exactly  
$WALK sub m (0 -> b)$.  \(sq
.SP1
.P
Combining Theorems 1 and 2, we have 
.SP1
.LP
\fBTheorem 3:\fR 
.SP1
.EQ(6)
WALK sub m sup G (a -> b ) = CT ~[~ PHI (x) sup m x sup -b 
 sum from {w epsilon W} (-1) sup l(w) x sup w(a)~] ~.
.EN
.SP1
.P
For special values of $a$, the sum on the right side of (6) 
factorizes nicely,
thanks to the celebrated \fIWeyl denominator formula\fR ([H], p. 138;
[Ca], p. 149), which we now recall. Let $delta$ be one half of the sum
of all the positive roots:
.SP1
.EQ
 delta := (1/2) sum from {alpha epsilon R sup + } alpha ~.
.EN
.SP1
Then we have
.SP1
.LP
\fBThe Weyl Denominator Formula\fR
.SP1
.EQ
sum from { w epsilon W } (-1) sup l(w) x sup { w( delta ) } =
 x sup {- delta} prod from { alpha epsilon R sup + } 
 ( x sup alpha -1 )~.
.EN
.SP1
Plugging this into Theorem 3 we have:
.SP1
.LP
\fBTheorem 4:\fR For any scalar $c$ such that $c delta $ 
is a lattice point,
and for any lattice vector $lambda$ that is invariant under the
Weyl group (i.e., $w( lambda ) = lambda$ for every $w$ in $W$), and 
such that $( lambda + c delta , alpha )$ is an integral multiple
of $k( alpha )$ for every $alpha$ in $DELTA$, we have
.SP1
.EQ(7)
WALK sub m sup G ( ~ lambda + c delta  ~-> ~ b ) = CT~ [ PHI (x) sup m 
 x sup {-b+ lambda - c delta } prod from { alpha epsilon R sup + } 
 ( x sup {c alpha} -1 )~]~.
.EN
.SP1
.P
If we replace each $x sub j$ with $e sup {i theta sub j}$, 
$j= 1, ... ,  n$,  and replace the operator "constant term" with that of
integration over the torus
$[0,~ 2 pi ] sup 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 sub 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 root-systems
follow from the Macdonald-Mehta conjectures, proved for the infinite
families by Regev and Beckner (see [M2]), for $F sub 4$ by Garvan [Ga],
and for all root systems by Opdam[O].

.SP1
.LP
\fIREFERENCES\fR
.SP1
.LP
[A] Andre\*', D., \fISolution directe du proble\*`me re\*'solu
par M. Bertrand\fR, C. R. Acad. Sci. Paris \fB105\fR (1887),
436-437.
.SP1
.LP
[BG] Benson, C. T., and Grove, L. C., "\fIFinite Reflection Groups\fR",
Bogden & Quigley, Terrytown-on-Hudson, NY, 1971.
.SP1
.LP
[B] Bourbaki. N., "\fIGroupes et alge\*`bres de Lie\fR", chaps. 4, 5, 
and 6, Hermann, Paris, 1968.
.SP1
.LP
[Ca] Carter, R. W., "\fISimple Groups of Lie Type\fR", John Wiley,
London, 1972.
.SP1
.LP
[Co] Coxeter, H. S. M., \fIDiscrete groups generated by reflections\fR,
Ann. Math. \fB35\fR (1934), 588-621.
.SP1
.LP
[Fil] Filaseta, M., \fIA new method for solving a class of ballot
problems\fR, J. Combin. Theory Ser. A \fB39\fR (1985), 102-111.
.SP1
.LP
[Fis] Fisher, M. E., \fIWalks, walls, wetting, and melting\fR,
J. Stat. Phys. \fB34\fR (1984), 667-729.
.SP1
.LP
[Ga] Garvan, F., \fISome Macdonald-Mehta integrals by brute
force\fR, in "\fIq-Series and Partitions\fR", D. Stanton, editor,
IMA Volumes in Mathematics and its Applications, Springer, New York,
1989.
.SP1
.LP
[Gr] Grossman, H. D., \fIFun with lattice points\fR, Scripta Math.
\fB16\fR (1950), 206-212.
.SP1
.LP
[H] Humphreys, J. E., \fI"Introduction to Lie Algebras and
Representation Theory"\fR, Springer, New York, 1972.
.SP1
.LP
[H1] Humphreys, J. E., \fI"Reflection Groups and Coxeter Groups"\fR,
Cambridge University Press, Cambridge, 1990.
.SP1
.LP
[HF] Huse, D., and Fisher, M. E., \fICommensurate melting,
domain walls, and dislocations\fR, Physical Review B \fB29\fR
(1984), 239-270.
.SP1
.LP
[K] Krattenthaler, C., \fIEnumeration of lattice paths and
generating functions for skew plane partitions\fR, Manuscripta
Math. \fB63\fR (1989), 129-155.
.SP1
.LP
[KM] Krattenthaler, C., and Mohanty, S. G., \fIq-Generalizations of
a ballot problem\fR, preprint.
.SP1
.LP
[M1] Macdonald, I. G., \fIAffine root systems and Dedekind's 
$eta$-function\fR, Inv. Math. \fB15\fR (1972), 91-143.
.SP1
.LP
[M2] Macdonald, I. G., \fISome conjectures for root systems and
finite reflection groups\fR, SIAM J. Math. Anal., \fB13\fR (1982),
988-1007.
.SP1
.LP
[O] Opdam, E., \fISome applications of hypergeometric shift
operators\fR, Inv. Math. \fB98\fR (1989), 1-18.
.SP1
.LP
[P] Proctor, R. A., \fIReflection and algorithm proofs of some more
Lie group dual pair identities\fR, preprint.
.SP1
.LP
[WM] Watanabe, T., and Mohanty, S. G., \fIOn an inclusion-exclusion
formula based on the reflection principle\fR, Discrete Math. \fB64\fR
(1987), 281-288.
.SP1
.LP
[Z] Zeilberger, D., \fIAndre\*''s reflection proof generalized to
the many-candidate ballot problem\fR, 
Discrete Math. \fB44\fR (1983), 325-326.