0
$\begingroup$

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$

$\endgroup$
  • 5
    $\begingroup$ This is a geometric series... $\endgroup$ – Peter Foreman Jul 11 at 18:17
  • 1
    $\begingroup$ @InterstellarProbe They all add to zero, but this is a partial sum that doesn't include all of the roots of unity. $\endgroup$ – Peter Foreman Jul 11 at 18:23
  • $\begingroup$ Is that $j$ in your exponent just a typo? $\endgroup$ – Mark Fischler Jul 11 at 18:31
  • $\begingroup$ @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$. $\endgroup$ – evaristegd Jul 11 at 18:50
  • $\begingroup$ 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 $\endgroup$ – user36 Jul 13 at 8:32
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.