Uniform distribution of primes having a prescribed primitive root

Pieter Moree

January 21, 1997

Abstract

Suppose that g ∈ ℤ is not an hth power with h ≥ 2. Let P_{g} denote the set of primes p such that g is a primitive root mod p and D_{g} the set of natural numbers d ≥ 1 such that P_{g} is weakly uniformly distributed mod d. Assuming GRH, that is the Generalized Riemann Hypothesis, D_{g} is computed. En route, for arbitrary f ≥ 1 the density of primes p such that p ≡ 1(mod f) and g is a primitive root mod p is computed (on GRH).

1 Introduction

If S is any set of numbers, denote by S(x) the number of elements in S not exceeding x. For given integers a and d, denote by S(x; a, d) the number of elements in S not exceeding x that are congruent to a modulo d. We say that S is weakly uniformly distributed mod d if S(x) → ∞ (x → ∞) and for every a coprime to d,

S(x; a, d) ∼ \frac{S(x)}{φ(d)},

where φ(d) denotes Euler’s totient. In [6] the (weak) uniform distribution of many important arithmetical sequences is considered. In this note the weak uniform distribution of a class of sequences, apparently not considered in this light before, will be investigated. Let G be the set of integers g such that g ≠ −1 and g is not a square. Let P_{g} denote the set of primes p such that g is a primitive root modulo p and let D_{g} denote the set of natural numbers d such that P_{g} is weakly uniformly distributed modulo d. Clearly a necessary condition for P_{g} to be infinite is that g ∈ G. That this is also a sufficient condition was conjectured by Emil Artin in 1927 and is called Artin’s primitive root conjecture. There is no value of g for which P_{g} is known to be infinite. Presently the best unconditional result on Artin’s conjecture is due to Heath-Brown [1], who strengthened a result of Gupta and Ram Murty. Heath-Brown’s result implies that there are at most two primes for which Artin’s conjecture fails. Assuming GRH, Hooley [2] proved in 1967 a quantitative version of Artin’s conjecture. In this note we will make use of the following straightforward generalization of Hooley’s result. As usual let ν respectively ζ_{n} denote the Möbius function respectively a primitive root of unity of order n.

Theorem 1 [5] Let M be Galois and g ≠ ±1 an integer. Suppose the Riemann Hypothesis holds for the fields M_{k} := M(ζ_{k}, g^{1/k}) for every squarefree k. Then N_{M}(g; x), the number of primes p not exceeding x that split completely in M and such that g is a primitive root mod p, satisfies

N_{M}(g; x) = (∑_{k=1}^{∞} \frac{μ(k)}{[M_{k} : ℚ]}) \frac{x}{log x} + O (\frac{x log log x}{log^{2} x}) .  (1)

Define

δ(M, g) := ∑_{k=1}^{∞} \frac{μ(k)}{[M_{k} : ℚ]}.

Hooley computed δ(ℚ, g) for g ∈ G. It turns out that δ(ℚ, g) ≠ 0 for such g and thus Artin’s conjecture holds true, on GRH. In particular δ(ℚ, g) is a rational number times

A = ∏_{p} (1 − \frac{1}{p(p − 1)}) (≈ .3739558),

the so called Artin constant. For example taking g = 2 and M = ℚ yields P_{2}(x) ∼ Ax/ log x. In this note we will compute δ(M, g) in case M is a cyclotomic field (Theorem 3). From Theorem 3 it is not dif and only ificult to deduce Theorem 2 with equality in i) replaced by inclusion (cf. the proof of Theorem 2). To obtain equality in i) we use the work of H. W. Lenstra [3].

In [8] Rodier, in connection with a coding theoretical result involving Dickson polynomials, made the conjecture that

P_{2}(x; 3, 28) + P_{2}(x; 19, 28) + P_{2}(x; 27, 28) ∼ \frac{A}{4} \frac{x}{log x}.  (2)

Note that weak uniform distribution mod 28 of P_{2} would imply Rodier’s conjecture. In [5] it was shown that D_{2} = {1, 2, 4}, and thus P_{2} is not WUD mod 28. Moreover, it was shown that the true constant, on GRH, in (2) is 21A/82. Another coding theoretical application of primitive roots in arithmetic progressions occurs in the theory of perfect arithmetic codes [4].

In this note D_{g} will be computed in case g is not an hth power with h ≥ 2. The same method can be applied for all g ∈ G, however at the cost of unwieldy technical complications. Throughout we use g_{1} to denote the squarefree part of g, that is g = g_{1}g_{2}^{2}, with g_{1} squarefree. We put h_{1} = 2g_{1} if g_{1} ≡ 1(mod 4), otherwise we put h_{1} = 4g_{1}.

Theorem 2 (GRH). Let g ∈ ℤ not be an hth power, with h ≥ 2. Then

i) D_{g} = {2^{n} : n ≥ 0} if g_{1} ≡ 1(mod 4);

ii) D_{g} = {1, 2, 4} if g_{1} ≡ 2(mod 4);

iii) D_{g} = {1, 2} if g_{1} ≡ 3(mod 4).

2 The density of primes p ≡ 1(mod f) having a prescribed primitive root

In this section Theorem 3 will be proved. This result gives, under GRH, for arbitrary f ≥ 1 the density of primes p such that p ≡ 1(mod f) and moreover a prescribed integer g is primitive root mod p. Theorem 1 relates this density to the degrees of the Kummerian fields [M(ζ_{k}, g^{1/k}) : ℚ] with M cyclotomic. These degrees are computed in Lemma 2, making use of the following well-known fact from cyclotomy (see e.g. [9, p. 163]).

Lemma 1 Let 0 ≠ a ∈ ℤ. Write a = a_{1}a_{2}^{2}, with a_{1} squarefree. Then the smallest cyclotomic field containing ℚ(\sqrt{a}) is ℚ(ζ_{|a_{1}|}) in case a_{1} ≡ 1(mod 4) and ℚ(ζ_{4|a_{1}|}) otherwise.

Lemma 2 Let g not be an hth power with h ≥ 2. Suppose that k|r. Put n(k, r) = [ℚ(g^{1/k}, ζ_{r}) : ℚ]. Then

i) if k is odd, n(k, r) = kφ(r);

ii) if k is even and h_{1} ∤ r, n(k, r) = kφ(r);

iii) if k is even and h_{1}|r, n(k, r) = kφ(r)/2.

Proof. The conditions on g ensure that [ℚ(g^{1/k}) : ℚ] = k. Every subfield of a cyclotomic field is normal. The maximal normal subfield of ℚ(g^{1/k}) is ℚ if k is odd and ℚ(\sqrt{g}) if k is even. Thus if k is odd, ℚ(ζ_{r}) and ℚ(g^{1/k}) are linearly disjoint and hence

n(k, r) = [ℚ(g^{1/k}) : ℚ][ℚ(ζ_{r}) : ℚ] = kφ(r).

If k is even, then \sqrt{g} ∈ ℚ(ζ_{r}) if and only if h_{1}|r, by Lemma 1. Then using that

n(k, r) = \frac{[ℚ(g^{1/k}) : ℚ][ℚ(ζ_{r}) : ℚ]}{[ℚ(ζ_{r}) ∩ ℚ(g^{1/k}) : ℚ]} = \frac{kφ(r)}{[ℚ(ζ_{r}) ∩ ℚ(g^{1/k}) : ℚ]},

the proof is completed. □

Proposition 1 Let f ≥ 1 be an integer. Then the function h : ℕ → ℕ defined by h(k) = kφ(lcm(k, f))/φ(f) is multiplicative.

Proof. We have to show that for arbitrary coprime natural numbers k and s,

φ(lcm(k, f))φ(lcm(s, f)) = φ(f)φ(lcm(ks, f)).  (2)

Due to the multiplicativity of Euler’s totient the left hand side and the right hand side of (2) can be written as ∏_{p|ksf} h_{1}(p) and ∏_{p|ksf} h_{2}(p) respectively. Now suppose that p|ksf, p^{α}||k, α ≥ 1. Then p ∤ s. Let p^{β}||f. Now h_{1}(p) = φ(p^{max(α,β)})φ(p^{β}) and h_{2}(p) = φ(p^{β})φ(p^{max(α,β)}). The case where p|s and p ∤ k is dealt with similarly. Thus (2) holds. □

Corollary 1 For k odd, h(2k) = h(2)h(k) = 2h(k).

Theorem 3 Let g ∈ ℤ be not an hth power with h ≥ 2. Let f ≥ 1 be an arbitrary integer. Let Δ denote the discriminant of ℚ(\sqrt{g}). Put b = Δ/(Δ, f). For k ≥ 1, put h(k) = kφ(lcm(k, f))/φ(f). Suppose the Riemann Hypothesis holds for the field ℚ(ζ_{f}, g^{1/k}, ζ_{k}) for every squarefree k. Then N_{ℚ(ζ_{f})}(g; x), the number of primes p not exceeding x that split completely in ℚ(ζ_{f}) and such that g is a primitive root mod p, satisfies

N_{ℚ(ζ_{f})}(g; x) = δ(ℚ(ζ_{f}), g)\frac{x}{log x} + O (\frac{x log log x}{log^{2} x}) ,

where

δ(ℚ(ζ_{f}), g) = \frac{1}{φ(f)} ∏_{p}(1 − \frac{1}{h(p)}) (1 − \frac{μ(|b|)}{∏_{p|b}(h(p) − 1)})
= \frac{A}{φ(f)} ∏_{p|f} (1 − \frac{p − 2}{p^{2} − p − 1}) (1 − \frac{μ(|b|)}{∏_{p|b}(p^{2} − p − 1)})  (3)

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. Otherwise

δ(ℚ(ζ_{f}), g) = \frac{1}{φ(f)} ∏_{p}(1 − \frac{1}{h(p)}) = \frac{A}{φ(f)} ∏_{p|f} (1 − \frac{p − 2}{p^{2} − p − 1}) .  (4)

Proof. For notational convenience put δ = δ(ℚ(ζ_{f}), g). Using Theorem 1 the proof of Theorem 3 reduces to rewriting

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

as a product. Using Lemma 2 and Corollary 1, it follows that

φ(f)δ = ∑_{k odd} \frac{μ(k)}{h(k)} + ∑_{{k=1 \atop h_{1}∤lcm(2k,f)}}^{∞} \frac{μ(2k)}{h(2k)} + 2 ∑_{{k=1 \atop h_{1}|lcm(2k,f)}}^{∞} \frac{μ(2k)}{h(2k)}.

= \frac{1}{2} ∑_{k odd} \frac{μ(k)}{h(k)} + ∑_{{k=1 \atop h_{1}|lcm(2k,f)}}^{∞} \frac{μ(2k)}{h(2k)} = I_{1} + I_{2}.

The arithmetic function h is multiplicative by Proposition 1, moreover h(2) = 2 and thus

I_{1} = \frac{1}{2} ∑_{k odd} \frac{μ(k)}{h(k)} = \frac{1}{2} ∏_{p∤2}(1 − \frac{1}{h(p)}) = ∏_{p}(1 − \frac{1}{h(p)}).

Suppose that g_{1} ≡ 1(mod 4). Thus h_{1} = 2g_{1} and since moreover h_{1} is squarefree it follows that

I_{2} = ∑_{{k=1 \atop g_{1}|kf}}^{∞} \frac{μ(2k)}{h(2k)} = ∑_{{k=1 \atop b|k}}^{∞} \frac{μ(2k)}{h(2k)} = \frac{μ(2|b|)}{h(2|b|)} ∑_{{k=1 \atop (k,2b)=1}}^{∞} \frac{μ(k)}{h(k)} = −\frac{1}{2} \frac{μ(|b|)}{h(|b|)} ∏_{p∤2b}(1 − \frac{1}{h(p)}), (5)

where in the derivation of the second equality it is used that g_{1}/(g_{1}, f) = Δ/(Δ, f) = b. The fourth identity follows on using that b is odd, μ(2) = −1 and Corollary 1. Adding the product expansions so found for I_{1} and I_{2}, one then obtains the first identity in (3). Notice that ∏_{p|b}(h(p) − 1) = ∏_{p|b, p|f}(p − 1) ∏_{p|b, p∤f}(p^{2} − p − 1). Since Δ is squarefree, (b, f) = 1 and thus ∏_{p|b}(h(p) − 1) = ∏_{p|b}(p^{2} − p − 1). Using this, we arrive at the second identity in (3).

Next assume that g_{1} ≡ 3(mod 4). Then h_{1} = 4g_{1}. Since the only terms contributing to I_{2} are those with k odd, for k is odd the condition h_{1}|lcm(2k, f) can only be satisfied if 4|f. If 4 ∤ f, then δ = I_{1}/(2φ(f)) and we obtain (4). If 4|f, then the condition h_{1}|lcm(2k, f) can be replaced by g_{1}|k(f/4) without altering the sum I_{2}. Analyzing I_{2} as before, we find the same product, but with b replaced by g_{1}/(g_{1}, f/4) = 4g_{1}/(4g_{1}, f) = Δ/(Δ, f). Notice that again b is odd and squarefree. So the fourth identity in (5) and the second in (3), follow as before.

Finally consider the case where g_{1} ≡ 2(mod 4). Then if 8 ∤ f, the sum I_{2} is seen to be zero and in that case δ is given by (4). If 8|f, the condition h_{1}|lcm(2k, f) can be replaced by g_{1}|k(f/4) without altering the sum I_{2}. Now proceed as in the case where g_{1} ≡ 3(mod 4). Notice that again b is odd and squarefree. So the fourth identity in (5) and the second in (3), follow as before. □

From Theorem 3 it is easily deduced that δ(ℚ(ζ_{f}), g) = 0 if and only if Δ|f, that is, by Lemma 1. if and only if \sqrt{g} ∈ ℚ(ζ_{f}). This is a particular case of the following result.

Theorem 4 (GRH). Let g ∈ ℤ be not an hth power with h ≥ 2. Let M be an abelian number field. Then

δ(M, g) = 0 ⟺ \sqrt{g} ∈ M.

Moreover, if N_{M}(g; x) → ∞ as x → ∞, then δ(M, g) ≠ 0.

Proof. Since for odd q, ℚ(g^{1/q}) is not normal, ℚ(ζ_{q}, g^{1/q}) ⊈ M. Using this and [3, Corollary 4.8], it then follows that δ(M, g) = 0 if and only if \sqrt{g} ∈ M. The latter part of the assertion follows from [3, Theorem 4.6]. □

As an example let us consider the set L of primes ℓ such that there are infinitely many primes p satisfying p ≡ ±1(mod ℓ) with ℓ a primitive root mod p. Thus we have to put M = ℚ(ζ_{ℓ} + ζ_{ℓ}^{−1}) and g = ℓ in Theorem 4. Since \sqrt{ℓ} ∈ ℝ and M is the maximal real subfield of ℚ(ζ_{ℓ}), we have that \sqrt{ℓ} ∈ M if and only if \sqrt{ℓ} ∈ ℚ(ζ_{ℓ}). Thus, using Lemma 1, we see that on GRH, L = {ℓ : ℓ ≡ 3(mod 4)}. Unconditionally it can be shown [7, Theorem 3.2] that L equals {ℓ : ℓ ≡ 3(mod 4)} with at most two primes excluded. The fact that L is infinite is used in Reznikov’s proof of a weaker version of a conjecture of Lubotzky and Shalev on three-manifolds [7].

3 Proof of the main result

In this section we will prove Theorem 2. First we carry out some preparations.

Lemma 3 Let g ∈ ℤ. If k is squarefree and g_{1} ≡ 1(mod 4) then, for n ≥ 0, ℚ(g^{1/k}, ζ_{k}) ∩ ℚ(ζ_{2^{n}}) = ℚ.

Proof. The intersection of the two fields under consideration must be abelian and so is contained in ℚ(\sqrt{g}, ζ_{k}). Since the prime divisors of d(L_{1} ·L_{2}) all divide d(L_{1})d(L_{2}), we see that d_{ℚ(\sqrt{g},ζ_{k})} is odd, on noting that d_{ℚ(\sqrt{g})} = g_{1}, d_{ℚ(ζ_{k})} = d_{ℚ(ζ_{k/2})} for k ≡ 2(mod 4) and that d_{ℚ(ζ_{k})} is not divisible by primes not dividing k. Thus 2 is not ramified in ℚ(\sqrt{g}, ζ_{k}). On the other hand, the field ℚ(ζ_{2^{n}}) is at most ramified in 2. Thus ℚ(g^{1/k}, ζ_{k}) ∩ ℚ(ζ_{2^{n}}) ⊆ ℚ(\sqrt{g}, ζ_{k}) ∩ ℚ(ζ_{2^{n}}), where the latter field intersection is not ramified in any prime and hence, by a well-known theorem from Minkowski, equals ℚ. □

Lemma 4 (GRH). Let g ∈ ℤ be not an hth power with h ≥ 2. Let ℓ be an odd prime. Then δ(ℚ(ζ_{l}), g) ≠ δ(ℚ, g)/φ(l).

Corollary 2 Let g and ℓ be as in Lemma 4. Then P_{g} is not WUD mod ℓ.

Proof. We prove the result by contradiction. So assume that δ(ℚ(ζ_{l}), g) = δ(ℚ, g)/φ(l).

First assume that g_{1} ≡ 1(mod 4). Then, by Theorem 3 and Δ = g_{1}, the equality δ(ℚ(ζ_{l}), g) = δ(ℚ, g)/φ(l) is equivalent with

(1 − \frac{μ(|g_{1}|)}{∏_{p|g_{1}}(p^{2} − p − 1)}) = (1 − \frac{ℓ − 2}{ℓ^{2} − ℓ − 1}) (1 − \frac{μ(|b|)}{∏_{p|b}(p^{2} − p − 1)}) . (6)

Now if ℓ ∤ g_{1}, then b = g_{1} and 1 − (ℓ − 2)/(ℓ^{2} − ℓ − 1) = 1, a contradiction. If ℓ|g_{1}, then b = g_{1}/ℓ and thus (6) becomes

(1 − \frac{μ(|g_{1}|)}{∏_{p|g_{1}}(p^{2} − p − 1)}) = (1 − \frac{ℓ − 2}{ℓ^{2} − ℓ − 1}) (1 + \frac{μ(|g_{1}|)(ℓ^{2} − ℓ − 1)}{∏_{p|g_{1}}(p^{2} − p − 1)}) .

Notice that μ(|g_{1}|) = 1. We find

∏_{p|g_{1}}(p^{2} − p − 1) = \frac{(ℓ^{2} − ℓ − 1)(ℓ^{2} − 2ℓ + 2)}{ℓ − 2}.  (7)

Since ((ℓ^{2} − ℓ − 1)(ℓ^{2} − 2ℓ + 2), ℓ − 2) divides 2 and the left hand side of (7) is an integer, it follows that ℓ = 3 and hence ∏_{p|g_{1}}(p^{2} − p − 1) = 25. Contradiction.

Next assume g_{1} ≢ 1(mod 4). Then δ(ℚ(ζ_{l}), g) = δ(ℚ, g)/φ(l) implies, by Theorem 3, that 1 − (ℓ − 2)/(ℓ^{2} − ℓ − 1) = 1. A contradiction. □

Proof of Theorem 2. Assume that g satisfies the assumptions of Theorem 2 and, moreover, assume GRH. Then by Theorem 3 with f = 1 it follows that {1, 2} ∈ D_{g}. If d ∈ D_{g}, then for all divisors δ of d we must have δ ∈ D_{g}. This observation together with Corollary 2 shows that D_{g} ⊆ {2^{n} : n ≥ 0}. Suppose that g_{1} ≡ 3(mod 4), then by Theorem 3 it follows that P_{g} is not WUD mod 4. Thus in this case D_{g} = {1, 2}. If g_{1} ≢ 3(mod 4), then it is easy to see, by Theorem 3 again, that 4 ∈ D_{g}. If g_{1} ≡ 2(mod 4) then, by Theorem 3 again, it follows that P_{g} is not WUD mod 8. Thus in this case D_{g} = {1, 2, 4}. Finally assume that g_{1} ≡ 1(mod 4). As we have seen D_{g} ⊆ {2^{n} : n ≥ 0}. Theorem 3 shows that δ(ℚ(ζ_{2^{n}}), g) = δ(ℚ, g)/φ(2^{n}). This is consistent with weak uniform distribution mod 2^{n}. In fact, using a result of H. W. Lenstra [3], we will show that P_{g} is WUD mod 2^{n} for every n ≥ 3. This then completes the proof.

Suppose that a is odd. The set of primes p such that p ≡ a(mod 2^{n}) and g is a primitive root mod p is, with at most finite exceptions, equal to the set M = M(ℚ, ℚ(ζ_{2^{n}}), σ_{a}, < g >, 1). (We use Lenstra’s notation.) Here σ_{a} denotes the automorphism of Gal(ℚ(ζ_{2^{n}})/ℚ) determined by σ_{a}(ζ_{2^{n}}) = ζ_{2^{n}}^{a}. Under GRH, the prime density, δ_{a}, of the set M is, by [3, (3.15)], equal to

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

where

c_{a}(k) := #{{σ_{a}} ∩ Gal(ℚ(ζ_{2^{n}})/ℚ(ζ_{2^{k}}, g^{1/k}) ∩ ℚ)}.

Using Lemma 3, it follows that c_{a}(k) = #{{σ_{a}} ∩ Gal(ℚ(ζ_{2^{n}})/ℚ)} = 1, in case g_{1} ≡ 1(mod 4), for every squarefree k. Thus δ_{a} = δ_{1}. This and δ_{1} = δ(ℚ(ζ_{2^{n}}), g) > 0, which follows by Theorem 3 (or alternatively Theorem 4), yields that P_{g} is WUD mod 2^{n}. □

Remark. It is instructive to try to apply the latter part of the argument for g_{1} ≢ 1(mod 4) as well. Then we already know that P_{g} is not WUD mod 2^{n} for n large enough. Thus c_{a}(k) ≠ 1 for some a and squarefree k, that is Lemma 3 must be false in this case. Indeed, if g_{1} ≡ 3(mod 4), then ℚ(g^{1/(2|g_{1}|)}, ζ_{2|g_{1}|}) ∩ ℚ(ζ_{2^{n}}) ⊇ ℚ(i) for n ≥ 2. If g_{1} ≡ 2(mod 4) then, for n ≥ 3, ℚ(g^{1/|g_{1}|}, ζ_{|g_{1}|}) ∩ ℚ(ζ_{2^{n}}) contains ℚ(\sqrt{2}), respectively ℚ(\sqrt{−2}) if g_{1}/2 ≡ 1(mod 4), respectively g_{1}/2 ≡ 3(mod 4).

The author thanks K. Belabas and T. Kleinjung for some helpful conversations.

References

[1] R. Heath-Brown, A remark on Artin’s conjecture, Quart. J. Math. Oxford 37 (1986), 27-38.

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

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

[4] H. W. Lenstra, jr., Perfect arithmetic codes, Séminaire Delange-Pisot-Poitou, 19e année 1978/79, Théorie des nombres, Fasc. 1, Exp. No. 15, 14pp.

[5] P. Moree, On a conjecture of Rodier on primitive roots, MPI-preprint 117, Bonn, 1996.

[6] W. Narkiewicz, Uniform distribution of sequences of integers in residue classes, LNIM 1087, Springer, Berlin.

[7] A. Reznikov and P. Moree, Three-manifold subgroup growth, homology of coverings and simplicial volume, MPI-preprint 171, Bonn, 1996.

[8] F. Rodier, Estimation asymptotique de la distance minimale du dual des codes BCH et polynômes de Dickson, Discrete Math. 149 (1996), 205-221.

[9] E. Weiss, Algebraic number theory, New York University Press, New York, 1963.

Pieter Moree Max-Planck-Institut für Mathematik Gottfried-Claren Str. 26 53225 Bonn Germany E-mail: moree@mpim-bonn.mpg.de