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?
Convolution and the Discrete Fourier Transform:
Suppose $(a_0, a_1, \ldots, a_{n-1})$ and $(b_0, b_1, \ldots, b_{n-1})$ denote two complex-valued sequences of length $n$, and let $a(z)=\sum_k a_kz^k$ and $b(z)=\sum_k b_kz^k$ denote the corresponding polynomials of degree $< n$.
The linear or aperiodic convolution of the two sequences is defined as the sequence $(c_0, c_1, \ldots, c_{2n-2})$ of length $2n-1$ where $$c_k = \begin{cases}\sum_{j=0}^k a_jb_{k-j}, &0 \leq k \leq n-1\\ \sum_{j=k-(n-1)}^{n-1} a_jb_{k-j}, &n \leq k \leq 2n-2. \end{cases}$$ and the corresponding polynomial $c(z) = \sum_k c_kz^k$ of degree $< 2n-1$ equals $a(z)b(z)$.
The circular or cyclic or periodic convolution of the two sequences is defined as the sequence $(d_0, d_1, \ldots, d_{n-1})$ of length $n$ where $$d_k = \sum_{j=0}^{n-1}a_jb_{(k-j) \bmod ~n}, ~0 \leq k \leq n-1.$$ Note that $$d_k = \begin{cases}c_k + c_{k+n}, &0 \leq k \leq n-2,\\ c_{n-1}, & k = n-1, \end{cases}$$ and the corresponding polynomial $d(z) = \sum_k d_k z^k$ of degree $< n$ equals $a(z)b(z) \bmod (z^n - 1)$ where for future reference we write this as $a(z)b(z) = q(z)(z^n-1) + d(z)$.
Let $\omega = \exp(i2\pi/n)$ denote a complex $n$-th root of unity. The Discrete Fourier Transform (DFT) of $(a_0, a_1, \ldots, a_{n-1})$ is $(A_0, A_1, \ldots, A_{n-1})$ where $$A_k = \sum_{j=0}^{n-1} a_j \omega^{-jk} = a(\omega^{-k}), ~ 0 \leq k \leq n-1.$$ The inverse DFT of $(A_0, A_1, \ldots, A_{n-1})$ is $$a_k = \frac{1}{n}\sum_{j=0}^{n-1} A_j \omega^{jk} = \frac{1}{n}A(\omega^{k}), ~ 0 \leq k \leq n-1.$$ The inverse DFT of $(A_0B_0, A_1B_1, \ldots, A_{n-1}B_{n-1})$, the term-by-term product of the DFTs of $(a_0, a_1, \ldots, a_{n-1})$ and $(b_0, b_1, \ldots, b_{n-1})$, is $(d_0, d_1, \ldots, d_{n-1})$, the periodic convolution of the two sequences, not the aperiodic convolution. An informal proof of this is that $A_kB_k = a(\omega^{-k})b(\omega^{-k})$ are the values of $a(z)b(z)$ at the $n$-th roots of unity. Since $a(z)b(z) = q(z)(z^n-1) + d(z)$, we know the values of $d(z)$ at the $n$ $n$-th roots of unity, and thus $d(z)$ of degree $< n$ must be the unique polynomial of degree $< n$ that interpolates through these $n$ points.
Chirp signals: The OP asks in what sense $$\sum_{j=0}^{n-1}(a_j z^{j^2/2})(z^{-(k-j)^2/2})$$ can be considered a convolution? With $\hat{a}_j = a_jz^{j^2/2}$ and $b_j = z^{-j^2/2}$, this is very much like a cyclic convolution $$d_k = \sum_{j=0}^{n-1}\hat{a_j}b_{(k-j) \bmod ~n}, ~0 \leq k \leq n-1$$ and is a cyclic convolution if $z^{n^2/2} = 1$.