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:

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

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

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:

1. Dogmachine noted that one finite counterexample would not settle wording

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

2. Adenwalla corrected the Hensley–Richards display to include a positive

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

3. old-bielefelder raised the apparent obstruction $x=y$.

4. Thomas Bloom explained that the conditional claim concerns infinitely many

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

5. 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:

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

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

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

4. **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

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

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

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)

|---:|---:|---:|---:|---:|---:|

| 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