Sieve Methods Citation Odlyzko, Andrew Michael (1971) Sieve Methods. Senior thesis (Major), California Institute of Technology. doi:10.7907/28FN-8P32. https://resolver.caltech.edu/CaltechTHESIS:01292014-160430243 Abstract Preface: The main goal of this work is to give an introductory account of sieve methods that would be understandable with only a slight knowledge of analytic number theory. These notes are based to a large extent on lectures on sieve methods given by Professor Van Lint and the author in a number theory seminar during the 1970-71 academic year, but rather extensive changes have been made in both the content and the presentation. Item Type: Thesis (Senior thesis (Major)) Subject Keywords: (Mathematics) ; sieve methods Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Apostol, Tom M. Thesis Committee: None, None Defense Date: June 1971 Record Number: CaltechTHESIS:01292014-160430243 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:01292014-160430243 DOI: 10.7907/28FN-8P32 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 8060 Collection: CaltechTHESIS Deposited By: Kathy Johnson Deposited On: 30 Jan 2014 00:45 Last Modified: 25 Jun 2024 00:06 Thesis Files Preview PDF - Final Version See Usage Policy. 18MB Repository Staff Only: item control page

SIEVE METHODS ANDRE\\ ~f. ODLYZKO A senior thesis CALIFORNIA INSTITUTE OF TECHNOLOGY PASADENA, CALIFORNIA 1971 CONTENTS Preface i 1 . The Sieves of Eratosthenes and Brun Notes 2. Selberg's Sieve Notes 3· Applications of Selberg's Sieve Notes 4. Primes in Arithmetic Progressions Notes 5· Gallagher' s Sieve Notes 6. Trigonometric Polynomial Inequalities Notes 7· The Large Sieve Notes 8. Bombieri's Theorem 15 17 27 29 46 48 61 62 68 69 94 S6 110 ,,1 Notes 128 BThl.iography 129 i PREFACE The main goal of this work is to give an introductory account of sieve methods that would be understandable with only a slight knowledge of analytic number theory. These notes are based to a large extent on lectures on sieve methods given by Professor Van Lint and the author in a number theory seminar during the 1970-71 academic year, but rather extensive changes have been made in both the content and the presentation. Several developments related to the subject of these notes are not discussed in them at all. One such is Renyi's probabilistic version of the large sieve, for which the reader is referred to Renyi [4]-[9]. Another is Vinogradov's method of trigonometric sums which was used to prove the famous theorem that any sufficiently large odd integer is representable as a sum of at most three primes. cussed in r . M. Vinogradov [1). This method is dis- Neither of the two methods mentioned above would fit in very well in this work, however. A much more serious omission, due to lack of time, is that of Selberg's lower bound method. Although much more complicated and in many ways less satisfactory than the upper bound method, it gives the best results known in many cases. We might mention here that using this method it has been shown that there are infinitely many primes p such that p + 2 is a product of at most thre~rimes, and thateyery sufficiently large even integer can be repre- ~ sented as a sum of a prime and a product of at most three primes . While these results do not prove the twin prime conjecture (which states that p + 2 is a prime for infinitely many primes p) nor Goldbach's conjecture ii (that every even integer~ 4 is a sum of two primes), they are still significant achievements. A new unified proof of both of the above results is given in Richert [1]. A good introduction to Selberg's sieve is provided in Halberstw and Roth ( 1; Chapter 4]. A much more com- prehensive and more up-to-date presentation is given in Richert [3]. All references for results quoted in any chapter are given in the notes at the end of that chapter. These notes also contain sane general bibliographic information and often some additional facts. The biblio- graphy contains practically all the publications on sieve methods of which the author is aware, and an attempt has been made to supply Mathematical Reviews references for as many as possible. I am greatly indebted to Professor Gall~ for pennission to use the material of Chapter 51 which has not yet been published. I would a.l so like to thank Professor Van Lint for lecturing on the material of Chapters 3 and 4, and for help on many problems. I am very grateful to the Mathematics Department of the California Institute of Technology for a 1970 Summer Research and Independent Study Fellowship, which made this work possible. Most of all I would like to thank Professor Apostol for his advice, encouragement, and guidance. His help in the writing and editing of these notes bas been invaluable. Finally, I would like to. e~ss my appreciation to Mrs. Lorayne Decker for her ~tience and =-...... skill in typing the manuscript. Andrew Odlyzko Pasadena 1 California June 1971 1 1 THE SIEVES OF ERATOSTHENES AND BRUN The name "sieve method" comes fran the sieve of Eratosthenes, an algorithm for finding all primes. It utilizes the fact that a natural number is prime if and only if it is not divisible by any prime smaller than itself. To find all the primes ~ x, one writes down the natural numbers 2, 3, 4, •.. , [x) in this order. Since 2 is the first prime, it is left untouched, but every proper multiple of it (that is, every second number starting with 4) is crossed out, since it is composi te. The next number in the sequence is 3, and it has not been crossed out yet. Hence it is not divisible by any prime smaller than itself, and so it is prime. Therefore 3 is left as it is, but every proper multiple of 3, being composite, is crossed out. The next number, 4, has already been crossed out, and therefore must be composite. not been crossed out and hence must be a prime. all its proper multiples are crossed out. The next one, 5, has It is left alone but Since if an integer~ x is composite, at least one of its prime factors has to be ~ rx ' it is sufficient to continue this process only up to [ Yx ] . The numbers which have not been crossed out are exactly the primes < x. Thus this procedure "sieves out" all the composite numbers. ~ ~t n(y) denote the number of primes ~ y. The sieve of Eratosthenes can be used to obtain an exact fonnula for n(x) - n( y'X), the number of primes between yx and x. Let 2 s'(n) = 1 ifn=1, 1 if n is prime and 0 otherwise. Vx < n ~ x, Then I n(x) - n( Vx) = s'(n). 2<n<x Now let II = Tf ~Yx P· We observe that the sieve of Eratosthenes removes all those natural numbers < x which are not relatively prime to II, except for the primes ~ Yx· Since the M8bius function satisfies the relation \ { 1 if n = 1, din 0 if n > 1, L ~(d) = we have s'(n) = ( 1• 1) I ~(d) dl (n,II) for each n ~ x, and hence n(x) - n( yX) + 1 = I n<x s'(n) = I I n<x ~(d) = dl (n,II) I ~(d)[~] diii 3 But I ~ = Pin IT ( din 1 - !) :: P TT P:: vx (1 - !) P and so we obtain the exact fonnul.a ( 1 .2) 1t(x)-1t(Yx)+1=xiT (1-~)+ I~(d){[~) -~}. P:: Yx Each term in di n I~(d){[~] - ~} is< 1 in absolute value, but there are din 21t( fx\erms, a number much larger than x. Still, one might hope that the first term on the right side of (1.2) yields the correct order of magnitude of 1t(x) - 1t( 1(X) and that the second term is of a smaller order because of cancellation due to alterations in the sign of ~(d) and the small size of the factors [~] - ~ is much smaller than 1 ). ( 1 • 3) (since for most divisors d of n,x/d However, a theorem of Mertens states that 1 e-y TT (1 - p)logy as y ~ ~, p~y where y is Euler's constant, so the first term on the right of (1.2) is asymptotic to 2e -yx/log x. But, by the prime number theorem, the left side of (1.2) is asymptotic to x/log x, so that the second term on the right is asymptotic to {1 - 2e-y)x/log x. o~(l. Hence each term on the right is asymptotic to a constant times ----x , so that we cannot 1 og x expect to obtain useful estimates for 1t(x) - 1t(l{X) from this identity. 4 Nevertheless, the same underlying ideas can be used to obtain estimates for the number of integers ~ x which are not diviEible by any prime p ~ z, provided z is much smaller than discussion we considered the case z = yi.) Yx· (In the foregoing This time we let n = Tfp p~z and define s'(n) by (1.1 ). Then the number S(x,z) of integers~ x not divisible by any prime ~ z is given by I ~(d) I dj(n,n) S(x,z) = Is'(n) = n<x n<x = Since each term in the sum on the right has absolute value < 1, the sum itself is 0(2~(z)), and therefore S(x,z) = x TT (1- .!.) + 0(2~{z)). ~z p By Mertens' theorem the first term is asymptotic to e-yx/log z as x ~ ~, provided z ~ ~ also. Now if z = log x we have log x log x log 4 log 4 log z log z 2~(z) < 22z/log z = 41og z = e =X = Xo( 1) so::-the.. second term is much smaller than the first term. -""'-._ as x ~~but z ~ log x we have e-yx S(x,z) - -1og z as x -+ ~. 1 Thus, if z ~ ~ 5 As is shown below, the above method can be generalized to give information about the number of integers ~ x which are not divisible by any prime ~ z, when these integers belong to sequences other than the sequences of natural numbers. Unfortunately the requirement that z be very small in comparison with x ltmits the usefulness of such generalizations. Modern sieve methods originated with Viggo Brun around 1920. He used a new sieve to obtain several important number-theoretic results, notably an estimate of the density of twin primes. In the next few pages we will develop a very simple form of Brun's sieve which will enable us to prove a theorem on the density of twin prtmes (Theorem 1.4). While weaker than the best results obtainable with Brun's sieve, i t will be sufficient to prove the ce~ebrated theorem of Brun that the sum of the reciprocals of the twin primes converges (Theorem 1.5). We will first state Theorem 1.4 and then use it to prove Theorem 1.5. The rest of the chapter will then be devoted to the proof of Theorem 1.4. ( 1 .4) THEOREM. Let T denote the set of twin primes (that is, primes p such that either p- 2 or p + 2 is also a prime), and let T(x) = E 1. p<x peT Then T(x) ~ log ~ x(log log x x)2 for x >_ 3, where ~ is the Vinogradov symbol*) • *) F(x) <g G(x) is equivalent to F(x) = O(G(x)); that is, both imply that there is a c >0 such that IF(x)l < c G{x) for x in the range indicated. 7 So far we have only utilized concepts from the sieve of Eratosthenes. Since good estimates for B(x,d) can be obtained quite easily (see (1.12) below), we could write S(x,z) as the sum of a main term for which an asymptotic estimate exists and a remainder. Unfortunately, just as before, the remainder would be a sum over all divisors d of n, and therefore we would need to take z of a much smaller order of magnitude than x to ensure that the main term is the dominant one. The main idea of Brun' s sieve is that in order to get an effective upper bound for S(x,z) when z is fairly large compared with x one should sum in (1.6) over only a relatively small subset of divisors of TI, where this subset is chosen so that the resulting sum is greater than or equal to S(x,z) (and to get a lower estimate one should sum over a subset that makes that sum less than or equal to S(x,z)). In this chapter we will 2o log log x • To do this, obtain an upper bound for S ( x,z ) when z = x let us take an even natural number m < r (which will be specified more exactly later) and define s(n) = ( 1. 7) L ~(d) dl (n(n+2),n) v(d) ~ m where v(k) is the number of distinct prime divisors of k. (1.8) LEMMA. For all integers n, s'(n) ~ s(n). 8 Proof: Let t = (n(n+2),n). Then we have s'(n) = I~(d), djt L ~(d). s(n) = dlt v(d}Sm If t = 1, then s'(n) = s(n) = 1. If t > 1, then s'(n) = o. Therefore in order to prove s'(n) ~ s(n), we only need to show s(n) ~ 0 when t > 1. Let us assume t > 1. Since t divides n, all divisors oft are squarefree and hence s(n) = L 1 I 1 djt djt v(d)< m v(d)< m v(d)-even v(d) -odd Fix a prime p which divides t. Suppose &It, v(6) < m, and v(6) is odd (so that 1 ~ v(&) S m - 1 because m is even). Let if p"' 6 , if P I 6 • Then v(6') = v(6)+1 { v(6) - 1 if p'}6, if P I 6 • Thus &_' is a divisor oft with v(6') even and 0 S v(6') ~ m. Since the correspondence between 6 and &' is one-to-one, there are at least as many d with dlt, v(d) < m for which v(d) is even as there are those for which v(d) is odd. Therefore s(n) ~ o, and the proof of the lemma is complete. 9 Applying Lemma 1 • 81 we obtain X X S(x,z) < ( 1.9) n;::1 I dl (n(n+2),n) n odd v(d)Sm In=1 s(n) = I n odd = ~(d) L ~ (d)B(x,d). din v(d)Sm In order to simplify further work we will denote by p (f) al.l d In with v(d) = f (with the convention p(O) = 1). t(f) will be understood to p Then (1. 9 ) becomes be the sum over all din with v(d) =f. m (1.10) S(x,z)S L(-1/ )' f=O B(x,p(f)). ;(f) Next let us compute B(x 1 p(f)) = B(x,pi ••• pi ) =number of odd 1 n S x such that n(n+2) e 0 (mod (p 11 •·· p 1f f )). Since for odd n we have (n,n+2) = 1, each pi divides exactly one of n, n + 2. Thus the con- j gruence n(n+2) =0 (mod (pi ••• pi )) is equivalent to the congruences 1 n f =0 (mod ( TT p)) p€P1 (1.11) n+2 = 0 (mod ( lT p) ) pEP2 where P 1 and P2 are any two sets such that 10 ( 1. 12) B(x,p (f) ) X f = 2f :::m + 2 a, I el < 1. 2p Combining (1.12) with (1.10) leads to (1.13) 8 (x,z ) ~ x 2 ~L ( - 1 )f \L :1fY 2f ~ (fr )2f, + L f=O p (f) p f=O Now (1.14) m m f=O f=O I (~)2f ~ I 2frf < (2r)m+l , and r 2f \ f-1 \ l ~...,c-1) L f=m+l (f) p =-rn+ ( 1.15) p =m p r = IT(l-~)+ ry~z where - f L (-1/-1 sf f=m+1 3 5 ... , s the f -th elementary symmetric function of 2 , 2 , *) The k-th elementary symmetric function of a 1, ••• ,at is defined as ~ ai *) t ••• a~ where the sum is over the (k) possible choices of i 1, ••• ,~ 1 from 1,2, ••• ,t; thus, for example, s 1(x,y,z) = x+y+z, s 2 (x,y,z) = xy + xz + yz, and s (x,y,z) = xyz. 3 11 We thus find from {1.12) - {1.15) that r ( 1.16) S(x,z) ~ (2r)m+ + ~ 1 \ole next lT {1- g)+~ 3~~z p I {-1)f-1 sf. f=m+l observe that ( 1. 17) since any product of {f+1) terms can be written in {f+l) ways as a product of a single factor and a product of f factors. 82 83 < 1 < 1 s 2 _ 2 , s _ b' and in general ( by induction ) Therefore 3 f s1 sf ~ f! • Relation (1.17) also shows that sf~ sf+l i f s 1 ~ f + 1. 2 choose m + 1 > s 1 = t 35P~Z p (the only restriction on m so far was that r it be even). Then Let us now ( -1 ) f-1 sf becomes an alternating sum with tenns m+1 m+1 s1 (mes 1) decreasing in absolute magnitude, so that it is < s 1 < ( 1 ), < - + 1 - m+ - m+ • t f=m+l (in t he last inequality we used the fact that n! > (n/e)n). In addition, since by a theorem of Mertens (1.t8), s1 = I ~ = 2 log log z + 0 ( 1 ) > ~pSz 2 we can choose m so that e s 1 < m + 1 < 9s guarantees m < r), and then 1 for sufficiently large z (this 12 es (m +11) m+ 1 1 S <e) m+ 1 2 8 < e-e 81 < e- 1 • Also, 1 - y S e-y for all real y, and thus 2 -s1 TT (1 - p-) < e • - rySz Since r = ~(z) - 1, we can use 2r < z in (1.16). Then the inequalities above lead to 9s 1 -s 1 S(x,z) S z + xe Because of (1.18} there is a constant C such that for z ~ 3, 2 log log z - C < s 1 < 2 log log z + C and therefore for sufficiently large x,z c S(x,z) < z(18 log log z + 9C) + -=xe~..,.,. 2 (log z) 1 We now take Z =X 20 log log x • Then for sufficiently large x log x < log z = 20 log log x , log log z _ log log x, and hence Therefore for all x ~ 3, say, 1 20 1og log x) ~ x(log log x) ~ log x S(x,x 2 • 13 To complete the proof of Theorem 1.8 we observe that T{x) < 2z + 2S(x,z) ~ x(10~ log og x 2 x) . The method used in proving Theorem 1.4 can easily be generalized. We could, for example, investigate the density of primes p for which p + 2 and p + 6 are also primes (it has been conjectured that there are infinitely many such prime triplets). h ~ x x (logioglog x) 3 of them below x. We would find that there are However, in Chapter 3 we will obtain more accurate and more general results by using Selberg's sieve, so we will not deal further with this subject here. So far we have dealt only with Brun' s upper bound method. However, the lower bound method is analogous {actually one of the advantages of Brun's over Selberg's sieve is that the two methods are almost identical in case of Brun' s sieve). The most important difference is that in ( 1. 7) we would take m odd in order to obtain a lower bound for S{x,z). After making a few obvious modifications in the proof of Theorem 1.4 we would ~~--1~~ 20 log log x) > cx( 10~0!0~ x) 2 find that s(x,x for same positive con- stant c. Unfortunately, this result does not allow us to obtain a lower bo\ll}d for T{x). "'-- The best versions of Brun's sieve give estimates a< 1/2 is a constant. There a set of primes is chosen: p <p <···<p. t t-1 1 0 for S(x,x ) where 14 In the upper bound method s(n) is defined as in (1.8) except that sum- mation is over those d which have at most 2i of their prime divisors greater than or equal to pi (~the lower bound method: at most 2i - 1). By choosing those t primes appropriately it is possible to show that T(x) ~ x(log x)- 2 • We will obtain this result using Selberg's sieve. 15 Notes on Chapter 1. Proofs of Mertens' theorems (Eqs. (1.3) and (1.18)) may be found in Hardy and Wright [1; Chapter 22]. The exact formula ( 1 .2) not only fails to give a good asymptotic estimate for n(x), but it is also not very useful in actually calculating n(x) for a specific x. However, Meissel [1] has found another exact formula for n(x) which leads to an effective (even though laborious) procedure for calculating this function. Uspensky and Heaslet [1; Chapter 5] also give a presentation of this method. Several mathematicians have investigated the number positive integers~ x and free ~(x,y) of of prime factors~ y. Buchstab [1] proved that for a fixed u ~ 2, lim t(yu,y)y-ulog y = w(u), y-+oo where d du (uw(u)} = w(u-1) for u > 2. Further results were later obtained by De Bruijn [ 1) -[ 3] and Ramaswami [1], [2]. Their methods, however, were analytic. Our version of Brun's sieve largely follows the presentation of Landau (2; Part 2, Chapter 2], Rademacher [2; Chapter 15], and Gelfand and Linnik [1; Chapter 5]. The main difference is our explicit use of the sieVing function s(u), a concept borrowed from Selberg's sieve. The literature on Brun's sieve is rather extensive. Practically all the papers listed in the Bibliography that were published before 1942 16 deal with this subject. Moreover, there is a presentation of Brun's sieve in Gelfand and Linnik [1; Chapter 5]. Although it had seemed for a while that Selberg's sieve had superseded Brun's, Miech [2] recently used the latter to prove important results on the almostprime values assumed by a polynomial. 17 2 SELBERG Is SIEVE Let us suppose that A = (a } is a sequence defined by a = h( v), v \) v = 1 ,2,... where h is an integer-valued polynomial. set of primes (:S. z for scme z). Let P be a finite Many important number theoretic problems reduce to the problem of estimating the number S(A,P,n) of w·hich are not divisible by any prime p E P. a \) , v-:1 , ••• , n For example, such estimates in the case h(x) = x(x+2) give information about the twin primes. In this chapter we prove a result (Theorem 2. 17) which will enable us to obtain effective upper bounds for S(A,P,n) in a wide variety of cases. Selberg's sieve can be formulated so as to apply to general sequences of integers. However, the sequences generated by polynomials are the most important ones for which effective estimates can be obtained, and so we will deal only with them. Let N(d) denote the number of solutions of (2 .1) h(v) =0 (mod d), 1 < v < d. Then by a property of congruences is a multiplicative function. N Those primes p for which N(p) = 0 do not contribute to the "sieving out" process and so we may assume that none of them belong to P. if N(p require ~ p for some prime p E P, then S(A,P,n) = o. :S. N(p) < p for all p E P. In addition, Therefore we will For convenience in later work ''e define (2.2) d f(d) = N(dJ . The function f is multiplicative and 1 < f(p) :S. p for all p E p. 18 The v between 1 and n are divided into [~] complete residue classes modulo d plus at most d - 1 additional v. There are exactly N(d) integers v in every complete residue class such that a v =0 (mod d) and there are at most N(d) such v among those left at the end. (2.3) Hence 1 = [~]N(d) + e·N(d) = f(~) + R(d), I (o ~ e ~ 1) v<n dja v where (2.4) IR(d) I Let us now define n = s. fCd) • ITp and pEP I ~(d) s'(a) = dl (a,n) if (a,n) = 1, if (a,TI) > 1. I ~(d) Then (2.5) S(A,P,n) = I s'(av) = I v<n v<n dj (a ,rr) v = I~(d) I 1 = n I ~f~~ + I~(d)R(d). din ~n djn djTI dja v Unfortunately this relation suffers fran the disadvantage that the second term, the remainder term, is a sum over all the divisors of IT, and so is very difficult to estimate. The main problem is to circumvent this obstacle. 19 First we observe that i f s(a) is a function defined by s(a) = (2.6) X(d) } '-' dl (a,n) where ~(d) is any function defined for all dill, then (just as in (2.5)) Ls(a) = n I ~~~~ + L~(d)R(d) v~n din where the left side depends on ~. din If~ is chosen so that s(a ) < s'(a ) v - \) for all v, then (2.7) L L S(A,P,n) ~ n ~~~~ + ~(d)R(d). din din The essential part of both Brun's and Selberg's sieves is the choice of ~ so that S(A,P,n) can be effectively estimated. The difficulty lies in the need to make the remainder smal.ler than the main term, while at the same time minimizing the latter (since we would like to minimize the right side of (2.7)). The task of making the remainder term fairly small is accomplished in both sieve methods by defining ~ to be zero outside a relatively small subset D* of divisors of n. In Brun's sieve, ~ is chosen equal to ~ on D* , and D* is chosen (in a rather complicated way) to ensure that s(a) ~ s '(a). In Selberg's sieve, on the other hand, the possibility of choosing ~ different from ~ is utilized, while D* is chosen in a rather simple fashion. The resulting estimates are, as it turns out, more effec- tive than those obtainable with Brun's sieve and are easier to find. 20 (It should be pointed out, however, that the transition fran Brun' s to Selberg's sieve was not as obvious as it might appear from this chapter. Our whole presentation utilizes many ideas introduced by Selberg in connection with his sieve, while Brun's sieve was originally formulated quite differently.) The set of all functions defined by (2.6) is too wide to work with. However, it turns out that very good sieving functions can be selected f rom a subset of it that is particularly well-behaved. Suppose we define (2.8) s(a) = L A(d) dl (a,n) where A is any function defined on all the divisors of n. (2.9) 2 Then 2 s (a) = ( L A(d)) = L ).(d) dl (a,n) dl (a,n) where (2. 10) ).(d) = L A(d 1 )A(~). d,,d21n d=[d,,~l Thus if we denote by T the set of all functions s defined by (2.6), then s 2 E T -vhenever s E T. Selberg's decisive observation was that we should 2 look for our sieving function among the functions s , where s E T. One great advantage of this choice, as we shall see, is that it leads to a 21 quadratic form which enables us, for every subset D of divisors of TI, to find the minimum value of X: ~ f(dJ over all .functions A which are d!TI zero outside D. The main reason for this is the great freedom of choice 2 2 as to A. To make s (a) > s'(a) it is sufficient to ensure that s (a) > 1 2 when (a,TI) = 1 and that s (a) > 0 when (a, TI) > 1. The first condition is easily satisfied by specifying A(1) = 1. But the second condition is satisfied trivially no matter what real-valued function we choose for A. Thus (2.7) will hold subject to the single restriction A(l) = 1. This is of great practical importance, since for a general function s defined by (2.6) it might be very difficult to prove that it satisfies s(a) ~ s'(a). As a result we can, when looking for the minimum of E diTI ~t~~ 1 treat A(d) as a free variable whenever d > 1. Before we prove the main theorem (Theorem 2.13) 1 we will derive a few preliminary results. Let us define (2. 11 > g(k) = I ~(d)f(k/d) dlk so that f(k) = Ig(d). dlk If kiTI then (d, ~) = 1 for each divisor d of k and hence f(k/d) = f(k)/f(d) since f is multiplicative. Therefore i f k ITI we have g(k) = f(k) I ~(d)/f(d) = f(k) IT (1 - fCp)) • djk Plk 22 In particular, we see that g(k) > 0. Also, since f is multiplicative, and therefore Next, let D be a finite, divisor-closed set (i.e., if d E D then all divisors of d belong to D) and let F(k) = I G(d), dED ktd where G is arbitrary. Then we have the inversion formula I ~(~)F(t) = G(d) (2. 12) tED dlt because I ~ (~ )F ( t ) = tED dlt (2.13) THEOREM. I ~ (~) L .t, ) L .t,) I ~ (~) = I .t, ) I ~ ( G( tED dlt .tED dl.t = G( .tED tl.t G( djt t!.t .tED dl.t 6 ) = G(d) • 6 I.e, d Let D be a divisor-closed set of divisors of n, and let D* ={~In, d = [d 1 ,~], where d 1 ,~ ED). that A(d) = 0 i f d ~ D, and let Assume that A(1) = 1 and 23 I X(d) = h(dl )A(~) if d E D* , d1'~ED [d,~]=d and define X(d) = 0 d ~ D* • if H(A) = Let I ~f~~ . dED* Then 1 H(A) ~ Q , (2.14) where (2. 15) Q= I sed> , dED and this lower bound is attained when A(d) (2. 16) 1\ = t+(d)f(dl \ Q /_, 1 SltY . tED dlt Proof: We have g(t) 24 Now we write y(t) = I ~f~~ · dED tid By (2.12) this means A(d) = f(d) I ~(t/d)y(t). tED dlt Since f is multiplicative, f(l) = 1, and by taking d = 1 we find 1 = I ~(t)y(t). tED This leads to \ 2 \ 2 2\ 1\~ 1 H(A) = L g(t)y (t) = Lg(t)y (t)- Q ~~(t)y(t) + ~ ~ -grt) + Q tED tED tED Q tED 2 1 1 1 =\~ srtT (g(t)y(t) - ~(t) QJ + Q. tED Therefore min H(A) = 1/Q and this minimum is attained if and only if y(t) = ~f~~ . But in view of (2.12) that is equivalent to •(d) n llil \ = Q ~(t/d))(t) - f(d)~J,(d) \ s(t Q L grty · tED tED dlt dlt L 25 (2.17) THEOREM. If Q and A are those of Theorem 2.13, then L IA(d1 )A(~)R( [dl'~]) I· S(A,P ,n) S ~ + {2. 18) d ,d ED 1 2 For D = (d: din, ~z) this leads to 2 S(A,P,n) ~ ~ + z (2.19) ~: 1 IT {1 - fGJ) -2 pEP . Relation (2.18) follows immediately fran (2.7) and (2.14). We thus only need to prove that (2.20) By Theorem 2. 13 \L g{t} <- S{dJ ~ .!. \ = ilil IA(d) I -- fill. Q Q L gnJ SfcfY 1 tED 1 6ED dlt since g{t) > 0 and g is multiplicative. f(k) sk [dt'~] d1~ IR([d1'~l)l s f([d,,~l) = {d,,~) Hence (2.21) Also, by {2.4) and the fact that 26 ITC1+b), L ~~ g\U.J pEP g,p, dED (2.22) Q= \ and 1 1 1 + g1P) = 1 + f[p)-1 Thus RSz2 ___!_(Pl_ 1 -1 = ~ = (1 - f{P)) • rr < -rr=' , . pEP >-2 1 .L\PJ This finishes the proof. In the proof of Theorem 2.17 we could have combined (2.18) with (2 .21) to obtain n 2 2 S(A,P,n) S Q + z Q • The reason we replaced the Q in the second tenn above by a. simpler expression (simpler than the expression defining Q1 that is) is that 2 2 the size of z Q is determined mostly by z, and we do not lose much by using the estimate (2.22) for Q. however, for the main tenn. The size of Q is critically important, The main difficulty in the applications we will be discussing in the next chapter will be in finding a. good lower bound for Q. 27 Notes on Chapter 2. An obvious way to generalize the results of this chapter is to drop the restriction that the a v be generated by a polynomial. the only place where we used this property of the a (2.3)· v In fact, was in proving If we were to start with some general sequence {a } and defined1 v say, R(d) = L1 - :t(d) v<n dTav satisfying 1 < f(p) S p for all for sane multiplication function f pEP, then Theorem 2.13 and the inequality (2.18) would still be valid (with the R(d) defined as above). Whether effective use could be made of these results would then depend on whether the function f can be chosen so as to make the second tenn on the right side of (2.18) small, which would be equivalent to making R(d) small on the average. in fact, be done for many sequences. This can, Perhaps the most important cases are those of values of polynomials at primes. Going back to the example of twin primes that was treated in Chapter 1, we could, instead of taking = (2n-1)(2n+1), consider a v p v + 2, where pv is the v-th prime, with v = 1, ••• , n = ~(x) for sane x. Then we would have a c v L = 1 l(p; p S x and p + 2 50 (mod d)ll = ~(x,d,-2). v<n dlav It would then be natural to write for d odd L = ~f~~ (~(x,d, v<n 1 djav + -2) - ~f~~). 28 (Notice that we are not literally following the suggestion at the beginning of this note.) In place of (2.7) we would then obtain (with 2 ~ P) S(A,P,1t(x)) ~ U(x) I ~f~~ + I >.(d){1t(x,d,-2) - ~~~~). din din We could then apply Theorem 2.13 and obtain an inequality analogous to (2.18); namely S(A,P,1t(x)) ~ U~x) + I d 1 ,~ED IA(d 1 )A(~}(1t(x,d,-2) - ~f~~ J I where the Q and A are defined in Theorem 2. 13. sieve becomes very useful. It is here that the large Through results such as Bombieri's theorem (Chapter 8), which says that the terms 1t(x,d,-2) - t~~~~ are small on the average, it enables us to conclude that the second tenn above is small. For further discussion the reader is referred to Richert (3). 29 3 APPLICATIONS OF SELBERG'S SIEVE This chapter discusses applications of Selberg's sieve. Our notation is the same as in Chapter 2; that is, we will work with a sequence A= (a ) given by a v polynomial. v = h(v),where h is an integer-valued N(d) will denote the number of solutions of h(v) :: 0 (mod d) for v = 1, ••• , d, P will be a set of primes such that p ~ z and 0 < N(p) < p for all p E P, n = 1TP, f(d) = N(d) for din. pEP We seek estimates of S = S(A,P,n), the number of elements of (a 1, ••• ,an) which are not divisible by any pEP. Theorem 2.17 then states t~~t s < !!. + z 2lT (1 -f"=' 1 ) -2 ' (3.1) -l'\ pEP ~ .1. \PJ where Q = r g(d) and g(d) • r ~(t)f(d/t). din tid d<z In all applications we follow the same basic procedure; namely, choose the polynomial h, find f, estimate Q from below, choose z so as to minimize the right side of (3.1),and complete the estimate. Our first application is to primes in arithmetic progressions. We consider the polynomial h(v) = t + kv, where t and k are relatively prime integers. Then N(p) IC 1 if p'i,k, 0 if Plk· { p We define P = (p ~ z; p)k), so that f(p) c NtPJ = p for pEP. for din we obtain Hence 30 I ~ <t < t > 2:: ~ t > ~ = rr g <d > = = )f d/ tid < d <1 - ~> = cp( d >• Pld tid Since the greatest squarefree d.i visor of every natural number d ~ z which is relatively prime to k divides rr, we find ( 3·2) I d 1 >> d<z (d,k)=1 To estimate the last sum, we use the following result: (3.3) LEMMA. For y ~ 1 and any positive integer K we have \L m! > !llillog Y• K m<y (m,K)=1 Proof: We have 1 ( IT (1 _ lp >- ) P IK ) L m<_y (m,K)=1 l = ~IT -12 + I <1 +.!.+ p m K P \ L l > m- \ .!. > log y. L m ~y ~y (m,K)=1 - Hence \ L m<y .!. > log y • 1T {1 - pl) = cpK(K) log y. m- PIK (m,K)=1 Using the above estimate ve now deduce fran (3.2) that Q > !i!llog z. - k 31 Also, z 2 2 2 1 2 1 2 1 -2 2 2 lT <1 - !'-'> = z IT <1 - - > < z IT (1 - - > ~ z log z . pEP .L\PJ pEP P p~z P Therefore (3.1) now yields ~ k n 2 2 S ~ ~ log z + z log z (3.4) for z ~ 2, when the constant implied by the ~ notation is absolute; that is, it is independent of k, .t, n, and z. To minimize the right side of (3.4) 2 1 2 we now choose z = n / /log n. Then for n sufficiently large we will have z ~ 2 and log n ~ log z. Therefore we finally obtain ( 3 •5 ) k n S~ ~ cp(k) log n for n sufficiently large. We now use this resul.t to prove a Brun- Titchmarsh type estimate on primes in arithmetic progressions. Let n(x,k,t) be the number of primes p ~ x such that p =-!, (mod k). (3.6) r.mEOREM. If x and yare real numbers, k and t integers satisfying 1 ~ k < y ~ x, (k,t) = 1, then where the implied constant is absolute. ~: Let m be the largest integer such that m ~ x - y 1 m and let n "" (x-m k] , so that n ~ y / k + 1 • =-!, (mod k) Then the integers a such that 1 x - y < a. < x and a = t (mod k) are precisely m + k, m + 2k, ••• , m + nk. Since (m,k) = (t,k) = 1, we find from (3.5) that of these ~ k __ yLk _ cp(k) lOiYlk 1 2 2 are not divisible by any prime p ~ n / /log n, provided y/k is sufficiently large. But then <{ y cp(k)log(y/k) , provided that y/k is greater than again sane constant. But for y/k bounded, this result is trivie.l.ly true. (3. 7) COROLLARY. If x is a. real number, k and t integers such that 1 < k < x, (k,t) = 1, then ~(x,k,t) <{ cp(k)l~g(x/k) • ~: Take x = y in Theorem 3.6. It might be expected at first that the above estimates could be easily derived fran the prime number theorem for arithmetic progressions, which gives an asymptotic formula for ~(x,k,t). the case, however. In general that is not Even under the assumption of the very powerful (and unproved) generalized Riemann hypothesis, we could only conclude that for (k,t) = 1 33 ~(x,k,t) = ;(£)) + O(x 1/ 2 log x). 2 If x is much larger than y , for example, ( 3.8) implies only that ~(x,k,t) - ~(x-y,k,t) = O(x1/ 2 log x), while 1f k is much larger than \(X , it would only imply that ~(x,k,t) = O(x1/ 2 log x). These results are much weaker than the estimates (3.6) and (3.7) (in many cases weaker even than the estimates one obtains by considering the total number of integers n, n ·= t (mod k), that are in the appropriate interval). The main purpose of proving first the estimates (3.5) - (3. 7) was to acquaint the reader with the methods used in applying Selberg's sieve. We will now prove a very general theorem which will include those estimates as special cases. In our first application of Selberg's sieve we have considered one linear factor kv + h, while in the second part of Chapter 1 we have applied Brun's sieve to the product of the two linear factors v and v + 2. We will now generalize to the case of s linear factors a 1v+b1' ••• , a 6 v+bs' where the ai and bi are arbitrary integers. More specifically1 we will obtain upper estimates as to how often all of the factors laiv + bil are prime at the same time, and then will apply these estimates to several important problems of number theory. To obtain the desired estimates we will consider h(v)"" {a 1v+b 1 ) (as v+ b s ) • To avoid the case where one of the linear factors of h has a constant prime divisor we will require that a 1 ~ 0 and ( ai, b ) = 1 1 for i "" 1, ••• , s. More generally, we will require that h as a whole ... should not have a constant prime divisor; that is, we will require that N(p) < p for all primes p. (A non-trivial case when this condition is violated is given by h(v) = v(v+2)(vt4). Here N(3) = 3, and therefore 3, 5, 7 is the only prime triplet of the fonn p, p+2, p+4.) Verifying t hat this condition is satisfied is quite easy, since N(p) S s for all primes p (as will be shown in Lemma 3.9), and therefore only the primes p ~ s have to be checked. Finally, we will require that aibj - ajbi ~ 0 for i ~ j 1 since we would not get any additional infonnation by allowing one of the linear factors to be a multiple of another (in view of the requirement that (ai,bi) = l, the only way a bj - ajbi = 0 can happen is 1 i f aiv + bi = ±(ajv .+ bj)). Our next step is to estimate N(p) for a prime p. ( 3.9) LEMMA. We have N(p) S s for all primes p. Moreover, N(p) < s i f and only i f pIE, where Proof : Let p be a fixed prime. Consider any linear factor a v + b • 1 1 If p lai, then (3.10) has no solution, since (a ,bi) = 1. 1 one solution for v = 1 1 ••• , p. If Plai' then (3.10) has exactly Since h(v) =0 (mod p) implies that (3.10) holds for same i, and (3.10) has at most one solution for each i, we must have N(p) S s. 35 Let us now investigate the conditions under which N(p) < s. have already seen that this happens i t pI a 1 for sane i. We Another (and the only remaining) way this can occur is if two of the linear factors are divisible simultaneously by p; that is, if there are i,j with i ~ J such that and ajv + bj e 0 (mod p) for sane integer v. However, this occurs i f and only if Pl(aibj- ajb ). 1 This finishes the proof. We define P = (p ~ z; N(p) ~ 1) to be our set of sieving primes. Then n = Tfp, and S = S(A,P ,n) is the number of positive integers p~z N(p)>o m < n such that none of aim + bi for i = 1, ••• , s is divisible by a prime p ~ z. As in the previous application of Selberg's sieve, main task will be to estimate Q = E 1 din g{d} our fran below. d<z Let P · k = Tf p for k = 0, 1, ... , s-1. We write each natural p<z N(p)=k number m as m = m TT p p; that is, m will be the exponent of p in the Plm prime power expansion of m. P 1 We also define m( ) = lT m p P, for Plm N(p)=i i = o, .•• , s 1 so that m = m(o) m(l) ••• m(s), where plm(i) if and only i f plm and N(p) = i (and m(i) = 1 if there are no primes p such that plm and N(p) • i). If k is a positive integer such that kiiT (and thus k is squarefree), then g(k) = f(k) I ~(d) f(d) f(k) 1T (1 - f(p)) = dlk Pl.k = N(k) pTflk (1 - !ili?J.). p Therefore, since n is the product of all primes ~ z which do not divide (3. 11) Q= I g(d) L Nid) 1T (1- ~)-1 = din d<z din d<z PI d - - = L IT (~ rf~p) + dlnPid d<z + ••• ) P -1 TT (N(p))dp d PI d Let us now define dt(m) for positive integers t,m to be the number of representations of m as a product of t positive integers, where two such representations k 1 ••• kt and k{ ·•· k~ are to be regarded as 37 identical only if ki = k~ fori= 1, ••• , t. (Thus, for example, 2·2·3 and 2·3·2 would be regarded as different representations of 12.) It is clear that for a fixed t, dt is a multiplicative function. proof: The lemma is true for t = 1 , since d (pa) = 1 = 1a. 1 it is true for t. Since each product of t + 1 factors Assume that is a product of one factor with the product of the remaining t factors, we obtain dt+l(pa) = I dt(pb) ~ L tb ~ (t + )a. 1 o<b<a o<b<a Hence the lemma is proved by induction. (3.13) LEMMA. I ~ i=IT ~z (m,P )=1 0 1 1 Proof: Let be a term appearing in ki Then k i = k(i) k(i+l) ••• k{s) i i i • From the following array k 1 = k(11 ) k2 = (3. 14) k(2) 1 k(3) ..•••....• kl( s) 1 k(2) 2 k(3) •••••••••• k2(a) 2 k(3) •••••••••• k3(s) 3 k3 = (2) m (s) • • • • ••• • • • m we see that if m = k 1 k 2 ••• ks' then (3.15) Now ki ~ z m(i) = k~i) 1/s k~i) •••••• k~i) for i = 1, .•• , s. Likewise, (ki 1 p 0 ) = 1 for all for each i, and s~ m ~ z. i implies (m,P 0 ) = 1. of the tenm k k 1 1 ~if we expand the k 2 ••• right side of (3.13), each 1 s will be equal to some tem. - on the left side. m Moreover, it is apparent from (3.15) that a given m appearing on the left side of (3.13) cannot be represented as k 1 ••• ks in more than d 1 (m( 1 )) ••• d (m(s)) ways. Hence the inequality (3.13) is valid. 6 The remainder of our worlt is now very easy. 3.12 we obtain -1 IT (N(p))mp = m PI m m IT <it<P P). Plm N(p)r::k From ( 3. 11 ) and Lemma 39 But dt is a multiplicative function for each fixed t, so > s I Tf i:: 1 k<z1/s (k,P0 ~•• Pi_ 1 )=1 utilizing Lemmas (3.13) and (3·3 ). Since E and P0 ••• Ps_ 1 have the same prime f&ctors,we find Q> ( - log z)s 6 - 1 s TT TT (1 - -) 1 -s s = s (log z) I P i= 0 p P ••• Pi . 0 This is the required lower bound for Q. v( p 1 s-N(p) 1 - -) • P E To estimate the remaindei tenn we note that N(p) S s for all primes p, and therefore for s < p {1 - ~) -1 f\PJ < {1 - !)- 1 < (1 - l)-s. p - - p If p S s, then N(p) ~ p - 1 {since N(p) < p for all p), and so -1 1 (1 - f1P}) MI ..... \ -1 = (1 - ~) S P· Hence 1 -2 -II (1 - f(p)) = lT (1 - ~> PEp pEP PSS -2 f\PJ ·pEP IT (1 s< p 2 t )-26 s (\><s lT p) . ( lT {t - p-) pEP - s<p 40 2) ( 1 )-2s s. \ IT P • IT <1 - -> S. s PS. z p S. c '(log z )2s for z ~ 2, where c 1 is a constant depending only on s. From (3. 1) we now obtain s s < ----~s----~~ s-N(p) 1 ff(l--) PIE z > 2. p 1 z = n / 2 (log n)-28 , then we find that If we now choose (3.16) n + c 1 ·z2 • (log z )2s for (log z)s -~=---- S < c • (s) - 1 IT (1 - -) pIE -s+N(p) p n (log n) 6 for n sufficiently large (bound dePending on s only) and c • a function of s alone. Because of its definition, S counts all those v for which none of the factors aiv + bi is divisible by any prime S. z, but it does not count those v for which each of laiv + bil is a prime if at least one of them is < z. However, for a given linear factor aiv + bi' laiv + bil S z has at most 2z + 1 solutions. Hence the total number of v such that laiv + bil is a prime for 0 = 1, ••• , s which were sieved out is Ss(2z+1). Wenowobtain (3.17) THEOREM. Lets be a positive integer, and suppose that for 41 s E = IT ai ·IT (aibj- ajbi) ~ 0. i=1 i<j Let N(p) be the number of solutions of (a 1v + b 1 ) ••• (a v + b ) ~ 0 - (mod p) for v = 1, ••• , p 5 8 prime p, and assume N(p) < p for all primes p. for each Then the number of positive integers m ~ n such that each of laim + bil (i = 1, ••. , s) is prime is < c(s) Proof: 1 -s+N(p) n 6 • lT (1 - p-) (log n) PIE For n larger than a certain bound ( depending only on s) this follows fran (3.16) and the remark preceding the statement of the theorem. But for n bounded it is trivially true! We can make a few simple deductions fran this theorem. (3.18) COROLLARY. The number T(x) of twin primes S x satisfies T(x) ~ Proof: x 2 (log x) Take h(v) = v(v + 2). p since N(2) for x > 2. Then lEI = 2 and N(p) < p for all primes = 1. Hence the number of primes p S [x] such that p + 2 is also a prime is < 2 c(2) - [x] 2 , (log [x]) and this implies the corollary. It has been conjectured that there are infinitely many primes p such that p + 2, p + 6, and p + 8 are also primes, but just as in the case of twin primes nothing is known for certain. The next corollary, how~ver, gives an upper bound for their density. (3.19) COROLLARY. The number of primes p S x such that p + 2, p + 6, and p + 8 are also primes is ~ Proof: x 4 for x > 2. (log x) Take h(v)= v(v + 2)(v + 6)(v + 8). N(2 ) = 1, N(3) = 2, proving N(p) < p 2 Then lEI = 29 ·3 , and for all primes p. For our last application we will consider the number of representations of an even positive integer as a sum of two primes. If Golbach's conjecture is correct, then this number is always positive (except for 2 and 4). We are going to give an upper bound for it. (3.20) COROLLARY. Let a be a positive even integer, and let T(a) be the number of primes p such that a - p = q is also a prime. T(a) ~ Proof: a Tf (1 + l) 2 (log a) pI a P Then for a > 2. We consider h(v) = (v + 2)(a- 2- v) for v = 1, ••• , a-5· lEI =a, N(2) = 1, and in general N(p) = 1 for pia. The corollary follows easily from Theorem 3.17 for a sufficiently large, and it is trivially true for a bounded. As an important application of the above estimates we will now prove the following important result. 43 (3.21) THEOREM. There is a constant c such that every integer~ 2 can be represented as a Proof: sum of not more than c prime numbers. The basic idea is to prove that the integers representable as a sum of two primes, Schnirelmann together with 1, form a sequence density. of positive The theorem will then follow by virtue of well- known results on addition of sequences. Let n 1 denote those integers that can be represented as a sum of two primes. Then by the Cauchy-Schwarz inequality n<x n<x n'<x Now I T(n) ~ I, = Jt (~) ~ (logx x) for x > 4. 2 2 2 n<x P,+P2Sx P,P2Sx/2 Also, by Corollary 3.20, we have In<xT(n) ~ (logx x) 4 n<x I pITI n (1 + -)P 2 < X 2 (log x)4 X 2 < ---T'"4 (log x) 1 2 , I I (I 1 n<x n=O(mod[d 1 ,~]) n<x din 1 d 1 ~[d 1 ,~l 2 + _...;.x.;..._--r- (log x) 4 In the second sum above we use the fact that each k ::: x can be expressed as [d 1 ,~] in at most k ways, and each such expression contributes 1 d ~ 1 1 ::: k to the sum. Therefore that sum is < x. In the first term we sum over k = (d 1 ,~) to find ~ d1'~ 1 1 ~ d ~t! ,~J = ~ k<x 1 1 : : I ~ k3 r}&2 (d1~)2 k<x ,& :::x 1 2 k 61 d1,d2 [d 1 ,~J:::x [d 1 ,~J:::x 2 (6,,62)=1 k=(d1'~) 1 \) ( ~ 2) ~ k<x k &<x ~ (I 2 6 1. Therefore '\ L 2 T (n) ~ n<x x3 4, (log x) and hence we find fran (3.22) that ( t T(n) )2 > n<x 2 E T (n) >x for x > 4. n<.x This implies that the sequence consisting of 1 and the numbers representable as a sum of two primes has positive Schnirelmann density, and therefore every positive integer is the sum of ::: c I c • , primes and ones, for sane constant To prove the theorem we have to show that given m ~ 2 there is a representation of it which does not involve ones. m = 2 or 3. Suppose therefore that m > 4 and that This is clearly true if 45 m - 2 = L1 + L pi for sane ~ c' C i<k 1 k<i<c is a representation of m - 2 that we have proved exists. If k = 1 or 0 1 then we write m= 3 + L pi' or m = 2 + \L p 1 , 1<i<c i<c respectively, and if k > 2 then we write the k ones as a sum of ~ k/2 twos and threes 1 and obtain m =2 + I + I 3 + I pi • 2 k<i<c In any event we have found a representation of m as a sum of < c' + 1 primes, and this canpletes the proof. 46 Notes on Chapter 3. The presentation of this chapter largely follows Prachar [ 1; Chapter 2], who also gives several additional applications of Theorem 3.17. problem which is dealt with neither One in Prachar's book nor in this chapter is the explicit determination of constants in the inequalities above. The next chapter, on the other hand, will be denoted entirely to obtaining the best estimates of the Brun-Titchmarsh type that are known so far, with particular attention being :paid to the constants and the relat"ive sizes of the main tem and the remainder. However, it has been found in many cases that the upper bounds given by Selberg's sieves are several times larger than either the asymptotic estimates obtained thr01.gh analytic method.s (where these exist) or the conjectured asymptotic estimates. As an example, it has been conjectured that T(x), the number of twin prime pairs S x, satisfies T(x) ,.,. 2C X (log x) 2 as x -+ co, where c = TT p~ 3 <, - , 2 >· (p-1) (For heuristic arguments supporting this conjecture see either the original paper of Hardy and Littlewood [ 1], or Hardy and Wright [ 1; Chapter 22], or Golomb [1].) The best upper estimates obtained so far are asymptotic to 8C x • It is not clear how far this bound can be lowered. 2 (log x) Selberg [2), [3] has actually proved that his sieve is in general incapable of giving the exact constants. 47 Material on the Schnirelmann density and the addition of sequences can be found in Niven and Zuckennan [ 1] , Halberstam [1; Chapter 1], or Gelfond and Linnik [1; Chapter 1]. and Roth It is easy to see from the proof of Theorem 3.21 that we can obtain a numerical value for c. This was actually done by Schnirelmann [ 1] in his original proof (in which, however, he used Brun's sieve, since Selberg's method was not known at that time), but his value was very large. many subsequent improvements Shapiro and warga 3.21 holds with c = 20. meantime I. M. Virogradov After [ 1] showed that Theorem (It should be mentioned, however, that in the [ 1] had proved that every sufficiently large integer is a sum of at most four primes.) 4 PRIMES IN ARITHMETIC PROGRESSIONS This chapter uses Selberg's sieve to obtain new Brun - estimates of the Titchmarsh type due to Van Lint and Richert • These are the best estimates of this type known to date. (4 . 1) THEOREM. They can be stated as follows: I f x and y are real numbers, k and t integers such that 1 < k < y < x, (k,t) 1: 1, - - then (4 .2) n(x,k,t) - n(x-y,k,t) < ~(k)l~(y/k) (1 + log(~/k) ) and (4 -3) By taking x = y in the above relations we immediately obtain (4 .4 ) COROLLARY. If x is a real number and k and t are integers such that 1 ~k < x, (k,t) = 1, then (4 .5) 2x n(x,k,t ) < ~(k)log(x/k) (1+ 8) log(x/k) and (4 .6) 3x n(x,k,t) < ~(k)log(x/k) • These results are of the same nature as those of (3.6) and (3.7). In proving the earlier estimates, however, as well as in our other applicat ions of Selberg's sieve, we absorbed the remainder in the main term 49 by appropriate choice of z. We used the ~ notation quite freely 1n t his process, without detemining the implied constants. Had we been more careful, we could have obtained an estimate similar to ( 4.2) 8 (for y/k sufficiently large, at least), but with log(y/k) in the 1 remainder replaced by c ~~g (~/£ fk) for some constant c. The improvement in the Van Lint - Richert result comes fran a very careful treatment of the remainder tenn in Selberg's sieve. An important feature of the proof is the repeated application of the sieve; first a sieve estimate is proved (equation (4.13)) with a remainder somewhat smaller than we had previously, and then this estimate is used to reduce the size of the remainder even further (Lemma 4.16). Our starting point will be, in essence, equation (2.18). However, (2.18) deals with the values of the polynomial kv + t for n consecutive values of v, while we are interested in the values of that polynomial which fall in the interval (x-y,x]. Therefore we derive first a slightly modified version of (2.18) which gives a better estimate in our case. It will be quite clear, however, that we are not doing anything basically new at this stage. Let ITI denote the number of elements of a finite set T. S = S(k,t,x,y,z,K) = l(n; x- y < n S x, n f or 1 < y S x, z > 1, (k,t) = 1, kiK, where n .. ~(z) = We define =t (mod k), (n,n) = 1)1 50 In particular, (d,k) = 1 for all din. Therefore if din, there is exactly one integer n in each residue class modulo kd such that n =t (mod k) and n =0 (mod d). Hence I ( n; X - y < n < X' n 5 t {mod k)' dIn) I c !a: + e' where 0 s. e s. 1 • Therefore, if s is a sieving function defined by (2.8), in view of (2.9) we find I 2 s (n) = I >-(d) = I >-(d) I dl (n,n) diiT x-y<nSx x-~ x-y<nSx n5t(mod k) n5t{mod k) n=t(mod k ) din <l \Mll+ \1>-(d)l -k L d L.. din din c L IA(d1 )A(~) I· ~ LAid) + d 1 ,~1n djn We again choose A to be a real-valued funct:Wn on the divisors of n such that A(1) = 1 and A(d) = 0 if d > z. 2 Then s ( n) ~ 1 whenever {n,Il) = 1, and therefore =~ 2 L ~ + (I IA(d)l) • din din - - d<z d<z 51 In order to find the minimum of the first term on the right of (4.7) we apply Theorem 2.13, where for aln we take f(d) = d and define g(d) by (2.11), so that g(d) =~(d). We then find from (2.14)and (4.7) that t he main term is minimized when I A(d) = ~(~)d tin 1 cprty ' t<z t~(mod d) where For this choice of A we obtain the estimate s ~~+ (4.8) (I lA(d) 1)2 • din d<z This is the modification of (2.18) that we have been seeking. Had we applied (2.18) directly, we would have obtained a similar estimate, but with~ in (4.8) replaced by (y/k + 1)/Q. For later convenience we define ~(x) 2 ~, X> 0. = nSx (n,k)=l n<x (n,k)=l ~ 52 Then lhl )~ ~ = cp{d) L \(x) c: diK <-J diK nSx (n,k)=1 (n,K)=d m<x/d (m,k)={m,K/d)=(m,d)=1 Since ~ (x) is an increasing function of x, 2 ~(x) =::_ L~ cp~~~ ~([) = cptK) ~(f) if (K,k) = 1. diK Therefore ~<x) = I ..:f~~ I d = I (4.9) nSx (n,k)=l djn dS.x (d,k)=l I ~:~:~~ m$;</d (m,k )c: 1 (m,d)=l Also, ( 4. 10) ~(x) = L ~ in) IT (1 2 nSX (n,K)=l pIn + -1 + -1 + • • • ) > p 2 p L -n-K > M'K' log x 1 ~ nSx {n,K )c: 1 by Lemma 3·3· We now return to the task of estimating S = S(k,t,x,y,z,K). new notation In our 53 Q= (4.11) \L b- \L ~Q_~(z) ~ - -,<;: ~\ UJ - din d<z n<z (n,K)-=1 and for din A(d) = ~~{z)) -x \ 1 \L cprty 1 -- ~~~d~d z cp(d) L~ tin uln t<z u$:1./d t::O(mOd d) (u,d)=1 (d)d = ~{z)~(d) &1 \ ~d (z/d) d L ~ c ~(d) ~ ~(z) u'5:_z/d {u,Kd)cl Therefore A(d) = 0 for d > z, and (4.12) I IA(d)l = '<tc/z) I ~2 (d) <p{d) I ~:1:l djn d<z ~/d d'S.z (d,K)=1 1 = ~(z) \ L nSz (n,K)=1 (m,Kd)=1 ~ \ ~(z) ~ Ld=uzy · cp n din ~ z Combining (4.8), (4.11), and (4.12) we obtain Sc ~(z) S(k,t,x,y,z,K) ~k~tz) + ~(z) . ~(z) 2 Equation (4.9) implies that (~(z)) (4.13) S z2 • Hence 2 S(k,t,x,y,z,K) S.k~(z) + z . · 54 This already represents an improvement over the estimates of Chapter 3, 2 2 when we knew only that the remainder tenn was ~ ~ z (log z) • It turns out, however, that the bound on the remainder can be reduced still further. We will carry out this reduction (which will use (4.13) in a very important way) in the next two lemmas. (4.14) LEMMA. If p(k) denotes the greatest prime divisor of k (with the convention p( 1) = 1), then for x ~ 103 and p(k) ~ x we have L < ;5 S!(~) x. Tk(x) = 1 nSx (n,k)=1 Proof: Let z satisfy 1 < z < x and define and K = IT p • p,S z p~k Then Tk {x) = S{1,1 1 x,x,z,K). 1 Therefore by (4.13) and (4.10) Tk (x) ~ 1 1 log z 1 - -) p< z p X IT ( 2 + z • p{k Now k 1 1k implies that ~(x) ~ Tk (x), and thus 1 Tk(x) ~ X 1 log z IT (1 - -) pS z P p~k 2 + z . 55 Since p(k) < x, we have It is known that for x > 1 Tf (1 - .!_ f 1 S e y log ( 2x) , (4.15) PSX p where y is Euler's constant, and therefore by taking z = (2x) l/3 we find T(x) k < ey( 3 + 2 ~ lo 2x) • ~ x (2x)1 3 k By considering its derivative, we find that the expression on the right decreases for 2x > e 3 , and for x = 103 it is< ~5 . We might remark here that for a fixed k, Tk(x) is asymptotic to ~ x. The importance of Lemma 4.14 canes fran the fact that it holds even when x is small, and that it gives a constant valid for all k and x satisfying the hypotheses. since the value of The restriction p(k) S x is quite natural, L 1 is independent of prime factors of k which are nsx (n,k)=l greater than x, while ~ = TT (1 - .!_) is a product over all prime PI k f actors of k. P Without the restriction p(k) S x we could take a sequence of values of k such that (for a fixed x) Tk(x) would be constant, while ~ would tend to zero. 56 (4.16) LEMMA. ~: For z > 103 and h even Define 2 2( ) a (n) ~ n 2 • cp (n) n<z (n,h)=1 Then by the Cauchy-Schwartz inequality (4.17) Since both a and ~ are multiplicative, we have for squarefree n a2(n)- IT 2 ~ (n) pI n (1 + {p+1)2- IT 2 (p-1) pI n 4p ) \ 4v(d)d 2 = L 2 ' (p-1) din cp (d) where v(d) is the number of distinct prime factor of d. Now h is even, and therefore (4.18) = )L dS:l ~ 2 4v(d)d (d) ~2_...:;:. ~ (d) 2 1.1. (m) (d,2)=1 \ 2 4v(d)d ::: z L ~ (d) = z lT ( 1 + 4 2) < -16 z, 2 (p-1) 5 d<z cp (d) p> 2 (d,2)=1 57 since TT <1 + p 4 2 ) = 15 • 9396. . . . (p-1) Combining (4.10), (4.17), (4.18), and Lemma 4.14 we obtain (z) .!2 • ~ • z • ~ z 2 -_n_ < 2 h 5 _ 24 h . _z-=-2 ~2(z) ~ (h) 1og2 z ~ log2 z ~ 2 K 2 ' h provided p(h) S z. But both Hb(z) and ~(z) are independent of those prime factors of h which are greater than z, while ~(h) is increased by them, so that the above inequality is true even when p(h) > z. Proof of Theorem 4.1: Let 6(x,y,k,t) = n(x,k,t) - n(x-y,k,t). Since for odd values of k the positive integers n such that n =t (mod k) are alternateiy even, and at most one of the even tenns can be prime, we will reduce the proof to the case of even k. h ={ More k if k even, 2k if k odd • precisely, we define Then for a suitable t 1 we will have 6(x,y,k,t) S6(x,y,h,t 1 ) + 1. Since S(h,t 1 ,x,y,z,h) counts at least those primes p which satisfy x - y < p S x, p > z, and p !I t 1 (mod h ) 1 we have 6(x,y,k,t) S S(h,t ,x,y,z,h) + n(z,h,t 1 ) + 1 for z > 1. 1 58 Therefore by (4.13) we find (4.19) We define If we take z = 2 in (4.19), then 6(x,y,k,t) ~ * + 2 ~ ~ + 2 =u 2 + 2. Therefore if' W = cp(k)l~~(yJk) 6{x,y1 kt), we have W < log u(.!. + g_) < 1 for 1 < u < e 2 ·9 . 2 2 2 u Also, since \L n(z,h,t 1 ) + 1 < ~ 2(m) ~ -z -- 1 for z ~ 10, 2 m<z (m,2)=1 we find frcm ( 4. 19), ~. 10), and ( 4. 9) W < log u f __ j - 2 U:Og z + z } 42 u Defining v by v ev u =- ./2 we choose z • ev • for z > 10. 59 Then (4.20) w < Log(v/J2) + v (1 + -1 } for v > log 10. - v 2v By examining the derivative - of the function on the right we find that it decreases for v ~ .j2e (j2e > log 10) 1 and for v = j2e it is<~ • This proves (4.3)· It remains to prove (4.2). Since ~(h)= ~(k), (4.10) implies that ----X-< y h~(z) - C9(k)log z · Also, ~(z,h,~ 1 ) + 1 ~£ + 2 ~ C9(k) z Combining these inequalities and Lemma 4.16 for z > 2. (his even) with (4.19) we find that for z > 103 (4.21) < log u { ~g u - 1 + 48 log u og z u2 z 2 2 log z + Choosing log z = log u - 2 we find that the right side of (4.21) is log u I 2 + 48 • liog u-2 4 e log u + 1 g u } 2" • (log u-2) e u 2 log u u 2 60 This function is decreasing in u, and for u = e proves (4.2) for u > e from (4.3). If e 10 • 10 it is < 4, which 8 If u S e , then (4.2) follows directly 8 < u < e 10 , then we use (4.20). It says that, in that range, we have w < 1 .4 < 1 + -log4- u ' which is the desired estimate. 61 Notes on Chapter 4. The presentation of this chapter follows closely the original paper of van Lint and Richert [1]. The only significant modification was made in the first p:l.rt in order to show the connection with the general theory of Selberg's sieve. The inequality (4.15) follows ~ediately from the inequality (3.30) of 1 Rosser and Schoenfeld [1] for x ~ e 10g 2 • For x smaller than this bound it is easily verified directly. A large sieve estimate very similar to the one presented above has been recently obtained by Bomhieri [4]. He showed that (4.2) holds with 0(1) in place of the 8 in the remainder term. 62 5 GALLAGHER Is SIEVE Both Brun 1 s and Selberg 1 s sieve methods are applicable only to a relatively small class of sequences. In particular, only a relatively small number of residue classes modulo each prime can be sieved out of a sequence of consecutive integers. However, it is often desirable to find estimates for the case in which a large number of congruence classes is sieved out modulo each prime; for example, to investigate the density of integers which are not primitive roots for any prime in a given set, one would sieve out the ~(p) residue classes of primitive roots modulo each of those primes p. Linnik's large sieve was invented, as its name suggests, especially for dealing with such problems. In its most refined form it is applicable to all integer sequences, and it gives upper bounds similar to those of Selberg's sieve where both methods can Chapters 6 and 7 will be devoted to an exposition of the large be used. sieve. This chapter presents a new and very elegant sieve due to Gallagher. Although very elementary, it is larger than the large sieve in the sense that it gives better results than the large sieve when the number of residue classes sieved out is very large. We consider the case in which all but g(q) residue classes modulo q are removed for a given set of prime powers q. can be stated as follows: Gallagher's basic result 63 (5.1) THEOREM. LetS be a finite set of prime powers, and let W be a subset of {M+1, ••• , M+N} (M and N any integers with N > 0) such that for any q inS all elements of W fall into at most g(q) residue classes modulo q. If Z = lwl (the number of elements of W) then I: A(q) - log N Z < q.._ES~-r--r----­ - I: log N (5.2) Mil - qESg-cq} provided the denominator is positive*). Proof: We define, for each q in s, Z(q,h) = I{n; n E W and n := h (mod q)} I· As we will see in Chapter 6, the function Z(q 1 h) arises quite naturally and plays a very important role in the large sieve method. q For any given in S we have q-1 z = L Z(q,h) h=O and therefore by applying the Cauchy-Schwarz inequality and the fact that at most g(q) of the Z(q,h) are nonzero we find that q-1 z 2 = ( 2 q-1 L z(q,h)) ~ g(q) L(Z(q,h) ) h=O 2 • h=O Q *) Mangoldt • s A-function is defined by A( q) = log p i f q = p for same prime p and same a> 1f and A(q) = 0 otherwise. One of its basic properties is that I: A(d) = log 1nl whenever n ~ o. din 64 Multiplying by ~(~~ and summing over s, we get (5.3) Now 2 (Z(q,h) ) = ( 1 • new n,m E W n,m=h(md q) n eh(mod q) Therefore (5.3) implies q-1 2 Z IqES ~~~~ ~ qESL h=O I n,mI E W 1 A(q) n,m E W n=m(mod q) n,mEh(mod q) = I (I ldl~ 1) . ( IA(q)) qld m,nEW m-n=d qES I 1) · ( I A( q)) + I ( I 1) · log Id I =( m,nEW m=n 1Sidi~N m,nEW qES m-n=d I A( q) + (z2 - Z) • log N. ~Z qES Dividing by Z (the result is trivial if Z = 0) we obtain Z • ( I ~ - log N) S. I A( q) - log N qE s which implies (5.2) if E ~q >log N. qES grq) qES 65 We now derive two consequences of Theoem 5.1, both better than the corresponding large sieve estimates. (5.4) COROLLARY. If all but at most G residue classes modulo each prime power q E S are removed from the sequence M+1, .•• , M+N, then the number Z of remaining integers satisfies (5. 5) Z<G I A(q) > G log N 2 if q€S and I A(q) > z < 2G-1 if ( 5.6) 2G log N. q€S Proof: We can assume that G is an integer (otherwise work with [ G] ) • We rewrite (5.2) as G 1: A(q) z< qES - G log N --=-E~A~(q"""':')---G-lo_g_N_ 2 N - G log N = G + GElot h q) - G log N q6S This implies that Z < G+1 if qES E 2 A(q) > G log N and Z < G + G if q$ r A(q) > 2 G log G. Since Z and G are integers, we obtain (5.5) and (5.6), qES respectively. (5.7) THEOREM. Let € > 0 be given. Then the number of positive integers n S N for which expp (n) S Na for all primes p S N9+€ is A~ Ne for 0 < e < 1, with the implied constant depending only on €*). *) expp (n) is the smallest positive integer k such that nk E 1 (mod p) if (p,n) 1; otherwise eXip(n) ~ o. R 66 Proof: The result is clear for e = 0. Therefore we assume from now on that e > o. For each prime p S y we remove all residue classes of exponent > x. Since there are ~(k) classes of exponent k for each kj(p-1) 1 as well as the zero class (which is of exponent 0), we have I ~(k). g(p) = 1 + k I (p-1) k<x We need to evaluate E 1 . By the cauchy-Schwarz inequality we find p~ (5 .8) By the prime number theorem I as log p ,.,. y y -+ co1 P'5_y and so the right side of (5.8) is~ y 2 for y ~ 2, say. I g(p)log p = I log p I I + VSY VSY - - < cp(k)log p p<.y k 1(p-1 ) - k<x I log p + log y I ~(k)lt(y ,k, 1 ). p<y k<x By the Brun-Titchmarsh estimate (3.7) lt(y k 1) ~ y ' ' ~ ~(k)log y Also 67 1 if k +E ~ y andy~ 2, with the implied constant depending only onE· Therefore i f x > 2 and y ~ x 1+€ , we find L g(p)log p ~ y + xy ~ xy pSy and thus where the applied constants again depend only on E. e 8+€ x = N , y = N • Theorem 5.1 then We now take ays that &+€ z~ N eN € - log N where c is some positive constant, provided cNE > log N (again, the constants depend only on E). for N sufficietly large. Therefore But the result is clearly true for bounded N. 68 Notes on Chapter 5· The material of this chapter is drawn from Gallagher [ 3) • That paper contains also a comparison of the effectiveness of Gallagher's sieve and the large sieve as well as another interesting application of the above estimates. If for every prime power q,except perhaps for the powers of a finite number of primes, there is an integer a(q) such that a a for same integer a. then Gallagher proved that a = b result had been proved previously by Schinzel [1).) =ba(q)(mod q), (A somewhat stronger 6 TRIGONOMETRIC POLYNOMIAL INEQUALITIES The large sieve was invented by Linn:ik for the purpose of investigating certain sequences obtained by sieving out a relatively large number of congruence classes modulo each prime frcm a given set of primes. It wasdiscovered soon afterwards, however, that the large sieve can be applied to all integer sequences (although it gives best estimates for sequences defined by a sieving process), giving quantitive estimates as to how much they deviate from uniform distributi moduli. into congruence classes to various Moreover, the inequalities used in proving these estimates lead to important results in analytic number theory, perhaps the most important so far being Bombieri' s theorem on the average of the remainder term in t he prime number theorem for arithmetic progressions. Bombieri's theorem is discussed in Chapter 8, while this chapter develops the trigonometrir polynomial inequalities that are the basis of the large sieve method., and Chapter 7 utilizes those estimates to study integer sequences. The underlying idea of the large sieve is to relate the properties of an integer sequence to the behavior of a trigonometric polynomial. The two very basic (and very easy) properties of the exponential function which make this process possible are the fact that if n, m, and q are integers, then n = m (mod q) is equivalent to e(n/q) = e(m/q)*), and the equation q (6. 1 ) I e{a ~) = {q 0 a=1 *) We use the definition e(t) = e2Jtit if n =0 (mod q), otherwise . 70 (Equation (6. 1) follows immediately fran the fonnula for the sum of the first q tenns of a geometric progression; the common ratio in our case is e(n/q), which is 1 if n ~ 0 (mod q) and unequal to 1 otherwise). As a result, if n 1 < ••• < Dz are integers, and we define for integers q and h (6 .2) Z(q,h) = I (i; 1 ~ i ~ z, ni and =h (mod q))l z (6.3) S(x) = L e(nix), i=l then we have q s(~) = (6.4) LZ(q,h)e(h ~) h.:l for all integers a. Now i f the sequence n1 , ••• , Dz is evenly distributed modulo q (that is, if Z(q 1 h) = Z/q for all h), then by (6.1) we have S(a/q) = 0 whenever a~ 0 (mod q). If, on the other hand, all the ni belong to the same congruence class modulo q 1 then js(a/q)j = Z for all integers a. Thus the values of js(x)l at the points a/q are somehow related to how evenly the n are distributed modulo q*). 1 This fact by itself does not help us 1 since we do not have any way of estimating js (a/q)l without reference to the sequence defining S(x). It was *) Note that values of S(x) at the point a/q can be used to detennine Z(q,h) explicitly; using (6.1) we obtain q a q Z(q1 h) = E S{a/q)e{-h q). a=l 71 discovered by Linnik, however, that useful upper estimates can be ob- tained for p-1 I I (6.5) ~x a=l which are largely independent of the nature of the sequence n 1 , ••• ,nz. (It is this fact that is responsible for the great generality of the large sieve.) That the expression (6. 5) reflects how evenly the ni are distributed modulo p for all primes p ~ X can be seen best from the following identity: (6.6) LEMMA. If q ~ 2 is an integer, then q-1 ac1 Proof: q Lls(~)l = q L(Z(q,h) - ~) • (6.7) 2 2 h=1 We write out the left side, using (6.4), as q-1 q-1 q q Ljs(~)l = L (LZ(q,h)e(h ~))·( LZ(q,h)e(-k ~)) 2 a=1 = a=1 h=1 q-1 q I a=1 q = k=1 L Z(q 1 h)Z(q,k)e(a(~-k)) h,k=1 q-1 I Z(q,h)Z(q,k) ac1L e(a(h-k)). q 72 Now by {6.1) we have q-1 L e{a h-k ) = { ( ) q if h ~ k {mod q), q-1 _, otherwise. a.=1 Therefore q-1 \ q a q I (Z(q,h)) - I Z(q,h)Z(q,k) 2 2 L ls(q)l = q a.:l h,ko::l q I (Z(q,h))2 ::;: q h=1 q =q I<z(q,h))2 h=l 2 q = q I (Z(q,h) - ~) . h=l Using the above lemma, we can now rewrite (6.5) in the form p I p L p~X h=l (Z{p,h)- ~) z2 p The so-called "variance" ~l {Z(p,h)- p-) from an even distribution modulo P• 2 • shows how far the ni depart Our upper bounds for (6 . 5) vill enable us to conclude that i f the ~ are sufficiently deue, then they cannot be very unevenly distributed modulo many prtme~. This will mean that if we start with a sequence that is unevenly distributed, then 1t cannot contain many elements. of the ni fall into any of As an example, suppose that none f(p) residue classes for each prime p ~ x. 73 Then Z(p,h) = 0 for f(p) values of h, and therefore p z 2 =( p 'i Z(p,h)) s_ (p- f(p))· L(Z(p,h))2 2 h=1 by the cauchy-Schwarz p h=1 inequality. 2 p L(Z(p,h)- ~) = L h=l But then p 2 (Z(p,h) ) ~ h=1 'i Z(p,h) h=1 and therefore 2 Since we will prove that the left side is ~ (N + x )z for N = nz- n 1 + 1, this will give the estimate (6.8) The above discussion demonstrates how sums of the form (6.5) can be used to study integer sequences. The next chapter will be devOted mainly to proving modifications of (6.7) and (6.8), while the rest of this chapter will deal mostly with estimates for sums similar to (6.5). We will work with trigonometric polynomials more general than those defined by (6.3), and we will estimate sums of values of ls(x)l 2 more general than (6.5). These generalizations are necessary for the analytic number theory applications of the large sieve, and they do not cause any material 74 difference in the proofs. It turns out that the crucial feature of (6.5) 2 is that it is a sum of ls(x)l over points x which are well-spaced; that is, if a/p and b/p' are two distinct points which appear in the sum (6.5), then I ~P _bprI = lap'pp'- bpi >- PP'1 >- X_12 • We will work with trigoncmetric polynomials of the fonn K S(x) = (6.9) I an e(nx), n=-K where K is a positive integer and the a n are any numbers, real or complex. If x 1 , ••• , ~ are real numbers satisfying*) (6.10) then we will obtain several estimates of the form R K Lls(xr)1 S D(K,6) I lanl 2, 2 (6.11) r=1 n=-K where D(K,6) will be functions of K and 6 only. The restriction that S be of the symmetric form (6.9) is only temporary, imposed to facilitate our proofs. Estimates for trigonometric polynomials of the fonn M+N \- a L n n=M+1 e(nx) will follow easily from estimates of the form (6.11). *) We denote by lltll the distance fran t to the nearest integer, so that lit II = min It -n I • n 75 Our first estimate is a beautiful result, on the lines of Linnik's original work, due to Gallagher. Its basic idea is to relate the sum R Lls(xr)l 2 (6.12) 1 to the integral I ls(x)l 2dx. Since the exponential function satisfies 0 the relation 1 I0 (6.13) { 1 if n = o, 0 otherwise, e(nx)dx = for integers n, we have 1 (6 .14) I 0 2 ls(x) 1 dx c 1 1 0 0 K I S(x)S(x)dx = I \L anma e( (n-m)x)dx n,m::-K K I = n=-K The sum (6.12) is related to the integral (6.14), and in fact, if Sis kept fixed and the xi are evenly spaced (say xr = ra for r = 1, ••• ,R 1 with 5 = R) then R L 5IS(xr)l I'l= 1 1 2 -+ I0 K 2 ls(x)l dx = L 1anl 2 as R-+ 0). n=-K 2 (This shows why one might expect 5-lE Ia 1 to appear in our estimates n of (6 .12).) x r In general our situation is different, however, since the and R are fixed, and therefore we cannot argue using limits. we will use is our knowledge of s'(x). What Since values of S(x) in a neigh- borhood of xr are detennined by S(xr) and values of s'(x) in that 76 neighborhood, we will estimate (6.10) in terms of the integral (6.12) and a function of s'(x), and then complete the estimate. (6.15) THEOREM. ••• ,~are real If S(x) is defined by (6.9), and x 1, numbers satisfying (6.10), then R K I ( 6. 16) 2 IS ( x r ) 1 S. (5- \ I 21tK) n=-K Proof: Since for any u 2 2 s (xr) = s (u) + xr s'(t)S(t)dt, 2I u we have X ls(xr)l 2 2 S. ls(u)l + 21 I rls'(t)S(t)ldtl· u We now integrate this inequality over the interval I r = (x r - 2 x + 2) 2' r 2 to obtain X ols(xr)1 2 s. 2 II ls(u)j du + 2JI r Now x I Iurls'(t)S(t)ldt,du. r 6 J II x+2 u rls'(t)s(t)jdt,du = r ( I ls'(t)s(t)ldt)du r r I J U X X + = Ix +£ 2 r X r I r 6 ( I ls'(t)S(t)ldt)du xr- 2 X .~ X u X r r s. ~I ls'(t)s(t)ldt Ir r ls'(t)S(t)l(xr+~- t)dt + [ _ ~ls'(t)S(t)l(t-xr+ ~)dt 2 77 a.nd thus 6IS(x )1 (6.17) 2 r S. J ls(u)l 2du + 6I I I r ls'(t)s(t)ldt. r Since by (6.10) the intervals Ir are disjoint modulo 1 (that is, if r ~ s then no point of I r differs by an integer from a point of I ) the integral of s any positive function over the I will be not larger than the integral of r that function over [0,1], provided that function is periodic with period 1. Since Sis periodic with period 1, we find by summing (6.17) over r that 1 + The first integral is K 6I0 ls'(t)s(t)ldt. 2 Ia I . The second satisfies t n=-K n 1 1 1/2 1 I0 ls'(t)s(t)ldt S. ( J0 ls(t)l dt) (I0 2 2)1/2( Ian I K =( I n=-K n n=-K L lanl2 n=-K since K s'(t) = I 21tinane(nt). n=-K 1/2 IK I2Jrna I2)1/2 K S. 2~ 2 ls'(t)l dt) 78 Hence R s K I ls<xr>l ~ (1 + o211K) I lanl 2 , 2 n=-K which completes the proof. We will now give two other estimates which were found by Bombieri and Davenport. The basic idea here is to write S(x) as the convolution of two appropriately chosen functions, so that the value of S at any given point is defined by an integral over a neighborhood of that point. The proof is much more camplic&ted than that of Gallagher's estimate, but the results that follow from it represent an important improvement in some &pplications. (Note, however, that for some values of Ko the estimates below &re weaker than Gallagher 1 s. ) First we prove our auxiliary result. (6.18) LD!MA. For x > 0 we have 1 <-. X Proof: We use contour 1_ -2i Jco eit _ e -it X t integration. The integral is eix Jco eit e -:ix Jco e -it dt = dt - dt. 2i O X+t 2i O X+ t eiz Let us take r > 0 and consider the integral of over the path conx+z sisting of (a) 0 to r &long the x-axis, (b) r tori &long the eircle lzl = r, (c) ri to 0 &long the y-axis. 79 Since the integrand has no poles inside the path of integration, the integral is zero. r Thus it 0 I ~+t dt + iJr 0 ire 19 e iQ d9 = o. x+re I ~ 2 -t x:it dt + ir I 0 2 ~ Now sin 9 ~ i 9 for 0 s_ t S, 2 , and therefore n/2 \iri 0 ~/2 ireie -r sin e e..;;.._ _ _ _ e ie de\ S ri x+re 0 de r n/2 - g er S. I0 e ~ d9 Hence it ~ -t ~ Io ~+t dt = iio ~+it dt. -it Similarly we can move the integral of :+it to the negative imaginary axis to obtain it iJ 0 x~it dt. Therefore II si~ ~ X ll t dtl = 2 eix I~ e -t dt 1 -ixs~ e -t + -2 e x-it dt 0 X+ it 0 -t -t 1 I ~ dt + 1.. I dt = - • -2 O 2 O < 1.. ~ ~ X !!___ X X I 8o (6.19) THEOREM. If S(x) is defined by (6.9), and x 1 , ••• ,~are real numbers satisfying (6.10), then R I ( 6 •20) K 2 I S ( x r) 1 ~ 2 max ( 2K, 6 -l ) I n=-K and (6.21) r=1 Proof: Let n=-K co t(x) = L bne(nx), with bn real, and bn = b -n, n=-co be a real function of integrable square such that t(x) = 0 when llxll > 6/2. Suppose also that b n t 0 for lnl <- K. Define a T(x) = bn e(nx). n=-K n K I Then 1 S(x) = It (y)T(x-y)dy 0 &/2 = I-6 /2 t(y)T(x-y)dy since 81 1 I .(y)T(x-y)dy = 0 co K m=-oo n=-K co K a b: bm L L I0e(my)e(n(x-y))dy a 1 b: bme(nx) e((m-n)y )dy Im=-oo L = 1 IO n=-K K = L a e(nx). 0 n=-K Therefore Using the fact that the intervals (x - 6/2, X + o/2) are disjoint modulo 1, r r and that T is periodic with period 1, we find (just as in the proof of Theorem 6.15) that 6/2 R 1 Ljs(xr)l S. 2( Io t (y)dy)( I 1T(z)j 2dz) 2 2 (6.22) 0 r=1 6/2 ""2( J 0 Now bn , 6/2 0 0 =I t(y)e(-ny)dy =I K 2 t (y)dy)·( Lla0 1~~ ) • 2 ~-K 0 y(y)e(-ny)dy 6/2 +I t(y)e(-ny)dy -6/2 = 2J t(y)coa(2~ny)dy. 0 82 We define 1 Y = 2 6t, ~(t) = f(y), u = K6· Then ~( t ) is an arbitrary function of integrable square, and J t (y)dy = 2 J, 6/ 2 2 1 6 0 2 ~ (t)dt, 0 1 b where s = n6. n = 6J ~(t)cos(rrst)dt, 0 Therefore for lnl < K, 1 IJ lbnl ~ 6 min ~(t)cos(rrst)dtl o<s<u 0 Therefore R I ls(xr)1 ~ 2 K 1 6- D(u) I 1an1 2 , n=-K where 1 I ~ (t)dt D(u) = sup o<s<n 2 0 IJ ~(t)cos(rrst)dtl 0 To prove the theorem it will then suffice to show that for function (6 .23) and (6 .24) ~(t) we have D(u) ~ 2 max (2u,l), a suitable 83 u ~ ~ + f2 . Case 1 : Since in this range 4u ~ ((2u) / 1 2 it suffices to prove (6 .24). 2 + 1) , We take A> u (which will be specified more exactly later) and define ~(t) = sin 1fAt t Since 00 I sin t dt _ 0 ~ - 2 ' t Lemma 6. 18 implies that X sin t dt = ~ O t 2 I J sint t dt > ~2 - l for x > o. oo X X Therefore for 0 < s < u we have - - 1 (6.25) 1 JO~(t)cos(rrst)dt = ~ Jo sin 1{(A+s)t ~sin n(A-s)t dt = .!. 2 1{(A+s) J 0 sin t dt + l which is positive for A sufficiently large. implies that 2 t Also rr( A-s) J 0 sin t dt t 84 Hence for this choice of ~(t) we have D(u) < 2). ( 1 - 2 22). 2 )-2 . 1t (A - u ) To prove (6.24) it suffices to prove that for an appropriate ). • But that is equivalent to showing that 2 We put A = u(1 + y) , with y > o. Then Thus we only need to show that (6.26) for an appropriate y. (2u) 1/2 1 (2u) / 2 + 1 1 1 <1 + y 2 2 1t uy By differentiating the right side we find that it attains its maximum when 1 With this choice of y the last expression in (6.25) is positive and (6.26) becomes equivalent to 85 2 3 2 n ~ < (~ + 1)(n~- 1), where ~ = ~ . But the last inequality reduces to 0 < n(n-2)~ 2 - (2n-1)~ + 11 and this one holds for~> 1.5, say. Since we only need to prove it for u ~ ~ + 12, which corresponds to ~ ~ 1 + 12 , the theorem is true in this case. case 2: 0 < u < 1/2. We take ~(t) = cos(nut). 1 (6.27) The derivative of 1 I0 ~(t)cos(nst)dt = I0 cos(nut)cos(nst)dt with respect to s is 1 -nJ0 t cos(nut)sin(~st)dt, which is negative for 0 < s ~ u ~ 1/2. Hence the minimum of (6.27 ) occurs at s = u, and it is 1 I cos2 (nut)dt = 21 + sin4nu2ru , 0 1 which is also equal to I ~ (t)dt. Therefore for this~ we have 2 0 Since 0 < u ~ 1/2, sin 2nu is non-negative, and therefore D(u) ~ 2, proving (6.23). (6 .28) To prove (6.24) we need to show that 2 ~ ( 1 + si~~~nu)((2u)1/2 + 1)2. 86 If u ~ 1/4, then ((2u) 1/ 2 + 1)2 > 2. Now suppose that u < l/4. From the Taylor series expansion of sin x we find that sin 2~ > 2nu - (26)3 . Hence 2 But u < 1/4 implies that ~ u < 3, so that 2 2 1I 2 2 (1 - ~ u )C(2u) + 1) > (1-u)(2u+1) > 1, 3 and therefore (6.28) is valid. case 3: i2 . In this range we have 1/2 ~ u ~ 3/2 + 4u ~ ((2u)1/2 + 1)2, so it suffices to show that D(u) ~ 4u for a suitable ~(t) . cos(~t) ~(t) = { for 0 ~t We take ~ (2u)- 1, for (2u)- ~ t ~ 1. 1 0 Then the derivative of (6.29) 1 (2u)-1 0 0 J ~(t)cos(~st)dt = J cos(nut)cos(~st)dt with res~ct to s is (2u) - 1 -~J t cos(~t)sin(~st)dt, 0 which is negative for 0 < s ~ u, and therefore the minimum of (6.29) is obtained when s = u. Therefore D(u) = { (2u)- 1 2 -1 cos (nut )dt} = 4u J0 for this choice of ~' and this completes the proof. 87 Theorems 6.15 and 6.19 apply only to trigonometric polynomials of the special form (6.9). However, we easily deduce from them the following estimates: (6.30) THEOREM. Let M+N I S(x) = ane(nx), n=M+1 (6.31) when M and N are integers, with N > 0, and the a n are any complex numbers. Suppose that x 1 , ••• , XR are real numbers satisfying Then we have R *N r=1 ncM+1 Ljs(xr)l2 S. (6-1 + JtN) L1anl2 ' (6 .32) R (6.33) I js(xr)1 2 S. 2 max(N,a- 1) r=1 and R (6 .34) n=M+1 r=1 Proof: M+N L!s(xr)j2 S. (N1/2 + 6-1/2) I janl2 • 2 Let K = [N 2], and define s*(x) = S(x) e(-(M+N-K)x). 88 Then c e(n.x), n n=-K where c n = a n+M+N- K (except when N is even and n = -K, in which case c_K = 0). To obtain the estimates (6.32) - (6.34) we apply Theorems 6.15 and 6.19 to S*(x), noting that M+N K ls*(x)l = ls(x)l, L lcnl = I 2 In such applications as Bombieri's theorem any one of the estimates (6.32) - (6.34) will be sufficient; in fact, only estimates of the form ~ (N + s- 1 )tla 12 will be used. In some applications, however, such as n those to primes in arithmetic progressions, it is inequality (6.34) that is most useful. The main reason is that we deal then with bounds of the form ( 6. 35) D(~,N) log X ' when N is the length of the interval we are investigating, X is a variable, 2 and where D(x2,N) is~+ nN if we use (6.32), 2 max(N,X ) if we use (6.33), 1 2 1 2 2 and (N / + X) if we use (6.34). By taking X= N / /log Nand using (6.34) we find that the main term of (6.35) is 2N log N • Inequalities (6.32) and (6.33) lead to similar estimates, but with 2 above replaced by 2~ and 4, respectively. 89 We now state, without proof, a more recent result of Bombieri and Davenport, which gives improved estimates when very small. N& is very large or It also shows that those estimates are essentially the best possible for the class of all trigonometric polynomials defined by (6.31). (6. 36) THEOREM. I. With the notation of Theorem ( 6. 30) we have If N& > 1, then R I ls(xr)12 < M+N (N + 5&-1) L lanl2. n=M+1 r=1 On the other hand, if c is a constant less than 1 then there exist sums S(x) with 6 arbitrarily small and N6 arbitrarily large for which R ~N I js(xr)12 > (N c6-1) L 1an12. + n=M+l r=l II. If N& ~ 1/4, then R Lls(xr)1 < (o2 M+N 1 3 2 + 270N & ) L lanj 2 • n=M+l r=1 On the other hand there exist sums S(x) With N& arbitrarily small for which R I ls(xr)12 > r=l M+N u)-1 + ~2 N3&2) L lan12. n=M+1 So far we have been considering only sums involving the exponential function. The inequalities of Theorem 6.30 can, however, be used to give estimates for sums involving Dirichlet's characters, and it is these estimates that make the large sieve a valuable tool in analytic number theory. We now present one way of obtaining such estimates. Suppose S(x) is a function of the character x defined by M+N s(x) = (6-37) I anx(n), n=M+l where, as before, M and N are integers with N > 0, and the a complex numbers. We then define the n are any corresponding trigonometric polynomial S(x) by (6.31); that is, M+N S(x) = I a e(nx), n n=M+l where M,N, and the a n are the same as in (6.37). (6.38) lEMMA. If L* Then we have denotes sumtl8tion over the primitive characters x mod q to the modulus q, then for a positive integer q we have q I ls(~)l 2 • a=l (a,q)=l Proof: Let q be a fixed positive integer. If X is a character to the modulus q, then for any integer r we define the Gauss sum q G(r,x) = I x(a)e(~). a=l 91 If (r,q) = 1, then G(r,x) is separable; that is, If x is primitive, then G(r,x) is separable for all r (separability of G(r,x) for all r actually characterizes primitive characters), and Now i f X is primitive, so is x· Hence we can write for a primitive character X q I e(r:;). G(t,x)x(n) = a.=l Multiplying both sides by an and summing over n, we find M+N G(l ,x) I M+N q anx(n) ... ~M+1 I x(a) a=l I ane(z:), n=M+l or q G(t,x)s(x) = I y:(a)s(~). a.=1 Taking squares of absolute values of both sides and summing over the primitive characters we obtain q I* ls(x)l 2 q = x mod q 2 I* II x(a)S(~) I x mod q a=1 q a b x(a)x(b)s(q-)s(q-) I I - x mod q a,b=l < q L S(~)S(~) L = a,b=l x(a)x{b) 'X mod q q I = (J)(q) ls<~>l 2 a=l (a,q)=1 since \ L (J)(q) if' n em (mod q) and (n,q) 0 otherwise. = 1, x(n)x(m) = { 'X mod q This proves the lemma. Since bounds for q ) I w q<X a=l - (a,q)=l follow of eifqy easily from Theorem 6.30, Lemma 6.38 gives us bounds for the sum 2 ls(x) I over all primitive characters 'X to all moduli q ~ x. In some applications where only primitive characters occur, this result is then immediately applicable. In others we will use the fact that every character is induced by a primitive character. The following lemma will be useful in such cases. (6.39) LEMMA. If S(x) is defined by (6.31) and ).(x) is a positive de- creasing continuous function on 0 < D ~x ~ Q, then c6 •4o > I ). c q> D<q~Q q L ls(~)l ~ a=1 (a,q)•l 2 2 (>-(D)(D + N) + Q M+N D n-=M+l Jx>.(x)dx) L 1anl 2 • 93 M+N Let Y = Proof: I an 2 , and let I 1 n=M+1 T(x) = q I I qs_x a=1 (a, q)=1 Since the points a/q, with 1 Sa S q, (a,q) = 1, and q S x are 1 separated by at least 2 , Theorem 6 . 30 says that X We now write t he left side of (6.4o)as a Riemann-Stieltjes intes~~l . It is equal to Q Q J X(x)dT(x) = X(Q)T(Q) - X(D)T(D) D 2 ~ >.(Q)(N+ Q )Y - JDT(x)dX(x) JQ (N+ x2 )Y dA(x) D Q == >.(Q)(N+ Q2 )Y - NY(>.(Q) - X(D)) - YJ x2dA(x) D Q = A(D)NY + X(Q)Q2Y - Y(Q2X(Q) - D2A(D) - 2J xX{x)dx) D Q ~ X(D)NY + X(D)D~ + YJ xX(x)dx, D and this proves the lemma. Notes on Chapter 6. Although the large sieve was originated by Linnik [1), much of its development is due to Renyi, who was the first to use the variance expression and to apply the large sieve to estimate the remainder term in Selberg's sieve. The results listed in this chapter were obtained in the late 1960's after several important advances had been made 1 notably by Roth [1), Bambieri [3), and Davenport and Halberstam [1). Theorem 6.15 (and its corollary, the estimate ( 6 -32) ) , as well as Lemmas 6. 38 and 6. 39, are derived from Gallagher [1]. Theorem 6.19 and the inequal- ities (6.33) and (6.34) came from Bombieri and Davenport [2). The r ecent results of Bombieri and Davenport [3), which we listed as Theorem 6.36, effectively concludes this part of the large sieve; by indicating what the best possible results are for general trigonometric polynomials ~ :1ey show that further advances can be obtained only for ISrticular case s oy ' utilizing some special properties of the polynomials under consideration. Properties of Dirichlet characters and Gauss sums are discussed in Ayoub [ 1; Chapter 5) and Prachar [ 1; chapters 4 and 7). G(r,x) for all r implies that x is primitive That seiSrabiJ.ity of has been proved by Apostol [ 1) • One weakness are affected of estimates such as those of Theorem 6.30 is that they greatly by two of the xi being close together. This weakness has been avoided by a result of Davenport and Halberstam [ 1) (also given in Davenport [1; Section 23) which states, in the notation of 95 Theorem 6.30, that i f & r = min i ~ r !lx1 - xrll' then M+N 2 min(1, ~ tJ )ls(x )1 r r 2 ~ N ) ~ Ian I2 . n=M+1 In the Corrigendum and Addendum to that paper they also gave inequalities for sums of js(x)l 2 and over all characters to the modulus q for all 7 THE lARGE SIEVE We have seen in the first part of Chapter 6 how the number of integers that remain in an interval after removing a given number of congruence classes modulo each prime p S X can be estimated fran bounds for the sum ( 7. 1 ) where Sis a trigonometric polynomial of the form (6.31). Now if a/p and b/p 1 are two points that appear in (7.1), and a/p ~ b/p 1 , then ap' - bp is a non-zero integer, and hence I ~ -prI .,. p Since the same b lap I - bpi > 1 > _1 pp' -:pp'- 2 X argument holds for lk - p~ + ~~ for any integer k, we p have the lower bound min 11 ~ - E.,ll > -12 , 1 a/p ~ b/p P P - x which is best possible in general. Therefore we can estimate (7.1) by -2 applying Theorem 6 .30 with o = X • But by the same argument we can take o =X ~ in estimating the sum of js(x)l 2 over all rational points, in their lowest terms, which lie in (0,1], and for which the denominator is< X. Therefore the bound for (7.1) that we obtain from Theorem 6 .30 is the same as t he bound for 97 q I (7.2) q~ 2 js(~)l . ac1 (a,q)=1 Since the numbers of terms in (7.1) and (7.2) are asymptotic to ~~/log X and ~/n2 , respectively, it is natural that in looking for improvements on (6.8) one should try to use the terms in (7.2) with q composite. We will do this by proving an identity for q I js(~)l2 acl (a,q)=1 similar to the one of Lemma 6.6 (which is not applicable to (7.2) because of the condition (a,q) = 1). The next step will be to use this identity, together with Theorem 6.30, to give estimates for sequences that have no elements in a given number of residue classes modulo p, f or each prime p S X. This whole chapter is devoted to the proof of these estimates (which were discovered by Montgomary) and a few applications. Instead of considering simply a sequence of integers from the interval [M+l, M+N], (M and N integers, N > 0), we will generalize to the case where every integer in that interval has attached certain complex "weight" a • n to it a Our inequalities will then measure the distribution of these weights into various congruence classes. Inequalities for the number of elements in a given sequence will then be obtained by choosing a n to be 1 if n is in that sequence and 0 otherwise. We let a n be any complex numbers defined for n = M+l, ••• , M+N. Define M+N I n=M+1 Z(q,h) = (7.3) a n n=h(mod. q) and M+N Z = Z(1,1) = (7 .4) I an' n=M+1 thus generalizing our previous definition (6.2). We will won with the associated trigonometric polynomial M+N S(x) = (7.5) a e(nx). I n=M+1 n (7.6) LEMMA. If q is a positive integer, then q q L Js(~)J2 = L II ~ z(~,h)l2· (7·7) q a=1 (a,q)=1 Proof: h=1 dJq Since for a an integer q I Z(q,h) e(~h), s(~) = h=1 we have} by (6.1) qz(q,h) = = I dlq qjd I b=1 (b,q/d)=1 S(~d)e( -b~). 99 If we define q (7.8) I s(~)eC:h), T(q,h) = a.=l (a,q)=1 then (7.9) qZ(q,h) = L T(q/d,h). dlq Applying the M8bius inversion fonnula to (7 .6) we obtain T(q,h) 0:: q L ~ Z(q/d,h). dlq But from (7.8) we find that I II ~ Z(q/d,h) I = i I IT(q,h) I q q 2 q h=l dlq 2 . h=l q I a,b=1 (a,q)=(b,q)=l q 1 =q I a,b=1 (a,q)=(b,q)=l q = I a-=1 (a,q)=l by (6.1), and this completes the proof. ls(~)l 2 100 We may note that for a prime p, (7.7) is the same (except for somewhat generalized a ) as (6.7), since n p pI h=1 IalpI ¥ Z(~,h)l2 p =pI IZ(p,h) - ~12· h=1 We now easily deduce (7.10) THEOREM. If Z(q,h) is defined by (7.3), then for X~ 1 we have q M+N I IL ¥ Z(~, h) 12 S 1/2 X)2 I I an12. I q qSX h=1 dlq Proof: (N + n=M+1 Let S(x) be defined by (7.5). By (6.34) we have q M+N Iq<X a=lI ls(~)l 2 2 1 2 < (N / + x) \L Ian 1 · - 2 q n=M+l - (a,q)=l But now we just substitute (7.7) in the left side above. We deduce from Theorem 7.10 (7.11) THEOREM. Let Z(q,h) and Z be respectively, and let X~ 1. defined by (7.3) and (7.4), For each prime p ~X let H(p) be the union of f(p) distinct residue classes modulo p. (7.12) a n Let the a = 0 if n E H(p) for some p S X. Then lzl 2 < (N - 1/2 +X) Q 2 M+N 2 \ Ia 1 L n=M+l n ' n satisfy 101 where Proof: In view of Theorem 7.10 it will suffice to show that for each q S, X we have (7.13) This is clearly true if ~(q) = o. fixed, squarefree Therefore assume that q S, X is a integer. If dJq, we define (7.14) K(d) = (h; 1 S, h S, q, hE H(p) if pjd, h ~ H(p) if pj(q/d)}. The sets K(d), for d going through all the divisors of q, form a partitioning of (1, ••• , q), since for each h we can write q uniquely as q =< 1T p). < IT p). plq hEH(p) pjq h,Elf(p) Therefore we will be able to write q I = dJIq hEK(d) I h=1 Let us fix a 6, &lq. Then by the Cauchy-Schwarz inequality 102 (7.15) II ~(qfd)d I Z(d,h) 12 = j I ~(~)q I z(qjd,h) 12 dlq hEK{6) dlq = hEK(5) I I I ~(~)q Z(q/d,h) 12 hEK(5) dlq ,}{I II '*<~)qz(qjd,h)l }· 2 s.{ I h€K(5) Let us consider the left side above. such that Pl(&,d). h€K(6) dlq Suppose (6,d) > 1, and choose a prime p Now Z(d,h) is a sum of a n with n implies that for such an a we haven m h (mod p). But PI& and hE K(6) mean, n in view of the definition an = 0 whenever n =h (mod d). But pld (7.14), that n E H(p). Therefore by (7.12) =h (mod d) and h E K(6). Hence the inner sum on the left side of (7.15) vanishes when (6,d) > 1, and so (7.16) L L I L '*(qjd)d Z(d,h) = '*(q/d)d Z(d,h). dlq hEK(6) dl(q/6) h€K(6) Let us fix d, with dl(qja). We have d I Z(d,h) = I hEK(6) Z(d,k)· l{h; hE K(6), h =k (mod d)JI, k=1 k,Eli(p) V Pld where the condition k ~ H(p) for all p dividing d follows from the fact that i f k E H(p) for same pld, then Z(d,k) = o. '\ve can campute S(6 1 d,k) ~ l{h; hE K(6), h ~ k (mod d)) I r 103 fork such that k E H(p) for all primes p dividing d. the Chinese remainder theorem h for all prtmes p dividing d. Now in view of =k (mod d) is equivalent to h =k (mod p) Also, h E K(6) is equivalent to h E H(p) for all prtmes p dividing 6 and h ~ H(p) for all prtmes p dividing qf 5. Therefore h E K(5) and h =k (mod d) if and only if the following three conditions are satisfied: =k (mod p) and h ~ H(p), a) Pld ~ h b) Pl5 ~hE H(p), c) Pl(q/dtJ),. h ~ H(p). Since we are dealing with k such that k ~ H(p) for all primes p dividing d, the second part of a) is satisfied whenever the first part is. now notice that We i f pld, then there is exactly one solution of a) modulo p. If Pl5, then there are f(p) solutions of b) modulo p, and i f Pl(qfd5), then there are p - f(p) solutions of c) modulo p. Applying the Chinese remainder theorem we find that S(5,d,k) = l{h; 1 ~ h ~ q, h satisfies a), b), and c)}l = [ 1T f{p)} { 1T (p- f(p))}. PI~ Pl6 This number is independent of k, and hence d L Z(d,h) = I h€K(6) k=1 Z(d,k) k,Si(p) v pjd TT f(p) IT (p-f(p)) Pl6 Pit& 104 d LZ(d,k)( lT f(p)) (IT (p- f(p))) = PI o k=1 Pli5 = Z( lT f(p)) ( lT (p- f(p))). Plo Pit& From (7.16) we now obtain (7.17) I~(qfd)d d Iq L Z(d,h) L ~(qfd)d z( IT f(p)}( lT (p- f(p))} = hEK( &) d I< qf s) PIs PI~ = ~(q)Z( IT f(p)}{ 1T (p- f(p))J 'i !'(d)d IT (p-f(p))- 1 P lo P 1 cqJ o> dTc qJ 6 ) PI d = ~(q)Z( IT f(p)}( 1T (p- f(p))} 1T (1 - p- ?(p)) Pis PI (qfo) PI (q/o) = ~(s)z( IT f(p))( 1T f(p)J = ~(s)z lT f(p). Plo Plqjo Plq The first factor on the right side of (7.15) is s(s, 1,1) = ( TT f(p)} ( TT (p- r(p))J Plo Pl(qfs) Dividing by it and using (7.17) we now find from (7.15)that We now sum on all olq. The right side is just q I I ~ z(q/d,h)l 1 h:l dlq 2 105 since the sets K(6) form a partition of {1, ••• , q}. The left side is This completes the proof. (7.18) COROLLARY. Let X~ 1 and let Z be the number of integers n such that M + 1 S n S M + N and n does nat fall into any of f(p) residue classes modulo p for any prime p ~ X. Then where \ 2 __1_(pl_ • Q = L~ (q) lT p:f(p}. qSX Proof: Let a n Plq be 1 if n is one of the given integers and 0 otherwise. Apply Theorem 7.11, noting that M+N I Z I .. Z "" L an 2 • I n•M+l 1 1o6 We first use Corollary 7.18 to obtain estimates which we proved previously using Selberg's sieve. (7. 19) THEOREM. Let k, M, and N be positive integers satisfying k < and lett be an integer such that (k,t) = 1. 1 3 N, Then (7.20) Proof: We consider m + rk for r = 1, ••• , n, where n is the largest integer such that m ~M and m s t (mod k), and n is the largest integer such that m + nk < M+N. Let X > 2. We consider ~ r ~ n for which m + rk is not divisible by any prime p ~ x. all r. Let p be a fixed prime. If Ptk, then pj(m+rk) only when r If pjk, then p\(m+rk) for =mk- 1 (mod p). Hence we may apply Corollary 7.18 with f(p) = 1 if pjk and f(p) = 0 if pjk. find that Z, the number We t hen of r S n for which m + rk is not divisible by any prime p ~X satisfies where by Lemma 3·3· We now choose \L .!.q>~log X - k I q<x q<x (q,k)=l (q,k)=l 107 Then 2n( 1 + 1 1 2 2N og n < -.,.,"""'t""i,.;;.·;___.,...._,.,.... -~log n- 2 log log n - C9(k)log N/k Z< k for N/k sufficiently large (as ) n ~ N/k + 1). Since n(M+N,k,t) - n(M,k,t) ~ Z + n(X) < Z + X, we obtain (7.20), again for N/k sufficiently large. But the theorem is clearly true for N/k bounded. Next we give a new proof of Theorem 3.17. (7.21) THEOREM. Lets be a positive integer, and suppose that for i = 1, ••• , s, a 1 and bi are integers such that (ai,bi) = 1 and E = s Tf ai • Tf (aibj - ajbi) ~ o. i= 1 Let N(p) be the number of solutions i< j of (a 1v + b 1 ) ·•• (asv + bs) =0 . (mod p) for v = 1, ••• , p for each prime p, and assume N(p) < p for all primes p. Then the number of positive integers m ~ n such that each of laim + bil (i = 1, ••• , s) is prime is < c ( s ) ___;,;n;,...___ . IT ( 1 - .!.)-s+N(p). Proof: (log n) 5 PIE p Let X ?: 1, and consider Z = l{m; m ~ n, Pi (aim+bi) for any p ~X and i = 1, ••• , s}l· Then the integers counted by Z do not fall into any of the N(p) residue classes modulo p corresponding to solutions of 108 for all p S X, and therefore Corollary 7.18 says that z<(n1/2+X)2 - Q ' where Let P 0 = TT p<x Then N(p)=O I Q= 2 ~o/(q) IT <ilil + ~ + .•• ) PI q q<x P P (q,P~)=1 > I ,TTI q q<X (q,P~)=l which is the estimate (3.11). p q N(p) ~ ' The rest of the proof is the same as that of Theorem 3.17. For our final application of Corollary 7.18 we consider a problem to which Selberg's sieve is not applicable due to the large number of congruence classes sieved out. It has been conjectured by Artin that every integer except for 0, -1, and the perfect squares is a primitive root for infinitely many primes. ~e While we cannot prove that conjecture, can give an upper bound on the number of positive integers S N which are not primitive roots for small primes. 109 (7.22) THEOREM. The number of positive integers~ N which are not 1/2 primitive roots for any prime ~ N is ~ N1/ 2 ·log N·log log N for N ~ 3. Proof: Here we sieve out the ~(p-1) residue classes of primitive 1/2 roots for each p ~ N • By Corollary 7.18 the number of remaining integers is where Q= \ '--"/ ~ q~N 2 I 2(q) TT ~(p-1) > \ I P -~(p-1)- p~ L 1I 2 p q ~(p-1) P But lim inf !(n)log log n = -y e ' n (7.23) where y is Euler's constant, and therefore ~(n) ~ 1 og ~ og n for n ~ 3. It follows that ~ Q~ .-(N1/2) ~ N1/2 1/2 ,. -:::--' log N·log log N for N ~ 3' log log N and this completes the proof. 110 Notes on Chapter 7. The material of this chapter is drawn primarily from Montgomery [1]. It should be mentioned, however, that Theorem 7.19 can be proved using large sieve inequalities for sums over by Bombieri and Davenport [2]. Dirichlet characters, as was done Recently Bombieri [3] has proved, using a specialized large sieve method, a result similar to the one of Van Lint and Richert (Theorem 4.1); in (7.20) can be 1 replaced by 0( log N/k ) • Eq. (7.23) is proved in Hardy and Wright [1; Chapter 18]. Theorem 7.22 is not the best possible. While applying a.n old fonn of the large sieve, Gallagher [1] proved that Using the contribution to Q of ccmposite integers it can be proved that Q is of an even larger order of magnitude. ,,1 8 BOMBIERI 'S THEOREM It has been known for same time that estimates for sums of Dirichlet series can be obtained from large sieve inequalities. The purpose of this chapter is to use such estimates to prove a very important theorem of Bombieri about the average of the remainder term in the prime number theorem for arithmetic progression. Let l(x,q,a) = L A(n), n<x n=a (mod q) where A is Mangoldt's A-function. Bombieri's result can then be stated as (8.1) THEOREM. For each positive constant A, there is a positive con- 12 stant B such that if Q = x / (log x)-B, then L (8.2) <~ q~ max max y ~ x (a,q)=l l+(y,q,a) - ~~ ~ x(log xfA, where the constant implied by the ~ symbol depends on A. An analogous estimate holds with v(y,q,a) and y/~(q) replaced by n(y,q,a) and li(y)/~(q), respectively. Now the extended Riemann hypo- thesis, which states that all the non-trivial zeros of Dirichlet L-series L(s,x) lie (8.3) on the line Re(s) = 1/2, implies that *(y,q,a) - -l-- ~ Yl/2 log2y, ~(q) 112 which in turn implies that Theorem 8. 1 holds with B = A + 2. Thus Bombieri 's theorem gives a result ccmparable to the one implied by the extended Riemann hypothesis (which has been neither proved nor disproved), and in many cases where only the average of the remainder tenn is important it can be used in place of the assumption that (8.3) is valid. Our proof, due to Gallagher, shows that B may be taken as 16A + 103, and even better results are possible, but they are relatively unimportant since no way has been found for detennining the constant implied by the <,g notation. Our proof of Bombieri's theorem will proceed through a series of lemmas. The basic idea is to express the left side of (8.2) in tenns of L-series, and then apply the large sieve inequalities of Chapter 6 to it. Actually, however, we will first apply a smoothing device to the functions t(y,q,a) - y/~(q) and work with the resulting functions. For functions F piecewise continuous on [1,oo], we put The main part of our proof will consist of showing that Theorem 8.1 holds with *(y,q,a) replaced by vk(y,q,a) fork sufficiently large (note that i f F(x) = x, then F 1(x) = x - 1, so that our smoothing device affects x to an extent that is negligible for our purposes). show this for k = 3· estimates imply (8.2). We will actually At the end of the proof we will show that such 113 First we prove an auxiliary result. (8.4) LEMMA. For x > 1 we have L cpC n} ~ 1 + log x. n<x Proof: This is · clearly true for x ~ 3· Assume therefore that x > 3. Since ~ is a multiplicative function, we have cp\n J 1 1 + ••• ) -+ IT (1 + cp1p + cp(p12 ) + ... ) = 1T (1 +p-1 In<x cp~ <- p:_x p(p-1) ~ p~x l2 ~ !+0(1) p<x (p-1)2 p<x P l2 2) < e = 1T (1 + =e (p-1) p:: X ~ = e log log x + 0(1) ~ 1 og x • ~ The next lemma shows that in order to estimate it is sufficient to estimate a sum involving primitive characters to fairly large moduli. Before we prove it we should make a few remarks about the values of A and k. Our goal is to prove (8.2) with the implied constant depending only on A. Due to the use of the smoothing device, however, the A's we will be working with will be functions of the A of Theorem 8.1. In order to ensure that all constants can be chosen so as 114 to depend only on the original A for which the theorem is being proved, which is given, we will require at each stage that the A and k be bounded (actually we will only need k ~ 3, and if A' is the given A of Theorem 8.1, then we will always have A ~ 8A 1 + 7), so that the implied constants will be valid for all values of A and k that we will use. Fran now on we write t for log x. t(x,x) = We use the usual definition I x(n)A(n). n<x (8.5) w.tfA. For Q ~ x 1/2 and for bounded k, A, and C, we have I max max l'tk(y,q,a)- ~~ ~ I €(q) I* maxltk(y,x)l+ x.t-A , qs_Q Y'5_x (a, q )= 1 where D = t n<qs_Q c , €(q) = 1 +log~Q/q) cp( q and \ * L ' 'X mod q yS_x denotes summation over 'X mod q primitive characters to the modules q. Proof: We have (by induction) +k(x,x) = fr I x(n)A(n)logk(~). n<x Also, since y(x,q,a) = 1 ~ \ x(a)~(x,x), L ')(mod q we find (8.6 ) 'fk(x,q,a) = 1 ~ 'X Imod qx(a)tk(x,x)· 115 If X is induced by the primitive character X* , then x(n) = X* (n) except possibly when (n,q) > 1. Therefore < 2 .tk -IT In<x A(n) = ~! pjqLlog L a p tk 1 a<x (n,q)>1 p- If Xo denotes the principal character to the modulus q, then Xo is induced by the identity character and thus Therefore we obtain from (8.6) max (a,q)=1 and hence + t k+l log q, 116 In the first term on the right of from the same primitive character. (8.7) we group together terms arising Since if x is induced by the primitive character X* , then the modulus of X* divides the modulus of x, we get 'k I (y 'X) I . , L ~ n$Q n:::O(mod q) where the last relation follows from Lemma 8.4. Hence for Q ~ x 1/2 and bounded k and A, (8.8) L qSQ ~X max Siegel's theorem implies that with arbitrarily large constants C and E. Therefore if k, A, and C are bounded, the terms with q S D = tc contribute ~ xt-A to the right side 117 of (8.8). Similarly, the prime number theorem implies that max l t(y)- Yl ~ xt-E, (8.10) y~x for arbitrarily large E, and therefore for arbitrarily large E, provided k is bounded. Hence for Q ~ x 1/2 and bounded k and A we obtain Combining all our estimates we obtain the statement of the lemma. Thus our task has been reduced to that of estimating The next lemma expressesthis sum in a form suitable for application of the large sieve. (8.11) LEMMA. Let L = L(s,x) be a Dirichlet L-series for the characterx and S = S(s,x) be any function bounded and analytic in a~ 1/2. 1 1 Define a= 1 + t - and 8 = 1/2 + t- , and denote by (a) and (e) the paths let a+ it (-oo < t < oo) and~+ it (-oo < t < oo), respectively. Then for k > 2 we have L €(q) D<q<Q L* ~x A(s) dt + x1/2J B(s) dt, max ltk(y,x) l ~ xtJ 1 1 (e) lslk+ x mod q (a) lslk+ 118 where A( s ) = L q) L* 11 - LS 12 € ( X mod q ~ and B(s) = ) (IL'LS I+ IL'Sj) • L €(q) "* 2 n<~ Proof: Since fork> ....... x mod q we have 1 k k! log X if X~ 1, 0 if 0 <X< 1, (8.12) and the series 00 (8.13) L' \ -L (s,x) = L x(n)h(n) n converges absolutely for a> 1, we obtain Now ( 8.14) L' L' L = r;-(1 - LS) 2 + (2L'S - L'LS2 ). For x ~ x0 , Land L' are analytic in a~ 1/2. 1 2 Moreover, L(s) ~ lsl / for a~ 1/2, and since by Cauchy's formula (8 .15) 1 L I ( s ) "' 2 d I L( z) y (z-s) 2 dz, 119 where y is a circle of radius tfor ~ ~ B= 1I 2 + t -1 1 1 2 centered at s, we have L'(s) ~ lsl / • Therefore the second term in (8.14) is analytic and ~ Is I in ~ > 8, and hence for k ~ 2 we can transfer the path of integration of the second term from (a) to (e). We find On ~ = a, we have for 1 ~ y ~ x, y s =y l+t -1 +it =e (1+t Similarly, on~= 8 we have y -1 )log y+it·log y ~ ~ 5 e log x+1 ~ ~ x. ~ x 1/ 2 for 1 ~ y ~ x. Also, l(u) ~ u and (8.13) imply that on ('J =a we have du Ci = /.,. u Hence we find that To finish the proof we just sum this estimate, multiplied by €(q), over all q with D < q ~ Q and all primitive characters to the modulus q. Application of the large sieve inequalities. We now use the inequalities of Chapter 6 to estimate A(s) on ('J =a and B(s) on ('J = e. Let a (8 .1 6) n be any complex numbers. q Ci(q) * M+N Then by Lemma 6 . 38 2 q M+N 2 I In=M+I 1anx(n)\ ~ a=L1 In=M+L1ane(~a)l ' X mod q (a,q)=l 120 and by Theorem 6.30 M+N L a ne(~)~ q I I 2 ~ (X2+ N) \ q<X a=1 - (a,q)=1 n=M+1 M+N ) ~...... Ian I2 . n=M+l Combining these two inequalities leads to (8. 17) q ~ * M+N X mod q n=M+l M+N 2 I I I anx(n)l ~ (X + N) L lanl 2 · • 2 n=M+l Lenma 6. 39 implies that for D ~ Q/log Q we have q log(Q/q)+l q M+N I an e(~a)l Ia=l In=M+l 2 (a,q)=l Q M+N ~ { los<§Ln)+l(D2+ N) + Jn(l+log(Q/x))dx} lanl2 I n=M+l M+N ~ ( Q + N l~g Q) ) Ia ~ n 12 • n=M+l Combining this with (8.15) leads to M+N (8. 18) >* I L w X mod q 2 anx(n) I ~ (Q + N ~og Q) L n=M+l n=M+l again with the restriction D ~ Q/log Q. For X a character to the modulus q, define R(x,x) = M+N L x(n). ':l<x 121 Then by a theorem of Polya and Vinogradov (8.19) Since the Dirichlet series for L(s,x) converges for a> 0 whenever x 1 x 0 , we have under these assumptions, for each integer H ~ 1, (8.20) Therefore for a ~ 1, H ~ 1, and x I= Xo' we have L(s,x) = I x<:l o(lsls ~ loa 1 2 + n=1 q ). n We choose H = ~ I (n)x(n) s ' n n=1 and notice that it satisfies the hypothesis of Lemma 8.11. Moreover, for H S, x and a~ 1 we have S(s,x) ~ log H S. t, so that for q S. x, where c(1) = 0, and for n > 1, c(n) = \L ~(d). din d,(n/d)SJ 122 I n particular, c(n) = 0 for n >~and n ~ H, and lc(n)l ~ d{n), the 2 number of divisors of n, for H < n £H. We now separate the integers 2 H+1, ••• , H into m sets: (H+l, ••• , 2H}, {2H+l, ••• , 4H}, ••• , (tn- 1H+ 1, ••• , 2Il}r}, where 2m- 1H+ 1 ~ H2 S, 2Il}r, so that m ~ log H ~ t. Using the Cauchy-Schwarz inequality, we obtain m-1 2h+1H m-1 II ( I h=O c(n)~(n) )j 2 ~ t I I I n c(n)~(n) 12 • h=O n=2 hH+ 1 n=2··rt+ 1 Next we apply (8.17) with a right side above. n h.. 2n+lH n = c(n)/ns to each of the factors on the 2 For each N = 2~ (S, x ), with D ~ Q/log Q and Q S. x, we find 2N ") e(q) I*l n=N+1 L \ I.....J ~Q x mod q 2 c(n)x(n)l ns 2N ~ (Q + Nt) \ L. D n=N+l 2 d (n) ~ (S + ~)t3 n2 since the inequality (8 .21) T(M) = I d2 (n) ~ M log3M n<M implies 2N I n=N+l Therefore, using m ~ t, m-1 A( s) <:g I ( {2 + ~ )t4 + I (log (Q/q} + h=O D<q~ ~ QH-\4 + n-\6 + lsi2Q~-2t4. N D ' 123 We can choose H = QDt -2 to get (8.22) on cr = a, provided t ~ D ~ Q/log Q. To estimate B(s) on cr =a, we apply (8.17) to ~ L b(n1(n) ' s2(s,x) = n where lb(n) I :: d(n), and get for cr :::_ 1/2 (8.23) when the last estimate again follows from ( 8.21 )by partial summation. It follows from (8.20) that for each N :::_ 1, 1/2 N L(s 'L ~ + o(lslq log q) for x ~ x and cr >_ 1/2. 'X s 1/2 ' 0 ) - n=l n N Therefore (8.24) We now apply (8.17) to the sum on the right. N 2 N2 Since (I x(~l) = L a(n);(n) , n=l n n=l n 124 with la(n)l ~ d(n), we find that (8.24) is N2 2 2 ~ (~ + N ) --" ~ ~ (X2 + N2 )log4N. n J n=1 We now choose N = [XIsl + 2]. L l<q~x IL(s,x)l 4 ~ ~lsl log 4 (xlsl + 2). 2 x mod q A Since C(s) ~ lsi (8.25) L* q>(q) Then the above inequalities give 1/2 for 1/2 ~ ~ < 3/4, say, we actually have \ \* q~X X mod q L q>(q) L IL(s,x)l 2 2 2 4 ~X lsi log (XIsl + 2) for 1/2 ~ ~ < 3/4. Applying H8lder's inequality to (8.15) twice gives 4 I L I ( s 'X) 1 ~ t5 I 4 I L( z 'X ) 1 • y Therefore on ~ = 9 we have (8.26) Using the Cauchy-Schwarz inequality, we now find that I 'l'(q} q~X ( X mod q 2 IL'IB 1 S 0:: <lfu ( IL'LI t I ifqy ( 2 q:S,X X mod q 2 ( q:S.X 4 112 ls1 ) X mod q \ * 4)1/2 ; Is I 1.-1 125 If we now choose H = DQ.(, -2 , then we easily obtain A5 2 B(s) ~ DQt lsllog (lsi+ 2) for c = ~· (8.27) Completion of the proof. Using Lemma 8.5 , Lemma 8.11, (8.22), and (8.27), we find that for k ~ 2, Q ~ x 1/2 , and bounded k and A, (8.28) provided t ~ D ~ Q/log Q. For k = 3 the right side of (8.28) is ~ xD- 7t 7 + x 1/ 2DQt5 + xt-A. Choosing D = tA+ 7 and Q = x 1/ 2 t-(2A+l 2 ), we find (8.29) We now deduce (8.2) from(8.2 9). Suppose that the following statement is true for a positive integer k: For every positive constant A, there is a constant ~(A) such that i f (8. 30) then with the implied constant depending only on A. 126 We will show that then (8.30) also holds fork - 1, with ~- 1 (A) = ~(2A + 1). Since vk_ 1(y,q,a) is an increasing function of y, we have, for 0<)..~1, eA J )dz ( 1 J r ->.. *k-1 z,q,a z- ~ *k-1 y,q,a) ~ r 'k-1(z,q,a) dz z; 1 Y e ( Y Y Y Evaluating the integrals we obtain (8.31) If we write tk(x,q,a) = ~(q) + rk(x,q,a), then (8.31) implies that .!.[Y( 1-e >.. cp ( q ) ->.. Therefore for Q ~ x ) - 1/2 2 max I rk (z,q,a )I) < ~ _ M q + rk-l ( y,q,a ) z~y we have T 127 But by (8.30) the right side is ~ ~ ).x.t + -1 A x.(, -A , This proves our assertion about (8.30). Since we have proved that B (A) = 2A + 12, this gives us B (A) = 16A + 103. 0 3 128 Notes on Chapter 8. The proof given above is due to Gallagher [2]. The original proof (Bombieri [3] ), which is considerably more involved, relates the sum (8.2) to the density of zeros of Dirichlet L-series in the and avoids the use of our smoothing device. initial (There is also a good exposition of this method in Davenport [1; Sections 24-28].) proved that B can be taken as 3A + 23, Bombieri but this is not very important since the use of Siegel's theorem (which plays a crucial role in both Bombieri's ani Gallagher's proofs) has so far prevented the determination of the constant implied by the ~ sign. Our proof presupposes a fair knowledge of analytic number theory, but practically everything used is quite standard and may be found in Prachar [1] and Ayoub [1]. The inequality (8 . 21), which is not known too well, is proved in Prachar [1; Chapter 1]. Many applications of Bombieri's theorem have been made. One of the most interesting is the proof by Elliott and Halberstam [1] that every sufficiently large integer n may be represented that is, as a sum of a prime and two squares . as n = p + x 2 2 + y ; Their paper lists previous proofs of this theorem, some of which used unproved conjectures such as the extended Riemann hypothesis. The large sieve estimates have been used in proving several other important results in analytic number theory. ot Jutila [1] and Montgomery [2), [3]. We might mention here the papers 129 BIBLIOORAPHY The following list contains, besides some general references, all the publications on sieve methods of which the author is aware. Relatively few of them are referred to in the text. ANKENY, N. C• 1. Applications of the sieve, Proceedings of Symposia Mathematics, 8(1965), 113-118. MR in Pure 31, no. 141. ANKENY, N. C"J and ONISHI, M. 1. The general sieve, Acta Arith. 10(1964), 31-62. MR 29, no. 4740. APOSTOL, T. M. 1. Euler's ~-function and separable Gauss sums, Proc. Amer. Math. Soc. 24(1970), 482-485. MR 41, no. 1661. AYOUB, R. 1. An Introduction to the Analytic Theory of Numbers, Mathematical Surveys, no. 10, Amer. Math. Soc., Providence, R. I., 1963 . MR 28 no. 3954. BARBAN, M. B. 1. 2. On a theorem of I. P. Kubilius, Izv. Akad. Nauk UZSSR Ser • Fiz. -Mat. Nauk 1961, no. 5, 3-9 and 1963, no . 1, 82-83. (Russian). MR 25 no .2051. New applications of the "large sieve" of Ju. v. Linnik, Akad. Nauk UzSSR Trudy Inst. Mat. 1961, no. 22, 1-20. (Russian~MR 30 no. 1990. A remark on the author's paper "New applications ••••• , " Theory Prob. Math. Statist., Tashkent, 3· 1964, 130-133· (Russian). Linnik's "large sieve 11 and a limit theorem for the class number of ideals of an imaginary quadratic field, Izv . Akad. Nauk SSSR Ser. 4. 5· Mat. 26 (1962), 573-580. (Russian). MR 27, no. 1426. Analogues of the divisor problem of Titchmarsh, Vestnik Leningrad. Univ. 1963, no. 19, 5-13. ("Russian). The density of zeros of Dirichlet L-series and the problem of sums of prime and "almost prime" numbers, Mat. Sb. N.S. 61(1 03)(1963), 418-425. (Russian). MR 30, no . 1992. 130 BARBAN, M. B. - continued 6. On the number of divisors of "translations" of the prime number twins, Acta Math. Akad. Sci. Hungar. 15(1964), 285-288. (Russian). MR 30, no. 11 02 • 7. The "large sieve" method and its applications in the theory of numbers, Uspehi Mat. Nauk 21(1966), no. 1 (127), 51-102 =Russian Math. Surveys, 21(1966), 49-103. MR 33 no. 7320. 8. On Bombieri's density conjecture, Dokl. Akad. Nauk SSSR 172(1967), 999-1000 = Soviet Math. Dokl. 8(1967), 202-203. MR 35 no. 5402. BATEMAN, P. T., and Horn, R. A. 1. Primes represented by polynomials in one variable, Proceedings of Symposia in Pure Mathematics, 8(1965), 119-132, ~ffi 31, no. 1234. BATEMAN, P. T., and STEMMLER, R. M. 1. Waring's problem for algebraic number fields and primes of the form (pr-1 )/(pd-1), Illinois J. Math. 6(1962), 142-156. MR 25 no. 2059· BOMBIERI, E. 1. Maggiorazione del resto nel "Primzablsatz" col metodo di Erd8s- Selberg, Inst. Lombardo Acad. Sci. Latt. Rend. A96(1962), 343-350. MR 27, no 120. 2. Sulle formule aritmetiche di A. Selberg generalizzate per classi di funzioni e le applicazioni al problema del resto nel "Primze..hlsatz", Riv. Mat. Univ. Parma (2) 3(1962), 393-440. MR 27, no. 4804. MR 33, no. 5590. 3. On the large sieve, Mathematika 12(1965), 201-225. 4. On a theorem ofVan Lint 3J'ld Richert, Symposia Mathematic& 4(1970), 175-180. BO:MBIERI, E. 1 and DAVENPORT, H. 1. Small differences between prime numbers, Proc. Royal Soc. A, 293(1966), 1-18. MR 33, no. 7314. 131 BOMBIERI, E and DAVENPORT, H. - continued 2. On the large sieve method, Number Theoty and Analysis (papers in honor of E. Landau, ed. by p. Turan), Berlin-New York 1969, 9-22. 3. MR 41, no.5327. Some inequalities involving trigonometrical polynomials, Ann. Scuola Norm. Sup. Pisa. Sci. fis. mat. III, Ser. 23 (1969), 223-241. MR 40, no. 2636. BRU IJN, N • G • DE 1. On the number of uncancelled elements in the sieve of Eratosthenes, Nederl. Akad. Wetensch. Proc. 52 (1950), 803-812 = Indagationes Math. 12 (1950), 247-256. MR 12-11. 2. The asymptotic behavior of a function occurring in the theory of primes, Indian Math. Soc. N. s. 15(1951), 25-32. MR 13-326. On the number of positive integers ~ x and free of prime factors > y, Nederl. Akad. Wetensch.Proc. 54(1951), 50-60 = Indagationes Math. 13 (1951), 2-12. MR 13-724. BRUN, V. 1• Le crible d'Eratosthene et le theoreme de Goldbach, Norske Vid- Selsk. Skr., I 2. Le serie M.-N. Kl., Kristiania, 3(1920) , 1-36. 1111 1 1 1 1 1 3 + 5 + 7 + IT + T3 + 17 + 19 + 29 + 3f + .•• convergente ou finie, est Bulletin des Sciences Mathematiques 43(1919), 100-104, 124-128. BUCHSTAP. A. A• 1. Asymptotische AbschHtzungen einer allgemeinen zahlentheoretischen Funktion, Mat. Sb. N.S. 44(1937), 1239-1246. 2. N~Verbesserung in der Methode des Eratosthenischen Siebes, Rec. Math. N.S. 4(1938), 375-387 . 3· On an additive representation of integers, Mat. Sb. N.S. 10(52), ( 1942), 87-91. (Russian). 132 BUCHSTAB, A. A. - continued 4. On those numbers in an arithmetic progression all prime factors of which are small in magnitude, Dokl. Akad. Nauk N.S. 67(1949), 5-9· SSSR (Russian). MR 11-84, 871. 5. Sur la decomposition des nombres pairs en somme de deux composantes dont chacune est formee d'un nombre borne de facteurs premiers, Dokl. Akad. Nauk SSSR N.S. 29(1949), 544-548. MR 2-348. 6. On an asymptotic estimate of the number of numbers of e.n arithmetic progression which are not divisible by "relatively" small prime numbers, Mat. Sb. N.S. 28(70), (1951), 165-184. (Russian). MR 13-626. 7· New results in the Goldbach-Euler problem and the twin prime problem, Dakl. Akad. Nauk SSSR, 162(1965), 735-738 =Soviet Math. Doklady, 6(1965), 729-732. MR 31, no. 2226. 8. A combinatorial strengthening of the Eratosthenes' sieve method, Uspehi Mat. Nauk 22 (3)(135), (1967), 199-226 = Russian Math. Surveys 22(1967), 205-233· MR 36, no. 1413. BURGESS, D. A., and ELLIOTT, p. D. T. A. 1. On the average order of the least primitive root, Mathematika 15(1968), 39-50. MR 38, no. 5736. DAVENPORT, H. 1. Multiplicative Number Theory, Chicago 1967. MR 36, no. 117. (See also Davenport and Halberstam [2], below.) DAVENPORT, H., and HALBERSTAM, H. 1. The values of a trigonometrical polynomial at well spaced points, Mathematika 13(1966), 91-96. 2. Corrigendum and Addendum, MR 33, no. 5592. (See also [2] below.) Mathematika 14(1967), 229-232. MR 36, no. 2569. 3· Primes in arithmatic progressions, Michigan Math. J. 13(1966 ), 485-489. MR 34, no. 156. +Corrigendum, Michigan Math. J., 15(1968), 505. MR 38, no. 2099. 133 ELLIOTT, P. D. T • A. The distribution of primitive roots, Ganad. J. Math. 21(1969), 822-841. MR 40, no. 104. 1. ELLIOI'T, P. D. T. A., and HALBERSTRAM, H. 1. Some applications of Bambieri's theorem, Mathematika 13 (1966), 196-203. MR 34, no. 5788 . " p. ERDOS, The difference of consecutive primes, Duke Math. J. 6(194o), 1. 438-441. 2. MR 1-292. On some applications of Brun's method, Acta Sci. Math. Szeged. 13(1949), 57-63. 3· MR 10-684. Problems and results on the difference of consecutive primes, Publ. Math. Debrecen 1(1949), 33-37· " MR 11-84. , ERDOS, P. , and RENYI, A. 1. Some problems and results on consecutive primes, Simon Stevin 2. 27(1950), 115-125. MR 11-644. Some remarks on the large sieve of Yu. v. Linnik, Ann. Univ . Sci. Budapest, E8tv8s Sect. Math. 11(1968), 3-13. MR 39, no. 2718. ESTERMANN, T. 1. Eine neue Darstellungen und neue Anwendungen der Viggo Brunscben Methode, J. Reine Angew. Math. 168(1932), 1o6-116. FAINLEIB, A. S. 1. The limit theorem for the number of classes of primitive quadratic form with negative discriminant , Dokl. Akad. Nauk SSSR 184(1969), 1048-1049 =Soviet Math. Doklady 10(1969), 206-207 . MR 39, no. 5474. FllJCH, W. 1. Verwendung der Zeta-Funktion beim Sieb von Selberg, Acta Arith. 5(1959), 381-405. MR 23, no . A1614. 134 GALLAGHER, P. X. 1. The large sieve, Mathematika 14(1967), 14-20. MR 35, no. 5411. 2. Bombieri's mean value theorem, Mathematika 14 (1968), 1-6. MR 38, no. 5724. 3· A larger sieve, to appear in Acta Arith. vol. 18. GELFOND, A• 0. , and LINNTIC, Yu • V. 1. Elementary Methods in Analytic Number Theory, Chicago 1965. MR 32, no. 5575· GOLDFELD, M. 1. On the number of primes p for vhich p +a has a large prime factor, Mathematika 16(1969), 23-27. MR 39, no. 5493· GOLOMB, S. W. 1. The tvin prime constant, Amer. Math. Monthly 67(1960), 767-769. HALBERSTAM, H. 1. Footnote to the Titchmarsh-Linnik divisor problem, Proc. Amer. Math. Soc. 18(1967), 187-188. MR 34, no. 4221. HALBERSTAM, H., JURKAT, W., and RICHERT, H. E. 1. Un nouveau resultat de la methode du crible,Comptes Rendus A, 264(1967), 920-923. MR 36, no. 6374. HALBERSTAM, H., and RICHERT, H. E. 1. Sieve Methods, to be published by Markham Publ. Co., Chicago. HALBERSTAM, H., and Ra.rH, K. F. 1. Sequences, vol. I, Oxford, 1966. MR 35, no. 1565. HALBERSTAM, H., and ROI'KIEWICZ, A. 1. A gap theorem for pseudo primes in arithmetic progressions, Acta Arith. 13(1967/68) , 395-404. MR 38, no. 1329. HARDY, G. H., and LITTLEWOOD, J. E. 1. Some problema of po.rtitio numerorum, Actn Math. 1~1~(1o/t?3), 1-'(0. 135 HARDY, G. H. , and tlRIGHT, E. M. 1. An Introduction to the Theory of Numbers, 4th ed ., Oxford, 1960 . HEILBRONN , H• II 1. Uber die Verteilung der Primzahlen in Polynomen, Math. Annalen, 104(1931), 794-799· HEILBRONN, H., LANDAU, E., and SCHERK, P. 1. Alle grossen ganzen Zahlen lassen sich als Summe von h5cbsten 71 Primzahlen darstellen, Casopis Pro Pestorani M~tematiky a Fysiky, 65 (1936), 11 7-140 . HUA, L. K. 1. Die Abschatzung von Exponentialsummen und ihre Anwendung in der Zahlentheorie, EnzyklopMdie der Math. Wissenschaften, Leipzig 1959, vol. I2, book 13, part 1, Art. 29. MR 24 , no. A94. 2. Additive Theory of Prime Numbers, Translations of Mathematical Monographs, no. 13, Providence, R. I., 1965. HUXLEY, M. N. 1 The large sieve inequality for algebraic number fields, Mathemat ika 15(1968), 178-187. 2. MR 38, no. 5737 · On the differences of primes in arithmetical progressions, Acta Arith. 15(1968/69 ), 367-392 · MR 39, no. 5494. IZUMI, M., and IZUMI, S. 1. On a theorem concerning trigonometrical polynomials, Proc. Japan Acad. 43(1967), 71-76. MR 36 , no. 592. JAMES, R. D. 1• On the sieve method of Viggo Brun, Bull. Amer. Ma.th. Soc. 1~9 ( 1943), 422-432. MR 4-265. 2• Recent progress on the Goldbach 55 (1949), 246-260. problem, Bull. Amer. Math. Soc . MR 10-515, 856. 136 JURKAT, W• , and RICHERT, H. -E. 1. An improvement of Selberg's sieve method I, Acta Arith. 11(1 965) , 217-240. MR 34, no. 2540. JUTIIA, M. 1. A statistical density theorem for L-functions with applications , Arta Arith. 16(1969), 207-216. MR 40, no. 5557· "' KATAI, I. 1. A note on a sieve method, Publ. Math. Debrecen 15(1968), 69-73 · MR 38, no. 5730. KLDfOV, N. I. 1. Combination of elementary and analytic methods in the theory of numbers, Uspehi Mat. Nauk. 13:3 (81) (1958 ), 145 -1 64 . (Russian). MR 20, no. 3841. 2. Almost prime numbers, Uspehi Mat. Nauk. 16(3)(99 )(1 96 1 ), 181-188. (Russian). MR 23, no. A2398 . KUHN, p, 1. Zur Viggo Brunschen Siebmethode, Norske Vid. Selsk. Forh., Trondheim, 14, no. 39 (1 941 ), 145-148. MR 8-503. 2 . Neue AbschHtzungen auf Grund der Viggo Brunschen Siebmethode, 12. Skand. Mat. Kongr., Lund 1953, 160-168 . MR 16 -676 . II 3. Uber die Primteilen eines Polynome s , Proc. Inter. Math. Congress, Amsterdam (1954), 35-37· LANDAU, E. 1. Die Goldbache Vermutung und der Schnirelmannsche Satz, G5ttinger Nachrichten, 1930, 255 -276 . 2. Elementary Number Theory, New York, 1958 . 137 LEVIN, B. V. 1. Lower estimates for the number of almost primes in some general sequences, Vestnik Leningrad. Univ. 15(1960), no. 7, 48-65 . (Russian). 2. MR 22, no. 7985. Distribution of almost prime numbers in sequences generated by integer- valued polynomials, Dokl. Akad. Nauk Uz3SR. 7 ( 1962), no. 11. 3. (Russian). On a class of number-theoretic problems that reduce to differential equations, Trudy TaSbkent Gos. Univ. 228 (1963), 56-68. (Russian). 4. Estimates of special sums and products which are connected to sieve methods, Trudy Tashkent Gos. Univ. 228( 1963) , 69- 80. (Russian). 5. Distribution of "almost prime" numbers in polynomial sequences, Mat. Sb. N.S. 61(103)(1963), 389-407. (Russian). MR 30, no 1991. 6. A one-dimensional sieve, Acta Arith. 10(1 965 ), 387-397 · MR 31, no. 4774. (Russian). 7. Comparison of A. Selberg's and v. Brun's sieves, Uspehi Mat. Nauk. 20(1965), no. 5 (125), 214-220. (Russian). MR 32, no . 7534 . 8. On the least almost prime number in an arithmetic progression 2 2 + 1, Uspehi Mat. Nauk . 20(1965), no. 4(124), and the sequence k x 158-162. (Russian). MR 32, no. 5612. 138 LEVIN, B. V., and MAKSUOOV, I. G. 1. Distribution of almost prime numbers in polynomials inn variables, Izv. Akad. NaukUz3SR Ser. Fiz.-Ma.t. Nauk 10(1966), no. 3, 15-23. MR 33, no. 7316. (Russian). LEVIN, B. V., and 'IUI.JAGANOVA, M. I. 1. The sieve of A. Selberg in algebraic number fields, Litovsk. Mat. Sb. 6(1966), 59-73· (Russian). MR 34, no. 7492 . LINNIK, Yu. V. 1. The large sieve, Dokl. Akad. Nauk SSSR 30(1941), 292-294. MR 2-349· 2. A remark on the least quadratic non-residue, Dokl. Akad. Nauk SSSR, 36(1942), 119-120. MR 4-189. LINT, J. H. VAN, and RICHERT, H. -E. 1. On primes in arithmetic progressions, Acta Arith. 11 ( 1965), 209-216. MR 32, no. 5613. MEISSEL, E. 1. II Uber die Bestim.mung der Primzahlenmenge innerhalb gegebener Grenze, Math. Ann. 2(1870), 636-642. MIECH, R. J. 1. Almost primes generated by a polynomial, Acta Arith. 10(1964 ), 9-30. MR 29, no. 1174. 2. Primes, polynomials, and almost primes, Acta Arith. 11(1965), 35-56. MR 31, no. 3390. 3· A uniform result on almost primes, Acta Arith. 11(1966 ), 371-391. MR 34, no . 1287. 139 MIENTKA, W. E. 1. An application of the Selberg sieve method, Indian Math. Soc, J. N.S. 25-26 (1961-62), 129-138. MR 27, no . 2490. MONTGOMERY, H. L. 1. A note on the large sieve, J. London Math. Soc . 43(1968), 93-98. MR 37, no. 184. 2. Mean and large values of Dirichlet polynomials, Invent. Math. 8(1969), 334-345 . 3· Zeros of L-functions, Invent. Math. 8(1969), 346-354. MR 40, no. 2620. NAGEL, T. 1. Generalis~tion d'un theoreme de TChebycheff, Journal de Mathematiques (8), 4(1921), 343-356. NIVEN, I. , and WCKERMAN, H. S. 1. An Introduction to the Theory of Numbers, New York, 1960. MR 22 , no. 5605. PAN, C. 1. On the representation of even numbers as the sum of a prime and an almost prime, Acta Math. Sinica 12(1962), 95 -1o6 ~ Chinese Math.Acta 3(1963), 101-112. 2. MR 27, no. 1427. On the representation of even numbers as the sum of a prime and a product of not more than four primes, Sci. Sinica 12(1963), 455-473· (Russian). MR 28, no. 73· 3· A note on the large sieve method and its applications, Acta Math. Sinica 13(1963), 262-268 ~Chinese Math.-Acta 4(1963), 283-290. MR 29, no. 82. 4. A new application of the JU. V. Linnik large sieve method, Acta Math. Sinica 14(1964), 597-606 ~ Chinese Math. -Acta 5(1964), 642-652. MR 30, no. 3871. PRACHAR, K. 1. Primzahlverteilung MR 19-393· , Berlin - Gottingen -Heidelberg, 1957. 140 RADEMACHER, H. 1. Beitrage zur Viggo-Brunschen Mathode in der Zahlentheorie, Abh. Hamburg 3 ( 1924), 12-30. Lectures on Elementary Number Theory, New York-Toronto-London, 1964. 2. RAMASWAMI, V. 1. On the number of positive integers< x and f ree of prime divisors > xc, Bull. Amer. Math. Soc. 55 (1949), 1122-1127. MR 11-233· On the number of positive integers S x and free of prime factors 2. > xc and a problem of s. S. Pillai, Duke Math. J. 16 (1949), 99-109, MR 10-597· RANKIN, R. A. 1. The difference between consecutive prime numbers III, J. London Math. Soc. 22 (1947), 226-230. , MR 9-498. RENYI, A. 1. On the representation of an even number as the sum of a single prime and a single almost prime number, Dokl. Akad. Nauk SSSR 455-458. 2. (Russian). N.S. 56 (1 947), MR 9-136. On the representation of an even number as the sum of a single prime and a single almost prime number, Izv. Akad. Nauk SSSR Ser. Mat. 12(1948), 57-78 = Translations Amer. Math. Soc. (2) 19 (1962), 299 -321. MR 9-413. 3· On the large sieve of Ju. v. Linnik, Compositio Math. 8 (1950 ), 68-75· MR 11-581. 4. Un nouveau theoreme concernent les fonctions independantes et ses applications ala theorie des nombres, J. Math. Pures Appl. 28 (1949~ 137-149. MR 11-161. 5· Sur un theoreme general de probabilite, Annals Inst. Fourier Univ. Grenoble 1 (1949), 43-52. MR 14-886. 6. On a general theorem in probability theory and its application in the theory of numbers , casopis Pest. Mat. Fys. (Russian). MR 12-590. 74 (1949), 167-175· 141 ; RENYI, A.- continued 7· Probability methods in number theory, Advancement in Math. 4(1958), 465-510. (Chinese). MR 20, no. 4535· 8. On the probabilistic generalization of the large sieve of Linnik, Magyar Tud. Akad. Mit. Kutato Inst. Kozl. 3(1958), 199-206. MR 22, no. 1937. 9· New version of the probabilistic generalization of the large sieve, Acta Math. Acad. Sci. Hungar. 10(1959), 217-226. MR 22, no. 1938. RICCI, G. 1. Ricerche aritmetiche sui polynomi, Rend. Mat. Palermo 57 (1933), 433-475· 2. Sur la congettura di Goldbach e la constante di Schnirelmann, Ann. Scuola Norm. Sup. Pisa (2), 6(1937), 71-116. 3. Sull 1 and.amento della differenza di numeri primi consecutiVi, Rivista Mat. Univ. Parma 5{1954), 3-54. MR 16-675· RICHERT, H. -E. 1. Selberg's sieve with weights, Mathematika 16(1969), 1-22. MR 40, no. 2. Selberg's sieve with weights, Symposia Mathematica, vol. 4{1970), 73-80. 3· Selberg's sieve with weights,to appear in an Amer. Math. Soc. volume on the 1969 Summer Institute on Number Theory at Stony Brook. RIEGER, G. 1. Anwendung der Siebmethode auf einige Zahlentheorie. I., F~gen der additiven J. Reine Angew.Math. 214/215 (1964), 373-385. MR 29, no. 86. 2. Anwendung der Siebmethode auf einige Fragen der additiven Zahlentheorie. II., Math. Nachr. 28 (1964/5), 207-217. 3· MR 31, no. 131. On polynomials and almost-primes, Bull. Amer. Math. Soc. 75(1969), 100-103. MR 38, no. 2104. 119. 142 RODRIQ)ES, G. 1. Sul problema dei divisori d1 Titchmarsh, Bolletino Unione Math. Italiana (3), 20(1965), 358-366. MR 33, no. 5574. ROSSER, J. B. , and SCHOENFELD, L. 1• Approximate fonnulas for some functions of prime numbers, Illinois J. Math. 6 (1962 ), 64-94. MR 25, no. 1139· ROTH, K. F. 1. On the large sieves of Linnik and Renyi, Mathematika 12 ( 1965), 1-9· MR 33, no. 5589. 2. The Large Sieve, Imperial College of Science and Technology, Univ. of London, 1968. MR 38, no. 5740. SAMANDAROV, A. G• 1. The large sieve in algebraic number fields, Mat. Zametki 2 (1967), 673-680. (Russian). MR 36, no. 6379· 2. Equidistribution of prime ideals in classes H mod f 1 Dokl. Akad. Nauk Tadzik SSR 11(1968), no. 2, 11-13. (Russian). MR 37, no. 1341. SCHALL, W. 1. On the large sieve method in algebraic number fields, J . of Number Theory 3(1970), 249-270. SCH:lliZEL, A. 1. On the congruence ax= b (mod p), Bull. Acad. Polan. Sciences 8(1960), 307-309· MR 23, no. A2377· SCHNIRELMANN, L. G. 1. tiber additive Eigenschaften von Zahlen, Math. Annalen 107(1933), 649-690. 143 SELBERG, A. 1. On an elementary method in the theory of primes, Norske Vid. Selsk. Forh. Trondheim 19, {18) (1947), 64-67. 2. MR 9-271. On elementary methods in prime number theory and their limitations, 11, Skand. Mat. Kongr., Trondheim 1949, 13-22. 3· MR 14-726. The general sieve method and its place in prime number theory, Proc. Inter. Congr., Cambridge, Mass. {1950), 286-292. SHAPIRO, H. N. 1 and WARGA, T. 1. On the representation of large integers as MR 13-438. sums of primes. I., Comm. Pure Appl. Math. 3 (1950), 153-176, MR 12-244. TARTAKOVSKII 1 V. A· 1. La methode du crible approximatif "elect if" 1 Dokl. Akad. Nauk SSSR, 23(1939), 127-130. 2. The sievemethod in group theory, Mat. Sb. N. S. 25(67) {1949), 3-50 = Amer. Math. Soc. Translations, no. 60(1952). MR 11-493· 3· Application of the sieve method to the solution of the word problem for certain types of groups, Mat. Sb. N.S. 25(67) {1949), 251-274 = Amer. Math. Soc. Translations, no. 60 (1952). MR 13-528. TCHUDAKOV, N• G. 1. The density of even numbers which cannot be represented as the sum of two primes, Izv. Akad. Nauk SSSR Ser. Mat. Nauk, no. 1 {1938), 25-40. (Russian). TCHULANOVSKI, I. V. 1. Certain estimates connected with a new method of Selberg in elementary number theory, Dokl. Akad. Nauk SSSR N.S. 63(1948), 491-494. (Russian). MR 10-355· TITCHMARSH, E. C. 1. The Theory of the Riemann Zeta-function, Oxford, 1951. MR 13-741. TOOASHI, A. , and UCHIYAMA, S. 1. On the representation of large even integers as sums of two almost primes. I., J. Fac. Sci. Hokkaido Univ., Ser. I, 18(1964), 60-68 . MR 29, no. 3420. 144 , 'IDRAN, P. 1. Certain function-theoretic sieve methods in the theory of numbers, Dokl. Akad. Nauk SSSR 171 ( 1966), 1289-1292 = Soviet Math. Doklady 7(1966), 1661-1662. MR 34, no. 5781. UCHIYAMA, M., and UCHIYAMA, S. 1. On the representation of large even integers as sums of a prime and an almost prime, Proc. Japan Akad. 40(1964), 150-154. MR 29, no. 2234. UCHIYAMA , S • 1. A note on the sieve method of A. Selberg, J. Fac. Sci. Hokkaido Univ. Ser. I, 16{1962), 189-192. MR 27, no. 1432. 2. A further note on the sieve method of A. Selberg, J. Fac. Sci. Hokkaido Univ., Ser I, 17{1963), 79-83. 3· MR 29, no. 1196. On a theorem concerning the distribution of almost primes, J. Fac. Sci. Hokkaido Univ., Ser I, 17(1963), 152-159· 4. MR 28, no. 2101. On the distribution of almost primes in an arithmetic progression, J. Fac. Sci. Hokkaido Univ., Ser. I, 18(1964), 1-22. 5. MR 30, no. 1108. On the representation of large even integers as sums of two almost primes. II., J. Fac. Sci. Hokkaido Univ., Ser. I, 18{1964), 69-77· MR 29, no. 3421. 6. On the representation of large even integers as sums of a prime and an almost prime, II., Proc. Japan Acad. 43{1967), 567-571. MR 37, no.179. USPENSKY, J. V., and HEASLET, M.A. 1. Elementary Number Theory, New York, 1939· VINOORAOOV, A I. 1. On numbers with small prime divisors, Dokl. Akad. Nauk SSSR N.S. 109{1956), 683-686. {Russian). MR 19-16. 2. Application of C(s) to the sieve of Eratosthenes, Mat. Sb. N.S. 41(83) {1957), 49-80 (+ 415-416) c Amer. Math. Soc. Translations, ser. 2 , 13(1960), 29-60. MR 20, no. 3836. 145 VINOGRADOV, A. I. - continued 3. The sieve method in algebraic fields. Lower bounds, Mat. Sb. N.S. 64(1964) 1 52-78. 4. (Russian). MR 29, no. 1195. The density conjecture for Dirichlet L-series, rzv. Akad. Nauk SSSR, Ser. Mat. 29(1965), 903-934 + 30(1966), 719-720. (Russian). MR 33, no. 2607 + 33, no. 5579· VINOGRADOV, I. M. 1. The Method of Trigoncmetric Sums in the Theory of Numbers, New York, 1954. MR 15-941. WANG, Y. 1. On the representation of R large even integer as a sum of a prime and a product of at most 4 primes, Acta Math . Sinica 6(1956), 565-582. (Chinese) . 2. MR 201 no.4530. On sieve methods and some of their applications, Science Record N.S. 1 (3)(1957), 1-5. 3· On sieve methods and same of the related problems, Sci. Record N.s. 1 (1957), 9-12. 4. MR 19-533· MR 23, no. A24oo. On the representation of a large even number as a sum of two almost primes, Sci. Record N.S. 1(1957), 291-295· (Chinese). 5. On some properties of integral valued polynomials, Advancement in Math. 3(1957), 416-423. (Chinese). 6. MR 20, no. 4531. On sieve methods and some of their applications, Acta Math. Sinica 8(1958), 413-429 = Sientia Sinica 8(1959), 357-381. + 21, no. 1958. 7. MR 21, no. 4944 A note on the least primitive root of a prime, Sci. Record N.S. 3(1959), 174-179· 8. MR 23, no. A874. (Chinese) . MR 24, no. A1894. On sieve methods and some of their applications, Acta Math. Sinica 9(1959), 87-100 = Scientia Sinica 11(1962), 1607-1624. MR 21, no. 5615 and 26, no. 3685. 9· On the representation of a large integer as a sum of a prime and an almost prime, Acta Math. Sinica 10(1960), 168-181 = Chinese Math.Acta 1(1962), 181-195· MR 27, no. 1424 and 5733· 146 WARLIMONT, R. 1. On squarefree numbers in arithmetic progressions, Monatsh. Math. 73(1969), 433-448. 2. MR 41, no. 3430. On divisor problems in connection with squarefree Monatsh. Math. 74(1970) 1 154-165. numbers, MR 41, no. 3431. WILSON, R. J. 1. The large sieve in algebraic number fields, Mathematika 16 (1969), 189-204. wmsmG, E. 1. II Uber die Zahlen, deren Primteiler einer gegebener Menge angehBren, Archiv. Math. 7(1956), 263-272. 2. Das asymptotischeVerhalten von Summen Uber multiplikative Funktionen, Math. Ann. 143(1961), 75-102. 3. MR 18-642. MR 24 1 no. A1241. Elementare Beweise des Primzahlsatzes mit Restglied. I., J. Reine Angew. Math. 211(1962) 1 205-214. 4. MR 27, no. 119. Elementare Beweise des Primzahlsatzes mit Restglied. II., J. Reine Angew. Math. 214/215(1964), 1-18. MR 29, no. 3457 · 5· Da.s asymptotische Verhalten von fummen Uber multiplikative Funktionen. II., Acta Math. Hung. 18(1967) 1 411-467. WOLKE, D. 1. A note on the least prime quadratic residue (mod p), Acta Arith . 16(1969/70), 85-87. 2. MR 39, no. 6842. Farey-Bruche mit primem Nenner und das grosse Sieb, Math. z. 114(1970) 1 145-158. MR 41, no. 5328.