On some sums involving primitive roots, II

Pieter Moree

Abstract Let g ∈ ℤ\{−1, 0, 1}. In part I a function w_{g}(p) was introduced having the property that under the Generalized Riemann Hypothesis (GRH), we have ∑_{p≤x} w_{g}(p) = π_{g}(x) + O(x log log x log^{−2} x). Here π_{g}(x) denotes the number of primes p ≤ x such that g is a primitive root mod p. The function w_{g}(p) can be thought of as the ‘probability’ that g is a primitive root mod p. In this note this result is generalized. Let a(mod f) be a primitive residue class. Let π_{g}(x; f, a) denote the number of primes p ≤ x with p ≡ a(mod f) such that g is a primitive root mod p. It is shown, under GRH, that

∑_{{p≤x \atop p≡a(mod f)}} w_{g}(p) = π_{g}(x; f, a) + O(x log log x log^{−2} x).

1 Introduction

Let g ∈ ℤ\{−1, 0, 1} and let h be the largest integer such that g is an hth power. Put w_{g}(p) = 0 if (g/p) = 1 (Legendre symbol) or (p − 1, h) > 1 and w_{g}(p) = 2φ(p − 1)/(p − 1) otherwise, with φ Euler’s totient. In part I we made the point that w_{g}(p) can be regarded as the ‘probability’ that g is a primitive root mod p. Working with the function w_{g}(p) has the advantage that it takes out considerations of algebraic number theoretical nature from the evaluation of quantities involving primes p that are required to be such that a prescribed integer g is a primitive root mod p. The disadvantage of working with w_{g}(p) is that one cannot be sure that the predicted result matches with reality. If w_{g}(p) is indeed the ‘probability’ that g is a primitive root mod p, it should be true that

∑_{p≤x} w_{g}(p) ∼ π_{g}(x),  (1)

where π_{g}(x) denotes the number of primes p ≤ x such that g is a primitive root mod p, in case π_{g}(x) → ∞ as x → ∞. Indeed, in part I we proved, under GRH, that something strong than (1) is actually true.

Theorem 1 [3]. (GRH). Let g ∈ ℤ\{−1, 0, 1} and let h be the largest integer such that g is an hth power. Then

2 ∑_{{p≤x \atop ( \frac{g}{p})=−1} ; (h,p−1)=1} \frac{φ(p − 1)}{p − 1} = π_{g}(x) + O (\frac{x log log x}{log^{2} x}) .  (2)

The proof proceeds by showing, unconditionally, that the l.h.s. of (2) is π(x)-like, that is that there is a constant δ_{g} such that for every C > 0 we have

∑_{p≤x} w_{g}(p) = δ_{g}Li(x) + O_{C}(x log^{−C} x),

with Li(x) the logarithmic integral. (As is well-known π(x), the number of primes p ≤ x, is π(x)-like.) From the work of Hooley [1] it follows, under GRH, that π_{g}(x) = δ_{g}Li(x) + O(x log log x log^{−2} x). From this the result then follows.

Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1 and g ∈ ℤ. Let P_{a,f,g} denote the set of primes p such that g is a primitive root mod p and p ≡ a(mod f). Let π_{g}(x; f, a) denote the number of primes p ≤ x such that p ∈ P_{a,f,g}. From the work of Lenstra [2] one knows that

Theorem 2 [2]. Put ζ_{m} = e^{2πi/m}. Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1. Let σ_{a} be the automorphism of ℚ(ζ_{f}) determined by σ_{a}(ζ_{f}) = ζ_{f}^{a}. Let c_{a}(n) be 1 if the restriction of σ_{a} to the field ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, g^{1/n}) is the identity and c_{a}(n) = 0 otherwise. Put

δ(a, f, g) = ∑_{n=1}^{∞} \frac{μ(n)c_{a}(n)}{[ℚ(ζ_{f}, ζ_{n}, g^{1/n}) : ℚ]},

with μ the Möbius function in case g is not −1 or a square and δ(a, f, g) = 0 otherwise. Then, assuming GRH, we have

π_{g}(x; f, a) = δ(a, f, g)\frac{x}{log x} + O (\frac{x log log x}{log^{2} x}) .

This result might give the impression that there is no simple formula for δ(a, f, g). Hence one expects that the sum ∑_{{p≤x \atop p≡a(mod f)}} w_{g}(p) should have a complicated dependency on a, f and g. However, on making this computation, one is in for a surprise:

Theorem 3 Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1 and g ∈ ℤ\{−1, 0, 1} and h be the largest integer such that g is an hth power. Write g = g_{1}g_{2}^{2} with g_{1} squarefree. Let g̃_{1}, ã denote the odd part of g_{1}, respectively ã. Let β = g_{1}/(g_{1}, f) and ϵ ∈ {−1, 1}. Put

A(a, f, h) = ∏_{p|(a−1,f)}(1 − \frac{1}{p}) ∏_{{p∤f \atop p|h}}(1 − \frac{1}{p − 1}) ∏_{{p∤f \atop p∤h}} (1 − \frac{1}{p(p − 1)})

if (a − 1, f, h) = 1 and A(a, f, h) = 0 otherwise. Let C > 0 be arbitrary. Then

2 ∑_{{p≤x, p≡a(mod f) \atop ( \frac{g}{p})=ϵ} ; (h,p−1)=1} \frac{φ(p − 1)}{p − 1} = ν_{ϵ}(a, f, g)Li(x) + O_{C}(\frac{x}{log^{C} x}),

where

ν_{ϵ}(a, f, g) = \frac{A(a, f, h)}{φ(f)} (1 + ϵ(\frac{a}{(f, g_{1})})\frac{(−1)^{\frac{g̃_{1}−1}{2} \frac{ã−1}{2}} μ(|β|)}{∏_{p|β, p|h}(p − 2) ∏_{p|β, p∤h}(p^{2} − p − 1)})

in case g_{1} ≡ 1(mod 4) or g_{1} ≡ 2(mod 4) and 8|f or g_{1} ≡ 3(mod 4) and 4|f and

ν_{ϵ}(a, f, g) = \frac{A(a, f, h)}{φ(f)},

otherwise. Here (./.) denotes the Jacobi symbol with the stipulation that (a/2) = (−1)^{(a^{2}−1)/8}.

An alternative expression for ν_{ϵ}(a, f, g) is

ν_{ϵ}(a, f, g) = \frac{A(a, f, h)}{φ(f)} (1 − ϵ(\frac{Δ}{a})(\frac{a}{|β|})\frac{μ(2|β|)}{∏_{p|β, p|h}(p − 2) ∏_{p|β, p∤h}(p^{2} − p − 1)}) ,

where (Δ/a) denotes the Kronecker symbol and (a/|β|) the Jacobi symbol, cf. [4]. Although this expression is more compact, the one given in Theorem 3 is the one that arises from the proof given here.

Inspired by the relative simplicity of the formula for ν_{ϵ}(a, f, g), I set out in [4] to calculate δ(a, f, g). It turns out that for a, f and g as in Theorem 3 we have δ(a, f, g) = ν_{−1}(a, f, g). From this, Theorem 2 and Theorem 3 we deduce the following generalization of Theorem 1.

Theorem 4 (GRH). Let a, f, g and h be as in the previous theorem. Then

2 ∑_{{p≤x, p≡a(mod f) \atop ( \frac{g}{p})=−1} ; (h,p−1)=1} \frac{φ(p − 1)}{p − 1} = π_{a,f,g}(x) + O (\frac{x log log x}{log^{2} x}) .  (3)

This gives further corraboration to the fact that w_{g}(p) should be considered as a probability.

The rest of this note is devoted to proving Theorem 3. In the next section we prove this result in the case h = 1 and use it in Section 3 as a building block in the proof of Theorem 3.

2 The case where h = 1

In this section we will prove Theorem 3 in the case h = 1. For convenience we write down Theorem 3 with h = 1 as a lemma.

Lemma 1 Let g ∈ ℤ\{−1, 0, 1} and suppose that g is not an hth power for any h ≥ 2. Write g = g_{1}g_{2}^{2} with g_{1} squarefree. Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1. Let g̃_{1}, ã denote the odd part of g̃_{1}, respectively ã. Let β = g_{1}/(g_{1}, f) and ϵ ∈ {−1, 1}. Then

2 ∑_{{p≤x \atop p≡a(mod f)} ; ( \frac{g}{p})=ϵ} \frac{φ(p − 1)}{p − 1}

is π(x)-like with constant

\frac{A(a, f, 1)}{φ(f)} (1 + ϵ(\frac{a}{(f, g_{1})})\frac{(−1)^{\frac{g̃_{1}−1}{2} \frac{ã−1}{2}} μ(|β|)}{∏_{p|β}(p^{2} − p − 1)})

in case g_{1} ≡ 1(mod 4) or g_{1} ≡ 2(mod 4) and 8|f or g_{1} ≡ 3(mod 4) and 4|f and π(x)-like with constant A(a, f, 1)/φ(f), otherwise. Here (./.) denotes the Jacobi symbol with the stipulation that (a/2) = (−1)^{(a^{2}−1)/8}.

The proof rests on the following three lemmata.

Lemma 2 Let r be squarefree. Then

∑_{δ|r} \frac{μ(δ)}{δ}φ(\frac{r}{δ}) = \frac{1}{r} ∏_{p|r}(p^{2} − p − 1).

Proof. Denote the above sum by h(r). It is a Cauchy product of two multiplicative functions and hence multiplicative. Notice that h(p) = (p^{2} − p − 1)/p. Thus for squarefree r we have

h(r) = ∏_{p|r} h(p) = \frac{1}{r} ∏_{p|r}(p^{2} − p − 1).

Lemma 3 The sum

∑_{p≤x, p≡a(mod f)} \frac{φ(p − 1)}{p − 1}

is π(x)-like with constant

\frac{1}{φ(f)} ∏_{p|(a−1,f)}(1 − \frac{1}{p}) ∏_{p∤f} (1 − \frac{1}{p(p − 1)}) .

Let f_{1}, ⋯, f_{s} be pairwise coprime integers and a_{1}(mod f_{1}), ⋯, a_{s}(mod f_{s}) be primitive residue classes. The sum

∑_{p≤x, p≡a_{i}(mod f_{i}), 1≤i≤s} \frac{φ(p − 1)}{p − 1}

is π(x)-like with constant

\frac{1}{φ(f_{1}f_{2} ⋯ f_{s})} ∏_{p|(a_{1}−1,f_{1})···(a_{s}−1,f_{s})}(1 − \frac{1}{p}) ∏_{p∤f_{1}···f_{s}} (1 − \frac{1}{p(p − 1)}) .

Proof. By the chinese remainder theorem there are integers n satisfying both n ≡ a(mod f) and n ≡ 1(mod d) iff a ≡ 1(mod (f, d)). Using this, it is easily seen (cf. [3]) that the sum under consideration is π(x)-like with constant

∑_{α|(a−1,f)} ∑_{(d,f)=α} \frac{μ(d)}{dφ(df/α)}.

But this sum equals the Euler product in the statement of the lemma.

The last part of the assertion can be deduced from the first one. By the chinese remainder theorem there exists γ such that γ ≡ a_{i}(mod f_{i}) for 1 ≤ i ≤ s. Clearly (γ −1, f_{i}) = (a_{i} −1, f_{i}). Now apply the first part with a = γ and f = f_{1} ⋯ f_{s} and use that (γ − 1, f_{1} ⋯ f_{s}) = (γ − 1, f_{1}) ⋯ (γ − 1, f_{s}) = (a_{1} − 1, f_{1}) ⋯ (a_{s} − 1, f_{s}). □ Lemma 4 Let t ≥ 1 be odd and squarefree. Put b = t/(f, t). Then

2 ∑_{{p≤x \atop p≡a(mod f)} ; (p/t)=ϵ} \frac{φ(p − 1)}{p − 1}

is π(x)-like with constant

(1 + ϵ(\frac{a}{(f, t)})\frac{μ(b)}{∏_{p|b}(p^{2} − p − 1)}) \frac{A(a, f, 1)}{φ(f)}.

Proof. We have

2 ∑_{p≤x ; {p≡a(mod f) \atop (p/t)=ϵ}} \frac{φ(p − 1)}{p − 1} = 2 ∑_{{1≤α≤t, (α,t)=1 \atop (α/t)=ϵ}} ∑_{{p≤x \atop p≡a(mod f)} ; p≡α(mod t) ; (p/t)=ϵ} \frac{φ(p − 1)}{p − 1} + O(1)

= 2 ∑_{{1≤α≤t, (α,t)=1 \atop (α/t)=ϵ} ; α≡a(mod (f,t))} ∑_{{p≤x \atop p≡a(mod f)} ; p≡α(mod b)} \frac{φ(p − 1)}{p − 1} + O(1),

where in the second step we used the chinese remainder theorem. Using Lemma 3 it follows that the sum in the statement of the lemma is π(x)-like with constant

\frac{2}{φ(fb)} ∏_{p|(a−1,f)}(1 − \frac{1}{p}) ∏_{p∤fb} (1 − \frac{1}{p(p − 1)}) ∑_{{1≤α≤t, (α,t)=1 \atop (α/t)=ϵ} ; α≡a(mod (f,t))} ∑_{d|(α−1,b)} \frac{μ(d)}{d},

that is with constant

\frac{1}{φ(fb)} ∏_{p|(a−1,f)}(1 − \frac{1}{p}) ∏_{p∤fb} (1 − \frac{1}{p(p − 1)}) (I_{1} + ϵI_{2})  (4)

with

I_{1} = ∑_{{1≤α≤t, (α,t)=1 \atop α≡a(mod (f,t))}} ∑_{d|(α−1,b)} \frac{μ(d)}{d}

and

I_{2} = ∑_{{1≤α≤t, (α,t)=1 \atop α≡a(mod (f,t))}}(\frac{α}{t}) ∑_{d|(α−1,b)} \frac{μ(d)}{d}

Now

I_{1} = ∑_{d|b} \frac{μ(d)}{d} ∑_{{1≤α≤t, (α,t)=1 \atop α≡a(mod (f,t))} ; α≡1(mod d)} 1

= ∑_{d|b} \frac{μ(d)}{d}φ(\frac{b}{d})
= \frac{1}{b} ∏_{p|b}(p^{2} − p − 1),

where we invoked Lemma 2. It remains to evaluate I_{2}. We have

I_{2} = ∑_{d| \frac{t}{(f,t)}} \frac{μ(d)}{d} ∑_{{1≤α≤t, (α,t)=1 \atop α≡a(mod (f,t))} ; α≡1(mod d)} (\frac{α}{t})

= (\frac{a}{(f, t)}) ∑_{d|b} \frac{μ(d)}{d} ∑_{{1≤β≤ \frac{b}{d} \atop (β, \frac{b}{d})=1}} (\frac{β}{b/d})

The inner sum equals 1 if d = b and is zero otherwise. Thus

I_{2} = (\frac{a}{(f, t)})\frac{μ(b)}{b}.

Inserting these expressions in (4), the result follows after some easy manipulations. □

Proof of Lemma 1. On using the law of quadratic reciprocity and its supplements, it is straightforward, but tedious due to case distinctions one has to make, to deduce Lemma 1 from Lemma 4. □

3 The general case

Here we will deduce Theorem 3 from Lemma 1, that is from Theorem 3 in the case where h = 1. We start with a lemma.

Lemma 5 Let t ≥ 1 be odd and squarefree. Let γ(n) = ∏_{p|n} p denote the squarefree kernel of n. Then

∑_{{1≤α≤h \atop (α,h)=1, (α−1,h)=1}}(\frac{α}{(h, t)}) = μ((h, t))\frac{h}{γ(h)} ∏_{p|h, p∤t}(p − 2)

Proof. Denote the l.h.s. by κ(h, t). Using the chinese remainder theorem we see that κ(h, t) is a multiplicative function in h. Suppose that h = p^{m}. If p ∤ t, then κ(p^{m}, t) = p^{m−1}(p − 2). If p|t, then

κ(p^{m}, t) = ∑_{{1≤α≤p^{m} \atop (α,p)=1, (α−1,p)=1}}(\frac{α}{p}) = p^{m−1} ∑_{2≤α≤p−1}(\frac{α}{p}) = −p^{m−1}.

From this the result easily follows. □

Corollary 1 Let t ≥ 1 be an odd squarefree divisor of h. Then

∑_{{1≤α≤h \atop (α,h)=1, (α−1,h)=1}}(\frac{α}{t}) = μ(t)\frac{h}{γ(h)} ∏_{p| \frac{γ(h)}{t}}(p − 2).

Proof of Theorem 3. Notice that Theorem 3 is true if h is even. Thus assume that h is odd. Since (p − 1, h) = 1 iff (p − 1, γ(h)) = 1, we can assume w.l.o.g. that h is squarefree. Now

2 ∑_{{p≤x, ( \frac{g}{p})=ϵ \atop p≡a(mod f)} ; (h,p−1)=1} \frac{φ(p − 1)}{p − 1} = O(1) + 2 ∑_{{1≤α≤h \atop (α,h)=1} ; (α−1,h)=1} ∑_{{p≤x, p≡a(mod f) \atop ( \frac{g}{p})=ϵ} ; p≡α(mod h)} \frac{φ(p − 1)}{p − 1}

= O(1) + 2 ∑_{{1≤α≤h, (α,h)=1 \atop (α−1,h)=1} ; α≡a(mod (f,h))} ∑_{{p≤x, p≡a(mod f) \atop ( \frac{g}{p})=ϵ} ; p≡α(mod h/(f,h))} \frac{φ(p − 1)}{p − 1}. (5)

Notice that the latter outer sum is empty in the case that (a − 1, (f, h)) = (a − 1, f, h) > 1. In this case Theorem 3 trivially follows. Thus we may assume that (a − 1, f, h) = 1. The latter inner sum can be evaluated using Lemma 1.

Put h_{1} = h/(f, h). Notice that since by assumption h is squarefree, h_{1} and f are coprime. For α ≡ a(mod (f, h)), let 1 ≤ β_{α} ≤ fh_{1} be the unique integer such that β_{α} ≡ a(mod f) and β_{α} ≡ α(mod h_{1}). Now for t ≥ 1, with t an odd squarefree divisor of h_{1}, put

S(t) = ∑_{{1≤α≤h \atop (α,h)=1, (α−1,h)=1} ; α≡a(mod (f,h))} (\frac{α}{t})\frac{A(β_{α}, fh_{1}, 1)}{φ(fh_{1})}.

Now using Lemma 1 and (5), we find that the sum in the l.h.s. of (5) is π(x)-like with constant

S(1) + ϵ(\frac{a}{(f, g_{1})})\frac{(−1)^{\frac{g̃_{1}−1}{2} \frac{ã−1}{2}} μ(|β|)}{μ((g_{1}, h_{1})) ∏_{p| \frac{β}{(g_{1},h_{1})}} (p^{2} − p − 1)}S((h_{1}, g_{1})),  (6)

in case g_{1} ≡ 1(mod 4) or g_{1} ≡ 2(mod 4) and 8|f or g_{1} ≡ 3(mod 4) and 4|f and π(x)-like with constant S(1) otherwise. Now

S(t) = \frac{1}{φ(f)φ(h_{1})} ∏_{p|(a−1,f)}(1 − \frac{1}{p}) ∏_{{p∤f \atop p∤h}}(1 − \frac{1}{p(p − 1)})S̃(t),  (7)

with

S̃(t) = ∑_{{1≤α≤h \atop (α,h)=1, (α−1,h)=1} ; α≡a(mod (f,h))} (\frac{α}{t}) ∏_{p|(α−1,h)}(1 − \frac{1}{p})

= ∑_{{1≤α≤h \atop (α,h)=1, (α−1,h)=1} ; α≡a(mod (f,h))} (\frac{α}{t})

= ∑_{{1≤β≤h_{1} \atop (β,h_{1})=1, (β−1,h_{1})=1}}(\frac{β}{t}),

where in the derivation of the last equality we made use of the assumption that (a − 1, f, h) = 1 and that t|h_{1}. Since by assumption t is an odd squarefree divisor of h_{1}, we have, by the Corollary to Lemma 5, that S̃(t) = μ(t) ∏_{p|h_{1}/t}(p − 2). Substituting this in (7), we obtain

S(t) = \frac{A(a, f, h)}{φ(f)} \frac{μ(t)}{∏_{p|t}(p − 2)}.  (8)

On noting that ∏_{p|(g_{1},h_{1})}(p − 2) = ∏_{p|β, p|h}(p − 2) and ∏_{p|β/(g_{1},h_{1})}(p^{2} − p − 1) = ∏_{p|β, p∤h}(p^{2} − p − 1), the theorem follows on combining (6) with (8). □

References

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

[2] H. W. Lenstra, jr., On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. 42 (1977), 201-224.

[3] P. Moree, On some sums involving primitive roots, MPI-preprint 42, 1998.

[4] P. Moree, Primes in arithmetic progressions having a prescribed primitive root, MPI-preprint 57, 1998.

Max-Planck-Institut für Mathematik, Gottfried-Claren-Straße 26, 53225 Bonn, Germany.

(e-mail: moree@mpim-bonn.mpg.de)