# Positional Encoding and Fourier transforms

While I was studying Positional Encoding, I came across an article that links coding resolution to Fourier transforms: "For anyone who has studied finite Fourier transforms, this problem should be familiar. Only half of the frequencies are unique. " However, even if I have explored this topic, I do not find the connection with the Fourier transform, in particular the reference to the fact that only half of the frequencies must be unique. Can anyone help me?

I think the statement "Only half of the frequencies are unique" refers to the aliasing and the time series being real for a discrete Fourier transform. The discrete Fourier transform (DFT) is defined as $$X_k = \sum_{n=0}^{N-1}x_n\exp\left(-i\frac{2\pi}{N}kn\right).$$ You can see that $$X_{k + N} = X_k$$. As \begin{aligned} X_{k+N} &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi\frac{(k+N)n}{N}\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N} - i2\pi \frac{N}{N}\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N} - i2\pi\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N}\right)\exp\left(- i2\pi\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N}\right)\\ &= X_k \end{aligned} This "feature" is called aliasing. Because of that only for $$k \in [-N / 2, N/2 - 1]$$ (assuming $$N$$ is even), $$X_k$$ are unique. And if the series to be transformed $$x_n$$ is real ($$x_n^* = x_n$$), then \begin{aligned} X_{-k} &=\sum_{n=0}^{N-1}x_n\exp\left(-i\frac{2\pi}{N}(-k)n\right)\\ &=\sum_{n=0}^{N-1}x_n\exp\left(i\frac{2\pi}{N}kn\right)\\ &=\sum_{n=0}^{N-1}\left[x^*_n\exp\left(-i\frac{2\pi}{N}kn\right)\right]^*\\ &=\sum_{n=0}^{N-1}\left[x_n\exp\left(-i\frac{2\pi}{N}kn\right)\right]^*\\ &=X^*_k, \end{aligned} where $$^*$$ refers to complex conjugate. Resulting in only half of the frequencies' $$X_k$$ being unique.
• How can i see that $X_ {k + N} = X_k$? Commented Mar 18, 2022 at 18:30
• As adding $N$ is the same as shifting the phase by $2\pi$, the value does not change ($\exp(i2\pi) = 1$), in details: $X_{k+N} = \sum_{n=0}^{N-1}x_n\exp(-i2\pi(k+N)n/N) = \sum_{n=0}^{N-1}x_n\exp(-i2\pi kn/N - i2\pi N/N) = \sum_{n=0}^{N-1}x_n\exp(-i2\pi kn/N - i2\pi) = \sum_{n=0}^{N-1}x_n\exp(-i2\pi kn/N) = X_k$. Let me also add this to the answer. Commented Mar 18, 2022 at 18:36
• your answer is really perfect, $$exp \ left (- i2 \ pi \ right) \\$$ is it 1 for Euler's identity (practically it is the square)? Commented Mar 18, 2022 at 18:52
• There are a few different ways to look at it, the easiest way would be $\exp(i2\pi) = \cos(2\pi) - i\sin(2\pi) = 1$. Or if you understood $\exp(i\theta)$ as a rotational on the complex plane, rotate by $2\pi$ obviously give you $1$. Glad that my answer helps; please consider accepting my answer. Commented Mar 18, 2022 at 18:56