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

Pieter Moree

Abstract

For a fixed rational number g ∉ {−1, 0, 1} and integers a and d we consider the set N_{g}(a, d) of primes p for which the order of g(mod p) is congruent to a(mod d). It is shown, assuming the Generalized Riemann Hypothesis (GRH), that this set has a natural density δ_{g}(a, d). Moreover, δ_{g}(a, d) is computed in terms of degrees of certain Kummer extensions. Several properties of δ_{g}(a, d) are established in case d is a power of an odd prime.

1 Introduction

Let g ∉ {−1, 0, 1} be a rational number (this assumption on g will be maintained throughout this paper). For u a rational number, let v_{p}(u) denote the exponent of p in the canonical factorisation of u (throughout the letter p will be used to indicate prime numbers). If v_{p}(g) = 0, then there exists a smallest positive integer k such that g^{k} ≡ 1(mod p). We put ord_{p}(g) = k. This number is the (residual) order of g(mod p). The index of the subgroup generated by g mod p inside the multiplicative group of residues mod p, |(ℤ/pℤ)^{×} : ⟨g(mod p)⟩|, is denoted by r_{g}(p) and called the (residual) index mod p of g. Note that ord_{g}(p)r_{g}(p) = p − 1.

We let N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x) count the number of primes p ≤ x with p ≡ a_{1}(mod d_{1}) and ord_{g}(p) ≡ a_{2}(mod d_{2}). For convenience denote N_{g}(0, 1; a, d)(x) by N_{g}(a, d)(x). Although our main interest is in the behaviour of N_{g}(a, d)(x) it turns out that sometimes it is fruitful to partition N_{g}(a, d)(x) in sets of the form N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x) with a well-chosen d_{1}. Let r|s be positive integers. By K_{s,r} we denote the number field ℚ(ζ_{s}, g^{1/r}), where ζ_{s} = exp(2πi/s). The main result of this paper is as folows (for notational convenience (a, b), [a, b] will be written for the greatest common divisor, respectively lowest common multiple of a and b and by (GRH) we indicate that GRH is assumed).

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

Theorem 1 (GRH). Let (a_{1}, d_{1}) = 1. Then

N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x) = δ_{g}(a_{1}, d_{1}; a_{2}, d_{2})\frac{x}{log x} + O_{d_{1},d_{2},g}(\frac{x}{log^{3/2} x}),

for a number δ_{g}(a_{1}, d_{1}; a_{2}, d_{2}) that is given by (13).

Specialising to a_{1} = 0 and d_{1} = 1 the following result is obtained.

Theorem 2 (GRH). We have

N_{g}(a, d)(x) = δ_{g}(a, d)\frac{x}{log x} + O_{d,g}(\frac{x}{log^{3/2} x}),

with

δ_{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} : ℚ]},  (1)

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

In part I [5] this result was established, by a slightly different method, in case 3 ≤ d ≤ 4 and explicit formulae for δ_{g}(a, 3) and δ_{g}(a, 4) were derived. By a different method some of the results for d = 4 with weaker error term and restricted values of g are established in [1] and [6], see also Corollary 1 of [5].

It turns out that the numbers c_{g} appearing in (1) have a strong tendency to equal one. This motivates the following definition:

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

For example, if d|a, then σ_{1+ta} is the identity element of the Galois group of ℚ(ζ_{dt}) over ℚ and then trivially δ_{g}(a, d) = δ_{g}^{(0)}(a, d).

Generically the degree [K_{[d,n]t,nt} : ℚ] appearing in (2) equals φ([d, n]t)nt. On substituting this value in (2) a number δ(a, d) is obtained that no longer depends on g:

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

In [3] it is shown that δ(a, d) is the average density of elements in a finite field having order ≡ a(mod d). The number δ(a, d) can be a regarded as a naïve heuristic for δ_{g}(a, d).

In case d is a power of an odd prime q the coefficients c_{g} are easily evaluated. This case is considered in extenso in Section 4. There it is shown, for example, that δ_{g}(a, q^{s}) = δ(a, q^{s}) for almost all integers g with |g| ≤ x.

This paper is part of a sequal of three papers, each one considering a larger class of moduli d. Due to the inherit arithmetic complexity, results in later papers are less explicit than those in the earlier ones. Thus only part of the results in the earlier papers follows from those of the later ones.

2 Preliminaries

2.1 Some notation

We recall some notation from our earlier papers [5, 3] on this topic. For any Dirichlet character χ of (ℤ/dℤ)^{∗}, we let h_{χ} denote the Dirichlet convolution of χ and μ. As usual we let L(s, χ) denote the Dirichlet L-series for χ. For properties of h_{χ} the reader is referred to [5]. From [5] we furthermore recall that

C_{χ}(h, r, s) = ∑_{(r,v)=1, s|v}^{∞} \frac{h_{χ}(v)(h, v)}{vφ(v)} and A_{χ} = ∏_{p:χ(p)≠0} (1 + \frac{[χ(p) − 1]p}{[p^{2} − χ(p)](p − 1)}) .

The constants A_{χ} turn out to be the basic constants for this problem. In many cases A_{χ} ∈ ℂ\ℝ, see [3, 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 [4]. The latter expansion of A_{χ} can be used to approximate A_{χ} with high numerical accuracy (see [3, Section 6]).

In [5, Lemma 10] it is shown that C_{χ}(h, r, s) = cA_{χ}, where c can be explicitly written down and is in ℚ(ζ_{o_{χ}}). Here o_{χ} is the order of the character χ, i.e. the smallest positive integer k such that χ^{k} = χ_{0}, the trivial character.

We recall from [5] that, if (b, f) = 1,

∑_{{t≡b(mod f) \atop t|v}} μ(\frac{v}{t}) = \frac{1}{φ(f)} ∑_{χ∈G_{f}} \overline{χ(b)}h_{χ}(v),  (4)

where the sum is over the characters in the character group G_{f} of (ℤ/ℤf)^{∗}.

2.2 Preliminaries on algebraic number theory

We first review some properties of the Kronecker symbol (a rarely discussed symbol in books on number theory). To this end we first recall the definition of the Legendre and the Jacobi symbol. By definition the Legendre symbol (\frac{n}{p}), where p ≥ 3 is a prime number and n ∈ ℤ, p ∤ n, is equal to 1 if n is a quadratic residue mod p, and to −1 otherwise.

Let m > 0 be an odd integer relatively prime to n. The Jacobi symbol (\frac{n}{m}) is defined as the product of the Legendre symbols (\frac{n}{m}) = (\frac{n}{p_{1}} ) ⋯ (\frac{n}{p_{s}}), where m = p_{1} ⋯ p_{s} and each p_{i} is a prime.

The Kronecker symbol (\frac{c}{d}) is defined for c ∈ ℤ, c ≡ 0(mod 4) or c ≡ 1(mod 4), c not a square, and d ≥ 1 an integer; if b = p_{1}p_{2} ⋯ p_{s} is the decomposition of b as a product of primes, we put (\frac{a}{−b}) = (\frac{a}{b}) = (\frac{a}{p_{1}} )(\frac{a}{p_{2}} ) ⋯ (\frac{a}{p_{s}}). If p is an odd prime (\frac{a}{p}) = 0 when p divides a, while (\frac{a}{p}) is the Legendre symbol (\frac{a}{p}) when p does not divide a and, finally, (\frac{a}{2}) = 1 when a ≡ 1(mod 8), while (\frac{a}{2}) = −1 when a ≡ 5(mod 8). Then if a and b are such that both the Jacobi and Kronecker symbols are defined, then these symbols coincide. If a is odd, then (\frac{a}{2}) = Jacobi symbol (\frac{2}{|a|}). If b > 0, (a, b) = 1, a is odd, then (\frac{a}{b}) = (\frac{b}{|a|}), where the symbol on the right hand side is the Jacobi symbol. Most importantly, if b > 0, (a, b) = 1 and a = 2^{r}ã with ã odd, then

(\frac{a}{b}) = (\frac{2}{b})^{r}(−1)^{\frac{ã−1}{2} \frac{b−1}{2}} (\frac{b}{|a|}),

where the symbols on the right hand side are Jacobi symbols.

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 (for a proof see e.g. [10, p. 263]).

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

Consider the cyclotomic extension ℚ(ζ_{f}) of the rationals. 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:

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

Proof. Using Lemma 1 we see that we can restrict to the case where f = |Δ_{d}|. Define χ by χ(b) = σ_{b}(\sqrt{d})/\sqrt{d}, 1 ≤ b ≤ |Δ_{d}|, (b, Δ_{d}) = 1. Then χ is the unique non-trivial character of the character group of ℚ(\sqrt{d}). As is well-known (see e.g. [7, p. 437]), the primitive character induced by this is (\frac{Δ_{d}}{b}). Using Lemma 1, we see that χ is a primitive character mod |Δ_{d}|. Thus χ(b) = (\frac{Δ_{d}}{b}). Now σ_{b}|_{ℚ(\sqrt{d})} = id iff χ(b) = (\frac{Δ_{d}}{b}) = 1. □

Remark 1. Another way to prove Lemma 2 is to note that σ_{b}|_{ℚ(\sqrt{d})} = id iff there exists a prime p ≡ b(mod f) that splits completely in ℚ(\sqrt{d}). It is well-known that there exists a prime p ≡ b(mod f) that splits completely in the field ℚ(\sqrt{d}) iff (\frac{Δ_{d}}{p}) = 1 (see e.g. [10, p. 236]). Since (\frac{Δ_{d}}{p}) = (\frac{Δ_{d}}{b}), the result follows.

Remark 2. The action of σ on \sqrt{d} can also be determined by relating \sqrt{d} to a Gauss sum ‘living’ in ℚ(ζ_{f}). It is straigthforward to determine the action of σ on such a Gauss sum.

2.3 Preliminaries on field degrees

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_{1}}). The notation D(g_{1}) along with the notation g_{0}, h and n_{r} introduced in the next lemma will reappear again and again in the sequel.

Lemma 3 [5]. 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)}.

From the latter lemma many consequences can be deduced.

Lemma 4 Let v, w and z be natural numbers with v|w and with z an odd divisor of w. Then [K_{zw,v} : ℚ] = z[K_{w,v} : ℚ].

Proof. The proof easily follows from Lemma 3 on observing that the odd part of n_{r} is squarefree and that φ(zw) = zφ(w). □

Lemma 5 The intersection ℚ(ζ_{f}) ∩ K_{v,v} is equal to ℚ(ζ_{(f,v)}) or a quadratic extension thereof. More precisely,

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

Proof. Clearly this intersection field is abelian and contains ℚ(ζ_{(f,v)}). We have

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

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

[ℚ(ζ_{f}) ∩ K_{v,v} : ℚ(ζ_{(f,v)})] = \frac{[ℚ(ζ_{f}) ∩ K_{v,v} : ℚ]}{φ((f, v))} = \frac{ϵ([f, v], v)}{ϵ(v, v)}.  (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_{v,v} is equal to ℚ(ζ_{(f,v)}) or a quadratic extension thereof. □

Lemma 6 Let q be an odd prime, s ≥ 0 and suppose q ∤ v. Put q^{∗} = (\frac{−1}{q})q. Consider the following conditions

i) q|D(g_{0}), s = 0 and \frac{n_{1}}{q} |v. ii) If g < 0 and 2|v, then 2^{ν_{2}(h)+1}|v. We have

ℚ(ζ_{q^{s+1}}) ∩ K_{q^{s}v,q^{s}v} = \{ \begin{matrix}ℚ(\sqrt{q^{∗}}) & if both i and ii are satisfied; \\ ℚ(ζ_{q^{s}}) & otherwise. \end{matrix}

Proof. By Lemma 5 we have [ℚ(ζ_{q^{s+1}})∩K_{q^{s}v,q^{s}v} : ℚ(ζ_{q^{s}})] = ϵ(q^{s+1}v, q^{s}v)/ϵ(q^{s}v, q^{s}v) and hence, by Lemma 3, ℚ(ζ_{q^{s+1}})∩K_{q^{s}v,q^{s}v} is a quadratic extenstion of ℚ(ζ_{q^{0}}) = ℚ if conditions i and ii are satisfied and ℚ(ζ_{q^{s+1}})∩K_{q^{s}v,q^{s}v} = ℚ(ζ_{q^{s}}) otherwise. Since ℚ(\sqrt{q^{∗}}) is the unique quadratic subfield of ℚ(ζ_{q}), the result now follows. □

Remark 3. If g > 0 or g < 0 and v is odd, then condition ii is vacuously satisfied.

Lemma 7 Let n be squarefree. Put t_{d} = ∏_{p|(t,d)} p^{ν_{p}(t)}. 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{c_{g}(1 + ta, dt, nt)}{[K_{[d,n]t,nt} : ℚ]} = \frac{c_{g}(1 + ta, dt_{d}, nt)}{[K_{[d,n]t,nt} : ℚ]}.  (7)

Proof. This follows from Chebotarev’s density theorem 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. □

Lemma 8 Assume that (b, f_{1}f_{2}) = 1, f_{1}|f_{2} and

\frac{[K_{[f_{1},v],v} : ℚ]}{φ(f_{1})} = \frac{[K_{[f_{2},v],v} : ℚ]}{φ(f_{2})}.  (8)

Then c_{g}(b, f_{1}, v) = c_{g}(b, f_{2}, v).

Proof. By (5) the assumption (8) implies that

[ℚ(ζ_{f_{1}}) ∩ K_{v,v} : ℚ] = [ℚ(ζ_{f_{2}}) ∩ K_{v,v} : ℚ].

This, together with the assumption that f_{1}|f_{2} ensures that ℚ(ζ_{f_{1}}) ∩ K_{v,v} = ℚ(ζ_{f_{2}}) ∩ K_{v,v} = L, say, whence L = ℚ(ζ_{(f_{1},f_{2})}) ∩ K_{v,v}. Since the map σ ∈ Gal(ℚ(ζ_{f_{1}})/ℚ) that sends ζ_{f_{1}} to ζ_{f_{1}}^{b} and the map σ′ ∈ Gal(ℚ(ζ_{f_{2}})/ℚ) that sends ζ_{f_{2}} to ζ_{f_{2}}^{b} act in the same way when restricted to ℚ(ζ_{(f_{1},f_{2})}), it follows that σ_{b}|_{ℚ(ζ_{f_{1}})∩K_{v,v}} = σ′_{b}|_{ℚ(ζ_{f_{2}})∩K_{v,v}} and hence c_{g}(b, f_{1}, v) = c_{g}(b, f_{2}, v). □

2.4 Remaining preliminaries

The following result is due to Wirsing [13].

Lemma 9 [13]. Suppose f(n) is a multiplicative function such that f(n) ≥ 0, for n ≥ 1, and such that there are constants γ_{1} and γ_{2}, with γ_{2} < 2, such that for every prime p and every ν ≥ 2, f(p^{ν}) ≤ γ_{1}γ_{2}^{ν}. Assume that as x → ∞,

∑_{p≤x} f(p) ∼ τ \frac{x}{log x},

where τ > 0 is a constant. Then, as x → ∞,

∑_{n≤x} f(n) ∼ \frac{e^{−γτ}}{Γ(τ)} \frac{x}{log x} ∏_{p≤x} (1 + \frac{f(p)}{p} + \frac{f(p^{2})}{p^{2}} + \frac{f(p^{3})}{p^{3}} + ⋯) ,

where γ is Euler’s constant and Γ(τ) denotes the gamma-function.

We use it to establish the following lemma.

Lemma 10 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).

Proof. Denote the number of integers counted in the formulation of the lemma by T_{d}(x). We define a multiplicative function f_{d}(n) as follows:

f_{d}(p^{α}) = \{ \begin{matrix}0 & if 2 ∤ α and p ≡ 1(mod d); \\ 1 & otherwise. \end{matrix}

Note that T_{d}(x) = ∑_{g≤x} f_{d}(g). Using Lemma 9, it then follows that

T_{d}(x) = O_{d} (\frac{x}{log x} ∏_{p≤x} (1 + \frac{f_{d}(p)}{p} + \frac{f_{d}(p^{2})}{p^{2}} + ⋯)) = O_{d} (\frac{x}{log x} ∏_{{p≤x \atop p≢1(mod d)}}(1 + \frac{1}{p})) .

Since by Mertens’ theorem for arithmetic progressions (cf. [12]) we have

∏_{{p≤x \atop p≡a(mod d)}}(1 + \frac{1}{p}) ∼ c_{a,d} log^{\frac{1}{φ(d)}} x, x → ∞,

for some c_{a,d} > 0, the result follows. □

3 The proofs of Theorems 1 and 2

In this section we analyse the growth behaviour of the counting functions N_{g}(a, d)(x) and N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x). Throughout we restrict to those primes p with ν_{p}(g) = 0. Let ω(d) = ∑_{p|d} 1 denote the number of distinct prime divisors of d.

Let

V_{g}(a, d; t)(x) = #{p ≤ x : r_{g}(p) = t, p ≡ 1 + ta(mod dt)}.

Note that N_{g}(a, d)(x) = ∑_{t=1}^{∞} V_{g}(a, d; t)(x). If (1 + ta, d) > 1 then there is at most one prime counted by V_{g}(a, d; t)(x) and this prime has to divide d. It follows

that N_{g}(a, d)(x) = ∑∞_{{t=1 \atop (1+ta,d)=1}} V_{g}(a, d; t)(x) + O(ω(d)). Let x_{1} = \sqrt{log x}. Assume

GRH. By [5, Lemma 7] it follows that = #{p ≤ x : r_{g}(p) > x_{1}} = O_{g}(x log^{−3/2} x). We thus infer that

N_{g}(a, d)(x) = ∑_{{t≤x_{1} \atop (1+ta,d)=1}} V_{g}(a, d; t)(x) + O_{g,d}(\frac{x}{log^{3/2} x}).  (9)

For fixed t the term V_{g}(a, d; t) can be estimated by a variation of Hooley’s classical argument [2]. However, we need to carry this out with a certain uniformity. This requires one to merely keep track of the dependence on t of the various estimates. This results in the following lemma.

Lemma 11 (GRH). For t ≤ x^{1/3} we have

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

where the implied constant depends at most on d and g.

Proof. Let

M′_{g}(x, y) = #{p ≤ x : p ≡ 1 + ta(mod dt), t|r_{g}(p), qt ∤ r_{g}(p), q ≤ y} and

M_{g}(x, y, z) = #{p ≤ x : qt|r_{g}(p), y ≤ q ≤ z},

where q denotes a prime number. Note that

V_{g}(a, d; t)(x) = M′_{g}(x, ξ_{1})+O(M_{g}(x, ξ_{1}, ξ_{2}))+O(M_{g}(x, ξ_{2}, ξ_{3}))+O(M_{g}(x, ξ_{3}, \frac{x − 1}{t})).

We take ξ_{1} = log x/6, ξ_{2} = \sqrt{x} log^{−2} x and ξ_{3} = \sqrt{x} log x. The three error terms were estimated in [5, Theorem 4]. Taking them together it is found that

V_{g}(a, d; t)(x) = M′_{g}(x, ξ_{1}) + O_{d,g} (\frac{x log log x}{φ(t) log^{2} x} + \frac{x}{log^{2} x}) ,  (10)

By inclusion and exclusion it follows that

M′_{g}(x, ξ_{1}) = ∑_{P (n)≤ξ_{1}} μ(n)#{p ≤ x : p ≡ 1 + ta(mod dt), nt|r_{g}(p)},

where P (n) denotes the greatest prime factor of n. The integers n counted in the latter sum are all less than x^{1/3} (cf. (6) of [2]). The counting functions in the latter sum can be estimated by an effective form of Chebotarev’s density theorem, cf. Theorem 3 of [5] and the discussion immediately following this theorem. This yields that

#\{p ≤ x : p ≡ 1 + ta(mod dt), nt|r_{g}(p)\} = \frac{c_{g}(1 + ta, dt, nt)}{[K_{[d,n]t,nt} : ℚ]}Li(x) + O(\sqrt{x} log x),

where the error term depends at most d and g. Indeed, applying applying Theorem 3 of [5] results in an error term of O(\sqrt{x} log(d_{L}x^{[L:ℚ]})/[L : ℚ]), with an absolute implied constant and L = K_{[d,n]t,nt}. On invoking Lemma 3 and [5, Lemma 2] it follows that this is O_{d,g}(\sqrt{x} log x). Proceeding as in section 6 of [2] it is then inferred that

M′_{g}(x, ξ_{1}) = \frac{x}{log x} ∑_{n=1}^{∞} \frac{μ(n)c_{g}(1 + ta, dt, nt)}{[K_{[d,n]t,nt} : ℚ]} + O_{d,g}(\frac{x}{log^{2} x}).  (11)

If nt|r_{g}(p), then p ≡ 1(mod nt). By the chinese remainder theorem it now follows that if (n, d)|a then #{p ≤ x : p ≡ 1 + ta(mod dt), nt|r_{g}(p)} is finite for every x and hence c_{g}(1 + ta, dt, nt) = 0 (an alternative way to see this is to note that in this case σ_{1+ta} does not act like the identity on ℚ(ζ_{nt})). It follows that in the sum in (11) we can restrict to those n satisfying (n, d)|a. On taking this into account and combining (10) and (11), the result follows. □

It is now straigthforward to establish Theorem 2. Proof of Theorem 2. Recall that x_{1} = \sqrt{log x}. Combination of (9) and Lemma 11 yields

N_{g}(a, d)(x) = \frac{x}{log x} ∑_{{t≤x_{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} : ℚ]} + O_{g,d} (\frac{x}{log^{3/2} x}) . (12)

Denote the latter double sum by D(x). By Lemma 3 and [5, Lemma 5] we find

D(x) = δ_{g}(a, d) + O(∑_{t>x_{1}} \frac{h}{tφ(t)}) = δ_{g}(a, d) + O(\frac{h}{\sqrt{log x}}).

On inserting the latter estimate in (12) the proof is then completed. □

A variation of the above (but notationally rather more awkward and hence we only sketch it) gives Theorem 1 with

δ_{g}(a_{1}, d_{1}; a_{2}, d_{2}) = ∑_{{t=1, (1+ta_{2},d_{2})=1 \atop 1+ta_{2}≡a_{1}(mod (d_{1},d_{2}t))}}^{∞} ∑_{n=1}^{∞} \frac{μ(n)c_{g}(a_{1}, d_{1}, 1 + ta_{2}, d_{2}t, nt)}{[K_{nt,nt}(ζ_{d_{1}}, ζ_{d_{2}t}) : ℚ]}, (13)

where, for (b_{1}, f_{1}) = (b_{2}, f_{2}) = 1 and b_{1} ≡ b_{2}(mod (f_{1}, f_{2})), we define

c_{g}(b_{1}, f_{1}, b_{2}, f_{2}, v) = \{ \begin{matrix}1 & if τ|_{ℚ(ζ_{[f_{1},f_{2}]})∩K_{v,v}} = id; \\ 0 & otherwise \end{matrix} ,

where τ is the (unique) automorphism of ℚ(ζ_{[f_{1},f_{2}]}) determined by τ(ζ_{f_{1}}) = ζ_{f_{1}}^{b_{1}} and τ(ζ_{f_{2}}) = ζ_{f_{2}}^{b_{2}}.

Proof of Theorem 1. This is a variation of the proof of Theorem 2. Most error terms can be estimated as before on dropping the condition that p ≡ a_{1}(mod d_{2}), which brings us in the situation of Theorem 2.

We first generalise Lemma 11. For that we only have to replace M′_{g}(x, ξ_{1})

M′′_{g}(x, ξ_{1}) say, where M′′_{g}(x, ξ_{1}) is defined as M′_{g}(x, ξ_{1}) with a = a_{2} and d = d_{2}, but where now furthermore the primes p are required to satisfy p ≡ a_{1}(mod d_{1}). The estimation of M′′_{g}(x, ξ_{1}) can be carried out completely similarly to that of M′_{g}(x, ξ_{1}).

The analogue of (9) is easily derived to be

N_{g}(a_{1}, d_{1}; a_{2}, d_{2})(x) = ∑_{{t≤x_{1}, (1+ta_{2},d_{2})=1 \atop 1+ta_{2}≡a_{1}(mod (d_{1},d_{2}t))}} V_{g}(a_{1}, d_{1}; a_{2}, d_{2}; t)(x) + O_{g,d}(\frac{x}{log^{3/2} x}).

From here on the proof is completed as before. □

4 The case where d is an odd prime

Let d = q be an odd prime. In this case it turns out to be fruitful to consider separately the primes p with p ≡ 1(mod q) and those with p ≢ 1(mod q).

4.1 The case where q|a

Trivially N_{g}(a, q) = N_{g}(0, q) and w.l.o.g, we may assume that a = 0. Note that the primes counted by N_{g}(0, q)(x) must satisfy p ≡ 1(mod q). Let j = ν_{q}(p − 1). Note that p ∉ N_{g}(0, q) iff q^{j}|r_{g}(p). Thus we infer that

N_{g}(0, q)(x) = #{p ≤ x : p ≡ 1(mod q)}−

∑_{j=1}^{∞} #{p ≤ x : p ≡ 1(mod q^{j}), p ≢ 1(mod q^{j+1}), q^{j}|r_{g}(p)}.

The density of primes p satisfying p ≡ 1(mod q^{j}), p ≢ 1(mod q^{j+1}) and q^{j}|r_{g}(p) can be computed by Chebotarev’s density theorem and equals

\frac{1}{[K_{q^{j},q^{j}} : ℚ]} − \frac{1}{[K_{q^{j+1},q^{j}} : ℚ]}.

A more refined analysis [11], cf. [8, 9] (with weaker error term), shows that

N_{g}(0, q)(x) = δ_{g}(0, q)Li(x) + O_{g,q} (\frac{x(log log x)^{4}}{log^{3} x} ) ,

with

δ_{g}(0, q) = \frac{1}{q − 1} − ∑_{j=1}^{∞} (\frac{1}{[K_{q^{j},q^{j}} : ℚ]} − \frac{1}{[K_{q^{j+1},q^{j}} : ℚ]}) .  (14)

Note that N_{g}(1, q; 0, q)(x) = N_{g}(0, q)(x) and hence δ_{g}(1, q; 0, q) = δ_{g}(0, q). The density δ_{g}(0, q) can be explicitly evaluated using Lemma 3:

δ_{g}(1, q; 0, q) = δ_{g}(0, q) = \frac{q^{1−ν_{q}(h)}}{q^{2} − 1} .  (15)

Let us now assume GRH. Using Theorem 2 it is inferred that

δ_{g}(0, q) = δ_{g}^{(0)}(0, q) = ∑_{t=1}^{∞} ∑_{n=1}^{∞} \frac{μ(n)}{[K_{[q,n]t,nt} : ℚ]} = S_{1} + S_{q},

say, where in S_{1} we take together those n with q ∤ n and in S_{q} those with q|n. We have

S_{1} = ∑_{v=1}^{∞} \frac{∑_{n|v, q∤n} μ(n)}{[K_{qv,v} : ℚ]} = ∑_{j=0}^{∞} \frac{1}{[K_{q^{j+1},q^{j}} : ℚ]},

and similarly

S_{q} = ∑_{t=1}^{∞} ∑_{{n=1 \atop q|n}}^{∞} \frac{μ(n)}{[K_{nt,nt} : ℚ]} = − ∑_{t=1}^{∞} ∑_{{n=1 \atop q∤n}}^{∞} \frac{μ(n)}{[K_{qnt,qnt} : ℚ]} = − ∑_{j=1}^{∞} \frac{1}{[K_{q^{j},q^{j}} : ℚ]},

On adding S_{q} to S_{1} we find (14) on noting that [K_{q,1} : ℚ] = q − 1.

4.2 The case where q ∤ a

In the remainder of this section we assume that q ∤ a. Recall that q^{∗} = (\frac{−1}{q})q.

Proposition 1 (GRH). Let q be an odd prime and q ∤ a. Then

δ_{g}(1, q; a, q) = \frac{1}{(q − 1)^{2}} (1 − \frac{q^{1−ν_{q}(h)}}{q + 1} ) .

In particular δ_{g}(1, q; a, q) ∈ ℚ_{>0} and does not depend on a.

Proof. The density δ_{g}(1, q; a, q) equals, using (13) and Lemma 7,

∑_{{t=1, q|t \atop (1+ta,q)=1}}^{∞} ∑_{{n=1 \atop q∤n}}^{∞} \frac{μ(n)c_{g}(1 + ta, qt, nt)}{[K_{qnt,nt} : ℚ]} = ∑_{{t=1 \atop q|t}}^{∞} ∑_{{n=1 \atop q∤n}}^{∞} \frac{μ(n)c_{g}(1 + ta, q^{1+ν_{q}(t)}, nt)}{[K_{qnt,nt} : ℚ]}.

Suppose that q ∤ n. By Lemma 6 it follows that ℚ(ζ_{q^{1+νq(t)}}) ∩ K_{nt,nt} = ℚ(ζ_{q^{νq(t)}}). Since 1 + ta ≡ 1(mod q^{ν_{q}(t)}), the automorphism σ_{1+ta} in Theorem 2 acts like the identity on the latter field intersection and hence c_{g}(1 + ta, q^{1+ν_{q}(t)}, nt) = 1. We thus infer that

δ_{g}(1, q; a, q) = ∑_{{t=1 \atop q|t}}^{∞} ∑_{{n=1 \atop q∤n}}^{∞} \frac{μ(n)}{[K_{qnt,nt} : ℚ]}.  (16)

In particular, it follows that δ_{g}(1, q; a, q) does not depend on a. We present two ways to complete the proof from this point onwards. First way. From (16) we infer that

δ_{g}(1, q; a, q) = ∑_{t=1}^{∞} ∑_{n=1, q∤n}^{∞} \frac{μ(n)}{[K_{q^{2}nt,qnt} : ℚ]} = ∑_{v=1}^{∞} \frac{∑_{n|v, q∤n} μ(n)}{[K_{q^{2}v,v} : ℚ]} = ∑_{j=1}^{∞} \frac{1}{[K_{q^{j+1},q^{j}} : ℚ]}.

Using Lemma 3 the latter sum is easily evaluated. Second way. Note that ∑_{0≤a≤q−1} δ_{g}(1, q; a, q) equals the density of primes p with p ≡ 1(mod q) and hence

∑_{0≤a≤q−1} δ_{g}(1, q; a, q) = \frac{1}{q − 1}.  (17)

Since, provided that q ∤ a, δ_{g}(1, q; a, q) does not depend on a, we conclude from (17) that

δ_{g}(1, q; a, q) = \frac{1}{q − 1} (\frac{1}{q − 1} − δ_{g}(1, q; 0, q)) .

Now invoke (15). □

Remark 4. Using a different method in [5, Theorem 10] the values of δ_{g}(1, 3^{s}; a, 3) for s ≥ 1 were calculated.

In order to determine δ_{g}(a, q) it turns out to be convenient to determine δ_{g}(a, d)− δ_{g}(1, q; a, q) first.

Lemma 12 (GRH). Let q be an odd prime and q ∤ a. Then

δ_{g}(a, q) − δ_{g}(1, q; a, q) =

\frac{1}{q − 1} − ∑_{{v=1 \atop q∤v}}^{∞} \frac{∑_{t≡− \frac{1}{a} (mod q), t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]} − ∑_{{v=1, q∤v \atop \sqrt{q^{∗}}∈Kv,v}}^{∞} \frac{∑_{( \frac{ta+1}{q})=−1, t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]}.

Proof. By Theorem 1, Theorem 2 and Lemma 7 we infer that

δ_{g}(a, q) − δ_{g}(1, q; a, q) = ∑_{{t=1, q∤t \atop (1+ta,q)=1}}^{∞} ∑_{{n=1 \atop q∤n}}^{∞} \frac{μ(n)c_{g}(1 + ta, q, nt)}{[K_{qnt,nt} : ℚ]}.

Let us restrict now to values of n and t that occur in the latter double sum. We have, by Lemma 5,

ℚ(ζ_{q}) ∩ K_{nt,nt} = \{ \begin{matrix}ℚ(\sqrt{q^{∗}}) & if \sqrt{q^{∗}} ∈ K_{nt,nt}; \\ ℚ & otherwise. \end{matrix}

Using Lemma 2 it then follows that

c_{g}(1 + ta, q, nt) = \{ \begin{matrix}(1 + (\frac{q^{∗}}{1+ta}))/2 & if \sqrt{q^{∗}} ∈ K_{nt,nt}; \\ 1 & otherwise. \end{matrix}

By the properties of the Kronecker symbol we have (q^{∗}/1 + ta) = (1 + ta/q), where the symbol (1 + ta/q) is just the Legendre symbol. We can thus write δ_{g}(a, q) − δ_{g}(1, q; a, q) = J_{1} − J_{2}, where

J_{1} = ∑_{{t=1, q∤t \atop (1+ta,q)=1}}^{∞} ∑_{{n=1 \atop q∤n}}^{∞} \frac{μ(n)}{[K_{qnt,nt} : ℚ]} and J_{2} = ∑_{{t=1, q∤t \atop ( \frac{1+ta}{q})=−1}}^{∞} ∑_{{n=1, q∤n \atop \sqrt{q^{∗}}∈K_{nt,nt}}}^{∞} \frac{μ(n)}{[K_{qnt,nt} : ℚ]}. (18)

On writing nt = v we obtain

J_{1} = ∑_{{v=1 \atop q∤v}}^{∞} \frac{∑_{t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]} − ∑_{{v=1 \atop q∤v}}^{∞} \frac{∑_{t≡− \frac{1}{a} (mod q), t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]}
= \frac{1}{q − 1} − ∑_{{v=1 \atop q∤v}}^{∞} \frac{∑_{t≡− \frac{1}{a} (mod q), t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]}  (19)

and

J_{2} = ∑_{{v=1, q∤v \atop \sqrt{q^{∗}}∈Kv,v}}^{∞} \frac{∑_{( \frac{1+ta}{q})=−1, t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]}.

On combining these expressions with δ_{g}(a, q) − δ_{g}(1, q; a, q) = J_{1} − J_{2}, the result follows. □ Example. For q = 3 and 3 ∤ a we obtain, on GRH, that

δ_{g}(2, 3; 1, 3) = \frac{1}{2} − ∑_{{v=1 \atop 3∤v}}^{∞} \frac{∑_{t≡2(mod 3), t|v} μ(\frac{v}{t})}{[K_{3v,v} : ℚ]} − ∑_{{v=1, 3∤v \atop \sqrt{−3}∈Kv,v}}^{∞} \frac{∑_{t≡1(mod 3), t|v} μ(\frac{v}{t})}{[K_{3v,v} : ℚ]}.
= \frac{1}{2} − ∑_{{v=1 \atop 3∤v}}^{∞} \frac{∑_{t|v} μ(\frac{v}{t})}{[K_{3v,v} : ℚ]} + ∑_{{v=1, 3∤v \atop \sqrt{−3}∉Kv,v}}^{∞} \frac{∑_{t≡1(mod 3), t|v} μ(\frac{v}{t})}{[K_{3v,v} : ℚ]}.
= ∑_{{v=1, 3∤v \atop \sqrt{−3}∉Kv,v}}^{∞} \frac{∑_{t≡1(mod 3), t|v} μ(\frac{v}{t})}{[K_{3v,v} : ℚ]}.

More generally, we have

δ_{g}(2, 3; a, 3) = ∑_{{v=1, 3∤v \atop \sqrt{−3}∉Kv,v}}^{∞} \frac{∑_{t≡a(mod 3), t|v} μ(\frac{v}{t})}{[K_{3v,v} : ℚ]}.

Rewriting this expression in terms of h′_{χ}s we obtain Theorem 11 of [5]. We now have the ingredients to establish the following result. Theorem 3 (GRH). Let q be an odd prime and q ∤ a. Then

δ_{g}^{(0)}(a, q) = \frac{1}{q − 1} + \frac{1}{(q − 1)^{2}} (1 − \frac{q^{1−ν_{q}(h)}}{q + 1} ) − ∑_{{v=1 \atop q∤v}}^{∞} \frac{∑_{t≡− \frac{1}{a} (mod q), t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]} (20)

and

δ_{g}(a, q) = δ_{g}^{(0)}(a, q) − ∑_{{v=1, q∤v \atop \sqrt{q^{∗}}∈Kv,v}}^{∞} \frac{∑_{( \frac{ta+1}{q})=−1, t|v} μ(\frac{v}{t})}{[K_{qv,v} : ℚ]}.  (21)

If q ∤ D(g_{0}), then δ_{g}(a, q) = δ_{g}^{(0)}(a, q).

Proof. Considering the terms with q|t and q ∤ t in the double sum for δ_{g}(a, q) separately we have, using (16) and (18) that δ_{g}^{(0)}(a, q) = δ_{q}(1, q; a, q) + J_{1}. On using Proposition 1, (19) and Lemma 12 the first two assertions are established.

If q ∤ D(g_{0}), then by Lemma 6 there is no integer v such that q ∤ v and \sqrt{q^{∗}} ∈ K_{v,v} and hence the double sum in (21) equals zero. □

Remark 5. The double sum (21) can be rewritten, using Lemma 6, as

∑_{v=1, q∤v}^{∞} (\frac{2}{[K_{qv,v} : ℚ]} − \frac{2}{(q − 1)[K_{v,v} : ℚ]}) ∑_{( \frac{ta+1}{q})=−1, t|v} μ(\frac{v}{t}).

Remark 6. Note that the proof of Theorem 3 makes essential use of the law of quadratic reciprocity (this law enters in the proof of Lemma 12).

Let G_{q} be the character group associated to (ℤ/ℤq)^{∗}. Since the latter group is abelian it follows that G_{q} ≅ (ℤ/ℤq)^{∗}. The principal character mod q will be denoted by χ_{0}. Recall that o_{χ} denotes the order of χ considered as an element of G_{q}.

Using (4) and the following lemma, δ_{g}(a, q) and δ_{g}^{(0)}(a, q) can be expressed as simple linear combinations of the constants C_{χ} introduced in Section 2.1. Each such constant can be explicitly evaluated and is of the form cA_{χ} with c ∈ ℚ(ζ_{o_{χ}}). This allows one to explicitly evaluate δ_{g}(a, q) and δ_{g}^{(0)}(a, q). For reasons of space we only will work this out in the case g ∈ G, where G is the set of rational numbers g that can not be written as −g_{0}^{h} or g_{0}^{h} with h > 1 an integer and g_{0} a rational number.

Lemma 13 [5, Lemma 11]. Let r, s be integers with s|r. Let χ be a Dirichlet character. Then, if g > 0 or g < 0 and s is even,

∑_{(r,v)=1} \frac{h_{χ}(v)}{[K_{sv,v} : ℚ]} = \frac{1}{φ(s)} (C_{χ}(h, r, 1) + C_{χ}(h, r, \frac{n_{s}}{(n_{s}, s)})) .

When g < 0 and s is odd, the latter sum equals

\frac{1}{φ(s)} (C_{χ}(h, r, 1) − \frac{1}{2}C_{χ}(h, r, 2) + \frac{1}{2}C_{χ}(h, r, 2^{ν_{2}(h)+1}) + C_{χ}(h, r, \frac{n_{s}}{(n_{s}, s)})) .

Now we can formulate one of our main results.

Theorem 4 (GRH). Let q be an odd prime and q ∤ a. We have

δ_{g}(a, q) = ∑_{χ∈G_{q}} χ(−a)c_{χ}A_{χ},

where c_{χ} ∈ ℚ(ζ_{o_{χ}}) may depend on q and g (but not a) and can be explicitly evaluated.

Proof. We only deal with the case where g > 0 or g < 0 and h is odd (the remaining more space consuming case being left to the reader).

Using the identity (4) and Lemma 13 we can rewrite (20) as

δ_{g}^{(0)}(a, q) = \frac{1}{q − 1}+

\frac{1}{(q − 1)^{2}} (1 − \frac{q^{1−ν_{q}(h)}}{q + 1} ) − \frac{1}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a) (C_{χ}(h, q, 1) + C_{χ}(h, q, \frac{n_{q}}{(n_{q}, q)})) .

Similarly, using Remark 5, we rewrite (21) as

δ_{g}(a, q) = δ_{g}^{(0)}(a, q)−\frac{2}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a) (C_{χ}(h, q, \frac{n_{q}}{(n_{q}, q)}) − C_{χ}(h, q, n_{1})) ∑_{b} \overline{χ(b)},

where the sum is over the integers 1 ≤ b ≤ q − 1 for which (\frac{1−b}{q}) = −1. Note that n_{1} = n_{q}. If q ∤ D(g_{0}), the latter double sum equals zero and we infer (as before) that δ_{g}(a, q) = δ_{g}^{(0)}(a, q). If q|D(g_{0}), then C_{χ}(h, q, n_{1}) = 0 and we infer that

δ_{g}(a, q) = δ_{g}^{(0)}(a, q) − \frac{2}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a)C_{χ}(h, q, \frac{n_{1}}{q}) ∑_{b} \overline{χ(b)}.

By [5, Lemma 10] we can write C_{χ}(h, r, s) as cA_{χ} with c ∈ ℚ(ζ_{o_{χ}}), where c can be explicitly given. Using this the proof is easily completed. □

The following result is an easy consequence of the latter proof.

Proposition 2 (GRH). If h is odd and 8|D(g), then δ_{g}(a, q) = δ_{−g}(a, q).

Proof. The assumptions imply that |n_{1}| = |n_{q}| = |D(±g)| and on noting that C_{χ}(h, r, s) = C_{χ}(h, r, −s) the character sum expression for δ_{g}(a, q) given in the proof of Theorem 4 is seen to equal that of δ_{−g}(a, q) in case q ∤ a. If q|a, then by (15) we have δ_{±g}(0, q) = q/(q^{2} − 1). □

The following result demonstates Theorem 4 in the special (but important) case where g ∈ G. Since almost all integers are in G it can be thought of as the set of ‘generic’ integers g.

Proposition 3 (GRH). Let q be an odd prime and q ∤ a. Suppose that g ∈ G. Put

ϵ_{g}(χ) = \{ \begin{matrix}1 & if 2 ∤ D(g); \\ \frac{χ(2)}{4} & if 4||D(g); \\ \frac{χ(2)^{2}}{16} & if 8|D(g). \end{matrix}

If q ∤ D(g), then δ_{g}(a, q) equals δ_{q}^{0}(a, q) which on its turn equals

\frac{q^{2}}{(q − 1)(q^{2} − 1)} − \frac{1}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a)A_{χ} (1 + ϵ_{g}(χ) ∏_{p|2D(g)} \frac{p(χ(p) − 1)}{p^{3} − p^{2} − p + χ(p)}) .

If q|D(g), then

δ_{g}(a, q) = \frac{q^{2}}{(q − 1)(q^{2} − 1)}

−\frac{1}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a)A_{χ} (1 + ϵ_{g}(χ)\{1 + 2 ∑_{b} \overline{χ(b)}\} ∏_{p|2D(g)/q} \frac{p(χ(p) − 1)}{p^{3} − p^{2} − p + χ(p)}) ,

where the sum is over all 1 ≤ b ≤ q − 1 for which (\frac{1−b}{q}) = −1.

Proof. By Lemma 3 we have

n_{1} = n_{q} = \{ \begin{matrix}[2, D(g_{0})] & if g > 0; \\ D(g_{0})/2 & if g < 0 and D(g) ≡ 4(mod 8); \\ [4, D(g_{0})] & if g < 0 and D(g) ≢ 4(mod 8). \end{matrix}

Now note that n_{1} = n_{q} = [2, D(g)] and that q|D(g_{0}) iff q|D(g). Working out the formulae involving the C_{χ}’s in the proof of Theorem 4 using [5, Lemma 10], the proof is then completed. □

In case d = q is an odd prime it can be shown [3, Proposition 7] that

δ(a, q) = \frac{q^{2}}{(q − 1)(q^{2} − 1)} − \frac{1}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a)A_{χ}.

Assume GRH. Proposition 3 shows that if g ∈ G and |g| tends to infinity, then δ_{g}(a, q) tends to δ(a, q). Proposition 3 also shows that if g ∈ G and D(g) contains a prime divisor p with p ≡ 1(mod q), then δ_{g}(a, q) = δ(a, q). It is not difficult to show that almost all integers g with |g| ≤ x satisfy g ∈ G and have D(g) with at least one prime divisor p with p ≡ 1(mod q). Consequently we infer that for almost all integers g with |g| ≤ x, δ_{g}(a, q) = δ(a, q). This shows that for a ‘generic’ g, δ_{g}(a, q) = δ(a, q). Furthermore, if δ_{g}(a, q) is not equal to δ(a, q) then usually it will be quite close to it. The results in the next section allow one to also draw these conclusions in the case where d is an odd prime power, which will be done in the final section.

5 The case where d is an odd prime power

The case where d = q^{s} with q an odd prime is easily reduced to the case d = q by the following result.

Theorem 5 (GRH). Suppose that d|d_{1}, the quotient d_{1}/d is odd and ω(d_{1}) = ω(d). Then δ_{g}(a, d_{1}) = \frac{d}{d_{1}} δ_{g}(a, d).

Corollary 1 Let q be an odd prime and j ≥ 1, then δ_{g}(a, q^{j}) = q^{1−j}δ_{g}(a, q).

Remark 7. From formula (3) for δ(a, d) it is easily inferred that if d|d_{1} and ω(d_{1}) = ω(d), then

δ(a, d_{1}) = \frac{d}{d_{1}} δ(a, d).  (22)

Proof of Theorem 5. If d|d_{1} and ω(d) = ω(d_{1}) and for all n and t with (1+ta, d) = 1, (n, d)|a and n is squarefree, we have [K_{[d_{1},n]t,nt} : ℚ]/φ(d_{1}) = [K_{[d,n]t,nt} : ℚ]/φ(d), then using Lemma 8 we infer that

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

= \frac{d}{d_{1}} ∑_{{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} : ℚ]} = \frac{d}{d_{1}} δ_{g}(a, d),

where we used that φ(d_{1})/φ(d) = d_{1}/d. Now invoke Lemma 4. □

6 Connection between δ_{g}(a, q^{s}) and δ(a, q^{s})

Define \overline{δ}_{g}(d) = (δ_{g}(0, d), δ_{g}(1, d), …, δ_{g}(d − 1, d)) (if this exists) and

\overline{δ}(d) = (δ(0, d), δ(1, d), …, δ(d − 1, d)).

The next result implies that, under GRH, for almost all integers g we have \overline{δ}_{g}(q^{s}) = \overline{δ}(q^{s}).

Theorem 6 (GRH). Let s ≥ 1 and q an odd prime. Then there are at most O_{q}(x log^{−1/(q−1)} x) integers g with |g| ≤ x such that \overline{δ}_{g}(q^{s}) ≠ \overline{δ}(q^{s}).

Proof. By the results of the previous section it is enough to prove this in case s = 1. By [3, Proposition 7] we have, for 1 ≤ a ≤ q − 1,

δ(a, q) = \frac{q^{2}}{(q − 1)(q^{2} − 1)} − \frac{1}{(q − 1)^{2}} ∑_{χ∈G_{q}} χ(−a)A_{χ},

and δ(0, q) = q/(q^{2} − 1) [3, Theorem 1]. Since there are at most O(\sqrt{x} log x) integers |g| ≤ x that are not in G, we can restrict ourselves to the case where g ∈ G. For such a g we then have, using (15), that δ_{g}(0, q) = δ(0, q). Now by Proposition 3 we infer that if D(g) has a prime divisor p with p ≡ 1(mod q), then \overline{δ}_{g}(q) = \overline{δ}(q) (since χ(p) = 1 for every χ ∈ G_{q}). It follows that the number of g ∈ G with |g| ≤ x such that \overline{δ}_{g}(q) ≠ \overline{δ}(q) is bounded above by the number of g with |g| ≤ x such that D(g) has no prime factor p satisfying p ≡ 1(mod q). By Lemma 10 the proof is then completed. □

If it is not true that \overline{δ}_{g}(q^{s}) = \overline{δ}(q^{s}), then our final result shows that \overline{δ}_{g}(q^{s}) will be close to \overline{δ}(q^{s}),

Proposition 4 (GRH). Suppose that g ∈ G. As |g| tends to infinity, \overline{δ}_{g}(q^{s}) tends to \overline{δ}(q^{s}).

Proof. A simple consequence of the results in the previous section, the formula given for δ(a, q) in the proof of Theorem 6, (15) and Proposition 3. □

For a numerical illustration of the latter result (with g = −19) see Table 1 of [3].

Acknowledgement. Work on this paper was begun at the Korteweg-de Vries Institute (Amsterdam), whilst the author was working in the NWO Pioneerproject of Prof. E. Opdam. I am grateful to Prof. Opdam for the opportunity to have been part of his group.

References

[1] K. Chinen and L. Murata, On a distribution property of the residual order of a(mod p). I, J. Number Theory 105 (2004), 60–81.

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

[3] P. Moree, On the average number of elements in a finite field with order or index in a prescribed residue class, ArXiv:math.NT/0212220, Finite Fields Appl., to appear.

[4] P. Moree, Convoluted convolved Fibonacci numbers, ArXiv:math.CO/0311205, J. Integer Seq., to appear.

[5] P. Moree, On the distribution of the order and index of g(mod p) over residue classes, submitted for publication, ArXiv:math.NT/0211259.

[6] L. Murata and K. Chinen, On a distribution property of the residual order of a(mod p). II, J. Number Theory 105 (2004), 82–100.

[7] W. Narkiewicz, Elementary and analytic theory of numbers, Springer, 2nd edition, 1989.

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

[9] F. Pappalardi, Squarefree values of the order function, New York J. Math. 9 (2003), 331–344.

[10] E. Weiss, Algebraic Number Theory, New York University Press, New York, 1963.

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

[12] K.S. Williams, Mertens’ theorem for arithmetic progressions, J. Number Theory 6 (1974), 353–359.

[13] E. Wirsing, Das asymptotische Verhalten von Summen über multiplikative Funktionen, Math. Ann. 143 (1961), 75–102.