DISPROVED (LEAN)
This has been solved in the negative and the proof verified in Lean.
Let $f(n)$ be an additive function (so that $f(ab)=f(a)+f(b)$ if $(a,b)=1$) such that\[\limsup_{p,k}\frac{f(p^k)}{\log p^k}=\infty.\]Is it true that\[\limsup_n \frac{f(n+1)-f(n)}{\log n}=\infty?\]Or perhaps even\[\limsup_n \frac{f(n+1)}{f(n)}=\infty?\]
A conjecture of Erdős and Wirsing. Wirsing
[Wi70] proved (see
[491]) that if $\lvert f(n+1)-f(n)\rvert \leq C$ then $f(n)=c\log n+O(1)$ for some constant $c$.
Erdős suggested that for simplicity one might first assume that $f(p^k)=f(p)$ or $f(p^k)=kf(p)$.
The answer to both questions is no, and in fact the $\limsup$ can be $0$ - a simple counterexample is to take $f(q)=g(q)\log q$ for some sufficiently slowly growing function $g$, for all prime powers $q$. This construction appears to have first appeared in the literature in a paper of Wirsing
[Wi81], although Wirsing credits this observation to Erdős.
For more related literature see the comment by Tao.
View the LaTeX source
This page was last edited 01 April 2026. View history
Additional thanks to: KoishiChan and Terence Tao
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #897, https://www.erdosproblems.com/897, accessed 2026-04-11
