A Note on Hodge’s Postulation Formula for Schubert Varieties ^{1}

SUDHIR R. GHORPADE^{2} Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India, srg@math.iitb.ac.in

1 INTRODUCTION

Given a projective algebraic variety X in the N-dimensional projective space ℙ_{k}^{N} over an algebraically closed field k, we can associate to X its Hilbert function, viz., the function h : ℕ → ℕ defined on the set ℕ of nonnegative integers by

h(ℓ) = dim_{k} R_{ℓ}, for ℓ ∈ ℕ

where R denotes the homogeneous coordinate ring of X, i.e., R is the polynomial ring over k in N + 1 variables modulo the vanishing ideal of X, and R_{ℓ} denotes its ℓ–th homogeneous component. It is well-known that h(ℓ) is a polynomial function, for all large enough values of ℓ, and this polynomial, called the Hilbert polynomial of X, contains a lot of useful geometric information about X. However, the Hilbert polynomial is not always easy to compute explicitly in substantial examples of geometric interest. Classically, the known cases seem only to include simple examples such as hypersurfaces, rational normal curves, and more generally, complete intersections. Recently, Hilbert polynomials of determinantal varieties of various kinds, have been explicitly determined [1, 2, 5, 7]. However some of these formulae are quite complicated.

Schubert varieties in Grassmannians form an important class of projective varieties, which have been considered at least since the last century. A nice, short and explicit formula for the Hilbert polynomial of such a variety, known as the postulation formula, was obtained by Hodge [9] in 1943. We feel that this formula deserves to be better known, especially since it arises in a number of seemingly different contexts, particularly in Combinatorics. Partly motivated by this desire, we describe in this note the formula of Hodge, derive a slightly simpler description of it and give an alternate proof of the formula. This will also provide us with an opportunity to briefly introduce combinatorics of nonintersecting lattice paths, which, in the same vein, deserves to be better known among the algebraists.

1This is an unofficial electronic version of the paper which has appeared in Geometric and Combinatorial Aspects of Commutative Algebra (Messina, 1999), J. Herzog and G. Restuccia Eds., Lecture Notes in Pure and Applied Mathematics, Vol. 217, Marcel Dekker, New York (2001), pp. 211-220; MR 2002d:14079.

2Partially supported by a ‘Career Award’ grant from AICTE, New Delhi and an IRCC grant from IIT Bombay.

The basic facts needed about Schubert varieties in Grassmannians are described in the next section. We review some combinatorial facts about lattice paths in Section 3. Finally, a proof of the postulation formula is given in Section 4.

2 SCHUBERT VARIETIES IN GRASSMANNIANS

Let k be a field, which, for simplicity, we assume to be algebraically closed. Let V be a vector space of dimension n over k. Given any integer d with 1 ≤ d ≤ n, the Grassmannian G_{d}(V) is defined to be the space of d-dimensional linear subspaces of V. This has a canonical embedding

G_{d}(V) ↪ ℙ(Λ^{d}V) ≃ ℙ_{k}^{\binom{n}{d}−1}

known as the Plücker embedding, and via this embedding G_{d}(V) has the structure of a projective algebraic variety. Briefly, the Plücker embedding may be described as follows. Fix a basis {e_{1}, …, e_{n}} of V. Then e_{α} := e_{α_{1}} ∧ … ∧ e_{α_{d}}, where α varies over the indexing set

I(d, n) = {α = (α_{1}, …, α_{d}) ∈ ℤ^{d} : 1 ≤ α_{1} < … < α_{k} ≤ n}

form a basis of Λ^{d}V. The image of a subspace W ∈ G_{d}(V) is the point of ℙ(Λ^{d}V) corresponding to the one-dimensional subspace of Λ^{d}V spanned by w_{1} ∧ … ∧ w_{d}, where {w_{1}, …, w_{d}} is (any) basis of W. If we write

w_{1} ∧ … ∧ w_{d} = ∑_{α∈I(d,n)} p_{α}(W)e_{α}, where p_{α}(W) ∈ k, for α ∈ I(d, n)

then p(W) = (p_{α}(W))_{α∈I(d,n)} is called the Plücker coordinate of W.

Given any α =∈ I(d, n), the corresponding Schubert variety Ω_{α} is defined by

Ω_{α} = {W ∈ G_{d}(V) : dim (W ∩ A_{i}) ≥ i for i = 1, …, d} ,

where A_{i} = span{e_{1}, …, e_{α_{i}}} for 1 ≤ i ≤ d. We have a partial order, called the Bruhat order, on the indexing set I(d, n), which is defined by

β ≤ β′ ⟺ β_{j} ≤ β′_{j} for all j = 1, …, d,

where β = (β_{1}, …, β_{d}) and β′ = (β′_{1}, …, β′_{d}) are arbitrary elements of I(d, n). Using this, we can describe Ω_{α} in terms of the Plücker coordinates as follows.

Ω_{α} = {p = (p_{γ}) ∈ G_{d}(V) : p_{β} = 0 for all β ∈ I(d, n) with β ≰ α} .

Hence, Ω_{α} is also a projective algebraic variety. In fact, Ω_{α} is irreducible and

dim Ω_{α} = ∑_{i=1}^{d} α_{i} − \frac{d(d + 1)}{2}.

Note that G_{d}(V) is a particular case of Ω_{α} with α = (n − d + 1, n − d + 2, …, n). In particular, dim G_{d}(V) = d(n − d). For proofs of the basic results mentioned above as well as for a more leisurely discussion, we refer to Hodge and Pedoe’s book [10] or the expository article of Kleiman and Laksov [12].

We shall now turn our attention to the structure of the homogeneous coordinate ring of Schubert varieties. Let P = {P_{γ} : γ ∈ I(d, n)} be a family of independent indeterminates over k and k[P] be the ring of polynomials in these indeterminates with coefficients in k. Fix α ∈ I(d, n), and let I(Ω_{α}) denote the (vanishing) ideal of Ω_{α}. This is a homogeneous ideal of k[P] and thus the residue class ring R^{α} = k[P]/I(Ω_{α}) has a natural graded ring structure. For ℓ ∈ ℕ, let R_{ℓ}^{α} denote the ℓ-th graded component of R^{α}. Also let p_{γ} denote the image of P_{γ} in R^{α}. By a standard monomial on Ω_{α} we mean an element of R^{α} of the form p_{γ^{1}}p_{γ^{2}} ⋯ p_{γ^{ℓ}}, where γ^{1}, …, γ^{ℓ} are elements of I(d, n) with the property that γ^{1} ≤ … ≤ γ^{ℓ} ≤ α. The number of terms, i.e., ℓ, is called the degree of this monomial. Now we have the following basic result.

THEOREM 1 The standard monomials on Ω_{α} form a vector space basis of R^{α}. More precisely, for each ℓ ∈ ℕ, the standard monomials on Ω_{α} of degree ℓ form a vector space basis of R_{ℓ}^{α}.

Observe that a standard monomial on Ω_{α} of degree ℓ is completely determined by a ℓ × d rectangular array (a_{ij}) of integers with the property that

1 ≤ a_{i1} < … < a_{id} for 1 ≤ i ≤ ℓ and a_{1j} ≤ … ≤ a_{ℓj} ≤ α_{j} for 1 ≤ i ≤ d. (1)

We shall refer to such integral arrays as rectangular standard tableaux bounded by α of size ℓ × d. The following corollary is an immediate consequence of the above theorem.

COROLLARY 2 The Hilbert function h_{α} of Ω_{α} is given by

h_{α}(ℓ) = #(rectangular standard tableaux bounded by α of size ℓ × d), for ℓ ∈ ℕ.

REMARK 3 The above theorem describing an explicit basis for the homogeneous coordinate ring of Schubert varieties is sometimes called Hodge Basis Theorem. A proof in characteristic zero is given in Hodge and Pedoe [10, Ch. XIV, Sec. 9]. For a characteristic free proof, see, for example, Musili [15]. The Brandeis lecture notes of Seshadri [16] is also a nice readable reference for a proof of this theorem as well as for extensions to the context of Schubert varieties in G/P, where G is a nice algebraic group and P a parabolic subgroup.

3 NONINTERSECTING LATTICE PATHS

Let A = (a, a′) and B = (b, b′) be points with integer coordinates, i.e., in ℤ^{2}. By a lattice path from A to B we mean a finite sequence L = (P_{0}, P_{1}, …, P_{m}) of points in ℤ^{2} with P_{0} = A, P_{m} = B and

P_{i} − P_{i−1} = (1, 0) or (0, 1) for i = 1, …, m.

Note that the lattice path L is determined by its point set L̄ = {P_{j} : 0 ≤ j ≤ m} by simply arranging the elements of this set in a lexicographic order.

In more intuitive terms, a lattice path consists of vertical or horizontal steps of length 1. For example, a lattice path from A = (1, 1) to B = (5, 6) may be depicted as follows.

[figure: A; B]

Figure 1

It is clear that a lattice path from A to B would require b − a vertical steps and b′ − a′ horizontal steps, and it would be determined once we choose which of the total b − a + b′ − a′ (ordered) steps are vertical. Thus,

# (lattice paths from A to B) = \binom{b − a + b′ − a′}{b − a}.  (2)

Note that this number is positive if and only if b ≥ a and b′ ≥ a′.

Given any two d-tuples 𝒜 = (A_{1}, …, A_{d}) and ℬ = (B_{1}, …, B_{d}) of points in ℤ^{2}, by a d-path, or simply, a path, from 𝒜 to ℬ we mean a d-tuple ℒ = (L_{1}, …, L_{d}) where L_{r} is a lattice path from A_{r} to B_{r}, for 1 ≤ r ≤ d. We call ℒ to be nonintersecting if no two of the paths L_{1}, …, L_{d} have a point in common; otherwise, we call it intersecting. For counting the number of nonintersecting lattice paths, we have the following beautiful result.

THEOREM 4 Let A_{r} = (a_{r}, a′_{r}) and B_{r} = (b_{r}, b′_{r}), r = 1, …, d, be points in ℤ^{2} satisfying

a_{1} ≥ … ≥ a_{d}, b_{1} ≥ … ≥ b_{d} and a′_{1} ≤ … ≤ a′_{d}, b′_{1} ≤ … ≤ b′_{d}.  (3)

Let 𝒜 = (A_{1}, …, A_{d}) and ℬ = (B_{1}, …, B_{d}). Then the number of nonintersecting paths from 𝒜 to ℬ is equal to the binomial determinant

det (\binom{b_{j} − a_{i} + b′_{j} − a′_{i}}{b_{j} − a_{i}}_{1≤i,j≤d})  (4)

In other words, this is the determinant of a d × d matrix whose (i, j)-th entry is the number of lattice paths from A_{i} to B_{j}.

The idea behind the proof is quite simple and elegant. Let us illustrate in the case d = 2. So let 𝒜 = (A_{1}, A_{2}) and ℬ = (B_{1}, B_{2}), with A_{i}, B_{i} as in Theorem 4. From (2) it is clear that

# (lattice paths from 𝒜 to ℬ) = \binom{b_{1} − a_{1} + b′_{1} − a′_{1}}{b_{1} − a_{1}}\binom{b_{2} − a_{2} + b′_{2} − a′_{2}}{b_{2} − a_{2}}. (5)

If a path ℒ = (L_{1}, L_{2}) from 𝒜 to ℬ, where L_{1} = (P_{0}, …, P_{s}) and L_{2} = (Q_{0}, …, Q_{t}) is intersecting, then we can find least i ≥ 0 such that P_{i} = Q_{j} for some j ≤ t. Now switch the paths at P_{i} = Q_{j}, i.e., consider L′_{1} = (P_{0}, …, P_{i}, Q_{j+1}, …, Q_{t}) and L′_{2} = (Q_{0}, …, Q_{j}, P_{i+1}, …, P_{s}). In this way we get a path from (A_{1}, A_{2}) to (B_{2}, B_{1}). Conversely, by (3), any path from (A_{1}, A_{2}) to (B_{2}, B_{1}) must intersect, and a similar switching yields an intersecting path from 𝒜 to ℬ. Thus one obtains a bijection which shows that

# (intersecting paths from 𝒜 to ℬ) = \binom{b_{2} − a_{1} + b′_{2} − a′_{1}}{b_{2} − a_{1}}\binom{b_{1} − a_{2} + b′_{1} − a′_{2}}{b_{1} − a_{2}}.

The last equation together with (5) implies the formula (4) in the case d = 2. In the general case, one considers permutations σ of {1, …, d} and the set

𝒫_{σ} = {ℒ = (L_{1}, …, L_{d}) : L_{r} is a lattice path from A_{r} to B_{σ(r)} for 1 ≤ r ≤ d} .

By a similar switching trick, one can obtain an involution ϕ on the set of pairs (σ, ℒ), where σ ∈ S_{d}, ℒ ∈ 𝒫_{σ} and ℒ is intersecting, such that if ϕ ((σ, ℒ)) = (σ′, ℒ′), then sgn(σ′) = −sgn(σ). Now, expanding the determinant in (4), and using (2), we see that (4) can be written as

∑_{σ∈S_{d}} sgn(σ) ∑_{ℒ∈𝒫_{σ}} 1 = ∑_{σ ∈ S_{d}, ℒ ∈ 𝒫_{σ} ℒ nonintersecting} sgn(σ) + ∑_{σ ∈ S_{d}, ℒ ∈ 𝒫_{σ} ℒ intersecting} sgn(σ).

Thanks to the sign-reversing involution ϕ, the terms in the last summation cancel each other, whereas by (3), a path ℒ ∈ 𝒫_{σ} can only be nonintersecting when σ is the identity permutation. Thus the right hand side is the number of nonintersecting paths from 𝒜 to ℬ, and we have the desired formula.

REMARK 5 The above result is due to Gessel and Viennot [4] though the ideas can perhaps be traced to the works of Karlin-McGregor [11] and Lindstorm [14]. In [4] the endpoints A_{i}, B_{i} are of a more restrictive nature, but the arguments in the proof remain similar.

4 HODGE’S POSTULATION FORMULA

Fix positive integers d, n with d ≤ n and α = (α_{1}, …, α_{d}) ∈ I(d, n). Let Ω_{α} denote, as before, the Schubert variety corresponding to α in the Grassmannian of d-dimensional linear subspaces of an n-dimensional vector space over k. The postulation formula of Hodge [10, Thm. III, p. 387], in our notation, can be stated as follows.

THEOREM 6 The Hilbert function of Ω_{α} is given by

h_{α}(ℓ) = det (\binom{α_{d−i+1} + ℓ + i − j − 1}{ℓ + i − j}_{1≤i,j≤d}) for ℓ ∈ ℕ.

In particular, the Hilbert polynomial of Ω_{α} equals the Hilbert function for all nonnegative integral values of the parameter ℓ.

An alternate description of this formula is provided by the following lemma.

LEMMA 7 Given any ℓ ∈ ℕ, we have

det (\binom{α_{d−i+1} + ℓ + i − j − 1}{ℓ + i − j}_{1≤i,j≤d}) = det (\binom{ℓ + α_{j} − j}{ℓ + i − j}_{1≤i,j≤d}) .

Proof: If (b_{i,j}) is any d × d matrix, then by a cyclic permutation of the rows (or alternatively, by successive row interchanges) we can transform it to the d × d matrix whose (i, j)-th entry is b_{d−i+1,j}. This will change the sign of det (b_{i,j}) by (−1)^{d(d−1)/2}. We can also do a similar operation on the columns. Combining these two, we see that det (b_{i,j}) = det (b_{d−i+1,d−j+1}). In particular, we have

det (\binom{α_{d−i+1} + ℓ + i − j − 1}{ℓ + i − j}_{1≤i,j≤d}) = det (\binom{α_{i} + ℓ − i + j − 1}{ℓ − i + j}_{1≤i,j≤d})

Now for the d×d matrix corresponding to the determinant on the right hand side of the above equation, we successively make the n − 1 elementary column operations C_{n} − C_{n−1}, C_{n−1} − C_{n−2}, …, C_{2} − C_{1}. Then in view of the Pascal triangle identity

\binom{s}{t} − \binom{s − 1}{t − 1} = \binom{s − 1}{t}

the (i, j)-th entry changes from \binom{α_{i}+ℓ−i+j−1}{ℓ−i+j} to \binom{α_{i}+ℓ−i+j−2}{ℓ−i+j}, for j ≥ 2, while the determinant is unaltered. Next, we make the n − 2 elementary column operations C_{n} − C_{n−1}, C_{n−1} − C_{n−2}, …, C_{3} − C_{2}, and continue in this way till in the end we just make a single column operation C_{n} − C_{n−1}. In this process the j-th column of the original matrix is altered j − 1 times, and its entries eventually become

\binom{α_{i} + ℓ − i + j − 1 − (j − 1)}{ℓ − i + j} = \binom{α_{i} + ℓ − i}{ℓ − i + j}.

By taking the transpose of the resulting matrix, we have the desired formula. □

We will now link the rectangular standard tableaux appearing in Corollary 2 to nonintersecting paths. The idea to associate such a path to a rectangular tableaux (a_{ij}) is quite simple. Start at (1, 1). Move vertically till (1, a_{11}). Go one step to the right, and then move vertically till (2, a_{21}). Continue in this way till we reach (ℓ, a_{ℓ1}). Take a final step to the right and then move vertically to end at (ℓ+1, α_{1}). Next, start at (0, 2) and use the second column to obtain the second lattice path, and so on. To recover the tableaux from a nonintersecting d-path, it suffices to look at the northeast corners in each path. More formally, we have the following.

LEMMA 8 Let ℓ ∈ ℕ. Define A_{r} = (2−r, r) and B_{r} = (ℓ−r+2, α_{r}), for 1 ≤ r ≤ d, and let 𝒜 = (A_{1}, …, A_{d}) and ℬ = (B_{1}, …, B_{d}). Then the set of rectangular standard tableaux bounded by α of size ℓ × d is in one-to-one correspondence with the set of nonintersecting paths between 𝒜 and ℬ.

Proof: Let (a_{ij}) be a rectangular standard tableaux bounded by α of size ℓ × d. As a convention, we set, a_{0j} = j and a_{ℓ+1 j} = α_{j} for 1 ≤ j ≤ d. By (1), it is clear that a_{0j} ≤ a_{1j} ≤ … ≤ a_{ℓj} ≤ a_{ℓ+1 j} for each j = 1, …, d. For 1 ≤ r ≤ d, define L_{r} to be the lattice path from A_{r} to B_{r} whose point set is given by

L̄_{r} = {(i − r + 1, j) : 1 ≤ i ≤ ℓ + 1 and a_{i−1 r} ≤ j ≤ a_{ir}}

It is easy to see that L_{r} is well-defined. Moreover, if for 1 ≤ r, s ≤ d, r ≠ s, the lattice paths L_{r} and L_{s} intersect, then we have (i_{1} − r + 1, j_{1}) = (i_{2} − s + 1, j_{2}) for appropriate i_{1}, i_{2}, j_{1}, j_{2}, and if, without loss of generality, we have r < s, then i_{1} ≤ i_{2} − 1 and hence j_{2} = j_{1} ≤ a_{i_{1}r} ≤ a_{i_{2}−1 r} < a_{i_{2}−1 s}, which is a contradiction. Thus ℒ = (L_{1}, …, L_{d}) is a nonintersecting d-path from 𝒜 to ℬ.

Conversely, let ℒ = (L_{1}, …, L_{d}) be a nonintersecting d-path from 𝒜 to ℬ. Given 1 ≤ r ≤ d, the fact that L_{r} is a lattice path implies that for 1 ≤ i ≤ ℓ, we have

max{j ∈ ℕ : (i − r + 1, j) ∈ L̄_{r}} = min{j ∈ ℕ : (i − r + 2, j) ∈ L̄_{r}};

let a_{ir} be this common value. In this way we get a ℓ × d array (a_{ij}) of integers. Since L_{r} is a lattice path from A_{r} to B_{r}, we have 1 ≤ a_{ir} ≤ a_{i+1 r} ≤ α_{r} for 1 ≤ i < ℓ. Further, if a_{ir} ≥ a_{i r+1}, then it is clear that the truncated paths L′_{r} and L′_{r+1} obtained respectively by moving along L_{r} and L_{r+1} till (i − r + 1, a_{ir}) and (i − r + 2, a_{i r+1}), must intersect. This contradicts the assumption that ℒ is nonintersecting. It follows that the array (a_{ij}) satisfies the properties in (1).

In this way we get a map from the set of nonintersecting d-paths from 𝒜 to ℬ to the set of rectangular standard tableaux bounded by α of size ℓ × d, and vice-versa. It is easy to see that the composites, either way, are identity maps. □

Proof of Theorem 6: Follows from Corollary 2, Theorem 4 and Lemmas 7 and 8. □

REMARK 9 It may be remarked that the above proof of Hodge’s postulation formula is structurally analogous to the proof given in [2] and [6] for determining the Hilbert function and Hilbert series of certain determinantal ideals. The correspondence between the standard bitableaux appearing there and nonintersecting lattice paths (with a given number of turns) was somewhat more intricate, i.e., first one had to use a version of the Robinson-Schensted-Knuth correspondence and then something like Viennot’s light-and-shadow procedure. Here, as Lemma 8 shows, we can use a more direct correspondence. On the other hand, it does not appear easy to find a ‘good formula’ for the Hilbert series of Ω_{α}. Connection with lattice paths has also been exploited in [8] to prove a formula for the multiplicity of determinantal ideals. Hodge’s postulation formula, and particularly the unusual fact that the Hilbert function h_{α}(ℓ) is a polynomial for all values of ℓ was in fact, the starting point of the investigations by Musili [15], which led to certain vanishing theorems for Schubert varieties in Grassmannians. These results have now been vastly generalized (see [13] for a survey) while a far-reaching generalization of Hodge’s postulation formula itself has been obtained by Fulton and Lascoux [3].

REFERENCES

1. S. S. Abhyankar. Enumerative Combinatorics of Young Tableaux. New York: Marcel Dekker, 1988.

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

3. W. Fulton, A. Lascoux. A Pieri formula in the Grothendieck ring of a flag bundle. Duke Math. J., 76:711–729, 1994.

4. I. Gessel, G. Viennot. Binomial determinants, paths and hook length formulae. Adv. Math., 58:300–321, 1985.

5. S. R. Ghorpade. Abhyankar’s work on Young tableaux and some recent developments. In: C. Bajaj ed. Algebraic Geometry and Its Applications. New York: Springer–Verlag, 1994, pp. 215–249.

6. S. R. Ghorpade. Young bitableaux, lattice paths and Hilbert functions. J. Statist. Plann. Inference, 54:55–66, 1996.

7. S. R. Ghorpade. On the enumeration of indexed monomials and the computation of Hilbert functions of ladder determinantal varieties. In: C. Martinez, M. Noy and O. Serra ed. FPSAC’99 Actes/Proceedings. Barcelona: Universitat Politécnica de Catalunya, 1999, pp. 225–232.

8. J. Herzog, N. V. Trung. Gröbner bases and multiplicity of determinantal and pfaffian ideals. Adv. Math., 96:1–37, 1992.

9. W. V. D. Hodge. Some enumerative results in the theory of forms. Proc. Camb. Phil. Soc. 39:22–30, 1943.

10. W. V. D. Hodge, D. Pedoe. Methods of Algebraic Geometry, Vol. II. Cambridge: Cambridge Univ. Press, 1952.

11. S. Karlin, G. McGregor. Coincidence probabilities. Pacific J. Math., 9:1141– 1164, 1958.

12. S. L. Kleiman, D. Laksov. Schubert Calculus. Amer. Math. Monthly, 79:1061– 1082, 1972.

13. V. Lakshmibai, C. S. Seshadri. Standard monomial theory. In: S. Ramanan, C. Musili and N. Mohan Kumar ed. Proceedings of the Hyderabad Conference on Algebraic Groups, Madras: Manoj Prakashan, 1991, pp. 279–322.

14. B. Lindstorm. On the vector representation of induced matroids. Bull. London Math. Soc., 5:85–90, 1973.

15. C. Musili. Postulation formula for Schubert varieties. J. Indian Math. Soc., 36:143–171, 1972.

16. C. S. Seshadri. Introduction to Standard Monomial Theory. Lecture Notes No. 4, Brandeis University, Waltham, MA, 1985.