Additive properties of sequences of pseudo s-th powers

In this paper, we study (random) sequences of pseudo s-th powers, as introduced by Erdős and Rényi (Acta Arith 6:83–110, 1960). Goguel (J Reine Angew Math 278/279:63–77, 1975) proved that such a sequence is almost surely not an asymptotic basis of order s. Our first result asserts that it is however almost surely a basis of order s+ ϵ for any ϵ> 0. We then study the s-fold sumset sA= A+ ⋯ + A (s times) and in particular the minimal size of an additive complement, that is a set B such that sA+ B contains all large enough integers. With respect to this problem, we prove quite precise theorems which are tantamount to asserting that a threshold phenomenon occurs.