Squares and Cubes Modulo $n$
Steven Finch and Pascal Sebah
We study the asymptotics of the average number of squares (or quadratic residues)\ in $\mathbb{Z}_{n}$ and $\mathbb{Z}_{n}^{*}$. Similar analyses are performed for cubes, square roots of $0$ and $1$, and cube roots of $0$ and $1$.
sqcb.tex
%% This document created by Scientific Word (R) Version 2.0
%% Starting shell: mathart1

\documentclass[12pt,thmsa]{article}%
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{sw20bams}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{graphicx}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{TCIstyle=Article/art1.lat,bams,mathart1}
%TCIDATA{LastRevised=Friday, March 25, 2016 11:02:13}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\begin{document}

\author{Steven Finch and Pascal Sebah}
\title{Squares and Cubes Modulo $n$}
\date{March 25, 2016}
\maketitle

\begin{abstract}
We study the asymptotics of the average number of squares (or quadratic
residues)\ in $\mathbb{Z}_{n}$ and $\mathbb{Z}_{n}^{*}$. Similar analyses are
performed for cubes, square roots of $0$ and $1$, and cube roots of $0$ and
$1$.

\end{abstract}

\footnotetext{Copyright \copyright \ 2006 by Steven R. Finch. All rights
reserved.}Let $\mathbb{Z}_{n}$ denote the ring of integers modulo $n$, and let
$\mathbb{Z}_{n}^{*}$ denote the group (under multiplication) of integers
relatively prime to $n$. The number of elements in $\mathbb{Z}_{n}^{*}$ is
$\varphi(n)$, where $\varphi$ is Euler's totient function. What is the average
number of elements in $\mathbb{Z}_{n}^{*}$, given an arbitrary $n$? One way to
answer this question is to apply the Selberg-Delange method \cite{Slbrg,
Dlnge, Tnbm} to the Dirichlet series
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{\varphi(n)}{n^{s+1}}  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{\varphi(p^{r})}{p^{r(s+1)}}\right) \\
& =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{p-1}{p^{rs+1}}\right) \\
& =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac{p-1}p%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac1{p^{rs}}\right) \\
& =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac{p-1}{p(p^{s}-1)}\right)  =G(s)\cdot\zeta(s)
\end{align*}
where $G(s)$ is bounded in a half plane $\operatorname*{Re}(s)>c$ for some
$c<1$. In fact, $G(s)=1/\zeta(s+1)$ in this case, and hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{\varphi(n)}n\sim\frac{G(1)}{\Gamma(1)}N=\frac1{\zeta(2)}N
\]
as $N\rightarrow\infty$. It follows by partial summation that
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\varphi(n)\sim\frac1{2\zeta(2)}N^{2}=\frac3{\pi^{2}}N^{2}.
\]
A more elementary proof of this asymptotic formula appears in \cite{Apstl}.
Since the Selberg-Delange method will be used throughout this paper, we choose
to illustrate its application in this simple setting.

Many other questions can be asked for arbitrary $n$:

\begin{itemize}
\item What is the average number of solutions of $x^{2}=1$ in $\mathbb{Z}%
_{n}^{*}?$

\item What is the average number of solutions of $x^{3}=1$ in $\mathbb{Z}%
_{n}^{*}?$

\item What is the average number of solutions of $x^{2}=0$ in $\mathbb{Z}%
_{n}?$

\item What is the average number of solutions of $x^{3}=0$ in $\mathbb{Z}%
_{n}?$

\item What is the average number of images of the map $y\mapsto y^{2}$ in
either $\mathbb{Z}_{n}$ or $\mathbb{Z}_{n}^{*}?$

\item What is the average number of images of the map $y\mapsto y^{3}$ in
either $\mathbb{Z}_{n}$ or $\mathbb{Z}_{n}^{*}?$
\end{itemize}

Although the answers require only straightforward use of standard techniques,
they do not seem to be explicitly given in the literature. We make no claim of
originality:\ Our purpose is only to collect results in one place and to
document relevant numerical techniques.

\section{Number Theory}

\subsection{Selberg-Delange Method}

Let $F(s)=\sum_{n=1}^{\infty}a(n)n^{-s}$ be a Dirichlet series with positive
coefficients and with the property that $G(s)=F(s)\cdot\zeta(s)^{-z}$ can be
analytically continued and is bounded over $\operatorname*{Re}(s)>c$, for some
$c<1$ and some $z\in\mathbb{C}$. Then
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
a(n)\sim\frac{G(1)}{\Gamma(z)}N\cdot(\ln N)^{z-1}%
\]
as $N\rightarrow\infty$. More terms of the asymptotic expansion are possible,
as is an accurate estimate of the error, but we omit these details for
brevity's sake.

A generalization of this method is required for our work involving averages
over arithmetic progressions. Let $\chi$ denote the principal character modulo
$k=q^{m}$, where $q$ is a prime and $m\geq1$. Here we examine
\[
F_{\chi}(s)=%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{\chi(n)a(n)}{n^{s}}=G_{\chi}(s)\cdot L_{\chi}(s)^{z}%
\]
where
\[
L_{\chi}(s)=%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{\chi(n)}{n^{s}}=\left(  1-\frac1{k^{s}}\right)  \zeta(s)
\]
is the L-series corresponding to $\chi$. Assuming $a(n)$ is a multiplicative
function and $q\nmid\ell$, it follows that
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
a(n)\sim\frac{G_{\chi}(1)}{\Gamma(z)}N\cdot(\ln N)^{z-1}%
\]
as $N\rightarrow\infty$ and, further, that
\[
G_{\chi}(1)=\frac1{\varphi(k)}\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{a(q^{r})}{q^{r}}\right)  ^{-1}G(1).
\]
In our examples, $q$ will be either $2$ or $3$ and the bracketed infinite
series will always collapse to a closed-form expression. Rather than directly
employing the formula for $G_{\chi}(1)$, however, we prefer instead to deduce
$F_{\chi}(s)$ (and hence $G_{\chi}(s)$) from $F(s)$ on basic principles.

\subsection{\label{Sqrt}Square Roots of Unity}

The number $a(n)$ of solutions of $x^{2}=1$ in $\mathbb{Z}_{n}^{*}$ is
\cite{Sec2}
\[
a(n)=\left\{
\begin{array}
[c]{lll}%
2^{\omega(n)-1} &  & \text{if }n\equiv2,6\operatorname*{mod}8,\\
2^{\omega(n)} &  & \text{if }n\equiv1,3,4,5,7\operatorname*{mod}8,\\
2^{\omega(n)+1} &  & \text{if }n\equiv0\operatorname*{mod}8
\end{array}
\right.
\]
where $\omega(n)$ denotes the number of distinct prime factors of $n$. It is
well-known that \cite{Finch}
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{2^{\omega(n)}}{n^{s}}  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+2%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac1{p^{rs}}\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac2{p^{s}-1}\right)  =\frac{\zeta(s)^{2}}{\zeta(2s)}%
=G(s)\cdot\zeta(s)^{2}%
\end{align*}
and hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
2^{\omega(n)}\sim\frac1{\zeta(2)}N\cdot\ln N=\frac6{\pi^{2}}N\cdot\ln N.
\]
We need to generalize this asymptotic formula to arithmetic progressions
$n\equiv\ell\operatorname*{mod}k$, where $k=2^{m}$ for $m\geq1$ and
$2\nmid\ell$. It can be shown that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n\equiv\ell\operatorname*{mod}k}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\equiv\ell\operatorname*{mod}k}}
%EndExpansion
\frac{2^{\omega(n)}}{n^{s}}  & \sim\frac1{\varphi(k)}%
%TCIMACRO{\dprod \limits_{p>2}}%
%BeginExpansion
{\displaystyle\prod\limits_{p>2}}
%EndExpansion
\left(  1+\frac2{p^{s}-1}\right) \\
\  & =\frac2k\left(  1+\frac2{2^{s}-1}\right)  ^{-1}\frac{\zeta(s)^{2}}%
{\zeta(2s)}=G_{\chi}(s)\cdot\zeta(s)^{2}%
\end{align*}
as $s\rightarrow1$, and thus
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
2^{\omega(n)}\sim\frac{G_{\chi}(1)}{\Gamma(2)}N\cdot\ln N=\frac4{k\pi^{2}%
}N\cdot\ln N.
\]
The cases $(k,\ell)=(8,1),(8,3),(8,5)$ and $(8,7)$ follow immediately. The
case $(k,\ell)=(8,4)$ proceeds from the case $(k,\ell)=(2,1)$:
\[
\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv4\operatorname*{mod}8 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv4\operatorname*{mod}8
}}}
%EndExpansion
2^{\omega(n)}=\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{4n\leq N, \\n\equiv1\operatorname*{mod}2
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{4n\leq N, \\n\equiv1\operatorname*{mod}2
}}}
%EndExpansion
2^{\omega(n)+1}\longrightarrow\frac14\cdot2\cdot\frac2{\pi^{2}}=\frac1{\pi
^{2}}.
\]
The case $(k,\ell)=(8,2)$ proceeds from the case $(k,\ell)=(4,1)$:
\[
\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv2\operatorname*{mod}8 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv2\operatorname*{mod}8
}}}
%EndExpansion
2^{\omega(n)}=\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{2n\leq N, \\n\equiv1\operatorname*{mod}4
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{2n\leq N, \\n\equiv1\operatorname*{mod}4
}}}
%EndExpansion
2^{\omega(n)+1}\longrightarrow\frac12\cdot2\cdot\frac1{\pi^{2}}=\frac1{\pi
^{2}}%
\]
and $(8,6)$ likewise proceeds from $(4,1)$. By everything proved thus far, we
have
\[
\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv0\operatorname*{mod}8 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv0\operatorname*{mod}8
}}}
%EndExpansion
2^{\omega(n)}\longrightarrow\frac6{\pi^{2}}-4\cdot\frac1{2\pi^{2}}-3\cdot
\frac1{\pi^{2}}=\frac1{\pi^{2}}.
\]
Therefore
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
a(n)\sim\left(  \frac12\cdot2\cdot\frac1{\pi^{2}}+\left(  4\cdot\frac
1{2\pi^{2}}+\frac1{\pi^{2}}\right)  +2\cdot\frac1{\pi^{2}}\right)  N\cdot\ln
N=\frac6{\pi^{2}}N\cdot\ln N.
\]
It is interesting that $(8,2)$ and $(8,6)$ balance perfectly against $(8,0)$
so that the mean value of $a(n)$ is asymptotically equivalent to the mean
value of $2^{\omega(n)}$.

\subsection{\label{Cbrt}Cube Roots of Unity}

The number $a(n)$ of solutions of $x^{3}=1$ in $\mathbb{Z}_{n}^{*}$ is
\cite{Sec3}
\[
a(n)=\left\{
\begin{array}
[c]{lll}%
3^{\tilde\omega(n)} &  & \text{if }n\equiv1,2,3,4,5,6,7,8\operatorname*{mod}%
9,\\
3^{\tilde\omega(n)+1} &  & \text{if }n\equiv0\operatorname*{mod}9
\end{array}
\right.
\]
where $\tilde\omega(n)$ denotes the number of distinct primes of the form
$3k+1$ dividing $n$:
\[
\tilde\omega(p^{r})=\left\{
\begin{array}
[c]{lll}%
0 &  & \text{if }p=3\text{ or }p\equiv2\operatorname*{mod}3,\\
1 &  & \text{if }p\equiv1\operatorname*{mod}3.
\end{array}
\right.
\]
First, note that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{3^{\tilde\omega(n)}}{n^{s}}  & =%
%TCIMACRO{\dprod \limits_{\substack{p=3\text{ or} \\p\equiv2\operatorname*{mod}%
%3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p=3\text{ or} \\p\equiv
2\operatorname*{mod}3 }}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac1{p^{rs}}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+3%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac1{p^{rs}}\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{\substack{p=3\text{ or} \\p\equiv2\operatorname*{mod}%
%3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p=3\text{ or} \\p\equiv
2\operatorname*{mod}3 }}}
%EndExpansion
\left(  1+\frac1{p^{s}-1}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac3{p^{s}-1}\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{\substack{p=3\text{ or} \\p\equiv2\operatorname*{mod}%
%3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p=3\text{ or} \\p\equiv
2\operatorname*{mod}3 }}}
%EndExpansion
\left(  1-\frac1{p^{s}}\right)  ^{-1}\cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1-\frac1{p^{s}}\right)  ^{-3}\left(  1-\frac1{p^{2s}}\right)  \left(
1-\frac2{p^{s}(p^{s}+1)}\right) \\
\  & =\zeta(s)\cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1-\frac1{p^{s}}\right)  ^{-2}\left(  1-\frac1{p^{2s}}\right)  \left(
1-\frac2{p^{s}(p^{s}+1)}\right)  =G(s)\cdot\zeta(s)^{2}%
\end{align*}
and \cite{Moree}
\[
\lim_{s\rightarrow1}%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1-\frac1{p^{s}}\right)  ^{-2}\cdot(s-1)=\frac{\sqrt{3}}{2\pi}%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1-\frac1{p^{2}}\right)  ^{-1};
\]
hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
3^{\tilde\omega(n)}\sim\frac{G(1)}{\Gamma(2)}N\cdot\ln N=C\cdot N\cdot\ln N
\]
where
\[
C=\frac{\sqrt{3}}{2\pi}%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1-\frac2{p(p+1)}\right)  =\frac{\sqrt{3}}{2\pi}%
(0.9410349413195354517900322...).
\]
We need to generalize this asymptotic formula to arithmetic progressions
$n\equiv\ell\operatorname*{mod}k$, where $k=3^{m}$ for $m\geq1$ and
$3\nmid\ell$. It can be shown that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n\equiv\ell\operatorname*{mod}k}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\equiv\ell\operatorname*{mod}k}}
%EndExpansion
\frac{3^{\tilde\omega(n)}}{n^{s}}  & \sim\frac1{\varphi(k)}%
%TCIMACRO{\dprod \limits_{p\equiv2\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv2\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac1{p^{s}-1}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac3{p^{s}-1}\right) \\
\  & =\frac3{2k}\left(  1+\frac1{3^{s}-1}\right)  ^{-1}G(s)\cdot\zeta
(s)^{2}=G_{\chi}(s)\cdot\zeta(s)^{2}%
\end{align*}
as $s\rightarrow1$, and thus
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
3^{\tilde\omega(n)}\sim\frac{G_{\chi}(1)}{\Gamma(2)}N\cdot\ln N=\frac
CkN\cdot\ln N.
\]
The cases $(k,\ell)=(9,1),(9,2),(9,4),(9,5),(9,7)$ and $(9,8)$ follow
immediately. The case $(9,3)$ proceeds from the case $(3,1)$:
\[
\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv3\operatorname*{mod}9 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv3\operatorname*{mod}9
}}}
%EndExpansion
3^{\tilde\omega(n)}=\frac1{N\cdot\ln N}%
%TCIMACRO{\dsum \limits_{\substack{3n\leq N, \\n\equiv1\operatorname*{mod}3
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{3n\leq N, \\n\equiv1\operatorname*{mod}3
}}}
%EndExpansion
3^{\tilde\omega(n)}\longrightarrow\frac13\cdot\frac C3=\frac C9
\]
and $(9,6),(9,0)$ likewise proceed from $(3,2),(3,0)$. Therefore
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
a(n)\sim\left(  8\cdot\frac C9+3\cdot\frac C9\right)  N\cdot\ln N=\frac
{11}9C\cdot N\cdot\ln N=(0.317...)N\cdot\ln N.
\]
Unlike earlier, the mean value of $a(n)$ is asymptotically greater than the
mean value of $3^{\tilde\omega(n)}$. Our estimate improves upon Cloitre
\cite{Sec3}, who gave $(0.4...)N\cdot\ln(N)$ on empirical grounds.

\subsection{Squares in $\mathbb{Z}_{n}^{*}$}

Let $a(n)$ be as defined in section [\ref{Sqrt}]. The number of squares, that
is, the cardinality of images under the map $y\mapsto y^{2}$ in $\mathbb{Z}%
_{n}^{*}$, is \cite{Sec4}
\[
b(n)=\frac{\varphi(n)}{a(n)}=\left\{
\begin{array}
[c]{lll}%
\dfrac{\varphi(n)}{2^{\omega(n)-1}} &  & \text{if }n\equiv
2,6\operatorname*{mod}8,\\
\dfrac{\varphi(n)}{2^{\omega(n)}} &  & \text{if }n\equiv
1,3,4,5,7\operatorname*{mod}8,\\
\dfrac{\varphi(n)}{2^{\omega(n)+1}} &  & \text{if }n\equiv0\operatorname*{mod}%
8.
\end{array}
\right.
\]
First, note that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{\varphi(n)}{n^{s+1}2^{\omega(n)}}  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac12%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{p-1}{p^{rs+1}}\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac{p-1}{2p(p^{s}-1)}\right)  =G(s)\cdot\zeta(s)^{1/2},
\end{align*}
hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{\varphi(n)}{n2^{\omega(n)}}\sim\frac{G(1)}{\Gamma(1/2)}N\cdot(\ln
N)^{-1/2}=C\cdot N\cdot(\ln N)^{-1/2}%
\]
where
\[
C=\frac1{\sqrt{\pi}}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{2p}\right)  \left(  1-\frac1p\right)  ^{1/2}=\frac1{\sqrt
{\pi}}(0.8121057111631225117062509...).
\]
It follows by partial summation that
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{\varphi(n)}{2^{\omega(n)}}\sim\frac C2\cdot N^{2}\cdot(\ln N)^{-1/2}.
\]
We need to generalize this asymptotic formula to arithmetic progressions
$n\equiv\ell\operatorname*{mod}k$, where $k=2^{m}$ for $m\geq1$ and
$2\nmid\ell$. It can be shown that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n\equiv\ell\operatorname*{mod}k}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\equiv\ell\operatorname*{mod}k}}
%EndExpansion
\frac{\varphi(n)}{n^{s+1}2^{\omega(n)}}  & \sim\frac1{\varphi(k)}%
%TCIMACRO{\dprod \limits_{p>2}}%
%BeginExpansion
{\displaystyle\prod\limits_{p>2}}
%EndExpansion
\left(  1+\frac{p-1}{2p(p^{s}-1)}\right) \\
\  & =\frac2k\left(  1+\frac1{4(2^{s}-1)}\right)  ^{-1}G(s)\cdot\zeta
(s)^{1/2}=G_{\chi}(s)\cdot\zeta(s)^{1/2}%
\end{align*}
as $s\rightarrow1$, and thus
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
\frac{\varphi(n)}{n2^{\omega(n)}}\sim\frac{G_{\chi}(1)}{\Gamma(1/2)}N\cdot(\ln
N)^{-1/2}=\frac8{5k}C\cdot N\cdot(\ln N)^{-1/2}%
\]
or
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
\frac{\varphi(n)}{2^{\omega(n)}}\sim\frac4{5k}C\cdot N^{2}\cdot(\ln N)^{-1/2}.
\]
The cases $(k,\ell)=(8,1),(8,3),(8,5)$ and $(8,7)$ follow immediately. The
case $(k,\ell)=(8,4)$ proceeds from the case $(k,\ell)=(2,1)$:
\[
\frac{(\ln N)^{1/2}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv4\operatorname*{mod}8 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv4\operatorname*{mod}8
}}}
%EndExpansion
\frac{\varphi(n)}{2^{\omega(n)}}=\frac{(\ln N)^{1/2}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{4n\leq N, \\n\equiv1\operatorname*{mod}2
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{4n\leq N, \\n\equiv1\operatorname*{mod}2
}}}
%EndExpansion
\frac{2\varphi(n)}{2^{\omega(n)+1}}\longrightarrow\frac1{16}\cdot\frac
4{10}C=\frac C{40}.
\]
The case $(k,\ell)=(8,2)$ proceeds from the case $(k,\ell)=(4,1)$:
\[
\frac{(\ln N)^{1/2}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv2\operatorname*{mod}8 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv2\operatorname*{mod}8
}}}
%EndExpansion
\frac{\varphi(n)}{2^{\omega(n)}}=\frac{(\ln N)^{1/2}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{2n\leq N, \\n\equiv1\operatorname*{mod}4
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{2n\leq N, \\n\equiv1\operatorname*{mod}4
}}}
%EndExpansion
\frac{\varphi(n)}{2^{\omega(n)+1}}\longrightarrow\frac14\cdot\frac12\cdot
\frac4{20}C=\frac C{40}%
\]
and $(8,6)$ likewise proceeds from $(4,1)$. By everything proved thus far, we
have
\[
\frac{(\ln N)^{1/2}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv0\operatorname*{mod}8 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv0\operatorname*{mod}8
}}}
%EndExpansion
\frac{\varphi(n)}{2^{\omega(n)}}\longrightarrow\frac C2-4\cdot\frac
C{10}-\frac C{40}-2\cdot\frac C{40}=\frac C{40}.
\]
Therefore
\begin{align*}%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
b(n)  & \sim\left(  2\cdot2\cdot\frac C{40}+\left(  4\cdot\frac C{10}+\frac
C{40}\right)  +\frac12\cdot\frac C{40}\right)  N^{2}\cdot(\ln N)^{-1/2}\\
\  & =\frac{43}{80}C\cdot N^{2}\cdot(\ln N)^{-1/2}=(0.246...)N^{2}\cdot(\ln
N)^{-1/2}.
\end{align*}


\subsection{Cubes in $\mathbb{Z}_{n}^{*}$}

Let $a(n)$ be as defined in section [\ref{Cbrt}]. The number of cubes, that
is, the cardinality of images under the map $y\mapsto y^{3}$ in $\mathbb{Z}%
_{n}^{*}$, is \cite{Sec5}
\[
b(n)=\frac{\varphi(n)}{a(n)}=\left\{
\begin{array}
[c]{lll}%
\dfrac{\varphi(n)}{3^{\tilde\omega(n)}} &  & \text{if }n\equiv
1,2,3,4,5,6,7,8\operatorname*{mod}9,\\
\dfrac{\varphi(n)}{3^{\tilde\omega(n)+1}} &  & \text{if }n\equiv
0\operatorname*{mod}9.
\end{array}
\right.
\]
First, note that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{\varphi(n)}{n^{s+1}3^{\tilde\omega(n)}}  & =%
%TCIMACRO{\dprod \limits_{\substack{p=3\text{ or} \\p\equiv2\operatorname*{mod}%
%3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p=3\text{ or} \\p\equiv
2\operatorname*{mod}3 }}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{p-1}{p^{rs+1}}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac13%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{p-1}{p^{rs+1}}\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{\substack{p=3\text{ or} \\p\equiv2\operatorname*{mod}%
%3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p=3\text{ or} \\p\equiv
2\operatorname*{mod}3 }}}
%EndExpansion
\left(  1+\frac{p-1}{p(p^{s}-1)}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac{p-1}{3p(p^{s}-1)}\right)  =G(s)\cdot\zeta(s)^{2/3},
\end{align*}
hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{\varphi(n)}{n3^{\tilde\omega(n)}}\sim\frac{G(1)}{\Gamma(2/3)}N\cdot(\ln
N)^{-1/3}=C\cdot N\cdot(\ln N)^{-1/3}%
\]
where
\begin{align*}
C  & =\frac1{\Gamma(2/3)}%
%TCIMACRO{\dprod \limits_{\substack{p=3\text{ or} \\p\equiv2\operatorname*{mod}%
%3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p=3\text{ or} \\p\equiv
2\operatorname*{mod}3 }}}
%EndExpansion
\left(  1+\frac1p\right)  \left(  1-\frac1p\right)  ^{2/3}\cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac1{3p}\right)  \left(  1-\frac1p\right)  ^{2/3}\\
\  & =\frac1{\Gamma(2/3)}(0.9477556177621765519078142...).
\end{align*}
It follows by partial summation that
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{\varphi(n)}{3^{\tilde\omega(n)}}\sim\frac C2\cdot N^{2}\cdot(\ln
N)^{-1/3}.
\]
We need to generalize this asymptotic formula to arithmetic progressions
$n\equiv\ell\operatorname*{mod}k$, where $k=3^{m}$ for $m\geq1$ and
$3\nmid\ell$. It can be shown that
\begin{align*}%
%TCIMACRO{\dsum \limits_{n\equiv\ell\operatorname*{mod}k}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\equiv\ell\operatorname*{mod}k}}
%EndExpansion
\frac{\varphi(n)}{n^{s+1}3^{\tilde\omega(n)}}  & \sim\frac1{\varphi(k)}%
%TCIMACRO{\dprod \limits_{p\equiv2\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv2\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac{p-1}{p(p^{s}-1)}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p\equiv1\operatorname*{mod}3}}%
%BeginExpansion
{\displaystyle\prod\limits_{p\equiv1\operatorname*{mod}3}}
%EndExpansion
\left(  1+\frac{p-1}{3p(p^{s}-1)}\right) \\
\  & =\frac3{2k}\left(  1+\frac2{3(3^{s}-1)}\right)  ^{-1}G(s)\cdot
\zeta(s)^{2/3}=G_{\chi}(s)\cdot\zeta(s)^{2/3}%
\end{align*}
as $s\rightarrow1$, and thus
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
\frac{\varphi(n)}{n3^{\tilde\omega(n)}}\sim\frac{G_{\chi}(1)}{\Gamma
(2/3)}N\cdot(\ln N)^{-1/3}=\frac9{8k}C\cdot N\cdot(\ln N)^{-1/3}%
\]
or
\[%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}k
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv\ell\operatorname*{mod}%
k }}}
%EndExpansion
\frac{\varphi(n)}{3^{\tilde\omega(n)}}\sim\frac9{16k}C\cdot N^{2}\cdot(\ln
N)^{-1/3}.
\]
The cases $(k,\ell)=(9,1),(9,2),(9,4),(9,5),(9,7)$ and $(9,8)$ follow
immediately. The case $(9,3)$ proceeds from the case $(3,1)$:
\[
\frac{(\ln N)^{1/3}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv3\operatorname*{mod}9 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv3\operatorname*{mod}9
}}}
%EndExpansion
\frac{\varphi(n)}{3^{\tilde\omega(n)}}=\frac{(\ln N)^{1/3}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{3n\leq N, \\n\equiv1\operatorname*{mod}3
%}}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{3n\leq N, \\n\equiv1\operatorname*{mod}3
}}}
%EndExpansion
\frac{2\varphi(n)}{3^{\tilde\omega(n)}}\longrightarrow\frac19\cdot2\cdot
\frac9{48}C=\frac C{24}%
\]
and $(9,6)$ likewise proceeds from $(3,2)$. By everything proved thus far, we
have
\[
\frac{(\ln N)^{1/3}}{N^{2}}%
%TCIMACRO{\dsum \limits_{\substack{n\leq N, \\n\equiv0\operatorname*{mod}9 }}}%
%BeginExpansion
{\displaystyle\sum\limits_{\substack{n\leq N, \\n\equiv0\operatorname*{mod}9
}}}
%EndExpansion
\frac{\varphi(n)}{3^{\tilde\omega(n)}}\longrightarrow\frac C2-6\cdot\frac
C{16}-2\cdot\frac C{24}=\frac C{24}.
\]
Therefore
\begin{align*}%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
b(n)  & \sim\left(  \left(  6\cdot\frac C{16}+2\cdot\frac C{24}\right)
+\frac13\cdot\frac C{24}\right)  N^{2}\cdot(\ln N)^{-1/3}\\
\  & =\frac{17}{36}C\cdot N^{2}\cdot(\ln N)^{-1/3}=(0.330...)N^{2}\cdot(\ln
N)^{-1/3}.
\end{align*}


\subsection{Square Roots of Nullity}

The number $a(n)$ of solutions of $x^{2}=0$ in $\mathbb{Z}_{n}$ is a
multiplicative function of $n$, with $a(p^{r})=p^{\left\lfloor
r/2\right\rfloor }$, thus \cite{Sec6, Brghn}
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{a(n)}{n^{s}}  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}+\frac p{p^{2s}}+\frac p{p^{3s}}+\frac{p^{2}}{p^{4s}%
}+\frac{p^{2}}{p^{5s}}+\frac{p^{3}}{p^{6s}}+\frac{p^{3}}{p^{7s}}+\cdots\right)
\\
\  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}1+\frac p{p^{2s}}+\frac1{p^{s}}\frac p{p^{2s}}%
+\frac{p^{2}}{p^{4s}}+\frac1{p^{s}}\frac{p^{2}}{p^{4s}}+\frac{p^{3}}{p^{6s}%
}+\frac1{p^{s}}\frac{p^{3}}{p^{6s}}+\cdots\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  \dfrac1{1-\dfrac p{p^{2s}}}+\dfrac{1/p^{s}}{1-\dfrac p{p^{2s}}%
}\right)  =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\dfrac1{p^{2s-1}}\right)  ^{-1}\left(  1+\frac1{p^{s}}\right) \\
\  & =\frac{\zeta(2s-1)\zeta(s)}{\zeta(2s)}=G(s)\cdot\zeta(s)^{2}%
\end{align*}
and $\lim_{s\rightarrow1}\zeta(2s-1)\cdot(s-1)=1/2$, hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
a(n)\sim\frac{G(1)}{\Gamma(2)}N\cdot\ln N=\frac3{\pi^{2}}N\cdot\ln N.
\]


\subsection{Cube Roots of Nullity}

The number $a(n)$ of solutions of $x^{3}=0$ in $\mathbb{Z}_{n}$ is a
multiplicative function of $n$, with $a(p^{r})=p^{\left\lfloor
2r/3\right\rfloor }$, thus \cite{Sec7}
\begin{align*}%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{a(n)}{n^{s}}  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}+\frac p{p^{2s}}+\frac{p^{2}}{p^{3s}}+\frac{p^{2}%
}{p^{4s}}+\frac{p^{3}}{p^{5s}}+\frac{p^{4}}{p^{6s}}+\frac{p^{4}}{p^{7s}}%
+\frac{p^{5}}{p^{8s}}+\frac{p^{6}}{p^{9s}}+\frac{p^{6}}{p^{10s}}+\cdots\right)
\\
\  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\tfrac1{p^{s}}1+\tfrac p{p^{2s}}1+\tfrac{p^{2}}{p^{3s}}%
+\tfrac1{p^{s}}\tfrac{p^{2}}{p^{3s}}+\tfrac p{p^{2s}}\tfrac{p^{2}}{p^{3s}%
}+\tfrac{p^{4}}{p^{6s}}+\tfrac1{p^{s}}\tfrac{p^{4}}{p^{6s}}+\tfrac p{p^{2s}%
}\tfrac{p^{4}}{p^{6s}}+\tfrac{p^{6}}{p^{9s}}+\tfrac1{p^{s}}\tfrac{p^{6}%
}{p^{9s}}+\cdots\right) \\
\  & =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  \dfrac1{1-\dfrac{p^{2}}{p^{3s}}}+\dfrac{1/p^{s}}{1-\dfrac{p^{2}%
}{p^{3s}}}+\dfrac{p/p^{2s}}{1-\dfrac{p^{2}}{p^{3s}}}\right)  =%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\dfrac1{p^{3s-2}}\right)  ^{-1}\left(  1+\frac1{p^{s}}%
+\frac1{p^{2s-1}}\right) \\
\  & =\zeta(3s-2)%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}+\frac1{p^{2s-1}}\right)  =G(s)\cdot\zeta(s)^{3}.
\end{align*}
We have
\begin{align*}
\lim_{s\rightarrow1}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}+\frac1{p^{2s-1}}\right)  \cdot(s-1)^{2}  &
=\lim_{s\rightarrow1}\frac1{\zeta(s)\cdot2\zeta(2s-1)}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}+\frac1{p^{2s-1}}\right) \\
\  & =\frac12\lim_{s\rightarrow1}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac1{p^{s}}+\frac1{p^{2s-1}}\right)  \left(  1-\frac1{p^{s}%
}\right)  \left(  1-\frac1{p^{2s-1}}\right) \\
\  & =\frac12%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac2p\right)  \left(  1-\frac1p\right)  ^{2}\\
\  & =\frac12%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1+\frac3{p-1}\right)  \left(  1-\frac1p\right)  ^{3}\\
\  & =\frac12%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\frac1{p^{2}}\right)  \left(  1-\frac2{p(p+1)}\right) \\
\  & =\frac1{2\zeta(2)}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\frac2{p(p+1)}\right)
\end{align*}
and $\lim_{s\rightarrow1}\zeta(3s-2)\cdot(s-1)=1/3$, hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
a(n)\sim\frac{G(1)}{\Gamma(3)}N\cdot(\ln N)^{2}=C\cdot N\cdot(\ln N)^{2}%
\]
where \cite{Finch, Sec7}
\[
C=\frac1{2\pi^{2}}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\frac2{p(p+1)}\right)  =\frac1{12}(0.2867474284344787341078927...).
\]


\subsection{Squares in $\mathbb{Z}_{n}$}

The number $b(n)$ of images under the map $y\mapsto y^{2}$ in $\mathbb{Z}_{n}$
is a multiplicative function of $n$, with \cite{Sec8, Prmrs, Stngl}
\[
b(p^{r})=\left\{
\begin{array}
[c]{lll}%
\dfrac13\left(  2^{r-1}+4\right)  &  & \text{if }p=2\text{ and }%
r\equiv0\operatorname*{mod}2,\\
\dfrac13\left(  2^{r-1}+5\right)  &  & \text{if }p=2\text{ and }%
r\equiv1\operatorname*{mod}2,\\
\dfrac1{2(p+1)}\left(  p^{r+1}+p+2\right)  &  & \text{if }p>2\text{ and
}r\equiv0\operatorname*{mod}2,\\
\dfrac1{2(p+1)}\left(  p^{r+1}+2p+1\right)  &  & \text{if }p>2\text{ and
}r\equiv1\operatorname*{mod}2
\end{array}
\right.
\]
and
\begin{align*}
F(s)=%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{b(n)}{n^{s+1}}=\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{b(2^{r})}{2^{r(s+1)}}\right)  \cdot%
%TCIMACRO{\dprod \limits_{p>2}}%
%BeginExpansion
{\displaystyle\prod\limits_{p>2}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{b(p^{r})}{p^{r(s+1)}}\right)  .
\end{align*}
The left-hand factor in $F(s)$ simplifies to
\begin{align*}
& \ \ \ 1+\frac13%
%TCIMACRO{\dsum \limits_{i=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{\infty}}
%EndExpansion
\frac{2^{2i-1}+4}{2^{(2i)(s+1)}}+\frac13%
%TCIMACRO{\dsum \limits_{j=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=1}^{\infty}}
%EndExpansion
\frac{2^{(2j-1)-1}+5}{2^{(2j-1)(s+1)}}\\
\  & =1+\frac12\left(  \frac{4^{s+1}-3}{(4^{s+1}-1)(4^{s}-1)}+2^{s}%
\frac{2\cdot4^{s+1}-7}{(4^{s+1}-1)(4^{s}-1)}\right) \\
\  & =\left(  1+\frac{2^{2s+1}-2^{s+1}-1}{2^{s+2}(2^{2s+1}-2^{s-1}-1)}\right)
\left(  1-\frac{2^{s+1}+2}{2(2^{s+1}+1)(2^{s+1}-1)}\right)  \left(
1-\frac1{2^{s}}\right)  ^{-1}%
\end{align*}
and the $p^{\text{th}}$ right-hand factor simplifies to
\begin{align*}
& \ \ \ 1+\dfrac1{2(p+1)}%
%TCIMACRO{\dsum \limits_{i=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{\infty}}
%EndExpansion
\dfrac{p^{2i+1}+p+2}{p^{(2i)(s+1)}}+\dfrac1{2(p+1)}%
%TCIMACRO{\dsum \limits_{j=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=1}^{\infty}}
%EndExpansion
\dfrac{p^{(2j-1)+1}+2p+1}{p^{(2j-1)(s+1)}}\\
\  & =1+\dfrac1{2(p+1)}\left(  \dfrac{p^{2s+3}+p^{2s+1}+2p^{2s}-2p-2}%
{(p^{2s+2}-1)(p^{2s}-1)}+p^{s+1}\dfrac{p^{2s+2}+2p^{2s+1}+p^{2s}%
-2p-2}{(p^{2s+2}-1)(p^{2s}-1)}\right) \\
\  & =\left(  1-\frac{(p^{s+1}+2)(p-1)}{2(p^{s+1}+1)(p^{s+1}-1)}\right)
\left(  1-\frac1{p^{s}}\right)  ^{-1}.
\end{align*}
We have
\[
F(s)=\zeta(s)\left(  1+\frac{2^{2s+1}-2^{s+1}-1}{2^{s+2}(2^{2s+1}-2^{s-1}%
-1)}\right)
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\frac{(p^{s+1}+2)(p-1)}{2(p^{s+1}+1)(p^{s+1}-1)}\right)
=G(s)\cdot\zeta(s)^{1/2}%
\]
and hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{b(n)}n\sim\frac{G(1)}{\Gamma(1/2)}N\cdot(\ln N)^{-1/2}=C\cdot N\cdot(\ln
N)^{-1/2}%
\]
where
\begin{align*}
C  & =\frac{17}{16}\frac1{\sqrt{\pi}}%
%TCIMACRO{\dprod \limits_{p}}%
%BeginExpansion
{\displaystyle\prod\limits_{p}}
%EndExpansion
\left(  1-\frac{p^{2}+2}{2(p^{2}+1)(p+1)}\right)  \left(  1-\frac1p\right)
^{-1/2}\\
\  & =\frac{17}{16}\frac1{\sqrt{\pi}}(1.2569136102101885959492115...).
\end{align*}
It follows by partial summation that
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
b(n)\sim\frac C2\cdot N^{2}\cdot(\ln N)^{-1/2}=(0.376...)N^{2}\cdot(\ln
N)^{-1/2}.
\]


\subsection{Cubes in $\mathbb{Z}_{n}$}

The number $b(n)$ of images under the map $y\mapsto y^{3}$ in $\mathbb{Z}_{n}$
is a multiplicative function of $n$, with
\[
b(p^{r})=\left\{
\begin{array}
[c]{lll}%
\dfrac1{13}\left(  3^{r+1}+10\right)  &  & \text{if }p=3\text{ and }%
r\equiv0\operatorname*{mod}3,\\
\dfrac1{13}\left(  3^{r+1}+30\right)  &  & \text{if }p=3\text{ and }%
r\equiv1\operatorname*{mod}3,\\
\dfrac1{13}\left(  3^{r+1}+12\right)  &  & \text{if }p=3\text{ and }%
r\equiv2\operatorname*{mod}3,\\
\dfrac1{p^{2}+p+1}\left(  p^{r+2}+p+1\right)  &  & \text{if }p\equiv
2\operatorname*{mod}3\text{ and }r\equiv0\operatorname*{mod}3,\\
\dfrac1{p^{2}+p+1}\left(  p^{r+2}+p^{2}+p\right)  &  & \text{if }%
p\equiv2\operatorname*{mod}3\text{ and }r\equiv1\operatorname*{mod}3,\\
\dfrac1{p^{2}+p+1}\left(  p^{r+2}+p^{2}+1\right)  &  & \text{if }%
p\equiv2\operatorname*{mod}3\text{ and }r\equiv2\operatorname*{mod}3,\\
\dfrac1{3(p^{2}+p+1)}\left(  p^{r+2}+2p^{2}+3p+3\right)  &  & \text{if
}p\equiv1\operatorname*{mod}3\text{ and }r\equiv0\operatorname*{mod}3,\\
\dfrac1{3(p^{2}+p+1)}\left(  p^{r+2}+3p^{2}+3p+2\right)  &  & \text{if
}p\equiv1\operatorname*{mod}3\text{ and }r\equiv1\operatorname*{mod}3,\\
\dfrac1{3(p^{2}+p+1)}\left(  p^{r+2}+3p^{2}+2p+3\right)  &  & \text{if
}p\equiv1\operatorname*{mod}3\text{ and }r\equiv2\operatorname*{mod}3
\end{array}
\right.
\]
and
\begin{align*}
F(s)=%
%TCIMACRO{\dsum \limits_{n=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{n=1}^{\infty}}
%EndExpansion
\frac{b(n)}{n^{s+1}}=\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{b(3^{r})}{3^{r(s+1)}}\right)  \cdot%
%TCIMACRO{\dprod \limits_{\substack{\text{ }p\equiv2 \\\operatorname*{mod}3
%}}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{\text{ }p\equiv2 \\\operatorname*{mod}3
}}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{b(p^{r})}{p^{r(s+1)}}\right)  \cdot%
%TCIMACRO{\dprod \limits_{\substack{p\equiv1 \\\operatorname*{mod}3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p\equiv1 \\\operatorname*{mod}3 }}}
%EndExpansion
\left(  1+%
%TCIMACRO{\dsum \limits_{r=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{r=1}^{\infty}}
%EndExpansion
\frac{b(p^{r})}{p^{r(s+1)}}\right)  .
\end{align*}
The expressions for $b(p^{r})$ follow from a conjecture by Wilson \cite{Sec9};
a proof for the case $p=2$, $r\equiv0\operatorname*{mod}3$ was given by Wilmer
\&\ Schirokauer \cite{WS}. The left-hand factor in $F(s)$ simplifies to
\begin{align*}
& 1+\frac1{13}\left(
%TCIMACRO{\dsum \limits_{i=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{\infty}}
%EndExpansion
\frac{3^{3i+1}+10}{3^{(3i)(s+1)}}+%
%TCIMACRO{\dsum \limits_{j=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=1}^{\infty}}
%EndExpansion
\frac{3^{(3j-2)+1}+30}{3^{(3j-2)(s+1)}}+%
%TCIMACRO{\dsum \limits_{k=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{k=1}^{\infty}}
%EndExpansion
\frac{3^{(3k-1)+1}+12}{3^{(3k-1)(s+1)}}\right) \\
& =1+\left(  \frac{7\cdot27^{s}-1}{(27^{s+1}-1)(27^{s}-1)}+3^{2s+1}%
\frac{9\cdot27^{s}-7}{(27^{s+1}-1)(27^{s}-1)}+3^{s+1}\frac{3\cdot27^{s}%
-1}{(27^{s+1}-1)(27^{s}-1)}\right) \\
& =\left(  1-\frac{2\left(  3^{s+2}+1\right)  }{(3^{s+1}+3^{(s+1)/2}%
+1)(3^{s+1}-3^{(s+1)/2}+1)(3^{s+1}-1)}\right)  \left(  1-\frac1{3^{s}}\right)
^{-1}.
\end{align*}
The $p^{\text{th}}$ right-hand factor simplifies to
\begin{align*}
& 1+\dfrac1{p^{2}+p+1}\left(
%TCIMACRO{\dsum \limits_{i=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{\infty}}
%EndExpansion
\dfrac{p^{3i+2}+p+1}{p^{(3i)(s+1)}}+%
%TCIMACRO{\dsum \limits_{j=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=1}^{\infty}}
%EndExpansion
\dfrac{p^{(3j-2)+2}+p^{2}+p}{p^{(3j-2)(s+1)}}+%
%TCIMACRO{\dsum \limits_{k=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{k=1}^{\infty}}
%EndExpansion
\dfrac{p^{(3k-1)+2}+p^{2}+1}{p^{(3k-1)(s+1)}}\right) \\
& =1+\dfrac1{p^{2}+p+1}\left(  \dfrac{p^{3s+5}+p^{3s+1}+p^{3s}-p^{2}%
-p-1}{(p^{3s+3}-1)(p^{3s}-1)}\right. \\
& \left.  \;\;+\,p^{2s+2}\dfrac{p^{3s+3}+p^{3s+2}+p^{3s+1}-p^{2}%
-p-1}{(p^{3s+3}-1)(p^{3s}-1)}\right. \\
& \left.  \;\;+\,p^{s+1}\dfrac{p^{3s+4}+p^{3s+2}+p^{3s}-p^{2}-p-1}%
{(p^{3s+3}-1)(p^{3s}-1)}\right) \\
& =\left(  1-\frac{(p^{s+1}+1)(p-1)}{(p^{s+1}+p^{(s+1)/2}+1)(p^{s+1}%
-p^{(s+1)/2}+1)(p^{s+1}-1)}\right)  \left(  1-\frac1{p^{s}}\right)  ^{-1}%
\end{align*}
when $p\equiv2\operatorname*{mod}3$ and
\begin{align*}
& \ \ 1+\tfrac1{3(p^{2}+p+1)}\left(
%TCIMACRO{\dsum \limits_{i=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{\infty}}
%EndExpansion
\tfrac{p^{3i+2}+2p^{2}+3p+3}{p^{(3i)(s+1)}}+%
%TCIMACRO{\dsum \limits_{j=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=1}^{\infty}}
%EndExpansion
\tfrac{p^{(3j-2)+2}+3p^{2}+3p+2}{p^{(3j-2)(s+1)}}+%
%TCIMACRO{\dsum \limits_{k=1}^{\infty}}%
%BeginExpansion
{\displaystyle\sum\limits_{k=1}^{\infty}}
%EndExpansion
\tfrac{p^{(3k-1)+2}+3p^{2}+2p+3}{p^{(3k-1)(s+1)}}\right) \\
& =1+\dfrac1{3(p^{2}+p+1)}\left(  \dfrac{p^{3s+5}+2p^{3s+2}+3p^{3s+1}%
+3p^{3s}-3p^{2}-3p-3}{(p^{3s+3}-1)(p^{3s}-1)}\right. \\
& \left.  \;\;+\,p^{2s+2}\dfrac{p^{3s+3}+3p^{3s+2}+3p^{3s+1}+2p^{3s}%
-3p^{2}-3p-3}{(p^{3s+3}-1)(p^{3s}-1)}\right. \\
& \left.  \;\;+\,p^{s+1}\dfrac{p^{3s+4}+3p^{3s+2}+2p^{3s+1}+3p^{3s}%
-3p^{2}-3p-3}{(p^{3s+3}-1)(p^{3s}-1)}\right) \\
& =\left(  1-\frac{(2p^{2s+2}+3p^{s+1}+3)(p-1)}{3(p^{s+1}+p^{(s+1)/2}%
+1)(p^{s+1}-p^{(s+1)/2}+1)(p^{s+1}-1)}\right)  \left(  1-\frac1{p^{s}}\right)
^{-1}%
\end{align*}
when $p\equiv1\operatorname*{mod}3$. We have
\begin{align*}
F(s)  & =\zeta(s)\left(  1-\frac{2\left(  3^{s+2}+1\right)  }{(3^{s+1}%
+3^{(s+1)/2}+1)(3^{s+1}-3^{(s+1)/2}+1)(3^{s+1}-1)}\right) \\
& \;\cdot%
%TCIMACRO{\dprod \limits_{\substack{\text{ }p\equiv2 \\\operatorname*{mod}3
%}}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{\text{ }p\equiv2 \\\operatorname*{mod}3
}}}
%EndExpansion
\left(  1-\frac{(p^{s+1}+1)(p-1)}{(p^{s+1}+p^{(s+1)/2}+1)(p^{s+1}%
-p^{(s+1)/2}+1)(p^{s+1}-1)}\right) \\
& \;\cdot%
%TCIMACRO{\dprod \limits_{\substack{p\equiv1 \\\operatorname*{mod}3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p\equiv1 \\\operatorname*{mod}3 }}}
%EndExpansion
\left(  1-\frac{(2p^{2s+2}+3p^{s+1}+3)(p-1)}{3(p^{s+1}+p^{(s+1)/2}%
+1)(p^{s+1}-p^{(s+1)/2}+1)(p^{s+1}-1)}\right) \\
& =G(s)\cdot\zeta(s)^{2/3}%
\end{align*}
and hence
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
\frac{b(n)}n\sim\frac{G(1)}{\Gamma(2/3)}N\cdot(\ln N)^{-1/3}=C\cdot N\cdot(\ln
N)^{-1/3}%
\]
where
\begin{align*}
C  & =\frac{12}{13}\frac1{\Gamma(2/3)}\left(  1-\frac13\right)  ^{-1/3}\\
& \;\;\cdot%
%TCIMACRO{\dprod \limits_{\substack{\text{ }p\equiv2 \\\operatorname*{mod}3
%}}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{\text{ }p\equiv2 \\\operatorname*{mod}3
}}}
%EndExpansion
\left(  1-\frac{p^{2}+1}{(p^{2}+p+1)(p^{2}-p+1)(p+1)}\right)  \left(
1-\frac1p\right)  ^{-1/3}\\
& \;\;\cdot%
%TCIMACRO{\dprod \limits_{\substack{p\equiv1 \\\operatorname*{mod}3 }}}%
%BeginExpansion
{\displaystyle\prod\limits_{\substack{p\equiv1 \\\operatorname*{mod}3 }}}
%EndExpansion
\left(  1-\frac{2p^{4}+3p^{2}+3}{3(p^{2}+p+1)(p^{2}-p+1)(p+1)}\right)  \left(
1-\frac1p\right)  ^{-1/3}\\
& =\frac{12}{13}\frac1{\Gamma(2/3)}(1.4225831466986636811460982...).
\end{align*}
It follows by partial summation that
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
b(n)\sim\frac C2\cdot N^{2}\cdot(\ln N)^{-1/3}=(0.484...)N^{2}\cdot(\ln
N)^{-1/3}.
\]
We emphasize that this result is only conjectural.

\subsection{Other Problems}

The power of the Selberg-Delange method is evident (many deeper applications
occur elsewhere in the literature). We merely mention that the number $a(n)$
of solutions of $x^{2}=-1$ in $\mathbb{Z}_{n}^{*}$ satisfies
\[%
%TCIMACRO{\dsum \limits_{n\leq N}}%
%BeginExpansion
{\displaystyle\sum\limits_{n\leq N}}
%EndExpansion
a(n)\sim\frac3{2\pi}N;
\]
in particular, $x^{2}=-1$ has asymptotically far fewer solutions than
$x^{2}=1$. Such asymmetry does not occur for $x^{3}=\pm1$ (just replace $x$ by
$-x$). See other modular polynomial equations at \cite{Sec10} and the
enumeration of weakly primitive Dirichlet characters at \cite{Fnch, Sec11}.

A more difficult exercise concerns the number $b(n)$ of elements of
$\mathbb{Z}_{n}$ that are \textit{both} squares and cubes. If $w=z^{6}$, then
clearly $w=(z^{3})^{2}=(z^{2})^{3}$. Conversely, if $w=u^{2}=v^{3}$, then
$(uv^{-1})^{6}=(u^{2})^{3}(v^{3})^{-2}=w^{3}w^{-2}=w$. Hence $b(n)$ is the
same as the number of sixth-powers in $\mathbb{Z}_{n}$. Wilson's conjecture
again provides expressions for $b(p^{r})$, which in turn give formulas for
$F(s)$ and $G(s)$. The details of this and other higher-power problems are
left to someone else \cite{Sec12}.\newpage\ \ 

\section{Numerical Techniques}

\subsection{Prime Products}

Here is a method for evaluating constants of the form
\[
C=\prod_{p\equiv\ell\operatorname*{mod}k}f(p)
\]
to high precision, where the product is taken over all primes of the form
$p=mk+\ell$. Suppose that the function $\ln f$ has asymptotic expansion
\[
\ln f(p)=\frac{c_{2}}{p^{s_{2}}}+\frac{c_{3}}{p^{s_{3}}}+\cdots+\frac{c_{n}%
}{p^{s_{n}}}+\cdots
\]
as $p\rightarrow\infty,$ where $\left(  c_{n},s_{n}\right)  $ are real numbers
and $1<s_{2}<...<s_{n}<...$. (Often $s_{n}=n$ occurs.) Define the
$(k,\ell)^{\text{th}}$ \textit{prime zeta function}
\[
P_{k,\ell}(s)=\sum_{p\equiv\ell\operatorname*{mod}k}\frac1{p^{s}}%
\]
for $\operatorname*{Re}(s)>1$; it follows that
\[
\ln C=\sum_{p\equiv\ell\operatorname*{mod}k}\ln f(p)=\sum_{n\geq2}%
c_{n}P_{k,\ell}(s_{n}).
\]
Let $p_{k,\ell}$ denote the smallest prime of the form $mk+\ell$; clearly
$P_{k,\ell}(n)\sim1/p_{k,\ell}^{n}$ as $n\rightarrow\infty$. Consequently, if
the coefficients $c_{n}$ are uniformly bounded, the convergence of the sum is
fast (geometric). It hence remains to accurately compute the values
$P_{k,\ell}(s_{n})$.

\subsection{Prime Zeta Functions}

Let $\operatorname*{Re}(s)>1$. The classical prime zeta function
$P(s)=P_{1,0}(s)$ can be related to the classical zeta function by Euler's
famous product:
\[
\ln\zeta(s)=-\sum_{p}\ln\left(  1-\frac1{p^{s}}\right)  =\sum_{p}\sum_{n\geq
1}\frac1{np^{ns}}=\sum_{n\geq1}\frac{P(ns)}n.
\]
Applying the M\"obius inversion formula, we obtain \cite{Frbrg, Cohen}
\[
P(s)=\sum_{n=1}^{\infty}\frac{\mu(n)}n\ln\zeta(ns).
\]
Since $\ln\zeta(ns)\sim2^{-ns}$ as $n\rightarrow\infty$, only a few terms in
this series are required to compute an accurate value of $P(s).$ Also
$P(s)\sim-\ln(s-1)$ as $s\rightarrow1^{+}$. These facts are useful in
computing constants of the form $\prod_{p}f(p)$.

For constants of the form $\prod_{p\equiv\ell\operatorname*{mod}3}f(p)$, we
need $P_{3,1}(s)$ and $P_{3,2}(s)$. To achieve this, it is necessary to
introduce the two characters modulo $3$:
\[%
\begin{array}
[c]{ccc}%
\chi_{0}(n)=\left\{
\begin{array}
[c]{ccc}%
1 &  & \text{if }n\equiv1\operatorname*{mod}3,\\
1 &  & \text{if }n\equiv2\operatorname*{mod}3,\\
0 &  & \text{if }n\equiv0\operatorname*{mod}3,
\end{array}
\right.  &  & \chi_{1}(n)=\left\{
\begin{array}
[c]{ccc}%
1 &  & \text{if }n\equiv1\operatorname*{mod}3,\\
-1 &  & \text{if }n\equiv2\operatorname*{mod}3,\\
0 &  & \text{if }n\equiv0\operatorname*{mod}3,
\end{array}
\right.
\end{array}
\]
and their associated Dirichlet L-series:
\[%
\begin{array}
[c]{ccc}%
L_{j}(s)=L_{\chi_{j}}(s)=\sum\limits_{n=1}^{\infty}\dfrac{\chi_{j}(n)}{n^{s}%
}=\dfrac{1}{3^{s}}\left(  \chi_{j}(1)\zeta\left(  s,\frac{1}{3}\right)
+\chi_{j}(2)\zeta\left(  s,\frac{2}{3}\right)  \right)  , &  & j=0,1
\end{array}
\]
where $\zeta\left(  s,a\right)  $ is the Hurwitz zeta-function. By well-known
acceleration procedures, series of this nature can be evaluated to many
decimal places.

From the Euler product expressions
\[
L_{0}(s)=\prod_{p}\left(  1-\frac{\chi_{0}(p)}{p^{s}}\right)  ^{-1}%
=\prod_{p\equiv1\operatorname*{mod}3}\left(  1-\frac1{p^{s}}\right)
^{-1}\prod_{p\equiv2\operatorname*{mod}3}\left(  1-\frac1{p^{s}}\right)
^{-1},
\]
\[
L_{1}(s)=\prod_{p}\left(  1-\frac{\chi_{1}(p)}{p^{s}}\right)  ^{-1}%
=\prod_{p\equiv1\operatorname*{mod}3}\left(  1-\frac1{p^{s}}\right)
^{-1}\prod_{p\equiv2\operatorname*{mod}3}\left(  1+\frac1{p^{s}}\right)
^{-1},
\]
we obtain
\[
\frac12\ln\left(  \frac{L_{0}(s)}{L_{1}(s)}\right)  =\frac12\sum
_{p\equiv2\operatorname*{mod}3}\ln\left(  \frac{1+p^{-s}}{1-p^{-s}}\right)
=\sum_{n=0}^{\infty}\frac{P_{3,2}((2n+1)s)}{2n+1},
\]
\[
\frac12\ln\left(  \frac{L_{0}(s)L_{1}(s)}{L_{0}(2s)}\right)  =\frac
12\sum_{p\equiv1\operatorname*{mod}3}\ln\left(  \frac{1+p^{-s}}{1-p^{-s}%
}\right)  =\sum_{n=0}^{\infty}\frac{P_{3,1}((2n+1)s)}{2n+1}%
\]
and, again, by M\"obius inversion,
\[
P_{3,2}(s)=\frac12\sum_{n=0}^{\infty}\frac{\mu(2n+1)}{2n+1}\ln\left(
\frac{L_{0}((2n+1)s)}{L_{1}((2n+1)s)}\right)  ,
\]
\[
P_{3,1}(s)=\frac12\sum_{n=0}^{\infty}\frac{\mu(2n+1)}{2n+1}\ln\left(
\frac{L_{0}((2n+1)s)L_{1}((2n+1)s)}{L_{0}((4n+2)s)}\right)  .
\]
Of course, $L_{0}(s)=\zeta(s)(1-1/3^{s})$ and $L_{1}(s)=1-1/2^{s}%
+1/4^{s}-1/5^{s}+\cdots.$ Also, $P_{3,1}(s)\sim-\frac12\ln(s-1)$ and
$P_{3,2}(s)\sim-\frac12\ln(s-1)$ as $s\rightarrow1^{+}$.

Similar techniques involving characters modulo $k$ can be used to compute
constants of the form $\prod_{p\equiv\ell\operatorname*{mod}k}f(p)$, but for
brevity's sake we do not discuss these here.

\subsection{A Simple Example}

Let us compute the constant
\[
C=\prod_{p\equiv1\operatorname*{mod}3}\left(  1-\frac2{p(p+1)}\right)
=\prod_{p\equiv1\operatorname*{mod}3}\left(  \frac{(p-1)(p+2)}{(p+1)p}\right)
\]
that appears in section [\ref{Cbrt}]. It is easy to establish that
\[
\ln C=\sum_{p\equiv1\operatorname*{mod}3}\left(  \ln\left(  \frac{p-1}%
{p+1}\right)  +\ln\left(  1+\frac2p\right)  \right)  =\sum_{n\geq2}\frac
{c_{n}}nP_{3,1}(n)
\]
where $c_{n}=2^{n}-2$ when $n$ is odd and $c_{n}=-2^{n}$ when $n$ is even.
Since $c_{n}=O(2^{n})$ and $P_{3,1}(n)=O(7^{-n})$, it is more efficient to
compute directly the product up to a certain cutoff $p_{c}$. For example, if
we take $p_{c}=31$, we find
\[
C=\frac{3247695}{3430336}\prod_{\substack{p\equiv1\operatorname*{mod}3, \\p>31
}}\left(  1-\frac2{p(p+1)}\right)
\]
and consequently
\[
\ln C=\ln\frac{3247695}{3430336}+\sum_{n=2}^{\infty}\frac{c_{n}}n\left(
P_{3,1}(n)-\frac1{7^{n}}-\frac1{13^{n}}-\frac1{19^{n}}-\frac1{31^{n}}\right)
\]
enjoys much faster convergence because $P_{3,1}(n)-\frac1{7^{n}}-\frac
1{13^{n}}-\frac1{19^{n}}-\frac1{31^{n}}=O(37^{-n})$. The first few terms of
this series produce
\[%
\begin{tabular}
[c]{c|c}%
$n$ & \multicolumn{1}{c}{$C$}\\\hline
\multicolumn{1}{l|}{$2$} &
\multicolumn{1}{|l}{$0.94(09438379523896292195206...)$}\\
\multicolumn{1}{l|}{$3$} &
\multicolumn{1}{|l}{$0.94103(87732177050567463275...)$}\\
\multicolumn{1}{l|}{$4$} &
\multicolumn{1}{|l}{$0.941034(8096648041499806620...)$}\\
\multicolumn{1}{l|}{$5$} &
\multicolumn{1}{|l}{$0.94103494(70255355752383278...)$}\\
\multicolumn{1}{l|}{$10$} &
\multicolumn{1}{|l}{$0.94103494131953(43277214763...)$}\\
\multicolumn{1}{l|}{$15$} &
\multicolumn{1}{|l}{$0.941034941319535451790(3566...)$}%
\end{tabular}
\]
and only 15 terms are necessary to obtain 20 correct decimal places.

\section{Acknowledgements}

We thank G\'{e}rald Tenenbaum \& Jean-Marie De Koninck for their expertise in
the Selberg-Delange method, Pieter Moree for his help in evaluating a complex
residue, and David Wilson \&\ Benoit Cloitre for their many contributions to
Neil Sloane's sequence database. \ Our work is extended in \cite{FMS} and we
gratefully acknowledge Greg Martin for his mastery of the subject.

\begin{thebibliography}{99}                                                                                               %
\bibitem {Slbrg}A. Selberg, Note on a paper by L. G. Sathe, \textit{J. Indian
Math. Soc.} 18 (1954) 83-87; MR0067143 (16,676a).

\bibitem {Dlnge}H. Delange, Sur des formules de Atle Selberg, \textit{Acta
Arith.} 19 (1971) 105-146 (errata insert); MR0289432 (44 \#6623).

\bibitem {Tnbm}G. Tenenbaum, \textit{Introduction to Analytic and
Probabilistic Number Theory}, Cambridge Univ. Press, 1995, pp. 180--197, 257;
MR1342300 (97e:11005b).

\bibitem {Apstl}T. M. Apostol, \textit{Introduction to Analytic Number
Theory}, Springer-Verlag, 1976, pp. 55--62, 229; MR0434929 (55 \#7892).

\bibitem {Sec2}N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences,
A060594, A001221 and A034444.

\bibitem {Finch}S. R. Finch, Hafner-Sarnak-McCurley constant: Carefree
couples, \textit{Mathematical Constants}, Cambridge Univ. Press, 2003, pp.
110--112; MR2003519 (2004i:00001).

\bibitem {Sec3}Sloane, op. cit., A060839, A005088 and A115069.

\bibitem {Moree}P. Moree and H. J. J. te Riele, The hexagonal versus the
square lattice, \textit{Math. Comp}. 73 (2004) 451--473; preprint available
online at http://arxiv.org/abs/math.NT/0204332; MR2034132 (2005b:11155).

\bibitem {Sec4}Sloane, op. cit., A046073 and A070306.

\bibitem {Sec5}Sloane, op. cit., A087692 and A115070.

\bibitem {Sec6}Sloane, op. cit., A000188.

\bibitem {Brghn}K. A. Broughan, Restricted divisor sums, \textit{Acta Arith.}
101 (2002) 105--114; MR1880301 (2002k:11155).

\bibitem {Sec7}Sloane, op. cit., A000189 and A065473.

\bibitem {Sec8}Sloane, op. cit., A000224 and A105612.

\bibitem {Prmrs}E. J. F. Primrose, The number of quadratic residues
$\operatorname*{mod}m$, \textit{Math. Gaz.} v. 61 (1977) n. 415, 60--61;
MR0460223 (57 \#218).

\bibitem {Stngl}W. D. Stangl, Counting squares in $\mathbb{Z}_{n}$,
\textit{Math. Mag}. 69 (1996) 285--289.

\bibitem {Sec9}Sloane, op. cit., A046530, A046630, A046631, A046633 and A046635.

\bibitem {WS}E. Wilmer and O. Schirokauer, A note on Stephan's conjecture 25,
unpublished note (2004); available online at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.210.4011\&rep=rep1\&type=pdf.

\bibitem {Sec10}Sloane, op. cit., A034444, A087688, A087782, A000089 and A000086.

\bibitem {Fnch}S. R. Finch, Quadratic Dirichlet L-series:\ Primitive
characters, unpublished note (2005); available online at
http://www.people.fas.harvard.edu/\symbol{126}sfinch/.

\bibitem {Sec11}Sloane, op. cit., A007431, A114643, A114810 and A114811.

\bibitem {Sec12}Sloane, op. cit., A052273, A052274, A052275, A085310, A085311,
A085312, A085313, A085314 and A055653.

\bibitem {Frbrg}C.-E. Fr\"oberg, On the prime zeta function, \textit{Nordisk
Tidskr. Informationsbehandling (BIT)} 8 (1968) 187--202; MR0236123 (38 \#4421).

\bibitem {Cohen}H. Cohen, High precision computation of Hardy-Littlewood
constants, unpublished note (1999); available online at
http://www.ufr-mi.u-bordeaux.fr/\symbol{126}cohen/.

\bibitem {FMS}S. R. Finch, G. Martin and P. Sebah, Roots of unity and nullity
modulo $n$, \textit{Proc. Amer. Math. Soc. }138 (2010) 2729--2743; preprint
available online at http://www.math.ubc.ca/\symbol{126}gerg/index.shtml?list;
MR 2011h:11105.\newline%

\begin{tabular}
[c]{llllll}
& Steven Finch &  &  & Pascal Sebah & \\
& \textit{steven\_finch@harvard.edu} &  &  & \textit{PSebah@yahoo.fr} &
\end{tabular}

\end{thebibliography}


\end{document}
tcilatex.tex
% Macros for Scientific Word and Scientific WorkPlace 5.5 documents saved with the LaTeX filter.
% Copyright (C) 2005 Mackichan Software, Inc.

\typeout{TCILATEX Macros for Scientific Word and Scientific WorkPlace 5.5 <06 Oct 2005>.}
\typeout{NOTICE:  This macro file is NOT proprietary and may be 
freely copied and distributed.}
%
\makeatletter

%%%%%%%%%%%%%%%%%%%%%
% pdfTeX related.
\ifx\pdfoutput\relax\let\pdfoutput=\undefined\fi
\newcount\msipdfoutput
\ifx\pdfoutput\undefined
\else
 \ifcase\pdfoutput
 \else 
    \msipdfoutput=1
    \ifx\paperwidth\undefined
    \else
      \ifdim\paperheight=0pt\relax
      \else
        \pdfpageheight\paperheight
      \fi
      \ifdim\paperwidth=0pt\relax
      \else
        \pdfpagewidth\paperwidth
      \fi
    \fi
  \fi  
\fi

%%%%%%%%%%%%%%%%%%%%%
% FMTeXButton
% This is used for putting TeXButtons in the 
% frontmatter of a document. Add a line like
% \QTagDef{FMTeXButton}{101}{} to the filter 
% section of the cst being used. Also add a
% new section containing:
%     [f_101]
%     ALIAS=FMTexButton
%     TAG_TYPE=FIELD
%     TAG_LEADIN=TeX Button:
%
% It also works to put \defs in the preamble after 
% the \input tcilatex
\def\FMTeXButton#1{#1}
%
%%%%%%%%%%%%%%%%%%%%%%
% macros for time
\newcount\@hour\newcount\@minute\chardef\@x10\chardef\@xv60
\def\tcitime{
\def\@time{%
  \@minute\time\@hour\@minute\divide\@hour\@xv
  \ifnum\@hour<\@x 0\fi\the\@hour:%
  \multiply\@hour\@xv\advance\@minute-\@hour
  \ifnum\@minute<\@x 0\fi\the\@minute
  }}%

%%%%%%%%%%%%%%%%%%%%%%
% macro for hyperref and msihyperref
%\@ifundefined{hyperref}{\def\hyperref#1#2#3#4{#2\ref{#4}#3}}{}

\def\x@hyperref#1#2#3{%
   % Turn off various catcodes before reading parameter 4
   \catcode`\~ = 12
   \catcode`\$ = 12
   \catcode`\_ = 12
   \catcode`\# = 12
   \catcode`\& = 12
   \catcode`\% = 12
   \y@hyperref{#1}{#2}{#3}%
}

\def\y@hyperref#1#2#3#4{%
   #2\ref{#4}#3
   \catcode`\~ = 13
   \catcode`\$ = 3
   \catcode`\_ = 8
   \catcode`\# = 6
   \catcode`\& = 4
   \catcode`\% = 14
}

\@ifundefined{hyperref}{\let\hyperref\x@hyperref}{}
\@ifundefined{msihyperref}{\let\msihyperref\x@hyperref}{}




% macro for external program call
\@ifundefined{qExtProgCall}{\def\qExtProgCall#1#2#3#4#5#6{\relax}}{}
%%%%%%%%%%%%%%%%%%%%%%
%
% macros for graphics
%
\def\FILENAME#1{#1}%
%
\def\QCTOpt[#1]#2{%
  \def\QCTOptB{#1}
  \def\QCTOptA{#2}
}
\def\QCTNOpt#1{%
  \def\QCTOptA{#1}
  \let\QCTOptB\empty
}
\def\Qct{%
  \@ifnextchar[{%
    \QCTOpt}{\QCTNOpt}
}
\def\QCBOpt[#1]#2{%
  \def\QCBOptB{#1}%
  \def\QCBOptA{#2}%
}
\def\QCBNOpt#1{%
  \def\QCBOptA{#1}%
  \let\QCBOptB\empty
}
\def\Qcb{%
  \@ifnextchar[{%
    \QCBOpt}{\QCBNOpt}%
}
\def\PrepCapArgs{%
  \ifx\QCBOptA\empty
    \ifx\QCTOptA\empty
      {}%
    \else
      \ifx\QCTOptB\empty
        {\QCTOptA}%
      \else
        [\QCTOptB]{\QCTOptA}%
      \fi
    \fi
  \else
    \ifx\QCBOptA\empty
      {}%
    \else
      \ifx\QCBOptB\empty
        {\QCBOptA}%
      \else
        [\QCBOptB]{\QCBOptA}%
      \fi
    \fi
  \fi
}
\newcount\GRAPHICSTYPE
%\GRAPHICSTYPE 0 is for TurboTeX
%\GRAPHICSTYPE 1 is for DVIWindo (PostScript)
%%%(removed)%\GRAPHICSTYPE 2 is for psfig (PostScript)
\GRAPHICSTYPE=\z@
\def\GRAPHICSPS#1{%
 \ifcase\GRAPHICSTYPE%\GRAPHICSTYPE=0
   \special{ps: #1}%
 \or%\GRAPHICSTYPE=1
   \special{language "PS", include "#1"}%
%%%\or%\GRAPHICSTYPE=2
%%%  #1%
 \fi
}%
%
\def\GRAPHICSHP#1{\special{include #1}}%
%
% \graffile{ body }                                  %#1
%          { contentswidth (scalar)  }               %#2
%          { contentsheight (scalar) }               %#3
%          { vertical shift when in-line (scalar) }  %#4

\def\graffile#1#2#3#4{%
%%% \ifnum\GRAPHICSTYPE=\tw@
%%%  %Following if using psfig
%%%  \@ifundefined{psfig}{\input psfig.tex}{}%
%%%  \psfig{file=#1, height=#3, width=#2}%
%%% \else
  %Following for all others
  % JCS - added BOXTHEFRAME, see below
    \bgroup
	   \@inlabelfalse
       \leavevmode
       \@ifundefined{bbl@deactivate}{\def~{\string~}}{\activesoff}%
        \raise -#4 \BOXTHEFRAME{%
           \hbox to #2{\raise #3\hbox to #2{\null #1\hfil}}}%
    \egroup
}%
%
% A box for drafts
\def\draftbox#1#2#3#4{%
 \leavevmode\raise -#4 \hbox{%
  \frame{\rlap{\protect\tiny #1}\hbox to #2%
   {\vrule height#3 width\z@ depth\z@\hfil}%
  }%
 }%
}%
%
\newcount\@msidraft
\@msidraft=\z@
\let\nographics=\@msidraft
\newif\ifwasdraft
\wasdraftfalse

%  \GRAPHIC{ body }                                  %#1
%          { draft name }                            %#2
%          { contentswidth (scalar)  }               %#3
%          { contentsheight (scalar) }               %#4
%          { vertical shift when in-line (scalar) }  %#5
\def\GRAPHIC#1#2#3#4#5{%
   \ifnum\@msidraft=\@ne\draftbox{#2}{#3}{#4}{#5}%
   \else\graffile{#1}{#3}{#4}{#5}%
   \fi
}
%
\def\addtoLaTeXparams#1{%
    \edef\LaTeXparams{\LaTeXparams #1}}%
%
% JCS -  added a switch BoxFrame that can 
% be set by including X in the frame params.
% If set a box is drawn around the frame.

\newif\ifBoxFrame \BoxFramefalse
\newif\ifOverFrame \OverFramefalse
\newif\ifUnderFrame \UnderFramefalse

\def\BOXTHEFRAME#1{%
   \hbox{%
      \ifBoxFrame
         \frame{#1}%
      \else
         {#1}%
      \fi
   }%
}


\def\doFRAMEparams#1{\BoxFramefalse\OverFramefalse\UnderFramefalse\readFRAMEparams#1\end}%
\def\readFRAMEparams#1{%
 \ifx#1\end%
  \let\next=\relax
  \else
  \ifx#1i\dispkind=\z@\fi
  \ifx#1d\dispkind=\@ne\fi
  \ifx#1f\dispkind=\tw@\fi
  \ifx#1t\addtoLaTeXparams{t}\fi
  \ifx#1b\addtoLaTeXparams{b}\fi
  \ifx#1p\addtoLaTeXparams{p}\fi
  \ifx#1h\addtoLaTeXparams{h}\fi
  \ifx#1X\BoxFrametrue\fi
  \ifx#1O\OverFrametrue\fi
  \ifx#1U\UnderFrametrue\fi
  \ifx#1w
    \ifnum\@msidraft=1\wasdrafttrue\else\wasdraftfalse\fi
    \@msidraft=\@ne
  \fi
  \let\next=\readFRAMEparams
  \fi
 \next
 }%
%
%Macro for In-line graphics object
%   \IFRAME{ contentswidth (scalar)  }               %#1
%          { contentsheight (scalar) }               %#2
%          { vertical shift when in-line (scalar) }  %#3
%          { draft name }                            %#4
%          { body }                                  %#5
%          { caption}                                %#6


\def\IFRAME#1#2#3#4#5#6{%
      \bgroup
      \let\QCTOptA\empty
      \let\QCTOptB\empty
      \let\QCBOptA\empty
      \let\QCBOptB\empty
      #6%
      \parindent=0pt
      \leftskip=0pt
      \rightskip=0pt
      \setbox0=\hbox{\QCBOptA}%
      \@tempdima=#1\relax
      \ifOverFrame
          % Do this later
          \typeout{This is not implemented yet}%
          \show\HELP
      \else
         \ifdim\wd0>\@tempdima
            \advance\@tempdima by \@tempdima
            \ifdim\wd0 >\@tempdima
               \setbox1 =\vbox{%
                  \unskip\hbox to \@tempdima{\hfill\GRAPHIC{#5}{#4}{#1}{#2}{#3}\hfill}%
                  \unskip\hbox to \@tempdima{\parbox[b]{\@tempdima}{\QCBOptA}}%
               }%
               \wd1=\@tempdima
            \else
               \textwidth=\wd0
               \setbox1 =\vbox{%
                 \noindent\hbox to \wd0{\hfill\GRAPHIC{#5}{#4}{#1}{#2}{#3}\hfill}\\%
                 \noindent\hbox{\QCBOptA}%
               }%
               \wd1=\wd0
            \fi
         \else
            \ifdim\wd0>0pt
              \hsize=\@tempdima
              \setbox1=\vbox{%
                \unskip\GRAPHIC{#5}{#4}{#1}{#2}{0pt}%
                \break
                \unskip\hbox to \@tempdima{\hfill \QCBOptA\hfill}%
              }%
              \wd1=\@tempdima
           \else
              \hsize=\@tempdima
              \setbox1=\vbox{%
                \unskip\GRAPHIC{#5}{#4}{#1}{#2}{0pt}%
              }%
              \wd1=\@tempdima
           \fi
         \fi
         \@tempdimb=\ht1
         %\advance\@tempdimb by \dp1
         \advance\@tempdimb by -#2
         \advance\@tempdimb by #3
         \leavevmode
         \raise -\@tempdimb \hbox{\box1}%
      \fi
      \egroup%
}%
%
%Macro for Display graphics object
%   \DFRAME{ contentswidth (scalar)  }               %#1
%          { contentsheight (scalar) }               %#2
%          { draft label }                           %#3
%          { name }                                  %#4
%          { caption}                                %#5
\def\DFRAME#1#2#3#4#5{%
  \vspace\topsep
  \hfil\break
  \bgroup
     \leftskip\@flushglue
	 \rightskip\@flushglue
	 \parindent\z@
	 \parfillskip\z@skip
     \let\QCTOptA\empty
     \let\QCTOptB\empty
     \let\QCBOptA\empty
     \let\QCBOptB\empty
	 \vbox\bgroup
        \ifOverFrame 
           #5\QCTOptA\par
        \fi
        \GRAPHIC{#4}{#3}{#1}{#2}{\z@}%
        \ifUnderFrame 
           \break#5\QCBOptA
        \fi
	 \egroup
  \egroup
  \vspace\topsep
  \break
}%
%
%Macro for Floating graphic object
%   \FFRAME{ framedata f|i tbph x F|T }              %#1
%          { contentswidth (scalar)  }               %#2
%          { contentsheight (scalar) }               %#3
%          { caption }                               %#4
%          { label }                                 %#5
%          { draft name }                            %#6
%          { body }                                  %#7
\def\FFRAME#1#2#3#4#5#6#7{%
 %If float.sty loaded and float option is 'h', change to 'H'  (gp) 1998/09/05
  \@ifundefined{floatstyle}
    {%floatstyle undefined (and float.sty not present), no change
     \begin{figure}[#1]%
    }
    {%floatstyle DEFINED
	 \ifx#1h%Only the h parameter, change to H
      \begin{figure}[H]%
	 \else
      \begin{figure}[#1]%
	 \fi
	}
  \let\QCTOptA\empty
  \let\QCTOptB\empty
  \let\QCBOptA\empty
  \let\QCBOptB\empty
  \ifOverFrame
    #4
    \ifx\QCTOptA\empty
    \else
      \ifx\QCTOptB\empty
        \caption{\QCTOptA}%
      \else
        \caption[\QCTOptB]{\QCTOptA}%
      \fi
    \fi
    \ifUnderFrame\else
      \label{#5}%
    \fi
  \else
    \UnderFrametrue%
  \fi
  \begin{center}\GRAPHIC{#7}{#6}{#2}{#3}{\z@}\end{center}%
  \ifUnderFrame
    #4
    \ifx\QCBOptA\empty
      \caption{}%
    \else
      \ifx\QCBOptB\empty
        \caption{\QCBOptA}%
      \else
        \caption[\QCBOptB]{\QCBOptA}%
      \fi
    \fi
    \label{#5}%
  \fi
  \end{figure}%
 }%
%
%
%    \FRAME{ framedata f|i tbph x F|T }              %#1
%          { contentswidth (scalar)  }               %#2
%          { contentsheight (scalar) }               %#3
%          { vertical shift when in-line (scalar) }  %#4
%          { caption }                               %#5
%          { label }                                 %#6
%          { name }                                  %#7
%          { body }                                  %#8
%
%    framedata is a string which can contain the following
%    characters: idftbphxFT
%    Their meaning is as follows:
%             i, d or f : in-line, display, or floating
%             t,b,p,h   : LaTeX floating placement options
%             x         : fit contents box to contents
%             F or T    : Figure or Table. 
%                         Later this can expand
%                         to a more general float class.
%
%
\newcount\dispkind%

\def\makeactives{
  \catcode`\"=\active
  \catcode`\;=\active
  \catcode`\:=\active
  \catcode`\'=\active
  \catcode`\~=\active
}
\bgroup
   \makeactives
   \gdef\activesoff{%
      \def"{\string"}%
      \def;{\string;}%
      \def:{\string:}%
      \def'{\string'}%
      \def~{\string~}%
      %\bbl@deactivate{"}%
      %\bbl@deactivate{;}%
      %\bbl@deactivate{:}%
      %\bbl@deactivate{'}%
    }
\egroup

\def\FRAME#1#2#3#4#5#6#7#8{%
 \bgroup
 \ifnum\@msidraft=\@ne
   \wasdrafttrue
 \else
   \wasdraftfalse%
 \fi
 \def\LaTeXparams{}%
 \dispkind=\z@
 \def\LaTeXparams{}%
 \doFRAMEparams{#1}%
 \ifnum\dispkind=\z@\IFRAME{#2}{#3}{#4}{#7}{#8}{#5}\else
  \ifnum\dispkind=\@ne\DFRAME{#2}{#3}{#7}{#8}{#5}\else
   \ifnum\dispkind=\tw@
    \edef\@tempa{\noexpand\FFRAME{\LaTeXparams}}%
    \@tempa{#2}{#3}{#5}{#6}{#7}{#8}%
    \fi
   \fi
  \fi
  \ifwasdraft\@msidraft=1\else\@msidraft=0\fi{}%
  \egroup
 }%
%
% This macro added to let SW gobble a parameter that
% should not be passed on and expanded. 

\def\TEXUX#1{"texux"}

%
% Macros for text attributes:
%
\def\BF#1{{\bf {#1}}}%
\def\NEG#1{\leavevmode\hbox{\rlap{\thinspace/}{$#1$}}}%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
% macros for user - defined functions
\def\limfunc#1{\mathop{\rm #1}}%
\def\func#1{\mathop{\rm #1}\nolimits}%
% macro for unit names
\def\unit#1{\mathord{\thinspace\rm #1}}%

%
% miscellaneous 
\long\def\QQQ#1#2{%
     \long\expandafter\def\csname#1\endcsname{#2}}%
\@ifundefined{QTP}{\def\QTP#1{}}{}
\@ifundefined{QEXCLUDE}{\def\QEXCLUDE#1{}}{}
\@ifundefined{Qlb}{\def\Qlb#1{#1}}{}
\@ifundefined{Qlt}{\def\Qlt#1{#1}}{}
\def\QWE{}%
\long\def\QQA#1#2{}%
\def\QTR#1#2{{\csname#1\endcsname {#2}}}%
  %	Add aliases for the ulem package
  \let\QQQuline\uline
  \let\QQQsout\sout
  \let\QQQuuline\uuline
  \let\QQQuwave\uwave
  \let\QQQxout\xout
\long\def\TeXButton#1#2{#2}%
\long\def\QSubDoc#1#2{#2}%
\def\EXPAND#1[#2]#3{}%
\def\NOEXPAND#1[#2]#3{}%
\def\PROTECTED{}%
\def\LaTeXparent#1{}%
\def\ChildStyles#1{}%
\def\ChildDefaults#1{}%
\def\QTagDef#1#2#3{}%

% Constructs added with Scientific Notebook
\@ifundefined{correctchoice}{\def\correctchoice{\relax}}{}
\@ifundefined{HTML}{\def\HTML#1{\relax}}{}
\@ifundefined{TCIIcon}{\def\TCIIcon#1#2#3#4{\relax}}{}
\if@compatibility
  \typeout{Not defining UNICODE  U or CustomNote commands for LaTeX 2.09.}
\else
  \providecommand{\UNICODE}[2][]{\protect\rule{.1in}{.1in}}
  \providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
  \providecommand{\CustomNote}[3][]{\marginpar{#3}}
\fi

\@ifundefined{lambdabar}{
      \def\lambdabar{\errmessage{You have used the lambdabar symbol. 
                      This is available for typesetting only in RevTeX styles.}}
   }{}

%
% Macros for style editor docs
\@ifundefined{StyleEditBeginDoc}{\def\StyleEditBeginDoc{\relax}}{}
%
% Macros for footnotes
\def\QQfnmark#1{\footnotemark}
\def\QQfntext#1#2{\addtocounter{footnote}{#1}\footnotetext{#2}}
%
% Macros for indexing.
%
\@ifundefined{TCIMAKEINDEX}{}{\makeindex}%
%
% Attempts to avoid problems with other styles
\@ifundefined{abstract}{%
 \def\abstract{%
  \if@twocolumn
   \section*{Abstract (Not appropriate in this style!)}%
   \else \small 
   \begin{center}{\bf Abstract\vspace{-.5em}\vspace{\z@}}\end{center}%
   \quotation 
   \fi
  }%
 }{%
 }%
\@ifundefined{endabstract}{\def\endabstract
  {\if@twocolumn\else\endquotation\fi}}{}%
\@ifundefined{maketitle}{\def\maketitle#1{}}{}%
\@ifundefined{affiliation}{\def\affiliation#1{}}{}%
\@ifundefined{proof}{\def\proof{\noindent{\bfseries Proof. }}}{}%
\@ifundefined{endproof}{\def\endproof{\mbox{\ \rule{.1in}{.1in}}}}{}%
\@ifundefined{newfield}{\def\newfield#1#2{}}{}%
\@ifundefined{chapter}{\def\chapter#1{\par(Chapter head:)#1\par }%
 \newcount\c@chapter}{}%
\@ifundefined{part}{\def\part#1{\par(Part head:)#1\par }}{}%
\@ifundefined{section}{\def\section#1{\par(Section head:)#1\par }}{}%
\@ifundefined{subsection}{\def\subsection#1%
 {\par(Subsection head:)#1\par }}{}%
\@ifundefined{subsubsection}{\def\subsubsection#1%
 {\par(Subsubsection head:)#1\par }}{}%
\@ifundefined{paragraph}{\def\paragraph#1%
 {\par(Subsubsubsection head:)#1\par }}{}%
\@ifundefined{subparagraph}{\def\subparagraph#1%
 {\par(Subsubsubsubsection head:)#1\par }}{}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These symbols are not recognized by LaTeX
\@ifundefined{therefore}{\def\therefore{}}{}%
\@ifundefined{backepsilon}{\def\backepsilon{}}{}%
\@ifundefined{yen}{\def\yen{\hbox{\rm\rlap=Y}}}{}%
\@ifundefined{registered}{%
   \def\registered{\relax\ifmmode{}\r@gistered
                    \else$\m@th\r@gistered$\fi}%
 \def\r@gistered{^{\ooalign
  {\hfil\raise.07ex\hbox{$\scriptstyle\rm\text{R}$}\hfil\crcr
  \mathhexbox20D}}}}{}%
\@ifundefined{Eth}{\def\Eth{}}{}%
\@ifundefined{eth}{\def\eth{}}{}%
\@ifundefined{Thorn}{\def\Thorn{}}{}%
\@ifundefined{thorn}{\def\thorn{}}{}%
% A macro to allow any symbol that requires math to appear in text
\def\TEXTsymbol#1{\mbox{$#1$}}%
\@ifundefined{degree}{\def\degree{{}^{\circ}}}{}%
%
% macros for T3TeX files
\newdimen\theight
\@ifundefined{Column}{\def\Column{%
 \vadjust{\setbox\z@=\hbox{\scriptsize\quad\quad tcol}%
  \theight=\ht\z@\advance\theight by \dp\z@\advance\theight by \lineskip
  \kern -\theight \vbox to \theight{%
   \rightline{\rlap{\box\z@}}%
   \vss
   }%
  }%
 }}{}%
%
\@ifundefined{qed}{\def\qed{%
 \ifhmode\unskip\nobreak\fi\ifmmode\ifinner\else\hskip5\p@\fi\fi
 \hbox{\hskip5\p@\vrule width4\p@ height6\p@ depth1.5\p@\hskip\p@}%
 }}{}%
%
\@ifundefined{cents}{\def\cents{\hbox{\rm\rlap c/}}}{}%
\@ifundefined{tciLaplace}{\def\tciLaplace{\ensuremath{\mathcal{L}}}}{}%
\@ifundefined{tciFourier}{\def\tciFourier{\ensuremath{\mathcal{F}}}}{}%
\@ifundefined{textcurrency}{\def\textcurrency{\hbox{\rm\rlap xo}}}{}%
\@ifundefined{texteuro}{\def\texteuro{\hbox{\rm\rlap C=}}}{}%
\@ifundefined{euro}{\def\euro{\hbox{\rm\rlap C=}}}{}%
\@ifundefined{textfranc}{\def\textfranc{\hbox{\rm\rlap-F}}}{}%
\@ifundefined{textlira}{\def\textlira{\hbox{\rm\rlap L=}}}{}%
\@ifundefined{textpeseta}{\def\textpeseta{\hbox{\rm P\negthinspace s}}}{}%
%
\@ifundefined{miss}{\def\miss{\hbox{\vrule height2\p@ width 2\p@ depth\z@}}}{}%
%
\@ifundefined{vvert}{\def\vvert{\Vert}}{}%  %always translated to \left| or \right|
%
\@ifundefined{tcol}{\def\tcol#1{{\baselineskip=6\p@ \vcenter{#1}} \Column}}{}%
%
\@ifundefined{dB}{\def\dB{\hbox{{}}}}{}%        %dummy entry in column 
\@ifundefined{mB}{\def\mB#1{\hbox{$#1$}}}{}%   %column entry
\@ifundefined{nB}{\def\nB#1{\hbox{#1}}}{}%     %column entry (not math)
%
\@ifundefined{note}{\def\note{$^{\dag}}}{}%
%
\def\newfmtname{LaTeX2e}
% No longer load latexsym.  This is now handled by SWP, which uses amsfonts if necessary
%
\ifx\fmtname\newfmtname
  \DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm}
  \DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf}
  \DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt}
  \DeclareOldFontCommand{\bf}{\normalfont\bfseries}{\mathbf}
  \DeclareOldFontCommand{\it}{\normalfont\itshape}{\mathit}
  \DeclareOldFontCommand{\sl}{\normalfont\slshape}{\@nomath\sl}
  \DeclareOldFontCommand{\sc}{\normalfont\scshape}{\@nomath\sc}
\fi

%
% Greek bold macros
% Redefine all of the math symbols 
% which might be bolded	 - there are 
% probably others to add to this list

\def\alpha{{\Greekmath 010B}}%
\def\beta{{\Greekmath 010C}}%
\def\gamma{{\Greekmath 010D}}%
\def\delta{{\Greekmath 010E}}%
\def\epsilon{{\Greekmath 010F}}%
\def\zeta{{\Greekmath 0110}}%
\def\eta{{\Greekmath 0111}}%
\def\theta{{\Greekmath 0112}}%
\def\iota{{\Greekmath 0113}}%
\def\kappa{{\Greekmath 0114}}%
\def\lambda{{\Greekmath 0115}}%
\def\mu{{\Greekmath 0116}}%
\def\nu{{\Greekmath 0117}}%
\def\xi{{\Greekmath 0118}}%
\def\pi{{\Greekmath 0119}}%
\def\rho{{\Greekmath 011A}}%
\def\sigma{{\Greekmath 011B}}%
\def\tau{{\Greekmath 011C}}%
\def\upsilon{{\Greekmath 011D}}%
\def\phi{{\Greekmath 011E}}%
\def\chi{{\Greekmath 011F}}%
\def\psi{{\Greekmath 0120}}%
\def\omega{{\Greekmath 0121}}%
\def\varepsilon{{\Greekmath 0122}}%
\def\vartheta{{\Greekmath 0123}}%
\def\varpi{{\Greekmath 0124}}%
\def\varrho{{\Greekmath 0125}}%
\def\varsigma{{\Greekmath 0126}}%
\def\varphi{{\Greekmath 0127}}%

\def\nabla{{\Greekmath 0272}}
\def\FindBoldGroup{%
   {\setbox0=\hbox{$\mathbf{x\global\edef\theboldgroup{\the\mathgroup}}$}}%
}

\def\Greekmath#1#2#3#4{%
    \if@compatibility
        \ifnum\mathgroup=\symbold
           \mathchoice{\mbox{\boldmath$\displaystyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\textstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptscriptstyle\mathchar"#1#2#3#4$}}%
        \else
           \mathchar"#1#2#3#4% 
        \fi 
    \else 
        \FindBoldGroup
        \ifnum\mathgroup=\theboldgroup % For 2e
           \mathchoice{\mbox{\boldmath$\displaystyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\textstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptscriptstyle\mathchar"#1#2#3#4$}}%
        \else
           \mathchar"#1#2#3#4% 
        \fi     	    
	  \fi}

\newif\ifGreekBold  \GreekBoldfalse
\let\SAVEPBF=\pbf
\def\pbf{\GreekBoldtrue\SAVEPBF}%
%

\@ifundefined{theorem}{\newtheorem{theorem}{Theorem}}{}
\@ifundefined{lemma}{\newtheorem{lemma}[theorem]{Lemma}}{}
\@ifundefined{corollary}{\newtheorem{corollary}[theorem]{Corollary}}{}
\@ifundefined{conjecture}{\newtheorem{conjecture}[theorem]{Conjecture}}{}
\@ifundefined{proposition}{\newtheorem{proposition}[theorem]{Proposition}}{}
\@ifundefined{axiom}{\newtheorem{axiom}{Axiom}}{}
\@ifundefined{remark}{\newtheorem{remark}{Remark}}{}
\@ifundefined{example}{\newtheorem{example}{Example}}{}
\@ifundefined{exercise}{\newtheorem{exercise}{Exercise}}{}
\@ifundefined{definition}{\newtheorem{definition}{Definition}}{}


\@ifundefined{mathletters}{%
  %\def\theequation{\arabic{equation}}
  \newcounter{equationnumber}  
  \def\mathletters{%
     \addtocounter{equation}{1}
     \edef\@currentlabel{\theequation}%
     \setcounter{equationnumber}{\c@equation}
     \setcounter{equation}{0}%
     \edef\theequation{\@currentlabel\noexpand\alph{equation}}%
  }
  \def\endmathletters{%
     \setcounter{equation}{\value{equationnumber}}%
  }
}{}

%Logos
\@ifundefined{BibTeX}{%
    \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
                 T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}}{}%
\@ifundefined{AmS}%
    {\def\AmS{{\protect\usefont{OMS}{cmsy}{m}{n}%
                A\kern-.1667em\lower.5ex\hbox{M}\kern-.125emS}}}{}%
\@ifundefined{AmSTeX}{\def\AmSTeX{\protect\AmS-\protect\TeX\@}}{}%
%

% This macro is a fix to eqnarray
\def\@@eqncr{\let\@tempa\relax
    \ifcase\@eqcnt \def\@tempa{& & &}\or \def\@tempa{& &}%
      \else \def\@tempa{&}\fi
     \@tempa
     \if@eqnsw
        \iftag@
           \@taggnum
        \else
           \@eqnnum\stepcounter{equation}%
        \fi
     \fi
     \global\tag@false
     \global\@eqnswtrue
     \global\@eqcnt\z@\cr}


\def\TCItag{\@ifnextchar*{\@TCItagstar}{\@TCItag}}
\def\@TCItag#1{%
    \global\tag@true
    \global\def\@taggnum{(#1)}%
    \global\def\@currentlabel{#1}}
\def\@TCItagstar*#1{%
    \global\tag@true
    \global\def\@taggnum{#1}%
    \global\def\@currentlabel{#1}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\def\QATOP#1#2{{#1 \atop #2}}%
\def\QTATOP#1#2{{\textstyle {#1 \atop #2}}}%
\def\QDATOP#1#2{{\displaystyle {#1 \atop #2}}}%
\def\QABOVE#1#2#3{{#2 \above#1 #3}}%
\def\QTABOVE#1#2#3{{\textstyle {#2 \above#1 #3}}}%
\def\QDABOVE#1#2#3{{\displaystyle {#2 \above#1 #3}}}%
\def\QOVERD#1#2#3#4{{#3 \overwithdelims#1#2 #4}}%
\def\QTOVERD#1#2#3#4{{\textstyle {#3 \overwithdelims#1#2 #4}}}%
\def\QDOVERD#1#2#3#4{{\displaystyle {#3 \overwithdelims#1#2 #4}}}%
\def\QATOPD#1#2#3#4{{#3 \atopwithdelims#1#2 #4}}%
\def\QTATOPD#1#2#3#4{{\textstyle {#3 \atopwithdelims#1#2 #4}}}%
\def\QDATOPD#1#2#3#4{{\displaystyle {#3 \atopwithdelims#1#2 #4}}}%
\def\QABOVED#1#2#3#4#5{{#4 \abovewithdelims#1#2#3 #5}}%
\def\QTABOVED#1#2#3#4#5{{\textstyle 
   {#4 \abovewithdelims#1#2#3 #5}}}%
\def\QDABOVED#1#2#3#4#5{{\displaystyle 
   {#4 \abovewithdelims#1#2#3 #5}}}%
%
% Macros for text size operators:
%

\def\tint{\msi@int\textstyle\int}%
\def\tiint{\msi@int\textstyle\iint}%
\def\tiiint{\msi@int\textstyle\iiint}%
\def\tiiiint{\msi@int\textstyle\iiiint}%
\def\tidotsint{\msi@int\textstyle\idotsint}%
\def\toint{\msi@int\textstyle\oint}%


\def\tsum{\mathop{\textstyle \sum }}%
\def\tprod{\mathop{\textstyle \prod }}%
\def\tbigcap{\mathop{\textstyle \bigcap }}%
\def\tbigwedge{\mathop{\textstyle \bigwedge }}%
\def\tbigoplus{\mathop{\textstyle \bigoplus }}%
\def\tbigodot{\mathop{\textstyle \bigodot }}%
\def\tbigsqcup{\mathop{\textstyle \bigsqcup }}%
\def\tcoprod{\mathop{\textstyle \coprod }}%
\def\tbigcup{\mathop{\textstyle \bigcup }}%
\def\tbigvee{\mathop{\textstyle \bigvee }}%
\def\tbigotimes{\mathop{\textstyle \bigotimes }}%
\def\tbiguplus{\mathop{\textstyle \biguplus }}%
%
%
%Macros for display size operators:
%

\newtoks\temptoksa
\newtoks\temptoksb
\newtoks\temptoksc


\def\msi@int#1#2{%
 \def\@temp{{#1#2\the\temptoksc_{\the\temptoksa}^{\the\temptoksb}}}%   
 \futurelet\@nextcs
 \@int
}

\def\@int{%
   \ifx\@nextcs\limits
      \typeout{Found limits}%
      \temptoksc={\limits}%
	  \let\@next\@intgobble%
   \else\ifx\@nextcs\nolimits
      \typeout{Found nolimits}%
      \temptoksc={\nolimits}%
	  \let\@next\@intgobble%
   \else
      \typeout{Did not find limits or no limits}%
      \temptoksc={}%
      \let\@next\msi@limits%
   \fi\fi
   \@next   
}%

\def\@intgobble#1{%
   \typeout{arg is #1}%
   \msi@limits
}


\def\msi@limits{%
   \temptoksa={}%
   \temptoksb={}%
   \@ifnextchar_{\@limitsa}{\@limitsb}%
}

\def\@limitsa_#1{%
   \temptoksa={#1}%
   \@ifnextchar^{\@limitsc}{\@temp}%
}

\def\@limitsb{%
   \@ifnextchar^{\@limitsc}{\@temp}%
}

\def\@limitsc^#1{%
   \temptoksb={#1}%
   \@ifnextchar_{\@limitsd}{\@temp}%   
}

\def\@limitsd_#1{%
   \temptoksa={#1}%
   \@temp
}



\def\dint{\msi@int\displaystyle\int}%
\def\diint{\msi@int\displaystyle\iint}%
\def\diiint{\msi@int\displaystyle\iiint}%
\def\diiiint{\msi@int\displaystyle\iiiint}%
\def\didotsint{\msi@int\displaystyle\idotsint}%
\def\doint{\msi@int\displaystyle\oint}%

\def\dsum{\mathop{\displaystyle \sum }}%
\def\dprod{\mathop{\displaystyle \prod }}%
\def\dbigcap{\mathop{\displaystyle \bigcap }}%
\def\dbigwedge{\mathop{\displaystyle \bigwedge }}%
\def\dbigoplus{\mathop{\displaystyle \bigoplus }}%
\def\dbigodot{\mathop{\displaystyle \bigodot }}%
\def\dbigsqcup{\mathop{\displaystyle \bigsqcup }}%
\def\dcoprod{\mathop{\displaystyle \coprod }}%
\def\dbigcup{\mathop{\displaystyle \bigcup }}%
\def\dbigvee{\mathop{\displaystyle \bigvee }}%
\def\dbigotimes{\mathop{\displaystyle \bigotimes }}%
\def\dbiguplus{\mathop{\displaystyle \biguplus }}%

\if@compatibility\else
  % Always load amsmath in LaTeX2e mode
  \RequirePackage{amsmath}
\fi

\def\ExitTCILatex{\makeatother\endinput}

\bgroup
\ifx\ds@amstex\relax
   \message{amstex already loaded}\aftergroup\ExitTCILatex
\else
   \@ifpackageloaded{amsmath}%
      {\if@compatibility\message{amsmath already loaded}\fi\aftergroup\ExitTCILatex}
      {}
   \@ifpackageloaded{amstex}%
      {\if@compatibility\message{amstex already loaded}\fi\aftergroup\ExitTCILatex}
      {}
   \@ifpackageloaded{amsgen}%
      {\if@compatibility\message{amsgen already loaded}\fi\aftergroup\ExitTCILatex}
      {}
\fi
\egroup

%Exit if any of the AMS macros are already loaded.
%This is always the case for LaTeX2e mode.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOTE: The rest of this file is read only if in LaTeX 2.09 compatibility
% mode. This section is used to define AMS-like constructs in the
% event they have not been defined.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\typeout{TCILATEX defining AMS-like constructs in LaTeX 2.09 COMPATIBILITY MODE}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Macros to define some AMS LaTeX constructs when 
%  AMS LaTeX has not been loaded
% 
% These macros are copied from the AMS-TeX package for doing
% multiple integrals.
%
\let\DOTSI\relax
\def\RIfM@{\relax\ifmmode}%
\def\FN@{\futurelet\next}%
\newcount\intno@
\def\iint{\DOTSI\intno@\tw@\FN@\ints@}%
\def\iiint{\DOTSI\intno@\thr@@\FN@\ints@}%
\def\iiiint{\DOTSI\intno@4 \FN@\ints@}%
\def\idotsint{\DOTSI\intno@\z@\FN@\ints@}%
\def\ints@{\findlimits@\ints@@}%
\newif\iflimtoken@
\newif\iflimits@
\def\findlimits@{\limtoken@true\ifx\next\limits\limits@true
 \else\ifx\next\nolimits\limits@false\else
 \limtoken@false\ifx\ilimits@\nolimits\limits@false\else
 \ifinner\limits@false\else\limits@true\fi\fi\fi\fi}%
\def\multint@{\int\ifnum\intno@=\z@\intdots@                          %1
 \else\intkern@\fi                                                    %2
 \ifnum\intno@>\tw@\int\intkern@\fi                                   %3
 \ifnum\intno@>\thr@@\int\intkern@\fi                                 %4
 \int}%                                                               %5
\def\multintlimits@{\intop\ifnum\intno@=\z@\intdots@\else\intkern@\fi
 \ifnum\intno@>\tw@\intop\intkern@\fi
 \ifnum\intno@>\thr@@\intop\intkern@\fi\intop}%
\def\intic@{%
    \mathchoice{\hskip.5em}{\hskip.4em}{\hskip.4em}{\hskip.4em}}%
\def\negintic@{\mathchoice
 {\hskip-.5em}{\hskip-.4em}{\hskip-.4em}{\hskip-.4em}}%
\def\ints@@{\iflimtoken@                                              %1
 \def\ints@@@{\iflimits@\negintic@
   \mathop{\intic@\multintlimits@}\limits                             %2
  \else\multint@\nolimits\fi                                          %3
  \eat@}%                                                             %4
 \else                                                                %5
 \def\ints@@@{\iflimits@\negintic@
  \mathop{\intic@\multintlimits@}\limits\else
  \multint@\nolimits\fi}\fi\ints@@@}%
\def\intkern@{\mathchoice{\!\!\!}{\!\!}{\!\!}{\!\!}}%
\def\plaincdots@{\mathinner{\cdotp\cdotp\cdotp}}%
\def\intdots@{\mathchoice{\plaincdots@}%
 {{\cdotp}\mkern1.5mu{\cdotp}\mkern1.5mu{\cdotp}}%
 {{\cdotp}\mkern1mu{\cdotp}\mkern1mu{\cdotp}}%
 {{\cdotp}\mkern1mu{\cdotp}\mkern1mu{\cdotp}}}%
%
%
%  These macros are for doing the AMS \text{} construct
%
\def\RIfM@{\relax\protect\ifmmode}
\def\text{\RIfM@\expandafter\text@\else\expandafter\mbox\fi}
\let\nfss@text\text
\def\text@#1{\mathchoice
   {\textdef@\displaystyle\f@size{#1}}%
   {\textdef@\textstyle\tf@size{\firstchoice@false #1}}%
   {\textdef@\textstyle\sf@size{\firstchoice@false #1}}%
   {\textdef@\textstyle \ssf@size{\firstchoice@false #1}}%
   \glb@settings}

\def\textdef@#1#2#3{\hbox{{%
                    \everymath{#1}%
                    \let\f@size#2\selectfont
                    #3}}}
\newif\iffirstchoice@
\firstchoice@true
%
%These are the AMS constructs for multiline limits.
%
\def\Let@{\relax\iffalse{\fi\let\\=\cr\iffalse}\fi}%
\def\vspace@{\def\vspace##1{\crcr\noalign{\vskip##1\relax}}}%
\def\multilimits@{\bgroup\vspace@\Let@
 \baselineskip\fontdimen10 \scriptfont\tw@
 \advance\baselineskip\fontdimen12 \scriptfont\tw@
 \lineskip\thr@@\fontdimen8 \scriptfont\thr@@
 \lineskiplimit\lineskip
 \vbox\bgroup\ialign\bgroup\hfil$\m@th\scriptstyle{##}$\hfil\crcr}%
\def\Sb{_\multilimits@}%
\def\endSb{\crcr\egroup\egroup\egroup}%
\def\Sp{^\multilimits@}%
\let\endSp\endSb
%
%
%These are AMS constructs for horizontal arrows
%
\newdimen\ex@
\ex@.2326ex
\def\rightarrowfill@#1{$#1\m@th\mathord-\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill
 \mkern-6mu\mathord\rightarrow$}%
\def\leftarrowfill@#1{$#1\m@th\mathord\leftarrow\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill\mkern-6mu\mathord-$}%
\def\leftrightarrowfill@#1{$#1\m@th\mathord\leftarrow
\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill
 \mkern-6mu\mathord\rightarrow$}%
\def\overrightarrow{\mathpalette\overrightarrow@}%
\def\overrightarrow@#1#2{\vbox{\ialign{##\crcr\rightarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}%
\let\overarrow\overrightarrow
\def\overleftarrow{\mathpalette\overleftarrow@}%
\def\overleftarrow@#1#2{\vbox{\ialign{##\crcr\leftarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}%
\def\overleftrightarrow{\mathpalette\overleftrightarrow@}%
\def\overleftrightarrow@#1#2{\vbox{\ialign{##\crcr
   \leftrightarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}%
\def\underrightarrow{\mathpalette\underrightarrow@}%
\def\underrightarrow@#1#2{\vtop{\ialign{##\crcr$\m@th\hfil#1#2\hfil
  $\crcr\noalign{\nointerlineskip}\rightarrowfill@#1\crcr}}}%
\let\underarrow\underrightarrow
\def\underleftarrow{\mathpalette\underleftarrow@}%
\def\underleftarrow@#1#2{\vtop{\ialign{##\crcr$\m@th\hfil#1#2\hfil
  $\crcr\noalign{\nointerlineskip}\leftarrowfill@#1\crcr}}}%
\def\underleftrightarrow{\mathpalette\underleftrightarrow@}%
\def\underleftrightarrow@#1#2{\vtop{\ialign{##\crcr$\m@th
  \hfil#1#2\hfil$\crcr
 \noalign{\nointerlineskip}\leftrightarrowfill@#1\crcr}}}%
%%%%%%%%%%%%%%%%%%%%%

\def\qopnamewl@#1{\mathop{\operator@font#1}\nlimits@}
\let\nlimits@\displaylimits
\def\setboxz@h{\setbox\z@\hbox}


\def\varlim@#1#2{\mathop{\vtop{\ialign{##\crcr
 \hfil$#1\m@th\operator@font lim$\hfil\crcr
 \noalign{\nointerlineskip}#2#1\crcr
 \noalign{\nointerlineskip\kern-\ex@}\crcr}}}}

 \def\rightarrowfill@#1{\m@th\setboxz@h{$#1-$}\ht\z@\z@
  $#1\copy\z@\mkern-6mu\cleaders
  \hbox{$#1\mkern-2mu\box\z@\mkern-2mu$}\hfill
  \mkern-6mu\mathord\rightarrow$}
\def\leftarrowfill@#1{\m@th\setboxz@h{$#1-$}\ht\z@\z@
  $#1\mathord\leftarrow\mkern-6mu\cleaders
  \hbox{$#1\mkern-2mu\copy\z@\mkern-2mu$}\hfill
  \mkern-6mu\box\z@$}


\def\projlim{\qopnamewl@{proj\,lim}}
\def\injlim{\qopnamewl@{inj\,lim}}
\def\varinjlim{\mathpalette\varlim@\rightarrowfill@}
\def\varprojlim{\mathpalette\varlim@\leftarrowfill@}
\def\varliminf{\mathpalette\varliminf@{}}
\def\varliminf@#1{\mathop{\underline{\vrule\@depth.2\ex@\@width\z@
   \hbox{$#1\m@th\operator@font lim$}}}}
\def\varlimsup{\mathpalette\varlimsup@{}}
\def\varlimsup@#1{\mathop{\overline
  {\hbox{$#1\m@th\operator@font lim$}}}}

%
%Companion to stackrel
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}%
%
%
% These are AMS environments that will be defined to
% be verbatims if amstex has not actually been 
% loaded
%
%
\begingroup \catcode `|=0 \catcode `[= 1
\catcode`]=2 \catcode `\{=12 \catcode `\}=12
\catcode`\\=12 
|gdef|@alignverbatim#1\end{align}[#1|end[align]]
|gdef|@salignverbatim#1\end{align*}[#1|end[align*]]

|gdef|@alignatverbatim#1\end{alignat}[#1|end[alignat]]
|gdef|@salignatverbatim#1\end{alignat*}[#1|end[alignat*]]

|gdef|@xalignatverbatim#1\end{xalignat}[#1|end[xalignat]]
|gdef|@sxalignatverbatim#1\end{xalignat*}[#1|end[xalignat*]]

|gdef|@gatherverbatim#1\end{gather}[#1|end[gather]]
|gdef|@sgatherverbatim#1\end{gather*}[#1|end[gather*]]

|gdef|@gatherverbatim#1\end{gather}[#1|end[gather]]
|gdef|@sgatherverbatim#1\end{gather*}[#1|end[gather*]]


|gdef|@multilineverbatim#1\end{multiline}[#1|end[multiline]]
|gdef|@smultilineverbatim#1\end{multiline*}[#1|end[multiline*]]

|gdef|@arraxverbatim#1\end{arrax}[#1|end[arrax]]
|gdef|@sarraxverbatim#1\end{arrax*}[#1|end[arrax*]]

|gdef|@tabulaxverbatim#1\end{tabulax}[#1|end[tabulax]]
|gdef|@stabulaxverbatim#1\end{tabulax*}[#1|end[tabulax*]]


|endgroup
  

  
\def\align{\@verbatim \frenchspacing\@vobeyspaces \@alignverbatim
You are using the "align" environment in a style in which it is not defined.}
\let\endalign=\endtrivlist
 
\@namedef{align*}{\@verbatim\@salignverbatim
You are using the "align*" environment in a style in which it is not defined.}
\expandafter\let\csname endalign*\endcsname =\endtrivlist




\def\alignat{\@verbatim \frenchspacing\@vobeyspaces \@alignatverbatim
You are using the "alignat" environment in a style in which it is not defined.}
\let\endalignat=\endtrivlist
 
\@namedef{alignat*}{\@verbatim\@salignatverbatim
You are using the "alignat*" environment in a style in which it is not defined.}
\expandafter\let\csname endalignat*\endcsname =\endtrivlist




\def\xalignat{\@verbatim \frenchspacing\@vobeyspaces \@xalignatverbatim
You are using the "xalignat" environment in a style in which it is not defined.}
\let\endxalignat=\endtrivlist
 
\@namedef{xalignat*}{\@verbatim\@sxalignatverbatim
You are using the "xalignat*" environment in a style in which it is not defined.}
\expandafter\let\csname endxalignat*\endcsname =\endtrivlist




\def\gather{\@verbatim \frenchspacing\@vobeyspaces \@gatherverbatim
You are using the "gather" environment in a style in which it is not defined.}
\let\endgather=\endtrivlist
 
\@namedef{gather*}{\@verbatim\@sgatherverbatim
You are using the "gather*" environment in a style in which it is not defined.}
\expandafter\let\csname endgather*\endcsname =\endtrivlist


\def\multiline{\@verbatim \frenchspacing\@vobeyspaces \@multilineverbatim
You are using the "multiline" environment in a style in which it is not defined.}
\let\endmultiline=\endtrivlist
 
\@namedef{multiline*}{\@verbatim\@smultilineverbatim
You are using the "multiline*" environment in a style in which it is not defined.}
\expandafter\let\csname endmultiline*\endcsname =\endtrivlist


\def\arrax{\@verbatim \frenchspacing\@vobeyspaces \@arraxverbatim
You are using a type of "array" construct that is only allowed in AmS-LaTeX.}
\let\endarrax=\endtrivlist

\def\tabulax{\@verbatim \frenchspacing\@vobeyspaces \@tabulaxverbatim
You are using a type of "tabular" construct that is only allowed in AmS-LaTeX.}
\let\endtabulax=\endtrivlist

 
\@namedef{arrax*}{\@verbatim\@sarraxverbatim
You are using a type of "array*" construct that is only allowed in AmS-LaTeX.}
\expandafter\let\csname endarrax*\endcsname =\endtrivlist

\@namedef{tabulax*}{\@verbatim\@stabulaxverbatim
You are using a type of "tabular*" construct that is only allowed in AmS-LaTeX.}
\expandafter\let\csname endtabulax*\endcsname =\endtrivlist

% macro to simulate ams tag construct


% This macro is a fix to the equation environment
 \def\endequation{%
     \ifmmode\ifinner % FLEQN hack
      \iftag@
        \addtocounter{equation}{-1} % undo the increment made in the begin part
        $\hfil
           \displaywidth\linewidth\@taggnum\egroup \endtrivlist
        \global\tag@false
        \global\@ignoretrue   
      \else
        $\hfil
           \displaywidth\linewidth\@eqnnum\egroup \endtrivlist
        \global\tag@false
        \global\@ignoretrue 
      \fi
     \else   
      \iftag@
        \addtocounter{equation}{-1} % undo the increment made in the begin part
        \eqno \hbox{\@taggnum}
        \global\tag@false%
        $$\global\@ignoretrue
      \else
        \eqno \hbox{\@eqnnum}% $$ BRACE MATCHING HACK
        $$\global\@ignoretrue
      \fi
     \fi\fi
 } 

 \newif\iftag@ \tag@false
 
 \def\TCItag{\@ifnextchar*{\@TCItagstar}{\@TCItag}}
 \def\@TCItag#1{%
     \global\tag@true
     \global\def\@taggnum{(#1)}%
     \global\def\@currentlabel{#1}}
 \def\@TCItagstar*#1{%
     \global\tag@true
     \global\def\@taggnum{#1}%
     \global\def\@currentlabel{#1}}

  \@ifundefined{tag}{
     \def\tag{\@ifnextchar*{\@tagstar}{\@tag}}
     \def\@tag#1{%
         \global\tag@true
         \global\def\@taggnum{(#1)}}
     \def\@tagstar*#1{%
         \global\tag@true
         \global\def\@taggnum{#1}}
  }{}

\def\tfrac#1#2{{\textstyle {#1 \over #2}}}%
\def\dfrac#1#2{{\displaystyle {#1 \over #2}}}%
\def\binom#1#2{{#1 \choose #2}}%
\def\tbinom#1#2{{\textstyle {#1 \choose #2}}}%
\def\dbinom#1#2{{\displaystyle {#1 \choose #2}}}%

% Do not add anything to the end of this file.  
% The last section of the file is loaded only if 
% amstex has not been.
\makeatother
\endinput

math0604465.extracted_bib
\begin{thebibliography}{99}                                                                                               %
\bibitem {Slbrg}A. Selberg, Note on a paper by L. G. Sathe, \textit{J. Indian
Math. Soc.} 18 (1954) 83-87; MR0067143 (16,676a).

\bibitem {Dlnge}H. Delange, Sur des formules de Atle Selberg, \textit{Acta
Arith.} 19 (1971) 105-146 (errata insert); MR0289432 (44 \#6623).

\bibitem {Tnbm}G. Tenenbaum, \textit{Introduction to Analytic and
Probabilistic Number Theory}, Cambridge Univ. Press, 1995, pp. 180--197, 257;
MR1342300 (97e:11005b).

\bibitem {Apstl}T. M. Apostol, \textit{Introduction to Analytic Number
Theory}, Springer-Verlag, 1976, pp. 55--62, 229; MR0434929 (55 \#7892).

\bibitem {Sec2}N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences,
A060594, A001221 and A034444.

\bibitem {Finch}S. R. Finch, Hafner-Sarnak-McCurley constant: Carefree
couples, \textit{Mathematical Constants}, Cambridge Univ. Press, 2003, pp.
110--112; MR2003519 (2004i:00001).

\bibitem {Sec3}Sloane, op. cit., A060839, A005088 and A115069.

\bibitem {Moree}P. Moree and H. J. J. te Riele, The hexagonal versus the
square lattice, \textit{Math. Comp}. 73 (2004) 451--473; preprint available
online at http://arxiv.org/abs/math.NT/0204332; MR2034132 (2005b:11155).

\bibitem {Sec4}Sloane, op. cit., A046073 and A070306.

\bibitem {Sec5}Sloane, op. cit., A087692 and A115070.

\bibitem {Sec6}Sloane, op. cit., A000188.

\bibitem {Brghn}K. A. Broughan, Restricted divisor sums, \textit{Acta Arith.}
101 (2002) 105--114; MR1880301 (2002k:11155).

\bibitem {Sec7}Sloane, op. cit., A000189 and A065473.

\bibitem {Sec8}Sloane, op. cit., A000224 and A105612.

\bibitem {Prmrs}E. J. F. Primrose, The number of quadratic residues
$\operatorname*{mod}m$, \textit{Math. Gaz.} v. 61 (1977) n. 415, 60--61;
MR0460223 (57 \#218).

\bibitem {Stngl}W. D. Stangl, Counting squares in $\mathbb{Z}_{n}$,
\textit{Math. Mag}. 69 (1996) 285--289.

\bibitem {Sec9}Sloane, op. cit., A046530, A046630, A046631, A046633 and A046635.

\bibitem {WS}E. Wilmer and O. Schirokauer, A note on Stephan's conjecture 25,
unpublished note (2004); available online at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.210.4011\&rep=rep1\&type=pdf.

\bibitem {Sec10}Sloane, op. cit., A034444, A087688, A087782, A000089 and A000086.

\bibitem {Fnch}S. R. Finch, Quadratic Dirichlet L-series:\ Primitive
characters, unpublished note (2005); available online at
http://www.people.fas.harvard.edu/\symbol{126}sfinch/.

\bibitem {Sec11}Sloane, op. cit., A007431, A114643, A114810 and A114811.

\bibitem {Sec12}Sloane, op. cit., A052273, A052274, A052275, A085310, A085311,
A085312, A085313, A085314 and A055653.

\bibitem {Frbrg}C.-E. Fr\"oberg, On the prime zeta function, \textit{Nordisk
Tidskr. Informationsbehandling (BIT)} 8 (1968) 187--202; MR0236123 (38 \#4421).

\bibitem {Cohen}H. Cohen, High precision computation of Hardy-Littlewood
constants, unpublished note (1999); available online at
http://www.ufr-mi.u-bordeaux.fr/\symbol{126}cohen/.

\bibitem {FMS}S. R. Finch, G. Martin and P. Sebah, Roots of unity and nullity
modulo $n$, \textit{Proc. Amer. Math. Soc. }138 (2010) 2729--2743; preprint
available online at http://www.math.ubc.ca/\symbol{126}gerg/index.shtml?list;
MR 2011h:11105.\newline%

\begin{tabular}
[c]{llllll}
& Steven Finch &  &  & Pascal Sebah & \\
& \textit{steven\_finch@harvard.edu} &  &  & \textit{PSebah@yahoo.fr} &
\end{tabular}

\end{thebibliography}