0

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.

Vincent Granville
  • 3,078
  • What is the definition of $r'(z)$? You don't state what you mean by that. – JoshuaZ Jul 04 '20 at 01:44
  • $r'(z)$ is the derivative of $r(z)$, and $r(z)$ is asymptotically equivalent to the number of solutions in positive integers to $x+y\leq z$ with $x,y\in S$. By asymptotically, I mean when $z\rightarrow\infty$. – Vincent Granville 7 hours ago – Vincent Granville Jul 04 '20 at 09:46
  • I must be missing something here. $r(z)$ is not a continuous function so how can it have a derivative? The right-hand side of the asymptotic does have a derivative. Is there something going on with a discrete analog like the finite difference method? – JoshuaZ Jul 04 '20 at 15:15
  • 1
    $r(z)$ is the asymptotic continuous version of the function counting the number of solutions to $x+y\leq z$, and it is assumed here to be equal to $a z^b/(\log z)^c$, and $r'(z)$ is its derivative. – Vincent Granville Jul 04 '20 at 18:51
  • 1
    Also, $r′(z)\sim r(z)-r(z−1)\sim dr(z)/dz$. See how I derived all these results, in a previous MO question: https://mathoverflow.net/questions/363055/goldbach-conjecture-and-other-problems-in-additive-combinatorics/ – Vincent Granville Jul 04 '20 at 19:04
  • 3
    What is your reason for believing conjecture A fails for pseudo-super-super-primes? Is it just computational? If so then the likeliest explanation is that the computational evidence is misleading and conjecture A does hold for large enough integers. The existence of small counterexamples for results that hold for all sufficiently large integers is a well-known phenomenon in additive number theory (e.g. see Waring's problem), and the sparser the sets you're working with, the larger the threshold for the 'eventual' behaviour to kick in would be. – Thomas Bloom Jul 04 '20 at 21:43
  • @Thomas. Yes I agree with you, glad that one more time this "conjecture A" is believed to be true. My guess is that my problem is purely computational, dealing with too small numbers. I worked more on this, and I have more and more theoretical evidence that conjecture A is correct. – Vincent Granville Jul 04 '20 at 23:11

1 Answers1

1

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, 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).

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

Vincent Granville
  • 3,078