From: "Noam D. Elkies" Subject: Re: Exponential Sums Sort-of Date: 28 May 2000 20:47:25 GMT Newsgroups: sci.math.research Summary: [missing] In article <39258fcc$0$73579@news.execpc.com>, John Washburn wrote: >I am exploring 3, sort-of exponential sums. >In all of them P is an odd prime, n an m are integers and alpha is a >complex number. >The first is: >sum(1/(exp(-2*Pi*I*n/P)-1),n=1..P-1); >The answer seems to be (P-1)/2. William Waterhouse already proved this one, and observed that the answer is off by a factor of -1 (should be (1-P)/2). >The second is: >sum((exp(2*Pi*I*m*n/P)-1)/(exp(-2*Pi*I*n/P)-1),n=1..P-1); >The answer seems to be m mod P. This too has been answered. >The third is: >sum((alpha*exp(2*Pi*I*m*n/P)-1)/(exp(-2*Pi*I*n/P)-1),n=1..P-1); >I have no idea what the general answer is. Once we know the sums with 1 and (exp(2*Pi*I*m*n/P)-1) in the numerator, an arbitrary linear combination of 1 and exp(2*Pi*I*m*n/P) can be summed. Here's an approach that will answer most problems of this type, including sums with higher powers of (exp(-2*Pi*I*n/P)-1) in the denominator. Also, P need not be assumed prime -- any positive integer will do. For any integer n which is not a multiple of P, let z = exp(2*Pi*I*n/P). Then z^P=1 and 1+z+z^2+...+z^(P-1)=0 (for instance from the formula for summing a geometric series). Now consider w=z+2z^2+3z^3+...+(P-1)z^(P-1). To evaluate this, multiply by (z-1) to obtain P-1 - (z+z^2+z^3+...+z^(P-1)) = P-1+1 = P. Therefore, w = P/(z-1). To put it another way, 1/(z-1) = w/P. The first question asks for the sum of 1/(z-1) over the P-1 possible values of z. That is the same as the sum of w/P. But we know how to sum each of the terms in w: the sum of z is -1, of 2z^2 is -2, of 3z^3 is -3, etc., so the sum of w is -(1+2+...+(P-1))=(P-P^2)/2. Dividing by P we obtain (1-P)/2 as claimed. z^(-m)/(z-1) can be summed in the same way: use the formula for 1/(z-1) to write z^(-m) as a linear combination of 1,z,z^2,...,z^(P-1). The sum of 1 is P-1, the sum of each other monomial is -1. --Noam D. Elkies (remove 4th root of unity from e-address to reply) Department of Mathematics, Harvard University ============================================================================== From: israel@math.ubc.ca (Robert Israel) Subject: Re: Exponential Sums Sort-of Date: 19 May 2000 22:11:46 GMT Newsgroups: sci.math.research In article <39258fcc$0$73579@news.execpc.com>, John Washburn wrote: >I am exploring 3, sort-of exponential sums. >In all of them P is an odd prime, n an m are integers and alpha is a >complex number. >The third is: >sum((alpha*exp(2*Pi*I*m*n/P)-1)/(exp(-2*Pi*I*n/P)-1),n=1..P-1); If we can work this one out, we'll have all of them. Writing a[n] = exp(-2*Pi*I*n/P), this is sum_{n=1}^{P-1} (alpha a[-m*n]-1)/(a[n]-1) Now consider S(r) = sum_{n=0}^{P-1} (1-alpha a[-m*n])/(1 - r a[n]). Expand it in a power series in r, converging absolutely for |r|<1: S(r) = sum_{n=0}^{P-1} sum_{j=0}^infinity (1-alpha a[-m*n]) r^j a[n*j] = sum_{j=0}^infinity r^j sum_{n=0}^{P-1} (a[n*j] - alpha a[n*(j-m)]) The sum of the first terms over n vanishes unless j is a multiple of P, and the sum of the second terms vanishes unless j-m is a multiple of P. I'm assuming 0 <= m <= P-1 (but of course the result is periodic in m with period P). Thus S(r) = P sum_{k=0}^infinity r^{kP} - P alpha sum_{k=0}^infinity r^{kP+m} = P (1 - alpha r^m)/(1-r^P) Your third sum is limit_{r -> 1} (S(r) - (1-alpha)/(1-r)) = (P-1)/2 + (2m-P+1) alpha /2 Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2