Finite vector spaces and certain lattices

Thomas W. Cusick

106 Diefendorf Hall, Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14214-3093 E-mail: cusick@acsu.buffalo.edu

Submitted: January 6, 1998; Accepted: March 18, 1998

Abstract

The Galois number G_{n}(q) is defined to be the number of subspaces of the n-dimensional vector space over the finite field GF (q). When q is prime, we prove that G_{n}(q) is equal to the number L_{n}(q) of n-dimensional mod q lattices, which are defined to be lattices (that is, discrete additive subgroups of n-space) contained in the integer lattice Z^{n} and having the property that given any point P in the lattice, all points of Z^{n} which are congruent to P mod q are also in the lattice. For each n, we prove that L_{n}(q) is a multiplicative function of q.

Keywords: Multiplicative function; Lattice; Galois numbers; Vector space; Identities

1991 Mathematical Reviews subject numbers: Primary 05A15 05A19 11A25 11H06

Secondary 05A30 94A60 11T99

1 Introduction

The well known Gaussian coefficient (or q-binomial coefficient)

\binom{n}{r}q = \frac{(q^{n} − 1)(q^{n−1} − 1) ⋯ (q^{n−r+1} − 1)}{(q^{r} − 1)(q^{r−1} − 1) ⋯ (q − 1)}

is equal to the number of r-dimensional vector subspaces of the n-dimensional vector space V_{n}(q) over the finite field GF (q). We let G_{n} = G_{n}(q) denote the total number of vector subspaces of V_{n}(q). The numbers G_{n} were named the Galois numbers by Goldman and Rota [4, p. 77].

Goldman and Rota [4] proved the recursion formula

G_{n+1} = 2G_{n} + (q^{n} − 1)G_{n−1}  (1)

for the Galois numbers.

Nijenhuis, Solow and Wilf [4] gave a different proof of (1) by using the observation that the r-dimensional vector subspaces of V_{n}(q) are in one-to-one correspondence with the n by n matrices over GF (q) which have rank r and are in reduced row echelon form (rref). Recall that such a matrix is in rref if its last n − r rows are all zeros; in each of the first r rows the first nonzero entry is a 1; the index of the i-th column (called a pivotal column) in which one of these r 1’s occurs strictly increases as i increases; and each of these r pivotal columns has only a single nonzero entry. We let E(r, n, q) denote the number of n by n matrices with rank r over the field GF (q) which are in rref. Then it was proved in [4] that

G_{n}(q) = ∑_{r=0}^{n} E(r, n, q).  (2)

The correspondence mentioned above gives

E(r, n, q) = \binom{n}{r}q.  (3)

For example, E(r, 4, 2) for r = 0, 1, 2, 3, 4 is 1, 15, 35, 15 and 1, respectively.

We shall need the concept of an n-dimensional mod q lattice, which is defined to be an n-dimensional lattice contained in the integer lattice Z^{n} and having the special property that given any point P in the lattice, all points of Z^{n} which are congruent to P mod q are also in the lattice. Later in this paper we shall show how the mod q lattices are connected to the Galois numbers G_{n}(q). It also turns out that the mod q lattices have an important application in cryptography, which we discuss elsewhere [2]. The set of mod q lattices contains various special subsets which can be used in the design of a novel kind of public-key cryptosystem. This idea originated with Ajtai [1].

2 The multiplicative property

We let L_{m}(q) denote the number of m-dimensional mod q lattices. Our first goal is to prove that L_{m}(q) is a multiplicative function, that is, for any positive integers r and s with gcd(r, s) = 1 we have L_{m}(rs) = L_{m}(r)L_{m}(s).

Theorem 1. The function L_{m}(q) is multiplicative for each m = 2, 3, . . ..

Proof. Clearly, every m-dimensional mod q lattice is the solution space of some system

Ax ≡ 0 mod q,  (4)

where A is an m by m matrix over the integers mod q. Conversely, the solution space of any system (4) is a mod q lattice. (Note that if e_{1}, e_{2}, …, e_{m} is the standard basis for R^{m}, then the m linearly independent vectors qe_{i} (1 ≤ i ≤ m) are always solutions of (4), so the solution space is always a lattice of dimension m.)

If gcd(r, s) = 1, there is a bijection between the set of m-dimensional mod rs lattices and the set of pairs of m-dimensional lattices made up of one mod r lattice and one mod s lattice. The bijection is defined as follows: Given a mod rs lattice which is the solution space of Ax ≡ 0 mod rs, we associate with it the pair of lattices which are solution spaces of

Bx ≡ 0 mod r and Cx ≡ 0 mod s,  (5)

where the matrices B and C are defined by

A ≡ B mod r and A ≡ C mod s;  (6)

and conversely, given (5) we define a matrix A by (6).

To prove that this is a bijection, we must first show that different lattice pairs give different mod rs lattices. Given relatively prime integers r and s, by the definition of L_{m}(q) we can choose two sets of matrices {B_{i} : 1 ≤ i ≤ L_{m}(r)}, where B_{i} is defined over the integers mod r, and {C_{i} : 1 ≤ i ≤ L_{m}(s)}, where C_{i} is defined over the integers mod s, such that every m-dimensional mod r lattice is the solution space of exactly one of the systems B_{i}x ≡ 0 mod r, 1 ≤ i ≤ L_{m}(r), and every m-dimensional mod s lattice is the solution space of exactly one of the systems C_{j}x ≡ 0 mod s, 1 ≤ j ≤ L_{m}(s). Since gcd(r, s) = 1, the theory of linear congruences in one variable shows that each pair of simultaneous congruences

A ≡ B_{i} mod r, A ≡ C_{j} mod s, 1 ≤ i ≤ L_{m}(r), 1 ≤ j ≤ L_{m}(s)  (7)

defines a unique m by m matrix A = A_{ij}, say, over the integers mod rs, and these matrices are all different since the pairs B_{i}, C_{j} are. We shall show that the solution spaces (which are the mod rs lattices) of the systems

A_{ij}x ≡ 0 mod rs, 1 ≤ i ≤ L_{m}(r), 1 ≤ j ≤ L_{m}(s)

are all distinct.

Let A_{IJ} and A_{KL} be any two different matrices chosen from the A_{ij}’s. Then by (7),

{x mod r : A_{IJ}x ≡ 0 mod rs} = {x : B_{I}x ≡ 0 mod r}

and

{x mod s : A_{IJ}x ≡ 0 mod rs} = {x : C_{J}x ≡ 0 mod s};

similar equations hold for A_{KL}. Since the pairs B_{I}, C_{J} and B_{K}, C_{L} are different, we have either

{x : B_{I}x ≡ 0 mod r} ≠ {x : B_{K}x ≡ 0 mod r}

or

{x : C_{J}x ≡ 0 mod s} ≠ {x : C_{L}x ≡ 0 mod s},

so the solution spaces for A_{IJ} and A_{KL} are different.

Finally we must show that different mod rs lattices give different lattice pairs. This is clear since each congruence Ax ≡ 0 mod rs gives a unique pair of congruences (5), where the matrices B and C are defined by (6).

3 Counting mod q lattices

Our first goal is to prove explicit formulas for the number of m-dimensional mod q lattices, which we denote by L_{m}(q), when m is small.

Theorem 2. The numbers L_{2}(q) and L_{3}(q) are given by

L_{2}(q) = ∑_{k_{1}|q} ∑_{k_{2}|q} gcd (k_{1}, \frac{q}{k_{2}} )  (8)

and

L_{3}(q) = ∑_{k_{1}|q} ∑_{k_{2}|q} ∑_{k_{3}|q} gcd (k_{1}, \frac{q}{k_{3}} ) gcd (k_{2}, \frac{q}{k_{3}} ) gcd (k_{1}, \frac{q}{k_{2}} ) .  (9)

We shall prove formula (8) first. We fix an x_{1}, x_{2} Cartesian coordinate system in R^{2}. Given any 2-dimensional mod q lattice Λ, we have a basis-free representation for it as follows: The x_{1} axis contains infinitely many points of Λ, with a density 1/k_{1}, where k_{1} is a positive integer which divides q. Every line x_{2} = c either contains no points of Λ or contains a shifted copy of the set of lattice points on x_{2} = 0. If x_{2} = k_{2} is the line x_{2} = c > 0 which is closest to the x_{1} axis and has points of Λ, then k_{2} is a divisor of q. A line x_{2} = c contains points of Λ if and only if has the form x_{2} = tk_{2} for some integer t. We say that Λ has jump k_{2} (in the x_{2} direction). If we let C_{2}(Λ) denote the 2-dimensional volume of a fundamental cell of Λ, then we have C_{2}(Λ) = k_{1}k_{2}.

To count the 2-dimensional mod q lattices which have given values of k_{1} and k_{2}, it suffices to count the number of distinct 1-dimensional sublattices on x_{2} = k_{2} which give a mod q lattice. We define the shift s, where s is an integer such that 0 ≤ s < k_{1}, to be the amount by which the 1-dimensional sublattice on x_{2} = k is shifted with respect to the 1-dimensional sublattice on x_{2} = 0. In order to give a mod q lattice, the shift s must give a 1-dimensional sublattice on x_{2} = q which is an unshifted copy of the same sublattice on x_{2} = 0. The sublattice on x_{2} = q is shifted from the one on x_{2} = 0 by qs/k_{2}, so the shift s gives a mod q lattice if and only if

k_{1} divides qs/k_{2}.  (10)

Clearly (10) holds for given k_{1} and k_{2} if and only if k_{1}k_{2}/ gcd(k_{1}k_{2}, q) = D, say, divides s. Thus there are k_{1}/D = gcd(k_{1}, q/k_{2}) allowable values of s in the range 0 ≤ s < k_{1}. This proves (8).

Now we prove formula (9). Each 3-dimensional mod q lattice Λ is made up of a 2-dimensional mod q sublattice in the x_{1}, x_{2} plane, which we denote by P_{0}, and shifted copies of this sublattice in each of various planes P_{i} (i nonzero integer) which are equally spaced parallel to P_{0}. As before, we let 1/k_{1} denote the density of the points of Λ on the x_{1} axis and we let k_{2} denote the jump in the x_{2} direction for the sublattice in P_{0} (and so for Λ). The plane P_{1} nearest to P_{0} is at a distance k_{3}, where k_{3} is a divisor of q. We say that Λ has jump k_{3} in the x_{3} direction. If we let C_{3}(Λ) denote the 3-dimensional volume of a fundamental cell of Λ, then we have C_{3}(Λ) = k_{1}k_{2}k_{3}.

To count the 3-dimensional mod q lattices with given k_{1}, k_{2} and k_{3}, for each 2dimensional mod q sublattice on P_{0} we count the number of distinct 2-dimensional sublattices in x_{3} = k_{3} (i.e., the plane P_{1}) which give a mod q lattice. We let s denote the shift for the 1-dimensional sublattices in P_{0}, as before, and we define the (vector) shift s = (s_{1}, s_{2}), where 0 ≤ s_{i} < k_{i} (i = 1, 2), to be the amount by which 0 in P_{0} is moved when we go to the sublattice in P_{1}. The shift s gives a mod q lattice if and only if

k_{1} divides qs_{1}/k_{3} and k_{2} divides qs_{2}/k_{3},  (11)

that is, if and only if the orthogonal projection of (q/k_{3})(s_{1}, s_{2}, k_{3}) into the plane P_{0} is a lattice point. Now (11) holds for given k_{1}, k_{2} and k_{3} if and only if k_{i}k_{3}/ gcd(k_{i}k_{3}, q) = D_{i}, say, divides s_{i} (i = 1, 2). Thus there are k_{i}/D_{i} = gcd(k_{i}, q/k_{3}) allowable values of s_{i} in the range 0 ≤ s_{i} < k_{i}. This proves (9).

It is possible to extend the formula in Theorem 2 to the case of general m, but complicated m-fold sums are involved. Since we do not need this result, we do not give it here.

A multiplicative function is completely determined by its values at prime powers, so it is of interest to examine L_{m}(p^{a}) for prime p. Direct calculation using (8) gives

L_{2}(p^{a}) = ∑_{i=0}^{a}(1 + 2i)p^{a−i} = \frac{(p + 1)p^{a+1} − (2a + 3)p + 2a + 1}{(p − 1)^{2}}.

Computer calculations using (9) give Table 1, which shows the expansion of L_{3}(p^{a}) in powers of p for small a. There does not seem to be any nice explicit formula for L_{3}(p^{a}), though various properties of the coefficients in the table can be deduced. Table 2 gives some values for L_{2}(q) and L_{3}(q).

a, j → 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1  4 2 2
2  7 6 6 5 3
3  10 10 12 10 10 8 4
4  13 14 18 17 18 14 15 11 5
5  16 18 24 24 28 22 24 20 20 14 6
6  19 22 30 31 38 32 35 30 30 27 25 17 7
7  22 26 36 38 48 42 48 42 42 38 38 34 30 20 8

Table 1: Coefficients of p^{j} in the expansion of L_{3}(p^{a}), a ≤ 7.

2 3 4 5 7 8 9 11 13 16 17 19 23
L_{2}(q) 5 6 15 8 10 37 23 14 16 83 20 22 26
L_{3}(q) 16 28 131 64 116 830 457 268 368 4633 616 1016 1108

Table 2: Values of L_{2}(q) and L_{3}(q) for small prime powers q.

4 The connection with Galois numbers

Because of (2), our next theorem shows that L_{m}(q) = G_{m}(q) whenever q is a prime.

Theorem 3. For any prime q, we have

L_{m}(q) = ∑_{r=0}^{m} E(r, m, q).

Proof. We have already seen that every m-dimensional mod q lattice is the solution space of some system (4), where A is an m by m matrix over the integers mod q. Conversely, the solution space of any system (4) is an m-dimensional mod q lattice. Since q is prime, the mod q lattices are thus in one-to-one correspondence with the m by m reduced row echelon forms of matrices over GF (q) and we have the desired equation.

Because of (3), it is easy to compute E(r, m, q) for given values of r, m, q.

If q is not prime, the first two sentences in the proof of Theorem 3 are still true, so the one-to-one correspondence between the mod q lattices and solution spaces of systems (4) is still valid. What is lost is the link with matrices over a field which are in reduced row echelon form (rref). Thus this paper shows that there are two different natural extensions of the Galois numbers G_{n}(q), q prime. One extension leads to the Galois numbers G_{n}(q) for arbitrary positive integers q, as given in [4]. In that paper a formal definition of a rref matrix over a set of q symbols is given and finite fields play no role. For each n, the numbers G_{n}(q) are fixed polynomials in q, and the recursion (1) holds as a polynomial identity. The other extension leads to the multiplicative functions L_{n}(q) in this paper. If q is not prime, then L_{n}(q) is not a polynomial in q and the analog of (1) does not hold.

References

[1] Miklos Ajtai, Generating hard instances of lattice problems, in: Proc. 28th ACM Symposium on the Theory of Computing, 1996, pp. 99-108.

[2] Thomas W. Cusick, The Ajtai random class of lattices, to appear.

[3] Jay Goldman and Gian-Carlo Rota, The number of subspaces of a vector space, in: Recent Progress in Combinatorics, ed. W. T. Tutte (Academic Press, 1969), pp. 75-83.

[4] Albert Nijenhuis, Anita E. Solow and Herbert S. Wilf, Bijective methods

in the theory of finite vector spaces, J. Combin. Theory (A) 37 (1984), 80-84.