VARIATIONS ON A THEME OF ROMANOFF

M. Ram Murty^{1}, Michael Rosen^{2}, Joseph H. Silverman^{3}

McGill University, Brown University, Brown University

Abstract. Fix an integer a ≥ 2. For each m ≥ 1, let f_{a}(m) be the smallest power f so that a^{f} ≡ 1 (mod m). We give explicit upper bounds for the series ∑_{m} 1/mf_{a}(m)^{ε} and ∑_{p} log(p)/pf_{a}(p)^{ε}, generalizing and strengthening results of Romanoff, Landau, Erdös and Turan. We also prove analogous results over number fields and for abelian varieties.

Contents

Introduction

1. A refinement of Erdös-Turan

2. Bounds for 𝔾_{m} over number fields

3. Bounds for abelian varieties

4. Application to densities

Introduction

Let a ≥ 2 be an integer, and for each positive integer m, let

f_{a}(m) = min{f ≥ 1 : a^{f} ≡ 1 (mod m)}.

(If gcd(a, m) > 1, we set f_{a}(m) = ∞.) Romanoff [12] proved that the series ∑_{m≥1} 1/mf_{a}(m) converges. The dependence on a was made explicit by Landau [9], who proved an upper bound of the form C(log log a)^{2}, and this was improved by Erdös and Turan [6,7] who proved for every ε > 0,

∑_{m≥1} \frac{1}{mf_{a}(m)^{ε}} ≤ C_{1}(ε) log log a.  (1)

(See also [4] for some related work of Erdös.) In this paper we will give a simplified proof of the Erdös-Turan result (1) which leads to the more precise estimate

∑_{m≥1} \frac{1}{mf_{a}(m)^{ε}} ≤ e^{γ} log log a + 2e^{γ}ε^{−1} + C_{2}  (2)

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11A07 11G10 11R04.

Key words and phrases. arithmetic series, order modulo m, abelian variety.

1 Research partially supported by NSERC grant OGP0009418.

2 Research partially supported by NSF DMS-9209063

3 Research partially supported by NSF DMS-9121727.

with an absolute constant C_{2}. Here γ ≈ 0.577216 is Euler’s constant. We will also show that the e^{γ} log log a cannot be improved, and we will give an estimate for an analgous sum over primes:

∑_{p} \frac{log p}{pf_{a}(p)^{ε}} ≤ log log a + 2ε^{−1} + C_{3}.  (3)

There are a number of ways to extend and generalize (2) and (3). For example, we can replace the element a with a free subgroup Γ ⊂ K^{∗} of rank r in a number field K with ring of integers R. Then f_{a}(m) becomes

f_{Γ}(𝔪) = # Image(Γ ⟶ R/𝔪).

(If some element of Γ is not relatively prime to 𝔪, set f_{Γ}(𝔪) = ∞.) We will prove

∑_{𝔪≠(0)} \frac{1}{N𝔪 · f_{Γ}(𝔪)^{ε}} ≤ e^{γ}κ_{K} log log H_{K}(Γ) + (1 + \frac{1}{r}) e^{γ}κ_{K}ε^{−1} + C_{4}(K, r), (4)

∑_{𝔭} \frac{log N𝔭}{N𝔭 · f_{Γ}(𝔭)^{ε}} ≤ log log H_{K}(Γ) + (1 + \frac{1}{r}) ε^{−1} + C_{5}(K, r),  (5)

where κ_{K} is the residue of ζ_{K}(s) at s = 1 and H_{K}(Γ) is a certain height associated to Γ.

We can also replace the multiplicative group K^{∗} with an abelian variety A/K. Much of the argument is the same, so we will just prove the analogue of (5). Thus let Γ ⊂ A(K) be a free subgroup of rank r, and for each prime ideal 𝔭 let

f_{Γ}(𝔭) = # Image(Γ ⟶ A mod 𝔭).

(If A has bad reduction at 𝔭, one can either set f_{Γ}(𝔭) = ∞ or work on the Néron model of A.) We will prove that

∑_{𝔭} \frac{log N𝔭}{N𝔭 · f_{Γ}(𝔭)^{ε}} ≤ log ĥ_{K}(Γ) + (1 + \frac{2}{r}) ε^{−1} + C_{6}(A/K),  (6)

where ĥ_{K}(Γ) is a certain canonical height associated to Γ. Notice that the quantity (1 + 1/r)ε^{−1} in (5) has been replaced by a (1 + 2/r)ε^{−1} in (6). This occurs because the logarithm function log(a^{f}) is linear in f, while the canonical height ĥ_{K}(fP) is quadratic in f.

We will now briefly describe the contents of this paper. In the first section we prove (2). This serves to illustrate the general method in the simplest setting. In section 2 we work with finitely generated groups in number fields and prove (4) and (5). Section 3 contains a proof of the abelian variety estimate (6). In the last section we show how the explicit dependence on ε in (2), (3), (4), (5), and (6) can be used to give density estimates. For example, we will use (2) and (3) to prove that for any θ > 0 the sets

{m ≥ 1 : f_{a}(m) ≤ m^{θ}} and {p : f_{a}(p) ≤ p^{θ}}

have (upper) Dirichlet densities at most 57θ/16 and 2θ respectively.

We close this introduction with a brief remark. An important application of Romanoff’s theorem [12] is its use in the proof of Bilharz’ theorem [2] concerning the function field analogue of Artin’s conjecture on primitive roots. Let 𝔽_{q} be a finite field with q elements, let A = 𝔽_{q}[T], and let a ∈ A be a non-constant polynomial which is not an ℓ^{th} power for any ℓ|q−1. Bilharz shows that the Dirichlet density of the prime ideals in A for which a is a primitive root is given by the sum ∑_{m} μ(m)/mf_{q}(m). The absolute convergence of this sum is a consequence of Romanoff’s theorem. That the sum is positive follows from a theorem of Heilbronn. Bilharz’s full result is even more general than this.

§1. A refinement of Erdös-Turan

In this section we will prove the following refinement of the theorem of Erdös and Turan [6, 7].

Theorem 1.1. Let a ≥ 2 be an integer, let ε > 0, and for each integer m ≥ 1, define f_{a}(m) by

f_{a}(m) = min{f ≥ 1 : a^{f} ≡ 1 (mod m)}.

(a)

∑_{m=1}^{∞} \frac{1}{mf_{a}(m)^{ε}} ≤ e^{γ} log log a + 2e^{γ}ε^{−1} + O(1).

(b) Let N ≥ 2 and a = 1 + LCM[1, 2, …, N]. Then

∑_{m=1}^{∞} \frac{1}{mf_{a}(m)^{ε}} ≥ e^{γ} log log a + O(log log log a) as N → ∞.

(In both parts, γ ≈ 0.577216 is Euler’s constant and the O(1) constants are absolute and effectively computable.)

Remark. Notice that f_{a}(m) < m for all m with gcd(a, m) = 1, so we have

∑_{m=1}^{∞} \frac{1}{mf_{a}(m)^{ε}} ≥ ∑_{\begin{matrix}m≥1 \\ gcd(a,m)=1 \end{matrix}} \frac{1}{m^{1+ε}} = ∏_{p|a} (1 − \frac{1}{p^{1+ε}} ) ζ(1 + ε).

This shows that the series grows at least like C(a)ε^{−1} as ε → 0. It would be interesting to compute the exact value of ε ∑ 1/mf_{a}(m)^{ε} as ε → 0 (if the limit exists).

The first step in proving Theorem 1.1 is the following elementary consequence of Mertens’ theorem.

Lemma 1.2. For all integers n ≥ 2,

∑_{d|n} \frac{1}{d} ≤ e^{γ} log log n + O(1).

Proof. This follows from Mertens’ theorem [8, Thm. 429] and a standard argument looking at large prime and small primes. (See also [8, Thm. 323].) We will prove a more general number field version in the next section (Corollary 2.3), so we do not include a proof here.

During the proof of Theorem 1.1 we will need to consider the following two sums:

d_{a}(f) = ∑_{\begin{matrix}m≥1 \\ f_{a}(m)=f \end{matrix}} \frac{1}{m}, D_{a}(x) = ∑_{f≤x} d_{a}(f).

Lemma 1.3. For all x ≥ 1,

D_{a}(x) ≤ 2e^{γ} log x + e^{γ} log log a + O(1).

Proof. Let

A(x) = ∏_{f≤x}(a^{f} − 1).

The trivial estimate

A(x) = ∏_{f≤x}(a^{f} − 1) ≤ ∏_{f≤x} a^{f} ≤ a^{x(x+1)/2} ≤ a^{x^{2}}

gives

log log A(x) ≤ 2 log x + log log a.  (7)

We also observe that

f_{a}(m) ≤ x ⟺ a^{f} ≡ 1 (mod m) for some f ≤ x ⟹ m|A(x).  (8)

We compute

D_{a}(x) = ∑_{f≤x} d_{a}(f) = ∑_{f≤x} ∑_{\begin{matrix}m≥1 \\ f_{a}(m)=f \end{matrix}} \frac{1}{m} by definition of D_{a}, d_{a}

= ∑_{\begin{matrix}m≥1 \\ f_{a}(m)≤x \end{matrix}} \frac{1}{m} ≤ ∑_{m|A(x)} \frac{1}{m} from (8)

≤ e^{γ} log log A(x) + O(1) from Lemma 1.2 ≤ e^{γ}(2 log x + log log a) + O(1) from (7).

This completes the proof of Lemma 1.3.

We are now ready to prove Theorem 1.1

Proof (of Theorem 1.1). Let S_{a} be the sum we are trying to estimate. We rewrite S_{a} as

S_{a} = ∑_{m=1}^{∞} \frac{1}{mf_{a}(m)^{ε}} = ∑_{f=1}^{∞} \frac{1}{f^{ε}} ∑_{\begin{matrix}m≥1 \\ f_{a}(m)=f \end{matrix}} \frac{1}{m} = ∑_{f=1}^{∞} \frac{d_{a}(f)}{f^{ε}}.

Lemma 1.3 tells us that

lim_{x→∞} \frac{1}{x^{ε}} ∑_{f≤x} d_{a}(f) = lim_{x→∞} \frac{1}{x^{ε}} · D_{a}(x) = 0,

so we can apply Abel summation to compute

S_{a} = ∫_{1}^{∞} D_{a}(t) · \frac{ε}{t^{1+ε}} dt (Abel summation [1, Thm. 4.2])

≤ ∫_{1}^{∞} \frac{(2e^{γ} log t + e^{γ} log log a + O(1))ε}{t^{1+ε}} dt (from Lemma 1.3)

= 2e^{γ}ε^{−1} + e^{γ} log log a + O(1) (elementary calculus).

This completes the proof of Theorem 1.1(a).

To prove (b), we let a = 1 + LCM[1, …, N]. Notice that f_{a}(m) = 1 for all m dividing a − 1, so we have

S_{a} ≥ ∑_{m|a−1} \frac{1}{m} = ∑_{m| LCM[1,... ,N]} \frac{1}{m} = e^{γ} log N + O(log log N),

where the last equality is an exercise using Mertens’ theorem. On the other hand, the prime number theorem says that

ψ(N) = log LCM[1, …, N] ∼ N,

so log N = log(a − 1) + o(1). Substituting this in above gives the desired result.

Remark. Erdös [4] has proven estimates of the form

∑_{d|a^{f} −1} \frac{1}{d} ≤ C_{4}(a) log log f.

Such estimates are clearly closely related to the results in this paper. He also conjectures (in our notation) that

D_{a}(x) ∼ C_{5}(a) log x  and  lim_{f→∞} d_{a}(f) = 0.

Notice that it is clear that D_{a}(x) ≥ C_{6}(a) log x, since f_{a}(m) ≤ m, so Lemma 1.3 tells us that D_{a}(x) = O_{a}(log x). Further, if Erdös’ conjecture is correct, then Lemma 1.3 implies that the constant C_{5}(a) satisfies C_{5}(a) ≤ 2e^{γ}, so it is bounded independently of a.

Remark. Sometimes it is useful to have estimates like those in Theorem 1.1 for sums involving f_{a}(m) over squarefree integers m, see for example [12]. Using the exact same methods, it is not hard to show that

∑_{m=1}^{∞} \frac{μ(m)^{2}}{mf_{a}(m)^{ε}} ≤ \frac{e^{γ}}{ζ(2)} (log log a + 2ε^{−1}) + O(1),

where the notation is as in Theorem 1.1. We will leave the details to the reader.

§2. Bounds for 𝔾_{m} over number fields

In this section we are going to generalize Theorem 1.1 by estimating an analogous sum for finitely generated subgroups of the multplicative group of a number field. We set the following notation, which will be used throughout the remainder of this paper.

K a number field of degree d. R the ring of integers of K. κ_{K} the residue of ζ_{K}(s) at s = 1. Thus κ_{K} = 2^{r_{1}}(2π)^{r_{2}}h_{K}R_{K}/w_{K}D_{K}^{1/2},

where r_{1}, r_{2} are the number of real and complex embeddings of K, h_{K} is the class number of K, R_{K} is the regulator of K, w_{K} is the number of roots of unity in K, and D_{K} is the absolute discriminant of K/ℚ.

H_{K} Weil height on K (see [10, Ch. 3, §1]).

Γ a free finitely generated subroup of K^{∗} of rank r ≥ 1. H_{K}(Γ) the minimum value of 3H_{K}(a_{1}) ⋯ H_{K}(a_{r}) over all sets of generators

{a_{1}, …, a_{r}} for Γ. (The factor of 3 is included merely to ensure that H_{K}(Γ) ≥ 3, so the quantity log log H_{K}(Γ) will be positive.)

For each non-zero integral ideal 𝔪 of K, we define

f_{Γ}(𝔪) = \{ \begin{matrix}# Image(Γ ⟶ R/𝔪) & if ord_{𝔭}(a) = 0 for all 𝔭|𝔪 and all a ∈ Γ, \\ ∞ & otherwise. \end{matrix}

Finally, we will use functions which have the following four properties:

[\begin{matrix}(i) & G : [1, ∞) → [0, 1]. \\ (ii) & G is continuously differentiable and non-increasing. \\ (iii) & G(1) = 1. \\ (iv) & ∫_{1}^{∞} G(x)/x dx < ∞. \end{matrix}]  (∗)

For example, the functions x^{−ε} and (1 + log x)^{−1−ε} satisfy condition (∗). We are now ready to state our main result.

Theorem 2.1. With notation as above, let G(x) be a function satisfying (∗). Then the following estimates hold, where the first sum is over non-zero integral ideals of K and the second sum is over prime ideals of K:

∑_{𝔪≠(0)} \frac{G(f_{Γ}(𝔪))}{N𝔪} ≤ e^{γ}κ_{K} log log H_{K}(Γ) + e^{γ}κ_{K} (1 + \frac{1}{r}) ∫_{1}^{∞} \frac{G(x)}{x}dx + O_{K}(r).

(9)

∑_{𝔭} G(f_{Γ}(𝔭))\frac{log N𝔭}{N𝔭} ≤ log log H_{K}(Γ) + (1 + \frac{1}{r}) ∫_{1}^{∞} \frac{G(x)}{x}dx + O_{K}(r). (10)

Remark. We observe that if we take G(x) = x^{−ε}, then (9) and (10) become the inequalities (4) and (5) stated in the introduction. If we further take K = ℚ and Γ = ⟨a⟩, then (9) and (10) become (2) and (3). So Theorem 2.1 contains all of the inequalities stated in the introduction except for the estimate (6) dealing with abelian varieties which we will prove in the next section.

We begin with a number field version of Mertens’ theorem and a useful corollary.

Proposition 2.2. For all x ≥ 1,

∏_{N𝔭≤x} (1 − \frac{1}{N𝔭})^{−1} = e^{γ}κ_{K} log x + O_{K}(1). (Mertens’ theorem)  (11)

∑_{N𝔭≤x} \frac{log N𝔭}{N𝔭} = log x + O_{K}(1).  (12)

Here γ ≈ 0.577216 is Euler’s constant.

Proof. These are standard results over ℚ, although Mertens’ theorem is usually stated merely as an asymptotic estimate instead of with the O(1). See for example [8, Thm. 429] for (11) and [8, Thm. 425] for (12). These proofs can be adapted to the number field case and the stronger Mertens’ estimate proven by making use of well known properties of the Dedekind zeta function ζ_{K}(s). See [13] for details.

Corollary 2.3. Let 𝔫 be a non-zero integral ideal in K with norm N𝔫 ≥ 2. Then

∑_{𝔡|𝔫} \frac{1}{N𝔡} ≤ e^{γ}κ_{K} log log N𝔫 + O_{K}(1).  (13)

∑_{𝔭|𝔫} \frac{log N𝔭}{N𝔭} ≤ log log N𝔫 + O_{K}(1).  (14)

Proof. Let

f(𝔫) = #{𝔭 : 𝔭|𝔫 and N𝔭 > log N𝔫}.

We begin with the “large” primes. Thus

N𝔫 ≥ ∏_{\begin{matrix}𝔭|𝔫 \\ N𝔭>log N𝔫 \end{matrix}} N𝔭 ≥ (log N𝔫)^{f(𝔫)}, so f(𝔫) ≤ \frac{log N𝔫}{log log N𝔫}.

This allows us to estimate

∏_{\begin{matrix}𝔭|𝔫 \\ N𝔭>log N𝔫 \end{matrix}} (1 − \frac{1}{N𝔭})^{−1} ≤ (1 − \frac{1}{log N𝔫})^{−f(𝔫)}

≤ (1 − \frac{1}{log N𝔫})^{− log N𝔫/ log log N𝔫}

= 1 + O (\frac{1}{log log N𝔫}) .  (15)

Similarly we estimate

∑_{\begin{matrix}𝔭|𝔫 \\ N𝔭>log N𝔫 \end{matrix}} \frac{log N𝔭}{N𝔭} ≤ f(𝔫)\frac{log log N𝔫}{log N𝔫} ≤ 1.  (16)

Next we consider the “small” primes. Using Mertens’ theorem (11), we compute

∏_{\begin{matrix}𝔭|𝔫 \\ N𝔭≤log N𝔫 \end{matrix}} (1 − \frac{1}{N𝔭})^{−1} ≤ ∏_{N𝔭≤log N𝔫} (1 − \frac{1}{N𝔭})^{−1} = e^{γ}κ_{K} log log N𝔫 + O_{K}(1). (17)

Similarly using (12) we find

∑_{\begin{matrix}𝔭|𝔫 \\ N𝔭≤log N𝔫 \end{matrix}} \frac{log N𝔭}{N𝔭} ≤ ∑_{N𝔭≤log N𝔫} \frac{log N𝔭}{N𝔭} = log log N𝔫 + O_{K}(1).  (18)

Now multiplying (15) and (17) gives

∑_{𝔡|𝔫} \frac{1}{N𝔡} ≤ ∏_{𝔭|𝔫} (1 − \frac{1}{N𝔭})^{−1} ≤ (e^{γ}κ_{K} log log N𝔫 + O_{K}(1)) (1 + O (\frac{1}{log log N𝔫}))
= e^{γ}κ_{K} log log N𝔫 + O_{K}(1),

which is exactly (13). Similarly, adding (16) and (18) gives (14). This completes the proof of Corollary 2.3.

The next result provides the crucial estimate needed for the proof of Theorem 2.1.

Proposition 2.4. For all x ≥ 1,

∑_{\begin{matrix}𝔪≠(0) \\ f_{Γ}(𝔪)≤x \end{matrix}} \frac{1}{N𝔪} ≤ e^{γ}κ_{K} log log H_{K}(Γ) + e^{γ}κ_{K} (1 + \frac{1}{r}) log x + O_{K}(r). (19)

∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)≤x \end{matrix}} \frac{log N𝔭}{N𝔭} ≤ log log H_{K}(Γ) + (1 + \frac{1}{r}) log x + O_{K}(r). (20)

Proof. Fix generators a_{1}, …, a_{r} for Γ so that H_{K}(Γ) = 3H_{K}(a_{1}) ⋯ H_{K}(a_{r}). For y ≥ 1, let

Γ(y) = {a_{1}^{n_{1}} ⋯ a_{r}^{n_{r}} ∈ Γ : |n_{1}|, …, |n_{r}| ≤ y}.

For any a ∈ K^{∗}, write the ideal (a − 1) as a quotient of integral ideals,

(a − 1) = 𝔞_{a}𝔡_{a}^{−1}.

We define an ideal 𝔄_{Γ}(y) by

𝔄_{Γ}(y) = ∏_{a∈Γ(y), a≠1} 𝔞_{a}.

Our first job is to prove the following claim.

Claim 1 : If f_{Γ}(𝔪) ≤ x, then 𝔪|𝔄_{Γ}(x^{1/r} + 2).

Note that if f_{Γ}(𝔪) < ∞, then every element of Γ is relatively prime to 𝔪, so we can reduce them modulo 𝔪. Consider the map

Γ(y) ⟶ R/𝔪, a ⟼ a mod 𝔪.

The image has order

#(Γ mod 𝔪) = f_{Γ}(𝔪)

by definition. On the other hand, if y ≥ 1, then Γ(y) has order

#Γ(y) = #{a_{1}^{n_{1}} ⋯ a_{r}^{n_{r}} ∈ Γ : |n_{1}|, …, |n_{r}| ≤ y} ≥ (2y − 1)^{r}.

Hence if we set y = \frac{1}{2}x^{1/r} + 1, then we have a strict inequality

#Γ(y) > #(Γ mod 𝔪),

so we can find distinct elements a, b ∈ Γ(y) with the same image. Then

ab^{−1} ∈ Γ(2y)  and  ab^{−1} ≡ 1 (mod 𝔪),

so 𝔪|𝔞_{ab^{−1}}. Therefore 𝔪|𝔄_{Γ}(2y), which completes the proof of Claim 1. Using Claim 1 and the inequalities (13) and (14) of Corollary 2.3, we find that

∑_{\begin{matrix}𝔪≠(0) \\ f_{Γ}(𝔪)≤x \end{matrix}} \frac{1}{N𝔪} ≤ ∑_{𝔪|𝔄_{Γ}(x^{1/r}+2)} \frac{1}{N𝔪} ≤ e^{γ}κ_{K} log log N𝔄_{Γ}(x^{1/r} + 2) + O_{K}(1).(21)

∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)≤x \end{matrix}} \frac{log N𝔭}{N𝔭} ≤ ∑_{𝔭|𝔄_{Γ}(x^{1/r}+2)} \frac{log N𝔭}{N𝔭} ≤ log log N𝔄_{Γ}(x^{1/r} + 2) + O_{K}(1). (22)

To complete the proof of Proposition 2.4, we need an upper bound for N𝔄_{Γ}(y) as described in our second claim.

Claim 2 : N𝔄_{Γ}(y) ≤ 2^{d(3y)^{r}}H_{K}(Γ)^{(3y)^{r+1}}.

To prove this claim we use elementary properties of height functions. Let a ∈ K with a ≠ 1. Then [10, pp. 51,53] tells us that

H_{K}(a − 1) = H_{K} (\frac{1}{a − 1}) = N𝔞_{a} ∏_{v∈M_{K}^{∞}} max\{1, ∥a − 1∥_{v}\} ≥ N𝔞_{a}.  (23)

We will also need the triangle inequality in the form

H_{K}(u + v) ≤ 2^{d}H_{K}(u)H_{K}(v)  for all u, v ∈ K.  (24)

Hence

N𝔄_{Γ}(y) = ∏_{a∈Γ(y), a≠1} N𝔞_{a} (definition of 𝔄_{Γ}(y))

≤ ∏_{a∈Γ(y)} H_{K}(a − 1) (from (23))

≤ ∏_{a∈Γ(y)} 2^{d}H_{K}(a) (from (24))

= ∏_{|n_{1}|≤y} ⋯ ∏_{|n_{r}|≤y} 2^{d}H_{K} (a_{1}^{n_{1}} ⋯ a_{r}^{n_{r}}) (definition of Γ(y))

≤ ∏_{|n_{1}|≤y} ⋯ ∏_{|n_{r}|≤y} 2^{d}H_{K}(a_{1})^{|n_{1}|} ⋯ H_{K}(a_{r})^{|n_{r}|}

≤ 2^{d(2y+1)^{r}}(H_{K}(a_{1}) ⋯ H_{K}(a_{r}))^{(2y+1)^{r−1}y(y+1)}

≤ 2^{d(3y)^{r}}H_{K}(Γ)^{(3y)^{r+1}}.

This completes the proof of Claim 2.

We now apply Claim 2 with y = x^{1/r} + 2 and take the double logarithm of both sides to obtain the estimate

log log N𝔄_{Γ}(x^{1/r} + 2) ≤ log{d(3x^{1/r} + 6)^{r} log 2 + (3x^{1/r} + 6)^{r+1} log H_{K}(Γ)}

= (r + 1) log(3x^{1/r} + 6) + log (\frac{d log 2}{3x^{1/r} + 6} + log H_{K}(Γ))

≤ (1 + \frac{1}{r}) log x + log log H_{K}(Γ) + O_{K}(r).  (25)

Substituting (25) into (21) gives (19), and substituting (25) into (22) gives (20). This completes the proof of Proposition 2.4.

We have now assembled all of the tools needed to prove Theorem 2.1.

Proof (of Theorem 2.1). To ease notation, we let

d_{Γ}(f) = ∑_{\begin{matrix}𝔪≠(0) \\ f_{Γ}(𝔪)=f \end{matrix}} \frac{1}{N𝔪}, D_{Γ}(x) = ∑_{f≤x} d_{Γ}(f) = ∑_{\begin{matrix}𝔪≠(0) \\ f_{Γ}(𝔪)≤x \end{matrix}} \frac{1}{N𝔪}.

Proposition 2.4 tells us that D_{Γ}(x) ≪ log x, so the fact that G(x) satisfies (∗) implies that

lim_{x→∞} G(x)D_{Γ}(x) = 0.

This allows us to apply Abel summation in the following calculation:

∑_{𝔪≠(0)} \frac{G(f_{Γ}(𝔪))}{N𝔪} = ∑_{f=1}^{∞} ∑_{\begin{matrix}𝔪≠(0) \\ f_{Γ}(𝔪)=f \end{matrix}} \frac{G(f)}{N𝔪} = ∑_{f=1}^{∞} G(f)d_{Γ}(f)

= − ∫_{1}^{∞} D_{Γ}(t)G′(t) dt (Abel summation [1, Thm. 4.2])

≤ − ∫_{1}^{∞} \{ε^{γ}κ_{K} log log H_{K}(Γ) + e^{γ}κ_{K} (1 + \frac{1}{r}) log t

+ O_{K}(r)} G′(t) dt (from (19). Note G′(t) < 0.)

= e^{γ}κ_{K} log log H_{K}(Γ) + e^{γ}κ_{K} (1 + \frac{1}{r}) ∫_{1}^{∞} \frac{G(t)}{t}dt + O_{K}(r)

(properties (∗) of G and integration by parts)

This completes the proof of the first inequality (9) of Theorem 2.1. The proof of the second inequality (10) is entirely similar, so we just briefly sketch. Thus we let

d̃_{Γ}(f) = ∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)=f \end{matrix}} \frac{log N𝔭}{N𝔭},  D̃_{Γ}(x) = ∑_{f≤x} d̃_{Γ}(f) = ∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)=f \end{matrix}} \frac{log N𝔭}{N𝔭}. (26)

Then

∑_{𝔭} G(f_{Γ}(𝔭))\frac{log N𝔭}{N𝔭} = ∑_{f=1}^{∞} G(f)d̃_{Γ}(f) = − ∫_{1}^{∞} D̃_{Γ}(t)G′(t) dt

≤ − ∫_{1}^{∞} \{log log H_{K}(Γ) + (1 + \frac{1}{r}) log t + O_{K}(r)\} G′(t) dt

= log log H_{K}(Γ) + (1 + \frac{1}{r}) ∫_{1}^{∞} \frac{G(t)}{t}dt + O_{K}(r).

§3. Bounds for abelian varieties

In this section we will prove an estimate for series associated to abelian varieties analogous to the series (26) of Theorem 2.1. We let K be a number field and R its ring of integers as in section 2, and we set the following additional notation for this section.

A/K an abelian variety defined over K.

A/R a Néron model for A/K.

ĥ_{K} the logarithmic canonical height on A(K), relative to K, associated to

a very ample symmetric divisor. Γ a free finitely generated subgroup of A(K) of rank r ≥ 1.

ĥ_{K}(Γ) the minimum value of ĥ_{K}(P_{1})+⋯+ĥ_{K}(P_{r})+1 over all sets of generators

{P_{1}, …, P_{r}} for Γ. (Note ĥ_{K}(Γ) ≥ 1.)

For each prime ideal 𝔭 of K, let

f_{Γ}(𝔭) = # Image(Γ ⟶ A mod 𝔭).

Theorem 3.1. With notation as above, let G(x) be a function satisfying the properties (∗) described in section 2. Then

∑_{𝔭} G(f_{Γ}(𝔭))\frac{log N𝔭}{N𝔭} ≤ log ĥ_{K}(Γ) + (1 + \frac{2}{r}) ∫_{1}^{∞} \frac{G(x)}{x}dx + O_{A/K}(r). (27)

We begin with an abelian analogue of Proposition 2.4.

Proposition 3.2. For all x ≥ 1,

∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)≤x \end{matrix}} \frac{log N𝔭}{N𝔭} ≤ log ĥ_{K}(Γ) + (1 + \frac{2}{r}) log x + O_{A/K}(r).  (28)

Proof. Fix generators P_{1}, …, P_{r} for Γ so that ĥ_{K}(Γ) = ĥ_{K}(P_{1}) + ⋯ + ĥ_{K}(P_{r}) + 1. For y ≥ 1, let

Γ(y) = {n_{1}P_{1} + ⋯ + n_{r}P_{r} ∈ Γ : |n_{1}|, …, |n_{r}| ≤ y}.

For any point P ∈ A(K), P ≠ O, define an ideal 𝔞_{P} by

𝔞_{P} = ∏_{\begin{matrix}𝔭 \\ P ≡O (mod 𝔭) \end{matrix}} 𝔭.

That is, 𝔞_{P} is the product of all prime ideals such that P reduces to the identity element on A mod 𝔭. Then we define another ideal

𝔄_{Γ}(y) = ∏_{P ∈Γ(y), P ≠O} 𝔞_{P} .

We begin with the following claim.

Claim 1 : If f_{Γ}(𝔭) ≤ x, then 𝔭|𝔄_{Γ}(x^{1/r} + 2).

We consider the map

Γ(y) ⟶ A mod 𝔭, P ⟼ P mod 𝔭.

The image has order #(Γ mod 𝔭) = f_{Γ}(𝔭) by definition. But for y ≥ 1, Γ(y) has at least (2y − 1)^{r} elements. Hence if we set y = \frac{1}{2}x^{1/r} + 1, then there is a strict inequality #Γ(y) > #(Γ mod 𝔭). Therefore we can find distinct elements P, Q ∈ Γ(y) with the same image modulo 𝔭. Then

P − Q ∈ Γ(y)  and  P − Q ≡ O (mod 𝔭),

so 𝔭|𝔞_{P −Q}. Therefore 𝔭|𝔄_{Γ}(2y), which completes the proof of Claim 1.

Using Claim 1 and inequality (14) of Corollary 2.3, we find that

∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)≤x \end{matrix}} \frac{log N𝔭}{N𝔭} ≤ ∑_{𝔭|𝔄_{Γ}(x^{1/r}+2)} \frac{log N𝔭}{N𝔭} ≤ log log N𝔄_{Γ}(x^{1/r} + 2) + O_{K}(1). (29)

To complete the proof of Proposition 3.2, we need an upper bound for N𝔄_{Γ}(y) as described in our second claim.

Claim 2 : log N𝔄_{Γ}(y) ≤ (6y)^{r+2}ĥ_{K}(Γ) + O_{A/K}((3y)^{r}).

To prove this claim, we first observe that since ĥ_{K} is defined relative to a very ample symmetric divisor D, we may assume that this divisor contains the zero element O of A. Then the canonical local height functions on A at a place 𝔭 satisfies

λ̂_{𝔭}(P) ≥ −c_{𝔭}  for all P ∈ A(K).  (32)
λ̂_{𝔭}(P) ≥ log N𝔭 − c_{𝔭} if P ≡ O (mod 𝔭).  (33)

Here the c_{𝔭}’s are M_{K}-constants which depend on A/K. That is, they are nonnegative constants for each place 𝔭) of K, and all but finitely many of them are zero. Now adding (32) and (33) over all places of K and using the definition of 𝔞_{P}, we find that

ĥ_{K}(P) = ∑_{𝔭} λ̂_{𝔭}(P) ≥ ∑_{\begin{matrix}𝔭 \\ P ≡O (mod 𝔭) \end{matrix}} log N𝔭 − ∑_{𝔭} c_{𝔭} = log N𝔞_{P} + O_{A/K}(1). (34)

Remark 3.2.1. For general facts about canonical local height functions, see [10, Ch. 11]. The lower bound (32) is a general property of local heights relative to positive divisors [10, Ch. 10, Prop. 3.1]. Further, (33) is an immediate consequence of[10, Ch. 11, Thm. 5.1], since if P ≡ O (mod 𝔭), then P mod 𝔭 lies on D mod 𝔭. Note that we are normalizing the local heights so that ĥ_{K}(P) = ∑_{v} λ̂_{v}(P). Also, we should mention that (32) is really only valid for points P not on the support of D. So we should really choose divisors D_{1}, …, D_{n} with D_{i} ∼ D and ∩|D_{i}| = {O} and consider (32) for each D_{i}. We will ignore this technicality.

Remark 3.2.2. For elliptic curves, it is possible to prove (34) in a much more elementary fashion. Thus let E/K be an elliptic curve and let x, y be coordinate functions for a Weierstrass equation for E/K. For any P ∈ E(K), P ≠ O, write the fractional ideal (x(P)) as 𝔟_{P} 𝔡_{P}^{−1}. Then P ≡ O (mod 𝔭) for all but finitely many prime ideals 𝔭|𝔡_{P}, so 𝔞_{P} |𝔡_{P}. (More precisely, this is true for all primes for which the given Weierstrass equation is minimal.) Then standard properties of the canonical height [14, VIII.9.3] give

ĥ_{K}(P) = h(x(P)) + O_{E/K}(1) ≥ log N𝔡_{P} + O_{E/K}(1) ≥ log N𝔞_{P} + O_{E/K}(1).

We now resume the proof of Claim 2. We compute

log N𝔄_{Γ}(y) = ∑_{P ∈Γ(y), P ≠O} log N𝔞_{P}

≤ ∑_{P ∈Γ(y)}(ĥ_{K}(P) + O_{A/K}(1)) (from (34))

= ∑_{|n_{1}|≤y} ⋯ ∑_{|n_{r}|≤y}(ĥ_{K}(n_{1}P_{1} + ⋯ + n_{r}P_{r}) + O_{A/K}(1))

≤ ∑_{|n_{1}|≤y} ⋯ ∑_{|n_{r}|≤y}(rn_{1}^{2}ĥ_{K}(P_{1}) + ⋯ + rn_{r}^{2}ĥ_{K}(P_{r}) + O_{A/K}(1))

(since ĥ_{K} is a positive definite quadratic form)

≤ r(2y + 1)^{r−1} \frac{y(y + 1)(2y + 1)}{6}(ĥ_{K}(P_{1}) + ⋯ + ĥ_{K}(P_{r}))

+ O_{A/K}((2y + 1)^{r})

≤ (6y)^{r+2}ĥ_{K}(Γ) + O_{A/K}((3y)^{r}).

This completes the proof of Claim 2.

We now apply Claim 2 with y = x^{1/r} + 2 and take the logarithm of both sides to obtain

log log N𝔄_{Γ}(x^{1/r} + 2) ≤ log{(6x^{1/r} + 12)^{r+2}ĥ_{K}(Γ) + O_{A/K}((3x^{1/r} + 6)^{r})}

= (r + 2) log(6x^{1/r} + 12) + log (ĥ_{K}(Γ) + O_{A/K} (\frac{1}{2^{r}y^{2}} ))

≤ (1 + \frac{2}{r}) log x + log ĥ_{K}(Γ) + O_{A/K}(r).  (35)

Substituting (35) into (29) gives (28), which completes the proof of Proposition 3.2.

We can now use Proposition 3.2 to prove Theorem 3.1 in exactly the same way that Proposition 2.4 was used to prove Theorem 2.1.

Proof (of Theorem 3.1). Let d̃_{Γ}(f) and D̃_{Γ}(x) be defined by the formulas (26) in section 2, although now Γ is a subgroup of A(K) rather than a subgroup of K^{∗}. Then D̃_{Γ}(x) ≪ log x from Proposition 3.2, so lim_{x→∞} G(x)D̃_{Γ}(x) = 0. This justifies our use of Abel summation in the following calculation:

∑_{𝔭} G(f_{Γ}(𝔭))\frac{log N𝔭}{N𝔭} = ∑_{f=1}^{∞} ∑_{\begin{matrix}𝔭 \\ f_{Γ}(𝔭)=f \end{matrix}} G(f)\frac{log N𝔭}{N𝔭} = ∑_{f=1}^{∞} G(f)d̃_{Γ}(f)

= − ∫_{1}^{∞} D̃_{Γ}(t)G′(t) dt (Abel summation [1, Thm. 4.2])

≤ − ∫_{1}^{∞} \{log ĥ_{K}(Γ) + (1 + \frac{2}{r}) log t + O_{A/K}(r)\} G′(t) dt

(from (28))

= log ĥ_{K}(Γ) + (1 + \frac{2}{r}) ∫_{1}^{∞} \frac{G(t)}{t}dt + O_{A,K}(r).

(properties (∗) of G and integration by parts)

This completes the proof of Theorem 3.1.

§4. Application to densities

In this section we will apply our earlier estimates to give bounds for the Dirichlet density of various sets. We let K be a number field as usual. For any set S of nonzero integral ideals of K, we define the upper Dirichlet density of S to be the quantity

δ(S) = lim sup_{s→1^{+}} \frac{∑_{𝔪∈S} N𝔪^{−s}}{∑_{𝔪≠(0)} N𝔪^{−s}} = lim sup_{s→1^{+}} \frac{s − 1}{κ_{K}} ∑_{𝔪∈S} \frac{1}{N𝔪^{s}} .

(Here κ_{K} is the residue of ζ_{K}(s) at s = 1, see section 2.)

We can use Theorem 2.1 to estimate the Dirichlet density of the ideals 𝔪 for which f_{Γ}(𝔪) is small.

Theorem 4.1. With notation as in section 2, for each real number 0 ≤ θ ≤ 1 we let

S_{Γ}(θ) = {ideals 𝔪 ≠ (0) such that f_{Γ}(𝔪) ≤ N𝔪^{θ}}.

Then

δ(S_{Γ}(θ)) ≤ e^{γ} (1 + \frac{1}{r}) θ.

In particular, if Γ = ⟨a⟩ has rank 1, then δ(S_{Γ}(θ)) ≤ 2e^{γ}θ < 57θ/16.

Proof. We begin by applying inequality (9) of Theorem 2.1 with G(x) = x^{−ε} to obtain the estimate

∑_{𝔪≠(0)} \frac{1}{N𝔪 · f_{Γ}(𝔪)^{ε}} ≤ e^{γ}κ_{K} (1 + \frac{1}{r}) ε^{−1} + O_{K,Γ}(1).  (36)

Notice that the big-O constant includes the term depending on Γ, but it is independent of ε.

Now we write s = 1 + ε and compute

∑_{𝔪∈S_{Γ}(θ)} \frac{1}{N𝔪^{s}} = ∑_{𝔪∈S_{Γ}(θ)} \frac{1}{N𝔪} · \frac{1}{N𝔪^{ε}}

≤ ∑_{𝔪∈S_{Γ}(θ)} \frac{1}{N𝔪} · \frac{1}{f_{Γ}(𝔪)^{ε/θ}} since f_{Γ}(𝔪) ≤ N𝔪^{θ} for 𝔪 ∈ S_{Γ}(θ)

≤ ∑_{𝔪≠(0)} \frac{1}{N𝔪} · \frac{1}{f_{Γ}(𝔪)^{ε/θ}}

≤ e^{γ}κ_{K} (1 + \frac{1}{r}) \frac{θ}{ε} + O_{K,Γ}(1) from (36)

= e^{γ}κ_{K} (1 + \frac{1}{r}) \frac{θ}{s − 1} + O_{K,Γ}(1).

Now multiply both sides by (s − 1)/κ_{K} and take the lim sup as s → 1^{+}. The left-hand side gives the upper Dirichlet density, so we find that

δ(S_{Γ}(θ)) ≤ e^{γ} (1 + \frac{1}{r}) θ.

This completes the proof of Theorem 4.1. (For the last statement, we just note that 2e^{γ} < 57/16.)

We can use Theorems 2.1 and 3.1 in a similar fashion to bound the primes for which f_{Γ}(𝔭) can be small. In this case it is more convenient to use the upper logarithmic Dirichlet density of a set of primes P, which is defined to be

δ̃(P) = lim sup_{s→1^{+}} \begin{matrix}∑_{𝔭∈P} & \frac{log N𝔭}{N𝔭^{s}} \\ ∑_{𝔭} & \frac{log N𝔭}{N𝔭^{s}} \end{matrix} = lim sup_{s→1^{+}}(s − 1) ∑_{𝔭∈P} \frac{log N𝔭}{N𝔭^{s}}.

Theorem 4.2. With notation as in section 2 or 3, let

P_{Γ}(θ) = {primes 𝔭 of K such that f_{Γ}(𝔭) ≤ N𝔭^{θ}}.

(a) Let Γ ⊂ K^{∗} be a free subgroup of K^{∗} as in section 2. Then

δ̃(P_{Γ}(θ)) ≤ (1 + \frac{1}{r}) θ.

(b) Let Γ ⊂ A(K) be a free subgroup of the Mordell-Weil group of an abelian variety as in section 3. Then

δ̃(P_{Γ}(θ)) ≤ (1 + \frac{2}{r}) θ.

Remark. Notice that if we take K = ℚ and Γ = ⟨a⟩ in Theorem 4.2(a), we find that the set

{primes p such that f_{a}(p) ≤ p^{θ}}  (37)

has upper logarithmic Dirichlet density at most 2θ. In particular, we can make the density as small as desired by taking θ sufficiently small. Using more advanced methods, Erdös and Murty [5] have shown that if θ < 1/2, then the set (37) has density 0.

Proof. Taking G(x) = x^{−ε} in inequality (10) of Theorem 2.1 gives

∑_{𝔭} \frac{log N𝔭}{N𝔭 · f_{Γ}(𝔭)^{ε}} ≤ (1 + \frac{1}{r}) ε^{−1} + O_{K,Γ}(1)  (38)

for the multiplicative group case. Similarly, using G(x) = x^{−ε} in inequality (27) of Theorem 3.1 gives

∑_{𝔭} \frac{log N𝔭}{N𝔭 · f_{Γ}(𝔭)^{ε}} ≤ (1 + \frac{2}{r}) ε^{−1} + O_{A/K,Γ}(1)  (39)

for the abelian variety case. Now both parts of Theorem 4.2 can be proven in exactly the same way as Theorem 4.1 by using (38) and (39) in place of (36).

Addendum. After this article was accepted for publication, Carl Pomerance was kind enough to draw our attention to his paper [11] and to another paper of Erdös [3]. In [3], Erdös gives an argument which shows (in our notation) that

D_{2}(x) ≤ (e^{γ} + o(1)) log x.

Using this estimate in our Theorem 1.1 would allow us to replace the term 2e^{γ}ε^{−1} with e^{γ}ε^{−1}. Using a more elaborate argument, Pomerance [11] proves the existence of a positive constant c so that

D_{2}(x) ≤ (e^{γ} − c + o(1)) log x.

Pomerance suggests (private communication) that in this case the correct constant is \frac{1}{2}e^{γ}, and more generally that one should have

D_{a}(x) ≤ \frac{ϕ(a)}{a}e^{γ} log x + e^{γ} log log a + O(1).

Pomerance’s article also contains much interesting information concerning the normal, minimal, and maximal orders of d_{a}(f) as a function of f.

References

1. T. Apostol, Introduction to Analytic Number Theory, UTM, Springer-Verlag, Berlin and New York, 1976.

2. H. Bilharz, Primdivisoren mit vorgegebener Primitivwürzel, Math. Annalen 114 (1937), 476– 3. Erdös, P., On some problems of Bellman and a theorem of Romanoff, J. Chinese Math. Soc.

1 (1951), 409–421.

4. , On the sum ∑_{d|2^{n}−1} d^{−1}, Israel J. Math. 9 (1971), 43–48.

5. P. Erdös and R. Murty, On the order of a (mod p), unpublished.

6. P. Erdös and P. Turan, Ein zahlentheoretischer Satz, Bull. de l’institut de Math. et Mêc. a l’université Konybycheff de Tomsk I (1935), 101–103.

7. , Über die vereinfachung eines Landauschen Satzes, Bull. de l’institut de Math. et Mêc. a l’université Konybycheff de Tomsk I (1935), 144–147.

8. G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Fourth edition, Oxford University Press, Oxford, 1975.

9. E. Landau, Verschärfung eines Romanoffschen Satzes, Acta Arith. (1935), 43–62.

10. S. Lang, Fundamentals of Diophantine Geometry, Springer-Verlag, New York, 1983.

11. C. Pomerance, On primitive divisors of Mersenne numbers, Acta Arithmetica XLVI (1986), 355–367.

12. N.P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109 (1934), 668– 678.

13. M. Rosen, A generalization of Mertens’ theorem; preprint, 1995.

14. J.H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Math., vol. 106, Springer-Verlag, Berlin and New York, 1986.

Mathematics Department McGill University Montréal, Canada E-mail address: murty@math.mcgill.ca

Mathematics Department Brown University Providence, RI 02912 USA E-mail address: michael rosen@brown.edu

Mathematics Department Brown University Providence, RI 02912 USA E-mail address: joseph silverman@brown.edu