The unnormalised cyclic convolution on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$

Let $N\ge 1$ and let ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ be the complex vector space of functions on the finite group $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (The vector space $F^X$ of all functions $X\to F$ with pointwise operations, and $F^n$ as the case $X=n=\{0,1,\dots ,n-1\}$). For $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ the cyclic convolution of $f$ and $g$, unnormalised, is the function $f\ast g:\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$ defined for $x\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$ by

$(f\ast g)(x):={\sum }_{y\in \mathbb{Z}\mathrm{/}N}f(y)g(x-y),$

where $x-y$ is the group operation of $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold) and the sum is the finite sum in the additive commutative monoid of $\mathbb{C}$ over the finite index set $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (A finite sum in a commutative monoid indexed by an arbitrary finite set). No factor $1\mathrm{/}N$ or $1\mathrm{/}\sqrt{N}$ is inserted, and this unnormalised convention is the one used throughout the page.

Well-definedness. The standard-representatives bijection gives $\mathrm{\mid }\mathbb{Z}\mathrm{/}N\mathbb{Z}\mathrm{\mid }=N$ (For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$). For fixed $x$, $f(y)$ and $g(x-y)$ are values at classes, so the finite sum of the complex family $y\mapsto f(y)g(x-y)$ is a single complex number (A finite sum in a commutative monoid indexed by an arbitrary finite set). Thus $x\mapsto (f\ast g)(x)$ is a well-defined function $\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$.

The operation is commutative. Fix $x\in \mathbb{Z}\mathrm{/}N\mathbb{Z}$ and let $h:\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{Z}\mathrm{/}N\mathbb{Z}$ be $h(y):=x-y$; then $h(h(y))=x-(x-y)=y$, so $h$ is its own two-sided inverse and hence a bijection (Injection, surjection, bijection, For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold). Reindexing the finite sum along a bijection (Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule, part 1) with the substitution $z:=x-y$ gives

$(f\ast g)(x)={\sum }_{y\in \mathbb{Z}\mathrm{/}N}f(y)g(x-y)={\sum }_{z\in \mathbb{Z}\mathrm{/}N}f(x-z)g(z)={\sum }_{z\in \mathbb{Z}\mathrm{/}N}g(z)f(x-z)=(g\ast f)(x),$

the middle equality being commutativity of multiplication in $\mathbb{C}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$). Hence $f\ast g=g\ast f$.

Attached to the finite set $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ is its counting set function, which gives weight $1$ to each point (Counting measure on an arbitrary set); the displayed sum is the convolution of $f$ and $g$ against that weight on the finite group. This cyclic convolution is a different operation from the linear convolution of finite sequences of coefficients, which agrees with it only after the sequences are padded with enough zeros; the companion page exhibits the wrap that occurs without such padding, and the transform law proved later on this page computes the cyclic, not the linear, convolution.

• The factor that this convention costs. Because no normalisation is built into $\ast$, the unitary transform of this page does not turn $\ast$ into an unadorned pointwise product: the transform law later on this page carries a factor $\sqrt{N}$. That factor is not an artefact of the proof but the exact price of leaving the convolution unnormalised, and it is recorded here once so that no later item silently mixes the two conventions.

• Cyclic convolution as reduction of polynomial products. Writing a function on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ as the coefficient list of a residue-class polynomial identifies $(f\ast g)(x)$ with the coefficient of $z^x$ in the product of the two polynomials taken modulo $z^N-1$: exponents add under the group operation and are reduced modulo $N$. This is the viewpoint of Taylor's (11.30)–(11.33) and of the MIT lecture, and it is what makes the diagonalisation of $\ast$ by the discrete Fourier transform the discrete analogue of the Fourier-multiplier calculus.