Let $S$ be an infinite set of positive integers. Let us define the following quantities:


* $N\_S(z)$ is the number of elements of $S$, less or equal to $z$
* $r\_S(z)$ if the number of positive integer solutions to $x+y\leq z$,
with $x,y\in S$ and $z$ an integer
* $t\_S(z)$ if the number of positive integer solutions to $x+y= z$,
with $x,y\in S$ and $z$ an integer


We assume here that
$$N\_S(z) \sim \frac{a z^b}{(\log z)^c}$$
where $a,b,c$ are positive real numbers with $b\leq 1$. This covers primes, super-primes, squares and more.


We have:


$$r(z)\sim \frac{a^2\Gamma^2(b+1)}{\Gamma(2b+1)} \cdot \frac{z^{2b}}{(\log z)^{2c}}$$


$$r'(z)\sim \frac{a^2\Gamma^2(b+1)}{\Gamma(2b)} \cdot \frac{z^{2b-1}}{(\log z)^{2c}}$$


For details about these results, see my previous MO question, [here](https://mathoverflow.net/questions/364559/general-asymptotic-result-in-additive-combinatorics-sums-of-sets). For super-prime numbers, see this [OEIS entry](http://oeis.org/wiki/Higher-order_prime_numbers), and especially [this paper](https://www.emis.de//journals/INTEGERS/papers/n43/n43.pdf). I mentioned earlier, and this seems to be a well known and trivial fact, that $t(z) \sim r'(z)$ ***on average***.


Barring congruence restrictions, a conjecture states that if $r'(z) \rightarrow \infty$ as $z\rightarrow \infty$, then almost all large enough integer $z$ can be written as $z=x+y$ with $x,y\in S$. I will call this **conjecture A**. Because of congruence restrictions, I worked with pseudo-primes instead of primes. They are generated as follows. A positive integer $k$ belongs to $S$ (set of pseudo-primes) if and only if $R\_k < N'\_S(k)$ where the $R\_k$'s are independent random deviates on $[0, 1]$. Here
$$N'\_S(z) \sim \frac{abz^{b-1}}{(\log z)^c}.$$


Note that $N'\_S(z)$ is the asymptotic derivative of $N\_S(z)$.


Examples:


* For pseudo-primes, $a=b=c=1$.
* For pseudo-super-primes, $a=b=1, c=2$.
* For pseudo-super-super-primes, $a=b=1, c = 3$.
* For my test power set, $a=1, b= \frac{2}{3}, c=0$.


Pseudo-super-primes are extremely rare compared to primes, yet all but a finite number of integers can be expressed as the sum of two pseudo-super-primes. This is compatible with results obtained [here](https://www.emis.de//journals/INTEGERS/papers/n43/n43.pdf) and intuitively, it makes sense. Pseudo-super-super-primes are even far more rare, and here the **conjecture A** seems to fail: it looks like not only a large chunk of integers can not be written as the sum of two pseudo-super-super-primes, but these exceptions seem to represent the immense majority of all positive integers. Now the paradox.


**Paradox**


My test power set (see definition in the example section) consists of integers that are even far more rare than pseudo-super-super-primes, yet for them conjecture A works, as expected. Perhaps this is caused by the fact that these integers are far more abundant than pseudo-super-super-primes among the first million integers, but asymptotically they become far less abundant than pseudo-super-super-primes.


**My question**


How do you explain my paradox? Is conjecture A wrong? Or is it possible that if you look at extremely, massively large integers (probably well above $10^{5000}$), they can always be expressed as a sum of two pseudo-super-super-primes despite the fact that the opposite is true for smaller integers that only have a few hundreds digits?


***Update**: I posted a new MO question suggesting that there is no paradox. See [here](https://mathoverflow.net/questions/364909/asymptotic-inversion-formula-in-additive-number-theory-sums-of-two-sets-of-posi).*



Paradox in additive combinatorics
I wrote:


*My test power set (see definition in the example section) consists of integers that are even far more rare than pseudo-super-super-primes, yet for them conjecture A works, as expected. Perhaps this is caused by the fact that these integers are far more abundant than pseudo-super-super-primes among the first million integers, but asymptotically they become far less abundant than pseudo-super-super-primes.*


Indeed, that's the explanation. If you check my new MO question [here](https://mathoverflow.net/questions/364909/curious-inversion-formula-in-additive-combinatorics), you have the following result. Let us denote as $w(z)$ the number of positive integers less or equal to $z$ that can not be written as $z=x+y$, with $x,y \in S$. These integers are called *exceptions*. We have


$$w(z) \approx \int\_0^z \exp\Big(-\frac{1}{2} r'(u)\Big)du.$$


The total number of exceptions (unless small, say $<50$) is well approximated by $w(\infty)$ when averaged over a large number of sets $S$ that have the same statistical distribution of elements. And because $b>\frac{1}{2}$ we have $w(\infty)<\infty$. Of course the range varies greatly across multiple sets, but it is correct on average.


In particular,


* For pseudo-super-primes, $w(\infty) \approx \int\_2^\infty
 \exp(-u\cdot(\log u)^{-4})du \approx 26341$.
* For pseudo-super-super-primes, $w(\infty) \approx \int\_2^\infty
 \exp(-u\cdot (\log u)^{-6})du > 10^7$. Still, it is finite.
* For my test power set, $w(\infty) \approx 65$ (see [here](https://mathoverflow.net/questions/364909/curious-inversion-formula-in-additive-combinatorics)).


Note that I used $\int\_2^\infty$ instead of $\int\_0^\infty$ due to a singularity at $1$ that should be ignored.


