%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publisher's TeX code    *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you either view the HTML version or    *
%_ * retrieve the article in DVI, PostScript, or PDF format.                *
%_ **************************************************************************
%  Author Package
%% Translation via Omnimark script a2l, July 21, 1997 (all in one day!)

\controldates{13-AUG-1997,13-AUG-1997,13-AUG-1997,18-AUG-1997}
 
\documentclass{era-l}
\issueinfo{3}{11}{January}{1997}
\dateposted{August 21, 1997}
\pagespan{78}{82}
\PII{S 1079-6762(97)00026-7}


%% Declarations:

\theoremstyle{plain}
\newtheorem*{theorem2}{The Cosmological Theorem}
\newtheorem*{theorem1}{Lemma}


%% User definitions:

\newcommand{\halmos}{\hbox {\vrule height0.15cm width0.01cm\vbox 
{\hrule height
 0.01cm width0.2cm \vskip 0.15cm \hrule height 0.01cm 
width0.2cm}\vrule height0.15cm width 0.01cm}}


\begin{document}

\title{Proof of Conway's lost cosmological theorem}
\author{Shalosh B. Ekhad}
\address{Department of Mathematics, Temple University,
Philadelphia, PA 19122}
\email{ekhad@math.temple.edu}
\author{Doron Zeilberger}
\address{Department of Mathematics, Temple University,
Philadelphia, PA 19122}
\email{zeilberg@math.temple.edu}
\thanks{Supported in part by the NSF}
%\issueinfo{3}{1}{July}{1997}
\copyrightinfo{1997}{American Mathematical Society}
\commby{Ronald Graham}
\subjclass{Primary 05Axx}
\date{May 6, 1997}
\begin{abstract}John Horton Conway's Cosmological Theorem about 
sequences like
{\bf 1, 11, 21, 1211, 111221, 312211,\dots}, for which
no extant proof existed, is given a new proof, this time
hopefully for good.
\end{abstract}
\maketitle


 
One of the most intriguing sequences  
\cite{CG},
\cite{F},
\cite{SP},
\cite{V}
is Conway's \cite{C}
{\bf 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,\dots }.
It is defined by the rule $C_{0}:=1$, and
$C_{i}:=JHC(C_{i-1})$, for $i>0$, where $JHC$ is Conway's
audioactive operator:
\begin{equation*}JHC(a_{1}^{m_{1}} a_{2}^{m_{2}} \dots a_{r}^{m_{r}}):=
m_{1} a_{1} m_{2} a_{2}  \dots m_{r} a_{r} .
\end{equation*}
Here $a^{m}$ is shorthand for ``$a$ repeated $m$ times''
(and we agree that the description is
optimal, i.e. $a_{i} \neq a_{i+1}$).
We assume familiarity with Conway's charming article \cite{C}.
 
Conway proved that his sequence has the property
$length(C_{i+1})/length(C_{i}) \rightarrow \lambda $, where
$\lambda =1.303577269\dots$ is {\em Conway's constant}.
He also stated that, more generally, if one starts
with an {\em arbitrary} nonempty finite string of integers, $B_{0}$ 
(except `boring old 22'), and
defines $B_{i}:=JHC(B_{i-1})$, $i>0$, then still
\begin{equation*}length(B_{i+1})/length(B_{i}) \rightarrow \lambda.
\end{equation*}
This is an immediate consequence of

\begin{theorem2} There exists an integer $N$ such
that every string decays in at most $N$ days to 
a compound of common and transuranic elements.
\end{theorem2}
 
Conway stated
that two independent proofs {\em used to exist}, one by himself
and Richard Parker (that only proved that $N$ existed), 
and another one by Mike Guy (that actually proved that  
one may take $N=24$,
and that it was best possible). Unfortunately
both proofs were lost. Here we announce a new proof
(which establishes that one may take $N=29$; with more computations
one should be able to rederive (or else refute) Guy's sharp
$N=24$).
 
The Cosmological Theorem is an immediate consequence of the following lemma.
 
\begin{theorem1} The length of any atom in 
the splitting of a $9$-day-old string is $\leq 80$. Every
such atom decays, in at most $20$ days, into stable or transuranic elements.
\end{theorem1}


The lemma is {\em proved} by
typing {\tt Cosmo(8);} in the Maple package {\tt HORTON},
retrievable from \newline
{\tt http://www.ams.org/era/1997-03-11/S1079-6762-97-00026-7/html/HORTON}. 

The procedure {\tt Cosmo}
computes iteratively all non-splittable
strings of length $i$ ($i=1,2, \dots $) that might conceivably
be substrings (`chunks') of an atom in the
splitting of a $9$-day-old-string
(by backtracking, examining its possible ancestors
up to (at most) $8$ days back and rejecting those that 
lead to grammatically incorrect ancestors;
see examples below). 
Every time a string of length $i$
is accepted, its longevity (number of days it takes to decay
to stable or transuranic elements) is computed, and checked whether
it is finite. The maximal longevity turned out to be $20$.
The program halts if and when an $i$ is reached for which the set
of such conceivable strings of length $i$ is empty.
 
If the program halts (it did for us),
then the Lemma, and hence the Cosmological Theorem, are proved.
In fact it halted after $i=80$, implying that there do not
exist atoms of length $>80$ that occur in 
the splitting of {\em mature}
(i.e. $9$-day-old) strings, and that all the atoms have bounded
($\leq 20$, as it turned out) longevity. 
We also get that the longevity of an arbitrary
string is $\leq 9+20=29$.
The input and output files may be obtained from \newline
{\tt
http://www.ams.org/era/1997-03-11/S1079-6762-97-00026-7/html/incosmo}\newline
and \newline
{\tt
http://www.ams.org/era/1997-03-11/S1079-6762-97-00026-7/html/ocosmo}\newline
respectively.
 
The Maple package {\tt HORTON}, also available from the authors'
websites \newline
({\tt http://www.math.temple.edu/\symbol{126}zeilberg}\newline 
and \newline
{\tt http://www.math.temple.edu/\symbol{126}ekhad})\newline 
rederives many other results
in Conway's paper, in particular it finds all the stable elements
{\em ab initio}, finds the minimal
polynomial for $\lambda $, finds the abundance of
all the stable elements,
and computes the longevity of any string. 
We refer the reader to the on-line documentation and to the source code.
 
\section*{Details}
 
Recall  that Conway proved that it suffices to consider strings
on $\{ 1,2,3\}$.
Let's call a chunk that starts with a comma {\em female}, and a chunk
that does not, {\em male}. Any chunk could have come either
from a father or a mother
(but of course not from both). Define
\begin{equation*}ParentOfGirl( a_{1} a_{2} a_{3} a_{4} a_{5} a_{6}  \dots ):=
a_{2}^{a_{1}} a_{4}^{a_{3}} a_{6}^{a_{5}} \dots ,
\end{equation*}
and
\begin{equation*}ParentOfBoy( a_{1} a_{2} a_{3} a_{4} a_{5} a_{6}  \dots ):=
a_{1} a_{3}^{a_{2}} a_{5}^{a_{4}} \dots\ .
\end{equation*}
Since a parent of a chunk may be either female or male
(but we have no way of knowing), any chunk has two potential
parents (but of course only one actual one), (up to) four 
(potential) grandparents
(some of them may disqualify on the grounds of being grammatically
incorrect), and so on. Now there are lots of chunks that cannot
possibly be factors of a mature string. Take for
example the female chunk ``$,12, 32,$''. It cannot be
a chunk of a $1$-day-old string (as observed in \cite{C}), since
starting at day $1$, all strings are descriptive, and
``$,12, 32,$'' would have been abbreviated  ``$,42,$''. So
we can {\em eliminate from the outset} any female string
of the form ``$, a c, b c,$'', in strings that are older than $0$ days.
 
Now consider the female string ``$,32,33,$''. It 
is grammatically correct, and so can be a chunk of a $1$-day-old string.
Her parent is:
``$222333$''. If the parent is a father, then it
is punctuated ``$2, 22, 33,3$'', which is grammatically incorrect,
and if the parent is a mother, then it would be
``$,22,23,33,$'', that is equally grammatically incorrect.
Hence we can conclude that ``$,32,33,$'', while it may
be a chunk of an atom in the splitting
of a $1$-day-old string, cannot possibly be
such a chunk of a $2$-day-old string.
 
Consider on the other hand the female string ``$,12,21,$''. Her
father is ``$2,11$'', and her mother is ``$,21,$''. Her paternal
grandparent is $21$ who is OK, being two-lettered.
Hence we cannot rule out ``$,12,21,$'' as a possible chunk in
an $L$-day-old string (for any $L>0$).
 
Let us define $U_{L}(i)$ as the set of female strings 
on the alphabet $\{1,2,3\}$ of length $2i$ that
do not split, and that 
have at least one
$(great)^{L-2}$ grandparent who is grammatically
correct, or some $(great)^{j-2}$ grandparent ($j