Upper bound for sum of the nth roots of unity

Question

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$

Answer 1

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$.