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 25^{th}, 2007, 1:46pm » 
Quote Modify

Let F(x) = sin(2x^{2}), and for a positive integer n, let S_{n} be the right Riemann sum of F over the interval [0, n], with n subintervals each of width 1/n. That is, S_{n} = 1/n _{k=1}^{n} F(k/n). Does S_{n} converge to the integral of F over [0,)? Give a closed form for S_{n}.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Riemann sums of the Fresnel integral
« Reply #1 on: Jul 29^{th}, 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 S_{n} = 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 23^{rd}, 2007, 1:18pm » 
Quote Modify

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^{4}+w^{9}+...+w^{n^2}). The value of w^{k^2} depends only on the residue class of k^{2} mod n, and the residue class of k^{2} 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=nx are the same. Moreover, if x^{2}=y^{2}, then n divides either xy 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^{2} 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^{1}+f(2)w^{2}+...+f(n)w^{n})), 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^{1} +...+f(n)w^{n}). Recalling that f(k)=((k  n) +1)/2, and recalling that w^{1}+...+w^{n}=0 for a primitive nth root of unity, we see that S_{n} is the imaginary part of n^{1/2}((1  n)w^{1} + ... + (n  n)w^{n}). 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.

« Last Edit: Aug 23^{rd}, 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 23^{rd}, 2007, 10:25pm » 
Quote Modify

on Aug 23^{rd}, 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 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) = _{n}^{k^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 = p^{e}, and let = _{n}. We break the sum into two parts depending on whether p  k. In the first case, k=px, with x /p^{e1}, and _{pk} ^{k^2} = _{Z/p^(e1)} ^{p^2x^2} = pA(p^{e2}). In the latter, k = a + p^{e1}x, for a (/p^{e1})^{*}, and x /p, but _{x} ^{[a^2+2axp^(e1)+x^2p^(2e2)]} = ^{a^2}*(_{p}^{2a})^{x} = 0. So A(p^{e}) = p A(p^{e2}), for e 2, and therefore A(p^{e}) = {p^{e}*}, p odd. Using the fact that for e 3, {k^{2}  k odd} {8t+1} mod 2^{e}, one can show similarly that A(2^{e}) = 2A(2^{e2}) for e 4. With initial conditions one finds A(2)=0, and A(2^{e}) = {2^{e+1}i} for e 2. [message continues]

« Last Edit: Aug 23^{rd}, 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 23^{rd}, 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} _{n}^{ma^2}_{m}^{nb^2} = _{n,m}(A(n)) _{m,n}(A(m)), where _{n,m} Gal((_{n})/) corresponds to _{n} _{n}^{m}. [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 (mn), 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)^{(n1)(m1)/4} {n*}{m*}. Checking the four cases, A(mn) = {mn*} in each case. For m=2^{e}, _{m}(n) is a power of i. If e > 1 is odd, it looks like _{m}(n) = i^{(n1)/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(2^{e}n) = (2n)^{e}_{2^e}(n) {n*} {2^{e+1}i}, which works out to {2^{e+1}n i} in each case. Thus, assuming the formula for , we see that S_{n} = Im A_{n}/n = 1 when n=0,3 mod 4, and S_{n} = 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 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 _{p} .

« Last Edit: Aug 24^{th}, 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 24^{th}, 2007, 1:01am » 
Quote Modify

on Aug 23^{rd}, 2007, 10:25pm, Eigenray wrote:For obvious reasons, I strongly suspect that _{n}(m) is the Jacobi symbol (mn). 
 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} _{mn}^{a}, 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} = _{n}_{m}. For prime powers, note _{1}(a) = 1, and _{p}(a) = (ap) by definition, and finally, since A(p^{e}) = p A(p^{e2}), we have _{p^e} = _{p^(e2)}, and putting it all together shows _{n}(a) = (an). Quote:For m=2^{e}, _{m}(n) is a power of i. If e > 1 is odd, it looks like _{m}(n) = i^{(n1)/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 (/2^{e})^{*}, and the fact that A(2)=0; A(2^{e}) = 2 A(2^{e2}) 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 



