wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Riemann sums of the Fresnel integral
        
(Message started by: Eigenray on Jan 25^th, 2007, 1:46pm)

Title: Riemann sums of the Fresnel integral
Post by Eigenray on Jan 25^th, 2007, 1:46pm

Let F(x) = sin(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifx²), and for a positive integer n, let S_n be the right Riemann sum of F over the interval [0, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn], with n subintervals each of width 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn. That is,

S_n = 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1ⁿ F(k/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn).

Does S_n converge to the integral of F over [0,http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif)? Give a closed form for S_n.

Title: Re: Riemann sums of the Fresnel integral
Post by Eigenray on Jul 29^th, 2007, 7:36pm

You might think this has a good chance of converging, since we are using subintervals of size 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif 0, while going from x=0 up to x=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif.

The first few terms are S_n = [hide]0, 0, 1, 1, 0, 0, 1, 1[/hide], ....

Title: Re: Riemann sums of the Fresnel integral
Post by Obob on Aug 23^rd, 2007, 1:18pm

First assume that n is prime. Let w be the nth root of unity e^{2 pi i/n}. Then S_n is the imaginary part of n^-1/2 (w+w⁴+w⁹+...+w^{n^2}). The value of w^{k^2} depends only on the residue class of k² mod n, and the residue class of k² mod n depends only on the residue class of k mod n.

Now we need to understand the squaring map Z/nZ -> Z/nZ. Notice that the image of x and -x=n-x are the same. Moreover, if x²=y², then n divides either x-y or x+y, and x=y or x=-y. So the fiber over an element y of Z/nZ consists of either 0, 1, or 2 points:

0 points, if y is not a square mod n
1 point, if y=0
2 points, otherwise.

Thus as k ranges from 1 to n, k² mod n assumes the value of each square mod n twice, except it only assumes 0 once.

Now let f(k) be 0 if k is not a square mod n, and 1 if k is a square mod n. In terms of Legendre symbols, f(k)=((k | n)+1)/2 where, for lack of better notation, (k | n) is the Legendre symbol, i.e. 1 if k is a square mod n and -1 if k is not a square mod n.

Now we see that S_n is the imaginary part of n^-1/2 (1+2(f(1)w¹+f(2)w²+...+f(n)wⁿ)), the factor of 2 coming from the fact that every nonzero square is a square in two different ways, and the 1 summand coming from 0 being a square in exactly one way. But since we only care about imaginary parts, we may as well write S_n as the imaginary part of 2n^-1/2(f(1)w¹ +...+f(n)wⁿ). Recalling that f(k)=((k | n) +1)/2, and recalling that w¹+...+wⁿ=0 for a primitive nth root of unity, we see that S_n is the imaginary part of n^-1/2((1 | n)w¹ + ... + (n | n)wⁿ). But the sum on the right is the classical Gauss sum, whose value is n^1/2 if n is 1 mod 4, and in^1/2 if n is 3 mod 4. Thus if n is a prime that is 1 mod 4, S_n equals 0, and if n is a prime that is 3 mod 4, S_n equals 1.

In particular, since there are infinitely many primes that are 1 mod 4 and infinitely many primes that are 3 mod 4, the sequence S_n is divergent. Therefore these particular Riemann sums do not converge to the Fresnel integral.

I'm not really sure how to give a closed form for S_n when n is not a prime, since the squaring map Z/nZ->Z/nZ is much more complicated then.

Title: Re: Riemann sums of the Fresnel integral
Post by Eigenray on Aug 23^rd, 2007, 10:25pm

on 08/23/07 at 13:18:26, Obob wrote:

But the sum on the right is the classical Gauss sum

Right. The 'Riemann sum'-ness of Gauss's sum just occurred to me one day and I thought it would make a cute problem: the integral converges, and the 'mesh' of the partition goes to 0, and yet the Riemann sum simply alternates between 0 and 1! (Of course the intervals are chosen very carefully.)

Quote:

I'm not really sure how to give a closed form for S_n when n is not a prime.

Neither am I. I knew the result for primes, and the sequence looks periodic as far as the eye could see, so I just assumed that was the answer when I posted it.

After thinking about it some more today I now know the result up to sign. Define

A(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n^{k^2},

where the sum is over k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif. For n an odd prime, this is Gauss's sum: A(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{n*}, where n* = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif n = 1 mod 4. We generalize this.

First suppose n = p^e, and let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n. We break the sum into two parts depending on whether p | k. In the first case, k=px, with x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/p^e-1, and

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_p|k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif^{k^2} = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_Z/p^(e-1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif^{p^2x^2} = pA(p^e-2).

In the latter, k = a + p^e-1x, for a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/p^e-1)^*, and x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/p, but

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif^{[a^2+2axp^(e-1)+x^2p^(2e-2)]} = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif^{a^2}*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_p^2a)^x = 0.

So A(p^e) = p A(p^e-2), for e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 2, and therefore

A(p^e) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{p^e*}, p odd.

Using the fact that for e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 3, {k² | k odd} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif {8t+1} mod 2^e, one can show similarly that A(2^e) = 2A(2^e-2) for e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 4. With initial conditions one finds

A(2)=0, and A(2^e) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{2^e+1i} for e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 2.

[message continues]

Title: Re: Riemann sums of the Fresnel integral
Post by Eigenray on Aug 23^rd, 2007, 10:25pm

Now suppose m,n are relatively prime. Then c http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/(mn) is equivalent to c = am + bn, with a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/m, b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/n. So

A(mn) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_a,b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_mn^{(am+bn)^2} = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_a,b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n^{ma^2}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_m^{nb^2}
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_n,m(A(n)) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_m,n(A(m)),

where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_n,m http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif Gal(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n)/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif) corresponds to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mapsto.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n^m. [In particular, A(n)=0 iff n=2 mod 4.]

Now suppose m,n are odd. Then (inductively) A(n) has degree http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2 over http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif, so http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_n,m(A(n)) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(m) A(n) for some homomorphism http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n : (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/n)^* http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif {http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1}. That is,

A(mn) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(m)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) A(m)A(n).

For obvious reasons, I strongly suspect that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(m) is the Jacobi symbol (m|n), but I haven't given it too much thought and don't have time tonight. Assuming this, by quadratic reciprocity and induction, we have

A(mn) = (-1)^(n-1)(m-1)/4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{n*}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{m*}.

Checking the four cases, A(mn) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{mn*} in each case.

For m=2^e, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) is a power of i. If e > 1 is odd, it looks like http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) = i^(n-1)/2. If e > 0 is even, it looks like http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) is 1 if n=1 mod 4, and -i if n=3 mod 4. Together then,

A(2^en) = (2|n)^ehttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_2^e(n) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{n*} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{2^e+1i},

which works out to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{2^e+1n i} in each case.

Thus, assuming the formula for http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif, we see that S_n = Im A_n/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn = 1 when n=0,3 mod 4, and S_n = 0 when n=1,2 mod 4.

However, even without knowing http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif exactly, we can still deduce inductively that A(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{n*} for n odd, and A(4n) is a power of i times http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{8ni}, which gives us S_n up to sign.

I remember reading somewhere that Gauss himself had trouble determining the sign of his own sum A(p). And the reason is that there really is no purely algebraic proof, since it depends on the choice of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbc.gif.

Title: Re: Riemann sums of the Fresnel integral
Post by Eigenray on Aug 24^th, 2007, 1:01am

on 08/23/07 at 22:25:58, Eigenray wrote:

For obvious reasons, I strongly suspect that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(m) is the Jacobi symbol (m|n).

Actually, this isn't hard: fix m,n odd relatively prime. We already know that A(mn) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifA(m)A(n), where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1. Now, the automorphism http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_mn,a of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_mn) taking http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_mn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/mapsto.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_mn^a, when restricted to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif_n), is just http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_n,a. So

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_mn(a) A(mn) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_mn,a(A(mn)) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_mn,a(A(m)A(n))
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_m,a(A(m)) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_n,a(A(n)) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(a)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(a) A(m)A(n)
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(a)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(a) A(mn),

and therefore http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_mn = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m. For prime powers, note http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif₁(a) = 1, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_p(a) = (a|p) by definition, and finally, since A(p^e) = p A(p^e-2), we have http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_p^e = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_p^(e-2), and putting it all together shows http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_n(a) = (a|n).

Quote:

For m=2^e, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) is a power of i. If e > 1 is odd, it looks like http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) = i^(n-1)/2. If e > 0 is even, it looks like http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_m(n) is 1 if n=1 mod 4, and -i if n=3 mod 4.

Using the fact that {http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif 1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif 5} is a complete set of coset representatives for the squares in (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/2^e)^*, and the fact that A(2)=0; A(2^e) = 2 A(2^e-2) for e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 4, it follows that we only need to compute http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif_2^e(n) for n = {-1, 5}, and e = {2, 3}, to get the complete description. So the above is correct.

Of course all this is assuming Gauss's result for the sign of A(p). Finally, I just wanted to point out that given A(p) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{p*} for odd primes p, the fact that A(pq) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{pq*} is easily seen to be equivalent to quadratic reciprocity. So any direct proof that A(n) always lies in the first quadrant is also a proof of quadratic reciprocity.