Prime Symmetric Divisor Functions by Roger Woodford B . S c , Univers i ty of M a n i t o b a , 2003 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Maste r of Science i n T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Mathemat ics) The University of British Columbia Augus t 2005 © Roger Woodford , 2005 Abstract In this thesis, we s tudy a new class of divisor-related functions: the pr ime symmetr ic functions. T h e elementary pr ime symmetr ic functions are denned on the nonnega-tive integers. T h e y take the values of the elementary symmetr ic functions appl ied to the multi-set of pr ime factors w i t h repet i t ion of an integer n. These functions are first defined i n [20]. In this thesis, we refine some of the definitions presented there, and revisit some of the key results regarding such functions. T h e pr ime symmetr ic functions are polynomials over Q i n the elementary pr ime symmetr ic functions, w i t h values i n Z . W e look at basic properties of prime symmetr ic functions. We s tudy the effect of i te ra t ion of these functions, and look at the question: when does i tera t ing produce cycles? We consider the inverse question of when and i n how many ways a number n can be expressed as f(m) for certain predetermined pr ime symmetr ic functions / . A s well , we look at asymptot ic approximat ions for certain classes of pr ime symmetr ic functions. i i Contents A b s t r a c t ii Contents ii i Acknowledgements v Dedicat ion v i 1 Div i sor Functions 1 1.1 Perfect Numbers , Var ia t ions on Perfect Numbers , and A l i q u o t Se-quences 2 2 P r i m e Symmetr i c Div i sor Functions 5 2.1 E lementa ry P r i m e Symmet r ic Div i sor Funct ions 6 2.2 Bas i c Proper t ies of the Elementary P r i m e Symmet r i c Funct ions . . . 9 3 T h e Second P r i m e Symmetr ic Funct ion 13 3.1 fi(n)=3 14 3.2 n(n) = 4 14 3.3 n(n) = 5 15 3.4 A n Inverse P r o b l e m 16 4 Higher E lementary P r i m e Symmetr ic Functions , 23 4.1 T h e H u n t for s 3 -cycles 26 i i i 5 T h e E x p o n e n t P r i m e Symmetr ic Div i sor Functions 32 5.1 T h e Average Order of 35 6 Further P r i m e Symmetr ic Functions 41 A p p e n d i x A M a p l e A lgor i thms 46 B ib l iography 49 iv Acknowledgements I wou ld like to acknowledge the encouragement and support of m y supervisors D r . Izabel la L a b a , and D r . Denis Sjerve, as well as the N a t u r a l Sciences and Engineer ing Research C o u n c i l for their generous funding. R O G E R W O O D F O R D The University of British Columbia August 2005 For She who is better t han rubies, who dwells w i t h prudence, and finds out knowledge of w i t ty inventions, B y w h o m kings reign and princes decree justice, W h o loves t hem that love her, and is found by those who seek her early, Whose fruit is better than gold; and whose revenue than choice silver, W h o was set up from everlasting, from the beginning, or ever the ear th was, Whose delights were i n the sons of men. v i Chapter 1 Divisor Functions T h e divisor function a : N —* N defined by d\n has been thoroughly s tudied for centuries. T h e first most na tura l general izat ion of the divisor funct ion are the divisor functions aa defined by <rQ(n) = X > , d\n Where a > 0 is a real number. W i t h this definition, OYJ counts the number of posit ive divisors of n. Sometimes o~o is denoted by d, and a\ is s imply a. Other relevant divisor-related functions are to, wh ich counts the number of dis t inct primes d i v i d i n g a number n , and Q, which counts the number of primes d i v i d i n g n, w i t h mul t ip l ic i ty . T h e functions aa are mul t ip l ica t ive , that is if m and n are relat ively pr ime, then <ja(mn) = aa(m)crQ(n). Derivat ions for the asymptot ic formulae of the average orders for aa can be found i n . [1]. In case a = 0, we have that for a l l x > l , d{n) = s l o g x + (2C - l)x + 0(y/x), n<x I where C is Eu le r ' s constant. A l s o , J2°(n) = J2x2 + 0(x\og x). n<x Furthermore , for a > 0, and a ^ 1, we have ^ M » ) = ^ a + 1 + o ( / ) , n<x where (3 = m a x { l , a } , and ( is the Riemann-ze ta function. I n this exposi t ion, we w i l l define and s tudy a new class of divisor functions: the pr ime symmetr ic divisor functions. These functions need not be mul t ip l ica t ive . T h e notions of perfect numbers, and aliquot sequences, and some of their gener-al izat ions based on the usual mul t ip l ica t ive divisor functions, or related functions, w i l l be extended to the prime symmetr ic divisor functions. 1.1 Perfect Numbers, Variations on Perfect Numbers, and Aliquot Sequences Several good texts detai l ing the basic theory of perfect numbers exist, see for instance [2], [6], [9], and [17]. In addi t ion, many variations on perfect numbers have been denned and studied. Examples can be found i n [4], [7], [8], [10], [11], [14], [15] and [16]. L e t <x*(n) = a(n)—n, that is cr*(n) sums al l the proper divisors of n . W e say that n is perfect i f a*(n) = n, excessive (or abundant) i f <7*(n) > n , and defective (or deficient) i f a*(n) < n. T h e first few perfect numbers are 6, 28, 496, 8128, 33550336. It has been known since E u c l i d ' s day that if p, and q = 2 P — 1 are pr ime, then the number n = 2 P _ 1 ( 2 P — 1) is perfect. T h i s can be readily checked, since its proper divisors correspond to the set { 1 , 2 , . . . , 2 P _ 1 , q, 2q,..., 2p~2q}, and hence 2 their sum is: a*(n) = 1 + 2 + • • • + 2p~l + q + 2q+--- + 2p~2q = 2 P - 1 + q{2p~l - 1) = (2p - l)2p~l = n. Euler proved conversely, that any even perfect number must be of this form. The proof is the same as that found in [12]. Theorem 1 An even number n is perfect if and only if n = 2p~lq, where p, and q — 2p — \ are both prime. Proof. We need only prove the only if part. Suppose n is an even perfect number. Write n = 2k~1m, where 2 f e~1||n, and so k > 2, and m is odd. Since o(n) = 2n, we have:' 2n = 2km = o{2k-1m) = (2k - l)er(m). Hence, 2k — 1 divides m, so we may write m = (2fc — Using this value of m, we get 2ke = o((2k -1)£). If £ > 1, then 1, £, and (2k — 1)£ are distinct divisors of m, and so 2k£ = o((2k - 1)£) >l+£+(2k-1)£ = 2k£ + 1, a contradiction. Thus £ = 1 and so 2k = a(2k - 1) = 1 + (2fe - 1) + ]T d, d\(2k-l) 1 < d < 2k - 1 so clearly, 2k — 1 must be prime. Furthermore, it is trivial to see that if k is composite, then 2k — 1 factors, thus q is also prime. • It is still not known if there are infinitely many even perfect numbers, or equivalently, if there are infinitely many Mersenne primes (primes of the form 2 P —1). It is also unknown whether or not there exists an odd perfect number. 3 T h e equivalent definit ion for a perfect number, i.e. n is perfect if a(n) = 2n motivates one generalization, that of multiperfect numbers. A number n is said to be &:-multiperfect i f <r(n) = kn. For instance, <x(120) = 360, so 120 is 3-multiperfect. A s already stated, there are numerous variations of the not ion of perfect number. T h e sequence {c*^(n)}^L0 is cal led the aliquot sequence of n , that is the aliquot sequence of n is obtained from n by i terat ing the sum of proper divisors funct ion a*. The aliquot sequence of a number n can fluctuate up and down. T h e unsolved Catalan-Dickson problem is to determine whether for every n , the sequence {t7*(fc) (n) }^LQ is eventually periodic. Instances are known when the shortest per iod is longer than 1. For instance: 12496 14288 15472 14536 14264 12496. T h e case when the per iod is of length 2 has a special name. If o-*^2\n) = n ^ cr*(n), then the pair {n,o*(n)} is cal led amicable. One such amicable pair is {220,284}. 4 Chapter 2 Prime Symmetric Divisor Functions T h e pr ime symmetr ic divisor functions are defined i n terms of the elementary sym-metr ic divisor functions. In this paper, we w i l l denote the set of nonnegative integers N u { 0 } b y N o . Definit ion 1 Let k € N o . Define : N o —> N o as follows: if n = 0, then Sfc(0) = 0, for all k. Forn > 0, if k = 0, Sfc(n) = 1. Ifk>0, andn = p\ • • -pr, where r = Q(n) is the number of prime factors (with multiplicity) of n, then where the sum is taken over all products of k prime factors from the multi-set { p i , . . . ,pr}- We say Sk is the kth elementary prime symmetric function. Note that i f k > r , then the s u m is empty, so Sfc(n) = 0. Definit ion 2 A function f : N o —> Z is called a prime symmetric function if it can be expressed as a polynomial over Q in the elementary prime symmetric functions S 0 , S i , . . . . 5 N o w we w i l l extend the not ion of perfection, aliquot sequences, etc. to more general classes of functions. Definition 3 Let S C Z , and suppose f : S —» Z . If n e 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 { / ^ ( n ) } ? | 0 is well defined, then it is called the f-sequence of n. If the sequence {/^ Hn)}f=o * s well-defined, we say it is an f -sequence of length e. A finite sequence {no,... ,n(} is an f-cycle of length t if the following con-ditions are satisfied: 1. t> 1, 2. n o , . . . , nt-i are distinct and n( = no, and 3. f(ni) = n i + 1 , fori = 0,1,...,£-1. 2.1 Elementary Prime Symmetric Divisor Functions Observe that i f J7(n) < k, we have s^(n) = 0. There is an alternate way of defining the functions Sfc. G i v e n n = pi • • -pr e N, set R Sn(x)=Y[(l+Pix). i=l T h e n Sfc(n) is the coefficient of xk i n Sn(x). T h e empty product is taken to be 1. Example 1 s 0 (12) = 1, S!(12) = 2 + 2 + 3 = 7, s 2 (12) = 2 - 2 + 2 - 3 + 2 - 3 = 16, s 3 (12) = 12, and s 4 (12) = 0. If f2(n) = k, then we t r i v i a l l y have that n is s^-perfect. T h i s is rather uninteresting, so we define a related version of Sfc-perfection to avoid this. 6 D e f i n i t i o n 4 Let n € N satisfy Q(n) > k. If Sfc(n) = n, then we say that n is s*k-perfect. If s^(n) > n, then we say that n is s^-special. E x a m p l e 2 If p is prime, then pp is an s*_i-perfect number, since sP-i{f)=(j)P_^J?-l=Pp. In fact, this example has a form of converse, first proved i n [20]: T h e o r e m 2 The prime power pa is s*k-perfect if and only if a = p and k = p — 1. Proof. We have seen that this is sufficient, now suppose k < a, and Sk(pa) = pa • T h e n For 1 < k < a — 1, (£) is divis ible by two dis t inct pr ime factors, hence we must have k = 1 or a — 1. N o w 4 = 2 2 , is the only sj-perfect number, and corresponds to the case where k = 1 = a — 1. Hence we may assume k — a — 1, wh ich from (2.1) implies that ct — p and k = p — 1. T h i s proves the theorem. • T h e next na tura l question to ask is: when is paq@ an s^-perfect number for some fc? T h i s turns out to be substantial ly more difficult t han the previous question. However, we w i l l come up w i t h some necessary condit ions and also look at some special cases. T h e o r e m 3 Suppose that p and q are distinct primes and that a,(3>0. If paq@ is s*k-perfect, then a^=k, and (3 ^ k. Proof. Suppose a = k. T h e n Sk{paq13) — paq13 is equivalent to T h i s is impossible as on ly the right side of this equat ion is divis ible by q. W e get a s imilar contradic t ion if /? = k. • 7 F r o m Compute r searches, there are two numbers of the form paqP known to be s£-per fec t for some k. 48 = 2 4 • 3 is s^-perfect, and 46875 = 3 • 5 6 is Sg-perfect. Note that these are bo th of the form paq. It is this form that we w i l l specialize our next theorem to. Theorem 4 Let p and q be distinct primes. (i) Suppose that p > q. If p > k + 1, and q > (a + l)/(a — k + 1), then paq is not s*k-perfect. (ii) Suppose that p < q. If p > k + 1, then paq is not s^-perfect. Proof, (i) In the first instance, suppose that paq is s^-perfect. W e have sk(Pag) = (f)Pk + (fc a_ ^Pk~\ = Pag. T h i s implies that or a — kl \a — k + 1 ' L e t t i n g £ = a — k + 1, we have Since p > q, we have that _ 1 P + ( i 1 = PQ-a \ (a\ ( a \ Ia\ (ot + 1 If we show that the assumption i n (i) implies that a + 1 ^ (2.2) £ then we are done. B u t ' a + l \ (a + l \ ( a \ fa - £ + 3 \ (a - £ + 2 £-1 \ 2 \ 1 There are £ terms i n this product . T h e first t e rm < q by assumption. Since a a - l ^ a - £ + 2 ^ e - i - e - 2 - ~ 1 by assumption, (2.2) holds and we have proved (i). (ii) T h e proof of (ii) is s imilar . In this case sk{paq) < ( a ^ 1 ) « ' where £ is as before. Hence it suffices to prove that Since p> a — £ + 2 = k + I, this indeed holds, so (ii) is proved. • 2.2 Basic Properties of the Elementary Prime Symmet-ric Functions T h e following propos i t ion from [20] is an immediate consequence of the definit ion. P r o p o s i t i o n 5 If n = 1 • • • p^T, then ii + ••• + ir = k ii, . . . , ir > 0 P r o p o s i t i o n 6 k •'• v sk{mn) = ^sk-i{m)si{n).- ~ Proo/ . If TO = 1, or n = 1, the result is immediate , as it is i f k = 0. If k > 0, TO = p i . . . p r , and n = q\... qs, let S, = {Pi,---,Pr,<2 ,i,-..,?s}. 9 T h e n s f c (mn) = ]P n---rk. {ri,...,rk}CS W e collect the terms of this sum having k — i factors from ra, and i factors from n. T h e sum of these is equal to sk-i(m)si(n). S u m m i n g as i ranges from 0 to A: gives the desired result. • Corollary 7 Let n, k £ N, and let p and q be primes, with p < q, and suppose Q(pn) > k. If pn — sk(pn) > 0, then pn — sk(pn) < qn — sk(qn). Proof. Since fl(n) > k, we have that Sfc(n) > 0. Therefore, since pn - sk(pn) > 0, it follows that n > Sfc_i(n) + sk(n)/p > Sfc_i(n). qn - sk(qn) =qn- qsk-i(n) - sk{n) > pn-psk-i{n) - Sfe(n) = pn- sk(pn). • In searching for s^-cycles and s£-per fec t numbers, it is essential to know when sk(n) > n. W e search by f ixing fi(n), and systematical ly checking a l l products of Q(n) primes. T h e corol lary tells us that i f sk(pn) < pn, then for any q > p, qn is also Sfc-defective. Lemma 8 Let k, n e N. Then there exists anr > k such that if Q(n) > r, then n is sk-defective. Let r(k) denote the least such r. Then ^ ~r-k • Hence, r(fc) = m i n { r : ( < 2r~k } . i k 1 10 Proof. There is an r > k such that the function 't satisfies f(t) < g(t) for a l l t>r, where g(t) = since / is a po lynomia l , and g is an exponential function. N o w suppose t >r, and let pi,... ,pt be t primes. T h e n < 2* fe, wh ich implies fc) G . t \ _ 1 where the sum is taken over a l l i i , . . . , it-k such that 1 < i\ < • • • < it-k < -^ T h i s implies YlPh • • •Vik <Pi---Pt, where the s u m is taken over a l l i\,... ,ik such that 1 < i\ < • • • < ik < t. T h i s i n t u r n implies that Sfc(pi • • -Pt) < P i • • -Pi-N o w we prove the second statement. T h e inequal i ty holds for a l l k > 1, and so r(k) > 2k. T h i s i n m i n d , let r(k) be as c la imed i n the statement of the theorem. We argue inductively. L e t t > r, and suppose that T h e n 11 Since t > 2k, we have t < 2(t — k), and so Hence t\ _ t ( t - l ) - - - ( t - k + 1) 2(t-l)(t-2)---(t-k) _ 2 f t - l k) ~ k\ K k\ 1 k and the proof is complete by induct ion . • Remark 1 An instructive way of viewing Lemma 8 is the following equality of sets: <2r-k}={r(k),r(k) + l,...}. T h e first few values of r(k) are given i n the following table: k r(k) 1 3 2 6 3 10 4 14 5 19 6 23 7 27 8 31 9 36 10 40 T h e properties of s i-perfect ion etc., corresponding to the first elementary pr ime symmetr ic function s i are easily characterized. T h e si-perfect numbers are the primes and 4 is the only s|-perfect number. A l l other numbers are si-defective. C lea r ly there are no si -cycles . We now investigate these properties i n the second pr ime symmetr ic function. 12 Chapter 3 The Second Prime Symmetric Function L e t n > 1 be an integer. B y a fami ly Ek(n,r) of s^-special numbers we mean a set Ek(n, r) = {npi • • -pr\pi, • • • ,pr are primes} such that i f m £ Ek(n,r), then m is s£-spec ia l . The fami ly ^ ( 4 , 1 ) of numbers of the form 4p, where p is pr ime, 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 Sfc(n) > n, and fl(n) > k. In t roducing the definit ion Ek(n,r), is product ive for classifying a l l sjji-special numbers for a fixed k. W e w i l l see later that w i t h finitely many exceptions, a l l such numbers are i n fact s^-excessive, and that the families Ek+i{n,r + 1) can be determined completely from the s^-special numbers. A s wel l , a l l but finitely many s^-special numbers belong to such families. To f ind a l l s^-perfect numbers and a l l S2-cycles we need to f ind a l l numbers n such that 2 < f i (n) < 6, w i t h S2(n) > n, since r(2) = 6. To do this we use the a lgor i thm mentioned after corol lary 7, the approach taken i n [20]. 13 3.1 fi(n)=3 s 2 ( 2 - 2 - p ) = 4p + 4 > 4 p , s 2 (2 • 3 • p) = 5p + 6 < 6p, when p > 6. T h i s shows that there are no other infinite families of sij-special numbers satisfying fi(n) = 3. Be low we find a l l s^-special numbers not belonging to this family. 5 2 ( 2 3 3) = 21 > 18, s 2 (2 3 5) = 31 > 30, s 2 (2 3 7) = 41 < 42, S2 (3 3 3) = 27, s 2 (3 3 5) = 39 < 45. T h u s 27 is the only s^i-perfect number satisfying fi(n) = 3. I terat ing on the above s 2 -excessive numbers shows none belong to s 2 -cycles . For example 3.2 fi(n) = 4 s 2 ( 2 • 2 • 2 • p) = 6p + 12 < 8p, when p > 6. T h u s there are no infinite families of Srj-special numbers w i t h Q(n) = 4. I terating on 8p for p = 2, 3, 5, shows that none belong to an s 2 -cyc le . Check ing other cases: s 2 ( 2 2 3 3) = 37 > 36, s 2 (2 2 3 5) = 5 1 < 60, s 2 ( 2 3 3 3) = 45 < 54. 14 Hence there are no sj-perfect numbers satisfying il(n) — 4. I terat ing on the above S2-excessive numbers shows that none belong to an S2-cycle. 3.3 Q(n) = 5 s 2 ( 2 • 2 • 2 • 2 • p) = 8p + 24 < 16p, when p > 3. T h u s there are no infinite families of s^-special numbers w i t h J7(n) = 5. I tera t ing on 16p for p = 2, 3, shows that 48 is i n fact s^-perfecti and 32, wh ich is S2-excessive, does not belong to an S2-cycle. Check ing other cases: s 2 (2 • 2 • 2 • 3 • 3) = 57 < 72, Hence 48 is the on ly s^-perfect number satisfying fi(n) = 5. We have proved the fol lowing theorem. T h e o r e m 9 27 and 48 are the only s^-perfect numbers. T h e o r e m 10 There are no si-cycles. Proof. A n S2-cycle must have a least element that is S2-excessive. It is easily verified (as it was above i n the case n = 18), that a l l of the finitely many s 2 -excessive numbers not of the form 4p do not belong to S2-cycles. Thus any such element must belong to the fami ly of numbers of the form 4p. We w i l l show that i n a l l but a few t r i v i a l cases S2(s 2(4p)) < 4p, g iv ing a contradict ion. N o w , s 2 (4p) = 8 ( ( p + l ) / 2 ) . We may assume that p is odd, and set m = ( p + 1 ) / 2 . T h u s we w i l l have a cont radic t ion if the fol lowing holds: s 2 (8ra) < 8 m - 4. T h i s is equivalent to 12 + 6 s i ( m ) + s2{m) < 8 m - 4 , (3.1) 15 which is equivalent to 16 A 1 V - 1 + 6 > : + > < Pl---Ps ^Pl---Pi---Ps l<£Ji<sVl---Pi---Pj---Ps where m = p\ • • • ps. Here p\ • • • pi • • • ps is defined to be p i • • • ps/pi, and p\ • • • p% • • • pj is defined to be p\ • • -ps/piPj. Since pi > 2, this expression is impl ied by: 16 _6s_ s(s-l) 1 wh ich holds for a l l s > 4. If s = 1, then m = p is pr ime, and so condi t ion (3.1) becomes: . " , 12 + 6p < 8p - 4 , . wh ich holds for a l l p > 8. It is easily verified for p = 2, 3, 5 and 7, that 8p does not belong to an S2-cycle. , For s = 2, we can wri te m = pg. T h e only values of m for wh ich (3.1) fails are determined by the pr ime pairs (p,q) = (2,2) , (2,3) . In bo th cases, 8 m does not belong to an S2-cycle. F i n a l l y for s = 3, i f in = pqr, only for the t r iple (p, q, r) = (2, 2,2) does m fai l to satisfy (3.1). A g a i n , i n this case, 8 m does not belong to an S2-cycle. • R e m a r k 2 The longest increasing si-sequence is 8 Jl> 12 J i » 16 J** 24 ^ 30 31. 3.4 A n Inverse Problem Definit ion 5 Lei fe e No- We define : N —> No 6t/ ^(n) = IK 1 [{n}] | 16 E x a m p l e 3 r i ( l ) = 0, but for all n > 2, r\(n) > 1. In fact, lim^oo r\(n) = oo. To see this, simply set n = si{2aib) = 2a + 36, and observe that the number of pairs (a, b) satisfying this equation can be made arbitrarily large for all n sufficiently large. W e now prove a weaker result for ri, as found i n [20]. T h e o r e m 11 There exists an N e N such that for all m> N, r2(m) > 1. Proof. It suffices to show that for m sufficiently large, m = S 2 ( 2 a 3 b 5 c 7 d ) , for some a, b, c, and d > 0. In general, S 2 ( 2 « 3 W , = 4 ( « ) + 9 Q ) + 2 5 ( « ) + 4 9 g ) - O ( 0 - G ) ( ? + - ( 9 ( f = i [(2a + 36 + 5c + 7d)2 - (4a + 96 + 25c + 49d)] So, given m, we need only find solutions to the equations: 2a + 36 + 5c + 7d = R, 4a + 96 + 25c + 49d = R2 -2m, w i t h nonnegative integers a, b, c, d, and R EN. These equations are equivalent to: 2a 10c - 28d = 3R - R2 + 2m,. (3.2) 36 + 15c + 35d = R2 - 2R - 2 m , (3.3) Since a and 6 must be nonnegative integers, we have the following necessary and sufficient condit ions for a solut ion to (3.2) and (3.3): 1. 2 m = R2 + R + d (mod 3), 17 2. R2 - 3 R - 10c - 28d < 2m, 3. 2m < R2 - 2R - 15c - 35d. No te that equat ion (3.2) is always satisfied modulo 2. C o n d i t i o n 1 results from t ak ing equat ion (3.3) modulo 3, and condit ions 2 and 3 are derived from the fact that a, b > 0. Consider the interval IR(c, d) = [R2 - 3 R - 10c - 28d, R2 - 2R - 15c - 35d]. For fixed d, let cR(d) be the least c such that £(IR(c,d)) < 15, where £ ( / ) denotes the length of an interval / . We use the nota t ion L(I) and R(I) to denote the left and right endpoints of an interval I, respectively. Since R(IR(C, d)) = i ? ( / # ( c + l , <i)) + 15, when they exist, we have that cR(d) [j IR(c, d) = [R2 - 3 R - 10cR(d) - 28d, R 2 - 2 R - 35d]. c = 0 Denote the above interval by Z]i(d). B y definit ion of ca{d), £(IR{cR(d), d))=R- 5cR(d) - Id < 15, so - 1 0 c f i ( d ) < -2R + 30 + 14d, and cR(d) is the least such c. Consider the interval Hd=o ^ R ( ^ ) - C lea r ly R(f]^-Q 1R{d)) R2 — 2R — 70. W e now wish to find an upper bound for L(Cfd=r)lR{d)). F r o m the above inequality, we have that L(IR(d)) = R 2 - 3 R - 10cfl(d) - 28d < R2 - 5 R - 14d + 30. 18 T h u s 2 L( p) lR(d)) = m a x { i ? 2 -3R- 10cR(d) - 28d\d = 0 ,1 ,2} < max{R2 - 5 R - Ud + 30|d = 0 ,1 ,2} = R2 - 5R + 30. Le t JR = [R2 -5R + 30, R 2 - 2 R - 70]. T h e n JR c f|S=o JR(D)- N O W L(JR+I) < R(JR), i f and only i f R2 - 3R + 26 < R2 - 2R - 70, wh ich holds for a l l R > 96. So i f 2 m > L(Jg^) = 8766, then there is an R > 96 such that 2 m € JR C fld=o-^ R(^)- Choose d G {0 ,1 ,2} such that condi t ion 1 is satisfied. Since 2 m s IR(d), there is a c > 0 such that 2 m € IR(C, d). For these values of R, c, and d, condit ions 2 and 3 are satisfied. In other words, there exists an n such that m = S2(n). T h i s completes the proof. • L e t us t r y and improve on this result. T h e o r e m 12 l i m m _ ( 0 0 r2(m) = oo Proof. Le t C O i=l where pi denotes the i th pr ime, Xi > 0, and xi = 0 for a l l but finitely many values of i. If O O 1=1 then s 2 ( n ) - i [ A 2 - ^ ] . Set S2(n) = m and then set = R, as before. T h i s gives two equations i n the unknowns x\,X2, - • • , and R, namely: 19 2 x i + 3a; 2 + • • • = R (3.4) 2 2 x i + 3 2 x 2 + ••• = R2 -2m. (3.5) E l i m i n a t i n g from the first and x\ from the second gives 2 x i - 1 0 x 3 {p2r- 3pr)xR = -R2 + 3R + 2m 3 x 2 + 1 5 x 3 + \-{p2r- 2pr)xR + • • • = R2 - 2R - 2m. If ( x 3 , X 4 , . . . , R), satisfy the conditions (1) 2m > R2 - 3R - 1 0 x 3 - 2 8 x 4 - •. • • - {pi - 3pr)xr , (2) 2m < R2 - 2R - 1 5 x 3 - 3 5 x 4 {pi - 2pr)xr , (3) 1 5 x 3 + 3 5 x 4 H + {pl~ 2pr)xr + --- = R2+R + m (mod 3), then they uniquely determine a solut ion ( x i , x 2 , . . . ,R) to the equations (3.4) and (3.5). Observe that given R and m , for any choice of X 3 , X 5 , x$,..., we can choose x 4 uniquely from the set {0 ,1 ,2} so that the congruence (3) holds. We w i l l do this i n the following way. L e t qi, ( j 2 , . . . be the odd primes congruent to 2 modulo 3, l is ted i n increasing order. T h e n for yi > 0, and r > 0, we have that 15^ /1 + 99y2 + • • • + (g? - 21r)yr = 0 (mod 3). Denote this sum as D = D{y\,..., yr), and let r C = ^ ( l i ~ 3 9i)2 / i i=0 20 L e t q be any o d d prime congruent to 2 modulo 3, k = q2 — 2>q, £ = q2 — 2q, and suppose a > 0. Consider intervals of the form IR(a) = [R2 -3R-28d-C- ak,R2 -2R- 35d — D — a£}. W e w i l l handle the case when R, m = 0 (mod 3). T h e other cases are v i r t ua l l y ident ical . In this case, choosing d = 0, we have that i f 2 m lies i n an interval IR{Q) = [R2 -3R-C - ak, R2 - 2R- D - a£], then m satisfies condit ions (1), (2), and (3), w i t h the primes qi, q. Note that d is p laying the role of X4 above. W e w i l l show that the number of such intervals containing 2 m tends to inf ini ty as m does. T h i s implies the theorem. If ml = 0 (mod 3) and i f 2 m ' lies i n the interval / f l - i ( 0 ) = [R2 - 5R + 4 - C, R2 - AR + 3 - D], then since R = 0 (mod 3), condi t ion (3) is satisfied w i t h respect to the primes occur r ing i n the terms of C and D, R — 1 instead of R, and m! instead of m. G i v e n R >> 0, C, D, k, £ and q, let aR > 0 be the largest number such that (using nota t ion as i n the previous theorem): (i) L(IR(aR)) < R(IR(aR)), and (ii) R(IR(aR + l))>L(IR(aR)). These condit ions ensure that U w A=0 is an interval , and of longest possible length. Since we always have R(IR(a + 1)) < R(IR(a)), then condi t ion (ii) implies condi t ion (i). C o n d i t i o n (ii) holds i f R2-2R-D-{aR + l)£> R2 -3R-C - aRk, which i n t u r n holds i f and only i f R > (D - C) + aR{£ -k) + e. 21 T h u s we have R (D-C) e-k Define JR=\J W. We wish to show that JRC] IR-I(0) is nonempty. T h a t is that L(JR) < R(IR-I(0)). T h i s is true i f and only i f L(IR(CIR)) < R(IR-I(Q)), i.e. i f and only i f R2 - 3R - C - aRk < R2 - 4R + 3 - D. Subs t i tu t ing i n the value for otR into the above gives Rz - m - C - R-i-(D-C) e-k k<R2-4R + 3-D. T h i s inequal i ty is impl i ed by the inequal i ty R 2 _ 3 R _ c + k-[R \ ( f C))k<R2-4R + 3-D, £ — k which is i n t u r n equivalent to the inequali ty R+(D-C)-3 + k< R-e-(D-C) e-k k. T h e coefficient of R on the left hand side of this inequal i ty is 1. O n the right hand side it is k/(e — k) — q — 3 > 1, and so for R large enough, this inequal i ty holds. Since q, and each qi could be taken to be arb i t ra ry o d d primes congruent to 2 (mod 3), we can vary the primes i n the terms of C and D. For each such choice, and each choice of q say w i t h q > qr, we obta in dist inct solutions for every rn such that 2 m lies i n JR, i n this case where R, m = 0 (mod 3). T h e remaining cases, i n which R and m need not be congruent to 0 (mod 3) are handled similar ly, by first selecting a different value of d G { 0 , 1 , 2 } , and showing that the corresponding interval JR reaches low enough to intersect the interval 7R_I(0). ' • W e end this section w i t h a conjecture. Conjecture 1 For every k G N, limn-^ oo r^(n) — oo. 22 Chapter 4 Higher Elementary Prime Symmetric Functions T h e o r e m 13 (1) Let n G N . If n is s*k-special then pn is Sk+\-excessive for every prime p. (2) Ifpn is sk+1-special for every prime p, then n is s\-special, and hence by (1) , pn is Sh+i-excessive for every prime p. Proof. (1) Suppose n is s^-special. T h e n since J7(n) > k, we have sk+i(n) > 0. So Sfc+i (pn) = psk (n) + s f c + i (n) >pn + sk+i(n) > pn. (2) If sk+i(pn) = psk(n) + sk+i(n) > pn, for every pr ime p, then sk(n) > n — sk+\(n)/p. L e t t i n g p —> oo, we have sk(n) >n. • C o r o l l a r y 14 For k € N , there are only finitely many s*k-perfect numbers. Proof. B y the previous theorem, any infinite family Ek(n, r ) , r > 0 contains only sk-excessive numbers. W e c l a i m that there are only finitely many s£-spec ia l numbers not belonging to any such family. Indeed if there were inf ini tely many, then by 23 L e m m a 8, there would be an r > k such that there are infini tely many such s£-special numbers n satisfying Q(n) = r. Wr i t e them as follows: s = {py--.p?\p?.-.p?\pw.--P(v,...} and assume that p\^ < Pi+V C lea r ly we must have that l i r n 3 _ 0 0 p ^ = oo, otherwise, we must have the same number occurr ing twice i n the sequence. If p^\ contains a bounded subsequence, then there must be an ident ical product p^p • • • p^_\\ occur r ing for infini tely many values of I. T h i s gives a contradict ion, since it implies that Ekipf0^ • • -Pr- i> 1) intersects S, where £n is one such value oil. T h u s l i r n 3 _ + 0 O p ^ 2 1 = oo. Inductively, by s imilar arguments, we conclude that l i m ^ o o P m ^ = oo, for m = 1,2,... ,r. B u t then J -oo pU) . . . pU) T h i s implies that the set S contains Sfc-defective elements, a contradic t ion. • T h e preceding results of this section were first proved i n [20], by the author. C o r o l l a r y 15 Let k e N . There are only finitely many d < 0 such that the equation n — Sfc(n) = ti has infinitely many solutions. Proof. T h e only such d are those for which — d is s£_ ] -pe r f ec t , of which there are only f ini tely many. • T h u s the infinite families of S3-excessive numbers are: £ 3 ( 4 , 2 ) , £ 3 ( 1 6 , 1 ) , £ 3 ( 1 8 , 1 ) , £ 3 ( 2 4 , 1 ) , £ 3 ( 2 7 , 1 ) , £3 (30 ,1 ) , £3 (32 ,1 ) , £ 3 ( 3 6 , 1 ) , £ 3 ( 4 0 , 1 ) , £ 3 ( 4 8 , 1 ) . T h a t is, those corresponding to the s^-special numbers £ 2 ( 4 , 1 ) U { 1 6 , 1 8 , 2 4 , 2 7 , 3 0 , 3 2 , 36 ,40 ,48} . B y exhaustive search (as was done w i t h k = 2), a l l other s^-special num-bers can be found. T h e y constitute the following set: {42p|p = 7 , 1 1 , . . . , 41} U {.56p|p = 7 ,11, . . . , 43} U {64p|p = 2 , 3 , . . . , 37}U {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} . 24 S3 197660 = 4 5- 9883 S3 248636 = 4 61 • 1019 S3 315452 = 4 17 •4639 S3 352508 = 4 13 • 6779 S3 428636 = 4 13 • 8243 None of the elements i n the above sets are Scj-perfect, hence there are no s^-perfect numbers. T h e diversi ty of possible increasing S3-sequences makes it difficult to rule out the existence of S3-cycles as we d i d S2-cycles. T h i s is i l lus t ra ted i n the following example. E x a m p l e 4 If pi, q\ are odd primes, then s^(Apxq-\) = 4 ( p i g i + pi + qi). It is possible that p\q\ + pi+ q\ = P2Q2, where P2, 92 are again odd primes, and so on. Several such sequences exist the longest one with piq± < 50000, andpi,qi > 3 is: 184892 = 4 • 17 • 2719 195836= 4 • 173 • 283 237212 = 4 • 31 • 1913 244988 = 4 - 7 3 - 8 3 9 252956 = 4 • 11 • 5749 275996 = 4 • 7 • 9857 334076 = 4 • 47 • 1777 341372= 4 • 31 • 2753 379676 = 4 • 11 • 8629 414236= 4 • 29 • 3571 461660 = 4 • 5 • 41 • 563. It seems h igh ly unl ikely however that an increasing S3-sequence be infinite. T h i s is part of the following conjecture: Conjecture 2 Any increasing Sk-sequence is finite. A related conjecture is given by: Conjecture 3 For any n S N o , the Sk-sequence of n is ultimately periodic. T h e evidence for these conjectures lies p r inc ipa l ly i n the fact that for a fixed k, w i t h finitely many exceptions, a l l s£-excess ive numbers belong to one of the families Ek(n,r). T h e union of a l l such families has asymptot ic density 0 i n the integers. Be low is a complete list of a l l s^-perfect numbers for k = 1,2,3, and 4, found by exhaustive search. 25 k sjl-perfect numbers 1 4 2 27, 48 3 none 4 3125, 9315, 31280 4.1 The Hunt for S3-cycles A s just noted, ru l ing out the existence of s 3 -cycles is not a t r i v i a l matter , since there seems no apparent m a x i m u m 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. U s i n g maple, computer searches were done to verify that many numbers do not belong to an s 3 -cyc le . These include: {42p\p = 7 , 1 1 , . . . , 41} U {56p|p = 7,11, . . . , 43} U {64p\p = 2 , 3 , . . . , 37}U {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, a l l those Sg-special numbers not belonging to any of the infinite families. It was also shown for each of the following sets: #3(16,1), #3(18,1), #3(24,1), #3(27,1), #3(30,1), #3(32,1), # 3 (36 ,1 ) , # 3 (40 ,1 ) , #3(48,1), wh ich are a l l o f t h e form {np\p is pr ime}, for a l l p < 1000, that none of the numbers belong to an S3-cycle. F ina l l y , the same was shown for the set # 3 (4 ,2 ) = {4pq\p, q are prime} i n the fol lowing ranges: 2<p< 30,2 < q < 1000, and 2 < p < 100,2 < q < 100. T h u s an s 3 - cyc le must have a least element belonging to one of the 10 infinite sets E%(n,k). W e label these sets i n the following way: we say m is type 1 i f m e £3(4,2). S i m i l a r l y we identify elements i n the following sets: . • £ 7 3 ( 1 6 , l ) - t y p e 2 , ' • # 3 (18 ,1 ) - type 3, 26 •£3(24,1) - type 4, •# 3 (27 ,1 ) - type 5, •#3(30,1) - type 6, •# 3 (32 ,1 ) - type 7, • # 3 ( 3 6 , 1 ) - type 8, •#3(40 ,1) - type 9, • # s ( 4 8 , l ) - type 10. T o analyze what increasing sequences begin w i t h elements of types 1 to 10, we w i l l consider the effect of apply ing S3 to such a number, and consider what type the result ing number may be, i f any type. We w i l l use the nota t ion type a —> type b to indicate the following: it is not impossible for d iv i s ib i l i t y 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. Be low is a complete list of a l l the possibil i t ies. Note that we are assuming that the numbers do not lie i n 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. T h i s list was arr ived at by s imply ru l ing out possibili t ies. For example, i f rn = 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). T h u s it is impossible for s$(l%p) to be of any of types 1 through 10. T h e list arr ived at above includes a l l those cases that could not be ruled out i n like manner. N e x t we w i l l rule out the possibi l i ty that numbers of the types that can not be of another type upon appl icat ion of S3, are not least elements of any S3-cycles. T h e o r e m 16 / / n is type 3, 4, 5, 6, 8, or 9, then n is not the least element of an ss-cycle. 27 Proof. F i r s t suppose n = 18p is type 3. We may assume that p > 1000. A p p l y i n g S3 we get S3(18p) = 21p + 18 = 3(7p + 6). L e t m = 7p + 6. If m is pr ime, then the s 3-sequence terminates, as it does if m is the product of 2 primes. If m = 919293 is the product of 3 primes, then we have s3 (n) < n if and only i f 3(<7i<?2 + 9193 + 9293) + 919293 < 18 ^ 9 l 9 2 ^ 3 — i f and on ly i f 108 + 21(9192 + 9^3 + 9293) < I l 9 i 9 2 9 3 - (4.1) Since p > 1000, we have that 919293 > 7006. A l s o , clearly q^ ^ 2 ,3 , or 7. Unde r these constraints, the inequali ty (4.1) holds, and so n cannot be the least element of an S3-cycle. Hence we may assume m = 91 • • -qr, where r > 4. T h e same holds for m > 7006, and qi ^ 2 ,3 , or 7. In this case, s 3 (n) < n i f and only i f 108 + 21 (9 i92 + h qr-iqr) + 7(9l9293 + r- 9 r _ 2 9 r - l 9 r ) < 1891 • • ' 9r-U p o n d i v i d i n g each side by m, and using the facts that m > 7006, and 9, > 5, we have that the latter inequal i ty is impl ied by the inequal i ty 108 21 fr\ 7 fr\ + r - ^ L + - T L < 1 8 . 7006 5 r - 2 V 2 / 5 r - 3 V 3 , T h i s indeed holds for r > 4. T h u s numbers of type 3 cannot be least elements of S3-cycles. T h e remain ing cases, types 4, 5, 6, 8, and 9 are handled i n v i r tua l ly ident ical fashion. • Remark 3 A consequence of the above proof, is that all but finitely many maximal increasing S3-sequences of length greater than 2 have as least element a type 1 num-ber, and have as second last element either a type 1 or a type 8 number, with all 28 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 —> fr/pe i —> • • • —• fj/pe. i —> type <? —> ro, where m satisfies S3(m) < rn. W e have accumulated enough informat ion to prove the non-existence of the simplest case of s 3 -cycles . T h e o r e m 17 There are no s^-cycles of length 2. That is, if sf\n) = n, then s 3 (n ) = n. Proof. A n y such s 3 -cyc le must have a least element n of type 1, 2, 7, or 10. F i r s t assume that n = Apq is type 1. Because of the computer searches, we may assume that the pair (p, q) lies outside of the ranges 2 < p < 3 0 , 2 < q < 1008, and 2 < p < 100, 2 < q < 100, and that p < q. L e t ro = pq+p + q. In the allowable range, the m i n i m u m value for m occurs when p = 2, and q = 1009, which gives m = 3029. No te that 2 \ m. W e have 4 2 ) (4p9) = s 3 (4ro) = 4s i ( ro) + 4s 2 ( ro) + s 3 (ro) . If s 3 2 ) ( n ) = t n e n 4si ( ro) + 4s 2 ( ro) + s 3 ( m ) = 4pg. (4.2) We w i l l take cases depending on i1{m). In the following, qi always indicates a pr ime d i v i d i n g m . If m = q\ is pr ime, then we are done since then s 2 (4ro) = 4 m . If ro — q\q%, then (4.2) implies qi + 92 + 9 i 9 2 = pq. Subs t i tu t ing qio2 = p o + p + o , and canceling gives qi+q2+P+q = 0, an impossibi l i ty . 29 If m = gig2<?3; then (4.2) implies that 4 s i ( m ) + 4s2(m) + m = 4pq. T h i s is impossible, since 2 { ra. In case m = q\ • • -04, we w i l l show that (4.2) is i n fact a str ict inequality. D i v i d i n g (4.2) through by m gives 4 ( _ L . + ... + - ! _ ) + 4 ( - L + ... + - L W I + ... + I ) . ^ a _ . V919293 929394/ \q\qi qsq^J \ 9 i q±) pq + p + q W e can min imize the right hand side of this equation. In the range i n question, 4pq/'(pq+p+q) is min imized w h e n p = 2,q = 1009, and this gives us that 4pq/(pq + p + q) > 2.6649. It is an easy check that if > 3, and m = g i • • -94 > 3029, then we always have 1 1 \ . / 1 1 \ / 1 1 + ••• + + — + ••• + — + ••• + - + 4 + • 910293 025304/ \q1q2 9394/ \ 9 l < 2.6649 < — . pq + p + q A s imilar approach can be used when il(m) = 5 . If r > 6, then 1 1 \ , ( 1 1 \ / 1 1 1 1 4 - 4 1 1 + -+ ••• + + 4 + ••• + + — + ••• + — 919293 qr-2qr-iqrJ \q1q2 qr-iqrJ \qi 9r / r \ 4 / r \ 4 fr\ 1 1 y 3 r - ! V2 /3 r - 2 V 3/ 3''" 3 < 2.6649 < — — , pq + p + q and we are done the type 1 case. N e x t suppose that the least element n = 16p is type 2. We may assume that p > 1009. N o w 4 2 ) ( 1 6 P ) = S3(8(3p + 4)). L e t m = 3p + 4, so 16p = 16(m - 4 ) / 3 . T h e n 2 ,3 \ m, and m > 3031, So s 3 2 ) ( 1 6 P ) = 8 + 12s i (m) + 6s2(m) + s3(m).~ T h e supposi t ion that s 3 '(n) = n is equivalent to (m — 4 N 8 + 12s i (m) + 6 s 2 ( m ) + s 3 ( m ) = 16 30 which is equivalent to 88 + 36si(m) + 18s2(m) + 3s3(m) = 16m, (4.3) We will do cases depending on the value of il(m). In the following, each g, is assumed to be prime. If m = gi is prime, then (4.3) becomes 88 + 36gi = 16gi, which is impossible. If m = g i g 2 , then (4.3) is also impossible for m in the allowable range. If m — 919293; then (4.3) is equivalent to 88 + 36(gi + q2 + g3) + 18(gig2 + 9i93 + 0293) = 13gig293-Dividing through by m, and using the facts that m > 3031, and qi > 5, we have the inequality 8 R + 3 6 r - i - + J _ + J L > ) + 1 8 f I + I + I , < 1 3 3031 V°i°2 9i93 9293/ \ 9 i 92 93, This contradicts (4.3). A similar contradiction occurs when fl(m) > 3. The proofs of the cases when n is type 7 'or 10 follow the same lines as the proof for case 2. • 31 Chapter 5 The Exponent Prime Symmetric Divisor Functions Anothe r na tura l class of pr ime symmetr ic divisor functions are the functions whose values on n G N are the sum of the kth powers of the primes d i v i d i n g n, w i t h repet i t ion. D e f i n i t i o n 6 Let k G No- Define the function : No —> No by e/c(0) = 0. For n = pi • • -pr G N , where the pi are the primes dividing n, with repetition, set r efc(n) = ]TP*-i=l We call the function the kth exponent prime symmetric divisor function. R e c a l l we were able to classify when a pr ime power pa was s^-perfect for some k. W e now present an analogous result per ta in ing to e/c-perfection. T h e o r e m 18 Let n=pa be a prime power. Then there exists a k G N such that n is ek-perfect if and only if k = p® — and a = p® for some j3 > 0. Proof. ek{pa) = pa i f and only i f apk = pa. Hence we may wri te a = pP for some (5 > 0. T h i s implies that p8^ = p^, and so k = p3 - /?. Conversely, it is t r i v i a l to see that pf^ is always e p^_^-perfect. • 32 R e m a r k 4 The set {pi3 - (3\p is prime and ft > 0} has density 0 in the integers. So, for "most" values of k, there is no prime power pa that is ek-perfect. W i t h the functions ek, we can also characterize which numbers are e^-perfect for some k for products of two pr ime powers. ' . T h e o r e m 19 Let n = paqP', where p and q are primes, and a, (5 > 0. Then n is not ek-perfect for any k. Proof. W i t h o u t loss of generality, p < q. Furthermore, since e i = s i , and the statement has been proved for s\, we may assume that k > 2. If ek(paq^) = Paq^, then apk + (3qk=paq0. (5.1) F i r s t assume that a,j3 > k. T h e n since Pqk=pk(pa-Y-a), we have that pk divides (3. S imi l a r ly qk divides a. Wr i t e (3 = bpk, and a = aqk. Clea r ly a, b > 0, and equat ion (5.1) becomes (a + b)pkqk =paikq bP". W e w i l l show that we instead have a strict inequali ty {a + b)pkqk < p a q q b p k . (5.2) Since a,b > 0, p > 2, and q > 3, it is easily seen that bp^1 < bpk — k, and aqk-i < agk _ ^ a n c i n e n c e t n e inequali ty (5.2) is impl i ed by o + 6 < p a « * " l 9 ' * * ~ 1 . T h i s is i n t u r n impl i ed by a + b < ab(pq)k~l 33 N o w pq > 6, and k > 2, so the latter inequali ty holds i f a + b < 6ab. T h i s is indeed true for a, b > 0. T h e second case we consider is when a, (3 < k. T h e n i n s imilar fashion to the previous case, we can wri te (3 = bpa, and a = aq@, where a, b > 0. T h i s however gives an immediate contradict ion, since then a = aqP = aqbp" > a. N e x t suppose that a < k, and (3 > k. T h e n for some a > 0, we have that T h i s is a contradic t ion. A similar contradic t ion results i n the remaining case, thus, R e c a l l that we considered the functions r^, wh ich counted the number of representations of n as Sfc(m) for some m. We now define their analogue for the exponent pr ime symmetr ic functions. Definit ion 7 Let : N —> N Q be defined by It is much easier to work w i t h the functions than w i t h their analogues rfe to the elementary pr ime symmetr ic functions: Theorem 20 For k £ N , we have that limn-^ oo £fc(n) = oo. Proof. Le t t £ {0, l , . . . , 2 f c - 1}, and consider the sequence {n2k + £}^=1. L e t q be any pr ime congruent to 1 modulo 2 f c . Numbers of the form 2nq(, satisfy ek{2nql) = n2k + £qk, and £qk = £ (mod 2k). Since there are infini tely many such o, we have that lim^oo ek{n2k + £) = oo. Since this holds for any £ e { 0 , 1 , . . . , 2k — 1}, we have the stated result. • F r o m the theory of part i t ions (see for instance [1]), we can construct gener-a t ing functions useful i n calculat ing £fc(n). Indeed, we have a = aqk > aqa > a. the theorem is proved. • £k(n) = \ek (n)|. 34 T h e proof is by analogy w i t h [1] pp.308-310. W e can relate the functions sk and using the N e w t o n - G i r a r d formulas (see [18]). These formulas i m p l y that k (-l)kksk + Yl(-l)i+keiSk-i = 0. i=l T h e function ek can be expressed s t r ic t ly i n terms of the elementary pr ime symmetr ic functions s\, . . . , Sfc as a determinant (see also [19]): 1 0 0 . . . o 2 s 2 Sl 1 0 . . . o 3 s 3 S2 Sl 1 . . . o efc = ( - l ) f c 4 s 4 S3 S2 S l . . . o ksk Sfc-l Sfc-2 Sfe- 3 • • • S i Simi lar ly , we can express sk i n terms of efc as follows: Sfc e i §2. 2 3 4 2 §2. 3 £2 4 £1 3 £2 4 4 e^-i e*'.-2 efc-3 efc-4 fe-1 fc-1 efc_i e f c_2 e f c_3 A- /c /c 5.1 The Average Order of G i v e n an ar i thmet ic function / , we denote by / the function defined by / » = / ( l ) + / ( 2 ) + . . . + / ( n ) . In this section we w i l l come up w i t h upper and lower bounds for the functions ek. D o i n g so is more straightforward than for the functions sk for the simple reason that 35 the functions ek satisfy ek(ab) = ek(a) + ek(b). In the following analysis, p always denotes a pr ime, so for instance indexing p < n means over a l l primes less t han or equal to n. Theorem 21 The function ek satisfies the following inequalities: ( - - l ) E ^ - M n ) E I 4 ) < 5 f c ( n ) < ^ - 1 ^ ^ T -p<n p<n p<n Proof. Le t n G N . W e recall de Pol ignac 's formula (see [13]): i f p is pr ime then the largest number a such that pa\n\ is W e have N o w , ejfe(n) = efc(l) + h ek(n) = ek(n\) / OO = E K E n j=i ^ • Llogp(n)J = E[pk E p<n \ i=l Llog p(n)j E z=i [log (n)J < V ^ - A^l pt 1=1 1 _ ^ 1 j L l o g " ( n ) J \ < n P- 1 n P- 1 n P- 1 n — 1 ' i \ Llog p (n)J > l - ( - ) p - 1 36 T h i s establishes the second inequality. To establish the first, observe that Llogp(n)J E n L i o g , » J , We c l a i m that T h i s is equivalent to „ / /l\Llogp(n)J\ — x l - ( - ) - L l o g P ( n ) J . l o g » - Llog p (n)J > U i ) j \ ( l°6p («)J l L e t a; = l o g p ( n ) , and XQ = x — |_x_|. T h e n the above inequal i ty becomes x - I x l > [ - 4 T - — ) , L J _ p - 1 V P W Px J which is equivalent to ( p - l ) x 0 + l >pxo. T h e curve y = p ' , 0 < £ < l lies below the secant line y = (p — l)t + 1 through the points (0 ,1) , and ( l , p ) . T h u s this last inequal i ty holds, by t ak ing t = XQ. Consequent ly Li°gP(«)J E i=i n — 1 log(n) ~ p - 1 log (p ) ' wh ich implies the first inequality. W e w i l l now give more explici t asymptot ic bounds for e~k(n)-• Lemma 22 LetkeN. Then p<n fe+1 (fc + l ) l o g ( n ) ' 37 where the sum is taken over all primes p < n. That is l i m n—>oo (fc + l ) l o g ( n ) E p < n P f c ^ 1 Proof. T h e sum can be expressed as a Riemann-Stiel t jes integral: rn /~^pk = / xkdir(x). Integrat ing by parts, we have that rn rn i xk dir(x) = nkir(n) - k / xk~1ix(x) dx. J3/2 JZ/2 Since log(x) by the pr ime number theorem, we have that nk+l /•« „k rn Jz/2 X dw(x) -kT — log(n) 73/2 log(x) dx. ,k+l log(n) k ^k+l (fc + l)log(n) _ i r x k + 1 J3/2 ( log(x)) ; dx ,fc+i (fc + l ) l o g ( n ) ' T h i s completes the proof. L e m m a 23 Let k € N. Then p<n log(p) (fc + l)(log(n))2-• Proof. A s before, we begin by expressing the sum as a Riemann-Stiel t jes integral: Y — p<n ft log(p) - f J3/2 log(x) dir(x). Integrating by parts we have: f A r t e ) = ^ - f f — - ^ ) n(x) dx k,2 l og (» ) ( j log(n) 73/2 l l o g ( x ) ( l og (x ) )2 j ffW 3/2 38 A p p e a l i n g to the pr ime number theorem as i n L e m m a 22, we have that r *k d7r{x)-nk*w !: r xk~^dx i r^iMdx 73/2 log(a;) log(n) J3/2 log(x) J3/2 ( l og (z ) ) 2 f^c+l rn xk rn xk ~ ( i o i ( n T p ~ f c y3/2 w d x + Uo^Wdx nk+i .. (log(n))2 k nk+l 2 rn xk (fc + l)(log(n))2 + fc+T i 3 / 2 ( b g M (fc + l)(log(n))2' comple t ing the proof. • C o m b i n i n g the results from the previous two lemmas and the theorem, we have the following: T h e o r e m 24 Let keN. Then 1 ^ • ,. M n ) l o g ( n ) Sfc(n) l o g ( n ) l — r < h m i n f i—r-1— < l i m s u p — , , , < —. k(k +1) ~ nfc+! _ F nk+l ~ k Proof. Since and we have that Pk fc-l fe-2 . 1 P — 1 P — 1 E ^ ' n ^1 ( n - l ) V - ^ ^ fclog(n) P<71 Simi lar ly , l 0 ^ ) E d ? ,fe n f e + 1 p < n l o g ( p ) (fc + l ) l o g ( n ) 39 by the previous l emma. T h u s by the inequalities i n theorem 21, we have that < ek(n) nfc+i fc l og (n ) ' T h i s implies the theorem. • 40 Chapter 6 Further Prime Symmetric Functions In this section we w i l l s tudy the properties of some more compl ica ted pr ime sym-metr ic functions. W e begin w i t h a definit ion, and some pre l iminary results. Definit ion 8 Letpi,... ,pr be primes such thatpi < ... < pr, and letn — p\- • -pr. We say that n is first Sk-defective of order r if n is Sk-defective and if whenever primes q\,..., qr satisfying q\ < ... < qr, are such that q\ • • • qr is Sk-defective and Qi < Pi for each i, then qi = Pi for each i. E x a m p l e 5 42 = 2 • 3 • 7 is first s^-defective of order 3. For a given k, and fixed r , there are only finitely many first s^-defective numbers of order r . L e t r(k) be defined as i n L e m m a 8. If r < k, or if r > r(k) then 2 r is the only first s^-defective number of order r . If r — k, there are no such numbers, since no such number is s^-defective. If n = pi • • • pr is Sfc-defective, then there exists an n ' = p[ • • • p'r wh ich is first Sfc-defective of order r , and such that p\ < pi for each i. We make use of the fact that there are only f ini tely many such numbers for each r i n the following lemma. 41 L e m m a 25 Let k G N , and let M > 0. Then there exists an N e N swc/i £fta£ i / n> N and n is sk-defective, then n — Sfc(n) > M. Proof. Le t n = p\ • • • pr. T h e inequal i ty n > Sfe(n) + M holds i f and only if T h i s is imp l i ed by V - 1 M 1 > 2^ + —. l<H<...<i r_ f c<rP i l n A " \ 1 M ,„ N There is an f? such that r > R implies that the inequal i ty (6.1) holds. O n the other hand, i f r < k, then we need only ensure N > M. T h u s we may assume k <r < R, for wh ich there are only finitely many possible values of r. F i x r i n this range. For the given r , there is a finite set of first Sfc-defective numbers of order r . L e t n' = p[ • • • p'r, where p'-, < ... < p'r, be one such number. T h e n since Sfc(n') < n', we have that i > E i l<U<...<ir_fc<r a. N o w i f n — pi • • • pr, where p\ < ... < pr and Pi > p\ for i = 1 , . . . , r , then 1 > a >- E — l<ii<...<ir_fc<r T h i s implies that Ph • • • Pir-k I M M > + — < c H . l<h<...<ir-k<r 1 T~k If we choose n large enough such that M l - a n~ < ~ ~ 2 ~ ' 42 then we have that n — Sk{n) < M as desired. There are only finitely many r for wh ich we must apply this analysis. For each such r, there are only finitely many first Sfc-defective numbers of order r , and as already stated, for any s^-defective number n = pi • • • pr, there is a first Sfc-defective number n' = p[ - • • p'r of order r such that Pi < Pi- T h i s proves the lemma. • T h e fol lowing Coro l l a ry is a companion to Coro l l a ry 15, and is an immediate consequence of the preceding L e m m a . C o r o l l a r y 26 Let k € N, and let d > 0. The equation n — Sk{n) — d has at most finitely many solutions. N o w let us look at some new prime symmetr ic functions. For 6 > 0, let / = Si + b. In [3], the case when 6 = 1 was studied It was shown that repeated i tera t ion of / eventually terminates i n the cycle 7 , 8 , 7 , 8 , e x c e p t when n < 7, i n wh ich case the sequence terminates i n 1 or 6. We w i l l show that for any 6 > 0, the funct ion / w i l l u l t imate ly terminate under repeated i tera t ion i n an / - c y c l e , or an /-perfect number. Fur thermore, we w i l l show that there are on ly finitely many such / - cyc les . For convenience, we w i l l consider an /-perfect number to be an / - c y c l e of length 1. T h e o r e m 27 Let 6 > 0 and let f — s\ + b. If n e N, then the f-sequence of n terminates in an f-cycle. Furthermore, there are only finitely many f-cycles. Proof. W e first need to show that the /-sequence of n must terminate i n an / - c y c l e . If not, then l i n i j _ > 0 0 f^(n) = oo. Le t p be the least pr ime not d iv id ing 6. If r > p, then elements of the sequence r, r + 6, r + 2 6 , . . . , r. + (p — 1)6 can not a l l be pr ime since one must be divis ible by p but s t r ic t ly greater t han p. B y L e m m a 25, there is an N such that i f n > N is not pr ime, then n > f(n) + 2pb. W h e n we iterate by / , a l l s t r ic t ly increasing subsequences of consecutive terms beginning above N are of the form q, q + 6 , . . . , q + ib, where q, q + 6 , . . . , q + 43 (i — 1)6 are pr ime, q + ib is not prime, and i < p — 1. In this case, we have that (g) = / ( g + i t ) < g + i& - 2p6 < q - pb. If g > max{7V + pb, / ( l ) + p6, / ( 2 ) + pb,..., f(N) + pb}, then fW(q) can never ascend above g + p 6 for any j. Thus the /-sequence of n, must terminate i n an / - c y c l e , since i n order for l i m ^ o o f^(n) = oo, it must contain such primes q. Showing there are only finitely many such cycles is done s imi la r ly to the first part of the proof. If there were infini tely many, we could choose a rb i t ra r i ly large least elements of such cycles. Clear ly , we can choose N large enough so that (1), i f n > iV is the least element of an / - cyc l e , then n is pr ime, and (2), i f m > N is not pr ime, then TO > / ( T O ) + pb. Le t n > N be the least element of an / - c y c l e . T h e n n is pr ime, and there is a least i < p such that n + ib is not prime. T h e n /( J + 1)(n) = f(n + ib) <n + ib — pb<n. T h i s contradicts that n is the least element of an / - c y c l e , and the Theorem is proved. • W e w i l l i l lustrate this Theorem w i t h the case when 6 = 2. Example 6 Let f = si + 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 various values of 6, and corresponding complete lists of / -cyc les , where / = s\ + b. 44 b / -cyc les 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} 45 Appendix A Maple Algorithms Computer searches and much of the experimentation for this exposition was done us-ing Maple. In this section I include some of the algorithms for computing some of the prime symmetric functions. First note that the wi th( l ina lg) : , 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 ui{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 fi(n) whose entries are the prime factors of n with repetition. pvect:=proc(n) c:=0: v:=array(l..1,1..bigomega(n)): 46 k:=omega(n): for i from 1 to k do for j from 1 to ifactors(n) [ 2 ][i] [ 2 ] do c:=c+l: v[l,c] :=ifactors(n) [2] [i] [1] : od:od: return(v): end proc: To calculate efc(n), use the following: e:=proc(k,n) v:=ifactors(n) [ 2 ] : r:=omega(n): s:=sum(v[j][2]*v[j] [ l ] ~ k , j = l - - 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[l,a[i][j]],j=l..k),i=l..binomial(b,k)); return(sk); end proc: 47 For example, to compute ss(174960), we would type s ( 5 , 1 7 4 9 6 0 ) ; H i t t i n g re turn yields the correct output of 134942. 48 Bibliography [1] A p o s t o l , T . , Introduction to Analytic Number Theory, Springer, N e w Y o r k -Ber l in -Heide lberg-Hong K o n g - L o n d o n - M i l a n - P a r i s - T o k y o , 1976. [2] B u r t o n , D . M . , Elementary Number Theory, A l l a n and B a c o n , Inc. Bos ton-London-Sydney, 1976. [3] Cadogan , C . C . and Cal lendar , B . A . , A problem on positive integers N e w Zealand M a t h . M a g . 11 (1974), 87-91, 94. [4] C h a n d r a n , V . R . , On generalized unitary perfect numbers, M a t h . Student, 61 (1992), 54-56. [5] Cohen , G . L . and te Riele , H . J . J . , Iterating the sum of divisors function. Exper imen t . M a t h . , 5 (1996), 91-100. [6] D u n h a m , W . , Euler The Master of Us All, T h e M a t h e m a t i c a l Assoc ia t ion of A m e r i c a , 1999. [7] Hardy , B . E . and Subbarao, M . V . , On hyperperfect numbers, Congr . Numer . , 42 (1984), 183-198. [8] Hunsucker , J . L . and Pomerance, C , There are no odd super perfect numbers less than 7 x 1 0 2 4 , Indian J . M a t h . 17 (1975), 107-120. [9] Loweke, G . P . , The Lore of Prime Numbers, Vantage Press, N e w Y o r k -Wash ing ton-At lan ta -Los Angeles-Chicago, 1982. 49 [10] M c C r a n i e , J . S., A study of hyperperfect numbers, J . of Integer Seq., 3 (2000), 153-157. [11] M i n o l i , D . , Issues in nonlinear hyperperfect numbers, Ma themat i c s of C o m p u -ta t ion , 34 (1980), 639-645. [12] Nathanson , M . , Elementary Methods in Number Theory, Springer, N e w Y o r k -Ber l in -Heide lberg-Hong K o n g - L o n d o n - M i l a n - P a r i s - T o k y o , 2000. [13] N i v e n , I., Zuckerman, H . , Montgomery, H . , An Introduction to the Theory of Numbers, J o h n W i l e y and Sons, Inc., N e w York-Chiches ter -Br isbane-Toronto-Singapore, 1991. [14] Pomerance, C , Multiply perfect numbers, Mersenne primes and effective com-putability, M a t h . A n n . 226 (1977), 195-206. [15] Suryanarayana, D . , Superperfect Numbers, E l e m . M a t h . , 24 (1967), 16-17. [16] te Rie le , H . J . J . , Hyperperfect numbers with three different prime factors, M a t h -ematics of Compu ta t i on , 36 (1981), 297-298. [17] Tat tersa l l , J . J . , Elementary Number Theory in Nine Chapters, Cambr idge Unive r s i ty Press, 1999. [18] E r i c W . Weisstein . " N e w t o n - G i r a r d Formulas ." F r o m M a t h W o r l d - A Wol f r am W e b Resource. h t t p : / /ma thwor ld .wo l f r am.com/Newton-Gi ra rdFormulas .h tml [19] E r i c W . Weisstein et a l . " S y m m e t r i c Po lyno -m i a l . " F r o m M a t h W o r l d - A Wol f ram Web Resource, h t tp: / / m a t h w o r l d . w o l f r a m . c o m / S y m m e t r i c P o l y n o m i a l . h t m l [20] Woodford , R . , A Variation on Perfect Numbers, Integers: E lec t ron ic Jou rna l of Combina to r i a l N u m b e r Theory, 4 (2004), A l l . 50
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Prime symmetric divisor functions
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Prime symmetric divisor functions Woodford, Roger 2005
pdf
Page Metadata
Item Metadata
Title | Prime symmetric divisor functions |
Creator |
Woodford, Roger |
Date Issued | 2005 |
Description | In this thesis, we study a new class of divisor-related functions: the prime symmetric functions. The elementary prime symmetric functions are denned on the nonnegative integers. They take the values of the elementary symmetric functions applied to the multi-set of prime factors with repetition of an integer n. These functions are first defined i n [20]. In this thesis, we refine some of the definitions presented there, and revisit some of the key results regarding such functions. The prime symmetric functions are polynomials over Q in the elementary prime symmetric functions, with values in Z. We look at basic properties of prime symmetric functions. We study the effect of iteration of these functions, and look at the question: when does iterating produce cycles? We consider the inverse question of when and in how many ways a number n can be expressed as f(m) for certain predetermined prime symmetric functions. As well, we look at asymptotic approximations for certain classes of prime symmetric functions. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2009-12-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0080069 |
URI | http://hdl.handle.net/2429/16789 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2005-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2005-0703.pdf [ 1.63MB ]
- Metadata
- JSON: 831-1.0080069.json
- JSON-LD: 831-1.0080069-ld.json
- RDF/XML (Pretty): 831-1.0080069-rdf.xml
- RDF/JSON: 831-1.0080069-rdf.json
- Turtle: 831-1.0080069-turtle.txt
- N-Triples: 831-1.0080069-rdf-ntriples.txt
- Original Record: 831-1.0080069-source.json
- Full Text
- 831-1.0080069-fulltext.txt
- Citation
- 831-1.0080069.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080069/manifest