Best smoothness function $f(n)$ writing every $n$ as a sum of two $f(n)$-smooth integers (Erdős #334)
Statement
For a positive integer $n$, an integer is called $y$-smooth if it has no prime factor exceeding $y$. Determine the smallest function $f(n)$ such that every $n$ can be written as $n=a+b$ with $a,b\geq1$ both $f(n)$-smooth (so every prime $p$ dividing $a$ or $b$ satisfies $p\leq f(n)$). How fast does the optimal $f$ grow — in particular, is $f(n)=n^{o(1)}$?
Acceptance. FULLY RESOLVES: determine the true growth of the optimal $f(n)$ — for example a proof that $f(n)=n^{o(1)}$, or a proof that $f(n)\geq n^{c}$ for some fixed $c>0$ — with all steps. ADVANCES (each independently checkable): (a) improve the upper-bound exponent strictly below the best bound stated in the background (the Balog exponent $4/(9\sqrt e)+\epsilon=0.2695\ldots$), with proof; or (b) prove any nontrivial lower bound on $f(n)$; or (c) extend the exactly-verified values of OEIS A062241 to a new record index with reproducible sieve code and a certificate that each reported value is the least non-representable integer for that prime bound. Any improved exponent must be strictly smaller than the exponent stated in the background. Deliver a proof, or search/sieve code plus the attained exponent or extended sequence with certificate.
Background
Asked by Erdős [Er76e, p.272], repeated in Erdős–Graham [ErGr80, p.70] and [Er82d, p.55]; listed as open on erdosproblems.com/334 (fetched 2026-07-13, status 'open', tagged 'number theory'). Erdős originally asked whether $f(n)\leq n^{1/3}$ always holds; this is now known, and the best bound is due to Balog [Ba89], who proved $f(n)\ll_\epsilon n^{4/(9\sqrt e)+\epsilon}$ for every $\epsilon>0$, where $4/(9\sqrt e)=0.2695\ldots$. It is expected that in fact $f(n)=n^{o(1)}$. The threshold data is tabulated as OEIS A062241, the smallest integer $\geq2$ that is not a sum of two positive integers all of whose prime factors are $\leq p_n$ (the $n$-th prime); extending this sequence gives direct numerical evidence about $f$. The problem also appears as Problem 59 on Ben Green's open-problems list. Erdős attached no prize. The attacker's tool: smooth-number and exponential-sum machinery of Balog type to lower the admissible exponent, together with sieve computation to extend A062241 and test the $n^{o(1)}$ prediction.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #334 (T. F. Bloom) | website |
| REF-02 | OEIS A062241 — smallest integer ≥2 not a sum of two integers whose prime factors are all ≤ the n-th prime | website |
| REF-03 | B. J. Green, Open problems (Problem 59) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.