Erdős Problem #420

The question

erdos_420.parts.i. If $\tau (n)$ counts the number of divisors of $n$ then let $$F(f,n)=\frac{\tau ((n+\lfloor f(n)\rfloor )!)}{\tau (n!)}.$$ Is it true that $$\underset{n\to \infty }{\lim }F((\log n{)}^C,n)=\infty$$ for large $C$?

"For large $C$" means for all sufficiently large real $C$. Since $(\log n{)}^C$ increases with $C$ for $n\ge 3$ and $F(f,n)$ is nondecreasing in $f(n)$, this is equivalent to asking for one such $C$.

erdos_420.parts.ii. Is it true that $F(\log n,n)$ is everywhere dense in $(1,\infty )$?

This asks that every point of $(1,\infty )$ lies in the closure of the set of values $F(\log n,n)$. Note that $F(f,n)\ge 1$ always (Erdos420.one_le_F).

erdos_420.parts.iii. More generally, if $f(n)\le \log n$ is a monotonic function such that $f(n)\to \infty$ as $n\to \infty$, then is $F(f,n)$ everywhere dense?

"Everywhere dense" means dense in $(1,\infty )$, as in Erdos420.erdos_420.parts.ii. Asking for $f(n)\le \log n$ for all $n$, rather than for all large $n$, gives an equivalent question.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«420» (3 statements).

theorem erdos_420.parts.i :
    ∀ᶠ C : ℝ in atTop, Tendsto (F fun m ↦ Real.log m ^ C) atTop atTop

theorem erdos_420.parts.ii :
    Set.Ioi (1 : ℝ) ⊆ closure (Set.range (F fun m ↦ Real.log m))

theorem erdos_420.parts.iii :
    ∀ f : ℕ → ℝ, Monotone f → (∀ n, f n ≤ Real.log n) → Tendsto f atTop atTop →
      Set.Ioi (1 : ℝ) ⊆ closure (Set.range (F f))

What counts as progress

• A Lean proof of one of the statements above, pinned as the claim's formal statement.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already — check erdosproblems.com/420. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

• erdosproblems.com/420
• [ErGr80] Erdős, P. and Graham, R., *Old and new problems and results in combinatorial number theory*. Monographies de L'Enseignement Mathematique (1980).
• [EGIP96] Erdős, P. and Graham, S. W. and Ivić, A. and Pomerance, C., *On the number of divisors of $n!$*. Analytic number theory, Vol. 1 (Allerton Park, IL, 1995), Progr. Math. 138, Birkhäuser Boston (1996), 337-355.

In the solved variants, $K(n)$ is the least $K\ge 1$ with $\tau ((n+K)!)\ge 2\tau (n!)$, so that $K(n)>h$ if and only if $F(h,n)<2$. These variants state Corollaries 2 and 3 of [EGIP96] as printed; the stronger claims on erdosproblems.com are not stated.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.