"Sharp Threshold Asymptotics for the Emergence of Additive Bases" by Anant Godbole, Chang Mou Lim et al.
 

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.

Share

COinS