As the title says, why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $O(N \log N)$?
This is a famous open problem in mathematics/theoretical computer science. Still, I cannot find any explanation why it is so difficult to construct a proof for it. Actually, I don't have any idea at all how proofs for such problems are usually written.
Intuitively, proofs that something can't be done are harder than proofs that something can be done, because the latter need only exhibit a way of doing it, while the former need to show that any possible approach will run into problems. Most proofs of impossibility use additional structure in the problem to show that any approach needs some number of steps to 'clarify' the structure or to construct 'adversaries' who can make the problem more difficult.
For instance, the straightforward proof that sorting requires $\Omega(n\log n)$ operations is of this form; since there are $n!\approx n^{n+1/2}e^{-n}$ different permutations of the data and any binary comparison can only cut the search space in half at best, then we need a minimum of $\lg(n!)\approx n\lg n-kn$ comparisons to 'pick out' the sorted data, using a binary comparison model of computation. This example also shows why specifying the model of computation matters; it's well known that sort on bounded data can be done in linear time(using e.g. bin sorts), and even that sorting on arbitrary sized integer data can be done more quickly than $\Omega(n\lg n)$ if the algorithm is allowed to perform arithmetic operations (and not just comparisons) on the data. Contrast this against something like matrix multiplication, where even though the naive algorithm is $O(n^3)$ there are no specific constraints that 'force' algorithms to be slow, and in fact the time has been pushed down to roughly $O(n^{2.4})$ with no reason to believe that $O(n^2)$ (the naive lower bound) is impossible.
In short, then, the reason why it's so hard to show that the DFT requires superlinear time is that we have no specific reason not to believe that it doesn't; since we only have $O(n)$ pieces of data coming out of the operation, it's at least conceivable that some very clever algorithm can find them all in $O(1)$ time per piece of data, or $O(n)$ time overall.