On the distribution of the order and index of g(mod p) over residue classes III

Pieter Moree

Abstract

For a fixed rational number g ∉ {−1, 0, 1} and integers a and d we consider the sets N_{g}(a, d), respectively R_{g}(a, d), of primes p for which the order, respectively the index of g(mod p) is congruent to a(mod d). Under the Generalized Riemann Hypothesis (GRH), it is known that these sets have a natural density δ_{g}(a, d), respectively ρ_{g}(a, d). It is shown that these densities can be expressed as linear combinations of certain constants introduced by Pappalardi. Furthermore it is proved that δ_{g}(a, d) and ρ_{g}(a, d) equal their g-averages for almost all g.

1 Introduction

Let g ∉ {−1, 0, 1} be a rational number (this assumption on g will be maintained throughout this paper) and let a and d be positive integers. The central object of study of this paper and its predecessors [M-I, M-II] are the sets N_{g}(a, d) and, to a lesser extent, due to its much greater simplicity of description, R_{g}(a, d). Nevertheless, the main results for both sets (Theorems 2, 3, 4) are quite analogous in character. However, Theorem 1 does not have an analog for ρ, cf. Proposition 8. The set N_{g}(a, d) consists of the primes p for which ν_{p}(g) = 0 and ord_{g}(p) ≡ a(mod d) (here and in the sequel the letter p will be used to indicate prime numbers). The set R_{g}(a, d) is similarly defined, but with ord_{g}(p) replaced by r_{g}(p), the residual index.

Pappalardi [P] established, under GRH, the existence of the natural density ρ_{g}(a, d) of R_{g}(a, d). In particular, he showed that

ρ_{g}(a, d) = ∑_{t≡a(mod d)} ∑_{n=1}^{∞} \frac{μ(n)}{[K_{nt,nt} : ℚ]},  (1)

Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Deutschland, E-mail:

moree@mpim-bonn.mpg.de

Mathematics Subject Classification (2000). 11N37, 11N69, 11R45

where for r|s we define K_{s,r} to be the number field ℚ(ζ_{s}, g^{1/r}). In [M-II] it was shown that, under GRH, the set N_{g}(a, d) has a natural density δ_{g}(a, d). In particular,

δ_{g}(a, d) = ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a}}^{∞} \frac{μ(n)c_{g}(1 + ta, dt, nt)}{[K_{[d,n]t,nt} : ℚ]},  (2)

where, for (b, f) = 1,

c_{g}(b, f, v) = \{ \begin{matrix}1 & if σ_{b}|_{ℚ(ζ_{f})∩K_{v,v}} = id; \\ 0 & otherwise, \end{matrix}

where σ_{b} is the automorphism of ℚ(ζ_{f}) that sends ζ_{f} to ζ_{f}^{b} (if a and b are integers, then by (a, b) and [a, b] we denote the greatest common divisor, respectively lowest common multiple of a and b). The rational number c_{g}(1+ta, dt, nt)/[K_{[d,n]t,nt} : ℚ] is the density of primes p ≡ 1 + ta(mod dt) that split completely in K_{nt,nt}. It turns out that the coefficient c_{g}(., ., .) has a strong tendency to equal 1 and this motivates the following definition:

Definition 1 Put

δ_{g}^{(0)}(a, d) = ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a}}^{∞} \frac{μ(n)}{[K_{[d,n]t,nt} : ℚ]},  (3)

For example, it can be shown that (unconditionally) δ_{g}(0, d) = δ_{g}^{(0)}(0, d). Other examples are provided by Proposition 9 and Lemma 18.

In case d = 2 unconditional results can be obtained, cf. [O, Wi1, Wi2]. For an extensive analysis of the case d = 3, see [M-I]. For the case d = 4 see also [M-I] (for less general results obtained by a different method for this modulus see [CM]). The case where d is prime is investigated in [M-II]. In this paper the general case is investigated. Not so surprisingly the present results will be somewhat less explicit.

By the following result d can be taken close to squarefree.

Theorem 1 (GRH).

1) If q is an odd prime dividing d_{1}, then δ_{g}(a, qd_{1}) = δ_{g}(a, d_{1})/q.

2) If 8|d, then δ_{g}(a, 2d_{1}) = δ_{g}(a, d_{1})/2. The same conclusion holds with δ_{g} replaced by δ_{g}^{(0)} or δ. In the latter case, the result holds true unconditionally.

By k(d) we denote the squarefree part of d, that is k(d) = ∏_{p|d} p. Also we define

k_{1}(d) = \{ \begin{matrix}k(d) & if d is odd; \\ 4k(d) & otherwise, \end{matrix} and k_{2}(d) = \{ \begin{matrix}k(d) & if d is odd; \\ (4, d/2)k(d) & otherwise. \end{matrix}

Note that, assuming GRH, we have ρ_{g}(a, d) = ρ_{g}(a, d_{1})d_{1}/d, where d_{1} = k_{2}(d).

It turns out that the average density of elements in a finite field of prime cardinality having order, respectively index, congruent to a(mod d) exists. Denote these densities by δ(a, d), respectively ρ(a, d). These densities can be studied by quite elementary methods and are easier to study than δ_{g}(a, d) and ρ_{g}(a, d). In this paper we will be particularly interested in the connection between δ_{g}(a, d) and δ(a, d) and the same for ρ_{g}(a, d) and ρ(a, d). The quantities δ(a, d) and ρ(a, d) are studied in [M-Av]. In this paper we will show that, under GRH, ∗(a, d) can also be regarded as the g-average of ∗_{g}(a, d) (where for ease of notation we define δ^{(0)}(a, d) = δ(a, d)):

Proposition 1 (GRH). With ∗ = δ, δ^{(0)} or ρ we have

\frac{1}{2x} ∑_{|g|≤x} ∗_{g}(a, d) = ∗(a, d) + O(\frac{1}{\sqrt{x}}).

(All results in this paper with the condition |g| ≤ x remain valid if this condition is replaced with 1 < g ≤ x or −x ≤ g < 1 and 2x by x.) Proposition 1 is a simple consequence of the following result in which G is the set of rational numbers g that cannot be written as −g_{0}^{h} or g_{0}^{h} with h > 1 an integer and g_{0} a rational number (in other words the rational numbers g that satisfy h = 1 in the notation of Lemma 3).

Theorem 2 (GRH). Suppose that g ∈ G. Set D_{1} = |D(g)/(D(g), d)| and D_{2} = [2, D(g)], where D(g) denotes the discriminant of the number field ℚ(\sqrt{g}). Then

|δ_{g}^{o}(a, d) − δ(a, d)| < \frac{2^{ω(D_{1})+2}}{φ(D_{1})D_{1}} , |δ_{g}(a, d) − δ(a, d)| < \frac{3 · 2^{ω(D_{1})+2}}{φ(D_{1})D_{1}} ,

and

|ρ_{g}(a, d) − ρ(a, d)| < \frac{2^{ω(D_{2})+2}}{φ(D_{2})D_{2}} ,

where ω(n) denotes the number of distinct prime divisors of n.

Corollary 1 If |D(g)| tends to infinity with g ∈ G, then ∗_{g}(a, d) tends to ∗(a, d), where ∗ = δ, δ^{(0)} or ρ.

Corollary 1 for ∗ = δ_{g} has been already announced (but not proved) as Theorem 2 of [M-Av]. Theorem 2 shows that ‘generically’ ∗_{g}(a, d) is quite close to ∗(a, d). For a numerical demonstration of this see Tables 1 and 2 of [M-Av]. Much more is true, however:

Theorem 3 (GRH). Let d be fixed. There are at most O_{d}(x log^{−1/φ(k_{1}(d))} x) integers g with |g| ≤ x such that ∗_{g}(a, d) ≠ ∗(a, d) for some integer a, where ∗ = δ, δ^{(0)} or ∗ = ρ. In particular,

(∗_{g}(0, d), …, ∗_{g}(d − 1, d)) = (∗(0, d), …, ∗(d − 1, d))

for almost all integers g.

This result allows one to introduce various notions of ‘genericity’ for g. Actually a more precise version of Theorem 3 is provided by Theorem 7 in case ∗ = δ or ∗ = δ^{(0)} and by Propositions 6 and 7 in case ∗ = ρ. Note that k_{1}(d)|4d.

The final main result is concerned with explicitly evaluating ∗_{g}(a, d). For χ a Dirichlet character, let

A_{χ} = ∏_{{p \atop χ(p)≠0}} (1 + \frac{[χ(p) − 1]p}{[p^{2} − χ(p)](p − 1)}) .

The constants A_{χ} turn out to be the basic constants in this context. They were introduced by Pappalardi [P]. In many cases A_{χ} ∈ ℂ\ℝ, see [M-Av, Table 3]. It can be shown that

A_{χ} ∏_{p|d}(1 − \frac{1}{p(p − 1)}) = A\frac{L(2, χ)L(3, χ)}{L(6, χ^{2})} ∏_{r=1}^{∞} ∏_{k=3r+1}^{∞} L(k, χ^{r})^{λ(k,r)},

where A denotes the Artin constant and the numbers λ(k, r) are non-zero integers that can be related to Fibonacci numbers [M-Fi] and L(s, χ) denotes the Dirichlet L-series associated to the character χ. The latter expansion of A_{χ} can be used to approximate A_{χ} with high numerical accuracy (see [M-Av, Section 6]).

(By G_{d} we denote the group of Dirichlet characters mod d and by o_{χ} the order of the Dirichlet character in G_{χ}.)

Theorem 4 (GRH). Let a and d be arbitrary natural numbers. Then there exists an integer d_{1} such that

∗(a, d) = ∑_{χ∈G_{d_{1}}} c_{χ}A_{χ} with c_{χ} ∈ ℚ(ζ_{o_{χ}}).

Furthermore, c_{χ} can be explicitly computed.

1) If ∗ = δ_{g}^{(0)}, then one can take d_{1} = k_{2}(d).

2) If ∗ = δ_{g}, then one can take d_{1} = k_{1}(d).

3) If ∗ = ρ_{g}, then one can take d_{1} = d/(a, d).

Unconditional results of this nature for δ(a, d) and ρ(a, d) are proved in [M-Av] (with d_{1} = k(d), respectively d_{1} = d/(a, d)).

The proofs of Theorems 3 and 4 require more explicit knowledge of the Galois coefficients c_{g} appearing in (2). Theorem 5 (which requires a good deal of work in order to be proved) allows one to compute ℚ(ζ_{f})∩K_{v,v}. Using this the coefficient c_{g} can be explicitly related to a Kronecker symbol. In all this, unfortunately, the case g < 0 turns out to be considerably more complicated than the case g > 0 (Proposition 4, however, sometimes brings relief).

2 Preliminaries on algebraic number theory

Let K : ℚ be an abelian number field. By the Kronecker-Weber theorem there exists an integer f such that K ⊆ ℚ(ζ_{f}). The smallest such integer is called the conductor of K. Note that K ⊆ ℚ(ζ_{n}) iff n is divisible by the conductor. Note also that the conductor of a cyclotomic field is never congruent to 2(mod 4). The following lemma allows one to determine all quadratic subfields of a given cyclotomic field.

Lemma 1 The conductor of a quadratic number field is equal to the absolute value of its discriminant.

Consider the cyclotomic extension ℚ(ζ_{f}) : ℚ. There are φ(f) distinct automorphisms each determined uniquely by σ_{a}(ζ_{f}) = ζ_{f}^{a}, with 1 ≤ a ≤ f and (a, f) = 1. We need to know when the restriction of such an automorphism to a given quadratic subfield of ℚ(ζ_{f}) is the identity. In this direction we have (for a description of the Kronecker symbol see e.g. §2.1 of [M-II]):

Lemma 2 Let ℚ(\sqrt{g_{1}}) ⊆ ℚ(ζ_{f}) be a quadratic field of discriminant D(g_{1}) and a be an integer with (a, f) = 1. We have σ_{a}|_{ℚ(\sqrt{g_{1}})} = id iff (\frac{D(g_{1})}{a}) = 1, with (\frac{·}{·}) the Kronecker symbol.

From the theory of profinite groups we recall the notion of a supernatural (or Steinitz) number. A supernatural number is a formal product ∏_{p} p^{e_{p}}, where each e_{p} ∈ ℕ ∪ {∞}. The set of supernatural numbers forms a commutative monoid with respect to the obvious product. If a is a supernatural number, then by ν_{p}(a) we denote the exponent of p occurring in a. We say that a|b, that is that a divides b, if ν_{p}(a) ≤ ν_{p}(b) for all primes p. If a|b, then b = ca, with c a supernatural number. Given supernatural numbers, we define their greatest common divisor by the formula (a, b) = ∏_{p} p^{inf(ν_{p}(a),ν_{p}(b))}. To a natural number d we associate the supernatural number d_{∞}, where d_{∞} = ∏_{p|d} p^{∞}. The ‘d-part’ of a natural number n is then given by (n, d_{∞}).

2.1 Preliminaries on field degrees and intersections

In order to explicitly evaluate certain densities in this paper, the following result will play a crucial role. Let g_{1} ≠ 0 be a rational number. By D(g_{1}) we denote the discriminant of the field ℚ(\sqrt{g}). An integer D is said to be a fundamental discriminant if D = D(g_{1}) for some g_{1} ∈ ℚ. If D is a fundamental discriminant, then ℚ(\sqrt{D}) has conductor |D| by Lemma 1. The notation D(g_{1}) along with the notation g_{0}, h, m and n_{r} introduced in the next lemma will reappear again and again in the sequel.

Lemma 3 [M-I]. Write g = ±g_{0}^{h}, where g_{0} is positive and not an exact power of a rational. Let D(g_{0}) denote the discriminant of the field ℚ(\sqrt{g_{0}}). Put m = D(g_{0})/2 if ν_{2}(h) = 0 and D(g_{0}) ≡ 4(mod 8) or ν_{2}(h) = 1 and D(g_{0}) ≡ 0(mod 8), and m = [2^{ν_{2}(h)+2}, D(g_{0})] otherwise. Put

n_{r} = \{ \begin{matrix}m & if g < 0 and r is odd; \\ [2^{ν_{2}(hr)+1}, D(g_{0})] & otherwise. \end{matrix}

We have

[K_{kr,k} : ℚ] = [ℚ(ζ_{kr}, g^{1/k}) : ℚ] = \frac{φ(kr)k}{ϵ(kr, k)(k, h)},

where, for g > 0 or g < 0 and r even we have

ϵ(kr, k) = \{ \begin{matrix}2 & if n_{r}|kr; \\ 1 & if n_{r} ∤ kr, \end{matrix}

and for g < 0 and r odd we have

ϵ(kr, k) = \{ \begin{matrix}2 & if n_{r}|kr; \\ \frac{1}{2} & if 2|k and 2^{ν_{2}(h)+1} ∤ k; \\ 1 & otherwise. \end{matrix}

Remark. Note that if h is odd, then n_{r} = [2^{ν_{2}(r)+1}, D(g)]. Note that n_{r} = n_{ν_{2}(r)}.

An easy consequence of the latter result is the following lemma.

Lemma 4

1) Suppose that q is an odd prime dividing d_{1} and q^{2} ∤ n. Then [K_{[qd_{1},n]t,nt} : ℚ] = q[K_{[d_{1},n]t,nt} : ℚ].

2) Suppose that ν_{2}(d_{1}) ≥ max{2, ν_{2}(D(g_{0}))} and 4 ∤ n. Then [K_{[2^{α}d_{1},n]t,nt} : ℚ] = 2^{α}[K_{[d_{1},n]t,nt} : ℚ].

Let g_{1} ≠ 0 be a rational number and n|2m. Note that the field ℚ(ζ_{m}, ζ_{n}\sqrt{g_{1}}) is either equal to ℚ(ζ_{m}) or a quadratic extension thereof. The following result records precisely when the extension is not quadratic. In the case m = n this result is Lemma 3 of [GP] (but earlier references undoubtedly exist).

Lemma 5 Let g_{1} ≠ 0 be a rational number and suppose that n|2m. Then we have that [ℚ(ζ_{m}, ζ_{n}\sqrt{g_{1}}) : ℚ(ζ_{m})] = ϵ_{1}(m, n), where

ϵ_{1}(m, n) = \{ \begin{matrix}1 & if D(g_{1})|m and ν_{2}(n) ≤ ν_{2}(m); \\ 1 & if D(g_{1})|m and 2||n; \\ 1 & if D(−g_{1})|m and 4||n; \\ 1 & if D(2g_{1})|m and 8||n; \\ 2 & otherwise. \end{matrix}

Proof. If p|D(g_{1}) and p is odd, then p ramifies in ℚ(ζ_{m}, ζ_{n}\sqrt{g_{1}}). This shows that if in addition p ∤ n, then [ℚ(ζ_{m}, ζ_{n}\sqrt{g_{1}}) : ℚ(ζ_{m})] = 2 (since then p does not ramify in ℚ(ζ_{m})). The rest of the argument requires some case distinctions and is left to the interested reader. □

Example. The result predicts that ℚ(i, ζ_{8}\sqrt{2}) = ℚ(i). Indeed, note that ζ_{8}\sqrt{2} = 1 + i.

Lemma 6 Let L : ℚ be abelian with L ⊆ M. If

[ℚ(ζ_{f}) ∩ L : ℚ] = [ℚ(ζ_{f}) ∩ M : ℚ].  (4)

for every integer f, then L is the maximal abelian subfield of M.

Proof. Suppose there is an abelian field L_{1} with L ⊊ L_{1} ⊂ M. Let f(L_{1}) be the conductor of L_{1}. Then

[ℚ(ζ_{f(L_{1})}) ∩ M : ℚ] ≥ [L_{1} : ℚ] > [L : ℚ] = [ℚ(ζ_{f(L_{1})}) ∩ L : ℚ].

This contradicts equation (4) with f = f(L_{1}). □

With some additional effort one can explicitly describe ℚ(ζ_{f}) ∩ K_{n,n}. Clearly this intersection field is abelian and contains ℚ(ζ_{(f,n)}). Let us first compute the absolute degree of K_{[f,n],n}. We have

[K_{[f,n],n} : ℚ] = \frac{φ(f)[K_{n,n} : ℚ]}{[ℚ(ζ_{f}) ∩ K_{n,n} : ℚ]}.  (5)

On noting that φ((f, n))φ([f, n]) = φ(f)φ(n), it follows from Lemma 3 and (5) that

[ℚ(ζ_{f}) ∩ K_{n,n} : ℚ(ζ_{(f,n)})] = \frac{[ℚ(ζ_{f}) ∩ K_{n,n} : ℚ]}{φ((f, n))} = \frac{ϵ([f, n], n)}{ϵ(n, n)}.  (6)

It is not difficult to infer from Lemma 3 that the latter quotient is either 1 or 2 (so the apparent possibility 4 does never arise). We conclude that ℚ(ζ_{f}) ∩ K_{n,n} is equal to ℚ(ζ_{(f,n)}) or a quadratic extension thereof.

Definition 2 Let D be a fundamental discriminant. Put b = D/(f, D) and let f_{odd} be the largest odd divisor of f. Put

γ(D) = \{ \begin{matrix}(−1)^{\frac{(f_{odd},D)−1}{2}} (f_{odd}, D) & if ν_{2}(f) < ν_{2}(D); \\ (−1)^{\frac{b−1}{2}} (f, D) & otherwise. \end{matrix}

Put

γ_{0}(D) = \{ \begin{matrix}γ(D) & if D ∤ n and D|[f, n]; \\ 1 & otherwise. \end{matrix}

Put

γ_{1}(D) = \{ \begin{matrix}γ(D) & if ν_{2}(f) > ν_{2}(n) and D|[f, n]; \\ 1 & otherwise. \end{matrix}

Lemma 7 The numbers γ(D), γ_{0}(D), γ_{1}(D), \frac{D}{γ_{(}D)}, \frac{D}{γ_{0}(D)} and \frac{D}{γ_{1}(D)} are all fundamental discriminants.

Proof. This requires a few case distinctions and is left to the reader. □

Remark. In this notation the dependence on f and n is suppressed. It would be more accurate to write γ_{0}(D; f, n) etcetera. This notation is used in Lemma 12.

Lemma 8 Let g_{1} ≠ 0 be a rational number. Then

[ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, \sqrt{g_{1}}) : ℚ(ζ_{(f,n)})] = \{ \begin{matrix}2 & if D(g_{1}) ∤ n and D(g_{1})|[f, n]; \\ 1 & otherwise. \end{matrix}

Furthermore,

ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, \sqrt{g_{1}}) = ℚ(ζ_{(f,n)}, \sqrt{γ_{0}(D(g_{1}))}),

with γ_{0}(D(g_{1})) ≠ 1 iff D(g_{1}) ∤ n and D(g_{1})|[f, n].

Proof. Using Lemma 1 we find that

[ℚ(ζ_{n}, \sqrt{g_{1}}) : ℚ] = φ(n)ϵ_{2}(n), where ϵ_{2}(n) = \{ \begin{matrix}1 & if D(g_{1})|n; \\ 2 & otherwise. \end{matrix}

It then follows (cf. the argument leading up to (6)) that [ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, \sqrt{g_{1}}) : ℚ(ζ_{(f,n)})] = ϵ_{2}(n)/ϵ_{2}([f, n]). Thus our field intersection is quadratic over ℚ(ζ_{(f,n)}) if D(g_{1}) ∤ n and D(g_{1})|[f, n] and equals ℚ(ζ_{(f,n)}) otherwise. In the latter case γ_{0}(D(g_{1})) = 1 and we are done. Next assume that D(g_{1}) ∤ n and D(g_{1})|[f, n]. Write γ = γ_{0}(D(g_{1})). By Lemma 7 γ is a fundamental discriminant and hence by Lemma 1 ℚ(\sqrt{γ}) is a quadratic field of conductor |γ|. Since γ|f, it follows that \sqrt{γ} ∈ ℚ(ζ_{f}). Likewise, using Lemma 7, it is seen that ℚ(\sqrt{D(g_{1})/γ}) is a field of conductor |D(g_{1})/γ|. Note that the assumption that D(g_{1}) divides [f, n] implies that \frac{D(g_{1})}{(f,D(g_{1}))}|\frac{n}{(f,n)}|n and, in case ν_{2}(f) < ν_{2}(D), that ν_{2}(n) ≥ ν_{2}(D(g_{1})). Using this we infer that \sqrt{D(g_{1})/γ} ∈ ℚ(ζ_{n}). Since \sqrt{D(g_{1})} ∈ ℚ(ζ_{n}, \sqrt{g_{1}}), it follows that \sqrt{γ} ∈ ℚ(ζ_{n}, \sqrt{g_{1}}). The proof will now be completed once we show that \sqrt{γ} ∉ ℚ(ζ_{(f,n)}). Assume that \sqrt{γ} ∈ ℚ(ζ_{(f,n)}). Then one infers, using that γ is a fundamental discriminant and, in case ν_{2}(f) < ν_{2}(D), that ν_{2}(n) ≥ ν_{2}(D), that (f, D(g_{1}))|(f, n). This together with \frac{D(g_{1})}{(f,D(g_{1}))}|\frac{n}{(f,n)} then leads to the conclusion that D(g_{1})|n, contradicting our assumption that D(g_{1}) ∤ n. □

Lemma 9 Let g_{1} ≠ 0 be a rational number. We have

ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{1}}) = \{ \begin{matrix}ℚ(ζ_{n}, \sqrt{g_{1}}) & if 2 ∤ n; \\ ℚ(ζ_{n}, \sqrt{−g_{1}}) & if ν_{2}(n) = 1; \\ ℚ(ζ_{n}, \sqrt{2g_{1}}) & if ν_{2}(n) = 2 and 8|D(g_{1}), \end{matrix}  (7)

and in these cases the intersection I = ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{1}}) can be determined using Lemma 8. Next assume that none of the conditions (7) are satisfied. Then

[I : ℚ(ζ_{(f,n)})] = \{ \begin{matrix}2 & if D(g_{1})|[f, n] and ν_{2}(f) > ν_{2}(n); \\ 1 & otherwise. \end{matrix}

Furthermore,

I = \{ \begin{matrix}ℚ(ζ_{(f,n)}, ζ_{2(f,n)}\sqrt{γ(D(g_{1})}) & if D(g_{1})|[f, n] and ν_{2}(f) > ν_{2}(n); \\ ℚ(ζ_{(f,n)}) & otherwise. \end{matrix}

Proof. Let us consider the case where 4|n, not both 8|D(g_{1}) and 4||n, and such that, moreover, D(g_{1})|[f, n] and ν_{2}(f) > ν_{2}(n). As in the proof of Lemma 8 we infer that \sqrt{γ(D(g_{1}))} ∈ ℚ(ζ_{f}). Since ν_{2}(f) > ν_{2}(n), we infer that ζ_{2(f,n)}\sqrt{γ(D(g_{1}))} is in ℚ(ζ_{f}). As in the proof of Lemma 8 we infer that \sqrt{D(g_{1})/γ(D(g_{1}))} ∈ ℚ(ζ_{n}). Since ζ_{2(f,n)}\sqrt{D(g_{1})} ∈ ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{1}}), we infer that ζ_{2(f,n)}\sqrt{γ(D(g_{1}))} ∈ ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{1}}). It remains to show that ζ_{2(f,n)}\sqrt{γ(D(g_{1}))} ∉ ℚ(ζ_{(f,n)}). If the latter element would be contained in ℚ(ζ_{(f,n)}), by Lemma 5 we would have D(2γ(D(g_{1})))|(f, n) and 8||2(f, n). Note that these conditions imply that 8|D(2g_{1}) and 8|f and so 8|D(2γ(D(g_{1})))|(f, n), contradicting the assumption that 4||(f, n). Note that

[I : ℚ(ζ_{(f,n)})] = [ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{1}}) : ℚ(ζ_{(f,n)})] = \frac{ϵ_{1}(n, 2n)}{ϵ_{1}([f, n], 2n)}. (8)

The conditions imposed ensure that ϵ_{1}(n, n) = 1. Using (8) and Lemma 5 it follows that

[I : ℚ(ζ_{(f,n)})] = \{ \begin{matrix}2 & if D(g_{1})|[f, n] and ν_{2}(f) > ν_{2}(n); \\ 2 & if D(2g_{1})|[f, n] and ν_{2}(n) = 2; \\ 1 & otherwise. \end{matrix}

Let us assume that D(2g_{1})|[f, n] and ν_{2}(n) = 2. Since if ν_{2}(n) = 2, then 8 ∤ D(g_{1}) (by assumption), it follows that ν_{2}(f) > ν_{2}(n) and so D(g_{1})|[f, n]. It follows that

[I : ℚ(ζ_{(f,n)})] = \{ \begin{matrix}2 & if D(g_{1})|[f, n] and ν_{2}(f) < ν_{2}(n); \\ 1 & otherwise. \end{matrix}

This concludes the proof. □

Let K_{n,n}^{ab} denote the maximal abelian subfield of K_{n,n}. Note that ℚ(ζ_{f}) ∩ K_{n,n} = ℚ(ζ_{f}) ∩ K_{n,n}^{ab}. In the next lemma K_{n,n}^{ab} is determined. Note that for each choice of g precisely one of the seven cases applies.

Lemma 10 Let g and g_{0} be as in Lemma 3. Let K_{n,n}^{ab} denote the maximal abelian subfield of K_{n,n}. We have

1) K_{n,n}^{ab} = ℚ(ζ_{n}) if g > 0 and ν_{2}(n) ≤ ν_{2}(h);

2) K_{n,n}^{ab} = ℚ(ζ_{n}, \sqrt{g_{0}}) if g > 0 and ν_{2}(n) ≥ ν_{2}(h) + 1;

3) K_{n,n}^{ab} = ℚ(ζ_{n}, \sqrt{g_{0}}) if g < 0 and ν_{2}(n) ≥ ν_{2}(h) + 2;

4) K_{n,n}^{ab} = ℚ(ζ_{n}, \sqrt{−g_{0}}) if g < 0, ν_{2}(n) = 1 and ν_{2}(h) = 0;

5) K_{n,n}^{ab} = ℚ(ζ_{n}, \sqrt{2g_{0}}) if g < 0, ν_{2}(h) = 1, ν_{2}(n) = 2 and 8|D(g_{0});

6) K_{n,n}^{ab} = ℚ(ζ_{2n}) if g < 0 and ν_{2}(n) ≤ ν_{2}(h);

7) K_{n,n}^{ab} = ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{0}}) if g < 0 and ν_{2}(n) = ν_{2}(h) + 1 and none of the previous cases apply.

The latter result can be formulated more compactly, but with regards to computing ℚ(ζ_{f}) ∩ K_{n,n} the more extended formulation turns out to be more suitable. A more compact reformulation of Lemma 10 is as follows.

Proposition 2 If g > 0, then

K_{n,n}^{ab} = \{ \begin{matrix}ℚ(ζ_{n}) & if ν_{2}(n) ≤ ν_{2}(h); \\ ℚ(ζ_{n}, \sqrt{g_{0}}) & if ν_{2}(n) > ν_{2}(h). \end{matrix}

If g < 0, then

K_{n,n}^{ab} = \{ \begin{matrix}ℚ(ζ_{2n}) & if ν_{2}(n) ≤ ν_{2}(h); \\ ℚ(ζ_{n}, ζ_{2n}\sqrt{g_{0}}) & if ν_{2}(n) = ν_{2}(h) + 1; \\ ℚ(ζ_{n}, \sqrt{g_{0}}) & if ν_{2}(n) ≥ ν_{2}(h) + 2. \end{matrix}

Proof of Lemma 10. For each of the seven cases one easily checks that the explicit field indicated, let us call it E, is abelian and is contained in K_{n,n}^{ab}. The idea is now to apply Lemma 6 with L = E and M = K_{n,n}. By (6) it follows that [ℚ(ζ_{f}) ∩ K_{n,n} : ℚ] = φ((f, n))ϵ([f, n], n)/ϵ(n, n). In cases 1 and 6 the degree [ℚ(ζ_{f}) ∩ E : ℚ] is trivially determined. In the cases 2, 3, 4 and 5 it can be determined by invoking Lemma 8. In the remaining case 6 we apply Lemma 9. One computes that in each of the seven cases [ℚ(ζ_{f})∩E : ℚ] = [ℚ(ζ_{f})∩K_{n,n} : ℚ] for every f and hence the result then follows on invoking Lemma 6.

As an example we deal with case 2. One checks that ℚ(ζ_{n}, \sqrt{g_{0}}) ⊆ K_{n,n}^{ab}. By Lemma 8 it follows that

[ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, \sqrt{g_{0}}) : ℚ(ζ_{(f,n)}] = \{ \begin{matrix}2 & if D(g_{0}) ∤ n and D(g_{0})|[f, n]; \\ 1 & otherwise. \end{matrix}

On the other hand, by (6) and Lemma 3,

[ℚ(ζ_{f}) ∩ K_{n,n}^{ab} : ℚ(ζ_{(f,n)}] = \frac{ϵ([f, n], n)}{ϵ(n, n)} = \{ \begin{matrix}2 & if D(g_{0}) ∤ n and D(g_{0})|[f, n]; \\ 1 & otherwise. \end{matrix}

The proof of this case then follows on invoking Lemma 6. □

Next we compute the intersection of ℚ(ζ_{f}) with the fields given in Lemma 10. To this end we require a definition.

Definition 3 In each of the seven cases as described in Lemma 10, we define γ_{g}(f, n) as follows.

1) γ_{g}(f, n) = 1.

2) γ_{g}(f, n) = γ_{0}(D(g_{0})).

3) γ_{g}(f, n) = γ_{0}(D(g_{0})).

4) γ_{g}(f, n) = γ_{0}(D(−g_{0})).

5) γ_{g}(f, n) = γ_{0}(D(2g_{0})).

6) γ_{g}(f, n) = 1.

7) γ_{g}(f, n) = γ_{1}(D(g_{0})).

Definition 4 If ν_{2}(f) > ν_{2}(n) ≥ 1 and either we are in case 6 or we are in case 7 and D(g_{0})|[f, n], then we say we are in the exceptional case.

Note that if h is odd or g > 0, the exceptional case does not arise.

Now the main result of this section can be formulated:

Theorem 5 The equality ℚ(ζ_{f}) ∩ K_{n,n} = ℚ(ζ_{(f,n)}, \sqrt{γ_{g}(f, n)}) holds, unless we are in the exceptional case when we have

ℚ(ζ_{f}) ∩ K_{n,n} = ℚ(ζ_{(f,n)}, ζ_{2(f,n)}\sqrt{γ_{g}(f, n)}).

Proof. Follows on combining Lemma 10 with Lemma 9 and Lemma 8. □

Corollary 2 Suppose that either g > 0 or g < 0 and h is odd. Then

ℚ(ζ_{f}) ∩ K_{n,n} = \{ \begin{matrix}ℚ(ζ_{(f,n)}, \sqrt{γ_{0}(D(g))}) & if ν_{2}(n) ≥ ν_{2}(h) + 1; \\ ℚ(ζ_{(f,n)}) & otherwise. \end{matrix}

Proof. By Lemma 10 we have

K_{n,n}^{ab} = \{ \begin{matrix}ℚ(ζ_{n}, \sqrt{g}) & if ν_{2}(n) ≥ ν_{2}(h) + 1; \\ ℚ(ζ_{n}) & otherwise. \end{matrix}

Now invoke Lemma 8. □

Lemma 11 Let a and f be natural numbers that are coprime. Then the density of primes p such that p splits completely in K_{n,n} and p ≡ a(mod f) is zero if a ≢ 1(mod (f, n)) and equals

\frac{1 + ϵ_{3}(a, f, n)(\frac{γ_{g}(f,n)}{a})}{2[K_{[f,n],n} : ℚ]}

otherwise, where (\frac{·}{·}) denotes the Kronecker symbol and

ϵ_{3}(a, f, n) = \{ \begin{matrix}(−1)^{\frac{a−1}{(f,n)}} & in the exceptional case; \\ 1 & otherwise. \end{matrix}

Proof. Using Chebotarev’s Density Theorem we infer that the set under consideration has a density and that the density equals 1/[K_{[f,n],n} : ℚ] if the restriction of σ_{a} to ℚ(ζ_{f}) ∩ K_{n,n} is the identity and zero otherwise. The latter intersection of fields always contains ζ_{(f,n)}. So if a ≢ 1(mod (f, n)), then σ_{a} does not leave ζ_{(f,n)} fixed and the density is zero. So assume that a ≡ 1(mod (f, n)). Using Lemma 2 and the fact that γ_{g}(f, n) is a fundamental discriminant, we infer that σ_{a}(\sqrt{γ_{g}(f, n)}) = (\frac{γ_{g}(f,n)}{a})\sqrt{γ_{g}(f, n)}. Furthermore, we have σ_{a}(ζ_{2(f,n)}) = (−1)^{(a−1)/(f,n)}ζ_{2(f,n)} = ϵ_{3}(a, f, n)ζ_{2(f,n)}. On invoking Theorem 5 the result then follows. □

Remark. If α ∈ ℚ(ζ_{f}) ∩ K_{n,n} and α ∉ ℚ(ζ_{(f,n)}), then σ_{a}(α) = ϵ_{3}(a, f, n)(\frac{γ_{g}(f,n)}{a})α.

Corollary 3 Let n be squarefree. Put t_{d} = (t, d^{∞}). The density of primes p such that p ≡ 1 + ta(mod dt) and p splits completely in K_{nt,nt} equals zero if (d, n) ∤ a or (1 + ta, d) > 1, otherwise it equals

\frac{1 + ϵ_{3}(1 + ta, dt, nt)(\frac{γ_{g}(dt,nt)}{1+ta})}{2[K_{[d,n]t,nt} : ℚ]} = \frac{1 + ϵ_{3}(1 + ta, dt_{d}, nt)(\frac{γ_{g}(dt_{d},nt)}{1+ta})}{2[K_{[d,n]t,nt} : ℚ]},  (9)

where

ϵ_{3}(1 + ta, dt_{d}, nt) = \{ \begin{matrix}(−1)^{\frac{a}{(d,n)}} & in the exceptional case; \\ 1 & otherwise. \end{matrix}

Proof. This follows from Lemma 11 together with the observation that the two systems of congruences

\{ \begin{matrix}x ≡ 1 + ta(mod dt) \\ x ≡ 1(mod nt) \end{matrix} and \{ \begin{matrix}x ≡ 1 + ta(mod dt_{d}) \\ x ≡ 1(mod nt) \end{matrix}

are equivalent. □

Remark. The equivalence of the system of congruences shows that [dt_{d}, nt] = [dt, nt] = [d, n]t, an observation that will be needed later (e.g. in the proof of Lemma 12).

The advantage of the formula on the right hand side of (9) is that the numbers γ_{g}(dt_{d}, nt) that occur are restricted to a finite set of divisors, namely those of (4d, D(g_{0})), so this is a very restricted set of numbers. The situation is described more precisely by the next result (the easy proof of which is left to the reader).

Lemma 12 Let D be a fundamental discriminant. If (d, D) = 1, then γ_{0}(D; dt_{d}, nt) = 1. Assume that (d, D) ≠ 1. Set

Δ_{1}(D) = (−1)^{\frac{(d_{odd},D)−1}{2}} (d_{odd}, D) and Δ_{2}(D) = (−1)^{\frac{D/(8d,D)−1}{2}} (8d, D).

1) If 2 ∤ d, then

γ_{0}(D; dt_{d}, nt) = \{ \begin{matrix}Δ_{1}(D) & if D ∤ nt and D|[d, n]t; \\ 1 & otherwise, \end{matrix}

where Δ_{1}(D)|d.

2) If ν_{2}(d) ≥ ν_{2}(D), then

γ_{0}(D; dt_{d}, nt) = \{ \begin{matrix}Δ_{2}(D) & if D ∤ nt and D|[d, n]t; \\ 1 & otherwise, \end{matrix}

where Δ_{2}(D)|d.

3) If 1 ≤ ν_{2}(d) < ν_{2}(D), then

γ_{0}(D; dt_{d}, nt) = \{ \begin{matrix}Δ_{1}(D) & if ν_{2}(t) < ν_{2}(D/d), D ∤ nt and D|[d, n]t; \\ Δ_{2}(D) & if ν_{2}(t) ≥ ν_{2}(D/d), D ∤ nt and D|[d, n]t; \\ 1 & otherwise, \end{matrix}

where Δ_{1}(D)|d/2 and Δ_{2}(D)|4d.

The symbol (\frac{γ_{g}(f,n)}{a}) appearing in Lemma 11 has a preference (certainly as D(g_{0}) becomes large), to be equal to 1. This can be quantified as follows.

Proposition 3 Let a and f be natural numbers that are coprime and assume that a ≡ 1(mod (f, n)). Then (\frac{γ_{g}(f,n)}{a}) ≠ 0. If D(g_{0})_{odd} ∤ [f, n], then (\frac{γ_{g}(f,n)}{a}) = 1.

Proof. Since by definition γ_{g}(f, n)|f and by assumption (a, f) = 1, the definition of the Kronecker symbol implies that (\frac{γ_{g}(f,n)}{a}) ≠ 0. If D(g_{0})_{odd} ∤ [f, n], then Definition 3 implies that γ_{g}(f, n) = 1. On noting that (\frac{γ_{g}(f,n)}{a}) = (\frac{1}{a}) = 1, the result follows. □

Remark. When h is odd the conclusion of Proposition 3 holds if we make the (weaker) assumption that D(g) ∤ [f, n].

3 A more explicit formula for δ_{g}(a, d)

After all this preparation we can rewrite (2) in a more explicit form involving the Kronecker symbol.

Theorem 6 (GRH). Let a ≥ 1 and t_{d} = (t, d^{∞}). Then

δ_{g}(a, d) = ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a}}^{∞} \frac{μ(n)c_{g}(1 + ta, dt, nt)}{[K_{[d,n]t,nt} : ℚ]},

where

c_{g}(1 + ta, dt, nt) = \frac{1}{2} (1 + ϵ_{3}(1 + ta, dt_{d}, nt) (\frac{γ_{g}(dt_{d}, nt)}{1 + ta})) ,

with γ_{g}(·, ·) as in Definition 3, (\frac{·}{·}) the Kronecker symbol and where ϵ_{3}(1+ta, dt_{d}, nt) equals (−1)^{a/(d,n)} if ν_{2}(d) > ν_{2}(n), ν_{2}(nt) ≥ 1 and K_{nt,nt}^{ab} falls under case 6 or 7 of Lemma 10 and where ϵ_{3}(1 + ta, dt_{d}, nt) = 1 otherwise.

Proof. Follows from (2), the observation that c_{g}(1+ta, dt, nt)/[K_{[d,n]t,nt} : ℚ] is the density of primes p ≡ 1 + ta(mod dt) that split completely in K_{nt,nt}, Corollary 3 and the definition of the exceptional case. □

Remark. If g > 0, d is odd or h is odd the exceptional case does not arise and hence ϵ_{3}(., ., .) = 1 for the relevant values of t and n.

Example. Suppose that h is odd and that, furthermore, d is odd or 8|d. Then, on GRH,

δ_{g}(a, d) = δ_{g}^{(0)}(a, d) − ∑_{t=1 ; {(1+ta,d)=1 \atop ( \frac{δ}{1+ta})=−1}}^{∞} ∑_{n=1, (d,n)|a ; {D(g)∤nt, D(g)|[d,n]t \atop ν_{2}(nt)≥1}}^{∞} \frac{μ(n)}{[K_{[d,n]t,nt} : ℚ]},  (10)

where

δ = \{ \begin{matrix}Δ_{1}(D(g)) & if d is odd; \\ Δ_{2}(D(g)) & if 8|d, \end{matrix}

where Δ_{1} and Δ_{2} are as in Lemma 12 and divide d. Alternatively one can write

δ_{g}(a, d) = δ_{g}^{(0)}(a, d) − ∑_{t=1 ; {(1+ta,d)=1 \atop ( \frac{δ}{1+ta})=−1}}^{∞} ∑_{{n=1, (n,d)|a \atop \sqrt{δ}∈K_{nt,nt}}}^{∞} \frac{μ(n)}{[K_{[d,n]t,nt} : ℚ]}.

Example. If g > 0 and either d is odd or 8|d, then, on GRH, (10) holds with the condition ν_{2}(nt) ≥ 1 replaced by ν_{2}(nt) ≥ ν_{2}(h) + 1 and D(g) by D(g_{0}).

Example (occurrence of exceptional case). Suppose that 8|d, g < 0 and ν_{2}(h) ≥ 2. Let t and n be such that (1 + ta, d) = 1 and (n, d)|a. Let δ = Δ_{2}(D(g_{0})). Then

2c_{g}(1+ta, dt, nt) = \{ \begin{matrix}1 + (\frac{δ}{1+ta}) & if ν_{2}(nt) ≥ ν_{2}(h) + 2; \\ 1 + (−1)^{\frac{a}{(d,n)}} (\frac{δ}{1+ta}) & if ν_{2}(nt) = ν_{2}(h) + 1 and D(g_{0})|[d, n]t; \\ 2 & otherwise. \end{matrix}

In case 1 ≤ ν_{2}(d) ≤ 2 more complicated formulae for δ_{g}(a, d) arise. For our purposes it turns out, however, that in order to prove Theorem 3 or part 2 of Theorem 4 these are not needed.

4 Relating δ_{−g}(a, d) to δ_{g}(a, d)

In this section δ_{−g}(a, d) is related to δ_{g}(a, d) (where g > 0). Since the case where g is negative is algebraically rather more complicated, this connection can sometimes be used to simplify proofs.

The basic observation is the following:

Lemma 13 Let p be odd and g ≠ 0 be a rational number. Suppose that ν_{p}(g) = 0. Then

ord_{p}(−g) = \{ \begin{matrix}2ord_{p}(g) & if 2 ∤ ord_{p}(g); \\ ord_{p}(g)/2 & if ord_{p}(g) ≡ 2(mod 4); \\ ord_{p}(g) & if 4|ord_{p}(g). \end{matrix}

Proof. Left to the reader. □

Using this observation the following result is almost immediate.

Proposition 4 (GRH). Suppose g > 0. There is an integer 1 ≤ k ≤ 4 and integers a_{j}, d_{j} for 1 ≤ j ≤ k such that δ_{−g}(a, d) = ∑_{j=1}^{k} δ_{g}(a_{j}, d_{j}), where d_{j}|\frac{8d}{(4,d)}.

Proof. First suppose that 4|d. Then, by Lemma 13,

δ_{−g}(a, d) = \{ \begin{matrix}δ_{g}(2a, 2d) & if 2 ∤ a; \\ δ_{g}(a/2, d/2) & if a ≡ 2(mod 4); \\ δ_{g}(a, d) & if a ≡ 0(mod 4). \end{matrix}  (11)

If 2|d we write δ_{−g}(a, d) = δ_{−g}(a, 2d) + δ_{−g}(a + d, 2d) and apply (11) to each of the summands. If 2 ∤ d, we write

δ_{−g}(a, d) = δ_{−g}(a, 4d) + δ_{−g}(a + d, 4d) + δ_{−g}(a + 2d, 4d) + δ_{−g}(a + 3d, 4d)

and apply (11) to each of the summands. □

5 Proof of Theorems 1 and 2

Proof of Theorem 1. A proof of part 1, based on part 1 of Lemma 4 was given in [M-II]. Similarly part 2 can be proved using part 2 of Lemma 4. The result for δ_{g}^{(0)} follows trivially from Lemma 4 and for δ it follows easily from part 1 of Theorem 1 of [M-I]. □

Proof of Theorem 2. Proof of the inequality for |δ_{g}^{(0)}(a, d) − δ(a, d)|. Using Lemma 3 we infer that

δ_{g}^{(0)}(a, d) = ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a}}^{∞} \frac{μ(n)}{φ([d, n]t)nt} + E,  (12)

with

|E| ≤ ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a, D(g)|dnt}}^{∞} \frac{|μ(n)|}{φ([d, n]t)nt}.

Let us denote the latter double sum by E_{1}. Note that

E_{1} ≤ ∑_{t=1}^{∞} ∑_{{n=1 \atop D(g)|dnt}}^{∞} \frac{|μ(n)|}{φ(nt)nt} = ∑_{D_{1}|v} \frac{2^{ω(v)}}{φ(v)v}

= ∑_{v_{1}=1}^{∞} \frac{2^{ω(D_{1}v_{1})}}{φ(D_{1}v_{1})D_{1}v_{1}} ≤ \frac{2^{ω(D_{1})}}{φ(D_{1})D_{1}} ∑_{v=1}^{∞} \frac{2^{ω(v)}}{φ(v)v} < \frac{2^{ω(D_{1})+2}}{φ(D_{1})D_{1}} .  (13)

By Theorem 3 of [M-Av] the second double sum in (12) equals δ(a, d). □

Remark. In case (a, d) = 1, the term φ(D_{1}) in the first inequality of Theorem 2 can be replaced by φ(dD_{1}).

Proof of the inequality for |δ_{g}(a, d) − δ(a, d)|. Using Theorem 6 and the remark following Proposition 3 we have δ_{g}(a, d) = δ_{g}^{(0)}(a, d) + E_{2}, with

|E_{2}| ≤ ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a, D(g)|[d,n]t}}^{∞} \frac{|μ(n)|}{[K_{[d,n]t,nt} : ℚ]}.

Using Lemma 3 we infer that

|E_{2}| ≤ 2 ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a, D(g)|dnt}}^{∞} \frac{|μ(n)|}{φ([d, n]t)nt} = 2E_{1}.

Using (13), we then infer that |E_{2}| < 2^{ω(D_{1})+3}/(φ(D_{1})D_{1}). From the latter estimate, (13) and the inequality for δ_{g}^{(0)}(a, d), the result then follows. □

Proof of inequality for |ρ_{g}(a, d) − ρ(a, d)|. For this, see the proof of Proposition 5 of [M-Av]. □

6 The index reconsidered

In this section we compare ρ_{g}(a, d) with its average value ρ(a, d). We will use the following two lemmas.

Lemma 14 [M-II]. Let d ≥ 3. The number of integers 1 ≤ g ≤ x such that D(g) has no prime divisor p with p ≡ 1(mod d) is O_{d}(x log^{−1/φ(d)} x). The same assertion holds with D(g) replaced by D(−g).

The following simple result is also needed.

Lemma 15 If p|v with p ≡ 1(mod d) and p ∤ m, then

∑_{{t≡a(mod d) \atop t|v, ( \frac{v}{t} ,m)|r}} μ(\frac{v}{t}) = 0.

Proof. Let p^{e}||v. Put v_{1} = v/p^{e}. Then

∑_{{t≡a(mod d) \atop t|v, ( \frac{v}{t} ,m)=α}} μ(\frac{v}{t}) = ∑_{j=0}^{e} ∑_{{t≡a(mod d) \atop t|v_{1}, ( \frac{v_{1}}{t} ,m)=α}} μ(p^{j} \frac{v_{1}}{t}) = ∑_{j=0}^{1}(−1)^{j} ∑_{{t≡a(mod d) \atop t|v_{1}, ( \frac{v_{1}}{t} ,m)=α}} μ(\frac{v_{1}}{t}) = 0.

Proposition 5 (GRH). Let α = (a, d) and d_{1} = d/α. Suppose that g ∈ G and D(g) has a prime divisor p with p ≡ 1(mod d_{1}) and p ∤ α, then ρ_{g}(a, d) = ρ(a, d).

Proof. On GRH we have (see [M-I])

ρ_{g}(a, d) = ∑_{t≡a(mod d)} ∑_{v=1}^{∞} \frac{μ(v)}{[K_{vt,vt} : ℚ]} = ∑_{w=1}^{∞} \frac{∑_{t|w, t≡a(mod d)} μ(\frac{w}{t})}{[K_{w,w} : ℚ]}.

By [M-Av] we have

ρ(a, d) = ∑_{w=1}^{∞} \frac{∑_{t|w, t≡a(mod d)} μ(\frac{w}{t})}{wφ(w)}.

Let n_{1} be as in Lemma 3 (note that n_{1} = [2, D(g)]). The assumption that g ∈ G ensures, by Lemma 3, that

ρ_{g}(a, d) = ρ(a, d) + ∑_{n_{1}|w} \frac{∑_{t|w, t≡a(mod d)} μ(\frac{w}{t})}{wφ(w)}.

= ρ(a, d) + ∑_{\frac{n_{1}}{(n_{1},α)} |w} \frac{∑_{t|w, t≡a/α(mod d_{1})} μ(\frac{w}{t})}{wαφ(wα)}.

If p|D(g), p ≡ 1(mod d_{1}) and p ∤ α, then p|\frac{n_{1}}{(n_{1},α)} and so p divides every w occurring in the latter sum and hence, by Lemma 15, this sum will equal zero. □

Proposition 6 (GRH). Let α = (a, d) and d_{1} = d/α. For almost all integers g we have ρ_{g}(a, d) = ρ(a, d). More precisely, if d_{1} ≤ 2, then there are at most O_{d}(\sqrt{x}) integers g with |g| ≤ x such that ρ_{g}(a, d) ≠ ρ_{g}(a, d). If d_{1} ≥ 3, then there are at most O_{d}(xlog^{−1/φ(d_{1})} x) integers g with |g| ≤ x such that, moreover, ρ_{g}(a, d) ≠ ρ(a, d).

Proof. In case d_{1} ≤ 2, then ρ_{g}(a, d) = ρ(a, d) for those g for which g ∈ G and D(g) is not in a certain finite set by the previous proposition. The set of remaining g is of size O_{d}(\sqrt{x}). (Note that there are at most O(\sqrt{x}) integers |g| ≤ x that are not in G and that, for a fixed integer g_{1}, there at most O(\sqrt{x}) integers g_{2} satisfying D(g_{2}) = D(g_{1}).) If d_{1} ≥ 3 we invoke Lemma 14 with d = d_{1}. □

In case d|2(a, d), that is d_{1} ≤ 2, the latter result can be improved. Then ρ(a, d) is a rational number and, more precisely, we have:

Lemma 16 [M-Av]. Let d ≥ 1. Then

ρ(0, d) = \frac{1}{dφ(d)} and ρ(d, 2d) = \{ \begin{matrix}ρ(0, 2d) & if d is odd; \\ 3ρ(0, 2d) & if d is even. \end{matrix}

In this case we can both improve the error term and drop the GRH assumption in Proposition 6.

Proposition 7 We have at most O_{d}(\sqrt{x}) integers g with |g| ≤ x such that ρ_{g}(0, d) ≠ ρ(0, d). Similarly we have at most O_{d}(\sqrt{x}) integers g with |g| ≤ x such that ρ_{g}(d, 2d) ≠ ρ(d, 2d).

Proof. It is not difficult to show that ρ_{g}(0, d) = 1/[K_{d,d} : ℚ] and hence ρ_{g}(d, 2d) = 1/[K_{d,d} : ℚ] − 1/[K_{2d,2d} : ℚ]. Using Lemma 3, we infer that there are at most finitely many squarefree integers g for which ρ_{g}(0, d) ≠ 1/dφ(d) = ρ(0, d) (where the equality is a consequence of Proposition 16) and that, similarly, there are at most finitely many squarefree integers g for which ρ_{g}(0, d) ≠ 1/dφ(d) − 1/2dφ(2d) = ρ(0, 2d) (where the equality is a consequence of Proposition 16). From this the result easily follows. □

Theorem 1 only seems to have an analog for ρ_{g}(a, d) in case d|a:

Proposition 8 If q is an odd prime dividing d_{1}, then ρ_{g}(0, qd_{1}) = ρ_{g}(0, d_{1})/q^{2} (on GRH) and ρ(0, qd_{1}) = ρ(0, d_{1})/q^{2}.

Proof. The first equality is an immediate consequence of (1) and [K_{vqd_{1},vqd_{1}} : ℚ] = q^{2}[K_{vd_{1},vd_{1}} : ℚ] which holds by Lemma 3 for arbitrary v. The second equality is a consequence of Lemma 16. □

7 Proof of Theorem 3

The idea of the proof of Theorem 3 is to show that if g ∈ G and D(g) contains a prime divisor p with p ≡ 1(mod k_{1}(d)), p | d, then ∗_{g}(a, d) = ∗(a, d). Lemma 14 then allows us to finish the proof. Thus, in outline, the proof is similar to that of Proposition 6 in the previous section. Note that in case ∗ = ρ we are done by Proposition 6.

Lemma 17 Let d ≥ 2. Suppose that g ∈ G and that D(g) has a prime divisor p with p ≡ 1(mod d/(a, d)) and p ∤ d, then δ_{g}^{(0)}(a, d) = δ(a, d).

Proof. By the definition of δ_{g}^{(0)}(a, d) and Lemma 3, we find that

δ_{g}^{(0)}(a, d) = ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1 \atop (n,d)|a}}^{∞} \frac{μ(n)}{φ([d, n]t)nt} + ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{n=1, (n,d)|a \atop n_{d/(d,n)}|[d,n]t}}^{∞} \frac{μ(n)}{φ([d, n]t)nt}.

In the first double sum we recognize δ(a, d). Let us denote the second double sum by E_{3}. By the remark following Lemma 3 we have n_{d/(d,n)} = [2^{ν_{2}(d/(d,n))+1}, D(g)]. Note that n_{d/(d,n)}|[d, n]t iff 2|nt and D(g)|[d, n]t. Following the argument of Proposition 7 of [M-Av] and dragging along the conditions 2|nt and D(g)|[d, n]t we obtain

E_{3} = ∑_{α|(a,d)} \frac{μ(α)}{α} ∑_{{t=1 \atop (1+ta,d)=1}}^{∞} ∑_{{m=1, (m,d)=1 \atop D(g)|dmt, 2|αmt}}^{∞} \frac{μ(m)}{φ(dmt)mt}.

Making the substitution mt = v we obtain

E_{3} = ∑_{α|(a,d)} \frac{μ(α)}{α} ∑_{{v=1 \atop D(g)|dv, 2|αv}}^{∞} \frac{∑_{t|v, (1+ta,d)=1, ( \frac{v}{t} ,d)=1} μ(\frac{v}{t})}{φ(dv)v}.

If p|D(g), p ≡ 1(mod d/(a, d)) and p ∤ d, then p divides every v occurring in the latter sum and hence, by Lemma 15, we deduce that E_{3} = 0 (note that the set of integers t satisfying (1 + ta, d) = 1 is an union of arithmetic progressions of modulus d/(a, d)). □

Remark. This lemma when combined with Theorem 1 shows, on GRH, that if g ∈ G, D(g) has a prime divisor p with p ≡ 1(mod k_{2}(d)) and p ∤ d, then δ_{g}^{(0)}(a, d) = δ(a, d).

The next few results are concerned with when the equality δ_{g}(a, d) = δ_{g}^{(0)}(a, d) holds.

Proposition 9 (GRH). Suppose that d is odd and (d, D(g_{0})) = 1. Then δ_{g}(a, d) = δ_{g}^{(0)}(a, d).

Proof. The condtions (d, D(g_{0})) = 1 and d is odd ensure that γ_{g}(dt_{d}, nt) = 1, respectively ϵ_{3}(1+ta, dt_{d}, nt) = 1 for all n and t (cf. the remark following Theorem 6). Now apply Theorem 6. □

Lemma 18 (GRH) Suppose that g ∈ G and that D(g) has a prime divisor p with p ≡ 1(mod k_{1}(d)) and p ∤ d, then δ_{g}(a, d) = δ_{g}^{(0)}(a, d).

Proof. Let us first consider the case where d is odd or 8|d. It follows from Theorem 1 that if δ_{g}(a, k_{1}(d)) = δ_{g}^{(0)}(a, k_{1}(d)), then δ_{g}(a, d) = δ_{g}^{(0)}(a, d) and thus, w.l.o.g., we may assume that k_{1}(d) = d. By (10) we have

δ_{g}(a, d) = δ_{g}^{(0)}(a, d) − ∑_{{(1+ta,d)=1 \atop ( \frac{δ}{1+ta})=−1}} ∑_{D(g)∤nt, D(g)|[d,n]t ; {ν_{2}(nt)≥ν_{2}(h)+1 \atop (d,n)|a}} \frac{μ(n)}{[K_{[d,n]t,nt} : ℚ]},

for some δ|d. Since δ is a fundamental discriminant dividing d it follows from the reciprocity law for the Kronecker symbol that the sum over t is a sum over a certain set of arithmetic progressions modulo d. Let us consider the inner sum where t runs over one such arithmetic progression, say t ≥ 1 and t ≡ b(mod d). Setting (d, n) = α and nt = v we obtain for the inner sum:

∑_{α|(a,d)} ∑_{{D(g)∤v,D(g)| \frac{d}{α} v \atop ν_{2}(v)≥ν_{2}(h)+1}} \frac{∑_{t≡b(mod d), ( \frac{v}{t} ,d)=α} μ(v/t)}{[K_{\frac{d}{α} v,v} : ℚ]}.

Now the assumption on D(g) implies, by Lemma 15, that for all v occurring in the sum the inner sum is zero. Hence we infer that δ_{g}(a, d) = δ_{g}^{(0)}(a, d).

In case d ≡ 4(mod 8) we note that δ_{g}(a, d) = δ_{g}(a, 2d) + δ_{g}(a + d, 2d) and δ_{g}^{(0)}(a, d) = δ_{g}^{(0)}(a, 2d) + δ_{g}^{(0)}(a + d, 2d). Hence it suffices to show that δ_{g}(a, 2d) = δ_{g}^{(0)}(a, 2d) and δ_{g}(a + d, 2d) = δ_{g}^{(0)}(a + d, 2d). Since 8|2d and k_{1}(2d) = k_{1}(d) we are reduced to the previous case. The remaining case where 2||d can be dealt with similarly. □

Theorem 7 (GRH). For almost all integers g we have ∗_{g}(a, d) = ∗(a, d), with ∗ is δ or δ^{(0)}. More precisely, there are at most O_{d}(x log^{−1/φ(k_{2}(d))} x) integers g with |g| ≤ x such that δ_{g}^{(0)}(a, d) ≠ δ(a, d). There are at most O_{d}(x log^{−1/φ(k_{1}(d))} x) integers g with |g| ≤ x such that δ_{g}(a, d) ≠ δ(a, d).

Proof. This follows from the remark following Lemma 17, Lemma 18 and Lemma 14 (cf. the proof of Proposition 6). □

Remark. For various choices of a and d, the terms φ(k_{2}(d)) and φ(k_{1}(d)) can be sometimes replaced by smaller numbers, resulting in a smaller error term.

Proof of Theorem 3. Combine Theorem 7 and Proposition 6. □

8 The proof of Theorem 4

For any Dirichlet character χ, we let h_{χ} denote the Dirichlet convolution of χ and μ. For properties of h_{χ} the reader is referred to [M-I].

Lemma 19 Let α, β, d, d_{1} and r be arbitrary positive integers with (α, β) = 1. Write v = v_{1}v_{d} with v_{1} = v/(v, d^{∞}) and v_{d} = (v, d^{∞}). Then

∑_{{t=1 \atop t≡α(mod β)}}^{∞} ∑_{{n=1 \atop (n,d)=1}}^{∞} \frac{μ(n)}{[K_{d_{1}rnt,rnt} : ℚ]} = \frac{1}{φ(β)} ∑_{χ∈G_{β}} \overline{χ(α)} ∑_{v=1}^{∞} \frac{χ(v_{d})h_{χ}(v_{1})}{[K_{d_{1}rv,rv} : ℚ]}.

Proof. We have

φ(β) ∑_{{t=1 \atop t≡α(mod β)}}^{∞} ∑_{{n=1 \atop (n,d)=1}}^{∞} \frac{μ(n)}{[K_{d_{1}rnt,rnt} : ℚ]} = ∑_{v=1}^{∞} \frac{∑_{t≡α(mod β), t|v, (v/t,d)=1} μ(v/t)}{[K_{d_{1}vr,vr} : ℚ]}

= ∑_{χ∈G_{β}} \overline{χ(α)} ∑_{v=1}^{∞} \frac{∑_{t|v, (v/t,d)=1} χ(t)μ(v/t)}{[K_{d_{1}rv,rv} : ℚ]}

= ∑_{χ∈G_{β}} \overline{χ(α)} ∑_{δ|d^{∞}} χ(δ) ∑_{{v=1 \atop (v,d)=1}}^{∞} \frac{h_{χ}(v)}{[K_{d_{1}δrv,δrv} : ℚ]}

= ∑_{χ∈G_{β}} \overline{χ(α)} ∑_{v=1}^{∞} \frac{χ(v_{d})h_{χ}(v_{1})}{[K_{d_{1}rv,rv} : ℚ]}.

This concludes the proof. □

Note that the inner three sums in the next result are finite sums. The complicated nature of the result suggests that the arithmetic function h_{χ}(v) might not be the proper one to work with. However, in the analysis of d = 3, 4 [M-I] and d is prime [M-II], this function turned out to be of crucial importance.

Theorem 8 Let a and d ≥ 1 be arbitrary integers. Then

δ_{g}^{(0)}(a, d) = ∑_{{0<t_{1}≤d \atop (1+t_{1}a,d)=1}} ∑_{χ∈G_{\frac{d}{(t_{1},d)}}} \frac{\overline{χ(\frac{t_{1}}{(t_{1},d)})}}{φ(\frac{d}{(t_{1},d)})} ∑_{α|(a,d)} μ(α) ∑_{v=1}^{∞} \frac{χ(v_{d})h_{χ}(v_{1})}{[K_{d(t_{1},d)v,d(t_{1},d)αv} : ℚ]}.

Proof. Note that

∑_{{n=1 \atop (n,d)|a}}^{∞} \frac{μ(n)}{[K_{[d,n]t,nt} : ℚ]} = ∑_{α|(a,d)} ∑_{{n=1 \atop (n,d)=α}}^{∞} \frac{μ(n)}{[K_{dnt/(d,n),nt} : ℚ]}

= ∑_{α|(a,d)} μ(α) ∑_{{n=1 \atop (n,d)=1}}^{∞} \frac{μ(n)}{[K_{dnt,αnt} : ℚ]},

cf. the proof of Part 2 of Theorem 1 [M-Av]. On invoking Lemma 19 the proof is then easily completed. □

Lemma 20 We have δ_{g}^{(0)}(a, d) = ∑_{χ∈G_{d}} c_{χ}A_{χ}, where c_{χ} ∈ ℚ(ζ_{o_{χ}}) can be explicitly computed.

The proof of this result can be easily inferred from the next lemma in combination with Theorem 8 and the observation that if a Dirichlet character χ mod d is the lift of a Dirichlet character χ′ mod d_{1}, then A_{χ}/A_{χ′} is rational.

Lemma 21 Let v_{1} and v_{d} be as in Lemma 19. We have

∑_{v=1}^{∞} \frac{χ(v_{d})h_{χ}(v_{1})}{[K_{d_{1}rv,rv} : ℚ]} = c_{χ}A_{χ},

where c_{χ} ∈ ℚ(ζ_{o_{χ}}) can be explicitly computed.

Proof. Using Lemmas 10 and 11 of [M-I] it is easily inferred that

∑_{(r,v)=1} \frac{h_{χ}(v)}{[K_{sv,v} : ℚ]} = c′_{χ}A_{χ},

where c′_{χ} can be effectively computed. The proof of the present lemma is a variation of this. □

Proof of Theorem 4.

1) Follows from Lemma 20 and Theorem 1.

2) (Sketch). The same trick as in the proof of Lemma 18 can be applied to reduce to the case where d is odd or 8|d. In these cases comparatively easy explicit formulae for δ_{g}(a, d) can be written down. Each of them can be expressed in terms of a function very closely related to h_{χ}(v), this being possible due to the fact that the t arising in these formulae run over an union of arithmetic progressions modulo a divisor of 4d. We then get a finite combination of sums not unlike those in Lemma 21 that, like the sums in Lemma 21 can be expressed in terms of A_{χ}. In case 8|d it suffices by (11) and Theorem 1 to only consider the case g > 0. As the amount of work involved is quite considerable and no new ideas are involved, I suppress the details here.

3) This is Theorem 5 of [M-I]. □

9 Equidistribution results

Let N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x) denote the number of primes p ≤ x with p ≡ a_{1}(mod d_{1}) such that ν_{p}(g) = 0 and the order of g modulo p is congruent to a_{2}(mod d_{2}). Although N_{g}(a, d)(x) does not seem to have equidistribution properties, results in this direction can be proved for N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x). In [M-II] it is established that, on GRH, N_{g}(a_{1}, d_{1}; a_{2}, d_{2}) has a density δ_{g}(a_{1}, d_{1}; a_{2}, d_{2}).

Recall that k(d) denotes the squarefree kernel of d. The result below generalizes results in [M-I] and [M-II].

Theorem 9 (GRH). Suppose that (a, d) = (b, d) = 1.

1) If d is odd, then ρ_{g}(1, k(d); a, d) = ρ_{g}(1, k(d); b, d).

2) If d is even, then ρ_{g}(1, 2k(d); a, d) = ρ_{g}(1, 2k(d); b, d).

Proof. A variation of Theorem 6 yields that

ρ_{g}(1, k(d); a, d) = ∑_{k(d)|t} ∑_{{n=1 \atop (n,d)=1}}^{∞} \frac{μ(n)ϵ_{4}(a, n, t)}{[K_{[d,n]t,nt} : ℚ]},  (14)

where ϵ_{4}(a, n, t) = c_{g}(1 + ta, dt, nt) = (1 + ϵ_{3}(1 + ta, dt_{d}, nt)(\frac{γ_{g}(dt_{d},nt)}{1+ta}))/2 ∈ \{0, 1\}.

1) The assumption that d be odd, implies that dt_{d} is odd and hence the exceptional case never arises and we have ϵ_{3}(1 + ta, dt_{d}, nt) = 1 for the values of n and t we sum over. Using that all quadratic subfields of ℚ(ζ_{dt_{d}}) are contained in ℚ(ζ_{k(d)}) and since k(d)|t, it follows that σ_{1+ta}(ζ_{k(d)}) = ζ_{k(d)} and so certainly σ_{1+ta}(\sqrt{γ_{g}(dt_{d}, nt)}) = \sqrt{γ_{g}(dt_{d}, nt)} and hence (γ_{g}(dt_{d}, nt)/1 + ta) = 1 (alternatively one can use quadratic reciprocity to infer this). It follows that ϵ_{4}(a, n, t) = 1 for all the values of n and t we sum over. Similarly we have ϵ_{4}(b, n, t) = 1 and it thus follows that

ρ_{g}(1, k(d); a, d) = ρ_{g}(1, k(d); b, d) = ∑_{k(d)|t} ∑_{{n=1 \atop (n,d)=1}}^{∞} \frac{μ(n)}{[K_{[d,n]t,nt} : ℚ]}.

2) In this case the analog of (14) holds, but with the condition k(d)|t replaced by 2k(d)|t. Now the exceptional case may arise. In that case we have ϵ_{3}(1 + ta, dt_{d}, nt) = (−1)^{ta/t_{d}} = −1 and, similarly, ϵ_{3}(1 + tb, dt_{d}, nt) = −1. Using that all quadratic subfields of ℚ(ζ_{dt_{d}}) are contained in ℚ(ζ_{4k(d)}) and since 4k(d)|t(a−b) (since 2k(d)|t and a − b is even), it follows that σ_{1+ta}(ζ_{4k(d)}) = σ_{1+tb}(ζ_{4k(d)}) and so certainly σ_{1+ta}(\sqrt{γ_{g}(dt_{d}, nt)}) is equal to σ_{1+tb}(\sqrt{γ_{g}(dt_{d}, nt)}) and hence (γ_{g}(dt_{d}, nt)/1 + ta) = (γ_{g}(dt_{d}, nt)/1 + tb). It follows that ϵ_{4}(a, n, t) = ϵ_{4}(b, n, t) for all the values of n and t we sum over in (14) and hence ρ_{g}(1, 2k(d); a, d) = ρ_{g}(1, 2k(d); b, d). □

Acknowledgement. This is the final paper concluding a rather extensive project. I like to thank Dr. Paul Tegelaar for his friendship, continuous support, interest, computer assistance and proofreading. The project was begun whilst the author was at the University of Amsterdam, he likes to thank Prof. Eric Opdam for the opportunity to work for several years in his PIONIER-group (funded by NWO).

References

[CM] K. Chinen and L. Murata, On a distribution property of the residual order of amod p), I, II J. Number Theory 105 (2004), 60–81, 82-100.

[GP] A.J. Granville and P.A.B. Pleasants, Aurefeuillian factorization revisited, preprint submitted to Mathematics of Computation.

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

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

[M-Fi] P. Moree, Convoluted convolved Fibonacci numbers, J. Integer Seq. 7 (2004), Article 04.2.2, 16 pp. (electronic)

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

[M-I] P. Moree, On the distribution of the order and index of g(mod p) over residue classes I, arXiv:math.NT/0211259, J. Number Theory, to appear.

[M-II] P. Moree, On the distribution of the order and index of g(mod p) over residue classes II, arXiv:math.NT/0404339, submitted.

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

[P] F. Pappalardi, On Hooley’s theorem with weights, Number theory, II (Rome, 1995), Rend. Sem. Mat. Univ. Politec. Torino 53 (1995), 375– 388.

[Wa] S.S. Wagstaff, jr., Pseudoprimes and a generalization of Artin’s conjecture, Acta Arith. 41 (1982), 141–150.

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

[Wi2] K. Wiertelak, On the density of some sets of primes p, for which n|ord_{p}(a), Funct. Approx. Comment. Math. 28 (2000), 237–241.