UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The iterated Carmichael lambda function Harland, Nicholas 2012

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
ubc_2013_spring_harland_nicholas.pdf [ 485.69kB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0073354.json
JSON-LD: 1.0073354+ld.json
RDF/XML (Pretty): 1.0073354.xml
RDF/JSON: 1.0073354+rdf.json
Turtle: 1.0073354+rdf-turtle.txt
N-Triples: 1.0073354+rdf-ntriples.txt
Original Record: 1.0073354 +original-record.json
Full Text
1.0073354.txt
Citation
1.0073354.ris

Full Text

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 2012Abstract 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, de ne 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. iiTable 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  (t; p; 1) . . . . . . . . . . . . . . . . . 33 3.8 Reduction of P 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 iiiTable 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 ivList of Figures 1.1 The Pratt tree for the prime 3691 . . . . . . . . . . . . . . . . 4 vAcknowledgements 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 signi cantly throughout my Ph.D. Without his guidance I would never have been able to attain my mathematical achievements. Speci cally 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  nancial 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. Speci cally I would like to thank Paul for his helpful suggestion in the proof of Lemma 2.4. viDedication 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. viiChapter 1 Introduction 1.1 History and Results The Carmichael lambda function  (n);  rst introduced by Carmichael [5], is de ned 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) = lcmf (a);  (b)g; 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  nding 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}os, Pomerance, and Schmutz in [9]. One of those results is the following. For an explicitly de ned constant A;  (n) = n exp   (log log n)(log log log n+A+O  (log log log n) 1+   (1.1) as n!1 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!1 for almost all n. 11.1. History and Results Applications of this function included the power generator of pseudoran- dom numbers un  u e n 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. De nition 1.1. The k{fold iterated Carmichael lambda function is de ned recursively to be  0(n) = n;  k(n) =  ( k 1(n)) for k  1: We de ne  k(n) similarly. Next we study a related function. De nition 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  nding normal orders for the preceding arithmetic functions. Next we de ne the meaning of normal order. De nition 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!1: 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  rst result is the proof of that conjecture. Theorem 1.4. For  xed positive integer k, the normal order of log n k(n) is 1 (k 1)!(log log n) k log log log n. 21.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)!1 as x!1: 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 anic a 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  : Speci cally 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: 31.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}os, 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 de ned as follows. The root node is p: Below p are nodes labelled with the primes q such that q j 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 certi cate (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 in nitely 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 in nitely 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 41.1. History and Results on the exponent arising from the Elliot{Halberstam conjecture. Recall the Bombieri{Vinogradov Theorem [7, Chapter 28] implies X n Q max y x      (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  0 be such that (1.5) holds for Q = x 0 : In [10] Ford, Konyagin and Luca showed for any c < 1=(e 1  log  0); 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 = Q p ii , then L(n) = max i fL(p ii )g (1.7) and L(p ) =   1 + L(p)  L(p): (1.8) These two equations imply L(n)  L(p) for any p j 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!1: 51.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: 6Chapter 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  xed 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 = Y p pvp(n): Let the set Pn be fp : p  1 (mod n)g: The notation q  q0 is de ned to mean that q0 2 Pq: In Chapter 3 we will assume x > ee e : The function y = y(x) is de ned to be log log x: Also let  (x) be any function going to 1 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 de ned by  (n) =  log p n = pl 0 otherwise. We use the Chebyshev bound X n x  (n) = X pl x log p x: (2.1) 72.2. Required Estimates Also de ne the related function  (x) = 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)]) X 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) X q>x log q q2  1 x : (2.4) (b) X 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), X q>x log q q2 = Z 1 x d( (t)) t2 = 2 (x) x3 + Z 1 x 2 (t)dt t3 = 2 (x) x3 +O  Z 1 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 X a2N P (a) ma = 1 m 1X a=0 P (a) ma and X a2N ma>x 1 ma  1 x     1X a=A 1 ma A     = 1 x     1X a=0 1 ma     82.2. Required Estimates for any polynomial P (x): Then by noting that P1 a=A P (a) ma  P 1 uniformly for m  2 and A  0 we obtain the estimates X a2N P (a) ma  P 1 m ; X a2N ma>x 1 ma  1 x : (2.6) From [17, Corollary 1.15] we get X 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;  (t;n; a) t  (n) log(t=n) : (2.8) By partial summation on (2.8) we can obtain X p t p2Pn 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 X p t p2Pn 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 X p2Pn p t 1 p = log log t  (n) +O  log n  (n)  : (2.11) Equation (2.11) easily implies X p2Pn p t 1 p 1 = log log t  (n) +O  log n  (n)  ; (2.12) 92.3. Early Results since the di erence is X p2Pn p t 1 p(p 1)  1X m=1 1 mn(mn+ 1) < 1 n2 1X m=1 1 m2  1 n2 : The Bombieri{Vinogradov Theorem [7, Chapter 28] implies X n Q max y x      (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;     X n t f(n)g(n)     2  X n t jf(n)j2 X n t jg(n)j2: (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 j qk 1  1; qk 1 j qk 2  1; : : : ; q1 j p 1 and p j 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 102.3. Early Results by X n x X pjn X q1jp 1    X qk 1jqk 2 1 X q jqk 1 1 1 = X qk 1 1 (mod q ) X qk 2 1 (mod qk 1)    X p 1 (mod q1) X n x n 0 (mod p) 1  X qk 1 1 (mod q ) X qk 2 1 (mod qk 1)    X p 1 (mod q1) x p  X qk 1 1 (mod q ) X qk 2 1 (mod qk 1)    X q1 1 (mod q2) xcy q1      X 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  (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 X m t mL  (m)L+1  L log t: (2.15) Proof. If f(n) is a non-negative multiplicative function, we know that X n t f(n)  Y p t 1X r=0 f(pr): (2.16) 112.3. Early Results Applying (2.16) with n L  (n)L+1 yields X m t mL  (m)L+1  Y p t  1 + 1X r=1 prL (pr  pr 1)L+1  = Y p t  1 + 1X r=1 pL r+1 (p 1)L+1  = Y p t  1 + 1 (p 1)L+1 pL 1 1p  = Y p t  1 + pL+1 (p 1)L+2   exp  X p t log  1 + pL+1 (p 1)L+2   = exp  X p t  pL+1 (p 1)L+2 +OL  1 p2    = exp  X 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 X m t (Cm+ 1)L  (Cm+ 1)L (m)  L; log t: (2.17) Proof. It will su ce to show X m t (Cm+ 1)2L 1  (Cm+ 1)2L  L; log t C (2.18) 122.3. Early Results as then by Cauchy{Schwarz (2.14) we can get that  X m t (Cm+ 1)L  (Cm+ 1)L (m)  2  X m t (Cm+ 1)2L 1  (Cm+ 1)2L X m t (Cm+ 1)  (m)2  L;  log t C  C log t  L; log 2 t by using Lemma 2.3 and (2.18). Let G(t) = X m t (Cm+ 1)2L  (Cm+ 1)2L : We show Equation (2.18) by  rst showing G(t)  L; t: This implies Equa- tion (2.18) since X m t (Cm+ 1)2L 1  (Cm+ 1)2L < 1 C X m t (Cm+ 1)2L m (Cm+ 1)2L = 1 C Z t 1 d(G(u)) u = 1 C  G(t) t + Z t 1 G(u) u2   L; 1 C  1 + Z t 1 1 u   L; 1 C (log t) To show Equation (2.18) we start by de ning s(n) to be the multiplicative function de ned by n2L  (n)2L = 1  s = X djn 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: 132.3. Early Results Hence X m t (Cm+ 1)2L  (Cm+ 1)2L = X n Ct+1 n 1 (mod C) n2L  (n)2L = X n Ct+1 n 1 (mod C) X djn s(d) = X d Ct+1 s(d) X n Ct+1 djn n 1 (mod C) 1 = X d Ct+1 s(d)  t d +O(1)  = t X d Ct+1 s(d) d +O  X d Ct+1 s(d)  : We require some estimates on s(d): For the sum of the multiplicative function s(d)=d; X d Ct+1 s(d) d  Y p Ct+1  1 + (1 1=p) 2L  1 p   Y p Ct+1  1 +OL  1 p2   = exp  X p Ct+1 log  1 +OL  1 p2    = exp  X p Ct+1 OL  1 p2   = exp(OL(1))  L 1: 142.3. Early Results For the sum of s(d); X d Ct+1 s(d)  Y p Ct+1  1 + (1 1=p) 2L  1  = Y p Ct+1 (1 1=p) 2L = exp  X p Ct+1 log  1 +OL  1 p    = exp  X 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 X d Ct+1 s(d) d +O  X 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 X 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 X 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: 152.3. Early Results By Cauchy{Schwarz (2.14), we get that  X 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  X m t (C1m+ 1)2L1(C2m+ 1)2L2 : : : (Crm+ 1)2Lr  (C1m+ 1)2L1 (C2m+ 1)2L2 : : :  (Crm+ 1)2Lr (m)  X m t (Cr+1m+ 1)2Lr+1  (Cr+1m+ 1)2Lr+1 (m)  L1;:::;Lr+1; log 2 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 X 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.  X m t (C1m+ 1)L1(C2m+ 1)L2 : : : (Crm+ 1)LrmL 1  (C1m+ 1)L1 (C2m+ 1)L2 : : :  (Crm+ 1)Lr (m)L  2  X m t (C1m+ 1)2L1(C2m+ 1)2L2 : : : (Crm+ 1)2Lr  (C1m+ 1)2L1 (C2m+ 1)2L2 : : :  (Crm+ 1)2Lr (m)  X m t m2L 2  (m)2L 1  L1;:::;Lr;L; log 2 t by Lemmas 2.3 and 2.5. 16Chapter 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  rst 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. X q>yk  q( k(n))=1 ( q( k(n))  q( k(n))) log q  y k (x) for almost all n  x. Proposition 3.2. X q>yk  q( k(n)) 2  q( k(n)) log q  y k (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. 173.1. Required Propositions and Proof of Theorem 1.4 Proposition 3.3. X q yk  q( k(n)) log q  y k (x) for almost all n  x: That will leave us with the contribution of small primes dividing  k(n): Recall the following de nition of an additive function. De nition 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 de ned by hk(n) = X p1jn X p2jp1 1    X pkjpk 1 1 X q yk  q(pk  1) log q: The following proposition shows that the di erence between the sum involv- ing the small primes dividing  k(n) and the term hk(n) is small. Proposition 3.5. X 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  nal proposition. Proposition 3.6. hk(n) = 1 (k  1)! yk log y +O(yk) for almost all n  x: 183.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)  = X q>yk ( q( k(n))  q( k(n))) log q + X q yk ( q( k(n))  q( k(n))) log q = X q>yk  q( k(n))=1 ( q( k(n))  q( k(n))) log q + X q>yk  q( k(n)) 2 ( q( k(n))  q( k(n))) log q + X q yk  q( k(n)) log q  X q yk  q( k(n)) log q: Note that if a j b, then  (a) j  (b) since  (a) j  (a) j  (ma) for any integer m. This quickly implies that  k(n) always divides  k(n) for all k and so we get 0  X q>yk  q( k(n)) 2 ( q( k(n))  q( k(n))) log q  X q>yk  q( k(n)) 2 ( q( k(n)) log q: 193.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)! yk log y +O  yk (x)  for almost all n  x;  nishing 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 j n: Clearly the number of such n is at most xq2 : Case 2: There exists p1 2 Pq2 ; p2 2 Pp1 ; p3 2 Pp2 ; :::; pl 2 Ppl 1 where pl j 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 2 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 de ne 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  nite set of primes. To begin, the set L1;2 will be an arbitrary  nite 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 2 L1;1 [ L1;2; there exists a unique prime r 2 L2;1 such that r 2 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: 203.2. Prime Power Divisors of  k(n) In general for all 1 < h  k we have for all p 2 Lh 1;1 [ Lh 1;2 there exists a unique prime r 2 Lh;1 such that r 2 Pp;Lh;2 is an arbitrary subset of Pq, and r 2 Lk;1 [ Lk;2 ) r j n: Some description of the terms are in order including some helpful de - nitions. De nition 3.7. An incarnation I of Case 3 is some speci ed 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 j  3(n) would be s1; s2; s3; r3; r4 2 Pq where r1 2 Ps1 ; r2 2 Ps2s3 ; p1 2 Pr1r2 ; p2 2 Pr3r4 ; with p1p2 j n: De nition 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 satis es incarnation J; then it will also satisfy incarnation I: For example, I is a subincarnation of the incarnation s1; s3; r3; r4 2 Pq where r1 2 Ps1 ; r2 2 Ps3 ; p1 2 Pr1r2 ; p2 2 Pr3r4 ; with p1p2 j 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 j 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 j  k(n), what is our exponent a? Let mh;i = #Lh;i: From the recursion above we can see that qmk;2 j  (n) and so do the primes in Lk 1;1: For the second iteration of  , qmk;2 1+mk 1;2 j  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 + X 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( Q 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  xed incarnation of Case 3, let M be the total number of primes, N be 213.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): Speci cally M = X h (mh;1 +mh;2) N = X h H mh;2 and H yields the maximum value in (3.3). Note that under this notation, qN H+1 j  k(n): For example, in the incarnation I above, L1;2 = fs1; s2; s3g;L2;1 = fr1; r2g;L2;2 = fr3; r4g;L3;1 = fp1; p2g;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 X n x X p12L1 X p22L2    X pk2Lk 1 = X p12L1 X p22L2    X pk2Lk X pkjn n x 1  X p12L1 X p22L2    X pk2Lk x Q pk2Lk 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 2 Ppk 1 for all the primes in Lk 1, and for p 2 Lk;2 we have p 2 Pq: By Brun{Titchmarsh (2.10) we get that the above sum is  X p12L1 X p22L2    X pk 12Lk 1 x(cy)mk;1+mk;2 Q pk 12Lk 1 pk 1qmk;2 : 223.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:  X p12L1 x(cy) P 2 i k(mi;1+mi;2) Q p12L1 p1q P 2 i kmi;2  x(cy) P 1 i k(mi;1+mi;2) q P 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. De nition 3.10. An incarnation of Case 3 is minimal if it does not contain any strings of p1 2 Pp2 ; p2 2 Pp3 : : : pk 1 2 Ppk where pk j 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 su ces to show X n x X q>yk  q( k(n))=1 ( q( k(n))  q( k(n))) log q  xy k 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 233.3. Large Primes Dividing  k(n) p1 2 Pq; p2 2 Pp1 ; p3 2 Pp2 ; : : : ; pk 2 Ppk 1 where pk j 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 = P h(mh;1 + mh;2)  k P hmh;2 = kN: The number of cases we get are O  cM xyM qN   cMxykN qN  cMxy2k 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 X q>yk X n x  q( k(n))=1 ( q( k(n))  q( k(n))) log q  X q>yk X n x  q( k(n))=1 N>1 log q  X 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  xyk 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   cMxyk q2 243.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 satis es an incarnation with M  k(N  1). Then it also satis es a minimal incarnation with M  k(N  1) since removing a string of p1 2 Pp2 ; p2 2 Pp3 : : : pk 1 2 Ppk , would decrease N by 1 and M by k leaving the inequality unchanged. Secondly we can assume that n also satis es 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 satisi es 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) = S q>yk Sq. Using Lemma 3.11 we have #S  X q>yk #Sq  X q>yk xyk q2  xyk X q>yk 1 q2  xyk log(yk)yk  x  (x) by (2.5). As for the n with n =2 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 = X 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 = X h (mh;1 +mh;2)  km1;2 + (k  1) X h>1 mh;2 = m1;2 + (k  1)N = k(N  1) N + k +m1;2 253.3. Large Primes Dividing  k(n) which implies m1;2 > N  k and so P h>1mh;2 = N  m1;1 < k: Therefore if m2;1 < a k; then M = X h (mh;1 +mh;2)  m1;2 + (k  1)m2;1 + (k  1) X 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 X n=2S n x X q>yk  q( k(n))>1 ( q( k(n)) log q  2 X n=2S n x X q>yk  q( k(n))>1 ( q( k(n)) 1) log q  X q>yk log q X a 2 a X n x n=2S  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 X q>yk log q X n x n=2S  q( k(n))=a 1 a x(cy)M qNg(a; k)  ack(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 X n=2S n x X q>yk  q( k(n))>1 ( q( k(n)) log q  X q>yk log q X a 2 ack(a+k 1)xy2k q2g(a; k) = xy2k X q>yk log q q2 X a 2 ack(a+k 1) g(a; k) 263.4. Small Primes Dividing  k(n) However the latter sum converges to some function depending on k, and so we get  xy2k X 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 j  k(n), we will need a lemma to deal with the number of cases where qa j  k(n): Fortunately this case is much simpler as the only two ways for qa j  (n) is for qa+1 j n or for there to exist p j n with p 2 Pqa : Note that these conditions aren’t su cient, but are necessary when q = 2: Lemma 3.12. The number of positive integers n  x for which qa j  k(n) is O(xy k qa ): Proof. We’ll proceed by induction on k. If k = 1, then qa j  (n) if qa+1 j n or p 2 Pqa with p j n. The number of such n is at most X n x qa+1jn 1 + X n x p2Pqa pjn 1 x qa+1 + X p2Pqa x p  x qa+1 + xy qa  xy qa : using (2.10). Suppose the number of n  x for which qa j  k 1(n) is O(xy k 1 qa ). If q a j  k(n), then either qa+1 j  k 1(n) or p 2 Pqa with p j  k 1(n). Hence the number of such n is bounded by X n x qa+1j k 1(n) 1 + X n x p2Pqa pj k 1(n) 1 xyk 1 qa+1 + X p2Pqa xyk 1 p  xyk 1 qa+1 + xyk qa  xyk qa as needed. Proof of Proposition 3.3. Like in the proof of previous propositions, we’ll show X n x X q yk  q( k(n)) log q  xy k: 273.5. Reduction to hk(n) for Small Primes The left hand side is equal to X n x X q yk  q( k(n)) log q = X n x X q yk log q X a2N qaj k(n) 1  X n x X q yk log q X a2N qa yk 1 + X n x X q yk log q X a2N qaj k(n) qa>yk 1: The  rst sum is X n x X q yk log q X a2N qa yk 1 = X n x X m yk  (m) X n x yk  xyk; using the de nition of  (m) and equation (2.1). Using Lemma 3.12, the geometric estimate in (2.6) and equation (2.1) the second sum becomes X n x X q yk log q X a2N qaj k(n) qa>yk 1 X q yk log q X a2N qa>yk xyk qa  X 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 j n: For this reason we will approximate the sum P q yk vq( k(n)) log q with hk(n) = X p1jn X p2jp1 1    X pkjpk 1 1 X q yk  q(pk  1) log q: (3.4) Proof of Proposition 3.5. For any  xed prime q, we know that vq( (m)) = maxf0; vq(m) 1g+ X pjm vq(p 1); 283.5. Reduction to hk(n) for Small Primes which implies X pjm vq(p 1)  vq( (m))  vq(m) + X pjm vq(p 1): Repeated use of this inequality for m =  l(n) where l ranges from k  1 to 0 yields X pj k 1(n) vq(p 1)  vq( k(n))  X pj k 1(n) vq(p 1) + X pj k 2(n) vq(p 1) +    + X pj (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 X ssf vq(p 1)  X pj k 1(n) vq(p 1)  X ssf vq(p 1) + X nssf vq(p 1): Combining this inequality with (3.5) yields X ssf vq(p 1)  vq( k(n))  X ssf vq(p 1) + X nssf vq(p 1) + X pj k 2(n) vq(p 1) +    + X pj (n) vq(p 1) + vq(n): Subtracting the sum over the supersquarefree case, multiplying through by log q and summing over q  yk yields 293.5. Reduction to hk(n) for Small Primes 0  X q yk  q( k(n)) log q  hk(n)  X q yk X nssf vq(p 1) log q + X q yk X pj k 2(n) vq(p 1) log q +    + X q yk X pjn vq(p 1) log q where we get hk(n) from (3.4). It su ces to show that the sum on the right side becomes our error term. For the sum X n x X q yk X pj m(n) vq(p 1) log q = X n x X q yk X pj m(n) X a2N qajp 1 log q = X n x X q yk log q X a2N X p2Pqa pj 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 X q yk log q X a2N X p2Pqa p yk 1 pj m(n) 1  X q yk log q X a2N  (yk 1; qa; 1)  X q yk log q X a2N yk 1  (qa)  yk 1 X 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  x an M and N from case 3 for which p j  m(n), of which there are at most Ok(1) such M;N since vp( (m)) = 1. Therefore 303.5. Reduction to hk(n) for Small Primes X n x X q yk log q X a2N X p>yk 1 p2Pqa pj m(n) 1 X q yk log q X a2N X p2Pqa p>yk 1 xyM pN  X q yk log q X a2N X p2Pqa xyM (k 1)(N 1) p  X q yk log q X a2N xyM (k 1)(N 1)+1 qa  X 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 X n x  X q yk X nssf vq(p 1) log q + X q yk X pj k 2(n) vq(p 1) log q + : : : + X q yk X pjn vq(p 1) log q   xyk 1 log y and so 313.6. Reduction to the First and Second Moments X q yk X nssf vq(p 1) log q + X q yk X pj k 2(n) vq(p 1) log q + : : : + X q yk X pjn vq(p 1) log q  y k 1 log y   (x) for almost all n  x as required. 3.6 Reduction to the First and Second Moments The Tur an-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 X n x jf(n) M1(x)j 2  CxM2(x) (3.6) where M1(x) = P p xjf(p)j=p and M2(x) = P p xjf(p)j 2=p: Since hk(n) is strongly additive we apply this inequality where M1(x) = P p x hk(p)=p, M2(x) = P p x hk(p) 2=p: We will need to  nd 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)! yk log y +O(yk) Proposition 3.14. For all x > ee e ; M2(x) y 2k 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 jhk(n)  M1(x)j > 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): 323.7. Summations Involving  (t; p; 1) 3.7 Summations Involving  (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  (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 X pk2Pb X pk 12Ppk    X p22Pp3  (t; p2; 1) t log t(log log t)k 2 b : (3.7) (b) If b  t 1 ; then X pl2Pb pl>t 2 X pl 12Ppl    X p22Pp3  (t; p2; 1) bl 1t  (b)l log t : (3.8) (c) If b  t 1 ; then X pl2Pb X pl 12Ppl    X p22Pp3  (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  (t; p2; 1)  t=p2 and several 333.7. Summations Involving  (t; p; 1) uses of Brun-Titchmarsh (2.10) to get X pk2Pb X pk 12Pk    X p22P3  (t; p2; 1)  X pk2Pb X pk 12Pk    X p22P3 t p2  t X pk2Pb X pk 12Pk    X p32P4 log log t p3  t X pk2Pb (log log t)k 2 pk  t X 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 X pl2Pb l>t 2 X pl 12Pl    X p22P3  (t; p2; 1) = X pl2Pb l>t 2 X pl 12Pl    X p32P4 #f(m1; p2) : p2 = 1 (mod p3); p2 > t  2 ; m1p2 + 1  t; p2;m1p2 + 1 primeg = X pl2Pb l>t 2 X pl 12Pl    X p42P5 #f(m1;m2; p3) : p3 = 1 (mod p4); p3 > t  2 ; m1(m2p3 + 1) + 1  t; fp3;m2p3 + 1;m1(m2p3 + 1) + 1g primeg = #f(m1;m2; : : : ;ml 1; pl) : pl = 1 (mod b); pl > t  2 ; m1(m2 : : : (ml 2(ml 1pl + 1) + 1) +    + 1  t; fpl;ml 1pl + 1; ml 2(ml 1pl + 1) + 1; : : : ; m1(m2 : : : (ml 2(ml 1pl + 1) + 1) +    + 1g primeg  X m1:::ml 1 t1  2 #fpl < t=m1 : : :ml 1 : pl = 1 (mod b); fpl;ml 1pl + 1;ml 2(ml 1pl + 1) + 1; : : : ; m1(m2:::(ml 2(ml 1pl + 1) + 1) +    + 1g primeg: 343.7. Summations Involving  (t; p; 1) From here will need to use Brun’s Sieve method (see [12, Theorem 2.4]) to get that #fpl <t=m1 : : :ml 1 : pl = 1 (mod b); fpl;ml 1pl + 1;ml 2(ml 1pl + 1) + 1; : : : ;m1(m2 : : : (ml 2(ml 1pl + 1) + 1) +    + 1g primeg  El 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 1Y i=1 mi(i+1)=2i  (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  El 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 X m1:::ml 1 t1  2 El 1  (E)l 1 c1  (c1) : : : cl 1  (cl 1) 1 m1 : : :ml 1 = X m1:::ml 1 t1  2 (E )l 1  (E )l 1 c1  (c1) : : : cl 1  (cl 1) 1 m1 : : :ml 1 where 353.7. Summations Involving  (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 o 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. X m1:::ml 1 t1  2 El 1  (E)l 1 c1  (c1) ::: cl 1  (cl 1) 1 m1 : : :ml 1  X m2:::ml 1 t1  2 (E0)l 1  (E0)l 1 c01  (c01) : : : c0l 1  (c0l 1) 1 m2 : : :ml 1 (log t)  X m3:::ml 1 t1  2 (E00)l 1  (E00)l 1 c001  (c001) : : : c00l 1  (c00l 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 X pl2Pb l>t 2 X pl 12Pl    X p22P3  (t; p2; 1) tbl 1  (b)l(log t)l (log t)l 1 = tbl 1  (b)l log t : As for part (c),  rst 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 363.7. Summations Involving  (t; p; 1) X pl2Pb pl t 2 X pl 12Pl    X p22P3 p2 t 2  (t; p2; 1) X pl2Pb pl t 2 X pl 12Pl    X p22P3 p2 t 2 t  (p2) log t=p2  X pl2Pb pl t 2 X pl 12Pl    X p22P3 p2 t 2 t p2 log t  X pl2Pb 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 X pl2Pb pl t 2 X pl 12Pl    X p22P3 p2>t 2  (t; p2; 1) X pl2Pb pl t 2 X pl 12Pl    X pm+12Pm+2 (pm 1)m 1t  (pm 1)m log t  X pl2Pb pl t 2 X pl 12Pl    X pm+12Pm+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  nishes 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 X p22Pb1 r22Pb2  (t; p2r2; 1) t log2 t b1b2 : (3.10) 373.7. Summations Involving  (t; p; 1) (b) If neither b1 nor b2 exceeds t 1 ; then X pk2Pb1 rk2Pb2 pkrk>t 2 ::: X p22Pp3 r22Pr3  (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 X pk2Pb1 rk2Pb2 ::: X p22Pp3 r22Pr3  (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 X pk2Pb1 rk2Pb2 ::: X p32Pp4 r32Pr4 X s2Pp3\Pr3  (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  rst assume 383.7. Summations Involving  (t; p; 1) that pk  rk, then X pk2Pb1 rk2Pb2 pk rk pkrk>t 2 ::: X p22Pp3 r22Pr3  (t; p2r2; 1) = X pk2Pb1 rk2Pb2 pkrk>t 2    X p32Pp4 r32Pr4 #f(m1; p2; r2) : p2 = 1 (mod p3); r2 = 1 (mod r3); r2p2 > t  2 ;m1r2p2 + 1  t; p2;m1r2p2 + 1 primeg = X pk2Pb1 pk rk X pk 12Pk    X p22P3 X rk2Pb2 pkrk>t 2 X rk 12Prk    X r42Pr5 #f(m1;m2; r3) : r3 = 1 (mod r4); r3p2 > t  2 ;m1p2(m2r3 + 1) + 1  t; fr3;m2r3 + 1;m1p2(m2r3 + 1) + 1g primeg = X pk2Pb1 pk rk X pk 12Pk    X p22P3 #f(m1;m2; : : : ;ml 1; rl) : rl = 1 (mod b2); p2rk > t  2 ;m1p2(m2 : : : (mk 2(mk 1rk + 1) + 1) +    + 1  t; frk;mk 1rk + 1;mk 2(mk 1rk + 1) + 1; : : : ; m1p2(m2 : : : (mk 2(mk 1rk + 1) + 1) +    + 1g primeg  X m1:::ml 1 t1  2 X pk2Pb1 pk rk X pk 12Pk    X p22P3 #frk < t=p2m1:::mk 1 : rk = 1 (mod b2); frk;mk 1rk + 1;mk 2(mk 1rk + 1) + 1; : : : ; p2m1(m2 : : : (mk 2(mk 1rk + 1) + 1) +    + 1g primeg 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 #frk < t=p2m1    k 1 : rk = 1 (mod b1); frk;mk 1rk + 1;mk 2(mk 1rk + 1) + 1; : : : ; p2m1(m2 : : : (mk 2(mk 1rk + 1) + 1) +    + 1g primeg  Ek 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 393.7. Summations Involving  (t; p; 1) where the ci and E are E = p2  l 1Y i=1 mi(i+1)=2i  (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 X pk2Pb1 rk2Pb2 pkrk>t 2    X p22Pp3 r22Pr3  (t; p2r2; 1) tbk 12  (b2)k log t X pk2Pb1 X pk 12Pk    X p22P3 1 p2  tbk 12  (b2)k log t X pk2Pb1 (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),  rst note that bi= (bi)  log log bi for i 2 f1; 2g: taking care of the case where pkrk > t 2 : As for 403.8. Reduction of P hk(p) to Small Values of pk pkrk  t 2 we get X pk2Pb1 rk2Pb2 pkrk t 2    X p22Pp3 r22Pr3  (t; p2r2; 1) X pk2Pb1 rk2Pb2 pkrk t 2    X p22Pp3 r22Pr3 t  (p2r2) log t=p2r2  X pk2Pb1 rk2Pb2 pkrk t 2    X p22Pp3 r22Pr3 t p2r2 log t  X pk2Pb1 rk2Pb2 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),  nishing part (c). As for part (d) we note that X p32Pp4 r32Pr4 X s2Pp3\Pr3  (t; s; 1) = X p32Pp4 r32Pr4 #f(m1; s) : s = 1 (mod p3r3);m1s+ 1  t; s;m1s+ 1 primeg = X p32Pp4 #f(m1;m2; r3) : r3 = 1 (mod r4);m1(m2p3r3 + 1) + 1  t; fm2p3r3 + 1;m1(m2p3r3 + 1) + 1 primeg and so on, yielding a similar sieve as part (b). 3.8 Reduction of P hk(p) to Small Values of pk We will be using Euler Summation on the sum P p t hk(p) in our e orts to  nd 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  (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). 413.8. Reduction of P hk(p) to Small Values of pk Lemma 3.17. For all 2  l  k, x > ee e and v > ee; X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3   (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) =  (t; r; 1) li(t)r 1 : Then we have X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2 : : : X pk l+22Ppk l+3 pk l+2 v1=3   (v; pk l+2; 1) li(v) pk l+2  1  = X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 E(v; pk l+2; 1)  X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j: Let  (m) denote the number of divisors of m which are primes or prime powers. We use the estimate  (m) logm to get 423.8. Reduction of P hk(p) to Small Values of pk X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j  log(yk) X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j X pk l+3jpk l+2 1 p3 v1=9 X pk l+4jpk l+3 1 pk l+4 v1=27    X q yk X a2N qajpk 1 1  log(yk) X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j X pk l+3jpk l+2 1 p3 v1=9 X pk l+4jpk l+3 1 pk l+4 v1=27    X pk v1=3 k 1 pkjpk 1 1  (pk  1)  log y X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j X pk l+3jpk l+2 1 p3 v1=9 X pk l+4jpk l+3 1 pk l+4 v1=27    X pk v1=3 k 1 pkjpk 1 1 log v: Continuing in this manner we obtain X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j  log y(log v)l 1 X pk l+22Ppk l+3 pk l+2 v1=3 jE(v; pk l+2; 1)j  v log y log v using Bombieri{Vinogradov (2.13). As for the di erence between X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 li(v) pk l+2  1 433.8. Reduction of P hk(p) to Small Values of pk and X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 li(v) pk l+2 (3.14) we get that it is X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3 li(v) pk l+2(pk l+2  1)  X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    1X i=1 li(v) (ipk l+3 + 1)(ipk l+3)  X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+32Ppk l+4 pk l+3 v1=9 li(v) p2k l+3  X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+32Ppk l+4 pk l+3 v1=9 li(v) pk l+3qa  X q yk log q X a2N li(v)(log log v)l 2 q2a  X 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, X p t hk(p) = X q yk log q X a2N X pk2Pqa pk t1=3 k 1 X pk 12Ppk pk 1 t1=3 k 2    X p22Pp3 p2 t1=3  (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  : 443.8. Reduction of P hk(p) to Small Values of pk Proof. For a prime p, hk(p) = X p1jp X p2jp1 1    X pkjpk 1 1 X q yk  q(pk  1) log q = X p2jp 1    X pkjpk 1 1 X q yk  q(pk  1) log q since the only prime which can divide p is p itself. Hence X p t hk(p) = X p t X p2jp 1    X pkjpk 1 1 X q yk  q(pk  1) log q = X p t X p2jp1 1    X pkjpk 1 1 X q yk X pk2Pqa a2N log q = X q yk log q X a2N X pk2Pqa X pk 12Ppk    X p22Pp3 X p t p2Pp2 1 = X q yk log q X a2N X pk2Pqa X pk 12Ppk    X p22Pp3  (t; p2; 1): We wish to approximate  (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=3 i 1 and qa  t1=3 k : Using Lemma 3.15, we get for large qa X q yk log q X a2N qa>t1=3 k X pk2Pqa X pk 12Ppk    X p32Pp2  (t; p2; 1)  X q yk log q X a2N 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=3 k , then we get that the above is bounded by 453.8. Reduction of P hk(p) to Small Values of pk O  t log t(log log t)k 2 X q yk log q qa   t1 1=3 k log t(log log t)k 2 X q yk log q  t1 1=3 k log t(log log t)k 2yk: Now suppose qa  t1=3 k : Let l be the last index (supposing one exists) where pi > t1=3 i 1 By using (3.8) where l ranges from 2 to k; we can bound the large values of the pi. X q yk log q X a2N qa t1=3 k X pk2Pqa pk t1=3 k 1    X pl+12Ppl+2 pl+1 t1=3 l X pl2Ppl+1 pl>t1=3 l 1 X pl 12Ppl    X p22Pp3  (t; p2; 1)  X q yk log q X a2N qa t1=3 k X pk2Pqa pk t1=3 k 1    X pl+22Ppl+3 pl+2 t1=3 l+1 X pl+12Ppl+2 pl+1>t1=3 l pl 1l+1t  (pl+1)l log t  X q yk log q X a2N qa t1=3 k X pk2Pqa pk t1=3 k 1    X pl+22Ppl+3 pl+2 t1=3 l+1 X pl+12Ppl+2 pl+1>t1=3 l t pl+1 log t since pl is prime and l  k. By Brun-Titchmarsh (2.10) we get  X q yk log q X a2N qa t1=3 k t(log log t)k l qa log t  X q yk t(log log t)k l log q q log t  t(log log t)k 2 log y log t 463.9. Evaluation of the Main Term by (2.3) and since l  2. Hence we get X p t hk(p) = X q yk log q X a2N qa t1=3 k X pk2Pqa pk t1=3 k 1 X pk 12Ppk pk 1 t1=3 k 2    X p22Pp3 p2 t1=3  (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   nishing 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 de nition. De nition 3.19. Let 2  l  k and 2  u  t. Then de ne gk;l(u) = X q yk log q X a2N X pk2Pqa pk u1=3 l 1 X pk 12Ppk pk 1 u1=3 l 2    X pk l+22Ppk l+3 pk l+2 u1=3  (u; pk l+2; 1): Note that gk;k(t) is the summation in Lemma 3.18. Next we’ll exhibit a recursive formula satis ed by the gk;l. Lemma 3.20. Let 3  l  k, then gk;l(v) = li(v) Z 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  by li and then use partial summa- tion to recover  : Using Lemma 3.17 we get gk;l(v) = X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk l+3 pk l+2 v1=3  (v; pk l+2; 1) = X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+22Ppk 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  : 473.9. Evaluation of the Main Term We use Euler summation on the inner sum to get X pk l+22Ppk l+3 pk l+2 v1=3 1 pk l+2 =  (v1=3; pk l+3; 1) v1=3 + Z v1=3 2  (u; pk l+3; 1) u2 du: Our function then becomes gk;l(v) = li(v) X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2 : : : X pk l+32Ppk l+4 pk l+3 v1=3   (v1=3; pk l+3; 1) v1=3 + Z v1=3 2  (u; pk l+3; 1) u2 du  +O  v log y log v + li(v)(log log v)l 2  : We trivially estimate  (x; q; 1) by x=q inside the sum and then use Brun{ Titchmarsh (2.10) to get X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+32Ppk l+4 pk l+3 v1=3  (v1=3; pk l+3; 1) v1=3  X q yk log q X a2N X pk2Pqa pk v1=3 l 1 X pk 12Ppk pk 1 v1=3 l 2    X pk l+32Ppk l+4 pk l+3 v1=3 1 pk l+3  X q yk log q X a2N (log log v)l 2 qa  X q yk log q (log log v)l 2 q  (log log v)l 2 log y: Multiplying through by li(v)  nishes the lemma. We now require a lemma to  nd the asymptotic formula for hk using the previous recurrence relation. 483.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 X 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  rst by setting l = k, u = t and using Lemma 3.18. We’ll proceed with the  rst 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) = X q yk log q X a2N X pk2Pqa pk u1=3  (u; pk; 1) = li(u) X q yk log q X a2N X pk2Pqa 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) 493.9. Evaluation of the Main Term to get gk;2(u) = li(u) X q yk log q X a2N  log log u1=3  (qa) +O  log(qa)  (qa)   +O  u log y log u  = li(u)(log log u+O(1)) X q yk log q X a2N  1 qa +O  1 qa+1   +O  li(u) X q yk log2 q X a2N a qa  +O  u log y log u  = li(u)(log log u+O(1)) X q yk  log q q +O  log q q2   +O  li(u) X 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) Z v1=3 2 1 u2 gk;l 1(u)du+O  v(log log v)l 2 log y log v  = li(v) Z 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) Z 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  : 503.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  rst moment. Proof of Proposition 3.13. M1(x) = X p x hk(p) p = X p ee hk(p) p + X ee<p x hk(p) p = O(1) + X ee<p x hk(p)  1 x + Z x p dt t2  = O(1) + 1 x X ee<p x hk(p) + Z x ee dt t2 X ee<p t hk(p): Using t = x in Lemma 3.21 we get that X ee<p x hk(p) xyk 1 log y log x : Since X ee<p t hk(p) and X p t hk(p) di er by a constant, we get that 513.11. The Proof of the Second Moment M1(x) = O(1) + 1 x O  xyk 1 log y log x  + Z 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 Z x ee dt t2 t1 1=3 k log t(log log t)k 2yk = Z x ee ykdt t1+  yk; we conclude that M1(x) is O(yk) +O  yk 1 log y log x  + Z 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(yk) as needed. 3.11 The Proof of the Second Moment We now turn our attention to the second moment. Our  rst 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. 523.11. The Proof of the Second Moment Lemma 3.22. X q1;q2 yk log q1 log q2 X a1;a22N X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 X s2Pp3\Pr3 X p t p2Ps 1  t1  yk log y + t(log log t)2k 2 log t log2 y for some  > 0: Proof. Our sum is X q1;q2 yk log q1 log q2 X a1;a22N X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 X s2Pp3\Pr3 X p t p2Ps 1 = X q1;q2 yk log q1 log q2 X a1;a22N X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 X s2Pp3r3  (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 X q1;q2 yk log q1 log q2 X a1;a22N q a1 1 >t  2 X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 X s2Pp3r3  (t; s; 1)  X q1;q2 yk log q1 log q2 X a1;a22N q a1 1 >t  2 X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 t log t p3r3  X q1;q2 yk log q1 log q2 X a1;a22N 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 = minfajqa11 > t  2 g we get  X 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 X q1 yk log q1 X q2 yk log q2 q2  t1  yk log y 533.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 X q1;q2 yk log q1 log q2 X a1;a22N q a1 1 q a2 2  t  X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 X s2Pp3r3  (t; s; 1)  X q1;q2 yk log q1 log q2 X a1;a22N q a1 1 q a2 2  t  t(log log t)2k 2 qa11 q a2 2 log t  X q1;q2 yk log q1 log q2 t(log log t)2k 2 q1q2 log t = t(log log t)2k 2 log t  X 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  nish the second moment which is the  nal piece of the puzzle. Proof of Proposition 3.14. X p t hk(p) 2 = X p x  X p1jp X p2jp1 1    X pkjpk 1 1 X q yk  q(pk  1) log q  2 = X q1;q2 yk log q1 log q2 X a1;a22N X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p22Pp3 r22Pr3 X p t p2Pp2 p2Pr2 1 since the condition p1 j 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 543.11. The Proof of the Second Moment X q1;q2 yk log q1 log q2 X a1;a22N X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk ::: X p22Pp3 r22Pr3 p2 6=r2 X p t p2Pp2 p2Pr2 1 +O  t1  yk log y + t(log log t)2k 2 log t log2 y  : The sum becomes X q1;q2 yk log q1 log q2 X a1;a22N X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p22Pp3 r22Pr3  (t; p2r2; 1): If qa11 > t  1 , then so is p2, and hence by (3.10) we get X q1;q2 yk log q1 log q2 X a1;a22N q a1 1 >t  1 X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk    X p32Pp4 r32Pr4 t log2 t p3r3  X q1;q2 yk log q1 log q2 X a1;a22N 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 X q1;q2 yk log q1 log q2 X a22N 1 qa22  t1  1 log2 t(log log t)2k 4 X 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 ; 553.11. The Proof of the Second Moment we get X q1;q2 yk log q1 log q2 X a1;a22N q a1 1 ;q a2 2  t  1 X pk2Pqa11 rk2Pqa22 X pk 12Ppk rk 12Prk : : : X pi2Ppi+1 ri2Pri+1 X pi 12Ppi ri 12Pri    X p22Pp3 r22Pr3  (t; p2r2; 1)  X q1;q2 yk log q1 log q2 X a1;a22N 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 X q1;q2 yk log q1 log q2 q1q2  t(log log t)2k 2 log2 y log t : The above gives us X 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) = X p x hk(p)2 p = X p ee hk(p)2 p + 1 x X ee p x hk(p) 2 + Z x ee dt t2 X ee p t hk(p) 2  1 + 1 x  x1  yk log y + x(log log x)2k 2 log2 y log x  + Z x ee  t 1  yk log y + (log log t)2k 2 log2 y t log t  dt  y2k 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. 56Chapter 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  rst note that it su ces 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  rst inequality is in fact an equality if be = 4. (Also note that in this case, it would not be hard to show that  (ab) j b (a):) If (a; b) = 1, then e = 0 and 57Chapter 4. Iterates Between  and   (ab) = lcm  b 1;  (pe11 ); : : : ;  (p ek k )   (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 j b, then  (a) j  (b) since  (a) j  (a) j  (ma) for anym. More easily we see  (a) j  (b) and  (a) j  (b): Inductively we can therefore show  k(n) j 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  58Chapter 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. 59Chapter 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 ! 1: 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 j 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    pmax( 1; 1)1  ;   pmax( 2; 2)2  ; : : : ;   pmax( r; r)r   =   pmax( 1; 1)1 p max( 2; 2) 2 : : : p max( r; r) r  =  (lcm(a; b)): Lemma 5.2. Given a positive integer n = Qr i p  i i ; 605.1. Lower Bound for L(n) (a) L(n) = maxifL(p  i i )g: (b) L(p ) =   1 + L(p)  L(p) for   1: Note that these two equations imply L(n)  L(p) for all p j 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 de nition 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 j 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), de ne a set S(x) = S(x; Y ) = fp : p  Y;H(p) < c log log pg: From [10, Theorem 3] we have that #S(x)  x=(log x)K for some K > 1: If p j n for some p =2 S(x); and p  Y; 615.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 2 S(x) such that p j n or else n is composed entirely of primes less than or equal to Y: The number of n  x where there exists p j n with p 2 S(x) is bounded by X n x X pjn p2S(x) 1 = X p x p2S(x) X n x n 0 (mod p) 1  X p x p2S(x) x p = x Z x Y d(S(t)) t = x  jS(x)j x + Z x Y S(t)dt t2   x logK x + Z 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!1: 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 625.2. Upper Bound for L(n) show Theorem 1.7 is a corollary to the following main propostion, that the di erence 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)! 1 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): Speci cally 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 = Q 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) = maxif i  1 + L(p)g. Our  rst goal is to show that the number of n for which there exists a large  with p j n is small. Fixing a prime p and   2, the number n  x such that p j n is at most x=p : Hence the number of bad n is bounded by X p x x p  x xX m=2 1 m  x Z 1 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)!1: Therefore for almost all n  x we can assume L(n)  max pjn (L(p) +  (x)) = max pjn (L(p) + o((log x) ) 635.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 di erence 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)  maxfH(p) + Pk i=1( i  1)g where q ii kqi 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 Qk i=1  i < p: Therefore we need to maximize the sum Pk i=1( i 1) subject to Qk 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  xed 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 Pk 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 Pk 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 j qk 1  1; qk 1 j qk 2  1; : : : ; q1 j p  1; p j 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 X   b (x)(log x) X k (log x) X q x(cy)k q : 645.2. Upper Bound for L(n) Summing q over all integers at least 2 instead of primes as above and using   2 makes this  X   b (x)(log x) 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 pjn  H(p) + kX 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) ! 1 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 fY < p  x j L(p) > (log p) g: 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 X n x X p2S(x) pjn 1  X p2S(x) x p = xjS(x)j x + x Z x Y jS(t)jdt t2  x exp   (log x)  + x Z 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. 655.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 di erence L(p) H(p) to show that it is not too large. As we saw in the previous section, this di erence is created when a branch of the Pratt tree has pai j 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 p ai i kpi 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 pakn is O(x=Y a 1): Proof. The number of n is bounded by X n x X p>Y pakn 1  X 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 kpi 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 cl 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 665.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 pal+1l+1 j 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  xed 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 pal+1l+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 in nity. 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)!1: 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) 675.3. Conjecture for the Normal Order of L(n): If ql+1 = 2; since,  (2a) = 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 coe cient 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 L0(n) similar to L(n) except that  0(2a) = 2a 1 for all positive integers a; that we may get a di erent normal order, perhaps even 2 log log n= log(2): 68Chapter 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 ! 1: 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 69Chapter 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}os, Pomerance, and Schmutz obtained a lower bound for  (n) of exp  c1 log log n log log log n): With a di erent constant, they also obtained an upper bound of the same form for in nitely 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 in nitely 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 + 1 k 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. 70Bibliography [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 atai 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 anic a. 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}os, 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 auser Boston, Boston, MA, (1990), 165{204. [9] P. Erd}os, 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 certi cate, 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 an, On a theorem of Hardy and Littlewood, J. London Math. Soc. 9 (1934), 274{276. 72Appendix A The Turan{Kubilius Inequality The Tur an{Kubilius Inequality is a result in probabilistic number theor. It is useful in  nding normal orders of additive arithmetic functions. The theorem was originally proved in a special case by Tur an [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 an were subsequently extended by Kubilius to more general additive functions. Theorem A.1 (Tur an{Kubilius). For any complex additive function f we have X n x jf(n) A(x)j2  xB(x)2 (A.1) where A(x) = X pk x f(pk)(1 p 1) pk ; B(x)2 = X pk x jf(pk)j2 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 X n x jf(n) M1(x)j 2  xM2(x) 2 where M1(x) = X p x f(p) p ; M2(x) 2 = X p x jf(p)j2 p : 73Appendix 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 = X pk x jf(p)j2 pk  X p x jf(p)j2 X k 1 1 pk  X p x jf(p)j2 1 p : As for A(x); the sum becomes A(x) = X pk x f(p)(1 p 1) pk = X pk x  f(p) pk  f(p) pk+1  Using Cauchy{Schwarz (2.14) the di erence between A(x) and M1(x) is at most X p x jf(p)j p2   X p x 1 p2 X p x jf(p)j2 p2  1=2  B(x): Therefore X n x jf(n) M1(x)j 2  2 X n x  jf(n) A(x)j2 + jA(x) M1(x)j 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 = X n x f2(n) 2A X n x f(n) + bxcA2 := S2  2AS1 + bxcA 2: (A.2) 74Appendix A. The Turan{Kubilius Inequality Since f(n) is additive, f(n) = P pkkn f(p k): Inserting this into S1 yields S1 = X n x X pkkn f(pk) = X pk x f(pk)   x pk    x pk+1    xA X pk x f(pk) using bxc  byc  x y  1: As for S2 we obtain S2 = X n x  X pkkn f(pk)  2 = X n x X pkkn f(pk) X qlkn f(ql): Splitting this up into the two cases where p = q or p 6= q yields S2 = X pk x f2(pk) X n x pkkn 1 + X pk x ql x q 6=p f(pk)f(ql) X n x pkkn qlkn 1  x X pk x f2(pk) pk + X 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 X pk x ql x q 6=p f(pk) pk (1 p 1) f(ql) ql (1 q 1) + 2 X 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 X pk x f(pk) + 2S3 +A 2: (A.3) Using Cauchy{Schwarz (2.14) on S3 yields S3   X pk x ql x f(pk)f(ql) pkql X pk x ql x pkql  1=2  B2  X n x n  1=2  xB2: 75Appendix A. The Turan{Kubilius Inequality Using Cauchy{Schwarz (2.14) again yields X pk x f(pk)   X pk x f2(pk) pk X pk x pk  1=2 = B  X 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  (x) +  (x1=2) +     x= log x: This bound implies X pk x f(pk) B  x2 log x  1=2 = B x p log x : As for A we use an estimate of Mertens [17, Theorem 2.7 (d)] and Cauchy{ Schwarz (2.14), implying A X pk x f(pk) pk   X pk x f2(pk) pk X 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

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
Japan 10 0
United States 4 1
France 1 0
Poland 1 0
City Views Downloads
Tokyo 10 0
Ashburn 4 0
Unknown 2 28

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0073354/manifest

Comment

Related Items