# Proof that the factorial is nonelementary

Is there a proof that the factorial function $!:\mathbb N\to\mathbb N$ is nonelementary?

If it were equal to an elementary function (call it $P(n)$), then it would extend the factorial function to the real and complex numbers. This sounds like the Gamma function, but we have $\dfrac{\Gamma(n+1)}{\Gamma(n)}=n$ for all real $n$. It's entirely possible that $\dfrac{P(n)}{P(n-1)}$ isn't $n$, but rather something like $n+\sin(\pi n)$ which is only equal to $n$ at the integers. (Also, I've never found a proof that Gamma is nonelementary, either. I do know that the incomplete Gamma function is nonelementary, due to differential Galois theory.)

Also, the fact that $\pi$ appears in limits involving factorials isn't a proof, by the way. For example, the fact that: $$\lim_{n\to\infty}\frac{(n!)^2(n+1)^{2n^2+n}}{n^{2n^2+3n+1}}=2\pi,$$ which comes from Stirling's approximation, doesn't prove that it can't be elementary; we also have: $$\lim_{n\to\infty}n(-1)^{1/n}-n=i\pi$$ so it's possible for elementary functions to have $\pi$ as a limiting value.

So, is there any proof that the factorial function is nonelementary?

• – Alex R. Aug 11 '15 at 5:23
• @AlexR. I already know about that result. – Akiva Weinberger Aug 11 '15 at 5:36

We will use the following facts:

(i) The extension, to a larger domain, of a non-elementary function is also non-elementary;

(ii) The derivative of an elementary function is also elementary;

(iii) The product of finitely many elementary functions is also elementary;

(iv) The product of an elementary function times a non-elementary function is non-elementary.

Claim 1: $\Gamma(x)$ is a non-elementary function.

Proof. Assume the contrary. By (i) $n!$ must be elementary, and by (ii) so is $\Gamma'(x)=\Gamma(x)\psi^{(0)}(x)$, which by (iii) implies the same for $\psi^{(0)}(x)$ and all of its derivatives. But we have $$\psi^{(n)}(x)=(-1)^{n+1}\ n!\ \zeta(n+1,x),$$ where $\zeta(a,s)$ is the non-elementary Hurwitz zeta function, so combining (iii) and (iv) yields that $\psi^{(n)}(x)$ is a non-elementary function, contradiction. $\ \ \ \text{QED}$

Claim 2: $n!$ is a non-elementary function.

Proof. The Riemann zeta function satisfies \begin{align} 2\ \pi^{-s/2}\Gamma\left(\frac{s}{2}\right)\zeta(s)&= \int_0 ^ \infty \left(\vartheta(0,it) -1\right)t^{s/2-1}dt,\end{align} where $\vartheta(z,q)$ is the non-elementary Jacobi theta function. So let $s=2n$ to obtain \begin{align}2\pi^{-n}\Gamma(n)\zeta(2n) &= \int_0 ^ \infty \left(\vartheta(0,it) -1\right)t^{n-1}dt \\ 2\ \pi^{-n} (n-1)! \frac{ (-1)^{n+1} B_{2n}(2\pi)^{2n}}{2(2n)!} &= \int_0 ^ \infty \left(\vartheta(0,it) -1\right)t^{n-1}dt \\ - (-\pi)^n 2^{2n} B_{2n}\frac{(n-1)!}{(2n)!}&=\int_0 ^ \infty \left(\vartheta(0,it) -1\right)t^{n-1}dt.\end{align} Now, by (i) the Bernoulli numbers are elementary, due to being a restriction of the Bernoulli polynomials, which are elementary. But the RHS is non-elementary by (ii), therefore by (iii) the ratio of factorials is non-elementary as well, and the claim follows combining this and (iii). $\ \ \ \text{QED}$

Of course Claim 1 directly follows from Claim 2 by (i), but I wanted to give two different and independent proofs.

• In fact there's no need of seeking for a contradiction, to prove Claim 2. – Vincenzo Oliva Aug 13 '15 at 19:13
• In fact, the gamma function doesn't even satisfy an algebraic differential equation -- see Expanded concept of elementary function?. – Dave L. Renfro Aug 13 '15 at 19:32
• @Dave: Nice, thank you. And +1, by the way. – Vincenzo Oliva Aug 13 '15 at 19:37