Curious inversion formula in additive combinatorics

Question

Let $S$ be an infinite set of positive integers, and $T=S+S=\{x+y, \mbox{ with } x,y\in S\}$.We definte the following functions:

• $N_S(z)$ is asymptotic continuous version of the function counting the number of elements in $S$ less or equal to $z$.
• $N'_S(z)$, the derivative of $N_S(z)$, is the "probability" for $z$ (an integer) to belong to $S$
• $r(z)$ is the asymptotic continuous version of the function counting the number of solutions $x+y \leq z$ with $x,y\in S$.
• $r'(z)$ is the derivative of $r(z)$.

We will work with $$N_S(z) \sim \frac{az^b}{(\log z)^c}.$$

Here $\frac{1}{2}< b \leq 1$ and $a>0, c\geq 0$. The case $b=1, c=0$ should be excluded. This covers a vast array of sets: sums of primes, sums of super-primes etc. The following is a known result (see here):

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

More generally (see here):

$$r(z) \sim z\int_0^{1} N_S(z(1-v))N'_S(zv) dv.$$ $$r'(z) \sim z\int_0^{1} N'_S(z(1-v))N'_S(zv) dv .$$

Since $b>\frac{1}{2}$, we have $r'(z) \rightarrow \infty$ as $z\rightarrow \infty$. This guarantees (it's a conjecture) that barring congruence restrictions, $T = S + S$ contains all the positive integers except a finite number of them. The inversion formula is as follows:

Inversion formula

$$N_T(z) = z-w(z), \mbox{ with } w(z) \sim \int_0^z \exp\Big(-\frac{1}{2} r'(u)\Big)du.$$

Since $r'$ is a function of $N'$ and thus, a function of $N$, we have a formula linking $N_T$ to $N_S$. So if you know $N_T$, by inversion (it involves solving an integral equation, though we are only interested in the asymptotic value of the solution) technically, you can retrieve $N_S$, assuming the solution is unique (chances are that the solution is far from unique.)

Note that $w(z)$ represents the number of positive integers, less or equal to $z$, that do not belong to $T=S+S$. These integers are called exceptions; $w(\infty)$ is finite and represents an estimate of the total number of exceptions. I tried to assess the validity of the inversion formula using some test sets $S$, and empirical evidence suggests that it is correct. Essentially, it is based on the following simple probabilistic argument (see proof in my answer to this post). Let $u(z)$ be the probability that $z$ (an integer) is an exception. Then, if $r'(z)\rightarrow\infty$ as $z\rightarrow\infty$ and $S$ is free of congruence restrictions and other sources of non-randomness, then
$$u(z) \sim \exp\Big(-\frac{1}{2}r'(z)\Big).$$

Testing the formula on an example

I created 100 test sets $S$, with $a=1, b=\frac{2}{3}, c=0$, as follows: an integer $k$ belongs to $S$ if and only if $U_k<N'_S(k)$, where the $U_k$'s are independent uniform deviates on $[0, 1]$. I computed various statistics, but I will mention only one here. The theoretical value for $w(\infty)$ is $$w(\infty) \approx \int_0^\infty \exp\Big(-\frac{\lambda}{2}u^{1/3}\Big)du \approx 63.76, \mbox{ with } \lambda = \frac{\Gamma^2(\frac{5}{3})}{\Gamma(\frac{4}{3})}.$$

Note that the above integral can be computed explicitly. I then conjectured the value $w(\infty)$ for each of the 100 test sets. It ranged from $13$ to $199$, with an average value of $65.88$. Again, $w(\infty)$ is an estimate of the number of exceptions, that is, positive integers that can not be represented as $x+y$ with $x, y \in S$. So the approximate theoretical value is in agreement with the average value inferred from my experiment.

My question

Is this inversion formula well known? Can it be of any practical use? Can it be further refined, maybe generalized to sums of three sets or made more accurate with bounds on the error term?

Answer 1

This is not an answer to the question, but an explanation as to how I came up with the formula for $w(z)$. We assume here that $S$ is a random set. That is, let us consider $X_z$ as a Bernouilli random variable of parameter $N'_S(z)$. A positive integer $z$ belongs to $S$ if and only if $X_z = 1$. Thus $P(z\in S) = N'_S(z)$.

Now we compute $u(z)=P(z\notin S + S)$ when $z$ is an odd positive integer. We have:

$$u(z) = \Big[\prod_{k=0}^z P(k\notin S \mbox{ or } z-k \notin S)\Big]^{1/2}.$$

The exponent $\frac{1}{2}$ is because we count $k + (z-k)$ and $(z-k) + k$ as two solutions when it should appear only once in the product. The following is easy to derive from the above product:

$$u(z) = \Big[\prod_{k=0}^z \Big(1-N'_S(k)N'_S(z-k) \Big)\Big]^{1/2}.$$

Thus $$\log u(z)=\frac{1}{2}\sum_{k=0}^z \log\Big(1-N'_S(k)N'_S(z-k) \Big).$$

Note that since $b\geq \frac{1}{2}$, either $N'_S(k)$ or $N'_S(z-k)$ tends to zero in the product when $z\rightarrow\infty$, so we have the approximation

$$\log\Big(1-N'_S(k)N'_S(z-k) \Big) \approx -N'_S(k)N'_S(z-k).$$

Also,

$$\sum_{k=0}^z N'_S(k)N'_S(z-k) \sim \int_0^z N'_S(v)N'_S(z-v)dv = z\cdot\int_0^1 N'_S(z(1-v))N'_S(zv)dv\sim r'(z).$$

It follows immediately that $$u(z) \approx \exp\Big[-\frac{1}{2} r'(z)\Big].$$

Similar reasoning for the case "$z$ even" leads to the same result. To complete the proof, note that

$$w(z)=\sum_{k=0}^z u(k) \sim \int_0^z u(v) dv \approx \int_0^z \exp\Big[-\frac{1}{2} r'(v)\Big] dv.$$

Some open problems

Let $R$ be the set of exceptions, that is, the finite set of positive integers that can not be written as $z=x+y$ with $x,y \in S$. Let

• $Y_z$ be a bernouilli random variable of parameter $u(z)$, such that $z\in R$ if and only if $Y_z=1$
• $N_R(z)=Y_0 + Y_1 +\cdots + Y_z$ be the number of exceptions less or equal to $z$
• $N_R(\infty)<\infty$ be the total number of exceptions
• $M_R$ be the largest exception ($M_R=k$ if and only if $Y_k=1$ and $Y_{k+n}=0$ for $n>0$).

All these variables are random variables. We have established (see above) that $$w(z) = E[N_R(z)] \approx \int_0^z \exp(-r'(v)/2) dv.$$

The big challenge here to make further progress is that the $Y_z$'s are not independent. Problems to investigate are

• What are the variances of $N_R(z), N_R(\infty)$ and $M_R$? (they are finite)
• What is the expectation of $M_R$? (it is finite)
• Are $N_R(\infty)$ and $M_R$ bounded random variables? If yes, what are the upper bounds?

The fact that $E[N_R(\infty)]$ is bounded does not imply that $N_R(\infty)$ is bounded. It may or may not be the case depending on $a, b, c$. If we had a positive answer to that question, we could make a tiny bit of progress towards proving Golbach's conjecture ($a=1,b=0,c=1$), though there are other big hurdles to overcome (the fact that primes are not random enough, for instance the sum of two odd primes is never an odd number).

Note that the Central Limit Theorem does not apply to $N_R(z)=Y_0+\cdots +Y_z$ because of auto-correlations in the $Y_k$'s, and especially the fact that $\mbox{Var}[N_R(z)]$ is bounded no matter how large $z$ is. It is very obvious based on empirical evidence that $(N_R(z)-E[N_R(z)])/\sqrt{\mbox{Var}(N_R(z))}$ does not tend to a Gaussian variable as $z\rightarrow\infty$, even if $S$ is a very thin set (e.g. $a=\frac{1}{100}, b=0.50001, c=200$) resulting in a very, very, very large yet finite $E[N_R(\infty)]$. Similar examples of lack of convergence to a Gaussian distribution are illustrated in one of my articles, see here.

A possible approach is to use the Borel-Cantelli lemma, or a sharper version of it to the set $R$, see here. Then, since $\sum_{z=1}^\infty u(z) < \infty$, it follows that with probability 1 (that is, almost surely), $Y_z=1$ only for finitely many integer $z$'s, and thus both $N_R(\infty)$ and $M_R$ are almost surely finite.