# When does Discrete Fourier analysis fail to detect a frequency?

I'm using python to learn about Discrete Fourier Analysis. What I want to understand is when does the technique fail to recover some frequency of the signal? I understand how this can occur via the phenomenon of aliasing, however, the following quote from the Wikipedia page for a Discrete Fourier Transform has let me to believe there are other reasons that the technique would fail.

The frequencies of the output sinusoids are integer multiples of a fundamental frequency, whose corresponding period is the length of the sampling interval.

Based on that quote, it is my understanding that the discrete Fourier transform can only recover the frequencies when they are integer multiples of the fundamental frequency (i.e. the sample rate). If this is true, then if I construct a signal based on a series whose frequencies are all co-prime with the sample rate, then the discrete fourier transform would fail to discover those frequencies in the signal.

Here is the test I have constructed using python:

The signal I am analyzing is a sum of $\sin(2\pi kt) + cos(2\pi kt)$ where $k$ is in $\{11, 13, 17, 19\}$ for any time $t$ measured in seconds. I have sampled this signal at a sample rate of $100$ samples per second over one second. Notice that none of the frequencies is an integer multiple of the sample rate.

I am not able to post the image of the plots I made, since I am a new member here, however, python's fft (I'm using the one included in numpy) is definitely able to detect each of the frequencies of the series.

Can anyone please explain where I have gone wrong? Why is the fft able to discover the frequencies and under what conditions does the fft fail to discover frequencies in a signal (besides aliasing).

-

## migrated from mathoverflow.netJul 30 '13 at 20:03

This question came from our site for professional mathematicians.

You might want to change the spelling; "discreet" (instead of the correct "discrete") will sound comical to many ears. –  user43208 Jul 30 '13 at 19:39
Have I been using the Indiscreet Fourier Transform??? Rats... –  Igor Rivin Jul 30 '13 at 19:57
I think you have a fundamental misunderstanding of what the DFT does. That quote from the Wiki page is referring to the frequencies of the orthonormal basis that comprises the DFT, viz. $\left\{e^{j2\pi / N \cdot f_s \cdot n }\right\}$ for $n=0,\dots,N-1$, where $f_s$ is the sampling frequency. The DFT samples the spectrum at those locations. That's it. The transform is an isomorphism, so it is not true that it can only recover those particular frequencies; it just expresses signals as a linear combination of those frequencies. –  AnonSubmitter85 Jul 30 '13 at 22:22
The DFT does not "discover" frequencies. It simply expresses a signal as a linear combination of complex sinusoids. These sinusoids are what are related by multiplies of the fundamental frequency. The transform is also bijective, so any set of DFT coefficients corresponds to one and only one signal in the time domain. There are principles and techniques for resolving frequency components, but, given your question, I don't think that is what you are after. –  AnonSubmitter85 Jul 31 '13 at 9:41
The transform is an isomorphism, so it is not true that it can only recover those particular frequencies; it just expresses signals as a linear combination of those frequencies. Thank you, that does answer my question. –  Harlequin144 Jul 31 '13 at 18:26

Hint: let me ask you something: How do the plots look when $k$ is an integer multiple of the fundamental frequency, compared to when it is not? Have you tried varying the sampling rate (say, 100 -> 50) to see what the effect on the plots is?
My guess is that you will see very sharp peaks when $k$ is an integer multiple; you will see slightly wider peaks when $k$ is not; and these peaks will increase in wideness as the sampling rate decreases.