Erdős problem 431: live audit, the current inverse-sieve wall, and exact finite data
Access/search date: 2026-07-26 UTC.
The labels used below are exactly those requested:
- (a) elementary-rigorous: proved here from elementary facts;
- (b) rigorous-modulo-named-theorem: a deduction using the stated,
primary-source theorem;
- (c) plausible/structural-unverified: a heuristic, bounded
literature-search miss, or cost extrapolation;
- (d) computational-only: a live-page observation or exhaustive finite
computation.
0. Mandatory live-page audit
(d) I fetched the rendered [live page for problem
431](https://www.erdosproblems.com/431) and its [live LaTeX
view](https://www.erdosproblems.com/latex/431) through the Bright Data
browser on 2026-07-26. I did not use the supplied YAML for the go/no-go
decision. The page displayed OPEN, 0 comments, 0 claimed proofs,
Interested in collaborating: None, and `Currently working on this
problem: None. It also displayed Likes this problem: Dogmachine, This
problem looks difficult: Dogmachine, This problem looks tractable: None`,
The results ... could be formalisable: None, and `I am working on
formalising ...: None. “Formalised statement?” was No`. The page was last
edited 08 April 2026. Thus none of the mandatory stop conditions fired.
Verbatim live statement
> Are there two infinite sets $A$ and $B$ such that $A+B$ agrees with the set of prime numbers up to finitely many exceptions?
(a) Here and below
\[ A+B=\{a+b:a\in A,\ b\in B\}, \]and “agrees up to finitely many exceptions” means that the symmetric
difference is finite. The cited papers formulate the summands as sets of
positive integers.
Everything else asserted on the live page
(b, page-cited ground truth) The page calls this Ostmann's *inverse
Goldbach problem* and records the expected answer as no.
(b, independently checked in the cited primary paper) Elsholtz and
Harper, [*Additive decompositions of sets with restricted prime
factors*](https://arxiv.org/abs/1309.0593), Theorem 2.6, prove that a
hypothetical decomposition satisfies, for all sufficiently large \(x\),
\[ \frac{x^{1/2}}{\log x\log\log x}\ll A(x)\ll x^{1/2}\log\log x, \qquad A(x)=|A\cap[1,x]|, \]and the same estimates hold for \(B(x)\).
(b, independently checked in the cited primary paper) Elsholtz,
[*The inverse Goldbach
problem*](https://www.math.tugraz.at/~elsholtz/WWW/papers/papers04inversegoldbachtexbased.pdf),
Mathematika 48 (2001), 151--158,
DOI 10.1112/S0025579300014406,
proves that no three sets \(A,B,C\), each of cardinality at least two, can
have \(A+B+C\) agree with the primes outside a finite set.
(b, independently checked against the primary abstract) Granville,
[*A note on sums of
primes*](https://doi.org/10.4153/CMB-1990-073-7), Canadian Mathematical
Bulletin 33 (1990), 452--454, proves under the prime \(k\)-tuples
conjecture that there is an infinite sequence whose pairwise averages are
prime. In the notation used by the live page, there are infinite \(B,C\)
such that
\[ \left\{\frac{b+c}{2}:b\in B,\ c\in C\right\}\subseteq\mathcal P. \](b, independently checked in the primary paper) Tao and Ziegler,
[*Infinite partial sumsets in the
primes*](https://arxiv.org/abs/2301.10303), Journal d'Analyse
Mathématique 151 (2023), 375--389, prove unconditionally that there are
infinite increasing sets \(B=\{b_1<\cdots\}\), \(C=\{c_1<\cdots\}\) for
which \(b_i+c_j\) is prime whenever \(i sumset, not the complete Cartesian sumset required here. (d) The live page additionally points to problems 429 and 432 and has no comments to transcribe. (d) I searched the exact problem wording and “Ostmann inverse Goldbach,” followed the live references, and searched recent primary sources for the associated inverse-large-sieve problem. I downloaded and read the relevant theorem/proof sections of arXiv:1309.0593 and arXiv:1311.6176, and the new paper below. This found no claimed resolution. That is a bounded search result, not a proof that no other relevant paper exists. (b) Green and Harper, [*Inverse questions for the large sieve*](https://arxiv.org/abs/1311.6176), Geometric and Functional Analysis 24 (2014), 1167--1203, isolate the principal missing statement as their Conjecture 1.5. In a simplified description, the local restrictions should force either a power saving below the square-root large-sieve scale or almost complete containment of both sets in rational quadratic images. Their Theorem 1.8 proves that this conjecture would settle Ostmann's problem: if \(A+B\) contains all sufficiently large primes, then it must also contain infinitely many composites. (b) The newest directly relevant primary source I found is Ernie Croot and Chi Hoi Yip, [*A weighted entropy approach for the quadratic inverse large sieve conjecture*](https://arxiv.org/abs/2607.15311), arXiv:2607.15311v1, submitted 15 July 2026. It is explicitly marked “preliminary version.” Its Corollary 1.10 says that if \(\mathcal P\sim A+B\), then for some \(c>0\) and all sufficiently large \(N\), there are integral quadratics such that and their product is at least The quadratics may depend on \(N\). (a/b) Croot--Yip does not close problem 431. Their conclusion is a large intersection with a quadratic image, whereas Green--Harper's conditional route needs near-containment (up to a power-saving exceptional set). A growing intersection alone does not force the whole cross-sum to contain a composite. (b) Hanson, [*Additive correlation and the inverse problem for the large sieve*](https://doi.org/10.1017/S0305004118000518), Mathematical Proceedings of the Cambridge Philosophical Society 168 (2020), 211--217, is the earlier unconditional input improved by Croot--Yip: at the square-root scale it forces additive correlation with the squares and, as Croot--Yip record, a logarithmic-size intersection with one quadratic image. (b) Ruzsa, [*Additive decomposition of signed primes*](https://arxiv.org/abs/2204.14013), Acta Arithmetica 209 (2023), 129--134, gives a useful boundary check, not a solution: conditional on the prime-tuple hypothesis, two infinite subsets of \(\mathbb Z\) have sumset exactly the positive and negative primes of absolute value greater than three. Allowing negative summands and signed primes removes the one-sided problem at issue here. Let \([N]=\{1,\ldots,N\}\), and define (a) Tail normalization. If \(\mathcal P\sim A+B\), there is a \(T\) such that every member of \(A+B\) at least \(T\) is prime and every prime at least \(T\) belongs to \(A+B\). Deleting the finitely many elements of each summand below \(T\) therefore leaves two infinite tails whose complete cross-sum consists of primes. (a) Qualitative reduction. A hypothetical solution makes \(\beta(N)\) unbounded: for each \(k\), choose \(k\) elements from each tail and take \(N\) to be their maximum. (b) Quantitative reduction. Applying Elsholtz--Harper's Theorem 2.6 after deleting the fixed initial pieces gives for every sufficiently large \(N\), if a hypothetical decomposition exists. (b) Mere unboundedness is no obstruction. The Green--Tao theorem, [*The primes contain arbitrarily long arithmetic progressions*](https://doi.org/10.4007/annals.2008.167.481), supplies prime progressions Choose any \(1\le c unconditionally, but Green--Tao supplies no bound remotely comparable to (2.2). (a) Local inverse-sieve condition. Suppose \(A,B\subseteq(Y,N]\), every \(a+b\) is prime, and \(p\le Y\) is prime. If an occupied residue of \(A\bmod p\) were the negative of an occupied residue of \(B\bmod p\), some \(a+b>2Y\ge2p\) would be divisible by \(p\), hence composite. Therefore This is the elementary source of the paired inverse-large-sieve problem. (b) A positive answer to Green's Problem 58 in his [*100 Open Problems*](https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf) would suffice: if every \(A,B\subseteq[N]\) of sizes at least \(N^{0.49}\) had a composite in \(A+B\), then \(\beta(N) (2.2). (d) Exact finite theorem. Exhaustive computation gives (d) Equivalently, the least \(N\) admitting a \(k\)-by-\(k\) all-prime-sum rectangle is as follows. Each row contains an explicit witness; the standalone checker proves nonexistence at the preceding integer. | \(k\) | least \(N\) | odd side \(A\) | even side \(B\) | |---:|---:|---|---| | 2 | 4 | \(1,3\) | \(2,4\) | | 3 | 10 | \(1,3,9\) | \(2,4,10\) | | 4 | 31 | \(1,7,25,31\) | \(6,12,16,22\) | | 5 | 45 | \(3,9,15,29,45\) | \(2,8,14,38,44\) | | 6 | 85 | \(1,7,25,55,67,85\) | \(4,12,16,46,72,82\) | | 7 | 151 | \(1,7,25,67,85,91,151\) | \(12,16,22,46,72,82,106\) | | 8 | 253 | \(1,3,31,43,45,121,135,253\) | \(16,28,58,106,136,148,196,238\) | | 9 | 420 | \(11,59,89,179,221,319,341,409,419\) | \(12,48,90,138,168,222,300,342,420\) | | 10 | \(>500\) | none through 500 | none through 500 | (a) Parity lemma. If \(A,B\) are sets of positive integers with at least two elements each and every member of \(A+B\) is prime, then one set is entirely odd and the other entirely even. Proof. If \(A\) contained an even \(e\) and an odd \(o\), no even \(b\) could belong to \(B\), because \(e+b\ge4\) would be even. Hence all \(b\in B\) would be odd. Then every \(o+b\) would be an even prime, forcing \(o=b=1\); this would force \(B=\{1\}\), a contradiction. Thus each set has constant parity. Equal parities are impossible: even plus even is at least four, while odd plus odd can be the prime two only when both terms are one. The two constant parities are therefore opposite. \(\square\) (a) By swapping the two sides, it is enough to select \(k\) odd vertices. For each odd \(a\le N\), the checker stores as one Python integer the bitset A \(k\)-rectangle exists exactly when some \(k\) odd vertices have at least \(k\) common neighbours. (a) The recursive search visits all \(k\)-subsets in a fixed order. It prunes only if fewer than the required number of odd vertices remain, or if the current common-neighbour set has size below \(k\). Both are necessary conditions for completion, so a returned nonexistence. Monotonicity of \(\beta(N)\), together with a witness at each listed transition and nonexistence at the preceding \(N\), proves every interval in (3.1). The additional exhaustive failure for \(k=10,N=500\) proves the final interval. (d) The complete, standard-library verifier is It performs four independent safeguards: 1. it sieves \(0,\ldots,1000\) and compares every entry with trial division; 2. it compares the optimized bitset search with literal subset enumeration for every relevant case \(N\le14\); 3. it checks every displayed witness and every one of its cross-sums by trial division, not by trusting the sieve; 4. it reruns the exhaustive nonexistence search at \((N,k)=(3,2),(9,3),(30,4),(44,5),(84,6),(150,7),(252,8),(419,9)\) and \((500,10)\). Run it with: (d) On this VM it finished in 40.09 wall seconds (40.08 user seconds, 11.2 MiB peak RSS). The nonexistence searches used, respectively, recursive nodes and ended with The core exhaustive routine is: (d) The table is a sharp result for the concrete finite regime \(N\le500\). It is not evidence that \(\beta(N)\) is bounded; Section 2 shows rigorously that it is unbounded. (a) No finite table can control the “finitely many exceptions” in problem 431, because their largest value is not bounded in the statement. Consequently (3.1) rules out no hypothetical decomposition by itself. (b) Exact missing analytic lemma. In view of Elsholtz--Harper, it would be enough to prove the uniform estimate The stronger bound \(\beta(N) is Green's Problem 58. Existing large-sieve machinery gives the square-root scale but no fixed power saving in this balanced, unstructured case; that is precisely the inverse-large-sieve barrier isolated by Green--Harper. (b) The July 2026 Croot--Yip theorem is genuine structural progress toward that barrier, but it forces only subpolynomial-size quadratic intersections. The missing upgrade is either: which the Green--Harper composite-producing argument applies. (c) Extending the exact table is computationally possible but does not approach (4.1). The current proof visits 6.1 million nodes for \((N,k)=(500,10)\); the raw unpruned search already has \(\binom{250}{10}=219005316087032475\) candidates. An exact \(N=1000\) extension with a purpose-built SAT/branch-and-bound implementation is roughly a 1--100 core-hour project, with high uncertainty from instance-dependent pruning. No finite extension, regardless of size, supplies the uniformity required in (4.1). PARTIAL: The problem remains open; verified current progress is Croot--Yip's July-2026 quadratic-intersection theorem, and this report adds an exhaustive sharp computation of the balanced all-prime-sum parameter beta(N) for every N<=500, with the exact unresolved uniform bound isolated in (4.1).1. Primary-source literature audit through 2026-07-26
2. Exact reduction to balanced all-prime-sum rectangles
3. New exact computation: all values of \(\beta(N)\) through 500
Why the finite proof is exhaustive
None is a proof ofruns/erdos431_wave5w_verify.py (SHA-256aaf302443bc02d5f668ab790676a06a7b324438cbb2087f1cacd842685a9e27f).python runs/erdos431_wave5w_verify.py
ALL CHECKS PASSED.def visit(position, need, common, chosen):
nonlocal nodes, selected, final_common
nodes += 1
if common.bit_count() < k or len(order) - position < need:
return False
if need == 0:
selected, final_common = chosen, common
return True
last_start = len(order) - need
for next_position in range(position, last_start + 1):
vertex = order[next_position]
new_common = common & neighbours[vertex]
if new_common.bit_count() < k:
continue
if visit(next_position + 1, need - 1, new_common,
chosen + (vertex,)):
return True
return False
4. What this does and does not prove