\documentclass[11pt]{article}
\usepackage{geometry} % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper} % ... or a4paper or a5paper or ...
%\geometry{landscape} % Activate for for rotated page geometry
%\usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\title{Notes on Computing Local Densities}
\author{Jonathan Hanke}
\date{May 14, 2009} % Activate to display a given date or no date
\begin{document}
\maketitle
%\section{}
%\subsection{}
\newcommand{\ve}{\varepsilon}
\newcommand{\al}{\alpha}
\newcommand{\ra}{\rightarrow}
\newcommand{\0}{\vec 0}
\newcommand{\x}{\vec x}
\newcommand{\Z}{\Bbb Z}
\newcommand{\F}{\Bbb F}
\renewcommand{\S}{\Bbb S}
\newcommand{\Unit}{\text{Unit}}
\newcommand{\NonUnit}{\text{NonUnit}}
\newcommand{\Leg}[2]{\left(\frac{#1}{#2}\right)}
%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definiton}
\newtheorem{example}[thm]{Example}
\newtheorem{condition}[thm]{Condition}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Computing local densities for a representing a number}
\subsection{Introduction}
Given an integer-valued quadratic form $Q(\x)$ in $n$ variables and an integer $m$, our goal is to compute the local representation densities
$$
\beta_{Q, p}(m) := \lim_{\al \ra \infty}\frac{r_{Q, p^{\al}}(m)}{p^{\al(n-1)}}
$$
where $r_{Q, p^{k}}(m)$ is the number of solutions of $Q(\x) \equiv m \pmod{p^{k}}$. We do this by a series of reduction steps based on breaking the solution vectors $\x$ into various ``types'' and then counting solutions of some auxiliary quadratic equations $Q'(\x) \equiv m'$ either mod $p$ (when $p\neq 2$) or mod 8 (when $p=2$), possibly with additional congruence conditions on $\x \pmod p$.
\subsection{Local Normal Form over $\Z_{p}$}
By an invertible linear change of variables over $\Z_{p}$ we can always write $Q(\x)$ as a direct sum of quadratic forms with at most two variables (and one variable when $p>2$) which is referred to as a {\bf Jordan decomposition} of $Q$. (See cite{} for details.) Assuming $Q$ is in this form, we group these blocks/subforms by their norm ideal and write
$$Q(\x) = \bigoplus_{j\in \Z} Q_{j}(\x_{j})$$
where $Q_{j}$ is the direct sum of all such subforms of norm ideal $(p^{j})$. This decomposition naturally breaks the vector $\x$ as a tuple of vectors $\x = (\x_{j})_{j\in \Z}$
%, which we also regard this as a single vector by concatenating all of these vectors together (by using the standard ordering).
%We will refer to t
%Locally (i.e. over $\Z_{p}$) we can assume that $Q = \oplus_{j\in \Z} Q_{j}$ is in (some fixed) Jordan block form, and hence that the solution vectors $\x$ can be written as a tuple of vectors $\x = (\x_{j})_{j\in \{1, \dots, m\}}$. We may also regard this as a single vector by concatenating all of these vectors together (by using the standard ordering).
Note that our choice of indices $j$ index the norm ideals, and not the scale ideals of the individual blocks, which is slightly non-standard indexing notation. These agree when $p>2$, but not in general for $p>2$. However, the choice of indexing by norm is more natural in our context since if $Q$ is integer-valued then we can always take $j\geq 0$ (i.e. $\dim(Q_{j}) = 0$ if $j<0$).
In implementing these algorithms it is more convenient to refer to {\it variables} $x_{i}$ than Jordan component vectors $\x_{j}$ containing those variables (though again they agree when $p=2$), which we refer to by the variable index $i$ which satisfies $0\leq i \leq n-1$ where $n=\dim(Q)$. Any conditions we specify on a vector $\x$ will depend only on the components $\x_{j}$, so for each $2\times2$ block we must refer to either both variables $x_{i}$ or to neither of them. This applies in particular to the sets $\S$ of indices $i$ described below.
{\bf Important Note:} All local density reduction algorithms require that $Q$ is written in block diagonal form (with minimal block sizes as described in \cite[Lemma 2.1, p355]{Ha}, though the blocks do not need to be strictly ordered by norm or scale.
\subsection{Notation and Conventions}
\subsubsection{Projections of vectors and forms:}
For any subset $\S\subseteq \{0, \dots, n-1\}$ we denote by $\x_{\S}$ the vector $\x_{\S} = (x_{i})_{i\in \S}$ given by restricting $\x$ to the components $x_{i}$ indexed by $\S$ with the standard increasing ordering on indices. We similarly denote $Q_{\S}$ to be direct sum of the subforms using the variables $x_{i}$ for $i\in\S$.
%
(Note that this is a slightly different convention from \cite[p354, \P4]{Ha} which refers to the vectors $\x_{\S} = (\x_{j})_{j\in \S}$ where the index refers to a component of a partition of $\{1, \dots, n\}$, whereas here the indexing set $\S$ runs over indices $i \in \{0, \dots, n-1\}$ and not over partition subsets of $\{1, \dots, n\}$.)
We also often write $\x_{\S} \equiv\0_{\S}$ (or $\x_{\S} \not\equiv\0_{\S}$) in the slightly abbreviated form $\x_{\S} \equiv\0$ (or $\x_{\S} \not\equiv\0$) since it is clear from the context that $\0$ here means $\0_{\S}$. This convention is consistent with \cite[]{Ha}.
\subsubsection{Conventions for $\S = \emptyset$:}
We also have the standard convention that when $\S = \emptyset$ that $\x_{\S} \equiv\0_{\S}$ is trivially true, and so its negation $\x_{\S} \not\equiv\0_{\S}$ is always false unless $\S \neq\emptyset$, which is mentioned explicitly in \cite[p357, \P1]{Ha}. We also adopt the convention that when $\S = \emptyset$ we define $r_{Q_{\S}, p^{k}}(m) = 1$.
\subsubsection{Standard Notation}
We denote by $\S, \S_{0}, \S_{1}, \S_{2+}, \Unit, \NonUnit, Is8, Not8$... sets of indices of variables $x_{i}$ as described above, which respect the (necessarily given) block decomposition of $Q$ into subforms of dimension $\leq 2$.
We let $r_{Q, p^{k}}(m), r^{Zero, Z\equiv \0}_{Q, p^{k}}(m), \text{ and } r^{Zero, Z\equiv \0, NZ\not\equiv \0}_{Q, p^{k}}(m)$ denote the number of solutions of $Q(\x) \equiv m \pmod{p^{k}}$ which respectively satisfy the additional congruence conditions: None, $\x_{Z} \equiv \0 \pmod p$, and both $\x_{Z} \equiv \0 \pmod p$ and $\x_{NZ} \not\equiv \0 \pmod p$. Since taking $Z = \emptyset$ is a vacuous condition we see that $r^{Z\equiv \0}_{Q, p^{k}}(m)$ can also express $r_{Q, p^{k}}(m)$, however there are no generically vacuous conditions for $NZ$ so this condition must be explicitly included or not in our formulas. Also while multiple zero congruence conditions $\x_{Z1} \equiv \0$ and $\x_{Z2} \equiv \0$ can be combined as $\x_{Z1\cup Z2}\equiv \0$ in a single condition, the non-zero congruence conditions cannot be combined. Our notation (and implementation) allows for at most one such non-zero condition, which is either passed in as the class ``None'' or as a vector of indices for $NZ$.
\subsection{Congruence Conditions}
\label{Subsec:Congruence}
It will be useful to consider representation densities for vectors subject to certain congruence conditions (mod $p$). These will always be relative to a fixed block diagonal decomposition of $Q$ as described above, and are not well-defined without this choice.
%
These either take the form $\x_{Z} \equiv \0_{Z} \pmod p$ or $\x_{NZ} \not\equiv \0_{NZ} \pmod p$ or both, for some sets of indices $Z$ and $NZ \subseteq\{0, \dots, n-1\}$. (It happens that for our purposes we will not need to have more than one non-zero congruence condition, and any number of zero congruence conditions are equivalent to a single larger one.)
There are two main observations for computing the densities subject to the conditions $\x_{Z} \equiv \0$ and $\x_{NZ} \not\equiv \0$:
\begin{enumerate}
%\item $\beta^{\x_{Z}\equiv \0, \x_{NZ}\not\equiv \0} = \beta^{\x_{Z}\equiv \0} - \beta^{\x_{Z \cup NZ} \equiv \0}$
\item $({\x_{Z}\equiv \0, \x_{NZ}\not\equiv \0}) = ({\x_{Z}\equiv \0}) - ({\x_{Z \cup NZ} \equiv \0})$
\item The above formula counts no solutions when $NZ \subseteq Z$, so when this happens we declare there are no solutions.
\end{enumerate}
\subsection{Counting Solutions in $\F_{p}$ for primes $p\neq 2$}
Assuming the Jordan block form above, we are interested in computing the number of solutions $r_{Q, p}(m)$ of $Q(\x) = m$ in $\F_{p}$. If we denote the $j=0$ (unit scale) indexing set by $\Unit$, and the other (non-unit scale) indices $j>0$ by $\NonUnit$, then reducing the Jordan form mod $p$ gives the formulas
%\begin{enumerate}
%\item[(a)]
$$r_{Q, p}(m) = r_{Q_{\Unit}, p}(m) \cdot p^{|\NonUnit|}$$
%\item[(b)]
\begin{equation}
\label{eq:zero-only}
r^{Z\equiv \0}_{Q, p}(m) = r_{Q_{\Unit - (\Unit\cap Z)}, p}(m) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|}
\end{equation}
%\end{enumerate}
since the components $\x_{\NonUnit}$ can be freely chosen.
%
Notice that this formula also holds with the convention that when $\S = \emptyset$ we set $r_{Q_{\S}}(m) = 1$.
%
By combining this with the method of dealing with non-zero congruence conditions described in subsection \ref{Subsec:Congruence}, we obtain the final formula for both zero and non-zero congruence conditions as:
\begin{align}
\label{eq:zero-nonzero}
r^{Z\equiv \0, NZ\not\equiv \0}_{Q, p}(m)
&= r_{Q_{\Unit - (\Unit\cap Z)}, p}(m) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|} \\
&- r_{Q_{\Unit - (\Unit\cap (Z\cup NZ))}, p}(m) \cdot p^{|\NonUnit| - |\NonUnit\cap (Z\cup NZ)|}
\end{align}
To evaluate $r_{Q, p}(m)$ when $Q = Q_{\Unit}$ we have the following formulas from the theory of Gauss sums for a non-degenerate quadratic form $Q$ of Gram determinant $D$ (hence $D$ is non-zero) over $\F_{p}$:
$$
r_{Q, p}(m) =
\begin{cases}
p^{n-1} & \text{ if $n$ is odd and $m \equiv 0 \pmod p$} \\
p^{n-1} + p^{\frac{n-1}{2}}\Leg{(-1)^\frac{n-1}{2}D\,m}{p} & \text{ if $n$ is odd and $m \not\equiv 0 \pmod p$} \\
p^{n-1} + p^{\frac{n-2}{2}}(p-1)\Leg{(-1)^\frac{n}{2}D}{p} & \text{ if $n$ is even and $m \equiv 0 \pmod p$} \\
p^{n-1} - p^{\frac{n}{2}}\Leg{(-1)^\frac{n}{2}D}{p} & \text{ if $n$ is even and $m \not\equiv 0 \pmod p$} \\
\end{cases}
$$
See \cite[]{BoSha} or \cite[]{Ca} for the general formulas, and \cite[Table 1, p363]{Ha} for when $n\leq 4$.
\subsection{Counting Good-type Solutions for $p\neq 2$}
\begin{defn}
We say that a solution vector $\x$ of $Q(\x) \equiv m \pmod{p^{k}}$ is of {\bf Good-type} solutions (for odd primes $p$) if $a_{ii}x_{i} \neq 0$ for some index $i$.
\end{defn}
%
We define indexing sets $\Unit$ and $\NonUnit$ to give the variable indices where $a_{ii}$ is (resp. is not) a unit mod $p$. In terms of the Jordan decomposition, the Good-type condition can be stated equivalently as saying that $\x_{\Unit} \not\equiv \0$.
\medskip
If $m \not\equiv 0 \pmod p$ then $r^{Good}_{Q, p}(m) = r_{Q, p}(m)$ since some component of $\x_{\Unit}$ must be non-zero.
The same formula also holds if we add any additional congruence conditions to both sides.
If $m\equiv 0$ then we can add the Good-type requirement to both sides of equations (\ref{eq:zero-only}) or (\ref{eq:zero-nonzero}) to obtain a formula. Since the ``type'' condition on a solution vector $\x$ is independent of any additional congruence conditions imposed on it, we are reduced to equation (\ref{eq:zero-nonzero}) where both terms on the RHS count only Good-type solutions. This happens for each term individually when $\x_{\Unit} \neq \0$ for each solution vector, so when $m=0$ we need to subtract off the zero vector, giving either
$$
r^{Good, Z\equiv \0}_{Q, p}(0)
= (r_{Q_{\Unit - (\Unit\cap Z)}, p}(0) - 1) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|} \\
$$
or
\begin{align*}
r^{Good, Z\equiv \0, NZ\not\equiv \0}_{Q, p}(0)
&= (r_{Q_{\Unit - (\Unit\cap Z)}, p}(0) - 1) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|} \\
&- (r_{Q_{\Unit - (\Unit\cap (Z\cup NZ))}, p}(0) - 1) \cdot p^{|\NonUnit| - |\NonUnit\cap (Z\cup NZ)|}.
\end{align*}
\subsection{Counting Good-type Solutions for $p=2$}
When $p=2$ to compute local densities by lifting Good-type solutions we must count solutions mod 8 (not just mod 2). Since $\Z/8\Z$ is not field we do not have a Gauss sum which quickly computes the number of solutions, and we resort to just counting solutions naively (i.e. one at at time) according to their solution type and auxiliary congruence conditions. ({\bf Note:} This can possibly be sped up by some fixed linear factor by caching various representation numbers of small dimensional forms mod 8, but this is not done currently.)
The only simplification we make is to simplify the dependence of the answer on the Jordan blocks whose norm is divisible by 8. If we denote by $Not8$ and $Is8$ the sets of indices of Jordan blocks whose norms respectively aren't and are divisible by 8, then we have the two formulas:
$$
r^{Good, Z\equiv \0}_{Q, 8}(m)
= r^{Good, Z\cap Not8 \equiv 0}_{Q_{Not8}, 8}(m)
\cdot 4^{|Is8 \cap Z|}
\cdot 8^{|Is8| - |Is8\cap Z|} \\
$$
and
$$
r^{Good, Z\equiv \0, NZ\not\equiv \0}_{Q, 8}(m)
= r^{Good, Z\equiv \0}_{Q, 8}(m) - r^{Good, Z\cup NZ\equiv \0}_{Q, 8}(m)
$$
where the last formula can be worked out explicitly in terms of the first formula.
\subsection{Counting Zero-type Solutions}
\begin{defn}
A solution $\x$ of $Q(\x) \equiv m \pmod{p^{k}}$ is said to be of {\bf Zero-type} if $\x \equiv \0 \pmod p$.
\end{defn}
%
Note that a necessary condition for such a solution to exist is that $p^{2}\mid m$, since $\x = p\x' \implies m = Q(\x) = Q(p\x') = p^{2}Q(\x')$.
%
From the definition, we see that the extra congruence conditions for Zero-type solutions are easily dealt with by the formulas
$$
r^{Zero, Z\equiv \0}_{Q, p^{k}}(m) = r^{Zero}_{Q, p^{k}}(m)
\qquad\text{and}\qquad
r^{Zero, Z\equiv \0, NZ\not\equiv \0}_{Q, p^{k}}(m) = 0.
$$
From \cite[p359]{Ha} we know that there is a surjective map
$$
\pi_{Z}: R_{Q, p^{k}}^{Zero}(m) \ra R_{Q, p^{k-2}}(m/p^{2})
$$
with multiplicity $p^{n}$, and taking $k>>1$ gives the reduction formula
$$
\beta^{Zero}_{Q,p}(m)
= \frac{r_{Q, p^{k}}^{Zero}(m)}{p^{(n-1)k}}
= \frac{r_{Q, p^{k-2}}(m/p^{2})\cdot p^{n}}{p^{(n-1)k}}
= \frac{r_{Q, p^{k-2}}(m/p^{2})\cdot p^{n-2(n-1)}}{p^{(n-1)(k-2)}}
= \tfrac{1}{p^{n-2}} \beta_{Q,p}(m/p^{2}).
$$
%
Thus we can reduce our computation of Zero-type solutions representing $m$ to arbitrary solutions representing $m/p^{2}$.
\subsection{Counting Bad-type I Solutions}
We define the indexing sets
\begin{align*}
\S_{0} &= \{ i \mid 0\leq i < n, x_{i} \text{ is a variable in } \x_{0} \,\text{(or in }Q_{0}) \} \\
\S_{1} &= \{ i \mid 0\leq i < n, x_{i} \text{ is a variable in } \x_{1} \,\text{(or in }Q_{1}) \} \\
\S_{2+} &= \{ i \mid 0\leq i < n, x_{i} \text{ is a variable in } \x_{j} \,\text{(or in }Q_{j}) \text{ for some $j\geq 2$} \}
\end{align*}
of sizes $s_{0}, s_{1}, \text{ and } s_{2+}$ respectively. Also let $\S_{\geq 1} := \S_{1} \cup \S_{2+}$.
\begin{defn}
In terms of these sets, we can define the Bad-type I solutions to be those not of Good-type or Zero-type
for which $\x_{\S_1} \not\equiv \0 \pmod p$.
\end{defn}
A necessary condition for these to exist is that $p\mid m$ and $\x_{\S_{1}}\not\equiv \0 \pmod p$.
%
%
From \cite[p360]{Ha} we know that there is a surjective map
$$
\pi_{B'}: R_{Q, p^{k}}^{Bad I}(m) \ra R_{Q', p^{k-1}}^{Good}(m/p)
$$
for some auxiliary form $Q'$ and this map has multiplicity $p^{s_{1} + s_{2+}}$.
Under $\pi_{B'}$, congruence conditions $Z\equiv \0$ restrict to $Z\cap(\S_{1}\cup\S_{2+}) \equiv \0$ and $NZ\not\equiv \0$ restrict to $NZ\cap(\S_{1}\cup\S_{2+}) \not\equiv \0$ (and this also holds true when the index intersection is $\emptyset$). Therefore we have that
$$
r_{Q, p^{k}}^{Bad I, Z\equiv \0, NZ\not\equiv \0}(m)
= p^{s_{1} + s_{2+}} \cdot r_{Q', p^{k-1}}^{Good, Z\cap\S_{\geq 1}\equiv \0, NZ\cap\S_{\geq 1}\not\equiv \0}(m/p)
$$
and similarly with no non-zero congruence condition on both sides.
%
By taking $k>>1$ we obtain the local density reduction formula
\begin{align*}
\beta^{Bad I, C}_{Q,p}(m)
&= \frac{r_{Q, p^{k}}^{Bad I, C}(m)}{p^{(n-1)k}}
= \frac{p^{s_{1} + s_{2+}} \cdot r_{Q', p^{k-1}}^{Good, C\cap\S_{\geq 1}}(m/p)}{p^{(n-1)k}} \\
&= \frac{p^{s_{1} + s_{2+} - (n-1)} \cdot r_{Q', p^{k-1}}^{Good, C\cap\S_{\geq 1}}(m/p)}{p^{(n-1)(k-1)}}
%= \frac{r_{Q, p^{k-2}}(m/p^{2})\cdot p^{n-2(n-1)}}{p^{(n-1)(k-2)}}
%= \tfrac{1}{p^{s_{0}-1}} \beta^{Good}_{Q,p}(m/p).
= p^{1-s_{0}} \cdot \beta^{Good, C\cap\S_{\geq 1}}_{Q,p}(m/p).
\end{align*}
\begin{rem}[\bf Notational Note]
In the above formula we are using the shorthand ``$C\cap\S$'' for ``$Z\cap\S \equiv \0, NZ\cap\S \not\equiv \0$'', and also the indexing set $\S_{\geq1}$ is defined relative to the original form $Q$ (not the new form $Q'$).
\end{rem}
\begin{rem}[\bf Ordering Warning]
The Bad-type I reduction procedure does not preserve the ``increasing valuation'' ordering of the block diagonal local normal form! This is important to notice because it means that we should not depend on this property of our block diagonal quadratic form which is then passed as input to other local density congruence routines!
\end{rem}
\subsection{Counting Bad-type II Solutions}
Another definition of the Bad-type II solutions are is that they are Bad-type solutions where $\x_{\S_1} \equiv \0$. For there to be solutions, we must have that $\S_{2+} \neq \emptyset$ (or more generally that $\x_{\S_{2+}} \not\equiv \0$) and that $p^2 \mid m$.
We then obtain a reduction formula which returns a reduction formula to solutions which satisfy the congruence conditions $Z\cap \S_{2+}\equiv \0$, $NZ\cap \S_{2+}\not\equiv \0$, and also $\x_{\S_{2+}} \not\equiv \0$. The presence of {\it two} non-zero congruence conditions does not fit into our current implementation framework (which accommodates at most one non-zero congruence condition), though this can be dealt with by
$$
(C\cap \S_{2+}, \x_{\S_{2+}} \not\equiv \0)
\quad = \quad
(Z\cap \S_{2+}\equiv \0, NZ\cap \S_{2+}\not\equiv \0) - (\S_{2+} \cup (Z\cap \S_{2+})\equiv \0, NZ\cap \S_{2+}\not\equiv \0).
$$
Here the second zero congruence can be simplified since $\S_{2+} \cup (Z\cap \S_{2+})$ is just $\S_{2+}$.
%\subsection{Good-type Implementation}
%\subsection{EXTRA STUFF}
\bibliography{mybib}{}
\bibliographystyle{plain}
\end{document}