Distribution of Missing Sums in Sumsets

被引:2
作者
Lazarev, Oleg [1 ]
Miller, Steven J. [2 ]
O'Bryant, Kevin [3 ,4 ]
机构
[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[2] Williams Coll, Dept Math & Stat, Williamstown, MA 01267 USA
[3] CUNY Coll Staten Isl, Dept Math, Staten Isl, NY 10314 USA
[4] Grad Ctr, Staten Isl, NY 10314 USA
基金
美国国家科学基金会;
关键词
Primary; 11P99; Secondary; 11K99; sumsets; uniformly random sumsets; Fekete's lemma; SETS;
D O I
10.1080/10586458.2013.743304
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a finite set of integers X, define its sumset X+X to be {x+y:x, yX}. In a recent paper, Martin and O'Bryant investigated the distribution of |A+A| given the uniform distribution on subsets A{0, 1, ..., n1}. They also conjectured the existence of a limiting distribution for |A+A| and showed that the expectation of |A+A| is . Zhao proved that the limits exist, and that Sigma(k0)m(k)=1. We continue this program and give exponentially decaying upper and lower bounds on m(k), and sharp bounds on m(k) for small k. Surprisingly, the distribution is at least bimodal; sumsets have an unexpected bias against missing exactly seven sums. The proof of the latter is by reduction to questions on the distribution of related random variables, with large-scale numerical computations a key ingredient in the analysis. We also derive an explicit formula for the variance of |A+A| in terms of Fibonacci numbers, finding that . New difficulties arise in the form of weak dependence between events of the form {xA+A}, {yA+A}. We surmount these obstructions by translating the problem to graph theory. This approach also yields good bounds on the probability for A+A missing a consecutive block of length k.
引用
收藏
页码:132 / 156
页数:25
相关论文
共 15 条
  • [1] Alon N., 1985, Eur. J. Comb, V6, P201, DOI [10.1016/S0195-6698(85)80027-5, DOI 10.1016/S0195-6698(85)80027-5]
  • [2] ERDos P., 1960, Acta Arith., V6, P83, DOI DOI 10.4064/AA-6-1-83-110
  • [3] FREIMAN GA, 1964, DOKL AKAD NAUK SSSR+, V158, P1038
  • [4] Geroldinger A, 2009, ADV COURSES MATH CRM
  • [5] Gilbert F., 2012, PREPRINT
  • [6] Hegarty P, 2010, ADDITIVE NUMBER THEORY: FESTSCHRIFT IN HONOR OF THE SIXTIETH BIRTHDAY OF MELVYN B. NATHANSON, P153, DOI 10.1007/978-0-387-68361-4_11
  • [7] When Almost All Sets Are Difference Dominated
    Hegarty, Peter
    Miller, Steven J.
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2009, 35 (01) : 118 - 136
  • [8] Generalized More Sums Than Differences sets
    Iyer, Geoffrey
    Lazarev, Oleg
    Miller, Steven J.
    Zhang, Liyang
    [J]. JOURNAL OF NUMBER THEORY, 2012, 132 (05) : 1054 - 1073
  • [9] Applications of nonstandard analysis in additive number theory
    Jin, RL
    [J]. BULLETIN OF SYMBOLIC LOGIC, 2000, 6 (03) : 331 - 341
  • [10] Martin G, 2007, CRM PROC & LECT NOTE, V43, P287