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.