Additive functions that rarely decrease at $n\mapsto n+1$: must they be $c\log n$? (Erdős #1122)
Statement
Let $f:\mathbb{N}\to\mathbb{R}$ be an additive function, meaning $f(ab)=f(a)+f(b)$ whenever $a$ and $b$ are coprime. Put $$A=\{n\geq 1 : f(n+1)<f(n)\},$$ the set of $n$ at which $f$ decreases. Suppose $\lvert A\cap[1,X]\rvert=o(X)$, i.e. this set has density zero. Must it then follow that $f(n)=c\log n$ for some constant $c\in\mathbb{R}$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean preferred, otherwise a full written proof) that every additive $f$ whose decrease-set $A$ satisfies $\lvert A\cap[1,X]\rvert=o(X)$ must equal $c\log n$ for some real $c$; OR an explicit counterexample — an additive function with density-zero decrease-set that is not a constant multiple of $\log$, with the density claim proved. ADVANCES: a proof strictly extending the best stated partial result of Mangerel, which currently assumes $\lvert A\cap[1,X]\rvert\ll X/(\log X)^{2+c}$ plus a bound on $f(p)$ — weaken the density hypothesis toward the full $o(X)$, or remove/relax the restriction on $f(p)$, stated in words and proved. Deliver the proof or the counterexample construction.
Background
Posed by Erdős [Er46]. Erdős himself proved the conclusion $f(n)=c\log n$ under the stronger hypotheses that $A$ is empty (so $f$ is nondecreasing) or that $f(n+1)-f(n)=o(1)$. The density-zero relaxation stated here is what remains open. Best partial progress: Mangerel [Ma22] proved the conclusion holds if $\lvert A\cap[1,X]\rvert\ll X/(\log X)^{2+c}$ for some $c>0$ (a sparsity assumption strictly stronger than $o(X)$), together with a technical restriction that $f(p)$ does not take very large values. Related: Erdős #491 (erdosproblems.com/491). Listed as open on erdosproblems.com/1122 (fetched 2026-07-21, status 'open'). Attacker's tool: analytic number theory in the Erdős–Wirsing tradition on additive functions — the Turán–Kubilius inequality and correlations of additive functions along the shift $n\mapsto n+1$ — aimed at pushing Mangerel's density threshold $X/(\log X)^{2+c}$ down to the full $o(X)$ and removing the constraint on $f(p)$; the problem offers little direct computational purchase.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1122 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #491 — related | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.