Higher Weights of Grassmann Codes

Sudhir R. Ghorpade^{1}^{,}^{⋆} and Gilles Lachaud^{2}

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

                          srg@math.iitb.ernet.in

2 Équipe “Arithmétique et Théorie de l’Information” Institut de Mathématiques de Luminy Luminy Case 907, 13288 Marseille, Cedex 9, France

                         lachaud@iml.univ-mrs.fr

Abstract. Using a combinatorial approach to studying the hyperplane sections of Grassmannians, we give two new proofs of a result of Nogin concerning the higher weights of Grassmann codes. As a consequence, we obtain a bound on the number of higher dimensional subcodes of the Grassmann code having the minimum Hamming norm. We also discuss a generalization of Grassmann codes.

1 Introduction

Let C be linear [n, k]_{q}–code, that is, a k-dimensional subspace of the n-dimensional vector space 𝔽_{q}^{n} over the finite field 𝔽_{q} with q elements. Given any (linear) subspace D of 𝔽_{q}^{n}, one defines (cf. [14]) the Hamming norm of D as

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

Given r ≥ 1, the r-th higher weight of the code C is defined by

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

Note that d_{1} = d_{1}(C) is the classical Hamming weight or the minimum distance of C. The notion of higher weights was first introduced by V. Wei in [15] and, besides being a natural generalization of Hamming weights, it has found a number of applications in Cryptography and Coding Theory. For a survey of this topic and a detailed bibliography, we refer to [14].

In this paper, we consider the so called Grassmann codes, which were introduced, and studied in a series of papers (cf. [8]– [12]) by C. Ryan and K. Ryan in the binary case (q = 2) and later by D. Nogin [7] in the general case. These codes may be viewed as a generalization of Reed-Muller codes. In [7], Nogin has shown that the higher weights d_{r} of the Grassmann code C(ℓ, m) satisfy the

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

Griesmer-Wei bound for r ≤ max{ℓ, m − ℓ} + 1. One of the main aims of this paper is to give an alternate, short proof of this result of Nogin. Our approach is based on using the Plücker embedding of the Grassmannian and a classical and elementary result concerning the same. This approach has turned out to be quite fruitful elsewhere in the study of MDS codes (cf. [1]) and it seems conceivable that this may also be helpful in studying a possibly far-reaching generalization of the Grassmann codes that is proposed in Section 5 of this paper. Besides the abovementioned alternate, short proof of Nogin’s result, we also indicate how, using a certain combinatorial structure theorem proved in [1], we can obtain a yet another proof. This second proof of Nogin’s result on higher weights of Grassmann codes C(ℓ, m) is arguably more ‘natural’ in the sense that, unlike in Nogin’s proof and our first proof, one does not have to pass to the dual Grassmannian in order to assume something like m − ℓ ≥ ℓ. In fact, this ‘natural’ proof makes it transparent why a quantity such as “max{ℓ, m − ℓ} + 1” should appear, and, moreover, one can also obtain as a corollary, a bound on the number of r-dimensional subcodes of C(ℓ, m) with minimum Hamming norm, for r ≤ max{ℓ, m − ℓ} + 1.

This paper is organized as follows. In Section 2 below, we collect some preliminaries concerning projective systems and Grassmannians. In Section 3, we recall a basic fact about Grassmannians and deduce some results for the number of 𝔽_{q}-rational points of sections of Grassmannians by coordinate hyperplanes. These are applied to give two proofs of Nogin’s result on higher weights in Section 4. Finally, in Section 5, we discuss a possible generalization of the Grassmann codes, make a conjecture about the minimum distance of these general codes, and prove a partial result towards this conjecture by using the techniques of Section 3. It may be remarked that the methods used in Sections 3 and 4 are similar to those in [1]. Also, a few results (Corollary 1, for example) are analogous to those in [1] but the proofs here are somewhat different. At any rate, it seemed desirable that for an alternate proof which is claimed to be ‘short’, the exposition here should be reasonably self-contained.

A part of this work was done when the first author was visiting the Institut de Mathématiques de Luminy (IML) in Marseille for a few months during 1997 and 1998. He would like to use this opportunity to thank the IML for its hospitality and the CNRS of France for its support. Thanks are also due to Michael Tsfasman for a number of helpful discussions, and to Hao Chen for his comments on a preliminary version of this paper.

2 Preliminaries

For studying, or even defining, the Grassmann codes, it is convenient to use the language of projective systems due to Tsfasman and Vlăduţ. Thus, we begin by briefly recalling some basic aspects of this terminology. For details, one may refer to [13], [14].

An [n, k]_{q}–projective system is a collection of n not necessarily distinct points in the (k − 1)-dimensional projective space ℙ_{𝔽_{q}}^{k−1} over 𝔽_{q}. It is called nondegenerate if these n points are not contained in any hyperplane. Incidentally, a linear [n, k]_{q}–code C ⊆ 𝔽_{q}^{n} is called nondegenerate if C is not contained in any coordinate hyperplane. One has a natural notion of equivalence of projective systems as well as of linear codes. There is a natural one-to-one correspondence between the equivalence classes of nondegenerate [n, k]_{q}–projective systems and the equivalence classes of nondegenerate linear [n, k]_{q}–codes. Under this correspondence, if X is an [n, k]_{q}–projective system and C is the corresponding code, then the nonzero codewords of C correspond to hyperplanes in ℙ_{𝔽_{q}}^{k−1} and more generally, subcodes D ⊂ C of dimension r correspond to (projective) subspaces of codimension r in ℙ_{𝔽_{q}}^{k−1}. Consequently, the higher weights of C are given by

d_{r}(C)

= min {|X ∩ Π^{c}| : Π is a projective subspace of codimension r in ℙ^{k−1}}
= n − max {|X ∩ Π| : Π is a projective subspace of codimension r in ℙ^{k−1}} .

Here Π^{c} denotes the complement (in ℙ_{𝔽_{q}}^{k−1}) of Π.

Nice examples of projective systems can be obtained by considering (the set of 𝔽_{q}-rational points of) projective algebraic varieties defined over 𝔽_{q}. In particular, the Grassmannian over 𝔽_{q}:

G_{ℓ,m} = G_{ℓ,m}(𝔽_{q}) = {W : W is a subspace of 𝔽_{q}^{m} with dim W = ℓ}

defines an [n, k]_{q}–projective system, with

n := |G_{ℓ,m}(𝔽_{q})| = \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}{ℓ}.

Note that the above formula for |G_{ℓ,m}(𝔽_{q})| is a well-known fact whose proof can be found, for example, in [2]. Here, we use the natural nondegenerate embedding of G_{ℓ,m}(𝔽_{q}) in ℙ_{𝔽_{q}}^{k−1}, called the Plücker embedding. This is concretely obtained as follows. Let

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

be an indexing set [ordered, say, lexicographically] for the points of ℙ^{k−1}(𝔽_{q}). Given any α ∈ I(ℓ, m) and any ℓ × m matrix A = (a_{ij}), let

p_{α}(A) = α–th minor of A := det (a_{iα_{j}})_{1≤i,j≤ℓ} .

Now, for any W ∈ G_{ℓ,m}(𝔽_{q}), we can find a ℓ × m matrix A_{W} whose rows give a basis of W, and then

p(W) = (p_{α}(A_{W}))_{α∈I(ℓ,m)} ∈ ℙ_{𝔽_{q}}^{k−1}

is called the Plücker coordinate of W. It is easy to see that this depends only on W and not on the choice of A_{W}. Moreover, the map W ↦ p(W) of G_{ℓ,m}(𝔽_{q}) → ℙ_{𝔽_{q}}^{k−1} is injective and its image equals the zero locus of certain quadratic polynomials (cf. [4], [5] for details); this map, then, is the Plücker embedding. Henceforth, we shall identify W with p(W). It may be remarked that in defining the Plücker embedding, we have tacitly used representations of elements of 𝔽_{q}^{m} in terms of the natural basis of 𝔽_{q}^{m}; if instead, we use another basis to define the ‘coordinates’, then we have a linear isomorphism (i.e., a collineation) of the ambient space ℙ_{𝔽_{q}}^{k−1}, which induces an isomorphism between the two different embeddings of G_{ℓ,m}(𝔽_{q}).

The nondegenerate linear [n, k]_{q}–code corresponding to the projective system defined by G_{ℓ,m}(𝔽_{q}) (with its Plücker embedding) is denoted by C(ℓ, m) and is called the Grassmann code. It may be noted that if ℓ = 1, then G_{ℓ,m}(𝔽_{q}) = ℙ_{𝔽_{q}}^{m−1}, and thus in this case C(ℓ, m) is essentially the Reed-Muller code. On the other hand, if l = m, then G_{ℓ,m}(𝔽_{q}) reduces to a single point. To avoid trivialities, hereafter we shall tacitly assume that 1 ≤ ℓ < m.

3 Linear Sections of Grassmannians

We begin by stating a classical result on Grassmannians and then prove some auxiliary results concerning sections of the Grassmannian by linear subspaces that are intersections of coordinate hyperplanes. First, we need some notation.

Given any α ∈ I(ℓ, m), we let

B_{α} = {p ∈ G_{ℓ,m}(𝔽_{q}) : p_{α} = 1}

and

C_{α} = {t = (t_{ij}) : t an ℓ × m matrix over 𝔽_{q} with t_{iα_{j}} = δ_{ij} for 1 ≤ i, j ≤ ℓ},

where δ_{ij} is the usual Kronecker delta. Given any γ_{1}, …, γ_{ℓ} ∈ {1, …, m} and any p ∈ ℙ^{k−1}(𝔽_{q}), we let

p_{γ_{1}...γ_{ℓ}} = \{ \begin{matrix}0 & if γ_{i} = γ_{j} for some i ≠ j \\ p_{α} & if there exists a permutation σ of \{1, …, ℓ\} \\ & such that (γ_{σ(1)}, …, γ_{σ(ℓ)}) = α ∈ I(ℓ, m). \end{matrix}

The following result appears essentially as Proposition 2 in [5], and is also implicit in [4]. For more motivation and references about this result, see [1].

Lemma 1 (Basic Cell Lemma). Fix any α ∈ I(ℓ, m). Then the polynomial maps (or morphisms) Φ : B_{α} → C_{α} and Ψ : C_{α} → B_{α} defined by

Φ(p) = (t_{ij}(p)) , where t_{ij}(p) := p_{α_{1}...α_{i−1}jα_{i+1}...α_{ℓ}}, for 1 ≤ i ≤ ℓ, 1 ≤ j ≤ m

and

Ψ(t) = (p_{β}), where p_{β} := β–th minor of t = det (t_{iβ_{j}})_{1≤i,j≤ℓ} , for β ∈ I(ℓ, m),

are bijective and inverses of each other.

Now we introduce the following notation for intersections of the Grassmannian by coordinate hyperplanes. Given any subset Λ of I(ℓ, m), we let

E_{Λ} = {p ∈ G_{ℓ,m}(𝔽_{q}) : p_{α} = 0 for all α ∈ Λ}.

For a “small” subset Λ such as {α}, {α, β}, {α, β, γ}, the corresponding E_{Λ} would be simply denoted by E_{α}, E_{αβ}, E_{αβγ}, respectively. By standard conventions, E_{Λ} equals G_{ℓ,m}(𝔽_{q}) if Λ is empty.

Given any α ∈ I(ℓ, m), by ᾱ we shall denote the corresponding set, i.e., ᾱ = {α_{1}, …, α_{ℓ}}. A family Λ ⊆ I(ℓ, m) will be called close if |ᾱ ∩ β̄| = k − 1 for all α, β ∈ Λ, α ≠ β.

Proposition 1. Let Λ ⊆ I(ℓ, m) be a close family of cardinality r. Let δ = ℓ(m − ℓ). Then

|E_{Λ}| = \left[{m \atop ℓ}\right]_{q} − q^{δ} − q^{δ−1} − … − q^{δ−r+1}.

Proof. We proceed by induction on r. The case when r = 0 (i.e., when Λ is empty) is trivial. Assume that r ≥ 1 and that the result holds for smaller values of r. Fix any α ∈ Λ. Since Λ is close, for any β ∈ Λ with β ≠ α, there exist unique integers u = u(β) and v = v(β) such that 1 ≤ u ≤ ℓ, 1 ≤ v ≤ m, v ∉ ᾱ and β = (α_{1}, …, α_{u−1}, v, α_{u+1}, …, α_{ℓ}). Clearly the pairs (u(β), v(β)) are distinct for distinct elements β ∈ Λ. Moreover, for any p ∈ B_{α}, and any β ∈ Λ with β ≠ α, the β-th minor of t = Φ(p) is precisely equal to t_{uv}. Thus it follows from Lemma 1 that the set A_{r−1} = {p ∈ G_{ℓ,m} : p_{α} ≠ 0 and p_{β} = 0 for all β ∈ Λ \ {α}} is in bijection with the zero locus of r − 1 distinct coordinates in 𝔽_{q}^{δ}, and hence |A_{r−1}| = q^{δ−r+1}. Now note that E_{Λ} = E_{Λ\{α}} \ A_{r−1}, and apply the induction hypothesis.

Corollary 1. Given any α ∈ I(ℓ, m), we have |E_{α}| = \left[{m \atop ℓ}\right]_{q} − q^{ℓ(m−ℓ)}.

Proof. Any singleton subset of I(ℓ, m) is close. So we can apply Proposition 1.

4 Computation of Higher Weights

In this section, we shall give two proofs of Nogin’s result on the determination of certain higher weights d_{r} of the Grassmann code C(ℓ, m). As in Proposition 1, we let δ = ℓ(m − ℓ). The following result is proved in [7, Thm. 4.1].

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

Remarks. 1. Notice that a weaker version of the above result, namely, the inequality, d_{1} ≤ q^{δ} is an immediate consequence of Corollary 1.

2. Nogin’s proof of Proposition 2 uses the language of Exterior Algebra, and he shows that if ω ∈ Λ^{m−ℓ}𝔽_{q}^{m} is “completely decomposable” then the corresponding hyperplane H_{ω} is of minimum weight, that is, |H_{ω}^{c} ∩ G_{ℓ,m}(𝔽_{q})| = q^{δ}.

It may be noted that these completely decomposable hyperplanes are essentially the same as the coordinate hyperplanes E_{α} = {p ∈ G_{ℓ,m}(𝔽_{q}) : p_{α} = 0}. Indeed, if a completely decomposable element ω = v_{1} ∧ ⋯ ∧ v_{m−ℓ} ∈ Λ^{m−ℓ}𝔽_{q}^{m} is nonzero, then we can extend {v_{1}, …, v_{m−ℓ}} to a basis {v_{1}, …, v_{m}} of 𝔽_{q}^{m}. If we use this basis to define the Plücker coordinates, then for any ω′ ∈ Λ^{ℓ}𝔽_{q}^{m}, the condition ω′ ∧ ω = 0 (that defines H_{ω}) corresponds precisely to the condition p_{α} = 0 (that defines E_{α}) for a uniquely determined α.

3. A change of basis of the ambient space can be viewed as an instance of the natural action of the general linear group GL_{m}(𝔽_{q}) on the Grassmannian G_{ℓ,m}(𝔽_{q}). (See, for example, [1] for an explicit description of this group action). This action is transitive and thus an ‘orbit’ of p_{α} will consist of |G_{ℓ,m}(𝔽_{q})| = \left[{m \atop ℓ}\right]_{q} elements. Moreover, the α-th Plücker coordinate p_{α} is determined only up to multiplication by nonzero elements of 𝔽_{q}. This shows that the number of hyperplanes H in ℙ_{𝔽_{q}}^{k−1} such that |H ∩ G_{ℓ,m}(𝔽_{q})| = \left[{m \atop ℓ}\right]_{q} − q^{δ}, or equivalently, the number of minimum weight codewords of the Grassmann code C(ℓ, m), is ≥ (q − 1)\left[{m \atop ℓ}\right]_{q}. This inequality may be viewed as a weak version of Corollary 4.5 of [7].

We are now ready to state and prove Nogin’s main result on higher weights of Grassmann codes.

Theorem 1. For 1 ≤ r ≤ max{ℓ, m − ℓ} + 1, we have

d_{r}(C(ℓ, m)) = q^{δ} + q^{δ−1} + … + q^{δ−r+1} = q^{δ} (1 + \frac{1}{q} + … + \frac{1}{q^{r−1}} ) .

Proof. It is well-known (cf. [15]) that the higher weights of any linear code satisfy the Griesmer-Wei bound:

d_{r} ≥ ∑_{i=0}^{r−1} ⌈\frac{d_{1}}{q^{i}} ⌉ .

Thus, for the Grassmann code C(ℓ, m), we find using Proposition 2 that

d_{r} ≥ q^{δ} + q^{δ−1} + … + q^{δ−r+1}.

Now, since G_{ℓ,m} and G_{m−ℓ,m} are isomorphic, we may assume without loss of generality that (m − ℓ) ≥ ℓ. Choose any subset λ of {1, 2, …, m} of cardinality ℓ − 1. Given any positive integer r such that r ≤ m − ℓ + 1, we can choose r distinct integers from the complement of λ in {1, 2, …, m}, and add them to λ to generate a close subset Λ of I(ℓ, m) cardinality r. Therefore, by Proposition 1 and the description, given in Section 2, of higher weights in terms of projective systems, it follows that

d_{r} ≤ q^{δ} + q^{δ−1} + … + q^{δ−r+1}.

This completes the proof.

For a more ‘natural’ proof of Proposition 1, we shall make use of a ‘Structure Theorem for Close Families’ that is proved in [1]. It suffices to note only the following consequence of this Structure Theorem, which is also proved in [1].

Proposition 3. For r ≥ 2, the cardinality c_{r} = c_{r}(ℓ, m) of the set of close families Λ ⊆ I(ℓ, m) with |Λ| = r, is given by

c_{r} = \binom{m}{r} [\binom{m − r}{ℓ − 1} + Δ_{2,r}\binom{m − r}{m − ℓ − 1}] ,

where Δ_{2,r} is the complement of Kronecker delta, which is 0 if r = 2 and 1 otherwise.

Henceforth, for r ≥ 1, we let c_{r} = c_{r}(ℓ, m) be the integer defined above if r ≥ 2 and c_{r}(ℓ, m) = \binom{m}{ℓ} if r = 1. Note that this definition is consistent with the set theoretic description in Proposition 3.

Corollary 2. Assume that 1 ≤ ℓ < m and r ≥ 1. Then

c_{r}(ℓ, m) > 0 ⟺ r ≤ max{ℓ, m − ℓ} + 1.

Proof. Since l ≥ 1, we have

\binom{m − r}{ℓ − 1} > 0 ⟺ ℓ − 1 ≤ m − r ⟺ r ≤ m − ℓ + 1.

In particular, since l < m, we have c_{2}(ℓ, m) > 0. Further, since l < m, we have

\binom{m − r}{m − ℓ − 1} > 0 ⟺ m − ℓ − 1 ≤ m − r ⟺ r ≤ ℓ + 1.

So the desired result follows from Proposition 3 if r ≥ 2. The case of r = 1 is obvious.

Proof (Second Proof of Theorem 1). Suppose 1 ≤ r ≤ max{ℓ, m − ℓ} + 1. By Corollary 2, there exists a close family Λ ⊆ I(ℓ, m) of cardinality r. Now Proposition 1 implies that

d_{r} ≤ q^{δ} + q^{δ−1} + … + q^{δ−r+1}.

The other inequality is obtained, as in the previous proof of Theorem 1, from the Griesmer-Wei bound.

Corollary 3. For 1 ≤ r ≤ max{ℓ, m − ℓ} + 1, the number of r-dimensional subcodes of C(ℓ, m) of minimum Hamming norm is at least c_{r}(ℓ, m).

Proof. The r-dimensional subcodes D of C(ℓ, m) of minimum Hamming norm, viz., ∥D∥ = d_{r} = d_{r}(C(ℓ, m)), are in one-to-one correspondence with projective subspaces Π of ℙ_{𝔽_{q}}^{k−1} of codimension r for which |G_{ℓ,m}(𝔽_{q}) ∩ Π| = n − d_{r}. Every close family Λ ⊆ I(ℓ, m) of cardinality r defines such a projective subspace Π(Λ), and evidently, Π(Λ) ≠ Π(Λ′) if Λ′ ⊆ I(ℓ, m) is a close family of cardinality r with Λ ≠ Λ′. Thus the desired result follows from Proposition 3.

5 A Generalization of the Grassmann code

In this section, we discuss what appears to be a natural and, from the viewpoint of Algebraic Geometry, obvious generalization of Grassmann codes. This is obtained by considering the so called Schubert subvarieties of the Grassmannian. These subvarieties may be described as follows.

Fix any α = (α_{1}, …, α_{ℓ}) ∈ I(ℓ, m). Let A_{1} ⊂ ⋯ ⊂ A_{ℓ} be the canonical partial flag of subspaces of 𝔽_{q}^{m} associated to α, given by

A_{i} = span{e_{1}, …, e_{α_{i}}}, for i = 1, …, ℓ

where {e_{1}, …, e_{m}} denotes the natural basis of 𝔽_{q}^{m}. Define the Schubert variety in G_{ℓ,m}(𝔽_{q}) associated to α (or more pedantically, to the above partial flag) by

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

It is well-known (cf. [4], [5]) that Ω_{α} is a projective algebraic variety. Indeed, if we define for β = (β_{1}, …, β_{ℓ}) and β′ = (β′_{1}, …, β′_{ℓ}) in I(ℓ, m),

β ≤ β′ ⟺ β_{i} ≤ β′_{i} for all i = 1, …, ℓ,

then we obtain a partial order on I(ℓ, m), and as a consequence of the Basic Cell Lemma 1, it can be shown (see, for example, [5, Prop. 3]) that

Ω_{α}(𝔽_{q}) = {p ∈ G_{ℓ,m}(𝔽_{q}) : p_{β} = 0 for all β ≰ α},

and moreover that for any β ≤ α, there exists some p ∈ Ω_{α}(𝔽_{q}) such that p_{β} ≠ 0. In fact, the (defining) ideal I (Ω_{α}) of Ω_{α} is generated by the generic Plücker coordinates p_{β}, for β ≰ α and certain quadratic polynomials (cf. [4] for details). It follows that the Plücker coordinates p_{β}, for β ≤ α, do not satisfy any linear relation. Thus if we let

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

then Ω_{α}(𝔽_{q}) gives rise to a nondegenerate [n_{α}, k_{α}]_{q}-projective system, via the induced Plücker embedding, and therefore, a linear [n_{α}, k_{α}]_{q}-code. This code may be called a Schubert code and denoted by C_{α}(ℓ, m).

Notice that if α = (m−ℓ+1, m−ℓ+2, …, m), then β ≤ α for all β ∈ I(ℓ, m), and thus Ω_{α}(𝔽_{q}) = G_{ℓ,m}(𝔽_{q}). Thus in this case C_{α}(ℓ, m) equals the Grassmann code C(ℓ, m).

The following conjecture seems plausible.

Conjecture 1 (Ghorpade). The minimum distance d_{1} (C_{α}(ℓ, m)) of the Schubert code C_{α}(ℓ, m) equals q^{δ_{α}}, where

δ_{α} = ∑_{i=1}^{ℓ}(α_{i} − i) = α_{1} + … + α_{ℓ} − \frac{ℓ(ℓ + 1)}{2}.

Notice that if α = (m − ℓ + 1, m − ℓ + 2, …, m), then δ_{α} = ℓ(m − ℓ), and in this case, the conjectured equality follows from Proposition 2. In the general case, the following inequality can be proved as an application of the Basic Cell Lemma.

Proposition 4. d_{1} (C_{α}(ℓ, m)) ≤ q^{δ_{α}}.

Proof. Identify ℙ^{k_{α}−1} as a subset of ℙ^{k−1} in a natural way. Let p = p(W) ∈ B_{α} ∩ Ω_{α}(𝔽_{q}). Then we can choose a basis of W such that the corresponding ℓ × m matrix A_{W} = (a_{ij}) has the property that a_{ij} = 0 for j > α_{i}. Now if Φ : B_{α} → C_{α} is as in Lemma 1 and t = Φ(p), then using Laplace development for determinants, it is easy to see that t_{ij} = 0 whenever j > α_{i}. Conversely, if t ∈ C_{α} has this property, then it is evident that the subspace corresponding to p = Ψ(t) ∈ G_{ℓ,m}(𝔽_{q}) satisfies the intersection conditions defining Ω_{α}(𝔽_{q}). It follows that B_{α} ∩ Ω_{α}(𝔽_{q}) is in one-to-one correspondence with the set

{t ∈ C_{α} : t_{ij} = 0, for 1 ≤ i ≤ ℓ and 1 ≤ j ≤ m with j > α_{i}},

which is evidently in bijection with 𝔽_{q}^{δ_{α}}. Consequently, for the coordinate hyperplane H_{α} = {p ∈ ℙ_{𝔽_{q}}^{k_{α}−1} : p_{α} = 0}, we have |Ω_{α}(𝔽_{q}) ∩ H_{α}| = n_{α} − q^{δ_{α}}. This proves the desired inequality.

Remarks. 1. It may be noted that unlike in the case of Grassmannians, the intersection of the Schubert variety Ω_{α}(𝔽_{q}) with an arbitrary coordinate hyperplane H_{β} = {p ∈ ℙ_{𝔽_{q}}^{k_{α}−1} : p_{β} = 0} is not the complement of an affine space unless β = α. Indeed, this intersection is the complement of a ‘determinantal variety’ if β ≤ α, and it is Ω_{α}(𝔽_{q}) if β ≰ α. For some details concerning this, one may refer to [6].

2. The Grassmann variety G_{ℓ,m} admits a natural generalization to homogeneous varieties of the form G/P, where G is a nice (say, semisimple) algebraic group and P a maximal parabolic (or more generally, any parabolic) subgroup. Moreover, Schubert subvarieties can also be defined in this general context as the Zariski closures of the corresponding Schubert cells, and these are indexed by the quotients W/W_{P} of the Weyl group of G by the Weyl group of P. This would of course lead to a further generalization of the Grassmann code.

3. However, before proceeding with further generalizations as indicated above, it may be worthwhile to note that already in the classical case which we have considered here, the Schubert code C_{α}(ℓ, m) is far from well understood. For example, even the basic parameters n_{α} and k_{α} are not so easy to describe explicitly, not to mention the entire weight hierarchy. Recently, M. Tsfasman and the first author have looked at these and other related problems, and are able to answer some of them. The details may appear elsewhere.

4. Professor Hao Chen, who came across a preliminary version of this paper, has recently informed us that he is able to prove Conjecture 1 for Schubert codes in G_{2,m}(𝔽_{q}), that is, in the case of ℓ = 2.

References

1. Ghorpade, S. R., Lachaud, G.: Hyperplane sections of Grassmannians and the number of MDS linear codes . Preprint, 1999.

2. Goldman, J., Rota, G.-C.: The number of subspaces of a vector space. In: “Recent Progress in Combinatorics” (W. T. Tutte Ed.), pp. 75–84, Academic Press, New York, 1969.

3. Hirschfeld, J. W. P., Tsfasman, M. A., Vlăduţ, S. G.: The weight hierarchy of higher-dimensional Hermitian codes. IEEE Trans. Inform. Theory 40 (1994) 275–278.

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

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

6. Musili, C.: Applications of standard monomial theory. In: “Proceedings of the Hyderabad Conference on Algebraic Groups”, (S. Ramanan, Ed.), pp. 381–406, Manoj Prakashan, Madras (Distributed outside India by the American Math. Society, Providence), 1991.

7. Nogin, D. Yu.: Codes associated to Grassmannians. In: “Arithmetic, Geometry and Coding theory” (R. Pellikan, M. Perret, S. G. Vlăduţ, Eds.), pp. 145–154, Walter de Gruyter, Berlin/New York, 1996.

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

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

10. Ryan, C. T.: The weight distribution of a code associated to intersection properties of the Grassmannian variety G(3, 6). Congr. Numer. 61 (1988) 183–198.

11. Ryan, C. T., Ryan, K. M.: An application of geometry to the calculation of weight enumerators. Congr. Numer. 67 (1988) 77–90.

12. Ryan, C. T., Ryan, K. M.: The minimum weight of the Grassmann codes C(k, n). Discrete Appl. Math. 28 (1990) 149–156.

13. Tsfasman M. A., Vlăduţ, S. G.: “Algebraic Geometric Codes”, Kluwer, Amsterdam, 1991.

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

15. Wei, V. K.: Generalized Hamming weights for linear codes. IEEE Trans. Inform. Theory 37 (1991) 1412–1418.