Erdős Problem #122

Erdős Problem 122: concentration of the values $n+f(n)$

Statement and a corrected quantifier

Which arithmetic functions $f$ have the following property: for every admissible positive length function $F$ with $F(n)/f(n)\to0$ for almost all integers $n$, the ratios \[ \frac{\#\{n\ge1:n+f(n)\in(x,x+F(x))\}}{F(x)} \] are unbounded along a sequence of $x$ tending to infinity? Here almost all refers to a set of natural density one. The ratio is $F/f$, not $f/F$. The reversed ratio in the earlier GPT-5.2 attempt changed the problem.

We give a broad obstruction and reconstruct the known unbounded-fibre theorem for $f=\omega$, conditional on an explicitly stated analytic lemma. Neither result classifies $f$ or proves the assertion for every admissible $F$; the problem is unresolved here. Source: https://www.erdosproblems.com/122.

An obstruction even for slowly growing functions

Suppose $f:\mathbb N\to\mathbb N$ tends to infinity and the integer-valued map $T(n)=n+f(n)$ has fibres of size at most $B$. An interval of real length $L$ contains at most $\lceil L\rceil$ integers, so \[ \#\{n:T(n)\in(x,x+L)\}\le B\lceil L\rceil. \tag{1} \] Choose $F(x)=\sqrt{f(\max(1,\lfloor x\rfloor))}$. Then $F(n)/f(n)\to0$ pointwise, $F(x)\to\infty$, and $1$ bounds the desired ratio by $B(1+1/F(x))$. Thus the requested property fails for this $f$, independently of any convention about very short intervals.

In particular, every nondecreasing integer-valued $f$ tending to infinity fails, since $T$ is strictly increasing. An example growing more slowly than every positive power of $\log n$ is $f(n)=\lceil\log\log(n+e^e)\rceil$. Slow growth alone is therefore insufficient; substantial oscillation or large fibres matter.

The analytic input for $\omega$

The following is Lemma 2 of Erdős, Pomerance and Sárközy, On locally repeated values of certain arithmetic functions, IV, Ramanujan J. 1 $1997$, 227--241: https://math.dartmouth.edu/~carlp/PDF/paper112.pdf. There are absolute constants $C,X_0$ such that, for $X\ge X_0$, $P\le X^{1/2}$, and every integer $h$, more than $X/(2P)$ integers $m\le X$ in the residue class $h\bmod P$ satisfy \[ |\omega_P(m)-\log\log X|<C\sqrt{\log\log X}, \tag{2} \] where $\omega_P$ counts prime divisors not dividing $P$. This uniform variance estimate is an external input, not proved here. We also use the prime number theorem in the standard form $p_j\sim j\log j$. The remainder is the authors' CRT and pigeonhole argument, with endpoint losses made explicit.

Reconstruction of the unbounded-fibre conclusion

Set $t=\lfloor\frac15\sqrt{\log X/\log\log X}\rfloor$. For $0\le i\le t$, take disjoint consecutive blocks $\mathcal P_i$ of $t-i$ primes, starting after all primes at most $t$, and let $P$ be their product. The number of selected primes is $t(t+1)/2$; the prime number theorem gives \[ \log P=(1/50+o(1))\log X. \] In particular $t<P\le X^{1/2}$ for large $X$. The Chinese remainder theorem gives a residue $r\bmod P$ with $r+i\equiv0\pmod p$ for every $p\in\mathcal P_i$. Since all these primes exceed $t$, no prime of $\mathcal P_j$ divides $r+i$ when $i\ne j$. Thus for every $n\equiv r\bmod P$, \[ \omega(n+i)=(t-i)+\omega_P(n+i). \tag{3} \]

For each $i$, $2$ supplies more than $X/(2P)$ suitable positive integers $m\equiv r+i\bmod P$. Discarding $m\le i$ loses at most one, because $i<P$. The remaining $m$ give positive bases $n=m-i\le X$ satisfying $2$. For large $X$, each $i$ supplies more than $X/(3P)$ such bases. There are at most $X/P+1\le2X/P$ possible bases in total, so some base $n$ has more than $(t+1)/6$ good indices $i$.

For these indices, $2$--$3$ place every $(n+i)+\omega(n+i)$ in the interval centred at $n+t+\log\log X$ of radius $C\sqrt{\log\log X}$. This interval contains at most $2C\sqrt{\log\log X}+1$ integers. Hence some integer $y\le X+\log X/\log2$ has \[ \#\{m:m+\omega(m)=y\} \gg\frac{\sqrt{\log X}}{\log\log X}. \tag{4} \] The right side tends to infinity. Such $y$ must also tend to infinity, since a fixed $y$ has at most $y$ positive preimages. This proves the known unbounded-fibre result relative to $2$ and the prime number theorem.

Remaining gap

Equation $4$ gives large concentrations at selected values. The problem quantifies over every admissible $F$, whose exceptional values may include those selected locations. Turning $4$ into that universal assertion, or classifying other arithmetic functions, requires further control not supplied by this proof.

COMPLETION ESTIMATE

COMPLETION: 45%

Erdős Problem #122

1) FORMAL RESTATEMENT

Let $f:\mathbb N\to\mathbb N$ be an arithmetic function. Consider any function $F:\mathbb N\to(0,\infty)$ such that \[ \frac{f(n)}{F(n)}\to 0\quad\text{for almost all }n \] (i.e. for all $\varepsilon>0$ the set $\{n: f(n)/F(n)>\varepsilon\}$ has asymptotic density $0$).

Question: for which functions $f$ is it true that there exist infinitely many $x\in\mathbb N$ such that \[ \frac{\#\{n\in\mathbb N:\ n+f(n)\in (x,x+F(x))\}}{F(x)}\to\infty\ ? \] (Here $(x,x+F(x))$ denotes the open interval in $\mathbb R$; equivalently we count those $n$ with $x<n+f(n)<x+F(x)$.)

2) QUICK LITERATURE/CONTEXT CHECK

From the problem text:

• Erdős--Pomerance--Sárközy proved the property holds for $f(n)=d(n)$ (divisor function) and for $f(n)=\omega(n)$ (number of distinct prime factors).
• Erdős believed it is false for $f(n)=\varphi(n)$ or $f(n)=\sigma(n)$.

No further sources are used here.

3) ATTACK PLAN

Try to identify simple necessary obstructions: classes of functions $f$ for which the conclusion cannot hold for some admissible choice of $F$. I give two such obstructions (bounded $f$, and eventually nondecreasing $f$), which already show the property is highly nontrivial and requires strong oscillation.

4) WORK

Lemma 122.1 (bounded $f$ cannot satisfy the conclusion).

Suppose $f$ is bounded: $f(n)\le B$ for all $n$. Then $f$ does not have the stated property.

Proof. Choose any function $F(n)\to\infty$ (e.g. $F(n)=n$). Then $f(n)/F(n)\to0$ for all $n$ and hence "for almost all $n$".

For any $x$, if $n+f(n)\in (x,x+F(x))$, then necessarily $n\in (x-B,\,x+F(x))$. Therefore \[ \#\{n:\ n+f(n)\in(x,x+F(x))\}\le \#\big(\mathbb N\cap(x-B,\,x+F(x))\big)\le F(x)+B+1. \] Dividing by $F(x)$ yields \[ \frac{\#\{n:\ n+f(n)\in(x,x+F(x))\}}{F(x)}\le 1+\frac{B+1}{F(x)}\to 1. \] In particular, this ratio cannot tend to $\infty$ along any sequence of $x$. Thus bounded $f$ fails the required property. $\square$

Lemma 122.2 (eventually nondecreasing $f$ cannot satisfy the conclusion).

Suppose $f$ is eventually nondecreasing: there exists $N_0$ such that $f(n+1)\ge f(n)$ for all $n\ge N_0$. Then $f$ does not have the stated property.

Proof. Define $g(n):=n+f(n)$. For $n\ge N_0$, we have \[ g(n+1)-g(n)=(n+1+f(n+1))-(n+f(n))=1+(f(n+1)-f(n))\ge 1. \] Hence $g$ is strictly increasing on $\{N_0,N_0+1,\dots\}$.

Fix any admissible $F$ with $f(n)/F(n)\to0$ for almost all $n$. For any $x$, the set $ \{n\ge N_0:\ g(n)\in(x,x+F(x))\} $ consists of integers $n$ whose strictly increasing images lie in an interval of length $F(x)$. Since $g$ increases by at least $1$ each step, there can be at most $\lceil F(x)\rceil$ such $n$ (more formally: the values $g(n)$ are distinct integers separated by $\ge1$, so an open interval of length $F(x)$ contains at most $\lceil F(x)\rceil$ of them). Thus for all sufficiently large $x$, \[ \#\{n:\ g(n)\in(x,x+F(x))\}\le F(x)+1. \] Dividing by $F(x)$ gives a uniform bound \[ \frac{\#\{n:\ n+f(n)\in(x,x+F(x))\}}{F(x)}\le 1+\frac{1}{F(x)}\le 2 \] for all large $x$. Hence the ratio cannot tend to $\infty$. Therefore any eventually nondecreasing $f$ fails the property. $\square$

5) VERIFICATION (FAST REALITY CHECK)

• Lemma 122.1 applies to $f(n)\equiv 1$ (bounded). Indeed $n+1$ hits any interval of length $F(x)$ in about $F(x)$ ways, ratio $\asymp 1$.
• Lemma 122.2 applies to $f(n)=n$ or $f(n)=n^2$ (eventually increasing). The map $n\mapsto n+f(n)$ is strictly increasing, so the count in any length-$F(x)$ interval is $O(F(x))$ and the normalized ratio is bounded.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. Two rigorous obstruction lemmas: bounded $f$ cannot satisfy the property (Lemma 122.1), and eventually nondecreasing $f$ cannot satisfy it (Lemma 122.2).

(ii) Exact first gap. Beyond these obstructions, characterize which highly oscillatory arithmetic functions (such as $d(n)$ or $\omega(n)$) do satisfy the "local repetition" phenomenon for every admissible $F$.

(iii) Top 3 next moves.

1. Try to prove a sufficient condition in terms of distribution of values of $f(n)$ in short intervals (e.g. many repeats) that forces the normalized count to become large.
2. Test the conjectured negative cases $\varphi(n)$ and $\sigma(n)$ by attempting to construct an explicit admissible $F$ that keeps the normalized ratio bounded.
3. Explore probabilistic models: treat $f(n)$ as a random-like multiplicative function and estimate clustering of $n+f(n)$.

(iv) Minimal counterexample structure. If Erdős' belief is correct for $\varphi$ or $\sigma$, a minimal counterexample would be a specific admissible $F$ such that, along all sequences of $x\to\infty$, the interval $(x,x+F(x))$ contains only $O(F(x))$ values of $n+f(n)$ with a uniformly bounded proportionality constant.