/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[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 \geq 1$ with $\tau((n+K)!) \geq 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.
F f n is
$$F(f,n)=\frac{\tau((n+\lfloor f(n)\rfloor)!)}{\tau(n!)},$$
where $\tau = \sigma_0$ counts divisors. We use the natural floor ⌊f n⌋₊, which agrees with
$\lfloor f(n) \rfloor$ when $f(n) \geq 0$ and is $0$ when $f(n) < 0$.
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
$$\lim_{n\to \infty}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 \geq 3$ and $F(f,n)$ is nondecreasing in $f(n)$, this is equivalent to asking for one
such $C$.
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) \geq 1$ always (Erdos420.one_le_F).
More generally, if $f(n)\leq \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) \leq \log n$ for all $n$, rather than for all large $n$, gives an equivalent question.
Erdős, Graham, Ivić and Pomerance proved [EGIP96, Corollary 2] that $K(n)/\log n$ is unbounded,
with $K(n)$ as in the module docstring. Equivalently, for every $c > 0$ we have
$F(c\log n, n) < 2$ for infinitely many $n$. In particular
$\liminf F(c\log n, n) \leq 2$.
Erdős, Graham, Ivić and Pomerance proved [EGIP96, Corollary 2] that for infinitely many $n$,
$$K(n) > \frac{\log n \cdot \log\log n \cdot \log\log\log\log n}{9(\log\log\log n)^3},$$
with $K(n)$ as in the module docstring. Equivalently,
$F(f,n) < 2$ for infinitely many $n$, where $f(n)$ is the right-hand side.
Erdős, Graham, Ivić and Pomerance proved [EGIP96, Corollary 3] that for all sufficiently large
$n$ we have $K(n) < n^{4/9}$, with $K(n)$ as in the module docstring. Hence
$F(n^{4/9}, n) \geq 2$ for all large $n$.