Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T04:28:44Z http://mathoverflow.net/feeds/question/42393 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42393/has-stirlings-formula-ever-been-applied-with-interesting-consequence-to-wilson Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem? Mike Jones 2010-10-16T16:42:59Z 2012-10-03T19:53:32Z <p>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.</p> http://mathoverflow.net/questions/42393/has-stirlings-formula-ever-been-applied-with-interesting-consequence-to-wilson/42398#42398 Answer by Charles for Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem? Charles 2010-10-16T18:46:35Z 2012-10-03T19:53:32Z <p>Using Robbins' [1] form of Stirling's formula,</p> <p>$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))&lt; n!&lt; \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$</p> <p>we get</p> <p>$$\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$$</p> <p>which is accurate enough to distinguish prime from composite for $n\le8$. For larger numbers, the error bound is too large.</p> <hr> <p>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.</p> <p>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.</p> <p>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.</p> <hr> <p>[1] H. Robbins, "A Remark on Stirling's Formula." <em>The American Mathematical Monthly</em> <strong>62</strong> (1955), pp. 26-29.</p>