From: "Noam D. Elkies" <elkies@math.harivard.edu>
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  <jwwwash@execpc.com> 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  <jwwwash@execpc.com> 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