几年前在知乎上有这么 一个问题：

当时我给了回答，后来账号注销了，答案也一并删除了。现在把我的原答案贴在这里：

今天我要介绍一个 Markov 链采样中的精彩算法，叫做 coupling from the past (CFTP)。这个算法看似简单，实则充满玄机。我相信你可以在五分钟内理解算法的步骤，然后再花五分钟左右看懂算法的证明，但是我打赌你需要几个星期甚至更久的时间来细细回味其中奥妙。

为了引出算法，我们从一个计数问题开始：

你可能经常听到这样一句话：“做数学要大胆假设，小心求证”。我们今天要介绍的故事主角平面分拆中的 Andrews 猜想就完美地符合这一点。两个看似风马牛不相及的计数对象，因为有着相同的计数序列，冥冥中被联系在了一起，启发三位数学家 Mill, Robins 和 Rumsey 解决了一个困难的组合学猜想。整个过程并无高深的内容，但是其中的“信仰一跃”和“灵魂一猜”构成了故事的高潮，而那些繁琐的计算过程不过是小心求证的注脚而已。

本文来自我几年前读 David Bressoud 的 (Bressoud 1999)

Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture

一书时的读书笔记。本文只介绍 DPP 的 Andrews 猜想，并仅使用初等的 \(q-\) 二项式定理作为工具。我这里采用的叙述方式与 Bressoud 的书不同：Bressoud 是把 DPP 的 Andrews 猜想和 CSPP 的 Macdonald 猜想统一用 \(q-\) 超几何级数一起解决的。Macdonald 猜想的证明似乎无法避免使用超几何级数的理论，但 Andrews 猜想是完全可以用初等的 \(q-\) 多项式解决的。

常见的生成树算法如 DFS/BFS 算法、Prim 算法、Kruskal 算法等给出的生成树都不是完全随机的。例如，取 \(G\) 为 \(\mathbb{Z}^2\) 中 \(m\times n\) 的网格图，\(G\) 的任何生成树都是一个迷宫，把背景平面涂黑，把生成树的边涂白，就可以清楚地看到迷宫的结构。迷宫的任何两个房间 ( 即树的顶点 ) 可以通过生成树中唯一的路径相连，这样的迷宫叫做完美迷宫。

DFS 算法 ( 每次将新顶点的顺序打乱再入栈 ) 倾向于尽可能深地探索整个图，因此得到的迷宫往往包含长且蜿蜒的路径，死角 ( 即叶节点 ) 是很少的：

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

它展示的是 Lie 代数 \(E_8\) 的根系图。\(E_8\) 的根系由 8 维欧式空间 \(\mathbb{R}^8\) 中的 240 个向量组成，将这 240 个向量投影到一个特殊的 2 维平面 ( 称作 Coxeter 平面 ) 上就会呈现出上图中旋转对称的图案。图中 240 个投影点分布在 8 个圆周上，每个圆周包含 30 个均匀分布的点，整个图案在角度为 \(2\pi/30\) 的旋转下保持不变。\(h=30\) 正是 \(E_8\) 的 Coxeter 数。

本文目的是介绍 Coxeter 元的一些基础知识，然后教大家怎样在 Python 中编写一个程序绘制上面的投影图案。我主要参考了 (Humphreys 1990) 和 (Casselman 2017)。虽然这里面涉及的数学并不复杂，但是真正动手编程实现的时候会有一些魔鬼藏在细节中，而这些细节是仅凭念书很难发现的。

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