Infinitely many $n$ with $\tau(n+k)\ll k$ for all $k\geq 1$? (Erdős #826)
Statement
For a positive integer $m$ let $\tau(m)$ denote the number of divisors of $m$. Is there an absolute constant $C$ such that, for infinitely many $n$, one has $$\tau(n+k)\leq Ck\quad\text{for every }k\geq 1?$$ Equivalently: are there infinitely many $n$ for which $\tau(n+k)\ll k$ holds uniformly over all $k\geq 1$, with an implied constant independent of both $n$ and $k$?
Acceptance. FULLY RESOLVES: a complete proof (Lean/Coq preferred, otherwise a full written proof) that there is an absolute constant $C$ with $\tau(n+k)\leq Ck$ for all $k\geq 1$ for infinitely many $n$; OR a proof that no such $n$ exist (for every constant $C$, only finitely many $n$ satisfy $\tau(n+k)\leq Ck$ for all $k$). ADVANCES: reduce Lau's exponent — a proof that for infinitely many $n$, $\tau(n+k)\ll k^{C'}$ for all $k\geq 1$, with an explicit $C'$ strictly smaller than the exponent $C$ established in Lau's [La26] result (state Lau's exponent, whatever value it is proved at, as the bar to beat); or an unconditional counting/density statement on the set of admissible $n$. Deliver the proof (formal or written) with the explicit improved exponent.
Background
Posed by Erdős [Er74b]; listed as open on erdosproblems.com/826 (fetched 2026-07-21, status 'open'). This is a strengthening of Erdős #248 (erdosproblems.com/248): it asks for integers $n$ past which the divisor counts of $n+1,n+2,\ldots$ grow no faster than linearly, uniformly in the offset. Recent progress: Lau [La26] proved that there is an absolute constant $C$ such that, for infinitely many $n$, $\tau(n+k)\ll k^{C}$ for all $k\geq 1$ — a polynomial-in-$k$ bound, leaving open whether the exponent can be brought down to $1$. The problem carries a 'looks difficult' reaction from Terence Tao on the site, and it has a Lean formalisation in the DeepMind formal-conjectures repository. Attacker's tool: sieve and smooth-number machinery to build long runs $n+1,\ldots,n+K$ with controlled divisor counts and to reduce Lau's exponent $C$ toward $1$; plus computational search over $n$ for the smallest attainable value of $\max_{k}\tau(n+k)/k$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #826 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #826 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.