Ergebnisse der Mathematik Volume 43 und ihrer Grenzgebiete 3. Folge A Series of Modern Surveys in Mathematics Editorial Board S. Feferman, Stanford M. Gromov, Bures-sur-Yvette J. Jost, Leipzig J. Kolhir, Princeton H.W. Lenstra, Jr., Berkeley P.-L. Lions, Paris M. Rapoport, K61n J.Tits, Paris D. B. Zagier, Bonn Managing Editor R. Remmert, Mtinster Springer-Verlag Berlin Heidelberg GmbH George Greaves Sieves in Number Theory , Springer George Greaves School of Mathematics U niversity of Wales Senghennydd Road CardiffCF244YH Wales, U.K. e-mail: [email protected] Library of Congress Cataloging-in-Publication Data applied for Die Deutsche Bibliothek -CIP-Einheitsaufnahme Greaves, George: Sieves in number theory / George Greaves. (Ergebnisse der Mathematik und ihrer Grenzgebiete ; Folge 3, VoI. 43) ISBN 978-3-642-07495-0 ISBN 978-3-662-04658-6 (eBook) DOI 10.1007/978-3-662-04658-6 Mathematics Subject Classification (2000): llN35 ISSN 0071-1136 ISBN 978-3-642-07495-0 This work is subject to copyright. AII rights are reserved. whether the whole or part of the materi al is concemed. specifically the rights of translation. reprinting. reuse of illustrations. recitation. broadcasting. reproduction on microfilms or in any other ways. and storage in data banks. Dupli cation of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9.1965. in its current version. and permission for use must always be obtained from Springer-Verlag Berlin Heidelberg GmbH. Violations are liable for prosecution under the German Copyright Law. http://www.springer.de © Springer-Verlag Berlin Heidelberg 2001 Originally published by Springer-Veriag Berlin Heidelberg New York in 2001 Softcover reprint of the hardcover 1st edition 2001 Typeset by the author using a Springer T EX macro package. Printed on acid-free paper SPIN 10746941 44f3142LK -5 43 210 Preface Slightly more than 25 years ago, the first text devoted entirely to sieve meth ods made its appearance, rapidly to become a standard source and reference in the subject. The book of H. Halberstam and H.-E. Richert had actually been conceived in the mid-1960's. The initial stimulus had been provided by the paper of W. B. Jurkat and Richert, which determined the sifting limit for the linear sieve, using a combination of the ,A2 method of A. Selberg with combinatorial ideas which were in themselves of great importance and in terest. One of the declared objectives in writing their book was to place on record the sharpest form of what they called Selberg sieve theory available at the time. At the same time combinatorial methods were not neglected, and Halber stam and Richert included an account of the purely combinatorial method of Brun, which they believed to be worthy of further examination. Necessar ily they included only a briefer mention of the development of these ideas due (independently) to J. B. Rosser and H. Iwaniec that became generally available around 1971. These combinatorial notions have played a central part in subsequent developments, most notably in the papers of Iwaniec, and a further account may be thought to be timely. There have also been some developments in the theory of the so-called sieve with weights, and an account of these will also be included in this book. The author's aim is to present a self-contained account of the "small" sieve method associated with the names of Brun, Selberg and their successors in a form that will be suitable for university graduates making their first acquaintance with the subject, leading them towards the frontiers of modern researches and unsolved problems in the subject area. This book could not have reached its present form without assistance and guidance that has been received from a number of sources. In particular the author is indebted to Henryk Iwaniec for making available valuable un published material in the form of lecture notes prepared in connection with courses given to graduate students at Rutgers University. N otation and Layout Theorems, lemmas and displays will be numbered consecutively and inde pendently within sections, and referred to from outside the section in which they appear by prefixing their reference number with their section number. For example Theorem 1 in Section 3.2 is referred to as Theorem 1 from within Section 3.2 and as Theorem 3.2.1 from elsewhere. Since section numbers ap pear in the running heads the reader will be able to locate any numbered entry quickly and without ambiguity. There are several notations and conventions that are used so regularly throughout the book that explicit reference to them every time they are used would become tedious. The pages on which some of these are introduced are indicated in the following table. List of Sieve N otations The Function S(a, P) ...................................... 13 The Set Ad ............................................... 14 The Sum S(A, P) ......................................... 14 The Remainders r A(d) ..................................... 19 The Function p ........................................... 19 The Level D .............................................. 20 The Product V(P) ........................................ 22 The Sifting Density /î, ...................................... 28 The Constants K and L .................................... 28 The Sifting Limit (3(/î,) ..................................... 37 Other notations that are standard in Number Theory are freely employed: J.L for the M6bius function, ~ for Euler's function, and so ono Frequently these are also explained on their first use. The total number of prime factors of n has, as usual, been denoted by il(n) , but we write v(n) for the number of distinct prime factors. Bibliographic information, historical remarks, supplementary information and the like are for the most part given in the notes at the end of each chapter where they will not interrupt the flow of the main text. The author wishes to make the usual disclaimer is respect of some of his historical remarks: he VIII Notation and Layout is not a historian, and has not consulted the primary source in connection with aH assertions made. If an intermediate secondary source has made an erroneous statement there is a possibility that it is repeated somewhere in this book. The "author, year" system of references to published material is used. A year given in brackets will refer to a date of publication. Table of Contents Introduction ................................................ 1 1. The Structure of Sifting Arguments ..................... 7 1.1 The Sieves of Eratosthenes and Legendre ................ 7 1.1.1 The Contribution of Eratosthenes ................. 7 1.1.2 Legendre's Sieve ................................ 8 1.1.3 An Estimate for 7r(X) ........................... 10 1.1.4 The Distribution of Primes ...................... 12 1.2 Examples of Sifting Situations .......................... 13 1.2.1 Notations ...................................... 13 1.2.2 The Integers in an Interval (Y - X, Y 1 ............ 14 1.2.3 Numbers Given by Polynomial Expressions ........ 15 1.2.4 Arithmetic Progressions ......................... 16 1.2.5 Sums of Two Squares ........................... 17 1.2.6 Polynomials with Prime Arguments ............... 17 1.3 A General Formulation of a Sifting Situation ............. 19 1.3.1 The Basic Formulation .......................... 19 1.3.2 Legendre's Sieve in a General Setting ............. 23 1.3.3 A Generalised Formulation ....................... 25 1.3.4 A Further Generalisation ........................ 26 1.3.5 Sifting Density ................................. 27 1.3.6 The Sifting Limit (3(K,) .......................... 37 1.3.7 Composition of Sieves ........................... 37 1.4 Notes on Chapter 1 ................................... 39 2. Selberg's Upper Bound Method ......................... 41 2.1 The Sifting Apparatus ................................. 42 2.1.1 Selberg's Theorem .............................. 42 2.1.2 The Numbers A(d) .............................. 46 2.1.3 A Simple Application ........................... 49 2.2 General Estimates of G(x) and E(D, P) ................. 50 2.2.1 An Estimate by Rankin's Device ................. 51 2.2.2 Asymptotic Formulas ........................... 54 2.2.3 The Error Term ................................ 60 X Table of Contents 2.3 Applications ......................................... 63 2.3.1 Arithmetic Progressions ......................... 63 2.3.2 Prime Twins and Goldbach's Problem ............. 64 2.3.3 Polynomial Sequences ........................... 66 2.4 Notes on Chapter 2 ................................... 68 3. Combinatorial Methods ................................. 71 3.1 The Construction of Combinatorial Sieves ............... 72 3.1.1 Preliminary Discussion of Brun's Ideas ............ 72 3.1.2 Fundamental Inequalities and Identities ........... 73 3.1.3 Buchstab's Identity ............................. 77 3.1.4 The Combinatorial Sieve Lemma ................. 78 3.2 Brun's Pure Sieve ..................................... 79 3.2.1 Inequalities and Identities ....................... 80 3.2.2 The "Pure Sieve" Theorem ...................... 81 3.2.3 A Corollary .................................... 83 3.2.4 Prime Twins ................................... 84 3.3 A Modern Edition of Brun's Sieve ...................... 85 3.3.1 Rosser's Choice of X ............................ 86 3.3.2 A Technical Estimate ........................... 87 3.3.3 A Simplifying Approximation .................... 88 3.3.4 A Combinatorial Sieve Theorem .................. 89 3.3.5 Applications ................................... 94 3.4 Brun's Version of his Method .......................... 96 3.4.1 Brun's Choice of X .............................. 96 3.4.2 The Estimations ................................ 97 3.4.3 The Result .................................... 98 3.5 Notes on Chapter 3 ................................... 100 4. Rosser's Sieve ........................................... 103 4.1 Approximations by Continuous Functions ................ 105 4.1.1 The Recurrence Relations ....................... 106 4.1.2 Partial Summation ............................. 108 4.1.3 The Leading Terms ............................. llO 4.2 The Functions F and 1 ................................ 113 4.2.1 The Difference-Differential Equations ............. ll3 4.2.2 The Adjoint Equation and the Inner Product ll5 4.2.3 Solutions of the Adjoint Equation ................ ll7 4.2.4 Particular Values of F(8) and 1(8) ................ 124 4.2.5 Asymptotic Analysis as K, -+ 00 ................... 129 4.3 The Convergence Problem ............................. 134 4.3.1 The Auxiliary Functions ......................... 135 4.3.2 Adjoints and Inner Products .. ;.................. 137 4.3.3 The Case K, :::; ~ •••••••••••••••••••••••••••••••• 141 Table of Contents XI 4.4 A Sieve Theorem Following Rosser ...................... 144 4.4.1 The Case", > ~: a First Result ................... 145 4.4.2 Theorem 1 when '" ~ ~ .......................... 148 4.4.3 An Improved Version of Proposition 1 ............. 150 4.4.4 A Two-Sided Estimate .......................... 156 4.5 Extrema! Examples ................................... 158 4.5.1 The Linear Case ................................ 158 = ................................ 4.5.2 The Case", ~ 164 4.6 Notes on Chapter 4 ................................... 167 5. The Sieve with Weights ................................. 173 5.1 Simpler Weighting Devices ............................. 176 5.1.1 Logarithmic Weights ............................ 176 5.1.2 Modified Logarithmic Weights .................... 179 5.1.3 Some Applications .............................. 184 5.2 More Elaborate Weighted Sieves ........................ 185 5.2.1 An Improved Weighting Device ................... 186 5.2.2 Buchstab's Weights ............................. 188 5.3 A Weighted Sieve Following Rosser ..................... 193 5.3.1 Combining Sieving and Weighting ................ 194 5.3.2 The Reduction Identities ........................ 202 5.3.3 An Identity for the Main Term ................... 205 5.3.4 The Estimate for the Main Term ................. 210 5.4 Notes on Chapter 5 ................................... 216 6. The Remainder Term in the Linear Sieve ............... 223 6.1 The Bilinear Nature of Rosser's Construction ............. 226 6.1.1 The Factorisation of XD ......................... 227 6.1.2 Discretisations of Rosser's Sieve .................. 229 6.1.3 Specification of Details .......................... 234 6.1.4 The Leading Contributions to the Main Term ...... 238 6.1.5 Composition of Sieves ........................... 241 6.1.6 The Remainder Term ........................... 243 6.2 Sifting Short Intervals ................................. 245 6.2.1 The Smoothed Formulation ...................... 246 6.2.2 The Remainder Sums ........................... 250 6.2.3 Trigonometrical Sums ........................... 252 6.3 Notes on Chapter 6 ................................... 256 > 7. Lower Bound Sieves when 1 ........................ 259 t;, 7.1 An Extension of Selberg's Upper Bound ................. 260 7.1.1 The Integral Equation and the Function 0-(8) ....... 261 7.1.2 The Estimation of CA8) ........................ 265