[math-fun] rationalize exp(%i*x), for floating point x.
I guess this is a continuation of my rant of one year ago re rationalizing a complex number instead of rationalizing its real & imaginary parts separately. I'm interested in approximations to exp(%i*x), for real floating point x, but it is essential that cabs() of the result is identically 1. One way this can be done is s = rationalize(sin(x/2)), c = rationalize(cos(x/2)) z = ((c^2-s^2) + %i*2*c*s)/(c^2+s^2) (clear factions with 'factor'). We can compute the accuracy of this approximation by xp = atan2(2*c*s,c^2-s^2) and compare xp with x. Unfortunately, unless the denominators get pretty large, x isn't all that close to xp (considering the worse case error around the unit circle). Can anyone think of a better method?
Hello, there is a way with PSLQ, it can handle complex numbers. so you can find for example, the best integers that would approximate a zero to the vector : [ln(1 + I), Pi, exp(1)], up to a certain precision, in this case , up to 6 digits: with [-23 + 41 I, 5 - 23 I, 9 + 28 I], Is this what you are looking for ? another example : with [ln(1 + I), Pi I, exp(I)] you would get : [11 + 88 I, -4 - 30 I, -38 + 10 I] which is close to -0.0012 - 0.0014 I. as a rule of thumb, the 6 digits does give a 3 digits approximation, you need to double the working digits. Best regards, Simon Plouffe
It occurred to me that this is a classical problem of factoring with Gaussian integers. The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented. In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1. Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r. At 04:21 PM 8/12/2013, Henry Baker wrote:
I guess this is a continuation of my rant of one year ago re rationalizing a complex number instead of rationalizing its real & imaginary parts separately.
I'm interested in approximations to exp(%i*x), for real floating point x, but it is essential that cabs() of the result is identically 1.
One way this can be done is
s = rationalize(sin(x/2)), c = rationalize(cos(x/2))
z = ((c^2-s^2) + %i*2*c*s)/(c^2+s^2) (clear factions with 'factor').
We can compute the accuracy of this approximation by
xp = atan2(2*c*s,c^2-s^2)
and compare xp with x.
Unfortunately, unless the denominators get pretty large, x isn't all that close to xp (considering the worse case error around the unit circle).
Can anyone think of a better method?
I did some simple calculations just to get a handle on the size of integers involved. Suppose we want to plot 100,000 points equally spaced around a circle of radius R on a square pixel grid. Suppose we want the 'second' point R*(cos(2pi/N)+i*sin(2pi/N) to be exactly 1 pixel different in its X-coordinate from the 'first' point R*(cos(0)+i*sin(0)). Then R*(cos(0)-cos(2pi/N))=1. Now if we Taylor cos(x)~1-x^2/2, then we can solve for R in terms of N: 2*R = D = (N/pi)^2 R = 506,605,918, i.e., the grid must be 2^30 pixels wide & 2^30 pixels high. It is also interesting to see how far above the 'first' pixel the 'second' pixel lies: Tayloring sin(x) ~ x, R*sin(2pi/N) ~ R*(2pi/N) = N/pi. For N=100000, R*sin(2pi/N) ~ 31,831. So, exp(i2pi/100000) ~ 506,605,917 + 31,831*i = (R-1) + 31,831*i = Z Computing the convex hull of a regular n-gon of 100,000 points requires 30-bit integers just to accurately represent the points; note that these coordinate values are approx. twice the number of bits required to represent N itself. But this number Z that we just found isn't even Pythagorean. We can get a Pythagorean number for double the angle (i.e., 4pi/N) by squaring Z and dividing by its norm: Z2 = Z^2/(Z*Z') (Z' is conjugate of Z) Unfortunately, this denominator 128,324,778,076,311,725 requires 57 bits to represent; i.e., approx. double the number of bits of Z's denominator. So, attempting to utilize Pythagorean numbers for representing uniformly spaced points around the circle seems to _double_ the number of bits involved. Doubling the size of the numbers seems a bit extreme; are Pythagorean triples really that rare? I hope that I'm wrong about this.
Every Pythagorean triple is some multiple of a permutation of (p^2 + q^2, p^2 - q^2, 2*p*q) for integer p,q . The number of such triples with hypoteneuse at most Z equals (roughly) the number of lattice points within a circle of radius sqrt(Z) , hence is linear in Z . WFL On 8/14/13, Henry Baker <hbaker1@pipeline.com> wrote:
I did some simple calculations just to get a handle on the size of integers involved.
Suppose we want to plot 100,000 points equally spaced around a circle of radius R on a square pixel grid.
Suppose we want the 'second' point R*(cos(2pi/N)+i*sin(2pi/N) to be exactly 1 pixel different in its X-coordinate from the 'first' point R*(cos(0)+i*sin(0)).
Then R*(cos(0)-cos(2pi/N))=1. Now if we Taylor cos(x)~1-x^2/2, then we can solve for R in terms of N:
2*R = D = (N/pi)^2
R = 506,605,918, i.e., the grid must be 2^30 pixels wide & 2^30 pixels high.
It is also interesting to see how far above the 'first' pixel the 'second' pixel lies:
Tayloring sin(x) ~ x,
R*sin(2pi/N) ~ R*(2pi/N) = N/pi. For N=100000, R*sin(2pi/N) ~ 31,831.
So, exp(i2pi/100000) ~ 506,605,917 + 31,831*i = (R-1) + 31,831*i = Z
Computing the convex hull of a regular n-gon of 100,000 points requires 30-bit integers just to accurately represent the points; note that these coordinate values are approx. twice the number of bits required to represent N itself.
But this number Z that we just found isn't even Pythagorean.
We can get a Pythagorean number for double the angle (i.e., 4pi/N) by squaring Z and dividing by its norm:
Z2 = Z^2/(Z*Z') (Z' is conjugate of Z)
Unfortunately, this denominator 128,324,778,076,311,725 requires 57 bits to represent; i.e., approx. double the number of bits of Z's denominator.
So, attempting to utilize Pythagorean numbers for representing uniformly spaced points around the circle seems to _double_ the number of bits involved.
Doubling the size of the numbers seems a bit extreme; are Pythagorean triples really that rare?
I hope that I'm wrong about this.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Some interesting relevant references I found online: Waterhouse, William C. "Continued Fractions and Pythagorean Triples". May 1992. Something about palindromic continued fractions & Pythagorean Triples. Don't completely understand it yet. From: http://www.fq.math.ca/Scanned/30-2/waterhouse.pdf Size: 913 KB (934,909 bytes) Faessler, Albert. "Multiple Pythagorean Number Triples". IMA Preprint Series #438, August 1988. Referenced by Wikipedia article on Pythagorean Triples. Very nice & pertinent discussion of the distribution of Pythagorean triples. From: http://conservancy.umn.edu/bitstream/4878/1/438.pdf Size: 484 KB (495,306 bytes) At 05:31 PM 8/12/2013, Henry Baker wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
At 04:21 PM 8/12/2013, Henry Baker wrote:
I guess this is a continuation of my rant of one year ago re rationalizing a complex number instead of rationalizing its real & imaginary parts separately.
I'm interested in approximations to exp(%i*x), for real floating point x, but it is essential that cabs() of the result is identically 1.
One way this can be done is
s = rationalize(sin(x/2)), c = rationalize(cos(x/2))
z = ((c^2-s^2) + %i*2*c*s)/(c^2+s^2) (clear factions with 'factor').
We can compute the accuracy of this approximation by
xp = atan2(2*c*s,c^2-s^2)
and compare xp with x.
Unfortunately, unless the denominators get pretty large, x isn't all that close to xp (considering the worse case error around the unit circle).
Can anyone think of a better method?
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
I did a few things close to what you describe. It can be downloaded here http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density. http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf is the same idea, restricted to Gaussian primes. The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients. Olivier
On 8/15/13, Olivier Gerard <olivier.gerard@gmail.com> wrote:
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
I did a few things close to what you describe. It can be downloaded here
http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf
I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density.
http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf
is the same idea, restricted to Gaussian primes.
The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients.
Olivier _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the same thing for the sphere quite recently: the "no-mans lands" are circular discs instead. [Unfortunately, I have no recollection of why I did it; so cannot track down the --- rather pretty --- pictorial results.] It does emphasise --- relevantly to what Henry is doing, perhaps --- that points equidistant from the centre and circumference of such a disc are very badly approximated by rational points! WFL
In this paper by Glyn Harman: http://matwbn.icm.edu.pl/ksiazki/aa/aa53/aa5323.pdf he proves (on page 210) that almost all real numbers have infinitely many convergents from their continued fraction expansion whose numerators and denominators are both sums of two integral squares. However, this theorem appears not to be able to address any individual real number! Victor On Thu, Aug 15, 2013 at 3:53 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 8/15/13, Olivier Gerard <olivier.gerard@gmail.com> wrote:
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
I did a few things close to what you describe. It can be downloaded here
http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf
I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density.
http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf
is the same idea, restricted to Gaussian primes.
The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients.
Olivier _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the same thing for the sphere quite recently: the "no-mans lands" are circular discs instead. [Unfortunately, I have no recollection of why I did it; so cannot track down the --- rather pretty --- pictorial results.]
It does emphasise --- relevantly to what Henry is doing, perhaps --- that points equidistant from the centre and circumference of such a disc are very badly approximated by rational points!
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
2-phi (= 1/phi^2 = .382-) is an example. The typical convergent is Fib(n)/Fib(n+2), e.g. 34/89. Fib(odd) is the sum of two squares, so at least half of the convergents for 2-phi fill the bill. Rich --------- Quoting Victor Miller <victorsmiller@gmail.com>:
In this paper by Glyn Harman: http://matwbn.icm.edu.pl/ksiazki/aa/aa53/aa5323.pdf he proves (on page 210) that almost all real numbers have infinitely many convergents from their continued fraction expansion whose numerators and denominators are both sums of two integral squares.
However, this theorem appears not to be able to address any individual real number!
Victor
On Thu, Aug 15, 2013 at 3:53 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 8/15/13, Olivier Gerard <olivier.gerard@gmail.com> wrote:
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
I did a few things close to what you describe. It can be downloaded here
http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf
I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density.
http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf
is the same idea, restricted to Gaussian primes.
The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients.
Olivier _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the same thing for the sphere quite recently: the "no-mans lands" are circular discs instead. [Unfortunately, I have no recollection of why I did it; so cannot track down the --- rather pretty --- pictorial results.]
It does emphasise --- relevantly to what Henry is doing, perhaps --- that points equidistant from the centre and circumference of such a disc are very badly approximated by rational points!
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Tracked it down: plot shows rational points [x/w, y/w, z/w] on unit sphere with w^2 + x^2 + y^2 + z^2 < 2 s^2 , where s = 199 . See https://www.dropbox.com/s/7u73fm17o5av7fd/rat_pts_sph.gif Note the ominously large "no-man's land" disc centred on an axis (I presume); and the intriguing pattern of (orthogonal?) circles traced by the points surrounding its boundary. Fred Lunnon On 8/16/13, rcs@xmission.com <rcs@xmission.com> wrote:
2-phi (= 1/phi^2 = .382-) is an example. The typical convergent is Fib(n)/Fib(n+2), e.g. 34/89. Fib(odd) is the sum of two squares, so at least half of the convergents for 2-phi fill the bill.
Rich
--------- Quoting Victor Miller <victorsmiller@gmail.com>:
In this paper by Glyn Harman: http://matwbn.icm.edu.pl/ksiazki/aa/aa53/aa5323.pdf he proves (on page 210) that almost all real numbers have infinitely many convergents from their continued fraction expansion whose numerators and denominators are both sums of two integral squares.
However, this theorem appears not to be able to address any individual real number!
Victor
On Thu, Aug 15, 2013 at 3:53 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 8/15/13, Olivier Gerard <olivier.gerard@gmail.com> wrote:
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
I did a few things close to what you describe. It can be downloaded here
http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf
I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density.
http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf
is the same idea, restricted to Gaussian primes.
The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients.
Olivier _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the same thing for the sphere quite recently: the "no-mans lands" are circular discs instead. [Unfortunately, I have no recollection of why I did it; so cannot track down the --- rather pretty --- pictorial results.]
It does emphasise --- relevantly to what Henry is doing, perhaps --- that points equidistant from the centre and circumference of such a disc are very badly approximated by rational points!
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That's a beautiful and intriguing map of the Moon that Fred posted. Those areas of avoidance almost look like parts of a Petri dish where antibiotics keep a mold from growing. It looks as if it would take a lot of mathematical explaining to understands why it looks that way. A much less interesting pattern, but interesting nonetheless, is this Wikipedia plot of all Pythagorean legs (a,b) of a triple a^2 + b^2 = c^2 for all |a|, |b| <= 6000: < http://upload.wikimedia.org/wikipedia/commons/9/97/Pythagorean_triple_scatte... >. --Dan On 2013-08-15, at 7:21 PM, Fred Lunnon wrote:
Tracked it down: plot shows rational points [x/w, y/w, z/w] on unit sphere with w^2 + x^2 + y^2 + z^2 < 2 s^2 , where s = 199 . See
https://www.dropbox.com/s/7u73fm17o5av7fd/rat_pts_sph.gif
Note the ominously large "no-man's land" disc centred on an axis (I presume); and the intriguing pattern of (orthogonal?) circles traced by the points surrounding its boundary.
Fred Lunnon
On 8/16/13, rcs@xmission.com <rcs@xmission.com> wrote:
2-phi (= 1/phi^2 = .382-) is an example. The typical convergent is Fib(n)/Fib(n+2), e.g. 34/89. Fib(odd) is the sum of two squares, so at least half of the convergents for 2-phi fill the bill.
Rich
--------- Quoting Victor Miller <victorsmiller@gmail.com>:
In this paper by Glyn Harman: http://matwbn.icm.edu.pl/ksiazki/aa/aa53/aa5323.pdf he proves (on page 210) that almost all real numbers have infinitely many convergents from their continued fraction expansion whose numerators and denominators are both sums of two integral squares.
However, this theorem appears not to be able to address any individual real number!
Victor
On Thu, Aug 15, 2013 at 3:53 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 8/15/13, Olivier Gerard <olivier.gerard@gmail.com> wrote:
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
It occurred to me that this is a classical problem of factoring with Gaussian integers.
The best 'denominators' are the most composite of Gaussian integers, so that you have the widest variety of angles represented.
In particular, pick denominators which are the product of 2 with all of the (rational integer) primes of the form 4n+1.
Turn on a light at the origin of the complex plane, put up thin barriers at every Gaussian integral point, and distribute some photograhic film around the circumference of a circle of radius r. Wherever the light shines through the most, those are angles that aren't well represented. In particular, I'm interested in the largest _gap_ in this circle for a given radius r; the size of that gap indicates the worst case for that radius r.
I did a few things close to what you describe. It can be downloaded here
http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf
I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density.
http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf
is the same idea, restricted to Gaussian primes.
The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients.
Olivier _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the same thing for the sphere quite recently: the "no-mans lands" are circular discs instead. [Unfortunately, I have no recollection of why I did it; so cannot track down the --- rather pretty --- pictorial results.]
It does emphasise --- relevantly to what Henry is doing, perhaps --- that points equidistant from the centre and circumference of such a disc are very badly approximated by rational points!
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Even better picture (and explanation) in this paper: Faessler, Albert. "Multiple Pythagorean Number Triples". IMA Preprint Series #438, August 1988. Referenced by Wikipedia article on Pythagorean Triples. Very nice & pertinent discussion of the distribution of Pythagorean triples. From: http://conservancy.umn.edu/bitstream/4878/1/438.pdf Size: 484 KB (495,306 bytes) At 11:37 PM 8/15/2013, Dan Asimov wrote:
That's a beautiful and intriguing map of the Moon that Fred posted. Those areas of avoidance almost look like parts of a Petri dish where antibiotics keep a mold from growing. It looks as if it would take a lot of mathematical explaining to understands why it looks that way.
A much less interesting pattern, but interesting nonetheless, is this Wikipedia plot of all Pythagorean legs (a,b) of a triple a^2 + b^2 = c^2 for all |a|, |b| <= 6000:
< http://upload.wikimedia.org/wikipedia/commons/9/97/Pythagorean_triple_scatte... >.
It generalizes nicely to roots of polynomials with small coefficients. http://www.math.ucr.edu/home/baez/roots/ On Fri, Aug 16, 2013 at 12:37 AM, Dan Asimov <dasimov@earthlink.net> wrote:
That's a beautiful and intriguing map of the Moon that Fred posted. Those areas of avoidance almost look like parts of a Petri dish where antibiotics keep a mold from growing. It looks as if it would take a lot of mathematical explaining to understands why it looks that way.
A much less interesting pattern, but interesting nonetheless, is this Wikipedia plot of all Pythagorean legs (a,b) of a triple a^2 + b^2 = c^2 for all |a|, |b| <= 6000:
< http://upload.wikimedia.org/wikipedia/commons/9/97/Pythagorean_triple_scatte... >.
--Dan
On 2013-08-15, at 7:21 PM, Fred Lunnon wrote:
Tracked it down: plot shows rational points [x/w, y/w, z/w] on unit sphere with w^2 + x^2 + y^2 + z^2 < 2 s^2 , where s = 199 . See
https://www.dropbox.com/s/7u73fm17o5av7fd/rat_pts_sph.gif
Note the ominously large "no-man's land" disc centred on an axis (I presume); and the intriguing pattern of (orthogonal?) circles traced by the points surrounding its boundary.
Fred Lunnon
On 8/16/13, rcs@xmission.com <rcs@xmission.com> wrote:
2-phi (= 1/phi^2 = .382-) is an example. The typical convergent is Fib(n)/Fib(n+2), e.g. 34/89. Fib(odd) is the sum of two squares, so at least half of the convergents for 2-phi fill the bill.
Rich
--------- Quoting Victor Miller <victorsmiller@gmail.com>:
In this paper by Glyn Harman: http://matwbn.icm.edu.pl/ksiazki/aa/aa53/aa5323.pdf he proves (on page 210) that almost all real numbers have infinitely many convergents from their continued fraction expansion whose numerators and denominators are both sums of two integral squares.
However, this theorem appears not to be able to address any individual real number!
Victor
On Thu, Aug 15, 2013 at 3:53 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
On 8/15/13, Olivier Gerard <olivier.gerard@gmail.com> wrote:
On Tue, Aug 13, 2013 at 2:31 AM, Henry Baker <hbaker1@pipeline.com> wrote:
> It occurred to me that this is a classical problem of factoring with > Gaussian integers. > > The best 'denominators' are the most composite of Gaussian integers, > so > that you have the widest > variety of angles represented. > > In particular, pick denominators which are the product of 2 with all > of > the (rational integer) primes of the form 4n+1. > > Turn on a light at the origin of the complex plane, put up thin > barriers > at every Gaussian integral point, > and distribute some photograhic film around the circumference of a circle > of radius r. Wherever the > light shines through the most, those are angles that aren't well > represented. In particular, I'm interested > in the largest _gap_ in this circle for a given radius r; the size of > that > gap indicates the worst case > for that radius r. > >
I did a few things close to what you describe. It can be downloaded here
http://list.seqfan.eu/extfiles/Gaussian%20Shadow.pdf
I draw a thin blue line through every Gaussian integer (here with absolute value less than 120) and I display a corona between two concentric circle (here 50 and 35) so that one can appreciate visually the resulting density.
http://list.seqfan.eu/extfiles/Gaussian%20Prime%20Shadow.pdf
is the same idea, restricted to Gaussian primes.
The angles less represented are the ones close to exact rational approximation, it reminds of the noman's land around a potent bacterial colony. You find similar isolation around algebraic integers with small coefficients.
Olivier _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I did the same thing for the sphere quite recently: the "no-mans lands" are circular discs instead. [Unfortunately, I have no recollection of why I did it; so cannot track down the --- rather pretty --- pictorial results.]
It does emphasise --- relevantly to what Henry is doing, perhaps --- that points equidistant from the centre and circumference of such a disc are very badly approximated by rational points!
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
"HB" == Henry Baker <hbaker1@pipeline.com> writes:
HB> I guess this is a continuation of my rant of one year ago re HB> rationalizing a complex number instead of rationalizing its real & HB> imaginary parts separately. Is that to say that, for a library offering "complex rationals", you'd prefer ratios of gaussian integers to cartesian or polar tuples of Q? Or did I parse backwards? -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
Well, there's actually 2 different questions here: 1. Which complex rational do you choose? 2. How do you represent the answer? I'll answer #2 first. You have several choices for how to represent complex rationals: a) a pair of rationals in reduced (n/d) form, b) a pair of integers with a common natural number denominator, c) a ratio of Gaussian integers (N/D) in reduced (no Gaussian integer factors) form. a) is often used in Common Lisp implementations, and may 'save space' if the real & imaginary parts are incommensurable. However, the moment you try to do very much calculation, you have to put the real & imaginary parts over a common denominator, so b) might seem preferable. c) is an interesting representation suggested in http://home.pipeline.com/~hbaker1/Gaussian.html I would tend to recommend b) for most calculational purposes, even though many/most integers will overflow into 'bignums'. Regarding question #2, I hate solving polynomial equations and getting answers like x = 1.000 + 5.3e-15 I, where I know darn well that x is actually real. If we use a continued fraction algorithm on the whole complex number, rather than the real and imaginary parts separately, we can get rid of these pesky things like '5.3e-15 I' above by producing a complex rational which is the closest _in the complex domain_. The following is from an email dated 7/11/2012: --------------------------------------- I've hated those pesky imaginary parts ever since Fortran has had complex numbers. I think I finally know how to get rid of them! ------ Here's a much better explanation for what I was trying to do: I've been hacking a new version of the Common Lisp & Maxima "rationalize" function which produces the worst rational approximation to a complex number that falls within epsilon of that complex number. In the case of Maxima, the epsilon is set by the global variable "ratepsilon". The traditional Euclidean algorithm for this process focuses on the number itself (which I call c), and only later worries about the epsilon and the radius of convergence. My algorithm starts with the _circle_ whose center is the given complex number c and whose real radius is r; we can denote this circle by (c,r). Since translation and inversion in the complex plane both take circles to circles (more accurately, "generalized circles" to "generalized circles"), we can perform a Euclidean procedure on the _circle_ (c,r) itself. At each stage we keep track of the transformations (translations & inversions), so that we can recover the original circle, if necessary. We first look at the given circle (c,r). If there is a (Gaussian) integer point within this circle, then we are done, because such a point is rational, so this is our answer. If we compute cr=round(c) (= round(realpart(c))+i*round(imagpart(c))), then this number cr is (one of) the closest integer points to c. If cr is "inside" the circle (c,r), then we are done. Now if r>sqrt(2)/2, then cr _has_ to be inside the circle (c,r). So we now consider the case where cr is not inside (c,r). After translating the origin to cr, we know that this new center is within sqrt(2)/2 from the origin -- i.e., inside the unit circle. We then invert the given circle in the unit circle, which will put the center of that new circle outside the unit circle. Furthermore, the radius of that new circle will grow bigger. We can now compute the closest integral point to the center of that new circle, and so forth. At each of these Euclidean steps, the circle radius grows larger, and must eventually enclose an integral point, at which time we invert the sequence of transformations to compute the final rational answer. This answer will be rational, because the integral point was transformed by inversions and translations by (Gaussian) integers. This discussion is not a _proof_, but shows how the algorithm was conceived. Here's the algorithm in Maxima: euclid(zc,m):= block([q,iqmat], /* zc is input circle in Schwerdtfeger's representation */ /* m accumulates transforms; m starts out as the 2x2 identity matrix */ /* Original circle is always transpose(m^^-1).zc.conjugate(m^^-1) */ q:cround(center(zc)), if is(inside(q,zc)) then m.matrix([q],[1]) else (iqmat:matrix([1,q],[0,1]), euclid(transpose(iqmat.imat).zc.conjugate(iqmat.imat),m.iqmat.imat))); imat:matrix([0,1],[1,0]); cround(z):=round(realpart(z))+%i*round(imagpart(z)); This produces is a column vector matrix([num],[denom]); the result is num/denom. euclid(gcircle(%pi,1.0e-7),ident(2)) produces [ - 122453 ] [ ] [ - 38978 ] = 122453/38978, which is within 10^-7 of pi. (%i13) abs((-122453)/(-38978)-%pi),numer; (%o13) 3.9724384226502707E-8 We use Hans Schwerdtfeger's representation for generalized circles as 2x2 Hermitian matrices. See this Wikipedia article for more details. http://en.wikipedia.org/wiki/Generalised_circle /* We test for "inside" by substituting the point into the equation. */ inside(w,c):=is(equation(c,w)<=0); Although very elegant, there is a problem with Schwerdtfeger's representation for circles: the squared radius of the circle is computed by the difference of two large quantities, so when we approach the limit of machine precision, we may inadvertently end up with a negative number, and hence an _imaginary_ radius! This example shows the problem in the lower right hand corner: (%i1) gcircle(%pi,1.0e-7); [ 1 - %pi ] (%o1) [ ] [ 2 ] [ - %pi %pi - 9.9999999999999984E-15 ] Perhaps this problem can be ameliorated with a slightly different representation for circles. Using the closest integer ("round" = least absolute remainder) isn't new. I don't have my Knuth V.I handy, but I think that using "round" instead of "floor" is several hundred years old. Rounding is also necessary for convergence in the complex plane -- e.g., for Gaussian integer gcd's. See this discussion: http://home.pipeline.com/~hbaker1/Gaussian.html BTW, the inverse of a circle (C,r) is the circle (C',r)/(CC'-r^2), and as you can imagine, things get very hairy when r^2=CC' -- i.e., when the circle goes directly through the origin. If the circle to be inverted encloses the origin, then its inverse will be "inside out" -- i.e., it will enclose infinity (oo), but exclude the origin. For small r, one could approximate 1/(CC'-r^2) with a Taylor expansion: 1/(CC'-r^2) ~ 1/(CC')(1+r^2/(CC')+...) So if we choose a smaller radius to take account of the approximation for the center point, then we might be able to use this Taylor expansion until r^2>1/2, which is all we will ever need. ---- Note that the sequence of partial quotients is slightly different from the classical algorithm. In particular, my algorithm might be "too" good, in the sense that it might not return the _worst_ approximation that fits within the original circle, but one that is "one click" better. If you are really looking for the worst approximation -- i.e., the one with the smallest denominator, my algorithm may not produce it. ---- It should be possible to get an estimate on the roundoff error involved in these procedures by carrying out 2 parallel computations: the traditional one using floating point numbers, and mine using rational numbers; we just have to agree on the partial quotients. Since the Mobius transform is rational and hence exact, if we ever arrive at a situation where the point to be approximated no longer lies "inside" its own circle, then we have clear evidence of roundoff error, and we must stop -- this is the best approximation we're going to be able to get within the limits of machine precision. ------ Hope this is more understandable. At 12:11 PM 8/14/2013, James Cloos wrote:
"HB" == Henry Baker <hbaker1@pipeline.com> writes:
HB> I guess this is a continuation of my rant of one year ago re HB> rationalizing a complex number instead of rationalizing its real & HB> imaginary parts separately.
Is that to say that, for a library offering "complex rationals", you'd prefer ratios of gaussian integers to cartesian or polar tuples of Q?
Or did I parse backwards?
-JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
participants (9)
-
Dan Asimov -
Fred Lunnon -
Henry Baker -
James Cloos -
Mike Stay -
Olivier Gerard -
rcs＠xmission.com -
Simon Plouffe -
Victor Miller