Sums and differences of correlated random sets

DOI10.1016/J.JNT.2014.06.022zbMATH Open1394.11008arXiv1401.2588OpenAlexW2096730026MaRDI QIDQ472815FDOQ472815

Authors: Archit Kulkarni, Steven J. Miller, David Moon, Thao Do, Jake L. Wellens 

Publication date: 20 November 2014

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

Abstract: Many fundamental questions in additive number theory (such as Goldbach's conjecture, Fermat's last theorem, and the Twin Primes conjecture) can be expressed in the language of sum and difference sets. As a typical pair of elements contributes one sum and two differences, we expect that $|A-A|>|A+A|$ for a finite set $A$. However, in 2006 Martin and O'Bryant showed that a positive proportion of subsets of $0,dots,n$ are sum-dominant, and Zhao later showed that this proportion converges to a positive limit as $noinfty$. Related problems, such as constructing explicit families of sum-dominant sets, computing the value of the limiting proportion, and investigating the behavior as the probability of including a given element in $A$ to go to zero, have been analyzed extensively. We consider many of these problems in a more general setting. Instead of just one set $A$, we study sums and differences of pairs of emph{correlated} sets $(A,B)$. Specifically, we place each element $ain0,dots,n$ in $A$ with probability $p$, while $a$ goes in $B$ with probability $h{o}_1$ if $ainA$ and probability $h{o}_2$ if $aotinA$. If $|A+B|>|(A-B)cup(B-A)|$, we call the pair $(A,B)$ a emph{sum-dominant $(p,h{o}_1,h{o}_2)$-pair}. We prove that for any fixed $vecho=(p,h{o}_1,h{o}_2)$ in $(0,1{)}^3$, $(A,B)$ is a sum-dominant $(p,h{o}_1,h{o}_2)$-pair with positive probability, and show that this probability approaches a limit $P(vecho)$. Furthermore, we show that the limit function $P(vecho)$ is continuous. We also investigate what happens as $p$ decays with $n$, generalizing results of Hegarty-Miller on phase transitions. Finally, we find the smallest sizes of MSTD pairs.

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

Recommendations

• Sets with more differences than sums
• Many sets have more sums than differences
• Sets characterized by missing sums and differences
• On sets with more restricted sums than differences
• Generalizing the distribution of missing sums in sumsets

zbMATH Keywords

phase transitioncorrelated random variablesmore sum than difference sets

Mathematics Subject Classification ID

Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Phase transitions (general) in equilibrium statistical mechanics (82B26) Additive bases, including sumsets (11B13) Probabilistic theory: distribution modulo (1); metric theory of algorithms (11K99) Additive number theory; partitions (11P99)

Cites Work

• When almost all sets are difference dominated
• Sets with more sums than differences
• Generalized more sums than differences sets
• Explicit constructions of large families of generalized more sums than differences sets
• Some explicit constructions of sets with more sums than differences
• Many sets have more sums than differences
• Sets characterized by missing sums and differences
• Constructing MSTD sets using bidirectional ballot sequences
• Explicit constructions of infinite families of MSTD sets

Cited In (6)

• Sets characterized by missing sums and differences in dilating polytopes
• Sets of random variables with a given uncorrelation structure
• When sets can and cannot have sum-dominant subsets
• Generalizing the distribution of missing sums in sumsets
• Distribution of Missing Differences in Diffsets
• On correlations between complete sets

This page was built for publication: Sums and differences of correlated random sets

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