Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  208.31403
Autor:  Erdös, Paul; Sárközi, A.; Szemerédi, E.
Title:  Über Folgen ganzer Zahlen. (On sequences of integers.) (In German)
Source:  Abh. Zahlentheorie Anal., 77-87 (1968).
Review:  [For the entire collection see Zbl 185.00201.]
A sequence of integers (ordered in increasing order) is said to be primitive, if no element divides another. The following results are known for primitive sequences a1 < a2 < ...:

sumai < xa-1i < c(log x)(log log x)- ½,     (1)

sumk(ak log ak)-1 < C,     (2)

and also, for infinite primitive sequences,

limx ––> oo (sumai < xa-1i ) (log x)-1(log log x) ½ = 0.    (3)

Here c and C stand for absolute constants and (1) and (3) are best possible [See F. Behrend, J. London Math. Soc. 10, 42-44 (1935; Zbl 012.05203); P. Erdös, ibid 126-128 (1935; Zbl 012.05202); the authors, J. Aust. Math. Soc. 7, 9-16 (1967; Zbl 146.27101)]. The authors also showed [J. Math. Anal. Appl. 15, 60-64 (1966; Zbl 151.03502)] that the condition of primitivity can be weakened to either (4) [ai,aj] = ar, ai < aj < ar has no solutions; or to (5) (ai,aj) = ar, ar < ai < aj has no solutions, and (1) still follows. Here [ai,aj] and (ai,aj) stand for the least common multiple and greatest common divisor, respectively. However, (4) does not imply the convergence of the series (2), while (5) does [The authors, Dokl. Akad. Nauk SSSR 176, 541-544 (1967; Zbl 159.06003)].
The purpose of the present paper is toshow that (5) also implies the validity of (3). The fairly complicated proof is subdivided into five Lemmas. These (and their proofs) are rather close to similar results in the earlier quoted work of the authors, except for Lemma 4, which may have also an independent interest: Let S be a set of n elements and A1,A2, ... ,Ak (with k > C1 · 2n · n- ½) be subsets of S. Assume also that for i,j \ne r, one never has Ai \cap Aj = Ar. Furthermore, denote by B1,B2, ... ,Bl those subsets of S, that contain at least one Ai (1 \leq i \leq k). Then 1 > C2 · 2n, with some C2 = C2(C1). The proof is inspired by D.J.Kleitman [Proc. Am. Math. Soc. 17, 139-141 (1966; Zbl 139.01004)] and uses a lemma of E.Sperner [Math. Z. 27, 544-548 (1928)].
Reviewer:  E.Grosswald
Classif.:  * 11B83 Special sequences of integers and polynomials
Citations:  Zbl 185.00201(EA)

© 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