# About Fourier transform of a probability measure on $\mathbb{Z}_2^d$

I am reading a paper by Diaconis and Graham and in page 219, in equation 2.5, Fourier transform of a probability measure $$Q$$ on $$\mathbb{Z}^d_2$$ is defined as:

For $$y\in \mathbb{Z}^d_2$$, the Fourier transform of $$Q$$ at $$y$$ is defined by:

$$\hat{Q}(y) = \sum_{x\in \mathbb{Z}_2^d} (-1)^{y^t x}Q(x)$$

where $$x^ty$$ is a dot product of the vectors $$x,y$$ and here the dot product is taken mod $$2$$.

May I know why the Fourier transform is defined this way? Let's say $$Q$$ is a probability measure on $$\mathbb{Z}_k^d$$, $$k>2$$ is an integer, then would the Fourier transform be defined the same way where we sum over $$x\in \mathbb{Z}^d_k$$ and the dot product is taken mod $$k$$?

I know that the Fourier transform of a probability measure generally is $$\hat{Q}(y)=\int e^{iyx}dQ(x)$$ but because the state space is $$\mathbb{Z}^d_2$$, somehow $$e^{iyx}$$ translates to $$(-1)^{y^tx}$$ which is don't understand?

## 1 Answer

In general, the Fourier transform of $$Q$$ at an element $$\boldsymbol y\in(\Bbb Z/n\Bbb Z)^d$$ is $$\widehat Q(\boldsymbol y)=\sum_{\boldsymbol x\in(\Bbb Z/n\Bbb Z)^d}Q(\boldsymbol x)\overline{\chi_{\boldsymbol y}(\boldsymbol x)}=\sum_{\boldsymbol x\in(\Bbb Z/n\Bbb Z)^d}Q(\boldsymbol x)e^{-2\pi i\boldsymbol x\cdot \boldsymbol y/n}$$ as defined in the Fourier transform on finite groups. The case $$n=2$$ gives us $$\chi_{\boldsymbol y}(\boldsymbol x)=(-1)^{\boldsymbol x\cdot \boldsymbol y}$$.

Here we simply have the root of unity transformation (character) $$\overline\chi_{\boldsymbol y}$$ which trivially satisfies $$\varrho:(\Bbb Z/n\Bbb Z)^d\to\operatorname{GL}(1,\Bbb C)$$, and is a group homomorphism (see the section on finite abelian groups).

• Thanks. I am not familiar with representation theory. I don't understand what $\bar{\chi}$ is. I know that it has to be a representation of the form $\varrho:(\Bbb Z/n\Bbb Z)^d\to\operatorname{GL}(1,\Bbb C)$. But I am not sure why the "root of unity transformation $\bar{\chi}$" means $\bar{\chi}(x)=e^{-2\pi ix\cdot y/n}$? Also, any details on why $\bar{\chi}$ satisfies that representation would be appreciated!
– user713585
Jan 20, 2022 at 14:36
• The reason is that $\Bbb Z/n\Bbb Z$ can be corresponded with the set of $n$th roots of unity; that is, through the map $[k]\to e^{2\pi ik/n}$ (and indeed, this is the most natural choice of isomorphism). When we take Fourier transforms, the roots of unity expression is conjugated, just like in DFT. Jan 20, 2022 at 14:47
• Sorry, is $\chi(x)=e^{2\pi ix/n}$ where $x\in \mathbb{Z}_n$? If that is the case, then for $n=2$, $\chi(x)=(-1)^x$. So I'm not sure how we got $\chi(x)=(-1)^{x\cdot y}$?
– user713585
Jan 20, 2022 at 15:30
• I've made it clearer now that we are talking about $\chi_y(x)=e^{2\pi ixy/n}$, which is called a character. See Proposition 1.3 of this paper (and the next couple of pages) for a more detailed explanation. Jan 20, 2022 at 15:54