{
  "id": "1109.4700",
  "version": "v3",
  "published": "2011-09-22T04:31:00.000Z",
  "updated": "2012-12-21T04:38:02.000Z",
  "title": "Distribution of Missing Sums in Sumsets",
  "authors": [
    "Oleg Lazarev",
    "Steven J. Miller",
    "Kevin O'Bryant"
  ],
  "comment": "To appear in Experimental Mathematics. Version 3. Larger computations than before, conclusively proving the divot exists. 40 pages, 15 figures",
  "categories": [
    "math.NT"
  ],
  "abstract": "For any finite set of integers X, define its sumset X+X to be {x+y: x, y in X}. In a recent paper, Martin and O'Bryant investigated the distribution of |A+A| given the uniform distribution on subsets A of {0, 1, ..., n-1}. They also conjectured the existence of a limiting distribution for |A+A| and showed that the expectation of |A+A| is 2n - 11 + O((3/4)^{n/2}). Zhao proved that the limits m(k) := lim_{n --> oo} Prob(2n-1-|A+A|=k) exist, and that sum_{k >= 0} m(k)=1. We continue this program and give exponentially decaying upper and lower bounds on m(k), and sharp bounds on m(k) for small k. Surprisingly, the distribution is at least bimodal; sumsets have an unexpected bias against missing exactly 7 sums. The proof of the latter is by reduction to questions on the distribution of related random variables, with large scale numerical computations a key ingredient in the analysis. We also derive an explicit formula for the variance of |A+A| in terms of Fibonacci numbers, finding Var(|A+A|) is approximately 35.9658. New difficulties arise in the form of weak dependence between events of the form {x in A+A}, {y in A+A}. We surmount these obstructions by translating the problem to graph theory. This approach also yields good bounds on the probability for A+A missing a consecutive block of length k.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2012-12-21T04:38:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11P99",
      "11K99"
    ],
    "keywords": [
      "missing sums",
      "large scale numerical computations",
      "difficulties arise",
      "related random variables",
      "fibonacci numbers"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 40,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.4700L"
    }
  }
}