The more common Fourier transform is here

Consider a Hamming space \(Q^n\). Let \(q=\#Q\) and identify \(Q = \mathbb{Z}/q\mathbb{Z}\).

Consider the \(\mathbb{C}\)-vector space \(H=\mathop{\mathrm{Maps}}(Q^n, \mathbb{C})\) and define the Fourier transform map

\[\begin{align} \mathcal{F}: H \rightarrow & \ H \\ f \mapsto & \ \mathcal{F}(f),\qquad \mathcal{F}(f)(x) = \sum_{ y \in {Q}^n} f(y) \zeta^{\langle x , y\rangle}. \label{eq:defi_of_complex_fourier} \end{align}\] Here \(\zeta = \exp(2\pi i /q)\) and \(\langle x, y\rangle\) is the sum \(\sum_{1\le i \le n}^{} x_i y_i\), where \(x=(x_1,x_2, \dots , x_n)\) and \(y = (y_1, y_2 ,\dots ,y_n)\).

Properties

Inversion

For \(f \in H\), we have \(\mathcal{F} \circ \mathcal{F}(f) (z) = q^n f(-z)\). So, to invert this Fourier transform, one needs to divide by \(q^n\) apart from negating the argument.

Radial functions

A small consequence of this definition is that radial functions (i.e. functions depending only on the weight) go to radial functions under the above notion of Fourier transform.

We also have an an analogous radial transformation formula, just like in the usual Fourier transform. If \(f:Q^n \to \mathbb{C}\) is a radial function, then \(\mathcal{F}(f)=\hat{f}\), as a function of weight \(t\), can be written as

\[\begin{align} \hat{f}(t) = \sum_{k=0}^{n} f(k) K_k(t), \end{align}\] where \(K_k\) are Kravchuk polynomials. Here \(f\) is also written as a function of the weight \(k\).

Convolution theorem

On the vector space \(H = \mathop{\mathrm{Maps}}(Q^n, \mathbb{C})\), there are two possible products that make \(H\) a commutative associative \(\mathbb{C}\)-algebra. For \(f,g \in H\), we define

1. \[\begin{equation}\label{eq:conv} f *g := z \mapsto \sum_{x+y=z}^{} f(x)g(y)\end{equation}\] which is the convolution product,
2. \[ fg : = z \mapsto f(z)g(z)\] which is the pointwise product.

In the first case, the unit is the indicator function at \(0 \in Q^n\) and for the second, the unit is the constant function \(1 \in {H}\). One can show that the Fourier transform is a \(\mathbb{C}\)-algebra isomorphism that takes the convolution product to the pointwise product. This well-known fact is called the convolution theorem.

Parseval identity

If \(\langle \ , \ \rangle_H\) is the standard inner product on \(H\), the identity \(\langle \mathcal{F}(f_1) , f_2\rangle_H = \langle f_1 , \mathcal{F}(f_2)\rangle_H\) can be easily verified. This identity is often called the Parseval identity in harmonic analysis.

Linear programming bound

See here