The Selberg Sieve and Prime Pairs by Martin 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 THE REQUIREMENTS FOR T H E DEGREE OF Master of Science in The Faculty of Graduate Studies Mathematics The University Of British Columbia A p r i l 21, 2005 © 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 sifting 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. iii Contents Abstract ii Contents iii Preface v Acknowledgements vi Dedication vii 1 Introduction 1 2 Sieve Notations and Preliminaries 3 3 The Selberg Sieve 14 3.1 14 14 19 21 21 25 33 3.2 The Set-up 3.1.1 Selberg's M a i n Theorem 3.1.2 Bounding X(d) Estimates for G(x) and E(D, P) 3.2.1 Using Rankin's Device 3.2.2 A n Asymptotic Bound 3.2.3 The Error Term , 4 Twin Primes 4.1 Sifting for T w i n Primes 4.1.1 A n example of the Sieve of Eratosthenes 4.1.2 A n Alternate Sieve for T w i n Primes 4.1.3 Proving the Alternate Sieve works 4.2 Applying Selberg's Results to T w i n Primes 4.2.1 The Eratosthenes Approach 4.2.2 The Alternate Approach 34 34 34 35 36 38 38 39 Contents 4.3 S u m o f the Reciprocals, of T w i n Primes . . . . . iv . . . . . . . . 41 5 General Prime Pairs (G.P.P.) 5.1 Sifting General Prime Pairs 5.1.1 A n example of the Sieve of Eratosthenes'. . . . . . . . . . 5.1.2 The Alternate Sieve for General Prime Pairs 5.1.3 Proving the General Alternate Sieve works 5.2 Applying Selberg's Method 5.2.1 The Eratosthenes Approach 5.2.2 The Alternate Approach 5.3 Sum of the Reciprocals . . . 45 45 45 46 48 51 51 53 55 6 Concluding Remarks 58 Bibliography 60 Preface I was in my senior year of high school when I first learned about twin primes and the famous T w i n Prime Conjecture. Though I found the problem fascinating 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 Martin 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. Vll To M y Parents This accomplishment was made possible by the sacrifices and hard work of my parents, Martin and Shira Duarte. I thank you both for your ever continuing love and support. i Chapter 1 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 numbers/objects is yielded from a larger set of numbers/objects. Eratosthenes, a mathematician of ancient Greece, is the first known person to have constructed a mathematical sieve (third century, B . C . ) . He started with a list of odd numbers and then proceeded to cancel 3 and every third number thereafter, then cancel 5 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. 2 2 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 problems where sieves provide useful information. One such problem is the so called "Twin Prime Problem". A T w i n 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: upper 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 will 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, £ ^ p<X g i II f 1 _ ,og = l o g d o ^ + C+ O O T + 0 (l) (2.1) p ~ ~) = e 7 l 0 S ( ) + CK ) ( 7 1 z i s ^ ) ; (2.2) Euler's constant) (2.3) (2.3) is known as Mertens' product. The Mobius function, /z, is important to Sieve Theory; we recall its definition: Mi) = i A*(PiP2 • • • Pr) y,(d) = (—l) if P i , •••) Pr are distinct primes — 0 if p | d for some prime p, - r 2 i.e., \x is the multiplicative function defined at prime powers, p , by a Hip) = - 1 , »(p ) = 0 if a > 2 . a 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 i n A that are divisible by d. P will denote a product of distinct primes, not necessarily containing all the primes up to some specified bound. However, in many cases, p<z P will usually be the product of primes we are sifting (cancelling) by. In connection with P, we denote P{z) = Hp . (2.6) p\p p<z In situations where no product P is implied or specified, we simply take P(z) to be P(z) = ]Jp . (2.7) p<z (a, b) will denote the g.c.d. of a and b. I Definition 2.1 We define S(X) = z^d|x/ ( ^)- Also, abbreviate S((a, P)) to S(a, P), so we have i S(a, P) = £ d\(a, P) , M - { c 1 (2.8) The second equality followed from identity (2.4). It is important to observe that the condition (a, P) = 1 says that a is not divisible by any "sifting" prime factor of P. Definition 2.2 With S(a, P) as in identity (2.8), we define S{A,P) = Y,S{a,P). (2.9) Chapter 2. Sieve Notations and Preliminaries 5 This says that S(A, P) is the number of a in A that are not divisible by any primes in the product P. Putting definitions (2.1) and (2.2) together, we get S(A, P) = £ £ / i ( d ) = £ / * ( < 0 I M a&A d\a d\P (2-10) d\P which is known as "Legendre's Identity". The second equality followed by switching the order of summation. It will be seen later that with the Selberg Sieve, identity (2.8) is replaced with an inequality where p is replaced by another function, A, where in some sense, it is easier to work with A. Also, suitable estimates for |^4^1 are needed in order to attain a good calculation of Legendre's Identity. W i t h the notations we have so far, conducting a sieve for twin primes can be thought of as a sieve on a set of numbers given by the polynomial expression: f(n) = n(n + 2). Likewise, for a more general prime pair, we would have /(re) =re(n+ 2B). More generally, we take A = {/(n) : Y - X <re< Y], where f(n) is a polynomial over the integers (for twin primes, /(re) = n(n+2), and for general prime pairs, / ( n ) = n(re + 25)). Also, P is as i n identity (2.5). To estimate |Ad|, we consider each residue class, mod d, separately. We get w= £ £ i-Eff+ow)- l<l<d Y-X<n<X f(l)=0 (mod d) n=l (mod d) I ^ <»•»> ' The inner sum over re was estimated by expressing re as I + dm, so m is confined to an interval of length X/d. Letting p(d) represent the number of roots of the congruence /(/) = 0 (mod d), we then get \A \=X^ d + 0{p{d)). (2.12) Chapter 2. Sieve Notations and Preliminaries 6 Using this in Legendre's Identity (2.10), we get S(A,P) = 5>(d)|Ai| d\P - * n ( i - ^ ) + ° f e * < > y V P<2 F \d\P / <"3) 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) — 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 \A \ = X ^ d a + r {d) A if d\P, d<D. (2.14) Identity (2.14) will be applicable with p a multiplicative function and D to be specified. Apparently, in many sieve problems, including the applications to twin primes and general prime pairs, \r (d)\ < p(d). A (2.15) Chapter 2. Sieve Notations and Preliminaries 7 Now recall we mentioned fi will be replaced by a different function A. In fact, functions A£, A ^ are constructed/chosen so that £ < £ / x ( d ) < £ A + ( d ) when B \ P. d\B d\B (2.16) d\B The idea is to pick A J , A# i n a way that the inequalities are effective i n a given sifting situation for relatively large products P. Also, D will have the property \±(d) ^ 0 => 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 = d\p V + (i_<*e>). \p ^ y P (2.i8) ' 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: Ew«»E^^n('-f)"'=^ d\p d<D d\p d<D p\p v F J («») ' v Using all the information so far, we now get the essential Meta-theorem of Sieve Theory: Theorern 2.1 When A satisfies identity (2.14) and X satisfies inequality ± (2.16) we obtainXV-(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 ± [ D j p ) = £ m ? m , d\P R ± { D , P ) = £ \%(d)r (d). d\P A (2.21) - Chapter 2. Sieve Notations and Preliminaries 8 Proof: Taking B = (a, P) i n inequality (2.16) and summing over a G A as i n Legendre's Identity (2.10), we get Y,W)\M d\P < s(A, p) < ] T A M • d\P Making use of Identity (2.14) we now have d\p A5(d) (x4& ^ + r (d)) < S(A, P ) < £ AS(«0 (X4& ' d\p ^ " A + r (d)) , / A 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 are relatively small in comparison to XV^, and much work is done in estimating V and R . 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 4 ± ± |A£(d)|<l for all d. (2.22) As a result of this, we have the following <EMrf)l ^2\i(d)r (d) d\P A d\P d<D from which we get a Corollary of Theorem 2.1: Corollary 2.1.1 Suppose identity (2.14) and inequalities (2.16) and (2.22) hold. Then xv-(D, P)-J2 d\P d<D ^ S(A, ) ^ xv (D, p + P) + J2 M < * ) l d\P d<D • Sifting Density: We mentioned earlier that the function p has a sifting density K if a certain Chapter 2. Sieve Notations and Preliminaries 9 average of p(p) at primes p is not greater than K. In many situations, the following is true: E £(p)log(p) = K l o g ( 2 ) + 0 ( 1 ) ( 2 2 3 ) P p<z When dealing with twin primes, for instance, we had p(p) — 2 for primes 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 i n some sense. Such complications are avoided, therefore, by using alternate formulations 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 formulations will 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<w<z, with K <1 W + -4-r- (2-25) In some cases a bit less is used: There exists a constant K > 1 such that K <K W when w>2. (2.26) Note: The choice w = p, z = p + e shows that inequality (2.24) gives ! _ PMy\.< '•/, Kp} V(2-.27) so p(p) is bounded away from p: p(p) < p(l — \/K ). Also, notice that « 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). p 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 _ 4_u^4y « 1 V{P{z)) - \ r \og(w)J \\og(w)J 2 < w < z ~ . • (. ) 2 28 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: • (2.29) P - p[p) Using this definition, we can replace inequality (2.24) by specifying the existence of a constant A > 1 such that ^2 g(p) log(p) < /dog (—) + A when 2<w <z. (2.30) w<p<z Note: As stated by Lemma 2.4 to follow, inequality (2.30) implies the usual sifting density hypothesis/definition (2.24). Many sifting situations, including that of twin primes and general prime pairs, satisfy both inequalities (2.24) and (2.30). In particular, the next lemma applies to the twin prime and general prime pair scenarios. Lemma 2.1 Suppose p{p) < p when p < K and p(p) < K for all p. Then p has sifting density K, in the stronger sense expressed by inequality (2.25), and also satisfies inequality (2.30). Proof: The inequality p(p) < p guarantees p(p) < p(l — 1/K) when p < K, for a certain K > 1 depending only on n, so that (1 — < 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<p<z p J x - \log(w)J A Vog(w)JJ JU, (\ _ s) • The last product over primes p is exp V.Si "V > v - \ VI) ~\ £ c \f = - (o(i P - 1 0 + (I), (2.31) 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 i n inequality (2.24) is bounded. In a similar way observe when w > K v-p^ ~Jk<* 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 Stieltjes integrals is convenient. Using integration by parts, one can take as a definition: f JW f(t)d(c(t)) = c(z)f(z)-c(w)f(w)- f f'(t)c(t)dt (2.32) JW when / ' is piecewise continuous on [w, z] and c is of bounded variation. Chapter 2. Sieve Notations and Preliminaries 12 Lemma 2.2 Define ( > y)= Y c x 0/1 x<n<y whenever the indicated numbers Cn are defined. (i) If w < z and f is piecewise continuous on [w, z], then J2 °"K ) = [ f(t)d(C(w, n t)) = - ['f(t)d(C(t, Z w<n<z Jw z)), (2.33) Jw where the integrals with respect to t are given by identity (2.32). (ii) Suppose, in addition, that f is positive and monotone in [w, z] and that C(x, y) is given by an expression C(x, y) = -y(y) - f(x) + e(x, y), where e(x, y) < E whenever w < x < y < z. Then °nf( ) n ^ f f(t)d(j(t)) + EmBx{f(w), Z f(z)}. (iii) If f and g both satisfy the conditions required of f in parts (i) and (ii) then J2 c f(n)g(n) < f f(t)g(t)d( (t)) + E ( max f(u)) ( max g(v)) . n 7 Lemma 2.3 Suppose that, when t and n are in an interval [x, y), f'(t) is continuous and f(t) is positive and decreasing, g(n) > 0, and E(t, n) < A. Then f. Jx<t<y /(*) d(J2 9in)E{t, n) ) < A Y, \ <n<t ) x f(n)g(n). x<n<y Lemma 2.4 Suppose p is such that the function g satisfies (2.30). Then the sifting density hypothesis follows in the form (2.25), with K < ^ e I o g W = 1+ L log(iu) Chapter 2. Sieve Notations and Preliminaries 13 Lemma 2.5 Suppose that p has sifting density K, and that 2 < w < z. (i) When inequality (2.26) holds we find £ —' z Pip) log(p) ^ ^ < ( p W<p<Z « + log(X))log(z). (2.34) (ii) If inequality (2.25) holds then W<p<Z Furthermore the function g(p) defined in identity (2.29) satisfies £ £ ( g(p)\og(p) < « l o g ( ^ ) + L ( l + « ) l o g ( e w<p<z ^ I? \og{w)' 2 ' 3 7 ) log(*) s>\ J (2.38) 14 Chapter 3 The Selberg Sieve 3.1 3.1.1 The Set-up 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 i n 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 i n 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 consequences 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 i n 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: \A \=X^d a + r (d)iid\P, A d<D (3.1.1) where \Aa\ is the number of a in A divisible by a squarefree number d, and p is multiplicative. The symbol [di, c^] denotes a least common multiple. The function p* will be the multiplicative function "conjugate" to p i n that its values at primes p are given as ... p* =p-p(p). (3.1.2) Chapter 3. The Selberg Sieve 15 This defines p*(d) for squarefree d, the only d that will be relevant. Then the function from identity (2.29) is a ( n y K \ I p( )/P*( ) n = ' \ n i f 0 n is squarefree , otherwise. \ • • > In Theorem 3.1.1 and elsewhere we shall denote = X>(n), G(z) (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 i n Lemma 3.1.1 are finite. The restriction to p(h) ^ 0 i n identity (3.1.6) is a natural one, because for other h the summand x (h)/g(h) is a multiple of p(h) as follows: identity (3.1.7) gives p(h) \ x(h), so that x (h) = p (h) • I, for some I. Now 2 2 2 x (h) _ (x (h)p*(h)) 2 2 9(h) (p (h).l-p*(h)) 2 pih) p(h) so after cancellation of p(h) from the numerator and denominator, the summand is a multiple of p(h). Lemma 3.1.1 Define v (\)=YE 7 T p + d \Pd \P x • ( - ) 3 l5 * 2 2 Then h<VB y v ' where g is as in identity (3.1.3) and x ( h ) = E ( 3 1 7 ) d=0 (mod h) Moreover = 5 > * W H ) : (3 1.8) : Chapter 3. The Selberg Sieve 16 Proof: Using [di, ofo] = d\d /(d\, d ) i n equation (3.1.5) gives 2 2 S^S^ K i)p(di) K 2)p(d ) (di, d ) d V (\)= + d 2 2 p((di,d ))#0 2 Since f = (d\, d ) is squarefree, the last fraction may be expressed as 2 / We therefore have, v+t\\- \ ^ V ^ A(c? )p(ti ) ^ 1 - 2^2^ 5; ^ 2_. zThy di d h\{d d ) ' p((di, d ))#0 Rearranging the order of summation gives ( A 2 2 ) 1 2 y K 2 u 2 2 V W ~ 2^-g-{K) 1 , J, di=0 (mod h) h<s/D ^ d 2 d =0 (mod h) 2 X (h) 2 h<VD W which is identity (3.1.6), where x(h) is as i n identity (3.1.7). Lastly, identity (3.1.7) inverts to give mN=d k\m KN)p(N) N ' which is identity (3.1.8). Here we used the characteristic property (2.4) of the Mobius function. Q.E.D. Chapter 3. The Selberg Sieve Theorem 3.1.1 17 Suppose identity (3.1.1) holds. Then S(A, P)<-jX-. + {D, E P), (3.1.9) where G is as in identity (3.1.4), E(D, ) = jm) E E WM<k)rA([di, d <VDd <VD di\P MP p 1 d \), 2 (3.1.10) 2 and the real numbers X(d) are given, for some C ^ 0, by ^M = Cp(d) Yl 9(h) h=0 (mod d) h<VD, h\P ifp(d)^0, (3.1.11) with \{d) = 0 if p{d) = 0. Some Notes: Taking d = 1 in equation (3.1.11) shows C = ^ L . (3.1.12) The usual normalization i n Theorem 3.1.1 is to make A ( l ) = 1. The value of X(d) when p(d) = 0 is irrelevant to the coefficient of X i n Theorem 3.1.1. The choice X(d) = 0 for these d is the most efficient one when the error term E(D, P) is considered. Since g is as i n identity (3.1.3), substituting h — dk i n equation (3.1.11) gives X(d) = Cp(d)-£p £ g(k). ^ ' (fc,d)=i k<s/D/d, k\P (3.1.13) Proof: Suppose, for the moment, that X(d) are arbitrary real numbers supported on squarefree d < \fD. We start with Selberg's brilliant idea A ( l ) S ( a , P)< 2 ( £ X(d)\ Vd\(a, P) ) . (3.1.14) Chapter 3. The Selberg Sieve 18 This holds because if (a, P) = 1, then S(a, P) — 1 and both sides of inequality (3.1.14) take the value A ( l ) , but if (o, P) > 1, then S(a, P) = 0 and the right side is non-negative. The right side of inequality (3.1.14) can be written 2 E E ¥)AW = E E ^ ) W E - a di\(a, P) d \(a, P) di\Pd \P 2 2 1 [d u d ]\a 2 On summing over a G A and expressing the result in terms of p from identity (3.1.1), this gives \ (1)S(A, P) < XV {\) 2 + + \ (1)E(D, 2 P), (3.1.15) with V (\) as i n 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 convention 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 will 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, p (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 + + + 2 + E t*(k)x(k) = A(l) (3.1.16) k<VD is now required by identity (3.1.8). We will use Cauchy's inequality (E ^) ^E 'E ^ A \h<H A / h<H 6 h<H which holds with equality when there is a constant C with h < H. This is an immediate consequence of the identity E l E l - (E a b h<H k<H AHBH \h<H ) = J \( E AHBK \h<H, k<H = Cbh whenever \ ' - ) • AKBH J Chapter 3. The Selberg Sieve 19 Apply Cauchy's inequality to the condition (3.1.16) in a way that relates to identity (3.1.6) for V+(\): * E § \fc<>/5 y K E *(*)) ' J \k<VD * ^(A)G(V5), (3.1.17) ) where G(\fD) is as stated in identity (3.1.4). Equality occurs in (3.1.17) if x(k) = Cp(k)g(k) when k < y/D, (3.1.18) in which case inequality (3.1.15) gives the conclusion (3.1.9) required in Theorem 3.1.1. This situation is attained if we make A(d) satisfy equation (3.1.8) with these x(k), so that X(d)p(d) = C £ p(k)p(kd)g(kd) = Cp(d) k<VD/d J2 h=0 (mod h<VD 9(h). d) This is the value stated i n equation (3.1.11), in which the implied constraint h | P was written explicitly. Q.E.D. 3.1.2 Bounding X(d) The following theorem states that [X(d)\ < |A(1)|. Keep in mind that the usual normalization in Theorem 3.1.1 is to make A(l) = 1, so Theorem 3.1.2 provides a nice, convenient upper bound on X(d). For given d, a squarefree number h may be written uniquely as h = fn, where / | d and (n, d) = 1. Hence E h<VD 9(h) <J2 f\d 9(f) E d)=l n<y/D (n, 9(n). (3.1.19) Chapter 3. The Selberg Sieve 20 Observe from identity (3.1.2) that for squarefree d the sum over / in (3.1.19) is As before, the fact that / , n and h divide P may be taken as implicit in the definition of the function p. Theorem 3.1.2 inequality The numbers \(d) described in Theorem 3.1.1 satisfy the \X(d)\ < |A(1)|. Proof: Let C be the normalizing constant as i n identity (3.1.12), so that A(l) = C £ g(h). h<VB This leads to the following inequality which is in the opposite sense/direction to inequality (3.1.19): |A(1)|>|C|£ (/) g(n). £ 5 f\d (n, (3.1.21) d)=l n<VT>/d W i t h the identity (3.1.20) this gives i— |A(1)|>|C|^ £ (n, 9(n) = \X(d)\, d)=l n<s/D/d by the expression (3.1.13) for \(d). Q.E.D. Corollary 3.1.2.1 In Theorem 3.1.1, the error term satisfies E(D, P)< £ di<VD di\P ^ - M ^ x , d })\. 2 d <y/~D d \P 2 2 Proof: The result immediately follows from identity (3.1.10) for E(D, P) and the previous theorem. Q.E.D. Chapter 3. The Selberg Sieve 3.2 21 Estimates for G(x) and E(D, P) We would now like to get some estimates for G(x) and E(D, P). We address each of these in turn. 3.2.1 Using Rankin's Device To get estimates for G(x), we will define a useful, related expression, G (x). Then the next theorem will provide upper and lower bounds for G (\/D), where the only assumptions about p used are: z z (1) 0<p(p)<p -L-\2 (2) ^ P { P ) l ' p<z ° g i P < ) (by Lemma 2.5), B (3.2.22) P where B is a constant. The proof of the theorem relies on the next lemma, which provides an upper bound for I (x) = G (oo) — G (x). The proof of the lemma uses a technique known as Rankin's device; it will be pointed out. In connection with G(x), we have the "incomplete" sum z z G (x) = z g(d). z (3.2.23) d<x d\P(z) This is considered "incomplete" because the sum is over all d dividing P(z) (not P) whereas the sum for G(x) is over all d dividing P. (Recall: P(z) = n | p , p < P )• For future reference recall that the equation g(p) — p(p)/(p — p(p)) introduced earlier can be rewritten as p 2 1- ) 9 ( P ) = M , 1+ 9 ( P ) = (j - < M ) "'. Observe that G (x) increases with z, so \. z " ' •• G(x) - G (x) > G (x) x z (3.2.24) •• •. (3.2.25) when z < x. In Theorem 3.1.1, a lower bound for G(x) is required (with x — \fD), so a lower bound for G (x) is relevant.. It is natural to denote z G,(oo) = £ 9{d), d\P(z) Chapter 3. The Selberg Sieve so that G (x) = Gz(oo) whenever x > P(z). identities i n (3.2.24) where necessary, Observe, referring to the z <?,(*) < G , o o ) = n ( (i+ (p))=• n 9 p\P{z) p\P(z) f 1 22 f) =™W pj - V y / V V 1 >> (3.2.26) We see here a connection between G (x) coming from Selberg's method and the product V(P), but the inequality is i n the wrong direction. The next theorem will give us what we seek, but first the lemma. z Lemma 3.2.1 Suppose that the assumptions (3.2.22) about p hold, and denote I (x) = G (oo) - G (x) = £ g(d), (3.2.27) z z z d>x d\P{z) and write x — z . Then for each c > 0 v Iz(x) < ^ ^ e x p ( - c t ; + B ( e - 1)). c (3.2.28) In particular where, for each v > 0, ip (v) = max JO, v log B - v+ = J log (Jj^j dt. Proof: We use Rankin's device. Letting e > 0, we observe that when d > x, we have (d/x) > l = 1, so we get € e Chapter 3. The Selberg Sieve J2 9(d) < £ /,(*) = d>x d\P(z) g(d) (±Y d>x d\P{z) * E ^ ' +!>«(£) d>x d|P(*) v d<x d|P(^) 7 E 9(d) (I)'= = 23 d\P{z) v v 7 ±; T, 9(d)d< ' d\P(z) = Xh II( P ^))1+ (-- ) £ 3 2 30 p\P{z) Hence, by the definitions of V(P(z)) and g(p): '• ™4n(^)(. ^) w + the last inequality following from the fact 1 + x < e . We may choose e = c/log(z), provided c > 0. Then z — e . Observing that (e* — \)/t increases when t > 0, we have when p.< z, x e p e — I e elog(p) clog(p)/16g(z)-J_ j g'c _ clog(p)/log(z) ~ c ]_ - • c It follows that f - 1< —(6log(p)) = ^ c c • - 4 - • log(p) = (e log(z) c log(z) and when x = z , x = (z ) = (z ) — (e ) — e . Using these facts along with the assumptions (3.2.22) about p, and the fact that summing over p < z v t v £ e v c v 00 Chapter 3. The Selberg Sieve 24 is greater or equal than summing over p | P(z), we now have I (x)V(P(z)) < lexpf z £ ^ f y - l ) | \m>) < < J v e u exp (-cv + B ( e - 1)), c as required for inequality (3.2.28). The optimal choice of c satisfies v = Be , i.e. c = log(f) — 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. c Theorem 3.2.1 Suppose that the assumptions (3.2.22) about p hold, where z>2, and write z = D . Then G (VD), as defined by (3.2.23), satisfies 1/S Z nPjz)) - G z { V D ) - nPjzTy ( 3 - 2 3 1 ) where ipB is as in the last lemma. In particular, Q ) ~ ^ exp^-VteQs^ < e ~ for all s > 0. ^ b s s i 7B °s( ) s a s s -> °°. a Proof: The second inequality i n (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~\ -> ~ e x p ( - ^ ( t ; ) ) G (x) = G (oo) - I (x) > V{P(z)) ' 1 B z 2 z Chapter 25 3. The Selberg Sieve and taking x = VD, so that the notations z = x and z = D ^ require v = | s . We get exp(V>B(|s)) < e ~ by taking the choice c = 2 in the last lemma and noting that e — 1 < 7. v 7B 1 s 2 Q.E.D. 3.2.2 A n Asymptotic Bound Though the last theorem provided a lower bound for G (\/~D), it is not the sharpest result. It turns out that in many applications of Theorem one wishes to estimate G (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 3.1.1, Z z ]TS(P) log(p) = (3.2.32) K\og(v) + n(t/) p<v where ri(t) is required to be bounded above. This is actually a little stronger than what is given by Lemma 2.5. It is possible to proceed just based on Lemma but using makes things a bit easier. For the sifting situations we're interested in, n(t) will indeed be bounded above, allowing us to make use of Theorem The proof of the theorem also relies on the next lemma, which gives an integral equation for G (x). To facilitate the lemma we write („\ - J 9(n) if n \ P(z) ~ \ 0 otherwise, 2.5 (3.2.32) 3.2.2. z a 9 z 1 so the expression j (3.2.23) becomes G (x)= z n<x n<x n\P(z) Lemma 3.2.2 When.z < x the expression G (x) z f x G (x) log(x) = / z dt G (t)+ Jl where S (x) z is expressible as 6 (x) = Y,9z(n)E , (^ z z n n<x (3.2.33) 9(n)=52g (n). z z t r dt G (t)+ S (x), x K given in (3.2:33) satisfies / z (3.2.34) x Jx/z t , with E (t)< (mm(t, z<n v z)) (3.2.35) Chapter 3. The Selberg Sieve 26 Proof: Since m is squarefree when g (m) ^ O w e have z J^&(m)log(m) = YJ2g (np)\og(p) z n p np<x J29z(n) E ri<a: 3(p)log(p) p<x/n p<z ~ E ^ n ) E n<x 3(p)log(p), p<x/n, p<z p\n where the second equality follows from g being multiplicative and m being squarefree. Write n = pk i n the last sum. This gives E 9z{m) log(m) = ]T&(n) £ m<x n<i tf(p)log(p) p<x/n p<z P<2, pffe E*(n)F,, ( £ ) , B where the use of equation (3.2.32) shows zM F = E^ ) p l o g ( ) p P<V P < < E _ 5 (p)log(p) 2 P<y/V, P<2 (P,n)=l Z E ^ p<y p<z 9 l o g ^ KlogCmiaCy. = Hence -2)) + ^(min(y, z)). _ E 9z(n) log(n) = K E 2*( ) n<x n<x n = « E 5 » l o g ( ^ ) n<a; l o S( m -« E n<x/z' i n ' (~> ) ) + » ( ) z s ^ W ^ g f ^ ) x +*z(x), (3.2.36) Chapter 3. The Selberg Sieve where, setting E (y) Ztn U ) = F (y) - relog(y), we have z>n = Ygz(.n)E x 27 E {t) < ?7(min(i, z)), with Ztn (3.2.37) Ztn n<x the desired expression for S . The last equality of (3.2.36) is best seen by looking at the two cases: when x/n < z, x/z < n making the second sum equal to zero, and when z < x/n, the difference agrees with the expression after the first equality i n (3.2.36). Next, note the following, valid for x > 1, z m<x m<x J m J i m<t Using this and the definition of G (x), we can rearrange and rewrite (3.2.36) to get z f dt r G (x) log(x) - (« + 1) J G (t)j + KJ^ x x/z z z dt G (t)j = 6 (x). z z This is equivalent to equation (3.2.34), so the proof is complete. Q.E.D. Theorem 3.2.2 Let G(z) = G (z) and n(t) be as specified in (3.2.25), (3.2.23), and (3.2.32). Assume z n{t) < A when 2 < t < z where A > 1. Then • G '^r . ( . ' TO( 1 + (3.2.38) + °(i4))' (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« V (P( )) X • ^ ( -X° ( ^ ) ) n, ( - J ) ' 0 - f r p < x (3.2.40) 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 will be seen in the following proof. Proof: This theorem refers to G (x) only in the case z = x, and Lemma 3.2.2 gives z dt f x G{x) log(x) = (K + 1) J G(t)j + 6(x), (3.2.41) where *(*) = 5 > ( n ) i ^ (£) . (3.2.42) n<x The primes p exceeding z are irrelevant to the theorem since all functions involving primes are only concerned with primes less than or equal to z. Therefore for present purposes, re-define p(p) for p > z by specifying 1 - M p = ( 1 V . I Y P) if > p z . (3.2.43) This will make questions relating to the convergence (as x —> oo) of the product i n 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 l-p(p)/p (P(P)/P) + l-p(p)/p 1 = 1 _ - (1 - P(P)/P) + l-p(p)/p 1 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 inequality 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 (i)' (3.2.46) K 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) dt Differentiation gives dS(t) = (d(G(t)) log(t) + G ( t ) y ) - (« + = d(G(t))log(t) - K^-dt t , thereby giving ^77T = (<*«?(*)) log(t) log (£) log" (i) K+1 A ). +1 (3.2.47) Now we also compute the following ® ^ log (*) G K = d(G(t))log-"(t) + d(g(t)) bg(t) log K+1 G(t){-K\og- -\t))ldt K 1 G(t) Iog" (<) « +1 (i) = ^^(d(G(t))log(t)-«^ift). (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 E (t/n) < "because of identity (3.2.35) and inequality (3.2.45), so Lemma 2.3 applies, to give n H{y)-H(x)<A 1 £ x<n<y (3.2.50) 6 \ J • Chapter 3. The Selberg Sieve 30 The sum in (3.2.50) can be expressed i n terms of the function H by a "condensation" procedure. Choose c > 1. When U > 2 we find 1 1 G(U ) ~ log(C7) log«([/) g(n) uhu>^ (n) C v +1 log([/) ^ j - The last equality follows from (3.2.49) and basic rules of logarithms. So we now have n<y Using this in (3.2.50) gives H(y) - H(x) < sup log(x) < x ff(*), (3.2.51) t < y with A2 = CJ4I. Here we have C = C K Y - . c r>0 Now choosing C = 1 + 1/(K + 1) ensures | l / c | < 1 so that we get H u — ~ ° r V r* K ' r>0 - =c C - K ~~ - v K + 1 (i/ )~c-r c Finally, using the fact that ( l + ( l / n ) ) < e for all n > 0, (see [7, pgs. 63-64]), we have n c - i i / ( « + i) V K + iy Now let 0 < e < ^, and let J — l i m s u p ^ ^ , H(t). otherwise there would exist a sequence y such that Then J is finite, for n H(y ) -»• 00 as n —>• 00, n # ( y ) > (1 - e) sup H(t), n t<y n and combining with inequality (3.2.51) then gives 1 — e < A2/log(x), which is false for large x. Chapter 3. The Selberg Sieve 31 If x is sufficiently large, then sup < H(t) < J + e. We can choose y > x so that H(y) > J - e. We manipulate inequality (3.2.51) and use these inequalities to get x H(x) > H(y) - t sup Hit) log(--c) x<t<y > H(y)--^-AJ \og{x) = J | 1 + e) Ai Ai log(x) log(x) _ l4o g ( xV) / - . fVi R T ^ !og(x) 2 + y Now take 0 < e < J / l o g ( x ) , so that with identity (3.2.49) we have ° { X ) log"(x) + o(-^-)), =H(x)>j(l ~\log(x) - ^ (3.2.52) 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/t , when s > 0 we have a w = E^-/><*» Now G ( l — e) = 0 for every e > 0 and l i m ^ o o G(t)/t — 0 so we just get s 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 / / = s oo G(t)d(t-) oo (J + o(l))log (t)d(r ) K poo (J + Jo o(l))u e- du K JT(K + 1) ~ — i s K s su . s^0 , '- as + where the quantities o(l) are as t —• oo and u —+ oo. The last approximation above follows from the definition of the Gamma function: x - e- dx r x , x with the substitutions r = K + 1 and x — su (so dx — s du). We now recall some facts about the Riemann £ function: (2) £(s + 1) has a simple pole at s — 0, and ((s + l ) s —• 1 as s —> 0. Using these facts along with the inequality we have for Z (s), we get the following: g limsu PIT ( 1 - - = r V ( 1 + —) = 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 ) when s > 0, so the sum converges uniformly to a sum continuous i n s > 0. That is, the product in (3.2.53) is continuous i n s > 0. It is now easy to infer 2 -< >,nHH-f) -l K+1 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)), i n Theorem 3.1.1. Theorem 3.2.3 Suppose that equation (3.1.1) holds with \r (d)\ < p(d), A pip) > 1 when p \ P , (3.2.54) and that p has sifting density K. Then E(D, P{z)) « £ > l o g ( z ) . 2 K Proof: Corollary 3.1.2.1 and (3.2.54) give d <VDd <VD l \d<VD,d\P 2 d \P di\P 2 Then d<VD d\P{z) p<z d\P(z) Here K ( P ( z ) ) result follows. _ 1 <S K\og (z) K because p has sifting density K, so the final Q.E.D. 34 Chapter 4 Twin Primes Recall that a twin prime is a pair of prime numbers that differ by 2. They can be represented as (p, p + 2), where both p and p + 2 are prime. We will now take a look at two methods for finding twin primes and then explore how Selberg's results apply to these methods. 4.1 Sifting for Twin Primes As mentioned in the introduction, 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. There also exists a different sifting approach that yields all twin primes except (3, 5). We provide examples of both approaches and also prove that the alternate sifting method works. 4.1.1 A n example of the Sieve of Eratosthenes For N — 36, we cancel all proper multiples of primes less that 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 (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) are twin primes. Note: In the following display of numbers and in those to follow throughout the paper, there is no special significance to the direction of the strokes. What is of some importance is that some numbers are cancelled more than once. 1 •2 • ; • • 7 13 19 25 31 $• 3 ? ^ n 5 i i ^ ty 17 2"jf 2i 1% 23 -2v 2V 2^ 29 3? 3^ 3^ 36 # n ty U ffl 3? Chapter 4. Twin Primes 4.1.2 35 A n Alternate Sieve for Twin Primes It turns out that one can obtain the twin primes (except (3, 5)) without the other primes by using a slightly different sifting approach to that of Eratosthenes. This new sieve actually yields twin primes in an indirect way in that it gives the numbers k, where both 6k — 1 and 6k + 1 are prime; i.e. a twin prime. The sieve also makes use of the observation that i£ 6A; — 1 (or 6k + 1) is not prime, then it has a prime factor less than or equal to y/6k — 1 (or VOk + 1).' We start with all the integers from 1 to N. Since N is the largest possible "k", the largest possible twin prime is (6N — 1, 6N + 1). As such, we need only worry about prime factors less than or equal to y/6N + 1, except for 2 and 3 since 2, 3 \ 6k — 1, 6k + 1 for any k. For each prime p, where 5 < p < \/6N + 1, we define a , b by p p 6a —1 = 0 (mod p), 0 < a < p p p 6b +l = 0 (mod p), p 0<b <p. p We observe that b = — a (modp). Then starting with -g-^, we cancel all numbers that are ± a (mod p). A l l remaining numbers, k, yield a twin prime: (6k — 1, 6k + 1). Also observe that the process only makes sense for N > 4. For N — 1, 2, 3, there is nothing to do since each of 1, 2, 3 yields a twin prime. 2 p p p 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, a — 1, and cancellation starts with ^ j p = 4. p For 7, a — 1, and cancellation starts with ^ p . = ' 8 . p For 11, a = 2, and cancellation starts with 1 1 For 13, a = 2, and cancellation starts with 1 3 For 17, a = 3, and cancellation starts with 1 7 p p p - 1 6 = 20. g - 1 = 28. g - 1 = 48. We therefore cancel everything starting with 4 that is ± 1 (mod 5), then cancel everything starting with 8 that is ± 1 (mod 7), then cancel everything starting with 20 that is ± 2 (mod 11), then cancel everything starting with Chapter 4. Twin Primes 36 28 that is ± 2 (mod 13), and finally, cancel everything starting with 48 that is ± 3 (mod 17). We observe that some numbers are cancelled more than once. 1 n n 2 3 i 5 0 12 n 1N5 22 23 H 25 26 32 33 u 3v n 4? 43 44 45 0 7 9 10 17 18 n 27 2$ n 30 37 38 30 40 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 Sieve 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 — 1 or 6m + 1, we see that all twin primes, except (3, 5), are of the form (6k — 1, 6A; + 1). Therefore, this sieve gives us all twin primes, except (3, 5). Theorem 4.1.1 For every prime p > 5, define a , b by p 6a — 1 = 0 (mod p), 0 < a < p p 6b + 1 p p p - 0 (mod p), 0 < b < p . p Let K = {k\ k 6 N and k ^ a (mod p), Vp prime, 5 < p < V6k — 1 p (when this makes sense)} P| {k\ k € N and k ^b p (mod p), Vp prime, 5 < p < V6k + 1 (when this makes sense)} Then k G K if and only if 6k — 1, 6k + 1 are both prime. 1, 6k + 1) is a twin prime. That is, (6k — Proof: "<S=" (Contrapositive) Suppose k $.K. Then either 5 < p < V6k - 1 < 6k - 1 k = a (mod p), for some prime p, or k = b (mod p), for some prime p, 5 < p < V6k +. 1 < 6k + 1 p p Chapter 4. Twin Primes 37 Therefore either 6/c-l 6k + 1 = = So one of 6k — 1, 6A; + prime. 1 or 6a — 1 = 0 (mod p), p < 6k - 1 6b + 1 = 0 (mod p), p < 6k + 1 p p is composite. That is, (6A; —1, 6A; + 1) is not a twin Suppose k E K. So k ^ CL (mod p), Vp prime, 5 < p < V6k — 1 and k ^ bp (mod p), Vp prime, 5 < p < \/6fc + 1 . P It follows that and 6k — 1 ^ 6A; + 1 ^ 6o — 1 = 0 (mod p), Vp prime, 5 < p < y/6k — 1 66 - f - 1 = 0 (mod p), Vp prime, 5 < p < V6A; + 1 . p p B y observing 2, 3 { 6fc — 1, 6A; + 1, we have and p \ 6k — 1 Vp prime, p < \/6k — 1 p f 6k + 1 Vp prime, p < y/6k + 1 . Therefore 6A; — 1, 6A; + 1 are both prime. That is, (6A; — 1, 6A; -I- 1) is a twin prime. Additional Remarks: 1. If k ^ dp (modp), Vp prime, 5"'< p < y/6k — 1, thereby indicating 6A; — 1 prime, then it is actually true that k ^ a (mod p), Vp prime, p > 5, except for p = 6k — 1 itself. p 2. Ii k ^ bp (modp), Vp prime, 5 < p < V6A; + 1 , thereby indicating 6/c + 1 prime, then it is actually true that k ^ b (mod p), Vp prime, p > 5, except for p = 6k + 1 itself. p 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 . This means that all possible 6/c± 1 that are divisible by p and not divisible by any prime q < p must be greater than or equal to p . This means that cancellation of numbers, k, where k = a (mod p), starts at [^-^p-J. Likewise, the cancellation of numbers, A;, where k = b (modp), starts at L - ^ ] . It is thus ensured that for all remaining numbers, k, both Qk — 1 ^ 0 (mod p) and 6k + 1 ^ 0 (mod p). We will refer to [ ^ J and [ ^ J as the starting points of cancellation and they are actually equal since for every p > 5, one has p = 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. 2 2 p 2 p 2 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 4.2.1 Applying Selberg's Results to Twin Primes T h e Eratosthenes A p p r o a c h 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 $ , • where the product is over all odd primes p. Then ^ 16CX ^ , ^ / O o g l o g X 7T (X) < T - ^ T Z 1+ O log X V V log* 2 2 • ... Chapter 4. Twin Primes 39 Proof: Take f(n) = n(n + 2). Then the function p i n this sifting situation is given by p(p) = 2 i f p > 2 , p(2) = l . Thus p(p) < 2 for all p, so (as i n 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 ( ^» K^)( fe)) . I ^ ( i o(^)), a i + o W + where = I n 2 ( p 11 - 1 ) 2 p(p-2) ^ f e ^1 ^A,*- ) 2 0 = 2^( 1 + 0 ( ^ ) ) (C as in (4.2.1)) ( s e e ( 2 ' 3 1 ) W i t h w ^ = Applying Theorems 3.1.1 and 3.2.3, we now have v IX ir (X) < S(A, P(VD)) + n(VD) < 2 +0(D log * D). 2 A log" VD D Our result follows as stated on choosing D = X / (log X) 2 K + 3 , where K — 2. Q.E.D. 4.2.2 T h e Alternate A p p r o a c h 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 — 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 — 1 are sifted where 1 < N < X, to retain those where both N = 6n — 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 — l)(6n + 1), just as the previous theorem sifted the numbers N(N + 2). If we let TT' (X) denote the number of n with 1 < n < X/6 such that both 6n — 1 and 6n + 1 are prime, we observe that TT' (X) = ^{X) — 1; (3, 5) is not counted by 7r (X). Hence we would expect TT (X) to have a similar upper bound as ^ ( X ) upon applying the Selberg sieve on the numbers (6n — l)(6n + 1). This is indeed the case as demonstrated by the next theorem, and we can actually achieve the same upper bound. 2 2 2 2 Theorem 4.2.2 Let where the product is over all odd primes p. Then Proof: Take f(n) = (6n — l)(6n + 1). Then the function p in this sifting situation is given by p{p) = 2 if p > 3, p(2) = 0, P(3) = 0. 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 Chapter 4. Twin Primes 41 where *-J.n>i)Vr 3<p<VD (p-i) = 1 P>V^ = 2 n 12^( 1 + V F ; °(TD)) (SEE (2 - 31) WITH ™ ^ = Applying Theorems 3.1.1 and 3.2.3, we have + Tt(VD) TT' (X) < S(A,P(VD)) 2 < 2 +0(Dlog "D) 2 ' J ^log . VD Our result follows as stated on choosing D = X/(log X) , where K — 2. 2K+3 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; • i J r n 1 > oo as n —• oo, Pi where pi is the i-th. prime number. The proof of this fact can be found i n 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 42 Primes 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\, p , ... be the sequence of prime numbers p such that p + 2 is also prime. Then 2 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 1 if n, n + 2 are both prime, 0 otherwise. and ( / ' is continuous on [2, oo)). Then let A(x) - £ . 0 ,•n 7T (x) = 7T (x), 2 2 2<n<x and B(x) E 2<n<i '71 a. n E 2<n<x n, n+2 prime 1 n Chapter 4. Twin Primes 43 Note here that B(x) is the sum of the reciprocals of only the first members of twin primes. This will not be a problem, however, because if B(x) is shown to be bounded by a constant y , then the sum of all reciprocals would be bounded by M since < ^- Proceeding now with use of Lemma 2.2, we have B{x) = J* f(t)d(A(t)), and making use of integration by parts (2.32), this becomes B(x) = [A(t)f(t)] - J\(t)f(t)dt = A(x)f(x) - A(2)/(2) - j T A(t)f'(t)dt = A(x)f(x)-J^ x 2 < 16C A(t)f'(t)dt (since A(2) = 0) ^(x)y ) )w0 ' ih Gog (*))( LViog' Viog (*h + 2 2 2 (by Theorems 4.2.1 and 4.2.2), where C is the constant from Theorems 4.2.1 and 4.2.2. Continuing the calculation, we get B(x) f 1 < 16C dt \og\x) + i; J t log (t) ~ 1 x - . 2 2 = = 16C 16C i _ r l0g (.T) 2 1 log (z) 16C log(2) 2 i |>g(0j J 2 1 (as x —> oo). From this it follows that VViT J , PiT J + , 4 2 1 log(x) +' log(2)J < M, Chapter 4. Twin Primes with M = 44 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 + 2 5 ) . 5.1 Sifting G e n e r a l P r i m e P a i r s 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 2 5 , 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 j V = 36, we cancel all proper multiples 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 — 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.) 1 2 3 i 7 9 9 13 19 22 25 28 27 31 32 33 34 n n n n n 5.1.2 5 11 17 23 29 35 46 ft n n u m n The Alternate Sieve for General P r i m e 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 actually yield general prime pairs in an indirect way. Since all primes, other than 2 and 3, are either of the form 6A; — 1 or 6k + 1, we see that general prime pairs, (p, p + 2B), are either of the form (6A; — 1, 6A; + 2B — 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 t ' -1 if B = 1 (mod 3) 1 if B = 2 (mod 3) < - 1 or 1 if fl = 0 (mod 3) k Convention Note: It will 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; — t, 6k + 2B — 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; — t, 6k + 2B — 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 — i , 6k + 2B — t are prime (when applicable); i.e., we get general prime pairs. The sieve also makes use of the observation that if 6k ± t (or 6A; + 2 5 ± t) is not prime, then it has a prime factor less than or equal to Chapter 5. General Prime Pairs (G.P.P.) 47 y/W±t (or \/6k + 2B±t). If B = 0 (mod 3), we actually conduct two separate applications of the alternate sieve, once for t = 1, and once for t — —1. 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). A s such, we need only worry about prime factors less than or equal to \/6N •+ 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 a , b by p 6a + t = p p 0 (mod p), 0 < a < p p 6b + 2B + t = 0 (modp), 0 < b < p. p p Then starting with J> cancel all numbers that are a (mod p), and starting with [ " g * ] , we cancel all numbers that are b (mod p). A l l remaining numbers, k, yield a general prime pair (6k + t, 6k + 2B +1). w e p p 5 - p A n example of the General Alternate Sieve We Consider the case B — 3. Here, we have both types of general prime pairs, (6k — 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 : a = 1, and cancellation starts with p L^-jpJ — 4. 6 = 0, and cancellation starts with L^ipJ = 3. For 7 : a = 6, and cancellation starts with L^pJ = 8. bp = 5, and cancellation starts with [-^pj = 7. P p 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 starting 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.) 1 4 2 3 4 ^ 12 1^3 14 1^ 0 1^ 7 8 9 17 18 48 .tK) It is easily verified that all the remaining numbers, k, yield general prime pairs, (6A; — 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 \/Il5 < 11, i.e., 5 and 7. + 7 = For 5 : a — 4, and cancellation starts with [^f^-\ = 4. p b = 3, and cancellation starts with [*%^J p For 7 : a = 1, and cancellation starts with p = 3. = 8- b = 0, and cancellation starts with L^ir"J = 7p 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 starting with 8 that is 1 (mod 7), and everything starting with 7 that is 0 (mod 7). 1 2 ? ^ 5 6 11 12 1^ % ty X A ^ 1 16 17 1\8 0 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 multiplicity 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 — t, 6k + 2B — 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 a , b by 6a + t = 0 (mod p), 0 < a < p 6b + 2B + t = 0 (modp), 0 < b <p . p p p p p p Let K = {k\ k G N and k ^ a (mod p), Vp prime, 5 < p < V^k + t (when this makes sense)} p (1 {k\ k E N and k ^ 6 (mod p), Vp pn'me, 5 < p < VQk + 2B + t (when this makes sense)} P Then k G K if and only if 6fc + t, 6k + 2B + t are both prime. That is, (6k + t, 6k + 2B + t) is a G.P.P. Proof: (Contrapositive) Suppose k £ K. Then either k •• = a (mod p), for a prime p, 5 < p < V6k + t <; 6k + t p or k = b (mod p), for a prime p, 5 < p < V6k + 2B + t < 6k + 2B + t p Therefore either 6k + t = 6a + t' = 0 (mod p), p < 6k + t or 6k + 2B + t = 6b + 2B + t == 0(modp), p <6k + 2B + t p p So one of 6k + t, 6k + 25 +1 is composite. That is, (6A; 4-1, 6k + 25 +1) is not a G.P.P. Chapter 5. General Prime Pairs (G.P.P.) 50 Suppose k 6 K. So k ^ and k ^ a (mod p), Vp prime, 5 < p < y/6k + t p bp (mod p), Vp prime, 5 < p < V6k + 2B + t . It follows that and 6k+ t =£ 6a + t 6k + 2B + t # p 66 + 2B +1 p = 0(modp), Vp prime, 5 < p < y/6k + t = 0(modp), Vp prime, 5 < p < \/6k + 2B + t B y observing 2, 3 f 6A; + t, 6k + 2B +1, we have and p\6k + t Vp prime, p < y/6k + £ p j 6/c + 2 5 + t Vp prime, p < V6k~+W~+t . Therefore 6k+ t, 6k + 2B + t are both prime. That is, (6A; +1, 6k + 2B +1) is a G.P.P. Additional Remarks: 1. If k ^ a (modp), Vp prime, 5 < p < y/6k +1, thereby indicating 6k + t prime, then it is actually true that k ^ d (mod p), Vp prime, p > 5, except for p = 6k +1 itself. p p 2. If k ^ 6 (mod p), Vp prime, 5 < p < \/6A; + 2B +1, thereby indicating 6k+2B+t prime, then it is actually true that k^b (mod p), Vp prime, p > 5, except for p = 6k + 2B +1 itself. P p 3. A s previously mentioned, the first composite number that is divisible ,by a prime, p, and has no prime factors q < p is p . 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 . This means that cancellation of numbers, k, where k = a (modp), starts at L^ipjLikewise, the cancellation of numbers, k, where k = b (mod p), starts at [ ~ ~ J . It is thus ensured that for all remaining numbers, k, both 6k + t^0 (mod p) and 6k + 2B +1 ^ 0 (mod p). 2 2 p p p 6 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, [ ~ J , then for these primes p = 6k +1, one could potentially have ^( ) ~ ~ j < 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. p 6k+t 2B t Q.E.D. 5.2 5.2.1 Applying Selberg's Method 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 B(X) to be the number of n where 1 < n < X, such that both n and n + 2B are prime. 2 Theorem 5.2.1 Let P(P - 2) (p - l ) 2 where the products are over odd primes p. Then p-1 (5.2.1) 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 f 2 ifp->\2B = pip) I 1 ifp 2B . 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) > 1 L ( - J ^ L = - ) [ i + 0 2! \V(P(VD))JX ' " ^ l o g ^ ( l o ( ^ ) ) , + VogD where A DB = \n(i-l) p\B n p\B P (p - 1 ) P(P - 2) 2 P<VD p\B, p*2 p?2 2 P P<VD P\B, P#2 P5*2 I- - i - i n nH n P(P ~ 2) (P " I) . P\B \p#2 P(P ~ 2) 2 \P#2 (C as in (5.2.1)) piP TTP U i-^ 2) 11 (p _ 1)2 . Pi* \P#2 v . P\B \p#2 ^ H 1 + 0 U (see (2.31) with w = \/15) = (C as in (5.2.1)). ^( {TE 1+0 B Applying Theorems 3.1.1 and 3.2.3, we have 8 7T BPO < S(A, 2 P{y/D)) + n(VD) < 2X A log y/D DB 2 + 0{D log * D) . 2 Chapter 5. General Prime Pairs (G.P.P.) Our result follows as stated on choosing D = J C / ( l o g X ) s 2re+3 53 , where K = 2. Q.E.D. 5.2.2 The Alternate Approach In the alternate approach presented for sifting general prime pairs, for 1 < n < X/6, if we sift the numbers n to retain those where both 6n+t, 6n+2B+t are prime (t fixed as either 1 or —1, and B > 1 is an integer constant), along with those where both 6n — t, 6n + 2B — 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 — t, N + 2B = 6n + 2B — t are prime (when applicable), we also get all the general prime pairs less than or equal to X. Therefore, i n applying the Selberg sieve to the alternate approach, we must sift the numbers (6n + t)(6n + 2B + t), along with the numbers (6n — t)(6n + 2B — 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 — l)(6n + 1) in the case of the alternate approach for sifting twin primes. We let 7 r ( 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 — t and 6n + 2B — t are also prime. We observe that 2 B - 1 if (3, 3 2B) is a G.P.P. i " ^ : if (3, .3 + 2B) is not a G.P.P. ; Hence we would expect 7 r ( 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 — t)(6n + 2B — t} (when applicable). This is indeed the case as demonstrated by the next theorem, and we can actually achieve the same upper bound. 2B Theorem 5.2.2 Let P-1 p>2 (P - I) 2 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 if B = 1 (mod 3) if B = 2 (mod 3) [ - 1 or 1 if B = 0 (mod 3). ( -1 t = < 1 Also recall that when 3 | B, we apply Theorem 5.1.1 to each case separately (t = 1 and i = — 1). So in the case when 3 | 5 , it is convenient to think of £ 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 — t, 6n + 2B — £). 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). A s such, we take / i ( n ) = (6n + £)(6n + 2B + £), and when applicable (i.e., 3 | B), f (n) = (6n-t)(6n + 2 2B-t). Then for each situation, fi and fa (when applicable), the function p is given by 0 ifp = 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 — 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.) where n A' DB 55 P p\B P5^2,3 3 p\B, p£2, p\B p^2,3 pfB, p#2, 3 n i-i 3 4 P \pjL2, 3 . n P(P ~ 2) (P " I ) P\B P(P - 2) 2 W , 3 2 ( C as in (5.2.2)) 12 n W 2 p TT P(P ~ 2) 11 (p_l)2 . .P|B ^ W2> 3 p V 3 1 J (see (2.31) with iw = v^D) 12 I 1 1_ £ ( 12C C if 3 | B and C + 1 B + 0 ( T D ) ) if 3 | B and C B as in (5.2.2) f l as in (5.2.2) 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 i n all cases, TT PO 2B < S(A,P(VD)) + *(VD) < A' log ^ 2 + 0(D log " D) . 2 DB Our result follows as stated on choosing D =,X / (log X ) 2 K + 3 , where = 2. Q.E.D. K 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 if -L_ )<M, N + Pi + 2B J ~ \p, where M is a constant. Proof: We wish to use partial summation; i n particular, Lemma 2.2 which makes use of integration by parts (2.32). Let n _ J 1 if n, n + 2B are both prime, \ 0 otherwise. and f(n) = — n ( / ' is continuous on [2, oo)). Then let () A x = £ n a = TT B( ), X 2 2<n<x and B{X) =y -= T a j 2<n<x 2<n<x n, n+2B prime Note here that B(x) is the sum of the reciprocals of only the first members of the general prime pairs. This will not be a problem, however, because if B(x) is shown to be bounded by a constant 4p t the sum of all reciprocals would be bounded by M since < K Proceeding now with use of Lemma 2.2, we have n e n B(x) = j f * f(t)d(A(t)), Chapter 5. General Prime Pairs (G.P.P.) 57 and making use of integration by parts (2.32), this becomes B(x) j*A(t)f'{t)dt = [A(t)f(t)] x 2 = A(x)f(x)-A(2)f(2)-£ A(t)f'(t)dt = A(x)f(x) - (since A(2) = 0). < 16CC B A(t)f'(t)dt x \og\x)) J \x) \\og\t)J 2 V* 2 dt (by Theorems 5.2.1 and 5.2.2), where C and CB are the constants from Theorems 5.2.1 and 5.2.2. Continuing the calculation, we get B(x) < r i 16CC B I log ix) J J H o g (*) + 2 = IQCCB Liog(t)J 2 1 = mcc B WCCB ' Liog (*) log(2) log(x)-'+ log (x) 2 -dt 2 1 log(2)J (as ir —> oo). From this it follows that Pi Pi + 2B with Af = < M, 32CC B log(2) • Q.E.D. 58 Chapter 6 Concluding Remarks 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 b = —a . 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 b = — a . 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 sifting 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 instance, 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 separated 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 p p p g.c.d.(A, I) = 1. p 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 T w i n Prime Conjecture states that they do occur infinitely often, and somewhat associated 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 T w i n Prime Conjecture and Goldbach Conjecture are only two of many problems where sieve techniques can be applied. 60 Bibliography [1] Apostol, Tom M . Introduction to Analytic Number Theory, Undergraduate Texts i n 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 . O n 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 Introduction 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-Hill, Inc. 1976. pgs. 63-64.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The Selberg Sieve and prime pairs
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The Selberg Sieve and prime pairs Duarte, Martin Christopher 2005
pdf
Page Metadata
Item Metadata
Title | The Selberg Sieve and prime pairs |
Creator |
Duarte, Martin Christopher |
Date Issued | 2005 |
Description | 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 sifting 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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2009-12-11 |
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. |
DOI | 10.14288/1.0080068 |
URI | http://hdl.handle.net/2429/16435 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2005-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2005-0203.pdf [ 2.36MB ]
- Metadata
- JSON: 831-1.0080068.json
- JSON-LD: 831-1.0080068-ld.json
- RDF/XML (Pretty): 831-1.0080068-rdf.xml
- RDF/JSON: 831-1.0080068-rdf.json
- Turtle: 831-1.0080068-turtle.txt
- N-Triples: 831-1.0080068-rdf-ntriples.txt
- Original Record: 831-1.0080068-source.json
- Full Text
- 831-1.0080068-fulltext.txt
- Citation
- 831-1.0080068.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-0080068/manifest