Distribution of Missing Sums in Sumsets

For a finite set of integers X, define its sumset X+X to be {x+y:x, yX}. In a recent paper, Martin and O'Bryant investigated the distribution of |A+A| given the uniform distribution on subsets A{0, 1, ..., n1}. They also conjectured the existence of a limiting distribution for |A+A| and showed that the expectation of |A+A| is . Zhao proved that the limits exist, and that Sigma(k0)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 seven 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 that . New difficulties arise in the form of weak dependence between events of the form {xA+A}, {yA+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.