Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
16  
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 '10 at 17:57
5  
@: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 '10 at 0:39

1 Answer 1

up vote 28 down vote accepted

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.

share|improve this answer
2  
The point being that I'm already pretty good at testing primality up to $n = 100$. –  Theo Johnson-Freyd Oct 17 '10 at 0:24
5  
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 '10 at 3:01
2  
Thanks. I had wondered about this for YEARS. –  Mike Jones Oct 17 '10 at 23:44
2  
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 '10 at 15:02
1  
@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 '10 at 16:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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