##
**Zentralblatt MATH**

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

**Zbl.No: ** 695.10048

**Autor: ** Cameron, Peter J.; Erdös, Paul

**Title: ** On the number of sets of integers with various properties. (In English)

**Source: ** Number theory, Proc. 1st Conf. Can. Number Theory Assoc., Banff/Alberta (Can.) 1988, 61-79 (1990).

**Review: ** [For the entire collection see Zbl 689.00005.]

In this interesting paper, the authors investigate the general problem of determining the number of subsets of [1,n] which satisfy a given constraint. These are classified under the headings of (i) additive conditions, (ii) multiplicative conditions, (iii) divisibility and common factors and (iv) miscellaneous problems. A brief resumé is:

(i) (a) sum-free sequences (a_{i}+a_{j}\ne a_{k}). Here, for example, the authors show that the number of sum-free sequences of [1,n] whose least element is > n/3 does not exceed c2^{n/2} for some absolute constant c. (b) Sidon sequences (a_{i}+a_{j}\ne a_{k}+a_{\ell} for **{** i,j**}**\ne **{**k,\ell **}**. (c) All partial sums distinct (**sum** \epsilon_{i}a_{i} are distinct, \epsilon_{i} = 0,1).

(ii) (a) Product-free sequences (a_{i}a_{j}\ne a_{k}). (b) Pairwise products distinct, and related constraints.

(iii) (a) Requiring divisibility (a_{i} | a_{j} for i < j). (b) Forbidding divisibility (a_{i}\nmid a_{j} for i\ne j). (c) Any two terms coprime. (d) No two terms coprime.

(iv) (a) (a_{i}+a_{j})\nmid a_{i}a_{j}. (b) No k-term arithmetic progression. (c) **sum** 1/a_{i} \leq s.

In each of these topics, the authors discuss the best results known, prove theorems of their own or conjecture what might be expected to be true.

**Reviewer: ** M.Nair

**Classif.: ** * 11B13 Additive bases

11B25 Arithmetic progressions

11B99 Sequences and sets

11B75 Combinatorial number theory

**Keywords: ** number of subsets; additive conditions; multiplicative conditions; divisibility; common factors; sum-free sequences; Sidon sequences; Product-free sequences; arithmetic progression

**Citations: ** Zbl 689.00005

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag