Wilson 均匀生成树算法

更新:在距离本文初稿完成数年后,我终于实现了一个 Python 程序,可以制作演示 Wilson 算法的 GIF 动图,见 这个 Github 项目。此外还用 Javascript + canvas 为本文写了一个动画演示,这也是我的第一个正式的 Javascript 程序 (其实就是把对应的 Python 程序修改下翻译了过来),你可以随时单击鼠标来重启动画。

Coxeter element: a computational approach

虽然本文起了个英文标题,但内容完全是中文的,原因是我没有想到合适的中文标题。

如果你对李代数有所了解的话,相信很大概率你会见过下面的图案:(参考维基百科的 Lie algebra 词条

它展示的是李代数 \(E_8\) 的根系图,李代数 \(E_8\) 的根系由八维欧式空间 \(\mathbb{R}^8\) 中的 240 个向量组成,每个向量恰好有 56 个与其距离最近的邻居。将这 240 个向量投影到一个特殊的二维平面 (叫做 Coxeter 平面) 就会呈现一个旋转对称的图案,你可以看到上图中的图案中,240 个投影点分布在 8 个圆周上,每个圆周包含 30 个均匀分布的顶点,所以它在角度为 \(\frac{2\pi}{30}\) 的旋转下是不变的。\(h=30\) 叫做 \(E_8\) 的 Coxeter 数。

这个现象并不是 \(E_8\) 独有的,对任何有限 Coxeter 群都有类似的结论成立,比如下图显示的是将 5 维超立方体的 32 个顶点和它们的边投影到其 Coxeter 平面后得到的图案:

有两个顶点被同时投影到了原点,其余 30 个顶点分布在 3 个圆周上,每个圆周包含 10 个均匀分布的顶点,所以其 Coxeter 数 \(h=10\)

本文下面以 \(E_8\) 为例子,通过具体的计算来解释背后的数学。我会不加证明地引用 Humphreys (1990) 中的结论。

本文的代码在 Github 上

David Madore 也有一个很棒的 交互式网页 可以绘制 \(E_8\) 的多种不同风格的图案。

Birkhoff 遍历定理

我研究生的高等概率论课程用的是 Durrett 的教材 “Probability: Theory and Examples”。这本书的好处我就不再介绍了,院长陈大岳老师在世图影印版的前言中已经夸了一遍。我个人的体会是,Durrett 的书在讲解证明的时候非常简练,很少写为什么要这样证,我有时候读了半天也没搞明白思路。Birkhoff 遍历定理算是其中一个,于是我重新整理了一下书中的证明,作此文留念。

Birkhoff 遍历定理最初由 Birkhoff 本人在 1931 年发表,原文长达 50 页。随后在 1939 年 K.Yosida (吉田耕作) 和 S.Kakutani (角谷) 利用极大遍历定理给出了一个 10 页的简洁证明,不过他们关于极大遍历定理的证明还是啰嗦了点,后来 Garsia 给出了极大遍历定理的一个仅有寥寥数行的惊人证明,这也是当前大多数教材采用的途径,本文就来介绍这一证明。

称硬币问题、小白鼠找毒药问题与编码理论

本文要讨论的问题比较常见,但是好像很少有人从纠错码的角度给出解释。从纠错码的角度看问题的好处是可以很容易理解为什么要这样设计策略,而且能举一反三处理其它类似的问题。事实上我觉得这种趣味问题正是帮助初学者理解纠错码基本概念的绝好例子。

不过本文并不假定读者事先学过编码论,但是需要懂一点有限域的知识。

称硬币问题

问题 1.1 有 12 枚外表一模一样的硬币,其中一枚是假币,其余都是真币。假币的重量与真币不同,但是更重还是更轻不知道。给你一个没有砝码和刻度的天平,最少称几次才能确保找出假币?

有限群的不可约实表示和复表示

在数学中有许多“三分天下”的例子,比如说:

  1. 常曲率空间只有欧式、球面、双曲三种。
  2. 三类典型的偏微分方程:热方程 (抛物)、Laplace 方程 (椭圆)、波方程 (双曲)。
  3. 复平面上全纯等价下只有三种单连通区域:单位圆 \(\mathbb{D}\)、复平面 \(\mathbb{C}\)、扩充复平面 \(\bar{\mathbb{C}}\)
  4. 不可约代数簇 (素理想) 在扩张下的三种行为:分解、惯性、分歧。
  5. 随机游动可以分为零常返、正常返、暂态。
  6. 实数域上的有限维结合可除代数只有三种:实数域 \(\mathbb{R}\)、复数域 \(\mathbb{C}\)、四元数 \(\mathbb{H}\)

本文要介绍的是另外两个三分天下的例子,它们来自群表示论,即有限群的不可约实表示在复数域上的分解,和不可约复表示在实数域上的实现。这两个例子是紧密相关的。

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器