# Maximum Magnitude Deviation between DFT and DTFT

This is a cross-post from signal processing forum as it was not conclusive. Let $$x[n]$$ be a finite-length sequence with length $$N$$. The continuous DTFT $$X(\omega)$$ is then $$X(\omega) = \sum_{n = 0}^{N-1} x[n] e^{-j \omega n}.$$

The length-$$N$$ DFT of $$x[n]$$ is $$X[k] = \sum_{n = 0}^{N-1} x[n] e^{-j 2 \pi \frac{k n}{N}}.$$ For this, the DFT is a sampled version of the DTFT, i.e., $$X[k] = X(2\pi k / N).$$ Please also see posts here and here. Now, we consider the maximum magnitudes $$m_{\textrm{d}} = \max_k |X[k]|$$ and $$m_{\textrm{c}} = \max_\omega |X(\omega)|$$. Because of above, we have $$m_{\textrm{d}} \leq m_{\textrm{c}}$$.

How much does $$m_{\textrm{d}}$$ underestimate $$m_{\textrm{c}}$$? Is there $$\gamma > 1$$ such that $$\gamma m_{\textrm{d}} \geq m_{\textrm{c}}$$?

• WLOG scale so that the norm is 1, and then we have the inequalities $1/\sqrt{N}\le m_d\le m_c \le 1$. So at the least you can take $\gamma=\sqrt{N}$. Since at each of the inequalities we must have $m_c=m_d$, I'm guessing there's a much better bound... – Dror Speiser Oct 4 at 21:06
• @DrorSpeiser thanks for the first bound. I also believe that there must be a much better bound as this would be highly impracticable for signal analysis purposes. – Sebastian Schlecht Oct 5 at 8:28
• I find this question to be interesting, though the subject matter is not my field of expertise. But I do have two things to report on, both from Montgomery's paper An Exponential Polynomial Formed with the Lagrange Symbol: 1. the Fekete polynomials give a lower bound $\gamma>2\log\log n/\pi$, so there's no uniform constant $\gamma$. 2. as Montgomery writes, Bernstein's inequality give a bound in terms of "a higher sampling rate", i.e. the polynomial evaluated at roots of unity of higher order. He doesn't prove the bound in the paper, but I think it works for all real polynomials. – Dror Speiser Oct 6 at 12:08

I believe to have found a partial answer in the paper:

Gronwall, T. H. (1921). A sequence of polynomials connected with the $$n$$th roots of unity. Bulletin of the American Mathematical Society, 27(6), 275–279. http://doi.org/10.1090/S0002-9904-1921-03411-2

It actually gives a full construction of a polynomial $$F(z)$$ such that $$|F(e^{i2\pi k/N})| \leq 1$$, but $$\max |F(z)| = \frac{1}{N} \sum_{n=0}^{N-1} \frac{1}{\sin \frac{2n + 1}{2N}\pi}$$.

This makes the upper bound $$\gamma$$ in the original question to be asymptotically equal to

$$\frac{2}{\pi}\left( \log N + C + \log \frac{2}{\pi} \right) + o(1),$$
where $$C$$ is the Euler's constant, and $$o(1)$$ tends to zero as $$N$$ increases indefinitely. There are various follow up questions:

1. $$F(z)$$ has complex coefficients. What is the bound for real coefficients?
2. How does this bound change if we add zero padding? It will tend to 1, but how quickly?
3. $$F(z)$$ gives the worst case bound, but how is this bound for random (Gaussian) distributed coefficients?
• Nice! I find it remarkable that, though the question is intended for signal processing purposes, Gronwall was tightening a bound of Landau that was used to study a number theory problem, namely about what are now called Fekete polynomials, that come up while studying class numbers of quadratic fields. (See reference in loc. cit.) – Dror Speiser Oct 15 at 23:54