DUALS OF AFFINE GRASSMANN CODES AND THEIR RELATIVES

PETER BEELEN, SUDHIR R. GHORPADE, AND TOM HØHOLDT

Abstract. Affine Grassmann codes are a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. These codes were introduced in a recent work [2]. Here we consider, more generally, affine Grassmann codes of a given level. We explicitly determine the dual of an affine Grassmann code of any level and compute its minimum distance. Further, we ameliorate the results of [2] concerning the automorphism group of affine Grassmann codes. Finally, we prove that affine Grassmann codes and their duals have the property that they are linear codes generated by their minimum-weight codewords. This provides a clean analogue of a corresponding result for generalized Reed-Muller codes.

1. Introduction

Fix a finite field 𝔽_{q} with q elements and positive integers ℓ, ℓ′ with ℓ ≤ ℓ′; set

m = ℓ + ℓ′ and δ = ℓℓ′.

Briefly put, the affine Grassmann code C^{𝔸}(ℓ, m) is the q-ary linear code obtained by evaluating linear polynomials in the minors of a generic ℓ×ℓ′ matrix X at all points of the δ-dimensional affine space of ℓ×ℓ′ matrices with entries in 𝔽_{q}. Evidently, when ℓ = 1, this gives the first order generalized Reed-Muller code RM(1, ℓ′). However, in general, C^{𝔸}(ℓ, m) is only a subcode of the ℓ^{th} order generalized Reed-Muller code RM(ℓ, δ). The length n and the dimension k of C^{𝔸}(ℓ, m) are given by

n = q^{δ} and k = \binom{m}{ℓ}.

Affine Grassmann codes were introduced in [2], where the following was shown. • The minimum distance of C^{𝔸}(ℓ, m) is

d(ℓ, m) := q^{δ−ℓ^{2}} ∏_{j=0}^{ℓ−1}(q^{ℓ} − q^{j}) = q^{δ} ∏_{i=1}^{ℓ} (1 − \frac{1}{q^{i}} ) .  (1)

• The (permutation) automorphism group of C^{𝔸}(ℓ, m) contains a subgroup isomorphic to the semidirect product M_{ℓ×ℓ′}(𝔽_{q})⋊_{θ} GL_{ℓ′}(𝔽_{q}) of the additive group of ℓ × ℓ′ matrices over 𝔽_{q} with the multiplication group of ℓ′ × ℓ′ nonsingular matrices over 𝔽_{q}, where θ : GL_{ℓ′}(𝔽_{q}) → Aut(M_{ℓ×ℓ′}(𝔽_{q})) is the homomorphism defined by θ(A)(u) := uA^{−1}.

• The minimum-weight codewords of C^{𝔸}(ℓ, m) are precisely the evaluations of leading maximal minors (formed by the ℓ rows and the first ℓ columns) of X′, where X′ = XA^{−1} + u for some A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}).

• The number of minimum-weight codewords of C^{𝔸}(ℓ, m) is given, in terms of the Gaussian binomial coefficients (defined below for any a ≥ b ≥ 0), by

(q − 1)q^{ℓ^{2}} \left[{ℓ′ \atop ℓ}\right]_{q} where \left[{a \atop b}\right]_{q} := \frac{(q^{a} − 1)(q^{a} − q) ⋯ (q^{a} − q^{b−1})}{(q^{b} − 1)(q^{b} − q) ⋯ (q^{b} − q^{b−1})}.  (2)

Date: November 5, 2011.

In this paper we continue the study of affine Grassmann codes and give an explicit description of the dual of C^{𝔸}(ℓ, m). As a result, it will be seen that affine Grassmann codes are almost always self-orthogonal. Moreover, we determine precisely the minimum distance of C^{𝔸}(ℓ, m)^{⊥} and show that it is at most 4. Thus, it is seen that the parity check matrix of C^{𝔸}(ℓ, m) is rather sparse and that an affine Grassmann code may be regarded as a LDPC code. Further, following a suggestion by an anonymous referee of [2], we augment the abovementioned result on the automorphism group of C^{𝔸}(ℓ, m) by showing that Aut(C) contains, in fact, a larger group that is essentially obtained by taking the product of the general linear group GL_{ℓ}(𝔽_{q}) with the semidirect product M_{ℓ×ℓ′}(𝔽_{q}) ⋊_{θ} GL_{ℓ′}(𝔽_{q}). It will also be seen that the full automorphism group can, in fact, be even larger. Finally, we show that the affine Grassmann codes as well as their duals have the property that the minimum-weight codewords generate the code. This can be viewed as an analogue of the classical result that binary Reed-Muller codes are generated by their minimum-weight codewords; see, e.g., MacWilliams and Sloane [9, Ch. 13, §6]. Such a result is not true, in general, for q-ary generalized Reed-Muller codes, and in this case, a complete characterization of generation by the minimum-weight codewords was obtained by Ding and Key [5, Thm. 1] (see also part (v) of Proposition 4 below). A special case ℓ = 1 of our results corresponds to their result for the generalized Reed-Muller codes RM(1, δ) and RM(δ(q − 1) − 2, δ).

Following a suggestion of D. Augot, we shall consider in this paper a mild generalization of C^{𝔸}(ℓ, m) obtained by choosing a nonnegative integer r ≤ ℓ and then restricting the function space to linear polynomials in the i×i minors of X for i ≤ r. The resulting linear codes are denoted by C^{𝔸}(ℓ, m; r) and called affine Grassmann codes of level r. Note that the first order Reed-Muller codes of length q^{δ} as well as the affine Grassmann codes are special cases; indeed, C^{𝔸}(ℓ, m; 1) = RM(1, δ) and C^{𝔸}(ℓ, m; ℓ) = C^{𝔸}(ℓ, m). Moreover, by varying the levels, we obtain a nice filtration, compatible with the Reed-Muller filtration:

C^{𝔸}(ℓ, m; 1) ⊂ C^{𝔸}(ℓ, m; 2) ⊂ ⋯ ⊂ C^{𝔸}(ℓ, m; ℓ)
∥ ⋂ ⋂
RM(1, δ) ⊂ RM(2, δ) ⊂ ⋯ ⊂ RM(ℓ, δ)

In general, for any r ≥ 0, the length n and the dimension k_{r} of C^{𝔸}(ℓ, m; r) are given by

n = q^{δ} and k_{r} = ∑_{i=0}^{r} \binom{ℓ}{i}\binom{ℓ′}{i},  (3)

whereas the formula (1) generalizes nicely to the following:

minimum distance of C^{𝔸}(ℓ, m; r) = q^{δ} ∏_{i=1}^{r} (1 − \frac{1}{q^{i}} ) .  (4)

The augmentation of the result concerning the automorphism group, an explicit description of the dual, determination of the minimum distance of the dual, and the result concerning generation by minimum-weight codewords are all obtained more generally, in the case of affine Grassmann codes of any given level. However, for the duals C^{𝔸}(ℓ, m; r)^{⊥}, it is shown that generation by minimum-weight codewords is valid for r = 1 and r = ℓ, but not, in general, for 1 < r < ℓ.

2. Preliminaries

Let X = (X_{ij}) be a ℓ × ℓ′ matrix whose entries are algebraically independent indeterminates over 𝔽_{q}. By R we denote the integral rectangle [1, ℓ] × [1, ℓ′], i.e.,

R := {(i, j) ∈ ℤ^{2} : 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′} .

By 𝔽_{q}[X] we denote the polynomial ring in the ℓℓ′ variables X_{ij} (where (i, j) vary over R) with coefficients in 𝔽_{q}. The set of all monomials in 𝔽_{q}[X] will be denoted by 𝕄(ℓ, m). Note that every μ ∈ 𝕄(ℓ, m) is of the form

μ = ∏_{(i,j)∈R} X_{ij}^{α_{ij}} for some nonnegative integers α_{ij}

The exponents α_{ij} ((i, j) ∈ R) are uniquely determined by μ and their sum is denoted by deg μ; also, we write deg_{X_{ij}} μ = α_{ij}. We say that the monomial μ is reduced (resp: squarefree) if 0 ≤ deg_{X_{ij}} μ ≤ q − 1 (resp: 0 ≤ deg_{X_{ij}} μ ≤ 1) for all (i, j) ∈ R. These two notions coincide when q = 2. The set of all reduced monomials in 𝔽_{q}[X] will be denoted by \overline{𝕄}(ℓ, m) and the 𝔽_{q}-linear space generated by \overline{𝕄}(ℓ, m) will be denoted by ℜ(ℓ, m). Elements of ℜ(ℓ, m) are called reduced polynomials. There is a natural surjective map from 𝕄(ℓ, m) to \overline{𝕄}(ℓ, m) that sends a monomial μ to the unique monomial μ̄ obtained from μ as follows: whenever an exponent α_{ij} of X_{ij} is ≥ q, replace it by r_{ij}, where r_{ij} ≡ α_{ij}(mod q − 1) and 1 ≤ r_{ij} ≤ q − 1. This map extends by 𝔽_{q}-linearity to a surjective 𝔽_{q}-vector space homomorphism 𝔽_{q}[X] → ℜ(ℓ, m), which may be referred to as the reduction map. We will denote the image of f ∈ 𝔽_{q}[X] under the reduction map by f̄, and call f̄ the reduced polynomial corresponding to f.

The set 𝕄(ℓ, m) is obviously a 𝔽_{q}-basis of 𝔽_{q}[X] and hence every f ∈ 𝔽_{q}[X] can be uniquely written as ∑_{μ∈𝕄(ℓ,m)} c_{μ}μ, where c_{μ} ∈ 𝔽_{q} for each μ ∈ 𝕄(ℓ, m) and c_{μ} = 0 for all except finitely many μ’s. A monomial μ for which c_{μ} ≠ 0 will be referred to as a term of f, and we let

Term(f) := {μ ∈ 𝕄(ℓ, m) : c_{μ} ≠ 0} .

Note that Term(f) is the empty set if and only if f is the zero polynomial. For 0 ≠ f ∈ 𝔽_{q}[X], the (total) degree and the degree in the variable X_{ij} are given by

deg f := max{deg μ : μ ∈ Term(f)} and deg_{X_{ij}} f := max{deg_{X_{ij}} μ : μ ∈ Term(f)}.

We shall denote the space of all ℓ × ℓ′ matrices with entries in 𝔽_{q} by 𝔸^{δ} (𝔽_{q}), or simply by 𝔸^{δ}. Fix an enumeration P_{1}, P_{2}, …, P_{q^{δ}} of 𝔸^{δ}. The map

Ev : 𝔽_{q}[X] → 𝔽_{q}^{q^{δ}} defined by Ev(f) := (f(P_{1}), …, f(P_{q^{δ}}))

will be referred to as the evaluation map of 𝔽_{q}[X]. It is clear that the evaluation map Ev defined above is a surjective linear map, and also that Ev(f) = Ev(f̄) for every f ∈ 𝔽_{q}[X]. Thus, the restriction of Ev to ℜ(ℓ, m) is also surjective. In fact, it is well-known that this restriction is injective as well. (See, e.g., [7, p. 11].) In other words, reduced polynomials can be identified with functions from 𝔸^{δ} to 𝔽_{q}.

Remark 1. Although the reduction map from 𝔽_{q}[X] onto ℜ(ℓ, m) is 𝔽_{q}-linear, it is not multiplicative, i.e., \overline{fg} need not be equal to f̄ḡ, in general. In fact, the product of reduced monomials need not be a reduced monomial. However, if f, g ∈ 𝔽_{q}[X] are polynomials in disjoint sets of variables, then \overline{fg} = f̄ḡ.

Recall that by a minor of X of order i we mean the determinant of an i × i submatrix of X. A minor of X of order i is sometimes referred to as an i × i minor of X. For 0 ≤ i ≤ ℓ, let Δ_{i}(ℓ, m) be the subset of 𝔽_{q}[X] consisting of all i × i minors of X, where, as per standard conventions, the only 0 × 0 minor of X is 1. For 0 ≤ r ≤ ℓ, we define

Δ(ℓ, m; r) := ⋃_{i=0}^{r} Δ_{i}(ℓ, m)

and F(ℓ, m; r) to be the 𝔽_{q}-linear subspace of 𝔽_{q}[X] generated by Δ(ℓ, m; r). Often Δ(ℓ, m; ℓ) and F(ℓ, m; ℓ) will just be denoted by Δ(ℓ, m) and F(ℓ, m), respectively.

Observe that deg_{X_{ij}} M ≤ 1 for all M ∈ Δ(ℓ, m) and (i, j) ∈ R. In particular, F(ℓ, m) ⊆ ℜ(ℓ, m). Next, we record the following basic result. It is an easy consequence of Lemma 2 of [2] and its proof together with Lemma 3 of [2].

Proposition 2. For every r ∈ {0, 1, …, ℓ}, the elements of Δ(ℓ, m; r) are linearly independent. In particular,

dim_{𝔽_{q}} F(ℓ, m; r) = ∑_{i=0}^{r} \binom{ℓ}{i}\binom{ℓ′}{i} and dim_{𝔽_{q}} F(ℓ, m) = \binom{m}{ℓ}.

Thanks to Proposition 2, every f ∈ F(ℓ, m) is a unique 𝔽_{q}-linear combination of the elements of Δ(ℓ, m), say f = ∑_{M∈Δ(ℓ,m)} a_{M}M, where a_{M} ∈ 𝔽_{q} for every M ∈ Δ(ℓ, m). We define the support of f to be the set

supp(f) := {M ∈ Δ(ℓ, m) : a_{M} ≠ 0}.

Note that the support of f is the empty set if and only if f is the zero polynomial. Also note that for 0 ≤ r ≤ ℓ and f ∈ F(ℓ, m; r), the sets supp(f) and Term(f) coincide only when r ≤ 1.

For any nonnegative integer r ≤ ℓ, the image of F(ℓ, m; r) under the evaluation map Ev will be denoted by C^{𝔸}(ℓ, m; r) and called the affine Grassmann code of level r. As in [2], we will write C^{𝔸}(ℓ, m) = C^{𝔸}(ℓ, m; ℓ) and refer to this simply as the affine Grassmann code (corresponding to the fixed parameters ℓ and ℓ′, or equivalently, ℓ and m). The following result is a consequence of Proposition 2. Its proof is similar to that of Lemma 7 of [2], and is hence omitted.

Proposition 3. For each r ∈ {0, 1, …, ℓ}, the affine Grassmann code of level r is a nondegenerate linear code of length n and dimension k_{r} given by (3).

Finally, in this section we review some basic facts about generalized Reed-Muller codes, which will be useful in the sequel. First, recall that for any nonnegative integer r ≤ δ(q − 1), the r^{th} order generalized Reed-Muller code of length q^{δ}, denoted RM_{q}(r, δ) or simply RM(r, δ), is the image of {μ ∈ ℜ(ℓ, m) : deg μ ≤ r} under the evaluation map Ev. Some of its fundamental properties are the following.

Proposition 4. Let r be a nonnegative integer ≤ δ(q − 1), and let Q, R be unique integers such that δ(q − 1) − r = Q(q − 1) + R and 0 ≤ R < q − 1. Then:

(i) RM(r, δ) is nondegenerate linear code of length q^{δ} and

dim RM(r, δ) = ∑_{i=0}^{r} ∑_{j=0}^{δ}(−1)^{j}\binom{δ}{j}\binom{δ + i − jq − 1}{i − jq}.

In particular, if r ≤ q − 1, then the dimension of RM(r, δ) is \binom{δ+r}{r}. (ii) The minimum distance of RM(r, δ) is (R+1)q^{Q} and the number of minimumweight codewords of RM(r, δ) is given, in terms of the Gaussian binomial coefficients (defined in (2) above), by

\begin{cases}(q^{δ−Q+1} − q^{δ−Q}) \left[{δ \atop Q}\right]_{q} & if R = 0, \\ (q^{δ} − q^{δ−Q−1}) \left[{δ \atop Q + 1}\right]_{q}\binom{q}{R + 1} & if R > 0. \end{cases}

(iii) If r ≥ 1, then the (permutation) automorphism group of RM(r, δ) is isomorphic to the affine general linear group AGL_{δ}(𝔽_{q}) of transformations 𝔽_{q}^{δ} → 𝔽_{q}^{δ} of the form x ↦ Mx + u, where M ∈ GL_{δ}(𝔽_{q}) and u ∈ 𝔽_{q}^{δ}.

(iv) The dual of RM(r, δ) is RM(δ(q − 1) − r − 1, δ).

(v) Write q = p^{t}, where p is a prime number and t ≥ 1. Then RM(r, δ) is generated by its minimum-weight codewords if and only if δ = 1 or t = 1 or r < p or r > (δ − 1)(q − 1) + p^{t−1} − 2.

A proof of the assertions in Proposition 4 can be found, for example, in: [1, §5.4] (parts (i) and (iv)), [4] (part (ii)), [3] (part (iii)), and [5] (part (v)).

3. Minimum distance

For a positive integer r ≤ ℓ, we shall denote by L_{r} the r^{th} leading principal minor of the ℓ × ℓ′ matrix X. In other words, L_{r} is the determinant of the submatrix of X formed by the first r rows and the first r columns. Also, we set L_{0} := 1. Often we write L_{ℓ} simply as L and refer to it as the leading maximal minor.

Theorem 5. Let r be a nonnegative integer ≤ ℓ. Then

minimum distance of C^{𝔸}(ℓ, m; r) = q^{δ} ∏_{i=1}^{r} (1 − \frac{1}{q^{i}} ) .  (5)

Moreover, Ev (L_{r}) is a minimum-weight codeword of C^{𝔸}(ℓ, m; r).

Proof. Let f ∈ F(ℓ, m; r) be such that f ≠ 0. Then there is a nonnegative integer s ≤ r such that supp(f)∩Δ_{s}(ℓ, m) is nonempty, but supp(f)∩Δ_{i}(ℓ, m) is empty for each i > s. Choose a minor M ∈ supp(f)∩Δ_{s}(ℓ, m) and let Y be the corresponding s × s submatrix of X. In view of Proposition 2, any specialization f̃ of f, obtained by substituting arbitrary values in 𝔽_{q} for the δ − s^{2} variables not occurring in Y, is a nonzero linear combination of minors of Y. It follows that

w_{H} (Ev(f)) ≥ d(s, 2s)q^{δ−s^{2}},

where w_{H}(c) denotes the the (Hamming) weight of a codeword c and d(s, 2s) denotes the minimum distance of the affine Grassmann code C^{𝔸}(s, 2s) corresponding to the s × s matrix Y. Using (1) (i.e., Theorem 16 of [2]) with ℓ = ℓ′ = s, we see that

w_{H} (Ev(f)) ≥ (q^{s^{2}} ∏_{i=1}^{s} (1 − \frac{1}{q^{i}} )) q^{δ−s^{2}} ≥ q^{δ} ∏_{i=1}^{r} (1 − \frac{1}{q^{i}} ) .

On the other hand, it is readily seen that L_{r} ∈ F(ℓ, m; r) and

w_{H} (Ev (L_{r})) = q^{δ−r^{2}}#GL_{r}(𝔽_{q}) = q^{δ−r^{2}} ∏_{j=0}^{r−1} (q^{r} − q^{j}) = q^{δ} ∏_{i=1}^{r} (1 − \frac{1}{q^{i}} ) .

This yields (5) and also shows that Ev (L_{r}) is a minimum-weight codeword. □

It may be tempting to believe that, as in the case of affine Grassmann codes, every minimum-weight codeword of C^{𝔸}(ℓ, m; r) is essentially of the form L_{r}, i.e., it is equal to Ev (L′), where L′ is the r^{th} leading principal minor of the ℓ × ℓ′ matrix X′, where X′ = XA^{−1} + u for some A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). However, the following example shows that if r < ℓ, then this need not be the case even when X′ is, more generally, of the form BXA^{−1} + u, where A, u are as above and B ∈ GL_{ℓ}(𝔽_{q}).

Example 6. Assume that ℓ ≥ 2 and let (c_{ij}) be any ℓ×ℓ′ matrix over 𝔽_{q} of rank ≥ 2. Then some 2 × 2 minor of (c_{ij}) is nonzero. Consider C^{𝔸}(ℓ, m; 1) = RM(1, δ). We know from Reed-Muller theory (or alternatively, Remark 11 of [2]) that any linear polynomial in 𝔽_{q}[X] in which some X_{ij} occurs with a nonzero coefficient gives rise to a minimum-weight codeword. In particular, Ev(f) is a minimum-weight codeword of C^{𝔸}(ℓ, m; 1), where

f = ∑_{i=1}^{ℓ} ∑_{j=1}^{ℓ′} c_{ij}X_{ij}.

However, f is not the first leading principal minor of any ℓ × ℓ′ matrix of the form BXA + u. Indeed if this were the case for some B = (b_{ij}) ∈ GL_{ℓ}(𝔽_{q}), A = (a_{ij}) ∈ GL_{ℓ′}(𝔽_{q}), and u = (u_{ij}) ∈ M_{ℓ×ℓ′}(𝔽_{q}), then

∑_{i=1}^{ℓ} ∑_{j=1}^{ℓ′} c_{ij}X_{ij} = u_{11} + ∑_{i=1}^{ℓ} ∑_{j=1}^{ℓ′} b_{1i}X_{ij}a_{j1}.

Consequently, u_{11} = 0 and c_{ij} = b_{1i}a_{j1} for 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′. But this is a contradiction since it is readily seen that every 2 × 2 minor of the ℓ × ℓ′ matrix (b_{1i}a_{j1}) is always zero.

4. Automorphisms

Recall that the (permutation) automorphism group Aut(C) of a code C ⊆ 𝔽_{q}^{n} is the set of all permutations σ of {1, …, n} such that (c_{σ(1)}, …, c_{σ(n)}) ∈ C for all c = (c_{1}, …, c_{n}) ∈ C. Evidently, Aut(C) is a subgroup of the symmetric group S_{n} on {1, …, n}. In this section, we shall observe that the result stated in the introduction about the automorphism groups of affine Grassmann codes being large can be extended a little further.

For any B ∈ GL_{ℓ}(𝔽_{q}), A ∈ GL_{ℓ′}(𝔽_{q}), and u ∈ M_{ℓ×ℓ′}(𝔽_{q}), define

ψ_{u,A,B} : 𝔸^{δ} (𝔽_{q}) → 𝔸^{δ} (𝔽_{q})

to be the affine transformation given by

ψ_{u,A,B}(P) = BP A^{−1} + u for P = (p_{ij})_{1≤i≤ℓ, 1≤j≤ℓ′} ∈ 𝔸^{δ} (𝔽_{q}) ,

It is clear that the transformation ψ_{u,A,B} gives a bijection of 𝔸^{δ} (𝔽_{q}) = {P_{1}, …, P_{n}} onto itself, and hence there is a unique permutation σ of {1, …, n} such that

(ψ_{u,A,B}(P_{1}), …, ψ_{u,A,B}(P_{n})) = (P_{σ(1)}, …, P_{σ(n)}) .

We shall denote this permutation σ by σ_{u,A,B} and for any c = (c_{1}, …, c_{n}) ∈ 𝔽_{q}^{n}, we will often write σ_{u,A,B}(c) for the n-tuple (c_{σ(1)}, …, c_{σ(n)}).

Lemma 7. Let r be a nonnegative integer ≤ ℓ and let B ∈ GL_{ℓ}(𝔽_{q}), A ∈ GL_{ℓ′}(𝔽_{q}), and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Then σ_{u,A,B} ∈ Aut (C^{𝔸}(ℓ, m; r)).

Proof. From Lemma 18 of [2] and with its proof, we know that if f = f(X) is in F(ℓ, m; r), then f(XA^{−1} + u) ∈ F(ℓ, m; r). Now consider the product BX and let s be any integer with 0 ≤ s ≤ r. Observe that any s × s minor of BX is of the form det(B_{s}X^{s}), where B_{s} is a s × ℓ submatrix of B and X^{s} is a ℓ × s submatrix of X. Hence by the Cauchy-Binet formula (cf. [2, Lemma 10]), every s × s minor of BX is a 𝔽_{q}-linear combination of s × s minors of X. Consequently, if f ∈ F(ℓ, m; r), then f(BXA^{−1} + u) ∈ F(ℓ, m; r). Moreover,

σ_{u,A,B} (Ev(f)) = (f(ψ_{u,A,B}(P)))_{P ∈𝔸^{δ}(𝔽_{q})} = Ev (f(BXA^{−1} + u)) .

It follows that σ_{u,A,B} ∈ Aut(C), where C = C^{𝔸}(ℓ, m; r) = Ev (F(ℓ, m; r)). □

Notice that ψ_{0,I_{ℓ′} ,I_{ℓ}} is the identity transformation of 𝔸^{δ}, where 0 denotes the zero matrix in M_{ℓ×ℓ′}(𝔽_{q}) and I_{ℓ′} (resp: I_{ℓ}) denotes the ℓ′ × ℓ′ (resp: ℓ × ℓ) identity matrix over 𝔽_{q}. Moreover, given any A, A′ ∈ GL_{ℓ′}(𝔽_{q}), B, B′ ∈ GL_{ℓ}(𝔽_{q}), and u, v ∈ M_{ℓ×ℓ′}(𝔽_{q}), we have

ψ_{u,A,B} ∘ ψ_{v,A′,B′} = ψ_{w,AA′,BB′} and ψ_{u,A,B}^{−1} = ψ_{u′,A^{−1},B^{−1}},  (6)

where w := BvA^{−1} + u and u′ = −B^{−1}uA. It follows that

ℌ(ℓ, m) := {ψ_{u,A,B} : A ∈ GL_{ℓ′}(𝔽_{q}), B ∈ GL_{ℓ}(𝔽_{q}), and u ∈ M_{ℓ×ℓ′}(𝔽_{q})}

is a group with respect to composition of maps. We determine the group structure of ℌ(ℓ, m) in the following result, which is an analogue of Proposition 20 of [2].

Proposition 8. Let Γ(ℓ, ℓ′) denote the factor group G/Z, where G is the direct product GL_{ℓ}(𝔽_{q}) × GL_{ℓ′}(𝔽_{q}) and Z is the normal subgroup of G given by {(λI_{ℓ}, λI_{ℓ′}) : λ ∈ 𝔽_{q}^{∗}}. Then as a group ℌ(ℓ, m) is isomorphic to the semidirect product M_{ℓ×ℓ′}(𝔽_{q}) ⋊_{θ} Γ(ℓ, ℓ′), where θ : Γ(ℓ, ℓ′) → Aut(M_{ℓ×ℓ′}(𝔽_{q})) is a group homomorphism defined by θ ((B, A)Z) (u) := BuA^{−1}.

Proof. It is easy to check that θ is well-defined and that it is a group homomorphism. Let η : M_{ℓ×ℓ′}(𝔽_{q})⋊_{θ}Γ(ℓ, ℓ′) → ℌ(ℓ, m) be the map given by (u, (B, A)Z) ↦ ψ_{u,A,B}. Clearly, η is well-defined and surjective. Moreover, from (6) it is readily seen that η is a group homomorphism. Finally, suppose (u, (B, A)Z) is in the kernel of η for some B ∈ GL_{ℓ}(𝔽_{q}), A ∈ GL_{ℓ′}(𝔽_{q}), and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Then

BP A^{−1} + u = P for all P ∈ 𝔸^{δ} (𝔽_{q}) .  (7)

Taking P to be the zero matrix in (7), we obtain u = 0. Next, write B = (b_{ij}) and A^{−1} = (a′_{ij}) and let us fix any r, s ∈ ℤ with 1 ≤ r ≤ ℓ and 1 ≤ s ≤ ℓ′. Taking P to be the ℓ × ℓ′ matrix E_{rs}, with 1 in (r, s)^{th} spot and 0 elsewhere, in (7), we obtain

b_{ir} a′_{sj} = \begin{cases}1 & if (i, j) = (r, s), \\ 0 & if (i, j) ≠ (r, s), \end{cases} for 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′.  (8)

In particular, b_{rr} ≠ 0 and a′_{ss} ≠ 0. Now taking j = s in (8), we obtain b_{ir} = 0 for i ≠ r. Likewise, a′_{sj} = 0 for j ≠ s. It follows that B and A^{−1} are diagonal matrices. Furthermore, thanks to (8), we have b_{11}a′_{11} = ⋯ = b_{ℓℓ}a′_{11} = 1 and b_{11}a′_{11} = ⋯ = b_{11}a′_{ℓ′ℓ′} = 1, and therefore B = λI_{ℓ} and A^{−1} = λ^{−1}I_{ℓ′} for some λ ∈ 𝔽_{q}^{∗}. This shows that the coset of (B, A) in G/Z is the identity element. Thus η is an isomorphism. □

It may be noted that C^{𝔸}(ℓ, m; 0) is a one-dimensional code of length n = q^{δ} spanned by (1, 1, …, 1) and thus its automorphism group is the full symmetric group S_{n}. For affine Grassmann codes of level r ≥ 1, one has the following partial result, which extends Theorem 21 of [2].

Theorem 9. Let r be a positive integer ≤ ℓ. Then the automorphism group of C^{𝔸}(ℓ, m; r) contains a subgroup isomorphic to ℌ(ℓ, m). In particular,

#Aut (C^{𝔸}(ℓ, m; r)) ≥ \frac{q^{δ}}{q − 1} (∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i})) ( ∏_{j=0}^{ℓ′−1}(q^{ℓ′} − q^{j})) .  (9)

Proof. In view of Lemma 7, ψ_{u,A,B} ↦ σ_{u,A,B} gives a natural map from ℌ(ℓ, m) into Aut (C^{𝔸}(ℓ, m; r)). It is readily seen that this map is a group homomorphism. So it suffices to show that this homomorphism is injective. To this end, suppose σ_{u,A,B} is the identity permutation for some B ∈ GL_{ℓ}(𝔽_{q}), A ∈ GL_{ℓ′}(𝔽_{q}), and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Then σ_{u,A,B}(Ev(f)) = Ev(f) for all f ∈ F(ℓ, m), i.e.,

f(BP A^{−1} + u) = f(P) for all f ∈ F(ℓ, m) and all P ∈ 𝔸^{δ} (𝔽_{q}).

By letting f vary over all possible 1×1 minors, we see that (7) holds. Hence ψ_{u,A,B} is the identity transformation of 𝔸^{δ}. Finally, (9) follows from Proposition 8. □

Remark 10. It may be tempting to believe that Aut (C^{𝔸}(ℓ, m; r)) is isomorphic to ℌ(ℓ, m) for any r ≥ 1. But already when r = 1, we know from part (iii) of Proposition 4 that Aut (C^{𝔸}(ℓ, m; 1)) = Aut (RM(1, δ)) ≃ AGL_{δ}(𝔽_{q}) ≃ 𝔽_{q}^{δ} ⋊ GL_{δ}(𝔽_{q}), and the latter is, in general, much larger that ℌ(ℓ, m). Even when r = ℓ = ℓ′ > 1, one can see as follows that Aut (C^{𝔸}(ℓ, m; r)) = Aut (C^{𝔸}(ℓ, m)) can be larger than ℌ(ℓ, m). Consider the permutation σ of S_{n} induced by the transpose map, i.e., σ ∈ S_{n} such that (P_{1}^{T} , …, P_{n}^{T}) = (P_{σ(1)}, …, P_{σ(n)}). It is clear that the minors of X^{T} are minors of X, and hence σ is an automorphism of C^{𝔸}(ℓ, m). If σ were equal to σ_{u,A,B} for some B ∈ GL_{ℓ}(𝔽_{q}), A ∈ GL_{ℓ′}(𝔽_{q}), and u ∈ M_{ℓ×ℓ′}(𝔽_{q}), then as in the proof of Theorem 9, we obtain

BP A^{−1} + u = P^{T} for all P = (p_{ij})_{1≤i≤ℓ, 1≤j≤ℓ′} ∈ 𝔸^{δ} (𝔽_{q}) .

Taking P to be the zero matrix, we conclude that u = 0. Further, since linear polynomials are reduced and hence determined by the corresponding 𝔽_{q}-valued function on 𝔸^{δ} (𝔽_{q}), we see that BXA^{−1} = X^{T}. In particular, writing B = (b_{ij}) and A^{−1} = (a′_{ij}), we see that

X_{ii} = ∑_{r=1}^{ℓ} ∑_{s=1}^{ℓ} b_{ir}X_{rs}a′_{si} for i = 1, …, ℓ.

Consequently, for any i, r, s ∈ {1, …, ℓ}, we obtain b_{ii}a′_{ii} = 1 and b_{ir}a′_{si} = 0 if (r, s) ≠ (i, i). This, in turn, implies that B and A^{−1} are diagonal matrices. But then the (i, j)^{th} entry of BXA^{−1} is b_{ii}X_{ij}a′_{jj}, which can not always be X_{ji} since ℓ > 1. This shows that σ does not belong the subgroup of Aut (C^{𝔸}(ℓ, m)) corresponding to ℌ(ℓ, m). At any rate, the complete determination of Aut(C^{𝔸}(ℓ, m)) and more generally, Aut (C^{𝔸}(ℓ, m; r)) for 1 < r ≤ ℓ, remains an open question.

5. Duality

In this section we shall explicitly determine the dual of any affine Grassmann code and compute its minimum distance. Let us begin by observing that the monomial

F := ∏_{(i,j)∈R} X_{ij}^{q−1} = ∏_{i=1}^{ℓ} ∏_{j=1}^{ℓ′} X_{ij}^{q−1}

is reduced and that μ ∈ 𝕄(ℓ, m) is a reduced monomial if and only if μ divides F. We may refer to F as the full product. Note that for 0 ≤ r ≤ ℓ,

dim ℜ(ℓ, m) = # \overline{𝕄}(ℓ, m) = ∑_{s=0}^{ℓ} \binom{δ}{s}(q − 1)^{s} = q^{δ} = length (C^{𝔸}(ℓ, m; r))

and also that

dim C^{𝔸}(ℓ, m; r)^{⊥} = n − dim C^{𝔸}(ℓ, m; r) = q^{δ} − ∑_{i=0}^{r} \binom{ℓ}{i}\binom{ℓ′}{i}.  (10)

The usual “inner product” on 𝔽_{q}^{q^{δ}} corresponds to the symmetric bilinear form ⟨ , ⟩ on the 𝔽_{q}-linear space ℜ(ℓ, m) given by

⟨f, g⟩ := ∑_{P ∈𝔸^{δ}} f(P)g(P) = ∑_{P ∈𝔸^{δ}} fg(P) = ∑_{P ∈𝔸^{δ}} \overline{fg}(P), for f, g ∈ ℜ(ℓ, m).

The dual of C^{𝔸}(ℓ, m; r) corresponds, via the 𝔽_{q}-linear isomorphism f ↦ Ev(f) of ℜ(ℓ, m) → 𝔽_{q}^{q^{δ}}, to the subspace

{f ∈ ℜ(ℓ, m) : ⟨f, M⟩ = 0 for all M ∈ Δ(ℓ, m; r)}  (11)

of ℜ(ℓ, m). We shall now proceed to determine an explicit 𝔽_{q}-basis of this subspace. The first step is to recall the following well-known result (cf. [4, Lem. 1.6]).

Proposition 11. Let μ ∈ \overline{𝕄}(ℓ, m) be a reduced monomial. Then

∑_{P ∈𝔸^{δ}} μ(P) = \begin{cases}0 & if μ ≠ F, \\ (−1)^{δ} & if μ = F. \end{cases}

We have noted in Remark 1 that \overline{fg} need not be equal to f̄ḡ for arbitrary f, g ∈ 𝔽_{q}[X]. The following useful lemma shows what is the best that we can do in a special case.

Lemma 12. Let μ, ν ∈ \overline{𝕄}(ℓ, m) be such that \overline{μν} = F. Then there is a divisor ν′ of ν such that μν′ = F. Moreover, if ν is squarefree and if q > 2, then μν = F.

Proof. For (i, j) ∈ R, let α_{ij} = deg_{X_{ij}} μ and β_{ij} = deg_{X_{ij}} ν. Since μ and ν are reduced, it follows that

deg_{X_{ij}} \overline{μν} = \begin{cases}α_{ij} + β_{ij} & if α_{ij} + β_{ij} ≤ q − 1, \\ α_{ij} + β_{ij} − q + 1 & if α_{ij} + β_{ij} ≥ q. \end{cases}

On the other hand, since \overline{μν} = F, we see that α_{ij} + β_{ij} ≥ q − 1 for all (i, j) ∈ R. Hence ν′ := ∏_{(i,j)∈R} X_{ij}^{q−1−α_{ij}} is a divisor of ν and it clearly satisfies μν′ = F. Finally, suppose ν is squarefree and q > 2, but ν′ ≠ ν. Then there is a variable X_{ij} that divides ν, but not ν′. Now since μν′ = F, we see that deg_{X_{ij}} μ = q − 1. But then deg_{X_{ij}} μν = q, which contradicts the assumption that \overline{μν} = F, since q > 2. □

Given any nonnegative integer r ≤ ℓ, define

\overline{F𝕄}(ℓ, m; r) := \{\frac{F}{t} : t ∈ Term(M) for some M ∈ Δ(ℓ, m; r)\} .

It is clear that elements of \overline{F𝕄}(ℓ, m; r) are reduced monomials; we shall refer to them as forbidden monomials with respect to the affine Grassmann code of level r. This terminology is justified by the following result.

Lemma 13. Let r be a nonnegative integer ≤ ℓ and let μ ∈ \overline{𝕄}(ℓ, m) be such that μ ∉ \overline{F𝕄}(ℓ, m; r). Then Ev(μ) ∈ C^{𝔸}(ℓ, m; r)^{⊥}.

Proof. Let M ∈ Δ(ℓ, m; r) and let t ∈ Term(M). Now \overline{μt} is reduced and if it were equal to F, then by Lemma 12, μ = F/t′ for some divisor t′ of t. But this contradicts the assumption that μ ∉ \overline{F𝕄}(ℓ, m; r) because the divisor of a term of a minor in Δ(ℓ, m; r) is also a term of a minor in Δ(ℓ, m; r). Thus, in view of Proposition 11, we obtain ⟨μ, t⟩ = ∑_{P ∈𝔸^{δ}} \overline{μt}(P) = 0. Consequently, μ is in the subspace of ℜ(ℓ, m) given by (11), and so Ev(μ) ∈ C^{𝔸}(ℓ, m; r)^{⊥}. □

Already, we have enough information to show that affine Grassmann codes are almost always self-orthogonal. More precisely, we have the following.

Theorem 14. Let r be a nonnegative integer ≤ ℓ. Then the affine Grassmann code C^{𝔸}(ℓ, m; r) of level r is self-orthogonal if and only if (ℓ, m; r; q) is different from (1, 2; 1; 2), (1, 2; 1; 3) and (1, 3; 1; 2).

Proof. First, if r = 0, then C^{𝔸}(ℓ, m; r) is the one-dimensional code spanned by the all 1-vector (1, 1, …, 1) in 𝔽_{q}^{q^{δ}} and this is clearly self-orthogonal. Now suppose r ≥ 1. Observe that if μ ∈ \overline{F𝕄}(ℓ, m; r) is any forbidden monomial, then

deg μ ≥ deg F − r ≥ deg F − ℓ = [(q − 1)ℓ′ − 1] ℓ ≥ [(q − 1)ℓ′ − 1] r.

In particular, if (q −1)ℓ′ > 2, then no reduced monomial of degree ≤ r is forbidden. On the other hand, C^{𝔸}(ℓ, m; r) is spanned by the evaluations of minors of size ≤ r, which, in turn, are 𝔽_{q}-linear combinations of reduced monomials of degree ≤ r. Hence by Lemma 13, we can conclude that C^{𝔸}(ℓ, m; r) ⊆ C^{𝔸}(ℓ, m; r)^{⊥} when (q − 1)ℓ′ > 2. Now suppose (q − 1)ℓ′ ≤ 2. Since 1 ≤ r ≤ ℓ ≤ ℓ′, the only possible values of (ℓ, ℓ′; r; q) are (1, 1; 1; 2), (1, 1; 1; 3), (1, 2; 1; 2), and (2, 2; 2; 2). For the first 3 values, one finds dim C^{𝔸}(ℓ, m; r) > dim C^{𝔸}(ℓ, m; r)^{⊥}, and hence C^{𝔸}(ℓ, m; r) is not self-orthogonal in these cases. When r = ℓ = ℓ′ = q = 2, the code C^{𝔸}(ℓ, m; r) is spanned by the evaluations of 1, X_{11}, X_{12}, X_{21}, X_{22} and the minor B := X_{11}X_{22} + X_{12}X_{21}. The first 5 are non-forbidden reduced monomials; hence by Lemma 13, they are in C^{𝔸}(ℓ, m; r)^{⊥}. A direct verification shows that ⟨B, B⟩ = 0, since q = 2. Thus C^{𝔸}(ℓ, m; r) is self-orthogonal when r = ℓ = ℓ′ = q = 2. □

Although the non-forbidden monomials give rise to linearly independent elements of the dual of an affine Grassmann code, they fail to span it. To extend these to a basis, one needs to add certain binomials such as the polynomial B in the proof of Theorem 14. A general definition of these binomials is given below.

First, let us introduce some notation, which will be useful in the sequel. For any nonnegative integer r ≤ ℓ, denote, as usual, by S_{r} the set of all permutations of {1, …, r}. Further, given any r × r minor M of X and any σ ∈ S_{r}, denote by t_{σ}(M) the signed term of M corresponding to the permutation σ. For example, t_{σ}(L_{r}) = sgn(σ)X_{1σ(1)} ⋯ X_{rσ(r)}, where L_{r} is the r^{th} leading principal minor of X. We will denote by ϵ the identity permutation and, by abuse of language, regard it as an element of S_{r} for every nonnegative integer r. In particular, for any minor M of X, the corresponding signed term t_{ϵ}(M) is precisely the product of the variables on the principal diagonal of the submatrix corresponding to M. Define

B_{M,σ} := \frac{F}{t_{ϵ}(M)} − \frac{F}{t_{σ}(M)} for M ∈ Δ_{r}(ℓ, m) and σ ∈ S_{r}.

Clearly, B_{M,σ} = 0 if σ = ϵ and in particular, if r ≤ 1. If r ≥ 2 and if σ is a nonidentity permutation, then B_{M,σ} is a reduced polynomial with exactly two terms, each of which is a forbidden monomial up to a sign. We may refer to B_{M,σ} as the binomial corresponding to the minor M and the permutation σ.

Lemma 15. Let i, r be integers such that 0 ≤ i ≤ r ≤ ℓ, and let M ∈ Δ_{i}(ℓ, m) and σ ∈ S_{i}. Then Ev (B_{M,σ}) ∈ C^{𝔸}(ℓ, m; r)^{⊥}.

Proof. Clearly, it suffices to show that ⟨B_{M,σ}, N ⟩ = 0 for all N ∈ Δ(ℓ, m; r). So let us fix some j × j minor N of X, where j ≤ r. Also let π denote a permutation of {1, …, j}. We will distinguish two cases.

Case 1: q > 2. Since sgn(π)t_{π}(N) is a squarefree monomial, it follows from Lemma 12 that \overline{(F/t_{σ}(M)) t_{π}(N)} = ±F only when t_{σ}(M) = ±t_{π}(N), which, in turn, is possible only when i = j, M = N, and σ = π. Consequently, in view of Proposition 11, we see that ⟨B_{M,σ}, N ⟩ = 0 if N ≠ M, whereas

⟨B_{M,σ}, M⟩ = ∑_{π∈S_{j}}⟨B_{M,σ}, t_{π}(M)⟩ = sgn(ϵ)^{2}(−1)^{δ} − sgn(σ)^{2}(−1)^{δ} = 0.

Case 2: q = 2. In this case it follows from Lemma 12 that \overline{(F/t_{σ}(M)) t_{π}(N)} = F only when t_{σ}(M) divides t_{π}(N). Further, if Y denotes the j × j submatrix of X corresponding to the minor N, then it is readily seen that t_{σ}(M) divides t_{π}(N) if and only if i ≤ j, M = det Y′, and σ = π′, where Y′ is an i × i submatrix of Y and π′ is the restriction to π to {1, …, i}. Consequently, in view of Proposition 11, we see that ⟨F/t_{σ}(M), t_{π}(N)⟩ = 1 for precisely (j − i)! permutations π ∈ S_{j} obtained by extending σ to {1, …, j} by permuting i + 1, …, j randomly. It follows that

⟨B_{M,σ}, N ⟩ = 2(j − i)! = 0.

This completes the proof. Consequently, in view of Proposition 11, we obtain ⟨B_{M,σ}, N ⟩ = 0 if N ≠ M, while

⟨B_{M,σ}, M⟩ = ∑_{π∈S_{j}}⟨B_{M,σ}, t_{π}(M)⟩ = sgn(ϵ)^{2}(−1)^{δ} − sgn(σ)^{2}(−1)^{δ} = 0.

□

We are now ready to describe an explicit basis for C^{𝔸}(ℓ, m; r)^{⊥}. In fact, this is given by the non-forbidden monomials and the binomials. More precisely, for a nonnegative integer r ≤ ℓ, we let

ℬ(ℓ, m; r) := (\overline{𝕄}(ℓ, m) \ \overline{F𝕄}(ℓ, m; r))∪(⋃_{i=0}^{r} \{B_{M,σ} : M ∈ Δ_{i}(ℓ, m) and σ ∈ S_{i}^{∗}\}) ,

where S_{i}^{∗} := S_{i} \ {ϵ} is the set of non-identity permutations of {1, …, i}; also let

ℱ^{∗}(ℓ, m; r) := 𝔽_{q}-linear span of ℬ(ℓ, m; r).

Note that ℱ^{∗}(ℓ, m; r) is a subspace of ℜ(ℓ, m) and, in particular, it is 𝔽_{q}-isomorphic to its image in 𝔽_{q}^{q^{δ}} under the evaluation map. Now we have the following explicit description of the dual of an affine Grassmann code of any given level.

Theorem 16. C^{𝔸}(ℓ, m; r)^{⊥} = Ev (ℱ^{∗}(ℓ, m; r)) for 0 ≤ r ≤ ℓ.

Proof. Fix a nonnegative integer r ≤ ℓ. Let us first show that the elements of ℬ(ℓ, m; r) are linearly independent. Suppose

∑_{μ} a_{μ}μ + ∑_{i=0}^{r} ∑_{M∈Δ_{i}(ℓ,m)} ∑_{σ∈S_{i}^{∗}} b_{i,σ,M} B_{M,σ} = 0,

for some a_{μ}, b_{i,σ,M} ∈ 𝔽_{q}, where μ varies over \overline{𝕄}(ℓ, m) \ \overline{F𝕄}(ℓ, m; r). Then

∑_{μ} a_{μ}μ + ∑_{i=2}^{r} ∑_{M∈Δ_{i}(ℓ,m)} ∑_{σ∈S_{i}} b_{i,σ,M} \frac{F}{t_{σ}(M)} = 0,  (12)

where, for 2 ≤ i ≤ r and M ∈ Δ_{i}(ℓ, m), we have put b_{i,ϵ,M} := − ∑_{σ∈S_{i}^{∗}} b_{i,σ,M}. Now observe that (12) is a linear combination of distinct monomials. Hence we must have a_{μ} = 0 and b_{i,σ,M} = 0 for all relevant parameters μ, i, σ, and M.

To complete the proof, it suffices to show that the cardinality of ℬ(ℓ, m; r) coincides with the dimension of the subspace of ℜ(ℓ, m) given by (11). To this end, let us first note that a forbidden monomial is completely determined by an i × i minor of X and by one of its i! terms. Since X has exactly \binom{ℓ}{i}\binom{ℓ′}{i} minors, we see that

#\overline{𝕄}(ℓ, m) \ \overline{F𝕄}(ℓ, m; r) = q^{δ} − ∑_{i=0}^{r} i!\binom{ℓ}{i}\binom{ℓ′}{i}.

On the other hand, the binomials are determined by an i × i minor of X and a non-identity permutation of {1, …, i}. Thus,

# ⋃_{i=0}^{r} \{B_{M,σ} : M ∈ Δ_{i}(ℓ, m) and σ ∈ S_{i}^{∗}\} = ∑_{i=0}^{r}(i! − 1)\binom{ℓ}{i}\binom{ℓ′}{i}.

Combining the last two equations, we see that #ℬ(ℓ, m; r) is the expression on the right in (10), as desired. □

We shall now proceed to determine the minimum distance of the dual of an affine Grassmann code. As a warm-up, it may be noted that the Singleton bound shows already that for any nonnegative integer r ≤ ℓ,

d (C^{𝔸}(ℓ, m; r)^{⊥}) ≤ 1 + ∑_{i=0}^{r} \binom{ℓ}{i}\binom{ℓ′}{i} ≤ 1 + \binom{m}{ℓ}.

This indicates that the minimum distance is rather small and it does not grow with q. In the trivial case r = 0, we obtain 2 as an upper bound, and it is readily seen that this is attained. Indeed, C^{𝔸}(ℓ, m; 0) is the one-dimensional code of length q^{δ} spanned by (1, 1, …, 1) and its dual contains no codeword of weight 1. Another trivial case is when q = 2 and r = ℓ = ℓ′ = 1. In this case, C^{𝔸}(1, 2; 1) = 𝔽_{2}^{2}, while C^{𝔸}(1, 2; 1)^{⊥} = {0}. Barring these, it will be seen below that the minimum distance is always 3 or 4.

Theorem 17. Let r be a positive integer ≤ ℓ. Then the minimum distance of the q-ary code C^{𝔸}(ℓ, m; r)^{⊥} is given by

d (C^{𝔸}(ℓ, m; r)^{⊥}) = \begin{cases}3 & if q > 2, \\ 4 & if q = 2 and ℓ′ > 1. \end{cases}

Moreover, if q > 2 and if a_{1}, a_{2} are any distinct elements of 𝔽_{q}^{∗}, then Ev (g_{a_{1},a_{2}}) is a minimum-weight codeword of C^{𝔸}(ℓ, m; r)^{⊥}, where

g_{a_{1},a_{2}} := \frac{1}{(X_{ℓℓ′} − a_{1}) (X_{ℓℓ′} − a_{2})} ∏_{(i,j)∈R} (X_{ij}^{q−1} − 1) .  (13)

On the other hand, if q = 2 and ℓ′ > 1, then there are distinct (i_{1}, j_{1}), (i_{2}, j_{2}) ∈ R such that i_{1} = i_{2} or j_{1} = j_{2}, and moreover for any such (i_{1}, j_{1}), (i_{2}, j_{2}), if we let

h := \frac{F}{X_{i_{1}j_{1}}X_{i_{2}j_{2}}} .  (14)

then Ev(h) is a minimum-weight codeword of C^{𝔸}(ℓ, m; r)^{⊥}.

Proof. Let us assume that either q > 2 or that q = 2 and ℓ′ > 1. This ensures that δ(q − 1) − 2 ≥ 0. Now, observe that every element of ℬ(ℓ, m; r) is either a reduced monomial of degree ≤ δ(q − 1) − 2 or a difference of two reduced monomials of degree ≤ δ(q − 1) − 2. Hence it follows from Theorem 16 that C^{𝔸}(ℓ, m; r)^{⊥} is a subcode of the generalized Reed-Muller code RM (δ(q − 1) − 2, δ). Consequently, from part (ii) of Proposition 4, we see that

d (C^{𝔸}(ℓ, m; r)^{⊥}) ≥ d (RM (δ(q − 1) − 2, δ)) = \begin{cases}3 & if q > 2, \\ 4 & if q = 2 and ℓ′ > 1. \end{cases}

To complete the proof, it suffices to show that the evaluations of (13) and (14) give codewords of (Hamming) weight 3 and 4, respectively.

To begin with, suppose q > 2 and let a_{1}, a_{2} be any distinct elements of 𝔽_{q}^{∗}. Since X^{q−1} − 1 = ∏_{a∈𝔽_{q}^{∗}}(X − a), it is clear that g_{a_{1},a_{2}} defined by (13) is in 𝔽_{q}[X] and is, in fact, a reduced polynomial. Moreover, deg_{X_{ℓℓ′}} g_{a_{1},a_{2}} ≤ q −3. On the other hand, since the terms of any minor are squarefree monomials, every forbidden monomial μ ∈ \overline{F𝕄}(ℓ, m; r) must satisfy deg_{X_{ij}} μ ≥ q−2 for all i = 1, …, ℓ and j = 1, …, ℓ′. It follows that g_{a_{1},a_{2}} is a 𝔽_{q}-linear combination of non-forbidden reduced monomials and in particular, it is in ℱ^{∗}(ℓ, m; r). Moreover, if P = (p_{ij}) ∈ 𝔸^{δ} (𝔽_{q}), then g_{a_{1},a_{2}}(P) ≠ 0 if and only if p_{ij} = 0 for all (i, j) ≠ (ℓ, ℓ′) and p_{ℓℓ′} ∈ {0, a_{1}, a_{2}}. Thus we conclude that Ev (g_{a_{1},a_{2}}) is a codeword of C^{𝔸}(ℓ, m; r)^{⊥} of weight 3.

Next, suppose q = 2 and ℓ′ > 1. The existence of distinct (i_{1}, j_{1}), (i_{2}, j_{2}) ∈ R such that i_{1} = i_{2} or j_{1} = j_{2} is obvious; for example, we can take i_{1} = i_{2} = ℓ, j_{1} = ℓ′ − 1 and j_{2} = ℓ′. Moreover, for any such (i_{1}, j_{1}), (i_{2}, j_{2}) ∈ R, the monomial X_{i_{1}j_{1}}X_{i_{2}j_{2}} contains two variables from the same row or from the same column, and hence it can never be the term of any minor of X. Consequently, the reduced monomial h defined by (14) is non-forbidden and Ev(h) is a codeword of C^{𝔸}(ℓ, m; r)^{⊥}. Furthermore, if P = (p_{ij}) ∈ 𝔸^{δ} (𝔽_{q}), then h(P) ≠ 0 if and only if p_{ij} = 1 for all (i, j) ∈ R different from (i_{1}, j_{1}) and (i_{2}, j_{2}). Thus we conclude that Ev(h) is of weight 4. □

6. Generation by Minimum-weight Codewords

In this section we will show that the affine Grassmann codes as well as their duals have the property that the codewords of minimum weight generate the code. The case of affine Grassmann codes is easy and in fact, it is shown below that the result holds more generally for affine Grassmann codes of any level.

Proposition 18. Let r be a nonnegative integer ≤ ℓ. Then the minimum-weight codewords of C^{𝔸}(ℓ, m; r) generate C^{𝔸}(ℓ, m; r).

Proof. The code C^{𝔸}(ℓ, m; r) is generated by Ev(M) as M varies over the i × i minors of X for 0 ≤ i ≤ r. We proceed by decreasing induction on i (0 ≤ i ≤ r) to show that Ev (M) is in the 𝔽_{q}-linear span of minimum-weight codewords of C^{𝔸}(ℓ, m; r) for every i×i minor M of X. To begin with, if i = r, then M is the r^{th} leading principal minor of Y := BXA for some permutation matrices B ∈ GL_{ℓ}(𝔽_{q}) and A ∈ GL_{ℓ′}(𝔽_{q}). Hence Lemma 7 shows that Ev (M) differs from Ev (L_{r}) by an automorphism of C^{𝔸}(ℓ, m; r); consequently, by Theorem 5, Ev (M) is itself a minimum-weight codeword of C^{𝔸}(ℓ, m; r). Now, suppose i < r and the result holds for the (i+1)×(i+1) minors of X. Let a_{1}, …, a_{i} and b_{1}, …, b_{i} denote, respectively, the row and column indices of X corresponding to the i × i minor M. Since i < r, we can choose a row index α distinct from a_{1}, …, a_{i} and a column index β distinct from b_{1}, …, b_{i}. Consider X′ = X + u, where u is the ℓ × ℓ′ matrix whose (α, β)^{th} entry is 1 and all other entries are 0. Let N (resp: N′) be the (i+1)×(i+1) minor of X (resp: X′) corresponding to the row indices a_{1}, …, a_{i}, α and column indices b_{1}, …, b_{i}, β. Observe that M = N′ − N. From the induction hypothesis together with Lemma 7, it follows that both Ev (N) and Ev (N′) are in the 𝔽_{q}-linear span of minimum-weight codewords of C^{𝔸}(ℓ, m; r) and therefore, so is Ev (M). □

Remark 19. Affine Grassmann codes are closely related to Grassmann codes, and this connection was explained in Section VII of [2]. We remark here that a result analogous to Proposition 18 holds for Grassmann codes as well. To see this, it suffices to note that by a result of Nogin (see, e.g., [6, Cor. 19]), the minimum-weight codewords of the Grassmann code C(ℓ, m) correspond precisely to the decomposable elements in the exterior power ∧^{m−ℓ}𝔽_{q}^{m} and evidently, these decomposable elements span the corresponding function space G(ℓ, m) = (∧^{ℓ}𝔽_{q}^{m})^{∗} ≃ ∧^{m−ℓ}𝔽_{q}^{m}.

As indicated in the Introduction, an analogous result for the dual of C^{𝔸}(ℓ, m; r) is not true, in general. However, the minimum-weight codewords of C^{𝔸}(ℓ, m)^{⊥} do generate C^{𝔸}(ℓ, m)^{⊥}. In other words, a result analogous to Proposition 18 holds for the duals of affine Grassmann codes (of level ℓ). This, in fact, seems much harder to prove and we will need a number of auxiliary results, which will be spread over the next three subsections. The first subsection contains lemmas of a general nature concerning generating sets and bases for certain spaces of polynomials. Next, we show that the evaluations of certain non-forbidden monomials with respect to C^{𝔸}(ℓ, m; r) are generated by the minimum-weight codewords. Finally, the binomials in ℬ(ℓ, m; r) are dealt with in the last subsection, where we conclude with the main result of this section. Wherever possible, we will consider affine Grassmann codes of an arbitrary level so as to make it clear what works in general and what goes wrong when r < ℓ as opposed to r = ℓ.

Before proceeding with generalities, and as a warm-up, let us consider the case of r = 0. Here C^{𝔸}(ℓ, m; 0) is the one-dimensional code of length n := q^{δ} spanned by (1, 1, …, 1) and C^{𝔸}(ℓ, m; 0)^{⊥} = {(c_{1}, …, c_{n}) ∈ 𝔽_{q}^{n} : c_{1} + ⋯ + c_{n} = 0}. Thus, if {e_{1}, …, e_{n}} denotes the standard basis of 𝔽_{q}^{n}, then e_{1} − e_{2}, …, e_{1} − e_{n} are

minimum-weight codewords and these clearly generate C^{𝔸}(ℓ, m; 0)^{⊥}.

6.1. Generators and Bases. Let T be an indeterminate over 𝔽_{q} and d a nonnegative integer. Denote by 𝔽_{q}[T] the space of polynomials in T with coefficients in 𝔽_{q}, and by 𝔽_{q}[T]_{≤d} the subspace of polynomials in 𝔽_{q}[T] of degree ≤ d. Also, denote by M_{d}[T] the set of monic polynomials in 𝔽_{q}[T] of degree d having d distinct roots in 𝔽_{q}.

Lemma 20. Assume that d < q. Then M_{d}[T] spans 𝔽_{q}[T]_{≤d}.

Proof. Since d < q, we can choose distinct elements a_{1}, …, a_{d+1} from 𝔽_{q}. The d+1 polynomials

p_{i}(T) := ∏_{1≤j≤d+1} ; j≠i(T − a_{j}) for i = 1, …, d + 1,

are elements of M_{d}[T]. Moreover, they are linearly independent, since a relation ∑_{j} β_{j}p_{j}(T) = 0 implies, after substituting a_{i} for T, that β_{i} = 0 for i = 1, …, d + 1. Since M_{d}[T] ⊂ 𝔽_{q}[T]_{≤d} and dim_{𝔽_{q}} 𝔽_{q}[T]_{≤d} = d + 1, the lemma follows. □

Corollary 21. M_{q−1}[T] = {(T − α)^{q−1} − 1 : α ∈ 𝔽_{q}} and moreover, M_{q−1}[T] is a 𝔽_{q}-basis of 𝔽_{q}[T]_{≤q−1}.

Proof. For each α ∈ 𝔽_{q}, the polynomial (T − α)^{q−1} − 1 is clearly monic of degree q − 1 and its roots are precisely the elements β ∈ 𝔽_{q} with β ≠ α. It follows that M_{q−1}[T] = {(T − α)^{q−1} − 1 : α ∈ 𝔽_{q}}. In particular, #M_{q−1}[T] = q = dim 𝔽_{q}[T]_{≤q−1}. Hence by Lemma 20, M_{q−1}[T] is a 𝔽_{q}-basis of 𝔽_{q}[T]_{≤q−1}. □

Remark 22. For 0 ≤ d < q, the set M_{d}[T] is a basis of 𝔽_{q}[T]_{≤d} if and only if d = 0 or d = q − 1. The case d = 0 is trivial whereas d = q − 1 was noted above. For the converse, it suffices to observe that #M_{d}[T] = \binom{q}{d} ≥ q > d + 1 when 1 ≤ d < q − 1. In general, for 0 ≤ d < q, upon letting e = q − 1 − d, one can write

M_{d}[T] = \{\frac{(T − α)^{q−1} − 1}{(T − a_{1}) ⋯ (T − a_{e})} : α, a_{1}, …, a_{e} distinct elements of 𝔽_{q}\} . (15)

This representation is particularly useful for large values of d. It may be noted, however, that for a given polynomial in M_{d}[T], the corresponding α ∈ 𝔽_{q} and the e-element subset {a_{1}, …, a_{e}} of 𝔽_{q} \ {α} is not unique.

We now derive a multivariable analogue of Lemma 20. To this end, let s be a positive integer and T_{1}, …, T_{s} independent indeterminates over 𝔽_{q}, and let d_{1}, …, d_{s} be nonnegative integers. Denote by 𝔽_{q}[T_{1}, …, T_{s}] the space of polynomials in T_{1}, …, T_{s} with coefficients in 𝔽_{q} and by 𝔽_{q}[T_{1}, …, T_{s}]_{≤(d_{1},...,d_{s})} the subspace of polynomials f ∈ 𝔽_{q}[T_{1}, …, T_{s}] with deg_{X_{j}} f ≤ d_{j} for j = 1, …, s. Also, let

M_{(d_{1},...,d_{s})}[T_{1}, …, T_{s}] = {∏_{i=1}^{s} f_{i}(T_{i}) : f_{i}(T_{i}) ∈ M_{d_{i}}[T_{i}] for i = 1, …, s} .

Lemma 23. Assume that d_{i} < q for i = 1, …, s. Then M_{(d_{1},...,d_{s})}[T_{1}, …, T_{s}] spans 𝔽_{q}[T_{1}, …, T_{s}]_{≤(d_{1},...,d_{s})}.

Proof. 𝔽_{q}[T_{1}, …, T_{s}]_{≤(d_{1},...,d_{s})} is generated by monomials of the form T_{1}^{e_{1}} ⋯ T_{s}^{e_{s}} with 0 ≤ e_{i} ≤ d_{i} for i = 1, …, s, and by Lemma 20, each factor T_{i}^{e_{i}} of such a monomial is a 𝔽_{q}-linear combination of elements of M_{d_{i}}[T_{i}]. □

As in Remark 22, it may be noted that M_{(d_{1},...,d_{s})}[T_{1}, …, T_{s}] is a basis of 𝔽_{q}[T_{1}, …, T_{s}]_{≤(d_{1},...,d_{s})} if and only if d_{1} = ⋯ = d_{s} = 0 or d_{1} = ⋯ = d_{s} = q − 1. In particular, M_{(q−1,...,q−1)}[T_{1}, …, T_{s}] is a basis of the space 𝔽_{q}[T_{1}, …, T_{s}]_{≤(q−1,...,q−1)} of all reduced polynomials in T_{1}, …, T_{s} with coefficients in 𝔽_{q}. The following lemma gives several other bases for this space. As in Section 2, for any f ∈ 𝔽_{q}[T_{1}, …, T_{s}], we denote by \overline{f} the reduced polynomial in 𝔽_{q}[T_{1}, …, T_{s}] corresponding to f. Note that if L ∈ 𝔽_{q}[T_{1}, …, T_{s}] is a homogeneous linear polynomial, i.e., if L = a_{1}T_{1} + ⋯ + a_{s}T_{s} for some a_{1}, …, a_{s} ∈ 𝔽_{q}, then \overline{L} = L. In particular, L can be identified with the functional 𝔽_{q}^{s} → 𝔽_{q} that maps w = (w_{1}, …, w_{s}) ∈ 𝔽_{q}^{s} to L(w) = a_{1}w_{1} + ⋯ + a_{s}w_{s}.

Lemma 24. Let {L_{i} : 1 ≤ i ≤ s} ⊆ 𝔽_{q}[T_{1}, …, T_{s}] be a set of s linearly independent homogeneous linear polynomials. Then the set

𝔏 := \{\overline{L_{1}^{e_{1}} ⋯ L_{s}^{e_{s}}} : 0 ≤ e_{i} ≤ q − 1 for i = 1, …, s\}

is a basis of 𝔽_{q}[T_{1}, …, T_{s}]_{≤(q−1,...,q−1)}.

Proof. Since the linear polynomials L_{1}, …, L_{s} are linearly independent, the map given by w ↦ (L_{1}(w), …, L_{s}(w)) is a 𝔽_{q}-linear isomorphism of 𝔽_{q}^{s} onto 𝔽_{q}^{s}. Hence given any v ∈ 𝔽_{q}^{s}, there exists w_{v} ∈ 𝔽_{q}^{s} such that (L_{1}(w_{v}), …, L_{s}(w_{v})) = v. Now let a relation ∑_{e_{1},...,e_{s}} α_{e_{1},...,e_{s}} \overline{L_{1}^{e_{1}} ⋯ L_{s}^{e_{s}}} = 0 be given, where α_{e_{1},...,e_{s}} ∈ F for all e_{1}, … e_{s} (with 0 ≤ e_{i} ≤ q − 1 for i = 1, …, s). Evaluating the given relation at w_{v}, we find ∑_{e_{1},...,e_{s}} α_{e_{1},...,e_{s}}α_{e_{1},...,e_{s}}v_{1}^{e_{1}} ⋯ v_{s}^{e_{s}} = 0. Consequently, the polynomial ∑_{e_{1},...,e_{s}} α_{e_{1},...,e_{s}}α_{e_{1},...,e_{s}}T_{1}^{e_{1}} ⋯ T_{s}^{e_{s}} vanishes at all points of 𝔽_{q}^{s}. Since 0 ≤ e_{i} ≤ q−1 for i = 1, …, s, this is only possible if α_{e_{1},...,e_{s}} = 0 for all e_{1}, …, e_{s}. Thus, 𝔏 is linearly independent. Finally, since # 𝔏 = q^{s} = dim_{𝔽_{q}} 𝔽_{q}[T_{1}, …, T_{s}]_{≤(q−1,...,q−1)}, the lemma is proved. □

6.2. Non-forbidden monomials. Let us fix a positive integer r ≤ ℓ. From Theorem 16, we know that C^{𝔸}(ℓ, m; r)^{⊥} = Ev (ℱ^{∗}(ℓ, m; r)), where ℱ^{∗}(ℓ, m; r) is the space spanned by the non-forbidden monomials and the binomials, or more precisely, by ℬ(ℓ, m; r). Let ℱ_{min}^{∗}(ℓ, m; r) denote the set of all f ∈ ℱ^{∗}(ℓ, m; r) such that Ev(f) is a minimum-weight codeword of C^{𝔸}(ℓ, m; r)^{⊥}, and let ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ denote the subspace of ℱ^{∗}(ℓ, m; r) spanned by ℱ_{min}^{∗}(ℓ, m; r).

We begin with a useful characterization of the non-forbidden monomials. To this end, let us first make a definition. We say that a reduced monomial μ ∈ \overline{𝕄}(ℓ, m) is maximal non-forbidden with respect to C^{𝔸}(ℓ, m; r) if

(i) μ = \frac{F}{t} for some t ∈ Term (M) and M ∈ Δ_{r+1}(ℓ, m),  (16)

or if there are (i_{1}, j_{1}), (i_{2}, j_{2}) ∈ R such that

(ii) μ = \frac{F}{X_{i_{1}j_{1}}X_{i_{2}j_{2}}} with i_{1} = i_{2} or j_{1} = j_{2}.  (17)

It may be noted that in (ii) above, the possibility (i_{1}, j_{1}) = (i_{2}, j_{2}) is not excluded except when q = 2, in which case it is automatically excluded since μ is a monomial to begin with. It may also be noted that when r = ℓ, i.e., in the case of affine Grassmann codes, possibility (i) does not arise at all, whereas when r = 1, we can combine (i) and (ii) to simply say that μ is a reduced monomial of degree δ(q−1)−2. The terminology in the above definition is justified by the following.

Lemma 25. A reduced monomial in \overline{𝕄}(ℓ, m) is non-forbidden with respect to C^{𝔸}(ℓ, m; r) if and only if it divides some maximal non-forbidden monomial with respect to C^{𝔸}(ℓ, m; r).

Proof. For a monomial μ ∈ 𝕄(ℓ, m) and for 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′, let us denote by μ_{i} the i^{th} row-degree of μ (i.e., the number of variables, counting multiplicities, from the i^{th} row of X appearing in μ) and by μ^{j} the j^{th} column-degree of μ. Observe that a monomial μ ∈ 𝕄(ℓ, m) is a term of a minor of size ≤ r, i.e., μ ∈ Term(M) for some M ∈ Δ(ℓ, m; r), if and only if deg(μ) ≤ r, μ_{i} ≤ 1 for all i = 1, …, ℓ and μ^{j} ≤ 1 for all j = 1, …, ℓ′. Hence if μ ∈ \overline{𝕄}(ℓ, m) is a reduced monomial, then

μ is forbidden ⇔ deg(μ) ≥ δ(q−1)−r, μ_{i} ≥ δ(q−1)−1 ∀ i, and μ^{j} ≥ δ(q−1)−1 ∀j.

In other words, a reduced monomial μ ∈ \overline{𝕄}(ℓ, m) is non-forbidden with respect to C^{𝔸}(ℓ, m; r) if and only if (a) deg(μ) ≤ δ(q − 1) − (r + 1), or (b) μ_{i} ≤ ℓ′(q − 1) − 2 for some i ∈ {1, …, ℓ}, or (c) μ^{j} ≤ ℓ(q − 1) − 2 for some j ∈ {1, …, ℓ′}. To conclude, it suffices to observe that for any μ ∈ \overline{𝕄}(ℓ, m), we have the following. If μ divides a monomial satisfying (16), then (a) holds. On the other hand, if (a) holds but neither (b) nor (c) holds, then μ divides a monomial satisfying (16). Finally, μ divides a monomial satisfying (17) if and only if (b) or (c) holds. □

We will now proceed to show that non-forbidden monomials of type (ii), i.e., those that divide a maximal non-forbidden monomial given by (17), are generated by the minimum-weight codewords. In what follows we will tacitly use the obvious fact that the (permutation) automorphisms of a code and its dual are identical and that minimum-weight codewords are always preserved by an automorphism. Furthermore, we will make frequent use of the automorphisms of C^{𝔸}(ℓ, m; r) given by Lemma 7, i.e., the automorphisms induced by the transformation X ↦ BXA+u, where B ∈ GL_{ℓ} (𝔽_{q}), A ∈ GL_{ℓ′} (𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). It is convenient to treat the binary and the non-binary cases separately.

Lemma 26. Assume that q = 2 and ℓ′ > 1. Suppose μ ∈ \overline{𝕄}(ℓ, m) is as in (17) and ν ∈ \overline{𝕄}(ℓ, m) divides μ. Then ν ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩.

Proof. First, observe that μ ∈ ℱ_{min}^{∗}(ℓ, m; r), thanks to Theorem 17. We use (finite) induction on d := deg (μ/ν) = deg(μ) − deg(ν) to show that ν ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. If d = 0, then ν = μ and there is nothing to prove. Assume that d > 0 and the result holds for smaller values of d. Since d > 0, there is a variable X_{ij} that divides μ/ν. Write ν′ = νX_{ij}. By induction hypothesis ν′ ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. Hence the polynomial, say f′, obtained from ν′ when X is changed to X+u is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ for every u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Now take u to be the ℓ × ℓ′ matrix whose (i, j)^{th} entry is 1 and all other entries are zero. Then f′ = ν′ + ν, and so ν ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. □

Lemma 27. Assume that q > 2. If f ∈ ℜ(ℓ, m) is such that deg_{X_{ij}} f ≤ q − 3 for some (i, j) ∈ R, then f ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩.

Proof. Applying an automorphism induced by X ↦ BXA, where B ∈ GL_{ℓ} (𝔽_{q}) and A ∈ GL_{ℓ′} (𝔽_{q}) are suitable permutation matrices, we may assume, without loss of generality, that (i, j) = (ℓ, ℓ′). In view of Corollary 21, Remark 22 and Lemma 23, we see that the space 𝔽_{q}[X]_{≤(q−1,q−1,...,q−1,q−3)} of all reduced polynomials of degree ≤ q − 3 in the last variable X_{ℓℓ′} is spanned by the products of the form

\frac{1}{(X_{ℓℓ′} − a_{1}) (X_{ℓℓ′} − a_{2})} ∏_{(i,j)∈R} (X_{ij} − α_{ij})^{q−1} − 1,

where α_{ij} vary over 𝔽_{q} and a_{1}, a_{2} vary over 𝔽_{q} \ {α_{ℓℓ′}}. But these products are precisely of the form (13) up to an automorphism induced by X ↦ X + u, where u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Hence from Theorem 17, we obtain the desired result. □

The above lemma shows that if q > 2 and if a reduced monomial ν divides a maximal non-forbidden monomial of the form F/X_{ij}^{2} for some (i, j) ∈ R, then ν is generated by minimum-weight codewords of C^{𝔸}(ℓ, m; r)^{⊥}. This covers, in particular, the case when ℓ′ = 1 (so that r = ℓ = 1). It only remains to consider the case of reduced monomials dividing maximal non-forbidden monomials of the form F/X_{i_{1}j_{1}}X_{i_{2}j_{2}}, where (i_{1}, j_{1}), (i_{2}, j_{2}) are distinct elements of R and where q > 2.

Lemma 28. Assume that q > 2 and ℓ′ > 1. Suppose μ is a maximal non-forbidden monomial of the form F/X_{i_{1}j_{1}}X_{i_{2}j_{2}}, where (i_{1}, j_{1}), (i_{2}, j_{2}) are distinct elements of R such that i_{1} = i_{2} or j_{1} = j_{2}. Then every divisor of μ is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩.

Proof. First, suppose i_{1} = i_{2}. Applying an automorphism induced by X ↦ BXA, where B ∈ GL_{ℓ} (𝔽_{q}) and A ∈ GL_{ℓ′} (𝔽_{q}) are suitable permutation matrices, we can and will assume that μ = F/X_{ℓℓ′−1}X_{ℓℓ′}. Let R′ := R \ {(ℓ, ℓ′ − 1), (ℓ, ℓ′)} and let

ν(X) = ∏_{(i,j)∈R′} X_{ij}^{e_{ij}} (0 ≤ e_{ij} ≤ q − 1)

be any reduced monomial in the ℓℓ′ − 2 variables {X_{ij} : (i, j) ∈ R′}. By Lemma 27, ν(X)X_{ℓℓ′−1}^{q−3}X_{ℓℓ′}^{q−1} ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. Consider the ℓ × ℓ′ matrix Y = (Y_{ij}) obtained from X by adding the (ℓ′ − 1)^{th} column to the last column (so that for 1 ≤ i ≤ ℓ, Y_{ij} = X_{ij} if 1 ≤ j < ℓ′ and Y_{iℓ′} = X_{iℓ′−1} + X_{iℓ′}). Clearly Y is obtained from X upon multiplication by an elementary matrix in GL_{ℓ′}(𝔽_{q}) on the right, and hence X ↦ Y induces an automorphism of C^{𝔸}(ℓ, m; r). Consequently, the corresponding reduced polynomial is generated by the minimum-weight codewords, i.e.,

\overline{ν(Y)X_{ℓℓ′−1}^{q−3} (X_{ℓℓ′−1} + X_{ℓℓ′})^{q−1}} ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ where ν(Y) = ∏_{(i,j)∈R′} Y_{ij}^{e_{ij}}.

Now since ν(Y) and X_{ℓℓ′−1}^{q−3} (X_{ℓℓ′−1} + X_{ℓℓ′})^{q−1} are polynomials in disjoint sets of variables, in view of Remark 1 and the binomial theorem, the polynomial

∑_{t=0}^{q−1} \overline{ν(Y)}\binom{q − 1}{t}\overline{X_{ℓℓ′−1}^{q−3+t}X_{ℓℓ′}^{q−1−t}}

is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. Moreover, by Lemma 27, each term in the above expansion, except possibly the term corresponding to t = 1, is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. It follows therefore that the the term corresponding to t = 1 is also in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. In other words, \overline{ν(Y)}X_{ℓℓ′−1}^{q−2}X_{ℓℓ′}^{q−2} ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. Finally, since the Y_{ij}, (i, j) ∈ R′, are clearly linearly independent, it follows from Lemma 24 that polynomials of the form \overline{ν(Y)} form a basis of the space of reduced polynomials in \{X_{ij} : (i, j) ∈ R′\}. Hence we conclude that any divisor of μ is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. The case when j_{1} = j_{2} is proved similarly. □

Corollary 29. Every non-forbidden monomial with respect to C^{𝔸}(ℓ, m) is in the 𝔽_{q}-linear span of minimum-weight codewords of C^{𝔸}(ℓ, m).

Proof. We have noted already that when r = ℓ, the only maximal non-forbidden monomials with respect to C^{𝔸}(ℓ, m; r) are those of type (ii), i.e., those given by (17). Hence the desired result follows from Lemmas 25, 26, 27, and 28. □

6.3. Binomials. Fix a positive integer r ≤ ℓ. Recall that the basis ℬ(ℓ, m; r) of C^{𝔸}(ℓ, m; r)^{⊥} consists of the non-forbidden monomials with respect to C^{𝔸}(ℓ, m; r) and the binomials

B_{M,σ} := \frac{F}{t_{ϵ}(M)} − \frac{F}{t_{σ}(M)},

where M varies over the minors of X with deg (M) ≤ r and σ varies over the nonidentity permutations of {1, 2, …, deg (M)}. The two monomials appearing in such a binomial are forbidden and therefore do not correspond to a codeword of C^{𝔸}(ℓ, m; r)^{⊥}. However, the binomials themselves correspond to codewords of C^{𝔸}(ℓ, m; r)^{⊥}, and we will show that they are generated by the minimum-weight codewords. We begin with an elementary algebraic observation, which will be useful in the sequel.

Lemma 30. Let x, y, z, w be independent indeterminates over 𝔽_{q}. Consider the polynomial f = (zw)^{q−2}(x + z)^{q−1}(y + w)^{q−1}. Also let

F_{0} := (xyzw)^{q−1} and B_{0} := \frac{F_{0}}{xw} + \frac{F_{0}}{yz} .  (18)

Then the reduced polynomial corresponding to f is given by

f̄ = \frac{F_{0}}{zw} + \frac{F_{0}}{xy} − B_{0} + h,

where h ∈ 𝔽_{q}[x, y, z, w] is a reduced polynomial such that every μ ∈ Term(h) satisfies deg_{x} μ ≤ q − 3 or deg_{y} μ ≤ q − 3.

Proof. Expanding (x + z)^{q−1} and (y + w)^{q−1} by the binomial theorem, we see that

f̄ = ∑_{s=0}^{q−1} ∑_{t=0}^{q−1} \binom{q − 1}{s}\binom{q − 1}{t}\overline{x^{q−1−s}z^{q−2+s}y^{q−1−t}w^{q−2+t}}.

Considering separately the terms in the double summation above corresponding to (s, t) = (0, 0), (1, 0), (0, 1) and (1, 1), and upon letting h denote the sum of the remaining terms, we readily obtain the desired result. □

Lemma 31. Assume that r > 1. Let ρ be an integer such that 1 < ρ ≤ r and let M ∈ Δ_{ρ}(ℓ, m). If σ, τ ∈ S_{ρ} are such that σ^{−1}τ is a transposition, then

\frac{F}{t_{σ}(M)} − \frac{F}{t_{τ} (M)} ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ .

Proof. Applying an automorphism induced by X ↦ BXA, where B ∈ GL_{ℓ} (𝔽_{q}) and A ∈ GL_{ℓ′} (𝔽_{q}) are suitable permutation matrices, we may assume that M = L_{ρ}, i.e., M is the ρ^{th} leading principal minor of X. Next, by a similar trick, we may assume that σ is the identity permutation and τ is a transposition in S_{ρ}, say (st). Let us denote the indeterminates X_{ss}, X_{st}, X_{ts} and X_{tt} by x, y, z and w, respectively. Also let R′ := R \ {(s, s), (s, t), (t, s), (t, t)}. With these simplifications and notations,

\frac{F}{t_{σ}(M)} − \frac{F}{t_{τ} (M)} = B_{0} ∏_{(i,j)∈R′} X_{ij}^{q−1},  (19)

where B_{0} is as in (18). On the other hand, by Lemmas 26 and 28, any divisor of F/zw is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. In particular, (zw)^{q−2} (xy)^{q−1} ν(X) ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ for any reduced monomial ν(X) in the ℓℓ′ − 4 variables {X_{ij} : (i, j) ∈ R′}. Now if Z = (Z_{ij}) is the ℓ × ℓ′ matrix obtained from X by adding the t^{th} row to the s^{th} row, then X ↦ Z induces an automorphism of C^{𝔸}(ℓ, m; r) and therefore in view of Remark 1,

(\overline{(zw)^{q−2} (x + z)^{q−1} (y + w)^{q−1}}) \overline{ν(Z)} ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ .

Moreover, by Lemma 24, the reductions \overline{ν(Z)} form a basis of the space of reduced polynomials in \{X_{ij} : (i, j) ∈ R′\}. Consequently, \overline{ν(Z)} can be replaced by an arbitrary reduced monomial in {X_{ij} : (i, j) ∈ R′}, and, in particular, by ∏_{(i,j)∈R′} X_{ij}^{q−1}.

This, in view of Lemma 30, shows that

\frac{F}{zw} + \frac{F}{xy} − (B_{0} ∏_{(i,j)∈R′} X_{ij}^{q−1}) + H ∈ ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ ,  (20)

where H ∈ 𝔽_{q}[X] is a reduced polynomial each of whose term has X_{ss}-degree or X_{st}-degree ≤ q − 3. By Lemmas 26 and 28, the first two terms in the above sum are in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩ and moreover, so is H, thanks to Lemma 27. It is now clear that (19) and (20) yield the desired result. □

An application of a classical result concerning permutations now yields the main result of this subsection.

Lemma 32. Let ρ be a nonnegative integer ≤ r and let M ∈ Δ_{ρ}(ℓ, m) and σ ∈ S_{ρ}. Then the binomial B_{M,σ} is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩.

Proof. If ρ ≤ 1, then σ is necessarily the identity permutation ϵ and B_{M,σ} = 0. Now assume that ρ > 1 and σ ≠ ϵ. Then σ is a nonempty product of transpositions in S_{ρ}, say σ = τ_{1}τ_{2} ⋯ τ_{t}. Define σ_{0} := ϵ and σ_{i} = τ_{1}τ_{2} ⋯ τ_{i} for 1 ≤ i ≤ t. Then σ_{i−1}^{−1}σ_{i} is a transposition for 1 ≤ i ≤ t, and hence using Lemma 31, we see that

B_{M,σ} = \frac{F}{t_{ϵ}(M)} − \frac{F}{t_{σ}(M)} = ∑_{i=1}^{t} \frac{F}{t_{σ_{i−1}}(M)} − \frac{F}{t_{σ_{i}}(M)}

is in ⟨ℱ_{min}^{∗}(ℓ, m; r)⟩. □

We are now ready to prove the main result of this section.

Theorem 33. C^{𝔸}(ℓ, m)^{⊥} is generated by its minimum-weight codewords.

Proof. Follows from Corollary 29 and Lemma 32. □

In the discussion before §6.1, we have noted that C^{𝔸}(ℓ, m; 0)^{⊥} is generated by its minimum-weight codewords. Moreover, analyzing the proofs of the results in this section, it can be seen that C^{𝔸}(ℓ, m; 1)^{⊥} is generated by its minimum-weight codewords. It is, however, easier to derive the result for C^{𝔸}(ℓ, m; 1)^{⊥} = RM(1, δ)^{⊥} = RM(δ(q − 1) − 2, δ) directly from Theorem 33 as shown below.

Corollary 34. For any positive integer d, the Reed-Muller codes RM(1, d) and RM(d(q − 1) − 2, d) are linear codes generated by their minimum-weight codewords.

Proof. Taking r = ℓ = 1 and ℓ′ = d in Proposition 18, we see that RM(1, d) is generated by its minimum-weight codewords. Moreover taking ℓ = 1 and ℓ′ = d in Theorem 33, we see that C^{𝔸}(1, d + 1)^{⊥} = RM(1, d)^{⊥} = RM(d(q − 1) − 2, d) is generated by its minimum-weight codewords. □

Remark 35. For the intermediate levels, generation by minimum-weight codewords is not true, in general. More precisely, if 1 < r < ℓ, then the minimum-weight codewords of C^{𝔸}(ℓ, m; r)^{⊥} need not generate C^{𝔸}(ℓ, m; r)^{⊥}. For example, if ℓ = ℓ′ = 3 and q = r = 2, then the affine Grassmann code C^{𝔸}(3, 6; 2) is a [512, 19, 192]- code, while its dual is a [512, 493, 4]-code, and a computer verification shows that the number of codewords of weight 4 in C^{𝔸}(3, 6; 2)^{⊥} and C^{𝔸}(3, 6; 3)^{⊥} is the same! Hence the minimum-weight codewords of C^{𝔸}(3, 6; 2)^{⊥} just generate C^{𝔸}(3, 6; 3)^{⊥}. In general, we have

C^{𝔸}(ℓ, m)^{⊥} = C^{𝔸}(ℓ, m; ℓ)^{⊥} ⊂ C^{𝔸}(ℓ, m; ℓ − 1)^{⊥} ⊂ ⋯ ⊂ C^{𝔸}(ℓ, m; 2)^{⊥} ⊂ C^{𝔸}(ℓ, m; 1)^{⊥}

and it seems plausible that for 1 < r < ℓ, the minimum of weight codewords of C^{𝔸}(ℓ, m; r)^{⊥} generate the smallest of these codes, namely, C^{𝔸}(ℓ, m)^{⊥}. In fact, the results of this section seem to show that the binomials and the non-forbidden monomials of type (ii) are generated by the minimum-weight codewords of C^{𝔸}(ℓ, m; r)^{⊥} for any r = 1, …, ℓ. In particular, they are generated by the minimum-weight codewords of C^{𝔸}(ℓ, m)^{⊥}. The difficulty arises due to maximal non-forbidden monomials of type (i), i.e., those given by (16). At any rate, a complete determination of the minimum-weight codewords of duals of affine Grassmann codes of any level and of the space generated by them could be an interesting problem.

Acknowledgments

We are grateful to the Otto Mønsted Foundation, which supported the visit of Sudhir Ghorpade to the Technical University of Denmark during May-July 2010 when some of this work was carried out.

References

[1] E. F. Assmus Jr. and J. D. Key, Designs and their Codes, Cambridge: Cambridge University Press, 1992.

[2] P. Beelen, S. R. Ghorpade, and T. Høholdt, “Affine Grassmann codes”, IEEE Trans. Information Theory, vol. 56, pp. 3166–3176, 2010.

[3] T. P. Berger and P. Charpin, “The automorphism group of generalized Reed-Muller codes”, Discrete Math., vol. 117, pp. 1–17, 1993.

[4] P. Delsarte, J. M. Goethals, and F. J. MacWilliams, “Generalized Reed-Muller codes and their relatives”, Inf. Control, vol. 16, pp. 403–442, 1974.

[5] P. Ding and J. D. Key, “Minimum-weight codewords as generators of generalized Reed-Muller codes”, IEEE Trans. Information Theory, vol. 46, pp. 2152–2158, 2000.

[6] S. R. Ghorpade, A. R. Patil and H. K. Pillai, “Decomposable subspaces, linear sections of Grassmann varieties, and higher weights of Grassmann codes”, Finite Fields Appl., vol. 15, pp. 54–68, 2009.

[7] J.-R. Joly, “Équations et variétés algébraiques sur un corps fini”, Enseign. Math., vol. 19, pp. 1–117, 1973.

[8] R. Knörr and W. Willems, “The automorphism groups of generalized Reed-Muller codes”, Astérisque, vol. 181–182, pp. 195–207, 1990.

[9] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, New York: Elsevier, 1977.

[10] V. Pless and W. C. Huffman (Eds.), Handbook of Coding Theory, Vols. I and II, Amsterdam: Elsevier, 1998.

Department of Mathematics, Technical University of Denmark, DK 2800, Lyngby, Denmark.

E-mail address: p.beelen@mat.dtu.dk

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

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

Department of Mathematics, Technical University of Denmark, DK 2800, Lyngby, Denmark.

E-mail address: T.Hoeholdt@mat.dtu.dk