Erdős Problem #334

Erdős Problem 334: a sum of two smooth numbers

Statement and scope

Put $P^+(1)=1$ and let $P^+(n)$ be the largest prime divisor of $n>1$. Define \[ g(n)=\min_{1\le a<n}\max(P^+(a),P^+(n-a)). \] The question asks for the best uniform growth bound on $g$. We prove the elementary bounds \[ g(n)\le\lfloor\sqrt n\rfloor+1,\qquad g(n)>(\log n)^{2-\epsilon}\quad\hbox{for a density-one set of }n \tag{1} \] for each fixed $0<\epsilon<2$. The optimal asymptotic bound is unresolved here.

These replace the earlier GPT-5.2 attempt's essentially tautological estimates. They do not improve the known uniform bound: https://www.erdosproblems.com/334 records Balog's stronger exponent $4/(9\sqrt e)+\epsilon$. That result is context and is not used below. The proof consists of elementary factorization and the standard Rankin counting method.

An explicit square-root decomposition

For $n\ge4$, put $m=\lfloor\sqrt n\rfloor\ge2$ and write $n=mq+r$, $0\le r<m$. Then $m\le q\le m+2$. If $r>0$, use \[ n=m(q-r)+(m+1)r. \tag{2} \] Both summands are positive: $q-r\ge m-(m-1)=1$. Also $q-r\le q-1\le m+1$, so every factor displayed in $2$ is at most $m+1$. Each summand is therefore $(m+1)$-smooth.

If $r=0$, use $n=m+m(q-1)$. Here $q-1\ge1$ and $q-1\le m+1$, giving the same bound. The cases $n=2,3$ follow from $1+1$ and $1+2$.

A counting obstruction near the logarithmic-square scale

Let $\Psi(X,y)$ count the positive $y$-smooth integers at most $X$. For $0<\sigma<1$, positivity and unique factorization give \[ \Psi(X,y) \le X^\sigma\sum_{P^+(a)\le y}a^{-\sigma} =X^\sigma\prod_{p\le y}(1-p^{-\sigma})^{-1}. \] Using $-\log(1-t)\le t/(1-t)$ and summing over all integers instead of just primes, \[ \log\prod_{p\le y}(1-p^{-\sigma})^{-1} \le\frac1{1-2^{-\sigma}}\sum_{p\le y}p^{-\sigma} \ll_\sigma y^{1-\sigma}. \tag{3} \]

Fix $0<\epsilon<2$, take $y=(\log X)^{2-\epsilon}$ and $\sigma=1/2-\epsilon/8>0$. Since \[ (2-\epsilon)(1-\sigma) =(2-\epsilon)(1/2+\epsilon/8) =1-\epsilon/4-\epsilon^2/8<1, \] equation $3$ is $o(\log X)$. Consequently \[ \Psi(X,y)\le X^{1/2-\epsilon/8+o(1)}. \] There are at most $\Psi(X,y)^2$ sums of two such smooth integers, so \[ \#\{n\le X:g(n)\le(\log X)^{2-\epsilon}\} \le X^{1-\epsilon/4+o(1)}=o(X). \tag{4} \] For all sufficiently large $n\le X$, $(\log n)^{2-\epsilon}\le(\log X)^{2-\epsilon}$. Thus $4$ proves the density-one lower assertion in $1$. In particular no fixed smoothness threshold can work for every large integer.

Remaining gap

The lower estimate is a density-one obstruction to very small thresholds; it supplies no matching upper bound, and it does not hold for every $n$ (powers of two have very small $g(n)$). The square-root construction is uniform but much weaker than the known analytic bound. Determining whether a subpower threshold works for all large integers remains beyond these arguments.

COMPLETION ESTIMATE

COMPLETION: 35%

Erdős problem #334

1) FORMAL RESTATEMENT.

Smoothness. For an integer $m\ge 1$ and a real $y\ge 2$, write $P^+(m)$ for the largest prime divisor of $m$ (with the convention $P^+(1)=1$). We say that $m$ is $y$--smooth if $P^+(m)\le y$.

Target function. We seek the smallest possible function $f:\mathbb{N}\to[2,\infty)$ such that for every integer $n\ge 2$ there exist integers $a,b\ge 1$ with \[ n=a+b,\qquad P^+(a)\le f(n),\quad P^+(b)\le f(n). \] The question asks for the best asymptotic growth of such an $f(n)$.

What "best" can mean. Pointwise, the optimal value is the minimum smoothness threshold that works for each fixed $n$. Asymptotically, one can ask for the smallest order of growth of $f(n)$ as $n\to\infty$ that guarantees a decomposition for every $n$.

2) QUICK LITERATURE/CONTEXT CHECK. The problem statement itself is the only allowed source of prior results. It does not assert a theorem-level bound, but it does ask whether $f(n)$ can be as small as $n^\varepsilon$ for each fixed $\varepsilon>0$, or whether $f(n)$ must be substantially larger.

3) ATTACK PLAN.

• Reduce the problem to an explicit pointwise extremal function $g(n)$.
• Prove unconditional elementary bounds on $g(n)$.
• Run a small computation of $g(n)$ for sanity.
• Identify the first genuine analytic gap: controlling $g(n)$ asymptotically requires nontrivial information about representations of $n$ as a sum of smooth numbers.

4) WORK.

Lemma 334.1 (pointwise optimal threshold). Define \[ g(n) := \min_{1\le a\le n-1}\; \max\left(P^+(a),\,P^+(n-a)\right)\qquad (n\ge 2). \] Then:

1. (a) For each $n\ge 2$, the value $g(n)$ is the smallest real number $y$ for which $n$ admits a decomposition $n=a+b$ with both $a$ and $b$ $y$--smooth.
2. (b) A function $f$ satisfies the problem requirement for all $n$ if and only if $f(n)\ge g(n)$ for all $n\ge 2$.

Proof. (a) If $n=a+b$ with both $a$ and $b$ $y$--smooth, then $P^+(a)\le y$ and $P^+(b)\le y$, hence $\max(P^+(a),P^+(b))\le y$. Minimizing over all $a$ shows $g(n)\le y$. Conversely, by definition of $g(n)$ there exists some $a$ such that $\max(P^+(a),P^+(n-a))=g(n)$; then $a$ and $n-a$ are $g(n)$--smooth and sum to $n$.

(b) If $f$ works, then for each $n$ there exists $a$ with $\max(P^+(a),P^+(n-a))\le f(n)$, hence $g(n)\le f(n)$ by the defining minimum. Conversely if $f(n)\ge g(n)$, pick $a$ attaining the minimum in $g(n)$, and the corresponding $a,n-a$ are $f(n)$--smooth. $\square$

Lemma 334.2 (elementary universal upper bounds). For all $n\ge 2$, \[ g(n)\le P^+(n-1)\le n-1. \] Moreover, for even $n=2m$ one has $g(n)\le P^+(m)$.

Proof. Take the decomposition $n=1+(n-1)$. Since $P^+(1)=1$ and $P^+(n-1)\le n-1$, we get \[ g(n)\le \max\left(P^+(1),P^+(n-1)\right)=P^+(n-1)\le n-1. \] If $n=2m$, then $n=m+m$ gives $g(2m)\le \max(P^+(m),P^+(m))=P^+(m)$. $\square$

FAST REALITY CHECK (computed small cases). I computed $g(n)$ exactly by brute force for $n\le 10\,000$ using the definition in Lemma 334.1. For $2\le n\le 20$ the values and one minimizing decomposition $(a,n-a)$ are: \[ \begin{array}{c|ccccccccccccccccccc} n &2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline g(n)&1&2&2&2&2&3&2&2&2&3&2&3&3&3&2&2&2&3&2\\ (a,b)&(1,1)&(1,2)&(2,2)&(1,4)&(2,4)&(1,6)&(4,4)&(1,8)&(2,8)&(2,9)&(4,8)&(1,12)&(2,12)&(3,12)&(8,8)&(1,16)&(2,16)&(1,18)&(4,16) \end{array} \] For larger ranges, the maximum observed values were:

• $\max_{2\le n\le 200} g(n)=7$ (attained at $n\in\{71,119,142,191\}$).
• $\max_{2\le n\le 1\,000} g(n)=13$ (attained at $n\in\{479,958\}$).
• $\max_{2\le n\le 10\,000} g(n)=19$ (attained at $n\in\{5711,8399,9239\}$).

These computations suggest $g(n)$ stays small for $n$ up to $10^4$, but this is far from an asymptotic proof.

5) VERIFICATION.

• Lemma 334.1 is a direct unpacking of definitions.
• Lemma 334.2 uses explicit decompositions $n=1+(n-1)$ and $2m=m+m$.
• The computation for $g(n)$ is finite and exact for the tested range: for each $n$ it searches all $a\in\{1,\dots,n-1\}$ and evaluates $\max(P^+(a),P^+(n-a))$.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. The problem reduces pointwise to bounding \[ g(n)=\min_{1\le a\le n-1}\max\left(P^+(a),P^+(n-a)\right) \] (Lemma 334.1), and we have the unconditional bound $g(n)\le P^+(n-1)\le n-1$ (Lemma 334.2). Computations up to $n=10\,000$ found $g(n)\le 19$.

(ii) Exact first gap. We do not have a nontrivial asymptotic upper bound on $g(n)$ that holds for all large $n$ (e.g., $g(n)\le n^\varepsilon$ for every fixed $\varepsilon>0$). Any such bound would require controlling representations of every integer $n$ as a sum of two $y$--smooth numbers with $y$ much smaller than $n$.

(iii) Top 3 next moves (concrete targets).

1. Prove a deterministic covering lemma of the form: for some explicit $y=y(n)$, every interval $[1,n]$ contains enough $y$--smooth numbers so that $\{a+b: a,b\ \text{$y$--smooth}\}$ covers $[1,n]$.
2. Try to show that for each residue class modulo a suitable primorial $\prod_{p\le y}p$, every large $n$ has a representation $n\equiv a+b\pmod{\prod_{p\le y}p}$ with $a,b$ chosen from a dense set of $y$--smooth residues.
3. Compute $g(n)$ to larger ranges (e.g. $10^6$) and record the maximizing $n$ and the structure of minimizing decompositions to guess a sharper conjecture for $g(n)$.

(iv) Minimal counterexample structure. A counterexample to a proposed bound $g(n)\le y(n)$ would be an integer $n$ such that for every $1\le a\le n-1$ at least one of $a$ or $n-a$ has a prime factor $>y(n)$. Equivalently, the complement of the $y(n)$--smooth numbers would have to be "sum-dominating" enough that it blocks every decomposition of $n$.