%_ ************************************************************************** %_ * 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