BASIC PARAMETERS OF SCHUBERT CODES

SUDHIR R. GHORPADE AND MICHAEL A. TSFASMAN

Abstract. Linear error correcting codes associated to Schubert varieties in Grassmannians were introduced by Ghorpade and Lachaud [3] as a natural generalization of the Grassmann codes, which have previously been studied by Ryan [14, 15] and Nogin [12]. For these codes, called Schubert codes, an upper bound for the minimal distance is given in [3], and it is conjectured that this bound equals the minimal distance. This conjecture has been proved in the affirmative in some special cases by Hao Chen [1] and independently, by Guerra and Vincenti [6]. In this paper, we give explicit formulae for the length and the dimension of arbitrary Schubert codes and also prove the Minimal Distance Conjecture in the affirmative for the codes associated to the Schubert divisors.

1. Introduction

A projective system is a set X of n points (possibly with multiplicities) in the projective space ℙ^{k−1} over the finite field 𝔽_{q} with q elements; we call X to be nondegenerate if these n points are not contained in a hyperplane. A nondegenerate projective system of n points in ℙ^{k−1} corresponds naturally to a nondegenerate linear [n, k]_{q}-code. Moreover, this correspondence is one-to-one up to suitable notions of equivalence (cf. [18] for details).

The idea of a projective system goes back to Manin and Vlăduţ [10], and it has been extensively used by Tsfasman and Vlăduţ [18]. 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 in a projective space (cf. [3], [8] for details), and this is known to be nondegenerate. So 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

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

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

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

Schubert variety.

Date: September 19, 2002.

Key words and phrases. Grassmannian, linear codes, minimal distance, projective system,

The first author was partially supported by a ‘Career Award’ grant from AICTE, New Delhi and an IRCC grant from IIT Bombay.

The second author was partially supported by the RFBR Grants 99-01-01204 and 02-01-01041.

In fact, Nogin [12] also determined some of the higher weights (cf. [19] for the definition and basic facts about higher weights) of C(ℓ, m), and these are given by

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

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 code is denoted by C_{α}(ℓ, m), and it corresponds to 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

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

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

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

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

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

We may refer to this equality as the Minimal Distance Conjecture (for Schubert codes C_{α}(ℓ, m)). Notice that when α = (m − ℓ + 1, …, m − 1, m), then Ω_{α} = G_{ℓ,m} and thus in this case (5) is an immediate consequence of (2).

The Minimal 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_{1}(C_{α}(ℓ, m)) = q^{δ_{α}} = q^{2m−h−4}

and moreover,

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} (6)

and

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

An alternative proof of the Minimal Distance Conjecture as well as the weight distribution of the codewords in the case ℓ = 2 was obtained independently by Guerra and Vincenti [6]; in the same paper, they prove also the following lower bound for d_{1}(C_{α}(ℓ, m)) in the general case.

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

In an earlier paper, Vincenti [20], partly in collaboration with Guerra, verified the Minimal 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 more crude than (8), and also proved the following formula^{1} for the length of C_{α}(ℓ, m).

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})} (9)

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 minimal 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 Minimal Distance Conjecture is true for all Schubert divisors such as, for instance, the unique nontrivial Schubert variety in the Klein quadric. Some of the main results of this paper, namely, Theorems 4, 6 and 8, 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.

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], and he suggests that the family of (generalized) Schubert codes is quite good from the point of view of Coding Theory. The general case, however, needs to be better understood and can be a source of numerous open 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 any β = (β_{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 we include here a sketch of the proof for the sake of completeness.

1In fact, in [20] and [6], 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 obtain (8) from [6, Thm. 1.1].

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

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

where the sum is 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 that 0 ≤ r_{j} − r_{j−1} ≤ 1, and, since r_{ℓ} = ℓ, there are exactly ℓ indices where this difference is 1. Thus there is a unique β ∈ I(ℓ, m) such that W is in

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 practise in view of the rather intricate summation that is involved there. 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) and this will be clear from the results in 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 a couple of preliminary lemmas.

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}} is 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.^{2} Also, dim(W ∩ A_{α_{ℓ}}) ≥ ℓ if and only if W is a subspace of 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).

2This follows, for example, because the map W ∩ A_{j} → 𝔽_{q} mapping a vector to its j-th coordinate (w.r.t. the fixed basis of V) has kernel W ∩ A_{j−1}.

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

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

Hence, by Mobiüs inversion applied to the poset L_{A} and the well-known formula for the Mobiüs 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

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}) (12)

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 u ≥ 1 and the result holds for 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].

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 length 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 [7]. For our purpose, we use a slightly simpler description of Hodge’s formula, which (together with an alternative proof) is given in [5].

Theorem 6. The dimension k_{α} of the Schubert code C_{α}(ℓ, m) is given by the ℓ × ℓ determinant

k_{α} = det_{1≤i,j≤ℓ} (\binom{α_{j} − j + 1}{i − j + 1}) = | \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} | . (13)

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

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

From the 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 7. 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 [9] seem to be applicable. The following Proposition shows, however, that in a special case a simpler formula can be obtained.

Theorem 8. Suppose α_{1}, …, α_{ℓ} are in 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 [9, 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 9. 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 Minimal 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 when the k_{i}’s are increasing was obtained by Ostrowski [13] in 1964. However, the case when the k_{i}’s 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 some 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 the literature on Combinatorics. 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 10. 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

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

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

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}}, (16)

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 Binomial Theorem, we compare the coefficient 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}.

While one usually likes to construct codes having both the rate k/n as well as the relative distance d/n as close to 1 as possible, the two requirements are often in conflict with each other. The following Corollary show that this conflict is perhaps best illustrated by the Schubert codes.

Corollary 11. 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 10. 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 minimal distance of C_{α}(ℓ, m), while L_{α}(q) denotes the lower bound given by (8).

4. Minimal 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 w.r.t 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

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

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 12. With notations as above, we have

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

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

Proof. Let 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, and Π̂ the corresponding subspace of ℙ^{k−1} = ℙ(∧^{ℓ}V) [defined by the same linear equations], then Π′ := Π̂ ∩ H_{θ} is a linear subspace of ℙ^{k−1} of codimension r + 1. Therefore,

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

Now, 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 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}.

This, 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 13. 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 4 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 [6] that the Minimal Distance Conjecture is true when ℓ = 2.

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 of the International Mathematical Union, and the warm hospitality of IML is gratefully acknowledged. Thanks are also due 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.

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, Mexico, 1998), J. Buchmann, T. Hoeholdt, H. Stichtenoth and H. Tapia-Recillas Eds., 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, Italy, 1999), J. Herzog and G. Restuccia Eds., Lect. Notes in Pure and Appl. Math. Vol. 217, Marcel Dekker, New York, 2001, pp. 211–220.

[6] L. Guerra and R. Vincenti, On the linear codes arising from Schubert varieties, preprint, January 2002.

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

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

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

[10] Yu. I. Manin and S. G. Vlăduţ, Linear codes and modular curves, J. Soviet Math. 30 (1985), 2611–2643.

[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. 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, Proc. Combinatorics 2000 (Gaeta, Italy), to appear in: Ital. J. Pure Appl. Math.

[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