Exponential Sums over Mersenne Numbers

William D. Banks

Dept. of Mathematics, University of Missouri Columbia, MO 65203, USA

bbanks@math.missouri.edu

Alessandro Conflitti

Dip. di Matematica, Università degli Studi di Roma “Tor Vergata”

Via della Ricerca Scientifica, I-00133 Roma, Italy

conflitt@mat.uniroma2.it

John B. Friedlander

Dept. of Mathematics, University of Toronto

Toronto, Ontario M5S 3G3, Canada

frdlndr@math.toronto.edu

Igor E. Shparlinski

Dept. of Computing, Macquarie University

Sydney, NSW 2109, Australia

   igor@ics.mq.edu.au

Abstract

We give estimates for exponential sums of the form

∑_{n≤N} Λ(n) exp(2πiag^{n}/m),

where m is a positive integer, a and g are integers relatively prime to m, and Λ(n) is the von Mangoldt function. We also discuss some applications of our results. In particular, our results yield bounds for exponential sums of the form

∑_{p≤N} exp(2πiaM_{p}/m),

where M_{p} is the Mersenne number M_{p} = 2^{p} − 1 for any prime p.

AMS Subject Classification Numbers: 11L07, 11L20.

1 Introduction

It is well-known that methods originating with Vinogradov [24] have been used successfully to find nontrivial estimates for a wide variety of exponential sums taken over the values of an integer polynomial at prime numbers. Certain modern and more convenient variants of these methods are due to Vaughan [23] and to Heath-Brown [10]. In this paper, we use such arguments to estimate exponential sums, taken again at prime values, where the integer polynomial is now replaced by an exponential function.

All of these methods employ a variant of the sieve of Eratosthenes to reduce the problem of estimating exponential sums over primes to that of deriving estimates for sums over consecutive integers and for a certain double sum with weights. For the case that we are considering here there are already in the literature a number of bounds for similar sums taken over consecutive integer values [12, 13, 14, 19, 20]. The corresponding double sums have not been previously studied, however. In Section 2, we obtain such bounds as a generalization of those in [7, 9].

Let m be an arbitrary positive integer. Put e(α) = exp(2πiα) for any real number α, and e_{m}(α) = e(α/m). Our goal is to estimate exponential sums of the form

∑_{n≤N} Λ(n) e_{m}(ag^{n}),

where a and g are integers relatively prime to m. As usual,

Λ(n) = \begin{cases}log p & if n is a power of a prime p, \\ 0 & otherwise, \end{cases}

is the von Mangoldt function, and log z denotes the natural logarithm of z. Let t denote the multiplicative order of g modulo m. We show that for any given δ > 0, the exponential sum above is small whenever t ≥ m^{10/11+δ} and N ≥ t^{5/8+δ}m^{7/4}.

Applying these considerations to the case g = 2, we deduce that, under the same conditions,

∑_{p≤N} e_{m}(aM_{p}) = o(π(N)),  (1)

where for any prime p, M_{p} is the Mersenne number defined by M_{p} = 2^{p} − 1. Here π(N) denotes the number of primes p ≤ N.

Certainly, it seems an interesting goal to ease the above restrictions so as to obtain estimates when the period t is smaller and also to treat shorter sums where the method given in our principal arguments (Section 3) seems to fail. Ironically, that method also fails to apply to the very long sums, which should be the easier ones, and so, to achieve the full range of uniformity stated above, we need to add (in Section 4) some refinements and further ingredients which depend on the distribution of primes in arithmetic progressions.

Throughout the paper, the implied constants in symbols ‘O’ and ‘≪’ may depend, where obvious, on one of the small positive parameters ε or δ and are absolute otherwise (we recall that A ≪ B is equivalent to A = O(B) ). For example, the well-known bound

τ(n) ≪ n^{ε}  (2)

holds for any ε > 0, where τ(n) denotes the number of positive integer divisors of n ∈ ℕ.

All of our results below are uniform in all parameters except (when present) ε or δ. In particular, our bounds are uniform over all integers a relatively prime to the modulus and over all integers g with the same multiplicative order modulo m or q.

2 Preparation

We use the following result of [23] in the form given in Chapter 24 of [4]:

Lemma 2.1. For any complex-valued function f(n) and any real numbers U, V > 1 with UV ≤ N, we have

∑_{n≤N} Λ(n)f(n) ≪ Σ_{1} + Σ_{2} + Σ_{3} + |Σ_{4}|,

where

Σ_{1} = |∑_{n≤U} Λ(n)f(n)| ,

Σ_{2} = (log UV) ∑_{v≤UV} | ∑_{s≤N/v} f(sv)| ,

Σ_{3} = (log N) ∑_{v≤V} max_{w≥1} | ∑_{w≤s≤N/v} f(sv)| ,

Σ_{4} = ∑_{\begin{matrix}kℓ≤N \\ k>V, ℓ>U \end{matrix}} Λ(ℓ) | ∑_{d|k, d≤V} μ(d)| f(kℓ).

The next result is essentially Theorem 10 in Chapter 1 of [14]; see also the proof of Lemma 2 in [13].

Lemma 2.2. Let ϑ be of multiplicative order T modulo a positive integer m. Then, for any H_{1} < H_{2} and any integer a relatively prime to m,

∑_{H_{1}<x≤H_{2}} e_{m}(aϑ^{x}) ≪ (\frac{H_{2} − H_{1}}{T} + 1) m^{1/2} log m.

In fact, the statement referred to in [14] is the corresponding bound

|∑_{x=1}^{T} e_{m}(aϑ^{x}) e_{T} (bx)| ≤ m^{1/2}  (3)

for the relevant complete sum, which is valid for any integer b. Lemma 2.2 follows from this by the standard method of “completing the sum.” Thus, the factor log m occurring in Lemma 2.2 is really only necessary for the second term on the right side, not the first.

We also need the following variant of the bound (3).

Lemma 2.3. Let ϑ be of multiplicative order T modulo a positive integer m. Then, for any integer a relatively prime to m,

∑_{\begin{matrix}x=1 \\ gcd(x,T)=1 \end{matrix}}^{T} e_{m}(aϑ^{x}) ≪ 2^{ν(T)}m^{1/2},

where ν(T) is the number of distinct prime divisors of T.

Proof. Using the inclusion-exclusion principle to detect the coprimality condition gcd(x, T) = 1, we obtain

∑_{\begin{matrix}x=1 \\ gcd(x,T)=1 \end{matrix}}^{T} e_{m}(aϑ^{x}) = ∑_{d|T} μ(d) ∑_{\begin{matrix}x=1 \\ x≡0 (mod d) \end{matrix}}^{T} e_{m}(aϑ^{x}) = ∑_{d|T} μ(d) ∑_{x=1}^{T/d} e_{m}(aϑ^{dx}),

where, as usual, μ denotes the Möbius function. Because ϑ^{d} is of multiplicative order T/d, we can use the bound (3), which gives

| ∑_{\begin{matrix}x=1 \\ gcd(x,T)=1 \end{matrix}}^{T} e_{m}(aϑ^{x})| ≤ m^{1/2} ∑_{d|T} |μ(d)| = 2^{ν(T)}m^{1/2}.

The following statement is the most important special case of Theorem 9 from [7].

Lemma 2.4. Let ϑ be of multiplicative order T modulo a positive integer m. Then, for any integers a and b with gcd(a, m) = 1, we have

∑_{y=1}^{T} |∑_{x=1}^{T} e_{m}(aϑ^{x} + bϑ^{xy})|^{4} ≪ T^{9/4}m^{5/2+ε}.

We are now ready to prove our basic estimate for weighted double sums that is needed for the Vaughan combinatorial lemma. For any sequence α = (α_{k}) of complex numbers with finite support, we denote its ℓ_{2} norm by

∥α∥ = (∑_{k} |α_{k}|^{2})^{1/2} .

Lemma 2.5. Let m be a positive integer, g an integer relatively prime to m, and t the multiplicative order of g modulo m. Let K, L, X, Y be real numbers with X, Y > 0. Then, for any two sequences of complex numbers α = (α_{k}) supported on the interval [K, K + X] and β = (β_{ℓ}) supported on [L, L + Y], and for any integer a relatively prime to m, we have

∑_{\begin{matrix}K<k≤K+X \\ L<ℓ≤L+Y \end{matrix}} α_{k} β_{ℓ} e_{m}(ag^{kℓ}) ≪ ∥α∥∥β∥(X/t + 1)^{1/2}(Y/t + 1)^{1/2}t^{21/32}m^{5/16+ε}.

Proof. First we group together terms in the sum in accordance with the greatest common divisor of ℓ and t. By the triangle inequality,

| ∑_{\begin{matrix}K<k≤K+X \\ L<ℓ≤L+Y \end{matrix}} α_{k} β_{ℓ} e_{m}(ag^{kℓ})| ≤ ∑_{d|t} σ_{d}(a),

where

σ_{d}(a) = | ∑_{K<k≤K+X} ∑_{\begin{matrix}L<ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} α_{k} β_{ℓ} e_{m}(ag^{kℓ})| .

Using the Cauchy inequality, we find

σ_{d}(a)^{2} ≤ ∑_{K<k≤K+X} |α_{k}|^{2} ∑_{K<k≤K+X} | ∑_{\begin{matrix}L<ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} β_{ℓ} e_{m}(ag^{kℓ})|^{2}

≤ ∥α∥^{2}(X/t + 1) ∑_{k=1}^{t} | ∑_{\begin{matrix}L<ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} β_{ℓ} e_{m}(ag^{kℓ})|^{2}

= ∥α∥^{2}(X/t + 1) ∑_{\begin{matrix}L<ℓ,r≤L+Y \\ gcd(ℓ,t)=gcd(r,t)=d \end{matrix}} β_{ℓ} \overline{β_{r}} ∑_{k=1}^{t} e_{m}(a(g^{kℓ} − g^{kr})).

Since 2|β_{ℓ} \overline{β_{r}}| ≤ |β_{ℓ}|^{2} + |β_{r}|^{2}, we deduce that

σ_{d}(a)^{2} ≤ \frac{1}{2}∥α∥^{2}(X/t + 1) ∑_{\begin{matrix}L<ℓ,r≤L+Y \\ gcd(ℓ,t)=gcd(r,t)=d \end{matrix}} |β_{ℓ}|^{2} |∑_{k=1}^{t} e_{m}(a(g^{kℓ} − g^{kr}))|

+\frac{1}{2}∥α∥^{2}(X/t + 1) ∑_{\begin{matrix}L<ℓ,r≤L+Y \\ gcd(ℓ,t)=gcd(r,t)=d \end{matrix}} |β_{r}|^{2} |∑_{k=1}^{t} e_{m}(a(g^{kℓ} − g^{kr}))|

= ∥α∥^{2}(X/t + 1) ∑_{\begin{matrix}L<ℓ,r≤L+Y \\ gcd(ℓ,t)=gcd(r,t)=d \end{matrix}} |β_{ℓ}|^{2} |∑_{k=1}^{t} e_{m}(a(g^{kℓ} − g^{kr}))|

≤ ∥α∥^{2}(X/t + 1)(Y/t + 1)

× ∑_{\begin{matrix}L≤ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} |β_{ℓ}|^{2} ∑_{\begin{matrix}1≤r≤t \\ gcd(r,t)=d \end{matrix}} |∑_{k=1}^{t} e_{m}(a(g^{kℓ} − g^{kr}))| .

Since each element ℓ with gcd(ℓ, t) = d can be represented in the form ℓ = dw with gcd(w, t/d) = 1, and ϑ_{d} = g^{d} is of multiplicative order t/d, it follows that the inner double sum over r and k does not depend on ℓ (to see this, make the change of variables k ↦ kw^{−1}, r ↦ rw). Therefore,

σ_{d}(a)^{2}

≤ ∥α∥^{2}(X/t + 1)(Y/t + 1) ∑_{\begin{matrix}L≤ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} |β_{ℓ}|^{2} ∑_{\begin{matrix}1≤r≤t \\ gcd(r,t)=d \end{matrix}} |∑_{k=1}^{t} e_{m}(a(g^{kd} − g^{kr}))|

≤ ∥α∥^{2}(X/t + 1)(Y/t + 1) ∑_{\begin{matrix}L≤ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} |β_{ℓ}|^{2} ∑_{r=1}^{t/d} |∑_{k=1}^{t} e_{m}(a(ϑ_{d}^{k} − ϑ_{d}^{kr}))|

= ∥α∥^{2}(X/t + 1)(Y/t + 1)dS ∑_{\begin{matrix}L≤ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} |β_{ℓ}|^{2},

where

S = ∑_{r=1}^{t/d} |∑_{k=1}^{t/d} e_{m}(a(ϑ_{d}^{k} − ϑ_{d}^{kr}))| .

By the Hölder inequality and Lemma 2.4, we see that

S^{4} ≤ (t/d)^{3} ∑_{r=1}^{t/d} |∑_{k=1}^{t/d} e_{m}(a(ϑ_{d}^{k} − ϑ_{d}^{kr}))|^{4} ≪ (t/d)^{3}(t/d)^{9/4}m^{5/2+ε},

so that

dS ≪ t^{21/16}d^{−5/16}m^{5/8+ε} ≪ t^{21/16}m^{5/8+ε}.

Consequently,

σ_{d}(a) ≪ ∥α∥(X/t + 1)^{1/2}(Y/t + 1)^{1/2}t^{21/32}m^{5/16+ε}( ∑_{\begin{matrix}L≤ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} |β_{ℓ}|^{2})^{1/2}

for every divisor d | t. Summing over d and using the Cauchy inequality, we obtain

∑_{d|t}( ∑_{\begin{matrix}L≤ℓ≤L+Y \\ gcd(ℓ,t)=d \end{matrix}} |β_{ℓ}|^{2})^{1/2} ≤ (τ(t))^{1/2} ∥β∥.

Applying the bound (2) and taking into account the fact that t ≤ m, we obtain the stated result.

In the special case where m = q is a prime number one can improve upon the preceding results. In this case, instead of Lemma 2.4, we use the following stronger bound from [2] (see also [3] for an earlier result of this type).

Lemma 2.6. Let ϑ be of multiplicative order T modulo a prime number q. Then, for any integers a and b with gcd(a, q) = 1, we have

∑_{y=1}^{T} |∑_{x=1}^{T} e_{q}(aϑ^{x} + bϑ^{xy})|^{4} ≪ T^{11/3}q.

Using Lemma 2.6 in place of Lemma 2.4, we obtain the following stronger analogue of Lemma 2.5.

Lemma 2.7. Let q be a prime number, a and g integers not divisible by q, and t the multiplicative order of g modulo q. Let K, L, X, Y be real numbers with X, Y > 0. Then, for any two sequences of complex numbers α = (α_{k}) supported on the interval [K, K + X] and β = (β_{ℓ}) supported on [L, L + Y], we have

∑_{\begin{matrix}K<k≤K+X \\ L<ℓ≤L+Y \end{matrix}} α_{k} β_{ℓ} e_{m}(ag^{kℓ}) ≪ ∥α∥∥β∥(X/t + 1)^{1/2}(Y/t + 1)^{1/2}t^{5/6}q^{1/8+ε}.

Finally, we need the following result.

Lemma 2.8. For K^{1/2} ≤ X ≤ K, we have the bounds

∑_{K<k≤K+X} τ(k) ≪ X log K  and  ∑_{K<k≤K+X} τ^{2}(k) ≪ X(log K)^{3}.

These bounds, actually valid in a larger range, may be found for example as special cases of Theorem 2 from [22].

3 Main Results

Theorem 3.1. Fix ε > 0. Let m be a positive integer, g an integer relatively prime to m, and t the multiplicative order of g modulo m. Then we have the bound

max_{gcd(a,m)=1} |∑_{n≤N} Λ(n) e_{m}(ag^{n})| ≪ (Nt^{−11/32}m^{5/16} + N^{5/6}t^{5/48}m^{7/24}) N^{ε},

where the implied constant depends only on ε.

Proof. Let U, V > 1 with UV ≤ N and apply Lemma 2.1 with the function f(n) = e_{m}(ag^{n}). In the notation of that lemma we have, by Chebyshev’s bound,

Σ_{1} = | ∑_{1≤n≤U} Λ(n)f(n)| ≤ ∑_{1≤n≤U} Λ(n) ≪ U.  (4)

Next, since the multiplicative order of ϑ = g^{v} is t/ gcd(t, v), Lemma 2.2 yields the bound

Σ_{2} ≤ log N ∑_{1≤v≤UV} (\frac{N gcd(t, v)}{vt} + 1) m^{1/2} log m

≤ Nt^{−1}m^{1/2} log N log m ∑_{1≤v≤UV} \frac{gcd(t, v)}{v} + UV m^{1/2} log N log m.

Moreover,

∑_{1≤v≤UV} \frac{gcd(t, v)}{v} = ∑_{d|t} ∑_{\begin{matrix}1≤v≤UV \\ gcd(t,v)=d \end{matrix}} \frac{d}{v} ≤ ∑_{d|t} ∑_{\begin{matrix}1≤v≤UV \\ d|v \end{matrix}} \frac{d}{v}

= ∑_{d|t} ∑_{1≤w≤UV/d} \frac{1}{w} ≪ ∑_{d|t} log UV ≤ τ(t) log N.

Therefore, we obtain the estimate

Σ_{2} ≪ (Nt^{−1}m^{1/2} + UV m^{1/2}) N^{ε}.  (5)

Similarly, we obtain the stronger bound

Σ_{3} ≪ (Nt^{−1}m^{1/2} + V m^{1/2}) N^{ε}.  (6)

It remains only to estimate Σ_{4}. Let us denote

A(k) = | ∑_{d|k, d≤V} μ(d)| ,

so that using (2), we obtain

A(k) ≤ τ(k) ≪ k^{ε/4} and Λ(ℓ) ≤ log ℓ ≪ ℓ^{ε/4}.  (7)

Now, let Δ be fixed in the range 1/V < Δ < 1/2, and define the set

Ω = {V (1 + Δ)^{i} | 0 ≤ i ≤ R} ,

where

R = ⌊\frac{log(N/V)}{log(1 + Δ)}⌋ ≪ Δ^{−1} log N.

Then

Σ_{4} = ∑_{\begin{matrix}kℓ≤N \\ k>V, ℓ>U \end{matrix}} A(k) Λ(ℓ) e_{m}(ag^{kℓ}) = ∑_{K∈Ω} σ(K),

where

σ(K) = ∑_{\begin{matrix}K<k≤K(1+Δ) \\ k<N/U \end{matrix}} ∑_{U<ℓ≤N/k} A(k) Λ(ℓ) e_{m}(ag^{kℓ}).

For any k in the range K < k ≤ K(1+Δ), we have N/k = N/K+O(ΔN/K). Assuming that

ΔN ≥ K  (8)

and using (7), it follows that

σ(K) = σ̃(K) + O(Δ^{2}N^{1+3ε/4}),

where

σ̃(K) = ∑_{\begin{matrix}K<k≤K(1+Δ) \\ k<N/U \end{matrix}} ∑_{U<ℓ≤N/K} A(k) Λ(ℓ) e_{m}(ag^{kℓ}).

Because Ω has at most O(Δ^{−1} log N) elements, it follows that

Σ_{4} = ∑_{K∈Ω} σ̃(K) + O(ΔN^{1+ε}).  (9)

We can estimate each σ̃(K), using Lemma 2.5 together with (7), obtaining

σ̃(K) ≪ N^{ε}(ΔK)^{1/2}(N/K)^{1/2}(ΔK/t + 1)^{1/2}(N/Kt + 1)^{1/2}t^{21/32}m^{5/16}. We write this as

σ̃(K) ≪ σ̃_{1}(K) + σ̃_{2}(K) + σ̃_{3}(K) + σ̃_{4}(K),  (10)

where

σ̃_{1}(K) = ΔN^{1+ε}t^{−11/32}m^{5/16},
σ̃_{2}(K) = ΔN^{1/2+ε}K^{1/2}t^{5/32}m^{5/16},
σ̃_{3}(K) = Δ^{1/2}N^{1+ε}K^{−1/2}t^{5/32}m^{5/16},
σ̃_{4}(K) = Δ^{1/2}N^{1/2+ε}t^{21/32}m^{5/16}.

For any real number α we trivially have

∑_{\begin{matrix}K∈Ω \\ A≤K≤B \end{matrix}} K^{α} ≪ Δ^{−1}(B^{α} + A^{α}) log N.

In particular, we derive that

∑_{K∈Ω} σ̃_{1}(K) ≪ N^{1+ε}t^{−11/32}m^{5/16},
∑_{K∈Ω} σ̃_{2}(K) ≪ N^{1+ε}U^{−1/2}t^{5/32}m^{5/16},
∑_{K∈Ω} σ̃_{3}(K) ≪ Δ^{−1/2}N^{1+ε}V^{−1/2}t^{5/32}m^{5/16},
∑_{K∈Ω} σ̃_{4}(K) ≪ Δ^{−1/2}N^{1/2+ε}t^{21/32}m^{5/16},

which is valid for every ε > 0. Putting these results together with (9) and (10), and then with (4), (5) and (6), we find that

Σ_{4} ≪ (B_{1} + B_{2} + B_{3} + B_{4} + B_{5}) N^{ε},

and

∑_{n≤N} Λ(n) e_{m}(ag^{n}) ≪ |Σ_{4}| + Σ_{1} + Σ_{2} + Σ_{3}
≪ (B_{1} + B_{2} + B_{3} + B_{4} + B_{5} + B_{6} + B_{7}) N^{ε},

where

B_{1} = Nt^{−11/32}m^{5/16},
B_{2} = NU^{−1/2}t^{5/32}m^{5/16},
B_{3} = Δ^{−1/2}NV^{−1/2}t^{5/32}m^{5/16},
B_{4} = Δ^{−1/2}N^{1/2}t^{21/32}m^{5/16},
B_{5} = ΔN,
B_{6} = Nt^{−1}m^{1/2},
B_{7} = UV m^{1/2}.

Note that the result is trivial unless B_{1} ≤ N and so we can assume that t ≥ m^{10/11}. From this it follows that B_{6} ≤ B_{1}, thus B_{6} can be neglected.

Next we choose U and V. We balance B_{2} and B_{3} by setting U = ΔV, and then we balance both of these with B_{7} by choosing

U = Δ^{2/5}N^{2/5}t^{1/16}m^{−3/40},

which gives

B_{2} = B_{3} = B_{7} = Δ^{−1/5}N^{4/5}t^{1/8}m^{7/20}.

It is easy to see these choices are optimal.

Now we choose Δ to balance these with B_{5}, the appropriate choice being

Δ = N^{−1/6}t^{5/48}m^{7/24};

this gives

B_{2} = B_{3} = B_{5} = B_{7} = N^{5/6}t^{5/48}m^{7/24}.

This would certainly be an optimal choice for Δ were it not for the presence of B_{4}. Fortunately, this term does not present any real difficulty. Indeed, it can now be seen that, for a nontrivial bound, we require N ≥ t^{5/8}m^{7/4}. Using this together with the trivial bound t ≤ m and the above choice of Δ, one verifies that

B_{4} = N^{7/12}t^{29/48}m^{1/6} < B_{5}.

It remains only to check that our choices of U, V, Δ satisfy the mild size restrictions imposed earlier. Since we can assume N ≥ 64t^{5/8}m^{7/4}, else the theorem is trivial, this implies Δ ≤ 1/2 as required. We also have

ΔV ≥ ΔU = N^{1/6}t^{5/24}m^{1/3} > 1

so that Δ > 1/U > 1/V and U, V > 1. In particular, since K ≤ N/U, we see that the assumption (8) is satisfied for this choice of parameters. Finally,

UV = Δ^{−3}(ΔU)^{2} = N^{5/6}t^{5/48}m^{−5/24} ≤ N

since t ≤ m. The result follows.

Theorem 3.2. Fix ε > 0. Let q be a prime number, g an integer not divisible by q, and t the multiplicative order of g modulo q. We have

max_{gcd(a,q)=1} |∑_{n≤N} Λ(n) e_{q}(ag^{n})| ≪ (Nt^{−1/6}q^{1/8} + N^{5/6}t^{2/9}q^{1/6}) N^{ε},

where the implied constant depends only on ε.

Proof. We follow the proof of Theorem 3.1 and keep the same notation. Applying Lemma 2.7 instead of Lemma 2.5, together with the estimate (7), we obtain that

σ̃(K) ≪ N^{ε}(ΔK)^{1/2}(N/K)^{1/2}(ΔK/t + 1)^{1/2}(N/Kt + 1)^{1/2}t^{5/6}q^{1/8}.

This improvement leads to the bound

∑_{n≤N} Λ(n) e_{m}(ag^{n}) ≪ (B_{1} + B_{2} + B_{3} + B_{4} + B_{5} + B_{6} + B_{7}) N^{ε},

where

B_{1} = Nt^{−1/6}q^{1/8},
B_{2} = NU^{−1/2}t^{1/3}q^{1/8},
B_{3} = Δ^{−1/2}NV^{−1/2}t^{1/3}q^{1/8},
B_{4} = Δ^{−1/2}N^{1/2}t^{5/6}q^{1/8},
B_{5} = ΔN,
B_{6} = Nt^{−1}q^{1/2},
B_{7} = UV q^{1/2}.

Balancing these expressions as before leads to the choice

U = ΔV = Δ^{2/5}N^{2/5}t^{2/15}q^{−3/20},

then to

Δ = N^{−1/6}t^{2/9}q^{1/6}.

Since the result is otherwise trivial we can assume that t ≥ q^{3/4} and that N ≥ 64t^{4/3}q; then B_{j} ≤ N for j = 1, …, 6, B_{5} < B_{1}, and B_{4} < B_{2} = B_{3} = B_{6} = B_{7}. Since we can also check that 1/V < 1/U < Δ ≤ 1/2, and that U, V > 1, UV < N, the result follows.

4 Longer Sums

The results of the previous section are not quite sufficient to give the range of uniformity claimed in the introduction. It is easy to see that, as stated, the above estimates become trivial when N becomes extremely large in relation to m. Indeed, the factor N^{ε}, which is not important when N and m are of the same logarithmic order, becomes crucial for larger values of N. Nevertheless, it is possible to overcome this problem by a slightly more careful treatment which we now describe.

Theorem 4.1. Let m be a positive integer and g an integer relatively prime to m. For each δ > 0, there exists η > 0 such that if the multiplicative order t of g modulo m satisfies t ≥ m^{10/11+δ}, then for all N ≥ t^{5/8+δ}m^{7/4} we have the bound

max_{gcd(a,m)=1} |∑_{n≤N} Λ(n) e_{m}(ag^{n})| ≪ Nt^{−η},

where the implied constant depends only on δ.

Proof. Let us fix a large constant A > 0. For N ≤ m^{A}, the desired result follows immediately from Theorem 3.1.

We now extend the range of N for which our bound is nontrivial from m^{A} up to exp(m^{γ}) for some fixed γ > 0. To do this, it suffices to replace the factor N^{ε} in Theorem 3.1 by any expression of the form m^{ε}(log N)^{c}, where c > 0 is an absolute constant. Examining our earlier treatment, we see at once that in our bounds for Σ_{1}, Σ_{2}, and Σ_{3}, the factor N^{ε} can easily be replaced by m^{ε}(log N)^{2}.

For Σ_{4}, the matter is a bit more complicated. To estimate Σ_{4} we apply Lemma 2.8 to the sums

∑_{K<k≤K(1+Δ)} A(k),  ∑_{K<k≤K(1+Δ)}(A(k))^{2},  K ∈ Ω,

using the trivial bound A(k) ≤ τ(k). To verify that Lemma 2.8 is applicable note that

\frac{log(ΔK)}{log K} = 1 + \frac{log Δ}{log K} ≥ 1 + \frac{log Δ}{log V}.

When N > m^{A} and A > 0 is large, which we can assume to be the case, it is easily checked that with our earlier choice of the parameters the right hand side is 2/3 + o(1) as A increases. We choose A sufficiently large so that the right hand side is at least 1/2.

Tracing through the reasoning in our earlier treatment of Σ_{4}, the first change required is in the approximation of σ(K). To this end we require the first part of Lemma 2.8 which together with trivial bound Λ(ℓ) ≤ log N yields

∑_{\begin{matrix}K<k≤K(1+Δ) \\ k<N/U \end{matrix}} ∑_{N/k<ℓ≤N/K} A(k) Λ(ℓ) ≪ ΔNK^{−1} log N ∑_{\begin{matrix}K<k≤K(1+Δ) \\ k<N/U \end{matrix}} A(k)

≪ Δ^{2}N(log N)^{2}.

The approximation now becomes

σ(K) = σ̃(K) + O (Δ^{2}N(log N)^{2}) ,

so that (9) is sharpened to

Σ_{4} = ∑_{K∈Ω} σ̃(K) + O(ΔN(log N)^{3}).

Next, in the application of Lemma 2.5 that provides bounds for each σ̃_{j}(K), 1 ≤ j ≤ 4, we now use the second part of Lemma 2.8 to estimate the sum over k, and we use the trivial bound Λ(ℓ) ≤ log N together with the Chebyshev bound to estimate the sum over ℓ. We find that N^{ε} can here be replaced by m^{ε}(log N)^{2}. A further factor of log N is introduced when these bounds are summed over K ∈ Ω.

Thus, without even bothering to optimize the final exponent of log N, we can choose it to be c = 3 and take U, V, and Δ as before. As a result, we obtain the bound of Theorem 3.1 but with N^{ε} replaced by m^{ε}(log N)^{3}, and this extends the range for N (for which the results save a power of t) up to exp(m^{γ}) for any fixed γ < 3.

By refining our method in the manner indicated above, we can dispense with the case m > (log N)^{C} for any C > 3, so that in the remaining case we may assume m ≤ (log N)^{C}, say with C = 4, which can be treated (as if the period m of the exponential sum is essentially fixed) by appealing to the Siegel–Walfisz theorem for the distribution of primes in arithmetic progressions modulo t. Thus

ψ(N; t, b) = ∑_{\begin{matrix}n≤N \\ n≡b (mod t) \end{matrix}} Λ(n) = χ_{0}(b)N/φ(t) + O(N(log N)^{−8}),

where φ is the Euler function, χ_{0} is the principal character modulo t, and where 8 can be replaced by whatever we like. This result may be found (in more general form) in many places. It occurs for example in Chapter 22 of [4], albeit not under the name Siegel–Walfisz.

We can write our exponential sum in the form

∑_{n≤N} Λ(n) e_{m}(ag^{n}) = ∑_{b=1}^{t} e_{m}(ag^{b})ψ(N; t, b).

On insertion of this in the asymptotic formula for ψ the error term therein gives a contribution E which satisfies the bound

E ≪ tN(log N)^{−8} ≪ Nt^{−1}.

The main term gives a contribution

M = \frac{N}{φ(t)} ∑_{\begin{matrix}b=1 \\ gcd(b,t)=1 \end{matrix}}^{t} e_{m}(ag^{b})

and to complete the argument it remains to recall Lemma 2.3, the inequality 2^{ν(t)} ≤ τ(t) and the bound (2).

Theorem 4.1 implies that for any δ > 0, there exists positive real η such that if N ≥ t^{5/8+δ}m^{7/4} and t ≥ m^{10/11+δ}, then

max_{gcd(a,m)=1} |∑_{p≤N} e_{m} (ag^{p})| ≪ π(N)t^{−η},  (11)

where the sum runs over all primes p ≤ N. In particular, this bound holds for exponential sums over Mersenne numbers, hence we obtain (1) under the stated conditions (with t equal to the order of g = 2 modulo m). Indeed,

|∑_{p≤N} e_{m} (a(g^{p} − 1))| = |e_{m}(−a) ∑_{p≤N} e_{m} (ag^{p})| = |∑_{p≤N} e_{m} (ag^{p})|

and, applying partial summation, we obtain

∑_{p≤N} e_{m} (ag^{p}) = ∑_{2≤n≤N} \frac{1}{log n}Λ(n) e_{m}(ag^{n}) + O(N^{1/2})

= \frac{1}{log N} ∑_{n=2}^{N} Λ(n) e_{m}(ag^{n})

+ ∑_{M=2}^{N−1} (\frac{1}{log M} − \frac{1}{log(M + 1)}) ∑_{n=2}^{M} Λ(n) e_{m}(ag^{n}) + O(N^{1/2})

≪ \frac{1}{log N} |∑_{n=2}^{N} Λ(n) e_{m}(ag^{n})| + ∑_{M=2}^{N−1} \frac{1}{M log^{2} M} |∑_{n=2}^{M} Λ(n) e_{m}(ag^{n})| + N^{1/2}.

After simple calculations, we obtain (11). Also, by Theorem 3.1 we see that

max_{gcd(a,m)=1} |∑_{p≤N} e_{m} (aM_{p})| ≪ (Nt^{−11/32}m^{5/16} + N^{5/6}t^{5/48}m^{7/24}) N^{ε}

for any ε > 0.

Analogously, for sums with prime denominators, we obtain the following result.

Theorem 4.2. Let q be a prime number, g an integer relatively prime to q. For each δ > 0, there exists η > 0 such that if the multiplicative order t of g modulo q satisfies t ≥ q^{3/4+δ}, then for all N ≥ t^{4/3+δ}q we have

max_{gcd(a,q)=1} |∑_{n≤N} Λ(n) e_{q}(ag^{n})| ≪ Nt^{−η},

where the implied constant depends only on δ.

Theorem 4.2 implies that for any δ > 0, there exists positive real η such that if N ≥ t^{4/3+δ}q and t ≥ q^{3/4+δ}, then

max_{gcd(a,q)=1} |∑_{p≤N} e_{q}(ag^{p})| ≪ π(N)t^{−η}.

In particular, this bound also holds for exponential sums over Mersenne numbers and implies (1) when m = q is prime and the above conditions hold.

From Theorem 3.2 we also have

max_{gcd(a,q)=1} |∑_{p≤N} e_{q} (aM_{p})| ≪ (Nt^{−1/6}q^{1/8} + N^{5/6}t^{2/9}q^{1/6}) N^{ε}

for any ε > 0.

5 Remarks

Our results are nontrivial provided that the multiplicative order t of g modulo m (or q) is sufficiently large. Although this should frequently be the case, unconditional results in this direction are still rather weak (see [5, 11, 16, 18, 21]) and only guarantee that when g is fixed, t is of order at least m^{1/2} for almost all integers m, and of order at least q^{1/2} for almost all primes q. We recall, however, that under the Extended Riemann Hypothesis, it is known that t is of order m for almost all integers m and of order q for almost all primes q; see [5, 15, 17]. We also remark that the results of [1] show that for many primes q, the order t of g modulo q is substantially larger than q^{1/2}. In particular, it follows from [1] that t ≥ q^{0.677} for at least cx/ log^{2} x primes q ≤ x with a positive constant c.

Using some of the results of [7], which hold for an arbitrary modulus m, one can estimate exponential sums over Fermat numbers F_{n} = 2^{2^{n}} + 1. Unfortunately, proving that there are members of this sequence of sufficiently large period modulo m appears to be quite difficult, and it is not clear whether there are any values of m for which the corresponding bound is nontrivial, although one certainly would expect this to be the case. Even for sums with a prime denominator q, the bounds from [6] (which are stronger than those for the general case of [7]) do not overlap with what is currently known about the period of F_{n} modulo q; see [8].

Finally, we note that it would be of very great interest to estimate the sums

∑_{n≤N} Λ(n)χ(g^{n} + a), gcd(a, m) = 1,

with multiplicative characters χ modulo m. Unfortunately, analogues of our underlying results, that is, those of [2] and [7], are not known for multiplicative characters.

6 Acknowledgements

During the preparation of this paper, W. B. was supported in part by NSF grant DMS-0070628 and by Macquarie University (Sydney), J. F. was supported in part by NSERC grant A5123 and by the Max Planck Institut für Mathematik (Bonn), and I. S. was supported in part by ARC grant A00000184.

References

[1] R. C. Baker and G. Harman, ‘Shifted primes without large prime factors,’ Acta Arith., 83 (1998), 331–361.

[2] R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman and I. E. Shparlinski, ‘On the statistical properties of Diffie–Hellman distributions’, Israel J. Math., 120 (2000), 23–46.

[3] R. Canetti, J. Friedlander and I. Shparlinski, ‘On certain exponential sums and the distribution of Diffie-Hellman triples’, J. London Math Soc. 59 (1999), 799–812.

[4] H. Davenport, Multiplicative Number Theory, 2nd ed., Springer-Verlag, New York 1980.

[5] P. Erdős and R. Murty, ‘On the order of a (mod p)’, Proc. 5th Canadian Number Theory Association Conf. Amer. Math. Soc., Providence, RI, 1999, 87–97.

[6] J. B. Friedlander, J. Hansen and I. E. Shparlinski, ‘On character sums with exponential functions’, Mathematika, 47 (2000), 75–85.

[7] J. B. Friedlander, S. V. Konyagin and I. E. Shparlinski, ‘Some doubly exponential sums over ℤ_{m}’, Acta Arith., (to appear).

[8] J. B. Friedlander, C. Pomerance and I. E. Shparlinski, ‘Period of the power generator and small values of Carmichael’s function’, Math. Comp., 70 (2001), 1591–1605.

[9] J. B. Friedlander and I. E. Shparlinski, ‘Double exponential sums over thin sets’, Proc. Amer. Math. Soc., 129 (2001), 1617–1621.

[10] D. R. Heath-Brown, ‘Prime numbers in short intervals and a generalized Vaughan identity’, Canad. J. Math., 34 (1982), 1365–1377.

[11] H.-K. Indlekofer and N. M. Timofeev, ‘Divisors of shifted primes’, Publ. Math. Debrecen, 60 (2002), 307–345.

[12] S. V. Konyagin and I. Shparlinski, Character sums with exponential functions and their applications, Cambridge Univ. Press, Cambridge, 1999.

[13] N. M. Korobov, ‘On the distribution of digits in periodic fractions’, Matem. Sbornik, 89 (1972), 654–670 (in Russian), English translation in Math. USSR–Sb., 18 (1972), 659–676.

[14] N. M. Korobov, Exponential sums and their applications, Kluwer Acad. Publ., Dordrecht, 1992.

[15] P. Kurlberg,‘On the order of unimodular matrices modulo integers’, Preprint, 2001, 1–12.

[16] P. Kurlberg and Z. Rudnick, ‘On quantum ergodicity for linear maps of the torus’, Comm. Math. Phys., 222 (2001), 201–227.

[17] S. Li and C. Pomerance, ‘On generalizing Artin’s conjecture on primitive roots to composite moduli,’ J. Reine Angew. Math., (to appear).

[18] M. R. Murty, M. Rosen and J. H. Silverman, ‘Variations on a theme of Romanoff’, Intern. J. Math. Soc., 7 (1996), 373–391.

[19] H. Niederreiter, ‘Quasi-Monte Carlo methods and pseudo-random numbers’, Bull. Amer. Math. Soc., 84 (1978), 957–1041.

[20] H. Niederreiter, Random number generation and Quasi–Monte Carlo methods, SIAM Press, 1992.

[21] F. Pappalardi, ‘On the order of finitely generated subgroups of ℚ^{∗} (mod p) and divisors of p − 1’, J. Number Theory, 57 (1996), 207–222.

[22] P. Shiu, ‘A Brun–Titchmarsh theorem for multiplicative functions’, J. Reine Angew. Math., 313 (1980), 161–170.

[23] R. C. Vaughan, ‘An elementary method in prime number theory’, Acta Arith., 37 (1980), 111–115.

[24] I. M. Vinogradov, The method of trigonometric sums in the theory of numbers, Interscience Publisher, 1954.