# How to prove that convolution is associative?

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*}

-
tagged it as hw. (in case it was not obvious) – user17762 Nov 22 '10 at 11:46

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.

-
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. – Qiaochu Yuan Nov 22 '10 at 15:57
@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.) – Pete L. Clark Nov 22 '10 at 16:19
ah, right. I thought the question was about l^2(Z). – Qiaochu Yuan Nov 22 '10 at 18:54

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)\$

-