Ostmann's inverse Goldbach problem: can $A+B$ be the primes up to finitely many exceptions? (Erdős #431)
Statement
Do there exist two INFINITE sets of positive integers $A$ and $B$ such that the sumset $A+B=\{a+b : a\in A,\ b\in B\}$ agrees with the set of prime numbers up to finitely many exceptions? That is, is the symmetric difference between $A+B$ and the set of primes finite for some infinite $A,B$?
Acceptance. FULLY RESOLVES: either a proof (machine-checkable preferred, otherwise a complete written proof) that NO infinite sets $A,B$ with $A+B$ equal to the primes up to finitely many exceptions exist; OR an explicit construction of such infinite $A,B$ together with a proof that their sumset differs from the primes in only finitely many places. ADVANCES (each independently checkable): strictly improve either side of the Elsholtz–Harper bound stated in the background (a proven upper bound below $x^{1/2}\log\log x$ or lower bound above $x^{1/2}/(\log x\log\log x)$ on $|A\cap[1,x]|$ for any admissible $A$); or a conditional non-existence proof under a clearly stated and named hypothesis; or extend Elsholtz's three-set non-existence result to a strictly larger regime. Deliver the proof, or the explicit sets with a verification of the sumset condition.
Background
A problem of Ostmann, commonly called the 'inverse Goldbach problem'. Raised by Erdős [Er61, p.225], [Er77c], [Er80], and Erdős–Graham [ErGr80, p.85]; in [Er80] Erdős dates it to roughly 1955. Listed as open on erdosproblems.com/431 (fetched 2026-07-21, status 'open'). The expected answer is NO — the primes should not admit such a nontrivial additive decomposition. The strongest evidence is due to Elsholtz and Harper [ElHa15], who proved that if infinite $A,B$ form such a representation then, for all large $x$, $$\frac{x^{1/2}}{\log x\,\log\log x}\ll |A\cap[1,x]| \ll x^{1/2}\log\log x,$$ and symmetrically for $B$ — pinning both sets near $x^{1/2}$. Elsholtz [El01] proved there are NO three sets $A,B,C$ (each of size at least $2$) with $A+B+C$ equal to the primes up to finitely many exceptions. In the positive direction, Granville [Gr90] showed (conditional on the prime $k$-tuples conjecture) that infinite $B,C$ exist with $\{(b+c)/2\}$ a subset of the primes, and Tao–Ziegler [TaZi23] gave an unconditional construction of infinite $B=\{b_1<\cdots\},C=\{c_1<\cdots\}$ with $\{b_i+c_j : i<j\}$ a subset of the primes. See also the related Erdős #429 and #432 (erdosproblems.com/429, /432). The attacker's tool: multiplicative and sieve number theory plus additive combinatorics, sharpening the Elsholtz–Harper counting window until it collapses to a contradiction.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #431 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.