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

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