Chirp Transform and Convolution 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?
 A: 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$.
