# Fourier transform on $\mathbb{Z}_{2}^{d}$

Let $$\mathbb{Z}_{2}^{d} = {\{\textbf{t} = (t_1, \ldots, t_d) : t_j \in \mathbb{Z}_2}\}$$.

Define the inner product on functions $$f, g : \mathbb{Z}_{2}^{d} \rightarrow \mathbb{C}$$ to be: $$\langle f, g \rangle = \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}} f(\textbf{t}) \overline{g(\textbf{t})}.$$

Let $$f : \mathbb{Z}_{2}^{d} \rightarrow \mathbb{C}$$. Define the fourier transform of $$f$$ at $$\textbf{k} \in \ \mathbb{Z}_{2}^{d}$$ to be: $$\widehat{f}(\textbf{k}) = \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}} f(\textbf{t})(-1)^{\textbf{k} \cdot \textbf{t}}$$ where $$\textbf{k} \cdot \textbf{t} = k_1 t_1 + \ldots + k_d t_d$$.

Now, I am trying to relate $$\langle f,g \rangle$$ and $$\langle \widehat{f}, \widehat{g} \rangle$$, where $$\langle \cdot , \cdot \rangle$$ denotes the inner product of functions $$f, g : \mathbb{Z}_{2}^{d} \rightarrow \mathbb{C}$$.

I started with $$\langle \widehat{f}, \widehat{g} \rangle = \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}} \widehat{f}(\textbf{t}) \overline{\widehat{g(\textbf{t})}} = \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}} \sum_{\textbf{s} \in \mathbb{Z}_{2}^{d}}f(\textbf{s})(-1)^{\textbf{t} \cdot \textbf{s}} \sum_{\textbf{r} \in \mathbb{Z}_{2}^{d}}\overline{g(\textbf{r})}(-1)^{\textbf{t} \cdot \textbf{r}}$$ which after swapping summations, gives $$\langle \widehat{f}, \widehat{g} \rangle = \sum_{\textbf{s} \in \mathbb{Z}_{2}^{d}} f(\textbf{s}) \sum_{\textbf{r} \in \mathbb{Z}_{2}^{d}}\overline{{g(\textbf{r})}} \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}}(-1)^{\textbf{t}\cdot(\textbf{s} + \textbf{r})}.$$ Now, when $$\textbf{s} = \textbf{r}$$, we get that $$\sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}}(-1)^{\textbf{t}\cdot(\textbf{s} + \textbf{r})} = \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}}(-1)^{0} = \sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}}1 = 2^d$$ and hence that $$\langle \widehat{f}, \widehat{g} \rangle = 2^d \langle f, g \rangle.$$

What about when $$\textbf{s} \neq \textbf{r}$$? What can be said about the sum $$\sum_{\textbf{t} \in \mathbb{Z}_{2}^{d}}(-1)^{\textbf{t}\cdot(\textbf{s} + \textbf{r})}$$ when $$\textbf{s} \neq \textbf{r} \in \mathbb{Z}_{2}^{d}$$?

## 1 Answer

The last sum in your question is $$0$$, namely if $$r, s \in \mathbb{Z}^d_2$$ with $$r\neq s$$ then $$\tag{1} S:= \sum\limits_{t \in \mathbb{Z}_2^d } (-1)^{t\cdot (r+ s)} = 0.$$ Indeed, assume there are exactly $$1\leq k \leq d$$ different bits in $$s$$ and $$r$$. WLOG, we may assume these $$k$$ bits are the first $$k$$, since otherwise we can simply rearrange the coordinates without changing the sum in $$(1)$$. Thus, $$s_i \neq t_i$$ for $$i = 1,...,k$$ and $$s_i = t_i$$ for $$i = k+1,...,d$$. We get $$s_i + r_i = 1$$ when $$i = 1,...,k$$ and $$s_i + r_i \in \{0, 2\}$$ for $$i=k+1,...,d$$, hence $$S = \sum\limits_{t\in \mathbb{Z}_2^d}(-1)^{ t_1 +...+t_k }.$$ Now pair each $$(t_1,...,t_k)\in \mathbb{Z}_2^k$$ with $$(1 - t_1,...,t_k)\in \mathbb{Z}_2^k$$. Since both vectors are present in the sum for $$S$$ and have opposite signs, they cancel each other leaving $$S = 0$$.