深度多线性电路的下界与分离性

1等深度多线性电路的下界与分离性兰·拉兹·阿米尔·耶胡达约夫摘要我们证明了一个指数下界的大小恒定深度的多线性算术电路计算的行列式或永久（电路被称为多线性，如果由它的每个门计算的多项式是多线性的）。 我们还证明了一个超多项式之间的产品深度1d和产品深度d +1多线性电路（其中d是常数）的大小分离。也就是说，存在一个多项式f，• 存在一个乘积深度为d+1的多线性电路，其多项式大小为计算f。• 每个计算f的乘积深度d的多线性电路都有超多项式大小。1介绍算术电路是计算多项式的标准模型算术电路规模的指数下界的证明是一个突出的公开问题。所以，限制类的算术以 色 列 Rehogan 魏 茨 曼 研 究 所 数 学 和 计 算 机 科 学 系 。 电 子 邮 件 ： ran. raz@weizmann.ac 。 伊 湖研 究 由BinatioalScienceFoundation（BSF）、Israel Science Foundation（ISF）和Minerva Foundation资助。†教师的数学和计算机科学、魏茨曼研究所，Rehoviti，以色列电子邮件：amir. weizmann.ac.il。由两国科学基金会（BSF），以色列科学基金会（ISF），密涅瓦基金会和以色列科学部（IMOS）资助的研究-Eshkol Fell owship。1.电路的积深度是电路中有向路径上的最大积门数根据标准定义的深度，我们展示了一个超多项式之间的分离深度d和深度d+2多线性电路的大小2^已经研究了诸如恒定深度电路和多线性电路的电路。对恒深布尔电路的研究为布尔计算提供了很好的见解;特别是，恒深布尔电路的指数下界是已知的[A，FSS，H，R，S，Y]。然而，令人惊讶的是，我们对恒定深度算术电路的理解要差得多，甚至对于深度为4的算术电路，也没有已知的一般下限（比n2更好）本文研究了常深度多线性电路。 我们证明了常数深度多线性电路的行列式和永久的大小的指数下界。我们还证明了一个超多项式分离的产品深度d和产品深度d+ 1多线性电路的大小。我们考虑产品深度的概念，而不是标准的深度概念，以简化演示，因为深度和产品深度的概念是等价的。1.1多线性电路域F和变量集X上的算术回路Φ是如下的有向非循环图。Φ中入度为0的每一个顶点都用X中的一个变量或F中的一个域元素标记。Φ中的每一个其他顶点都用×或+标记。如果一个算术电路是一个有向树（其边从叶子指向根），则它被称为公式Φ的顶点也称为门。每一个入度为0的门被称为输入门。每一个出度为0的门都被称为输出门。每一个用×标记的门叫做积门。每一个标记为+的门都被称为和门。对于Φ中的两个门u和v，如果（u，v）是Φ中的一条边，则u称为v的子门，v称为u的父门。我们用CHILD（v）表示v的子集合。Φ的大小，表示为|Φ|是Φ中的边数。门v在Φ中的积深度，记为p− depth（v），是到达v的有向路径中的最大积门数。Φ的积深是浇口在Φ中的最大积深。对于Φ中的门v，定义Φv为Φ的以v为根的子电路。 用Xv表示出现在Φv中的变量的集合。算术电路以自然的方式计算多项式。标记为α∈F<$X的输入门计算多项式α。乘积门计算由其子门计算的多项式的乘积。和门计算由其子项计算的多项式的和。我们用Φv表示由Φ中的门v计算的F[Xv]中的多项式一个多项式f∈F[X]称为多线性的，如果f中每个变量的次数至多为1。 一个算术电路Φ称为多线性的，如果Φ中的每个门都计算一个多线性多项式。一个3算术电路Φ称为语法多线性的，如果对于Φ中的每一个乘积门和每两个门v1，v2∈CHILD（v），两个集合Xv1和Xv2是不相交的.1.2背景多线性电路的研究是由Nisan和Wigderson在[NW96]中发起的。文[R04A]证明了行列式和积和式的多重线性公式的长度的一个超多项式下界。然后，[R04B]证明了多线性公式的规模和多线性电路的规模之间的超多项式分离（[RY]简化了这种分离的证明）。后来，[RSY]证明了一个大约n4/3下界的大小语法多线性算术电路。恒深算术电路已被广泛研究。在有限域上[GK，GR]证明了深度为3的电路的大小的指数下界。在领域的特征零[SW]证明了一个大致n2下界的大小深度3电路。对于任意常数深度的算术电路[SS，R 07]，证明了深度为d的算术电路（在任意域上）的大小的一个约为n1+1/d的在本文中，我们研究的电路，都是多线性和恒定的深度-我们分别对每个模型的下限进行了改进给出了积深为d和积深为d+ 1的多线性电路之间的超多项式分离。1.3方法我们使用的想法，在那里使用之前证明多线性电路和公式的下界[R04A，R04B，RSY]。[R04B]中多线性公式与电路规模分离的证明意味着这些思想未能证明多线性电路规模的超多项式下界。本文利用等深度电路的性质，结合文献[R04A，R04B，RSY]中的思想，证明了等深度多线性电路规模的一个指数下界.此外，我们给出了一个多线性多项式的构造，该多项式可由乘积深度为d+1的多项式大小的多线性电路计算，并且不可由乘积深度为d的多项式大小的多线性电路计算。4|≥ 2。|≥ 2.1.4结果下面的定理给出了计算行列式或永久式的常数深度多线性电路的大小的指数下界（它也给出了非常数但有界深度的超多项式下界）。定理1.1.设n ∈ N，Φ是域F上乘积深度为d的多线性算术圈，其中2d =o（10gn/loglogn）在变量集X={xi，j}i，j∈[n]c上计算X的行列式或X的积和式. 然后，n（1/d）下面的定理给出了乘积深度d和乘积深度d+ 1多线性电路的大小之间的超多项式分离（即使对于非常数但有界的d，分离也保持超多项式）。我们注意到，作为乘积深度d和乘积深度d+ 1多线性电路之间的分离证明的一部分，我们证明了乘积深度d多线性电路的大小的一个紧下界。定理1.2. 设d ∈ N为常数，f = f d+1为第6.1节中定义的F [X，W]中的多项式，记为|X|+的|W|=N. 然后，• 存在积深度d+ 1和尺寸poly（N）在域F和变量集合X上计算f。• 域F上和变量集上XW计算f的超多项式大小为N（log1/（2 d）（N））。2预赛对于整数n∈N，记[n]={1，. . . ，n}。2除非另有说明，否则基数为2。u∈CHILD（v）uJ ∈CHILD（u）52.1恒深多线性电路现在我们将定义d-范式公式（其中d∈N）。d-正规形式公式具有以下形式：你好啊。`2d+1x形式上，该定义是归纳的：0-范式公式是输入门的和，并且对于d>0，以门v为根的d-正规形式公式具有以下形式：YΦuJ，u∈CHILD（v）uJ ∈CHILD（u）其中ΦuJ是（d−1）-正规形式公式。我们可以很方便地把一个等深电路看作是一个正规形式公式。下面的引理表明，这种观点没有误导。引理2.1. 设Φ是在域F和变量集X上计算多项式f的乘积深度d的多线性算术电路。 则存在一个长度至多为（d+1）2的d-范式语法多线性算术公式|Φ |2d+1在域F和变量集X上计算f。我们在下面的2.1.4节中证明了引理，使用下面的三个声明。2.1.1定深回路是公式下面的权利要求表明，恒定深度电路和公式是等效的。权利要求2.2. 设Φ是在域F和变量集X上计算多项式f的乘积深度d的多线性算术电路。 则存在乘积深度d和最大尺寸的多重线性算术公式|Φ |2d+1在域F和变量集X上计算f。证据证明如下归纳D。如果d= 0，则不失一般性，Φ是一个公式，并得出以下结论。假设d >0。设v是Φ计算f的门。在不失一般性的情况下，假设Φ=φYΦuJu∈CHILD（v）uJ ∈CHILD（u）6^^(ifv不是和门，或者如果一些门u∈CHILD（v）是输入门，我们添加一些对于每个门uJ（如上所述），通过归纳，存在乘积深度的多线性公式mostd−1andsizeatmost|ΦuJ|2（d−1）+1计算Φ^uJ。Let是形式mu∈CHILD（v）QuJ∈CHILD（u）阿努河因此，在本发明中，|（|Φ| 1）2（|Φ| − 1）2 d −1 + |Φ| ≤ |Φ|2d +1。|2d+1 .此外，它是乘积深度d的多线性，并计算f。2.1.2多线性公式在句法上是多线性的每个语法上的多线性算术公式也是多线性的。在[R04A]中显示，另一个方向也成立。从形式上讲，权利要求2.3. 对于每一个多重线性算术公式，都存在一个语法上的多重线性算术公式，它具有相同的长度和乘积深度，计算相同的多项式。为了完整性，我们给出了证明的主要思想。设Φ是变量集X上的算术公式。 设v是Φ中的一个乘积门，有两个子门v1和v2，使得多项式Φv是多线性的。设x∈Xv1<$Xv2.然后，不失一般性，多项式Φv1中x的次数为0。由于Φ是一个公式，在Φv1中代入0而不是x后，Φv1和Φv2仍然计算相同的多项式。2.1.3公式具有范式粗略地说，下面的权利要求表明，一个语法上的多线性公式具有正规形式。权利要求2.4. 设Φ是域F和变量集X上乘积深度d的语法多线性算术公式，计算多项式f。 则存在一个长度至多为（d+1）2的d-范式语法多线性算术公式|Φ|在域F和变量集合X上计算多项式f。证据这个证明是通过对Φ的乘积深度的归纳得出的。如果Φ的积深度为0，则不失一般性地Φ是0-正规型的。否则，不失一般性地假设，Φ=φYΦuJ，7^2u∈CHILD（v）uJ ∈CHILD（u）其中v是Φ计算f中的门（我们注意到v可能不是和门，并且某些门u∈CHILD（v）可能是输入门;在这些情况下，我们向电路中添加“伪”门）。通过归纳，对于每个uJ，存在大小不超过d2的（d-1）-范式语法多线性算术公式<$uJ|Φ uJ|+2 d− 1在变量集X uJ上计算多项式Φ uJ（如果u j的乘积深度小于d − 1，我们可能需要添加最多2 d− 1个“伪”门）。设置=u∈CHILD（v）uJ ∈CHILD（u）由于Φ是语法上的多线性，所以Φ也是。 此外，本发明还提供了一种方法，| ≤ Σ Σ|吉乌河|+的|Φ|+1 ≤（d + 1）|Φ|.|.2.1.4引理2.1的证明设Φ是在域F和变量集X上计算多项式f的乘积深度d的多线性算术电路。根据权利要求2.2、2.3和2.4，存在大小至多为（d + 1）2的d -正规形式语法多线性算术公式|Φ |2d+1在域F和变量集X上计算f。2.2分区设X、Y、Z为三组变量。X的一个划分A是一个从X到Y<$Z<${0，1}的映射，使得每个t∈Y<$Z都允许|A−1（t）|= 1。对于一个分布在分块μ上的分布，我们用Aμμ表示一个按照μ分布的分块。我们将重点讨论两种类型的分区。第一种类型（用于永久式和行列式的下界）是从变量X到Y<$Z<${0， 1}的n×n矩阵的映射，其中Y和Z的大小大约是n1/3。第二种类型（用于分离）将是从X到Y<$Z的一对一映射，其中Y和Z是两个大小相等的集合。对于集合XJ<$X和划分A，我们表示DA（XJ）=. A−1（Y）<$XJ. −。A−1（Z）<$XJ. .8..^1因此，在本发明中， DA（·） 根据A测量集合的“不平衡”量。设Φ是变量集X上的算术回路。给定一个划分A，我们可以定义一个新的算术回路ΦA，它与Φ相同，只是每个变量x∈X都被A（x）代替。因此，ΦA是变量集Y<$Z上的算术回路，如果Φ是语法多线性的，那么ΦA也是。此外，在Φ中的门和ΦA中的门之间存在一一对应。也就是说，对于Φ中的每个门v，ΦA中存在对应的门，反之亦然。因此，对于Φ中的门v，我们用Xv表示Φv中出现的X变量的集合，用Yv表示ΦA中出现的Y变量的集合，用Zv表示ΦA中出现的Z变量的集合。V V类似地，给定F[X]中的多项式f，我们用fA∈F[Y，Z]表示将每个x∈X替换为A（x）∈Y<$Z<${0， 1}后的多项式f。因此，如果f是多线性的，那么fA也是。在本文的其余部分，我们将考虑在变量X的集合上以及在变量Y和Z的两个集合上的回路和多项式。 我们可以把变量Y和Z看作是X中某些变量的重命名。2.3偏导数矩阵设F是一个域，Y和Z是两个大小为m∈N的变量集.设f是F[Y，Z]中的多线性多项式.用Mf表示以下2m×2m矩阵，元素在F中：对于变量集Y中的多线性单项式p和变量集Z中的多线性单项式q，Mf中的（p，q）项是多项式f中单项式p·q的系数。 矩阵Mf称为 f的偏导数矩阵 特别感兴趣的将是多项式的偏导数矩阵有满秩。这样的多项式被称为具有满秩。对于在域F上和两组变量Y和Z上的多线性电路中的门v，用Mv表示多项式Mv的偏导数矩阵。下面的命题给出了偏导数矩阵的一些有用的性质。2.5号提案 设F是一个域，Y和Z是两个大小为m ∈ N的变量集. 设Y1和Y2是Y的两个子集. 设Z1和Z2是Z的两个子集. 设f1是F [Y1，Z1]中的多线性多项式，f2是F [Y2，Z2]中的多线性多项式. 然后，1.02-02|Y1|、|Z1|）的。912.秩（M f1+f2）≤秩（M f1）+秩（M f2）。3. 如果Y1<$Y2=且Z1<$Z2=，则秩（M f1·f2）=秩（M f1）·秩（M f2）。证据1. M f最多有2 |Y1|非零行，最多2行|Z1|非零列。2. 注意，Mf1+f2=Mf1+Mf2，并且秩（Mf1+Mf2）≤秩（Mf1）+秩（Mf2）。3. 设M是Mf1·f2的非零行列子矩阵，M1是Mf1的非零行列子矩阵，M2是Mf2的非零行列子矩阵.由于Y1<$Y2=，Z1<$Z2=，M是M1和M2 的乘 积。最后，Rank（M1<$M2）= Rank（M1）·Rank（M2），其中Rank表示张量积。3中心路与弱公式设λ是两个变量集Y和Z（每个变量集的大小为m∈N）上的d-正规形式语法多线性算术公式。 对于门v，用Yv表示出现在门v中的Y变量的集合，用Zv表示出现在门v中的Z变量的集合，并表示avg（v）= |Yv|+的|Zv|.2对于k∈N，如果γ从一个输入门开始，并且γ中的每条边（u，v）允许以下条件，则称γ中的一条简单有向路γ为k-中心的· 如果v是乘积门，则每个门UJ∈CHILD（v）允许avg（UJ）≤avg（u），· 如果v是和门，则avg（u）≥avg（v）−k/2。10粗略地说，一条中心路径通向一个有许多变量的子节点。我们注意到，并不是每一个门都有一个中心路径到达它。对于k∈N，我们说，在n中的门v具有k-低秩，如果秩（M v）≤2 avg（v）−k。我们说一个门v是k-弱的，如果每个到达v的k-中心路径都包含一个k-低秩门。我们说一个公式是k-弱的，如果它的输出门是k-弱的.下面的定理表明弱公式不计算满秩多项式。定理3.1. 设Φ是域F上两组变量Y和Z上的一个d-范式语法多线性算术公式，v是Φ中的一个门。 对于任意k ∈N，如果v是k-弱的，则秩（M v）≤| Φ v|2 avg（v）−k/2。证据这个证明是通过对Φv的大小的归纳得出的。考虑以下三种情况：案例一：v有k-低秩。 以来|Φ v| ≥ 1，秩（M v）≤| Φ v|2 avg（v）−k/2。对于其余的证明，我们假设v没有k-低秩。第二种情况：v是一个和门。将v的子项划分为两个集合C1={u∈CHILD（v）：avg（u）≥avg（v）−k/2}且C2=CHILD（v）\C1。由于v不具有k-低秩，并且由于到达C1中的门的每个k-中心路径可以被扩展，对于到达v的k-中心路，每个门u∈C1都是k-弱的.因此，通过归纳，每个u∈C1都允许秩（Mu）≤| Φ u|2 avg（v）−k/2（因为avg（u）≤ avg（v））。此外，对于每个门u∈C2，最小值（|Yu|、|Z u|）≤ avg（u）0。因为行列式由行列式计算，所以所有的变量都出现在行列式中。2由定理4.2可知，在μ的支撑下存在一个划分A，使得μ是k-弱的，k =[n/2] μ。根据定理3.1，由于行列式是计算的，Rank（Mdet（X）A）≤ |Ψ |2 m−k/2<2 m。15秩（Mdet（X）A）=Y秩（My−z）=2m，[使用属性3。 第2.5条，并使用上述备注4.1，这是个矛盾因此，在本发明中，我我i∈[m]|≥（d + 1）−2 /（2 d +1）|Ψ|1 /（2 d +1）≥ 2 n/（1 /d）|1/(2d+1) ≥ 2 nΩ(1/d)（因为d=o（logn/ log logn））。 一个类似的论证表明，如果Φ计算永久变量，则|≥ 2 n（1 /d）。|≥ 2nΩ(1/d).在本节的其余部分，我们证明定理4.2。定理的证明大致如下。选择一个随机分区Aµ。使用权利要求4.5，ΦA中的每个中心路径包含无效门。我们将粗略地证明，每个无效门都有低秩，概率为1− 2−n1/d。由于中心路径的数目最多是公式的大小，因此定理将使用并界来遵循。实际的证明更加复杂，因此我们需要更多的定义和一些引理。4.4定义W对于一个划分A和i∈[m]，记为并且表示Wi=A−1（{yi，zi}），W=i∈[m]Wi=A−1（Y<$Z）(for简单起见，我们从符号中省略了对A的依赖性集合W<$X有一个特殊的结构：回想一下，我们认为X是一个变量矩阵。 每个变量xi，j∈W都有一个唯一的变量xiJ，jJ/=xi，j在W中与xi，j在同一行或同一列。 集合{xi，j，xiJ，jJ}是集合W1，. . . ，Wm. 集合W1，. . . ，W m形成W到m个不相交对的划分。如果你不介意的话Wi（X<$）=Wi<$X<$且W（X<$）=W<$X <$，16[48..... S.公司简介927d一个J并且表示WJ（X）=i ∈ [m]：|Wi（X）|=1个Wi（X）.集合WJ（X_j）是所有xi，j∈W（X_j）的集合，其中W（X_j）中没有其他变量与xi，j在同一行或同一列。对于Φ中的门v，表示W（v）= W（X v）。4.5无效的门和好的W对于l，τ ∈ N，Φ A中的门v称为（l，τ）-无效门，如果v是乘积门，使得|W（v）|≥ lτ，且每个门u∈CHILD（v）允许|W（u）| ≤ |W（v）|/τ。粗略地说，一个无效门是一个有许多子门的门，每个子门都有很少的变量。我们定义好的W我们说W对Φ是好的，如果对于每个（l，τ）-无效门v，22Φ，对于l=[n]和τ=[n /2]，存在一个整数l≥l和一族两两不相交集C1，. . . ，C[τ/2]∈C（v），使得对于每个i ∈ {1，. . . ，[τ/2 π}，lJ≤W（i）≤2lJ且WJ（i）≥lJ，其中，对于每个i ∈ { 1，.，.，.}，W（i）=W u∈ CiX u且WJ（i）= W Ju∈CiX u。. .，[τ/2π}. W为好的条件将帮助我们证明无效门具有低秩和高概率。4.6定理4.2的证明下面的命题说明小公式有好的W。4.3号提案 设Φ是变量集X={xi，j}i，j∈[n]上的一个d-范式语法上的多线性算术公式，使得所有的变量都在Φ中cur. 然后，P [W对Φ不好] ≤ |Φ |2 −n（1）+o（1），其中W=A−1（Y<$Z）且A<$µ。172≤ ||−n≤ ||−n||−n下面的命题指出，具有良好W的小公式可以变得弱。我们将使用以下符号。对于一个适合于Φ的集合W<$X，用μ（W）表示在A−1（Y<$Z）=W的条件下A<$μ上的分布。4.4号提案 设Φ是变量集X={xi，j}i，j∈[n]上的一个d-范式语法上的多线性算术公式，使得所有变量都在Φ中收敛. 假设对于Φ，W∈X是g ood。然后，P [Φ A不是k-弱的] ≤ |Φ |2 −n（1/d）2对于k =[n 27 d/2 π]，其中A π μ（W）.现在我们来证明定理4.2。设Aµ，W = A−1（YZ），k =[n27 d/2。通过以上两个命题，P [Φ A不是k-弱]= P [Φ A不是k-弱|W对Φ有利]·P [W对Φ有利]+ P [Φ A]不是k-弱的|W不适合Φ]·P [W不适合Φ]（1/d）（1）Φ 2 + Φ 2+o（1）（1/d）Φ2+ o（1）。在本节的其余部分，我们将证明命题4.3和命题4.4。我们先来证明命题4.4。4.7命题4.4在证明命题之前，我们需要中心路的以下性质。4.7.1中心路径和无效门下面的声明表明，一个中心路径包含一个无效的门。权利要求4.5. 设d，l，τ ∈ N使得τ ≥ 2. 设A ∈ supp（μ），且令φ = Φ A。 设v是n中的一个门，使得n是d-正规形式，|W（v）|> l·（2 τ）d. 然后，从输入门到v的每个k-中心路径（0 ≤ k ≤ l）包含一个（l，τ）-无效门。18[2014-05-23]48CHILD（v）\（Si∈{1，. ，[τ/2π}Ci）. Den oteDi=. DA（W（i））. ，并且由E来确定E ∈{1，.. ，[τ/2π}Di<两千证据该声明遵循d上的归纳。d= 0，因为|W（v）|> l，因为对于每个输入门|W（v）|≤ 1，没有k-中心路径到达v. 这是一种（在空洞的意义上）的主张。d >0如果没有到达v的k-中心路径，则如下所述。否则，设γ是到达v的k-中心路，u是v在γ中的子路。由于Φv有d-normal-from，u是乘积门。因为γ是k-中心的，|W（u）| ≥ |W（v）|-k。设w是u在γ中的子项。如果|W（w）| ≤ |W（u）|/τ，因为γ是k-中心的，所以对于u的每个子都是如此。因此，由于|W（u）|≥lτ，u是（l，τ）-无效的.否则，|W（w）| ≥ |W（u）|/τ >（l·（2 τ）d−k）/τ≥l·（2 τ）d−1。现在，通过归纳，从一个输入门到w的每一条k-中心路径都包含一个（l，τ）-无效门。因此，γ包含一个（l，τ）-无效门，并遵循该声明。4.7.2命题4.4设A∈μ（W），其中W对Φ有好处。记为φ = ΦA，并回忆我们认为Φ的门和φ的门是我们首先注意到，对于Φ中的每个门v，不管A如何，|=2 · avg（v）。|= 2·avg(v).2设γ是从输入门到输出门的l-中心路径，其中l=n_9（如果不存在2这样的路径，命题如下）。 设τ =[n27 d/2 π]。 由于所有变量都发生在Φ中（并且由于l·（2τ）dm对于足够大的n），根据权利要求4.5，γ包含（l，τ）-无效门v。我们将证明v没有k-低秩的概率是2−n<$（1/d）。然后，使用并界，命题将随之而来。由于W是好的，所以存在一个整数LJ≥l，和一族两两不交集C1，. . .，C[τ/2 π]子（v）使得对于每个i∈ {1，，. . .，[τ/2 π}，lJ≤. W（i）. ≤ 2 lJ且。WJ（i）. ≥lJ，其中W（i）=W。Su∈CiXu∈ Ci，且WJ（i）=. W.J. Su∈C. i∈{1，. . . ，[τ/2π}. DenoteC0=19ΣYv48. [啊。200F或每个i∈{0，. . . ，[τ/2π}，用Mi表示Qu∈CiΦ^u的部分导数矩阵，并表示vg（i）=我们将证明E的概率至多为2−n<$（1/d）。这将完成命题的证明u∈Ci平均值（u）按属性1.命题2.5的Rank（M0）≤ 2avg（0），且对任意i∈ {1，. . .，[τ/2 π}，R ank（Mi）≤2avg（i）−Di/2。由于Φ是语法上多线性的，avg（v）=i∈{0，.，[τ/2π}avg（i）.此外，使用属性3。第2.5章，因此，我们认为，等级（Mv）=i ∈{0，.，[τ/2π}R ank（Mi）≤2avg（v）−i∈{1，. . . ，[τ/2π}Di/2.P[v没有k-低秩]=P[秩（M）>2avg（v）−k]≤P[E]≤2−n（1/d）。因此，它仍然是约束的概率E。我们现在将WJJ（i）定义为（粗略地）Did ends所依赖的变量的集合。对于任意的变量x∈WJ（i），存在唯一的变量sx∈W，满足Wj={x，x∈}，其中j∈[m]（x∈W中与x在同一空间的变量）. 设WJ J（i）是所有x ∈ W的集合，则W j j（i）是x ∈ W的集合，则x ∈ W j（i）对某个j ∈ [ m ]，x∈ W j（i）满足W j = { x，x ∈}.我们现在确定一个集合T{1，. . .，[τ/2 <$}的大小|不|≥τ/400使得随机变量{Di}i∈T是“几乎”独立的。我们将通过以下迭代过程找到T：T0是空集。给定Th，我们将Th+1定义如下。因为对于每个i∈T h，我们有|W（i）|≤ 2 lJ，则可以得出W（i）≤2 lJh.i∈Th另外，对于每个i ∈ {1，. . . ，[τ/2 π}\T h，|为|W j（i）|≥ l j. |≥ lJ.因此，只要h <τ/400，则存在j ∈ {1，. . . ，[τ/2 π}\T h，使得. WJJ（j）\[W（i）. ≥ lJ.i∈Th20设Th+1=Th<${j}。最后，设T=Th，h=[τ/4 00|. 为了简单起见，不失一般性地假设Th={1，. . . ，h}，对于每个h。