Uniform distribution of primes having a prescribed rational primitive root

Pieter Moree

Abstract

Suppose that g ∈ ℚ^{∗} satisfies g ≠ −1 and g ∉ ℚ^{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). Also a related problem is considered.

[This is a rewritten an extended version of an earlier preprint, MPI-97-5, the main result is now extended to rational primitive roots and a related problem is considered.]

1 Introduction

If S is any set of integers, denote by S(x) the number of integers in S not exceeding x. For given integers a and d, denote by S(x; a, d) the number of integers 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. The progressions a(mod d) such that the latter asymptotic equivalence holds and S(x) → ∞ (x → ∞) are said to get their fair share of primes from S. Thus S is weakly uniformly distributed mod d if and only if all the progressions mod d get their fair share of primes from S. W. Narkiewicz [6] has written a nice survey on the state of knowledge regarding the (weak) uniform distribution of many important arithmetical sequences. 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 non-zero rational numbers g such that g ≠ −1 and g is not a square of a rational number. 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 R. Heath-Brown [1]. Heath-Brown’s result implies that there are at most two primes for which Artin’s conjecture fails. Assuming GRH, C. 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 μ, respectively ζ_{n} denote the Möbius function, respectively a primitive root of unity of order n.

1991 Mathematics Subject Classificiation. 11R45, 11A07, 11N69.

Theorem 1 [3] Let M be Galois and g ∈ G. Suppose the Riemann Hypothesis holds for the fields 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}, g^{1/k}) : ℚ]}) \frac{x}{log x} + O (\frac{x log log x}{log^{2} x}) .  (1)

For g ≠ −1, 0, 1 define

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

(Since [M(ζ_{k}, g^{1/k}) : ℚ] ≫ kφ(k), the series is seen to converge, even absolutely, and hence δ(M, g) is well-defined.) 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 paper δ(M, g) in case M is cyclotomic (Theorem 4) will be computed. From Theorem 4 it is not difficult to deduce Theorem 2 with in the cases where it is asserted that D_{g} equals an infinite set, the assertion becomes that D_{g} is contained in this infinite set. To prove the equalities, the work of H. Lenstra [3] is used.

In [8] F. 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, on GRH, D_{2} = {1, 2, 4}, and thus P_{2} is not weakly uniformly distributed 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 for g ∈ G. Notice that we can uniquely write g = g_{1}g_{2}^{2}, with g_{1} a squarefree integer and g_{2} ∈ ℚ_{>0}. We put γ = 2g_{1} if g_{1} ≡ 1(mod 4), and γ = 4g_{1} otherwise.

Theorem 2 (GRH). Let g ∈ G, and h the largest integer such that g is a pure hth power. Assume that not both g_{1} = 21 and (h, 21) = 7, then D_{g}, the set of natural numbers d such that the set of primes p such that g is a primitive root mod p is weakly uniformly distributed mod d, equals

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

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

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

In the remaining case g_{1} = 21 and (h, 21) = 7, we have D_{g} = {2^{n}3^{m} : n, m ≥ 0}.

For simplicity we call g exceptional if g_{1} = 21 and (h, 21) = 7 and ordinary otherwise. The following variant of Theorem 2 sheds some light on i), ii) and iii) of Theorem 2:

Theorem 3 (GRH). Let g and h be as in Theorem 2 such that, moreover, g is not exceptional. Then P_{g} is weakly uniformly distributed modulo d if and only if for every squarefree k ≥ 1, ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{d}) = ℚ.

Lemma 6 shows that the condition in Theorem 3 that g be not exceptional cannot be dropped.

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

In this section Theorem 4 will be proved. This result gives, on 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 fields M(ζ_{k}, g^{1/k}) with M cyclotomic (namely M = ℚ(ζ_{f})). These degrees are computed in Lemma 2, making use of the following well-known fact from cyclotomy (see e.g. [10, p. 163]).

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

The next result can be proved by a trivial generalization of an argument given by Hooley [2, pp. 213-214].

Lemma 2 Let g ∈ G and let h be the largest positive integer such that g is a pure hth power. Suppose that k|r and k is squarefree. Put k_{1} = k/(k, h) and n(k, r) = [ℚ(ζ_{r}, g^{1/k}) : ℚ]. Then

i) if k is odd, n(k, r) = k_{1}φ(r);

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

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

Proposition 1 Let f, h ≥ 1 be integers. Then the function w : ℕ → ℕ defined by

w(k) = \frac{kφ(lcm(k, f))}{(k, h)φ(f)}

is multiplicative.

Proof. For every multiplicative function g and arbitrary integers a, b ≥ 1, we obviously have g(a)g(b) = g(gcd(a, b))g(lcm(a, b)). Hence, to finish the proof it is enough to show that φ((k, f)) is a multiplicative function of k, which is obvious. □

Theorem 4 Let g ∈ G and h be the largest integer such that g is a pure hth power. Let f ≥ 1 be an arbitrary integer. Let Δ denote the discriminant of ℚ(\sqrt{g}). Put b = Δ/(Δ, f). Let w(k) be as in Proposition 1. Put

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

If (f, h) > 1, then δ(ℚ(ζ_{f}), g) = 0. Next assume that (f, h) = 1. Then

δ(ℚ(ζ_{f}), g) = \frac{1}{φ(f)} (1 − \frac{μ(|b|)}{∏_{p|b}(w(p) − 1)}) ∏_{p}(1 − \frac{1}{w(p)})
= \frac{A(f, h)}{φ(f)} (1 − \frac{μ(|b|)}{∏_{p|b, p|h}(p − 2) ∏_{p|b, p∤h}(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}{w(p)}) = \frac{A(f, h)}{φ(f)}.  (4)

Let N_{ℚ(ζ_{f})}(g; x) denote the number of primes p not exceeding x that split completely in ℚ(ζ_{f}) and such that g is a primitive root mod p. Suppose the Riemann Hypothesis holds for the field ℚ(ζ_{f}, ζ_{k}, g^{1/k}) for every squarefree k. Then

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

Remark. The assertion of Theorem 4 in case (f, h) > 1 can be trivially improved. Then the order mod p of g, for those primes p for which it exists, is bounded above by (p − 1)/q_{1}, where q_{1} is the smallest prime dividing (f, h). So N_{ℚ(ζ_{f})}(g; x) is bounded above and this holds unconditionally.

Proof of Theorem 4. For notational convenience put δ = δ(ℚ(ζ_{f}), g). We have to evaluate

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

Using Lemma 2 it follows that

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

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

The arithmetic function w is multiplicative by Proposition 1 thus, by Euler’s identity, I_{1} = ∏_{p}(1 − 1/w(p)). Suppose that g_{1} ≡ 1(mod 4). Then γ = 2g_{1} and since moreover γ is squarefree it follows that

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

where in the derivation of the second equality it is used that g_{1}/(g_{1}, f) = Δ/(Δ, f) = b.

First consider the case that (f, h) = 1. Then w(p) > 1 for every prime p, and, moreover, ∏_{p}(1 − 1/w(p)) = A(f, h) > 0. Adding the product expansions that were found for I_{1} and I_{2} results in the first equality in (3) on using that w(p) > 1. Notice that

∏_{p|b}(w(p) − 1) = ∏_{p|b, p|f}(p − 1) ∏_{p|b, p∤f, p|h}(p − 2) ∏_{p|b, p∤f, p∤h}(p^{2} − p − 1).

Since g_{1} is squarefree, (b, f) = 1 and thus

∏_{p|b}(w(p) − 1) = ∏_{p|b, p|h}(p − 2) ∏_{p|b, p∤h}(p^{2} − p − 1).

Using this, we arrive at the second equality in (3).

Next assume that g_{1} ≡ 3(mod 4). Then γ = 4g_{1}. For k is odd the condition γ|lcm(2k, f) can only be satisfied if 4|f. Thus I_{2} = 0 if 4 ∤ f and hence δ = I_{1}/φ(f) and thus (4) is satisfied in this case. If 4|f, the condition γ|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). Again b is odd and the fourth equality in (5) follows as before. Notice that again (b, f) = 1. So the second equality in (3) follows as before.

Now 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 γ|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). Again b is odd and the fourth equality in (5) follows as before. Notice that again (b, f) = 1. So the second equality in (3) follows as before.

Finally assume that (f, h) > 1. Since g ∈ G, h is odd. Since (b, f) = 1 and h is odd, there is an odd prime p_{1} such that p_{1}|h, p_{1}|f and p_{1} ∤ 2b. Since w(p_{1}) = 1, it follows that I_{1} = I_{2} = 0 and thus δ(ℚ(ζ_{f}), g) = 0.

The proof is completed on invoking Theorem 1. □

Let g ∈ G and h be the largest integer such that g is a pure hth power. From [3, Theorem 8.3] it follows that, under GRH, δ(ℚ(ζ_{f}), g) = 0 if and only if either (f, h) > 1 or Δ|f. Notice that this is an easy consequence of Theorem 4. Assume GRH and, moreover, (f, h) = 1. Then the above fact can be reformulated, with the help of Lemma 1, as δ(ℚ(ζ_{f}), g) = 0 if and only if \sqrt{g} ∈ ℚ(ζ_{f}). This is a particular case of the following result:

Theorem 5 (GRH). Let g ∈ G and h be the largest integer such that g is a pure hth power. Let M be an abelian number field of conductor f. Suppose that (f, h) = 1. Then δ(M, g) = 0 if and only if \sqrt{g} ∈ M. Moreover, if N_{M}(g; x) → ∞ as x → ∞, then δ(M, g) > 0.

We will deduce Theorem 5 from a result of Lenstra [3, Theorem 4.6], which in this context simplifies to:

Theorem 6 Let g ∈ G and M : ℚ be Galois. Let π = ∏_{ℓ|h, ℓ prime} ℓ, where h is the largest integer such that g is an hth power. Then if P_{g} is infinite, there exists σ ∈ Gal(M(ζ_{π})/ℚ) with (σ|_{M}) =id_{M} and, for every prime ℓ such that ℚ(ζ_{ℓ}, g^{1/ℓ}) ⊆ M(ζ_{π}), (σ|_{ℚ(ζ_{ℓ},g^{1/ℓ})}) ≠ id_{ℚ(ζ_{ℓ},g^{1/ℓ})}. Conversely, if such a σ exists and GRH is true, then P_{g} is infinite and δ(M, g) > 0.

Proof of Theorem 5. We first prove the if and only if part of the assertion. ‘⇐’. If \sqrt{g} ∈ M, then there does not exist a σ such that (σ|_{M}) =id_{M} and (σ|_{ℚ(ζ_{2},\sqrt{g})}) ≠ id_{ℚ(ζ_{2},\sqrt{g})}, thus, by Theorem 6, δ(M, g) = 0. ‘⇒’. If ℓ ∤ h and ℓ is odd, then ℚ(g^{1/ℓ}) is not normal and hence ℚ(ζ_{ℓ}, g^{1/ℓ}) ⊈ M(ζ_{π}). If ℓ|h, then ℚ(ζ_{ℓ}, g^{1/ℓ}) = ℚ(ζ_{ℓ}) ⊆ M(ζ_{π}). Thus the ℓ such that ℚ(ζ_{ℓ}, g^{1/ℓ}) ⊆ M(ζ_{π}), are precisely the prime divisors of π and possibly 2. We are done if we show that if \sqrt{g} ∉ M, there exists σ satisfying the requirements of Theorem 6. The existence of σ is a consequence of the Galois correspondence. The extension M(ζ_{h}) : M is Galois. If an extension σ as required in Theorem 5 would not exist, then either M(ζ_{ℓ}) for some prime ℓ|π or M(\sqrt{g}) would be contained in the fixed field of Gal(M(ζ_{h})/M). Since ℓ ∤ f, M(ζ_{ℓ}) ≠ M. Furthermore, M(\sqrt{g}) ≠ M. Thus M(ζ_{π}) : M is not Galois. Contradiction.

The assertion regarding N_{M}(g; x) now easily follows using the latter part of Theorem 6. □

As an example let us consider the set L of odd 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 5. 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 non-empty is used in A. 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 Theorem 2 will be proved. First we carry out some preparations. Throughout we denote by h the largest integer such that g is a pure hth power.

The next two lemmas are well-known. Lemma 3 follows for example from [9, Theorem 13.2.1]. For the convenience of the reader a direct proof is given. For Lemma 4, I was not able to find a reference.

Lemma 3 Let M be a number field and κ ∈ M. If [M(ζ_{k}, κ^{1/k}) : M] = kφ(k), then M(ζ_{k}) : M is the maximal abelian subextension of M(ζ_{k}, κ^{1/k}) : M.

Proof. Let

M_{k} = \{({1 \atop r} {0 \atop s}) : r ∈ ℤ/kℤ, s ∈ (ℤ/kℤ)^{∗}\} .

Notice that M′_{k}, the commutator subgroup of M_{k}, equals \{({1 \atop r} {0 \atop 1}) : r ∈ ℤ/kℤ\} . It is enough to show that if the condition of the lemma is satisfied, then Gal(M(ζ_{k}, κ^{1/k}) : M) ≅ M_{k}. For then the Galois group of the maximal abelian subextension of M(ζ_{k}, κ^{1/k}) : M is isomorphic to M_{k}/M′_{k} ≅ (ℤ/kℤ)^{∗}. Since the maximal abelian subextension of M(ζ_{k}, κ^{1/k}) : M contains M(ζ_{k}) : M and the condition of the lemma implies that the latter has Galois group (ℤ/kℤ)^{∗}, we are done.

Let α be a root of x^{k} − κ. For any σ ∈ Gal(M(ζ_{k}, κ^{1/k}) : M), there exists ℓ(σ) ∈ (ℤ/kℤ) and m(σ) ∈ (ℤ/kℤ)^{∗}, such that σ(α) = ζ_{k}^{ℓ(σ)}α and σ(ζ_{k}) = ζ_{k}^{m(σ)}. Now define a map ψ ↦ ({1 \atop ℓ(σ)} {0 \atop m(σ)}) . One checks that it is a monomorphism of Gal(M(ζ_{k}, κ^{1/k}) : M) into M_{k}. Since |M_{k}| = kφ(k) and, by assumption, |Gal(M(ζ_{k}, κ^{1/k}) : M)| = kφ(k), ψ is actually an isomorphism. □

Lemma 4 Let g ∈ G and k be squarefree. Then the maximal abelian subextension of ℚ(ζ_{k}, g^{1/k}) is ℚ(ζ_{k}) if k is odd and ℚ(ζ_{k}, \sqrt{g}) otherwise.

Proof. Write g = γ_{1}^{h}, γ_{1} ∈ ℚ.

i) k is odd. By Lemma 2 and Lemma 3, ℚ(ζ_{k}) is the maximal abelian subextension of ℚ(ζ_{k}, γ_{1}^{1/k}). Since ℚ(ζ_{k}) ⊆ ℚ(ζ_{k}, g^{1/k}) ⊆ ℚ(ζ_{k}, γ_{1}^{1/k}), we are done in this case. ii) k is even and \sqrt{γ_{1}} ∉ ℚ(ζ_{k}). Taking M = ℚ(\sqrt{γ_{1}}) and k = γ_{1} in Lemma 3, we find, on using Lemma 2, that the maximal abelian subextension of ℚ(ζ_{k}, \sqrt{γ_{1}}) = ℚ(ζ_{k}, \sqrt{g}). Since ℚ(ζ_{k}, \sqrt{g}) : ℚ is abelian and

ℚ(ζ_{k}, \sqrt{g}) ⊆ ℚ(ζ_{k}, g^{1/k}) ⊆ ℚ(ζ_{k}, γ_{1}^{1/k}),

we are done in this case. iii) k is even and \sqrt{γ_{1}} ∈ ℚ(ζ_{k}). Using Lemma 2 it follows that ℚ(ζ_{k}, g^{1/k}) = ℚ(ζ_{k/2}, g^{2/k}). Since by assumption 4 ∤ k, we are thus reduced to case i). □

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

Proof. The intersection of the two fields under consideration must be abelian and is contained in ℚ(ζ_{k}, \sqrt{g}) by Lemma 4. Let d_{K} denote the discriminant over ℚ of the number field K. Since the prime divisors of d_{L_{1}·L_{2}} all divide d_{L_{1}}d_{L_{2}}, we see that d_{ℚ(ζ_{k},\sqrt{g})} 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 at ℚ(ζ_{k}, \sqrt{g}). On the other hand, the field ℚ(ζ_{2^{n}}) is at most ramified at 2. Thus ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{2^{n}}) ⊆ ℚ(ζ_{k}, \sqrt{g}) ∩ ℚ(ζ_{2^{n}}), where the latter field intersection is not ramified at any prime and hence, by a well-known theorem due to Minkowski, equals ℚ. □

An integer is called y-smooth if all its prime divisors are ≤ y.

Lemma 6 Let d be 3-smooth, but not 2-smooth. Let g ∈ G be such that g_{1} = 21 and (h, 21) = 7. Let k ≥ 1 be squarefree. Then ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{d}) = ℚ(\sqrt{−3}) if 3|k or 14|k and ℚ otherwise. Put v(k) = [ℚ(ζ_{k}, g^{1/k}, ζ_{d}) : ℚ] and k_{1} = k/(k, h). If 42|k, then v(k) = φ(d)φ(k)k_{1}/4, if 3 ∤ k and 14 ∤ k, then v(k) = φ(d)φ(k)k_{1} and v(k) = φ(d)φ(k)k_{1}/2 otherwise.

Proof. When k is even we have

ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{d}) ⊆ ℚ(ζ_{k}, \sqrt{21}) ∩ ℚ(ζ_{d}) ⊆ ℚ(ζ_{k}, \sqrt{21}) ∩ ℚ(ζ_{3^{α}}) ⊆ ℚ(ζ_{3}),

where 3^{α}||d. The first inclusion follows on using Lemma 4, the second on using that ℚ(ζ_{k}, \sqrt{g}) is not ramified at 2 (cf. the proof of the previous lemma) and the third on noticing that \sqrt{21} ∉ ℚ(ζ_{3^{α}}) and (k, 3^{α})|3. The above inclusions also hold for the case k is odd, but then \sqrt{21} can be left out. In that case it is clear that ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{d}) = ℚ(ζ_{3}) if and only if 3|k. Now the intersection part of the assertion follows if we show that, for squarefree k, \sqrt{−3} ∈ ℚ(ζ_{2k}, \sqrt{21}) if and only if 3|k or 7|k. The ⇐ direction of this assertion is obvious. Now assume that 3 ∤ k and 7 ∤ k and assume that \sqrt{−3} ∈ ℚ(ζ_{2k}, \sqrt{21}). Then ℚ(\sqrt{21}) is linearly disjoint from ℚ(ζ_{2k}) and the compositum has Galois group isomorphic to (ℤ/2kℤ)^{∗} × ℤ/2ℤ. Let ω(k) denote the number of distinct prime divisors of k. Then ℚ(ζ_{2k}, \sqrt{21}) contains 2^{ω(k)+1} − 1 distinct quadratic subfields. On the other hand, denoting the odd prime divisors of k by p_{1}, ⋯, p_{ω(k)} and p^{∗} := (−1/p)p, we can construct 2^{ω(k)+2} − 1 distinct quadratic subfields, on using that \sqrt{−3}, \sqrt{−7}, \sqrt{p_{1}^{∗}}, ⋯, \sqrt{p_{ω(k)}^{∗}} ∈ ℚ(ζ_{2k}, \sqrt{21}). Contradiction.

The rest of the assertion now follows easily. We have [ℚ(ζ_{k}, g^{1/k}) : ℚ] = φ(k)k_{1}/2 if 42|k and [ℚ(ζ_{k}, g^{1/k}) : ℚ] = φ(k)k_{1} otherwise. Now use that

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

together with the first part of the assertion. Alternatively one can use Lemma 2 to establish the assertions on v(k) made in Lemma 6. □

Lemma 7 Let g ∈ G. Let ℓ be an odd prime not dividing h. Then δ(ℚ(ζ_{ℓ}), g) ≠ δ(ℚ, g)/φ(ℓ), except when g is exceptional and ℓ = 3.

Proof. Using Theorem 4 we see that δ(ℚ(ζ_{3}), g) = δ(ℚ, g)/2 in case g is exceptional. The remainder of the assertion we prove by contradiction. So assume that δ(ℚ(ζ_{ℓ}), g) = δ(ℚ, g)/φ(ℓ) and that we are not in the case where g is exceptional and ℓ = 3. Put P (α, β) = ∏_{p|α, p|β}(p − 2) ∏_{p|α, p∤β}(p^{2} − p − 1).

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

(1 − \frac{μ(|g_{1}|)}{P (g_{1}, h)}) = (1 − \frac{ℓ − 2}{ℓ^{2} − ℓ − 1}) (1 − \frac{μ(|b|)}{P (b, h)}) .  (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}, h)}) = (1 − \frac{ℓ − 2}{ℓ^{2} − ℓ − 1}) (1 + \frac{μ(|g_{1}|)(ℓ^{2} − ℓ − 1)}{P (g_{1}, h)}) .

Notice that μ(|g_{1}|) = 1. We find P (g_{1}, h) = (ℓ^{2} − ℓ − 1)(ℓ^{2} − 2ℓ + 2)/(ℓ − 2). Since ((ℓ^{2}−ℓ−1)(ℓ^{2}−2ℓ+2), ℓ−2) divides 2 and P (g_{1}, h) must be an integer, it follows that ℓ = 3 and hence P (g_{1}, h) = 25. Thus g is exceptional and ℓ = 3, which contradicts our assumption.

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

Lemma 7 has the following easy consequence for the weak uniform distribution of P_{g}.

Lemma 8 (GRH). Let g ∈ G and ℓ be an odd prime. Then P_{g} is not weakly uniformly distributed mod ℓ, except when g is exceptional and ℓ = 3.

Proof. Left to the reader. □

Proof of Theorem 2. Assume that g satisfies the assumptions of Theorem 2 and, moreover, assume GRH. Then by Theorem 4 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}. First consider the case where g is ordinary. Then this observation together with Lemma 8 shows that D_{g} ⊆ {2^{n} : n ≥ 0}. Suppose that g_{1} ≡ 3(mod 4), then by Theorem 4 it follows that P_{g} is not weakly uniformly distributed mod 4. Thus in this case D_{g} = {1, 2}. If g_{1} ≢ 3(mod 4), then it is easy to see, by Theorem 4 again, that 4 ∈ D_{g}. If g_{1} ≡ 2(mod 4) then, by Theorem 4 again, it follows that P_{g} is not weakly uniformly distributed 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 4 shows that δ(ℚ(ζ_{2^{n}}), g) = δ(ℚ, g)/φ(2^{n}). This is consistent with weak uniform distribution mod 2^{n}. In fact, using a result of Lenstra [3], we will show that P_{g} is weakly uniformly distributed mod 2^{n} for every n ≥ 3. This then completes the proof in the case where g is ordinary.

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, (2.15)], equal to

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

where c_{a}(k) = 1 if σ_{a} fixes ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{2^{n}}) pointwise and c_{a}(k) = 0 otherwise. In case g_{1} ≡ 1(mod 4), by Lemma 5 the latter intersection of fields equals ℚ (at least when k is squarefree) and hence c_{a}(k) = 1 for every squarefree k. Thus δ_{a} = δ_{1}. This and δ_{1} = δ(ℚ(ζ_{2^{n}}), g) > 0, which follows by Theorem 4 (or alternatively Theorem 5), yields that P_{g} is weakly uniformly distributed mod 2^{n}.

It remains to deal with the case where g is exceptional. By Corollary 8, a necessary condition for P_{g} to be weakly uniformly distributed mod d, is that d is 3-smooth. The proof of the theorem will be completed once we show that this necessary condition is also sufficient. The analysis of the case g_{1} ≡ 1(mod 4) applies in the exceptional case as well and we find that for every 2-smooth integer d, P_{g} is weakly uniformly distributed mod d. Next assume that d is 3-smooth, but not 2-smooth. Let a be an integer such that (a, 6) = 1. Let σ_{a} denote the automorphism of Gal(ℚ(ζ_{d})/ℚ) determined by σ_{a}(ζ_{d}) = ζ_{d}^{a}. Then δ_{a} = ∑_{k} μ(k)c̃_{a}(k)/v(k), where c̃_{a}(k) = 1 if σ_{a} fixes M_{k,d} := ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{d}) pointwise and c̃_{a}(k) = 0 otherwise. (Recall that v(k) = [ℚ(ζ_{k}, g^{1/k}, ζ_{d}) : ℚ].) By Lemma 6, there are, in case k is squarefree, only two possibilities for M_{k,d}; either ℚ(\sqrt{−3}) or ℚ. Thus either δ_{a} = ∑_{k} μ(k)/v(k), or δ_{a} = ∑_{k} μ(k)/v(k) − ∑_{3|k or 14|k} μ(k)/v(k) (depending on whether σ_{a} fixes ℚ(\sqrt{−3}) or not). Since, by Theorem 5 for example, δ_{1} > 0, it remains to show that

J := ∑_{{k=1 \atop 3|k or 14|k}}^{∞} \frac{μ(k)}{v(k)} = 0.

Now

J = ∑_{{3|k \atop 14∤k}} \frac{μ(k)}{v(k)} + ∑_{{3∤k \atop 3|k}} \frac{μ(k)}{v(k)} + ∑_{42|k} \frac{μ(k)}{v(k)} = J_{1} + J_{2} + J_{3},

say. Using Lemma 6 we find

J_{1} = −\frac{1}{18φ(d)} ∏_{p≠2,3,7} (1 − \frac{1}{p(p − 1)}) ∏_{{p|h \atop p≠7}} (1 − \frac{1}{p − 1}) ,

J_{2} = −3J_{1} and J_{3} = 2J_{1}. Hence J = 0. □

Remark 1. In the exceptional case the only integers that can be shown to be in D_{g} by appealing to Theorem 4 only, are 1, 2, 3, 4, 6 and 12.

Remark 2. It is instructive to try to apply the argument that showed that P_{g} is weakly uniformly distributed modulo 2-smooth numbers in case g_{1} ≡ 1(mod 4) to the remaining g_{1}. Then we already know that P_{g} is not weakly uniformly distributed mod 2^{n} for n large enough. Thus c_{a}(k) ≠ 1 for some a and squarefree k, that is Lemma 5 must be false in this case. Indeed, if g_{1} ≡ 3(mod 4), then ℚ(ζ_{2|g_{1}|}, 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 next lemma together with Theorem 2 immediately implies Theorem 3.

Lemma 9 Let d ≥ 1 and g ∈ G. We have ℚ(ζ_{k}, g^{1/k})∩ ℚ(ζ_{d}) = ℚ for every squarefree k if and only if i), ii) or iii) of Theorem 2 is satisfied.

Proof. ‘⇒’. Suppose d contains an odd prime factor, p. Then ℚ(ζ_{p}) ⊆ ℚ(ζ_{p}, g^{1/p}) ∩ ℚ(ζ_{d}) thus d = 2^{n}, for some n ≥ 0. Suppose that g_{1} ≡ 2(mod 4), we have to show that n ≤ 2. So assume that n ≥ 3. Then ℚ(ζ_{|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). Finally suppose that g_{1} ≡ 3(mod 4). We have to show that n ≤ 1. So assume that n ≥ 2. Notice that then ℚ(i) ⊆ ℚ(ζ_{2|g_{1}|}, g^{1/2|g_{1}|}) ∩ ℚ(ζ_{2^{n}}). ‘⇐’. If g_{1} ≡ 1(mod 4), then this follows by Lemma 5. The other cases, except g_{1} ≡ 2(mod 4) and d = 4 are trivial. It remains to show that i ∉ ℚ(ζ_{k}, g^{1/k}) for k squarefree and g_{1} ≡ 2(mod 4). A way of showing that i ∉ ℚ(ζ_{k}, g^{1/k}) is to show that [ℚ(ζ_{lcm(4,k)}, g^{1/k}) : ℚ] = 2[ℚ(ζ_{k}, g^{1/k}) : ℚ]. This now follows by computing these degrees using Lemma 2. □

4 A related open problem

Throughout this section g is assumed to be in G. A question similar to that of determining D_{g}, is to determine all d and g such that δ(ℚ(ζ_{d}), g) = δ(ℚ, g)/φ(d). Some obvious solutions are given by Theorem 2. In order to exclude these solutions from further consideration, I introduce the concept of special pairs. To this end let us define, for a coprime to d,

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

where c_{a}(k) = 1 if σ_{a} fixes ℚ(ζ_{k}, g^{1/k}) ∩ ℚ(ζ_{d}) pointwise and c_{a}(k) = 0 otherwise. (Here σ_{a} denotes the automorphism of Gal(ℚ(ζ_{d})/ℚ) determined by σ_{a}(ζ_{d}) = ζ_{d}^{a}.) Notice that δ(1, d, g) = δ(ℚ(ζ_{d}), g). We say that a pair [g, d] is special if δ(1, d, g) = δ(1, 1, g)/φ(d), and there exists a such that δ(a, d, g) ≠ δ(1, 1, g)/φ(d). If for some g, there is no d such that [g, d] is special, then g is said to be a good generator. Similarly, if for some d there is no g such that [g, d] is special, then d is said to be a good modulus. Notice that, under GRH, a generator g is good if, for arbitrary d, the progession 1(mod d) gets its fair share of primes from P_{g} if and only if P_{g} is weakly uniformly distributed mod d. On using Theorem 4 it is easily deduced that if g_{1} ≢ 1(mod 4), then g is a good generator. So from now on assume that g_{1} ≡ 1(mod 4). Recall that P (α, β) = ∏_{p|α, p|β}(p − 2) ∏_{p|α, p∤β}(p^{2} − p − 1). Notice that P (α, β) is odd when β is odd. From Theorem 4 and the proof of Theorem 2 it now follows that [g, d] is special if it satisfies

(1 − \frac{μ(|g_{1}|)}{P (g_{1}, h)}) = κ(d) (1 − \frac{μ(|b|)}{P (b, h)})  (7)

and d is not listed in Theorem 2. In (7) the function κ is defined by

κ(d) := ∏_{p|d} (1 − \frac{p − 2}{p^{2} − p − 1}) = ∏_{p|d} \frac{(p − 1)^{2}}{p^{2} − p − 1}.

Notice that κ : ℕ → ℚ is a multiplicative function satisfying 0 < κ(d) ≤ 1. Also note that (x − 2)/(x^{2} − x − 1) is monotonously decreasing for x > 3 and that κ(d) = 1 implies that d is 2-smooth. Let Ĩ denote the image of the odd integers under κ. Clearly Ĩ equals κ(ℕ) with 1 removed. Recall that b = g_{1}/(g_{1}, d).

First we will fix g and study the set of moduli d for which (7) is satisfied. Since we are only interested in exceptional pairs and every 2-smooth number d is a good modulus, we may assume that d contains an odd prime factor, and hence κ(d) < 1. By comparing the size of the left and right hand side of (7), it is seen that μ(|b|) = −1. Thus (g_{1}, d) ≠ |g_{1}|. On the other hand, if (g_{1}, d) = 1 then d must be 2-smooth. Thus it follows that [g, d] is not special if g_{1} is a prime.

Taking μ(|b|) = −1 and rewriting (7) a little bit shows that if

Q(g, δ̃) ∉ Ĩ for all δ̃|g_{1} with 1 < δ̃ < |g_{1}| and μ(|g_{1}/δ̃|) = −1,  (8)

where, for δ̃|g_{1},

Q(g, δ̃) := \frac{P (g_{1}, h) − μ(|g_{1}|)}{P (δ̃, h)(P (g_{1}/δ̃, h) + 1)},

then g is a good generator.

From (8) and the next lemma it follows that given g, there are at most finitely many squarefree moduli d such that [g, d] is special and that they can be effectively determined.

Lemma 10 For every q ∈ ℚ, there are at most finitely many squarefree values of d such that κ(d) = q. Moreover, they can be effectively determined.

Proof. Notice that there is at most one prime p such that κ(p) = q and that p can be effectively determined. We proceed by induction. Assume that we know there are at most finitely many effectively determinable squarefree d with ω(d) ≤ s such that κ(d) = q for every fixed q ∈ ℚ, then we will show that there are at most finitely many effectively determinable d with ω(d) ≤ s + 1 such that κ(d) = q for every fixed q ∈ ℚ. To this end consider the equation κ(p_{1}p_{2} ⋯ p_{s+1}) = q with p_{1} < p_{2} < p_{2} < … < p_{s+1}. Since the lemma is clearly true when q ≥ 1, assume that q < 1. Let p̃ be the largest prime such that κ(p̃)^{s+1} ≤ q. Then p_{1} ≤ p̃, for otherwise κ(p_{1} ⋯ p_{s+1}) ≥ κ(p_{1})^{s+1} > q. Now for each p_{1} ≤ p̃, the equation κ(p_{2} ⋯ p_{s+1}) = q/κ(p_{1}) has at most finitely many solutions, which are, moreover, effectively determinable. Thus the induction step is completed. Since ord_{2}(κ(p)) ≥ 2 for p > 2, it follows that every solution d of κ(d) = q satisfies ω(d) ≤ [\frac{e}{2}] + 1, where e = ord_{2}(q). □

Let q ∈ ℚ. The formulation (8) gives rise to the problem whether or not q ∈ Ĩ. The following two lemmas turn out to be of some help:

Lemma 11 Let q be in Ĩ, that is in the image of κ on the odd squarefree integers. Write q = q_{1}/q_{2}, with (q_{1}, q_{2}) = 1. We have q < 1. Also ord_{2}(q) > 0 and ord_{2}(q) is even. If ord_{2}(q) = 2, then q_{1} must be a square. Suppose that ord_{p_{1}}(q) ≠ 0, with p_{1} ≡ ±2(mod 5) and p_{1} prime. Then ord_{p_{1}}(q) > 0 and ord_{p_{1}}(q) is even.

Proof. We leave this to the reader, but like to give a hint. If p_{2} is a prime and p^{2} − p − 1 ≡ 0(mod p_{2}), then (2p + 1)^{2} = 4(p^{2} − p − 1) + 5 ≡ 5(mod p_{2}). Thus, by quadratic reciprocity, p_{2} = 5 or p_{2} ≡ ±1(mod 5). □

Lemma 12 Suppose that q < 1, q ∈ ℚ and ord_{2}(q) = 4. Let p be a prime such that p ≡ ±1(mod 5) and ord_{p}(q) is odd and positive. Let p_{1} be the smallest prime such that p_{1}^{2} − p_{1} − 1 ≡ 0(mod p). Let p_{2} be the smallest prime such that p_{2} ≡ 1(mod p). If κ(p_{1})κ(p_{2}) > q, then q ∉ Ĩ.

These lemmas were implemented by Karim Belabas in PARI and it was found that the only pairs [g, d] with 1 < g_{1} < 10^{6} satisfying (g_{1}, h) = 1 that could not be dealt with are those satisfying g_{1} = 7185 and (g_{1}, d) = 479 or g_{1} = 345729 and (g_{1}, d) = 6779 or g_{1} = 923329 and (g_{1}, d) = 83939. We leave it to the interested reader to show that these pairs do not give rise to special pairs with (g_{1}, h) = 1. The following example might be helpful in doing so.

We consider the pairs [g, d] with g_{1} = 1184961, (g_{1}, d) = 394987 and (g_{1}, h) = 1. In this case (7) is satisfied if and only if there exists an odd integer δ such that A ∏_{p|δ}(p^{2} − p − 1) = B ∏_{p|δ}(p − 1)^{2}, where A = 2^{8} · 3041 · 4639 and B = 65831^{2}. We will make use of the observation that 102059 is the smallest prime such that 4639|p^{2} − p − 1 for some prime p and that 22511 is the smallest prime p satisfying 4639|p − 1.

Notice that ω(δ) ≤ 4. First suppose that ω(δ) = 1. Then we have to solve A(p_{1}^{2} − p_{1} − 1) = B(p_{1} − 1)^{2}. Note that p_{1} ≡ 1(mod 4639). Since 4639^{2} ∤ A and p^{2} − p − 1 ≡ −1(mod 4639), this is impossible. Next suppose that ω(δ) = 2. Then we have to solve

A(p_{1}^{2} − p_{1} − 1)(p_{2}^{2} − p_{2} − 1) = B(p_{1} − 1)^{2}(p_{2} − 1)^{2}.  (9)

Without loss of generalization we can assume that p_{1} ≡ 1(mod 4639). Thus the right hand side of (9) is divisible by at least 4639^{2}. Since 4639 ∤ A(p_{1}^{2} − p_{1} − 1), we must have 4639|p_{2}^{2} − p_{2} − 1. It follows that p_{1} ≥ 102059 and p_{2} ≥ 22511. Thus κ(p_{1})κ(p_{2}) ≥ κ(102059)κ(22511) > A/B. This contradicts (9). Next suppose that ω(δ) = 3. Then we have to solve

A(p_{1}^{2} − p_{1} − 1)(p_{2}^{2} − p_{2} − 1)(p_{3}^{2} − p_{3} − 1) = B(p_{1} − 1)^{2}(p_{2} − 1)^{2}(p_{3} − 1)^{2}. (10)

Since κ(22511)^{3} > A/B, at least one of the primes, say p_{1}, is less than 22511. We have, without loss of generalization, that p_{2} ≡ 1(mod 4639), since 4639^{2} ∤ A(p_{1}^{2} − p_{1} − 1), we find reasoning as in the case ω(δ) = 2, that κ(p_{2})κ(p_{3}) ≥ κ(102059)κ(22511). Put α_{1} := max_{p>2}{A/(Bκ(p)) | A/B < κ(p)}. Note that α_{1} < .9896. The maximum of A/(Bκ(p)) not exceeding 1 occurs for p = 5. Thus κ(p_{2})κ(p_{3}) ≥ κ(102059)κ(22511) > α_{1} ≥ A/(Bκ(p_{1})) and so κ(p_{1})κ(p_{2})κ(p_{3}) > A/B, contradicting (10).

The pairs with g_{1} < 0 are taken care of using the following elementary observation:

Lemma 13 We have P (α, β) ≡ μ(α) + 2 (mod 4), if α > 0, α is squarefree and α ≡ 3(mod 4).

Namely if g_{1} < 0, then g_{1} = −g̃_{1} with g̃_{1} ≡ 3(mod 4) and g̃_{1} > 0. Then by Lemma 13 it follows that 2||(P (g_{1}, h) − μ(g_{1})). (Note that P (g_{1}, h) = P (g̃_{1}, h).) Thus ord_{2}(Q(g, δ̃)) ≤ 0. Then, by Lemma 11, Q(g, δ̃) ∉ Ĩ. Thus:

Lemma 14 A pair [g, d] with g_{1} < 0 is never special.

Lemma 13 does not seem to generalize to higher 2-powers than 4. It does, however, on imposing (α, β) = 1.

Lemma 15 If α > 0, α is squarefree, and (α, β) = 1, then P (α, β) ≡ μ(α) + 4 (mod 8) if α ≡ 5(mod 8) and P (α, β) ≡ μ(α) + 8 (mod 16) if α ≡ 9(mod 16).

The latter lemma gives one the final tool to prove:

Theorem 7 Suppose that [g, d] is an exceptional pair. Then g_{1} > 0, g_{1} is not a prime and g_{1}/(g_{1}, d) has an odd number of prime divisors. If (g_{1}, h) = 1, then we have, moreover, g_{1} > 10^{6} and g_{1} ≡ 1(mod 16).

Proof. By Lemma 14 we know that g_{1} > 0. As we have seen, |g_{1}| is not a prime and μ(|b|) = −1. Thus the second sentence of the statement follows. Now assume (g_{1}, h) = 1. The numerical work done shows that g_{1} > 10^{6}. We know that g_{1} ≡ 1(mod 4). Since δ̃ > 1 and (g_{1}, h) = 1, 4|P (δ̃, h). From Lemma 15 it follows that ord_{2}(Q(g, δ̃)) ≤ 0 in case g_{1} ≡ 5(mod 8) or g_{1} ≡ 9(mod 16). Thus, by Lemma 11, Q(g, δ̃) ∉ Ĩ in these cases. On invoking condition (8), it follows that g_{1} ≡ 1(mod 16). □

Sofar we fixed g and then considered the possible d such that [g, d] is an exceptional pair. One can also fix d and try to determine the g such that [g, d] is an exceptional pair. It is not difficult to see that, given d, there is a finite set S_{d} such that if [g, d] is exceptional, then g_{1} ∈ S_{d}. As remarked before a 2-smooth integer is always a good modulus. Also if d is a good modulus, then 2d is a good modulus. A more difficult observation is that if d ≥ 3 and both d and d^{2} − d − 1 are prime, then d is a good modulus. Using this and a little bit of computation one finds, for example, that all moduli d ≤ 100 are good. Thus exceptional pairs, if they exist at all, seem to be sparse at least.

The author thanks K. Belabas for helping him with the numerical work reported on in Section 4. He thanks K. Belabas, T. Kleinjung, F. Lemmermeyer, A. Schinzel and P. Stevenhagen for helpful (e-mail) discussions.

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, Abh. Math. Sem. Univ. Hamburg 67 (1997), 165-171.

[6] W. Narkiewicz, Uniform distribution of sequences of integers in residue classes, Lecture Notes in Math. 1087, Springer, 1984.

[7] A. Reznikov and P. Moree, Three-manifold subgroup growth, homology of coverings and simplicial volume, MPI-preprint 171, Bonn, 1996. (To appear in the Asian Journal of Mathematics.)

[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] S. Roman, Field Theory, Graduate Texts in Mathematics 158, Springer-Verlag, Berlin, 1995.

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

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

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