SCHUBERT VARIETIES, LINEAR CODES AND ENUMERATIVE COMBINATORICS

SUDHIR R. GHORPADE AND MICHAEL A. TSFASMAN

Abstract. We consider linear error correcting codes associated to higher dimensional projective varieties defined over a finite field. The problem of determining the basic parameters of such codes often leads to some interesting and difficult questions in combinatorics and algebraic geometry. This is illustrated by codes associated to Schubert varieties in Grassmannians, called Schubert codes, which have recently been studied. The basic parameters such as the length, dimension and minimum distance of these codes are known only in special cases. An upper bound for the minimum distance is known and it is conjectured that this bound is achieved. We give explicit formulae for the length and dimension of arbitrary Schubert codes and prove the minimum distance conjecture in the affirmative for codes associated to Schubert divisors.

1. Introduction

Let 𝔽_{q} denote the finite field with q elements, and let n, k be integers with 1 ≤ k ≤ n. The n-dimensional vector space 𝔽_{q}^{n} has a norm, called Hamming norm, which is defined by

∥x∥ = | {i ∈ {1, …, n} : x_{i} ≠ 0} | for x ∈ 𝔽_{q}^{n}.

More generally, if D is a subspace of 𝔽_{q}^{n}, the Hamming norm of D is defined by

∥D∥ = | {i ∈ {1, …, n} : there exists x ∈ D with x_{i} ≠ 0} |.

A linear [n, k]_{q}-code is, by definition, a k-dimensional subspace of 𝔽_{q}^{n}. The adjective linear will often be dropped since in this paper we only consider linear codes. The parameters n and k are referred to as the length and the dimension of the corresponding code. If C is an [n, k]_{q}-code, then the minimum distance d = d(C) of C is defined by

d(C) = min {∥x∥ : x ∈ C, x ≠ 0} .

More generally, given any positive integer r, the rth higher weight d_{r} = d_{r}(C) of C is defined by

d_{r}(C) = min {∥D∥ : D is a subspace of C with dim D = r} .

Note that d_{1}(C) = d(C).

An [n, k]_{q}-code is said to be nondegenerate if it is not contained in a coordinate hyperplane of 𝔽_{q}^{n}. Two [n, k]_{q}-codes are said to be equivalent if one can be obtained from another by permuting coordinates and multiplying them by nonzero elements of 𝔽_{q}; in other words, if they are in the same orbit for the natural action of the semidirect product of (𝔽_{q}^{∗})^{n} and S_{n}. It is clear that this gives a natural equivalence relation on the set of [n, k]_{q}-codes.

Date: July 5, 2004.

Key words and phrases. Grassmannian, linear codes, minimum distance, projective system, Schubert variety.

The first named author was partially supported by a ‘Career Award’ grant from AICTE, New Delhi and an IRCC grant from IIT Bombay. The second named author was partially supported by the RFBR Grants 99-01-01204, 02-01-01041 and 02-01-22005.

An alternative way to describe codes is via the language of projective systems introduced in [18]. A projective system is a (multi)set X of n points in the projective space ℙ^{k−1} over 𝔽_{q}. We call X nondegenerate if these n points are not contained in a hyperplane of ℙ^{k−1}. Two projective systems in ℙ^{k−1} are said to be equivalent if there is a projective automorphism of the ambient space ℙ^{k−1}, which maps one to the other; in other words, if they are in the same orbit for the natural action of P GL(k, 𝔽_{q}). It is clear that this gives a natural equivalence relation on the set of projective systems of n points in ℙ^{k−1}.

It turns out that a nondegenerate projective system of n points in ℙ^{k−1} corresponds naturally to a nondegenerate linear [n, k]_{q}-code. Moreover, if we pass to equivalence classes with respect to the equivalence relations defined above, then this correspondence is one-to-one. The minimum distance of the code C = C_{X} associated to a nondegenerate projective system X of n points in ℙ^{k−1} admits a nice geometric interpretation in terms of X, namely,

d(C_{X}) = n − max {|X ∩ H| : H a hyperplane of ℙ^{k−1}} .

We have a similar interpretation for the rth higher weight d_{r}(C_{X}), where the hyperplane H is replaced by a projective subspace of codimension r in ℙ^{k−1}. For more details concerning projective systems, higher weights and a proof of the above mentioned one-to-one correspondence, we refer to [18] and [19].

The language of projective systems not only explains the close connection between algebraic geometry and coding theory, but also facilitates the introduction of linear codes corresponding to projective algebraic varieties defined over a finite field. A case in point is the Grassmannian G_{ℓ,m} = G_{ℓ}(V) of ℓ-dimensional subspaces of an m-dimensional vector space V over 𝔽_{q}. We have the well-known Plücker embedding of the Grassmannian into a projective space (cf. [3], [9]), and this embedding is known to be nondegenerate. Considering the (𝔽_{q}-rational) points of G_{ℓ,m} as a projective system, we obtain a q-ary linear code, called the Grassmann code, which we denote by C(ℓ, m). These codes were first studied by Ryan [14, 15, 16] in the binary case and by Nogin [12] in the q-ary case. It is clear that the length n and the dimension k of C(ℓ, m) are given by

(1)  n = \left[{m \atop ℓ}\right]_{q} := \frac{(q^{m} − 1)(q^{m} − q) ⋯ (q^{m} − q^{ℓ−1})}{(q^{ℓ} − 1)(q^{ℓ} − q) ⋯ (q^{ℓ} − q^{ℓ−1})} and k = \binom{m}{ℓ}.

The minimum distance of C(ℓ, m) is given by the following elegant formula due to Nogin [12]:

(2)  d (C(ℓ, m)) = q^{δ}, where δ := ℓ(m − ℓ).

In fact, Nogin [12] also determined some of the higher weights of C(ℓ, m). More precisely, he showed that for 1 ≤ r ≤ max{ℓ, m − ℓ} + 1,

(3)  d_{r} (C(ℓ, m)) = q^{δ} + q^{δ−1} + ⋯ + q^{δ−r+1}.

Alternative proofs of (3) were given in [3], and in the same paper a generalization to Schubert codes was proposed. The Schubert codes are indexed by the elements of the set

I(ℓ, m) := {α = (α_{1}, …, α_{ℓ}) ∈ ℤ^{ℓ} : 1 ≤ α_{1} < ⋯ < α_{ℓ} ≤ m}.

Given any α ∈ I(ℓ, m), the corresponding Schubert code is denoted by C_{α}(ℓ, m), and it is the code obtained from the projective system defined by the Schubert variety Ω_{α} in G_{ℓ,m} with a nondegenerate embedding induced by the Plücker embedding. Recall that Ω_{α} can be defined by

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

where A_{j} denotes the span of the first j vectors in a fixed basis of V, for 1 ≤ j ≤ m. It was observed in [3] that the length n_{α} and the dimension k_{α} of C_{α}(ℓ, m) are abstractly given by

(4)  n_{α} = |Ω_{α}(𝔽_{q})| and k_{α} = |{β ∈ I(ℓ, m) : β ≤ α}|,

where for β = (β_{1}, …, β_{ℓ}) ∈ I(ℓ, m), by β ≤ α we mean that β_{i} ≤ α_{i} for i = 1, …, ℓ. It was shown in [3] that the minimum distance of C_{α}(ℓ, m) satisfies the inequality

d(C_{α}(ℓ, m)) ≤ q^{δ_{α}}, where δ_{α} := ∑_{i=1}^{ℓ}(α_{i} − i) = α_{1} + ⋯ + α_{ℓ} − \frac{ℓ(ℓ + 1)}{2}.

Further, it was conjectured by the first named author that, in fact, the equality holds, i.e.,

(5)  d(C_{α}(ℓ, m)) = q^{δ_{α}}.

We shall refer to (5) as the minimum distance conjecture (for Schubert codes). Note that if α = (m − ℓ + 1, …, m − 1, m), then Ω_{α} = G_{ℓ,m} and so in this case (5) is an immediate consequence of (2).

The minimum distance conjecture has been proved in the affirmative by Hao Chen [1] when ℓ = 2. In fact, he proves the following. If ℓ = 2 and α = (m − h − 1, m) [we can assume that α is of this form without any loss of generality], then d(C_{α}(2, m)) = q^{δ_{α}} = q^{2m−h−4}, and moreover,

(6)  n_{α} = \frac{(q^{m} − 1)(q^{m−1} − 1)}{(q^{2} − 1)(q − 1)} − ∑_{j=1}^{h} ∑_{i=1}^{j} q^{2m−j−2−i}, and

(7)  k_{α} = \frac{m(m − 1)}{2} − \frac{h(h + 1)}{2}.

An alternative proof of the minimum distance conjecture, as well as the weight distribution of codewords in the case ℓ = 2, was obtained independently by Guerra and Vincenti [7]; in the same paper, they prove also the following lower bound for d(C_{α}(ℓ, m)) in the general case:

(8)  d(C_{α}(ℓ, m)) ≥ \frac{q^{α_{1}}(q^{α_{2}} − q^{α_{1}}) ⋯ (q^{α_{ℓ}} − q^{α_{ℓ−1}})}{q^{1+2+···+ℓ}} ≥ q^{δ_{α}−ℓ}.

In an earlier paper, Vincenti [20], partly in collaboration with Guerra, verified the minimum distance conjecture for the unique nontrivial Schubert variety in the Klein quadric G_{2,4}, namely Ω_{(2,4)}, and obtained a lower bound which is weaker than (8), and also proved the following formula^{1} for the length of C_{α}(ℓ, m).

(9)  n_{α} = |Ω_{α}(𝔽_{q})| = ∑_{(k_{1},...,k_{ℓ−1})} ∏_{i=0}^{ℓ−1} \left[{α_{i+1} − α_{i} \atop k_{i+1} − k_{i}}\right]_{q}q^{(α_{i}−k_{i})(k_{i+1}−k_{i})},

where the sum is over all (ℓ − 1)-tuples (k_{1}, …, k_{ℓ−1}) of integers with i ≤ k_{i} ≤ α_{i} and k_{i} ≤ k_{i+1} for 1 ≤ i ≤ ℓ − 1, and where, by convention, α_{0} = 0 = k_{0} and k_{ℓ} = ℓ.

We can now describe the contents of this paper. In Section 2 below, we give two formulae for the length n_{α} of C_{α}(ℓ, m). Of these, the first is very simple and is related to a classical result about the Grassmannians. The other formula is somewhat similar to (9) even though it was obtained independently. The latter formula may be a little more effective in actual computations. Next, in Section 3, we give a determinantal formula for the dimension k_{α} of C_{α}(ℓ, m) and show that in certain cases this determinant can be evaluated. Moreover, we also give an alternative formula for k_{α} using the formulae for n_{α} obtained in the previous section. Finally, in Section 4, we show that the minimum distance and some of the higher weights for the codes corresponding to Schubert divisors, i.e., Schubert varieties of codimension one in the corresponding Grassmannians, can be easily obtained using the results of [3] and [12]. This shows, in particular, that the minimum distance conjecture is true for all Schubert divisors such as, for instance, the unique nontrivial Schubert variety in the Klein quadric.

1In fact, in [20] and [7], the Grassmannian and its Schubert subvarieties are viewed as families of projective subspaces of a projective space rather than linear subspaces of a vector space. The two viewpoints are, of course, equivalent. To get (9) from [20, Prop. 15], one has to set ℓ = d + 1, α_{i} = a_{i−1} + 1 and k_{i} = ℓ_{i−1} + 1 for 1 ≤ i ≤ ℓ. A similar substitution has to be made to get (8)

from [7, Thm. 1.1].

As a byproduct of the results in this paper, we see that n_{α} can be expressed in three distinct ways and k_{α} in two. This yields curious combinatorial identities, which may not be easy to prove directly.

Some of the main results of this paper, namely, Theorems 4, 7 and 9, were presented during a talk by the first author at the Conference on Arithmetic, Geometry and Coding Theory (AGCT-8) held at CIRM, Luminy in May 2001. The article [6], written for FPSAC-2003, gives an overview (without proofs) of the results in this paper, and it may be referred to for a more leisurely introduction to this paper.

We end this introduction with the following comment. The Grassmannian is a special instance of homogeneous spaces of the form G/P where G is a semisimple algebraic group and P a parabolic subgroup. Moreover, Schubert varieties also admit a generalization in this context. Thus it was indicated in [3] that the Grassmann and Schubert codes can also be introduced in a much more general setting. It turns out, in fact, that the construction of such general codes was already proposed in the binary case by Wolper in an unpublished paper [21]. The general case, however, needs to be better understood and can be a source of numerous interesting problems.

2. Length of Schubert codes

Fix integers ℓ, m with 1 ≤ ℓ ≤ m. Let I(ℓ, m) be the indexing set with the partial order ≤ defined in the previous section. For β = (β_{1}, …, β_{ℓ}) ∈ I(ℓ, m), let

δ_{β} := ∑_{i=1}^{ℓ}(β_{i} − i) = β_{1} + ⋯ + β_{ℓ} − \frac{ℓ(ℓ + 1)}{2}.

Finally, fix some α ∈ I(ℓ, m) and let C_{α}(ℓ, m) be the corresponding Schubert code.

Quite possibly, the simplest formula for the length n_{α} of C_{α}(ℓ, m) is the one given in the theorem below. This formula is an easy consequence of the well-known cellular decomposition of the Grassmannian, which goes back to Ehresmann [2]. However, it doesn’t seem easy to locate this formula in the literature, and thus, for the sake of completeness, we include here a sketch of the proof.

Theorem 1. The length n_{α} of C_{α}(ℓ, m) or, in other words, the number of 𝔽_{q}- rational points of Ω_{α}, is given by

(10)  n_{α} = ∑_{β≤α} q^{δ_{β}}

where the sum is taken over all β ∈ I(ℓ, m) satisfying β ≤ α.

Proof. Consider, as in the previous section, the subspaces A_{j} spanned by the first j basis vectors, for 1 ≤ j ≤ m. Given any W ∈ G_{ℓ,m}, the numbers r_{j} = dim W ∩ A_{j} have the property^{2} that 0 ≤ r_{j} − r_{j−1} ≤ 1 (where r_{0} = 0, by convention), and, since r_{m} = ℓ, there are exactly ℓ indices where this difference is 1. Thus there is a unique β ∈ I(ℓ, m) such that W is in

2This follows, for example, from the fact that the kernel of the map W ∩ A_{j} → 𝔽_{q}, mapping a vector to its j-th coordinate (with respect to the fixed basis of V), is W ∩ A_{j−1}.

C_{β} := {L ∈ G_{ℓ,m} : dim(L ∩ A_{β_{j}}) = j and dim(L ∩ A_{β_{j}−1}) = j − 1 for 1 ≤ j ≤ ℓ} .

Moreover, for any L ∈ C_{β}, we have: L ∈ Ω_{α} ⇔ β ≤ α. It follows that Ω_{α} is the disjoint union of C_{β} as β varies over the elements of I(ℓ, m) satisfying β ≤ α. Now it suffices to observe that the subspaces in C_{β} are in natural one-to-one correspondence with ℓ × m matrices (over 𝔽_{q}) with 1 in the (i, β_{i})-th spot, and zeros to its right as well as below, for 1 ≤ i ≤ ℓ. □

It may be argued that even though formula (10) is simple and elegant, it may not be very effective in practice in view of the rather intricate summation involved. For example, if Ω_{α} is the full Grassmannian G_{ℓ,m}, then (10) involves \binom{m}{ℓ} summands, while the closed form formula in (1) given by the Gaussian binomial coefficient may be deemed preferable. For an arbitrary α ∈ I(ℓ, m), it is not easy to estimate the number of summands in (10), as may be clear from the results of Section 3. With this in view, we shall now describe another formula for n_{α}, which is far from being elegant but may also be of some interest. First, we need an elementary definition and a couple of preliminary lemmas.

By a consecutive block in an ℓ-tuple β = (β_{1}, …, β_{ℓ}) ∈ I(ℓ, m), we mean an ordered sequence of the form β_{i}, …, β_{j} where 1 ≤ i ≤ j ≤ ℓ and β_{p+1} = β_{p} + 1 for i ≤ p < j. For example, 3, 4 is a consecutive block in (1, 3, 4, 7) as well as in (1, 3, 4, 5) and in (2, 3, 4, 5). Note that any β ∈ I(ℓ, m) always has ℓ consecutive blocks although it may often be regarded as having fewer consecutive blocks.

Lemma 2. Suppose α = (α_{1}, …, α_{ℓ}) has u + 1 consecutive blocks:

α = (α_{1}, …, α_{p_{1}}, α_{p_{1}+1}, …, α_{p_{2}}, …, α_{p_{u−1}+1}, …, α_{p_{u}}, α_{p_{u}+1}, …, α_{ℓ})

so that 1 ≤ p_{1} < ⋯ < p_{u} < ℓ and α_{p_{i}+1}, …, α_{p_{i+1}} are consecutive for 0 ≤ i ≤ u, where by convention, p_{0} = 0 and p_{u+1} = ℓ. Then

Ω_{α} = {W ∈ G_{ℓ,α_{ℓ}} : dim(W ∩ A_{α_{p_{i}}}) ≥ p_{i} for i = 1, …, u}.

Proof. As in the proof of Theorem 1, for any W ∈ G_{ℓ,α_{ℓ}}, we have dim(W ∩A_{j−1}) ≥ dim(W ∩ A_{j}) − 1 for 1 ≤ j ≤ m. Also, dim(W ∩ A_{α_{ℓ}}) ≥ ℓ if and only if W is a subspace of A_{α_{ℓ}}. The desired result is now clear. □

Given any integers a, b, s, t, we define

λ(a, b; s, t) = ∑_{r=s}^{t}(−1)^{r−s}q^{\binom{r−s}{2}}\left[{a − s \atop r − s}\right]_{q}\left[{b − r \atop t − r}\right]_{q}.

Here, for any u, v ∈ ℤ, the Gaussian binomial coefficient \left[{u \atop v}\right]_{q} is defined as in (1)

when 0 ≤ v ≤ u, and 0 otherwise. Thus, if a = s = 0, then λ(a, b; s, t) = \left[{b \atop t}\right]_{q}.

Lemma 3. Let B be a b-dimensional vector space over 𝔽_{q} and G_{t,b} = G_{t}(B) denote the Grassmannian of t-dimensional subspaces of B. Now suppose A is any subspace of B and S is any subspace of A, and we let a = dim A and s = dim S. Then

|{T ∈ G_{t}(B) : T ∩ A = S}| = λ(a, b; s, t).

Proof. Let L_{A} be the poset of all subspaces of A with the partial order given by inclusion. Define functions f, g : L_{A} → ℕ by

f(S) = |{T ∈ G_{t}(B) : T ∩ A = S}| and g(S) = |{T ∈ G_{t}(B) : T ∩ A ⊇ S}|.

It is clear that for any S ∈ L_{A} with dim S = s, we have

g(S) = _{∑_{R∈L_{A}} ; R⊇S}f(R).

On the other hand, for any S as above, we clearly have

(11)  g(S) = |\{T ∈ G_{t}(B) : T ⊇ S\}| = |G_{t−s}(B/S)| = \left[{b − s \atop t − s}\right]_{q}.

Hence, by Möbius inversion applied to the poset L_{A} and the well-known formula for the Möbius function of L_{A} (cf. [17, Ch. 3]), we obtain

f(S) = _{∑_{R∈L_{A}} ; R⊇S}μ(S, R)g(R) = _{∑_{R∈L_{A}} ; R⊇S}(−1)^{dim R−dim S}q^{\binom{dim R−dim S}{2}}\left[{b − r \atop t − r}\right]_{q}.

Since the terms in the last summation depend only on the dimension of the varying subspace R, we may write it as

∑_{r=s}^{a} |\{R ∈ L_{A} : R ⊇ S and dim R = r\}|(−1)^{r−s}q^{\binom{r−s}{2}}\left[{b − r \atop t − r}\right]_{q}.

As in (11), the cardinality of the set appearing in the above summand is readily seen to be \left[{a−s \atop r−s}\right]_{q}. This yields the desired equality. □

Theorem 4. Let u and p_{1}, …, p_{u} be as in Lemma 2. Then the length n_{α} of the Schubert code C_{α}(ℓ, m) is given by

(12)  n_{α} = ∑_{s_{1}=p_{1}}^{α_{p_{1}}} ∑_{s_{2}=p_{2}}^{α_{p_{2}}} ⋯ ∑_{s_{u}=p_{u}}^{α_{pu}} ∏_{i=0}^{u} λ(α_{p_{i}}, α_{p_{i+1}}; s_{i}, s_{i+1})

where, by convention, s_{0} = p_{0} = 0 and s_{u+1} = p_{u+1} = ℓ.

Proof. We use induction on u. If u = 0, i.e., if α_{1}, …, α_{ℓ} are consecutive, then Ω_{α} = G_{ℓ,α_{ℓ}}, and so we know that n_{α} = \left[{α_{ℓ} \atop ℓ}\right]_{q} = λ(0, α_{ℓ}; 0, ℓ). Now suppose that u ≥ 1 and the result holds for all smaller values of u. Then, by Lemma 2, we see that

Ω_{α} = ∐_{S}{T ∈ G_{ℓ,α_{ℓ}} : T ∩ A_{α_{pu}} = S}

where the disjoint union is taken over the set, say Λ_{u}, of all subspaces S of A_{α_{pu}} satisfying dim S ≥ u and dim S ∩ A_{α_{p_{i}}} ≥ p_{i} for 1 ≤ i ≤ u − 1. Hence, by Lemma 3,

n_{α} = |Ω_{α}(𝔽_{q})| = ∑_{s=p_{u}}^{α_{pu}} |{S ∈ Λ_{u} : dim S = s}|λ(α_{p_{u}}, α_{ℓ}; s, ℓ).

But for any s with p_{u} ≤ s ≤ α_{p_{u}}, the set of s-dimensional subspaces in Λ_{u} is precisely the Schubert variety in G_{s,α_{pu}} corresponding to the tuple (α_{1}, …, α_{p_{u}}) with u consecutive blocks. Hence the induction hypothesis applies. □

Remark 5. In the case ℓ = 2, we obviously have u ≤ 1, and the formula given above becomes somewhat simpler. It is not difficult to verify that this agrees with the formula (6) of Hao Chen [1].

Remark 6. As a consequence of the results in this section, we obtain a purely combinatorial identity which equates the right hand sides of (9), (10) and (12). It would be an intriguing problem to prove this without invoking Schubert varieties.

3. Dimension of Schubert codes

Let the notation be as in the beginning of the previous section. Our aim is to give an explicit formula for the dimension k_{α} of the Schubert code C_{α}(ℓ, m). As in the case of Theorem 1, it suffices to appeal to another classical fact about Schubert varieties in Grassmannians, namely, the postulation formula due to Hodge [8]. For our purpose, we use a slightly simpler description of Hodge’s formula, which (together with an alternative proof) is given in [5].

Theorem 7. The dimension k_{α} of the Schubert code C_{α}(ℓ, m) equals the determinant of the ℓ × ℓ matrix whose (i, j)th entry is \binom{α_{j}−j+1}{i−j+1}, i.e.,

(13)  k_{α} = | \begin{matrix}\binom{α_{1}}{1} & 1 & 0 & … & 0 \\ \binom{α_{1}}{2} & \binom{α_{2}−1}{1} & 1 & … & 0 \\ ⋮ & & & & ⋮ \\ \binom{α_{1}}{ℓ} & \binom{α_{2}−1}{ℓ−1} & \binom{α_{3}−2}{ℓ−2} & … & \binom{α_{ℓ}−ℓ+1}{1} \end{matrix} | .

Proof. Recall the abstract description in (4) for the dimension k_{α} of C_{α}(ℓ, m):

k_{α} = |{β ∈ I(ℓ, m) : β ≤ α}|.

By Hodge Basis Theorem (cf. [5, Thm. 1]), we know that a vector space basis for the t-th component, say R_{t}, of the homogeneous coordinate ring of Ω_{α} is indexed by the t-tuples (β^{(1)}, …, β^{(t)}) of elements of I(ℓ, m) satisfying β^{(1)} ≤ ⋯ ≤ β^{(t)} ≤ α. The postulation formula of Hodge gives the Hilbert function h(t) := dim R_{t} (t ∈ ℕ) of this ring. Now, using [5, Lemma 7], we may write

h(t) = det_{1≤i,j≤ℓ} (\binom{t + α_{j} − j}{t + i − j}) for t ∈ ℕ.

By putting t = 1, we get the desired result. □

Remark 8. In the case ℓ = 2, we obviously have

k_{α} = α_{1}(α_{2} − 1) − \binom{α_{1}}{2} = \frac{α_{1}(2α_{2} − α_{1} − 1)}{2}

and if we write α = (m − h − 1, m), then we retrieve the formula (7) of Chen [1].

The determinant in (13) is not easy to evaluate in general. For example, none of the recipes in the rather comprehensive compendium of Krattenthaler [10] seem to be applicable. The following Proposition shows, however, that in a special case a simpler formula can be obtained.

Theorem 9. Suppose α_{1}, …, α_{ℓ} are in an arithmetic progression, i.e., there are c, d ∈ ℤ such that α_{i} = c(i − 1) + d for i = 1, …, ℓ. Let α_{ℓ+1} = cℓ + d = ℓα_{2} + (1 − ℓ)α_{1}. Then

k_{α} = \frac{α_{1}}{ℓ!} ∏_{i=1}^{ℓ−1}(α_{ℓ+1} − i) = \frac{α_{1}}{α_{ℓ+1}} \binom{α_{ℓ+1}}{ℓ}.

Proof. If α_{i} = c(i − 1) + d for i = 1, …, ℓ, then the (i, j)-th entry of the transpose of the ℓ × ℓ matrix in (13) can be written as

\binom{c(i − 1) + d − i + 1}{j − i + 1} = \binom{BL_{i} + A}{L_{i} + j}, where B = 1 − c, L_{i} = 1 − i and A = d.

Now we use formula (3.13) in [10, Thm. 26], which says that for an ℓ × ℓ matrix whose (i, j)-th entry of the form \binom{BL_{i}+A}{L_{i}+j} [where A, B can be indeterminates and the L_{i}’s are integers], the determinant is given by

\frac{∏_{1≤i<j≤ℓ}(L_{i} − L_{j})}{∏_{i=1}^{ℓ}(L_{i} + ℓ)!} ∏_{i=1}^{ℓ} \frac{(BL_{i} + A)!}{((B − 1)L_{i} + A − 1)!} ∏_{i=1}^{ℓ}(A − Bi + 1)_{i−1},

where in the last product we used the shifted factorial notation, viz., (a)_{0} := 1 and (a)_{t} := a(a+1) ⋯ (a+t−1), for t ≥ 1. Substituting B = 1−c, L_{i} = 1−i and A = d and making elementary simplifications, we obtain the desired formula. □

Remark 10. The simplest case, where the above Proposition is applicable is when α_{1}, …, α_{ℓ} are consecutive, i.e., c = 1 and α_{i} = d + i − 1. Notice that in this case, the formula for k_{α} reduces to \binom{d+ℓ−1}{ℓ}. Of course, this is not surprising since Ω_{α} is nothing but the smaller Grassmannian G_{ℓ,d+ℓ−1} in this case. Thus, in this case we also have simpler formulae for n_{α} and δ_{α} and the minimum distance conjecture is true. However, even in this simplest case, the evaluation of the determinant in (13) does not seem obvious. Indeed, here it becomes an instance of the Ostrowski determinant det (\binom{d}{k_{i}−j}) if we take k_{i} = i + 1. A formula for such a determinant and the result that it is positive for increasing {k_{i}} was obtained by Ostrowski [13] in 1964. The case when {k_{i}} are consecutive seems to go back to Zeipel in 1865 (cf. [11, Vol. 3, pp. 448-454]).

An alternative formula for the dimension k_{α} of C_{α}(ℓ, m) can be derived using results of the previous section. To this end, we begin by observing that the dimension k of the q-ary Grassmann code C(ℓ, m) doesn’t depend on q, and bears the following relation to the length n = n(q) of C(ℓ, m):

(14)  lim_{q→1} n(q) = k or, in other words, lim_{q→1} \left[{m \atop ℓ}\right]_{q} = \binom{m}{ℓ}.

Much has been written on this limiting formula in combinatorics literature. For example, a colourful, albeit mathematically incorrect, way to state it would be to say that the (lattice of) subsets of an m-set is the same as the (lattice of) subspaces of an m-dimensional vector space over the field of one element! In the proposition below, we observe that a similar relation holds in the case of Schubert codes, and, then, use this relation to obtain the said alternative formula for k_{α}.

Proposition 11. The dimension k_{α} of the q-ary Schubert code C_{α}(ℓ, m) is independent of q and is related to the length n_{α} = n_{α}(q) of C_{α}(ℓ, m) by the formula

(15)  lim_{q→1} n_{α}(q) = k_{α}.

Consequently, if u and p_{1}, …, p_{u} be are as in Lemma 2, then

(16)  k_{α} = ∑_{s_{1}=p_{1}}^{α_{p_{1}}} ∑_{s_{2}=p_{2}}^{α_{p_{2}}} ⋯ ∑_{s_{u}=p_{u}}^{α_{pu}} ∏_{i=0}^{u} \binom{α_{p_{i+1}} − α_{p_{i}}}{s_{i+1} − s_{i}},

where, by convention, s_{0} = p_{0} = 0 and s_{u+1} = p_{u+1} = ℓ.

Proof. The limiting formula (15) follows from the abstract description in (4) of k_{α} and Theorem 1. Further, (16) will follow from Theorem 4 if we show that for any integer parameters a, b, s, t, we have

lim_{q→1} λ(a, b; s, t) = \binom{b − a}{t − s}.

But, in view of (14), this is equivalent to proving the binomial identity

∑_{j≥0}(−1)^{j}\binom{a − s}{j}\binom{b − s − j}{t − s − j} = \binom{b − a}{t − s}.

This identity is trivial if t < s, and if t ≥ s, it follows easily if, after expanding by the binomial theorem, we compare the coefficients of X^{t−s} in the identity

(1 − X)^{a−s}(1 − X)^{t−b−1} = (1 − X)^{a−b+t−s−1}

and observe that for any integers M and N, we have \binom{−N−1}{M} = (−1)^{M} \binom{N+M}{M}. □

Remark 12. As a consequence of the results in this section, we obtain a purely combinatorial identity which equates the right hand sides of (13) and (16). It would be an intriguing problem to prove this without invoking Schubert codes.

While one would like to construct codes having both the rate k/n and the relative distance d/n as close to 1 as possible, the two requirements are in conflict with each other. For Schubert codes, this conflict manifests itself in a peculiar way:

Corollary 13. Let R = R(q) and Δ = Δ(q) denote, respectively, the rate and the relative distance of the q-ary Schubert code C_{α}(ℓ, m). Then, we have

lim_{q→1} R(q) = 1 and lim_{q→∞} Δ(q) = 1.

Proof. The limiting formula for the rate is immediate from Proposition 11. As for the relative distance, it suffices to observe that using Theorem 1, we have

lim_{q→∞} \frac{U_{α}(q)}{n_{α}(q)} = 1 and lim_{q→∞} \frac{L_{α}(q)}{n_{α}(q)} = 1,

where U_{α}(q) := q^{δ_{α}} denotes the upper bound (cf. [3, Prop. 4]) for the minimum distance of C_{α}(ℓ, m), while L_{α}(q) denotes the lower bound given by (8). □

4. Minimum Distance Conjecture for Schubert Divisors

The notation in this section will be as in the Introduction and at the beginning of Section 2. To avoid trivialities, we may tacitly assume that 1 < ℓ < m. Further, we let

θ := (m − ℓ + 1, m − ℓ + 2, …, m) and η := (m − ℓ, m − ℓ + 2, …, m).

Note that with respect to the partial order ≤, defined in the Introduction, θ is the unique maximal element of I(ℓ, m) whereas η the unique submaximal element. Moreover, by (4), we have

k_{θ} = k := \binom{m}{ℓ} and k_{η} = k − 1; also δ_{θ} = δ := ℓ(m − ℓ) and δ_{η} = δ − 1.

Thus, in view of Theorem 1, we have

(17)  n_{θ} = |Ω_{θ}| = |G_{ℓ,m}| = \left[{m \atop ℓ}\right]_{q} and n_{η} = |Ω_{η}| = \left[{m \atop ℓ}\right]_{q} − q^{δ}.

Indeed, Ω_{θ} is the full Grassmannian G_{ℓ,m}, whereas Ω_{η} is the unique subvariety of G_{ℓ,m} of codimension one, which is often referred to as the Schubert divisor in G_{ℓ,m}.

Theorem 14. If η := (m − ℓ, m − ℓ + 2, …, m) so that δ_{η} = δ − 1, then

(18) d_{r} (C_{η}(ℓ, m)) = q^{δ−1} + q^{δ−2} + ⋯ + q^{δ−r} for 1 ≤ r ≤ max{ℓ, m − ℓ}.

In particular, d_{1} (C_{η}(ℓ, m)) = q^{δ_{η}}, and so the minimum distance conjecture is valid in this case.

Proof. Let r be a positive integer and H_{θ} = {p = (p_{β}) ∈ ℙ^{k−1} = ℙ(∧^{ℓ}V) : p_{θ} = 0} be the hyperplane given by the vanishing of the Plücker coordinate corresponding to θ. Note that Ω_{η} = G_{ℓ,m} ∩ H_{θ}. Now, if Π is a linear subspace of ℙ^{k_{η}−1} = ℙ (H_{θ}) of codimension r, then as a linear subspace of ℙ^{k−1}, it is of codimension r + 1. Therefore,

|Ω_{η} ∩ Π| = |G_{ℓ,m} ∩ H_{θ} ∩ Π| = |G_{ℓ,m} ∩ Π| ≤ |G_{ℓ,m}| − d_{r+1} (C(ℓ, m)) .

Hence, in view of (17), if r ≤ max{ℓ, m − ℓ}, then by (3), we see that

d_{r} (C_{η}(ℓ, m)) = |Ω_{η}| − max_{codim Π=r} |Ω_{η} ∩ Π| ≥ |Ω_{η}| − |G_{ℓ,m}| + q^{δ} + q^{δ−1} + ⋯ + q^{δ−r}.

Thus, to complete the proof it suffices to exhibit a codimension r linear subspace Π of ℙ^{k_{η}−1} = ℙ (H_{θ}) such that |Ω_{η} ∩ Π| = |Ω_{η}| − (q^{δ−1} + q^{δ−2} + ⋯ + q^{δ−r}). To this end, we use the notion of a close family introduced in [3] and [4], and some results from [3].

First, suppose m − ℓ ≥ ℓ so that r ≤ m − ℓ. Now let

α^{(j)} = (m − ℓ + 2 − j, m − ℓ + 2, m − ℓ + 3, …, m), for j = 1, …, r + 1,

and let Λ = {α^{(1)}, …, α^{(r+1)}}. Then Λ is a subset of I(ℓ, m) and a close family^{3}, in the sense of [3, p. 126]. Note that α^{(1)} = θ and α^{(2)} = η. Thus if Π denotes the linear subspace of ℙ^{k_{η}−1} = ℙ (H_{θ}) defined by the vanishing of the Plücker coordinates corresponding to α^{(2)}, …, α^{(r+1)}, and Π′ denotes the linear subspace of ℙ^{k−1} defined by the vanishing of the Plücker coordinates corresponding to α^{(1)}, …, α^{(r+1)}, then codim Π′ = r + 1, and using [3, Prop. 1], we obtain

|Ω_{η} ∩ Π| = |G_{ℓ,m} ∩ Π′| = \left[{m \atop ℓ}\right]_{q} − q^{δ} − q^{δ−1} − ⋯ − q^{δ−r}.

Thus, in view of (17), it follows that Π is a subspace of ℙ^{k_{η}−1} = ℙ (H_{θ}) of codimension r with the desired property.

On the other hand, suppose ℓ ≥ m − ℓ. Then we let

α^{(j)} = (m − ℓ, m − ℓ + 1, …, { \atop m − ℓ + j − 1}, …, m), for j = 1, …, r + 1,

where { \atop m − ℓ + j − 1} indicates that the element m − ℓ + j − 1 is to be removed. Once again, for r ≤ ℓ, Λ = {α^{(1)}, …, α^{(r+1)}} is a subset of I(ℓ, m) and a close family with α^{(1)} = θ. Hence we can proceed as before and apply [3, Prop. 1] to obtain the desired formula for d_{r} (C_{η}(ℓ, m)). □

Remark 15. An obvious analogue of the inductive argument in the above proof seems to fail for Schubert subvarieties of codimension 2 or more. For example, in G_{3,6} the subvariety Ω_{α} corresponding to α = (3, 4, 6) is of codimension 2. However, Ω_{α} is not the intersection of G_{3,6} with two Plüker coordinate hyperplanes but with four of them [viz., those corresponding to (j, 5, 6) for 1 ≤ j ≤ 4]. Thus, to determine d_{1}(C_{α}(3, 6)), we should know d_{5}(C(3, 6)). But we know d_{r}(C(3, 6)) only for r ≤ max{3, 6 − 3} + 1 = 4. The argument will, however, work for Schubert varieties of codimension 2 in G_{2,m} because one of these two varieties will be a lower order Grassmannian while the other is a section by just 3 hyperplanes, and assuming, as we may, that m > 4, we can apply formula (3) and some results from [3]. We leave the details to the reader. In any case, we know from the work of Hao Chen [1] and Guerra-Vincenti [7] that the minimum distance conjecture is true when ℓ = 2.

3Two elements α = (α_{1}, …, α_{ℓ}) and β = (β_{1}, …, β_{ℓ}) in I(ℓ, m) are said to be close if they differ in a single coordinate, that is, | {α_{1}, …, α_{ℓ}} ∩ {β_{1}, …, β_{ℓ}} | = ℓ − 1. A subset of I(ℓ, m) is called a close family if any two distinct elements in it are close.

Acknowledgments

A part of this work was done when the first author was visiting the Institut de Mathématiques de Luminy (IML), Marseille during May-June 1999. Partial support for this visit from the Commission on Development and Exchanges (CDE) of the International Mathematical Union (IMU), and the warm hospitality of IML is gratefully acknowledged. Thanks are also due to Gilles Lachaud and Serge Vlăduţ for useful discussions, to Christian Krattenthaler for some helpful correspondence concerning determinant evaluations, and to Lucio Guerra and Rita Vincenti for a week long visit in June 2002 to the University of Perugia during which the first author learned of their recent results. We are also grateful to a vicious landlady, whom we do not name here, and more so to a kind-hearted one, Mme C. Cerisier, whose actions led us to share an apartment in Marseille in June 1996, where this work began.

References

[1] H. Chen, On the minimum distance of Schubert codes, IEEE Trans. Inform. Theory, 46 (2000), 1535–1538.

[2] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. of Math. (2) 35 (1934), 396–443.

[3] S. R. Ghorpade and G. Lachaud, Higher weights of Grassmann codes, in: “Coding Theory, Cryptography and Related Areas” (Guanajuato, 1998), Springer-Verlag, Berlin/Heidelberg, 2000, pp. 122–131.

[4] S. R. Ghorpade and G. Lachaud, Hyperplane sections of Grassmannians and the number of MDS linear codes, Finite Fields Appl. 7 (2001), 468–506.

[5] S. R. Ghorpade, A note on Hodge’s postulation formula for Schubert varieties, in: “Geometric and Combinatorial Aspects of Commutative Algebra” (Messina, 1999), Marcel Dekker, New York, 2001, pp. 211–220.

[6] S. R. Ghorpade and M. A. Tsfasman, Classical varieties, codes and combinatorics, Proc. 15th Int’l Conf. on Formal Power Series and Algebraic Combinatorics (Vadstena, Sweden, 2003).

[7] L. Guerra and R. Vincenti, On the linear codes arising from Schubert varieties, Des. Codes Cryptogr. 33 (2004), 173–180.

[8] W. V. D. Hodge, Some enumerative results in the theory of forms, Proc. Cambridge Phil. Soc. 39 (1943), 22–30.

[9] W. V. D. Hodge and D. Pedoe, “Methods of Algebraic Geometry, Vol. II”, Cambridge Univ. Press, Cambridge, 1952.

[10] C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Article B42q, 67 pp.

[11] T. Muir, “The Theory of Determinants in the Historical Order of Development”, 4 Vols., Macmillan, London, 1906–1923.

[12] D. Yu. Nogin, Codes associated to Grassmannians, in: “Arithmetic, Geometry and Coding Theory” (Luminy, 1993), R. Pellikaan, M. Perret, S. G. Vlăduţ, Eds., pp. 145–154, Walter de Gruyter, Berlin/New York, 1996.

[13] A. M. Ostrowski, On some determinants with combinatorial numbers, J. Reine Angew. Math. 216 (1964), 25-30.

[14] C. T. Ryan, An application of Grassmannian varieties to coding theory, Congr. Numer. 57 (1987), 257–271.

[15] C. T. Ryan, Projective codes based on Grassmann varieties, Congr. Numer. 57 (1987), 273–279.

[16] C. T. Ryan and K. M. Ryan, The minimum weight of Grassmannian codes C(k, n), Disc. Appl. Math. 28 (1990), 149–156.

[17] R. P. Stanley, “Enumerative combinatorics, Vol. I”, Wadsworth & Brooks/Cole, Monterey, CA, 1986.

[18] M. A. Tsfasman and S. G. Vlăduţ, “Algebraic Geometric Codes”, Kluwer, Amsterdam, 1991.

[19] M. A. Tsfasman and S. G. Vlăduţ, Geometric approach to higher weights, IEEE Trans. Inform. Theory 41 (1995), 1564–1588.

[20] R. Vincenti, On some classical varieties and codes, Rapporto Tecnico 20/2000, Dipartimento di Matematica e Informatica, Universitá degli Studi di Perugia, Italy.

[21] J. Wolper, Linear Codes from Schubert varieties, Issac Newton Institute of Mathematical Sciences, Cambridge, Preprint No. NI96048 (1996).

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: srg@math.iitb.ac.in

Institut de Mathématiques de Luminy, Case 907, 13288 Marseille, France, and Independent University of Moscow, and Dorbushin Math. Lab., Institute for Information Transmission Problems, Moscow.

E-mail address: tsfasman@iml.univ-mrs.fr