Sums and differences of correlated random sets

Abstract

Many questions in additive number theory (Goldbach's conjecture, Fermat's Last Theorem, the Twin Primes conjecture) can be expressed in the language of sum and difference sets. As a typical pair contributes one sum and two differences, we expect |A−A|>|A+A|for finite sets A. However, Martin and O'Bryant showed a positive proportion of subsets of {0,…,n} are sum-dominant. We generalize previous work and study sums and differences of pairs of correlated sets (A,B)(a∈{0,…,n} is in A with probability p, and a goes in B with probability_(ρ1) if a∈A and probability_(ρ2)if a∉A). If |A+B|>|(A−B)∪(B−A)|, we call (A,B) a sum-dominant (p,_(ρ1,ρ2))-pair. We prove for any fixed ρ→=(p,ρ1,ρ2) in (0,1)^3, (A,B) is a sum-dominant (p,_(ρ1,ρ2))-pair with positive probability, which approaches a limit P(ρ→). We investigate p decaying with n, generalizing results of Hegarty–Miller on phase transitions, and find the smallest sizes of MSTD pairs.

Files

Additional details