Distributions associated with random sets and sums of random sets

Question

Let's say you have an infinite random set $S$ of non-negative integers, and $T=S+S=\{x+y$ with $x,y\in S\}$. Let $N_S(z)$ be the number of elements of $S$ less than or equal to $z$; it is a random variable. Assume that the set $S$ is large enough so that $T$ consists almost surely of all but a finite number of non-negative integers. This is the case if $$E[N_S(z)] \sim \frac{az^b}{(\log z)^c} \mbox{ with } a,b,c\geq 0 \mbox{ and } \frac{1}{2}<b\leq 1.$$

The set $S$ is built as follows. Each non-negative integer $z$ belongs to $S$ if and only if $U_z < f(z)$, where the $U_z$'s are independently and uniformly distributed random variable on $[0, 1]$. In practice, $$f(z) =\frac{abz^{b-1}}{(\log z)^c},$$ so that the above requirement is met. For details, see here and here. This is connected to the Golbach conjecture and other related conjectures. It does not work if $b\leq \frac{1}{2}$, even if $b=\frac{1}{2}$: in that case, $T$ behaves as the set of sums of two perfect squares, it is sparse and has density zero.

Questions

Let $R'_S(z)$ be the number of ways that an integer $z$ can be written as $x+y=z$ with $x,y \in S$, and

$$R^*_S(z)=\frac{R'_S(z)-E[R'_S(z)]}{\sqrt{Var[R'_S(z)]}}.$$

• What is the asymptotic distribution of $R^*_S(z)$ as $z\rightarrow\infty$? Note that $x+y$ and $y+x$ counts as two ways.
• Let $M_S(z)$ be the largest integer $\leq z$ that can not be written as $z=x+y$ with $x,y \in S$, and $M_S=M_S(\infty)$. What is the distribution of $M_S$?
• Let $W_S(z)$ be the total number of non-negative integers $\leq z$ (known as exceptions) that can not be written as $z=x+y$ with $x,y \in S$. What is the distribution of $W_S=W_S(\infty)$, the total number (a.s. finite if $b>\frac{1}{2}$) of exceptions?

These distributions depend on $a, b, c$. The empirical distributions can be obtained by computing the statistics in question over a large number of observed sets $S$ with the same $a,b,c$, generated with the above mechanism. Because the elements in $T$ are NOT independently distributed, neither the Central Limit Theorem nor the law of the iterated algorithm apply to $W_S$ or $M_S$. I started to investigate this problem in my answer to this question, where I use the Borel-Cantelli lemma. One fact that seems clear is this (see here):

$$E[R_S(z)]\sim \frac{a^2z^{2b}}{(\log z)^{2c}}\cdot\frac{\Gamma^2(b+1)}{\Gamma(2b+1)}$$

where $R_S(z)$ is the number of non-negative integer solutions to $x+y\leq z$ with $x,y \in S$. From this, by derivation with respect to $z$, you can get a similar formula for $E[R'_S(z)]$, also featured in the same post:

$$E[R'_S(z)]\sim \frac{a^2z^{2b-1}}{(\log z)^{2c}}\cdot\frac{\Gamma^2(b+1)}{\Gamma(2b)}.$$

Another problem of interest is this: is any realization of $S$ almost surely equidistributed in residue classes? What about $T$? More on this here and here.

Examples

Below is a chart showing the empirical distribution (actually, the frequency table) for $W_S$ when $a=1, b=\frac{2}{3}, c=0$. It clearly is not a Gaussian distribution. It reads as follows: there is about 19 occurrences (Y-axis), computed on 1,000 sets $S$ with same $a,b,c$, for which the number of exceptions is 50 (X-axis).

Below is the scatterplot for $W_S$ (X-axis) versus $M_S$ (Y-axis):

I have also tested other examples, see here:

• $a=1,b=1,c=1$: pseudo primes (directly related to Golbach conjecture)
• $a=1, b=1, c=2$: pseudo super-primes (much stronger than Goldbach conjecture)

Keep in mind that pseudo-primes are not primes, they are just numbers that look random (generated with the mechanism described here) but having a distribution similar to primes, except that primes are by no mean the realization of a random set: sums of two primes are very rarely an odd integer, making them totally unfit as an example of a random set. And that's just one issue of non-randomness with primes, there are many others. So my post here is of no help to prove Golbach conjecture, and that was not the goal to begin with.

A pretty good approximation for $E[W_S]$, depending on $a,b,c$, is given by

$$E[W_S] \approx \int_0^\infty \exp\Big(-\frac{1}{2} E[R'_S(u)]\Big)du.$$

See my answer to this question for details, as well as here. In this case, the integral is finite and yields $E[W_S]\approx 63.76$ while the exact value looks very close to $65$. The variance of $W_S$ is also expected to be finite, and this is the reason why the Central Limit Theorem does not apply here.

Answer 1

If $z$ is an odd integer, we have $$R'_S(z) = \sum_{k=0}^z X_k X_{z-k}=2\sum_{k=0}^{(z-1)/2}X_k X_{z-k}=2\sum_{k=0}^{(z-1)/2}Y_k$$

where

• $X_k$ is Bernouilli of parameter $f(k)$
• The $Y_k$'s ($k=0,\cdots, \frac{z-1}{2}$) are independent, non-identically distributed Bernouilli variables of parameter $p_k=f(k)f(z-k)$

It follows (see here and here) that

$$E[R'_S(z)]= 2\sum_{k=0}^{(z-1)/2}p_k=\sum_{k=0}^zp_k \sim \frac{a^2z^{2b-1}}{(\log z)^{2c}}\cdot\frac{\Gamma^2(b+1)}{\Gamma(2b)}\mbox{ as } z\rightarrow\infty$$

$$Var[R'_S(z)]=4\sum_{k=0}^{(z-1)/2}(1-p_k)p_k = 2\sum_{k=0}^z p_k(1-p_k)\sim 2E[R'_S(z)]$$

In addition, since the $p_k$'s tends to zero as $z$ increases, $R'_S(z)$ is well approximated by $2Y_z$ where $Y_z$ has a Poisson distribution of parameter $(p_0+\cdots +p_z)/2$. See here for the Poisson approximation, based on Le Cam's theorem.

If $b>\frac{1}{2}$ then the variance $Var[R'_S(z)]$ tends to infinity as $z\rightarrow\infty$, and thus the Central Limit Theorem applies. This remains true with same asymptotic result if $z$ is even. That case is slightly different but leads to the same asymptotic results.

For $M_S$ and $W_S$, if $b>\frac{1}{2}$, then these random variables are almost surely finite: that is, the set of observed sets $S$ with $M_S=\infty$ or $W_S=\infty$ has Lebesgue measure zero. In other words, $P(M_S=\infty)=P(W_S=\infty)=0$. In this case, the Central Limit Theorem may not apply. Note that an infinite set $S$ is uniquely identified by its characteristic number $\mu(S)=\sum_{k=0}^\infty \chi(k) \cdot 2^{-k}$ where $\chi(k)=1$ if $k\in S$ and $\chi(k)=0$ otherwise.

Detailed computation of $Var[R'_S(z)]$

We have $$Var[R'_S(z)] =2\sum_{k=0}^z p_k(1-p_k) = 2E[R'_S(z)] -2\sum_{k=0}^z p_k^2.$$

The rightmost sum involving $p_k^2$ tends to zero as $z\rightarrow\infty$. More precisely,

$$\sum_{k=0}^z p_k^2\sim \int_0^z f^2(u)f^2(z-u) du =z\int_0^1 f^2(zw)f^2(z(1-w))dw$$

with the change of variable $u=wz$. Since we use $f(z) = abz^{b-1}/(\log z)^c$, the integral becomes

$$\int_0^1 f^2(zw)f^2(z(1-w))dw \sim z^{4b-3}\frac{a^4b^4}{(\log z)^4}\int_0^1 w^{2b-2}(1-w)^{2b-2} dw.$$

If $b<\frac{3}{4}$, it tends to zero as $z\rightarrow\infty$. And even if $\frac{3}{4}\leq b<1$, or if $b=1$ and $c>0$, this integral is an order of magnitude smaller than $E[R'_S(z)]$.

Note that the opposite happens if $b\leq\frac{1}{2}$. In that case, $M_S$ and $W_S$ are almost surely infinite while $E[R'_S(z)]$ and $Var[R'_S(z)]$ are bounded as $z\rightarrow \infty$.

Conclusion

This analysis is further legitimating the fact that the strong Goldbach's conjecture (among many others in additive combinatorics) is true with probability one. Strong GC would be proved (with probability one, so not really a real proof) if prime numbers were random enough, random enough as the numbers featured in this discussion. Unfortunately, they are not: for instance, the sum of two odd primes is never an odd integer. GC corresponds to $a=1, b=1, c=1$, which fits with the theory presented here. But the gap to prove GC, based on this analysis, may be not that far away to fill. The first step is to look at results deeper than the central limit theorem, like the law of the iterated logarithm, and shows it applies to GC. It also involves proving that primes are "random enough".