%\input amstex
%\input amspptbk.sty



\magnification1200
\hsize13cm
\vsize19cm

\input path.sty

\TagsOnRight

\def\VienAA{15}
\def\RoZeAA{14}
\def\ModaAA{13}
\def\LindAA{12}
\def\KulkAC{11}
\def\KrLaAA{10}
\def\KrRuAA{9}
\def\KrPrAA{8}
\def\KratBQ{7}
\def\KratBE{6}
\def\GeViAB{5}
\def\FultAC{4}
\def\DeViAA{3}
\def\CoHeAA{2}
\def\BiLaAA{1}

\def\mult{\operatorname{mult}}
\def\EN{\operatorname{EN}}
\def\GF{\operatorname{GF}}
\def\Gr{\operatorname{Gr}}
\def\nipaths{\frak n\frak i\frak p\frak a\frak t\frak h\frak s}
\def\Rmsets{\frak R\frak m\frak s\frak e\frak t\frak s}
\def\points{\text{\tt points}}
\def\Mpoints{\text{\tt Mpoints}}
\def\lightshadow{\text{\tt lightshadow}}
\def\3{\ss}

\topmatter 
\title On multiplicities of points on Schubert varieties in
Gra\3mannians II
\endtitle 
\author C.~Krattenthaler\footnote"$^\dagger$"{Partially supported
by EC's IHRP Programme, grant HPRN-CT-2001-00272, 
``Algebraic\linebreak
\hbox{ Combinatorics in Europe", and by the
Austrian Science Foundation FWF, 
grant P13190-MAT.}\hss}\footnote"*"{Current address: Institut Girard 
Desargues, Universit\'e Claude Bernard Lyon-I, 
21, avenue Claude \hbox{Bernard, F-69622 Villeurbanne Cedex, France;
e-mail: {\tt kratt\@euler.univ-lyon1.fr}.}\hss}
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\
e-mail: KRATT\@Ap.Univie.Ac.At\\
WWW: \tt http://www.mat.univie.ac.at/\~{}kratt
\endaffil
\address Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.
\endaddress
%\email KRATT\@Ap.Univie.Ac.At\\
%WWW: \tt http://www.mat.univie.ac.at/People/kratt\endemail
%\dedicatory \enddedicatory
%\date \enddate
%\thanks \endthanks
\subjclass Primary 14M15;
 Secondary 05A15 05E15 14H20
\endsubjclass
\keywords Schubert varieties, singularities, multiplicities,
non-intersecting lattice paths, turns of paths\endkeywords
\abstract 
We prove a conjecture by Kreiman and Lakshmibai on a combinatorial
description of multiplicities of points on Schubert
varieties in Gra\3mannians in terms of certain sets of reflections in
the corresponding Weyl group. The proof is accomplished by relating
these sets of reflections to the author's previous
combinatorial interpretation of these multiplicities in terms of
non-intersecting lattice paths (S\'eminaire Lotharingien Combin\.
{\bf 45} (2001), Article~B45c).
Moreover, we provide a compact formula for the
Hilbert series of the tangent cone to a Schubert variety in a
Gra\3mannian assuming the truth of another conjecture of Kreiman and
Lakshmibai. 

\endabstract
\endtopmatter
\document

\leftheadtext{C. Krattenthaler}


\subhead 1. Introduction\endsubhead
The {\it multiplicity} of a point on an algebraic variety is an important 
invariant that ``measures" singularity of the point.
It was an important recent advance in Schubert calculus when 
Rosenthal and Zelevinsky \cite{\RoZeAA} gave a
determinantal formula for the multiplicity of a point on
a Schubert variety in a Gra\3mannian. It paved the way to a
combinatorial understanding of this multiplicity. More precisely, it
was shown in \cite{\KratBQ} that it counts certain families of
non-intersecting lattice paths (and also certain tableaux). An
alternative, conjectural
combinatorial interpretation was proposed by Kreiman and
Lakshmibai in \cite{\KrLaAA, Conjecture~2}, in terms of certain sets of
reflections. The purpose of this paper is to prove that this latter
combinatorial interpretation is indeed valid.

The reason for the proposition of this alternative combinatorial
interpretation of the multiplicity of a point on
a Schubert variety in a Gra\3mannian in terms of sets of reflections
is that it appears that these sets of reflections also allow the
computation of the Hilbert series of the tangent cone at this
point (see \cite{\KrLaAA, Conjecture~1}). 
While we are not able to prove this more general 
conjecture\footnote{See, however, the Note at the end of this paper.}, 
we provide an
equivalent form of the conjecture in which the Hilbert series is
essentially given in terms of a generating function for certain
families of non-intersecting lattice paths which are counted with
respect to turns. This equivalent form of the conjecture has the
advantage over the original form that it reduces the computation of
the Hilbert series to a finite problem. Moreover, it is analogous to
similar formulas for the Hilbert series associated to related 
determinantal varieties (see \cite{\CoHeAA, Eq.~(1)}, 
\cite{\KrPrAA, p.~1021, line~11} 
or \cite{\KrRuAA, Theorem~1}).

Our paper is organised as follows.
In the next section we fix notation and formulate the multiplicity
conjecture by Kreiman and Lakshmibai. There we also recall the
author's combinatorial interpretation of the multiplicity in terms of
non-intersecting lattice paths. Section~3 contains the proof of the
conjecture, which is accomplished 
by showing that these non-intersecting
lattice paths and the sets of reflections of Kreiman and Lakshmibai
are essentially the same objects.
In fact, we prove a more general assertion (see Claim~2), which allows
us to show, in Theorem~2 of Section~4, 
the above mentioned reformulation, in terms of
non-intersecting lattice paths, of 
Conjecture~1 in \cite{\KrLaAA} on the Hilbert series of the tangent
cone to a Schubert variety in a Gra\3mannian. 
It is an open problem to find a compact formula for the generating
function of non-intersecting lattice paths that appears in this
formulation (see Remark~(2) after Theorem~2).

\subhead 2. Combinatorial interpretations of multiplicities of points
on Schubert varieties in Gra\3mannians\endsubhead
We recall some basic notions from the Schubert calculus
in the Gra\3mannian, and fix the notation that we are going to use.
We refer the reader to \cite{\BiLaAA, Sec.~3.1} and \cite{\FultAC, Sec.~9.4}
for in-depth introductions into the subject.


\smallskip
Let $d$ and $n$ be positive integers with $0\le d\le n$. The {\it
Gra\3mannian} $\Gr_d(V)$ is the variety of all $d$-dimensional
subspaces in an $n$-dimensional vector space $V$ (over some
algebraically closed field of arbitrary characteristic). 
Schubert varieties in the Gra\3mannian $\Gr_d(V)$ are indexed by 
elements in 
$S_n/(S_d\times S_{n-d})$, where $S_m$ denotes the symmetric group of
order $m$. Any coset $C$ in $S_n/(S_d\times S_{n-d})$ has a {\it minimal
representative}, which is the unique permutation $w=i_1i_2\dots i_n$ in $C$ 
such that $i_1<i_2<\dots<i_d$ and
$i_{d+1}<\dots<i_{n-1}<i_n$. We will often identify such a minimal
representative $w$ with the vector $\bold i=(i_1,i_2,\dots,i_d)$ of its
first $d$ elements. The usual {\it Ehresmann--Bruhat order} on $S_n$
induces an order on the cosets of $S_n/(S_d\times S_{n-d})$. Given
two representatives $w$ and $\tau$, 
identified with $\bold i=(i_1,i_2,\dots,i_d)$ and 
$\bold j=(j_1,j_2,\dots,j_d)$, respectively, 
$\tau$ is less than or equal to $w$
in this induced Ehresmann--Bruhat order if and only if $j_\ell\le i_\ell$ for
all $\ell=1,2,\dots, d$. 
In that case, we write $\tau\le w$, respectively $\bold j\le \bold i$.

Given a minimal representative $w$, we denote the corresponding
{\it Schubert variety} in the Gra\3mannian $\Gr_d(V)$ by $X(w)$. It is
well-known that $X(w)$ decomposes into the disjoint union 
of {\it Schubert cells} which are indexed by elements
$\tau\in S_n/(S_d\times S_{n-d})$ with $\tau\le w$. 
The multiplicity of a point $x$ in
$X(w)$ is constant on each Schubert cell.
Following \cite{\KrLaAA} we denote the
multiplicity of a point $x$ in the Schubert cell indexed by $\tau$
by $\mult_\tau X(w)$. In slight abuse of terminology
we will often call it the 
``multiplicity of the point $\tau$ on the Schubert variety $X(w)$."

\smallskip
Let us now recall the multiplicity formula conjectured in \cite{\KrLaAA}. 
We are given two minimal representatives $w$ and
$\tau$ of cosets in $S_n/(S_d\times S_{n-d})$ with $\tau\le w$.
In Conjecture~2 of \cite{\KrLaAA}, 
sets $S$ of reflections $s=(x,y)$, $1\le x\le d$, $d+1\le y\le
n$ (here we use standard transposition notation), are considered
with the property that
\roster
\item "(S1)" Any chain (in the Ehresmann-Bruhat order on $S_n$) 
$s_1>s_2>\dots>s_t$ of commuting reflections,
all of them contained in $S$, satifies $w\ge\tau s_1\cdots s_t$ (in
the induced Ehresmann--Bruhat order on $S_n/(S_d\times S_{n-d})$);
\item "(S2)" $S$ is maximal with respect to property (S1).
\endroster

It should be noted that, if $s_i=(x_i,y_i)$, $1\le i\le t$, then
$s_1>s_2>\dots>s_t$ is a chain of commuting reflections if and only if
$x_1<x_2<\dots<x_t$ and $y_1>y_2>\dots>y_t$.

For the future, since all the reflections which we consider in
this paper will always be reflections $(x,y)$ with 
$1\le x\le d$ and $d+1\le y \le n$, let us abbreviate this set
of reflections by $[1,d]\times[d+1,n]$ (in slight abuse of standard
notation). 

For an illustration of the conditions (S1) and (S2), 
let us consider the example $n=7$, $d=3$, $w=3561247$ and 
$\tau=1352467$, so that the corresponding $\bold i$ and $\bold j$ are
$\bold i=(3,5,6)$ and $\bold j=(1,3,5)$. Then there are exactly two sets 
of reflections (contained in $[1,d]\times[d+1,n]=
[1,3]\times[4,7]\}$) satisfying (S1) and (S2):
$$\big([1,3]\times[4,6]\big)\backslash\{(1,6)\}
\quad \text{and}\quad 
\big([1,3]\times[4,6]\big)\backslash\{(2,5)\}.
\tag2.1$$
To see this, we first observe that a set of reflections satisfying
(S1) cannot contain a reflection $(x,7)$, $x\le 3$. 
For, we have
$$(\tau \circ(x,7))(x)=\left(
\pmatrix 1\ 2\ 3\ 4\ 5\ 6\ 7\\1\ 3\ 5\ 2\ 4\ 6\ 7\endpmatrix
\circ(x,7)\right)(x)=7,$$
and therefore the minimal representative of $\tau\circ (x,7)$ in
$S_n/(S_d\times S_{n-d})$ is 
$$r_1r_27r_4\dots r_7\not\le 3561247=w,$$
a contradiction to (S1).

Second, we observe that $(1,6)$ and $(2,5)$ cannot be both in a set
of reflections satisfying (S1), because they form a chain of commuting
reflections and
$$\tau \circ(1,6)\circ(2,5)=
\pmatrix 1\ 2\ 3\ 4\ 5\ 6\ 7\\1\ 3\ 5\ 2\ 4\ 6\ 7\endpmatrix
\circ(1,6)\circ(2,5)=\pmatrix 1\ 2\ 3\ 4\ 5\ 6\ 7\\
6\ 4\ 5\ 2\ 3\ 1\ 7\endpmatrix.$$
The minimal representative of this permutation in
$S_n/(S_d\times S_{n-d})$ is $4561237\not\le 3561247=w$,
thereby contradicting (S1).

It can now be checked that the two sets in (2.1) do indeed satisfy
(S1). By the above observations, they cannot be enlarged. Thus, they
also satisfy (S2).

\medskip
Now we are in the position to formulate Conjecture~2 from
\cite{\KrLaAA}, which becomes a theorem by our proof in Section~3.

\proclaim{Theorem 1}
The multiplicity of the point $\tau$ on the Schubert variety $X(w)$
is given by
$$\mult _\tau X(w)=\vert\{S:S\subseteq[1,d]\times[d+1,n]\text{ and }
S\text { satisfies {\rm(S1)} and
{\rm(S2)}}\}\vert,\tag2.2$$
where, as before, $[1,d]\times[d+1,n]$ denotes the set of reflections
$(x,y)$ with $1\le x\le d$ and $d+1\le y\le n$.
\endproclaim

\midinsert
\vskip8pt
\vbox{
$$
\Gitter(10,22)(0,0)
%\Koordinatenachsen(-9,10)(0,0)
\PfadDicke{.5pt}
\Pfad(0,-1),2222222222222222222222\endPfad
\Pfad(-1,0),11111111111\endPfad
\PfadDicke{1.2pt}
\Pfad(1,9),22221222112212221111\endPfad
\Pfad(2,9),2212\endPfad
\Pfad(3,9),2\endPfad
\Pfad(4,9),222\endPfad
\Pfad(5,9),222222221221211\endPfad
\Pfad(6,9),22222221\endPfad
\Pfad(7,9),222222\endPfad
\Pfad(8,9),22222222212\endPfad
\Pfad(9,9),22222222\endPfad
%\SPfad(-1,9),11111111111\endSPfad
%\SPfad(1,10),112212221112211\endSPfad
\DickPunkt(1,9)
\DickPunkt(2,9)
\DickPunkt(3,9)
\DickPunkt(4,9)
\DickPunkt(5,9)
\DickPunkt(6,9)
\DickPunkt(7,9)
\DickPunkt(8,9)
\DickPunkt(9,9)
\DickPunkt(3,10)
\DickPunkt(3,12)
\DickPunkt(4,12)
\DickPunkt(7,15)
\DickPunkt(7,16)
\DickPunkt(9,17)
\DickPunkt(9,19)
\DickPunkt(9,20)
\DickPunkt(9,21)
\hskip4.5cm
$$
\centerline{\eightpoint Figure 1}
}
\vskip8pt
\endinsert

Thus, returning to our previous example where $n=7$ and $d=3$,
the theorem says that
$$\mult_{1352467}X(3561247)=2,$$
since the set on the right-hand side of (2.2) in this special case 
consists of the two elements given in (2.1).

\medskip
Next we recall the combinatorial interpretation of multiplicities in
terms of non-intersecting lattice paths from \cite{\KratBQ}, which is
a more or less straight-forward combinatorial translation of the 
Rosenthal--Zelevinsky formula \cite{\RoZeAA} using the
Lindstr\"om--Gessel--Viennot theorem 
\cite{\LindAA, Lemma~1}, \cite{\GeViAB, Theorem~1}.
As before, let $w$ and $\tau$ be two minimal representatives
of cosets from $S_n/(S_d\times S_{n-d})$ with $w\ge \tau$, 
and identify them with $\bold i=(i_1,i_2,\dots,i_d)$,
$1\le i_1<i_2<\dots<i_d\le n$, and $\bold j=(j_1,j_2,\dots,j_d)$,
$1\le j_1<j_2<\dots<j_d\le n$, respectively.
In particular, $\bold i\ge\bold j$.
Furthermore, we define the numbers $\kappa_q:=
\vert \{\ell:i_q<j_\ell\}\vert$. Then 

\vskip-7pt
{\openup-1\jot
$$\align 
\mult_\tau X(w)=&\#\text {\big(families $(P_1,P_2,\dots,P_d)$
of non-intersecting lattice paths,}\\
&\kern11pt
\text {\,where the
path $P_\ell$ runs from $(d+1-\ell,d)$
to }\\
&\kern11pt
\text {\,$(d-\kappa_{\sigma(\ell)},\kappa_{\sigma(\ell)}+i_{\sigma(\ell)}), \
\ell=1,2,\dots,d$,\text{ for some $\sigma\in S_d$}\big).}
\tag2.3
\endalign$$}
\vskip-7pt

\noindent
Here, by {\it lattice path} we mean a lattice path
in the plane consisting of positive 
horizontal and vertical unit steps. Furthermore, a family of lattice
paths is called {\it non-intersecting} if no two paths of the family
have a common point.
To given an example, let $d=9$, $\bold i=(4,6,7,13,14,17,19,20,21)$
and $\bold j=(1,2,4,7,10,12,13,15,16)$. For this choice the vector of
the $\kappa_q$'s is $(6,6,5,2,2,0,0,0,0)$. 
Figure~1 shows a typical family of paths as described in (2.3) 
for this choice of $\bold i$ and
$\bold j$. The
permutation $\sigma$ is $674583129$ in this example.

\remark{Remarks}
At this point, there are several comments to be made, most of them
recalling facts from \cite{\KratBQ}:

\smallskip
(1) In \cite{\KratBQ}
the starting points of the paths are $(-\ell+1,\ell-1)$ and the end
points are $(-\kappa_{\ell},\kappa_{\ell}+i_{\ell})$, $\ell=1,2,\dots,d$ (the
latter in some order, determined by the permutation $\sigma$).
If we shift everything by $d$ units to the right then we obtain the
points $(d+1-\ell,\ell-1)$ and 
$(d-\kappa_{\ell},\kappa_{\ell}+i_{\ell})$. Whereas now
the end points are in agreement, the starting points still differ slightly.
However, the arguments in Section~4
of \cite{\KratBQ} (and, in fact, figures such as Figure~3 in
\cite{\KratBQ}) show that 
portions of paths below the horizontal line $y=d$ are forced and can
therefore be omitted. This means that we may indeed replace the starting points
$(d+1-\ell,\ell-1)$ by the points $(d+1-\ell,d)$.
(In fact, Figure~1 shows exactly the result when the forced
portions of the paths in Figure~3 of \cite{\KratBQ} are cut off.)

(2) The sequence $(\ka_q)_{1\le q\le d}$ is weakly monotone decreasing
if $q$ increases, while 
the sequence $(\ka_q+i_q)_{1\le q\le d}$ is weakly monotone increasing
if $q$ increases. This implies that the end points
$(d-\ka_q,\ka_q+i_q)$, $q=1,2,\dots,d$, of the paths of a family in (2.3)
are arranged from bottom-left to top-right, to be precise,
the $q$-th end point $(d-\ka_q,\ka_q+i_q)$ is weakly to the left and
weakly below the $(q+1)$-st end point
$(d-\ka_{q+1},\ka_{q+1}+i_{q+1})$, $q=1,2,\dots,d-1$. (See Figure~1.)

(3) We have $\ka_q\ge d-i_q$, or, equivalently, $\ka_q+i_q\ge 
d$. Thus, the end points are never below the starting
points of the paths. Moreover, since $\bold i\ge\bold j$,
we have $\ka_q\le d-q$, or, equivalently, $d-\ka_q\ge q$.
Therefore there is always at least one family of non-intersecting
lattice paths in (2.3).

(4) It is an implication of (2) and (3) that 
the order in which starting and end points are connected by
the non-inter\-sect\-ing paths is always the same, i.e., for fixed
$\bold i$ and $\bold j$, the permutation $\sigma$ in (2.3) is 
uniquely determined.
\endremark



\subhead 3. Proof of Theorem~1 plus a generalization\endsubhead
Theorem~1 follows from Claim~1 below. However, the actual goal of this
section is to prove a more general assertion, given in Claim~2, which
implies Claim~1 (and, thus, Theorem~1). The purpose and full impact of
this more general assertion will become clear in Section~4, where it
will be used to prove the compact formula for the
Hilbert series of the tangent cone to a Schubert variety 
in a Gra\3mannian given in Theorem~2. 
The proof of Claim~2 will be
accomplished by proving a technical assertion given in Claim~3 which
implies Claim~2.

In a Bourbaki-style exposition, one would (probably) start with the
statement of (the totally unmotivated) Claim~3, prove it, then derive
Claim~2 as a corollary, and finally derive Claim~1 as a corollary of
Claim~2. It is perhaps beneficial for the reader to proceed in the
reverse order, that is, to begin with the statement of Claim~1, then
explain Claim~2 and show that it does indeed imply Claim~1, then
explain Claim~3 and show that it does indeed imply Claim~2, and
finally give a proof of Claim~3, because that way the reader is
gradually moved from the point of departure (Theorem~1) to higher
levels of generality and technicality.

From now on, we shall always tacitly assume fixed
$w$ and $\tau$, $w\ge \tau$, or, equivalently, fixed $\bold i$ and $\bold
j$, $\bold i\ge \bold j$.
We will prove that the multiplicity formulas in Theorem~1 and (2.3)
are equivalent, by showing that the set of reflections in (2.2) and
the families of non-intersecting lattice paths in (2.3) are
essentially the same objects. 

For convenience, let us abbreviate
the set of families of non-intersecting lattice paths in (2.3) by the
symbol $\nipaths$. Clearly, a family of non-intersecting lattice paths
is uniquely determined by the set of all lattice points which lie on
its paths. A family $\bold P\in\nipaths$, however, is already uniquely
determined by the set of all lattice points which lie on its paths
{\it with $y$-coordinate} $>d$ since the starting points of the paths of any
family in $\nipaths$ are always $(d+1-\ell,d)$,
$\ell=1,2,\dots,d$. Let $\points(\bold P)$
denote this set of all lattice points
which lie on the paths of $\bold P$ and the $y$-coordinates of which are
greater than $d$. For example, $\points(\bold P_0)$, where $\bold P_0$
is the family of paths in Figure~1, is
$$\{(1,10),(1,11),(1,12),(1,13),\break(2,13),(2,14),\dots,
(9,21),(2,10),\dots,(3,12),\dots\}.\tag3.1$$

The precise formulation of the claim that the sets of reflections in
(2.2) and the families of non-intersecting lattice paths in (2.3) are
essentially the same objects is given in the following claim. There,
and for the rest of the paper, we identify a reflection $s=(x,y)$ with
the point $(x,y)$ in the plane.

\proclaim{Claim 1}
We have
$$\{S:S\subseteq[1,d]\times[d+1,n]\text{ and }
S\text{ satisfies {\rm(S1)} and {\rm(S2)}}\}=\points(\nipaths),$$
where, as usual, 
$$\points(\nipaths)=\{\points(\bold P):\bold P\in\nipaths\}.$$
\endproclaim

It is immediate that Claim~1 implies Theorem~1.

In order to illustrate Claim~1, we return to our example in Figure~1: 
the set of lattice points on the paths with $y$-coordinate $>9$,
i.e., the set (3.1) is a set of reflections with
the properties (S1) and (S2).

\medskip
As we said at the beginning of this section,
rather than giving a direct proof of Claim~1, we shall 
next explain a more general claim (Claim~2 below), 
which is the actual main result of
this paper, generalizing Claim~1 to
{\it multisets}. (Recall that a multiset is a set where one allows
repetitions of elements.) In order to be
able to formulate this more general claim, 
we have to explain the {\it``light-and-shadow
procedure with the sun in the south-east"} (an idea due
to Viennot \cite{\VienAA, \DeViAA}).
We will do this by considering an example.

\midinsert
\vskip8pt
\vbox{
$$
\Gitter(10,22)(0,0)
%\Koordinatenachsen(-9,10)(0,0)
\PfadDicke{.5pt}
\Pfad(0,-1),2222222222222222222222\endPfad
\Pfad(-1,0),11111111111\endPfad
\DickPunkt(2,13)
\DickPunkt(4,16)
\DickPunkt(5,18)
\DickPunkt(3,11)
\DickPunkt(6,17)
\DickPunkt(7,19)
\DickPunkt(4,10)
\DickPunkt(7,11)
\DickPunkt(9,13)
\DickPunkt(6,18)
\DickPunkt(8,21)
\DickPunkt(3,10)
\DickPunkt(7,16)
\DickPunkt(9,18)
\Label\o{\eightpoint\ssize (2)}(3,11)
\Label\o{\eightpoint\ssize (4)}(8,21)
\Label\o{\eightpoint\ssize (3)}(5,18)
\Label\o{\eightpoint\ssize (3)}(3,10)
\Label\o{\eightpoint\ssize (2)}(7,16)
\hbox{\hskip7cm}
\Gitter(10,22)(0,0)
%\Koordinatenachsen(-9,10)(0,0)
\PfadDicke{.5pt}
\Pfad(0,-1),2222222222222222222222\endPfad
\Pfad(-1,0),11111111111\endPfad
\PfadDicke{1.2pt}
\Pfad(1,9),22221222112212221111\endPfad
\Pfad(2,9),2212\endPfad
\Pfad(3,9),2\endPfad
\Pfad(4,9),222\endPfad
\Pfad(5,9),222222221221211\endPfad
\Pfad(6,9),22222221\endPfad
\Pfad(7,9),222222\endPfad
\Pfad(8,9),22222222212\endPfad
\Pfad(9,9),22222222\endPfad
%\SPfad(-1,9),11111111111\endSPfad
%\SPfad(1,10),112212221112211\endSPfad
\Kreis(1,9)
\Kreis(2,9)
\Kreis(3,9)
\Kreis(4,9)
\Kreis(5,9)
\Kreis(6,9)
\Kreis(7,9)
\Kreis(8,9)
\Kreis(9,9)
\Kreis(3,10)
\Kreis(3,12)
\Kreis(4,12)
\Kreis(7,15)
\Kreis(7,16)
\Kreis(9,17)
\Kreis(9,19)
\Kreis(9,20)
\Kreis(9,21)
\DickPunkt(2,13)
\DickPunkt(4,16)
\DickPunkt(5,18)
\DickPunkt(3,11)
\DickPunkt(6,17)
\DickPunkt(7,19)
\DickPunkt(4,10)
\DickPunkt(7,11)
\DickPunkt(9,13)
\DickPunkt(6,18)
\DickPunkt(8,21)
\DickPunkt(3,10)
\DickPunkt(7,16)
\DickPunkt(9,18)
\Label\lo{\eightpoint\ssize (2)}(3,11)
\Label\o{\eightpoint\ssize (4)}(8,21)
\Label\lo{\eightpoint\ssize (3)}(5,18)
\Label\o{\eightpoint\ssize (3)}(3,10)
\Label\o{\eightpoint\ssize (2)}(7,16)
\Label\u{A_9}(1,9)
\Label\u{A_8}(2,9)
\Label\u{A_7}(3,9)
\Label\u{A_6}(4,9)
\Label\u{A_5}(5,9)
\Label\u{A_4}(6,9)
\Label\u{A_3}(7,9)
\Label\u{A_2}(8,9)
\Label\u{A_1}(9,9)
\Label\l{E_1}(3,10)
\Label\o{E_2}(3,12)
\Label\o{E_3}(4,12)
\Label\r{E_4}(7,15)
\Label\r{E_5}(7,16)
\Label\r{E_6}(9,17)
\Label\r{E_7}(9,19)
\Label\r{E_8}(9,20)
\Label\r{E_9}(9,21)
\hskip4.5cm
$$
\centerline{\eightpoint a. A multiset of points
\kern4cm
b. Light-and-shadow}
\centerline{\eightpoint Figure 2}
}
\vskip8pt
\endinsert

Suppose that we are given a multiset $S$ of reflections contained
in $[1,d]\times[d+1,n]$. For example, Figure~2.a
shows the multiset of reflections (identified with points in the plane)
$$\multline 
\{(2,13), (3,10), (3,10), (3,10), (3,11), (3,11), (4,10), (4,16), \\
(5,18), (5,18), (5,18), 
(6,17), (6,18), (7,11), (7,16), (7,16), \\
(7,19), (8,21), (8,21), (8,21), (8,21), (9,13), (9,18) \}.
\endmultline$$
(In that example, we have chosen $d=9$ and for $n$ a value $\ge21$.)

Next we suppose that there is a light source being located in the
bottom-right corner. The {\it shadow} of a point
$(x,y)$ is defined to be the set of points $(x',y')\in\Bbb R^2$ ($\Bbb
R$
denoting the set of real numbers) with $x'\le x$ and $y'\ge y$. 
We consider the (bottom-right) {\it border} of the union of
the shadows of all the points of the multiset $S$. 
We also include the shadows of the starting points $A_\ell=(d+1-\ell,d)$ and
the end points $E_\ell=(d-\kappa_\ell,\kappa_\ell+i_\ell)$,
$\ell=1,2,\dots,d$. This border is a
lattice path. We restrict our attention to the portion of this lattice
path between $A_1$ and $E_{\sigma(1)}$. (Here, as before, $\sigma$ is the
permutation as in (2.3) which describes how starting and end points are
connected in the case of non-intersecting lattice paths, see
Remark~(4) after Theorem~1.
In our example in Figure~2,
$A_1$ and $E_{\sigma(1)}$ are the points $(9,9)$ and $(9,17)$, respectively.)
We remove all the points of the 
multiset that lie on this path, including $A_1$ and $E_{\sigma(1)}$. 
(In our example, we would remove $(9,9)$, $(9,13)$ and $(9,17)$.)
Then the
light-and-shadow procedure is repeated with the remaining
points. (That is, in the next step the roles of $A_1$ and
$E_{\sigma(1)}$ are played by $A_2$ and $E_{\sigma(2)}$, respectively,
etc.) 
We stop after a total of $d$ iterations. (The result of applying this
procedure to the multiset in Figure~2.a is shown in Figure~2.b.)
It is obvious that at this point we will have obtained $d$
non-intersecting lattice paths, the $\ell$-th path connecting $A_\ell$
and $E_{\sigma(\ell)}$, and the family of these paths will be an
element of $\nipaths$. We denote this family by $\lightshadow(S)$. 
There may however be left-over points, that
is, there may be points of the multiset $S$ which do not lie on any of
the $d$ paths from $\lightshadow(S)$.

Before we are able to state Claim~2, we need to introduce some more notation. Let
$\Rmsets(Q)$ denote the set of all multisets of reflections $(x,y)$
contained in $[1,d]\times[d+1,n]$ which have the property $Q$. For
example, Claim~2 will make an assertion about $\Rmsets(\text{S1})$, the set
of all multisets of reflections $(x,y)$
contained in $[1,d]\times[d+1,n]$ which have the property
(S1). Furthermore, we let
$\Mpoints(\nipaths)$ be the set of all multisets of lattice points
which lie on some path family from $\nipaths$.

We are now ready to state:
\proclaim{Claim 2}
We have
$$\Rmsets(\text{\rm S1})=\Mpoints(\nipaths).$$
Furthermore, for any multiset $S$ from $\Rmsets(\text{\rm S1})$, 
$\lightshadow(S)$ is an element of $\nipaths$, and it covers all the
points of $S$. 
\endproclaim

Let us for a moment assume that Claim~2 were already proved
and show that it does indeed imply Claim~1: 
suppose that we are given a set (sic!)
$S$ of reflections contained in $[1,d]\times[d+1,n]$ 
with properties (S1) and (S2). Then the second
assertion of Claim~2 says that this set of points lies on
$\lightshadow(S)$, the latter being a path
family from $\nipaths$. If $S$ were not
the complete set of lattice points on the paths with $y$-coordinate
$>d$, then we may add such a missing point, $(x,y)$ say, to $S$. The
first assertion of Claim~2 then says that $S\cup\{(x,y)\}$ is a set
of reflections satisfying (S1). Thus $S$ was not maximal, a
contradiction.
On the other hand, if we are given a path family $\bold P$ from $\nipaths$
and consider the set of points $\points(\bold P)$, 
then the first assertion of Claim~2 says that
this is a set of reflections satisfying (S1). In addition, it is 
maximal with respect to (S1). For suppose that it is not. Then we may
add another reflection, $(x,y)$ say, to $\points(\bold P)$, 
thus obtaining $S'=\points(\bold P)\cup
\{(x,y)\}$. Clearly, $\lightshadow(S')$ cannot cover all the points from $S'$.
However, this is a contradiction to the second assertion of
Claim~2.

\smallskip
A direct proof of Claim~2 seems difficult. We shall accomplish the
proof by introducing a further set of multisets, defined by a
technical condition which we shall refer to as the {\it chain
condition} and abbreviate as (CC). The previously announced Claim~3
will then connect these new multisets to the ones in Claim~2.

Let us call a set $\{(x_1,y_1),(x_2,y_2),\dots,(x_t,y_t)\}$ of points
with $x_1<x_2<\dots<x_t$ and $y_1>y_2>\dots>y_t$ a {\it chain}. 
Furthermore, given a point $A=(a_1,a_2)$, let us define regions $R(A)$ by
$$R(A):=\{(x,y):x\le a_1,\ y>a_2\}.$$
(This is the region in the plane weakly to the left and strictly above
the point $A$.)
We say that {\it a multiset $S$ satisfies the chain condition} (CC) if,
for any $q$ with $1\le q\le d$,
the maximal number of points in a chain that can be chosen from $S$
such that all of them are located inside $R(E_q)$
is at most $d-\kappa_q-q$. Here, as before, $E_q=(d-\kappa_q,\kappa_q+i_q)$.


\proclaim{Claim 3}
We have
$$\Rmsets(\text{\rm S1})=\Rmsets(\text{\rm CC})$$
and
$$\Mpoints(\nipaths)=\Rmsets(\text{\rm CC}).$$
\endproclaim

Before we turn to the proof of Claim~3, let us verify that it does
indeed imply Claim~2: the first assertion of Claim~2 is obvious
assuming the truth of Claim~3. Let us now suppose that the second
assertion of Claim~2 does not hold for the multiset $S\in\Rmsets(\text{S1})$. 
Since, by construction, $\lightshadow(S)$ is an element of $\nipaths$,
this means that $\lightshadow(S)$ does not cover all the
points of $S$. Let $Z_0\in S$ be such a point which is not covered by 
$\lightshadow(S)$. This point must necessarily lie to the left and above 
of the paths from $\lightshadow(S)$, see Figure~3 for a sketch of a typical
situation. (The labels $Z_1,Z_2,Z_3,E_q$ should be ignored at the moment.) 
We shall show that $S$ does not
satisfy the chain condition, thus obtaining a contradiction to the
first equality in Claim~3.

\midinsert
\vskip8pt
\vbox{
$$
\Gitter(10,12)(0,0)
\Pfad(1,7),11212\endPfad
\Pfad(1,6),11111222\endPfad
\Pfad(1,3),1112111222122\endPfad
\Pfad(6,1),221\endPfad
\Pfad(8,1),2222\endPfad
\Pfad(9,1),22222222\endPfad
\SPfad(6,0),2\endSPfad
\SPfad(8,0),2\endSPfad
\SPfad(9,0),2\endSPfad
\SPfad(4,9),2\endSPfad
\SPfad(6,9),2\endSPfad
\SPfad(8,9),2\endSPfad
\SPfad(9,9),2\endSPfad
\SPfad(0,3),1\endSPfad
\SPfad(0,6),1\endSPfad
\SPfad(0,7),1\endSPfad
\DickPunkt(1,9)
\DickPunkt(3,7)
\DickPunkt(6,6)
\DickPunkt(7,4)
\DickPunkt(7,3)
\Kreis(8,5)
\Label\r{Z_0}(1,9)
\Label\r{Z_1}(3,7)
\Label\u{Z_2}(6,6)
\Label\r{Z_3}(7,4)
\Label\u{E_q}(7,3)
\hskip4.5cm
$$
\centerline{\eightpoint Figure 3}
}
\vskip8pt
\endinsert

The idea is to construct,
in the region strictly to the right and
strictly below of $Z_0$, a sequence of {\it east-north turns}
of the paths of $\lightshadow(S)$. Here, an east-north turn
({\it EN-turn\/} for short) is a point in a lattice path which 
is the end point of a horizontal
step and at the same time the starting point of a vertical step.
For example, the EN-turns of the left-most lattice path in
Figure~1 are $(2,13)$, $(4,16)$ and $(5,18)$.
This sequence is constructed in the following way
(see Figure~3): let $Z_1$ be an
EN-turn of a path of $\lightshadow(S)$ such that the straight segment
connecting $Z_0$ and $Z_1$ does not cross any other path. If a $Z_1$
is found, the construction is iterated, that is, in the region
strictly to the right and strictly below of $Z_1$, we look for
an EN-turn $Z_2$ of a path of $\lightshadow(S)$ such that the straight segment
connecting $Z_1$ and $Z_2$ does not cross any other path. If, at some
stage, we should not be able to find an EN-turn strictly 
to the right and strictly below of $Z_k$, then the location of the
starting and end points of the paths guarantees that in the region
weakly to the right and strictly below of $Z_k$ we find an end point
$E_q$. Thus, we have found in fact a chain 
$Z_0>Z_1>\dots>Z_k$ in $R(E_q)$. Now we observe that, for any path
family $\bold P$ from $\nipaths$, the number of lattice paths in
$\bold P$ that start strictly to the left of $E_q$ and
pass strictly above $E_q$
(thus, terminating weakly to the right of $E_q$; cf\. Figure~1) is
exactly $d-\ka_q-q$. This observation follows, for example, 
by a reverse induction on $q$. Thus, $k=d-\ka_q-q$, and, since by
definition of $\lightshadow(S)$ {\it any} EN-turn is an element of $S$,
all the points $Z_0,Z_1,\dots,Z_k$ are elements of $S$. This means that we have
found a chain of $k+1=d-\ka_q-q+1$ elements of $S$ contained in $R(E_q)$,
and consequently $S$ does not satisfy the chain condition. This is
the desired contradiction to the first equality in Claim~3.
Thus, Claim~3 does indeed imply Claim~2.

\medskip

We finally prove Claim~3 (and, thus, Claims~2 and 1, and Theorem~1).
\demo{Proof of Claim 3}
We prove both equalities by showing, first, that
the left-hand side is included in
the right-hand side, and then that the right-hand side is included in
the left-hand side. Thus, we have to prove four assertions, which we
label A1--A4. Below, for all the multisets considered, we shall always
tacitly assume that they are contained in $[1,d]\times[d+1,n]$.

\smallskip
A1. $\Mpoints(\nipaths)\subseteq\Rmsets(\text{CC})$. 
This is obvious from the above observation that,
for any path family $\bold P$ from $\nipaths$, $d-\kappa_q-q$ is the
number of lattice paths in $\bold P$ that start strictly to the left
of $E_q$ and pass strictly above $E_q$.

\smallskip
A2. $\Mpoints(\nipaths)\supseteq\Rmsets(\text{CC})$. 
Given a multiset $S\in\Rmsets(\text{CC})$, our goal is to show that all
the points of $S$ lie on $\lightshadow(S)$, the latter being an
element of $\nipaths$. This is more or
less ``obvious.'' The only matter is notation. Probably the most
convenient way to prove this rigorously is by induction on $d$. 

\midinsert
\vskip8pt
\vbox{
$$
\Gitter(10,22)(0,0)
%\Koordinatenachsen(-9,10)(0,0)
\PfadDicke{.5pt}
\Pfad(0,-1),2222222222222222222222\endPfad
\Pfad(-1,0),11111111111\endPfad
\PfadDicke{1.2pt}
\Pfad(8,21),1\endPfad
\Pfad(8,20),1\endPfad
\Pfad(8,18),12\endPfad
\Pfad(9,9),22222222\endPfad
%\SPfad(-1,9),11111111111\endSPfad
%\SPfad(1,10),112212221112211\endSPfad
\Kreis(1,9)
\Kreis(2,9)
\Kreis(3,9)
\Kreis(4,9)
\Kreis(5,9)
\Kreis(6,9)
\Kreis(7,9)
\Kreis(8,9)
\Kreis(9,9)
\Kreis(3,10)
\Kreis(3,12)
\Kreis(4,12)
\Kreis(7,15)
\Kreis(7,16)
\Kreis(9,17)
\Kreis(9,19)
\Kreis(9,20)
\Kreis(9,21)
\DickPunkt(2,13)
\DickPunkt(4,16)
\DickPunkt(5,18)
\DickPunkt(3,11)
\DickPunkt(6,17)
\DickPunkt(7,19)
\DickPunkt(4,10)
\DickPunkt(7,11)
\DickPunkt(9,13)
\DickPunkt(6,18)
\DickPunkt(8,21)
\DickPunkt(3,10)
\DickPunkt(7,16)
\DickPunkt(9,18)
\Label\lo{\eightpoint\ssize (2)}(3,11)
\Label\o{\eightpoint\ssize (4)}(8,21)
\Label\lo{\eightpoint\ssize (3)}(5,18)
\Label\o{\eightpoint\ssize (3)}(3,10)
\Label\o{\eightpoint\ssize (2)}(7,16)
\Label\u{A_9}(1,9)
\Label\u{A_8}(2,9)
\Label\u{A_7}(3,9)
\Label\u{A_6}(4,9)
\Label\u{A_5}(5,9)
\Label\u{A_4}(6,9)
\Label\u{A_3}(7,9)
\Label\u{A_2}(8,9)
\Label\u{A_1}(9,9)
\Label\l{E_1}(3,10)
\Label\o{E_2}(3,12)
\Label\o{E_3}(4,12)
\Label\r{E_4}(7,15)
\Label\r{E_5}(7,16)
\Label\r{E_6}(9,17)
\Label\r{E_7}(9,19)
\Label\r{E_8}(9,20)
\Label\r{E_9}(9,21)
\Label\l{E'_7}(8,18)
\Label\l{E'_8}(8,20)
\Label\l{E'_9}(8,21)
\hskip4.5cm
$$
\centerline{\eightpoint Figure 4}
}
\vskip8pt
\endinsert

For $d=1$ the assertion is obvious (the quantity $d-\kappa_q-q$ being 0 for
$d=q=1$). Let us now assume that we have
already proved the assertion for $d-1$. We want to show that this implies 
the truth of the assertion for $d$. Given $\bold
i=(i_1,i_2,\dots,i_{d})$ and $\bold j=(j_1,j_2,\dots,j_{d})$ and
a multiset $S$ of lattice points satisfying the chain condition, we
apply the light-and-shadow procedure. We restrict our attention to
the right-most strip of the picture, i.e., the region of points with
$x$-coordinate between $d-1$ and $d$, see Figure~4. There, we have
chosen $d=9$, $\bold i=(4,6,7,13,14,17,19,20,21)$
and $\bold j=(1,2,4,7,10,12,13,15,16)$. The starting and end points
determined by $\bold i$ and $\bold j$ are indicated by circles. The
multiset of points is indicated by bold dots, multiplicities being
indicated by the numbers in parentheses. (This is in fact the same
example as in Figure~2. The path pieces should be ignored for the
moment.)

Let $k$ be minimal such that $i_k\ge j_{d}$. (In our example we have
$k=6$.) Then the end points with
$x$-coordinate $d$ are $E_k,E_{k+1},\dots,E_{d}$. Clearly, under
light-and-shadow, $E_k$ is connected with $A_1$. The path portions
leading to the other end points $E_{k+1},\dots,E_{d}$ hit the
vertical line $x=d-1$ the last time in the points
$E'_{k+1},\dots,E'_{d}$, say (see Figure~4). Using the chain
condition for $E_k,E_{k+1},\dots E_d$,
it is easy to see that for any $q$ with $k+1\le q\le d$
the maximal number of points that can be chosen from $S$
such that they form a chain and all of them are located inside $R(E'_q)$
is at most $d-q$. Now, instead of $\bold i$ and $\bold j$, 
we consider
$\bold i'=(i_1,\dots,i_{k-1},i'_{k+1}-1,\dots,\break i'_{d}-1)$ and $\bold
j'=(j_1,j_2,\dots,j_{d-1})$, 
where $i'_{\ell}$ denotes the $y$-coordinate of $E'_{\ell}$,\linebreak
$\ell=k+1,\dots,d$. 
It should be observed that, up to a vertical shift of 1 unit, 
the starting points determined by $\bold i'$
and $\bold j'$ are $A_2,A_3,\dots,A_{d}$, whereas the corresponding
end points are $E_1,\dots,E_{k-1},E'_{k+1},\dots,E'_{d}$. By the
above consideration, the multiset $S$ satisfies the chain condition with
respect to these new starting and end points. Thus, we may apply the
induction hypothesis, which says that light-and-shadow yields a
family of paths connecting the (new) starting points with the (new) end
points, thereby covering all elements of $S$ with $x$-coordinate
at most $d-1$. This family
of paths is finally concatenated with the path portions that we
already obtained in the strip between the vertical lines $x=d-1$ and
$x=d$. Thus we have found a path family from $\nipaths$ that covers
all the points of $S$. 

\smallskip
A3. $\Rmsets(\text{S1})\subseteq\Rmsets(\text{CC})$. 
Suppose we are given a multiset of reflections which satisfies (S1)
but does not satisfy the chain condition. 
Then for some $q$ there is a chain of $d-\kappa_q-q+1$ reflections 
from the multiset which are all located inside $R(E_q)$. 

Let the reflections in the chain be $s_1,s_2,\dots,s_{d-\kappa_q-q+1}$,
and consider a reflection in the chain, $(x,y)$ say. 
Since $(x,y)\in R(E_q)$ we have $x\le d-\kappa_q$. Furthermore, we have 
$$(\tau s_1\cdots s_{d-\kappa_q-q+1})(x)=\tau(y),$$
where as before $\tau$ is identified with $\bold j$, i.e., 
$\tau=j_1j_2\dots j_n$ with $j_1<j_2<\dots<j_d$ and
$j_{d+1}<\dots<j_{n-1}<j_n$.
Since $(x,y)$ is contained in $R(E_q)$ we have $y>\kappa_q+i_q\ge d$.
Because of $j_{d+1}<\dots<j_{n-1}<j_n$, this implies $\tau(y)\ge
\tau(\kappa_q+i_q+1)$. 

We claim that $\tau(\kappa_q+i_q+1)=i_q+1$. This is seen as follows. 
Taking into account the trivial fact that the set of values
$\{j_{d+1},j_{d+2},\dots,j_{n}\}$ is equal to the complement of
$\{j_{1},j_{2},\dots,j_{d}\}$ in $\{1,2,\dots,n\}$, a
value $\tau(y)=j_y$ for $y>d$ is {\it characterized\/} by
$$j_y=(y-d)+\vert\{\ell:1\le \ell\le d\text{ and }j_{\ell}<j_{y}\}\vert.$$
Thus we may verify our claim by setting $y=\kappa_q+i_q+1$ and substituting
$i_q+1$ for $j_{\kappa_q+i_q+1}$ in this equation. Indeed, we have
$i_q+1=(\kappa_q+i_q+1-d)+(d-\kappa_q)$. Hence, we have $\tau(y)>i_q$.

In summary, we have found $d-\kappa_q-q+1$ values of $x$, $1\le x\le
d$, such that 
$$(\tau s_1\cdots s_{d-\kappa_q-q+1})(x)>i_q,\tag3.2$$
all of which are $\le d-\kappa_q$.
Moreover, if $d-\kappa_q<x\le d$, then we have 
$$(\tau s_1\cdots s_{d-\kappa_q-q+1})(x)=\tau(x)=j_x>i_q.$$
Hence, in total we found $(d-\kappa_q-q+1)+\kappa_q=d-q+1$ values
$x$ for which (3.2) holds. If we recall that we also always identify $w$
with $\bold i$, i.e., $w=i_1i_2\dots i_n$, then 
this is a contradiction to (S1).

\smallskip
A4. $\Rmsets(\text{S1})\supseteq\Rmsets(\text{CC})$. 
Let $S\in\Rmsets(\text{CC})$, and 
consider a chain of $t$ points of $S$, viewed as
reflections $s_1>s_2>\dots>s_t$.
Still identifying $w$ and $\bold i$, we observe that
the inequality $w\ge\tau s_1\cdots s_t$ is equivalent to the
inequality
$$\big\vert\{x:1\le x\le d\text{ and }(\tau s_1\cdots
s_t)(x)>i_q\}\big\vert \le d-q\tag3.3$$
to hold for $1\le q\le d$.

A careful examination of the arguments in A3 shows that they actually
prove 
$$\big\vert\{x:1\le x\le d\text{ and }(\tau s_1\cdots
s_t)(x)>i_q\}\big\vert =\big\vert\{\ell:s_\ell\in R(E_q)\}\big\vert +
\kappa_q.$$ 
By assumption, our multiset $S$ of points satisfies the chain condition,
hence $\big\vert\{\ell:s_\ell\in R(E_q)\}\big\vert \le
d-\kappa_q-q$. Clearly, this implies (3.3), as desired.
\qed
\enddemo



\subhead 4. A formula for the Hilbert series of the tangent cone at 
a point\endsubhead
Now the full significance of Claim~2 can be revealed. Briefly, it allows the
formulation of a version of Conjecture~1 in \cite{\KrLaAA}
which has the
advantage of being {\it efficient}, as it reduces the computation of the
Hilbert function of the tangent cone to $X(w)$ at a point $\tau$ 
to a {\it finite} problem. More precisely, we can express
the {\it Hilbert series} of the tangent cone 
in terms of a generating function for the set $\nipaths$ of
non-intersecting lattice paths from the previous section (which is
obviously a finite set). This form of
the conjecture is the analogue of, say, formulas for the Hilbert
series as in \cite{\CoHeAA, Eq.~(1)}, \cite{\KrPrAA, p.~1021, line~11} 
or in \cite{\KrRuAA, Theorem~1}.

In order to formulate this equivalent form, we need to introduce some
further notation. We recall from the previous section that
a point in a lattice path $P$ which is the end point of a horizontal
step and at the same time the starting point of a vertical step is
called an EN-turn of the lattice path $P$. 
We write $\EN(P)$ for the number of
EN-turns of $P$. Also, given a family $\bold P=(P_1,P_2,\dots,P_d)$ of
paths $P_\ell$, we write $\EN(\bold P)$ for the number $\sum _{\ell=1}
^{d}\EN(P_\ell)$ of all EN-turns in the family.
Finally, given any weight function $\mu$ defined on a set $\Cal M$, by
the generating function $\GF(\Cal M;\mu)$ we mean $\sum _{x\in\Cal M}
^{}\mu(x)$.

\proclaim{Theorem 2} Conjecture~1 from \cite{\KrLaAA} 
is equivalent to saying that the
Hilbert series of the tangent cone to $X(w)$ at $\tau$ is equal to
$$\frac {\GF(\nipaths;z^{\EN(.)})}
{(1-z)^{\sum _{\ell=1} ^{d}i_\ell-\binom {d+1}2}},
\tag4.1$$
where, as before, $\nipaths$ is the set of all families 
$(P_1,P_2,\dots,P_d)$ of non-intersecting lattice paths, where the
path $P_\ell$ runs from $(d+1-\ell,d)$ to
$(d-\kappa_\ell,\kappa_\ell+i_\ell)$,
$\ell=1,2,\dots,d$.
\endproclaim

\demo{Proof} We can simply copy the corresponding proof in
\cite{\KrPrAA, first proof of Theorem~2}.

According to Conjecture~1 from \cite{\KrLaAA}, the dimension  
of the $m$-th homogeneous component of the tangent cone is equal to
the number of $m$-element multisets from $\Rmsets(S1)$, that is,
to the number of multisets of cardinality $m$ which are 
contained in $[1,d]\times[d+1,n]$ and satisfy (S1).
Following \cite{\KrLaAA} we denote this dimension by $h_{TC_\tau
X(w)}(m)$.

Let $S$ be an $m$-element multiset from $\Rmsets(S1)$. 
We apply the light-and-shadow procedure
from Section~3 to it. By
Claim~2, we obtain a path family $(P_1,P_2,\dots,P_d)$ from $\nipaths$.
Each path $P_\ell$ contains a few (possibly multiple) points of $S$.
However, at each EN-turn of $P_\ell$ there has to be {\it at least
one\/} element of $S$, $\ell=1,2,\dots,d$. 
Therefore, 
given such a path family $(P_1,P_2,\dots,P_d)$ from $\nipaths$ 
with a total number of
exactly $t$ EN-turns, there are exactly $\binom{T+m-t-1}{m-t}$
multisets $S$ of cardinality $m$ that reduce to
$(P_1,P_2,\dots,P_d)$ under light-and-shadow, where 
$$T=\sum _{\ell=1} ^{d}((d-\kappa_\ell)+(\kappa_\ell+i_\ell))-
\sum _{\ell=1} ^{d}((d+1-\ell)+d)=
\sum _{\ell=1} ^{d}i_\ell-\binom {d+1}2$$
is the total number of lattice points with $y$-coordinate $>d$ 
on the lattice paths
$P_1,P_2,\dots,P_d$. ($T$ is independent of the path family.)
Because of the first assertion of Claim~2, all of these 
multisets satisfy (S1).

Hence, if we let $h_t$ denote the number of all path
families in $\nipaths$ with a total number of
exactly $t$ EN-turns, we obtain for the Hilbert series,
$$\align \sum _{m=0} ^{\infty}h_{TC_\tau X(w)}(m)\, z^m&=
\sum _{m=0} ^{\infty}\bigg(\sum _{t=0}
^{m}\binom{T+m-t-1}{m-t}h_t\bigg)z^m\\
&=\sum _{t=0} ^{\infty}h_t\sum _{m=t}
^{\infty}\binom{T+m-t-1}{m-t}z^m\\
&=\sum _{t=0} ^{\infty}h_tz^t\sum _{m=0}
^{\infty}\binom{T+m-1}{m}z^m\\
&=\frac {\sum _{t=0} ^{\infty}h_tz^t} {(1-z)^T}.
\endalign$$
The generating function $\sum _{t=0} ^{\infty}h_tz^t$ is exactly
the numerator in (4.1).
This proves the theorem.\quad \quad \qed
\enddemo


\remark{Remarks} (1) Formula (4.1) implies the
Rosenthal--Zelevinsky formula. For, the multiplicity $\mult_\tau X(w)$ 
is equal to the {\it numerator} of the 
Hilbert series of the tangent cone to $X(w)$ at $\tau$, 
{\it evaluated at $z=1$}. But, by (4.1), this is
exactly the {\it number} of all families of non-intersecting lattice
paths in $\nipaths$, i.e., of all path families as
described in (2.3). As we already remarked earlier, the combinatorial
interpretation (2.3) of the multiplicity in terms of the non-intersecting
lattice paths from $\nipaths$ is equivalent to the
Rosenthal--Zelevinsky formula.

(2)  Unfortunately, all the results that
have been found so far on the enumeration of non-intersecting lattice
paths with respect to turns (see \cite{\KratBE, \KrPrAA, \KrRuAA,
\KulkAC, \ModaAA}) 
do not cover the above case, because the
location of the starting and end points is quite unusual. This means
that, up to now, there is no compact formula (a determinant, or
whatever) for $\nipaths$.
\endremark


\remark{Acknowledgement} I am indebted to an anonymous referee for
an extremely careful reading of the manuscript, and for 
numerous helpful remarks.
\endremark

{
\eightpoint
\subhead Note\endsubhead
After the first version of this paper was distributed,
Vijay Kodiyalam and K.~N.~Raghavan proved Conjecture~1 from \cite{\KrLaAA}
in ``Hilbert functions of points on Schubert varieties in Grassmannians,"  
{\it J. Algebra} {\bf 270}  (2003), 28--54. Thus, our Theorem~2 becomes
an unconditional theorem, that is to say, the Hilbert series of the
tangent cone to $X(w)$ at $\tau$ is indeed given by (4.1).

}

\Refs

\ref\no \BiLaAA\by S. C. Billey and V. Lakshmibai \yr 2000 \book Singular 
loci of Schubert varieties\publ Birkh\"auser\publaddr Boston\endref

\ref\no \CoHeAA\by A.    Conca and J. Herzog \yr 1994 \paper On the
Hilbert function of determinantal rings and their canonical module
\jour Proc\. Amer\. Math\. Soc\. \vol 122 \pages 677--681\endref 

\ref\no\DeViAA \by M. Desainte--Catherine, X. Viennot\paper Enumeration
of certain Young tableaux with bounded height\inbook Combinatoire
\'enum\'erative\publ 
G.~Labelle, P.~Leroux, Eds.\publaddr Springer--Verlag, Berlin,
Heidelberg, New York\yr 1986\pages 58--67\endref

\ref\no \FultAC\by W.    Fulton \yr 1997 \book Young tableaux\publ 
Cambridge University Press\publaddr Cambridge\endref

\ref\no \GeViAB\by I. M. Gessel and X. Viennot \yr 1989 
\paper Determinants, paths, and plane partitions 
\paperinfo preprint, 1989\finalinfo available at 
{\tt http://www.cs.brandeis.edu/\~{}ira}\endref

\ref\no \KratBE\by C.    Krattenthaler \yr 1995 \paper 
Counting nonintersecting lattice paths with turns\jour 
S\'eminaire Lotharingien Combin\.\vol 34\pages paper B34i, 17~pp\endref

\ref\no \KratBQ\by C.    Krattenthaler \yr 2001 
\paper On multiplicities of points on Schubert varieties in Grassmannians
\jour S\'eminaire Lotharingien Combin\.\vol 45
\pages Article~B45c\endref

\ref\no \KrPrAA\by C.    Krattenthaler and M. Prohaska \yr 1999 \paper 
A remarkable formula for counting nonintersecting lattice paths in a 
ladder with respect to turns\jour Trans\. Amer\. Math\. Soc\. 
\vol 351\pages 1015--1042\endref

\ref\no \KrRuAA\by C.    Krattenthaler and M. Rubey \yr 2004\paper 
A determinantal formula for the Hilbert series of one-sided 
ladder determinantal rings\inbook Algebra, Arithmetic and Geometry 
with Applications\eds C.~Christensen, G.~Sundaram, A.~Sathaye and C.~Bajaj
\publ Springer-Verlag\publaddr New York\pages 525--552\endref

\ref\no \KrLaAA\by V. Kreiman and V. Lakshmibai\yr 2004\paper 
Multiplicities of singular points in Schubert varieties
of Grassmannians\inbook Algebra, Arithmetic and Geometry 
with Applications\eds C.~Christensen, G.~Sundaram, A.~Sathaye and C.~Bajaj
\publ Springer-Verlag\publaddr New York\pages 553--563\endref

\ref\no \KulkAC\by D. M. Kulkarni \yr 1996 \paper Counting of paths and 
coefficients of Hilbert polynomial of a determinantal ideal\jour 
Discrete Math\.\vol 154\pages 141--151\endref

\ref\no \LindAA\by B.    Lindstr\"om \yr 1973 
\paper On the vector representations of induced matroids
\jour Bull\. London Math\. Soc\.\vol 5
\pages 85--90\endref

\ref\no \ModaAA\by M. R. Modak \yr 1992 \paper Combinatorial meaning of 
the coefficients of a Hilbert polynomial\jour 
Proc\. Indian Acad\. Sci\. (Math\. Sci\.)\vol 102\pages 93--123\endref

\ref\no \RoZeAA\by J.    Rosenthal and A. Zelevinsky \yr 2001 
\paper Multiplicities of points on Schubert varieties in Grassmannians
\jour J. Algebraic Combin\.\vol 13
\pages 213--218\endref

\ref\no\VienAA \by X. Viennot\paper Une forme g\'eom\'etrique de la
correspondance de Robinson--Schensted\inbook Combinatoire et
Repr\'esentation du Groupe Sym\'etrique\publ 
D. Foata ed.\publaddr Lecture Notes in Math\., Vol.~579,
Springer--Verlag, New York\yr 1977\pages 29--58\endref

\endRefs
\enddocument

