Specifying a least upper bound for the number of divisors as a function of n

Question

As the title suggest, I'm wondering if there is an explicit formula $f(n)$ for the maximum number of non-trivial divisors of any integer $n$. If that's not possible, then some bound on the number of divisors would also be appreciated.

For example, let $d$ be a function returning the number of divisors of an integer. If we restrict the domain of $f$ to just the integers $(5,10)$, then $f(n)=n/3$ since:

$d(5)=0$,

$d(6)=2$,

$d(7)=0$,

$d(8)=2$,

$d(9)=1$,

$d(10)=2$

I wrote a short script to test this and it looks like $n/3$ is a limit for any integer up to 10,000 (see below for the script). Does this hold to infinity? If so does anyone have an argument why this is the case?

max.divisibility=function (x) {
  for (i in 1:x) {
   a[i]=(length(factors(i))-2)/i
  }
  return(max(a))
}

max.divisibility(10000)
[1] 0.3333333

Answer 1

An even better explicit upper bound is $2\sqrt n$, since:

• every divisor $d$ of $n$ has a complementary divisor $n/d$;
• if $d\ge\sqrt n$ then $n/d\le\sqrt n$;
• therefore the number of divisors of $n$ greater than $\sqrt n$ is the same as the number of divisors of $n$ less than $\sqrt n$;
• the number of divisors of $n$ less than $\sqrt n$ is trivially at most $\sqrt n$.

(It turns out to be true that for every $\varepsilon>0$, there exists a constant $C_\varepsilon>0$ such that the number of divisors of $n$ is at most $C_\varepsilon n^\varepsilon$; the argument is a little bit more complicated.)

Answer 2

$$ d(n) \leq n^{ \left( \frac{1.0660186782977...}{\log \log n} \right) }. $$ Full details of the proof appear in J.-L. Nicolas et G. Robin. Majorations explicites pour le nombre de diviseurs de n, Canad. Math. Bull., 26, 1983, 485--492. Equality occurs at a single number (and this defines the constant 1.066..), namely 6,983,776,800.

Note that the above is not as strong asymptotically as Wigert's $$ \limsup \frac{d(n) \log \log n}{\log n} = \log 2 $$

Robin gave explicit bounds reflecting this, $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left(1 + \frac{1.934850967971441......}{\log \log n} \right) }$$ with equality at a single number, a Superior Highly Composite number roughly $6.929 \cdot 10^{40}$

Answer 3

Here’s an argument for Greg Martin’s claim that for every $\epsilon\gt0$ there is a constant $C_\epsilon\gt0$ such that the number of divisors of $n$ is at most $C_\epsilon n^\epsilon$.

If $n$ has prime factorization $\prod_kp_k^{\alpha_k}$, it has $\sigma_0(n)=\prod_k(\alpha_k+1)$ divisors (as a divisor is determined by choosing for each $p_k$ a number between $0$ and $\alpha_k$ of factors of $p_k$ to include).

Now

\begin{eqnarray} \log\frac{\sigma_0(n)}{n^\epsilon}=\sum_k\left(\log(\alpha_k+1)-\epsilon\alpha_k\log p_k\right)\;. \end{eqnarray}

The summand goes to $-\infty$ for $\alpha_k\to-1$ and for $\alpha_k\to\infty$, so it must have a maximum in between. Its derivative with respect to $\alpha_k$ is

$$ \frac1{\alpha_k+1}-\epsilon\log p_k\;, $$

so the maximum is at $\alpha_k=\frac1{\epsilon\log p_k}-1$. This is negative for sufficiently large $p_k$, and in this case the maximum is attained on the boundary $\alpha_k=0$, where the summand is $0$. Thus the sum is bounded by the sum of the maximum values of the summands for a finite number of primes. It follows that $\frac{\sigma_0(n)}{n^\epsilon}$ is likewise bounded.