Generalization of a Theorem of Erdos and Renyi on Sidon Sequences

作者：Cilleruelo Javier^*; Kiss Sandor Z; Ruzsa Imre Z; Vinuesa Carlos

来源：Random Structures and Algorithms, 2010, 37(4): 455-464.

DOI：10.1002/rsa.20350

• Sidon sequences
• the probabilistic method

Erdos and Renyi claimed and Vu proved that for all h >= 2 and for all epsilon > 0, there exists g = g(h)(epsilon) and a sequence of integers A such that the number of ordered representations of any number as a sum of h elements of A is bounded by g, and such that vertical bar A boolean AND [1, x]vertical bar >> x(1/h-epsilon).
We give two new proofs of this result. The first one consists of an explicit construction of such a sequence. The second one is probabilistic and shows the existence of such a g that satisfies g(h)(epsilon) << epsilon(-1), improving the bound g(h)(epsilon) << epsilon(-h+1) obtained by Vu.
Finally we use the "alteration method" to get a better bound for g(3)(epsilon), obtaining a more precise estimate for the growth of B(3)[g] sequences.

• 出版日期2010-12