Exact integer convolution from approximate DFTs (Harvey–van der Hoeven §5.3)

Let $s_i<t_i$ be coprime for $i<d$ with $s_i\le\alpha^2(t_i-s_i)$, $\alpha\ge2$, and let $p$ satisfy the precision conditions of Theorem 4.1 (thm_4_1_fp). Let $F_t$ be any fixed-point oracle for the normalised DFT $\mathcal F_t$ on the box $\prod_i[0,t_i)$ (dftBox): for inputs in the disc of radius $2^p$ its in-box outputs lie in the disc and are within $\varepsilon_F$ of $2^p\mathcal F_t(2^{-p}U)$. Let $u,v$ be integer arrays with $|u_x|,|v_x|<2^b$, $b\le p$.

The algorithm exactConv scales $u,v$ to fixed point and applies $\widetilde{\mathcal F}_s=\tilde B\circ F_t\circ\tilde A$ (Gaussian resampling, Theorem 4.1) to both. It multiplies the results pointwise, applies $\widetilde{\mathcal F}_s$ to the conjugate, and rescales by $S^2\,2^{2b+6d\alpha^2}/2^p$ ($S=\prod_is_i$) with rounding to the nearest integer. Put $E=\varepsilon_A+\varepsilon_F+\varepsilon_B$, where $\varepsilon_A=d(6\lceil\sqrt p\rceil\alpha+4)$ and $\varepsilon_B=\sum_i(n_i(10m+12)+4)$ are the errors of Theorem 4.1. If

then at every index of the box $\prod_i[0,s_i)$ the output equals the exact cyclic convolution

This is the correctness half of the recursive step of Harvey–van der Hoeven (Proposition 5.4), with the power-of-two transform left as a hypothesis. It can be discharged by Theorem 3.1 or by Bluestein's reduction (bluestein_fp) to any convolution routine.