Yeah, I know - 119 read more lines...

Yeah, I know - 119 read more lines...
It's cool, trust me. 

Originally shared by Richard Green

The look-and-say sequence and Conway's Cosmological Theorem

This graphic illustrates the look-and-say sequence, which is a good example of an idea from recreational mathematics that turns out to have hidden depths. To find the next number in the sequence after “111221”, we read out an inventory of the digits in the number (three 1s; two 2s; one 1) and then we represent the inventory itself as the digits of a new number (312211).

The well-known mathematician John H. Conway noticed that, with two exceptions, the long-term behaviour of this iterative process is very interesting, and he proved some nontrivial theorems about it. The two “boring” cases, as Conway calls them, are the number 22, which consists of two 2s and immediately goes into an infinite loop, and the empty string of digits, which never gets anywhere. Any other starting string of digits is defined to be interesting.

Conway's key observation is that after sufficiently many iterations of this procedure, any interesting string of digits will separate into consecutive substrings that never again interact with neighbouring substrings. Using the metaphor of radioactivity, the minimal substrings of this form are known as atoms, and the iterative procedure is known as decay. Because the sequence involves reading previous terms aloud, Conway named this iterative procedure audioactive decay in a 1986 paper. (He enjoys playing with words when introducing new concepts.)

There are 92 basic types of atoms, all of which only involve the digits 1, 2 and 3. These 92 types are known as common elements, and they are nicknamed after the first 92 elements of the periodic table (from hydrogen to uranium). There are also so-called transuranic elements: the Neptunium family (1311222113321132211221121332211n) and the Plutonium family (31221132221222112112322211n), where n can be any digit that is 4 or larger. 

Conway's Cosmological Theorem states that every string eventually decays into a compound of common and transuranic elements. (This terminology should not be taken too seriously, and in particular, Conway is not suggesting that the universe is a giant plutonium atom, because that would be ridiculous.) Conway also proves that, starting from an interesting string, the terms eventually grow by about 30 percent on each iteration. More precisely, the length of the string increases asymptotically at each step by a factor of about 1.3035772690, a number known as Conway's constant. This number is an eigenvalue of the 92 by 92 transition matrix associated to the iterative process, and is the unique positive real root of a certain degree 71 polynomial with integer coefficients.

Although it may appear initially that the nature of this problem may depend significantly on the number base chosen, this turns out not to be the case, so long as the base is at least 4. This is because it is provably impossible for any digits other than 1, 2 or 3 to appear in a sequence, unless the initial number contains such a digit or a run of more than three of the same digit. Another remarkable property of audioactive decay, proved by Conway, is that every common element will eventually show up in the decay of any interesting string.

The full statement of the Cosmological Theorem makes a stronger assertion: it states that there exists an integer N such that every string decays in at most N steps to a compound of common and transuranic elements. According to Conway, there used to exist a proof of this fact by him and Richard Parker, as well as another proof by Mike Guy showing that one could take N=24 and that this was the best possible value. Somehow, both these proofs were lost, but fortunately, Shalosh B. Ekhad and Doron Zeilberger showed in their 1997 paper Proof of Conway's lost Cosmological Theorem that N exists and is at most 29. The mathematician Shalosh B. Ekhad (Hebrew for “3B1”) is notable for not being human: it is the name of Zeilberger's computer. Despite this, it has written some single-author papers.

Relevant links

Here's a recent Numberphile video in which Conway talks about this sequence: http://goo.gl/S24CmM. I am grateful to Joachim Kessel and Marc Schnau for telling me about the video. I see that the Numberphile channel has just passed the 1 million subscribers mark, so congratulations are in order!

Mathworld on the Cosmological Theorem: http://mathworld.wolfram.com/CosmologicalTheorem.html

Wikipedia on the look-and-say sequence: http://en.wikipedia.org/wiki/Look-and-say_sequence

The look-and-say sequence on the On-Line Encyclopedia of Integer Sequences: http://oeis.org/A005150

Kevin Watkins has some interesting slides and a paper about the Cosmological Theorem on his web page: http://www.cs.cmu.edu/~kw

Ekhad and Zeilberger's paper: http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/horton.html

#mathematics #scienceeveryday