Hyperplane Sections of Grassmannians and the Number of MDS Linear Codes

Sudhir R. Ghorpade^{*}

Department of Mathematics, Indian Institute of Technology, Bombay, Powai, Mumbai 400076, India E-mail: srg@math.iitb.ac.in

and

Gilles Lachaud

Équipe “Arithmétique et Théorie de l’Information”, Institut de Mathématiques

de Luminy, Luminy Case 907, 13288 Marseille, Cedex 9, France E-mail: lachaud@iml.univ-mrs.fr

Communicated by Michael Tsfasman

Received May 28, 1999; revised July 11, 2000

We obtain some effective lower and upper bounds for the number of (n, k)- MDS linear codes over 𝔽_{q}. As a consequence, one obtains an asymptotic formula for this number. These results also apply for the number of inequivalent representations over 𝔽_{q} of the uniform matroid, or, alternatively, the number of 𝔽_{q}-rational points of certain open strata of Grassmannians. The techniques used in the determination of bounds for the number of MDS codes are applied to deduce several geometric properties of certain sections of Grassmannians by coordinate hyperplanes.

Key Words: Grassmannians, MDS codes, hyperplane sections, uniform matroids, arcs in projective spaces.

1. INTRODUCTION

Let V be a vector space of dimension n over the finite field 𝔽_{q} of q elements. Fixing a basis of V, we can represent elements x ∈ V by their ‘coordinates’ (x_{1}, …, x_{n}), and then we can define a metric, known as the

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

Hamming metric, on V by

d(x, y) = | {i ∈ {1, 2, …, n} : x_{i} ≠ y_{i}}} |, for x, y ∈ V.

An (n, k)–linear code over 𝔽_{q} is simply a k-dimensional subspace of V. Given such a code C, one defines the minimal distance of C to be

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

If d(C) = t, then the code C ‘corrects’ ⌊(t − 1)/2⌋ errors. Thus, in Coding Theory, one is often interested in constructing codes C for which d(C) is as large as possible. In general, the minimal distance of any (n, k)-linear code satisfies the Singleton bound (cf. [29]), namely,

d(C) ≤ n − k + 1.

If d(C) = n − k + 1, then C is said to be a Maximum Distance Separable code, or simply, a MDS code.

Let q be a prime power and n, k be any integers such that 1 ≤ k ≤ n. We are primarily interested in the following problem.

Problem A: Determine the number of (n, k)-MDS linear codes over 𝔽_{q}.

It turns out that this problem admits a number of equivalent formulations. For example, in Matroid Theory, one has the notion of a uniform matroid. If we let U_{k,n} denote the uniform matroid on n elements (in which any k elements form a base), then Problem A is equivalent to

Problem A′: Determine the number of inequivalent representations over 𝔽_{q} of the uniform matroid U_{k,n}.

For a proof of equivalence of Problem A and Problem A′, and some related results, we refer to [42].

As another example, consider the Grassmannian, which is one of the most basic objects in Algebraic Geometry. If we let G_{k,n} denote the Grassmannian (of k-dimensional subspaces of an n-space) along with its canonical Plücker embedding [see Section 2 for details], and if U(k, n) denotes the open stratum of G_{k,n} consisting of those points of G_{k,n} for which all the Plücker coordinates are nonzero, then Problem A is equivalent to

Problem A′′: Determine the number of 𝔽_{q}-rational points of U(k, n).

It may be noted that, in view of Weil Conjectures, the last problem is essentially equivalent to determining the (ℓ-adic) Betti numbers of U(k, n) and the eigenvalues of the Frobenius endomorphisms on the étale cohomology groups of U(k, n). For details concerning this formulation, we refer to [41].

In a sense, Problem A can be traced back to some classical problems in Finite (Projective) Geometry posed by B. Segre in 1955. To describe these problems, we recall that an n-arc in the (k − 1)–dimensional projective space ℙ^{k−1} is a set of n points P_{1}, …, P_{n} in ℙ^{k−1} such that no k of them lie in a hyperplane. An n-arc is said to be complete if it can not be extended to a (n + 1)-arc in ℙ^{k−1}. Note that the point set of the rational normal curve, namely {P_{t} : t ∈ 𝔽_{q}} ∪ {P_{∞}}, where P_{t} = (1, t, t^{2}, …, t^{k−1}) and P_{∞} = (0, 0, …, 0, 1), is a classical example of a complete (q + 1)-arc. The problems of Segre can now be stated as follows.

S1 For which n, does there exist an n-arc in ℙ^{k−1}(𝔽_{q})?

S2 For which k, k < q, is every (q + 1)-arc in ℙ^{k−1}(𝔽_{q}) the point set of the rational normal curve?

S3 For which n and k, k < q, is every n-arc in ℙ^{k−1}(𝔽_{q}) a subset of the point set of the rational normal curve?

It is not difficult to see that the notion of an n-arc in ℙ^{k−1}(𝔽_{q}) is essentially equivalent to the notion of a (n, k)-MDS linear code. Thus Problem A also admits an equivalent formulation in the language of arcs in projective spaces over finite fields (see, for example, [38, Lem. 4]). To relate Segre’s problems to MDS codes, we let

γ(q) = γ(q; k, n) = the number of (n, k)-MDS codes over 𝔽_{q} .

Now the connection of Segre’s problems with MDS codes is clear from the following observations (cf. [41, Prop. 3.2]).

C1 There exists an n-arc in ℙ^{k−1}(𝔽_{q}) if and only if γ(q; k, n) > 0.

C2 If k < q, then every (q + 1)-arc in ℙ^{k−1}(𝔽_{q}) is the point set of the rational normal curve if and only if γ(q; k, q + 1) = γ(q; 2, q + 1) = (q − 1)^{q}(q − 2)!

C3 If n ≤ q + 1 and k < n − 1, then every n-arc in ℙ^{k−1}(𝔽_{q}) is a subset of the point set of the rational normal curve if and only if γ(q; k, n) = γ(q; 2, n) = (q − 1)^{n−1}(q − 2)(q − 3) ⋯ (q − n + 2).

For more on Segre’s problems and the known results concerning them, we refer to [6], [7] and [19].

Returning to Problem A, an exact formula for for γ(q; k, n) is known only when k = 2 (any n) and k = 3 (and n ≤ 9). Since there is a duality for MDS codes (cf. [45, Prop. 4.1]), we have γ(q; k, n) = γ(q; n − k, n), and in this way a few more values of (n, k) are covered. The known exact formulae are as follows.

(i) γ(q; 1, n) = (q − 1)^{n−1}

(ii) γ(q; 2, n) = (q − 1)^{n−1}(q − 2) ⋯ (q − n + 2)

(iii) γ(q; 3, 6) = (q − 1)^{5}(q − 2)(q − 3)(q^{2} − 2q + 21)

(iv) γ(q; 3, 7)=(q−1)^{6}[(q − 3)(q − 5)(q^{4} − 20q^{3} + 148q^{2} − 468q) −30a_{1}(q)]

(v) γ(q; 3, 8) = (q − 1)^{7}[(q − 5)(q^{7} − 43q^{6} + 788q^{5} − 7937q^{4} + 47097q^{3} −162834q^{2} − 299280q − 222960) − 240(q^{2} − 20q + 78)a_{1}(q) + 840b_{2}(q)]

(vi) γ(q; 3, 9) = (q − 1)^{8} [q^{10} − 75q^{9} + 2530q^{8} − 50466q^{7} + 657739q^{6} −5835825q^{5} − 35563770q^{4} − 146288034q^{3} + 386490120q^{2}− 588513120q+389442480−1080(q^{4}−47q^{3}+807q^{2}−5921q+15134)a_{1}(q) +840(9q^{2} − 243q + 1684)b_{2}(q) + 30240(−9b_{3}(q) + 9a_{2}(q) + 2a_{3}(q))].

Here, the functions a_{j}(q), b_{ℓ}(q) appearing in the formulae (iv)–(vi) are defined by a_{j}(q) = |{x ∈ 𝔽_{q} : f_{j}(x) = 0}|, where f_{1}(x) = x^{2} + x + 1, f_{2}(x) = x^{2} + x − 1 and f_{3}(x) = x^{2} + 1, and for a prime ℓ, b_{ℓ}(q) = 1 if q is a power of ℓ and 0 otherwise.

Of these exact formulae, (i) is trivial, (ii) is easy and (iii) is not difficult to obtain directly. Formulae (iv) and (v) were proved by Glynn [15]. Also, (iv) was proved independently in characteristic 2 by Rolland [38]. Lastly, (vi) was proved a few years ago by Iampolskaia, Skorobogatov and Sorokin [23]. It is clear that the exact formulae become increasingly complicated as n increases even for a small value of k such as k = 3, and it is perhaps a hopeless task to obtain an exact formula in the general case. In fact, as Skorobogatov [41] has remarked, the work of Mnëv [33] indicates that it may be theoretically impossible to determine γ(q; k, n) in general.

Faced with this scenario, we attempt in this paper to do what seems to be the next best thing to obtaining an exact solution of Problem A. Namely, we determine explicit upper and lower bounds for the number γ(q; k, n), for any values of n, k and q (see Theorem 5.5 for a precise statement). As a Corollary, one obtains the following asymptotic formula

γ(q; k, n) = q^{δ} + [1 − \binom{n}{k}] q^{δ−1} + O (q^{δ−2}) , where δ = k(n − k).

This implies in particular that given any (n, k) with 1 ≤ k ≤ n, there exist (many) MDS codes for sufficiently large q. To get some idea of how closely these bounds approximate γ(q), the reader may have a look at the tables in Section 7. It is seen therein that as q increases, our bounds become close to each other and (hence) to the exact value. Thus, these bounds seem fairly effective.

The main idea behind obtaining these bounds is quite simple. We work with the equivalent formulation in terms of the open stratum in Grassmannian (Problem A′′), and note that to calculate the number of its 𝔽_{q}-rational points, it suffices to determine the number of 𝔽_{q}-rational points of all sections (typically denoted by E_{Λ}) of the Grassmannian G_{k,n} by arbitrary families Λ of coordinate hyperplanes. Counting the latter is difficult in general, but in some cases we can do it using classical geometric facts about Grassmannians and some combinatorial ramifications thereof. Moreover, in the general case, we can obtain bounds for the number of 𝔽_{q}-rational points of E_{Λ}, using the Griesmer-Wei bounds for higher weights of linear codes and some work of Nogin [35] about the so called Grassmann codes. The information thus obtained about |E_{Λ}(𝔽_{q})| is applied to yield the bounds for γ(q; k, n) via the classical Bonnferroni inequalities.

In the process of counting the number of 𝔽_{q}-rational points of E_{Λ}, we are led to consider a combinatorial notion of “close” families of subsets of a finite set and prove a Structure Theorem concerning them. This part may perhaps be of interest in itself, and the reader may directly refer to Section 4 for details.

The counting of |E_{Λ}(𝔽_{q})| also paves the way for deducing a number of geometric results concerning the linear sections of Grassmannians by coordinate hyperplanes. This is done mainly using the Grothendieck-Lefschetz Trace Formula and Deligne’s Main Theorem ascertaining the validity of Riemann Hypothesis for varieties over finite fields (see Theorem 6.4 for a combined statement) and also using a result on hyperplane sections from [25]. It may be noted that the Schubert varieties in Grassmannians are particular cases of linear sections such as E_{Λ}. Also, a result of Mnëv [33] shows that up to birational equivalence and a torus action, the linear sections E_{Λ} are as general as any quasiprojective variety (at least over the reals). Thus, geometric properties of the linear sections E_{Λ} can be of considerable interest. We are able to prove results concerning the dimension, irreducibility (and, in general, the number of irreducible components), bounds on the dimensions of the singular loci, and in some cases Cohen-Macaulayness and normality, for the linear sections E_{Λ} when |Λ| ≤ 2. In case Λ is singleton, these results can be recovered from the known results concerning Schubert varieties (although our proofs are different) but when Λ has two elements, the results appear to be new. More generally, when Λ is a “close” family of cardinality > 2, we determine the dimension of E_{Λ} and show that it has only one top-dimensional irreducible component.

This paper is organized as follows. In the next section, we set up some notation, and collect some preliminaries concerning Grassmannians, MDS codes and elementary facts about counting or estimating the cardinality of finite unions of finite sets. Main lemmas about the cardinality of sections of Grassmannians by coordinate hyperplanes are proved in Section 3. In Section 4, we define the notion of close families and prove basic results concerning them. This section is self-contained and can be read independently of others. Our main results about the bounds on the number of MDS codes are proved in Section 5. Geometric applications of our techniques to linear sections of Grassmannians are given in Section 6, and a reader primarily interested in these geometric results can go directly to this section, referring to the earlier sections only as and when necessary. Finally, in Section 7, we give a number of tables which contain numerical values of the lower and upper bounds for γ(q; k, n) together with the exact value (wherever available) for certain ‘small’ values of (n, k) and q.

2. PRELIMINARIES

We begin with some notation and generalities about Grassmannians. A vector space V of dimension n over the field 𝔽_{q} of q elements, a basis {v_{1}, …, v_{n}} of V and an integer k with 1 ≤ k ≤ n will be kept fixed throughout this paper. We set

δ = k(n − k)  and  N = \binom{n}{k}.

By G_{k,n}(𝔽_{q}), or often simply by G_{k,n}, we shall denote the Grassmannian consisting of all k–dimensional subspaces of V. It is well-known that G_{k,n} can be naturally embedded in the projective space ℙ^{N−1}(𝔽_{q}). This is known as the Plücker embedding and it can be explicitly described as follows. First, let

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

We can, and will, index the points of ℙ^{N−1}(𝔽_{q}) by elements of I(k, n) [ordered, say, lexicographically]. Now, given a k–dimensional subspace W, the ‘coordinates’ (in terms of {v_{1}, …, v_{n}}) of a basis of W give a k × n matrix A = (a_{ij}) of rank k and the Plücker coordinate associated to W is given by p = (p_{α})_{α∈I(k,n)} where

p_{α} = α–th minor of A = det (a_{iα_{j}})_{1≤i,j≤k} , for α ∈ I(k, n).

Note that a different choice of a basis for W results in all p_{α}’s being multiplied by a nonzero scalar, and thus W uniquely determines a point of ℙ^{N−1}(𝔽_{q}). Note also that the above construction is valid if 𝔽_{q} is replaced by any field F. In case F is an algebraically closed field (for example, the algebraic closure of 𝔽_{q}), then it is well-known that the corresponding Grassmannian G_{k,n}(F) is a nondegenerate, irreducible, nonsingular projective variety in ℙ^{N−1}(F) of dimension δ (cf. [22]).

Following Andrews [3], we define the q–factorial of a nonnegative integer d by

[d]! = (q^{d} − 1)(q^{d−1} − 1) … (q − 1)

and the Gaussian binomial coefficient corresponding to n and k by

\left[{n \atop k}\right]_{q} = \frac{[n]!}{[k]![n − k]!} = \frac{(q^{n} − 1)(q^{n} − q) … (q^{n} − q^{k−1})}{(q^{k} − 1)(q^{k} − q) … (q^{k} − q^{k−1})}.

It is well-known (and not difficult to prove) that \left[{n \atop k}\right]_{q} is precisely the car-

dinality of the Grassmannian G_{k,n}(𝔽_{q}), and q^{\binom{d}{2}}[d]! is the cardinality of the general linear group GL_{d}(𝔽_{q}). (See, for example, [17]). It is also wellknown that \left[{n \atop k}\right]_{q} is, in fact, a polynomial in q of degree δ with positive integral coefficients; indeed

\left[{n \atop k}\right]_{q} = ∑_{i=0}^{δ} ν_{i} q^{i}

where ν_{i} is the number of partitions of i with at most k parts, each ≤ n−k, i.e., ν_{i} equals the cardinality of the following set:

{(λ_{1}, …, λ_{r}) ∈ ℕ^{r} : λ_{1}+⋯+λ_{r} = i, r ≤ k and n−k ≥ λ_{1} ≥ … ≥ λ_{r} ≥ 1}.

Alternately, ν_{i} can be described in terms of paths in a k ×(n−k) rectangle, or topologically (cf. [5, p. 292]) by ν_{i} = dim H^{2i}(G_{k,n}; ℂ). Notice that the sequence ν_{0}, ν_{1}, …, ν_{δ} of the coefficients of \left[{n \atop k}\right]_{q} is symmetric, i.e., ν_{i} = ν_{δ−i} for 0 ≤ i ≤ δ. This follows readily from the combinatorial description (by considering the complement in a k×(n−k) rectangle of the Young diagram of a partition) or from the topological description (by Poincaré duality). Thus, whenever 1 < k < n−1, one gets easily the following estimate, which will be useful for us in the sequel.

\left[{n \atop k}\right]_{q} = q^{δ} + q^{δ−1} + 2q^{δ−2} + O(q^{δ−3}). (1)

We now turn to some preliminaries about MDS codes. Throughout, by a code we will mean a linear code. Thus, an (n, k)-code over 𝔽_{q} is simply a k-dimensional subspace of V. Recall that the dual of an (n, k)-code C is the (n, n − k)-code C^{⊥} given by {x ∈ V : ⟨x, y⟩ = 0 for all y ∈ C}, where ⟨ ⟩ is the usual dot product on V w.r.t the basis {v_{1}, …, v_{n}}. Let us also recall the following well-known characterization of the minimal distance of a code. This result is implicit in [29] as well as in [36] and [38], and in any case, its proof is a simple exercise in Linear Algebra.

Lemma 2.1. Let C be an (n, k)–linear code over 𝔽_{q} and H be its parity check matrix [i.e., an (n − k) × n matrix whose rows form a basis of the dual of C in V] and d be a positive integer. Then d = d(C) if and only if every set of d − 1 columns of H is linearly independent and some set of d columns of H is linearly dependent.

Note that the Singleton inequality d(C) ≤ n − k + 1 is an immediate consequence of the above Lemma. Further, we have the following corollary, which links MDS codes to Grassmannians.

Corollary 2.2. Let C be an (n, k)–linear code over 𝔽_{q} and A be a k × n matrix whose rows form a basis of C. Then C is an MDS code if and only if all k ×k minors of A are nonzero. Consequently, the number of (n, k)–linear MDS codes over 𝔽_{q} equals the cardinality of the open stratum {p ∈ G_{k,n}(𝔽_{q}) : p_{α} ≠ 0 for all α ∈ I(k, n)} of the Grassmannian.

Proof. Follows by applying Lemma 2.1 to the dual C^{⊥} of C and noting that C is an MDS code if and only if C^{⊥} is. The latter follows, for instance, from Proposition 4.1 of [45].

Finally, in this section, we will recall some classical facts from Set Theory. Let N be a nonnegative integer. Put

[N] = {1, 2, …, N} and for r ∈ [N], I_{r}[N] = {Λ ⊆ [N] : |Λ| = r}.

Let A_{1}, …, A_{N} be finite sets. Given any Λ ⊆ [N], let

E_{Λ} = ⋂_{i∈Λ} A_{i}.

Given any r ∈ [N], let

e_{r} = ∑_{Λ∈I_{r}[N]} |E_{Λ}| and B_{r} = ∑_{i=1}^{r}(−1)^{i+1}e_{i}.

Proposition 2.3 (Principle of Inclusion and Exclusion).

| ⋃_{i∈[N]} A_{i} | = B_{N} = ∑_{i=1}^{N}(−1)^{i+1}e_{i}.

Proposition 2.4 (Bonnferroni Inequalities). Given any r ∈ [N], we have

| ⋃_{i∈[N]} A_{i} | ≤ B_{r} if r is odd,

and

| ⋃_{i∈[N]} A_{i} | ≥ B_{r} if r is even.

Remark 2.5. These results are very well-known. The inequalities in Proposition 2.4 seem to have first appeared in a paper of Bonnferroni (1936) on Probability and Statistics. For a reference to Bonnferroni’s work as well as for a proof of Propositions 2.3 and 2.4, see, for example, [9, §4.1 and 4.7]. It may be tempting to think that the Bonnferroni bounds B_{r} become better as r increases, that is,

B_{1} ≥ B_{3} ≥ B_{5} ≥ ⋯ and B_{2} ≤ B_{4} ≤ B_{6} ≤ · · · .

But this is not true in general. Examples are easy to construct. Roughly speaking, this will be true if the intersections E_{Λ} are not too large compared to the A_{i}’s. However, one can show that the inequalities above will always hold starting from B_{r} if r > ⌈N/2⌉. Indeed, for such r, we have \binom{N}{r−1} ≥ \binom{N}{r}, and one can find a “contractive surjection” f : I_{r−1}[N] → I_{r}[N] (i.e., a surjective map such that f(Λ′) ⊃ Λ′ for all Λ′ ∈ I_{r−1}[N]). The existence of such a map follows from the Symmetric Chain Decomposition (SCD) of the Boolean lattice (cf. [4, Thm. 1, p. 18]) or, alternatively, as a consequence of Hall’s Marriage Theorem (cf. [4, Ex. 7, p. 9]). Now,

∑_{Λ′∈I_{r−1}[N]} |E_{Λ′}| = ∑_{Λ∈I_{r}[N]} ∑_{Λ′∈f^{−1}(Λ)} |E_{Λ′}|
≥ ∑_{Λ∈I_{r}[N]} |E_{Λ}||f^{−1}(Λ)|
≥ ∑_{Λ∈I_{r}[N]} |E_{Λ}| ,

where the first inequality follows since f is contractive and the second since f is surjective. Thus e_{r−1} ≥ e_{r}, and this implies the desired inequalities for the Bonnferroni bounds.

3. HYPERPLANE SECTIONS OF GRASSMANNIANS

We now introduce a variant of a set-theoretic notation used in the previous section, which will be relevant for our purpose. Given any subset Λ of I(k, n), we let

E_{Λ} = {p ∈ G_{k,n} : p_{α} = 0 for all α ∈ Λ}.

For a “small” subset Λ such as {α}, {α, β}, {α, β, γ}, the corresponding E_{Λ} would be simply denoted by E_{α}, E_{αβ}, E_{αβγ}, respectively. Given any α ∈ I(k, n), by ᾱ we denote the corresponding set, i.e., ᾱ = {α_{1}, …, α_{k}}. Finally, given any point p = (p_{α}) ∈ ℙ^{N−1}(𝔽_{q}) and any integers γ_{1}, …, γ_{k} between 1 and n, we set

p_{γ_{1}...γ_{k}} = \{ \begin{matrix}0 & if γ_{i} = γ_{j} for some i ≠ j \\ sgn(σ)p_{α} & if γ_{1}, …, γ_{k} are distinct and σ ∈ S_{k}, α ∈ I(k, n) \\ & are such that γ_{σ(i)} = α_{i}, for 1 ≤ i ≤ k. \end{matrix}

In estimating the number of points of the open stratum of Corollary 2.2, the following fundamental lemma about the Grassmannian would be crucial. Briefly, it says that the intersection of G_{k,n} with a basic open subset U_{α} = {p ∈ ℙ^{N−1} : p_{α} ≠ 0} is in natural one-to-one correspondence with a cell (i.e., an affine space) of dimension δ. This result is classical and appears, for instance, essentially as Proposition 2 in [24]. It may be noted that although in [24] it is assumed that the ground field is ℂ, the argument therein works for arbitrary ground fields (of any characteristic). A slightly weaker version appears also in the literature on Coding Theory (see, for example, [36], [38], [41]).

Lemma 3.1 (Basic Cell Lemma). Fix any α ∈ I(k, n). Let

B_{α} = {p ∈ G_{k,n} : p_{α} = 1}

and

C_{α} = {t = (t_{ij}) ∈ M_{k,n}(𝔽_{q}) : t_{iα_{j}} = δ_{ij} for 1 ≤ i, j ≤ k},

where M_{k,n}(𝔽_{q}) denotes the set of all k × n matrices with entries in 𝔽_{q} and δ_{ij} denotes the Kronecker delta. Then the polynomial maps (or morphisms) Φ : B_{α} → C_{α} and Ψ : C_{α} → B_{α} defined by

Φ(p) = (t_{ij}(p)) ,

where for p ∈ B_{α},

t_{ij}(p) := p_{α_{1}...α_{i−1}jα_{i+1}...α_{k}}, for 1 ≤ i ≤ k, 1 ≤ j ≤ n

and

Ψ(t) = (p_{β}),

where for t ∈ C_{α},

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

are bijective and inverses of each other. In particular, G_{k,n} ∩ U_{α} is in one-to-one correspondence with 𝔸^{δ}(𝔽_{q}), where U_{α} = {p ∈ ℙ^{N−1} : p_{α} ≠ 0}.

Corollary 3.2. Given any α ∈ I(k, n), we have |E_{α}| = \left[{n \atop k}\right]_{q} − q^{δ}.

Proof. With U_{α} as in Lemma 3.1, we have E_{α} = G_{k,n} \(G_{k,n} ∩ U_{α}) and |𝔸^{δ}(𝔽_{q})| = q^{δ}.

Corollary 3.3. Let α, β ∈ I(k, n) be distinct and let d = k − |ᾱ ∩ β̄| be the “distance” between them. Then

|E_{αβ}| = \left[{n \atop k}\right]_{q} − 2q^{δ} + q^{δ−\binom{d+1}{2}}[d]!.

In particular, if |ᾱ ∩ β̄| = k − 1, then

|E_{αβ}| = \left[{n \atop k}\right]_{q} − 2q^{δ} − q^{δ−1}.

Proof. Let A_{1} = {p ∈ G_{k,n} : p_{α} ≠ 0 and p_{β} = 0} and n_{1} = |A_{1}|. By Lemma 3.1, we see that n_{1} = |{t ∈ C_{α} : f_{β}(t) = 0}|, where C_{α} is as in Lemma 3.1 and f_{β}(t) is the k × k minor det (t_{iβ_{j}})_{1≤i,j≤k}. Now, write

β̄ \ (ᾱ ∩ β̄) = {s_{1}, s_{2}, …, s_{d}} with s_{1} < s_{2} < … < s_{d}.

Since t_{iα_{j}} = δ_{ij} (1 ≤ i, j ≤ k), by expanding the k × k matrix (t_{iβ_{j}}) suitably, using Laplace development, it follows that

f_{β}(t) = det (t_{iβ_{j}})_{1≤i,j≤k} = ± det (t_{is_{j}})_{1≤i,j≤d} .

Therefore, the affine variety {t ∈ C_{α} : f_{β}(t) = 0} is a cone over the complement of GL_{d}(𝔽_{q}) in 𝔽_{q}^{d^{2}}. Consequently,

n_{1} = q^{δ−d^{2}} (q^{d^{2}} − q^{\binom{d}{2}}[d]!) = q^{δ} − q^{δ−\binom{d+1}{2}}[d]!.

The desired equality now follows from Corollary 3.2 since E_{αβ} = E_{β} \A_{1}.

Remark 3.4. Given any α, β ∈ I(k, n), if d = k − |ᾱ ∩ β̄| denotes the “distance” between them, then we always have d ≤ min{k, n − k}. Indeed, it is obvious that d ≤ k, and moreover, the relations

2k − |ᾱ ∩ β̄| = |ᾱ| + |β̄| − |ᾱ ∩ β̄| = |ᾱ ∪ β̄| ≤ n

readily imply that d ≤ n − k.

In general, the cardinality of E_{Λ} is very difficult to determine exactly. However, we show below that it can be determined if the elements of Λ are “close” to each other. Moreover, a rather surprising application of Coding Theory shows that the cardinality in the general case is bounded above by that in the “close” case.

Lemma 3.5. Let Λ be a subset of I(k, n) of cardinality r. Then

|E_{Λ}| ≤ \left[{n \atop k}\right]_{q} − q^{δ} − q^{δ−1} − … − q^{δ−r+1}.

Moreover, if Λ has the property that |ᾱ ∩ β̄| = k − 1, for all α, β ∈ I(k, n), α ≠ β, then the equality holds.

Proof. Since the Plücker embedding G_{k,n} ↪ ℙ^{N−1}(𝔽_{q}) is nondegenerate, it defines a nondegenerate projective system in the sense of Tsfasman– Vlăduţ (cf. [44], [45]) and therefore (by [45, Theorem 2.1]) a nondegenerate linear (\left[{n \atop k}\right]_{q}, N)–code. Viewed this way, the higher weights d_{r} of this code satisfy the following Griesmer–Wei bound (cf. [46]):

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

Moreover, we know from the work of Nogin [35] that the minimum distance d_{1} for this code is q^{δ}. Now, using the equivalence with the language of projective systems (cf. [45]) once again, we find that the difference \left[{n \atop k}\right]_{q}− d_{r} is given by

max {|G_{k,n} ∩ Π_{r}| : Π_{r} a codimension r projective subspace of ℙ^{N−1}} .

Thus, using the Griesmer–Wei bound with d_{1} = q^{δ}, we see that for any projective subspace Π_{r} of codimension r in ℙ^{N−1}, we have

|G_{k,n} ∩ Π_{r}| ≤ \left[{n \atop k}\right]_{q} − q^{δ} − q^{δ−1} − … − q^{δ−r+1}.

Now E_{Λ} is evidently the intersection of G_{k,n} with r coordinate hyperplanes, and hence the first part of the Lemma is proved. Next, suppose Λ has the property that |ᾱ ∩ β̄| = k − 1, for all α, β ∈ I(k, n), α ≠ β. Choose any α ∈ Λ. Using arguments similar to those in the proof of Corollary 3.3 above, we see that for any p ∈ G_{k,n} and β ∈ Λ \ {α}, p_{β} corresponds to ±t_{uv} in the correspondence of Lemma 3.1, for a pair (u, v) ≠ (i, α_{j}) for all 1 ≤ i, j ≤ k, which is uniquely determined by β. Moreover, the pairs (u, v) corresponding to distinct elements of Λ \ {α} are distinct. It follows that the set

A_{r−1} = {p ∈ G_{k,n} : p_{α} ≠ 0 and p_{β} = 0 for all β ∈ Λ \ {α}}

is in bijection with the zero locus of r − 1 distinct coordinates in 𝔽_{q}^{δ}, and thus |A_{r−1}| = q^{δ−r+1}. The desired equality follows by induction on r since E_{Λ} = E_{Λ\{α}} \ A_{r−1}.

Remark 3.6. For a more leisurely proof of the above Lemma as well as for an application of these ideas to the study of the so called Grassmann codes, see [13].

4. CLOSE FAMILIES OF k-SUBSETS

In this section, we shall prove some set-theoretic and combinatorial results, which, together with Corollary 3.3 and Lemma 3.5, would be useful in estimating the number of MDS codes. We shall find it convenient to use ‘subsets’ instead of ‘sequences’. Accordingly, we consider I_{k}[n] instead of I(k, n). Recall that for any integer j, we let

I_{j}[n] = {A : A is a subset of [n] with |A| = j}

and that [n] denotes the set of first n positive integers. As in Axiomatic Set Theory, for a given Λ ⊆ I_{k}[n], the intersection of all A ∈ Λ will be denoted by ∩Λ.

A family Λ ⊆ I_{k}[n] will be called close if

|A ∩ B| = k − 1 for all A, B ∈ Λ, A ≠ B.

Basic examples of close families can be obtained by considering either of the following two types.

Definition 4.1. Let Λ ⊆ I_{k}[n] be a nonempty family with |Λ| = r. We say that

(i) Λ is of Type I if there exists S ∈ I_{k−1}[n] and T ⊆ [n] \ S with |T | = r such that

Λ = {S ∪ {t} : t ∈ T }.

(ii) Λ is of Type II if there exists S ∈ I_{k−r+1}[n] and T ⊆ [n] \ S with |T | = r such that

Λ = {S ∪ T \ {t} : t ∈ T }.

Remark 4.1. With notation as in the Definition above, observe that if Λ is of Type I or of Type II, then ∩Λ is equal to S; in particular,

| ∩ Λ| = \{ \begin{matrix}k − 1 & if Λ is of Type I \\ k − r + 1 & if Λ is of Type II . \end{matrix}

It follows that if r > 2, the class of Type I families is disjoint from the class of Type II families. If r = 2, these two classes coincide. If r = 1, any Λ ⊆ I_{k}[n] with |Λ| = r is of Type I as well as of Type II.

The following characterization of close families is reminiscent of results in Extremal Set Theory or the Theory of Block Designs. However, we were unable to find it in the relevant literature.

Theorem 4.2 (Structure Theorem for Close Families). Let Λ ⊆ I_{k}[n] with |Λ| = r ≥ 2. Then Λ is close if and only if Λ is either of Type I or of Type II.

Proof. It is obvious that if Λ is of Type I or Type II, then Λ is close. Conversely, suppose Λ is close. We proceed by induction on r. The case of r = 2 is trivial. Suppose r = 3. Write Λ = {A, B, C} and let t_{B}, t_{C} ∈ A and j_{B}, j_{C} ∈ [n] \ A be the unique elements such that

B = (A \ {t_{B}}) ∪ {j_{B}} and C = (A \ {t_{C}}) ∪ {j_{C}}.

If t_{B} = t_{C}, then Λ is clearly of Type I, whereas if t_{B} ≠ t_{C}, then |B ∩ C| = k − 1 implies that j_{B} = j_{C}, and consequently, Λ is of Type II.

Now suppose r > 3 and that the result holds for smaller values of r. Fix any A ∈ Λ and let

Λ′ = Λ \ {A}, S′ = ∩Λ′ and S = ∩Λ.

By induction hypothesis, we are in either of the two cases below.

Case 1. Λ′ is of Type I.

Here, |S′| = k − 1, and thus for S = S′ ∩ A, we have k − 2 ≤ |S| ≤ k − 1. Suppose, if possible, |S| = k − 2. Now since r > 3, we can find distinct sets B_{1}, B_{2}, B_{3} ∈ Λ′ and distinct elements t_{1}, t_{2}, t_{3} ∈ [n] \ S′ such that B_{i} = S′ ∪ {t_{i}} for i = 1, 2, 3. Since |B_{i} ∩ A| = k − 1 > k − 2 = |S′ ∩ A|, we must have t_{i} ∈ A for i = 1, 2, 3. But then |A| ≥ k + 1, which is a contradiction. Therefore, |S| = k − 1 and so Λ must be of Type I.

Case 2. Λ′ is of Type II.

Here, |S′| = k − r + 2, and there exists T′ ⊆ [n] \ S′ with |T′| = r − 1 such that Λ′ = {S′ ∪ T′ \ {t′} : t′ ∈ T′}. Thus, for S = S′ ∩ A, we have k−r+1 ≤ |S| ≤ k−r+2. In any case, since r > 3, there exists t′_{1} ∈ T′ such that t′_{1} ∈ A. Let B_{1} = S′ ∪ T′ \ {t′_{1}}. Suppose, if possible, |S| = k − r + 2. Then S′ = S ⊆ A and since |A| = k, there exists t′_{2} ∈ T′ such that t′_{2} ∉ A. Let B_{2} = S′ ∪ T′ \ {t′_{2}}. Now |B_{1} ∩ A| = k − 1 implies that T′ \ {t′_{2}} ⊆ A. But then |B_{2} ∩ A| = k, which is a contradiction. Therefore, |S| = k − r + 1. So there is a unique s′ ∈ S′ such that S = S′ \ {s′}. Now |B_{1} ∩ A| = k − 1 implies that T′ ⊆ A, and thus S′ ∪ T′ \ {s′} = A. It follows that if we let T = T′ ∪ {s′}, then T ⊆ [n] \ S, |T | = r and Λ = {S ∪ T \ {t} : t ∈ T }. Thus Λ is of Type II.

This completes the proof.

Remark 4.3. It may be remarked that subfamilies Λ of I_{k}[n] are sometimes referred to as k-uniform hypergraphs or simply, as hypergraphs (see, for example [4]). Indeed, if k = 2, then these are essentially the same as simple graphs (i.e., finite graphs without loops or multiple edges). In the case of k = 2, the ‘Structure Theorem’ above is equivalent to an elementary result in Graph Theory that if a connected simple graph G has the property that any two edges are incident, then G is either a star or a triangle.

As a consequence of the ‘Structure Theorem’ above, we can calculate the cardinality of close families of a given size. In the sequel, we shall tacitly use the following elementary identities of binomial coefficients; for a proof of these, one may refer to [12, Lem. 3.1 (iv) and Lem. 3.2].

Given any integers a, b, c with a ≥ 0, we have

\binom{a}{b}\binom{a − b}{c} = \binom{a}{c}\binom{a − c}{a − b − c} = \binom{a}{a − b − c}\binom{b + c}{b}.

Corollary 4.4. Given any integer r ≥ 1, let c_{r} = c_{r}(k, n) denote the cardinality of all close families in I_{k}[n] of cardinality r. Then

c_{r} = \{ \begin{matrix}N & if r = 1 \\ \binom{n}{r}\binom{n − r}{k − 1} & if r = 2 \\ \binom{n}{r} [\binom{n − r}{k − 1} + \binom{n − r}{n − k − 1}] & if r ≥ 3 . \end{matrix}

Proof. The case of r = 1 is trivial. For r ≥ 2, the number of Λ ⊆ I_{k}[n] of Type I is clearly equal to

\binom{n}{k − 1}\binom{n − k + 1}{r} = \binom{n}{r}\binom{n − r}{n − k + 1 − r}

whereas the number of Λ ⊆ I_{k}[n] of Type II is clearly equal to

\binom{n}{k − r + 1}\binom{n − k + r − 1}{r} = \binom{n}{r}\binom{n − r}{n − k − 1}.

Thus, in view of Remark 4.1, the desired result follows from Theorem 4.2.

Remark 4.5. It would be interesting to determine the structure and consequently or otherwise, the cardinality of the set of families Λ ⊆ I_{k}[n] of k-subsets of [n] such that |Λ| = r and any two distinct elements of Λ are at “distance” d from each other (i.e., |A∩B| = k −d for A, B ∈ Λ, A ≠ B). The above two results correspond to the case of d = 1 while the Proposition below corresponds to the case of r = 2. It may be remarked that a variant of this general problem wherein one replaces the condition “distance d” by “distance ≤ d” (i.e., |A ∩ B| ≥ k − d for all A, B ∈ Λ) is much studied in the literature. For example, the well-known Erdös-Ko-Rado Theorem (cf. [4, p. 45]) is related to the case d = k − 1 of the latter problem.

Proposition 4.6. Let d be an integer with 1 ≤ d ≤ k and λ_{d} = λ_{d}(k, n) be the number of 2-element subsets {A, B} of I_{k}[n] such that |A∩B| = k−d. Then

λ_{d} = \frac{1}{2}\binom{n}{k}\binom{n − k}{d}\binom{k}{d} = \frac{N}{2} \binom{n − k}{d}\binom{k}{d}.

Proof. Choosing an ordered pair (A, B) with A, B ∈ I_{k}[n] and |A∩B| = k − d is equivalent to choosing any k − d elements of [n], and then any d elements from the rest, and finally, any d elements from the remaining n − (k − d) − d integers. Hence, the number of such ordered pairs is equal to

\binom{n}{k − d}\binom{n − k + d}{d}\binom{n − k}{d} = \binom{n}{n − k}\binom{k}{d}\binom{n − k}{d}.

For subsets instead of ordered pairs, we have to divide by 2.

Remark 4.7. With notations as in the two results above, we have:

1.λ_{d} = 0 if d > min{k, n − k}.

2. ∑_{d=1}^{min\{k,n−k\}} λ_{d} = \binom{N}{2}.

3.c_{2} = λ_{1}.

These identities follow easily from the formulae obtained above or alternatively, from the set-theoretic descriptions of c_{r} and λ_{d} and the observation in Remark 3.4.

5. BOUNDS FOR THE NUMBER OF MDS CODES

In this section, we shall prove our main results concerning estimates for

γ(q) = γ(q; k, n) = the number of (n, k)-MDS codes over 𝔽_{q} .

It is trivial to check that if k = n, then γ(q) = 1. Moreover, using the wellknown duality between MDS codes and their duals (cf. [45, Prop. 4.1]), we clearly have γ(q; k, n) = γ(q; n − k, n). Thus using Corollary 2.2, we can easily see that

γ(q; 1, n) = γ(q; n − 1, n) = (q − 1)^{n−1}.

With this in view, we shall tacitly assume throughout this section that 1 < k < n − 1.

Following Section 3, we will consider hyperplane sections E_{Λ} for Λ ⊆ I(k, n). As a variant of the notation used in Section 2, we define for any r ≥ 1,

e_{r}(q) = e_{r}(q; k, n) = ∑_{|Λ|=r} |E_{Λ}|,

where the sum is over all subfamilies Λ ⊆ I(k, n) of cardinality r. We set, by convention,

e_{0}(q) = e_{0}(q; k, n) = |G_{k,n}(𝔽_{q})| = \left[{n \atop k}\right]_{q}.

We also define for any r ≥ 0,

ℬ_{r}(q) = ℬ_{r}(q; k, n) = ∑_{i=0}^{r}(−1)^{i}e_{i}(q).

Note that for r > N = \binom{n}{k}, we have e_{r}(q) = 0 and ℬ_{r}(q) = ℬ_{N}(q).

Lemma 5.1. γ(q) = ℬ_{N}(q) = ∑_{r=0}^{N}(−1)^{r}e_{r}(q). Moreover, for any r ≥ 0,

ℬ_{2r+1}(q) ≤ γ(q) ≤ ℬ_{2r}(q).

Proof. By Corollary 2.2, we have

γ(q) = | G_{k,n}(𝔽_{q}) \ ⋃_{α∈I(k,n)} E_{α} | = \left[{n \atop k}\right]_{q} − | ⋃_{α∈I(k,n)} E_{α} |.

Thus the desired result follows from Proposition 2.3 and Proposition 2.4.

Now recall that for any r ≥ 1, we have defined in Section 4 the function c_{r} = c_{r}(k, n). Also for any integer d with 1 ≤ d ≤ k, we have defined the function λ_{d} = λ_{d}(k, n). It may be noted that c_{r} and λ_{d} are explicitly computable from the formulae given in Corollary 4.4 and Proposition 4.6. We set c_{0} = 1. Observe that as a consequence of Theorem 4.2, it is readily seen that for r ≥ 0,

c_{r}(k, n) = 0 if and only if r > max{k, n − k} + 1. (2)

It may be noted that the last assertion can also be derived from Corollary 4.4 (cf. [13]).

We define another explicit function by putting for any r ≥ 0,

ϵ_{r}(q) = ϵ_{r}(q; k, n) = \left[{n \atop k}\right]_{q} − q^{δ} − q^{δ−1} − ⋯ − q^{δ−r+1}.

Note that ϵ_{0}(q) = e_{0}(q) = \left[{n \atop k}\right]_{q}. More generally, we have the following relation between ϵ_{r}(q) and e_{r}(q).

MDS CODES AND GRASSMANNIANS 19

Lemma 5.2. For 0 ≤ r ≤ N, we have: c_{r}ϵ_{r}(q) ≤ e_{r}(q) ≤ \binom{N}{r}ϵ_{r}(q). Proof. The upper bound follows from the first assertion in Lemma 3.5

while the lower bound follows from the second assertion in Lemma 3.5. Proposition 5.3. With notations as above, we have the following.

(i) ℬ_{0}(q) = e_{0}(q) = \left[{n \atop k}\right]_{q}. And asymptotically, ℬ_{0}(q) = q^{δ} + q^{δ−1} + 2q^{δ−2} + O (q^{δ−3}) .

(ii) ℬ_{1}(q) = e_{0}(q) − e_{1}(q) is given by

ℬ_{1}(q) = Nq^{δ} + (1 − N)\left[{n \atop k}\right]_{q} = Nq^{δ} + (1 − N) ∏_{j=0}^{k−1} \frac{q^{n} − q^{j}}{q^{k} − q^{j}}

and asymptotically, it is given by

ℬ_{1}(q) = q^{δ} + (1 − N)q^{δ−1} + (2 − 2N)q^{δ−2} + O (q^{δ−3}) . (iii) ℬ_{2}(q) = e_{0}(q) − e_{1}(q) + e_{2}(q) is equal to

[N − 2\binom{N}{2}] q^{δ} + [1 − N + \binom{N}{2}] \left[{n \atop k}\right]_{q} + ∑_{d=1}^{min\{k,n−k\}} λ_{d}q^{δ−\binom{d+1}{2}}[d]!

and asymptotically, it is given by

ℬ_{2}(q) = q^{δ} + (1 − N)q^{δ−1} + [2 − 2N + \binom{N}{2}] q^{δ−2} + O (q^{δ−3}) .

Proof. The first assertion is trivial and the asymptotic formula in (i) has already been noted in Section 2. For (ii), note that

e_{1}(q) = ∑_{α∈I(k,n)} |E_{α}| = ∑_{α∈I(k,n)} (\left[{n \atop k}\right]_{q} − q^{δ}) = N\left[{n \atop k}\right]_{q} − Nq^{δ},

where the second equality follows from Corollary 3.2. The asymptotic formula for ℬ_{2}(q) follows from (i). Lastly, in view of Remark 3.4, we have

e_{2}(q) = ∑_{\begin{matrix}\{α, β\} ⊆ I(k, n) \\ α ≠ β \end{matrix}} |E_{αβ}| = ∑_{d=1}^{min\{k,n−k\}} ∑_{\begin{matrix}\{α, β\} ⊆ I(k, n) \\ |α ∩ β| = k − d \end{matrix}} |E_{αβ}|

= ∑_{d=1}^{min\{k,n−k\}} λ_{d} (\left[{n \atop k}\right]_{q} − 2q^{δ} + q^{δ−\binom{d+1}{2}}[d]!)

where the last equality follows from Corollary 3.3 and Proposition 4.6. The desired formulae for ℬ_{2}(q) follow from above in view of Remark 4.7. Moreover, if d > 1, then we have

q^{δ−\binom{d+1}{2}}[d]! = q^{δ} − q^{δ−1} − q^{δ−2} + O (q^{δ−3}) .

In view of (1) and Remark 4.7, this yields the asymptotic formula for ℬ_{2}(q).

Definitions 5.4. Given any s ≥ 0, we define L̃_{s}(q) = L̃_{s}(q; k, n) and Ũ_{s}(q) = Ũ_{s}(q; k, n) by

L̃_{s}(q) = ∑_{r=0}^{s} c_{2r}ϵ_{2r}(q) − ∑_{r=1}^{s+1} \binom{N}{2r − 1}ϵ_{2r−1}(q)

and

Ũ_{s}(q) = ∑_{r=0}^{s} \binom{N}{2r}ϵ_{2r}(q) − ∑_{r=0}^{s} c_{2r−1}ϵ_{2r−1}(q).

Further, we define L_{s}(q) = L_{s}(q; k, n) by L_{0}(q) = ℬ_{1}(q) and for s ≥ 1,

L_{s}(q) = ℬ_{2}(q) + ∑_{r=2}^{s} c_{2r}ϵ_{2r}(q) − ∑_{r=2}^{s+1} \binom{N}{2r − 1}ϵ_{2r−1}(q)

and U_{s}(q) = U_{s}(q; k, n) by U_{0}(q) = ℬ_{0}(q), U_{1}(q) = ℬ_{2}(q) and for s ≥ 2,

U_{s}(q) = ℬ_{2}(q) + ∑_{r=2}^{s} \binom{N}{2r}ϵ_{2r}(q) − ∑_{r=2}^{s} c_{2r−1}ϵ_{2r−1}(q).

Finally, we define

L̃(q) = L̃(q; k, n) = max {L̃_{s}(q) : 0 ≤ s ≤ ⌊(N − 1)/2⌋};
Ũ(q) = Ũ(q; k, n) = min {Ũ_{s}(q) : 0 ≤ s ≤ ⌊N/2⌋} ,

and

L(q) = L(q; k, n) = max {L_{s}(q) : 0 ≤ s ≤ ⌊(N − 1)/2⌋};
U(q) = U(q; k, n) = min {U_{s}(q) : 0 ≤ s ≤ ⌊N/2⌋} .

Theorem 5.5. We have the following lower and upper bounds for the number γ(q) = γ(q; k, n) of all (n, k)-MDS linear codes over 𝔽_{q}.

(i) For 0 ≤ s ≤ ⌊(N − 1)/2⌋, we have

L̃_{s}(q) ≤ L_{s}(q) ≤ γ(q).

(ii) For 0 ≤ s ≤ ⌊N/2⌋, we have

γ(q) ≤ U_{s}(q) ≤ Ũ_{s}(q).

(iii) Lastly, we have

L̃(q) ≤ L(q) ≤ γ(q) ≤ U(q) ≤ Ũ(q).

Proof. Given any s ≥ 0, by Lemma 5.1, we have γ(q) ≥ ℬ_{2s+1}(q). In particular, γ(q) ≥ ℬ_{1}(q) = L_{0}(q) = L̃_{0}(q). Now if 1 ≤ s ≤ ⌊(N − 1)/2⌋, or equivalently, if 1 ≤ 2s + 1 ≤ N, then by Lemma 5.2,

ℬ_{2s+1}(q) = ℬ_{2}(q) + ∑_{r=2}^{s} e_{2r}(q) − ∑_{r=2}^{s+1} e_{2r−1}(q)

≥ ℬ_{2}(q) + ∑_{r=2}^{s} c_{2r}ϵ_{2r}(q) − ∑_{r=2}^{s+1} \binom{N}{2r − 1}ϵ_{2r−1}(q).

Thus ℬ_{2s+1}(q) ≥ L_{s}(q). Likewise, Lemma 5.2 implies that

ℬ_{2}(q) ≥ c_{0}ϵ_{0}(q) − Nϵ_{1}(q) + c_{2}ϵ_{2}(q)

and thus L_{s}(q) ≥ L̃_{s}(q). This proves (i). Assertion (ii) is similarly proved, and (iii) is an immediate consequence of (i) and (ii).

Corollary 5.6. For any given parameters (n, k) with 1 ≤ k ≤ n, there exist (n, k)-MDS linear codes over 𝔽_{q} for sufficiently large q. In fact, γ(q; k, n) > 0 whenever q ≥ N = \binom{n}{k}.

Proof. Indeed, by Lemma 5.3 (ii), we have

L_{0}(q) = ℬ_{1}(q) = q^{δ} + (1 − N)q^{δ−1} + O (q^{δ−2}) .

Since the coefficient of q^{δ} is positive, it follows that L_{0}(q) > 0 for sufficiently large q. Hence, by Theorem 5.5 (i), γ(q) > 0 for q sufficiently large. The last assertion follows by looking at L_{0}(q) more carefully. Thus, we write,

L_{0}(q) = Nq^{δ} + (1 − N)\left[{n \atop k}\right]_{q} = ∑_{i=0}^{δ} ν_{i}q^{i} − ∑_{i=0}^{δ−1} Nν_{i}q^{i} = 1 + ∑_{i=0}^{δ−1} ν_{i}(q − N)q^{i}

where ν_{i} denotes the coefficient of q^{i} in the polynomial expansion of the Gaussian binomial coefficient \left[{n \atop k}\right]_{q}. As remarked in Section 2, each ν_{i} is pos-

itive, and thus the last expression above is ≥ 1 if q ≥ N.

Remark 5.7. The last assertion in the above Corollary appears to give a partial answer to the first problem of B. Segre. However, the bound N = \binom{n}{k} is not optimal, in general; this may be seen easily from the existence of the Reed-Solomon codes. However, the proof of Corollary 5.6 also shows that as soon as q > N, there is an abundance of MDS codes for the corresponding parameters.

Theorem 5.8. The number γ(q) = γ(q; k, n) of all (n, k)-MDS linear codes over 𝔽_{q} is asymptotically equal to

γ(q) = q^{δ} + [1 − \binom{n}{k}] q^{δ−1} + O (q^{δ−2}) .

Proof. By Lemma 5.3, both L_{0}(q) = ℬ_{1}(q) and U_{1}(q) = ℬ_{2}(q) are asymptotically given by

q^{δ} + (1 − N)q^{δ−1} + O (q^{δ−2}) .

Now by Theorem 5.5, L_{0}(q) ≤ γ(q) ≤ U_{1}(q) for all q. This implies the desired formula.

Remark 5.9. It may be worthwhile to write down explicitly some of the lower bounds and upper bounds given by Theorem 5.5. For example, L_{s}(q) for s = 0 gives the following lower bound for γ(q):

\binom{n}{k}q^{k(n−k)} + [1 − \binom{n}{k}] \frac{(q^{n} − 1)(q^{n} − q) … (q^{n} − q^{k−1})}{(q^{k} − 1)(q^{k} − q) … (q^{k} − q^{k−1})}

while U_{s}(q) for s = 0 gives the ‘trivial upper bound’

\left[{n \atop k}\right]_{q} = \frac{(q^{n} − 1)(q^{n} − q) … (q^{n} − q^{k−1})}{(q^{k} − 1)(q^{k} − q) … (q^{k} − q^{k−1})}.

A simpler, and slightly less trivial, upper bound can be obtained as a direct consequence of the Basic Cell Lemma. Namely,

γ(q; n, k) ≤ q^{k(n−k)}.

To see this, note that by Corollary 2.2, γ(q) ≤ |G_{k,n}(𝔽_{q}) \ E_{α}|, for any α ∈ I(k, n), and then use Corollary 3.2. We leave it to the reader to work out more special cases of the bounds in Theorem 5.5 and to observe that in a few cases, some simplifications in the defining expressions can be made.

6. GEOMETRIC APPLICATIONS

Let F be an algebraically closed field. Consider the Grassmannian G_{k,n}(F) of all k-dimensional subspaces of the n-dimensional vector space F^{n} over F. Let {v(1), …, v(n)} be the standard F -basis of F^{n}. As noted before, G_{k,n}(F) is a projective algebraic variety of ℙ_{F}^{N−1}, which is defined over ℤ (and hence over 𝔽_{q} for any prime power q). We are interested in the geometry of the closed subvarieties

E_{Λ}(F) = {p = (p_{γ}) ∈ G_{k,n}(F) : p_{γ} = 0 for all γ ∈ Λ}

where Λ ⊆ I(k, n). Note that classical Schubert varieties Ω_{α}(F) of G_{k,n}(F) are particular cases of E_{Λ}(F). Indeed, given α = (α_{1}, …, α_{k}) ∈ I(k, n), the corresponding Schubert variety Ω_{α}(F) is given by

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

where A_{i} = span{v(α_{1}), …, v(α_{i})} for 1 ≤ i ≤ k. Further, if we consider the ‘Bruhat order’ on I(k, n) defined by

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

where β = (β_{1}, …, β_{k}) and β′ = (β′_{1}, …, β′_{k}) are arbitrary elements of I(k, n), then, in terms of the Plücker coordinates, we have

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

It is well-known (cf. [22]) that Ω_{α}(F) are irreducible algebraic varieties and

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

Note that the Grassmannian G_{k,n}(F) is a particular case of Ω_{α}(F) with α = (n−k +1, n−k +2, …, n). In particular, dim G_{k,n}(F) = δ = k(n−k).

Lastly, recall that we have a natural transitive action of GL_{n}(F) on the Grassmannian G_{k,n}(F), given by (g, W) ↦ W′, where W′ ∈ G_{k,n}(F) is obtained from g ∈ GL_{n}(F) and W ∈ G_{k,n}(F) by considering a k×n matrix C whose rows form a basis of W and letting W′ be the subspace spanned by the rows of Cg. Alternatively, we can view G_{k,n}(F) as the quotient GL_{n}(F)/P_{k}, where P_{k} is the parabolic subgroup of GL_{n}(F) consisting of invertible matrices g = (g_{ij}) such that g_{ij} = 0 whenever 1 ≤ j ≤ k < i ≤ n; now GL_{n}(F) acts naturally on this quotient and thus on G_{k,n}(F). In particular, G_{k,n}(F) is a homogeneous space.

Lemma 6.1. For any α ∈ I(k, n), E_{α}(F) is isomorphic to a Schubert variety in G_{k,n}(F). In particular, E_{α}(F) is an irreducible variety, and moreover the dimension of E_{α}(F) is δ − 1.

Proof. By the homogeneity of G_{k,n}(F), it is clear that E_{α}(F) is isomorphic to E_{θ}(F), for any θ ∈ I(k, n). Take θ = (n−k+1, n−k+2, …, n−1, n). Then θ is the ‘maximal element’ of I(k, n) w.r.t. the Bruhat order and if η = (n − k, n − k + 2, …, n − 1, n), then: β ≰ η ⇔ β = θ, for any β ∈ I(k, n). Hence Ω_{η}(F) = E_{θ}(F). Therefore E_{θ}(F), and consequently any E_{α}(F) is irreducible. The assertion about the dimension of E_{α}(F) follows easily from the formula for the dimension of Schubert varieties.

Remarks 6.2. (i) It may be noted that the sections E_{α} and E_{θ} appearing in the above proof are not only isomorphic but also isotopic in the sense that there is an automorphism of the ambient space ℙ_{F}^{N−1} (in fact, a collineation, i.e., a projective linear isomorphism), which leaves G_{k,n}(F) invariant and maps E_{α}(F) onto E_{θ}(F). Indeed, let g ∈ GL_{n}(F) be the matrix corresponding to a permutation of the basis {v(1), …, v(n)} in such a way that v(α_{i}) ↦ v(θ_{i}) for 1 ≤ i ≤ k. Then the compound matrix C_{g} [which, by definition, is the N × N matrix, with rows and columns indexed by the elements of I(k, n), whose (β, γ)-th entry is the k × k minor det (g_{β_{i}γ_{j}})_{1≤i,j≤k}, where β, γ ∈ I(k, n)] is nonsingular and gives the desired collineation.

(ii) It is well-known (see, for example, [34, Thm. 4.1]) that if t = {t_{β} : β ∈ I(k, n)} is the set of coordinate functions on G_{k,n}(F), then the vanishing ideal of Ω_{α}(F) in the homogeneous coordinate ring R = F [t] of G_{k,n}(F) is precisely the ideal J_{α} generated by {t_{β} : β ≰ α}. In particular, the ring R/J_{α} is reduced. Note that if α = η = (n − k, n − k + 2, …, n − 1, n), then the ideal of Ω_{η}(F) in R is (t_{θ}). Hence, from the previous remark, we see that the ideal of E_{α}(F) in R is (t_{α}) and the ring R/(t_{α}) is reduced.

We shall now try to study more general linear sections E_{Λ} of the Grassmannian G_{k,n}. We begin by proving a useful fact about sections by close families as a nice application of the Structure Theorem.

Lemma 6.3. Let P = {P_{γ} : γ ∈ I(k, n)} be a family of N independent indeterminates over F and S = F [P] denote the corresponding polynomial ring. Let Q = I(G_{k,n}) denote the (vanishing) ideal of G_{k,n} in S. If Λ is a close subset of I(k, n), then the ideal I_{Λ} = Q + (P_{γ} : γ ∈ Λ) generated by Q and the indeterminates corresponding to Λ, is a radical ideal. In particular, the linear section E_{Λ} is also the scheme-theoretic intersection of G_{k,n} and the linear subvariety defined by the vanishing of the P_{γ}’s for γ ∈ Λ.

Proof. The case when Λ is empty is trivial. If |Λ| = 1, then E_{Λ} = E_{α} for some α ∈ I(k, n) and the result follows from Lemma 6.1 and Remark 6.2 (ii). Assume that |Λ| = r ≥ 2. By Theorem 4.2, Λ is of Type I or Type II. If Λ is of Type I, then by suitably permuting the basis elements v(1), …, v(n) of F^{n} [which, as in Remark 6.2 (i), would give a collineation of ℙ_{F}^{N−1} leaving G_{k,n}(F) invariant; or algebraically, an automorphism of S which leaves Q invariant], we may assume that Λ equals

Λ_{I} = {(n − k + 1 − j, n − k + 2, n − k + 3, …, n) : 0 ≤ j ≤ r − 1} .

On the other hand, if Λ is of Type II, then a suitable permutation of the basis elements would permit us to assume that Λ equals

Λ_{II} = \{(n − k, n − k + 1, …, { \atop n − k + j}, …, n) : 0 ≤ j ≤ r − 1\} ,

where { \atop n − k + j} indicates that n − k + j is deleted. Note that both Λ_{I} and Λ_{II} are upwards closed w.r.t the Bruhat order in the sense that if U denotes any one of them, then

α′ ∈ U, β′ ∈ I(k, n) and α′ ≤ β′ ⟹ β′ ∈ U.

Therefore from [34, Thm. 4.4], it follows that I_{Λ} is a radical ideal.

We shall now show how one can quickly obtain some interesting geometric information about some of the linear sections E_{Λ} if we use the results of Section 3 together with powerful results in Algebraic Geometry for varieties over finite fields. For simplicity, we shall assume henceforth that the ground field F is an algebraic closure of a finite field 𝔽_{q} of characteristic p. It is clear of course that all the varieties considered in this section (such as E_{Λ}(F)) are defined over 𝔽_{q} or for that matter over the prime subfield 𝔽_{p}. Now that F is fixed, we may simply write G_{k,n}, E_{α}, etc., in place of G_{k,n}(F), E_{α}(F), etc., in the remainder of this section.

We state below a weak version of the Grothendieck-Lefschetz Trace Formula, coupled with Deligne’s Main Theorem concerning the so called Riemann hypothesis for varieties over finite fields.

Theorem 6.4. Let X be a projective algebraic variety defined over 𝔽_{q}, and let X̄ = X ⊗ F denote the corresponding variety over the algebraic closure F of 𝔽_{q}. Let dim X̄ = d. Then there exist integers b_{i}, for 0 ≤ i ≤ 2d, and algebraic integers ω_{ij}, for 0 ≤ i ≤ 2d, 1 ≤ j ≤ b_{i}, such that

|ω_{ij}| ≤ q^{i/2} for 0 ≤ i ≤ 2d, 1 ≤ j ≤ b_{i},

and for any m ≥ 1, we have

|X(𝔽_{q^{m}})| = ∑_{i=0}^{2d}(−1)^{i} ∑_{j=1}^{b_{i}} ω_{ij}^{m};

in particular,

|X(𝔽_{q^{m}})| ≤ ∑_{i=0}^{2d} b_{i}(q^{m})^{i/2}.

Further, if X̄ is irreducible, then for any m ≥ 1, we have

|X(𝔽_{q^{m}})| = (q^{m})^{d} + ∑_{i=0}^{2d−1}(−1)^{i} ∑_{j=1}^{b_{i}} ω_{ij}^{m} ≤ (q^{m})^{d} + ∑_{i=0}^{2d−1} b_{i}(q^{m})^{i/2}.

Remark 6.5. The numbers ω_{ij} are the eigenvalues of the (geometric) Frobenius endomorphism on the étale cohomology spaces H^{i}(X̄) = H^{i}(X̄, ℚ_{ℓ}) of X̄, where ℓ is a prime different from p. The assertion about the absolute values of ω_{ij} may be stated more precisely by saying that each ω_{ij} is pure of weight ≤ i/2. Recall that a number ω ∈ \overline{ℚ}_{ℓ} is said to be pure of weight r if ω is an algebraic integer and |ι(ω)| = q^{r/2} for any embedding ι of \overline{ℚ}_{ℓ} in ℂ. And H^{i}(X̄) is said to be pure of weight i if all the eigenvalues of the Frobenius endomorphism on H^{i}(X̄) are pure of weight i. It is known that if X is nonsingular, then each H^{i}(X̄) is pure of weight i. For a more general and more detailed description of the above Theorem, see [14], [32], and/or the original sources referred therein.

Corollary 6.6. Let X be a projective algebraic variety defined over 𝔽_{q}, and let X̄ = X ⊗F denote the corresponding variety over F. If dim X̄ = d, then the limit

lim_{m→∞} \frac{|X(𝔽_{q^{m}})|}{q^{md}}.

exists and is equal to the number of irreducible components of X̄ of dimension d.

Proof. Let

X̄ = Y_{1} ∪ … ∪ Y_{b} ∪ Y_{b+1} ∪ … ∪ Y_{b+c}

be an irredundant decomposition of X̄ into irreducible subvarieties, where Y_{1}, …, Y_{b} are of dimension d and Y_{b+1}, …, Y_{b+c} are of dimension < d. Since the decomposition is irredundant, it follows that for r > 1 and 1 ≤ i_{1} < … < i_{r} ≤ b + c, the intersection Y_{i_{1}} ∩ ⋯ ∩ Y_{i_{r}} is of dimension < d. Now by Proposition 2.3, we see that |X(𝔽_{q^{m}})| equals

∑_{i=1}^{b} |Y_{i}(𝔽_{q^{m}})| + ∑_{j=1}^{c} |Y_{b+j}(𝔽_{q^{m}})| − ∑_{1≤i<j≤b+c} |Y_{i}(𝔽_{q^{m}}) ∩ Y_{j}(𝔽_{q^{m}})| + · · · .

Dividing by q^{md} and taking limit as m → ∞, the desired result follows readily from Theorem 6.4.

Remark 6.7. As noted in [14, Proof of Prop. 3.3], we have, in general, that for any scheme X of dimension d, the number of irreducible components of dimension d is equal to the dimension of the (2d)-th étale cohomology space of X̄.

Theorem 6.8. Suppose 1 < k < n − 1. Let Λ ⊆ I(k, n) be a family such that |Λ| ≥ 2. Then we have the following.

(i) If Λ is close, then dim E_{Λ} = δ − 2.

(ii) If Λ is close and |Λ| = 2, then E_{Λ} has exactly two irreducible components of dimension δ − 2,

(iii) If Λ is close and |Λ| > 2, then E_{Λ} has exactly one irreducible component of dimension δ − 2.

(iv) If Λ is not close and |Λ| = 2, then E_{Λ} has exactly one irreducible component of dimension δ − 2.

Proof. Let r = |Λ|. Since r ≥ 2, we can find two distinct elements α and β in Λ. Assume that either Λ is close or |Λ| = 2. In case Λ is close, by Lemma 3.5, we have

|E_{Λ}(𝔽_{q})| = \left[{n \atop k}\right]_{q} − q^{δ} − q^{δ−1} − … − q^{δ−r+1} (3)

whereas if Λ is not close and |Λ| = 2, then d = k − |ᾱ ∩ β̄| > 1 and by Corollary 3.3, we have

|E_{αβ}(𝔽_{q})| = \left[{n \atop k}\right]_{q} − 2q^{δ} + q^{δ−\binom{d+1}{2}}[d]!. (4)

Also recall that by Corollary 3.2, we have

|E_{α}(𝔽_{q})| = \left[{n \atop k}\right]_{q} − q^{δ}. (5)

Now using the asymptotic description for \left[{n \atop k}\right]_{q} as in Section 2, and the

asymptotic description for q^{δ−\binom{d+1}{2}}[d]! appearing in the proof of Proposition 5.3, we see that

|E_{Λ}(𝔽_{q})| = bq^{δ−2} + O (q^{δ−3}) (6)

where

b = \{ \begin{matrix}1 & if |Λ| > 2 and Λ is close, \\ 1 & if |Λ| = 2 and Λ is not close, \\ 2 & if |Λ| = 2 and Λ is close. \end{matrix}

It is clear that each of the identities (3), (4), (5) and (6) are valid with q replaced by q^{m} for any m ≥ 1. Hence we see that E_{Λ} is a proper subvariety of E_{α}. By Lemma 6.1, the latter is irreducible of dimension δ − 1, and therefore, if we let e = dim E_{αβ}, then e ≤ δ − 2. Moreover, if e < δ − 2, then from Theorem 6.4 we see that |E_{Λ}(𝔽_{q^{m}})|/q^{me} is unbounded as m → ∞. But this contradicts Corollary 6.6. Thus, e = δ − 2. The remaining assertions concerning the number of irreducible components of dimension δ − 2 follow from (6) in view of Corollary 6.6.

In the case of E_{Λ}, where Λ is close and |Λ| = 2, we can sharpen the result in Theorem 6.8 (ii) using the following algebro-geometric result. Recall that a projective algebraic variety is said to be arithmetically Cohen-Macaulay if its homogeneous coordinate ring is Cohen-Macaulay.

Theorem 6.9. Suppose 1 < k < n − 1. Let α, β ∈ I(k, n) be such that |ᾱ ∩ β̄| = k − 1. Then the projective variety E_{αβ} is arithmetically Cohen-Macaulay. In particular, E_{αβ} is Cohen-Macaulay and equidimensional.

Proof. Let P = {P_{γ} : γ ∈ I(k, n)}, S = F [P] and Q = I(G_{k,n}) be as in Lemma 6.3. Further, let I = I(E_{α}) and J = I(E_{αβ}) denote, respectively, the ideals of E_{α} and E_{αβ} in S. By Lemma 6.1 and the arithmetic Cohen-Macaulayness of Schubert varieties (cf. [21], [27] or [34]), we see that the homogeneous coordinate ring A = S/I of E_{α} is a Cohen-Macaulay domain of dimension δ. Moreover, by Theorem 6.8, it follows that the homogeneous coordinate ring B = S/J of E_{αβ} is of dimension δ − 1. Also, in view of Remark 6.2 (ii), Lemma 6.3 and Hilbert’s Nullstellensatz, we have I = (Q, P_{α}) and J = (I, P_{β}).

The arithmetic Cohen-Macaulayness of the projective variety E_{αβ} (or equivalently, the Cohen-Macaulayness of S/J) now follows from one of several ‘routine’ arguments using the fact that S/I is Cohen-Macaulay, J = (I, P_{β}) and dim S/J = dim S/I − 1. We outline below one such argument for the sake of completeness. Let h_{β} denote the image of P_{β} in A = S/I. Then B = S/J is isomorphic to Ā = A/ (h_{β}). Now let 𝔪 be a maximal ideal of A containing h_{β} and \overline{𝔪} be the corresponding maximal ideal of Ā. Since A is Cohen-Macaulay, it is universally catenary (cf. [30, Thm. 33]), and thus (using, for example, the observations in [30, Sec. 14.B]), it follows that the localizations A_{𝔪} and Ā\overline{𝔪} are of dimensions δ and δ −1 respectively and the former is Cohen-Macaulay. In particular, h_{β} is a regular element in A_{𝔪} and by [30, Thm. 30], it can be extended to a maximal regular sequence h_{β}, f_{2}, …, f_{δ} of A_{𝔪}. Consequently, f̄_{2}, …, f̄_{δ} is a regular sequence of Ā\overline{𝔪}. Therefore Ā\overline{𝔪} is Cohen-Macaulay. This shows that E_{αβ} is arithmetically Cohen-Macaulay. The remaining assertions are consequences of standard facts in Commutative Algebra (see, for example, [30, Sec. 16]).

Remark 6.10. The irreducibility and arithmetic Cohen-Macaulayness of E_{α} can also be derived using arguments similar to those in the proofs of Theorem 6.8 and Theorem 6.9. In other words, we can first use Corollary 3.2 and Theorem 6.4 to determine the dimension and the number of topdimensional irreducible components of E_{α}, and secondly, we can use the connection with Schubert varieties [in effect, just the ‘Basis Theorem’] only to the extent of deducing the observation in Remark 6.2 (ii) that the ideal of E_{α} in R is (t_{α}). In this way, one can avoid Lemma 6.1 and using some results from [21], [27] or [34].

Corollary 6.11. Suppose 1 < k < n − 1. Let α, β ∈ I(k, n) be such that |ᾱ ∩ β̄| = k − 1. Then the projective variety E_{αβ}(F) has exactly two irreducible components, each of dimension δ − 2.

Proof. Follows from Theorem 6.8 and Theorem 6.9.

It turns out that the results of Section 3 can be used not only to get information about the dimension of the hyperplane sections E_{Λ} and of their irreducible components, but also to derive interesting facts concerning the singularities of these hyperplane sections. To this end, we shall use the following result, which is proved in [25, Prop. 3.2]. We use this opportunity to remark a small correction in [25, Prop. 3.2], namely that #X_{Z(f)}(𝔽_{q}) should be replaced by q #X_{Z(f)}(𝔽_{q}) on two occasions in the statement of the said proposition. Indeed, the proof of [25, Prop. 3.2] is valid only if this correction is made.

Proposition 6.12. Let X be an irreducible projective variety in ℙ_{F}^{N−1} of dimension d defined over 𝔽_{q}, f be a homogeneous polynomial in N variables with coefficients in 𝔽_{q}, H be subscheme of ℙ_{F}^{N−1} corresponding to the principal ideal generated by f, and let E^{∗} be the scheme-theoretic intersection of X and H. Let σ(f) = dim Sing E^{∗} denote the dimension of the singular locus of E^{∗} and let E be the algebraic set (i.e., the reduced subscheme) associated to E^{∗}. Then there exists a constant B_{0} = B_{0}(f, X), independent of q such that

| q|E(𝔽_{q})| − |X(𝔽_{q})| | ≤ B_{0}(f, X)q^{(d+σ(f)+2)/2}.

Remark 6.13. From Lemma 6.3 and the proof of Theorem 6.9, it is clear that if {α, β} is close, then the scheme theoretic intersection of E_{α} with the hyperplane H_{β} corresponding to the ideal (P_{β}) is reduced and equals E_{αβ}.

Corollary 6.14. Given any α ∈ I(k, n), we have dim Sing E_{α} ≥ δ − 4, or equivalently, the codimension of Sing E_{α} in E_{α} is ≤ 3.

Proof. The case when k = 1 or k ≥ n−1 is trivial. Thus we may assume that 1 < k < n. From Corollary 3.2 and the asymptotic description for \left[{n \atop k}\right]_{q} given in Section 2, we have

|E_{α}(𝔽_{q})| = \left[{n \atop k}\right]_{q} − q^{δ} = q^{δ−1} + 2q^{δ−2} + O (q^{δ−3}) .

Applying Proposition 6.12 with X = G_{k,n}(F) and f = P_{α} and noting that

q (q^{δ−1} + 2q^{δ−2} + ⋯) − (q^{δ} + q^{δ−1} + 2q^{δ−2} + ⋯) = q^{δ−1} + O (q^{δ−2}) , we get δ − 1 ≤ (δ + σ(f) + 2)/2, which implies that σ(f) ≥ δ − 4. Hence from Lemma 6.1 and the fact that E_{α} is reduced (cf. Remark 6.2 (ii)), it follows that codim Sing E_{α} ≤ 3.

Remark 6.15. In fact, a more precise result than that given by the above Corollary is known. Indeed, by Lemma 6.1, we know that E_{α} is isomorphic to the Schubert variety Ω_{η}(F) in G_{k,n}(F), where η = (n − k, n − k + 2, …, n − 1, n), Now, thanks to the work of Lascoux [28], Svanes [43], and Lakshmibai-Weymann [26], the structure of the singular locus of all Schubert varieties in Grassmannians is well understood. Thus, for example, from [26, Thm. 5.3], we can easily see that Sing Ω_{η}(F) = Ω_{η′}(F), where η′ = (n − k − 1, n − k, n − k + 3, …, n − 1, n). In particular, from the dimension formula noted at the beginning of this section and in view of the proof of Lemma 6.1, we obtain that dim Sing E_{α} = dim Ω_{η′}(F) = 2(n − k − 2) + (k − 2)(n − k) = δ − 4, and thus codim Sing E_{α} = 3. This shows, in particular, that E_{α} has no singularities in codimension 1, and since, as noted in the proof of Theorem 6.9, it is Cohen-Macaulay, it follows from Serre’s criterion of normality, that E_{α} is a normal variety. It may be remarked that the normality of arbitrary Schubert varieties is known in general from the work of Andersen [2], Ramanan-Ramanathan [37] and Seshadri [40] (see also [31] for a short proof). However, in the case of more general hyperplane sections E_{Λ}, which may not be Schubert varieties, very little seems to be known in the literature. In the case of E_{αβ}, where {α, β} is close, the following Corollary gives some results that our methods would yield.

Corollary 6.16. Suppose 1 < k < n − 1. Let α, β ∈ I(k, n) be such that |ᾱ ∩ β̄| = k − 1. Then dim Sing E_{αβ} = δ − 3, or equivalently, the codimension of Sing E_{αβ} in E_{αβ} is 1. In particular, E_{αβ} is not a normal variety.

Proof. By Lemma 6.1 we know that E_{α} is an irreducible projective variety with dim E_{α} = δ − 1. Now in view of Corollary 3.2 and Corollary 3.3, by applying Proposition 6.12 with X = E_{α} and f = P_{β} it follows that there is a constant B_{0} independent of q such that

| q (2q^{δ−2} + ⋯) − (q^{δ−1} + 2q^{δ−2} + ⋯) | ≤ B_{0}q^{(δ−1+σ(f)+2)/2}.

Consequently, δ − 1 ≤ (δ + σ(f) + 1)/2, and therefore σ(f) ≥ δ − 3. On the other hand, by Remark 6.13, the scheme theoretic intersection E_{αβ}^{∗} of E_{α} and the hyperplane H_{β} corresponding to (P_{β}) is reduced, and thus it has no singularities in codimension 0 (see, for example, [11, Ex. 11.10, p. 266]). Hence E_{αβ}^{∗} = E_{αβ} and σ(f) ≤ dim E_{αβ} − 1 = δ − 3. Thus codim Sing E_{αβ} = 1. Now since E_{αβ} has singularities in codimension 1, Serre’s criterion of normality implies that it can not be a normal variety.

In contrast to the linear section E_{αβ} by a close family of two coordinate hyperplanes, we shall show that in the case of families {α, β} which are not close, the variety E_{αβ} is much better behaved.

Theorem 6.17. Suppose 1 < k < n − 1. Let α, β ∈ I(k, n) be such that |ᾱ∩β̄| < k−1. Let H_{β} denote the hyperplane in ℙ_{F}^{N−1} defined by {P_{β} = 0}, and let E_{αβ}^{∗} denote the scheme theoretic intersection of E_{α} and H_{β}. Then we have the following.

(i) dim Sing E_{αβ}^{∗} ≥ δ − 5. In other words, codim Sing E_{αβ}^{∗} ≤ 3.

(ii) E_{αβ}^{∗} is arithmetically Cohen-Macaulay. In particular, it is Cohen-Macaulay and equidimensional.

(iii) E_{αβ} is an irreducible variety.

Proof. To prove (i), we proceed as in the proof of Corollary 6.16. Thus, we first note that E_{α} is irreducible of dimension δ−1. Now, using Corollary 3.2, Corollary 3.3, the asymptotic description for q^{δ−\binom{d+1}{2}}[d]! appearing in the proof of Proposition 5.3, and Proposition 6.12, we see that there is a constant B_{0} independent of q such that

| q (q^{δ−2} + 3q^{δ−3} + ⋯) − (q^{δ−1} + 2q^{δ−2} + ⋯) | ≤ B_{0}q^{(δ−1+σ(f)+2)/2}.

Consequently, δ −2 ≤ (δ +σ(f)+1)/2, and therefore σ(f) ≥ δ −5. Next, to prove (ii), we let S = F [P] and Q be as in Lemma 6.3 so that R = S/Q is the homogeneous coordinate ring of G_{k,n}. Write R = F [t], where t = {t_{γ} : γ ∈ I(k, n)} and t_{γ} denotes the image of P_{γ} in R. Let J^{∗} be the ideal of R generated by t_{α} and t_{β}. Since E_{α} and H_{β} are both reduced, it follows that the homogeneous coordinate ring of E_{αβ}^{∗} is isomorphic to R/J^{∗}. Since J^{∗} and \sqrt{J^{∗}} have the same set of minimal primes, it follows from Hilbert’s Nullstellensatz that dim E_{αβ}^{∗} = dim E_{αβ} = δ−2. Now R is Cohen-Macaulay (cf. [21]) and J^{∗} is an ideal of codimension 2 and is generated by two elements. Hence, by [11, Prop. 18.13], we can conclude that R/J^{∗} is Cohen-Macaulay. This proves (ii). In particular E_{αβ}^{∗} is equidimensional. But we know from Theorem 6.8 (iv) that E_{αβ} has exactly one irreducible component of dimension δ−2. This implies that \sqrt{J^{∗}} is prime and thus E_{αβ} is irreducible.

Remark 6.18. It appears likely that if {α, β} ⊆ I(k, n) is not close, then E^{∗}αβ is reduced (so that E_{αβ}^{∗} = E_{αβ}) and dim Sing E_{αβ} = δ − 5; this would then imply that E_{αβ} is Cohen-Macaulay and normal. In any case, it is clear already that the geometry of E_{αβ} seems to depend a lot on the combinatorial condition as to whether or not {α, β} is close.

Examples 6.19. Finally, in this section, we work out two examples, which nicely illustrate some of the results proved above.

1. Consider G_{2,4}, which is the simplest nontrivial Grassmannian. This is a hypersurface in ℙ^{5} of dimension δ = 4 and is defined by the equation

P_{12}P_{34} − P_{13}P_{24} + P_{14}P_{23} = 0.

Suppose α = (1, 2). Then E_{α} = G_{2,4}∩{P_{12} = 0} is like a projective cylinder over the affine cone defined by an equation of the form xw − yz = 0. Thus E_{α} is clearly irreducible of dimension 3; indeed, the ideal of E_{α} is like the principal ideal (xw − yz) in the polynomial ring F [x, y, z, w, u], and this ideal is clearly a prime ideal of height 1. Moreover the point defined by P_{12} = P_{13} = P_{24} = P_{14} = P_{23} = 0 and P_{34} = 1 is the only singular point of E_{α} and thus dim Sing E_{α} = 0 as is to be expected. Next, if β = (1, 3), then {α, β} is a close family and E_{αβ} is the union of the two planes Π_{1} and Π_{2} defined by P_{12} = P_{13} = P_{14} = 0 and P_{12} = P_{13} = P_{23} = 0 respectively. So, dim E_{αβ} = 2 and E_{αβ} has two irreducible components of dimension 2. Moreover, the singular locus of E_{αβ} is the line formed by the intersections of Π_{1} and Π_{2}. Thus dim Sing E_{αβ} = 1, as is to be expected. Finally, if γ = (1, 4), then Λ = {α, β, γ} is a close family of maximum possible cardinality and the corresponding E_{Λ} is isomorphic to ℙ^{2} so that it is irreducible of dimension δ −2. It may be noted that if we take a family such as Λ′ = {(1, 2), (1, 3), (3, 4)}, which is not close, then E_{Λ′} is isomorphic to a union of two ℙ^{1}’s and thus it is reducible of dimension < δ −2. On the other hand, if we let θ = (3, 4) and we take the 2-element family {α, θ}, which is not close then E_{αθ} is the determinantal hypersurface in ℙ^{4} given by an equation of the form xw − yz = 0. Thus E_{αθ} is irreducible (and Cohen-Macaulay) of dimension 2.

2. Consider G_{2,5}, which is a subvariety of ℙ^{9} of dimension δ = 6. It is not difficult to see that the following 5 quadratic relations determine G_{2,5}.

P_{12}P_{34} − P_{13}P_{24} + P_{14}P_{23} = 0;
P_{12}P_{45} − P_{14}P_{25} + P_{15}P_{24} = 0;
P_{12}P_{35} − P_{13}P_{25} + P_{15}P_{23} = 0;
P_{13}P_{45} − P_{14}P_{35} + P_{15}P_{34} = 0;
P_{23}P_{45} − P_{24}P_{35} + P_{25}P_{34} = 0.

Suppose α = (1, 2) and β = (1, 3). Consider E_{αβ} = G_{2,5}∩{P_{12} = P_{13} = 0}. Then from the above quadratic relations, we see that for any p ∈ E_{αβ}, we must have p_{23} = 0 or p_{14} = p_{15} = 0. It follows that E_{αβ} = V^{(1)} ∪ V^{(2)} where V^{(1)} and V^{(2)} are subvarieties of ℙ^{9} defined by

V^{(1)} = {P_{12} = P_{13} = P_{14} = P_{15} = 0 = P_{23}P_{45} − P_{24}P_{35} + P_{25}P_{34}}

and

\begin{aligned}V^{(2)} = \{P_{12} = P_{13} = P_{23} = 0 & = P_{14}P_{25} − P_{15}P_{24} \\ & = P_{14}P_{35} − P_{15}P_{34} = P_{24}P_{35} − P_{25}P_{34}\}. \end{aligned}

It is clear that V^{(1)} is isomorphic to G_{2,4} and thus it is irreducible of dimension 4. Further, V^{(2)} is isomorphic to a cylinder [since P_{45} is free] over a determinantal variety in ℙ^{5} defined by an ideal of the form

I_{2} ([ \begin{matrix}x & y & z \\ u & v & w \end{matrix} ])

that is generated by the 2 × 2 minors of a generic 2 × 3 matrix. It is well-known (cf. [8, Prop. 1.1]) therefore that the projective variety in ℙ^{5} corresponding to the ideal above is irreducible and has dimension 4−1 = 3. Therefore, V^{(2)} is also irreducible, and dim V^{(2)} = 3 + 1 = 4. So, the assertions (i) and (ii) of Theorem 6.8 are verified. Next, let γ = (1, 4), and consider E_{αβγ}. As in the case of E_{αβ}, we can easily see that for any p ∈ E_{αβγ}, we must have p_{15} = 0 or p_{23} = p_{24} = p_{25} = 0. It follows that E_{αβγ} is the union of two subvarieties, one isomorphic to G_{2,4} and the other isomorphic to ℙ^{3}. It may be noted that in this case E_{αβγ} is reducible of dimension 4 but it has only one irreducible component of dimension 4. Finally, consider Λ = {(1, 2), (1, 3), (1, 4), (1, 5)}, which is a close family of maximum possible cardinality. Then E_{Λ} is isomorphic to G_{2,4}, which is irreducible of dimension 4.

Note that if in G_{2,5}, we consider a 2-element family which is not close such as {α, θ}, where θ = (3, 4), then, the corresponding E_{αθ} turns out to be a projective variety in ℙ^{8} defined by an ideal of the form

I_{2} ([ \begin{matrix}x_{1} & x_{2} & x_{3} \\ x_{4} & x_{5} & x_{6} \\ x_{7} & x_{8} \end{matrix} ])

that is generated by the 2 × 2 minors of a ladder shaped subset of a generic 3 × 3 matrix. It may be remarked that such ladder determinantal varieties have recently been of interest and one knows that in general, they are irreducible (cf. [1, Thm. 20.16.4]), arithmetically Cohen-Macaulay (cf.

[18, Cor. 4.10]) and projectively normal (cf. [10, Prop. 3.3]). Also, from [18, Cor. 4.7] it can be seen that the dimension of E_{αθ} is 4. This confirms some of the results of Theorem 6.8 and Theorem 6.17 in the particular case of the linear section E_{αθ} of G_{2,5}.

We remark that the above decompositions of E_{αβ} (say) into irreducible components can be used to compute directly the number of 𝔽_{q}-rational points of E_{αβ}. It is interesting and instructive, especially in the second example, to do so and compare with the formula given by Corollary 3.3.

7. TABLES

In this section, we give some numerical data to compare, wherever possible, the lower bound L(q) = L(q; k, n) and the upper bound U(q) = U(q; k, n) for the number γ(q) = γ(q; k, n) of all (n, k)-MDS linear codes over 𝔽_{q}. It will be seen that the bounds quickly become better as q increases. Of course, the MDS codes may not always exist for a given set of parameters and in such a case the lower bound L(q) is usually negative. In fact, we can easily avoid these negative values and, in view of Remark 5.9, also make a minor improvement in the upper bound U(q) by replacing L(q) and U(q) by L̂(q) and Û(q), respectively, where the latter are defined by L̂(q) = max{L(q), 0} and Û(q) = min{U(q), q^{δ}}. However, in practice L(q) quickly becomes positive and U(q) quickly becomes smaller than q^{δ}.

(n, k) = (5, 2)
L(q) = -755
q = 2  γ(q) = 0
U(q) = 155
L(q) = -116945
q = 8  γ(q) = 72030
U(q) = 250180
L(q) = 752269015
q = 32  γ(q) = 803463270
U(q) = 834446500
L(q) = 4083938982775
q = 128 γ(q) = 4097278095750
U(q) = 4104293323300
L(q) = 17696499789458935
q = 512 γ(q) = 17699930414237190
U(q) = 17701667866691620
L(q) = 73462400307624392695
q = 2048 γ(q) = 73463279573643761670
U(q) = 73463720623898435620
L(q) = 301899332435640416395255
q = 8192 γ(q) = 301899557593636585365510
U(q) = 301899670263342869807140

\begin{aligned}& & (n, k) = (6, 2) \\ & L(q) = & -5274 \\ q = 2 & γ(q) = & 0 \\ & U(q) = & 651 \\ & L(q) = & 587426008626 \\ q = 32 & γ(q) = & 697406118360 \\ & U(q) = & 773487190971 \\ & L(q) = & 4592733883143010903026 \\ q = 512 & γ(q) = & 4594689536371003677720 \\ & U(q) = & 4595715252586834081371 \\ & L(q) = & 20247738819037735639138726461426 \\ q = 8192 & γ(q) = & 20247771753930719892728171053080 \\ & U(q) = & 20247788696637052969529490759771 \end{aligned} ; \begin{aligned}& & (n, k) = (6, 3) \\ & L(q) = & -16265 \\ q = 2 & γ(q) = & 0 \\ & U(q) = & 1395 \\ & L(q) = & 12924803540365 \\ q = 32 & γ(q) = & 18854872557090 \\ & U(q) = & 23274288377355 \\ & L(q) = & 2327775159087185688779245 \\ q = 512 & γ(q) = & 2329516639604540539808130 \\ & U(q) = & 2330369613207389653784235 \\ & L(q) = & 165768039589972820570950606406918125 \\ q = 8192 & γ(q) = & 165768509822290080011242807140458370 \\ & U(q) = & 165768733035888981455839539456467115 \end{aligned}

(n, k) = (7, 3)
L(q) = -258214
q = 2  γ(q) = 0
U(q) = 11811
L(q) = 14123647489168989269978846
q = 128 γ(q) = 14763973216014483920056080
U(q) = 15093570758315423135537841
L(q) = 5354042033282754906723825686066392657886
q = 2048 γ(q) = 5354784455399714241650925286098021465360
U(q) = 5355088314817274002456447976702416620081

(n, k) = (8, 3)
L(q) = -3508517
q = 2  γ(q) = 0
U(q) = 97155
L(q) = 22859051508168206183682487379017
q = 128 γ(q) = 26143755283265696967345957437040
U(q) = 27818370911486822148299133905997
L(q) = 38858929850431024228647936374271440818633
q = 512 γ(q) = 39096878508416888436124942798204100945520
U(q) = 39186366672436705546578090425688010235853

(n, k) = (9, 3)
L(q) = -43386809
q = 2  γ(q) = 0
U(q) = 788035
L(q) = 29035501732844392930104338279237572141
q = 128 γ(q) = 43680038826242120201491233198224596320
U(q) = 51566850324744464560126628177426264779

We can also consider the case when (n, k) = (10, 3), where no exact formula is known but the lower and upper bounds can still be computed. If we compute these as q runs over powers of 2, we don’t get any interesting information till q = 64 because for q ≤ 32, L(q) is negative while U(q) is positive. Later, however L(q) is a fairly large positive integer, and, the difference between L(q) and U(q) becomes relatively small. For instance, the first four digits of L(q) and U(q) are identical, for q = 2048. This time we avoid making a table since the numbers involved are quite huge.

Finally, we remark that the tables above have been prepared using Mathematica. A more extensive data is also available. Anyone interested in this data and/or a copy of the relevant Mathematica programs, may send an e-mail to the first author.

ACKNOWLEDGMENT

This research was partly supported by the Indo-French Mathematical Research Program of the Centre National de la Recherche Scientifique (CNRS) of France and the National Board for Higher Mathematics (NBHM) of India, and we thank these organizations for their support. We would also like to express our warm gratitude to Robert Rolland, Alexeï Skorobogatov, Murali Srinivasan and Michael Tsfasman for a number of helpful discussions, and to Sameer D’Costa for writing the Mathematica programs to generate the tables in Section 7.

REFERENCES

1. S. S. Abhyankar, “Enumerative Combinatorics of Young Tableaux”, Marcel Dekker, New-York, 1988.

2. H. H. Andersen, Schubert varieties and Demazure’s character formula, Invent. Math. 79 (1985), 611–618.

3. G. E. Andrews, “Theory of Partitions”, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley, Reading, Mass., 1976.

4. B. Bollobás, “Combinatorics : set systems, hypergraphs, families of vectors, and combinatorial probability”, Cambridge Univ. Press, Cambridge, 1986.

5. R. Bott and L. W. Tu, “Differential forms in Algebraic Topology”, Springer-Verlag, New York, 1980.

6. A. Blokhuis, A. A. Bruen and J. A. Thas, Arcs in P G(n, q), MDS-codes, and three fundamental problems of B. Segre—some extensions, Geom. Dedicata 35 (1991), 1–11.

7. A. A. Bruen, J. A. Thas and A. Blokhuis, On M.D.S. codes, arcs in P G(n, q) with q even, and a solution of three fundamental problems of B. Segre, Invent. Math. 92 (1988), 441–459.

8. W. Bruns and U. Vetter, “Determinantal Rings”, Lecture Notes in Math., Vol. 1327, Springer-Verlag, Berlin, 1988.

9. L. Comtet, “Advanced Combinatorics”, D. Reidel, Dordrecht-Holland, 1974.

10. A. Conca, Ladder determinantal rings, . J. Pure and Appl. Algebra 98 (1995), 119– 11. D. Eisenbud, “Commutative Algebra with a view towards Algebraic Geometry”,

Grad. Texts in Math., Vol. 150, Springer-Verlag, New-York, 1995.

12. S. R. Ghorpade, Young multitableaux and higher dimensional determinants, Adv. Math. 121 (1996), 167–195.

13. S. R. Ghorpade and G. Lachaud, Higher weights of Grassmann codes, in “Coding Theory, Cryptography and Related Areas” (J. Buchmann, T. Hoeholdt, H. Stichtenoth, H. Tapia-Recillas, Eds.), pp. 122-131, Springer-Verlag, Berlin/Heidelberg, 2000.

14. S. R. Ghorpade and G. Lachaud, Étale cohomology, Lefschetz theorems, and number of points of singular varieties over finite fields, Prétirage n^{∘} 99-13 (45 pp.), Institut de Mathématiques de Luminy, Marseille, France, 1999.

15. D. Glynn, Rings of geometries, II, J. Combin. Theory Ser. A 49 (1988), 26–66.

16. J. M. Goethals, A polynomial approach to linear codes, Philips Research Reports 24 (1969), 145–159.

17. J. Goldman and G.-C. Rota, 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.

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

19. J. W. P. Hirschfeld and J. A. Thas, “General Galois Geometries”, Oxford Univ. Press, Oxford, 1991.

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

21. M. Hochster, Grassmannians and their Schubert subvarieties are arithmetically Cohen-Macaulay, J. Algebra 25 (1973), 40–57.

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

23. A. I. Iampolskaia, A. N. Skorobogatov, and E. A. Sorokin, Formula for the number of [9, 3] MDS codes, IEEE Trans. Inform. Theory 41 (1995), 1667–1671.

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

25. G. Lachaud, Number of points of linear codes defined on algebraic varieties, in “Arithmetic, Geometry and Coding theory” (R. Pellikan, M. Perret, S. G. Vlăduţ, Eds.), pp. 77–104, Walter de Gruyter, Berlin/New York, 1996.

26. V. Lakshmibai and J. Weyman, Multiplicity of points on a Schubert variety in a miniscule G/P, Adv. Math. 84 (1990), 179–208.

27. D. Laksov, The arithmetic Cohen-Macaulay character of Schubert schemes, Acta. Math. 129 (1972), 1–9.

28. A. Lascoux, “Polynôme symétriques, Foncteurs de Schur et Grassmanniennes”, Thèse, Université de Paris VII, 1977.

29. F. J. MacWilliams and N. J. A. Sloane, “The Theory of Error Correcting Codes”, North Holland, Amsterdam, 1977.

30. H. Matsumura, “Commutative Algebra”, 2nd Ed., Benjamin/Cummings, Reading, Mass., 1980.

31. V. B. Mehta and V. Srinivas, Normality of Schubert varieties, Amer. J. Math. 109 (1987), 987–989.

32. J. S. Milne, “Étale cohomology”, Princeton Math. Series vol. 33, Princeton University Press, Princeton, 1980.

33. N. E. Mnëv, On manifolds of combinatorial types of projective configurations and convex polytopes, Soviet Math. Doklady 32:1 (1985), 335–337.

34. C. Musili, Postulation formula for Schubert varieties, J. Indian Math. Soc. 36 (1972), 143–171.

35. D. Yu. Nogin, 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.

36. U. Oberst and A. Dür, A constructive characterization of all optimal linear codes, in, “Seminaire d’Algebre” (P. Dubriel, M. P. Malliavin, Eds.), Lecture Notes in Math., Vol. 1146, pp. 176–213, Springer–Verlag, Berlin, 1985.

37. S. Ramanan and A. Ramanathan, Projective normality of flag varieties and Schubert varieties, Invent. Math. 79 (1985), 217–224.

38. R. Rolland, The number of MDS [7,3] codes on finite fields of characteristic 2, Appl. Algebra Engrg. Comm. Comput. 3 (1992), 301–310.

39. R. Rolland and A. N. Skorobogatov, Dénombrement de configurations dans le plan projectif, in “Arithmetic, Geometry and Coding theory” (R. Pellikan, M. Perret, S. G. Vlăduţ, Eds.), pp. 199–207, Walter de Gruyter, Berlin/New York, 1996.

40. C. S. Seshadri, Line bundles on Schubert varieties, in “Vector Bundles on Algebraic Varieties” (Papers presented at the Bombay Colloquium, 1984), pp. 495–528, Oxford Univ. Press, Bombay, 1987.

41. A. N. Skorobogatov, Linear codes, strata of Grassmannians and the problems of Segre, in “Coding Theory and Algebraic Geometry” (H. Stichtenoth and M. A. Tsfasman, Eds.), Lecture Notes in Math., Vol. 1518, pp. 210–223, Springer–Verlag, Berlin, 1992.

42. A. N. Skorobogatov, On the number of representations of matroids over finite fields, Des. Codes Cryptogr. 9 (1996), 215–226.

43. T. Svanes, Coherent cohomology on Schubert subschemes of flag schemes and applications, Adv. Math. 14 (1974), 369–453.

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

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

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