4
$\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$
2
  • 1
    $\begingroup$ See Wilson's theorem. $\endgroup$
    – Lucian
    Commented May 1, 2014 at 15:31
  • 1
    $\begingroup$ Is it possible to find an asymptotic formula for prime counting function by using this formula? $\endgroup$
    – esege
    Commented May 3, 2014 at 20:49

2 Answers 2

4
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .