12
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.