边看边说序列的宇宙学（一）原创 2016-01-22
安安以迁迁
科学公园
1、无聊的序列，奇特的理论
在介绍主题以前，我们先来做一件看似无聊的事情。我写下一个数： 1 然后问你看见了什么。你回答道：“1个1。”我把你的回答中的数字依次写下： 11 然后问你看见了什么。你回答道：“2个1。”我把你的回答中的数字依次写下： 21
然后问你看见了什么。你回答道：“1个2，1个1。”我把你的回答中的数字依次写下： 1211 然后问你看见了什么。你回答道：“1个1，1个2，2个1。”我把你的回答中的数字依次写下： 111221 然后问你看见了什么。你回答道：“3个1，2个2，1个1。”我把你的回答中的数字依次写下： 312211 我们可以一直这样下去，得到一个序列，序列里的每一项都是一个数字串。这个数字串序列被称为——
边看边说序列
Look-and-say sequence
也有人翻译成“外观数列”。注意到其实这并不是一个数列，因为其中的每一项并不是一个数，比如第三项21并不代表数字二十一，而是2和1这两个数字构成的字符串（本文称之为数字串）。
咋一看这个序列很枯燥，生成的过程一点技术含量都没有，大概只适合做脑筋急转弯的素材：“请问：1, 11, 21, 1211, 111221, 312211接下去一项是什么？”
1977年在贝尔格莱德举行国际奥林匹克数学竞赛的闲暇时刻，荷兰队向英国队提出的挑战，似乎是这道脑筋急转弯题的最初记载，不过也许它还有更早的历史。赛后，英国参赛队员将它带回英国，辗转相传。到了1983年11月，轮到在英国剑桥大学教书的著名数学家J·H·康威(John Horton Conway)做这道题了。
康威是一位在代数、几何、数论等领域都有相当大贡献的数学家。群论中的魔群月光猜想（一种拥有极其众多元素的被称作“怪兽”的群和模形式之间有意想不到的联系，猜想名字中的“月光”是“疯狂”的意思）由他和Simon P. Norton提出和命名；1998年英国数学家Richard Borcherds因证明此猜想而获菲尔兹奖。康威最为数学爱好者们乐道的则是他在组合游戏理论中的巨大成就，以一系列奇思妙想而闻名。他建立了超实数理论（这是一个把游戏和数结合在一起的理论，其中每个数都是一个游戏局面），并创作了以此理论为基础来分析大量经典（以及自创的）游戏的数学科普书籍《稳操胜劵》。他提出的“生命游戏”更是脍炙人口，让元胞自动机理论广为人知。科普大师马丁·加德纳将《数学嘉年华》一书题辞献给康威，感谢他在趣味数学领域作出了“深刻、优雅和幽默相结合的独特贡献”。
不过要比脑筋急转弯，象康威这样出色的数学家似乎也不比一个小学生更厉害。当他的学生抱着点恶作剧的心理拿这题给他做时，康威平时智计百出的脑子不好使了，阴沟里翻船，最终无奈地让学生告知他答案。
但和一般人听到答案后呵呵一笑了之不同，直到那年的圣诞节期间，康威还在不断研究——按照他的说法，是“把玩”——这个序列，并从中发展出一个怪异而美妙的理论来。在这个理论中有一个小小的宇宙，这个宇宙由92或94种元素组成。这些元素在衰变中互相演化，让这个小小宇宙以每天增长大约30%的速度膨胀。
2、分割、元素、化学定理和算术定理
在具体介绍这个理论的内容以前，先让我们也来把玩一番前面这个序列，以便对它的演化有一些直观的了解。 把这个序列多写出几项来：
注意到从第8项起在数字串中多写了一个“.”，它将数字串分成了前后两个子串，而这两部分接下去在互不影响地独立演化：
前子串总是以2结束；这是一个很容易证明的一般规律的特例：如果一个序列以某数字x结尾，那么它的所有后代也总以x结尾。而后子串的开头则以 1321…… →1113……→3113……→1321……
的形式循环，所以永远不可能以2开始。于是前后这两部分不会再交缠在一起。 另一个简单的例子是，如果一个数字串恰好以两个2结尾：……s22（其中s是不为2的数字），那么它可以分割成……s.22的形式。因为如上所说，前子串的后代总以s结尾，而后子串的后代永远是它本身：22。
从上面的例子里我们看到了这个理论中最重要的现象——数字串的分割：一个数字串可以分割成若干子串，使得它的演化结果是由这些子串的独立演化结果拼接而成。这样，对一个数字串的演化的研究可以转化成对它的子串的演化的研究。可以把这个现象和正整数的乘法分解作对比。我们知道，每一个大于1的正整数都可以唯一地分解成素数的乘积。素数犹如构建正整数的基本砖块，这个结论因极其重要而被称为算术基本定理，它确定了素数在数论研究中的核心地位。在康威的边看边说序列理论中，和素数的地位相当的是无法再分割得更小的数字串，康威称之为元素或原子。比如说从1开始演化的这个序列的前七项，都是无法分割的元素，而它的第8项则可分割成两个元素：11132和13211。这些不可分割的元素就是构建数字串的基本砖块。由元素拼接起来的数字串则被称为化合物。
毫无疑问，这种命名方式是一种暗喻，将边看边说序列理论中的对象和化学理论联系起来（当然这绝不是在暗示边看边说序列理论真的是研究现实世界中化学元素和化合物的理论）。在后面大家会看到这种暗喻是相当巧妙和贴切的。因此我们也将相当自由地使用一些很容易直观理解的术语，比如前面谈论数字串的“演化”以及它的“后代”。我们会谈论元素的“衰变”，也就是它的演化过程。数字串每演化一项，我们会说“一天后”数字串如何如何。康威把序列的第一项称为“第0天”，然后依次为“第1天”、“第2天”等等，在本文后续章节中我们甚至会看到“一天引理”和“两天引理”。 边看边说序列理论中的元素有许多种，确切地说，有无数种。比如将“13”重复n次的数字串1313……13就是无法分割的：假设它在某个1和3之间可以分割： ……1.3…… 下一步是 ……11.13……
出现了跨越分割号的连续三个1，这就是说前面假设中的分割是错误的。假设它在某个3和1之间可以分割： ……13.13…… 下面两步是 ……1113.1113…… ……3113.3113……
出现了跨越分割号的连续两个3，这同样是错误的分割。
康威的重要发现是：存在着一族共有92种特殊的元素，它们之间会互相演化。这92种元素被他称为“普通元素”，并分别以化学元素表中1号（氢）到92号（铀）元素命名。对于普通元素，有如下的结论：
1、存在92种普通元素（具体的元素列表和它们的性质将在稍后给出）。可以分割成普通元素的化合物称为“普通化合物”（为了简化叙述起见，我们也把普通元素看作是仅由一个元素组成的普通化合物）。
2、（化学定理）任何一种普通元素的后代都是普通化合物。普通化合物的后代也是普通化合物。除了第1号元素氢（即数字串22）外，从任意一种普通化合物开始，演化足够多天后，得到的化合物将由所有92种元素组成。
3、（算术定理）从任何一个普通化合物开始，每一步演化得到的数字串的长度和上一步相比，越来越趋近于一个固定常数λ。在此过程中，每种元素在这些数字串中的比例越来越趋近一个（仅和此元素本身相关，而与初始普通化合物的选择无关的）大于0的常数值，称为这种元素的丰度。上述固定常数λ是以下71次多项式的唯一的正实数根（也是所有根中模最大的）：
它约等于1.303577269034，称作康威常数。
在整个边看边说序列理论中，最令人吃惊的大概就是上面这个多项式了，乍一看真可谓从天而降，莫名其妙。欲知其妙，则需懂得一些线性代数的知识。我们将在本文后续章节中比较详细地讨论这件事情，并通过在康威发表论文之后线性代数的新成果，得到比以上算术定理中叙述的更好的结果。
化学定理指出，普通化合物是一个封闭的圈子，普通化合物只能演化成普通化合物。但是还有一些本不是普通化合物的数字串，它们可以在若干天内演化成普通化合物，掉进这个圈子里去。对这样的数字串来说，上面的结论绝大部分也同样成立，因为考虑的是“演化足够多天后”的事情。比如本文最开始讲到的从1开始的序列，数字串1本身不是普通化合物，但在第八天演化成可以分割为72号元素铪（11132）和50号元素锡（13211）的普通化合物。所以演化足够多天后，得到的化合物也将由所有92种元素组成，数字串的长度和前一天长度之比也将越来越接近康威常数，每种元素在化合物中的比例也越来越接近于此元素的丰度。
下面是完整的92种普通元素列表。本文中元素名称前通常以前下标形式注明相应的原子序数以便查询，毕竟不是每个人都能熟练地说出某元素的原子序数；笔者就无法做到这点，所以阅读康威的论文时对此有痛苦感。如果不是要自己动手验证的话，读者大可不必仔细阅读这个表格。这个表里值得注意的有几点：
~1号元素氢所代表的数字串22是唯一的衰变到自己的元素。
~92号元素铀所代表的数字串3是最短的元素。
~除氢外，第n号元素“一天后衰变物”一栏中都有一个加粗的第n-1号元素成份。康威基于这个性质给这92种元素排序，此性质将在后面的论证中用到。这个“第n号元素一天后会衰变出第n-1号元素”的次序并不是唯一的，康威只是挑选了其中一种。
~两种元素并不是可以随意拼合在一起的。比如92号元素铀（3）和20号元素钙（12）顺次拼合在一起的结果“312”应看作是另一种元素——30号元素锌，而非可分割的。而>铀（3）和91号元素镤（13）顺次拼合在一起的结果“313”既不是普通化合物，又不可分割，是一种不稳定的元素。判定一个数字串是否可被分割和如何分割的准则，称为“分割定理”，是比较技术性的内容，留在本文下篇介绍。
~一个31号元素镓会在下一天衰变出两个20号元素钙。这是唯一的某个元素会在下一天衰变出超过一个的同一种元素的情况。
下面是元素的丰度表，和康威的原始论文中一样，数据被乘以了一百万，以使长度固定；也就是说，一个普通化合物演化足够长时间后得到的数字串被分割成普通元素后，每一百万个元素里大约会有91790个1号元素氢，3237个2号元素氦，4220个3号元素锂等等。注重细节和有耐心的读者可以将下表这些数据和康威论文中的数据相对比，就会发现小数最后一位往往会有一点不同，比如2号元素氦的丰度是3237.2968587而原始论文中是3237.2968588。下表的数据我使用了两种不同的计算软件库得到，结果相同，所以应该没有错误。原始论文数据的差异应当是上世纪80年代时康威使用的计算软件的浮点精度不够的缘故，当然这完全没有什么大碍。有兴趣和能力的朋友也可自行计算验证，计算方法将在本文后续章节中介绍。
参考文献
[1] Henry Bottomley, Seven complete sequences for the Conway Look and Say elements[2] John Horton Conway, The weird and wonderful chemistry of audioactive decay, Eureka 46:5-16 (1985); reprinted in Open Problems in Communication and Computation, T.M. Cover & B. Gopinath, eds., Springer-Verlag, New York, 173–188 (1987).
| 
发表于 2016-3-12 23:15
收藏
分享