I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE > 1$.
I would like to put forward a formal argument that if we use complex DFT for computing a convolution on a physical machine, it will yield incorrect results at some transform length $n\in \mathbb{N}$.
What was easy to prove was the fact that at some big $n$ computing the convolution with DFT will not at all be possible, since, for example, the following difference of primitive roots modulo $n$: $\omega_n^1 - \omega_n^2 \rightarrow 0$ when $n \rightarrow \infty$, and if we are restricted by some machine epsilon $\epsilon$, at some $n$ it will make the values indistinguishable and interpolation impossible.
But the boundary I've received using such an argument was way too big: only for $n=2^{60}$ I've received $\omega_n^1 - \omega_n^2$ that had both components, $Re$ and $Im$, less than representable by $double$-precision type. This certainly is a boundary, but not very practical one.
What I would like to show (if it is possible), is that much earlier than interpolation becomes theoretically impossible, the round-off errors will start to give wrong coefficients in the convolution, so that
$$a\cdot b \neq IDFT(DFT(a)\times DFT(b)),$$
where $DFT$ and $IDFT$ are algorithm implementations that I use to calculate the Fourier transform.
Maybe it is possible to make use of the fact that the value of the primitive root modulo $n$, $\omega_n = \exp(-2\pi i / n)$, is an irrational number for the majority of $n$'s. It will thereby be computed with inevitable error $\psi$, defined as the value needed to "round off" everything that's less than the machine epsilon $\epsilon$. Thus all the values used for DFT,
$$\omega_n^0, \omega_n^1, ..., \omega_n^{n-1},$$
except for $\omega_n^0$ will also be computed with errors.
Since I'm not a good mathematician at all, I don't know if and how I could use this fact to prove that the situation is going to worsen with increasing $n$ and that eventually the convolution is going to be computed incorrectly.
I would also like to have and argument for OR against the following claim: for fixed $n$, the maximal error will be produced when all the coefficients of both polynomials are $BASE-1$.
Thank you very much in advance!
