0
$\begingroup$

How to prove that convolution is associative, that is $(x*y)*z = x*(y*z)$, for $x,y,z \in l^2(Z_N)$. Either directly from the definition of convolution( Definition of convolution: For $z,w \in l^2(Z_N)$, the convolution $z*w \in l^2(Z_N)$ is the vector with components $z*w(m) = \sum_{n=0}^{N-1} z(m-n)w(n)$ ) or using following lemma:Suppose $z,w \in l^2(Z_N)$. Then for each m, $(z*w)\hat{}(m) = \hat{z(m)}\hat{w(m)}$( where ^ is discrete fourier transform $\sum_{n=0}^{N-1} z(n)e^{-2 \pi i m n/N}$) and also Fourier inversion formula: $z(n) = 1/N \sum_{m=0}^{N-1} \hat{z(m)} e^{2 \pi i m n/N}$, for $n=0,1,\dots, N-1$. In my solution I have used lemma above and Fourier inversion formula as following: \begin{align*} (x*y)*z(n) &= \frac{1}{N} \sum_{m=0}^{N-1} ((x*y)*z)\widehat{(m)}e^{2 \pi i m n/N}\\ &= \frac{1}{N} \sum_{m=0}^{N-1} (x*y)\widehat{(m)}*\widehat{z(m)}e^{2 \pi i m n/N}\\ &= \frac{1}{N} \sum_{m=0}^{N-1} \widehat{x(m)}\widehat{y(m)}\widehat{z(m)}e^{2 \pi i m n/N} \\ &= \frac{1}{N} \sum_{m=0}^{N-1} \widehat{x(m)}(y*z)\widehat{(m)}e^{2 \pi i m n/N}\\ &= \frac{1}{N} \sum_{m=0}^{N-1} (x*(y*z))\widehat{(m)}e^{2 \pi i m n/N}\\ &= x*(y*z). \end{align*}

  • 1
    tagged it as hw. (in case it was not obvious)2010-11-22

2 Answers 2

5

This (very standard) computation is done in more generality on Proposition 46, p. 41 of

http://math.uga.edu/~pete/integral.pdf

The OP is asking for the special case in which the algebra $R$ is $\mathbb{C}$ and the semigroup $M$ is the (group) $(\mathbb{Z}/N\mathbb{Z},+)$.

Of course use of the language of algebras and semigroups is overkill for this particular special case. But if you look at the three lines of computation in the middle of the page, you see that the point is just to expand each of $(x*y)*z$ and $x*(y*z)$ into a triple sum and then notice that these two triple sums are identical.

In other words, just do it: it sounds harder than it actually is.

  • 0
    Right. In particular you don't need to know anything about the Fourier transform to do this computation. Morally it follows from the special case of functions with finite support.2010-11-22
  • 0
    @Qiaochu: unless I am misinterpreting the notation, we are talking about the *discrete* Fourier transform on a finite abelian group, so all functions have finite support. (But I agree that the proofs in other cases, like the Fourier transform on $\mathbb{R}^n$, are quite similar.)2010-11-22
  • 0
    ah, right. I thought the question was about l^2(Z).2010-11-22
2

HINT $\ $ Put $\rm\ \hat f = \sum_{i=0}^{N-1} \:f(i)\: X^i\ $ and note $\rm\ \hat f \:(\hat g\: \hat h) \equiv (\hat f\: \hat g)\:\hat h\ \ (mod\:\ X^N - 1)\ $