WHEN ALMOST ALL SETS ARE DIFFERENCE DOMINATED IN Z/nZ

摘要

We investigate the behavior of the sum and difference sets of A ? Z/nZ chosen independently and randomly according to a binomial parameter p(n) = o(1). We show that for rapidly decaying p(n), A is almost surely difference-dominated as n → ∞, but for slowly decaying p(n), A is almost surely balanced as n → ∞, with a continuous phase transition as p(n) crosses a critical threshold. Specifically, we show that if p(n) = o(n?1/2), then |A ? A|/|A + A| converges to 2 almost surely as n → ∞ and if p(n) = c · n?1/2, then |A ? A|/|A + A| converges to 1 + exp(?c2/2) almost surely as n → ∞. In these cases, we modify the arguments of Hegarty and Miller on subsets of Z to prove our results. When √log n · n?1/2 = o(p(n)), we prove that |A ? A| = |A + A| = n almost surely as n → ∞ if some additional restrictions are placed on n. In this case, the behavior is drastically different from that of subsets of Z and new technical issues arise, so a novel approach is needed. When n?1/2 = o(p(n)) and p(n) = O( √log n · n?1/2), the behavior of |A + A| and |A ? A| is markedly different and suggests an avenue for further study. These results establish a “correspondence principle” with the existing results of Hegarty, Miller, and Vissuet. As p(n) decays more rapidly, the behavior of subsets of Z/nZ approaches the behavior of subsets of Z shown by Hegarty and Miller. Moreover, as p(n) decays more slowly, the behavior of subsets of Z/nZ approaches the behavior shown by Miller and Vissuet in the case where p(n)=1/2.