December 2013 - mathfun@mailman.xmission.com

Re: [math-fun] "life" generalized CAs classified ala Wolfram?
by Warren D Smith 17 Dec '13

17 Dec '13

>The most interesting aspect of this project, it seems to me, is the isInteresting() predicate. --it occurs to me that you could get a hell of a long way toward making a good IsInteresting predicate by simply computing discrete fourier transforms. I.e. if a cell is periodic in time, a temporal FFT would detect that. Wolfram's "4 (vague) types" of 1D CAs were: 1.Evolution leads to a homogeneous state. 2.Evolution leads to a set of separated simple stable or periodic structures. 3.Evolution leads to a chaotic pattern. 4.Evolution leads to complex localized structures, sometimes long-lived. Note 1 and 2 seem trivial to detect using FFT. Distinguishing types 3 & 4 may be a little bit tougher, but I bet it would be easy to make an automated classifier comparable in ability to Wolfram himself. >Alternatively we might start with the simpler 4 cell neighborhood, thus only 2^10 cases. --the checkerboard neighborhood graph is bipartite, so this probably not a good idea. Using the equilateral triangle lattice, 6 neighbors, might be better, though.

2 1

Re: [math-fun] "life" generalized CAs classified ala Wolfram?
by Warren D Smith 16 Dec '13

16 Dec '13

>IIRC these are called "totalistic" rules. >The most interesting aspect of this project, it seems to me, is the isInteresting() predicate. However (as the OEIS shows) defining "interesting" can be a challenge. >One possible choice in this context might be "can be used to build a Turing machine". But--considering the heroics entailed constructing a Turing-equivalent pattern just for the single Life rule--this seems kinda daunting. >But if we had even a quick partial implementation at least we might winnow out the vast majority of the quarter million rules and just concentrate on the most promising candidates. --indeed. S.Wolfram wrote a paper where he carried out the analogous project for 1-dimensional cellular automata with cardinality-8 neighborhoods, 256 machines considered in all. His "IsInteresting()" predicate consisted of him looking at graphical output and pushing one of several buttons. In fact, he undoubtably would have liked to use "Turing machines exist" as one of his predicates, but was unable and instead merely made conjectures... and indeed, eventually Matthew Cook managed to prove Wolfram's "rule 110" conjecture http://en.wikipedia.org/wiki/Rule_110 in an excellent piece of work which Wolfram responded to with a lawsuit (!). Anyhow, you'd have to make an "Automated Wolfram eyeball" as your IsInteresting() heuristic predicate.

1 0

[math-fun] Fwd: [CASE:520044] Documented bug(s) in Rationalize
by Bill Gosper 16 Dec '13

16 Dec '13

Another chance for funsters to take sides. On 12/16/2013, 03:30pm, Bill Gosper wrote: Doc: "Rationalize[x,dx] yields the rational number with smallest denominator that lies within dx of x." First of all, is this strictly between, or inclusive of the endpoints? I can't tell because it's broken: Doc: "Successive rational approximations to π: In[1]:= Table[Rationalize[Pi, 10^-n], {n, 1, 10}] Out[1]= {22/7, 22/7, 201/64, 333/106, 355/113, 355/113, 75948/24175, \ 100798/32085, 103993/33102, 312689/99532}" The first ratio should be 16/5 ! |π - 16/5| < 1/10 Simpler case: In[117]:= Rationalize[1/4, 1/11] Out[117]= 1/4 should be 1/3, which should also be the answer to Rationalize[1/4, 1/12] if "within" is not strictly. The following code, which includes the "Strict" option seems to work. It also includes the Mediant function, which Mathematica should offer. ratinint[hi_,lo_]/;hi>lo:=ratinint[lo,hi]; ratinint[lo_,hi_]:=Block[{M={{1,0},{0,1}},k}, While[{{1,0},{0,1}}!=(k=Floor[{{1,-Divide@@(M.{1,-hi})}, {-Divide@@Reverse[M.{1,-lo}],1}}]),M=k.M];Mediant@@(Divide@@#&/@M)] rationalize[x_,dx_,Strict]:=ratinint[x-dx,x+dx]; rationalize[x_?NumericQ,dx_]:=Block[{M=IdentityMatrix[2],d=dx}, NestWhile[(M=(M.{{#,1},{1,0}}&)@Floor[#]; d=-d;1/Mod[#,1])&,x,Abs[x*M[[2,1]]-M[[1,1]]]>Abs[M[[2,1]]*dx]&]; Divide@@(M.{1,-#})&@Floor[Divide@@({1,-d-x}.M)]] Mediant[a__] := Divide @@ (Plus @@ # & /@ {Numerator[{a}], Denominator[{a}]}) (It also harmlessly divides by 0.) My second issue is much deeper, and we may want to split it off as a separate discussion. Doc: "No rational number is by default considered "close enough" to N[Pi]: In[1]:= Rationalize[N[Pi]] Out[1]= 3.14159 Force a rational approximation to be found: In[1]:= Rationalize[N[Pi], 0] Out[1]= 245850922/78256779 " No! Mathematica is perpetrating the pernicious delusion that it has "inexact numbers". In fact, ALL things NumberQ are exact, dyadic rationals (or the Complex of two such). "Inexact" numbers are really exact quantities subject to *inexact operations*. "Force a rational approximation to be found" should actually say "Subject N[π], which is already a rational approximation, to a mysterious reapproximation in which the denominator is minimal wrt some inexplicit accuracy bound." On the MacBook Pro, at least, the actual exact value of N[π] is 884279719003555/2^48, and it is very unhelpful to conceal this fact. The subterfuge gets even more frustrating with quantities like N[π,69]. --Bill Gosper

1 0

[math-fun] "life" generalized CAs classified ala Wolfram?
by Warren D Smith 15 Dec '13

15 Dec '13

On the usual 2D integer grid with 0/1 binary state on each grid point, there are exactly 262144=2^18 possible cellular automaton rules of the form MyNewState = F(MyOldState, NumberOfNeighborsWhichAre1) based on each grid point regarded as having 8 neighbors, any number 0-8 of which can be in state 1. One could, I suppose, try to classify all 262144 trying to find the small fraction among such rules which are "interesting." LIFE and the new rule Lunnon just pointed out (if I understand it aright), are interesting. -- Warren D. Smith http://RangeVoting.org

2 1

[math-fun] Tired of "Life"? Fwd: fractal + chaos + complex CA dynamics
by Fred Lunnon 14 Dec '13

14 Dec '13

The attachments won't make it past the list server, but I will forward them to anyone expressing an interest. WFL ---------- Forwarded message ---------- From: Genaro <genaro.juarez.martinez(a)gmail.com> Date: Sat, 14 Dec 2013 00:16:47 -0600 Subject: fractal + chaos + complex CA dynamics To: Genaro Juarez Martinez <genaro.juarez.martinez(a)gmail.com> Hi dear friends, Just, I want share a simple initial condition but with an interesting evolution from two diagonal lines in the Diffusion rule (or B2/S7, which is identical to Seeds rule or B2/S). I have attached a high resolution picture in this email. Diffusion rule home page. http://uncomp.uwe.ac.uk/genaro/Diffusion_Rule/diffusionLife.html Paper in JCA and arxiv. "Localization dynamics in a binary two-dimensional cellular automaton: the Diffusion Rule" http://www.oldcitypublishing.com/JCA/JCAcontents/JCAv5n4-5contents.html http://cds.cern.ch/record/1198124?ln=en Also, you can run this RLE file (attached) in the new Golly's version. http://golly.sourceforge.net/ Happy weekend! Genaro -- Genaro Juarez Martinez Unconventional Computing Center, UWE, UK http://uncomp.uwe.ac.uk/genaro/ Computer Science Laboratory, IPN, Mexico http://uncomp.uwe.ac.uk/LCCOMP/ Foundation of Computer Science Laboratory, HU, Japan http://www.iec.hiroshima-u.ac.jp/ Centre for Chaos and Complex Networks, CUHK, China http://www.ee.cityu.edu.hk/~cccs/ Laboratoire de Recherche Scientifique, France http://labores.eu/ Institut des Systèmes Complexes en Normandie, France http://iscn.univ-lehavre.fr/

1 0

Re: [math-fun] periodic CFs with Round vs Floor
by Bill Gosper 14 Dec '13

14 Dec '13

On 2013-12-13 15:16, Allan Wechsler wrote: > You've investigated the pure ceiling flavor, have you not? An interesting > feature of these is that they can be sorted by magnitude just using > dictionary ordering. > Are you using non-regular (≠1) numerators? I'm just getting an initial hiccup (lasting at most three terms?), followed by the negatives of the ordinary terms. E.g., In[321]:= Reap[Nest[1/(# - Sow[Ceiling[#]]) &, Coth[1], 9]][[2, 1]] Out[321]= {2, -1, -2, -5, -7, -9, -11, -13, -15} vs In[322]:= Reap[Nest[1/(# - Sow[Floor[#]]) &, Coth[1], 9]][[2, 1]] Out[322]= {1, 3, 5, 7, 9, 11, 13, 15, 17} For quadratic surds, the periods are similarly isomorphic. For √14 In[319]:= ceiltrm /@ dismat[cfrtceil[14, 8]] Out[319]= {4, -3, -1, -6, -1, -2, -1, -6, -1} In[318]:= ContinuedFraction[Sqrt[14]] Out[318]= {3, {1, 2, 1, 6}} Below, I used Floor[#+1/2] vs round-to-even, but it shouldn't matter for irrationals. > > > On Fri, Dec 13, 2013 at 5:46 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > >> Superficial observations. How much does rounding (thereby disabling >> terms =1, Except possibly the first. >> and enabling negative terms) shorten the period? >> In[281]:= rtcfperiod /@ Range[69] - rndcfperiod /@ Range[69] >> >> Out[281]= {{0}, 0, 0, {1}, 0, 0, 2, 0, {2}, 0, 0, 0, 2, 2, 0, {3}, 0, \ >> 0, 2, 0, 2, 2, 2, 0, {4}, 0, 0, 0, -3, 0, 2, 2, 2, 2, 0, {5}, 0, 0, \ >> 0, 0, 0, 0, 4, 4, 2, 4, 2, 0, {6}, 0, 0, 2, -3, 2, 0, 0, 2, -1, 2, 2, \ >> 4, 2, 0, {7}, 0, 0, 2, 0, 2} >> >> It actually lengthened √29 (and √53) by three! and √241 by seven: >> In[282]:= >> rtcfperiod /@ Range[239, 288] - rndcfperiod /@ Range[239, 288] >> >> Out[282]= {2, 0, -7, 4, 2, 12, 4, 4, -2, 2, 6, 2, 4, 2, 8, 2, 0, \ >> {15}, 0, 0, 2, 0, 4, 4, 4, 0, 2, 0, 2, 6, 0, 0, 8, 0, 2, 2, 2, 4, 6, \ >> 2, -2, 0, 4, 4, 8, 6, 2, 2, 2, 0} >> >> The biggest helps seem to outweigh the biggest hurts. >> The curlybraces mark the terminating (square) cases. >> In[275]:= cfrnt[29, 9] >> >> Out[275]= {{{0, 29}, {1, 0}}, {{5, 1}, {4, -5}}, {{7, 4}, {-5, -7}}, >> {{3, -5}, {-4, -3}}, {{5, -4}, {-1, -5}}, {{5, -1}, {-4, -5}}, >> {{7, -4}, {5, -7}}, {{3, 5}, {4, -3}}, {{5, 4}, {1, -5}}, {{5, 1}, {4, >> -5}}} >> >> The actual √29 roundcf, >> In[276]:= rndtrm /@ % >> >> Out[276]= {5, 3, -2, -2, -10, -3, 2, 2, 10, 3} >> >> vs the vanilla one, >> In[278]:= ContinuedFraction[Sqrt[29], Length[%%]] >> >> Out[278]= {5, 2, 1, 1, 2, 10, 2, 1, 1, 2} >> >> In[279]:= FromContinuedFraction /@ {%276, %278} >> >> Out[279]= {315156/58523, 9801/1820} >> >> of course converges faster, term for term: >> In[280]:= % - Sqrt[29.] >> >> Out[280]= {-1.35546*10^-10, 2.80303*10^-8} >> >> Even faster, period for period. >> --rwg --rwg Antibiotics don't actually kill bacteria--they merely hinder their reproductive cycle. For example, the widely prescribed arithromycin permits microbes that normally proliferate exponentially to grow only linearly.

1 0

[math-fun] Magic Pi
by Christian Boyer 14 Dec '13

14 Dec '13

In the latest update of www.multimagie.com, a new smallest known magic square of powers. A 144x144 magic square of 7th powers, constructed by Toshihiro Shirakawa. Magic sum = 3141592653589793238462643383279502884197169399375105. Amazing, all the digits of its magic sum are exactly the 52 first digits of Pi! And a reminder. On smallest possible magic squares, there still remain ten enigmas for winning €6,900 (~$9,500) and ten bottles of champagne. Christian.

4 4

Re: [math-fun] To Jim Re: Terminology riddle
by James Propp 14 Dec '13

14 Dec '13

Dan, I should have been clearer. A pee-print includes only those ideas that are needed for the claim being staked. E.g., one states a result and sketches a proof to convince the reader that the author has a new idea without actually communicating that idea in a useable form. Maybe the original pee-print was that anagram of "ut tensio sic vis" that Hooke (or maybe someone else who found Hooke's Law first) promulgated. (Perhaps someone in this group could remind me/us of the details of this method of staking claims?) Jim Propp On Friday, December 13, 2013, Dan Asimov <dasimov(a)earthlink.net> wrote: > I like Mike's suggestion of peeprint -- and I'd almost be that's what you had in mind, or something very similar. > > Still, although your question is clearly jocular, I'm a bit baffled conceptually: If the purpose is not to convey ideas, then what mathematical territory could be marked? > > Regards, > > Dan > > > On 2013-12-13, at 8:15 AM, James Propp wrote: > >> Q.What do you call a sketchy article whose purpose is not to convey ideas >> but to establish priority and/or to mark some mathematical territory as >> one's own? >> >> (I'll post my answer this afternoon.) >> >> Jim >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >

2 1

[math-fun] Terminology riddle
by James Propp 14 Dec '13

14 Dec '13

Q.What do you call a sketchy article whose purpose is not to convey ideas but to establish priority and/or to mark some mathematical territory as one's own? (I'll post my answer this afternoon.) Jim

3 4

[math-fun] Elser's barrier energy problem for orthogonal matrices
by Warren D Smith 14 Dec '13

14 Dec '13

> From: Veit Elser <ve10(a)cornell.edu> > Here's a question about orthogonal matrices. > Consider orthogonal matrices U of size NxN with the following "energy": > E(U) = -sqrt(N) sum_{i j} |U_i j| > (the negative sum of the absolute values of all the elements, appropriately > scaled). > The lowest energy matrices are Hadamard matrices, as these have > equal-magnitude > elements. We'll consider only N where Hadamard matrices exist. > > Let U_0 and U_1 be any two distinct Hadamard matrices, so two ground states > of our energy function. Let U(t) be a continuous curve between these two > matrices, > i.e. U(0)=U_0 and U(1)=U_1. Here's the question: find a good lower bound on > the "energy barriers" between ground states: the maximum over t, of > E(U(t))-E(U(0)). For the 2x2matrix 1 0 0 1 we have E = -2*sqrt(2) while for the 2x2 matrix +1 -1 -1 +1 / sqrt(2) we have E = -4, confirming V.E's claim for this one case anyhow. Re barrier, any Hadamard matrix of size N>=4 has size divisible by 4 and any 3 of its rows wlog are of the form 11111111111111111111 1111111111---------- 11111-----11111----- where - stands for -1. If we were to do the Givens rotation on the first two (wlog) of those rows we'd reach at the halfway point 00000000001111111111 11111111110000000000 * sqrt(2) which is a barrier height of (2-sqrt2)*N=0.585786*N above the ground energy -N*N. The four kinds of columns can be thought of as the 4 vertices of the top face of the cube [-1,+1]^3. If we rotate the cube about (say) the y axis (010) by 90 degrees, that is just a Givens rotation with aforementioned barrier=(2-sqrt2)*N=0.585786*N. We could instead rotate it about a 3-fold axis like (111) by 120 degrees, with barrier=(2/3)*N=0.666667*N. Or about a 2-fold axis like (110) by 180 degrees, with barrier=1*N. So this tentatively makes it appear that the Givens plan is best possible.

1 0