uncertain orthogonality of discrete Fourier transform on the ring of integers modulo some number

Question

Update: I corresponded with one of the authors of CLRS, and he confirmed that the problem indeed should say "$n$ is a power of two", not "$n$ is even".

Original question:

The third edition of CLRS Exercise 30.2-6 claims that for any positive even $n$ and positive integer $t$, a discrete Fourier transform can be defined on the ring of integers modulo $m = 2^{tn/2} + 1$, using $w = 2^t$ as the principle $n$th root of unity.

Wikipedia seems to say that if $w$ is a principal $n$th root of unity, then for $1 \leq k < n$, we must have

$$ T_k = \sum_{j=0}^{n-1} w^{jk} = 0 \mod m $$

However, choosing $n = 6$ and $t = 3$, we have $m = 513$ and $w = 8$, and it's easy to see that $T_2 = 114 \mod m$. Isn't this supposed to be zero? If yes, where have I gone wrong above?

Answer 1

Given any $m$ and $w\in \Bbb{Z/mZ}^\times$ of order $n$, the necessary and sufficient condition for $T_0 \in \Bbb{Z/mZ}^\times$ and $T_1=\ldots=T_{n-1}=0$ is that $\gcd(n,m)=1$ and for each $k\ne 0\bmod n, w^k-1$ is a unit ie. for each prime $p| m$, $w\bmod p$ has order $n$.

• If $\gcd(n,m)\ne 1$ then $T_0$ is not a unit.

• If each $w^k-1$ is a unit then $w^{nk}-1=0$ implies $T_k=\frac{w^{kn}-1}{w^k-1}=0$.

• If $w^k-1$ is not a unit then $w^k=1\bmod p$ for some $p|m$ thus $T_k = n\ne 0 \bmod p$

• If for each prime $p| m$, $w\bmod p$ has order $n$ then each $w^k-1$ is a unit.

• If for some prime $p| m$, $w\bmod p$ has order $k<n$ then $w^k-1$ is not a unit.

It is not obvious at all for which $n,t$ the condition is satisfied with $m=2^{nt/2}+1, w=2^t$ (except when $n$ is a power of $2$, see comment below)

Answer 2

There is almost certainly an error in the CLRS claim, since $n$ being even is not sufficient, as demonstrated by the $n = 6$ counterexample.

On the other hand, $n$ being a power of two is sufficient, though it is still unclear to me whether it's necessary.

Proof (M. Pinson, private communication):

When $n = 2^\ell$, we have

$$ T_k = \frac{w^{nk} - 1}{w^k-1} = \prod_{J=0}^{\ell-1} \left( w^{2^J k} + 1\right). $$

Without loss of generality, let $k = 2^R q$ where $q$ is odd. Since $0 < k < n$, we have $0 \leq R < \ell$, and thus we examine the $J = \ell - 1 - R$ factor and see that it becomes $w^{2^{\ell - 1}q} + 1$. Since $x^q + 1$ is always divisible by $x+1$ for any odd $q$ [which can be seen by computing $\sum_{i=0}^{q-1} (-x)^i $], we know that the factor $w^{2^{\ell - 1}q} + 1$ must be divisible by $m = w^{2^{\ell - 1}} + 1$, and we are done.

Update: I corresponded with one of the authors of CLRS, and he confirmed that the problem indeed should say "$n$ is a power of two", not "$n$ is even".

Update 2 In CLRS fourth edition $n$ is now indeed "an exact power of 2" in problem 30.2-6

Answer 3

Let $m$ be a positive integer with the prime factorization $m = p_1^{d_1} p_2^{d_2} \cdots p_k^{d_k}$. A discrete Fourier transform of length $n$ is definable if $n$ divides $\boldsymbol{0}(m) := gcd(p_1 - 1, p_2 - 1, \dots, p_k - 1)$ as shown in Fast Convolution using fermat number transforms with applications to digital filtering.

Additionally, the condition for commutative rings is that the transform length $n$ must be invertible in the ring and there must exist a principal $n$-th root of unity. See Faster Integer Multiplication or Integer Multiplication in $O(n log n)$. It can be shown, with some effort, for an integer ring $\mathbb{Z}_m$, the existence of a principal $n$-th root of unity with $n$ invertible is equivalent to $n | \boldsymbol{0}(m)$.