Coxeter 群,有限状态机与均匀铺砌

终于完成了一个新的 Python 小程序,虽然还有一些功能有待实现,但是大致的效果已经出来了。

这个程序是我最近半年多来利用几乎所有业余时间呕心沥血、披星戴月、艰苦攻关完成的一个新作品,是一个纯粹的、优雅的、有益于广大人民欣赏数学之美的小程序,代码在 github 上。

这个程序可以用来绘制二维和三维欧式空间、双曲空间和球面上的各种均匀铺砌 (均匀的含义是对称群在顶点集合上的作用是传递的)。部分例子如下:

Möbius 变换的分类与上半双曲空间的等距 (本文内含若干 shader 动画所以加载较慢)

本文的想法源自 Roice Nelson 的 shadertoy 项目,我觉得他的创意很棒,就是效果有点糙,于是动手改进了一番,结果见这里。不懂的人看这个动画可能只是觉得好玩,其实它背后的数学并不简单。

这篇文章将用动画的形式从三个角度演示 Möbius 变换 (这三个角度是密切相关的):

  1. Möbius 变换作为扩充复平面 \(\hat{\mathbb{C}}\) 到自身的全纯函数。
  2. Möbius 变换作为 Riemann 球面 \(S^2\) 到自身的全纯函数。
  3. Möbius 变换作为上半双曲空间中的等距变换。

本文只做演示,并不介绍详细的数学证明。读者可以参考下面的两份资料:

  1. 维基百科页面.
  2. Visual complex analysis, Tristan Needham.

借助本文的动画你可以很容易地理解这两份资料中的内容。

文中的动画全部使用 shader 程序制作,需要你的浏览器支持 Webgl2.0,代码在 github 上。

Wilson 均匀生成树算法

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

Birkhoff 遍历定理

我觉得 Durrett 概率论中关于 Birkhoff 定理的讲述实在太糟糕,翻了翻其它教材,也没有找到满意的版本,于是决定自己写一份 Birkhoff 遍历定理的证明。

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

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

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

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

称硬币问题

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

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

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

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

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

相亲问题与倒向归纳法

问题:假设你是一位大龄男士,准备参加 100 场相亲 (别介意具体数字)。你打算依次与每个女士 \(i\) 约会,然后根据印象给她打一个分数 \(X_i\)\(X_i\) 的值介于 \([0,1]\) 之间。如果你对女士 \(i\) 很满意,那么就和她结婚,否则就放弃她,参加下一场相亲,当然拒绝了人家可就没有回头的机会了。如果你拒绝了前 99 位女士,那么不论第 100 次相亲结果如何你都只能和最后这位女士结婚。在相亲之前,你对这些女士的情况一无所知,所以姑且假定她们的分数 \(X_i\) 都是 \([0,1]\) 上均匀分布的独立的随机变量。问题是:应该采取怎样的相亲策略,才能娶到你最中意的女士?

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