{
  "id": "0911.2870",
  "version": "v1",
  "published": "2009-11-15T13:41:49.000Z",
  "updated": "2009-11-15T13:41:49.000Z",
  "title": "Generalization of a theorem of Erdos and Renyi on Sidon Sequences",
  "authors": [
    "Javier Cilleruelo",
    "Sandor Z. Kiss",
    "Imre Z. Ruzsa",
    "Carlos Vinuesa"
  ],
  "comment": "12 pages, no figures",
  "categories": [
    "math.NT",
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-11-15T13:41:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11B50",
      "11B34"
    ],
    "keywords": [
      "sidon sequences",
      "generalization",
      "precise estimate",
      "explicit construction",
      "alteration method"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0911.2870C"
    }
  }
}