# Proof that DFT does not require more than N points

I'm trying to show how the discrete Fourier transform (DFT) arises from the equation for the continuous-time Fourier Transform. I've run into an interesting caveat which I can't seem to find an explanation to anywhere. My 'derivation' goes something like this:

Lets consider the continuous time Fourier transform equation $$F(\omega) = \int_{-\infty}^{+\infty} \, f(t) \, e^{-2\pi i \omega t} \,dt$$ If $$f(t)$$ was to be discretised at $$N$$ evenly spaced sampling points with the sampling interval of $$dt$$, then it could be thought of as a continuous function of time with Dirac deltas at each sampling point. The integral of each of the deltas would be equal to the value of $$f(t)$$ at that point. Lets denote $$f(t)$$ at $$k$$-th sampling point (0-indexed) as $$f_k$$. Now, the integral is non-zero only at those delta functions so the entire above equation can be written as a sum $$F(\omega) = dt \times \sum_{k=0}^{N-1} \, f_k\, e^{-2\pi i \omega (k dt)}$$ Even though the sum is finite, this is a continuous function of $$\omega$$. $$F(\omega)$$ turns out to be periodic in $$\omega$$ and therefore just a single period of it is needed to be kept to retain all of the information about the sampled version of $$f(t)$$ it came from.

All of this is (I believe) fine. Here comes the tricky bit. I want to then say that this single period of $$F(\omega)$$ can be sampled down to $$N$$ evenly spaced points which would in fact give the equation for the DFT. I say that: "It is one of the implications of the Shannon information theory (...) that for a general case of $$N$$ arbitrary bits of information, there does not exist a smaller set of bits which can be used to represent all of the information of the original $$N$$ bits. This places a lower bound on how many samples of $$F(\omega)$$ one can take."

Question 1: Is this a correct statement about implications of the information theory?

Question 2: I know that N bits of $$F(\omega)$$ are sufficient, but how do I prove it? To put it differently: How can I one show that for any arbitrary signal I will not loose any information about $$f(t)$$ by sampling $$F(\omega)$$ at only $$N$$ points.

• the most fundamental thing is that the DFT maps a periodic sequence $x_n$ having period $N$ (so that $x_{n+N}=x_n \quad \forall n \in \mathbb{Z}$) to another periodic sequence $X_k$ having the same period $N$. Relating the DFT to the DTFT or, as you are trying to do, the continuous-time Fourier transform, requires a little bit of hand-waving to put it into a form of the Riemann integral. – robert bristow-johnson Jul 8 '19 at 21:39