1

If, given a root-of-unity approximation $\omega \approx e^{2 \pi i/n}$, and we want to take this approximation to the power $m$, how exacting must we be with the approximation so that:

$$\left|\left( e^{2 \pi i/n} \right)^m - \omega^m \right| < \epsilon$$

In other words, if we approximate a root-of-unity, and take this approximation to the $m$th power, how exacting must we be with our approximation to have error within $\epsilon$?

Note that we will use a complex value for the approximation; i.e. $\omega = a + b i$.

Matt Groff
  • 6,117
  • 2
    Since the numbers are complex you should probably be comparing the absolute value of their difference rather than the numbers themselves. – Matt Samuel Feb 06 '15 at 16:46
  • My only question is, why would you want to do that? Wouldn't it make more sense to first consider $e^{2mi\pi/n} = \cos(2m\pi/n) + i\sin(2m\pi/n)$ and then approximate? – Pedro M. Feb 06 '15 at 16:48
  • You still don't have the absolute value bars quite right; your expression is satisfied by any $\omega$ on the unit circle. You want $|(e^{2\pi i/n})^m-\omega^m|<\epsilon$. – Mario Carneiro Feb 06 '15 at 16:56
  • @PedroM.: If I could get the approximations to the $m$th power, I would. This is taken a bit out of context, and I need to take the approximations to the $m$th power. – Matt Groff Feb 06 '15 at 16:56

1 Answers1

1

This type of question is best handled using derivatives. Let $f(z)=z^m$; then from Taylor's theorem, $$f(z+\delta)=f(z)+\delta f'(z)+O(\delta^2)$$ so since $f'(z)=mz^{m-1}$, we get that an error in $z=e^{2\pi i/n}$ of size $\delta$ causes an error of size $mz^{m-1}\delta$ in $f(z+\delta)$. Since $|z|=1$, this means that $|\omega^m-z^m|\le m|\delta|+O(|\delta|^2)$, i.e. the error is magnified by $m$.

For an exact bound, we can write \begin{align} |(z+\delta)^m-z^m|&=\left|\int_0^1m\delta(z+t\delta)^{m-1}\right|\le\int_0^1m|\delta|(1+t|\delta|)^{m-1}=(1+|\delta|)^m-1. \end{align}

To find a $\delta$ such that $(1+|\delta|)^m-1<\epsilon$, we can solve to get $|\delta|<\sqrt[m]{1+\epsilon}-1$, or we can use the weaker rational upper bound $(1+|\delta|)^m-1\le\dfrac{2m|\delta|}{2-(m-1)|\delta|}$ to get $|\delta|<\dfrac{2\epsilon}{2m+(m-1)\epsilon}$.

To prove this, let $f(x)=\dfrac{2mx}{2-(m-1)x}-(1+x)^m-1$. Then $f(0)=0$, and for $0<x<\frac2{m-1}$,\begin{align} f'(x)&=\frac{4m}{2-(m-1)x}-m(1+x)^{m-1}\ge0\\ \iff4&\ge(2-mx+x)(1+x)^{m-1}=:g(x).\\ \end{align}

Taking another derivative to get $g'(x)=(m-1)(1-mx)(1+x)^{m-2}$, we find that $g(x)$ takes its maximum value at $x=\frac1m$, where the value is $g(1/m)=(1+1/m)^m<e<4$, proving the claim. Thus $|\delta|<\dfrac{2\epsilon}{2m+(m-1)\epsilon}\le\sqrt[m]{1+\epsilon}-1$ implies $|\omega^m-z^m|<\epsilon$.

Mario Carneiro
  • 27,438