Does x not dominate log(x!) asymptotically?

Question

In my study of asymptotics I learnt a general order of asymptotic growth of functions

$$1 < \log(\log x) < \log(x) < x^a < x^c < c^x < x! < x^x \quad\text{where } c > 1 > a > 0$$

I expected that

$$\lim_{x \to \infty}\frac{\log{x!}}{x} = 0$$

and thus $\log{x!} = \mathcal{O}(x)$ (my reasoning was that $x$ dominates a logarithmic function).

However, as per Wolfram Alpha

$$\lim_{x \to \infty}\frac{\log{x!}}{x} = \infty$$

Why is it so?

Answer 1

First Method: Stirling Approximation:

Perhaps we should use the Stirling approximation. For $x$ large,

$$x! \sim \frac{\sqrt{2 \pi}}{e^x} x^{x+1/2}$$

Then

$$L := \lim_{x \to \infty} \frac 1 x \log(x!) = \lim_{x \to \infty} \frac 1 x \log \left( \frac{\sqrt{2 \pi}}{e^x} x^{x+1/2} \right)$$

With some logarithm properties,

$$\log \left( \frac{\sqrt{2 \pi}}{e^x} x^{x+1/2} \right) = \frac 1 2 \log(2\pi)-x+ \left( x + \frac 1 2 \right) \log(x)$$

and so

$$L = \lim_{x \to \infty} \left( \frac{\log(2\pi)/2}{x} - 1 + \left( 1 + \frac{1}{2x} \right) \log(x) \right)$$

Clearly,

$$\begin{align*} \frac{\log(2\pi)/2}{x} &\xrightarrow{x \to \infty} 0 \\ -1 &\xrightarrow{x \to \infty} -1 \\ \log(x) &\xrightarrow{x \to \infty} \infty \\ \frac{\log(x)}{2x} &\xrightarrow{x \to \infty} 0 \end{align*}$$

Consequently, it is clear that $L = \infty$.

---

Alternate Method: Log-Gamma Series:

The log-gamma function (where $\Gamma(x)$ is a continuation of the factorial, the gamma function) $\ln(\Gamma(x))$ has the series representation

$$\ln \Gamma ( z ) = - \gamma z - \ln z + \sum _ { k = 1 } ^ { \infty } \left[ \frac { z } { k } - \ln \left( 1 + \frac { z } { k } \right) \right]$$

($\gamma$ is the Euler-Mascheroni constant.) Clearly then

$$\frac 1 x \ln \Gamma(x) = - \gamma - \frac{\ln x}{x} + \sum _ { k = 1 } ^ { \infty } \left[ \frac { 1 } { k } - \frac 1 x \ln \left( 1 + \frac { x } { k } \right) \right]$$

It is not difficult to see that, for $k \ge 1$, we have

$$0 < \frac 1 x \ln \left( 1 + \frac { x } { k } \right) < 1$$

Then we have that

$$\lim_{x \to \infty} \frac 1 x \ln \Gamma(x) = - \gamma +\lim_{x \to \infty} \sum _ { k = 1 } ^ { \infty } \left[ \frac { 1 } { k } - \frac 1 x \ln \left( 1 + \frac { x } { k } \right) \right] \ge \sum _ { k = 1 } ^ { \infty } \frac { 1 } { k } $$

and hence the limit is infinite since the harmonic series diverges.

Some trivial algebra should handle the fact that $\Gamma(x) = (x-1)!$ for integers $x$ to find the limit you more precisely desire, but I'll leave that to you.

---

Alternate Method: L'Hopital's Rule & The Digamma Function:

It should not be difficult to convince you that $\ln(x!)/x$ has an $\infty/\infty$ form, so L'Hopital applies. Appealing to the log-gamma function again then,

$$\lim_{x \to \infty} \frac{\ln \Gamma(x)}{x} = \lim_{x \to \infty} \frac{d}{dx} \ln \Gamma(x) = \lim_{x \to \infty} \frac{\Gamma'(x)}{\Gamma(x)}$$

As it happens, the digamma function is defined by

$$\psi(x) = \frac{d}{dx} \ln \Gamma(x) = \frac{\Gamma'(x)}{\Gamma(x)}$$

Numerous identities apply from here, each of which give a way to see an infinite limit:

• $\psi(x) \sim \ln(x) - 1/(2x) \to \infty$
• $\psi(x) = -\gamma + \sum_{k=1}^{x-1} 1/k \to \infty$ (at least for $x$ an integer)
• $\psi(x) = -\gamma + \sum_{n=0}^\infty \frac{x-1}{(n+1)(n+x)} \to \infty$ (the summands approach $1/(1+n)$ in the limit, so we deal with the harmonic series again)

just by skimming the page some.

---

(My reasoning was that $x$ dominates a logarithmic function.)

In general, yes, $x$ would dominate logarithms of polynomials. However, $x!$ is not a polynomial in the usual sense: this is essentially because, as $x$ is growing larger, you are adding more and more terms to that polynomial, in some sense. So (again, claiming very loosely) by taking an infinite limit, you essentially turn that polynomial into an infinite series -- at that point, the bets of domination are off, and you have to resort to other methods.