Erdős Problem #855

Erdős Problem 855 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/855

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/855.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/855.tex.

FORMAL RESTATEMENT

Let $\pi(x)$ denote the number of primes in $[1,x]$ (for real $x\ge 0$, interpret $\pi(x)=\pi(\lfloor x\rfloor)$).

The conjectural inequality is \[ \pi(x+y) \le \pi(x)+\pi(y), \] stated informally "for large $x$ and $y$".

Ambiguity note. "For large $x$ and $y$" could mean:

• $S1$ there exists $X_0$ such that for all real $x,y\ge X_0$ the inequality holds; or
• $S2$ for all real $x,y\ge 2$ the inequality holds (a common sharpened form).

I treat $S2$ as the minimal corrected precise statement, but I also record that the literal inequality fails for small $y$.

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The statement reports conditional incompatibility with the Hardy--Littlewood prime tuples conjecture (Hensley--Richards; Clark--Jarvis) and unconditional upper bounds of Montgomery--Vaughan type.

ATTACK PLAN

• Disproof track: Search for explicit $(x,y)$ with $\pi(x+y)>\pi(x)+\pi(y)$; if found for arbitrarily large parameters it would disprove $S1$/$S2$.
• Proof track: Prove the inequality in special regimes (fixed small $y$, or restricted residue classes) and sanity-check numerically for moderate $(x,y)$.

WORK

Lemma 855.1 (Interval formulation). For real $x,y\ge 0$, \[ \pi(x+y) \le \pi(x)+\pi(y) \] holds if and only if the number of primes in the interval $(x,x+y]$ is at most $\pi(y)$.

Proof. By definition, $\pi(x+y)-\pi(x)$ equals the number of primes $p$ with $x<p\le x+y$, i.e. primes in $(x,x+y]$. Subtracting $\pi(x)$ from both sides gives \[ \pi(x+y)-\pi(x) \le \pi(y), \] which is exactly the stated interval bound. $\square$

Lemma 855.2 (Literal inequality fails for $y=1$). There exist $x,y$ with $y=1$ such that $\pi(x+y) > \pi(x)+\pi(y)$.

Proof. Take $(x,y)=(1,1)$. Then $\pi(2)=1$ while $\pi(1)+\pi(1)=0+0=0$, so $\pi(2)>\pi(1)+\pi(1)$. $\square$

Lemma 855.3 (The inequality holds for $y=2$ once $x\ge 2$). For every integer $x\ge 2$, \[ \pi(x+2) \le \pi(x)+\pi(2)=\pi(x)+1. \]

Proof. For $x\ge 2$, the interval $(x,x+2]$ contains exactly one even integer. Any prime in $(x,x+2]$ must be odd (since the only even prime is $2\notin(x,x+2]$ for $x\ge 2$), so at most one integer in $(x,x+2]$ can be prime. Thus $\pi(x+2)-\pi(x)\le 1=\pi(2)$. Apply Lemma 855.1. $\square$

Lemma 855.4 (The inequality holds for $y=3$ once $x\ge 2$). For every integer $x\ge 2$, \[ \pi(x+3) \le \pi(x)+\pi(3)=\pi(x)+2. \]

Proof. For $x\ge 2$, the interval $(x,x+3]$ contains at most two odd integers. Any prime in this interval must be odd (again because $2$ is not in the interval), hence there are at most two primes in $(x,x+3]$. Therefore $\pi(x+3)-\pi(x)\le 2=\pi(3)$ and Lemma 855.1 gives the claim. $\square$

FAST REALITY CHECK (exhaustive computation for moderate range). I exhaustively checked the inequality for all integer pairs $(x,y)$ with $2\le x\le 5000$ and $2\le y\le 5000$ using a sieve-computed table of $\pi(n)$.

Result:

For all integers 2 <= x <= 5000 and 2 <= y <= 5000:
  pi(x+y) <= pi(x) + pi(y)  holds.

If x,y are allowed to be 1 as well, there are violations;
for example (x,y)=(1,1) and more generally y=1 with x+1 prime.

I also performed 200,000 random trials with $1\le x,y\le 10^7$ and found no violations in that sample.

VERIFICATION

• Ambiguity handling: Lemma 855.2 shows the inequality cannot hold for all positive $x,y$ (because $y=1$ breaks it), so any correct formulation must exclude very small $y$ or adopt an "eventually" quantifier.
• Lemma 855.3--855.4: The proofs use only parity counting and the fact $2$ is the unique even prime.
• Computation: The exhaustive check for $2\le x,y\le 5000$ is exact within that box; it does not prove $S1$/$S2$ but serves as a sanity check.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. The inequality is equivalent to a bound on primes in short intervals (Lemma 855.1). It is false without excluding tiny $y$ (Lemma 855.2). It holds for all $x\ge 2$ when $y\in\{2,3\}$ (Lemmas 855.3--855.4), and computationally holds for all integer $2\le x,y\le 5000$.
2. (ii) First gap (crisp). Decide whether there exist arbitrarily large integers $x,y\ge 2$ such that $\pi(x+y)>\pi(x)+\pi(y)$ (disproof of $S1$/$S2$), or else prove that for all sufficiently large $x,y\ge 2$ the inequality holds.
3. (iii) Top 3 next moves.
   1. Guided by Lemma 855.1, search for explicit intervals $(x,x+y]$ with unusually many primes compared to $\pi(y)$; computationally, maximize $\pi(x+y)-\pi(x)$ over $x$ for a given large $y$.
   2. Attempt to make the conditional Hensley--Richards mechanism effective unconditionally: produce explicit admissible patterns that would force many primes in a length-$y$ interval, and check numerically whether they occur.
   3. Prove the inequality in restricted regimes (e.g. for $y\ge (\log x)^C$ as conjectured in the statement) using known upper bounds for primes in short intervals, if allowed.
4. (iv) Minimal counterexample structure. A counterexample with $x,y\ge 2$ is equivalent to a "prime-rich" interval $(x,x+y]$ containing more than $\pi(y)$ primes; heuristically this would require $x$ not much larger than $y$ (otherwise prime density near $x$ is smaller than near $y$).

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Let $\pi(x)$ denote the number of primes in $[1,x]$ (for real $x\ge 0$, interpret $\pi(x)=\pi(\lfloor x\rfloor)$).

The conjectural inequality is \[ \pi(x+y) \le \pi(x)+\pi(y), \] stated informally "for large $x$ and $y$".

Ambiguity note. "For large $x$ and $y$" could mean:

• $S1$ there exists $X_0$ such that for all real $x,y\ge X_0$ the inequality holds; or
• $S2$ for all real $x,y\ge 2$ the inequality holds (a common sharpened form).

I treat $S2$ as the minimal corrected precise statement, but I also record that the literal inequality fails for small $y$.

QUICK LITERATURE/CONTEXT CHECK

I do not import external results beyond what is explicitly stated in the problem file. The statement reports conditional incompatibility with the Hardy--Littlewood prime tuples conjecture (Hensley--Richards; Clark--Jarvis) and unconditional upper bounds of Montgomery--Vaughan type.

ATTACK PLAN

• Disproof track: Search for explicit $(x,y)$ with $\pi(x+y)>\pi(x)+\pi(y)$; if found for arbitrarily large parameters it would disprove $S1$/$S2$.
• Proof track: Prove the inequality in special regimes (fixed small $y$, or restricted residue classes) and sanity-check numerically for moderate $(x,y)$.

WORK

Lemma 855.1 (Interval formulation). For real $x,y\ge 0$, \[ \pi(x+y) \le \pi(x)+\pi(y) \] holds if and only if the number of primes in the interval $(x,x+y]$ is at most $\pi(y)$.

Proof. By definition, $\pi(x+y)-\pi(x)$ equals the number of primes $p$ with $x<p\le x+y$, i.e. primes in $(x,x+y]$. Subtracting $\pi(x)$ from both sides gives \[ \pi(x+y)-\pi(x) \le \pi(y), \] which is exactly the stated interval bound. $\square$

Lemma 855.2 (Literal inequality fails for $y=1$). There exist $x,y$ with $y=1$ such that $\pi(x+y) > \pi(x)+\pi(y)$.

Proof. Take $(x,y)=(1,1)$. Then $\pi(2)=1$ while $\pi(1)+\pi(1)=0+0=0$, so $\pi(2)>\pi(1)+\pi(1)$. $\square$

Lemma 855.3 (The inequality holds for $y=2$ once $x\ge 2$). For every integer $x\ge 2$, \[ \pi(x+2) \le \pi(x)+\pi(2)=\pi(x)+1. \]

Proof. For $x\ge 2$, the interval $(x,x+2]$ contains exactly one even integer. Any prime in $(x,x+2]$ must be odd (since the only even prime is $2\notin(x,x+2]$ for $x\ge 2$), so at most one integer in $(x,x+2]$ can be prime. Thus $\pi(x+2)-\pi(x)\le 1=\pi(2)$. Apply Lemma 855.1. $\square$

Lemma 855.4 (The inequality holds for $y=3$ once $x\ge 2$). For every integer $x\ge 2$, \[ \pi(x+3) \le \pi(x)+\pi(3)=\pi(x)+2. \]

Proof. For $x\ge 2$, the interval $(x,x+3]$ contains at most two odd integers. Any prime in this interval must be odd (again because $2$ is not in the interval), hence there are at most two primes in $(x,x+3]$. Therefore $\pi(x+3)-\pi(x)\le 2=\pi(3)$ and Lemma 855.1 gives the claim. $\square$

FAST REALITY CHECK (exhaustive computation for moderate range). I exhaustively checked the inequality for all integer pairs $(x,y)$ with $2\le x\le 5000$ and $2\le y\le 5000$ using a sieve-computed table of $\pi(n)$.

Result:

For all integers 2 <= x <= 5000 and 2 <= y <= 5000:
  pi(x+y) <= pi(x) + pi(y)  holds.

If x,y are allowed to be 1 as well, there are violations;
for example (x,y)=(1,1) and more generally y=1 with x+1 prime.

I also performed 200,000 random trials with $1\le x,y\le 10^7$ and found no violations in that sample.

VERIFICATION

• Ambiguity handling: Lemma 855.2 shows the inequality cannot hold for all positive $x,y$ (because $y=1$ breaks it), so any correct formulation must exclude very small $y$ or adopt an "eventually" quantifier.
• Lemma 855.3--855.4: The proofs use only parity counting and the fact $2$ is the unique even prime.
• Computation: The exhaustive check for $2\le x,y\le 5000$ is exact within that box; it does not prove $S1$/$S2$ but serves as a sanity check.

FINAL

UNRESOLVED

1. (i) Strongest proved partial result. The inequality is equivalent to a bound on primes in short intervals (Lemma 855.1). It is false without excluding tiny $y$ (Lemma 855.2). It holds for all $x\ge 2$ when $y\in\{2,3\}$ (Lemmas 855.3--855.4), and computationally holds for all integer $2\le x,y\le 5000$.
2. (ii) First gap (crisp). Decide whether there exist arbitrarily large integers $x,y\ge 2$ such that $\pi(x+y)>\pi(x)+\pi(y)$ (disproof of $S1$/$S2$), or else prove that for all sufficiently large $x,y\ge 2$ the inequality holds.
3. (iii) Top 3 next moves.
   1. Guided by Lemma 855.1, search for explicit intervals $(x,x+y]$ with unusually many primes compared to $\pi(y)$; computationally, maximize $\pi(x+y)-\pi(x)$ over $x$ for a given large $y$.
   2. Attempt to make the conditional Hensley--Richards mechanism effective unconditionally: produce explicit admissible patterns that would force many primes in a length-$y$ interval, and check numerically whether they occur.
   3. Prove the inequality in restricted regimes (e.g. for $y\ge (\log x)^C$ as conjectured in the statement) using known upper bounds for primes in short intervals, if allowed.
4. (iv) Minimal counterexample structure. A counterexample with $x,y\ge 2$ is equivalent to a "prime-rich" interval $(x,x+y]$ containing more than $\pi(y)$ primes; heuristically this would require $x$ not much larger than $y$ (otherwise prime density near $x$ is smaller than near $y$).