Pearls [pearls]

Short, elegant, and enlightening proof that illustrate important principles or techniques.

Backlinks

Exegesis. Cauchy–Aczél 论证 [CN2A]

June 25, 2021
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$

Cauchy–Aczél 论证是次可加归纳的一个直接应用. 凭此能够同时证明 Cauchy 不等式、Titu 引理、Aczél 不等式和 Aczél 不等式 Engel 形式. 具体步骤如下.

在次可加归纳中取 $f(x, \ell) = \frac{x^2}{\ell}$, 于是 Titu 引理 $\iff$ Aczél 不等式 Engel 形式, 又因为 Cauchy 不等式等价于 Titu 引理, Aczél 不等式等价于 Aczél 不等式 Engel 形式. 于是只需证明 Cauchy 不等式中 $n=2$ 的情况, 现在做差

$$ (a_1^2 + a_2^2)(b_1^2 + b_2^2) - (a_1b_1 + a_2b_2)^2 \spaces= (a_1b_2 - a_2b_1)^2 $$

右侧非负, 从而证毕. 读者也应留意到, 尝试直接说明 Cauchy 不等式和 Aczél 不等式等价往往不容易看出, 而沿着下面的路径就要轻松的多.

$$ \begin{CD} \text{Cauchy} @>s>> \text{Titu} \\ @. @VV\text{次线性归纳}V \\ \text{Aczél} @<<s^{-1}< X_1 \end{CD} $$

此处 $X_1$ 即 Aczél 不等式 Engel 形式, $s$ 为 $(a_k, b_k) \mapsto (\frac{x_k}{\sqrt\ell_k},\sqrt\ell_k)$.

Exegesis. Hölder–Popoviciu 论证 [HP2E]

June 25, 2021
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$

类似 Cauchy–Aczél 论证, 也可以将次可加归纳应用于 Hölder 不等式和 Aczél–Popoviciu 不等式.

在次可加归纳中取 $f(x, \ell) = \frac{x^p}{\ell^{p-1}}$, 此时 $\eta_*: \sum_i x_i^p / \ell_i^{p-1} \ge (\sum_i x_i)^p / (\sum_i \ell_i)^{p-1}$ 即 Radon 不等式, $\varphi_*: (x - \sum_i x_i)^p / (\ell - \sum_i \ell_i)^{p-1} \ge x^p / \ell^{p-1} - \sum_i x_i^p / \ell_i^{p-1}$ 即 Aczél–Popoviciu 不等式 Engel 形式. 沿下图

$$ \begin{CD} \text{Hölder} @>s>> \text{Radon} \\ @. @VV\text{次线性归纳}V \\ A_2 @<<s^{-1}< X_2 \end{CD} $$

此处 $A_2$ 为 Aczél–Popoviciu 不等式, $X_2$ 为 Aczél–Popoviciu 不等式 Engel 形式, $s$ 为 $(a_k, b_k) \mapsto (\frac{x_k}{\sqrt[q]\ell_k}, \sqrt[q]\ell_k)$. 证明这四个命题等价于证明命题 $\eta$, 即

$$ (a_1^p + a_2^p)^{\frac{1}{p}}(b_1^q + b_2^q)^{\frac{1}{q}} \spaces\ge a_1b_1+a_2b_2 $$

以下证明是标准的, 可见于任何一本泛函分析课本. 记

$$ x_i = a_i /(a_1^p + a_2^p)^{\frac{1}{p}}, \quad y_i = b_i / (b_1^q + b_2^q)^{\frac{1}{q}}$$

则 $x_1^p + x_2^p = 1, y_1^q + y_2^q = 1$. 欲证明 $x_1y_1 + x_2y_2 \le 1$, 只要对 $(x_i, y_i)$ 使用 Young 不等式, 如此

$$ x_1y_1 + x_2y_2 \spaces\le \frac{x_1^p}{p} + \frac{y_1^q}{q} + \frac{x_2^p}{p} + \frac{y_2^q}{q} $$

由加法交换律和 $\frac{1}{p} + \frac{1}{q} = 1$, 右侧当然 $=1$.

Exegesis. Young 引理 [YL2A]

May 14, 2019
kokic
Pearls

Young 不等式有许多风格迥然的证明, 最常见的办法可能是使用定积分.

我们在此介绍一种充分利用对数线性化 $\log x \le x -1 $ 的方法, 即 Young 引理. 并展示 Young 不等式与其他常见不等式如何作为此结果的直接推论.

Lemma. Young 引理 [YL2B]

May 14, 2019
kokic

$\gdef\spaces#1{~ #1 ~}$

对数函数 $\log$ 的独特性质体现在 $\log a^b = b\log a$ 和 $\log a b = \log a + \log b$. 另一方面, 我们知道对于非负的 $X,Y$, 不等式 $X \le Y$ 等价于 $\log \frac XY \le 0$. 如果我们希望充分利用这三点, 那么就可以试着去考虑

$$ \log \frac{f_1^{p_1}f_2^{p_2}}{g^{p_1+p_2}} \spaces= p_1\log\frac{f_1}g \spaces+ p_2\log\frac{f_2}g $$

现在对右侧使用对数的线性化, 得到

$$ \begin{aligned} \log \frac{f_1^{p_1}f_2^{p_2}}{g^{p_1+p_2}} &\spaces\le p_1\Big(\frac{f_1}g-1\Big) \spaces+ p_2\Big(\frac{f_2}g-1\Big) \\ &\spaces= g^{-1}(p_1f_1+p_2f_2) - (p_1+p_2) \end{aligned} $$

我们当然希望 $\log\frac\Box\Box \le 0$. 这就是说, 如果有关于加法和乘法的条件

$$ p_1f_1+p_2f_2 \spaces\le (p_1+p_2)g $$

那么可以推出 $f_1^{p_1}f_2^{p_2} \le g^{p_1+p_2}$ 这样一个指数上的结果. 有时我们也写成

$$ p_1 \log f_1 + p_2 \log f_2 \spaces\le (p_1+p_2)\log g $$

用完全相同的步骤, 也可以证明任意多个 $p_i$ 和 $f_i$ 时的情况.

Corollary. Young 不等式 [YL3A]

May 14, 2019
kokic

$\gdef\spaces#1{~ #1 ~}$

我们在此处的条件中再添一笔 $p_1+p_2=1$, 然后替换 $(p_1,p_2)$ 为 $(\frac1p, \frac1q)$, 替换 $(f_1,f_2)$ 为 $(a,b)$, 这样就有

$$ (p_1f_1 + p_2f_2 \space =) \quad \frac ap + \frac bq \quad (= \space g) $$

立刻得出 $a^{\frac1p}b^{\frac1q} \le \frac ap + \frac bq$, 当且仅当 $a=b$ 取得等号.

Corollary. Bernoulli 不等式 [YL3B]

May 15, 2019
kokic

$\gdef\spaces#1{~ #1 ~}$

Bernoulli 不等式是说 $(1+x)^n \ge 1+nx$. 这里 $n \ge 1$, $x \ge -1$. 等价地, 我们来证明

$$ x^n + n-1 \spaces\ge nx, \qquad (n \ge 1, x \ge 0) $$

在 Young 引理的条件中令 $p_i = \frac1n$, $(f_i)_{1\le i \le n}=(x^n, 1, 1, \cdots)$, $g = (x^n + n-1)n^{-1}$, 这个时候以下条件显然成立

$$ \frac1n x^n + \underbrace{\frac1n + \frac1n + \cdots + \frac1n}_{n-1 ~ \text{times}} \spaces= \frac{x^n + n-1}n $$

于是可以得到 $(x^n)^{n^{-1}} \le (x^n + n-1)n^{-1}$. $\quad\Box$

Corollary. 加权算术平均–几何平均不等式 [YL3C]

May 15, 2019
kokic

$\gdef\spaces#1{~ #1 ~}$

我们要证的结果可以写成下面的样子

$$ \Big(\prod_{i \in S}z_i^{w_i}\Big)^{(\sum_{i \in S}w_{i})^{-1}} \spaces\le \Big(\sum_{i \in S}w_iz_i\Big) \Big(\sum_{i \in S}w_i\Big)^{-1} $$

实际上可以利用对数的线性化对这个定理给出一个直接的证明, 不过这并非本文的重点. 我们在此处更关心如何将这些表达式调整为适合使用此引理的形式. 先引入一些记号, 用 $\Sigma_w$ 表示 $\sum_{i \in S}w_{i}$, 用 $\omega_i$ 表示 $w_i\Sigma_w^{-1}$. 这样目标就变成了

$$ \prod_{i \in S}z_i^{\omega_i} \spaces\le \sum_{i \in S}\omega_iz_i $$

如果把这里的 $\omega_i$ 看作 $p_i$, $z_i$ 看作 $f_i$, $\sum_{i \in S}\omega_iz_i$ 看作 $g$. 那我们只要验证下面这件事

$$ \sum_{i \in S}\omega_iz_i \spaces\le \sum_{i \in S}\omega_iz_i $$

而这应该是很容易的. $\quad\Box$

代数数可数 [CAN0]

July 25, 2020
kokic
Pearls

$\gdef\Q{\mathbf{Q}}$ $\gdef\N{\mathbf{N}}$

代数数即 $\Q$-系数首一多项式的根, 容易看出这也是任意整系数多项式方程的根. 1874 年, Cantor 在文章 “Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen” 中运用多项式高度的概念证明了实代数数的可数性.

Exegesis. Cantor 的思路 [CAN1]

$\gdef\N{\mathbf{N}}$ $\gdef\C{\mathbf{C}}$

Cantor 的思路很大程度上可以视为一种数论策略. 他首先想的是对多项式 $P$ 定义一个恰当的高度概念 $H(P) \in \N$, 使得一旦我们固定了正整数 $h$, 则只会存在有限个多项式 $P$ 满足 $H(P) = h$, 且任意多项式都能被某个高度覆盖. 即用高度分类全体多项式的同时又控制了多项式的复杂程度. 随后, 代数基本定理保证给定 $n$ 次多项式, 其根在 $\C$ 上至多只有 $n$ 个, 全体代数数便可以写为可数个有限集的并, 如此证得.

Definition. 多项式高度 [CAN2]

$\gdef\spaces#1{~ #1 ~}$ $\gdef\N{\mathbf{N}}$

遵循着这种思路, Cantor 给出的高度定义为:

$$ H(P) \spaces= \deg P - 1 + \sum_{0 \le i \le n} |a_i| $$

反过来, 任给一个整系数多项式 $P$, 我们都能计算他的 $H(P) \in \N$.

Lemma. 定高多项式集有限 [CAN3]

$\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$

固定 $h \in \N$, 则集合 $P_h = \{ P \in \Z[x] : H(P) = h \}$ 有限. 为了证明这件事, 注意到此时多项式的次数最多是 $h$, 因为至少有一个非零整系数 $a_i$ 使得 $|a_i| \ge 1$. 另一方面, 每个 $a_i$ 也满足 $|a_i| \le h$, 因此一个多项式的所有信息都被正整数 $h$ 控制, 故 $P_h$ 有限.

Lemma. 定高多项式根集有限 [CAN4]

$\gdef\C{\mathbf{C}}$

固定 $h \in \N$, 集合 $R_h = \{ z \in \C : P(z) = 0, P \in P_h \}$ 有限. 对 $P \in P_h$ 处每一个固定的 $P$ 使用代数基本定理, 便可得到此时的 $z$ 也只有有限多个.

Theorem. 代数数只有可数多个 [CAN5]

$\gdef\spaces#1{~ #1 ~}$ $\gdef\A{\mathbb{A}}$ $\gdef\N{\mathbf{N}}$

根据代数数域 $\A$ 的定义之一, 我们知道 $\A = \bigcup_{h \in \N} R_h$ 所以 $|\A| = |\N|$, 即可数.

Example. 循环幂和不等式 [CPSI]

June 20, 2019
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$

设 $0 < x_1, x_2, \cdots, x_n < 1$. 试证

$$ x_1^{x_2} + x_2^{x_3} + \cdots + x_n^{x_1} > 1 $$

利用 Bernoulli 不等式, $(1+\frac{x}{y})^{\frac{1}{x}} \geqslant 1+\frac{1}{y} > \frac{1}{y}$ 得到 $1+\frac{x}{y} > \frac{1}{y^x}$, 即 $y^x > \frac{1}{1+\frac{x}{y}}$.

$$ \begin{aligned} x_1^{x_2} + x_2^{x_3} + \cdots + x_n^{x_1} &\spaces> \sum_{1 \leqslant i \leqslant n} \frac{1}{1+\frac{x_1}{x_{i+1}}} \\ &\spaces> \sum_{1 \leqslant i \leqslant n} \frac{x_{i+1}}{x_1 + x_2 + \cdots + x_n} \\ &\spaces= 1 \end{aligned} $$

此处 $i+1$ 按照 $\Z/n\Z$ 处理.

生成函数系数 [GF2A]

August 15, 2021
kokic
Pearls

$\gdef\Z{\mathbf{Z}}$

设 $\frac1{(1-q)^3} = \sum_{u \ge 0} a_u q^u$, 求 $a_n$.

不难发现, 此处 $a_n$ 同时也是 $x_1+x_2+x_3 = n$ 于 $\Z_{\ge 0}$ 上解的个数. 在 $(1-q)^{-n}$ 的系数中取 $n = 3$, 得到 $a_{u} = \frac{1}{2}(u + 2)(u + 1)$.

Lemma. $\footnotesize (1-q)^{-m}$ 的系数 [GF3A]

August 15, 2021
kokic
Pearls

$\gdef\d{\operatorname{d}}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$

我们来证明

$$ \frac{1}{(1 - q)^{n}} \spaces= \sum_{u \geq 0}\binom{n + u - 1}{u}q^{u} $$

对于 $(1-q)^{-m}$ 这类特殊的有理函数, 注意到 $((1-q)^{-1})' = (1 - q)^{- 2}$. 归纳地, 可以得到

$$ \frac{\d^{n}}{\d q^{n}}(1 - q)^{- 1} \spaces= \frac{n!}{(1 - q)^{n + 1}} \quads\Longrightarrow \frac{1}{(1 - q)^{n}} \spaces= \frac{1}{(n - 1)!} \cdot \frac{\d^{n - 1}}{dq^{n - 1}}(1 - q)^{- 1} $$

另一方面, 我们知道几何级数满足 $\frac{1}{1 - q} = 1 + q + q^2 + \cdots = \sum_{u \geq 0}q^{u}$, 代入可得

$$ \frac{1}{(1 - q)^{n}} \spaces= \frac{1}{(n - 1)!} \cdot \frac{\d^{n - 1}}{\d q^{n - 1}}\sum_{u \geq 0}q^{u} $$

现在我们再使用下面的观察

$$ \frac{\d^n}{\d x^n} x^m \spaces= \begin{cases} x^{m-n} \prod_{0 \le k \le n-1}(m-k) & n \le m \\ 0 & \text{otherwise} \end{cases} $$

就可以算出 $\frac{\d^{n - 1}}{\d q^{n - 1}}\sum_{u \geq 0}q^{u}$ 这一部分

$$ \begin{aligned} \frac{1}{(1 - q)^{n}} &\spaces= \frac{1}{(n - 1)!} \cdot \sum_{u \geq n - 1}q^{u - (n - 1)}\prod_{0 \leq k \leq n - 2}(u - k) \\ &\spaces= \frac{1}{(n - 1)!} \cdot \sum_{u \geq 0}q^{u}\prod_{0 \leq k \leq n - 2}(u + n - k - 1) \\ &\spaces= \frac{1}{(n - 1)!} \cdot \sum_{u \geq 0}q^{u}(u + n - 1)(u + n - 2) \spaces\cdots (u + 1) \end{aligned} $$

$q^{u}$ 的系数从 $u = 0$ 开始, 则系数可再一次简化为组合数

于是明所欲证.

辗转相除法步数估计 [euclid-step]

June 10, 2021
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$

1844 年, 49 岁的法国数学家 Gabriel Lamé 发现, 设 $a,b$ 两数辗转相除至余数为零所用步数为 $n$, 则

$$ n \spaces\le 1 + \log_\phi \min(a,b) $$

其中 $\phi = \frac{1+\sqrt5}{2}$ 为黄金分割. 当然, 这也给出用递归实现 $\gcd$ 函数的时间复杂度. 如今认为, 此结果标志着计算复杂度理论的开始.

我们首先来证明 $n\le\log_\phi\sqrt{5}\min(a,b)$. 不妨设 $a\gt b$, 于是有 $a=qb+r_1,r_{k-1}=q_kr_k+r_{k+1}$, 其中 $1\le k\le n-1$, 显然一定有 $r_n=0$. 还注意 $r_k$ 依次递减且有 $r_k-r_{k+1}\ge1$, 则 $r_{k-1}=q_kr_k+r_{k+1}\ge r_k+r_{k+1}$. 将下标取反 $(s_k=r_{n-k})$ 即 $s_{k+1}\ge s_k+s_{k-1}$. 故考虑 Fibonacci 数列 $F_n$, 知 $s_k\ge F_k$, 即 $b\ge F_n$, 又 $F_n \sim \frac{\phi^n}{\sqrt5}$, 证毕.

现在, 注意到此估计与待证估计之差为

$$ \begin{aligned} \log_{\phi}\sqrt5-1 \ &\spaces= \dfrac{\log\sqrt5}{\log\dfrac{1+\sqrt5}{2}}-1 \\ &\spaces= \dfrac{1}{2}\cdot\dfrac{\log5}{\log(1+\sqrt5)-\log2}-1\\ &\spaces\lt 2\cdot\dfrac{\log5}{\log5}-1 \\ &\spaces= 1 \end{aligned} $$

其中最后一个不等号是因为, 根据基本不等式 $1+\sqrt5 \ge 2\cdot5^{1/4}$, 于是

$$ \log(1+\sqrt5) - \log2 \spaces\gt\log(2\cdot5^{1/4})-\log2 \spaces=\tfrac{1}{4}\log5 $$

故 $n \le \log_{\phi}b+1$.

极坐标出现前人们怎样计算高斯积分 [gaussian-integral]

November 2, 2024
kokic
Pearls

这一证明最早似乎来自 Michael Rozman. 除此之外 MSE 上也有极类似的回答, 见此处.

M. Rozman, Evaluate Gaussian integral using differentiation under the integral sign, Course notes for Physics 2400 (UConn), Spring 2016.

$\gdef\R{\mathbf{R}}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\d{\operatorname{d}}$

核心技巧来自一个函数 $F(t)$ 的构造. 对 $t \in \R$ 定义如下函数

$$ F(t) \spaces= \int_0^\infty \frac{e^{-t^2(1+x^2)}}{1+x^2} \d x $$

容易验证 $F(t)$ 满足 $F(0)=\frac{\pi}{2}$, $F(\infty) = 0$, 以及最关键的

$$ F'(t) \spaces= \int_0^\infty -2te^{-t^2(1+x^2)} \d x \spaces= -2te^{-t^2} \int_0^\infty e^{-(tx)^2} \d x $$

记高斯积分为 $I$. 这就有 $F'(t) = -2Ie^{-t^2}$, 此时再求 $F'(t)$ 于 $[0, \infty)$, 上的积分, 就能得到

$$ F(\infty)- F(0) \spaces= -2I \int_0^\infty e^{-t^2} \d t \spaces= -2I^2 $$

于是这给出 $I = \frac{\sqrt\pi}2$.

Theorem. 删除–收缩公式 [deletion-contraction]

July 21, 2024
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\without{\setminus}$

对于简单图 $G$, 其色多项式 $\pi(G)$ 成立如下关系

$$ \pi(G) \spaces= \pi(G \without e) \spaces- \pi(G / e), \quad \forall ~ e \in \text{Edge}(G) $$

Proof. [deletion-contraction-pf]

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\without{\setminus}$

$\gdef\str#1{{\footnotesize #1}}$ $\gdef\sstr#1{~{\footnotesize #1}~}$

假定边 $e$ 的两个端点分别为 $A,B$, 不难发现

$$ \begin{aligned} \pi(G \without e) &\spaces= \pi(G \without e \sstr{中} A,B ~\str{同色的部分}) ~ + ~ \pi(G \without e \sstr{中} A,B ~\str{异色的部分}) \\ &\spaces= \pi(G / e) ~ + ~ \pi(G) \end{aligned} $$

此处, $G \without e$ 是将 $G$ 的边 $e$ 删去, $G/e$ 是将 $e$ 两侧的顶点合并为一个.

这个结果可等价地叙述成连接的版本, 可称为 “连接–收缩公式”. 对于简单图 $G = (V, E)$

$$ \pi(G) \spaces= \pi(G + uv) \spaces+ \pi(G / uv), \quad \forall ~ uv \notin E $$

这里, $G+e$ 是指将 $e$ 两侧的顶点连接, $u v$ 是指顶点 $u, v$ 连接得到的边.

回声 [index]

本站使用 Kodama 构建, 源文件位于此处. 另有专栏证明珠玑.

千高原 [mille-plateaux]

平面曲线的有理点 [rational-points]

December 26, 2024
kokic

$\gdef\ul#1{\underline{#1}}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$ $\gdef\R{\mathbf{R}}$ $\gdef\Q{\mathbf{Q}}$

Exegesis. Canterbury 物语 [canterbury]

December 26, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

此问题来自一本名为 The Canterbury Puzzles 的书, 是其中的 “The Puzzle of the Doctor of Physic” 的重述. 本文希望以此问题为起点, 介绍历史上若干算术问题的几何方法.

Problem. 古代物理学博士问题 [canterbury-2A]

December 26, 2024
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$

有两个正方体, 一个边长为 $1$, 另一个边长为 $2$. 请找到另外两个边长为有理数的正方体使它们的体积总和相同. 换言之, 求下述方程的一组 (正) 有理解.

$$ x^3 + y^3 \spaces= 9 \quad \color{gray}{(= ~ 1^3+2^3)} $$

Solution. [canterbury-2B]

December 26, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

我们先画出 $x^3 + y^3 = 9$. 然后由已知的 $P=(1,2)$ 出发做切线得到 $2P$, $4P$, $8P$. 这种几乎全凭借运气的操作是 Fermat 及 Viète 研究此类问题的方式.

如图, 随后注意到 $8P$ 恰好位于 $x > 0,y > 0$ 的区域, 现在写出其坐标.

$$ 8P \spaces= \left(\frac{1243617733990094836481}{609623835676137297449}, \frac{487267171714352336560}{609623835676137297449}\right) $$

Lemma. 切线与交点 [canterbury-3A]

December 27, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

对 $\Gamma: x^3+y^3=c$ 求导得 $3x^2 + 3y^2y^\prime = 0$, 故 $y^\prime = -\frac{x^2}{y^2}$. 任取 $\Gamma$ 上一个点 $P(x_\Box, y_\Box)$. 由此得到该点处的切线 $\ell_P: y - y_\Box = -\frac{x_\Box^2}{y_\Box^2}(x - x_\Box)$. 代入 $\Gamma$, 即

$$ x^3 + (y_\Box-\frac{x_\Box^2}{y_\Box^2}(x - x_\Box))^3 \spaces= x_\Box^3 + y_\Box^3 $$

注意这里有一个 $(\frac1{y_\Box^2})^3$, 我们将其提出其即可得到

$$ y_\Box^{-6}(x-x_\Box)^2(y_\Box^6x - x_\Box^6x + x_\Box^7 + 3x_\Box^4y_\Box^3+2x_\Box y_\Box^6) \spaces= 0 $$

随后解这个关于 $x,y$ 的方程. 注意这里 $(x-x_\Box)^2$ 当然来自于我们做的 $P$ 点切线, 也就是重根 $x_\Box$. $\Gamma$ 是一条三次曲线, 与直线的交点方程最多三个解, 因此最后一项关于 $x$ 是线性的, 故只需要解一个线性方程, 立刻得到

$$ 2P: (x_\Box, y_\Box) \quad \leadsto \quad \left(\frac{x_\Box(x_\Box^3 + 2y_\Box^3)}{x_\Box^3 - y_\Box^3}, \frac{y_\Box(y_\Box^3 + 2x_\Box^3)}{y_\Box^3 - x_\Box^3}\right) $$

反复利用映射 $2P$ 即可得到前文的 $8P$. 当然, 这也给出如下经典的恒等式. 最早亦可追溯到 Viète 和 Bacht.

$$ x^3 + y^3 \eqq \left(\frac{x(x^3 + 2y^3)}{x^3 - y^3}\right)^3 + \left(\frac{y(y^3 + 2x^3)}{y^3 - x^3}\right)^3 $$

Exegesis. Fermat 提升法 [fermat-ascent]

December 26, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\Q{\mathbf{Q}}$

考虑一般的三次曲线 $\Gamma$. 已知一有理点时, 我们可以过此点做切线. 已知两有理点 $P, Q$ 时, 连接两点得到直线 $\ell$ 交曲线 $\Gamma$ 于另一点 $S$, 这个时候 $\ell$ 和 $\Gamma$ 的交点方程仍然是一个三次方程. 根与系数的关系给出

$$ x(P) \spaces + x(Q) \spaces + x(S) \spaces \in \Q $$

这使得 $x(S) \in \Q$. 我们也可以将这个想法直接应用到二次曲线上.

Exegesis. 圆的参数化 [circular-parameterization]

December 28, 2024
kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\Q{\mathbf{Q}}$ $\gdef\R{\mathbf{R}}$

我们对于 $\R$ 上的单位圆周曲线 $C(\R):x^2+y^2=1$ 和它关于角度 $\theta$ 的参数化 $\theta \mapsto (\cos\theta, \sin\theta)$ 是不陌生的. 通过计算这类统称为三角函数或者圆函数的映射, 很容易就能发现圆上的一些不同寻常的点

$$ (\tfrac1{\sqrt2}, \tfrac1{\sqrt2}), \quad (\tfrac{1+\sqrt5}4, \sqrt{\tfrac58 - \tfrac{\sqrt5}8}), \quad (\tfrac{\sqrt3}2, \tfrac12) $$

但是如果我们希望找到 $C(\Q)$ 上的点, 这个参数化就没有那么有用了. 考虑 $C(\Q):x^2+y^2=r^2$, 我们从点 $P(-r, 0)$ 出发, 任选一个 $t \in \R$ 作为过 $P$ 点直线的斜率, 即 $y = t(x+r)$, 随后联立之.

$$ (1+t^2)x^2 + 2rt^2x + r^2t^2 - r^2 = 0 $$

由于我们已经知道它的一个根 $x_1 = -r$. 且根与系数的关系给出

$$ x_1 + x_2 = -\frac{2rt^2}{1+t^2} $$

立得 $x_2 = r \cdot \frac{1-t^2}{1+t^2}$. 从而给出一个熟知的有理参数化

$$ t \quads\mapsto r \cdot \bigg(\frac{1-t^2}{1+t^2}, \frac{2t}{1+t^2}\bigg) $$

这样一种寻找点的方式, 通常被称为弦切法.

Exegesis. 圆曲线 [circular-curve]

December 30, 2024
kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\d{\operatorname{d}}$ $\gdef\E{\operatorname{E}}$ $\gdef\arc{\text{arc}}$ $\gdef\R{\mathbf{R}}$ $\gdef\Q{\mathbf{Q}}$

考虑半径为 $r$ 的实圆周 $x^2+y^2=r^2$，其在上半平面的轨迹可表为函数 $y=\sqrt{r^2-x^2},x\in[-r,r]$，长度为

$$ L \spaces= \int_{-r}^r\dfrac{r}{\sqrt{r^2-x^2}}\d x \spaces= r\arcsin\dfrac{x}{r}\bigg|_{-r}^r \spaces= \pi r $$

因而圆的弧长定义了反正弦函数，即

$$ \arcsin x \spaces= \int_0^x\dfrac{1}{\sqrt{1-t^2}}\d t $$

其反函数被称为正弦函数，统称圆函数或者三角函数.

现在, 注意到 $\cot(x)$ 和 $\cot^\prime(x)$ 满足 $\cot^2(x) + \cot^\prime(x) = 1$, 令 $(\cot(x), \cot^\prime(x)) \mapsto (x,y)$, 即 $y=c-x^2$.

其他三角函数及其导数也有类似的关系, 以下列出.

$$\def\arraystretch{2}\begin{array}{|c|c|c|c|} \hline u & (u, u^\prime) \mapsto (x,y) & g & \int \frac{\d x}{y} \\ \hline \cot & y = -x^2-1 & 0 & -\tan^{-1} x \\ \hline \tan & y = x^2 + 1 & 0 & \tan^{-1} x \\ \hline \cos, \sin & y^2 = 1-x^2 & 0 & \tan^{-1}\dfrac{x}{\sqrt{1-x^2}} \\ \hline \sec, \csc & y^2 = x^4-x^2 & 0 & \dfrac{x\sqrt{x^2-1} \tan^{-1}(\sqrt{x^2-1})}{\sqrt{x^4-x^2}} \\ \hline \end{array}$$

现在取 $C(\Q): y=x^2+1$ 上一定点 $(0, 1)$, 固定斜率 $t$ 从而有直线 $\ell(\Q): y=tx+1$, 类似地求曲线 $\ell(\Q) \cdot C(\Q) = 0$ 的交点, 得到 $(t, t^2+1)$.

如果我们对抛物线 $C(\R)$ 求弧长, 所得到的将是 $\log$ 或 $\sinh^{-1}$ 的代数函数. 当然, $\sinh^{-1}$ 实际上也是 $\log$ 的代数函数. $$ \begin{aligned} s &\spaces= \int\sqrt{1+(2x)^2}\d x \\ &\spaces= \frac12 \sqrt{1+4x^2} + \frac14\sinh^{-1}(2x) \end{aligned} $$

现在重新回顾

$$ \int\dfrac{\d x}{y}, \quad y = \sqrt{r^2-x^2} $$

积分号内的项是 $x,y$ 的有理函数, $y$ 是 $x$ 的代数函数, 同时我们已经知道 $x,y$ 满足的代数方程有一个有理参数化, 也就是说

$$ \begin{aligned} \int\dfrac{\d x}{y} &\spaces= \int \frac{\d{(\frac{1-t^2}{1+t^2})}}{\frac{2t}{1+t^2}} \\ &\spaces= \int -\frac{4t}{(1+t^2)^2} \cdot \frac{1+t^2}{2t} \d t \\ &\spaces= \int -\frac{2}{1+t^2} \d t \\ &\spaces= -2\tan^{-1} t \end{aligned} $$

这是切线半角换元或者按俄罗斯与国内更流行的称呼则是万能三角换元. 另一方面, 我们知道 $t = \pm\frac{\sqrt{1-x}}{\sqrt{1+x}}$. 这就意味着 $\arcsin x$ 和 $-2\tan^{-1} t$ 之间最多只相差一个常数, 容易计算这个常数正是 $\frac{\pi}2$, 则有

$$ \arcsin x \spaces= \frac{\pi}2-2\arctan\frac{\sqrt{1-x}}{\sqrt{1+x}} $$

双曲线时的情况略有不同. 考虑 $C(\R):x^2-y^2=1$, 如果朴素地计算平面直角坐标系上的积分, 将得到一个会被归类为椭圆积分的表达式

$$ \int \sqrt{\frac{2x^2-1}{x^2-1}} \d x \spaces= \int \frac{4x^4-1}{\sqrt{x^2-1}\sqrt{2x^2+1}} \d x $$

由于分子部分的 $4x^4-1$ 是多项式函数, 因此整个积分的核心就在于下面这一项

$$ \int \frac1{\sqrt{(x^2-1)(2x^2+1)}} \d x \tag{1} $$

椭圆积分的经验很容易让我们认为最后的结果当中势必会出现椭圆函数. 事实正是如此, 注意这个时候 $y^2 = (x^2-1)(2x^2+1)$ 的 $g$ 是 $1$, 而且实际上在引入椭圆函数后, $(1)$ 的表达式要远比弧长的表达式复杂.

现在考虑双曲线 $C(\R)$ 的一个参数化 $$ (x,y) \quads\mapsto (\cosh t, \sinh t) $$

相应的, 关于 $x \in [a,b]$ 弧长积分变为 $t \in [\cosh^{-1}a, \cosh^{-1}b]$ 的积分

$$ \begin{aligned} \int \sqrt{\sinh^2 t + \cosh^2 t} \d t &\spaces= \int \sqrt{\cosh 2t} \d t \\ &\spaces= -i \E(it \mid 2) \\ &\spaces= -i \E(i \cosh^{-1}x \mid 2) \\ &\spaces= \E(\sin^{-1}x \mid 2) \\ \end{aligned} $$

周期函数的构造 [periodic-2A]

December 31, 2024
kokic

$\gdef\R{\mathbf{R}}$ $\gdef\Z{\mathbf{Z}}$ $\gdef\spaces#1{~ #1 ~}$

我们的目的是构造某些完备域上的非常值周期函数. 对于实数域 $\R$, 圆函数告诉我们这当然是可行的, 不过我们的构造过程应当不依赖于对圆函数的印象.

Exegesis. Weierstraß 的灵感来源 [periodic-2B]

$\gdef\spaces#1{~ #1 ~}$

对于周期 $1$. 下面这个观察因为 Weierstraß 的使用而变得广为人知. 具体来说, 可以从这样一个级数出发

$$ f(x) \spaces= \sum_{n \in \Z} \frac1{(n-x)^2}, \quad x \notin \Z $$

因为 $n$ 取遍了所有整数, $f(x)$ 在映射 $n \mapsto n + k$, $k \in \Z$ 下不变. 这样一来, 如果 $x$ 被选定为任意一个整数, 总会存在 $n-x$ 为零的项使整个级数发散, 这就要求 $x \notin \Z$. 同样的, $f(x)$ 在映射 $x \mapsto x + k$, $k \in \Z$ 下不变, 这就意味着 $f(x)$ 以 $1$ 为周期. 现在我们当然知道这个 $f(x)$ 其实就是 $\pi^2\csc^2(\pi x)$.

由于 $(n-x)^2 \ge x^2-n^2$, 这使得如下级数也是收敛的

$$ \sum_{n \in \Z} \frac{x}{x^2-n^2} \quad (= ~ \pi\cot(\pi x)) $$

Exegesis. 双周期函数 [periodic-2C]

$\gdef\R{\mathbf{R}}$ $\gdef\Q{\mathbf{Q}}$ $\gdef\Z{\mathbf{Z}}$ $\gdef\spaces#1{~ #1 ~}$

我们要求两个 $\R$-周期 $T_1,T_2$ 是 $\R$-线性无关的, 否则周期之比 $\frac{T_1}{T_2} = \frac{p}{q} \in \Q$, $\gcd(p,q) = 1$, 这意味着 $T_i$ 生成的周期集合退化

$$ \begin{aligned} \{ nT_1 + mT_2 : n,m \in \Z \} &\spaces= \left\{ \left(\frac{np}{q} + m \right) T_2 : n,m \in \Z \right\} \\ &\spaces= \left\{ (np + mq) \cdot \frac{T_2}{q} : n,m \in \Z \right\} \end{aligned} $$

此时 $np + mq \in \Z$, 所以该集合被周期 $\frac{T_2}{q}$ 生成, 矛盾.

数据与可计算结构 [data-structure]

七树合一定理 [seven-trees-in-one]

September 24, 2024
kokic
$n$Lab

Definition. 二叉树类型 [binary-tree]

September 24, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

二叉树意味树的每个结点最多两个子树. 其类型由两个构造器归纳给出

inductive Tree α
  | leaf : Tree α
  | node : α → Tree α → Tree α → Tree α

叶结点构造器 leaf 用于构造出一棵空树, 空树作为某个结点的所有子结点时, 该结点正是叶结点. 相应的, 二叉树的值存储在非叶结点中. 每个 (非空, 无标记) 二叉树类型的值要么是一个单结点 $\{\text{pt}\} = 1$, 要么等价于二叉树的有序配对 $B \times B = B^2$. 即 $B \xrightarrow{\sim} \{\text{pt}\} \sqcup B^2$.

换言之, 二叉树可定义为某种满足 $B=1+B^2$ 的 (代数) 结构. 回顾 $6$ 次分圆多项式 $$ \Phi_6(x) \spaces= x^2-x+1 $$ 其复根 $\zeta_6$, $\zeta^{-1}_6$ 是所谓的 $6$ 次本原单位根.

Theorem. Blass–Lawvere 定理 [blass-lawvere]

September 24, 2024
kokic

$\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$

记 $B$ 是二叉树类型, 则存在一个 “极精确的双射” $B \xrightarrow{\sim} B^7$.

显然并非所有 $\zeta_6$ 满足的等式都能提升到 $B$ 之间的同构, 如 $B^6 \ncong 1$. 自然的问题是, 哪些等式能提升到同构? 这个问题由下面的 Fiore–Leinster 定理回答.

Theorem. Fiore–Leinster [fiore-leinster]

$\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$

设 $f,g_1,g_2 \in \N[x]$, 其中 $f$ 有非零常数项且 $\deg f \ge 2$. 若 $f(x) - x$ 整除非常值的 $g_1-g_2$ (在 $\Z[x]$ 中), 则在 $\N[x]/(x=f(x))$ 中, $g_1(x)=g_2(x)$.

特别的, 取 $f(x)=1+x^2$, Fiore–Leinster 定理表明, 若在 $\N[x]/(x=1+x^2)$ 中成立 $f(x) = g(x)$, 则存在 “极精确的双射” $f(B) \cong g(B)$. 在 $\N[x]/(x=1+x^2)$ 中可以演绎得到 $x=x^7$ 但无法给出 $1=x^6$. 对于前者 $x^7-x = (x^2-x+1)(x^5+x^4-x^2-x) = 0$. 再看 $x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)$, 这给出 $B^4+B^2+1 \ncong 0$, $B^4+B^2+B+1=B$.

这套想法亦可应用于其他树结构, 如有根平面树, 其每个结点有 $0$, $1$ 或 $2$ 个子结点, 即 $T \cong 1+T+T^2$. 由 Fiore–Leinster 定理, 存在 “极精确的双射” $T \cong T^5$.

栈置换–二叉树同构 [isomorphism]

November 06, 2024 — November 08, 2024
kokic
CC BY-NC-SA 4.0
PDF

Definition. 栈置换 [stack-permutation]

November 06, 2024
kokic

栈置换 (stack permutation) 也称作栈混洗 (stack shuffle). 给定一个非空栈 $A$ 和空栈 $B$ 与 $S$, 每次只允许 $(i)$ 弹出 $A$ 并压入 $S$. $(ii)$ 弹出 $S$ 并压入 $B$. 可以想见, 最终 $A$ 的元素一定会全部进入 $B$. 这样的 $B$ 就称为 $A$ 的一个栈置换.

不难发现, $A$ 的所有栈置换其实就是 $A$ 的所有出栈可能. 熟知 $n$ 元素栈共有 $\frac1{n+1}{2n \choose n}$ 种出栈情况. 另一方面, $n$ 个节点能构成 $\frac1{n+1}{2n \choose n}$ 种二叉树, 两者的计算都可以在 Catalan 数的相关条目中找到. 这表明两者作为集合同构, 一个可以考虑的问题是, 如何实现该同构? 即, 具体地写出这个双射. 这方面的开创性工作来自 R. F. Hille.

Definition. Hille 编码 [hille-encode]

1982
Reinhold Friedrich Hille
Stack permutations and an order relation for binary trees

以下三条规则给出 Hille 编码到二叉树的转换过程. 同时不难验证, 任给一个二叉树, 可以通过这三条规则得到其 Hille 编码.

1 表示添加当前树节点的左子树. 例如 111 表示的树为 (⋅ (⋅ (⋅))).
01 表示添加当前树节点的右子树. 例如 10101 表示的树为 (⋅ _ (⋅ _ (⋅))).
而对于 01 前的 $k$ 个 0, 这些 0 用于表示将当前树节点回溯到前 $k$ 层. 例如 11001 表示的树为 (⋅ (⋅) (⋅)).

注意到每个树节点的双亲 (parent) 节点是唯一的, 因此回溯操作良定, 一次回溯就是将当前节点改为其双亲.

相应的, 可以据此定义 Hille 编码的解析规则, 用于将这样一段有效的二进制序列转换为构造一颗二叉树的若干操作. 我们使用一种类 BNF 文法来定义这个解析器, 仅供读者理解.

由于我们的讨论不涉及具体元素, 不失一般性, 可以固定栈置换的入栈顺序为 $123\cdots n$. 同时这些数字也是二叉树节点的标签. 影响出栈序列的只有压入和弹出两个操作, 而构建二叉树允许的操作粗看起来要多一些. 因此首先需要通过一些技巧将二叉树构建操作的表示简化. 我们将栈的压入和弹出分别编码为 1 和 0, 并将栈置换对应的二进制序列称为栈编码. 对应的, 以 Hille 编码刻画二叉树的构建.

Example. $n=3$ [three-nodes]

November 06, 2024
kokic

以下写出三节点二叉树的所有 $5$ 种情况, 以展示这些树的二进制序列如何对应到栈置换. 此处二进制序列按栈弹空为标准, 补充了末尾的零.

这个过程的反向实际上并不平凡, 如果只考虑 $n=3$ 也就是上图的情况, 敏锐的读者可以发现, 这些栈置换其实就是二叉树按节点添加顺序 ¹ 编号后的中序遍历序列 ². 我们接下来将解释其中的不平凡之处, 以及这一巧合发生的具体条件. 首先是对原始文献的一个观察, Hille 原始文献当中提出的算法实际上存在错误, 将之改写成 Lean4 语言, 即

def encode : Tree → String
  | .node l r => "1" ++ encode l ++ encode r
  | _ => "0"

只要考虑下面这个例子即可发现, 将一棵二叉树转化为它的 Hille 编码并非是简单的中序遍历.

可以验证, 从 110100100 这个编码出发, 无法直接恢复原本的 , 其正确的 Hille 编码应该为 1101000100. 但是另一方面, 如果将序列 110100100 解释为栈的压入弹出操作, 即栈编码, 则可以得到正确的栈置换 2314. 这就意味着, 当二叉树的节点个数 $n > 3$ 时, 存在二叉树使得其栈编码与 Hille 编码不同. 回忆二叉树和栈置换之间的双射关系, 这表明必然存在一套手续允许我们在两者之间互相转换, 下面我们将构造性地给出这个结果. 见栈编码与 Hille 编码的等价性. 随后通过相交率解释, 为何中序遍历在 $n$ 不大情况下能够频繁得到正确的 Hille 编码.

Proposition. 栈编码与 Hille 编码的等价性 [equivalence]

November 06, 2024
kokic

首先容易验证的是, 中序遍历总是能够给出二叉树 $b \in B$ 到栈置换 $s \in S$ 的映射, 而对于每一个栈置换 $s \in S$, 都能够写出唯一的二进制序列, 即栈编码 $c \in C$. 不考虑末尾连续的 0, 当栈编码 $c$ 与二叉树 $b$ 的 Hille 编码 $h \in H$ 相同时, 对 $B$ 直接进行中序遍历便能得出正确的 Hille 编码.

$$ \begin{CD} B @>>> S \\ @VVV @VVV \\ H @>>> C \end{CD} $$

Proof. [equivalence-pf]

November 06, 2024
kokic

记 $B \to H$ 为 $f$, 根据 Hille 编码的定义, $f$ 是一个双射. 根据二叉树的性质, $g: B \to S$ 是中序遍历, 前文已经固定栈置换的入栈顺序为 $123\cdots n$, 这样一来就固定了 $B$ 的层序遍历, 因此 $g$ 也是双射. 现在来看 $h: S \to C$, 这显然也是一个双射. 最后, 我们能够从 $h \in H$ 当中恢复出 $c \in C$ 的信息, 只要将 $h$ 序列视为栈编码, 并且忽略空栈的弹出, 这就意味着 $H \to C$ 是满射, 随后利用 $C \to S \to B \to H$, 这样就得到了 $H \cong C$.

现在, Hille 原文所使用的 encode 算法就是 $h \circ g: B \to C$, 而预期的正确实现则是 $f$, 因此两者在结果上相差一个同构.

Proposition. 相交数 [intersection]

November 06, 2024
kokic

$\gdef\eqdef{\overset{\scriptscriptstyle\text{def}}{=}}$ $\gdef\spaces#1{~ #1 ~}$

所有 $n$ 节点二叉树的 Hille 编码构成的集合记为 $H_n$, 所有 $n$ 节点二叉树的栈编码构成的集合记为 $C_n$. 对于 $H_n \cap C_n$ 的大小 $a_n \eqdef |H_n \cap C_n|$, 我们有如下刻画.

$$ a_n \spaces= \sum_{k = 0}^{n-1} \sum_{j = 0}^{n-k} \frac{1}{j+1}\binom{n-k-j}j \binom kj \binom{k+j+2}j $$

记 $N = n+1$. 等式的证明可以通过分析一个半长为 $N$ 且不包含 UUDD 子序列的 Dyck 路径得到. 同时这也是从 $(0,0)$ 到 $(N,N)$ 不越过对角线且允许步长 $(1,k), (k,1), k \geqslant 1$ 的格路径的个数. 或者更简单地说, 是长度为 $N$ 的斜 Motzkin 路径的个数.

Corollary. 相交率 [ratio]

November 06, 2024
kokic

记 Catalan 数为 $c_n$, 也即 $H_n$ 或 $C_n$ 的个数. 自然要问 $|H \cap C_n|$ 在全体 $n$ 节点二叉树个数中所占的比例与 $n$ 的关系. 根据相交数与 Catalan 数的渐进估计 $a_{n} \sim \frac{\sqrt{2 + r}}{2\sqrt{\pi}n^{3/2}r^{n}}$, $c_n \sim \frac{4^n}{\sqrt\pi n^{3/2}}$ 可以知道 $\lim\limits_{n\to\infty} \frac{a_n}{c_n} = 0$. 并且事实上只要二叉树的节点个数 $n$ 大于 $8$, $H_n$ 与 $C_n$ 相同的部分就会少于整体的一半.

Exegesis. 有效长度的上下界 [bounds]

November 06, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

一个可供探究的问题是, 给定 $n$ 节点二叉树, 询问其 Hille 编码 $H_n$ 有效长度 $\ell(H_n)$ 的范围. 这里的有效不外乎是指去除末尾连续的 0. 我们将对此问题给出确切的回答.

任意 $n$ 节点二叉树的 Hille 编码的有效长度满足下面的不等式

$$n \spaces\leqslant \ell_{n} \spaces\leqslant \max(0,2n - 1,3n - 4)$$

下界 $n$ 的验证是容易的, 构造一棵 $n$ 节点二叉树最少也需要 $n$ 个 1. 由于此处的讨论, 我们只需要验证 $n \geqslant 3$ 时 Hille 编码的有效长度至多是 $3n - 4$.

Proof. [bounds-pf]

November 06, 2024
kokic

注意到为使有效长度最大, 相应的二叉树中的右节点个数和回溯次数要尽可能多. 同时满足这两个要求意味着 $(i)$ 除根节点外至少有一个左结点 ¹. $(ii)$ 该二叉树必有一个位于根节点右侧的节点 ². 如下图所示

由此出发, 我们将剩余的所有 $n-3$ 个节点全部添加到树中唯一的左节点的右侧. 即

下面我们只需算出 $\ell(M)$, 便可得到 $\ell_n$ 的最大值. 不妨直接写出 $h(M)$

立刻看出 $\ell(M) = 2 + 2(n-3) + (n-2) + 2 = 3n-4$.

如若不然, 这颗二叉树只会形如 1010101$\cdots$, 其长度为 $2n - 1$.

否则回溯贡献的长度便不是最大值 $n-2$.

反过来, 从树 $M$ 出发, 也可以验证任何使得节点总数不变的操作都不会增加其 Hille 编码的有效长度. 更进一步, 我们可以断言任何使得节点总数不变的操作都将严格减小其 Hille 编码的有效长度. 换言之, 使得 $\ell(B) = 3n-4$ 的二叉树 $B$ 的结构是唯一的, 即 $M$.

即按照 Hille 编码逐步添加节点的顺序.

如二叉树 1101000100 按添加顺序对节点编号, 然后做中序遍历得到的是 2314.

综合微分法 [synthetic-differential]

May 9, 2024 — May 14, 2024
kokic

Exegesis. 数值微分的误差 [numerical]

May 9, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

我们首先观察朴素的数值微分的计算过程. 待微分函数为 $(x+3)^2$, 此处不妨取 $x=-2$, $h=10^{-5}$, 这一位置的导数 $A$ 近似为

$$ A \quads\approx \frac{f(x+h)-f(x)}h \eqq \frac{(1 + 10^{-5})^2 - 1^2}{10^{-5}} \eqq 2.00001 $$

并且如果试图得到与预期的 $A=2$ 更接近的结果, 则须将无穷小近似 $h$ 选取为更靠近 $0$ 的数值, 这对于浮点精度有限的计算机来说极为不利.

而常规符号微分程序视表达式为树结构, 通过遍历树并对符合模式的节点应用求导规则 $(uv)' = u'v+uv'$. 即

$$ \begin{aligned} (x+3)^2 & \spaces\to (x+3)'(x+3) + (x+3)(x+3)' \\ & \spaces\to 1 \cdot (x+3) + (x+3) \cdot 1 \\ & \spaces\to 2x+6 \end{aligned} $$

此时再应用 $x=-2$ 得到 $A=2$. 这个做法在结果上可行, 但处理复杂的表达式时, 复合求导的中间过程本身会产生大量新的结点, 使递归遍历的实际时间达到指数级 $\mathcal{O}(2^N)$.

有没有方法可以既避免递归又减少中间结点呢? 我们先看一个涉及复数域的观察.

Exegesis. 复步微分法 [complex-step]

May 13, 2024
kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$

Mathworks 的创始人 Cleve Moler 约 60 年 ¹ 前提出了借用虚数单位 $i$ 的数值微分, 相关文献称为 complex step 微分法 ². 考虑光滑函数 $f(x)$, 其在 $x=a$ 处可表为关于 $X$ 的 Taylor 级数 ³ $f(a) + f'(a)(X-a) + \text{etc.}$, 注意

$$ f(a+i h) \spaces= f(a) + i h f'(a) - \frac{h^2}{2!}f''(a) - \frac{ih^3}{3!}f'''(a) + \cdots $$

这个其实就是将 Taylor 级数的每一项完全展开, 在后续的计算中也会继续用到. 如此便有 $$ \frac{\partial f}{\partial x} \spaces= \frac{\Im f(x+ih)}{h} + \mathcal{O}(h^2) \quads\implies \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$

这个方法最初被设计用于处理数值微分问题, 但稍加思考就能发现, 该过程也适用于符号微分. 与前一个问题所改进的结果的精度不同, 用于符号微分时, 所取得的优势是更精简的中间表达式和非递归的计算过程.

即 1967 年. 不过这个名字要等到 1998 年, William Squire 和 George Trapp 才正式提出.

按方法的流程看, complex step 微分可以翻译为 “复步微分”.

习惯上会混淆 $x$ 与 $X$.

Exegesis. 误差修正 [moler-correction]

May 9, 2024
kokic

$\gdef\C{\mathbf{C}}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

选取同样的 $h=10^{-5}$, 以下计算表明 Moler 的方法相比此处基于有限差分的数值微分方法能够很好的避免精度损失.

$$ \frac{\Im(1 + 10^{-5}i)^{2}}{10^{-5}} \eqq \frac{\Im(\square + 2 \times 10^{- 5}i)}{10^{- 5}} \eqq 2 $$

实际上此处 $h$ 的选取, 只要其非零, 从而带有 $i$ 的项不消失, 就不会影响到最终的结果. 换言之, 这个方法从根本上来说, 是无关于 $h \in \R\smallsetminus\{0\}$ 和 $i$ 的, 只是在数值计算时借由复数算术和复函数值可以免去一些幂零结构的讨论. 一旦意识到这一点, 我们便可以将复步微分法的

$$ \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$

中的近似 “$\approx$” 修正为严格等于 “$=$”, 这只需要将 $\{z \in \C : z^2 = -1\}$ 替换为 $D = \{x \in R : x^2 = 0\}$, 问题就来到了如何构造这样的 $R$ 使得 $D$ 中有非零的元素, 这样的结构实际上会动摇经典逻辑中对于排中律的看法.

Definition. 对偶数 [dual-number]

May 14, 2024
kokic

$\gdef\R{\mathbf{R}}$ $\gdef\C{\mathbf{C}}$

一种通俗的讲法是, 认为对偶数 $R[x]/(x^2)$ 可以作为复数 $\R[x]/(x^2+1)$ 的类比. 如果有读者能轻率地暂时忽略 $R[x]/(x^2)$ 这种结构的存在性, 或者说接受了下面的 $d$ 的定义

$$ \exists ~ d \in R\smallsetminus\{0\}, ~ d^2 = 0 $$

不能接受也很正常, 因为这轻易就会导致某个经典逻辑中的矛盾. 相比之下满足 $x^2 = -1$ 的 $x$ 对于大众而言要更容易接受的多, 甚至对于三次方程是必须品. 为此我们需要下面的准备工作.

Axiom. Kock–Lawvere [kock-lawvere]

May 13, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\R{\mathbf{R}}$

首先需要强调的是, 这个公理所涉及到的结构的有效性全都依赖于意象理论, 而相关基础的严格性保证基本上在 1970 年之前就已经由 William Lawvere 完工. 记 $\mathcal{E}$ 是光滑空间之间的光滑映射构成的范畴, 同时假定 $\mathcal{E}$ 还是笛卡尔闭范畴, 也就是 $\mathcal{E}$ 中的箭头对笛卡尔积封闭.

我们可以从 $\mathcal{E}$ 中选出一条几何直线 $R$, 通过指定 $R$ 上两点 $0$ 和 $1$ 之间的距离作为单位长度来确定其他线段的长度. 发挥一些古希腊精神, 线段的移动可以给出 $R$ 上的加法, 尺规作图所构造的相似三角形能给出 $R$ 上的乘法 $\gamma = \alpha\beta$.

因此 $R$ 带有交换环结构, 并且允许经典数学中的对象实数环 $\R$ 成为 $R$ 的模型, 注意这里我们只能考虑 $\R$ 作为环的部分, 因为 $R$ 中存在着幂零元.

Kock–Lawvere 公理说的是, 对任意映射 $f: D \to R$, 存在唯一的 $a,b \in R$, 使得

$$ f(\epsilon) \spaces= a + b \epsilon, \quad \forall \epsilon \in D $$

将这里的 $a$ 换成 $f(0)$, 并完全使用量词叙述, 则是

$$ \forall ~ f \in R^D, ~ \exists! ~ b ~ \text{s.t.} ~ \forall ~ d \in D \quad (f(d) = f(0) + b d) $$

如果说这个公理的形式还不足以暗示它的目的, 那么下面这个推论就完全能做到了.

Corollary. 所有函数都光滑 [smooths]

May 13, 2024
kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$

对任意函数 $f:R \rightarrow R$, 存在唯一的函数 $f':R \rightarrow R$ 满足

$$ f(x + \varepsilon) \spaces= f(x) + f'(x)\varepsilon,\quad \forall ~ x \in R, ~ \forall ~ \varepsilon \in D $$

这个通常作为 Kock–Lawvere 公理的推论出现, 不过从 $\mathcal{E}$ 的定义来看, 这才是整套框架真正的目的之一. 即, 为全体函数恢复牛顿时期 “幂零无穷小量” 计算上的直观, 而不导致矛盾.

Axiom is incompatible with the law of excluded middle. Either the one or the other has to leave the scene. In Part I of this book, the law of excluded middle has to leave, being incompatible with the natural synthetic reasoning on smooth geometry to be presented here. In the terms which the logicians use, this means that the logic employed is ‘constructive’ or ‘intuitionistic’. We prefer to think of it just as ‘that reasoning which can be carried out in all sufficiently good cartesian closed categories’.
— Anders Kock, Synthetic Differential Geometry

无论是单纯接受这个公理还是认可该公理存在的舞台 $\mathcal{E}$, 其实都会导致完全相同的结果, 那就是 $\mathcal{E}$ 当中一般函数的性质发生了变化, 让所有的函数都变得光滑. 与之相对的, 这样的好性质所要求的代价是, $\mathcal{E}$ 当中不能使用经典逻辑中的选择公理、排中律、反证法等命题.

Exegesis. 矩阵表示 [matrix-represent]

May 9, 2024
kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\str#1{{\footnotesize #1}}$ $\gdef\C{\mathbf{C}}$ $\gdef\spaces#1{~ #1 ~}$

这样一来, 我们所说的 “将近似修正为严格等于” 就可以精确表示为

$$ \frac{\partial f}{\partial x} \quads= f(x+\varepsilon) ~ \str{中} ~ \varepsilon ~ \str{项的系数} $$

复步微分法的来源是完全解析的, 但其得到的微分方法却能代数地刻画. 正如我们可以考虑复数的 $z = a+b\sqrt{-1} \in \C$ 矩阵表示

$$ A \spaces= \begin{pmatrix} a & -b \\ b & ~~~a \\ \end{pmatrix} ,\quad \det A \spaces= (a+b\sqrt{-1})(a-b\sqrt{-1}) $$

我们也可以构造对偶数 $a + b \varepsilon \in R$ 的矩阵表示, 并自动得到微分运算的加法和乘法规则, 这可以被简单地视为 Moler 方法的矩阵版本.

$$ A \spaces= \begin{pmatrix} a & a' \\ 0 & a \\ \end{pmatrix} ,\quad \det A \spaces= (a+b\varepsilon)(a-b\varepsilon) $$

Example. 导出微分运算 [derived-differential]

May 9, 2024
kokic

$\gdef\Mat{\operatorname{Mat}}$ $\gdef\d{\operatorname{d}}$ $\gdef\Z{\mathbf{Z}}$ $\gdef\spaces#1{~ #1 ~}$

设 $u, v \in R^R$, $n \in \Z$. 记 $A(u, u') = (\begin{smallmatrix} u & u' \\ 0 & u \end{smallmatrix})$. 从矩阵运算中立刻得到

$A(u, u') + A(v, v') \spaces= A(u+v, u'+v')$
$A(u, u') - A(v, v') \spaces= A(u-v, u'-v')$
$A(u, u') \cdot A(v, v') \spaces= A(uv, u'v + uv')$
$A(u, u') \cdot (A(v, v'))^{-1} \spaces= A(uv^{-1}, (u'v - uv')v^{-2})$
$(A(u, u'))^n = A(u^n, nu^{n-1}u')$

对于 $e^{A(u,u')}$, 注意 $A(u, u') = A(u, 0) + A(0, u')$, 这里 $(A(0, u))^2 = 0$. 同样可以计算得到 $e^{A(u,u')} = A(e^u, 0) \cdot A(1, u') = A(e^u, e^u u')$. 而对于 $\log A(u,u')$ 我们直接展开为 $\sum_{k \ge 1}\frac{(-1)^{k+1}}{k} \cdot (A-1)^k$ 即可验证:

$$ \begin{pmatrix} \sum_{k \ge 1}\frac{(-1)^{k+1}}{k} \cdot (u-1)^k & \sum_{k \ge 0} (-1)^k (u-1)^k \cdot u' \\ 0 & \sum_{k \ge 1}\frac{(-1)^{k+1}}{k} \cdot (u-1)^k \end{pmatrix} \spaces= \begin{pmatrix} \log u & u'u^{-1} \\ 0 & \log u \end{pmatrix} $$

Exegesis. 链式法则 [chain-rule]

May 9, 2024
kokic

$\gdef\Mat{\operatorname{Mat}}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\d{\operatorname{d}}$ $\gdef\eqdef{\overset{\scriptscriptstyle\text{def}}{=}}$

与 $\Mat_{2 \times 2}(R^R)$ 上的运算不同, 复合运算是只位于 $R^R$ 上的, 或者说 $\Mat_{2 \times 2}(R^R)$ 上并没有周知的复合运算. 为了自然地给出 $A: J^1(R, R) \to \Mat_{2 \times 2}(R^R)$ 上的复合, 这里 $J^1$ 是一阶射流丛. 记 $\square(x)$ 为 $\square_x $, $A(u)$ 为 $A(u,u')$, 考虑显式应用的 $A(u)$, 即

$$ A(u)_x \spaces\eqdef \begin{pmatrix} u_x & u'_x \\ 0 & u_x \end{pmatrix} \spaces\in \Mat_{2 \times 2}(R), \quad x \in R $$

对于 $u: Y \to Z$, $v: X \to Y$. $A$ 上的复合 $A(u) \circ A(v)$ 可定义为 $A(u)_{v_x}$, $(v_x, v'_x) \in A(v)_x$. 我们来验证 $A(u) \circ A(v) = A(u \circ v)$.

$$ \begin{aligned} A(u)_{v_x} &\spaces= \Big(u \cdot \frac{\partial A}{\partial u} + \frac{\d u}{\d x} \cdot \frac{\partial A}{\partial u'}\Big)\Big|_{v_x} \\ &\spaces= u(v_x) \cdot \frac{\partial A}{\partial u} + \frac{\d u(v_x)}{\d v_x} \frac{\d v_x}{\d x} \cdot \frac{\partial A}{\partial u'} \\ &\spaces= A(u(v(x)), u'(v(x))v'(x)) \\ \end{aligned} $$

线性代数杂记 [linear-algebra]

Conjecture. Kontsevich 周期性猜想 [kontsevich-periodicity]

February 16, 2025
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\Mat{\operatorname{Mat}}$ $\gdef\Q{\mathbf{Q}}$

令 $(M_{ij})_{1 \le i,j \le 3}$ 是包含 $9$ 个非交换独立变量的矩阵. $I_1: M \to M^{-1}$ 是对矩阵求逆, $I_2: M_{ij} \to M_{ij}^{-1}$ 是对矩阵各分量求逆, $I_3: M \to M^T$ 是矩阵的转置. 则 Kontsevich 猜测, 存在两个 $3$ 阶对角矩阵 $L,R$ 使得

$$ (I_3 \circ I_2 \circ I_1)^3(M) \spaces= LMR $$

且这里 $I,R$ 的分量是以 $M$ 的 $9$ 个分量 $M_{ij}$ 为变量的非交换有理函数.

Kontsevich 周期性猜想已由 Natalia Iyudu 和 Stanislav Shkarin 于 2013 年 5 月 8 日证明, 因此这一猜想有时也被称作 Iyudu–Shkarin 定理. 不过这个证明过于暴力, 也没有对于一般的矩阵 $M \in \Mat_{n \times n}$ 回答 $n>3$ 时的 Kontsevich 周期性猜想

$$ (I_3 \circ I_2 \circ I_1)^n(M) \spaces= LMR $$

为何不成立 ¹.

Exegesis. $n=2$ 交换版本 [kontsevich-periodicity-2A]

February 18, 2025
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\Mat{\operatorname{Mat}}$

我们来观察对于交换环 $R$ 和对应的 $\Mat_{2\times 2}(R)$ 中的矩阵, $(I_3 \circ I_2 \circ I_1)^2$ 具体做了些什么. 令 $\varphi = I_3 \circ I_2 \circ I_1$, 则 $\varphi(M)$ 可以算出是

$$ \varphi: ~ M ~\leadsto~ \det M \cdot S I_2(M) S^T $$

其中 $S = (\begin{smallmatrix}0 & -1 \\ 1 & ~~~0\end{smallmatrix})$ 是一个行列式为 $1$ 的反对称矩阵 ¹, 记 $\tau: M \leadsto SI_2(M)S^T$, 可以验证 $\tau \circ \tau = \text{id}$. 现在我们来计算 $\varphi^2(M)$.

$$ \begin{aligned} \varphi^2(M) &\spaces= \varphi(\det M \cdot SI_2(M)S^T) \\ &\spaces= \det(\det M \cdot SI_2(M)S^T) \cdot S I_2(\det M \cdot SI_2(M)S^T) S^T \\ &\spaces= (\det M)^2 \det(SI_2(M)S^T) \cdot (\det M)^{-1}M \\ &\spaces= \det M \det(SI_2(M)S^T) \cdot M \\ &\spaces= \det M \det(I_2(M)) \cdot M \end{aligned} $$

也就是说 $\varphi^2(M)$ 实际上会是 $M$ 的常数倍, 并且这个常数是

$$ \det M \det(I_2(M)) \spaces= (ad-bc)\Big(\frac1{ad}-\frac1{bc}\Big) $$

当我们把 $S$ 看作线性映射 $A$ 的表示时, 在定义上 $A$ 就被称为反自伴算子.

如果矩阵的分量是交换元, 则 $n=1,2$ 情况很容易验证. Iyudu 和 Shkarin 在他们的论文中首先验证了 Kontsevich 周期性猜想对于 $n=2$ 非交换的情况也正确, 随后才讨论 $n=3$ 的版本.

Theorem. Rayleigh 商定理 [rayleigh-quotient]

November 5, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

设矩阵 $M$ 是 $n$ 阶对角矩阵, 即

$$ M \spaces= \begin{pmatrix} \lambda_{1} \\ & \ddots \\ & & \lambda_{n} \end{pmatrix} $$

则对非零向量 $x$ 和 $x$ 的共轭转置 $x^*$ 有如下结果:

$$ \min\limits_{1 \leqslant i \leqslant n}\lambda_{i} \spaces\leqslant \frac{x^{\ast}Mx}{x^{\ast}x} \spaces\leqslant \max\limits_{1 \leqslant i \leqslant n}\lambda_{i} $$

其中 $\max\limits_{1 \leqslant i \leqslant n}\lambda_{i}$ 常被称作谱半径.

Exegesis. 某类二次型的商 [rayleigh-quotient-2A]

November 5, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

注意, $x^* M x$ 和 $x^*x = \|x\|$ 当然都是标准二次型. 特别的, 取 $x = \left( x_{1},\cdots,x_{n} \right)^{T}$, 则

$$ x^{\ast}Mx \spaces= \sum_{1 \leqslant i \leqslant n}\lambda_{i}x_{i}^{2},\quad x^{\ast}x \spaces= \sum_{1 \leqslant i \leqslant n}x_{i}^{2} $$

Rayleigh 商定理正是在说

$$ \min\limits_{1 \leqslant i \leqslant n}\lambda_{i} \spaces\leqslant \frac{\sum_{1 \leqslant i \leqslant n}\lambda_{i}x_{i}^{2}}{\sum_{1 \leqslant i \leqslant n}x_{i}^{2}} \spaces\leqslant \max\limits_{1 \leqslant i \leqslant n}\lambda_{i} $$

Rayleigh 商定理中的对角矩阵 $M$ 可推广到 Hermite 矩阵 ¹, 也即 $M$ 是共轭对称的方阵 $M^* = M$, 对实数而言这当然就是对称矩阵. 稍稍回忆线性代数, 有限维谱定理说:

任何实对称矩阵都可以由正交矩阵对角化.
任何复对称矩阵都可以由酉矩阵对角化, 即 Autonne–Takagi 分解.

具体而言, 对于每个实对称矩阵 [resp., 复对称矩阵] $A$, 都存在一个实正交矩阵 [resp., 酉矩阵] 使得 $Q^* A Q$ 是对角矩阵.

Example. 二阶情形 [rayleigh-quotient-2B]

November 5, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

考虑 $M = \scriptsize\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$, 将 $M$ 对角化得到 $D = \scriptsize\begin{pmatrix} 3 & ~~~0 \\ 0 & -1 \end{pmatrix}$, 相应的正交矩阵是 $\frac1{\sqrt{2}}\scriptsize\begin{pmatrix} 1 & ~~~1 \\ 1 & -1 \end{pmatrix}$. 注意, $(uP)^*M(uP) = u^{2}P^*MP$, 因此我们通过 $P^*MP$ 来计算 $Q^*MQ$ ¹:

$$ \frac12 \begin{pmatrix} 1 & ~~~1 \\ 1 & -1 \end{pmatrix}^*\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\begin{pmatrix} 1 & ~~~1 \\ 1 & -1 \end{pmatrix} \spaces= \frac12 \begin{pmatrix} 6 & ~~~0 \\ 0 & -2 \end{pmatrix} \spaces= \begin{pmatrix} 3 & ~~~0 \\ 0 & -1 \end{pmatrix} $$

那么, 这就得到了 $M$ 的 Rayleigh 商之值域

$$ \frac{a^{2} + 4ab + b^{2}}{a^{2} + b^{2}} \quads\to \frac{3a^{2} - b^{2}}{a^{2} + b^{2}} \quads\in \lbrack - 1,3\rbrack $$

下面讨论 $A = \scriptsize\begin{pmatrix} p & q \\ q & p \end{pmatrix}$ 的对角化问题. 依然取正交矩阵 $Q = \frac1{\sqrt2} \scriptsize\begin{pmatrix} 1 &~~~1 \\ 1 & -1 \end{pmatrix}$, 相应的 $Q^*AQ = \scriptsize\begin{pmatrix} p + q & 0 \\ 0 & p - q \end{pmatrix}$. 故

$$ \begin{aligned} \frac{pa^{2} + 2qab + pb^{2}}{a^{2} + b^{2}} \quads\to & \frac{(p + q)a^{2} + (p - q)b^{2}}{a^{2} + b^{2}} \\ \quads\in & [p-q, p + q] \end{aligned} $$

最后, 对于对称矩阵 $\scriptsize\begin{pmatrix} a & b \\ b & c \end{pmatrix}$ 也就是二次形 $ax^2 + 2bxy + cy^2$. 其对角化为

$$ \begin{pmatrix} a & b \\ b & c \end{pmatrix} \quads\mapsto \frac12 \begin{pmatrix} r - \sqrt{s} & 0 \\ 0 & r + \sqrt{s} \end{pmatrix} $$

这里 $r = a + c$, $s = (a-c)^2 + 4b^2$.

由此, 其实不需要真的找一个正交矩阵 $Q$ 使得 $M = Q^*MQ$, 只需让 $P$ 满足 $MP = PD$.

广义 Rayleigh 商 $\frac{x^* A x}{x^* B x}$ 可以通过变换 $D = C^{-1} A C^*{}^{-1}$ 简化为 Rayleigh 商 $\frac{x^* D x}{(C^*x)^*(C^*x)}$, 其中 $C C^*$ 是 Hermite 正定矩阵的 Cholesky 分解. 对此, 我们也给出一例.

Example. 一般二次型的商 [rayleigh-quotient-3A]

November 5, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

我们要求解问题可以叙述成下面的形式

$$ F \spaces= \frac{3a^2 + 4ab + 3b^2}{4a^2 + 12ab + 34b^2}, \quad \min_\R F, \quad \max_\R F $$

这里相应的 $A = \scriptsize\begin{pmatrix} 3 & 2 \\ 2 & 3 \end{pmatrix}$, $B = \scriptsize\begin{pmatrix} 4 & ~~6 \\ 6 & 34 \end{pmatrix}$. 我们首先对 $B$ 进行 Cholesky 分解, 得到 $C = \scriptsize\begin{pmatrix} 2 & 0 \\ 3 & 5 \end{pmatrix}$ 使得 $B = CC^*$. 接下来通过 $C^{-1} A C^*{}^{-1}$ 求出 $D$ 及其对角化 $E$, 这样就结束了此问题.

$$ \begin{aligned} D \spaces= \frac14 \begin{pmatrix} ~~~3 & -1 \\ -1 & ~~~\frac35 \end{pmatrix}, ~~ E \spaces= & \begin{pmatrix} 9-\sqrt{61} & 0 \\ 0 & 9+\sqrt{61} \end{pmatrix} \cdot \frac1{20} \\ \spaces= &\begin{pmatrix} \min_\R F & 0 \\ 0 & \max_\R F \end{pmatrix} \end{aligned} $$

自伴随矩阵, 复对称矩阵.

Exegesis. 置换矩阵构造 [permutation-matrix]

January 16, 2025
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$ $\gdef\str#1{{\footnotesize #1}}$ $\gdef\sstr#1{~{\footnotesize #1}~}$ $\gdef\Mat{\operatorname{Mat}}$

置换矩阵基本上可以认为是置换群的矩阵构造, 或者说矩阵表示. 这也可以为此处的结论及证明提供直观.

首先, 显然所有的置换矩阵都是单位矩阵 $I_n$ 的重新排列. 我们先从置换群 $S_2$ 也就是对换开始. 只考虑其中的非单位元 $\sigma = (1 ~~ 2)$.

$$ \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix} \spaces= \begin{pmatrix} x_2 \\ x_1 \\ \end{pmatrix} , \quad \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \spaces\hookrightarrow (1 ~~ 2) $$

现在来考虑对换的复合, 为了通过矩阵去计算 $(2 ~~ 3)(1 ~~ 2)$, 我们实际上需要先对齐这两个方阵的阶. 换一种角度说, 对换记号 $(i ~~ j)$ 对应的并不是某个固定的方阵, 而是全体如下形式方阵当中的一个 ¹.

$$ I_n \sstr{交换水平方向的} i ~ j \sstr{列得到的方阵} $$

当然, 如果我们固定 $n$, 这样的对应就是唯一的了. 我们在这里强调水平方向是因为台湾等地区关于行列的称呼与大陆是相反的. 具体到矩阵乘法时, 从 $(i ~ ~ j)$ 对应的方阵中选取同阶方阵进行运算.

$$ \underbrace{\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}}_{(2 ~ 3) ~ \curvearrowright ~ I_3} \spaces\cdot \underbrace{\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}}_{(1 ~ 2) ~ \curvearrowright ~ I_3} \eqq \underbrace{\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}}_{(3 ~ 1 ~ 2) ~ \curvearrowright ~ I_3} $$

将矩阵乘法得到的结果翻译回置换，这当然就是 $(3 ~~ 1 ~~ 2)$, 与我们直接计算置换的复合相符. 也就是说

$$ \sigma_2\sigma_1 \quads\cong (\sigma_2 \curvearrowright I) \cdot (\sigma_1 \curvearrowright I) $$

规定为垂直方向当然也可行, 但这样会使得 $A\vec x$ 当中的 $A$ 必须记为它的转置 $A^T$.

Exegesis. 自动机与矩阵求逆 [amtx]

May 9, 2024 — May 10, 2024
kokic
CC BY-NC-SA 4.0

Definition. 正则语言集 [regular-language]

May 9, 2024
kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$ $\gdef\spaces#1{~ #1 ~}$

固定有限字母表 $\Sigma$, 正则语言集 $\textbf{Reg}_\Sigma$ 可定义如下

空集 $\varnothing$ 是正则语言, 作为加法单位 $0_\Sigma$.
只包含空字符串的集合 $\{\epsilon\}$ 是正则语言, 作为乘法单位 $1_\Sigma$.
对于 $a \in \Sigma$, $\{a\}$ 是正则语言.
对于正则语言 $A$, $B$. $A \cup B$, $A \times_\Sigma B$ 和 $A^*$ 是正则语言.
$\Sigma$ 上不存在其它正则语言.

这里 $A \times_\Sigma B$ 基本就是 $A \times B = \{ (a, b) : a \in A, b \in B \}$, 但将配对 $(a, b)$ 视为字符串拼接 $a b$. $A$ 的闭包 $A^*$ 定义为满足如下性质的最小集合.

$\quad (i)$ 匹配空. 即 $\epsilon \in A^*$. $\quad (ii)$ 对拼接封闭. 即 $A \times_\Sigma A \times_\Sigma \cdots \times_\Sigma A \subset A^*$.

这里的 $\square^*$ 通常被称为 Kleene 星运算, 按照数学的习惯, $A^*$ 也被称为集合 $A$ 的自由幺半群. 约定 $A^0 = \{\epsilon\}, A^1 = A, A^{i+1} = \{wv : w \in V^i, v \in V \}$, $i \ge 1$. 同样的, 如果 $A$ 是一个字母表或形式语言, $A^i$ 收集的就是所有长度为 $i$ 且字符属于 $V$ 的字符串. 于是 $A^*$ 也可以定义成如下形式

$$ A^* \eqq \bigcup_{i \ge 0} A^i $$

从直觉上说, $A^*$ 是为了刻画 $A$ 的零次或多次重复. 如果读者熟悉正则表达式, 那么显然此处的 $\cup$ 就是 $+$ 的别名, 对应匹配器的或运算, 于是我们也用 $+_\Sigma$ 表示 $\cup$. 注意这里的 $\cup$ 有无穷多个, 从这个定义可以直接看出 $(A^*)^* = A^*$, 这样一来, $\square^*$ 就会是一个幂等运算.

可以验证, 正则语言集 $\textbf{Reg}_\Sigma$ 连同其上的加法 $+_\Sigma$ 和乘法 $\times_\Sigma$ 构成一个半环 $(\textbf{Reg}_\Sigma, +_\Sigma, \times_\Sigma, 0_\Sigma, 1_\Sigma)$. 从匹配的角度, 我们还能明白以下两点为何是必须的.

$\quad (i)~$ 加法单位 $0_\Sigma$ 对于乘法运算 $\times_\Sigma$ 的吸收性.
$\quad (ii)$ 加法 $+_\Sigma$ 是幂等运算, 即 $a+a = a$.

现在, 从半环 $(\textbf{Reg}_\Sigma, +_\Sigma, \times_\Sigma)$ 出发, 在其上定义偏序 $a \le b$ $\iff$ $a+b=b$, 等价地 $\exists ~ x$ 使得 $a+x = b$. 最后, 可以验证 $\square^*$ 与定义的偏序还满足下面的公理.

$$ \begin{aligned} (1) &~~ 1+aa^* \le a^* \\ (2) &~~ 1+a^*a \le a^* \\ (3) &~~ ax \le x \implies a^* x \le x \\ (4) &~~ xa \le x \implies xa^* \le x \end{aligned} $$

这使 $\textbf{Reg}_\Sigma$ 成为 Kleene 代数 $(\textbf{Reg}_\Sigma, +_\Sigma, \times_\Sigma, \square^*)$. 反过来, 按照公理化定义的顺序, 从正则语言集的性质 $(1)\sim(4)$ 能够直接得出 Kleene 星运算 $\square^*$ 的定义, 正则语言集本身就是 Kleene 代数的一个模型. Kleene 代数的另一个简单例子是 Boole 代数, 其中的 $a^* = 1$. 而热带半环尽管有幂等加法, 但可以验证它并非 Kleene 代数.

Exegesis. 关于半环的注释 [semiring]

May 9, 2024
kokic

$\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$ $\gdef\Q{\mathbf{Q}}$ $\gdef\R{\mathbf{R}}$ $\gdef\C{\mathbf{C}}$ $\gdef\Mat{\operatorname{Mat}}$

半环取消了环中加法逆的存在, 仅仅从定义上来看, 可能很难认识到半环的作用, 并轻率地认为半环是一种性质不够好的结构, 哪怕考虑一些具体的例子如布尔代数和 $\N$ 也难以影响这样的印象. 但是人们对于环的印象就完全不同, 因为环总是与域紧密关联着, 为此人们可能会列举出下面的证据:

$\quad (i)$ 整数环 $\Z$ 处于数论研究的中心位置, 它的分式域是有理数域 $\Q$, 这种构造适用于任何整环 $R$, 通过商 $(R \times R \smallsetminus \{0\})/\sim$ 来完成, 此处 $(a,b) \sim (c,d) \iff ad = bc$. 从域 $\Q$ 出发, 构造以它为系数的多项式, 这些多项式将形成一个新的环结构 $\Q[x]$. 现在我们从中取一个不可约多项式 $p(x)$, 然后再利用 $\Q[x]$ 对 $p$ 生成的理想 $(p)$ 的商, 于是我们又得到一个新的域 $\Q[x]/(p)$. 另一方面, 记 $p(x)$ 在商环中的一个根为 $r$, 能够验证 $\Q[r] \cong \Q[x]/(p)$. $\Q[r]$ 的重要之处在于, 它是包含 $\Q$ 和 $r$ 的最小的域. 如果我们把这个步骤中的 $\Q$ 换成 $\R$ 并让 $p(x) = x^2+1$, 我们就得到了 $\C$.

$\quad (ii)$ 同样从域 $\Q$ 出发, 另一种从域中产生环的方法是考虑以它为元素的矩阵. 类似的, 所有的这些矩阵构成矩阵环 $\Mat(\Q)$. 不同于一般是交换环的多项式环, 矩阵环往往非交换. 仅从统计的意义上说, 在数学之外的领域, 恐怕很少有什么结构能够比矩阵更为重要.

现在请回忆, 正如我们可以把 $(i)$ 当中用于构造多项式环的域 $\Q$ 更换为一般的交换环 $R$, 这个时候 $R[x]$ 仍然是交换环. 当我们把 $(ii)$ 的域 $\Q$ 更换为半环 $\mathcal{Q}$ 时, $\Mat_{n \times n}(\mathcal{Q})$ 能够恰好地成为半环. 这个事实导致了半环上能够操作相当一部分的线性代数, 并且在很多场景下激发了半环结构的用途 ¹. 另外值得注意的一点是, 矩阵半环上可以通过 Leibniz 律定义导子.

例如: 求解最短路径问题的 Floyd 算法, 计算 Boole 矩阵传递闭包的 Warshall 算法, 求逆矩阵的 Gauss–Jordan 消元, 以及 Kleene 对 “每个正则语言都可被正则表达式定义” 的证明.

Definition. 星半环 [star-semiring]

May 9, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$

$\gdef\Q{\mathbf{Q}}$ $\gdef\R{\mathbf{R}}$

仅仅只是为半环添加闭包或者说 Kleene 星运算, 所得到的结构称为星半环. 与 Kleene 代数类似, 星半环也通过递归公理定义星运算. 但是 Kleene 代数所要求的幂等加法对于很多数字系统如 $\Q, \R$ 而言都难以实现, 因为这破坏了 Archimedes 性. 如果我们取消幂等加法这一点, 此时所得到的结构是完备星半环或称为闭半环, 因为 Kleene 代数本身还允许了无穷和 $\sum_{i \ge 0}a^i$ 以及 $a^*$ 的存在性, 这就是称它 “完备” 或者 “闭” 的原因.

下面来介绍一个重要的例子. 非负扩展实数集 $\R_{\ge 0} \cup \{\infty\}$ 也即 $\R_{\ge 0}$ 的单点紧化连同实数的通常加法和乘法构成闭半环, 其中 $a \ne 1$ 时 $a^* = \frac1{1-a}$, 否则 $a^* = \infty$. 注意这个结构中不存在非零的加法逆 $-a$, 而乘法逆 $a^{-1}$ 则是未必存在. $\frac1{1-a}$ 应当被认为是一个整体记号, 或者说它实际上是无穷和 $1 + a + a^2 + \cdots$ 在 $\R_{\ge 0}$ 被添入全体非零加法逆 $\R_{\lt0}$ 后所得的环 $\R$ 中于 $(-1,1)$ 处收敛的结果. 然后由于

$$ \R_{\ge 0} ~ \cap ~ \{a < 1 : a \in \R_{\ge 0}\} \quads= [0, 1) \spaces\subset (-1,1) $$

从而在闭半环的 $a<1$ 处继续沿用这个记号. 这样, 一旦当我们扩大到环 $\R$ 时, 闭半环 $\R_{\ge 0} \cup \{\infty\}$ 当中得出的结果仍然有效. 我们在这里要求 $\R_{\ge 0} \cup \{\infty\}$ 还有另一个原因, 如果对所有 $a$ 都定义 $a^* = \frac1{1-a}$, 那么 $a^{***} = a$, 即 $\square^*$ 是 $3$-幂等的运算, 这会让 Kleene 闭包和正则表达式的概念无从谈起.

我们的论证可以直接拓展到一般的闭半环 $(\mathcal{Q}, +, \times, \square^*)$. 当其中的半环 $(\mathcal{Q}, +, \times)$ 被替换为环 $(R, +, \times)$ 时, 如果 $R$ 当中的 $\frac1{1-a}$ 在 $\mathcal{Q}$ 当中存在, 则 $\mathcal{Q}$ 当中的 $a^*$ 对应于 $R$ 当中的 $\frac1{1-a}$. 当然, 隐含的条件是, $R$ 的加法和乘法与 $\mathcal{Q}$ 兼容.

Exegesis. 矩阵闭包 [amtx-2A]

May 10, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\Mat{\operatorname{Mat}}$ $\gdef\R{\mathbf{R}}$ $\gdef\str#1{{\footnotesize #1}}$ $\gdef\sstr#1{~{\footnotesize #1}~}$

记 $\R_{\ge 0}^* = \R_{\ge 0} \cup \{\infty\}$. 从现在起, 我们对于 $\R_{\ge 0}^* ~ (= \mathcal{Q})$ 当中的许多有用的观察可以安全地转移到 $\R ~ (= R)$. 根据半环注释, 我们优先考虑 $\Mat_{n \times n}(\mathcal{Q})$, 从最小的非平凡情况 $n=2$ 开始, 由于我们的目的是计算矩阵的逆, 故取这个半环的可逆子集也即幺半群 $\Mat_{n \times n}(\mathcal{Q})^\times$, 其中的元素会形如

$$ M \spaces= \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \quad ad - bc \spaces\neq 0 $$

请注意, 接下来应该考虑的是 $\square^*$. 因为我们要利用 $X^* = \frac1{1-X}$ 这个关系间接地计算 $M^{-1}$. 只要取 $X = 1-M$, 我们就得到了

$$ (1-M)^* \spaces= \frac1M \quad (= ~ M^{-1}) $$

此处的 $1-M$ 非常微妙, 因为一般情况下它只能存在于 $\Mat_{n \times n}(R)$ 而非 $\Mat_{n \times n}(\mathcal{Q})$. 如果我们暂时忽略这个问题, 那么根据半环注释, 由于矩阵的加法直接就是 $\mathcal{Q}$ 或者 $R$ 的加法, 而乘法来自线性空间. 此时 $M$ 与 $M^*$ 之间存在一种直接的关系, 可以说成 $(M^*)_{ij} = $ 有向图 $G$ 中所有 $i \to j$ 的路径.

具体的说, 固定下标 $i,j$, 分量 $(M^*)_{ij}$ 的值会等于以 $M$, $M^*$ 为结点, $M_{ij}$ 为箭头的 $G$ 中所有 $i \to j$ 的路径 $\hom(i,j)$ 的正则表达式. 并且从这些路径中我们也能够写出 $\hom(i,j)$ 对应的正则表达式, 这就为计算 $(M^*)_{ij}$ 提供了可能.

$$\begin{aligned} 1 \longrightarrow 1 &: \quad (a+b d^*c)^* \\ 1 \longrightarrow 2 &: \quad (a+b d^*c)^*b d^* \\ 2 \longrightarrow 1 &: \quad d^* c(a+b d^*c)^* \\ 2 \longrightarrow 2 &: \quad d^* + d^*c(a+b d^*c)^*b d^* \\ \end{aligned}$$

简单起见记 $\alpha = (a+b d^*c)^*$, 那么上一段的讨论就是在说

$$ M^* \spaces= \begin{pmatrix} \alpha & \alpha b d^* \\ d^* c \alpha & \quad d^* + d^*c \alpha b d^* \tag{1.1} \end{pmatrix} $$

这里有两个不应忽视的问题. 其一, 虽然我们考虑的是 $\Mat_{n \times n}(\mathcal{Q})$ 上的 Kleene 星运算 $\square^*$, 但右侧的表达式中涉及了 $\mathcal{Q} ~ (= \R_{\ge 0}^*)$ 上的 Kleene 星运算 $\square^*$, 根据之前的内容, 我们可以自然地确定它就是 $a \mapsto \frac1{1-a}$. 这允许我们从 $M$ 的各个分量 $M_{ij}$ 计算出 $M^*$. 更加重要的是, 由于 $\Mat_{n \times n}(\mathcal{Q})$ 也能通过这样的方式构成闭半环, 这实际上允许我们将 $(1.1)$ 的适用范围拓展到任意大小的方阵 $\Mat_{n \times n}(\mathcal{Q})$, 此时的 $a,b,c,d$ 能够选取为 $M$ 的分块矩阵. 其二, $d^* + d^*c \alpha b d^*$ 在一般的星半环中不能直接替换为 $(d+ca^*b)^*$, 可替换的前提被称为 Conway 条件.

Example. 二阶矩阵的逆 [amtx-3A]

May 9, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

作为热身运动, 我们现在来恢复一个经典的事实, 即二阶矩阵的逆. 对于二阶可逆矩阵 $M$, 其逆 $M^{-1}$ 可以由它的四个分量 $a,b,c,d$ 经由 $M \to 1-M \to (1-M)^*$ 这样的过程得到, 这里 $1$ 当然是单位矩阵.

$$ \begin{aligned} M^{-1} &\spaces= (1-M)^* \\ &\spaces= \begin{pmatrix}1 - a & -b \\ -c & 1 - d\end{pmatrix}^* \\ &\spaces= \begin{pmatrix} (1 - a + b(1-d)^*c)^* & \quad \cdots \quad \\ \quad \cdots \quad & \quad \cdots \quad \end{pmatrix} \\ &\spaces= \frac{1}{a d - b c} \begin{pmatrix}d & -b \\ -c & a\end{pmatrix} \end{aligned} $$

Example. 分块矩阵的逆 [amtx-3B]

May 10, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

我们下面来处理 $n \times n$ 矩阵 ($n \ge 3$) 的逆, 将其分块并假定后续要取逆的矩阵都是非奇异的

$$ M \spaces= \begin{pmatrix} A & B \\ C & D \end{pmatrix}, \quad 1-M \spaces= \begin{pmatrix} 1-A & -B \\ -C & 1-D \end{pmatrix} $$

我们还是直接计算 $(1-M)^*$, 实际上这非常容易. 回顾 $M^*$

$$ M^* \spaces= \begin{pmatrix} (A+BD^*C)^* & (A+BD^*C)^*BD^* \\ D^*C(A+BD^*C)^* & D^* + D^*C(A+BD^*C)^*BD^* \end{pmatrix} $$

类似的记 $\alpha_\square$ 为方阵 $\square$ 分为 $4$ 块后的左上角第 $1$ 部分. $\alpha_{M^*} = (A+BD^*C)^*$, $\alpha_{M^{-1}} = \alpha_{(1-M)^*}$, 则

$$ \begin{aligned} \alpha_{M^{-1}} &\spaces= (1 - A + B(1-D)^*C)^* \\ &\spaces= (1 - A + BD^{-1}C)^* \\ &\spaces= (1 - (A - BD^{-1}C))^* \\ &\spaces= (A - BD^{-1}C)^{-1} \end{aligned} $$

同样, 考虑分块的其他部分

$$ \begin{CD} M @>>> 1-M \\ @VVV @VVV \\ M^* @>>> (1-M)^* \end{CD} $$

在 $M \to 1-M$ 这个箭头下, $M$ 当中所有的 $D$ 会被替换为 $1-D$, 因此 $M^*$ 当中所有的 $D^*$ 可以直接替换为 $D^{-1}$. 而 $B, C$ 在 $M \to 1-M$ 下替换为 $-\square$, 于是现在立刻有

$$ \begin{aligned} M^{-1} &\spaces= \begin{pmatrix} \alpha_{M^{-1}} & -\alpha_{M^{-1}} BD^{-1} \\ -D^{-1}C \alpha_{M^{-1}} & D^{-1} + D^{-1}C \alpha_{M^{-1}} BD^{-1} \end{pmatrix} \\ &\spaces= \begin{pmatrix} (A - BD^{-1}C)^{-1} & -(A - BD^{-1}C)^{-1} BD^{-1} \\ -D^{-1}C (A - BD^{-1}C)^{-1} & D^{-1} + D^{-1}C (A - BD^{-1}C)^{-1} BD^{-1} \end{pmatrix} \\ \end{aligned} $$

在这里, 我们得到了一个相当经典且重要的结果, 即分块求逆.

Daily Surf [daily-surf]

Bevy 备注 [bevy]

August 29, 2025
kokic

E0786

error[E0786]: found invalid metadata files for crate `serde`                               
  --> C:\Users\...\.cargo\registry\src\...\bevy_math-0.16.1\src\ray.rs:60:42
   |
60 | #[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]      
   |                                          ^^^^^^^^^^^^^^^^
   |
   = note: failed to mmap rmeta metadata: '\\?\D:\...\target\release\deps\libserde-f884fbba2cdca77e.rmeta'
   = note: this error originates in the derive macro `serde::Serialize` (in Nightly builds, run with -Z macro-backtrace for more info)

如果在 Windows 设备上 cargo build --release 时遇到这个错误, 那很可能是 Windows 的路径长度限制所致 ¹. 管理员身份运行如下 Powershell 命令即可启用长路径支持.

New-ItemProperty -Path "HKLM:SYSTEM\CurrentControlSet\Control\FileSystem" -Name "LongPathsEnabled" -Value 1 -PropertyType DWORD -Force

另见 Registry setting to enable long paths - Microsoft Learn.

In the Windows API (with some exceptions discussed in the following paragraphs), the maximum length for a path is MAX_PATH, which is defined as 260 characters.

Poetry. Adams 谱序列 [adams]

August 21, 2025
Yuniversal Y. Creeper 🥐

每个人都是独一无二的笨蛋

看到独一无二的宿命, 向另一个笨蛋提枪冲锋

死去, 照耀着独一无二的光荣

Sublime Text 4 高分屏设置 [sublime-text-config]

February 21, 2025
kokic

装好 PackageDev ¹ 包后, 修改主题文件如 Default.sublime-theme 即可.

侧边栏字体大小

"class": "sidebar_label",
"fg": "var(sidebar_label)",
"font.face": "var(font_face)",
"font.size": "var(font_size)"  // line 264

侧边栏文件树条目 padding

"class": "sidebar_tree",
"platforms": ["windows"],
"row_padding": [6, 5, 4, 5],  // line 226

文件 Tab 字体大小

"class": "tab_label",
"font.face": "var(font_face)",
"font.size": "var(font_size_lg)",  // line 938

PackageResourceViewer 这个包也能用, 不过相对而言太旧了.

Sagemath Jupyter 主题设置 [sagemath-theme]

February 17, 2025
kokic

如果你是一个没有定制化需求的 Sagemath 用户或者单纯地使用 Jupyter Notebook 连接一些与 Sagemath 无关的服务, 你遇到本文所关心问题的可能性是很低的, 这个主要有以下两个原因.

Sagemath Jupyter Notebook 在 Visual Studio Code 上几乎不能使用. 这是因为, 所有由 MathJax 提供渲染的公式都无法呈现, 甚至连 Cell 也不出现. 于是最稳妥的做法就变成了使用浏览器访问 Jupyter Notebook.
Jupyter Notebook 的主题设计非常混乱, 常用主题位于 jupyterthemes 包, 但是这个包的文档和使用示例并不适用于 Sagemath.

这两点使得问题看上去不太容易. 因为一般的, 如果用户使用 Visual Studio Code 访问 Jupyter Notebook 就完全不需要担心主题问题, 于是相应的可能在互联网上存在的解决方案就会变少. 关于第二点, 如果尝试在 Jupyter Notebook 当中执行下面这样的程序

from jupyterthemes import get_themes, jtplot
import jupyterthemes as jt
from jupyterthemes.stylefx import set_nb_theme

set_nb_theme('monokai')

确实能够切换到 monokai 主题, 同时你还会发现当前使用的 Jupyter Notebook 的 Header 和 Toolbar 消失了 ¹. 如果你尝试检索相关信息, 你会在 jupyterthemes 的文档中找到像是

jt -t monokai -T -N

这样的做法, 这里的 -T 是 Toolbar Visible, -N 是 Name & Logo Visible. 然后遗憾地发现这不会对 Sagemath 的 Jupyter Notebook 造成任何作用. 同时, 这样的设置也是临时的, 如果希望将某个特定的主题作为默认主题, 就得另谋他法.

最直接的方法是, 找到像下面这样的编译后的样式文件

sagemath/runtime/opt/sagemath-9.3/local/lib/python3.7/site-packages/jupyterthemes/styles/compiled/monokai.css

然后覆盖到

<SAGE_HOME>/.sage/jupyter-4.1/custom/custom.css

这样你就得到了一个永久生效的样式设置. 随后可以通过修改 div#maintoolbar 和 #header-container 的 display 为 block 重新显示这两个组件. 修改 .MathJax 的 font-size 为 120% 或者更大则能够增大渲染后公式的字号.

$\textbf{Remark.}$ 一个无关正文的冷知识: 如果你需要带完整头文件的 C / C++ 编译器, 但还没安装 GCC 或者 Clang, 那 sagemath/runtime/bin 目录下就有一个, 头文件位于 sagemath/runtime/usr/include.

从编译后的样式文件中我们可以看到, div#maintoolbar 和 #header-container 确实被设置为了 display: none.

Git 过滤分支 [git-filter-branch]

February 15, 2025
kokic

一个常见的需求是对已经存在的 git commit 历史作出修改. 如果目标 commits 都存在于本地分支, 那么一组 rebase 就能解决问题. 但若是要修改已经推送至远程仓库或托管平台 ¹ 则没有一步到位的操作, 且对于真实的多人协作仓库来说, 这么做的潜在危害远高于修改 commits 历史所得到的短期好处 ². 因此, 接下来的讨论都是以接受 “潜在危害” 这一点作为前提而进行的.

这里只说方法. 即便对于已经提交的 commit, 其修改仍然可用 rebase. 但此时不能直接推送, 我们需要额外做一步 filter-branch.

git filter-branch --force

filter-branch 配合 replace 或者 <GIT_DIR>/info/grafts 也能够用来快速清除某次 commit 之前的所有记录. grafts 文件内是 commit 的 hash 值, 可以通过 git log 查询.

注意, grafts 目前已经被标记为 deprecated, 不过依旧可用.

hint: Support for <GIT_DIR>/info/grafts is deprecated
hint: and will be removed in a future Git version.
hint:
hint: Please use "git replace --convert-graft-file"
hint: to convert the grafts into replace refs.
hint:
hint: Turn this message off by running
hint: "git config advice.graftFileDeprecated false"

如 Github, GitLab, SourceHut, Codeberg 等.

这就是为何你应该对每个任务都开新的分支, 同时在每次正式推送之前都 rebase, 来避免污染主分支的 commit 树.

Exegesis. 日经观点 [baby-viewpoint]

February 11, 2025
kokic

$\gdef\Mat{\operatorname{Mat}}$ $\gdef\vol{\operatorname{vol}}$ $\gdef\diag{\operatorname{diag}}$ $\gdef\d{\operatorname{d}}$ $\gdef\R{\mathbf{R}}$ $\gdef\Q{\mathbf{Q}}$

一个矩阵 $A \in \Mat_{n \times n}(\R)$ 所确定的线性映射 $\alpha: \R^n \to \R^n$ 作用在 $X \in \R^n$ 上, 此映射对 $X$ 的 (有向) 体积 $\vol(X)$ 的缩放量为 $\det A$. 即 $\vol(\alpha X) = \det A \cdot \vol(X)$. 特别地取 $A = \diag(a,b)$, 然后乘单位圆 $u^2+v^2=1$ 上一点构成的向量 $(u,v)$, 得到满足椭圆方程 $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ 的 $(x,y)$, 这样便能看出椭圆的面积 $S = \det A \cdot \pi$.
设 $\omega$ 是一个 $k$-形式, 它的两次微分 $\d(\d \omega) = 0$. 另一方面, 考虑一个有向流形 $\Omega$ 和它的边缘 $\partial \Omega$, 我们知道 $\partial(\partial M) = \varnothing$. 这两件事相互对偶.
考虑数域 $K=\Q(\alpha_1, \cdots, \alpha_i)$ 的一个存在于上的历史原因是, 在适当的 $K$ 中考虑能够使原本在 $\Q$ 上无法分解的 Diophantus 方程因式分解. 如 $\Q(\sqrt{-7})$ 能使 Ramanujan–Nagell 方程 $x^2=2^n-7$ 改写为 $(x+\sqrt{-7})(x-\sqrt{-7})=2^n$. Fermat 方程 $x^n+y^n=z^n$ 能够在 $\Q(\zeta_n)$ 上分解成 $x^n=(z-y)(z-\zeta_n y) \cdots (z-\zeta_n^{n-1} y)$, 这是 Kummer 提出理想数概念的一个原因.

Fibonacci 抛硬币 [fibonacci-flip]

January 24, 2025
kokic

抛一枚硬币 $n \ge 2$ 次且从不连续出现正面, 这样的可能共有 $F_{n+2}$ 种, 这里的 $F_{n+2}$ 是从零开始的 Fibonacci 数列. 我们把抛 $n$ 次不连续出现正面的可能数记为 $S_n$, 考虑相邻的两次抛硬币, 假设第 $i$ 次掷硬币为正面, 则第 $i+1$ 次掷硬币只能是反面, 这个时候的所有可能为 $S_{n-2}$. 假设第 $i$ 次掷硬币为反面, 则第 $i+1$ 次掷硬币的结果可任意. 因此 $S_n = S_{n-1} + S_{n-2}$, 再利用初值 $S_1$, $S_2$ 就能解出 $S_n$.

屏幕右上角的 “FPS GPU CPU 延时” [nvidia-fps-gpu-cpu]

January 9, 2025
kokic

根据这个 Reddit 问题.

首先这项功能来自 Nvidia Overlay, Intel 用户可以通过 Alt+R 开启这个 “PC 统计数据”¹ AMD 则是 Ctrl + Shift + O. 目前看来这个信息会出现在安装了 Nvidia APP (Beta) 或者 GeForce Experience 程序的设备上.

我们姑且按照该 Reddit 问题的某个回答这么称呼此信息.

Wolfram 引擎与 WLJS [wolfram-engine]

July 29, 2024
kokic

Wolfram 把 Mathematica 的内核 Wolfram Engine 单独拆出来并作为免费软件 ¹ 提供已不是什么新鲜事. 如不考虑实际的交互体验, 至少对于开发者而言, 为最新版 Mathematica 付费这件事基本就意味着只购买了个带官方服务支持的 Wolfram Notebook.

Wolfram 引擎能直接使用 Homebrew 或 winget 等包管理器安装, 命令行功能由引擎自带的 Wolfram Script 提供. 虽然能用, 但可想而知体验不会太好. 最早的一个方案是用 Visual Studio Code 和相关 Notebook 插件连接到 Wolfram 引擎, 这样一来比起纯命令行能好上不少, 但是对于习惯了 Mathematica 官方笔记本的用户来说还差点意思.

要是用户不在乎多装一个浏览器以此换来更好的 Notebook 体验, 那么开源的 WLJS 会是一个可供考虑的选择. Augsburg 大学的物理学家 Kirill Vasin 在 2023 年 11 月 16 日发布了 WLJS 的第一个长期版本 ². WLJS 这几个字母是 Wolfram JS Frontend 的缩写, 从技术上说, 它是一个 Electron APP, 如果用户的目的是对于 Mathematica 功能有高度依赖的科研用途, 那么多装一个浏览器的代价自然算不了什么. 另外 WLJS 的引导部分做的很不错, 也有不少很有意思但是 Wolfram Notebook 不具备的功能.

Windows 上的 Wolfram Engine 安装完成之后能占用大约 6.5GB 的磁盘空间. 比起 Sagemath 还是大了不少.

The immortal edition.

文件互传 [file-transfer]

May 18, 2022
kokic

因为各种读者可以想象的原因, 基于网络的面对面文件互传其实是一件经常会遇到的事. 笔者先后尝试过依赖于特定品牌的互传功能, 但时不时会遇到因未知原因导致的传输无法开始的问题. 索性另求他法.

我们假设有设备 $A$, $B$, 且 $A$ 将要发送文件 $F$ 给 $B$, 另可设文件 $F$ 充分大 (如 $\geqslant 1 \text{GB}$). 方案如下.

$B$ 联网且开热点, $A$ 连接热点. 随后 $A$ 通过 Termux + miniserve 或其他等效软件在文件 $F$ 所在目录开启本地 HTTP 服务器, 记下 IP. $B$ 使用浏览器访问 IP, 下载文件即可, 此时下载速率依赖于 $B$ 连接到的网络.

翠玉录 [smaragdina]

Lynch 对于人们说 “你的电影没有意义” 的回应 [lynch-movie]

February 21, 2025
David Lynch
Youtube

I think I love ideas. I like a story that’s got some concrete you know structure but also holds abstractions. Life is filled with abstractions and the way we make heads tails of it is through intuition. And so people get used to film that pretty much explains itself a hundred percent. And they kind of turn off that you know beautiful thing of intuition when they’re looking at a film that has some abstractions. And some people on the other hand love these abstractions. And it gives them room to dream.

A abstractions to me is a thing that cinema can say. And it’ so beautiful for me anyway to think about these pictures and some sounds flowing along together in the time in a sequence making a thing that can only really be said in cinema. It’s not words. It’s not just music. It’s the whole bunch of things coming together and making a thing that didn’t exist before. And that’s what i really love about it.

And then to answer your question a little further. It’s up to the people you know to you know find their own your know interpretation. It’s doesn’t really matter what I think. It’s all every screening no matter what even if all the frames of the film are exactly the same. But there no two screenings that are exactly the same. It’s the viwer and the picture and the sound and it makes a circle and it just goes like that. And so you just feel it and think it. That’s kind of intuition emotion and thinking together and come up make it have a sense to you.

译: 我想我钟爱的是理念本身. 我喜欢那种既有具象结构又蕴含抽象思维的故事. 生活本就充满抽象, 而我们理解它的方式就是通过直觉. 人们已经习惯了那些将一切解释得明明白白的电影, 当看到带有抽象元素的影片时, 他们往往会关闭那种美妙的直觉感知. 而另一些人却恰恰痴迷这种抽象, 因为这给了他们造梦的空间.

对我而言, 抽象正是电影独有的表达方式. 当画面与声音在流动的时间中交织, 形成唯有电影才能言说的意境 $—$ 这不是文字能描述的, 也不仅是音乐能呈现的, 而是所有元素共同创造出前所未有的存在 $—$ 这种构想本身就已美得令人心醉.

进一步回答你的问题: 观众完全可以根据自己的理解来诠释作品. 我的想法其实无关紧要. 每一次放映都是独特的相遇, 即便胶片帧数分毫不差, 但银幕光影与观者感受却不可重现. 这种循环生生不息, 你只需去感受, 去思考, 让直觉情感与理性交融, 最终形成属于你自己的体验.

The Celtic Myths 摘录 [celtic-myths]

February 21, 2025
kokic
豆瓣

中译版很烂, 所以引的是原文.

The preface to the 1957 edition of Jorge Luis Borges’ collection of essays The Book of Imaginary Beings (幻兽辞典) contains the comment that monsters will always stalk mythic stories because real animals are a deeply important part of human experience and because monstrous beings are combinations of the real and the imagined, the stuff of nightmares and dreams. The Classical mythic centaur, which melds the forms of man and horse, has its Celtic counterpart in the Welsh horse-woman, Rhiannon. The Cretan Minotaur (米诺陶洛斯), a hideous blend of bull and human, can perhaps be seen transmuted in Irish mythology to become the great fighting bulls of Ulster and Connacht, which had human speech and understanding, or, in Wales, the enchanted boar Twrch Trwyth (图鲁夫图鲁维斯). Borges even goes so far as to argue that monsters are ‘necessary’ for human society. In our own day, fascinated by space and the possibility of worlds beyond, we conjure up fantastic images of galactic monsters, nowhere more clearly presented than in the Star Wars cantina, in which Skywalker and Solo encounter a collection of weird and wonderful beings from all over the Universe. Such are our modern mythic creations. 26

A persistent feature of both Irish and Welsh mythology is the theme of the magical cauldron, a vessel capable of raising the dead and of providing ever-replenishing supplies of food. The Irish god Daghdha, (‘the Good God’), possessed a huge inexhaustible cauldron. The central focus of the Irish Otherworld feast was the cauldron, which never ran out of food. One Irish cauldron-myth was associated with sacral kingship, where the new king of Ulster had to bathe in one, while consuming the meat and broth of a white mare he had ritually ‘married’. 29

$\S$ Ceridwen’s Cauldron: A Welsh mythic tale, preserved in a 13th-century text, The Book of Taliesin (塔列辛之书), contains a rich story of an enchanted cauldron, whose contents endowed those who ate or drank from it with knowledge and inspiration. The cauldron’s keeper was Ceridwen. She bore two children, Crearwy (‘the light or beautiful one’) and Afagddu (‘black’ or ‘ugly’). Wanting to compensate her son for his ill-favoured appearance, his mother mixed a special brew in the cauldron, designed to give him absolute wisdom. Because the potion needed to boil for a year, Ceridwen appointed a young boy, Gwion, to watch over it. As he was tending the cauldron, three drops of scalding liquid splashed onto his hand and, without thinking, he licked his fingers, thus inadvertently acquiring the wisdom intended for Afagddu. Gwion’s flight and pursuit by the angry Ceridwen eventually caused Gwion’s rebirth as the great visionary poet Taliesin. 30

Words are powerful things, the more so if they are spoken aloud, so that sound and meaning blend into a single powerful message that can be shared simultaneously by many people. Keepers of oral tradition had to have prodigiously long and accurate memories and the ability to learn long tales by heart, while adding embellishments along the way. Listeners, too, would remember stories they had heard all their lives, and would not have hesitated to point out errors or inconsistencies. 43

为民主提供现代定义 — 悼念 F. William Lawvere [mourn-lawvere]

October 28, 2024 — November 2, 2024
kokic

Central Committee, CPC

译者: Kokic Hydrangea

原文: Central Committee, Communist Party of Canada (Marxist-Leninist), Providing Democracy with a Modern Definition. TML MONTHLY, Newspaper of the Communist Party of Canada (Marxist-Leninist). Volume 53 Number 1 - January 2023. https://cpcml.ca/Tmlm2023/Articles/M530010.HTM.

怀着深切的悲痛, 我们谨此告知, 著名数学家 William Lawvere 博士于 2023 年 1 月 23 日与世长辞. Lawvere 教授是加拿大共产党 (马列主义) 的好友, 一位始终秉持人类文明崇高道路的同路人, 致力于对抗并改变社会上的陈旧道德观念, 扫除阻碍进步与启蒙的障碍.

从 1970 年代初开始, 他与 CPC (M-L) [译注: 即 Communist Party of Canada (Marxist-Leninist), 加拿大共产党 (马列主义)] 的创始人和领导人 Hardial Bains 在 “变革的必然性” 与辩证法等哲学及其他项目上展开合作, Hardial Bains 本身就是一位科学家和哲学家. 从 1969 年到 1971 年, 作为 Killam 学者任职于 Halifax Dalhousie 大学, 领导一支享有国际声誉的数学家团队. 但在 1971 年, 当 Lawvere 教授抗议 Pierre Trudeau 颁布《战争措施法》[War Measures Act] 并暂停公民自由、实施种种暴行时, Dalhousie 大学拒绝续聘用他. 尽管其本人领导的数学家团队强烈抗议. 时逾千名学生齐聚 Dalhousie 大学学生会大楼大厅声援劳威尔教授, 反对校方这一专横解雇决定.

多年来, Lawvere 教授多次在加拿大与我们一起讨论重要议题, 并以他深厚广博的学识作出卓越贡献. 1996 年 2 月, 他在温莎大学举行的主题为 “意识起源和社会变革” [The Origin of Consciousness and Social Change] 的跨学科会议上发表了演讲. 该次会议所提交的论文, 对 “独立于人类之外的意识存在” “冷战史学” “现代民主人格的兴起” 等议题提出了深刻洞见. Lawvere 教授提交的论文为《数学改革的历史和哲学》[The History and Philosophy of Mathematic Reform], 该论文剖析了当时一种限制数学科学知识传播的教学趋势, 并指出除其他关切外, 这种趋势如何有效地助长了神秘主义与对权威的盲目服从.

1997 年, 他与来自世界各地的学者一起参加了 Bains 同志的葬礼. 他还参加了 1998 年的 CPC (M-L) 第七次代表大会, 会上他对 Hardial Bains 的工作表示赞赏, 并对大会讨论的论纲作出了贡献. 2005 年, 他参加了党的 35 周年庆典, 再次表达了对党在理论和现代定义方面的工作的赞赏. 他后来写道, 35 周年纪念日 “是一个非常有意义的时刻. […] 特别是, 这一场合使我的工作取得了进一步的进展, 特别是为纪念列宁哲学著作一百周年的项目, 详细介绍了它们如何从自然科学的角度以及从为启蒙而进行的阶级斗争的角度, 成为研究 19 世纪和 20 世纪哲学发展的有用指南. 自从 35 年前 Hardial 指出这些书的重要性以来, 它们一直是我的伴侣. […]”

获悉 Lawvere 教授逝世的消息后, 他的长期伙伴 Eric Hoffman 在感谢 Hardial Bains 和 Bill Lawvere [译注: 即 William Lawvere] 对他自己的生活和工作产生的深远影响时说:

“他们各自在1960年代早期所开展的开创性工作, 如今交汇出一种崭新而令人惊讶的关联, 其最强有力的证据已然显现. 这种关联是人类与自然之间复杂关系网络的一个组成部分. Bill 说, 这一复杂整体所具有的客观性, 迫使我们必须坚定不移地关注对空间与数量的研究.

“在他博客上的一次采访中, Bill 说, ‘数学理论的核心, 在于空间中数量的变化, 以及在这种变化中质的飞跃.’ 无论考虑的是几何学、范畴、逻辑、政治形态的转变、亲属关系亦或其他领域, Bill 始终印证着对立面的统一与同一, 即辩证法的真实存在.

“Bill 的工作将作为扩大启蒙空间的贡献而经久不衰.”

在 CPC (M-L) 中央第一书记发给 Lawvere 教授家人的哀悼信中, 她写道:

“Bill 在他的一生中做出了如此多的贡献, 我们非常感激. 他对发现新事物的热情和奉献精神总是令人鼓舞. 他的方法总是充满活力、专注、在许多方面都很新鲜. 他作为教师的耐心、他的论点的智慧和连贯性、他对年轻一代和教化他们的热情, 以及他对文明崇高道路的勇敢坚持, 都非常出色.

“与 Bill 会面总是非常高兴. 我们将永远珍惜他的友谊、慷慨的精神和对我们共同事业的奉献精神, 他为此毫不畏惧地大声疾呼. 这正彰显了他非凡的品格.

为展示 Lawvere 教授作为数学教育者的风范, 其对问题直截了当的阐释方式, 以及对所有对其工作感兴趣者开放坦诚的讨论态度, 我们谨举一例: 他曾应请求就 “为何范畴论可能如此有用” 提供一个宽泛的论证. 以下是比尔的回答:

人类的日常活动, 如在溪流旁的山上建造房屋、铺设电话管道网络、在太阳系中航行, 都需要可行的计划. 规划任何此类工作都需要发展对空间的思考. 每个发展都涉及许多思考步骤和许多相关的空间几何结构. 由于思考空间的必要多步骤性质, 必须采取独特的数学措施来使其可靠. 只有明确的思维原则 (逻辑) 和明确的空间原则 (几何) 才能保证可靠性. Eilenberg 和 Mac Lane 60 年前发明的理论所取得的巨大进步使逻辑和几何学的原则变得明确; 他们通过发现逻辑与几何的共同形式, 使得二者之间的关系原则也变得清晰可见. 他们解决了亚里士多德在 2300 年前提出的一个问题, 即初步尝试将 “概念的范畴” 显式化. 在 21 世纪, 他们的解决方案不仅适用于平面几何和中世纪三段论, 还适用于无穷维变换空间、数据 “空间” 以及其他每日被成千上万次应用的概念工具. 范畴学家发现, 逻辑与几何原则的形式, 根植于空间之间变换以及空间内部变换的 “自然性” 之中.

下文附上 Lawvere 教授逝世时发表的讣告 [译注: 讣告和后文的传真件等内容请前往原文查看.]. 我们添加了 1971 年 1 月 22 日《达尔豪斯公报》[Dalhousie Gazette] 上关于他被 Dalhousie 大学开除的文章的传真件. 我们还提供了 Lawvere 博士在 1996 年 2 月 9 日至 11 日在温莎大学举行的关于意识起源和社会变革的跨学科会议上发表的题为 “数学教育改革的历史与哲学” [The History and Philosophy of Mathematic Reform] 的论文. 最后, 我们还提供一段 Lawvere 博士的访谈, 其中他亲自阐释了自己的学术工作.

我们向 Bill 的终身伴侣与合作者、他的子女、孙辈、兄弟姊妹, 以及无数朋友与同事致以最深切的哀悼. 愿他们从共同创造的美好回忆中获得慰藉.

冒泡排序合成置换分解 [bubble-compose]

December 26, 2024
kokic
Pearls

任意置换 $\sigma$ 都可被写成若干个对换之积. 这里, 集合 $X$ 上的置换是指 $X$ 到 $X$ 的双射. 而对换 $(i ~ j)$ 则是交换元素 $i,j$ 位置的映射.

Proof. (笔者) [bubble-compose-pf]

December 27, 2024
kokic

冒泡排序使用若干次对换将 $X$, $Y$ 打到有序列表 $Z$, 把这些对换之积复合出的两个映射记为 $\sigma_X, \sigma_Y$. 现在观察下图, 写出 $\sigma_Y^{-1}\sigma_X$, 这当然就是 $\sigma$.

Problem. 古代物理学博士问题 [canterbury-2A]

December 26, 2024
kokic
Pearls

$\gdef\spaces#1{~ #1 ~}$

有两个正方体, 一个边长为 $1$, 另一个边长为 $2$. 请找到另外两个边长为有理数的正方体使它们的体积总和相同. 换言之, 求下述方程的一组 (正) 有理解.

$$ x^3 + y^3 \spaces= 9 \quad \color{gray}{(= ~ 1^3+2^3)} $$

Solution. [canterbury-2B]

December 26, 2024
kokic

$\gdef\spaces#1{~ #1 ~}$

我们先画出 $x^3 + y^3 = 9$. 然后由已知的 $P=(1,2)$ 出发做切线得到 $2P$, $4P$, $8P$. 这种几乎全凭借运气的操作是 Fermat 及 Viète 研究此类问题的方式.

如图, 随后注意到 $8P$ 恰好位于 $x > 0,y > 0$ 的区域, 现在写出其坐标.

$$ 8P \spaces= \left(\frac{1243617733990094836481}{609623835676137297449}, \frac{487267171714352336560}{609623835676137297449}\right) $$

素数无限多与 Furstenberg 拓扑 [pftb-P005]

$\gdef\Z{\mathbf{Z}}$ $\gdef\PP{\mathbf{P}}$

此证明由 Hillel Furstenberg 于 1955 年提出 ¹, 收录于 PFTB, p. 5, 此页配图的说明文字写道

Pitching flat rocks, infinitely. $\quad$ (掷扁石, 至无穷远.)

对 $a,b \in \Z, b > 0$, 令 $N_{a,b} = \{ a + nb : n \in \Z \}$. 每个集合 $N_{a,b}$ 都是正负无界的算术级数. 如果集合 $O \subseteq \Z$ 满足以下条件之一:

$O$ 是空集.
对任意的 $a \in O$ 存在 $b > 0$ 使得 $N_{a,b} \subseteq O$.

则称 $O$ 是开集. 这些条件保证 $O$ 在 $a$ 点附近 “稠密”. 显然, 开集的并总是开集. 另外, 如果 $O_1$ 和 $O_2$ 开, 则对任意的 $a \in O_1 \cap O_2$, $N_{a,b_1} \subseteq O_1$ 及 $N_{a,b_2} \subseteq O_2$, 都有 $a \in N_{a,b_1b_2} \subseteq O_1 \cap O_2$. 所以开集的有限交也开. 从而此处定义的开集族的确导出了 $\Z$ 上的一个拓扑. 随后, 我们注意:

$(\text{A})$ 每个非空的开集都是无界的, 显然.
$(\text{B})$ 每个 $N_{a,b}$ 都是既开又闭的. 因为 $N_{a,b} = \mathbb{Z} \setminus \bigcup_{i=1}^{b-1} N_{a+i,b}$, 这说明 $N_{a,b}$ 是开集的补, 因而闭.

现在我们引出素数. 对于每个整数 $n \neq 1,-1$ 都有某个素因子 $p$ 使得 $n \in N_{0,p}$ 以及 $\Z \setminus \{\pm1\} = \bigcup_{p \in \PP} N_{0,p}$. 如果 $\PP$ 是有限的, 那么根据 $(\text B)$, $\bigcup_{p \in \PP} N_{0,p}$ 将是有限个闭集的并, 所以是闭的. 进而可以导出 $\{\pm1\}$ 是一个开集, 这与 $(\text A)$ 矛盾, 证毕.

我们回顾证明, 不难发现核心是用拓扑解释 “每个整数都有素因子” 这件事, 进而 $\bigcup_{p \in \PP} N_{0,p} = \Z \setminus \{\pm1\}$ 在 $\Z$ 上稠密, 于是 $\PP$ 绝不可能有限. 此方法实质利用了算术级数的性质, 而非拓扑内涵. 所以也可以翻译成不使用拓扑的版本, 见 Idris D. Mercer 写的 On Furstenberg’s Proof of theInfinitude of Primes.

Furstenberg 当时是 Yeshiva 大学的本科生, 其在美国数学月刊上发表了 “On the infinitude of primes”, 这才有了 Proofs from THE BOOK 对此证明的收录.