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 SN be a sequence of Z positive integers < N, and let Z(a,p) = \# {x in SN: x \equiv a(mod p) }. Set

\Delta 2(p) = sum p = 1a = 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 sump \leq Q \Delta 2(p) = O(Z(Q3+N)) for Q \leq \sqrt N, which, compared to the then known estimate, was better for Q \leq N3/8, and weaker for Q > N3/8. E. Bombieri [Mathematika, London 12, 201-225 (1965; Zbl 136.33004)] has shown that sump \leq Q \Delta2(p) = O(Z(Q2+N)) and P. X. Gallagher [ibid. 14, 14-20 (1967; Zbl 163.04401)] that

sump \leq Q\Delta 2(p) \leq Z(Q2+\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 SN, sump \leq Q \Delta2(p) is of the order NQ2/(8 log Q)+O(NQ2/ log2Q), that the inequality (*) is not true for all SN 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 SN if \sqrt N \leq Q \leq \sqrt{N log N}.
Reviewer:  O.P.Stackelberg
Classif.:  * 11N35 Sieves

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page