= Cyclic convolution
{title2=$a*_k b$}
For arrays $a,b$ indexed by <integers> modulo $k$, their cyclic convolution is
$$
(a*_k b)_r=\sum_{i=0}^{k-1}a_i b_{(r-i)\bmod k}.
$$
When $a_i$ and $b_j$ count choices with respective <residue classes> $i$ and $j$, the cyclic convolution counts pairs whose sum has <residue class> $r$. Repeated cyclic convolution therefore counts sums of longer sequences. The <discrete Fourier transform> converts cyclic convolution into pointwise multiplication.
Back to article page
