TAOCP 4.3.3 Exercise 9

Let $k$ be the length of the discrete Fourier transform and let $\omega = e^{2\pi i / k}$ be a primitive $k$th root of unity.

taocpmathematicsalgorithmsvolume-2math-simple

Section 4.3.3: How Fast Can We Multiply?

Exercise 9. [M15] Suppose the Fourier transformation method of the text is applied with all occurrences of $\omega$ replaced by $\omega^q$, where $q$ is some fixed integer. Find a simple relation between the numbers $(\hat{u}_0, \hat{u}1, \ldots, \hat{u}{k-1})$ obtained by this general procedure and the numbers $(\hat{u}_0, \hat{u}1, \ldots, \hat{u}{k-1})$ obtained when $q = 1$.

Verified: yes
Solve time: 4m51s

Solution

Let $k$ be the length of the discrete Fourier transform and let $\omega = e^{2\pi i / k}$ be a primitive $k$th root of unity. The ordinary Fourier transform of a sequence $(u_0, u_1, \ldots, u_{k-1})$ is defined by

$\hat{u}j = \sum{m=0}^{k-1} u_m , \omega^{jm}, \qquad j = 0, 1, \ldots, k-1. \eqno(1)$

Now consider the modified procedure in which $\omega$ is replaced by $\omega^q$ for a fixed integer $q$. Denote the resulting transform by $(\hat{u}_0^{(q)}, \hat{u}1^{(q)}, \ldots, \hat{u}{k-1}^{(q)})$, so that

$\hat{u}j^{(q)} = \sum{m=0}^{k-1} u_m , (\omega^q)^{jm} = \sum_{m=0}^{k-1} u_m , \omega^{qjm}, \qquad j = 0, 1, \ldots, k-1. \eqno(2)$

We wish to relate $\hat{u}_j^{(q)}$ to the original transform $\hat{u}_j$ defined in (1).

Observe that raising $\omega$ to the power $qj$ is equivalent to evaluating the original Fourier transform at index $qj \pmod{k}$. More precisely, the mapping

$j \mapsto qj \pmod{k}$

induces a permutation of the set ${0, 1, \ldots, k-1}$ if and only if $\gcd(q,k) = 1$. Under this assumption, we have

$\hat{u}j^{(q)} = \sum{m=0}^{k-1} u_m , \omega^{(qj)m} = \hat{u}_{qj \bmod k}. \eqno(3)$

Hence each component of the modified transform is simply a reordering of the components of the original transform: the $j$th component of the $q$-powered transform equals the $(qj \bmod k)$th component of the standard transform.

If $\gcd(q,k) > 1$, then some indices are repeated modulo $k$ and others are skipped, so the mapping $j \mapsto qj \pmod{k}$ is no longer a permutation. In that case, multiple entries of $(\hat{u}_0, \hat{u}1, \ldots, \hat{u}{k-1})$ are summed together in $\hat{u}_j^{(q)}$, yielding a coarser transform. In the common case of $q$ coprime to $k$, the relation (3) fully describes the effect of replacing $\omega$ by $\omega^q$.

This completes the solution.

∎