外观数列

定义 设 $ \mathbb{Z}_{\ge1} $ 为正整数集, $ W $ 定义为由 $ \mathbb{Z}_{\ge1} $ 生成的自由半群, 其中运算为并置, 按如下的方式定义映射 $ D\colon W\to W $, 设字 $ w\in W $ 可以表示为 $ w=a_1^{r_1}\cdots a_n^{r_n} $ 的形式, 其中诸 $ a_i $ 和 $ r_i $ 为正整数, $ a_i\neq a_{i+1} $, 则定义 $ D(w)=r_1a_1\cdots r_na_n $.

定理(一天定理) 设 $ w\in W $, 则在 $ D(w) $ 中, 一定不会出现从奇数位置开始的形如 $ baca $ 的数字串, 也不会出现形如 $ aaaa $ 或 $ aaabbb $ 的数字串, 其中 $ a $, $ b $ 和 $ c $ 是正整数.

证明 若 $ baca $ 在奇数位置出现, 相当于说在 $ w $ 中有 $ b $ 个 $ a $, $ c $ 个 $ a $, 而此时应该说 $ b+c $ 个 $ a $, 因此这样的数字串不存在.
若 $ aaaa $ 在奇数位置出现, 由前一情形知不可能, 若 $ aaaa $ 在偶数位置出现, 说明它前面至少存在一个数, 设为 $ d $, 那么 $ daaa $ 就是在奇数位置出现的, 这也是不可能的. 相同的论证也说明形如 $ aaabbb $ 的数字串不可能出现.

定理(两天定理) 设 $ w\in W $, 则 $ D(w) $ 和 $ D^2(w) $ 中包含的大于等于 $ 4 $ 的数字均是相同的, 即在第二天及之后不会产生除 $ 1 $, $ 2 $ 和 $ 3 $ 外的新数字, 此外 $ D^2(W) $ 中一定不存在形如 $ 3a3 $ 和 $ bc $ 的数字串, 其中 $ a $ 是正整数, $ b $ 和 $ c $ 是大于 $ 3 $ 的正整数.

证明 设 $ x\ge4 $, $ x $ 包含于 $ D(w) $, 显然也包含于 $ D^2(w) $, 若 $ x $ 包含于 $ D^2(w) $, 则它的来源有两种, 要么 $ D(w) $ 中包含若干个 $ x $, 要么 $ D(w) $ 中包含 $ x $ 个某数, 而由一天定理知 $ D(w) $ 中不可能有四个数连续出现, 这与 $ x\ge4 $ 矛盾, 所以只可能 $ x $ 包含于 $ D(w) $.
若 $ 3a3 $ 在奇数位置出现, 就是说 $ D(w) $ 中包含连续的 $ 3 $ 个 $ a $ 和 $ 3 $ 个某数, 由一天定理知这不可能, 若 $ 3a3 $ 在偶数位置出现, 说明它前面至少存在一个数, 设为 $ d $, 而由一天定理知形如 $ d3a3 $ 的数字串不可能在 $ D^2(w) $ 中出现. 相同的论证也说明形如 $ bc $ 的数字串不可能出现.

定理(起首定理) 定义如下几种类型的字,
- $ A $ 型, 形如 $ 1a\dots $, 其中 $ a $ 是不同于 $ 1 $ 的数, 省略号部分是空的或是不以 $ a $ 开头的数字串,
- $ B $ 型, 形如 $ 111\dots $, 其中省略号部分要么是空的, 要么是不以 $ 1 $ 开头的数字串,
- $ C $ 型, 形如 $ 3\dots $, 其中省略号部分要么是空的, 要么是不以 $ 3 $ 开头的数字串, 若省略号部分长度不小于 $ 3 $, 则前三个数不全相同,
- $ A' $ 型, 形如 $ 22\dots $, 其中省略号部分是一个A型数字串,
- $ B' $ 型, 形如 $ 22\dots $, 其中省略号部分是一个B型数字串,
- $ C' $ 型, 形如 $ 22\dots $, 其中省略号部分是一个C型数字串,
则任何一个字在映射 $ D $ 的迭代下一定会进入如下三种循环之一,
- $ \cdots\rightarrow A\rightarrow B\rightarrow C\rightarrow A\rightarrow\cdots $,
- $ \cdots\rightarrow A'\rightarrow B'\rightarrow C'\rightarrow A'\rightarrow\cdots $,
- $ \cdots\rightarrow 22\rightarrow 22\rightarrow 22\rightarrow\cdots $.

证明 若 $ w=22 $, 则落入第三种循环, 若 $ w $ 的前两个数都是 $ 2 $, 设 $ w' $ 是 $ w $ 去掉开头的 $ 22 $ 得到的字, 则要么 $ D^n(w)=22D^n(w') $ 对所有正整数 $ n $ 成立, 要么存在某个 $ n $ 使得 $ D^n(w) $ 不以 $ 22 $ 开头, 在前一情况下, $ w' $ 落入第一种循环等价于 $ w $ 落入第二种循环. 所以以下可以设 $ w $ 不以 $ 22 $ 开头.
显然 $ D^{n+1}(w) $ 一定在 $ D^n(w) $ 前面产生了一个新数, 并且当 $ n\ge1 $ 时, 产生的这个新数只能是 $ 1 $, $ 2 $ 或 $ 3 $, 则在足够长的时间后, 开头 $ 3 $ 个数中只有 $ 1 $, $ 2 $ 和 $ 3 $, 共有限种情况, 逐一验证即知它们均进入第一种循环.

定义 若字 $ w $ 可以表示为 $ a $ 和 $ b $ 的并置, 即 $ w=ab $, 并且 $ D^n(w)=D^n(a)D^n(b) $ 对任意正整数 $ n $ 都成立, 则称 $ w $ 分裂为 $ a $ 和 $ b $, 或 $ w $ 是 $ a $ 和 $ b $ 的分裂并置.

定义 若字不可分裂, 则称该字是一个元素, 由元素分裂并置得到的字称为化合物.

定理 每个字都是有限多个元素的化合物.

证明 对字的长度使用归纳法即可.

定理(分裂定理) 定义如下两种类型的字,
- $ X $ 型, 以大于 $ 3 $ 的数开头的数字串,
- $ X' $ 型, 形如 $ 22\dots $, 其中省略号部分是空的或是一个 $ X $ 型数字串,
$ D^2(w) $ 分裂为 $ lr $ 的充要条件是 $ l $ 和 $ r $ 满足如下三种情况之一,
- $ l $ 以大于 $ 3 $ 的数结尾, $ r $ 以小于等于 $ 3 $ 的数开头,
- $ l $ 以 $ 2 $ 结尾, $ r $ 为 $ A $ 型或 $ B $ 型或 $ C $ 型或 $ X $ 型,
- $ l $ 以 $ 1 $ 或 $ 3 $ 结尾, $ r $ 为 $ A' $ 型或 $ B' $ 型或 $ C' $ 型或 $ X' $ 型.

证明 使用起首定理进行细致的检验.

定义(常见元素) 设 $ x $ 是一个元素, 若对任意 $ w\in W $, $ w\neq22 $, 都存在一个 $ n $ 使得 $ x $ 包含在 $ D^n(w) $ 中, 则称 $ x $ 为一个常见元素.

定义(超铀元素) 对整数 $ n\ge4 $, 定义 $$ \mathrm{Pu}_n=31221132221222112112322211n,\qquad \mathrm{Np}_n=1311222113321132211221121332211n, $$ 称 $ \mathrm{Pu}_n $ 为钚的同位素, $ \mathrm{Np}_n $ 为镎的同位素, 统称为超铀元素.

定义(丰度) 设 $ w\neq22 $, $ D^n(w) $ 的分解中常见元素 $ E_i $ 出现 $ N_i(n) $ 次, 则 $ E_i $ 的丰度定义为 $$ a_i=10^6\lim_{n\to\infty}\frac{N_i(n)}{\sum_{j=1}^{92}N_j(n)}, $$ 可证明该极限存在, 且与初始词 $ w $ 无关.

定理(化学定理) 对每个 $ 1\le i\le92 $, $ D(E_i) $ 是常见化合物. 常见元素只有这 $ 92 $ 个. 除 $ E_1=\mathrm{H}=22 $ 外, 存在一个正整数 $ M $ 使得对所有 $ n\ge M $, $ D^n(E_i) $ 同时包含全部 92 个常见元素. 除 $ w=22 $ 外, 存在一个正整数 $ M' $ 使得对所有 $ n\ge M' $, $ D^n(w) $ 同时包含全部 92 个常见元素.

证明 逐一验证或查表即可得到第一个和第三个断言, 假设 $ x $ 是不同于这92个的常见元素, 由第一个断言知这92个元素除 $ \mathrm{H}=22 $ 外无论迭代多少次都不可能包含 $ x $, 矛盾, 第二个断言得证. 对于第四个断言, 存在一个正整数 $ n $ 使得 $ D^n(w) $ 的前 $ 3 $ 个数中只有 $ 1 $, $ 2 $ 和 $ 3 $, 对有限种情况逐一验证即知它们最终一定包含某个常见元素, 再由第三个断言知最终一定包含全部 92 个常见元素.

定理(宇宙学定理) 对任意 $ w\neq22 $ 和 $ n\ge24 $, $ D^n(w) $ 都是 92 个常见元素与超铀元素的化合物, 此外不含任何其他数字串.

定理(Perron–Frobenius定理) 设 $ A $ 是一个 $ n $ 阶方阵, 其中每一个元素都非负, 而且 $ A $ 对应的有向图连通, 则 $ A $ 有一个正的特征值 $ \lambda $, 它是 $ A $ 的特征多项式的一个单根, 对应的特征子空间是一维的, 并且 $ \lambda $ 大于等于任何其他特征值的模, 存在以 $ \lambda $ 为特征值的特征向量满足其各分量都严格正.

定理(算术定理) 设 $ w\neq22 $, $ L_n $ 为 $ D^n(w) $ 的长度, 则极限 $$ \lambda=\lim_{n\to\infty}\frac{L_{n+1}}{L_n} $$ 存在且与初始词 $ w $ 无关, 该极限称为康威常数, 大约为 $$ \lambda=1.3035772690342963912570991121525518907307025046594\ldots $$ 此外, 丰度是良定的, 即定义中的极限存在且与初始词无关.

证明 首先假设 $ w $ 是一个常见元素. 设 $ 92 $ 维列向量 $ v_n $ 的第 $ i $ 分量为 $ D^n(w) $ 中包含常见元素 $ E_i $ 的个数 $ N_i(n) $, 设 $ 92 $ 维行向量 $ u $ 的第 $ i $ 分量为常见元素 $ E_i $ 的长度, 则 $ L_n=u\cdot v_n=u\cdot\mathcal{M}^n v_{0} $, 由化学定理知 $ \mathcal{M} $ 对应的有向图除去 $ \mathrm{H} $ 之外连通, 则 $ \mathcal{M} $ 有一个大于等于其他特征值的模的特征值 $ \lambda $, 设它对应的特征向量是 $ r $, 设 $ v_0 $ 在 $ r $ 方向的投影为 $ c $, 则由 $ \lambda $ 大于其他特征值的模知在 $ n\to\infty $ 时有渐进公式 $$ \mathcal{M}^nv_0=c\lambda^nr+o(\lambda^n), $$ 所以 $$ \lim_{n\to\infty}\frac{L_{n+1}}{L_n}=\lim_{n\to\infty}\frac{c\lambda^{n+1}u\cdot r}{c\lambda^nu\cdot r}=\lambda. $$ 若 $ w $ 是任意不等于 $ 22 $ 的字, 则由宇宙学定理知 $ w $ 最终一定变成基本元素和超铀元素的化合物, 不妨设只有一个大于 $ 3 $ 的数, 若有多个则重复以下过程即可. 将矩阵 $ \mathcal{M} $ 扩充到 $ 94 $ 阶, 设 $$ P=\begin{pmatrix}0&1\\1&0\end{pmatrix}, $$ 则新矩阵有分块形式 $$ \begin{pmatrix}\mathcal{M}&B\\0&P\end{pmatrix}, $$ 其中 $ B $ 是 $ D(\mathrm{Np}_n) $ 中的非超铀部分, $ P $ 对应的特征值是 $ \pm1 $, 其模均小于 $ \lambda $, 所以新矩阵的模最大特征值仍是 $ \lambda $, 又因超铀部分的长度永远是有界的, 所以 $$ \lim_{n\to\infty}\frac{L_{n+1}}{L_n}=\lambda $$ 仍然成立.
对于丰度, 以 $ \|v_n\| $ 记其所有分量的和, 即 $ \sum_{j=1}^{92}N_j(n) $, 则 $ v_n/\|v_n\| $ 是与 $ v_n $ 同向的向量, 设 $ e_i=(\dots,1,\dots) $ 是除第 $ i $ 个位置外均为 $ 0 $ 的 $ 92 $ 维向量, 则丰度 $$ a_i=10^6\lim_{n\to\infty}\frac{e_i\cdot v_n}{\|v_n\|}=10^6\lim_{n\to\infty}\frac{c\lambda^n e_i\cdot r}{c\lambda^n\|r\|}=10^6\frac{e_i\cdot r}{\|r\|} $$ 极限存在且等于 $ \lambda $ 对应的归一化特征向量的第 $ i $ 分量的 $ 10^6 $ 倍.

定理 康威常数 $ \lambda $ 是代数数.

证明 $ \lambda $ 是 $ \mathcal{M} $ 的特征多项式的根, 故是代数数, 此外可以验证其最小多项式是 $ 71 $ 次多项式 $$ \begin{aligned} 0&=x^{71}-x^{69}-2x^{68}-x^{67}+2x^{66}+2x^{65}+x^{64}-x^{63}-x^{62}-x^{61}\\ &\quad-x^{60}-x^{59}+2x^{58}+5x^{57}+3x^{56}-2x^{55}-10x^{54}-3x^{53}-2x^{52}+6x^{51}\\ &\quad+6x^{50}+x^{49}+9x^{48}-3x^{47}-7x^{46}-8x^{45}-8x^{44}+10x^{43}+6x^{42}+8x^{41}\\ &\quad-5x^{40}-12x^{39}+7x^{38}-7x^{37}+7x^{36}+x^{35}-3x^{34}+10x^{33}+x^{32}-6x^{31}\\ &\quad-2x^{30}-10x^{29}-3x^{28}+2x^{27}+9x^{26}-3x^{25}+14x^{24}-8x^{23}-7x^{21}\\ &\quad+9x^{20}+3x^{19}-4x^{18}-10x^{17}-7x^{16}+12x^{15}+7x^{14}+2x^{13}-12x^{12}-4x^{11}\\ &\quad-2x^{10}+5x^{9}+x^{7}-7x^{6}+7x^{5}-4x^{4}+12x^{3}-6x^{2}+3x-6. \end{aligned} $$ 定理得证.