##
**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 a_{1} < a_{2} < ...: **sum**_{ai < x}a^{-1}_{i} < c(log x)(log log x)^{- ½}, (1)

**sum**_{k}(a_{k} log a_{k})^{-1} < C, (2) and also, for infinite primitive sequences,

**lim**_{x ––> oo} **(****sum**_{ai < x}a^{-1}_{i} **)** (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) [a_{i},a_{j}] = a_{r}, a_{i} < a_{j} < a_{r} has no solutions; or to (5) (a_{i},a_{j}) = a_{r}, a_{r} < a_{i} < a_{j} has no solutions, and (1) still follows. Here [a_{i},a_{j}] and (a_{i},a_{j}) 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 A_{1},A_{2}, ... ,A_{k} (with k > C_{1} · 2^{n} · n^{- ½}) be subsets of S. Assume also that for i,j \ne r, one never has A_{i} \cap A_{j} = A_{r}. Furthermore, denote by B_{1},B_{2}, ... ,B_{l} those subsets of S, that contain at least one A_{i} (1 \leq i \leq k). Then 1 > C_{2} · 2^{n}, with some C_{2} = C_{2}(C_{1}). 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