Re: [math-fun] a strange class of algebraic numbers
From: Simon Plouffe <simon.plouffe@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] a strange class of algebraic numbers I have been working on a simple idea that lead to something interesting. Some of you may know that the iteration Z(n+1)= Z(n)^2 + c for some simple c will lead to an algebraic number, in this case, many times to a 4'th degree algebraic number.
--Comments on paper follow. Warning: I'm handicapped by not speaking French. --if it converges (to Z) then Z = Z^2 + c which is a quadratic equation and hence we would get an algebraic number of degree=2. So evidently Simon Plouffe is speaking of something other than mere convergence, perhaps he means converges to a fixed-length attractive cycle, in which case we would generically expect the algebraic numbers that are the cycle elements, each to have degree = 2^k where k is the cycle's length (cardinality). --In the paper, it would help the reader if, whenever you presented one of your cool graphical images, you were to SAY in the caption, what the width & height of the image are, in pixels, i.e, bits. I presume bits in raster order (rightward in rows, row by row going down?). --Also, your first image seems to have 3 colors, green, black, and blue, which means WHAT about the binary bits you are depicting? And the caption says 270 million bits are depicted, which is absurd; I assure you my computer's screen I am using to view this image is not capable of depicting that much information, so I conclude that really, your picture cheats in some manner, i.e. erases a great deal of information. --What I think is interesting about this all, is it demonstrates that the naive guess that some algebraic irrational is going to have "random" bits, is false. Actually for example 1000 / (500 + sqrt(249999)) = = 1.000001000002000005000014000042000132000429001430004862016796058786... in decimal (note Catalan number sequence) so it is well known that "nonrandomness" can happen -- but Plouffe's numbers "stay nonrandom" for much longer than this example does. --I suspect we can explain what is going on using "generating functions." The above Catalan example arose from the Catalan generating function, see my paper http://rangevoting.org/EnvyFree.html which mentions some in section 2. Now if we instead had a generating function F(x) for a different sequence which did not grow exponentially like the Catalan numbers, but rather grew much more slowly, e.g. logarithmically or polynomially, then this kind of example when x was a suitable power of 2 would (in radix 2) produce numbers with nonrandom-looking patterns which extended for a very long way. Observe that ANY algebraic function of x, call it F(x), which has the property that its points of non-analyticity (in the complex x-plane) have modulus=1, will automatically have a Maclaurin series whose coefficients grow at most only polynomially with n. If in fact these coefficients ARE polynomials in n (as opposed to, say, rational functions, which would be unfriendly with binary neatness) then we'd get a "very nonrandom" number. Also, even with exponential coefficient growth not polynomial, if we merely chose x to be very very tiny and binary-friendly, such as x=2^(-65536), again we'd expect very "lacunary" behavior, which would continue for a long way, i.e. at least until the coefficients grew larger than 1/x. And I notice Plouffe is doing just that. Now consider this example: F(x) = 1 + 32 * x^16 * sqrt(x^(-10)+24*sqrt(x^(-4)+4)) Its Maclaurin series is: F(x) = 1+32*x^11+384*x^19+768*x^23-3072*x^27-7680*x^31+23808*x^35+176640*x^39-281088*x^43-3326976* x^47+168192*x^51+70439424*x^55+80647680*x^59-1354681344*x^63-3764190720*x^67+25309811712*x^71+ 118764966912*x^75-404576667648*x^79-3346846172928*x^83+4756985860608*x^87+85558030695936*x^91+ 11334396625920*x^95-2040547018553856*x^99+... the coefficients in this series appear always to be integers (confirmed out to x^500) of both signs, and appear to increase roughly singly-exponentially with n. I presume the fact these coeffs always are integers can be proven by finding a recurrence which they obey. (Lunnon's "number wall" being one way to seek such.) The powers are always 3 mod 4 so it would have been "better" to consider x*F(x) not F(x). But anyhow, this generating function is responsible for Plouffe's example on his page 6. Observe that every point of non-analyticity of F(x) has modulus 1/sqrt(2) = 0.7071067814 or one of these {0.6599289943, 0.6499107662, 0.7141108228} hence I expect the coefficients to grow roughly like (1/0.6499107662)^n and this kind of argument will prove the |coeffs| indeed behave like simply-exponentially growing functions of n. Now consider G(x) = 1 + (1/2) * x^2 * sqrt(2*x^(-2) + 2*sqrt(x^(-4)+16)) which has Maclaurin series G(x) = 1+1*x+2*x^5-10*x^9+84*x^13-858*x^17+9724*x^21-117572*x^25+1485800*x^29 -19389690*x^33+ 259289580*x^37-3534526380*x^41+48932534040*x^45-686119227300*x^49+9723892802904*x^53-\ 139067101832008*x^57+2004484433302736*x^61-29089272078453818*x^65+424672260824486220*x^69-\ 6232570989814602524*x^73+91901608649243484728*x^77-1360850743459951600780*x^81+ 20227837183275796268040*x^85-301706958410170703321400*x^89+4514235708154496146507440*x^93-\ 67737547514382093772858980*x^97+... again with all coefficients apparently integers of both signs, again growing singly-exponentially. The powers are 1 mod 4 so that G(x)*x^3 would have been "better" than G(x). Anyhow, this generating function is responsible for Plouffe's equation 1 on his page 2. --Warren D. Smith.
If we're willing to look at non-algebraic numbers, we can get easy examples of numbers with patterns in their decimal expansions that go on forever; my favorite is the infinite product (1-q)(1-q^2)(1-q^3)(1-q^4)... evaluated at q=0.1. Jim Propp On Tue, Mar 18, 2014 at 2:38 PM, Warren D Smith <warren.wds@gmail.com>wrote:
From: Simon Plouffe <simon.plouffe@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] a strange class of algebraic numbers I have been working on a simple idea that lead to something interesting. Some of you may know that the iteration Z(n+1)= Z(n)^2 + c for some simple c will lead to an algebraic number, in this case, many times to a 4'th degree algebraic number.
--Comments on paper follow. Warning: I'm handicapped by not speaking French.
--if it converges (to Z) then Z = Z^2 + c which is a quadratic equation and hence we would get an algebraic number of degree=2. So evidently Simon Plouffe is speaking of something other than mere convergence, perhaps he means converges to a fixed-length attractive cycle, in which case we would generically expect the algebraic numbers that are the cycle elements, each to have degree = 2^k where k is the cycle's length (cardinality).
--In the paper, it would help the reader if, whenever you presented one of your cool graphical images, you were to SAY in the caption, what the width & height of the image are, in pixels, i.e, bits. I presume bits in raster order (rightward in rows, row by row going down?).
--Also, your first image seems to have 3 colors, green, black, and blue, which means WHAT about the binary bits you are depicting? And the caption says 270 million bits are depicted, which is absurd; I assure you my computer's screen I am using to view this image is not capable of depicting that much information, so I conclude that really, your picture cheats in some manner, i.e. erases a great deal of information.
--What I think is interesting about this all, is it demonstrates that the naive guess that some algebraic irrational is going to have "random" bits, is false. Actually for example 1000 / (500 + sqrt(249999)) = = 1.000001000002000005000014000042000132000429001430004862016796058786... in decimal (note Catalan number sequence) so it is well known that "nonrandomness" can happen -- but Plouffe's numbers "stay nonrandom" for much longer than this example does.
--I suspect we can explain what is going on using "generating functions." The above Catalan example arose from the Catalan generating function, see my paper http://rangevoting.org/EnvyFree.html which mentions some in section 2. Now if we instead had a generating function F(x) for a different sequence which did not grow exponentially like the Catalan numbers, but rather grew much more slowly, e.g. logarithmically or polynomially, then this kind of example when x was a suitable power of 2 would (in radix 2) produce numbers with nonrandom-looking patterns which extended for a very long way.
Observe that ANY algebraic function of x, call it F(x), which has the property that its points of non-analyticity (in the complex x-plane) have modulus=1, will automatically have a Maclaurin series whose coefficients grow at most only polynomially with n. If in fact these coefficients ARE polynomials in n (as opposed to, say, rational functions, which would be unfriendly with binary neatness) then we'd get a "very nonrandom" number.
Also, even with exponential coefficient growth not polynomial, if we merely chose x to be very very tiny and binary-friendly, such as x=2^(-65536), again we'd expect very "lacunary" behavior, which would continue for a long way, i.e. at least until the coefficients grew larger than 1/x. And I notice Plouffe is doing just that. Now consider this example: F(x) = 1 + 32 * x^16 * sqrt(x^(-10)+24*sqrt(x^(-4)+4)) Its Maclaurin series is: F(x) = 1+32*x^11+384*x^19+768*x^23-3072*x^27-7680*x^31+23808*x^35+176640*x^39-281088*x^43-3326976*
x^47+168192*x^51+70439424*x^55+80647680*x^59-1354681344*x^63-3764190720*x^67+25309811712*x^71+
118764966912*x^75-404576667648*x^79-3346846172928*x^83+4756985860608*x^87+85558030695936*x^91+ 11334396625920*x^95-2040547018553856*x^99+... the coefficients in this series appear always to be integers (confirmed out to x^500) of both signs, and appear to increase roughly singly-exponentially with n. I presume the fact these coeffs always are integers can be proven by finding a recurrence which they obey. (Lunnon's "number wall" being one way to seek such.) The powers are always 3 mod 4 so it would have been "better" to consider x*F(x) not F(x). But anyhow, this generating function is responsible for Plouffe's example on his page 6. Observe that every point of non-analyticity of F(x) has modulus 1/sqrt(2) = 0.7071067814 or one of these {0.6599289943, 0.6499107662, 0.7141108228} hence I expect the coefficients to grow roughly like (1/0.6499107662)^n and this kind of argument will prove the |coeffs| indeed behave like simply-exponentially growing functions of n.
Now consider G(x) = 1 + (1/2) * x^2 * sqrt(2*x^(-2) + 2*sqrt(x^(-4)+16)) which has Maclaurin series G(x) = 1+1*x+2*x^5-10*x^9+84*x^13-858*x^17+9724*x^21-117572*x^25+1485800*x^29 -19389690*x^33+
259289580*x^37-3534526380*x^41+48932534040*x^45-686119227300*x^49+9723892802904*x^53-\
139067101832008*x^57+2004484433302736*x^61-29089272078453818*x^65+424672260824486220*x^69-\
6232570989814602524*x^73+91901608649243484728*x^77-1360850743459951600780*x^81+
20227837183275796268040*x^85-301706958410170703321400*x^89+4514235708154496146507440*x^93-\ 67737547514382093772858980*x^97+... again with all coefficients apparently integers of both signs, again growing singly-exponentially. The powers are 1 mod 4 so that G(x)*x^3 would have been "better" than G(x). Anyhow, this generating function is responsible for Plouffe's equation 1 on his page 2.
--Warren D. Smith.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hello, I intend of course to make an english version of this very short note. The graphic is in false colors, of course there are only 2 colors : white and light blue, depending on the screen and the magnification factor. I presumed that most people have access to a kind of mathematica, maple, or pari-gp or mpmath like program in order to verify that the claim is authentic, when f(n) is evaluated at n=1000000 or 2^20 the pattern pushes up to 2^40 which is 1000 billion binary digits. I made it that way so that we could see the pattern in 1 image. To see the image with whatever system you may have, I use Photoshop which can view an image of up to 90 billion pixels : 300000 x 300000. Here is the recipe : Prepare a binary file or if you want a file containing only <0> and <1> with no CR or LF , only plain binary file. Change the suffix of the file to the_file.raw , in raw format. Open Photoshop and open the file , it will then ask you for the width and length, then type the 2 numbers. It is now necessary to adjust the tone and brightness or contrast of the image. There are then a variety of ways to do that. Now about a possible generating function, well I know a bit about this subject, in plain English : there are no known formulas that would exhibit a pattern up to the billion'th term in terms of analytical or ordinary generating function ans still be visible for an ordinary eye, the example with Catalan numbers is way too fast growing , the n'th term is proportional to 4^n, this is way too big. The billionth Catalan number has hundreds of millions digits wide, it cannot be something simple, the complexity grows exponentially. As I said before, there is a wide grey area where the pattern is clearly visible and still cannot be expressed simply with a simple generating function or rational or a certain distance to irrationals, the pattern is there but cannot be simply explained in analytical terms, how to do you explain that the formula for f(2^20) can still be visible after 1000 billion binary digits ?? Sorry for the crude and french language results, but still the pattern remains and it is still very very persistent. Best regards, Simon Plouffe
participants (3)
-
James Propp -
Simon Plouffe -
Warren D Smith