Distribution of Missing Sums in Sumsets

Mathematics – Number Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-262234

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.