# 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?

-
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 –  Gerhard Paseman Mar 11 '11 at 21:13
The work in computing the Riemann zeta function quickly uses certain ideas like this. I'm not familiar enough with the literature to cite all the right papers though. I know Ghaith Hiary recently made some progress on this by evaluating cubic exponential sums. His paper is at arxiv.org/abs/0711.5005. –  Matt Young Mar 12 '11 at 1:47
As I said, I am thinking of deg(P) bounded (and M large) –  H A Helfgott Mar 12 '11 at 13:21
- and I would be very interested in hearing some details working out G. Paseman's slightly condensed remarks. –  H A Helfgott Mar 12 '11 at 14:00
I am working on a paper that Will Jagy is kindly reviewing for me. If you send him an email for me, he will forward it to me. I will reply, but it will take me a few days to get my head out of the paper and on to expanding the comments (with no guarantee that it will do what you want). You can ask Will if I'm a safe guy to deal with; all I'll say about Will for now is that I trust him with my email address. Gerhard "Internet Paranoia Is Our Specialty" Paseman, 2011.03.12 –  Gerhard Paseman Mar 13 '11 at 5:15

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.