Erdős problem 428: live audit, a witness-gap theorem, and exact finite data

Access/search date: 2026-07-26 UTC.

The labels used throughout are exactly those requested:

• (a) elementary-rigorous: proved here without an external theorem;
• (b) rigorous-modulo-named-theorem: the deduction is rigorous, with the

named input stated explicitly;

• (c) plausible/structural-unverified: heuristic, conjectural, or a

literature-search miss rather than a theorem;

• (d) computational-only: a browser/source observation or an exhaustive

finite computation.

0. Mandatory live-page audit

(d) I fetched the live Erdős Problems page #428 through the Bright Data browser on 2026-07-26; I did not rely on the supplied YAML. The page displayed OPEN. It displayed 3 comments, 0 claimed proofs, `Interested in collaborating: None, and Currently working on this problem: None`. The other displayed markers were also all None: likes, “looks difficult,” “looks tractable,” “results ... could be formalisable,” and “I am working on formalising ...”. “Formalised statement?” was Yes. Thus none of the mandatory stop conditions fired.

Verbatim live statement

Is there a set $A\subseteq \mathbb{N}$ such that, for infinitely many $n$, all of $n-a$ are prime for all $a\in A$ with $0<a<n$ and\[\liminf\frac{\lvert A\cap [1,x]\rvert}{\pi(x)}>0?\]

(b, page-cited ground truth) The one known result printed below the statement is: Erdős and Graham could prove the assertion, assuming the prime $k$-tuple conjecture, when lim inf is replaced by lim sup. The citation is [ErGr80]: Paul Erdős and Ronald L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de L'Enseignement Mathématique 28 (1980); see the bibliographic record. The available book preview did not expose the relevant page, so the attribution—not a rechecked proof—is being taken from the live page as the task directs.

Every live comment

The site itself warns that comments are not verified. I therefore record them as (c) unless independently upgraded below.

1. (c) Will Sawin, 01:28 on 03 Jul 2026: the conjectural prime number

theorem \[ \pi(x+y)-\pi(x)=(1+o(1))y/\log x \] in every fixed power-size interval $x^\delta\leq y<x$ would give a negative answer. If the lower relative density is $\epsilon>0$, take $\delta<\epsilon$, put $x=\lceil n^\delta\rceil$ at a witness $n$, and compare $A(x)$ with the primes in $(n-x,n)$. Sawin explicitly says that proving this short-interval input is far out of reach.

1. (c) on the page; (b) after the independent check below. Steve Fan,

03:49 on 03 Jul 2026, corrects the final coefficient in that argument and observes that the Guth--Maynard exponent $\delta>17/30$ yields the unconditional necessary condition \[ \liminf_{x\to\infty}\frac{|A\cap[1,x]|}{\pi(x)}\leq \frac{17}{30}. \]

1. (c) Steve Fan, 19:12 on 02 Jul 2026: (i) Dickson's conjecture

suffices for a construction with limsup at least $1$; (ii) if a finite set $\mathcal H$ has all $|n-h|$ prime and larger than $|\mathcal H|$, then $\mathcal H$ is admissible; (iii) an induction adds reversed primes between the old witness and half the new witness; (iv) a uniform upper-bound sieve gives limsup at most $2$ for every possible $A$; and (v) the second Hardy--Littlewood conjecture $\pi(x+y)\leq\pi(x)+\pi(y)$ would improve that upper bound to $1$.

1. Primary-source audit and current unconditional inputs

(d) I searched the exact problem wording, the [ErGr80] attribution, forward references, and combinations of “liminf,” “prime tuple,” and the reversed-prime condition. I found no primary paper that explicitly claims to settle the live liminf question. This is a bounded search result, not a proof that no such paper exists.

(b) Guth and Maynard, New large value estimates for Dirichlet polynomials, Annals of Mathematics 203 (2026), 623--675, Corollary 1.3, prove uniformly for

that

This verifies the theorem and exponent used in Fan's newer comment.

(b) Here is the deduction of Fan's bound. Let

At a witness $n$, for $y=n^\delta$ the injection $a\mapsto n-a$ gives

For fixed $17/30<\delta<0.99$, Guth--Maynard makes the right side $(1+o(1))y/\log n$. For every fixed finite $\lambda<L$, the prime number theorem and the definition of the liminf make the left side at least

Hence $\lambda\leq\delta$ for every $\lambda<L$, so $L\leq\delta$; letting $\delta\downarrow17/30$ gives $L\leq17/30$. If the same asymptotic were known for every fixed $\delta>0$, this argument would instead give $L=0$, exactly explaining the negative heuristic in the first comment.

(b) The uniform two-form sieve needed below is stated explicitly in Jacob Korevaar, Prime pairs and Zeta's zeros, arXiv:0806.0934, equations (1.3) and (1.5). If

then, for every $\varepsilon>0$, there is an $x_0(\varepsilon)$ independent of $r$ such that

Korevaar attributes this uniform Selberg-sieve estimate to Halberstam and Richert, Sieve Methods (1974).

(b) Tao and Ziegler, Infinite partial sumsets in the primes, arXiv:2301.10303, Theorem 1.5, prove unconditionally that there is an increasing infinite sequence whose every finite prefix is prime-producing. Their Proposition 5.1 is stronger in a different direction: from any specified infinite admissible set it extracts an infinite subset lying in the orbit closure of the primes; the proof states that every finite prefix has infinitely many simultaneous prime translations. It supplies neither relative-prime density nor a bound on the least translation.

(b) Hensley and Richards, Primes in intervals, Acta Arithmetica 25 (1974), 375--391, define $\rho^(x)$ as the maximum size of a finite admissible tuple in an interval of length $x$ and prove $\rho^(x)-\pi(x)\to\infty$. This shows why large finite admissible blocks do not by themselves address the required single nested infinite set.

2. An exact reformulation and an admissibility obstruction

Let $A=\{a_1<a_2<\cdots\}$ and put $a_0=0$.

(a) Exact synchronized-chain reformulation. The problem has a positive answer if and only if there is such a sequence with

and infinitely many pairs $(k,n_k)$ for which

Indeed, for a witness $n$, choose $k$ so that $a_k<n\leq a_{k+1}$; the elements of $A$ below $n$ are exactly the first $k$. Conversely, (2.1) says exactly that all members of $A$ below $n_k$ give prime differences. This makes the missing synchronization visible: “every finite prefix has some arbitrarily large prime translation” is not enough—the translation must land before the next, as-yet-uncontrolled element.

(a) Every candidate is globally admissible. For every prime $q$, the residue set $A\bmod q$ must omit a class. Otherwise choose $b_0,\ldots,b_{q-1}\in A$, one in each residue class. At any witness $n>\max b_i+q$, the integer $n-b_{n\bmod q}$ is a multiple of $q$ larger than $q$, hence composite, a contradiction. More precisely, for all sufficiently large witnesses $n$, the residue $n\bmod q$ belongs to the complement of $A\bmod q$. In particular, if $A$ omits exactly one class modulo $q$, all sufficiently large witnesses occupy that one class.

(a/b) What Tao--Ziegler does and does not give. Proposition 5.1 handles the admissibility/prime-producing-prefix part, modulo its cited theorem, but (2.1) identifies two remaining requirements: preserve $A(x)\gg x/\log x$ at every large scale, and place infinitely many prefix translations inside the specific gaps $(a_k,a_{k+1}]$. Neither conclusion follows from qualitative prime production, even under Dickson's conjecture, because its least simultaneous-prime translate has no uniform bound as the tuple grows.

3. New result in this report: witnesses must have enormous gaps

(b) Proposition. Suppose $A$ satisfies the requested positive lower relative density, and let

There are constants $c_A>0$ and $M_A$ such that every pair $m<n$ in $\mathcal W(A)$ with $m\geq M_A$ satisfies

Consequently all sufficiently large witnesses have the same parity, and

The proposition is unconditional, modulo the named uniform Selberg-sieve bound above, the prime number theorem, and the standard Mertens estimate $n/\varphi(n)\ll\log\log(3n)$.

Proof. Choose a finite $\lambda$ with $0<\lambda<\liminf A(x)/\pi(x)$, take two witnesses $m<n$, and set $d=n-m$. For each $a\in A$ with $a\leq\lfloor m/2\rfloor$, put $p=m-a$. Then

The map $a\mapsto p$ is injective, so

(a) For large $m$, the left side is nonzero and all these $p$ exceed $2$. Thus $d$ cannot be odd: two integers differing by an odd number have opposite parity, so one would be an even prime larger than $2$. Write $d=2r$.

(b) Fixing $\varepsilon=1$ in the uniform sieve estimate and using

where the convergent product of the second factors is absorbed into the constant, (3.3) gives an absolute $K$ with

For all sufficiently large $m$, the choice of $\lambda$ and the prime number theorem give

Combining (3.4) and (3.5),

Thus $3r\geq\exp(m^{\lambda/(8K)})$. Absorbing the harmless factor $2/3$ and slightly decreasing the exponent proves (3.1).

(a) Apply (3.1) to consecutive large witnesses $w_j<w_{j+1}$. After replacing $c_A$ by a smaller positive constant, $w_{j+1}\geq\exp(w_j^{c_A})$. On setting $u_j=(c_A/2)\log w_j$, the recurrence implies $u_{j+1}\geq\exp(u_j)$ once $u_j$ is large. Iterating logarithms proves (3.2). This completes the proof.

The point of (3.1) is not merely that witnesses have unbounded gaps: any hypothetical positive-density construction must cross deserts longer than every fixed power of the preceding witness while keeping $A$ prime-dense at every intermediate scale.

4. Exact two-witness computation

For a concrete finite obstruction, define

(a) If $m,n$ are two witnesses in $[H,2H]$, then $A(\lfloor m/2\rfloor)/\pi(\lfloor m/2\rfloor)\leq R(H)$.

(d) Exhaustive enumeration gives the following exact values. The pair shown is the lexicographically first maximizer. The last column is the prime-pair singular multiplier

The standalone verifier is erdos428_wave5v_verify.py. It uses only the Python standard library and can be run with

python runs/erdos428_wave5v_verify.py

(d) Verification performed here:

• Eratosthenes primality for every integer through $20000$ was independently

compared with deterministic trial division.

• The sliding-window enumeration was compared to a literal transcription of

(4.1) for $H=10,20,35$.

• Every displayed maximum was recomputed; every winning $a$ was checked by

trial division; exact rational comparisons, row assertions, and singular multipliers were checked.

• Two clean runs ended in PASS; the second used 20.75 wall seconds,

20.72 CPU seconds, and 12,816 KiB maximum RSS.

• SHA-256:

97226229c7fb54f1861638f43dd5d009e2ab40e231662e9927c0bd081c468300.

The algorithm is $O(H^2)$ time and $O(H)$ memory. Extrapolating the measured rate, extending the same exact calculation to $H=10^6$ would cost roughly 55--60 core-hours on this VM (about \$3--\$6 at \$0.05--\$0.10 per core-hour), and $H=10^7$ roughly 230--240 core-days. Such finite extension cannot supply the missing uniform-in-$H$ argument, so it was not run.

5. Exact remaining wall

(a) The synchronized-chain equivalence (2.1) states the positive direction's missing lemma exactly:

Construct an increasing admissible sequence $a_1<a_2<\cdots$ with $A(x)\gg x/\log x$ for every sufficiently large $x$, together with infinitely many indices $k$ for which the growing $k$-tuple has a simultaneous prime translate in the prescribed one-gap window $(a_k,a_{k+1}]$.

(b/c) Tao--Ziegler gives qualitative simultaneous translations for all finite prefixes but loses density and gives no least-translate/window control. Dickson's conjecture still gives no uniform bound capable of putting the translate into $(a_k,a_{k+1}]$ when $k\asymp a_k/\log a_k$. The Hensley--Richards theorem supplies dense finite admissible blocks but no nested infinite sequence with the synchronization property. Bridging these three properties is the precise positive-side wall.

(b/c) On the negative side, the short-interval comparison proves only $L\leq17/30$ with present unconditional technology. A prime number theorem in every fixed power-size interval would force $L=0$, but that is the exact missing analytic input. The pair sieve cannot do this: its singular factor can be made large by giving the witness difference many small prime divisors, and the rigorous consequence is the super-polynomial separation (3.1), not a contradiction.

No construction or counterexample is therefore claimed, and the live problem remains open.

PARTIAL: Any hypothetical witness sequence is rigorously forced by a uniform Selberg prime-pair bound to have gaps at least $\exp(m^{c_A})$, an exact synchronized-chain reduction and two-witness maxima through $H=10000$ are verified, but existence remains open.