# Upper bound for sum of the nth roots of unity

Are there any upper bounds available for the following partial sum of Nth roots of unity

$$\Bigl \vert \sum_{l=0}^{Z-1} e^\frac{j2\pi li}{N } \Bigl\vert$$

apart from the trivial bound Z

$$N$$ is a power of 2 , $$Z < N$$ and $$1 \le i \le N$$

• This is a geometric series... – Peter Foreman Jul 11 at 18:17
• @InterstellarProbe They all add to zero, but this is a partial sum that doesn't include all of the roots of unity. – Peter Foreman Jul 11 at 18:23
• Is that $j$ in your exponent just a typo? – Mark Fischler Jul 11 at 18:31
• @MarkFischler , I thought the same, but I think $j$ is the imaginary number, and $i$ is some number that is bounded by $1$ and $N$. – evaristegd Jul 11 at 18:50
• Thank you very much Mark for your insights .....The summation is a function of i and the upper bound will vary for each i and thus will be a function of i – user36 Jul 13 at 8:32

Let's do this for $$j=1$$ (I assume you use $$i$$ as $$\sqrt{-1}$$ rather than some integer) and find an upper bound on the square of the sum $$S^2$$, which is less than $$Z^2$$.
Let $$\phi = \frac{2\pi}{N}$$. Then $$S^2 =\left| \sum_{m=0}^{Z-1} e^{m\phi / N} \right|^2 = \left( \sum_{m=0}^{Z-1} \cos (m\phi) \right)^2 + \left( \sum_{m=0}^{Z-1} \sin (m\phi) \right)^2 \\ = \sum_{m=0}^{Z-1} \left( \cos^2(m\phi) + \sin^2(m\phi) \right) + \sum_{p=0}^{Z-1} \sum_{\stackrel{q=0}{q \neq p}}^{Z-1}\left( \cos (p\phi) \cos(q\phi) + \sin(p\phi) \sin(q\phi) \right) \\ = Z + \sum_{p=0}^{Z-1} \sum_{\stackrel{q=0}{q \neq p}}^{Z-1} \left( \cos (p\phi) \cos(q\phi) + \sin(p\phi) \sin(q\phi) \right) =Z + \sum_{p=0}^{Z-1} \sum_{\stackrel{q=0}{q \neq p}}^{Z-1} \cos ((p-q)\phi)$$ Let's change summation variables on that double sum by writing $$k=p-q$$. The $$k=0$$ term drops out because that has $$q=p$$, and the value for $$-k$$ is the same as the value for $$k$$, so we get twice a sum from $$1$$ to $$Z-1$$ The number of possible $$(p,q)$$ pairs for each $$k$$ value is $$Z-k$$. (For example, when $$k=2$$, $$q$$ can be any number from $$0$$ to $$Z-3$$ (and $$p$$ is from $$2$$ to $$Z-1$$) and there are $$Z-2$$ such numbers. Then we get $$S^2 = Z + 2\sum_{k=1}^{Z-1}(Z-k) \cos(k\phi)$$ Thus far everything is exact, but now we use $$\cos x \leq 1-\frac{x^2}2+\frac{x^4}{24}$$ which holds for all the $$Z < N/2$$ cases we will care about. $$S^2 \leq Z + 2 \sum_{k=1}^{Z-1}(Z-k) \left[1-\frac{k^2\phi^2}2+\frac{k^4\phi^4}{24}\right] \\= Z + 2 \sum_{k=1}^{Z-1} Z -2\sum_{k=1}^{Z-1}k - \phi^2Z\sum_{k=1}^{Z-1}k^2 +\phi^2\sum_{k=1}^{Z-1}k^3+\frac{\phi^4Z}{12}\sum_{k=1}^{Z-1}k^4-\frac{\phi^4}{12}\sum_{k=1}^{Z-1}k^5 \\ = Z + (2Z^2-2Z) -(Z^2-Z) -\left(\frac13 Z^4 - \frac12 Z^3 + \frac16 Z^2\right)\phi^2 + \left(\frac14 Z^4 - \frac12Z^3 + \frac14 Z^2\right)\phi^2\\ + \left(\frac1{60}Z^6 -\frac1{24}Z^5 + \frac1{36}Z^4 + \frac1{360}Z^2 \right)\phi^4 - \left(\frac1{72}Z^6 -\frac1{24}Z^5 + \frac5{144}Z^4 + \frac1{144}Z^2 \right)\phi^4$$ Simplifying, $$S^2 \leq Z^2 \left( 1 - \frac{\phi^2}{12}Z^2 + \frac{\phi^2}{12} + \frac{\phi^4}{360}Z^4 - \frac{\phi^4}{144}Z^2 - \frac{\phi^4}{240}\right)$$ Then replacing $$\phi = \frac{2\pi}{N}$$ and noting that once we pass $$Z=N/2$$ any further entries merely cancel early entries in the sum, thus decreasing the absolute value, we can write this as $$S^2 \leq Z^2 \left( 1 - \frac{\pi^2}{12}\left(\frac{2Z}{N}\right)^2+ \frac{\pi^4}{360}\left(\frac{2Z}{N}\right)^4 +\frac{\pi^2}{3N^2} - \frac{\pi^2}{36 N^2}\left(\frac{2Z}{N}\right)^2 -\frac{\pi^4}{15N^4} \right)$$ Then if what you care about is large $$N$$, you can say that
$$\left| \sum_{m=0}^{Z-1} e^{m\phi / N} \right| \leq Z\sqrt{1 - \frac{\pi^2}{12}\left(\frac{2Z}{N}\right)^2+ \frac{\pi^4}{360}\left(\frac{2Z}{N}\right)^4}$$
By the way, just as an example, with $$N = 2^{10}$$, the absolute value for $$Z=200$$ is $$S = 0.93842 Z$$. The upper bound from the formula given is $$0.93851 Z$$.