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

Erdős problem #855 — wave 6o

Date of audit and computation: 2026-07-27 UTC.

Outcome

This is not a solution. I obtained two independently checkable finite artifacts:

an explicit 447-element admissible set in the 3159 integer positions

$\{1,\ldots,3159\}$, whereas $\pi(3159)=446$, together with a complete residue-class check and an explicit CRT progression with no local obstruction; and

exact maxima of $\pi(x+y)-\pi(x)$ for six fixed $y$'s and every integer

$y\leq x\leq 10^8$.

The first artifact gives a completely elementary implication from the prime-$k$-tuples conjecture to a fixed-width violation, but that conjecture is unproved and the live problem asks about large $x$ and large $y$. The second artifact is finite and therefore cannot decide an eventual assertion.

Claim labels used below:

(a) elementary-rigorous — a proof is included and has no unproved input;
(b) rigorous-modulo-named-theorem — the exact named theorem is identified;
(c) plausible/structural-unverified — includes implications whose

antecedent is an unproved conjecture;

(d) computational-only — a finite exhaustive result reproduced by the

standalone checker.

Step 0: live-page gate

I fetched the protected page and its forum thread through the Bright Data browser route, not datacenter curl.

Live page: <https://www.erdosproblems.com/855>
Discussion containing all five comments:

<https://www.erdosproblems.com/forum/thread/855>

Accessed: 2026-07-27.
The page says it was last edited 2026-04-08.

Verbatim live statement

If $\pi(x)$ counts the number of primes in $[1,x]$ then is it true that (for large $x$ and $y$)\[\pi(x+y) \leq \pi(x)+\pi(y)?\]

Stop-condition audit

Status: OPEN.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: ColoursX.
Other markers: Dogmachine and Basile_Beyer_de_Ryke marked it difficult;

nobody marked it tractable.

External-data fields: “Formalised statement? Yes” and related OEIS sequence

A023193. The displayed tags are “number theory” and “primes”; as instructed, I did not treat those tags as part of the statement.

Thus the requested stop condition did not fire. An “interested” marker is present, but no current worker or proof claim is present.

Everything material listed on the live page

The following is a faithful synopsis of the page, not a new proof:

It calls this the second Hardy–Littlewood conjecture and says Erdős regarded

it as an old conjecture probably already stated by Hardy and Littlewood.

Hensley–Richards are cited for the following conditional result: assuming the

Hardy–Littlewood prime-tuples conjecture, for every large $y$ there are infinitely many $x$ with \[ \pi(x+y)>\pi(x)+\pi(y)+(\log 2-o(1)) \frac{y}{(\log y)^2}. \]

Straus's proposed replacement

\[ \pi(x+y)\leq\pi(x)+2\pi(y/2) \] is also incompatible with the prime-tuples conjecture, by Clark–Jarvis.

Erdős conjectured the weaker upper bound

\[ \pi(x+y)\leq\pi(x)+\pi(y)+O\!\left(\frac{y}{(\log y)^2}\right); \] the page says Hensley–Richards make its order conditionally best possible, while Richards conjectured even this weaker statement is false.

Erdős–Richards conjectured density $1$ for the $x$'s for which the

original inequality holds for every $y<x$, and proved positive lower density.

They also conjectured that for every $x$ the inequality holds when

$y\gg(\log x)^C$, for some large constant $C$.

Erdős separately conjectured

\[ \pi(x+y)\leq\pi(x)+O(y/\log x) \quad\text{for }x\geq y\gg(\log x)^C. \]

The page attributes

$\pi(x+y)\leq\pi(x)+O(\pi(y))$ to Hardy–Littlewood and lists the Montgomery–Vaughan bound \[ \pi(x+y)\leq\pi(x)+\frac{2y}{\log y} \] as the best result in that direction.

The five comments contain no proof or work claim. In substance:

Dogmachine noted that one finite counterexample would not settle wording

quantified over large $x,y$, and suggested OPEN rather than falsifiable.

Adenwalla corrected the Hensley–Richards display to include a positive

$c\,y/\log^2y$ surplus; the page records that it was updated.

old-bielefelder raised the apparent obstruction $x=y$.
Thomas Bloom explained that the conditional claim concerns infinitely many

$x$ for each given $y$, so $x=y$ is not imposed.

Dogmachine remarked that enormous computation might in principle produce

explicit counterexamples, but finite examples would not settle the live eventual statement.

Primary-source literature audit

I searched exact-title and exact-inequality queries in arXiv, AMS, journal pages, and the references exposed by the live page. The technically relevant primary sources I could verify are:

**Hensley–Richards, “Primes in intervals,” Acta Arith. 25 (1974),

375–391, DOI 10.4064/aa-25-4-375-391. The scanned paper really defines the maximal admissible-set function $\rho^*(y)$, proves \[ \rho^*(y)-\pi(y)>(\log 2-\varepsilon)y/\log^2y \] for all sufficiently large $y$, and derives the incompatibility with prime $k$-tuples. (b)**

**Montgomery–Vaughan, “The large sieve,” Mathematika 20 (1973),

119–134, DOI 10.1112/S0025579300004708. This is the actual paper named for the large-sieve upper bound. (b)**

**Gordon–Rodemich, “Dense Admissible Sets,” ANTS III (1998),

216–225, author PDF. It reports exhaustive computation of $\rho^*(u)$ through $u=1663$ and, using subadditivity of $\rho^*$, obtains $\rho^*(u)\leq\pi(u)$ through $u=1731$. (b/d, external computation; not rerun here)**

**Christian Axler, “Some Results on a Conjecture of Hardy and

Littlewood,” arXiv:1909.12625, official arXiv page. Among other ranges, Theorem 1.3 proves the inequality for $m\geq n\geq0.7088167809\,m/\log^2m$. Proposition 2.4 reports a computer verification for $m+n\leq39\,708\,229\,123=p_{1.7\cdot10^9}$. I verified that the PDF contains this exact claim; I did not recompute $1.7$ billion primes, so the proposition is recorded only as an external computational claim. (b) for the proved ranges; (d) for Proposition 2.4**

**B. Chahal, E. Elma, N. Fellini, A. Vatwani, D. N. T. Vo,

“On the Second Hardy–Littlewood Conjecture,” arXiv:2503.02766, official paper. Their Theorem 1.1 says that if \[ |\pi(t)-\operatorname{li}(t)|\leq C R(t) \] with their stated monotonicity hypotheses, then, for sufficiently large $x$, \[ \frac{3C R(2x)\log^2x}{\log\log x}\leq y\leq x \quad\Longrightarrow\quad \pi(x+y)\leq\pi(x)+\pi(y). \] Assuming RH, their Corollary 1.2 improves this to, for every $\varepsilon>0$, \[ y\geq \frac{(2+\varepsilon)\sqrt{x}\log^2x}{8\pi}. \] (b)**

A search also finds Matt Visser's arXiv:2101.03283 with the title claiming

truth of the conjecture. The official arXiv record says the paper is withdrawn and gives the reason: a critical inequality has the wrong direction and the proof does not appear fixable. It is not a current proof claim and supplies no result used here.

I found no later primary source claiming a valid unconditional solution. This is a search result, not a proof that no uncatalogued literature exists.

Exact reductions

1. Prime-index form

Let $p_i$ denote the $i$-th prime. For the standard integer version, the inequality for all $x,y\geq2$ is equivalent to

p_{i+j-1}\geq p_i+p_j-1\qquad(i,j\geq2). \tag{1}

Proof (a). Given $x,y$, put $i=\pi(x)+1$ and $j=\pi(y)+1$. Since all quantities are integral, $p_i\geq x+1$ and $p_j\geq y+1$. Equation (1) gives $p_{i+j-1}>x+y$, hence $\pi(x+y)\leq i+j-2=\pi(x)+\pi(y)$.

Conversely, substitute $x=p_i-1$, $y=p_j-1$ in subadditivity. It gives $\pi(p_i+p_j-2)\leq i+j-2$, which is exactly $p_{i+j-1}\geq p_i+p_j-1$. This is Segal's equivalence, but the two-line argument above proves the needed form directly.

This reduction explains why a finite verification can be organized using prime gaps, but it does not turn any finite bound into an eventual theorem.

2. Admissible-set form

A finite set $H$ is admissible if $H\bmod p$ omits at least one residue class for every prime $p$.

H\subseteq\{1,\ldots,y\},\qquad |H|>\pi(y), \tag{2}

and some translate $n+H$ consists entirely of primes, then

\pi(n+y)-\pi(n)\geq |H|>\pi(y). \tag{3}

This implication is elementary. (a)

The prime-$k$-tuples conjecture asserts that every fixed admissible $H$ has infinitely many all-prime translates. Applying that unproved conjecture to (2) turns (3) into a conditional counterexample. (c)

For the live wording, one fixed $y$ is insufficient. Hensley–Richards' theorem supplies sets satisfying (2), with quantitative surplus, for every sufficiently large $y$; prime $k$-tuples would then give counterexamples with both parameters unbounded. (b theorem + c conjectural antecedent)

Explicit 447-set and local-obstruction certificate

Define the following fixed residue table:

(2,0) (3,2) (5,0) (7,4) (11,6) (13,11) (17,2) (19,10)
(23,12) (29,5) (31,16) (37,35) (41,5) (43,22) (47,24)
(53,45) (59,30) (61,27) (67,34) (71,36) (73,40)
(89,52) (97,5) (101,26) (113,14)

and

H=\{1\leq h\leq3159:h\not\equiv r\pmod p \text{ for every listed }(p,r)\}. \tag{4}

The standalone script reconstructs (4), rather than trusting a pasted 447-number list. It proves the following finite facts:

$|H|=447$, $\min H=1$, and $\max H=3159$;
the SHA-256 of the comma-separated increasing list is

4ef04716111695e2071b6b91713d294906aabc168d6950b0f54c0e532ccb2601;

$\pi(3159)=446$;
for every prime $p\leq443$, $H\bmod p$ has a missing class; the

script prints one such class for every $p$;

for every prime $p\geq449$, admissibility follows without computation

from $|H|=447<p$.

Thus $H$ is admissible. (d finite exhaustive check; its short cardinality argument is (a))

The missing classes also give a fully explicit Chinese-remainder certificate. Let

M =
106799349783510324633088196370154963001649294985563231205816767298822135097700082617263814630462281610668318462376243299771362029792038518622755267843677086440779983634954128409675690

X0 =
20499370041925666315178288885852663105642845878314753540522650708878928839402615328257498236951862071123315435901241246307891319221603538716451667213716497340677518685252782465367590

The script recomputes $M=\prod_{p\leq443}p$, constructs $X_0$ by CRT, and checks

\gcd(M,X_0+h)=1\qquad(h\in H). \tag{5}

Consequently (5) also holds with $X_0$ replaced by $X_0+tM$, for every integer $t$. (a), with all finite arithmetic recomputed in (d)

This is a concrete all-local-obstructions-removed family. For primes dividing $M$, (5) is the certificate; for a prime $q\nmid M$, multiplication by $M$ permutes the classes modulo $q$, and admissibility of $H$ leaves a choice of $t\bmod q$ avoiding divisibility of every form. It is not a family of prime translates: proving that even one, let alone infinitely many, of these 447-tuples is all prime is far beyond current methods. Nor would the fixed value $y=3159$ alone refute the live eventual statement.

Exact $x\leq10^8$ computation

The script sieves from scratch through $101\,000\,000$. For each listed width it exhausts every integer

y\leq x\leq100\,000\,000

and computes the exact maximum of $\pi(x+y)-\pi(x)$. (d)

$y$	$\pi(y)$	exact max	deficit	a maximizing $x$	last prime
1,731	269	220	49	1,972	3,701
3,159	446	377	69	3,202	6,361
4,333	591	492	99	4,420	8,753
10,000	1,229	1,035	194	10,036	20,029
100,000	9,592	8,397	1,195	100,042	200,041
1,000,000	78,498	70,437	8,061	1,000,116	2,000,113

Here “deficit” is $\pi(y)-\max_x(\pi(x+y)-\pi(x))$, so every row has a substantial positive safety margin on the stated finite domain.

The exhaustiveness argument is short. If $p$ is the first prime in $(x,x+y]$ and $p\leq10^8+1$, replacing $x$ by $p-1$ cannot lose a prime and keeps $x$ in range. The interval then corresponds to a consecutive block of primes of diameter at most $y-1$. A two-pointer pass checks every such block. If $p>10^8+1$, moving $x$ to the right endpoint $10^8$ loses no prime, and the script checks that boundary separately. Finally, a separate binary-search count verifies each reported witness. (a) exhaustiveness reduction + (d) arithmetic

The measured run was:

python runs/erdos855_wave6o_verify.py
...
TIMING: sieve=6.440s total=20.534s
ALL CHECKS PASSED
PROCESS elapsed=20.65 cpu=99% maxrss_kb=371216

This does not improve Axler's reported range of validity: all of these sums are far below his external $3.97\cdot10^{10}$ bound. Its extra content is the exact maximum and witness for each selected width, obtained independently from scratch.

Exact analytic reduction and the wall

Let

\operatorname{Li}_2(t)=\int_2^t\frac{du}{\log u}, \qquad E(t)=\pi(t)-\operatorname{Li}_2(t).

For $x\geq y>2$, define the main-term advantage of the initial interval

A(x,y)=\operatorname{Li}_2(y) -\int_x^{x+y}\frac{du}{\log u}. \tag{6}

It is positive throughout the sufficiently-large regime relevant here (it need not be positive for every tiny $y$). Then the identity

\pi(x+y)-\pi(x)-\pi(y) =-A(x,y)+E(x+y)-E(x)-E(y) \tag{7}

is exact. Therefore the sufficient condition

A(x,y)\geq |E(x+y)|+|E(x)|+|E(y)| \tag{8}

proves the desired inequality. (a)

For $y=o(x)$, the main margin in (6) has scale

\frac{y\log(x/y)}{\log x\,\log y}.

Separate global bounds on $|E(x)|$ cannot make (8) work once $y$ drops below the prime-number-theorem error scale times logarithmic factors. Chahal et al.'s theorem makes this precise and, under RH, reaches roughly $\sqrt{x}\log^2x$. The live page's conjectural regime $(\log x)^C$ is vastly shorter. (b)

The exact missing positive-side lemma is thus a one-sided, constant-1 uniform upper bound for primes in short intervals, or equivalently control of the increment $E(x+y)-E(x)$ far below what follows by subtracting two global PNT error bounds. The large sieve gives the constant $2$, not the needed asymptotic constant $1$, and ordinary sieve machinery encounters the parity barrier. This identifies the analytic obstruction rather than merely saying “the problem is open.”

On the negative side, the exact missing lemma is realization of dense admissible sets by primes. Hensley–Richards already construct admissible sets larger than $\pi(y)$ for every large $y$, but turning the members of one such set into simultaneous primes is precisely a prime-$k$-tuples problem. Maynard–Tao-type bounded-gap theorems guarantee only some primes among a substantially larger admissible tuple; they do not make all $\asymp y/\log y$ prescribed positions prime.

Why more finite computation does not close the gap

The measured $10^8$ scan scales linearly only at the level of sieving and fixed-width window passes. A monolithic Python extrapolation to Axler's $3.97\cdot10^{10}$ endpoint would require over 100 GB once the byte sieve and Python prime list are included, so it does not fit this 62 GB VM. A segmented C/C++ implementation would plausibly cost about 5–20 core-hours and under 8 GB for compact prime/window state; I did not run it because it would merely recheck a published finite range and still could not prove an eventual statement. No realistic finite extrapolation reaches an expected all-prime translate of a 447-form tuple.

Reproduction

Full standalone checker:

runs/erdos855_wave6o_verify.py

Commands:

# Fast construction, admissibility, pi(3159), and CRT check
python runs/erdos855_wave6o_verify.py --construction-only

# Full exact table above
python runs/erdos855_wave6o_verify.py

The checker uses only the Python standard library and regenerates every prime, tuple element, missing residue, CRT integer, and finite-window count; it contains no downloaded prime/admissible-tuple table.

PARTIAL: explicit 447-in-3159 admissible/CRT certificate and exact fixed-width scan through x=10^8 verified; the live large-x,large-y question remains open because the missing step is simultaneous primality of dense admissible sets (negative side) or a constant-1 short-interval upper bound below the PNT-error scale (positive side).

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