« 回声

default

serena

printer

Pearls [pearls][edit]

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

Backlinks

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

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)$.

Theorem. 加减乘除不能解二次方程 [GALA][edit]

October 23, 2021
kokic
Pearls

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

只通过系数的加减乘除不能解一般的二次方程, 换言之, 二次方程的根不是系数的有理函数.

$k$ 是域, $k$ 关于 $t_0,t_1$ 的有理函数域 $k(t_0,t_1)$ 记为 $F$. 下面只需考虑首一多项式 $f(x) = x^2 + t_1x + t_0 \in k[x]$ 且没有重根的情况, 即 $\Delta \ne 0$.

假设存在 $r \in F$ 使得 $f(r) = 0$, 由 Viète 定理 $x_1+x_2 = -t_1$, 另一个根为 $-t_1-r \in F$. 于是

$$ f(x) \spaces= (x-r)(x+t_1+r) \spaces\in F[x] $$

其判别式 $\Delta = (x_1-x_2)^2 = (2r+t_1)^2 \in F$ 是 $F$ 中的平方元. 另一方面, 借助 Viète 定理, 判别式可完全表示为系数的函数

$$ \begin{array}{c|c} \begin{aligned} \Delta &\spaces= (x_1-x_2)^2 \\ &\spaces= (x_1+x_2)^2 - 4x_1x_2 \\ &\spaces= t^2 - 4t_0 \end{aligned} \quad & \quad \begin{aligned} x_1 + x_2 &\spaces= -t_1 \\ x_1x_2 &\spaces= t_0 \end{aligned} \end{array} $$

这就表明 $t^2 - 4t_0$ 是 $F$ 中的平方元.

由于 $F$ 是有理函数域 $k(t_0,t_1)$, 所以知道一定存在一组关于 $t_0,t_1$ 的互质多项式 $p,q \in k[t_0,t_1]$ 使得

$$ \bigg(\frac{p}{q}\bigg)^2 \spaces= t_1^2 - 4t_0 $$

也就是 $p^2 = (t_1^2 - 4t_0)q^2$, 等式两边是 $k[t_0,t_1]$ 中的多项式, 所以 $\Delta$ 整除 $p^2$. 注意 $k[t_0,t_1]$ 是唯一分解整环, 由 $\Delta$ 是不可约多项式知 $\Delta$ 整除 $p$, 因此存在 $p_1 \in k[t_0,t_1] $ 使得 $p = \Delta p_1$. 代入 $p^2 = \Delta q^2$, 因为 $\Delta \ne 0$, 可在整环中消去 $\Delta$, 得

$$ (\Delta p_1)^2 = \Delta q^2 \spaces\implies \Delta p_1^2 = q^2 $$

所以 $\Delta$ 整除 $q^2$. 类似知道 $\Delta$ 整除 $q$. 综上, 非常数多项式 $\Delta$ 整除 $p$ 且 $\Delta$ 整除 $q$, 但这与 $p,q$ 互质矛盾. 故 $\sqrt{\Delta} \notin F$.

如果可约, 则存在两个一次 $k[t_0,t_1]$-多项式, 其乘积为 $\Delta$, 即

$$ \begin{aligned} \Delta &\spaces= (\alpha_1 t_0 + \alpha_2 t_1 + \alpha_3)(\beta_1 t_0 + \beta_2 t_1 + \beta_3) \\ &\spaces= \alpha_1\beta_1 t_0^2 + \alpha_2\beta_2 t_1^2 + (\alpha_1\beta_2 + \alpha_2\beta_1) t_0t_1 + \\ &\kern{1.8em} (\alpha_1\beta_3 + \alpha_3\beta_1)t_0 + (\alpha_2\beta_3 + \alpha_3\beta_2)t_1 + \alpha_3\beta_3 \\ &\spaces= t_1^2 - 4t_0 \end{aligned} $$

于是系数必须满足以下方程组

$$ \begin{equation*} \begin{align} \alpha_1\beta_1 &\spaces= 0 \\ \alpha_2\beta_2 &\spaces= 1 \\ \alpha_1\beta_2 + \alpha_2\beta_1 &\spaces= 0 \\ \alpha_1\beta_3 + \alpha_3\beta_1 &\spaces= -4 \kern{3em} \\ \alpha_2\beta_3 + \alpha_3\beta_2 &\spaces= 0 \\ \alpha_3\beta_3 &\spaces= 0 \end{align} \end{equation*} $$

公式 $(1)$ 表明 $\alpha_1, \beta_1$ 中必有一个是 $0$. 讨论之:

若 $\alpha_1 = 0$, $(3)$ 化简为 $\alpha_2\beta_1 = 0$, 而 $(2)$ 推出 $\alpha_2 \ne 0$, 故只能是 $\beta_1 = 0$, 代入 $(4)$ 得 $0 = -4$, 矛盾.
若 $\beta_1 = 0$, $(3)$ 化简为 $\alpha_1\beta_2 = 0$, 而 $(2)$ 推出 $\beta_2 \ne 0$, 故只能是 $\alpha_1 = 0$. 代入 $(4)$ 得 $0 = -4$, 矛盾.

所以假设的两个一次多项式不存在, $t_1^2 - 4t_0$ 不可约.

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

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} $$

证得这四个命题等价于证明命题 $\eta$, 此处 $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][edit]

May 14, 2019
kokic
Pearls

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

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

Lemma. Young 引理 [YL2B][edit]

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][edit]

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][edit]

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][edit]

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][edit]

July 25, 2020
kokic
Pearls

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

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

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

Definition. 多项式高度 [CAN2][edit]

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

对于任意一个 $\Z$-多项式 $P$, 其高度 $H(P)$ 限制了 $P$ 的次数和系数.

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

$\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$ 有限.

$\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$ 也只有有限多个.

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

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

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

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][edit]

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. $(1-q)^{-m}$ 的系数 [GF3A][edit]

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][edit]

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][edit]

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][edit]

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) $$

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

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

$$ \begin{aligned} \pi(G \without e) &\spaces= \pi(G \without e \sstr{中} A,B ~同色的部分) ~ + ~ \pi(G \without e \sstr{中} A,B ~异色的部分) \\ &\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$ 连接得到的边.

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

December 26, 2024
kokic
Pearls

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

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

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

December 26, 2024
kokic
Pearls

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

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

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

我们先画出 $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][edit]

August 31, 2025
kokic
Proofs from THE BOOK, p. 5
Pearls

$\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 对此证明的收录.