December 2011 - mathfun@mailman.xmission.com

[math-fun] Conway's angel (hopper) versus devil (square eater)
by Warren Smith 06 Dec '11

06 Dec '11

John Conway proposed a game on the infinite square grid. Rules: 0. All squares initially white. 1. angel can in 1 move fly a taxicab distance A from wherever she is, to a white square. 2. devil can in 1 move color any B squares black. 3. If the angel has no white squares within range to fly to, then angel loses. If it can escape to infinity, angel wins. Who wins? The problem with B=1 remained open for about 30 years, then 4 people [Gacs, Kloster, Mathe, Bowditch] independently solved it, showing that with any A>=2 and B=1, the angel wins (but with A=B=1 the devil wins, shown by Berlekamp). But for some reason the problem with B>1 was not addressed. http://home.broadpark.no/~oddvark/angel/index.html http://en.wikipedia.org/wiki/Angel_problem The real truth is, if B is large enough compared to A the devil wins, if A is large enough compared to B the angel wins. The real question is: which (A,B) are which? If B>2*A*(A+1) the devil wins in 1 move. If A>4*B the angel wins, as far as I can tell from generalizing Mathe's proof. Gacs' proof also shows directly that there exists a positive constant so if A>const*B then angel wins. There is a large gap between these.

1 0

[math-fun] Counting problem
by Dan Asimov 06 Dec '11

06 Dec '11

What are all the ways that 30-, 60-, and 90-degree angles can be arranged about the origin in the plane? Let two ways be equivalent if one can be carried into the other by either a rotation or a flip of the plane -- i.e., by an element of the group O(2). This appears to be a messy counting job but certainly doable by hand because of its small scale. As a first step, I found there are 19 partitions of 12 using only 1's, 2's, and 3's (appended). Can anyone suggest a smart way to go about this, or is there no good way to shorten the task? --Dan ----------------------- 3+3+3+3 2+2+2+3+3 2+2+2+2+2+2 1+2+3+3+3 1+2+2+2+2+3 1+1+2+2+3+3 1+1+2+2+2+2+2 1+1+1+3+3+3 1+1+1+2+2+2+3 1+1+1+1+2+3+3 1+1+1+1+2+2+2+2 1+1+1+1+1+2+2+3 1+1+1+1+1+1+3+3 1+1+1+1+1+1+2+2+2 1+1+1+1+1+1+1+2+3 1+1+1+1+1+1+1+1+2+2 1+1+1+1+1+1+1+1+1+3 1+1+1+1+1+1+1+1+1+1+2 1+1+1+1+1+1+1+1+1+1+1+1 ----------------------- ________________________________________________________________________________________ It goes without saying that .

3 3

[math-fun] Is immortality possible? Gacs says yes.
by Warren Smith 06 Dec '11

06 Dec '11

Let me reword my question about the 2D "life" cellular automaton more carefully. QUESTION (IS EXPTIME "IMMORTALITY" MATHEMATICALLY POSSIBLE?): Does there exist a lifeform, which enjoys "homeostasis"? That is, suppose we use the usual life time-evolution rule, but with "epsilon random noise" added, i.e. each cell independently disobeys the rule with probability epsilon at any given timestep. Does there exist an epsilon>0 and P>0 and C with 0<C<1 such that for every sufficiently large number N, there exists a life pattern of initial diameter N that, with probability>1/2, will evolve for exponential(N^P) timesteps (staying nonempty) in the noisy world, in such a way that the Hamming distance between its no-noise and noisy evolution, is always upperbounded by C*diam^2 [where diam>0 is the time-varying diameter of the no-noise version]? -----------------------------CLAIMED SOLUTION (OR NEARLY) Peter Gacs, in a very long and difficult paper (really, a "book"...), claimed to have shown immortality *is* possible in certain universal 1D cellular automata and he also can achieve this in higher dimensions more easily than 1D (not for the "life" CA rule, though): http://www.cs.bu.edu/~gacs/papers/long-ca-ms.pdf "Reliable Cellular Automata with Self-Organization", J. Statistical Physics 103, 1/2 (2001) 45-267. "Reliable computation with cellular automata", Journal of Computer System Science 32,1 (1986) 15-78 http://www.cs.bu.edu/faculty/gacs/papers/GacsReliableCA86.pdf Note Gacs et al in many of their papers require the entire infinite space to be preset to whatever values he needs. That is, Gacs is showing that an immortal lifeform of infinite size can exist in a suitable CA. He is not showing that a compact finite-size lifeform with exptime survival, exists. (I think.) The difference is that the world external to the lifeform has to be preset to some fixed value, or periodic pattern ("homogeneity"). However in his huge paper, it appears he does solve the latter problem. This is a fantastic achievement but very few people understand it. Including me among those who do not understand it.

1 0

Re: [math-fun] spherical pendulums?
by Henry Baker 06 Dec '11

06 Dec '11

Surely there must be conditions more than simply "smooth". For example, if the cross-section is smooth, but not convex, then the particle will leave the surface when the curvature becomes negative. At 11:08 AM 12/6/2011, Eugene Salamin wrote: >The curved cylinder imposes a normal force on the point mass, and this does not affect the motion parallel to the surface. So indeed the particle moves in a parabola wrapped around the cylinder, no matter what the cross section, at least for smooth surfaces. > > -- Gene > >>________________________________ >> From: Henry Baker <hbaker1(a)pipeline.com> >>To: Adam P Goucher <apgoucher(a)gmx.com> >>Cc: math-fun(a)mailman.xmission.com >>Sent: Tuesday, December 6, 2011 8:01 AM >>Subject: Re: [math-fun] spherical pendulums? >> >>Hmmmm.... >> >>Does it matter if we wrap the transparent paper around a cylinder with circular >>cross section, or could the cross section be another shape -- e.g., an ellipse >>or something else? >> >>Obviously, if the shape included some sort of cusp, it wouldn't stay on the >>shape. >> >>Aren't we assuming that any accelerations are perpendicular to the shape of >>the cross section? But if the moving object is accelerating/decelerating >>along other dimensions, wouldn't that change things? >> >>At 10:43 AM 12/5/2011, Adam P. Goucher wrote: >>>>Here's a related problem: >>>> >>>>A point particle of mass M (i.e., zero moment of inertia) is sliding frictionlessly around inside a vertical cylinder; gravity is downwards of strength G. What are the paths? >>> >>>Imagine drawing a parabolic arc on a sheet of transparent paper, and wrapping >>>it around the inside of the cylinder. This is parametrised by: >>> >>>x = r cos(wt) >>>y = r sin(wt) >>>z = -Â½gtÂ² >>> >>>(w, r and g are constants, namely the angular speed, radius and gravitational >>>field strength, respectively.) >>> >>>Sincerely, >>> >>> Adam P. Goucher

2 1

[math-fun] fast spinning stars
by Warren Smith 06 Dec '11

06 Dec '11

H.Baker: http://www.edhat.com/site/tidbit.cfm?nid=75955 star spinning at 600 km/sec --I point out millisecond pulsars (neutron stars spun up via infalling gas) are known spinning as fast as 716 rev/second, including ones that have planets. Assuming equatorial diameter of 24km this is 54000 km/sec = 0.18c.

1 0

[math-fun] "Genesis seed" pattern for Life, & other questions about life such as "immortality"
by Warren Smith 06 Dec '11

06 Dec '11

Dan Asimov: Is there an "Adam & Eve pattern" whose future Life-evolution will (eventually, somewhere) yield every pattern that fits in any fixed-size rectangle and which has an infinite sequence of ancestors? Robert Munafo: Claimed proof answer is "no." WDS: Sorry, I do not follow Munafo's "no" proof. This sentence in his proof is false: "If the Adam/Eve starting pattern's evolution includes any of the block predecessors, its subsequent evolution must lead to the block." Asimov's is actually an interesting question and there are a number of related interesting questions. I can argue that the answer to a weaker question is "yes." Conway et al showed that life is Turing-universal and the computer you can build inside Life can also be a "universal assembler" capable of synthesizing anything that gliders can synthesize, anyhow. (Is that right? I do not have Conway's proof in front of me, but definitely something like this, is true.) So, make a Turing-universal computer and program it to do stuff. For one thing, we can program it to count 1,2,3,4,... which in some sense enumerate every integer, i.e. every possible pattern. Whether it has ancestors or not. However, this enumeration is only in an abstract sense as "bits in memory", not explicitly as life alive-death patterns. We could presumably program our machine to spit out every possible glider configuration to synthesize eventually every possible glider-synthesizable pattern... except the problem is those patterns might then rise up and destroy their creator. To save ourselves from that fate, we could have our computer mentally simulate an Life inside its memory, investigating patterns to see which ones eventually died or were eventually killable with gliders. It could then systematically safely synthesize every pattern 1. synthesizable with gliders 2. whose future was killable with gliders. So this is a pretty impressive set of descendant patterns all coming from one fixed "Genesis seed pattern." And note: any glider-synthesizable pattern automatically has an infinite set of ancestors. It is Turing-undecidable whether a given finite CA pattern, has an infinite sequence of ancestors... indeed it is undecidable whether it has a father, both proven here: Jarkko Kari: Reversibility of 2D cellular automata is undecidable, Physica D 45 (1990) 379-385. More simply we know it is undecidable whether a given pattern has an infinite sequence of nonempty descendants (proof: Turing's halting problem). Q1. Do there exist "cancer" patterns that are unkillable with gliders? [A pattern is "killable with gliders" if some set of incoming gliders will cause it to evolve to the empty state.] Q2. Do there exist patterns with infinite ancestors that are not glider-synthesizable? Q3. Does there exist a lifeform, which enjoys "homeostasis"? That is, suppose we use the usual life time-evolution rule, but with "epsilon random noise" added, i.e. each cell disobeys the rule with probability epsilon at any given timestep (all probabilities independent). Does there exist an epsilon>0 and P>0 such that there exists for all sufficiently large N, a pattern of initial diameter N that will evolve for exponential(N^P) timesteps (staying nonempty) in the noisy world, almost the same way as it was supposed to evolve in the non-noisy world? Meaning the Hamming distance between the noiseless and noisy evolution, stays bounded by a constant C times the area of a bounding ball throughout this timespan, with probability-->1 when epsilon-->0+, where C depends on epsilon and C-->0 when epsilon-->0+. I think question Q3 is especially important; if the answer is "no" that "proves that immortality is impossible"; if yes it proves it pretty much proves it is possible. (Exponential lifespan is not infinite, but it clearly is the best that can be hoped for and is pretty damn near infinite.)

1 0

[math-fun] UCSB scholar has found the fastest-rotating massive star ever recorded
by Henry Baker 06 Dec '11

06 Dec '11

FYI -- I'm more impressed that one star of a binary system can be expelled at an extremely high speed. It appears that there are quite a large number of these fast-moving ronin objects -- planets & stars -- that have been ejected from their systems, and are moving through space at all kinds of weird angles. The ronin planets would be too dark to see, but ronin stars can be seen if looked for. http://www.edhat.com/site/tidbit.cfm?nid=75955 An international team of scientists has found the fastest-rotating massive star ever recorded. The star spins around its axis at the speed of 600 kilometers per second at the equator, a rotational velocity so high that the star is nearly tearing apart due to centrifugal forces. This confirms a prediction put forward by astrophysicist Matteo Cantiello, a postdoctoral fellow with UC Santa Barbara's Kavli Institute for Theoretical Physics, who contributed to the discovery published this week in the Astrophysical Journal Letters. The observations were made at the European Southern Observatory's Very Large Telescope, at the Paranal Observatory in Chile, as part of a survey of the heaviest and brightest stars in a region called the Tarantula Nebula. The Tarantula Nebula is a region of star formation located in a neighboring galaxy called the Large Magellanic Cloud, about 160,000 light years from Earth. The reported star, VFTS 102, is extremely hot and luminous, shining about 100,000 times more brightly than the sun. According to the research team, this star had a violent past and was ejected from a double star system by its exploding companion star. Cantiello and collaborators explained that stars could reach such rapid rotation via a "cosmic dance" with another star so close that gravity strips gas from its surface. "This gas falls onto the companion star, increasing the mass and spinning it up," said Cantiello. "Similar to a tennis ball spinning fast after being hit by a glancing blow, a star rotates quickly after being hit off-center by the in-falling gas." Cantiello previously predicted the possibility of observing this type of star. He reported this theoretical finding with Sung-Chul Yoon, Norbert Langer, and Mario Livio in a paper published in 2007 in Astronomy & Astrophysics Letters. This theoretical investigation of stars in binary systems predicted extreme rotational velocities after mass accretion. The observed rotational velocity for the star agrees with this prediction. The star is unusual not only because it rotates so fast, but also because it is moving away from its neighboring stars at a velocity of about 70,000 miles per hour, or 30 kilometers per second. "Having been part of a binary system could explain this space oddity," said Cantiello. "It has been known for over 40 years that a star in a massive binary system can be shot away from its surroundings when the companion ends its life in a spectacular explosion called a supernova. In our theoretical calculations we noticed that the 'spun-up' star would also be moving from its surroundings at a high rate. It is very exciting to find a star that matches both of these predictions." The star is located close to a pulsar and a supernova remnant, which may be left over from the companion star that once spun-up the observed star. If confirmed, this would provide additional support for the theoretical explanation put forward by Cantiello and collaborators in 2007. Cantiello said that this star may produce dramatic fireworks as it dies. Such a rapidly rotating, massive star is believed to be the progenitor of some of the brightest explosions in the universe: gamma-ray bursts. These occur when the star's fast rotation produces powerful jets of light and matter.

1 0

[math-fun] Quick census of primitive Heron triangles
by Warren Smith 06 Dec '11

06 Dec '11

diameter #primtris with diam<=that ==================================== 2 0 4 0 8 3 16 7 ratio=2.333 32 26 ratio=3.714 64 78 ratio=3.000 128 266 ratio=3.410 256 752 ratio=2.827 512 2291 ratio=3.047 *** 1024 6332 ratio=2.764 2048 17415 ratio=2.750 4096 47313 ratio=2.717 8192 126061 ratio=2.664 16384 331121 ratio=2.627 >From *** onward the ratio is decreasing... ultimately to 2+? That (and only that) limit would confirm my hypothesis that the asymptotic behavior is count=O(diam^(1+epsilon)). The "permanent ratio decrease" alone (without the limit) would prove that count=O(diam^1.4). Within the range of the table, though, the growth is more like count=0.16*diam^1.5. [And the count for nonprimitive Herons should be at least a constant factor but at most a log factor greater than the count of primitive Herons, analogously to the way the count of integers is a log factor greater than the count of primes...]

1 0

Re: [math-fun] Request for example elementary non-constructive proofs with "witnesses"
by Bill Gosper 06 Dec '11

06 Dec '11

Allan, can you sketch the 3x3 proof? My 3x3 memory, also vague, was that someone at the AILab (Beeler? Speciner?) Greatly reduced the GOE bound by exhaustively searching for the 3x3 with fewest predecessors (= the hollow box, despite its frequency of appearance). Banks then used this to focus his GOE search.) --rwg ACW>*Winning Ways* came out in 1982, more than a decade after the original flurry of Life columns in Martin Gardner's column. I have a memory, that may of course be a confabulation, of seeing a sketch of the 3-by-3 block proof in one of those columns. I certainly knew the 3-by-3 proof by 1973 or 1974 at the latest. On Mon, Dec 5, 2011 at 12:55 PM, Richard Guy <rkg(a)cpsc.ucalgary.ca <http://gosper.org/webmail/src/compose.php?send_to=rkg%40cpsc.ucalgary.ca>> wrote: > Allan & others,> Winning Ways was written some time ago, especially> some parts of it. I would be interested to learn the reference> to any ``earlier proof''. R.>>> On Mon, 5 Dec 2011, Allan Wechsler wrote:>> Why did Winning Ways use the very profligate Garden of Eden proof,>> featuring 5-by-5 subsquares, instead of the earlier proof (I think it was>> featured in a Mathematical Games column), which has much smaller numbers>> and uses 3-by-3 subsquares?>>>> The older proof demonstrates very handily that a Garden of Eden exists in>> a>> 42-by-42 square. (The key inequality is that 140^196 < 2^1404.) Why the>> elaborate construction with 5-by-5 subsquares, which doesn't achieve>> crossover until the square measures in the billions of cells on a side?>>>> When I was in high school sometime around 1972, I went to see John Conway>> talk either at Wayne State University or the University of Michigan. I>> have a very clear memory of him sketching the proof with the 3-by-3>> subsquares.>>>> On Mon, Dec 5, 2011 at 3:29 AM, Bill Gosper <billgosper(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> wrote:>>>> rcs>>>>>>> I think the original counting argument was Moore's, and it easily>>> applied directly to Life. However, there's an easy example of a GOE>>> from the counting argument: The argument shows that there's some>>> GOE pattern, of size < a computable number N. To make the argument>>> constructive, just make up a supersize pattern, with all possible>>> patterns of size N.>>>>>> Wrt showing Louiville numbers are transcendental:>>> Use the example L = sum 10 ^ (- N!).>>> In this special case, it's not too hard to check that>>> L defeats any prospective polynomial.>>>>>> Rich>>>>>> --->>> Quoting Allan Wechsler <acwacw(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=acwacw%40gmail.com>>>> <http://gosper.org/webmail/**src/compose.php?send_to=**>>> acwacw%40gmail.com<http://gosper.org/webmail/src/compose.php?send_to=acwacw%40gmail.com>>>> >>:>>>>>>> This is the one I've been trying to remember. Thank you, Alon.>> This>>>>>>> also reminds me of the proof that the Game of Life has a finite Garden>>>> of>>> Eden pattern. (Since the original proof, many explicit predecessorless>>>> patterns have been found.) It depends on counting possible predecessors>>>> and shows that for a certain class of patterns, the number of candidate>>>> predecessors is smaller than the number of patterns, so one of that>>> class>>>> must lack a predecessor. The class is astronomically large, though, and>>>> the counting argument gives no hints about how to find an example.>>> <...>>>>>>><http://www.tweedledum.com/rwg/goe.htm>>>> --rwg

3 2

[math-fun] Life's Adam & Eve
by Dan Asimov 06 Dec '11

06 Dec '11

When I first read the subject "Life's Garden of Eden" a few weeks ago, I didn't know its definition as a pattern without predecessor. Instead I wondered if it meant a pattern that eventually gave rise to all other patterns. So: Is there such an "Adam & Eve" pattern? Specifically, a finite pattern P = P(0) such that for any K and L in Z+ and pattern Q of bits in a KxL rectangle, there is some Life descendant P(t) of P that contains some KxL rectangle with exactly the pattern Q in it ??? Or is there a proof that this is impossible? --Dan ________________________________________________________________________________________ It goes without saying that .

2 1