Distribution of Missing Sums in Sumsets

Abstract

For a finite set of integers X, define its sumset X+X to be {x+y:x, y∈X}. In a recent paper, Martin and O’Bryant investigated the distribution of |A+A| given the uniform distribution on subsets A⊆{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 . Zhao proved that the limits exist, and that ∑ _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 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 {x∈A+A}, {y∈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.

2000 AMS Subject Classification:

• Primary 11P99
• Secondary 11K99

Keywords:

• sumsets
• uniformly random sumsets
• Fekete’s lemma

Acknowledgments

We thank the participants of the SMALL 2011 REU at Williams College for many enlightening conversations, and the referee for many helpful comments on an earlier draft. Oleg Lazarev was supported by NSF grants DMS0850577 and Williams College. Steven J. Miller was partially supported by NSF grant DMS0970067. This research was supported in part under National Science Foundation Grants CNS-0958379 and CNS-0855217 and the City University of New York High Performance Computing Center.