# General asymptotic result in additive combinatorics (sums of sets)

Let $$S_1,\cdots,S_k$$ be $$k$$ infinite sets of positive integers. Let $$N_i(z)$$ be the numbers of elements in $$S_i$$ that are less or equal to $$z$$. Let us further assume that $$N_i(S) \sim \frac{a_i z^{b_i}}{(\log z)^{c_i}} \mbox{ as } z\rightarrow \infty,$$ where $$a_i>0, 0 < b_i \leq 1, c_i \geq 0 (i=1,\cdots k)$$ are constants. Also, let

• $$r(z)$$ be the number of solutions to $$x_1+\cdots + x_k\leq z$$, with $$x_i \in S_i$$ (here $$z$$ is an integer).
• $$t(z)$$ be the number of solutions to $$x_1+\cdots + x_k = z$$, with $$x_i \in S_i$$ (here $$z$$ is an integer).

Note that $$t(z) = r(z) - r(z-1) \sim r'(z)$$ asymptotically on average, where $$r'$$ denotes the derivative.

Question: Is the following result correct?

$$r(z) \sim \frac{\prod_{i=1}^k a_i \Gamma(b_i+1)}{\Gamma(1+\sum_{i=1}^k b_i)} \cdot \frac{z^{b_1 + \cdots + b_k}}{(\log z)^{c_1 +\cdots + c_k}} \mbox{ as } z \rightarrow \infty.$$

This covers many cases such as

• Sums of squares
• Sums of primes
• Sums of powers
• Sums of a square and a prime
• Sums of superprimes

However it assumes that there are no congruence restrictions (for instance sums of odd integers can not be an odd integer, thus it does not work for sums of two odd primes, but it does for sums of two pseudo-primes depending on how you define pseudo-primes). See a proof for the case $$k=2$$, here. Also, is it true that if $$r'(z) \rightarrow\infty$$ as $$z\rightarrow\infty$$, then almost all integers can be written as $$z = x_1+\cdots + x_k, \mbox{ with } x_i \in S_i.$$ By almost, I mean all but a finite number, or maybe all but a small infinite subset of positive integers, of density zero. If this was true, we would have the following result, maybe not that hard to prove:

Almost all positive integers can be written as $$x_1^{d_1} + \cdots + x_k^{d_k}$$ if $$\frac{1}{d_1} + \cdots + \frac{1}{d_k}> 1$$.

Here the $$d_i$$'s and $$x_i$$'s are positive integers. The constants $$d_1,\cdots,d_k$$ are fixed. This is compatible with a conjecture associated with the Waring problem, in the absence of congruence restrictions (see Wikipedia entry, check out the section Lower Bounds for $$G(k)$$). Namely, the fact that almost all positive integers can be written as $$x_1^k + x_2^k +\cdots + x_{k+1}^k$$ in the absence of congruence restrictions (e.g. not true for $$k=2, 4$$ due to congruence restrictions, but potentially true for $$k=3,5,7, 11, 13$$ etc.)

• I'm slightly confused because you answer your own question in the negative (is this asymptotic true - not necessarily, because there may be congruence restrictions). Do you mean further assume some kind equidistribution amongst different congruence classes, to e.g. rule out primes? Jul 1 '20 at 6:48
• Yes you must assume some kind of equidistribution and define that concept. Jul 1 '20 at 14:47
• Your guess for $r(z)$ is conjecturally correct, once corrected for congruence class restrictions (the way in which one does so is not obvious, and is a story in itself). This is a form of the heuristic which has been used in additive number theory, going back to Hardy and Littlewood, to make various conjectures about the count of solutions in Goldbach's conjecture and similar problems. Jul 1 '20 at 15:44
• Of course, a conjecture and the heuristics leading to it are a long way from a theorem and a proof! Indeed, the last 100 years of the circle method have, in some sense, been an attempt to prove such conjectures, with varying degrees of success. Jul 1 '20 at 15:44
• Could you share a reference about the definition of "no congruence class restrictions" assuming there is one generally agreed upon? Thank you. Jul 1 '20 at 16:00