Sumsets and differencesets of uniformly random subsets of {1,2,...,n}

For each subset A of {1,2,...,n}, let X(A)=2n-1-|A+A|, and let p_k be the number of A such that X(A)=k, i.e., the scaled probability that a random subset A has a sumset that is missing exactly k elements. I will outline a proof that p_8>p_6>p_7. In other words, sumsets prefer to miss 6 or 8 elements rather than 7. As an encore, let k,j be nonnegative integers and let q_{k,j} be the number of subsets of {1,2,...,n} whose sumset is missing exactly k elements and whose difference set is missing exactly 2j elements. I will prove that q_{k,j}/2^n has a limit as n goes to infinity, and that the limit is positive. This talk encompasses joint work with Greg Martin and Peter Hagerty.

Kevin O'Bryant