wu :: forums « wu :: forums - Riemann sums of the Fresnel integral » Welcome, Guest. Please Login or Register. Sep 7th, 2024, 10:43am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Grimbal, SMQ, william wu, Eigenray, Icarus, towr)    Riemann sums of the Fresnel integral « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Riemann sums of the Fresnel integral  (Read 3636 times)
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Riemann sums of the Fresnel integral   « on: Jan 25th, 2007, 1:46pm » Quote Modify

Let F(x) = sin(2x2), and for a positive integer n, let Sn be the right Riemann sum of F over the interval [0, n], with n subintervals each of width 1/n.  That is,

Sn = 1/n k=1n F(k/n).

Does Sn converge to the integral of F over [0,)?  Give a closed form for Sn.
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Riemann sums of the Fresnel integral   « Reply #1 on: Jul 29th, 2007, 7:36pm » Quote Modify

You might think this has a good chance of converging, since we are using subintervals of size 1/n 0, while going from x=0 up to x=n .

The first few terms are Sn = 0, 0, 1, 1, 0, 0, 1, 1, ....
 IP Logged
Obob
Senior Riddler

Gender:
Posts: 489
 Re: Riemann sums of the Fresnel integral   « Reply #2 on: Aug 23rd, 2007, 1:18pm » Quote Modify

First assume that n is prime.  Let w be the nth root of unity e2 pi i/n.  Then Sn is the imaginary part of n-1/2 (w+w4+w9+...+wn^2).  The value of wk^2 depends only on the residue class of k2 mod n, and the residue class of k2 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 x2=y2, 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, k2 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 Sn is the imaginary part of n-1/2 (1+2(f(1)w1+f(2)w2+...+f(n)wn)), 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 Sn as the imaginary part of 2n-1/2(f(1)w1 +...+f(n)wn).  Recalling that f(k)=((k | n) +1)/2, and recalling that w1+...+wn=0 for a primitive nth root of unity, we see that Sn is the imaginary part of n-1/2((1 | n)w1 + ... + (n | n)wn).  But the sum on the right is the classical Gauss sum, whose value is n1/2 if n is 1 mod 4, and in1/2 if n is 3 mod 4.  Thus if n is a prime that is 1 mod 4, Sn equals 0, and if n is a prime that is 3 mod 4, Sn 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 Sn 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 Sn when n is not a prime, since the squaring map Z/nZ->Z/nZ is much more complicated then.
 « Last Edit: Aug 23rd, 2007, 2:01pm by Obob » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Riemann sums of the Fresnel integral   « Reply #3 on: Aug 23rd, 2007, 10:25pm » Quote Modify

on Aug 23rd, 2007, 1:18pm, 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 Sn 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) = nk^2,

where the sum is over k /n.  For n an odd prime, this is Gauss's sum: A(n) = {n*}, where n* = n = 1 mod 4.  We generalize this.

First suppose n = pe, and let = n.  We break the sum into two parts depending on whether p | k.  In the first case, k=px, with x /pe-1, and

p|k k^2 = Z/p^(e-1) p^2x^2 = pA(pe-2).

In the latter, k = a + pe-1x, for a (/pe-1)*, and x /p, but

x [a^2+2axp^(e-1)+x^2p^(2e-2)] = a^2*(p2a)x = 0.

So A(pe) = p A(pe-2), for e 2, and therefore

A(pe) = {pe*}, p odd.

Using the fact that for e 3, {k2 | k odd} {8t+1} mod 2e, one can show similarly that A(2e) = 2A(2e-2) for e 4.  With initial conditions one finds

A(2)=0, and A(2e) = {2e+1i} for e 2.

[message continues]
 « Last Edit: Aug 23rd, 2007, 10:28pm by Eigenray » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Riemann sums of the Fresnel integral   « Reply #4 on: Aug 23rd, 2007, 10:25pm » Quote Modify

Now suppose m,n are relatively prime.  Then c /(mn) is equivalent to c = am + bn, with a /m, b /n.  So

A(mn) = a,b mn(am+bn)^2 = a,b nma^2mnb^2
= n,m(A(n)) m,n(A(m)),

where n,m Gal((n)/) corresponds to n nm.  [In particular, A(n)=0 iff n=2 mod 4.]

Now suppose m,n are odd.  Then (inductively) A(n) has degree 2 over , so n,m(A(n)) = n(m) A(n) for some homomorphism n : (/n)* {1}.  That is,

A(mn) = n(m)m(n) A(m)A(n).

For obvious reasons, I strongly suspect that 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 {n*}{m*}.

Checking the four cases, A(mn) = {mn*} in each case.

For m=2e, m(n) is a power of i.  If e > 1 is odd, it looks like m(n) = i(n-1)/2.  If e > 0 is even, it looks like m(n) is 1 if n=1 mod 4, and -i if n=3 mod 4.  Together then,

A(2en) = (2|n)e2^e(n) {n*} {2e+1i},

which works out to {2e+1n i} in each case.

Thus, assuming the formula for , we see that Sn = Im An/n = 1 when n=0,3 mod 4, and Sn = 0 when n=1,2 mod 4.

However, even without knowing exactly, we can still deduce inductively that A(n) = {n*} for n odd, and A(4n) is a power of i times {8ni}, which gives us Sn 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 p .
 « Last Edit: Aug 24th, 2007, 1:02am by Eigenray » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Riemann sums of the Fresnel integral   « Reply #5 on: Aug 24th, 2007, 1:01am » Quote Modify

on Aug 23rd, 2007, 10:25pm, Eigenray wrote:
 For obvious reasons, I strongly suspect that 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) = A(m)A(n), where = 1.  Now, the automorphism mn,a of (mn) taking mn mna, when restricted to (n), is just n,a.  So

mn(a) A(mn) = mn,a(A(mn)) = mn,a(A(m)A(n))
= m,a(A(m)) n,a(A(n)) = m(a)n(a) A(m)A(n)
= m(a)n(a) A(mn),

and therefore mn = nm.  For prime powers, note 1(a) = 1, and p(a) = (a|p) by definition, and finally, since A(pe) = p A(pe-2), we have p^e = p^(e-2), and putting it all together shows n(a) = (a|n).

Quote:
 For m=2e, m(n) is a power of i.  If e > 1 is odd, it looks like m(n) = i(n-1)/2.  If e > 0 is even, it looks like m(n) is 1 if n=1 mod 4, and -i if n=3 mod 4.

Using the fact that { 1, 5} is a complete set of coset representatives for the squares in (/2e)*, and the fact that A(2)=0; A(2e) = 2 A(2e-2) for e 4, it follows that we only need to compute 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) = {p*} for odd primes p, the fact that A(pq) = {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.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »