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.

1more comment