From: Robin Chapman Subject: Re: A complex exponential summation Date: Mon, 12 Jul 1999 17:48:03 GMT Newsgroups: sci.math To: chris.dearlove@gecm.com Keywords: Gauss sum In article <7mcsl9$7v2$1@miranda.gmrc.gecm.com>, chris.dearlove@gecm.com wrote: > A colleague has a problem which includes the summation > > Sum for n from 0 to N-1 of w^(n^2) > > where w is the first complex Nth root of unity, i.e. w = exp(2 pi i / N) > > A possibly unreliable source suggests (without proof or reference) that > for N an odd prime the absolute value of the sum is sqrt(N). This is > certainly true for N=3 and N=5 (and not for some non-prime N) but we > haven't tried any further values. (Obviously a simple program, which I > may well throw together, has the potential to take this further.) > This is the quadratic Gauss sum. Let G(N) denote the above sum. Then G(N) = sqrt(N) if N = 1 (mod 4) 0 if N = 2 (mod 4) i sqrt(N) if N = 3 (mod 4) (1+i) sqrt(N) if N = 0 (mod 4). This is not easy to prove in full. See e.g. chapter 2 of Davenport's Multiplicative Number Theory (2nd ed) Springer 1980. It's not so hard to prove some parts of this. For N = 2 (mod 4) we get w^{n^2} = -w^{{n+N/2}^2} so that the whole sum cancels. For odd N we get that |G(N)|^2 is the double sum of w^{n^2-m^2} or that of w^{ab} putting a = n+m and b = n-m. This is easily seen to equal N. Again for odd N there's a nice proof using matrices. Let M be the matrix with entries w^{ij}. Then the trace of M is G(N). The eigenvalues of M^2 are N and -N with multiplicities (N+1)/2 and (N-1)/2 by explicit computation. Thus the eigenvalues of M are +-sqrt(N) and +-isqrt(N) with multiplicities to be determined. They can be found by calculating det(M), which is facilitated by M haveing Vandermonde type. Finally for distinct odd primes p and q we get G(pq) = (p/q)(q/p) G(p)G(q) where (p/q) and (q/p) are Legendre symbols. Thus the law of quadratic reciprocity follows from the evaluation of the G(N)! -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "They did not have proper palms at home in Exeter." Peter Carey, _Oscar and Lucinda_ Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. ============================================================================== From: Robin Chapman Subject: Re: A complex exponential summation Date: Tue, 13 Jul 1999 08:59:30 GMT Newsgroups: sci.math To: chris.dearlove@gecm.com In article <7mcuj0$a55$1@miranda.gmrc.gecm.com>, chris.dearlove@gecm.com wrote: > Chris Dearlove (cmd@gmrc.gecm.com) wrote: > : A colleague has a problem which includes the summation > > : Sum for n from 0 to N-1 of w^(n^2) > > : where w is the first complex Nth root of unity, i.e. w = exp(2 pi i / N) > > : A possibly unreliable source suggests (without proof or reference) that > : for N an odd prime the absolute value of the sum is sqrt(N). This is > : certainly true for N=3 and N=5 (and not for some non-prime N) but we > : haven't tried any further values. (Obviously a simple program, which I > : may well throw together, has the potential to take this further.) > > To follow myself up in fact experimental evidence suggests a result of > sqrt(N) when N is odd, sqrt(2N) when N is a multiple of 4 or zero > when N is an odd multiple of 2. A generalisation my colleague is also > interested in, namely > > Sum for n from 0 to N-1 of w(n^2 + n * m) > > seems to reverse the two even cases when m is one. > When m is even then w^(n^2 + nm) = w^{-m^2/4} w^{(n+m)^2} and so the new sum is w^{-m^2/4) G(N) where G(N) denotes the quadratic Gauss sum. If m is odd but N is also odd we can replace m by m+N and so the same thing. For m odd and N even we need to be more cunning. Assume that m = 1 and N is even (the general case is similar). Set z = exp(pi i/2N) so that z^4 = w. Then w^(n^2 + n) = z^((2n+1)^2)/z. Replacing n by n+N doesn't change the value of this term so the sum equals (1/2z) sum_{n=0}^{2N-1} z^{(2n+1)^2} = (1/2z)[G(4N) - sum_{n=0}^{2N-1} z^{4n^2}] = (1/2z)[G(4N) - 2G(N)]. For N divisible by 4 the bracket is (1+i)sqrt(4N) - 2(1+i)sqrt(N) = 0. For N = 2 (mod 4) the bracket is (1+i)sqrt(4N) = 2(1+i)sqrt(N). When N is divisible by 4 we can see the result more easily by noting that the n and n + N/2 terms cancel. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "They did not have proper palms at home in Exeter." Peter Carey, _Oscar and Lucinda_ Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.