"Science, Faculty of"@en . "Mathematics, Department of"@en . "DSpace"@en . "UBCV"@en . "Harland, Nicholas"@en . "2012-10-26T17:15:10Z"@en . "2012"@en . "Doctor of Philosophy - PhD"@en . "University of British Columbia"@en . "The arithmetic function \u00CE\u00BB(n) is the exponent of the cyclic group (Z/nZ)^x. The k-th iterate of \u00CE\u00BB(n) is denoted by \u00CE\u00BBk(n) In this work we will show the normal order for log(n/\u00CE\u00BBk(n)) is (loglog n)k\u00E2\u0081\u00BB\u00C2\u00B9}(logloglog n)/(k-1)! . Second, we establish a similar normal order for other iterate involving a combination of \u00CE\u00BB(n) and \u00CE\u00A6(n). Lastly, define L(n) to be the smallest k such that \u00CE\u00BB_k(n)=1. We determine new upper and lower bounds for L(n) and conjecture a normal order."@en . "https://circle.library.ubc.ca/rest/handle/2429/43537?expand=metadata"@en . "The Iterated Carmichael Lambda Function by Nicholas Harland B.Sc., The University of Manitoba, 2003 M.Math., The University of Waterloo, 2004 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) October 2012 c\u00C2\u00A9 Nicholas Harland 2012 Abstract The arithmetic function \u00CE\u00BB(n) is the exponent of the cyclic group (Z/nZ)\u00C3\u0097. The kth iterate of \u00CE\u00BB(n) is denoted by \u00CE\u00BBk(n). In this work we will show the normal order for log(n/\u00CE\u00BBk(n)) is (log logn) k\u00E2\u0088\u00921 log log log n/(k\u00E2\u0088\u0092 1)!. Second, we establish a similar normal order for other iterate involving a combination of \u00CE\u00BB and \u00CF\u0086. Lastly, define L(n) to be the smallest k such that \u00CE\u00BBk(n) = 1. We determine new upper and lower bounds for L(n) and conjecture a normal order. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 History and Results . . . . . . . . . . . . . . . . . . . . . . . 1 2 Notation and Required Estimates . . . . . . . . . . . . . . . 7 2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Required Estimates . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Early Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Iterated Carmichael Lambda Function . . . . . . . . . . . . 17 3.1 Required Propositions and Proof of Theorem 1.4 . . . . . . . 17 3.2 Prime Power Divisors of \u00CF\u0086k(n) . . . . . . . . . . . . . . . . . 20 3.3 Large Primes Dividing \u00CF\u0086k(n) . . . . . . . . . . . . . . . . . . 23 3.4 Small Primes Dividing \u00CE\u00BBk(n) . . . . . . . . . . . . . . . . . . 27 3.5 Reduction to hk(n) for Small Primes . . . . . . . . . . . . . 28 3.6 Reduction to the First and Second Moments . . . . . . . . . 32 3.7 Summations Involving pi(t, p, 1) . . . . . . . . . . . . . . . . . 33 3.8 Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk . . . . . . . . . . 41 3.9 Evaluation of the Main Term . . . . . . . . . . . . . . . . . . 47 3.10 The Proof of the First Moment . . . . . . . . . . . . . . . . . 51 3.11 The Proof of the Second Moment . . . . . . . . . . . . . . . 52 4 Iterates Between \u00CF\u0086 and \u00CE\u00BB . . . . . . . . . . . . . . . . . . . . . 57 iii Table of Contents 5 Bounds on L(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.1 Lower Bound for L(n) . . . . . . . . . . . . . . . . . . . . . . 60 5.2 Upper Bound for L(n) . . . . . . . . . . . . . . . . . . . . . . 62 5.3 Conjecture for the Normal Order of L(n). . . . . . . . . . . . 66 6 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Appendices A The Turan\u00E2\u0080\u0093Kubilius Inequality . . . . . . . . . . . . . . . . . 73 iv List of Figures 1.1 The Pratt tree for the prime 3691 . . . . . . . . . . . . . . . . 4 v Acknowledgements I would like to thank my dedicated teachers throughout my academic ca- reer. I would like to thank my supervisor Greg Martin, who has helped me significantly throughout my Ph.D. Without his guidance I would never have been able to attain my mathematical achievements. Specifically his help with techniques to estimate summations was invaluable to this work. His advice in general has been, and will continue to be, helpful as I continue my academic career. I would also like to thank Greg Martin and Nike Vatsal for their financial support over the last 3 years. I would also like to acknowledge Mike Bennett. Not only has he been an outstanding instructor, but his advice involving research and presentation has and will assist me in my career. Finally I would like to acknowledge my fellow students and postdocs for helpful conversations. Notably Carmen Bruni, Jay Heumann, Erick Wong, Kevin Doerkson, Vishaal Kapoor and Paul Pollack. Specifically I would like to thank Paul for his helpful suggestion in the proof of Lemma 2.4. vi Dedication I would like to dedicate my thesis to my wife Jamie. Her support over the last 3 years has been wonderful. I also dedicate my thesis to my son Miles. Finally to my parents and family for always encouraging me and helping me any way they could. vii Chapter 1 Introduction 1.1 History and Results The Carmichael lambda function \u00CE\u00BB(n), first introduced by Carmichael [5], is defined to be the order of the largest cyclic subgroup of the multiplicative group (Z/nZ)\u00C3\u0097, that is, the smallest postive integer m such that am \u00E2\u0089\u00A1 1 (mod n) for all integers a which are coprime to n. It can be computed at odd prime powers to be the same as \u00CF\u0086(pk) = pk\u00E2\u0088\u00921(p \u00E2\u0088\u0092 1). As for even prime powers, \u00CE\u00BB(2) = 1, \u00CE\u00BB(4) = 2, and \u00CE\u00BB(2k) = \u00CF\u0086(2k)/2 = 2k\u00E2\u0088\u00922 for k \u00E2\u0089\u00A5 3. By the Chinese Remainder Theorem, if (a, b) = 1, then \u00CE\u00BB(ab) = lcm{\u00CE\u00BB(a), \u00CE\u00BB(b)}, which allows the calculation of the function for all positive integers. In addition to being an interesting arithmetic function to study, the Carmichael lambda function has a connection with some primality testing algorithms [1], [15]. In [1], the authors create a prime testing algorithm. It is shown that the running time of the algorithm is connected to finding an upper bound of \u00CE\u00BB(N) for specially created numbers N. In [15], the primality test involves looking at Carmichael numbers. That is numbers which satisfy an\u00E2\u0088\u00921 \u00E2\u0089\u00A1 1 (mod n) for all (a, n) = 1. It is well known that composite numbers satisfy this conguence if and only if \u00CE\u00BB(n) divdes n\u00E2\u0088\u0092 1. Miller uses this idea to help create his algorithm to test primes. Several properties of \u00CE\u00BB(n) were studied by Erdo\u00CC\u008Bs, Pomerance, and Schmutz in [9]. One of those results is the following. For an explicitly defined constant A, \u00CE\u00BB(n) = n exp (\u00E2\u0088\u0092 (log log n)(log log log n+A+O((log log log n)\u00E2\u0088\u00921+\u000F)) (1.1) as n\u00E2\u0086\u0092\u00E2\u0088\u009E for almost all n. Martin and Pomerance showed in [16] that \u00CE\u00BB(\u00CE\u00BB(n)) = n exp ( \u00E2\u0088\u0092 (1 + o(1))(log log n)2 log log log n ) (1.2) as n\u00E2\u0086\u0092\u00E2\u0088\u009E for almost all n. 1 1.1. History and Results Applications of this function included the power generator of pseudoran- dom numbers un \u00E2\u0089\u00A1 uen\u00E2\u0088\u00921 (mod m), 0 \u00E2\u0089\u00A4 un \u00E2\u0089\u00A4 m\u00E2\u0088\u0092 1, n = 1, 2, . . . . This generator has lots of cryptographic applications (see [11]), and se- quences of large period given by \u00CE\u00BB(\u00CE\u00BB(m)) are quite important. In [16], the authors provided lower bounds on the number of cycles of the power gener- ator for almost all m by relating that number to \u00CE\u00BB(\u00CE\u00BB(m)) and then use their estimate. This thesis studies the asymptotic properties of the following two func- tions. Definition 1.1. The k\u00E2\u0080\u0093fold iterated Carmichael lambda function is defined recursively to be \u00CE\u00BB0(n) = n, \u00CE\u00BBk(n) = \u00CE\u00BB(\u00CE\u00BBk\u00E2\u0088\u00921(n)) for k \u00E2\u0089\u00A5 1. We define \u00CF\u0086k(n) similarly. Next we study a related function. Definition 1.2. For a positive integer n, let L(n) denote the smallest k such that \u00CE\u00BBk(n) = 1. Throughout this work we are interested in finding normal orders for the preceding arithmetic functions. Next we define the meaning of normal order. Definition 1.3. Let f(n) be an arithmetic function. We say f(n) has normal order g(n) if for all \u000F > 0, (1\u00E2\u0088\u0092 \u000F)g(n) < f(n) < (1 + \u000F)g(n) (1.3) for almost all n. By \u00E2\u0080\u009Cfor almost all n\u00E2\u0080\u009D we mean the proportion of n \u00E2\u0089\u00A4 x for which (1.3) does not hold goes to 0 as n\u00E2\u0086\u0092\u00E2\u0088\u009E. In [16] it is conjectured that \u00CE\u00BBk(n) = n exp ( \u00E2\u0088\u0092 1 (k \u00E2\u0088\u0092 1)!(1 + ok(1))(log log n) k log log log n ) for almost all n. Our first result is the proof of that conjecture. Theorem 1.4. For fixed positive integer k, the normal order of log n\u00CE\u00BBk(n) is 1 (k\u00E2\u0088\u00921)!(log log n) k log log log n. 2 1.1. History and Results Note that Theorem 1.4 has been proved for k = 1 in [9]. Therefore from now on we will assume that k 6= 1. We\u00E2\u0080\u0099ll prove the theorem in Chapter 3 in the following slightly stronger form. Let \u00CF\u0088(x) be a function which satisifes the following two properties. 1. \u00CF\u0088(x) = o(log log log x) and 2. \u00CF\u0088(x)\u00E2\u0086\u0092\u00E2\u0088\u009E as x\u00E2\u0086\u0092\u00E2\u0088\u009E. We will show log ( n \u00CE\u00BBk(n) ) = 1 (k \u00E2\u0088\u0092 1)!(log log n) k ( log log log n+Ok ( \u00CF\u0088(n) )) for all but O(x/\u00CF\u0088(x)) integers up to x. The proof of Theorem 1.4 involves breaking down n/\u00CE\u00BBk(n) in terms of the iterated Euler \u00CF\u0086 function by using n \u00CE\u00BBk(n) = ( n \u00CF\u0086(n) )( \u00CF\u0086(n) \u00CF\u00862(n) ) . . . ( \u00CF\u0086k\u00E2\u0088\u00921(n) \u00CF\u0086k(n) )( \u00CF\u0086k(n) \u00CE\u00BBk(n) ) . (1.4) Estimates for all but the last term are known. Hence log(n/\u00CE\u00BBk(n)) can be written as a sum of the logarithms on the right side of (1.4). It will be necessary to analyze the term log(\u00CF\u0086k(n)/\u00CE\u00BBk(n)). Our second result is an asymptotic formula involving iterates involving \u00CE\u00BB and \u00CF\u0086. Banks, Luca, Saidak and Sta\u00CC\u0086nica\u00CC\u0086 in [4] showed that for almost all n, \u00CE\u00BB(\u00CF\u0086(n)) = n exp(\u00E2\u0088\u0092(1 + o(1))(log log n)2 log log log n) and \u00CF\u0086(\u00CE\u00BB(n)) = n exp(\u00E2\u0088\u0092(1 + o(1))(log log n) log log log n). As a corollary to Theorem 1.4 we will obtain asymptotic formulas for higher iterates involving \u00CE\u00BB and \u00CF\u0086. Specifically we prove the following. Theorem 1.5. For l \u00E2\u0089\u00A5 0 and k \u00E2\u0089\u00A5 1, let g(n) = \u00CF\u0086l(\u00CE\u00BB(f(n))), where f(n) is a (k\u00E2\u0088\u0092 1) iterated arithmetic function consisting of iterates of \u00CF\u0086 and \u00CE\u00BB. The normal order of log(n/g(n)) is 1(k\u00E2\u0088\u00921)!(log log n) k log log log n. An example of the use of this theorem is for \u00CF\u0086\u00CF\u0086\u00CE\u00BB\u00CF\u0086\u00CF\u0086\u00CE\u00BB\u00CE\u00BB\u00CF\u0086(n). Since l = 2, k = 5, we get that the normal order of log n\u00CF\u0086\u00CF\u0086\u00CE\u00BB\u00CF\u0086\u00CF\u0086\u00CE\u00BB\u00CE\u00BB\u00CF\u0086(n) is 1 24 (log log n)5 log log log n. 3 1.1. History and Results 3691 2 3 2 5 2 41 2 5 2 Figure 1.1: The Pratt tree for the prime 3691 A result by Erdo\u00CC\u008Bs, Granville, Pomerance and Spiro in [8] established that n/\u00CF\u0086k(n) does not have a normal order. That result combined with Theorem 1.5 completes the picture of how all iterates of \u00CE\u00BB and \u00CF\u0086 relate to n. However it doesn\u00E2\u0080\u0099t show how they relate to each other. For example log n\u00CE\u00BB\u00CF\u0086\u00CF\u0086\u00CE\u00BB\u00CE\u00BB\u00CF\u0086(n) \u00E2\u0088\u00BC log n\u00CE\u00BB6(n) for almost all n, but is there a normal order for log \u00CE\u00BB\u00CF\u0086\u00CF\u0086\u00CE\u00BB\u00CE\u00BB\u00CF\u0086(n)\u00CE\u00BB6(n) ? Kapoor [14] found results for k = 2, but the problem remains open for higher iterates. We then turn our attention to L(n). In order to study this function, we use the Pratt tree for a prime p which is defined as follows. The root node is p. Below p are nodes labelled with the primes q such that q | p \u00E2\u0088\u0092 1. The nodes below q are primes dividing q\u00E2\u0088\u0092 1 and so on until we are left with just 2. For example, if we want to take the prime 3691, the primes dividing 3690 are 2, 3, 5 and 41. Then we take the primes dividing one less than each of these and obtain the tree in Figure 1.1. In 1975, Pratt [19] introduced these trees to show that every prime has a short certificate (proof of primality). The Pratt tree is of interest to us because the way the primes go down a branch of the tree is similar to how those same primes divide iterates of \u00CE\u00BB(n). The height of the Pratt tree H(p) is the length of the longest branch. That height is related to L(n). Since \u00CE\u00BB(n) is either even or 1, and \u00CE\u00BB(n) \u00E2\u0089\u00A4 n/2 for even n, we easily see that L(n) \u00E2\u0089\u00A4 blog n/ log 2 + 1c. By considering when n is a power of 3 we can note that L(n) \u00E2\u0089\u00A5 1 + (1/ log 3) log n for infinitely many values of n. As for upper bounds, Martin and Pomerance [16] gave a construction for which L(n) < (1/ log 2 + o(1)) log log n for infinitely many n. The number of such n \u00E2\u0089\u00A4 x have asymptotic density 0. It is conjectured that for a set of positive integers with asymptotic density 1, that L(n) \u0010 log logn however no previous results have shown L(n) = o(log n) for almost all n. It\u00E2\u0080\u0099s easy to see thatH(p) \u00E2\u0089\u00A4 L(p), so any lower bound onH acts as a lower bound on L. Bounds for the height of the Pratt tree H(p) were obtained in a 2010 paper by Ford, Konyagin and Luca [10]. The bound depends 4 1.1. History and Results on the exponent arising from the Elliot\u00E2\u0080\u0093Halberstam conjecture. Recall the Bombieri\u00E2\u0080\u0093Vinogradov Theorem [7, Chapter 28] implies\u00E2\u0088\u0091 n\u00E2\u0089\u00A4Q max y\u00E2\u0089\u00A4x \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3pi(y;n, 1)\u00E2\u0088\u0092 li(y)\u00CF\u0086(m) \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u001C x(log x)\u00E2\u0088\u0092A (1.5) holds for any Q \u00E2\u0089\u00A4 x1/2(log x)\u00E2\u0088\u0092B and any A > 0, where B = B(A). The Elliot\u00E2\u0080\u0093Halberstam conjecture says that (1.5) holds for Q = x\u00CE\u00B8 for any \u00CE\u00B8 < 1. Let \u00CE\u00B8\u00E2\u0080\u00B2 be such that (1.5) holds for Q = x\u00CE\u00B8\u00E2\u0080\u00B2 . In [10] Ford, Konyagin and Luca showed for any c < 1/(e\u00E2\u0088\u00921 \u00E2\u0088\u0092 log \u00CE\u00B8\u00E2\u0080\u00B2), H(p) > c log log p (1.6) for all butO ( x/(log x)K ) primes p, for someK > 1.Under Elliot\u00E2\u0080\u0093Halberstam, we can take any c < e, but unconditionally, Bombieri\u00E2\u0080\u0093Vinogradov gives any c < 1/(e\u00E2\u0088\u00921 + log 2). In Chapter 5 we show that if n = \u00E2\u0088\u008F p\u00CE\u00B1ii , then L(n) = max i {L(p\u00CE\u00B1ii )} (1.7) and L(p\u00CE\u00B1) = \u00CE\u00B1\u00E2\u0088\u0092 1 + L(p) \u00E2\u0089\u00A5 L(p). (1.8) These two equations imply L(n) \u00E2\u0089\u00A5 L(p) for any p | n. This motivates the following theorem which will be proved in Chapter 5 Theorem 1.6. There exists some c > 0 such that L(n) \u00E2\u0089\u00A5 c log logn for almost all n \u00E2\u0089\u00A4 x. For an upper bound, in [10] it was shown that H(p) \u00E2\u0089\u00A4 (log p)0.95022 (1.9) for all p \u00E2\u0089\u00A4 x outside a set of size O(x exp(\u00E2\u0088\u0092(log x)\u00CE\u00B4) for some \u00CE\u00B4 > 0. We extend this to a result about L(n). Theorem 1.7. If H(p) \u00E2\u0089\u00A4 (log p)\u00CE\u00B3 for almost all p \u00E2\u0089\u00A4 x outside a set of size O ( x exp(\u00E2\u0088\u0092(log x)\u00CE\u00B4)) for some \u00CE\u00B4 > 0, then for some function \u00CE\u00B7, L(n)\u001C (log n)\u00CE\u00B3\u00CE\u00B7(n) for almost all n as n\u00E2\u0086\u0092\u00E2\u0088\u009E. 5 1.1. History and Results The function \u00CE\u00B7(x) can be taken to be as small as O(log log log x). Equa- tion (1.9) yields the following corollary. Corollary 1.8. For almost all n, L(n)\u001C (log n)0.9503. In [10], the authors also came up with a nice probabilistic model which suggested a conjecture that the normal order forH(p) is e log log p. Assuming this conjecture, we give some evidence to suggest a related conjecture for L(n). Conjecture 1.9. The normal order of L(n) is e log logn. 6 Chapter 2 Notation and Required Estimates 2.1 Notation The following notations and conventions will be used throughout this the- sis. The letters p, q, r, s and their subscripts will always denote primes. In Chapters 3 and 4, k \u00E2\u0089\u00A5 2 will be a fixed integer. In Chapter 3 any implicit constant may depend on k, otherwise the constants are absolute. Let vp(n) be the largest power of p which divides n, so that n = \u00E2\u0088\u008F p pvp(n). Let the set Pn be {p : p \u00E2\u0089\u00A1 1 (mod n)}. The notation q \u00E2\u0089\u00BA q\u00E2\u0080\u00B2 is defined to mean that q\u00E2\u0080\u00B2 \u00E2\u0088\u0088 Pq. In Chapter 3 we will assume x > eee . The function y = y(x) is defined to be log log x. Also let \u00CF\u0088(x) be any function going to \u00E2\u0088\u009E such that \u00CF\u0088(x) = o(log y) = o(log log log x). Whenever we use the phrase \u00E2\u0080\u009Cfor almost all n \u00E2\u0089\u00A4 x\u00E2\u0080\u009D in a result, we mean that the result is true for all n \u00E2\u0089\u00A4 x except a set of size o(x). In Chapter 3 the exceptional set will be O(x/\u00CF\u0088(x)). 2.2 Required Estimates The following estimates will be used throughout this thesis. Let \u00CE\u009B(n) be the Von\u00E2\u0080\u0093Mangoldt function defined by \u00CE\u009B(n) = { log p n = pl 0 otherwise. We use the Chebyshev bound\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00CE\u009B(n) = \u00E2\u0088\u0091 pl\u00E2\u0089\u00A4x log p\u001C x. (2.1) 7 2.2. Required Estimates Also define the related function \u00CE\u00B8(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x log p. It follows from (2.1) that \u00CE\u00B8(x)\u001C x. (2.2) We also require a formula of Mertens (see [17, Theorem 2.7(b)])\u00E2\u0088\u0091 q\u00E2\u0089\u00A4x log q q = log x+O(1). (2.3) We use partial summation on (2.2) to obtain some tail estimates. Lemma 2.1. For all x > 2, we have the following sums over primes. (a) \u00E2\u0088\u0091 q>x log q q2 \u001C 1 x . (2.4) (b) \u00E2\u0088\u0091 q>x 1 q2 \u001C 1 x log x . (2.5) Proof. Equation (2.5) follows from (2.4) since log x < log q. As for Equation (2.4), \u00E2\u0088\u0091 q>x log q q2 = \u00E2\u0088\u00AB \u00E2\u0088\u009E x d(\u00CE\u00B8(t)) t2 = 2\u00CE\u00B8(x) x3 + \u00E2\u0088\u00AB \u00E2\u0088\u009E x 2\u00CE\u00B8(t)dt t3 = 2\u00CE\u00B8(x) x3 +O (\u00E2\u0088\u00AB \u00E2\u0088\u009E x dt t2 ) \u001C 1 x . Given m,x \u00E2\u0089\u00A5 2, let A be the smallest a for which ma > x. We can then manipulate the sums \u00E2\u0088\u0091 a\u00E2\u0088\u0088N P (a) ma = 1 m \u00E2\u0088\u009E\u00E2\u0088\u0091 a=0 P (a) ma and \u00E2\u0088\u0091 a\u00E2\u0088\u0088N ma>x 1 ma \u001C 1 x \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 \u00E2\u0088\u009E\u00E2\u0088\u0091 a=A 1 ma\u00E2\u0088\u0092A \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 = 1x \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 \u00E2\u0088\u009E\u00E2\u0088\u0091 a=0 1 ma \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 8 2.2. Required Estimates for any polynomial P (x). Then by noting that \u00E2\u0088\u0091\u00E2\u0088\u009E a=A P (a) ma \u001CP 1 uniformly for m \u00E2\u0089\u00A5 2 and A \u00E2\u0089\u00A5 0 we obtain the estimates\u00E2\u0088\u0091 a\u00E2\u0088\u0088N P (a) ma \u001CP 1 m , \u00E2\u0088\u0091 a\u00E2\u0088\u0088N ma>x 1 ma \u001C 1 x . (2.6) From [17, Corollary 1.15] we get\u00E2\u0088\u0091 s\u00E2\u0089\u00A4x 1 s = log x+O(1) (2.7) We will also make frequent use of the Brun-Titchmarsh inequality [17, The- orem 3.9] which says for all n \u00E2\u0089\u00A4 t, pi(t;n, a)\u001C t \u00CF\u0086(n) log(t/n) . (2.8) By partial summation on (2.8) we can obtain\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t p\u00E2\u0088\u0088Pn 1 p \u001C log log t \u00CF\u0086(n) . (2.9) Whenever n/\u00CF\u0086(n) is bounded, as it will be whenever n is a prime, prime power or a product of two prime powers, we can replace (2.9) with\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t p\u00E2\u0088\u0088Pn 1 p \u00E2\u0089\u00A4 c log log t n (2.10) for some absolute constant c. We include the c because occasionally we require an inequality as opposed to an estimate. From [18, Theorem 1] we obtain the asymptotic\u00E2\u0088\u0091 p\u00E2\u0088\u0088Pn p\u00E2\u0089\u00A4t 1 p = log log t \u00CF\u0086(n) +O ( log n \u00CF\u0086(n) ) . (2.11) Equation (2.11) easily implies\u00E2\u0088\u0091 p\u00E2\u0088\u0088Pn p\u00E2\u0089\u00A4t 1 p\u00E2\u0088\u0092 1 = log log t \u00CF\u0086(n) +O ( log n \u00CF\u0086(n) ) , (2.12) 9 2.3. Early Results since the difference is \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pn p\u00E2\u0089\u00A4t 1 p(p\u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 \u00E2\u0088\u009E\u00E2\u0088\u0091 m=1 1 mn(mn+ 1) < 1 n2 \u00E2\u0088\u009E\u00E2\u0088\u0091 m=1 1 m2 \u001C 1 n2 . The Bombieri\u00E2\u0080\u0093Vinogradov Theorem [7, Chapter 28] implies\u00E2\u0088\u0091 n\u00E2\u0089\u00A4Q max y\u00E2\u0089\u00A4x \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3pi(y;n, 1)\u00E2\u0088\u0092 li(y)\u00CF\u0086(m) \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u001C x(log x)\u00E2\u0088\u0092A (2.13) with Q \u00E2\u0089\u00A4 x1/2(log x)\u00E2\u0088\u0092B for any A > 0 and B = B(A). We will use this repeatedly in Chapter 3 with Q = x1/3. We also often use the Cauchy\u00E2\u0080\u0093 Schwarz inequality in the following form. If f(n) and g(n) are arithmetic functions, then for any t \u00E2\u0089\u00A5 1,\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u0091 n\u00E2\u0089\u00A4t f(n)g(n) \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A32 \u00E2\u0089\u00A4\u00E2\u0088\u0091 n\u00E2\u0089\u00A4t |f(n)|2 \u00E2\u0088\u0091 n\u00E2\u0089\u00A4t |g(n)|2. (2.14) 2.3 Early Results In Chapters 3 and 5 we will require the following technical lemma. Lemma 2.2. Fix a prime q and positive integers k, \u00CE\u00B1. The number of n \u00E2\u0089\u00A4 x such that there exists p, q1, . . . , qk\u00E2\u0088\u00921 satisfying q\u00CE\u00B1 | qk\u00E2\u0088\u00921 \u00E2\u0088\u0092 1, qk\u00E2\u0088\u00921 | qk\u00E2\u0088\u00922 \u00E2\u0088\u0092 1, . . . , q1 | p\u00E2\u0088\u0092 1 and p | n is at most x(cy)k q\u00CE\u00B1 for some absolute constant c. Proof. By repeated uses of Equation (2.10), the number of such n is bounded 10 2.3. Early Results by \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 p|n \u00E2\u0088\u0091 q1|p\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 qk\u00E2\u0088\u00921|qk\u00E2\u0088\u00922\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00CE\u00B1|qk\u00E2\u0088\u00921\u00E2\u0088\u00921 1 = \u00E2\u0088\u0091 qk\u00E2\u0088\u00921\u00E2\u0089\u00A11 (mod q\u00CE\u00B1) \u00E2\u0088\u0091 qk\u00E2\u0088\u00922\u00E2\u0089\u00A11 (mod qk\u00E2\u0088\u00921) \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p\u00E2\u0089\u00A11 (mod q1) \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x n\u00E2\u0089\u00A10 (mod p) 1 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 qk\u00E2\u0088\u00921\u00E2\u0089\u00A11 (mod q\u00CE\u00B1) \u00E2\u0088\u0091 qk\u00E2\u0088\u00922\u00E2\u0089\u00A11 (mod qk\u00E2\u0088\u00921) \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p\u00E2\u0089\u00A11 (mod q1) x p \u00E2\u0089\u00A4 \u00E2\u0088\u0091 qk\u00E2\u0088\u00921\u00E2\u0089\u00A11 (mod q\u00CE\u00B1) \u00E2\u0088\u0091 qk\u00E2\u0088\u00922\u00E2\u0089\u00A11 (mod qk\u00E2\u0088\u00921) \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 q1\u00E2\u0089\u00A11 (mod q2) xcy q1 \u00E2\u0089\u00A4 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 qk\u00E2\u0088\u00921\u00E2\u0089\u00A11 (mod q\u00CE\u00B1) x(cy)k\u00E2\u0088\u00921 qk\u00E2\u0088\u00921 \u00E2\u0089\u00A4 x(cy) k q\u00CE\u00B1 . In our proofs of Propositions 3.13 and 3.14 we will see that M1(x) and M2(x) will reduce to summations involving pi(x; p, 1). We will be using some sieve techniques to bound these sums and those will require some bounds on sums on multiplicative functions involving \u00CF\u0086(m). The following involves the estimation of the latter sums. Lemma 2.3. For any non-negative integer L we have \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t mL \u00CF\u0086(m)L+1 \u001CL log t. (2.15) Proof. If f(n) is a non-negative multiplicative function, we know that \u00E2\u0088\u0091 n\u00E2\u0089\u00A4t f(n) \u00E2\u0089\u00A4 \u00E2\u0088\u008F p\u00E2\u0089\u00A4t \u00E2\u0088\u009E\u00E2\u0088\u0091 r=0 f(pr). (2.16) 11 2.3. Early Results Applying (2.16) with n L \u00CF\u0086(n)L+1 yields \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t mL \u00CF\u0086(m)L+1 \u00E2\u0089\u00A4 \u00E2\u0088\u008F p\u00E2\u0089\u00A4t ( 1 + \u00E2\u0088\u009E\u00E2\u0088\u0091 r=1 prL (pr \u00E2\u0088\u0092 pr\u00E2\u0088\u00921)L+1 ) = \u00E2\u0088\u008F p\u00E2\u0089\u00A4t ( 1 + \u00E2\u0088\u009E\u00E2\u0088\u0091 r=1 pL\u00E2\u0088\u0092r+1 (p\u00E2\u0088\u0092 1)L+1 ) = \u00E2\u0088\u008F p\u00E2\u0089\u00A4t ( 1 + 1 (p\u00E2\u0088\u0092 1)L+1 pL 1\u00E2\u0088\u0092 1p ) = \u00E2\u0088\u008F p\u00E2\u0089\u00A4t ( 1 + pL+1 (p\u00E2\u0088\u0092 1)L+2 ) \u00E2\u0089\u00A4 exp (\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t log ( 1 + pL+1 (p\u00E2\u0088\u0092 1)L+2 )) = exp (\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t ( pL+1 (p\u00E2\u0088\u0092 1)L+2 +OL ( 1 p2 ))) = exp (\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t ( 1 p +OL ( 1 p2 ))) \u001CL log t using (2.3). Lemma 2.4. Let L be a nonnegative integer and \u00CE\u00B3 a positive real number. Given a positive integer C \u00E2\u0089\u00A4 t\u00CE\u00B3 and non-negative integer L we have \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)L \u00CF\u0086(Cm+ 1)L\u00CF\u0086(m) \u001CL,\u00CE\u00B3 log t. (2.17) Proof. It will suffice to show \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)2L\u00E2\u0088\u00921 \u00CF\u0086(Cm+ 1)2L \u001CL,\u00CE\u00B3 log t C (2.18) 12 2.3. Early Results as then by Cauchy\u00E2\u0080\u0093Schwarz (2.14) we can get that(\u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)L \u00CF\u0086(Cm+ 1)L\u00CF\u0086(m) )2 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)2L\u00E2\u0088\u00921 \u00CF\u0086(Cm+ 1)2L \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1) \u00CF\u0086(m)2 \u001CL,\u00CE\u00B3 ( log t C ) C log t \u001CL,\u00CE\u00B3 log2 t by using Lemma 2.3 and (2.18). Let G(t) = \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)2L \u00CF\u0086(Cm+ 1)2L . We show Equation (2.18) by first showing G(t) \u001CL,\u00CE\u00B3 t. This implies Equa- tion (2.18) since \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)2L\u00E2\u0088\u00921 \u00CF\u0086(Cm+ 1)2L < 1 C \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)2L m\u00CF\u0086(Cm+ 1)2L = 1 C \u00E2\u0088\u00AB t 1\u00E2\u0088\u0092 d(G(u)) u = 1 C ( G(t) t + \u00E2\u0088\u00AB t 1\u00E2\u0088\u0092 G(u) u2 ) \u001CL,\u00CE\u00B3 1 C ( 1 + \u00E2\u0088\u00AB t 1\u00E2\u0088\u0092 1 u ) \u001CL,\u00CE\u00B3 1 C (log t) To show Equation (2.18) we start by defining s(n) to be the multiplicative function defined by n2L \u00CF\u0086(n)2L = 1 \u00E2\u0088\u0097 s = \u00E2\u0088\u0091 d|n s(d). Testing at prime powers, we can easily see that s(1) = 1, s(p) = ( 1\u00E2\u0088\u0092 1 p )\u00E2\u0088\u00922L \u00E2\u0088\u0092 1 and s(pk) = 0 for all k \u00E2\u0089\u00A5 2. 13 2.3. Early Results Hence \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cm+ 1)2L \u00CF\u0086(Cm+ 1)2L = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4Ct+1 n\u00E2\u0089\u00A11 (mod C) n2L \u00CF\u0086(n)2L = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4Ct+1 n\u00E2\u0089\u00A11 (mod C) \u00E2\u0088\u0091 d|n s(d) = \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) \u00E2\u0088\u0091 n\u00E2\u0089\u00A4Ct+1 d|n n\u00E2\u0089\u00A11 (mod C) 1 = \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) ( t d +O(1) ) = t \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) d +O ( \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) ) . We require some estimates on s(d). For the sum of the multiplicative function s(d)/d, \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) d \u00E2\u0089\u00A4 \u00E2\u0088\u008F p\u00E2\u0089\u00A4Ct+1 ( 1 + (1\u00E2\u0088\u0092 1/p)\u00E2\u0088\u00922L \u00E2\u0088\u0092 1 p ) \u00E2\u0089\u00A4 \u00E2\u0088\u008F p\u00E2\u0089\u00A4Ct+1 ( 1 +OL ( 1 p2 )) = exp ( \u00E2\u0088\u0091 p\u00E2\u0089\u00A4Ct+1 log ( 1 +OL ( 1 p2 ))) = exp ( \u00E2\u0088\u0091 p\u00E2\u0089\u00A4Ct+1 OL ( 1 p2 )) = exp(OL(1)) \u001CL 1. 14 2.3. Early Results For the sum of s(d),\u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) \u00E2\u0089\u00A4 \u00E2\u0088\u008F p\u00E2\u0089\u00A4Ct+1 ( 1 + (1\u00E2\u0088\u0092 1/p)\u00E2\u0088\u00922L \u00E2\u0088\u0092 1 ) = \u00E2\u0088\u008F p\u00E2\u0089\u00A4Ct+1 (1\u00E2\u0088\u0092 1/p)\u00E2\u0088\u00922L = exp ( \u00E2\u0088\u0091 p\u00E2\u0089\u00A4Ct+1 log ( 1 +OL ( 1 p ))) = exp ( \u00E2\u0088\u0091 p\u00E2\u0089\u00A4Ct+1 OL ( 1 p )) = exp ( OL(log log(Ct+ 1)) ) \u001C exp (OL,\u00CE\u00B3(log log t)) \u001C (log t)OL,\u00CE\u00B3(1) \u001CL,\u00CE\u00B3 t Therefore G(t) = t \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) d +O ( \u00E2\u0088\u0091 d\u00E2\u0089\u00A4Ct+1 s(d) ) \u001CL,\u00CE\u00B3 t as needed. The following sum seems more complicated. However, we can handle it using repeated applications of Lemma 2.4. Lemma 2.5. For positive integers C1, C2, . . . , Cr \u00E2\u0089\u00A4 t\u00CE\u00B3 and non-negative integers L1, L2, . . . , Lr we have\u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) L1(C2m+ 1) L2 . . . (Crm+ 1) Lr \u00CF\u0086(C1m+ 1)L1\u00CF\u0086(C2m+ 1)L2 . . . \u00CF\u0086(Crm+ 1)Lr\u00CF\u0086(m) \u001CL1,...,Lr,\u00CE\u00B3 log t. (2.19) Proof. We proceed by induction. The case r = 1 is covered by Lemma 2.4. Suppose \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) L1(C2m+ 1) L2 ...(Crm+ 1) Lr \u00CF\u0086(C1m+ 1)L1\u00CF\u0086(C2m+ 1)L2 . . . \u00CF\u0086(Crm+ 1)Lr\u00CF\u0086(m) \u001CL1,...,Lr,\u00CE\u00B3 log t. 15 2.3. Early Results By Cauchy\u00E2\u0080\u0093Schwarz (2.14), we get that(\u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) L1(C2m+ 1) L2 . . . (Cr+1m+ 1) Lr+1 \u00CF\u0086(C1m+ 1)L1\u00CF\u0086(C2m+ 1)L2 . . . \u00CF\u0086(Cr+1m+ 1)Lr+1\u00CF\u0086(m) )2 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) 2L1(C2m+ 1) 2L2 . . . (Crm+ 1) 2Lr \u00CF\u0086(C1m+ 1)2L1\u00CF\u0086(C2m+ 1)2L2 . . . \u00CF\u0086(Crm+ 1)2Lr\u00CF\u0086(m) \u00C2\u00B7 \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (Cr+1m+ 1) 2Lr+1 \u00CF\u0086(Cr+1m+ 1)2Lr+1\u00CF\u0086(m) \u001CL1,...,Lr+1,\u00CE\u00B3 log2 t by the induction hypothesis and Lemma 2.4, completing the proof. Now here is the lemma that we will use in Section 3.7. Lemma 2.6. For positive integers C1, C2, ..., Cr \u00E2\u0089\u00A4 t\u00CE\u00B3 and non-negative in- tegers L1, L2, ..., Lr, L we have\u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) L1(C2m+ 1) L2 ...(Crm+ 1) LrmL\u00E2\u0088\u00921 \u00CF\u0086(C1m+ 1)L1\u00CF\u0086(C2m+ 1)L2 . . . \u00CF\u0086(Crm+ 1)Lr\u00CF\u0086(m)L \u001CL1,...,Lr,L,\u00CE\u00B3 log t. (2.20) Proof. Once again we\u00E2\u0080\u0099ll use Cauchy\u00E2\u0080\u0093Schwarz (2.14) and the previous lem- mas.(\u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) L1(C2m+ 1) L2 . . . (Crm+ 1) LrmL\u00E2\u0088\u00921 \u00CF\u0086(C1m+ 1)L1\u00CF\u0086(C2m+ 1)L2 . . . \u00CF\u0086(Crm+ 1)Lr\u00CF\u0086(m)L )2 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t (C1m+ 1) 2L1(C2m+ 1) 2L2 . . . (Crm+ 1) 2Lr \u00CF\u0086(C1m+ 1)2L1\u00CF\u0086(C2m+ 1)2L2 . . . \u00CF\u0086(Crm+ 1)2Lr\u00CF\u0086(m) \u00C2\u00B7 \u00E2\u0088\u0091 m\u00E2\u0089\u00A4t m2L\u00E2\u0088\u00922 \u00CF\u0086(m)2L\u00E2\u0088\u00921 \u001CL1,...,Lr,L,\u00CE\u00B3 log2 t by Lemmas 2.3 and 2.5. 16 Chapter 3 Iterated Carmichael Lambda Function 3.1 Required Propositions and Proof of Theorem 1.4 As mentioned in Chapter 1, the main contribution to log(n/\u00CE\u00BBk(n)) will come from log(\u00CF\u0086k(n)/\u00CE\u00BBk(n)). Estimating this term will involve a summation over prime powers which divide each of \u00CF\u0086k(n) and \u00CE\u00BBk(n). It turns out that the largest contribution to this term will come from small primes which divide \u00CF\u0086k(n). By small, we mean primes q \u00E2\u0089\u00A4 (log log x)k = yk. We will split the sum into small primes and large primes q > yk. To prove Theorem 1.4 we will require the following propositions. The first summations deal with the large primes which divide \u00CF\u0086k(n) and the second involves the large primes whose prime powers divide \u00CF\u0086k(n). We will show that the contribution of these primes to the main sum is small and hence it will end up as part of the error term. Proposition 3.1.\u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))=1 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q \u001C yk\u00CF\u0088(x) for almost all n \u00E2\u0089\u00A4 x. Proposition 3.2. \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0089\u00A52 \u00CE\u00BDq(\u00CF\u0086k(n)) log q \u001C yk\u00CF\u0088(x) for almost all n \u00E2\u0089\u00A4 x. Since the main contribution will come from small primes dividing \u00CF\u0086k(n), the next proposition will show that the contribution of small primes dividing \u00CE\u00BBk(n) to the main sum can also be merged into the error term. 17 3.1. Required Propositions and Proof of Theorem 1.4 Proposition 3.3. \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CE\u00BBk(n)) log q \u001C yk\u00CF\u0088(x) for almost all n \u00E2\u0089\u00A4 x. That will leave us with the contribution of small primes dividing \u00CF\u0086k(n). Recall the following definition of an additive function. Definition 3.4. An arithmetic function f(n) is called additive if for all (m,n) = 1, f(mn) = f(m) + f(n). If in addition f(pk) = f(p) for all k \u00E2\u0089\u00A5 1, then f(n) is called strongly additive. We will use a strongly additive function to approximate the remaining sum. Let hk(n) be the strongly additive function defined by hk(n) = \u00E2\u0088\u0091 p1|n \u00E2\u0088\u0091 p2|p1\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(pk \u00E2\u0088\u0092 1) log q. The following proposition shows that the difference between the sum involv- ing the small primes dividing \u00CF\u0086k(n) and the term hk(n) is small. Proposition 3.5.\u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CF\u0086k(n)) log q = hk(n) +O(y k\u00E2\u0088\u00921 log y \u00C2\u00B7 \u00CF\u0088(x)) for almost all n \u00E2\u0089\u00A4 x. That leaves us with log(\u00CF\u0086k(n)/\u00CE\u00BBk(n)) being approximated by hk(n). The last proposition will obtain an asymptotic formula for hk(n). From there we will have enough armoury to tackle Theorem 1.4. Since hk(n) is strongly additive, we use the Turan\u00E2\u0080\u0093Kubilius inequality (Corollary A.2) which will show the final proposition. Proposition 3.6. hk(n) = 1 (k \u00E2\u0088\u0092 1)!y k log y +O(yk) for almost all n \u00E2\u0089\u00A4 x. 18 3.1. Required Propositions and Proof of Theorem 1.4 Proof of Theorem 1.4. We start by breaking down the function log(n/\u00CE\u00BBk(n)). log ( n \u00CE\u00BBk(n) ) = log ( n \u00CF\u0086(n) ) + log ( \u00CF\u0086(n) \u00CF\u00862(n) ) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ log ( \u00CF\u0086k\u00E2\u0088\u00921(n) \u00CF\u0086k(n) ) + log ( \u00CF\u0086k(n) \u00CE\u00BBk(n) ) . (3.1) Using the lower bound \u00CF\u0086(m)\u001D m/ log logm from [17, Theorem 2.3] we have that log ( n \u00CF\u0086(n) ) + log ( \u00CF\u0086(n) \u00CF\u00862(n) ) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ log ( \u00CF\u0086k\u00E2\u0088\u00921(n) \u00CF\u0086k(n) ) \u001C log log log n. (3.2) Inserting equation (3.2) into equation (3.1) yields log ( n \u00CE\u00BBk(n) ) = log ( \u00CF\u0086k(n) \u00CE\u00BBk(n) ) +O(log log log n). In fact we could have used a more precise estimate for \u00CF\u0086i(n)/\u00CF\u0086i+1(n) for i \u00E2\u0089\u00A5 1 which can be found in [8] but the one we used is good enough. Next we break down the remaining term into summations. We will break it up into small primes and large primes. log ( \u00CF\u0086k(n) \u00CE\u00BBk(n) ) = \u00E2\u0088\u0091 q>yk (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q = \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))=1 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q + \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0089\u00A52 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CF\u0086k(n)) log q \u00E2\u0088\u0092 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CE\u00BBk(n)) log q. Note that if a | b, then \u00CE\u00BB(a) | \u00CF\u0086(b) since \u00CE\u00BB(a) | \u00CF\u0086(a) | \u00CF\u0086(ma) for any integer m. This quickly implies that \u00CE\u00BBk(n) always divides \u00CF\u0086k(n) for all k and so we get 0 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0089\u00A52 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0089\u00A52 (\u00CE\u00BDq(\u00CF\u0086k(n)) log q. 19 3.2. Prime Power Divisors of \u00CF\u0086k(n) Using Propositions 3.1,3.2,3.3 and 3.5 we get log ( n \u00CE\u00BBk(n) ) = hk(n) +O ( yk\u00CF\u0088(x) ) for almost all n \u00E2\u0089\u00A4 x. Finally by using Proposition 3.6 we get log ( n \u00CE\u00BBk(n) ) = 1 (k \u00E2\u0088\u0092 1)!y k log y +O ( yk\u00CF\u0088(x) ) for almost all n \u00E2\u0089\u00A4 x, finishing the proof of Theorem 1.4. 3.2 Prime Power Divisors of \u00CF\u0086k(n) For various reasons thoughout this paper, we are concerned with the number of n \u00E2\u0089\u00A4 x such that qa can divide \u00CF\u0086k(n). We will analyze a few of those situations here: Case 1: q2 | n. Clearly the number of such n is at most x q2 . Case 2: There exists p1 \u00E2\u0088\u0088 Pq2 , p2 \u00E2\u0088\u0088 Pp1 , p3 \u00E2\u0088\u0088 Pp2 , ..., pl \u00E2\u0088\u0088 Ppl\u00E2\u0088\u00921 where pl | n. By using Lemma 2.2 we know the number of such n \u00E2\u0089\u00A4 x is Ol(xyl/q2). Cases 1 and 2 deal with any case where p \u00E2\u0088\u0088 Pq2 , we are just left with the possibilities not containing any powers of q. Unfortunately these cases still allow for many possibilities which we will display in an array. There are lots of ways for a prime power qa to divide \u00CF\u0086k(n). We now define various sets of primes that are involved in generating these powers of q, and we will eventually sum over all possibilities for these sets of primes. The set Lh,i will denote a finite set of primes. To begin, the set L1,2 will be an arbitrary finite set of primes in Pq and let L1,1 be empty. That is: Case 3: Level (1,2) L1,2 \u00E2\u008A\u0086 Pq. Level (2,1) (Obtaining the primes in the previous level) L2,1 is any set of primes with the property that for all p \u00E2\u0088\u0088 L1,1 \u00E2\u0088\u00AA L1,2, there exists a unique prime r \u00E2\u0088\u0088 L2,1 such that r \u00E2\u0088\u0088 Pp. In other words p will divide \u00CF\u0086(r) and hence the primes in L2,1 will create the primes in L1,1\u00E2\u0088\u00AAL1,2. Level (2,2) (New primes in Pq) L2,2 \u00E2\u008A\u0086 Pq. 20 3.2. Prime Power Divisors of \u00CF\u0086k(n) In general for all 1 < h \u00E2\u0089\u00A4 k we have for all p \u00E2\u0088\u0088 Lh\u00E2\u0088\u00921,1 \u00E2\u0088\u00AA Lh\u00E2\u0088\u00921,2 there exists a unique prime r \u00E2\u0088\u0088 Lh,1 such that r \u00E2\u0088\u0088 Pp,Lh,2 is an arbitrary subset of Pq, and r \u00E2\u0088\u0088 Lk,1 \u00E2\u0088\u00AA Lk,2 \u00E2\u0087\u0092 r | n. Some description of the terms are in order including some helpful defi- nitions. Definition 3.7. An incarnation I of Case 3 is some specified description of how the primes in a lower level create the primes in the level directly above. For example, for k = 3, an incarnation I for which q4 | \u00CF\u00863(n) would be s1, s2, s3, r3, r4 \u00E2\u0088\u0088 Pq where r1 \u00E2\u0088\u0088 Ps1 , r2 \u00E2\u0088\u0088 Ps2s3 , p1 \u00E2\u0088\u0088 Pr1r2 , p2 \u00E2\u0088\u0088 Pr3r4 , with p1p2 | n. Definition 3.8. An subincarnation of I is an incarnation with added condi- tions. In other words if J is a subincarnation of I and an integer n satisfies incarnation J, then it will also satisfy incarnation I. For example, I is a subincarnation of the incarnation s1, s3, r3, r4 \u00E2\u0088\u0088 Pq where r1 \u00E2\u0088\u0088 Ps1 , r2 \u00E2\u0088\u0088 Ps3 , p1 \u00E2\u0088\u0088 Pr1r2 , p2 \u00E2\u0088\u0088 Pr3r4 , with p1p2 | n. Let p be a prime in Lh,i which we need to divide \u00CF\u0086k\u00E2\u0088\u0092h+1(n). The def- inition of Lh,i ensures that there is a unique prime r dividing \u00CF\u0086k\u00E2\u0088\u0092h(n) for which p | r\u00E2\u0088\u0092 1. The primes in levels (k, 1), (k, 2) dividing n are for the base case of the recursion, so that each prime divides \u00CF\u00860(n) = n. When i = 2 we are introducing new primes to get greater powers of q in \u00CF\u0086k(n). Note that it\u00E2\u0080\u0099s not necessary to have any primes on the levels (h, 2). In fact the \u00E2\u0080\u009Cworst case scenario\u00E2\u0080\u009D that we will see has no primes on these except Level (1,2). Now that we\u00E2\u0080\u0099ve described the way to get qa | \u00CF\u0086k(n), what is our exponent a? Let mh,i = #Lh,i. From the recursion above we can see that qmk,2 | \u00CF\u0086(n) and so do the primes in Lk\u00E2\u0088\u00921,1. For the second iteration of \u00CF\u0086, qmk,2\u00E2\u0088\u00921+mk\u00E2\u0088\u00921,2 | \u00CF\u00862(n) and so do the primes in Lk\u00E2\u0088\u00922,1. Hence the power of q which divides \u00CF\u0086k(n) is max 1\u00E2\u0089\u00A4j\u00E2\u0089\u00A4k (m1,1 + \u00E2\u0088\u0091 2\u00E2\u0089\u00A4h\u00E2\u0089\u00A4j (mh,2 \u00E2\u0088\u0092 1)) (3.3) where the sum can be empty if there are no primes in the second level (j, 2) or there are not enough to survive, i.e. mj,2 < j\u00E2\u0088\u00921 and hence q - \u00CF\u0086j( \u00E2\u0088\u008F Lj,2 p). Without loss of generality, we can assume the former, since the later is a subincarnation of the former. Now we\u00E2\u0080\u0099ll introduce some notation to be used in future propositions. For any fixed incarnation of Case 3, let M be the total number of primes, N be 21 3.2. Prime Power Divisors of \u00CF\u0086k(n) the total number of new primes introduced at the levels (h, 2) and H be the maximum necessary level (h, 2). Specifically M = \u00E2\u0088\u0091 h (mh,1 +mh,2) N = \u00E2\u0088\u0091 h\u00E2\u0089\u00A4H mh,2 and H yields the maximum value in (3.3). Note that under this notation, qN\u00E2\u0088\u0092H+1 | \u00CF\u0086k(n). For example, in the incarnation I above, L1,2 = {s1, s2, s3},L2,1 = {r1, r2},L2,2 = {r3, r4},L3,1 = {p1, p2},L3,2 = \u00E2\u0088\u0085 as well as m1,2 = 3,m2,1 = 2,m2,2 = 2,m3,1 = 2,m3,2 = 0. Hence M = 9, N = 5, H = 2 and so the power of q which divides \u00CF\u00863(n) is 5\u00E2\u0088\u0092 2 + 1 = 4 as expected. Now that we\u00E2\u0080\u0099ve described Case 3, how many possible n are in that case? Lemma 3.9. The number of n \u00E2\u0089\u00A4 x satisfying any incarnation of Case 3 is O ( cM xyM qN ) where c is the constant from equation (2.10). Proof. Let Lh = Lh,1 \u00E2\u0088\u00AA Lh,2. We use Brun-Titchmarsh (2.10) for all the primes at each level of Case 3, so the number of n is \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 p1\u00E2\u0088\u0088L1 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088L2 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Lk 1 = \u00E2\u0088\u0091 p1\u00E2\u0088\u0088L1 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088L2 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Lk \u00E2\u0088\u0091 pk|n n\u00E2\u0089\u00A4x 1 \u001C \u00E2\u0088\u0091 p1\u00E2\u0088\u0088L1 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088L2 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Lk x\u00E2\u0088\u008F pk\u00E2\u0088\u0088Lk pk . Note that we have repeatedly counted the same primes in the sum as we can reorder the primes in each level. It won\u00E2\u0080\u0099t be important here, but will need to be more carefully addressed later. Since the primes in level (k, 1) gave us some pk \u00E2\u0088\u0088 Ppk\u00E2\u0088\u00921 for all the primes in Lk\u00E2\u0088\u00921, and for p \u00E2\u0088\u0088 Lk,2 we have p \u00E2\u0088\u0088 Pq. By Brun\u00E2\u0080\u0093Titchmarsh (2.10) we get that the above sum is \u001C \u00E2\u0088\u0091 p1\u00E2\u0088\u0088L1 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088L2 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Lk\u00E2\u0088\u00921 x(cy)mk,1+mk,2\u00E2\u0088\u008F pk\u00E2\u0088\u00921\u00E2\u0088\u0088Lk\u00E2\u0088\u00921 pk\u00E2\u0088\u00921q mk,2 . 22 3.3. Large Primes Dividing \u00CF\u0086k(n) Once again we get mk\u00E2\u0088\u00921,1 + mk\u00E2\u0088\u00921,2 new applications of Brun-Titchmarsh giving the new primes in level k \u00E2\u0088\u0092 2 as well as mk\u00E2\u0088\u00921,2 new powers of q. Continuing along in this manner we get: \u001C \u00E2\u0088\u0091 p1\u00E2\u0088\u0088L1 x(cy) \u00E2\u0088\u0091 2\u00E2\u0089\u00A4i\u00E2\u0089\u00A4k(mi,1+mi,2)\u00E2\u0088\u008F p1\u00E2\u0088\u0088L1 p1q \u00E2\u0088\u0091 2\u00E2\u0089\u00A4i\u00E2\u0089\u00A4kmi,2 \u001C x(cy) \u00E2\u0088\u0091 1\u00E2\u0089\u00A4i\u00E2\u0089\u00A4k(mi,1+mi,2) q \u00E2\u0088\u0091 1\u00E2\u0089\u00A4i\u00E2\u0089\u00A4kmi,2 = x(cy)M qN . The last thing we\u00E2\u0080\u0099ll consider in this section about the ways to obtain \u00CF\u0086k(n) is to determine the number of possible incarnations of Case 3. We note that there are lots of incarnations which are subincarnations of others. We will develop a concept of minimality. Definition 3.10. An incarnation of Case 3 is minimal if it does not contain any strings of p1 \u00E2\u0088\u0088 Pp2 , p2 \u00E2\u0088\u0088 Pp3 . . . pk\u00E2\u0088\u00921 \u00E2\u0088\u0088 Ppk where pk | n. Note that any incarnation of Case 3 is a subincarnation of a minimal one. We now use this concept to show the number of necessary incarnations of Case 3 is small. 3.3 Large Primes Dividing \u00CF\u0086k(n) In this section we will prove the two propositions dealing with q being large. We\u00E2\u0080\u0099ll start with the proposition where \u00CE\u00BDq(\u00CF\u0086k(n)) = 1. Proof of Proposition 3.1. It suffices to show\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))=1 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q \u001C xyk as then there are at most O ( xyk yk\u00CF\u0088(x) ) = O ( x \u00CF\u0088(x) ) such n where the bound for the sum in Proposition 3.1 fails to hold. We examine the cases where \u00CE\u00BDq(\u00CF\u0086k(n)) = 1. Using the notation in Lemma 3.9 we have two subcases for Case 3, whether N = 1 or N > 1. Suppose N = 1, then H = 1, m1,2 = 1 and mh,2 = 0 for 1 < h \u00E2\u0089\u00A4 k. Since mh,1 \u00E2\u0089\u00A4 mh\u00E2\u0088\u00921,1 + mh\u00E2\u0088\u00921,2 we get mh,1 \u00E2\u0089\u00A4 1 for all 1 \u00E2\u0089\u00A4 h \u00E2\u0089\u00A4 k. Hence mh,1 = 1 for all h \u00E2\u0089\u00A4 k. Therefore we are left with the case 23 3.3. Large Primes Dividing \u00CF\u0086k(n) p1 \u00E2\u0088\u0088 Pq, p2 \u00E2\u0088\u0088 Pp1 , p3 \u00E2\u0088\u0088 Pp2 , . . . , pk \u00E2\u0088\u0088 Ppk\u00E2\u0088\u00921 where pk | n. However in this case we also get \u00CE\u00BDq(\u00CE\u00BBk(n))) = 1 giving us no additions to our sum. Suppose N > 1, then by repeatedly using mh,1 \u00E2\u0089\u00A4 mh\u00E2\u0088\u00921,1 + mh\u00E2\u0088\u00921,2 we have M = \u00E2\u0088\u0091 h(mh,1 + mh,2) \u00E2\u0089\u00A4 k \u00E2\u0088\u0091 hmh,2 = kN. The number of cases we get are O ( cM xyM qN ) \u001C c MxykN qN \u001C c Mxy2k q2 since y > qk. Since vq(\u00CF\u0086k(n)) = N \u00E2\u0088\u0092H + 1 and H \u00E2\u0089\u00A4 k, we conclude N \u00E2\u0089\u00A4 k implying that M \u00E2\u0089\u00A4 k2. Hence cM is bounded as a function of k. Also since M is bounded in terms of k, there are Ok(1) possible incarnations of Case 3, and the bound already absorbs the possiblities from Cases 1 and 2. Hence we have \u00E2\u0088\u0091 q>yk \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00CE\u00BDq(\u00CF\u0086k(n))=1 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 \u00CE\u00BDq(\u00CE\u00BBk(n))) log q \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q>yk \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00CE\u00BDq(\u00CF\u0086k(n))=1 N>1 log q \u001C \u00E2\u0088\u0091 q>yk xy2k log q q2 \u001C xyk by (2.4). We turn our attention to vq(\u00CF\u0086k(n)) > 1. We have to be more careful here since we can\u00E2\u0080\u0099t guarantee that the number of incarnations of Case 3 is Ok(1). We\u00E2\u0080\u0099ll start by proving a lemma which can eliminate a lot of those cases. Lemma 3.11. Let q > yk and Sq = Sq(x) consist of all n \u00E2\u0089\u00A4 x such that Case 1,2 or Case 3 where M \u00E2\u0089\u00A4 k(N \u00E2\u0088\u0092 1) occurs. Then #Sq \u001C xy k q2 . Proof. There are clearly Ok(1) incarnations of Cases 1 and 2 and each yield at most O(xyk/q2) such n. By Lemma 3.9 for each incarnation of Case 3, we get at most O ( cMxyM qN ) \u001C c Mxyk q2 24 3.3. Large Primes Dividing \u00CF\u0086k(n) such n since M \u00E2\u0089\u00A4 k(N \u00E2\u0088\u0092 1) and q > yk. It remains to show we only require Ok(1) such incarnations. Suppose n satisfies an incarnation with M \u00E2\u0089\u00A4 k(N \u00E2\u0088\u0092 1). Then it also satisfies a minimal incarnation with M \u00E2\u0089\u00A4 k(N \u00E2\u0088\u0092 1) since removing a string of p1 \u00E2\u0088\u0088 Pp2 , p2 \u00E2\u0088\u0088 Pp3 . . . pk\u00E2\u0088\u00921 \u00E2\u0088\u0088 Ppk , would decrease N by 1 and M by k leaving the inequality unchanged. Secondly we can assume that n also satisfies an incarnation where k(N \u00E2\u0088\u00922) < M \u00E2\u0089\u00A4 k(N \u00E2\u0088\u00921) since we can keep eliminating primes in the Li,2, which decrease N by 1, but M by at most k. This must eventually produce an incarnation where k(N \u00E2\u0088\u0092 2) < M \u00E2\u0089\u00A4 k(N \u00E2\u0088\u0092 1) since if we eliminate all primes in the Li,2 but 1, then M > k(N \u00E2\u0088\u0092 1). Also note that the condition mh,1 \u00E2\u0089\u00A4 mh\u00E2\u0088\u00921,1 +mh\u00E2\u0088\u00921,2 forces M \u00E2\u0089\u00A4 kN. If M is bounded between k(N \u00E2\u0088\u00922) and kN and the incarnation is minimal, we get that N is bounded by 2k since eliminating a prime in Li,2 can only shrink M by at most k \u00E2\u0088\u0092 1 since our incarnation is minimal. Therefore n satisifies an incarnation where N and hence M are bounded functions of k. Since there are only Ok(1) such incarnations, we get our result, noting that cM can be absorbed into the constant as well. Proof of Proposition 3.2. Let S = S(x) = \u00E2\u008B\u0083 q>yk Sq. Using Lemma 3.11 we have #S \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q>yk #Sq \u001C \u00E2\u0088\u0091 q>yk xyk q2 \u001C xyk \u00E2\u0088\u0091 q>yk 1 q2 \u001C xy k log(yk)yk \u001C x \u00CF\u0088(x) by (2.5). As for the n with n /\u00E2\u0088\u0088 S and a = \u00CE\u00BDq(\u00CF\u0086k(n)) > 1, the only remaining case is that M > k(N \u00E2\u0088\u0092 1). Recall that a = N + H \u00E2\u0088\u0092 1. If H = 1, then N = m1,2 = a. This implies m2,1 = a\u00E2\u0088\u0092 1 or a, since otherwise for k \u00E2\u0089\u00A5 2, M = \u00E2\u0088\u0091 h mh,1 \u00E2\u0089\u00A4 a+(k\u00E2\u0088\u00921)m2,1 \u00E2\u0089\u00A4 a+(k\u00E2\u0088\u00921)(a\u00E2\u0088\u00922) = k(a\u00E2\u0088\u00921)\u00E2\u0088\u0092k+2 \u00E2\u0089\u00A4 (k\u00E2\u0088\u00921)N leading to a contradiction. If H > 1, then we again wish to show that m2,1 \u00E2\u0089\u00A5 a\u00E2\u0088\u0092 k. M = \u00E2\u0088\u0091 h (mh,1 +mh,2) \u00E2\u0089\u00A4 km1,2 + (k \u00E2\u0088\u0092 1) \u00E2\u0088\u0091 h>1 mh,2 = m1,2 + (k \u00E2\u0088\u0092 1)N = k(N \u00E2\u0088\u0092 1)\u00E2\u0088\u0092N + k +m1,2 25 3.3. Large Primes Dividing \u00CF\u0086k(n) which implies m1,2 > N \u00E2\u0088\u0092 k and so \u00E2\u0088\u0091 h>1mh,2 = N \u00E2\u0088\u0092m1,1 < k. Therefore if m2,1 < a\u00E2\u0088\u0092 k, then M = \u00E2\u0088\u0091 h (mh,1 +mh,2) \u00E2\u0089\u00A4 m1,2 + (k \u00E2\u0088\u0092 1)m2,1 + (k \u00E2\u0088\u0092 1) \u00E2\u0088\u0091 h>1 mh,2 \u00E2\u0089\u00A4 a+ (k \u00E2\u0088\u0092 1)(a\u00E2\u0088\u0092 k \u00E2\u0088\u0092 1) + (k \u00E2\u0088\u0092 1)(k \u00E2\u0088\u0092 1) = ak \u00E2\u0088\u0092 2k \u00E2\u0089\u00A4 k(N \u00E2\u0088\u0092 1) as N > a again leading to a contradiction. Hence m2,1 \u00E2\u0089\u00A5 a \u00E2\u0088\u0092 k and so we conclude \u00E2\u0088\u0091 n/\u00E2\u0088\u0088S n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))>1 (\u00CE\u00BDq(\u00CF\u0086k(n)) log q \u00E2\u0089\u00A4 2 \u00E2\u0088\u0091 n/\u00E2\u0088\u0088S n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))>1 (\u00CE\u00BDq(\u00CF\u0086k(n))\u00E2\u0088\u0092 1) log q \u001C \u00E2\u0088\u0091 q>yk log q \u00E2\u0088\u0091 a\u00E2\u0089\u00A52 a \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x n/\u00E2\u0088\u0088S \u00CE\u00BDq(\u00CF\u0086k(n))=a 1. Unfortunately, just blindly using the Brun-Titchmarsh inequality in (2.10) won\u00E2\u0080\u0099t be good enough as we must sum over all a. Let g(a, k) = (a \u00E2\u0088\u0092 k)! if a \u00E2\u0089\u00A5 k or 1 otherwise and note that since we have m1,2 \u00E2\u0089\u00A5 a\u00E2\u0088\u0092 k, we have at least g(a, k) permutations of the same primes. Thus by using Lemma 3.9 we get a \u00E2\u0088\u0091 q>yk log q \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x n/\u00E2\u0088\u0088S \u00CE\u00BDq(\u00CF\u0086k(n))=a 1\u001C a x(cy) M qNg(a, k) \u001C ac k(a+k\u00E2\u0088\u00921)xy2k q2g(a, k) using the assumption that q > yk and M \u00E2\u0089\u00A4 kN \u00E2\u0089\u00A4 k(a + k \u00E2\u0088\u0092 1). Hence we get that our sum is \u00E2\u0088\u0091 n/\u00E2\u0088\u0088S n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q>yk \u00CE\u00BDq(\u00CF\u0086k(n))>1 (\u00CE\u00BDq(\u00CF\u0086k(n)) log q \u001C \u00E2\u0088\u0091 q>yk log q \u00E2\u0088\u0091 a\u00E2\u0089\u00A52 ack(a+k\u00E2\u0088\u00921)xy2k q2g(a, k) = xy2k \u00E2\u0088\u0091 q>yk log q q2 \u00E2\u0088\u0091 a\u00E2\u0089\u00A52 ack(a+k\u00E2\u0088\u00921) g(a, k) 26 3.4. Small Primes Dividing \u00CE\u00BBk(n) However the latter sum converges to some function depending on k, and so we get \u001C xy2k \u00E2\u0088\u0091 q>yk log q q2 \u001C xyk by (2.4). 3.4 Small Primes Dividing \u00CE\u00BBk(n) We now turn our attention to the bound involving \u00CE\u00BBk(n) in the summand. Just like when we were dealing with the number of cases where qa | \u00CF\u0086k(n), we will need a lemma to deal with the number of cases where qa | \u00CE\u00BBk(n). Fortunately this case is much simpler as the only two ways for qa | \u00CE\u00BB(n) is for qa+1 | n or for there to exist p | n with p \u00E2\u0088\u0088 Pqa . Note that these conditions aren\u00E2\u0080\u0099t sufficient, but are necessary when q = 2. Lemma 3.12. The number of positive integers n \u00E2\u0089\u00A4 x for which qa | \u00CE\u00BBk(n) is O(xy k qa ). Proof. We\u00E2\u0080\u0099ll proceed by induction on k. If k = 1, then qa | \u00CE\u00BB(n) if qa+1 | n or p \u00E2\u0088\u0088 Pqa with p | n. The number of such n is at most\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x qa+1|n 1 + \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x p\u00E2\u0088\u0088Pqa p|n 1\u001C x qa+1 + \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pqa x p \u001C x qa+1 + xy qa \u001C xy qa . using (2.10). Suppose the number of n \u00E2\u0089\u00A4 x for which qa | \u00CE\u00BBk\u00E2\u0088\u00921(n) is O(xy k\u00E2\u0088\u00921 qa ). If q a | \u00CE\u00BBk(n), then either qa+1 | \u00CE\u00BBk\u00E2\u0088\u00921(n) or p \u00E2\u0088\u0088 Pqa with p | \u00CE\u00BBk\u00E2\u0088\u00921(n). Hence the number of such n is bounded by \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x qa+1|\u00CE\u00BBk\u00E2\u0088\u00921(n) 1 + \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x p\u00E2\u0088\u0088Pqa p|\u00CE\u00BBk\u00E2\u0088\u00921(n) 1\u001C xy k\u00E2\u0088\u00921 qa+1 + \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pqa xyk\u00E2\u0088\u00921 p \u001C xy k\u00E2\u0088\u00921 qa+1 + xyk qa \u001C xy k qa as needed. Proof of Proposition 3.3. Like in the proof of previous propositions, we\u00E2\u0080\u0099ll show \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CE\u00BBk(n)) log q \u001C xyk. 27 3.5. Reduction to hk(n) for Small Primes The left hand side is equal to\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CE\u00BBk(n)) log q = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa|\u00CE\u00BBk(n) 1 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4yk 1 + \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa|\u00CE\u00BBk(n) qa>yk 1. The first sum is\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4yk 1 = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 m\u00E2\u0089\u00A4yk \u00CE\u009B(m)\u001C \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x yk \u001C xyk, using the definition of \u00CE\u009B(m) and equation (2.1). Using Lemma 3.12, the geometric estimate in (2.6) and equation (2.1) the second sum becomes \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa|\u00CE\u00BBk(n) qa>yk 1\u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa>yk xyk qa \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q xyk yk \u001C xyk. 3.5 Reduction to hk(n) for Small Primes The small primes dividing \u00CF\u0086k(n) are what contributes to the asymptotic term of log(n/\u00CE\u00BBk(n)). In this section we show that the important case is the supersquarefree case of p dividing \u00CF\u0086k(n) which is when p \u00E2\u0089\u00BA p1 \u00E2\u0089\u00BA p2 \u00E2\u0089\u00BA \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0089\u00BA pk, pk | n. For this reason we will approximate the sum \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk vq(\u00CF\u0086k(n)) log q with hk(n) = \u00E2\u0088\u0091 p1|n \u00E2\u0088\u0091 p2|p1\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(pk \u00E2\u0088\u0092 1) log q. (3.4) Proof of Proposition 3.5. For any fixed prime q, we know that vq(\u00CF\u0086(m)) = max{0, vq(m)\u00E2\u0088\u0092 1}+ \u00E2\u0088\u0091 p|m vq(p\u00E2\u0088\u0092 1), 28 3.5. Reduction to hk(n) for Small Primes which implies\u00E2\u0088\u0091 p|m vq(p\u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 vq(\u00CF\u0086(m)) \u00E2\u0089\u00A4 vq(m) + \u00E2\u0088\u0091 p|m vq(p\u00E2\u0088\u0092 1). Repeated use of this inequality for m = \u00CF\u0086l(n) where l ranges from k \u00E2\u0088\u0092 1 to 0 yields \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00921(n) vq(p\u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 vq(\u00CF\u0086k(n)) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00921(n) vq(p\u00E2\u0088\u0092 1) + \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00922(n) vq(p\u00E2\u0088\u0092 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ \u00E2\u0088\u0091 p|\u00CF\u0086(n) vq(p\u00E2\u0088\u0092 1) + vq(n). (3.5) A prime p divides \u00CF\u0086k\u00E2\u0088\u00921(n) either in the supersquarefree case (ssf), or not in the supersquarefree case (nssf), yielding \u00E2\u0088\u0091 ssf vq(p\u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00921(n) vq(p\u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 ssf vq(p\u00E2\u0088\u0092 1) + \u00E2\u0088\u0091 nssf vq(p\u00E2\u0088\u0092 1). Combining this inequality with (3.5) yields\u00E2\u0088\u0091 ssf vq(p\u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 vq(\u00CF\u0086k(n)) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 ssf vq(p\u00E2\u0088\u0092 1) + \u00E2\u0088\u0091 nssf vq(p\u00E2\u0088\u0092 1) + \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00922(n) vq(p\u00E2\u0088\u0092 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ \u00E2\u0088\u0091 p|\u00CF\u0086(n) vq(p\u00E2\u0088\u0092 1) + vq(n). Subtracting the sum over the supersquarefree case, multiplying through by log q and summing over q \u00E2\u0089\u00A4 yk yields 29 3.5. Reduction to hk(n) for Small Primes 0 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(\u00CF\u0086k(n)) log q \u00E2\u0088\u0092 hk(n) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 nssf vq(p\u00E2\u0088\u0092 1) log q + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00922(n) vq(p\u00E2\u0088\u0092 1) log q + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|n vq(p\u00E2\u0088\u0092 1) log q where we get hk(n) from (3.4). It suffices to show that the sum on the right side becomes our error term. For the sum \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|\u00CF\u0086m(n) vq(p\u00E2\u0088\u0092 1) log q = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|\u00CF\u0086m(n) \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa|p\u00E2\u0088\u00921 log q = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pqa p|\u00CF\u0086m(n) 1, we\u00E2\u0080\u0099ll split the sum over values of p \u00E2\u0089\u00A4 yk\u00E2\u0088\u00921 and p > yk\u00E2\u0088\u00921. For p \u00E2\u0089\u00A4 yk\u00E2\u0088\u00921 we uniformly get for all n that \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pqa p\u00E2\u0089\u00A4yk\u00E2\u0088\u00921 p|\u00CF\u0086m(n) 1 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N pi(yk\u00E2\u0088\u00921; qa, 1) \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N yk\u00E2\u0088\u00921 \u00CF\u0086(qa) \u001C yk\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q q \u001C yk\u00E2\u0088\u00921 log y using the geometric estimate (2.6) and the prime number theorem for arith- metic progressions. As for p > yk\u00E2\u0088\u00921 we fix an M and N from case 3 for which p | \u00CF\u0086m(n), of which there are at most Ok(1) such M,N since vp(\u00CF\u0086(m)) = 1. Therefore 30 3.5. Reduction to hk(n) for Small Primes \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 p>yk\u00E2\u0088\u00921 p\u00E2\u0088\u0088Pqa p|\u00CF\u0086m(n) 1\u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pqa p>yk\u00E2\u0088\u00921 xyM pN \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 p\u00E2\u0088\u0088Pqa xyM\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921) p \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N xyM\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921)+1 qa \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk xyM\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921)+1 log q q \u001C xyM\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921)+1 log yk \u001C xyM\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921)+1 log y. Since the M,N were chosen for \u00CF\u0086m(n) we know that M \u00E2\u0089\u00A4 mN where equal- ity holds if and only if we are in the supersquarefree case. Now either m \u00E2\u0089\u00A4 k \u00E2\u0088\u0092 2 or m = k \u00E2\u0088\u0092 1 and we are not in the supersquarefreecase. In the former case we have an error of O(xy(k\u00E2\u0088\u00922)N\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921)+1 log y) = O(xyk\u00E2\u0088\u0092N log y) = O(xyk\u00E2\u0088\u00921 log y) since N \u00E2\u0089\u00A5 1, or in the latter case O(xy(k\u00E2\u0088\u00921)N\u00E2\u0088\u00921\u00E2\u0088\u0092(k\u00E2\u0088\u00921)(N\u00E2\u0088\u00921)+1 log y) = O(xyk\u00E2\u0088\u00921 log y). Thus we get \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x ( \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 nssf vq(p\u00E2\u0088\u0092 1) log q + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00922(n) vq(p\u00E2\u0088\u0092 1) log q + . . . + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|n vq(p\u00E2\u0088\u0092 1) log q ) \u001C xyk\u00E2\u0088\u00921 log y and so 31 3.6. Reduction to the First and Second Moments \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 nssf vq(p\u00E2\u0088\u0092 1) log q + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|\u00CF\u0086k\u00E2\u0088\u00922(n) vq(p\u00E2\u0088\u0092 1) log q + . . . + \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 p|n vq(p\u00E2\u0088\u0092 1) log q \u001C yk\u00E2\u0088\u00921 log y \u00C2\u00B7 \u00CF\u0088(x) for almost all n \u00E2\u0089\u00A4 x as required. 3.6 Reduction to the First and Second Moments The Tura\u00CC\u0081n-Kubilius inequality, which is discussed further in the appendix, asserts that if f(n) is a complex strongly additive function, then there exists an absolute constant C such that\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x |f(n)\u00E2\u0088\u0092M1(x)|2 \u00E2\u0089\u00A4 CxM2(x) (3.6) where M1(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x|f(p)|/p and M2(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x|f(p)|2/p. Since hk(n) is strongly additive we apply this inequality where M1(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x hk(p)/p, M2(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x hk(p) 2/p. We will need to find bounds on M1 and M2 there- fore it\u00E2\u0080\u0099s our goal to prove the following two propositions: Proposition 3.13. For all x > ee e , M1(x) = 1 (k \u00E2\u0088\u0092 1)!y k log y +O(yk) Proposition 3.14. For all x > ee e , M2(x)\u001C y2k\u00E2\u0088\u00921 logk\u00E2\u0088\u00921 y. These will lead to a proof of Proposition 3.6. Proof of Proposition 3.6. Let N denote the number of n \u00E2\u0089\u00A4 x for which |hk(n) \u00E2\u0088\u0092M1(x)| > yk. The contribution of such n to the sum in (3.6) is at least Ny2k. Thus Proposition 3.14 implies N \u001C x logk\u00E2\u0088\u00921 y/y and so Propo- sition 3.13 implies that hk(n) = 1 (k\u00E2\u0088\u00921)!y k log y+O(yk) except for a set of size O(x(log y)k\u00E2\u0088\u00921/y). 32 3.7. Summations Involving pi(t, p, 1) 3.7 Summations Involving pi(t, p, 1) The proofs of Propositions 3.13 and 3.14 involve multiple summations over primes. Those sums can be re\u00E2\u0080\u0093written as sums including terms such as pi(t, p, 1). A lot of these summations will involve sieving techniques. This section will be split into proofs of two lemmas involving the summations required for the sums arising from the Propositions 3.13 and 3.14. Lemma 3.15. Let b, k, l be positive integers with 2 \u00E2\u0089\u00A4 l \u00E2\u0089\u00A4 k. Let t > ee be a real number and let constants \u00CE\u00B1, \u00CE\u00B11, \u00CE\u00B12 satisfy 0 < \u00CE\u00B1 < 1/2 and 0 < \u00CE\u00B11 < \u00CE\u00B12 < 1/2. (a) If b > t\u00CE\u00B1, then \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 pi(t; p2, 1)\u001C t log t(log log t) k\u00E2\u0088\u00922 b . (3.7) (b) If b \u00E2\u0089\u00A4 t\u00CE\u00B11 , then \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl>t \u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Ppl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 pi(t; p2, 1)\u001C b l\u00E2\u0088\u00921t \u00CF\u0086(b)l log t . (3.8) (c) If b \u00E2\u0089\u00A4 t\u00CE\u00B11 , then \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Ppl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 pi(t; p2, 1)\u001C t(log log t) l\u00E2\u0088\u00921 \u00CF\u0086(b) log t . (3.9) The implicit constants in (a)\u00E2\u0088\u0092 (c) depend on the choices of the \u00CE\u00B1. Proof. For (3.7) we just use the trivial estimate pi(t; p2, 1) \u00E2\u0089\u00A4 t/p2 and several 33 3.7. Summations Involving pi(t, p, 1) uses of Brun-Titchmarsh (2.10) to get\u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 pi(t; p2, 1) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 t p2 \u001C t \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088P4 log log t p3 \u001C t \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb (log log t)k\u00E2\u0088\u00922 pk \u00E2\u0089\u00A4 t \u00E2\u0088\u0091 m\u00E2\u0089\u00A11 (mod b) t\u00CE\u00B1\u00E2\u0089\u00A4m\u00E2\u0089\u00A4t (log log t)k\u00E2\u0088\u00922 m \u00E2\u0089\u00A4 t log t(log log t) k\u00E2\u0088\u00922 b where m > 1 and m \u00E2\u0089\u00A1 1 (mod b) imply that m > b and by using (2.7). As for (3.8) we get\u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb l>t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 pi(t; p2, 1) = \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb l>t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088P4 #{(m1, p2) : p2 = 1 (mod p3), p2 > t\u00CE\u00B12 , m1p2 + 1 \u00E2\u0089\u00A4 t, p2,m1p2 + 1 prime} = \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb l>t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p4\u00E2\u0088\u0088P5 #{(m1,m2, p3) : p3 = 1 (mod p4), p3 > t\u00CE\u00B12 , m1(m2p3 + 1) + 1 \u00E2\u0089\u00A4 t, {p3,m2p3 + 1,m1(m2p3 + 1) + 1} prime} = #{(m1,m2, . . . ,ml\u00E2\u0088\u00921, pl) : pl = 1 (mod b), pl > t\u00CE\u00B12 , m1(m2 . . . (ml\u00E2\u0088\u00922(ml\u00E2\u0088\u00921pl + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1 \u00E2\u0089\u00A4 t, {pl,ml\u00E2\u0088\u00921pl + 1, ml\u00E2\u0088\u00922(ml\u00E2\u0088\u00921pl + 1) + 1, . . . , m1(m2 . . . (ml\u00E2\u0088\u00922(ml\u00E2\u0088\u00921pl + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1} prime} \u00E2\u0089\u00A4 \u00E2\u0088\u0091 m1...ml\u00E2\u0088\u00921\u00E2\u0089\u00A4t1\u00E2\u0088\u0092\u00CE\u00B12 #{pl < t/m1 . . .ml\u00E2\u0088\u00921 : pl = 1 (mod b), {pl,ml\u00E2\u0088\u00921pl + 1,ml\u00E2\u0088\u00922(ml\u00E2\u0088\u00921pl + 1) + 1, . . . , m1(m2...(ml\u00E2\u0088\u00922(ml\u00E2\u0088\u00921pl + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1} prime}. 34 3.7. Summations Involving pi(t, p, 1) From here will need to use Brun\u00E2\u0080\u0099s Sieve method (see [12, Theorem 2.4]) to get that #{pl t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 pi(t; p2, 1)\u001C tb l\u00E2\u0088\u00921 \u00CF\u0086(b)l(log t)l (log t)l\u00E2\u0088\u00921 = tbl\u00E2\u0088\u00921 \u00CF\u0086(b)l log t . As for part (c), first note that b/\u00CF\u0086(b)\u001C log log b, so for pl > t\u00CE\u00B12 , we get that part (b) implies our bound. As for pl \u00E2\u0089\u00A4 t\u00CE\u00B12 we\u00E2\u0080\u0099ll split it into cases where p3 is less than or greater than t\u00CE\u00B12 . If p3 \u00E2\u0089\u00A4 t\u00CE\u00B12 , then 36 3.7. Summations Involving pi(t, p, 1) \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl\u00E2\u0089\u00A4t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 p2\u00E2\u0089\u00A4t\u00CE\u00B12 pi(t; p2, 1)\u001C \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl\u00E2\u0089\u00A4t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 p2\u00E2\u0089\u00A4t\u00CE\u00B12 t \u00CF\u0086(p2) log t/p2 \u001C \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl\u00E2\u0089\u00A4t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 p2\u00E2\u0089\u00A4t\u00CE\u00B12 t p2 log t \u001C \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb t(log log t)l\u00E2\u0088\u00922 pl log t \u001C t(log log t) l\u00E2\u0088\u00921 \u00CF\u0086(b) log t If p3 > t \u00CE\u00B12 , then since b \u00E2\u0089\u00A4 t\u00CE\u00B12 there is a minimum m such that pm \u00E2\u0089\u00A4 t\u00CE\u00B12 . So using part (b) with l = m we get \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl\u00E2\u0089\u00A4t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 p2>t\u00CE\u00B12 pi(t; p2, 1)\u001C \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl\u00E2\u0089\u00A4t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pm+1\u00E2\u0088\u0088Pm+2 (pm\u00E2\u0088\u00921)m\u00E2\u0088\u00921t \u00CF\u0086(pm\u00E2\u0088\u00921)m log t \u001C \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Pb pl\u00E2\u0089\u00A4t\u00CE\u00B12 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Pl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pm+1\u00E2\u0088\u0088Pm+2 t pm\u00E2\u0088\u00921 log t \u001C t(log log t) l\u00E2\u0088\u0092m \u00CF\u0086(b) log t \u001C t(log log t) l\u00E2\u0088\u00921 \u00CF\u0086(b) log t since m \u00E2\u0089\u00A5 2 and by using Brun-Titchmarsh (2.10) which finishes part (c) and the lemma. As for the summations requires for the second moment, we\u00E2\u0080\u0099ll note that we need twice as many sums due to hk(p) 2. However the techniques required are similar. Lemma 3.16. Let t > ee and 0 < 2\u00CE\u00B11 < \u00CE\u00B12 < 1/2. Then (a) If b1 > t \u00CE\u00B11 or b2 > t \u00CE\u00B11 then\u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pb1 r2\u00E2\u0088\u0088Pb2 pi(t; p2r2, 1)\u001C t log 2 t b1b2 . (3.10) 37 3.7. Summations Involving pi(t, p, 1) (b) If neither b1 nor b2 exceeds t \u00CE\u00B11 , then \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk>t \u00CE\u00B12 ... \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1)\u001C t(log log t) k\u00E2\u0088\u00921bk\u00E2\u0088\u009212 \u00CF\u0086(b1)\u00CF\u0086(b2)k log t + t(log log t)k\u00E2\u0088\u00921bk\u00E2\u0088\u009211 \u00CF\u0086(b2)\u00CF\u0086(b1)k log t . (3.11) (c) If neither b1 nor b2 exceeds t \u00CE\u00B11 , then \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 ... \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1)\u001C t(log log t) 2k\u00E2\u0088\u00922 \u00CF\u0086(b1)\u00CF\u0086(b2) log t . (3.12) (d) If neither b1 nor b2 exceeds t \u00CE\u00B11 , then \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 ... \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 \u00E2\u0088\u0091 s\u00E2\u0088\u0088Pp3\u00E2\u0088\u00A9Pr3 pi(t; s, 1)\u001C t(log log t) 2k\u00E2\u0088\u00922 \u00CF\u0086(b1)\u00CF\u0086(b2) log t . (3.13) Again the implicit constants depend on our choice of the \u00CE\u00B1. Proof. (a) is similar to part (a) of Lemma 3.15. For part (b) we first assume 38 3.7. Summations Involving pi(t, p, 1) that pk \u00E2\u0089\u00A4 rk, then\u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pk\u00E2\u0089\u00A4rk pkrk>t \u00CE\u00B12 ... \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1) = \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk>t \u00CE\u00B12 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 #{(m1, p2, r2) : p2 = 1 (mod p3), r2 = 1 (mod r3), r2p2 > t \u00CE\u00B12 ,m1r2p2 + 1 \u00E2\u0089\u00A4 t, p2,m1r2p2 + 1 prime} = \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 pk\u00E2\u0089\u00A4rk \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 \u00E2\u0088\u0091 rk\u00E2\u0088\u0088Pb2 pkrk>t \u00CE\u00B12 \u00E2\u0088\u0091 rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 r4\u00E2\u0088\u0088Pr5 #{(m1,m2, r3) : r3 = 1 (mod r4), r3p2 > t \u00CE\u00B12 ,m1p2(m2r3 + 1) + 1 \u00E2\u0089\u00A4 t, {r3,m2r3 + 1,m1p2(m2r3 + 1) + 1} prime} = \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 pk\u00E2\u0089\u00A4rk \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 #{(m1,m2, . . . ,ml\u00E2\u0088\u00921, rl) : rl = 1 (mod b2), p2rk > t \u00CE\u00B12 ,m1p2(m2 . . . (mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1 \u00E2\u0089\u00A4 t, {rk,mk\u00E2\u0088\u00921rk + 1,mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1, . . . , m1p2(m2 . . . (mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1} prime} \u00E2\u0089\u00A4 \u00E2\u0088\u0091 m1...ml\u00E2\u0088\u00921\u00E2\u0089\u00A4t1\u00E2\u0088\u0092\u00CE\u00B12 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 pk\u00E2\u0089\u00A4rk \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 #{rk < t/p2m1...mk\u00E2\u0088\u00921 : rk = 1 (mod b2), {rk,mk\u00E2\u0088\u00921rk + 1,mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1, . . . , p2m1(m2 . . . (mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1} prime} Just like in Lemma 3.15 we use Brun\u00E2\u0080\u0099s Sieve. However, notice that we have almost the same set, except with m1 replaced with m1p2. Hence we have #{rk < t/p2m1 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7k\u00E2\u0088\u00921 : rk = 1 (mod b1), {rk,mk\u00E2\u0088\u00921rk + 1,mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1, . . . , p2m1(m2 . . . (mk\u00E2\u0088\u00922(mk\u00E2\u0088\u00921rk + 1) + 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ 1} prime} \u001C E k\u00E2\u0088\u00921 \u00CF\u0086(E)k\u00E2\u0088\u00921 bk\u00E2\u0088\u009212 \u00CF\u0086(b2)k\u00E2\u0088\u00921 b2c1 . . . ck\u00E2\u0088\u00921 \u00CF\u0086(b2c1 . . . ck\u00E2\u0088\u00921) t/p2m1 . . .mk\u00E2\u0088\u00921b2 (log t/p2m1 . . .mk\u00E2\u0088\u00921b2)k 39 3.7. Summations Involving pi(t, p, 1) where the ci and E are E = p2 ( l\u00E2\u0088\u00921\u00E2\u0088\u008F i=1 m i(i+1)/2 i ) (1 + p2m1 + p2m1m2 + ...+ p2m1 . . .mk\u00E2\u0088\u00923) (1 +m2 +m2m3 + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+m2 . . .mk\u00E2\u0088\u00923) . . . (1 +mk\u00E2\u0088\u00923) (1 + p2m1 + p2m1m2 + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ p2m1 . . .mk\u00E2\u0088\u00924)(1 +m2 +m2m3 + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+m2 . . .mk\u00E2\u0088\u00924) . . . (1 +mk\u00E2\u0088\u00924) . . . (1 + p2m1) and for 2 \u00E2\u0089\u00A4 i \u00E2\u0089\u00A4 k \u00E2\u0088\u0092 2, c1 = 1 + p2m1 + p2m1m2 + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+ p2m1 . . .mk\u00E2\u0088\u00922, ci = 1 +mi +mimi+1 + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7+mi . . .mk\u00E2\u0088\u00922, ck\u00E2\u0088\u00921 = 1. By the same methods as Lemma 3.15, using that p2/\u00CF\u0086(p2) is bounded and noting that t p2m1...mk\u00E2\u0088\u00921b2 > rk b1 > t\u00CE\u00B12/2\u00E2\u0088\u0092\u00CE\u00B11 = t\u000F for some \u000F > 0 since \u00CE\u00B12 > 2\u00CE\u00B11, we get that \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk>t \u00CE\u00B12 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1)\u001C tb k\u00E2\u0088\u00921 2 \u00CF\u0086(b2)k log t \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Pk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088P3 1 p2 \u001C tb k\u00E2\u0088\u00921 2 \u00CF\u0086(b2)k log t \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 (log log t)k\u00E2\u0088\u00922 pk \u001C t(log log t) k\u00E2\u0088\u00921bk\u00E2\u0088\u009212 \u00CF\u0086(b1)\u00CF\u0086(b2)k log t . The case for rk \u00E2\u0089\u00A4 pk is similar. As for part (c), first note that bi/\u00CF\u0086(bi) \u001C log log bi for i \u00E2\u0088\u0088 {1, 2}. taking care of the case where pkrk > t\u00CE\u00B12 . As for 40 3.8. Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk pkrk \u00E2\u0089\u00A4 t\u00CE\u00B12 we get\u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk\u00E2\u0089\u00A4t\u00CE\u00B12 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1)\u001C \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk\u00E2\u0089\u00A4t\u00CE\u00B12 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 t \u00CF\u0086(p2r2) log t/p2r2 \u001C \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk\u00E2\u0089\u00A4t\u00CE\u00B12 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 t p2r2 log t \u001C \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pb1 rk\u00E2\u0088\u0088Pb2 pkrk\u00E2\u0089\u00A4t\u00CE\u00B12 t(log log t)2k\u00E2\u0088\u00924 pkrk log t \u001C t(log log t) 2k\u00E2\u0088\u00922 \u00CF\u0086(b1)\u00CF\u0086(b2) log t using Brun-Titchmarsh (2.10), finishing part (c). As for part (d) we note that\u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 \u00E2\u0088\u0091 s\u00E2\u0088\u0088Pp3\u00E2\u0088\u00A9Pr3 pi(t; s, 1) = \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 #{(m1, s) : s = 1 (mod p3r3),m1s+ 1 \u00E2\u0089\u00A4 t, s,m1s+ 1 prime} = \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 #{(m1,m2, r3) : r3 = 1 (mod r4),m1(m2p3r3 + 1) + 1 \u00E2\u0089\u00A4 t, {m2p3r3 + 1,m1(m2p3r3 + 1) + 1 prime} and so on, yielding a similar sieve as part (b). 3.8 Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk We will be using Euler Summation on the sum \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) in our efforts to find our estimate for M1(x). It will turn out that the large primes do not contribute much to the sum. The sum will involve estimating pi(t; p, 1) by li(t)/p\u00E2\u0088\u0092 1. The following lemma will deal with those errors and will involve the Bombieri\u00E2\u0080\u0093Vinogradov Theorem (2.13). 41 3.8. Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk Lemma 3.17. For all 2 \u00E2\u0089\u00A4 l \u00E2\u0089\u00A4 k, x > eee and v > ee,\u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 ( pi(v, pk\u00E2\u0088\u0092l+2, 1) \u00E2\u0088\u0092 li(v) pk\u00E2\u0088\u0092l+2 ) \u001C v log y log v + li(v)(log log v)l\u00E2\u0088\u00922. Proof. Let E(t; r, 1) = pi(t; r, 1)\u00E2\u0088\u0092 li(t)r\u00E2\u0088\u00921 . Then we have\u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 . . . \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 ( pi(v, pk\u00E2\u0088\u0092l+2, 1)\u00E2\u0088\u0092 li(v) pk\u00E2\u0088\u0092l+2 \u00E2\u0088\u0092 1 ) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 E(v; pk\u00E2\u0088\u0092l+2, 1) \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)|. Let \u00E2\u0084\u00A6(m) denote the number of divisors of m which are primes or prime powers. We use the estimate \u00E2\u0084\u00A6(m)\u001C logm to get 42 3.8. Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)| \u00E2\u0089\u00A4 log(yk) \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)| \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3|pk\u00E2\u0088\u0092l+2\u00E2\u0088\u00921 p3\u00E2\u0089\u00A4v1/9 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+4|pk\u00E2\u0088\u0092l+3\u00E2\u0088\u00921 pk\u00E2\u0088\u0092l+4\u00E2\u0089\u00A4v1/27 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa|pk\u00E2\u0088\u00921 1 \u00E2\u0089\u00A4 log(yk) \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)| \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3|pk\u00E2\u0088\u0092l+2\u00E2\u0088\u00921 p3\u00E2\u0089\u00A4v1/9 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+4|pk\u00E2\u0088\u0092l+3\u00E2\u0088\u00921 pk\u00E2\u0088\u0092l+4\u00E2\u0089\u00A4v1/27 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4v1/3k\u00E2\u0088\u00921 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0084\u00A6(pk \u00E2\u0088\u0092 1) \u001C log y \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)| \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3|pk\u00E2\u0088\u0092l+2\u00E2\u0088\u00921 p3\u00E2\u0089\u00A4v1/9 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+4|pk\u00E2\u0088\u0092l+3\u00E2\u0088\u00921 pk\u00E2\u0088\u0092l+4\u00E2\u0089\u00A4v1/27 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4v1/3k\u00E2\u0088\u00921 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 log v. Continuing in this manner we obtain\u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)| \u001C log y(log v)l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 |E(v; pk\u00E2\u0088\u0092l+2, 1)| \u001C v log y log v using Bombieri\u00E2\u0080\u0093Vinogradov (2.13). As for the difference between\u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 li(v) pk\u00E2\u0088\u0092l+2 \u00E2\u0088\u0092 1 43 3.8. Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk and \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 li(v) pk\u00E2\u0088\u0092l+2 (3.14) we get that it is\u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 li(v) pk\u00E2\u0088\u0092l+2(pk\u00E2\u0088\u0092l+2 \u00E2\u0088\u0092 1) \u00E2\u0089\u00A4 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u009E\u00E2\u0088\u0091 i=1 li(v) (ipk\u00E2\u0088\u0092l+3 + 1)(ipk\u00E2\u0088\u0092l+3) \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+4 pk\u00E2\u0088\u0092l+3\u00E2\u0089\u00A4v1/9 li(v) p2k\u00E2\u0088\u0092l+3 \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+4 pk\u00E2\u0088\u0092l+3\u00E2\u0089\u00A4v1/9 li(v) pk\u00E2\u0088\u0092l+3qa \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N li(v)(log log v)l\u00E2\u0088\u00922 q2a \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk li(v)(log log v)l\u00E2\u0088\u00922 log q q2 \u001C li(v)(log log v)l\u00E2\u0088\u00922. The estimate used the Brun\u00E2\u0080\u0093Titchmarsh inequality (2.10), the inequality pk\u00E2\u0088\u0092l+3 \u00E2\u0089\u00A5 qa and noting that the sum over q converges. Lemma 3.18. For all x > ee e and t > ee,\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 p2\u00E2\u0089\u00A4t1/3 pi(t; p2, 1) +O ( t1\u00E2\u0088\u00921/3 k log t(log log t)k\u00E2\u0088\u00922yk + t(log log t)k\u00E2\u0088\u00922 log y log t ) . 44 3.8. Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk Proof. For a prime p, hk(p) = \u00E2\u0088\u0091 p1|p \u00E2\u0088\u0091 p2|p1\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(pk \u00E2\u0088\u0092 1) log q = \u00E2\u0088\u0091 p2|p\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(pk \u00E2\u0088\u0092 1) log q since the only prime which can divide p is p itself. Hence \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t \u00E2\u0088\u0091 p2|p\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(pk \u00E2\u0088\u0092 1) log q = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t \u00E2\u0088\u0091 p2|p1\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa a\u00E2\u0088\u0088N log q = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t p\u00E2\u0088\u0088Pp2 1 = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 pi(t; p2, 1). We wish to approximate pi(t; p2, 1) by li(t) p2\u00E2\u0088\u00921 and use the Bombieri-Vinogradov Theorem to deal with the error. However this approximation only allows primes up to say t1/3. So we use the estimations in Lemma 3.15 to bound these errors. We will see that the main contribution comes from pi \u00E2\u0089\u00A4 t1/3i\u00E2\u0088\u00921 and qa \u00E2\u0089\u00A4 t1/3k . Using Lemma 3.15, we get for large qa \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa>t1/3 k \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp2 pi(t; p2, 1) \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa>t1/3 k t log t(log log t)k\u00E2\u0088\u00922 qa . By geometric estimates, if a\u00E2\u0088\u0097 is the smallest a where qa > t1/3k , then we get that the above is bounded by 45 3.8. Reduction of \u00E2\u0088\u0091 hk(p) to Small Values of pk O ( t log t(log log t)k\u00E2\u0088\u00922 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q qa\u00E2\u0088\u0097 ) \u001C t1\u00E2\u0088\u00921/3k log t(log log t)k\u00E2\u0088\u00922 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u001C t1\u00E2\u0088\u00921/3k log t(log log t)k\u00E2\u0088\u00922yk. Now suppose qa \u00E2\u0089\u00A4 t1/3k . Let l be the last index (supposing one exists) where pi > t 1/3i\u00E2\u0088\u00921 By using (3.8) where l ranges from 2 to k, we can bound the large values of the pi. \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4t1/3k \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pl+1\u00E2\u0088\u0088Ppl+2 pl+1\u00E2\u0089\u00A4t1/3l \u00E2\u0088\u0091 pl\u00E2\u0088\u0088Ppl+1 pl>t 1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pl\u00E2\u0088\u00921\u00E2\u0088\u0088Ppl \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 pi(t; p2, 1) \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4t1/3k \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pl+2\u00E2\u0088\u0088Ppl+3 pl+2\u00E2\u0089\u00A4t1/3l+1 \u00E2\u0088\u0091 pl+1\u00E2\u0088\u0088Ppl+2 pl+1>t 1/3l pl\u00E2\u0088\u00921l+1t \u00CF\u0086(pl+1)l log t \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4t1/3k \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pl+2\u00E2\u0088\u0088Ppl+3 pl+2\u00E2\u0089\u00A4t1/3l+1 \u00E2\u0088\u0091 pl+1\u00E2\u0088\u0088Ppl+2 pl+1>t 1/3l t pl+1 log t since pl is prime and l \u00E2\u0089\u00A4 k. By Brun-Titchmarsh (2.10) we get \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4t1/3k t(log log t)k\u00E2\u0088\u0092l qa log t \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk t(log log t)k\u00E2\u0088\u0092l log q q log t \u001C t(log log t) k\u00E2\u0088\u00922 log y log t 46 3.9. Evaluation of the Main Term by (2.3) and since l \u00E2\u0089\u00A5 2. Hence we get\u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N qa\u00E2\u0089\u00A4t1/3k \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4t1/3k\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 p2\u00E2\u0089\u00A4t1/3 pi(t, p2, 1) +O ( t1\u00E2\u0088\u00921/3 k log t(log log t)k\u00E2\u0088\u00922yk + t(log log t)k\u00E2\u0088\u00922 log y log t ) finishing the lemma. 3.9 Evaluation of the Main Term Now we\u00E2\u0080\u0099ll deal with the main term from Lemma 3.18. We will deal with estimating the individual sums recursively. Hence we wish to make the following definition. Definition 3.19. Let 2 \u00E2\u0089\u00A4 l \u00E2\u0089\u00A4 k and 2 \u00E2\u0089\u00A4 u \u00E2\u0089\u00A4 t. Then define gk,l(u) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4u1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4u1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4u1/3 pi(u; pk\u00E2\u0088\u0092l+2, 1). Note that gk,k(t) is the summation in Lemma 3.18. Next we\u00E2\u0080\u0099ll exhibit a recursive formula satisfied by the gk,l. Lemma 3.20. Let 3 \u00E2\u0089\u00A4 l \u00E2\u0089\u00A4 k, then gk,l(v) = li(v) \u00E2\u0088\u00AB v1/3 2 1 u2 gk,l\u00E2\u0088\u00921(u)du+O ( v(log log v)l\u00E2\u0088\u00922 log y log v ) . (3.15) Proof. We\u00E2\u0080\u0099ll proceed by approximating pi by li and then use partial summa- tion to recover pi. Using Lemma 3.17 we get gk,l(v) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 pi(v; pk\u00E2\u0088\u0092l+2, 1) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 li(v) pk\u00E2\u0088\u0092l+2 +O ( v log y log v + li(v)(log log v)l\u00E2\u0088\u00922 ) . 47 3.9. Evaluation of the Main Term We use Euler summation on the inner sum to get \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+2\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+3 pk\u00E2\u0088\u0092l+2\u00E2\u0089\u00A4v1/3 1 pk\u00E2\u0088\u0092l+2 = pi(v1/3; pk\u00E2\u0088\u0092l+3, 1) v1/3 + \u00E2\u0088\u00AB v1/3 2 pi(u; pk\u00E2\u0088\u0092l+3, 1) u2 du. Our function then becomes gk,l(v) = li(v) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 . . . \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+4 pk\u00E2\u0088\u0092l+3\u00E2\u0089\u00A4v1/3 ( pi(v1/3; pk\u00E2\u0088\u0092l+3, 1) v1/3 + \u00E2\u0088\u00AB v1/3 2 pi(u; pk\u00E2\u0088\u0092l+3, 1) u2 du ) +O ( v log y log v + li(v)(log log v)l\u00E2\u0088\u00922 ) . We trivially estimate pi(x; q, 1) by x/q inside the sum and then use Brun\u00E2\u0080\u0093 Titchmarsh (2.10) to get \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+4 pk\u00E2\u0088\u0092l+3\u00E2\u0089\u00A4v1/3 pi(v1/3; pk\u00E2\u0088\u0092l+3, 1) v1/3 \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00921 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk pk\u00E2\u0088\u00921\u00E2\u0089\u00A4v1/3l\u00E2\u0088\u00922 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk\u00E2\u0088\u0092l+3\u00E2\u0088\u0088Ppk\u00E2\u0088\u0092l+4 pk\u00E2\u0088\u0092l+3\u00E2\u0089\u00A4v1/3 1 pk\u00E2\u0088\u0092l+3 \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N (log log v)l\u00E2\u0088\u00922 qa \u001C \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q (log log v)l\u00E2\u0088\u00922 q \u001C (log log v)l\u00E2\u0088\u00922 log y. Multiplying through by li(v) finishes the lemma. We now require a lemma to find the asymptotic formula for hk using the previous recurrence relation. 48 3.9. Evaluation of the Main Term Lemma 3.21. Let 2 \u00E2\u0089\u00A4 l \u00E2\u0089\u00A4 k. gk,l(u) = ku(log log u)l\u00E2\u0088\u00921 log y (l \u00E2\u0088\u0092 1)! log u +O ( u(log log u)l\u00E2\u0088\u00921 log u + u(log log u)l\u00E2\u0088\u00922 log2 y log u ) which implies \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) = kt(log log t)k\u00E2\u0088\u00921 log y (k \u00E2\u0088\u0092 1)! log t +O ( t(log log t)k\u00E2\u0088\u00921 log t + t(log log t)k\u00E2\u0088\u00922 log2 y log t + t1\u00E2\u0088\u00921/3 k log t(log log t)k\u00E2\u0088\u00922yk ) . Proof. The second formula is derived from the first by setting l = k, u = t and using Lemma 3.18. We\u00E2\u0080\u0099ll proceed with the first formula by induction on l. Using the estimates we obtained via Bombieri\u00E2\u0080\u0093Vinogradov (2.13) in Lemma 3.17, we have for l = 2 gk,2(u) = \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4u1/3 pi(u; pk, 1) = li(u) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa pk\u00E2\u0089\u00A4u1/3 1 pk +O ( li(u) + u log y log u ) . We then use (2.12) and log log(u1/3) = log log u+O(1) 49 3.9. Evaluation of the Main Term to get gk,2(u) = li(u) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N ( log log u1/3 \u00CF\u0086(qa) +O ( log(qa) \u00CF\u0086(qa) )) +O ( u log y log u ) = li(u)(log log u+O(1)) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N ( 1 qa +O ( 1 qa+1 )) +O ( li(u) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log2 q \u00E2\u0088\u0091 a\u00E2\u0088\u0088N a qa ) +O ( u log y log u ) = li(u)(log log u+O(1)) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk ( log q q +O ( log q q2 )) +O ( li(u) \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log2 q q + u log y log u ) = li(u) log log u log(yk) +O ( li(u)(log y + log log u+ log2 y) + u log y log u ) = ku log log u log y log u +O ( u log log u log u + u log2 y log u ) , using equation (2.3), completing the base case. Now using Lemma 3.20 we get gk,l(v) = li(v) \u00E2\u0088\u00AB v1/3 2 1 u2 gk,l\u00E2\u0088\u00921(u)du+O ( v(log log v)l\u00E2\u0088\u00922 log y log v ) = li(v) \u00E2\u0088\u00AB v1/3 2 1 u2 ( ku(log log u)l\u00E2\u0088\u00922 log y (l \u00E2\u0088\u0092 2)! log u +O ( u(log log u)l\u00E2\u0088\u00922 log u + u(log log u)l\u00E2\u0088\u00923 log2 y log u )) du+O ( v(log log v)l\u00E2\u0088\u00922 log y log v ) = li(v) \u00E2\u0088\u00AB v1/3 2 ( k(log log u)l\u00E2\u0088\u00922 log y (l \u00E2\u0088\u0092 2)!u log u +O ( (log log u)l\u00E2\u0088\u00922 u log u + (log log u)l\u00E2\u0088\u00923 log2 y u log u )) du+O ( v(log log v)l\u00E2\u0088\u00922 log y log v ) = k li(v)(log log v1/3)l\u00E2\u0088\u00921 log y (l \u00E2\u0088\u0092 1)! +O ( li(v)(log log v1/3)l\u00E2\u0088\u00921 + li(v)(log log v1/3)l\u00E2\u0088\u00922 log2 y + v(log log v)l\u00E2\u0088\u00922 log y log v ) . 50 3.10. The Proof of the First Moment Once again by using log log v1/3 = log log v +O(1) we get kv(log log v)l\u00E2\u0088\u00921 log y (l \u00E2\u0088\u0092 1)! log v +O ( v(log log v)l\u00E2\u0088\u00921 log v + v(log log v)l\u00E2\u0088\u00922 log2 y log v + v(log log v)l\u00E2\u0088\u00922 log y log v ) = kv(log log v)l\u00E2\u0088\u00921 log y (l \u00E2\u0088\u0092 1)! log v +O ( v(log log v)l\u00E2\u0088\u00921 log v + v(log log v)l\u00E2\u0088\u00922 log2 y log v ) , completing the induction. 3.10 The Proof of the First Moment We now are in a position to prove the proposition for the first moment. Proof of Proposition 3.13. M1(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x hk(p) p = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4ee hk(p) p + \u00E2\u0088\u0091 ee 0. Proof. Our sum is\u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 \u00E2\u0088\u0091 s\u00E2\u0088\u0088Pp3\u00E2\u0088\u00A9Pr3 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t p\u00E2\u0088\u0088Ps 1 = \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 \u00E2\u0088\u0091 s\u00E2\u0088\u0088Pp3r3 pi(t; s, 1). We split up into two cases. If qa11 q a2 2 > t \u00CE\u00B1, then suppose qa11 > t \u00CE\u00B1/2. (the other case is analogous) Thus p3r3 > t \u00CE\u00B1/2. Hence Lemma 3.15 part (a) yields\u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 >t \u00CE\u00B1 2 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 \u00E2\u0088\u0091 s\u00E2\u0088\u0088Pp3r3 pi(t; s, 1) \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 >t \u00CE\u00B1 2 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 t log t p3r3 \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 >t \u00CE\u00B1 2 t log t(log log t)2k\u00E2\u0088\u00924 q\u00CE\u00B111 q \u00CE\u00B12 2 . using Brun\u00E2\u0080\u0093Titchmarsh (2.10). By letting A = min{a|qa11 > t \u00CE\u00B1 2 } we get \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 t log t(log log t)2k\u00E2\u0088\u00924 qA1 q2 \u00E2\u0089\u00A4 t1\u00E2\u0088\u0092\u00CE\u00B12 log t(log log t)2k\u00E2\u0088\u00924 \u00E2\u0088\u0091 q1\u00E2\u0089\u00A4yk log q1 \u00E2\u0088\u0091 q2\u00E2\u0089\u00A4yk log q2 q2 \u001C t1\u00E2\u0088\u0092\u000Fyk log y 53 3.11. The Proof of the Second Moment by equations (2.1) and (2.3). If qa11 q a2 2 \u00E2\u0089\u00A4 t\u00CE\u00B1, then by Lemma 3.16 part (d) we get\u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 q a2 2 \u00E2\u0089\u00A4t\u00CE\u00B1 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 \u00E2\u0088\u0091 s\u00E2\u0088\u0088Pp3r3 pi(t; s, 1) \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 q a2 2 \u00E2\u0089\u00A4t\u00CE\u00B1 t(log log t)2k\u00E2\u0088\u00922 qa11 q a2 2 log t \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 t(log log t)2k\u00E2\u0088\u00922 q1q2 log t = t(log log t)2k\u00E2\u0088\u00922 log t ( \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk log q q )2 \u001C t(log log t) 2k\u00E2\u0088\u00922 log t log2 y by (2.3), completing the lemma. We now have enough to finish the second moment which is the final piece of the puzzle. Proof of Proposition 3.14. \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) 2 = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x (\u00E2\u0088\u0091 p1|p \u00E2\u0088\u0091 p2|p1\u00E2\u0088\u00921 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 pk|pk\u00E2\u0088\u00921\u00E2\u0088\u00921 \u00E2\u0088\u0091 q\u00E2\u0089\u00A4yk \u00CE\u00BDq(pk \u00E2\u0088\u0092 1) log q )2 = \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t p\u00E2\u0088\u0088Pp2 p\u00E2\u0088\u0088Pr2 1 since the condition p1 | p only occurs if p1 = p. We then split up the sum according to whether or not p2 = r2. Lemma 3.22 deals with the part where s = p2 = r2 leaving us with 54 3.11. The Proof of the Second Moment \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk ... \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 p2 6=r2 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t p\u00E2\u0088\u0088Pp2 p\u00E2\u0088\u0088Pr2 1 +O ( t1\u00E2\u0088\u0092\u000Fyk log y + t(log log t)2k\u00E2\u0088\u00922 log t log2 y ) . The sum becomes\u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1). If qa11 > t \u00CE\u00B11 , then so is p2, and hence by (3.10) we get \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 >t \u00CE\u00B11 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p3\u00E2\u0088\u0088Pp4 r3\u00E2\u0088\u0088Pr4 t log2 t p3r3 \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 >t \u00CE\u00B11 t log2 t(log log t)2k\u00E2\u0088\u00924 qa11 q a2 2 \u001C t1\u00E2\u0088\u0092\u00CE\u00B11 log2 t(log log t)2k\u00E2\u0088\u00924 \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a2\u00E2\u0088\u0088N 1 qa22 \u001C t1\u00E2\u0088\u0092\u00CE\u00B11 log2 t(log log t)2k\u00E2\u0088\u00924 \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 q2 \u001C t1\u00E2\u0088\u0092\u00CE\u00B11 log2 t(log log t)2k\u00E2\u0088\u00924(yk log y). We similarly get the same bound if qa22 > t \u00CE\u00B11 . If neither of qa11 , q a2 2 exceed t\u00CE\u00B11 , then by (3.12) and using that for bi = q ai i bi \u00CF\u0086(bi) \u001C 1, 1 \u00CF\u0086(bi) \u001C 1 bi , 55 3.11. The Proof of the Second Moment we get \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 ,q a2 2 \u00E2\u0089\u00A4t\u00CE\u00B11 \u00E2\u0088\u0091 pk\u00E2\u0088\u0088Pqa11 rk\u00E2\u0088\u0088Pqa22 \u00E2\u0088\u0091 pk\u00E2\u0088\u00921\u00E2\u0088\u0088Ppk rk\u00E2\u0088\u00921\u00E2\u0088\u0088Prk . . . \u00E2\u0088\u0091 pi\u00E2\u0088\u0088Ppi+1 ri\u00E2\u0088\u0088Pri+1 \u00E2\u0088\u0091 pi\u00E2\u0088\u00921\u00E2\u0088\u0088Ppi ri\u00E2\u0088\u00921\u00E2\u0088\u0088Pri \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0088\u0091 p2\u00E2\u0088\u0088Pp3 r2\u00E2\u0088\u0088Pr3 pi(t; p2r2, 1) \u001C \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 \u00E2\u0088\u0091 a1,a2\u00E2\u0088\u0088N q a1 1 ,q a2 2 \u00E2\u0089\u00A4t\u00CE\u00B11 t(log log t)2k\u00E2\u0088\u00922 qa11 q a2 2 log t \u001C t(log log t) 2k\u00E2\u0088\u00922 log t \u00E2\u0088\u0091 q1,q2\u00E2\u0089\u00A4yk log q1 log q2 q1q2 \u001C t(log log t) 2k\u00E2\u0088\u00922 log2 y log t . The above gives us \u00E2\u0088\u0091 p\u00E2\u0089\u00A4t hk(p) 2 \u001C t1\u00E2\u0088\u0092\u000Fyk log y + t(log log t) 2k\u00E2\u0088\u00922 log2 y log t . Using partial summation we have M2(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x hk(p) 2 p = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4ee hk(p) 2 p + 1 x \u00E2\u0088\u0091 ee\u00E2\u0089\u00A4p\u00E2\u0089\u00A4x hk(p) 2 + \u00E2\u0088\u00AB x ee dt t2 \u00E2\u0088\u0091 ee\u00E2\u0089\u00A4p\u00E2\u0089\u00A4t hk(p) 2 \u001C 1 + 1 x ( x1\u00E2\u0088\u0092\u000Fyk log y + x(log log x)2k\u00E2\u0088\u00922 log2 y log x ) + \u00E2\u0088\u00AB x ee ( t\u00E2\u0088\u00921\u00E2\u0088\u0092\u000Fyk log y + (log log t)2k\u00E2\u0088\u00922 log2 y t log t ) dt \u001C y 2k\u00E2\u0088\u00922 log2 y log x + x\u00E2\u0088\u0092\u000Fyk log y + (log log x)2k\u00E2\u0088\u00921 log2 y \u001C y2k\u00E2\u0088\u00921 log2 y completing the proof of Proposition 3.14 and hence Theorem 1.4. 56 Chapter 4 Iterates Between \u00CF\u0086 and \u00CE\u00BB We now turn our attention to the proof of Theorem 1.5. It will be necessary to use the following upper bound for the Carmichael function of a product. Lemma 4.1. Let a, b be natural numbers, then \u00CE\u00BB(ab) \u00E2\u0089\u00A4 b\u00CE\u00BB(a). (4.1) Proof. We first note that it suffices to show the inequality whenever b is prime, because if b = p1 . . . pk where the pi are not necessarily distinct, then repeated use of the theorem where b is prime yields \u00CE\u00BB(ab) = \u00CE\u00BB(ap1 . . . pk) \u00E2\u0089\u00A4 p1\u00CE\u00BB(ap2 . . . pk) \u00E2\u0089\u00A4 \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0089\u00A4 p1 . . . pk\u00CE\u00BB(a) = b\u00CE\u00BB(a). If b is a prime which divides a, then for some e > 0 a = bepe11 . . . p ek k and ab = b e+1pe11 . . . p ek k . Therefore \u00CE\u00BB(ab) = lcm ( \u00CE\u00BB(be+1), \u00CE\u00BB(pe11 ), . . . , \u00CE\u00BB(p ek k ) ) \u00E2\u0089\u00A4 lcm ( b\u00CE\u00BB(be), \u00CE\u00BB(pe11 ), . . . , \u00CE\u00BB(p ek k ) ) \u00E2\u0089\u00A4 b \u00E2\u0088\u0097 lcm ( \u00CE\u00BB(be), \u00CE\u00BB(pe11 ), . . . , \u00CE\u00BB(p ek k ) ) = b\u00CE\u00BB(a) where the first inequality is in fact an equality if be = 4. (Also note that in this case, it would not be hard to show that \u00CE\u00BB(ab) | b\u00CE\u00BB(a).) If (a, b) = 1, then e = 0 and 57 Chapter 4. Iterates Between \u00CF\u0086 and \u00CE\u00BB \u00CE\u00BB(ab) = lcm ( b\u00E2\u0088\u0092 1, \u00CE\u00BB(pe11 ), . . . , \u00CE\u00BB(pekk ) ) \u00E2\u0089\u00A4 (b\u00E2\u0088\u0092 1) lcm ( \u00CE\u00BB(pe11 ), . . . , \u00CE\u00BB(p ek k ) ) < b\u00CE\u00BB(a), ending the proposition. Suppose that g(n) is an arithmetic function of the form \u00CF\u0086(h(n)) where h(n) is a (k \u00E2\u0088\u0092 1)\u00E2\u0080\u0093fold iterate involving \u00CF\u0086 and \u00CE\u00BB. Note that if a | b, then \u00CE\u00BB(a) | \u00CF\u0086(b) since \u00CE\u00BB(a) | \u00CF\u0086(a) | \u00CF\u0086(ma) for anym. More easily we see \u00CE\u00BB(a) | \u00CE\u00BB(b) and \u00CF\u0086(a) | \u00CF\u0086(b). Inductively we can therefore show \u00CE\u00BBk(n) | g(n). Thus we can use equation (4.1) to get \u00CE\u00BBl+k(n) \u00E2\u0089\u00A4 \u00CE\u00BBl(g(n)) = \u00CE\u00BBl ( g(n) \u00CE\u00BBk(n) \u00CE\u00BBk(n) ) \u00E2\u0089\u00A4 \u00CE\u00BBl+k(n) g(n) \u00CE\u00BBk(n) . Since g(n) \u00E2\u0089\u00A4 n we have that g(n) \u00CE\u00BBk(n) \u00E2\u0089\u00A4 n \u00CE\u00BBk(n) = exp ( 1 (k \u00E2\u0088\u0092 1)!(1 + ok(1))(log log n) k log log log n ) by Theorem 1.4 for almost all n. Hence \u00CE\u00BBl+k(n) \u00E2\u0089\u00A4 \u00CE\u00BBl(g(n)) \u00E2\u0089\u00A4 \u00CE\u00BBl ( g(n) \u00CE\u00BBk(n) \u00CE\u00BBk(n) ) \u00E2\u0089\u00A4 \u00CE\u00BBl+k(n) exp ( 1 (k \u00E2\u0088\u0092 1)!(log log n) k(1 + ok(1)) log log log n ) for almost all n. From the fact that \u00CE\u00BBl+k(n) = n exp ( \u00E2\u0088\u0092 1 (k + l \u00E2\u0088\u0092 1)!(1 + ol,k(1))(log log n) k+l log log log n ) we get \u00CE\u00BBl(g(n)) = n exp ( \u00E2\u0088\u0092 1 (k + l \u00E2\u0088\u0092 1)!(1 + ol,k(1))(log log n) k+l log log log n ) 58 Chapter 4. Iterates Between \u00CF\u0086 and \u00CE\u00BB for almost all n. As for \u00CF\u0086(g(n)) we note that unless g(n) = \u00CF\u0086k(n), g(n) can be writen as \u00CF\u0086l(h(n)) where h(n) is a (k \u00E2\u0088\u0092 l)\u00E2\u0080\u0093fold iterate beginning with a \u00CE\u00BB. From above we can see that h(n) = n exp ( \u00E2\u0088\u0092 1 (k \u00E2\u0088\u0092 l \u00E2\u0088\u0092 1)!(1 + ok(1))(log log n) k\u00E2\u0088\u0092l log log log n ) and so \u00CF\u0086(h(n)) is bounded above by h(n) and below by h(n) e\u00CE\u00B3 log log h(n) + 3log log h(n) = h(n) e\u00CE\u00B3 log ( log n\u00E2\u0088\u0092 1(k\u00E2\u0088\u0092l\u00E2\u0088\u00921)!(1 + ok(1))(log log n)k\u00E2\u0088\u0092l log log log n ) = h(n) e\u00CE\u00B3 log log n\u00E2\u0088\u0092O( 1(k\u00E2\u0088\u0092l\u00E2\u0088\u00921)! logn(1 + ok(1))(log log n)k\u00E2\u0088\u0092l log log log n) = h(n) exp ( O(log log log n) ) which is within the error of h(n). Hence any string of \u00CF\u0086 will not change our estimate. Therefore if j(n) is a k\u00E2\u0080\u0093fold iteration of \u00CF\u0086 and \u00CE\u00BB which is not \u00CF\u0086k(n), but which begins with l copies of \u00CF\u0086, then j(n) = n exp ( \u00E2\u0088\u0092 1 (k \u00E2\u0088\u0092 l \u00E2\u0088\u0092 1)!(1 + ok(1))(log log n) k\u00E2\u0088\u0092l log log log n ) yielding our theorem. 59 Chapter 5 Bounds on L(n) In this chapter, we will be showing upper and lower bounds for the arithmetic function L(n). Recall L(n) is the smallest k such that \u00CE\u00BBk(n) = 1. The height of the Pratt Tree is H(p). Our goal is to prove Theorems 1.6 and 1.7. The former says there exists some c > 0 such that L(n) \u00E2\u0089\u00A5 c log logn for almost all n \u00E2\u0089\u00A4 x. The latter says if H(p) \u00E2\u0089\u00A4 (log p)\u00CE\u00B3 for almost all p \u00E2\u0089\u00A4 x outside a set of size O ( x exp(\u00E2\u0088\u0092(log x)\u00CE\u00B4)) for some \u00CE\u00B4 > 0, then for some function \u00CE\u00B7, we have L(n) \u001C (log n)\u00CE\u00B3\u00CE\u00B7(n) for almost all n as n \u00E2\u0086\u0092 \u00E2\u0088\u009E. Finally we justify a conjecture about the normal order of L(n). 5.1 Lower Bound for L(n) We start with two lemmas which establishes that L(n) \u00E2\u0089\u00A5 L(p) provided p | n. This will be essential in our proof of the lower bound. Lemma 5.1. For all natural numbers a, b, \u00CE\u00BB(lcm(a, b)) = lcm(\u00CE\u00BB(a), \u00CE\u00BB(b)). Proof. Let a = p\u00CE\u00B111 p \u00CE\u00B12 2 . . . p \u00CE\u00B1r r and b = p \u00CE\u00B21 1 p \u00CE\u00B22 2 . . . p \u00CE\u00B2r r where at least one of \u00CE\u00B1i, \u00CE\u00B2i > 0. Then lcm(\u00CE\u00BB(a), \u00CE\u00BB(b)) = lcm ( \u00CE\u00BB(p\u00CE\u00B111 p \u00CE\u00B12 2 . . . p \u00CE\u00B1r r ), \u00CE\u00BB(p \u00CE\u00B21 1 p \u00CE\u00B22 2 . . . p \u00CE\u00B2r r ) ) = lcm(\u00CE\u00BB(p\u00CE\u00B111 ), \u00CE\u00BB ( p\u00CE\u00B122 ), . . . , \u00CE\u00BB(p \u00CE\u00B1r r ), \u00CE\u00BB(p \u00CE\u00B21 1 ), \u00CE\u00BB(p \u00CE\u00B22 2 ), . . . , \u00CE\u00BB(p \u00CE\u00B2r r ) ) = lcm ( \u00CE\u00BB ( p max(\u00CE\u00B11,\u00CE\u00B21) 1 ) , \u00CE\u00BB ( p max(\u00CE\u00B12,\u00CE\u00B22) 2 ) , . . . , \u00CE\u00BB ( pmax(\u00CE\u00B1r,\u00CE\u00B2r)r )) = \u00CE\u00BB ( p max(\u00CE\u00B11,\u00CE\u00B21) 1 p max(\u00CE\u00B12,\u00CE\u00B22) 2 . . . p max(\u00CE\u00B1r,\u00CE\u00B2r) r ) = \u00CE\u00BB(lcm(a, b)). Lemma 5.2. Given a positive integer n = \u00E2\u0088\u008Fr i p \u00CE\u00B1i i , 60 5.1. Lower Bound for L(n) (a) L(n) = maxi{L(p\u00CE\u00B1ii )}. (b) L(p\u00CE\u00B1) = \u00CE\u00B1\u00E2\u0088\u0092 1 + L(p) \u00E2\u0089\u00A5 L(p) for \u00CE\u00B1 \u00E2\u0089\u00A5 1. Note that these two equations imply L(n) \u00E2\u0089\u00A5 L(p) for all p | n. Proof. We show both parts by induction. For part (a) we show \u00CE\u00BBk(n) = lcm ( \u00CE\u00BBk(p \u00CE\u00B11 1 ), . . . , \u00CE\u00BBk(p \u00CE\u00B1r r ) ) (5.1) for k \u00E2\u0089\u00A5 0. For k = 0, it is true by the definition of n. Suppose it\u00E2\u0080\u0099s true for some k, then by Lemma 5.1 \u00CE\u00BBk+1(n) = \u00CE\u00BB(\u00CE\u00BBk(n)) = \u00CE\u00BB ( lcm ( \u00CE\u00BBk(p \u00CE\u00B11 1 ), . . . , \u00CE\u00BBk(p \u00CE\u00B1r r ) )) = lcm ( \u00CE\u00BB ( \u00CE\u00BBk(p \u00CE\u00B11 1 ) ) , . . . , \u00CE\u00BB ( \u00CE\u00BBk(p \u00CE\u00B1r r ) )) = lcm ( \u00CE\u00BBk+1(p \u00CE\u00B11 1 ), . . . , \u00CE\u00BBk+1(p \u00CE\u00B1r r ) ) proving the induction. Equation (5.1) implies part (a) since the least com- mon multiple of a set is 1 if and only if each number in the set is 1. For part (b), we prove this by induction on \u00CE\u00B1. If \u00CE\u00B1 = 1 then the theorem is clearly true. Suppose L(p\u00CE\u00B1) = \u00CE\u00B1\u00E2\u0088\u0092 1 + L(p) then for \u00CE\u00B1+ 1, \u00CE\u00BB(p\u00CE\u00B1+1) = p\u00CE\u00B1\u00CE\u00BB(p). Since (p\u00CE\u00B1, \u00CE\u00BB(p)), by part (a), L(p\u00CE\u00B1\u00CE\u00BB(p)) = max ( L(p\u00CE\u00B1), L(\u00CE\u00BB(p)) ) = max ( \u00CE\u00B1\u00E2\u0088\u00921+L(p), L(p)\u00E2\u0088\u00921) = \u00CE\u00B1\u00E2\u0088\u00921+L(p). Therefore L(p\u00CE\u00B1+1) = \u00CE\u00B1+ L(p), completing the induction and the theorem. For any p | n, we know that L(n) \u00E2\u0089\u00A5 L(p), which implies that L(n) > c log log p for almost all p. However, if all the primes p dividing n are small relative to n, or if n is divisible by exceptional primes, this will not imply that L(n) > c log log n. The proof of Theorem 1.6 therefore relies on showing that not many n are composed entirely of small primes as well as dealing with the exceptional set for which (1.6) doesn\u00E2\u0080\u0099t hold. Proof of Theorem 1.6. Let Y = Y (x) \u00E2\u0089\u00A4 x. Given c from equation (1.6), define a set S(x) = S(x, Y ) = {p : p \u00E2\u0089\u00A5 Y,H(p) < c log log p}. From [10, Theorem 3] we have that #S(x) \u001C x/(log x)K for some K > 1. If p | n for some p /\u00E2\u0088\u0088 S(x), and p \u00E2\u0089\u00A5 Y, 61 5.2. Upper Bound for L(n) L(n) \u00E2\u0089\u00A5 L(p) \u00E2\u0089\u00A5 H(p) \u00E2\u0089\u00A5 c log log p \u00E2\u0089\u00A5 c log log Y. Either there exists p \u00E2\u0089\u00A5 Y, p \u00E2\u0088\u0088 S(x) such that p | n or else n is composed entirely of primes less than or equal to Y. The number of n \u00E2\u0089\u00A4 x where there exists p | n with p \u00E2\u0088\u0088 S(x) is bounded by \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 p|n p\u00E2\u0088\u0088S(x) 1 = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x p\u00E2\u0088\u0088S(x) \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x n\u00E2\u0089\u00A10 (mod p) 1 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x p\u00E2\u0088\u0088S(x) x p = x \u00E2\u0088\u00AB x Y d(S(t)) t = x ( |S(x)| x + \u00E2\u0088\u00AB x Y S(t)dt t2 ) \u001C x logK x + \u00E2\u0088\u00AB x Y dt t logK t \u001C x logK\u00E2\u0088\u00921 Y using partial summation. Let \u00CE\u00A8(x, z) be the number of n \u00E2\u0089\u00A4 x composed of primes p \u00E2\u0089\u00A4 z and let z = x1/u. Let U > 0, and \u00CF\u0081(u) be the Dickman function which goes to 0 as u\u00E2\u0086\u0092\u00E2\u0088\u009E. By [17, Theorem 7.2], \u00CE\u00A8(x, z)\u001C x\u00CF\u0081(u) uniformly for 0 \u00E2\u0089\u00A4 u \u00E2\u0089\u00A4 U. Given \u000F > 0, choose Y such that log Y = (log x)1\u00E2\u0088\u0092\u000F. Since Y < x\u00CE\u00B3 for all \u00CE\u00B3 > 0, this choice yields L(n) \u00E2\u0089\u00A5 c(1\u00E2\u0088\u0092 \u000F) log log x for all but O ( x/(log Y )K\u00E2\u0088\u00921+\u00CE\u00A8(x, Y ) ) = o(x) such n \u00E2\u0089\u00A4 x, completing the theorem. 5.2 Upper Bound for L(n) The Pratt tree for a prime p describes the primes q where q \u00E2\u0089\u00BA \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0089\u00BA p. This is useful in calculating L(p). However L(p) is also increased by prime powers which the Pratt tree does not describe. The proof of Theorem 1.7 hinges on bounding the contribution of these large prime powers. We will 62 5.2. Upper Bound for L(n) show Theorem 1.7 is a corollary to the following main propostion, that the difference between H(p) and L(p) cannot be too great. Proposition 5.3. Let b > 0 and c be the constant from (2.10). Suppose H(p) \u00E2\u0089\u00A4 (log p)\u00CE\u00B3 for all p \u00E2\u0089\u00A4 x outside a set of size O(x exp(\u00E2\u0088\u0092(log x)\u00CE\u00B4)) and let \u00CE\u00B7(x) be a function such that x(cy)(log x) \u00CE\u00B3+1 2b(log x)\u00CE\u00B3\u00CE\u00B7(x)\u00E2\u0088\u00922 = o(x). (5.2) Then L(n)\u001C (log x)\u00CE\u00B3\u00CE\u00B7(x) for almost all n \u00E2\u0089\u00A4 x, for which the excluded n are divisible by at least one prime p in the above excluded set. Note that if \u00CE\u00B7\u00E2\u0088\u0097(x) is some function such that b\u00CE\u00B7\u00E2\u0088\u0097(x)(log x)\u00CE\u00B3 \u00E2\u0088\u0092 log(cy)\u00E2\u0086\u0092 \u00E2\u0088\u009E and \u00CE\u00B7(x) > 1b log 2 log(cy) + \u00CE\u00B7\u00E2\u0088\u0097(x), then x(cy)(log x) \u00CE\u00B3+1 2b(log x)\u00CE\u00B3\u00CE\u00B7(x)\u00E2\u0088\u00922 = x exp ( ((log x)\u00CE\u00B3 + 1) log(cy) ) exp ( (b\u00CE\u00B7(x)(log x)\u00CE\u00B3 \u00E2\u0088\u0092 2) log 2) \u001C x exp ( log(cy)\u00E2\u0088\u0092 b\u00CE\u00B7\u00E2\u0088\u0097(x)(log x)\u00CE\u00B3) = o(x). Specifically we can choose \u00CE\u00B7(x)\u001Cb log log log x. The proof of Propostion 5.3 begins by analyzing the ways that L(p) can be much larger than H(p) and then showing in those cases that it cannot happen for many p. Proof of Proposition 5.3. Let n = \u00E2\u0088\u008F p\u00CE\u00B1ii be the prime factorization of n where H(p) \u00E2\u0089\u00A4 (log p)\u00CE\u00B3 for all p dividing n. By equations (1.7) and (1.8), L(n) = maxi{\u00CE\u00B1i \u00E2\u0088\u0092 1 + L(p)}. Our first goal is to show that the number of n for which there exists a large \u00CE\u00B1 with p\u00CE\u00B1 | n is small. Fixing a prime p and \u00CE\u00B1 \u00E2\u0089\u00A5 2, the number n \u00E2\u0089\u00A4 x such that p\u00CE\u00B1 | n is at most x/p\u00CE\u00B1. Hence the number of bad n is bounded by \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x x p\u00CE\u00B1 \u00E2\u0089\u00A4 x x\u00E2\u0088\u0091 m=2 1 m\u00CE\u00B1 \u001C x \u00E2\u0088\u00AB \u00E2\u0088\u009E 2 t\u00E2\u0088\u0092\u00CE\u00B1dt = x (\u00CE\u00B1\u00E2\u0088\u0092 1)2\u00CE\u00B1\u00E2\u0088\u00921 . Therefore the number of bad n is bounded is o(x) for any choice of \u00CE\u00B1 = \u00CE\u00BE(x) with \u00CE\u00BE(x)\u00E2\u0086\u0092\u00E2\u0088\u009E. Therefore for almost all n \u00E2\u0089\u00A4 x we can assume L(n) \u00E2\u0089\u00A4 max p|n (L(p) + \u00CE\u00BE(x)) = max p|n (L(p) + o((log x)\u00CE\u00B3) 63 5.2. Upper Bound for L(n) by taking \u00CE\u00BE(x) = o((log x)\u00CE\u00B3). Let \u00CE\u00B7(x) be a function satifying the hypothesis of the proposition. We must determine how L(p) can be larger than H(p) and by how much. First note that for any prime in the Pratt tree, the difference between the factors of q \u00E2\u0088\u0092 1 and the primes in the Pratt tree are just the powers of that prime which divide q \u00E2\u0088\u0092 1. Therefore, if we have a branch of the Pratt tree, 2 = qk \u00E2\u0089\u00BA qk\u00E2\u0088\u00921 \u00E2\u0089\u00BA \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u00E2\u0089\u00BA q1 \u00E2\u0089\u00BA q0 = p, then L(p) \u00E2\u0089\u00A4 max{H(p) + \u00E2\u0088\u0091k i=1(\u00CE\u00B1i \u00E2\u0088\u0092 1)} where q\u00CE\u00B1ii \u00E2\u0080\u0096qi\u00E2\u0088\u00921 \u00E2\u0088\u0092 1 and the max is taken over all the branches of the Pratt tree. The inequality q\u00CE\u00B1ii < qi\u00E2\u0088\u00921 holds for all i which implies 2 \u00E2\u0088\u008Fk i=1 \u00CE\u00B1i < p. Therefore we need to maximize the sum \u00E2\u0088\u0091k i=1(\u00CE\u00B1i\u00E2\u0088\u0092 1) subject to \u00E2\u0088\u008Fk i=1 \u00CE\u00B1i < log x/ log 2. Suppose we have rs = tu, where 2 \u00E2\u0089\u00A4 r, s, t, u \u00E2\u0089\u00A4 M. The larger of r + s and t+u will be where the two terms are further apart. Consequently if we wish to maximize a sum subject a fixed product and number of terms, we want some terms to be the lowest possible value, in this case 2, and the rest to be the largest value, in this case M. Suppose for the purpose of contradiction, that \u00E2\u0088\u0091k i=1(\u00CE\u00B1i\u00E2\u0088\u00921)\u001D \u00CE\u00B7(x)(log x)\u00CE\u00B3 , where 2 \u00E2\u0089\u00A4 \u00CE\u00B1i \u00E2\u0089\u00A4M and M \u00E2\u0089\u00A4 b\u00CE\u00B7(x)(log x)\u00CE\u00B3 for any constant b. By the above reasoning we know the sum is bounded by 2(k \u00E2\u0088\u0092 l) + lM for some l \u00E2\u0089\u00A4 k. However, M l \u00E2\u0089\u00A4 log x/ log 2 implying l \u00E2\u0089\u00A4 (log log x\u00E2\u0088\u0092 log log 2)/ logM. Since k \u001C log log x, we conclude 2(k \u00E2\u0088\u0092 l) + lM is bounded above by O ( log log x+M(log log x\u00E2\u0088\u0092 log log 2)/ logM ) = o ( \u00CE\u00B7(x)(log x)\u00CE\u00B3 ) , contradicting the fact that the sum is \u001D \u00CE\u00B7(x)(log x)\u00CE\u00B3 . As a result, either\u00E2\u0088\u0091k i=1(\u00CE\u00B1i\u00E2\u0088\u00921)\u001C \u00CE\u00B7(x)(log x)\u00CE\u00B3 , completing the theorem, or M \u00E2\u0089\u00A5 b\u00CE\u00B7(x)(log x)\u00CE\u00B3 . In the latter case, there exists some \u00CE\u00B1i \u00E2\u0089\u00A5 b\u00CE\u00B7(x)(log x)\u00CE\u00B3 for some b > 0. It remains to show that the number of n \u00E2\u0089\u00A4 x such that there exists q\u00CE\u00B1 | qk\u00E2\u0088\u00921 \u00E2\u0088\u0092 1, qk\u00E2\u0088\u00921 | qk\u00E2\u0088\u00922 \u00E2\u0088\u0092 1, . . . , q1 | p \u00E2\u0088\u0092 1, p | n, with \u00CE\u00B1 \u00E2\u0089\u00A5 b\u00CE\u00B7(x)(log x)\u00CE\u00B3 is o(x). Note that k \u00E2\u0089\u00A4 H(p) \u00E2\u0089\u00A4 (log x)\u00CE\u00B3 . By Lemma 2.2, the number of n is bounded by \u00E2\u0088\u0091 \u00CE\u00B1\u00E2\u0089\u00A5b\u00CE\u00B7(x)(log x)\u00CE\u00B3 \u00E2\u0088\u0091 k\u00E2\u0089\u00A4(log x)\u00CE\u00B3 \u00E2\u0088\u0091 q x(cy)k q\u00CE\u00B1 . 64 5.2. Upper Bound for L(n) Summing q over all integers at least 2 instead of primes as above and using \u00CE\u00B1 \u00E2\u0089\u00A5 2 makes this \u001C \u00E2\u0088\u0091 \u00CE\u00B1\u00E2\u0089\u00A5b\u00CE\u00B7(x)(log x)\u00CE\u00B3 \u00E2\u0088\u0091 k\u00E2\u0089\u00A4(log x)\u00CE\u00B3 x(cy)k 2\u00CE\u00B1\u00E2\u0088\u00921 . Summing the geometric series under both \u00CE\u00B1 and k yields \u001C x(cy) (log x)\u00CE\u00B3+1 2b\u00CE\u00B7(x)(log x)\u00CE\u00B3\u00E2\u0088\u00922 . By the choice of \u00CE\u00B7 this is o(x) and hence for almost all n \u00E2\u0089\u00A4 x, L(n) \u00E2\u0089\u00A4 o((log x)\u00CE\u00B3) + max p|n { H(p) + k\u00E2\u0088\u0091 i=1 (\u00CE\u00B1i \u00E2\u0088\u0092 1) } \u001C (log n)\u00CE\u00B3 + \u00CE\u00B7(x)(log x)\u00CE\u00B3 \u001C \u00CE\u00B7(x)(log x)\u00CE\u00B3 . We are now in a position to prove Theorem 1.7. Proposition 5.3 yields the theorem provided n wasn\u00E2\u0080\u0099t divisible by any primes for which (1.9) fails to hold, so it remains to consider when n is divisible by such a prime. Proof of Theorem 1.7. Let Y = Y (x) \u00E2\u0086\u0092 \u00E2\u0088\u009E such that log Y \u001C (log x)\u00CE\u00B3 . As in the proof of Theorem 1.6 we know that the set of n \u00E2\u0089\u00A4 x which are com- posed entirely of primes less than or equal to Y has density 0. Therefore we only need to consider values of n for which there exists a prime greater than Y where H(p) > (log p)\u00CE\u00B3 . Let S(x) be the set {Y < p \u00E2\u0089\u00A4 x | L(p) > (log p)\u00CE\u00B3}. Since L(p) > H(p), by (1.9) we know that #S(x) \u001C x exp (\u00E2\u0088\u0092(log t)\u00CE\u00B4). The number of n \u00E2\u0089\u00A4 x where n is divisible by a prime in S(x) is bounded by\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 p\u00E2\u0088\u0088S(x) p|n 1 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 p\u00E2\u0088\u0088S(x) x p = x|S(x)| x + x \u00E2\u0088\u00AB x Y |S(t)|dt t2 \u001C x exp (\u00E2\u0088\u0092(log x)\u00CE\u00B4)+ x \u00E2\u0088\u00AB x Y exp (\u00E2\u0088\u0092(log t)\u00CE\u00B4)dt t \u001C x exp (\u00E2\u0088\u0092(log x)\u00CE\u00B4)+ x log x + x log Y using partial summation and exp(\u00E2\u0088\u0092(log t)\u00CE\u00B4)\u001C (log t)\u00E2\u0088\u00922. By our choice of Y the number of n is o(x) completing the theorem. 65 5.3. Conjecture for the Normal Order of L(n). 5.3 Conjecture for the Normal Order of L(n). The purpose of this section is to justify Conjecture 1.9 assuming the conjec- ture in [10, Conjecture 2] which says H(p) = e log log p\u00E2\u0088\u0092 32 log log log p+E(p) for a slow growing function E(p), and for almost all p. Note that this im- plies both that H(p) \u00E2\u0088\u00BC e log log p and that H(p) \u00E2\u0089\u00A4 log log p for almost all p. To justify our conjecture, we wish to analyze the difference L(p)\u00E2\u0088\u0092H(p) to show that it is not too large. As we saw in the previous section, this difference is created when a branch of the Pratt tree has pai | pi\u00E2\u0088\u00921 \u00E2\u0088\u0092 1 where a > 1. Let Y = Y (x) \u00E2\u0089\u00A4 x. Also let a branch of the Pratt tree be p1 \u001F p2 \u001F \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u001F pl \u001F pl+1 \u001F \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u001F pk = 2 where paii \u00E2\u0080\u0096pi\u00E2\u0088\u00921 \u00E2\u0088\u0092 1 and let l be the largest index such that pl > Y. We will separate our arguments into there parts. First is the trivial case to show there are not too many primes after pl+1. Then we deal with i < l + 1, and i = l + 1, by some probability arguments. By the trivial estimate L(n) \u001C log n we know L(pl+1) \u001C log Y. By a suitable choice of Y this will be made to be o(log log x). For i \u00E2\u0089\u00A4 l, we wish to know the probability that n has a factor pa, where p > Y. We use the following lemma. Lemma 5.4. The number of n \u00E2\u0089\u00A4 x for which there exists p > Y where pa\u00E2\u0080\u0096n is O(x/Y a\u00E2\u0088\u00921). Proof. The number of n is bounded by\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 p>Y pa\u00E2\u0080\u0096n 1 \u00E2\u0089\u00A4 \u00E2\u0088\u0091 p>Y x pa \u001C x Y a\u00E2\u0088\u00921 . By Lemma 5.4 we should expect a proportion of at most c/Y a. This implies that the probability of paii \u00E2\u0080\u0096pi\u00E2\u0088\u00921 \u00E2\u0088\u0092 1 where (a2 \u00E2\u0088\u0092 1) + (a3 \u00E2\u0088\u0092 1) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 + (al \u00E2\u0088\u0092 1) = \u00CE\u00B7(x) is bounded by cl/Y \u00CE\u00B7(x). Since the number of possible branches of the Pratt tree is trivially bounded by log x, the probability of there existing such a string of ai is bounded by 1\u00E2\u0088\u0092 ( 1\u00E2\u0088\u0092 c l Y \u00CE\u00B7(x) )log x . This bound will approach 0 provided log x = o ( Y \u00CE\u00B7(x)/cl ) . Under the assump- tion that H(p) \u00E2\u0089\u00A4 e log log(p), we have l \u00E2\u0089\u00A4 H(p) \u00E2\u0089\u00A4 e log log(p). Therefore a 66 5.3. Conjecture for the Normal Order of L(n). choice of Y = exp((log log x)3/4) and \u00CE\u00B7(x) = (log log x)3/4 makes the contri- bution to L(p)\u00E2\u0088\u0092H(p) be o(log log x) for i 6= l + 1. For i = l + 1, we have p al+1 l+1 | pl \u00E2\u0088\u0092 1. The remaining contribution to L(p) \u00E2\u0088\u0092H(p) is al+1 \u00E2\u0088\u0092 1, if pl+1 > 2 and d(al+1 + 1)/2e if pl+1 = 2. For the al+1 to contribute a lot to L(p), it must be at the end of a long prime chain, i.e. l \u001D log log p, otherwise the conjectured value of H(p) being e log log p would nullify the contribution. To show this is unlikely, we use a result from [3] which implies that the number of primes at a fixed level n of the Pratt tree is \u00E2\u0088\u00BC (log log p)n/n!. If we allow some dependence and use n = c log log p, for 0 < c < log log p we get roughly (e/c)c log log p = (log p)c log(e/c) primes at level n. We show that the probability of none of these primes being congruent to 1 modulo p al+1 l+1 goes to 1 provided p al+1 l+1 is large enough. Suppose we have N primes. The probability that any one of them is congruent to 1 modulo ra for a prime r and positive integer a, is 1/\u00CF\u0086(ra). Assuming independence, the probability that none of the N primes are con- gruent to 1 modulo ra is ( 1\u00E2\u0088\u0092 1 \u00CF\u0086(ra) )N . Let \u00CE\u00B7 be a function going to infinity. Furthermore, let ra > N\u00CE\u00B7(N) be a prime power. Since r is prime, we know \u00CF\u0086(ra) \u00E2\u0089\u00A5 ra/2. This bound implies the probability is bounded below by( 1\u00E2\u0088\u0092 2 ra )N . Using our lower bound on ra we get( 1\u00E2\u0088\u0092 2 ra )N \u00E2\u0089\u00A5 1\u00E2\u0088\u0092 ( 1\u00E2\u0088\u0092 2 N\u00CE\u00B7(N) )N \u00E2\u0086\u0092 1, since \u00CE\u00B7(N)\u00E2\u0086\u0092\u00E2\u0088\u009E. We know wish to use the lower bound on ra to bound al+1 and therefore our contribution to L(p)\u00E2\u0088\u0092H(p). Suppose ql+1 6= 2. If the level l \u00E2\u0089\u0088 c log log p, for almost all p, we expect al+1 \u00E2\u0089\u00A4 log(N logN) log ql+1 = c log(e/c) log ql+1 log log p+O(log3 p). Combining all the contributions along any particular branch, we get L(p) \u00E2\u0089\u00A4 ( c+ c log(e/c) log ql+1 ) log log p+ o(log log p). (5.3) 67 5.3. Conjecture for the Normal Order of L(n). If ql+1 = 2, since, \u00CE\u00BB(2 a) = 2a\u00E2\u0088\u00922 we get( c+ c log(e/c) 2 log 2 ) log log p+ o(log2 p) = ( c+ c log(e/c) log 4 ) log log p+ o(log2 p). Consequently, 3 is the value of ql+1 which yields the largest coefficient of log log p in (5.3). Since c + c log(e/c)/ log 3 \u00E2\u0089\u00A4 e for 0 < c < e, we conclude that for almost all p \u00E2\u0089\u00A4 x, L(p) \u00E2\u0088\u00BC e log log p. The reason that we can replace p by n is the same reason as in Theorem 1.6. It may seem obvious to conclude L(p) \u00E2\u0088\u00BC e log log p, sinceH(p) \u00E2\u0088\u00BC e log log p. However, note that the function ( c + c log(e/c)log 2 ) does not yield a maximum value of e, but instead has its maximum of 2/ log(2) at c = 2. This may suggest if we had a function L\u00E2\u0080\u00B2(n) similar to L(n) except that \u00CE\u00BB\u00E2\u0080\u00B2(2a) = 2a\u00E2\u0088\u00921 for all positive integers a, that we may get a different normal order, perhaps even 2 log log n/ log(2). 68 Chapter 6 Open Problems Here is a list of open problems regarding \u00CE\u00BB(n), L(n) and H(p). Theorem 1.4 showed that the normal order of log n\u00CE\u00BBk(n) is 1 (k\u00E2\u0088\u00921)!(log log n) k log log log n. Theorem 1.5 showed that if g(n) = \u00CF\u0086l(\u00CE\u00BB(f(n))), where f(n) is a (k \u00E2\u0088\u0092 1) iterated arithmetic function consisting of iterates of \u00CF\u0086 and \u00CE\u00BB, then the normal order of log(n/g(n)) is 1(k\u00E2\u0088\u00921)!(log log n) k log log log n. This is because g(n) relates to n in the same way as \u00CE\u00BBk(n). However this doesn\u00E2\u0080\u0099t explain the relationship between g(n) and \u00CE\u00BBk(n). The question has been solved for k = 2 by Kapoor [14]. Theorem 6.1. The normal order of log (\u00CE\u00BB(\u00CF\u0086(n)) \u00CE\u00BB(\u00CE\u00BB(n)) ) is log log n log log log n. It would be interesting to see if a similar result could be proven for higher values of k. Based on Theorem 6.1 is seems reasonable to think that if f1(n) and f2(n) are compositions of \u00CE\u00BB and \u00CF\u0086, then log ( \u00CE\u00BB(f1(n)) \u00CE\u00BB(f2(n)) ) \u00E2\u0088\u00BC log ( f1(n) f2(n) ) . (6.1) For example the normal order of log \u00CE\u00BB\u00CE\u00BB\u00CF\u0086\u00CE\u00BB\u00CE\u00BB\u00CF\u0086(n)\u00CE\u00BB6(n) is conjecturally log \u00CF\u0086\u00CE\u00BB\u00CE\u00BB\u00CF\u0086(n) \u00CE\u00BB4(n) \u00E2\u0088\u00BC 1 3! (log log n)4 log log log n. It would also be interesting to see if there can be a more precise result of Theorem 1.4. In [9], for k = 1, there is an improved result. Instead of simply log(n/\u00CE\u00BB(n)) = log log n(log log log n+O(\u00CF\u0088(n))), they more precisely showed log ( n \u00CE\u00BB(n) ) = log log n ( log log log n+A+O ( (log log log n)\u00E2\u0088\u00921+\u000F )) (6.2) for almost all n as n \u00E2\u0086\u0092 \u00E2\u0088\u009E. There is no result like (6.2) even for k = 2. For k = 1, the authors in [9] split up the primes q into four regions, namely q \u00E2\u0089\u00A4 y/ log y, y/ log y < q \u00E2\u0089\u00A4 y log y, y log y < q \u00E2\u0089\u00A4 y2 and y2 < q. On the 69 Chapter 6. Open Problems other hand in Theorem 1.4, as well as the theorem of Martin and Pomerance in [16], the values of q were only split up into the two regions q \u00E2\u0089\u00A4 yk and q > yk. Perhaps reasoning closer to [9] can obtain a more precise estimate. Another improvement would be a more uniform result for Theorem 1.4. The implicit constant is at least exponential in k, meaning the best uni- form result wouldn\u00E2\u0080\u0099t even get k < log log log log n. It\u00E2\u0080\u0099s unlikely the methods of Chapter 3 will produce a more uniform result even with more careful consideration. In [9], Erdo\u00CC\u008Bs, Pomerance, and Schmutz obtained a lower bound for \u00CE\u00BB(n) of exp ( c1 log log n log log log n).With a different constant, they also obtained an upper bound of the same form for infinitely many n. It would be interest- ing to see if something similar could be done for \u00CE\u00BB(\u00CE\u00BB(n)) or more generally \u00CE\u00BBk(n). Naively inputting the lower bound into itself recursively can show a lower bound to be exp ( ck logk+1(n) logk+2(n) ) , (6.3) where logk(n) is the k\u00E2\u0080\u0093th iterate of the log function. However, this may or may not be the \u00E2\u0080\u009Dbest\u00E2\u0080\u009D lower bound. Perhaps there are infinitely many n with an upper bound of the form (6.3) for \u00CE\u00BBk(n). If that is true, then it can be shown that for those n, L(n) = k + L(\u00CE\u00BBk(n)) \u00E2\u0089\u00A4 k + log(\u00CE\u00BBk(n)) log 2 + 1\u001Ck logk+1(n) logk+2(n) settling a conjecture given in [16]. Even showing this for k = 2 would yield a better result than is currently known. If (6.3) is not a desirable lower bound, perhaps a better one could be found, along with a sequence of n which obtain that lower bound. Another notable open problems regarding \u00CE\u00BB(n) is the analog of the fa- mous Carmichael conjecture. In [6], R.D. Carmichael made the following conjecture: Conjecture 6.2. For any natural number m, the equation \u00CF\u0086(n) = m does not have exactly one solution. The conjecture is open for both \u00CF\u0086 as well as \u00CE\u00BB, although it\u00E2\u0080\u0099s known to be true for \u00CE\u00BB conditionally using the generalized Riemann hypothesis. For \u00CE\u00BB, it is known from [2] that any counterexample is a multiple of the smallest one. Much more is known see [2] about the (probably non\u00E2\u0080\u0093existent) counterexample of the \u00CE\u00BB case. 70 Bibliography [1] L.M. Adleman, C. Pomerance and R.S. Rumely. On distiguishing prime numbers from composite numbers, Ann. of Math. 117 (1983), 173\u00E2\u0080\u0093206. [2] W.D. Banks, J. Friedlander, F. Luca, F. Pappalardi, and I.E. Shparlin- ski, Coincidences in the values of the Euler and Carmichael functions, Acta Arith., 122 (2006), 207\u00E2\u0080\u0093234. [3] N. L. Bassily, I. Ka\u00CC\u0081tai and M. Wijsmuller, Number of prime divisors of \u00CF\u0086k(n), where \u00CF\u0086k is the k\u00E2\u0080\u0093fold iterate of \u00CF\u0086, J. Number Theory 65 (1997), 226\u00E2\u0080\u0093239. [4] W.D. Banks, F. Luca, F. Saidak and P. Sta\u00CC\u0086nica\u00CC\u0086. Compositions with the Euler and Carmichael functions, Abh. Math. Sem. Univ. Hamburg., 75 (2005), 215\u00E2\u0080\u0093244. [5] R.D. Carmichael. Note on a new number theory function, Bull. Amer. Math. Soc., 5 (1910), 232\u00E2\u0080\u0093238. [6] R.D. Carmichael. Note on Euler\u00E2\u0080\u0099s \u00CF\u0086 function, Bull. Amer. Math. Soc., 28 (1922), 109\u00E2\u0080\u0093110. [7] H. Davenport, Multiplicative Number Theory Third Edition, Graduate Texts in Math., New York: Springer-Verlag, Vol. 74 (2000). [8] P. Erdo\u00CC\u008Bs, A. Granville, C. Pomerance, and C. Spiro, On the normal be- havior of the iterates of some arithmetic functions, in Analytic Number Theory (Allerton Park, IL, 1989), Progr. Math., 85 Birkha\u00CC\u0088user Boston, Boston, MA, (1990), 165\u00E2\u0080\u0093204. [9] P. Erdo\u00CC\u008Bs, C. Pomerance, and E. Schmutz, Carmichael\u00E2\u0080\u0099s lambda func- tion, Acta Arith., 58 (1991), 363\u00E2\u0080\u0093385. [10] K. Ford, S.V. Konyagin and F. Luca, Prime chains and Pratt trees, Geom. Funct. Anal., 20 (2010), 1231\u00E2\u0080\u00931258. 71 [11] J. Friedlander, C. Pomerance and I.E. Shparlinski, Period of the power generator and small values of the Carmichael function, Math. Comp., 70 (2001), 1591\u00E2\u0080\u00931605. [12] H. Halberstam and H. Richert Sieve Methods, Academic Press [A sub- sidiary of Harcourt Brace Jovanovich, Publishers], London-New York (2004) London Mathematical Society Monographs, No.4. [13] J.P. Kubilius, Probabilistic Methods in the Theory of Numbers, Trans- lations of Mathetical Monographs, Vol. 11, American Math. Soc., Prov- idence (1964). [14] V. Kapoor, Asymptotic formulae for arithmetic functions, Ph.D. The- sis, The University of British Columbia, April 2011. [15] G. Miller. Riemann\u00E2\u0080\u0099s hypothesis and tests for primality, J. Comput. System Sci., 13 (1976), 300\u00E2\u0080\u0093317. [16] G. Martin and C. Pomerance, The iterated Carmichael \u00CE\u00BB\u00E2\u0080\u0093function and the number of cycles of the power generator, Acta Arith., 118 (2005), no. 4, 305\u00E2\u0080\u0093335. [17] H. Montgomery and R. Vaughan, Multiplicative Number Theory I. Clas- sical Theory, Cambridge University Press, New York (2007). [18] C. Pomerance, On the distribution of amicable numbers, J. Reine Angew. Math., 293/294 (1977), 217\u00E2\u0080\u0093222. [19] V. Pratt, Every prime has a succinct certificate, SIAM J. Comput., 4 (1975), no. 3, 214\u00E2\u0080\u0093220. [20] G. Tenenbaum, Introduction to Analytic and Probabilistic Number The- ory, Cambridge University Press, New York (1995). [21] P. Tura\u00CC\u0081n, On a theorem of Hardy and Littlewood, J. London Math. Soc. 9 (1934), 274\u00E2\u0080\u0093276. 72 Appendix A The Turan\u00E2\u0080\u0093Kubilius Inequality The Tura\u00CC\u0081n\u00E2\u0080\u0093Kubilius Inequality is a result in probabilistic number theor. It is useful in finding normal orders of additive arithmetic functions. The theorem was originally proved in a special case by Tura\u00CC\u0081n [21] to prove the following theorem of Hardy and Littlewood. Let \u00CF\u0089(n) be the number of distinct prime divisors of n, and \u00E2\u0084\u00A6(n) be the number of prime divisors including multiplicity. For any \u00CE\u00B4 > 0, the number of n \u00E2\u0089\u00A4 x for which \u00CF\u0089(n) = log log n+O ( (log log n)1/2+\u00CE\u00B4 ) fails to hold is o(x). The analagous result for \u00E2\u0084\u00A6 holds as well. The methods of Tura\u00CC\u0081n were subsequently extended by Kubilius to more general additive functions. Theorem A.1 (Tura\u00CC\u0081n\u00E2\u0080\u0093Kubilius). For any complex additive function f we have \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x |f(n)\u00E2\u0088\u0092A(x)|2 \u001C xB(x)2 (A.1) where A(x) = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk)(1\u00E2\u0088\u0092 p\u00E2\u0088\u00921) pk , B(x)2 = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x |f(pk)|2 pk . For a strongly additive function, that is f(pk) = f(p) for all k \u00E2\u0089\u00A5 1, the theorem reduces to the following corollary. Corollary A.2. For any complex completely additive function f we have\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x |f(n)\u00E2\u0088\u0092M1(x)|2 \u001C xM2(x)2 where M1(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x f(p) p , M2(x) 2 = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x |f(p)|2 p . 73 Appendix A. The Turan\u00E2\u0080\u0093Kubilius Inequality To see the redution to the corollary for strongly additive function, note that we can replace B(x)2 by M2(x) 2 because B(x)2 = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x |f(p)|2 pk \u00E2\u0089\u00A4 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x |f(p)|2 \u00E2\u0088\u0091 k\u00E2\u0089\u00A51 1 pk \u001C \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x |f(p)|2 1 p . As for A(x), the sum becomes A(x) = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(p)(1\u00E2\u0088\u0092 p\u00E2\u0088\u00921) pk = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ( f(p) pk \u00E2\u0088\u0092 f(p) pk+1 ) Using Cauchy\u00E2\u0080\u0093Schwarz (2.14) the difference between A(x) and M1(x) is at most \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x |f(p)| p2 \u00E2\u0089\u00A4 (\u00E2\u0088\u0091 p\u00E2\u0089\u00A4x 1 p2 \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x |f(p)|2 p2 )1/2 \u001C B(x). Therefore\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x |f(n)\u00E2\u0088\u0092M1(x)|2 \u00E2\u0089\u00A4 2 \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x (|f(n)\u00E2\u0088\u0092A(x)|2 + |A(x)\u00E2\u0088\u0092M1(x)|2) \u001C xB(x)2 \u001C xM2(x)2. Our proof of Theorem A.1 is taken mostly from [20, III.3 Theorem 1]. We will prove it for f real and positive. Note that proof for f real can be done by combining the positive and negative parts of f. The proof for f complex can be done by combining the real and imaginary parts of f. Proof of Theorem A.1. For notational convience, let A = A(x), B = B(x) and S = S(x) be the sum in equation (A.1). Then S = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x f2(n)\u00E2\u0088\u0092 2A \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x f(n) + bxcA2 := S2 \u00E2\u0088\u0092 2AS1 + bxcA2. (A.2) 74 Appendix A. The Turan\u00E2\u0080\u0093Kubilius Inequality Since f(n) is additive, f(n) = \u00E2\u0088\u0091 pk\u00E2\u0080\u0096n f(p k). Inserting this into S1 yields S1 = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 pk\u00E2\u0080\u0096n f(pk) = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk) (\u00E2\u008C\u008A x pk \u00E2\u008C\u008B \u00E2\u0088\u0092 \u00E2\u008C\u008A x pk+1 \u00E2\u008C\u008B) \u00E2\u0089\u00A5 xA\u00E2\u0088\u0092 \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk) using bxc \u00E2\u0088\u0092 byc \u00E2\u0089\u00A5 x\u00E2\u0088\u0092 y \u00E2\u0088\u0092 1. As for S2 we obtain S2 = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x (\u00E2\u0088\u0091 pk\u00E2\u0080\u0096n f(pk) )2 = \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x \u00E2\u0088\u0091 pk\u00E2\u0080\u0096n f(pk) \u00E2\u0088\u0091 ql\u00E2\u0080\u0096n f(ql). Splitting this up into the two cases where p = q or p 6= q yields S2 = \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f2(pk) \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x pk\u00E2\u0080\u0096n 1 + \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ql\u00E2\u0089\u00A4x q 6=p f(pk)f(ql) \u00E2\u0088\u0091 n\u00E2\u0089\u00A4x pk\u00E2\u0080\u0096n ql\u00E2\u0080\u0096n 1 \u00E2\u0089\u00A4 x \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f2(pk) pk + \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ql\u00E2\u0089\u00A4x q 6=p f(pk)f(ql) (\u00E2\u008C\u008A x pkql \u00E2\u008C\u008B \u00E2\u0088\u0092 \u00E2\u008C\u008A x pkql+1 \u00E2\u008C\u008B \u00E2\u0088\u0092 \u00E2\u008C\u008A x pk+1ql \u00E2\u008C\u008B + \u00E2\u008C\u008A x pk+1ql+1 \u00E2\u008C\u008B) \u00E2\u0089\u00A4 xB2 + x \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ql\u00E2\u0089\u00A4x q 6=p f(pk) pk (1\u00E2\u0088\u0092 p\u00E2\u0088\u00921)f(q l) ql (1\u00E2\u0088\u0092 q\u00E2\u0088\u00921) + 2 \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ql\u00E2\u0089\u00A4x q 6=p f(pk)f(ql) using bxc\u00E2\u0088\u0092byc \u00E2\u0089\u00A4 x\u00E2\u0088\u0092y+1. Let the last sum be S3. Inserting these estimates into (A.2) yields S \u00E2\u0089\u00A4 xB2 + 2A \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk) + 2S3 +A 2. (A.3) Using Cauchy\u00E2\u0080\u0093Schwarz (2.14) on S3 yields S3 \u00E2\u0089\u00A4 ( \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ql\u00E2\u0089\u00A4x f(pk)f(ql) pkql \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x ql\u00E2\u0089\u00A4x pkql )1/2 \u001C B2 (\u00E2\u0088\u0091 n\u00E2\u0089\u00A4x n )1/2 \u001C xB2. 75 Appendix A. The Turan\u00E2\u0080\u0093Kubilius Inequality Using Cauchy\u00E2\u0080\u0093Schwarz (2.14) again yields \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk) \u00E2\u0089\u00A4 ( \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f2(pk) pk \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x pk )1/2 = B ( \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x pk )1/2 . We would like to bound the sum by a sum over all n \u00E2\u0089\u00A4 x like in our bound for S3, however that would give us an estimate of Bx which is too large. Instead we bound each term by x and bound the sum over prime powers by pi(x) + pi(x1/2) + \u00C2\u00B7 \u00C2\u00B7 \u00C2\u00B7 \u001C x/ log x. This bound implies \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk)\u001C B ( x2 log x )1/2 = B x\u00E2\u0088\u009A log x . As for A we use an estimate of Mertens [17, Theorem 2.7 (d)] and Cauchy\u00E2\u0080\u0093 Schwarz (2.14), implying A\u001C \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f(pk) pk \u00E2\u0089\u00A4 ( \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x f2(pk) pk \u00E2\u0088\u0091 pk\u00E2\u0089\u00A4x 1 pk )1/2 \u001C B(log log x)1/2. Putting all these estimates together with (A.3) yields S \u001C xB2+2 ( B(log log x)1/2 )( B x (log x)1/2 ) +2xB2+B2(log log x)\u001C xB2 completing the theorem. It\u00E2\u0080\u0099s worth noting that the strongly additive condition is not necessary for the replacement of B(x) with M2(x). See [13, Lemma 3.1] for a proof. Also note that the function hk(n) in the proof of Theorem 1.4 is a strongly additive function justifying our use of Corollary A.2. 76"@en . "Thesis/Dissertation"@en . "2013-05"@en . "10.14288/1.0073354"@en . "eng"@en . "Mathematics"@en . "Vancouver : University of British Columbia Library"@en . "University of British Columbia"@en . "Attribution 3.0 Unported"@en . "http://creativecommons.org/licenses/by/3.0/"@en . "Graduate"@en . "The iterated Carmichael lambda function"@en . "Text"@en . "http://hdl.handle.net/2429/43537"@en .