《数学女孩》同人：杭州纪行(Ch. 1-4)

· · 休闲·娱乐

数学女孩（同人）：杭州纪行(Ch. 1-4)

用 Markdown+LaTeX 排版，部分表达与 Lofter 不一致

DISCLAIMER

本作品是对结城浩《数学女孩》系列的二次创作，属于爱好者个人行为，不用于任何商业用途。

在创作中，作者将尽可能保证人物形象与原作匹配，避免出现 OOC 现象。然而，由于写作水平的限制，难免有吞设定、小学生文笔现象，敬请谅解。

本作品是在原作数学讨论氛围中较多融入人文性的尝试，因此数学部分的难度和深度会明显低于原作，对于程度较高的读者可能有些简单，敬请谅解。

序章：记忆中的樱花树·启程

我不止一次地梦到那棵樱花树，还有站在樱花树下的她。 这种现象是从什么时候开始的，我已经记不清楚了。我只记得在高中毕业之前，我曾与她们一起探寻如此多的世界：形式系统的世界、群的世界、流形的世界…… 樱花在春的曙光中肆意生长，在空中形成了优美的斐波那契螺旋。 真希望她也能看到啊…… --- “我们可以到杭州去。虽然印象中是一个以风景闻名的城市，但是那里的数学遗迹和应用也值得一见。” 在机缘巧合下，Eulerians 的大家得以重逢，米尔嘉提出了“数学之旅”的活动方案，得到了大家的一致认可。 “是中国的城市吗？我还从来没有去过中国喵，第一次就可以和大家一起去……”尤里兴奋地抓住了米尔嘉的胳膊。 “杭州原来还有这样不为人知的一面吗？之前一直以为只有风景与人文来着。”泰朵拉若有所思。 “到杭州的话，先飞到上海再乘火车更经济……”理纱已经开始筹划。 “说起来，你对中国古代的数学了解多少？”米尔嘉突然问我。 “嗯……我对历史之类的了解的不多，只是大概知道中国古代的数学长于应用，比如《九章算术》里面就记载了很多数学应用题及其解法。” “确实是这样，与古希腊的数学不同，中国的数学更加注重应用，但在这个过程中也提出了很多重要的数学证明，比如针对勾股定理的弦图证明，虽然理论化、体系化的程度和西方相比还是不足，但也是人类文明早期的重要成就。” “大概的行程……就这样规划吧。”在闲谈的间隙，理纱迅速整理好了一份方案。 “好耶！出发，去杭州喵！” --- “前方到站：杭州东站。” 列车驶过开阔的江面，右边一辆蓝色涂装的列车与我们隔着一道玻璃幕墙，缓缓停下，应该是地铁到站。我们的终点，也在距此不远处。 “这座桥是彭埠大桥，刚刚在我们右边的是杭州地铁19号线。”理纱看着地图说。 “我们的第一站是？”我问。 “前两天我们都会在西湖附近活动，计划的第一站是灵隐飞来峰。”米尔嘉说，“佛教经典中专门关于数学的论述不多，但也蕴含了包括时空、无穷在内的重要数学思想。” 列车缓缓靠站，我第一个下车，却差点摔个趔趄。 “杭州东站沉降严重，大家小心。”理纱提醒大家注意安全。 “你还好吗？”米尔嘉抓住我的手，熟悉的柑橘香愈发浓烈。 “没事，并没有摔到，谢谢。” 虽然其实行动并无大碍，但我还是牵着米尔嘉的手一路走到了地铁站。 ## 第一章：灵隐·无穷与增长 ### 1.1 三千大千世界 公交车稳稳停在灵隐路 32 号，顺着人流的方向走去，不久就到了写着“灵隐寺”的牌匾。 “先去飞来峰，这样的路径更优。”理纱说。 我们沿着山路拾阶而上，两旁是许多雕工精致的佛像，虽然我几乎都不认识。 “这是弥勒佛吧。”泰朵拉驻足在那尊最大的佛像前。 “肯定是的喵，我在书上看到过。”尤里得意地说，“佛教传说里还认为，须弥山为中心构成的单位世界，一千个单位世界是一个小千世界，一千个小千世界是一个中千世界，一千个中千世界是一个大千世界，这样换算下来，一个千大世界就是十亿个单位世界喵。” “我们只是大千世界的一小部分啊。”泰朵拉感叹。 “虽然是这样，但这毕竟还是一个有限的数吧。$10^9$，在日常生活中确实是很大的数了，但在数学家眼里应该也不算什么吧。”我说。 “说到这个，数学家确实喜欢研究一些很大的数，这形成了一门数学分支，叫作大数数学。”米尔嘉像之前一样，开始讲起了数学。 ### 1.2 大数数学 “所谓大数数学，英文很有意思，叫做 googology，其中 googol 就是一个很大的数，也就是 $10^{100}$，在一的后面写上一百个零。” “谷歌好像一开始就打算叫这个名字，后来因为打错了才叫 Google。”理纱说。 “googology……确实很符合英文的构词规则。但是，既然我们有了科学记数法，能够表示像 googol 这样的大数了，那为什么还需要大数数学呢？” “泰朵拉的问题很好。在我们的印象中，使用科学记数法已经能够表示出很多大数了。但是大数数学研究的’大数‘比它们还要大，甚至超出了常规的科学记数法能表示的范围。我们需要引入一些新的记号，比如高德纳箭头。” --- 我们需要引入一些新的记号，比如高德纳箭头。 $a$ 的 $b$ 次方 $a^b$，用高德纳箭头表示为 $a\uparrow b$。 我们把 $c$ 个高德纳箭头连在一起的形式记作 $\uparrow^c$，例如 $\uparrow^3$ 表示 $\uparrow \uparrow\uparrow$，那么 $a\uparrow^c b = a \uparrow^{c-1}(a\uparrow^c (b-1))$。特别的，我们规定 $a\uparrow^1 b=a^b$，并且 $a\uparrow^c 1=a$。可以看出，高德纳箭头是递归定义的。 > 求 $2\uparrow^2 3$的值。 “两个箭头，不能直接写成指数，所以要用定义展开吧。” $$ 2\uparrow^2 3 = 2\uparrow (2\uparrow^2 2) = 2\uparrow(2\uparrow(2\uparrow^2 1))=2\uparrow(2\uparrow2)=2\uparrow 4=16 $$ 这个数只是一个很小的例子，但是只要稍微修改一下这里的数值，它就可以变得很大。 > 求 $3\uparrow^2 3$ 的值。 “也是一样的吧。” $$ 3\uparrow^2 3=3\uparrow(3\uparrow^2 2)=3\uparrow(3\uparrow(3\uparrow^2 1))=3\uparrow(3\uparrow3)=3^{27} $$ “这个数看起来好大喵，只是稍微修改了一下，高德纳箭头就能把这么小的数变得这么大。” 高德纳箭头就是这样，它是大数数学的重要记号。利用高德纳箭头，我们可以构造出著名的葛立恒数。 定义 $G(1)=3\uparrow^4 3$，$G(n+1)=3\uparrow^{G(n)} 3$，则 $G(64)$ 就是葛立恒数。 之前我们算出来 $3\uparrow^2 3=3^{27}$，这个数大概是 7.6 万亿，不到 $G(1)$ 的零头，更遑论 $G(64)$ 了。大数数学研究的就是像这样的大数，用常规的科学记数法根本不可能表示出来。 “还有比葛立恒数更大的数吗？” 当然有比葛立恒数大的数，而且有无穷多个。不过，大数数学研究的是“有意义”的大数，像“葛立恒数加一”这种类型不在讨论范围内。一个典型的例子是 $TREE(3)$，它源于 $TREE$ 函数。这个函数比较复杂，但其结果戏剧性的地方在于，$TREE(1)=1$ 且 $TREE(2)=3$，它们都非常小，而 $TREE(3)$ 就成了远超葛立恒数的大数。可以看出，大数数学虽然不是主流的数学分支，但也包含许多有意思的东西。 --- “真的是很大的数啊。”泰朵拉感叹，“这都不能用天文数字来形容了，之前和学长一起去天象仪，知道可观测宇宙的直径是 930 亿光年，也不过是 $10^{26}$ 米的数量级，远远没有达到大数数学的门槛呢。” “确实如此，大数数学中研究的数超过了自然界中所有事物的数量级——你什么时候跟他去天象仪的？我怎么不知道？” 空气突然凝固了。 “应该是很久以前的事吧。”我赶忙顾左右而言他，“但是，这毕竟是有限大小的数，如果是无限大的话，情况会不一样吧。比如像自然数集和实数集这样的无限集合，比较的时候用的是映射的思想。” “自然数集是 $\aleph_0$ 的。”理纱说，“这是可数集的基数。” ### 1.3 无穷集合的势 米尔嘉的眼神又变得明亮起来。 “Aleph 是一个希伯来字母，用来表示无穷集合的基数，或者叫作’势‘。无穷集合的势用 $\aleph$ 可以依次表示成 $\aleph_0,\aleph_1,\aleph_2\cdots$。我们之前一起证明过，实数集的势大于自然数，使用的是对角论证法。“ 对角论证法？好像是有这么回事……原来是这样，大概想起来了。 “怎么，这也是很久以前的事吗？” “啊不不不，我记得很清楚，当时是按照对角线取小数位，构造出一个不可能出现在数表里的实数，进而证明不存在从自然数集到实数集的满射。包括后面村木老师的夺命 n 连问，我都记得。” “这才对嘛。”米尔嘉满意地看着我，“那么接下来，比较一下自然数集的幂集和实数集的势吧。” > 比较自然数集的幂集 $\mathscr{P}(\mathbb{N})$ 和实数集 $\mathbb{R}$ 的势。 “米尔嘉学姐，幂集的定义是什么？”泰朵拉问。 “幂集就是一个集合的全体子集构成的集合。比如 $\{1,3,4\}$，$\{2\}$ 都是幂集 $\mathscr{P}(\mathbb{N})$ 中的元素。幂集也可以写作 $2^\mathbb{N}$ 这样的形式。” “原来如此，幂集的英文是 power set 吧，所以可以写成 power 的形式，而且 $2$ 的乘幂正好对应了有限集合中的子集数量。” 这个问题确实有些难度，对角论证法证明了 $\mathbb{R}$ 的势比 $\mathbb{N}$ 大，但是 $\mathscr{P}(\mathbb{N})$ 并不是 $\mathbb{N}$，所以需要想办法构造某种映射。 “不妨把这里的实数集变成和它等势的 $(0,1)$，这样其中的任何一个实数 $b$ 用小数形式可以表示成 $0.b_1b_2\cdots b_n\cdots$。那么，我们就得到一个无穷数列$\langle b_1,\cdots,b_n,\cdots\rangle$，并且每一项都是 $[0,9]$ 的整数。”我试图回答米尔嘉的问题。“比如我把自然数集从小到大十个十个分组，然后每一组根据 $b_i$ 是从 $0$ 到 $9$ 哪一个数决定将哪一个数放入子集。这样就构造出了从 $(0,1)$ 到 $\mathscr{P}(\mathbb{N})$ 的单射，因为不可能存在两个不相同的实数对应到同一个子集上。” “等一下，我还是不太理解，什么是’分组并按照 $b_i$ 决定要不要放入子集‘？”泰朵拉打断了我。 “比如说，按照 $0\sim9$、$10\sim 19$，$20\sim 29$ 这样对自然数进行分组。初始时 $S=\varnothing$，如果 $b_1=3$，就把 $3$ 放入 $S$；如果$b_2=5$，就把 $15$ 放入子集；如果 $b_3=1$，就把 $21$ 放入子集……以此类推，所有的 $10(i-1)+b_i$ 构成的集合 $S$ 就是实数 $b$ 在 $\mathscr{P}(\mathbb{N})$ 中所对应的元素。这样的 $S$ 显然不可能同时对应两个不同的实数，因此这必然构成一个从 $(0,1)$ 到 $\mathscr{P}(\mathbb{N})$ 的单射。” “构造出单射只能说明 $(0,1)$ 的势不大于 $\mathscr{P}(\mathbb{N})$，还有剩下的一半，你打算如何做呢？” “确实，这样的映射并不是满射，因为如果存在同一分组的两个数被选进了 $S$，它就没法在 $(0,1)$ 中找到对应了。但是我们可以反过来想，只要存在从 $\mathscr{P}(\mathbb{N})$ 到 $(0,1)$ 的单射，这个证明也就完成了。换句话说，这个证明可以是非构造性的……” 我们沿着石板路慢慢走去。 “我想到一个办法，”泰朵拉说，“用类似二进制的方法，$b_i=1$ 当且仅当 $i-1\in S$，否则 $b_i=0$，这样就得到从 $\mathscr{P}(\mathbb{N})$ 到 $(0,1)$ 的单射了。” “这样就完整了。$A$ 不大于 $B$，$B$ 不大于 $A$，于是两者等势。实数集的势等于自然数集幂集的势，利用 power set 的写法，这个势可以写作 $2^{\aleph_0}$。” “$2^{\aleph_0}$，是 $\aleph_1$ 喵？” ### 1.4 连续统假设 无穷大原来还可以这样比较，不需要构造出双射，只需要构造出两个单射就可以了，真是神奇啊。 “尤里的问题提得非常好。$\aleph_1$ 是可数集基数 $\aleph_0$ 之后的第一个基数。但是这涉及到一个问题：$2^{\aleph_0}$ 究竟是不是 $\aleph_0$ 之后的第一个基数？这涉及到一个重要的假设：连续统假设。连续统是实数集的另一个名字，连续统假设认为 $2^{\aleph_0}=\aleph_1$，也就是说在可数集和连续统之间不存在其他的势。” “那连续统假设究竟是否成立喵？” “很遗憾，这个假设在 ZFC 公理系统中是不可判定的。ZFC 是对集合论的公理化抽象，因为它包含了皮亚诺算术公理，根据哥德尔第一不完备定理，其中定然存在一个不可判定的命题。” “哥德尔不完备定理……”泰朵拉若有所思，“是在研讨会上讨论过的那个数学问题，用哥德尔数进行编号，导出一个不可判定命题，我到现在还是不能完全明白。” “连续统假设是不可判定命题的一个具体的例子。它独立于 ZFC 公理，因此无法在这一系统中判定它正确与否。如果连续统假设正确，则 $2^{\aleph_0}=\aleph_1$，否则 $2^{\aleph_0}>\aleph_1$。不过，连续统假设是集合论中的具体命题，跟哥德尔不完备定理构造的算术命题属于不同层面的事情。” “如果把连续统假设加进 ZFC 公理系统，是不是就可以了喵？” “根据哥德尔不完备定理，即使将连续统假设加进公理系统，也会有其他不可判定的命题出现，这是包含了皮亚诺算术公理且相容的形式系统所不可避免的。不过这个洞察倒是启发我们一点，在这样的公理系统中，会有无穷多个不可判定的命题。因为我们可以一步一步将不可判定命题加入公理系统，而系统中定然有新的不可判定的命题，这个缝缝补补的工作是没有尽头的。” “希尔伯特的美梦这下是真碎了啊。”我苦笑。 “所幸数学没有因此崩溃，它只是独立于形式系统，并没有破坏形式系统的自洽性。我们依然能在其中展开推理与证明。”米尔嘉停下脚步，“一个有趣的巧合：在满足哥德尔第一不完备定理前提的形式系统里面，不可判定命题，如果按照等价关系划分，其等价类集合的基数恰好为 $2^{\aleph_0}$。” $\aleph$、连续统假设、哥德尔不完备定理……记忆如潮水般涌回。 “跟三千大千世界好像喵，可以通过幂集不断构造出比无穷更大的无穷，就像不断构造出比千世界更大的千世界一样。” 我们不断向上攀登，到了峰顶，小憩一下，就下山去，向着灵隐寺进发了。 ### 1.5 函数的增长 即使是工作日，前来灵隐寺的人也并不少。许多人拿着门口发放的三柱香，在大殿前的香炉排队等待敬香。进入大殿内，亦有许多跪拜的信徒。 大殿并非最高点。想要到达灵隐寺的最高处——华严殿，还要走一段台阶路。 “还好台阶的高度是有限的，要是这高度是无限大的话，我们就永远到不了了。”这是理纱式的幽默。 “假如台阶的数量是 $n$，如果人不会累的话就可以用 $\Theta(n)$ 的时间走完，但是考虑到人一定会疲劳，这个时间应该是 $\Omega(n)$ 的。”我接过这个话茬。 “这是时间复杂度喵？这里的 $\Theta$ 和 $\Omega$ 有什么区别呢？和之前用得最多的大 $O$ 是什么关系？” “$\Theta(n)$ 表示恰好为 $n$ 的阶，$O(n)$ 表示至多为 $n$ 的阶，$\Omega(n)$ 表示至少为 $n$ 的阶。所以，$\Theta(n)$ 其实就是 ‘$\Omega(n)$ 且 $O(n)$’的语法糖。” “语法糖是什么？是好吃的糖果喵？” 理纱久违地忍俊不禁。 “语法糖不能吃，它是用来简化表达的语法结构，对实际功能没有影响，但可以提高表达的效率。使用 $\Theta$ 比起同时使用 $\Omega$ 和 $O$ 要方便许多。” “我大概想起来了，”泰朵拉说，“这些记号都是用来描述 $T(n)$ 的渐近性质的，比如当 $T(n)=n^3+2n^2+1$ 的时候，用 $T(n)=\Theta(n^3)$ 就可以表示出当 $n$ 充分大的时候，$T(n)$ 和 $n^3$ 的增长同阶。” “这是对无穷的另外一种认识。”米尔嘉补充，“在集合论当中，无穷指的是元素的个数，比较时使用的工具是映射；在分析当中，无穷指的是函数越来越大的过程，比较时使用的工具是渐近分析。我们说 $T(n)=O(f(n))$，就是当 $n$ 大于某一个常数 $N$ 时，$T(n)$ 不超过 $f(n)$ 的常数倍。” $$ T(n)=O(f(n))\Leftrightarrow\exists N>0\exists c>0(n>N\to T(n)\le c\cdot f(n)) $$ $$ T(n)=\Omega(f(n))\Leftrightarrow\exists N>0\exists c>0(n>N\to T(n)\ge c\cdot f(n)) $$ “这里我们额外引入一个小 $o$ 记号 $T(n)=o(f(n))$，用理纱的话说，它是‘ $T(n)=O(f(n))$ 且 $T(n)\ne\Theta(f(n))$’的语法糖，比如 $n^2=o(n^3)$。但要小心，算法分析中 $n$ 是趋于无穷的量，但在一般的微积分里面并不一定，有时它又不能解释成语法糖了。” --- 但要小心，算法分析中 $n$ 是趋于无穷的量，但在一般的微积分里面并不一定，有时它又不能解释成语法糖了。 “一般的微积分……比如 $n$ 不是趋于无穷，而是趋于某一个常数的情况吗？” 没错，一般的微积分里面，$f(x)=o(g(x))$ 指的是下面这件事： $$ \lim_{x\to a} \frac{f(x)}{g(x)}=0 $$ 也就是说，当 $x\to a$ 时，$f(x)$ 是 $g(x)$ 的高阶无穷小，$f(x)$ 比 $g(x)$ 趋向零的速度更快。这个 $a$ 很关键，所以有的时候也会加上下角标，写成 $f(x)=o_{x\to a}(g(x))$。 “无穷小……说的是趋于 $0$ 的情况吧。但是在算法分析里面又说是趋于无穷的情况，这样不会冲突吗？” 完全不冲突，而且说的是同一件事。如果 $f(x)=o_{x\to a} (g(x))$，那么 $\lim_{x\to a} \frac{f(x)}{g(x)}=0$。这时候我们要关心 $f(x)$ 和 $g(x)$ 本身的趋势。如果 $f(x)$ 和 $g(x)$ 在 $x\to a$ 时趋向零，我们就是在比较两个无穷小，此时我们说 $f(x)$ 是比 $g(x)$ 高阶的无穷小；如果 $f(x)$ 和 $g(x)$ 在 $x\to a$ 时趋向无穷，我们就是在比较两个无穷大，此时我们说 $f(x)$ 是比 $g(x)$ 低阶的无穷大。 这里的无穷小、无穷大，指的是某一个函数。趋于零的就是无穷小，趋于无穷的就是无穷大。 “好多好多种无穷，要搞乱了喵。” 当你看到无穷符号 $\infty$ 时，你要敏锐地注意到它的定义依赖的是包括“任意”“存在”的量词的 $\epsilon-\delta$ 语言，而不是在谈论“无穷”这一抽象概念。“趋近于无穷”本身就是一种为了符合人类直觉而设置的语法糖；而当你看到“低阶无穷大”“高阶无穷小”这样的概念时，你应该认识到这实际上是在比较函数趋向某一个值的快慢，它的定义依赖的是比值极限或者说渐近分析。两者存在着重要的区别。至于集合论中的无穷，那又是另外一回事了。 “米尔嘉学姐，我想起来之前在微积分课本上有这样一个公式。” $$ f(x)-f(a)=f'(a)(x-a)+o(|x-a|) $$ “这里的 $o(|x-a|)$ 其实就是省略了$x\to a$ 的下角标，表示一个高阶的无穷小吧？” 泰朵拉的理解完全正确。实际的增量和线性主部 $f'(a)(x-a)$ 之间存在的误差项其实远远低于 $|x-a|$ 的距离。如果用定义写，就是这样的： $$ \lim_{x\to a} \frac{f(x)-f(a)-f'(a)(x-a)}{|x-a|} = 0 $$ 其中，分子就是实际误差，分母就是自变量之间的距离。随着 $x$ 向 $a$ 逐渐逼近，误差和 $|x-a|$ 相比可以忽略不计了。因此在 $a$ 附近可以使用线性近似 $f'(a)(x-a)+f(a)$ 来估算 $f(x)$ 的值。 泰朵拉熟悉的泰勒展开，其实就是高阶的近似，所以误差项会像 $o((x-a)^3)$，$o((x-a)^5)$ 一样，变成越来越高阶的无穷小。 --- 说到“熟悉”的时候，米尔嘉显然加了重音。 “不管怎么样，能把数学知识记住就是好的，最好‘一辈子都不会忘记’。” 泰朵拉的脸颊微微泛红。 “华严殿快到了，我们加吧劲，争取 $O(n)$ 之内到。”我连忙打圆场。 我们沿着灵隐寺的中轴线一路向上攀登，最终到达了华严殿前。 “中间是毗卢遮那佛，象征着宇宙的绝对真理和无限智慧。左右是文殊菩萨和普贤菩萨，分别象征智慧和行愿。”理纱念着导览中的介绍。 “这应该就是佛教修行的目标吧。”我说，“数学、哲学、佛教，大抵都在追求真理和智慧，只不过方法不一样。” “修行的速度不一样，也可以用渐近记号来表示喵。” ### 1.6 递归式与主定理 结束了灵隐寺的游览，我们来到公交换乘中心。 公交车一班接着一班，把游客运到不同的目的地——黄龙、湖滨…… “不同方向的乘客到不同的站台……这是分治算法喵！” “把问题拆分成规模更小的子问题，确实是分治法。”理纱表示赞同。 “涉及到分治的情况下，$T(n)$ 的表达式会比较特殊，它涉及到分解与合并子问题的代价，以及子问题的数量和规模。”米尔嘉说。 “之前的快速排序是不是就是典型的分治法？分成比枢纽项小的部分，以及比枢纽项大的子问题，然后分别求解，最后直接合并成原序列的有序排列。”泰朵拉问。 “是的，但是快速排序是不稳定的排序，它的复杂度受到数据分布的影响。一种更加稳定的利用分治思想的排序是归并排序。” --- 快速排序是不稳定的排序，它的复杂度受到数据分布的影响。一种更加稳定的利用分治思想的排序是归并排序。 归并排序同样划分为两个子序列，但这次是均匀划分，所以每个子序列的规模就是 $n/2$。我们递归对子序列进行排序，然后用 $\Theta(n)$ 的时间，把两个有序子序列合并成一个。于是，此时的递归式可以写成 $T(n)=2T(n/2)+\Theta(n)$，递归边界 $T(1)=\Theta(1)$。类比之前我们在快速排序中的证明方法，我们可以知道归并排序的复杂度是 $\Theta(n\log n)$。归并排序是稳定的排序，它的复杂度不受数据分布的影响。 --- “这样的递归式也可以用主定理来求解。”理纱说。 “主定理，那是什么喵？” “对于递归式 $T(n)=aT(n/b)+\Theta(n^d)$ 而言，两项当中谁是主，复杂度就由谁决定。” “这江东到底你是主，还是我是主？”尤里说着不知道哪里学来的句子。 “$a$ 和 $b$ 代表了子问题的分支数和规模，$d$ 代表了分解与合并子问题的代价，只要比较 $\log_b a$ 和 $d$，就可以确定复杂度了。” “原来是这样喵。那刚刚的归并排序里面，$\log_a b=d=1$，两者势均力敌，就是共主吗？” “没错，就像孙权和周瑜一样。”理纱说。 原来是三国电视剧里学来的啊，话说为什么这两人好像对上电波了一样？ --- “能再讲点主定理的事喵？”尤里在路上一直缠着理纱问问题，“比如如果 $\log_b a$ 更大会怎么样？” “如果 $\log_b a$ 比 $d$ 更大，说明处理子问题的代价是主导，复杂度是 $\Theta(n^{\log_b a})$，相当于底下的周瑜是主。” “那如果 $d$ 更大，是不是就是 $\Theta(n^d)$，相当于上面的孙权是主喵？” “这种情况下会特殊一点，需要存在常数 $c<1$ 使得对于足够大的 $n$，满足 $a (n/b)^d\le cn^d$ 才可以。这是正则化条件，防止子问题反弹。” “就是防止底下的周瑜造反喵！” （这两人到底是多喜欢三国电视剧啊！） ”小理纱，我有一个问题，如果递归式中 $\Theta$ 里面不是幂函数，主定理还能用吗？“泰朵拉问。 ”第一，不要加‘小’；第二，可以用，主定理是好方略，但要稍作修改。“ --- 主定理是好方略，但要稍作修改。考虑递归式 $T(n)=aT(n/b)+\Theta(f(n))$。为了生动形象，我们把顶层分解与合并的代价 $f(n)$ 称为“孙权”，把下层分支的代价 $n^{\log_b a}$ 称为“周瑜”。 先看”势均力敌“的情况，如果 $f(n)=\Theta(n^{\log_b a} \log^k n)$ 对于某个 $k\ge 0$ 成立，那么总的时间复杂度两者都要考虑，$T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$。“孙权”和“周瑜”的对数次方级别的微小差距不妨碍共为江东之主，但由于决策需要在两人间反复横跳，所以复杂度会多出一个 $\log n$； 再看“周瑜是主”的情况，如果 $f(n)=O(n^{\log_b a-\epsilon})$ 对于某个 $\epsilon>0$ 成立，说明“孙权”已经落后“周瑜”幂次的级别了，处理子问题的代价远高于分解与合并的代价，“周瑜”是真正的江东之主，复杂度 $T(n)=\Theta(n^{\log_b a})$。 最后看“孙权是主”的情况，如果 $f(n)=\Omega(n^{\log_b a+\epsilon})$ 对于某个 $\epsilon>0$ 成立，并且存在 $c<1$ 使得 $af(n/b)\le cf(n)$ 对于足够大的 $n$ 都成立，则“孙权”的势力以幂次的级别强于“周瑜”，同时正则条件又保证“孙权”能够镇压“周瑜”的反弹，此时分解与合并的代价是真正的主，复杂度 $T(n)=\Theta(f(n))$。 总之，$f(n)$ 是处理顶层事务的“孙权”，$n^{\log_b a}$ 是处理下层事务的“周瑜”，只有一个比另一个超出 $n$ 的幂次级别，才有可能成为真的主。 --- “原来是这样，想要成为真正的主就必须要以幂次的级别遥遥领先，上层想要稳住主导地位更是要能够压住底层的反抗才可以。这就是‘主定理’的含义吧。谢谢你……理纱。”泰朵拉差点又习惯性地加上“小”字，“但是，主定理并没有覆盖所有的情况吧。如果正则条件不满足，谁是主呢？” 理纱思索了几秒钟。 “此时主定理不适用，需要用其他方法，比如代入法、递归树等。” 公交车缓缓驶出灵隐路，进入北山街。 ### 1.7 无穷与超越 “这个小笼包好好吃喵！” 去灵隐寺走了那么多路，而且脑子还没闲过，确实是时候多吃一点东西了。 “无穷……好复杂，但是好有趣啊。”泰朵拉还沉浸在思考中。 “对无穷的思考是几乎所有文明先哲的共同追求。”米尔嘉也加入了讨论，“‘一尺之棰， 日取其半，万世不竭’，这是中国古人对无穷与极限的思考。” “无穷集合的势告诉我们，无穷也是有等级的。”我说，“所以无穷并不是终点，我们对它的追问必然要继续。” “无穷是可以把握的，通过逻辑和数学，我们能够正确应用无穷。”理纱说。 湖畔的微风轻轻吹拂，将五个人对数学与青春的热爱吹向无穷远的天际。 ## 第二章：西湖·图论与离散数学 ### 2.1 湖滨 今天的春光令人陶醉。我们站在杭州最繁华的中心，向着西湖走去。 “这就是西湖吗？真美啊……” 我们顺着人流缓缓朝着湖面走去，到了湖边，就沿着步道一路向北。 “由南向北，依次是一公园到六公园。”理纱说。她火红的头发在湖滨浓厚的二次元氛围中，竟不显得违和。 “直接用数字来命名，这么直接的喵？” 日光下的湖面波光粼粼，那熟悉的柑橘味芳香在春的酝酿下愈发浓烈。 “这里人很多，不要走丢了。”米尔嘉并没有征询我的意见。 （真是的，我又不是小孩子，怎么可能不牵着手就容易走丢呢？） ### 2.2 欧拉路径与哈密顿路径 我们迎着阳光，沿着北山街徐行。 白堤、苏堤、杨公堤，这是西湖上最有名的三条堤坝。在白堤的入口处，许多游人排成长队，等待放行。 “西湖上的桥好多喵，有没有可能一遍走完喵？” “这就是柯尼斯堡七桥问题的翻版，”我说，“尤里应该还记得吧？” “数奇点的数量喵……北里湖周边已经有四个奇点了，所以不可能实现。但是，如果只是要求经过所有顶点一次，还是可以实现的吧？” “欧拉路径不存在，但是哈密顿路径存在。”理纱说。 在白堤上望去，北山街的春色尽收眼底。远处的保俶塔在葱郁的山中，显得格外耀眼。 “欧拉路径……哈密顿路径……哥哥只告诉我怎样才能经过所有的桥恰好一次喵，这就是欧拉路径吗？哈密顿路径，是经过所有顶点恰好一次的路径喵？” “看来尤里对图论很感兴趣呢。”米尔嘉说。 --- 所谓图论，研究的是被称为“图”的数学对象的性质。一般化来说，图 $G$ 包括一个点集 $V$ 和一个边集 $E$。对于七桥问题而言，边是没有方向的，我们把这样的图叫作无向图。 经过所有的边恰好一次的路径称为欧拉路径，特别的，如果起点和终点相同，则称为欧拉回路。存在欧拉路径的充要条件是奇点的数量小于等于 2。显然，西湖上的桥梁不满足这一条件。 但是，经过所有顶点一次的哈密顿路径大概率是存在的。因为西湖景区内的道路——也就是图的边——足够密集，是一个稠密图。 “大概率存在……不像欧拉路径那样有个简单的判定标准喵？” 很遗憾，目前没有找到。不少数学家给出了存在哈密顿路径的充分不必要条件，但是哈密顿路径的简单形式的充要条件，仍然有待解决。而且，哈密顿路径问题，是一个 NP 完全问题，和我们之前提到的 3-SAT 一样。 “NP 完全问题……如果找到多项式的算法来解决，就能变成大富翁了喵！” 尤里知道怎么用多项式的做法来找到欧拉路径吗？ “嗯……哥哥教过我，只要一直找圈圈，然后把圈圈连起来变成大的圈圈就可以找到欧拉回路了。但是如果起点和终点不一样的话……” 尤里的做法在数学上叫作 Hierholzer 算法。它首先从任意的一个顶点出发找出一个自环，然后在这个自环上找一个新的起点，再从此出发找一个与已有自环无公共边的新自环，将原有的自环不断扩大，最后就找到了整个图的欧拉回路。至于起点和终点不一样的情况，我们可以引入一条从连结起点和终点的虚拟的边，从而化归到我们熟悉的欧拉回路问题。 “米尔嘉学姐，我有些不理解，这个算法是如何将两个自环合并成一个新的自环的呢？” 我们可以用递归的方式理解这个过程。 假设从 `A` 出发，找到一个自环 `A→B→C→D→E→A`，然后发现从C出发又可以有新的与已有自环不交的自环 `C→E→F→A→C`，则我们可以将其合并为： `A→B→C...C→D→E→A` 省略号的部分插入我们找到的新自环，这样就得到了一个扩展之后的更大的自环：`A→B→C→E→F→A→C→D→E→A`。用这样的方式不断扩展自环，直到其包含所有的边，就可以得到整个图的欧拉回路。欧拉路径可以化归到欧拉回路来进行求解。 “这个算法是多项式的喵？” 没错。如果用 $|V|$ 表示顶点的数量，$|E|$ 表示边的数量，则这一算法的复杂度是 $\Theta(|V|+|E|)$，是一个相当高效的算法。但是哈密顿路径不一样，尽管问题的形式看起来和欧拉路径十分相似。 --- “3-SAT，哈密顿路径……它们都是 NP 完全问题，也就是说只要用多项式时间解决任意一个，就证明了 P=NP……米尔嘉学姐，NP 问题是可以在多项式时间内验证的意思吧？就是如果有人宣称‘找到了游览西湖景区的哈密顿路径’，我们可以用多项式时间走一遍，就能验证他说得对不对吗？” “没错，如果有人宣称找到了哈密顿路径，我们就可以通过走一遍的方式验证他的路径是不是哈密顿路径。NP 问题的本义是可以在非确定性图灵机上用多项式时间求解，但也可以等价表述为可以在图灵机上用多项式时间内验证解答是否正确。” 我们穿过孤山公园，走过西泠桥，再一次回到北山街。 “之前用的是随机算法解决 3-SAT 问题，那也能用随机算法，或者类似的方法，解决哈密顿路径问题喵？” “是。”理纱给出了果断的回答。 “最新的进展是高德纳在 Claude 和 GPT 辅助下完成的有向网格图的哈密顿分解的证明，并使用 Lean 4 验证了其正确性。至于 P=NP，也许最终还是需要人类和大模型协作完成。”说到这里，米尔嘉顿了一下，“理纱，你相信 P=NP 吗？” …… 理纱望向远处的山和天空，火红的头发在日光的照射下格外耀眼。 “如果是这样，那未免也太简单了。” “说的是呢。”米尔嘉轻轻拂去理纱发额上的柳絮，“这个世界也许没有那么简单，学术界主流也认为 P≠NP。但是，人们从来没有停止对此类问题的探索，算法的价值不仅在于理论上的‘最优’和‘唯一’。理纱，你也是这样想的吗？” 理纱点了点头，“算法就是不断向不完美的世界妥协。” 我们又何尝不是呢？我想。 ### 2.3 启发式搜索 “北山街……灵隐路，我们又回来了喵！” 在尤里的提醒下，我才注意到路牌的变化。 “左转就是杨公堤了。” 与湖滨和北山街相比，杨公堤的人流更为稀少，建筑也被层叠的树木所取代，路旁则是小湖、小道，似是诱人神隐其中。 “之前以为西湖只是一个湖泊，没想到里面这么大，这真能看得完吗？”泰朵拉站在小道的入口处望去。 “深度优先搜索的复杂度是指数级的。”理纱说。 “搜索，是不是就是找东西喵？” “尤里说得对，搜索就是找东西，也就是找目标状态。”米尔嘉说。 --- 搜索就是找东西，也就是找目标状态。 假如我们要找到西湖里的某一处景点，比如花港观鱼，那么“花港观鱼”就是我们的目标状态。如果我们没有有关西湖景区的信息，直接开始寻找目标状态，这就是“无信息搜索”或者“盲目搜索”。而如果我们大概知道当前位置到目标还有多久，并利用这个信息优化搜索，这就是“有信息搜索”或者“启发式搜索”。 理纱刚刚说的深度优先搜索，就是从一个状态出发往一个方向探索到底，然后进行回溯并换方向继续向深处探索的搜索方式，是一种典型的无信息搜索。另一种无信息搜索方式是广度优先搜索，它向各个方向进行探索，并将每次探索到的状态都存入队列当中。算法不断从队列头中拿出状态，然后把队头状态的“后继状态”加入队尾。广度优先搜索可以帮助我们找到从当前位置出发，最短需要经过多少条边才能到达目标状态。 “广度优先搜索，能够让我们找到最短的路径喵？” 如果所有边代表的距离——也就是代价或者权值——都相等且为正的话，这是可以的，但是现实世界往往不是这样。此时，扩展节点的顺序是重要的。我们按照一定的规则确定扩展节点的顺序，最终会形成一个“优先队列”。 什么样的状态应该被优先扩展呢？对于每一个状态，我们引入评估函数 $f=f(g,h^*)$，每次都选择优先队列中 $f$ 小的状态，其中 $g$ 是这一状态到起点的距离，$h^*$ 是这一状态到终点的距离。但是 $h^*$ 往往不能精确知道，所以需要使用一个估计 $h$，称为启发式函数。 --- “米尔嘉学姐，我有一个疑问，$h$ 是用来估计状态到终点的距离的，那具体应该怎样估计呢？比如用直线距离来作为 $h$，这样低估了到终点的距离，是可以的吗？” “$h$ 的选取标准比较随意，泰朵拉说的欧氏距离是常见的一种 $h$ 选取，因为它同时满足可采纳性和一致性。” “可采纳，一致……英文是 admissible 和 consistent 吧？它们的定义是什么？满足它们有什么好处吗？” “简单来说，可采纳性就是 $h\le h^*$，表示启发式函数不会高估到终点的距离；而一致性就是 $h(v)\le c(v,w)+h(w)$，也就是三角不等式，表示走一条边减少的估计距离值不会超过这条边本身的权值。如果这两个条件都满足，则可以用评估函数 $f=g+h$ 作为扩展的依据，并保证能得到最短路径。这种算法就是 A* 算法，可采纳性和一致性保证了 A* 算法的最优性。” “如果以景区道路的长度作为边权值，欧氏距离作为启发式函数，那么显然满足可采纳性和一致性。”理纱说。 “导航软件里用的就是 A* 吧。”我说。 “没错，A* 是导航软件的常用算法。” “如果把估价函数 $f=g+h$ 换成其他的，也可以进行搜索喵？” “当 $f=h$ 时称为贪心搜索，当 $f=g$ 时称为一致代价搜索——理纱应该更喜欢叫它 Dijkstra 算法。前者不能保证最优，后者在边权非负的情况下能保证最优。” 出了杨公堤，站在南山路和虎跑路的路口，隐约能看到远处的雷峰塔。 “以目测作为启发式函数，雷峰塔比六和塔更近。” “不错，幽默感有进步。”米尔嘉笑了一下，轻轻抓住我的手腕。 ### 2.4 子图 “西湖真的逛不完喵。” 南山路的视野更为开阔，完整的西湖风光尽收眼底。 “我们逛的也只是西湖的一个很小的子图罢了。”理纱回头看了看虎跑路的方向，那是通往六和塔和钱塘江大桥的方向。 “子图，那是什么喵？” “取 $V$ 的子集 $V'$ 和 $E$ 的子集 $E'$，构成的新图 $(V',E')$ 就是原图的子图。” “原来是这样喵……跟子群很像，都是取子集，然后验证子集是否满足相应的条件。” “不错，类比是很重要的学习方法，”米尔嘉说，“我们在群论里会关心像正规子群这样的特殊子群，在图论里同样存在值得注意的特殊子图，比如说连通分量和生成树。” --- 我们走过的道路构成的子图，显然是连通的，任意两个顶点都能互相到达，这就是连通子图。如果将连通子图进行扩展，得到极大连通子图，就是连通分量。由于西湖的所有景点都有道路向量，所以整个西湖景区可以看作构成一个连通分量。 “米尔嘉学姐，我想到之前学过的概念，顶点间可达能不能看作顶点之间的等价关系？把顶点集除以‘互相可达’的等价关系是不是就是各个连通分量所对应顶点的商集？” 泰朵拉的理解完全正确，而且只要顶点被按照等价关系分类后得到商集后，相应的边自然就可以被归属到连通分量中。实际计算中，从某个顶点出发进行遍历，就可以得到这个顶点所在的连通分量了。 对于一个无向图，如果它是连通且无环的，那么就称为“树”。如果连通图的一个子图包含其所有的顶点，且是一棵树，那这个子图称为原图的生成树。 显然，假如原图是无环的，生成树只有一种可能，就是原图本身。但是，当图中存在环的时候，生成树的情况会变得复杂。 --- > 考虑 $n$ 个顶点的无向图，其边首尾相连使得整个图变为一个大环，即 $(1,2),(2,3),...,(n-1,n),(n,1)$，求这个图的生成树的数量。 “我们可以去掉一条边，然后就得到生成树了吧？既然有 $n$ 条边，那生成树的数量也是 $n$ 吧？” “没错，这就是环状图 $C_n$ 的生成树数量。接下来考虑完全图 $K_n$，它的生成树数量又是多少呢？” > 考虑 $n$ 个顶点两两相连形成的无向图（称为完全图），求其生成树数量。 西湖边绿树成荫，确实是适合数树的好地方。 $n$ 个顶点的完全图的生成树……我边走边想着这个问题。等一下，既然任意两个顶点都存在边，那么任何可能的树形结构都是原图的生成树，所以说…… “我想到了，其实只要考虑 $n$ 个顶点能形成多少种树就可以了。”我说。 米尔嘉露出了笑容。 “$n$ 个有编号顶点能够形成多少棵树，很像我们见过的计数问题吧？那该如何处理呢？” “之前和米尔嘉学姐一起做过很多这类问题，”泰朵拉说，“比如卡特兰数，分拆数……用递推式和生成函数来得出通项，这个问题也适用吗？” “应该是的吧，”我思考怎样构建递推关系，“用 $t(n)$ 表示相应的树的数量，那么 $t(1)=t(2)=1$。如果我们先确定了一个顶点作为‘树根’，那么它的‘子树’会有 $m$ 个……假设子树的顶点数为 $k_1,k_2,\cdots,k_m$，那么它们的和 $\sum k_i$ 应该是 $n-1$。” “这个分析完全正确，那假如 $m$ 已知的情况下，会有多少种树呢？” “子树的顶点数量为 $k_i$ 的话，那么会有 $t(k_i)$ 种子树的排布，然后子树选择一个顶点用来和树根相连，又有 $k_i$ 个选择。 $$ t(n,m) = \sum_{k_1+\cdots+k_m=n-1,k_i>0} C(n-1; k_1,...,k_m)\cdot k_1\cdot t(k_1)\cdot k_2\cdot t(k_2)...k_m·t(k_m) / m! $$ “$C(n-1; k_1,\cdots,k_m)$ 表示把 $n-1$ 个元素按照给定元素数进行划分的方案数，除以 $m!$ 是因为不需要考虑子树的顺序。一般的，$m$ 可以取 $1$ 到 $n-1$ 的数值，所以应该用二重求和。” $$ t(n) = \sum_{m=1}^{n-1} \frac{1}{m!}\cdot\sum_{k_1+...+k_m=n-1,k_i>0} C(n-1; k_1,\cdots,k_m) · k_1\cdot t(k_1)\cdot k_2\cdot t(k_2)\cdots k_m\cdot t(k_m) $$ “是不是遇到了一点困难？想一想生成函数吧，但是这时候不一样了哦，需要用到指数生成函数。” 指数生成函数？不是 $\sum t(n)x^n$ 了吗？ “$e^x$ 的泰勒展开，和数列 $1,1,1,1,\cdots$ 的关系，就是指数生成函数哦，泰朵拉最擅长这个了吧。” 米尔嘉这话为什么感觉听起来有些奇怪？不管了，还是先解出问题要紧。 我们转了一圈，又回到了湖滨，由于尚未到晚饭时间，先回酒店做个短休息。当然，最好能把数学题目先做出来。 ### 2.5 指数生成函数 根据理纱的建议，我们并没有把酒店订在湖滨，而是选在了不远处的文三路地铁站附近。这里紧邻黄龙国际中心，我和泰朵拉趁着休息的间隙在咖啡馆单独见面。 “学长，刚刚米尔嘉学姐说的泰勒展开和指数生成函数，是这样的吗？”泰朵拉在笔记本上写了起来。 $$ e^x = 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots $$ $$ f(x) = \sum_{n=0}^\infty a(x)\frac{x^n}{n!} $$ “我觉得她应该就是这个意思，给普通生成函数的每一项除以一个阶乘……但这和指数有什么关系？” “因为 $e^x$ 是指数函数？所以米尔嘉学姐特意提及 $e^x$ 的泰勒展开……这还是学长教我的呢。”泰朵拉的脸颊红了。 “刚刚的递推式里确实有很多阶乘，如果能用指数生成函数处理应该就能解决了。” $$ t(n) = \sum_{m=1}^{n-1} \frac{1}{m!}\cdot\sum_{ k_1+\cdots+k_m=n-1,k_i>0 } C(n-1; k_1,\cdots,k_m) \cdot k_1\cdot t(k_1)\cdot k_2\cdot t(k_2)\cdot k_m\cdot t(k_m) $$ “这里的 $C(n-1; k_1,...,k_m)$ 称为多项组合系数，可以用 $(n-1)!/(k_1!k_2!\cdots k_m!)$ 来表示，所以递推式可以写成这样： $$ t(n) = \sum_{m=1}^{n-1} \frac{1}{m!} \cdot \sum_{k_1+\cdots+k_m=n-1,ki>0} (n-1)! \cdot \frac{t(k_1)}{(k_1-1)!}\cdot \frac{t(k_2)}{(k_2-1)!}\cdots \frac{t(k_m)}{(k_m-1)!} $$ 然后，只要再用 $u(n) = nt(n)$ 重新写这个递推式，就可以用指数生成函数处理了。我们把右边的 $(n-1)!$ 移到左边，再用 $t(n)=u(n)/n$ 的代换，则得到一个便于处理的形式。” $$ \frac{u(n)}{n!} = \sum_{m=1}^{n-1} \frac{1}{m!} \cdot\sum_{k_1+\cdots+k_m=n-1,ki>0} \frac{u(k_1)}{k_1!}\cdot \frac{u(k2)}{k2!}\cdots \frac{u(k_m)}{k_m!} $$ “学长，请等一等，我感觉我可以往下做了，让我来，可以吗？” 我把笔记本递给泰朵拉。 “这里的 $u(n)/n!$ 可以看作指数生成函数 $U(x)$ 的 $x^n$ 项的系数，而且右边 $\sum u(k_1)/k_1!·u(k_2)/k_2!...u(k_m)/k_m!$ 这一部分其实就是 $U(x)$ 中 $x^{n-1}$ 项的系数吧。所以 $u(n)/n!$，其实就是 $\sum 1/m! \cdot (U(x))^m=e^{U(x)}$ 的 $x^{n-1}$ 项的系数，也就是 $x\cdot e^{U(x)}$的 $x^n$ 项系数。” $$ U(x) = x\cdot e^{U(x)} $$ 两边都是 $U(x)$，接下来只要把 $U(x)$ 展开成幂级数就行了吧。 “学长……对不起，我好像不知道该怎么办了。” 我仔细一看，才发现这个表达式中 $U(x)$ 处在指数的位置上，几乎没法用常规的代数变形处理。 “不需要道歉，这里的处理我也完全不会，泰朵拉能做出关于 $U(x)$ 的方程已经非常不容易了。” 泰朵拉还是一副懊丧的样子。 “还记得分拆数吗？那时我们也没有找到分拆数的通项公式。有的时候，答案并不是最关键的东西——要出去走走吗？” --- 正当我们走出咖啡馆的时候，一个熟悉的身影出现在眼前。 “怎么样？有结果了吗？” “米尔嘉学姐……我刚刚写出了关于指数生成函数的方程，但是后面进行不下去了。” “这样啊，因为 $x\cdot e^{U(x)}$ 很难处理吧？看来我们需要一些新的武器，比如拉格朗日反演。” “话说为什么你会在这里？”我忍不住问米尔嘉。 “好问题，这得先问问你自己。” 气氛开始变得微妙起来。 “米尔嘉学姐，拉格朗日反演是什么？” “拉格朗日反演提供了一种处理幂级数的技巧。” --- 拉格朗日反演提供了一种处理形式幂级数的技巧。 比如说，如果我们令 $\phi(U)=e^U$，那么形式幂级数 $U(x)$ 满足 $U=x\phi(U)$ 且 $\phi(0)\ne 0$。根据拉格朗日反演公式，有对应项的系数相等。 $$ [x^n] U(x) = \frac{1}{n} [\tau^{n-1}] \phi(\tau)^n $$ 这里的“$[\cdot]$”表示相应项的系数。将 $\phi$ 的定义代入，可以得到 $U(x)$ 的展开式。 $$ [x^n]U(x) = \frac{1}{n} [\tau^{n-1}] e^{nτ} = \frac{1}{n}\cdot \frac{n^{n-1}}{(n-1)!} $$ $$ U(x)=\sum \frac{n^{n-1}}{n!} x^n $$ 于是，$nt(n) = n^{n-1}$，从而 $t(n) = n^{n-2}$，这就是 $n$ 个有编号顶点构成的树的数量，称为 Cayley 公式。 --- “米尔嘉学姐，这里的拉格朗日反演公式，是用来求解某种特定形式的幂级数函数方程的吧？” “没错，拉格朗日反演是通过函数方程构建幂级数逆元的显式表达式。它可以用复变函数中的柯西积分定理来证明。” “复变函数……之前讨论黎曼猜想的时候见过，没想到在这里还会用到。” “不管怎么说，这个问题总算告一段落了。” “指数生成函数，拉格朗日反演……现在的‘武器库’又丰富了好多。谢谢米尔嘉学姐！谢谢学长！” “差不多要到吃饭时间了吧，我去叫一下她们两个？”我说。 ### 2.6 离散数学 “哥哥怎么跟泰朵拉学姐讨论数学不叫我，真讨厌喵！” “这个……十分抱歉，因为是泰朵拉找的我，不过她有重大发现，虽然中间过程非常复杂，但是生成树的数量可以简单表示为 $n^{n-2}$。” “真的喵？原来答案这么简单，数学好神奇！” “大家有什么想吃的吗？”泰朵拉说。 “是啊，吃什么喵？”——我疑心尤里又在模仿三国电视剧台词。 夜幕降临，街上川流不息，城市的灯光照亮了文三路的夜空。 -- “‘文三数字生活街区’……这条路好有科技感喵！” “这里原先是电脑市场，后来改造成了现在这样。”理纱看向远处的数码大厦，“刚刚你们说的 Cayley 公式，有一种更简单的证明方法，用有编号树的 Prüfer 序列。” “Prüfer 序列……那是什么？”米尔嘉问。 （难以置信，米尔嘉居然会向别人请教数学） “不断去掉树中编号最小的叶子节点，并将和它相邻的节点纳入序列，最终会得到一个长度为 $n-2$ 的序列，就是 Prüfer 序列。” “原来如此，利用 Prüfer 序列对树进行计数……确实比用生成函数算半天要简单许多。” “米尔嘉大人也有不了解的数学概念吗？” “数学是一门非常广阔的学科，我也只是了解其中的一小部分。这里用到的数学知识属于离散数学，里面有很多我还不熟悉的概念。” “离散数学？那是什么喵？” “是研究离散对象的数学分支，比如命题逻辑和谓词逻辑，计算复杂性，计数和图论等等。它是计算机科学的基石，理纱在这方面比我更了解。” “离散数学，我听说过，”泰朵拉说，“在计算机里面很重要。它不像纯数学那样抽象，每一个概念都对应计算机科学中的真实需求。” “这里科技感的背后都是大量的离散数学。”理纱说。 “等下吃完饭要去看音乐喷泉吗？”我问，“湖滨的可能赶不上，但武林广场的应该还来得及。” ### 2.7 音乐喷泉 晚上八点半，武林广场。 武林广场的人不像湖滨那样密集，不少人坐在喷泉前的台阶上。 喷泉中央的少女塑像一手高高举起，另一只手彼此牵着，似是优雅的舞者；喷泉边缘的少女塑像则端庄地坐着，分别演奏着不同的乐器。 “开始了！” 悠扬的古典乐响起，灯光交替着闪烁，水柱一圈一圈打向空中。 “是约翰·施特劳斯的《春之声》。”米尔嘉说。 “$\omega$ 的华尔兹？还是半径为零的圆？” “怎么，你还想再来一次？” 音乐到高潮处时，中央的水柱喷涌到十米多高，视觉上甚至超出了不远处的杭州大厦一倍有余。 “和你想的一样吗？” 柑橘味的芳香包裹了我。 “如果被她们看到了……” “你闭嘴。”米尔嘉说。 --- 音乐喷泉的表演结束了，这是今天最后一场，广场上的人们陆陆续续散去。 “好壮观……这里就是杭州的中心喵？” “杭州的中心，是这里，还是西湖呢？”泰朵拉问。 “武林湖滨中心，一般会这样表述。”理纱说，“这是杭州三大城市中心中最早的一个。” “还有别的中心喵？” “钱江两岸中心，城西科创中心。” “建立这么多中心，都是为了城市的发展吧。为了适应未来的需要，杭州不可能永远停留在老城的舒适区内。” “永恒发展是世界的普遍规律，数学是这样，城市是这样，我们也是这样。”米尔嘉看向远处，“也许有一天，我们也会离开‘老城’，走向各自的‘新城’。” 晚风吹得人有些凉。 “发展新城不会以放弃老城为代价，”不知道为什么，我产生了一种强烈的表达欲望，“这里永远会是杭州人的精神寄托。” “原来你是这样想的啊，”米尔嘉笑了，“那希望你能说到做到哦。” （为什么是我？不是在聊城市的事吗？） 我们进入武林广场的地下通道，朝着地铁站走去。春的思绪与疑惑离散在这片夜色中。 ## 第三章：道古桥·数书九章·秦九韶 ### 3.1 道古桥畔 今天的杭州，下着淅淅沥沥的小雨。 我们打着伞，行走在这条名为“天目山路”的主干道旁。“天目山”，有趣的名字，是上天的眼睛吗？如果有了那“天目”，是否就能看穿数学密林中的真相呢？ “这里就是道古桥了，道古，是秦九韶先生的字。”米尔嘉指着一处古朴的小桥说。 那座石桥跨过一条窄窄的小溪，在树林之间并不显眼。由于地面有些湿滑，我们缓缓前行，到了桥边，才见得一座写着“道古桥”的石碑。 “这是秦九韶先生建的桥喵？” “是，但是这座桥是现代人拆除重建后的，距离原来的桥一百米左右。我们脚下的小溪叫作西溪，当时为了方便两岸的人通行，秦九韶特意建了这座桥。” 雨滴在西溪的水面上激起微小的涟漪，柑橘味的芳香混杂着草木香，让这个雨天不再令人烦扰。 “秦九韶不仅是一位数学家，还是一位心系百姓的官员。他的身上有强烈的中国知识分子的情怀，”米尔嘉看向桥旁的石碑，“他在杭州为官期间，创造了大量可以直接用于实际应用的数学方法，并用它解决了许多实际问题。说到这个，你们能想到用秦九韶的名字命名的公式或算法吗？” “米尔嘉学姐，我想到算三角形面积的海伦公式，实际上又称为秦九韶公式，这应该属于秦九韶的重要贡献吧？” “没错，秦九韶的‘三斜求积术’等价于海伦公式，只是形式不同。秦九韶还用这一方法测算钱塘江潮汐涨落，实现了数学的现实应用。” “还有计算多项式的秦九韶算法，”理纱说，“是高次多项式求值的高效算法，可以用 Θ(n) 的时间计算多项式的值。” “没错，秦九韶用这种方法求解一元高次方程的正根，称为‘正负开方术’。” ### 3.2 秦九韶算法 秦九韶用这种方法求解一元高次方程的正根，称为‘正负开方术’。 考虑多项式 $a_n x^n +a_{n-1} x^{n-1} + ... + a_1 x + a_0$，如果用常规方法代入求值，时间复杂度为 $\Theta(n^2)$。为了优化这一过程，数学家提出了降次的思想，比如 $x(a_n x^{n-1} + a_{n-1} x^{n-2}+...+a_1) + a_0$。这样，在计算 $x^n$ 时相当于复用了 $x^{n-1}$ 的结果。秦九韶算法将这一降次过程反复进行，将计算 $n$ 次多项式转换为 $n$ 个一次多项式。 比如，对于三次多项式 $2x^3-x^2-3x+1$，可以转化为 $x(2x^2-x-3)+1=x(x(2x-1)-3)+1$。每次迭代计算时，将当前结果乘以 $x$，并加上下一项的系数即可。这样，计算 $n$ 次乘法和 $n$ 次加法，时间复杂度为 $\Theta(n)$。 “那要怎么用这种方法求解高次方程呢？” 秦九韶将这种算法运用于“正负开方术”中。所谓“开方”，与现在我们说的开高次方根有相似之处。我们考虑一个三次方程，如 $x^3-x-1=0$，目标是求出其在 $1.5$ 附近的根的数值值。 先考虑这个根的整数部分 $1$，称为“首商”，“商”就是根。于是做减根变换 $x=1+y$（实际上就是 $y=x-1$，将 $x$ 减去方程的“商”后设为新元），我们需要把原本关于 $x$ 方程的系数变为关于 $y$ 的方程的系数，这里用到的就是秦九韶算法。 $(-1, -1, 0, 1)$，从左到右称为“实、方、廉、隅”，依次对应常数项、一次项系数、二次项系数、三次项系数。 接下来用增乘程序：**从最高次项系数开始，依次将 $n$ 次项系数乘上“商”之后的结果增加到 $(n-1)$ 次项上。** $(-1, -1, 0, 1)\to (-1, -1, 0+1\times 1=1, 1)\to (-1, -1+1\times 1=0, 1, 1)\to (-1+0\times 1=\mathbf{-1}, 0, 1, 1)

注意到新的常数项为 -1，但我们还要对 (0, 1, 1) 进行同样的操作，进而得到关于 y 的新方程的各项系数。

$(2, 1)→(2+1\times 1=\mathbf{3}, \mathbf{1})$，也就是说新方程的二次项系数为 $3$。三次项系数无法再操作，于是为 $1$。得到完整的新方程为 $y^3+3y^2+2y-1=0$。 接下来用同样的方法解新方程：首先“估根”，以方约实（常数项的相反数除以一次项系数），得到 $1\div 2=0.5$。令 $g(y)=y^3+3y^2+2y-1$，得到 $g(0.5)>0, g(0.4)>0, g(0.3)<0$，所以选择 $0.3$ 作为“续商”。做减根变换 $y=z+0.3$，得到关于 z 的新方程。 $(-1, 2, 3, 1)\to (-1, 2, 3+1\times 0.3=3.3, 1)→(-1, 2+3.3\times 0.3=2.99, 3.3, 1)→(-1+2.99\times 0.3=\mathbf{-0.103}, 2.99, 3.3, 1)$，于是常数项为 $-0.103$。 $(2.99, 3.3, 1)\to(2.99, 3.3+1\times 0.3=3.6, 1)\to (2.99+3.6\times0.3=\mathbf{4.07}, 3.6, 1)$，于是一次项系数为 $4.07$。 $(3.6, 1)\to (3.6+1\times 0.3=\mathbf{3.9}, \mathbf{1})$，于是二次项系数为 $3.9$，三次项系数为 $1$。最终得到新方程：$z^3+3.9z^2+4.07-0.103=0$。 反复执行同样的“估根→新方程→更新新方程各项系数”，并将每一步所得的“续商”与“首商”相加，就可以一位一位求得原方程的数值解。我们刚刚就求得数值解 $1.3$，这个过程还可以继续。 ------ 这个算法的过程听起来真是有够复杂的。但是，“一位一位地算”令我想到了些什么。 “我好像明白这个算法的本质了，先给出关于根的一个不足估计 $c_1$，然后得出关于 $(x-c_1)$ 的新方程，再得出关于 $(x-c_1)$ 的新方程的根的不足估计 $c_2$，然后得出关于 $(x-c_1-c_2)$ 的新方程，再得出关于 $(x-c_1-c_2)$ 新方程的根的不足估计 $c_3$……最后把所有的估计加起来就是 $x$ 的数值解了吧。真是巧妙啊！” “米尔嘉学姐，我好像知道秦九韶算法在这里的作用了。要得到关于 $(x-c)$ 的新方程，用秦九韶算法将 $x=c$ 代入原本关于 $x$ 的方程的左边进行求值，得到的值就是新方程的常数项，然后不断迭代得到新方程的各项系数。不过……得到新方程的常数项后，继续得到新方程的更高次项系数，这一步的原理是什么呢？” “得到更高次项的系数仍然用的是将 $x=c$ 代入求值，”理纱说，“原理是通过新旧多项式同步求导不断把低次项系数扔掉。” “当时还没发展出微积分吧？”我说。 “这就是中国古代数学的特点，在理论有限的情况下，优先发展应用。”米尔嘉补充，“中国古代甚至在没有发展出矩阵理论的情况下实现了用消元法求解线性方程组。可惜的是，理论的缺乏使其在近代没能像西方那样创造严密的数学体系。” “理论化……看来很重要喵。” ### 3.3 中国剩余定理 > 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ “这也是秦九韶解决的问题喵？” “这个问题最早不是秦九韶解答的，但秦九韶的‘大衍求一术’将这类问题的解法系统化了。我们现在利用数论的知识，也可以尝试解答。” “除以 $3$ 余 $2$，除以 $5$ 余 $3$，除以 $7$ 余 $2$……”泰朵拉念着，“那就是说除以 $21$ 要余 $2$……最小的解是 $23$，也满足除以 $5$ 余 $3$ 的条件。” “泰朵拉应该看出来了吧，这个问题实际上是在求解同余方程组。不过，你是怎么看出这个数除以 $21$ 余 $2$ 的呢？” “嗯……因为除以 $3$ 和除以 $7$ 的余数都是 $2$ 吧，所以 $x=3m+2=7n+2$，也就是说 $(x-2)$ 是 $3$ 和 $7$ 的公倍数，也就一定是是 $21$ 的倍数，因此 $x=21k+2$，所以除以 $21$ 就余 $2$ 了，而 23 正好满足所有的条件。” “没错，最小的解是 $23$，在此基础上加上 $3$、$5$、$7$ 的公倍数，也就是 $105$ 的整数倍，即可得到许多其他的解。这个问题最早出自约公元 4 世纪的《孙子算经》，书中的解法是‘三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之，得二百三十三，以二百十减之，即得’。意思就是用 $70\times 2+21\times 3+15\times 2-105\times 2=23$ 来得到最小的答案。如果除以 $3$、$5$、$7$ 的余数一般化为 $R_1$、$R_2$、$R_3$，可以用 $70R_1+21R_2+15R_3-105P$ 来求解，这里通过减去 $3$、$5$、$7$ 的最小公倍数 $105$ 的整数倍来求得最小的答案。” “米尔嘉学姐，这里的 $70$、$21$、$15$ 是怎么来的？它是用除数算出来的吗？” “$70$ 是 $5$ 和 $7$ 的公倍数，$21$ 是 $3$ 和 $7$ 的公倍数，$15$ 是 $3$ 和 $5$ 的公倍数，也就是说这里的每一个数都是除自身外其余除数的乘积。对于所有除数两两互质的线性同余方程组，可以用中国剩余定理求解。” ------ 对于所有除数两两互质的线性同余方程组，可以用中国剩余定理求解。 所谓同余方程组，就是由同余式 $x\equiv a_i \pmod{n_i}\qquad i=1,2,...,k$ 构成的方程组。例如，之前的问题中的同余方程组，可以这样表示： $$ \begin{cases} x\equiv 2\pmod 3\\ x\equiv 3\pmod 5\\ x\equiv 2\pmod 7 \end{cases} $$ 中国剩余定理指出，当除数（或者叫模数）两两互质时，同余方程组的解 $x$ 关于全体模数的乘积 $N=n_1n_2\cdots n_k$ 满足一个同余关系式： $$ x\equiv c_ia_i\pmod N $$ 这里的 $c_i=m_i m_i^{-1}$，其中 $m_i=N/n_i$ 表示当前除数以外的除数的乘积，而 $m_i^{-1}$ 则是 $m_i$ 关于模 $n_i$ 的逆元。例如，考虑“$x$ 除以 $3$ 余 $2$”的情况，$a_1=2$，$m_1=5\times 7=35$，$m_1^{-1}$ 是 $35$ 在模 $3$ 意义下的逆元。 “逆元……我记得是群论当中的概念吧，什么是模意义下的逆元呢？” 群论里面说元素 $a$ 的逆元 $a^{-1}$ 是满足 $a*a^{-1}=a^{-1}*a=e$ 的元素对吧，这里模 $3$ 意义下的逆元就是考虑 $0, 1, 2$ 构成的代数系统，其中 $m_i$ 的逆元 $m_i^{-1}$ 就是使得 $m_i\cdot m_i^{-1}\equiv 1 \pmod 3$ 的相应元素。由于 $35$ 除以 $3$ 的余数为 $2$，相当于求 $2$ 在模 $3$ 意义下的逆元，也就是 $2$。因为 $2\times 2\equiv 1 \pmod 3$。由于模数两两互质，$N/n_i$ 和 $n_i$ 互质，从而保证这个逆元一定存在。 因此，$c_1=35\times 2=70$。用同样的方法，求出的 $c_2, c_3$ 分别为 $21$ 和 $15$。 这样，和式 $\sum c_ia_i=70\times 2+21\times 3+15\times 2=233$，通过减去 $105$ 的倍数，得到最小解 $23$。 ------ “米尔嘉学姐，我想到一种理解方式：线性同余方程组的解 $x$ 除以模数之积 $N$ 所得的余数，必然是各个余数 $a_i$ 的线性组合，而线性组合的系数 $c_i$ 则通过‘其余模数之积 $m_i$’和‘$m_i$ 在模 $n_i$ 意义下的逆元’相乘得到，只要我们能求逆元，就能很快求出线性同余方程组的解，是这样吗？” “就是这样没错，不过泰朵拉可以想一想，为什么这样得到的结果就一定是线性同余方程组的解呢？” “因为 $\sum c_ia_i$ 除以 $n_j$ 的余数只由 $c_ja_j$ 贡献吧，剩下的 $i\ne j$ 的 $c_i$ 包含 $m_i$ 因子，而 $m_i$ 是 $n_j$ 的倍数，可以直接忽略。由于 $c_j=m_j\cdot m_j^{-1}$，所以 $c_j$ 除以 $n_j$ 的余数必然为 $1$，从而余数就变成了 $1\cdot a_j=a_j$……中国剩余定理好神奇！” “秦九韶是怎么求解逆元的喵？” “秦九韶求逆元的做法称为‘大衍求一术’。” ### 3.4 大衍求一术 秦九韶求逆元的做法称为“大衍求一术”。 我们要求解像 $ax\equiv 1 \pmod n$ 这样的同余方程，且保证 $\gcd(a,n)=1$，也就是逆元存在。秦九韶通过一种高度机械化的方式解决这一问题。这里的模数 $n$ 称为“定母”，系数 $a$ 称为“奇数”，逆元 $x$ 称为“乘率”。 “置奇右上，定居右下，立天元一于左上”，我们用 $2\times 2$ 矩阵表示为 $\begin{bmatrix}1& a\\ 0& n\end{bmatrix}$。 “先以右上除右下”，这说的是右下方的数大于右上方的数的情况。考虑一般的 $\begin{bmatrix} x_{11}& x_{12}\\ x_{21}& x_{22}\end{bmatrix}$ 矩阵，如果 $x_{12}<x_{22}$，则“右上除右下”是以右上方的 $x_{12}$ 为除数，得到 $x_{22}\div x_{21}$ 的商 $q$ 和余数 $r$。这里的余数范围是 $1\sim x_{21}$，与我们通常用的余数不同，称为**最小正剩余**。 “这里的余数一定是正数喵，还可以等于除数，是怎么做到的呢？” 我们令商 $q=\lfloor(x_{22}-1)/x_{21}\rfloor$，余数 $r=x_{22}-q\cdot x_{21}$，就可以得到这一组特殊的商和余数，并用于后续的计算。 “所得商数与左上一相生，入左下。”将左下的 $x_{21}$ 增加 $q\cdot x_{11}$，这里的“相生”就是相乘，“入”就是将这个乘积加到某个变量上。得到的那个余数 $r$ 则填入右下，成为新的 $x_{22}$。这样，当 $x_{12}<x_{22}$ 时，相当于对矩阵进行了一个变换： $$ \begin{bmatrix} x_{11}& x_{12}\\ x_{21}& x_{22}\end{bmatrix} \to \begin{bmatrix} x_{11}& x_{12}\\ x_{21}+q\cdot x_{11}& r\end{bmatrix} $$ “然后乃以右行上下以少除多，递互除之，所得商数随即递互累乘，归左行上下”，意思就是说，只看右边这一列，谁少谁做除数，谁多谁做被除数。比如，当 $x_{12}>x_{22}$ 时，矩阵变换的对应行会变化： $$ \begin{bmatrix}x_{11}& x_{12}\\ x_{21}& x_{22}\end{bmatrix} \to \begin{bmatrix} x_{11}+q\cdot x_{21}& r\\ x_{21}& x_{22}\end{bmatrix} $$ 这里的 $q$ 和 $r$ 是 $x_{12}$ 除以 $x_{22}$ 的最小正剩余意义下的商和余数。可以看出，我们每一步迭代需要先比较右边这一列，并把较小的值作为除数，得到的商和余数用来更新被除数所在的行。 “使右上得一而止，左上为乘率。”当右上方 $x_{12}$ 变为 $1$ 时，左上方的 $x_{11}$ 就是我们要求的逆元。 这样说还是有些抽象。“示例是理解的试金石”，我们来用大衍求一术求解一下刚刚提到的逆元。 ------ > 用大衍求一术，求 $35$ 在模 $3$ 意义下的逆元。 其实就是求 $35x\equiv 1 \pmod 3$ 的解吧。$35$ 是“奇数”，$3$ 是“定母”……置奇右上，定居右下……总有一种上古文课的感觉。 “是这样吧，把系数放到右上方，模数放到右下方，左上方是 $1$，初始的矩阵就是 $\begin{bmatrix}1& 35\\ 0& 3\end{bmatrix}$。”我说。 “看样子你古文学得不错嘛。”米尔嘉说，“那接下来该比较什么，更新什么呢？泰朵拉知道吗？” “米尔嘉学姐，我记得好像是比较右边这一列的吧……$35$ 比 $3$ 大，所以商是 $11$，余数是 $2$ 吧。这里的余数是正的，所以最小正剩余的结果和正常的求余是一样的。左上方是 $1+11\times 0=1$，右上方就是余数 $2$，所以矩阵变为 $\begin{bmatrix} 1& 2\\ 0& 3\end{bmatrix}$。” “感觉变简单了好多喵。”尤里加入了进来，“现在 $3$ 比 $2$ 大，商 $1$ 余数 $1$，左下角更新为 $0+1\times 1=1$，矩阵就变成 $\begin{bmatrix} 1& 2\\ 1& 1\end{bmatrix}$ 了喵。” “$2>1$，商 $1$ 余数 $1$，左上变为 $1+1\times 1=2$，右上变为余数 $1$，矩阵变为 $\begin{bmatrix} 2& 1\\ 1& 1\end{bmatrix}$……右上为 $1$，算法终止，返回值为左上方 $2$。” 一步接一步，大衍求一术成功完成了。 “大衍求一术好厉害喵！一直做同样的操作，就把逆元求出来了。” “中国古代的数学能够解决很多现代数学中的重要问题，现在的许多算法都源于中国古代的数学贡献，”米尔嘉说，“刚刚我们以数学完成了和秦九韶跨越千年的对话。” 雨渐渐停了，道古桥上惠风和畅。 “当然，我们刚刚还没有提到秦九韶最重要的贡献——大衍总数术，它是一套完整的求解线性同余方程组的算法，并且能够处理模数不互质的情况。关于这一部分，由于秦九韶的记载以古文写成，不同的文献有不同的解释，但总体的思想和之前我们求解‘乘率’的方法是一致的。” 跨越千年的对话……通过古文的记载，能够还原出完整且高效的求解问题的办法。 ——数学超越时空。 “这个石碑后面好像还有字喵！”尤里在镌刻着“道古桥”的石碑的后方喊着。 ### 3.5 数与道非二本也 石碑的后方预留有供人站立的台阶，离水面十多厘米高。 “中文……可以尝试理解一下，”我说，“《数书九章》，是秦九韶的著作……碑文还特别提到了中国剩余定理。” “没错，《数书九章》包括了各个方面的数学内容，其中的‘大衍类’就是我们提到的整套线性同余方程组的解法。其他的章节，则聚焦于数学的具体应用，如计算田亩，建筑施工，交易利息等。” “都是现实生活中的问题喵。” “秦九韶认为数学可以‘经世务，类万物’。《数书九章》中的大量应用问题，就是这一观点的体现。” “确实是实用的数学，但这样不会太浅层了喵？” “这确实是中国古代数学的局限性，但是，秦九韶本身是反对把数学看成浅近的学问的。他认为数学可以‘通神明，顺性命’。这里的‘神明’和‘性命’与现在的含义不同，泛指世界运动变化性质的范畴，以及万物的天赋与禀受。这也就是说数学可以帮助我们通晓世界的变化与发展，以及了解事物的内在性质。秦九韶还认为，‘数与道非二本也’，说的是数学和道有着相同的本源。” “道？怎么变哲学了喵？” “这与秦九韶所处的时代有关系。他所处的南宋时期，人们热衷于探讨‘道’和‘器’，大致上是普遍法则和具体事物的关系。秦九韶的意思可以通俗地理解为，数学和道有相同的本源，都是世界普遍的法则，现代的数学发展更加印证了这一点。” 用哲学概念描述数学……有意思。 阳光穿过云层，将水面照得波光粼粼。树叶的沙沙声和马路上不时传来的汽笛声混杂在一起，同我们一起穿越道古桥畔的数理千年。 ## 第四章：钱江新城·分形维数·挂谷猜想 ### 4.1 天地换乘 天气渐渐放晴了，西溪河上清风徐来，水波不兴。 “做了那么久数论了，好饿喵！” “要不先去旁边吃饭吧，下午还要去钱江新城呢。”泰朵拉说。 沿教工路向北走，左转进入熟悉的文三路，在新丰小吃随便吃了点东西，就准备出发了。 “19 号线永盛路方向，在御道换乘 9 号线，往观音塘方向到新业路。”理纱调出地铁图。 列车经过杭州东站后，从地面逐渐进入高架。窗外的景象由漆黑变得明亮，依稀可见远处的江水静静地流淌着。 “天地换乘，要下楼。”下车后，理纱打头阵乘上了前往地面的长扶梯，泰朵拉和尤里紧随其后。 19 号线御道站站台位于彭埠大桥上，列车在此为飞越钱塘江做准备，站台高度离地面足足有 15 米。 “你们先下去吧，我买瓶水。” 我前往自动售货机买了瓶水，当然这只是借口。 “米尔嘉……这个扶梯很平稳，不会有事的……那边有直梯，要过去吗？” 米尔嘉没有说话，默默靠在我后面，我们就这样乘扶梯下了楼。 真是的，为什么非要勉强自己啊？之前摩天轮那次也是这样。 从地面向下前往 9 号线站台的扶梯短了许多，我们一切如常地向下走去。 只有我自己知道，我的身上留下了柑橘香的余温。 ### 4.2 市民中心 “终于到了喵！那个换乘好长啊，我们现在是在哪里喵？” 眼前是一座环形的高楼，四周若干 L 形建筑林立着。 “这里就是市民中心了，”我说，“周边这些建筑应该可以进去看看吧。” 走进图书馆，里面人头攒动。书架上是各种各样的中文书，铺满一整层。随手拿下一本，只能勉强看懂大致意思。 我把书放回书架，却看见米尔嘉正拿着一本书入神地看了起来。这真奇怪，难道米尔嘉会中文？我缓缓凑近过去，直到空气变成柑橘味的。 “我不会中文”米尔嘉缓缓开口，“但是有些术语，日中的汉字写法是相似的，还有公式和图表，可以大致知道在讲什么。” 我这才看清上面的内容。书上画着科赫雪花和谢尔宾斯基三角形的图像，同时还有一行公式：$H=\log(N)/\log(S)$。 “这里是用自相似性定义豪斯多夫维数。之前你做的那个三维版谢尔宾斯基三角形，你知道它的豪斯多夫维数怎么算吗？” 三维版的谢尔宾斯基三角形——其实应该叫四面体，应该还是去游乐园的那次做的。一个大的四面体有 $N=4$ 个自相似的小四面体（一个小四面体在顶上，另外四个在底下），小四面体的线度是大四面体的一半，所以缩放因子 $S=2$，豪斯多夫维数应该是 $\log(4)/\log(2)=2$。 “这样的话不该叫‘三维’的谢尔宾斯基三角形，因为实际上维数小于 $3$ 吧。”我说。 “确实是这样。虽然一般情况下的豪斯多夫维数要用更复杂的数学来计算，但对于自相似分形这种特殊情况，用刚刚的简单方法就可以。” 米尔嘉还记得上次游乐园的事情啊。她当时拼的是什么来着？好像是克莱因瓶吧。 “其实我们脚下的这座城市，也有类似分形自相似那样的结构哦。” 米尔嘉说出这句话的语气异常轻松，但却让我更为困惑：城市那么复杂的结构，怎么能用分形那样单纯的数学概念来解释呢？ 带着这样的疑惑，我在书海内徘徊许久，直到大家决定前往下一个地点。 ### 4.3 分形结构 虽然高楼林立，但市民中心中间的广场和楼宇之间的空地异常开阔，不但没有产生威压感，反而令人心旷神怡。 “哥哥刚刚在跟米尔嘉大人说什么悄悄话喵？是不是又在讨论什么有趣的数学问题？” “是关于分形维数的，尤里了解吗？” “之前在书上看到说科赫雪花是 $1.26$ 维，谢尔宾斯基三角形是 $1.58$ 维，好奇怪喵，为什么会算出来这种数字呢？” “比如说，如果把谢尔宾斯基三角形的边长放大到两倍，它占据的‘面积’会变成原来的几倍呢？这里可要好好想一想。” “难道不是四倍喵？不对，谢尔宾斯基三角形的中间一块是空的，所以只会放大到三倍，这样维数就会比 $2$ 要小。那就是要问 $2$ 的多少次方等于3。”尤里边说边用手指在空中比划三角形的样子，“所以 $1.58$ 这个数字是解 $2^x=3$ 这个方程解出来的近似值！好有趣喵。” “如果中间面积不断被挖空的话，剩下来的面积不应该是 $0$ 才对吗？”泰朵拉的眼中充满了困惑。 我仔细回想谢尔宾斯基三角形的结构，确实，按照自相似性无穷无尽地砍掉中间的三角形，剩下部分的面积确实应该是 $0$ 才对。那这个东西占据的空间应该叫什么呢？ “是测度。”米尔嘉像上学时那样突然靠过来，“用周长和面积，难以描述分形的特征，比如科赫雪花的周长无穷大而围成的面积有限，我们定义这些自相似分形的维数是基于测度论的，通过缩放因子和测度变化的对数关系，就可以定义它的豪斯多夫维数。” “我知道了，科赫雪花的曲线一边有四个自相似部分，缩放了三倍，所以解 $3^x=4$，就得到了 $1.26$。虽然围成的面积是关于线度平方，但是我们看的是外围曲线的‘测度’喵。”尤里把“测度”这个词发得很重。 “其实周长和面积就是测度的一种，只不过面对分形的时候这种常规的测度会失效，我们需要更先进的武器。”米尔嘉说，“刚刚我们定义的是豪斯多夫维数在自相似分形中特殊的简化计算方法，一般的严格定义需要用到豪斯多夫外测度从零跳变到非零点的临界值，对我们来说太复杂了。” “米尔嘉……你刚刚说的那个城市分形是怎么回事？城市也像分形一样有自相似结构吗？” “城市规划展览馆就在斜对角。”理纱突然冒出来。 “正好，过去看看你就知道了。”米尔嘉柑橘般的笑容在阳光下氤氲。 ### 4.4 城市的结构 展厅内的介绍文字清一色是中文，我们借助一旁的图片尝试理解其含义。 “我们现在在这里。”理纱指了指地图上的一点，西湖往东紧邻钱塘江的地方。 “好像离西湖也不是很远吧，”我说，“为什么这里被称为是第二中心呢？” “虽然表面上只有五公里左右，但实际上从西湖到钱塘江，算是一种不小的变化。”米尔嘉看着地图说着，“刚刚不是说了城市分形吗？这么说主要是借用自相似结构和分形维数的概念，这个地图尺度还不够，我们需要更大的。” 我们穿过各式各样的展厅，从“钱塘自古繁华”到“勇立潮头”——虽然不完全明白其中的意思——然后来到上层，俯瞰巨大的沙盘。 “原来杭州这么大喵，为什么西边都是山呢？” 我这才看清，西边那些群山也被呈现在了沙盘上，之前那张地图仅仅是杭州的东部占比极小的部分。 “如果生活在西边的话，是不是很不方便？”泰朵拉说，“没有地铁，说不定公交也很少，出来一趟会很累吧。” “但那边的聚落并不少，你看，”我的手指沿着钱塘江溯流而上，直到一片比西湖大得多的湖泊，“那一片虽然离市中心很远，但人类活动非常活跃。” “新安江水库，千岛湖。”理纱说，“城市东扩，旅游西进。” “可惜千岛湖对我们来说太远了。”米尔嘉说，“不过我们确实可以去到杭州的第三中心，它名字带有城西，但也没有那么西边，坐地铁就可以到。” “多中心……自相似结构……这就是城市分形吗？”我问。 “严格地讲这只是一部分，我们可以借助沙盘粗略讨论它的几何分形结构，但是涉及到网络结构和演化过程就需要更复杂的数据了。实际上计算用的是一种数值方法，用边长为 $r$ 的网格去盖城市要素，如果需要的网格数量是 $N(r)$，我们可以用 $N(r)$ 和 $r$ 的拟合函数关系来得出分形维数。” ### 4.5 计算分形维数的数值方法 我们可以用 $N(r)$ 和 $r$ 的拟合函数关系来得出分形维数。 之前尤里用解指数方程的方式思考了数学上自相似分形的维数，现在我们同样要解这样一个指数方程：$N(r)\cdot r^D=C$。这里的 $C$ 直观理解为“整个城市中的有效要素占据的某种测度的大小”，它是一个常数。如果把 $r^D$ 移到右边，就有 $N(r)=C\cdot r^{-D}$这样一个函数关系了。 “像之前一样把这里的 $D$ 解出来是不是就可以了喵？” 这里会比之前复杂一点，因为 $r$ 和 $N(r)$ 都是变量。对于成对相关变量的统计分析，数学家和科学家都有一套成熟的武器。比如取对数变成 $\log N(r)=-D\log(r)+C$，这样就成了 $\log N(r)$ 和 $\log(r)$的线性回归问题。这里的 $C$ 实际上是取对数后的了，但因为它的具体值与我们的问题无关，所以我们可以把它作为一个形式常数保留在那里，不用变形。 “线性回归是什么？是最小二乘喵？” 最小二乘是求解线性回归问题的一种重要方法。有意思的是，它既可以是求得精确解的解析方法，也可以是用近似迭代求得数值解的数值方法。实践中由于数据量可能很多，常常用数值的最小二乘法来解决这个线性回归问题。 “米尔嘉学姐，这个方法看起来很清晰，只要 $r$ 和 $N(r)$ 就能做。但是，如果确定 $N(r)$ ，是不是必须指定‘需要覆盖哪些我们感兴趣的元素’？这应该如何确定呢？” 这个问题问得很好，城市是一个复杂多样的系统。我们在研究城市分形时，通常要选取道路、建筑等感兴趣的要素。这种要素的选择没有绝对的标准，需要考虑城市的实际特征和我们要研究的问题。 我们可以定性估计三大中心附近的局部分形维数。武林湖滨中心附近老城区大致呈现出空间密集，高度接近于 $2$ 的分形维数特征；而钱江两岸呈现出典型的带状分布，维数相对更小；城西科创中心处于快速发展的阶段当中，分形维数目前较小，但随着城市要素的密集化最终会逐渐变大。 ### 4.6 解析方法和数值方法 "闭馆时间快到了。"理纱看着时间说，就像当年提醒我们放学的瑞谷老师。 用不同尺度的盒子去度量同一座城市，分析盒子数量和盒子尺度的关系，就可以得到分形维数，这种方法真有意思。 “用盒子来套，接近于计算闵可夫斯基维数的思想。但我们采用了一种数值方法。”米尔嘉说。 我们朝着展馆的出口走去，太阳已经快落山了。 “数值方法，就是需要用计算机才能算出来的方法喵？” “不，人一样可以采用数值方法，像 Mathematica 这样的符号计算软件也一样可以做解析方法。数值方法的核心在于使用巧妙的数值逼近来得到问题的近似解，并评估这个解的精度和可靠性。” “米尔嘉学姐，刚刚那样的线性回归问题，我听说可以用最小二乘公式直接得到解析解，那这是不是一种解析方法？” “最小二乘公式可以用来解析求解线性回归问题，但我们刚刚面对的原本的问题是‘城市结构的分形维数’，我们用不同尺度的小方格去度量得到一部分 $N(r)$ 与 $r$ 的数据点，本身就已经是一种数值逼近方法了，最小二乘公式只是解决了线性回归的解析求解，并没有进行原本问题的解析求解。” “用割圆术求圆周率，算不算一种数值方法？”我问。 “没错，这也进一步说明了数值方法并不是计算机时代的全新方法，计算机大幅将人从繁琐的计算中简化出来，使得数值方法在这个时代迎来了新生。现在计算机可以用级数来将圆周率算到任意的精确度，只要时间充足。” ### 4.7 新的工具 展馆里很多信息是中文写的，很难以看懂，只能通过图片理解大概。 不过，还能像之前一样听米尔嘉讲数学，也不能说不算一项收获。 我们走在富春路上，向左平行于钱江路，向右平行于之江路。无论是富春，钱江，还是之江，本质上都指同一条江流。数学又何尝不是这样，零测集到了概率论里面变成了几乎不可能事件，到了分形几何中又化身成为分形结构。 “零测集挺有意思的，对吧？”米尔嘉仿佛看出了我的心思似的，“我们之前说了自相似分形的性质，而数学家研究的很多结构是没有自相似性的，比如零测挂谷集合，这就需要新的工具。” “挂谷集合，是挂谷猜想喵？在电视节目里面看到过！”尤里兴奋地在空中比划，“一根针往各种方向转来转去，转出来扫过的集合就是挂谷集喵。但是人家不明白，为什么说它可能是零测集呢？如果转出来占据空间，哪怕占的空间很小，不应该也有正的‘测度’吗？” “现代的挂谷集合不用连续转针了。”米尔嘉笑着摸了模尤里的脑袋，抓住她的手在空中转动，“像这样连续转出来的挂谷集测度永远不为零，所以数学家把这个定义弱化，只要集合能放下每个方向的针就可以。这样，如果针的排列方式够古怪，我们就能得到零测挂谷集合了。” “米尔嘉学姐，那最近解决的那部分挂谷猜想，研究的是什么问题呢？”泰朵拉问。 “三维空间中零测挂谷集的维数问题。”米尔嘉说，“它没有自相似结构，而且单纯的盒子覆盖很容易重叠，所以我们之前研究分形的初等方法，在这全部失效。解决这个猜想需要用到高深的几何测度论和调和分析工具。” “全都不会做——”尤里又学着不知道哪部电视节目的人物说话腔调。 “万象城到了，先吃饭吧，”理纱开口，“尤里，你更喜欢黄瓜还是苦瓜？” ### 4.8 挂谷猜想 什么黄瓜苦瓜，又在说一些让人听不懂的话。 我们沿着角落上的小门进入商场。商场的内部金碧辉煌，但出入口却几乎都在角落上，显得十分内敛。 “这里。”理纱带我们到了地下层的一家餐厅，“这边套餐比较好。” “三维的针，除了平行和相交，还能异面，这会让三维的挂谷猜想比二维更难吗？”泰朵拉用两根筷子摆出异面直线。 “这就是这个问题比二维还要难得多的地方之一，而三维零测挂谷集的诡异之处远不止这一点。尤里刚刚说在电视上看到挂谷猜想，应该是讲菲尔兹奖的节目吧？数学家王虹最终通过证明这种集合维数为 $3$，从而获得了菲尔兹奖，这背后的洞察和努力是我们难以想象的。” “原来是这样。王虹肯定是很厉害的数学家，做了很多努力，才能解决这么难的猜想。但是‘洞察’又是什么意思喵？她能直接在脑海里想象这个集合吗？” “这个问题说起来比较复杂，”米尔嘉过了许久，缓缓开口，“她的导师曾经评价她做研究不求快但极为深入，有着独特的学术直觉和极强的韧性。这种‘深入’和‘直觉’并不是说对挂谷集合有几何直观，而是能够主动发明几何测度论和调和分析中的高阶工具，去研究一个极为抽象、复杂到诡异的数学对象，对于一般人甚至只能用转针来类比。” 服务员将第一道菜摆到桌上，虽然挂谷猜想很吸引人，但我也着实有些饿了，于是狼吞虎咽吃了起来。 “我们再不吃就被他一个人吃成零测集了。”理纱冷不丁地说。 “看得出来是真饿了。”米尔嘉笑着看我。我这才发现自己实在是丢了风度，脸颊在发烫。 不久之后，一道又一道美食摆上了餐桌。这次的套餐不像是某个单一国家的菜式，像是各种国家的拼盘，甚至一部分带有上次伽罗瓦节时法餐的影子。 “在杭州能吃这么多国家的美食，真是赚大了喵。” “王虹的经历是不是很独特来着？在三个国家完成了自己的学术培养全流程。” “确实是这样，但是国际化的环境对于数学家的成长是极为重要的，这一点实际上有普遍性。” “米尔嘉大人也是这样喵？” “双仓博士当时也差不多是这么跟我说的，多接触国际的东西没什么坏处。” “等下要不要去城市阳台转转？” ### 4.9 城市阳台 钱塘江两岸的灯光亮起来了。 从市民中心到钱塘江边的地块很有意思，左边的建筑像月亮，右边的建筑像太阳。我们在闪烁的灯光中穿过日月之间，来到江边。 灯光开始整齐地变换，模拟出钱塘江的波涛。 “刚刚展馆里的钱塘自古繁华，是说这条江存在很久了喵？” “应该是这样的吧，”我说，“如果钱塘江在这里这么久，那以前的人们要过去应该很难吧。” “难的东西是可以变容易的，”理纱说，“现在过去的通道至少有十几条。” “$n$ 维挂谷猜想和黎曼猜想，哪个会先被证明喵？” “这个问题很有意思，从最近的突破来看确实是挂谷猜想相关的工具更成熟，但是未来怎么样，谁也不知道。” “数学家即使不知道前路怎么样，甚至不知道这些问题未来会产生什么影响，也要继续前进，他们大概是最符合展馆里说的‘勇立潮头’的人吧。” 我们在江边驻足，一直到灯光停止变换为止。