we-solve (beta)

Math-791-A2 · revision r1 · on Math-791

gpt pro 5.2 attempt on Math-791

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem #385
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. VERIFICATION
  7. FINAL
  8. COMPLETION ESTIMATE

Problem #385

FORMAL RESTATEMENT

For an integer $m\ge 2$, let $p(m)$ denote the least prime divisor of $m$. Define, for integers $n\ge 5$, \[ F(n)\ :=\ \max_{\substack{m<n\\ m\ \text{composite}}}\ \left(m+p(m)\right). \] The problem asks:
  1. Is there an $N$ such that for all $n\ge N$ one has $F(n)>n$?
  2. Does $F(n)-n\to\infty$ as $n\to\infty$ (i.e. for every $M$ there is $N_M$ such that $n\ge N_M\Rightarrow F(n)-n\ge M$)?

QUICK LITERATURE/CONTEXT CHECK

This is Erdős problem #385 in the Erdős Problems database. It is presented as open there, with the remark that "plausible conjectures on primes" suggest $F(n)\le n$ only finitely often and that perhaps $F(n)\ge n+(1-o(1))\sqrt{n}$ might hold; also note the trivial upper bound $F(n)\le n+\sqrt{n}$. Terence Tao has a detailed blog discussion relating the difficulty of ruling out $F(n)\le n$ to the parity barrier in sieve theory and to controlling gaps between certain almost primes (e.g. semiprimes with restricted factor ranges). The database notes an equivalence to another formulation (problem #[430] there) and a related question (problem #[463] there).

ATTACK PLAN

Write the inequality $m+p(m)>n$ as $p(m) > n-m$. Thus to prove $F(n)>n$ it suffices to find, for each large $n$, a composite $m$ in some short interval $[n-h,n)$ with least prime factor exceeding $h$ (i.e. an $h$-rough composite). Potential approaches suggested by the literature:
  • Reduce to locating semiprimes (or more generally $y$-rough integers) in intervals of length comparable to $y$.
  • Use sieve-theoretic estimates for rough numbers in short intervals; the main obstruction is that existing methods struggle to guarantee at least one survivor uniformly in $n$ at the relevant intermediate scales.
  • Try to build explicit families of "bad" $n$ with $F(n)=n$ (disproof of (a)), or conversely show that such families cannot persist beyond some scale (proof of (a)).

WORK

We record several unconditional observations.

Lemma 1 (odd $n$ are trivially good). If $n\ge 5$ is odd, then $F(n)\ge n+1$ (hence $F(n)>n$).

Proof: If $n$ is odd and $n\ge 5$, then $m:=n-1$ is an even integer $\ge 4$, hence composite, and $p(m)=2$. Therefore $m+p(m)= (n-1)+2=n+1$, and since $m<n$ we have $F(n)\ge n+1$. ∎

Lemma 2 (even $n$ satisfy $F(n)\ge n$). If $n\ge 6$ is even, then $F(n)\ge n$.

Proof: Let $m:=n-2$. Then $m$ is even and $\ge 4$, hence composite, and $p(m)=2$. Thus $m+p(m)=(n-2)+2=n$, so $F(n)\ge n$. ∎

Lemma 3 (even $n$ with $n-1$ composite are good). If $n\ge 6$ is even and $n-1$ is composite, then $F(n)>n$.

Proof: Take $m:=n-1$. Then $m<n$ and $m$ is an odd composite, hence $p(m)\ge 3$. Therefore \[ m+p(m)\ \ge\ (n-1)+3\ =\ n+2\ >\ n, \] so $F(n)\ge m+p(m)>n$. ∎

Corollary 4 (structure of possible counterexamples to (a)). If $n\ge 6$ and $F(n)\le n$, then $n$ must be even, $n-1$ must be prime, and necessarily $F(n)=n$.

Proof: By Lemma 1, no odd $n\ge 5$ can satisfy $F(n)\le n$. So $n$ is even. By Lemma 2, $F(n)\ge n$, hence $F(n)\le n$ forces $F(n)=n$. Finally, if $n-1$ were composite then Lemma 3 would give $F(n)>n$, a contradiction. Thus $n-1$ is prime. ∎

Lemma 5 (easy limsup lower bound). Along the subsequence $n=q^2+1$ with $q$ prime one has $F(n)-n\ge q-1\to\infty$. In particular, \[ \limsup_{n\to\infty}\left(F(n)-n\right)=\infty. \]

Proof: Fix a prime $q$ and set $n=q^2+1$. Take $m:=q^2<n$, which is composite with $p(m)=q$. Then \[ F(n)\ \ge\ m+p(m)\ =\ q^2+q\ =\ (q^2+1)+(q-1)\ =\ n+(q-1), \] so $F(n)-n\ge q-1\to\infty$ along this subsequence. ∎

Lemma 6 (trivial upper bound). For all $n\ge 5$, $F(n)\le n+\sqrt{n}$.

Proof: If $m<n$ is composite then $p(m)\le \sqrt{m}<\sqrt{n}$. Hence $m+p(m)<n+\sqrt{n}$, so taking the maximum over such $m$ gives $F(n)\le n+\sqrt{n}$. ∎

Computational sanity check (not a proof). A brute-force computation for $n\le 200$ shows that $F(n)=n$ for \[ n\in\{6,8,12,14,18,20,24,30,32,42,44,48,60,62,72,74,84,90,102,104,108,110,114,132,140,168,182,198,200\}, \] and $F(n)>n$ for all other $5\le n\le 200$.

VERIFICATION

The above lemmas are elementary and were checked symbolically:
  • Lemmas 1--3 are direct constructions of a single admissible composite $m<n$.
  • Corollary 4 is a direct logical combination of Lemmas 1--3.
  • Lemma 5 uses the explicit choice $m=q^2$; no hidden assumptions.
  • Lemma 6 uses the classical bound $p(m)\le \sqrt{m}$ for composite $m$.
None of these steps address the main difficulty: ruling out infinitely many even $n=p+1$ with $p$ prime and $F(n)=n$.

FINAL

UNRESOLVED.

Most promising partial results obtained above:

  • Complete reduction: any counterexample to eventual positivity must be even and of the form $n=p+1$ with $p$ prime (Corollary 4).
  • $\limsup (F(n)-n)=\infty$ (Lemma 5), and always $F(n)\le n+\sqrt{n}$ (Lemma 6).

Specific barrier:

  • One must control existence of $h$-rough composite numbers in intervals $[n-h,n)$ at intermediate scales (roughly $\log n \ll h \ll \sqrt{n}$), which is tightly connected to the parity problem in sieve theory.

Smallest missing step to a full resolution:

  • Prove (or disprove) that for all sufficiently large primes $p$ there exists a composite $m<p+1$ with $m+p(m)>p+1$; equivalently, show that for each large prime $p$ one can find an $h$ and a composite $m\in[p+1-h,p]$ whose least prime factor exceeds $h$.

COMPLETION ESTIMATE

COMPLETION: 35%