<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amssymb, latexsym, amsfonts}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Asymptotically Exact Heuristics for Prime \\
\vskip .1in Divisors of the Sequence 
$\{a^k+b^k\}_{k=1}^{\infty}$}
\vskip 1cm
\large
Pieter Moree\footnote{Author's current address:
Max-Planck-Institut f\"ur Mathematik,
Vivatsgasse 7, D-53111 Bonn, Germany.\\
E-mail:  \href{mailto:moree@mpim-bonn.mpg.de}{\tt moree@mpim-bonn.mpg.de} .}
\\
Korteweg-de Vries Instituut\\
Plantage Muidergracht 24\\
1018 TV Amsterdam \\
The Netherlands \\
\href{mailto:moree@science.uva.nl}{\tt moree@science.uva.nl}\\
\end{center}

\vskip .2 in

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\textwidth=30cc
%\baselineskip=16pt
%\def\@ptsize{2}
%\setlength{\parsep}{2em}
%\setlength{\textheight}{9.5in}
%\setlength{\textwidth}{5.7in}
%\setlength{\topmargin}{-8ex}

\newtheorem{Thm}{Theorem}
\newtheorem{Conj}{Conjecture}
\newtheorem{Lem}{Lemma}
\newtheorem{remark}{Remark}
\newtheorem{Def}{Definition}
\newtheorem{Cor}{Corollary}
\newcommand{\pr}{{\bf Proof:}}
\newtheorem{Prop}{Proposition}
%\newcommand{\qed}{\hfill $\Box$}
\newcommand{\al}{\alpha}
\newcommand\bepsilon {\bar \epsilon}

%\renewcommand{\baselinestretch}{1.5}

\begin{abstract}
\noindent Let $N_{a,b}(x)$ count the number of primes $p\le x$ with $p$ 
dividing $a^k+b^k$ for some $k\ge 1$. It is known that 
$N_{a,b}(x)\sim c(a,b)x/\log x$ for some rational number $c(a,b)$ 
that depends in a rather intricate way on $a$ and $b$. A simple 
heuristic formula for $N_{a,b}(x)$ 
is proposed and it is proved that it is asymptotically exact, i.e.,
has the same asymptotic behavior as $N_{a,b}(x)$. Connections with
Ramanujan sums and character sums are discussed.
\end{abstract}

\section{Introduction}
Let $p$ be a prime (indeed, throughout this note the letter $p$ will be used to
indicate primes). Let $g$ be a non-zero rational number. By $\nu_p(g)$ we denote the exponent
of $p$ in the canonical factorization of $g$. If $\nu_p(g)=0$, 
then by ord$_g(p)$ we denote the
smallest positive integer $k$ such that $g^k\equiv 1 \ ({\rm mod~}p)$. If $k=p-1$, then
$g$ is said to be a {\it primitive root} mod $p$. If $g$ is a primitive root mod $p$, 
then $g^j$ is a primitive root mod $p$ iff gcd$(j,p-1)=1$. There are thus
$\varphi(p-1)$
 primitive roots mod $p$ in $(\mathbb Z/p\mathbb Z)^*$, where $\varphi$ denotes Euler's
 totient function.\\
\indent Let  $\pi(x)$ denote the number of primes $p\le x$ and 
$\pi_g(x)$ the number of primes $p\le x$ such that $g$ is a primitive root mod $p$. 
Artin's celebrated primitive root conjecture (1927) states that if $g$ is an
integer with $|g|&gt;1$ and $g$ is not a square, then for some positive rational number $c_g$
we have $\pi_g(x)\sim c_gA\pi(x)$, as $x$ tends to infinity. Here $A$ denotes
{\it Artin's constant} 
$$A=\prod_p\left(1-{1\over p(p-1)}\right)=0.3739558136\cdots$$ 
Hooley \cite{Hooley} established Artin's conjecture and
explicitly evaluated $c_g$, under
assumption of the Generalized Riemann Hypothesis (GRH).\\
\indent It is an old heuristic idea that the behavior of $\pi_g(x)$ should be mimicked
by $H_1(x)=\sum_{p\le x}\varphi(p-1)/(p-1)$, the idea being that the `probability' that $g$ is
a primitive root mod $p$ equals $\varphi(p-1)/(p-1)$ (since this is the density of
primitive roots in $(\mathbb Z/p\mathbb Z)^*$). Using the Siegel-Walfisz theorem 
(see Lemma \ref{walvis} below), it is
not difficult to show, unconditionally, that  $H_1(x)\sim A\pi(x)$. Although
true for many $g$ and also on average, it is however not always true, under GRH,
that $\pi_g(x)\sim H_1(x)$, i.e., the heuristic $H_1(x)$ is
not always asymptotically exact. Nevertheless, 
Moree \cite{M1} found a modification, $H_2(x)$, of the above heuristic $H_1(x)$
involving the Legendre symbol that is always asymptotically exact (assuming GRH).\\
\indent A prime $p$ is said to divide a sequence $S$ of integers, if it divides at least
one term of the sequence $S$ (see \cite{Ballot} for
a nice introduction to this topic). Several authors studied the problem of characterizing
(prime) divisors of the sequence $\{a^k+b^k\}_{k=1}^{\infty}$. Hasse \cite{Hasse} seems to have
been the first to consider the Dirichlet density of prime divisors of such
sequences. Later authors, e.g., Odoni \cite{Odoni}
and Wiertelak strengthened the analytic aspects of his work, with
the strongest result being due to Wiertelak \cite{Wiertelak}. In particular, Theorem 2 of
Wiertelak \cite{Wiertelak}, in the formulation of \cite{M0}, yields the following corollary  
(recall that Li$(x)=\int_2^x dt/\log t$ is the logarithmic integral):
\begin{Thm}
\label{oud}
Let $a$ and $b$ be non-zero integers. 
Let $N_{a,b}(x)$ count the number of primes $p\le x$ that divide some
term $a^k+b^k$ in the sequence $\{a^k+b^k\}_{k=1}^{\infty}$.
Put $r=a/b$. Assume that $r\ne \pm 1$.
Let $\lambda$ be the largest integer such that $|r|=u^{2^{\lambda}}$, with
$u$ a rational number. Let $\varepsilon={\rm sgn}(r)$ and
$L=\mathbb Q(\sqrt{u})$. We have
$$N_{a,b}(x)=\delta(r){\rm Li}(x)+O\left({x(\log \log x)^4\over \log^3 x}\right),$$
where the implied constant may depend on $a$ and $b$, and $\delta(r)$ is a
positive rational number that is given
in Table {\rm 1}.
\end{Thm}

\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$L$  &amp; $\lambda$ &amp; $\delta(r)$ if $\varepsilon=+1$ &amp; 
$\delta(r)$ if $\varepsilon=-1$ \\
\hline
$L\ne \mathbb Q(\sqrt{2})$  &amp; $\lambda\ge 0$ &amp; $2^{1-\lambda}/3$ &amp; 
$1-2^{-\lambda}/3$ \\
\hline
$L=\mathbb Q(\sqrt{2})$  &amp; $\lambda=0$ &amp; $17/24$ &amp; 
$17/24$ \\
\hline
$L=\mathbb Q(\sqrt{2})$  &amp; $\lambda=1$ &amp; $5/12$ &amp; 
$2/3$ \\
\hline
$L=\mathbb Q(\sqrt{2})$  &amp; $\lambda\ge 2$ &amp; $2^{-\lambda}/3$ &amp; 
$1-2^{-1-\lambda}/3$ \\
\hline
\end{tabular}
\end{center}
\caption{The value of $\delta(r)$}
\end{table}

Theorem \ref{oud} implies that if $a$
and $b$ are non-zero integers such 
 that $a\ne \pm b$, then asymptotically $N_{a,b}(x)\sim \delta(r)x/\log x$ with
$\delta(r)&gt;0$ (thus the constant $c(a,b)$ mentioned in the introduction equals
$\delta(r)$). In particular, 
the set of prime divisors of the sequence $\{a^k+b^k\}_{k=1}^{\infty}$ has a positive
natural density.\\
\indent A starting point in the proof of Theorem \ref{oud} is the observation that 
$p\nmid 2ab$ divides the sequence $\{a^k+b^k\}_{k=1}^{\infty}$ iff ord$_r(p)$ is 
even, where $r=a/b$. The condition that ord$_r(p)$ be even is weaker than the
condition that ord$_r(p)=p-1$ and now the analytic tools are strong enough to establish
an unconditional result.\\
\indent Note that $\delta(r)$ does not depend on $\varepsilon$ in case $\lambda=0$. For a `generic'
choice  of $a$ and $b$, $L$ will be different from $\mathbb Q(\sqrt{2})$ and $\lambda$ will
be zero and hence $\delta(a/b)=2/3$. It is not difficult to show \cite{M4} that the average
density of elements of even order in a finite field of prime cardinality also equals $2/3$.\\
\indent In this note analogs $H^{(1)}_{a,b}(x)$ and $H^{(2)}_{a,b}(x)$ of $H_1(x)$
and $H_2(x)$ will be introduced and it will be shown that $H^{(2)}_{a,b}(x)$ is
always asymptotically exact. This leads to the following main result 
(where $\pi(x;k,l)$ denotes the number of primes
$p\le x$ satisfying $p\equiv l \ ({\rm mod~}k)$ and $(*/p)$ 
denotes the Legendre symbol):
\begin{Thm}
\label{main}
Let $a$ and $b$ be non-negative natural numbers.
Put
$r=a/b$ and $\varepsilon={\rm sgn}(a/b)$. Assume that $r\ne \pm 1$. Let $h$ be the largest integer such
that $|r|=r_0^h$ for some $r_0\in \mathbb Q$ and $h\ge 1$.
Put $e=\nu_2(h)$. If $\varepsilon=1$, then
$$N_{a,b}(x)=\pi(x;2^{e+1},1)-2^{e+1}\sum_{p\le x,~(r_0/p)=1\atop \nu_2(p-1)&gt;e}2^{-\nu_2(p-1)}
+O\left({x(\log \log x)^4\over \log^3 x}\right),$$
and if $\varepsilon=-1$, then 
$$N_{a,b}(x)=\pi(x)-\sum_{p\le x,~(r_0/p)=-1\atop \nu_2(p-1)=e+1}1-2^{e+1}\sum_{p\le x,~(r_0/p)=1\atop 
\nu_2(p-1)&gt;e+1}2^{-\nu_2(p-1)}
+O\left({x(\log \log x)^4\over \log^3 x}\right),$$
where the
implied constants depend at most on $a$ and $b$. In the latter three sums it is required
in addition that $p\nmid 2ab$.
\end{Thm}
Numerical work, cf. Table 2, suggests that the main term in
Theorem \ref{main} approximates $N_{a,b}(x)$ better than $\delta(r){\rm Li}(x)$ (or
$\delta(r)\pi(x)$ for that matter). It also suggests that the 
error term $O(x(\log \log x)^4\log^{-3}x)$ is far from being sharp. Indeed,
assuming GRH one can prove a much better result.
\begin{Thm} 
\label{maingrh}
{\rm (GRH)}. The error term in both Theorem {\rm 1} and {\rm 2} is
of magnitude $\sqrt{x}\log^{\omega(d)+1}x$, where $\omega(d)$ denotes the number
of distinct prime divisors of $d$ and the implied constant depends at most
on $a$ and $b$.
\end{Thm} 
The result that, under GRH, we have 
\begin{equation}
\label{pietjeboy}
N_{a,b}(x)=\delta(r){\rm Li}(x)+
O(\sqrt{x}\log^{\omega(d)+1}x),
\end{equation}
was established by the author in
an earlier paper \cite{M5}.



\section{Preliminaries} 
The proof of Theorem \ref{main} requires a result from analytic number theory: the 
Siegel-Walfisz theorem, see e.g., \cite[Satz 4.8.3]{Prachar}. For notational convenience
we write $(a,b)$ instead of gcd$(a,b)$.
\begin{Lem} 
\label{walvis} 
Let $C&gt;0$ be arbitrary. There exists $c_1&gt;0$ such that
$$\pi(x;k,l)={{\rm Li}(x)\over \varphi(k)}+O(x e^{-c_1\sqrt{\log x}}),$$
uniformly for $1\le k\le \log^C x$, $(l,k)=1$, where the 
implied constant depends at most on $C$.
\end{Lem} 
\indent We will also make use of the Chebotarev density theorem, which we recall now. Let
$L/\mathbb Q$ be a finite Galois extension of degree $n_L$ and with discriminant $d_L$.
Let $\pi_1(x;L/\mathbb Q)$ denote the number of primes $p\le x$ such that $p$ splits
completely in $L/\mathbb Q$. The Chebotarev density theorem asserts that
\begin{equation}
\label{chebbieagain}
\pi_1(x;L/\mathbb Q)\sim {1\over n_L}{x\over \log x}.
\end{equation}
On GRH this can be made much more precise (see \cite[p. 133]{S}, cf. \cite{L}):
\begin{Lem} 
\label{chebbiesterk}
Assuming the RH for the Dedekind zeta function of $L$ one has
$$\pi_1(x;L/\mathbb Q)={{\rm Li}(x)\over n_L}+O\left({\sqrt{x}\over n_L}\log(|d_L|x^{n_L})\right).$$
\end{Lem}
Note that in case $L=\mathbb Q$ Lemma \ref{chebbiesterk} implies that
$\pi(x)={\rm Li}(x)+O(\sqrt{x}\log x)$, under RH. This result was first proved in 1901
by H. von Koch.\\
\indent We will also need an estimate for the discriminant of $K(\zeta_n)$ in terms of $n$
and $d_K$, the discriminant of $K$.
\begin{Lem}
\label{diskie}
We have $\log |d_{K(\zeta_n)}|\le \varphi(k)(n_K\log n + \log |d_K|)$.
\end{Lem}
{\it Proof}. If $L_1/\mathbb Q$ and $L_2/\mathbb Q$ are two extension fields and $L$ is
their compositum, then the associated discriminant (over $\mathbb Q$) satisfies
$d_L|d_{L_1}^{[L:L_1]}d_{L_2}^{[L:L_2]}$. From this and the obvious estimates
$[L:L_1]\le [L_2:\mathbb Q]$ and $[L:L_2]\le [L_1:\mathbb Q]$, we obtain the estimate
$\log |d_L| \le [L_2:\mathbb Q]\log |d_{L_1}|+[L_1:\mathbb Q]\log |d_{L_2}|$.
On using the well-known fact that the discriminant of $\mathbb Q(\zeta_n)$ is 
a divisor of $n^{\varphi(n)}$, the result then follows on taking
$L_1=\mathbb Q(\zeta_n)$ and $L_2=K$. \qed\\

Our two heuristics will be based on the following
elementary observation in group theory.
\begin{Lem}
\label{Eerste} $~$\\
\noindent {\rm 1)} Let $h\ge 1$ and $w\ge 0$ be integers. Let $G$ be a cyclic group of order $n$.
Let $G^h=\{g^h:g\in G\}$ and
$G_{w}^h=\{g^h:\nu_2({\rm ord}(g^h))=w\}$. We have
$\# G^h=n/(n,h)$ and $\# G_{0}^h=2^{-\nu_2(n/(n,h))}n/(n,h)$.
Furthermore, for $w\ge 1$, we have
\begin{equation}
\label{subtieler}
\#G_w^h=\begin{cases}
2^{w-1-\nu_2(n/(n,h))}n/(n,h), &amp; \text{if} \ \nu_2(n/(n,h))\ge w;\\
0, &amp; \text{otherwise}.
\end{cases}
\end{equation}
{\rm 2)} If $\nu_2(h)\ge \nu_2(n)$, then every element in $G^h$ has odd order.
If $\nu_2(h)&lt;\nu_2(n)$, then $G_0^h\subseteq G^{2h}$.\\
{\rm 3)} We have
$$G_1^{h}\subseteq 
\begin{cases}
G^h\backslash G^{2h}, &amp; \text{if} \ \nu_2(n)=\nu_2(h)+1; \\
G^{2h}, &amp; \text{if} \ \nu_2(n)&gt;\nu_2(h)+1.
\end{cases}$$
If $\nu_2(n)\le \nu_2(h)$, then $G_1^{h}$ is empty.
\end{Lem}
{\it Proof.} 1) Let $g_0$ be a generator of $G$. On noting that
$g_0^{m_1}=g_0^{m_2}$ iff $m_1\equiv m_2\ ({\rm mod~}n)$, the 
proof becomes a 
simple exercise in solving linear congruences. In this way one infers
that $G^h=\{g_0^{hk}~:~1\le k\le n/(n,h)\}$ and hence
$\# G^h=n/(n,h)$. Note that ord$(g_0^{hk})$ is the smallest positive integer
$m$ such that $n/(n,h)$ divides $mk$. Thus ord$(g_0^{hk})$ will be odd iff
$\nu_2(k)\ge \nu_2(n/(n,h))$. 
Using this observation we obtain that
\begin{equation}
\label{gnul}
G_{0}^h=\{g_0^{hk}~:~1\le k\le {n\over (n,h)},~\nu_2(k)\ge 
\nu_2({n\over (n,h)})\}
\end{equation}
and hence $\#G_{0}^h=2^{-\nu_2(n/(n,h))}n/(n,h)$. Similarly
$$G_{w}^h=\{g_0^{hk}~:~1\le k\le {n\over (n,h)},~\nu_2(k)=\nu_2({n\over (n,h)})-w\}$$
and hence we obtain (\ref{subtieler}).\\
2) If $\nu_2(h)\ge \nu_2(n)$, then $\# G_0^h=\# G^h$ by part 1 and hence
every element in $G^h$ has odd order. 
If $\nu_2(h)&lt;\nu_2(n)$, then using (\ref{gnul}) we infer that
$$G_0^h\subseteq \{g_0^{hm}:1\le m\le {n\over (n,h)},~\nu_2(m)\ge 1\}
=\{g_0^{2hk}:1\le k\le {n\over (n,2h)}\}=G^{2h},$$
where we have written $m=2k$ and used that $(n,2h)=2(n,h)$.\\
3) Similar to that of part 2. \qed\\

\noindent {\it Remark}.
Note that $G^h$ and $G_0^h$ with the induced group operation from
$G$ are actually subgroups of $G$.


\section{Two heuristic formulae for $N_{a,b}(x)$}

In this section we propose two heuristics for $N_{a,b}(x)$; one more
refined than the other. The starting point is the observation that
a prime $p\nmid 2ab$ divides the sequence $\{a^k+b^k\}_{k=1}^{\infty}$ if
and only if ord$_r(p)$ is even, where $r=a/b$. Let $h$
be the largest integer such that we can write $|r|=r_0^h$ with $r_0$ 
a rational number. Let $\varepsilon={\rm sgn}(r)$ and $e=\nu_2(h)$.\\
\indent We will use Lemma \ref{Eerste} in 
the case $G=G_p:=(\mathbb Z/p\mathbb Z)^*\cong \mathbb F_p^*$. 
The first heuristic approximation we consider is
$$K_{a,b}^{(1)}(x)=\sum_{p\le x,~p\nmid 2ab}{\# G_{p,(1-\varepsilon)/2}^h\over \# G_p^h},$$
where $K_{a,b}^{(1)}(x)$ is supposed to be an heuristic for the number of primes $p\le x$
such that ord$_r(p)$ is odd. From our results below it will follow that $\lim_{x\rightarrow \infty}
K_{a,b}^{(1)}(x)/\pi(x)$ exists. Note that in case $h=1$ this 
limit is the average density of elements
of odd order (if $\varepsilon=1$),
respectively of order congruent to $2 \ ({\rm mod~}4)$ (if
$\varepsilon=-1$). For a more detailed investigation of the average number of elements having
order $\equiv a \ ({\rm mod~}d)$, see  \cite{M4}.\\
\indent Suppose that $p\nmid 2ab$. By assumption $r\in \varepsilon G_p^h$. 
In the case $\varepsilon=1$, the latter set  has
$\# G_{p,0}^h$ elements having odd order and so, in some sense,
${\# G_{p,0}^h/\# G_p^h}$ is the probability that ord$_r(p)$ is
odd. This motivates the definition of $K_{a,b}^{(1)}(x)$ in case $\varepsilon=1$.
In case $\varepsilon=-1$ we use the observation that for $p$ is odd, $-r_0^h$ has
odd order iff $r_0^h$ has order congruent to $2 \ ({\rm mod~}4)$. Thus the
elements in $-G_p^h$ of odd order are precisely the elements having order 
$2 \ ({\rm mod~}4)$ in $G_p^h$ and hence have cardinality $\# G_{p,1}^h$. 
On using part 1 of Lemma \ref{Eerste} we infer that
$K_{a,b}^{(1)}(x)=\sum_{p\le x,~p\nmid 2ab}k_{a,b}^{(1)}(p)$ with
\begin{equation}
\label{lokaaleen}
k_{a,b}^{(1)}(p)=
\begin{cases}
(1+\varepsilon)/2, &amp; \text{if} \ \nu_2(p-1)\le e;\\
2^{e-\nu_2(p-1)},&amp; \text{if} \ \nu_2(p-1)&gt;e.
\end{cases}
\end{equation}
An
heuristic $H_{a,b}^{(1)}(x)$ for $N_{a,b}(x)$ is now obtained merely by setting
$$H_{a,b}^{(1)}(x)=\pi(x)-K_{a,b}^{(1)}(x).$$ 
Put $\omega(n)=\sum_{p|n}1$.
On using (\ref{lokaaleen}) we then
infer that
$$H_{a,b}^{(1)}(x)=\pi(x;2^{e+1},1)-2^{e}\sum_{p\le x\atop \nu_2(p-1)&gt;e}2^{-\nu_2(p-1)}+
O(\omega(ab)),$$ 
if $\varepsilon=1$
and $$H_{a,b}^{(1)}(x)=\pi(x)-2^{e}\sum_{p\le x\atop \nu_2(p-1)&gt;e}2^{-\nu_2(p-1)}
+O(\omega(ab)),$$ 
if $\varepsilon=-1$.\\
\indent In the context of (near) primitive roots it
is known that the analogs of $H_{a,b}^{(1)}(x)$ do not always, assuming
GRH, exhibit the correct 
asymptotic behavior, but that an appropriate `quadratic' heuristic, i.e.,
an heuristic taking into account Legendre symbols, always has the
correct asymptotic behavior \cite{M1, M2, M3} (in \cite{M3} 
the main result of \cite{M2} is proved in a different and much shorter way). With this in 
mind, we propose a second, more refined, heuristic: $H_{a,b}^{(2)}(x)$.\\
\indent If $\nu_p(r)=0$ we
can consider $|r|=r_0^h$ and $r_0$ as elements of $G_p$. 
We write $(r_0/p)=1$ if $r_0$ is a square in $G_p$ and $(r_0/p)=-1$ otherwise.\\
\indent First consider the case where $\varepsilon=1$. If
$\nu_2(p-1)\le e$, then $r$ has odd order by part 2 of Lemma \ref{Eerste}.
If $\nu_2(p-1) &gt; \nu_2(h)$ and $(r_0/p)=-1$, then $r\in G_p^h$, but
$r\not\in G_p^{2h}$ (by part 2 of Lemma \ref{Eerste} again). It then follows that $r$ has even order.
On the other hand, if $(r_0/p)=1$ then $r\in G_p^{2h}$. This suggests to take
$$K_{a,b}^{(2)}(x)=\sum_{p\le x,~\nu_2(p-1)\le e}1+\sum_{p\le x,~(r_0/p)=1\atop \nu_2(p-1)&gt;e}{\# G_{p,0}^h
\over \# G_p^{2h}},$$ where furthermore we require that $p\nmid 2ab$.
A similar argument, now using part 3 instead of part 2 of Lemma \ref{Eerste}, leads to the choice
$$K_{a,b}^{(2)}(x)=\sum_{p\le x,~(r_0/p)=-1\atop \nu_2(p-1)=e+1}{\# G_{p,1}^h
\over \# G_p^{2h}}+\sum_{p\le x,~(r_0/p)=1\atop \nu_2(p-1)&gt;e+1}{\# G_{p,1}^h
\over \# G_p^{2h}},$$
in case $\varepsilon=-1$, where again we furthermore require 
that $p\nmid 2ab$. We obtain $K_{a,b}^{(2)}(x)=\sum_{p\le x,~p\nmid 2ab}k_{a,b}^{(2)}(p)$, with
\begin{equation}
\label{lokaaltwee}
k_{a,b}^{(2)}(p)=
\begin{cases}
(1+\varepsilon)/2, &amp; \text{if} \ \nu_2(p-1)\le e;\\
(1+\varepsilon ({r_0\over p}))/2, &amp; \text{if} \ \nu_2(p-1)=e+1;\\
(1+({r_0\over p}))2^{e-\nu_2(p-1)}, &amp; \text{if} \  \nu_2(p-1)&gt;e+1.
\end{cases}
\end{equation}
Now we put $H_{a,b}^{(2)}(x)=\pi(x)-K_{a,b}^{(2)}(x)$ as before.
On invoking Lemma \ref{Eerste}, $H_{a,b}^{(2)}(x)$ can then be more explicitly written as
\begin{equation}
\label{heurieen} 
H_{a,b}^{(2)}(x)=\pi(x;2^{e+1},1)-2^{e+1}\sum_{p\le x,~(r_0/p)=1\atop \nu_2(p-1)&gt;e}2^{-\nu_2(p-1)}
+O(\omega(ab)),
\end{equation}
if $\varepsilon=1$ and
\begin{equation}
\label{heuritwee}
H_{a,b}^{(2)}(x)=\pi(x)-
\sum_{p\le x,~(r_0/p)=-1\atop \nu_2(p-1)=e+1}1-
2^{e+1}\sum_{p\le x,~(r_0/p)=1\atop \nu_2(p-1)&gt;e+1}2^{-\nu_2(p-1)}+O(\omega(ab)),
\end{equation}
if $\varepsilon=-1$.


\section{Asymptotic analysis of the heuristic formulae}
\subsection{Unconditional asymptotic analysis}
In this section we determine the unconditional asymptotic behavior of $H_{a,b}^{(1)}(x)$ and
$H_{a,b}^{(2)}(x)$. 
We adopt the notation from Theorem \ref{main} and in addition write $D$ for the
discriminant of $\mathbb Q(\sqrt{r_0})$. Note that $D&gt;0$.
\begin{Thm} 
\label{maintwee}
Let $A&gt;0$ be arbitrary. The implied constants below depend at most on $A$.\\
{\rm 1)} We have
$H_{a,b}^{(1)}(x)=\delta_1(r){\rm Li}(x)+O(x\log^{-A}x)+O(\omega(ab))$,
where $$\delta_1(r)=
\begin{cases}
2^{1-e}/3, &amp; \text{if} \ \varepsilon=+1;\\
1-2^{-e}/3, &amp; \text{if} \ \varepsilon=-1.
\end{cases} $$
In particular, if $L\ne \mathbb Q(\sqrt{2})$, then $H_{a,b}^{(1)}(x)$ is
an asymptotically exact heuristic for $N_{a,b}(x)$.\\
{\rm 2)}  We have
$H_{a,b}^{(2)}(x)=\delta(r){\rm Li}(x)+O(D^2x\log^{-A}x)+O(\omega(ab))$.
In particular, $H_{a,b}^{(2)}(x)$ is
an asymptotically exact heuristic for $N_{a,b}(x)$.
\end{Thm}
The proof of part 2 requires some facts from algebraic number theory, the proof of part 1 does
not even require that and is an easier variant of the proof of part 2 (and is
left to the interested reader). The proof of part 2 rests on a few lemmas.
\begin{Lem}
\label{voorgaande}
Let $n$ be a non-zero integer, 
$\zeta_n=e^{2\pi i/n}$, and $K=\mathbb Q(\sqrt{n})$ 
be a quadratic number field of discriminant $\Delta$.
Let $A&gt;1$ and $C&gt;0$ be positive real numbers. Then
$$\sum_{p\le x,~(n/p)=1\atop \nu_2(p-1)=k}1={\rm Li}(x)\left({1\over [K(\zeta_{2^k}):\mathbb Q]}
-{1\over [K(\zeta_{2^{k+1}}):\mathbb Q]}\right)+O\left({|\Delta|x\over \log^A x}\right),$$
uniformly in $k$ with $k$ satisfying $2^{k+3}|\Delta|\le \log^C x$, where 
the implied constant depends
at most on $A$ and $C$.
\end{Lem}
{\it Proof}. By quadratic reciprocity a prime $p$ satisfies $(n/p)=1$ iff $p$ is in a certain set of 
congruences classes modulo $4|\Delta|$. Thus the primes we are counting in our sum are precisely
the primes that belong to certain congruences classes modulo $2^{k+2}|\Delta|$, but do not belong
to certain congruence classes modulo $2^{k+3}|\Delta|$. The total number of congruence classes
involved is less than $8|\Delta|$. Now apply Lemma \ref{walvis}. This yields the result but with
an, as yet, unknown density.\\
\indent On the other hand, the primes $p$ that are counted are precisely the primes $p\le x$ that split
completely in the normal number field $K(\zeta_{2^k})$, but do not split
completely in the normal number field
$K(\zeta_{2^{k+1}})$. If $M$ is any normal extension then it is a consequence of Chebotarev's density
theorem (\ref{chebbieagain}) that the set of primes that split completely in $M$ has density $1/[M:\mathbb Q]$. On using
this, the proof is completed. \qed


\begin{Lem}
Let $m$ be fixed. With the notation as in the previous lemma we have
$$T_n(m;x)={\rm Li}(x)\sum_{k=m}^{\infty}
{1\over 2^k}\left({1\over [K(\zeta_{2^k}):\mathbb Q]}
-{1\over [K(\zeta_{2^{k+1}}):\mathbb Q]}\right)+O\left({\Delta^2x\over \log^A x}\right),$$
where the implied constant depends at most on $A$ and
$$T_n(m;x):=\sum_{p\le x,~(n/p)=1\atop \nu_2(p-1)\ge m}2^{-\nu_2(p-1)}.$$
\end{Lem}
{\it Proof}. We have
$$T_n(m;x)=\sum_{k=m}^{m_1}
\sum_{p\le x,~(n/p)=1\atop \nu_2(p-1)=k}2^{-k}+O({x\over 4^{m_1}}),$$
where we used the trivial bound $\sum_{p\le x,~\nu_2(p-1)\ge m_1}2^{-\nu_2(p-1)}=O({x/4^{m_1}})$.
Choose $m_1$ to be the largest integer such that $2^{m_1+3}|\Delta|\le \log^C x$. Apply
Lemma \ref{voorgaande} with any $C&gt;A/2$. It follows that
\begin{eqnarray}
T_n(m;x)&amp;=&amp; {\rm Li}(x)\sum_{k=m}^{m_1}
{1\over 2^k}\left({1\over [K(\zeta_{2^k}):\mathbb Q]}
-{1\over [K(\zeta_{2^{k+1}}):\mathbb Q]}\right)+O({x\over 4^{m_1}});\nonumber\cr
&amp;=&amp; {\rm Li}(x)\sum_{k=m}^{\infty}
{1\over 2^k}\left({1\over [K(\zeta_{2^k}):\mathbb Q]}-
{1\over [K(\zeta_{2^{k+1}}):\mathbb Q]}\right)+O({x\over 4^{m_1}}),\nonumber
\end{eqnarray}
where we used that $\varphi(2^k)\le [K(\zeta_{2^k}):\mathbb Q]\le 2\varphi(2^k)$. 
On noting that $O(x/4^{m_1})=O(\Delta^2x\log^{-A}x)$, the result follows. \qed


\begin{Lem}
\label{bijna}
We have $H_{a,b}^{(2)}(x)=\delta_2(r){\rm Li}(x)+O(D^2x\log^{-A}x)+O(\omega(ab))$, where
\begin{equation}
\label{pluseen}
\delta_2(r)={1\over 2^e}-2^{e+1}\sum_{k=e+1}^{\infty}{1\over 2^k}\left({1\over [L(\zeta_{2^k}):\mathbb Q]}
-{1\over [L(\zeta_{2^{k+1}}):\mathbb Q]}\right)
\end{equation}
if $\varepsilon=1$ and, in case $\varepsilon=-1$,
$$\delta_2(r)=1-{1\over 2^{e+1}}
+{1\over [L(\zeta_{2^{e+1}}):\mathbb Q]}-{1\over [L(\zeta_{2^{e+2}}):\mathbb Q]}$$
\begin{equation}
\label{plustwee}
-
{2^{e+1}}\sum_{k=e+2}^{\infty}{1\over 2^k}\left({1\over [L(\zeta_{2^k}):\mathbb Q]}
-{1\over [L(\zeta_{2^{k+1}}):\mathbb Q]}\right).
\end{equation}
\end{Lem}
{\it Proof}. This easily follows on combining the previous lemma 
with equation (\ref{heurieen}), respectively (\ref{heuritwee}). 
(Note that $L=\mathbb Q(\sqrt{u})=\mathbb Q(\sqrt{r_0})$.) \qed\\


\noindent {\it Remark}.
From (\ref{pluseen}) and (\ref{plustwee}) we infer that
$$\delta_2(-|r|)-\delta_2(|r|)=
1-{3\over 2^{e+1}}+{2\over [L(\zeta_{2^{e+1}}):\mathbb Q]}
-{2\over [L(\zeta_{2^{e+2}}):\mathbb Q]}.$$


\noindent The number $\delta_2(r)$ can be readily evaluated on using the following simple fact
from algebraic number theory:
\begin{Lem}
\label{graad}
Let $K$ be a real quadratic field.
Let $k\ge 1$. Then 
$$[K(\zeta_{2^k}):\mathbb Q]=\begin{cases}
2^k, &amp; \text{if} \ k\le 2 \text{or} K\ne \mathbb Q(\sqrt{2});\\
2^{k-1}, &amp; \text{if} \  k\ge 3  \text{and} K=\mathbb Q(\sqrt{2}).
\end{cases}
$$
\end{Lem}
{\it Proof}. If $K$ is a quadratic field other than $\mathbb Q(\sqrt{2})$ then there is an odd prime
that ramifies in it. This prime, however, does not ramify in $\mathbb Q(\zeta_{2^n})$, so in this
case $K$ and $\mathbb Q(\sqrt{2})$ are linearly disjoint.
Note that $\zeta_8+\zeta_8^{-1}=\sqrt{2}$ and hence $\mathbb Q(\sqrt{2})\subset \mathbb Q(\zeta_8)$.
Using the well-known result that $[\mathbb Q(\zeta_n):\mathbb Q]=\varphi(n)$, the result is then
easily completed. \qed\\


\noindent The result of this evaluation is stated below.
\begin{Lem}
We have $\delta_2(r)=\delta(r)$.
\end{Lem}

\noindent After all this preliminary work, it is straightforward to 
prove the two main results of this note:\\

\noindent {\it Proof of Theorem} \ref{maintwee}. 1) Left to the reader. 2) Combine the latter
lemma with Lemma \ref{bijna}. Comparison with Theorem \ref{oud} shows that
$H_{a,b}^{(2)}(x)\sim N_{a,b}(x)$ as $x\rightarrow \infty$ and thus $H_{a,b}^{(2)}(x)$ is
an asymptotically exact approximation of $N_{a,b}(x)$. \qed\\

\noindent {\it Proof of Theorem} \ref{main}. Combine part 2 of Theorem \ref{maintwee} 
(with any $A&gt;3$), Theorem \ref{oud}
and equations (\ref{heurieen}) and (\ref{heuritwee}). \qed

\subsection{Conditional asymptotic analysis}
In this section we redo the unconditional analysis under the assumption that
RH holds for all fields of the form $K(\zeta_{2^n})$ with $K$ quadratic or $K=\mathbb Q$. Let
us abbreviate this assumption by SRH (with S standing for `small'). 
\begin{Lem}
\label{voorgaande2}
{\rm (SRH)}. Let $n$ be a non-zero integer and $K=\mathbb Q(\sqrt{n})$ 
be a quadratic number field of discriminant $\Delta$.
Then
$$\sum_{p\le x,~(n/p)=1\atop \nu_2(p-1)=k}1={\rm Li}(x)\left({1\over [K(\zeta_{2^k}):\mathbb Q]}
-{1\over [K(\zeta_{2^{k+1}}):\mathbb Q]}\right)+O\left(\sqrt{x}[k\log 2+\log (|\Delta|x)]\right).$$
\end{Lem}
{\it Proof}. The proof follows the second part
of the proof in Lemma \ref{voorgaande}, but this time with the Chebotarev density theorem
as given by Lemma \ref{chebbiesterk}, rather than (\ref{chebbieagain}).  The terms
$\log|d_{K(\zeta_{2^m})}|$ involved (with $m=k$ and $m=k+1$) are estimated
using Lemma \ref{diskie}. \qed\\

\noindent By simply summing the right hand side in Lemma \ref{voorgaande2} from $k=m$
onwards, one obtains that, on SRH,
$$T_n(m;x)={\rm Li}(x)\sum_{k=m}^{\infty}
{1\over 2^k}\left({1\over [K(\zeta_{2^k}):\mathbb Q]}
-{1\over [K(\zeta_{2^{k+1}}):\mathbb Q]}\right)+O\left(\sqrt{x}\log(|\Delta|x)\right).$$
With these ingredients one obtains that on SRH we have that Theorem \ref{maintwee} holds
with error term $O(\sqrt{x}\log x)$, respectively $O(\sqrt{x}\log(|D|x))$  in part 1, 
respectively part 2. On using (\ref{pietjeboy}) the proof of Theorem \ref{maingrh}
is then easily completed. 

















 

\section{Two alternative formulations}
\subsection{An alternative formulation using Ramanujan sums}
Recall that the {\it Ramanujan sum} $c_n(m)$ is  defined as $\sum_{1\le k\le n,~(k,n)=1}e^{2\pi i km/n}$.
Alternatively one can write $c_n(m)={\rm Tr}_n(\zeta_n^m)$, where
by Tr$_n$ we denote the trace over the cyclotomic field $\mathbb Q(\zeta_n)$. It follows at
once from the properties of the trace that $c_n(m)=c_n((n,m))$. Since $\zeta_n^m$ is an algebraic integer, it follows that
$c_n(m)$ is an integer. The following result is known as {\it H\"older's identity}. 
\begin{Lem}[H\"older's identity]
\label{hoelderlin}
Let $\mu$ denote the M\"obius function. Then 
$$c_n(m)=\varphi(n){\mu({n\over (n,m)})\over \varphi({n\over (n,m)})}.$$
\end{Lem}
{\it Proof}. Write $v=(n,m)$. Note that $\zeta_n^m=\zeta_{n/v}^{m/v}$ and $(n/v,m/v)=1$. From this we obtain
$$c_n(m)={\rm Tr}_n(\zeta_n^m)={\varphi(n)\over \varphi({n\over v})}{\rm Tr}_{n\over v}(\zeta_{n\over v}^{m\over v})=
{\varphi(n)\over \varphi({n\over v})}{\rm Tr}_{n\over v}(\zeta_{n\over v}).$$
Note that the result follows if we show that Tr$_n(\zeta_n)=\mu(n)$.
Suppose that $v$ and $w$ are coprime integers. 
Noting that the set $$\{\zeta_{vw}^j:1\le j\le vw,~(j,vw)=1\}$$
equals the set $$\{\zeta_v^a\zeta_w^b:1\le a\le v,1\le b\le w,(a,v)=(b,w)=1\},$$ it is seen that
Tr$_{vw}(\zeta_{vw})={\rm Tr}_v(\zeta_v){\rm Tr}_w(\zeta_w)$ and that consequently Tr$_n(\zeta_n)$ is
a multiplicative function in $n$. The minimal polynomial over $\mathbb Q$, $m_{p^r}(X)$, of $\zeta_{p^r}$ 
is seen to be
$m_{p^r}(X)=(X^{p^r}-1)/(X^{p^{r-1}}-1)=\sum_{j=0}^{p-1}X^{p^{r-1}j}$ and hence Tr$_{p^r}(\zeta_{p^r})=\mu(p^r)$ and 
so, indeed, 
Tr$_n(\zeta_n)=\mu(n)$. \qed\\
 
\noindent For our purposes the following weak version of H\"older's identity will
suffice:
\begin{equation}
\label{zwak}
c_{2^v}(t)=\begin{cases}
0, &amp; \text{if} \ \nu_2(t)\le v-2; \\
-\varphi(2^v), &amp; \text{if} \ \nu_2(t)=v-1;\cr
\varphi(2^v), &amp; \text{if} \ \nu_2(t)\ge v.
\end{cases}
\end{equation}
Another elementary property of Ramanujan sums we need is that for arbitrary natural numbers $n$ and $m$
\begin{equation}
\label{indicator}
{1\over n}\sum_{d|n}c_d(m)=\begin{cases}
1, &amp; \text{if} \ n|m; \\
0, &amp; \text{otherwise} .
\end{cases}
\end{equation}
Suppose that $\nu_p(r)=0$, then ord$_r(p)[\mathbb F_p^*:\langle r \rangle]=p-1$. Note that ord$_r(p)$
is odd iff $2^{\nu_2(p-1)}|[\mathbb F_p^*:\langle r\rangle]$. Using identity (\ref{indicator}) it then
follows that
\begin{equation}
\label{schietop}
N_{a,b}(x)=\pi(x)-\sum_{p\le x,~p\nmid 2ab}2^{-\nu_2(p-1)}\sum_{v\le \nu_2(p-1)}c_{2^v}
([\mathbb F_p^*:\langle r\rangle])+O(\omega(ab)).
\end{equation}
The following lemma relates Ramanujan sums with our heuristics.
\begin{Lem} 
\label{puhpuh}
Let $a,b,\varepsilon$ and $e$ be as in Theorem {\rm \ref{main}}, 
$k_{a,b}^{(1)}(p)$ and $k_{a,b}^{(2)}(p)$ be as in {\rm (\ref{lokaaleen})}, respectively 
{\rm (\ref{lokaaltwee})}, and let $p\nmid 2ab$.\\
{\rm 1)} We have
$$2^{-\nu_2(p-1)}\sum_{v\le {\rm min}(\nu_2(p-1),e)}c_{2^{\nu}}([\mathbb F_p^*:\langle {r}\rangle])
=k_{a,b}^{(1)}(p).$$
{\rm 2)} We have $$2^{-\nu_2(p-1)}\sum_{v\le {\rm min}(\nu_2(p-1),e+1)}c_{2^{\nu}}([\mathbb F_p^*:\langle 
{r}\rangle])
=k_{a,b}^{(2)}(p).$$
\end{Lem}
\begin{Cor} 
\label{puhpuhpuh}
For $1\le j\le 2$ we have
$$\sum_{p\le x,~p\nmid 2ab}2^{-\nu_2(p-1)}
\sum_{v\le {\rm min}(\nu_2(p-1),e+j-1)}c_{2^{\nu}}([\mathbb F_p^*:\langle {r}\rangle])=K_{a,b}^{(j)}(x).$$
\end{Cor}
{\it Proof of Lemma} \ref{puhpuh}. 1) We consider the two cases $\nu_2(p-1)&gt;e$ and
$\nu_2(p-1)\le e$ separately.\\
-{\it The case} $\nu_2(p-1)&gt;e$. 
Note that $(\varepsilon r_0^h)^{p-1\over 2^e}\equiv 1 \ ({\rm mod~}p)$ and so 
$\nu_2([\mathbb F_p^*:\langle {r}\rangle])\ge e$. Hence the sum in the statement of the lemma reduces
to $$2^{-\nu_2(p-1)}\sum_{v\le e}\varphi(2^v)=
2^{e-\nu_2(p-1)}=k_{a,b}^{(1)}(p),$$
where (\ref{zwak}), (\ref{lokaaleen}) and the identity $\sum_{d|n}\varphi(d)=n$ are used.\\
-{\it The case} $\nu_2(p-1)\le e$. Note that
$$\nu_2([\mathbb F_p^*:\langle {r}\rangle])=
\begin{cases}
\nu_2(p-1)-1, &amp; \text{if} \  \varepsilon=-1;\\
\nu_2(p-1), &amp; \text{if} \ \varepsilon=1.
\end{cases}
$$
If $\epsilon=-1$, the sum under consideration equals
$$2^{-\nu_2(p-1)}[\sum_{v\le \nu_2(p-1)-1}\varphi(2^v)-\varphi(2^{\nu_2(p-1)})]=0={1+\varepsilon\over 2}.$$
If $\epsilon=1$, the sum under consideration equals 
$$2^{-\nu_2(p-1)}\sum_{v\le \nu_2(p-1)}\varphi(2^v)=1={1+\varepsilon\over 2}.$$ We thus infer that the sum
under consideration equals $(1+\varepsilon)/2=k_{a,b}^{(1)}(p)$.\\
2) We consider the three cases $\nu_2(p-1)\le e$, $\nu_2(p-1)=e+1$ and $\nu_2(p-1)&gt;e+1$
separately.\\
{\it -The case} $\nu_2(p-1)\le e$. The quantity under consideration agrees with that considered in part 1 
of this proof and by 
(\ref{lokaaltwee}) we obtain that $k_{a,b}^{(1)}(p)=(1+\varepsilon)/2=k_{a,b}^{(2)}(p)$.\\
-{\it The case} $\nu_2(p-1)=e+1$. Now 
$$\varepsilon^{p-1\over 2^{e+1}}=\varepsilon,~(r_0^h)^{p-1\over 2^{e+1}}\equiv 
({r_0\over p}) \ ({\rm mod~}p){\rm ~and~hence~}r^{p-1\over 2^{e+1}}=(\varepsilon r_0^h)^{p-1\over 2^{e+1}}\equiv \varepsilon({r_0\over p}) \ ({\rm mod~}p).$$
It follows that
$\nu_2([\mathbb F_p^*:\langle r\rangle ])\ge e+1$ if $\varepsilon({r_0\over p})=1$ and
$\nu_2([\mathbb F_p^*:\langle r\rangle])=e$ if $\varepsilon({r_0\over p})=-1$. Using (\ref{zwak}) the quantity
under consideration is reduced to
$$2^{-\nu_2(p-1)}\left(\sum_{v\le e}\varphi(2^v)+\varepsilon({r_0\over p})2^e\right)=
{1+\varepsilon({r_0\over p})
\over 2}.$$
By (\ref{lokaaltwee}) this equals $k_{a,b}^{(2)}(p)$.\\
-{\it The case}  $\nu_2(p-1)&gt;e+1$. Now $r^{(p-1)/2^{1+e}}\equiv ({r_0\over p}) \ ({\rm mod~}p)$. 
Proceeding as before
the quantity under consideration reduces to
$$2^{-\nu_2(p-1)}\left(\sum_{v\le e}\varphi(2^v)+
({r_0\over p})2^e\right)=2^{e-\nu_2(p-1)}(1+({r_0\over p})).$$
By (\ref{lokaaltwee}) this equals $k_{a,b}^{(2)}(p)$. \qed\\

\noindent Corollary \ref{puhpuhpuh} shows that if in the double sum in (\ref{schietop})
the summation 
is restricted to those $v$ satisfying in
addition $v\le e$, respectively $v\le e+1$, then $K_{a,b}^{(1)}(x)$, respectively $K_{a,b}^{(2)}(x)$
is obtained. This in combination with Theorems \ref{oud}, \ref{maingrh}
and \ref{maintwee} leads to the following theorem:
\begin{Thm}
\label{maindrie}
We have in the notation of Theorem {\rm \ref{main}},
$$N_{a,b}(x)=\pi(x)-\sum_{p\le x,~p\nmid 2ab}2^{-\nu_2(p-1)}\sum_{2^v|(p-1,2h)}c_{2^{\nu}}
([\mathbb F_p^*:\langle {r}\rangle])
+O\left({x(\log \log x)^4\over \log^3 x}\right),$$
and 
$$\sum_{p\le x,~p\nmid 2ab}2^{-\nu_2(p-1)}\sum_{e+2\le v\le \nu_2(p-1)}c_{2^{\nu}}
([\mathbb F_p^*:\langle {r}\rangle])=O\left({x(\log \log x)^4\over \log^3 x}\right),$$
where the implied constant depends at most on $a$ and $b$. Under GRH the above error
terms can be replaced by $O(\sqrt{x}\log^{\omega(d)+1}x)$.
\end{Thm}

{\it Remark}. Note that the 
inequality $v\le {\rm min}(\nu_2(p-1),e+1)$ is equivalent to $2^v|(p-1,2h)$.

\subsection{An alternative formulation involving character sums}
Let $G$ be a cyclic group of order $n$ and $g$ an element in 
$G$. It is not difficult to show that, for any $d|n$,
$\sum_{{\rm ord}(\chi)=d}\chi(g)=c_d([G:\langle g\rangle])$, where the
sum is over the characters $\chi$ of $G$ of order $d$. 
Using this and noting
that $\chi(r)=\chi(\varepsilon)\chi^h(r_0)$, equation (\ref{schietop}) can be rewritten as
\begin{equation}
\label{schietop2}
N_{a,b}(x)=\pi(x)-\sum_{p\le x,~p\nmid 2ab}2^{-\nu_2(p-1)}\sum_{{\rm
ord}(\chi)|2^{\nu_2(p-1)}}\chi(\varepsilon)\chi^h(r_0)
+O(\omega(ab)),
\end{equation}
where the sum is over all characters of $\mathbb F_p^*$ having order dividing $2^{\nu_2(p-1)}$.
Note that if $\chi$ is of order $2^v$, then $\chi^h$ is the trivial character  if $v\le e$ and a
quadratic character if $v=e+1$. If in the main term of (\ref{schietop2}) only those characters of order dividing
$h$ are retained, i.e., those for which $\chi^h$ is 
the trivial character, then $H_{a,b}^{(1)}(x)$ is obtained (this is a reformulation of
part 1 of Lemma \ref{puhpuh}) and hence, by part 1 of 
Theorem \ref{maintwee}, the na\"{\i}ve heuristic. If in (\ref{schietop2}) only those 
characters of order dividing
$2h$ are retained, i.e., those for which $\chi^h$ is 
the trivial or a quadratic character, then the 
asymptotically exact heuristic is obtained. 
The error term assertion in Theorem \ref{maindrie} can be reformulated as:
\begin{Prop}
We have
$$\sum_{p\le x,~p\nmid 2ab}2^{-\nu_2(p-1)}\sum_{2^{e+2}|{\rm ord}(\chi)|2^{\nu_2(p-1)}}
\chi(\varepsilon)\chi^h(r_0)=O\left({x(\log \log x)^4\over \log^3 x}\right),$$
where the implied constant depends at most on $a$ and $b$. Under GRH the above error
term can be replaced by $O(\sqrt{x}\log^{\omega(d)+1}x )$.
\end{Prop}
In the setting of near primitive roots it is already known
that for the main term of the counting function of (near) primitive roots only the contributions 
coming from characters that are either trivial or quadratic need to be included \cite{M2}. 

\section{Some numerical experiments}
Let $N'_{a,b}(x)$ denote the number of odd prime divisors $p\le x$ of the sequence 
$\{a^k+b^k\}_{k=1}^{\infty}$ and $\pi'(x)$ the number of odd primes not exceeding $x$.
We define
$${\rm min_{old}}=\min_{x\le 10^6}\{N'_{a,b}(x)-\delta({a\over b})\pi'(x)\}{\rm ~and~}
{\rm max_{old}}=\max_{x\le 10^6}\{N'_{a,b}(x)-\delta({a\over b})\pi'(x)\}.$$
Similarly we define $\min_{heur}$ and $\max_{heur}$, but with $\delta(a/b)\pi'(x)$
replaced by the main term in Theorem 2.\\
\indent Numerical work strongly suggests (cf. Table 2) that the main term in
Theorem 2 gives a better approximation to $N_{a,b}(x)$ than $\delta(r)\pi(x)$ (which
on its turn gives a better approximation that $\delta(r){\rm Li}(x)$).

\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
${\rm sequence}$  &amp; ${\rm min_{old}}$ &amp; ${\rm max_{old}}$ &amp; ${\rm min_{heur}}$ &amp; ${\rm max_{heur}}$ \\
\hline
$\{2^k+1\}_{k=1}^{\infty}$  &amp; $-56.416\cdots$ &amp; $46.958\cdots$ &amp; 
$-24.791\cdots$ &amp; $22.432\cdots$ \\
\hline
$\{4^k+1\}_{k=1}^{\infty}$  &amp; $-54.916\cdots $ &amp; $45.500\cdots$ &amp; 
$-11.328\cdots$ &amp; $38.466\cdots$\\
\hline
$\{16^k+1\}_{k=1}^{\infty}$  &amp; $-22.250\cdots$ &amp; $35.083\cdots$ &amp; 
$-2.785\cdots$ &amp; $44.571\cdots$\\
\hline
$\{9^k+1\}_{k=1}^{\infty}$  &amp; $-71.666\cdots$ &amp; $32.000\cdots$ &amp; 
$-6.237\cdots$ &amp; $41.006\cdots$\\
\hline
$\{(-2)^k+1\}_{k=1}^{\infty}$  &amp; $-33.833\cdots$ &amp; $32.041\cdots$ &amp; 
$-7.051\cdots$ &amp; $29.440\cdots$\\
\hline
$\{(-3)^k+1\}_{k=1}^{\infty}$  &amp; $-43.666\cdots$ &amp; $44.666\cdots$ &amp; 
$-6.514\cdots$ &amp; $39.951\cdots$\\
\hline
$\{(-4)^k+1\}_{k=1}^{\infty}$  &amp; $-49.000\cdots$ &amp; $45.333\cdots$ &amp; 
$-19.641\cdots$ &amp; $30.507\cdots$\\
\hline
\end{tabular}
\end{center}
\caption{The old approximation of $N'_{a,b}(x)$ versus the heuristic one}
\end{table}

\noindent The results in Table 2 were produced using the Maple package.

\section{Conclusion}
There is a na\"{\i}ve heuristic for $N_{a,b}(x)$ that in many, but not all, cases is asymptotically exact.
There is a quadratic modification of this heuristic involving the 
Legendre symbol that is
{\it always} asymptotically exact. The same phenomenon is observed (assuming GRH) in the setting of Artin's 
primitive root conjecture. Numerical experiments strongly suggests that the 
quadratic heuristic better approximates $N_{a,b}(x)$ than the main terms in 
earlier results.\\

\section{Acknowledgments}

I would
like to thank Peter Stevenhagen for pointing out that 
Lemma \ref{hoelderlin} follows easily using properties of the trace.
Since I am not aware of a proof 
along these lines in the literature, I
have included it here.

Thanks are also due to the referee for his/her extensive comments.


\begin{thebibliography}{99}
\bibitem{Ballot} C. Ballot, Density of 
prime divisors of linear recurrences, 
{\it Mem. Amer. Math. Soc.} {\bf 115} (1995), no. 551.

\bibitem{Hasse} H. Hasse, \"Uber die Dichte der Primzahlen $p$, f\"ur die eine 
vorgegebene ganzrationale Zahl $a\not=0$ von gerader
  bzw. ungerader Ordnung mod. $p$ ist, {\it Math. Ann.}  {\bf 166} (1966), 19--23. 

\bibitem{Hooley} C. Hooley, Artin's conjecture for primitive roots, 
{\it J. Reine Angew. Math.} {\bf 225} (1967), 209--220.

\bibitem{L} S. Lang, On the zeta function of number fields, 
{\it Invent. Math.} {\bf 12} (1971), 337--345.

\bibitem{M0} P. Moree, On the divisors of 
$a\sp k+b\sp k$, {\it Acta Arith.} {\bf 80} (1997), 197--212. 

\bibitem{M1} P. Moree, On primes in arithmetic progression having a 
prescribed primitive root, {\it J. Number Theory} {\bf 78} (1999), 85--98.

\bibitem{M2} P. Moree, Asymptotically exact heuristics for 
(near) primitive roots, {\it J. Number Theory} {\bf 83} (2000), 155--181. 

\bibitem{M3} P. Moree, Asymptotically exact heuristics for 
(near) primitive roots. II, {\it Japan. J. Math.} {\bf 29} (2003), 143--157.

\bibitem{M4} P. Moree, On the average number of elements in a finite field
with order or index in a prescribed residue class, 
 {\it Finite Fields Appl.}  {\bf 10} (2004), 438--463.

\bibitem{M5} P. Moree, On primes $p$ for which $d$ divides ord$_p(g)$, 
{\it Funct. Approx. Comment. Math.} {\bf 33} (2005), 85--95.

\bibitem{Odoni} R. W. K. Odoni, A conjecture of 
Krishnamurthy on decimal periods and some 
allied problems, {\it J. Number Theory} {\bf 13} (1981), 303--319. 

\bibitem{Prachar} K. Prachar, {\it Primzahlverteilung},
Springer, New York, 1957.

\bibitem{S} J.-P. Serre, Quelques applications du 
th\'eor\`eme de densit\'e de Chebotarev, 
{\it Inst. Hautes \'Etudes Sci. Publ. Math.} {\bf 54} (1981), 323--401.

\bibitem{Wiertelak} K. Wiertelak, On the density of some 
sets of primes. IV, {\it Acta Arith.} {\bf 43}  (1984),  177--190.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11N37; Secondary 11N69, 11R45.

\noindent \emph{Keywords: } primitive root, Chebotarev density theorem,
Dirichlet density.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 14 2005;
revised version received February 24 2006. 
Published in {\it Journal of Integer Sequences}, July 7 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>