Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  841.11006
Autor:  Erdös, Paul; Sárközy, A.; Sós, V.T.
Title:  On sum sets of Sidon sets. II. (In English)
Source:  Isr. J. Math. 90, No.1-3, 221-233 (1995).
Review:  Let A\subseteq N = {1, 2,...} and SA = {a+a' | a,a' in A}. If for every n in N the equation a+a' = n; a \leq a'; a,a' in A has at most one solution then A is called a Sidon set.
At first blocks of consecutive elements in SA for Sidon sets A are studied. For n in N let H(n) = max{h in N | {m+1, m+2, ..., m+h} \subseteq SA, m \leq n} taken over all Sidon sets A\subseteq {1, 2, ..., n}. It is shown that n1/3 << H(n) << n ½. The lower bound is obtained by construction of a suitable infinite Sidon set while the upper bound is a consequence of the following much sharper result, choosing l = [200 n ½]: For all Sidon sets A\subseteq {1, 2,...,n} and all l in N, k in Z we have

| SA\cap [k+1, k+l]| < {style 1/2} l+7l ½ n1/4.

Let n in N. For A\subseteq N, | A| = n the minimum of |SA| is obtained by arithmetic progressions A and the maximum by Sidon sets A. Therefore one can expect that a well-covering of a Sidon set by arithmetic progressions is impossible, even by generalized arithmetic progressions P = {e+x1 f1+···+xm fm | xi in {1, ..., li} for i = 1,..., m}, where m,l1, ..., lm in N; e,f1, ..., fm in Z. Let dim P = m and Q(P) = l1 l2 ... lm be the dimension and size of P. A measure of well-covering for A by generalized arithmetic progressions (g.a.p.) of dimension m is given by the minimum Dm (A) of the terms tsumtj = 1 Q(Pj) taken over all coverings A\subseteq \bigcuptj = 1 Pj where Pj are g.a.p. with dim Pj = m for j = 1, ..., t. If Dm (A) is close to |A| then A can be covered by ``few'' g.a.p.. If Dm (a) is close to |A|2 we have the opposite situation. For all finite Sidon sets A it is shown that Dm(A) > 2-m-1 |A|2. On the other hand for all m in N there exists a finite Sidon set A such that Dm(A) \leq 1/2 | A|2. These two theorems are proved in a more general form for B2[g] sets.
Reviewer:  J.Zöllner (Mainz)
Classif.:  * 11B13 Additive bases
                   11B25 Arithmetic progressions
Keywords:  sum sets of Sidon sets; additive bases; B2-sequences; B2[g] sets; arithmetic progressions

© 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