Erdos 1960 additive properties random sequences positive integers

../

---

Paul Erdős, Alfréd Rényi, Additive properties of random sequences of positive integers. Acta Arithmetica 6 (1960), 83-110.

Erdős and Rényi introduce random sequences v_k generated by independent indicators with P(n in the sequence) = p_n and study the number f(n) of additive representations. Theorem 1 shows that if p_n and q_n tend to 0 and the convolution sum tends to a limit lambda, then f(n) is asymptotically Poisson with mean lambda; Theorem 2 upgrades this to an almost-sure density statement, the set S_r of integers with exactly r representations n = v_k + mu_l having density lambda^r e^{-lambda}/r! with probability 1, and its corollary gives the sumset density 1 - e^{-lambda}. Theorems 3 and 4 handle n = k^2 + mu_l and n = v_k + v_l, Theorem 5 gives asymptotic normality of f(n) when its variance tends to infinity, and Theorem 8 shows that for p_n = c n^{-1/2-epsilon}, with 0 < epsilon < 1/2, the sequence is almost surely a B_2 sequence with f(n) bounded, at most [1/(2 epsilon)] apart from finitely many n. Section 6 is the r-fold generalization cited for problem 1192: Theorem 6 takes p_n = c n^{1/s - 1} for an integer s >= 3, so the sequence has counting function of order x^{1/s}, and shows the number of representations as a sum of s increasing terms has, with probability 1, Poisson densities with mean lambda = c^s Gamma(1/s)^s / s! - so the representation counts stay bounded in mean. The paper does not estimate the sum of f_s(n)^2 up to x, the quantity in the problem statement, and the sequence is not a basis, since S_0 has positive density; that gap is the problem. Theorems 11 and 12 give stochastic analogs of Romanoff's theorem.

Source: https://www.renyi.hu/~p_erdos/1960-02.pdf. The file's text layer carries no copyright or license line; the journal's record offers the PDF under the download link "Pobierz zgodnie z CC-BY", rendered "Free download under CC-BY license" on the English site, and names no version or URL for it (https://www.impan.pl/get/doi/10.4064/aa-6-1-83-110, read 2026-10-02): the Creative Commons Attribution license, with no version stated.

Bears on. #1192

Results to transcribe.

• Theorem 1: If p_n, q_n tend to 0 and the convolution sum tends to lambda > 0, the number f(n) of representations n = v_k + mu_l is asymptotically Poisson with mean lambda.
• Theorem 2: If p_n, q_n are decreasing and tend to 0, the convolution sum tends to lambda > 0, and both partial sums are O(n^{1-delta}) for some 0 < delta < 1, the set of n with exactly r representations has density lambda^r e^{-lambda}/r! with probability 1; the corollary gives sumset density 1 - e^{-lambda}.
• Theorem 6: For p_n = c n^{1/s - 1} with integer s >= 3, the number of representations of n as a sum of s increasing terms has almost surely Poisson densities lambda^r e^{-lambda}/r!, so representation counts are bounded on average.
• Theorem 5: With A_1(n) = sum_{k<n/2} p_k p_{n-k} and A_2(n) = sum_{k<n/2} p_k^2 p_{n-k}^2, if A_1(n) - A_2(n) tends to infinity, then the number f(n) of representations n = v_k + v_l with k < l, minus A_1(n) and normalized by the square root of A_1(n) - A_2(n), is asymptotically standard normal.
• Theorem 8: For p_n = c n^{-1/2-epsilon} with 0 < epsilon < 1/2, with probability 1 the number f(n) of representations n = v_k + v_l with k <= l is bounded and at most [1/(2 epsilon)] except for finitely many n, so the sequence is almost surely a B_2 sequence.
• Theorem 12: For independent random sequences v_k and mu_l with q_n decreasing, both partial sums P(n), Q(n) tending to infinity, Q(np)/Q(n) -> p for every p > 0, and R(n)/n -> lambda > 0, where R(n) sums the convolution sums r_k = sum_{j<k} p_j q_{k-j} over k <= n, the set of n with exactly r representations n = v_k + mu_l has density lambda^r e^{-lambda}/r! with probability 1. It covers cases where condition (2.5) of Theorem 2 fails.