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© Nicholas Harland 2012 Abstract The arithmetic function λ(n) is the exponent of the cyclic group (Z/nZ)×. The kth iterate of λ(n) is denoted by λk(n). In this work we will show the normal order for log(n/λk(n)) is (log logn) k−1 log log log n/(k− 1)!. Second, we establish a similar normal order for other iterate involving a combination of λ and φ. Lastly, define L(n) to be the smallest k such that λk(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 φk(n) . . . . . . . . . . . . . . . . . 20 3.3 Large Primes Dividing φk(n) . . . . . . . . . . . . . . . . . . 23 3.4 Small Primes Dividing λk(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 ∑ 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 φ and λ . . . . . . . . . . . . . . . . . . . . . 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–Kubilius 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 λ(n), first introduced by Carmichael [5], is defined to be the order of the largest cyclic subgroup of the multiplicative group (Z/nZ)×, that is, the smallest postive integer m such that am ≡ 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 φ(pk) = pk−1(p − 1). As for even prime powers, λ(2) = 1, λ(4) = 2, and λ(2k) = φ(2k)/2 = 2k−2 for k ≥ 3. By the Chinese Remainder Theorem, if (a, b) = 1, then λ(ab) = lcm{λ(a), λ(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 λ(N) for specially created numbers N. In [15], the primality test involves looking at Carmichael numbers. That is numbers which satisfy an−1 ≡ 1 (mod n) for all (a, n) = 1. It is well known that composite numbers satisfy this conguence if and only if λ(n) divdes n− 1. Miller uses this idea to help create his algorithm to test primes. Several properties of λ(n) were studied by Erdős, Pomerance, and Schmutz in [9]. One of those results is the following. For an explicitly defined constant A, λ(n) = n exp (− (log log n)(log log log n+A+O((log log log n)−1+)) (1.1) as n→∞ for almost all n. Martin and Pomerance showed in [16] that λ(λ(n)) = n exp ( − (1 + o(1))(log log n)2 log log log n ) (1.2) as n→∞ for almost all n. 1 1.1. History and Results Applications of this function included the power generator of pseudoran- dom numbers un ≡ uen−1 (mod m), 0 ≤ un ≤ m− 1, n = 1, 2, . . . . This generator has lots of cryptographic applications (see [11]), and se- quences of large period given by λ(λ(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 λ(λ(m)) and then use their estimate. This thesis studies the asymptotic properties of the following two func- tions. Definition 1.1. The k–fold iterated Carmichael lambda function is defined recursively to be λ0(n) = n, λk(n) = λ(λk−1(n)) for k ≥ 1. We define φk(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 λk(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 > 0, (1− )g(n) < f(n) < (1 + )g(n) (1.3) for almost all n. By “for almost all n” we mean the proportion of n ≤ x for which (1.3) does not hold goes to 0 as n→∞. In [16] it is conjectured that λk(n) = n exp ( − 1 (k − 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λk(n) is 1 (k−1)!(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’ll prove the theorem in Chapter 3 in the following slightly stronger form. Let ψ(x) be a function which satisifes the following two properties. 1. ψ(x) = o(log log log x) and 2. ψ(x)→∞ as x→∞. We will show log ( n λk(n) ) = 1 (k − 1)!(log log n) k ( log log log n+Ok ( ψ(n) )) for all but O(x/ψ(x)) integers up to x. The proof of Theorem 1.4 involves breaking down n/λk(n) in terms of the iterated Euler φ function by using n λk(n) = ( n φ(n) )( φ(n) φ2(n) ) . . . ( φk−1(n) φk(n) )( φk(n) λk(n) ) . (1.4) Estimates for all but the last term are known. Hence log(n/λk(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(φk(n)/λk(n)). Our second result is an asymptotic formula involving iterates involving λ and φ. Banks, Luca, Saidak and Stănică in [4] showed that for almost all n, λ(φ(n)) = n exp(−(1 + o(1))(log log n)2 log log log n) and φ(λ(n)) = n exp(−(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 λ and φ. Specifically we prove the following. Theorem 1.5. For l ≥ 0 and k ≥ 1, let g(n) = φl(λ(f(n))), where f(n) is a (k− 1) iterated arithmetic function consisting of iterates of φ and λ. The normal order of log(n/g(n)) is 1(k−1)!(log log n) k log log log n. An example of the use of this theorem is for φφλφφλλφ(n). Since l = 2, k = 5, we get that the normal order of log nφφλφφλλφ(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 Erdős, Granville, Pomerance and Spiro in [8] established that n/φk(n) does not have a normal order. That result combined with Theorem 1.5 completes the picture of how all iterates of λ and φ relate to n. However it doesn’t show how they relate to each other. For example log nλφφλλφ(n) ∼ log nλ6(n) for almost all n, but is there a normal order for log λφφλλφ(n)λ6(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 − 1. The nodes below q are primes dividing q− 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 λ(n). The height of the Pratt tree H(p) is the length of the longest branch. That height is related to L(n). Since λ(n) is either even or 1, and λ(n) ≤ n/2 for even n, we easily see that L(n) ≤ blog n/ log 2 + 1c. By considering when n is a power of 3 we can note that L(n) ≥ 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 ≤ x have asymptotic density 0. It is conjectured that for a set of positive integers with asymptotic density 1, that L(n) log logn however no previous results have shown L(n) = o(log n) for almost all n. It’s easy to see thatH(p) ≤ 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–Halberstam conjecture. Recall the Bombieri–Vinogradov Theorem [7, Chapter 28] implies∑ n≤Q max y≤x ∣∣∣∣pi(y;n, 1)− li(y)φ(m) ∣∣∣∣ x(log x)−A (1.5) holds for any Q ≤ x1/2(log x)−B and any A > 0, where B = B(A). The Elliot–Halberstam conjecture says that (1.5) holds for Q = xθ for any θ < 1. Let θ′ be such that (1.5) holds for Q = xθ′ . In [10] Ford, Konyagin and Luca showed for any c < 1/(e−1 − log θ′), H(p) > c log log p (1.6) for all butO ( x/(log x)K ) primes p, for someK > 1.Under Elliot–Halberstam, we can take any c < e, but unconditionally, Bombieri–Vinogradov gives any c < 1/(e−1 + log 2). In Chapter 5 we show that if n = ∏ pαii , then L(n) = max i {L(pαii )} (1.7) and L(pα) = α− 1 + L(p) ≥ L(p). (1.8) These two equations imply L(n) ≥ 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) ≥ c log logn for almost all n ≤ x. For an upper bound, in [10] it was shown that H(p) ≤ (log p)0.95022 (1.9) for all p ≤ x outside a set of size O(x exp(−(log x)δ) for some δ > 0. We extend this to a result about L(n). Theorem 1.7. If H(p) ≤ (log p)γ for almost all p ≤ x outside a set of size O ( x exp(−(log x)δ)) for some δ > 0, then for some function η, L(n) (log n)γη(n) for almost all n as n→∞. 5 1.1. History and Results The function η(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) (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 ≥ 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 = ∏ p pvp(n). Let the set Pn be {p : p ≡ 1 (mod n)}. The notation q ≺ q′ is defined to mean that q′ ∈ Pq. In Chapter 3 we will assume x > eee . The function y = y(x) is defined to be log log x. Also let ψ(x) be any function going to ∞ such that ψ(x) = o(log y) = o(log log log x). Whenever we use the phrase “for almost all n ≤ x” in a result, we mean that the result is true for all n ≤ x except a set of size o(x). In Chapter 3 the exceptional set will be O(x/ψ(x)). 2.2 Required Estimates The following estimates will be used throughout this thesis. Let Λ(n) be the Von–Mangoldt function defined by Λ(n) = { log p n = pl 0 otherwise. We use the Chebyshev bound∑ n≤x Λ(n) = ∑ pl≤x log p x. (2.1) 7 2.2. Required Estimates Also define the related function θ(x) = ∑ p≤x log p. It follows from (2.1) that θ(x) x. (2.2) We also require a formula of Mertens (see [17, Theorem 2.7(b)])∑ q≤x 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) ∑ q>x log q q2 1 x . (2.4) (b) ∑ q>x 1 q2 1 x log x . (2.5) Proof. Equation (2.5) follows from (2.4) since log x < log q. As for Equation (2.4), ∑ q>x log q q2 = ∫ ∞ x d(θ(t)) t2 = 2θ(x) x3 + ∫ ∞ x 2θ(t)dt t3 = 2θ(x) x3 +O (∫ ∞ x dt t2 ) 1 x . Given m,x ≥ 2, let A be the smallest a for which ma > x. We can then manipulate the sums ∑ a∈N P (a) ma = 1 m ∞∑ a=0 P (a) ma and ∑ a∈N ma>x 1 ma 1 x ∣∣∣∣ ∞∑ a=A 1 ma−A ∣∣∣∣ = 1x ∣∣∣∣ ∞∑ a=0 1 ma ∣∣∣∣ 8 2.2. Required Estimates for any polynomial P (x). Then by noting that ∑∞ a=A P (a) ma P 1 uniformly for m ≥ 2 and A ≥ 0 we obtain the estimates∑ a∈N P (a) ma P 1 m , ∑ a∈N ma>x 1 ma 1 x . (2.6) From [17, Corollary 1.15] we get∑ s≤x 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 ≤ t, pi(t;n, a) t φ(n) log(t/n) . (2.8) By partial summation on (2.8) we can obtain∑ p≤t p∈Pn 1 p log log t φ(n) . (2.9) Whenever n/φ(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∑ p≤t p∈Pn 1 p ≤ 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∑ p∈Pn p≤t 1 p = log log t φ(n) +O ( log n φ(n) ) . (2.11) Equation (2.11) easily implies∑ p∈Pn p≤t 1 p− 1 = log log t φ(n) +O ( log n φ(n) ) , (2.12) 9 2.3. Early Results since the difference is ∑ p∈Pn p≤t 1 p(p− 1) ≤ ∞∑ m=1 1 mn(mn+ 1) < 1 n2 ∞∑ m=1 1 m2 1 n2 . The Bombieri–Vinogradov Theorem [7, Chapter 28] implies∑ n≤Q max y≤x ∣∣∣∣pi(y;n, 1)− li(y)φ(m) ∣∣∣∣ x(log x)−A (2.13) with Q ≤ x1/2(log x)−B 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– Schwarz inequality in the following form. If f(n) and g(n) are arithmetic functions, then for any t ≥ 1,∣∣∣∣∑ n≤t f(n)g(n) ∣∣∣∣2 ≤∑ n≤t |f(n)|2 ∑ n≤t |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, α. The number of n ≤ x such that there exists p, q1, . . . , qk−1 satisfying qα | qk−1 − 1, qk−1 | qk−2 − 1, . . . , q1 | p− 1 and p | n is at most x(cy)k qα 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 ∑ n≤x ∑ p|n ∑ q1|p−1 · · · ∑ qk−1|qk−2−1 ∑ qα|qk−1−1 1 = ∑ qk−1≡1 (mod qα) ∑ qk−2≡1 (mod qk−1) · · · ∑ p≡1 (mod q1) ∑ n≤x n≡0 (mod p) 1 ≤ ∑ qk−1≡1 (mod qα) ∑ qk−2≡1 (mod qk−1) · · · ∑ p≡1 (mod q1) x p ≤ ∑ qk−1≡1 (mod qα) ∑ qk−2≡1 (mod qk−1) · · · ∑ q1≡1 (mod q2) xcy q1 ≤ · · · ≤ ∑ qk−1≡1 (mod qα) x(cy)k−1 qk−1 ≤ x(cy) k qα . 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 φ(m). The following involves the estimation of the latter sums. Lemma 2.3. For any non-negative integer L we have ∑ m≤t mL φ(m)L+1 L log t. (2.15) Proof. If f(n) is a non-negative multiplicative function, we know that ∑ n≤t f(n) ≤ ∏ p≤t ∞∑ r=0 f(pr). (2.16) 11 2.3. Early Results Applying (2.16) with n L φ(n)L+1 yields ∑ m≤t mL φ(m)L+1 ≤ ∏ p≤t ( 1 + ∞∑ r=1 prL (pr − pr−1)L+1 ) = ∏ p≤t ( 1 + ∞∑ r=1 pL−r+1 (p− 1)L+1 ) = ∏ p≤t ( 1 + 1 (p− 1)L+1 pL 1− 1p ) = ∏ p≤t ( 1 + pL+1 (p− 1)L+2 ) ≤ exp (∑ p≤t log ( 1 + pL+1 (p− 1)L+2 )) = exp (∑ p≤t ( pL+1 (p− 1)L+2 +OL ( 1 p2 ))) = exp (∑ p≤t ( 1 p +OL ( 1 p2 ))) L log t using (2.3). Lemma 2.4. Let L be a nonnegative integer and γ a positive real number. Given a positive integer C ≤ tγ and non-negative integer L we have ∑ m≤t (Cm+ 1)L φ(Cm+ 1)Lφ(m) L,γ log t. (2.17) Proof. It will suffice to show ∑ m≤t (Cm+ 1)2L−1 φ(Cm+ 1)2L L,γ log t C (2.18) 12 2.3. Early Results as then by Cauchy–Schwarz (2.14) we can get that(∑ m≤t (Cm+ 1)L φ(Cm+ 1)Lφ(m) )2 ≤ ∑ m≤t (Cm+ 1)2L−1 φ(Cm+ 1)2L ∑ m≤t (Cm+ 1) φ(m)2 L,γ ( log t C ) C log t L,γ log2 t by using Lemma 2.3 and (2.18). Let G(t) = ∑ m≤t (Cm+ 1)2L φ(Cm+ 1)2L . We show Equation (2.18) by first showing G(t) L,γ t. This implies Equa- tion (2.18) since ∑ m≤t (Cm+ 1)2L−1 φ(Cm+ 1)2L < 1 C ∑ m≤t (Cm+ 1)2L mφ(Cm+ 1)2L = 1 C ∫ t 1− d(G(u)) u = 1 C ( G(t) t + ∫ t 1− G(u) u2 ) L,γ 1 C ( 1 + ∫ t 1− 1 u ) L,γ 1 C (log t) To show Equation (2.18) we start by defining s(n) to be the multiplicative function defined by n2L φ(n)2L = 1 ∗ s = ∑ d|n s(d). Testing at prime powers, we can easily see that s(1) = 1, s(p) = ( 1− 1 p )−2L − 1 and s(pk) = 0 for all k ≥ 2. 13 2.3. Early Results Hence ∑ m≤t (Cm+ 1)2L φ(Cm+ 1)2L = ∑ n≤Ct+1 n≡1 (mod C) n2L φ(n)2L = ∑ n≤Ct+1 n≡1 (mod C) ∑ d|n s(d) = ∑ d≤Ct+1 s(d) ∑ n≤Ct+1 d|n n≡1 (mod C) 1 = ∑ d≤Ct+1 s(d) ( t d +O(1) ) = t ∑ d≤Ct+1 s(d) d +O ( ∑ d≤Ct+1 s(d) ) . We require some estimates on s(d). For the sum of the multiplicative function s(d)/d, ∑ d≤Ct+1 s(d) d ≤ ∏ p≤Ct+1 ( 1 + (1− 1/p)−2L − 1 p ) ≤ ∏ p≤Ct+1 ( 1 +OL ( 1 p2 )) = exp ( ∑ p≤Ct+1 log ( 1 +OL ( 1 p2 ))) = exp ( ∑ p≤Ct+1 OL ( 1 p2 )) = exp(OL(1)) L 1. 14 2.3. Early Results For the sum of s(d),∑ d≤Ct+1 s(d) ≤ ∏ p≤Ct+1 ( 1 + (1− 1/p)−2L − 1 ) = ∏ p≤Ct+1 (1− 1/p)−2L = exp ( ∑ p≤Ct+1 log ( 1 +OL ( 1 p ))) = exp ( ∑ p≤Ct+1 OL ( 1 p )) = exp ( OL(log log(Ct+ 1)) ) exp (OL,γ(log log t)) (log t)OL,γ(1) L,γ t Therefore G(t) = t ∑ d≤Ct+1 s(d) d +O ( ∑ d≤Ct+1 s(d) ) L,γ 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 ≤ tγ and non-negative integers L1, L2, . . . , Lr we have∑ m≤t (C1m+ 1) L1(C2m+ 1) L2 . . . (Crm+ 1) Lr φ(C1m+ 1)L1φ(C2m+ 1)L2 . . . φ(Crm+ 1)Lrφ(m) L1,...,Lr,γ log t. (2.19) Proof. We proceed by induction. The case r = 1 is covered by Lemma 2.4. Suppose ∑ m≤t (C1m+ 1) L1(C2m+ 1) L2 ...(Crm+ 1) Lr φ(C1m+ 1)L1φ(C2m+ 1)L2 . . . φ(Crm+ 1)Lrφ(m) L1,...,Lr,γ log t. 15 2.3. Early Results By Cauchy–Schwarz (2.14), we get that(∑ m≤t (C1m+ 1) L1(C2m+ 1) L2 . . . (Cr+1m+ 1) Lr+1 φ(C1m+ 1)L1φ(C2m+ 1)L2 . . . φ(Cr+1m+ 1)Lr+1φ(m) )2 ≤ ∑ m≤t (C1m+ 1) 2L1(C2m+ 1) 2L2 . . . (Crm+ 1) 2Lr φ(C1m+ 1)2L1φ(C2m+ 1)2L2 . . . φ(Crm+ 1)2Lrφ(m) · ∑ m≤t (Cr+1m+ 1) 2Lr+1 φ(Cr+1m+ 1)2Lr+1φ(m) L1,...,Lr+1,γ 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 ≤ tγ and non-negative in- tegers L1, L2, ..., Lr, L we have∑ m≤t (C1m+ 1) L1(C2m+ 1) L2 ...(Crm+ 1) LrmL−1 φ(C1m+ 1)L1φ(C2m+ 1)L2 . . . φ(Crm+ 1)Lrφ(m)L L1,...,Lr,L,γ log t. (2.20) Proof. Once again we’ll use Cauchy–Schwarz (2.14) and the previous lem- mas.(∑ m≤t (C1m+ 1) L1(C2m+ 1) L2 . . . (Crm+ 1) LrmL−1 φ(C1m+ 1)L1φ(C2m+ 1)L2 . . . φ(Crm+ 1)Lrφ(m)L )2 ≤ ∑ m≤t (C1m+ 1) 2L1(C2m+ 1) 2L2 . . . (Crm+ 1) 2Lr φ(C1m+ 1)2L1φ(C2m+ 1)2L2 . . . φ(Crm+ 1)2Lrφ(m) · ∑ m≤t m2L−2 φ(m)2L−1 L1,...,Lr,L,γ 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/λk(n)) will come from log(φk(n)/λk(n)). Estimating this term will involve a summation over prime powers which divide each of φk(n) and λk(n). It turns out that the largest contribution to this term will come from small primes which divide φk(n). By small, we mean primes q ≤ (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 φk(n) and the second involves the large primes whose prime powers divide φk(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.∑ q>yk νq(φk(n))=1 (νq(φk(n))− νq(λk(n))) log q ykψ(x) for almost all n ≤ x. Proposition 3.2. ∑ q>yk νq(φk(n))≥2 νq(φk(n)) log q ykψ(x) for almost all n ≤ x. Since the main contribution will come from small primes dividing φk(n), the next proposition will show that the contribution of small primes dividing λk(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. ∑ q≤yk νq(λk(n)) log q ykψ(x) for almost all n ≤ x. That will leave us with the contribution of small primes dividing φk(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 ≥ 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) = ∑ p1|n ∑ p2|p1−1 · · · ∑ pk|pk−1−1 ∑ q≤yk νq(pk − 1) log q. The following proposition shows that the difference between the sum involv- ing the small primes dividing φk(n) and the term hk(n) is small. Proposition 3.5.∑ q≤yk νq(φk(n)) log q = hk(n) +O(y k−1 log y · ψ(x)) for almost all n ≤ x. That leaves us with log(φk(n)/λk(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–Kubilius inequality (Corollary A.2) which will show the final proposition. Proposition 3.6. hk(n) = 1 (k − 1)!y k log y +O(yk) for almost all n ≤ 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/λk(n)). log ( n λk(n) ) = log ( n φ(n) ) + log ( φ(n) φ2(n) ) + · · ·+ log ( φk−1(n) φk(n) ) + log ( φk(n) λk(n) ) . (3.1) Using the lower bound φ(m) m/ log logm from [17, Theorem 2.3] we have that log ( n φ(n) ) + log ( φ(n) φ2(n) ) + · · ·+ log ( φk−1(n) φk(n) ) log log log n. (3.2) Inserting equation (3.2) into equation (3.1) yields log ( n λk(n) ) = log ( φk(n) λk(n) ) +O(log log log n). In fact we could have used a more precise estimate for φi(n)/φi+1(n) for i ≥ 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 ( φk(n) λk(n) ) = ∑ q>yk (νq(φk(n))− νq(λk(n))) log q + ∑ q≤yk (νq(φk(n))− νq(λk(n))) log q = ∑ q>yk νq(φk(n))=1 (νq(φk(n))− νq(λk(n))) log q + ∑ q>yk νq(φk(n))≥2 (νq(φk(n))− νq(λk(n))) log q + ∑ q≤yk νq(φk(n)) log q − ∑ q≤yk νq(λk(n)) log q. Note that if a | b, then λ(a) | φ(b) since λ(a) | φ(a) | φ(ma) for any integer m. This quickly implies that λk(n) always divides φk(n) for all k and so we get 0 ≤ ∑ q>yk νq(φk(n))≥2 (νq(φk(n))− νq(λk(n))) log q ≤ ∑ q>yk νq(φk(n))≥2 (νq(φk(n)) log q. 19 3.2. Prime Power Divisors of φk(n) Using Propositions 3.1,3.2,3.3 and 3.5 we get log ( n λk(n) ) = hk(n) +O ( ykψ(x) ) for almost all n ≤ x. Finally by using Proposition 3.6 we get log ( n λk(n) ) = 1 (k − 1)!y k log y +O ( ykψ(x) ) for almost all n ≤ x, finishing the proof of Theorem 1.4. 3.2 Prime Power Divisors of φk(n) For various reasons thoughout this paper, we are concerned with the number of n ≤ x such that qa can divide φk(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 ∈ Pq2 , p2 ∈ Pp1 , p3 ∈ Pp2 , ..., pl ∈ Ppl−1 where pl | n. By using Lemma 2.2 we know the number of such n ≤ x is Ol(xyl/q2). Cases 1 and 2 deal with any case where p ∈ 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 φk(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 ⊆ 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 ∈ L1,1 ∪ L1,2, there exists a unique prime r ∈ L2,1 such that r ∈ Pp. In other words p will divide φ(r) and hence the primes in L2,1 will create the primes in L1,1∪L1,2. Level (2,2) (New primes in Pq) L2,2 ⊆ Pq. 20 3.2. Prime Power Divisors of φk(n) In general for all 1 < h ≤ k we have for all p ∈ Lh−1,1 ∪ Lh−1,2 there exists a unique prime r ∈ Lh,1 such that r ∈ Pp,Lh,2 is an arbitrary subset of Pq, and r ∈ Lk,1 ∪ Lk,2 ⇒ 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 | φ3(n) would be s1, s2, s3, r3, r4 ∈ Pq where r1 ∈ Ps1 , r2 ∈ Ps2s3 , p1 ∈ Pr1r2 , p2 ∈ 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 ∈ Pq where r1 ∈ Ps1 , r2 ∈ Ps3 , p1 ∈ Pr1r2 , p2 ∈ Pr3r4 , with p1p2 | n. Let p be a prime in Lh,i which we need to divide φk−h+1(n). The def- inition of Lh,i ensures that there is a unique prime r dividing φk−h(n) for which p | r− 1. The primes in levels (k, 1), (k, 2) dividing n are for the base case of the recursion, so that each prime divides φ0(n) = n. When i = 2 we are introducing new primes to get greater powers of q in φk(n). Note that it’s not necessary to have any primes on the levels (h, 2). In fact the “worst case scenario” that we will see has no primes on these except Level (1,2). Now that we’ve described the way to get qa | φk(n), what is our exponent a? Let mh,i = #Lh,i. From the recursion above we can see that qmk,2 | φ(n) and so do the primes in Lk−1,1. For the second iteration of φ, qmk,2−1+mk−1,2 | φ2(n) and so do the primes in Lk−2,1. Hence the power of q which divides φk(n) is max 1≤j≤k (m1,1 + ∑ 2≤h≤j (mh,2 − 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−1 and hence q - φj( ∏ Lj,2 p). Without loss of generality, we can assume the former, since the later is a subincarnation of the former. Now we’ll 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 φk(n) the total number of new primes introduced at the levels (h, 2) and H be the maximum necessary level (h, 2). Specifically M = ∑ h (mh,1 +mh,2) N = ∑ h≤H mh,2 and H yields the maximum value in (3.3). Note that under this notation, qN−H+1 | φk(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 = ∅ 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 φ3(n) is 5− 2 + 1 = 4 as expected. Now that we’ve described Case 3, how many possible n are in that case? Lemma 3.9. The number of n ≤ 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 ∪ Lh,2. We use Brun-Titchmarsh (2.10) for all the primes at each level of Case 3, so the number of n is ∑ n≤x ∑ p1∈L1 ∑ p2∈L2 · · · ∑ pk∈Lk 1 = ∑ p1∈L1 ∑ p2∈L2 · · · ∑ pk∈Lk ∑ pk|n n≤x 1 ∑ p1∈L1 ∑ p2∈L2 · · · ∑ pk∈Lk x∏ pk∈Lk pk . Note that we have repeatedly counted the same primes in the sum as we can reorder the primes in each level. It won’t be important here, but will need to be more carefully addressed later. Since the primes in level (k, 1) gave us some pk ∈ Ppk−1 for all the primes in Lk−1, and for p ∈ Lk,2 we have p ∈ Pq. By Brun–Titchmarsh (2.10) we get that the above sum is ∑ p1∈L1 ∑ p2∈L2 · · · ∑ pk−1∈Lk−1 x(cy)mk,1+mk,2∏ pk−1∈Lk−1 pk−1q mk,2 . 22 3.3. Large Primes Dividing φk(n) Once again we get mk−1,1 + mk−1,2 new applications of Brun-Titchmarsh giving the new primes in level k − 2 as well as mk−1,2 new powers of q. Continuing along in this manner we get: ∑ p1∈L1 x(cy) ∑ 2≤i≤k(mi,1+mi,2)∏ p1∈L1 p1q ∑ 2≤i≤kmi,2 x(cy) ∑ 1≤i≤k(mi,1+mi,2) q ∑ 1≤i≤kmi,2 = x(cy)M qN . The last thing we’ll consider in this section about the ways to obtain φk(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 ∈ Pp2 , p2 ∈ Pp3 . . . pk−1 ∈ 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 φk(n) In this section we will prove the two propositions dealing with q being large. We’ll start with the proposition where νq(φk(n)) = 1. Proof of Proposition 3.1. It suffices to show∑ n≤x ∑ q>yk νq(φk(n))=1 (νq(φk(n))− νq(λk(n))) log q xyk as then there are at most O ( xyk ykψ(x) ) = O ( x ψ(x) ) such n where the bound for the sum in Proposition 3.1 fails to hold. We examine the cases where νq(φk(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 ≤ k. Since mh,1 ≤ mh−1,1 + mh−1,2 we get mh,1 ≤ 1 for all 1 ≤ h ≤ k. Hence mh,1 = 1 for all h ≤ k. Therefore we are left with the case 23 3.3. Large Primes Dividing φk(n) p1 ∈ Pq, p2 ∈ Pp1 , p3 ∈ Pp2 , . . . , pk ∈ Ppk−1 where pk | n. However in this case we also get νq(λk(n))) = 1 giving us no additions to our sum. Suppose N > 1, then by repeatedly using mh,1 ≤ mh−1,1 + mh−1,2 we have M = ∑ h(mh,1 + mh,2) ≤ k ∑ hmh,2 = kN. The number of cases we get are O ( cM xyM qN ) c MxykN qN c Mxy2k q2 since y > qk. Since vq(φk(n)) = N −H + 1 and H ≤ k, we conclude N ≤ k implying that M ≤ 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 ∑ q>yk ∑ n≤x νq(φk(n))=1 (νq(φk(n))− νq(λk(n))) log q ≤ ∑ q>yk ∑ n≤x νq(φk(n))=1 N>1 log q ∑ q>yk xy2k log q q2 xyk by (2.4). We turn our attention to vq(φk(n)) > 1. We have to be more careful here since we can’t guarantee that the number of incarnations of Case 3 is Ok(1). We’ll 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 ≤ x such that Case 1,2 or Case 3 where M ≤ k(N − 1) occurs. Then #Sq 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 ) c Mxyk q2 24 3.3. Large Primes Dividing φk(n) such n since M ≤ k(N − 1) and q > yk. It remains to show we only require Ok(1) such incarnations. Suppose n satisfies an incarnation with M ≤ k(N − 1). Then it also satisfies a minimal incarnation with M ≤ k(N − 1) since removing a string of p1 ∈ Pp2 , p2 ∈ Pp3 . . . pk−1 ∈ 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 −2) < M ≤ k(N −1) 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 − 2) < M ≤ k(N − 1) since if we eliminate all primes in the Li,2 but 1, then M > k(N − 1). Also note that the condition mh,1 ≤ mh−1,1 +mh−1,2 forces M ≤ kN. If M is bounded between k(N −2) 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 − 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) = ⋃ q>yk Sq. Using Lemma 3.11 we have #S ≤ ∑ q>yk #Sq ∑ q>yk xyk q2 xyk ∑ q>yk 1 q2 xy k log(yk)yk x ψ(x) by (2.5). As for the n with n /∈ S and a = νq(φk(n)) > 1, the only remaining case is that M > k(N − 1). Recall that a = N + H − 1. If H = 1, then N = m1,2 = a. This implies m2,1 = a− 1 or a, since otherwise for k ≥ 2, M = ∑ h mh,1 ≤ a+(k−1)m2,1 ≤ a+(k−1)(a−2) = k(a−1)−k+2 ≤ (k−1)N leading to a contradiction. If H > 1, then we again wish to show that m2,1 ≥ a− k. M = ∑ h (mh,1 +mh,2) ≤ km1,2 + (k − 1) ∑ h>1 mh,2 = m1,2 + (k − 1)N = k(N − 1)−N + k +m1,2 25 3.3. Large Primes Dividing φk(n) which implies m1,2 > N − k and so ∑ h>1mh,2 = N −m1,1 < k. Therefore if m2,1 < a− k, then M = ∑ h (mh,1 +mh,2) ≤ m1,2 + (k − 1)m2,1 + (k − 1) ∑ h>1 mh,2 ≤ a+ (k − 1)(a− k − 1) + (k − 1)(k − 1) = ak − 2k ≤ k(N − 1) as N > a again leading to a contradiction. Hence m2,1 ≥ a − k and so we conclude ∑ n/∈S n≤x ∑ q>yk νq(φk(n))>1 (νq(φk(n)) log q ≤ 2 ∑ n/∈S n≤x ∑ q>yk νq(φk(n))>1 (νq(φk(n))− 1) log q ∑ q>yk log q ∑ a≥2 a ∑ n≤x n/∈S νq(φk(n))=a 1. Unfortunately, just blindly using the Brun-Titchmarsh inequality in (2.10) won’t be good enough as we must sum over all a. Let g(a, k) = (a − k)! if a ≥ k or 1 otherwise and note that since we have m1,2 ≥ a− k, we have at least g(a, k) permutations of the same primes. Thus by using Lemma 3.9 we get a ∑ q>yk log q ∑ n≤x n/∈S νq(φk(n))=a 1 a x(cy) M qNg(a, k) ac k(a+k−1)xy2k q2g(a, k) using the assumption that q > yk and M ≤ kN ≤ k(a + k − 1). Hence we get that our sum is ∑ n/∈S n≤x ∑ q>yk νq(φk(n))>1 (νq(φk(n)) log q ∑ q>yk log q ∑ a≥2 ack(a+k−1)xy2k q2g(a, k) = xy2k ∑ q>yk log q q2 ∑ a≥2 ack(a+k−1) g(a, k) 26 3.4. Small Primes Dividing λk(n) However the latter sum converges to some function depending on k, and so we get xy2k ∑ q>yk log q q2 xyk by (2.4). 3.4 Small Primes Dividing λk(n) We now turn our attention to the bound involving λk(n) in the summand. Just like when we were dealing with the number of cases where qa | φk(n), we will need a lemma to deal with the number of cases where qa | λk(n). Fortunately this case is much simpler as the only two ways for qa | λ(n) is for qa+1 | n or for there to exist p | n with p ∈ Pqa . Note that these conditions aren’t sufficient, but are necessary when q = 2. Lemma 3.12. The number of positive integers n ≤ x for which qa | λk(n) is O(xy k qa ). Proof. We’ll proceed by induction on k. If k = 1, then qa | λ(n) if qa+1 | n or p ∈ Pqa with p | n. The number of such n is at most∑ n≤x qa+1|n 1 + ∑ n≤x p∈Pqa p|n 1 x qa+1 + ∑ p∈Pqa x p x qa+1 + xy qa xy qa . using (2.10). Suppose the number of n ≤ x for which qa | λk−1(n) is O(xy k−1 qa ). If q a | λk(n), then either qa+1 | λk−1(n) or p ∈ Pqa with p | λk−1(n). Hence the number of such n is bounded by ∑ n≤x qa+1|λk−1(n) 1 + ∑ n≤x p∈Pqa p|λk−1(n) 1 xy k−1 qa+1 + ∑ p∈Pqa xyk−1 p xy k−1 qa+1 + xyk qa xy k qa as needed. Proof of Proposition 3.3. Like in the proof of previous propositions, we’ll show ∑ n≤x ∑ q≤yk νq(λk(n)) log q xyk. 27 3.5. Reduction to hk(n) for Small Primes The left hand side is equal to∑ n≤x ∑ q≤yk νq(λk(n)) log q = ∑ n≤x ∑ q≤yk log q ∑ a∈N qa|λk(n) 1 ≤ ∑ n≤x ∑ q≤yk log q ∑ a∈N qa≤yk 1 + ∑ n≤x ∑ q≤yk log q ∑ a∈N qa|λk(n) qa>yk 1. The first sum is∑ n≤x ∑ q≤yk log q ∑ a∈N qa≤yk 1 = ∑ n≤x ∑ m≤yk Λ(m) ∑ n≤x yk xyk, using the definition of Λ(m) and equation (2.1). Using Lemma 3.12, the geometric estimate in (2.6) and equation (2.1) the second sum becomes ∑ n≤x ∑ q≤yk log q ∑ a∈N qa|λk(n) qa>yk 1 ∑ q≤yk log q ∑ a∈N qa>yk xyk qa ∑ q≤yk log q xyk yk xyk. 3.5 Reduction to hk(n) for Small Primes The small primes dividing φk(n) are what contributes to the asymptotic term of log(n/λk(n)). In this section we show that the important case is the supersquarefree case of p dividing φk(n) which is when p ≺ p1 ≺ p2 ≺ · · · ≺ pk, pk | n. For this reason we will approximate the sum ∑ q≤yk vq(φk(n)) log q with hk(n) = ∑ p1|n ∑ p2|p1−1 · · · ∑ pk|pk−1−1 ∑ q≤yk νq(pk − 1) log q. (3.4) Proof of Proposition 3.5. For any fixed prime q, we know that vq(φ(m)) = max{0, vq(m)− 1}+ ∑ p|m vq(p− 1), 28 3.5. Reduction to hk(n) for Small Primes which implies∑ p|m vq(p− 1) ≤ vq(φ(m)) ≤ vq(m) + ∑ p|m vq(p− 1). Repeated use of this inequality for m = φl(n) where l ranges from k − 1 to 0 yields ∑ p|φk−1(n) vq(p− 1) ≤ vq(φk(n)) ≤ ∑ p|φk−1(n) vq(p− 1) + ∑ p|φk−2(n) vq(p− 1) + · · ·+ ∑ p|φ(n) vq(p− 1) + vq(n). (3.5) A prime p divides φk−1(n) either in the supersquarefree case (ssf), or not in the supersquarefree case (nssf), yielding ∑ ssf vq(p− 1) ≤ ∑ p|φk−1(n) vq(p− 1) ≤ ∑ ssf vq(p− 1) + ∑ nssf vq(p− 1). Combining this inequality with (3.5) yields∑ ssf vq(p− 1) ≤ vq(φk(n)) ≤ ∑ ssf vq(p− 1) + ∑ nssf vq(p− 1) + ∑ p|φk−2(n) vq(p− 1) + · · ·+ ∑ p|φ(n) vq(p− 1) + vq(n). Subtracting the sum over the supersquarefree case, multiplying through by log q and summing over q ≤ yk yields 29 3.5. Reduction to hk(n) for Small Primes 0 ≤ ∑ q≤yk νq(φk(n)) log q − hk(n) ≤ ∑ q≤yk ∑ nssf vq(p− 1) log q + ∑ q≤yk ∑ p|φk−2(n) vq(p− 1) log q + · · ·+ ∑ q≤yk ∑ p|n vq(p− 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 ∑ n≤x ∑ q≤yk ∑ p|φm(n) vq(p− 1) log q = ∑ n≤x ∑ q≤yk ∑ p|φm(n) ∑ a∈N qa|p−1 log q = ∑ n≤x ∑ q≤yk log q ∑ a∈N ∑ p∈Pqa p|φm(n) 1, we’ll split the sum over values of p ≤ yk−1 and p > yk−1. For p ≤ yk−1 we uniformly get for all n that ∑ q≤yk log q ∑ a∈N ∑ p∈Pqa p≤yk−1 p|φm(n) 1 ≤ ∑ q≤yk log q ∑ a∈N pi(yk−1; qa, 1) ∑ q≤yk log q ∑ a∈N yk−1 φ(qa) yk−1 ∑ q≤yk log q q yk−1 log y using the geometric estimate (2.6) and the prime number theorem for arith- metic progressions. As for p > yk−1 we fix an M and N from case 3 for which p | φm(n), of which there are at most Ok(1) such M,N since vp(φ(m)) = 1. Therefore 30 3.5. Reduction to hk(n) for Small Primes ∑ n≤x ∑ q≤yk log q ∑ a∈N ∑ p>yk−1 p∈Pqa p|φm(n) 1 ∑ q≤yk log q ∑ a∈N ∑ p∈Pqa p>yk−1 xyM pN ≤ ∑ q≤yk log q ∑ a∈N ∑ p∈Pqa xyM−(k−1)(N−1) p ∑ q≤yk log q ∑ a∈N xyM−(k−1)(N−1)+1 qa ∑ q≤yk xyM−(k−1)(N−1)+1 log q q xyM−(k−1)(N−1)+1 log yk xyM−(k−1)(N−1)+1 log y. Since the M,N were chosen for φm(n) we know that M ≤ mN where equal- ity holds if and only if we are in the supersquarefree case. Now either m ≤ k − 2 or m = k − 1 and we are not in the supersquarefreecase. In the former case we have an error of O(xy(k−2)N−(k−1)(N−1)+1 log y) = O(xyk−N log y) = O(xyk−1 log y) since N ≥ 1, or in the latter case O(xy(k−1)N−1−(k−1)(N−1)+1 log y) = O(xyk−1 log y). Thus we get ∑ n≤x ( ∑ q≤yk ∑ nssf vq(p− 1) log q + ∑ q≤yk ∑ p|φk−2(n) vq(p− 1) log q + . . . + ∑ q≤yk ∑ p|n vq(p− 1) log q ) xyk−1 log y and so 31 3.6. Reduction to the First and Second Moments ∑ q≤yk ∑ nssf vq(p− 1) log q + ∑ q≤yk ∑ p|φk−2(n) vq(p− 1) log q + . . . + ∑ q≤yk ∑ p|n vq(p− 1) log q yk−1 log y · ψ(x) for almost all n ≤ x as required. 3.6 Reduction to the First and Second Moments The Turán-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∑ n≤x |f(n)−M1(x)|2 ≤ CxM2(x) (3.6) where M1(x) = ∑ p≤x|f(p)|/p and M2(x) = ∑ p≤x|f(p)|2/p. Since hk(n) is strongly additive we apply this inequality where M1(x) = ∑ p≤x hk(p)/p, M2(x) = ∑ p≤x hk(p) 2/p. We will need to find bounds on M1 and M2 there- fore it’s our goal to prove the following two propositions: Proposition 3.13. For all x > ee e , M1(x) = 1 (k − 1)!y k log y +O(yk) Proposition 3.14. For all x > ee e , M2(x) y2k−1 logk−1 y. These will lead to a proof of Proposition 3.6. Proof of Proposition 3.6. Let N denote the number of n ≤ x for which |hk(n) −M1(x)| > yk. The contribution of such n to the sum in (3.6) is at least Ny2k. Thus Proposition 3.14 implies N x logk−1 y/y and so Propo- sition 3.13 implies that hk(n) = 1 (k−1)!y k log y+O(yk) except for a set of size O(x(log y)k−1/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–written 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 ≤ l ≤ k. Let t > ee be a real number and let constants α, α1, α2 satisfy 0 < α < 1/2 and 0 < α1 < α2 < 1/2. (a) If b > tα, then ∑ pk∈Pb ∑ pk−1∈Ppk · · · ∑ p2∈Pp3 pi(t; p2, 1) t log t(log log t) k−2 b . (3.7) (b) If b ≤ tα1 , then ∑ pl∈Pb pl>t α2 ∑ pl−1∈Ppl · · · ∑ p2∈Pp3 pi(t; p2, 1) b l−1t φ(b)l log t . (3.8) (c) If b ≤ tα1 , then ∑ pl∈Pb ∑ pl−1∈Ppl · · · ∑ p2∈Pp3 pi(t; p2, 1) t(log log t) l−1 φ(b) log t . (3.9) The implicit constants in (a)− (c) depend on the choices of the α. Proof. For (3.7) we just use the trivial estimate pi(t; p2, 1) ≤ t/p2 and several 33 3.7. Summations Involving pi(t, p, 1) uses of Brun-Titchmarsh (2.10) to get∑ pk∈Pb ∑ pk−1∈Pk · · · ∑ p2∈P3 pi(t; p2, 1) ≤ ∑ pk∈Pb ∑ pk−1∈Pk · · · ∑ p2∈P3 t p2 t ∑ pk∈Pb ∑ pk−1∈Pk · · · ∑ p3∈P4 log log t p3 t ∑ pk∈Pb (log log t)k−2 pk ≤ t ∑ m≡1 (mod b) tα≤m≤t (log log t)k−2 m ≤ t log t(log log t) k−2 b where m > 1 and m ≡ 1 (mod b) imply that m > b and by using (2.7). As for (3.8) we get∑ pl∈Pb l>tα2 ∑ pl−1∈Pl · · · ∑ p2∈P3 pi(t; p2, 1) = ∑ pl∈Pb l>tα2 ∑ pl−1∈Pl · · · ∑ p3∈P4 #{(m1, p2) : p2 = 1 (mod p3), p2 > tα2 , m1p2 + 1 ≤ t, p2,m1p2 + 1 prime} = ∑ pl∈Pb l>tα2 ∑ pl−1∈Pl · · · ∑ p4∈P5 #{(m1,m2, p3) : p3 = 1 (mod p4), p3 > tα2 , m1(m2p3 + 1) + 1 ≤ t, {p3,m2p3 + 1,m1(m2p3 + 1) + 1} prime} = #{(m1,m2, . . . ,ml−1, pl) : pl = 1 (mod b), pl > tα2 , m1(m2 . . . (ml−2(ml−1pl + 1) + 1) + · · ·+ 1 ≤ t, {pl,ml−1pl + 1, ml−2(ml−1pl + 1) + 1, . . . , m1(m2 . . . (ml−2(ml−1pl + 1) + 1) + · · ·+ 1} prime} ≤ ∑ m1...ml−1≤t1−α2 #{pl < t/m1 . . .ml−1 : pl = 1 (mod b), {pl,ml−1pl + 1,ml−2(ml−1pl + 1) + 1, . . . , m1(m2...(ml−2(ml−1pl + 1) + 1) + · · ·+ 1} prime}. 34 3.7. Summations Involving pi(t, p, 1) From here will need to use Brun’s Sieve method (see [12, Theorem 2.4]) to get that #{pl <t/m1 . . .ml−1 : pl = 1 (mod b), {pl,ml−1pl + 1,ml−2(ml−1pl + 1) + 1, . . . ,m1(m2 . . . (ml−2(ml−1pl + 1) + 1) + · · ·+ 1} prime} E l−1 φ(E)l−1 bl−1 φ(b)l−1 bc1 . . . cl−1 φ(bc1 . . . cl−1) t/m1 . . .ml−1b (log t/m1 . . .ml−1b)l where the ci and E are E = ( l−1∏ i=1 m i(i+1)/2 i ) (1 +m1 +m1m2 + · · ·+m1 . . .ml−3)(1 +m2 +m2m3 + · · ·+m2 . . .ml−3) . . . (1 +ml−3)(1 +m1 +m1m2 + . . . +m1 . . .ml−4)(1 +m2 +m2m3 + · · ·+m2 . . .ml−4) . . . (1 +ml−4) . . . (1 +m1) and for 1 ≤ i ≤ l − 1, ci = 1 +mi +mimi+1 + · · ·+mi . . .ml−2, cl−1 = 1. Using φ(mn) ≥ φ(m)φ(n) and m1 . . .ml−1b ≤ t1+α1−α2 where 1+α1−α2 < 1 we get E l−1 φ(E)l−1 bl−1 φ(b)l c1 φ(c1) . . . cl−1 φ(cl−1) t m1 . . .ml−1(log t)l . Using mL φ(mL) = m φ(m) , we get the sum is ∑ m1...ml−1≤t1−α2 El−1 φ(E)l−1 c1 φ(c1) . . . cl−1 φ(cl−1) 1 m1 . . .ml−1 = ∑ m1...ml−1≤t1−α2 (E∗)l−1 φ(E∗)l−1 c1 φ(c1) . . . cl−1 φ(cl−1) 1 m1 . . .ml−1 where 35 3.7. Summations Involving pi(t, p, 1) E∗ =(1 +m1 +m1m2 + · · ·+m1 . . .ml−3)(1 +m2 +m2m3 + · · ·+ m2 . . .ml−3) . . . (1 +ml−3)(1 +m1 +m1m2 + · · ·+m1 . . .ml−4) (1 +m2 +m2m3 + · · ·+m2 . . .ml−4) . . . (1 +ml−4) . . . (1 +m1). We have that every factor in E∗ as well as the ci are of the form 1+Cmi for some i or of the form mLi . Hence using l−1 applications of Lemmas 2.3, 2.5 or 2.6 we can pick off the factors of the form (1 + Cmi) one at a time. Let E(e), c (e) i denote the E ∗ and ci terms with the factors of the form 1 + Cm1 through 1 + Cme removed. ∑ m1...ml−1≤t1−α2 El−1 φ(E)l−1 c1 φ(c1) ... cl−1 φ(cl−1) 1 m1 . . .ml−1 ∑ m2...ml−1≤t1−α2 (E′)l−1 φ(E′)l−1 c′1 φ(c′1) . . . c′l−1 φ(c′l−1) 1 m2 . . .ml−1 (log t) ∑ m3...ml−1≤t1−α2 (E′′)l−1 φ(E′′)l−1 c′′1 φ(c′′1) . . . c′′l−1 φ(c′′l−1) 1 m3 . . .ml−1 (log2 t) · · · (log t)l−1. Note that the C are at most 1 + t+ t2 + · · ·+ tk−3 ≤ tk−2 and l ≤ k so the implied constant only depends on k. Therefore ∑ pl∈Pb l>tα2 ∑ pl−1∈Pl · · · ∑ p2∈P3 pi(t; p2, 1) tb l−1 φ(b)l(log t)l (log t)l−1 = tbl−1 φ(b)l log t . As for part (c), first note that b/φ(b) log log b, so for pl > tα2 , we get that part (b) implies our bound. As for pl ≤ tα2 we’ll split it into cases where p3 is less than or greater than tα2 . If p3 ≤ tα2 , then 36 3.7. Summations Involving pi(t, p, 1) ∑ pl∈Pb pl≤tα2 ∑ pl−1∈Pl · · · ∑ p2∈P3 p2≤tα2 pi(t; p2, 1) ∑ pl∈Pb pl≤tα2 ∑ pl−1∈Pl · · · ∑ p2∈P3 p2≤tα2 t φ(p2) log t/p2 ∑ pl∈Pb pl≤tα2 ∑ pl−1∈Pl · · · ∑ p2∈P3 p2≤tα2 t p2 log t ∑ pl∈Pb t(log log t)l−2 pl log t t(log log t) l−1 φ(b) log t If p3 > t α2 , then since b ≤ tα2 there is a minimum m such that pm ≤ tα2 . So using part (b) with l = m we get ∑ pl∈Pb pl≤tα2 ∑ pl−1∈Pl · · · ∑ p2∈P3 p2>tα2 pi(t; p2, 1) ∑ pl∈Pb pl≤tα2 ∑ pl−1∈Pl · · · ∑ pm+1∈Pm+2 (pm−1)m−1t φ(pm−1)m log t ∑ pl∈Pb pl≤tα2 ∑ pl−1∈Pl · · · ∑ pm+1∈Pm+2 t pm−1 log t t(log log t) l−m φ(b) log t t(log log t) l−1 φ(b) log t since m ≥ 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’ll 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α1 < α2 < 1/2. Then (a) If b1 > t α1 or b2 > t α1 then∑ p2∈Pb1 r2∈Pb2 pi(t; p2r2, 1) t log 2 t b1b2 . (3.10) 37 3.7. Summations Involving pi(t, p, 1) (b) If neither b1 nor b2 exceeds t α1 , then ∑ pk∈Pb1 rk∈Pb2 pkrk>t α2 ... ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1) t(log log t) k−1bk−12 φ(b1)φ(b2)k log t + t(log log t)k−1bk−11 φ(b2)φ(b1)k log t . (3.11) (c) If neither b1 nor b2 exceeds t α1 , then ∑ pk∈Pb1 rk∈Pb2 ... ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1) t(log log t) 2k−2 φ(b1)φ(b2) log t . (3.12) (d) If neither b1 nor b2 exceeds t α1 , then ∑ pk∈Pb1 rk∈Pb2 ... ∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3∩Pr3 pi(t; s, 1) t(log log t) 2k−2 φ(b1)φ(b2) log t . (3.13) Again the implicit constants depend on our choice of the α. 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 ≤ rk, then∑ pk∈Pb1 rk∈Pb2 pk≤rk pkrk>t α2 ... ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1) = ∑ pk∈Pb1 rk∈Pb2 pkrk>t α2 · · · ∑ p3∈Pp4 r3∈Pr4 #{(m1, p2, r2) : p2 = 1 (mod p3), r2 = 1 (mod r3), r2p2 > t α2 ,m1r2p2 + 1 ≤ t, p2,m1r2p2 + 1 prime} = ∑ pk∈Pb1 pk≤rk ∑ pk−1∈Pk · · · ∑ p2∈P3 ∑ rk∈Pb2 pkrk>t α2 ∑ rk−1∈Prk · · · ∑ r4∈Pr5 #{(m1,m2, r3) : r3 = 1 (mod r4), r3p2 > t α2 ,m1p2(m2r3 + 1) + 1 ≤ t, {r3,m2r3 + 1,m1p2(m2r3 + 1) + 1} prime} = ∑ pk∈Pb1 pk≤rk ∑ pk−1∈Pk · · · ∑ p2∈P3 #{(m1,m2, . . . ,ml−1, rl) : rl = 1 (mod b2), p2rk > t α2 ,m1p2(m2 . . . (mk−2(mk−1rk + 1) + 1) + · · ·+ 1 ≤ t, {rk,mk−1rk + 1,mk−2(mk−1rk + 1) + 1, . . . , m1p2(m2 . . . (mk−2(mk−1rk + 1) + 1) + · · ·+ 1} prime} ≤ ∑ m1...ml−1≤t1−α2 ∑ pk∈Pb1 pk≤rk ∑ pk−1∈Pk · · · ∑ p2∈P3 #{rk < t/p2m1...mk−1 : rk = 1 (mod b2), {rk,mk−1rk + 1,mk−2(mk−1rk + 1) + 1, . . . , p2m1(m2 . . . (mk−2(mk−1rk + 1) + 1) + · · ·+ 1} prime} Just like in Lemma 3.15 we use Brun’s Sieve. However, notice that we have almost the same set, except with m1 replaced with m1p2. Hence we have #{rk < t/p2m1 · · ·k−1 : rk = 1 (mod b1), {rk,mk−1rk + 1,mk−2(mk−1rk + 1) + 1, . . . , p2m1(m2 . . . (mk−2(mk−1rk + 1) + 1) + · · ·+ 1} prime} E k−1 φ(E)k−1 bk−12 φ(b2)k−1 b2c1 . . . ck−1 φ(b2c1 . . . ck−1) t/p2m1 . . .mk−1b2 (log t/p2m1 . . .mk−1b2)k 39 3.7. Summations Involving pi(t, p, 1) where the ci and E are E = p2 ( l−1∏ i=1 m i(i+1)/2 i ) (1 + p2m1 + p2m1m2 + ...+ p2m1 . . .mk−3) (1 +m2 +m2m3 + · · ·+m2 . . .mk−3) . . . (1 +mk−3) (1 + p2m1 + p2m1m2 + · · ·+ p2m1 . . .mk−4)(1 +m2 +m2m3 + · · ·+m2 . . .mk−4) . . . (1 +mk−4) . . . (1 + p2m1) and for 2 ≤ i ≤ k − 2, c1 = 1 + p2m1 + p2m1m2 + · · ·+ p2m1 . . .mk−2, ci = 1 +mi +mimi+1 + · · ·+mi . . .mk−2, ck−1 = 1. By the same methods as Lemma 3.15, using that p2/φ(p2) is bounded and noting that t p2m1...mk−1b2 > rk b1 > tα2/2−α1 = t for some > 0 since α2 > 2α1, we get that ∑ pk∈Pb1 rk∈Pb2 pkrk>t α2 · · · ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1) tb k−1 2 φ(b2)k log t ∑ pk∈Pb1 ∑ pk−1∈Pk · · · ∑ p2∈P3 1 p2 tb k−1 2 φ(b2)k log t ∑ pk∈Pb1 (log log t)k−2 pk t(log log t) k−1bk−12 φ(b1)φ(b2)k log t . The case for rk ≤ pk is similar. As for part (c), first note that bi/φ(bi) log log bi for i ∈ {1, 2}. taking care of the case where pkrk > tα2 . As for 40 3.8. Reduction of ∑ hk(p) to Small Values of pk pkrk ≤ tα2 we get∑ pk∈Pb1 rk∈Pb2 pkrk≤tα2 · · · ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1) ∑ pk∈Pb1 rk∈Pb2 pkrk≤tα2 · · · ∑ p2∈Pp3 r2∈Pr3 t φ(p2r2) log t/p2r2 ∑ pk∈Pb1 rk∈Pb2 pkrk≤tα2 · · · ∑ p2∈Pp3 r2∈Pr3 t p2r2 log t ∑ pk∈Pb1 rk∈Pb2 pkrk≤tα2 t(log log t)2k−4 pkrk log t t(log log t) 2k−2 φ(b1)φ(b2) log t using Brun-Titchmarsh (2.10), finishing part (c). As for part (d) we note that∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3∩Pr3 pi(t; s, 1) = ∑ p3∈Pp4 r3∈Pr4 #{(m1, s) : s = 1 (mod p3r3),m1s+ 1 ≤ t, s,m1s+ 1 prime} = ∑ p3∈Pp4 #{(m1,m2, r3) : r3 = 1 (mod r4),m1(m2p3r3 + 1) + 1 ≤ t, {m2p3r3 + 1,m1(m2p3r3 + 1) + 1 prime} and so on, yielding a similar sieve as part (b). 3.8 Reduction of ∑ hk(p) to Small Values of pk We will be using Euler Summation on the sum ∑ p≤t 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− 1. The following lemma will deal with those errors and will involve the Bombieri–Vinogradov Theorem (2.13). 41 3.8. Reduction of ∑ hk(p) to Small Values of pk Lemma 3.17. For all 2 ≤ l ≤ k, x > eee and v > ee,∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 ( pi(v, pk−l+2, 1) − li(v) pk−l+2 ) v log y log v + li(v)(log log v)l−2. Proof. Let E(t; r, 1) = pi(t; r, 1)− li(t)r−1 . Then we have∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 . . . ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 ( pi(v, pk−l+2, 1)− li(v) pk−l+2 − 1 ) = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 E(v; pk−l+2, 1) ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)|. Let Ω(m) denote the number of divisors of m which are primes or prime powers. We use the estimate Ω(m) logm to get 42 3.8. Reduction of ∑ hk(p) to Small Values of pk ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)| ≤ log(yk) ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)| ∑ pk−l+3|pk−l+2−1 p3≤v1/9 ∑ pk−l+4|pk−l+3−1 pk−l+4≤v1/27 · · · ∑ q≤yk ∑ a∈N qa|pk−1 1 ≤ log(yk) ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)| ∑ pk−l+3|pk−l+2−1 p3≤v1/9 ∑ pk−l+4|pk−l+3−1 pk−l+4≤v1/27 · · · ∑ pk≤v1/3k−1 pk|pk−1−1 Ω(pk − 1) log y ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)| ∑ pk−l+3|pk−l+2−1 p3≤v1/9 ∑ pk−l+4|pk−l+3−1 pk−l+4≤v1/27 · · · ∑ pk≤v1/3k−1 pk|pk−1−1 log v. Continuing in this manner we obtain∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)| log y(log v)l−1 ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 |E(v; pk−l+2, 1)| v log y log v using Bombieri–Vinogradov (2.13). As for the difference between∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 li(v) pk−l+2 − 1 43 3.8. Reduction of ∑ hk(p) to Small Values of pk and ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 li(v) pk−l+2 (3.14) we get that it is∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 li(v) pk−l+2(pk−l+2 − 1) ≤ ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∞∑ i=1 li(v) (ipk−l+3 + 1)(ipk−l+3) ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+3∈Ppk−l+4 pk−l+3≤v1/9 li(v) p2k−l+3 ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+3∈Ppk−l+4 pk−l+3≤v1/9 li(v) pk−l+3qa ∑ q≤yk log q ∑ a∈N li(v)(log log v)l−2 q2a ∑ q≤yk li(v)(log log v)l−2 log q q2 li(v)(log log v)l−2. The estimate used the Brun–Titchmarsh inequality (2.10), the inequality pk−l+3 ≥ qa and noting that the sum over q converges. Lemma 3.18. For all x > ee e and t > ee,∑ p≤t hk(p) = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤t1/3k−1 ∑ pk−1∈Ppk pk−1≤t1/3k−2 · · · ∑ p2∈Pp3 p2≤t1/3 pi(t; p2, 1) +O ( t1−1/3 k log t(log log t)k−2yk + t(log log t)k−2 log y log t ) . 44 3.8. Reduction of ∑ hk(p) to Small Values of pk Proof. For a prime p, hk(p) = ∑ p1|p ∑ p2|p1−1 · · · ∑ pk|pk−1−1 ∑ q≤yk νq(pk − 1) log q = ∑ p2|p−1 · · · ∑ pk|pk−1−1 ∑ q≤yk νq(pk − 1) log q since the only prime which can divide p is p itself. Hence ∑ p≤t hk(p) = ∑ p≤t ∑ p2|p−1 · · · ∑ pk|pk−1−1 ∑ q≤yk νq(pk − 1) log q = ∑ p≤t ∑ p2|p1−1 · · · ∑ pk|pk−1−1 ∑ q≤yk ∑ pk∈Pqa a∈N log q = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa ∑ pk−1∈Ppk · · · ∑ p2∈Pp3 ∑ p≤t p∈Pp2 1 = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa ∑ pk−1∈Ppk · · · ∑ p2∈Pp3 pi(t; p2, 1). We wish to approximate pi(t; p2, 1) by li(t) p2−1 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 ≤ t1/3i−1 and qa ≤ t1/3k . Using Lemma 3.15, we get for large qa ∑ q≤yk log q ∑ a∈N qa>t1/3 k ∑ pk∈Pqa ∑ pk−1∈Ppk · · · ∑ p3∈Pp2 pi(t; p2, 1) ∑ q≤yk log q ∑ a∈N qa>t1/3 k t log t(log log t)k−2 qa . By geometric estimates, if a∗ is the smallest a where qa > t1/3k , then we get that the above is bounded by 45 3.8. Reduction of ∑ hk(p) to Small Values of pk O ( t log t(log log t)k−2 ∑ q≤yk log q qa∗ ) t1−1/3k log t(log log t)k−2 ∑ q≤yk log q t1−1/3k log t(log log t)k−2yk. Now suppose qa ≤ t1/3k . Let l be the last index (supposing one exists) where pi > t 1/3i−1 By using (3.8) where l ranges from 2 to k, we can bound the large values of the pi. ∑ q≤yk log q ∑ a∈N qa≤t1/3k ∑ pk∈Pqa pk≤t1/3k−1 · · · ∑ pl+1∈Ppl+2 pl+1≤t1/3l ∑ pl∈Ppl+1 pl>t 1/3l−1 ∑ pl−1∈Ppl · · · ∑ p2∈Pp3 pi(t; p2, 1) ∑ q≤yk log q ∑ a∈N qa≤t1/3k ∑ pk∈Pqa pk≤t1/3k−1 · · · ∑ pl+2∈Ppl+3 pl+2≤t1/3l+1 ∑ pl+1∈Ppl+2 pl+1>t 1/3l pl−1l+1t φ(pl+1)l log t ∑ q≤yk log q ∑ a∈N qa≤t1/3k ∑ pk∈Pqa pk≤t1/3k−1 · · · ∑ pl+2∈Ppl+3 pl+2≤t1/3l+1 ∑ pl+1∈Ppl+2 pl+1>t 1/3l t pl+1 log t since pl is prime and l ≤ k. By Brun-Titchmarsh (2.10) we get ∑ q≤yk log q ∑ a∈N qa≤t1/3k t(log log t)k−l qa log t ∑ q≤yk t(log log t)k−l log q q log t t(log log t) k−2 log y log t 46 3.9. Evaluation of the Main Term by (2.3) and since l ≥ 2. Hence we get∑ p≤t hk(p) = ∑ q≤yk log q ∑ a∈N qa≤t1/3k ∑ pk∈Pqa pk≤t1/3k−1 ∑ pk−1∈Ppk pk−1≤t1/3k−2 · · · ∑ p2∈Pp3 p2≤t1/3 pi(t, p2, 1) +O ( t1−1/3 k log t(log log t)k−2yk + t(log log t)k−2 log y log t ) finishing the lemma. 3.9 Evaluation of the Main Term Now we’ll 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 ≤ l ≤ k and 2 ≤ u ≤ t. Then define gk,l(u) = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤u1/3l−1 ∑ pk−1∈Ppk pk−1≤u1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤u1/3 pi(u; pk−l+2, 1). Note that gk,k(t) is the summation in Lemma 3.18. Next we’ll exhibit a recursive formula satisfied by the gk,l. Lemma 3.20. Let 3 ≤ l ≤ k, then gk,l(v) = li(v) ∫ v1/3 2 1 u2 gk,l−1(u)du+O ( v(log log v)l−2 log y log v ) . (3.15) Proof. We’ll proceed by approximating pi by li and then use partial summa- tion to recover pi. Using Lemma 3.17 we get gk,l(v) = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 pi(v; pk−l+2, 1) = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 li(v) pk−l+2 +O ( v log y log v + li(v)(log log v)l−2 ) . 47 3.9. Evaluation of the Main Term We use Euler summation on the inner sum to get ∑ pk−l+2∈Ppk−l+3 pk−l+2≤v1/3 1 pk−l+2 = pi(v1/3; pk−l+3, 1) v1/3 + ∫ v1/3 2 pi(u; pk−l+3, 1) u2 du. Our function then becomes gk,l(v) = li(v) ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 . . . ∑ pk−l+3∈Ppk−l+4 pk−l+3≤v1/3 ( pi(v1/3; pk−l+3, 1) v1/3 + ∫ v1/3 2 pi(u; pk−l+3, 1) u2 du ) +O ( v log y log v + li(v)(log log v)l−2 ) . We trivially estimate pi(x; q, 1) by x/q inside the sum and then use Brun– Titchmarsh (2.10) to get ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+3∈Ppk−l+4 pk−l+3≤v1/3 pi(v1/3; pk−l+3, 1) v1/3 ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤v1/3l−1 ∑ pk−1∈Ppk pk−1≤v1/3l−2 · · · ∑ pk−l+3∈Ppk−l+4 pk−l+3≤v1/3 1 pk−l+3 ∑ q≤yk log q ∑ a∈N (log log v)l−2 qa ∑ q≤yk log q (log log v)l−2 q (log log v)l−2 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 ≤ l ≤ k. gk,l(u) = ku(log log u)l−1 log y (l − 1)! log u +O ( u(log log u)l−1 log u + u(log log u)l−2 log2 y log u ) which implies ∑ p≤t hk(p) = kt(log log t)k−1 log y (k − 1)! log t +O ( t(log log t)k−1 log t + t(log log t)k−2 log2 y log t + t1−1/3 k log t(log log t)k−2yk ) . Proof. The second formula is derived from the first by setting l = k, u = t and using Lemma 3.18. We’ll proceed with the first formula by induction on l. Using the estimates we obtained via Bombieri–Vinogradov (2.13) in Lemma 3.17, we have for l = 2 gk,2(u) = ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤u1/3 pi(u; pk, 1) = li(u) ∑ q≤yk log q ∑ a∈N ∑ pk∈Pqa pk≤u1/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) ∑ q≤yk log q ∑ a∈N ( log log u1/3 φ(qa) +O ( log(qa) φ(qa) )) +O ( u log y log u ) = li(u)(log log u+O(1)) ∑ q≤yk log q ∑ a∈N ( 1 qa +O ( 1 qa+1 )) +O ( li(u) ∑ q≤yk log2 q ∑ a∈N a qa ) +O ( u log y log u ) = li(u)(log log u+O(1)) ∑ q≤yk ( log q q +O ( log q q2 )) +O ( li(u) ∑ q≤yk 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) ∫ v1/3 2 1 u2 gk,l−1(u)du+O ( v(log log v)l−2 log y log v ) = li(v) ∫ v1/3 2 1 u2 ( ku(log log u)l−2 log y (l − 2)! log u +O ( u(log log u)l−2 log u + u(log log u)l−3 log2 y log u )) du+O ( v(log log v)l−2 log y log v ) = li(v) ∫ v1/3 2 ( k(log log u)l−2 log y (l − 2)!u log u +O ( (log log u)l−2 u log u + (log log u)l−3 log2 y u log u )) du+O ( v(log log v)l−2 log y log v ) = k li(v)(log log v1/3)l−1 log y (l − 1)! +O ( li(v)(log log v1/3)l−1 + li(v)(log log v1/3)l−2 log2 y + v(log log v)l−2 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−1 log y (l − 1)! log v +O ( v(log log v)l−1 log v + v(log log v)l−2 log2 y log v + v(log log v)l−2 log y log v ) = kv(log log v)l−1 log y (l − 1)! log v +O ( v(log log v)l−1 log v + v(log log v)l−2 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) = ∑ p≤x hk(p) p = ∑ p≤ee hk(p) p + ∑ ee<p≤x hk(p) p = O(1) + ∑ ee<p≤x hk(p) ( 1 x + ∫ x p dt t2 ) = O(1) + 1 x ∑ ee<p≤x hk(p) + ∫ x ee dt t2 ∑ ee<p≤t hk(p). Using t = x in Lemma 3.21 we get that∑ ee<p≤x hk(p) xy k−1 log y log x . Since ∑ ee<p≤t hk(p) and ∑ p≤t hk(p) differ by a constant, we get that 51 3.11. The Proof of the Second Moment M1(x) = O(1) + 1 x O ( xyk−1 log y log x ) + ∫ x ee dt t2 ( kt(log log t)k−1 log y (k − 1)! log t +O ( t(log log t)k−1 log t + t(log log t)k−2 log2 y log t + t1−1/3 k log t(log log t)k−2yk )) using Lemma 3.21. Noting that∫ x ee dt t2 t1−1/3 k log t(log log t)k−2yk = ∫ x ee ykdt t1+ yk, we conclude that M1(x) is O(yk) +O ( yk−1 log y log x ) + ∫ x ee dt t2 ( kt(log log t)k−1 log y (k − 1)! log t +O ( t(log log t)k−1 log t + t(log log t)k−2 log2 y log t )) = O(yk) + k(log log x)k log y k(k − 1)! +O ( (log log x)k + (log log x)k−1 log2 y ) = yk log y (k − 1)! +O(y k) as needed. 3.11 The Proof of the Second Moment We now turn our attention to the second moment. Our first lemma will bound the case where p3 = r3 and then we’ll use the summations from Lemma 3.16 to take care of the rest. 52 3.11. The Proof of the Second Moment Lemma 3.22.∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3∩Pr3 ∑ p≤t p∈Ps 1 t1−yk log y + t(log log t) 2k−2 log t log2 y for some > 0. Proof. Our sum is∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3∩Pr3 ∑ p≤t p∈Ps 1 = ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3r3 pi(t; s, 1). We split up into two cases. If qa11 q a2 2 > t α, then suppose qa11 > t α/2. (the other case is analogous) Thus p3r3 > t α/2. Hence Lemma 3.15 part (a) yields∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 >t α 2 ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3r3 pi(t; s, 1) ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 >t α 2 ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 t log t p3r3 ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 >t α 2 t log t(log log t)2k−4 qα11 q α2 2 . using Brun–Titchmarsh (2.10). By letting A = min{a|qa11 > t α 2 } we get ∑ q1,q2≤yk log q1 log q2 t log t(log log t)2k−4 qA1 q2 ≤ t1−α2 log t(log log t)2k−4 ∑ q1≤yk log q1 ∑ q2≤yk log q2 q2 t1−yk log y 53 3.11. The Proof of the Second Moment by equations (2.1) and (2.3). If qa11 q a2 2 ≤ tα, then by Lemma 3.16 part (d) we get∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 q a2 2 ≤tα ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 ∑ s∈Pp3r3 pi(t; s, 1) ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 q a2 2 ≤tα t(log log t)2k−2 qa11 q a2 2 log t ∑ q1,q2≤yk log q1 log q2 t(log log t)2k−2 q1q2 log t = t(log log t)2k−2 log t ( ∑ q≤yk log q q )2 t(log log t) 2k−2 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. ∑ p≤t hk(p) 2 = ∑ p≤x (∑ p1|p ∑ p2|p1−1 · · · ∑ pk|pk−1−1 ∑ q≤yk νq(pk − 1) log q )2 = ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p2∈Pp3 r2∈Pr3 ∑ p≤t p∈Pp2 p∈Pr2 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 ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk ... ∑ p2∈Pp3 r2∈Pr3 p2 6=r2 ∑ p≤t p∈Pp2 p∈Pr2 1 +O ( t1−yk log y + t(log log t)2k−2 log t log2 y ) . The sum becomes∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1). If qa11 > t α1 , then so is p2, and hence by (3.10) we get ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 >t α1 ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk · · · ∑ p3∈Pp4 r3∈Pr4 t log2 t p3r3 ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 >t α1 t log2 t(log log t)2k−4 qa11 q a2 2 t1−α1 log2 t(log log t)2k−4 ∑ q1,q2≤yk log q1 log q2 ∑ a2∈N 1 qa22 t1−α1 log2 t(log log t)2k−4 ∑ q1,q2≤yk log q1 log q2 q2 t1−α1 log2 t(log log t)2k−4(yk log y). We similarly get the same bound if qa22 > t α1 . If neither of qa11 , q a2 2 exceed tα1 , then by (3.12) and using that for bi = q ai i bi φ(bi) 1, 1 φ(bi) 1 bi , 55 3.11. The Proof of the Second Moment we get ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 ,q a2 2 ≤tα1 ∑ pk∈Pqa11 rk∈Pqa22 ∑ pk−1∈Ppk rk−1∈Prk . . . ∑ pi∈Ppi+1 ri∈Pri+1 ∑ pi−1∈Ppi ri−1∈Pri · · · ∑ p2∈Pp3 r2∈Pr3 pi(t; p2r2, 1) ∑ q1,q2≤yk log q1 log q2 ∑ a1,a2∈N q a1 1 ,q a2 2 ≤tα1 t(log log t)2k−2 qa11 q a2 2 log t t(log log t) 2k−2 log t ∑ q1,q2≤yk log q1 log q2 q1q2 t(log log t) 2k−2 log2 y log t . The above gives us ∑ p≤t hk(p) 2 t1−yk log y + t(log log t) 2k−2 log2 y log t . Using partial summation we have M2(x) = ∑ p≤x hk(p) 2 p = ∑ p≤ee hk(p) 2 p + 1 x ∑ ee≤p≤x hk(p) 2 + ∫ x ee dt t2 ∑ ee≤p≤t hk(p) 2 1 + 1 x ( x1−yk log y + x(log log x)2k−2 log2 y log x ) + ∫ x ee ( t−1−yk log y + (log log t)2k−2 log2 y t log t ) dt y 2k−2 log2 y log x + x−yk log y + (log log x)2k−1 log2 y y2k−1 log2 y completing the proof of Proposition 3.14 and hence Theorem 1.4. 56 Chapter 4 Iterates Between φ and λ 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 λ(ab) ≤ bλ(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 λ(ab) = λ(ap1 . . . pk) ≤ p1λ(ap2 . . . pk) ≤ · · · ≤ p1 . . . pkλ(a) = bλ(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 λ(ab) = lcm ( λ(be+1), λ(pe11 ), . . . , λ(p ek k ) ) ≤ lcm ( bλ(be), λ(pe11 ), . . . , λ(p ek k ) ) ≤ b ∗ lcm ( λ(be), λ(pe11 ), . . . , λ(p ek k ) ) = bλ(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 λ(ab) | bλ(a).) If (a, b) = 1, then e = 0 and 57 Chapter 4. Iterates Between φ and λ λ(ab) = lcm ( b− 1, λ(pe11 ), . . . , λ(pekk ) ) ≤ (b− 1) lcm ( λ(pe11 ), . . . , λ(p ek k ) ) < bλ(a), ending the proposition. Suppose that g(n) is an arithmetic function of the form φ(h(n)) where h(n) is a (k − 1)–fold iterate involving φ and λ. Note that if a | b, then λ(a) | φ(b) since λ(a) | φ(a) | φ(ma) for anym. More easily we see λ(a) | λ(b) and φ(a) | φ(b). Inductively we can therefore show λk(n) | g(n). Thus we can use equation (4.1) to get λl+k(n) ≤ λl(g(n)) = λl ( g(n) λk(n) λk(n) ) ≤ λl+k(n) g(n) λk(n) . Since g(n) ≤ n we have that g(n) λk(n) ≤ n λk(n) = exp ( 1 (k − 1)!(1 + ok(1))(log log n) k log log log n ) by Theorem 1.4 for almost all n. Hence λl+k(n) ≤ λl(g(n)) ≤ λl ( g(n) λk(n) λk(n) ) ≤ λl+k(n) exp ( 1 (k − 1)!(log log n) k(1 + ok(1)) log log log n ) for almost all n. From the fact that λl+k(n) = n exp ( − 1 (k + l − 1)!(1 + ol,k(1))(log log n) k+l log log log n ) we get λl(g(n)) = n exp ( − 1 (k + l − 1)!(1 + ol,k(1))(log log n) k+l log log log n ) 58 Chapter 4. Iterates Between φ and λ for almost all n. As for φ(g(n)) we note that unless g(n) = φk(n), g(n) can be writen as φl(h(n)) where h(n) is a (k − l)–fold iterate beginning with a λ. From above we can see that h(n) = n exp ( − 1 (k − l − 1)!(1 + ok(1))(log log n) k−l log log log n ) and so φ(h(n)) is bounded above by h(n) and below by h(n) eγ log log h(n) + 3log log h(n) = h(n) eγ log ( log n− 1(k−l−1)!(1 + ok(1))(log log n)k−l log log log n ) = h(n) eγ log log n−O( 1(k−l−1)! logn(1 + ok(1))(log log n)k−l log log log n) = h(n) exp ( O(log log log n) ) which is within the error of h(n). Hence any string of φ will not change our estimate. Therefore if j(n) is a k–fold iteration of φ and λ which is not φk(n), but which begins with l copies of φ, then j(n) = n exp ( − 1 (k − l − 1)!(1 + ok(1))(log log n) k−l 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 λk(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) ≥ c log logn for almost all n ≤ x. The latter says if H(p) ≤ (log p)γ for almost all p ≤ x outside a set of size O ( x exp(−(log x)δ)) for some δ > 0, then for some function η, we have L(n) (log n)γη(n) for almost all n as n → ∞. 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) ≥ 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, λ(lcm(a, b)) = lcm(λ(a), λ(b)). Proof. Let a = pα11 p α2 2 . . . p αr r and b = p β1 1 p β2 2 . . . p βr r where at least one of αi, βi > 0. Then lcm(λ(a), λ(b)) = lcm ( λ(pα11 p α2 2 . . . p αr r ), λ(p β1 1 p β2 2 . . . p βr r ) ) = lcm(λ(pα11 ), λ ( pα22 ), . . . , λ(p αr r ), λ(p β1 1 ), λ(p β2 2 ), . . . , λ(p βr r ) ) = lcm ( λ ( p max(α1,β1) 1 ) , λ ( p max(α2,β2) 2 ) , . . . , λ ( pmax(αr,βr)r )) = λ ( p max(α1,β1) 1 p max(α2,β2) 2 . . . p max(αr,βr) r ) = λ(lcm(a, b)). Lemma 5.2. Given a positive integer n = ∏r i p αi i , 60 5.1. Lower Bound for L(n) (a) L(n) = maxi{L(pαii )}. (b) L(pα) = α− 1 + L(p) ≥ L(p) for α ≥ 1. Note that these two equations imply L(n) ≥ L(p) for all p | n. Proof. We show both parts by induction. For part (a) we show λk(n) = lcm ( λk(p α1 1 ), . . . , λk(p αr r ) ) (5.1) for k ≥ 0. For k = 0, it is true by the definition of n. Suppose it’s true for some k, then by Lemma 5.1 λk+1(n) = λ(λk(n)) = λ ( lcm ( λk(p α1 1 ), . . . , λk(p αr r ) )) = lcm ( λ ( λk(p α1 1 ) ) , . . . , λ ( λk(p αr r ) )) = lcm ( λk+1(p α1 1 ), . . . , λk+1(p αr 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 α. If α = 1 then the theorem is clearly true. Suppose L(pα) = α− 1 + L(p) then for α+ 1, λ(pα+1) = pαλ(p). Since (pα, λ(p)), by part (a), L(pαλ(p)) = max ( L(pα), L(λ(p)) ) = max ( α−1+L(p), L(p)−1) = α−1+L(p). Therefore L(pα+1) = α+ L(p), completing the induction and the theorem. For any p | n, we know that L(n) ≥ 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’t hold. Proof of Theorem 1.6. Let Y = Y (x) ≤ x. Given c from equation (1.6), define a set S(x) = S(x, Y ) = {p : p ≥ Y,H(p) < c log log p}. From [10, Theorem 3] we have that #S(x) x/(log x)K for some K > 1. If p | n for some p /∈ S(x), and p ≥ Y, 61 5.2. Upper Bound for L(n) L(n) ≥ L(p) ≥ H(p) ≥ c log log p ≥ c log log Y. Either there exists p ≥ Y, p ∈ S(x) such that p | n or else n is composed entirely of primes less than or equal to Y. The number of n ≤ x where there exists p | n with p ∈ S(x) is bounded by ∑ n≤x ∑ p|n p∈S(x) 1 = ∑ p≤x p∈S(x) ∑ n≤x n≡0 (mod p) 1 ≤ ∑ p≤x p∈S(x) x p = x ∫ x Y d(S(t)) t = x ( |S(x)| x + ∫ x Y S(t)dt t2 ) x logK x + ∫ x Y dt t logK t x logK−1 Y using partial summation. Let Ψ(x, z) be the number of n ≤ x composed of primes p ≤ z and let z = x1/u. Let U > 0, and ρ(u) be the Dickman function which goes to 0 as u→∞. By [17, Theorem 7.2], Ψ(x, z) xρ(u) uniformly for 0 ≤ u ≤ U. Given > 0, choose Y such that log Y = (log x)1−. Since Y < xγ for all γ > 0, this choice yields L(n) ≥ c(1− ) log log x for all but O ( x/(log Y )K−1+Ψ(x, Y ) ) = o(x) such n ≤ x, completing the theorem. 5.2 Upper Bound for L(n) The Pratt tree for a prime p describes the primes q where q ≺ · · · ≺ 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) ≤ (log p)γ for all p ≤ x outside a set of size O(x exp(−(log x)δ)) and let η(x) be a function such that x(cy)(log x) γ+1 2b(log x)γη(x)−2 = o(x). (5.2) Then L(n) (log x)γη(x) for almost all n ≤ x, for which the excluded n are divisible by at least one prime p in the above excluded set. Note that if η∗(x) is some function such that bη∗(x)(log x)γ − log(cy)→ ∞ and η(x) > 1b log 2 log(cy) + η∗(x), then x(cy)(log x) γ+1 2b(log x)γη(x)−2 = x exp ( ((log x)γ + 1) log(cy) ) exp ( (bη(x)(log x)γ − 2) log 2) x exp ( log(cy)− bη∗(x)(log x)γ) = o(x). Specifically we can choose η(x)b 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 = ∏ pαii be the prime factorization of n where H(p) ≤ (log p)γ for all p dividing n. By equations (1.7) and (1.8), L(n) = maxi{αi − 1 + L(p)}. Our first goal is to show that the number of n for which there exists a large α with pα | n is small. Fixing a prime p and α ≥ 2, the number n ≤ x such that pα | n is at most x/pα. Hence the number of bad n is bounded by ∑ p≤x x pα ≤ x x∑ m=2 1 mα x ∫ ∞ 2 t−αdt = x (α− 1)2α−1 . Therefore the number of bad n is bounded is o(x) for any choice of α = ξ(x) with ξ(x)→∞. Therefore for almost all n ≤ x we can assume L(n) ≤ max p|n (L(p) + ξ(x)) = max p|n (L(p) + o((log x)γ) 63 5.2. Upper Bound for L(n) by taking ξ(x) = o((log x)γ). Let η(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 − 1 and the primes in the Pratt tree are just the powers of that prime which divide q − 1. Therefore, if we have a branch of the Pratt tree, 2 = qk ≺ qk−1 ≺ · · · ≺ q1 ≺ q0 = p, then L(p) ≤ max{H(p) + ∑k i=1(αi − 1)} where qαii ‖qi−1 − 1 and the max is taken over all the branches of the Pratt tree. The inequality qαii < qi−1 holds for all i which implies 2 ∏k i=1 αi < p. Therefore we need to maximize the sum ∑k i=1(αi− 1) subject to ∏k i=1 αi < log x/ log 2. Suppose we have rs = tu, where 2 ≤ r, s, t, u ≤ 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 ∑k i=1(αi−1) η(x)(log x)γ , where 2 ≤ αi ≤M and M ≤ bη(x)(log x)γ for any constant b. By the above reasoning we know the sum is bounded by 2(k − l) + lM for some l ≤ k. However, M l ≤ log x/ log 2 implying l ≤ (log log x− log log 2)/ logM. Since k log log x, we conclude 2(k − l) + lM is bounded above by O ( log log x+M(log log x− log log 2)/ logM ) = o ( η(x)(log x)γ ) , contradicting the fact that the sum is η(x)(log x)γ . As a result, either∑k i=1(αi−1) η(x)(log x)γ , completing the theorem, or M ≥ bη(x)(log x)γ . In the latter case, there exists some αi ≥ bη(x)(log x)γ for some b > 0. It remains to show that the number of n ≤ x such that there exists qα | qk−1 − 1, qk−1 | qk−2 − 1, . . . , q1 | p − 1, p | n, with α ≥ bη(x)(log x)γ is o(x). Note that k ≤ H(p) ≤ (log x)γ . By Lemma 2.2, the number of n is bounded by ∑ α≥bη(x)(log x)γ ∑ k≤(log x)γ ∑ q x(cy)k qα . 64 5.2. Upper Bound for L(n) Summing q over all integers at least 2 instead of primes as above and using α ≥ 2 makes this ∑ α≥bη(x)(log x)γ ∑ k≤(log x)γ x(cy)k 2α−1 . Summing the geometric series under both α and k yields x(cy) (log x)γ+1 2bη(x)(log x)γ−2 . By the choice of η this is o(x) and hence for almost all n ≤ x, L(n) ≤ o((log x)γ) + max p|n { H(p) + k∑ i=1 (αi − 1) } (log n)γ + η(x)(log x)γ η(x)(log x)γ . We are now in a position to prove Theorem 1.7. Proposition 5.3 yields the theorem provided n wasn’t 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) → ∞ such that log Y (log x)γ . As in the proof of Theorem 1.6 we know that the set of n ≤ 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)γ . Let S(x) be the set {Y < p ≤ x | L(p) > (log p)γ}. Since L(p) > H(p), by (1.9) we know that #S(x) x exp (−(log t)δ). The number of n ≤ x where n is divisible by a prime in S(x) is bounded by∑ n≤x ∑ p∈S(x) p|n 1 ≤ ∑ p∈S(x) x p = x|S(x)| x + x ∫ x Y |S(t)|dt t2 x exp (−(log x)δ)+ x ∫ x Y exp (−(log t)δ)dt t x exp (−(log x)δ)+ x log x + x log Y using partial summation and exp(−(log t)δ) (log t)−2. 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− 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) ∼ e log log p and that H(p) ≤ log log p for almost all p. To justify our conjecture, we wish to analyze the difference L(p)−H(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−1 − 1 where a > 1. Let Y = Y (x) ≤ x. Also let a branch of the Pratt tree be p1 p2 · · · pl pl+1 · · · pk = 2 where paii ‖pi−1 − 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) log n we know L(pl+1) log Y. By a suitable choice of Y this will be made to be o(log log x). For i ≤ 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 ≤ x for which there exists p > Y where pa‖n is O(x/Y a−1). Proof. The number of n is bounded by∑ n≤x ∑ p>Y pa‖n 1 ≤ ∑ p>Y x pa x Y a−1 . By Lemma 5.4 we should expect a proportion of at most c/Y a. This implies that the probability of paii ‖pi−1 − 1 where (a2 − 1) + (a3 − 1) + · · · + (al − 1) = η(x) is bounded by cl/Y η(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− ( 1− c l Y η(x) )log x . This bound will approach 0 provided log x = o ( Y η(x)/cl ) . Under the assump- tion that H(p) ≤ e log log(p), we have l ≤ H(p) ≤ 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 η(x) = (log log x)3/4 makes the contri- bution to L(p)−H(p) be o(log log x) for i 6= l + 1. For i = l + 1, we have p al+1 l+1 | pl − 1. The remaining contribution to L(p) −H(p) is al+1 − 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 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 ∼ (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/φ(ra). Assuming independence, the probability that none of the N primes are con- gruent to 1 modulo ra is ( 1− 1 φ(ra) )N . Let η be a function going to infinity. Furthermore, let ra > Nη(N) be a prime power. Since r is prime, we know φ(ra) ≥ ra/2. This bound implies the probability is bounded below by( 1− 2 ra )N . Using our lower bound on ra we get( 1− 2 ra )N ≥ 1− ( 1− 2 Nη(N) )N → 1, since η(N)→∞. We know wish to use the lower bound on ra to bound al+1 and therefore our contribution to L(p)−H(p). Suppose ql+1 6= 2. If the level l ≈ c log log p, for almost all p, we expect al+1 ≤ 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) ≤ ( 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, λ(2 a) = 2a−2 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 ≤ e for 0 < c < e, we conclude that for almost all p ≤ x, L(p) ∼ 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) ∼ e log log p, sinceH(p) ∼ 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′(n) similar to L(n) except that λ′(2a) = 2a−1 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 λ(n), L(n) and H(p). Theorem 1.4 showed that the normal order of log nλk(n) is 1 (k−1)!(log log n) k log log log n. Theorem 1.5 showed that if g(n) = φl(λ(f(n))), where f(n) is a (k − 1) iterated arithmetic function consisting of iterates of φ and λ, then the normal order of log(n/g(n)) is 1(k−1)!(log log n) k log log log n. This is because g(n) relates to n in the same way as λk(n). However this doesn’t explain the relationship between g(n) and λk(n). The question has been solved for k = 2 by Kapoor [14]. Theorem 6.1. The normal order of log (λ(φ(n)) λ(λ(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 λ and φ, then log ( λ(f1(n)) λ(f2(n)) ) ∼ log ( f1(n) f2(n) ) . (6.1) For example the normal order of log λλφλλφ(n)λ6(n) is conjecturally log φλλφ(n) λ4(n) ∼ 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/λ(n)) = log log n(log log log n+O(ψ(n))), they more precisely showed log ( n λ(n) ) = log log n ( log log log n+A+O ( (log log log n)−1+ )) (6.2) for almost all n as n → ∞. 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 ≤ y/ log y, y/ log y < q ≤ y log y, y log y < q ≤ 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 ≤ 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’t even get k < log log log log n. It’s unlikely the methods of Chapter 3 will produce a more uniform result even with more careful consideration. In [9], Erdős, Pomerance, and Schmutz obtained a lower bound for λ(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 λ(λ(n)) or more generally λk(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–th iterate of the log function. However, this may or may not be the ”best” lower bound. Perhaps there are infinitely many n with an upper bound of the form (6.3) for λk(n). If that is true, then it can be shown that for those n, L(n) = k + L(λk(n)) ≤ k + log(λk(n)) log 2 + 1k 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 λ(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 φ(n) = m does not have exactly one solution. The conjecture is open for both φ as well as λ, although it’s known to be true for λ conditionally using the generalized Riemann hypothesis. For λ, 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–existent) counterexample of the λ 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–206. [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–234. [3] N. L. Bassily, I. Kátai and M. Wijsmuller, Number of prime divisors of φk(n), where φk is the k–fold iterate of φ, J. Number Theory 65 (1997), 226–239. [4] W.D. Banks, F. Luca, F. Saidak and P. Stănică. Compositions with the Euler and Carmichael functions, Abh. Math. Sem. Univ. Hamburg., 75 (2005), 215–244. [5] R.D. Carmichael. Note on a new number theory function, Bull. Amer. Math. Soc., 5 (1910), 232–238. [6] R.D. Carmichael. Note on Euler’s φ function, Bull. Amer. Math. Soc., 28 (1922), 109–110. [7] H. Davenport, Multiplicative Number Theory Third Edition, Graduate Texts in Math., New York: Springer-Verlag, Vol. 74 (2000). [8] P. Erdős, 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 Birkhäuser Boston, Boston, MA, (1990), 165–204. [9] P. Erdős, C. Pomerance, and E. Schmutz, Carmichael’s lambda func- tion, Acta Arith., 58 (1991), 363–385. [10] K. Ford, S.V. Konyagin and F. Luca, Prime chains and Pratt trees, Geom. Funct. Anal., 20 (2010), 1231–1258. 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–1605. [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’s hypothesis and tests for primality, J. Comput. System Sci., 13 (1976), 300–317. [16] G. Martin and C. Pomerance, The iterated Carmichael λ–function and the number of cycles of the power generator, Acta Arith., 118 (2005), no. 4, 305–335. [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–222. [19] V. Pratt, Every prime has a succinct certificate, SIAM J. Comput., 4 (1975), no. 3, 214–220. [20] G. Tenenbaum, Introduction to Analytic and Probabilistic Number The- ory, Cambridge University Press, New York (1995). [21] P. Turán, On a theorem of Hardy and Littlewood, J. London Math. Soc. 9 (1934), 274–276. 72 Appendix A The Turan–Kubilius Inequality The Turán–Kubilius 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 Turán [21] to prove the following theorem of Hardy and Littlewood. Let ω(n) be the number of distinct prime divisors of n, and Ω(n) be the number of prime divisors including multiplicity. For any δ > 0, the number of n ≤ x for which ω(n) = log log n+O ( (log log n)1/2+δ ) fails to hold is o(x). The analagous result for Ω holds as well. The methods of Turán were subsequently extended by Kubilius to more general additive functions. Theorem A.1 (Turán–Kubilius). For any complex additive function f we have ∑ n≤x |f(n)−A(x)|2 xB(x)2 (A.1) where A(x) = ∑ pk≤x f(pk)(1− p−1) pk , B(x)2 = ∑ pk≤x |f(pk)|2 pk . For a strongly additive function, that is f(pk) = f(p) for all k ≥ 1, the theorem reduces to the following corollary. Corollary A.2. For any complex completely additive function f we have∑ n≤x |f(n)−M1(x)|2 xM2(x)2 where M1(x) = ∑ p≤x f(p) p , M2(x) 2 = ∑ p≤x |f(p)|2 p . 73 Appendix A. The Turan–Kubilius 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 = ∑ pk≤x |f(p)|2 pk ≤ ∑ p≤x |f(p)|2 ∑ k≥1 1 pk ∑ p≤x |f(p)|2 1 p . As for A(x), the sum becomes A(x) = ∑ pk≤x f(p)(1− p−1) pk = ∑ pk≤x ( f(p) pk − f(p) pk+1 ) Using Cauchy–Schwarz (2.14) the difference between A(x) and M1(x) is at most ∑ p≤x |f(p)| p2 ≤ (∑ p≤x 1 p2 ∑ p≤x |f(p)|2 p2 )1/2 B(x). Therefore∑ n≤x |f(n)−M1(x)|2 ≤ 2 ∑ n≤x (|f(n)−A(x)|2 + |A(x)−M1(x)|2) xB(x)2 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 = ∑ n≤x f2(n)− 2A ∑ n≤x f(n) + bxcA2 := S2 − 2AS1 + bxcA2. (A.2) 74 Appendix A. The Turan–Kubilius Inequality Since f(n) is additive, f(n) = ∑ pk‖n f(p k). Inserting this into S1 yields S1 = ∑ n≤x ∑ pk‖n f(pk) = ∑ pk≤x f(pk) (⌊ x pk ⌋ − ⌊ x pk+1 ⌋) ≥ xA− ∑ pk≤x f(pk) using bxc − byc ≥ x− y − 1. As for S2 we obtain S2 = ∑ n≤x (∑ pk‖n f(pk) )2 = ∑ n≤x ∑ pk‖n f(pk) ∑ ql‖n f(ql). Splitting this up into the two cases where p = q or p 6= q yields S2 = ∑ pk≤x f2(pk) ∑ n≤x pk‖n 1 + ∑ pk≤x ql≤x q 6=p f(pk)f(ql) ∑ n≤x pk‖n ql‖n 1 ≤ x ∑ pk≤x f2(pk) pk + ∑ pk≤x ql≤x q 6=p f(pk)f(ql) (⌊ x pkql ⌋ − ⌊ x pkql+1 ⌋ − ⌊ x pk+1ql ⌋ + ⌊ x pk+1ql+1 ⌋) ≤ xB2 + x ∑ pk≤x ql≤x q 6=p f(pk) pk (1− p−1)f(q l) ql (1− q−1) + 2 ∑ pk≤x ql≤x q 6=p f(pk)f(ql) using bxc−byc ≤ x−y+1. Let the last sum be S3. Inserting these estimates into (A.2) yields S ≤ xB2 + 2A ∑ pk≤x f(pk) + 2S3 +A 2. (A.3) Using Cauchy–Schwarz (2.14) on S3 yields S3 ≤ ( ∑ pk≤x ql≤x f(pk)f(ql) pkql ∑ pk≤x ql≤x pkql )1/2 B2 (∑ n≤x n )1/2 xB2. 75 Appendix A. The Turan–Kubilius Inequality Using Cauchy–Schwarz (2.14) again yields ∑ pk≤x f(pk) ≤ ( ∑ pk≤x f2(pk) pk ∑ pk≤x pk )1/2 = B ( ∑ pk≤x pk )1/2 . We would like to bound the sum by a sum over all n ≤ 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) + · · · x/ log x. This bound implies ∑ pk≤x f(pk) B ( x2 log x )1/2 = B x√ log x . As for A we use an estimate of Mertens [17, Theorem 2.7 (d)] and Cauchy– Schwarz (2.14), implying A ∑ pk≤x f(pk) pk ≤ ( ∑ pk≤x f2(pk) pk ∑ pk≤x 1 pk )1/2 B(log log x)1/2. Putting all these estimates together with (A.3) yields S xB2+2 ( B(log log x)1/2 )( B x (log x)1/2 ) +2xB2+B2(log log x) xB2 completing the theorem. It’s 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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The iterated Carmichael lambda function
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The iterated Carmichael lambda function Harland, Nicholas 2012
pdf
Page Metadata
Item Metadata
Title | The iterated Carmichael lambda function |
Creator |
Harland, Nicholas |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | The arithmetic function λ(n) is the exponent of the cyclic group (Z/nZ)^x. The k-th iterate of λ(n) is denoted by λk(n) In this work we will show the normal order for log(n/λk(n)) is (loglog n)k⁻¹}(logloglog n)/(k-1)! . Second, we establish a similar normal order for other iterate involving a combination of λ(n) and Φ(n). Lastly, define L(n) to be the smallest k such that λ_k(n)=1. We determine new upper and lower bounds for L(n) and conjecture a normal order. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-10-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution 3.0 Unported |
DOI | 10.14288/1.0073354 |
URI | http://hdl.handle.net/2429/43537 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by/3.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_spring_harland_nicholas.pdf [ 485.69kB ]
- Metadata
- JSON: 24-1.0073354.json
- JSON-LD: 24-1.0073354-ld.json
- RDF/XML (Pretty): 24-1.0073354-rdf.xml
- RDF/JSON: 24-1.0073354-rdf.json
- Turtle: 24-1.0073354-turtle.txt
- N-Triples: 24-1.0073354-rdf-ntriples.txt
- Original Record: 24-1.0073354-source.json
- Full Text
- 24-1.0073354-fulltext.txt
- Citation
- 24-1.0073354.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0073354/manifest