自旋系统中相关性衰减至唯一性

摘要

我们给出了在一般图上具有强空间混合的二态反铁磁自旋系统的完整表征。 我们证明，当且仅当系统在无限正则树上具有唯一的吉布斯测度时，二态反铁磁自旋系统在所有最大度数最多 $\mathrm{\Delta }$ 的图上具有强空间混合到 $\mathrm{\Delta }$，其中 $\mathrm{\Delta }$ 可以是有界的，也可以是无界的。 因此，当在度数高达 的无限正则树上满足唯一性条件时，在最大度数最多 $\mathrm{\Delta }$ 的图上，存在一个二态反铁磁自旋系统的配分函数 FPTAS $\mathrm{\Delta }$。 特别是，如果所有无限正则树都满足唯一性，则任意图都存在 FPTAS。 作为特殊情况，这涵盖了一般结构图上两态反铁磁系统的所有先前算法结果。

结合 Jerrum-Sinclair 和 Goldberg-Jerrum-Paterson 的二态铁磁自旋系统的 FPRAS，以及 Sly-Sun 和独立于 Galanis-S̆tefankovic̆-Vigoda 的最新硬度结果，这给出了完整的分类，除了相变边界，所有二态自旋系统的近似性，在有度限制的图族或所有图族上。

1简介

自旋系统在统计物理、应用概率和计算机科学领域得到了深入研究，作为捕捉局部相互作用和约束如何影响粒子系统宏观特性的本质的通用框架。 系统通常用图来描述，每个顶点处于固定数量的状态之一（称为自旋），边指定系统的邻域关系。

令 $G(V,E)$ 为图表，$q$ 为自旋状态数。 系统的配置是$q^{|V|}$可能的分配$\sigma :V\to [q]$之一。 每个配置$\sigma$都有一个能量$H(\sigma )$作为所有边和顶点的总和，使得边$(u,v)\in E$的贡献由对称函数确定自旋状态$\sigma (u)$和$\sigma (v)$，顶点$v\in V$的贡献由其自旋状态$\sigma (v)$的函数确定。 配置$\sigma$的权重是$w(\sigma )=\exp (-\frac{H(\sigma )}{T})$，其中$T$是温度。 我们专注于两种状态的自旋系统。 在归一化之前，二态自旋系统完全由三个参数 $(\beta ,\gamma ,\lambda )$ 捕获，其中 $\beta$ 和 $\gamma$ 确定边缘贡献的对称函数，$\lambda$，也称为外部场，决定顶点贡献的函数。 吉布斯测度是所有配置的自然概率分布，配置 $\sigma$ 的概率为 $\frac{w(\sigma )}{Z}$，其中归一化因子 $Z=\sum w(\sigma )$ 称为配分函数。 配分函数编码了有关自旋系统宏观行为的丰富信息。 然而，对于几乎所有重要的设置来说，计算配分函数的精确值是非常困难的。

自旋系统最重要的特性之一是相关性衰减，它表示两个顶点的边缘吉布斯分布之间的相关性随着两个顶点之间的距离而快速衰减。 此属性也称为弱空间混合 [26]。 具有更大算法意义的是强烈的空间混合，这表明在其他顶点存在任意固定自旋的情况下相关性会衰减。 对于二态自旋系统，强空间混合可能意味着配分函数的有效近似算法。 那么，通过系统的参数来表征在图的任意实例上表现出强空间混合的系统是一个重要的问题。

如果相邻顶点有利于自旋一致，则二态自旋系统是铁磁的，否则是反铁磁的。 对于所有二态铁磁自旋系统，配分函数可以有效地近似[12, 10]。 在反铁磁区域，相关衰减在配分函数的近似性中起着核心作用。 人们认为（参见[19])，对于此类模型，配分函数的逼近性由无限正则树上吉布斯测度的唯一性来表征，这相当于无限正则树上的弱空间混合普通树。 该条件称为唯一性条件。

在开创性的著作[26]中，Weitz 表明，对于硬核模型来说，强空间混合的特点是唯一性条件，而在 Sinclair、Srivastava 和 Thurley 最近的著作中[21] 反铁磁伊辛模型也证明了相同的特征。 这两个模型都是重要的特殊双态反铁磁自旋系统。 在硬度方面，Sly [23] 和 Galanis 等人 [6] 为硬核模型证明了这一点，并且最近对于 Sly 和 Sun [24] 以及 Galanis、S̆tefankovic̆ 和 Vigoda [7] 独立提出的一般二态反铁磁自旋系统，违反唯一性条件意味着配分函数的不可近似性。 对于我们对二态自旋系统中的相关衰减和计算的完整理解，有两个问题仍然悬而未决：强空间混合的表征和一般二态自旋系统的近似性。

1.1我们的结果

我们通过无限正则树上吉布斯测度的唯一性来表征二态反铁磁自旋系统，该系统在一般有度有界图或任意图上表现出强烈的空间混合。

Theorem 1。

对于任何有限$\mathrm{\Delta }\ge 2$或$\mathrm{\Delta }=\mathrm{\infty }$，二态反铁磁自旋系统在最大度图上最多$\mathrm{\Delta }$具有强空间混合当且仅如果系统在所有$d\le \mathrm{\Delta }$的无限$d$-正则树上表现出唯一性。

由于Weitz的自回避游走树构造[26]，有度有界图上的二态自旋系统的强空间混合立即意味着配分函数的FPTAS。 事实上，我们展示了之前的工作[15]中引入的更强大的相关性衰减概念，即计算有效的相关性衰减，它不仅为有度有界图提供 FPTAS，还为任意图提供 FPTAS当满足相应的唯一性条件时，具有无界度。

Theorem 2.

对于任意有限的$\mathrm{\Delta }\ge 3$或$\mathrm{\Delta }=\mathrm{\infty }$，在最多$\mathrm{\Delta }$的图上，二态反铁磁自旋系统的配分函数存在一个FPTAS > 如果对于所有$d\le \mathrm{\Delta }$，系统参数位于无限$d$-正则树的唯一性区域的内部。

在上述两个定理中，$\mathrm{\Delta }=\mathrm{\infty }$情况代表无界度图。

由于 Sly 和 Sun [24] 针对一般二态自旋系统的最新硬度结果以及 Galanis、S̆tefankovic̆ 和 Vigoda [7] 针对一般二态自旋系统的独立结果不太通用的设置，违反唯一性条件意味着配分函数的不可近似性。

Theorem 3 （由于[24]和[7])。

对于任何有限的$\mathrm{\Delta }\ge 3$或$\mathrm{\Delta }=\mathrm{\infty }$，除非$NP=RP$，不存在用于二态反铁磁自旋系统在图上的配分函数的FPRAS如果对于某些$d\le \mathrm{\Delta }$，系统参数位于无限$d$-正则树的非唯一性区域的内部，则最大度至多$\mathrm{\Delta }$。

[24] 中的原始定理适用于 $d$ - 具有固定 $d$ 的正则图，这立即意味着有度有界图或任意图的硬度。 而 [24] 和 [7] 中的硬度条件要求在具有 $d\ge 3$ 的 $d$ 不规则树上的非唯一性。 但无限2-正则树（即无限路径）上的唯一性对于任何二态反铁磁自旋系统始终成立，因此定理3中的条件就足够了。

对于最大次数为 2 或更小的图，可以在多项式时间内精确计算配分函数。 因此，定理2和定理3与两态铁磁自旋系统[12, 10]的FPRAS一起给出了几乎完整的（除了在相变边界）所有二态自旋系统的配分函数的近似性分类，在有度有界图族或所有图族上。

1.1.1 规律性和单调性

在统计物理学中，相关性衰减通常在正则图甚至结构对称图（例如 Bethe 晶格）上研究。 尽管对于仅考虑正则图的硬度结果将加强下界，但从算法的角度来看，考虑通用图上的自旋系统更为普遍。 [26]中硬核模型的近似算法和反铁磁Ising模型的[21]中的近似算法均适用于具有有限最大度的一般图。 正如[21, 24]中所讨论的，对于具有固定$d$的$d$规则图上的一般双态自旋系统，在参数平移之前，硬核模型和伊辛模型是完整的。然而，这并不包括最一般的情况，即一般图上有界或无界度的一般双态自旋系统。 造成这种差距的根本原因是一般自旋系统的非单调性。

充分研究的硬核和反铁磁 Ising 模型（以及所有具有 $\beta ,\gamma \le 1$ 的双态自旋系统）都是单调自旋系统，从某种意义上说，无限 $d$ 上的唯一性 -正则树意味着所有具有较小度数的无限正则树的唯一性。 这种单调性在一般的二态自旋系统中并不一定成立。

在[26]中，Weitz 在硬核模型中建立了以下含义：

Claim ([26]中的定理2.3）。

$d$-正则树上的强空间混合意味着最大程度至多$d$的所有图上的强空间混合。

在[26]中，Weitz在没有证明的情况下也指出这一推论对于所有二态自旋系统都成立（事实上，这在[21]中的反铁磁伊辛模型中得到了严格证明>)。 有了这一点，为有度有界图上的二态自旋系统设计近似算法就可以简化为验证 $d$ 正则树上的强空间混合。 这已被接受为关于二态自旋系统的事实，并已成为此类系统的近似算法的构建块（参见[21]中的定理2.8以及[22中的讨论） ，23])。 [22]中还提出了该主张是否适用于一般多态自旋系统的猜想。

作为我们分析的副产品（参见第 5 节），我们发现 $d$ 正则树和最大度图上的强空间混合之间的这种可信的含义大多数 $d$ 仅适用于单调自旋系统（包括硬核和反铁磁 Ising 模型）。 对于一般的二态自旋系统，唯一性以及所有有度有界图之间的强空间混合的最坏情况确实是常规树，但可能不再是最高度的树。 这种复杂性的一个好处是，较高的度数可能会产生更快的相关性衰减，从而使 FPTAS 能够用于具有无界度数的图。

这些新现象表明，一般的二态自旋系统比经过充分研究的单调自旋系统（例如硬核和反铁磁伊辛模型）具有更丰富的结构。 前一种方法通过$d$正则树上的强空间混合，在一般图上的单调自旋系统和正则图上的一般自旋系统上取得了成功，但在处理一般图上的一般自旋系统时遇到了障碍。 我们通过任意树而不是$d$-常规树上的强空间混合，给出了一般二态自旋系统中相关性衰减的统一方法。 这种方法是在我们之前处理无界度图的工作[15]中发起的。 在本文中，我们设计了一种统一的基于势的分析，它适应任意树的不规则性和一般二态自旋系统的非单调性，并给出所有二态反铁磁自旋系统的紧密相关衰减结果关于图的有度族和所有图的族。

1.1.2 主要结果的意义

通过解决唯一性条件，我们可以以各种阈值形式重申我们的主要结果。 定理2作为特殊情况涵盖了一般结构图上二态反铁磁自旋系统的所有先前算法结果，并清除了以前未发现的情况。

在互动方面。

我们可以固定外场$\lambda$并讨论$(\beta ,\gamma )$的可处理区域。 由于$\beta$和$\gamma$的作用是对称的，我们可以进一步固定其中一个并讨论另一个的可处理范围。 [10, 15]中使用了该公式。

我们的主要结果可以重述如下：对于任何$\mathrm{\Delta }$，对于无限正则树上的唯一性有一个临界阈值${\gamma }_c(\beta ,\lambda ,\mathrm{\Delta })$，直到程度$\mathrm{\Delta }$，这样如果存在最大度数最多为$\mathrm{\Delta }$的图的FPTAS；特别地，${\gamma }_c={\gamma }_c(\beta ,\lambda ,\mathrm{\infty })>1$是绝对常数，因此如果$\gamma \in ({\gamma }_c,\frac{1}{\beta })$则任意图都存在FPTAS。

作为特殊情况，这涵盖了[10]中关于反铁磁系统的所有算法结果以及[15]中的所有结果，扩展了这些先前作品中的可处理区域，并且也考虑有度有界图。

在外场方面。

在硬核伊辛模型和反铁磁伊辛模型研究的推动下，我们可以固定$(\beta ,\gamma )$并讨论外场的可处理范围。

由于$\beta$和$\gamma$的对称作用，我们可以假设$\beta \le \gamma$。 我们的主要结果可以在特定设置下重述如下：

• 硬约束（当 $\beta =0$ 时）：对于任何 $\mathrm{\Delta }$, 是无限正则树上唯一性的关键阈值，最高可达 $\mathrm{\Delta }$ 度> 这样，如果 存在最大度数最多 $\mathrm{\Delta }$ 的 FPTAS。

  对于$\gamma \le 1$，临界阈值等于${\lambda }_c(\gamma ,\mathrm{\Delta })=\frac{{\gamma }^{\mathrm{\Delta }}{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }}}$。 在无界度的无限正则树上不存在满足唯一性的外场$\lambda >0$。 这与没有度数限制的硬核模型的硬度结果[4, 23]一致。 一个特别有趣的情况是当$\gamma =1$时，在这种情况下，模型是具有逸度$\lambda$的硬核模型，并且${\lambda }_c(1,\mathrm{\Delta })=\frac{{(\mathrm{\Delta }-1)}^{\mathrm{\Delta }-1}}{{(\mathrm{\Delta }-2)}^{\mathrm{\Delta }}}$是临界阈值。 这涵盖了[26]的结果。

  对于 $\gamma >1$，除了度受限图的结果外，还存在一个绝对正常数 ${\lambda }_c(\gamma )={\min }_{d>1}\frac{{\gamma }^{d+1}{d}^d}{{(d-1)}^{d+1}}$，它可以降低所有 $\mathrm{\Delta }$ 的 ${\lambda }_c(\gamma ,\mathrm{\Delta })$ 的边界，这样，如果 ，就存在一个适用于任意图的 FPTAS。

• 软约束（当 $\beta >0$ 时）：如果 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 的唯一性条件对于任何外部域 $\lambda >0$ 都成立，并且对于最大度最多为 $\mathrm{\Delta }$ 的图，总是存在一个 FPTAS。

  现在假设$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$。 令$\overline{\mathrm{\Delta }}$为满足$\sqrt{\beta \gamma }\le \frac{d-1}{d+1}$的最小$d$。 对于每个整数 ，对于无限 $(d+1)$ 正则树上的唯一性，存在两个阈值 ${\lambda }_1(\beta ,\gamma ,d)$ 和 ${\lambda }_2(\beta ,\gamma ,d)$，这样如果或$\lambda >{\lambda }_2(\beta ,\gamma ,d)$对于所有整数，最大度数最多为$\mathrm{\Delta }$的图存在一个FPTAS。

  此外，如果$\gamma \le 1$，则上述唯一性条件可以简化为或$\lambda >{\overline{\lambda }}_c$，其中和。 特别是，对于反铁磁伊辛模型$\beta =\gamma$，我们有${\overline{\lambda }}_c=1/{\lambda }_c$，并且当$|\log \lambda |>\log {\overline{\lambda }}_c$时唯一性成立。 这涵盖了[21]中反铁伊辛模型的结果。

  对于无界最大度$\mathrm{\Delta }$，如果$\gamma \le 1$，则在所有度的无限正则树上不存在满足唯一性的$\lambda >0$，这与硬度结果一致[10]；如果$\gamma >1$，则当或$\lambda >{\lambda }_2(\beta ,\gamma ,d)$对于所有$d\ge \overline{\mathrm{\Delta }}$时，所有无限正则树的唯一性成立，在这种情况下，存在用于任意图的 FPTAS。

1.2相关作品

自旋系统配分函数的近似已得到广泛研究[12,13,9,3,11,25,4,5,17]。 在一项开创性的工作[12]中，Jerrum 和 Sinclair 为铁磁 Ising 模型设计了完全多项式时间随机逼近方案 (FPRAS)。 后来在[10]中，通过将参数转换为铁磁伊辛模型，将 FPRAS 扩展到所有二态铁磁自旋系统。 同样在[10]中，Goldberg、Jerrum 和 Paterson 给出了任意图上两态反铁磁自旋系统的 FPRAS 和不可逼近性结果。 Dyer、Frieze 和 Jerrum 在 [4] 中提出了一种基于随机正则二部图的小工具，Mossel、Weitz 和 Wormald 在 [19] 中也对此进行了分析研究有界图上的不可逼近性。 人们普遍认为，反铁磁自旋系统的近似性转变是由无限树上的唯一性相变捕获的。 这是在[19]中作为猜想公开提出的。 Sly在[23]中针对硬核模型证明了该猜想。 Galanis 等人在[6]中将该结果改进为多种参数。 最近，Sly 和 Sun [24] 证明了无限正则树上所有非唯一二态反铁磁自旋系统的硬度。 Galanis、S̆tefankovic̆ 和 Vigoda 在[7]中独立证明了无外场反铁磁 Ising 模型的相同结果。

由 Weitz [26] 以及 Bandyopadhyay 和 Gamarnik [1] 独立开发的相关衰减技术是设计分区的确定性完全多项式时间近似方案 (FPTAS) 的强大工具函数（其他重要示例包括 [8, 2])。 在[26]中，Weitz引入了强空间混合的概念，并用它为硬核模型设计了达到唯一性阈值的FPTAS。 Sinclair、Srivastava 和 Thurley 最近在[21]中研究了另一个最重要的二态反铁磁自旋系统，即反铁磁伊辛模型，其中提出了一种更强大的消息衰减方法引入来分析强烈的空间混合并使 FPTAS 达到唯一性阈值。 Restrepo 等人在[20]中开发了一种强大的技术，它利用图的特定结构进行强空间混合。 通过利用图的结构，在网格上实现了比唯一性区域更广泛的可处理区域。 在之前的工作[15]中，我们给出了在具有无界度的任意图上无外场的二态反铁磁自旋系统的FPTAS，直到唯一性阈值的连续松弛。 本文使用的方法是在[15]中提出的，但是[15]中的分析无法在一定程度上分离唯一性，因此无法处理程度有界图族。

2 定义和基本知识

两态自旋系统由图$G=(V,E)$描述。 系统的配置是顶点状态的$2^{|V|}$可能分配$\sigma :V\to \{0,1\}$之一。 我们还使用蓝色和绿色两种颜色来表示这两种状态。 配置的权重可以描述为各个边和顶点的贡献的乘积。 让 和 $b=(b_0,b_1)$。 配置$\sigma :V\to \{0,1\}$的权重由下式给出

$w(\sigma )={\displaystyle \prod _{(u,v)\in E}}{A}_{\sigma (u),\sigma (v)}{\displaystyle \prod _{v\in V}}{b}_{\sigma (v)}.$

吉布斯测度是$\rho (\sigma )=\frac{w(\sigma )}{Z(G)}$定义的所有配置的概率分布。 归一化因子$Z(G)={\sum }_{\sigma }w(\sigma )$称为配分函数。

我们可以将 $\{\mathrm{𝚋𝚕𝚞𝚎},\mathrm{𝚐𝚛𝚎𝚎𝚗}\}$ 边和绿色顶点的贡献标准化为 1。 因此 代表某些 $\beta ,\gamma \ge 0$,$b=(b_0,b_1)=(\lambda ,1)$ 代表某些 $\lambda >0$。 由于蓝色和绿色的角色是对称的，我们可以假设$\beta \le \gamma$而不失一般性。 三个参数$(\beta ,\gamma ,\lambda )$与$0\le \beta \le \gamma$和$\lambda >0$完全指定了一个二态自旋系统。 具有$\beta =\gamma$的二态自旋系统是伊辛模型，具有$\beta =0,\gamma =1$或对称$\beta =1,\gamma =0$的二态自旋系统是硬核模型。

如果相邻顶点有利于不同的自旋，即如果，则二态自旋系统称为反铁磁。 不失一般性，我们重点关注$\beta \le \gamma$的情况。

Definition 4。

$(\beta ,\gamma ,\lambda )$ 如果$0\le \beta \le \gamma$、$\gamma >0$、和$\lambda >0$，则为反铁磁。

通过 $\beta$ 和 $\gamma$ 的对称性以及情况 $\beta =\gamma =0$ 的平凡性，对于所有非平凡的二态反铁磁系统，该定义是完整的

2.1相关性衰减

吉布斯测度定义了每个顶点的状态边缘分布。 让 $p_v$ 表示顶点 $v$ 被着色为蓝色的概率。 令 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 为 $\mathrm{\Lambda }\subset V$ 的配置。 我们将顶点$v\in \mathrm{\Lambda }$ 固定顶点称为$v\notin \mathrm{\Lambda }$自由顶点。 我们使用$p_v^{{\sigma }_{\mathrm{\Lambda }}}$表示在$\mathrm{\Lambda }$的配置固定为${\sigma }_{\mathrm{\Lambda }}$的条件下$v$被着色为蓝色的边际概率。

Definition 5。

如果对于图族中的任意图 $G=(V,E)$、任意 $v\in V,\mathrm{\Lambda }\subset V$ 和 ${\sigma }_{\mathrm{\Lambda }},{\tau }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 来说，图族上的自旋系统具有 强空间混合性、

$|p_v^{{\sigma }_{\mathrm{\Lambda }}}-p_v^{{\tau }_{\mathrm{\Lambda }}}|\le \exp (-\mathrm{\Omega }(\mathrm{dist}(v,S))),$

其中 $S\subset \mathrm{\Lambda }$ 是 ${\sigma }_{\mathrm{\Lambda }}$ 和 ${\tau }_{\mathrm{\Lambda }}$ 不同的子集，$\mathrm{dist}(v,S)$ 是距 $v$ 的最短距离到 $S$ 中的任意顶点。

弱空间混合可以通过测量相对于$\mathrm{dist}(v,\mathrm{\Lambda })$而不是$\mathrm{dist}(v,S)$的衰减来定义。 空间混合特性在统计物理学中也称为相关衰减。

令 $T$ 为一棵以 $v$ 为根的树。将 $R_T^{{\sigma }_{\mathrm{\Lambda }}}=p_v^{{\sigma }_{\mathrm{\Lambda }}}/(1-p_v^{{\sigma }_{\mathrm{\Lambda }}})$ 定义为在施加条件 ${\sigma }_{\mathrm{\Lambda }}$ 时根 $v$ 为蓝色和绿色的概率之间的比率（约定为 $R_T^{{\sigma }_{\mathrm{\Lambda }}}=\mathrm{\infty }$ 当 $p_v^{{\sigma }_{\mathrm{\Lambda }}}=1$ 时）。 假设 $v$ 有 $d$ 个子级，并且 $T_i$ 是以第 $i$ 个子级为根的子树。 由于子树的独立性，我们有一个简单的递归来计算$R_T^{{\sigma }_{\mathrm{\Lambda }}}$：

$R_T^{{\sigma }_{\mathrm{\Lambda }}}$ $=\lambda {\displaystyle \prod _{i=1}^d}{\displaystyle \frac{\beta R_{T_i}^{{\sigma }_{\mathrm{\Lambda }}}+1}{R_{T_i}^{{\sigma }_{\mathrm{\Lambda }}}+\gamma }}.$ (1)

令 $G(V,E)$ 为图表。 类似地定义$R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}=p_v^{{\sigma }_{\mathrm{\Lambda }}}/(1-p_v^{{\sigma }_{\mathrm{\Lambda }}})$。 与树的情况相反，由于循环引起的依赖性，对于一般图$G$来说，计算$R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}$并不容易。 在[26]中，引入了一种称为自回避游走（SAW）树的结构，它将一般图中边缘分布的计算减少到树中的计算。 具体来说，给定一个图 $G(V,E)$ 和一个顶点 $v\in V$。 SAW 树 $T_{\text{SAW}}(G,v)$ 是一棵以 $v$ 为根的树，具有新的顶点集 $V_{\text{SAW}}$（它有效地枚举了源自 $v$ 的所有路径） $G$ 并且可能包括固定叶子）。 此外，任何顶点集$S\subset \mathrm{\Lambda }\subset V$都映射到相应的$S_{\text{SAW}}\subset {\mathrm{\Lambda }}_{\text{SAW}}\subset V_{\text{SAW}}$，任何配置${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$都映射到${\sigma }_{{\mathrm{\Lambda }}_{\text{SAW}}}\in {\{0,1\}}^{{\mathrm{\Lambda }}_{\text{SAW}}}$。 如果不会引起歧义，我们会滥用这种表示法并编写 $S=S_{\text{SAW}}$ 和 ${\sigma }_{\mathrm{\Lambda }}={\sigma }_{{\mathrm{\Lambda }}_{\text{SAW}}}$。 给定图形 $G(V,E)$、$v\in V$ 和 $S\subset V$，令 ${\mathrm{dist}}_G(v,S)$ 为 $G$ 中距 $v$ 到 $S$ 中的任意顶点。

Theorem 6 （Weitz定理3.1[26])。

令 $G(V,E)$ 为图形，$v\in V$、${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 为 $\mathrm{\Lambda }\subset V$ 上的配置，以及 $S\subset V$。 让$T=T_{\mathrm{SAW}}(G,v)$。 其认为$T$的最大阶数等于$G$、${\mathrm{dist}}_G(v,S)={\mathrm{dist}}_T(v,S)$和$R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}=R_T^{{\sigma }_{\mathrm{\Lambda }}}$的最大阶数。 此外，$T$ 中 $v$ 的任何邻域都可以在与邻域大小成正比的时间内构建。

2.2 唯一性条件

我们考虑无限 $(d+1)$ 不规则树 ${\widehat{𝕋}}^d$ 上吉布斯度量的唯一性，其中由于 ${\widehat{𝕋}}^d$ 的对称结构，递归由 $f_d(x)\triangleq \lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d$ 给出。

设${\widehat{x}}_d$为$f_d(x)$的正不动点，即${\widehat{x}}_d=f({\widehat{x}}_d)$。 已知[14, 18],${\widehat{𝕋}}^d$上的二态反铁磁自旋系统在$|f_d^{\prime }({\widehat{x}}_d)|=1$处发生相变，并且当$|f_d^{\prime }({\widehat{x}}_d)|\le 1$。 这引发了以下定义。

Definition 7。

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 设${\widehat{x}}_d$为函数$f_d(x)=\lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d$的正不动点。我们说 $(\beta ,\gamma ,\lambda )$ 是 up-to-$\mathrm{\Delta }$ 唯一的，如果对于所有整数 ，

特别是，如果$(\beta ,\gamma ,\lambda )$是最多$\mathrm{\infty }$唯一，那么它就是普遍唯一。

达到$\mathrm{\Delta }$的唯一性相当于系统在无限正则树上的弱空间混合达到$\mathrm{\Delta }$度。 唯一性条件可以用各种阈值形式来描述，在附录A中给出。

唯一性是通过要求 来定义的。 以下引理指出，只要唯一性条件成立，$|f_d^{\prime }({\widehat{x}}_d)|$ 就受到绝对常数的限制。

Lemma 8.

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 如果 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一，则存在一个绝对常数 ，它仅取决于 $\beta$、$\gamma$、$\lambda$ 和 $\mathrm{\Delta }$，例如 $|f_d^{\prime }({\widehat{x}}_d)|\le c$ 适用于所有 。

证明。

对于有限的$\mathrm{\Delta }$，引理是微不足道的。 接下来需要证明的是，在普遍唯一性的情况下，随着 $d$ 增长到无穷大，$|f_d^{\prime }({\widehat{x}}_d)|$ 不能任意接近 1。 如果$(\beta ,\gamma ,\lambda )$是普遍唯一的，由于引理21.2，我们必须有$\gamma >1$。 对于反铁磁$(\beta ,\gamma ,\lambda )$,$\beta \le \frac{1}{\gamma }$，因此固定点${\widehat{x}}_d=\lambda {\left(\frac{\beta {\widehat{x}}_d+1}{{\widehat{x}}_d+\gamma }\right)}^d\le \frac{\lambda }{{\gamma }^d}$，因此$|f_d^{\prime }({\widehat{x}}_d)|=\frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}\le \frac{d\lambda }{{\gamma }^d}$。 引理如下。 ∎

3 一般图上的强空间混合

本节我们证明定理1。 唯一性条件的必要性是微不足道的，因为一般图上的强空间混合意味着常规树上的弱空间混合。 接下来就剩下证明下面的定理了。

Theorem 9。

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 对于任何有限的$\mathrm{\Delta }\ge 2$或$\mathrm{\Delta }=\mathrm{\infty }$，如果$(\beta ,\gamma ,\lambda )$最多是$\mathrm{\Delta }$唯一，则参数的二态自旋系统$(\beta ,\gamma ,\lambda )$在最多$\mathrm{\Delta }$的最大度图上具有强空间混合。

我们的方法是证明任意树上最大度至多$\mathrm{\Delta }$的强空间混合，这通过自回避游走树构造隐含了定理。 请注意，与 [26] 和 [21] 不同，我们分析任意树而不是常规树的衰减。 这是因为对于一般的二态反铁磁自旋系统，最大程度$d$的所有图之间强空间混合的最坏情况可能不再是$d$-正则树。 我们将在5节中详细解释这一点。

给定最大度最多为 $\mathrm{\Delta }$ 的任意图 $G(V,E)$、$\mathrm{\Lambda }\subset V$ 上的任意配置 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 和任意 $S\subset \mathrm{\Lambda }$，固定任意顶点 $v\in V$、根据定理 6，可以构造一棵自避走树 $T=T_{\text{SAW}}(G,v)$，使得 $T$ 的最大度受 $\mathrm{\Delta }$、${\mathrm{dist}}_G(v,S)={\mathrm{dist}}_T(v,S)$ 和 $R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}=R_T^{{\sigma }_{\mathrm{\Lambda }}}$ 的约束。 回想一下 $R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}=p_v^{{\sigma }_{\mathrm{\Lambda }}}/(1-p_v^{{\sigma }_{\mathrm{\Lambda }}})$ 因此 $p_v^{{\sigma }_{\mathrm{\Lambda }}}=R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}/(1+R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}})$。 对于任何 ${\sigma }_{\mathrm{\Lambda }}$ 和 ${\tau }_{\mathrm{\Lambda }}$，

$\left|p_v^{{\sigma }_{\mathrm{\Lambda }}}-p_v^{{\tau }_{\mathrm{\Lambda }}}\right|=\left|{\displaystyle \frac{R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}}{1+R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}}}-{\displaystyle \frac{R_{G,v}^{{\tau }_{\mathrm{\Lambda }}}}{1+R_{G,v}^{{\tau }_{\mathrm{\Lambda }}}}}\right|\le \left|R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}-R_{G,v}^{{\tau }_{\mathrm{\Lambda }}}\right|=\left|R_T^{{\sigma }_{\mathrm{\Lambda }}}-R_T^{{\tau }_{\mathrm{\Lambda }}}\right|.$

这引发了以下定义。

Definition 10。

令 $T$ 为以顶点 $v$ 为根的树，${\tau }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$ 为 $\mathrm{\Lambda }\subset V$ 上的配置，$S\subseteq \mathrm{\Lambda }$ 为顶点集。 将 $R_v$ 和 ${\delta }_v$ 定义为：对于所有 ${\sigma }_{\mathrm{\Lambda }}\in {\{0,1\}}^{\mathrm{\Lambda }}$，$R_v\le R_T^{{\tau }_{\mathrm{\Lambda }}}\le R_v+{\delta }_v$ 只在 $S$ 上与 ${\tau }_{\mathrm{\Lambda }}$ 不同。

通过为 $T=T_{\text{SAW}}(G,v)$ 构造这样的 $R_v$ 和 ${\delta }_v$ 并证明 ${\delta }_v\le \exp (-\mathrm{\Omega }(\mathrm{dist}(v,S)))$ 就足以证明定理 9 >。

令 $T$ 为一棵以 $v$ 为根的树，它有 $d$ 个子节点 $v_1,\mathrm{\dots },v_d$,$T_i$ 为子树以 $v_i$ 为根。 它认为

$R_T^{{\sigma }_{\mathrm{\Lambda }}}$ $=f(R_{T_1}^{{\sigma }_{\mathrm{\Lambda }}},\mathrm{\dots },R_{T_d}^{{\sigma }_{\mathrm{\Lambda }}})\triangleq \lambda {\displaystyle \prod _{i=1}^d}{\displaystyle \frac{\beta R_{T_i}^{{\sigma }_{\mathrm{\Lambda }}}+1}{R_{T_i}^{{\sigma }_{\mathrm{\Lambda }}}+\gamma }}.$

下限和上限$R_v$和$R_v+{\delta }_v$可以递归地构造如下。 基本情况是： (1) $v\in S$，在这种情况下$R_v=0$和${\delta }_v=\mathrm{\infty }$； (2) $v\in \mathrm{\Lambda }\setminus S$，即$v$固定为所有${\sigma }_{\mathrm{\Lambda }}$中相同的颜色，此时${\delta }_v=0$和$R_v=\mathrm{\infty }$（或$R_v=0$)如果$v$固定为蓝色（或绿色）。 对于$v\notin \mathrm{\Lambda }$，由于$f(R_1,\mathrm{\dots },R_d)$对于反铁磁$(\beta ,\gamma ,\lambda )$是单调递减的，

$R_v$ $=f(R_{v_1}+{\delta }_{v_1},\mathrm{\dots },R_{v_d}+{\delta }_{v_d}),$

$R_v+{\delta }_v$ $=f(R_{v_1},\mathrm{\dots },R_{v_d}),$

其中 $R_{v_i}$ 和 $R_{v_i}+{\delta }_{v_i}$ 是 $R_{T_i}^{{\sigma }_{\mathrm{\Lambda }}}$、$1\le i\le d$ 相应的下限和上限。 特别是，当$d=0$时，按照惯例，空乘积等于1，因此$R_v=R_v+{\delta }_v=\lambda$，这与$v$是没有子节点的自由顶点的情况一致。

通过$f(R_1,\mathrm{\dots },R_d)$的单调性，很容易检验上面构造的$R_v$和$R_v+{\delta }_v$是否满足定义10的要求。 我们的目标是证明，当唯一性成立时，${\delta }_v$ 的递归深度呈指数衰减。 一种简单的方法是尝试证明 $\delta$ 在每个递归步骤中以恒定速率收缩。 但这不一定是真的才能保证指数衰减。 事实上，在某些情况下，误差不会单步衰减，而是长期衰减。 为了克服这个问题，我们使用潜力 $\mathrm{\Phi }$来摊销收缩并表明$\delta \cdot \mathrm{\Phi }$以恒定速率收缩。 我们选择势函数为

$\mathrm{\Phi }(R)={\displaystyle \frac{1}{\sqrt{R(\beta R+1)(R+\gamma )}}}.$

我们正在分析任意树上具有不规则程度的腐烂。 为了适应这种不规则性，势函数不能以$d$作为输入，而只能携带有关当前顶点的分布信息，但它必须能够为步骤提供正确的补偿 -在 $R$ 的任何状态下以及对于满足足够唯一性的所有自旋系统而言，明智的衰减。 附录C中讨论了引导我们得到这个良好势函数的启发式过程。

令$\phi (R)$为满足${\phi }^{\prime }(R)=\mathrm{\Phi }(R)$的单调函数。 我们定义

${ϵ}_v\triangleq \phi (R_v+{\delta }_v)-\phi (R_v),$

相应地，${ϵ}_{v_i}\triangleq \phi (R_{v_i}+{\delta }_{v_i})-\phi (R_{v_i})$、$1\le i\le d$。

我们定义一个函数$\alpha (d;x_1,\mathrm{\dots },x_d)$如下：

$\alpha (d;x_1,\mathrm{\dots },x_d)$ $\triangleq {\displaystyle \frac{(1-\beta \gamma ){\left(\lambda {\prod }_{i=1}^d\frac{\beta x_i+1}{x_i+\gamma }\right)}^{\frac{1}{2}}}{{\left(\beta \lambda {\prod }_{i=1}^d\frac{\beta x_i+1}{x_i+\gamma }+1\right)}^{\frac{1}{2}}{\left(\lambda {\prod }_{i=1}^d\frac{\beta x_i+1}{x_i+\gamma }+\gamma \right)}^{\frac{1}{2}}}}\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{x_i^{\frac{1}{2}}}{{(\beta x_i+1)}^{\frac{1}{2}}{(x_i+\gamma )}^{\frac{1}{2}}}}.$

以下引理是通过应用中值定理获得的。 之前在 [15, 20] 中使用了类似的例程。 引理的证明在附录B中。

Lemma 11.

以下内容适用于${ϵ}_v$。

1. （与${\delta }_v$相关） ${ϵ}_v={\delta }_v\cdot \mathrm{\Phi }(\tilde{R})$对于某些$\tilde{R}\in [R_v,R_v+{\delta }_v]$.

2. （绝对界限） 假设 $\gamma >1$ 或 $T$ 的最大度以常数为界，如果 $v\notin \mathrm{\Lambda }$ 则 $R_v+{\delta }_v=O(1)$ ，如果 $v_i\notin S$ 对于所有 $1\le i\le d$ 则 ${ϵ}_v=O(1)$ 。

3. （逐步收缩）存在$\widetilde{R_i}\in [R_{v_i},R_{v_i}+{\delta }_{v_i}]$,$1\le i\le d$，使得

   ${ϵ}_v\le \alpha (d;{\tilde{R}}_1,\mathrm{\dots },{\tilde{R}}_d)\cdot \underset{1\le i\le d}{\max }\{{ϵ}_{v_i}\}.$

To prove the strong spatial mixing, we first relate ${\delta }_v$ to ${ϵ}_v$ by Item 1 of Lemma 11, and then apply induction on the depth in $T$, with Item 2 of Lemma 11 as basis and Item 3 of Lemma 11 as induction step. 然后我们需要限制收缩率$\alpha (d;x_1,\mathrm{\dots },x_d)$。 请注意，$\frac{z}{(\beta z+1)(z+\gamma )}\le {\left(1+\sqrt{\beta \gamma }\right)}^{-2}\le 1$ 对于 $z\in [0,\mathrm{\infty })$，因此它无条件地适用于所有 $x_i\in [0,\mathrm{\infty })$、$1\le i\le d$，即

$\alpha (d;x_1,\mathrm{\dots },x_d)$ $\le d,$ (2)

$\alpha (d;x_1,\mathrm{\dots },x_d)$ $\le d\cdot \sqrt{{\displaystyle \frac{\lambda }{{\gamma }^{d+1}}}}.$ (3)

凭借唯一性，可以证明以下更紧的收缩界。

Lemma 12.

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 如果 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一，则存在一个常量 ，使得对于任何整数 和任何 $x_1,\mathrm{\dots },x_d\in [0,+\mathrm{\infty })$、$1\le i\le d$，则成立$\alpha (d;x_1,\mathrm{\dots },x_d)\le \alpha$。

这个引理是我们分析的技术核心。 它关键取决于势函数的选择。 在深入研究引理12的形式证明之前，我们注意到该引理可以隐含定理9。

定理证明9。

令 $T=T_{\text{SAW}}(G,v)$ 为 $G$，其最大度数至多为 $\mathrm{\Delta }$。 那么 $T$ 的最大度最多为 $\mathrm{\Delta }$，因此根 $v$ 在 $T$ 中最多有 $\mathrm{\Delta }$ 个子顶点，而 $T$ 中的每个其他顶点都有少于 $\mathrm{\Delta }$ 个子顶点。 我们为 $T$ 中的每个子树递归构造 $R_u$、${\delta }_u$ 和 ${ϵ}_u$。

让$t=\mathrm{dist}(v,S)$。 在不损失一般性的前提下，反复应用例题 11 的 3 项，我们在 $T$ 中有一条路径 $u_1{u}_2\mathrm{\cdots }{u}_{t-2}$ 与 $u_1=v$，使得 ${ϵ}_{u_j}\le \alpha (d_j;x_1,\mathrm{\dots },x_{d_j})\cdot {ϵ}_{u_{j+1}}$ 对于 $j=1,2,\mathrm{\dots },t-3$，其中 $d_j$ 是 $u_j$ 和 $x_i\in [0,\mathrm{\infty })$ 的子节点数，$1\le i\le d_j$。

请注意，$d_1\le \mathrm{\Delta }$ 和 代表所有其他 $j$。 假设 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 是唯一的。 如果 $\mathrm{\Delta }$ 是有界的，那么根据定理 12，存在一个常数 ，使得 ${ϵ}_{u_j}\le \alpha \cdot {ϵ}_{u_{j+1}}$ 对于 $2\le j\le t-3$，并且 ${ϵ}_v\le d_1\cdot {ϵ}_{u_2}\le \mathrm{\Delta }\cdot {ϵ}_2$ 由于 (2)；如果 $\mathrm{\Delta }=\mathrm{\infty }$，那么根据定理 12，对于所有 $1\le j\le t-3$ ${ϵ}_{u_j}\le \alpha \cdot {ϵ}_{u_{j+1}}$。 在这两种情况下我们都有${ϵ}_v=O({\alpha }^t\cdot {ϵ}_{u_{t-2}})$。

由于引理 11 的第 1 项，${\delta }_v=\frac{{ϵ}_v}{\mathrm{\Phi }(\tilde{R})}=O\left(\frac{1}{\mathrm{\Phi }(\tilde{R})}\cdot {\alpha }^t{ϵ}_{u_{t-2}}\right)$ 对于某些 $\tilde{R}\in [R_v,R_v+{\delta }_v]$ 而言。 然后我们绑定$\mathrm{\Phi }(\tilde{R})$和${ϵ}_{u_{t-2}}$。 由于引理 21 的项 2,$(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 唯一这一事实意味着 $\mathrm{\Delta }$ 是有界的或 $\gamma >1$。 请注意，$v$ 必须是自由的，否则该定理的证明很简单，并且 $u_{t-2}$ 的子级都不在 $S$ 中，因为 $\mathrm{dist}(v,S)=t$ 。 因此，根据引理11、${ϵ}_{u_{t-2}}=O(1)$和$\tilde{R}\le R_v+{\delta }_v=O(1)$的项2，这意味着$\mathrm{\Phi }(\tilde{R})=\frac{1}{\sqrt{\tilde{R}(\beta \tilde{R}+1)(\tilde{R}+\gamma )}}=\mathrm{\Omega }(1)$。

总之，如果$(\beta ,\gamma ,\lambda )$最多是$\mathrm{\Delta }$唯一，则存在一个常量，使得${\delta }_v=O\left({\alpha }^t\right)$。 正如本节开头所讨论的，这证明了定理 9。

引理12的证明。

本节的其余部分致力于引理 12 的证明。 鉴于 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，因此存在绝对常数 ，使得 $\alpha (d;x_1,\mathrm{\dots },x_d)\le \alpha$ 对于任何 和 $x_1,\mathrm{\dots },x_d\ge 0$。

我们定义 $\alpha (d;x_1,\mathrm{\dots },x_d)$ 的对称版本：

${\alpha }_d(x)$ $\triangleq \alpha (d;\underset{d}{\underbrace{x,\mathrm{\dots },x}})={\displaystyle \frac{d(1-\beta \gamma ){\left(x\cdot \lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d\right)}^{\frac{1}{2}}}{{(\beta x+1)}^{\frac{1}{2}}{(x+\gamma )}^{\frac{1}{2}}{\left(\beta \lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d+1\right)}^{\frac{1}{2}}{\left(\lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d+\gamma \right)}^{\frac{1}{2}}}}.$

以下引理表明，通过使用 Cauchy-Schwarz 不等式以及算术和几何平均值，对称情况主导 $\alpha (d;x_1,\mathrm{\dots },x_d)$ 的最大值。

Lemma 13.

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 那么对于任何整数$d$和任何$x_1,\mathrm{\dots },x_d\in [0,+\mathrm{\infty })$，都存在一个$\overline{x}\in [0,+\mathrm{\infty })$使得$\alpha (d;x_1,\mathrm{\dots },x_d)\le \alpha (d,\overline{x})$。

证明。

让$z_i=\frac{\beta x_i+1}{x_i+\gamma }$。 然后是$z_i\in (\beta ,\frac{1}{\gamma }]$和$x_i=\frac{1-\gamma z_i}{z_i-\beta }$。 用$z_i$表达$\alpha (d;x_1,\mathrm{\dots },x_d)$：

$\alpha (d;x_1,\mathrm{\dots },x_d)$ $={\displaystyle \frac{{\left(\lambda {\prod }_{i=1}^d{z}_i\right)}^{\frac{1}{2}}}{{\left(\beta \lambda {\prod }_{i=1}^d{z}_i+1\right)}^{\frac{1}{2}}{\left(\lambda {\prod }_{i=1}^d{z}_i+\gamma \right)}^{\frac{1}{2}}}}\cdot {\displaystyle \sum _{i=1}^d}{(z_i^{-1}-\gamma )}^{\frac{1}{2}}{(z_i-\beta )}^{\frac{1}{2}}.$

由于柯西-施瓦茨不等式，

${\displaystyle \sum _{i=1}^d}{(z_i^{-1}-\gamma )}^{\frac{1}{2}}{(z_i-\beta )}^{\frac{1}{2}}\le d{\left({\displaystyle \frac{1}{d}}{\displaystyle \sum _{i=1}^d}(z_i^{-1}-\gamma )(z_i-\beta )\right)}^{\frac{1}{2}}=d{\left(1+\beta \gamma -{\displaystyle \frac{1}{d}}{\displaystyle \sum _{i=1}^d}(z_i\gamma +\beta z_i^{-1})\right)}^{\frac{1}{2}}.$

由于算术平均值和几何平均值不等式，

$d{\left(1+\beta \gamma -{\displaystyle \frac{1}{d}}{\displaystyle \sum _{i=1}^d}(z_i\gamma +\beta z_i^{-1})\right)}^{\frac{1}{2}}$ $\le d{\left(1+\beta \gamma -\gamma {\left({\displaystyle \prod _{i=1}^d}{z}_i\right)}^{\frac{1}{d}}-\beta {\left({\displaystyle \prod _{i=1}^d}{z}_i\right)}^{-\frac{1}{d}}\right)}^{\frac{1}{2}}.$

让$\overline{z}={\left({\prod }_{i=1}^d{z}_i\right)}^{\frac{1}{d}}$。 然后结合上面的计算，

$\alpha (d;x_1,\mathrm{\dots },x_d)$ $\le {\displaystyle \frac{{(\lambda {\overline{z}}^d)}^{\frac{1}{2}}\cdot d{(1+\beta \gamma -\gamma \overline{z}-\beta {\overline{z}}^{-1})}^{\frac{1}{2}}}{{(\beta \lambda {\overline{z}}^d+1)}^{\frac{1}{2}}{(\lambda {\overline{z}}^d+\gamma )}^{\frac{1}{2}}}}=d\cdot \sqrt{{\displaystyle \frac{\lambda {\overline{z}}^d({\overline{z}}^{-1}-\gamma )(\overline{z}-\beta )}{(\beta \lambda {\overline{z}}^d+1)(\lambda {\overline{z}}^d+\gamma )}}}.$

假设 $\overline{x}$ 是 $\frac{\beta \overline{x}+1}{\overline{x}+\gamma }=\overline{z}$。 然后 $\overline{x}\in [0,+\mathrm{\infty })$ 并用 $\frac{\beta \overline{x}+1}{\overline{x}+\gamma }$ 替换 $\overline{z}$，我们有

$\alpha (d;x_1,\mathrm{\dots },x_d)$ $\le {\displaystyle \frac{d(1-\beta \gamma ){\left(\overline{x}\cdot \lambda {\left(\frac{\beta \overline{x}+1}{\overline{x}+\gamma }\right)}^d\right)}^{\frac{1}{2}}}{{(\beta \overline{x}+1)}^{\frac{1}{2}}{(\overline{x}+\gamma )}^{\frac{1}{2}}{\left(\beta \lambda {\left(\frac{\beta \overline{x}+1}{\overline{x}+\gamma }\right)}^d+1\right)}^{\frac{1}{2}}{\left(\lambda {\left(\frac{\beta \overline{x}+1}{\overline{x}+\gamma }\right)}^d+\gamma \right)}^{\frac{1}{2}}}}={\alpha }_d(\overline{x}).$

∎

Lemma 14.

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 如果 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一，则存在一个常量 ，这样对于任何整数 ，它都满足${\alpha }_d(x)\le \alpha$ 对于所有 $x\ge 0$。

证明。

将 $d$ 固定为任意正整数。 我们描述 ${\alpha }_d(x)$ 达到最大值时 $x$ 的值。 我们表示$f_d(x)=\lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d$。对 ${\alpha }_d(x)$ 对 $x$ 求导，我们得到

${\alpha }_d^{\prime }(x)=d(1-\beta \gamma )\cdot {\displaystyle \frac{G^{\prime }(x)}{2\sqrt{G(x)}}},$

其中$G(x)=\frac{x{f}_d(x)}{(\beta f_d(x)+1)(f_d(x)+\gamma )(\beta x+1)(x+\gamma )}$，其导数为

$G^{\prime }(x)$ $={\displaystyle \frac{f_d(x)\cdot d(1-\beta \gamma )x}{(\beta f_d(x)+1)(f_d(x)+\gamma ){(\beta x+1)}^2{(x+\gamma )}^2}}\cdot \left({\displaystyle \frac{\gamma -\beta x^2}{d(1-\beta \gamma )x}}-{\displaystyle \frac{\gamma -\beta f_d{(x)}^2}{(\beta f_d(x)+1)(f_d(x)+\gamma )}}\right).$

由于 $x$ 的范围超过 $[0,\mathrm{\infty })$，因此函数 $\frac{\gamma -\beta x^2}{d(1-\beta \gamma )x}$ 在 $x$ 中严格递减，范围从 $+\mathrm{\infty }$ 到 $-\mathrm{\infty }$，函数$\frac{\gamma -\beta f_d{(x)}^2}{\left(\beta f_d(x)+1\right)\left(f_d(x)+\gamma \right)}$在$x$中严格递增，并且有一个有界范围。 因此，方程

${\displaystyle \frac{\gamma -\beta x^2}{d(1-\beta \gamma )x}}$ $={\displaystyle \frac{\gamma -\beta f_d{(x)}^2}{\left(\beta f_d(x)+1\right)\left(f_d(x)+\gamma \right)}}.$ (4)

$(0,\mathrm{\infty })$有唯一解，记为$x_d$。 此外，它认为

(5)

对于${\alpha }_d^{\prime }(x)$也是如此。 因此，对于任何固定的$d$,${\alpha }_d(x)$在$x=x_d$时达到最大值。

因此，对于所有$x\ge 0$，

${\alpha }_d(x)\le {\alpha }_d(x_d)$ $=d(1-\beta \gamma ){\left({\displaystyle \frac{x_d{f}_d(x_d)}{(\beta x_d+1)(x_d+\gamma )\left(\beta f_d(x_d)+1\right)\left(f_d(x_d)+\gamma \right)}}\right)}^{\frac{1}{2}}$

$={\left(d(1-\beta \gamma )\cdot {\displaystyle \frac{(\gamma -\beta x_d^2)}{(\beta x_d+1)(x_d+\gamma )}}\cdot {\displaystyle \frac{f_d(x_d)}{\left(\gamma -\beta f_d{(x_d)}^2\right)}}\right)}^{\frac{1}{2}}$ (6)

$\triangleq {\tilde{\alpha }}_d(x_d).$

将$\left(\beta f_d(x_d)+1\right)\left(f_d(x_d)+\gamma \right)$代入(4)，得到式(6)。

设${\widehat{x}}_d$为$f_d(x)$的正不动点，即${\widehat{x}}_d=f_d({\widehat{x}}_d)$。 然后我们声称，如果 $(\beta ,\gamma ,\lambda )$ 最多是 $\mathrm{\Delta }$ 唯一，则对于任何整数 ,${\tilde{\alpha }}_d(x_d)\le {\tilde{\alpha }}_d({\widehat{x}}_d)$ 是唯一的，要看到这个声明足以暗示引理，请注意，替换 ${\widehat{x}}_d=f_d({\widehat{x}}_d)$ 后，我们有 ${\tilde{\alpha }}_d({\widehat{x}}_d)=\sqrt{\frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}}=\sqrt{\left|f_d^{\prime }({\widehat{x}}_d)\right|}$。 并且由于引理 8，如果 $(\beta ,\gamma ,\lambda )$ 最多是 $\mathrm{\Delta }$ 唯一，则存在一个常量 使得 对于所有整数 。

然后我们证明这一主张。 假设 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 是唯一的且 。 那么足以证明，如果 ${\widehat{x}}_d\le x_d$，则 正在减少，如果 ${\widehat{x}}_d>x_d$，则 ${\tilde{\alpha }}_d(x)$ 正在增加。

情况 1：${\widehat{x}}_d\le x_d$。 由于 (5)，$G^{\prime }({\widehat{x}}_d)\ge 0$。 注意

$G^{\prime }({\widehat{x}}_d)={\displaystyle \frac{d(1-\beta \gamma )(\gamma -\beta {\widehat{x}}_d^2){\widehat{x}}_d^2}{{(\beta {\widehat{x}}_d+1)}^3{({\widehat{x}}_d+\gamma )}^3}}\cdot \left({\displaystyle \frac{1}{d(1-\beta \gamma ){\widehat{x}}_d}}-{\displaystyle \frac{1}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}}\right).$

由于唯一性，，因此$\frac{1}{d(1-\beta \gamma ){\widehat{x}}_d}-\frac{1}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}>0$。 与 $G^{\prime }(x)\ge 0$ 结合，我们有 $\gamma -\beta {\widehat{x}}_d^2\ge 0$。 由于函数$f_d(x)$是单调递减的，并且${\widehat{x}}_d$是其不动点，因此$\gamma -\beta f_d{(x_d)}^2\ge \gamma -\beta f_d{({\widehat{x}}_d)}^2=\gamma -\beta {\widehat{x}}_d^2\ge 0$。 由于$x_d$满足(4)，$\gamma -\beta x_d^2$和$\gamma -\beta f_d{(x_d)}^2$必须同时为正或负，因此也成立$\gamma -\beta x_d^2\ge 0$。 那么$\frac{(\gamma -\beta x^2)}{(\beta x+1)(x+\gamma )}$和$\frac{f_d(x)}{\left(\gamma -\beta f_d{(x)}^2\right)}$都是正数，并且在$x\in [{\widehat{x}}_d,x_d]$中单调递减。 因此，${\tilde{\alpha }}_d(x_d)\le {\tilde{\alpha }}_d({\widehat{x}}_d)$。

情况 2：${\widehat{x}}_d>x_d$。 根据与上面相同的论证，它成立、和。 因此，$\frac{(\gamma -\beta x^2)}{(\beta x+1)(x+\gamma )}$和$\frac{f_d(x)}{\left(\gamma -\beta f_d{(x)}^2\right)}$都是负数，并且在$x\in [x_d,{\widehat{x}}_d]$中单调递减，因此它们的乘积是正数，并且在$x\in [x_d,{\widehat{x}}_d]$中递增。 因此，${\tilde{\alpha }}_d(x_d)\le {\tilde{\alpha }}_d({\widehat{x}}_d)$。 ∎

引理12是通过组合引理13和14来证明的。 这样就完成了定理9的证明。

普通树上的强烈空间混合。

作为我们分析的副产品，我们证明了规则树的强空间混合定理。 当图 $G$ 本身是一棵常规树时。 所有顶点（根除外）都具有相同的数量。 并且证明中出现的所有$d$（摘录根的一个）都相同且等于该元数。 那么度数达到$\mathrm{\Delta }$的所有无限正则树上唯一性成立的条件就可以用无限$\mathrm{\Delta }$正则树上的唯一性来代替。

Theorem 15。

对于二态反铁磁自旋系统，在任何无限$\mathrm{\Delta }$-正则树上，唯一性意味着强烈的空间混合。

结合硬核模型[26]和反铁磁Ising模型[21]的相同定理，并转换一般二态参数，可以得到相同的结果这些模型的反铁磁自旋系统（如[24, 21]中讨论）。 然而，与硬核模型和反铁磁 Ising 模型不同，对于一般二态反铁磁自旋系统，定理 15 本身不足以暗示最大程度图上的强空间混合 $\mathrm{\Delta }$。 这将在 5 节中讨论。

4 算法含义

本节我们证明定理2。 也就是说，如果反铁磁性 $(\beta ,\gamma ,\lambda )$ 到 $\mathrm{\Delta }$ 是唯一的，那么对于最大度最多为 $\mathrm{\Delta }$ 的任何图 $G$，存在分割函数 $Z(G)$ 的 FPTAS，特别是普遍唯一性意味着任意图 $G$ 的 FPTAS。

众所周知，$Z(G)$ 可以通过以下标准过程从 $p_v^{{\sigma }_{\mathrm{\Lambda }}}$ 计算得出。 让 $v_1,\mathrm{\dots },v_n$ 枚举 $G$ 中的顶点。对于 $0\le i\le n$，令 ${\sigma }_i$ 为固定第一个 $i$ 顶点 $v_1,\mathrm{\dots },v_i$ 的配置，如下所示： ${\sigma }_i(v_j)={\sigma }_{i-1}(v_j)$ for $1\le j\le i-1$和${\sigma }_i(v_i)$被固定，使得$p_i\triangleq \mathrm{Pr}[{\sigma }_i(v_i)\mid {\sigma }_{i-1}]\ge 1/3$。 特别是，${\sigma }_n\in {\{0,1\}}^V$ 是 $V$ 的配置。对于 ${\sigma }_n$ 的吉布斯度量，$\rho ({\sigma }_n)=p_1{p}_2\mathrm{\cdots }{p}_n$ 以及 $\rho ({\sigma }_n)=\frac{w({\sigma }_n)}{Z(G)}$都成立，因此 $Z(G)=\frac{w({\sigma }_n)}{p_1{p}_2\mathrm{\cdots }{p}_n}$，其中权重 $w({\sigma }_n)={\prod }_{(u,v)\in E}{A}_{{\sigma }_n(u),{\sigma }_n(v)}{\prod }_{v\in V}{b}_{{\sigma }_n(v)}$ 可以针对任何特定的 ${\sigma }_n$ 以 $n$ 的多项式时间精确计算。请注意，$p_i$ 等于 $p_{v_i}^{{\sigma }_{i-1}}$ 或 $1-p_{v_i}^{{\sigma }_{i-1}}$。 因此，如果$p_v^{{\sigma }_{\mathrm{\Lambda }}}$可以在$n$和$\frac{1}{ϵ}$中时间多项式的加性误差$ϵ$内近似，则配置${\sigma }_i$ 可以有效地构造，使得所有 $p_i$ 都远离 0，因此乘积 $p_1{p}_2\mathrm{\cdots }{p}_n$ 可以在时间上在 $(1\pm nϵ)$ 因子内近似$n$ 和 $\frac{1}{ϵ}$ 中的多项式，这意味着 $Z(G)$

有界度图。

令 $G$ 为最大度数至多为 $\mathrm{\Delta }$ 的图，$v$ 为任意顶点。 可以构造一棵自回避游走树$T=T_{\text{SAW}}(G,v)$，使得$R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}=R_T^{{\sigma }_{\mathrm{\Lambda }}}$。 我们可以使用3节中描述的递归过程来计算$R_T^{{\sigma }_{\mathrm{\Lambda }}}$的上下界，设置为对于所有大于$t$的顶点距离根 $v$ 几步远，使用简单边界 $0\le R_T^{{\sigma }_{\mathrm{\Lambda }}}\le \mathrm{\infty }$。 那么定理9的证明表明，递归过程返回$R_0$和$R_1$，使得$R_0\le R_T^{{\sigma }_{\mathrm{\Lambda }}}\le R_1$和$R_1-R_0=O({\alpha }^t)$ 对于一些常量 假设 $(\beta ,\gamma ,\lambda )$ 最多是 $\mathrm{\Delta }$ 唯一。 请注意$R_T^{{\sigma }_{\mathrm{\Lambda }}}=R_{G,v}^{{\sigma }_{\mathrm{\Lambda }}}=\frac{p_v^{{\sigma }_{\mathrm{\Lambda }}}}{1-p_v^{{\sigma }_{\mathrm{\Lambda }}}}$。 让 $p_0=\frac{R_0}{R_0+1}$ 和 $p_1=\frac{R_1}{R_1+1}$。 然后 $p_0\le p_v^{{\sigma }_{\mathrm{\Lambda }}}\le p_1$ 和

$p_1-p_0={\displaystyle \frac{R_1}{R_1+1}}-{\displaystyle \frac{R_0}{R_0+1}}\le R_1-R_0=O({\alpha }^t).$ (7)

递归过程在时间 $O({\mathrm{\Delta }}^t)$ 内运行，因为它只需要构造自回避游走树的前 $t$ 层。 如果$\mathrm{\Delta }$有界，通过设置$t={\log }_{\alpha }ϵ$，这给出了一个算法，该算法在时间多项式的加性误差$O(ϵ)$内逼近$p_v^{{\sigma }_{\mathrm{\Lambda }}}$$n$ 和 $\frac{1}{ϵ}$，这意味着 $Z(G)$ 的 FPTAS。

任意图形。

令 $G$ 为任意图，$v$ 为任意顶点。 让$T=T_{\text{SAW}}(G,v)$。 我们使用[15]中引入的计算高效相关性衰减方法来处理无界度。 直观上，使用这种方法，我们观察到精细度量中的相关性衰减，而不是图距离，这样在这个新度量中，中等大小的邻域足以保证所需的相关性衰减。

类似地，我们使用3节中描述的递归过程来计算$R_T^{{\sigma }_{\mathrm{\Lambda }}}$的上限和下限，但这次终止条件依赖于定义如下的新深度。

Definition 16。

令 $T$ 为有根树，$M>1$ 为常量。 对于 $T$ 中的任意顶点 $v$，定义 $v$ 的基于 $M$ 的深度，表示为 ${\mathrm{\ell }}_M(v)$：如果 $v$ 是根节点，则定义为 ${\mathrm{\ell }}_M(v)=0$；如果 $v$ 是 $u$ 的 $d$ 子节点之一，则定义为 ${\mathrm{\ell }}_M(v)={\mathrm{\ell }}_M(u)+\lceil {\log }_M(d+1)\rceil$。

让 $M>1$ 被修复。 用 $B(\mathrm{\ell })$ 表示具有基于 $M$ 的深度 的所有顶点及其在 $T$ 中的子代和孙子的集合。归纳起来可以验证$|B(\mathrm{\ell })|\le n^2{M}^{\mathrm{\ell }}$。 当当前$v\in B(\mathrm{\ell })$不在内时，递归将用于估计$R_T^{{\sigma }_{\mathrm{\Lambda }}}$，直到$v$不再在$B(\mathrm{\ell })$内，在这种情况下，将使用微分边界$0\le R_T^{{\sigma }_{\mathrm{\Lambda }}}\le \mathrm{\infty }$。

让 ${ϵ}_v$ 的定义如 3 节中所述。 重复应用定理 11 的 3 项，在不违背一般性的前提下，我们在 $T$ 中有一条路径 $u_1{u}_2\mathrm{\cdots }{u}_k$ 从根 $u_1=v$ 到 $u_k$ 的 ${\mathrm{\ell }}_M(u_k)\ge \mathrm{\ell }$ 和 、使得${ϵ}_{u_j}\le \alpha (d_j;x_1,\mathrm{\dots },x_{d_j})\cdot {ϵ}_{u_{j+1}}$为$j=1,2,\mathrm{\dots },k$，其中$d_j$为$u_j$和$x_i\in [0,\mathrm{\infty })$、$1\le i\le d_j$的子节点数。 克服无界度引起的爆炸的关键是观察收缩$\alpha (d;x_1,\mathrm{\dots },x_d)$随着度$d$的增加而急剧减小。

Lemma 17.

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 如果$(\beta ,\gamma ,\lambda )$满足通用唯一性，则存在常量和$M>1$，使得对于任何整数$d\ge 1$和任何$x_i\in [0,\mathrm{\infty })$,$1\le i\le d$，它成立$\alpha (d;x_1,\mathrm{\dots },x_d)\le {\alpha }^{\lceil {\log }_M(d+1)\rceil }$。

证明。

假设$(\beta ,\gamma ,\lambda )$具有普遍唯一性。 由于引理12，存在一个常数使得$\alpha (d;x_1,\mathrm{\dots },x_d)\le \alpha$。 根据引理21的项2，通用唯一性意味着$\gamma >1$，因此存在一个常数$M>1$使得$d\cdot \sqrt{\frac{\lambda }{{\gamma }^{d+1}}}\le {\alpha }^{\lceil {\log }_M(d+1)\rceil }$ 对于所有$d\ge M$。 由于 (3)，它对于所有 $d\ge M$ 都成立 $\alpha (d;x_1,\mathrm{\dots },x_d)\le d\cdot \sqrt{\frac{\lambda }{{\gamma }^{d+1}}}\le {\alpha }^{\lceil {\log }_M(d+1)\rceil }$。 请注意，$\alpha (d;x_1,\mathrm{\dots },x_d)\le \alpha$ 表示$\alpha (d;x_1,\mathrm{\dots },x_d)\le {\alpha }^{\lceil {\log }_M(d+1)\rceil }$ 代表。因此，$\alpha (d;x_1,\mathrm{\dots },x_d)\le {\alpha }^{\lceil {\log }_M(d+1)\rceil }$适用于所有$d$。 ∎

根据引理17，存在常量和$M>1$，使得

${ϵ}_v$ $\le {ϵ}_{u_k}\cdot {\displaystyle \prod _{j=1}^k}{\alpha }^{\lceil {\log }_M(d_j+1)\rceil }\le {ϵ}_{u_k}\cdot {\alpha }^{{\sum }_{j=1}^k\lceil {\log }_M(d_j+1)\rceil }={ϵ}_{u_k}\cdot {\alpha }^{{\mathrm{\ell }}_M(u_k)}\le {ϵ}_{u_k}\cdot {\alpha }^{\mathrm{\ell }}.$

对于 3 中使用的符号，$S$ 是 $B(\mathrm{\ell })$ 的补集。 请注意，$u_k$ 的所有子代都在 $B(\mathrm{\ell })$ 中，因此它们都不在 $S$ 中，而根据 Lemma 21的 2 项，普遍唯一性意味着 $\gamma >1$。 因此，根据引理11的项2，它支持${ϵ}_{u_k}=O(1)$。 因此，${ϵ}_v\le {ϵ}_{u_k}\cdot {\alpha }^{\mathrm{\ell }}=O({\alpha }^{\mathrm{\ell }})$。

让${\delta }_v=R_1-R_0$，其中$R_0$和$R_1$是递归过程返回的边界，使得$R_0\le R_T^{{\sigma }_{\mathrm{\Lambda }}}\le R_1$。 通过与3、${\delta }_v=\frac{{ϵ}_v}{\mathrm{\Phi }(\tilde{R})}=O({ϵ}_v)=O({\alpha }^{\mathrm{\ell }})$节中相同的分析。 然后通过(7)，在$O({\alpha }^{\mathrm{\ell }})$的加性误差内近似边际概率$p_v^{{\sigma }_{\mathrm{\Lambda }}}$。 递归的运行时间为$O(nB(\mathrm{\ell }))=O(n^3{M}^{\mathrm{\ell }})$。 通过设置 $\mathrm{\ell }={\log }_{\alpha }ϵ$，我们得到了一种算法，它可以在 $O(ϵ)$ 的加法误差范围内逼近 $p_v^{{\sigma }_{\mathrm{\Lambda }}}$，所用时间为 $n$ 和 $\frac{1}{ϵ}$ 的多项式，这意味着对于任意图 $G$，$Z(G)$ 的 FPTAS。

异质自旋系统。

我们在上一节和本节中的分析实际上适用于异构自旋系统，该系统允许每个顶点 $v$ 具有不同的恒定外场 ${\lambda }_v>0$。

Theorem 18.

对于每个顶点$v$处具有参数$\beta$、$\gamma$和外场${\lambda }_v$的二态反铁磁异质自旋系统，对于任何有限的$\mathrm{\Delta }\ge 2$或$\mathrm{\Delta }=\mathrm{\infty }$，如果对于所有$v$,$(\beta ,\gamma ,{\lambda }_v)$最多是$\mathrm{\Delta }$唯一则自旋系统具有强空间混合性，并且在最大度图上具有至多$\mathrm{\Delta }$的FPTAS。

5 一般二态自旋系统的非单调性

在本节中，我们证明以下定理。

Theorem 19.

存在二态反铁磁自旋系统，其在无限$d$-正则树上表现出强空间混合，但在至多$d$的所有最大度图上不表现出强空间混合。

在开创性的工作[26]中，Weitz证明了对于硬核模型，无限$d$正则树上的强空间混合意味着最大度图上的强空间混合最$d$([26]中的定理2.3）。 他进一步指出，同样的含义适用于所有两种状态的自旋系统。 那是，

对于任何二态自旋系统，无限$d$正则树上的强空间混合意味着最大度数最多$d$的图上的强空间混合。

这一主张对于当前对二态自旋系统相关衰减的理解以及为此类系统设计 FPTAS 发挥了重要作用。 [21] 中引用了该主张的算法形式作为所有二态自旋系统的定理([21] 中的定理 2.8），并被证明用于反-铁磁伊辛模型。 在[22]中提出了这个主张是否适用于多状态自旋系统的猜想。

在这里我们澄清这一说法仅适用于有限设置下的二态自旋系统，但并不适用于所有一般的二态自旋系统。 这反驳了[22]中的猜想，并表明了人们普遍认为$d$-正则树代表了所有最大度图之间强空间混合的最坏情况，最多$d$ 不能推广到一般的二态自旋系统。 我们首先描述一个区域，证明该说法是正确的。

Lemma 20.

对于$0\le \beta ,\gamma \le 1$，无限$d$-正则树上的强空间混合意味着最大度数最多为$d$的树上的强空间混合。

证明。

给定最大度数为 $d$ 的有根树，对于具有 的 $k$ 子代的每个顶点，我们可以附加 $d-1-k$ 虚拟子代具有固定的自旋态（分布）。 这是[26]和[21]中使用的方法：对于硬核模型，虚拟子项被固定为空闲，对于反铁磁Ising模型，虚拟子项被固定为空闲子级在自旋态上呈均匀分布。 在这两种情况下，虚拟孩子对其父母没有影响。 一般来说，我们将每个虚拟子节点的分布固定为 $(p_0,p_1)$ 满足

$p_0+p_1$ $=1,$

$\beta p_0+p_1$ $=p_0+\gamma p_1.$

当$0\le \beta ,\gamma \le 1$时，系统在$0\le p_0,p_1\le 1$中有解。 第 $i$ 个子级的比率 $R_i$、$1\le i\le k$ 和虚拟子级 的 $R_i=p_0/p_1$ 的比率，父级的比率由递归给出

$\lambda {\displaystyle \prod _{i=1}^{d-1}}{\displaystyle \frac{\beta R_i+1}{R_i+\gamma }}=\lambda {\displaystyle \prod _{i=1}^k}{\displaystyle \frac{\beta R_i+1}{R_i+\gamma }},$

与原始数量相同。 ∎

由于自回避游走树构造（定理6)，它认为对于$0\le \beta ,\gamma \le 1$，无限$d$-正则树上的强空间混合意味着强空间混合和最大度至多$d$图上的FPTAS。

对于$0\le \beta ,\gamma \le 1$，自旋系统表现出以下单调性质：无限$d$正则树上的唯一性意味着所有更小度的无限正则树上的唯一性。 这可以通过以下推理来验证：根据定理15，在无限$d$-正则树上，唯一性意味着强烈的空间混合，对于$0\le \beta ,\gamma \le 1$ ，意味着所有较小度的无限正则树上的强空间混合（包括唯一性）。

存在非单调的二态反铁磁自旋系统。 我们可以选择满足$\gamma >1$和$\lambda >{\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )$的反铁磁$(\beta ,\gamma ,\lambda )$，其中${\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )$是Lemma 21的8项中给出的普遍唯一性的上临界值。 由于 Lemma 21的 3 项，对于 $\gamma >1$ 而言，在所有足够大的 $d$ 中，唯一性在 $d$ 不规则树上成立。另一方面，由于 Lemma 21 的 8 项，当 $\lambda >{\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )$ 时，$(\beta ,\gamma ,\lambda )$ 不可能是普遍唯一的，这意味着存在一个有限的 $d^{\prime }$，使得系统在 $d^{\prime }$ 不规则树上是非唯一的。

对于这样的非单调系统，由于定理15，唯一性意味着对于足够大的$d$,$d$正则树上存在强空间混合，但是强空间混合不适用于较小程度的规则树（因为较小树上的非唯一性）。 因此，$d$正则树上的强空间混合与最大度至多$d$图上的强空间混合之间的含义对于一般的二态自旋系统并不成立。

致谢。

我们要感谢 Alistair Sinclair 和 Piyush Srivastava 对本文早期版本的有益评论。

致谢 2021 年修订。

我们要感谢Xiaoyu Chen、Weiming Feng 和Xinyuan 张在论文原始（2013）版本中找到引理21 中的错误并提出修复建议。

附录 A 唯一性阈值

以下引理将唯一性条件转换为其各种阈值形式。 引理(2除外）不用于主要结果的证明，而是用于主要结果的解释以及与先前结果的比较，这些结果大多以阈值形式表述。

Lemma 21.

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。

1. $(\beta ,\gamma ,\lambda )$ 最多为 2 个唯一。

2. 如果$\gamma \le 1$，那么唯一性不成立于无限$d$-所有足够大的正则树$d$。

3. 如果$\gamma >1$，则唯一性保持无限$d$-所有足够大的正则树 $d$。

4. 对于任何$\mathrm{\Delta }$（包括$\mathrm{\Delta }=\mathrm{\infty }$），存在一个临界阈值${\gamma }_c={\gamma }_c(\beta ,\lambda ,\mathrm{\Delta })$，当且仅当$\gamma \in ({\gamma }_c,\frac{1}{\beta })$时，$(\beta ,\gamma ,\lambda )$直到$\mathrm{\Delta }$是唯一的。特别是，${\gamma }_c(\beta ,\lambda ,\mathrm{\infty })>1$ 和${\gamma }_c(\beta ,\lambda ,\mathrm{\infty })={\gamma }_c(\beta ,\lambda ,\mathrm{\Delta })$ 对于某个有限的$\mathrm{\Delta }$.。

5. 如果$\beta =0$，对于任何$\mathrm{\Delta }$（包括$\mathrm{\Delta }=\mathrm{\infty }$），存在一个临界阈值，使得$(\beta ,\gamma ,\lambda )$直到$\mathrm{\Delta }$是唯一的，当且仅当$\lambda \in (0,{\lambda }_c)$.。

6. 如果$\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$，则对于任何外部字段$\lambda$、$(\beta ,\gamma ,\lambda )$ 最多为-$\mathrm{\Delta }$ 唯一。

7. 如果$\beta >0$，对于任何$\mathrm{\Delta }$（包括$\mathrm{\Delta }=\mathrm{\infty }$) $\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$,$\lambda$的制度满足最多-0>$\mathrm{\Delta }$ 唯一性如下。

   让$\overline{\mathrm{\Delta }}\triangleq \frac{1+\sqrt{\beta \gamma }}{1-\sqrt{\beta \gamma }}$。对于任意整数，令$x_1(d)\le x_2(d)$为方程$\frac{d(1-\beta \gamma )x}{(\beta x+1)(x+\gamma )}=1$的两个正根>，更具体地说，

   $x_1(d)={\displaystyle \frac{-1-\beta \gamma +d(1-\beta \gamma )-\sqrt{{(-1-\beta \gamma +d(1-\beta \gamma ))}^2-4\beta \gamma }}{2\beta }},$

   $x_2(d)={\displaystyle \frac{-1-\beta \gamma +d(1-\beta \gamma )+\sqrt{{(-1-\beta \gamma +d(1-\beta \gamma ))}^2-4\beta \gamma }}{2\beta }}.$

   让${\lambda }_i(d)\triangleq x_i(d){\left(\frac{x_i(d)+\gamma }{\beta x_i(d)+1}\right)}^d$（其中$i=1,2$)被定义为整数 .

   那么 $(\beta ,\gamma ,\lambda )$ 最多 - $\mathrm{\Delta }$ 唯一当且仅当 $\lambda$属于以下政权

   (8)

   如果此外$\gamma \le 1$，则$(\beta ,\gamma ,\lambda )$可达-$\mathrm{\Delta }$ 唯一当且仅当 $\lambda \in (0,{\lambda }_c)\cup ({\overline{\lambda }}_c,\mathrm{\infty })$，其中

   ${\lambda }_c$

   ${\overline{\lambda }}_c$

   特别是，当$\beta =\gamma$时，它成立${\lambda }_c\cdot {\overline{\lambda }}_c=1$，因此$(\beta ,\beta ,\lambda )$ 最多 - $\mathrm{\Delta }$ 唯一当且仅当 $|\log \lambda |>\log {\overline{\lambda }}_c$。0>

8. 只有当 $\gamma >1$ 时，$(\beta ,\gamma ,\lambda )$ 才可能是普遍唯一的。如果$\gamma >1$，则存在有限正常数${\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}={\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}(\beta ,\gamma )$和${\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}={\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )$，其中${\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}\le {\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}$、使得$(\beta ,\gamma ,\lambda )$在条件下是普遍唯一的，而$(\beta ,\gamma ,\lambda )$只有在条件下是普遍唯一的。

Remark (SODA’13版本错误)。

在论文的早期版本中，引理21的第7项有错误（这是SODA'13会议版本中的引理3.1[16] )。 在该版本中，唯一性机制 (8) 被无条件且错误地简化为双区间简单形式 $(0,{\lambda }_c)\cup ({\overline{\lambda }}_c,\mathrm{\infty })$，实际上，当 $\beta ,\gamma \le 1$。 然而，当$\gamma >1$时，存在这样的，使得唯一性机制(8)可能变得比最多由两个区间组成更复杂。 例如，当 $\beta =\frac{1}{122}$、$\gamma =100$ 和 $\mathrm{\Delta }=23$ 时，$\lambda$ 的机制使得 $(\beta ,\gamma ,\lambda )$ 为up-to-$\mathrm{\Delta }$ 唯一，由三个间隔 $(0,102.664)\cup (104.339,106.967)\cup (109.444,\mathrm{\infty })$ 组成。

当前版本纠正了错误并更改了引理21的项目7和项目8的陈述。 我们进一步指出，该错误不会影响论文的主要结果，即从 up-to-$\mathrm{\Delta }$ 唯一性到强空间混合和 FPTAS 的含义，因为引理 21不用于主要结果的证明（除了第2项），而仅用于解释各种阈值形式的唯一性机制以及与其他已知结果的比较。

引理21的证明。

令$f_d(x)=\lambda {\left(\frac{\beta x_d+1}{x_d+\gamma }\right)}^d$和${\widehat{x}}_d=f_d({\widehat{x}}_d)$为$f_d(x)$的正不动点。 然后

$|f_d({\widehat{x}}_d)|={\displaystyle \frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}}.$

令 $(\beta ,\gamma ,\lambda )$ 是反铁磁性的。 即 $0\le \beta \le \gamma$、$\gamma >0$ 和 ，即 。

1. 很容易验证对于,$(\beta x+1)(x+\gamma )-(1-\beta \gamma )x>0$对于任何正$x>0$。 因此，当$d=1$时，我们有，这意味着$(\beta ,\gamma ,\lambda )$是最多2个唯一的。

2. 对于所有足够大的 $d$，它认为

   $\lambda {\beta }^d\exp \left({\displaystyle \frac{d}{(1-\beta \gamma )d-3}}\right)$

   $\lambda \exp \left(-{\displaystyle \frac{\gamma d}{d(1-\beta \gamma )-3}}\right)$ $>{\displaystyle \frac{\gamma }{d(1-\beta \gamma )-3}}.$

   根据矛盾，假设$|f_d({\widehat{x}}_d)|=\frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}\le 1$。 然后，

   $1\ge {\displaystyle \frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}}={\displaystyle \frac{d(1-\beta \gamma )}{\beta {\widehat{x}}_d+\frac{\gamma }{{\widehat{x}}_d}+(1+\beta \gamma )}}\ge {\displaystyle \frac{d(1-\beta \gamma )}{\beta {\widehat{x}}_d+\frac{\gamma }{{\widehat{x}}_d}+2}}.$

   • ${\widehat{x}}_d\ge \gamma$。 然后$\frac{\gamma }{{\widehat{x}}_d}\le 1$。 因此，

     $1\ge {\displaystyle \frac{d(1-\beta \gamma )}{\beta {\widehat{x}}_d+\frac{\gamma }{{\widehat{x}}_d}+2}}\ge {\displaystyle \frac{d(1-\beta \gamma )}{\beta {\widehat{x}}_d+3}},$

     这意味着${\widehat{x}}_d\ge \frac{d(1-\beta \gamma )-3}{\beta }$。 然而，它认为

     ${\widehat{x}}_d$ $=\lambda {\left({\displaystyle \frac{\beta {\widehat{x}}_d+1}{{\widehat{x}}_d+\gamma }}\right)}^d\le \lambda {\left({\displaystyle \frac{\beta {\widehat{x}}_d+1}{{\widehat{x}}_d}}\right)}^d\le \lambda {\left(\beta +{\displaystyle \frac{\beta }{d(1-\beta \gamma )-3}}\right)}^d$

     矛盾。

   • 。 然后。 因此，

     $1\ge {\displaystyle \frac{d(1-\beta \gamma )}{\beta {\widehat{x}}_d+\frac{\gamma }{{\widehat{x}}_d}+2}}\ge {\displaystyle \frac{d(1-\beta \gamma )}{\frac{\gamma }{{\widehat{x}}_d}+3}},$

     这意味着${\widehat{x}}_d\le \frac{\gamma }{d(1-\beta \gamma )-3}$。 然而，它认为

     ${\widehat{x}}_d$ $=\lambda {\left({\displaystyle \frac{\beta {\widehat{x}}_d+1}{{\widehat{x}}_d+\gamma }}\right)}^d\ge {\displaystyle \frac{\lambda }{{({\widehat{x}}_d+1)}^d}}\ge \lambda {\left(1+{\displaystyle \frac{\gamma }{d(1-\beta \gamma )-3}}\right)}^{-d}$

     $\ge \lambda \cdot \exp \left(-{\displaystyle \frac{\gamma d}{d(1-\beta \gamma )-3}}\right)>{\displaystyle \frac{\gamma }{d(1-\beta \gamma )-3}},$

     矛盾。

3. 让$\gamma >1$。 固定点${\widehat{x}}_d=\lambda {\left(\frac{\beta {\widehat{x}}_d+1}{{\widehat{x}}_d+\gamma }\right)}^d\le \frac{\lambda }{{\gamma }^d}$，以及

   $|f_d^{\prime }({\widehat{x}}_d)|={\displaystyle \frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}}\le {\displaystyle \frac{d\lambda }{{\gamma }^d}},$

   对于所有足够大的 $d$ 来说，它严格小于 1。因此，对于所有足够大的$d$，无限$d$-正则树具有唯一性。

4. 我们首先表明，存在一个临界阈值 ${\gamma }_c={\gamma }_c(\beta ,\lambda ,\mathrm{\Delta })$，使得 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的，当且仅当 $\gamma \in ({\gamma }_c,\frac{1}{\beta })$ 时。 足以证明，如果反铁磁 $(\beta ,\gamma ,\lambda )$ 的唯一性可达 $\mathrm{\Delta }$，则 $(\beta ,{\gamma }^{\prime },\lambda )$ 的唯一性可达 $\mathrm{\Delta }$ 对于任何 ${\gamma }^{\prime }>\gamma$ 和 都是唯一的。

   回想一下，${\widehat{x}}_d$ 是 $f_d(x)=\lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d$ 的正不动点。还让 ${\widehat{x}}_d^{\prime }$ 表示 $x=\lambda {\left(\frac{\beta x+1}{x+{\gamma }^{\prime }}\right)}^d$ 的正解。

   我们首先展示。 根据矛盾，假设${\widehat{x}}_d^{\prime }\ge {\widehat{x}}_d$。 由于对于反铁磁$(\beta ,\gamma ,\lambda )$,$f_d(x)$是单调递减的，我们有

   $${\widehat{x}}_d=\lambda {\left(\frac{\beta {\widehat{x}}_d+1}{{\widehat{x}}_d+\gamma }\right)}^d\ge \lambda {\left(\frac{\beta {\widehat{x}}_d^{\prime }+1}{{\widehat{x}}_d^{\prime }+\gamma }\right)}^d>\lambda {\left(\frac{\beta {\widehat{x}}_d^{\prime }+1}{{\widehat{x}}_d^{\prime }+{\gamma }^{\prime }}\right)}^d={\widehat{x}}_d^{\prime },$$

   矛盾。

   自从

   我们有

   对于，也成立

   将以上两个不等式相乘，我们有

   请注意，这些是当参数为$(\beta ,\gamma ,\lambda )$和$(\beta ,{\gamma }^{\prime },\lambda )$时在各自固定点处的绝对导数。 因此，如果 $(\beta ,\gamma ,\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一，则 $(\beta ,{\gamma }^{\prime },\lambda )$ 最多为 $\mathrm{\Delta }$ 唯一。

   由于引理的 2 部分，如果 $\gamma \le 1$、$|f_d^{\prime }({\widehat{x}}_d)|>1$ 对于所有足够大的 $d$，因此 ${\gamma }_c(\beta ,\lambda ,\mathrm{\infty })>1$。 并且由于引理的 3 部分，对于任何 $\gamma \ge {\gamma }_c(\beta ,\lambda ,\mathrm{\infty })>1$，随着 $d$ 增长到无穷大，$|f_d^{\prime }({\widehat{x}}_d)|$ 任意接近 0，因此${\gamma }_c(\beta ,\lambda ,\mathrm{\infty })={\gamma }_c(\beta ,\lambda ,\mathrm{\Delta })$对于有限的$\mathrm{\Delta }$。

5. 当$\beta =0$,$|f_d^{\prime }({\widehat{x}}_d)|=\frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}=\frac{d{\widehat{x}}_d}{{\widehat{x}}_d+\gamma }$时，唯一性条件相当于（这里我们假设$d>1$，因为由于引理的 1 部分，对于 $d=1$ ，唯一性始终成立）。 回想一下${\widehat{x}}_d=\lambda {\left(\frac{1}{{\widehat{x}}_d+\gamma }\right)}^d$。那么 当且仅当

   让。 它认为当且仅当 $\lambda \in (0,{\lambda }_c)$ 时 $(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的。

6. 我们注意到 $|f_d^{\prime }({\widehat{x}}_d)|=\frac{d(1-\beta \gamma ){\widehat{x}}_d}{(\beta {\widehat{x}}_d+1)({\widehat{x}}_d+\gamma )}$ 在 ${\widehat{x}}_d$ 中不是单调的。 它在${\widehat{x}}_d=\sqrt{\frac{\beta }{\gamma }}$处达到最大值。 因此，如果对于任何,对于$x=\sqrt{\frac{\beta }{\gamma }}$，则$(\beta ,\gamma ,\lambda )$最多是$\mathrm{\Delta }$唯一对于任何$\lambda$。 当 $\sqrt{\beta \gamma }>\frac{d-1}{d+1}$ 对于所有 时，即当 $\sqrt{\beta \gamma }>\frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$ 时，此条件成立。

7. 让$\theta (d)\triangleq -1-\beta \gamma +d(1-\beta \gamma )$。 它对所有 $d\ge \overline{\mathrm{\Delta }}=\frac{1+\sqrt{\beta \gamma }}{1-\sqrt{\beta \gamma }}$ 都适用 $\theta (d)\ge 2\sqrt{\beta \gamma }$。 因此，$x_1(d),x_2(d)$ 是明确定义的，可以表示为：

   $x_1(d)={\displaystyle \frac{\theta (d)-\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }}\text{and}{x}_2(d)={\displaystyle \frac{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }}.$

   回想一下 ${\lambda }_i(d)\triangleq x_i(d){\left(\frac{x_i(d)+\gamma }{\beta x_i(d)+1}\right)}^d$ 代表 $i=1,2$。

   下面的${\lambda }_2(d)$的单调性和无界性很容易验证。

   Claim 22。

   ${\lambda }_2(d)$ 在 $d$ 中单调递增，并随着 $d$ 的增长而趋于无穷大。

   证明。

   观察到对于$0\le \beta \le \gamma$、和$d\ge \overline{\mathrm{\Delta }}$，它认为和$\frac{x+\gamma }{\beta x+1}$在$x$。 而且，

   ${\displaystyle \frac{x_2(d)+\gamma }{\beta x_2(d)+1}}$ $=$ ${\displaystyle \frac{1}{\beta }}\cdot {\displaystyle \frac{(d-1)(1-\beta \gamma )+\sqrt{\theta {(d)}^2-4\beta \gamma }}{(d+1)(1-\beta \gamma )+\sqrt{\theta {(d)}^2-4\beta \gamma }}}$

   $\ge$ ${\displaystyle \frac{d+1}{d-1}}\cdot {\displaystyle \frac{(d-1)(1-\beta \gamma )}{(d+1)(1-\beta \gamma )}}=1.$

   很容易验证 $x_2(d)$ 在 $d$ 中不断增加，并且随着 $d$ 的增长而无限制。 因此，我们可以得出结论，${\lambda }_2(d)=x_2(d){\left(\frac{x_2(d)+\gamma }{\beta x_2(d)+1}\right)}^d$ 在 $d$ 中不断增加，并且随着 $d$ 的增长而无界。 ∎

   我们继续分析唯一性机制。 对于 ，它保持 $\sqrt{\beta \gamma }>\frac{d-1}{d+1}$，在这种情况下，由于此引理的第 6 部分，它始终保持 。

   回想一下$\sqrt{\beta \gamma }\le \frac{\mathrm{\Delta }-2}{\mathrm{\Delta }}$。 仍然需要分析 $|f_d^{\prime }({\widehat{x}}_d)|$ 中的那些 。 对于这样的 $d$，我们有 $\sqrt{\beta \gamma }\le \frac{d-1}{d+1}$，并且由于 $x_1(d)$ 和 $x_2(d)$ 是方程 $\frac{d(1-\beta \gamma )x}{(\beta x+1)(x+\gamma )}=1$ 的根>，当且仅当 或 ${\widehat{x}}_d>x_2(d)$ 时，才成立 。 请注意，$x{\left(\frac{x+\gamma }{\beta x+1}\right)}^d$ 在$x$ 中单调递增。 因此：

   ${\widehat{x}}_d>x_2(d)$ $⟺\lambda ={\widehat{x}}_d{\left({\displaystyle \frac{{\widehat{x}}_d+\gamma }{\beta {\widehat{x}}_d+1}}\right)}^d>x_2(d){\left({\displaystyle \frac{x_2(d)+\gamma }{\beta x_2(d)+1}}\right)}^d={\lambda }_2(d),$

   这意味着对于任何,当且仅当$\lambda \in (0,{\lambda }_1(d))\cup ({\lambda }_2(d),\mathrm{\infty })$。

   因此，当且仅当 $\lambda$ 属于该政权时，$(\beta ,\gamma ,\lambda )$ 最多 $\mathrm{\Delta }$ 是唯一的

   这正是唯一性机制 (8)。 回想起那个

   其中最后一个方程是由于 ${\lambda }_2(d)$ 的单调性造成的。

   然后我们证明，对于 $\gamma \le 1$，唯一性机制 (8) 变为 $(0,{\lambda }_c)\cup ({\overline{\lambda }}_c,\mathrm{\infty })$。 我们需要以下断言，其证明推迟到本节末尾。

   Claim 23。

   对于，它总是成立

   此外，如果 ${\lambda }_1(d+1)\le {\lambda }_2(d)$ 对于所有整数 ，则

   Claim 24。

   以下内容成立：

   • 如果 $\gamma \le 1$，则 ${\lambda }_1(d+1)\le {\lambda }_2(d)$ 对于所有整数 $d\ge \overline{\mathrm{\Delta }}$;

   • 如果$\gamma >1$，则存在有限的$d_0=d_0(\beta ,\gamma )\ge \overline{\mathrm{\Delta }}$使得${\lambda }_1(d+1)\le {\lambda }_2(d)$ 对于所有$d\ge d_0$。

   现在假设$\gamma \le 1$。 根据声明24，对于所有整数,${\lambda }_1(d+1)\le {\lambda }_2(d)$。 然后由于声明 23，唯一性机制 (8) 变为

   特别是考虑反铁磁伊辛模型$\beta =\gamma$。 很容易验证$x_1(d)\cdot x_2(d)=\frac{\gamma }{\beta }=1$，因此

   $${\lambda }_1(d)\cdot {\lambda }_2(d)=x_1(d)\cdot x_2(d){\left(\frac{x_1(d)+\gamma }{\beta x_1(d)+1}\cdot \frac{x_2(d)+\gamma }{\beta x_2(d)+1}\right)}^d=1.$$

   因此，由于权利要求22所保证的${\lambda }_2(d)$的单调性，${\lambda }_1(d)=1/{\lambda }_2(d)$是单调递减的。 结果是 ${\lambda }_c={\lambda }_1(\mathrm{\Delta }-1)$、${\overline{\lambda }}_c={\lambda }_2(\mathrm{\Delta }-1)$ 和 ${\lambda }_c\cdot {\overline{\lambda }}_c={\lambda }_1(\mathrm{\Delta }-1)\cdot {\lambda }_2(\mathrm{\Delta }-1)=1$。 那么当且仅当 $|\log \lambda |>\log {\overline{\lambda }}_c$ 时 $(\beta ,\beta ,\lambda )$ 最多是 $\mathrm{\Delta }$ 是唯一的。

8. $\beta =0$ 的情况在该引理的 5 部分中处理。 在这种情况下，由于引理的 5 部分，$(0,\gamma ,\lambda )$ 最多是 $\mathrm{\Delta }$ 唯一，当且仅当 $\lambda \in (0,{\lambda }_c(\gamma ,\mathrm{\Delta }))$其中。 特别是，如果 $\gamma \le 1$,${\lambda }_c(\gamma ,\mathrm{\infty })={\min }_{d>1}\frac{{\gamma }^{d+1}{d}^d}{{(d-1)}^{d+1}}$ 变为 0；如果 $\gamma >1$, 变为正且有限的 ${\lambda }_c(\gamma )>0$。 因此，仅当 $\gamma >1$ 时，$(0,\gamma ,\lambda )$ 才是普遍唯一的，并且当 $\gamma >1$ 时，$(0,\gamma ,\lambda )$ 是普遍唯一的，当且仅当 $\lambda \in (0,{\lambda }_c(\gamma ))$. 我们可以令 ${\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}(\gamma )={\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\gamma )={\lambda }_c(\gamma )$ 和引理如下。

   对于 $\beta >0$ 的情况，由于引理的 7 部分，对于所有 $\mathrm{\Delta }\ge \overline{\mathrm{\Delta }}\triangleq \frac{1+\sqrt{\beta \gamma }}{1-\sqrt{\beta \gamma }}$，元组 $(\beta ,\gamma ,\lambda )$ 是 up-to -$\mathrm{\Delta }$ 唯一当且仅当 $\lambda$ 属于以下机制：

   当 $\gamma \le 1$ 时，此状态变为 $(0,{\lambda }_c(\beta ,\gamma ,\mathrm{\Delta }))\cup (\overline{\lambda }(\beta ,\gamma ,\mathrm{\Delta }),\mathrm{\infty })$，其中 和 。

   Claim 25。

   以下内容成立：

   • 如果 $\gamma \le 1$，则 ${\lambda }_1(d)$ 接近 0，如 $d$ 增长到无穷大；

   • 如果 $\gamma >1$，则 ${\lambda }_1(d)$ 无界，如 $d$ 增长到无穷大。

   证明。

   对于整数 $d\ge \overline{\mathrm{\Delta }}$，让 $\theta (d)\triangleq -1-\beta \gamma +d(1-\beta \gamma )$，并让

   ${\widehat{\lambda }}_1(d)\triangleq {\displaystyle \frac{2{\gamma }^{d+1}}{\theta (d)}}{\left({\displaystyle \frac{d+1}{d-1}}\right)}^d.$ (9)

   当$\gamma \le 1$时，很容易验证随着$d$增长到无穷大，${\widehat{\lambda }}_1(d)$接近0。

   此外，${\lambda }_1(d)$的上限以${\widehat{\lambda }}_1(d)$为界。 具体来说，对于$d\ge \overline{\mathrm{\Delta }}$，

   $x_1(d)$ $={\displaystyle \frac{\theta (d)-\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }}={\displaystyle \frac{2\gamma }{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}}\le {\displaystyle \frac{2\gamma }{\theta (d)}}.$

   由于当时$\frac{x+\gamma }{\beta x+1}$在$x$中增加，我们有

   $$\frac{x_1(d)+\gamma }{\beta x_1(d)+1}\le \frac{\frac{2\gamma }{\theta (d)}+\gamma }{\frac{2\beta \gamma }{\theta (d)}+1}=\gamma \cdot \frac{d+1}{d-1}.$$

   因此，对于所有 $d\ge \overline{\mathrm{\Delta }}$，

   ${\lambda }_1(d)$ $=x_1(d){\left({\displaystyle \frac{x_1(d)+\gamma }{\beta x_1(d)+1}}\right)}^d\le {\displaystyle \frac{2{\gamma }^{d+1}}{\theta (d)}}{\left({\displaystyle \frac{d+1}{d-1}}\right)}^d={\widehat{\lambda }}_1(d).$ (10)

   因此，当$\gamma \le 1$时，随着$d$增长到无穷大，${\lambda }_1(d)$趋近于0。

   另一方面，当$\gamma >1$时，对于$d\ge \overline{\mathrm{\Delta }}$，

   ${\lambda }_1(d)=x_1(d){\left({\displaystyle \frac{x_1(d)+\gamma }{\beta x_1(d)+1}}\right)}^d\ge x_1(d)\cdot {\gamma }^d={\displaystyle \frac{2{\gamma }^{d+1}}{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}},$

   随着 $d$ 的增长，这显然是无限的。 ∎

   当$\lambda \le 1$时，由于上述说法，随着$d$增长到无穷大，${\lambda }_1(d)$趋近于0，这意味着${\lambda }_c(\beta ,\gamma ,\mathrm{\infty })=0$；根据声明22，随着$d$增长到无穷大，${\lambda }_2(d)$也趋于无穷大，这意味着${\overline{\lambda }}_c(\beta ,\gamma ,\mathrm{\infty })=\mathrm{\infty }$。 因此，只有当$\gamma >1$时，$(\beta ,\gamma ,\lambda )$才可以是全局唯一的。

   现在假设$\gamma >1$。 根据声明 25，随着 $d$ 的增长，${\lambda }_1(d)$ 是无界的。 因此，${\lambda }_1(d)$ 在有限的$d=d(\beta ,\gamma )\ge \overline{\mathrm{\Delta }}$ 处达到其最小值。 显然，对于任何有限的 $d\ge \overline{\mathrm{\Delta }}$,${\lambda }_1(d)$ 总是有限的且为正值。 因此，${\lambda }_c(\beta ,\gamma ,\mathrm{\infty })={\lambda }_c(\beta ,\gamma ,d(\beta ,\gamma ))$是有限且正的。 让 ${\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}(\beta ,\gamma )={\lambda }_c(\beta ,\gamma ,\mathrm{\infty })>0$ 表示这个有限的正阈值。

   另一方面，根据权利要求 24，对于 $\gamma >1$，存在一个有限的 $d_0=d_0(\beta ,\gamma )\ge \overline{\mathrm{\Delta }}$，使得 ${\lambda }_1(d+1)\le {\lambda }_2(d)$ 适用于所有 $d\ge d_0$。 让${\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )={\min }_{d\ge d_0}{\lambda }_1(d)$。 显然，${\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )\ge {\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}(\beta ,\gamma )>0$。 并且 ${\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )\le {\lambda }_1(d_0(\beta ,\gamma ))$ 也是有限的。

   由于声明23以及声明22的${\lambda }_2(d)$的单调性和无界性，$\mathrm{\infty }$-唯一性的制度，即${\bigcap }_{d⩾\overline{\mathrm{\Delta }}}\left((0,{\lambda }_1(d))\cup ({\lambda }_2(d),\mathrm{\infty })\right)$，夹层如下：

   $(0,{\lambda }_c^{\mathrm{𝗅𝗈𝗐𝖾𝗋}}(\beta ,\gamma ))$ $\subseteq {\displaystyle \bigcap _{d⩾\overline{\mathrm{\Delta }}}}\left((0,{\lambda }_1(d))\cup ({\lambda }_2(d),\mathrm{\infty })\right)$

   $\subseteq {\displaystyle \bigcap _{d⩾d_0}}\left((0,{\lambda }_1(d))\cup ({\lambda }_2(d),\mathrm{\infty })\right)$

   $=(0,{\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma ))\cup ({\lambda }_2(\mathrm{\infty }),\mathrm{\infty })$

   $=(0,{\lambda }_c^{\mathrm{𝗎𝗉𝗉𝖾𝗋}}(\beta ,\gamma )).$

   因此，当 且仅当 时，$(\beta ,\gamma ,\lambda )$ 是普遍唯一的。

∎

现在还有待证明索赔23和索赔24。

索赔证明23。

首先，很容易验证对于，它总是成立

因为对于所有，它总是成立

接下来，我们证明如果对于所有整数 都 ${\lambda }_1(d+1)\le {\lambda }_2(d)$，则两种机制相等。 这是通过归纳法证明的。

当时，权利要求中的相等关系是微不足道的，因为在这种情况下，最多有一个整数 $d$ 满足 。 那么等式两边就变成了

$$\left((0,{\lambda }_1(d))\cup ({\lambda }_2(d),\mathrm{\infty })\right).$$

这就奠定了归纳基础。

对于归纳假设，假设 $d_1>d_0$ 等式成立：

(11)

我们在哪里表示

对于归纳步​​骤，我们希望在 $d_1$ 加 1 时建立相等关系。 因此另外，我们假设${\lambda }_1(d+1)\le {\lambda }_2(d)$为唯一整数$d\in [d_1-1,d_1)$，即

${\lambda }_1(\lceil d_1\rceil )\le {\lambda }_2(\lceil d_1\rceil -1).$ (12)

为了完成归纳，只需验证

假设归纳假设 (11)。 因此，只要验证一下就足够了

$=$ (13)

请注意，$\lceil d_1\rceil$ 是$[d_1,d_1+1)$ 中的唯一整数。 由于${\lambda }_2(d)$的单调性，我们有。 因此， 以及 (13) 与 一样长，这是由假设 (12) 保证的。 ∎

索赔证明24。

回想一下 (9) 中定义的函数 ${\widehat{\lambda }}_1(d)$：对于整数 $d\ge \overline{\mathrm{\Delta }}$，设 ${\widehat{\lambda }}_1(d)\triangleq \frac{2{\gamma }^{d+1}}{\theta (d)}{\left(\frac{d+1}{d-1}\right)}^d$，其中 $\theta (d)\triangleq -1-\beta \gamma +d(1-\beta \gamma )$。 到 (10)，对于所有 $d\ge \overline{\mathrm{\Delta }}$，我们有 ${\lambda }_1(d)\le {\widehat{\lambda }}_1(d)$。

它还成立${\widehat{\lambda }}_1(d)\le {\lambda }_2(d)$。 对于所有 $d\ge \overline{\mathrm{\Delta }}$，我们有 $x_2(d)=\frac{\theta (d)+\sqrt{\theta {(d)}^2-4\beta \gamma }}{2\beta }\ge \frac{\theta (d)}{2\beta }$。 由于$\frac{x+\gamma }{\beta x+1}$在时在$x$中单调递增，因此成立$\frac{x_1(d)+\gamma }{\beta x_1(d)+1}\ge \frac{\frac{\theta (d)}{2\beta }+\gamma }{\frac{\theta (d)}{2}+1}=\frac{1}{\beta }\cdot \frac{d-1}{d+1}$。 同时，对于所有$d\ge \overline{\mathrm{\Delta }}=\frac{1+\sqrt{\beta \gamma }}{1-\sqrt{\beta \gamma }}$,$\beta \gamma \le {\left(\frac{d-1}{d+1}\right)}^2$和$\theta {(d)}^2\ge 4\beta \gamma$成立。 所以，

${\lambda }_2(d)$ $=x_2(d){\left({\displaystyle \frac{x_2(d)+\gamma }{\beta x_2(d)+1}}\right)}^d\ge {\displaystyle \frac{\theta (d)}{2{\beta }^{d+1}}}{\left({\displaystyle \frac{d-1}{d+1}}\right)}^d\ge {\displaystyle \frac{2{\gamma }^{d+1}}{\theta (d)}}{\left({\displaystyle \frac{d+1}{d-1}}\right)}^d={\widehat{\lambda }}_1(d).$ (14)

假设$\gamma \le 1$。 也不难观察到 ${\widehat{\lambda }}_1(d)$ 在 $d\ge \overline{\mathrm{\Delta }}>1$ 中正在减少。 事实上，如果$\gamma \le 1$，那么$\frac{2{\gamma }^{d+1}}{\theta (d)}>0$在$d\ge \overline{\mathrm{\Delta }}$中单调递减；我们可以验证函数$h(d)\triangleq {\left(\frac{d+1}{d-1}\right)}^d$对于$d\ge \overline{\mathrm{\Delta }}>1$的单调性，如下所示：

${\left(\ln h(d)\right)}^{\prime }$ $=-{\displaystyle \frac{2d}{d^2-1}}+\ln \left({\displaystyle \frac{d+1}{d-1}}\right)\to 0\text{as}d\to \mathrm{\infty },$

${\left(\ln h(d)\right)}^{\prime \prime }$ $={\displaystyle \frac{4}{d^2-1}}>0,$

这保证了 $h(d)$ 在 $d$ 中单调递减，因此对于 $d\ge \overline{\mathrm{\Delta }}$,${\widehat{\lambda }}_1(d)=\frac{2{\gamma }^{d+1}}{\theta (d)}\cdot h(d)$ 在 $d$ 中单调递减，因为 $\frac{2{\gamma }^{d+1}}{\theta (d)}$ 和 $h(d)$ 都是正数，并且 $d$ 中是递减的。

因此，当$\gamma \le 1$时，由于(10)、${\widehat{\lambda }}_1(d)$的单调性，以及(14)，对于所有$d\ge \overline{\mathrm{\Delta }}$,

$${\lambda }_1(d+1)\le {\widehat{\lambda }}_1(d+1)\le {\widehat{\lambda }}_1(d)\le {\lambda }_2(d).$$

这就证明了当$\gamma \le 1$时，${\lambda }_1(d+1)\le {\lambda }_2(d)$对于所有$d\ge \overline{\mathrm{\Delta }}$。

最后，当$\gamma >1$时，通过矛盾假设${\lambda }_1(d+1)>{\lambda }_2(d)$对于某些$d\ge \overline{\mathrm{\Delta }}$。 然后我们对这种糟糕的 $d$ 推导出有限上限 $d_0(\beta ,\gamma )$。到(10)，我们得到${\lambda }_1(d+1)\le {\widehat{\lambda }}_1(d+1)=\frac{2{\gamma }^{d+2}}{\theta (d+1)}\cdot h(d+1)\le \frac{2{\gamma }^{d+2}}{\theta (d)}\cdot h(d)$，其中最后一个不等式是由于$\theta (d)$增加而$h(d)$减少；到 (14)，我们得到 ${\lambda }_2(d)\ge \frac{\theta (d)}{2{\beta }^{d+1}}\cdot \frac{1}{h(d)}$。 因此 ${\lambda }_1(d+1)>{\lambda }_2(d)$ 意味着

(15)

回想一下，对于 $d\ge \overline{\mathrm{\Delta }}=\frac{1+\sqrt{\beta \gamma }}{1-\sqrt{\beta \gamma }}$，它始终保持 $\theta {(d)}^2\ge 4\beta \gamma$。 在不失一般性的情况下，我们只考虑足够大的 $d\ge 2$，因此 $h(d)\le h(2)=9$ 因为 $h(d)$ 正在减小。 因此不等式 (15) 意味着

这为我们提供了 ${\lambda }_1(d+1)>{\lambda }_2(d)$ 的必要条件 ，其中 $d$ 是 $d\ge \overline{\mathrm{\Delta }}$ 和 $d\ge 2$。 让

$$d_0(\beta ,\gamma )\triangleq \max \{2,\overline{\mathrm{\Delta }},{\log }_{\frac{1}{\beta \gamma }}(81\gamma )\}.$$

然后它必须为所有 $d\ge d_0(\beta ,\gamma )$ 保留该 ${\lambda }_1(d+1)\le {\lambda }_2(d)$。 ∎

附录 B 引理证明 11（中值定理方法）

我们证明引理11。 这些符号在 3 节中定义。

1. 根据中值定理，存在 $\tilde{R}\in [R_v,R_v+{\delta }_v]$ 使得

   ${ϵ}_v$ $=\phi (R_v+{\delta }_v)-\phi (R_v)={\phi }^{\prime }(\tilde{R})\cdot {\delta }_v=\mathrm{\Phi }(\tilde{R})\cdot {\delta }_v.$

2. 假设每个顶点最多有 $k$ 个子节点。 然后由于假设 $k$ 有界或 $\gamma >1$。

   如果 $v\notin \mathrm{\Lambda }$，则 ${\delta }_v\le R_v+{\delta }_v=f(R_{v_1},\mathrm{\dots },R_{v_d})\le f(0,\mathrm{\dots },0)=\frac{\lambda }{{\gamma }^d}$，其中 $0\le d\le k$。 如果$\gamma >1$，则$R_v+{\delta }_v\le \lambda =O(1)$；如果$k$是有限的，则$R_v+{\delta }_v\le \max \{\frac{\lambda }{{\gamma }^k},\lambda \}=O(1)$。

   根据中值定理，存在$\widetilde{R_i}\in [R_{v_i},R_{v_i}+{\delta }_{v_i}]$,$1\le i\le d$，使得

   ${ϵ}_v$ $=\phi \left(f(R_{v_1},\mathrm{\dots },R_{v_d})\right)-\phi \left(f(R_{v_1}+{\delta }_{v_1},\mathrm{\dots },R_{v_d}+{\delta }_{v_d})\right)$

   $=-\nabla \phi \left(f(\widetilde{R_1},\mathrm{\dots },\widetilde{R_d})\right)\cdot ({\delta }_{v_1},\mathrm{\dots },{\delta }_{v_d})$

   $={\displaystyle \frac{(1-\beta \gamma )\cdot {\left(f(\widetilde{R_1},\mathrm{\dots },\widetilde{R_d})\right)}^{\frac{1}{2}}}{{\left(\beta f(\widetilde{R_1},\mathrm{\dots },\widetilde{R_d})+1\right)}^{\frac{1}{2}}{\left(f(\widetilde{R_1},\mathrm{\dots },\widetilde{R_d})+\gamma \right)}^{\frac{1}{2}}}}\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{{\delta }_{v_i}}{(\beta \widetilde{R_i}+1)(\widetilde{R_i}+\gamma )}}$

   $\le \sqrt{{\displaystyle \frac{f(0,\mathrm{\dots },0)}{\gamma }}}\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{{\delta }_{v_i}}{\gamma }}.$

   如果$v_i\notin S$代表所有$v_i$，那么由于上述论点，${\delta }_{v_i}\le \frac{\lambda }{{\gamma }^{d_i}}$代表免费的$v_i$，其中$0\le d_i\le k$是$v_i$的孩子数量；简单地 ${\delta }_{v_i}=0$ 表示固定的 $v_i$。 因此，${ϵ}_v\le \sqrt{\frac{\lambda }{{\gamma }^{d+1}}}{\sum }_{i=1}^d\frac{\lambda }{{\gamma }^{d_i+1}}\le {\lambda }^{\frac{3}{2}}d{\gamma }^{-\frac{d+3}{2}}\cdot \max \{\frac{1}{{\gamma }^k},1\}$。 如果$\gamma >1$，那么很容易看出$d{\gamma }^{-\frac{d+3}{2}}$以常数为界，因此成立${ϵ}_v=O(1)$；如果$k$是有界的，那么$d\le k$也是有界的，因此显然是${ϵ}_v=O(1)$。

3. 然后我们分析${ϵ}_v$的逐步收缩。 定义 $y_v=\phi (R_v)$ 以及相应的 $y_{v_i}=\phi (R_{v_i})$、$1\le i\le d$。 然后是$y_v+{ϵ}_v=\phi (R_v+{\delta }_v)$和$y_{v_i}+{ϵ}_{v_i}=\phi (R_{v_i}+{\delta }_{v_i})$、$1\le i\le d$。 我们有

   $y_v$ $=$ $\phi (f({\phi }^{-1}(y_{v_1}+{ϵ}_{v_1}),\mathrm{\dots },{\phi }^{-1}(y_{v_d}+{ϵ}_{v_d}))),$

   $y_v+{ϵ}_v$ $=$ $\phi (f({\phi }^{-1}(y_{v_1}),\mathrm{\dots },{\phi }^{-1}(y_{v_d}))).$

   应用中值定理。 存在$\widetilde{y_i}\in [y_{v_i},y_{v_i}+{ϵ}_{v_i}]$和对应的$\widetilde{R_i}\in [R_{v_i},R_{v_i}+{\delta }_{v_i}]$满足$\widetilde{y_i}=\phi (\widetilde{R_i}),1\le i\le d$，使得

   ${ϵ}_v$ $=\phi (f({\phi }^{-1}(y_{v_1}),\mathrm{\dots },{\phi }^{-1}(y_{v_d})))-\phi (f({\mathrm{\Phi }}^{-1}(y_{v_1}+{ϵ}_{v_1}),\mathrm{\dots },{\phi }^{-1}(y_{v_d}+{ϵ}_{v_d})))$

   $=-\nabla \phi (f({\phi }^{-1}(\widetilde{y_1}),\mathrm{\dots },{\phi }^{-1}(\widetilde{y_d})))\cdot ({ϵ}_{v_1},\mathrm{\dots },{ϵ}_{v_d})$

   $=-\mathrm{\Phi }(f(\widetilde{R_1},\mathrm{\dots },\widetilde{R_d}))\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{\partial f}{\partial R_i}}{\displaystyle \frac{1}{\mathrm{\Phi }(\widetilde{R_i})}}\cdot {ϵ}_i$

   $={\displaystyle \frac{(1-\beta \gamma ){\left(\lambda {\prod }_{i=1}^d\frac{\beta \widetilde{R_i}+1}{\widetilde{R_i}+\gamma }\right)}^{\frac{1}{2}}}{{\left(\beta \lambda {\prod }_{i=1}^d\frac{\beta \widetilde{R_i}+1}{\widetilde{R_i}+\gamma }+1\right)}^{\frac{1}{2}}{\left(\lambda {\prod }_{i=1}^d\frac{\beta \widetilde{R_i}+1}{\widetilde{R_i}+\gamma }+\gamma \right)}^{\frac{1}{2}}}}\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{{ϵ}_{v_i}{\widetilde{R_i}}^{\frac{1}{2}}}{{(\beta \widetilde{R_i}+1)}^{\frac{1}{2}}{(\widetilde{R_i}+\gamma )}^{\frac{1}{2}}}}$

   $\le \underset{1\le i\le d}{\max }\{{ϵ}_{v_i}\}\cdot {\displaystyle \frac{(1-\beta \gamma ){\left(\lambda {\prod }_{i=1}^d\frac{\beta \widetilde{R_i}+1}{\widetilde{R_i}+\gamma }\right)}^{\frac{1}{2}}}{{\left(\beta \lambda {\prod }_{i=1}^d\frac{\beta \widetilde{R_i}+1}{\widetilde{R_i}+\gamma }+1\right)}^{\frac{1}{2}}{\left(\lambda {\prod }_{i=1}^d\frac{\beta \widetilde{R_i}+1}{\widetilde{R_i}+\gamma }+\gamma \right)}^{\frac{1}{2}}}}\cdot {\displaystyle \sum _{i=1}^d}{\displaystyle \frac{{\widetilde{R_i}}^{\frac{1}{2}}}{{(\beta \widetilde{R_i}+1)}^{\frac{1}{2}}{(\widetilde{R_i}+\gamma )}^{\frac{1}{2}}}}$

   $=\alpha (d;{\tilde{R}}_1,\mathrm{\dots },{\tilde{R}}_d)\cdot \underset{1\le i\le d}{\max }\{{ϵ}_{v_i}\}.$

附录C启发式地找到一个好的势函数

也许我们证明中最神秘的一步是势函数$\mathrm{\Phi }(x)=\frac{1}{\sqrt{x(\beta x+1)(x+\gamma )}}$的选择。 正如在许多应用势分析的情况下一样，没有用于搜索合适的势函数的标准例程。 另一方面，我们不太可能在没有任何提示的情况下猜出这样一个相当复杂的公式。 在这里，我们提出了一种启发式方法，引导我们发现良好的潜在函数。 这部分并不严格，对于我们结果的合理性来说，逻辑上也是不必要的。 然而，这种启发式方法足够通用且有趣，并且可能会在其他场景中找到应用，因​​此值得在这里进行阐述。

启发式方法包括三个步骤：

1. 求势函数的必要条件，即与势函数在某一点相关的方程。

2. （启发式步骤）通过假设方程适用于变量的整个范围来增强条件，这给了我们一个微分方程。

3. 求解微分方程并得到势函数。

我们首先假设系统处于唯一性的边界。 这意味着 $d$ 是临界度，$f^{\prime }(\widehat{x})=-1$ 是正不动点，其中 $f(x)=\lambda {\left(\frac{\beta x+1}{x+\gamma }\right)}^d$ 和 $\widehat{x}=f(\widehat{x})$ 是正不动点。

我们有以下身份：

$\widehat{x}=\lambda {\left({\displaystyle \frac{\beta \widehat{x}+1}{\widehat{x}+\gamma }}\right)}^d\text{and}1=\lambda d(1-\beta \gamma ){\displaystyle \frac{{(\beta \widehat{x}+1)}^{d-1}}{{(\widehat{x}+\gamma )}^{d+1}}},$

这一起意味着另一个身份

$d(1-\beta \gamma )\widehat{x}$ $=(\beta \widehat{x}+1)(\widehat{x}+\gamma ).$ (16)

我们的目标是找到一个势函数，使 $\alpha (x)=|f^{\prime }(x)|\frac{\mathrm{\Phi }\left(f(x)\right)}{\mathrm{\Phi }(x)}\le 1$ 适用于所有 $x$。 另一方面，我们有$\alpha (\widehat{x})=|f^{\prime }(\widehat{x})|\frac{\mathrm{\Phi }(f(\widehat{x}))}{\mathrm{\Phi }(\widehat{x})}=1\cdot \frac{\mathrm{\Phi }(\widehat{x})}{\mathrm{\Phi }(\widehat{x})}=1$。 所以$\alpha (x)$在$x=\widehat{x}$时达到最大值。 作为一个可微函数，它满足${\alpha }^{\prime }(\widehat{x})=0$，即

$${{\left[f^{\prime }(x)\cdot \frac{\mathrm{\Phi }\left(f(x)\right)}{\mathrm{\Phi }(x)}\right]}^{\prime }|}_{x=\widehat{x}}=0.$$

我们有以下计算：

${\left[f^{\prime }(x)\cdot {\displaystyle \frac{\mathrm{\Phi }(f(x))}{\mathrm{\Phi }(x)}}\right]}_{x=\widehat{x}}^{\prime }=0$

$\iff$ ${{\left[f^{\prime }(x)\mathrm{\Phi }(f(x))\right]}^{\prime }\mathrm{\Phi }(x)|}_{x=\widehat{x}}={f^{\prime }(x)\mathrm{\Phi }(f(x)){\mathrm{\Phi }}^{\prime }(x)|}_{x=\widehat{x}}$

$\iff$ $\left[f^{\prime \prime }(\widehat{x})\mathrm{\Phi }(f(\widehat{x}))+f^{\prime }(\widehat{x}){\mathrm{\Phi }}^{\prime }(f(\widehat{x}))f^{\prime }(\widehat{x})\right]\mathrm{\Phi }(\widehat{x})=f^{\prime }(\widehat{x})\mathrm{\Phi }(f(\widehat{x})){\mathrm{\Phi }}^{\prime }(\widehat{x})$

$\iff$ $f^{\prime \prime }(\widehat{x})\mathrm{\Phi }(\widehat{x})+{\mathrm{\Phi }}^{\prime }(\widehat{x})=-{\mathrm{\Phi }}^{\prime }(\widehat{x})$

$\iff$ $-{\displaystyle \frac{f^{\prime \prime }(\widehat{x})}{2}}={\displaystyle \frac{{\mathrm{\Phi }}^{\prime }(\widehat{x})}{\mathrm{\Phi }(\widehat{x})}}={\left(\ln (\mathrm{\Phi }(\widehat{x}))\right)}^{\prime },$

我们使用 $\widehat{x}=f(\widehat{x})$ 和 $f^{\prime }(\widehat{x})=-1$ 的事实。

对$f(x)$求二阶导数，我们有

$f^{\prime \prime }(x)=\lambda d(\beta \gamma -1){\displaystyle \frac{{(\beta x+1)}^{d-2}}{{(x+\gamma )}^{d+2}}}\left((d-1)\beta (x+\gamma )-(d+1)(\beta x+1)\right).$

该方程已经给出了 $\mathrm{\Phi }$ 的恒等式。 但它太复杂了。 我们可以在$x=\widehat{x}$点进一步简化上面的公式。

$f^{\prime \prime }(\widehat{x})$ $=$ $\lambda d(\beta \gamma -1){\displaystyle \frac{{(\beta \widehat{x}+1)}^{d-2}}{{(\widehat{x}+\gamma )}^{d+2}}}\left((d-1)\beta (\widehat{x}+\gamma )-(d+1)(\beta \widehat{x}+1)\right)$

$=$ ${\displaystyle \frac{1}{(\beta \widehat{x}+1)(\widehat{x}+\gamma )}}\left((d+1)(\beta \widehat{x}+1)-(d-1)\beta (\widehat{x}+\gamma )\right)$

$=$ ${\displaystyle \frac{d+1}{\widehat{x}+\gamma }}-{\displaystyle \frac{(d-1)\beta }{\beta \widehat{x}+1}}$

$=$ ${\displaystyle \frac{d(1-\beta \gamma )}{(\beta \widehat{x}+1)(\widehat{x}+\gamma )}}+{\displaystyle \frac{1}{\widehat{x}+\gamma }}+{\displaystyle \frac{\beta }{\beta \widehat{x}+1}}$

$=$ ${\displaystyle \frac{1}{\widehat{x}}}+{\displaystyle \frac{1}{\widehat{x}+\gamma }}+{\displaystyle \frac{\beta }{\beta \widehat{x}+1}}.$

所以我们有

${\left(\ln \left(\mathrm{\Phi }(\widehat{x})\right)\right)}^{\prime }=-{\displaystyle \frac{f^{\prime \prime }(\widehat{x})}{2}}=-{\displaystyle \frac{1}{2}}({\displaystyle \frac{1}{\widehat{x}}}+{\displaystyle \frac{1}{\widehat{x}+\gamma }}+{\displaystyle \frac{\beta }{\beta \widehat{x}+1}}).$ (17)

我们应用启发式方法并假设 (17) 对于所有 $x$ 均成立。 这给了我们一个微分方程

$${\left(\ln (\mathrm{\Phi }(x))\right)}^{\prime }=-\frac{1}{2}(\frac{1}{x}+\frac{1}{x+\gamma }+\frac{\beta }{\beta x+1}).$$

该微分方程的解为

$$\ln (\mathrm{\Phi }(x))=-\frac{1}{2}\ln (x(x+\gamma )(\beta x+1))+C_1,$$

这给出了

$$\mathrm{\Phi }(x)=\frac{C_2}{\sqrt{x(\beta x+1)(x+\gamma )}},$$

其中 $C_1,C_2$ 是一些常量。 这给出了我们在论文中使用的势函数。

对于固定点$\widehat{x}$，还有其他等式成立。 选择$\widehat{x}$的哪个方程启发式扩展到所有$x$可能会影响我们获得的势函数。 例如，(16) 意味着

$$\frac{1}{d\widehat{x}}=\frac{1-\beta \gamma }{(\beta \widehat{x}+1)(\widehat{x}+\gamma )}=\frac{1}{\widehat{x}+\gamma }-\frac{\beta }{\beta \widehat{x}+1},$$

因此我们可以将 $f^{\prime \prime }(\widehat{x})$ 重写为

$$f^{\prime \prime }(\widehat{x})=\frac{1}{\widehat{x}}+\frac{1}{\widehat{x}+\gamma }+\frac{\beta }{\beta \widehat{x}+1}=\frac{d+1}{d\widehat{x}}+\frac{2\beta }{\beta \widehat{x}+1}.$$

这给出了

$${\left(\ln (\mathrm{\Phi }(\widehat{x}))\right)}^{\prime }=-\frac{d+1}{2d\widehat{x}}-\frac{\beta }{\beta \widehat{x}+1}.$$

我们还可以将此方程视为变量 $x$ 的微分方程，求解它可以得到

$$\mathrm{\Phi }(x)=\frac{c}{x^{\frac{d+1}{2d}}(\beta x+1)},$$

这是[15]中使用的势函数。