%% A LaTeX file for a 7-page document
\documentclass[12pt]{article}
\usepackage{amsmath,amsthm}
\let\workingver=n
\renewcommand {\b}{\bar}
\newcommand{\bb}{\bar}
\newcommand{\hs }{\hspace{.6cm}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\gata}{\end{equation}}
\def\sms{\small\scshape}
\def\op{\oplus}
\def\ler{\Longleftrightarrow}
\textheight=22.9cm
\textwidth=15.2cm
%\textheight=20.5cm
%\textwidth=14.9cm
\oddsidemargin=0.7cm
\evensidemargin=0cm
\topmargin=0cm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\refeq#1{\if\workingver y(\ref{#1})-[[#1]]\else(\ref{#1})\fi}
\def\refth#1{\if\workingver y\ref{#1}-[[#1]]\else\ref{#1}\fi}
\def\mylabel#1{\if\workingver y\label{#1}{\bf\ \ [[#1]]\ \ }\else\label{#1}\fi}
\def\mybibitem#1{\if\workingver y\bibitem{#1}{\bf\ \ [[#1]]\ \ }\else\bibitem{#1}\fi}
\def\monitorstyle{
\setlength{\textheight}{15cm}
}
\def\lcdstyle{
\setlength{\textheight}{9cm}
\setlength{\textwidth}{14.5cm}
}
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ex}[thm]{Example}
\newtheorem{algo}[thm]{Algorithm}
\newtheorem{rem}[thm]{Remark}
\newtheorem{conj}[thm]{Conjecture}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\eps{\epsilon}
\def\ga{\gamma}
\def\be{\beta}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\st{\star}
\def\Mod{{\rm Mod}}
\def\dbl{\left[\left[}
\def\dbr{\right]\right]}
\def\Det{{\rm Det}}
\def\R{{\bf R}}
%%%%%%%%%%%%%%%%%%%%%%%
\font\tenrm=cmr10
\font\tensl=cmsl10
\font\ninerm=cmr9
\font\erm=cmr8
\begin{document}
%\baselineskip=2\baselineskip
\title{\bf Finite vector spaces and certain lattices}
\author{Thomas W. Cusick}
\date{
\small 106 Diefendorf Hall, Department of Mathematics,\\
\small State University of New York at Buffalo, Buffalo, NY 14214-3093\\
{E-mail: cusick@acsu.buffalo.edu}}
\maketitle
\begin{center}
Submitted: January 6, 1998; \ Accepted: March 18, 1998
\end{center}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 5 (1998), \#R17\hfill}
\thispagestyle{empty}
\begin{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 ${\bf Z}^n$ and
having the property that given any point $P$ in the lattice, all points of
${\bf 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$.
\end{abstract}
{\it Keywords:}\ {\tenrm Multiplicative function; Lattice; Galois numbers;
Vector space; Identities}\\
{\it 1991 Mathematical Reviews subject numbers:}\ {\tenrm Primary 05A15
05A19 11A25 11H06\\ Secondary 05A30 94A60 11T99}
\newpage
\section{Introduction}
The well known {\it Gaussian coefficient} (or q-binomial coefficient)
\[
\binom{n}{r}_{\textstyle q}=
\frac{(q^n-1)(q^{n-1}-1)\cdots (q^{n-r+1}-1)}{(q^r-1)(q^{r-1}-1)\cdots (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 {\it Galois numbers} by
Goldman and Rota [4, p. 77].
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\L{\Lambda}
\def\v{{\bf v}}
\def\h{{\bf h}}
\def\e{{\bf e}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
Goldman and Rota [4] proved the recursion formula
\beq
G_{n+1}=2G_n+(q^n - 1)G_{n-1}
\end{equation}
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 {\it 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
\beq
G_n(q)=\sum_{r=0}^n E(r,n,q).
\end{equation}
The correspondence mentioned above gives
\beq
E(r,n,q)=\binom{n}{r}_{\textstyle q}.
\end{equation}
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 {\it mod $q$ lattice},
which is defined to be an n-dimensional lattice contained in the integer
lattice ${\bf Z}^n$ and having the special property that given any point
$P$ in the lattice, all points of ${\bf Z}^n$ which are congruent to
$P\bmod 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].
\section{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)$.
\begin{thm}
The function $L_m(q)$ is multiplicative for each $m=2,3,\ldots$.
\end{thm}
\begin{proof}
Clearly, every $m$-dimensional mod $q$ lattice is the solution
space of some system
\beq
A{\bf x}\equiv 0\bmod q,
\end{equation}
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,\ldots,\e_m$ is the standard basis for
${\bf R}^m$,
then the $m$ linearly independent vectors $q\e_i\ (1\leq i\leq 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
$A{\bf x}\equiv 0\bmod rs$, we associate with it the pair of lattices
which are solution spaces of
\beq
B{\bf x}\equiv 0\bmod r\ \text{and}\ C{\bf x}\equiv 0\bmod s,
\end{equation}
where the matrices $B$ and $C$ are defined by
\beq
A\equiv B\bmod r\ \text{and}\ A\equiv C\bmod s;
\end{equation}
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\leq i\leq L_m(r)\}$, where
$B_i$ is defined over the integers mod $r$, and $\{C_i: 1\leq i\leq
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{\bf x}\equiv 0\bmod r,\ 1\leq i\leq L_m(r),$
and every $m$-dimensional mod $s$ lattice is the solution space of exactly
one of the systems
$C_j{\bf x}\equiv 0\bmod s,\ 1\leq j\leq L_m(s).$
Since $\gcd(r,s)=1$, the theory of linear congruences in one variable
shows that each pair of simultaneous congruences
\beq
A\equiv B_i\bmod r,\ A\equiv C_j\bmod s,\ 1\leq i\leq L_m(r),\ 1\leq
j\leq L_m(s)
\end{equation}
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}{\bf x}\equiv 0\bmod rs,\ 1\leq i\leq L_m(r),\ 1\leq j\leq 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),
\[
\{{\bf x} \bmod r: A_{IJ}{\bf x}\equiv 0\bmod {rs}\}=\{{\bf x}: B_I{\bf
x}\equiv 0\bmod r\}
\]
and
\[
\{{\bf x} \bmod s: A_{IJ}{\bf x}\equiv 0\bmod {rs}\}=\{{\bf x}: C_J{\bf
x}\equiv 0\bmod s\};
\]
similar equations hold for $A_{KL}$. Since the pairs $B_I, C_J$ and $B_K,
C_L$ are different, we have either
\[
\{{\bf x}: B_I{\bf x}\equiv 0\bmod r\} \neq \{{\bf x}: B_K{\bf x}\equiv
0\bmod r\}
\]
or
\[
\{{\bf x}: C_J{\bf x}\equiv 0\bmod s\} \neq \{{\bf x}: C_L{\bf x}\equiv
0\bmod 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 $A{\bf x}\equiv 0\bmod {rs}$
gives a unique pair of congruences (5), where the matrices $B$ and $C$ are
defined by (6).
\end{proof}
\section{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.
\begin{thm}
The numbers $L_2(q)$ and $L_3(q)$ are given by
\beq
L_2(q)=\sum_{k_1|q}\sum_{k_2|q}\gcd\left(k_1,\frac{q}{k_2}\right)
\end{equation}
and
\beq
L_3(q)=\sum_{k_1|q}\sum_{k_2|q}\sum_{k_3|q}\gcd\left(k_1,\frac{q}{k_3}\right)
\gcd\left(k_2,\frac{q}{k_3}\right)\gcd\left(k_1,\frac{q}{k_2}\right).
\end{equation}
\end{thm}
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 $\L$, we have a
basis-free representation for it as follows: The $x_1$ axis contains
infinitely many points of $\L$,
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 $\L$ 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 $\L$, then $k_2$ is a divisor of $q$. A line $x_2=c$
contains points of $\L$ if and only if has the form $x_2=t k_2$ for some
integer $t$. We say that $\L$ has {\it jump}
$k_2$ (in the $x_2$ direction). If we let $C_2(\L)$ denote the
2-dimensional
volume of a fundamental cell of $\L$, then we have
$C_2(\L)=k_1k_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 {\it shift} $s$, where $s$ is
an integer such that $0\leq s