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}$?


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.