For which arithmetic functions $f$ do the values $n+f(n)$ cluster into short intervals? (Erdős #122)
Statement
For which number-theoretic functions $f$ is the following true: for every function $F$ with $F(n)/f(n)\to 0$ for almost all $n$, there are infinitely many $x$ such that $$\frac{\#\{n\in\mathbb{N}:n+f(n)\in(x,x+F(x))\}}{F(x)}\to\infty?$$ Informally, for which $f$ do the shifted values $n+f(n)$ pile up in short windows far more densely than a window of width $F$ would predict, infinitely often? Erdős restricts attention to slowly growing $f$ (growing slower than $(\log n)^{1-c}$ for some fixed $c>0$).
Acceptance. FULLY RESOLVES: a complete characterisation of the slowly-growing number-theoretic functions $f$ for which the clustering property holds — a stated necessary-and-sufficient condition together with its proof (full written proof preferred). ADVANCES (each a self-contained checkable milestone): prove the clustering property for a specific named $f$ not already covered (beyond $\tau$ and $\omega$), with a complete proof; OR prove that the property FAILS for $f=\varphi$ or for $f=\sigma$ — exhibit an admissible $F$ (with $F(n)/f(n)\to0$ a.e.) for which no such $x$ exist, with proof — settling a case Erdős conjectured 'probably fails'; OR give a complete proof of the [EPS97] result for $\omega$ (or $\tau$) with interval widths $\lvert I\rvert,\lvert J\rvert$ strictly better than those stated in the background. Deliver the proof file for the characterisation, or for a specific $f$ (a proof that the property holds or that it fails).
Background
Posed by Erdős [Er97, p.155],[Er97e, p.533] and studied by Erdős, Pomerance, and Sárközy [EPS97]. They established the clustering phenomenon for $f=\omega(n)$ (the number of distinct prime factors): for all large $x$ there are intervals $I,J\subset[1,x]$ with $\lvert I\rvert\asymp(\log x/\log\log x)^{1/2}$ and $\lvert J\rvert\asymp(\log\log x)^{1/2}$ such that $n\in I\Rightarrow n+\omega(n)\in J$ (the normal order of $\omega$ is $\log\log x$, so $(\log\log n)^{1/2}/\omega(n)\to0$ almost everywhere, meeting the admissibility condition on $F$). Erdős reports [Er97],[Er97e] that he, Pomerance, and Sárközy can prove the general claim for $f=\tau(n)$ (the divisor function) and for $f=\omega(n)$, and states that it 'probably fails' for $f=\varphi(n)$ or $f=\sigma(n)$. The open task is to characterise the class of admissible $f$ and to settle the named borderline cases. The problem carries no cash prize, and has not yet been formalised in the Google DeepMind Formal Conjectures project. Listed as open on erdosproblems.com/122 (fetched 2026-07-13, status 'open', tagged 'number theory'). Attacker's tool: probabilistic and analytic number theory on the distribution of $n+f(n)$ in short intervals (the Erdős–Pomerance–Sárközy circle of methods), guided by direct computation of the empirical clustering of $n+f(n)$ for the candidate functions $\tau,\omega,\varphi,\sigma$ to steer a proof or a disproof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #122 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.