and also, for infinite primitive sequences,

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₁,A₂, ... ,A_k (with k > C₁ · 2ⁿ · 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₁,B₂, ... ,B_l those subsets of S, that contain at least one A_i (1 \leq i \leq k). Then 1 > C₂ · 2ⁿ, with some C₂ = C₂(C₁). 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