Composite numbers in sumsets of sparse sets

If two sets of integers up to $N$ are large enough, the sums of their elements cannot all be prime. Sieve methods prove this once both sets have more than $N^{1/2 + \varepsilon}$ elements, but nobody can push the exponent below one half: the question is whether sets of size $N^{0.49}$ still force a composite sum. It is one of Ben Green's favourite open problems.

Problem

Let $N$ be large and let $A, B \subseteq \{1, \dots, N\}$ with $|A|, |B| \ge N^{0.49}$ . Must the sumset $A + B = \{a + b : a \in A, b \in B\}$ contain a composite number?

More generally, Green and Harper conjectured: for every $\delta > 0$ , if $N$ is sufficiently large in terms of $\delta$ and $A, B \subseteq \{1, \dots, N\}$ satisfy $|A|, |B| \ge N^{\delta}$ , then $A + B$ contains a composite number.

Background

The question grew out of Ostmann's inverse Goldbach problem (1956): can the set of primes, up to finitely many exceptions, be written as $A + B$ with $|A|, |B| \ge 2$ ? Elsholtz (2001) showed that any such decomposition would force both sets to have about $\sqrt{N}$ elements up to $N$ , up to logarithmic factors, so a positive answer to the problem above would rule it out. Green and Harper (2014) noted that their conjecture for any exponent $\delta < 1/2$ would imply the inverse Goldbach conjecture, and that an inverse theorem for the large sieve would also do so. In September 2026 OpenAI posted a proof of the inverse Goldbach conjecture by a different route, with a Lean formalisation of the full statement (an unrefereed preprint); it says nothing about sparse finite sets, so the question here remains open. Below the square-root scale, Green writes, our understanding of sumsets is "close to negligible".

What is known

For sets of size $N^{1/2 + \varepsilon}$ the statement is known; Green and Harper (2014) remark that they cannot prove it for any exponent $\delta \le 1/2$ .
In the other direction, there are sets $A, B \subseteq \{1, \dots, N\}$ with $|A|, |B| \ge \log N / \log\log N$ all of whose sums are prime (Elsholtz, as cited by Shao, 2016).
The three-set analogue is known slightly beyond its natural barrier: Shao (2016) proved that if $A_1, A_2, A_3 \subseteq \{1, \dots, N\}$ each have at least $N^{1/3 - c}$ elements, for some small absolute $c > 0$ , then $A_1 + A_2 + A_3$ contains a composite number, improving the bound $N^{1/3}$ from Gallagher's larger sieve.
Green and Harper showed that a positive solution would follow from a sufficiently good understanding of the inverse large sieve problem (sets occupying at most about half the residue classes modulo every prime look like values of a quadratic). Recent progress on that problem: Croot, Mao, Pohoata and Yip (2026) showed that such a set of size $\gg \sqrt{N}$ in $\{1, \dots, N\}$ has at least $\exp(c\sqrt{\log N}/\log\log N)$ elements in the image of a single quadratic $m \pm x^2$ .

What would count as progress

A proof for any explicit exponent $\delta < 1/2$ , which would also give a new proof of the inverse Goldbach conjecture.
A conditional proof, for example assuming the Generalized Riemann Hypothesis or an inverse large sieve conjecture, for $\delta = 0.49$ .
Explicit large pairs $A, B \subseteq \{1, \dots, N\}$ all of whose sums are prime, for moderate $N$ , to show how far below $\sqrt{N}$ the true threshold lies; any such pair is checked by testing $|A|\,|B|$ numbers for primality.
A formal proof of the Lean statement green_58 in GreensOpenProblems/58.lean (google-deepmind/formal-conjectures).

References

B. Green and A. J. Harper, Inverse questions for the large sieve, Geom. Funct. Anal. 24 (2014), 1167–1203; arXiv:1311.6176.
C. Elsholtz, The inverse Goldbach problem, Mathematika 48 (2001), 151–158.
X. Shao, On an inverse ternary Goldbach problem, Amer. J. Math. 138 (2016), 1167–1191.
E. Croot, J. Mao, C. Pohoata and C. H. Yip, A sharp inverse theorem for the quadratic large sieve, arXiv:2607.15311 (2026).
OpenAI, The additive indecomposability of the primes, preprint (2026).

Source

Imported from Ben Green's 100 open problems 58, curated by Ben Green. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.