Sums and differences of correlated random sets

DOI10.1016/J.JNT.2014.06.022MaRDI QIDQ472815zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(6)

• Distribution of Missing Differences in Diffsets
• 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
• 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)