Asymptotically Exact Heuristics for Prime Divisors of the Sequence {a^{k} + b^{k}}_{k=1}^{∞}

Pieter Moree^{1} Korteweg-de Vries Instituut Plantage Muidergracht 24 1018 TV Amsterdam The Netherlands

                     moree@science.uva.nl

Abstract Let N_{a,b}(x) count the number of primes p ≤ x with p dividing a^{k} + b^{k} for some k ≥ 1. It is known that N_{a,b}(x) ∼ 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.

1 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 ν_{p}(g) we denote the exponent of p in the canonical factorization of g. If ν_{p}(g) = 0, then by ord_{g}(p) we denote the smallest positive integer k such that g^{k} ≡ 1 (mod p). If k = p − 1, then g is said to be a 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 φ(p − 1) primitive roots mod p in (ℤ/pℤ)^{∗}, where φ denotes Euler’s totient function.

Let π(x) denote the number of primes p ≤ x and π_{g}(x) the number of primes p ≤ 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| > 1 and g is not a square, then for some positive rational number c_{g} we have π_{g}(x) ∼ c_{g}Aπ(x), as x tends to infinity. Here A denotes Artin’s constant

A = ∏_{p} (1 − \frac{1}{p(p − 1)}) = 0.3739558136 ⋯

1Author’s current address: Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Germany.

E-mail: moree@mpim-bonn.mpg.de .

Hooley [3] established Artin’s conjecture and explicitly evaluated c_{g}, under assumption of the Generalized Riemann Hypothesis (GRH).

It is an old heuristic idea that the behavior of π_{g}(x) should be mimicked by H_{1}(x) = ∑_{p≤x} φ(p − 1)/(p − 1), the idea being that the ‘probability’ that g is a primitive root mod p equals φ(p − 1)/(p − 1) (since this is the density of primitive roots in (ℤ/pℤ)^{∗}). Using the Siegel-Walfisz theorem (see Lemma 1 below), it is not difficult to show, unconditionally, that H_{1}(x) ∼ Aπ(x). Although true for many g and also on average, it is however not always true, under GRH, that π_{g}(x) ∼ H_{1}(x), i.e., the heuristic H_{1}(x) is not always asymptotically exact. Nevertheless, Moree [6] found a modification, H_{2}(x), of the above heuristic H_{1}(x) involving the Legendre symbol that is always asymptotically exact (assuming GRH).

A prime p is said to divide a sequence S of integers, if it divides at least one term of the sequence S (see [1] 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}^{∞}. Hasse [2] seems to have been the first to consider the Dirichlet density of prime divisors of such sequences. Later authors, e.g., Odoni [11] and Wiertelak strengthened the analytic aspects of his work, with the strongest result being due to Wiertelak [14]. In particular, Theorem 2 of Wiertelak [14], in the formulation of [5], yields the following corollary (recall that Li(x) = ∫_{2}^{x} dt/ log t is the logarithmic integral):

Theorem 1. Let a and b be non-zero integers. Let N_{a,b}(x) count the number of primes p ≤ x that divide some term a^{k} + b^{k} in the sequence {a^{k} + b^{k}}_{k=1}^{∞}. Put r = a/b. Assume that r ≠ ±1. Let λ be the largest integer such that |r| = u^{2^{λ}}, with u a rational number. Let ε = sgn(r) and L = ℚ(\sqrt{u}). We have

N_{a,b}(x) = δ(r)Li(x) + O (\frac{x(log log x)^{4}}{log^{3} x} ) ,

where the implied constant may depend on a and b, and δ(r) is a positive rational number that is given in Table 1.

\begin{matrix}L & λ & δ(r) if ε = +1 & δ(r) if ε = −1 \\ L ≠ ℚ(\sqrt{2}) & λ ≥ 0 & 2^{1−λ}/3 & 1 − 2^{−λ}/3 \\ L = ℚ(\sqrt{2}) & λ = 0 & 17/24 & 17/24 \\ L = ℚ(\sqrt{2}) & λ = 1 & 5/12 & 2/3 \\ L = ℚ(\sqrt{2}) & λ ≥ 2 & 2^{−λ}/3 & 1 − 2^{−1−λ}/3 \end{matrix}

Table 1: The value of δ(r)

Theorem 1 implies that if a and b are non-zero integers such that a ≠ ±b, then asymptotically N_{a,b}(x) ∼ δ(r)x/ log x with δ(r) > 0 (thus the constant c(a, b) mentioned in the introduction equals δ(r)). In particular, the set of prime divisors of the sequence {a^{k} +b^{k}}_{k=1}^{∞} has a positive natural density.

A starting point in the proof of Theorem 1 is the observation that p ∤ 2ab divides the sequence {a^{k} + b^{k}}_{k=1}^{∞} 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.

Note that δ(r) does not depend on ε in case λ = 0. For a ‘generic’ choice of a and b, L will be different from ℚ(\sqrt{2}) and λ will be zero and hence δ(a/b) = 2/3. It is not difficult to show [9] that the average density of elements of even order in a finite field of prime cardinality also equals 2/3.

In this note analogs H_{a,b}^{(1)}(x) and H_{a,b}^{(2)}(x) of H_{1}(x) and H_{2}(x) will be introduced and it will be shown that H_{a,b}^{(2)}(x) is always asymptotically exact. This leads to the following main result (where π(x; k, l) denotes the number of primes p ≤ x satisfying p ≡ l (mod k) and (∗/p) denotes the Legendre symbol):

Theorem 2. Let a and b be non-negative natural numbers. Put r = a/b and ε = sgn(a/b). Assume that r ≠ ±1. Let h be the largest integer such that |r| = r_{0}^{h} for some r_{0} ∈ ℚ and h ≥ 1. Put e = ν_{2}(h). If ε = 1, then

N_{a,b}(x) = π(x; 2^{e+1}, 1) − 2^{e+1} ∑_{{p≤x, (r_{0}/p)=1 \atop ν_{2}(p−1)>e}} 2^{−ν_{2}(p−1)} + O (\frac{x(log log x)^{4}}{log^{3} x} ) ,

and if ε = −1, then

N_{a,b}(x) = π(x) − ∑_{{p≤x, (r_{0}/p)=−1 \atop ν_{2}(p−1)=e+1}} 1 − 2^{e+1} ∑_{{p≤x, (r_{0}/p)=1 \atop ν_{2}(p−1)>e+1}} 2^{−ν_{2}(p−1)} + O (\frac{x(log log x)^{4}}{log^{3} x} ) ,

where the implied constants depend at most on a and b. In the latter three sums it is required in addition that p ∤ 2ab.

Numerical work, cf. Table 2, suggests that the main term in Theorem 2 approximates N_{a,b}(x) better than δ(r)Li(x) (or δ(r)π(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.

Theorem 3. (GRH). The error term in both Theorem 1 and 2 is of magnitude \sqrt{x} log^{ω(d)+1} x, where ω(d) denotes the number of distinct prime divisors of d and the implied constant depends at most on a and b.

The result that, under GRH, we have

N_{a,b}(x) = δ(r)Li(x) + O(\sqrt{x} log^{ω(d)+1} x),  (1)

was established by the author in an earlier paper [10].

2 Preliminaries

The proof of Theorem 2 requires a result from analytic number theory: the Siegel-Walfisz theorem, see e.g., [12, Satz 4.8.3]. For notational convenience we write (a, b) instead of gcd(a, b).

Lemma 1. Let C > 0 be arbitrary. There exists c_{1} > 0 such that

π(x; k, l) = \frac{Li(x)}{φ(k)} + O(xe^{−c_{1}\sqrt{log x}}),

uniformly for 1 ≤ k ≤ log^{C} x, (l, k) = 1, where the implied constant depends at most on C.

We will also make use of the Chebotarev density theorem, which we recall now. Let L/ℚ be a finite Galois extension of degree n_{L} and with discriminant d_{L}. Let π_{1}(x; L/ℚ) denote the number of primes p ≤ x such that p splits completely in L/ℚ. The Chebotarev density theorem asserts that

π_{1}(x; L/ℚ) ∼ \frac{1}{n_{L}} \frac{x}{log x}.  (2)

On GRH this can be made much more precise (see [13, p. 133], cf. [4]):

Lemma 2. Assuming the RH for the Dedekind zeta function of L one has

π_{1}(x; L/ℚ) = \frac{Li(x)}{n_{L}} + O (\frac{\sqrt{x}}{n_{L}} log(|d_{L}|x^{n_{L}})) .

Note that in case L = ℚ Lemma 2 implies that π(x) = Li(x) + O(\sqrt{x} log x), under RH. This result was first proved in 1901 by H. von Koch.

We will also need an estimate for the discriminant of K(ζ_{n}) in terms of n and d_{K}, the discriminant of K.

Lemma 3. We have log |d_{K(ζ_{n})}| ≤ φ(k)(n_{K} log n + log |d_{K}|).

Proof. If L_{1}/ℚ and L_{2}/ℚ are two extension fields and L is their compositum, then the associated discriminant (over ℚ) satisfies d_{L}|d_{L_{1}}^{[L:L_{1}]}d_{L_{2}}^{[L:L_{2}]}. From this and the obvious estimates [L : L_{1}] ≤ [L_{2} : ℚ] and [L : L_{2}] ≤ [L_{1} : ℚ], we obtain the estimate log |d_{L}| ≤ [L_{2} : ℚ] log |d_{L_{1}}| + [L_{1} : ℚ] log |d_{L_{2}}|. On using the well-known fact that the discriminant of ℚ(ζ_{n}) is a divisor of n^{φ(n)}, the result then follows on taking L_{1} = ℚ(ζ_{n}) and L_{2} = K.

Our two heuristics will be based on the following elementary observation in group theory.

Lemma 4.

1) Let h ≥ 1 and w ≥ 0 be integers. Let G be a cyclic group of order n. Let G^{h} = {g^{h} : g ∈ G} and G_{w}^{h} = {g^{h} : ν_{2}(ord(g^{h})) = w}. We have #G^{h} = n/(n, h) and #G_{0}^{h} = 2^{−ν_{2}(n/(n,h))}n/(n, h). Furthermore, for w ≥ 1, we have

#G_{w}^{h} = \begin{cases}2^{w−1−ν_{2}(n/(n,h))}n/(n, h), & if ν_{2}(n/(n, h)) ≥ w; \\ 0, & otherwise. \end{cases}  (3)

2) If ν_{2}(h) ≥ ν_{2}(n), then every element in G^{h} has odd order. If ν_{2}(h) < ν_{2}(n), then G_{0}^{h} ⊆ G^{2h}.

3) We have

G_{1}^{h} ⊆ \begin{cases}G^{h}\G^{2h}, & if ν_{2}(n) = ν_{2}(h) + 1; \\ G^{2h}, & if ν_{2}(n) > ν_{2}(h) + 1. \end{cases}

If ν_{2}(n) ≤ ν_{2}(h), then G_{1}^{h} is empty.

Proof. 1) Let g_{0} be a generator of G. On noting that g_{0}^{m_{1}} = g_{0}^{m_{2}} iff m_{1} ≡ m_{2} (mod n), the proof becomes a simple exercise in solving linear congruences. In this way one infers that G^{h} = {g_{0}^{hk} : 1 ≤ k ≤ 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 ν_{2}(k) ≥ ν_{2}(n/(n, h)). Using this observation we obtain that

G_{0}^{h} = \{g_{0}^{hk} : 1 ≤ k ≤ \frac{n}{(n, h)}, ν_{2}(k) ≥ ν_{2}(\frac{n}{(n, h)})\}  (4)

and hence #G_{0}^{h} = 2^{−ν_{2}(n/(n,h))}n/(n, h). Similarly

G_{w}^{h} = \{g_{0}^{hk} : 1 ≤ k ≤ \frac{n}{(n, h)}, ν_{2}(k) = ν_{2}(\frac{n}{(n, h)}) − w\}

and hence we obtain (3).

2) If ν_{2}(h) ≥ ν_{2}(n), then #G_{0}^{h} = #G^{h} by part 1 and hence every element in G^{h} has odd order. If ν_{2}(h) < ν_{2}(n), then using (4) we infer that

G_{0}^{h} ⊆ \{g_{0}^{hm} : 1 ≤ m ≤ \frac{n}{(n, h)}, ν_{2}(m) ≥ 1\} = \{g_{0}^{2hk} : 1 ≤ k ≤ \frac{n}{(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.

Remark. Note that G^{h} and G_{0}^{h} with the induced group operation from G are actually subgroups of G.

3 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 ∤ 2ab divides the sequence {a^{k} + b^{k}}_{k=1}^{∞} 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 ε = sgn(r) and e = ν_{2}(h).

We will use Lemma 4 in the case G = G_{p} := (ℤ/pℤ)^{∗} ≅ 𝔽_{p}^{∗}. The first heuristic approximation we consider is

K_{a,b}^{(1)}(x) = ∑_{p≤x, p∤2ab} \frac{#G_{p,(1−ε)/2}^{h}}{#G_{p}^{h}} ,

where K_{a,b}^{(1)}(x) is supposed to be an heuristic for the number of primes p ≤ x such that ord_{r}(p) is odd. From our results below it will follow that lim_{x→∞} K_{a,b}^{(1)}(x)/π(x) exists. Note that in case h = 1 this limit is the average density of elements of odd order (if ε = 1), respectively of order congruent to 2 (mod 4) (if ε = −1). For a more detailed investigation of the average number of elements having order ≡ a (mod d), see [9].

Suppose that p ∤ 2ab. By assumption r ∈ εG_{p}^{h}. In the case ε = 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 ε = 1. In case ε = −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 (mod 4). Thus the elements in −G_{p}^{h} of odd order are precisely the elements having order 2 (mod 4) in G_{p}^{h} and hence have cardinality #G_{p,1}^{h}. On using part 1 of Lemma 4 we infer that K_{a,b}^{(1)}(x) = ∑_{p≤x, p∤2ab} k_{a,b}^{(1)}(p) with

k_{a,b}^{(1)}(p) = \begin{cases}(1 + ε)/2, & if ν_{2}(p − 1) ≤ e; \\ 2^{e−ν_{2}(p−1)}, & if ν_{2}(p − 1) > e. \end{cases}  (5)

An heuristic H_{a,b}^{(1)}(x) for N_{a,b}(x) is now obtained merely by setting

H_{a,b}^{(1)}(x) = π(x) − K_{a,b}^{(1)}(x).

Put ω(n) = ∑_{p|n} 1. On using (5) we then infer that

H_{a,b}^{(1)}(x) = π(x; 2^{e+1}, 1) − 2^{e} ∑_{{p≤x \atop ν_{2}(p−1)>e}} 2^{−ν_{2}(p−1)} + O(ω(ab)),

if ε = 1 and

H_{a,b}^{(1)}(x) = π(x) − 2^{e} ∑_{{p≤x \atop ν_{2}(p−1)>e}} 2^{−ν_{2}(p−1)} + O(ω(ab)),

if ε = −1.

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 [6, 7, 8] (in [8] the main result of [7] 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).

If ν_{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.

First consider the case where ε = 1. If ν_{2}(p − 1) ≤ e, then r has odd order by part 2 of Lemma 4. If ν_{2}(p − 1) > ν_{2}(h) and (r_{0}/p) = −1, then r ∈ G_{p}^{h}, but r ∉ G_{p}^{2h} (by part 2 of Lemma 4 again). It then follows that r has even order. On the other hand, if (r_{0}/p) = 1 then r ∈ G_{p}^{2h}. This suggests to take

K_{a,b}^{(2)}(x) = ∑_{p≤x, ν_{2}(p−1)≤e} 1 + ∑_{{p≤x, (r_{0}/p)=1 \atop ν_{2}(p−1)>e}} \frac{#G_{p,0}^{h}}{#G_{p}^{2h}} ,

where furthermore we require that p ∤ 2ab. A similar argument, now using part 3 instead of part 2 of Lemma 4, leads to the choice

K_{a,b}^{(2)}(x) = ∑_{{p≤x, (r_{0}/p)=−1 \atop ν_{2}(p−1)=e+1}} \frac{#G_{p,1}^{h}}{#G_{p}^{2h}} + ∑_{{p≤x, (r_{0}/p)=1 \atop ν_{2}(p−1)>e+1}} \frac{#G_{p,1}^{h}}{#G_{p}^{2h}} ,

in case ε = −1, where again we furthermore require that p ∤ 2ab. We obtain K_{a,b}^{(2)}(x) = ∑_{p≤x, p∤2ab} k_{a,b}^{(2)}(p), with

k_{a,b}^{(2)}(p) = \begin{cases}(1 + ε)/2, & if ν_{2}(p − 1) ≤ e; \\ (1 + ε(\frac{r_{0}}{p}))/2, & if ν_{2}(p − 1) = e + 1; \\ (1 + (\frac{r_{0}}{p}))2^{e−ν_{2}(p−1)}, & if ν_{2}(p − 1) > e + 1. \end{cases}  (6)

Now we put H_{a,b}^{(2)}(x) = π(x) − K_{a,b}^{(2)}(x) as before. On invoking Lemma 4, H_{a,b}^{(2)}(x) can then be more explicitly written as

H_{a,b}^{(2)}(x) = π(x; 2^{e+1}, 1) − 2^{e+1} ∑_{{p≤x, (r_{0}/p)=1 \atop ν_{2}(p−1)>e}} 2^{−ν_{2}(p−1)} + O(ω(ab)),  (7)

if ε = 1 and

H_{a,b}^{(2)}(x) = π(x) − ∑_{{p≤x, (r_{0}/p)=−1 \atop ν_{2}(p−1)=e+1}} 1 − 2^{e+1} ∑_{{p≤x, (r_{0}/p)=1 \atop ν_{2}(p−1)>e+1}} 2^{−ν_{2}(p−1)} + O(ω(ab)),  (8)

if ε = −1.

4 Asymptotic analysis of the heuristic formulae

4.1 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 2 and in addition write D for the discriminant of ℚ(\sqrt{r_{0}}). Note that D > 0.

Theorem 4. Let A > 0 be arbitrary. The implied constants below depend at most on A.

1) We have H_{a,b}^{(1)}(x) = δ_{1}(r)Li(x) + O(x log^{−A} x) + O(ω(ab)), where

δ_{1}(r) = \begin{cases}2^{1−e}/3, & if ε = +1; \\ 1 − 2^{−e}/3, & if ε = −1. \end{cases}

In particular, if L ≠ ℚ(\sqrt{2}), then H_{a,b}^{(1)}(x) is an asymptotically exact heuristic for N_{a,b}(x).

2) We have H_{a,b}^{(2)}(x) = δ(r)Li(x) + O(D^{2}x log^{−A} x) + O(ω(ab)). In particular, H_{a,b}^{(2)}(x) is an asymptotically exact heuristic for N_{a,b}(x).

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.

Lemma 5. Let n be a non-zero integer, ζ_{n} = e^{2πi/n}, and K = ℚ(\sqrt{n}) be a quadratic number field of discriminant Δ. Let A > 1 and C > 0 be positive real numbers. Then

∑_{{p≤x, (n/p)=1 \atop ν_{2}(p−1)=k}} 1 = Li(x) (\frac{1}{[K(ζ_{2^{k}}) : ℚ]} − \frac{1}{[K(ζ_{2^{k+1}}) : ℚ]}) + O (\frac{|Δ|x}{log^{A} x}) ,

uniformly in k with k satisfying 2^{k+3}|Δ| ≤ log^{C} x, where the implied constant depends at most on A and C.

Proof. By quadratic reciprocity a prime p satisfies (n/p) = 1 iff p is in a certain set of congruences classes modulo 4|Δ|. Thus the primes we are counting in our sum are precisely the primes that belong to certain congruences classes modulo 2^{k+2}|Δ|, but do not belong to certain congruence classes modulo 2^{k+3}|Δ|. The total number of congruence classes involved is less than 8|Δ|. Now apply Lemma 1. This yields the result but with an, as yet, unknown density.

On the other hand, the primes p that are counted are precisely the primes p ≤ x that split completely in the normal number field K(ζ_{2^{k}}), but do not split completely in the normal number field K(ζ_{2^{k+1}}). If M is any normal extension then it is a consequence of Chebotarev’s density theorem (2) that the set of primes that split completely in M has density 1/[M : ℚ]. On using this, the proof is completed.

Lemma 6. Let m be fixed. With the notation as in the previous lemma we have

T_{n}(m; x) = Li(x) ∑_{k=m}^{∞} \frac{1}{2^{k}} (\frac{1}{[K(ζ_{2^{k}}) : ℚ]} − \frac{1}{[K(ζ_{2^{k+1}}) : ℚ]}) + O (\frac{Δ^{2}x}{log^{A} x}) ,

where the implied constant depends at most on A and

T_{n}(m; x) := ∑_{{p≤x, (n/p)=1 \atop ν_{2}(p−1)≥m}} 2^{−ν_{2}(p−1)}.

Proof. We have

T_{n}(m; x) = ∑_{k=m}^{m_{1}} ∑_{{p≤x, (n/p)=1 \atop ν_{2}(p−1)=k}} 2^{−k} + O(\frac{x}{4^{m_{1}}} ),

where we used the trivial bound ∑_{p≤x, ν_{2}(p−1)≥m_{1}} 2^{−ν_{2}(p−1)} = O(x/4^{m_{1}}). Choose m_{1} to be the largest integer such that 2^{m_{1}+3}|Δ| ≤ log^{C} x. Apply Lemma 5 with any C > A/2. It follows that

T_{n}(m; x) = Li(x) ∑_{k=m}^{m_{1}} \frac{1}{2^{k}} (\frac{1}{[K(ζ_{2^{k}}) : ℚ]} − \frac{1}{[K(ζ_{2^{k+1}}) : ℚ]}) + O(\frac{x}{4^{m_{1}}} );
= Li(x) ∑_{k=m}^{∞} \frac{1}{2^{k}} (\frac{1}{[K(ζ_{2^{k}}) : ℚ]} − \frac{1}{[K(ζ_{2^{k+1}}) : ℚ]}) + O(\frac{x}{4^{m_{1}}} ),

where we used that φ(2^{k}) ≤ [K(ζ_{2^{k}}) : ℚ] ≤ 2φ(2^{k}). On noting that O(x/4^{m_{1}}) = O(Δ^{2}x log^{−A} x), the result follows.

Lemma 7. We have H_{a,b}^{(2)}(x) = δ_{2}(r)Li(x) + O(D^{2}x log^{−A} x) + O(ω(ab)), where

δ_{2}(r) = \frac{1}{2^{e}} − 2^{e+1} ∑_{k=e+1}^{∞} \frac{1}{2^{k}} (\frac{1}{[L(ζ_{2^{k}}) : ℚ]} − \frac{1}{[L(ζ_{2^{k+1}}) : ℚ]})  (9)

if ε = 1 and, in case ε = −1,

δ_{2}(r) = 1 − \frac{1}{2^{e+1}} + \frac{1}{[L(ζ_{2^{e+1}}) : ℚ]} − \frac{1}{[L(ζ_{2^{e+2}}) : ℚ]}

−2^{e+1} ∑_{k=e+2}^{∞} \frac{1}{2^{k}} (\frac{1}{[L(ζ_{2^{k}}) : ℚ]} − \frac{1}{[L(ζ_{2^{k+1}}) : ℚ]}) .  (10)

Proof. This easily follows on combining the previous lemma with equation (7), respectively (8). (Note that L = ℚ(\sqrt{u}) = ℚ(\sqrt{r_{0}}).)

Remark. From (9) and (10) we infer that

δ_{2}(−|r|) − δ_{2}(|r|) = 1 − \frac{3}{2^{e+1}} + \frac{2}{[L(ζ_{2^{e+1}}) : ℚ]} − \frac{2}{[L(ζ_{2^{e+2}}) : ℚ]}.

The number δ_{2}(r) can be readily evaluated on using the following simple fact from algebraic number theory:

Lemma 8. Let K be a real quadratic field. Let k ≥ 1. Then

[K(ζ_{2^{k}}) : ℚ] = \begin{cases}2^{k}, & if k ≤ 2orK ≠ ℚ(\sqrt{2}); \\ 2^{k−1}, & if k ≥ 3andK = ℚ(\sqrt{2}). \end{cases}

Proof. If K is a quadratic field other than ℚ(\sqrt{2}) then there is an odd prime that ramifies in it. This prime, however, does not ramify in ℚ(ζ_{2^{n}}), so in this case K and ℚ(\sqrt{2}) are linearly disjoint. Note that ζ_{8} + ζ_{8}^{−1} = \sqrt{2} and hence ℚ(\sqrt{2}) ⊂ ℚ(ζ_{8}). Using the well-known result that [ℚ(ζ_{n}) : ℚ] = φ(n), the result is then easily completed.

The result of this evaluation is stated below.

Lemma 9. We have δ_{2}(r) = δ(r).

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

Proof of Theorem 4. 1) Left to the reader. 2) Combine the latter lemma with Lemma 7. Comparison with Theorem 1 shows that H_{a,b}^{(2)}(x) ∼ N_{a,b}(x) as x → ∞ and thus H_{a,b}^{(2)}(x) is an asymptotically exact approximation of N_{a,b}(x).

Proof of Theorem 2. Combine part 2 of Theorem 4 (with any A > 3), Theorem 1 and equations (7) and (8).

4.2 Conditional asymptotic analysis

In this section we redo the unconditional analysis under the assumption that RH holds for all fields of the form K(ζ_{2^{n}}) with K quadratic or K = ℚ. Let us abbreviate this assumption by SRH (with S standing for ‘small’).

Lemma 10. (SRH). Let n be a non-zero integer and K = ℚ(\sqrt{n}) be a quadratic number field of discriminant Δ. Then

∑_{{p≤x, (n/p)=1 \atop ν_{2}(p−1)=k}} 1 = Li(x) (\frac{1}{[K(ζ_{2^{k}}) : ℚ]} − \frac{1}{[K(ζ_{2^{k+1}}) : ℚ]}) + O (\sqrt{x}[k log 2 + log(|Δ|x)]) .

Proof. The proof follows the second part of the proof in Lemma 5, but this time with the Chebotarev density theorem as given by Lemma 2, rather than (2). The terms log |d_{K(ζ_{2^{m}})}| involved (with m = k and m = k + 1) are estimated using Lemma 3.

By simply summing the right hand side in Lemma 10 from k = m onwards, one obtains that, on SRH,

T_{n}(m; x) = Li(x) ∑_{k=m}^{∞} \frac{1}{2^{k}} (\frac{1}{[K(ζ_{2^{k}}) : ℚ]} − \frac{1}{[K(ζ_{2^{k+1}}) : ℚ]}) + O (\sqrt{x} log(|Δ|x)) .

With these ingredients one obtains that on SRH we have that Theorem 4 holds with error term O(\sqrt{x} log x), respectively O(\sqrt{x} log(|D|x)) in part 1, respectively part 2. On using (1) the proof of Theorem 3 is then easily completed.

5 Two alternative formulations

5.1 An alternative formulation using Ramanujan sums

Recall that the Ramanujan sum c_{n}(m) is defined as ∑_{1≤k≤n, (k,n)=1} e^{2πikm/n}. Alternatively one can write c_{n}(m) = Tr_{n}(ζ_{n}^{m}), where by Tr_{n} we denote the trace over the cyclotomic field ℚ(ζ_{n}). It follows at once from the properties of the trace that c_{n}(m) = c_{n}((n, m)). Since ζ_{n}^{m} is an algebraic integer, it follows that c_{n}(m) is an integer. The following result is known as Hölder’s identity.

Lemma 11 (Hölder’s identity). Let μ denote the Möbius function. Then

c_{n}(m) = φ(n)\frac{μ(\frac{n}{(n,m)})}{φ(\frac{n}{(n,m)})}.

Proof. Write v = (n, m). Note that ζ_{n}^{m} = ζ_{n/v}^{m/v} and (n/v, m/v) = 1. From this we obtain

c_{n}(m) = Tr_{n}(ζ_{n}^{m}) = \frac{φ(n)}{φ(\frac{n}{v})}Tr\frac{n}{v} (ζ \frac{m}{v} ; \frac{n}{v}) = \frac{φ(n)}{φ(\frac{n}{v})}Tr\frac{n}{v} (ζ\frac{n}{v}).

Note that the result follows if we show that Tr_{n}(ζ_{n}) = μ(n). Suppose that v and w are coprime integers. Noting that the set

{ζ_{vw}^{j} : 1 ≤ j ≤ vw, (j, vw) = 1}

equals the set

{ζ_{v}^{a}ζ_{w}^{b} : 1 ≤ a ≤ v, 1 ≤ b ≤ w, (a, v) = (b, w) = 1},

it is seen that Tr_{vw}(ζ_{vw}) = Tr_{v}(ζ_{v})Tr_{w}(ζ_{w}) and that consequently Tr_{n}(ζ_{n}) is a multiplicative function in n. The minimal polynomial over ℚ, m_{p^{r}}(X), of ζ_{p^{r}} is seen to be m_{p^{r}}(X) = (X^{p^{r}} − 1)/(X^{p^{r−1}} − 1) = ∑_{j=0}^{p−1} X^{p^{r−1}j} and hence Tr_{p^{r}}(ζ_{p^{r}}) = μ(p^{r}) and so, indeed, Tr_{n}(ζ_{n}) = μ(n).

For our purposes the following weak version of Hölder’s identity will suffice:

c_{2^{v}}(t) = \begin{cases}0, & if ν_{2}(t) ≤ v − 2; \\ −φ(2^{v}), & if ν_{2}(t) = v − 1; \\ φ(2^{v}), & if ν_{2}(t) ≥ v. \end{cases}  (11)

Another elementary property of Ramanujan sums we need is that for arbitrary natural numbers n and m

\frac{1}{n} ∑_{d|n} c_{d}(m) = \begin{cases}1, & if n|m; \\ 0, & otherwise. \end{cases}  (12)

Suppose that ν_{p}(r) = 0, then ord_{r}(p)[𝔽_{p}^{∗} : ⟨r⟩] = p − 1. Note that ord_{r}(p) is odd iff 2^{ν_{2}(p−1)}|[𝔽_{p}^{∗} : ⟨r⟩]. Using identity (12) it then follows that

N_{a,b}(x) = π(x) − ∑_{p≤x, p∤2ab}2^{−ν_{2}(p−1)} ∑_{v≤ν_{2}(p−1)} c_{2^{v}}([𝔽_{p}^{∗} : ⟨r⟩]) + O(ω(ab)).  (13)

The following lemma relates Ramanujan sums with our heuristics.

Lemma 12. Let a, b, ε and e be as in Theorem 2, k_{a,b}^{(1)}(p) and k_{a,b}^{(2)}(p) be as in (5), respectively (6), and let p ∤ 2ab.

1) We have

2^{−ν_{2}(p−1)} ∑_{v≤min(ν_{2}(p−1),e)} c_{2^{ν}}([𝔽_{p}^{∗} : ⟨r⟩]) = k_{a,b}^{(1)}(p).

2) We have

2^{−ν_{2}(p−1)} ∑_{v≤min(ν_{2}(p−1),e+1)} c_{2^{ν}}([𝔽_{p}^{∗} : ⟨r⟩]) = k_{a,b}^{(2)}(p).

Corollary 1. For 1 ≤ j ≤ 2 we have

∑_{p≤x, p∤2ab}2^{−ν_{2}(p−1)} ∑_{v≤min(ν_{2}(p−1),e+j−1)} c_{2^{ν}}([𝔽_{p}^{∗} : ⟨r⟩]) = K_{a,b}^{(j)}(x).

Proof of Lemma 12. 1) We consider the two cases ν_{2}(p − 1) > e and ν_{2}(p − 1) ≤ e separately. -The case ν_{2}(p − 1) > e. Note that (εr_{0}^{h})^{\frac{p−1}{2^{e}}} ≡ 1 (mod p) and so ν_{2}([𝔽_{p}^{∗} : ⟨r⟩]) ≥ e. Hence the sum in the statement of the lemma reduces to

2^{−ν_{2}(p−1)} ∑_{v≤e} φ(2^{v}) = 2^{e−ν_{2}(p−1)} = k_{a,b}^{(1)}(p),

where (11), (5) and the identity ∑_{d|n} φ(d) = n are used. -The case ν_{2}(p − 1) ≤ e. Note that

ν_{2}([𝔽_{p}^{∗} : ⟨r⟩]) = \begin{cases}ν_{2}(p − 1) − 1, & if ε = −1; \\ ν_{2}(p − 1), & if ε = 1. \end{cases}

If ϵ = −1, the sum under consideration equals

2^{−ν_{2}(p−1)}[ ∑_{v≤ν_{2}(p−1)−1} φ(2^{v}) − φ(2^{ν_{2}(p−1)})] = 0 = \frac{1 + ε}{2}.

If ϵ = 1, the sum under consideration equals

2^{−ν_{2}(p−1)} ∑_{v≤ν_{2}(p−1)} φ(2^{v}) = 1 = \frac{1 + ε}{2}.

We thus infer that the sum under consideration equals (1 + ε)/2 = k_{a,b}^{(1)}(p).

2) We consider the three cases ν_{2}(p − 1) ≤ e, ν_{2}(p − 1) = e + 1 and ν_{2}(p − 1) > e + 1 separately. -The case ν_{2}(p − 1) ≤ e. The quantity under consideration agrees with that considered in part 1 of this proof and by (6) we obtain that k_{a,b}^{(1)}(p) = (1 + ε)/2 = k_{a,b}^{(2)}(p). -The case ν_{2}(p − 1) = e + 1. Now

ε^{\frac{p−1}{2^{e+1}}} = ε, (r_{0}^{h})^{\frac{p−1}{2^{e+1}}} ≡ (\frac{r_{0}}{p}) (mod p) and hence r^{\frac{p−1}{2^{e+1}}} = (εr_{0}^{h})^{\frac{p−1}{2^{e+1}}} ≡ ε(\frac{r_{0}}{p}) (mod p).

It follows that ν_{2}([𝔽_{p}^{∗} : ⟨r⟩]) ≥ e + 1 if ε(\frac{r_{0}}{p}) = 1 and ν_{2}([𝔽_{p}^{∗} : ⟨r⟩]) = e if ε(\frac{r_{0}}{p}) = −1. Using (11) the quantity under consideration is reduced to

2^{−ν_{2}(p−1)} (∑_{v≤e} φ(2^{v}) + ε(\frac{r_{0}}{p})2^{e}) = \frac{1 + ε(\frac{r_{0}}{p})}{2}.

By (6) this equals k_{a,b}^{(2)}(p). -The case ν_{2}(p − 1) > e + 1. Now r^{(p−1)/2^{1+e}} ≡ (\frac{r_{0}}{p}) (mod p). Proceeding as before the quantity under consideration reduces to

2^{−ν_{2}(p−1)} (∑_{v≤e} φ(2^{v}) + (\frac{r_{0}}{p})2^{e}) = 2^{e−ν_{2}(p−1)}(1 + (\frac{r_{0}}{p})).

By (6) this equals k_{a,b}^{(2)}(p).

Corollary 1 shows that if in the double sum in (13) the summation is restricted to those v satisfying in addition v ≤ e, respectively v ≤ e + 1, then K_{a,b}^{(1)}(x), respectively K_{a,b}^{(2)}(x) is obtained. This in combination with Theorems 1, 3 and 4 leads to the following theorem:

Theorem 5. We have in the notation of Theorem 2,

N_{a,b}(x) = π(x) − ∑_{p≤x, p∤2ab}2^{−ν_{2}(p−1)} ∑_{2^{v}|(p−1,2h)} c_{2^{ν}}([𝔽_{p}^{∗} : ⟨r⟩]) + O (\frac{x(log log x)^{4}}{log^{3} x} ) ,

and

∑_{p≤x, p∤2ab}2^{−ν_{2}(p−1)} ∑_{e+2≤v≤ν_{2}(p−1)} c_{2^{ν}}([𝔽_{p}^{∗} : ⟨r⟩]) = O (\frac{x(log log x)^{4}}{log^{3} x} ) ,

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^{ω(d)+1} x).

Remark. Note that the inequality v ≤ min(ν_{2}(p − 1), e + 1) is equivalent to 2^{v}|(p − 1, 2h).

5.2 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, ∑_{ord(χ)=d} χ(g) = c_{d}([G : ⟨g⟩]), where the sum is over the characters χ of G of order d. Using this and noting that χ(r) = χ(ε)χ^{h}(r_{0}), equation (13) can be rewritten as

N_{a,b}(x) = π(x) − ∑_{p≤x, p∤2ab}2^{−ν_{2}(p−1)} ∑_{ord(χ)|2^{ν_{2}(p−1)}} χ(ε)χ^{h}(r_{0}) + O(ω(ab)),  (14)

where the sum is over all characters of 𝔽_{p}^{∗} having order dividing 2^{ν_{2}(p−1)}. Note that if χ is of order 2^{v}, then χ^{h} is the trivial character if v ≤ e and a quadratic character if v = e + 1. If in the main term of (14) only those characters of order dividing h are retained, i.e., those for which χ^{h} is the trivial character, then H_{a,b}^{(1)}(x) is obtained (this is a reformulation of part 1 of Lemma 12) and hence, by part 1 of Theorem 4, the naïve heuristic. If in (14) only those characters of order dividing 2h are retained, i.e., those for which χ^{h} is the trivial or a quadratic character, then the asymptotically exact heuristic is obtained. The error term assertion in Theorem 5 can be reformulated as:

Proposition 1. We have

∑_{p≤x, p∤2ab}2^{−ν_{2}(p−1)} ∑_{2^{e+2}|ord(χ)|2^{ν_{2}(p−1)}} χ(ε)χ^{h}(r_{0}) = O (\frac{x(log log x)^{4}}{log^{3} x} ) ,

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^{ω(d)+1} x).

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 [7].

6 Some numerical experiments

Let N′_{a,b}(x) denote the number of odd prime divisors p ≤ x of the sequence {a^{k} + b^{k}}_{k=1}^{∞} and π′(x) the number of odd primes not exceeding x. We define

min_{old} = min_{x≤10^{6}}\{N′_{a,b}(x) − δ(\frac{a}{b})π′(x)\} and max_{old} = max_{x≤10^{6}}\{N′_{a,b}(x) − δ(\frac{a}{b})π′(x)\}.

Similarly we define min_{heur} and max_{heur}, but with δ(a/b)π′(x) replaced by the main term in Theorem 2.

Numerical work strongly suggests (cf. Table 2) that the main term in Theorem 2 gives a better approximation to N_{a,b}(x) than δ(r)π(x) (which on its turn gives a better approximation that δ(r)Li(x)).

sequence  min_{old}  max_{old}  min_{heur}  max_{heur}
{2^{k} + 1}_{k=1}^{∞} −56.416 ⋯ 46.958 ⋯ −24.791 ⋯ 22.432 ⋯
{4^{k} + 1}_{k=1}^{∞} −54.916 ⋯ 45.500 ⋯ −11.328 ⋯ 38.466 ⋯
{16^{k} + 1}_{k=1}^{∞} −22.250 ⋯ 35.083 ⋯ −2.785 ⋯ 44.571 ⋯
{9^{k} + 1}_{k=1}^{∞} −71.666 ⋯ 32.000 ⋯ −6.237 ⋯ 41.006 ⋯
{(−2)^{k} + 1}_{k=1}^{∞} −33.833 ⋯ 32.041 ⋯ −7.051 ⋯ 29.440 ⋯
{(−3)^{k} + 1}_{k=1}^{∞} −43.666 ⋯ 44.666 ⋯ −6.514 ⋯ 39.951 ⋯
{(−4)^{k} + 1}_{k=1}^{∞} −49.000 ⋯ 45.333 ⋯ −19.641 ⋯ 30.507 ⋯

Table 2: The old approximation of N′_{a,b}(x) versus the heuristic one

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

7 Conclusion

There is a naï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 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.

8 Acknowledgments

I would like to thank Peter Stevenhagen for pointing out that Lemma 11 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.

References

[1] C. Ballot, Density of prime divisors of linear recurrences, Mem. Amer. Math. Soc. 115 (1995), no. 551.

[2] H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a ≠ 0 von gerader bzw. ungerader Ordnung mod. p ist, Math. Ann. 166 (1966), 19–23.

[3] C. Hooley, Artin’s conjecture for primitive roots, J. Reine Angew. Math. 225 (1967), 209–220.

[4] S. Lang, On the zeta function of number fields, Invent. Math. 12 (1971), 337–345.

[5] P. Moree, On the divisors of a^{k} + b^{k}, Acta Arith. 80 (1997), 197–212.

[6] P. Moree, On primes in arithmetic progression having a prescribed primitive root, J. Number Theory 78 (1999), 85–98.

[7] P. Moree, Asymptotically exact heuristics for (near) primitive roots, J. Number Theory 83 (2000), 155–181.

[8] P. Moree, Asymptotically exact heuristics for (near) primitive roots. II, Japan. J. Math. 29 (2003), 143–157.

[9] P. Moree, On the average number of elements in a finite field with order or index in a prescribed residue class, Finite Fields Appl. 10 (2004), 438–463.

[10] P. Moree, On primes p for which d divides ord_{p}(g), Funct. Approx. Comment. Math. 33 (2005), 85–95.

[11] R. W. K. Odoni, A conjecture of Krishnamurthy on decimal periods and some allied problems, J. Number Theory 13 (1981), 303–319.

[12] K. Prachar, Primzahlverteilung, Springer, New York, 1957.

[13] J.-P. Serre, Quelques applications du théorème de densité de Chebotarev, Inst. Hautes Études Sci. Publ. Math. 54 (1981), 323–401.

[14] K. Wiertelak, On the density of some sets of primes. IV, Acta Arith. 43 (1984), 177–190.

2000 Mathematics Subject Classification: Primary 11N37; Secondary 11N69, 11R45. Keywords: primitive root, Chebotarev density theorem, Dirichlet density.

Received February 14 2005; revised version received February 24 2006. Published in Journal of Integer Sequences, July 7 2006.

Return to Journal of Integer Sequences home page.