Goldbach conjecture and other problems in additive combinatorics

Question

The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance:

• $S = T$ is the set of primes (leading to Goldbach's conjecture)
• $S$ is the set of squares and $T$ is the set of primes, leading to the deeper Hardy and Littlewood's Conjecture $H$, see my previous question here

A possible approach to check if $S+T = \{x+y, x\in S, y \in T\}$ covers all sufficiently large integers is as follows.

Define $N_S(x)$ as the number of elements in $S$ that are smaller or equal to $x$, and $N_T(y)$ as the number of elements in $T$ that are smaller or equal to $y$. The $n$-th element of $S$ is $N_S^{-1}(n)$, and $n$-th element of $T$ is $N_T^{-1}(n)$. The number $r(z)$ of solutions to $$N_S^{-1}(x) + N_T^{-1}(y) \leq z$$ is asymptotically $$r(z) \sim \int_0^{N_S(z)} N_T(z-N_S^{-1}(x)) dx.$$

The number $t(z)$ of ways that an integer $z$ can be written as $x+y$ with $x\in S, y\in T$ is thus $$t(z) = r(z) - r(z-1) \sim \frac{dr(z)}{dz}$$ as $z$ becomes larger and larger. So in order to prove that for $z$ large enough, $z$ is the sum of an element of $S$ and an element of $T$, one "only" has to prove that $t(z) > 0$ for $z$ large enough.

Question

Is it possible to solve this problem using extremely precise approximations in all the asymptotic derivations discussed here? For instance, if $S$ is the set of prime numbers, then $N_S(z) \sim z/\log z$ and $N_S^{-1}(z)=z\log z$, but this is not precise enough to prove that every large enough even integer is the sum of two primes. You need far better approximations. Likewise, if $S$ is the set of squares, then $N_S(z) \sim \sqrt{z}$ and $N_S^{-1}(z)=z^2$, but this is not enough to prove that every large enough non-square integer is the sum of a square and a prime.

One issue is with the integral, which is only the first term in an Euler - Maclaurin series expansion to approximate $r(z)$. You need to use more than just the first term. If $S=T$ are the sets of squares, rather precise formulas are available for $r(z)$: see the Gauss-circle problem, here (Wikipedia) and here (MSE).

Another question is whether my method is equivalent to the circle method.

Note

Besides $N_S(x), N_S^{-1}(x), N_T(y), N_T^{-1}(y), r(z), dr(z)/dz$, another quantity of interest is the probability for an integer $z$ to belong to $S$: it is defined as $dN_S(z)/dz$, for instance, equal to $1/\log z$ if $S$ is the set of primes.

Illustration

When $S$ is the set of squares and $T$ the set of primes, I made all the computations in my previous question: see here. I also added a lot of new material recently, for instance: among the first 750,000 integers, $z=78754$ is the last one to admit only one ($r(z) = 1$) decomposition as $z=x^2+y$ with $x$ integer and $y$ prime. That is, if $z>78754$ then $r(z) > 1$. Likewise:

• $z=101794$ is the last one with $r(z) =2$
• $z=339634$ is the last one with $r(z) =3$
• $z=438166$ is the last one with $r(z) =4$
• $z=383839$ is the last one with $r(z) =5$

The sequence of $z$'s with $r(z)=1$ is listed at the bottom of my previous question, see here. I searched for this sequence to see if it had been discovered, but could not find any reference.

Conclusion

If my approach (assuming it is new!) ever leads to a proof of some famous conjectures, the proof will be very technical, difficult and long. It is beyond my reach but some mathematicians with experience dealing with extremely precise (second- or third-order approximations) to the asymptotics involved might have an answer about the feasibility of my approach. Just to give an idea of the many problems, it may require excellent asymptotics about a function more complex than the Lambert function (again, this briefly outlined in my previous question).

Maybe the following is true for sums of two primes and sums of a prime and and a square: there only finitely many $z$'s that can be expressed as $z=x+y$ in less than $k$ different ways, with $x\in S, y \in T$, regardless of $k$. This would imply that all but a finite number of $z$'s can be expressed as the sum in question.

Answer 1

It seems what you are asking is "If we have a precise asymptotic for the number of elements of a set, can we solve binary additive problems involving that set?"

The answer in general seems to be `no'. Let's consider Goldbach's conjecture that every large integer $n$ is the sum of two primes. It is not hard to see from pigeonholing that the typical $n$ will have at most $O( n / \log^2 n)$ solutions to $n=p+q$ within the primes. In fact, classical sieve theory easily establishes a uniform upper bound of this form unconditionally.

Now pick a rapidly increasing sequences of numbers $n'$ and remove from the set of primes those primes arising in solutions to $n'=p+q$ for that given $n'$. For each $n'$ we have removed at most $O(n' / \log^2 n')$ elements from the full set of primes, and so the asymptotic of the counting function of our set has not changed, however the assertion that every large integer is the sum of two elements from our modified set is now false.

You might object that my modified set of primes will not satisfy the more precise asymptotics (with error terms) that hold for the primes, such as the consequences of the (Generalized) Riemann Hypothesis or the Elliott-Halberstam conjectures. And this is true. However, there has been a lot of effort put into trying to deduce solutions to additive problems conditional on these conjectures, and even assuming these conjectures there is no known proof of either of the two famous additive problems (Goldbach and twin primes). Indeed there is an obstruction related to the "parity problem" in sieve theory which also enters the picture.

This does give rise to the following interesting question, which I do not know the answer to:

Does there exist a set of integers that satisfies the asymptotic behavior of the primes in arithmetic progressions (with the error term implied by GRH), but which fails to satisfy weak Goldbach?

A negative answer to this question would fairly conclusively yield a negative answer to your question.

Answer 2

The formula $$r(z) \sim \int_0^{N_S(z)} N_T(z-N_S^{-1}(x)) dx$$ can be re-written in a more appealing way. With the change of variable $u=N_S^{-1}(x)$ it becomes $$r(z) \sim \int_0^{z} N_T(z-u)N'_S(u) du,$$ where $N'_S(u)$ is the derivative of $N_S(u)$ with respect to $u$. With an additional change of variable $u=zv$ it becomes $$r(z) \sim z\int_0^{1} N_T(z(1-v))N'_S(zv) dv.$$ Likewise $$t(z) \sim r'(z) = \frac{dr(z)}{dz} =z\int_0^{1} N'_T(z(1-v))N'_S(zv) dv .$$

An interesting case is when $S=T$ and $$N_S(u) \sim \frac{a u^b}{(\log u)^c}, \mbox{ with } 0<a, 0<b\leq 1, \mbox{ and } c \geq 0.$$ This covers sums of two primes ($a=1, b=1, c=1$) and sums of two squares ($a=1, b=\frac{1}{2}, c=0$). We have: $$r(z) \sim \frac{a^2b z^{2b}}{(\log z)^{2c}}\cdot \int_0^1 (1-v)^b v^{b-1}dv = \frac{a^2b z^{2b}}{(\log z)^{2c}}\cdot \frac{\Gamma(b)\Gamma(b+1)}{\Gamma(2b+1)}$$

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

Notes

• Solutions such as $z=x+y$ and $z=y+x$ count as two solutions: $(x,y)$ and $(y, x)$.

• The asymptotic formula for $t(z) \sim r'(z)$, representing the number of solutions to $z=x+y$ with $x\in S, y\in T$ is true only on average, as $z$ becomes larger and larger. There may still be infinitely many integer $z$'s for which $t(z)=0$ even if $r'(z) \rightarrow\infty$ as $z\rightarrow\infty$.

• We assume that the sets $S$ and $T$ are "well balanced", both for small and large values. For instance, if you remove the first $10^{5000}$ elements of $S$, the asymptotic formula for $N_S(u)$ remains unchanged, but this is likely to cause many formulas to fail.

• On some tests, I noticed that there are more solutions (on average) to $z=x+y$ with $x\in S, y\in T$ (here $x, y, z$ are integers), if $z$ is even.

• If $S=T$ is the set of primes, some adjustments must be made because the primes are not "well balanced", they are less random than they seem (for instance the sum of two odd primes can not be an odd number, but there are also more subtle issues). This is best described in the Wikipedia entry about Goldbach's conjecture (see section about heuristics).

• To generate a set like $S$, one way is as follows. Use a random number generator function $U$ returning independent uniform deviates on $[0, 1]$. If $U(k) < N'_S(k)$ then add the integer $k$ to the set $S$, otherwise discard it. Do that for all integers.

• For sums involving three terms, say $R+S+T$, you can proceed as follows: first work on $S'=R+S$ and derive all the asymptotics for $S'$ using the methodology proposed here. Then work on $S'+T$.

• If there are singularities in the functions $N_S$ or $N_S'$, they must be handled properly in the integral formulas, unless the integrals are improper but converging.

Generalization of the formula

It also works if $S\neq T$. Say

$$N_S(u) \sim \frac{a_1 u^{b_1}}{(\log u)^{c_1}}, N_T(u) \sim \frac{a_2 u^{b_2}}{(\log u)^{c_2}}$$ with $0<a_1,a_2, 0<b_1, b_2 \leq 1$, and $c_1, c_2 \geq 0$. Then

$$r(z) \sim \frac{a_1 a_2 z^{b_1 + b_2}}{(\log z)^{c_1+c_2}}\cdot \frac{\Gamma(b_1 +1)\Gamma(b_2+1)}{\Gamma(b_1 + b_2+1)}$$

$$r'(z) \sim \frac{a_1 a_2 z^{b_1 + b_2 -1}}{(\log z)^{c_1+c_2}}\cdot \frac{\Gamma(b_1 +1)\Gamma(b_2+1)}{\Gamma(b_1 + b_2)}$$

In particular, it applies to sums of a square and a prime, see here. A generalization to sums of $k$ sets is discussed in my new MO question, here.

Answer 3

Here is a possible path to prove Golbach's and other conjectures in additive number theory, such as the deeper Hardy and Littlewood's $H$ conjecture (All but 21 non-square integers are the sum of a square and a prime). The idea is to try to prove a far deeper, more generic, and stronger result which is just a pure analytical result, not even connected anymore to number theory, in the same way that the roots of Riemann's function is a purely analytical problem that can solve many number theory problems.

It goes as follows. Note that Golbach can be rewritten as follows: each sufficiently large positive integer $z$ can be written as $z=(p-1)/2 + (q-1)/2$ where $p,q$ are odd primes.

Step #1: remove almost all primes from the set $S$ of primes, but still keep infinitely many of them. Just keep a tiny fraction of them and the conjecture (now much stronger) still remains true. The number of primes less than $z$ is $~ z / \log z$, and we are removing so many of them that the number of elements in $S$ that are less than $z$, after removing all these primes, is of the order $z^{2/3}$. In order to achieve this and keep $S$ "well balanced", keep only the primes closest to $z^{3/2}$, for $z=2, 3, 4, 5$ and so on. Thus the new set $S$ satisfies $N_S(x) \sim x^{2/3}$. Based on my above answer, on average each element of $S$ has still a growing number of solutions to $z= x+y$ with $x\in S, y\in S$, as $z$ is growing.

Step #2: now $S$ is "well balanced" (this concept still needs to be defined, this is the most difficult part of the problem), and any well-balanced set $S$ with $r'(z) \rightarrow \infty$ (this is the case here) satisfies the following conjecture ($w$ is an integer):

$$m(z) = \min_{w\geq z} t(w) \rightarrow \infty \mbox { as } z\rightarrow \infty.$$

That is, not only each integer $z$ can be represented as $z=x+y$ with $x\in S, y\in S$, in at least one way, but it actually can be represented in that form in an growing number of ways as $z$ increases.

Illustration

I created 50 different sets $S$ that satisfy the requirements of steps #2, with $N_S(x)\sim \frac{3}{2} x^{2/3}$. The blue curve is the average value of $t(z)$ on the Y-axis, with $z$ (an integer) between $2$ and $250000$ on the X-axis. The red curve represents the minimum $t(z)$ for each $z$ computed across the 50 sets. Even that minimum seems to be growing indefinitely.

Below is the source code to produce these charts. They come from the last part of the code, producing the text file Prob4.txt. It is written in Perl.

$N=500000;  
$Nsamples=50;

$a=1;
$b=1/3;

$seed=50000;
srand($seed);

open(OUT,">prob.txt");
open(OUT1,">prob1.txt");
open(OUT2,">prob2.txt");
open(OUT3,">prob3.txt");

for ($sample=0; $sample<$Nsamples; $sample++) {

# -> use better rand generator?


%hash=();
$c=0;

for ($k=2; $k<$N; $k++) {
  $r=rand();
  if ($r < $a/($k**$b)) { 
    $hash{$k}=1;
    $c++;
    print OUT "$sample\t$c\t$k\n"; 
  }  
}

#-----------------

$max_z=-1;
@count=(); 
foreach $x (keys(%hash)) {
  foreach $y (keys(%hash)) {
    $z=$x+$y;
    if ($z< $N) { 
      $count[$z]++; 
      if ($z>$max_z) { $max_z=$z; }
    }
  }
}

#------------------

$c=0;
@max=();
for ($k=2; $k<$N; $k++) {
  $cn=$count[$k];  
  if ($cn eq "") { $cn=0; $count[$k]=0; }
  $max[$cn]=$k;     # largest z for which z = x + y has k solutions
  $c+=$count[$k];   # cumulative count
  print OUT1 "$sample\t$k\t$cn\t$c\n"; 
}

for ($k=0; $k<40; $k++) {
  print OUT2 "$sample\t$k\t$max[$k]\n";
}


#-------------
#compute largest z for which z = x + y has k or fewer solutions
#  

print "sample: $sample -- max: $max_z\n";

$min=999999999;
for ($k=$max_z; $k>1; $k--) {
  if  ($count[$k]< $min) { $min=$count[$k]; }
  if ($k < $N/2) { print OUT3 "$sample\t$k\t$min\n"; }
}


}


close(OUT);
close(OUT1);
close(OUT2);
close(OUT3);

--------------------------------------------------------------------
# post analysis

@amin=();
@minmin=();
for ($k=2; $k<$N/2; $k++) { $minmin[$k]=999999999; }

open(IN,"<prob3.txt");
while ($i=<IN>) {
  $i=~s/\n//g;
  @aux=split(/\t/,$i);
  $sample=$aux[0];
  $k=$aux[1];
  $min=$aux[2];
  $amin[$k]+=$min;
  if ($min<$minmin[$k]) { $minmin[$k]=$min; }

}
close(IN);

open(OUT,">prob4.txt");
for ($k=2; $k<$N/2; $k++) {
  $avg=$amin[$k]/$Nsamples;
  print OUT "$k\t$avg\t$minmin[$k]\n";
}
close(OUT);

A very interesting reference

In a paper by Andrew Granville, published in Project Euclid (see here) one can read the following:

This is very similar to what I discuss here. While Andrew comes up with $N_S(x) \propto \sqrt{x \log x}$, a stronger result than my $N_S(x) \propto x^{2/3} $ since he needs even fewer primes than me, it is using the same idea that you only need to work with a tiny subset of all primes to prove Goldbach. His argument is probabilistic thus not a proof, mine is non-probabilistic but I don't end up with a proof either. Note that my $x^{2/3}$ can be reduced to $x^\mu$ for any $\mu> \frac{1}{2}$, based on the results featured in my previous answer: that way, we continue to have $r'(z)\rightarrow\infty$ as $z\rightarrow \infty$, which is what we need. If you use $\mu = \frac{1}{2}$, it won't work: $r'(z)=\frac{\pi}{4}$ is a constant, and the primes left are just as rare as square integers. We all know sums of two squares do not cover all integers, but only a very small set of integers, of density zero.

If Andrew Granville had used the more profound law of the iterated logarithm (rather than the central limit theorem), he would probably have ended up with a formal proof of the following result: the density of even integers $z$ that can not be written as $z=x+y$ with $x, y$ belonging to his very small subset of primes, is zero. I believe this statement may have been formally proved already, if you consider the set of all primes, rather than a tiny subset of primes.

Note: Maybe an example of a well-balanced set $S$ is one where the gaps between successive elements is a monotonic (increasing) function. I guess we can make that happen for the tiny subsets of primes needed to prove Goldback, with $\mu=\frac{2}{3}$. However, well-balanced also requires some congruence features. For instance, if all elements of $S$ are odd, then $S$ can not be well-balanced.