Galois_Field_1048576 教你在 Nimber 中构造 1048576 元有限域

Galois_Field_1048576 · 2024-09-15 12:36:05 · 个人记录

本文的内容可能较为散乱, 但旨趣是介绍 \omega^{\omega^\omega} 以下的序数的 Nimber 运算 (添加若干有趣但对主线无帮助的的插曲). 我们会从组合博弈论起笔.

前置知识: 什么是集合的归纳法? 若 \forall x \in S, P(x) 可以推出 P(S), 且 P(\varnothing) (upd: 实际上, 由于虚真论断, 可以省去这一条件, 感谢 @MatrixGroup), 则 P 对于所有集合都成立. 证明是直观的. 这导出集合的递归定义 (设 P(S) 是 D(S) 不被定义的 S).

公平组合游戏

定义 1.1. 本文所论公平组合游戏, 是指 Zermelo-Fraenkel 公理下的集合. 一个公平组合游戏 S 的玩法为: 首先存储变量 t, 初值为 S. 两人轮流操作, 每次将 t 替换为 t 的一个元素, 得到 \varnothing 者胜 (i.e. 无法操作者负). 这个公平组合游戏不可能无限地玩下去, 这是正则公理的内容.

命题 1.2. 若将公平组合游戏 S 有先手必胜策略 (或简作先手必胜) 记作 W(S), 则 W 由下列递归约束式确定:

证明. 抽丝剥茧即可发现这就是我们熟悉的博弈 dp 定义式.

例 1.3, 在 Zermelo-Fraenkel 公理下, 我们经常使用空集套空集的方法来表示自然数: 回忆任意自然数是从 0 往后数 (行话为后继) 若干次的结果. 这样 0 = \varnothing, \mathrm{succ}(n) = n \cup \{n\}, 换句话说, 0 = \varnothing, 1 = \{0\}, 2 = \{0, 1\}, \dots. 因此, 任意自然数可以作为公平组合游戏, 且 P(n) \iff n \ne 0.

定义 1.4. 对于两个公平组合游戏 S, T, 递归地定义它们的和为 S \boxplus T 为 \{x \boxplus T : x \in S\} \cup \{S \boxplus y : y \in T\}. 换句话说, 将 S, T 两游戏并置, 每人每次操作只能操作 S, T 中的一个.

例 1.5 (Nim 游戏). Nim 游戏是形如 k_1 \boxplus k_2 \boxplus \dots \boxplus k_n 的公平组合游戏戏. 熟知的结论告诉我们

定义 1.6 (游戏等价). 称公平组合游戏 G, G' 等价, 记作 G \simeq G', 若 W(G \boxplus H) \iff W(G' \boxplus H).

命题 1.7. x \boxplus x \simeq 0.

证明: 对于 x \boxplus x \boxplus G, 如果对手动前两个中的任意一个, 就用模仿策略使另一个也跟进. 此论证对双方都成立.

命题 1.8. 设 G, G' 是公平组合游戏, f : G \to G' 是双射, 满足 x \simeq f(x), 则 G \simeq G'.

证明. 设 H 是公平组合游戏, 且 \neg W(G \boxplus H), 将证 \neg W(G' \boxplus H). 对 H 施归纳法. 此为:

前一项已然化为 \forall x \in H, W(x \boxplus H), 而后一项可以利用归纳假设进行转化. 因此我们成功得到 \neg W(G' \boxplus H). 注意到论证自对偶, 所以可以证明另一个方向, 所以 W(G \boxplus H) \iff W(G' \boxplus H), 为 G \simeq G' 之所需.

命题 1.9. G \simeq G' \implies G \boxplus H \simeq G' \boxplus H.

证明. 为了证 G \boxplus H \simeq G' \boxplus H, 则须证 W(G \boxplus H \boxplus H') \iff W(G' \boxplus H \boxplus H'), 结合律, 得证.

Sprague–Grundy 定理

OIer 们熟悉的游戏是有限的, 具体来说, 是遗传有限的, 也即 S 是有限集, S 的元素是有限集, S 的元素的元素的元素是有限集, 等等. 这个概念通过 von Neumann 层垒谱系得以建立. 此略陈定义:

定义 2.1. 遗传有限集组成的集合 \mathcal F 定义为:

其中 \mathscr P 是幂集符号, 上标 n 表示迭代.

定理 2.2 (Sprague–Grundy 定理之重述版本). 对任意 \mathcal F 的元素 S, 都存在自然数 n, 使得 S \simeq n.

证明: 递归地定义 \mathcal F 中的 Grundy 数, 即 \mathrm{SG}(S) = \mathrm{mex} \{\mathrm{SG}(x) : x \in S\}. 将归纳地证明 S \simeq \mathrm{SG}(S). 不难发现只需证 S \boxplus \mathrm{SG}(S) \simeq 0, 而 G \simeq 0 直接等价于 \neg W(G). 这样我们可以确定一个后手必胜的策略: 若先手动 S 到 x \in S, 分类讨论: x < \mathrm{SG}(S) 时动 \mathrm{SG}(S) 的 Nim 堆, 将这堆石子变为 x 个, x > \mathrm{SG}(S) 时取 y \in x 使得 \mathrm{SG}(y) = \mathrm{SG}(x). 若先手动 Nim 堆则直接取 x \in S 使得 \mathrm{SG}(x) = Nim 堆中的石子数. 这个策略显然使得先手必败.

定理 2.3 (Sprague–Grundy 定理). 设公平组合游戏 G_1, \dots, G_n \in \mathcal F, 则 W(G_1 \boxplus G_2 \boxplus \dots \boxplus G_n) 当且仅当这些公平组合游戏的 Grundy 数的异或和非 0.

证明: 无非上一个定理和 Nim 熟知结论的直接推论.

例 2.4. 既然我们用空集套空集定义了自然数, 我们的自然数集就可以写成:

它是一个公平组合游戏, 我们记作 \omega. \omega 不属于 \mathcal F, 但是属于 \mathscr P(\mathcal F). 这是无穷堆的 Nim 游戏, 带领着我们走向超限.

插曲: Fano 平面

定义 A.1. 线性空间 V 上的 射影空间为 V 的所有一维子空间组成的集合, 记作 \mathbb P(V), 其维数定义为 \dim V - 1. 对于域 \mathbb F 定义 \mathbb P^n(\mathbb F) = \mathbb P(\mathbb F^{n+1}).

定义 A.2. Fano 平面是 \mathbb P^2(\mathbb F_2), 是最小的射影平面.

定义 A.3. 对于 \mathbb P(V), 其射影子空间定义为 \mathbb P(U), 其中 U 是 V 的子空间. 射影空间 \mathbb P(V) 中的点, 线, 面分别定义为其 0, 1, 2 维子空间.

命题 A.4 (对偶原理). 设 n = \dim V, 则我们有自然同构 \mathbb P(V) \to \mathbb P(V^*), 其中 V^* 为 V \to \mathbb F 的所有线性映射组成的线性空间.

证明: 取法为 \mathbb P(U) (U 是 V 的子空间) 变为 \mathbb P(U^\perp), 其中 U^\perp = \{\varphi \in V^* : \forall u \in U, \varphi(u) = 0\}.

注记 A.5. 此命题在平面几何中诱导 Menelaus-Ceva 对偶性与 Pascal-Brianchon 对偶性.

命题 A.6. 下面是 Fano 平面的一个图示:

其中每个圆圈节点是射影平面中的点, 中间的圆和一条线段都是射影直线, 而射影直线上的三个点 u, v, w 满足 u \oplus v \oplus w = 0.

证明. 直接验证.

此图连带 (0, n, n) 完全编码了 Nim 游戏中先手必败的状态, 虽然这是显然的, 但是此图更有大用:

如果我们对这个图对称地定向, 则我们惊奇地发现, 考虑八元数代数 \mathbb O = \mathrm{span}\{1. \bold e_1, \dots, \bold e_7\}, 若在此平面中有 i \to j \to k, 则 \bold e_i \bold e_j = \bold e_k. 如果我们能画出更高维的 \mathbb P^n(\mathbb F_2). 则我们可以发现这完美地对应于 Cayley-Dickson 构造.

走向超限

本次 NOI 联合省选的最后一题是最长待机, 这是介绍序数的好机会.

定义 3.1. 我们用 a + b 表示程序的反向连接 (先 b 后 a, 因为将来的序数加法是这个顺序, 我们只好遵循数学传统), 1 表示待机一秒, N 表示输入一个数, 例如程序 N + 1 表示先待机一秒, 再输入一个数, 待机这么多秒 (N = 1 \cdot N).

定义 3.2. 设小 \omega 持有程序 A, 小 \aleph 持有程序 B, 若这个游戏使小 \omega 必胜, 则记 A > B; 若使小 \aleph 必胜, 则记 A < B; 这个游戏是公平的, 则记 A = B.

注意, 这不是公平组合游戏, 所以我们刚才探讨的组合博弈论不能贸然替换在这上面.

命题 3.3. 1 + N = N < N + 1.

证明. 对于断言 1 + N = N, 两者同时输入数据 (回忆加法是反向拼接), 所以胜负未定, 是公平的; 对于断言 N < N + 1, 当一方输入 n 时对方输入 n + 10^{100}, 显然取得必胜.

定义 3.4. A \cdot B 是将 B 中的所有待机一秒换为 A 的结果.

命题 3.5. 2 \cdot N = N < N \cdot 2.

证明. 类似于 命题 3.3, 故略去.

因此, 我们发现, Sleep++ 程序的运算于通常的运算不一样, 它是一个名为序数运算的东西. 如果我们将最长待机与 Nim 进行缝合, 我们会得到一个很有趣的东西:

定义 3.6. 设 F 是一个 Sleep++ 程序. 我们递归地定义一个公平组合游戏 \mathrm{Nim}(F):

• 如果 F 需要控制台立即输入一个数 n, 若输入数 n 得到的剩余部分程序为 F_n, 则 \mathrm{Nim}(F) = \bigcup_{n \in \mathbb N} \mathrm{Nim}(F_n).

例 3.7. 回看例 2.4. 则这个自然数游戏 \mathbb N 无非是 \mathrm{Nim}(N).

定理 3.8 A = B \iff \mathrm{Nim}(A) \simeq \mathrm{Nim}(B).

证明: 不难发现 A 与 B 对峙的最长待机游戏策略和 \mathrm{Nim}(A) \boxplus \mathrm{Nim}(B) 作为公平组合游戏的游戏策略一一对应.

更大的序数

我们可以尝试构造更大的序数 (目前还可以称为最长待机程序, 但是不久后我们就会超过题目中规定的 Sleep++ 的极限, 不妨想象一个 (Sleep++)++).

定义 4.1. 对于自然数 n, A^n 定义为 \underset n{\underbrace{A \ldots A}}. 我们自然地可以定义 A^N 等物, 但仍给出严谨的定义: A^B 的程序流程为:

• 一开始, T = 1.
• 然后将 B 的每一个 1 (待机一秒) 变为 T \gets T \cdot A.
• 运行一次 B, 得到一个最终的 T.
• 运行这个最终的 T.

命题 4.2. 2^N = N < N^N.

证明: 与命题 3.3/3.5 类似, 略去.

本文主要研究的序数是在 N^{N^N} 以下的, 然而无妨给出 \varepsilon_0 的定义:

定义 4.3. \varepsilon_0 = F^N(1), F(x) = N^x, 上标表示迭代.

定义 4.4 (揭开伪装). 后文中, \omega 指 N, 最长待机程序将被称为序数.

表示序的数

定义 5.1 (最小值与最大值). 假设集合 X 中每两个元素都可以比较大小, 例如 \mathbb N. 设 Y 是 X 的子集, 则 Y 的最小值是指集合 Y 中的一个元素, 该元素小于或等于集合中的所有元素. 类似地, 可以定义最大值. 注意, 最小最大值均应当属于 Y.

例 5.2. \mathbb N 的最小值为 0, 没有最大值.

定义 5.3 (上界与下界). 假设集合 X 中每两个元素都可以比较大小, 例如 \mathbb N. 设 Y 是 X 的子集, 则 Y 的下界是指集合 \boldsymbol X 中的一个元素, 该元素小于或等于集合中的所有元素. 类似地, 可以定义上界. 注意, 上界与下界可以不属于 Y.

例 5.4. 考虑集合 Y = \{q \in \mathbb Q : q^2 < 2\} \subseteq X = \mathbb R. 它没有最小值, 其所有下界组成的集合为 Y_- = \{r \mid r \le -\sqrt2\}, 上界组成的集合为 Y_+ = \{r \mid r \ge \sqrt2\}. 注意, Y_- 有最小值 -\sqrt 2, Y_+ 有最大值 \sqrt 2. 我们将 Y_+ 的最小值称为上确界, 记作 \sup Y, Y_- 的最大值称为下确界, 记作 \inf Y.

定理 5.5 (序数是一个良序集). 设 S 是一个集合, 其每一个元素 \alpha \in S 都是序数. 则 S 存在最小值.

证明. 由于我们目前还没有对序数下一个严格的定义, 这个证明只好挪到插曲中去讲. 插曲是可以略过的.

插曲: von Neumann 序数构造

下文可能需要更加深刻的对「集合套集合」的认识, 请酌情阅读.

公理 B.1 (正则公理). 不存在 \in 关系的无穷降链, 也就是说, 不存在集合 x_0, x_1, x_2, \dots, 使得

事实上这是集合归纳法的等价形式. 因此, 我们在前面的论证中已经使用了正则公理不止一次了.

公理 B.1' (正则公理). Zermelo-Fraenkel 公理除了替换公理模式 (分离公理模式可以由空集公理和替换公理模式推出) 以外全部都使用一阶语言叙述. 一阶语言中不能叙述无穷个集合或 \mathbb N \to \mathbf V (\mathbf V 指代所有集合构成的类) 的概念, 所以正则公理的实际叙述是这样的: 对于任意的集合 S, 总存在 x, 使得 x \cap S 是空集.

证明. 在这里证明两条公理的等价性.

• (\neg\mathrm{B.1} \implies \neg\mathrm{B.1'}): 对于 \neg\mathrm{B.1} 断言的无穷降链 x_0 \ni x_1 \ni x_2 \ni \cdots,

  考虑集合 S = \{x_i \mid i \in \mathbb N\}, 则对于其元素 x_i, 有 x_i \cap S = \{x_j \mid j > i\} \ne \varnothing. 因此 \mathrm{B.1'} 不成立.

• (\neg\mathrm{B.1'} \implies \neg\mathrm{B.1}) 对于满足 \forall x \in S, x \cap S \ne \varnothing 的集合 S, 则如下的递归构造形成一个降链.

定义 B.2 (传递集). 称集合 S 传递, 若 S \subseteq \mathscr P(S), 其中 \mathscr P(S) 表示 S 的所有子集组成的集合.

命题 B.3. 回忆我们对于最长待机程序 P 规定的 Nim 游戏 \mathrm{Nim}(P), 它是一个传递集.

证明.

• 若 S = \mathrm{Nim}(X) 是传递集, 则 S \sqcup \{S\} = \mathrm{Nim}(X + 1) 满足 S \subseteq \mathscr P(S) \subseteq \mathscr P(S \sqcup \{S\}), \{S\} \subseteq \mathscr P(S) \subseteq \mathscr P(S \sqcup \{S\}), 即 S \sqcup \{S\} \subseteq \mathscr P(S \sqcup \{S\});
• 若 S_n = \mathrm{Nim}(F_n), 则 S = \bigcup_{n \in \mathbb N} S_n = \mathrm{Nim}(F_\omega)

  满足 S_k \subseteq \mathscr P(S_k) \subseteq \mathscr P(S), 也就是说 S \subseteq \mathscr P(S).

定义 B.4 (序数). 称 \alpha 是序数, 若 \alpha 是传递集的同时还满足条件: 对相异元素 x, y \in \alpha, 一定有 x \in y 和 y \in x 中的一个成立.

命题 B.5. 设 x, y, z \in \alpha, x \in y, y \in z, 则 x \in z.

证明. 根据序数的定义, 如果 x \in z 不成立, 则 z \in x. 这样形成了 \in 关系的无穷降链

矛盾.

命题 B.6. 对于所有的最长待机程序 X, \mathrm{Nim}(X) 是序数.

证明. 类似命题 B.4.

命题 B.7. 序数的元素是序数.

证明. 若 \beta \in \alpha, \alpha 是序数, 可知 \beta \subsetneq \alpha, 因此, 对于相异的 x, y \in \beta, 有 x \in y 或 y \in x 成立. 而传递性质来源于: 设 x \in \beta, 则 x \in \beta \in \alpha \implies x \in \alpha, 这样 x \subseteq \alpha, 只需证这个 x 的元素都属于 \beta 即可. 其证明来自 p \in x \in \beta \implies p \in \beta.

命题 B.8. 对于 \alpha, \beta 为序数, \alpha \subsetneq \beta \implies \alpha \in \beta.

证明. 考虑 \beta \setminus \alpha, 它有一个最小值 n (否则每一个元素 \gamma 都有比它更小的元素 \gamma', 导致降链 \gamma \ni \gamma' \ni \gamma'' \ni \cdots), 则 n \subseteq \alpha, 而对于 x \in \alpha \subsetneq \beta, 显然 x \ne n, 而 n \notin x (因为 n \notin \alpha), 由于 x, n 都是序数 \beta 中的元素, 所以 x \in n. 现在, 对于任意的 x \in \alpha 都有 x \in n, 所以 \alpha \subseteq n.

命题 B.9. 对于序数 \alpha, \beta, \alpha \subseteq \beta 与 \beta \subseteq \alpha 必居其一.

证明. 观察到 \gamma = \alpha \cap \beta 是序数, 而 \gamma \ne \alpha 与 \gamma \ne \beta 的话就会发生 \gamma \in \alpha, \gamma \in \beta \implies \gamma \in \gamma, 与正则公理矛盾. 因此 \gamma = \alpha 或 \gamma = \beta, 可以导出结论.

由上可见, 所有的序数可以通过 \in 关系比较大小. 现在我们完成定理 5.5 的证明.

证明 (定理 5.5). 考虑序数

这样 \alpha 是一个序数 (简单验证), 且 \alpha \in S (否则 \alpha \in \alpha). 这样有对于所有的 \beta \in S, \alpha \subseteq \beta, 当 \alpha \ne \beta 时相当于 \alpha\in \beta.

超现实数

Nimber, 可以翻译为无偏数或 Nim 数, 是本文的主角. 在此之前, 我们简要地介绍一下这个概念是如何诞生的.

Conway, 在其一周写成的巨著 On Numbers And Games 中, 剖析了一般的非公平组合游戏: 他认为, 一个游戏是一个二元组 (L \mid R), 其中 L, R 都是一些游戏组成的集合. 我们称游戏 (L \mid R) 遗传地满足性质 P, 若 (L \mid R) 本身满足性质 P, 且 L 的每个元素 x 和 R 的每个元素 x 都满足性质 P. 这样, 无偏数, 或公平组合游戏, 是遗传地满足 L = R 的游戏.

一般的游戏很难考虑, 但 Conway 注意到类似这样的游戏:

定义 6.1 (扭曲分数游戏). 所谓扭曲分数游戏, 是指如下的非公平组合游戏: 游戏从 \dfrac pq 出发, Alice 先手, 后轮流进行操作. 每次对于分数 \dfrac pq, Alice 或 Bob 用新的分数 \dfrac ab 替换之, 但 Alice 要求 \dfrac ab < \dfrac pq, Bob 要求 \dfrac ab > \dfrac pq, 且二者都要求 b < q. 若 q = 1, 游戏结束, 则若 p 是正数, 则 Alice 胜, 否则 Bob 胜. 我们记这个游戏为 R\left(\dfrac pq\right).

例 6.2. 设 \dfrac pq = \dfrac 25, 则 Alice 的可能操作有 \dfrac 13, \dfrac 14, \dfrac {-1}2, -2^{20}, \dots, 而 Bob 的可能操作为 \dfrac 12, \dfrac 23, \dfrac 34, 1, 2^{20}, \dots.

命题 6.3. 扭曲分数游戏中, 最优的策略如下: 从 \lambda = \dfrac pq 出发, 在 Stein–Brocot 树中定位之, 有 \lambda = \mu_0 \oplus \mu_1, 则 Alice 永远会把 \lambda 替换为 \mu_0, Bob 永远会把 \lambda 替换为 \mu_1.

证明. 注意到 \lambda 越大, 对 Alice 越有利, 与此同时, 在所有分母 \le q 的分数中, Stein–Brocot 树的中序遍历构成了所有分数的升序排列. 由于 \lambda 是叶子结点, 所以在 \lambda 附近, 中序遍历形如 \mu_0, \lambda, \mu_1. 因此 Alice 永远会优先选择 \mu_0, 而 Bob 永远会优先选择 \mu_1.

例 6.4. 类似地定义非公平组合游戏的游戏和. 游戏和仍然有交换律和结合律成立. 但我们有等式

成立. 因此, 游戏和在 R-数上并不是自然的. 我们需要一个 R-数到 \mathbb R 的同态, 它会满足:

定义 6.5. 我们如下递归地定义 Minkwoski 问号函数 ?(\lambda): 在 Stein–Brocot 树中定位 \lambda, 有 \lambda = \mu_0 \oplus \mu_1, 则

并且

命题 6.6. 我们所希望的,

成立.

证明. 这需要超现实数的更深入知识, 如果有兴趣, 可以参考 On Numbers And Games 或者 MatrixGroup 的超现实数入门系列 (1, 2, 3, 4).

因此, 实数似乎以一种自然的方式成为游戏: 无论是 ?(R(\lambda)) 还是其它, 都指向了这样一个结果:

定义 6.7. Conway 认为, 0 是最简单的实数, 1 和 -1 是次简单的, 然后是 2 和 -2, 3 和 -3; 第 \omega 简单的实数为 \dfrac n2, \omega + 1 简单的是 \dfrac n4, 依此类推. 而 \dfrac n3, \mathrm e, \sqrt 2 均被视为第 \omega 2 简单的实数. 这样, 实数 r 被 Alice 替换为比它简单且小于它的实数, 而 Bob 替换为比它简单且大于它的实数. 我们称这样的游戏为实数的自然游戏.

无论是扭曲分数游戏, 还是实数的自然游戏, 每个人进行操作后, 均会比原来的局势更劣. 因此, 如果一个人能够不操作, 会得到一定的优势. Conway 注意到了这一点, 得到了如下的定义:

定义 6.8. 一个超现实数是游戏 (L \mid R), 附带序结构: (P \mid Q) \le (A \mid B) 当且仅当对于 p \in P, b \in B, p \ge (A \mid B) 不成立, (P \mid Q) \ge b 不成立, 且超现实数遗传地满足 \forall l \in L, r \in R, l < r.

超现实数与无偏数的运算

超现实数,