5
$\begingroup$

I saw this formula on this paper page 2

$$\pi (n)=\sum_{j=2}^{n}\frac{\sin^{2}\left(\pi \frac{(j-1)!^{2}}{j}\right)}{\sin^{2}(\frac{\pi }{j})}$$

Where $\pi(n)$ is the prime counting function. Is this true? How to prove it?

$\endgroup$
  • 1
    $\begingroup$ See Wilson's theorem. $\endgroup$ – Lucian May 1 '14 at 15:31
  • $\begingroup$ Is it possible to find an asymptotic formula for prime counting function by using this formula? $\endgroup$ – esege May 3 '14 at 20:49
3
$\begingroup$

The simplest way in which this proposition would be true would be if $\displaystyle f(j)=\frac{\sin^2\left(\pi\frac{(j-1)!^2}{j}\right)}{\sin^2\left(\frac{\pi}{j}\right)}$ is equal to 1 if $j$ is prime, and 0 otherwise. It turns out that this is the case.

First, I will show that if $j$ is composite then $f(j)=0$. It is well known that if $j$ is composite (and not equal to 4), then $j\,|\,(j-1)!$. In this case, we just need that $j\,|\,(j-1)!^2$, which is true for any composite $j$ and can be shown by noting that if $j$ is composite, then one can write $j=ab$ where $1<a,b<j$. But then $a\,|\,(j-1)!$ and $b\,|\,(j-1)!$ and so obviously $j=ab\,|\,(j-1)!^2$. We see that if $j$ is composite, $f(j)=0$ since the argument of the $\sin$ function in the numerator is an integer multiple of $\pi$.

Now suppose that $j$ is prime. Then, by Wilson's Theorem, we have that $(j-1)!\equiv -1\,\text{ mod }j$ and so $(j-1)!^2\,\equiv 1\,\text{ mod }j$.

We can thus write $(j-1)!^2=1+kj$ for some integer k, and so

$\displaystyle \pi\frac{(j-1)!^2}{j}=\frac{\pi}{j}+k\pi$

But then $\displaystyle \sin^2\left(\pi\frac{(j-1)!^2}{j}\right)=\sin^2\left(\frac{\pi}{j}+k\pi\right)=\sin^2\left(\frac{\pi}{j}\right)$ since $\displaystyle \sin\left(\frac{\pi}{j}+k\pi\right)=\pm\sin\left(\frac{\pi}{j}\right)$ depending on whether $k$ is odd or even. This shows that $f(j)=1$.

This shows that the sum in question is indeed $\pi(n)$

$\endgroup$
4
$\begingroup$

Plug in some values in the sum and you see that the terms are just $0$ if $j$ is composite and $1$ if $j$ is prime. So there is nothing deep to understand about the entire sum, we just need to see how the summand determines primality. Clearly, you need to understand the behavior of $(n-1)! \mod n.$

If $n$ is composite, we can write $n= a\times b$ where $a,b < n.$ If $a\neq b,$ then both $a$ and $b$ appear in the terms of $(n-1)!$ so then $(n-1)! = 0\mod n.$ If $a=b,$ then both $a$ and $2a$ appear in the terms of $(n-1)!$ again and it is $0\mod n$ again unless $n=4.$ In that case we just compute $3! = 2\mod 4.$

Now suppose $n=p$ is prime. The equation $m^2=1\mod p$ has at most $2$ solutions since $\mathbb{Z}/(p)$ is a field, and these solutions are $1, -1.$ There are no other elements of $\mathbb{Z}/(p)$ which are self-inverse, so in the list of factors in $(p-1)! = 1\cdot 2 \cdots (p-1)$ we can pair up all the terms, except $1$ and $p-1,$ with their distinct inverse, so $(p-1)! = 1\cdot (p-1) = -1\mod p.$

Now plugging this information into the summand, we see that the terms are $0$ if $n$ is composite and $1$ if $n$ is prime, which is why the sum represents the prime counting function.

$\endgroup$

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.