Estimate $h(n)$, the powerful integers in $[n^2,(n+1)^2)$: is it $(\log n)^{c+o(1)}$? (Erdős #942)
Statement
For a positive integer $n$, let $h(n)$ be the number of powerful integers in the interval $[n^2,(n+1)^2)$ (an integer $m$ is powerful if $p\mid m\Rightarrow p^2\mid m$ for every prime $p$). Estimate $h(n)$. In particular, is there a constant $c>0$ such that $$h(n) < (\log n)^{c+o(1)}\ \text{ for all } n,\qquad\text{and}\qquad h(n) > (\log n)^{c-o(1)}\ \text{ for infinitely many } n?$$
Acceptance. FULLY RESOLVES: determine the true order of $h(n)$ — a proof, machine-checkable preferred else full written, establishing a constant $c>0$ with $h(n)<(\log n)^{c+o(1)}$ for all $n$ and $h(n)>(\log n)^{c-o(1)}$ for infinitely many $n$, and identifying $c$. ADVANCES: a proven upper bound $h(n)\ll(\log n)^{C}$ for some explicit constant $C$ (currently no such bound is recorded); an infinitely-often lower bound strictly stronger than the current record $h(n)\gg\log n/(\log\log n\,\log\log\log n)$, with proof; a rigorous determination or improved estimate of the densities $\delta_\ell$ (e.g. sharpening $\delta_1\approx 0.275$); or an extended reproducible computation of $h(n)$ and its extreme values over a new range with a certificate. Deliver the proof, or the bound/computation together with its certificate.
Background
Posed by Erdős [Er76d, p.35]. Erdős noted that it is not hard to show $\limsup_n h(n)=\infty$ (a proof that $h(n)$ is unbounded is given by van Doorn in the site comments) and that the density $\delta_\ell$ of $n$ with $h(n)=\ell$ exists with $\sum_\ell\delta_\ell=1$. De Koninck and Luca [DeLu04] proved that $h(n)\gg(\log n/\log\log n)^{1/3}$ for infinitely many $n$, and computed the density ($\approx 0.275$) of $n$ with $h(n)=1$. Hughes (with AI assistance) observed that the De Koninck–Luca argument makes two inefficient choices; optimised — as described in the site comments, see also [DLS05] — it yields infinitely many $n$ with $h(n)\gg\frac{\log n}{\log\log n\,\log\log\log n}$, essentially $(\log n)^{1-o(1)}$ and the current record infinitely-often lower bound (page last edited 15 June 2026). A matching upper bound of the shape $(\log n)^{O(1)}$ pinning the exponent $c$ remains open. Formalised in Lean as part of the Google DeepMind Formal Conjectures project (formal-conjectures/942). Listed as open on erdosproblems.com/942 (fetched 2026-07-21, status 'open'); no Erdős prize is attached. Attacker's tool: computation of $h(n)$ over large ranges (sieve powerful numbers via $a^2b^3$ and bucket them into $[n^2,(n+1)^2)$) to estimate the extremal growth and the densities $\delta_\ell$, together with the sieve/counting analysis behind the De Koninck–Luca construction to push the exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #942 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #942 (Google DeepMind Formal Conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.