March 2014 - mathfun@mailman.xmission.com

Re: [math-fun] a strange class of algebraic numbers
by Warren D Smith 18 Mar '14

18 Mar '14

It appears J.Shallit & I both came up with approx. same idea -- generating functions -- to explain Simon Plouffe's weird numbers. If x were something like 2^(-10000) and if the coeffs in the generating function grew like, say, 1.5^n, then this could explain nonrandomness out to about the (10^8)th bit, corresponding to about the (10^4)th series-coefficient. This is approximately right (i.e. that is about how far Plouffe's nonrandomness extended), so it looks to me like my/Shallit's explanations were correct. Now, thinking a bit more: can we now purposefully design even more dramatic examples than Plouffe had found? For that, there are several avenues to pursue. 1. If the recurrence (which I have not yet worked out) obeyed by the generating function coefficients happens to be a binary-friendly recurrence, e.g. itself involving coefficients which are, say, powers of 2, then this might be able to produce even-further-extending nonrandom patterns. 2. Another (related) possible avenue to look at, is double generating functions F(x,y). 3. If we can design the function F(x) to get series-coefficient growth which is only polynomial(n), not exponential, then we will get nonrandomness extending tremendously further than in Plouffe's numbers. The following kind of function of x: F(x,a,b) = (1-x^a)^(-b) where a,b, are positive integers, and sums and products of such functions, all have got series coeffs which automatically grow only polynomially with n and automatically are all-integer. Also, if b is half-integer such as b=5/2, then F(2*x,a,b) or F(4*x,a,b) have all-integer coefficients too, but that grow exponentially. The growth constants are however exactly powers of 2, which acts a lot like non-growth (i.e. growthconst=1) from the view of binary-friendliness. Therefore these F's will yield examples far more dramatically-long nonrandom than Plouffe's examples.

1 0

Re: [math-fun] a strange class of algebraic numbers
by Warren D Smith 18 Mar '14

18 Mar '14

> From: Simon Plouffe <simon.plouffe(a)gmail.com> > To: math-fun <math-fun(a)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.

3 2

[math-fun] Another theory on the 777
by Bernie Cosell 18 Mar '14

18 Mar '14

Warren's arrogance and certainty in the face of essentially no information [not to mention rudeness] notwithstanding, here's another analysis (which differs rather dramatically from Warren's analysis). Maybe he should send a letter to wired calling the guy that made the conjectures in the article an ill-informed idiot... <http://www.wired.com/autopia/2014/03/mh370-electrical-fire/> /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

2 1

[math-fun] a strange class of algebraic numbers
by Simon Plouffe 18 Mar '14

18 Mar '14

Hello, 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. This is quite puzzling for many reasons, first the convergence to a constant when it happens is geometric, but ??, since we know that the Mandelbrot set is self-similar , what if we take a series of very close rationals (the c's in the equation) , can it be that these numbers would also show some patterns in their binary ? or decimal expansion ? We can construct a series of rational values and from that get their algebraic equivalent when the formula Z(n+1) = Z(n)^2+c , does converge and then what..., The question is naive, there is no connection between these two things, but still I was very puzzled by the idea. So , as usual, since I can't completely understand this phenomena, at the least I made some tables of it, a lot of them, and then, I looked at these numbers, in binary in search of a pattern. By looking at those algebraic numbers I saw, or had the intuition that something is going on with some valuesand found something. Some algebraic numbers of degree 4 have a very definite and persistent pattern in their binary expansion, the pattern does not go to infinity BUT for some values, it can extend to the first 1000 billion binary digits. , much more than the ordinary approximation. These crazy numbers are chaotic in their continued fractiontoo, not onlythat, the log and the exp is also crazy. see for yourself : http://www.plouffe.fr/simon/On%20a%20strange%20class%20of%20algebraic%20num… This pattern is astonishing. The one presented on page 1 of the article goes to at least the first 270 million bits, the numbers are f(n) = 1+1/4*(2*4^n+2*(16^n+1)^(1/2))^(1/2)/(2^n)^2, if n=8192, it gives a pattern that goes for 270 million bits, and for n=1048576, to 1000 billion digits. a very good question now : can this be generated with a cellular automata ? I submitted the article to the arxiv site. As far as I know, this is not known, I searched for some insights with the work of Douady and Hubbard, nothing found, interesting but not definite, maybe it needs a closer look, Best regards, Simon Plouffe

4 6

[math-fun] gravitational waves from big bang?
by Warren D Smith 17 Mar '14

17 Mar '14

http://www.scientificamerican.com/article/gravity-waves-cmb-b-mode-polariza… http://www.nature.com/nature/journal/v420/n6917/abs/nature01269.html Ron Cowen: Telescope captures view of gravitational waves Images of the infant Universe reveal evidence for rapid inflation after the Big Bang. Nature 507 (17 March 2014) 281-282 http://www.nature.com/news/telescope-captures-view-of-gravitational-waves-1… The paper all that hype is based on appears to be this manuscript: http://bicepkeck.org/b2_respap_arxiv_v1.pdf I think their point is supposed to be, that we have yet another angular-statistics confirmation of some of the predictions of "inflationary cosmology" which yet again seems, at least naively, to be very impressive theory-observation agreement. I personally never found this kind of thing to be as impressive as the hype, because whatever I've seen has not compared different possible theories versus the evidence; only one theory. E.g. perhaps these impressive agreements might actually be predicted pretty universally by a much wider class of cosmic models; and if not I haven't seen a convincing and clear demonstration of not, nor a clear understanding of just what class of models are permitted and which not. In short, it should be about discriminating among theories, not about exhibiting agreement with one theory. But anyhow, at present I have not read this paper; that was just a general purpose rant. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

[math-fun] A005130 complete asymptotic
by Bill Gosper 17 Mar '14

17 Mar '14

Sorry, with G11 looming, I had not time to make it shorter: (1/(36*n*(1 + n)))*(-3 + 3*n*(-3*n*(4 + n*(7 + 2*n)) + 4*n*z1 + 4*(1 + z1)) + n*(4*ArcCoth[3*n] - 18*Log[n] + 84*Log[1 + n] - 69*Log[2 + n] + 4*Log[-1 + 3*n] - 3*Log[-1 + 9*n^2] + Log[(6144*Pi^6)/ Gamma[1/6]^12] + n*(15*Log[2] - 29*Log[3] - 54*Log[n] + 123*Log[1 + n] - 72*Log[2 + n] - 10*Log[-1 + 3*n] + 14*Log[1 + 3*n] + 3*n*(Log[729] - 30*Log[n] + Log[1 + n] + 17*Log[2 + n] - 8*Log[-8 + 24*n] + 10*Log[-1 + 9*n^2] + 6*n*(2*n*ArcCoth[3 + 2*n] - 3*Log[n*(1 + n)] + 4*Log[(2 + n)/2] + Log[-3 + 27*n^2])) - 3*Log[((-1 + 9*n^2)*Gamma[4/3]^8)/Pi^4])) + 36*n*(1 + n)*Sum[(1/(2 + k))* ((1/((-(1/3) + n)^k*k) + ((-1 + n)*n^(-1 - k))/ (1 + k) + (-1 + n)/((2 + n)^k*(k*(1 + k))) + ((-1 + 2^k - k)/(2^k*n^k*k) + (1/3 + n)^(-k))/ (1 + k) + (1/(k*(1 + k)*(1 + n)))* ((k*((1/3 + n)*(1 + n))^k*(-1 + n^2) + (2 + n)^k*((1 + n)^(1 + k) + (1/3 + n)^k* (2 + 3*k + n - (1 + k)*n^2)))/ ((1/3 + n)*(1 + n)*(2 + n))^k))*B[2 + k]), {k, 2, Infinity}]) You can even take two terms with n=1: In[674]:= Table[ InputForm[ E^ReleaseHold[%668 /. {n -> 1., \[Infinity] -> k, B -> BernoulliB, z1 -> Zeta'[-1]}]], {k, 1, 23, 2}] Out[674]= {InputForm[1.0103197650836289`], InputForm[ 0.9971632720879865], InputForm[1.0026975018949733`], InputForm[ 0.9945756764366318], InputForm[1.0192129702965944`], InputForm[ 0.9022068215761623], InputForm[2.2230028233909853`], InputForm[ 0.00021460545039988252`], InputForm[ 6.109203829072703*^50], InputForm[ 2.391297463695393665650687064619`12.495500717694712*^-893], \ InputForm[ 1.2327361911718592314255798015869541197472854729273`11.\ 191037729790512*^19431], InputForm[ 1.81378280396368952850445868471`9.881928587042173*^-513388]} and nine with n=3: In[675]:= Table[ InputForm[ E^ReleaseHold[%668 /. {n -> 3., \[Infinity] -> k, B -> BernoulliB, z1 -> Zeta'[-1]}]], {k, 1, 23, 2}] Out[675]= {InputForm[7.0081268915275], InputForm[ 6.999782449734494], InputForm[7.000017783415529], InputForm[ 6.999997135705913], InputForm[7.000000757779692], InputForm[ 6.999999702042258], InputForm[7.000000163276266], InputForm[ 6.999999880868429], InputForm[7.000000111814524], InputForm[ 6.999999868606976], InputForm[7.000000189122515], InputForm[ 6.999999672531021]} And as usual, as many as you like by boosting n via A[n+1]/A[n] = ((n! * (3 * n + 1)!)/((2 * n)! * (2 * n + 1)!)) (which Mathematica can't even *test*, DiscreteRatio having been sandbagged with a mountain of fractional BarnesGs. --rwg Way to go, Adam! Can we start a new found plane thread when they find it?

1 0

[math-fun] Lewis Carroll's determinant method and some (new?) uses
by Warren D Smith 17 Mar '14

17 Mar '14

Lewis Carroll's determinant method ====Warren D. Smith===March 2014==== http://www.maa.org/sites/default/files/pdf/Mathhorizons/pdfs/nov_2006_pp.12… http://mathtourist.blogspot.com/2007/03/lewis-carroll-and-his-telescoping.h… Lewis Carroll (Rev. Charles L. Dodgson) in 1866 gave the following method to evaluate det(M) where M is an nXn matrix. At each step, we have a kXk matrix which is "condensed" to a (k-1)X(k-1) matrix. Finally, a 1X1 matrix, i.e. single number, is got, which is the desired determinant. ALGORITHM: We begin with M0 = M. initial step (k=n): M1 = the 2x2 determinants of adjacent entries in M0. Note M1 is (n-1)X(n-1). for(j=2 .. n-1){ M[j] = the 2x2 determinants of adjacent entries in M[j-1]; Note M[j] is (n-j)X(n-j). This is not yet the final form of M[j]. for(a=1..n-j){ for(b=1..n-j){ Divide entry a,b of M[j] by entry a+1,b+1 of M[j-2]. } } That yields the final form of M[j], the j-condensed version of M. } The sole entry of M[n-1] is now the desired determinant. END OF ALGORITHM. This process requires O(n^3) operations (each +,-,/,*) and fails if at some point it divides by zero. [However, by performing some random row operations before beginning, we usually can eliminate internal zeros so the process will not fail. Alternatively, you could replace all 0s by epsilons, continue on symbolically, and at the end take the limit epsilon-->0. Both approaches are a pain.] Of course we only need to store a constant number of the M[j] matrices, not all of them, hence the total storage needs are O(n^2) entries, not order n^3. WHY SHOULD ANYBODY CARE? 1. I point out, which remark I have not seen before, that Carroll's condensation process preserves certain special matrix forms. If M is Toeplitz, Hankel, diagonal, or banded with bandwidth=w, then all the condensed matrices also are. If the original matrix was all-integer, then all the condensed matrices also are. As a result, it seems to me that this yields an O(n^2) step algorithm for computing the determinants of Toeplitz and Hankel matrices, and an O(n^2 * w) step algorithm for matrices with bandwidth=w, and an O(n) algorithm for diagonal matrices. This Toeplitz result seems quite nice, although probably asymptotically faster methods are possible (?). 2. The RESULTANT of two polynomials is the determinant of the Sylvester matrix, http://en.wikipedia.org/wiki/Sylvester_matrix, which is made by gluing together two matrices which are rectangular chunks of Toeplitz matrices. The Carroll j-condensed forms of Sylvester matrices, also have Sylvester form, except for j extra rows inserted between the two Toeplitz rectangles... does this lead to a quadratic-time resultant algorithm? Unfortunately I am not seeing any obvious reason why this process can be made to run in only quadratic time for resultants. 3. David Bressoud and James Propp have remarked that Carroll's method is highly parallelizable. It also exhibits excellent memory-locality. On n^2 processors, each condensation will run in O(1) time, causing the whole determinant process to take time O(n). 4. There are also other condensation processes similar to (but different from) Carroll's, including Chio's process (M.F.Chio 1853, http://mathworld.wolfram.com/ChioPivotalCondensation.html ) , and methods which involve 3x3 rather than 2x2 determinants of adjacent entries, with shrinkage by 2 not 1 at each step. Chio's process seems better than Carroll's in the respect that it is easier to avoid dividing by zero. 5. If you solve an nXn linear system using Cramer's rule, then each entry of the solution vector is got in O(n) time using n^2 processors i.e. O(n^3) total work. The full solution vector then would naively require n^4 work. However it is possible to share work and thus reduce the total work back to O(n^3). This is described for a 3x3 version of Chio's condensation process in: Ken Habgood & Itamar Arel: A condensation-based application of Cramerʼs rule for solving large-scale linear systems, J. Discrete Algorithms 10 (January 2012) 98-109. http://web.eecs.utk.edu/~itamar/Papers/JDA2011.pdf Their work-sharing scheme is a bit of a pain, although they succeeded in programming and testing it. Its underlying idea is to regard the matrix as a binary tree (splits by vertical cuts) and note that any two Cramer determinants share a lot of their computation-trees, so by memoizing subtree results you avoid redoing those subtrees. There is a picture in their paper which makes it clearer how they do that. It seems to me a similar scheme would also work for Carroll's 2x2 process described here, although I have not carefully checked. In any case, it seems to me that the primary benefit of Habgood & Arel is one they did not mention (!!) -- that their approach is highly parallelizable. It will solve an nXn linear system in O(n) time with n^2 parallel processors. Habgood & Arel encountered some numerical problems. There is an analogue of "pivoting" which could be used to improve the numerics of the Chio-based determinant computation, but if you use it then it screws up the Habgood-Arel work-sharing scheme. But a different linear-system-solving method which also works in O(n) time with n^2 parallel processors is conjugate gradient method. And this method is considerably simpler to program and uses only O(n) storage beyond the original matrix. Further, CG can also be run less than all the way to completion and still will often compute good approximate answers. 6. That suggests seeking a task that condensation with work-sharing can do, which CG cannot do. How about computing the INVERSE of an nXn matrix? Using its explicit formula in terms of the n^2 minors, each (n-1)x(n-1), of the matrix (as well as the determinant of the original matrix). The naive implementation of this would compute the inverse in order n^5 total work. However, if we can share work enough, then this would be reduced to O(n^3) work in O(n) time with n^2 processors. (A new record?) I believe this can actually be done, using a treelike scheme resembling Habgood & Arel's, but based on a "quadtree" (both horizontal & vertical splitting) rather than a binary horiz-splits-only tree. 7. Certain matrices whose a,b entries are given by formulas in terms of a and b, yield condensed forms also given by other formulas,... which in some cases enables you to compute the determinant in closed form. 8. Also might be useful for thinking about determinants of "random" matrices. SUMMARY: New(?) results are an O(n) time n-processor parallel det-algorithm for Toeplitz and Hankel matrices (but if there is a similar way to do resultants in this time bound, I am not seeing it), and an O(n) time parallel algorithm on n^2 processors for matrix inversion.

3 5

Re: [math-fun] Missing plane discussion closed.
by Adam P. Goucher 17 Mar '14

17 Mar '14

Affine 3-space is like projective 3-space, but with a missing plane. Sincerely, Adam P. Goucher > ----- Original Message ----- > From: rcs(a)xmission.com > Sent: 03/17/14 04:38 AM > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] Missing plane discussion closed. > > I'm declaring the thread about the missing plane closed. > > Rich > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] How to find Malaysia370 missing plane.
by Warren D Smith 17 Mar '14

17 Mar '14

Bernie Cosell: They mentioned that arc and pointed out that it was unlikely to be on that arc because it is almost completely covered by military radars. The idea that the plane could fly over Sri Lanka, India and Pakistan [not to mention the other nearby countries] without being detected is considered pretty unlikely. WDS: what bullshit. First of all, India stated their military radar is often turned off. Second, Pakistan let tons of USA drones fly over and bomb the place and was evidently unable or unwilling to stop them, which if they had working radar and fighter planes, would have been easy. I deduce the claim Pakistani military radar would have detected and/or stopped it, is garbage. Third, my pictured/deduced route did not go anywhere near Sri Lanka and mainly went over Bangledesh and Nepal, areas which I presume are among the least military-radared in all Asia. Fourth, we know for a fact that Malaysian military radar's detection of it was simply ignored. Don't believe the self-serving propaganda. Fifth, the alternative if you did believe that propaganda, would be to assume the plane simply flew round in circles over the ocean for about 6 hours, thus staying off all radars, then finally intersected the sat-ping circular arcs, then soon after crashed, with nobody noticing! Why would anybody who went to this degree of planning and with this amount of ability/knowledge, do anything that idiotic? But hey, feel free to choose that alternative. What you, and certainly the media, do not seem to comprehend at all when assessing "unlikely" is the concept of CONDITIONAL probability. Conditioned on the facts, my hypothesis is not "unlikely." It is "the most probable explanation." -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Math is where you find it
by Keith F. Lynch 17 Mar '14

17 Mar '14

The recent death of Joe McGinniss, best known as the author of _Fatal Vision_, has led me to re-read books on both sides of that controversy. The question is whether Jeffrey MacDonald murdered his wife and children, as a jury concluded, or whether someone else did. One of the most crucial pieces of evidence is a man's pajama top with 48 icepick holes. The prosecution managed to get them to line up in an allegedly incriminating way. The defense said you can get them to line up in any way you like, but didn't demonstrate this. There's a chart of this pajama top in one of the books. I've been thinking about scanning it in and writing a computer program to test this and see who is right. As some of you know, for personal reasons I've long been very interested in the issue of wrongful convictions. This presents a rare opportunity for me to do something other than compare narratives. What is known about this kind of puzzle? There's a flat, or I suppose in this case cylindrical or conical, piece of cloth with holes in it, and the task is to figure out how it was folded when those holes were made. Very likely there are multiple solutions, in which case the ones with the fewest number of folds are presumably to be preferred.

2 1