"Science, Faculty of"@en . "Mathematics, Department of"@en . "DSpace"@en . "UBCV"@en . "Duarte, Martin Christopher"@en . "2009-12-11T17:01:20Z"@en . "2005"@en . "Master of Science - MSc"@en . "University of British Columbia"@en . "This paper gives an exposition of the Selberg Sieve and its application to the\r\nsifting of prime pairs. In particular, Selberg's methods are applied to the sifting\r\napproach of Eratosthenes and to an alternate sifting approach presented\r\nby the author. The results obtained are then used to show that the sum of\r\nthe reciprocals of the twin primes (and similarly for general prime pairs) is\r\nconvergent or finite. This paper is intended to be mostly self-contained and\r\nwill hopefully be readable to someone with little background in the area of\r\nSieve Theory."@en . "https://circle.library.ubc.ca/rest/handle/2429/16435?expand=metadata"@en . "The Selberg Sieve and Prime Pairs by Mart in Christopher Duarte B . S c , York University, 2001 A THESIS S U B M I T T E D IN P A R T I A L F U L F I 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 Master of Science in The Faculty of Graduate Studies Mathematics The University Of British Columbia Apr i l 21, 2005 \u00C2\u00A9 Martin Christopher Duarte, 2005 11 Abstract This paper gives an exposition of the Selberg Sieve and its application to the sifting of prime pairs. In particular, Selberg's methods are applied to the sift-ing approach of Eratosthenes and to an alternate sifting approach presented by the author. The results obtained are then used to show that the sum of the reciprocals of the twin primes (and similarly for general prime pairs) is convergent or finite. This paper is intended to be mostly self-contained and will hopefully be readable to someone with little background in the area of Sieve Theory. i i i Contents Abstract i i Contents i i i Preface v Acknowledgements v i Dedication v i i 1 Introduction 1 2 Sieve Notations and Preliminaries 3 3 The Selberg Sieve 14 3.1 The Set-up 14 3.1.1 Selberg's Main Theorem 14 3.1.2 Bounding X(d) , 19 3.2 Estimates for G(x) and E(D, P) 21 3.2.1 Using Rankin's Device 21 3.2.2 A n Asymptotic Bound 25 3.2.3 The Error Term 33 4 Twin Primes 34 4.1 Sifting for Twin Primes 34 4.1.1 A n example of the Sieve of Eratosthenes 34 4.1.2 A n Alternate Sieve for Twin Primes 35 4.1.3 Proving the Alternate Sieve works 36 4.2 Applying Selberg's Results to Twin Primes 38 4.2.1 The Eratosthenes Approach 38 4.2.2 The Alternate Approach 39 Contents iv 4.3 Sumof the Reciprocals, of Twin Primes . . . . . . . . . . . . . 41 5 G e n e r a l P r i m e P a i r s ( G . P . P . ) 45 5.1 Sifting General Prime Pairs 45 5.1.1 A n example of the Sieve of Eratosthenes'. . . . . . . . . . 45 5.1.2 The Alternate Sieve for General Prime Pairs 46 5.1.3 Proving the General Alternate Sieve works 48 5.2 Applying Selberg's Method 51 5.2.1 The Eratosthenes Approach 51 5.2.2 The Alternate Approach 53 5.3 Sum of the Reciprocals . . . 55 6 C o n c l u d i n g R e m a r k s 58 B i b l i o g r a p h y 60 Preface I was in my senior year of high school when I first learned about twin primes and the famous Twin Prime Conjecture. Though I found the problem fas-cinating at the time, I had given it little thought and soon forgot about it. Then in the beginning of the second year of my studies at York University, I was once again introduced to the outstanding problem. I was once again fascinated by the fact that nobody could solve this problem over the course of approximately the last two thousand years. I asked a close friend of mine at the time if he would be interested to work on the problem with me. It soon became clear that he was not interested and I began to seriously think about the problem on my own. I recall staying behind after one of my computer science lectures to ponder the mysteries behind twin primes. I began to notice some peculiarities among the twin primes and later would discover the alternate sifting approach to that of Eratosthenes, along with a quite cumbersome proof that it worked. I knew next to nothing about modular arithmetic at the time. Over the last few years I made some progress toward cleaning up the proof and also learned some number theory and of the existence of Sieve Theory. I then met my supervisor, Greg Martin, at the University of British Columbia and he suggested that I learn more about Sieve Theory. It is thus that the thesis you are about to read came into being. In particular, I have focused on the Selberg Sieve and much of the paper is dedicated to an exposition of it. I have then applied Selberg's results to the Eratosthenes approach for sifting twin primes and to my own approach as well. I have also discovered that the alternate approach works for general prime pairs as well. In fact, by making that discovery, I have come to'a greater understanding of how the alternate sieve works. The proofs showing that it works for twin primes and general prime pairs have been greatly simplified making good use of modular arithmetic. Finally, I have also applied Selberg's results to both sifting approaches in the case of general prime pairs. vi Acknowledgements I would like to thank Greg Mart in for all of his guidance with this thesis. Without his support and supervision, this paper would have been impossible. I would like to thank David Boyd for taking the time to be the second reader. Thanks to Lee Yupitun and Izabella Laba for providing me with the necessary information for ensuring that all requirements are met for submission of this thesis. Thanks to Michael Forbes for providing the necessary tools used to format the paper. I would also like to thank all my family, friends, peers, and especially Mariah Hamel and Abbas Moameni. Without their support, I could not have achieved this accomplishment. V l l To My Parents This accomplishment was made possible by the sacrifices and hard work of my parents, Mart in and Shira Duarte. I thank you both for your ever continuing love and support. Chapter 1 i Introduction What is a Sieve /SIV/n.? The first definition that follows is provided by the Oxford Minidictionary, whereas the second is provided by the author. 1. Utensil with a wire mesh or gauze through which liquids or fine particles can pass. -v.t. put through a sieve. 2. A mathematical cancellation process by which a desired set of num-bers/objects is yielded from a larger set of numbers/objects. Eratosthenes, a mathematician of ancient Greece, is the first known per-son to have constructed a mathematical sieve (third century, B .C . ) . He started with a list of odd numbers and then proceeded to cancel 3 2 and every third number thereafter, then cancel 5 2 and every fifth number thereafter, and so forth. After going through this process, one is left with the number 1 and the prime numbers. Today, this process is generally referred to as the \"Sieve of Eratosthenes\" and makes use of the observation that a number, n, if not prime, has a prime factor less than or equal to ^/n. For example, one starts with a list of all integers from 1 to N, and then cancels the proper multiples of all the primes, p, between 1 and y/N. The numbers yielded by this sieve are 1 and the primes between 1 and N. In 1808, A . M . Legendre observed that sieves can be used to give useful information about the distribution of primes and provided a more analytical formulation of the concept. His work and the work of those that follow him, like Brun and Selberg, provide the necessary tools and notations of Sieve Theory. The Selberg formulation and results can be used for a variety of prob-lems where sieves provide useful information. One such problem is the so called \"Twin Prime Problem\". A Twin Prime is a pair of prime numbers that differ by 2; (5,7) and (11,13) are examples. They are usually sifted by simply picking them out after conducting the Sieve of Eratosthenes. While it is well known that prime numbers occur infinitely throughout the integers, it is still an open question as to whether or not twin primes occur infinitely Chapter 1. Introduction 2 often. One may also wish to consider more general prime pairs, (p,p + 2B). It is also unknown whether or not they occur infinitely often throughout the integers. Selberg's method provides useful upper bounds for both problems: up-per bounds on the number of twin primes less than X, and on the number of general prime pairs less than X. A n alternate approach to the Sieve of Eratosthenes for sifting the twin primes, or general prime pairs, also leads to the same upper bounds. In all cases, one can deduce that the sum of the reciprocals of the twin primes is convergent (or possibly finite), and similarly for more general prime pairs. 3 Chapter 2 Sieve Notations and Preliminaries In order to discuss the Selberg Sieve and applications of it, we first need to look at the notations and language of Sieve Theory. Several lemmas and identities that wil l be needed should also be mentioned. The following are some identities that are relevant when discussing sieves; they can be found in many texts on Analytic Number Theory. Where p represents a prime and C is a constant, \u00C2\u00A3 ^ _ , o g O T + 0 (l) (2.1) p 2 . We also recall a key identity involving the Mobius function: T,M = {1 otherwise. <2\"4) Chapter 2. Sieve Notations and Preliminaries 4 A will denote a set of numbers we wish to sift. A typical example would be to let A be the set of natural numbers up to some bound, and then proceed to sift (choose via a cancellation process) this set for numbers not divisible by certain primes, i.e., cancel the numbers from A that are divisible by certain primes. Ad will denote the set of numbers in A that are divisible by d. P wil l denote a product of distinct primes, not necessarily containing all the primes up to some specified bound. However, in many cases, p l ( d ) | A i | d\P - * n ( i - ^ ) + \u00C2\u00B0 f e * < > y <\"3) P<2 V F / \d\P J The function p just mentioned plays a very important role in Sieve Theory. It is related to another concept known as sifting density, or dimension of a sieve. The function p has a sifting density K if a certain average of p(p) at primes p is not greater than K (and the sieve is said to have dimension re). For twin primes, p has a sifting density of 2 since f(n) \u00E2\u0080\u0094 n(n + 2) = 0 (mod p) has 2 roots for primes p > 3 and 1 root for p = 2. Similarly, one can check that p has a sifting density of 2 for more general prime pairs, where f(n) = n(n + 2B). We will see later how the sifting density concept is defined for sieves in general. It also turns out that the following assumptions can be made about the function p: (1) 0 < p{p) < p when p | P (2) p(p) = 0 whenever p \ P . Convention: p(d) ^ 0 only when d \ P means that the condition d \ P may be omitted from any sums involving p(d). Definition 2.3 When Ad, X, and p{d) are specified, define the \"remainder\" rA{d) by \Ad\ = X ^ - + rA{d) if d\P, d d < D, (2.17) Definition 2.4 When inequalities (2.16) and (2.17) hold, we say that A + , A -are (respectively) upper and lower sifting functions of level D for the product P. Definition 2.5 Define the expression V(P) by v w _ E ^ = n(i_<*e>). (2.i8) d\p P\p ^ y ' V+ and V~ are similarly defined where u. is replaced by X+, \~ respectively. This along with identity (2.15) and D/d > 1 gives the following useful result: E w \u00C2\u00AB \u00C2\u00BB E ^ ^ n ( ' - f ) \" ' = ^ (\u00C2\u00AB\u00C2\u00BB) d\p d\p p\p v F J v ' d \" . XV-(D, P) + R-(D, P) < S(A, P) < XV+(D, P) + R+(D, P), (2.20) where S is as in identities (2.8) and (2.9) and v \u00C2\u00B1 [ D j p ) = \u00C2\u00A3 m ? m , R \u00C2\u00B1 { D , P ) = \u00C2\u00A3 \%(d)rA(d). (2.21) d\P d\P Chapter 2. Sieve Notations and Preliminaries 8 Proof: Taking B = (a, P) in inequality (2.16) and summing over a G A as in Legendre's Identity (2.10), we get Y,W)\M < s(A, p) < ] T A M \u00E2\u0080\u00A2 d\P d\P Making use of Identity (2.14) we now have A5(d) (x4& + rA(d)) < S(A, P) < \u00C2\u00A3 AS(\u00C2\u00AB0 (X4& + rA(d)) , d\p ^ ' d\p ^ \" / from which the statement of the theorem follows. Q.E.D. The goal, therefore, is to find and choose A* and D so that i t 4 are relatively small in comparison to XV^, and much work is done in estimating V\u00C2\u00B1 and R\u00C2\u00B1. It turns out that things can be done in such a way that A ^ ( l ) = 1 (this is known as a normalizing constraint), and we will also get | A \u00C2\u00A3 ( d ) | < l for all d. (2.22) As a result of this, we have the following ^2\i(d)rA(d) d\P 3 and p(p) = 1 for p = 2. In this case, identity (2.23) follows from identity (2.1) with K = 2 (as desired). It turns out that in many sifting arguments, working with identity (2.23) can lead to annoying complications such as p depending on the size of A in some sense. Such complications are avoided, therefore, by using alternate for-mulations of the sifting density concept. However, the various formulations for sifting density are equivalent in the sense that one can be obtained from the others using the techniques of partial summation. Also, these formula-tions wil l not disagree with the K = 2 density for twin primes and general prime pairs. Definition 2.6 We say that K is a sifting density for the function p if there exists a constant L > 1 (depending on K) such that if2 1 such that KW2. (2.26) Note: The choice w = p, z = p + e shows that inequality (2.24) gives ! _ PMy\.< Kp} '\u00E2\u0080\u00A2/, V(2-.27) so p(p) is bounded away from p: p(p) < p(l \u00E2\u0080\u0094 \/Kp). Also, notice that \u00C2\u00AB is not uniquely defined. If inequality (2.24) holds.for some Ko, then it holds for K > Ko- For some sieve techniques, the following definition is used, in which will be unique (provided it exists). Chapter 2. Sieve Notations and Preliminaries 10 Definition 2.7 We say that K is a two-sided sifting density for p if it satisfies Definition 2.6 and, additionally, there exists L > L (depending on p) such that M > f 1 _ r 4 _ u ^ 4 y \u00C2\u00AB 2 < w < z . (2.28) V{P{z)) - \ \og(w)J \\og(w)J ~ \u00E2\u0080\u00A2 v ' For the Selberg Sieve, it turns out that it is more convenient to use something slightly stronger than Definition 2.6. Definition 2.8 Let g(d) be the multiplicative function defined for squarefree d by specifying for primes p: \u00E2\u0080\u00A2 (2.29) P - p[p) Using this definition, we can replace inequality (2.24) by specifying the exis-tence of a constant A > 1 such that ^2 g(p) log(p) < /dog (\u00E2\u0080\u0094) + A when 2 1 depending only on n, so that (1 \u00E2\u0080\u0094 < K for these p. Mertens' product (2.3) shows that Chapter 2. Sieve Notations and Preliminaries 11 where the O-constant may depend on K. When w > K this gives w - \ VI) ~ \ \u00C2\u00A3 c \f = - P ( o ( i - 1 + 0 (I), ( 2 . 3 1 ) so inequality (2.25) follows, with some value of the constant L. It also holds when w < K, possibly with a larger value of L, because the contribution from primes p < K to the product in inequality (2.24) is bounded. In a similar way observe when w > K v-p^ ~ J k < * p - K \" K w J where we used identity (2.1). Thus inequality (2.30) follows for these w, and remains valid for smaller w because g(p) is bounded when p < K. Q .E .D. We are now finally ready to discuss the Selberg Sieve but first we record the next four lemmas for completion and referral. See [4, Section 1.3.5] for their proofs and more detailed information on sifting density. The first two lemmas deal with Partial Summation where use of the notation of Stielt-jes integrals is convenient. Using integration by parts, one can take as a definition: f f(t)d(c(t)) = c(z)f(z)-c(w)f(w)- f f'(t)c(t)dt (2.32) J W J W when / ' is piecewise continuous on [w, z] and c is of bounded variation. Chapter 2. Sieve Notations and Preliminaries 12 Lemma 2.2 Define c(x> y)= Y 0/1 x 0, and E(t, n) < A. Then f. /(*) d(J2 9in)E{t, n) ) < A Y, f(n)g(n). Jx\ J I? \og{w)' (2.38) Chapter 3 The Selberg Sieve 14 3.1 The Set-up 3.1.1 Selberg's Main Theorem The main goal of this section is Theorem 3.1.1. It seems a bit artificial at first glance and one wonders how it was conceived, but keep in mind that Theorem 3.1.1 is the end result of a series of discoveries. The main thing to focus on here is the upper bound (3.1.9) for S(A, P). G(\fb~) is as m identity (3.1.4) and it is being used in Theorem 3.1.1 because, as will be seen later, it can be estimated in such a way that we get nice results/estimates for the upper bound (3.1.9) for S(A, P). The rest of Theorem 3.1.1, i.e., identity (3.1.10) for the error term and identity (3.1.11) involving A, are consequences of Lemma 3.1.1. In turn, Lemma 3.1.1 gives several identities, (3.1.6), (3.1.7), (3.1.8), that are conse-quences of identity (3.1.5) for V + ( A ) and are relevant to the proof and result of Theorem 3.1.1. The identity (3.1.5) shows up in the proof of Theorem 3.1.1 as a result of Selberg's clever idea: inequality (3.1.14) involving the square of the sum of the A values. We first recall the following: \Ad\=X^- + rA(d)iid\P, d In Theorem 3.1.1 and elsewhere we shall denote G ( z ) = X>(n), (3.1.4) n|P where P is a specified product of primes. In Lemma 3.1.1, the numbers X(d) may be arbitrary, subject only to a restriction that they are supported on an interval 1 < d < VT), so that all the sums appearing in Lemma 3.1.1 are finite. The restriction to p(h) ^ 0 in identity (3.1.6) is a natural one, because for other h the summand x2(h)/g(h) is a multiple of p(h) as follows: identity (3.1.7) gives p(h) \ x(h), so that x2(h) = p2(h) \u00E2\u0080\u00A2 I, for some I. Now x2(h) _ (x2(h)p*(h)) (p2(h).l-p*(h)) 9(h) pih) p(h) so after cancellation of p(h) from the numerator and denominator, the sum-mand is a multiple of p(h). Lemma 3.1.1 Define v+(\)=YE 7 T p \u00E2\u0080\u00A2 ( 3- l 5) dx\Pd2\P 2* Then h * W H ) : (3 :1.8) Chapter 3. The Selberg Sieve 16 Proof: Using [di, ofo] = d\d2/(d\, d2) in equation (3.1.5) gives V+(\)= S^S^ Kdi)p(di) Kd2)p(d2) (di, d2) p((di,d2))#0 Since f = (d\, d2) is squarefree, the last fraction may be expressed as / We therefore have, v+t\\- \ ^ V ^ A(c?2)p(ti2) ^ 1 ( A ) - 2 ^ 2 ^ 5; ^ 2_. zThy di d2 1 2 h\{dud2) y K ' p((di, d2))#0 Rearranging the order of summation gives V W ~ 2^-g-{K) 1 , J, ^ d2 h 1, then S(a, P) = 0 and the right side is non-negative. The right side of inequality (3.1.14) can be written E E \u00C2\u00A5 ) A W = E E a ^ ) W E 1-di\(a, P) d2\(a, P) di\Pd2\P [du d2]\a On summing over a G A and expressing the result in terms of p from identity (3.1.1), this gives \2(1)S(A, P) < XV+{\) + \2(1)E(D, P), (3.1.15) with V+(\) as in identity (3.1.5) and E(D, P) as stated in identity (3.1.10). If we had A(l) = 1, then we would have achieved the result of Theorem 2.1. The conclusions of Theorem 3.1.1 are achieved by minimizing V+(\), thereby getting the best bound possible for S(A, P). We now proceed to show how this is done. In discussing V+(X) we may streamline the notation by using the con-vention that p(d) = 0 if d \ P, together with a natural one that terms with p(d) = 0 are not to be included in summations over d. This wil l save a certain amount of repetition of the conditions d \ P or p{d) ^ 0, where these are implied. Similarly, the conditions d < y/TJ, p2(d) = 1 need not be explicit in a sum involving \(d). Theorem 3.1.1 will follow by choosing x(k) so as to minimize, for given A(l ) , the expression (3.1.6) for the quantity V + ( A ) . The constraint E t*(k)x(k) = A(l) (3.1.16) k/5 y K ' J \k | C | \u00C2\u00A3 5 ( / ) \u00C2\u00A3 g(n). (3.1.21) f\d (n, d)=l n/d With the identity (3.1.20) this gives i \u00E2\u0080\u0094 by the expression (3.1.13) for \(d). | A ( 1 ) | > | C | ^ \u00C2\u00A3 9(n) = \X(d)\, (n, d)=l n Gz(x) (3.2.25) when z < x. In Theorem 3.1.1, a lower bound for G(x) is required (with x \u00E2\u0080\u0094 \fD), so a lower bound for Gz(x) is relevant.. It is natural to denote G,(oo) = \u00C2\u00A3 9{d), d\P(z) Chapter 3. The Selberg Sieve 22 so that Gz(x) = Gz(oo) whenever x > P(z). Observe, referring to the identities in (3.2.24) where necessary, > (3.2.26) We see here a connection between Gz(x) coming from Selberg's method and the product V(P), but the inequality is in the wrong direction. The next theorem will give us what we seek, but first the lemma. Lemma 3.2.1 Suppose that the assumptions (3.2.22) about p hold, and de-note Iz(x) = G z(oo) - Gz(x) = \u00C2\u00A3 g(d), (3.2.27) d>x d\P{z) and write x \u00E2\u0080\u0094 zv. Then for each c > 0 Iz(x) < ^ ^ e x p ( - c t ; + B ( e c - 1)). (3.2.28) In particular where, for each v > 0, ipB(v) = max JO, v log - v + = J log (Jj^j Proof: dt. We use Rankin's device. Letting e > 0, we observe that when d > x, we have (d/x)\u00E2\u0082\u00AC > l e = 1, so we get Chapter 3. The Selberg Sieve 23 /,(*) = J2 9(d) < \u00C2\u00A3 g(d) (\u00C2\u00B1Y d>x d>x ^ ' d\P(z) d\P{z) * E +!>\u00C2\u00AB(\u00C2\u00A3) d>x v 7 d 0. Then ze \u00E2\u0080\u0094 ec. Observing that (e* \u00E2\u0080\u0094 \)/t increases when t > 0, we have when p.< z, pe \u00E2\u0080\u0094 I e clog(p)/16g(z)-J_ j g'c _ ]_ - \u00E2\u0080\u00A2 elog(p) clog(p)/log(z) ~ c It follows that f - 1 < \u00E2\u0080\u0094 ( 6 l o g ( p ) ) = ^ \u00E2\u0080\u00A2 - 4 - \u00E2\u0080\u00A2 log(p) = (ec -c c log(z) log(z) and when x = zv, xt = (zv)\u00C2\u00A3 = (ze)v \u00E2\u0080\u0094 (ec)v \u00E2\u0080\u0094 e00. Using these facts along with the assumptions (3.2.22) about p, and the fact that summing over p < z Chapter 3. The Selberg Sieve 24 < eu is greater or equal than summing over p | P(z), we now have Iz(x)V(P(z)) < l e x p f \u00C2\u00A3 ^ f y - l ) | \m>) v J < exp (-cv + B ( e c - 1)), as required for inequality (3.2.28). The optimal choice of c satisfies v = Bec, i.e. c = log(f) \u00E2\u0080\u0094 log(S), provided v > B. If v < B then the best permissible choice is c = 0. This yields inequality (3.2.29) and the proof is complete. Q.E .D. Theorem 3.2.1 Suppose that the assumptions (3.2.22) about p hold, where z>2, and write z = D1/S. Then GZ(VD), as defined by (3.2.23), satisfies nPjz)) - G z { V D ) - nPjzTy ( 3 - 2 - 3 1 ) where ipB is as in the last lemma. In particular, ^ b Q s ) ~ ^ s i \u00C2\u00B0 s ( s ) a s s -> \u00C2\u00B0\u00C2\u00B0. e x p ^ - V t e Q s ^ < e7B~a for all s > 0. Proof: The second inequality in (3.2.31) is just (3.2.26). The proof of (3.2.31) is completed by noting that inequality (3.2.26), identity (3.2.27), and inequality (3.2.29) give r i~\ r tn~\ r r~\ -> 1 ~ exp(-^ B ( t ;)) Gz(x) = G 2(oo) - Iz(x) > V{P(z)) ' Chapter 3. The Selberg Sieve 25 and taking x = VD, so that the notations zv = x and z = D1^ require v = | s . We get exp(V>B(|s)) < e7B~s by taking the choice c = 2 in the last lemma and noting that e 2 \u00E2\u0080\u0094 1 < 7. Q.E.D. 3.2.2 An Asymptotic Bound Though the last theorem provided a lower bound for GZ(\/~D), it is not the sharpest result. It turns out that in many applications of Theorem 3.1.1, one wishes to estimate Gz(x) from below in the case when z = x. The next theorem provides a much desired, sharp asymptotic lower bound. The proof of the theorem makes use of ]TS(P) log(p) = K\og(v) + n(t/) (3.2.32) p z ) ) + s \u00C2\u00BB ( x ) nn(y) - relog(y), we have U x ) = Ygz(.n)EZtn with EZtn{t) < ?7(min(i, z)), (3.2.37) n 1, m 1. Then \u00E2\u0080\u00A2 . ' G ' ^ r ( . + TO(1 + \u00C2\u00B0 ( i 4 ) ) ' ( 3 ' 2 ' M ) where V(P) is as defined earlier. The implied' constant depends only on K. In (3.2.39) we may use = - 7 \u00C2\u00AB \u00E2\u0080\u00A2 ^ ( - \u00C2\u00B0 ( ^ ) ) n ( - J ) ' 0 - f r -(3.2.40) V (P(X)) X , p < x Chapter 3. The Selberg Sieve 28 Equation (3.2.40) follows from Mertens' product discussed earlier. The form on the right (with x = z) is what wil l be seen in the following proof. Proof: This theorem refers to Gz(x) only in the case z = x, and Lemma 3.2.2 gives fx dt G{x) log(x) = (K + 1) J G(t)j + 6(x), (3.2.41) where *(*) = 5 > ( n ) i ^ (\u00C2\u00A3) . (3.2.42) n z by specifying 1 - M = ( 1 . I Y if p > z . (3.2.43) p V P) This will make questions relating to the convergence (as x \u00E2\u0080\u0094> oo) of the product in equation (3.2.40) become trivial. Also, when p > z the function g as in identities (3.2.24) now satisfies g(p) = Pfr) = P(P)/P = (P(P)/P) + 1 - 1 _ - (1 - P(P)/P) + 1 p-p(p) l-p(p)/p l-p(p)/p l-p(p)/p The last equality follows from the binomial theorem and the two equalities before that follow from (3.2.43). Now inequality (3.2.38) extends to an in-equality valid also when t > z, rj(t) < Ai < A when 2 < t, (3.2.45) where the constant A\ may be somewhat larger than A. Using Stieltjes integrals, equation (3.2.41) leads to G(t) log K ( i ) ' (3.2.46) Chapter 3. The Selberg Sieve 29 This is best seen as follows. Re-arranging (3.2.41) gives 5(x) = G(x) log(s) - (K + 1) J* G(t) Differentiation gives dt dS(t) = (d(G(t)) log(t) + G(t )y) - (\u00C2\u00AB + = d(G(t))log(t) - K^-dt , t thereby giving ^77T = (<*\u00C2\u00AB?(*)) log(t) - A ) . (3.2.47) log K + 1 (\u00C2\u00A3 ) log\" + 1 ( i ) Now we also compute the following G\u00C2\u00AE ^ = d(G(t))log-\"(t) + G(t){-K\og-K-\t))ldt logK(*) d(g(t)) bg(t) 1 G(t) l og K + 1 ( i ) Iog\"+1(<) \u00C2\u00AB = ^ ^ ( d ( G ( t ) ) l o g ( t ) - \u00C2\u00AB ^ i f t ) . (3.2.48) Equating (3.2.47) and (3.2.48) and integrating yields (3.2.46). Denote ( 3 ' 2 ' 4 9 ) Then, for 2 < x. < y, (3.2.46) and (3.2.42) give Here En(t/n) < \"because of identity (3.2.35) and inequality (3.2.45), so Lemma 2.3 applies, to give H{y)-H(x) 1. When U > 2 we find v g(n) 1 G(UC) 1 uhu>^+1(n) ~ log(C7) log\u00C2\u00AB([/) log([/) ^ j-The last equality follows from (3.2.49) and basic rules of logarithms. So we now have n0 Now choosing C = 1 + 1/(K + 1) ensures | l / c | < 1 so that we get r* V - = cK -r>0 v C K + 1 H \u00E2\u0080\u0094 rK u ~ \u00C2\u00B0 ' ~ ~ - ( i / c ) ~ c - r Finally, using the fact that ( l + ( l / n ) ) n < e for all n > 0, (see [7, pgs. 63-64]), we have c - i i / ( \u00C2\u00AB + i ) V K + i y Now let 0 < e < ^, and let J \u00E2\u0080\u0094 l i m s u p ^ ^ , H(t). Then J is finite, for otherwise there would exist a sequence yn such that H(yn) -\u00C2\u00BB\u00E2\u0080\u00A2 00 as n \u00E2\u0080\u0094>\u00E2\u0080\u00A2 00, #(y n ) > (1 - e) sup H(t), t x so that H(y) > J - e. We manipulate inequality (3.2.51) and use these inequalities to get H(x) > H(y) - sup Hit) log(--c) x H(y)--^-AJ + e) \og{x) Ai Ai log(x) log(x) = J | 1 _ R 4 T V - . f i + ^2 log(x) / V !og(x)y Now take 0 < e < J / log(x) , so that with identity (3.2.49) we have \u00C2\u00B0 { X ) =H(x)>j(l + o(-^-)), (3.2.52) log\"(x) - ^ ~\log(x) initially for sufficiently large x, and so for x > 2. We need a partial identification of the constant J. For this purpose we have the following Dirichlet series: * . M - E ^ = II(I + ^ ) n=l P since g is supported on squarefree numbers. Recalling integration by parts and,Lemma 2.2 with C = G and f(t) = l/ta, when s > 0 we have w = E^- /><*\u00C2\u00BB Now G ( l \u00E2\u0080\u0094 e) = 0 for every e > 0 and l im^oo G(t)/ts \u00E2\u0080\u0094 0 so we just get /oo G(t)d(t-) Chapter 3. The Selberg Sieve 32 Appealing to inequality (3.2.52) and then using the substitution u = log(i), we get /oo G(t)d(t-) /oo (J + o(l))logK(t)d(rs) poo = s (J + o(l))uKe-sudu Jo JT(K + 1) . ~ \u00E2\u0080\u0094 i '- as s ^ 0 + , sK where the quantities o(l) are as t \u00E2\u0080\u0094\u00E2\u0080\u00A2 oo and u \u00E2\u0080\u0094+ oo. The last approximation above follows from the definition of the Gamma function: xr-xe-xdx , with the substitutions r = K + 1 and x \u00E2\u0080\u0094 su (so dx \u00E2\u0080\u0094 s du). We now recall some facts about the Riemann \u00C2\u00A3 function: (2) \u00C2\u00A3(s + 1) has a simple pole at s \u00E2\u0080\u0094 0, and ((s + l )s \u00E2\u0080\u0094\u00E2\u0080\u00A2 1 as s \u00E2\u0080\u0094> 0. Using these facts along with the inequality we have for Zg(s), we get the following: l imsuPIT (1 - - = r V (1 + \u00E2\u0080\u0094) = l i m s u P < J - T ( * + I). (3.2.53) Our choice (3.2.43) of p(j>) when p > z ensures that the product on the left converges when s = 0, being in fact finite for this s. Observe when z < x < y the contribution to (3.2.53) from large p is Chapter 3. The Selberg Sieve 33 Because of equation (3.2.44) the summand is 0 ( l / p 2 ) when s > 0, so the sum converges uniformly to a sum continuous in s > 0. That is, the product in (3.2.53) is continuous in s > 0. It is now easy to infer -l -,nHH-f) Theorem 3.2.2 now follows in the form using identity (3.2.40) on taking x = z in inequality (3.2.52). Q.E .D. 3.2.3 The Error Term The following theorem provides an upper bound estimate for the Error term, E(D, P(z)), in Theorem 3.1.1. Theorem 3.2.3 Suppose that equation (3.1.1) holds with \rA(d)\ < p(d), pip) > 1 when p \ P, (3.2.54) and that p has sifting density K. Then E(D, P{z)) \u00C2\u00AB \u00C2\u00A3 > l o g 2 K ( z ) . Proof: Corollary 3.1.2.1 and (3.2.54) give Then dl 4. For N \u00E2\u0080\u0094 1, 2, 3, there is nothing to do since each of 1, 2, 3 yields a twin prime. An example of the Alternate Sieve For N = 48, we worry about prime factors p where 5 < p < y/6N + 1 = y/289 = 17, i.e.,-5, 7, 11, 13 and17. For 5, ap \u00E2\u0080\u0094 1, and cancellation starts with ^ j p = 4. For 7, ap \u00E2\u0080\u0094 1, and cancellation starts with ^ p . = ' 8 . For 11, ap = 2, and cancellation starts with 1 1 6 - 1 = 20. For 13, ap = 2, and cancellation starts with 1 3 g - 1 = 28. For 17, ap = 3, and cancellation starts with 1 7 g - 1 = 48. We therefore cancel everything starting with 4 that is \u00C2\u00B1 1 (mod 5), then cancel everything starting with 8 that is \u00C2\u00B1 1 (mod 7), then cancel everything starting with 20 that is \u00C2\u00B1 2 (mod 11), then cancel everything starting with Chapter 4. Twin Primes 36 28 that is \u00C2\u00B1 2 (mod 13), and finally, cancel everything starting with 48 that is \u00C2\u00B1 3 (mod 17). We observe that some numbers are cancelled more than once. 1 2 3 i 5 0 7 9 10 n 12 n 1N5 17 18 n 22 23 H 25 26 27 2$ n 30 n 32 33 u 3v n 37 38 30 40 4? 43 44 45 0 47 One can easily verify that the remaining numbers, k, all yield twin primes ( 6 f c - l , 6k + I). 4.1.3 P r o v i n g the A l t e r n a t e S ieve works The following theorem states that the Alternate Sieve does indeed yield twin primes. B y observing that all primes p > 5 are either of the form 6m \u00E2\u0080\u0094 1 or 6m + 1, we see that all twin primes, except (3, 5), are of the form (6k \u00E2\u0080\u0094 1, 6A; + 1). Therefore, this sieve gives us all twin primes, except (3, 5). Theorem 4.1.1 For every prime p > 5, define ap, bp by 6ap \u00E2\u0080\u0094 1 = 0 (mod p), 0 < ap < p 6bp + 1 - 0 (mod p), 0 < bp < p . Let K = {k\ k 6 N and k ^ ap (mod p), Vp prime, 5 < p < V6k \u00E2\u0080\u0094 1 (when this makes sense)} P| {k\ k \u00E2\u0082\u00AC N and k ^bp (mod p), Vp prime, 5 < p < V6k + 1 (when this makes sense)} Then k G K if and only if 6k \u00E2\u0080\u0094 1, 6k + 1 are both prime. That is, (6k \u00E2\u0080\u0094 1, 6k + 1) is a twin prime. Proof: \" 5, except for p = 6k \u00E2\u0080\u0094 1 itself. 2. Ii k ^ bp (modp), Vp prime, 5 < p < V6A; + 1 , thereby indicating 6/c + 1 prime, then it is actually true that k ^ bp (mod p), Vp prime, p > 5, except for p = 6k + 1 itself. 3. We mentioned earlier that to check the primality of a number, n, we only had to be concerned about the primes p < \fn. We now observe Chapter 4. Twin Primes 38 that for every prime, p, the first composite number that is divisibly by p and has no prime factors q < p is p 2 . This means that all possible 6/c\u00C2\u00B1 1 that are divisible by p and not divisible by any prime q < p must be greater than or equal to p 2 . This means that cancellation of numbers, k, where k = ap (mod p), starts at [^-^p-J. Likewise, the cancellation of numbers, A;, where k = bp (modp), starts at L 2 - ^ ] . It is thus ensured that for all remaining numbers, k, both Qk \u00E2\u0080\u0094 1 ^ 0 (mod p) and 6k + 1 ^ 0 (mod p). We wil l refer to [ ^ J and [ ^ J as the starting points of cancellation and they are actually equal since for every p > 5, one has p 2 = 1 (mod 6). We will see later on that for a more general prime pair, the starting points of cancellation may not necessarily coincide, and there could be complications if one decided to use only the lower cancellation point. 4. We observe that if p < V6fc - 1 (y/Qk + 1), then k > [ ^ J ( L ^ J ) , which further justifies the starting points of cancellation for each prime p > 5 when the sieve is performed. Q.E.D. 4.2 Applying Selberg's Results to Twin Primes 4.2.1 The Eratosthenes Approach For the next theorem we apply Selberg's method to the numbers n(n + 2). Let 7T2(X) denote the number of n with 1 < n < X such that both n and n + 2 are prime. Theorem 4.2.1 Let . c - n f c $ , \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 . . . where the product is over all odd primes p. Then ^ 16CX ^ , ^ / O o g l o g X 7T2(X) < T - ^ T Z 1 + O l o g 2 X V V l o g * Chapter 4. Twin Primes 39 Proof: Take f(n) = n(n + 2). Then the function p in this sifting situation is given by p(p) = 2 i fp>2, p(2) = l . Thus p(p) < 2 for all p, so (as in Lemma 2.1) p has sifting density K = 2, and (3.2.38) holds with n(z,w) = 0(1). Then Theorem 3.2.2 gives G ( ^ \u00C2\u00BB a K ^ ) ( i + o f e ) ) . I W ^ ( i + o(^)), where = I n ( p - 1 ) 2 2 11 p(p-2) ^ f e ^ (C as in (4.2.1)) 2 0 ^ A , * - 1 ) = 2 ^ ( 1 + 0 ( ^ ) ) ( s e e ( 2 ' 3 1 ) W i t h w = ^ Applying Theoremsv3.1.1 and 3.2.3, we now have IX ir2(X) < S(A, P(VD)) + n(VD) < +0(D log 2* D). AD log\" VD Our result follows as stated on choosing D = X / (log X ) 2 K + 3 , where K \u00E2\u0080\u0094 2. Q.E.D. 4.2.2 The Alternate Approach In the alternate approach presented for sifting the twin primes, if we sift the numbers n where 1 < n < X/6, to retain only those for which both Chapter 4. Twin Primes 40 6n \u00E2\u0080\u0094 1,6n + 1 are prime, we obtain all the twin primes less than or equal to X. Correspondingly with the standard approach, if the numbers N = 6n \u00E2\u0080\u0094 1 are sifted where 1 < N < X, to retain those where both N = 6n \u00E2\u0080\u0094 l,N + 2 = 6n + 1 are prime, we also get all the twin primes less than or equal to X. Therefore, in applying the Selberg sieve to the alternate approach, we must sift the numbers (6n \u00E2\u0080\u0094 l)(6n + 1), just as the previous theorem sifted the numbers N(N + 2). If we let TT'2(X) denote the number of n with 1 < n < X/6 such that both 6n \u00E2\u0080\u0094 1 and 6n + 1 are prime, we observe that TT'2(X) = ^{X) \u00E2\u0080\u0094 1; (3, 5) is not counted by 7r 2(X). Hence we would expect TT2(X) to have a similar upper bound as ^ ( X ) upon applying the Selberg sieve on the numbers (6n \u00E2\u0080\u0094 l)(6n + 1). This is indeed the case as demonstrated by the next theorem, and we can actually achieve the same upper bound. Theorem 4.2.2 Let where the product is over all odd primes p. Then Take f(n) = (6n \u00E2\u0080\u0094 l)(6n + 1). Then the function p in this sifting situation is given by Thus p(p) < 2 for all p, so (as in Lemma 2.1) p has sifting density K \u00E2\u0080\u0094 2, and (3.2.38) holds with n(z,w) = 0(1). Then Theorem 3.2.2 gives Proof: p{p) = 2 if p > 3, p(2) = 0, P(3) = 0. Chapter 4. Twin Primes 41 where * - J . n > i ) V r 3 V ^ V F ; = 1 2 ^ ( 1 + \u00C2\u00B0 (TD)) ( S E E ( 2 - 3 1 ) W I T H \u00E2\u0084\u00A2 = ^ Applying Theorems 3.1.1 and 3.2.3, we have TT'2(X) < S(A,P(VD)) + Tt(VD) < 2 ' J +0(Dlog2\"D) . ^ l o g VD Our result follows as stated on choosing D = X/(log X)2K+3, where K \u00E2\u0080\u0094 2. Q.E .D. As can be seen by comparing the results of the last two theorems, the alternate approach to sifting the twin primes leads to the same upper bound as the standard (Eratosthenes) approach. 4.3 Sum of the Reciprocals of Twin Primes It has been known for quite some time that the sum of the reciprocals ,qf the prime numbers is divergent. That is; \u00E2\u0080\u00A2 i J r n 1 > oo as n \u00E2\u0080\u0094\u00E2\u0080\u00A2 oo, Pi where pi is the i-th. prime number. The proof of this fact can be found in many texts on elementary number theory (see [6, Theorem 1.19]). In particular, this result implies that there are infinitely many prime numbers (a fact earlier known to Euclid (see [6, Theorem 1.17])). So a good question to ask is \"Can this strategy be used to show that there are infinitely many twin primes?\". Chapter 4. Twin Primes 42 Unfortunately, the answer is \"No\", leaving open to this day the question as to whether or not there are infinitely many twin primes. Viggo Brun was the first to show that the sum of the reciprocals of twin primes is convergent (or finite if there are only finitely many twin primes) [2]. That is, for some constant M , where pi is the i-th. twin prime, counting the twin primes by their first members. We present a proof of this result using Partial Summation and the common result of the previous two theorems. In the proof, we will also provide an explicit constant M. Theorem 4.3.1 Let p\, p2, ... be the sequence of prime numbers p such that p + 2 is also prime. Then We wish to use partial summation, in particular Lemma 2.2 which makes use of integration by parts (2.32). Let where M is a constant. Proof: 1 if n, n + 2 are both prime, 0 otherwise. and (/ ' is continuous on [2, oo)). Then let A(x) - \u00C2\u00A3 . 0 , \u00E2\u0080\u00A2n 7T2(x) = 7T2(x), 2 g ( 0 j 2 J 1 1 1 + log(2) log 2(z) log(x) ' log(2)J (as x \u00E2\u0080\u0094> oo). From this it follows that V T J , T J , 4 Vi Pi + 2 < M, Chapter 4. Twin Primes 44 with M = 32C log(2)' Q.E.D. 45 Chapter 5 General Prime Pairs (G.P.P.) The last section gave some good results concerning twin primes; prime pairs of the form (p, p + 2), where p and p + 2 are both prime. Similar results can also be obtained for a more general prime pair, (p, p + 2B), where B > 1 is an integer constant. We shall apply Selberg's results to both the traditional (Eratosthenes) method for finding general prime pairs, and to a general version of the alternate method that was used to find twin primes. As such, we first proceed to show that the alternate sifting method can be generalized to find general prime pairs, (p, p + 25) . 5.1 Sifting Genera l P r i m e Pairs Recall in the introduction that after conducting the sieve of Eratosthenes to the set of numbers from 1 to N, one can then identify those primes that differ by 2, i.e., twin primes. Similarly, one could simply pick out those primes that differ by 25 , i.e., G.P.P.s. We provide a simple example of the Eratosthenes approach and then demonstrate the generalized alternate sifting method. Also, we provide proof that the general version of the alternate sieve works. 5.1.1 A n example of the Sieve of Eratosthenes Using the same example from before, for jV = 36, we cancel all proper mul-tiples of primes less than or equal to y/N = 6 (i.e., 2, 3, 5) and obtain 1 and all primes p where 1 < p < N. We then observe that for B \u00E2\u0080\u0094 4, (3, 11), (5, 13), (11, 19), (23, 31) are G.P.P.s of the form (p, p + 2B). Chapter 5. General Prime Pairs (G.P.P.) 46 1 7 13 19 25 31 9 n 32 2 9 n n 27 33 3 i n n 22 28 34 35 5 11 17 23 29 ft n n u m n 5.1.2 The Alternate Sieve for General Pr ime Pairs As for twin primes, one can obtain the general prime pairs (except possibly (3, 3 + 2B)) without the other primes by using a modified version of the previously described alternate approach. As before, this new sieve will ac-tually yield general prime pairs in an indirect way. Since all primes, other than 2 and 3, are either of the form 6A; \u00E2\u0080\u0094 1 or 6k + 1, we see that general prime pairs, (p, p + 2B), are either of the form (6A; \u00E2\u0080\u0094 1, 6A; + 2B \u00E2\u0080\u0094 1), or (6A; + 1, 6A; + 2B + 1). Furthermore, we see that the existence of these forms depends on the residue class, modulo 3, of B. That is, general prime pairs are of the form (6k + t, 6k + 2B + t) where Convention Note: It wil l be convenient for us to always say that general prime pairs are of the form (6A; + t, 6k + 2B + t), where it is to be understood that t has been predetermined by B , and should B = 0 (mod 3), we will say that general prime pairs have either the form (6k + t, 6k + 2B + t) or (6A; \u00E2\u0080\u0094 t, 6k + 2B \u00E2\u0080\u0094 t). Also, in several situations to follow, we will use the phrase \"(when applicable)\" in connection with the general prime pairs of the form (6A; \u00E2\u0080\u0094 t, 6k + 2B \u00E2\u0080\u0094 t), to indicate the possibility of dealing with both types of general prime pairs should B = 0 (mod 3). We shall see that the general alternate sieve is indirect in that it gives the numbers k, where both 6k + t, 6k + 2B + t are prime, and/or possibly both 6k \u00E2\u0080\u0094 i , 6k + 2B \u00E2\u0080\u0094 t are prime (when applicable); i.e., we get general prime pairs. The sieve also makes use of the observation that if 6k \u00C2\u00B1 t (or 6A; + 2 5 \u00C2\u00B1 t) is not prime, then it has a prime factor less than or equal to t < ' - 1 if B = 1 (mod 3) 1 if B = 2 (mod 3) k - 1 or 1 if fl = 0 (mod 3) Chapter 5. General Prime Pairs (G.P.P.) 47 y/W\u00C2\u00B1t (or \/6k + 2B\u00C2\u00B1t). If B = 0 (mod 3), we actually conduct two separate applications of the alternate sieve, once for t = 1, and once for t \u00E2\u0080\u0094 \u00E2\u0080\u00941. Afterward, we combine the numbers, k, retrieved from both applications, making careful note of any repeated elements. We start with all the integers from 1 to N. Since N is the largest possible \"k\", the largest possible general prime pair is (6N +1, 6N + 2B + t). As such, we need only worry about prime factors less than or equal to \/6N \u00E2\u0080\u00A2+ 2B + t, except for 2 and 3 since 2, 3 \ 6k +1, 6k + 2B + t for any k (recall that t is predetermined specifically so that 3 \ 6k +1, 6k + 2B +1). For each prime p, where 5 < p < \/6N + 2B + t, we define ap, bp by 6ap + t = 0 (mod p), 0 < ap < p 6bp + 2B + t = 0 (modp), 0 < bp < p. Then starting with J > w e cancel all numbers that are ap (mod p), and starting with [p \" g 5 - * ] , we cancel all numbers that are bp (mod p). A l l re-maining numbers, k, yield a general prime pair (6k + t, 6k + 2B +1). An example of the General Alternate Sieve We Consider the case B \u00E2\u0080\u0094 3. Here, we have both types of general prime pairs, (6k \u00E2\u0080\u0094 1, 6k + 5), and (6k + 1, 6k + 7). We conduct the sieve for each type separately and respectively, and then combine the results. Type 1: (6A; ~ 1, 6k \ 5) For N = 18, we worry about prime factors p where 5 < p < \/6N + 5 = VTI3 < 11, i.e., 5 and 7. For 5 : ap = 1, and cancellation starts with L^ -jpJ \u00E2\u0080\u0094 4. 6P = 0, and cancellation starts with L^ipJ = 3. For 7 : ap = 6, and cancellation starts with L^ pJ = 8. bp = 5, and cancellation starts with [-^pj = 7. We therefore cancel everything starting with 4 that is 1 (mod 5), and everything starting with 3 that is 0 (mod 5). Then cancel everything start-ing with 8 that is 6 (mod 7), and everything starting with 7 that is 5 (mod 7). Chapter 5. General Prime Pairs (G.P.P.) 48 1 2 3 4 ^ 0 7 8 9 .tK) 4 12 1^3 14 1^ 1^ 17 18 It is easily verified that all the remaining numbers, k, yield general prime pairs, (6A; \u00E2\u0080\u0094 1, 6fc + 5). T y p e 2: (6k + 1, 6k + 7) For N = 18, we worry about prime factors p where 5 < p < \/6N + 7 = \/Il5 < 11, i.e., 5 and 7. For 5 : ap \u00E2\u0080\u0094 4, and cancellation starts with [^f^-\ = 4. bp = 3, and cancellation starts with [*%^ J = 3. For 7 : ap = 1, and cancellation starts with = 8-bp = 0, and cancellation starts with L^ir\"J = 7-We therefore cancel everything starting with 4 that is 4 (mod 5), and everything starting with 3 that is 3 (mod 5). Then cancel everything start-ing with 8 that is 1 (mod 7), and everything starting with 7 that is 0 (mod 7). 1 2 ? ^ 5 6 X A ^ 1 0 11 12 1^ % ty 16 17 1\8 It is easily verified that all the remaining numbers, k, yield general prime pairs, (6k + 1, 6k + 7). Combining together all the numbers, k, with mul-tiplicity if needed, that we got from the double application of the sieve, we get all general prime pairs, (p, p + 6), that are less than or equal to 6AT + 7 = 6(18) + 7 = 115. 5.1.3 Proving the General Alternate Sieve works The following theorem states that the General Alternate Sieve does indeed yield general prime pairs. We have already seen that all general prime pairs, except possibly (3, 3 + 2B), are of the form (6A; + t, 6k + 2B + t) and/or (6k \u00E2\u0080\u0094 t, 6k + 2B \u00E2\u0080\u0094 t) (when applicable). Therefore, this sieve, or a double application of it (when applicable), gives us all general prime pairs, except possibly (3, Z + 2B).' Chapter 5. General Prime Pairs (G.P.P.) 49 Theorem 5.1.1 Let B > 1 be an integer constant and, { 1 if 2 5 - 1 = 0 (mod 3) (i.e., B = 2 (mod 3)) -1 if 2B+ 1 = 0 (mod 3) (i.e., B = 1 (mod 3)) lor -1 if B = 0 (mod 3) . Also, for every prime p>5, define ap, bp by 6ap + t = 0 (mod p), 0 < ap < p 6bp + 2B + t = 0 (modp), 0 < bp

5, except for p = 6k +1 itself. 2. If k ^ 6P (mod p), Vp prime, 5 < p < \/6A; + 2B +1, thereby indicating 6k+2B+t prime, then it is actually true that k^bp (mod p), Vp prime, p > 5, except for p = 6k + 2B +1 itself. 3. As previously mentioned, the first composite number that is divisible ,by a prime, p, and has no prime factors q < p is p 2 . So all possible 6k + t, 6k + 2B + t that are divisible by p and not divisible by any prime q < p must be greater than or equal to p 2 . This means that cancellation of numbers, k, where k = ap (modp), starts at L^ ipj-Likewise, the cancellation of numbers, k, where k = bp (mod p), starts at [ p ~ 6 ~ J. It is thus ensured that for all remaining numbers, k, both 6k + t^0 (mod p) and 6k + 2B +1 ^ 0 (mod p). Chapter 5. General Prime Pairs (G.P.P.) 51 4. If p < VhT+t (V6k + 2B + t) then k > [^J (L^'f^J), which further justifies the starting points of cancellation for each prime p > 5 when the sieve is performed. 5. When sifting {1, . . . , N}, one has sifting conditions for all primes p < y/6N + 2B + t. There could be some k where 6k+t, 6k+2B+t are both prime and 6k + t < y/6N + 2B +1. If one decided to only use the smaller starting cancellation points, [p ~ J , then for these primes p = 6k +1, one could potentially have ^(6k+t) ~2B~tj < equivalently 6k + t < V6k + 2B +1. This means that these values of k would get cancelled incorrectly. However, when B is small, as in the case for twin primes, one can safely use just the lower of the two starting points, due to Remark 1 and the fact that y/6k + 2B +1 < 6k + t when B is small. For larger B, one can still use just the lower of the two starting points, but some care must be taken to not cancel those values of k where 6k +1 and 6k + 2B +1 are prime, and 6k + t < y/6k + 2B + t. 5.2 Applying Selberg's Method 5.2.1 The Eratosthenes Approach Recall that for the Eratosth'enes approach to sifting twin primes, we applied Selberg's method to the numbers n(n + 2). Similarly, we now apply the method to the numbers n(n + 2B). We define 7T 2B(X) to be the number of n where 1 < n < X, such that both n and n + 2B are prime. Theorem 5.2.1 Let Q.E.D. P(P - 2) (p - l ) 2 p-1 (5.2.1) where the products are over odd primes p. Then Chapter 5. General Prime Pairs (G.P.P.) 52 Proof: Take /(n) = n(n + 2B). Then the function p in this sifting situation is given by >\2B 2B . pip) = f 2 ifp-I 1 ifp 1 Thus p(p) < 2 for all p, so (as in Lemma 2.1) p has sifting density K = 2, and (3.2.38) holds with n{z,w) = 0(1). Then Theorem 3.2.2 gives G(VD) > L ( - J ^ L = - ) [ i + 0 where ADB 2! \V(P(VD))JX ' \" VogD ^ l o g ^ ( l + o ( ^ ) ) , = \n(i-l) n p\B P5*2 p\B p?2 P 1 is an integer constant), along with those where both 6n \u00E2\u0080\u0094 t, 6n + 2B \u00E2\u0080\u0094 t are prime (when applicable), we obtain all the general prime pairs less than or equal to X. Correspondingly with the standard approach, for 1 < ./V < X, if the numbers N = 6n + t are sifted to retain those where both N = 6n+t, N + 2B = 6n+2B+t are prime, along with those where both N = 6n \u00E2\u0080\u0094 t, N + 2B = 6n + 2B \u00E2\u0080\u0094 t are prime (when applicable), we also get all the general prime pairs less than or equal to X. Therefore, in applying the Selberg sieve to the alternate approach, we must sift the numbers (6n + t)(6n + 2B + t), along with the numbers (6n \u00E2\u0080\u0094 t)(6n + 2B \u00E2\u0080\u0094 t) (when applicable), just as the previous theorem sifted the numbers N(N + 2B). This makes sense and agrees with the fact that the Selberg sieve was applied to the numbers (6n \u00E2\u0080\u0094 l)(6n + 1) in the case of the alternate approach for sifting twin primes. We let 7 r 2 B ( X ) denote the number of n with 1 < n < X/6 such that both 6n +1 and 6n + 2J5 +1 are prime, and when applicable, 6n \u00E2\u0080\u0094 t and 6n + 2B \u00E2\u0080\u0094 t are also prime. We observe that Hence we would expect 7 r 2 B ( X ) to have a similar upper bound as IT2B(X) upon applying the Selberg sieve on the numbers (6n. +1)(6n + 2B +1), along with the numbers (6n \u00E2\u0080\u0094 t)(6n + 2B \u00E2\u0080\u0094 t} (when applicable). This is indeed the case as demonstrated by the next theorem, and we can actually achieve Q . E . D . ; - 1 if (3, 3 2B) is a G.P.P. i \" ^ : if (3, .3 + 2B) is not a G.P.P. the same upper bound. Theorem 5.2.2 Let p>2 ( P - I)2 P - 1 P - 2 (5.2.2) Chapter 5. General Prime Pairs (G.P.P.) 54 where the products are over odd primes p. Then Proof: Recall that general prime pairs are of the form (6n + t, 6n + 2B + t) where B > 1 is an integer constant and ( - 1 if B = 1 (mod 3) t = < 1 if B = 2 (mod 3) [ - 1 or 1 if B = 0 (mod 3). Also recall that when 3 | B, we apply Theorem 5.1.1 to each case separately (t = 1 and i = \u00E2\u0080\u0094 1). So in the case when 3 | 5 , it is convenient to think of \u00C2\u00A3 as being fixed (say t = 1) and so general prime pairs in this situation are either of the form (6n +1, 6n + 2B + i) or of the form (6n \u00E2\u0080\u0094 t, 6n + 2B \u00E2\u0080\u0094 \u00C2\u00A3). When 3 \ B, we just said that general prime pairs are of the form (6n + t, 6n + 2B +1) (recall t is.understood to be predetermined). As such, we take / i (n) = (6n + \u00C2\u00A3)(6n + 2B + \u00C2\u00A3), and when applicable (i.e., 3 | B), f2(n) = (6n-t)(6n + 2B-t). Then for each situation, fi and fa (when applicable), the function p is given by { 0 i fp = 2 o r p = 3 1 if p | B a n d p ^ 2 or 3 2 otherwise. Thus p(p) < 2 for all p, so (as in Lemma 2.1) p has sifting density K \u00E2\u0080\u0094 2, and (3.2.38) holds with n(z,w) = 0(1). Then Theorem 3.2.2 gives Chapter 5. General Prime Pairs (G.P.P.) 55 where A' DB n p\B P5^2,3 p\B p^2,3 p\B, p\u00C2\u00A32, 3 pfB, p#2, 3 P n \pjL2, 3 i - i P 3 4 n . P\B W 2 , 3 P(P ~ 2) (P \" I) 2 P(P - 2) (C as in (5.2.2)) 12 n W 2 - 3 p p T T P(P ~ 2) 11 ( p _ l ) 2 . .P |B V ^ 1 W 2 > 3 J (see (2.31) with iw = v^D) + if 3 | B and C f l as in (5.2.2) \u00C2\u00A3 ( 1 + 0 ( T D ) ) if 3 | B and C B as in (5.2.2) 12 I 1 1_ 1 2 C B C Applying Theorems 3.1.1 and 3.2.3, and multiplying by 2 in the case when 3 | B (to combine both situations, / i and / 2 ) , we have in all cases, TT2BPO < S(A,P(VD)) + *(VD) < -A'DBlog2^ + 0(D log 2 \" D) . Our result follows as stated on choosing D =,X / (log X ) 2 K + 3 , where K = 2. Q.E.D. As can be seen by comparing the results of the last two theorems, the alternate approach to sifting the general prime pairs leads to the same upper bound as the standard (Eratosthenes) approach. 5.3 Sum of the Reciprocals As for twin primes, the sum of the reciprocals for general prime pairs is convergent (or possibly finite). The proof of this result is practically identical Chapter 5. General Prime Pairs (G.P.P.) 56 to that of Theorem 4.3.1 but with the obvious differences. Theorem 5.3.1 Let pi, p2, . . . be the sequence of prime numbers p such that p + 2B is also prime. Then V f l + - L _ N ) < M , if \p, Pi + 2B J ~ where M is a constant. Proof: We wish to use partial summation; in particular, Lemma 2.2 which makes use of integration by parts (2.32). Let _ J 1 if n, n + 2B are both prime, n \ 0 otherwise. and f(n) = \u00E2\u0080\u0094 ( / ' is continuous on [2, oo)). n Then let A(x) = \u00C2\u00A3 an = TT2B(X), 2 oo). From this it follows that with Pi Pi + 2B 32CCB < M, Af = log(2) \u00E2\u0080\u00A2 Q.E.D. 58 C h a p t e r 6 C o n c l u d i n g R e m a r k s As we have seen, the methods of Selberg are quite good for providing upper bounds. This is good and leads to results like those of Theorems 4.3.1 and 5.3.1, where the sum of the reciprocals of the twin primes/general prime pairs are convergent (or finite). However, mathematicians would like to find some means of providing effective lower bounds. It is not yet clear if, and how, the methods of Selberg can be manipulated or reformulated in such a way so as to provide good lower bounds. This is an area of active research; [4] addresses/presents some plausible approaches to the problem. The alternate approach we presented for sifting twin primes was quite elegant and easy to perform. The starting points of cancellation coincided and we saw that for every prime p > 5, we had bp = \u00E2\u0080\u0094ap. This meant that the cancellation step for each prime had a symmetrical aspect to it. While things were pleasant for twin primes, they got a bit uglier for more general prime pairs. We generally had two distinct starting cancellation points for each prime p > 5 and we no longer had symmetry in the form bp = \u00E2\u0080\u0094 ap. Also, depending on whether or not 3 | B, we may have had to perform a double application of the sieve. Despite all this, however, the alternate sift-ing approach was effective and easy to perform. It must also be pointed out that the alternate sifting approach could be reformulated and applied toward finding very specific prime pairs. For in-stance, if one were specifically interested in finding prime pairs of the form (Ak + l, Ak + 2B + 1), where A, B, I are fixed constants and g.c.d.(A, I) = 1 and g.c.d:(A, 2B + I) = 1,. the alternate approach could be formulated to do just that. In addition to this, the alternate sifting approach.can also be extended and used for finding prime n-tuples; that is, tuples each consisting of n primes, where it has been pre-determined how the primes are to be sep-arated from each other (twin primes are 2-tuples that are separated by 2). Note also that one could decide to \"shrink\" the method and find 1-tuples; i.e., just find primes of some form Ak + I, where A, I are constants and g.c.d.(A, I) = 1. Chapter 6. Concluding Remarks 59 We saw how the Selberg method was applied to twin primes, and it was mentioned earlier that it is still an open problem as to whether or not the twin primes occur infinitely often throughout the integers. The Twin Prime Conjecture states that they do occur infinitely often, and somewhat associ-ated with this conjecture, is the famous Goldbach Conjecture, which states that every even number greater than 2 can be written as the sum of precisely two primes. Both of these problems have been open for many years, but the techniques of Sieve Theory have come remarkably close to solving them. Things seem to have culminated with the results of J.R. Chen, see [3]. He essentially proved, using similar techniques, the following two theorems. Theorem 6.1 There are infinitely many primes p where p+2 is either prime or is the product of 2 primes. Theorem 6.2 Every sufficiently large even number is either the sum of two primes or is the sum of a prime and a product of 2 primes. One can also see [5, Chapter 11], where the entire chapter is devoted to Chen's theorem(s). It is clear that Sieve Theory is quite powerful and useful, yet seems to be in need of new information in order to crack these age old problems. The Twin Prime Conjecture and Goldbach Conjecture are only two of many problems where sieve techniques can be applied. 60 B i b l i o g r a p h y [1] Apostol, Tom M . Introduction to Analytic Number Theory, Undergrad-uate Texts in Mathematics. Springer, 1976. [2] Brun, Viggo. L a serie 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 + 1/29 + 1/31 + 1/41 + 1/43 + 1/59 + 1/61 + ou les denominateurs sont \"nombres premiers jumeaux\" est convergente ou finie. Bulletin des Sciences Mathematiques, 43, 1919. pgs. 100-104, 124-128. [3] Chen, J . On the representation of a large even integer as the sum of a prime and the product of at most two primes. (Chinese) Kexue Tongbao, 17, 1966. pgs. 385-386. [4] Greaves, George. Sieves in Number Theory, A Series of Modern Surveys in Mathematics, Volume 43. Springer, 2001. [5] Halberstam, H . and Richert, H. -E . Sieve Methods. Academic Press Inc. 1974. pgs. 320-338. [6] Niven, Ivan; Zuckerman, Herbert S. and Montgomery, Hugh L . An Intro-duction to The Theory of Numbers, fifth edition. John Wiley and Sons, Inc. 1991. pgs. 25-28. [7] Rudin, Walter. Principles of Mathematical Analysis, third edition. McGraw-Hil l , Inc. 1976. pgs. 63-64. "@en . "Thesis/Dissertation"@en . "2005-05"@en . "10.14288/1.0080068"@en . "eng"@en . "Mathematics"@en . "Vancouver : University of British Columbia Library"@en . "University of British Columbia"@en . "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."@en . "Graduate"@en . "The Selberg Sieve and prime pairs"@en . "Text"@en . "http://hdl.handle.net/2429/16435"@en .