By applying(5)recursively,it is not hard to see that one can compute the quantity R(C,x) eractly.Of course,exact computation using this scheme will typically require exponential time,so as in [12]we will stop the recursion at some(small)depth L to keep the computations feasible within polynomial time.This will yield a quantity R(C,x,L)and the hope is that, by choosing L appropriately,the error R(C,L)-R(C,x)will be sufficiently small. In light of(5),a natural way to define R(C,L)for integer L>0 is as follows7. 1, if x is free in C orL=0, R(C,x,L) -Π路尚) otherwise. It is immediate that when the formula C has maximum degree bounded by a constant and, further,every clause has arity also bounded above by a constant,one can compute R(C,x,L) in time polynomial in n whenever L=O(logn).To account for formulas where the arities of the clauses can be arbitrarily large (but still where the degrees of variables are bounded by a constant),one needs to be more careful with clauses of large arity (i.e.,when their arity as a function of n is w(1),say log n).As in [12],we will account for this more general setting by pruning the recursion earlier whenever we encounter clauses with large arity. Definition 11.For any integer w,let :[loge(w+1)1. Note that l=...=15 =1.For integer L,we set if x is free in C or L≤0， R(C,,L)= Π11-Π) R(Ci.j.i.jL-Lu) (7) otherwise. The particular choice of the logarithm base in Definition 11 is not very important as long as it is a big enough constant.The quantity R(C,r,L)is typically called a "message" (because it gets passed up the computation tree). Remark 12.For formulas C with a variable x which is not forced in C,we have the lower bound R(C,)z(1/2)4-(C).The bound is simple to see using (5)and the fact that R(Ci,xi）≤1 for all i∈[dr(C)】andj∈[l.Similark4,for all integers L and all nodes (C,)in the computation tree we have the bound R(C,r,L)>(1/2)d=(C). 3 Proof Outline We want to guarantee that the error R(C,x,L)-R(C,r)is exponentially small in L.Notice that if we run the recursion long enough,it computes the true value;namely,R(C,oo)= R(C,z).More precisely,we will prove the following two lemmas,which correspond to the settings of Theorem 2 and Theorem 3,respectively.Recall that C&.A is the set of all monotone CNF formulas which have maximum degree at most A and whose clauses have arity at least k. Our proof will use the following constant. Definition 13.Let a =1-10-4. 7Note that the value 1 of R(C,,L)when L<0 is somewhat arbitrary since L0 corresponds to stopping the recursion.Our choice of the value 1 will be convenient for technical reasons that will become apparent in the proof of the upcoming Lemma 20. 11
By applying (5) recursively, it is not hard to see that one can compute the quantity R(C, x) exactly. Of course, exact computation using this scheme will typically require exponential time, so as in [12] we will stop the recursion at some (small) depth L to keep the computations feasible within polynomial time. This will yield a quantity R(C, x, L) and the hope is that, by choosing L appropriately, the error |R(C, x, L) − R(C, x)| will be sufficiently small. In light of (5), a natural way to define R(C, x, L) for integer L ≥ 0 is as follows7 . R(C, x, L) = { 1, if x is free in Ce or L = 0, ∏d i=1 ( 1 − ∏wi j=1 R(Ci,j ,xi,j ,L−1) 1+R(Ci,j ,xi,j ,L−1) ) , otherwise. It is immediate that when the formula C has maximum degree bounded by a constant and, further, every clause has arity also bounded above by a constant, one can compute R(C, x, L) in time polynomial in n whenever L = O(log n). To account for formulas where the arities of the clauses can be arbitrarily large (but still where the degrees of variables are bounded by a constant), one needs to be more careful with clauses of large arity (i.e., when their arity as a function of n is ω(1), say log n). As in [12], we will account for this more general setting by pruning the recursion earlier whenever we encounter clauses with large arity. Definition 11. For any integer w, let lw := ⌈log6 (w + 1)⌉. Note that l1 = . . . = l5 = 1. For integer L, we set R(C, x, L) = { 1, if x is free in Ce or L ≤ 0, ∏d i=1 ( 1 − ∏wi j=1 R(Ci,j ,xi,j ,L−lwi ) 1+R(Ci,j ,xi,j ,L−lwi ) ) , otherwise. (7) The particular choice of the logarithm base in Definition 11 is not very important as long as it is a big enough constant. The quantity R(C, x, L) is typically called a “message” (because it gets passed up the computation tree). Remark 12. For formulas C with a variable x which is not forced in C, we have the lower bound R(C, x) ≥ (1/2)dx(C) . The bound is simple to see using (5) and the fact that R(Ci,j , xi,j ) ≤ 1 for all i ∈ [dx(C)] and j ∈ [wi ]. Similarly, for all integers L and all nodes (C, x) in the computation tree we have the bound R(C, x, L) ≥ (1/2)dx(C) . 3 Proof Outline We want to guarantee that the error |R(C, x, L)−R(C, x)| is exponentially small in L. Notice that if we run the recursion long enough, it computes the true value; namely, R(C, x, ∞) = R(C, x). More precisely, we will prove the following two lemmas, which correspond to the settings of Theorem 2 and Theorem 3, respectively. Recall that Ck,∆ is the set of all monotone CNF formulas which have maximum degree at most ∆ and whose clauses have arity at least k. Our proof will use the following constant. Definition 13. Let α = 1 − 10−4 . 7Note that the value 1 of R(C, x, L) when L ≤ 0 is somewhat arbitrary since L ≤ 0 corresponds to stopping the recursion. Our choice of the value 1 will be convenient for technical reasons that will become apparent in the proof of the upcoming Lemma 20. 11
Lemma 14.There erists a constant T >0 such that for every CEC3.6,every variable x EC, and every integer L. IR(C,x,L)-R(C,x,o川≤ra Lemma 15.Let k and△be two integers such that k≥△and△≥200.There exists a constant T>0 such that for every CECk.A;every variable x in C,and every integer L, |R(C,x,L)-R(C,x,oo)川≤ra Our proof uses correlation decay techniques together with a new method which accounts for the shape of the computation tree.Lemma 15 is technically simpler and is proved in Section 4 to better illustrate the idea.Lemma 14 is proved in Section 5.In the rest of this section,we give an overview of our overall proof strategy. To analyze the error of the recursion,the standard approach so far in the literature has been to show that,for a node (C,r)in the computation tree,the quantity R(C,z,L)- R(C,,oo)is bounded by a maxijR(Cij,rij,L-1)-R(Cij,ij,oo)for some constant 0<a 1.This allows one to inductively deduce that R(C,x,L)-R(C,x,oo)decays exponentially in L.This approach has been extremely successful when strong spatial mixing holds[18,11,12,17,23,13]. In fact,this step-wise decay seldom holds if we track R(C,x,L)directly.Instead,the analysis is usually done by tracking (R(C,r,L))for an appropriate potential function In particular,letΦ：(0，l→R be a potential function that satisfies: is continuously differentiable on (0,1],and :=satisfies (z)>0 for z(0,1].(8) The usual approach is to show that(R(C,,L))-(R(C,x,oo))decays exponentially in L,which is sufficient to imply lemmas like Lemma 14 and Lemma 15. In our setting,this inductive approach is problematic since,inside the computation tree, we are faced with the possibility that the formula at the root of a subtree could have many arity-2 clauses.For A>6,these subtrees prohibit the application of the above proof scheme since they are in non-uniqueness and hence the desired step-by-step decay is no longer present, regardless of the choice of the potential function. While arity-2 clauses are problematic,clauses with larger arities do at least lead to good decay of correlation in a single step.In general,as the arity gets larger,the decay gets better. Thus,our approach is to do an amortised analysis.In a single step,we track both the one-step decay of correlation and the number of variables in the current formula that are pinned to 0. These 0 pinnings will decrease the effective arity of clauses,and will later lead to worse decay. More formally,we will track a specific quantity m(C,x,L)which is assigned to each node in the computation tree.Let C*be the original monotone CNF formula and let (C,z)be a node in the computation tree.As explained in Section 2.3,each clause c'of C is obtained from a clause c of C*by pinning a certain number of variables to 0(possibly none),which effectively is the same as removing those variables from the clause.We call these 0-pinnings deficits and let max{0,k-lc}be the number of deficits of c.Note that a clause of arity larger than k is considered to have no deficit,although some variables of it may have been pinned to 0. Definition 16.Let D(C)=cec max{o,k-lc}denote the sum of the deficits of the clauses in C. 12
Lemma 14. There exists a constant τ > 0 such that for every C ∈ C3,6, every variable x ∈ C, and every integer L, |R(C, x, L) − R(C, x, ∞)| ≤ ταL . Lemma 15. Let k and ∆ be two integers such that k ≥ ∆ and ∆ ≥ 200. There exists a constant τ > 0 such that for every C ∈ Ck,∆, every variable x in C, and every integer L, |R(C, x, L) − R(C, x, ∞)| ≤ ταL . Our proof uses correlation decay techniques together with a new method which accounts for the shape of the computation tree. Lemma 15 is technically simpler and is proved in Section 4 to better illustrate the idea. Lemma 14 is proved in Section 5. In the rest of this section, we give an overview of our overall proof strategy. To analyze the error of the recursion, the standard approach so far in the literature has been to show that, for a node (C, x) in the computation tree, the quantity |R(C, x, L) − R(C, x, ∞)| is bounded by α maxi,j |R(Ci,j , xi,j , L − 1) − R(Ci,j , xi,j , ∞)| for some constant 0 < α < 1. This allows one to inductively deduce that |R(C, x, L) − R(C, x, ∞)| decays exponentially in L. This approach has been extremely successful when strong spatial mixing holds [18, 11, 12, 17, 23, 13]. In fact, this step-wise decay seldom holds if we track R(C, x, L) directly. Instead, the analysis is usually done by tracking Φ(R(C, x, L)) for an appropriate potential function Φ. In particular, let Φ : (0, 1] → R be a potential function that satisfies: Φ is continuously differentiable on (0, 1], and φ := Φ′ satisfies φ(z) > 0 for z ∈ (0, 1]. (8) The usual approach is to show that |Φ(R(C, x, L)) − Φ(R(C, x, ∞))| decays exponentially in L, which is sufficient to imply lemmas like Lemma 14 and Lemma 15. In our setting, this inductive approach is problematic since, inside the computation tree, we are faced with the possibility that the formula at the root of a subtree could have many arity-2 clauses. For ∆ ≥ 6, these subtrees prohibit the application of the above proof scheme since they are in non-uniqueness and hence the desired step-by-step decay is no longer present, regardless of the choice of the potential function. While arity-2 clauses are problematic, clauses with larger arities do at least lead to good decay of correlation in a single step. In general, as the arity gets larger, the decay gets better. Thus, our approach is to do an amortised analysis. In a single step, we track both the one-step decay of correlation and the number of variables in the current formula that are pinned to 0. These 0 pinnings will decrease the effective arity of clauses, and will later lead to worse decay. More formally, we will track a specific quantity m(C, x, L) which is assigned to each node in the computation tree. Let C ∗ be the original monotone CNF formula and let (C, x) be a node in the computation tree. As explained in Section 2.3, each clause c ′ of C is obtained from a clause c of C ∗ by pinning a certain number of variables to 0 (possibly none), which effectively is the same as removing those variables from the clause. We call these 0-pinnings deficits and let max{0, k − |c ′ |} be the number of deficits of c ′ . Note that a clause of arity larger than k is considered to have no deficit, although some variables of it may have been pinned to 0. Definition 16. Let D(C) = ∑ c ′∈C max{0, k − |c ′ |} denote the sum of the deficits of the clauses in C. 12
Observe that if a clause c of C*does not show up in C,it does not contribute any deficits. For any node(C,x)in the computation tree,let m(C,z,L):=D(C)(R(C,,L)) where 6(0,1)is a constant that we will choose later,and the potential function will be specified shortly in Definition 17.Crucially,the root formula C*satisfies lm(C,x,L)-m(C*,x,o)川=lΦ(R(C,x,L)-Φ(R(C*,x,o)川 since at the root no variable is pinned yet and D(C*)=0.Thus,the key step is to show that the quantity m(C,x,L)-m(C,oo)decays exponentially with L;we will show that,for an arbitrary node (C,z)in the computation tree,it holds that Im(C,,L)-m(C,x,oo)I<a maxi,j lm(Cij,zij,L-1)-m(Cij,ri.j,oo), (9) where a =1-10-4 is from Definition 13. In previous applications of the correlation decay technique,the ordering of the children of each node (C,x)is usually arbitrary.Since we want to take the shape of the computation tree into consideration,this ordering becomes important to us.We will order clauses in the order of increasing size,except that we leave arity 2 clauses to the end. Unfortunately,the quantity m(C,,L)is more complicated than the plain message R(C,x,L) and it is even more complicated than (R(C,x,L)),since it incorporates combinatorial infor- mation about the formula C and thus it does not satisfy a simple recursion (unlike R(C,L)). Nevertheless,we are able to define a multi-variable quantity K(see (12))and we will show (see Lemma 20)that when K 1,inequality (9)holds. We will use the following potential function,which satisfies (8)as required.In general, the choice of an appropriate potential function is guided by an"educated guess". Definition 17.Let x=1/2 and =13/10.Define (:=1log X b-zx Let (z)denote (z)so that p()=（2)=地-z Remark 18.The exact values ofx and do not matter at this stage,but it is important that 0<x<1 and >1.For such values of x and v,erists and is uniquely defined over the range ofΦ(z)forz∈(0,1]. 3.1 A general framework to bound the error First let us calculate how the number of deficits changes in one step of the recursion.To avoid trivialities,we assume k >2.Let (C,x)be a node in the computation tree.As in Section 2.3,we first perform a pre-processing step on C which removes redundant clauses and removes clauses of arity 1,producing a new formula C.Every clause in C is a clause of C,so D(C)<D(C).Also,x is neither forced nor free in C(otherwise,(C,x)is a leaf in 13
Observe that if a clause c of C ∗ does not show up in C, it does not contribute any deficits. For any node (C, x) in the computation tree, let m(C, x, L) := δ D(C)Φ(R(C, x, L)) where δ ∈ (0, 1) is a constant that we will choose later, and the potential function Φ will be specified shortly in Definition 17. Crucially, the root formula C ∗ satisfies |m(C ∗ , x, L) − m(C ∗ , x, ∞)| = |Φ(R(C ∗ , x, L)) − Φ(R(C ∗ , x, ∞))|, since at the root no variable is pinned yet and D(C ∗ ) = 0. Thus, the key step is to show that the quantity |m(C, x, L)− m(C, x, ∞)| decays exponentially with L; we will show that, for an arbitrary node (C, x) in the computation tree, it holds that |m(C, x, L) − m(C, x, ∞)| ≤ α maxi,j |m(Ci,j , xi,j , L − 1) − m(Ci,j , xi,j , ∞)|, (9) where α = 1 − 10−4 is from Definition 13. In previous applications of the correlation decay technique, the ordering of the children of each node (C, x) is usually arbitrary. Since we want to take the shape of the computation tree into consideration, this ordering becomes important to us. We will order clauses in the order of increasing size, except that we leave arity 2 clauses to the end. Unfortunately, the quantity m(C, x, L) is more complicated than the plain message R(C, x, L) and it is even more complicated than Φ(R(C, x, L)), since it incorporates combinatorial information about the formula C and thus it does not satisfy a simple recursion (unlike R(C, x, L)). Nevertheless, we are able to define a multi-variable quantity κ∗ (see (12)) and we will show (see Lemma 20) that when κ∗ ≤ 1, inequality (9) holds. We will use the following potential function, which satisfies (8) as required. In general, the choice of an appropriate potential function is guided by an “educated guess”. Definition 17. Let χ = 1/2 and ψ = 13/10. Define Φ(z) := 1 χψ log ( z χ ψ − z χ ) . Let φ(z) denote Φ ′ (z) so that φ(z) := Φ′ (z) = 1 z(ψ − z χ) . Remark 18. The exact values of χ and ψ do not matter at this stage, but it is important that 0 < χ ≤ 1 and ψ > 1. For such values of χ and ψ, Φ −1 exists and is uniquely defined over the range of Φ(z) for z ∈ (0, 1]. 3.1 A general framework to bound the error First let us calculate how the number of deficits changes in one step of the recursion. To avoid trivialities, we assume k ≥ 2. Let (C, x) be a node in the computation tree. As in Section 2.3, we first perform a pre-processing step on C which removes redundant clauses and removes clauses of arity 1, producing a new formula Ce. Every clause in Ce is a clause of C, so D(Ce) ≤ D(C). Also, x is neither forced nor free in Ce (otherwise, (C, x) is a leaf in 13
the computation tree).Let d=d(C)and let c1,...,cd be the clauses where z occurs in C. Recall that w;=cl-1.As we mentioned in Section 3,the order of c1,...,ca is important. We will order clauses in order of increasing size,except that we leave arity-2 clauses to the end.Here is some notation to describe the ordering.Let be denote the number of clauses amongst ci,...,ca with arity e.We will use the variables b,to denote cumulative sums for l>2,sot=0and,fore≥3，=b-1+be.We order the clauses so that,forl≥3，clauses c+,chave arity Finally,clauses c+,...,cd have arity 2.Let si be the sum of the deficits of clauses c1,...,ci.Thus, s=>max(0,k--1). t=1 We will now consider how the deficits change when we construct the node(Ci.i,ij)from (C,r)according to the method described in Section 2.3,where j[wil. The arity-2 clauses in C are always removed in the construction of Cij,resulting in a loss of deficit of b2(k-2). The clauses c1,...,ci are also removed in the construction of Cij resulting in an ad- ditional loss of deficit of smin(id).(The minimum is to avoid double-counting if i>d-b2 since in that cases some of these clauses have arity 2,and have already been counted.) The occurrences of x are pinned to 0 in clauses ci+1,...,cd.Consider some t e fi+ 1,...,d}.If the arity of ct is greater than k then this pinning does not cause any increase in deficit.Also,if the arity of ct is 2,then the clause will be removed,so there is no increase in deficit.Thus,the increase in deficit from these pinnings is at most max(0,b-i). If i<d-b2 then wi>1 and all occurrences of i.1,...,xij-1 are pinned to 0,resulting in an increase in deficit of at most (j-1)(A-1). Let 1i<d-b be zero-one indicator variable for the event that i is at most d-b2.Then,putting these observations together,we conclude that D(Cij)<D(C)-b2(k-2)-Smin(i.d-62)+max(0,b-i)+(j-1)(A-1)1isd-b2. Since D(C)<D(C),we have D(C)≤D(C)-b2(k-2)-8min6.d-b2)+max(0,bk-i)+(j-1(A-1)1isd-b2·(10) Recall that the recursion for R(C,z,L)depends on the function Fd.w(r)implicitly defined by(7),i.e., ea-i0-i） (11) 1 i1 where ri,∈0，l]for all i∈[d and j∈[wl.In particular,unless x is free in C or L≤O,we have R(C,,L)=Fa.w(R(Ci.j;ij,L-:)}). 14
the computation tree). Let d = dx(Ce) and let c1, . . . , cd be the clauses where x occurs in Ce. Recall that wi = |ci | − 1. As we mentioned in Section 3, the order of c1, . . . , cd is important. We will order clauses in order of increasing size, except that we leave arity-2 clauses to the end. Here is some notation to describe the ordering. Let bℓ denote the number of clauses amongst c1, . . . , cd with arity ℓ. We will use the variables b ′ ℓ to denote cumulative sums for ℓ > 2, so b ′ 2 = 0 and, for ℓ ≥ 3, b ′ ℓ = b ′ ℓ−1 + bℓ . We order the clauses so that, for ℓ ≥ 3, clauses cb ′ ℓ−1+1, . . . , cb ′ ℓ have arity ℓ. Finally, clauses cd−b2+1, . . . , cd have arity 2. Let si be the sum of the deficits of clauses c1, . . . , ci . Thus, si = ∑ i t=1 max(0, k − wt − 1). We will now consider how the deficits change when we construct the node (Ci,j , xi,j ) from (C, x e ) according to the method described in Section 2.3, where j ∈ [wi ]. • The arity-2 clauses in Ce are always removed in the construction of Ci,j , resulting in a loss of deficit of b2(k − 2). • The clauses c1, . . . , ci are also removed in the construction of Ci,j resulting in an additional loss of deficit of smin(i,d−b2) . (The minimum is to avoid double-counting if i > d − b2 since in that cases some of these clauses have arity 2, and have already been counted.) • The occurrences of x are pinned to 0 in clauses ci+1, . . . , cd. Consider some t ∈ {i + 1, . . . , d}. If the arity of ct is greater than k then this pinning does not cause any increase in deficit. Also, if the arity of ct is 2, then the clause will be removed, so there is no increase in deficit. Thus, the increase in deficit from these pinnings is at most max(0, b′ k − i). • If i ≤ d − b2 then wi > 1 and all occurrences of xi,1, . . . , xi,j−1 are pinned to 0, resulting in an increase in deficit of at most (j − 1)(∆ − 1). Let 1i≤d−b2 be zero-one indicator variable for the event that i is at most d−b2. Then, putting these observations together, we conclude that D(Ci,j ) ≤ D(Ce) − b2(k − 2) − smin(i,d−b2) + max(0, b′ k − i) + (j − 1)(∆ − 1)1i≤d−b2 . Since D(Ce) ≤ D(C), we have D(Ci,j ) ≤ D(C) − b2(k − 2) − smin(i,d−b2) + max(0, b′ k − i) + (j − 1)(∆ − 1)1i≤d−b2 . (10) Recall that the recursion for R(C, x, L) depends on the function F d,w(r) implicitly defined by (7), i.e., F d,w(r) := ∏ d i=1 ( 1 − ∏wi j=1 ri,j 1 + ri,j ) , (11) where ri,j ∈ [0, 1] for all i ∈ [d] and j ∈ [wi ]. In particular, unless x is free in Ce or L ≤ 0, we have R(C, x, L) = F d,w({R(Ci,j , xi,j , L − lwi )}). 14
The m(C,L)variables also satisfy a recursion which could be made explicit by map- ping them back to the R(C,z,L)variables,though we will not directly analyse this recur- sion.Instead,we will define a quantity w(r)which tracks the rate at which m(C,,L)- m(C,,o)I decays in the recursion.Specifically,define w(r)as follows a-bi6(ba(k-2)+()-max-i)-(j-1)(-1)1sa-v)P(Fdw(r)0Fd.w(r) i=1=1 p(rij) ∂rij (12) The main step in the proofs of Lemma 14 and Lemma 15 will be to bound(r).By construction,the elements in w are in increasing order,apart from the 1s at the end,and the bound on kw(r)will use this fact,so we give the following definition. Definition 19.Let wo =2.A vector w=w1,...,wd is suitable if its entries are positive integers and there is a t∈{0，，d such for all j in{l,,t,wj≥wj-1 and for all j in {t+1,...,d,wj =1.Given a suitable vector w we use the following global notation (which depends implicitly on w):be is the number of entries of w which are equal to e-1. ik=bg+…+be.Finally,s=∑t-1max(0,k-w-l). Lemma20.Suppose that△and k are integers with△≥2andk≥3.Suppose that there are constants0<6<1andU>0 such that,.for all1≤d≤△，all suitable w=w1,.,wa, and all r satisfying(1/2)A-l1≤r≤1，it holds that 4w()≤ when d≤△-1， U (13) when d=△. Then there exists a constant T>0 such that,,for every C∈Ck,△，every variable x∈C, and every integer L,it holds that lR(C,x,L)-R(C,,∞川≤ra (14) Proof.We will show that there is a constant>0 such that for all such C,x and L,it holds that lm(C,x,L)-m(C,x,o川≤a (15) Assuming (15)for the moment,let us conclude (14).Consider CE Ck.A.We may assume that L >0 since for L=0 the inequality (14)holds for all sufficiently large r (any T>1 works).Consider any z C and consider the computation tree rooted at (C,z).By the definition of m(,,)and since by assumption D(C)=0,we have that lm(C,x,L)-m(C,x,o川=Φ(R(C,x,L)-Φ(R(C,x,oo)儿 (16) Let)=(1/2)△-1 and let Kain :min ()min () and xEn,1 x∈[n,1] == xEn,1 Since o is continuous and ()>0 for all r [n,1],we have that Kmin and Kax are positive. We have that RC,-RC,xoI≤(RC,xL)-RC,工，o川 (17) 15
The m(C, x, L) variables also satisfy a recursion which could be made explicit by mapping them back to the R(C, x, L) variables, though we will not directly analyse this recursion. Instead, we will define a quantity κ d,w ∗ (r) which tracks the rate at which |m(C, x, L) − m(C, x, ∞)| decays in the recursion. Specifically, define κ d,w ∗ (r) as follows. κ d,w ∗ (r) := ∑ d i=1 ∑wi j=1 α −lwi δ (b2(k−2)+smin(i,d−b2)−max(0,b′ k−i)−(j−1)(∆−1)1i≤d−b2 )φ(F d,w(r)) φ(ri,j ) ∂Fd,w(r) ∂ri,j . (12) The main step in the proofs of Lemma 14 and Lemma 15 will be to bound κ d,w ∗ (r). By construction, the elements in w are in increasing order, apart from the 1s at the end, and the bound on κ d,w ∗ (r) will use this fact, so we give the following definition. Definition 19. Let w0 = 2. A vector w = w1, . . . , wd is suitable if its entries are positive integers and there is a t ∈ {0, . . . , d} such for all j in {1, . . . , t}, wj ≥ wj−1 and for all j in {t + 1, . . . , d}, wj = 1. Given a suitable vector w we use the following global notation (which depends implicitly on w): bℓ is the number of entries of w which are equal to ℓ − 1. b ′ k = b3 + · · · + bk. Finally, si = ∑i t=1 max(0, k − wt − 1). Lemma 20. Suppose that ∆ and k are integers with ∆ ≥ 2 and k ≥ 3. Suppose that there are constants 0 < δ < 1 and U > 0 such that, for all 1 ≤ d ≤ ∆, all suitable w = w1, . . . , wd, and all r satisfying (1/2)∆−11 ≤ r ≤ 1, it holds that κ d,w ∗ (r) ≤ { 1, when d ≤ ∆ − 1, U, when d = ∆. (13) Then there exists a constant τ > 0 such that, for every C ∈ Ck,∆, every variable x ∈ C, and every integer L, it holds that |R(C, x, L) − R(C, x, ∞)| ≤ ταL . (14) Proof. We will show that there is a constant τ >ˆ 0 such that for all such C, x and L, it holds that |m(C, x, L) − m(C, x, ∞)| ≤ ταˆ L . (15) Assuming (15) for the moment, let us conclude (14). Consider C ∈ Ck,∆. We may assume that L > 0 since for L = 0 the inequality (14) holds for all sufficiently large τ (any τ ≥ 1 works). Consider any x ∈ C and consider the computation tree rooted at (C, x). By the definition of m(·, ·, ·) and since by assumption D(C) = 0, we have that |m(C, x, L) − m(C, x, ∞)| = Φ(R(C, x, L)) − Φ(R(C, x, ∞)) . (16) Let η = (1/2)∆−1 and let Kmin Φ := min x∈[η,1] Φ ′ (x) = min x∈[η,1] φ(x), and Kmax Φ := max x∈[η,1] Φ ′ (x) = max x∈[η,1] φ(x). Since φ is continuous and φ(x) > 0 for all x ∈ [η, 1], we have that Kmin Φ and Kmax Φ are positive. We have that |R(C, x, L) − R(C, x, ∞)| ≤ 1 Kmin Φ |Φ(R(C, x, L)) − Φ(R(C, x, ∞))|. (17) 15