Erdoes #431 - working report - Erdős Problem a Day

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 and its live LaTeX view 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, 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, 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, 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, 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<j$. This is a triangular partial 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.

1. Primary-source literature audit through 2026-07-26

(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, 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

|A\bmod p|+|B\bmod p|\le p+1

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, 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

q_A(x)=m_A\pm x^2,\qquad q_B(x)=m_B\pm x^2

such that

|A\cap[N]\cap q_A(\mathbb Z)|,\, |B\cap[N]\cap q_B(\mathbb Z)| \ge \exp\!\left( c\frac{\sqrt{\log N}}{(\log\log N)^{3/2}} \right)

and their product is at least

\exp\!\left(c\frac{\sqrt{\log N}}{\log\log N}\right).

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, 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, 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.

2. Exact reduction to balanced all-prime-sum rectangles

Let $[N]=\{1,\ldots,N\}$, and define

\beta(N)=\max\left\{k: \begin{array}{l} \text{there are }A,B\subseteq[N],\ |A|=|B|=k,\\ a+b\text{ is prime for every }(a,b)\in A\times B \end{array}\right\}. \tag{2.1}

(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

\boxed{\quad \beta(N)\gg \frac{\sqrt N}{\log N\log\log N} \quad} \tag{2.2}

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, supplies prime progressions

p,p+d,\ldots,p+(2k-2)d.

Choose any $1\le c<p$, set

A=\{c+id:0\le i<k\},\qquad B=\{p-c+jd:0\le j<k\};

then every cross-sum is one of those primes. Thus $\beta(N)\to\infty$ 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

(A\bmod p)\cap-(B\bmod p)=\varnothing,\qquad |A\bmod p|+|B\bmod p|\le p. \tag{2.3}

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 would suffice: if every $A,B\subseteq[N]$ of sizes at least $N^{0.49}$ had a composite in $A+B$, then $\beta(N)<N^{0.49}=o(\sqrt N/(\log N\log\log N))$, contradicting (2.2).

3. New exact computation: all values of $\beta(N)$ through 500

(d) Exact finite theorem. Exhaustive computation gives

\begin{array}{c|c} \text{range of }N&\beta(N)\\ \hline 1\le N\le3&1\\ 4\le N\le9&2\\ 10\le N\le30&3\\ 31\le N\le44&4\\ 45\le N\le84&5\\ 85\le N\le150&6\\ 151\le N\le252&7\\ 253\le N\le419&8\\ 420\le N\le500&9 \end{array} \tag{3.1}

(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

Why the finite proof is exhaustive

(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

\Gamma(a)=\{b\le N:b\text{ even and }a+b\text{ prime}\}.

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 None is a proof of 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 runs/erdos431_wave5w_verify.py (SHA-256 aaf302443bc02d5f668ab790676a06a7b324438cbb2087f1cacd842685a9e27f). It performs four independent safeguards:

it sieves $0,\ldots,1000$ and compares every entry with trial

division;

it compares the optimized bitset search with literal subset

enumeration for every relevant case $N\le14$;

it checks every displayed witness and every one of its cross-sums by

trial division, not by trusting the sieve;

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:

python runs/erdos431_wave5w_verify.py

(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,

1,\ 3,\ 55,\ 181,\ 1962,\ 25541,\ 288942,\ 3876064,\ 6101854

recursive nodes and ended with ALL CHECKS PASSED.

The core exhaustive routine is:

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

(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

\boxed{\quad \beta(N)=o\!\left(\frac{\sqrt N}{\log N\log\log N}\right). \quad} \tag{4.1}

The stronger bound $\beta(N)<N^{0.49}$ for all sufficiently large $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:

a power saving for a pair without near-quadratic structure; or
near-containment of both summands in controlled quadratic images, after

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).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger

\(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