The inverse Goldbach problem

by Christian Elsholtz

Submission September 7, 2000 (this version includes galley corrections). Appeared in Mathematika 2001.

Abstract We improve the upper and lower bounds of the counting functions of the conceivable additive decomposition sets of the set of primes. Suppose that A + B = P′, where P′ differs from the set of primes in finitely many elements only and |A|, |B| ≥ 2.

Here we prove the following bounds on the counting functions A(x) and B(x), for sufficiently large x:

x^{1/2}(log x)^{−5} ≪ A(x) ≪ x^{1/2}(log x)^{4}.

The same bounds hold for B(x).

This immediately solves the ternary inverse Goldbach problem: there is no ternary additive decomposition A + B + C = P′, where P′ is as above and |A|, |B|, |C| ≥ 2.

1 Introduction

The inverse Goldbach problem is the question of whether the set of primes has an additive decomposition in the following sense. Given subsets A and B of the positive integers, let

A + B := {a + b : a ∈ A, b ∈ B}

be the sum of these two sets. Let P denote the set of primes. Let P′ denote a set of positive integers that differs from the set of primes P in only finitely many elements, i.e., for sufficiently large x_{0}, we have P ∩ [x_{0}, ∞] = P′ ∩ [x_{0}, ∞]. It is easy to see that A + B = P cannot hold with |A|, |B| ≥ 2. But the following question of Ostmann (see page 13 of [9], or [2]) is still open: do there exist sets A, B and P′ with |A|, |B| ≥ 2 such that

A + B = P′?

Even though it is generally believed that such a decomposition cannot exist, this might, according to Erdős (see [5]), be out of reach. The problem was posed again in the problem session at the 1998 Oberwolfach conference by Prof. Wirsing (see [14]). Partial answers concentrated on bounds of the counting functions A(x) = ∑_{a∈A,a≤x} 1 and B(x). Note that such a decomposition would have far reaching consequences towards the prime ktuple conjecture. It is easy to see that both A and B must contain infinitely many elements (see [4], [7], [9], [5]). If b_{1}, b_{2}, …, b_{k} ∈ B, then there would be infinitely many integers n such that n + b_{1}, …, n + b_{k} are simultaneously prime. Here we prove the following bounds on the counting functions A(x) and B(x): Theorem. Suppose that there exist sets P′, A, B with P′ = A + B, where |A|, |B| ≥ 2 and P′ coincides with the set of primes for elements p > x_{0}. For sufficiently large x ≥ x_{1} the following bounds hold:

\frac{x^{1/2}}{(log x)^{5}} ≪ A(x) ≪ x^{1/2}(log x)^{4}.

The same bounds hold for B(x). Our theorem immediately implies the following corollary.

Corollary (Solution of the inverse ternary Goldbach problem). There do not exist sets of integers A, B, and C with |A|, |B|, |C| ≥ 2, and a set P′ which coincides with the set of primes P for sufficiently large elements such that A + B + C = P′ holds.

Our bounds in the binary case are close to best possible and should be compared with previous results on this subject. Hornfeck (see [4]) proved for arbitrary k that

(log x)^{k} ≪ A(x) ≪ \frac{x}{(log x)^{k}}

holds. Hofmann and Wolke (see [5]) improved this to

exp (c\frac{log x}{log_{2} x}) ≪ A(x) ≪ \frac{x}{exp (c\frac{log x}{log_{2} x})}

and the present author (see [1]) refined their method to yield

exp (c_{r} \frac{log x}{log_{r} x}) ≪ A(x) ≪ \frac{x}{exp (c_{r} \frac{log x}{log_{r} x})} for any r.

Here log_{r} x denotes the r-th iterated logarithm. The same bounds hold for B(x). In the seventies, Wirsing proved (see [13]) that A(x)B(x) = O(x), a result which was independently proved by Pomerance, Sárközy & Stewart (see [10]) and Hofmann & Wolke (see [5]). Acknowledgements: the research on this paper was done while the author was working at the University of Stuttgart. He would like to thank J. Brüdern for encouraging remarks on earlier versions of this paper. Further thank goes to S. Daniel, C. List, L. Lucht, A. Schinzel, E. Wirsing, and D. Wolke for comments or further references.

2 Proof

Let us first prove that our theorem implies the corollary. We make use of the following result, which is a special case of a theorem of Pomerance, Sárközy, and Stewart, see theorem 3 of [10].

Lemma 1. Let ε be a positive real number, let x be a positive integer, and let A, B, C denote nonempty subsets of {1, ⋯, x}. For sufficiently large x and for min(|A|, |B|, |C|) > x^{1/3+2ε} there is a prime p with

p < x^{1/3+ε}

such that A + B + C contains an element which is divisible by p.

Proof of the corollary. It follows from (A + B) + C = (A + C) + B = A + (B + C) = P′ and the lower bound found in the binary inverse Goldbach problem (which is our theorem) that A(x), B(x), C(x) ≫ x^{1/2−ε}. For x > (x_{1})^{2.5} let A_{1} = A ∩ [x^{0.4}, ∞]. Then A_{1}(x) ≫ x^{1/2−ε} still holds. The lemma implies that A_{1} + B + C contains an element a_{1} + b + c ≥ x^{0.4} which is divisible by some prime p ≤ x^{1/3+ε}. This proves the corollary. Of course, the same conclusion holds for more than three summands.

Before we turn to the proof of the theorem we have to recall some known results about the large sieve method and describe the new method. The large sieve method has been invented to deal with sieve problems where a large number of residue classes modulo primes can be sifted. Suppose now we consider a sieve problem involving two sequences of integers. Then our new method allows to remove any given residue class either when sifting the first sequence by the first sieve method or when sifting the second sequence by the second sieve method. This means that all residue classes can be used in this combined sieve method. Let us state Montgomery’s sieve (see [8]):

Lemma 2. Let P denote the set of primes. Let p be a prime. Let C denote a set of integers which avoids ω(p) residue classes modulo p. Here ω : P → ℕ with 0 ≤ ω(p) ≤ p − 1. Let C(x) denote the counting function C(x) = ∑_{c≤x,c∈C} 1. Then the following upper bound on the counting function holds:

C(x) ≤ \frac{2x}{L}, where L = ∑_{q≤x^{1/2}} μ^{2}(q) ∏_{p|q} \frac{ω(p)}{p − ω(p)}.

Vaughan (see [11]) has found a suitable evaluation of L if ∑_{p≤y} \frac{ω(p)}{p} is known.

Lemma 3. The following lower bound holds:

L ≥ ∑_{m} exp (m log (\frac{1}{m} ∑_{p≤x^{1/(2m)}} \frac{ω(p)}{p})) .

The size of this sum can be approximated by choosing a value of m which maximizes the summand. The parameter m denotes the number of prime factors of q in the definition of L.

Hence 1 ≤ m ≤ \frac{log(x^{1/2})}{log 2}.

In situations where the number of removed residue classes is close to p, so that only a small number of classes remain, it is better to use Gallagher’s larger sieve (see [3]).

Lemma 4. Let S denote a set of primes such that A lies modulo p (for p ∈ S) in at most ν(p) residue classes. Then the following bound holds, provided the denominator is positive:

A(x) ≤ \frac{− log x + ∑_{p∈S} log p}{− log x + ∑_{p∈S} \frac{log p}{ν(p)}} .

We intend to use Montgomery’s sieve to give an upper bound for A(x). In view of π(x) ≪ A(x)B(x) this also implies lower bounds for B(x). For a ∈ A, b ∈ B, a + b = p_{1} ∈ P (for p_{1} > x_{0}) we have a ≢ −b mod p for all primes p < p_{1}. A residue class that occurs in B induces a forbidden residue class in A. This class will be used in the application of Montgomery’s sieve for an upper bound on A(x). On the other hand, a class modulo p that does not occur in B can be sifted, when using Gallagher’s sieve for bounds on B(x). Even though we do not know how many residue classes modulo p are needed to cover the set B we do know that this number cannot be too small (on average). If the number of classes covering B is small, then many classes are excluded and an application of Gallagher’s sieve implies an upper bound on B(x) that contradicts existing lower bounds. This combination of both types of the large sieve gives us new information which finally leads to much better bounds than were known before. We now come to the details of the proof. We will first prove a slightly weaker result and then iterate the argument.

Proposition. For any ε > 0 and for sufficiently large x ≥ x_{2}, we have the following bounds:

x^{1/2−ε} ≪ A(x) ≪ x^{1/2+ε}.

The same bounds hold for B(x).

For sufficiently large x > (x_{0})^{2}, we know that

P ∩ (x^{1/2}, ∞) = P′ ∩ (x^{1/2}, ∞).

Put

A_{1} = A ∩ (x^{1/2}, x), B_{1} = B ∩ (0, x).

For any prime x_{0} < p ≤ x^{1/2}, let ν_{A_{1}}(p) and ν_{B_{1}}(p) denote the number of residue classes modulo p that contain elements of A_{1} and B_{1}, respectively. Now a_{1} + b_{1} (with a_{1} ∈ A_{1}, b_{1} ∈ B_{1}) is a prime p_{1} > x^{1/2}, i.e. a_{1} + b_{1} ≢ 0 mod p for any prime p ≤ x^{1/2}. Hence, for any prime x_{0} < p ≤ x^{1/2}, a_{1} lies outside ν_{B_{1}}(p) residue classes modulo p. Let us sketch Hornfeck’s bounds: With |B| ≥ 2 one can apply a two dimensional sieve which leads to A(x) ≪ \frac{x}{(log x)^{2}} . From π(x) ≪ A(x)B(x) we see that B(x) ≫ log x. In

particular, B has infinitely many elements so that we can apply in a next step, for any fixed k, a k + 1-dimensional sieve which proves A(x) ≪ \frac{x}{(log x)^{k+1}} and B(x) ≫ (log x)^{k}.

At this stage, the argument of Hofmann and Wolke continues with sieving with ω(p) = c_{k}(log p)^{k}. This uses the fact that the elements of B which are less than p trivially lie in distinct classes modulo p. We take a completely different approach. We exploit the fact that (log x)^{k} can be considerably larger than (log p)^{k}. Hence ω(p) can be chosen possibly much larger than assumed by Hofmann and Wolke. In fact we shall make two iterations of essentially the same argument using different parameters. Iteration A: We shall use lemma 3 with the following choice of m:

m = m_{A} = [\frac{ε}{4} \frac{log x}{log log x}] .

Let y = x^{1/(2m)}. Hence y ∼ (log x)^{2/ε}. For the sieve process we use all primes in the interval x_{0} < p ≤ y. We split these primes into two sets,

P_{A1} := {x_{0} < p ≤ y | ν_{B_{1}}(p) < p^{1−ε}} and P_{A2} := {x_{0} < p ≤ y | ν_{B_{1}}(p) ≥ p^{1−ε}}.

One of these two sets must contain at least half of the primes of the interval (x_{0}, y]. Let condition A1 denote the case in which P_{A1} contains at least half of these primes. Similarly, condition A2 is satisfied when P_{A2} contains at least half of these primes.

Lemma 5. By the prime number theorem we have

− log x + ∑_{p∈P_{A1}} log p ≤ ∑_{p≤y} log p ∼ y.

Lemma 6. Suppose that condition A1 holds. Then we have (for y → ∞)

∑_{p∈P_{A1}} \frac{log p}{p^{1−ε}} ≫ y^{ε}.

Because of the monotonicity of \frac{log p}{p^{1−ε}}, the worst case occurs when all occurring primes are as

large as possible.

∑_{p∈P_{A1}} \frac{log p}{p^{1−ε}} ≫ y^{ε} − (\frac{2y}{3} )^{ε} ≫ y^{ε}.

(Recall that both intervals, (x_{0}, \frac{y}{2}] and (\frac{y}{2}, y] contain asymptotically half of the primes of the interval (x_{0}, y]. Since P_{A1} contains by assumption half of these primes, the sum is -in this worst case- essentially over the interval (\frac{y}{2}, y].)

Since y ≫ (log x)^{2/ε}, the last lemma implies:

Lemma 7. Suppose that condition A1 holds. Then we have

− log x + ∑_{p∈P_{A1}} \frac{log p}{ν_{B_{1}}(p)} ≫ y^{ε}.

Similarly we can state a lemma corresponding to condition A2.

Lemma 8. Suppose that condition A2 holds. With ω(p) = ν_{B_{1}}(p) ≥ p^{1−ε} for p ∈ P_{A2} and for y → ∞ we have

∑_{p∈P_{A2}} \frac{ω(p)}{p} ≫ \frac{y^{1−ε}}{log y} .

Again, the worst case occurs when all of the primes in P_{A2} are as large as possible, whence

∑_{p∈P_{A2}} \frac{ω(p)}{p} ≥ (π(y) − π(\frac{2y}{3} )) \frac{1}{y^{ε}} ≫ \frac{y^{1−ε}}{log y} .

After these preliminary remarks the proof of our proposition is very simple. In the case that condition A1 holds, we may apply Gallagher’s sieve with ν_{B_{1}}(p) < p^{1−ε} for p ∈ P_{A1}. By lemmas 5 and 7

B(x) ≤ \frac{− log x + ∑_{p∈P_{A1}} log p}{− log x + ∑_{p∈P_{A1}} \frac{log p}{p^{1−ε}}} ≪ \frac{y}{y^{ε}} = y^{1−ε} ≪ (log x)^{2(1−ε)/ε},

which contradicts previously known lower bounds on B(x), even those due to Hornfeck. Hence condition A2 must hold. We use Montgomery’s sieve to give an upper bound on A(x). Here we may sieve with ω(p) = ν_{B_{1}}(p) ≥ p^{1−ε}, for p ∈ P_{A2}.

Lemma 3 and lemma 8 imply that (for some c > 0)

L ≥ exp (m log (\frac{1}{m} ∑_{p∈P_{A2}} \frac{ω(p)}{p}))
≥ exp (m log (\frac{c}{m} \frac{(x^{1/(2m)})^{1−ε}}{log(x^{1/(2m)})} ))
≥ exp (m log (\frac{c}{m} \frac{2mx^{(1−ε)/(2m)}}{log x} ))
≥ exp (m (log 2 + log c − log_{2} x + \frac{1 − ε}{2m} log x))
≥ exp ((\frac{1}{2} − \frac{ε}{2} − \frac{ε}{4}) log x + m(log 2 + log c))
≫ x^{1/2−ε}.

By Montgomery’s sieve method we have A_{1}(x) ≤ \frac{2x}{L} ≪ x^{1/2+ε}, for any ε > 0. This implies that

A(x) = A_{1}(x) + O(x^{1/2}) ≪ x^{1/2+ε}.

The lower bound B(x) ≫ x^{1/2−ε̃}, for any ε̃ > 0, follows from A(x)B(x) ≫ π(x). This proves our proposition. In this argument we assumed that B(x) ≫ (log x)^{2(1−ε)/ε} is already known. Now, after having proved a much better lower bound, we can expect that the same idea brings us even further towards x^{1/2}. Iteration B The very same argument with differently chosen parameters works as follows: we choose m = 2 so that y = x^{1/4}, and c = 20. We split the primes x_{0} < p ≤ y into two sets,

P_{B1} := \{x_{0} < p ≤ y | ν_{B_{1}}(p) < \frac{p}{c log p}\} and P_{B2} := \{x_{0} < p ≤ y | ν_{B_{1}}(p) ≥ \frac{p}{c log p}\}.

We say that condition B1 holds if P_{B1} contains at least half of the primes of the interval (x_{0}, y]; similarly condition B2 holds if P_{B2} contains at least half of these primes. Let us assume that condition B1 holds. Then we see that for sufficiently large y

∑_{p∈P_{B1}} \frac{log p}{ν_{B_{1}}(p)} ≥ ∑_{p∈P_{B1}} \frac{c(log p)^{2}}{p} ≥ \frac{c}{2} ((log y)^{2} − (log \frac{2y}{3} )^{2}) = c(log \frac{3}{2})(log y) − \frac{c}{2}(log \frac{2}{3})^{2}
≥ 2 log x.

Gallagher’s sieve yields

B(x) ≤ \frac{− log x + ∑_{p∈P_{B1}} log p}{− log x + ∑_{p∈P_{B1}} \frac{log p}{ν_{B_{1}}(p)}} ≤ \frac{y}{log x} = \frac{x^{1/4}}{log x},

which is a contradiction to our proposition. This implies that condition B2 must hold. Therefore P_{B2} must contain at least half of the primes of the interval (x_{0}, y]. By Montgomery’s sieve with ω(p) = ν_{B_{1}}(p) and suitable constants c′ and c′′:

L ≥ exp (m log (\frac{1}{m} ∑_{p∈P_{B2}} \frac{ω(p)}{p}))
≥ exp (m log (\frac{1}{m} ∑_{p∈P_{B2}} \frac{1}{c log p}))
≥ exp (m log (\frac{c′}{m} \frac{y}{(log y)^{2}} ))
≥ exp (2\frac{1}{4} log x − 4 log log x + c′′)
≫ x^{1/2}(log x)^{−4}.

This implies A_{1}(x) ≪ x^{1/2}(log x)^{4}, i.e. A(x) ≪ A_{1}(x) + O(x^{1/2}) ≪ x^{1/2}(log x)^{4}. Hence B(x) ≫ x^{1/2}(log x)^{−5}. By symmetry the same bounds hold for A(x) and B(x), which proves our theorem.

References

[1] Elsholtz, C., A remark on Hofmann and Wolke’s Additive decompositions of the set of primes, Arch. Math. 76, 30–33, (2001).

[2] Erdős, P., Problems and results in number theory, Number Theory Day, New York, 1976, Springer, Lecture Notes in Math. 626, pp.43–72.

[3] Gallagher, P.X., A larger sieve, Acta Arith. 18, (1971), 77–81.

[4] Hornfeck, B., Ein Satz über die Primzahlmenge, Math. Z., 60, (1954), 271–273, see also the correction in vol. 62, (1955), page 502.

[5] Hofmann, A., Wolke, D., On additive decompositions of the set of primes, Arch. Math. 67, (1996), 379–382.

[6] Laffer, W.B., Mann, H.B., Decomposition of sets of group elements. Pacific J. Math. 14, 547–558, (1964).

[7] Mann, H., Addition theorems: The addition theorems of group theory and number theory, Wiley, Interscience, New York-London-Sydney, 1965.

[8] Montgomery, H.L., The Analytic Principle of the Large Sieve, Bull. Amer. Math. Soc., 84, (1978), 547–567.

[9] Ostmann, H.-H., Additive Zahlentheorie. 1. Teil: Allgemeine Untersuchungen, Springer-Verlag, Berlin-Heidelberg-New York, 1968.

[10] Pomerance, C., Sárközy, A., Stewart, C.L., On divisors of sums of integers. III, Pacific J. Math., 133, (1988), 363–381.

[11] Vaughan, R.C., Some Applications of Montgomery’s Sieve, J. Number Theory, 5, (1973), 64–79.

[12] Wirsing, E., Ein metrischer Satz über Mengen ganzer Zahlen. Arch. Math. 4, (1953), 392–398.

[13] Wirsing, E., Über additive Zerlegungen der Primzahlmenge, unpublished manuscript, an abstract can be found in Tagungsbericht 28/1972, Oberwolfach.

[14] Wirsing, E., Problem at the problem session, Abstracts of the Oberwolfach Conference 10/1998.

Author’s address: Christian Elsholtz Institut für Mathematik TU Clausthal Erzstrasse 1 D-38678 Clausthal-Zellerfeld Germany elsholtz@math.tu-clausthal.de

AMS Classification: 11P32 Goldbach type theorems; other additive questions involving primes 11N35 Sieves 11N36 Applications of sieve methods 11P70 Inverse problems of additive number theory