In [Er97] Erdős is only considering number theoretic functions which grow 'slowly' (i.e. slower than $(\log n)^{1-c}$ for some $c>0$).

This is considered by Erdős, Pomerance, and Sárközy [EPS97], who prove in particular that if $\omega(n)$ counts the number of distinct prime divisors of $n$, then for all large $x$ there are intervals $I,J\subset [1,x]$ of width\[\lvert I\rvert\asymp \left(\frac{\log x}{\log\log x}\right)^{1/2}\]and\[\lvert J\rvert \asymp (\log\log x)^{1/2}\]such that if $n\in I$ then $n+\omega(n)\in J$. (Note the normal order of $\omega$ is $\log\log x$, and hence $(\log\log n)^{1/2}/\omega(n)\to 0$ for almost all $n$.)

In [Er97] and [Er97e] Erdős reports that he, Pomerance, and Sárkzözy can prove the more general claim above for $f$ being $\tau(n)$, the divisor function, or $\omega(n)$, and states it 'probably fails' for $\phi(n)$ or $\sigma(n)$.

View the LaTeX source

This page was last edited 01 April 2026. View history