Generalization of a theorem of Erdos and Renyi on Sidon Sequences

Abstract

Erd\H os and Ré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.

arXiv comment12 pages, no figures