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 func- tions 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Divisor Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Perfect Numbers, Variations on Perfect Numbers, and Aliquot Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Prime Symmetric Divisor Functions . . . . . . . . . . . . . . 4 2.1 Elementary Prime Symmetric Divisor Functions . . . . . . . 5 2.2 Basic Properties of the Elementary Prime Symmetric Func- tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 The Second Elementary Prime Symmetric Function . . . . 13 3.1 Ω(n) = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Ω(n) = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Ω(n) = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Inverse Problems . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Higher Elementary Prime Symmetric Functions . . . . . . 22 4.1 The Hunt for s3-cycles . . . . . . . . . . . . . . . . . . . . . 25 iii Table of Contents 5 The Power Prime Symmetric Divisor Functions . . . . . . 30 5.1 The Average Order of ek . . . . . . . . . . . . . . . . . . . . 32 5.2 A Statistical Look at ek . . . . . . . . . . . . . . . . . . . . . 36 6 The Average Order of sk,` . . . . . . . . . . . . . . . . . . . . 47 7 Modular Distribution of Prime Symmetric Functions . . . 58 7.1 Perron’s Formula . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2 Bounding L(s, χ) and ζ(s) . . . . . . . . . . . . . . . . . . . 61 7.3 Additive Prime Symmetric Functions . . . . . . . . . . . . . 65 7.4 The Distribution of sk Modulo q . . . . . . . . . . . . . . . . 70 7.4.1 The Dirichlet Series . . . . . . . . . . . . . . . . . . . 71 7.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.5.1 s2 modulo 3 . . . . . . . . . . . . . . . . . . . . . . . 77 7.5.2 s3 modulo 2 . . . . . . . . . . . . . . . . . . . . . . . 79 7.5.3 sk modulo a prime q . . . . . . . . . . . . . . . . . . 81 8 Partitions into Prime Powers . . . . . . . . . . . . . . . . . . 82 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.2 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.3 Asymptotic Formulae . . . . . . . . . . . . . . . . . . . . . . 98 8.3.1 Asymptotic Formula for the Generating Function . . 99 8.3.2 Bounding from Above . . . . . . . . . . . . . . . . . . 107 8.3.3 Bounding from Below . . . . . . . . . . . . . . . . . . 109 9 Sequences of Iterates . . . . . . . . . . . . . . . . . . . . . . . 117 9.1 Density of Sets with Given Terminal Value . . . . . . . . . . 117 9.2 Distribution of Products in Partitions into Primes . . . . . . 125 9.3 The Number of Iterations of s until termination . . . . . . . 126 9.3.1 The Average order of t(n) . . . . . . . . . . . . . . . 129 9.4 Iterating s+ b . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Appendices A Maple Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 139 iv List of Tables Table 1. Initial values of r(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Table 2. s∗k-perfect numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Table 3. s3(n) modulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Table 4. Selected values ofBp(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Table 5. Selected values ofBp(x)/x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Table 6. Iterations of s2 terminating in 39 . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Table 7. Average order of t(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Table 8. (s+b)-cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 v Glossary of Fundamental Notation N0, N∞, N0,∞, P 4 sk 4 sk,` 4 ek 4 r(k) 9 rf , rk,`, rk 16 Ek(n, r) 22 pA(n) 37 p (k) A (n) 37, 82 P (n), bk(x, y),Ψ(x, y) 38 Bm,Bm 117 tf 126 vi Acknowledgements Two faculty members at UBC have given me the invaluable insight, direc- tion, encouragement and support that has made this possible. For these things it is my privilege to thank and acknowledge my supervisor Dr. Iz- abella Laba, and Dr. Greg Martin, who is also on my supervisory committee. I also wish to express my gratitude to the Natural Sciences and Engineer- ing 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 iterat- ing 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 Jour- nal 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ős ([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ős 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. Chap- ters 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 σ(n) = ∑ d|n d has been thoroughly studied for centuries. The first, most natural general- ization of σ are the functions σα defined by σα(n) = ∑ d|n dα, 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,∑ n≤x d(n) = x log x+ (2C − 1)x+O(√x), where C is Euler’s constant. Also,∑ n≤x σ(n) = pi2 12 x2 +O(x log x). Furthermore, for α > 0, and α 6= 1, we have∑ n≤x σα(n) = ζ(α+ 1) α+ 1 xα+1 +O(xβ), 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 func- tions: the prime symmetric divisor functions. These functions are not mul- tiplicative in general. The following notions, those of perfect numbers, and aliquot sequences, and some of their generalizations based on the usual mul- tiplicative 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−2q}, and hence their sum is: σ∗(n) = 1 + 2 + · · ·+ 2p−1 + q + 2q + · · ·+ 2p−2q = 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−1q, 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−1m, where 2k−1||n, and so k ≥ 2, and m is odd. Since σ(n) = 2n, we have: 2n = 2km = σ(2k−1m) = (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|(2k−1) 1<d<2k−1 d, 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. The sequence {σ∗(k)(n)}∞k=0, or the sequence {σ∗(k)(n)}tk=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 6= σ∗(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 kth 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 func- tion 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 sk,`(n) = ∑ 1≤i1<...<ik≤r (pi1 · · · pik)`. 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 Sn(x) = r∏ i=1 (1 + pix). 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 p− 1 ) pp−1 = pp. 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 ( α k ) = pα−k. (2.1) 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 α 6= k, and β 6= k. Proof. Suppose α = k. Then sk(pαqβ) = pαqβ is equivalent to pk + ( k k − 1 ) pk−1 ( β 1 ) q + · · ·+ ( k 1 ) p ( β k − 1 ) qk−1 + ( β k ) qk = pkqβ . 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 = 2 4 · 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 ) pk + ( α k − 1 ) pk−1q = pαq. This implies that ( α k ) p+ ( α k − 1 ) q = pα−k+1q, or ( α α− k ) p+ ( α α− k + 1 ) q = pα−k+1q. Letting ` = α− k + 1, we have( α `− 1 ) p+ ( α ` ) q = p`q. Since p > q, we have that( α `− 1 ) p+ ( α ` ) q < ( α `− 1 ) p+ ( α ` ) p = ( α+ 1 ` ) p. If we show that the assumption in (i) implies that( α+ 1 ` ) ≤ p`−1q, (2.2) then we are done. But( α+ 1 ` ) = ( α+ 1 ` )( α `− 1 ) · · · ( α− `+ 3 2 )( α− `+ 2 1 ) . There are ` terms in this product. The first term α+1` satisfies α+1 ` ≤ q by assumption. Since α `− 1 ≤ α− 1 `− 2 ≤ · · · ≤ α− `+ 2 1 ≤ p, 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) < ( α+ 1 ` ) q, where ` 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α11 · · · pαrr , then sk(n) = ∑ i1+···+ir=k i1, ...,ir≥0 ( α1 i1 ) · · · ( αr ir ) pi11 · · · pirr . Proposition 2.12. For nonnegative integers m and n, the function sk sat- isfies sk(mn) = k∑ i=0 sk−i(m)si(n). 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 sk(mn) = ∑ {r1,...,rk}⊂S r1 · · · rk. 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 t− k ) < 2t−k, which implies∑ 1 pi1 · · · pit−k ≤ ( t t− k ) 1 2t−k < 1, 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 ) 2k ≥ 2r(k)−1−k+k = 2r(k)−1 = n. 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 ≤ (rk). 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 ) < 2t−1−k. Then 2 ( t− 1 k ) < 2t−k. Since t > 2k, we have t < 2(t− k), and so( t k ) = t(t− 1) · · · (t− k + 1) k! < 2(t− 1)(t− 2) · · · (t− k) k! = 2 ( t− 1 k ) . 10 Chapter 2. Prime Symmetric Divisor Functions Hence ( t k ) < 2 ( t− 1 k ) < 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 r(k) 1 3 2 6 3 10 4 14 5 19 6 23 7 27 8 31 9 36 10 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√ 2pix(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 )( r k ) . (2.6) A simple induction can be used to show that ( 5k k ) < 24k for all k ∈ N, and hence that r(k) ≤ 5k. Thus, r(k) k. 11 Chapter 2. Prime Symmetric Divisor Functions The inequalities (2.6) are equivalent to 1√ 2pi rr+ 1 2 kk+ 1 2 (r − k)r−k+ 12 ( 1 +O ( 1 k )) < 2r−k ≤ 2 ( r − k r ) 1√ 2pi rr+ 1 2 kk+ 1 2 (r − k)r−k+ 12 ( 1 +O ( 1 k )) . (2.7) Write ck = r(k)/k = r/k. Clearly 2 < ck ≤ 5. Now (2.7) becomes 1√ 2pi k− 1 2 c ckk+ 1 2 k (ck − 1)(ck−1)k+ 12 ( 1 +O ( 1 k )) < 2(ck−1)k ≤ 2 ( ck − 1 ck ) 1√ 2pi k− 1 2 c ckk+ 1 2 k (ck − 1)(ck−1)k+ 12 ( 1 +O ( 1 k )) . (2.8) Taking logarithms and dividing through by k, we see that (2.8) is equivalent to (ck − 1) log 2 = ck log ck − (ck − 1) log (ck − 1) +O ( log k k ) . (2.9) 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) 6= 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 elemen- tary prime symmetric function s1 are easily characterized. The s1-perfect numbers are the primes and 4, the latter being the only s∗1-perfect num- ber. 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 num- bers 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 18 s2−→ 21 s2−→ 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 p1 · · · ps + 6 s∑ i=1 1 p1 · · · p̂i · · · ps + ∑ 1≤i<j≤s 1 p1 · · · p̂i · · · p̂j · · · ps < 8, 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/pipj . Since pi ≥ 2, this expression is implied by: 16 2s + 6s 2s−1 + s(s− 1) 2 1 2s−2 < 8, 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 8 s2−→ 12 s2−→ 16 s2−→ 24 s2−→ 30 s2−→ 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 rsk = 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(2a3b) = 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(2a3b5c7d), for some a, b, c, and d ≥ 0. In general, s2(2a3b5c7d) = 4 ( a 2 ) + 9 ( b 2 ) + 25 ( c 2 ) + 49 ( d 2 ) + 6 ( a 1 )( b 1 ) + 10 ( a 1 )( c 1 ) + 14 ( a 1 )( d 1 ) + 15 ( b 1 )( c 1 ) + 21 ( b 1 )( d 1 ) + 35 ( c 1 )( d 1 ) = 1 2 [ (2a+ 3b+ 5c+ 7d)2 − (4a+ 9b+ 25c+ 49d)] 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 equiva- lent 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)⋃ c=0 IR(c, d) = [R2 − 3R− 10cR(d)− 28d,R2 − 2R− 35d]. 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 ⋂2 d=0 IR(d). Clearly R( ⋂2 d=0 IR(d)) = R2 − 2R− 70. We now wish to find an upper bound for L( ⋂2 d=0 IR(d)). From the above inequality, we have that L(IR(d)) = R2 − 3R− 10cR(d)− 28d < R2 − 5R− 14d+ 30. Thus L ( 2⋂ d=0 IR(d) ) = max{R2 − 3R− 10cR(d)− 28d|d = 0, 1, 2} < 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 ⊂ ⋂2 d=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 Ak = ∞∑ i=1 pki xi, where pi denotes the ith prime, xi ≥ 0, and xi = 0 for all but finitely many values of i. If n = ∞∏ i=1 pxii , then s2(n) = 1 2 [A21 −A2]. 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 (3.4) 22x1 + 32x2 + · · · = R2 − 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 in- creasing order. Then for yi ≥ 0, and r ≥ 0, we have that 15y1 + 99y2 + · · ·+ (q2r − 2qr)yr ≡ 0 (mod 3). Denote this sum as D = D(y1, . . . , yr), and let C = r∑ i=0 (q2i − 3qi)yi Let q be any odd prime congruent to 2 modulo 3, k = q2 − 3q, ` = q2 − 2q, and suppose α ≥ 0. Consider intervals of the form 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⋃ α=0 IR(α) 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 − αRk, which in turn holds if and only if R ≥ (D − C) + αR(`− k) + `. Thus we have αR = ⌊ R− `− (D − C) `− k ⌋ . Define JR = αR⋃ α=0 IR(α). 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 − αRk ≤ 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 ⌋ k ≤ R2 − 4R+ 3−D. 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: S = {p(1)1 · · · p(1)r , p(2)1 · · · p(2)r , p(3)1 · · · p(3)r , . . .} and assume that p(j)i ≤ p(j)i+1. Clearly we must have that limj→∞ p(j)r = ∞, otherwise, we must have the same number occurring twice in the sequence. If p(j)r−1 contains a bounded subsequence, then there must be an identical product p(`)1 · · · p(`)r−1 occurring for infinitely many values of `. This gives a contradiction, since it implies that Ek(p (`0) 1 · · · p(`0)r−1, 1) intersects S, where `0 is one such value of `. Thus limj→∞ p (j) r−1 = ∞. Inductively, by similar arguments, we conclude that limj→∞ p (j) m = ∞, for m = 1, 2, . . . , r. But then lim j→∞ sk(p (j) 1 · · · p(j)r ) p (j) 1 · · · p(j)r = 0. 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(4p1q1) = 4(p1q1+ p1+ q1). It is possible that p1q1 + p1 + q1 = p2q2, where p2, q2 are again odd primes, and so on. Several such sequences exist the longest one with p1q1 < 50000, and pi, qi > 3 is: 184892 = 4 · 17 · 2719 s3−→ 195836= 4 · 173 · 283 s3−→ 197660 = 4 · 5 · 9883 s3−→ 237212 = 4 · 31 · 1913 s3−→ 244988 = 4 · 73 · 839 s3−→ 248636 = 4 · 61 · 1019 s3−→ 252956 = 4 · 11 · 5749 s3−→ 275996 = 4 · 7 · 9857 s3−→ 315452 = 4 · 17 · 4639 s3−→ 334076 = 4 · 47 · 1777 s3−→ 341372= 4 · 31 · 2753 s3−→ 352508 = 4 · 13 · 6779 s3−→ 379676 = 4 · 11 · 8629 s3−→ 414236= 4 · 29 · 3571 s3−→ 428636 = 4 · 13 · 8243 s3−→ 461660 = 4 · 5 · 41 · 563. It seems highly unlikely however that an increasing s3-sequence be infi- nite. 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 peri- odic. 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 s∗k-perfect numbers 1 4 2 27, 48 3 none 4 3125, 9315, 31280 4.1 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 = q1q2q3 is the product of 3 primes, then we have s (2) 3 (n) < n if and only if 3(q1q2 + q1q3 + q2q3) + q1q2q3 < 18 ( q1q2q3 − 6 7 ) if and only if 108 + 21(q1q2 + q1q3 + q2q3) < 11q1q2q3. (4.1) Since p > 1000, we have that q1q2q3 > 7006. Also, clearly qi 6= 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 6= 2, 3, or 7. In this case, s (2) 3 (n) < n if and only if 108 + 21(q1q2 + · · ·+ qr−1qr) + 7(q1q2q3 + · · ·+ qr−2qr−1qr) < 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 7006 + 21 5r−2 ( r 2 ) + 7 5r−3 ( r 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 ele- ment 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. Theorem 4.9. There are no s3-cycles of length 2. That is, if s (2) 3 (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 We have s(2)3 (4pq) = s3(4m) = 4s1(m) + 4s2(m) + s3(m). If s (2) 3 (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 = q1q2, then (4.2) implies q1 + q2 + q1q2 = pq. Substituting q1q2 = pq + p + q, and canceling gives q1 + q2 + p + q = 0, an impossibility. If m = q1q2q3, 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 q1q2q3 + · · ·+ 1 q2q3q4 ) + 4 ( 1 q1q2 + · · ·+ 1 q3q4 ) + ( 1 q1 + · · ·+ 1 q4 ) = 4pq pq + p+ q . 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 q1q2q3 + · · ·+ 1 q2q3q4 ) + 4 ( 1 q1q2 + · · ·+ 1 q3q4 ) + ( 1 q1 + · · ·+ 1 q4 ) < 2.6649 < 4pq pq + p+ q . A similar approach can be used when Ω(m) = 5. If r ≥ 6, then 4 ( 1 q1q2q3 + · · ·+ 1 qr−2qr−1qr ) +4 ( 1 q1q2 + · · ·+ 1 qr−1qr ) + ( 1 q1 + · · ·+ 1 qr ) < ( r 1 ) 4 3r−1 + ( r 2 ) 4 3r−2 + ( r 3 ) 1 3r−3 < 2.6649 < 4pq pq + p+ q , 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 that p ≥ 1009. Now s(2)3 (16p) = s3(8(3p + 4)). Let m = 3p + 4, so 16p = 16(m − 4)/3. Then 2, 3 - m, and m ≥ 3031. So s(2)3 (16p) = 8 + 12s1(m) + 6s2(m) + s3(m). The supposition that s (2) 3 (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 = q1q2, then (4.3) is also impossible for m in the allowable range. If m = q1q2q3, then (4.3) is equivalent to 88 + 36(q1 + q2 + q3) + 18(q1q2 + q1q3 + q2q3) = 13q1q2q3. Dividing through by m, and using the facts that m ≥ 3031, and qi ≥ 5, we have the inequality 88 3031 + 36 ( 1 q1q2 + 1 q1q3 + 1 q2q3 ) + 18 ( 1 q1 + 1 q2 + 1 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 + βqk = pαqβ . (5.1) First assume that α, β ≥ k. Then since βqk = pk(pα−kqβ − α), we have that pk divides β. Similarly qk divides α. Write β = bpk, and α = aqk. Clearly a, b > 0, and equation (5.1) becomes (a+ b)pkqk = paq k qbp k . 30 Chapter 5. The Power Prime Symmetric Divisor Functions We will show that we instead have a strict inequality (a+ b)pkqk < paq k qbp k . (5.2) Since a, b > 0, p ≥ 2, and q ≥ 3, it is easily seen that bpk−1 ≤ bpk − k, and aqk−1 ≤ aqk − k, and hence the inequality (5.2) is implied by a+ b < paq k−1 qbp 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β = aqbp α > α. Next suppose that α < k, and β ≥ k. Then for some a > 0, we have that α = aqk > 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 (−1)kksk + k∑ i=1 (−1)i+keisk−i = 0. 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 ∣∣∣∣∣∣∣∣∣∣∣∣∣ s1 1 0 0 · · · 0 2s2 s1 1 0 · · · 0 3s3 s2 s1 1 · · · 0 4s4 s3 s2 s1 · · · 0 ... ... ... ... ... ... ksk sk−1 sk−2 sk−3 · · · s1 ∣∣∣∣∣∣∣∣∣∣∣∣∣ 31 Chapter 5. The Power Prime Symmetric Divisor Functions Similarly, we can express sk in terms of ek as follows: sk = ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ e1 1 0 0 · · · 0 e2 2 e1 2 1 0 · · · 0 e3 3 e2 3 e1 3 1 · · · 0 e4 4 e3 4 e2 4 e1 4 · · · 0 ... ... ... ... ... ... ek−1 k−1 ek−2 k−1 ek−3 k−1 ek−4 k−1 · · · 1 ek k ek−1 k ek−2 k ek−3 k · · · e1k ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ 5.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):∑ n≤x ek(n) = ζ(k + 1)xk+1 (k + 1) log x +O ( 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ős [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∑ p≤x pk log` p = xk+1 (k + 1) log`+1 x +O ( xk+1 log`+2 x ) . Proof. The sum may be expressed as a Riemann-Stieltjes integral: ∑ p≤x pk log` p = ∫ x 3/2 tk log` t dpi(t). Integrating by parts we have:∫ x 3/2 tk log` t dpi(t) = xkpi(x) log` x − ∫ x 3/2 ( ktk−1 log` t − `t k−1 log`+1 t ) pi(t) dt. 32 Chapter 5. The Power Prime Symmetric Divisor Functions By the prime number theorem, this gives∫ x 3/2 tk log` t dpi(t) = xk log` x ( x log x +O ( x log2 x )) − ∫ x 3/2 ( ktk−1 log` t − `t k−1 log`+1 t )( t log t +O ( t log2 t )) dt = xk+1 log`+1 x +O ( xk+1 log`+2 x ) − k ∫ x 3/2 tk log`+1 t dt+O (∫ x 3/2 tk log`+2 t dt ) = xk+1 log`+1 x − k [ xk+1 (k + 1) log`+1 x +O(1) + `+ 1 k + 1 ∫ x 3/2 tk log`+2 t dt ] +O ( 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, ∑ n≤x ek(n) = ζ(k + 1)xk+1 (k + 1) log x +O ( xk+1 log log x log2 x ) . Proof. We have ∑ n≤x ek(n) = ∑ p≤x ∞∑ i=1 pk ⌊ x pi ⌋ = ∑ p≤x pk ⌊ x p ⌋ + ∞∑ i=2 ∑ p≤x1/i pk ⌊ 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 ∑ p≤x pk ⌊ x p ⌋ = ∑ i≤x/2 ∑ x i+1 <p≤x i ipk = ∑ i≤x/2 ∑ p≤x/i pk = ∑ i≤x/2 ( (x/i)k+1 (k + 1) log (x/i) +O ( (x/i)k+1 log2 (x/i) )) . (5.4) Let Σ1 = ∑ i≤log2 x 1 ik+1 log (x/i) , and Σ2 = ∑ log2 x<i≤x/2 1 ik+1 log (x/i) , so that ∑ i≤x/2 1 ik+1 log (x/i) = Σ1 +Σ2. We have that Σ1 ≥ 1log x ∑ i≤log2 x 1 ik+1 = 1 log x ζ(k + 1)− ∑ i>log2 x 1 ik+1 = 1 log x ( ζ(k + 1) +O ( 1 log2k x )) = ζ(k + 1) log x +O ( 1 log2k+1 x ) . 34 Chapter 5. The Power Prime Symmetric Divisor Functions On the other hand, Σ1 ≤ ∑ i≤log2 x 1 ik+1(log x− 2 log log x) = 1 log x ( 1 +O ( log log x log x )) ∑ i≤log2 x 1 ik+1 = 1 log x ( 1 +O ( log log x log x ))( ζ(k + 1) +O ( 1 log2k x )) = ζ(k + 1) log x +O ( log log x log2 x ) . Combining these results we have that Σ1 = ζ(k + 1) log x +O ( log log x log2 x ) . (5.5) The sum Σ2 is negligible by comparison: Σ2 = ∑ log2 x<i≤x/2 1 ik+1 log (x/i) ∑ i>log2 x 1 ik+1 ∫ ∞ log2 x 1 tk+1 dt 1 log2k x . (5.6) Now we need to bound the error term in (5.4): ∑ i≤x/2 1 ik+1 log2 (x/i) = O (∫ x/2 1 dt t2 log2 x/t ) = O (∫ √x 1 dt t2 log2 x/t + ∫ x/2 √ x dt t2 log2 x/t ) = O ( 4 log2 x ∫ √x 1 dt t2 + ∫ x/2 √ x dt t2 ) = O ( 1 log2 x ) (5.7) 35 Chapter 5. The Power Prime Symmetric Divisor Functions Hence by (5.5), (5.6), and (5.7), we have that∑ p≤x pk ⌊ x p ⌋ = ζ(k + 1)xk+1 (k + 1) log x +O ( xk+1 log log x log2 x ) . To conclude the proof, we need to bound the second term in (5.3). ∞∑ i=2 ∑ p≤x1/i pk ⌊ x pi ⌋ ≤ x ∞∑ i=2 ∑ p≤x1/i pk pi ≤ x ∑ p≤√x pk−1 p− 1 ≤ 2x ∑ p≤√x pk−2 = O(x log log x), if k = 1;O(x k+12log 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, x k+1 2 log x = O ( 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 solu- tions 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 r1,k(n) = pP(k)(n) = |e(−1)k {n}| (5.8) It is much easier to work with the functions pP(k)(n), than with the ana- logues 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 2nq`, satisfy ek(2nq`) = n2k+`qk, and `qk ≡ ` (mod 2k). Since there are infinitely many such q, we have that limn→∞ pP(k)(n2 k + `) =∞. 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∏ p 1 1− xpk = ∞∑ n=0 pP(k)(n)x n. 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 write as p(j)P(k) : ∞∑ n=0 p (j) P(k)(n)x n = (1− x)j ∞∑ n=0 pP(k)(n)x n = (1− x)j ∏ p 1 1− xpk . (5.9) In particular we have that p (−1) P(k) (n) = n∑ m=0 pP(k)(m). 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ős 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 p = log log x+ b1 +O ( 1 log x ) . Lemma 5.10. There is a constant b2 such that∑ n≤x Ω(n) = x log log x+ b2x+O ( x log x ) . Proof. By the additivity of Ω(n), and de Polignac’s formula,∑ n≤x Ω(n) = ∑ p≤x ∞∑ j=1 ⌊ x pj ⌋ = x ∑ p≤x ∞∑ j=1 ( 1 pj ) − ∑ p≤x ∞∑ j=1 { x pj } = x ∑ p≤x 1 p− 1 +O ∑ p≤x log x log p = x ∑ p≤x ( 1 p + 1 p(p− 1) ) +O ( x log x ) . The last step followed from Lemma 5.4. Hence by Lemma 5.9,∑ n≤x Ω(n) = x ( log log x+ b1 +O ( 1 log x )) + x ∑ p∈P 1 p(p− 1) +O ( x log x ) = x log log x+ b2x+O ( 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≤x Ω(n)2 = x(log log x)2 +O(x log log x). (5.14) Proof. ∑ n≤x Ω(n)2 = ∑ n≤x ∑ p`|n 1 2 = ∑ n≤x ∑ p`|n 1 ∑ qm|n 1 = ∑ p`≤x ∑ qm≤x ∑ n≤x p`,qm|n 1 = ∑ p≤x ∑ `,m≤log x/ log p ∑ n≤x pmax{`,m}|n 1 + ∑ p`,qm≤x p6=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 Σ1 = ∑ p≤x ∑ `,m≤Rp ⌊ x pmax{`,m} ⌋ = x ∑ p≤x ∑ `,m≤Rp 1 pmax{`,m} +O ∑ p≤x ⌊ log x log p ⌋2 = x ∑ p≤x ∑ k≤Rp 2k − 1 pk +O log2 x∑ p≤x 1 log2 p = O x∑ p≤x ∑ k≤Rp k pk +O( x log x ) , using Lemma 5.4 = O x∑ p≤x [ 1 p ( 1− 1/pbRc (1− 1/p)2 ) − bRc pbRc+1(1− 1/p) ]+O( x log x ) = O x∑ p≤x [ p (p− 1)2 ( 1− 1 x ) − log x (p− 1)x log p ]+O( x log x ) = O x∑ p≤x 1 p +O( x log x ) = O(x log log x). We now turn our attention to Σ2: Σ2 = x ∑ p`,qm≤x p6=q 1 p`qm +O ∑ p`,qm≤x p6=q 1 = x ∑ p,q≤x p6=q 1 pq + x ∑ p`,qm≤x p6=q max{`,m}≥2 1 p`qm +O ( x log x ) . 40 Chapter 5. The Power Prime Symmetric Divisor Functions But ∑ p,q≤x p6=q 1 pq = ∑ q≤x 1 q ∑ p≤x p6=q 1 p = ∑ q≤x 1 q (log log x+O(1)) = (log log x)2 +O(log log x), and ∑ p`,qm≤x p6=q max{`,m}≥2 1 p`qm = O ∑ p`≤x `≥2 1 p` ∑ q≤x 1 q +O(1) = O(log log x). (5.15) Hence Σ2 = x(log log x)2 +O(x log log x), (5.16) and therefore ∑ n≤x Ω(n)2 = x(log log x)2 +O(x log log x) (5.17) 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án [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) = ∑ n≤x, n∈S 1 ≤ ∑ n≤x (Ω(n)− log log x)2 (log log x)3/2 (log log x)−3/2 ∑ n≤x Ω(n)2 − 2 log log x ∑ n≤x Ω(n) + x(log log x)2 (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) − c1x√ log log x ≤ bk(x, y) ≤ Ψ(x, y1/k) (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) − c1x√ 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 bk(x, n) = n∑ m=0 pP(k)(n) = p (−1) P(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 y1/α, 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 bk(x, xα) ∼ Ψ(x, xα/k) ∼ ρ ( 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). Conse- quently (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, ( xα 2 log log x )1/k) − c1x√ log log x ≤ bk(x, 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 u = log x log y = log x (α/k) log x− (1/k) log(2 log log x) = ( k α ) 1 1− (1/α) log(2 log log x)/ log x. The identity 1 1− a < 1 + 2a holds for 0 < a < 1/2. So if x is chosen sufficiently large such that 0 < log(2 log log x) α log x < 1 2 , then u < 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ρ ( k α + 2k log(2 log log x) α2 log x )[ 1 +O ( 1 log x )] = xρ ( k α + 2k log(2 log log x) α2 log x ) +O ( x log x ) ≥ xρ ( k α ) − 2kx log(2 log log x) α2 log x +O ( x log x ) = xρ ( k α ) +O ( x log log log x 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 ∑ n≤x sk,`(n) = ζ(`+ 1)x`+1(log log x)k−1 (`+ 1)(k − 1)! log x +O ( 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: ∑ n≤x sk,`(n) = k∑ r=1 ∑ p1<...<pr ∑ i1+···+ir=k i1,...,ir>0 (pi11 · · · pirr )`× ∞∑ j1,...,jr=1 ( j1 − 1 i1 − 1 ) · · · ( jr − 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 pj11 , . . . , p jr r ||n is⌊ x pj11 · · · pjrr ⌋ − (⌊ x pj1+11 p j2 2 · · · pjrr ⌋ + ⌊ x pj11 p j2+1 2 · · · pjrr ⌋ + · · ·+ ⌊ x pj11 p j2 2 · · · pjr+1r ⌋) + · · ·+ (−1)r ⌊ x pj1+11 · · · pjr+1r ⌋ , which we write as β(j1, . . . , jr). Each such n contributes ( j1 i1 ) · · · (jrir) copies of (pi11 · · · pirr )` to the sum ∑ n≤x sk,`(n). Thus (p i1 1 · · · pirr )` occurs ∞∑ j1,...,jr=1 ( j1 i1 ) · · · ( jr ir ) β(j1, . . . , jr) times. We make the following claim: ∞∑ j1,...,jr=1 ( j1 i1 ) · · · ( jr ir ) β(j1, . . . , jr) = ∞∑ j1,...,jr=1 ( j1 − 1 i1 − 1 ) · · · ( jr − 1 ir − 1 )⌊ x pj11 · · · pjrr ⌋ . (6.1) To prove (6.1), first note that ⌊ x p j1 1 ···pjrr ⌋ occurs ( j1 i1 ) · · · ( jr ir ) − (( j1 − 1 i1 )( j2 i2 ) · · · ( jr ir ) + · · ·+ ( j1 i1 )( j2 i2 ) · · · ( jr − 1 ir )) + · · ·+ (−1)r ( j1 − 1 i1 )( j2 − 1 i2 ) · · · ( jr − 1 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,` ( j1 i1 ) · · · ( jr ir ) − (( j1 − 1 i1 )( j2 i2 ) · · · ( jr ir ) + · · ·+ ( j1 i1 )( j2 i2 ) · · · ( jr − 1 ir )) + · · ·+ (−1)r ( j1 − 1 i1 )( j2 − 1 i2 ) · · · ( jr − 1 ir ) = ( j1 − 1 i1 − 1 ) · · · ( jr − 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 i1 − 1 ) · · · ( jr − 1 ir − 1 ) . But factoring, the identity (6.2) and the induction hypothesis give us that Cr = ( jr ir ) Cr−1 − ( jr − 1 ir ) Cr−1 = Cr−1 ( jr − 1 ir − 1 ) = ( j1 − 1 i1 − 1 ) · · · ( jr−1 − 1 ir−1 − 1 )( jr − 1 ir − 1 ) . 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 generaliza- tions of the prime number theorem. These are taken from Nathanson [33], pp.313-319, however we also include precise error terms. Let pik(x) = #{n ≤ x : Ω(n) = ω(n) = k}; and pi∗k(x) = #{n ≤ x : Ω(n) = k}. That is, pik(x) counts the number of n ≤ x such that are products of exactly k distinct prime factors, and pi∗k(x) counts the number of n ≤ x which have k prime factors with repetition. Note that pi1(x) = pi∗1(x) = pi(x). For k = 1, the prime number theorem gives us pi(x) = x log x +O ( x log2 x ) . (6.4) 49 Chapter 6. The Average Order of sk,` For k ≥ 2, we also have that pik(x) = x(log log x)k−1 (k − 1)! log x +O ( x(log log x)k−2 log x ) , (6.5) and 0 ≤ pi∗k(x)− pik(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 ∑ n≤x ω(n)=Ω(n)=k nu = xu+1(log log x)k−1 (u+ 1)(k − 1)! log x +O ( xu+1(log log x)k−2 log x ) . Proof. Writing the sum as a Riemmann-Stieltjes integral, we have:∑ n≤x ω(n)=Ω(n)=k nu = ∫ x 2k− tu dpik(t) =xupik(x)− u ∫ x 2k tu−1pik(t) dt = xu+1(log log x)k−1 (k − 1)! log x +O ( xu+1(log log x)k−2 log x ) − u ∫ x 2k tu(log log t)k−1 (k − 1)! log t dt+O (∫ x 2k tu(log log t)k−2 log t dt ) It is easy to see via a straightforward application of integration by parts that∫ x 2k tu(log log t)k−1 log t dt = xu+1(log log x)k−1 (u+ 1) log x +O ( xu+1(log log x)k−1 log2 x ) . Combining this information, we have ∑ n≤x ω(n)=Ω(n)=k nu = xu+1(log log x)k−1 (u+ 1)(k − 1)! log x +O ( 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)` ∞∑ j1,...,jk=1 ⌊ x pj11 · · · pjkk ⌋ = ∑ p1<...<pk (p1 · · · pk)` ⌊ x p1 · · · pk ⌋ + ∑ p1<...<pk (p1 · · · pk)` ∞∑ j1,...,jk=1 j1···jk>1 ⌊ x pj11 · · · 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 p1 · · · pk ⌋ = ∑ m≤x/2k ∑ p1<...<pk x m+1 <p1···pk≤ xm m(p1 · · · pk)` = ∑ m≤x/2k ∑ p1<...<pk p1···pk≤x/m (p1 · · · pk)` = x`+1 (`+ 1)(k − 1)! ∑ m≤x/2k (log log (x/m))k−1 m`+1 log (x/m) +O x`+1 ∑ m≤x/2k (log log (x/m))k−2 m`+1 log (x/m) . (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) + ∑ log2 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 m`+1 log (x/m) ≤ (log log x) k−1 m`+1(log x− 2 log log x) = (log log x)k−1 m`+1 log x ( 1 +O ( log log x log x )) , which implies that ∑ m≤log2 x (log log (x/m))k−1 m`+1 log (x/m) ≤(log log x) k−1 log x ( 1 +O ( log log x log x )) ∑ m≤log2 x 1 m`+1 = (log log x)k−1 log x ( 1 +O ( log log x log x )) × ζ(`+ 1) ( 1 +O ( 1 log2` x )) = ζ(`+ 1)(log log x)k−1 log x +O ( (log log x)k log2 x ) . (6.10) On the other hand, for m ∈ [1, log2 x] we have (log log (x/m))k−1 m`+1 log (x/m) ≥(log (log x− 2 log log x)) k−1 m`+1 log x = ( log log x+ log ( 1− 2 log log xlog x ))k−1 m`+1 log x = ( log log x+O ( log log x log x ))k−1 m`+1 log x = (log log x)k−1 +O ( (log log x)k−1 log x ) m`+1 log x , and so 52 Chapter 6. The Average Order of sk,` ∑ m≤log2 x (log log (x/m))k−1 m`+1 log (x/m) ≥(log log x) k−1 log x ( ζ(`+ 1) +O ( 1 log2` x )) +O ( (log log x)k−1 log2 x ) = ζ(`+ 1)(log log x)k−1 log x +O ( (log log x)k−1 log2 x ) . (6.11) Combining (6.10) and (6.11) we have that ∑ m≤log2 x (log log (x/m))k−1 m`+1 log (x/m) = ζ(`+ 1)(log log x)k−1 log x +O ( (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 p1 · · · pk ⌋ = x`+1 (`+ 1)(k − 1)!×( ζ(`+ 1)(log log x)k−1 log x +O ( (log log x)k log2 x )) +O ( x`+1(log log x)k−2 log x ) = ζ(`+ 1)x`+1(log log x)k−1 (`+ 1)(k − 1)! log x +O ( x`+1(log log x)k−2 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,` ∑ p1<...<pk (p1 · · · pk)` ∞∑ j1,...,jk=1 j1···jk>1 ⌊ x pj11 · · · pjkk ⌋ x ∑ p1<...<pk p21p2···pk≤x (p1 · · · pk)` ∞∑ j1,...,jk=1 j1···jk>1 1 pj11 · · · pjkk x ∑ p1<...<pk p21p2···pk≤x (p1 · · · pk)` ( 1 (p1 − 1) · · · (pk − 1) − 1 p1 · · · pk ) x ∑ p1<...<pk p21p2···pk≤x (p1 · · · pk)` p21p2 · · · pk x ∑ p≤x 1 k+1 p`−2 ∑ n≤x/p ω(n)=Ω(n)=k−1 n`−1 x ∑ p≤x 1 k+1 ( p`−2 (x/p)`(log log (x/p))k−2 log (x/p) ) = x`+1 ∑ p≤x 1 k+1 (log log (x/p))k−2 p2 log (x/p) 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 j − 1 ) xn = ( x 1− x )j , which holds for |x| < 1. We have 55 Chapter 6. The Average Order of sk,` k−1∑ r=1 ∑ p1<...<pr ∑ i1+···+ir=k i1,...,ir>0 (pi11 · · · pirr )`× ∞∑ j1,...,jr=1 ( j1 − 1 i1 − 1 ) · · · ( jr − 1 ir − 1 )⌊ x pj11 · · · pjrr ⌋ x k−1∑ r=1 ∑ i1+···+ir=k i1,...,ir>0 ∑ p1<...<pr p i1 1 ···pirr ≤x (pi11 · · · pirr )` r∏ m=1 ∞∑ jm=im ( jm − 1 im − 1 ) 1 pjm = x k−1∑ r=1 ∑ i1+···+ir=k i1,...,ir>0 ∑ p1<...<pr p i1 1 ···pirr ≤x (pi11 · · · pirr )` r∏ m=1 ( 1 pm − 1 )im x k−1∑ r=1 ∑ i1+···+ir=k i1,...,ir>0 ∑ p1<...<pr p i1 1 ···pirr ≤x (pi11 · · · pirr )`−1 = x ∑ n≤x ω(n)<k=Ω(n) n`−1 = x ∫ x 2− t`−1 d(pi∗k(t)− pik(t)). (6.16) Applying integration by parts to (6.16), and using the bound (6.6), we have that k−1∑ r=1 ∑ p1<...<pr ∑ i1+···+ir=k i1,...,ir>0 (pi11 · · · pirr )`× ∞∑ j1,...,jr=1 ( j1 − 1 i1 − 1 ) · · · ( jr − 1 ir − 1 )⌊ x pj11 · · · pjrr ⌋ x `+1(log log x)k−2 log x . (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 ` ≥ 1. Then ∑ n≤x sk,`(n) = ζ(`+ 1)x`+1(log log x)k−1 (`+ 1)(k − 1)! log x +O ( 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 pa- per 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ős. 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 ∑ n≤x (−1)e1(n) xe−c0 √ log x log log x. They also proved the related result: ∞∑ n=1 (−1)e1(n) n = 0. 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 ∣∣∣∣∣∣ ′∑ n≤x an − 12pii ∫ c+iT c−iT A(s)xs s ds ∣∣∣∣∣∣ ( ∞∑ n=1 |an|n−c ) xc T + ∑ x 2 <n< 3x 2 |an|min { 1, x T |x− n| } + (ax T if x ∈ N ) . 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:( ∞∑ n=1 |an|n−c ) xc T ζ(c)x c T x T (c− 1) x log x T . For the second error term, we break up the sum:∑ x 2 <n< 3x 2 |an|min { 1, x T |x− n| } = ∑ x 2 <n<(1− 1T )x x (x− n)T + ∑ (1− 1T )x≤n≤(1+ 1T )x 1 + ∑ (1+ 1T )x<n< 3x2 x (n− x)T =Σ1 +Σ2 +Σ3. Now Σ2 x/T , and Σ1 x T ∫ (1− 1T )x x 2 dt x− t = x T [− log (x− t)]t=(1− 1 T )x t=x 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∣∣∣∣∣∣ ∑ n≤x an − 12pii ∫ c+iT c−iT A(s)xs s ds ∣∣∣∣∣∣ x log xT . 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) logw |t| if |t| ≥ 4 A(s) 1|s− 1|α if |t| ≤ 4. 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 c−iT A(s)xs s ds x (log x)(1−α)/2 . Furthermore, if A(s) is the Dirichlet series for an, and |an| ≤ 1, then∑ n≤x an 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 around the branch cut. Let c′ = 1 − Klog (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 ∫ 9 ∫ c+iT c′+iT |A(s)||xs| |s| ds x c logw T (c− c′) T x log w−1 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, ∫ 8 ∫ c′+iT c′+i4 |A(s)||xs| |s| ds xc′ ∫ T 2 logw t t dt x log w+1 T exp ( K log x log T ) x(log x) (w+1)δ exp (K(log x)1−δ) The integral over γ2 can be likewise bounded. Furthermore, ∫ 7 xc′ ∫ c′+i4 c′+ic′′ ds |s− 1|α x logα T 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∫ 6 xc ∫ c′+ic′′ c+ic′′ ds |s− 1|α x (c′′)α log T x (log x)δ−αβ = x (log x)(1−α)/2 , with a similar result holding for γ4. Finally,∫ 5 xc ∫ c+ic′′ c−ic′′ ds |s− 1|α xc ′′ logα x = x (log x)β−α = 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 pos- itive constant Kq such that if σ ≥ 1 −Kq/ log (|t|+ 4), then for each non- principal χ (mod q), L(s, χ) is nonzero, and satisfies | logL(s, χ)| ≤ log log (|t|+ 4) +Oq(1); 1 L(s, χ) q log (|t|+ 4). (7.1) 61 Chapter 7. Modular Distribution of Prime Symmetric Functions These inequalities in turn imply that: L(s, χ)q log (|t|+ 4); (7.2) | argL(s, χ)| ≤ 2 log log (|t|+ 4) +Oq(1). (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 L(s, χ0) = ζ(s) ∏ p|q (1− p−s). (7.4) 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) log (|t|+ 4), (7.5) ζ(s) log |t|, if |t| ≥ 4 (7.6) ζ ′ ζ (s) 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 log (|t|+ 4) ≤ σ ≤ 2 } \{y ∈ R : y ≤ 1}. 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+δ = ∑ p log p p1+δ +O(1) = ∫ ∞ 2− log u u1+δ dpi(u) +O(1) ∫ ∞ 2 du u1+δ +O(1) = O ( 1 δ ) . (7.9) For a given N ∈ N, σ must lie in one of the intervals[ 1− K log (t+ 4) , 1 + 1 log t ] , [ 1 + 1 log t , 1 + 1 (log t)1−1/N ] ,[ 1 + 1 (log t)1−1/N , 1 + 1 (log t)1−2/N ] , . . . , [ 1 + 1 (log t)1/N , 2 ] . 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)| = ∣∣∣∣∫ σ∞ ζ ′ ζ (ς + it) dς ∣∣∣∣ ≤ ∫ 2 ∞ ∣∣∣∣ζ ′ζ (ς + it) ∣∣∣∣ dς + N−1∑ n=0 ∫ σn+1 σn ∣∣∣∣ζ ′ζ (ς + it) ∣∣∣∣ dς + ∫ σN+1 σN ∣∣∣∣ζ ′ζ (ς + it) ∣∣∣∣ dς = O(1) + N−1∑ n=0 O ( σn − 1 σn+1 − 1 ) +O(1) = O ( N(log t)1/N ) +O(1). Putting N = blog log tc, 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 |s− 1|α (1 +O(s− 1)) 1 |s− 1|α . Lemma 7.6. Let ω = α + iβ. For σ ≥ 1 − Kq/ log (|t|+ 4), with χ non- principal, we have that exp (ω logL(s, χ))q (log (|t|+ 4))|α|+2|β|. Proof. For s as required, we have by (7.1), (7.2) and (7.3) that |exp (ω logL(s, χ))| = |L(s, χ)|α exp (−β argL(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 ∏ p≡a (mod q) 1 1− ωp−s = exp ω φ(q) ∑ χ (mod q) χ̄(a) logL(s, χ) exp(ϕ(s)), where ϕ(s) is analytic on σ > 1/2, and satisfies ϕ(s) 1 for σ ≥ 1/2 + . 64 Chapter 7. Modular Distribution of Prime Symmetric Functions Hence ∏ p≡a (q) 1 1−ωp−s has an analytic continuation to Dq = { s : 1− Kq log (|t|+ 4) ≤ σ } \{y ∈ R : y ≤ 1}. Proof. We shall make use of the result 1 φ(q) ∑ χ(mod q) χ̄(a) logL(s, χ) = ∑ pj≡a(mod q) p−js j , (c.f. [5], p. 239), which holds for σ > 1. Let ϕ(s) = ∑ p≡a (mod q) ∞∑ j=2 ωjp−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: ∏ p≡a (mod q) 1 1− ωp−s = exp ∑ p≡a (mod q) ∞∑ j=1 ωjp−js j = exp ω ∑ pj≡a (mod q) p−js j exp(ϕ(s)) = exp ω φ(q) ∑ χ (mod q) χ̄(a) logL(s, χ) exp(ϕ(s)). 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ős. 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 e2pii/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 involv- ing 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:∑ n≤x n≡b(mod m) e(n)≡a(mod q) 1 ∼ x mq as x→∞. (7.10) Observe that 1 q r∏ `=1 q`−1∑ j=0 ζ (ek` (n)−a`)j q` = {1, if e(n) ≡ a(q); 0 otherwise. For j = (j1, . . . , jr) ∈ Zq1 × · · · × Zqr , let f(n) = f(j;n) = ζ ek1 (n)j1 q1 · · · ζekr (n)jrqr . Note that f(n) is completely multiplicative. Hence we have 66 Chapter 7. Modular Distribution of Prime Symmetric Functions ∑ n≤x n≡b(mod m) e(n)≡a(mod q) 1 = 1 q q1−1∑ j1=0 ζ−a1j1q1 · · · qr−1∑ jr=0 ζ−arjrqr ∑ n≤x n≡b(m) f(j;n) = 1 q q1−1∑ j1=0 ζ−a1j1q1 · · · qr−1∑ jr=0 ζ−arjrqr ∑ 0≤n≤(x−b)/m f(j;mn+ b) = 1 q q1−1∑ j1=0 ζ−a1j1q1 · · · qr−1∑ jr=0 ζ−arjrqr f(j; d) ∑ 0≤n≤(x−b)/m f(j;m′n+ b′) = 1 q q1−1∑ j1=0 ζ−a1j1q1 · · · qr−1∑ jr=0 ζ−arjrqr f(j; d) ∑ n≤x/d em′b′(n)f(j;n). Since m′ and b′ are relatively prime, we may write em′b′(n) = 1 φ(m′) ∑ χ(mod m′) χ̄(b′)χ(n). Thus, ∑ n≤x n≡b(mod m) e(n)≡a(mod q) 1 = 1 qφ(m′) q1−1∑ j1=0 ζ−a1j1q1 · · · qr−1∑ jr=0 ζ−arjrqr × f(j; d) ∑ χ(mod m′) χ̄(b′) ∑ n≤x/d χ(n)f(j;n). Note that f(0;n) = 1, and so 67 Chapter 7. Modular Distribution of Prime Symmetric Functions ∑ n≤x n≡b(mod m) e(n)≡a(mod q) 1 = 1 qφ(m′) ∑ χ(mod m′) χ̄(b′) ∑ n≤x/d χ(n) + 1 qφ(m′) ∑ j 6=0 ζ−a1j1q1 · · · ζ−arjrqr f(j; d) ∑ χ(mod m′) χ̄(b′) ∑ n≤x/d χ(n)f(j;n) = x qm +O(1) + 1 qφ(m′) ∑ j 6=0 ζ−a1j1q1 · · · ζ−arjrqr f(j; d) ∑ χ(mod m′) χ̄(b′) ∑ n≤x/d χ(n)f(j;n) (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 6= 0 and character χ (modm′). To do this, we shall use Perron’s formula, and hence we must consider the Dirichlet series ∑∞ n=1 χ(n)f(n)n −s. Fix such a j and χ (mod m′). Now, for σ > 1, define A(s) = A(j, χ; s) = ∞∑ n=1 χ(n)f(n)n−s. 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 1 1− χ(p)f(p)p−s = ∏ p|q 1 1− χ(p)f(p)p−s ∏ a∈S ∏ p≡a(mod Q) 1 1− χ(a)ζak1j1q1 · · · ζa kr jr qr 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 A(s) = F (s) exp(ϕ(s)) exp ∑ χ∗(mod q) ω(χ∗) logL(s, χ∗) , where ω(χ∗) = ω(j, χ;χ∗) = 1 φ(Q) ∑ a∈S χ(a)χ̄∗(a)ζa k1j1 q1 · · · ζa kr jr qr . Note that F (s)q,k 1 on 1/2 ≤ σ ≤ 2, and also that |ω(χ∗)| ≤ 1. Write ω(χ∗) = α(χ∗) + β(χ∗)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 ω(χ∗) 6= 1. Indeed, if ω(χ∗) = 1, then χ(a)χ̄∗(a)ζa k1j1 q1 · · · ζa kr jr qr = 1 for all a ∈ S, and in particular for a = 1. However, since q1, . . . , qr are pairwise relatively prime, j 6= 0 by assumption, and χ(1) = χ∗(1) = 1, this yields a contradiction. It follows that α(χ∗) < 1. Define constants w1, w > 0 as follows: w1 = w1(j, χ) = ∑ χ∗ 6=χ∗0(mod Q) (|α(χ∗)|+ 2|β(χ∗)|); 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 1|s− 1|α0 if |t| ≤ 4, (7.13) A(s)Q logw |t| if |t| ≥ 4. (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 inequal- ity (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∑ n≤x n≡b(m) e(n)≡a(q) 1 = x mq +O ( x logδ x ) Proof. By Proposition 7.10, we may apply Lemma 7.2 to A(j; s), for each j 6= 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∑ n≤x s(n)≡a(q) 1 = x q +Oq ( x√ log x ) . Proof. In this case, we have m = 1 = r, and k1 = 1. Since q is prime, we have: ω0 = 1 q − 1 q−1∑ b=1 ζbjq = α0 = − 1 q − 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 ζ = e2pii/q. Then ∑ n≤x sk(n)≡a(q) 1 = 1 q q−1∑ j=0 ζ−aj ∑ n≤x ζjsk(n) (7.15) 70 Chapter 7. Modular Distribution of Prime Symmetric Functions Thus we must study the sum ∑ n≤x ζ jsk(n). With this intent let A(j; s) = ∞∑ n=1 ζjsk(n)n−s. 7.4.1 The Dirichlet Series Definition 7.13. Define κ = κ(q, k) = q ∏ p|q pβ ||k! pβ . 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′ ) + κ k′! p(n) ≡ ( 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 j1 ) · · · ( kq−1 jq−1 ) 1j1 · · · (q − 1)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 ( Ωq,1(n) j1 ) · · · ( Ωq,q−1(n) jq−1 ) 1j12j2 · · · (q − 1)jq−1 ≡ ∑ j1+···+jq−1=k ( k1 j1 ) · · · ( kq−1 jq−1 ) 1j12j2 · · · (q − 1)jq−1 , by Lemma 7.14 = σ(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 prod- uct, 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 combi- nation 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)∑ 0≤i0≤κ−1 · · · ∑ 0≤iq−1≤κ−1 α(j; i0, . . . , iq−1) q−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 α(j; i) = 1 κq ∑ k∈Zqκ ζ−k·iκ ζ jσ(k). 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) = ∑ i α(j; i)ζi·kκ . (7.18) 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∗ = κqI, 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 x = α(j; 0, 0, . . . , 0) α(j; 1, 0, . . . , 0) ... α(j;κ− 1, κ− 1, . . . , κ− 1) and b = ζjσ(0,0,...,0) ζjσ(1,0,...,0) ... ζjσ(κ−1,κ−1,...,κ−1) , then x = 1 κq A∗b, which implies that α(j; i) = 1 κq ∑ k∈Zqκ ζ−k·iκ ζ jσ(k) 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 ∑ i α(j; i)ζi·kκ , 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 F (i; s) = ∏ p|q 1 1− ζipκ p−s . 73 Chapter 7. Modular Distribution of Prime Symmetric Functions Then by the previous proposition and Lemma 7.7 we can write A(j; s) = ∑ i∈Zqκ α(j; i)F (i; s) ∏ b∈S ∏ p≡b(mod q) ( 1 1− ζibκ p−s ) = ∑ i∈Zqκ α(j; i)F (i; s) exp ∑ χ (mod q) ω(i;χ) logL(s, χ) exp(ϕ(i; s)), (7.19) where ϕ(i; s) 1 for σ ≥ 1/2 + , and ω(i;χ) = 1 φ(q) ∑ b∈S ζibκ χ̄(b) = α(i;χ) + iβ(i;χ). 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+α 2)/2 ) c = 1 + 1 log x G(i; s) = ∏ p|q 1− p−s 1− ζipκ p−s . Note that 0 ≤ α < 1. Now we can express A(j; s) as follows: A(j; s) = ∑ i∈Z α(j; i)G(i; s)ζ(s) + ∑ i∈Z′ α(j; i)F (i; s) exp ∑ χ (mod q) ω(i;χ) logL(s, χ) exp(ϕ(i; s)). (7.20) 74 Chapter 7. Modular Distribution of Prime Symmetric Functions It is easily seen that for i ∈ Z ′ the function F (i; s) exp ∑ χ (mod q) ω(i;χ) logL(s, χ) exp(ϕ(i; s)) satisfies the conditions of Lemma 7.2 with respect to the given α. Hence by that same Lemma, we may conclude that ∫ c+iT c−iT ( xs s ) F (i; s) exp ∑ χ (mod q) ω(i;χ) logL(s, χ) exp(ϕ(i; s)) ds x (log x)(1−α)/2 . (7.21) On the other hand, if i ∈ Z, then 1 2pii ∫ c+iT c−iT ( xs s ) G(i; s)ζ(s) ds =Res (( xs s ) G(i; s)ζ(s); s = 1 ) + 1 2pii ∫ γ ( xs s ) G(i; s)ζ(s) ds, where γ is the union of the following three paths: γ1 : line segment from c− iT to 1− Klog (T + 4) − iT γ2 : Along 1− Klog (|t|+ 4) + it for −T ≤ t ≤ T γ3 : line segment from 1− Klog (T + 4) + iT to c+ iT Using arguments analogous to Lemma 7.2, together with the bounds estab- lished on ζ(s) and the fact that the path γ is bounded away from the pole at s = 1, we have that 1 2pii ∫ 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∑ n≤x ζjsk(n) = 1 2pii ∫ c+iT c−iT A(j; s)xs s ds+O ( x log x T ) = 1 2pii ∑ i∈Z α(j; i) ∫ c+iT c−iT ( xs s ) G(i; s)ζ(s) ds + 1 2pii ∑ i∈Z′ α(j; i) × ∫ c+iT c−iT ( xs s ) F (i; s) exp ∑ χ (mod q) ω(i;χ) logL(s, χ) exp(ϕ(i; s)) ds +O ( x log x T ) = ∑ i∈Z α(j; i)xG(i; 1) +O ( x (log x)(1−α)/2 ) . (7.23) Theorem 7.21. There is a δ > 0 such that as x→∞,∑ n≤x sk(n)≡a (q) 1 = x qκq q−1∑ j=0 ∑ i∈Zqκ (b,q)=1⇒ib=0 ∑ k∈Zqκ ζ(σ(k)−a)jζ−i·kκ ∏ p|q ( 1− p−1 1− ζipκ p−1 ) +O ( x logδ x ) , where if q is prime, we interpret iq to be i0. Proof. Using Proposition 7.18, and combining equations (7.15) and (7.23) we have:∑ n≤x sk(n)≡a (q) 1 = 1 q q−1∑ j=0 ζ−aj [∑ i∈Z α(j; i)xG(i; 1) +O ( x (log x)(1−α)/2 )] = x q q−1∑ j=0 ζ−aj ∑ i∈Z α(j; i)G(i; 1) +O ( x (log x)(1−α)/2 ) = x qκq q−1∑ j=0 ∑ i∈Z ∑ k∈Zqκ ζ(σ(k)−a)jζ−i·kκ ∏ p|q ( 1− p−1 1− ζipκ p−1 ) +O ( x (log x)(1−α)/2 ) . 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∑ n≤x ζs2(n) = o(x), where ζ = e2pii/3. Let A(s) = ∞∑ n=1 ζs2(n)n−s. Since s2(3rn) ≡ s2(n) (mod 3), we may write A(s) = 1 1− 3−s ∞∑ 3-n ζs2(n)n−s. For i = (i1, i2) ∈ Z23, there are constants α(i) such that ∞∑ 3-n ζs2(n)n−s = ∑ i∈Z23 α(i) ∏ p≡1 (3) 1 1− ζi1p−s ∏ p≡2 (3) 1 1− ζi2p−s . If 3 - n, then s2(n) ≡ ∑ j1+j2=2 ( Ω3,1(n) j1 )( Ω3,2(n) j2 ) 2j2 (mod 3). 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 1 ζ ζ2 1 ζ ζ2 1 ζ ζ2 1 ζ2 ζ 1 ζ2 ζ 1 ζ2 ζ 1 1 1 ζ ζ ζ ζ2 ζ2 ζ2 1 ζ ζ2 ζ ζ2 1 ζ2 1 ζ 1 ζ2 ζ ζ 1 ζ2 ζ2 ζ 1 1 1 1 ζ2 ζ2 ζ2 ζ ζ ζ 1 ζ ζ2 ζ2 1 ζ ζ ζ2 1 1 ζ2 ζ ζ2 ζ 1 ζ 1 ζ2 α(0, 0) α(1, 0) α(2, 0) α(0, 1) α(1, 1) α(2, 1) α(0, 2) α(1, 2) α(2, 2) = 1 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 ( k1 j1 )( k2 j2 ) 2j2 . The coefficient matrix A satisfies A = 1 1 11 ζ ζ2 1 ζ2 ζ ⊗ 1 1 11 ζ ζ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 and obtain α(0, 2) = α(2, 0) = 12 + i √ 3 6 , α(1, 1) = −i√3 3 , and the rest to be 0. This enables us to write A(s) = ( 1 2 + i √ 3 6 ) exp [( ζ2 − 1 2 ) log (1− 3−s) ] exp [ − ( ζ 2 ) log ζ(s) ] × 2∑ j=1 exp [ (−1)j ( ζ2 − 1 2 ) logL(s, χ1) ] exp (ϕj(s)) − i √ 3 3 exp ((ζ − 1) log(1− 3−s)) exp (ζ log ζ(s)) exp (ϕ3(s)), 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 A(s) = ∑∞ n=1(−1)s3(n)n−s. It transpires that s3(n) (mod 2) is determined 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=0 α(j) ∏ p6=2 1 1− ijp−s . Equating coefficients in the Dirichlet series yields the system 1 1 1 1 1 i −1 −i 1 −1 1 −1 1 −i −1 i α(0) α(1) α(2) α(3) = (−1)(03) (−1)(13) (−1)(23) (−1)(33) = 1 1 1 −1 , with solutions α(0) α(1) α(2) α(3) = 1/2 −i/2 1/2 i/2 . This enables us to write A(s) = 1 2 ζ(s)− i 2 exp ((i− 1) log(1− 2−s)) exp (i log ζ(s)) exp(ϕ1(s)) + ( 1 2 )( 1 + 2−s 1− 2−s ) ζ(2s) ζ(s) + i 2 exp ((−i− 1) log(1− 2−s)) exp (−i log ζ(s)) exp(ϕ3(s)). Note the term 12ζ(s). Thus taking T = exp (√ log x ) , we can show 79 Chapter 7. Modular Distribution of Prime Symmetric Functions ∑ n≤x s3(n)≡0 (2) 1 = ∑ n≤x 1 + (−1)s3(n) 2 = bxc 2 + 1 2 ∑ n≤x (−1)s3(n) ∼ x 2 + ( 1 2 ) 1 2pii ∫ c+iT c−iT A(s)xs s ds ∼ x 2 + ( 1 2 ) 1 2pii ∫ c+iT c−iT ζ(s) 2 xs s ds ∼ x 2 + ( 1 2 ) Res ( ζ(s) 2 xs s ; s = 1 ) = x 2 + x 4 = 3x 4 . This density result is confirmed by empirical data: 80 Chapter 7. Modular Distribution of Prime Symmetric Functions Table 3. s3(n)-Modulo 2 x #{n ≤ x : s3(n) ≡ 0 (mod 2)} 1x#{n ≤ x : s3(n) ≡ 0 (mod 2)} 100 93 .93 1000 836 .836 5000 3954 .7908 10000 7743 .7743 20000 15232 .7616 30000 22654 .75513 50000 37350 .747 7.5.3 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−1κ −→ Zq by σ(k) = σ(k1, . . . , kq−1) = ∑ j1+···+jq−1=k ( k1 j1 ) · · · ( kq−1 jq−1 ) 1j1 · · · (q − 1)jq−1 . If ζ = e2pii/q, then ∑ n≤x sk(n)≡a (q) 1 ∼ x qκq−1 q−1∑ j=0 ∑ k∈Zq−1κ ζ(σ(k)−a)j . 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 r + 2 ) ζ ( 1 r + 1 )]r/(r+1) n1/(r+1)(log n)−r/(r+1), (8.1) where Γ(z) = ∫ ∞ 0 e−ttz−1 dt 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ős 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ős [4]. First let us revisit some important notation. The k-th difference function p(k)A (n) can defined inductively as follows: for k = 0, p(k)A (n) = pA(n). If k > 0, then p (k) A (n) = p (k−1) A (n)− p(k−1)A (n− 1). 82 Chapter 8. Partitions into Prime Powers Let f (k)A (x) be the generating function for p (k) A (n). We have [4] the fol- lowing power series identity: f (k) A (x) = ∞∑ n=0 p (k) A (n)x n (8.2) = (1− x)k ∞∑ n=0 pA(n)xn (8.3) = (1− x)k ∏ a∈A 1 1− xa . (8.4) This may be used to define p(k)A (n) for all k ∈ Z, including k < 0. Bateman and Erdős [4] characterize the sets A for which p(k)A (n) is ulti- mately nonnegative. Note that if k < 0, then the power series representation of (1− x)k has nonnegative coefficients so that p(k)A (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 lim n→∞ p (k) A (n) =∞. A simple consequence of this is the fact that pA(n) is eventually monotonic if k > 0. No explicit bounds for when p(k)A (n) ceases to take on negative values are included with the result of Bateman and Erdős [4]. By following their approach but specializing to the case when A = P, we shall find bounds for n depending on k which guarantee that p(k)P (n) ≥ 0. In a subsequent paper, Bateman and Erdős [3] prove that p(1)P (n) ≥ 0 for all n ≥ 2. That is, the sequence of partitions of n into primes is weakly in- creasing for n ≥ 1. We have shown [49] that if A = P(`) is the set of `-th pow- ers of primes, and F (k, `) = min {N ∈ N : n ≥ N implies that p(k)A (n) > 0}, then for a fixed ` ∈ N, logF (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 asymp- totic 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 A = P(`). Richmond finds [38] an asymptotic formula in n for p(k)A (n). Unfortunately, his formula is not useful towards finding bounds for when p (k) A (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 eαa − 1 − k eα − 1 . 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ős [4]. His result applies to A = P(`), and states that p (k+1) A (n) p (k) A (n) = O(n−1/2), as n→∞. We shall write ζn for the primitive n-th root of unity e2pii/n, and them-th prime by pm. We will have cause to use the so-called “primorial” notation, that is, let n# = ∏ p≤n p, 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 demon- strate that for a given k ∈ N, there exist h, h1 ∈ N depending on k such that if n ≥ h+ h1 − 1, then p(k)P (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 N(k) = min{N ∈ N : p(k)P (n) ≥ 0 for all n ≥ N}, then as k →∞, logN(k) kk(4+log 16) ( 1+O ( log log k log k )) . Following Bateman and Erdős [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. The function p(k)B (n) can be decomposed as follows: p (k) B (n) = g (k) B (n) + ψ (k) B (n), 84 Chapter 8. Partitions into Prime Powers where g(k)B (n) is a polynomial in n of degree r−k−1 with leading coefficient( (r − k − 1)!∏p∈B p)−1, and ψ(k)B (n) is periodic in n with period ∏p∈B p. Proof. We use partial fractions to decompose the generating function f (k)B (x) as follows: f (k) B (x) = 1 (1− x)r−k ∏ p∈B p−1∏ j=1 1 1− ζjpx (8.5) = α1 1− x + α2 (1− x)2 + . . .+ αr−k (1− x)r−k + ∑ p∈B p−1∑ j=1 β(ζjp) 1− ζjpx , (8.6) where the αi, and β(ζ j p) are complex numbers depending on k and the set B. Note that αr−k = ∏ p∈B p −1 . The power series expansion for (1− x)−h is given by 1 (1− x)h = ∞∑ n=0 ( n+ h− 1 h− 1 ) xn. Hence, if g (k) B (n) = r−k∑ h=1 αh ( n+ h− 1 h− 1 ) , and ψ (k) B (n) = ∑ q∈B q−1∑ j=1 β(ζjq )ζ jn q , then the lemma is proved. For the remainder of this section, g(k)B (n) and ψ (k) 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 β(ζjq ). To simplify notation a little, write βζ instead, when ζ is clear from 85 Chapter 8. Partitions into Prime Powers the context. In particular, suppose η = ζjq , where q ∈ B, and 0 < j < q. Then (1− ηx)f (k)B (x) = (1− x)k 1 1 + ηx+ · · ·+ (ηx)q−1 ∏ p∈B p6=q 1 1− xp = βη + (1− ηx) α1 1− x + · · ·+ αr−k (1− x)r−k + ∑ ζ 6=η βζ 1− ζx , hence, βη = (1− η̄)k q ∏ p∈B p6=q 1 1− η̄p . The following inequalities shall be useful: 1− θ 2 2 ≤ cos θ ≤ 1− θ 2 2 + θ4 24 , which holds for all values of θ. Note that |eiθ − 1| = √ 2(1− cos θ), so for −2√3 ≤ θ ≤ 2√3, |θ| √ 1− θ 2 12 ≤ |eiθ − 1| ≤ |θ|. In particular, for 0 ≤ θ ≤ pi, θ √ 1− θ 2 12 ≤ |eiθ − 1| ≤ θ. (8.7) Lemma 8.3. Suppose that ζ 6= 1 is a q-th root of unity, q ≥ 2, and let b0 = 2pi √ 1− pi212 . Then b0 q ≤ |1− ζ| ≤ 2. Proof. Clearly |1− ζ| ≤ 2. On the other hand, by the inequality (8.7), |1− ζ| ≥ |1− e2pii/q| ≥ 2pi q √ 1− 4pi 2 12q2 ≥ b0 q . 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 η = ζjq , for some q ∈ B, j ∈ {1, . . . , q − 1}. Then |βη| ≤ 2kqr−2 br−10 , if k ≥ 0; qr−k−2 br−k−10 , if k < 0. Proof. Making use of Remark 8.2 and Lemma 8.3 we have that for k ≥ 0: |βη| = |1− ζ −j q |k q ∏ p∈B p6=q 1 |1− ζ−jpq | ≤ 2 k q ∏ p∈B p6=q 1 |1− ζq| ≤ 2 k q ( q b0 )r−1 = 2kqr−2 br−10 . 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)B (n)| ≤ 2k br−10 ∑ p∈B p r−1, if k ≥ 0; 1 br−k−10 ∑ p∈B p r−k−1, if k < 0. 87 Chapter 8. Partitions into Prime Powers Proof. First assume that k ≥ 0. By Lemmas 8.4 and 8.1, |ψ(k)B (n)| = ∣∣∣∣∣∣ ∑ p∈B p−1∑ j=1 β(ζjp)ζ jn p ∣∣∣∣∣∣ ≤ ∑ p∈B p−1∑ j=1 |β(ζjp)| ≤ ∑ p∈B p−1∑ j=1 2kpr−2 br−10 = 2k br−10 ∑ p∈B (p− 1)pr−2 ≤ 2 k br−10 ∑ p∈B pr−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 dB(r0) = ∏ p∈B p−1∏ j=1 (|ζjp − 1| − r0). Then |αh| ≤ 1 rr−k−h0 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| = ∣∣∣∣ 12pii ∫ γ f (k) B (z)(z − 1)h−1 dz ∣∣∣∣ ≤ 1 2pi ∫ γ 1 |z − 1|r−k−h+1 ∏ p∈B p−1∏ j=1 1 |1− ζjpz| dz ≤ 1 rr−k−h0 dB(r0) . 88 Chapter 8. Partitions into Prime Powers Proposition 8.7. For k ≤ 0, and D1 ⊆ D2 ⊆ N, we have p(k)D2(n) ≥ p (k) D1 (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ős [4]. Proposition 8.8. Let D ⊆ N be an infinite set. For any t ∈ N, we have that pD(n) p (−1) D (n) ≤ 1 t+ 1 + (t− 1)2 t+ 1 n2t−3 p (−1) D (n) . 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 ∞∑ n=0 Pq(n)xn = ∑ {a1,...aq}⊆D xa1 1− xa1 · · · xaq 1− xaq . If Rq(m) is defined by ∞∑ m=0 Rq(m)xm = ∑ {a1,...aq}⊆[n] xa1 1− xa1 · · · xaq 1− xaq , where [n] = {1, . . . , n}, then Pq(n) ≤ Rq(n). There are ( n q ) 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 ( m− 1 q − 1 ) xm, so Pq(n) ≤ ( n q )( n− 1 q − 1 ) ≤ n2q−1. 89 Chapter 8. Partitions into Prime Powers Any partition n = n1a1 + · · ·nqaq, where a1, . . . , aq ∈ D, gives rise to a partition of n− ai for i = 1, . . . , q, namely n− a1 = (n1 − 1)a1 + n2a2 + · · ·+ nqaq, n− a2 = n1a1 + (n2 − 1)a2 + · · ·+ nqaq, ... n− aq = n1a1 + n2a2 + · · ·+ (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∑ q=1 qPq(n) ≤ n−1∑ m=0 pD(m). Now if t ∈ N, then p (−1) D (n) = n∑ m=0 pD(m) ≥ pD(n) + n∑ q=1 qPq(n) = (t+ 1)pD(n) + n∑ q=1 (q − t)Pq(n) ≥ (t+ 1)pD(n)− (t− 1) t−1∑ q=1 Pq(n) ≥ (t+ 1)pD(n)− (t− 1)2n2t−3, and the theorem is proved. A consequence of Proposition 8.8 is that for an infinite set D, lim n→∞ pD(n) p (−1) D (n) = 0. 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: g = ( 2 b0 )k+1∑ p∈B pk+1 − 1 , h = pk+2# ( 2 b0 )k+1∑ p∈B pk+1 , 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 = 12 |1− ζQ|, and d = ∏ p∈C1 Γ ( p+ 1 2 )2( pi2p−1 3p/2p2p−1 ) Γ((√3pi + 12) p+ 12) Γ ((√ 3 pi − 12 ) p+ 12 ) , Finally, let h1 = ⌈ Q#u pk+2# ( 2 d ( 2Q b0 )u + 1 + u2 4 (u− 1)u−1 )⌉ . Lemma 8.10. For all n ∈ N0, p(k)B (n) ≥ −g, and for all n ≥ h, p(k)B (n) ≥ 1. Proof. From Lemma 8.1, p (k) B (n) = g (k) B (n) + ψ (k) B (n). Then p (k) B (n) = g (k) B (n) + ψ (k) B (n) = α1 + α2(n+ 1) + ψ (k) B (n) ≥ α1 + α2 + ψ(k)B (n), 91 Chapter 8. Partitions into Prime Powers since α2 = 1/(pk+2#) > 0. But α1 + α2 = 1− ψ(k)B (0), so p (k) B (n) ≥ 1 + ∑ p∈B p−1∑ j=1 β(ζjp)(ζ jn p − 1) ≥ 1− 2 ∑ p∈B p−1∑ j=1 |β(ζjp)| ≥ 1− ( 2 b0 )k+1∑ p∈B pk+1, 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 p (k) B (n) ≥ α1 + α2 + ( 2 b0 )k+1∑ p∈B pk+1 + ψ(k)B (n) ≥ 1, reasoning as before. Lemma 8.11. If n ≥ h1 then (t− 1)2 t+ 1 n2t−3 p (−1) C1 (n) ≤ 1 t+ 1 , (8.8) and hence (t− 1)2 t+ 1 n2t−3 p (−1) C (n) ≤ 1 t+ 1 . (8.9) Proof. The second inequality follows from the first via Proposition 8.7. By Lemma 8.1, we may write p (−1) C1 (n) = g(−1)C1 (n) + ψ (−1) C1 (n), where g (−1) C1 (n) = u+1∑ h=1 αh ( n+ h− 1 h− 1 ) . By Lemma 8.6, we have |αh| ≤ 1 ru0dC1(r0) , 92 Chapter 8. Partitions into Prime Powers so g (−1) C1 (n) ≥ pk+2# Q# ( n+ u u ) − 1 ru0dC1(r0) u∑ h=1 ( n+ h− 1 h− 1 ) ≥ pk+2# Q# ( n+ u u ) − 1 ru0dC1(r0) ( n+ u u− 1 ) . Let δp = p−1∏ j=1 (|1− ζjp | − r0) , so that dC1(r0) = ∏ p∈C1 δp. Since all the elements of C1 are odd, making use of the inequalities (8.7), we have δp = p−1 2∏ j=1 (|1− ζjp | − r0)2 = p−1 2∏ j=1 |1− ζjp |2 ( 1− 1 2 |1− ζQ| |1− ζjp | )2 ≥ p−1 2∏ j=1 4pi2j2 p2 ( 1− pi 2j2 3p2 )( 1 2 )2 = p−1 2∏ j=1 pi2j2 p2 ( 1− pi 2j2 3p2 ) = Γ ( p+ 1 2 )2( pi2√ 3p2 )p−1 p−12∏ j=1 (√ 3p pi − j )(√ 3p pi + j ) = Γ ( p+ 1 2 )2( pi2p−1 3p/2p2p−1 ) Γ((√3pi + 12) p+ 12) Γ ((√ 3 pi − 12 ) p+ 12 ) . (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# Q# ( n+ u u ) − 1 ru0d ( n+ u u− 1 ) − ∑ p∈C1 ( p b0 )u ≥ u 2 4 nu−1. (8.11) 93 Chapter 8. Partitions into Prime Powers Together with the fact that via Lemma 8.3, 1 ru0 ≤ ( 2Q b0 )u , the inequality (8.11) is implied by n ≥ Q#u pk+2# ( n+u−1 u−1 ) 1 d ( 2Q b0 )u(n+ u u− 1 ) + ∑ p∈C1 ( p b0 )u + u2 4 nu−1 , (8.12) for n ≥ h1. It is easily deduced that h1 ≥ Quu and that (u− 1)u−1 (Quu)u−1 < bu0 uQu . Hence for n ≥ h1, we have( n+u u−1 )( n+u−1 u−1 ) = n+ u n+ 1 ≤ 2, 1( n+u−1 u−1 ) ∑ p∈C1 ( p b0 )u ≤ ( u− 1 n+ u− 1 )u−1 ∑ p∈C1 ( p b0 )u ≤ (u− 1) u−1 (Quu)u−1 ∑ p∈C1 ( p b0 )u < 1, and nu−1( n+u−1 u−1 ) ≤ nu−1(u− 1)u−1 (n+ u− 1)u−1 ≤ (u− 1) u−1. The inequality (8.12) is implied by n ≥ Q#u pk+2# [ 2 d ( 2Q b0 )u + 1 + u2 4 (u− 1)u−1 ] , 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) p (−1) C (n) ≤ 2 t+ 1 . 94 Chapter 8. Partitions into Prime Powers Theorem 8.13. If n ≥ h+ h1 − 1, then p (k) P (n) ≥ 0. Proof. The following identity is established by considering the generating function for p(k)P (n), and using the fact that P is the disjoint union of B and C: p (k) P (n) = n∑ m=0 p (k) B (n−m)pC(m). Thus, by Lemma 8.10 and Corollary 8.12, for n ≥ h+ h1 − 1, p (k) P (n) = n−h∑ m=0 p (k) B (n−m)pC(m) + n∑ m=n−h+1 p (k) B (n−m)pC(m) ≥ n−h∑ m=0 pC(m)− g n∑ m=n−h+1 pC(m) = p(−1)C (n)− (g + 1) n∑ m=n−h+1 pC(m) ≥ p(−1)C (n)− (g + 1)p(−1)C (n) n∑ m=n−h+1 pC(m) p (−1) C (m) ≥ p(−1)C (n)− (g + 1)p(−1)C (n)h ( 2 t+ 1 ) = p(−1)C (n)− p(−1)C (n) = 0. Next we will use the information in this section to compute an asymptotic bound in k. Theorem 8.14. Let N(k) = min{N ∈ N : p(k)P (n) ≥ 0 for all n ≥ N}. There is a function ε = ε(k) log log klog k such that as k →∞, logN(k) kk(4+log 16)(1+ε). 95 Chapter 8. Partitions into Prime Powers Proof. Clearly, logN(k) log h+ log h1. Now, log h log (pk+2#) + log ∑ p∈B pk+1 ∑ p∈B log p+ log ( pk+2k+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 log ( Q# pk+2# ) + log ( 1 d ) + u logQ. (8.14) But log ( Q# pk+2# ) k+2t∑ j=1 log pj k+2t∑ j=1 log j t log t since k < t, and (8.15) u logQ t log t. (8.16) Also, log ( 1 d ) ∑ p∈C1 | log δp|, (8.17) so we need to look at bounding δp and 1/δp, for p ∈ C1. By Stirling’s Formula (2.5) we have δp ≤ p−1 2∏ j=1 |1− ζjp |2 ≤ p−1 2∏ j=1 4pi2j2 p2 = ( 2pi p )p−1 Γ ( p+ 1 2 )2 ( 2pi p )p−1 pi(p− 1)p 2p−1ep−1 (pi e )p p. 96 Chapter 8. Partitions into Prime Powers On the other hand, if c1 = (√ 3 pi − 1 2 ) p− 1 2 , c2 = (√ 3 pi + 1 2 ) p− 1 2 and c3 = (√ 3 pi − 12 )(√3 pi − 1 2 ) (√ 3 pi + 1 2 )(√3 pi + 1 2 ) , then by (8.10) and Stirling’s formula, 1 δp ≤ ( 3p/2p2p−1 pi2p−1 ) Γ(c1 + 1) Γ ( p+1 2 )2 Γ(c2 + 1) ( 3p/2p2p−1 pi2p−1 ) 2p−1ep−1 pi(p− 1)p cc11 c2c2 √ c1 c2 ec2−c1 ( 2e2 √ 3c3 pi2 )p p2p−1p−2p ( 2e2 √ 3c3 pi2 )p( 1 p ) . We may conclude that | log δp| p, and so by (8.17) log ( 1 d ) ∑ p∈C1 p Q 2 logQ t2 log t. (8.18) In turn, by (8.13) through (8.16), we have that logN(k) t2 log t. (8.19) To complete the proof, we must bound t2 log t. Since t gh, and h pk+2#g we have t2 log t (gh)2 log h (pk+2#)2g4k log k (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≤n p < 4n. 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 ( log log k log k ))] = k(log 16)k ( 1+O ( log log k log k )) . (8.21) Next, g ( 2 b0 )k+1∑ p∈B pk+1 (k + 2) ( 2pk+2 b0 )k+1 k [( 2 b0 ) (k + 2) log (k + 2) ( 1 +O ( log log k log k ))]k+1 kk+2(log k)k+1 ( 2 b0 )k+1 [ 1 +O ( log log k log k )]k+1 (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)] kk(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: log p(k−1)P(r) (n) =(r + 1) [ Γ ( 1 r + 2 ) ζ ( 1 r + 1 )]r/(r+1) n1/(r+1)(log n)−r/(r+1) × ( 1 +O (√ (log log n)1+ log n )) , 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 proof of this fact. Indeed, they assume that for a given r, p(1)P(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ős [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: pi(x) = Li(x) + E(x), where, recalling if necessary Li(x) = ∫ x 2 1 log t dt; and E(x) = Oδ ( x logδ x ) , for all δ ≥ 2. 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 φ(s) = ∑ p e−sp r . Lemma 8.15. As s→ 0+, φ(s) = ∫ ∞ 2 e−sur log u du+Oδ ( 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− e−su r dpi(u) = ∫ ∞ 2− e−su r d(Li(u) + E(u)) = ∫ ∞ 2 e−sur log u du+ ∫ ∞ 2− e−su r dE(u). (8.23) Let C = C(s) = log−δ (1/s). Note that as s → 0+, s = o(C(s)). Assume that 2rs < C. Integration by parts gives∫ ∞ 2− e−su r dE(u) = rs ∫ ∞ 2 ur−1e−su r E(u) du+O(1) δ rs ∫ ∞ 2 ure−sur logδ u du+O(1) δ rδ ∫ ∞ 2rs ( t s )1/r e−t logδ (t/s) dt+O(1), via the substitution t = sur = Cs−1/r ∫ ∞ 2rs t1/re−t( log t log (1/s) + 1 )δ dt+O(1) = Cs−1/r ∫ C 2rs t1/re−t( log t log (1/s) + 1 )δ dt+ ∫ ∞ C t1/re−t( log t log (1/s) + 1 )δ dt +O(1). (8.24) 100 Chapter 8. Partitions into Prime Powers Now, ∫ C 2rs t1/re−t( log t log (1/s) + 1 )δ dt ∫ C 2rs t1/re−t( log (2rs) log (1/s) + 1 )δ dt = ∫ C 2rs t1/re−t( r log 2 log (1/s) )δ dt δ logδ (1/s) ∫ C 2rs t1/re−t dt δ 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∫ ∞ C t1/re−t( log t log (1/s) + 1 )δ dt ∫ ∞ C t1/re−t(−δ log log (1/s) log (1/s) + 1 )δ dt δ ∫ ∞ 0 t1/re−t dt δ 1. Hence by (8.24), ∫ ∞ 2− e−su r dE(u)δ Cs−1/r, which together with (8.23) completes the proof. Lemma 8.16. As s→ 0+,∫ ∞ 2 e−sur log u du = rΓ ( 1 r + 1 ) s−1/r(log (1/s))−1 +O ( s−1/r log log (1/s) log2 (1/s) ) . Proof. Making the substitution t = sur into the integral gives∫ ∞ 2 e−sur log u du = s−1/r ∫ ∞ 2rs t1/r−1e−t log (1/s) dt = s−1/r(log (1/s))−1(I1 + I2 + I3), (8.25) 101 Chapter 8. Partitions into Prime Powers where I1 = ∫ 1/ log2r (1/s) 2rs t1/r−1e−t 1 + log tlog (1/s) dt, I2 = ∫ log2 (1/s) 1/ log2r (1/s) t1/r−1e−t 1 + log tlog (1/s) dt, and I3 = ∫ ∞ log2 (1/s) t1/r−1e−t 1 + log tlog (1/s) dt. We will consider each of these integrals individually. For t ∈ [2rs, 1/ log2r (1/s)], log t/ log (1/s) is closest to −1 when t = 2rs. Hence I1 ∫ 1/ log2r (1/s) 2rs t1/r−1e−t 1 + log 2 rs log (1/s) dt, log (1/s) ∫ 1/ log2r (1/s) 2rs t1/r−1e−t dt log (1/s) ∫ 1/ log2r (1/s) 0 t1/r−1 dt 1 log (1/s) . (8.26) Now we consider I2. For t ∈ [1/ log2r (1/s), log2 (1/s)], we have 1 1 + log tlog (1/s) = 1 +O ( log log (1/s) log (1/s) ) , and so using integration by parts: I2 = ∫ log2 (1/s) 1/ log2r (1/s) t1/r−1e−t dt+O ( log log (1/s) log (1/s) ) =r [ t1/re−t ]log2 (1/s) 1/ log2r (1/s) + r ∫ ∞ 0 t1/re−t dt+O (∫ 1/ log2r (1/s) 0 t1/re−t dt ) +O (∫ ∞ log2 (1/s) t1/re−t dt ) +O ( log log (1/s) log (1/s) ) . But ∫ ∞ 0 t1/re−t dt = Γ ( 1 r + 1 ) , 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 r + 1 ) +O ( log log (1/s) log (1/s) ) . (8.27) Finally, I3 1log (1/s) ∫ ∞ log2 (1/s) t1/r−1e−t dt 1 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Γ ( 1 r + 1 ) s−1/r (log (1/s))−1 +O ( s−1/r log log (1/s) log2 (1/s) ) . Let k ∈ N, and define f(s) = ∞∑ n=0 p (k) P(r)(n)e −ns = (1− e−s)k ∏ p (1− e−spr)−1. That is, f(s) is the generating function in e−s of the kth difference function of pP(r)(n). Taking logarithms we have log f(s) = k log (1− e−s)− ∑ p log (1− e−spr) = k log (1− e−s) + ∑ p ∞∑ j=1 e−jspr j = k log (1− e−s) + ∞∑ j=1 1 j ∑ p e−jsp r = k log (1− e−s) + ∞∑ j=1 φ(js) j . (8.29) We wish to use our approximations for φ(s) to evaluate the sum ∑∞ j=1 φ(js) j . To do this we break up the sum into two parts. Let N = (1/s)/(log (1/s)). 103 Chapter 8. Partitions into Prime Powers Then by Corollary 8.17:∑ j≤N φ(js) j =rΓ ( 1 r + 1 ) s−1/r × ∑ j≤N 1 j1+1/r log (1/js) +O ∑ j≤N log log (1/js) j1+1/r log2 (1/js) . (8.30) Now, ∑ j≤N 1 j1+1/r log (1/js) = 1 log (1/s) ∑ j≤N 1 j1+1/r ( 1− log jlog (1/s) ) = 1 log (1/s) ∑ j≤N 1 j1+1/r + 1 log (1/s) ∑ j≤N log j j1+1/r ( 1− log jlog (1/s) ) =(log (1/s))−1 ( ζ ( 1 r + 1 ) +O ( 1 N1/r )) + 1 log2 (1/s) O ∑ j≤N 1 j1+1/2r ( 1− log jlog (1/s) ) . (8.31) We have, (log (1/s))−1 N1/r = O(s1/r), (8.32) and ∑ j≤N 1 j1+1/2r ( 1− log jlog (1/s) ) = Σ1 +Σ2, where Σ1 = ∑ j≤1/√s 1 j1+1/2r ( 1− log jlog (1/s) ) , and Σ2 = ∑ 1/ √ s<j≤N 1 j1+1/2r ( 1− log jlog (1/s) ) . But Σ1 ∑ j≤1/√s 1 j1+1/2r 1, 104 Chapter 8. Partitions into Prime Powers and Σ2 ∑ 1/ √ s<j≤N 1 j1+1/2r ( 1− logNlog (1/s) ) ∑ 1/ √ s<j≤N log (1/s) j1+1/2r log log (1/s) s 1/4r log (1/s) log log (1/s) , Hence ∑ j≤N 1 j1+1/2r ( 1− log jlog (1/s) ) 1. (8.33) We use a similar technique to bound the error term in (8.30). Write∑ j≤N log log (1/js) j1+1/r log2 (1/js) = 1 log2 (1/s) (Σ′1 +Σ ′ 2), where Σ′1 = ∑ j≤1/√s log log (1/js) j1+1/r ( 1− log jlog (1/s) )2 , and Σ′2 = ∑ 1/ √ s<j≤N log log (1/js) j1+1/r ( 1− log jlog (1/s) )2 . Then Σ′1 ∑ j≤1/√s log log (1/s) j1+1/r log log (1/s), and Σ′2 ∑ 1/ √ s<j≤N log log (1/s) j1+1/r ( 1− logNlog (1/s) )2 ∑ 1/ √ s<j≤N log2 (1/s) j1+1/r log log (1/s) s 1/2r log2 (1/s) log log (1/s) . 105 Chapter 8. Partitions into Prime Powers Hence, ∑ j≤N log log (1/js) j1+1/r log2 (1/js) log log (1/s) log2 (1/s) . (8.34) Next we must consider the tail of the sum ∑ φ(js)/j: ∑ j>N φ(js) j ∞∑ n=2 ∑ j>N e−jsn j 1 N ∞∑ n=2 ∑ j>N e−jsn 1 N ∞∑ n=2 e−Nsn 1− e−sn = 1 N ∑ 2≤n≤1/s e−Nsn 1− e−sn + 1 N ∑ n>1/s e−Nsn 1− e−sn 1 N ∑ 2≤n≤1/s e−Nsn sn + 1 N ∑ n>1/s e−Nsn log (1/s) ∞∑ n=2 e−Nsn + 1 N e−N 1− e−Ns log (1/s) e −2Ns 1− e−Ns + s log (1/s)e−1/(s log (1/s)) 1− e−Ns log2 (1/s)e−2/ log (1/s) + s log2 (1/s)e−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 r + 1 ) ζ ( 1 r + 1 ) s−1/r(log (1/s))−1+O ( 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. Let k, r ≥ 1, an = p(k)P(r)(n), An = ∑n i=0 ai = p (k−1) P(r) (n), and denote the following constants: A = rΓ ( 1 r + 1 ) ζ ( 1 r + 1 ) , B = (r + 1) [ Γ ( 1 r + 2 ) ζ ( 1 r + 1 )]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 logAn from above. Lemma 8.19. There exists a function β log log n/ log n such that for all n sufficiently large, logAn < Bn1/(r+1) (log n)r/(r+1) (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 C2 = N∑ j=0 |aj |. 107 Chapter 8. Partitions into Prime Powers Thus if n > N , then Ane −ns = N∑ j=0 aje −ns + n∑ j=N+1 aje −ns < N∑ j=0 aje −ns + n∑ j=N+1 aje −js = N∑ j=0 aj(e−ns − e−js) + n∑ j=0 aje −js < f(s) + C2, and so logAn <ns+ (1 + δ(s))As−1/r(log (1/s))−1 + log (1 + C2e−(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 As−(r+1)/r(log (1/s))−1 < n < 1 + δ(s) r As−(r+1)/r(log (1/s))−1. (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 s = [( A rn log (1/s) )( 1 +O ( log log (1/s) log (1/s) ))]r/(r+1) = [( A(r + 1) r2n log n )( 1 +O ( log log (1/s) log (1/s) ))]r/(r+1) = B (r + 1)(n log n)r/(r+1) ( 1 +O ( log log 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) ( 1 +O ( log log n log n )) + A(r + 1)(r+1)/rn1/(r+1) rB1/r(log n)r/(r+1) ( 1 +O ( log log n log n )) = Bn1/(r+1) (log n)r/(r+1) ( 1 +O ( log log n log n )) . Therefore, by (8.37), logAn < 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, logAn > Bn1/(r+1) (log n)r/(r+1) (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 log log x log x , then logA(x) < Bx1/(r+1) (log x)r/(r+1) (1 + η1(x)) . (8.43) Now f(s) = ∞∑ n=0 ane −ns = ∞∑ n=0 An(e−ns − e−(n+1)s) = s ∞∑ n=0 An ∫ n+1 n e−sx dx = s ∫ ∞ 0 A(x)e−sx dx. (8.44) The inequalities (8.36) together with equation (8.44) imply that exp ( (1− δ(s))As−1/r(log (1/s))−1 ) < s ∫ ∞ 0 A(x)e−sx dx < 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 correspond- ing m > 0 such that 1 s = r + 1 B (m logm)r/(r+1). (8.46) 110 Chapter 8. Partitions into Prime Powers Now, denote f(s) = s ∫ ∞ 0 A(x)e−sx dx = s (∫ m/H 0 + ∫ (1−ζ)m m/H + ∫ (1+ζ)m (1−ζ)m + ∫ Hm (1+ζ)m + ∫ ∞ Hm ) = J1 + J2 + J3 + J4 + J5, (8.47) where ζ = √ (log logm)1+ logm , andH > 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 J1 = s ∫ m/H 0 A(x)e−sx dx < 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 r (1− η) < logm 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− logHlogm )r/(r+1) < (1 + η3(s)) logmlog (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 logm ( 1− logHlogm )r/(r+1) <(1 + η3(s))A(r + 1)(r+1)/rr log (1/s) , (1 + η1(m/H))B(r+1)/r logm ( 1− logHlogm )r/(r+1) <(1 + η3(s))A(r + 1)(r+1)/rr log (1/s) , (1 + η1(m/H))Bm1/(r+1) (logm)r/(r+1) ( 1− logHlogm )r/(r+1) <(1 + η3(s))A(r + 1)(r+1)/rrB1/r log (1/s) ×m1/(r+1)(logm)1/(r+1) (1 + η1(m/H))Bm1/(r+1) (log (m/H))r/(r+1)H1/(r+1) < (1 + η3(s))A(r + 1) rH1/(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) H1/(r+1) ≤ 1 + δ(s) 2 . 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 r + 1 > 2(1 + C3/e) Hr/(r+1) . Then s = B (r + 1)(m logm)r/(r+1) > 2(1 + C3/e)B (Hm log (Hm))r/(r+1) ≥ 2(1 + η1(x))B (x log x)r/(r+1) for all x ≥ Hm, 112 Chapter 8. Partitions into Prime Powers and so (1 + η1(x))Bx1/(r+1) (log x)r/(r+1) < sx 2 , for all x ≥ Hm. Thus J5 = s ∫ ∞ Hm A(x)e−sx dx < s ∫ ∞ Hm exp [ Bx1/(r+1)(1 + η1(x)) (log x)r/(r+1) − sx ] dx < s ∫ ∞ 0 e−sx/2 dx = 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), J4(s) = s ∫ Hm (1+ζ)m A(x)e−sx dx < s ∫ Hm (1+ζ)m eψ(x) dx, 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 differen- tiation, it transpires that 1 s = ( 1 +O ( log log x0 log x0 )) r + 1 B x r/(r+1) 0 (log x0) r/(r+1). (8.50) Comparing this with (8.46), we conclude that logm log x0, and that x0 = ( 1 +O ( log log x0 log x0 )) 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 ξ2 d2 dx2 [ (1 + η1(x))x1/(r+1)(log x)−r/(r+1) ] ∣∣∣∣ 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 dx21 (1 + η1(x1)) [ x 1/(r+1) 1 (log x1) −r/(r+1) ] < −C4x1/(r+1)−21 (log x1)−r/(r+1) < −C5m1/(r+1)−2(logm)−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 ] × ∫ ∞ (ζ−η)m exp [ −C6ξ2m1/(r+1)−2(logm)−r/(r+1) ] dξ. The integral on the right-hand side of this inequality is simplified by observ- ing that it is of the form ∫ ∞ D e−Cx 2 dx, for C,D > 0. Substituting u2 = Cx2 − CD2, we have that∫ ∞ D e−Cx 2 dx = 1√ C ∫ ∞ 0 ue−CD2−u2√ u2 + CD2 du < e−CD2√ C ∫ ∞ 0 e−u 2 du = e−CD2 2 √ pi C . Hence with D = (ζ − η)m, and C = C6m1/(r+1)−2(logm)−r/(r+1), there is a C7 > 0 such that J4(s) s exp [ (1 + η)As−1/r(log (1/s))−1 − C7ζ2m1/(r+1)(logm)−r/(r+1) ]√ m1/(r+1)−2(logm)−r/(r+1) . (8.56) 114 Chapter 8. Partitions into Prime Powers Now, by definition of m, s√ m1/(r+1)−2(logm)−r/(r+1) = s √ m(m logm)r/(r+1) √sm 1√ s1/r log (1/s) . As we similarly have s−1/r(log (1/s))−1 m1/(r+1)(logm)−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 (1−ζ)m A(x)e−sx dx (8.59) Since A(x) is eventually increasing, we have exp [ (1− δ1(s))As−1/r(log (1/s))−1 ] < sA((1 + ζ)m) ∫ (1+ζ)m (1−ζ)m e−sx dx. 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)(logm)−r/(r+1) ( 1 +O ( log logm logm ))] . 115 Chapter 8. Partitions into Prime Powers Now, equation (8.46) yields eζsm − e−ζsm = e ζBr+1m1/(r+1)(logm)−r/(r+1) ( 1− e− 2ζBr+1m1/(r+1)(logm)−r/(r+1) ) , and so by (8.60), A((1 + ζ)m) > exp [ Bm1/(r+1)(logm)−r/(r+1) ( 1− ζ r + 1 +O ( log logm logm ))] . (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 = n 1 + ζ into (8.61), and observing that logm 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, log p(k−1)P(r) (n) =(r + 1) [ Γ ( 1 r + 2 ) ζ ( 1 r + 1 )]r/(r+1) n1/(r+1)(log n)−r/(r+1) × ( 1 +O (√ (log log n)1+ log n )) , 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 integerm, are two sets which we define as follows: Bm = {n ∈ N : s(n) = m,n 6= m}, and (9.1) Bm = {n ∈ N : s(i)(n) = m for some i ≥ 0}. (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} ∪ ⋃̇ p≥5 Bp , (9.3) 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} ∪ ( ⋃̇ n∈Bm Bn ) , (9.4) 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 ofBp(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 5 7 11 13 17 19 23 29 31 37 5000 1426 810 327 374 152 184 121 62 86 56 10000 2830 1605 649 714 306 377 213 134 172 104 15000 4188 2397 941 1049 497 573 306 183 241 156 20000 5534 3202 1241 1400 677 780 426 235 316 200 25000 6846 3996 1556 1737 856 976 538 285 392 235 30000 8197 4812 1860 2066 1027 1175 664 341 472 289 35000 9547 5597 2156 2421 1203 1358 788 404 552 332 40000 10879 6380 2477 2758 1360 1566 900 462 622 374 45000 12217 7176 2785 3086 1506 1755 1012 520 703 423 50000 13585 7964 3081 3440 1667 1948 1118 585 776 463 55000 14879 8742 3367 3767 1809 2157 1251 642 850 522 60000 16226 9509 3662 4111 1964 2351 1356 698 927 572 65000 17599 10319 3938 4453 2088 2542 1473 765 998 620 70000 18967 11049 4237 4812 2243 2734 1597 827 1068 672 75000 20288 11858 4512 5138 2383 2927 1707 882 1128 706 80000 21643 12677 4820 5458 2535 3123 1832 939 1198 764 85000 22976 13450 5126 5819 2680 3297 1937 998 1279 801 90000 24340 14243 5417 6128 2826 3472 2059 1063 1353 849 95000 25655 15017 5736 6483 2993 3669 2175 1125 1413 898 100000 27023 15753 6032 6821 3146 3837 2289 1194 1497 937 119 Chapter 9. Sequences of Iterates x\p 41 43 47 53 59 61 67 71 73 79 5000 51 70 40 37 28 45 22 27 33 22 10000 88 113 88 76 50 85 58 52 74 43 15000 139 170 139 97 77 124 84 76 110 65 20000 180 221 189 128 101 158 102 103 139 82 25000 221 289 223 156 121 193 124 130 171 110 30000 260 346 263 187 145 231 143 153 191 126 35000 287 398 303 221 171 266 168 171 212 146 40000 331 453 340 253 199 303 188 195 243 165 45000 368 520 375 275 225 341 213 220 272 183 50000 396 588 409 312 246 367 235 239 305 206 55000 441 643 449 345 275 399 258 259 341 226 60000 469 705 492 378 294 437 289 271 374 244 65000 503 757 523 403 318 469 304 293 416 268 70000 537 804 565 434 335 503 325 323 455 284 75000 577 869 597 474 362 536 350 351 493 306 80000 609 921 640 498 390 567 365 371 523 323 85000 647 983 678 527 406 613 385 398 557 341 90000 682 1041 704 567 435 638 397 413 592 366 95000 708 1092 752 593 454 672 417 430 625 384 100000 747 1161 792 626 477 719 444 444 658 401 120 Chapter 9. Sequences of Iterates Table 5. Selected Values of Bp(x)/x x\p 5 7 11 13 17 19 23 29 31 37 5000 .2852 .1620 .0654 .0748 .0304 .0368 .0242 .0124 .0172 .0112 10000 .2830 .1605 .0649 .0714 .0306 .0377 .0213 .0134 .0172 .0104 15000 .2792 .1598 .0627 .0699 .0331 .0382 .0204 .0122 .0161 .0104 20000 .2767 .1601 .0621 .0700 .0339 .0390 .0213 .0118 .0158 .0100 25000 .2738 .1598 .0622 .0695 .0342 .0390 .0215 .0114 .0157 .0094 30000 .2732 .1604 .0620 .0689 .0342 .0392 .0221 .0114 .0157 .0096 35000 .2728 .1599 .0616 .0692 .0344 .0388 .0225 .0115 .0158 .0095 40000 .2720 .1595 .0619 .0690 .0340 .0392 .0225 .0116 .0156 .0094 45000 .2715 .1595 .0619 .0686 .0335 .0390 .0225 .0116 .0156 .0094 50000 .2717 .1593 .0616 .0688 .0333 .0390 .0224 .0117 .0155 .0093 55000 .2705 .1590 .0612 .0685 .0329 .0392 .0227 .0117 .0155 .0095 60000 .2704 .1585 .0610 .0685 .0327 .0392 .0226 .0116 .0155 .0095 65000 .2708 .1588 .0606 .0685 .0321 .0391 .0227 .0118 .0154 .0095 70000 .2710 .1578 .0605 .0687 .0320 .0391 .0228 .0118 .0153 .0096 75000 .2705 .1581 .0602 .0685 .0318 .0390 .0228 .0118 .0150 .0094 80000 .2705 .1585 .0603 .0682 .0317 .0390 .0229 .0117 .0150 .0096 85000 .2703 .1582 .0603 .0685 .0315 .0388 .0228 .0117 .0150 .0094 90000 .2704 .1583 .0602 .0681 .0314 .0386 .0229 .0118 .0150 .0094 95000 .2701 .1581 .0604 .0682 .0315 .0386 .0229 .0118 .0149 .0095 100000 .2702 .1575 .0603 .0682 .0315 .0384 .0229 .0119 .0150 .0094 121 Chapter 9. Sequences of Iterates x\p 41 43 47 53 59 61 67 71 73 79 5000 .0102 .0140 .0080 .0074 .0056 .0090 .0044 .0054 .0066 .0044 10000 .0088 .0113 .0088 .0076 .0050 .0085 .0058 .0052 .0074 .0043 15000 .0093 .0113 .0093 .0065 .0051 .0083 .0056 .0051 .0073 .0043 20000 .0090 .0111 .0095 .0064 .0051 .0079 .0051 .0052 .0070 .0041 25000 .0088 .0116 .0089 .0062 .0048 .0077 .0050 .0052 .0068 .0044 30000 .0087 .0115 .0088 .0062 .0048 .0077 .0048 .0051 .0064 .0042 35000 .0082 .0114 .0087 .0063 .0049 .0076 .0048 .0049 .0061 .0042 40000 .0083 .0113 .0085 .0063 .0050 .0076 .0047 .0049 .0061 .0041 45000 .0082 .0116 .0083 .0061 .0050 .0076 .0047 .0049 .0060 .0041 50000 .0079 .0118 .0082 .0062 .0049 .0073 .0047 .0048 .0061 .0041 55000 .0080 .0117 .0082 .0063 .0050 .0073 .0047 .0047 .0062 .0041 60000 .0078 .0118 .0082 .0063 .0049 .0073 .0048 .0045 .0062 .0041 65000 .0077 .0116 .0080 .0062 .0049 .0072 .0047 .0045 .0064 .0041 70000 .0077 .0115 .0081 .0062 .0049 .0072 .0046 .0047 .0065 .0041 75000 .0077 .0116 .0080 .0063 .0048 .0071 .0046 .0047 .0066 .0041 80000 .0076 .0115 .0080 .0062 .0049 .0071 .0046 .0046 .0065 .0040 85000 .0076 .0116 .0080 .0062 .0048 .0071 .0045 .0047 .0066 .0040 90000 .0076 .0116 .0078 .0063 .0048 .0071 .0044 .0046 .0066 .0041 95000 .0075 .0115 .0079 .0062 .0048 .0071 .0044 .0045 .0066 .0040 100000 .0075 .0116 .0079 .0063 .0048 .0072 .0044 .0044 .0066 .0040 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 unre- solved. 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 often approximately pi 2n 12 logn , is the average value of s (i)(n) asymptotic to the i-th composition of pi 2n 12 logn 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 {m ∈ N : s(i)k (m) = n, for some i ≥ 0} is infinite, then it has a positive asymptotic density. 122 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 B(x) B(x)/x 5000 40 .00800 10000 54 .00540 15000 68 .00453 20000 85 .00425 25000 96 .00384 30000 107 .00357 35000 117 .00334 40000 132 .00330 45000 144 .00320 50000 153 .00306 55000 165 .00300 60000 188 .00313 65000 199 .00306 70000 210 .00300 75000 222 .00296 80000 232 .00290 85000 241 .00284 90000 253 .00281 95000 263 .00277 100000 276 .00276 It should be noted however, that it is still well within the range of pos- sibility 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 under- stood for k ≥ 2, because ek-sequences tend to fluctuate unpredictably. This makes sense since the average value of ek(n) 1 x ∑ n≤x ek(n) ∼ ζ(k + 1)x k (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 Bn(x) = 1 + ∑ m∈Bn Bm(x). (9.5) 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 · 3bm/3c, 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) 6= 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 tom. 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(α) = e2piiα, for 0 ≤ α ≤ 1, let f(α) = ∑ n≤x e(αs(n)). Then #{n ≤ x : s(n) = m} = ∫ 1 0 f(α)e(−αm) dα. 125 Chapter 9. Sequences of Iterates Ideally, we would proceed by estimating f(α) when α = a/q, a ratio- nal number in lowest terms. Clearly f(0) = f(1) = bxc. In Chapter 7 we bounded the absolute value of sums of the form f(a/q) using Perron’s for- mula. 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 f(1/2) ≈ 1 2pii ∫ c+iT c−iT 1 + 2−s 1− 2−s ζ(2s) ζ(s) xs s ds, 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 2pii ∫ c+iT c−iT 1 (1− 3−s)3/2 exp ∑ p ∞∑ j=2 (ζpj − ζpj )p−js/j L(s, χ)i√3/2ζ(s)−1/2xs s ds, 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 s(k)(n) ≤ n 2k + 2 2k−1 + 2 2k−2 + · · ·+ 2, < n 2k + 4. 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 s(k)(n) < n 2dk/2e · 3bk/2c + 22 5 . Proof. This can be verified numerically for n = 2, 3, 4, 5. For n > 5, we have seen that s(n) ≤ n 2 + 2, 127 Chapter 9. Sequences of Iterates when n is not prime, so by the preceding remarks, s(2)(n) ≤ n 2 · 3 + 2 3 + 3 s(3)(n) ≤ n 22 · 3 + 2 2 · 3 + 3 2 + 2 s(4)(n) ≤ n 22 · 32 + 2 2 · 32 + 3 2 · 3 + 2 3 + 3, and in general, s(2k−1)(n) ≤ n 2k · 3k−1 + 2 k−1∑ i=0 1 2i · 3i + 3 2 k−2∑ i=0 1 2i · 3i < n 2k · 3k−1 + 7 2 ∞∑ i=0 1 6i s(2k)(n) ≤ n 2k · 3k + 2 3 k−1∑ i=0 1 2i · 3i + 3 k−1∑ i=0 1 2i · 3i < n 2k · 3k + 11 3 ∞∑ i=0 1 6i . Combining these we have that s(k)(n) < n 2dk/2e · 3bk/2c + 22 5 . Proposition 9.6. If n ≥ 2, then t(n) < 2 log n log 6 + 2 log 5 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) < n 2dk/2e · 3bk/2c + 22 5 , and so 2dk/2e · 3bk/2c < 5 3 n. But 2dk/2e · 3bk/2c ≥ 6k/2 √ 2 3 , so 6k/2 < 5√ 6 n. 128 Chapter 9. Sequences of Iterates This implies that k + 1 < 2 log n log 6 + ( 2 log (5/ √ 6) log 6 + 1 ) = 2 log n log 6 + 2 log 5 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 + ∑ m∈Bn Bm(x) = 1 + ∑ m∈Bn Bm(x). (9.6) Proposition 9.7. The average order of t(n) has the following expressions:∑ n≤x t(n) = 2 + ∑ 2≤n≤x Bn(x) = 1 + bxc+ ∑ 2≤n≤x ∑ m∈Bn Bm(x) 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 each n, 2 ≤ n ≤ x once for each m ≤ x satisfying s(i)(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 ∑ n≤x t(n) x log log x. Indeed, consider the following table of values: 129 Chapter 9. Sequences of Iterates Table 7. Average Order of t(n) x ∑ n≤x t(n) ∑ n≤x t(n) 1 x log x ∑ n≤x t(n) 1 x log log x 5000 19571 .4595645436 1.827283521 10000 40471 .4394082995 1.822749691 15000 61620 .4272133008 1.814962097 20000 83104 .4195693666 1.812213183 25000 104673 .4134563567 1.808472967 30000 126593 .4093302983 1.808719966 35000 148545 .4056294504 1.807668137 40000 170568 .4024107756 1.806453766 45000 192657 .3995799640 1.805230307 50000 215000 .3974203434 1.805678899 55000 237041 .3948512538 1.803168591 60000 259322 .3928371307 1.802284432 There is a heuristic argument that lends credence to the possibility that∑ n≤x t(n) ∼ Cx log log x for some constant C > 0. In Section 5.2, we saw that s(n) ≤ xα a posi- tive proportion of the time on the interval [1, x]. Iterating the function xα j times gives us xα j . Setting xα j ≤ c for some constant c, we see that the min- imum 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′ = p′1 · · · p′r which is first sk-defective of order r, and such that p′i ≤ 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 pi1 · · · pir−k + M n . This is implied by 1 > ( r k ) 1 2r−k + M 2r . (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′ = p′1 · · · p′r, where p′1 ≤ . . . ≤ p′r, be one such number. Then since sk(n′) < n′, we have that 1 > ∑ 1≤i1<...<ir−k≤r 1 p′i1 · · · p′ir−k = α. Now if n = p1 · · · pr, where p1 ≤ . . . ≤ pr and pi ≥ p′i 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 1 pi1 · · · pir−k + M n ≤ α+ M n . If we choose n large enough such that M n < 1− α 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′ = p′1 · · · p′r of order r such that p′i ≤ pi. This proves the lemma. The following corollary is a companion to Corollary 4.3, and is an im- mediate 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 (s+ b)-cycles 1 {1},{6},{7,8} 2 {8} 3 {9},{10} 4 {11,15,12}, {13,17,21,14} 5 {12},{13,18},{14} 6 {14,15} 7 {15} 8 {16} 9 {17,26,24,18}, {22} 10 {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 In- troductory 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, rel- ative 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. Stu- dent, 61 (1992), 54-56. 135 Bibliography [13] Cohen, G. L. and te Riele, H. J. J., Iterating the sum of divisors func- tion, 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 Associ- ation of America, (1999). [16] Erdős, 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. Pan- jab. Univ. (N.S.), 21 (1970), 251-253. [19] Hardy, G. H. and Ramanujan, S., Asymptotic formulae for the distri- bution 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 fac- tors, 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. [25] Kerawala, S. M., On the asymptotic values of ln pA(n) and ln p (d) A (n) with A as the set of primes, J. Natur. Sci. and Math. 9 (1969), 209- 216. [26] Lal, M., Iterates of a Number-Theoretic Function,Mathematics of Com- putation 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 York- Washington-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-Chichester- Brisbane-Toronto-Singapore, 1991. [35] Pomerance, C., Multiply perfect numbers, Mersenne primes and effec- tive 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ős, 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), 16- 17. [41] te Riele, H. J. J., Hyperperfect numbers with three different prime fac- tors, Mathematics of Computation, 36 (1981), 297-298. 137 Bibliography [42] Tattersall, J. J., Elementary Number Theory in Nine Chapters, Cam- bridge University Press, 1999. [43] Turán, 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/Newton- GirardFormulas.html [45] Eric W. Weisstein et al. “Symmetric Polyno- mial.” 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 differ- ence functions, Accepted for publication in the Canadian Journal of Mathematics in 2006. [49] Woodford, R., Bounds for the Eventual Positivity of Difference Func- tions 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 Func- tions, 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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Partitions into prime powers and related divisor functions
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Partitions into prime powers and related divisor functions Mullen Woodford, Roger 2008
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Partitions into prime powers and related divisor functions |
Creator |
Mullen Woodford, Roger |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | 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. |
Extent | 659963 bytes |
Subject |
Analytic number theory Combinatorial number theory Pure mathematics Theory of partitions |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-08-01 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0066490 |
URI | http://hdl.handle.net/2429/1246 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2008-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2008_fall_mullenwoodford_roger.pdf [ 644.5kB ]
- Metadata
- JSON: 24-1.0066490.json
- JSON-LD: 24-1.0066490-ld.json
- RDF/XML (Pretty): 24-1.0066490-rdf.xml
- RDF/JSON: 24-1.0066490-rdf.json
- Turtle: 24-1.0066490-turtle.txt
- N-Triples: 24-1.0066490-rdf-ntriples.txt
- Original Record: 24-1.0066490-source.json
- Full Text
- 24-1.0066490-fulltext.txt
- Citation
- 24-1.0066490.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0066490/manifest