# Prove or disprove $\sum_{k=1}^{n} \frac{\cos(\frac{2\pi k x}{n})}{n}=1$ iff $n|x$, and equals $0$ otherwise.

I know for sure it must be impossible that the function I put forth to only have all prime and only prime zeroes, but I have to be able to prove it to be untrue.

Below is the summation I have found:

$$f(x) = 2 - \sum_{n=1}^{x} \sum_{k=1}^{n} \frac{\cos(\frac{2\pi k x}{n})}{n}$$

The exact thing I must disprove is that: $$f(x) = 0$$ iff x is prime, for integer x. If anyone can help me prove this to be false, I would really appreciate it. Thank you.

EDIT: I suppose at this time what I have need to prove or disprove is that:

$$f(n, x) = \sum_{k=1}^{n} \frac{\cos(\frac{2\pi k x}{n})}{n}$$

returns $$1$$ iff $$n | x$$, and return $$0$$ otherwise.

• You know for sure that it's false? How do you know? – quasi Sep 21 at 0:19
• @quasi I know it's false because if it is true then that means I can incredibly easily make a closed form of the prime counting function, which means that the Riemann Hypothesis is unnecessary in number theory. Essentially I think it's false because I don't think I'm smart enough to have come up with something this important in the realm of number theory. – Jackson Sep 21 at 0:24
• It appears to be the case that for all positive integers $x$, the double summation is equal to the number of positive integer divisors of $x$. – quasi Sep 21 at 0:35
• @quasi If this is true, then I better start writing about this. If anybody is able to prove this false in the meantime, I hope someone will explain how it does not work. – Jackson Sep 21 at 0:39
• Note that the summation requires on the order of $x^2$ summands. – quasi Sep 21 at 0:45

As you remark, it is enough to prove that $$\sum_{k = 1}^n\frac{\cos\left(\frac{2\pi Nk}{n}\right)}{n} = \begin{cases}1, &n\mid N\\0 & n\nmid N.\end{cases}$$ Note that since $$n$$ is fixed, it is equivalent to show $$\sum_{k = 1}^n\cos\left(\frac{2\pi Nk}{n}\right) = \begin{cases}n, &n\mid N\\0 & n\nmid N.\end{cases}$$

First, if $$n\mid N,$$ we have $$nm = N$$ for some integer $$N.$$ Then it follows that $$\sum_{k = 1}^n\cos\left(\frac{2\pi Nk}{n}\right) = \sum_{k = 1}^n\cos(2\pi mk) = \sum_{k = 1}^n 1 = n.$$

Now, recall that $$\cos(x) + i\sin(x) = e^{ix},$$ so that we have $$\sum_{k = 1}^n\cos\left(\frac{2\pi Nk}{n}\right) = \Re\left(\sum_{k = 1}^n\left(\cos\left(\frac{2\pi Nk}{n}\right) + i\sin\left(\frac{2\pi Nk}{n}\right)\right)\right) = \Re\left(\sum_{k = 1}^n e^{i\frac{2\pi Nk}{n}}\right).$$ Thus, it suffices to prove that more generally that if $$n\nmid N,$$ $$\sum_{k = 1}^n e^{i\frac{2\pi Nk}{n}} = 0.$$ Now, set $$\zeta_n = e^{2\pi i/n}.$$ We know that $$\zeta_n$$ is a primitive $$n$$th root of unity, and we have $$\zeta_n^{Nk} = e^{i\frac{2\pi Nk}{n}}$$. Dividing $$N$$ by $$n,$$ we have $$N = nq + r$$ for some integers $$r$$ and $$q$$ with $$0 < r < N.$$ This implies that $$\zeta_n^N = \zeta_n^r.$$ If $$\gcd(r,n) = 1,$$ then $$\zeta_n^r$$ is a primitive $$n$$th root of unity as well, and if $$\gcd(r,n) = d,$$ then $$\zeta_n^r$$ is a primitive $$n/d$$-th root of unity.

So, we now need to prove the following:

Lemma: Let $$n>2$$ be a positive integer. Suppose that $$\zeta_n$$ is a primitive $$n$$th root of unity, and let $$m$$ be a positive multiple of $$n.$$ Then $$\sum_{k = 1}^m\zeta_n^k = 0.$$

Proof: Writing $$m = na$$ for some (positive) integer $$a,$$ we can split up the sum as follows: \begin{align*} \sum_{k = 1}^m\zeta_n^k &= \sum_{k = 1}^{an}\zeta_n^k\\ &= \sum_{k = 1}^n\zeta_n^k + \sum_{k = n+1}^{2n}\zeta_n^{k} + \dots + \sum_{k = (a-1)n+1}^{an}\zeta_n^{k}\\ &= \sum_{k = 1}^n\zeta_n^k + \sum_{k = 1}^{n}\zeta_n^{n+k} + \dots + \sum_{k = 1}^{n}\zeta_n^{(a-1)n + k}\\ &= \sum_{k = 1}^n\zeta_n^k + \sum_{k = 1}^{n}\zeta_n^n\zeta_n^k + \dots + \sum_{k = 1}^{n}\zeta_n^{(a-1)n}\zeta_n^{k}\\ &= \sum_{k = 1}^n\zeta_n^k + \sum_{k = 1}^{n}\zeta_n^k + \dots + \sum_{k = 1}^{n}\zeta_n^{k}\\ &= a\sum_{k = 1}^n\zeta_n^k.\\ \end{align*} So in fact, it is enough to prove that $$\sum_{k = 1}^n\zeta_n^k = 0$$ if $$\zeta_n$$ is a primitive $$n$$th root of unity. However, we have $$\zeta_n^n = 1,$$ which implies that $$\zeta_n^n - 1 = 0.$$ Factoring the left hand side gives $$(\zeta_n - 1)(\zeta_n^{n - 1} + \zeta_n^{n-2} + \zeta_n^{n-3} + \dots + \zeta_n^2 + \zeta_n + 1) = 0.$$ Since $$\zeta_n$$ is a primitive $$n$$th root of unity, $$\zeta_n - 1\neq 0,$$ and so $$\zeta_n^{n - 1} + \zeta_n^{n-2} + \zeta_n^{n-3} + \dots + \zeta_n^2 + \zeta_n + 1 = 0.$$ But $$1 = \zeta_n^n,$$ so $$\zeta_n^n + \zeta_n^{n - 1} + \zeta_n^{n-2} + \zeta_n^{n-3} + \dots + \zeta_n^2 + \zeta_n = 0.$$ This is exactly what we wanted to prove! $$\square$$

So, your function does in fact have roots at exactly the primes (supposing that the domain of $$f$$ is the set of positive integers). However, this doesn't make the Riemann hypothesis unnecessary. We've known formulas for primes for a while, see for example here. I'm not an expert in analytic number theory, but I believe that part of the issue is that the formulas we have for primes are incredibly inefficient. Your formula involves a double sum which has a substantial number of terms, becoming rather computationally heavy as $$x$$ grows. I would recommend asking an additional question about why formulas for prime numbers (such as yours or the ones in the linked Wikipedia article) don't "make the Riemann hypothesis unnecessary," so that experts on that topic can answer and you can get a better understanding of how the Riemann hypothesis and prime numbers/prime number formulas interact.

• This is beautiful, thank you. I will make note that the computationally heavy summation I wrote does not represent a prime formula. It is a formula for the prime counting function, which does not currently have any definitions other than ones including the zeroes of the Riemann Zeta function. This is why the Riemann Hypothesis is so necessary for this generally. That's why I made that, in hindsight rather pompous, statement. – Jackson Sep 21 at 3:43
• @Jackson I'm not sure how what you wrote is a prime counting function: that should be a function $\pi$ such that $\pi(x) = \#\textrm{ of prime numbers }\leq x.$ Your function $f$ tells us when the input is a prime or not. – Stahl Sep 21 at 4:14
• Additionally, there are known formulas for $\pi(x).$ For example, see here. Again, there is an issue of efficiency in such a formula. – Stahl Sep 21 at 4:20
• The prime counting formulas I put forth are in the comment section. And you are right, I apologize. – Jackson Sep 21 at 4:24

Your formula has a closed form. Now first notice that if $$n$$ divides $$x=mn$$ we have

$$f(n, mn) = \frac{1}{n}\sum_{k=1}^{n} \cos(\frac{2\pi k mn}{n})$$

but this is simply

$$\frac{1}{n}\sum_{k=1}^{n} \cos(2\pi k m)=1$$

On the other hand the closed form when $$n$$ does not divide $$x$$ is

$$f(n, x) = \sum_{k=1}^{n} \frac{\cos(\frac{2\pi k x}{n})}{n}=\frac1{2} \left ( \frac{\sin(\pi(\frac1{n}+2)x)}{\sin(\frac{\pi x}{n})} -1 \right )$$

Since $$x$$ is an integer, we can remove $$2\pi x$$ getting

$$\frac1{2} \left ( \frac{\sin(\pi \frac1{n}x) }{\sin(\frac{\pi x}{n})} -1 \right ) = 0$$

So your formula is a form of sieving, linear. Riemann zeta function is based on sieving as well, but it condenses it and technically surpasses its linear nature.