The Fraction of Subspaces of GF(q)^{n} with a Specified Number of Minimal Weight Vectors is Asymptotically Poisson

Edward A. Bender Center for Communications Research 4320 Westerra Court San Diego, CA 92121, USA

                           ed@ccrwest.org

E. Rodney Canfield Department of Computer Science University of Georgia Athens, GA 30602, USA

                           erc@cs.uga.edu

Submitted: August 30, 1996; Accepted: November 27, 1996

Abstract

The weight of a vector in the finite vector space GF(q)^{n} is the number of nonzero components it contains. We show that for a certain range of parameters (n, j, k, w) the number of k-dimensional subspaces having j(q − 1) vectors of minimum weight w has asymptotically a Poisson distribution with parameter λ = \binom{n}{w}(q−1)^{w−1}q^{k−n}. As the Poisson parameter grows, the distribution becomes normal.

AMS-MOS Subject Classification (1990). Primary: 05A16 Secondary: 05A15, 11T99

1. Introduction

Almost all the familiar concepts of linear algebra, such as dimension and linear independence, are valid without regard to the characteristic of the underlying field. An example of a characteristic-dependent result is that a nonzero vector cannot be orthogonal to itself; researchers accustomed to real vector spaces must modify their “intuition” on this point when entering the realm of finite fields.

Let q be a prime power, fixed for the remainder of the paper, and GF(q) be the finite field with q elements. Because the underlying field is finite, there are many counting problems associated with fundamental concepts of linear algebra; for example, how many subspaces of dimension k are there in the vector space GF(q)^{n} ? The answer is often denoted \left[{n \atop k}\right]_{q}, and we have

\left[{n \atop k}\right]_{q} = \frac{(1 − q^{n})(1 − q^{n−1}) ⋯ (1 − q^{n−k+1})}{(1 − q^{k})(1 − q^{k−1}) ⋯ (1 − q)},

the Gaussian polynomial. The reader may consult [2] for an introduction to the subject.

Define the weight of a vector v in GF(q)^{n} to be the number of nonzero coordinates in v. The interaction of weight with familiar concepts of linear algebra yields more and harder counting problems. Consider the n vectors of weight 1 in GF(2)^{n}; how many vector spaces of dimension k do they span ? The easy answer is the well known binomial coefficient \binom{n}{k}. Now consider the \binom{n}{2} vectors of weight 2 in GF(2)^{n}; how many vector spaces of dimension k do they span ? More thought is needed this time, but again the answer is a classical array from combinatorics, the Stirling numbers of the second kind S(n, n − k). If we ask the same question for weight 3 or higher, no simple answer is known and the numbers cannot be computed easily. However, that familiar properties of \binom{n}{k} and S(n, k) persist in the higher weight version is part of a sweeping conjecture that the Whitney numbers of the second kind for any geometric lattice are log-concave. [1, p.141]

Extend the notion of weight to subspaces by saying that a subspace V ⊆ GF(q)^{n} has weight w if w is the minimum weight of all nonzero vectors in V. A natural problem is to describe how the \left[{n \atop k}\right]_{q} subspaces of dimension k are distributed by weight. We cannot give a definitive solution to this question, but using asymptotic methods, we can gain some insight into the problem. The number of weight w vectors in a vector space over GF(q) is a multiple of q − 1 since multiplication by a nonzero scalar preserves weight. Let p(j; n, k, w) be the fraction of k-dimensional subspaces of GF(q)^{n} containing j(q − 1) vectors of weight w, and no nonzero vector of weight less than w. Masol [3] showed that

p(0; n, k, 1) − e^{−λ} → 0 uniformly as n → ∞ where λ = nq^{k−n}.

We extend this result as follows:

Theorem 1. Fix a prime power q, positive constants b ≤ \frac{1}{2} and B < 1 − b, and a function μ(n) = o(1). Then, uniformly for j, k, w satisfying

1 ≤ w ≤ μ(n)n^{b}/ log_{q} n and λ ≡^{def} \binom{n}{w}(q − 1)^{w−1}q^{k−n} ≤ B log_{q} n, (1)

we have

p(j; n, k, w) − λ^{j}e^{−λ}/j! → 0 as n → ∞.

Theorem 2. Fix a prime power q, positive constants b ≤ \frac{1}{2} and B < 1 − b, and a function μ(n) = o((log n)^{−1/4}). When (1) holds,

\sqrt{2πλ} p(j; n, k, w) − e^{−(j−λ)^{2}/2λ} → 0 uniformly as λ → ∞.

We remind the reader of the meaning of uniformity. A function f : N^{ℓ} → N goes to 0 as n → ∞, uniformly over A ⊆ N^{ℓ}, provided

sup_{a∈A_{n}} |f(n, a)| → 0 as n → ∞, where A_{n} = {a ∈ N^{ℓ−1} : (n, a) ∈ A}.

Since (q − 1)λ/q^{k} is the the probability that a randomly chosen vector has weight w, the distribution of (q − 1)-tuples of weight w vectors in k-dimensional subspaces is asymptotically the same as the distribution of weight w vectors in random samples of \frac{q^{k}−1}{q−1} (nonzero) vectors: They are asymptotically Poisson with parameter λ. A point in projective space is the (q − 1)-tuple of scalar multiples of a nonzero point in GF(q)^{n}. Thus, in a projective n-space over GF(q), the previous observation states that the distribution of weight w points is asymptotically the same among random sets of \frac{q^{k}−1}{q−1} points and among random (k − 1)-dimensional projective subspaces, namely Poisson with parameter λ.

2. Proof of the theorems

We will find it convenient to work with the somewhat larger

λ ≡^{def} \frac{(q − 1)^{w−1}n^{w}}{q^{n−k}w!} ≤ B log_{q} n,  (2)

rather than the definition in (1). Since the ratio of the two versions of λ is

\frac{\binom{n}{w}w!}{n^{w}} = (1 − O(w/n))^{w} = exp(O(w^{2}/n)) = exp(o(1/(log n)^{2})),

it is easily seen that the ratio of the two versions of λ tends to 1 and also that the theorems for either version of λ imply the theorems for the other version. Since the ratio of the two versions of λ approach 1, the inequality in (2) follows from that in (1) by replacing B with the average of B and 1 − b.

Let d = n − k, ϵ = (1 − b − B)/2, and J = (B + ϵ) log_{q} n. Making μ(n) larger if necessary, we may assume

μ(n) ≥ max(n^{−b}, e^{−ϵ^{2} log_{q} n/4}).  (3)

Our proof consists of five parts:

(a) Eliminating small k.

(b) Some easy estimates.

(c) Conversion of the problem to the study of d × n matrices over GF(q).

(d) An estimate for j ≤ J.

(e) Completion of the proof. Although we will not explicitly state it, all estimates in o(⋯) and O(⋯) as well as all estimates of the form ⋯ → ⋯ are uniform.

(a) Eliminating small k. Suppose Theorem 1 holds for k = k_{0} ≡^{def} ⌈n/2⌉. We will deduce that it holds for k < k_{0}. From the bound on w in (1), it follows that λ → 0 whenever k ≤ k_{0}. Since Theorem 1 is equivalent to p(0; n, k, w) = 1 − o(1) when λ → 0, it suffices to prove that p(0; n, k, w) ≥ p(0; n, k_{0}, w) when k < k_{0}.

To this end we recall a property of downsets in regular ranked posets. A ranked poset P is regular provided that every element of rank k is comparable to the same number of elements of rank k + 1, and likewise k − 1. (This is the requirement that each of the bipartite graphs formed by restricting the covering relation of P to two adjacent ranks be regular in the graph theoretic sense.) For example, both the subsets of a set and the subspaces of a vector space, ordered by inclusion, are regular. A downset in a partially ordered set is a set S such that x ∈ S and y < x imply y ∈ S. We claim that if S is a downset then the fraction |S ∩ P_{k}|/|P_{k}| decreases with k, where P_{k} is the set of elements of rank k. To see this, let α and β be the common degrees of elements in the bipartite graph P_{k} × P_{k+1}. Clearly

|P_{k}|α = β|P_{k+1}|.  (4)

Since S is a downset, every element of S ∩ P_{k+1} is related to β elements of S ∩ P_{k}. Hence

|S ∩ P_{k}|α ≥ β|S ∩ P_{k+1}|.

Dividing the left side by the left side of (4) and the right side by the right side of (4) proves the claim.

Let I_{j} be the set of subspaces of GF(q)^{n} that contain at most j(q − 1) vectors of weight w and no nonzero vectors of less weight. Since this is a downset in the poset of subspaces of GF(q)^{n}, the fraction of k-dimensional subspaces that lie in I_{j} is a decreasing function of k and hence p(0; n, k, w) ≥ p(0; n, k_{0}, w) when k < k_{0}.

From now on, we assume that k ≥ k_{0} = ⌈n/2⌉.  (5)

(b) Some easy estimates. By (1)

λ^{2}w^{2}/n < J^{2}w^{2}/n < μ(n)^{2} → 0  (6)

and

q^{−d}(ej)^{w} = λ(q − 1) (\frac{ejw}{(q − 1)n})^{w} ≤ λ(q − 1) (\frac{ejw}{(q − 1)n}) = O(J^{2}w/n) (7)

when j ≤ J. Taking logarithms in (2) and using Stirling’s formula, we have

d − Jw = w{log_{q} n − log_{q}w − J + O(1)} − log_{q} λ
= w{(1 − B − ϵ) log_{q} n − log_{q}w + O(1)} − O(log log n).

Fix K. Since 1 − B − ϵ = (1 + b − B)/2 > b, it follows easily that

w{(1 − B − ϵ) log_{q} n − log_{q} w + K}

is an increasing function of w for sufficiently large n. Hence, for sufficiently large n,

d − j(w − 1) ≥ b log_{q} n when j ≤ J.  (8)

(c) Conversion to d × n Matrices. For V a subspace of GF(q)^{n} let V^{⊥} be its orthogonal complement, the set of vectors orthogonal to every element of V. As noted in the introduction, for nonzero characteristic the intersection V ∩ V^{⊥} may have positive dimension; nevertheless, it is easily checked that the map V ↦ V^{⊥} is a bijection from k-dimensional to d-dimensional subspaces. So it suffices to work with V^{⊥}.

Let H be a d × n matrix whose rows form a basis for V^{⊥} (in coding theory terminology, a checksum matrix for V). Denote the columns of H by h_{i}. Note that ∑ v_{i}h_{i} = 0 if and only if v ∈ V. If a set S of vectors is linearly dependent and no proper subset is, then call the set minimally dependent. If w is the minimal weight in V, the previous discussion shows that there is a bijection between sets of w minimally dependent vectors among the columns of H and (q − 1)-tuples of vectors of weight w in V, where a tuple consists of all nonzero multiples of a weight w vector.

Since every d-dimensional subspace of GF(q)^{n} has the same number of ordered bases, the fraction of ordered bases with a desired property will be the same as the fraction of d-dimensional subspaces with the property. We will look at ordered bases.

The rows of H are required to be independent; however, the fraction of all d×n matrices with this property is

\begin{aligned}q^{−nd} ∏_{i=0}^{d−1}(q^{n} − q^{i}) & = ∏_{t=k+1}^{n}(1 − q^{−t}) = exp(−∑_{t=k+1}^{n}q^{−t} + O(q^{−2t})) \\ & = exp(O(q^{−k})) = 1 + O(q^{−n/2}), \end{aligned}  (9)

by (5). We can, in effect, ignore the requirement that the rows of H be independent.

(d) An estimate for j ≤ J. In this part of the proof, we will show that

p(j; n, k, w) ≥ (λ^{j}e^{−λ}/j!){1 + O(μ(n)^{2})} + O(q^{−n/2}) when j ≤ J.  (10)

It is instructive, and useful, to treat part of the w = 1 case separately. A 1-set of minimally dependent vectors must be {0}. Hence the fraction of H containing exactly j such sets is

q^{−nd}\binom{n}{j}(q^{d} − 1)^{n−j} = \frac{n^{j}}{q^{jd}j!} exp(O(j^{2}/n) − (n − j)q^{−d}(1 + O(q^{−d}))

uniformly since j = o(n^{1/2}). Using, (9), the theorem now follows easily.

For w > 1, we generalize this argument. There is a complication: It is now possible for w-sets of minimally dependent vectors to overlap. We count some of the subspaces with nonoverlapping cases and show that this consists of almost all subspaces. Here is how we choose the columns:

(a) Repeat j times: Choose w columns of minimal dependency that are independent of the columns already chosen.

(b) Choose the remaining n − jw columns to avoid introducing more dependent sets of size w or less.

(c) Choose how to order the vectors. Let N_{a} and N_{c} be the number of ways to carry out the choices in (a) and (c). The number of ways to carry out (b) depends on the choices in (a). Let N_{b} be a lower bound on the number of ways to carry out (b). We seek a lower bound for N_{a}N_{b}N_{c}.

Suppose that i sets have been chosen in (a). Since the vectors already chosen span a space of dimension i(w − 1), the next set can be chosen in

(q^{d} − q^{i(w−1)})(q^{d} − q^{i(w−1)+1}) ⋯ (q^{d} − q^{i(w−1)+w−2}) × (q − 1)^{w−1}

ways and so

\begin{aligned}N_{a} & = (q^{d}(q − 1))^{j(w−1)} ∏_{t=0}^{j(w−1)−1}(1 − q^{t−d}) \\ & = (q^{d}(q − 1))^{j(w−1)} exp(O(q^{j(w−1)−d})) = (q^{d}(q − 1))^{j(w−1)}(1 + O(n^{−b})) \end{aligned}

by (8).

An upper bound on the number of vectors that can be expressed as a linear combination of at most w−1 of the vectors in an i-set is h(i, w) = ∑_{l≤w−1}(q−1)^{l}\binom{i}{l}. Thus

N_{b} ≥ ∏_{i=jw}^{n−1}(q^{d} − h(i, w)) = q^{d(n−jw)} ∏_{i=jw}^{n−1} exp(−q^{−d}h(i, w) + O(q^{−2d}h(i, w)^{2}))

the electronic journal of combinatorics 4 (1997), #R3 7

provided the expression inside the O( ) is bounded. Now

q^{−d}h(i, w) < q^{−d}(q − 1)^{w−1}\binom{n}{w − 1}O(1) = O(wλ/n),

and so

N_{b} ≥ q^{d(n−jw)} exp(−q^{−d} ∑_{l≤w−1}(q − 1)^{l} ∑_{i=jw}^{n−1} \binom{i}{l} + O(w^{2}λ^{2}/n))  (11)

by (6). Note that for w ≥ 1, using Stirling’s formula,

∑_{l≤w−1} \binom{jw}{l + 1} = O(1)\binom{jw}{w} = O((ej)^{w}).

Since

∑_{l≤w−1}(q − 1)^{l} ∑_{i=jw}^{n−1} \binom{i}{l} = ∑_{l≤w−1}(q − 1)^{l} (\binom{n}{l + 1} − \binom{jw}{l + 1})

= (q − 1)^{w−1}\binom{n}{w}\{1 + O(w/n)\} + O((ejq)^{w})

= \frac{(q − 1)^{w−1}n^{w}}{w!} \{1 + O(w^{2}/n)\} + O((ejq)^{w}),

we find, using (11), (7), and the definition of λ,

\begin{aligned}N_{b} & ≥ q^{d(n−jw)} exp(−λ(1 + O(w^{2}/n)) + O(J^{2}w/n) + O(w^{2}λ^{2}/n)) \\ & = q^{d(n−jw)}e^{−λ}(1 + O(J^{2}w^{2}/n)). \end{aligned}

Finally, the number of ways to arrange the vectors, taking into account the fact that there is already some ordering among them is

N_{c} = \frac{n!}{j!(w!)^{j}(n − wj)!} = \frac{n^{wj}}{j!(w!)^{j}} (1 + O(w^{2}j^{2}/n)).

Putting all these results together, we obtain the lower bound

N_{a}N_{b}N_{c} ≥ q^{nd}(λ^{j}e^{−λ}/j!){1 + O(J^{2}w^{2}/n) + O(n^{−b})}.  (12)

Equation (10) follows from (9), (12), and (3).

(e) Completion of the Proof. Summing (10) over j ≤ J gives

\begin{aligned}1 ≥ ∑_{j≤J} p(j; n, k, w) & ≥ (1 + O(μ(n)^{2}))e^{−λ} ∑_{j≤J} \frac{λ^{j}}{j!} + O(Jq^{−n/2}) \\ & = 1 + O(μ(n)^{2}) − ∑_{j>J} \frac{λ^{j}}{e^{λ}j!}, \end{aligned}  (13)

where the last equality follows from (3), (5), and the definition of J. Since the ratio of consecutive terms in the last summation is less than

\frac{λ^{J+1}}{(J + 1)!}/ \frac{λ^{J}}{J!} < λ/J ≤ \frac{B}{B + ϵ} = 1 − \frac{ϵ}{B + ϵ},

we have

∑_{j>J} \frac{λ^{j}}{e^{λ}j!} < \frac{B + ϵ}{ϵ} \frac{λ^{J}}{e^{λ}J!} < \frac{B + ϵ}{ϵ} (\frac{λ}{J} )^{J} e^{J−λ}.

Since this is an increasing function of λ, it is bounded above by O(D^{log_{q} n}) where

D = (\frac{B}{B + ϵ})^{B+ϵ}e^{ϵ}.

For a fixed ϵ, (\frac{B}{B+ϵ})^{B+ϵ} increases with B; letting B equal 1, and using 0 < ϵ < 1/2 and 1 + ϵ ≥ e^{ϵ−ϵ^{2}/2}, we see

D ≤ (1 + ϵ)^{−1−ϵ}e^{ϵ} ≤ e^{−ϵ^{2}/2+ϵ^{3}/2} ≤ e^{−ϵ^{2}/4}.

Thus (13) becomes

1 ≥ ∑_{j≤J} p(j; n, k, w) ≥ 1 + O(μ(n)^{2}) + O(D^{log_{q} n}) = 1 + O(μ(n)^{2}), (14)

where the last equality follows from (3). It follows that

p(j; n, k, w) = \frac{λ^{j}e^{−λ}}{j!} + O(μ(n)^{2}) for j ≤ J  (15)

and p(j; n, k, w) = O(μ(n)^{2}) for j > J. This completes the proof of Theorem 1.

We now turn to Theorem 2. The standard approximation of the Poisson distribution by the normal says

\sqrt{2πλ} (\frac{λ^{j}e^{−λ}}{j!} ) − e^{−(j−λ)^{2}/2λ} → 0 uniformly in j as λ → ∞.

(This can be obtained directly from Stirling’s formula.) Since λ^{1/2}μ(n)^{2} → 0, Theorem 2 follows from (15).

References

1. M. Aigner, Whitney numbers. In N. White (ed.), Combinatorial Geometries, volume II, Cambridge University Press (1987) 139–160.

2. J. R. Goldman and G.-C. Rota, On the foundations of combinatorics, IV: Finite vector spaces and Eulerian generating functions, Studies Appl. Math. 49 (1970) 239–258.

3. V. I. Masol, The asymptotics of the number of k-dimensional subspaces of minimal weight over a finite field, Random Oper. and Stoch. Eqs. 1 (1993) 287–292.