The analytic principle of the large sieve

12] has written at length concerning applications of the large sieve to number theory. Our intent here is to complement his exposition by devoting our attention to the analytic principle of the large sieve; we describe only briefly how applications to number theory are made. The large sieve was studied intensively during the decade 1965-1975, with the result that the subject has lost its mystery: We now possess a variety of simple ideas which provide very precise results and a host of variants. While the large sieve can no longer be considered deep, it nevertheless gives powerful estimates in many different settings. 1. Historical background. The large sieve originates in a short paper of Ju. V. Linnik [51]. Linnik [52] made a simple application to the distribution of quadratic nonresidues, but it was A. Rnyi [72]-[81] who systematically studied the large sieve, and who first made an important application to number theory: Using the large sieve, Rnyi [72], [73] was the first to show that every large even number In can be expressed in the form In = p + P k9 where p is prime and P k has at most k prime factors. (Rnyi did not determine a value for k, but M. B. Barban [2], [3] showed that one can take k * 4. The mean value theorem of Bombieri enables one to take k = 3, and Chen [17], [18] (see also [36], [84]