To see (17),we may assume that R(C,,L)R(C,x,oo)(otherwise the inequality holds at equality),in which case the inequality follows by an immediate application of the Mean Value Theorem to the function Combining (16),(17)with (15)yields (14)with r =/kin,as desired. To prove (15),we will first show a slightly weaker claim.Namely,for all nodes(C,x)in the computation tree where C∈Ck,△andx∈C is a variable with degree≤△-l,for all integer L,it holds that lm(C,x,L)-m(C,E,o川≤Kaxa (18) ForL≤O,we have that m(C,x,L)-m(C,x,∞1=6DC)IΦ(R(C,x,L)-重(R(C,,∞)川 ≤K雷a|R(C,E,L)-R(C,x,o)川≤Kax, where in the first inequality we used that 6 (0,1],D(C)>0 and an application of the Mean Value theorem analogous to the one used in (17),while in the second inequality we used that for L<0 it holds that R(C,x,L)=1 (by definition)and 0<R(C,x,oo)<1. Since 0<a<1,this proves (18)for L<0. To prove (18)for integer L>0 we proceed by induction on L.Namely,we assume that L>0 and that (18)holds for all smaller values than L (the base cases L <0 have already been shown). Recall from(4)that x is not forced in C and that C is the formula obtained by removing the redundant clauses in C.We may assume that z is not free in C-otherwise,observe that R(C,,L)=R(C,x,oo)=1 and thus m(C,x,L)=m(C,x,oo),so that (18)holds.We will thus focus on x which appear only in (a non-zero number of)clauses in C of arity >2. Letd=dz(C).Fori∈[d and j∈[ul,it holds that m(Cij::L-l)=D(C3)(R(Cij:ij:L-L)) (19) m(Cj,i,o)=6DC)重(R(Cj,xi,0∞). Denote by r()the vector whose coordinates are given by R(Ci.j,ij,L-lw)for ie[d]and j[wi].Denote also by r(2)the vector whose coordinates are given by R(Cij,ij,oo)for i∈[d]and j∈[w.Observe that R(C,,L)=R(C,,L)=Fd.w(r(1))and R(C,,o)=R(C,,0)=Fd.w (r(2)). Note also that n1<r(1),r(2)<1(cf.property (4)for the nodes of the computation tree,(7), footnote 7 and Remark 12). We next boundΦ(F4w(r）-Φ(F4w(r2②)川in terms of maxiΦ()-Φ(r)l.For convenience,denote F:=Fd,w and for i[d and j [wil,let :=()，2=Φ(r) For0∈0，l,leta(0)=0z9+(1-0)z号and letri(0)=重-1(a(0)(note that the inverseΦ-1 exists and is uniquely defined in the intervalΦ([m,l)cf.Remark 18and(⑧)： Denote by r()the vector whose coordinates are ri(0)and note that n1 <r(0)<1.Finally, let h():=(F(r())).Observe that h is differentiable for all values of E [0,1].By applying 16
To see (17), we may assume that R(C, x, L) ̸= R(C, x, ∞) (otherwise the inequality holds at equality), in which case the inequality follows by an immediate application of the Mean Value Theorem to the function Φ. Combining (16), (17) with (15) yields (14) with τ = ˆτ /Kmin Φ , as desired. To prove (15), we will first show a slightly weaker claim. Namely, for all nodes (C, x) in the computation tree where C ∈ Ck,∆ and x ∈ C is a variable with degree ≤ ∆ − 1, for all integer L, it holds that |m(C, x, L) − m(C, x, ∞)| ≤ Kmax Φ α L . (18) For L ≤ 0, we have that |m(C, x, L) − m(C, x, ∞)| = δ D(C) |Φ(R(C, x, L)) − Φ(R(C, x, ∞))| ≤ Kmax Φ |R(C, x, L) − R(C, x, ∞)| ≤ Kmax Φ , where in the first inequality we used that δ ∈ (0, 1], D(C) ≥ 0 and an application of the Mean Value theorem analogous to the one used in (17), while in the second inequality we used that for L ≤ 0 it holds that R(C, x, L) = 1 (by definition) and 0 ≤ R(C, x, ∞) ≤ 1. Since 0 < α < 1, this proves (18) for L ≤ 0. To prove (18) for integer L > 0 we proceed by induction on L. Namely, we assume that L > 0 and that (18) holds for all smaller values than L (the base cases L ≤ 0 have already been shown). Recall from (4) that x is not forced in C and that Ce is the formula obtained by removing the redundant clauses in C. We may assume that x is not free in Ce — otherwise, observe that R(C, x, L) = R(C, x, ∞) = 1 and thus m(C, x, L) = m(C, x, ∞), so that (18) holds. We will thus focus on x which appear only in (a non-zero number of) clauses in Ce of arity ≥ 2. Let d = dx(Ce). For i ∈ [d] and j ∈ [wi ], it holds that m(Ci,j , xi,j , L − lwi ) = δ D(Ci,j ) Φ(R(Ci,j , xi,j , L − lwi )) m(Ci,j , xi,j , ∞) = δ D(Ci,j ) Φ(R(Ci,j , xi,j , ∞)). (19) Denote by r (1) the vector whose coordinates are given by R(Ci,j , xi,j , L − lwi ) for i ∈ [d] and j ∈ [wi ]. Denote also by r (2) the vector whose coordinates are given by R(Ci,j , xi,j , ∞) for i ∈ [d] and j ∈ [wi ]. Observe that R(C, x, L) = R(C, x, L e ) = F d,w ( r (1)) and R(C, x, ∞) = R(C, x, e ∞) = F d,w ( r (2)) . Note also that η1 ≤ r (1) , r (2) ≤ 1 (cf. property (4) for the nodes of the computation tree, (7), footnote 7 and Remark 12). We next bound Φ ( F d,w(r (1)) ) −Φ ( F d,w(r (2)) ) in terms of maxi,j Φ ( r (1) i,j ) −Φ ( r (2) i,j ) . For convenience, denote F := F d,w and for i ∈ [d] and j ∈ [wi ], let z (1) i,j := Φ( r (1) i,j ) , z (2) i,j := Φ( r (2) i,j ) . For θ ∈ [0, 1], let zi,j (θ) := θ z(1) i,j + (1 − θ) z (2) i,j and let ri,j (θ) := Φ−1 (zi,j (θ)) (note that the inverse Φ −1 exists and is uniquely defined in the interval Φ([η, 1]) cf. Remark 18 and (8)). Denote by r(θ) the vector whose coordinates are ri,j (θ) and note that η1 ≤ r(θ) ≤ 1. Finally, let h(θ) := Φ(F(r(θ))). Observe that h is differentiable for all values of θ ∈ [0, 1]. By applying 16
the Mean Value theorem to the function h(),we obtain that there exists 0o (0,1)such that Φ(F(r)-Φ(F(2)= ah 009=o We have that d ∂h aF(r(0))arij(0) a0 F(》=dErO)2Fo-®Fr(o a0 a0 Orij 1 =Φ'(F(r(0) ∑∑o aF(r(0))azi(0) Orij a0 =1j=1 =Φ'(F(r(0)】 1 FG() =1=1 Orij It follows that lm(C,x,L)-m(C,x,o川 =6DC1厘(R(C,x,L)-重(R(C,x,∞)川 ≤max SD(C d wi max -C(m(C)-m(C i=1j=1 p(r,）Tari (20) where the inequality follows by the triangle inequality and the fact (see Definition 17)that p=Φ'satisfies(⑧).Now note that for all i∈[d]and j∈[wl,we have by induction that m(Cij,ij,L-lw)-m(Cij,i)Kaxa (21) From(20)and the bounds(21),we obtain Im(C,,L)-m(C ,oo)Kax max 6PC-DCe(F(F回|a- a p(rij)I arii (22) The lower bounds on D(C)-D(Cii),(10),imply that ∑∑o-c2 F o|。s4“g. d wi (23) =1j=1 p(r）0ri where in the inequality we used that 6(0,1]. Combining (22),(23)and the assumption (13)that w(r)1 for d-1 yields (18), as wanted. 17
the Mean Value theorem to the function h(θ), we obtain that there exists θ0 ∈ (0, 1) such that Φ ( F ( r (1))) − Φ ( F ( r (2))) = ∂h ∂θ θ=θ0 . We have that ∂h ∂θ = ∂Φ(F(r(θ))) ∂θ = Φ′ (F(r(θ)))∂F(r(θ)) ∂θ = Φ′ (F(r(θ))) ∑ d i=1 ∑wi j=1 ∂F(r(θ)) ∂ri,j ∂ri,j (θ) ∂θ = Φ′ (F(r(θ))) ∑ d i=1 ∑wi j=1 1 Φ′(ri,j (θ)) ∂F(r(θ)) ∂ri,j ∂zi,j (θ) ∂θ = Φ′ (F(r(θ))) ∑ d i=1 ∑wi j=1 1 Φ′(ri,j (θ)) ∂F(r(θ)) ∂ri,j ( z (1) i,j − z (2) i,j ) . It follows that |m(C, x, L) − m(C, x, ∞)| = δ D(C) |Φ(R(C, x, L)) − Φ(R(C, x, ∞))| ≤ max r δ D(C) ∑ d i=1 ∑wi j=1 φ(F(r)) φ(ri,j ) ∂F(r) ∂ri,j z (1) i,j − z (2) i,j = max r ∑ d i=1 ∑wi j=1 δ D(C)−D(Ci,j )φ(F(r)) φ(ri,j ) ∂F(r) ∂ri,j m(Ci,j , xi,j , L − lwi ) − m(Ci,j , xi,j , ∞) , (20) where the inequality follows by the triangle inequality and the fact (see Definition 17) that φ = Φ′ satisfies (8). Now note that for all i ∈ [d] and j ∈ [wi ], we have by induction that m(Ci,j , xi,j , L − lwi ) − m(Ci,j , xi,j , ∞) ≤ Kmax Φ α L−lwi . (21) From (20) and the bounds (21), we obtain |m(C, x, L) − m(C, x, ∞)| ≤ Kmax Φ max r ∑ d i=1 ∑wi j=1 δ D(C)−D(Ci,j )φ(F(r)) φ(ri,j ) ∂F(r) ∂ri,j α −lwi α L . (22) The lower bounds on D(C) − D(Ci,j ), (10), imply that ∑ d i=1 ∑wi j=1 δ D(C)−D(Ci,j )φ(F(r)) φ(ri,j ) ∂F(r) ∂ri,j α −lwi ≤ κ d,w ∗ (r), (23) where in the inequality we used that δ ∈ (0, 1]. Combining (22), (23) and the assumption (13) that κ d,w ∗ (r) ≤ 1 for d ≤ ∆ − 1 yields (18), as wanted. 17
Finally,we prove(15)with=Kax.maxfU,1,where U is the constant in assumption (13).For x of degree <A-1,we get (15)immediately from(18).Now suppose that (C,z) are such that x has degree A in C.Note,for a node (C,r')in the computation tree,x'may have degree d =A in C'only if (C,')is the root of the tree.It follows that the children of the node (C,)say (Cij,ij)with ie [d]and j [wil,are such that zij has degree at most A-1 in Cij.Hence,by applying (18),we obtain that (21)holds for all i,j and hence (as before)we deduce that (22),(23)hold as well.Inequality (15)now follows since by assumption(13)we have that4w(r)≤max{U,l}ford≤△. This concludes the proof of Lemma 20. 口 We now state two technical lemmas which will be proved later in the paper.These lemmas verify the premise of Lemma 20 in the settings of Theorems 2 and 3.Note from Equation(12) that(r)depends on the global quantity k and on various quantities (depending on w) which are defined in Definition 19. Lemma2l.Let k and△be two integers such that k≥△and△≥200.There are constants 0<6<1andU>0 such that,for all1≤d≤△，all suitable w=wi,,wd,and all r satisfying0<r≤1，it holds that 4w(r)≤ 1 when d≤△-l when d=△. Lemma 22.Let A=6 and k =3.There are constants 0<6<1 and U>0 such that,for all1≤d≤△，all suitable w=w,,wa,and all r satisfying(1/2)△-l1≤r≤l,it holds that 1. when d≤△-1， U, when d=△. Lemma 21 will be proved in Section 4 and Lemma 22 will be proved in Section 5.Using these lemmas and Lemma 20,we can prove Lemma 14 and Lemma 15. Lemma 14.There exists a constant T>0 such that for every C E C3.6,every variable EC, and every integer L, 1R(C,x,L)-R(C,x,oo川≤Ta Proof.The lemma follows immediately from Lemma 22 and Lemma 20. 口 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 r in C,and every integer L, |R(C,x,L)-R(C,x,o川≤ra2. Proof.The lemma follows immediately from Lemma 21 and Lemma 20 口 3.2 Proof of the main theorems In this section,we give the proofs of Theorems 2 and 3,which we restate here for convenience. Theorem 2.There is an FPTAS for #HyperlndSet(3,6). 18
Finally, we prove (15) with τˆ := Kmax Φ · max{U, 1}, where U is the constant in assumption (13). For x of degree ≤ ∆ − 1, we get (15) immediately from (18). Now suppose that (C, x) are such that x has degree ∆ in C. Note, for a node (C ′ , x′ ) in the computation tree, x ′ may have degree d = ∆ in C ′ only if (C ′ , x′ ) is the root of the tree. It follows that the children of the node (C, x), say (Ci,j , xi,j ) with i ∈ [d] and j ∈ [wi ], are such that xi,j has degree at most ∆ − 1 in Ci,j . Hence, by applying (18), we obtain that (21) holds for all i, j and hence (as before) we deduce that (22), (23) hold as well. Inequality (15) now follows since by assumption (13) we have that κ d,w ∗ (r) ≤ max{U, 1} for d ≤ ∆. This concludes the proof of Lemma 20. We now state two technical lemmas which will be proved later in the paper. These lemmas verify the premise of Lemma 20 in the settings of Theorems 2 and 3. Note from Equation (12) that κ d,w ∗ (r) depends on the global quantity k and on various quantities (depending on w) which are defined in Definition 19. Lemma 21. Let k and ∆ be two integers such that k ≥ ∆ and ∆ ≥ 200. There are constants 0 < δ < 1 and U > 0 such that, for all 1 ≤ d ≤ ∆, all suitable w = w1, . . . , wd, and all r satisfying 0 < r ≤ 1, it holds that κ d,w ∗ (r) ≤ { 1, when d ≤ ∆ − 1, U, when d = ∆. Lemma 22. Let ∆ = 6 and k = 3. 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 = ∆. Lemma 21 will be proved in Section 4 and Lemma 22 will be proved in Section 5. Using these lemmas and Lemma 20, we can prove Lemma 14 and Lemma 15. 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 . Proof. The lemma follows immediately from Lemma 22 and Lemma 20. 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 . Proof. The lemma follows immediately from Lemma 21 and Lemma 20. 3.2 Proof of the main theorems In this section, we give the proofs of Theorems 2 and 3, which we restate here for convenience. Theorem 2. There is an FPTAS for #HyperIndSet(3, 6). 18
Proof.First,reformulate #HyperlndSet(3,6)as the monotone CNF problem with instances in C3.6,following the reformulation in Section 2.2.Then,just invoke Lemmas 7 and 14. Theorem3.Let k and△be two integers such that k≥△and△≥200.Then there is an FPTAS for the problem #HyperlndSet(k,A) Proof.Once again,reformulate #HyperlndSet(k,A)as the monotone CNF problem with in- stances in Ck.A.Then invoke Lemmas 7 and 15. 口 We have now finished the proofs of Theorems 2 and 3 except that we have not yet proved the Lemmas 21 and 22 which we used to bound w(r)in the proofs of Lemmas 14 and 15. Lemma 21 will be proved in Section 4 and Lemma 22 will be proved in Section 5.The proofs bound the multivariate decay rate function(r).This is an optimisation problem that is quite complicated to solve.Moreover,we need to solve it for all possible suitable vectors w. The analysis of bounding (r)is the technical core of our proof. 3.3 Application to counting dominating sets In this section,we use Theorems 2 and 3 to obtain Corollary 4,which we restate here for convenience. Corollary4.For all positive integers△satisfying either△≤5or△≥l99,there is an FPTAS for the problem #RegDomSet(A). The corollary follows from the observation that a dominating set in a A-regular graph is defined by a collection of constraints of arity A+1 with each variable occurring in A+1 constraints.The details are spelled out in the following proof. Proof of Corollary4.Let△be an integer satisfying either2≤△≤5or△≥l99.Let G be a A-regular graph and denote by #DomSets(G)the number of dominating sets in G. Let:=△+l,△'：=△+l.We will construct a k'-uniform hypergraph H where ev- ery vertex of H has degree A'such that the number ZH of independent sets in H satisfies Z=#DomSets(G).To conclude the corollary we then only have to check that,for the relevant range of A,we can invoke one of the FPTASes of Theorems 2 and 3 to approxi- mate ZH.Indeed,when△≥l99,we have△'≥200andk≥△'.Thus,by Theorem3. #HyperlndSet(,A')admits an FPTAS and thus so does #RegDomSet(A).Similarly,when 2≤△≤5，we have△'≤6 andk'≥3.By Theorem2,#HyperlndSet(3,6)admits an FPTAS and thus so does #RegDomSet(A). We conclude the proof by showing the construction of H.For a vertex vE V of G,denote by v1,...,vA its neighbours in G(note that there are exactly A of those since G is A-regular) and let ev=fv,v1,...,vA}.Then H is the hypergraph with vertex set V and hyperedge set F=Uvevee.It is clear from the construction that H is k'-uniform withk'=A+1.Further, every vertex v of H has degree A'=A+1 since it appears in the hyperedges ev,ev,...,eva. This completes the construction of H. It remains to show that the number of dominating sets in the graph G is equal to the number of independent sets in the hypergraph H.It suffices to show that S V is an independent set of H iff V\S is a dominating set of G.Indeed,if S is an independent set of H,then for every vertex v E S,at least one of v1,...,vA is not in S(since ev is a hyperedge of H)and hence V\S is a dominating set of G.Similarly,if VS is a dominating set of G,then 19
Proof. First, reformulate #HyperIndSet(3, 6) as the monotone CNF problem with instances in C3,6, following the reformulation in Section 2.2. Then, just invoke Lemmas 7 and 14. Theorem 3. Let k and ∆ be two integers such that k ≥ ∆ and ∆ ≥ 200. Then there is an FPTAS for the problem #HyperIndSet(k, ∆). Proof. Once again, reformulate #HyperIndSet(k, ∆) as the monotone CNF problem with instances in Ck,∆. Then invoke Lemmas 7 and 15. We have now finished the proofs of Theorems 2 and 3 except that we have not yet proved the Lemmas 21 and 22 which we used to bound κ d,w ∗ (r) in the proofs of Lemmas 14 and 15. Lemma 21 will be proved in Section 4 and Lemma 22 will be proved in Section 5. The proofs bound the multivariate decay rate function κ d,w ∗ (r). This is an optimisation problem that is quite complicated to solve. Moreover, we need to solve it for all possible suitable vectors w. The analysis of bounding κ d,w ∗ (r) is the technical core of our proof. 3.3 Application to counting dominating sets In this section, we use Theorems 2 and 3 to obtain Corollary 4, which we restate here for convenience. Corollary 4. For all positive integers ∆ satisfying either ∆ ≤ 5 or ∆ ≥ 199, there is an FPTAS for the problem #RegDomSet(∆). The corollary follows from the observation that a dominating set in a ∆-regular graph is defined by a collection of constraints of arity ∆ + 1 with each variable occurring in ∆ + 1 constraints. The details are spelled out in the following proof. Proof of Corollary 4. Let ∆ be an integer satisfying either 2 ≤ ∆ ≤ 5 or ∆ ≥ 199. Let G be a ∆-regular graph and denote by #DomSets(G) the number of dominating sets in G. Let k ′ := ∆ + 1, ∆′ := ∆ + 1. We will construct a k ′ -uniform hypergraph H where every vertex of H has degree ∆′ such that the number ZH of independent sets in H satisfies ZH = #DomSets(G). To conclude the corollary we then only have to check that, for the relevant range of ∆, we can invoke one of the FPTASes of Theorems 2 and 3 to approximate ZH. Indeed, when ∆ ≥ 199, we have ∆′ ≥ 200 and k ′ ≥ ∆′ . Thus, by Theorem 3, #HyperIndSet(k ′ , ∆′ ) admits an FPTAS and thus so does #RegDomSet(∆). Similarly, when 2 ≤ ∆ ≤ 5, we have ∆′ ≤ 6 and k ′ ≥ 3. By Theorem 2, #HyperIndSet(3, 6) admits an FPTAS and thus so does #RegDomSet(∆). We conclude the proof by showing the construction of H. For a vertex v ∈ V of G, denote by v1, . . . , v∆ its neighbours in G (note that there are exactly ∆ of those since G is ∆-regular) and let ev = {v, v1, . . . , v∆}. Then H is the hypergraph with vertex set V and hyperedge set F = ∪v∈V ev. It is clear from the construction that H is k ′ -uniform with k ′ = ∆ + 1. Further, every vertex v of H has degree ∆′ = ∆ + 1 since it appears in the hyperedges ev, ev1 , . . . , ev∆. This completes the construction of H. It remains to show that the number of dominating sets in the graph G is equal to the number of independent sets in the hypergraph H. It suffices to show that S ⊆ V is an independent set of H iff V \S is a dominating set of G. Indeed, if S is an independent set of H, then for every vertex v ∈ S, at least one of v1, . . . , v∆ is not in S (since ev is a hyperedge of H) and hence V \S is a dominating set of G. Similarly, if V \S is a dominating set of G, then 19
for every vertex vES,at least one of vi,...,v is in V\S and hence S is an independent set of H(since each hyperedge e of H contains at least one vertex which does not belong to S). This completes the proof. ▣ 4 Bounding the decay rate for large A This section is devoted to proving Lemma 21.Let k and A be two integers such that k>A and A200.We start by setting up some upper bounds on the function(r)which is defined in (12)using notation from Definition 19.Consider the following definitions,which apply to suitable vectors w. a-lm 8sti-dt-(-1)(A-1) 8Fd.w if1≤i≤d-b2, pw(r):- apd.w (24) ifd-b2+1≤i≤d. w(r):=(w(r))6(-2)>pw.i(r). (25) =1 We first argue that(r)dw(r).To see this,note that smin(i.d)is si for 1i d-b2 and is sd-b2ford-b2+1≤i≤d.Also,bk≤d-b2,so max(0,k-i)≤d-b2-iand if i>d-b2+1 then max(0,b -i)=0.Finally,(j-1)(A-1)1isd-b2 is equal to (j-1)(A-1) when1≤i≤d-b2 and to0 when d-b2+1≤i. Recall from Definition 13 that a =1-10-4.For brevity,we will denote Fd.w(r)by F(r). Finally,we define the constant 6(which depends on A). Definition 23.Let c=0.7.Given A,define 6 by A =c. In order to bound kd.w(r),an important special case is when b2 =0.Indeed,as we will see soon,handling this special case implies an upper bound of dw(r)for the general case. Define the following quantity for suitable vectors w. d Π受少-的 ri.j 4o)=-for-e-a-。 1 层高 1十Tij (26) The next lemma gives an upper bound on the quantity Rd.w(r). Lemma24.Let k and△be two integers such that k≥△and△≥200.Let d be a positive integer such that d<A-1.Let w =w1,...,wd be a suitable vector with b2 =0.Then,for allr satisfying0<r≤1，R4,w(r)≤1. In the case d=A for w=w1,...,wd,a suitable vector with b2 =0 and all r satisfying 0<r≤1,4，w(r)≤1/6. Note that in the statement of Lemma 24,the wi's are positive integers in non-decreasing order,all of which are at least 2.Lemma 24 will be proved in the remainder of Section 4. First we use it to prove Lemma 21,which we restate for convenience. 20
for every vertex v ∈ S, at least one of v1, . . . , v∆ is in V \S and hence S is an independent set of H (since each hyperedge ev of H contains at least one vertex which does not belong to S). This completes the proof. 4 Bounding the decay rate for large ∆ This section is devoted to proving Lemma 21. Let k and ∆ be two integers such that k ≥ ∆ and ∆ ≥ 200. We start by setting up some upper bounds on the function κ d,w ∗ (r) which is defined in (12) using notation from Definition 19. Consider the following definitions, which apply to suitable vectors w. ρ w,i(r) := α −lwi δ si+i−d+b2 ∑wi j=1 δ −(j−1)(∆−1) 1 φ(ri,j ) ∂Fd,w ∂ri,j if 1 ≤ i ≤ d − b2, α −lwi δ sd−b2 1 φ(ri,1) ∂Fd,w ∂ri,1 if d − b2 + 1 ≤ i ≤ d. . (24) κ d,w(r) := φ(F d,w(r))δ b2(k−2)∑ d i=1 ρ w,i(r). (25) We first argue that κ d,w ∗ (r) ≤ κ d,w(r). To see this, note that smin(i,d−b2) is si for 1 ≤ i ≤ d−b2 and is sd−b2 for d−b2 + 1 ≤ i ≤ d. Also, b ′ k ≤ d−b2, so max(0, b′ k −i) ≤ d−b2 −i and if i ≥ d−b2 + 1 then max(0, b′ k −i) = 0. Finally, (j −1)(∆ −1)1i≤d−b2 is equal to (j −1)(∆ −1) when 1 ≤ i ≤ d − b2 and to 0 when d − b2 + 1 ≤ i. Recall from Definition 13 that α = 1 − 10−4 . For brevity, we will denote F d,w(r) by F(r). Finally, we define the constant δ (which depends on ∆). Definition 23. Let c = 0.7. Given ∆, define δ by δ ∆ = c. In order to bound κ d,w(r), an important special case is when b2 = 0. Indeed, as we will see soon, handling this special case implies an upper bound of κ d,w(r) for the general case. Define the following quantity for suitable vectors w. κb d,w(r) := 1 ψ − F(r) χ ∑ d i=1 δ si+i−d−(wi−1)(∆−1)α −lwi ∏wi j=1 ri,j 1+ri,j 1 − ∏wi j=1 ri,j 1+ri,j ∑wi j=1 ψ − r χ i,j 1 + ri,j . (26) The next lemma gives an upper bound on the quantity κb d,w(r). Lemma 24. Let k and ∆ be two integers such that k ≥ ∆ and ∆ ≥ 200. Let d be a positive integer such that d ≤ ∆ − 1. Let w = w1, . . . , wd be a suitable vector with b2 = 0. Then, for all r satisfying 0 < r ≤ 1, κb d,w(r) ≤ 1. In the case d = ∆ for w = w1, . . . , wd, a suitable vector with b2 = 0 and all r satisfying 0 < r ≤ 1, κb d,w(r) ≤ 1/δ. Note that in the statement of Lemma 24, the wi ’s are positive integers in non-decreasing order, all of which are at least 2. Lemma 24 will be proved in the remainder of Section 4. First we use it to prove Lemma 21, which we restate for convenience. 20