Sharp Threshold Asymptotics for the Emergence of Additive Bases
Document Type
Book Contribution
Publication Date
1-1-2014
Description
A set A ⊆ [n] ∪ {0} is said to be a 2-additive basis for [n] if each j ∈ [n] can be written as j = x + y, x, y ∈ A, x ≤ y. If we pick each integer in [n] ∪ {0} independently with probability p = pn → 0, thus getting a random set A, what is the probability that we have obtained a 2-additive basis? We address this question when the target sum-set is [(1 - α)n, (1 + α)n] (or equivalently [αn, (2 - α)n]) for some 0 < α < 1. We use a delicate application of Janson's correlation inequalities in conjuction with the Stein-Chen method of Poisson approximation to tease out a very sharp threshold for the emergence of a 2-additive basis. Generalizations to k-additive bases are then given.
Citation Information
Godbole, Anant; Lim, Chang Mou; Lyzinski, Vince; and Triantafillou, Nicholas George. 2014. Sharp Threshold Asymptotics for the Emergence of Additive Bases. Integers: Annual Volume 2013. 195-211. https://doi.org/10.1515/9783110298161.195 ISBN: 9783110298161,9783110298116