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](https://www.erdosproblems.com/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](https://books.google.com/books/about/Old_and_New_Problems_and_Results_in_Comb.html?id=E-sZAQAAIAAJ).
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.
2. (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}. \]
3. (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](https://annals.math.princeton.edu/2026/203-2/p06), Corollary 1.3,
prove uniformly for
\[ y\in[x^{17/30+\varepsilon},x^{0.99}] \]that
\[ \pi(x+y)-\pi(x) =\frac{y}{\log x} O_\varepsilon\!\left(y\exp(-(\log x)^{1/4})\right). \]This verifies the theorem and exponent used in Fan's newer comment.
(b) Here is the deduction of Fan's bound. Let
\[ L=\liminf_{x\to\infty} A(x)/\pi(x),\qquad A(x):=|A\cap[1,x]|. \]At a witness $n$, for $y=n^\delta$ the injection
$a\mapsto n-a$ gives
\[ A(y)\leq \pi(n)-\pi(n-y). \]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
\[ (\lambda-o(1))\pi(y)=(\lambda/\delta-o(1))y/\log n. \]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
\[ \pi_{2r}(x)=|\{p\leq x:p,\ p+2r\text{ are prime}\}|, \]then, for every $\varepsilon>0$, there is an $x_0(\varepsilon)$
independent of $r$ such that
\[ \pi_{2r}(x)\leq(8+\varepsilon)C_{2r}\frac{x}{\log^2x} \quad(x\geq x_0), \qquad C_{2r}=C_2\prod_{\substack{p\mid r\\p>2}}\frac{p-1}{p-2}. \]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](https://www.impan.pl/en/publishing-house/journals-and-series/acta-arithmetica/all/25/4/100146/primes-in-intervals),
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
\[ \liminf_{x\to\infty}A(x)/\pi(x)>0 \]and infinitely many pairs $(k,n_k)$ for which
\[ a_k$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
\[ \mathcal W(A)=\{n:\ n-a\text{ is prime for every }a\in A,\ 0$m<n$ in $\mathcal W(A)$ with $m\geq M_A$ satisfies
\[ \boxed{\ n-m\geq \exp(m^{c_A})\ }. \tag{3.1} \]Consequently all sufficiently large witnesses have the same parity, and
\[ |\mathcal W(A)\cap[1,X]|\leq \log^*X+O_A(1). \tag{3.2} \]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
\[ p,\ p+d=n-a\ \text{are prime},\qquad \lceil m/2\rceil\leq p(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
\[ \begin{aligned} \prod_{\substack{p\mid r\\p>2}}\frac{p-1}{p-2} &= \prod_{\substack{p\mid r\\p>2}} \left[ \frac{p}{p-1} \left(1+\frac{1}{p(p-2)}\right) \right]\\ &\ll \frac r{\varphi(r)} \ll\log\log(3r), \end{aligned} \]where the convergent product of the second factors is absorbed into the
constant, (3.3) gives an absolute $K$ with
\[ A(\lfloor m/2\rfloor) \leq K\,\log\log(3r)\frac m{\log^2m}. \tag{3.4} \]For all sufficiently large $m$, the choice of $\lambda$ and the prime number
theorem give
\[ A(\lfloor m/2\rfloor) \geq \lambda\,\pi(\lfloor m/2\rfloor) \geq \frac{\lambda}{8}\frac m{\log m}. \tag{3.5} \]Combining (3.4) and (3.5),
\[ \log\log(3r)\geq \frac{\lambda}{8K}\log m. \]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
\[ R(H)= \max_{H\leq m$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
\[ C_d/C_2=\prod_{\substack{p\mid(d/2)\\p>2}}\frac{p-1}{p-2}. \]| $H$ | $m$ | $n$ | $d=n-m$ | common $a$ | $\pi(\lfloor m/2\rfloor)$ | $R(H)$ | $C_d/C_2$ |
|---:|---:|---:|---:|---:|---:|---:|---:|
| 100 | 110 | 140 | 30 | 10 | 16 | $10/16=0.625000000$ | $8/3$ |
| 250 | 252 | 282 | 30 | 16 | 30 | $16/30=0.533333333$ | $8/3$ |
| 500 | 620 | 830 | 210 | 33 | 63 | $33/63=0.523809524$ | $16/5$ |
| 1000 | 1118 | 1328 | 210 | 54 | 102 | $54/102=0.529411765$ | $16/5$ |
| 2000 | 2018 | 2438 | 420 | 80 | 169 | $80/169=0.473372781$ | $16/5$ |
| 5000 | 5282 | 7592 | 2310 | 178 | 382 | $178/382=0.465968586$ | $32/9$ |
| 10000 | 10332 | 12642 | 2310 | 301 | 687 | $301/687=0.438136827$ | $32/9$ |
The standalone verifier is
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.