加入
Composite numbers in sumsets of sparse sets
Show that if A, B ⊆ {1,…,N} each have at least N^0.49 elements, then the sumset A + B contains a composite number.
shoal 2周前提交
0 个父提交
提交 5c5ae8dcc1222c60ed8464bd3b18206fa6ac5da8
+39 −0 README.md 新增 查看文件
| @@ -0,0 +1,39 @@ | ||
| 1 | +# Composite numbers in sumsets of sparse sets | |
| 2 | + | |
| 3 | +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. | |
| 4 | + | |
| 5 | +## Problem | |
| 6 | + | |
| 7 | +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? | |
| 8 | + | |
| 9 | +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. | |
| 10 | + | |
| 11 | +## Background | |
| 12 | + | |
| 13 | +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". | |
| 14 | + | |
| 15 | +## What is known | |
| 16 | + | |
| 17 | +- 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$. | |
| 18 | +- 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). | |
| 19 | +- 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. | |
| 20 | +- 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$. | |
| 21 | + | |
| 22 | +## What would count as progress | |
| 23 | + | |
| 24 | +- A proof for any explicit exponent $\delta < 1/2$, which would also give a new proof of the inverse Goldbach conjecture. | |
| 25 | +- A conditional proof, for example assuming the Generalized Riemann Hypothesis or an inverse large sieve conjecture, for $\delta = 0.49$. | |
| 26 | +- 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. | |
| 27 | +- A formal proof of the Lean statement `green_58` in [GreensOpenProblems/58.lean](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/GreensOpenProblems/58.lean) (google-deepmind/formal-conjectures). | |
| 28 | + | |
| 29 | +## References | |
| 30 | + | |
| 31 | +1. B. Green and A. J. Harper, [Inverse questions for the large sieve](https://doi.org/10.1007/s00039-014-0288-1), Geom. Funct. Anal. **24** (2014), 1167–1203; [arXiv:1311.6176](https://arxiv.org/abs/1311.6176). | |
| 32 | +2. C. Elsholtz, [The inverse Goldbach problem](https://doi.org/10.1112/S0025579300014406), Mathematika **48** (2001), 151–158. | |
| 33 | +3. X. Shao, [On an inverse ternary Goldbach problem](https://arxiv.org/abs/1404.6022), Amer. J. Math. **138** (2016), 1167–1191. | |
| 34 | +4. E. Croot, J. Mao, C. Pohoata and C. H. Yip, [A sharp inverse theorem for the quadratic large sieve](https://arxiv.org/abs/2607.15311), arXiv:2607.15311 (2026). | |
| 35 | +5. OpenAI, [The additive indecomposability of the primes](https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/the-additive-indecomposability-of-the-primes-September-24-2026/paper.pdf), preprint (2026). | |
| 36 | + | |
| 37 | +## Source | |
| 38 | + | |
| 39 | +Imported from [Ben Green's 100 open problems 58](https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf#problem.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. | |