5
$\begingroup$

An exercise:

Using the prime number theorem find an asymptotic expression for $d(n!)$ where $d$ is the number of divisors.

  • 1
    $d$ is multiplicative so write $n!=\prod_{p\le n}p^{v_p(n)}$ where each $v_p(n)=\sum_{l=1}\lfloor n/p^l\rfloor$, then $d(n!)=\prod_{p\le n}\left(1+\sum_{l=1}\left\lfloor\frac{n}{p^l}\right\rfloor\right)\le \prod_{p\le n}\left(1+\frac{n}{p-1}\right)$ which is bounded below by $n^{\pi(n)}/n\#$ and above by $n^{\pi(n)}/\prod(1-1/p)$. I'll see if I can flesh this out later.2011-11-29

3 Answers 3

6

The prime power-decomposition of $n!$ is well-known: $ n! = p_1^{e_1} \times \cdots \times p_k^{e_k} $ where $e_i = \left\lfloor \frac{n - s(p_i,n)}{p_i-1} \right\rfloor$, where $s(b,n)$ is sum of digits of number $n$ in base $b$. Thus $ d(n!) = \prod_{i=1}^k (e_i+1) = \prod_{i=1}^k \left( \left\lfloor \frac{n - s(p_i,n)}{p_i-1} \right\rfloor + 1 \right) $

Reasonably efficient code to compute $d(n!)$ in Mathematica is

FactorialPrimeExponent[n_, p_] :=   Quotient[n - Total[IntegerDigits[n, p]], p - 1]  FactorialDivisorCount[n_Integer] :=   Apply[Times, (FactorialPrimeExponent[n, #] & /@       Prime[Range[PrimePi[n]]]) + 1] 

The last half of $\{ e_i \}_{i=1}^k$ consists of ones, making $d(n!) \ge 2^{\Pi(n)}$ for all $n \ge 1$. The following plot suggests $d(n!) \sim O\left(\frac{\mathrm{e}^n}{n}\right)$:

enter image description here

4

Just to be annoying, taking $n!$ is not the most efficient way to get a large number of divisors. There is a recipe, which takes as parameter some real number $\delta > 0,$ and gives the exponent on each prime factor of a (very large) number, call it $N_\delta.$ the exponent of the prime $p$ is given by $ \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor $ which gives nonzero coefficients as long as $p^\delta \leq 2,$ that is $p \leq 2^{1/\delta}.$

An unusually rough approximation is $ N_\delta \approx e^{2^{1/\delta}} $

So, $ N_\delta \; = \; \prod_{p} \; p^{ \left\lfloor \frac{1}{p^\delta - 1} \right\rfloor} $ Note that the exponents are non-increasing and eventually zero, this is a finite product.

The number $N_\delta$ gives the largest possible value, among all positive integers $n,$ of $ \frac{d(n)}{n^\delta}.$ If the optimum should be achieved at more than one integer $n,$ the set is nevertheless finite and our $N_\delta$ is the largest number in the set.

See http://en.wikipedia.org/wiki/Superior_highly_composite_number as well as http://oeis.org/A002201

The definition tells us some quick theorems, $ d(n) \leq \sqrt{12 n} $ and $ d(n) \; \leq \; \; 24 \; \; \left( \frac{n}{315} \right)^{(1/3)} $ More elaborate work gives $ d(n) \; \leq \; \; n^{\frac{1.0660186782977...}{\log \log n}}$ with equality only at $n = 6,983,776,800,$ this number being $N_\delta$ when $\delta = 0.23,$ and $d(N_\delta) = 2304.$

From pages 260-266 in Hardy and Wright, we find Theorem 317, $ \limsup \frac{\log d(n) \log \log n}{\log n} = \log 2 $

We can give this quantitative shape with $ d(n) \; \leq \; \; n^{\left(\frac{\log 2}{\log \log n}\right) \left( 1 + \frac{1.93485096797...}{\log \log n} \right)}$ with equality only at $n =N_\delta$ for $\delta = 0.155,$ and $N_\delta \approx 6.929 \times 10^{40},$ and $d(N_\delta) = 764,411,904 \approx 7.6 \times 10^8.$

1

The answer is $\log d(n!)=c \frac{n}{\log n}+O(\frac{n}{\log^2 n}\log \log n) \ \ (*)$ where $c:=\sum_{k \geq 1}\frac{\log(1+\frac{1}{k})}{k}$To prove this we break the sum $\log d(n!)=\sum_{p\leq n} \log (1+v_p(n))$ into the sum over $ p \leq \frac{n}{\log n}$ and into $ \frac{n}{\log n}

The first case will give the error term and the second term will give the main term of (*).

We begin by finding an upper bound for each term of the sum: $v_p(n)=\sum_{k \geq 1}[\frac{n}{p^k}] \leq \frac{n}{p-1}$ and hence $1+u_p(n) \leq 3 \frac{n}{p}$ from which we get $\sum_{p \leq \frac{n}{\log n}} \log (1+u_p(n)) \leq \log 3 \pi(\frac{n}{\log n})+(\log n) \pi(\frac{n}{\log n})-\theta(\frac{n}{\log n}) \ll \frac{n}{\log^2 n}\log \log n $ The last inequality comes from the PNT estimates $\pi(x)=\frac{x}{\log x}+O(\frac{x}{\log^2x}) , \theta(x)=x+O(\frac{x}{\log x})$ Using stronger versions of the PNT, one might get a better approximation for the error term in (*).

The remaining region is over $p \in (\frac{n}{\log n},n].$ The union of the disjoint intervals $I_k:=(\frac{n}{k+1},\frac{n}{k}] \ \ k=1,2,..,m:=[\log n]$ certainly covers the remaining region. The union might extend a bit to the left of $\frac{n}{\log n}$, namely it is contained in $(\frac{n}{\log n}-2\frac{n}{\log^2 n},n].$ Notice that $u_p(n)=k$ when $p \in I_k$. Therefore, the "main term" sum is equal to $ \sum_{k=1}^{m} \log(1+k)(\pi(\frac{n}{k+1})-\pi(\frac{n}{k}))+O(\frac{n}{\log^2 n}\log \log n)$ where the error term comes from the contribution of the primes in $ (\frac{n}{\log n}-2\frac{n}{\log^2 n},\frac{n}{\log n}].$ The sum is equal to $\sum_{k=1}^m \log(1+\frac{1}{k}) \pi(n/k)-\log(1+m)\pi(n/m)$ Using the PNT in the aforementioned form one arrives at (*) by a finite amount of computation. The fact that $k \ll \log n$ is very handy for these computations since it provides the equality $\frac{1}{\log(n/k)}=\frac{1}{\log n}(1+O(\log \log n/\log n))$. One also uses $\sum_{k>m}\frac{\log(1+k^{-1})}{k}\ll \sum_{k>m} k^{-2} \ll \frac{1}{m}$