Ticket #6037: Local Densities Writeup.tex

File Local Densities Writeup.tex, 18.2 KB (added by jonhanke, 12 years ago)

LaTeX file used to create the PDF writeup

Line 
1\documentclass[11pt]{article}
2\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
3\geometry{letterpaper}                   % ... or a4paper or a5paper or ...
4%\geometry{landscape}                % Activate for for rotated page geometry
5%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
6\usepackage{graphicx}
7\usepackage{amssymb}
8\usepackage{epstopdf}
9\usepackage{amsfonts}
10\usepackage{amsmath}
11\usepackage{amsthm}
12
13\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
14
15\title{Notes on Computing Local Densities}
16\author{Jonathan Hanke}
17\date{May 14, 2009}                                           % Activate to display a given date or no date
18
19\begin{document}
20\maketitle
21%\section{}
22%\subsection{}
23
24\newcommand{\ve}{\varepsilon}
25\newcommand{\al}{\alpha}
26\newcommand{\ra}{\rightarrow}
27\newcommand{\0}{\vec 0}
28\newcommand{\x}{\vec x}
29\newcommand{\Z}{\Bbb Z}
30\newcommand{\F}{\Bbb F}
31\renewcommand{\S}{\Bbb S}
32\newcommand{\Unit}{\text{Unit}}
33\newcommand{\NonUnit}{\text{NonUnit}}
34
35\newcommand{\Leg}[2]{\left(\frac{#1}{#2}\right)}
36
37
38%%%%%%%%%%%%%%%%%%%%%%%
39
40\newtheorem{thm}{Theorem}[section]
41\newtheorem{cor}[thm]{Corollary}
42\newtheorem{lem}[thm]{Lemma}
43\newtheorem{conj}[thm]{Conjecture}
44
45
46\newtheorem{defn}[thm]{Definiton}
47
48\newtheorem{example}[thm]{Example}
49
50\newtheorem{condition}[thm]{Condition}
51
52
53
54\theoremstyle{remark}
55\newtheorem{rem}[thm]{Remark}
56
57
58%%%%%%%%%%%%%%%%%%%%%%%%%
59
60
61
62\section{Computing local densities for a representing a number}
63
64\subsection{Introduction}
65Given an integer-valued quadratic form $Q(\x)$ in $n$ variables and an integer $m$, our goal is to compute the local representation densities
66$$
67\beta_{Q, p}(m) := \lim_{\al \ra \infty}\frac{r_{Q, p^{\al}}(m)}{p^{\al(n-1)}}
68$$
69where $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$.
70
71
72
73\subsection{Local Normal Form over $\Z_{p}$}
74By 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
75$$Q(\x) = \bigoplus_{j\in \Z}  Q_{j}(\x_{j})$$ 
76where $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}$
77
78%, which we also regard this as a single vector by concatenating all of these vectors together (by using the standard ordering).
79
80%We will refer to t
81
82%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).
83
84Note 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$).
85
86
87In 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.
88
89{\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.
90
91
92\subsection{Notation and Conventions}
93
94\subsubsection{Projections of vectors and forms:}
95For 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$.
96%
97(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\}$.)
98
99
100We 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}.
101
102
103\subsubsection{Conventions for $\S = \emptyset$:}
104We 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$.
105
106
107\subsubsection{Standard Notation}
108We 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$.
109
110We 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$.
111
112
113
114
115
116
117
118\subsection{Congruence Conditions}
119\label{Subsec:Congruence}
120It 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.
121%
122These 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.)
123
124There are two main observations for computing the densities subject to the conditions $\x_{Z} \equiv \0$ and $\x_{NZ} \not\equiv \0$:
125\begin{enumerate}
126%\item $\beta^{\x_{Z}\equiv \0, \x_{NZ}\not\equiv \0} = \beta^{\x_{Z}\equiv \0} - \beta^{\x_{Z \cup NZ} \equiv \0}$
127\item $({\x_{Z}\equiv \0, \x_{NZ}\not\equiv \0}) = ({\x_{Z}\equiv \0}) - ({\x_{Z \cup NZ} \equiv \0})$ 
128\item The above formula counts no solutions when $NZ \subseteq Z$, so when this happens we declare there are no solutions.
129\end{enumerate}
130
131
132
133
134
135
136
137
138\subsection{Counting Solutions in $\F_{p}$ for primes $p\neq 2$}
139
140Assuming 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
141%\begin{enumerate}
142%\item[(a)]
143$$r_{Q, p}(m) = r_{Q_{\Unit}, p}(m) \cdot p^{|\NonUnit|}$$
144%\item[(b)]
145\begin{equation}
146\label{eq:zero-only} 
147r^{Z\equiv \0}_{Q, p}(m) = r_{Q_{\Unit - (\Unit\cap Z)}, p}(m) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|}
148\end{equation}
149%\end{enumerate}
150since the components $\x_{\NonUnit}$ can be freely chosen.
151%
152Notice that this formula also holds with the convention that when $\S = \emptyset$ we  set $r_{Q_{\S}}(m) = 1$.
153%
154By 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:
155\begin{align}
156\label{eq:zero-nonzero}
157r^{Z\equiv \0, NZ\not\equiv \0}_{Q, p}(m)
158&= r_{Q_{\Unit - (\Unit\cap Z)}, p}(m) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|} \\
159&- r_{Q_{\Unit - (\Unit\cap (Z\cup NZ))}, p}(m) \cdot p^{|\NonUnit| - |\NonUnit\cap (Z\cup NZ)|}
160\end{align}
161
162To 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}$:
163$$
164r_{Q, p}(m) = 
165\begin{cases}
166p^{n-1} & \text{ if $n$ is odd and $m \equiv 0 \pmod p$} \\
167p^{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$} \\
168p^{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$} \\
169p^{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$} \\
170\end{cases}
171$$
172See \cite[]{BoSha} or \cite[]{Ca} for the general formulas, and \cite[Table 1, p363]{Ha} for when $n\leq 4$.
173
174
175
176
177
178
179
180\subsection{Counting Good-type Solutions for $p\neq 2$}
181\begin{defn}
182We 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$.
183\end{defn}
184%
185We 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$.
186
187\medskip
188
189
190If $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.
191The same formula also holds if we add any additional congruence conditions to both sides. 
192
193
194
195If $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
196$$
197r^{Good, Z\equiv \0}_{Q, p}(0) 
198= (r_{Q_{\Unit - (\Unit\cap Z)}, p}(0) - 1) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|} \\
199$$
200or
201\begin{align*}
202r^{Good, Z\equiv \0, NZ\not\equiv \0}_{Q, p}(0)
203&= (r_{Q_{\Unit - (\Unit\cap Z)}, p}(0) - 1) \cdot p^{|\NonUnit| - |\NonUnit\cap Z|} \\
204&- (r_{Q_{\Unit - (\Unit\cap (Z\cup NZ))}, p}(0) - 1) \cdot p^{|\NonUnit| - |\NonUnit\cap (Z\cup NZ)|}.
205\end{align*}
206
207
208\subsection{Counting Good-type Solutions for $p=2$}
209
210When $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.)
211
212
213
214The 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:
215$$
216r^{Good, Z\equiv \0}_{Q, 8}(m) 
217= r^{Good, Z\cap Not8 \equiv 0}_{Q_{Not8}, 8}(m) 
218\cdot 4^{|Is8 \cap Z|}
219\cdot 8^{|Is8| - |Is8\cap Z|} \\
220$$
221and
222$$
223r^{Good, Z\equiv \0, NZ\not\equiv \0}_{Q, 8}(m) 
224=  r^{Good, Z\equiv \0}_{Q, 8}(m) - r^{Good, Z\cup NZ\equiv \0}_{Q, 8}(m) 
225$$
226where the last formula can be worked out explicitly in terms of the first formula.
227
228
229
230
231\subsection{Counting Zero-type Solutions}
232\begin{defn}
233A solution $\x$ of $Q(\x) \equiv m \pmod{p^{k}}$ is said to be of {\bf Zero-type} if $\x \equiv \0 \pmod p$.
234\end{defn}
235%
236Note 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')$.
237%
238From the definition, we see that the extra congruence conditions for Zero-type solutions are easily dealt with by the formulas
239$$
240r^{Zero, Z\equiv \0}_{Q, p^{k}}(m) = r^{Zero}_{Q, p^{k}}(m)
241\qquad\text{and}\qquad
242r^{Zero, Z\equiv \0, NZ\not\equiv \0}_{Q, p^{k}}(m) = 0.
243$$
244
245
246
247
248From \cite[p359]{Ha} we know that there is a surjective map
249$$
250\pi_{Z}: R_{Q, p^{k}}^{Zero}(m) \ra R_{Q, p^{k-2}}(m/p^{2})
251$$
252with multiplicity $p^{n}$, and taking $k>>1$ gives the reduction formula
253$$
254\beta^{Zero}_{Q,p}(m) 
255= \frac{r_{Q, p^{k}}^{Zero}(m)}{p^{(n-1)k}}
256= \frac{r_{Q, p^{k-2}}(m/p^{2})\cdot p^{n}}{p^{(n-1)k}}
257= \frac{r_{Q, p^{k-2}}(m/p^{2})\cdot p^{n-2(n-1)}}{p^{(n-1)(k-2)}}
258= \tfrac{1}{p^{n-2}} \beta_{Q,p}(m/p^{2}).
259$$
260%
261Thus we can reduce our computation of Zero-type solutions representing $m$ to arbitrary solutions representing $m/p^{2}$
262
263
264
265
266
267
268
269
270\subsection{Counting Bad-type I Solutions}
271We define the indexing sets
272\begin{align*}
273\S_{0} &= \{ i \mid 0\leq i < n, x_{i} \text{ is a variable in } \x_{0} \,\text{(or in }Q_{0}) \} \\
274\S_{1} &= \{ i \mid 0\leq i < n, x_{i} \text{ is a variable in } \x_{1} \,\text{(or in }Q_{1}) \} \\
275\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$} \} 
276\end{align*}
277of sizes $s_{0}, s_{1}, \text{ and } s_{2+}$ respectively.  Also let $\S_{\geq 1} := \S_{1} \cup \S_{2+}$.
278
279\begin{defn}
280In terms of these sets, we can define the Bad-type I solutions to be those not of Good-type or Zero-type
281for which $\x_{\S_1} \not\equiv \0 \pmod p$.
282\end{defn}
283
284
285A necessary condition for these to exist is that $p\mid m$ and $\x_{\S_{1}}\not\equiv \0 \pmod p$.
286%
287%
288From \cite[p360]{Ha} we know that there is a surjective map
289$$
290\pi_{B'}: R_{Q, p^{k}}^{Bad I}(m) \ra R_{Q', p^{k-1}}^{Good}(m/p)
291$$
292for some auxiliary form $Q'$ and this map has multiplicity $p^{s_{1} + s_{2+}}$.
293
294
295Under $\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
296$$
297r_{Q, p^{k}}^{Bad I, Z\equiv \0, NZ\not\equiv \0}(m) 
298= 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)
299$$
300and similarly with no non-zero congruence condition on both sides.
301%
302By taking $k>>1$ we obtain the local density reduction formula
303\begin{align*}
304\beta^{Bad I, C}_{Q,p}(m)
305&= \frac{r_{Q, p^{k}}^{Bad I, C}(m)}{p^{(n-1)k}} 
306= \frac{p^{s_{1} + s_{2+}} \cdot  r_{Q', p^{k-1}}^{Good, C\cap\S_{\geq 1}}(m/p)}{p^{(n-1)k}} \\
307&= \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)}}
308%= \frac{r_{Q, p^{k-2}}(m/p^{2})\cdot p^{n-2(n-1)}}{p^{(n-1)(k-2)}}
309%= \tfrac{1}{p^{s_{0}-1}} \beta^{Good}_{Q,p}(m/p).
310= p^{1-s_{0}} \cdot \beta^{Good, C\cap\S_{\geq 1}}_{Q,p}(m/p).
311\end{align*}
312
313\begin{rem}[\bf Notational Note]
314In 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'$).
315\end{rem}
316
317
318\begin{rem}[\bf Ordering Warning]
319The 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!
320\end{rem}
321
322
323
324
325
326
327\subsection{Counting Bad-type II Solutions}
328
329Another 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$.
330
331
332We 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
333$$
334(C\cap \S_{2+}, \x_{\S_{2+}} \not\equiv \0)
335\quad = \quad
336(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).
337$$
338Here the second zero congruence can be simplified since $\S_{2+} \cup (Z\cap \S_{2+})$ is just $\S_{2+}$.
339
340
341
342
343
344
345%\subsection{Good-type Implementation}
346
347
348%\subsection{EXTRA STUFF}
349
350
351\bibliography{mybib}{}
352\bibliographystyle{plain}
353
354
355
356\end{document}