Why can this cosine sum function show all primes less than $N^2$?

Solution 1:

We will first show (with some help from my office-mate) that the function $P(m,x)$ is equal to the function: $$f_m(x)=\sum_{k=2}^m \frac{1}{k^2}\left(\frac{\sin(\pi x)}{\sin(\pi x/k)}\right)^2$$ In order to do this, we first recall the exponential sum formula: $$\sum_{j=-n}^{n}\exp(inx)=\exp\left(\frac{-inx}{2}\right)\frac{\sin(\frac{1}{2}(n+1)x)}{\sin(\frac{1}{2}x)}$$ From this formula (a commonly known formula in any book dealing with exponential sums), we obtain: $$\sum_{k=2}^m \frac{1}{k^2}\left(\frac{\sin(\pi x)}{\sin(\pi x/k)}\right)^2=\sum_{k=2}^m \frac{1}{k^2}\left(\sum_{j=1-k}^{k-1}\exp(ij\frac{2\pi x}{k})\right)^2$$ $$=\sum_{k=2}^m\frac{1}{k^2}\sum_{j=1-k}^{k-1}\sum_{t=1-k}^{k-1}\exp(i\frac{2\pi x}{k}(j+t))$$ Writing this out using sines and cosines: $$=\sum_{k=2}^m\frac{1}{k^2}\sum_{j=1-k}^{k-1}\sum_{t=1-k}^{k-1}\left[\cos\left(\frac{2\pi x}{k}(j+t)\right)+i\sin\left(\frac{2\pi x}{k}(j+t)\right)\right]$$

Notice that cosine is an even function so the cosine terms with $j+t>0$ and $-j-t$ may be combined to give $2\cos(\cdot\cdot\cdot)$ while sine being an odd function implies that the $j+t>0$ and $-j-t<0$ contributions will cancel. Thus, we may rewrite our formula as: $$=\sum_{k=2}^m\frac{1}{k^2}\left[\sum_{j+t=0}\cos\left(\frac{2\pi x}{k}(j+t)\right)+2\sum_{j+t>0}\cos\left(\frac{2\pi x}{k}(j+t)\right)\right]$$ where $1-k\leq j,t\leq k-1$ in the above summations. A simple counting argument for when different values of $j+t$ are equal then gives: $$=\sum_{k=2}^m\frac{1}{k^2}\left[k+2\sum_{j=1}^{k-1}(k-j)\cos\left(\frac{2\pi xj}{k}\right)\right]$$ and multiplying through by one of the factors of $\frac{1}{k}$ therefore indeed gives $f_m(x)=P(m,x)$.

Now, we will apply this useful identity to analyze the function:

If $x$ is an integer, then $\sin(\pi x/k)$ will be zero exactly when $k|x$, and $\lim_{x\to kt}\left(\frac{\sin(\pi x)}{\sin(\pi x/k)}\right)^2=k^2$, where $t\in\mathbb{Z}$. Every other term with $k\nmid x$ ($x$ still an integer) will have $\sin(\pi x)=0$ and $\sin(\pi x/k)$ nonzero. That is, for $x$ an integer, the only non-zero contributions come from divisors of $x$, and each of these will contribute $\frac{1}{k^2}\cdot k^2=1$. So, $f_m(x)$ gives the number of distinct divisors of $x$ which lie in between $2$ and $m$. This is why for $x$ a prime number between $2$ and $m$, the function gives $1$; for $x$ a prime number between $m$ and $m^2$, the function gives $0$; and why the function acts as a prime sieve for $x$ larger than $m^2$.

In this form, it is fairly easy to see that the period of $f_m(x)$, as it is the sum of these $\sin$ terms, is $\operatorname{lcm}(2,3,...,m)$.