Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Partitions into prime powers and related divisor functions Mullen Woodford, Roger 2008

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

Item Metadata

Download

Media
ubc_2008_fall_mullenwoodford_roger.pdf [ 644.5kB ]
Metadata
JSON: 1.0066490.json
JSON-LD: 1.0066490+ld.json
RDF/XML (Pretty): 1.0066490.xml
RDF/JSON: 1.0066490+rdf.json
Turtle: 1.0066490+rdf-turtle.txt
N-Triples: 1.0066490+rdf-ntriples.txt
Original Record: 1.0066490 +original-record.json
Full Text
1.0066490.txt
Citation
1.0066490.ris

Full Text

Partitions into Prime Powers and Related Divisor Functions by Roger Mullen Woodford  B.Sc., The University of Manitoba, 2003 M.Sc., The University of British Columbia, 2005  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Doctor of Philosophy in The Faculty of Graduate Studies (Mathematics)  The University Of British Columbia (Vancouver) August, 2008 c Roger Mullen Woodford 2008  Abstract In this thesis, we will study a class of divisor functions: the prime symmetric functions. These are polynomials over Q in the so-called elementary prime symmetric functions, whose values lie in Z. The latter are defined on the nonnegative integers and take the values of the elementary symmetric functions applied to the multi-set of prime factors (with repetition) of an integer n. Initially we look at basic properties of prime symmetric functions, and consider analogues of questions posed for the usual sum of proper divisors function, such as those concerning perfect numbers or Aliquot sequences. We consider the inverse question of when, and in how many ways a number n can be expressed as f (m) for certain prime symmetric functions f . Then we look at asymptotic formulae for the average orders of certain fundamental prime symmetric functions, such as the arithmetic function whose value at n is the sum of k-th powers of the prime divisors (with repetition) of n. For these last functions in particular, we also look at statistical results by comparing their distribution of values with the distribution of the largest prime factor dividing n. In addition to average orders, we look at the modular distribution of prime symmetric functions, and show that for a fundamental class, they are uniformly distributed over any fixed modulus. Then our focus shifts to the related area of partitions into prime powers. We compute the appropriate asymptotic formulae, and demonstrate important monotonicity properties. We conclude by looking at iteration problems for some of the simpler prime symmetric functions. In doing so, we consider the empirical basis for certain conjectures, and are left with many open problems.  ii  Table of Contents Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  ii  Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . .  iii  List of Tables  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  v  Glossary of Fundamental Notation . . . . . . . . . . . . . . . . .  vi  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Dedication Preface  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  ix  1 Divisor Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Perfect Numbers, Variations on Perfect Numbers, and Aliquot Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1  2 Prime Symmetric Divisor Functions . . . . . . . . . . . . . . 2.1 Elementary Prime Symmetric Divisor Functions . . . . . . . 2.2 Basic Properties of the Elementary Prime Symmetric Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  4 5  3 The 3.1 3.2 3.3 3.4  Second Elementary Prime Ω(n) = 3 . . . . . . . . . . . Ω(n) = 4 . . . . . . . . . . . Ω(n) = 5 . . . . . . . . . . . Inverse Problems . . . . . . .  Symmetric Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . . . . .  . . . . .  . . . . .  2  8  . . . . .  13 13 14 14 16  4 Higher Elementary Prime Symmetric Functions . . . . . . 4.1 The Hunt for s3 -cycles . . . . . . . . . . . . . . . . . . . . .  22 25  iii  Table of Contents 5 The Power Prime Symmetric Divisor Functions . . . . . . 5.1 The Average Order of ek . . . . . . . . . . . . . . . . . . . . 5.2 A Statistical Look at ek . . . . . . . . . . . . . . . . . . . . .  30 32 36  6 The Average Order of sk,  47  . . . . . . . . . . . . . . . . . . . .  7 Modular Distribution of Prime Symmetric Functions 7.1 Perron’s Formula . . . . . . . . . . . . . . . . . . . . . 7.2 Bounding L(s, χ) and ζ(s) . . . . . . . . . . . . . . . . 7.3 Additive Prime Symmetric Functions . . . . . . . . . . 7.4 The Distribution of sk Modulo q . . . . . . . . . . . . . 7.4.1 The Dirichlet Series . . . . . . . . . . . . . . . . 7.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5.1 s2 modulo 3 . . . . . . . . . . . . . . . . . . . . 7.5.2 s3 modulo 2 . . . . . . . . . . . . . . . . . . . . 7.5.3 sk modulo a prime q . . . . . . . . . . . . . . .  . . . . . . . . . .  8 Partitions into Prime Powers . . . 8.1 Introduction . . . . . . . . . . . . 8.2 Monotonicity . . . . . . . . . . . . 8.3 Asymptotic Formulae . . . . . . . 8.3.1 Asymptotic Formula for the 8.3.2 Bounding from Above . . . 8.3.3 Bounding from Below . . .  . . . .  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Generating Function . . . . . . . . . . . . . . . . . . . . . . . .  9 Sequences of Iterates . . . . . . . . . . . . . . . . . 9.1 Density of Sets with Given Terminal Value . . . . 9.2 Distribution of Products in Partitions into Primes 9.3 The Number of Iterations of s until termination . 9.3.1 The Average order of t(n) . . . . . . . . . 9.4 Iterating s + b . . . . . . . . . . . . . . . . . . . .  . . . . . .  . . . . . .  . . . . . .  . . . . . . . . . .  . . . . . . . . . .  58 58 61 65 70 71 77 77 79 81  . . . . . . . . .  . 82 . 82 . 82 . 98 . 99 . 107 . 109  . . . . . .  . . . . . .  . . . . . .  117 117 125 126 129 130  Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135  Appendices A Maple Algorithms  . . . . . . . . . . . . . . . . . . . . . . . . . 139  iv  List of Tables  Table 1. Table 2. Table 3. Table 4. Table 5. Table 6. Table 7. Table 8.  Initial values of r(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 s∗k -perfect numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 s3 (n) modulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Selected values of Bp (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Selected values of Bp (x)/x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Iterations of s2 terminating in 39 . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Average order of t(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 (s+b)-cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134  v  Glossary of Fundamental Notation N0 , N∞ , N0,∞ , P sk sk, ek r(k) rf , rk, , rk Ek (n, r) pA (n) (k) pA (n) P (n), bk (x, y), Ψ(x, y) Bm , Bm tf  4 4 4 4 9 16 22 37 37, 82 38 117 126  vi  Acknowledgements Two faculty members at UBC have given me the invaluable insight, direction, encouragement and support that has made this possible. For these things it is my privilege to thank and acknowledge my supervisor Dr. Izabella Laba, and Dr. Greg Martin, who is also on my supervisory committee. I also wish to express my gratitude to the Natural Sciences and Engineering Research Council, and the University of British Columbia for generous funding and employment opportunities.  vii  Dedication To my wife Trish, a friend and source of inspiration and moderation through this and many other adventures.  viii  Preface Who so in pompe of proud estate (quoth she) Does swim, and bathes himselfe in courtly blis, Does waste his dayes in darke obscuritee, And in oblivion ever buried is: Where ease abounds, yt’s eath to doe amis; But who his limbs with labours, and his mind Behaves with cares, cannot so easie mis. Abroad in armes, at home in studious kind Who seekes with painfull toile, shall honor soonest find. Belphoebe to Braggadocchio The Faerie Queene Sir Edmund Spenser  The work found here began in 2001 when I began to think about iterating the sum of prime factors with repetition function. Later, I generalized this function by looking at other symmetric polynomials in the paper “A Variation on Perfect Numbers” [46] published in Integers: Electronic Journal of Combinatorial Number Theory, in 2004, which in turn became the starting point for my Masters thesis [47]. With tools from analytic number theory and the theory of partitions, I have been able to prove many new results and connect them to other areas, and research done by prominent mathematicians. One of the key examples of work that is important to us is that of Hardy and Ramanujan on partition functions [19] which in the instance of partitions into powers of primes we correct and generalize. To do this we cite the work of Bateman and Erd˝os ([3], [4]) on the monotonicity of partition functions, which we use to find bounds for when difference functions of partitions into primes cease to be negative. Levan’s work [27] on the average order of the sum of k-th powers of primes is important to us as well, as is that of Alladi and Erd˝os on the ix  Preface uniform distribution modulo 2 of the sum of prime factors function. We will compute the average orders of functions generalizing these, and extend the modular distribution results to other moduli. Work on the functions we generalize in this treatise is scattered across the literature of the twentieth century. It is our intent not only to bring this work together and add to it as much as possible, but to ask fresh questions, and provide some fresh answers as well. The majority of the work found in this treatise is new, and much of that which was contained in my Masters thesis has been improved upon. Chapters 1 through 4, the initial pages of Chapter 5, and Section 9.4 originate in my Masters thesis, and are included for completeness with appropriate revisions and notational changes. The average order and statistical results of Chapters 5 and 6 have now been published in a separate paper in Integers [50]. Chapter 7, dealing with modular distribution derives from a paper submitted to the Journal of Number Theory. The monotonicity results of Chapter 8 are based on my paper [49] published in the Journal of Integer Sequences, though they have been thoroughly revised with a fresh approach. As well, a paper in which the asymptotic formulae for partitions into prime powers and their difference functions are derived (also in Chapter 8) has been accepted for publication in the Canadian Journal of Mathematics [48]. Finally, a word on notation: much of the notation used in this thesis is chapter, or occasionally, section specific. For this reason, a comprehensive glossary of notation would be challenging, or even misleading in the few instances where the same, or similar symbols are used to mean different things in different sections. To remedy this problem I have done two things. First, I have endeavored to make it abundantly clear in the context of each chapter (or section) what meanings are to be attributed to which symbols. Second, in the “Glossary of Fundamental Notation” I have indicated the page on which some of the universal symbols are defined.  x  Chapter 1  Divisor Functions The sum of divisors function σ : N → N defined by d  σ(n) = d|n  has been thoroughly studied for centuries. The first, most natural generalization of σ are the functions σα defined by dα ,  σα (n) = d|n  where α ≥ 0 is a real number. With this definition, σ0 counts the number of positive divisors of n. Sometimes σ0 is denoted by d, and σ1 is simply σ. Other relevant divisor-related functions are ω, which counts the number of distinct primes dividing a number n, and Ω, which counts the number of primes dividing n, with multiplicity. The functions σα are multiplicative, that is if m and n are relatively prime, then σα (mn) = σα (m)σα (n). Derivations for the asymptotic formulae of the average orders for σα can be found in Apostol [2]. In case α = 0, we have that for all x ≥ 1, √ d(n) = x log x + (2C − 1)x + O( x), n≤x  where C is Euler’s constant. Also, σ(n) = n≤x  π2 2 x + O(x log x). 12  Furthermore, for α > 0, and α = 1, we have σα (n) = n≤x  ζ(α + 1) α+1 x + O(xβ ), α+1  where β = max {1, α}, and ζ is the Riemann-zeta function. 1  Chapter 1. Divisor Functions In this exposition, we will define and study a new class of divisor functions: the prime symmetric divisor functions. These functions are not multiplicative in general. The following notions, those of perfect numbers, and aliquot sequences, and some of their generalizations based on the usual multiplicative divisor functions, or related functions, will be extended to the prime symmetric divisor functions.  1.1  Perfect Numbers, Variations on Perfect Numbers, and Aliquot Sequences  Several good texts detailing the basic theory of perfect numbers exist (cf. [10], [15], [28] and [42]). In addition, many variations on perfect numbers have been defined and studied. Examples can be found in [12], [20], [23], [29], [30], [35], [40] and [41]. Let σ ∗ (n) = σ(n) − n, that is σ ∗ (n) sums all the proper divisors of n. We say that n is perfect if σ ∗ (n) = n, excessive (or abundant) if σ ∗ (n) > n, and defective (or deficient) if σ ∗ (n) < n. The first few perfect numbers are 6, 28, 496, 8128, 33550336. It has been known since Euclid’s day that if p, and q = 2p − 1 are prime, then the number n = 2p−1 (2p − 1) is perfect. This can be readily checked, since its proper divisors correspond to the set {1, 2, . . . , 2p−1 , q, 2q, . . . , 2p−2 q}, and hence their sum is: σ ∗ (n) = 1 + 2 + · · · + 2p−1 + q + 2q + · · · + 2p−2 q = 2p − 1 + q(2p−1 − 1) = (2p − 1)2p−1 = n. Euler proved conversely, that any even perfect number must be of this form. The proof is the same as that found in [33]. Theorem 1.1. An even number n is perfect if and only if n = 2p−1 q, where p, and q = 2p − 1 are both prime. Proof. We need only prove the only if part. Suppose n is an even perfect number. Write n = 2k−1 m, where 2k−1 ||n, and so k ≥ 2, and m is odd. Since σ(n) = 2n, we have: 2n = 2k m = σ(2k−1 m) = (2k − 1)σ(m). Hence, 2k − 1 divides m, so we may write m = (2k − 1) . Using this value of m, we get 2k = σ((2k − 1) ). 2  Chapter 1. Divisor Functions If  > 1, then 1, , and (2k − 1) are distinct divisors of m, and so 2k = σ((2k − 1) ) ≥ 1 + + (2k − 1) = 2k + 1,  a contradiction. Thus  = 1 and so  2k = σ(2k − 1) = 1 + (2k − 1) +  d, d|(2k −1) 1<d<2k −1  so clearly, 2k − 1 must be prime. Furthermore, it is trivial to see that if k is composite, then 2k − 1 factors, thus q is also prime. It is still not known if there are infinitely many even perfect numbers, or equivalently, if there are infinitely many Mersenne primes (primes of the form 2p − 1). It is also unknown whether or not there exists an odd perfect number. The equivalent definition for a perfect number, i.e. n is perfect if σ(n) = 2n motivates one generalization, that of multiperfect numbers. A number n is said to be k-multiperfect if σ(n) = kn. For instance, σ(120) = 360, so 120 is 3-multiperfect. As already stated, there are numerous variations of the notion of perfect number. ∗(k) (n)}t The sequence {σ ∗(k) (n)}∞ k=0 , or the sequence {σ k=0 if it begins to cycle after t + 1 iterations, is called the aliquot sequence of n. That is, the aliquot sequence of n is obtained from n by iterating the sum of proper divisors function σ ∗ . The aliquot sequence of a number n can fluctuate up and down. The unsolved Catalan-Dickson problem is to determine whether for every n, the sequence {σ ∗(k) (n)}∞ k=0 is eventually periodic. Instances are known when the shortest period is longer than 1. For instance: σ∗  σ∗  σ∗  σ∗  σ∗  12496 −→ 14288 −→ 15472 −→ 14536 −→ 14264 −→ 12496. The case when the period is of length 2 has a special name. If σ ∗(2) (n) = n = σ ∗ (n), then the pair {n, σ ∗ (n)} is called amicable. One such amicable pair is {220, 284}.  3  Chapter 2  Prime Symmetric Divisor Functions The prime symmetric divisor functions are defined in terms of the elementary prime symmetric functions. Write N0 , N∞ and N0,∞ for the sets N ∪ {0}, N ∪ {∞} and N ∪ {0, ∞} respectively, and denote the set of primes by P. Definition 2.1. Let k ∈ N0 . Define sk : N0 → N0 as follows: if n = 0, then sk (0) = 0, for all k. For n > 0, if k = 0, sk (n) = 1. If k > 0, and n = p1 · · · pr , where r = Ω(n) is the number of prime factors (with multiplicity) of n, then sk (n) =  pi1 · · · pik ,  where the sum is taken over all products of k prime factors from the multi-set {p1 , . . . , pr }. We say sk is the k th elementary prime symmetric function. Note that if k > r, then the sum is empty, so sk (n) = 0. Definition 2.2. A function f : N0 → Z is called a prime symmetric function if it can be expressed as a polynomial over Q in the elementary prime symmetric functions s0 , s1 , . . .. The elementary prime symmetric functions sk are a special case of a larger class of functions: Definition 2.3. Let k, ∈ N0 . We define sk, (0) = 0. If n = p1 · · · pr ∈ N, where the pi are primes, not necessarily distinct, then (pi1 · · · pik ) .  sk, (n) = 1≤i1 <...<ik ≤r  We write the function s1, as e , and call e the -th “power prime symmetric function.” Oftentimes we shall use the subscript k in place of in the power prime symmetric functions, so it is important to keep watch for that. 4  Chapter 2. Prime Symmetric Divisor Functions Note that e0 (n) = Ω(n), for n ∈ N, and that sk,1 = sk . Also observe that by the fundamental theorem of symmetric functions, the functions sk, are indeed prime symmetric. In fact, in Chapter 5, we will express the functions e in terms of the elementary prime symmetric functions and vice versa. In Chapter 6, we shall find the average order of sk, . In the standard theory of symmetric polynomials, s is usually used to indicate Schur functions, and e the elementary symmetric polynomials, so please bear in mind the difference in notation. Now we will extend the notion of perfection, aliquot sequences, etc. to more general classes of functions. Definition 2.4. Let S ⊂ Z, and suppose f : S → Z. If n ∈ S satisfies f (n) = n, then we say that n is f -perfect. If f (n) > n, then we say that n is f -excessive. If f (n) < n, then we say that n is f -defective. If f (n) ≥ n, then we say that n is f -special. If the sequence {f (i) (n)}∞ i=0 is well defined, then it is called the f -sequence of n. If the sequence {f (i) (n)}i=0 is well-defined, we say it is an f -sequence of length . A finite sequence {n0 , . . . , n } is an f -cycle of length if the following conditions are satisfied: 1.  > 1,  2. n0 , . . . , n  −1  are distinct and n = n0 , and  3. f (ni ) = ni+1 , for i = 0, 1, . . . , − 1.  2.1  Elementary Prime Symmetric Divisor Functions  Observe that if Ω(n) < k, we have sk (n) = 0. There is an alternate way of defining the functions sk . Given n = p1 · · · pr ∈ N, set r  Sn (x) =  (1 + pi x). i=1  Then sk (n) is the coefficient of xk in Sn (x). The empty product is taken to be 1. Example 2.5. s0 (12) = 1, s1 (12) = 2+2+3 = 7, s2 (12) = 2·2+2·3+2·3 = 16, s3 (12) = 12, and s4 (12) = 0. 5  Chapter 2. Prime Symmetric Divisor Functions If Ω(n) = k, then we trivially have that n is sk -perfect. This is rather uninteresting, so we define a related version of sk -perfection to avoid this. Definition 2.6. Let n ∈ N satisfy Ω(n) > k. If sk (n) = n, then we say that n is s∗k -perfect. If sk (n) ≥ n, then we say that n is s∗k -special. Example 2.7. If p is prime, then pp is an s∗p−1 -perfect number, since sp−1 (pp ) =  p pp−1 = pp . p−1  In fact, this example has a form of converse, first proved in [46]: Theorem 2.8. The prime power pα is s∗k -perfect if and only if α = p and k = p − 1. Proof. We have seen that this is sufficient, now suppose k < α, and sk (pα ) = pα . Then α = pα−k . (2.1) k For 1 < k < α − 1, αk is divisible by two distinct prime factors, hence we must have k = 1 or α − 1. Now 4 = 22 , is the only s∗1 -perfect number, and corresponds to the case where k = 1 = α − 1. Hence we may assume k = α − 1, which from (2.1) implies that α = p and k = p − 1. This proves the theorem. The next natural question to ask is: when is pα q β an s∗k -perfect number for some k? This turns out to be substantially more difficult than the previous question. However, we will come up with some necessary conditions and also look at some special cases. Theorem 2.9. Suppose that p and q are distinct primes and that α, β > 0. If pα q β is s∗k -perfect, then α = k, and β = k. Proof. Suppose α = k. Then sk (pα q β ) = pα q β is equivalent to pk +  k β k β β k pk−1 q + ··· + p q k−1 + q = pk q β . k−1 1 1 k−1 k  This is impossible as only the right side of this equation is divisible by q. We get a similar contradiction if β = k.  6  Chapter 2. Prime Symmetric Divisor Functions From computer searches, there are two numbers of the form pα q β known to be s∗k -perfect for some k. The number 48 = 24 · 3 is s∗2 -perfect, and 46875 = 3 · 56 is s∗5 -perfect. Note that these are both of the form pα q. It is to this form that we will specialize our next theorem. Theorem 2.10. Let p and q be distinct primes. (i) Suppose that p > q. If p ≥ k + 1, and q ≥ (α + 1)/(α − k + 1), then pα q is not s∗k -perfect. (ii) Suppose that p < q. If p ≥ k + 1, then pα q is not s∗k -perfect. Proof. (i) In the first instance, suppose that pα q is s∗k -perfect. We have sk (pα q) =  α k α p + pk−1 q = pα q. k k−1  This implies that α α p+ q = pα−k+1 q, k k−1 or  Letting  α α p+ q = pα−k+1 q. α−k α−k+1 = α − k + 1, we have α α p+ q = p q. −1  Since p > q, we have that α α p+ q< −1  α α p+ p= −1  α+1  p.  If we show that the assumption in (i) implies that α+1  ≤p  −1  ···  α− +3 2  q,  (2.2)  then we are done. But α+1  =  α+1  α −1  There are terms in this product. The first term assumption. Since  α+1  α− +2 1 satisfies  α+1  . ≤ q by  α α−1 α− +2 ≤ ≤ ··· ≤ ≤ p, −1 −2 1 7  Chapter 2. Prime Symmetric Divisor Functions by assumption, (2.2) holds and we have proved (i). (ii) The proof of (ii) is similar. In this case sk (pα q) < where  α+1  q,  is as before. Hence it suffices to prove that α+1  ≤p .  Since p ≥ α − + 2 = k + 1, this indeed holds, so (ii) is proved.  2.2  Basic Properties of the Elementary Prime Symmetric Functions  The following proposition from [46] is an immediate consequence of the definition. Proposition 2.11. If n = pα1 1 · · · pαr r , then sk (n) = i1 +···+ir =k i1 , ...,ir ≥0  α1 αr i1 ··· p · · · pirr . i1 ir 1  Proposition 2.12. For nonnegative integers m and n, the function sk satisfies k  sk (mn) =  sk−i (m)si (n). i=0  Proof. If m = 1, or n = 1, the result is immediate, as it is if k = 0. If k > 0, m = p1 . . . pr , and n = q1 . . . qs , let S = {p1 , . . . , pr , q1 , . . . , qs }. Then r1 · · · rk .  sk (mn) = {r1 ,...,rk }⊂S  We collect the terms of this sum having k − i factors from m, and i factors from n. The sum of these is equal to sk−i (m)si (n). Summing as i ranges from 0 to k gives the desired result. 8  Chapter 2. Prime Symmetric Divisor Functions Corollary 2.13. Let n, k ∈ N, and let p and q be primes, with p < q, and suppose Ω(n) ≥ k. If pn − sk (pn) ≥ 0, then pn − sk (pn) < qn − sk (qn). Proof. Since Ω(n) ≥ k, we have that sk (n) > 0. Therefore, since pn − sk (pn) ≥ 0, it follows that n ≥ sk−1 (n) + sk (n)/p > sk−1 (n). Hence, qn − sk (qn) = qn − qsk−1 (n) − sk (n) > pn − psk−1 (n) − sk (n) = pn − sk (pn).  In searching for sk -cycles and s∗k -perfect numbers, it is essential to know when sk (n) ≥ n. We search by fixing Ω(n), and systematically checking all products of Ω(n) primes. The corollary tells us that if sk (pn) < pn, then for any q > p, qn is also sk -defective. Lemma 2.14. Let k, n ∈ N. Then there exists an r > k such that if Ω(n) ≥ r, then n is sk -defective. Let r(k) denote the least such r. Then r(k) = min  r : r ≥ k,  r k  < 2r−k  .  Proof. There is an r > k such that the function f (t) =  t k  satisfies f (t) < g(t) for all t ≥ r, where g(t) = 2t−k , since f is a polynomial, and g is an exponential function. Now suppose t ≥ r, and let p1 , . . . , pt be t primes. Then t k  t < 2t−k , which implies t−k 1 t 1 ≤ < 1, t−k pi1 · · · pit−k t−k 2 =  9  Chapter 2. Prime Symmetric Divisor Functions where the sum is taken over all i1 , . . . , it−k such that 1 ≤ i1 < · · · < it−k ≤ t. This implies that pi1 · · · pik < p1 · · · pt , where the sum is taken over all i1 , . . . , ik such that 1 ≤ i1 < · · · < ik ≤ t. In other words, sk (p1 · · · pt ) < p1 · · · pt . Now we prove the second statement. First note that if n = 2r(k)−1 , then sk (n) =  r(k) − 1 k 2 ≥ 2r(k)−1−k+k = 2r(k)−1 = n. k  In other words there are numbers satisfying Ω(n) = r(k) − 1 that are sk excessive. Now let us see by induction that if k < r < 2k, then 2r−k ≤  r . k  (2.3)  Note that this case does not apply when k = 1, so we may assume k ≥ 2. Clearly then, (2.3) holds when r = k + 1. Now, for k + 1 ≤ r ≤ 2k − 2, suppose 2r−k ≤ kr . Then 2r+1−k ≤ 2  r k  =2 1−  k r+1  r+1 k  ≤  r+1 . k  So (2.3) holds by induction. The inequality 2k k  ≥ 2k  holds for all k ≥ 1, and so we have r(k) > 2k. With this in mind, let r(k) be as claimed in the last part of the statement of the lemma, for some k ≥ 1. We argue inductively. Let t > r(k), and suppose that t−1 k Then 2  t−1 k  < 2t−1−k .  < 2t−k .  Since t > 2k, we have t < 2(t − k), and so t k  =  t(t − 1) · · · (t − k + 1) 2(t − 1)(t − 2) · · · (t − k) t−1 < =2 . k! k! k 10  Chapter 2. Prime Symmetric Divisor Functions Hence  t k  t−1 k  <2  < 2t−k ,  and the proof is complete by induction. Remark 2.15. An instructive way of viewing Lemma 2.14 is the following equality of sets: r:  r k  < 2r−k  = {r(k), r(k) + 1, . . .}.  (2.4)  The first few values of r(k) are given in the following table:  Table 1. Initial Values of r(k) k 1 2 3 4 5 6 7 8 9 10  r(k) 3 6 10 14 19 23 27 31 36 40  From the table it appears as though r(k) is approximately linear. This is indeed the case as was observed by Dr. Greg Martin who suggested the following. We will make use of Stirling’s Formula to compute an asymptotic formula for r(k): Γ(x + 1) =  x e  x√  2πx(1 + O(1/x)),  (2.5)  as x → ∞ (cf. [32], p.503). Note that r = r(k) if and only if r k  < 2r−k ≤ 2  r−k r  A simple induction can be used to show that hence that r(k) ≤ 5k. Thus, r(k) k.  r . k 5k k  (2.6)  < 24k for all k ∈ N, and  11  Chapter 2. Prime Symmetric Divisor Functions The inequalities (2.6) are equivalent to 1  1 rr+ 2 √ 1 1 2π k k+ 2 (r − k)r−k+ 2 ≤2  r−k r  1 k  1+O  < 2r−k  1  1 rr+ 2 √ 1 1 2π k k+ 2 (r − k)r−k+ 2  1+O  1 k  .  (2.7)  Write ck = r(k)/k = r/k. Clearly 2 < ck ≤ 5. Now (2.7) becomes 1  ck k+ 1  k − 2 ck 2 1 √ 1 2π (ck − 1)(ck −1)k+ 2 ≤2  ck − 1 ck  1 k  1+O 1  < 2(ck −1)k  ck k+ 1  k − 2 ck 2 1 √ 1 2π (ck − 1)(ck −1)k+ 2  1+O  1 k  .  (2.8)  Taking logarithms and dividing through by k, we see that (2.8) is equivalent to log k (ck − 1) log 2 = ck log ck − (ck − 1) log (ck − 1) + O . (2.9) k Let c be the root, c ≈ 4.403497879, of the equation (c − 1) log 2 = c log c − (c − 1) log (c − 1), and let f (x) = (x − 1) log 2 − x log x + (x − 1) log (x − 1), on [4, 5], so that f (c) = 0. It is easily verified that f (c) = 0, and that in an interval about c, f is bounded, and bounded away from 0. By (2.9), f (ck ) = O(log k/k), so by the Mean Value Theorem we can conclude that ck = c + O  log k k  .  Thus we have proved the following theorem: Theorem 2.16. As k → ∞, r(k) = ck + O(log k),  (2.10)  where c is the root of the equation (c − 1) log 2 = c log c − (c − 1) log (c − 1). The properties of s1 -perfection etc., corresponding to the first elementary prime symmetric function s1 are easily characterized. The s1 -perfect numbers are the primes and 4, the latter being the only s∗1 -perfect number. All other numbers are s1 -defective. Clearly there are no s1 -cycles. We now investigate these properties in the second elementary prime symmetric function. 12  Chapter 3  The Second Elementary Prime Symmetric Function To describe all s∗2 -perfect numbers and all s2 -cycles we need to find all numbers n such that 2 < Ω(n) < 6, with s2 (n) ≥ n, since r(2) = 6. To do this we use the algorithm mentioned after Corollary 2.13, the approach taken in [46]. That is, we shall temporarily fix Ω(n), and increase the prime divisors until we cease to obtain s∗k -special numbers. We begin with Ω(n) = 3.  3.1  Ω(n) = 3  Applying s2 we have: s2 (2 · 2 · p) = 4p + 4 > 4p, s2 (2 · 3 · p) = 5p + 6 < 6p, when p > 6. Below we find all s∗2 -special numbers not of the forms listed above s2 (2 · 3 · 3) = 21 > 18, s2 (2 · 3 · 5) = 31 > 30, s2 (2 · 3 · 7) = 41 < 42, s2 (3 · 3 · 3) = 27, s2 (3 · 3 · 5) = 39 < 45. By Corollary 2.13 there are no other s∗2 -special numbers satisfying Ω(n) = 3 than those already mentioned. Thus 27 is the only s∗2 -perfect number satisfying Ω(n) = 3. Iterating on all the s2 -excessive numbers above, save those of the form 4p, shows that none belong to an s2 -cycle. For example s  s  2 2 18 −→ 21 −→ 21 · · · .  13  Chapter 3. The Second Elementary Prime Symmetric Function  3.2  Ω(n) = 4  Applying s2 to numbers with Ω(n) = 4 we obtain s2 (2 · 2 · 2 · p) = 6p + 12 < 8p, when p > 6. From this together with Corollary 2.13 we can conclude that there are only finitely many s∗2 -special numbers with Ω(n) = 4. Iterating on 8p for p = 2, 3, 5, shows that none belongs to an s2 -cycle. Checking other cases: s2 (2 · 2 · 3 · 3) = 37 > 36, s2 (2 · 2 · 3 · 5) = 51 < 60, s2 (2 · 3 · 3 · 3) = 45 < 54. Hence there are no s∗2 -perfect numbers satisfying Ω(n) = 4. Iterating on the above s2 -excessive numbers shows that none belong to an s2 -cycle.  3.3  Ω(n) = 5  Applying s2 to numbers with Ω(n) = 5 we obtain s2 (2 · 2 · 2 · 2 · p) = 8p + 24 < 16p, when p > 3. Thus by Corollary 2.13 there are only finitely many s∗2 -special numbers with Ω(n) = 5. Iterating on 16p for p = 2, 3, shows that 48 is in fact s∗2 -perfect, and 32, which is s2 -excessive, does not belong to an s2 -cycle. Checking other cases: s2 (2 · 2 · 2 · 3 · 3) = 57 < 72, Hence 48 is the only s∗2 -perfect number satisfying Ω(n) = 5. We have proved the following theorem. Theorem 3.1. The numbers 27 and 48 are the only s∗2 -perfect numbers. Theorem 3.2. There are no s2 -cycles. Proof. An s2 -cycle must have a least element that is s2 -excessive. It is easily verified (as it was above in the case n = 18), that all of the finitely many s2 -excessive numbers not of the form 4p do not belong to s2 -cycles. Thus any such element must belong to the family of numbers of the form 4p. 14  Chapter 3. The Second Elementary Prime Symmetric Function We will show that in all but a few trivial cases s2 (s2 (4p)) < 4p, giving a contradiction. Now, s2 (4p) = 8((p + 1)/2). We may assume that p is odd, and set m = (p + 1)/2. Thus we will have a contradiction if the following holds: s2 (8m) < 8m − 4. This is equivalent to 12 + 6s1 (m) + s2 (m) < 8m − 4,  (3.1)  which is equivalent to 16 +6 p 1 · · · ps  s i=1  1 + p1 · · · pˆi · · · ps  1≤i<j≤s  1 < 8, p1 · · · pˆi · · · pˆj · · · ps  where m = p1 · · · ps . Here p1 · · · pˆi · · · ps is defined to be p1 · · · ps /pi , and p1 · · · pˆi · · · pˆj · · · ps is defined to be p1 · · · ps /pi pj . Since pi ≥ 2, this expression is implied by: 16 6s s(s − 1) 1 + s−1 + < 8, s 2 2 2 2s−2 which holds for all s ≥ 4. If s = 1, then m is prime, and so condition (3.1) becomes: 12 + 6m < 8m − 4, which holds for all m > 8. It is easily verified for m = 2, 3, 5 and 7, that 8m does not belong to an s2 -cycle. For s = 2, we can write m = pq. The only values of m for which (3.1) fails are determined by the prime pairs (p, q) = (2, 2), (2, 3). In both cases, 8m does not belong to an s2 -cycle. Finally for s = 3, if m = pqr, only for the triple (p, q, r) = (2, 2, 2) does m fail to satisfy (3.1). Again, in this case, 8m does not belong to an s2 -cycle. Remark 3.3. The longest increasing s2 -sequence is s  s  s  s  s  2 2 2 2 2 8 −→ 12 −→ 16 −→ 24 −→ 30 −→ 31.  15  Chapter 3. The Second Elementary Prime Symmetric Function  3.4  Inverse Problems  For a given prime symmetric function f , and an integer n, we are interested in the number of solutions to the equation f (m) = n. This leads to a new class of arithmetic functions. We state the following definition in full generality, then specialize it. Definition 3.4. Let S ⊆ Z, and suppose f : S → Z. Let rf : N → N0,∞ be the function whose value at n is rf (n) = |f −1 [{n}]|. In case there are infinitely many solutions to the equation f (m) = n, we say rf (n) = ∞. Moreover, let rsk, = rk, , and r s k = rk . Example 3.5. r1 (1) = 0, but for all n ≥ 2, r1 (n) ≥ 1. In fact, limn→∞ r1 (n) = ∞. To see this, simply set n = s1 (2a 3b ) = 2a + 3b, and observe that the number of pairs (a, b) satisfying this equation can be made arbitrarily large for all n sufficiently large. We now prove a weaker result for r2 , as found in [46]. Theorem 3.6. There exists an N ∈ N such that for all m ≥ N , r2 (m) ≥ 1. Proof. It suffices to show that for m sufficiently large, m = s2 (2a 3b 5c 7d ), for some a, b, c, and d ≥ 0. In general, a b c d +9 + 25 + 49 2 2 2 2 a b a c a d +6 + 10 + 14 1 1 1 1 1 1 b c b d c d + 15 + 21 + 35 1 1 1 1 1 1 1 = (2a + 3b + 5c + 7d)2 − (4a + 9b + 25c + 49d) 2  s2 (2a 3b 5c 7d ) = 4  16  Chapter 3. The Second Elementary Prime Symmetric Function So, given m, we need only find solutions to the equations: 2a + 3b + 5c + 7d = R, 4a + 9b + 25c + 49d = R2 − 2m, with nonnegative integers a, b, c, d, and R ∈ N. These equations are equivalent to: 2a − 10c − 28d = 3R − R2 + 2m, (3.2) 3b + 15c + 35d = R2 − 2R − 2m,  (3.3)  Since a and b must be nonnegative integers, we have the following necessary and sufficient conditions for a solution to (3.2) and (3.3): 1. 2m ≡ R2 + R + d (mod 3), 2. R2 − 3R − 10c − 28d ≤ 2m, 3. 2m ≤ R2 − 2R − 15c − 35d. Note that equation (3.2) is always satisfied modulo 2. Condition 1 results from taking equation (3.3) modulo 3, and conditions 2 and 3 are derived from the fact that a, b ≥ 0. Consider the interval IR (c, d) = [R2 − 3R − 10c − 28d, R2 − 2R − 15c − 35d]. For fixed d, let cR (d) be the least c such that (IR (c, d)) < 15, where (I) denotes the length of an interval I. We use the notation L(I) and R(I) to denote the left and right endpoints of an interval I, respectively. Since R(IR (c, d)) = R(IR (c + 1, d)) + 15, when they exist, we have that cR (d)  IR (c, d) = [R2 − 3R − 10cR (d) − 28d, R2 − 2R − 35d]. c=0  Denote the above interval by IR (d). By definition of cR (d), (IR (cR (d), d)) = R − 5cR (d) − 7d < 15, so −10cR (d) < −2R + 30 + 14d, 17  Chapter 3. The Second Elementary Prime Symmetric Function and cR (d) is the least such c. Consider the interval 2d=0 IR (d). Clearly R( 2d=0 IR (d)) = R2 − 2R − 70. We now wish to find an upper bound for L( 2d=0 IR (d)). From the above inequality, we have that L(IR (d)) = R2 − 3R − 10cR (d) − 28d < R2 − 5R − 14d + 30. Thus 2  IR (d)  L  = max{R2 − 3R − 10cR (d) − 28d|d = 0, 1, 2}  d=0  < max{R2 − 5R − 14d + 30|d = 0, 1, 2} = R2 − 5R + 30. Let JR = [R2 − 5R + 30, R2 − 2R − 70]. Then JR ⊂  2 d=0 IR (d).  Now  L(JR+1 ) ≤ R(JR ), if and only if R2 − 3R + 26 ≤ R2 − 2R − 70, which holds for all R ≥ 96. So if 2m ≥ L(J96 ) = 8766, then there is an R ≥ 96 such that 2m ∈ JR ⊂ 2d=0 IR (d). Choose d ∈ {0, 1, 2} such that condition 1 is satisfied. Since 2m ∈ IR (d), there is a c ≥ 0 such that 2m ∈ IR (c, d). For these values of R, c, and d, conditions 2 and 3 are satisfied. In other words, there exists an n such that m = s2 (n). This completes the proof. Let us try and improve on this result. Theorem 3.7. limm→∞ r2 (m) = ∞ Proof. Let  ∞  pki xi ,  Ak = i=1  where pi denotes the ith prime, xi ≥ 0, and xi = 0 for all but finitely many values of i. If ∞  pxi i ,  n= i=1  then  1 s2 (n) = [A21 − A2 ]. 2 18  Chapter 3. The Second Elementary Prime Symmetric Function Set s2 (n) = m and then set A1 = R, as before. This gives two equations in the unknowns x1 , x2 , . . . , and R, namely: 2x1 + 3x2 + · · · = R 2  2  (3.4) 2  2 x1 + 3 x2 + · · · = R − 2m.  (3.5)  Eliminating x2 from the first and x1 from the second gives 2x1 − 10x3 − · · · − (p2r − 3pr )xR − · · · = −R2 + 3R + 2m 3x2 + 15x3 + · · · + (p2r − 2pr )xR + · · · = R2 − 2R − 2m. If (R, x3 , x4 , . . .), satisfy the conditions (1) 2m ≥ R2 − 3R − 10x3 − 28x4 − · · · − (p2r − 3pr )xr − · · · , (2) 2m ≤ R2 − 2R − 15x3 − 35x4 − · · · − (p2r − 2pr )xr − · · · , (3) 15x3 + 35x4 + · · · + (p2r − 2pr )xr + · · · ≡ R2 + R + m (mod 3), then they uniquely determine a solution (R, x1 , x2 , . . .) to equations (3.4) and (3.5). Observe that given R and m, for any choice of x3 , x5 , x6 , . . ., we can choose d = x4 uniquely from the set {0, 1, 2} so that the congruence (3) holds. We will do this in the following way. Let q1 , q2 , . . . be the odd primes congruent to 2 modulo 3, listed in increasing order. Then for yi ≥ 0, and r ≥ 0, we have that 15y1 + 99y2 + · · · + (qr2 − 2qr )yr ≡ 0 (mod 3). Denote this sum as D = D(y1 , . . . , yr ), and let r  (qi2 − 3qi )yi  C= i=0  Let q be any odd prime congruent to 2 modulo 3, k = q 2 − 3q, and suppose α ≥ 0. Consider intervals of the form  = q 2 − 2q,  IR (α) = [R2 − 3R − 28d − C − αk, R2 − 2R − 35d − D − α ]. We will handle the case when R, m ≡ 0 (mod 3). The other cases are virtually identical. In this case, choosing d = 0, we have that if 2m lies in 19  Chapter 3. The Second Elementary Prime Symmetric Function an interval IR (α) = [R2 − 3R − C − αk, R2 − 2R − D − α ], then m satisfies conditions (1), (2), and (3), with the primes qi , q. We will show that the number of such intervals containing 2m tends to infinity as m does. This implies the theorem. If m ≡ 0 (mod 3) and if 2m lies in the interval IR−1 (0) = [R2 − 5R + 4 − C, R2 − 4R + 3 − D], then since R ≡ 0 (mod 3), condition (3) is satisfied with respect to the primes occurring in the terms of C and D, R − 1 instead of R, and m instead of m. Given R sufficiently large, C, D, k, and q, let αR ≥ 0 be the largest number such that (using notation as in the previous theorem): (i) L(IR (αR )) ≤ R(IR (αR )), and (ii) R(IR (αR + 1)) ≥ L(IR (αR )). These conditions ensure that αR  IR (α) α=0  is an interval, and of longest possible length. Since we always have R(IR (α + 1)) ≤ R(IR (α)), then condition (ii) implies condition (i). Condition (ii) holds if R2 − 2R − D − (αR + 1) ≥ R2 − 3R − C − αR k, which in turn holds if and only if R ≥ (D − C) + αR ( − k) + . Thus we have αR =  R − − (D − C) . −k  Define  αR  JR =  IR (α). α=0  We wish to show that JR ∩ IR−1 (0) is nonempty. That is that L(JR ) ≤ R(IR−1 (0)). This is true if and only if L(IR (αR )) ≤ R(IR−1 (0)), i.e. if and only if R2 − 3R − C − αR k ≤ R2 − 4R + 3 − D. 20  Chapter 3. The Second Elementary Prime Symmetric Function Substituting in the value for αR into the above gives R2 − 3R − C −  R − − (D − C) k ≤ R2 − 4R + 3 − D. −k  This inequality is implied by the inequality R2 − 3R − C + k −  R − − (D − C) −k  k ≤ R2 − 4R + 3 − D,  which is in turn equivalent to the inequality R + (D − C) − 3 + k ≤  R − − (D − C) −k  k.  The coefficient of R on the left hand side of this inequality is 1. On the right hand side it is k/( − k) = q − 3 > 1, and so for R large enough, this inequality holds. Since q, and each qi could be taken to be arbitrary odd primes congruent to 2 (mod 3), we can vary the primes in the terms of C and D. For each such choice, and each choice of q say with q > qr , we obtain distinct solutions for every m such that 2m lies in JR , in this case where R, m ≡ 0 (mod 3). The remaining cases, in which R and m need not be congruent to 0 (mod 3) are handled similarly, by first selecting a different value of d ∈ {0, 1, 2}, and showing that the corresponding interval JR reaches low enough to intersect the interval IR−1 (0). We end this section with a conjecture. Conjecture 3.8. For each k, ∈ N, limn→∞ rk, (n) = ∞. The cases when k = 1 are answered in this thesis. It indeed transpires that r1, (n) → ∞. In fact, we shall do better and derive an asymptotic formula for log r1, (n). Evidence for the conjecture lies in the fact that the average orders of sk, are, as we shall see, only greater in magnitude than that of s1, by a power of log log x, which proves to be relatively insignificant. As n increases there are more and more values of m such that s1, (m) = m, so it seems natural that it be similarly represented for k > 1.  21  Chapter 4  Higher Elementary Prime Symmetric Functions Let n > 1 be an integer. By a family Ek (n, r) of s∗k -special numbers we mean a set Ek (n, r) = {np1 · · · pr |p1 , . . . , pr ∈ P} such that if m ∈ Ek (n, r), then m is s∗k -special. The family E2 (4, 1) of numbers of the form 4p, where p is prime, is one such set, since the elements satisfy s2 (4p) = 4p + 4 > 4p. Ek (n, 0) merely denotes the singleton set of the number n satisfying sk (n) ≥ n, and Ω(n) > k. Introducing the definition Ek (n, r), is productive for classifying all s∗k special numbers for a fixed k. We will see later that with finitely many exceptions, all such numbers are in fact sk -excessive, and that the families Ek+1 (n, r + 1) can be determined completely from the s∗k -special numbers. As well, all but finitely many s∗k -special numbers belong to such families. Theorem 4.1. (1) Let n ∈ N. If n is s∗k -special then pn is sk+1 -excessive for every prime p. (2) If pn is s∗k+1 -special for infinitely many primes p, then n is s∗k -special, and hence by (1), pn is sk+1 -excessive for every prime p. Proof. (1) Suppose n is s∗k -special. Then since Ω(n) > k, we have sk+1 (n) > 0. So sk+1 (pn) = psk (n) + sk+1 (n) ≥ pn + sk+1 (n) > pn. (2) If sk+1 (pn) = psk (n) + sk+1 (n) ≥ pn, for infinitely many primes p, then sk (n) ≥ n − sk+1 (n)/p. Letting p → ∞, we have sk (n) ≥ n. Corollary 4.2. For k ∈ N, there are only finitely many s∗k -perfect numbers. 22  Chapter 4. Higher Elementary Prime Symmetric Functions Proof. By the previous theorem, any infinite family Ek (n, r), r > 0 contains only sk -excessive numbers. We claim that there are only finitely many s∗k special numbers not belonging to any such family. Indeed if there were infinitely many, then by Lemma 2.14, there would be an r > k such that there are infinitely many such s∗k -special numbers n satisfying Ω(n) = r. Write them as follows: (1)  (2)  (3)  (2) (3) S = {p1 · · · p(1) r , p1 · · · pr , p1 · · · pr , . . .} (j)  (j)  (j)  and assume that pi ≤ pi+1 . Clearly we must have that limj→∞ pr = ∞, otherwise, we must have the same number occurring twice in the sequence. (j) If pr−1 contains a bounded subsequence, then there must be an identical ( )  ( )  product p1 · · · pr−1 occurring for infinitely many values of . This gives a ( )  ( )  0 contradiction, since it implies that Ek (p1 0 · · · pr−1 , 1) intersects S, where  (j)  0  is one such value of . Thus limj→∞ pr−1 = ∞. Inductively, by similar (j)  arguments, we conclude that limj→∞ pm = ∞, for m = 1, 2, . . . , r. But then (j) (j) sk (p1 · · · pr ) lim = 0. (j) (j) j→∞ p1 · · · pr This implies that the set S contains sk -defective elements, a contradiction. The preceding results of this section were first proved in [46], by the author. Corollary 4.3. Let k ∈ N. There are only finitely many d > 0 such that the equation sk (n) = n + d has infinitely many solutions. Proof. Suppose sk (n) = n+d has infinitely many solutions n for some d ∈ N. Of these solutions, infinitely many must belong to an infinite family of sk excessive numbers of the form Ek (m, r). It is easily seen that we must have r = 1. Thus there are infinitely many primes p such that sk (m)+psk−1 (m) = pm + d, and so sk (m) = d. But there can only be finitely many such m, as d > 0, so the Corollary holds. Thus the infinite families of s3 -excessive numbers are: E3 (4, 2), E3 (16, 1), E3 (18, 1), E3 (24, 1), E3 (27, 1), E3 (30, 1), E3 (32, 1), E3 (36, 1), E3 (40, 1), E3 (48, 1). That is, those corresponding to the s∗2 -special numbers E2 (4, 1) ∪ {16, 18, 24, 27, 30, 32, 36, 40, 48}. By exhaustive search (as was done with  23  Chapter 4. Higher Elementary Prime Symmetric Functions k = 2), all other s∗3 -special numbers can be found. They constitute the following set: {42p|p = 7, 11, . . . , 41} ∪ {56p|p = 7, 11, . . . , 43} ∪ {64p|p = 2, 3, . . . , 37}∪ {726, 858, 250, 350, 225, 315, 968, 1144, 300, 420, 162, 270, 378, 243, 400, 560, 216, 360, 504, 324, 288, 480, 672, 432, 256, 384, 640, 576, 512, 768}. None of the elements in the above sets are s∗3 -perfect, hence there are no s∗3 -perfect numbers. The diversity of possible increasing s3 -sequences makes it difficult to rule out the existence of s3 -cycles as we did s2 -cycles. This is illustrated in the following example. Example 4.4. If p1 , q1 are odd primes, then s3 (4p1 q1 ) = 4(p1 q1 + p1 + q1 ). It is possible that p1 q1 + p1 + q1 = p2 q2 , where p2 , q2 are again odd primes, and so on. Several such sequences exist the longest one with p1 q1 < 50000, and pi , qi > 3 is: s  s  s  s  s  s  s  s  s  s  s  s  s  s  3 3 184892 = 4 · 17 · 2719 −→ 195836= 4 · 173 · 283 −→ 197660 = 4 · 5 · 9883 3 3 3 −→ 237212 = 4 · 31 · 1913 −→ 244988 = 4 · 73 · 839 −→ 248636 = 4 · 61 · 1019 3 3 3 −→ 252956 = 4 · 11 · 5749 −→ 275996 = 4 · 7 · 9857 −→ 315452 = 4 · 17 · 4639 3 3 3 −→ 334076 = 4 · 47 · 1777 −→ 341372= 4 · 31 · 2753 −→ 352508 = 4 · 13 · 6779 3 3 3 −→ 379676 = 4 · 11 · 8629 −→ 414236= 4 · 29 · 3571 −→ 428636 = 4 · 13 · 8243  s  3 −→ 461660 = 4 · 5 · 41 · 563.  It seems highly unlikely however that an increasing s3 -sequence be infinite. This is part of the following conjecture: Conjecture 4.5. Any increasing sk -sequence is finite. A related conjecture is given by: Conjecture 4.6. For any n ∈ N0 , the sk -sequence of n is ultimately periodic. The evidence for these conjectures lies principally in the fact that for a fixed k, with finitely many exceptions, all s∗k -excessive numbers belong to one of the families Ek (n, r). The union of all such families has asymptotic density 0 in the positive integers. Below is a complete list of all s∗k -perfect numbers for k = 1, 2, 3, and 4, found by exhaustive search. 24  Chapter 4. Higher Elementary Prime Symmetric Functions  Table 2. s∗k -Perfect Numbers k 1 2 3 4  4.1  s∗k -perfect numbers 4 27, 48 none 3125, 9315, 31280  The Hunt for s3 -cycles  As just noted, ruling out the existence of s3 -cycles is not a trivial matter, since there seems to be no apparent maximum length on increasing s3 sequences. Nonetheless, there are a number of things which can be done to get a better picture of what such a sequence can look like. Using Maple, computer searches were done to verify that many numbers do not belong to an s3 -cycle. These include: {42p|p = 7, 11, . . . , 41} ∪ {56p|p = 7, 11, . . . , 43} ∪ {64p|p = 2, 3, . . . , 37}∪ {250, 350, 225, 315, 968, 1144, 300, 420, 162, 270, 378, 243, 400, 560, 216, 360, 504, 324, 288, 480, 672, 432, 256, 384, 640, 576, 512, 768}, that is, all those s∗3 -special numbers not belonging to any of the infinite families. It was also shown for each of the following sets: E3 (16, 1), E3 (18, 1), E3 (24, 1), E3 (27, 1), E3 (30, 1), E3 (32, 1), E3 (36, 1), E3 (40, 1), E3 (48, 1), which are all of the form {np|p is prime}, for all p < 1000, that none of the numbers belong to an s3 -cycle. Finally, the same was shown for the set E3 (4, 2) = {4pq|p, q are prime} in the following ranges: 2 ≤ p ≤ 30, 2 ≤ q ≤ 1000, and 2 ≤ p ≤ 100, 2 ≤ q ≤ 100. Thus an s3 -cycle must have a least element belonging to one of the 10 infinite sets E3 (n, r). We label these sets in the following way: we say m is type 1 if m ∈ E3 (4, 2). Similarly we identify elements in the following sets: •E3 (16, 1) - type 2, •E3 (18, 1) - type 3, •E3 (24, 1) - type 4, •E3 (27, 1) - type 5, •E3 (30, 1) - type 6, •E3 (32, 1) - type 7, •E3 (36, 1) - type 8, •E3 (40, 1) - type 9, 25  Chapter 4. Higher Elementary Prime Symmetric Functions •E3 (48, 1) - type 10. To analyze what increasing sequences begin with elements of types 1 to 10, we will consider the effect of applying s3 to such a number, and consider what type the resulting number may be, if any type. We will use the notation type a −→ type b to indicate the following: it is not impossible for divisibility reasons for to have numbers m and s3 (m) of type a and b respectively. We have noted that type 1 −→ type 1 is possible. Below is a complete list of all the possibilities. Note that we are assuming that the numbers do not lie in the ranges ruled out by the computer searches. •type 1 −→ type 1, type 8, •type 2 −→ type 9, •type 7 −→ type 9, •type 10 −→ type 9. This list was arrived at by simply ruling out possibilities. For example, if m = 18p is type 3, then s3 (18p) = 21p + 18 = 3(7p + 6). Since we may assume p > 1000, p is clearly not 2 or 3, so 3||s3 (18p), and 2 s3 (18p). Thus it is impossible for s3 (18p) to be of any of types 1 through 10. The list arrived at above includes all those cases that could not be ruled out in like manner. Next we will rule out the possibility that numbers of the types that can not be of another type upon application of s3 , are not least elements of any s3 -cycles. Theorem 4.7. If n is type 3, 4, 5, 6, 8, or 9, then n is not the least element of an s3 -cycle. Proof. First suppose n = 18p is type 3. By the computer searches mentioned earlier in this section, we may assume that p > 1000. Applying s3 we get s3 (18p) = 21p + 18 = 3(7p + 6). Let m = 7p + 6. If m is prime, then the s3 -sequence terminates, as it does if m is the product of 2 primes. If m = q1 q2 q3 is the product of 3 primes, then we have (2)  s3 (n) < n if and only if 3(q1 q2 + q1 q3 + q2 q3 ) + q1 q2 q3 < 18  q1 q2 q3 − 6 7  if and only if  108 + 21(q1 q2 + q1 q3 + q2 q3 ) < 11q1 q2 q3 .  (4.1)  Since p > 1000, we have that q1 q2 q3 > 7006. Also, clearly qi = 2, 3, or 7. Under these constraints, the inequality (4.1) holds, and so n cannot be the least element of an s3 -cycle. 26  Chapter 4. Higher Elementary Prime Symmetric Functions Hence we may assume m = q1 · · · qr , where r ≥ 4. We may again assume that m > 7006, and qi = 2, 3, or 7. In this case, (2)  s3 (n) < n if and only if 108 + 21(q1 q2 + · · · + qr−1 qr ) + 7(q1 q2 q3 + · · · + qr−2 qr−1 qr ) < 18q1 · · · qr . Upon dividing each side by m, and using the facts that m > 7006, and qi ≥ 5, we have that the latter inequality is implied by the inequality 108 21 r 7 r + + r−3 7006 5r−2 2 5 3  < 18.  This indeed holds for r ≥ 4. Thus numbers of type 3 cannot be least elements of s3 -cycles. The remaining cases, types 4, 5, 6, 8, and 9 are handled in virtually identical fashion, but are omitted to avoid tediousness. Remark 4.8. A consequence of the above proof, is that all but finitely many maximal increasing s3 -sequences of length greater than 2 have as least element a type 1 number, and have as second last element either a type 1 or a type 8 number, with all intermediate numbers type 1. That is, the sequence must be of the form type 1 → type 1 → · · · → type 1 → m, or of the form type 1 → type 1 → · · · → type 1 → type 8 → m, where m satisfies s3 (m) < m. We have accumulated enough information to prove the non-existence of the simplest case of s3 -cycles. (2)  Theorem 4.9. There are no s3 -cycles of length 2. That is, if s3 (n) = n, then s3 (n) = n. Proof. Any such s3 -cycle must have a least element n of type 1, 2, 7, or 10. First assume that n = 4pq is type 1. Because of the computer searches, we may assume that the pair (p, q) lies outside of the ranges 2 ≤ p ≤ 30, 2 ≤ q ≤ 1008, and 2 ≤ p ≤ 100, 2 ≤ q ≤ 100, and that p ≤ q. Let m = pq + p + q. In the allowable range, the minimum value for m occurs when p = 2, and q = 1009, which gives m = 3029. Note that 2 m. 27  Chapter 4. Higher Elementary Prime Symmetric Functions (2)  (2)  We have s3 (4pq) = s3 (4m) = 4s1 (m) + 4s2 (m) + s3 (m). If s3 (n) = n, then 4s1 (m) + 4s2 (m) + s3 (m) = 4pq. (4.2) We will take cases depending on Ω(m). In the following, qi always indicates a prime dividing m. If m = q1 is prime, then we are done since then s2 (4m) = 4m. If m = q1 q2 , then (4.2) implies q1 + q2 + q1 q2 = pq. Substituting q1 q2 = pq + p + q, and canceling gives q1 + q2 + p + q = 0, an impossibility. If m = q1 q2 q3 , then (4.2) implies that 4s1 (m) + 4s2 (m) + m = 4pq. This is impossible, since 2 m. In case m = q1 · · · q4 , we will show that (4.2) should be replaced with a strict inequality. Dividing (4.2) through by m gives 4  1 1 + ··· + q1 q2 q3 q2 q3 q4 4pq . = pq + p + q  1 1 + ··· + q1 q2 q3 q4  +4  +  1 1 + ··· + q1 q4  We can minimize the right hand side of this equation. In the range in question, 4pq/(pq + p + q) is minimized when p = 2, q = 1009, and this gives us that 4pq/(pq + p + q) > 2.6649. It is an easy check that if qi ≥ 3, and m = q1 · · · q4 ≥ 3029, then we always have 4  1 1 + ··· + q1 q2 q3 q2 q3 q4  1 1 + ··· + + q1 q2 q3 q4 4pq < 2.6649 < . pq + p + q  +4  1 1 + ··· + q1 q4  A similar approach can be used when Ω(m) = 5. If r ≥ 6, then 4  1 1 + ··· + q1 q2 q3 qr−2 qr−1 qr  1 1 1 1 + ··· + + + ··· + q1 q2 qr−1 qr q1 qr r 4 r 4 r 1 < + + r−1 r−2 r−3 1 3 2 3 3 3 4pq , < 2.6649 < pq + p + q  +4  28  Chapter 4. Higher Elementary Prime Symmetric Functions and we are done the type 1 case. Next suppose that the least element n = 16p is type 2. We may assume (2) that p ≥ 1009. Now s3 (16p) = s3 (8(3p + 4)). Let m = 3p + 4, so 16p = (2) 16(m − 4)/3. Then 2, 3 m, and m ≥ 3031. So s3 (16p) = 8 + 12s1 (m) + (2) 6s2 (m) + s3 (m). The supposition that s3 (n) = n is equivalent to 8 + 12s1 (m) + 6s2 (m) + s3 (m) = 16  m−4 3  ,  which is equivalent to 88 + 36s1 (m) + 18s2 (m) + 3s3 (m) = 16m,  (4.3)  We will consider cases depending on the value of Ω(m). In the following, each qi is assumed to be prime. If m = q1 is prime, then (4.3) becomes 88 + 36q1 = 16q1 , which is impossible. If m = q1 q2 , then (4.3) is also impossible for m in the allowable range. If m = q1 q2 q3 , then (4.3) is equivalent to 88 + 36(q1 + q2 + q3 ) + 18(q1 q2 + q1 q3 + q2 q3 ) = 13q1 q2 q3 . Dividing through by m, and using the facts that m ≥ 3031, and qi ≥ 5, we have the inequality 88 + 36 3031  1 1 1 + + q1 q2 q1 q3 q2 q3  + 18  1 1 1 + + q1 q2 q3  < 13.  This contradicts (4.3). A similar contradiction occurs when Ω(m) > 3. The proofs of the cases when n is type 7 or 10 follow the same lines as the proof for case 2, and are omitted.  29  Chapter 5  The Power Prime Symmetric Divisor Functions We now begin our study of the power prime symmetric functions. Recall we were able to classify when a prime power pα was s∗k -perfect for some k. We now present an analogous result pertaining to ek -perfection. Theorem 5.1. Let n = pα be a prime power. Then there exists a k ∈ N such that n is ek -perfect if and only if k = pβ − β and α = pβ for some β ≥ 0. Proof. ek (pα ) = pα if and only if αpk = pα . Hence we may write α = pβ for β some β ≥ 0. This implies that pβ+k = pp , and so k = pβ − β. β Conversely, it is trivial to see that pp is always epβ −β -perfect. Remark 5.2. The set {pβ −β|p is prime and β ≥ 0} has asymptotic density 0 in N. So, for “most” values of k, there is no prime power pα that is ek perfect. With the functions ek , we can also characterize which numbers are ek perfect for some k for products of two prime powers. Theorem 5.3. Let n = pα q β , where p and q are primes, and α, β > 0. Then n is not ek -perfect for any k. Proof. Without loss of generality, p < q. Furthermore, since e1 = s1 , and the statement has been proved for s1 , we may assume that k ≥ 2. If ek (pα q β ) = pα q β , then αpk + βq k = pα q β . (5.1) First assume that α, β ≥ k. Then since βq k = pk (pα−k q β − α), we have that pk divides β. Similarly q k divides α. Write β = bpk , and α = aq k . Clearly a, b > 0, and equation (5.1) becomes k  k  (a + b)pk q k = paq q bp . 30  Chapter 5. The Power Prime Symmetric Divisor Functions We will show that we instead have a strict inequality k  k  (a + b)pk q k < paq q bp .  (5.2)  Since a, b > 0, p ≥ 2, and q ≥ 3, it is easily seen that bpk−1 ≤ bpk − k, and aq k−1 ≤ aq k − k, and hence the inequality (5.2) is implied by a + b < paq  k−1  q bp  k−1  .  This is in turn implied by a + b < ab(pq)k−1 Now pq ≥ 6, and k ≥ 2, so the latter inequality holds if a + b < 6ab. This is indeed true for a, b > 0. The second case we consider is when α, β < k. Then in similar fashion to the previous case, we can write β = bpα , and α = aq β , where a, b > 0. This α however gives an immediate contradiction, since then α = aq β = aq bp > α. Next suppose that α < k, and β ≥ k. Then for some a > 0, we have that α = aq k > aq α > α. This is a contradiction. A similar contradiction results in the remaining case, thus, the theorem is proved. We can relate the functions sk and ek using the Newton-Girard formulas (see [44]). These formulas imply that k k  (−1)i+k ei sk−i = 0.  (−1) ksk + i=1  The function ek can be expressed strictly in terms of the elementary prime symmetric functions s1 , . . . , sk as a determinant (see also [45]):  ek = (−1)k  ··· ··· ··· ··· .. .  0 0 0 0 .. .  ksk sk−1 sk−2 sk−3 · · ·  s1  s1 2s2 3s3 4s4 .. .  1 s1 s2 s3 .. .  0 1 s1 s2 .. .  0 0 1 s1 .. .  31  Chapter 5. The Power Prime Symmetric Divisor Functions Similarly, we can express sk in terms of ek as follows: 0 0 0 0 .. .  ek−4 k−1 ek−3 k  ··· ···  e1 k  1  e2 2 e3 3 e4 4  e1 2 e2 3 e3 4  e1 3 e2 4  e1 4  ek−1 k−1 ek k  ek−2 k−1 ek−1 k  ek−3 k−1 ek−2 k  sk =  5.1  .. .  ··· ··· ··· ··· .. .  e1  .. .  0 1  .. .  0 0 1  .. .  1  The Average Order of ek  Analysis in Sections 5.1 and 5.2 and Chapter 6 are taken from the paper [50] of the author, previously published in Integers: The Electronic Journal of Combinatorial Number Theory. In this section we shall prove the following asymptotic formula for the average order of ek (n): ek (n) = n≤x  ζ(k + 1)xk+1 +O (k + 1) log x  xk+1 log log x log2 x  .  The asymptotic alone (without the error term included) has been proved by Kerawala [24] and LeVan [27] each using different techniques. The case when k = 1 was treated by Alladi and Erd˝os [1]. We shall make precise LeVan’s sketch of the proof. First we require the following Lemma: Lemma 5.4. For x ≥ 2, and k, ∈ N0 we have xk+1 pk = log p (k + 1) log p≤x  +1  x  +O  xk+1 log +2 x  .  Proof. The sum may be expressed as a Riemann-Stieltjes integral: pk = log p p≤x  x 3/2  tk dπ(t). log t  Integrating by parts we have: x 3/2  tk xk π(x) dπ(t) = − log t log x  x 3/2  ktk−1 tk−1 − log t log +1 t  π(t) dt.  32  Chapter 5. The Power Prime Symmetric Divisor Functions By the prime number theorem, this gives x 3/2  tk xk dπ(t) = log t log x  x +O log x  x  ktk−1 tk−1 − log t log +1 t  − =  3/2 xk+1  log  +1  x x  3/2  =  x  tk dt + O log +1 t  t log2 t  dt  tk dt log +2 t  3/2  xk+1 xk+1 − k log +1 x (k + 1) log +O  t +O log t  xk+1 log +2 x  +O  −k =  x log2 x  +1  x  + O(1) +  +1 k+1  x 3/2  tk dt log +2 t  xk+1 log +2 x  xk+1 (k + 1) log  +1  x  +O  xk+1 log +2 x  ,  and the proof is complete. Theorem 5.5. For k ∈ N, ek (n) = n≤x  ζ(k + 1)xk+1 +O (k + 1) log x  xk+1 log log x log2 x  .  Proof. We have ∞  pk  ek (n) = p≤x i=1  n≤x  pk  = p≤x  x pi  x + p  ∞  pk i=2 p≤x1/i  x . pi  (5.3)  As we shall see, the first term contributes the greater portion to the sum:  33  Chapter 5. The Power Prime Symmetric Divisor Functions  pk p≤x  x = p  ipk i≤x/2  x <p≤ xi i+1  pk  = i≤x/2 p≤x/i  = i≤x/2  (x/i)k+1 +O (k + 1) log (x/i)  Let  (x/i)k+1 log2 (x/i)  1  Σ1 = 2  i≤log x  ik+1 log (x/i)  and 2  log x<i≤x/2  (5.4)  ,  1  Σ2 =  .  ik+1 log (x/i)  ,  so that 1 i≤x/2  ik+1 log (x/i)  = Σ1 + Σ2 .  We have that Σ1 ≥  1 log x  1 i≤log2 x  ik+1   =  1  ζ(k + 1) − log x   1   i>log2 x  ik+1  1 1 ζ(k + 1) + O log x log2k x ζ(k + 1) 1 = +O . 2k+1 log x log x =  34  Chapter 5. The Power Prime Symmetric Divisor Functions On the other hand, Σ1 ≤ i≤log2 x  =  1 log x  1 ik+1 (log x − 2 log log x) log log x log x  1+O  1 i≤log2 x  log log x 1 1+O log x log x ζ(k + 1) log log x = +O log x log2 x  ik+1 1 log2k x  ζ(k + 1) + O  =  .  Combining these results we have that ζ(k + 1) +O log x  log log x log2 x The sum Σ2 is negligible by comparison: Σ1 =  .  (5.5)  1  Σ2 = log2 x<i≤x/2  ik+1 log (x/i)  1 i>log2 x ∞ 2  log x  ik+1 1 dt tk+1  1 . log2k x  (5.6)  Now we need to bound the error term in (5.4): 1 =O 2 k+1 i log (x/i) i≤x/2  x/2  dt t2 log2 x/t  1 √  =O 1  x  dt + 2 t log2 x/t √  =O =O  4 log2 x 1 log2 x  1  x  dt + t2  x/2 √  x  x/2 √  x  dt t2 log2 x/t  dt t2 (5.7)  35  Chapter 5. The Power Prime Symmetric Divisor Functions Hence by (5.5), (5.6), and (5.7), we have that pk p≤x  x ζ(k + 1)xk+1 = +O p (k + 1) log x  xk+1 log log x log2 x  .  To conclude the proof, we need to bound the second term in (5.3). ∞  pk i=2 p≤x1/i  x pi  ∞  ≤x i=2 p≤x1/i  ≤x √ p≤ x  pk pi  pk−1 p−1 pk−2  ≤ 2x √  p≤ x  =   O(x log log x), if k = 1; k+1  O  x 2 log x  , if k > 1.  Note that for the k = 1 case, x log log x = O  x2 log log x log2 x  ,  and for the k > 1 case, k+1  x 2 =O log x  xk+1 log log x log2 x  .  Hence, these error terms may be absorbed to yield the theorem. The case when k = 0, i.e. the average order of Ω(n), will be covered in the next section.  5.2  A Statistical Look at ek  In the last section we found the average order of ek (n). In this section we will take a statistical look at its range of values. First, we need some notation and context for the functions r1,k . We have looked at the functions rk , which counted the number of solutions to the equation sk (m) = n for a fixed n. The analogue for the functions ek is none other than the function which counts the number of partitions into k-th powers of primes. 36  Chapter 5. The Power Prime Symmetric Divisor Functions Definition 5.6. Let A ⊆ N. The number of partitions of n into parts taken from A is denoted by pA (n). Note that pA (0) = 1, corresponding to the empty partition. Writing the set of k-th powers of primes as P(k) , we have (−1)  r1,k (n) = pP(k) (n) = |ek  {n}|  (5.8)  It is much easier to work with the functions pP(k) (n), than with the analogues rk (n) with the elementary prime symmetric functions. For instance, it is a trivial matter to see that pP(k) (n) → ∞ with n: Theorem 5.7. For k ∈ N, we have that limn→∞ pP(k) (n) = ∞. Proof. Let ∈ {0, 1, . . . , 2k − 1}, and consider the sequence {n2k + }∞ n=1 . Let q be any prime congruent to 1 modulo 2k . Numbers of the form 2n q , satisfy ek (2n q ) = n2k + q k , and q k ≡ (mod 2k ). Since there are infinitely many such q, we have that limn→∞ pP(k) (n2k + ) = ∞. Since this holds for any ∈ {0, 1, . . . , 2k − 1}, we have the stated result. From the theory of partitions (see for instance [2]), we can construct generating functions useful in calculating pP(k) (n). Indeed, we have ∞  1 = pP(k) (n)xn . 1 − xpk n=0  p  The proof of this fact is by analogy with [2] pp.308-310. Generating functions provide easy expressions for the j-th difference functions for pP(k) , which we (j) write as pP(k) : ∞  ∞ (j)  n=0  pP(k) (n)xn = (1 − x)j  pP(k) (n)xn = (1 − x)j p  n=0  1 . 1 − xpk  (5.9)  In particular we have that n (−1)  pP(k) (n) =  pP(k) (m). m=0  The following trivial identity turns out to be rather useful in deriving some statistical properties of the exponent prime symmetric functions. We denote by P (n) the largest prime factor dividing n. Then: P (n)k ≤ ek (n) ≤ P (n)k Ω(n).  (5.10) 37  Chapter 5. The Power Prime Symmetric Divisor Functions Definition 5.8. Let bk (x, y) = #{n ≤ x : ek (n) ≤ y},  (5.11)  Ψ(x, y) = #{n ≤ x : P (n) ≤ y},  (5.12)  Erd˝os and Pomerance [16] show that for every > 0 there is a δ > 0 such that for x sufficiently large there is at least (1 − )x choices for n ≤ x such that P (n) < e1 (n) < (1 + x−δ )P (n). We will use our comparison 5.10 to relate the quantities bk (x, y) and Ψ(x, y), but first we require some background material from analytic number theory. The proof of the first lemma that follows can be found in [33] pp. 278-279. Lemma 5.9. There is a constant b1 such that  p≤x  1 = log log x + b1 + O p  1 log x  .  Lemma 5.10. There is a constant b2 such that Ω(n) = x log log x + b2 x + O n≤x  x log x  .  Proof. By the additivity of Ω(n), and de Polignac’s formula, ∞  Ω(n) = n≤x  p≤x j=1 ∞   1 +O p−1  log x  log p  p≤x j=1  p≤x  =x p≤x  1 pj  ∞  x pj   =x  =x  x pj − p≤x j=1  p≤x  1 1 + p p(p − 1)  +O  x log x  .  The last step followed from Lemma 5.4. Hence by Lemma 5.9, Ω(n) = x log log x + b1 + O n≤x  = x log log x + b2 x + O  1 log x x log x  +x p∈P  1 +O p(p − 1)  x log x  ,  38  Chapter 5. The Power Prime Symmetric Divisor Functions where b2 = b1 + p∈P  1 . p(p − 1)  (5.13)  A similar result holds for ω(n), and can be found in [33] p. 283. We also need to compute the average order for Ω(n)2 . Doing so will constitute the content of the next lemma. Lemma 5.11. The average order of Ω(n)2 is given by Ω(n)2 = x(log log x)2 + O(x log log x).  (5.14)  n≤x  Proof. 2   Ω(n)2 = n≤x  1   n≤x  = n≤x  p |n        1  p |n   1 q m |n  =  1 p ≤x q m ≤x  n≤x p ,q m |n  =  1+ p≤x ,m≤log x/ log p  n≤x pmax{ ,m} |n  p ,q m ≤x p=q  x p qm  = Σ1 + Σ2 , where the obvious designations are made for Σ1 , and Σ2 . We shall first show that the triple sum Σ1 is O(x log log x). Indeed, letting Rp = log x/ log p,  39  Chapter 5. The Power Prime Symmetric Divisor Functions we have x  Σ1 =  pmax{ ,m}  p≤x ,m≤Rp   1  =x p≤x ,m≤Rp  pmax{ ,m}  +O p≤x  log x log p    2       2k − 1 1  + O log2 x k p log2 p p≤x k≤Rp p≤x   k x , using Lemma 5.4 = O x +O log x pk p≤x k≤Rp   R 1 1 − 1/p R x +O = O x − R +1 2 p (1 − 1/p) log x p (1 − 1/p) p≤x   p 1 log x x +O = O x 1− − 2 (p − 1) x (p − 1)x log p log x p≤x   x 1 = O x +O p log x =x  p≤x  = O(x log log x). We now turn our attention to Σ2 :  Σ2 = x p ,q m ≤x p=q  =x p,q≤x p=q       1 +O  m pq   1   1 +x pq  p ,q m ≤x p=q  p ,q m ≤x p=q max{ ,m}≥2  1 +O p qm  x log x  .  40  Chapter 5. The Power Prime Symmetric Divisor Functions But  p,q≤x p=q  1 = pq  q≤x  = q≤x  1 q  p≤x p=q  1 p  1 (log log x + O(1)) q  = (log log x)2 + O(log log x), and   p  ,q m ≤x   1 = O  m pq  p ≤x ≥2  p=q max{ ,m}≥2   1  p   q≤x     1 + O(1)   = O(log log x). q  (5.15)  Hence Σ2 = x(log log x)2 + O(x log log x),  (5.16)  Ω(n)2 = x(log log x)2 + O(x log log x)  (5.17)  and therefore  n≤x  as claimed. The function Ω(n) is “close” to log log n for almost all values of n. This statement is made more precise by the following theorem and its subsequent remark, for which we have Tur´an [43] to thank: Theorem 5.12. The number of n ≤ x such that |Ω(n) − log log x| > (log log x)3/4 is O  √  x log log x  .  Proof. Denote by S the set {n ∈ N : |Ω(n) − log log x| > (log log x)3/4 }, and  41  Chapter 5. The Power Prime Symmetric Divisor Functions let S(x) = #{n ≤ x : n ∈ S}, be the counting function of S. Then S(x) =  1 n≤x, n∈S  ≤  (Ω(n) − log log x)2 (log log x)3/2 n≤x  (log log x)−3/2    Ω(n) + x(log log x)2   Ω(n)2 − 2 log log x n≤x  n≤x  (log log x)−3/2 (x(log log x)2 + O(x log log x) − 2 log log x(x log log x + O(x)) + x(log log x)2 ) =O  √  x log log x  .  Remark 5.13. It is also true that #{n ≤ x : |Ω(n) − log log n| > (log log n)3/4 } = O  √  x log log x  .  The proof of this fact is similar to that of theorem 5.12. We are now equipped to relate the quantities bk (x, y), and Ψ(x, y). Theorem 5.14. There is an absolute positive constant c1 such that the inequalities Ψ x,  y log log x + (log log x)3/4  1/k  −√  c1 x ≤ bk (x, y) ≤ Ψ(x, y 1/k ) log log x (5.18)  hold. Proof. By equation (5.10), we have that #{n ≤ x : P (n)k Ω(n) ≤ y} ≤ bk (x, y) ≤ #{n ≤ x : P (n)k ≤ y}. This implies the second inequality. By remark 5.13, there is an absolute positive constant c1 such that #{n ≤ x : |Ω(n) − log log n| ≤ (log log n)3/4 } ≥ x 1 − √  c1 log log x  . 42  Chapter 5. The Power Prime Symmetric Divisor Functions Given this, we have the following chain of inequalities: #{n ≤ x : P (n)k Ω(n) ≤ y} ≥#{n ≤ x : P (n)k Ω(n) ≤ y, and Ω(n) ≤ log log n + (log log n)3/4 } ≥#[{n ≤ x : P (n)k (log log n + (log log n)3/4 ) ≤ y} ∩ {n ≤ x : Ω(n) ≤ log log n + (log log n)3/4 }] ≥#{n ≤ x : P (n)k (log log x + (log log x)3/4 ) ≤ y} + #{n ≤ x : |Ω(n) − log log n| ≤ (log log n)3/4 } − x ≥Ψ x,  y log log x + (log log x)3/4  1/k  −√  c1 x , log log x  and the theorem is proved. There is an interesting connection between bk (x, y), and pP(k) (n). For x sufficiently large relative to n, bk (x, n) − bk (x, n − 1) = pP(k) (n). A telescoping sum yields n (−1)  bk (x, n) = m=0  pP(k) (n) = pP(k) (n).  Unfortunately, for x in this range, the best estimates for Ψ(x, n) give error terms that are too large to be useful. However, we will see that for x in ranges such as y 1/α , where 0 < α < 1, Theorem 5.14 is useful in describing the behaviour of bk (x, y). The “Dickman function” ρ(u) is defined to be the unique continuous solution to the differential-difference equation uρ (u) = −ρ(u − 1) (u > 1), satisfying the initial condition ρ(u) = 1 (0 ≤ u ≤ 1). The Dickman function is nonnegative for u > 0, and decreasing for u > 1. This definition and description is taken from [22], which is a comprehensive survey of work on the function Ψ(x, y). 43  Chapter 5. The Power Prime Symmetric Divisor Functions It is also true that ρ(u) is convex on (1, ∞). By the functional equation, it is apparent that lim ρ (u) = −1. u→1+  It follows that ρ(a + b) ≥ ρ(a) − b, for a ≥ 1, b ≥ 0.  (5.19)  De Bruijin [9] proved that Ψ(x, y) = xρ(u) 1 + O  log (u + 1) log y  (5.20)  holds uniformly for u = log x/ log y in the range y ≥ 2, 1 ≤ u ≤ (log y)3/5− .  (5.21)  This has since been improved by Hildebrand [21] to the range y ≥ 2, 1 ≤ u ≤ exp (log y)3/5− .  (5.22)  For the next theorem, we are interested in the range y = xα/k , and hence u = k/α. Theorem 5.15. Let 0 < α < 1, and let k ∈ N be fixed constants. Then k α  bk (x, xα ) ∼ Ψ(x, xα/k ) ∼ ρ  x.  In fact, we have bk (x, xα ) = ρ  k α  x+O  √  x log log x  .  Proof. Note that for x ≥ 2k/α , we are within the range (5.22). Consequently (5.20) applies: Ψ(x, xα/k ) = xρ  k α  1+O  1 log x  .  Furthermore, the second inequality of Theorem 5.14 gives us: bk (x, xα ) ≤ Ψ(x, xα/k ). 44  Chapter 5. The Power Prime Symmetric Divisor Functions Similarly, the first inequality from theorem 5.14 yields: Ψ x,  1/k  xα 2 log log x  −√  c1 x ≤ bk (x, xα ), log log x  since Ψ(x, y) is increasing in y. For x sufficiently large, (5.20) gives Ψ x,  xα 2 log log x  1/k  = xρ  log x (α/k) log x − (1/k) log(2 log log x)  × 1+O  log (u + 1) log y  ,  where in this instance, y=  xα 2 log log x  1/k  and log x log x = log y (α/k) log x − (1/k) log(2 log log x) k 1 = . α 1 − (1/α) log(2 log log x)/ log x  u=  The identity 1 < 1 + 2a 1−a holds for 0 < a < 1/2. So if x is chosen sufficiently large such that 0< then u<  log(2 log log x) 1 < , α log x 2  k 2k log(2 log log x) + . α α2 log x  45  Chapter 5. The Power Prime Symmetric Divisor Functions Hence, since ρ(u) decreases on (1, ∞), we have Ψ x,  xα 2 log log x  1/k  ≥ xρ = xρ ≥ xρ = xρ  k 2k log(2 log log x) + α α2 log x  1+O  1 log x  x k 2k log(2 log log x) +O + 2 α α log x log x k 2kx log(2 log log x) x − +O α α2 log x log x k x log log log x +O , α log x  using equation (5.19). Combining this information with theorem 5.14 we obtain the following inequalities: xρ  k α  +O  √  x log log x  ≤ Ψ x,  xα 2 log log x  1/k  ≤ bk (x, xα ) ≤ Ψ(x, xα/k ) = xρ  k α  +O  x log x  ,  which proves the theorem.  46  Chapter 6  The Average Order of sk, In the last chapter, we looked at the power prime symmetric functions, and were able to compute asymptotic expressions for their average orders. This computation proves to be rather more straightforward than the analogous computation for sk , primarily due to the fact that ek is an additive arithmetic function. We will now, however, do even better and compute the average order of sk, . A useful tool in the following computation will be Lemma 5.4. First we need to get a handle on the sum n≤x sk, (n). Throughout this section, k will be a positive integer, and pi shall always denote a prime, not necessarily the i-th prime. Our main result is Theorem 6.3, which states that  sk, (n) = n≤x  ζ( + 1)x +1 (log log x)k−1 +O ( + 1)(k − 1)! log x  x  +1 (log log x)k−2  log x  ,  for k ≥ 2, and ≥ 1. The k = 1 case was handled in the last chapter. For it, the error term is slightly better. Theorem 6.1. The average order of sk, (n) has the following expression: k  (pi11 · · · pirr ) ×  sk, (n) = n≤x  r=1 p1 <...<pr i1 +···+ir =k i1 ,...,ir >0    ∞   j1 ,...,jr =1  j1 − 1 jr − 1 ··· i1 − 1 ir − 1   x pj11  · · · pjrr  .  Proof. The terms in the sum n≤x sk, (n) are products of k -th powers of primes, not necessarily distinct. In other words, an arbitrary term is of the form (pi11 · · · pirr ) , where r ≤ k, p1 < . . . < pr , i1 , . . . , ir > 0, and i1 + · · · + ir = k. Fix (pi11 · · · pirr ) . We shall count the number of times this expression occurs in the sum. 47  Chapter 6. The Average Order of sk, By the inclusion-exclusion principle, the number of n ≤ x such that is  pj11 , . . . , pjrr ||n x pj11 −  · · · pjrr x pj11 +1 pj22  · · · pjrr  + · · · + (−1)r  x  +  pj11 pj22 +1 · · · pjrr  x  x  + ··· +  pj11 pj22  · · · pjrr +1  ,  pj11 +1 · · · pjrr +1  which we write as β(j1 , . . . , jr ). Each such n contributes ji11 · · · jirr copies of (pi11 · · · pirr ) to the sum n≤x sk, (n). Thus (pi11 · · · pirr ) occurs ∞  j1 jr ··· β(j1 , . . . , jr ) i1 ir  j1 ,...,jr =1  times. We make the following claim: ∞ j1 ,...,jr =1  j1 jr ··· β(j1 , . . . , jr ) i1 ir ∞  j1 − 1 jr − 1 ··· i1 − 1 ir − 1  = j1 ,...,jr =1  To prove (6.1), first note that j1 jr ··· i1 ir  −  j1 − 1 i1  + · · · + (−1)r  x j p11 ···pjrr  x pj11  · · · pjrr  .  (6.1)  occurs  j2 jr j1 j2 jr − 1 ··· + ··· + ··· i2 ir i1 i2 ir j1 − 1 j2 − 1 jr − 1 ··· i1 i2 ir  times in the left hand side. But an induction on r, with the identity j i  −  j−1 i  =  j−1 , i−1  (6.2)  being the r = 1 case gives us that  48  Chapter 6. The Average Order of sk,  jr j1 ··· ir i1 + · · · + (−1)r  jr − 1 j2 j1 jr j1 − 1 j2 ··· + ··· + ··· i2 ir i1 ir i2 i1 j1 − 1 j2 − 1 jr − 1 j1 − 1 jr − 1 ··· = ··· . i1 i2 ir i1 − 1 ir − 1 (6.3)  −  Indeed, suppose that (6.3) holds for r − 1. Denote the left-hand side of (6.3) by Cr . We need to show that Cr =  j1 − 1 jr − 1 ··· . i1 − 1 ir − 1  But factoring, the identity (6.2) and the induction hypothesis give us that jr jr − 1 Cr−1 − Cr−1 ir ir jr − 1 = Cr−1 ir − 1 j1 − 1 jr−1 − 1 jr − 1 = ··· . i1 − 1 ir−1 − 1 ir − 1  Cr =  Thus the claim (6.1) is proved. The Theorem follows by summing over all values of r from 1 to k, all possible r-tuples of primes, and for each such r-tuple, all r-tuples (i1 , . . . , ir ) satisfying ij > 0 for j = 1, . . . , r, and i1 + · · · + ir = k. We will first investigate the part of the sum in Theorem 6.1 corresponding to r = k, and hence i1 = . . . = ik = 1. To do so, we require some generalizations of the prime number theorem. These are taken from Nathanson [33], pp.313-319, however we also include precise error terms. Let πk (x) = #{n ≤ x : Ω(n) = ω(n) = k}; and πk∗ (x) = #{n ≤ x : Ω(n) = k}. That is, πk (x) counts the number of n ≤ x such that are products of exactly k distinct prime factors, and πk∗ (x) counts the number of n ≤ x which have k prime factors with repetition. Note that π1 (x) = π1∗ (x) = π(x). For k = 1, the prime number theorem gives us π(x) =  x +O log x  x log2 x  .  (6.4) 49  Chapter 6. The Average Order of sk, For k ≥ 2, we also have that x(log log x)k−1 +O (k − 1)! log x  πk (x) =  x(log log x)k−2 log x  ,  (6.5)  and 0 ≤ πk∗ (x) − πk (x)  x(log log x)k−2 . log x  (6.6)  We shall use the first result to prove a Lemma: Lemma 6.2. Let u ≥ 0, and k ≥ 2. Then xu+1 (log log x)k−1 +O (u + 1)(k − 1)! log x  nu = n≤x ω(n)=Ω(n)=k  xu+1 (log log x)k−2 log x  .  Proof. Writing the sum as a Riemmann-Stieltjes integral, we have: x  nu =  tu dπk (t) 2k−  n≤x ω(n)=Ω(n)=k  x  =xu πk (x) − u =  tu−1 πk (t) dt  2k u+1 x (log log x)k−1  xu+1 (log log x)k−2 (k − 1)! log x log x x u x u k−1 t (log log t) t (log log t)k−2 −u dt + O dt log t 2k (k − 1)! log t 2k +O  It is easy to see via a straightforward application of integration by parts that x u t (log log t)k−1 2k  log t  dt =  xu+1 (log log x)k−1 +O (u + 1) log x  xu+1 (log log x)k−1 log2 x  .  Combining this information, we have nu = n≤x ω(n)=Ω(n)=k  xu+1 (log log x)k−1 +O (u + 1)(k − 1)! log x  xu+1 (log log x)k−2 log x  ,  and the Lemma is proved. 50  Chapter 6. The Average Order of sk, The case when k = 1 was handled in an earlier chapter. Hence for the remainder, we shall assume that k ≥ 2. We will also assume that ≥ 1. For r = k, we have the following: ∞  (p1 · · · pk ) p1 <...<pk  x · · · pjkk  j1 ,...,jk =1  pj11  +  (p1 · · · pk )  p1 <...<pk ∞  p1 <...<pk  x p1 · · · pk  (p1 · · · pk )  =  x pj11  j1 ,...,jk =1 j1 ···jk >1  · · · pjkk  .  (6.7)  We further focus by looking at the first term on the right-hand side of (6.7), that is, the term corresponding to j1 = . . . = jk = 1. Making use of Lemma 6.2, we have:  (p1 · · · pk ) p1 <...<pk  x p 1 · · · pk  m(p1 · · · pk )  = m≤x/2k  p1 <...<pk x x <p1 ···pk ≤ m m+1  m≤x/2k  p1 <...<pk p1 ···pk ≤x/m  (p1 · · · pk )  =  =  (log log (x/m))k−1 x +1 ( + 1)(k − 1)! m +1 log (x/m) m≤x/2k   k−2 (log log (x/m)) . + O x +1 m +1 log (x/m) k m≤x/2  (6.8) Now  m≤x/2k  (log log (x/m))k−1 = m +1 log (x/m)  m≤log2 x  (log log (x/m))k−1 m +1 log (x/m)  + 2  log x<m≤x/2k  (log log (x/m))k−1 . m +1 log (x/m)  (6.9)  For m ∈ [1, log2 x],  51  Chapter 6. The Average Order of sk,  (log log (x/m))k−1 (log log x)k−1 ≤ +1 +1 m log (x/m) m (log x − 2 log log x) log log x (log log x)k−1 1+O = +1 log x m log x  ,  which implies that  m≤log2 x  (log log (x/m))k−1 (log log x)k−1 ≤ log x m +1 log (x/m)  1+O  (log log x)k−1 log x  1+O  log log x log x  m≤log2 x  log log x log x 1 × ζ( + 1) 1 + O log2 x (log log x)k ζ( + 1)(log log x)k−1 +O = log x log2 x  =  1 m +1  . (6.10)  On the other hand, for m ∈ [1, log2 x] we have (log log (x/m))k−1 (log (log x − 2 log log x))k−1 ≥ m +1 log (x/m) m +1 log x log log x + log 1 − =  =  m  +1 log x  log log x + O  log log x log x  m  k−1  k−1  +1 log x  (log log x)k−1 + O =  2 log log x log x  m  (log log x)k−1 log x  +1 log x  ,  and so  52  Chapter 6. The Average Order of sk,  m≤log2 x  (log log (x/m))k−1 (log log x)k−1 ≥ log x m +1 log (x/m)  ζ( + 1) + O  1 log2 x  (log log x)k−1 log2 x ζ( + 1)(log log x)k−1 = +O log x  +O  (log log x)k−1 . log2 x (6.11)  Combining (6.10) and (6.11) we have that  m≤log2 x  ζ( + 1)(log log x)k−1 (log log (x/m))k−1 = +O log x m +1 log (x/m)  (log log x)k log2 x  .  (6.12) Now we must bound the second term on the right-hand side of (6.9).  log2 x<m≤x/2k  (log log (x/m))k−1 m +1 log (x/m)  log2 x<m≤x/2k  (log log x)k−1 m +1  (log log x)k−1 . log2 x A similar argument shows that  m≤x/2k  (log log (x/m))k−2 m +1 log (x/m)  (log log x)k−2 . log x  (6.13)  This we use to bound the error term in (6.8). Applying this information to (6.8) we have that  53  Chapter 6. The Average Order of sk,  (p1 · · · pk ) p1 <...<pk  x p 1 · · · pk  =  x +1 × ( + 1)(k − 1)! ζ( + 1)(log log x)k−1 +O log x +O  =  x  (log log x)k log2 x  +1 (log log x)k−2  log x +1 (log log x)k−1  ζ( + 1)x ( + 1)(k − 1)! log x x +1 (log log x)k−2 +O log x  .  (6.14)  This is the main term in n≤x sk, (n). To complete the computation of the sum, we need only bound all that remains. We will first complete the case when r = k, by bounding the second term in the right-hand side of (6.7):  54  Chapter 6. The Average Order of sk,  ∞  x  (p1 · · · pk ) p1 <...<pk  j1 ,...,jk =1 j1 ···jk >1  pj11  · · · pjkk ∞  (p1 · · · pk )  x p1 <...<pk p21 p2 ···pk ≤x  p1 <...<pk p21 p2 ···pk ≤x  x p1 <...<pk p21 p2 ···pk ≤x  (p1 · · · pk ) p21 p2 · · · pk   x 1     p   p≤x k+1  p  x  · · · pjkk  1 1 − (p1 − 1) · · · (pk − 1) p1 · · · pk  (p1 · · · pk )  x  1  j1 j1 ,...,jk =1 p1 j1 ···jk >1  −2  n n≤x/p ω(n)=Ω(n)=k−1  −2 (x/p)  1  −1      (log log (x/p))k−2 log (x/p)  p≤x k+1  =x  +1 1  (log log (x/p))k−2 p2 log (x/p)  p≤x k+1  x  +1 (log log x)k−2  log x  .  (6.15)  Let us now bound the terms of Theorem 6.1 corresponding to r < k. We require the following power series identity: ∞ n=j  n−1 n x = j−1  x 1−x  j  ,  which holds for |x| < 1. We have  55  Chapter 6. The Average Order of sk,  k−1  (pi11 · · · pirr ) × r=1 p1 <...<pr i1 +···+ir =k i1 ,...,ir >0    ∞   j1 ,...,jr =1  j1 − 1 jr − 1 ··· i1 − 1 ir − 1   x pj11  · · · pjrr  ∞  r  k−1  (pi11  x    · · · pirr )  r=1 i1 +···+ir =k p1 <...<pr i1 ,...,ir >0 pi1 ···pirr ≤x  m=1 jm =im  jm − 1 1 im − 1 pjm  1  k−1  r  (pi11  =x  · · · pirr )  r=1 i1 +···+ir =k p1 <...<pr i1 ,...,ir >0 pi1 ···pirr ≤x  m=1  1 pm − 1  im  1  k−1  (pi11 · · · pirr )  x  −1  r=1 i1 +···+ir =k p1 <...<pr i1 ,...,ir >0 pi1 ···pirr ≤x 1  =x  =  n  −1  n≤x ω(n)<k=Ω(n) x x t −1 d(πk∗ (t) 2−  − πk (t)).  (6.16)  Applying integration by parts to (6.16), and using the bound (6.6), we have that k−1  (pi11 · · · pirr ) × r=1 p1 <...<pr i1 +···+ir =k i1 ,...,ir >0    ∞   j1 ,...,jr =1  x  j1 − 1 jr − 1 ··· i1 − 1 ir − 1  +1 (log log x)k−2  log x  .   x pj11 · · · pjrr   (6.17)  Combining Theorem 6.1 with (6.14), (6.15), and (6.17), we have proved the following Theorem: 56  Chapter 6. The Average Order of sk, Theorem 6.3. Let k ≥ 2, and let sk, (n) = n≤x  ≥ 1. Then  ζ( + 1)x +1 (log log x)k−1 +O ( + 1)(k − 1)! log x  x  +1 (log log x)k−2  log x  .  57  Chapter 7  Modular Distribution of Prime Symmetric Functions The material found in this chapter is an outgrowth of work found in the paper of the author entitled “On the modular distribution of divisor functions” submitted for publication to the Journal of Number Theory. The problems we tackle here are motivated by a result of Alladi and Erd˝os. They showed [1], that the sum of prime factors with repetition function, e1 is uniformly distributed modulo 2. More precisely, they used an elementary argument to demonstrate that there is a constant c0 > 0 such that √ (−1)e1 (n) xe−c0 log x log log x . n≤x  They also proved the related result: ∞ n=1  (−1)e1 (n) = 0. n  We will prove look at some generalizations of this result, though with weaker error terms. Our main tool will be Perron’s formula.  7.1  Perron’s Formula an −  n≤x  1 2πi  c+iT c−iT  A(s)xs ds s  ∞  x <n< 3x 2 2  xc T  x T |x − n|  +  n=1  |an | min 1,  +  |an |n−c  ax if x ∈ N . T  The version in this form was first shown to us by Dr. Greg Martin from his lecture notes. It can be derived from [32], pp. 137-142. The summation symbol Σ indicates that if x is an integer, then “the last term is to be 58  Chapter 7. Modular Distribution of Prime Symmetric Functions counted with weight 1/2” ([32] p.138). Here A(s) is the Dirichlet series for the sequence an , and the constant c is a real number greater than the maximum of 0 and the abscissa of convergence of A(s). In the cases we shall be concerned with, an will always satisfy |an | ≤ 1. Consequently, we can take c = 1+1/ log x. We will also assume that T → ∞ but that T ≤ x. The third error term is O(1/T ). The first error term satisfies: ∞  |an |n−c n=1  xc T  ζ(c)  xc T  x T (c − 1)  x log x . T  For the second error term, we break up the sum: |an | min 1, x <n< 3x 2 2  x T |x − n|  = x <n< 2  (1− T1 )x  x (x − n)T  1+  + (1− T1 )x≤n≤(1+ T1 )x  (1+ T1 )x<n< 3x 2  x (n − x)T  =Σ1 + Σ2 + Σ3 . Now Σ2 Σ1  x/T , and x T  (1− T1 )x dt x t=(1− 1 )x = [− log (x − t)]t= x T x 2 x−t T 2  x log T . T  A similar result holds for Σ3 . We have proved the following Lemma: Lemma 7.1. If |an | ≤ 1, T ≤ x and c = 1 + 1/ log x, then an − n≤x  1 2πi  c+iT c−iT  A(s)xs ds s  x log x . T  Lemma 7.2. Suppose that A(s) is analytic on a region of the form D=  σ + it : σ ≥ 1 −  K log (|t| + 4)  \{y ∈ R : y ≤ 1}.  Suppose further that there are real constants w > 0 and α, 0 ≤ α < 1 such that A(s) A(s)  logw |t| if |t| ≥ 4 1 if |t| ≤ 4. |s − 1|α 59  Chapter 7. Modular Distribution of Prime Symmetric Functions If c = 1 + 1/ log x, and T = exp logδ x , where δ = (1 + α2 )/2, then c+iT  A(s)xs ds s  c−iT  x . (log x)(1−α)/2  Furthermore, if A(s) is the Dirichlet series for an , and |an | ≤ 1, then an n≤x  x . (log x)(1−α)/2  Proof. The last statement follows from the first together with Lemma 7.1. The idea of the proof is to pull back the integral where we can, and integrate K around the branch cut. Let c = 1 − log (T +4) , let β = (1 + α)/2, and let c = 1/ logβ x. Shift the line of integration to the union of the following line segments in sequence: γ1 : c − iT to c − iT γ2 : c − iT to c − i4 γ3 : c − i4 to c − ic γ4 : c − ic to c − ic γ5 : c − ic to c + ic γ6 : c + ic to c + ic γ7 : c + ic to c + i4 γ8 : c + i4 to c + iT γ9 : c + iT to c + iT. Assume that T ≥ 4. Denote the integral of A(s)xs /s over γi as  i.  Then  c+iT  9  |A(s)||xs | ds |s| c +iT xc logw T (c − c ) T w−1 x log T T x(log x)δ(w−1) exp (logδ x)  The integral over γ1 can be likewise bounded. 60  Chapter 7. Modular Distribution of Prime Symmetric Functions Next, c +iT 8  c +i4 T c  x  |A(s)||xs | ds |s|  logw t dt t 2 x logw+1 T K log x log T  exp  x(log x)(w+1)δ exp (K(log x)1−δ ) The integral over γ2 can be likewise bounded. Furthermore, c +i4  xc 7  c +ic  x logα T  ds |s − 1|α  exp  K log x log T  x logα T , exp (K(log x)1−δ )  and the integral over γ3 can be likewise bounded. Over γ6 we have c +ic  xc 6  c+ic  ds |s − 1|α  x (c  )α log T  x x , = δ−αβ (log x) (log x)(1−α)/2  with a similar result holding for γ4 . Finally, c+ic  xc 5  c−ic  ds |s − 1|α  xc logα x =  x x = . β−α (log x) (log x)(1−α)/2  In each case, it is clear that the integral is bounded as the Lemma requires.  7.2  Bounding L(s, χ) and ζ(s)  Fix a modulus q. We wish to bound ζ(s) and L(s, χ) for a non-principal character χ modulo q in ways that will be useful to us. We have the following consequences of [32] pp.362-363. There is a positive constant Kq such that if σ ≥ 1 − Kq / log (|t| + 4), then for each nonprincipal χ (mod q), L(s, χ) is nonzero, and satisfies | log L(s, χ)| ≤ log log (|t| + 4) + Oq (1); 1 q log (|t| + 4). L(s, χ)  (7.1)  61  Chapter 7. Modular Distribution of Prime Symmetric Functions These inequalities in turn imply that: L(s, χ)  q  log (|t| + 4);  | arg L(s, χ)| ≤ 2 log log (|t| + 4) + Oq (1).  (7.2) (7.3)  Note that we need not concern ourselves with whether or not q is exceptional, since we need only take the constant Kq to be smaller to produce the same results. In the case when χ = χ0 is the principal character modulo q, we have (1 − p−s ).  L(s, χ0 ) = ζ(s)  (7.4)  p|q  From [5], p.188, 197-198, 208, there is a constant K > 0 such that for σ ≥ 1 − K/ log (|t| + 4), ζ(s) is nonzero, and satisfies the following: 1 ζ(s) ζ(s) ζ (s) ζ  log (|t| + 4),  (7.5)  log |t|, if |t| ≥ 4  (7.6)  log |t|, if |t| ≥ 4.  (7.7)  From equations (7.5) and (7.6), it follows that | log |ζ(s)|| ≤ log log |t| + O(1), for |t| ≥ 4.  (7.8)  Let D denote the region D=  s:1−  K ≤ σ ≤ 2 \{y ∈ R : y ≤ 1}. log (|t| + 4)  Lemma 7.3. For s ∈ D, with |t| ≥ 4, log ζ(s)  log log t  Proof. We may assume that t ≥ 4. For any δ, 0 < δ ≤ 1, if 1 + δ ≤ ς ≤ 2,  62  Chapter 7. Modular Distribution of Prime Symmetric Functions then ζ (ς + it) ≤ ζ  ∞ n=1  Λ(n) n1+δ log p + O(1) p1+δ  = p  ∞  log u dπ(u) + O(1) 1+δ 2− u ∞ du + O(1) 1+δ u 2 1 . =O δ  =  (7.9)  For a given N ∈ N, σ must lie in one of the intervals K 1 1 1 ,1 + , 1+ ,1 + , log (t + 4) log t log t (log t)1−1/N 1 1 1 1+ ,1 + ,..., 1 + ,2 . 1−1/N 1−2/N (log t) (log t) (log t)1/N 1−  Let σn = 1+1/(log t)n/N , for n = 0, 1, . . . , N , and let σN +1 = 1−K/ log (t + 4). Now σ  | log ζ(s)| = ∞ 2  ≤ ∞  ζ (ς + it) dς ζ  ζ (ς + it) dς + ζ N −1  = O(1) +  O n=0  N −1 n=0  σn − 1 σn+1 − 1  σn+1 σn  ζ (ς + it) dς + ζ  σN +1 σN  ζ (ς + it) dς ζ  + O(1)  = O N (log t)1/N + O(1). Putting N = log log t , we have the desired result. We use Lemma 7.3 to prove the following: Lemma 7.4. Let ω ∈ C satisfy |ω| ≤ 1. There is an absolute positive constant C0 such that for s ∈ D with |t| ≥ 4, exp (ω log ζ(s))  logC0 |t|. 63  Chapter 7. Modular Distribution of Prime Symmetric Functions Proof. Write ω = α + iβ. Then for s as required, | exp (ω log ζ(s))| =|ζ(s)|α exp (−β arg ζ(s)) log|α| |t| exp (| log ζ(s)| + | log |ζ(s)||), by (7.5) and (7.6), exp (O(log log t)), by (7.8) and Lemma 7.3.  Lemma 7.5. Let ω = α + iβ. For s ∈ D, |t| ≤ 4, exp (ω log ζ(s))  1 . |s − 1|α  Proof. Since ζ(s) = 1/(s − 1) + O(1), on the specified region we have that arg ζ(s) 1. Hence | exp (ω log ζ(s))| = |ζ(s)|α exp (−β arg ζ(s)) |ζ(s)|α 1 = (1 + O(s − 1)) |s − 1|α  1 . |s − 1|α  Lemma 7.6. Let ω = α + iβ. For σ ≥ 1 − Kq / log (|t| + 4), with χ nonprincipal, we have that exp (ω log L(s, χ))  q  (log (|t| + 4))|α|+2|β| .  Proof. For s as required, we have by (7.1), (7.2) and (7.3) that |exp (ω log L(s, χ))| = |L(s, χ)|α exp (−β arg L(s, χ)) q  (log (|t| + 4))|α| exp (2|β| log log (|t| + 4))  = (log (|t| + 4))|α|+2|β| .  Lemma 7.7. Suppose (a, q) = 1, and ω ∈ C satisfies |ω| ≤ 1. Then   1 ω = exp  χ(a) ¯ log L(s, χ) exp(ϕ(s)), 1 − ωp−s φ(q) p≡a (mod q)  χ (mod q)  where ϕ(s) is analytic on σ > 1/2, and satisfies ϕ(s)  1 for σ ≥ 1/2 + . 64  Chapter 7. Modular Distribution of Prime Symmetric Functions Hence  1 p≡a (q) 1−ωp−s  has an analytic continuation to  s:1−  Dq =  Kq ≤ σ \{y ∈ R : y ≤ 1}. log (|t| + 4)  Proof. We shall make use of the result 1 φ(q)  χ(a) ¯ log L(s, χ) = pj ≡a(mod q)  χ(mod q)  p−js , j  (c.f. [5], p. 239), which holds for σ > 1. Let ∞  ϕ(s) = p≡a (mod q) j=2  ω j p−js −ω j  pj ≡a(mod q) j≥2  p−js j  Thus ϕ(s) satisfies the claims of the Lemma, because it is represented as an absolutely convergent series for σ > 1/2, and as the coefficients of p−js are bounded, ϕ(s) is bounded as required. Furthermore:   ∞ j −js 1 ω p  = exp  −s 1 − ωp j p≡a (mod q) p≡a (mod q) j=1   −js p  = exp ω exp(ϕ(s)) j pj ≡a (mod q)   ω = exp  χ(a) ¯ log L(s, χ) exp(ϕ(s)). φ(q) χ (mod q)  The lemma then follows from the results on zero free regions of analyticity for L-functions.  7.3  Additive Prime Symmetric Functions  In this section, we will put the previous results to work in generalizing Alladi and Erd˝os. Let m, r, k1 , . . . , kr ∈ N, let b be an integer such that 1 ≤ b ≤ m, and let q1 , . . . , qr ≥ 2 be pairwise relatively prime integers. In general, we shall denote the real and imaginary parts of a complex number s by σ and t respectively, and for n ∈ N, we shall write ζn for the primitive n-th root of unity e2πi/n . The following notations apply to Section 7.3: 65  Chapter 7. Modular Distribution of Prime Symmetric Functions Notation 7.8. e = (ek1 , . . . , ekr ), q = q1 · · · qr , d = gcd(m, b) m = m/d b = b/d Q = lcm(q, m ) S = {1 ≤ n < Q : (n, Q) = 1} ek (n) =  1, if n ≡ (mod k); 0 otherwise.  For ease of explication, let a = (a1 , . . . , ar ) be a fixed element of Zq1 × · · · × Zqr , and let q = (q1 , . . . , qr ), and k = (k1 , . . . , kr ). Congruences involving these vectors are taken coordinate-wise over the appropriate moduli. We wish to show that the collection of functions (ek1 , . . . , ekr ) taken in order is simultaneously uniformly distributed modulo (q1 , . . . , qr ), over the arithmetic sequence b (mod m). The main result of Section 7.3 is the following asymptotic formula: 1∼ n≤x n≡b(mod m) e(n)≡a(mod q)  x as x → ∞. mq  (7.10)  Observe that 1 q  r =1        (ek (n)−a )j  ζq  q −1  =  j=0  1, if e(n) ≡ a(q); 0 otherwise.  For j = (j1 , . . . , jr ) ∈ Zq1 × · · · × Zqr , let ek (n)j1  f (n) = f (j; n) = ζq1 1  e  · · · ζqrkr  (n)jr  .  Note that f (n) is completely multiplicative. Hence we have  66  Chapter 7. Modular Distribution of Prime Symmetric Functions  1= n≤x n≡b(mod m) e(n)≡a(mod q)  1 q  1 = q =  =  1 q 1 q  q1 −1  qr −1 1 j1 ζq−a ··· 1  j1 =0  r jr ζq−a r  jr =0  q1 −1  f (j; n) n≤x n≡b(m)  qr −1 1 j1 ζq−a 1  r jr ζq−a r  ···  j1 =0  jr =0  q1 −1  f (j; mn + b) 0≤n≤(x−b)/m  qr −1 1 j1 ζq−a ··· 1  r jr f (j; d) ζq−a r  j1 =0  jr =0  q1 −1  qr −1 1 j1 ζq−a ··· 1  j1 =0  f (j; m n + b ) 0≤n≤(x−b)/m  r jr ζq−a f (j; d) r  jr =0  em b (n)f (j; n). n≤x/d  Since m and b are relatively prime, we may write em b (n) =  1 φ(m )  χ(b ¯ )χ(n). χ(mod m )  Thus,  1= n≤x n≡b(mod m) e(n)≡a(mod q)  1 qφ(m )  q1 −1  qr −1 1 j1 ζq−a ··· 1  j1 =0  r jr ζq−a r  jr =0  × f (j; d)  χ(b ¯ ) χ(mod m )  χ(n)f (j; n). n≤x/d  Note that f (0; n) = 1, and so  67  Chapter 7. Modular Distribution of Prime Symmetric Functions  1= n≤x n≡b(mod m) e(n)≡a(mod q)  + =  1 qφ(m )  1 qφ(m )  χ(n)  χ(b ¯ ) n≤x/d  χ(mod m )  r jr 1 j1 ζq−a · · · ζq−a f (j; d) r 1  j=0  x + O(1) qm 1 + qφ(m )  r jr 1 j1 f (j; d) ζq−a · · · ζq−a r 1  j=0  χ(n)f (j; n)  χ(b ¯ ) n≤x/d  χ(mod m )  χ(b ¯ ) χ(mod m )  χ(n)f (j; n) n≤x/d  (7.11) To prove the asymptotic formula (7.10), it suffices, due to (7.11), to show that n≤x χ(n)f (n) = o(x), for any fixed j = 0 and character χ (mod m ). To do this, we shall use Perron’s formula, and hence we must consider the Dirichlet −s series ∞ n=1 χ(n)f (n)n . Fix such a j and χ (mod m ). Now, for σ > 1, define ∞  χ(n)f (n)n−s .  A(s) = A(j, χ; s) = n=1  Note that A(s) is absolutely convergent for σ > 1. Due to the complete multiplicativity of χ(n)f (n), A(s) has the following Euler product for σ > 1:  A(s) = p  = p|q  1 1 − χ(p)f (p)p−s 1 1 − χ(p)f (p)p−s  1 a∈S p≡a(mod Q)  1−  k1 χ(a)ζqa1 j1  kr j r  · · · ζqar  p−s  .  The first term in this product is a non-zero analytic function for σ > 0, which we will denote by F (s). That is, F (s) = F (j, χ; s) = p|q  1 . 1 − χ(p)f (p)p−s  A(s) continues analytically to the region DQ as described in Lemma 7.7. By taking KQ smaller if necessary, we may insist that DQ ⊆ D ∪ {s ∈ C : 68  Chapter 7. Modular Distribution of Prime Symmetric Functions σ ≥ 1}, and so the results of Lemmas 7.3 through 7.6 apply for s ∈ DQ . Furthermore, there is a function ϕ(s) satisfying the claims of Lemma 7.7 such that   ω(χ∗ ) log L(s, χ∗ ),  A(s) = F (s) exp(ϕ(s)) exp  χ∗ (mod q)  where ω(χ∗ ) = ω(j, χ; χ∗ ) = Note that F (s) Write  q,k  1 φ(Q)  k1 j 1  χ(a)χ¯∗ (a)ζqa1  kr j r  · · · ζqar  .  a∈S  1 on 1/2 ≤ σ ≤ 2, and also that |ω(χ∗ )| ≤ 1. ω(χ∗ ) = α(χ∗ ) + β(χ∗ )i,  for its real and imaginary parts, and for the principal character modulo Q, make the denotations: ω0 = ω(χ∗0 ), α0 = α(χ∗0 ), β0 = β(χ∗0 ). Remark 7.9. It transpires that ω(χ∗ ) = 1. Indeed, if ω(χ∗ ) = 1, then k1 kr χ(a)χ¯∗ (a)ζqa1 j1 · · · ζqar jr = 1 for all a ∈ S, and in particular for a = 1. However, since q1 , . . . , qr are pairwise relatively prime, j = 0 by assumption, and χ(1) = χ∗ (1) = 1, this yields a contradiction. It follows that α(χ∗ ) < 1. Define constants w1 , w > 0 as follows: (|α(χ∗ )| + 2|β(χ∗ )|);  w1 = w1 (j, χ) = χ∗ =χ∗0 (mod Q)  w = w1 + C0 . Proposition 7.10. Let s ∈ D ∩ DQ . Then A(s)  Q  logw1 (|t| + 4) exp (ω0 log ζ(s)).  (7.12)  Furthermore, A(s)  Q  A(s)  Q  1 if |t| ≤ 4, |s − 1|α0 logw |t| if |t| ≥ 4.  (7.13) (7.14) 69  Chapter 7. Modular Distribution of Prime Symmetric Functions Proof. The inequality (7.12) follows from the above results, together with (7.4) and Lemma 7.6. From this, (7.13) follows, via Lemma 7.5. The inequality (7.14) follows from (7.12) and Lemma 7.4. Theorem 7.11. If q1 , . . . , qr ≥ 2 are pairwise relatively prime, then there is a number δ > 0, such that x +O mq  1= n≤x n≡b(m) e(n)≡a(q)  x logδ x  Proof. By Proposition 7.10, we may apply Lemma 7.2 to A(j; s), for each j = 0, taking α = max{0, α0 }, and K = KQ , since α0 < 1. Note that α0 depends on j. The theorem then follows by (7.11). Corollary 7.12. Let s(n) denote the sum of prime factors with repetition function, and let q be a fixed prime. Then 1= n≤x s(n)≡a(q)  x + Oq q  √  x log x  .  Proof. In this case, we have m = 1 = r, and k1 = 1. Since q is prime, we have: q−1 1 1 ω0 = ζqbj = α0 = − , q−1 q−1 b=1  for any j not congruent to 0 modulo q. Thus we may take α = max{−1/(q − 1), 0} = 0, and so (1 − α)/2 = 1/2. The Corollary follows from Lemma 7.2.  7.4  The Distribution of sk Modulo q  We now switch our focus to the elementary prime symmetric functions. It is tempting to assume that sk must also be uniformly distributed modulo any modulus, but this is not the case. Our goal then, is to compute an asymptotic formula for #{n ≤ x : sk (n) ≡ a(mod q)} for some q ≥ 2. To do so, we will proceed as we did in the previous section, using Perron’s formula in conjunction with Lemma 7.2. Let ζ = e2πi/q . Then 1= n≤x sk (n)≡a(q)  1 q  q−1  ζ −aj j=0  ζ jsk (n)  (7.15)  n≤x  70  Chapter 7. Modular Distribution of Prime Symmetric Functions Thus we must study the sum  n≤x ζ  jsk (n) .  With this intent let  ∞  ζ jsk (n) n−s .  A(j; s) = n=1  7.4.1  The Dirichlet Series  Definition 7.13. Define pβ .  κ = κ(q, k) = q p|q pβ ||k!  Note that for any n ∈ N, (q, n) = 1 if and only if (κ, n) = 1. Lemma 7.14. For any n ∈ N, and k ≤ k, n k  ≡  n + κ(q, k) k  (mod q).  Proof. Let κ = κ(q, k). Then there is a polynomial p(x) ∈ Z[x] such that n+κ k  =  n k  +  κ p(n) ≡ k!  n k  (mod q).  Definition 7.15. For i, q ∈ N, let Ωq,i (n) = #{p|n repetitions allowed : p ≡ i (mod q)}. Corollary 7.16. Suppose that for n ∈ N, Ωq,i (n) ≡ ki (mod κ), for i = 0, . . . , q − 1, where ki is chosen to be the least nonnegative residue modulo κ. Let σ : Zqκ −→ Zq be defined by σ(k) = σ(k0 , . . . , kq−1 ) = j1 +···+jq−1 =k  k1 kq−1 j1 ··· 1 · · · (q − 1)jq−1 , j1 jq−1  Then σ(k) ≡ sk (n)(mod q).  71  Chapter 7. Modular Distribution of Prime Symmetric Functions Proof. By the definition of sk , we have modulo q: sk (n) ≡ j1 +···+jq−1 =k  ≡ j1 +···+jq−1 =k  Ωq,1 (n) Ωq,q−1 (n) j1 j2 ··· 1 2 · · · (q − 1)jq−1 j1 jq−1 kq−1 j1 j2 k1 1 2 · · · (q − 1)jq−1 , by Lemma 7.14 ··· jq−1 j1  = σ(k).  Remark 7.17. Corollary 7.16 implies that the value of sk (n) modulo q depends only on the values of Ωq,i (n) modulo κ. From this it follows that for any m, n ∈ N, we have that sk (mκ n) ≡ sk (n) (mod q). The Dirichlet series A(j; s) cannot be nicely expressed as an Euler product, since except for the case when k = 1, ζ jsk (n) is not multiplicative. The key however, is to observe that A(j; s) can be expressed as a linear combination of Euler products. Proposition 7.18. There exist constants α(j; i0 , . . . , iq−1 ), where 0 ≤ ib ≤ κ − 1 for b = 0, . . . , q − 1 such that for σ > 1, A(j; s) =  (7.16) q−1  ··· 0≤i0 ≤κ−1  α(j; i0 , . . . , iq−1 ) 0≤iq−1 ≤κ−1  b=0 p≡b(mod q)  1 1 − ζκib p−s  .  (7.17) Denote the vector (i0 , . . . , iq−1 ) by i, and by k the vector (k0 , . . . , kq−1 ), 0 ≤ ki ≤ κ − 1 for i = 0, . . . , q − 1, and let σ(k) be as in Corollary 7.16. Then we have 1 ζκ−k·i ζ jσ(k) . α(j; i) = q κ q k∈Zκ  Proof. Order variables α(j; i0 , . . . , iq−1 ) according to the base κ expansion of i0 . . . iq−1 ; that is, let α(j; i0 , . . . , iq−1 ) be in the i0 +i1 κ+· · ·+iq−1 κq−1 -th position, beginning at 0. Sums over i range over all values in Zqκ . Now consider the κq equations in the κq unknowns α(j; i) where the k0 + k1 κ + · · · + kq−1 κq−1 -th equation is ζ jσ(k) =  α(j; i)ζκi·k .  (7.18)  i  72  Chapter 7. Modular Distribution of Prime Symmetric Functions Let A1 denote the κ × κ Vandermonde matrix whose ij-th entry (beginning the row and column count at 0) is ζκij . By construction, the coefficient matrix of this system, which we shall denote by A, is the q-fold Kronecker product of A1 with itself. A1 and hence A are symmetric Butson-Hadamard matrices (cf. [6] and [7]). Hence, AA∗ = κq I, where A∗ is the conjugate matrix of A (equal in this case to the conjugate transpose). If we express this system in the form Ax = b, where     ζ jσ(0,0,...,0) α(j; 0, 0, . . . , 0)     α(j; 1, 0, . . . , 0) ζ jσ(1,0,...,0)     x=  and b =  , .. ..     . . ζ jσ(κ−1,κ−1,...,κ−1)  α(j; κ − 1, κ − 1, . . . , κ − 1) then x=  1 ∗ A b, κq  which implies that α(j; i) =  1 κq  ζκ−k·i ζ jσ(k) k∈Zqκ  Now fix an n and suppose that Ωq,i (n) ≡ ki (mod κ) for i = 0, . . . , q − 1. Then ζ jsk (n) = ζ jσ(k) . On the right-hand side of (7.17), we see that the coefficient of n−s is α(j; i)ζκi·k , i  so equating the coefficients in (7.17) we obtain equations of the type (7.18). Hence the α(j; i) exist as required. Let S = {n ∈ N : 1 ≤ n ≤ q − 1, (n, q) = 1}, and let 1  F (i; s) =  i  p|q  1 − ζκp p−s  .  73  Chapter 7. Modular Distribution of Prime Symmetric Functions Then by the previous proposition and Lemma 7.7 we can write 1  α(j; i)F (i; s)  A(j; s) = i∈Zqκ  1 − ζκib p−s  b∈S p≡b(mod q)      α(j; i)F (i; s) exp   = i∈Zqκ  ω(i; χ) log L(s, χ) exp(ϕ(i; s)),  χ (mod q)  (7.19) 1 for σ ≥ 1/2 + , and  where ϕ(i; s)  ω(i; χ) =  1 φ(q)  ζκib χ(b) ¯ = α(i; χ) + iβ(i; χ). b∈S  Remark 7.19. Note that |ω(i; χ)| ≤ 1. The important question though is whether or not ω(i; χ0 ) = 1, since these will be the exponents of ζ(s) in the expression for A(j; s). This occurs precisely when ib = 0 for all b ∈ S. Thus there are κq−φ(q) values of i for which this takes place. Notation 7.20. Z = {i ∈ Zqκ : ib = 0 for all b ∈ S}, Z = Zqκ \Z, α = max{0, α(i; χ0 ) : i ∈ Z }, T = exp (log x)(1+α c=1+ G(i; s) =  1 log x 1 − p−s i  p|q  1 − ζκp p−s  2 )/2  .  Note that 0 ≤ α < 1. Now we can express A(j; s) as follows: A(j; s) =  α(j; i)G(i; s)ζ(s) i∈Z   +  α(j; i)F (i; s) exp  i∈Z   ω(i; χ) log L(s, χ) exp(ϕ(i; s)).  χ (mod q)  (7.20)  74  Chapter 7. Modular Distribution of Prime Symmetric Functions It is easily seen that for i ∈ Z the function     ω(i; χ) log L(s, χ) exp(ϕ(i; s))  F (i; s) exp  χ (mod q)  satisfies the conditions of Lemma 7.2 with respect to the given α. Hence by that same Lemma, we may conclude that   c+iT s x F (i; s) exp  ω(i; χ) log L(s, χ) exp(ϕ(i; s)) ds s c−iT χ (mod q)  x . (log x)(1−α)/2  (7.21)  On the other hand, if i ∈ Z, then 1 2πi  c+iT c−iT  xs s  G(i; s)ζ(s) ds =Res +  1 2πi  xs s  G(i; s)ζ(s); s = 1 xs s  γ  G(i; s)ζ(s) ds,  where γ is the union of the following three paths: γ1 : line segment from c − iT to 1 −  K − iT log (T + 4)  K + it for −T ≤ t ≤ T log (|t| + 4) K + iT to c + iT γ3 : line segment from 1 − log (T + 4) γ2 : Along 1 −  Using arguments analogous to Lemma 7.2, together with the bounds established on ζ(s) and the fact that the path γ is bounded away from the pole at s = 1, we have that 1 2πi  c+iT c−iT  xs s  G(i; s)ζ(s) ds = xG(i; 1) + O  x (log x)(1−α)/2  .  (7.22)  The order of magnitude of the error term is in fact much better than this, but it is all we require. Note that the implicit constants here depend on q.  75  Chapter 7. Modular Distribution of Prime Symmetric Functions Now, by (7.20), (7.21), (7.22) and Lemma 7.1 we obtain ζ jsk (n) = n≤x  =  1 2πi +  A(j; s)xs ds + O s  c−iT c+iT  α(j; i) c−iT  i∈Z  1 2πi  G(i; s)ζ(s) ds  i∈Z  × c−iT  +O  xs s  x log x T  α(j; i)  c+iT  =  c+iT  1 2πi    xs    F (i; s) exp   s  ω(i; χ) log L(s, χ) exp(ϕ(i; s)) ds  χ (mod q)  x log x T  α(j; i)xG(i; 1) + O i∈Z  x (log x)(1−α)/2  .  (7.23)  Theorem 7.21. There is a δ > 0 such that as x → ∞,  n≤x sk (n)≡a (q)  x 1= q qκ  q−1  1 − p−1  ζ (σ(k)−a)j ζκ−i·k j=0  i∈Zqκ k∈Zqκ (b,q)=1⇒ib =0  i  1 − ζκp p−1  p|q  x , logδ x where if q is prime, we interpret iq to be i0 . +O  Proof. Using Proposition 7.18, and combining equations (7.15) and (7.23) we have: 1= n≤x sk (n)≡a (q)  =  =  1 q x q  q−1  ζ −aj j=0  α(j; i)xG(i; 1) + O i∈Z  q−1  ζ −aj j=0  x qκq  α(j; i)G(i; 1) + O i∈Z  q−1  +O  x (log x)(1−α)/2  x (log x)(1−α)/2 1 − p−1  ζ (σ(k)−a)j ζκ−i·k j=0 i∈Z k∈Zqκ  x (log x)(1−α)/2  i  p|q  1 − ζκp p−1  .  76  Chapter 7. Modular Distribution of Prime Symmetric Functions  7.5  Examples  The process outlined in the last section can be simplified (and elucidated) with examples.  7.5.1  s2 modulo 3  It transpires that s2 is uniformly distributed modulo 3 in the sense that ζ s2 (n) = o(x), n≤x  where ζ = e2πi/3 . Let  ∞  ζ s2 (n) n−s .  A(s) = n=1  Since s2  (3r n)  ≡ s2 (n) (mod 3), we may write A(s) =  1 1 − 3−s  ∞  ζ s2 (n) n−s . 3n  For i = (i1 , i2 ) ∈ Z23 , there are constants α(i) such that ∞  ζ s2 (n) n−s =  α(i) i∈Z23  3n  p≡1 (3)  1 1 − ζ i1 p−s  p≡2 (3)  1 . 1 − ζ i2 p−s  If 3 n, then s2 (n) ≡ j1 +j2 =2  Ω3,1 (n) j1  Ω3,2 (n) j2 2 (mod 3). j2  Equating the coefficient of n−s , we obtain a system of equations in the  77  Chapter 7. Modular Distribution of Prime Symmetric Functions α(i), Ax = b:      1 1 1 1 1 1 1 1 1 α(0, 0) 1 1 ζ ζ 2 1 ζ ζ 2 1 ζ ζ 2  α(1, 0)  1       1 ζ 2 ζ 1 ζ 2 ζ 1 ζ 2 ζ  α(2, 0)  ζ        1 1 1 ζ ζ ζ ζ 2 ζ 2 ζ 2  α(0, 1)  1        1 ζ ζ 2 ζ ζ 2 1 ζ 2 1 ζ  α(1, 1) = ζ 2  .      1 ζ 2 ζ ζ 1 ζ 2 ζ 2 ζ 1  α(2, 1) ζ 2       1 1 1 ζ 2 ζ 2 ζ 2 ζ ζ ζ  α(0, 2)  ζ       1 ζ ζ 2 ζ 2 1 ζ ζ ζ 2 1  α(1, 2) ζ 2  1 ζ2 ζ ζ2 ζ 1 ζ 1 ζ2 α(2, 2) ζ The vector b is obtained by considering the values of ζ σ(k) , where k = (k1 , k2 ) ∈ Z23 corresponds to (Ω3,1 (n), Ω3,2 (n)), and σ(k) = j1 +j2 =2  The coefficient matrix A  1  A= 1 1  k1 j1  k2 j2 2 . j2  satisfies    1 1 1 1 1 ζ ζ 2  ⊗ 1 ζ ζ 2  . ζ2 ζ 1 ζ2 ζ  It is a symmetric Butson Hadamard matrix and hence satisfies AA∗ = 9I, where A∗ is its conjugate matrix. Using this it is easy to solve the system √ √ i 3 −i 3 1 and obtain α(0, 2) = α(2, 0) = 2 + 6 , α(1, 1) = 3 , and the rest to be 0. This enables us to write √ 1 i 3 ζ2 − 1 ζ A(s) = + exp log (1 − 3−s ) exp − log ζ(s) 2 6 2 2 2  exp (−1)j  × j=1  ζ2 − 1 2  log L(s, χ1 ) exp (ϕj (s))  √ i 3 − exp ((ζ − 1) log(1 − 3−s )) exp (ζ log ζ(s)) exp (ϕ3 (s)), 3 where χ1 is the non-principal character (mod 3), and the ϕj (s) are bounded as in Lemma 7.7. Since every term of the form exp (c log ζ(s)) occurs only with the real part of c less than 1, everything can be suitably bounded, and we can prove that n≤x ζ s2 (n) = o(x). 78  Chapter 7. Modular Distribution of Prime Symmetric Functions  7.5.2  s3 modulo 2  This example will be a case in which uniform distribution does not occur. Let s3 (n) n−s . It transpires that s (n) (mod 2) is determined A(s) = ∞ 3 n=1 (−1) by Ω2,1 (n) (mod 4). In fact, s3 (n) ≡  Ω2,1 (n) 3  (mod 2).  There are constants α(j) for j ∈ Z4 such that A(s) =  1 1 − 2−s  3  α(j) j=0  p=2  1 . 1 − ij p−s  Equating coefficients in the Dirichlet series yields the system   0      (−1)(3) α(0) 1 1 1 1 1   1 1 i −1 −i  α(1) (−1)(3)   1         1 −1 1 −1 α(2) = (−1)(23)  =  1  ,   3 α(3) 1 −i −1 i −1 ) ( 3 (−1) with solutions     1/2 α(0) α(1) −i/2     α(2) =  1/2  . i/2 α(3)   This enables us to write 1 i A(s) = ζ(s) − exp ((i − 1) log(1 − 2−s )) exp (i log ζ(s)) exp(ϕ1 (s)) 2 2 1 1 + 2−s ζ(2s) + 2 1 − 2−s ζ(s) i + exp ((−i − 1) log(1 − 2−s )) exp (−i log ζ(s)) exp(ϕ3 (s)). 2 √ Note the term 21 ζ(s). Thus taking T = exp log x , we can show  79  Chapter 7. Modular Distribution of Prime Symmetric Functions  1= n≤x s3 (n)≡0 (2)  n≤x  = ∼  1 + (−1)s3 (n) 2  x 1 + 2 2 x + 2  1 2  (−1)s3 (n) n≤x  1 2πi  x 1 1 + 2 2 2πi x 1 ∼ + Res 2 2 3x x x . = + = 2 4 4  ∼  c+iT c−iT c+iT  A(s)xs ds s  ζ(s) xs ds 2 s c−iT ζ(s) xs ;s = 1 2 s  This density result is confirmed by empirical data:  80  Chapter 7. Modular Distribution of Prime Symmetric Functions  Table 3. s3 (n)-Modulo 2 x 100 1000 5000 10000 20000 30000 50000  7.5.3  #{n ≤ x : s3 (n) ≡ 0 (mod 2)} 93 836 3954 7743 15232 22654 37350  1 x #{n  ≤ x : s3 (n) ≡ 0 (mod 2)} .93 .836 .7908 .7743 .7616 .75513 .747  sk modulo a prime q  The result of Theorem 7.21 simplifies considerably if we restrict q to being prime. In this case, we take κ = q β+1 , where q β ||k!, and we define σ : −→ Zq by Zq−1 κ σ(k) = σ(k1 , . . . , kq−1 ) = j1 +···+jq−1 =k  k1 kq−1 j1 ··· 1 · · · (q − 1)jq−1 . j1 jq−1  If ζ = e2πi/q , then  n≤x sk (n)≡a (q)  x 1 ∼ q−1 qκ  q−1  ζ (σ(k)−a)j . j=0 k∈Zq−1 κ  81  Chapter 8  Partitions into Prime Powers 8.1  Introduction  In this chapter we look at partitions of positive integers into fixed powers of prime numbers. For a given underlying set A ⊆ N, and a positive integer n ∈ N, we denote the number of partitions of n with parts taken from A by pA (n). For the most part, we will be taking A = P(r) , by which we mean the set of rth powers of prime numbers. The asymptotic formula  log pP(r) (n) ∼ (r + 1) Γ  1 +2 ζ r  r/(r+1)  1 +1 r  n1/(r+1) (log n)−r/(r+1) , (8.1)  where  ∞  Γ(z) =  e−t tz−1 dt  0  is the gamma function, was first proved by Hardy and Ramanujan [19] in 1916. Further work has been done by Mitsui [31] and Grosswald [17]. Kerawala [25] attempts an elementary proof of (8.1) for r = 1, but his proof contains errors. We begin by adapting work of Bateman and Erd˝os on the eventual monotonicity of a large class of partition functions to a case of interest.  8.2  Monotonicity  In this section we follow the work of the author [49] previously published in the Journal of Integer Sequences, and that of Bateman and Erd˝os [4]. First (k) let us revisit some important notation. The k-th difference function pA (n) (k) can defined inductively as follows: for k = 0, pA (n) = pA (n). If k > 0, then (k)  (k−1)  pA (n) = pA  (k−1)  (n) − pA  (n − 1).  82  Chapter 8. Partitions into Prime Powers (k)  (k)  Let fA (x) be the generating function for pA (n). We have [4] the following power series identity: ∞ (k)  (k)  pA (n)xn  fA (x) =  (8.2)  n=0 ∞  = (1 − x)k  pA (n)xn  (8.3)  1 . 1 − xa  (8.4)  n=0 k  = (1 − x)  a∈A (k)  This may be used to define pA (n) for all k ∈ Z, including k < 0. (k) Bateman and Erd˝os [4] characterize the sets A for which pA (n) is ultimately nonnegative. Note that if k < 0, then the power series representation (k) of (1 − x)k has nonnegative coefficients so that pA (n) ≥ 0. For k ≥ 0, they prove the following: if A satisfies the property that whenever k elements are removed from it, the remaining elements have greatest common divisor 1, then (k) lim p (n) n→∞ A  = ∞.  A simple consequence of this is the fact that pA (n) is eventually monotonic if k > 0. (k) No explicit bounds for when pA (n) ceases to take on negative values are included with the result of Bateman and Erd˝os [4]. By following their approach but specializing to the case when A = P, we shall find bounds for (k) n depending on k which guarantee that pP (n) ≥ 0. (1) In a subsequent paper, Bateman and Erd˝os [3] prove that pP (n) ≥ 0 for all n ≥ 2. That is, the sequence of partitions of n into primes is weakly increasing for n ≥ 1. We have shown [49] that if A = P( ) is the set of -th pow(k) ers of primes, and F (k, ) = min {N ∈ N : n ≥ N implies that pA (n) > 0}, then for a fixed ∈ N, log F (k, ) = o (k + 2)8  k  ,  as k → ∞. For the sake of clarity, we have decided to restrict our attention to the set of prime numbers. In a series of papers (c.f. [36]- [39]), L. B. Richmond studies the asymptotic behaviour of partition functions and their differences for sets satisfying 83  Chapter 8. Partitions into Prime Powers certain stronger conditions. The results nonetheless apply in the cases of (k) A = P( ) . Richmond finds [38] an asymptotic formula in n for pA (n). Unfortunately, his formula is not useful towards finding bounds for when (k) pA (n) must be positive, since, as is customary, he does not include explicit constants in the error term. Furthermore, his asymptotic formula includes functions such as α = α(n) defined by the solution to the equation n= a∈A  a k − α . −1 e −1  eαa  As we are seeking explicit constants, a direct approach will be cleaner than than attempting to adapt the aforementioned formula. Another result worthy of comment from Richmond [38] pertains to a conjecture of Bateman and Erd˝os [4]. His result applies to A = P( ) , and states that (k+1) pA (n) = O(n−1/2 ), as n → ∞. (k) pA (n) We shall write ζn for the primitive n-th root of unity e2πi/n , and the m-th prime by pm . We will have cause to use the so-called “primorial” notation, that is, let n# = p, p≤n  where the product is taken over all primes less than or equal to n. We have two main results. The first is Theorem 8.13 in which we demonstrate that for a given k ∈ N, there exist h, h1 ∈ N depending on k such that (k) if n ≥ h + h1 − 1, then pP (n) ≥ 0. In Notation 8.9 (p. 91) shall determine explicit formulae for h and h1 in terms of k. Secondly, in Theorem 8.14 we show that if (k)  N (k) = min{N ∈ N : pP (n) ≥ 0 for all n ≥ N }, then as k → ∞, log N (k)  k  k(4+log 16) 1+O  log log k log k  .  Following Bateman and Erd˝os [4], we first tackle the finite case. Lemma 8.1. Let B be a finite subset of P of size r, and suppose that k < r. (k) The function pB (n) can be decomposed as follows: (k)  (k)  (k)  pB (n) = gB (n) + ψB (n), 84  Chapter 8. Partitions into Prime Powers (k)  where gB (n) is a polynomial in n of degree r − k − 1 with leading coefficient (r − k − 1)!  −1  p∈B  (k)  , and ψB (n) is periodic in n with period  p  p∈B  p.  (k)  Proof. We use partial fractions to decompose the generating function fB (x) as follows: (k) fB (x)  1 = (1 − x)r−k  p−1  p∈B j=1  1  (8.5)  1 − ζpj x  α1 α2 αr−k + = + + ... + 2 1 − x (1 − x) (1 − x)r−k  p−1  p∈B j=1  β(ζpj ) 1 − ζpj x  ,  (8.6)  where the αi , and β(ζpj ) are complex numbers depending on k and the set B. Note that  −1 αr−k =   p  .  p∈B  The power series expansion for (1 − x)−h is given by 1 = (1 − x)h  ∞  n+h−1 n x . h−1  n=0  Hence, if r−k (k)  gB (n) =  αh h=1  and  n+h−1 , h−1  q−1 (k) ψB (n)  β(ζqj )ζqjn ,  = q∈B j=1  then the lemma is proved. (k)  (k)  For the remainder of this section, gB (n) and ψB (n) shall be as in Lemma 8.1, for a given finite set B ⊆ P which shall be clear from the context. Remark 8.2. Let B be as in Lemma 8.1. We wish to know the precise value of β(ζqj ). To simplify notation a little, write βζ instead, when ζ is clear from  85  Chapter 8. Partitions into Prime Powers the context. In particular, suppose η = ζqj , where q ∈ B, and 0 < j < q. Then 1 1 (k) (1 − ηx)fB (x) = (1 − x)k q−1 1 + ηx + · · · + (ηx) 1 − xp p∈B p=q   = βη + (1 − ηx)   α1 αr−k + + ··· + 1−x (1 − x)r−k  ζ=η   βζ  , 1 − ζx  hence, βη =  (1 − η¯)k q  p∈B p=q  1 . 1 − η¯p  The following inequalities shall be useful: θ2 θ2 θ4 ≤ cos θ ≤ 1 − + , 2 2 24 which holds for all values of θ. Note that 1−  √  √  |eiθ − 1| =  2(1 − cos θ),  so for −2 3 ≤ θ ≤ 2 3, |θ| 1 −  θ2 ≤ |eiθ − 1| ≤ |θ|. 12  In particular, for 0 ≤ θ ≤ π, θ2 ≤ |eiθ − 1| ≤ θ. (8.7) 12 Lemma 8.3. Suppose that ζ = 1 is a q-th root of unity, q ≥ 2, and let θ  b0 = 2π  1−  π2 12 .  1−  Then  b0 ≤ |1 − ζ| ≤ 2. q Proof. Clearly |1 − ζ| ≤ 2. On the other hand, by the inequality (8.7), |1 − ζ| ≥ |1 − e2πi/q | ≥  2π q  ≥  b0 . q  1−  4π 2 12q 2  86  Chapter 8. Partitions into Prime Powers  We shall continue to use the value for b0 given in Lemma 8.3 throughout this section. Note that b0 ≈ 2.647398833. Lemma 8.4. Suppose that k < r, and B ⊆ P, satisfies |B| = r. Suppose further that η = ζqj , for some q ∈ B, j ∈ {1, . . . , q − 1}. Then  k r−2 q  2 r−1 , if k ≥ 0; b0 |βη | ≤ qr−k−2  r−k−1 , if k < 0. b0  Proof. Making use of Remark 8.2 and Lemma 8.3 we have that for k ≥ 0: |βη | =  ≤  |1 − ζq−j |k q 2k q  p∈B p=q  1 p∈B p=q  |1 − ζq−jp |  1 |1 − ζq |  2k q q b0 2k q r−2 = r−1 . b0  r−1  ≤  A similar arguments works for the case when k < 0. Theorem 8.5. Suppose that k < r, and B ⊆ P, satisfies |B| = r. Then  k 2 r−1 ,  r−1 if k ≥ 0; p∈B p (k) b0 |ψB (n)| ≤ 1 r−k−1 ,  r−k−1 if k < 0. p∈B p b0  87  Chapter 8. Partitions into Prime Powers Proof. First assume that k ≥ 0. By Lemmas 8.4 and 8.1, p−1 (k) |ψB (n)|  β(ζpj )ζpjn  = p∈B j=1 p−1  |β(ζpj )|  ≤ p∈B j=1 p−1  ≤ p∈B j=1  = ≤  2k pr−2 br−1 0  2k br−1 0  (p − 1)pr−2 p∈B  2k  p br−1 0 p∈B  r−1  .  A similar argument works for k < 0. To obtain bounds for the coefficients αh , we will use Laurent series. Lemma 8.6. Suppose that k < r, and B ⊆ P, satisfies |B| = r. Denote the largest element of B by Q, and suppose further that 0 < r0 < |1 − ζQ |. Let p−1  (|ζpj − 1| − r0 ).  dB (r0 ) = p∈B j=1  Then |αh | ≤  1 r0r−k−h dB (r0 )  .  Proof. Let γ be the circle |z − 1| = r0 . From equations (8.5) and (8.6), and the Laurent Expansion Theorem, we have that |αh | = ≤ ≤  1 2πi 1 2π  (k)  γ  fB (z)(z − 1)h−1 dz 1  γ  |z − 1|r−k−h+1 1  r0r−k−h dB (r0 )  p−1  1  j p∈B j=1 |1 − ζp z|  dz  .  88  Chapter 8. Partitions into Prime Powers (k)  Proposition 8.7. For k ≤ 0, and D1 ⊆ D2 ⊆ N, we have pD2 (n) ≥ (k)  pD1 (n) ≥ 0. Proof. This follows immediately from equation 8.3 and the fact that for k ≤ 0, the power series expansion for (1 − x)k has nonnegative coefficients. For the sake of clarity and the comprehensiveness of this exposition we include the following proposition, suitably adapted to our requirements from Bateman and Erd˝os [4]. Proposition 8.8. Let D ⊆ N be an infinite set. For any t ∈ N, we have that pD (n) (t − 1)2 n2t−3 1 + ≤ . (−1) t+1 t + 1 p(−1) (n) p (n) D  D  Proof. Denote by Pq (n), the number of partitions of n into parts from D such that there are exactly q distinct parts. Pq (n) has generating function ∞  Pq (n)xn = n=0  {a1 ,...aq }⊆D  xaq xa1 · · · . 1 − xa1 1 − xaq  If Rq (m) is defined by ∞  Rq (m)xm = m=0  {a1 ,...aq }⊆[n]  xa1 xaq , · · · 1 − xa1 1 − xaq  where [n] = {1, . . . , n}, then Pq (n) ≤ Rq (n). There are nq subsets of [n] of size q. Also, the coefficient of xn in (xa1 + x2a1 + · · · ) · · · (xaq + x2aq + · · · ) is less than or equal to the coefficient of xn in ∞  (x + x2 + · · · )q = m=q  so Pq (n) ≤  n q  n−1 q−1  m−1 m x , q−1 ≤ n2q−1 .  89  Chapter 8. Partitions into Prime Powers Any partition n = n1 a1 + · · · nq aq , where a1 , . . . , aq ∈ D, gives rise to a partition of n − ai for i = 1, . . . , q, namely n − a1 = (n1 − 1)a1 + n2 a2 + · · · + nq aq , n − a2 = n1 a1 + (n2 − 1)a2 + · · · + nq aq , .. . n − aq = n1 a1 + n2 a2 + · · · + (nq − 1)aq . Note that no two distinct partitions of n can give rise to the same partition of any m < n in this way, and so n  n−1  qPq (n) ≤ q=1  pD (m). m=0  Now if t ∈ N, then n (−1) pD (n)  =  pD (m) m=0 n  ≥ pD (n) +  qPq (n) q=1 n  (q − t)Pq (n)  = (t + 1)pD (n) + q=1  t−1  ≥ (t + 1)pD (n) − (t − 1)  Pq (n) q=1 2 2t−3  ≥ (t + 1)pD (n) − (t − 1) n  ,  and the theorem is proved. A consequence of Proposition 8.8 is that for an infinite set D, lim  n→∞  pD (n) (−1)  pD  = 0.  (n)  We are now going to restrict our attention to some more specific subsets of P.  90  Chapter 8. Partitions into Prime Powers Notation 8.9. For the remainder of this section, fix k ∈ N, and B = {p1 , p2 , . . . , pk+2 } ⊂ P. Furthermore, define positive integers g, h, t, and u by:     k+1  2  k+1  g= p − 1 , b0 p∈B   k+1 2 pk+1  h= , pk+2 # b0   p∈B  t = 2h(g + 1) − 1, u = 2t − 2. Let C = P \ B, and let C1 = {pk+3 , pk+4 , . . . , pk+2t } be the least u elements of C, Q = max{C1 } = pk+2t , r0 = 21 |1 − ζQ |, and √  d=  Γ p∈C1  p+1 2  π 2p−1  Γ  3p/2 p2p−1  Γ  2  3 π √ 3 π  +  1 2  p+  1 2  −  1 2  p+  1 2  ,  Finally, let h1 =  Q#u pk+2 #  2 d  2Q b0  u  +1+  u2 (u − 1)u−1 4  (k)  . (k)  Lemma 8.10. For all n ∈ N0 , pB (n) ≥ −g, and for all n ≥ h, pB (n) ≥ 1. Proof. From Lemma 8.1, (k)  (k)  (k)  pB (n) = gB (n) + ψB (n). Then (k)  (k)  (k)  pB (n) = gB (n) + ψB (n) (k)  = α1 + α2 (n + 1) + ψB (n) (k)  ≥ α1 + α2 + ψB (n),  91  Chapter 8. Partitions into Prime Powers (k)  since α2 = 1/(pk+2 #) > 0. But α1 + α2 = 1 − ψB (0), so p−1 (k)  β(ζpj )(ζpjn − 1)  pB (n) ≥ 1 + p∈B j=1  p−1  |β(ζpj )|  ≥1−2 p∈B j=1  2 b0  ≥1−  k+1  pk+1 , p∈B  by Theorem 8.5. The first assertion then follows from the fact that b0 is transcendental. This establishes the first assertion. For the second, if n ≥ h, then (k)  pB (n) ≥ α1 + α2 +  k+1  2 b0  (k)  pk+1 + ψB (n) ≥ 1, p∈B  reasoning as before. Lemma 8.11. If n ≥ h1 then (t − 1)2 n2t−3 1 , ≤ (−1) t+1 p t+1 (n)  (8.8)  1 (t − 1)2 n2t−3 ≤ . (−1) t+1 p t+1 (n)  (8.9)  C1  and hence  C  Proof. The second inequality follows from the first via Proposition 8.7. By Lemma 8.1, we may write (−1)  (−1)  (−1)  pC1 (n) = gC1 (n) + ψC1 (n), where  u+1 (−1)  gC1 (n) =  αh h=1  n+h−1 . h−1  By Lemma 8.6, we have |αh | ≤  1  , r0u dC1 (r0 ) 92  Chapter 8. Partitions into Prime Powers so (−1) gC1 (n)  1 pk+2 # n + u − u ≥ Q# u r0 dC1 (r0 )  u  n+h−1 h−1  h=1  pk+2 # n + u n+u 1 ≥ . − u Q# u r0 dC1 (r0 ) u − 1 Let  p−1  |1 − ζpj | − r0 ,  δp = j=1  so that dC1 (r0 ) =  δp . p∈C1  Since all the elements of C1 are odd, making use of the inequalities (8.7), we have p−1 2  |1 − ζpj | − r0  δp =  2  j=1 p−1 2  |1 −  = j=1 p−1 2  ≥ j=1 p−1 2  = j=1  =Γ  4π 2 j 2 p2 π2j 2 p2  1−  1−  p+1 2  2  p+1 2  2  2  1 |1 − ζQ | 1− 2 |1 − ζpj |  ζpj |2  π2j 2 3p2  2  1 2  π2j 2 3p2  π2 √ 3p2  p−1  p−1 2  √  j=1  √  =Γ  π 2p−1 3p/2 p2p−1  Γ Γ  √  3p −j π  3 π √ 3 π  3p +j π  +  1 2  p+  1 2  −  1 2  p+  1 2  .  (8.10)  Thus we can conclude that dC1 (r0 ) ≥ d. Making use of Theorem 8.5, we have that our Theorem will be proved if for all n ≥ h1 , pk+2 # n + u 1 n+u − u − Q# u r0 d u − 1  p∈C1  p b0  u  ≥  u2 u−1 n . 4  (8.11)  93  Chapter 8. Partitions into Prime Powers Together with the fact that via Lemma 8.3, 1 ≤ r0u  2Q b0  u  ,  the inequality (8.11) is implied by  u Q#u n+u  1 2Q n≥ + n+u−1 d b0 u−1 pk+2 # u−1  p∈C1  p b0  u   u2 u−1  + n , 4 (8.12)  for n ≥ h1 . It is easily deduced that h1 ≥ Quu and that bu0 (u − 1)u−1 < . (Quu )u−1 uQu Hence for n ≥ h1 , we have n+u u−1 n+u−1 u−1  1 n+u−1 u−1  p∈C1  p b0  =  n+u ≤ 2, n+1  ≤  u−1 n+u−1  u  u−1 p∈C1  (u − 1)u−1 ≤ (Quu )u−1 nu−1  ≤  n+u−1 u−1  nu−1 (u  p b0  p∈C1 1)u−1  p b0  u  u  < 1, and  − ≤ (u − 1)u−1 . (n + u − 1)u−1  The inequality (8.12) is implied by Q#u 2 n≥ pk+2 # d  2Q b0  u  +1+  u2 (u − 1)u−1 , 4  which is certainly true for all n ≥ h1 . The following Corollary is an immediate consequence of Lemma 8.11 and Proposition 8.8: Corollary 8.12. For n ≥ h1 , pC (n) (−1) pC (n)  ≤  2 . t+1 94  Chapter 8. Partitions into Prime Powers Theorem 8.13. If n ≥ h + h1 − 1, then (k)  pP (n) ≥ 0. Proof. The following identity is established by considering the generating (k) function for pP (n), and using the fact that P is the disjoint union of B and C: n  (k) pP (n)  (k)  pB (n − m)pC (m).  = m=0  Thus, by Lemma 8.10 and Corollary 8.12, for n ≥ h + h1 − 1, n−h (k)  n (k)  (k)  pB (n − m)pC (m) +  pP (n) = m=0  m=n−h+1  n−h  ≥  pB (n − m)pC (m)  n  pC (m) − g m=0 (−1)  = pC  pC (m) m=n−h+1 n  (n) − (g + 1)  pC (m) m=n−h+1 n  (−1)  ≥ pC  (−1)  (n) − (g + 1)pC  (n)  (−1)  m=n−h+1 (−1)  (n) − (g + 1)pC  (−1)  (n) − pC  ≥ pC  = pC  (−1)  (−1)  pC (m)  (n)h  pC  (m)  2 t+1  (n) = 0.  Next we will use the information in this section to compute an asymptotic bound in k. Theorem 8.14. Let (k)  N (k) = min{N ∈ N : pP (n) ≥ 0 for all n ≥ N }. There is a function ε = ε(k)  log log k log k  log N (k)  such that as k → ∞,  k k(4+log 16)(1+ε) .  95  Chapter 8. Partitions into Prime Powers Proof. Clearly, log N (k)  log h  log h + log h1 . Now,    pk+1   log (pk+2 #) + log  p∈B  log p + log p∈B  pk+2 k+2 (k + 2) log pk+2  k log pk+2 + k log k  k log k.  (8.13)  From the definition of h1 , it is easily seen that log h1  Q# pk+2 #  log  1 d  + log  + u log Q.  (8.14)  But log  Q# pk+2 # u log Q  k+2t  k+2t  log pj  log j  j=1  t log t since k < t, and  (8.15)  j=1  t log t.  (8.16)  Also, log  1 d  | log δp |,  (8.17)  p∈C1  so we need to look at bounding δp and 1/δp , for p ∈ C1 . By Stirling’s Formula (2.5) we have p−1 2  |1 − ζpj |2  δp ≤ j=1 p−1 2  ≤ j=1  =  4π 2 j 2 p2  2π p 2π p  p−1  Γ p−1  p+1 2  π(p − 1)p 2p−1 ep−1  2  π e  p  p.  96  Chapter 8. Partitions into Prime Powers On the other hand, if √  3 1 − π 2 √ 3 1 + π 2  c1 = c2 =  p−  1 and 2  √  √  3 π  c3 =  1 p− , 2  3 − 21 π  1 2  −  √  √  3 π  3 + 21 π  1 2  +  ,  then by (8.10) and Stirling’s formula, 1 ≤ δp  3p/2 p2p−1 π 2p−1  Γ(c1 + 1) Γ  3p/2 p2p−1 π 2p−1 √ 2e2 3c3 π2  1 d  2  Γ(c2 + 1)  2p−1 ep−1 cc11 π(p − 1)p c2 c2 p  We may conclude that | log δp | log  p+1 2  p  2p−1 −2p  p  c1 c2 −c1 e c2 √ 2e2 3c3 π2  p  1 p  .  p, and so by (8.17) p p∈C1  Q2 log Q  t2 log t.  (8.18)  In turn, by (8.13) through (8.16), we have that log N (k)  t2 log t.  To complete the proof, we must bound t2 log t. Since t h pk+2 #g we have t2 log t  (gh)2 log h  (pk+2 #)2 g 4 k log k  (8.19) gh, and  (8.20)  So we must bound g, but first, from Nathanson [33], p. 269, we invoke that fact that for every positive integer n, p < 4n . p≤n  97  Chapter 8. Partitions into Prime Powers In particular, we have that (pk+2 #)2 < 16pk+2 = exp ((log 16)pk+2 ) = exp (log 16)k log k 1 + O =k  (log 16)k 1+O  log log k log k  log log k log k  .  (8.21)  Next, 2 b0  g  k+1  pk+1 p∈B  (k + 2) k  2 b0  2pk+2 b0  k+1  (k + 2) log (k + 2) 1 + O  k k+2 (log k)k+1  2 b0  k+1  1+O  log log k log k  k+1  k+1  log log k log k  (8.22)  Putting together (8.19) through (8.22) we have  logN (k)  k  4+log 16+O  log log k log k  k+9  (log k)4k+5   2+O  log log k log k  b0  4k+4   exp [k log k(4 + log 16) + O(k log log k) + 9 log k + (4k + 5) log log k + O(k)] k  k(4+log 16) 1+O  log log k log k  ,  and the proof is complete.  8.3  Asymptotic Formulae  The material found in this section is taken from the paper [48] by the author entitled “On partitions into powers of primes and their difference functions,” accepted for publication in the Canadian Journal of Mathematics.  98  Chapter 8. Partitions into Prime Powers Our purpose in this section is to prove the following asymptotic formula: 1 +2 ζ r  (k−1)  log pP(r) (n) =(r + 1) Γ ×  1 +1 r  (log log n)1+ log n  1+O  r/(r+1)  n1/(r+1) (log n)−r/(r+1) , as n → ∞,  for fixed k, r ≥ 1. This is a generalization of (8.1) which is the k = 1 case. The asymptotic (8.1) was first given by Hardy and Ramanujan [19], though without an explicit error term. They did not, however, provide a rigorous (1) proof of this fact. Indeed, they assume that for a given r, pP(r) (n) ≥ 0 for all n. This is readily seen to be false for r as low as 2, n = 5. Fortunately, we can use the monotonicity results of the previous section and Bateman and Erd˝os [4] to rectify the dilemma, and still follow their approach to the problem. The theorem is of the Tauberian type: we shall first prove estimates for the generating functions, and then use them to yield information about the coefficients. The subsequent analysis will be made easier with the following version of the prime number theorem: π(x) = Li(x) + E(x), where, recalling if necessary x  1 dt; and 2 log t x E(x) = Oδ , for all δ ≥ 2. logδ x  Li(x) =  8.3.1  Asymptotic Formula for the Generating Function  In the following argument, s is assumed to be a small positive quantity approaching 0. Define r φ(s) = e−sp . p  Lemma 8.15. As s → 0+ , ∞  φ(s) = 2  r  e−su du + Oδ log u  s−1/r logδ (1/s)  , 99  Chapter 8. Partitions into Prime Powers for any δ ≥ 2. Proof. Using Riemann-Stieltjes integration, we have ∞  φ(s) = 2− ∞  =  r  e−su dπ(u) r  e−su d(Li(u) + E(u))  2− ∞  = 2  r  e−su du + log u  ∞  r  e−su dE(u).  (8.23)  2−  Let C = C(s) = log−δ (1/s). Note that as s → 0+ , s = o(C(s)). Assume that 2r s < C. Integration by parts gives ∞  ∞  r  e−su dE(u) = rs  2−  r  ur−1 e−su E(u) du + O(1)  2 ∞ δ  rs 2  r  ur e−su du + O(1) logδ u  ∞ δ  t s  rδ 2r s  ∞  = Cs−1/r  2r s  1/r  e−t dt + O(1), via the substitution t = sur δ log (t/s) t1/r e−t  log t log (1/s)  δ  dt + O(1)  +1     = Cs−1/r   C 2r s  ∞  t1/r e−t log t log (1/s)  δ  +1  dt + C  t1/r e−t log t log (1/s)  δ  +1   dt + O(1). (8.24)  100  Chapter 8. Partitions into Prime Powers Now, t1/r e−t  C  log t log (1/s)  2r s  t1/r e−t  C δ  dt 2r s  log (2r s) log (1/s)  C  t1/r e−t  2r s  r log 2 log (1/s)  +1 =  δ  δ C  δ  dt  +1  logδ (1/s)  dt  t1/r e−t dt  2r s δ  C logδ (1/s)  = 1. On the other hand for C ≤ t < ∞, we have that log t/ log (1/s) + 1 is minimized when t = C, so that ∞  ∞  t1/r e−t log t log (1/s)  C  δ  t1/r e−t  dt  −δ log log (1/s) log (1/s)  C  +1  ∞ δ  δ  dt  +1  t1/r e−t dt  0 δ  1.  Hence by (8.24), ∞  r  e−su dE(u)  2−  δ  Cs−1/r ,  which together with (8.23) completes the proof. Lemma 8.16. As s → 0+ , ∞ 2  r  e−su du = rΓ log u  1 + 1 s−1/r (log (1/s))−1 + O r  s−1/r log log (1/s) log2 (1/s)  .  Proof. Making the substitution t = sur into the integral gives ∞ 2  r  e−su du = s−1/r log u  ∞ 1/r−1 −t t e 2r s  log (1/s)  dt  = s−1/r (log (1/s))−1 (I1 + I2 + I3 ),  (8.25) 101  Chapter 8. Partitions into Prime Powers where 1/ log2r (1/s)  t1/r−1 e−t  I1 = log2 (1/s)  I2 =  t1/r−1 e−t  1/ log2r (1/s) ∞  I3 =  log t log (1/s)  1+  2r s  1+  log t log (1/s)  t1/r−1 e−t  log2 (1/s)  1+  log t log (1/s)  dt,  dt, and  dt.  We will consider each of these integrals individually. For t ∈ [2r s, 1/ log2r (1/s)], log t/ log (1/s) is closest to −1 when t = 2r s. Hence 1/ log2r (1/s)  I1  t1/r−1 e−t 1+  2r s  log 2r s log (1/s)  1/ log2r (1/s)  log (1/s)  dt,  t1/r−1 e−t dt  2r s 1/ log2r (1/s)  t1/r−1 dt  log (1/s) 0  1 . log (1/s)  (8.26)  Now we consider I2 . For t ∈ [1/ log2r (1/s), log2 (1/s)], we have 1 1+  log t log (1/s)  =1+O  log log (1/s) log (1/s)  ,  and so using integration by parts: log2 (1/s)  I2 = 1/ log  =r t  2r  (1/s)  1/r −t  e  log log (1/s) log (1/s)  t1/r−1 e−t dt + O ∞  log2 (1/s) 1/ log2r (1/s)  ∞  +O  +r  But  ∞ 0  e  1/ log2r (1/s)  dt + O  0  t1/r e−t dt  log2 (1/s)  t  1/r −t  t1/r e−t dt  0  +O  log log (1/s) log (1/s)  t1/r e−t dt = Γ  .  1 +1 , r 102  Chapter 8. Partitions into Prime Powers and all the remaining terms are O(log log (1/s)/ log (1/s)), so I2 = rΓ  1 +1 +O r  log log (1/s) log (1/s)  .  (8.27)  Finally, 1 log (1/s) 1 . log (1/s)  I3  ∞  t1/r−1 e−t dt  2  log (1/s)  (8.28)  The proof is completed by combining (8.25), (8.26), (8.27), and (8.28). The previous two lemmas yield: Corollary 8.17. As s → 0+ , φ(s) = rΓ  s−1/r log log (1/s) log2 (1/s)  1 + 1 s−1/r (log (1/s))−1 + O r  .  Let k ∈ N, and define ∞ r  (k)  f (s) = n=0  pP(r) (n)e−ns = (1 − e−s )k  (1 − e−sp )−1 . p  That is, f (s) is the generating function in e−s of the kth difference function of pP(r) (n). Taking logarithms we have r  log f (s) = k log (1 − e−s ) −  log (1 − e−sp ) p ∞  = k log (1 − e−s ) + p j=1 ∞  = k log (1 − e−s ) + j=1 ∞  = k log (1 − e−s ) + j=1  1 j  r  e−jsp j  r  e−jsp p  φ(js) . j  We wish to use our approximations for φ(s) to evaluate the sum To do this we break up the sum into two parts. Let  (8.29) ∞ φ(js) j=1 j .  N = (1/s)/(log (1/s)). 103  Chapter 8. Partitions into Prime Powers Then by Corollary 8.17:  j≤N  φ(js) j 1 + 1 s−1/r r  =rΓ  ×  j≤N    log log (1/js) 1  . +O j 1+1/r log (1/js) j 1+1/r log2 (1/js) j≤N  (8.30)  Now, 1 1 1 = log (1/s) log (1/js) 1+1/r 1 − log j j≤N j j≤N log (1/s)   1 1 1 log j   = + 1+1/r log j log (1/s) log (1/s) j 1+1/r j 1 − j≤N j≤N log (1/s) j 1+1/r  1 1 +1 +O =(log (1/s))−1 ζ r N 1/r   1 1 . O + 1+1/2r 1 − log j log2 (1/s) j≤N j log (1/s)  (8.31)  We have, (log (1/s))−1 = O(s1/r ), N 1/r and  1 j≤N  j 1+1/2r 1 −  (8.32)  = Σ1 + Σ2 ,  log j log (1/s)  where 1  Σ1 = j≤1/  Σ2 =  √  1+1/2r 1 − sj  log j log (1/s)  , and  1 √ 1/ s<j≤N  But Σ1  j 1+1/2r 1 − 1  √ j 1+1/2r j≤1/ s  log j log (1/s)  .  1,  104  Chapter 8. Partitions into Prime Powers and 1  Σ2  √ 1/ s<j≤N  j 1+1/2r 1 −  √ 1/ s<j≤N  j 1+1/2r  log N log (1/s)  log (1/s) log log (1/s)  s1/4r log (1/s) , log log (1/s) Hence  1 j≤N  j 1+1/2r 1 −  1.  log j log (1/s)  (8.33)  We use a similar technique to bound the error term in (8.30). Write  j≤N  1 log log (1/js) = (Σ1 + Σ2 ), 2 2 j 1+1/r log (1/js) log (1/s)  where log log (1/js)  Σ1 = j≤1/  Σ2 =  √  1+1/r 1 − sj  2,  log log (1/js) √  1/ s<j≤N  Then Σ1  log j log (1/s)  √  j≤1/ s  j 1+1/r 1 −  log log (1/s) j 1+1/r  log j log (1/s)  and  2.  log log (1/s),  and Σ2  log log (1/s) √ 1/ s<j≤N  √ 1/ s<j≤N  j 1+1/r 1 −  log N log (1/s)  2  log2 (1/s) j 1+1/r log log (1/s)  s1/2r log2 (1/s) . log log (1/s) 105  Chapter 8. Partitions into Prime Powers Hence, j≤N  log log (1/js) log2 (1/js)  log log (1/s) . log2 (1/s)  j 1+1/r  Next we must consider the tail of the sum  j>N  ∞  φ(js) j  n=2 j>N ∞  1 N 1 N  =  1 N 1 N  (8.34)  φ(js)/j:  e−jsn j e−jsn  n=2 j>N ∞ −N sn n=2  e 1 − e−sn 1 e−N sn + −sn 1−e N  2≤n≤1/s  e−N sn 2≤n≤1/s ∞  sn  +  1 N  e−N sn +  log (1/s)  n=2 e−2N s  n>1/s  e−N sn 1 − e−sn  e−N sn n>1/s  1 e−N N 1 − e−N s  s log (1/s)e−1/(s log (1/s)) 1 − e−N s 1 − e−N s 2 −2/ log (1/s) 2 log (1/s)e + s log (1/s)e−1/(s log (1/s))  log (1/s)  +  log2 (1/s).  (8.35)  Combining (8.29) through (8.35), and the fact that log (1 − e−s )  log (1/s)  s−1/r log log (1/s) , log2 (1/s)  as s → 0+ , we have the following theorem: Theorem 8.18. As s → 0+ , log f (s) = rΓ  1 +1 ζ r  1 + 1 s−1/r (log (1/s))−1 +O r  s−1/r log log (1/s) log2 (1/s)  106  .  Chapter 8. Partitions into Prime Powers  8.3.2  Bounding from Above  Now we are in a position to prove our main theorem, which we do in two parts, the first being the simplest. First let us introduce some new notation. (k−1) (k) Let k, r ≥ 1, an = pP(r) (n), An = ni=0 ai = pP(r) (n), and denote the following constants: A = rΓ  1 +1 ζ r  1 +1 , r  1 +2 ζ r  B = (r + 1) Γ  1 +1 r  r/(r+1)  .  Furthermore, choose C1 > 0 such that if δ(s) = C1  log log (1/s) , log (1/s)  then |1 − (1/A)s1/r log (1/s) log f (s)| < C1  log log (1/s) . log (1/s)  We begin by bounding log An from above. Lemma 8.19. There exists a function β n sufficiently large, log An <  log log n/ log n such that for all  Bn1/(r+1) (1 + β). (log n)r/(r+1)  Proof. We have that (1 − δ(s))As−1/r (log (1/s))−1 < log f (s) < (1 + δ(s))As−1/r (log (1/s))−1 . (8.36) Since limn→∞ an = ∞, there exists an N ∈ N depending on k and r such that n > N implies that an ≥ 0. We define a constant C2 by N  |aj |.  C2 = j=0  107  Chapter 8. Partitions into Prime Powers Thus if n > N , then N −ns  An e  n −ns  =  aj e  aj e−ns  +  j=0  j=N +1  N  n −ns  <  aj e  aj e−js  +  j=0  j=N +1  N  n −ns  =  aj (e  −js  −e  aj e−js  )+  j=0  j=0  < f (s) + C2 , and so log An <ns + (1 + δ(s))As−1/r (log (1/s))−1 + log (1 + C2 e−(1−δ(s))As  −1/r (log (1/s))−1  )  <ns + (1 + δ(s))As−1/r (log (1/s))−1 + O(e−(1−δ(s))As  −1/r (log (1/s))−1  ).  (8.37)  For a large value of n, we can, by continuity, choose a corresponding s > 0 such that 1 + δ(s) −(r+1)/r 1 − δ(s) −(r+1)/r As (log (1/s))−1 < n < As (log (1/s))−1 . r r (8.38) For these values of s and n, we deduce from (8.38) that 1 = s  rn log (1/s) A  1+O  log log (1/s) log (1/s)  r/(r+1)  ,  (8.39)  and hence log (1/s) =  r log n r+1  1+O  log log (1/s) log n  .  (8.40)  Note that this implies that log (1/s) log n log (1/s) as s → 0, or equivalently, as n → ∞, so we may use log n, and log (1/s) interchangeably in various error terms. This fact, together with equations (8.39) and (8.40)  108  Chapter 8. Partitions into Prime Powers implies that A rn log (1/s)  s=  log log (1/s) log (1/s)  1+O  r/(r+1)  r/(r+1) log log (1/s) A(r + 1) 1+O = r2 n log n log (1/s) B log log n . = 1+O r/(r+1) log n (r + 1)(n log n)  (8.41)  From (8.40) and (8.41), we infer that ns+As−1/r (log (1/s))−1 =  Bn1/(r+1) (r + 1)(log n)r/(r+1) +  =  A(r + 1)(r+1)/r n1/(r+1) rB 1/r (log n)r/(r+1)  Bn1/(r+1) (log n)r/(r+1)  1+O  log log n log n  1+O  1+O  log log n log n  log log n log n .  Therefore, by (8.37), log An <  Bn1/(r+1) (log n)r/(r+1)  1+O  log log n log n  .  (8.42)  This completes the proof of the lemma.  8.3.3  Bounding from Below  Lemma 8.19 is one half of what we require. We use it to prove the other half. Lemma 8.20. Let  > 0 be given. Then there is a function β  (log log n)1+ log n  such that for all n sufficiently large, log An >  Bn1/(r+1) (1 − β). (log n)r/(r+1) 109  Chapter 8. Partitions into Prime Powers First let us introduce a convenient bit of notation. At times throughout the following argument, we are guaranteed the existence of certain positive functions which are O(log log (1/s)/ log (1/s)) in magnitude, as s → 0+ . Rather than rename each such function, we may simply write η. Thus the precise η may vary, depending on the context, even within the same equation, but will always be used to denote such a positive function whose existence is guaranteed. Proof. Let A(x) = An , for n ≤ x < n + 1. Hence by (8.42), there is a constant C3 > 0, such that if η1 (x) = C3 then  log log x , log x  Bx1/(r+1) (1 + η1 (x)) . (log x)r/(r+1)  log A(x) <  (8.43)  Now ∞  an e−ns  f (s) = n=0 ∞  An (e−ns − e−(n+1)s )  =  n=0 ∞  =s  n+1  An n=0 ∞  =s  e−sx dx  n  A(x)e−sx dx.  (8.44)  0  The inequalities (8.36) together with equation (8.44) imply that ∞  exp (1 − δ(s))As−1/r (log (1/s))−1 < s  A(x)e−sx dx  0  < exp (1 + δ(s))As−1/r (log (1/s))−1 . (8.45) Given a small value of s > 0, we can, by continuity, choose a corresponding m > 0 such that r+1 1 = (m log m)r/(r+1) . s B  (8.46) 110  Chapter 8. Partitions into Prime Powers Now, denote ∞  f (s) = s  A(x)e−sx dx  0  (1−ζ)m  m/H  0  ∞  +  +  +  +  Hm  (1+ζ)m  (1−ζ)m  m/H  =s  (1+ζ)m  Hm  = J1 + J2 + J3 + J4 + J5 ,  (8.47)  where ζ=  (log log m)1+ , log m  and H > 1 is a constant yet to be determined. We will see that the dominant term here is J3 , but first we shall prove that the terms J1 , J2 , J4 , and J5 are negligible in comparison to the exponentials on either side of (8.45). We first despatch J1 , and J5 . From Lemma 8.19, we have m/H  J1 = s  A(x)e−sx dx  0  < exp (1 + η1 (m/H))B(m/H)1/(r+1) (log (m/H))−r/(r+1) .  (8.48)  Taking logarithms of (8.46), we see that r+1 log m (1 − η) < . r log (1/s) We can in light of this fact, select a positive function η3 (s) log log (1/s)/ log (1/s) such that for m sufficiently large relative to H (i.e. s sufficiently small), r+1 r  1 + η1 (m/H) 1−  log H log m  r/(r+1)  <  (1 + η3 (s)) log m . log (1/s)  111  Chapter 8. Partitions into Prime Powers This leads to the following string of inequalities: (1 + η1 (m/H))A(r + 1)1+(r+1)/r r2 log m 1 −  log H log m  r/(r+1)  (1 + η1 (m/H))B (r+1)/r log m 1 −  log H log m  r/(r+1)  (1 + η1 (m/H))Bm1/(r+1) (log m)r/(r+1) 1 −  log H log m  r/(r+1)  <  (1 + η3 (s))A(r + 1)(r+1)/r , r log (1/s)  <  (1 + η3 (s))A(r + 1)(r+1)/r , r log (1/s)  <  (1 + η3 (s))A(r + 1)(r+1)/r rB 1/r log (1/s) × m1/(r+1) (log m)1/(r+1)  (1 + η1 (m/H))Bm1/(r+1) (1 + η3 (s))A(r + 1) . < r/(r+1) 1/(r+1) (log (m/H)) H rH 1/(r+1) s1/r log (1/s) Comparing the final inequality with (8.48) yields: J1 < exp (1 + η3 (s))AH −1/(r+1) s−1/r (log (1/s))−1 , for s sufficiently small. Choose H large enough such that for all s in the range in question, 1 + η3 (s) 1 + δ(s) . ≤ 1/(r+1) 2 H Then J1 < exp ((1 + δ(s))/2)As−1/r (log (1/s))−1 . We now consider J5 . Note that max {η1 (x) : x > 1} = C3 /e. We may choose H sufficiently large such that 1 2(1 + C3 /e) > . r+1 H r/(r+1) Then B (r + 1)(m log m)r/(r+1) 2(1 + C3 /e)B > (Hm log (Hm))r/(r+1) 2(1 + η1 (x))B ≥ for all x ≥ Hm, (x log x)r/(r+1)  s=  112  Chapter 8. Partitions into Prime Powers and so  sx (1 + η1 (x))Bx1/(r+1) < , r/(r+1) 2 (log x)  for all x ≥ Hm. Thus ∞  J5 = s  A(x)e−sx dx  Hm ∞  <s  Bx1/(r+1) (1 + η1 (x)) − sx dx (log x)r/(r+1)  exp Hm ∞  <s  e−sx/2 dx  0  = 2, where the first inequality follows from (8.43). Now we take a look at the integrals J2 , and J4 , beginning with the latter. By (8.43), Hm  Hm  A(x)e−sx dx < s  J4 (s) = s (1+ζ)m  eψ(x) dx, (1+ζ)m  where ψ(x) = (1 + η1 (x))Bx1/(r+1) (log x)−r/(r+1) − sx.  (8.49)  If the maximum for ψ(x) occurs at x0 , then, via a straightforward differentiation, it transpires that 1 = s  1+O  log log x0 log x0  r + 1 r/(r+1) x (log x0 )r/(r+1) . B 0  Comparing this with (8.46), we conclude that log m x0 =  1+O  log log x0 log x0  (8.50)  log x0 , and that  m,  (8.51)  and therefore, for s sufficiently small, (1 − ζ)m < x0 < (1 + ζ)m.  (8.52)  Writing x = x0 + ξ, Taylor’s formula gives us ψ(x) = ψ(x0 ) +  B 2 d2 ξ (1 + η1 (x))x1/(r+1) (log x)−r/(r+1) 2 dx2  , x=x1  113  Chapter 8. Partitions into Prime Powers where x0 < x1 < x, and hence (1 − ζ)m < x1 < Hm.  (8.53)  From this, it is easily seen that there exist positive constants C4 , C5 such that d2 1/(r+1) 1/(r+1)−2 (1 + η1 (x1 )) x1 (log x1 )−r/(r+1) < −C4 x1 (log x1 )−r/(r+1) 2 dx1 < −C5 m1/(r+1)−2 (log m)−r/(r+1) . (8.54) Equations (8.49), and (8.50) yield that ψ(x0 ) = As−1/r (log (1/s))−1 1 + O  log log (1/s) log (1/s)  .  (8.55)  Combining the information on ψ(x), we see that there is a constant C6 > 0 such that J4 (s) <s exp (1 + η)As−1/r (log (1/s))−1 ∞  exp −C6 ξ 2 m1/(r+1)−2 (log m)−r/(r+1) dξ.  × (ζ−η)m  The integral on the right-hand side of this inequality is simplified by observing that it is of the form ∞  2  e−Cx dx,  D  for C, D > 0. Substituting ∞  −Cx2  e D  1 dx = √ C  ∞ 0  u2  = Cx2 − CD2 , we have that 2  2  ue−CD −u e−CD √ du < √ u2 + CD2 C  2  ∞  −u2  e 0  e−CD du = 2  2  π . C  Hence with D = (ζ − η)m, and C = C6 m1/(r+1)−2 (log m)−r/(r+1) , there is a C7 > 0 such that J4 (s)  s exp (1 + η)As−1/r (log (1/s))−1 − C7 ζ 2 m1/(r+1) (log m)−r/(r+1) m1/(r+1)−2 (log m)−r/(r+1)  .  (8.56)  114  Chapter 8. Partitions into Prime Powers Now, by definition of m, s m1/(r+1)−2 (log m)−r/(r+1)  = s m(m log m)r/(r+1) √  1  sm  s1/r  log (1/s)  .  As we similarly have s−1/r (log (1/s))−1  m1/(r+1) (log m)−r/(r+1) ,  there is a constant C8 > 0 such that J4 (s)  exp (1 + η − C8 ζ 2 )As−1/r (log (1/s))−1 s1/r log (1/s) exp (1 − C8 ζ 2 /2)As−1/r (log (1/s))−1 .  (8.57)  Virtually the same analysis works for J2 (s) giving a bound of a similar form. The results thus far have guaranteed us the existence of a constant C9 > 0, such that J1 , J2 , J4 , J5  exp (1 − C9 ζ 2 )As−1/r (log (1/s))−1 .  (8.58)  Hence by (8.45), we may select a new function δ1 (s) of the form C log log (1/s)/ log (1/s) (2δ(s) works), such that for s sufficiently small, exp (1 − δ1 (s))As−1/r (log (1/s))−1 < s  (1+ζ)m  A(x)e−sx dx  (8.59)  (1−ζ)m  Since A(x) is eventually increasing, we have exp (1 − δ1 (s))As−1/r (log (1/s))−1 < sA((1 + ζ)m)  (1+ζ)m  e−sx dx.  (1−ζ)m  Evaluating the integral leads to (eζsm − e−ζsm )A((1 + ζ)m) > exp (1 − δ1 (s))As−1/r (log (1/s))−1 + ms . (8.60) Substituting s in terms of m into the right-hand side of (8.60), we obtain an expression of the form exp Bm1/(r+1) (log m)−r/(r+1) 1 + O  log log m log m  . 115  Chapter 8. Partitions into Prime Powers Now, equation (8.46) yields ζB  1/(r+1) (log m)−r/(r+1)  eζsm − e−ζsm = e r+1 m  2ζB  1/(r+1) (log m)−r/(r+1)  1 − e− r+1 m  ,  and so by (8.60), A((1 + ζ)m) > exp Bm1/(r+1) (log m)−r/(r+1) 1 −  ζ +O r+1  log log m log m  . (8.61)  But (1 + ζ)m is a continuous function of m, which is ultimately increasing. Thus for all n sufficiently large, we may choose a unique value of s, and hence of m such that (1 + ζ)m = n. Substituting m= into (8.61), and observing that log m  n 1+ζ log n, we have the lemma.  Together, Lemmas 8.19 and 8.20 yield our main theorem: Theorem 8.21. For a fixed k ≥ 1, (k−1) log pP(r) (n)  =(r + 1) Γ ×  1+O  1 +2 ζ r  1 +1 r  (log log n)1+ log n  r/(r+1)  n1/(r+1) (log n)−r/(r+1) , as n → ∞.  116  Chapter 9  Sequences of Iterates The simplest classes of prime symmetric functions we have looked at are those of the form ek and sk . The s1 -sequences and s2 -sequences of n are ultimately periodic (in fact of period 1) for any n. It seems highly probable, but is not yet proven whether the sequences must terminate for any other functions of the form sk, . For the most part in this section we will narrow our focus to s1 , which for ease of notation we denote by s and study its corresponding s-sequences.  9.1  Density of Sets with Given Terminal Value  Lal [26] investigates the function s, which he writes as J. We summarize his observations which are based on accumulated empirical data via computer searches. We will also expand on his data via our own computer searches. Corresponding to each integer m, are two sets which we define as follows: Bm = {n ∈ N : s(n) = m, n = m}, and (i)  Bm = {n ∈ N : s (n) = m for some i ≥ 0}.  (9.1) (9.2)  That is, Bm is the set of all n > m such that s(n) = m, whereas Bm consists of all those integers n which include m in their s-sequence. The letter “B” is chosen in both instances to correspond to the word “branching.” We can think of the set Bm as a partially ordered set where n ≥ if s(i) (n) = for some i ≥ 0. With the exceptions of m = 0, 1, 2, 3, and 4, the sets Bm are infinite. The sets Bm are always finite with cardinality pP (m) if m is not prime, and pP (m) − 1 otherwise. For n ≥ 5, the s-sequence of n always terminates in a prime p. Thus we have   ˙ N = {1, 2, 3, 4} ∪  Bp  , (9.3) p≥5  117  Chapter 9. Sequences of Iterates where all the unions are disjoint, and the second union is of infinite sets taken over all primes p ≥ 5. We also have that Bm = {m} ∪  ˙  Bn  ,  (9.4)  n∈Bm  where again, all unions are disjoint. Lal observes that the set Bp appears to define a positive asymptotic density for each prime p ≥ 5. That is, if Bp (x) = #{n ∈ Bp : n ≤ x} is the counting function for Bp , then Bp (x)/x has a positive limit as x → ∞. Let us consider some empirical data that might motivate such a conjecture. The tables below are extensions of those provided by Lal. In the first two, the entries correspond to values of Bp (x) for different primes p, with x increasing in increments of 5000. In the second two, we evaluate the ratio Bp (x)/x. The algorithm we use to compute Bp (x) is found in the appendix on Maple algorithms.  118  Chapter 9. Sequences of Iterates  Table 4. Selected Values of Bp (x) x\p 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000  5 1426 2830 4188 5534 6846 8197 9547 10879 12217 13585 14879 16226 17599 18967 20288 21643 22976 24340 25655 27023  7 810 1605 2397 3202 3996 4812 5597 6380 7176 7964 8742 9509 10319 11049 11858 12677 13450 14243 15017 15753  11 327 649 941 1241 1556 1860 2156 2477 2785 3081 3367 3662 3938 4237 4512 4820 5126 5417 5736 6032  13 374 714 1049 1400 1737 2066 2421 2758 3086 3440 3767 4111 4453 4812 5138 5458 5819 6128 6483 6821  17 152 306 497 677 856 1027 1203 1360 1506 1667 1809 1964 2088 2243 2383 2535 2680 2826 2993 3146  19 184 377 573 780 976 1175 1358 1566 1755 1948 2157 2351 2542 2734 2927 3123 3297 3472 3669 3837  23 121 213 306 426 538 664 788 900 1012 1118 1251 1356 1473 1597 1707 1832 1937 2059 2175 2289  29 62 134 183 235 285 341 404 462 520 585 642 698 765 827 882 939 998 1063 1125 1194  31 86 172 241 316 392 472 552 622 703 776 850 927 998 1068 1128 1198 1279 1353 1413 1497  119  37 56 104 156 200 235 289 332 374 423 463 522 572 620 672 706 764 801 849 898 937  Chapter 9. Sequences of Iterates x\p 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000  41 51 88 139 180 221 260 287 331 368 396 441 469 503 537 577 609 647 682 708 747  43 70 113 170 221 289 346 398 453 520 588 643 705 757 804 869 921 983 1041 1092 1161  47 40 88 139 189 223 263 303 340 375 409 449 492 523 565 597 640 678 704 752 792  53 37 76 97 128 156 187 221 253 275 312 345 378 403 434 474 498 527 567 593 626  59 28 50 77 101 121 145 171 199 225 246 275 294 318 335 362 390 406 435 454 477  61 45 85 124 158 193 231 266 303 341 367 399 437 469 503 536 567 613 638 672 719  67 22 58 84 102 124 143 168 188 213 235 258 289 304 325 350 365 385 397 417 444  71 27 52 76 103 130 153 171 195 220 239 259 271 293 323 351 371 398 413 430 444  73 33 74 110 139 171 191 212 243 272 305 341 374 416 455 493 523 557 592 625 658  79 22 43 65 82 110 126 146 165 183 206 226 244 268 284 306 323 341 366 384 401  120  Chapter 9. Sequences of Iterates  Table 5. Selected Values of Bp (x)/x x\p 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000  5 .2852 .2830 .2792 .2767 .2738 .2732 .2728 .2720 .2715 .2717 .2705 .2704 .2708 .2710 .2705 .2705 .2703 .2704 .2701 .2702  7 .1620 .1605 .1598 .1601 .1598 .1604 .1599 .1595 .1595 .1593 .1590 .1585 .1588 .1578 .1581 .1585 .1582 .1583 .1581 .1575  11 .0654 .0649 .0627 .0621 .0622 .0620 .0616 .0619 .0619 .0616 .0612 .0610 .0606 .0605 .0602 .0603 .0603 .0602 .0604 .0603  13 .0748 .0714 .0699 .0700 .0695 .0689 .0692 .0690 .0686 .0688 .0685 .0685 .0685 .0687 .0685 .0682 .0685 .0681 .0682 .0682  17 .0304 .0306 .0331 .0339 .0342 .0342 .0344 .0340 .0335 .0333 .0329 .0327 .0321 .0320 .0318 .0317 .0315 .0314 .0315 .0315  19 .0368 .0377 .0382 .0390 .0390 .0392 .0388 .0392 .0390 .0390 .0392 .0392 .0391 .0391 .0390 .0390 .0388 .0386 .0386 .0384  23 .0242 .0213 .0204 .0213 .0215 .0221 .0225 .0225 .0225 .0224 .0227 .0226 .0227 .0228 .0228 .0229 .0228 .0229 .0229 .0229  29 .0124 .0134 .0122 .0118 .0114 .0114 .0115 .0116 .0116 .0117 .0117 .0116 .0118 .0118 .0118 .0117 .0117 .0118 .0118 .0119  31 .0172 .0172 .0161 .0158 .0157 .0157 .0158 .0156 .0156 .0155 .0155 .0155 .0154 .0153 .0150 .0150 .0150 .0150 .0149 .0150  121  37 .0112 .0104 .0104 .0100 .0094 .0096 .0095 .0094 .0094 .0093 .0095 .0095 .0095 .0096 .0094 .0096 .0094 .0094 .0095 .0094  Chapter 9. Sequences of Iterates  x\p 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000  41 .0102 .0088 .0093 .0090 .0088 .0087 .0082 .0083 .0082 .0079 .0080 .0078 .0077 .0077 .0077 .0076 .0076 .0076 .0075 .0075  43 .0140 .0113 .0113 .0111 .0116 .0115 .0114 .0113 .0116 .0118 .0117 .0118 .0116 .0115 .0116 .0115 .0116 .0116 .0115 .0116  47 .0080 .0088 .0093 .0095 .0089 .0088 .0087 .0085 .0083 .0082 .0082 .0082 .0080 .0081 .0080 .0080 .0080 .0078 .0079 .0079  53 .0074 .0076 .0065 .0064 .0062 .0062 .0063 .0063 .0061 .0062 .0063 .0063 .0062 .0062 .0063 .0062 .0062 .0063 .0062 .0063  59 .0056 .0050 .0051 .0051 .0048 .0048 .0049 .0050 .0050 .0049 .0050 .0049 .0049 .0049 .0048 .0049 .0048 .0048 .0048 .0048  61 .0090 .0085 .0083 .0079 .0077 .0077 .0076 .0076 .0076 .0073 .0073 .0073 .0072 .0072 .0071 .0071 .0071 .0071 .0071 .0072  67 .0044 .0058 .0056 .0051 .0050 .0048 .0048 .0047 .0047 .0047 .0047 .0048 .0047 .0046 .0046 .0046 .0045 .0044 .0044 .0044  71 .0054 .0052 .0051 .0052 .0052 .0051 .0049 .0049 .0049 .0048 .0047 .0045 .0045 .0047 .0047 .0046 .0047 .0046 .0045 .0044  73 .0066 .0074 .0073 .0070 .0068 .0064 .0061 .0061 .0060 .0061 .0062 .0062 .0064 .0065 .0066 .0065 .0066 .0066 .0066 .0066  Observe that for each value of p, the ratio Bp (x)/x appears to converge to a fixed positive value, or else generally decreases at an increasingly slow rate. Presently, the positivity, or even existence of the limit remains unresolved. To investigate this conjecture, it would, in the least, be necessary to determine if generally, the composite functions s(i) (n) behave “nicely” for i fixed, or at least suitably small relative to n. That is, given that s(n) is 2 often approximately 12πlogn n , is the average value of s(i) (n) asymptotic to the 2  i-th composition of 12πlogn n with itself? Empirical evidence leads to corresponding conjectures for each sk : Conjecture 9.1. Let k, n ∈ N, and suppose that sk (n) = n. If the set (i)  {m ∈ N : sk (m) = n, for some i ≥ 0} is infinite, then it has a positive asymptotic density. 122  79 .0044 .0043 .0043 .0041 .0044 .0042 .0042 .0041 .0041 .0041 .0041 .0041 .0041 .0041 .0041 .0040 .0040 .0041 .0040 .0040  Chapter 9. Sequences of Iterates Example 9.2. The number 39 satisfies s2 (39) = 39, and the set of numbers which terminate in 39 under iteration by s2 is infinite. If we denote this set by B, then we have the following table of values for B(x) and B(x)/x with x ranging in increments of 5000 up to 100000:  123  Chapter 9. Sequences of Iterates  Table 6. Iterations of s2 Terminating in 39 x 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000  B(x) 40 54 68 85 96 107 117 132 144 153 165 188 199 210 222 232 241 253 263 276  B(x)/x .00800 .00540 .00453 .00425 .00384 .00357 .00334 .00330 .00320 .00306 .00300 .00313 .00306 .00300 .00296 .00290 .00284 .00281 .00277 .00276  It should be noted however, that it is still well within the range of possibility that the sets under discussion do not have an asymptotic density. Any illuminating information on their distribution would be of value. The corresponding sets for the functions ek (n) would be much less easily understood for k ≥ 2, because ek -sequences tend to fluctuate unpredictably. This makes sense since the average value of ek (n) 1 x  ek (n) ∼ n≤x  ζ(k + 1)xk , (k + 1) log x  which grows significantly faster than x for k ≥ 2.  124  Chapter 9. Sequences of Iterates  9.2  Distribution of Products in Partitions into Primes  The problem of the asymptotic density of Bn remains tantalizingly open. The value of Bn (x) can be determined from the values of Bm (x) using the formula Bm (x). (9.5) Bn (x) = 1 + m∈Bn  Hence, a good understanding of the distribution of the elements of Bm would lead to information regarding the density of Bm . That is, we require an understanding of the distribution of the products of parts in partitions into primes. We studied this problem in Section 5.2, when we looked at bk (x, y), however, the value of y was dependent on x. We wish to understand b1 (x, y) for a fixed y. We drop the subscript and write b(x, y) for b1 (x, y). We have the relation Bm (x) =  b(x, m) − b(x, m − 1), if m is not prime or 4, b(x, m) − b(x, m − 1) − 1, if m is prime or 4.  Hansraj Gupta [18] shows that the largest element of s(−1) [{m}] for m ≥ 2 is given by t · 3 m/3 , where t = 1, 4/3, or 2 according as m ≡ 0, 1 or 2 (mod 3) respectively. He goes on to show that corresponding to any prime p ≥ 5, the largest integer hr = hr (p) such that s(r) (hr ) = p, but s(r−1) (hr ) = p is given by hr = 3hr−1 /3 ; with h1 = 4 · 3(p−4)/3 or 2 · 3(p−2)/3 , according as p ≡ 1 or 2 (mod 3). The similar question as to the least element of Bm could at best be answered approximately, and depends on the Goldbach conjecture. Thus the set Bm has a very large range relative to m. Empirical evidence would suggest however that x needn’t be as high as O(3m/3 ) for Bm (x) to capture most of Bm . A possible line of attack on the function Bm (x) could involve exponential sums and the circle method. With the customary notation e(α) = e2πiα , for 0 ≤ α ≤ 1, let f (α) =  e(αs(n)). n≤x  Then  1  #{n ≤ x : s(n) = m} =  f (α)e(−αm) dα. 0  125  Chapter 9. Sequences of Iterates Ideally, we would proceed by estimating f (α) when α = a/q, a rational number in lowest terms. Clearly f (0) = f (1) = x . In Chapter 7 we bounded the absolute value of sums of the form f (a/q) using Perron’s formula. In fact, we did so to far more general sums. We were able to do this because the additive properties of the divisor functions in question enabled us to express corresponding Dirichlet series in terms of L-functions. The problem here however arises from the fact that we are trying not simply to bound an integral from above, but approximate its actual value. This poses difficulties even in the case when α = 1/2. By Perron’s formula, we have the heuristic c+iT 1 1 + 2−s ζ(2s) xs f (1/2) ≈ ds, 2πi c−iT 1 − 2−s ζ(s) s for suitably chosen T > 0 and c > 1. Of course the function in the integrand is analytic in a region that extends beyond the line σ = 1, but even assuming the Riemann Hypothesis, it is not clear what the value of the integral should be. In case α = 1/3, after some work, we obtain the heuristic f (1/3) ≈ 1 2πi  c+iT c−iT   1 exp  (1 − 3−s )3/2    ∞ pj  √  (ζ pj − ζ )p−js /j L(s, χ)i p  j=2  3/2  ζ(s)−1/2  xs ds, s  where ζ = e(1/3), and χ is the non-principal character modulo 3. Assuming the Generalized Riemann Hypothesis, the function in the integrand can be analytically continued to the region in the plane {s : σ > 1/2}\{s : σ ≤ 1, t = 0}. Trying to integrate around the branch cut proves problematic. Furthermore, in general, it is not clear what size the minor arcs should be in application of the circle method. This will in turn affect the values of c and T chosen for a given α = a/q. The problems and complexity increase with the value of the denominator q. To conclude, if the circle method is to be used to estimate Bm (x), then it may not be practicable to do so in conjunction with Perron’s formula.  9.3  The Number of Iterations of s until termination  Definition 9.3. Suppose f : N0 → N0 is an arithmetic function. Then we define the function tf : N0 → N∞ by letting tf (n) be the number of distinct elements in the f -sequence of n. The value of tf is infinity if the f -sequence never becomes periodic. 126  Chapter 9. Sequences of Iterates If f = s, we let t = tf . For k > 1, the ek -sequences tend to be rather erratic. This is due to the fact that when n has few divisors relative to k, then ek (n) tends to be very large relative to n. This lack of stability makes it difficult to predict the behaviour of the sequence of iterates, and hence of the function tf . None the less, the case k = 1 proves to provide a wealth of fascinating material for study, and at least empirically seems to behave with a high degree of regularity. Clearly t(n) > 0 for all n, and t(n) = 1 if and only if n is 0, a prime, or 4. A trivial upper-bound for t(n) is found as follows. Proposition 9.4. For all n ≥ 5, t(n) ≤ log(n)/ log(2) + 1. Proof. It is straightforward to see that if n is not a prime, then s(n) ≤ n/2 + 2. Thus n 2 2 + k−1 + k−2 + · · · + 2, k 2 2 2 n < k + 4. 2  s(k) (n) ≤  providing s(i) (n) is never prime for 0 ≤ i ≤ k − 1. This sequence must terminate at a prime p ≥ 5. Thus the sequence can be iterated at most k = log2 (n) times before terminating at a prime. That is, t(n) ≤ log2 (n) + 1 as claimed. Observe that the bound s(n) ≤ n/2 + 2 is only attained when n = 2p, for p prime, apart from the case when n itself is prime. Apart from these cases, we have that s(n) ≤ n/3 + 3. If n = 2p, then s(n) = p + 2, and so for p > 2, we can not have s(n) = 2p1 for some other prime p1 . This observation will allow us to effect a slight improvement in the constant 1/ log 2. Lemma 9.5. Let k ≥ 0, n ≥ 2. If s(i) (n) is not prime for any i, 0 ≤ i < k, then n 22 s(k) (n) < k/2 + . k/2 5 2 ·3 Proof. This can be verified numerically for n = 2, 3, 4, 5. For n > 5, we have seen that n s(n) ≤ + 2, 2 127  Chapter 9. Sequences of Iterates when n is not prime, so by the preceding remarks, n 2 + +3 2·3 3 2 3 n + + +2 s(3) (n) ≤ 2 2 ·3 2·3 2 2 3 n 2 (4) + s (n) ≤ 2 2 + + + 3, 2 2 ·3 2·3 2·3 3  s(2) (n) ≤  and in general, (2k−1)  s  n (n) ≤ k k−1 + 2 2 ·3  s(2k) (n) ≤  2k  n 2 + k 3 ·3  k−1  i=0 k−1 i=0  2i  k−2  1 3 + 2i · 3i 2 1 +3 · 3i  i=0 k−1 i=0  2i  1 n 7 < k k−1 + 2i · 3i 2 2 ·3 1 n 11 < k k+ i ·3 3 2 ·3  ∞ i=0  ∞ i=0  1 6i  1 . 6i  Combining these we have that s(k) (n) <  2  k/2  n ·3  k/2  +  22 . 5  Proposition 9.6. If n ≥ 2, then t(n) <  2 log n 2 log 5 + . log 6 log 6  Proof. This can be verified numerically for n = 2, 3, 4, 5. For n > 5, write t(n) = k + 1. This means s(k) (n) = p ∈ P. By the lemma, we have 5 ≤ p = s(k) (n) <  2  k/2  and so 2  k/2  ·3  k/2  n ·3  k/2  +  22 , 5  5 < n. 3  But 2 so  k/2  ·3  k/2  ≥ 6k/2  2 , 3  5 6k/2 < √ n. 6 128  Chapter 9. Sequences of Iterates This implies that √ 2 log (5/ 6) +1 log 6  2 log n k+1< + log 6  =  2 log n 2 log 5 + , log 6 log 6  which is the statement of the proposition. The improvement of the multiplicative constant is somewhat slight, from 1/ log 2 ≈ 1.44270, to 2/ log 6 ≈ 1.11622.  9.3.1  The Average order of t(n)  The following formulae are useful: Bn (x) = 1 +  Bm (x) = 1 + m∈Bn  Bm (x).  (9.6)  m∈Bn  Proposition 9.7. The average order of t(n) has the following expressions: t(n) = 2 + n≤x  Bn (x) = 1 + x + 2≤n≤x  Bm (x) 2≤n≤x m∈Bn  Proof. The second equation follows from the first, and the first equation in (9.6). To prove the first, first note that t(1) = 2. The sum t(n) counts (i) each n, 2 ≤ n ≤ x once for each m ≤ x satisfying s (m) = n for some i ≥ 0. Simply combine these two facts. Though we have shown that t(n) log x, it is no surprise that this does not seem to be optimal on average. Empirical results appear to indicate that t(n) x log log x. n≤x  Indeed, consider the following table of values:  129  Chapter 9. Sequences of Iterates  Table 7. Average Order of t(n) x 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000  n≤x t(n)  1 n≤x t(n) x log x  1 n≤x t(n) x log log x  19571 40471 61620 83104 104673 126593 148545 170568 192657 215000 237041 259322  .4595645436 .4394082995 .4272133008 .4195693666 .4134563567 .4093302983 .4056294504 .4024107756 .3995799640 .3974203434 .3948512538 .3928371307  1.827283521 1.822749691 1.814962097 1.812213183 1.808472967 1.808719966 1.807668137 1.806453766 1.805230307 1.805678899 1.803168591 1.802284432  There is a heuristic argument that lends credence to the possibility that t(n) ∼ Cx log log x n≤x  for some constant C > 0. In Section 5.2, we saw that s(n) ≤ xα a positive proportion of the time on the interval [1, x]. Iterating the function xα j j j times gives us xα . Setting xα ≤ c for some constant c, we see that the minimum required value of j is roughly log log x. At present, unfortunately, we can do no better than argue heuristically and provide supporting empirical evidence.  9.4  Iterating s + b  The main goal of this section is to study the sequences formed by iterating the function s+b for positive integral values of b. We begin with a definition. Definition 9.8. Let p1 , . . . , pr be primes such that p1 ≤ . . . ≤ pr , and let n = p1 · · · pr . We say that n is first sk -defective of order r if n is sk defective and if whenever primes q1 , . . . , qr satisfying q1 ≤ . . . ≤ qr , are such that q1 · · · qr is sk -defective and qi ≤ pi for each i, then qi = pi for each i. Example 9.9. 42 = 2 · 3 · 7 is first s2 -defective of order 3.  130  Chapter 9. Sequences of Iterates For a given k, and fixed r, there are only finitely many first sk -defective numbers of order r. Let r(k) be defined as in Lemma 2.14. If r < k, or if r ≥ r(k) then 2r is the only first sk -defective number of order r. If r = k, there are no such numbers, since no such number is sk -defective. If n = p1 · · · pr is sk -defective, then there exists an n = p1 · · · pr which is first sk -defective of order r, and such that pi ≤ pi for each i. We make use of the fact that there are only finitely many such numbers for each r in the following lemma. Lemma 9.10. Let k ∈ N, and let M > 0. Then there exists an N ∈ N such that if n ≥ N and n is sk -defective, then n − sk (n) > M . Proof. Let n = p1 · · · pr . The inequality n > sk (n) + M holds if and only if 1> 1≤i1 <...<ir−k ≤r  1 M . + pi1 · · · pir−k n  This is implied by 1>  r 1 M + r. r−k k 2 2  (9.7)  There is an R such that r ≥ R implies that the inequality (9.7) holds. On the other hand, if r < k, then we need only ensure N > M . Thus we may assume k < r < R, for which there are only finitely many possible values of r. Fix r in this range. For the given r, there is a finite nonempty set of first sk -defective numbers of order r. Let n = p1 · · · pr , where p1 ≤ . . . ≤ pr , be one such number. Then since sk (n ) < n , we have that 1> 1≤i1 <...<ir−k ≤r  1 = α. pi1 · · · pir−k  Now if n = p1 · · · pr , where p1 ≤ . . . ≤ pr and pi ≥ pi for i = 1, . . . , r, then 1>α ≥ 1≤i1 <...<ir−k ≤r  1 . pi1 · · · pir−k  131  Chapter 9. Sequences of Iterates This implies that  1≤i1 <...<ir−k ≤r  M 1 M + ≤α+ . pi1 · · · pir−k n n  If we choose n large enough such that M 1−α < , n 2 then we have that n − sk (n) < M as desired. There are only finitely many r for which we must apply this analysis. For each such r, there are only finitely many first sk -defective numbers of order r, and as already stated, for any sk -defective number n = p1 · · · pr , there is a first sk -defective number n = p1 · · · pr of order r such that pi ≤ pi . This proves the lemma. The following corollary is a companion to Corollary 4.3, and is an immediate consequence of the preceding lemma. Corollary 9.11. Let k ∈ N, and let d > 0. The equation n − sk (n) = d has at most finitely many solutions. Now let us look at some new prime symmetric functions. For b > 0, let f = s + b. In [11], the case when b = 1 was studied It was shown that repeated iteration of f eventually terminates in the cycle 7, 8, 7, 8, ..., except when n < 7, in which case the sequence terminates in 1 or 6. We will show that for any b > 0, the function f will ultimately terminate under repeated iteration in an f -cycle, or an f -perfect number. Furthermore, we will show that there are only finitely many such f -cycles. For convenience, we will consider an f -perfect number to be an f -cycle of length 1. Theorem 9.12. Let b ∈ N and let f = s + b. If n ∈ N, then the f -sequence of n terminates in an f -cycle. Furthermore, there are only finitely many f -cycles. Proof. We first need to show that the f -sequence of n must terminate in an f -cycle. If not, then limi→∞ f (i) (n) = ∞. Let p be the least prime not dividing b. If r > p, then elements of the sequence r, r + b, r + 2b, . . . , r + (p − 1)b can not all be prime since one must be divisible by p but strictly greater than p. By Lemma 9.10, there is an N such that if n > N is not prime, then n > f (n) + 2pb.  132  Chapter 9. Sequences of Iterates When we iterate by f , all strictly increasing subsequences of consecutive terms beginning with q ≥ N are of the form q, q + b, . . . , q + ib, where q, q + b, . . . , q + (i − 1)b are prime, q + ib is not prime, and i ≤ p − 1. In this case, we have that f (i+1) (q) = f (q + ib) < q + ib − 2pb < q − pb. If q > max{N + pb, f (1) + pb, f (2) + pb, . . . , f (N ) + pb}, then f (j) (q) can never ascend above q + pb for any j. Thus the f -sequence of n, must terminate in an f -cycle, since in order for limi→∞ f (i) (n) = ∞, it must contain such primes q. Showing there are only finitely many such cycles is done similarly to the first part of the proof. If there were infinitely many, we could choose arbitrarily large least elements of such cycles. Clearly, we can choose N large enough so that (1), if n > N is the least element of an f -cycle, then n is prime, and (2), if m > N is not prime, then m > f (m)+pb. Let n > N be the least element of an f -cycle. Then n is prime, and there is a least i < p such that n + ib is not prime. Then f (i+1) (n) = f (n + ib) < n + ib − pb < n. This contradicts that n is the least element of an f -cycle, and the Theorem is proved. We will illustrate this Theorem with the case when b = 2. Example 9.13. Let f = s + 2. Then for n ∈ N, the f -sequence of n terminates in the f -cycle {8}. Indeed it is easily verified that this is so for n = 1, 2, . . . , 35. It is also readily seen that for n larger, if n is not prime, then f (n) + 4 < n. If there is another f -cycle, it must have a least element q > 35 which is prime. However, one of q +2, and q +4 can not be prime. In either case, if we apply f , we get a contradiction to q being the least element. Below is a table of complete lists of f -cycles, where f = s + b, for b = 1, . . . , 10.  133  Chapter 9. Sequences of Iterates  Table 8. (s + b)-Cycles b 1 2 3 4 5 6 7 8 9 10  (s + b)-cycles {1},{6},{7,8} {8} {9},{10} {11,15,12}, {13,17,21,14} {12},{13,18},{14} {14,15} {15} {16} {17,26,24,18}, {22} {18}, {19,29,39,26,25,20}  134  Bibliography [1] Alladi, K., and Erdos, P., On an additive arithmetic function, Pacific J. Math., 71 (2), (1977), 275-294. [2] Apostol, T., Introduction to analytic number theory, Springer, New York-Berlin-Heidelberg-Hong Kong-London-Milan-Paris-Tokyo, 1976. [3] Bateman, P. T. and Erdos, P., Partitions into primes, Publ. Math. (Debrecen), 4 (1956), 198–200. [4] Bateman, P. T. and Erdos, P., Monotonicity of partition functions, Mathematika, 3 (5), (1956), 1-14. [5] Bateman, P., and Diamond, H. G., Analytic Number Theory - An Introductory Course, World Scientific Publishing Co. Pte. Ltd., 2004. [6] Butson, A. T., Generalized Hadamard Matrices, Proc. Am. Math. Soc., 13, (1962), 894-898. [7] Butson, A. T., Relations among generalized Hadamard matrices, relative difference sets, and maximal length linear recurring sequences, Canad. J. Math., 15, (1963), 42-48. [8] Davenport, H., Multiplicative Number Theory, Markham Publishing Company, Chicago, 1966. [9] de Bruijn, N. G., On the number of positive integers ≤ x and free of prime factors > y, Nederl. Akad. Wetensch. Proc. Ser. A 54 (1951), 50-60. [10] Burton, D. M., Elementary Number Theory, Allan and Bacon, Inc. Boston-London-Sydney, 1976. [11] Cadogan, C. C. and Callendar, B. A., A problem on positive integers New Zealand Math. Mag. 11 (1974), 87-91, 94. [12] Chandran, V. R., On generalized unitary perfect numbers, Math. Student, 61 (1992), 54-56. 135  Bibliography [13] Cohen, G. L. and te Riele, H. J. J., Iterating the sum of divisors function, Experiment. Math., 5 (1996), 91-100. [14] Davenport, H., Multiplicative Number Theory, Markham Publishing Company, Chicago, 1966. [15] Dunham, W., Euler The Master of Us All, The Mathematical Association of America, (1999). [16] Erd˝os, P., and Pomerance, C., On the largest prime factors of n and n + 1, Aequationnes Math., 17 (1978), 311-321. [17] Grosswald, E., Partitions into prime powers, Michigan Math. J., 7 (1960), 97122. [18] Gupta, H., Products of parts in partitions into primes, Res. Bull. Panjab. Univ. (N.S.), 21 (1970), 251-253. [19] Hardy, G. H. and Ramanujan, S., Asymptotic formulae for the distribution of integers of various types, Proc. London Math. Soc., Ser. 2, 16 (1916), 112-132. [20] Hardy, B. E. and Subbarao, M. V., On hyperperfect numbers, Congr. Numer., 42 (1984), 183-198. [21] Hildebrand, A., On the number of positive integers ≤ x and free of prime factors > y, J. Number Theory 22 (1986), 289-307. [22] Hildebrand, A. and Tenenbaum, G., Integers without large prime factors, J. Theorie des Nombres de Bordeaux, 5 (1993), 411-484. [23] Hunsucker, J. L. and Pomerance, C., There are no odd super perfect numbers less than 7 × 1024 , Indian J. Math. 17 (1975), 107-120. [24] Kerawala, S. M., A note on the orders of two arithmetic functions F (n, k) and F ∗ (n, k), J. Natur. Sci. and Math. 9 (1969), 105-107. (d)  [25] Kerawala, S. M., On the asymptotic values of ln pA (n) and ln pA (n) with A as the set of primes, J. Natur. Sci. and Math. 9 (1969), 209216. [26] Lal, M., Iterates of a Number-Theoretic Function, Mathematics of Computation 23 (1968), 181-183.  136  Bibliography [27] LeVan, Marijo O., On the order of F (x, r), J. Natur. Sci. and Math. 10 (1970), 163–166. [28] Loweke, G. P., The Lore of Prime Numbers, Vantage Press, New YorkWashington-Atlanta-Los Angeles-Chicago, 1982. [29] McCranie, J. S., A study of hyperperfect numbers, J. of Integer Seq., 3 (2000), 153-157. [30] Minoli, D., Issues in nonlinear hyperperfect numbers, Mathematics of Computation, 34 (1980), 639-645. [31] Mitsui, T., On the partitions of a number into the powers of prime numbers, J. Math. Soc. Jpn., 9 (1957), 428-447. [32] Montgomery, H. L., and Vaughn, R. C., Multiplicative Number Theory 1: Classical Theory, Cambridge University Press, 2006. [33] Nathanson, M., Elementary Methods in Number Theory, Springer, New York-Berlin-Heidelberg-Hong Kong-London-Milan-Paris-Tokyo, 2000. [34] Niven, I., Zuckerman, H., Montgomery, H., An Introduction to the Theory of Numbers, John Wiley and Sons, Inc., New York-ChichesterBrisbane-Toronto-Singapore, 1991. [35] Pomerance, C., Multiply perfect numbers, Mersenne primes and effective computability, Math. Ann. 226 (1977), 195-206. [36] Richard, L. B., Asymptotic relations for partitions, J. Number Theory, 7 (1975), 389-405. [37] Richard, L. B., Asymptotic results for partitions (I) and the distribution of certain integers, J. Number Theory, 8 (1976), 372-389. [38] Richard, L. B., Asymptotic results for partitions (II) and a conjecture of Bateman and Erd˝ os, J. Number Theory, 8 (1976), 390-396. [39] Richard, L. B., Asymptotic relations for partitions, Trans. Amer. Math. Soc., 219 (1976), 379-385. [40] Suryanarayana, D., Superperfect Numbers, Elem. Math., 24 (1967), 1617. [41] te Riele, H. J. J., Hyperperfect numbers with three different prime factors, Mathematics of Computation, 36 (1981), 297-298. 137  Bibliography [42] Tattersall, J. J., Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999. [43] Tur´an, D., On a theorem of Hardy and Ramanujan, J. London Math. Soc., 9 (1934), 274-276. [44] Eric W. Weisstein. “Newton-Girard Formulas.” From MathWorld– A Wolfram Web Resource. http://mathworld.wolfram.com/NewtonGirardFormulas.html [45] Eric W. Weisstein et al. “Symmetric Polynomial.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/SymmetricPolynomial.html [46] Woodford, R., A Variation on Perfect Numbers, Integers: Electronic Journal of Combinatorial Number Theory, 4 (2004), A11. [47] Woodford, R., Prime Symmetric Divisor Functions, Masters Thesis: University of British Columbia, Department of Mathematics (2005). [48] Woodford, R., On partitions into powers of primes and their difference functions, Accepted for publication in the Canadian Journal of Mathematics in 2006. [49] Woodford, R., Bounds for the Eventual Positivity of Difference Functions of Partitions into Prime Powers, Journal of Integer Sequences, 10 (2007), 07.1.3. [50] Woodford, R., On the Average Orders of a Class of Divisor Functions, Integers: Electronic Journal of Combinatorial Number Theory, 7 (2007), A13.  138  Appendix A  Maple Algorithms Computer searches and much of the experimentation for this exposition was done using Maple. In this section I include some of the algorithms for computing some of the prime symmetric functions. First note that the with(linalg):, with(numtheory):, with(combinat): and with(LinearAlgebra): commands should be invoked at the beginning of the worksheet. The omega procedure with input n returns the value of ω(n), that is, the number of distinct prime factors of n. omega:=proc(n) om:=Dimension(Vector(ifactors(n)[2]))/2: return(om): end proc: The pvect procedure with input n returns a vector of length Ω(n) whose entries are the prime factors of n with repetition. pvect:=proc(n) c:=0: v:=array(1..1,1..bigomega(n)): k:=omega(n): for i from 1 to k do for j from 1 to ifactors(n)[2][i][2] do c:=c+1: v[1,c]:=ifactors(n)[2][i][1]: od:od: return(v): end proc: To calculate ek (n), use the following: e:=proc(k,n) v:=ifactors(n)[2]: r:=omega(n): 139  Appendix A. Maple Algorithms s:=sum(v[j][2]*v[j][1]^k,j=1..r); return(s); end proc: So, for example, if we wished to calculate e3 (1444), we would type e(3,1444); Maple returns the correct value of 13734. To compute the function sk at n, use the following: s:=proc(k,n): b:=bigomega(n): v:=pvect(n): a:=choose(b,k); sk:=sum(product(v[1,a[i][j]],j=1..k),i=1..binomial(b,k)); return(sk); end proc: For example, to compute s5 (174960), we would type s(5,174960); Hitting return yields the correct output of 134942. The algorithm we use to compute the final value of the sk -sequence of n is as follows: term:=proc(k,n): d:=n: while d<>s(k,d) do d:=s(k,d): od: return(d); end proc: For instance, typing term(1,16) will yield an output of 5. We use the term procedure to compute Bp (x) as follows. You must first input values for p and x. Use only integer values for x. y:=0: for m from 1 to x do tt:=term(1,m): if tt=p then y:= y+1: fi: od; y; 140  Appendix A. Maple Algorithms To compute the number tsk (n) of elements in the sk -sequence of n, use the following variant of the term procedure: t:=proc(k,n): d:=n: te:=1: while d<>s(k,d) do d:=s(k,d): te:=te+1: od: return(te); end proc: Thus, t(1,16) will yield an output of 4.  141  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 24 10
United States 13 2
United Kingdom 4 0
India 3 0
Finland 3 1
Canada 3 0
Germany 2 11
Thailand 2 0
Poland 1 0
Portugal 1 0
Russia 1 0
France 1 0
City Views Downloads
Beijing 19 0
Unknown 16 16
Mountain View 4 1
Shenzhen 4 10
Kolkata 3 0
Jacksonville 2 0
Taunton 2 0
Ashburn 2 0
Ottawa 1 0
Columbus 1 0
Victoria 1 0
Hangzhou 1 0
Bradford 1 0

{[{ 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-0066490/manifest

Comment

Related Items