2026-09-05 · 树上临界点为何一眼可见

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 在一张无穷图 $G=(V,E)$ 上，把每条边独立地以概率 $p$ 宣告为 open（开），否则为 closed（闭）。固定顶点 $o$，记 $C(o)$ 为所有可由开边路径从 $o$ 到达的顶点所成的 open cluster（开簇），并令

$${\theta }_G(p):={\mathbb{P}}_p(|C(o)|=\mathrm{\infty }),p_c(G):=inf\{p\in [0,1]:{\theta }_G(p)>0\}.$$

阈值定义只告诉我们 $p<p_c$ 时没有无穷簇、$p>p_c$ 时有正概率出现无穷簇；它没有自动决定端点：${\theta }_G(p_c)$ 究竟是 $0$ 还是正数？这正是 critical percolation（临界渗流）的边界问题。

今天先在一个完全可解的几何上回答它：根植 $b$ 叉树 $T_b$，其中 $b\ge 2$，每个顶点恰有 $b$ 个孩子。树没有环，因此根簇的不同子枝真正独立；这使图上的连通问题逐字变成 Galton–Watson branching process（Galton–Watson 分枝过程）。我们将证明

$$p_c(T_b)=\frac{1}{b},{\theta }_{T_b}\left(\frac{1}{b}\right)=0.$$

对象与量词有四层：

1. 先固定整数 $b\ge 2$ 和确定性无穷树 $T_b$；
2. 对每个 $p\in [0,1]$，在边集上取独立 Bernoulli product measure（Bernoulli 乘积测度）${\mathbb{P}}_p$；
3. 对每个代数 $n\ge 0$，数根簇在第 $n$ 层的顶点数 $Z_n$；
4. 最后研究事件 $\{Z_n>0\mathrm{\forall }n\}$，它在 locally finite tree（局部有限树）上恰等于 $\{|C(o)|=\mathrm{\infty }\}$。

先修：独立 Bernoulli 变量、二项分布、概率生成函数、凸函数。主导 proof engines：子树独立性把簇编码为分枝过程；灭绝概率由生成函数迭代给出；临界性由不动点在 $1$ 处的导数控制。去向：一般图的 $p_c$、susceptibility（平均簇大小）、临界指数、格点重整化，以及形式化证明中“kernel checks a theorem”与“the formal theorem expresses the intended mathematics”的分层审计。

本期是 ISO week 36 的 weekly roaming issue：它从昨日《Varadhan 引理》末尾“临界渗流证明应区分主张与接受”的旁线出发，转入概率论、无穷组合、统计物理与形式验证的交叉处；它不是大偏差 arc 的 Day 4。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 从开簇到分枝过程

在 $T_b$ 的每条边上独立放置状态。令

$$Z_n:=\mathrm{\#}\{v\in C(o):d(o,v)=n\},Z_0=1.$$

若第 $n$ 代有 $Z_n=k$ 个顶点，则每个顶点各有 $b$ 条通向下一代的边；这些边彼此不同并且独立。因此在给定 $Z_n$ 后，下一代可以写成

$$Z_{n+1}=\sum _{i=1}^{Z_n}{X}_{n,i},X_{n,i}\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}.}{\sim }\mathrm{Bin}(b,p).$$

所以 $(Z_n{)}_{n\ge 0}$ 正是以后代变量 $X\sim \mathrm{Bin}(b,p)$ 驱动的 Galton–Watson 过程，其平均后代数为

$$m:=\mathbb{E}X=bp.$$

这里“树”不是图像比喻，而是独立性的结构来源：不同孩子以下的后代边集不相交。若底图有环，两条探索枝可能重新相遇，便不能把它们当作互不相干的家系。

1.2 灭绝概率是最小不动点

后代变量的 probability-generating function（概率生成函数）为

$$f(s):=\mathbb{E}[s^X]=(1-p+ps{)}^b,0\le s\le 1.$$

令

$$q_n:={\mathbb{P}}_p(Z_n=0).$$

因为一旦灭绝便永不复生，事件 $\{Z_n=0\}$ 随 $n$ 递增。又由每个孩子的后代过程独立且与原过程同分布，

$$q_0=0,q_{n+1}=f(q_n).$$

于是 $q_n\uparrow q\in [0,1]$，连续性给出 $q=f(q)$。反过来，若 $r\in [0,1]$ 满足 $f(r)=r$，则由 $q_0=0\le r$ 和 $f$ 的单调性归纳得 $q_n\le r$，故 $q\le r$。因此

灭绝不动点原理。 灭绝概率

$$q={\mathbb{P}}_p(\mathrm{\exists }n:Z_n=0)$$

是 $f$ 在 $[0,1]$ 中的最小不动点；存活概率为 $1-q$。

在局部有限树上，若根簇无限，则它每一层都有顶点；反之，若每一层都有顶点，König infinity lemma（König 无穷引理）给出一条从根出发的无穷射线。因此

$${\theta }_{T_b}(p)={\mathbb{P}}_p(Z_n>0\text{ for every }n)=1-q.$$

1.3 主定理：$p_c=1/b$，且临界点不渗流

定理。 对每个整数 $b\ge 2$，在根植 $b$ 叉树 $T_b$ 的独立 Bernoulli 边渗流中，

$$\mathrm{\forall }p\in [0,1],{\theta }_{T_b}(p)>0⟺bp>1.$$

特别地，

$$p_c(T_b)=\frac{1}{b}\text{且}{\theta }_{T_b}(p_c)=0.$$

证明架构。 写 $g(s)=f(s)-s$。我们有

$$f(1)=1,f^{\prime }(1)=bp=m,$$

并且当 $0<p<1$ 时，$f$ 在 $[0,1]$ 上严格凸。

• 若 $m\le 1$，凸函数位于它在 $1$ 处切线之上：

  $$f(s)\ge f(1)+f^{\prime }(1)(s-1)=1+m(s-1)\ge s,0\le s<1.$$

  在 $m=1$ 时，严格凸性使第一步对 $s<1$ 为严格不等式；在 $m<1$ 时，第二步为严格不等式。因此 $[0,1]$ 中没有小于 $1$ 的不动点，最小不动点是 $q=1$，故 ${\theta }_{T_b}(p)=0$。端点 $p=0$ 也显然如此。

• 若 $m>1$ 且 $p<1$，则 $g(0)=(1-p{)}^b>0$，而 $g(1)=0$、$g^{\prime }(1)=m-1>0$。所以对充分接近 $1$ 且小于 $1$ 的 $s$，有 $g(s)<0$。由介值定理，$g$ 在 $(0,1)$ 有一个零点，故最小不动点 $q<1$，于是 ${\theta }_{T_b}(p)>0$。若 $p=1$，所有边都开，结论直接成立。

这也解释了为何假设恰好落在 $bp$ 上：$bp$ 不是“典型分枝数”的模糊估计，而是生成函数在灭绝不动点 $1$ 处的线性化系数。

作为次临界的另一条快速证明，若 $bp<1$，则

$$\mathbb{E}{Z}_n=(bp{)}^n,\mathbb{P}(Z_n>0)\le \mathbb{E}{Z}_n=(bp{)}^n⟶0.$$

但在临界点 $bp=1$，这个一阶矩论证只给 $\mathbb{E}{Z}_n=1$，不再衰减；端点必须由不动点的二阶几何或一般临界分枝过程灭绝定理处理。

1.4 与 Erdős–Rényi 巨分量阈值的局部桥梁

这套判据也是 roadmap 节点“Erdős–Rényi thresholds”的局部机制。取稀疏随机图 $G(n,c/n)$，从均匀顶点 $v$ 开始 breadth-first search（广度优先探索）。在已经暴露的顶点数仍为 $O(1)$ 时，一个新顶点通向尚未探索部分的边数近似服从

$$\mathrm{Bin}(n-O(1),\frac{c}{n})⟹\mathrm{Poisson}(c),$$

而有限次探索中发生碰撞的概率趋于零。因此对每个固定深度，$v$ 的邻域局部收敛到后代律 $\mathrm{Poisson}(c)$ 的 Galton–Watson 树。上一节的不动点判据遂预言：$c\le 1$ 时局部探索必灭，$c>1$ 时有正存活概率；这正是 giant component（巨分量）在 $c=1$ 出现的分枝机制。

须分清“机制”与“完整定理”：固定深度的局部收敛本身还不能控制大小为 $\mathrm{\Theta }(n)$ 的分量。把分枝过程近似延伸到增长中的探索、控制碰撞与耗尽，并证明唯一巨分量出现，才构成有限随机图相变的全局证明。

1.5 谱系与现代边界：树的答案为何不是格点的证明

Bernoulli percolation（Bernoulli 渗流）由 Broadbent 与 Hammersley 在 1950 年代系统引入；树模型随后成为把几何增长与分枝过程联系起来的可解实验室。Lyons 与 Peres 的 Probability on Trees and Networks 给出了统一框架：对 $n$ 叉树，根簇就是后代律 $\mathrm{Bin}(n,p)$ 的 Galton–Watson 树，因而 $p_c=1/n$。

对 Euclidean lattice（Euclidean 格点）${\mathbb{Z}}^d$，定义仍是

$${\theta }_d(p)={\mathbb{P}}_p(0\leftrightarrow \mathrm{\infty }),p_c(d)=inf\{p:{\theta }_d(p)>0\},$$

但“一个顶点的不同孩子”不再生成互斥后代：探索路径会绕环、合并，并共享尚未揭示的边。树上的单变量递推 $q=f(q)$ 因而消失。

现代扩张与当前证据状态（截至 2026-09-05，Asia/Shanghai）。 Kozma 与 Nitzan 在 2024 年把 ${\mathbb{Z}}^d$ 上的 ${\theta }_d(p_c)=0$ 归约到一类有限加权图上的 conjectured gluing inequality（猜想性粘合不等式）；其论文明确写的是“若该不等式成立，则临界点无渗流”，并非当时已经无条件解决。2026 年 9 月公开的 Lean 4 / Mathlib 研究产物则给出一个 machine-checked claim（机器核验主张）：证明其中的 near-one gluing，再形式推出所有 $d\ge 2$ 的 ${\theta }_d(p_c)=0$。该仓库同时明确声明：产物尚未经作者之外的独立数学家评审，机械检查不替代对 Challenge.lean 是否准确表达预期数学命题的语义审计。

所以当前应分开记录三件事：

1. 2024 条件归约：Kozma–Nitzan 的公开论文及其精确条件；
2. 2026 形式产物：固定源码与工具链下，Lean kernel 接受了给定形式陈述的证明项；
3. 共同体接受状态：形式陈述的语义对应、文献输入重现与独立审阅仍需另外核查。

这不是贬低形式验证，恰恰是尊重它的精确能力边界：kernel 极强地回答“这个 proof term 是否具有这个 formal type”，却不会替人回答“这个 type 是否完整忠实地刻画了原先的自然语言问题”。

2. 固定模板习题 (Template Exercise)

题目

设 $(S_k{)}_{k\ge 0}$ 是整数线段 $\{0,1,\dots ,N\}$ 上的随机游走，$N\ge 2$，初值 $S_0=i\in \{0,\dots ,N\}$。在到达 $0$ 或 $N$ 前，每一步以概率 $p\in (0,1)$ 向右走一格，以概率 $q:=1-p$ 向左走一格。令

$${\tau }_a:=inf\{k\ge 0:S_k=a\}.$$

求

$$h_i:={\mathbb{P}}_i({\tau }_N<{\tau }_0)$$

在 $p\ne q$ 与 $p=q=1/2$ 两种情形下的显式公式。

模板识别

“有限状态 Markov 链 + 先击中哪个边界 + 最近邻转移”提示使用 discrete harmonic boundary-value problem（离散调和边值问题）：先作首步条件化得到内部调和方程，再用两个边界值确定唯一解。不要从枚举所有路径开始。

分级提示

1. 写出 $h_0,h_N$，并对 $1\le i\le N-1$ 以第一步向左或向右作条件化。
2. 把二阶递推 $h_i=p{h}_{i+1}+q{h}_{i-1}$ 改写为相邻差 $d_i:=h_i-h_{i-1}$ 的一阶递推。
3. 当 $p\ne q$ 时，$d_i$ 是公比 $q/p$ 的几何数列；最后使用 $\sum _{i=1}^N{d}_i=h_N-h_0$。
4. 当 $p=q$ 时不要把 $q/p=1$ 生硬代入几何和的分式；直接解零二阶差分，或取连续极限。

3. 大家之言 (Mathematician in Their Own Words)

人物与语境。 理论计算机科学家 Scott Aaronson 在个人博客 Shtetl-Optimized 的 2019 年 3 月 7 日文章 Death of proof greatly exaggerated 中，讨论传统证明、计算机辅助证明与完全形式化证明的关系。下引保持原文标点，是一段关于数学家日常所称“已证明”的第一人称描述：

“When mathematicians say that a theorem has been ‘proved,’ they still mean, as they always have, something more like: ‘we’ve reached a social consensus that all the ideas are now in place for a strictly formal proof that could be verified by a machine … with the only task remaining being massive rote coding work that none of us has any intention of ever doing!’”

“当数学家说一个定理已经‘被证明’时，他们通常仍是说：共同体已经形成共识——构造一份可由机器核验的严格形式证明所需的全部思想都已到位，剩下的只是庞大的机械编码工作，而没有人真打算去做。”

评注。 这段话刻画的是 working proof（工作意义下的证明）与 fully formal proof（完全形式证明）之间的传统劳动分工，不是把社会共识当作逻辑正确性的定义。到 2026 年的临界渗流产物，自动化系统已经实际承担了 Aaronson 当时所说的“大量编码”乃至部分证明搜索；但证据链并没有因此缩成一个按钮：formal statement 的自然语言对应、文献定理是否被忠实重现、依赖与公理、以及独立复核仍是不同问题。

树模型让这种分层变得可执行。我们既可以检查每个公式是否推出下一个公式，也可以另问：根植 $b$ 叉树、无向 $(b+1)$-regular tree（正则树）与 ${\mathbb{Z}}^d$ 是否被混作同一对象？$\theta (p_c)=0$ 是否只陈述端点消失，还是还偷偷声称了定量临界指数？形式严格性之所以珍贵，正在于它迫使这些类型与结论边界被逐项说清。

4. 反例与边界 (Counterexample & Boundary)

下面检验一个非常诱人的错误命题：

错误命题。 若 ${\mathbb{E}}_p|C(o)|=\mathrm{\infty }$，则 ${\mathbb{P}}_p(|C(o)|=\mathrm{\infty })>0$。

取临界 $b$ 叉树渗流 $p=1/b$。逐项检查：

1. 根簇的第 $n$ 代大小为 $Z_n$，且
   $$\mathbb{E}{Z}_n=(bp{)}^n=1.$$
2. 根簇总大小满足扩展非负随机变量恒等式
   $$|C(o)|=\sum _{n=0}^{\mathrm{\infty }}{Z}_n.$$
3. 由 Tonelli theorem（Tonelli 定理），不需要预先假设可积，
   $$\mathbb{E}|C(o)|=\sum _{n=0}^{\mathrm{\infty }}\mathbb{E}{Z}_n=\sum _{n=0}^{\mathrm{\infty }}1=\mathrm{\infty }.$$
4. 但主定理已经证明临界过程几乎必然灭绝，所以
   $${\mathbb{P}}_{1/b}(|C(o)|=\mathrm{\infty })=0.$$

因此反例同时满足“簇几乎必然有限”和“簇大小期望无穷”。失败点是把 expectation-level divergence（期望层发散）误当成 positive mass at infinity（无穷处有正质量）：越来越罕见但越来越大的有限簇，足以让均值发散。

这条边界在统计物理语言中尤为重要。susceptibility（磁化率或平均簇大小）

$$\chi (p):={\mathbb{E}}_p|C(o)|$$

可在临界点发散，而 order parameter（序参量）$\theta (p)$ 仍为零。二者都在描述“大簇”，却是不同量词：$\chi$ 对所有有限尺度加权求和；$\theta$ 问单个样本是否真正贯穿到无穷。

5. 今日一问与数学地图 (Question & Map)

今日一问。 仍取临界参数 $p=1/b$。令

$$a_n:=\mathbb{P}(Z_n>0)=1-f^{\circ n}(0).$$

能否只从

$$f(1-x)=1-x+\frac{f^{″}(1)}{2}{x}^2+O(x^3)(x\downarrow 0)$$

出发，确定 $a_n$ 的一阶渐近阶，并解释为什么临界过程“必然灭绝”却能在很深的层数仍留下 polynomial tail（多项式尾），而不是次临界时的指数尾？

方向提示。 先把 $a_{n+1}=1-f(1-a_n)$ 写成形如

$$a_{n+1}=a_n-c{a}_n^2+O(a_n^3)$$

的递推；不要直接求 $a_n$，而比较 $a_{n+1}^{-1}-a_n^{-1}$。

数学地图。

$$\begin{array}{c}\text{Bernoulli product measure}+\text{rooted tree geometry}\\ \downarrow \\ \text{Galton--Watson encoding}\\ \downarrow \\ \text{generating-function fixed point}⟶p_c(T_b)=1/b\\ \downarrow \\ \text{critical Taylor expansion}⟶\text{survival-depth exponent}\\ \downarrow \\ \text{susceptibility / finite-size scaling / critical exponents}\end{array}$$

横向连接则是

$$\text{tree exact recursion}⟷\text{branching number and electrical networks},$$

而向格点走时必须用新的几何工具替代独立子枝：crossing estimates（穿越估计）、gluing inequalities（粘合不等式）、renormalization（重整化）和 lace expansion（花边展开）。向形式数学走时还需加一张审计图：自然语言命题 $\to$ formal statement $\to$ dependency graph $\to$ kernel check $\to$ independent semantic review。证明完成之后，理解仍有地图要画。

附录 A：习题完整解答 (Full Solution)

展开完整解答

可复用模板：首步条件化—离散调和方程—差分降阶—边界归一化。

边界值立即给出

$$h_0=0,h_N=1.$$

对每个 $1\le i\le N-1$，按第一步条件化，并使用 Markov property（Markov 性），得到

$$\begin{array}{}\text{(1)}& h_i=p{h}_{i+1}+q{h}_{i-1}.\end{array}$$

定义相邻差

$$d_i:=h_i-h_{i-1},1\le i\le N.$$

由 (1)，

$$p(h_{i+1}-h_i)=q(h_i-h_{i-1}),$$

即

$$\begin{array}{}\text{(2)}& d_{i+1}=\frac{q}{p}{d}_i.\end{array}$$

情形一：$p\ne q$。 记 $r=q/p\ne 1$。由 (2)，

$$d_i=d_1{r}^{i-1}.$$

又由边界条件作 telescoping sum（望远镜求和），

$$1=h_N-h_0=\sum _{j=1}^N{d}_j=d_1\sum _{j=0}^{N-1}{r}^j=d_1\frac{1-r^N}{1-r}.$$

故

$$d_1=\frac{1-r}{1-r^N}.$$

再次求和得到

$$\boxed{{\displaystyle h_i=\sum _{j=1}^i{d}_j=\frac{1-r^i}{1-r^N}=\frac{1-(q/p{)}^i}{1-(q/p{)}^N}}}.$$

情形二：$p=q=1/2$。 此时 (2) 给 $d_{i+1}=d_i$，所以所有相邻差相等。由

$$\sum _{j=1}^N{d}_j=1$$

知 $d_j=1/N$，从而

$$\boxed{{\displaystyle h_i=\frac{i}{N}}}.$$

最后说明唯一性：若两组数都满足 (1) 和同一边界条件，则其差仍满足齐次调和递推且两端为零；上述差分推导迫使全部相邻差为零，故两解相同。因此求出的序列确为所求击中概率，而不只是递推方程的某个候选解。

资料与来源 (Sources)

1. Russell Lyons and Yuval Peres, Probability on Trees and Networks, Cambridge University Press, 2016；作者维护的 2026 corrected/updated paperback electronic edition。Chapter 5, especially §5.1–§5.2：Galton–Watson 灭绝判据、Bernoulli percolation 定义，以及 $n$ 叉树根簇具有 $\mathrm{Bin}(n,p)$ 后代律并满足 $p_c=1/n$。作者书页与可审计全文：https://rdlyons.pages.iu.edu/prbtree/ ，https://rdlyons.pages.iu.edu/prbtree/book_pb.pdf
2. Gady Kozma and Shahaf Nitzan, “A reduction of the $\theta (p_c)=0$ problem to a conjectured inequality,” arXiv:2401.12397, submitted 22 January 2024. 摘要明确说明该不等式若成立，则推出所有 $d>1$ 的 Euclidean lattice 临界点无渗流：https://arxiv.org/abs/2401.12397
3. Scott Aaronson, “Death of proof greatly exaggerated,” Shtetl-Optimized, 7 March 2019. 本期“大家之言”的第一人称语境和英文引文据原页逐字核验：https://scottaaronson.blog/?p=4133
4. Anthropic, formal-math/percolation, commit 795efb86f191735c5481675763537cfb4ff37e55, September 2026 research artifact. README 陈述 Lean 4 / Mathlib 中的 $\theta (p_c)=0$ 形式结果、Kozma–Nitzan 归约链、工具链与审计边界，并明确标注尚无独立于作者的评审：https://github.com/anthropics/formal-math/blob/795efb86f191735c5481675763537cfb4ff37e55/percolation/README.md
5. Gil Kalai, “Amazing: There is no Percolation at the Critical Probability in all Dimensions. (Solved by AI via a conjecture of Gady Kozma and Shahaf Nitzan.)”, Combinatorics and more, 3 September 2026. 作为发现线索与同期数学共同体反应；原文以 “If verified” 作条件性表述：https://gilkalai.wordpress.com/2026/09/03/amazing-there-is-no-percolation-at-the-critical-probability-in-all-dimensions-solved-by-ai-via-a-conjecture-of-gady-kozma-and-shahaf-nitzan
6. Remco van der Hofstad, Random Graphs and Complex Networks, lecture notes, 26 January 2013, Chapters 3–4，尤其 §4.1.2 “Informal link to Poisson branching processes” 与随后对分枝过程的比较；用于 $G(n,c/n)$ 局部探索和 $c=1$ 巨分量机制：https://rhofstad.win.tue.nl/NotesRGCN2013.pdf