On multiplicities of points on Schubert varieties in Graßmannians II

C. Krattenthaler^{†}*

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Ap.Univie.Ac.At

               WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We prove a conjecture by Kreiman and Lakshmibai on a combinatorial description of multiplicities of points on Schubert varieties in Graßmannians 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éminaire Lotharingien Combin. 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ßmannian assuming the truth of another conjecture of Kreiman and Lakshmibai.

1. Introduction. The 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 [14] gave a determinantal formula for the multiplicity of a point on a Schubert variety in a Graßmannian. It paved the way to a combinatorial understanding of this multiplicity. More precisely, it was shown in [7] 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 [10, 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ßmannian 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 [10, Conjecture 1]). While we are not able to prove this more general conjecture^{1}, 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 [2, Eq. (1)], [8, p. 1021, line 11] or [9, Theorem 1]).

2000 Mathematics Subject Classification. Primary 14M15; Secondary 05A15 05E15 14H20.

Key words and phrases. Schubert varieties, singularities, multiplicities, non-intersecting lattice paths, turns of paths.

†Partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”, and by the Austrian Science Foundation FWF, grant P13190-MAT.

*Current address: Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France; e-mail: kratt@euler.univ-lyon1.fr.

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 [10] on the Hilbert series of the tangent cone to a Schubert variety in a Graßmannian. 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).

2. Combinatorial interpretations of multiplicities of points on Schubert varieties in Graßmannians. We recall some basic notions from the Schubert calculus in the Graßmannian, and fix the notation that we are going to use. We refer the reader to [1, Sec. 3.1] and [4, Sec. 9.4] for in-depth introductions into the subject.

Let d and n be positive integers with 0 ≤ d ≤ n. The Graßmannian 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ßmannian Gr_{d}(V) are indexed by elements in S_{n}/(S_{d} × S_{n−d}), where S_{m} denotes the symmetric group of order m. Any coset C in S_{n}/(S_{d} × S_{n−d}) has a minimal representative, which is the unique permutation w = i_{1}i_{2} … i_{n} in C such that i_{1} < i_{2} < ⋯ < i_{d} and i_{d+1} < ⋯ < i_{n−1} < i_{n}. We will often identify such a minimal representative w with the vector i = (i_{1}, i_{2}, …, i_{d}) of its first d elements. The usual Ehresmann–Bruhat order on S_{n} induces an order on the cosets of S_{n}/(S_{d} ×S_{n−d}). Given two representatives w and τ, identified with i = (i_{1}, i_{2}, …, i_{d}) and j = (j_{1}, j_{2}, …, j_{d}), respectively, τ is less than or equal to w in this induced Ehresmann–Bruhat order if and only if j_{ℓ} ≤ i_{ℓ} for all ℓ = 1, 2, …, d. In that case, we write τ ≤ w, respectively j ≤ i.

Given a minimal representative w, we denote the corresponding Schubert variety in the Graßmannian Gr_{d}(V) by X(w). It is well-known that X(w) decomposes into the disjoint union of Schubert cells which are indexed by elements τ ∈ S_{n}/(S_{d} ×S_{n−d}) with τ ≤ w. The multiplicity of a point x in X(w) is constant on each Schubert cell. Following [10] we denote the multiplicity of a point x in the Schubert cell indexed by τ by mult_{τ} X(w). In slight abuse of terminology we will often call it the “multiplicity of the point τ on the Schubert variety X(w).”

1See, however, the Note at the end of this paper.

Let us now recall the multiplicity formula conjectured in [10]. We are given two minimal representatives w and τ of cosets in S_{n}/(S_{d} × S_{n−d}) with τ ≤ w. In Conjecture 2 of [10], sets S of reflections s = (x, y), 1 ≤ x ≤ d, d + 1 ≤ y ≤ n (here we use standard transposition notation), are considered with the property that

(S1) Any chain (in the Ehresmann-Bruhat order on S_{n}) s_{1} > s_{2} > ⋯ > s_{t} of commuting reflections, all of them contained in S, satifies w ≥ τs_{1} ⋯ s_{t} (in the induced Ehresmann–Bruhat order on S_{n}/(S_{d} × S_{n−d}));

(S2) S is maximal with respect to property (S1).

It should be noted that, if s_{i} = (x_{i}, y_{i}), 1 ≤ i ≤ t, then s_{1} > s_{2} > ⋯ > s_{t} is a chain of commuting reflections if and only if x_{1} < x_{2} < ⋯ < x_{t} and y_{1} > y_{2} > ⋯ > y_{t}.

For the future, since all the reflections which we consider in this paper will always be reflections (x, y) with 1 ≤ x ≤ d and d + 1 ≤ y ≤ n, let us abbreviate this set of reflections by [1, d] × [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 τ = 1352467, so that the corresponding i and j are i = (3, 5, 6) and j = (1, 3, 5). Then there are exactly two sets of reflections (contained in [1, d] × [d + 1, n] = [1, 3] × [4, 7]}) satisfying (S1) and (S2):

([1, 3] × [4, 6])\{(1, 6)} and ([1, 3] × [4, 6])\{(2, 5)}.  (2.1)

To see this, we first observe that a set of reflections satisfying (S1) cannot contain a reflection (x, 7), x ≤ 3. For, we have

(τ ∘ (x, 7))(x) = (( \begin{matrix}1 2 3 4 5 6 7 \\ 1 3 5 2 4 6 7 \end{matrix} ) ∘ (x, 7)) (x) = 7,

and therefore the minimal representative of τ ∘ (x, 7) in S_{n}/(S_{d} × S_{n−d}) is

r_{1}r_{2}7r_{4} … r_{7} ≰ 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

τ ∘ (1, 6) ∘ (2, 5) = ( \begin{matrix}1 2 3 4 5 6 7 \\ 1 3 5 2 4 6 7 \end{matrix} ) ∘ (1, 6) ∘ (2, 5) = ( \begin{matrix}1 2 3 4 5 6 7 \\ 6 4 5 2 3 1 7 \end{matrix} ) .

The minimal representative of this permutation in S_{n}/(S_{d} × S_{n−d}) is 4561237 ≰ 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).

Now we are in the position to formulate Conjecture 2 from [10], which becomes a theorem by our proof in Section 3.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • • • • • • • • • • • • •_{Figure 1}

Theorem 1. The multiplicity of the point τ on the Schubert variety X(w) is given by

mult_{τ} X(w) = |{S : S ⊆ [1, d] × [d + 1, n] and S satisfies (S1) and (S2)}|, (2.2)

where, as before, [1, d] × [d + 1, n] denotes the set of reflections (x, y) with 1 ≤ x ≤ d and d + 1 ≤ y ≤ n.

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

Next we recall the combinatorial interpretation of multiplicities in terms of nonintersecting lattice paths from [7], which is a more or less straight-forward combinatorial translation of the Rosenthal–Zelevinsky formula [14] using the Lindström– Gessel–Viennot theorem [12, Lemma 1], [5, Theorem 1]. As before, let w and τ be two minimal representatives of cosets from S_{n}/(S_{d} × S_{n−d}) with w ≥ τ, and identify them with i = (i_{1}, i_{2}, …, i_{d}), 1 ≤ i_{1} < i_{2} < ⋯ < i_{d} ≤ n, and j = (j_{1}, j_{2}, …, j_{d}), 1 ≤ j_{1} < j_{2} < ⋯ < j_{d} ≤ n, respectively. In particular, i ≥ j. Furthermore, we define the numbers κ_{q} := |{ℓ : i_{q} < j_{ℓ}}|. Then

mult_{τ} X(w) =#(families (P_{1}, P_{2}, …, P_{d}) of non-intersecting lattice paths,

where the path P_{ℓ} runs from (d + 1 − ℓ, d) to

(d − κ_{σ(ℓ)}, κ_{σ(ℓ)} + i_{σ(ℓ)}), ℓ = 1, 2, …, d, for some σ ∈ S_{d}).(2.3)

Here, by 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 nonintersecting if no two paths of the family have a common point. To given an example, let d = 9, i = (4, 6, 7, 13, 14, 17, 19, 20, 21) and j = (1, 2, 4, 7, 10, 12, 13, 15, 16). For this choice the vector of the κ_{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 i and j. The permutation σ is 674583129 in this example.

Remarks. At this point, there are several comments to be made, most of them recalling facts from [7]:

(1) In [7] the starting points of the paths are (−ℓ + 1, ℓ − 1) and the end points are (−κ_{ℓ}, κ_{ℓ} +i_{ℓ}), ℓ = 1, 2, …, d (the latter in some order, determined by the permutation σ). If we shift everything by d units to the right then we obtain the points (d + 1 − ℓ, ℓ − 1) and (d − κ_{ℓ}, κ_{ℓ} + i_{ℓ}). Whereas now the end points are in agreement, the starting points still differ slightly. However, the arguments in Section 4 of [7] (and, in fact, figures such as Figure 3 in [7]) 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 − ℓ, ℓ − 1) by the points (d + 1 − ℓ, d). (In fact, Figure 1 shows exactly the result when the forced portions of the paths in Figure 3 of [7] are cut off.)

(2) The sequence (κ_{q})_{1≤q≤d} is weakly monotone decreasing if q increases, while the sequence (κ_{q} + i_{q})_{1≤q≤d} is weakly monotone increasing if q increases. This implies that the end points (d−κ_{q}, κ_{q} +i_{q}), q = 1, 2, …, 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−κ_{q}, κ_{q}+i_{q}) is weakly to the left and weakly below the (q + 1)-st end point (d − κ_{q+1}, κ_{q+1} + i_{q+1}), q = 1, 2, …, d − 1. (See Figure 1.)

(3) We have κ_{q} ≥ d − i_{q}, or, equivalently, κ_{q} + i_{q} ≥ d. Thus, the end points are never below the starting points of the paths. Moreover, since i ≥ j, we have κ_{q} ≤ d − q, or, equivalently, d − κ_{q} ≥ 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-intersecting paths is always the same, i.e., for fixed i and j, the permutation σ in (2.3) is uniquely determined.

3. Proof of Theorem 1 plus a generalization. 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ßmannian 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 τ, w ≥ τ, or, equivalently, fixed i and j, i ≥ 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 𝔫𝔦𝔭𝔞𝔱𝔥𝔰. 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 P ∈ 𝔫𝔦𝔭𝔞𝔱𝔥𝔰, however, is already uniquely determined by the set of all lattice points which lie on its paths with y-coordinate > d since the starting points of the paths of any family in 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 are always (d + 1 − ℓ, d), ℓ = 1, 2, …, d. Let points(P) denote this set of all lattice points which lie on the paths of P and the y-coordinates of which are greater than d. For example, points(P_{0}), where P_{0} is the family of paths in Figure 1, is

{(1, 10), (1, 11), (1, 12), (1, 13), (2, 13), (2, 14), …, (9, 21), (2, 10), …, (3, 12), … }.

(3.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.

Claim 1. We have

{S : S ⊆ [1, d] × [d + 1, n] and S satisfies (S1) and (S2)} = points(𝔫𝔦𝔭𝔞𝔱𝔥𝔰),

where, as usual,

points(𝔫𝔦𝔭𝔞𝔱𝔥𝔰) = {points(P) : P ∈ 𝔫𝔦𝔭𝔞𝔱𝔥𝔰}.

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

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 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 “light-and-shadow procedure with the sun in the south-east” (an idea due to Viennot [15, 3]). We will do this by considering an example.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • •  • • •  • • • • •  • •^{(2)}  ^{(4)}^{(3)}^{(3)}  ^{(2)}  _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘  ∘ ∘ ∘ ∘ ∘ ∘ • • • •  • • •  • • • • •  • •^{(2)}  ^{(4)}^{(3)}^{(3)}  ^{(2)}^{A_{9}} ^{A_{8}} ^{A_{7}} ^{A_{6}} ^{A_{5}} ^{A_{4}} ^{A_{3}} ^{A_{2}} ^{A_{1}}^{E_{1}}^{E_{2}} ^{E_{3}}  ^{E_{4}}^{E_{5}}  ^{E_{6}}^{E_{7}}^{E_{8}}^{E_{9}}

a. A multiset of points b. Light-and-shadow Figure 2

Suppose that we are given a multiset S of reflections contained in [1, d] × [d + 1, n].

For example, Figure 2.a shows the multiset of reflections (identified with points in the plane)

{(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)}.

(In that example, we have chosen d = 9 and for n a value ≥ 21.)

Next we suppose that there is a light source being located in the bottom-right corner. The shadow of a point (x, y) is defined to be the set of points (x′, y′) ∈ ℝ^{2} (ℝ denoting the set of real numbers) with x′ ≤ x and y′ ≥ y. We consider the (bottom-right) 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_{ℓ} = (d + 1 − ℓ, d) and the end points E_{ℓ} = (d − κ_{ℓ}, κ_{ℓ} + i_{ℓ}), ℓ = 1, 2, …, d. This border is a lattice path. We restrict our attention to the portion of this lattice path between A_{1} and E_{σ(1)}. (Here, as before, σ 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_{σ(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_{σ(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_{σ(1)} are played by A_{2} and E_{σ(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 ℓ-th path connecting A_{ℓ} and E_{σ(ℓ)}, and the family of these paths will be an element of 𝔫𝔦𝔭𝔞𝔱𝔥𝔰. 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 ℜ𝔪𝔰𝔢𝔱𝔰(Q) denote the set of all multisets of reflections (x, y) contained in [1, d] × [d + 1, n] which have the property Q. For example, Claim 2 will make an assertion about ℜ𝔪𝔰𝔢𝔱𝔰(S1), the set of all multisets of reflections (x, y) contained in [1, d] × [d + 1, n] which have the property (S1). Furthermore, we let Mpoints(𝔫𝔦𝔭𝔞𝔱𝔥𝔰) be the set of all multisets of lattice points which lie on some path family from 𝔫𝔦𝔭𝔞𝔱𝔥𝔰.

We are now ready to state:

Claim 2. We have

ℜ𝔪𝔰𝔢𝔱𝔰(S1) = Mpoints(𝔫𝔦𝔭𝔞𝔱𝔥𝔰).

Furthermore, for any multiset S from ℜ𝔪𝔰𝔢𝔱𝔰(S1), lightshadow(S) is an element of 𝔫𝔦𝔭𝔞𝔱𝔥𝔰, and it covers all the points of S.

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]×[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 𝔫𝔦𝔭𝔞𝔱𝔥𝔰. 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 ∪ {(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 P from 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 and consider the set of points points(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(P), thus obtaining S′ = points(P)∪{(x, y)}. Clearly, lightshadow(S′) cannot cover all the points from S′. However, this is a contradiction to the second assertion of Claim 2.

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 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}), …, (x_{t}, y_{t})} of points with x_{1} < x_{2} < ⋯ < x_{t} and y_{1} > y_{2} > ⋯ > y_{t} a chain. Furthermore, given a point A = (a_{1}, a_{2}), let us define regions R(A) by

R(A) := {(x, y) : x ≤ 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 a multiset S satisfies the chain condition (CC) if, for any q with 1 ≤ q ≤ 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 − κ_{q} − q. Here, as before, E_{q} = (d − κ_{q}, κ_{q} + i_{q}).

Claim 3. We have

ℜ𝔪𝔰𝔢𝔱𝔰(S1) = ℜ𝔪𝔰𝔢𝔱𝔰(CC)

and

Mpoints(𝔫𝔦𝔭𝔞𝔱𝔥𝔰) = ℜ𝔪𝔰𝔢𝔱𝔰(CC).

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 ∈ ℜ𝔪𝔰𝔢𝔱𝔰(S1). Since, by construction, lightshadow(S) is an element of 𝔫𝔦𝔭𝔞𝔱𝔥𝔰, this means that lightshadow(S) does not cover all the points of S. Let Z_{0} ∈ 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.

The idea is to construct, in the region strictly to the right and strictly below of Z_{0}, a sequence of east-north turns of the paths of lightshadow(S). Here, an eastnorth turn (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

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} . . . . .  . . . . . . . . . . . . . . .  . . . . .  . . . . . . . . . .^{.....}^{.....}^{.....}• •  • • • ∘ Z_{0} Z_{1}  Z_{2} Z_{3} E_{q}_{Figure 3}

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} > ⋯ > Z_{k} in R(E_{q}). Now we observe that, for any path family P from 𝔫𝔦𝔭𝔞𝔱𝔥𝔰, the number of lattice paths in 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 − κ_{q} − q. This observation follows, for example, by a reverse induction on q. Thus, k = d − κ_{q} − q, and, since by definition of lightshadow(S) any EN-turn is an element of S, all the points Z_{0}, Z_{1}, …, Z_{k} are elements of S. This means that we have found a chain of k + 1 = d − κ_{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.

We finally prove Claim 3 (and, thus, Claims 2 and 1, and Theorem 1).

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] × [d + 1, n].

A1. Mpoints(𝔫𝔦𝔭𝔞𝔱𝔥𝔰) ⊆ ℜ𝔪𝔰𝔢𝔱𝔰(CC). This is obvious from the above observation that, for any path family P from 𝔫𝔦𝔭𝔞𝔱𝔥𝔰, d − κ_{q} − q is the number of lattice paths in P that start strictly to the left of E_{q} and pass strictly above E_{q}.

A2. Mpoints(𝔫𝔦𝔭𝔞𝔱𝔥𝔰) ⊇ ℜ𝔪𝔰𝔢𝔱𝔰(CC). Given a multiset S ∈ ℜ𝔪𝔰𝔢𝔱𝔰(CC), our goal is to show that all the points of S lie on lightshadow(S), the latter being an element of 𝔫𝔦𝔭𝔞𝔱𝔥𝔰. 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.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘  ∘ ∘ ∘ ∘ ∘ ∘ • • • •  • • •  • • • • •  • •^{(2)}  ^{(4)}^{(3)}^{(3)}  ^{(2)}^{A_{9}} ^{A_{8}} ^{A_{7}} ^{A_{6}} ^{A_{5}} ^{A_{4}} ^{A_{3}} ^{A_{2}} ^{A_{1}}^{E_{1}}^{E_{2}} ^{E_{3}}  ^{E_{4}}^{E_{5}}  ^{E_{6}}^{E_{7}}^{E_{8}}^{E_{9}}^{E′_{7}}^{E′_{8}}^{E′_{9}}_{Figure 4}

For d = 1 the assertion is obvious (the quantity d − κ_{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 i = (i_{1}, i_{2}, …, i_{d}) and j = (j_{1}, j_{2}, …, 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, i = (4, 6, 7, 13, 14, 17, 19, 20, 21) and j = (1, 2, 4, 7, 10, 12, 13, 15, 16). The starting and end points determined by i and 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} ≥ j_{d}. (In our example we have k = 6.) Then the end points with x-coordinate d are E_{k}, E_{k+1}, …, 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}, …, E_{d} hit the vertical line x = d − 1 the last time in the points E′_{k+1}, …, E′_{d}, say (see Figure 4). Using the chain condition for E_{k}, E_{k+1}, … E_{d}, it is easy to see that for any q with k + 1 ≤ q ≤ 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 i and j, we consider i′ = (i_{1}, …, i_{k−1}, i′_{k+1} − 1, …, i′_{d} − 1) and j′ = (j_{1}, j_{2}, …, j_{d−1}), where i′_{ℓ} denotes the y-coordinate of E′_{ℓ}, ℓ = k + 1, …, d. It should be observed that, up to a vertical shift of 1 unit, the starting points determined by i′ and j′ are A_{2}, A_{3}, …, A_{d}, whereas the corresponding end points are E_{1}, …, E_{k−1}, E′_{k+1}, …, 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 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 that covers all the points of S.

A3. ℜ𝔪𝔰𝔢𝔱𝔰(S1) ⊆ ℜ𝔪𝔰𝔢𝔱𝔰(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 − κ_{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}, …, s_{d−κ_{q}−q+1}, and consider a reflection in the chain, (x, y) say. Since (x, y) ∈ R(E_{q}) we have x ≤ d − κ_{q}. Furthermore, we have

(τs_{1} ⋯ s_{d−κ_{q}−q+1})(x) = τ(y),

where as before τ is identified with j, i.e., τ = j_{1}j_{2} … j_{n} with j_{1} < j_{2} < ⋯ < j_{d} and j_{d+1} < ⋯ < j_{n−1} < j_{n}. Since (x, y) is contained in R(E_{q}) we have y > κ_{q} + i_{q} ≥ d. Because of j_{d+1} < ⋯ < j_{n−1} < j_{n}, this implies τ(y) ≥ τ(κ_{q} + i_{q} + 1).

We claim that τ(κ_{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}, …, j_{n}} is equal to the complement of {j_{1}, j_{2}, …, j_{d}} in {1, 2, …, n}, a value τ(y) = j_{y} for y > d is characterized by

j_{y} = (y − d) + |{ℓ : 1 ≤ ℓ ≤ d and j_{ℓ} < j_{y}}|.

Thus we may verify our claim by setting y = κ_{q} + i_{q} + 1 and substituting i_{q} + 1 for j_{κ_{q}+i_{q}+1} in this equation. Indeed, we have i_{q} + 1 = (κ_{q} + i_{q} + 1 − d) + (d − κ_{q}). Hence, we have τ(y) > i_{q}.

In summary, we have found d − κ_{q} − q + 1 values of x, 1 ≤ x ≤ d, such that

(τs_{1} ⋯ s_{d−κ_{q}−q+1})(x) > i_{q},  (3.2)

all of which are ≤ d − κ_{q}. Moreover, if d − κ_{q} < x ≤ d, then we have

(τs_{1} ⋯ s_{d−κ_{q}−q+1})(x) = τ(x) = j_{x} > i_{q}.

Hence, in total we found (d − κ_{q} − q + 1) + κ_{q} = d − q + 1 values x for which (3.2) holds. If we recall that we also always identify w with i, i.e., w = i_{1}i_{2} … i_{n}, then this is a contradiction to (S1).

A4. ℜ𝔪𝔰𝔢𝔱𝔰(S1) ⊇ ℜ𝔪𝔰𝔢𝔱𝔰(CC). Let S ∈ ℜ𝔪𝔰𝔢𝔱𝔰(CC), and consider a chain of t points of S, viewed as reflections s_{1} > s_{2} > ⋯ > s_{t}. Still identifying w and i, we observe that the inequality w ≥ τs_{1} ⋯ s_{t} is equivalent to the inequality

|{x : 1 ≤ x ≤ d and (τs_{1} ⋯ s_{t})(x) > i_{q}}| ≤ d − q  (3.3)

to hold for 1 ≤ q ≤ d.

A careful examination of the arguments in A3 shows that they actually prove

|{x : 1 ≤ x ≤ d and (τs_{1} ⋯ s_{t})(x) > i_{q}}| = |{ℓ : s_{ℓ} ∈ R(E_{q})}| + κ_{q}.

By assumption, our multiset S of points satisfies the chain condition, hence |{ℓ : s_{ℓ} ∈ R(E_{q})}| ≤ d − κ_{q} − q. Clearly, this implies (3.3), as desired. □

4. A formula for the Hilbert series of the tangent cone at a point. Now the full significance of Claim 2 can be revealed. Briefly, it allows the formulation of a version of Conjecture 1 in [10] which has the advantage of being efficient, as it reduces the computation of the Hilbert function of the tangent cone to X(w) at a point τ to a finite problem. More precisely, we can express the Hilbert series of the tangent cone in terms of a generating function for the set 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 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 [2, Eq. (1)], [8, p. 1021, line 11] or in [9, 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 P = (P_{1}, P_{2}, …, P_{d}) of paths P_{ℓ}, we write EN(P) for the number ∑_{ℓ=1}^{d} EN(P_{ℓ}) of all EN-turns in the family. Finally, given any weight function μ defined on a set M, by the generating function GF(M; μ) we mean ∑_{x∈M} μ(x).

Theorem 2. Conjecture 1 from [10] is equivalent to saying that the Hilbert series of the tangent cone to X(w) at τ is equal to

\frac{GF(𝔫𝔦𝔭𝔞𝔱𝔥𝔰; z^{EN(.)})}{(1 − z)^{∑_{ℓ=1}^{d} i_{ℓ}−\binom{d+1}{2}}} ,  (4.1)

where, as before, 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 is the set of all families (P_{1}, P_{2}, …, P_{d}) of non-intersecting lattice paths, where the path P_{ℓ} runs from (d+1−ℓ, d) to (d−κ_{ℓ}, κ_{ℓ}+i_{ℓ}), ℓ = 1, 2, …, d.

Proof. We can simply copy the corresponding proof in [8, first proof of Theorem 2].

According to Conjecture 1 from [10], the dimension of the m-th homogeneous component of the tangent cone is equal to the number of m-element multisets from ℜ𝔪𝔰𝔢𝔱𝔰(S1), that is, to the number of multisets of cardinality m which are contained in [1, d] × [d + 1, n] and satisfy (S1). Following [10] we denote this dimension by h_{T C_{τ} X(w)}(m).

Let S be an m-element multiset from ℜ𝔪𝔰𝔢𝔱𝔰(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}, …, P_{d}) from 𝔫𝔦𝔭𝔞𝔱𝔥𝔰. Each path P_{ℓ} contains a few (possibly multiple) points of S. However, at each EN-turn of P_{ℓ} there has to be at least one element of S, ℓ = 1, 2, …, d. Therefore, given such a path family (P_{1}, P_{2}, …, P_{d}) from 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 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}, …, P_{d}) under light-and-shadow, where

T = ∑_{ℓ=1}^{d}((d − κ_{ℓ}) + (κ_{ℓ} + i_{ℓ})) − ∑_{ℓ=1}^{d}((d + 1 − ℓ) + d) = ∑_{ℓ=1}^{d} i_{ℓ} − \binom{d + 1}{2}

is the total number of lattice points with y-coordinate > d on the lattice paths P_{1}, P_{2}, …, 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 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 with a total number of exactly t EN-turns, we obtain for the Hilbert series,

∑_{m=0}^{∞} h_{T C_{τ} X(w)}(m) z^{m} = ∑_{m=0}^{∞} ( ∑_{t=0}^{m} \binom{T + m − t − 1}{m − t}h_{t})z^{m}

= ∑_{t=0}^{∞} h_{t} ∑_{m=t}^{∞} \binom{T + m − t − 1}{m − t}z^{m}

= ∑_{t=0}^{∞} h_{t}z^{t} ∑_{m=0}^{∞} \binom{T + m − 1}{m}z^{m}

= \frac{∑_{t=0}^{∞} h_{t}z^{t}}{(1 − z)^{T}} .

The generating function ∑_{t=0}^{∞} h_{t}z^{t} is exactly the numerator in (4.1). This proves the theorem. □

Remarks. (1) Formula (4.1) implies the Rosenthal–Zelevinsky formula. For, the multiplicity mult_{τ} X(w) is equal to the numerator of the Hilbert series of the tangent cone to X(w) at τ, evaluated at z = 1. But, by (4.1), this is exactly the number of all families of non-intersecting lattice paths in 𝔫𝔦𝔭𝔞𝔱𝔥𝔰, 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 𝔫𝔦𝔭𝔞𝔱𝔥𝔰 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 [6, 8, 9, 11, 13]) 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 𝔫𝔦𝔭𝔞𝔱𝔥𝔰.

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

Note. After the first version of this paper was distributed, Vijay Kodiyalam and K. N. Raghavan proved Conjecture 1 from [10] in “Hilbert functions of points on Schubert varieties in Grassmannians,” J. Algebra 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 τ is indeed given by (4.1).

References

1. S. C. Billey and V. Lakshmibai, Singular loci of Schubert varieties, Birkhäuser, Boston, 2000.

2. A. Conca and J. Herzog, On the Hilbert function of determinantal rings and their canonical module, Proc. Amer. Math. Soc. 122 (1994), 677–681.

3. M. Desainte–Catherine, X. Viennot, Enumeration of certain Young tableaux with bounded height, Combinatoire énumérative, G. Labelle, P. Leroux, Eds., Springer–Verlag, Berlin, Heidelberg, New York, 1986, pp. 58–67.

4. W. Fulton, Young tableaux, Cambridge University Press, Cambridge, 1997.

5. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint, 1989, available

at http://www.cs.brandeis.edu/~ira.

6. C. Krattenthaler, Counting nonintersecting lattice paths with turns, Séminaire Lotharingien Combin. 34 (1995), paper B34i, 17 pp.

7. C. Krattenthaler, On multiplicities of points on Schubert varieties in Grassmannians, Séminaire Lotharingien Combin. 45 (2001), Article B45c.

8. C. Krattenthaler and M. Prohaska, A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, Trans. Amer. Math. Soc. 351 (1999), 1015–1042.

9. C. Krattenthaler and M. Rubey, A determinantal formula for the Hilbert series of one-sided ladder determinantal rings, Algebra, Arithmetic and Geometry with Applications (C. Christensen, G. Sundaram, A. Sathaye and C. Bajaj, eds.), Springer-Verlag, New York, 2004, pp. 525–552.

10. V. Kreiman and V. Lakshmibai, Multiplicities of singular points in Schubert varieties of Grassmannians, Algebra, Arithmetic and Geometry with Applications (C. Christensen, G. Sundaram, A. Sathaye and C. Bajaj, eds.), Springer-Verlag, New York, 2004, pp. 553–563.

11. D. M. Kulkarni, Counting of paths and coefficients of Hilbert polynomial of a determinantal ideal, Discrete Math. 154 (1996), 141–151.

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

13. M. R. Modak, Combinatorial meaning of the coefficients of a Hilbert polynomial, Proc. Indian Acad. Sci. (Math. Sci.) 102 (1992), 93–123.

14. J. Rosenthal and A. Zelevinsky, Multiplicities of points on Schubert varieties in Grassmannians, J. Algebraic Combin. 13 (2001), 213–218.

15. X. Viennot, Une forme géométrique de la correspondance de Robinson–Schensted, Combinatoire et Représentation du Groupe Symétrique, D. Foata ed., Lecture Notes in Math., Vol. 579,

Springer–Verlag, New York, 1977, pp. 29–58. Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.