# Solution count of quadratic form congruence over $\Bbb Z / 8 \Bbb Z$

Let $(L,q)$ be an even Lorentzian lattice of signature $(1,l-1)$, i.e., $q(\lambda) \in \Bbb Z$ for all $\lambda \in L$ and the (non-degenerate) quadratic form $q$ is of type $(1,l-1)$ (the type/signature shouldn't matter here, I think...). I am interested in counting the number of solutions $x \in L/8L$ modulo $a \in (\Bbb Z / 8 \Bbb Z)^*$, i.e., what is $$N(a) := \# \{ x \in L/8L : q(x) \equiv a \pmod 8 \}$$

We could rewrite this as $N(a) = \# \{ x \in \Bbb Z / 8 \Bbb Z : q(x) \equiv a \pmod 8 \}$ again using $q(x)$ for the quadratic form $\frac 1 2 x^t S x$, $S$ the Gram matrix, for vectors $x \in \Bbb Z / 8 \Bbb Z$.

A trivial bound would be $8^l$ assuming that all vectors are solutions. One can verify, that all even vectors are no solutions, i.e., vectors $x$ for which there is a vector $x' \in (\Bbb Z / 8 \Bbb Z)^l$ such that $x = 2 x'$. Because then $q(x) = 4 q(x') \in \{0,4\}$ but we assumed that $a \in (\Bbb Z / 8 \Bbb Z)^*$ so $x$ cannot be a solution. This gives a slightly better bound of $8^l - 4^l$. But I was hoping for a bound like $4 \cdot 8^{l-1} = 8^l /2$, i.e., that only at most half of the vectors are solutions. My intuition tells me that this should be possible, assuming that $a$ is a unit.

-

I solved it the following way. I also put this solution in my thesis, so it ought to be correct :) I start by stating a Lemma from the theory of $p$-adic classification of quadratic forms.

$\newcommand{\ZZ}{\mathbb{Z}}$ Lemma: Every integral lattice is $p$-adically equivalent to a lattice with diagonal Gram matrix, if $p \neq 2$. For $p=2$ there is a $2$-adic equivalence to a lattice whose Gram matrix has either $1 \times 1$-blocks of the form $(2^{l}\varepsilon)$, $l \geq 0$, $\varepsilon$ a unit in $\ZZ/ 8\ZZ$, or $2 \times 2$-blocks of the form $$2^{l} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \quad\text{or}\quad 2^{l} \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix},\, l \geq 0 %\label{eqn:2-adicMatrices} \tag{M}$$ on its diagonal. We get the (finite) $p$-adic orthogonal decomposition $$L \sim_{p} p^{0} L_{0} \perp p^{1} L_{1} \perp \ldots % \tag{2}$$ into lattices $L_{i}$ with quadratic forms whose Gram determinants are not divisible by $p$.

For references, see [Co-Cl] (Thm. 2, p. 369), [Cas08] (Lem. 4.1, p. 117) and [Kit93] (pp. 76)

Proof of assertion from question: We use the theory of $p$-adic classification from the previous Lemma for $p=2$. Let $$L \sim_{2} 2^{0} L_{0} \perp 2^{1} L_{1} \perp \ldots$$ be the $2$-adic decomposition of $L$. If $L_{0}$ is $0$, then the congruence $$\tag{C} q(x) \equiv a \pmod 8$$ over $\ZZ_{2} / 2^{3} \ZZ_{2} = \ZZ/ 2^{3} \ZZ$ has no solutions as $q$ would only take even values, but $a \in (\ZZ / 8 ZZ)^{*}$. So suppose $L_{0}$ is non-trivial. If its Gram matrix contains a $1 \times 1$ block $(b)$, $b \in (\ZZ/ 8\ZZ)^{*}$ on its diagonal, let it w.l.o.g. be the first entry on the diagonal. Fixing the last $l-1$ coordinates of a vector $x \in (\ZZ/ 8\ZZ)^{l}$, the congruence (C) becomes the quadratic congruence (after multiplying with $b^{-1}$) $$x_{1} \equiv c \pmod 8$$ for some unknown constant $c(=b^{-1}(a-q((0,x_{2},\ldots,x_{l})))$. In the worst case that $c=1$, this congruence has the four units of $\ZZ/ 8\ZZ$ as solutions. This would yield the upper bound $8^{l-1}\cdot 4 = 8^{l}/2$ as stated in the question.

In the other two cases, that the Gram matrix of $L_{0}$ only contains the matrices (M) on its diagonal, there are even less solutions. This can be shown by some tedious calculations by cases. Fix the last $l-2$ coordinates of $x \in (\ZZ/ 8\ZZ)^{l}$. The congruence becomes now one of the two cases $$\begin{eqnarray} 2 x_{1} x_{2} & \equiv & c \pmod 8, \tag{M1} \\ 2 ({x_{1}}^{2} + x_{1} x_{2} + {x_{2}}^{2}) & \equiv & c \pmod 8 \tag{M2} \end{eqnarray}$$ again for some unknown constant $c$. Instead of doing the tedious calculations, one can also just issue the script

for M in [[0,1,0],[1,1,1]]:

in Sage (e.g, go to sagenb.org if you don't have a local installation), to find that the congruence (M1) has at most $20 < 8^{2}/2$ solutions and the second congruence (M2) has at most $12 < 8^{2}/2$ solutions.
By the way, I have a meta question at this point: I couldn't use \label and \ref commands, no matter what I tried. Is this disabled on math.stackexchange? – sebastian Dec 5 '12 at 19:20