Fourier Transformation on a Ring

[Albert01]

Hello,

I have a question about the FFT and would like to share my thoughts with you. The background is a problem 30.2-6 from the legendary algorithms book by Cormen.

It says that instead of doing an n element FFT over the field of complex numbers, we can use $\mathbb{Z}_m$, where $m = 2^{t \cdot n/2}$ and t is a positive integer. So we can use $\omega = 2^t$ instead of $\omega_n$ as the nth unit root modulo m.

First, we can note that all $2^t,2^{2t},...,2^{t \cdot n/2}$ are all distinct, so far clear. But how can we determine that all powers of $\omega$ are different? I found the following approach to this, which I first state and then ask my question about it: for $1 \leq k < n/2$ (why $<$ and not $\leq$ ?), $2^{kt}2^{nt/2}$ is equivalent to $-2^{kt}$ which is respectively $2^{nt/2}+1-2^{kt}$ and this is odd (why is this important?) and one conclude that all powers of $\omega$ are different (why?).

Now why does it just follow that if this is odd that the powers are different? would like to understand what this "odd" means in this context.

Thanks!

 

[fresh_42]

If $2^{it}=2^{jt}$ with, say $i<j,$ then $2^{(j-i)t}=1=2^0=2^{tn/2}$ and $0<j-i =n/2$ which is impossible.

You can find more information in
https://www.amazon.com/dp/B01M1NP1B6/?tag=pfamazon01-20

or you search the internet for the Mattson-Solomon polynomial or the discrete (or finite) Fourier transformation.

 

[Albert01]

Thanks for the answer. But I have to include a correction here because $m = 2^{t \cdot n/2}+1$ is correct.

A couple of questions on your answer.
- Why is $2^{(j-i)t}=1$ ? Simply because there must be this assignment?
- Why is $1=2^{t \cdot n/2}$ ? I don't see it that way, because modulo $m = 2^{t \cdot n/2}+1$, would result in $-1 = 2^{t \cdot n/2}$?

 

[fresh_42]

Thanks for the answer. But I have to include a correction here because $m = 2^{t \cdot n/2}+1$ is correct.

A couple of questions on your answer.
- Why is $2^{(j-i)t}=1$ ? Simply because there must be this assignment?
- Why is $1=2^{t \cdot n/2}$ ? I don't see it that way, because modulo $m = 2^{t \cdot n/2}+1$, would result in $-1 = 2^{t \cdot n/2}$?

\begin{align*}
2^{it}=2^{jt}&\Longrightarrow 2^{it}\cdot 2^{-it}=2^{jt}\cdot 2^{-it} \Longrightarrow 2^{it-it}=2^{jt-it}\Longrightarrow 2^0=1=2^{(j-i)t}
\end{align*}
Now for the second part. If we consider $\mathbb{Z}_m$ then its multiplicative group has one element, the zero, less. As it is a finite group, we get $a^{m-1}=1$ for all $a\in \mathbb{Z}_m-\{0\}.$ We get with your corrected value for $m$ that $a^{t \cdot n/2}=1.$ This is for $a=\omega=2^t,$ $\omega^{n/2} \equiv 1\pmod{m},$ so $\omega$ is the $n/2$-th root of unity as required. If $\omega^{j-i}=1$ then $(j-i)\,|\,n/2.$

My book uses a primitive root of unity for the discrete Fourier transformation, i.e. $j-i\in \{0,n/2\}$, and we are done. The authors also mention that $\omega$ can be taken as an arbitrary root of unity. In this case, I do not see either that all powers of $\omega$ are different.

Take $n=8\, , \,t=2$ and $\omega =-1.$ Then $\omega^{n/2}=(-1)^4=1$ but
$$
\{\omega^{t}\, , \,\omega^{2t}\, , \,\omega^{3t}\, , \,\omega^{tn/2}\}=\{(-1)^2\, , \,(-1)^4\, , \,(-1)^6\, , \,(-1)^8\}=\{1\}
$$
has only one element instead of four elements. $t$ and $n/2$ should either be coprime or the powers of $\omega$ do not hit all roots of unity. This problem does not occur if we simply choose the first or last root of unity different from $1.$ This would have been $\omega =\pm \,\mathrm{i}$ in the example here. So just have a look at the exponent of $e$ that is actually used.

 

[Albert01]

Thanks for the answer!

About your first line: We assume there are two distinct elements that are equal and from that we get $2^0 = 1 = 2^{(j-i)t}$, which can only be true if $j-i = 0$, which means that $j = i$. But this just means that the elements are unique, right?

In first paragraph you say because it is a finite group we get $a^{m-1} = 1$. This is a reformulation of the statement $a^m = a$, and correct because we stay in the same coset, right? But that requires a multiplicative inverse element, and in general $\mathbb{Z}_m$ is not necessarily a multiplicative group only if $gcd(a,m) = 1$ with $a \in \mathbb{Z}_m$. But because you consider $\mathbb{Z}_m$ (without proof) as multiplicative group, the statement $a^{m-1} = 1 \Leftrightarrow a^m = a$ is correct ?.

 

[fresh_42]

This is very confusing, especially the role of $m.$ And it's been a few decades since I last dealt with cyclic codes.

Do you have a link where I can see what the author actually said? My book uses a slightly different notation and I get more and more confused. E.g. shouldn't $m$ be a length? Instead, you take it as the total number of elements, but of what? The group (with $\omega$ in it), the field (the alphabet for the code), or the vector space (for the code words)?

 

[Albert01]

Hello,

these comments were actually more related to your previous post #4. I actually just wanted to know if I have understood this correctly so far:

$\begin{align*} 2^{it}=2^{jt}&\Longrightarrow 2^{it}\cdot 2^{-it}=2^{jt}\cdot 2^{-it} \Longrightarrow 2^{it-it}=2^{jt-it}\Longrightarrow 2^0=1=2^{(j-i)t} \end{align*}$

1.) If two different elements are equal $2^{it} = 2^{jt} \Rightarrow 2^0 = 1 = 2^{(j-i)t}$, that can only be correct if $j-i = 0$ which means that $j = i$. But in consequence this means that the elements are unique. With this you show the uniqueness so to speak, don't you? If I understand this correctly.

---

The second part of my question was really just about how you came up with $a^{m-1}=1$ (for me that was very quick, I don't see it right away) in post #4.

---

I don't know if I'm allowed to publish the link of the book "Introduction to Algorithms" by Cormen et. al here so freely. But with a Google search you can find the PDF there it is in the 4th edition on page 893 task 30.2-6.

 

[fresh_42]

Hello,

these comments were actually more related to your previous post #4.

Yes, but this depends on my understanding which I'm not sure I got it right.

I actually just wanted to know if I have understood this correctly so far:

$\begin{align*} 2^{it}=2^{jt}&\Longrightarrow 2^{it}\cdot 2^{-it}=2^{jt}\cdot 2^{-it} \Longrightarrow 2^{it-it}=2^{jt-it}\Longrightarrow 2^0=1=2^{(j-i)t} \end{align*}$

If we have the finite cyclic multiplicative group $\mathbb{Z}_m-\{0\}$ then $a^{m-1}=1$ for all elements $a\in \mathbb{Z}_m-\{0\}.$ If $a^{(j-i)t}=1$ then $((j-i)t)\,|\,(m-1)$ by Lagrange's theorem.

Here it is crucial what $t\, , \,m$ and $n/2$ actually are! I think that $\omega =2^t$ should be an element of $\mathbb{Z}_{2^{n/2}}-\{0\},$ a primitive $n/2$-the root of unity. Primitive means that it generates the multiplicative group so that all powers $\omega^0,\ldots,\omega^{-1+n/2}$ are different. Otherwise, see my example, we do not get all $n/2$ many roots. If $t$ and $n/2$ are coprime, then $2^{(j-i)t}=1$ so $(j-i)t=0$ or $(j-i)t=n/2$ depending on whether you count from $0$ to $-1+n/2$ or from $1$ to $n/2.$ Now, if $t$ and $n/2$ are coprime, then $i-j=0$ or $i-j=n/2,$ again depending on where you start to count. In either case, we get $j=i.$ But if $t$ and $n/2$ are not coprime, then we won't get all roots (see the example with $\omega =-1.$)

1.) If two different elements are equal $2^{it} = 2^{jt} \Rightarrow 2^0 = 1 = 2^{(j-i)t}$, that can only be correct if $j-i = 0$ which means that $j = i$. But in consequence this means that the elements are unique. With this you show the uniqueness so to speak, don't you? If I understand this correctly.

---

The second part of my question was really just about how you came up with $a^{m-1}=1$ (for me that was very quick, I don't see it right away).

---

This is Lagrange's theorem.
https://en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory)

It implies that $a^{|G|}=1.$ If $m$ is a power of two and the group $G$ is the multiplicative group of field with $m$ elements, then $|G|=|\mathbb{Z}_m-\{0\}|=m-1$ and $a^{m-1}=1.$

This is why I think that $m=2^{n/2}.$ This would be the alphabet of the code/message/signal, whatever you use.

 

[fresh_42]

Your answer is: The powers of $\omega$ are different because we start with a primitive root of unity. $\omega =e^{2\pi i/n}$ is the first of the $n$ many roots after $1$ if we circle the unit circle counterclockwise. It is called the principal root which is a primitive root since the power $1$ is automatically coprime to $n.$ Here we count from $0$ to $n-1.$
$$
R=\{\underbrace{\omega^0 }_{=1}\, , \,\underbrace{\omega^1 }_{=\text{principal root}}\, , \,\ldots\, , \,\omega^{n-1}\}
$$
$\omega^n=1$ again.

 

[fresh_42]

@Albert01 Here is my final answer:

As to 30.2-6 we have $m=2^{tn/2}+1$ for an even $n\, , \,\omega =2^t$ instead of $e^{2\pi i /n},$ and $t>0.$

1.) $\omega^n=2^{tn}=(m-1)^2=m^2-2m+1 \equiv 1 \pmod{m},$ so $\omega$ is an $n$-th root of unity modulo $m.$

2.) Say $\omega^i=\omega^j$ for $0\leq i<j <n.$ Then
\begin{align*}
2^{t(j-i)}-1&\equiv 0\pmod{m}\\
(2^{tn/2}+1)\,&|\,(2^{t(j-i)}-1)\\
(2^{tn/2}+1)\cdot q &=2^{t(j-i)}-1\\
(2^{tn/2}+1)\cdot (2k-1) &=2^{t(j-i)}-1\\
(2k-1)\cdot 2^{tn/2}+2k&=2^{t(j-i)}\\
2^{j-i}&=(2k-1)2^{n/2}+\dfrac{2k}{2^t}
\end{align*}
If $k=0$ then $2^{j-i}+2^{n/2}=0$ which is not possible. If $k\neq 0$ then $2^{t-1}\,|\,k,$ say $k=2^{t-1}r_0$ so $2^{j-i}=2^{t+n/2}r_0-2^{n/2}+r_0$ and $r_0=2r_1$ is even. Thus
\begin{align*}
2^{j-i}&=2^{t+n/2}r_0-2^{n/2}+r_0\\
2^{j-i-1}&=2^{t+n/2}r_1-2^{-1+n/2}+r_1\\
\ldots &=\ldots\\
1&=2^{(j-i)-(j-i)}=2^{t+n/2}r_{j-i}-2^{-(j-i)+n/2}+r_{j-i}\\
r_{j-i}&=1\\
2^{t+n/2}&=2^{-(j-i)+n/2}\\
t&=i-j
\end{align*}
which is impossible since $t>0.$ Therefore $j=i.$

(I hope I made no sign error again.)

 

[Albert01]

@fresh_42 Thank you for your wonderful response, I really appreciate it! I will now take the time to look into this in detail!

One question: You mentioned a book "The Mathematical Theory of Coding" by Mullin, is this still your reference? Unfortunately, I can only see the table of contents, and I don't see a chapter on the Fourier transform?!

 

[fresh_42]

@fresh_42 Thank you for your wonderful response, I really appreciate it! I will now take the time to look into this in detail!

One question: You mentioned a book "The Mathematical Theory of Coding" by Mullin, is this still your reference? Unfortunately, I can only see the table of contents, and I don't see a chapter on the Fourier transform?!

Your book is fine!

I just mentioned the one that my book mentioned. The chapter on DFT is quite short in my book so they referred to Blake & Mullin. You can get the mathematical background cheaper from lecture notes of one of the thousand universities on the globe. Just google "discrete mathematics + pdf".