HvdH Thm 4.1: $\mathcal F_{\mathbf s}=2^{2d\alpha^2}\mathcal B\mathcal F_{\mathbf t}\mathcal A$ (multidimensional Gaussian resampling)

Multidimensional Gaussian resampling (Harvey–van der Hoeven, Theorem 4.1).

Let $d\ge1$, let $s_1,\dots,s_d$ and $t_1,\dots,t_d$ be positive integers with $s_i<t_i$ and $\gcd(s_i,t_i)=1$, and let $\alpha\ge2$ be an integer with $\alpha^2\,(t_i/s_i-1)\ge1$ for every $i$. For $\mathbf s=(s_1,\dots,s_d)$ write $\mathcal F_{\mathbf s}$ for the normalised $d$-dimensional DFT on $\mathbb C^{s_1}\otimes\cdots\otimes\mathbb C^{s_d}$ (functions on $\prod_i\mathbb Z/s_i$):

Then there are linear maps $\mathcal A$ and $\mathcal B$, both of norm at most $1$ for the sup norm, with

So a DFT of awkward (for example prime) dimensions is reduced, at the cost of $O(d\alpha^2)$ bits of precision, to a DFT of convenient dimensions $t_i$ (powers of two in the paper). This is the step that lets the algorithm of Harvey–van der Hoeven use the synthetic FFT in Section 5.

Formalization note. $\mathcal A=\bigotimes_i\mathcal A_i$ and $\mathcal B=\bigotimes_i\mathcal B_i$ are tensor products of the one-dimensional maps of IntMul.HvdH.prop_4_7_i.