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. For super-prime numbers, see this OEIS entry, and especially this paper. 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 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.

2more comments