Computing exponential sums rapidly? I am looking at sums of the form 
$\sum_{N\le n \leq N+M} e(P(n))$
where $P\in R[x]$ is a polynomial of bounded degree. Let's say $M\sim c N$ (and $N$ is large).
The question is - when can one compute this sum rapidly? By "computing" I mean "computing with an error of less than 0.5" (or "computing exactly", which boils down to the same thing for what I have in mind). By "rapidly" I should mean ideally "in time $O((\log N)^{O(1)})$" -
but really I would be somewhat happy with any running time of the form $O(N^{1-\delta})$, $\delta>0$.
If $deg(P)=1$, this is easy.
If $deg(P)=2$, then complete Gauss sums can help.
What is known for deg(P)>2?
 A: I reproduce my comments from above, and then "evaporate" them slightly.
If deg(P) is small compared to N and M, I have some ideas which might produce O(N) running time methods (similar to Horner's method for polynomials). If you can determine c(a,b) which satisfies e(c(a,b)) = e(a) + e(b) to the desired accuracy, you might be able to do some kind of analogue to Karatsuba multiplication. If deg(P) is comparable to N and M, I have no ideas. Gerhard "Ask Me About System Design" Paseman, 2011.03.11
Horner's method for polynomials is
$(...((a_n*x + a_{n-1})*x + a_{n-2})*x + ... )*x + a_0$,
which evaluates a polynomial using n multiplications and n additions for a polynomial of degree n.  For a sum of your type, let D(n) = P(n) - P(n-1), then one has
(...(exp(D(N+M)) +1)*exp(D(N+M-1) +1)*exp(D(N+M-2) ... +1)*exp(P(N)), if I haven't fouled up the arithmetic.  There are numerical analysis issues with the above, not to mention the time involved in computing the values D(n).  If M is small compared to N, then this may be tolerable, especially if P is monotonic over the range of interest, but it is still O(N).  If P has some symmetry properties to exploit, you might be able to rearrange the order of evaluations and compress some of the computations (e.g. maybe there are k and c such that P(2n+c) = k + P(2n) ) but I don't even know that deg(P) is much smaller than M or N, much less what properties P has that can be exploited.
Suppose you can compute quickly c(a,b), so that given a and b you can find c(a,b) and then exponentiate so that exp(a) + exp(b) = exp(c(a,b)).  Karatsuba multiplication benefits from the identity (aN +b)(cN +d) = acNN + (bc +ad)N + bd which can be gotten from three multiplications of words roughly half the size of the original words instead of four, here N being the size of a convenient word.  I am imagining that there may be a relation that allows you to compute conveniently exp(w) + exp(x) + exp(y) + exp(z) by looking at
(some permutations of) c(w,x), c(y,z) and c(c(w,x),c(y,z)).  If there are, it may not produce an algorithm running faster than O(N), but it may still be tolerable.
Besides the two ideas above, there is the Fast Fourier Transform, which has many versions suitable for multiplication; it may be possible to adapt one for exponential sums.  (If you take a look at this things from a programming/general algebra perspective,  your vision mildly blurs the distinction between operations and suggests parallels between known algorithms and possibilities for your current situation.  Also, taking off your glasses helps.)
None of the above is a direct answer to your question.  One of them might spark a notion which would help in your computations.  (E.g. if deg(P)=3, there might be a way to use third-order differences in combination with some of the above to get what you want.)  If you know anything else about P(), or want me to consider special cases, I might come up with something even more useful.  In any case, I hope this is enough expansion for you.
Gerhard "Ask Me About Blurry Vision" Paseman, 2011.03.26
