Generalizing the distribution of missing sums in sumsets

DOI10.1016/J.JNT.2021.10.016MaRDI QIDQ2672014zbMATH OpenOpenAlexWikidataFDO

Authors Hùng Viẹt Chu, Dylan A. King, Noah Luntzlara, Thomas C. Martinez, Steven J. Miller, L. Shao, Chenyang Sun, Victor Xu

Publication date 8 June 2022

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.07981

zbMATH Keywords

correlated setsdivotindependent setsmore sums than differences setssumsets

Mathematics Subject Classification ID

Additive bases, including sumsets (11B13) Other combinatorial number theory (11B75)

Abstract: Given a finite set of integers $A$, its sumset is $A+A:=a_i+a_{j}mid{a}_i,a_{j}inA$. We examine $|A+A|$ as a random variable, where $Asubset{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 $pin(0,1)$. Recently, Martin and O'Bryant studied the case in which $p=1/2$ and found a closed form for $mathbbE[|A+A|]$. Lazarev, Miller, and O'Bryant extended the result to find a numerical estimate for $extVar(|A+A|)$ and bounds on the number of missing sums in $A+A$, $m_{n,;,p}(k):=mathbbP(2n-1-|A+A|=k)$. Their primary tool was a graph-theoretic framework which we now generalize to provide a closed form for $mathbbE[|A+A|]$ and $extVar(|A+A|)$ for all $pin(0,1)$ and establish good bounds for $mathbbE[|A+A|]$ and $m_{n,;,p}(k)$. We continue to investigate $m_{n,;,p}(k)$ by studying $m_p(k)=li{m}_{noinfty}{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 $pgeq0.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 $mathbbP(iinBmidiinA)=p_1$ and $mathbbP(iinBmidiotinA)=p_2$. We provide some preliminary results using the extension of this framework.

Review text

A natural question in the area of combinatorial number theory is the following: given \(p \in (0, 1)\), construct the set \(A \subseteq \{0,\dots, n-1\}\) by taking each \(i\) in \(A\) independently with probability \(p\). The question is then to study \(|A+A|\). The study of the expectation of \(|A+A|\) was initiated by Martin and O'Bryant, who obtained the expected value for \(p=1/2\). Lazarev, Miller, and O'Bryant [\textit{O. Lazarev} et al., Exp. Math. 22, No. 2, 132--156 (2013; Zbl 1309.11010)] extended this result by studying the variance of the random variable \(|A+A|\) for \(p=1/2\), as well as bounds on the number of missing sums in \(A+A\). This paper continues this investigation by studying the variance for \(p\neq 1/2\), as well as missing sums distribution.

Recommendations

• Distribution of Missing Sums in Sumsets
• Sums and differences of correlated random sets
• Distribution of Missing Differences in Diffsets
• On the number of sums and differences
• Sets characterized by missing sums and differences

Cites work

• Constructing MSTD sets using bidirectional ballot sequences
• Coordinate sum and difference sets of d-dimensional modular hyperbolas
• Distribution of Missing Sums in Sumsets
• Explicit constructions of infinite families of MSTD sets
• Explicit constructions of infinite families of MSTD sets
• Explicit constructions of large families of generalized more sums than differences sets
• Fringe pairs in generalized MSTD sets
• Generalizations of a curious family of MSTD sets hidden by interior blocks
• Generalized more sums than differences sets
• scientific article; zbMATH DE number 3873442 (Why is no real title available?)
• scientific article; zbMATH DE number 3595193 (Why is no real title available?)
• Many sets have more sums than differences
• Most subsets are balanced in finite groups
• On A Conjecture of Conway
• On Conway's Conjecture for Integer Sets
• On sets with more restricted sums than differences
• On the number of sums and differences
• Problems in additive number theory. I
• Sets characterized by missing sums and differences
• Sets with more sums than differences
• Some explicit constructions of sets with more sums than differences
• Sums and differences of correlated random sets
• When almost all sets are difference dominated
• When almost all sets are difference dominated in \(\mathbb{Z}/n\mathbb{Z}\)
• When sets can and cannot have sum-dominant subsets

Cited in

(3)

• Sums and differences of correlated random sets
• Distribution of Missing Differences in Diffsets
• Distribution of Missing Sums in Sumsets

This page was built for publication: Generalizing the distribution of missing sums in sumsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2672014)