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 (ai+aj\ne ak). 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 c2n/2 for some absolute constant c. (b) Sidon sequences (ai+aj\ne ak+a\ell for { i,j}\ne {k,\ell }. (c) All partial sums distinct (sum \epsiloniai are distinct, \epsiloni = 0,1).
(ii) (a) Product-free sequences (aiaj\ne ak). (b) Pairwise products distinct, and related constraints.
(iii) (a) Requiring divisibility (ai | aj for i < j). (b) Forbidding divisibility (ai\nmid aj for i\ne j). (c) Any two terms coprime. (d) No two terms coprime.
(iv) (a) (ai+aj)\nmid aiaj. (b) No k-term arithmetic progression. (c) sum 1/ai \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