Mathematics – Number Theory
Scientific paper
2011-09-22
Mathematics
Number Theory
Scientific paper
For any finite set of integers A, define its sumset A+A to be {x+y: x, y in A}. In a recent paper, Martin and O'Bryant studied sum-dominant sets, where |A+A| > |A-A|. These are interesting as one expects a generic A to have |A+A| < |A-A| (as addition is commutative but subtraction is not). They proved a positive percentage of all sets are sum-dominant, and investigated the distribution of |A+A| given the uniform distribution on subsets A of {0, 1, ..., n-1}. They also conjectured the existence of a limiting distribution for |A+A| and showed that the expectation of |A+A| is 2n - 11 + O((3/4)^{n/2}). We derive an explicit formula for the variance of |A+A| in terms of Fibonacci numbers via a graph-theoretic approach. We also prove exponential upper and lower bounds (independent of n) for Prob(A subset of {0, ..., n-1}: |A+A| = 2n -1 -k). These bounds are based on bounds on probabilities like Prob(k+ a_1, ..., and k + a_m not in A+A), which we prove are roughly exponential in k for fixed a_1, ..., a_m by applying a modified version of Fekete's Lemma. Finally, we prove that Prob(k+1, ..., k+m not in A+A), the probability that A+A is missing a consecutive block of m elements starting at k+1, is approximately (1/2)^{(k+m)/2} for large m, k. This approximation implies that essentially the only way for A+A to miss a consecutive block of m elements starting at k+1 is to miss all elements up to k+m.
Lazarev Oleg
Miller Steven J.
No associations
LandOfFree
Distribution of Missing Sums in Sumsets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distribution of Missing Sums in Sumsets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution of Missing Sums in Sumsets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-262234