4
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – user713585
    Jan 20, 2022 at 14:36
  • $\begingroup$ 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. $\endgroup$
    – TheSimpliFire
    Jan 20, 2022 at 14:47
  • $\begingroup$ 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}$? $\endgroup$
    – user713585
    Jan 20, 2022 at 15:30
  • $\begingroup$ 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. $\endgroup$
    – TheSimpliFire
    Jan 20, 2022 at 15:54

You must log in to answer this question.