SUMS AND DIFFERENCES OF CORRELATED RANDOM SETS

ABSTRACT. Many questions in additive number theory (Goldbach’s conjecture, Fermat’s Last The-orem, 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 fi-nite 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 corre-lated 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 6 ∈ 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. CONTENT