## Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem?

Pressing the envelope, presumably the best scenario would be a simple proof of the Prime Number Theorem. After all, Wilson’s Theorem gives a necessary and sufficient condition, in terms of the Gamma Function, for a number to be a prime, and Stirling’s Formula specifies the asymptotic behaviour of the Gamma Function.

-
You're not pressing the envelope, you're trying to stuff a watermelon into it. I am pretty sure the error in Stirling's formula for $\Gamma(n)$ is way bigger than $n$ for large $n$ no matter how many terms you include, hence your idea has no chance of going anywhere. – Harald Hanche-Olsen Oct 16 2010 at 17:57
@:Harald Hanche-Olsen:Your point is well taken, but poorly given. The word “envelope” here is not the postal kind, but rather means a specialized case of “boundary” (specifically, sense # 7 of the definition of “envelope” in the Merriam-Webster online dictionary). You could have appropriately said, for example, “You are not pressing the envelope, but egregiously elbowing it.” – Mike Jones Oct 19 2010 at 0:39

## 1 Answer

Using Robbins' [1] form of Stirling's formula,

$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))< n!< \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$

we get

$$\left\lceil\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-11))\right\rceil$$ $$\le (n-1)!\le$$ $$\left\lfloor\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-12))\right\rfloor$$

which is accurate enough to distinguish prime from composite for $n\le8$. For larger numbers, the error bound is too large.

This can be extended further using a modification of Wilson's theorem: for n > 9, $$\lfloor n/2\rfloor!\equiv0\pmod n$$ if and only if n is composite. This allows testing 10 through 15, plus (with some cleverness) 17.

With tighter explicit bounds and high-precision evaluation, it might be possible to test as high as 100 with related methods: direct evaluation up to 25 and the 'divide by 4' variant of the above for n > 25.

This is not so much 'using a cannon to swat a fly' (using methods more powerful than needed) as it is 'using the space station to swat a fly': the methods must be extremely powerful and accurate to do very little.

[1] H. Robbins, "A Remark on Stirling's Formula." The American Mathematical Monthly 62 (1955), pp. 26-29.

-
The point being that I'm already pretty good at testing primality up to $n = 100$. – Theo Johnson-Freyd Oct 17 2010 at 0:24
Yes, but with less than two hours of research, plus a bignum library, you could have a millisecond-scale test rather than a nanosecond-scale test! – Charles Oct 17 2010 at 3:01
Thanks. I had wondered about this for YEARS. – Mike Jones Oct 17 2010 at 23:44
Remark: If you use the stronger form of Stirlings's theorem, where the trailing term is a sum over Bernoulli numbers, and you truncate that sum at the optimal point, then you can get much farther but you still lose in the end. The error is computing $n!$ this way is roughly $n!/(\pi e^{2 \pi n} \sqrt{n})$, which is greater than $1$ once $n$ is larger than $1455 \approx e^{2 \pi +1}$. See Concrete Mathematics, Problem 9.26. – David Speyer Oct 21 2010 at 15:02
@David: I really didn't expect to be able to get that far. With cautious modifications to Wilson's theorem that could probably give primality tests up to ten or fifteen thousand. Ah, wastefulness... – Charles Oct 21 2010 at 16:18
show 5 more comments