Finding the integer $\le n$ with largest number of divisors

As mentioned in an answer to this question an integer less than $n$ with largest number of divisors can be found exploring the numbers $x$ of the form $$ x = 2^{a_1} 3^{a_2} \dots p_k^{a_k} \dots $$ (where $p_k$ is the $k$-th prime number) with the conditions $$ x \le n < 2x \quad \text{and}\quad a_1 \ge a_2 \ge \dots \ge a_k \ge \dots$$ to determine the complexity of this algorithm I would like to know the asymptotic number of tuples $(a_1, a_2, \dots)$ verifying these conditions as $n\to \infty$. I suspect that this number is $\gg_l \log^l n$ for every $l$ and $\ll_\epsilon n^\epsilon$ for every $\epsilon > 0$, but I don't know how to prove it.

Thanks for your help.

Solution 1:

For a given $n$, let $N(n)$ be the number of admissible exponent sequences, that is, the number of sequences $a_1 \geqslant a_2 \geqslant \ldots$ on nonnegative integers such that $$\frac{n}{2} < \prod_{\nu = 1}^{\infty} p_{\nu}^{a_{\nu}} \leqslant n\,. \tag{1}$$ Then indeed we have $N(n) \ll_{\epsilon} n^{\epsilon}$ for every $\epsilon > 0$ and $N(n) \gg_l \log^l n$ for every $l$.

This is easy to prove if we write the product in $(1)$ as a product of primorials. The non-increasingness of the exponent sequence makes this possible. Define $k = k(n)$ as the index such that $$p_k\# \leqslant n < p_{k+1}\#\,. \tag{2}$$ Then by the prime number theorem we have $k \sim \frac{\log n}{\log \log n}$. If $$\prod_{\nu = 1}^{k} (p_{\nu}\#)^{b_{\nu}} \leqslant n\,,$$ then a fortiori we have $$(p_{\nu}\#)^{b_{\nu}} \leqslant n \iff b_{\nu} \leqslant \frac{\log n}{\log (p_{\nu}\#)} = \frac{\log n}{\vartheta(p_{\nu})}$$ for each $\nu$. Hence $$N(n) \leqslant \prod_{\nu = 1}^{k}\biggl(1 + \biggl\lfloor \frac{\log n}{\vartheta(p_{\nu})}\biggr\rfloor\biggr) < 2^k\prod_{\nu = 1}^{k} \frac{\log n}{\vartheta (p_{\nu})}\,.$$ Now $$2^k = \exp (k\log 2) = \exp \frac{(1 + o(1))(\log 2)\log n}{\log \log n} = n^{o(1)}$$ and $$(\log n)^k = \exp (k\log \log n) = n^{1 + o(1)}$$ are straightforward. To estimate the denominator, we use \begin{align} \sum_{\nu = 1}^{k} \log \vartheta(p_{\nu}) &= \sum_{\nu = 1}^{k} \bigl(\log p_{\nu} + O(1)\bigr) \\ &= \vartheta(p_k) + O(k) \\ &= \log n + O(\log \log n) + O(k) \\ &= \log n + O\biggl(\frac{\log n}{\log \log n}\biggr) \end{align} per the Chebyshev bounds and $(2)$, thus $$\prod_{\nu = 1}^{k} \vartheta(p_{\nu}) = n^{1 + O\bigl(\frac{1}{\log \log n}\bigr)}\,.$$ Putting everything together gives $N(n) = n^{o(1)}$, whence $N(n) \ll_{\epsilon} n^{\epsilon}$ for all $\epsilon > 0$.

For the lower bound, fix an arbitrary $l > 0$ and assume $n$ is so large that $k > l+1$. Then we count the products $$\prod_{\nu = 2}^{l+1} (p_{\nu}\#)^{b_{\nu}} \leqslant n\,.\tag{3}$$ For every such product there is a unique $b_1$ such that $$\frac{n}{2} < \prod_{\nu = 1}^{l+1} (p_{\nu}\#)^{b_{\nu}} \leqslant n\,,$$ hence the number of products $(3)$ is a lower bound for $N(n)$. These products correspond to the lattice points in the simplex $S \subset \mathbb{R}^l$ with vertices $0$ and $$\frac{\log n}{\vartheta(p_{\nu})}\cdot e_{\nu-1},\qquad 2 \leqslant \nu \leqslant l+1,$$ whose ($l$-dimensional) volume is $$\frac{1}{l!}\prod_{\nu = 2}^{l+1} \frac{\log n}{\vartheta(p_{\nu})} = C_l \cdot \log^l n\,.$$ As $n \to \infty$ the number of lattice points in $S$ is asymptotically equal to the volume of $S$, hence $N(n) \gg_l \log^l n$ for every $l$.