Distribution of Missing Sums in Sumsets

Oleg Lazarev, Steven J. Miller, Kevin O'Bryant

Published 2011-09-22, updated 2012-12-21Version 3

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.