##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 207.35901

**Autor: ** Erdös, Paul; Rényi, Alfréd

**Title: ** Some remarks on the large sieve of Yu. V. Linnik (In English)

**Source: ** Ann. Univ. Sci. Budapest. Rolando Eötvös, Sect. Math. 11, 3-13 (1968).

**Review: ** The authors use probabilistic arguments to prove some results concerning the Yu. V. Linnik large sieve method in number theory, and discuss some related open problems. The main result is described in the last paragraph. Let S_{N} be a sequence of Z positive integers < N, and let Z(a,p) = \# **{**x in S_{N}: x \equiv a(mod p) **}**. Set \Delta ^{2}(p) = **sum** ^{p = 1}_{a = 0} p(Z(a,p)- ^{Z}/_{p})^{2}. p is always prime in what follows. In the first probabilistic approach to the large sieve method, *A. Rényi* [Compos. Math. 8, 68-75 (1950; Zbl 034.02403)] established the estimate **sum**_{p \leq Q} \Delta ^{2}(p) = O(Z(Q^{3}+N)) for Q \leq \sqrt N, which, compared to the then known estimate, was better for Q \leq N^{3/8}, and weaker for Q > N^{3/8}. *E. Bombieri* [Mathematika, London 12, 201-225 (1965; Zbl 136.33004)] has shown that **sum**_{p \leq Q} \Delta^{2}(p) = O(Z(Q^{2}+N)) and *P. X. Gallagher* [ibid. 14, 14-20 (1967; Zbl 163.04401)] that

**sum**_{p \leq Q}\Delta ^{2}(p) \leq Z(Q^{2}+\pi N) if Q \leq \sqrt N . (*) The authors deduce from their main (probabilistic) theorem, which, roughly, states that for the large majority of all sequences S_{N}, **sum**_{p \leq Q} \Delta^{2}(p) is of the order NQ^{2}/(8 log Q)+O(NQ^{2}/ log^{2}Q), that the inequality (*) is not true for all S_{N} if Q is of larger order of magnitude than \sqrt{N log N}. This fact had been mentioned without proof by *P. Erdös* [Mat. Lapok 17, 135-155 (1966; Zbl 146.27201)]. Unfortunately, the standard probabilistic methods used cannot, as the authors point out, answer the still open question whether or not (*) holds for all sequences S_{N} if \sqrt N \leq Q \leq \sqrt{N log N}.

**Reviewer: ** O.P.Stackelberg

**Classif.: ** * 11N35 Sieves

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag