I was reading about the discrete fourier transform from the CLR algorithms book and I came upon an exercise whose hint confuses me. The exercise reads as follows:
The chirp transform of a vector $a=(a_0,a_1,\ldots,a_n)$ is a vector $y=(y_0,y_1,\ldots,y_n)$, where $y_k=\sum_{j=0}^{n-1}a_j (z^{k})^j$ and $z$ is any complex number. The DFT is therefore a special case of the chirp transform, obtained by taking $z=\omega_n$. Prove that the chirp transform can be evaluated in time $O(n\lg n)$ for any complex number $z$. (Hint: use the equation $y_k = z^{k^2/2}\sum_{j=0}^{n-1}(a_j z^{j^2/2})(z^{-(k-j)^2/2})$ to view the chirp transform as a convolution.
My question is about what is a convolution. I am familiar with taking two vectors $a=(a_0,a_1,\ldots,a_n)$ and $b=(b_0,b_1,\ldots,b_n)$ and forming the convolution $c=(c_0,c_1,\ldots,c_n)$ where $c_k = \sum_{j=0}^k a_j b_{k-j}$. Here the index of $j$ runs from $0$ to $k$ unlike in the hint given above where the index runs from $0$ to $n-1$. In what sense is the hint above a convolution?