Generalizing the Distribution of Missing Sums in Sumsets

Abstract

Given a finite set of integers $A$, its sumset is $A+A:=\{a_i+a_j\mid a_i,a_j\in A\}$. We examine $|A+A|$ as a random variable, where $A\subset I_n=[0,n-1]$, the set of integers from 0 to $n-1$, so that each element of $I_n$ is in $A$ with a fixed probability $p\in (0,1)$. Recently, Martin and O'Bryant studied the case in which $p=1/2$ and found a closed form for $\mathbb{E}[|A+A|]$. Lazarev, Miller, and O'Bryant extended the result to find a numerical estimate for $\text{Var}(|A+A|)$ and bounds on the number of missing sums in $A+A$, $m_{n;p}(k):=\mathbb{P}(2n-1-|A+A|=k)$. Their primary tool was a graph-theoretic framework which we now generalize to provide a closed form for $\mathbb{E}[|A+A|]$ and $\text{Var}(|A+A|)$ for all $p\in (0,1)$ and establish good bounds for $\mathbb{E}[|A+A|]$ and $m_{n;p}(k)$. We continue to investigate $m_{n;p}(k)$ by studying $m_p(k)={\lim }_{n\to \infty }{m}_{n;p}(k)$, proven to exist by Zhao. Lazarev, Miller, and O'Bryant proved that, for $p=1/2$, $m_{1/2}(6)>m_{1/2}(7)<m_{1/2}(8)$. This distribution is not unimodal, and is said to have a "divot" at 7. We report results investigating this divot as $p$ varies, and through both theoretical and numerical analysis, prove that for $p\ge 0.68$ there is a divot at $1$; that is, $m_p(0)>m_p(1)<m_p(2)$. Finally, we extend the graph-theoretic framework originally introduced by Lazarev, Miller, and O'Bryant to correlated sumsets $A+B$ where $B$ is correlated to $A$ by the probabilities $\mathbb{P}(i\in B\mid i\in A)=p_1$ and $\mathbb{P}(i\in B\mid i\notin A)=p_2$. We provide some preliminary results using the extension of this framework.

Version 1.0, 35 pages, 14 figures

References in corpus (6)

• Constructing MSTD Sets Using Bidirectional Ballot Sequences
• Sets Characterized by Missing Sums and Differences
• When Sets Can and Cannot Have MSTD Subsets
• Generalizations of a Curious Family of MSTD Sets Hidden By Interior Blocks
• Distribution of missing differences in diffsets
• Coordinate sum and difference sets of $d$-dimensional modular hyperbolas