Sharp Threshold Asymptotics for the Emergence of Additive Bases

Document Type

Book Contribution

Publication Date



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.