Asymptotic Formulae for Arithmetic Functions by Vishaal Kapoor B.Sc., Simon Fraser University, 2004 M.Sc., The University of British Columbia, 2006 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) April 2011 c Vishaal Kapoor 2011 Abstract In this work we will consider several questions concerning the asymptotic nature of arithmetic functions. First, we conduct a finer analysis on the behavior of λ(ϕ(n)) in relation to λ(λ(n)), proving that log(λ(ϕ(n))/λ(λ(n))) is asymptotic to (log log n)(log log log n) for almost all n. Second, we establish an asymptotic formula for sums of a generalized divisor function on the Gaussian numbers. And third, for complex-valued multiplicative functions that are sufficiently close to 1 on the primes and bounded on prime powers, we determine the average value over a short interval x < n ≤ x + w provided the interval is sufficiently long with respect to x. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Compositions of the Euler and Carmichael Functions 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 2.2 Notation and Useful Results . . . . . . . . . . . . . . . 2.3 The Proof of Theorem 4 . . . . . . . . . . . . . . . . . 2.4 Large Primes q > Y . . . . . . . . . . . . . . . . . . . 2.5 Small Primes q ≤ Y . . . . . . . . . . . . . . . . . . . 2.5.1 Normal Order of g(n) . . . . . . . . . . . . . . 2.5.2 Normal Order of h(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 8 8 12 14 16 21 24 28 3 An Asymptotic Formula . . . . . . . . . . . . . . . . . . . . . . 30 4 Short Sums of Multiplicative Functions . . . . . . . . . . . . 37 iii 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Compositions of the Euler and Carmichael Functions 5.2 An Asymptotic Formula . . . . . . . . . . . . . . . . 5.3 Short Sums of Multiplicative Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 50 51 52 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 iv List of Figures 2.1 2.2 Ways that q can Divide λλ(n) . . . . . . . . . . . . . . . . . . 17 Ways that q can Divide λϕ(n) . . . . . . . . . . . . . . . . . . 18 3.1 Keyhole Contour . . . . . . . . . . . . . . . . . . . . . . . . . 32 v Acknowledgements I am thankful for the brilliant teachers that I have had in my academic career. My supervisor, Greg Martin, has tirelessly taught me for the past 6 years, always being available to provide insight into mathematics and research. His encouragement and guidance have been most crucial to the completion of my MSc and Phd. My family has provided the solid support that has allowed me to pursue a higher education, and the continued love and laughter have made the pursuit all the more enjoyable (thanks Rosie). I would like to thank Erick Wong and Vasu Tewari for always providing interesting discussion about the curious questions of mathematics and computer trends, and Aurel Meyer for providing a great example to follow of solid work ethic. Lastly, I would like to thank Nike Vatsal, David Boyd, Michael Bennett, and Will Evans for providing valuable feedback and suggestions for improvement for this thesis; and I would like to thank Kevin Ford for suggesting the examples of Corollary 1. vi Dedication I dedicate this thesis to my family. vii Chapter 1 Introduction A central theme in multiplicative number theory involves determining the asymptotic behavior of functions of a multiplicative nature and of their sums over intervals of positive integers. The primary focus of this work is to derive asymptotic formulae for • the composition of Carmichael’s λ-function and Euler’s totient function, • a generalized divisor function on the Gaussian numbers, and • short interval sums of multiplicative functions of a certain type. A complex-valued function defined on the positive integers is called an arithmetic function. Such functions are very general, and typically one is interested in functions with more structure. If one has the additional relationship f (ab) = f (a)f (b) when a and b are relatively prime positive integers, then f (n) is called a multiplicative function. We remind the reader that a prime number is a positive integer that has exactly two positive factors (i.e. 2, 3, 5, 7, 11, . . . ), and two positive integers are said to be relatively prime if they share no common prime factors. Let f (n) and g(n) be two arithmetic functions. We say that f (n) is asymptotically equivalent to g(n) (written f (n) ∼ g(n)) if f (n)/g(n) tends to 1 as n tends to infinity; we may also express this equivalence as the asymptotic formula f (n) = (1 + o(1))g(n). Here we are using the little-oh notation f (n) = o(g(n)) which means that f (n)/g(n) tends to 0 as n tends to infinity. Occasionally, one might obtain an asymptotic equivalence f (n) ∼ 1 g(n) on a subset of the natural numbers with asymptotic density 1. In such case we say that f (n) has normal order g(n). The study of arithmetic functions is central to number theory, and it is largely through the study of these functions that one gains insight into the positive integers. In particular, the multiplicative nature of the positive integers is of great interest, and studying arithmetic functions that have a multiplicative nature such as Euler’s totient function and Carmichael’s λfunction can prove fruitful. Euler’s totient function ϕ(n) is defined as the cardinality of the multiplicative group Z/nZ, and Carmichael’s function λ(n) is defined to be the size of the largest cyclic subgroup of the multiplicative group Z/nZ. We have ϕ(n) = Y pa−1 (p − 1), pa ||n where the product is over all prime powers pa exactly dividing n. Carmichael’s λ-function satisfies the relations λ(n) = lcm(λ(pa11 ), ..., λ(pakk )), where ( λ(pa ) = pa−1 (p − 1) if p ≥ 3 or a ≤ 2, and 2a−2 if p = 2 and a ≥ 3. One notes from the definitions that ϕ(n) ≥ λ(n), as the largest cyclic subgroup can be no larger than the group itself. Additionally, one sees that the primes that divide λ(n) are exactly the same as those that divide ϕ(n), except the primes divide λ(n) with no larger multiplicity than they divide ϕ(n). We remark that for odd n, the definitions of ϕ(n) and λ(n) are of Q a parallel nature. Namely, when n is odd, ϕ(n) = pa ||n pa−1 (p − 1) while λ(n) = lcmpa ||n {pa−1 (p − 1)}; for even n, the same relation holds up to a 2 factor of 2. It is helpful to keep such a description in mind when comparing ϕ(n) and λ(n). We have mentioned that by investigating ϕ(n) and λ(n) one gains insight into the multiplicative make-up of n. We give one such example that uses the following simple observation. When comparing the product of a set to the lowest common multiple of the same set, the larger the set, the more likely the lowest common multiple will be significantly smaller than the product due to the repeated occurrence of prime power factors. Thus if n is “highly composite”, that is, if n consists of the product of many distinct prime factors, then one would expect the ratio ϕ(n)/λ(n) to be large – in this way we have a measure as to how “composite” n is. The ratio between ϕ(n) and λ(n) has been the study of [5, 8], and it has been shown that log(ϕ(n)/λ(n)) has normal order (log log n)(log log log n). As Euler’s totient function and Carmichael’s λ-function are of a fundamental nature, we will consider a similar heuristic to analyse the multiplicative structure of the functions ϕ(n) and λ(n) themselves. We have mentioned that ϕ(n) and λ(n) are defined in a parallel fashion so one would expect a strong multiplicative similarity between these two functions. To argue such a case, we look at the comparison λ(ϕ(n))/λ(λ(n)). Here we have applied λ(n) to both ϕ(n) and λ(n) in the ratio ϕ(n)/λ(n). What we find is that the logarithm log(λ(ϕ(n))/λ(λ(n))) has the same normal order as that of log(ϕ(n)/λ(n)). This is a curious result as we find that upon application of λ(n), the normal order is unchanged. We prove that Theorem 1. The normal order of log(λ(ϕ(n))/λ(λ(n))) is (log log n)(log log log n). We mention that the multiplicative nature of ϕ(n) and λ(n) has been previously studied. In [7] it is shown that the number of prime factors (counted with multiplicity) of ϕ(n) is normally the same as that of λ(n) – both have normal order (log log n)2 /2. This is significantly larger than the number of prime factors of an arbitrary positive integer n which is of normal order log log n prime factors counted with multiplicity. By counting the primes 3 with multiplicity, one may deduce that the number of divisors of ϕ(n) and λ(n) has normal order exp((log 2)(log log n)2 /2) (see [11]). These results are suggestive of the multiplicative similarity of ϕ(n) and λ(n); however, the number of divisors of an integer, and the number of prime factors of an integer are functions which have smaller ranges for a given positive integer n than Carmichael’s λ-function. Thus the assertion of Theorem 1 provides more compelling evidence of the similarity between the multiplicative makeup of ϕ(n) and λ(n). Banks, Luca, Saidak, and Stănică [1] studied the set of n for which λ(ϕ(n)) = ϕ(λ(n)) as well as the asymptotic behavior of log(n/λ(ϕ(n))). They proved that the normal order of log(n/λ(ϕ(n))) is log(n/λ(λ(n))), the latter having known normal order (log log n)2 (log log log n) due to Martin and Pomerance [16]. Theorem 1 furthers the current state of knowledge concerning the composition of λ(ϕ(n)) by comparing λ(ϕ(n)) with the closer function λ(λ(n)) rather than the distant function n, and completes the picture concerning the comparisons of the functions ϕ(ϕ(n)), ϕ(λ(n)), λ(ϕ(n)) and λ(λ(n)). Previously, the relative comparisons of each of these four functions were known with the exception of the comparison between λ(ϕ(n)) and λ(λ(n)) provided by Theorem 1. Our main innovation over the work of Banks, et al. in the analysis of λ(ϕ(n)) is the case-by-case analysis of the ways that the powers of primes can divide λ(ϕ(n)). Such an analysis requires many ingredients, the primary ingredients being the Turán-Kubilius inequality and a Brun-Titchmarsh inequality that gives upper bounds on the sum of 1/p where p ranges through an arithmetic progression. The method we use is that of [5, 8, 16]. In addition to analysing the asymptotic behavior of an arithmetic function, one may gain insight by analysing the asymptotic behavior of the sum of a function over intervals of positive integers. Such sums are revealing because a sum over many values of a function mitigates minor erratic behavior, typically resulting in well-behaved asymptotic formulae. One would be 4 hard-pressed to find a simple formula describing exactly which n are prime, but one can simply say there are asymptotically x/ log x prime numbers less than x. Estimates for sums of arithmetic functions frequently arise in number theoretic applications so additional tools to handle these sums are valuable. As an example from analytic number theory, one commonly has to estimate sums of the generalized divisor function τk (n), that is, the number of ways of expressing a positive integer n as a product of k positive integers for some positive integer k. We now move to the second topic of this work. We will study a related divisor function which we call τk0 (n) which counts the number of ways of expressing n as the product of k Gaussian numbers, that is, numbers which are the sum of two squares of integers. Our interest in this generalized divisor function has to do with an open problem concerning the distribution of Gaussian numbers in short intervals. It is currently known that for any positive real number x, the interval (x, x + 6x1/4 ) contains a Gaussian number. It was our hope to gain more information about the indicator function for the Gaussian numbers, τ0 (n), by studying the related functions τk0 (n) for higher values of k in the same way that one may study a weighted sum to gain information about the original sum. What we have proven is in accordance with Landau’s original work on the subject in 1908, where he states that the number of Gaussian numbers up to x is given by the asymptotic formula X τ00 (n) = αx(log x)−1/2 + O(x(log x)−3/2 ). n≤x Using the Selberg-Delange method, we establish an asymptotic formula for an even more general divisor function τz0 (n) on the Gaussian numbers where z is allowed to be complex. We prove 5 Theorem 2. Let x ≥ 4. Then as x → ∞ X n≤x τz0 (n) = 1 x(log x)z/2−1 + O(x(log x) x3/5 . Here ε > 0 is sufficiently small, and the implicit constant in the Vinogradov notation depends on A, θ and ε. This theorem improves on the work of Bordellès [2, 3] and is an attempt at furthering a general theory for short sums of multiplicative functions. An ideal result in this theory would be to prove that an asymptotic formula of the above type holds whenever the Euler product converged to a non-zero number. This would be analogous to the theory of long sums established by Delange and Halász (see [8]). Following a theorem of this sort, analogous results for the generalized divisor function on the Gaussian numbers would be an important step towards understanding the distribution of Gaussian numbers in short intervals. The author is currently investigating this direction of research. We will prove and provide detailed overviews of the presented theorems in the following three chapters. 7 Chapter 2 Compositions of the Euler and Carmichael Functions 2.1 Introduction Euler’s totient function ϕ(n) is defined to be the cardinality of the multiplicative group modulo n, for any positive integer n. Carmichael’s λ-function [4] denotes the cardinality of the largest cycle in the multiplicative group modulo n. In other words, λ(n) is the smallest positive integer m such that am ≡ 1 (mod n) for all reduced residues a (mod n). We notice that when the multiplicative group modulo n is cyclic, namely when n = 1, 2, 4, pa or 2pa where p is an odd prime and a ≥ 1, both ϕ(n) and λ(n) are equal. One may compute ϕ(n) with the aid of the Chinese remainder theorem by using the formula ϕ(n) = |(Z/pa11 Z)× | × · · · × |(Z/pakk Z)× | = pa11 −1 (p1 − 1) · · · pakk −1 (pk − 1). where n has the prime decomposition n = pa11 · · · pakk . For Carmichael’s function we note ( pa−1 (p − 1) if p ≥ 3 or a ≤ 2, and λ(pa ) = (2.1) 2a−2 if p = 2 and a ≥ 3, together with λ(n) = lcm(λ(pa11 ), ..., λ(pakk )). (2.2) 8 We introduce notation that we will use in this chapter. Given two functions f (n) and g(n), we will frequently drop the outer parentheses from the expression f (g(n)), instead writing the composition as f g(n). Additionally for f (n) denoting λ(n), ϕ(n) or log(n), we define f1 (n) = f (n) and fk+1 (n) = f (fk (n)) for k ≥ 1. We will use the expression “for almost all n” to mean for n in a set of positive integers of asymptotic density 1. We will use the expression “for almost all n ≤ x” to mean that the number of counterexamples up to x is of size o(x). We recall that for arithmetic functions f (n) and g(n), we say f (n) has normal order g(n) if f (n) is asymptotic to g(n) for almost all n, or equivalently if f (n) = (1 + o(1))g(n) for almost all n. The theorem that we prove in this article is: Theorem 4. The normal order of log(λϕ(n)/λλ(n)) is log2 n log3 n. More precisely, we show that for almost all n ≤ x, log λϕ(n) = log2 n log3 n + O(ψ(x) log2 x), λλ(n) (2.3) where ψ(x) is a function tending to infinity slower than log3 x. We also show that the exceptional set of positive integers n for equation (2.3) is of asymptotic density O(x/ψ(x)). There has been extensive study on the asymptotic behavior of ϕ(n) and λ(n) and their compositions. In 1928, Schoenberg [18] established that the quotient n/ϕ(n) has a continuous distribution function. In other words: Proposition 5. The limit Φ(t) = lim |{n ≤ N : n/ϕ(n) ≥ t}|/N N →∞ exists and is continuous for any real t. Recently Weingartner [20] studied the asymptotic behavior of Φ(t) showing that as t tends to infinity, log Φ(t) = − exp(te−γ )(1 + O(t−2 )), where γ = 0.5722... is Euler’s constant. 9 We mention that higher iterates of ϕ(n) have been studied by Erdős, Granville, Pomerance and Spiro in [6]. They established: Proposition 6. The normal order of ϕk (n)/ϕk+1 (n) is keγ log3 n, for k ≥ 1. In 1955 Erdős established the normal order of log(n/λ(n)) in [5]. This result was refined by Erdős, Pomerance, and Schmutz in [8] where they proved the following result. Proposition 7. For almost all n, log n = log2 n(log3 n + A + O((log3 n)−1+ε ), λ(n) where A = −1 + q = .2269688..., (q − 1)2 q prime X and ε > 0 is fixed but arbitrarily small. The author is currently undertaking the analysis of Theorem 1 to obtain a more accurate asymptotic formula of a form more closely resembling the previous proposition. Martin and Pomerance subsequently considered the question of understanding the behavior of λλ(n). In [16] they proved Proposition 8. For almost all n, log n = (1 + o(1))(log2 n)2 log3 n. λλ(n) (2.4) Based on heuristic reasoning, Martin and Pomerance have conjectured the behavior of the higher iterates of λλ(n). Conjecture. For each k ≥ 1, n log = λk (n) 1 + o(1) (log2 n)k log3 n, (k − 1)! 10 for almost all n. Banks, Luca, Saidak, and Stănică [1] studied the the compositions of λ and ϕ. In particular, they studied the set of n on which λϕ(n) = ϕλ(n). In their paper, they also established the following: Proposition 9. For almost all n, n = (1 + o(1)) log2 n log3 n, and ϕλ(n) n = (1 + o(1))(log2 n)2 log3 n. log λϕ(n) log Consequently, log (2.5) (2.6) ϕλ(n) has normal order (log2 n)2 log3 n. λϕ(n) The proof of Proposition 9 uses a simple clever argument that rests on the theorem of Martin and Pomerance. It is interesting to see what we may obtain trivially from Propositions 8 and 9. Subtracting (2.5) from (2.4) gives an asymptotic formula for the comparison between ϕλ(n) and λλ(n), log ϕλ(n) ∼ (log2 n)2 log3 n, λλ(n) for almost all n. However, if we subtract (2.6) from (2.4), the main terms cancel and we are left with log λϕ(n) = o((log2 n)2 log3 n), λλ(n) for almost all n. This relation is interesting because it leads one to seek a more accurate asymptotic formula. This more accurate result is the content of Theorem 4. 11 2.2 Notation and Useful Results Let a, n ∈ Z. Then the Brun-Titchmarsh inequality is the asymptotic relationship that π(z; n, a) z ϕ(n) log(z/n) (z > n), (2.7) where π(z; n, a) is the number of primes congruent to a (mod n) up to z. We will be primarily concerned with implications of the Brun-Titchmarsh inequality in the case that a = 1. For convenience, define Pn to be the set of primes congruent to 1 (mod n), and for a given integer m, define the greatest common divisor of m and Pn , denoted (m, Pn ), to be the product of the primes congruent to 1 (mod n) that divide m, or 1 if none exist. We will frequently use the following weaker form of (2.7) without mention. Lemma 10 (A Brun-Titchmarsh Inequality). For all z > ee , X 1 log log z . p ϕ(n) p≤z (2.8) p∈Pn One may obtain (2.8) from (2.7) by partial summation. We will also use the following prime estimates stated in [16]. Lemma 11. Let z > e. Then we have the following: X log p z, p≤z p≤z X log p p>z X log p p2 1 , and z log z, X log2 p p p≤z X 1 1 , 2 p z log z p>z p log2 z, These estimates follow via partial summation applied to Mertens’ estiP mate M (z) = p≤z (log p)/p = log z + O(1). We illustrate the derivation of 12 the first tail estimate. One writes the Riemann-Steltjies integral Z X 2 (log p)/p = p>z ∞ ∞ 1/t dM (t) = M (t)/t z + z Z = (log z)/z + O(1/z) + Z ∞ M (t)/t2 dt z ∞ (log t)/t2 + O(1/t2 ) dt z 2 1/z , as required. We remind the reader that we will be writing the composition of two arithmetic functions f (n) and g(n) as f g(n), and subscripts will be used with functions to indicate the number of times a function will be composed with itself (i.e. log2 n = log log n). The multiplicity to which a prime q divides n is denoted by νq (n). In what follows, the variables p, q, r will be reserved for primes. Throughout, we denote y = y(x) = log2 x. The function ψ(x) denotes a function tending to infinity, but slower than log y. When we use the expression “for almost all n ≤ x”, we will mean for all positive integers n ≤ x except those in an exceptional set of asymptotic density O(x/ψ(x)). We will make use of two parameters Y = Y (x) and Z = Z(x) in the course of the proof of Theorem 4 which we now define as Y = 3cy, and Z = y2, where c is the implicit constant appearing in the Brun-Titchmarsh theorem (2.7) and (2.8). 13 2.3 The Proof of Theorem 4 We intend to establish an asymptotic formula for log λϕ(n) X = (νq (λϕ(n)) − νq (λλ(n))) log q, λλ(n) q (2.9) valid for n in a set of natural density 1. We will consider the “large” q and the “small” q separately. The cut-off for this distinction is the parameter Y giving the cases q > Y and q ≤ Y , respectively. For q > Y , it will be unusual for νq (λϕ(n)) to be strictly larger than νq (λλ(n)) and so the contribution in (2.9) from large q will be negligible. We bound the sum in (2.9) by the two cases, X (νq (λϕ(n)) − νq (λλ(n))) log q ≤ X νq (λϕ(n)) log q q>Y νq (λϕ(n))≥2 q>Y X + (νq (λϕ(n)) − νq (λλ(n))) log q. q>Y νq (λϕ(n))=1 (2.10) We prove the two bounds: Proposition 12. For almost all n ≤ x, X (νq (λϕ(n)) − νq (λλ(n))) log q yψ(x), q>Y νq (λϕ(n))=1 and Proposition 13. For almost all n ≤ x, X νq (λϕ(n)) log q yψ(x). (2.11) q>Y νq (λϕ(n))≥2 14 Combining Propositions 12 and 13 gives the upper bound we seek: Proposition 14. For almost all n ≤ x, X (νq (λϕ(n)) − νq (λλ(n))) log q yψ(x). (2.12) q>Y We now consider those primes q ≤ Y. It will turn out that the main P P term comes from the quantity q≤Y νq (λϕ(n)) with the sum q≤Y νq (λλ(n)) sufficiently small. Proposition 15. For almost all n ≤ x, X νq (λλ(n)) log q yψ(x). q≤Y We are left with the final piece of establishing the asymptotic behavior P of q≤Y νq (λϕ(n)). This will involve a case-by-case analysis of the various ways that q can divide λϕ(n) with multiplicity. Two functions g(n) and h(n) arise from this analysis: g(n) = h(n) = X X q≤Y α≥1 q α+1 |ϕ(n) log q, X X q≤Y α≥1 ω((n,Qqα ))>0 log q, and Qqα = {r ≤ x : ∃p ∈ Pqα st r ∈ Pp }. P We will show that g(n) is a good approximation to q≤Y νq (λϕ(n)). To deal with g(n), we will choose a suitably close additive function to approximate g(n) and employ the Turán-Kubilius inequality to find the normal order of g(n). 15 Proposition 16. For almost all n ≤ x, g(n) = y log y + O(y). Proposition 17. For almost all n ≤ x, h(n) ψ(x)y. We will combine these propositions to show Proposition 18. X (νq (λϕ(n)) − νq (λλ(n))) log q = y log y + O(ψ(x)y). q≤Y Summing the results from Propositions 14 and 18 gives X (νq (λϕ(n)) − νq (λλ(n))) log q = y log y + O(ψ(x)y), q which proves Theorem 1. In the following two sections, we will establish all of the propositions of this section except proposition 14 which we have established. 2.4 Large Primes q > Y In this section we prove Propositions 12 and 13. In order to proceed, we must first understand the different ways in which prime powers can divide λλ(n) and λϕ(n). We assume Y ≥ 2 so all primes q under consideration are odd. From the definition λ(n) (see (2.1) and (2.2)), one sees that λλ(n) has q as a prime divisor if q 2 divides λ(n) or if n is divisible by some prime in Pq . We emphasize that these conditions are not exclusive. We may expand 16 these conditions in turn. If q 2 |λ(n), then the higher power q 3 divides n, or a prime in Pq2 divides n; while if some prime p ∈ Pq divides λ(n), then p2 |n, or (n, Pp ) > 1. We summarize these cases in the tree diagram below. q 3 |n q 2 |λ(n) ∃p ∈ Pq2 st p|n q|λλ(n) ∃p ∈ Pq st p2 |n ∃p ∈ Pq st p|λ(n) ∃p ∈ Pq st ∃r ∈ Pp , r|n Figure 2.1: Ways that q can Divide λλ(n) We proceed with a similar analysis on the ways that q can be a divisor of λϕ(n). We saw that either q 2 or some prime in Pq must divide the argument ϕ(n) of λϕ(n). If two copies of q divide ϕ(n), then their presence can come from the cube q 3 dividing n, two distinct primes dividing n with each prime in Pq contributing one factor of q, both q 2 |n and a prime p ∈ Pq dividing n, or a single prime in Pq2 dividing n. In the other case, if a prime p ∈ Pq divides ϕ(n), then p2 |n or (n, Pp ) > 1. Now we turn to the proof of Proposition 12. Proof of Proposition 12. One sees from the above analysis that q|λϕ(n) whenever q|λλ(n), so the only way (νq (λϕ(n)) − νq (λλ(n))) can be nonzero is if q|λϕ(n) and q - λλ(n). Moreover, there are only two ways that q can divide λϕ(n) but not λλ(n); namely, two distinct primes p1 , p2 ∈ Pq could divide n, 17 q 3 |n ∃p1 , p2 ∈ Pq st p1 6= p2 , p1 p2 |n q 2 |ϕ(n) q 2 |n, ∃p ∈ Pq st p|n ∃p ∈ Pq2 st p|n q|λϕ(n) ∃p ∈ Pq st p2 |n ∃p ∈ Pq st p|ϕ(n) ∃p ∈ Pq st ∃r ∈ Pp , r|n Figure 2.2: Ways that q can Divide λϕ(n) or both q 2 and a single prime p ∈ Pq could divide n. Thus 1X x n≤x X (νq (λϕ(n)) − νq (λλ(n))) log q ≤ q>Y νq (λϕ(n))=1 1XX 1X X log q log q + x q>Y p ,p ∈P x q>Y n≤x 1 2 q p∈Pq pq 2 |n p1 p2 |n n≤x 1X x q>Y xy 2 xy + 3 q2 q log q y 2 /Y, where we used Lemmata 10 and 11. Plugging in Y = 3cy the upper bound 18 is y. We deduce that for almost all n ≤ x, X (νq (λϕ(n)) − νq (λλ(n))) log q yψ(x). q>Y νq (λϕ(n))=1 Now we would like to show that X νq (λϕ(n)) log q y 2 ψ(x)/Y (2.13) q>Y νq (λϕ(n))≥2 holds normally. Proof of Proposition 13. Define Sq = Sq (x) = {n ≤ x : q 2 |n or p|n for some p ∈ Pq2 } and S = ∪q>Y Sq . A simple estimate shows that the cardinality of S is O(xy/(Y log Y )). We will choose Y to be of asymptotic order y, thus the number of elements in S is O(x/ψ(x)). As we are interested in a normality result, we may safely ignore the positive integers in S. Consequently, to establish (2.13) for almost all n, it suffices to establish the mean value estimate 1X x n≤x X νq (λϕ(n)) log q y 2 /Y. (2.14) q>Y n6∈S νq (λϕ(n))≥2 19 To this end we write 1X x n≤x X νq (λϕ(n)) log q ≤ q>Y n6∈S νq (λϕ(n))≥2 ≤ 1X x q>Y X νq (λϕ(n)) log q n≤x n6∈S νq (λϕ(n))≥2 1 XX X 2 log q x q>Y n≤x α≥2 n6∈S q α |λϕ(n) 2X X ≤ log q x q>Y n≤x α≥2 n6∈S q α |λϕ(n) 2X ≤ x q>Y X α≥2 n≤x p∈Pqα p|ϕ(n) + X log q. n≤x n6∈S q α+1 |ϕ(n) In order for the prime p to be a divisor of ϕ(n), one of: p2 divides n, or r ∈ Pp and r divides n for some prime r must occur. Thus, X n≤x p∈Pqα p|ϕ(n) 1= X X p≤x n≤x p∈Pqα p|ϕ(n) X x X x X xy X x x xy 2 1 + + + . p2 r p2 p αq α log q qα p>q α p≤x r≤x p≤x p∈Pqα r∈Pp p∈Pqα (2.15) Summing over q > Y and α ≥ 2 and weighting by log q we have the asymptotic upper bound 1X X log q y 2 /Y. x q>Y n≤x α≥2 p∈Pqα p|ϕ(n) 20 Now we would like to establish 1X x q>Y α≥2 X log q y 2 /Y. n≤x n6∈S q α+1 |ϕ(n) We note that the contribution of prime powers of q dividing ϕ(n) for n 6∈ S can only come from distinct primes in Pq dividing n. We then have X 1 n≤x n6∈S 1 (α + 1)! p X X 1 ,...,pα+1 ∈Pq p1 ···pα+1 |n≤x 1 x(cy)α+1 , (α + 1)!q α+1 (2.16) q α+1 |ϕ(n) where we intentionally omit the condition that the primes pi ∈ Pq are distinct and where c is the constant appearing in the Brun-Titchmarsh theorem. As Y ≥ 2cy we have cy/q ≤ 1/2. Thus summing the LHS of (2.16) over α ≥ 2 and q > Y and weighting by log q gives X X xcα y α q>Y α≥3 α!q α log q ≤ xc2 y 2 X 1 X log q xy 2 /Y α 2 α!2 q α≥1 q>Y (2.17) as required. 2.5 Small Primes q ≤ Y In this section we will be concerned with estimates for small primes; namely, we will prove Propositions 15, 16, 17 and 18. The main term in our asymptotic formula will come from Proposition 16 which concerns the sum X νq (λϕ(n)) log q. (2.18) q≤Y The remaining two Propositions provide us with error terms. 21 We restate a Lemma 11 from [16] which we will use: Lemma 19. For a power of a prime q a , the number of positive integers n ≤ x with q a dividing λλ(n) is O(xy 2 /q a ). Proof of Proposition 15. We break the summation up into two parts depending on the size of q α , X X νq (λλ(n)) log q = q≤Y q≤Y X q≤Y X log q 1 α≥1 q α |λλ(n) log q X α≥1 q α ≤Z 1+ X log q q≤Y X 1. α≥1 q α >Z q α |λλ(n) We may bound the first sum as X q≤Y log q X 1 Y log Z/ log Y. α≥1 q α ≤Z We use an average estimate to bound the second sum. Note X X 1 XX 1X log q 1= log q x n≤x q≤Y x q≤Y α≥1 α≥1 q α >Z q α |λλ(n) X 1. (2.19) n≤x q α >Z q α |λλ(n) From Lemma 19, we see (2.19) is X y 2 log q X xy 2 1X y2Y log q . x q≤Y qα Z Z α≥1 q≤Y q α >Z 22 Therefore X X log q 1 y 2 Y ψ(x)/Z, α≥1 q≤Y q α >Z q α |λλ(n) for almost all n ≤ x. Combining our upper bounds gives X νq (λλ(n)) log q (Y log Z/ log Y + y 2 Y /Z)ψ(x), q≤Y for almost all n ≤ x. Substituting Y = 3cy and Z = y 2 gives the theorem. Recall q α divides λϕ(n) if one of • q α+1 |ϕ(n) • q α |p − 1, p|r − 1, r|n • q α |p − 1, p2 |n occurs. Note that these conditions are not mutually exclusive. We write (2.18) as X νq (λϕ(n)) log q = g(n) + O h(n) + q≤Y X X log q , q≤Y p∈Pqα p2 |n where g(n) = X X log q, α≥1 q≤Y q α+1 |ϕ(n) h(n) = X X q≤Y α≥1 ω(n,Qqα )>0 log q, and Qqα = {r ≤ x : ∃p ∈ Pqα st r ∈ Pp }. 23 Thus, for almost all n ≤ x, X νq (λϕ(n)) log q = g(n) + O(h(n) + ψ(x) log2 Y ). (2.20) q≤Y In the next two sections, we prove Propositions 16 and 17. We see that Proposition 18 follows immediately by applying these two propositions to equation (2.20) giving X νq (λϕ(n)) log q = y log y + O(yψ(x)) q≤Y for almost all n ≤ x, as required. 2.5.1 Normal Order of g(n) Our strategy is to approximate g(n) from above and below by an additive arithmetic function, thus indirectly making g(n) amenable to the TuránKubilius inequality. To start, write g(n) as g(n) = = X X q≤Y α≥1 q α+1 |ϕ(n) X (νq (ϕ(n)) − 1) log q log q q≤Y = XX νq (p − 1) log q − Y (1 + o(1)) + O X νq (n) log q , (2.21) q≤Y q≤Y p|n where we used the double inequality X p|n νq (p − 1) ≤ νq (ϕ(n)) ≤ X νq (p − 1) + νq (n). p|n We will use the Turán-Kubilius inequality: 24 Lemma 20 (The Turán-Kubilius Inequality). There exists an absolute constant C such that for all additive functions f (n) and all x ≥ 1 the inequality X |f (n) − A(x)|2 ≤ CxB(x)2 (2.22) n≤x holds where A(x) = X f (p)/p, and p≤x X 2 B(x) = |f (pk )|2 /pk . pk ≤x Proof of Proposition 16. We will use Lemma 20 for the additive function P P g0 (n) = q≤Y p|n νq (p − 1) log q. Let A(x) and B(x) be the first and second moments: A(x) = X g0 (r)/r, and r≤x B(x) = X g0 (rk )2 /rk . rk ≤x Notice that g0 (rk ) = g0 (r) = A(x) = X 1 XX r≤x r P q≤Y νq (r − 1) log q leading to νq (p − 1) log q = q≤Y p|r X log q r≤x q≤Y = X X νq (r − 1) log q q≤Y r X X 1 . r α≥1 r≤x r∈Pqα We split the sum over α into X 1≤α≤wq X 1 X X 1 + , r r α>w r≤x r≤x q r∈Pqα r∈Pqα 25 with wq to be determined later. The first we estimate with Page’s theorem and the second we bound with the Brun-Titchmarsh bound X 1/r y/ϕ(d). r≤x r≡1 (mod d) ∞ X α=1 y yq y y + O wq + wq = + O wq + wq ϕ(q α ) q (q − 1)2 q (2.23) Note that we used the bound 1/q bwq c+1 = O(1/q wq ). Taking wq = log y/ log q gives an error term of O(wq ) = O(log y/ log q). Summing (2.23) over q ≤ Y weighted by log q gives the asymptotic formula X q log q Y log y A(x) = y +O +Y 2 (q − 1) log Y q≤Y Y log y = y log Y + O +Y . log Y (2.24) Expanding the square, write the second moment B(x) as B(x) = X log q1 log q2 q1 ,q2 ≤Y Uniformly in primes r, (i = 1, 2) as X νq1 (r − 1)νq2 (r − 1) r≤x P k≥1 X 1/rk . k≤1 rk ≤x 1/rk 1/r. We may also express νqi (r − 1) νqi (r − 1) = X 1, αi ≥1 r∈Pqαi i 26 giving the expanded B(x) X X X α1 ,α2 ≥1 r≤x r∈Pqα1 ∩Pqα2 log q1 log q2 q1 ,q2 ≤Y 1 1 . r 2 We split the sum in q1 , q2 into the two cases: q1 = q2 and q1 6= q2 . For the q1 , q2 with q = q1 = q2 we have X (log q)2 q≤Y X X X α 1 X = (log q)2 r q≤Y r α≥1 r≤x X α1 ,α2 ≥1 r≤x r∈P r∈Pqα q max(α1 ,α2 ) X (log q)2 α≥1 q≤Y y X αy qα X (log q)2 q≤Y q y(log Y )2 . (2.25) If q1 and q2 are distinct then we have an upper bound (intentionally ignoring the condition that q1 6= q2 in the sum) X q1 ,q2 ≤Y log q1 log q2 X X α1 ,α2 ≥1 r≤x r∈Pqα1 qα2 1 X X y 1 log q1 log q2 α1 α2 r q q α ,α ≥1 1 2 q ,q ≤Y 1 1 2 2 2 y X log q1 log q2 q1 q 2 q ,q ≤Y 1 2 y(log Y )2 . (2.26) Combining (2.25) and (2.26) gives B(x) y(log Y )2 . (2.27) Using Lemma 20 we may conclude that The statement of Lemma 20 gives 27 us the equation X |g0 (n) − A(x)|2 ≤ CxB(x)2 . (2.28) n≤x Thus the set of n ≤ x on which g0 (n) differs from A(x) by more than y is O(x(log Y )2 /y) = O(x/ψ(x)). P P The mean value of q≤Y νq (n) log q for n ≤ x is 1/x q≤Y x log q/q P P 2 q≤Y log q/q ∼ log Y, so q≤Y νq (n) log q log Y for almost all n ≤ x. Thus from (2.21), we see that for almost all n ≤ x, Y log y +Y , g(n) = y log Y + O log Y (2.29) Substituting Y = 3cy gives the theorem. 2.5.2 Normal Order of h(n) Proof of Proposition 17. In order to find an upper bound on a set of asymptotic density 1, we will compute the first moment of h(n): H(x) := 1X 1X h(n) = x n≤x x q≤Y X log q n≤x α≥1 ω(n,Qqα )>0 = 1 X x qα ≤Z X log q + n≤x q≤Y ω(n,Qqα )>0 α≥1 1 X x qα >Z X log q. n≤x q≤Y ω(n,Qqα )>0 α≥1 We deal with the two sums in turn. Small q α 1 X x qα ≤Z The first part is for small powers of q: X n≤x q≤Y ω(n,Qqα )>0 log q ≤ X X Y log Z 1 X log q 1≤ log q = . x qα ≤Z log Y α n≤x q ≤Z q≤Y (2.30) q≤Y 28 Large q α The second part is for large powers of q. In this case we use a crude estimate that is sufficient for our needs: 1 X x qα >Z X log q n≤x q≤Y ω(n,Qqα )>0 X X 1 X log q 1 x qα >Z r∈Q α n≤x q q≤Y r|n X x 1 X log q x qα >Z r r∈Q α q q≤Y X log q q α >Z q≤Y y2 X X1 r p∈P α r∈P q X log q . α q α q >Z p (2.31) q≤Y P P α ≤ The sum in the RHS of (2.31) is less than q≤Y α>log Z/ log q log q/q P P 2 q≤Y log q/q log Z/ log q Y /Z, or alternatively q α ≥ Z and q≤Y log q ∼ Y . Thus 1 X x qα >Z X log q = O(y 2 Y /Z). (2.32) n≤x q≤Y ω(n,Qqα )>0 Summing (2.30) and (2.32) gives H(x) Y log Z/ log Y + y 2 Y /Z y, where we substituted the values of Y and Z. Thus, for almost all n ≤ x, h(n) yψ(x). 29 Chapter 3 An Asymptotic Formula for a Divisor Function on the Gaussian Numbers A natural number is a Gaussian number if it can be written as the sum of two squares of integers. We let S denote the set of Gaussian numbers and define S(x) to be the number of Gaussian numbers ≤ x. In 1908, Landau proved that S(x) = αx(log x)−1/2 + O(x(log x)−3/2 ) where α is the constant1 Q 2−1/2 p≡3 (mod 4) (1 − p−2 )−1/2 . Under the Riemann hypotheses for ζ(s) and L(s, χ4 ) where χ4 is the non-principal character modulo 4, one can reduce the error term in Landau’s problem to O(x1/2 (log x)2 ). Gediri [12] noted that though one can use the Riemann hypotheses to obtain a smaller power in the error term of Landau’s problem, one can obtain an unconditional asymptotic formula for the summatory function of the number of Gaussian divisors with a small error term. Define the counting function for the number of Gaussian divisors, τ 0 (n) = P Σ0n=ab 1, and its relatives τk0 (n) = s1 s2 ...sk =n 1 for any positive integer k. Here both of the sums are over indices restricted to lie in S and τ 0 (n) := P 0 0 τ20 (n). Gediri proves for positive integers k that D2k (n) := n≤x τ2k (n) = 1−c0 /k2/3 xPk (log x) + O(x ), where Pk (x) is a polynomial of degree k − 1 and 0 c is an effective absolute constant. We will prove an analogous asymptotic formula for k any complex number, generalizing the definition of τk0 (n) appropriately. First, we must define what we mean by τk0 (n) for k ∈ C. 1 p is a prime unless otherwise specified. 30 P −s Let F (s) = be the Dirichlet function corresponding to the n∈S n sequence of Gaussian numbers. Then for a complex number z ∈ C the generalized Gaussian divisor function τz0 (n) is defined by the relation z F (s) = ∞ X τ 0 (n) z n=1 ns (~~ 1), where wz := exp(z log w). Unless otherwise specified, we will choose the logarithm to be real on the positive real axis. We prove the following theorem. Theorem 21. Let x ≥ 4. Then as x → ∞ X n≤x τz0 (n) = 1 x(log x)z/2−1 + O(x(log x) 1. One sees that F (s)2 = ζ(s)L(s, χ4 )Φ(s) where χ4 is the nonQ principal character modulo 4, and Φ(s) = (1−2−s )−1 p≡3 (mod 4) (1−p−2s )−1 . 31 Therefore, z F (s) = 1 1− s 2 −z/2 Y p≡1 (mod 4) z/2 z/2 = ζ(s) L(s, χ4 ) ∞ X τz0 (n) = . ns n=1 −z/2 1 1− s p Y p≡3 (mod 4) −z/2 1 1 − 2s p z/2 Φ(s) t iT 0 1 Σ -iT Figure 3.1: Keyhole Contour 32 Recall the function log+ y defined to be log y for y ≥ e and 1 otherwise. In this chapter, we will drop the superscript and simply refer to log y. Write s = σ+it where σ, t ∈ R, define σ(t) = 1−c/ log |t|, and take c > 0 sufficiently small so that ζ(s) and L(s, χ4 ) are non-zero in the region {s : σ > σ(t)}. √ Define κ = 1 + 1/ log x, T = exp( log x). Perron’s inversion formula [17, pp. 139-140] says that X τz0 (n) Z κ+iT − zx F (s) κ−iT n≤x s s ds X |τz0 (n)| min x/2 0 one defines a Hankel contour H to be a contour formed from the path (−∞, −r] followed by the circle |s| = r (excluding s = −r) traced out counter-clockwise, followed by the path (−∞, −r], where we traverse (−∞, −r] twice, the first time with argument −π and 35 the second with argument π. Though we do not use this fact, one has R 1/Γ(w) = (2πi)−1 H w−z ew dw for any complex w. For a proof see [19, pg 183]. If instead of (−∞, r] we were to use the paths (−X, −r] traced out twice, we have what is called a truncated Hankel contour denoted by H(X). In other words, H(X) would consist of all the points on a Hankel contour with real part > −X. We have the following result (see [19, pg. 184]). Lemma 22. Let X > 1. Then uniformly for w ∈ C, Z 1 2πi w−z ew dw = H(X) 1 + O(47|z| Γ(1 + |z|)e−X/2 ). Γ(z) In the main term in (3.5) make the change of variables w = (s − 1) log x. This transforms the contour integral into x(log x)z/2−1 2πi Z H(c log x) w−z/2 ew dw = 1 x(log x)z/2−1 + O(x1−c (log x)z/2−1 ), Γ(z/2) (3.7) with implicit constant depending on z by the Lemma. Adding (3.7) to the error term (3.6) gives Theorem 21 since the remaining error terms are O(x/(log x)R+2 ). 36 Chapter 4 Short Sums of Multiplicative Functions The literature is rich with asymptotic formulae for the sum of a multiplicative function over long intervals n ≤ x. In contrast, little is known about multiplicative functions summed over short intervals x < n ≤ x + y except in special circumstances. In 2002, Bordellès showed that under the hypothesis that f (n) is a real-valued multiplicative function taking values in [0, 1] and assuming the value 1 on primes, f (n) has average value tending to Y 1 f (p) f (p2 ) Cf = 1− + 2 + ... 1+ p p p p on the short interval provided y ≥ x1/5+ε for some ε > 0. In this article, we extend Bordellès theorem to a larger class of functions, lifting the requirement that f (n) be real-valued and weakening the hypothesis on the values of f (n) on the primes. More specifically, we allow any complex-valued multiplicative function that is uniformly bounded on the prime powers and “close” to 1 on the primes. Theorem 23. Let A and θ be positive constants with θ ≥ 4/5. Define FA,θ to be the class of complex-valued multiplicative functions f (n) which are bounded by A on prime powers and satisfy the inequality |f (p) − 1| ≤ Ap−θ , 37 for all primes p. For any f ∈ FA,θ if θ ≥ 4/5, then X f (n) = wCf + O(∆(x, w, ε)) (4.1) x x3/5 . Here ε > 0 is sufficiently small, and the implicit constant in the Vinogradov notation depends on A, θ and ε. When w ≤ x3/5 , the three expressions x1/5+ε , x1/15+ε w2/3 , and x−1/10+ε w dominate the error term in the ranges w ≤ x1/5 , x1/5 < w ≤ x1/2 , and w > x1/2 respectively. In particular this theorem is nontrivial when w ≥ x1/5+ε . We note that the range of θ can be enlarged to θ > 1/2. However, in the range 1/2 < θ < 4/5 the error term depends heavily on the choice of θ, so we omit the details and refer the reader to the comments following the proof of Theorem 23. For an application of Theorem 23, we find asymptotic formulae for short sums of the functions n/ϕ(n) and σ(n)/n over squarefree positive integers n. Both of these sums involve functions that are not identically 1 on the set of primes and that have values outside [0, 1] and thus can not be handled using Bordellès theorem. Applying Theorem 23 with θ = 1 gives the short interval asymptotic formulae: Corollary 1. For 1 ≤ w ≤ x we have both X x 0. Both of these formulae are nontrivial when w > x1/5+ε . In what follows, we will not state the implicit dependence on A, θ, or ε in the Vinogradov and big-Oh notations. We use the notation bac to denote the largest integer ≤ a. The Dirichlet convolution of two arithmetic functions f and g is defined as (f ∗ g)(n) = X f (a)g(b), ab=n where a, b range over positive integers. Recall a squarefree number is a natural number not divisible by the square of any prime, and a squarefull number is a natural number with every prime factor appearing with multiplicity at least 2. We outline our strategy to prove Theorem 23. We begin by establishing two simple lemmata, and stating the more technical Lemma 26; this is followed by the proof of Theorem 23. We will require two results to prove Lemma 26 - we then state these results and prove the lemma. Lemma 24. Let ε > 0. For z ≥ 1 we have X mε z 1/2+ε (4.2) 1 1 1/2−ε 1−ε m z (4.3) m≤z m squarefull and we have X m>z m squarefull 39 if ε < 1/2. Proof. We prove the second result - the proof of the first is analogous. Let S(t) be the number of squarefull numbers ≤ t. Using integration by parts on the Riemann-Steltjies integral, X m>z m squarefull 1 = m1−ε Z z ∞ 1 t1−ε S(t) dS(t) 1−ε t Golomb has shown that S(t) required. √ ∞ Z + z z ∞ S(t) dt. t2−ε (4.4) t (see [13]), so (4.4) is z −1/2+ε as Lemma 25. Suppose f ∈ FA,θ for some A > 0, and θ ≥ 1/2+ε where ε > 0. Let g = f ∗ µ. Then for y ≥ 1 we have X |g(d)| y 1/2+ε d≤y and we have X g(d) d>y d y ε−1/2 when ε < 1/2. Proof. On primes p, |g(p)| ≤ A/pθ and on higher prime powers |g(pk )| ≤ 2A. Thus for squarefree n, one has g(n) nε−θ (4.5) following from the well-known upper bound Aω(n) A,ε nε . For arbitrary n, we have g(n) nε . We use (4.5) and (4.6) to find upper bounds on the sums (4.6) P d≤y |g(d)| and 40 P g(d)/d. One can uniquely parameterize d ≤ y as the product of relatively prime m and n, with m squarefull, and n squarefree. Thus, d>y X |g(d)| = X X |g(n)| n≤y n squarefree d≤y nm≤y (m,n)=1 m squarefull 1 X n≤y n squarefree |g(m)| X nθ−ε mε . m≤y/n m squarefull By (4.2) this is 1/2+ε X 1 y 1/2+ε y 1/2+ε = y θ+1/2 nθ−ε n n n 1 X n≤y n squarefree since θ > 1/2. This establishes the first estimate. The deal with the second estimate, we write X g(d) d>y d n g(n) n squarefree X = X n squarefree X nm>y (m,n)=1 m squarefull 1 nθ+1−ε g(m) m X m≥y/n m squarefull 1 . m1−ε 41 By (4.3) this is 1/2−ε n θ+1−ε n y squarefree X 1 1 X n y ε−1/2 n nθ+1/2 θ y ε−1/2 , (4.7) when ε < 1/2. The inner sum converges because θ > 1/2. Lemma 26. There exists a sufficiently small positive constant c0 such that if Y ≤ c0 X 1/2 and X ≥ 1/2, then X Y 0. Lemma 26 is based on lattice point estimates of Huxley and Sargos (see [14, 15]), and Filaseta and Trifonov [10, Theorem 7]; we summarize these results in Lemma 28. Lemma 26 is essentially proved by Bordellès over the two papers [2, 3]. For the convenience of the reader, we will collect the details of the proof following the proof of Theorem 23. Now, we are ready to prove Theorem 23. Like Bordellès, we express f (n) as the Dirichlet convolution of the identity function and a second function, g(n), which is small in magnitude in lieu of the hypotheses imposed on f (n). However, because we have relaxed the conditions on f (n) at primes, we are left with more technical estimates on g(n). Further, we will consider short intervals of length ≤ x, where Bordellès considers intervals of length x1/2 . In this wider consideration, we will use the estimate of Filaseta and Trifonov (4.18) in as large a range as possible, and use the estimates of Huxley and Sargos (4.17) otherwise. 42 Proof of Theorem 23. Let g = f ∗ µ and 1 ≤ y ≤ x. Write X f (n) = xy (4.9) d≤y Applying Lemma 25 to the error terms and expressing the infinite sum as an Euler product gives Σ1 = yCf + O(y 1/2+ε ), (4.10) Q where Cf = p (1 − 1/p)(1 + f (p)/p + f (p2 )/p2 + ...). Now we consider Σ2 : |Σ2 | ≤ X |g(n)| n squarefree n≤2x X n≤2x X 1 nθ−ε y/nu k≤u Applying the estimates of Lemma 25 gives X f (n) = u n≤u ∞ X g(k) k=1 k + O(u1/2+ε ) = uCf + O(u1/2+ε ). Applying this result for u = x + w and u = x and subtracting gives X f (n) = wCf + O(x1/2+ε ), x≤n≤x+w 45 as required. In Theorem 23, although one requires θ ≥ 4/5 for the bound on Σ2 in Equation (4.11), we remark that some mileage may be obtained in the range 1/2 < θ < 4/5. In this range of θ, one may sum the series involving n up to x to obtain the upper bound Σ2 x3ε Eθ0 (x, y) + x2ε E(x, y), (4.14) where Eθ0 (X, Y ) = X 1/3−θ Y 2/3 + X 11/15−θ Y 4/15 + X 1−θ + X 5/6−θ Y 1/6 . P Here we have used the bound n≤u 1/na 1 + u1+ε−a valid for a > 0 and including a uε to bound log u in the case a = 1. One may then proceed similarly as in the proof of Theorem 23, again using standard convolution arguments applied to the long sums when appropriate. We omit the details as they depend on the choice of θ. The proof of Lemma 26 requires the following: Lemma 27. For 1 ≤ y ≤ x, and r a positive integer, one has X T (x, y; r) := x 0. We 46 define R(ϕ, N, δ) = |{n ∈ Z : N < n ≤ 2N and ∃m ∈ Z st |ϕ(n) − m| ≤ δ}|. Then for a function γ(n) > 0 with δ = δ(N ) = maxN 0. If there exists λk = λk (N ) such that |ϕ(k) (x)| λk when N < x ≤ 2N , then 2/k(k+1) R(ϕ, N, δ) N λk 1/k + N δ 2/k(k−1) + (δλ−1 + 1. k ) (4.17) There exists a sufficiently small positive constant c0 = c0 (k) such that if N k−1 δ ≤ c0 and N ≤ x1/k , then R(x/nk , N, δ) k x1/(2k+1) + x1/(6k+3) δN (6k 2 +k−1)/(6k+3) . (4.18) Proof of Lemma 26. We sketch the proof from “On Short Sums of Certain Multiplicative Functions” and “Corrigendum to On Short Sums of Certain Multiplicative Functions.” The sum over squarefull m in (4.8) can be parameterized in terms of a, b writing m = a2 b3 with b squarefree. Since m > Y , one of a and b is greater 47 than Y 1/5 . Thus X X + Y X − m m Y ~~