We have to arrays $a$ and $b$, and the convolution operation in the discrete case is defined as: $$ (a \star b)_i = \sum_{j = 0}^{N} a_j b_{i - j} $$ And the naive approach to the computation would take $\mathcal{O}(N^2)$. The better approach is known, and via FFT (Fast Fourier transform) one can achieve a complexity of $\mathcal{O}(N \log N)$ : $$ (a \star b) = \mathcal{F}^{-1} (\mathcal{F}(a) \cdot \mathcal{F}(b)) $$ where $\mathcal{F}(a)$ is a discrete Fourier transform of $a$: $$ \mathcal{F}(a) = \sum_{n = 0}^{N-1} a_n e^{-\frac{2\pi i k n}{N}} $$ But in fact both $a, b$ and the result $a \star b$ have $\mathcal{O}(N)$.
My question is : can one do better, at least in principle? Maybe no one has come with a better idea so far, but it may the case some bright mind came up with even a faster algorithm, or it can be proven, that this $\mathcal{O}(N \log N)$ is in fact the best one can achieve?