Generalization of a theorem of Erdos and Renyi on Sidon Sequences

Javier Cilleruelo, Sandor Z. Kiss, Imre Z. Ruzsa, Carlos Vinuesa

Published 2009-11-15Version 1

Erd\H os and R\'{e}nyi claimed and Vu proved that for all $h \ge 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 $|A \cap [1,x]| \gg 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) \ll \epsilon^{-1}$, improving the bound $g_h(\epsilon) \ll \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.