CLASSICAL VARIETIES, CODES AND COMBINATORICS

SUDHIR R. GHORPADE AND MICHAEL A. TSFASMAN

1. Introduction

For over two decades, the theory of linear (error correcting) codes has extensive and fruitful interaction with the theory of algebraic curves. The study of linear codes associated to higher dimensional algebraic varieties over finite fields is relatively new. However, given the richness of the geometric objects at our disposal, it promises to play a useful role in coding theory. Moreover, such a study often seems to lead to questions that could also be of interest in combinatorics and algebraic geometry.

In this article we attempt to illustrate these remarks by considering linear codes associated to Schubert varieties in Grassmannians. Our main results are presented here only with a brief idea of proofs; for details, we refer to [7]. To motivate and to give a perspective, we include a quick outline of some background material and known results.

2. Linear Codes and Projective Systems

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 article 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} .

The first named author was partially supported by the IRCC grant 97IR012 from IIT Bombay. The second named author was partially supported by the RFBR Grants 99-01-01204, 02-01-01041 and 02-01-22005.

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.

An alternative way to describe codes is via the language of projective systems introduced in [21]. 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}.

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. For more details concerning projective systems and a proof of the above mentioned one-to-one correspondence, we refer to [21] and [22].

3. Grassmann Codes and Schubert Codes

Perhaps the most basic example of a projective algebraic variety over 𝔽_{q} 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], [11]), 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 [17, 18, 19] in the binary case and by Nogin [14] 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 [14]:

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

In fact, Nogin [14] 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 [9]; 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 [23], 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_{ℓ} = ℓ.

Now, we are ready to state our main results.

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

1In fact, in [23] and [9], 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 [23, 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 [9, Thm. 1.1].

Quite possibly, the simplest formula for the length n_{α} of C_{α}(ℓ, m) is the one given in the theorem below. This is essentially an easy consequence of the well-known cellular decomposition of the Grassmannian, which goes back to Ehresmann [2].

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 over all β ∈ I(ℓ, m) satisfying β ≤ α.

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) for n may be deemed preferable. For an arbitrary α ∈ I(ℓ, m), it is not easy to estimate the number of summands in (10), as will be clear from the results in Section 5. 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 some notation.

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

Theorem 2. Let α = (α_{1}, …, α_{ℓ}) have 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 the length n_{α} of the Schubert code C_{α}(ℓ, m) is given by

(11)  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} = ℓ.

The key idea in the proof of the above theorem is to use an inductive argument together with Möbius inversion applied to the poset of subspaces of a finite dimensional vector space over 𝔽_{q}, and the well-known formula for the Möbius function of this poset (cf. [20, Ch. 3]).

Remark 3. 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 4. 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 (11). It would be an intriguing problem to prove this without invoking Schubert varieties.

5. Dimension of Schubert codes

Let the notation be as in the beginning of the previous section. An explicit formula for the dimension k_{α} of the Schubert code C_{α}(ℓ, m) is given by the following

Theorem 5. 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.,

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

The key idea in the proof of this theorem is to use the postulation formula for Schubert varieties in Grassmannians, which goes back to Hodge [10] (see also [5]).

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

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

Setting α = (m − h − 1, m), we retrieve the formula (7) of Chen [1].

The determinant in (12) is, in general, not easy to evaluate. For example, none of the recipes in the rather comprehensive compendium of Krattenthaler [12] seems applicable. However, in a special case, a much simpler formula can be obtained.

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

k_{α} = \frac{α_{1}}{α_{ℓ+1}} \binom{α_{ℓ+1}}{ℓ}, where α_{ℓ+1} := cℓ + d = ℓα_{2} + (1 − ℓ)α_{1}.

The key idea in the proof of the above theorem is to use formula (3.13) from [12, Thm. 26].

Remark 8. The simplest case where the above Proposition is applicable is when α_{1}, …, α_{ℓ} are consecutive, i.e., c = 1 and α_{i} = d + i − 1. Then, the formula for k_{α} reduces to \binom{d+ℓ−1}{ℓ}. Of course, this is not surprising because in this case Ω_{α} is nothing but the smaller Grassmannian G_{ℓ,d+ℓ−1}. So, here 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 (12) does not seem obvious. Indeed, 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 [15] in 1964. The case when {k_{i}} are consecutive seems to go back to Zeipel in 1865 (cf. [13, 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) does not depend on q, and bears the following relation to the length n = n(q) of C(ℓ, m):

(13)  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! It turns out that a similar relation holds in the case of Schubert codes. This can, then, be used to obtain the said alternative formula for k_{α}: Proposition 9. The dimension k_{α} of the q-ary Schubert code C_{α}(ℓ, m) is independent of q and is related to its length n_{α} = n_{α}(q) by the formula

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

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

(15)  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} = ℓ. Remark 10. As a consequence of the results in this section, we obtain a purely combinatorial identity which equates the right hand sides of (12) and (15). 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 11. Let R = R(q) and Δ = Δ(q) denote, respectively, the rate and the relative distance of the q-ary Schubert code C_{α}(ℓ, m). Then

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

This corollary is a consequence of Proposition 9 together with Theorem 1 and some results from [3].

6. Minimum Distance Conjecture for Schubert Divisors

As remarked earlier, the minimum distance conjecture for the unique nontrivial Schubert variety in the Klein quadric G_{2,4}, namely Ω_{(2,4)}, was proved in [23]. The result in [1] and [9] for Schubert varieties in G_{2,m} generalizes this simple example. Another natural generalization is the family of Schubert varieties of codimension one in G_{ℓ,m} for arbitrary ℓ and m. It turns out that the conjecture can also be proved, in the affirmative, for this other generalization. However, the general case of the minimum distance conjecture remains open.

Let us, as before, fix integers ℓ, m with 1 ≤ ℓ ≤ m, and for any β = (β_{1}, …, β_{ℓ}) ∈ I(ℓ, m), let δ_{β} = ∑_{i=1}^{ℓ}(β_{i} − i). 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 Section 3, θ is the unique maximal element of I(ℓ, m), whereas η the unique submaximal element. Moreover δ_{θ} = δ := ℓ(m − ℓ) and δ_{η} = δ − 1. Thus, Ω_{θ} 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. For 1 ≤ r ≤ max{ℓ, m − ℓ}, we have

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

In particular, d (C_{η}(ℓ, m)) = q^{δ_{η}}, i.e., the minimum distance conjecture is valid in this case.

The key idea in the proof of this theorem is to use the notion of a close family introduced in [3] and [4], and some results from [3].

7. Related Developments

Just as a Schubert variety is a natural generalization of the Grassmannian, another natural generalization is the variety of partial flags. These are defined as follows. Let V be a vector space of dimension m over 𝔽_{q}. Let \underline{ℓ} = (ℓ_{1}, …, ℓ_{s}) be a sequence of integers such that 0 < ℓ_{1} < ⋯ < ℓ_{s} < m. A partial flag of dimension \underline{ℓ} is a sequence (V_{1}, …, V_{s}) of subspaces of V such that V_{1} ⊂ ⋯ ⊂ V_{s} and dim V_{i} = ℓ_{i} for 1 ≤ i ≤ s. Let F\underline{ℓ}(V) denote the set of partial flags of dimension \underline{ℓ}. Note that if s = 1, then F\underline{ℓ}(V) is the Grassmannian Gr_{ℓ_{1}}(V). In general, F\underline{ℓ}(V) embeds naturally into a product of Grassmannians, and hence into a product of projective spaces via the Plücker embeddings, and consequently, into a large projective space via the Segre embedding. As such, it is a projective variety defined over 𝔽_{q} and gives rise to a linear code, which we denote by C(\underline{ℓ}; m) or C(ℓ_{1}, …, ℓ_{s}; m). The basic parameters n, k and d of this code were determined by Rodier [16] when s = 2 and \underline{ℓ} = (1, m − 1). In effect, he showed:

n = \frac{(q^{m} − 1)(q^{m−1} − 1)}{(q − 1)^{2}}, k = m^{2} − 1 and d = q^{2m−3} − q^{m−2}.

It turns out that it is possible to extend the first two results so as to obtain formulae for n and k in the general case. The general formula for n is, in essence, known for many years and can be gleaned, for example, from [6, Sec. 2]. The general formula for k is a little more involved and uses ideas from representation theory. These results about the length and dimension of codes associated to flag varieties are expected to appear in [8]. However, for the minimum distance of these codes, nothing seems to be known, in general, even conjecturally.

Finally, we remark that Grassmannians and flag varieties are 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 generalization in this context. Thus it was indicated in [3] that codes such as 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 [24]. The general case, however, needs to be better understood and can be a source of numerous interesting problems.

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 G. Lachaud, Number of solutions of equations over finite fields, and a conjecture of Lang and Weil, in: Number Theory and Discrete Mathematics (Chandigarh, 2000), Birkhäuser, Basel, 2002, pp. 269-291.

[7] S. R. Ghorpade and M. A. Tsfasman, Schubert varieties, linear codes and enumerative combinatorics, Prétirage n^{o} 2003-04, Institut de Mathématiques de Luminy, Marseille, 2003.

[8] S. R. Ghorpade, Flag varieties and error correcting codes, in preparation.

[9] L. Guerra and R. Vincenti, On the linear codes arising from Schubert varieties, to appear in: Des. Codes Cryptogr.

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

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

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

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

[14] D. Yu. Nogin, Codes associated to Grassmannians, in: “Arithmetic, Geometry and Coding Theory” (Luminy, 1993), Walter de Gruyter, Berlin/New York, 1996, pp. 145–154.

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

[16] F. Rodier, Codes from flag varieties over a finite field, J. Pure Appl. Algebra 178 (2003) 203–214.

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

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

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

[20] R. Stanley, “Enumerative combinatorics, Vol. I”, Revised Ed., Cambridge Univ. Press, Cambridge, 1997.

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

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

[23] R. Vincenti, On some classical varieties and codes, Proc. Combinatorics 2000 (Gaeta, Italy), to appear in: Ital. J. Pure Appl. Math.

[24] 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
URL: http://www.math.iitb.ac.in/∼srg

Institut de Mathématiques de Luminy, Case 907, 13288 Marseille, France,

and Independent University of Moscow, and Dorbushin Math. Lab., Institute for Information Transmission Prob-

lems, Moscow.

E-mail address: tsfasman@iml.univ-mrs.fr
URL: http://www.aha.ru/∼tsfasman