Abstract
This article is concerned with self-avoiding walks (SAW) on \(\mathbb {Z}^{d}\) that are subject to a self-attraction. The attraction, which rewards instances of adjacent parallel edges, introduces difficulties that are not present in ordinary SAW. Ueltschi has shown how to overcome these difficulties for sufficiently regular infinite-range step distributions and weak self-attractions (Ueltschi in Probab Theory Relat Fields 124(2):189–203, 2002). This article considers the case of bounded step distributions. For weak self-attractions we show that the connective constant exists, and, in \(d\ge 5\), carry out a lace expansion analysis to prove the mean-field behaviour of the critical two-point function, hereby addressing a problem posed by den Hollander (Random Polymers, vol. 1974. Springer-Verlag, Berlin, 2009).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
1.1 Model definition
Let \(\mathbb {Z}^{d}\) denote the d-dimensional integer lattice with nearest-neighbour edges, and assume \(d\ge 2\). Let \(\mathbb {P}\) be the law of a random walk on the vertices of \(\mathbb {Z}^{d}\) with i.i.d. increments distributed according to a step distribution D. Letting \(\{\pm e_{i}\}_{i=1}^{d}\) denote the standard generators of \(\mathbb {Z}^{d}\), a plaquette is a collection of vertices of the form \(\{x,x+u,x+v,x+u+v\}\) where \(u\notin \{\pm v\}\) and u and v are in \(\{\pm e_{i}\}_{i=1}^{d}\). Two edges \(\{x_{1},y_{1}\}\) and \(\{x_{2},y_{2}\}\) of \(\mathbb {Z}^{d}\) are adjacent if \(\{x_{1},y_{1},x_{2},y_{2}\}\) is a plaquette.
A walk is a sequence of vertices in \(\mathbb {Z}^{d}\), and the edges of a walk \(\omega \) are the pairs \(\{\omega _{i},\omega _{i+1}\}\) of consecutive vertices. Note that, for general increment distributions D, the edges of a walk in the support of \(\mathbb {P}\) are not necessarily edges of \(\mathbb {Z}^{d}\). Define \(\mathsf {adj}(\omega )\) to be the collection of pairs of edges of \(\omega \) that are adjacent edges of \(\mathbb {Z}^{d}\), and let \(\left| \mathsf {adj}(\omega )\right| \) be the cardinality of this set. See Fig. 1.
Let \(\mathbb {P}_{n}\) denote the law induced by \(\mathbb {P}\) on n-step walks that begin at the origin \(o\in \mathbb {Z}^{d}\), and recall that a walk is self-avoiding if it does not visit any vertex more than once (see Sect. 3.1 for a more precise definition). The models we are interested in are perturbations \(\mathsf {P}_{n,\kappa }\) of \(\mathbb {P}_{n}\) defined by
where \(\Gamma _{n}\) is the set of n-step self-avoiding walks with initial vertex \(\omega _{0}=o\) and
The symbol \(:=\) indicates equality by definition. The law \(\mathsf {P}_{n,\kappa }\) on n-step walks is called (n-step) attracting self-avoiding walk with attraction strength\(\kappa \), or (n-step) \(\kappa \)-ASAW. When the length of the walk is irrelevant the adjective n-step will be dropped. We think of the right-hand side of (1.1) as defining the \(\kappa \)-ASAW weight of a walk \(\omega \). The probability of a walk is proportional to its weight.
The law \(\mathsf {P}_{n,0}\) defined by (1.1) is the law of n-step self-avoiding walk (SAW) [3]. Physically, self-avoiding walk is a model of a linear polymer in a good solvent. The self-avoidance constraint represents the inability of two molecules in the polymer to occupy the same space. If \(\kappa >0\), walks under the \(\kappa \)-ASAW law are attracted to themselves. Physically, this is a model of a linear polymer in a poor solvent, see [4, Section 6.3] and [2, Chapter 6]. The molecules huddle together to escape exposure to the surrounding solvent.
1.2 Lack of submultiplicativity
Before stating our results, we briefly discuss the central difficulty of the model. Let \(c_{n}(\kappa )\) denote the normalization constant that makes \(\mathsf {P}_{n,\kappa }\) a probability measure, i.e.,
Note that \(c_{n}(\kappa )\) is implicitly also a function of the step distribution D.
The first mathematical fact one learns about self-avoiding walk is that when \(\kappa =0\) the sequence \((c_{n}(\kappa ))_{n\ge 1}\) is submultiplicative, i.e.,
This bound arises because any \((n+m)\)-step self-avoiding walk can be split into an n-step self-avoiding walk and an m-step self-avoiding walk. Simple estimates and Fekete’s lemma [5, Lemma 1.2.1] on submultiplicative sequences imply that \((c_{n}(0))^{1/n}\) converges as \(n\rightarrow \infty \); see [6, Section 1.2].Footnote 1
The basic difficulty in the study of \(\kappa \)-ASAW is that the sequence \((c_{n}(\kappa ))_{n\ge 1}\) is generally not submultiplicative for \(\kappa >0\). To see that submultiplicativity cannot hold in general, consider the nearest-neighbour step distribution \(D(x) = (2d)^{-1}{\mathbb {1}}_{\left\{ \Vert x\Vert _{1}=1\right\} }\). Submultiplicativity of the sequence \(c_{n}(\kappa )\) would imply
which cannot hold for fixed \(n\ge 3\) when \(\kappa \) is sufficiently large, as the left-hand side is a polynomial in \(\kappa \) of degree at least 1.
2 Results
Henceforth it will be assumed that D(x) is invariant under the symmetries of \(\mathbb {Z}^{d}\) (namely, reflections in hyperplanes and rotations by \(\pi /2\) about coordinate axes), and that \(D(e_{1}) :=p_{1}>0\). Thus, \(D(\pm e_{i})=p_{1}\) for both choices of sign and all choices of \(i=1,2,\ldots , d\).
The next two subsections present our main results, Theorem 2.1 and Theorem 2.3, and in Sects. 2.3 and 2.4 we discuss the main ideas of the proofs and briefly describe how our results fit into the literature.
2.1 Connective constants
The limiting value \(\mu (\kappa )\) of \((c_{n}(\kappa ))^{1/n}\), if the limit exists, is called the connective constant with self-attraction\(\kappa \). We will prove that the connective constant of \(\kappa \)-ASAW exists for \(\kappa \) sufficiently small despite not knowing if submultiplicativity holds.
Theorem 2.1
Let \(d\ge 2\). There exists a \(\kappa _{0} = \kappa _{0}(D)>0\) such that for \(0<\kappa <\kappa _{0}\) the limit \(\mu (\kappa ) = \lim _{n\rightarrow \infty }(c_{n}(\kappa ))^{1/n}\) exists.
Note that the dependence of \(\kappa _{0}\) on D implicitly means that \(\kappa _{0}\) may depend on the dimension d. The remainder of this section briefly describes the proof of Theorem 2.1, although we delay a discussion of how the lack of submultiplicativity is overcome to Sect. 2.3. The proof appears in Sect. 4.
An n-step self-avoiding walk \(\omega \) is a bridge if \(\pi _{1}(\omega _{0})<\pi _{1}(\omega _{j})\le \pi _{1}(\omega _{n})\) for all \(j=1,\ldots ,n\), where \(\pi _{1}\) denotes projection onto the first coordinate. A key observation for the proof of Theorem 2.1 is that \(\mathcal {W}_{\kappa }\) is supermultiplicative on bridges when \(\kappa \ge 0\). This implies the connective constant for bridges, \(\mu _{\mathsf {B}}(\kappa )\), exists.
A classical argument due to Hammersley and Welsh shows that the number of n-step self-avoiding bridges is the same, up to sub-exponential corrections, as the number of n-step self-avoiding walks [7]; see also [6, Section 3.1]. An immediate consequence is that \(\mu _{\mathsf {B}}(0)=\mu (0)\). To prove the existence of \(\mu (\kappa )\), we adapt the Hammersley-Welsh argument to \(\kappa >0\); i.e., we prove that the difference in the \(\kappa \)-ASAW weight of n-step bridges and n-step walks is sub-exponential in n.
The Hammersley-Welsh argument involves “unfolding” self-avoiding walks by reflecting segments of the walk through well-chosen hyperplanes. It is during unfolding that the lack of submultiplicativity must be overcome.
2.2 Mean-field behaviour
To formulate Theorem 2.3, our main lace expansion result, we require further assumptions on the step distribution D.
Definition 1
Let \(L>0\). A step distribution D is spread-out with parameter L if it has the form
where \(h:\left[ -1,1\right] ^{d}\rightarrow \left[ 0,\infty \right) \) is a piecewise continuous function such that \(h(0)>0\), 0 is a point of continuity, and
-
(i)
h is invariant under the symmetries of \(\mathbb {Z}^{d}\), and
-
(ii)
\(\int h(x)\,dx =1\).
In what follows when we consider a “spread-out step distribution” we mean the one-parameter family of step distributions obtained by choosing a single function h. Note that \(h(0)>0\) and 0 being a point of continuity for h implies that the denominator in (2.1) is positive and \(D(e_{1})=p_{1}>0\) if L is taken sufficiently large. We will implicitly assume L is at least this large in what follows. The variance of D will be denoted by \(\sigma ^{2}:=\sum _{x\in \mathbb {Z}^{d}}\Vert x\Vert _{2}^{2}D(x)\).
Example 2.2
Consider \(h(x)=2^{-d}\) on \(\left[ -1,1\right] ^{d}\). This leads to D(x) being uniformly distributed on vertices \(x\ne o\) with \(\Vert x\Vert _{\infty }\le L\).
The proof of Theorem 2.1 relies in part on establishing that \(\kappa \)-ASAW is repulsive in an averaged sense; roughly speaking, this means that a walk under the \(\kappa \)-ASAW law is not typically attracted to its earlier trajectory. This idea, which is explained more precisely in Sect. 2.3, also turns out to enable a lace expansion analysis of \(\kappa \)-ASAW at criticality, a notion which we introduce in the next two definitions.
Definition 2
The susceptibility of \(\kappa \)-ASAW is the power series
Definition 3
The critical point\(z_{c}= z_{c}(D,\kappa )\) of \(\kappa \)-ASAW is defined to be
For SAW, submultiplicativity implies that \(z_{c}(0) = \mu (0)^{-1}\). For \(\kappa \) small enough that Theorem 2.1 applies, it remains true that \(z_{c}(\kappa )=\mu (\kappa )^{-1}\) by the Cauchy–Hadamard characterization of the radius of convergence.
Before stating our main result on the behaviour of \(\kappa \)-ASAW at the critical point \(z_{c}(\kappa )\), we require a few more definitions. Precise formulations of the classes of walks involved in these definitions can be found in Sect. 3.1.
The two-point function of \(\kappa \)-ASAW is defined, for \(z\ge 0\) and \(x\in \mathbb {Z}^{d}\), by
Note that the inner sum is restricted to self-avoiding walks that end at x; only n-step walks with positive probability under \(\mathsf {P}_{n,\kappa }\) contribute.
The \(\kappa \)-ASAW two-point function should be compared with the simple random walk two-point function
in which the inner sum is over \(\mathsf {W}_{n}(x)\), the set of all n-step walks with initial vertex \(o\in \mathbb {Z}^{d}\) and terminal vertex \(x\in \mathbb {Z}^{d}\). The term “simple” is used to indicate that the associated law on n-step walks is \(\mathbb {P}_{n}\), although this may not be a nearest-neighbour walk. Let \(\left| \left| \left| x\right| \right| \right| \) denote \(\max \{\Vert x\Vert _{2},1\}\), where \(\Vert \cdot \Vert _{2}\) is the Euclidean norm. Despite the notation, \(\left| \left| \left| \cdot \right| \right| \right| \) is not a norm.
Theorem 2.3
Let \(d\ge 5\). For sufficiently spread-out step distributions, with parameter \(L\ge L_{0}(D)\), there is a \(\kappa _{0}>0\) such that if \(0\le \kappa \le \kappa _{0}\) and \(\alpha >0\) then
where \(\sigma ^{2}\) is the variance of the step distribution D, the constants implicit in the \(O(\cdot )\) notation may depend on \(\kappa \) and \(\alpha \), and \(a_{d} = 2^{-1} \pi ^{-d/2} d \Gamma (\frac{d}{2}-1)\). Here \(\Gamma (\frac{d}{2}-1)\) is the evaluation of Euler’s Gamma function at \(\frac{d}{2}-1\).
Theorem 2.3 shows that the critical two-point function of \(\kappa \)-ASAW has the same asymptotics as the critical (\(z=1)\) two-point function of simple random walk in \(d\ge 5\). In the language of critical exponents, see [4, p.12], this says that \(\eta =0\), i.e., this is a verification that \(\kappa \)-ASAW has mean-field behaviour. We have not attempted to optimize the relation between \(\kappa _{0}\) and L in our proof, as our primary interest is in the existence of \(\kappa _{0}>0\) for finite L.
It is typically difficult to apply the lace expansion to models containing attracting interactions, as these attractions make it difficult to obtain what are known as diagrammatic bounds. We are able to overcome this difficulty as the on average repulsion that \(\kappa \)-ASAW satisfies is compatible with calculating such bounds. This is discussed in more detail in Sect. 2.3. Once the diagrammatic bounds are obtained the remaining part of the lace expansion analysis is well understood and can be adapted from existing arguments [8]. We recall how this can be done in Appendix A. The proof of Theorem 2.3 is carried out in Sect. 6.
2.3 Main idea
The proofs of Theorems 2.1 and 2.3 are essentially independent, but they share a common idea which we explain here.
Let \(\Gamma \) denote the set of all self-avoiding walks, not necessarily starting at the origin o. Writing a walk \(\omega \) as a concatenation \(\omega = \omega ^{1}\circ \omega ^{2}\) of two subwalks determines an interaction conditional on \(\omega ^{1}\), i.e.,
where this formula defines \(H_{\kappa }(\cdot \,;\omega ^{1})\). Explicitly,
where \(\mathsf {adj}(\omega ^{1},\,\omega ^{2})\) is the set of pairs of adjacent edges \(\{f_{1},f_{2}\}\) with \(f_{i}\in \omega ^{i}\), \(i=1,2\).
For SAW, i.e., \(\kappa =0\), the interaction is trivial: \(e^{-H_{0}(\omega )}=e^{-H_{0}(\omega ^{2};\omega ^{1})}=1\). Submultiplicativity therefore follows from (2.6) and the observation that
For \(\kappa >0\) it is not generally true that \(e^{-H_{\kappa }(\eta ;\,\omega ^{1})} \le e^{-H_{\kappa }(\eta )}\). See Fig. 1 and consider splitting the walk into the indicated subwalks.
Equation (2.6) highlights a tension between self-avoidance and self-attraction. Energetic rewards of \((1+\kappa )\) due to the conditional interaction only occur if the walk \(\omega ^{2}\) has edges adjacent to edges in \(\omega ^{1}\). Such an edge in \(\omega ^{2}\) carries an entropic penalty, as the potential configurations of \(\omega ^{2}\) are reduced. Thus there is both an entropic benefit and an energetic penalty to dropping the conditional interaction due to \(\omega ^{1}\) when (2.6) is summed over a suitable class of walks.
More explicitly, if \(\omega ^{2}\) contains an edge \(\{x_{1},y_{1}\}\) adjacent to an edge \(\{x_{2},y_{2}\}\) of \(\omega ^{1}\), then typically there is a self-avoiding modification of \(\omega ^{2}\) that traverses \(\{x_{2},y_{2}\}\) instead of \(\{x_{1},y_{1}\}\). The modified walk will be longer than the original, and will be assigned zero weight by the conditional interaction. However, it has positive \(\kappa \)-ASAW weight. The entropic gain of ignoring \(\omega ^{1}\) can therefore be estimated by considering the possible modifications to \(\omega ^{2}\) and estimating the energetic cost of the modifications. The energetic cost decreases as \(\kappa \) decreases, and for \(\kappa \) sufficiently small we will show that the entropic benefit outweighs the energetic penalty. This idea, which involves a weighted version of the multivalued map principle [9, Section 2.0.1], has been fruitful in obtaining upper bounds on the number of self-avoiding polygons of given length [9].
2.4 Discussion
Ueltschi [1] considered a model of SAWs with an attracting reward for pairs of nearest-neighbour vertices under the assumption that the step distribution D(x) and attraction strength \(\kappa \) satisfy
Note that the condition on D(x) in (2.8) implies the step distribution has infinite range. Given (2.8) it can be shown that the entropic reward of ignoring \(\omega ^{1}\) outweighs the energetic cost. The fact that D(x) has infinite range and is “smooth” allows the use of a length preserving transformation to prove the model is submultiplicative. Using this idea Ueltschi also carries out a lace expansion analysis via the inductive approach of [10]; the length-preserving nature of the transformation is important for the application of the inductive method. Ueltschi’s result was significant for being the first application of the lace expansion to a self-attracting random walk. Self-attracting interactions, which are also called non-repulsive, are typically difficult to handle with lace expansion methods [4, Section 6.3].
The problem of analysing models of self-attracting self-avoiding walks under weaker hypotheses on the step distributions was raised by den Hollander [2, Chapter 4.8(5)], and our work addresses this question when \(d\ge 5\). As described in Sect. 2.3 the main idea is to combine energy-entropy methods with classical techniques for self-avoiding walk.
Beyond our main theorems, an important aspect of this work is that it suggests that energy-entropy methods may be more generally useful in the context of the lace expansion. In particular there is no need to restrict to length-preserving transformations as in [1] (although length-preserving transformations do simplify technical aspects due to [10]). This is significant as energy-entropy methods should be a fairly robust way to overcome a lack of repulsion caused by weak attractions. Roughly speaking, the key step in such an argument is to first subdivide an object, and then to prove the gain in conformational freedom that arises when forgetting one part outweighs the loss of energetic attractions. Our proof implements this strategy for \(\kappa \)-ASAW, and it is plausible it could be implemented for other models, e.g., weakly self-attracting lattice trees in high dimensions via an adaptation of [8, 11].
It is worth noting that energy-entropy arguments are carried out by finding a transformation that estimates the number of new configurations that are available. Finding a transformation is a combinatorial and analytic problem, in contrast to other approaches to overcoming a lack of repulsion via correlation inequalities [4, 12], resummation identities [13], or asymmetry assumptions [14].
We end this section by mentioning two recent related works on self-avoiding random walks subject to self-attraction. Firstly, there has been interesting progress [15] on den Hollander’s problem for weakly self-avoiding walk (WSAW) with a contact self-attraction when \(d=4\). The authors prove Gaussian decay of the critical two-point function when the self-attraction and self-repulsion strengths are sufficiently small by making use of a rigorous renormalization group analysis. The techniques of [15] are wholly different than those of the present paper, and an analysis of self-attracting WSAW when \(d\ge 5\) via lace expansion techniques would be a very interesting complement to the results of [15]. Secondly, in [16] it has been shown that a related model known as prudent self-avoiding walk undergoes a collapse transition in \(d=2\) when the self-attraction is strong enough.
3 Initial definitions, path transformations
3.1 Conventions
By a common abuse of notation \(\mathbb {Z}^{d}\) will denote the d-dimensional hypercubic lattice, i.e., the graph with vertex set \(\mathbb {Z}^{d}\) and edge set \(E(\mathbb {Z}^{d}):=\{\{x,y\} \mid \Vert x-y\Vert _{1}=1\}\). Recall that the standard generators of \(\mathbb {Z}^{d}\) will be denoted \(e_{1},\ldots , e_{d}\). \(\left| A\right| \) will denote the cardinality of a finite set A, and \(A\sqcup B\) will denote the union of disjoint sets A and B.
For \(n\in \mathbb {N}:=\{0,1,2,\ldots \}\), an n-step walk is a sequence \((\omega _{i})_{i=0}^{n}\), where \(\omega _{i}\in \mathbb {Z}^{d}\) for \(0\le i\le n\) and \(\omega _{i}\ne \omega _{i-1}\), \(1\le i\le n\). For such a walk let \(\left| \omega \right| :=n\), and for \(0\le i<j\le \left| \omega \right| \) we write \(\omega _{\left[ i,j\right] }\) to denote the walk \((\omega _{i}, \omega _{i+1}, \ldots , \omega _{j})\). Let \(\mathsf {W}_{n}(x,y)\) be the set of n-step walks with \(\omega _{0}=x\) and \(\omega _{n}=y\). We omit the first argument if \(x=o\), the origin of \(\mathbb {Z}^{d}\), and let \(\mathsf {W}(x,y) :=\bigsqcup _{n\ge 0}\mathsf {W}_{n}(x,y)\). We also let \(\mathsf {W}_{n}\) denote the set of all n-step walks, with no constraints on the initial or final vertices.
A walk is self-avoiding if \(\omega _{i}\ne \omega _{j}\) for \(i\ne j\), and is a self-avoiding polygon if \(\left| \omega \right| >2\), \(\omega _{i}\ne \omega _{j}\) for \(0\le i<j<\left| \omega \right| \), and \(\omega _{0}=\omega _{\left| \omega \right| }\). Note that polygons are rooted and oriented, which is a somewhat non-standard definition. Let \(\Gamma _{n}(x,y)\) denote the set of n-step self-avoiding walks from x to y and \(\tilde{\Gamma }_{n}(x)\) denote the set of n-step self-avoiding polygons with initial vertex x. For self-avoiding walks let \(\Gamma _{n}(x) :=\Gamma _{n}(o,x)\), and again we will omit the subscript n to indicate a union over n. \(\Gamma \) and \(\tilde{\Gamma }\) denote the sets of all self-avoiding walks and polygons, respectively, with no restrictions on the initial vertex.
Let \(\mathsf {adj}(A,B)\) denote the set of plaquettes spanned by pairs of adjacent edges \(e\in A\), \(f\in B\) for subsets \(A,B\subset E(\mathbb {Z}^{d})\), and let \(\mathsf {adj}(A) :=\mathsf {adj}(A,A)\). Let \(E(\omega ) :=\{ \{\omega _{i},\omega _{i+1}\}\}_{i=0}^{\left| \omega \right| -1}\) be the set of edges traversed by a walk \(\omega \). By a slight abuse of notation we will write \(\mathsf {adj}(\omega ,\eta )\) in place of \(\mathsf {adj}(E(\omega ),E(\eta ))\), and \(\mathsf {adj}(\omega ):=\mathsf {adj}(\omega ,\omega )\).
3.2 Transformations by symmetries of \(\mathbb {Z}^{d}\); basic path operations
For \(x\in \mathbb {Z}^{d}\), let \(\mathcal {T}_{x}\) denote the operator of translation by x, i.e., \(\mathcal {T}_{x}f(y) = f(y-x)\) for f a function on \(\mathbb {Z}^{d}\). Translations will also act on subsets or collections of subsets of \(\mathbb {Z}^{d}\) by identifying sets with indicator functions. For example, if \(\omega \in \mathsf {W}_{n}\), \(\mathcal {T}_{x}\,\omega \) is the n-step walk \((\omega _{0}+x, \omega _{1}+x, \ldots , \omega _{n}+x)\).
The projection operator \(\pi _{i}:\mathbb {Z}^{d}\rightarrow \mathbb {Z}\) maps \(x = (x_{1}, \ldots , x_{d})\) to \(x_{i}\). To lighten notation, let \(\pi _{i}^{-1}(x) = \pi _{i}^{-1}(\pi _{i}(x))\) denote the hyperplane passing through x with normal \(e_{i}\). The reflection operator \(\mathcal {R}_{i}:\mathbb {Z}^{d}\rightarrow \mathbb {Z}^{d}\) reflects any vertex in the coordinate hyperplane \(\pi _{i}^{-1}(o)\).
If \(\omega ^{1}\in \mathsf {W}_{m}\) and \(\omega ^{2}\in \mathsf {W}_{n}\) their concatenation\(\eta = \omega ^{1}\circ \omega ^{2}\) is the \((n+m)\)-step walk with \(\eta _{i}=\omega ^{1}_{i}\) for \(0\le i\le m\), and \(\eta _{m+i} = \mathcal {T}_{(\omega ^{1}_{m}-\omega ^{2}_{0})}\, \omega ^{2}_{i}\) for \(0\le i\le n\). This translation moves the initial vertex of \(\omega ^{2}\) to the terminal vertex of \(\omega ^{1}\), so the concatenated walk continues from where \(\omega ^{1}\) ends.
3.3 Flips
Let \(\omega \) be a walk and P be a plaquette such that there is a unique i such that \(\omega _{j}\in P\) iff \(j\in \{i,i+1\}\). We will call such a plaquette Pflippable. This condition implies that \(\omega \) has exactly one edge in the plaquette P, and no other vertices in P. Otherwise P is not flippable. Since flippability is defined in terms of \(\omega \) we will write, for example, flippable for\(\omega \) to indicate this dependence.
Suppose P is a flippable plaquette for \(\omega \), and that \((\omega _{i},\omega _{i+1})\) is the unique edge of \(\omega \) in P. The flip of\(\omega \)atP, denoted \(\mathcal {F}_{P}(\omega )\), is the walk \(\omega ^{\prime }\) that replaces \((\omega _{i},\omega _{i+1})\) with the traversal of P along the three edges distinct from \(\{\omega _{i},\omega _{i+1}\}\). See Fig. 2. If P is not flippable, define \(\mathcal {F}_{P}(\omega ) = \omega \). Two plaquettes \(P_{1}\) and \(P_{2}\) are said to be disjoint if they have no vertices in common. Sets of disjoint flippable plaquettes are what will be entropically important in what follows. The next three lemmas establish useful properties of \(\mathcal {F}_{P}\).
Lemma 3.1
For any plaquette P and vertices \(x,y\in \mathbb {Z}^{d}\), \(\mathcal {F}_{P}:\mathsf {W}(x,y)\rightarrow \mathsf {W}(x,y)\), \(\mathcal {F}_{P}:\Gamma (x,y)\rightarrow \Gamma (x,y)\), and \(\mathcal {F}_{P}\) is invertible. If \(P'\) is disjoint from P, then \(\mathcal {F}_{P}\circ \mathcal {F}_{P'}=\mathcal {F}_{P'}\circ \mathcal {F}_{P}\).
Proof
To prove \(\mathcal {F}_{P}:\mathsf {W}(x,y)\rightarrow \mathsf {W}(x,y)\) it suffices to prove that \(\mathcal {F}_{P}\) does not change the endpoints of a walk. This is immediate as the first and last vertices of \(\mathcal {F}_{P}(\omega )\) in P are the same as the first and last vertices of \(\omega \) in P.
If \(\omega \in \Gamma (x,y)\) and P is not flippable for \(\omega \), then \(\mathcal {F}_{P}(\omega )=\omega \), so the image is in \(\Gamma (x,y)\). If P is flippable, then \(\omega \) contains one edge of P and no other vertices; since \(\mathcal {F}_{P}\) only modifies \(\omega \) on P the result is self-avoiding.
Invertibility of \(\mathcal {F}_{P}\) is clear, as if P is not flippable for \(\omega \) then \(\mathcal {F}_{P}\) is the identity, while if P is flippable then \(\omega \) can be recovered from \(\mathcal {F}_{P}(\omega )\) by replacing the traversal of three consecutive edges of P in \(\mathcal {F}_{P}(\omega )\) by the traversal of the single unoccupied edge of P. Lastly, commutativity holds as flips at disjoint plaquettes modify the walk on disjoint sets of edges. \(\square \)
Given a disjoint set of plaquettes \(B=\{P_{1},\ldots , P_{k}\}\), define \(\mathcal {F}_{B}(\omega ) :=\mathcal {F}_{P_{1}}\circ \ldots \circ \mathcal {F}_{P_{k}}(\omega )\); the commutativity of flips at disjoint plaquettes implies the definition of \(\mathcal {F}_{B}\) is unambiguous.
Lemma 3.2
Let \(\eta \circ \omega \in \Gamma \) and let \(B\subset \mathsf {adj}(\eta ,\omega )\) be a disjoint set of plaquettes that are flippable for \(\omega \). Then \(\omega \) is uniquely determined by \(\mathcal {F}_{B}(\omega )\) and \(\eta \).
Proof
Since the plaquettes in B are disjoint, we can consider them separately. For each \(P\in B\), there is at least one edge of P in \({\tilde{\omega }} = \mathcal {F}_{P}(\omega )\) that is also in \(\eta \). Suppose there is one edge \(({\tilde{\omega }}_{i},{\tilde{\omega }}_{i+1})\). Then P is the plaquette \(\{{\tilde{\omega }}_{i-1}, {\tilde{\omega }}_{i}, {\tilde{\omega }}_{i+1}, {\tilde{\omega }}_{i+2}\}\). If there are two edges of \({\tilde{\omega }}\) in \(\eta \) then P is the plaquette spanned by the two edges, and three or four edges being in \(\eta \) contradicts \(\eta \circ \omega \in \Gamma \).
Thus, given \(\eta \) and \({\tilde{\omega }}\), we can determine B. By Lemma 3.1\(\mathcal {F}_{B}\) is invertible, so \(\omega \) is uniquely determined. \(\square \)
Suppose a self-avoiding walk \(\eta \) is composed of two subwalks \(\omega ^{1}\) and \(\omega ^{2}\), i.e., \(\eta = \omega ^{1}\circ \omega ^{2}\). It will be convenient to abuse notation and write \(\mathsf {adj}(\omega ^{1},\omega ^{2})\) in place of \(\mathsf {adj}(\omega ^{1},\mathcal {T}_{x}\omega ^{2})\), where \(\mathcal {T}_{x}\) is the translation that takes the initial vertex of \(\omega ^{2}\) to the final vertex of \(\omega ^{1}\). As it will be contextually clear we are discussing pairs of adjacent edges between \(\omega ^{1}\) and \(\omega ^{2}\), this should not cause any confusion.
The next lemma says most plaquettes in \(\mathsf {adj}(\omega ^{1},\omega ^{2})\) are flippable for \(\omega ^{2}\); to quantify this we define
Lemma 3.3
If \(\omega ^{1}\circ \omega ^{2}\in \Gamma \), there are at most \(k_{0}\) plaquettes in \(\mathsf {adj}(\omega ^{1},\omega ^{2})\) that are not flippable for \(\omega ^{2}\). If \(\omega ^{1}\circ \omega ^{2}\in \tilde{\Gamma }\), there are at most \(2k_{0}\) plaquettes in \(\mathsf {adj}(\omega ^{1},\omega ^{2})\) that are not flippable for \(\omega ^{2}\).
Proof
Without loss of generality, assume that \(\omega ^{2}_{0}\) is the endpoint of \(\omega ^{1}\), and call the vertices in common to \(\omega ^{2}\) and \(\omega ^{1}\)points of concatenation. The proof characterises when \(P\in \mathsf {adj}(\omega ^{1},\omega ^{2})\) is not flippable for \(\omega ^{2}\) case by case, depending on how many edges of P are contained in \(\omega ^{1}\circ \omega ^{2}\). By the definition of \(P\in \mathsf {adj}(\omega ^{1},\omega ^{2})\) there are at least two such edges.
First, note that a self-avoiding walk or polygon containing four edges in a single plaquette is a four step self-avoiding polygon. The claim is true in this case, as there are exactly two adjacent pairs of edges. Henceforth we may assume there are no plaquettes containing four edges.
Suppose that \(\omega ^{1}\) and \(\omega ^{2}\) each contain exactly one edge of P. If P does not contain a point of concatenation, then P is flippable for \(\omega ^{2}\) since the two vertices of P in \(\omega ^{1}\) are not in \(\omega ^{2}\). See Fig. 3a. If P contains a point of concatenation it may or may not be flippable for \(\omega ^{2}\).
Suppose that \(\omega ^{1}\circ \omega ^{2}\) contains three edges of P. Note that the three edges must occur sequentially in \(\omega ^{1}\circ \omega ^{2}\) since this walk is self-avoiding or a self-avoiding polygon, and hence P must contain a point of concatenation if it is to be in \(\mathsf {adj}(\omega ^{1},\omega ^{2})\). If two edges belong to \(\omega ^{1}\), then P is flippable for \(\omega ^{2}\). Otherwise, P is not flippable for \(\omega ^{2}\). See Fig. 3b.
Thus \(P\in \mathsf {adj}(\omega ^{1},\omega ^{2})\) and P not being flippable implies there is a point of concatenation in P. As there are at most two points of concatenation, this verifies the claim, as each vertex of \(\mathbb {Z}^{d}\) is contained in \(k_{0}\) plaquettes. \(\square \)
The cost \(p_{1}^2= \frac{\mathbb {P}_{n+2}(\omega ^{\prime })}{\mathbb {P}_{n}(\omega )}\) is the additional cost of the modified walk \(\omega ^{\prime }\) according to the a priori measure \(\mathbb {P}\). Recall the definition of \(\mathcal {W}_{\kappa }\) in (1.2). The next lemma is our basic estimate for the energetic penalty of a flip. For future reference, define
Lemma 3.4
Let \(\omega \) be a self-avoiding walk and P a flippable plaquette. Let \(\omega ^{\prime }=\mathcal {F}_{P}(\omega )\). Then
Proof
The factor of \(p_{1}^2\) comes from comparing the a priori measures in the definition of \(\mathcal {W}_{\kappa }\). What remains is to bound the difference \(\left| \mathsf {adj}(\omega )\right| - \left| \mathsf {adj}(\omega ')\right| \).
The flip creates at least one pair of adjacent edges in \(\omega '\) that was not present in \(\omega \), namely the pair of adjacent edges of \(\omega '\) in P. There are \(2d-2\) edges that are potentially adjacent to the unique edge of \(\omega \) in P, and the hypothesis of P being flippable for \(\omega \) implies at least one of these edges is not in \(\omega \). Thus at most \(2d-3\) adjacent pairs of edges in \(\omega \) are not present in \(\omega '\). This proves (3.3). \(\square \)
In what follows it will be necessary to flip many plaquettes. Lemma 3.1 guarantees the result will be self-avoiding if the flipped plaquettes are disjoint. The next lemma guarantees that every collection of plaquettes has a positive density subset of disjoint plaquettes. Define \(\alpha = \alpha (d)\) by
Lemma 3.5
Given a finite set A of plaquettes in \(\mathbb {Z}^{d}\), there exists a subset of pairwise disjoint plaquettes of A of size \(\lceil \alpha \left| A\right| \rceil \).
Proof
The constant \(\alpha \) is \((1+R)^{-1}\), where R is the number of plaquettes \(P'\ne P\) sharing a vertex with P. The remainder of the proof verifies the value of R claimed in (3.4) by performing inclusion-exclusion on the number of vertices \(P'\ne P\) shares with P; note that this number is at most two.
Any vertex x is contained in exactly \(4{d\atopwithdelims ()2}\) plaquettes. To see this, note these plaquettes are in bijection with sets \(\{(u_{i},\sigma _{i})\}_{i=1,2}\), where \(u_{1}\ne u_{2}\) are distinct generators of \(\mathbb {Z}^{d}\) and \(\sigma _{i}\in \{\pm 1\}\): these sets identify the unique plaquette containing \(x, x+ \sigma _{1}u_{1}, x+\sigma _{2}u_{2}\). Since every edge belongs to exactly \(2(d-1)\) plaquettes, the total number of plaquettes sharing a vertex with a plaquette P is therefore
where the factors of \(-1\) correct for the presence of P in our counts. \(\square \)
4 Existence of the connective constant: proof of Theorem 2.1
4.1 Half-space walks and bridges
We begin by recalling the basic definitions used in the Hammersley-Welsh argument.
Definition 4
The set \(\mathsf {B}_{n}\) of n-step bridges is the subset of \(\omega \in \Gamma _{n}\) such that
The set \(\mathsf {H}_{n}\) of n-step half-space walks is the set of \(\omega \in \Gamma _{n}\) such that
Let \(\mathsf {H}:=\sqcup _{n\ge 0}\mathsf {H}_{n}\) and \(\mathsf {B}:=\sqcup _{n\ge 0}\mathsf {B}_{n}\). The masses\(h_{n}(\kappa )\) of n-step half-space walks and \(b_{n}(\kappa )\) of half-space bridges are defined by
Note that the inclusions \(\mathsf {B}_{n}\subset \mathsf {H}_{n}\subset \Gamma _{n}\) imply that \(b_{n}(\kappa )\le h_{n}(\kappa )\le c_{n}(\kappa )\).
While self-attraction on adjacent edges ruins the submultiplicativity of self-avoiding walks, it enhances the supermultiplicativity of bridges.
Proposition 4.1
Let \(\kappa \ge 0\). The limit \(\mu _{\mathsf {B}}(\kappa ) = \lim _{n\rightarrow \infty } (b_{n}(\kappa ))^{1/n}\) exists and is equal to \(\sup _{n\ge 1} \big ( b_{n}(\kappa ) \big )^{1/n}\).
Proof
The definition of a bridge implies that the concatenation \(\omega ^{1}\circ \omega ^{2}\) of two bridges \(\omega ^{1}\) and \(\omega ^{2}\) is a bridge. Each pair of adjacent edges in \(\omega ^{i}\) remains adjacent in \(\omega ^{1}\circ \omega ^{2}\). Any other pair of adjacent edges in the concatenation receives weight \(1+\kappa \ge 1\), so
for all choices of \(n_{1},n_{2}\in \mathbb {N}\). The left-hand side is \(b_{n_{1}}(\kappa )b_{n_{2}}(\kappa )\). Ignoring the indicator on the right-hand side gives an upper bound \(b_{n_{1}+n_{2}}(\kappa )\). Thus \(b_{n}(\kappa )\) is supermultiplicative, and the proposition follows by Fekete’s lemma. \(\square \)
4.2 Unfolding I. Classical unfolding
This section recalls how half-space walks can be unfolded into a concatenation of bridges. We do this because a multivalued extension of this procedure will be introduced in the next section. We omit the proofs of the various facts that we recall; for details see [6, Section 3.1].
Definition 5
Let \(\omega \in \mathsf {H}\). The (first) bridge point\(\tau (\omega )\) of \(\omega \) is the maximal index i satisfying \(\pi _{1}(\omega _{i}) = \max _{j}\pi _{1}(\omega _{j})\).
Definition 6
The span of a self-avoiding walk is
Note that if \(\omega \) is an n-step bridge then \(\mathrm {span}(\omega )=\pi _{1}(\omega _{n})\).
Given a half-space walk \(\omega \in \mathsf {H}_{n}\), let \(x:=-\omega _{\tau (\omega )}\) and define the initial bridge\(\omega ^{b} :=\omega _{\left[ 0,\tau (\omega )\right] }\) and the remainder\(\omega ^{h} :=\mathcal {T}_{x}\,\omega _{\left[ \tau (\omega ),n\right] }\). We will write \(\omega =(\omega ^{b},\omega ^{h})\) in what follows to indicate this decomposition into an initial bridge and a remainder. The following properties of the decomposition are important.
-
(i)
\(\omega = \omega ^{b}\circ \omega ^{h}\),
-
(ii)
\(\mathcal {R}_{1}(\omega ^{h})\) is a half-space walk,
-
(iii)
\(\mathrm {span}(\omega ^{b}) = \mathrm {span}(\omega )\), and
-
(iv)
\(\mathrm {span}(\mathcal {R}_{1}(\omega ^{h}))<\mathrm {span}(\omega ^{b})\), as \(\omega \) never revisits the coordinate hyperplane \(\pi _{1}^{-1}(o)\) after \(\omega _{0}\).
Definition 7
The classical unfolding map\(\Psi :\mathsf {H}\rightarrow \mathsf {B}\) is recursively defined as follows. \(\Psi \) is the identity map on \(\mathsf {B}\). Otherwise, if \(\omega \in \mathsf {H}{\setminus }\mathsf {B}\), let \(\omega = (\omega ^{b},\omega ^{h})\) and define \(\Psi (\omega ) = \omega ^{b}\circ \Psi (\mathcal {R}_{1}(\omega ^{h}))\).
In words, \(\Psi \) reflects the remainder \(\omega ^{h}\) of the walk \(\omega \) through \(\pi _{1}^{-1}(\omega _{\tau (\omega )})\), the affine hyperplane with normal \(e_{1}\) that contains the endpoint \(\omega _{\tau (\omega )}\) of \(\omega ^{b}\). Since the reflection of \(\omega ^{h}\) is itself a half-space walk, this procedure can be iterated until the first bridge point of the newest half-space walk is also the endpoint of the walk. The recursion terminates at some depth \(r=r(\omega )\) as the spans of the half-space walks produced are strictly decreasing. See Figs. 4 and 5 for one step of this procedure (the meaning of the shaded plaquettes will be explained in the next section).
Thus, \(\Psi \) produces a sequence of bridges \(\omega ^{b_{i}}\), \(i=1,\ldots , r\), and \(\Psi (\omega )=\omega ^{b_{1}}\circ \cdots \circ \omega ^{b_{r}}\). This sequence of bridges is called the classical bridge decomposition of \(\omega \). In what follows, the bridges in the classical bridge decomposition will always be denoted by \(\{\omega ^{b_{i}}\}_{i=1}^{r}\). Let us record some properties of this decomposition.
Proposition 4.2
-
(i)
\(\mathrm {span}(\Psi (\omega ))=\sum _{i=1}^{r}\mathrm {span}(\omega ^{b_{i}})\),
-
(ii)
the sequence \((\mathrm {span}(\omega ^{b_{i}}))_{i=1}^{r}\) of spans is strictly decreasing in i, and
-
(iii)
given \(\Psi (\omega )\) and \(\{\mathrm {span}(\omega ^{b_{i}})\}_{i=1}^{r}\), \(\omega \) is uniquely determined.
Again we will not prove these claims, but let us remark that the third property holds as knowing the lengths of the spans indicates the locations at which to fold the bridge \(\Psi (\omega )\) in order to undo the unfolding procedure.
4.3 Unfolding II. Multivalued unfolding
This section describes a multivalued extension of the classical unfolding map. Roughly speaking, this multivalued extension quantifies an entropic gain in unfolding a half-space walk \(\omega \) into bridges. The gain arises because the unfolded walk may have fewer adjacent edges than the original walk \(\omega \).
Definition 8
The marked unfolding map\({\bar{\Phi }}\) is recursively defined on \(\mathsf {H}\) by
Let \(r:=r(\omega )\) denote the number of bridges generated by this recursion. The image of \({\bar{\Phi }}(\omega )\) will be denoted \(((\omega ^{b_{i}},\mathsf {adj}_{i}))_{i=1}^{r}\), where \(\mathsf {adj}_{r}:=\emptyset \) and for \(1\le i<r\) we have used \(\mathsf {adj}_{i}\) as shorthand for the set of plaquettes defined by (4.6) in the ith step of the recursion.
The marked unfolding map is an extension of \(\Psi \). It records the plaquettes at which \(\omega ^{b_{i}}\) is flippable with respect to the remainder of the half-space walk with initial bridge \(\omega ^{b_{i}}\). Denote the set of discovered flippable plaquettes by \(\mathsf {adj}_{{\bar{\Phi }}}(\omega )\), i.e.,
where \(\mathcal {T}_{i}\) is the translation that translates the bridge \(\omega ^{b_{i}}\) to its location in the bridge \(\Psi (\omega )\).
For \(k\in \mathbb {N}\), let \(\mathsf {H}_{n}^{k}\subset \mathsf {H}_{n}\) be the set of n-step half-space walks with \(\left| \mathsf {adj}_{{\bar{\Phi }}}(\omega )\right| =k\). To define the multivalued extension of \(\Psi \) on \(\mathsf {H}_{n}^{k}\), we will make use of the following facts. First, Lemma 3.5 implies there exists a subset \(\mathsf {adj}^{\star }_{{\bar{\Phi }}}(\omega ) \subset \mathsf {adj}_{{\bar{\Phi }}}(\omega )\) of size \(\lceil \alpha k\rceil \) such that the plaquettes in \(\mathsf {adj}^{\star }_{{\bar{\Phi }}}\) are pairwise disjoint. In what follows we will assume the set \(\mathsf {adj}^{\star }_{{\bar{\Phi }}}\) has been chosen according to some arbitrary (but definite) procedure. Second, Lemma 3.1 implies that if B is a finite collection of pairwise vertex-disjoint plaquettes and \(x\in \mathbb {Z}^{d}\), then \(\mathcal {F}_{B} = \prod _{P\in B}\mathcal {F}_{P}\) is an unambiguously defined map from \(\Gamma (x)\) to \(\Gamma (x)\).
Definition 9
Let \(0<\delta <\frac{1}{2}\), \(n\in \mathbb {N}\), and \(0\le k\le n\). The multivalued unfolding map\(\Phi :\mathsf {H}^{k}_{n} \rightarrow 2^{\mathsf {B}_{n+2\lceil \alpha \delta k\rceil }}\) is defined by
where \({A\atopwithdelims ()k}\) denotes the k-element subsets of a set A.
The next lemma gives the basic properties of \(\Phi \); in particular it verifies the stated codomain in the previous definition. To lighten the notation, define
Lemma 4.3
Let \(\omega \in \mathsf {H}^{k}_{n}\). Then
-
(i)
Every \(P\in \mathsf {adj}_{{\bar{\Phi }}}(\omega )\) is flippable for \(\Psi (\omega )\).
-
(ii)
Each walk \(\omega ^{\prime }\in \Phi (\omega )\) is a bridge in \(\mathsf {B}_{n+2\delta _{k}}\).
-
(iii)
The half-space walk \(\omega \) can be reconstructed from any \(\omega ^{\prime }\in \Phi (\omega )\) given the spans \(\mathrm {span}(\omega ^{b_{i}})\).
Proof
Recall \(\omega = \omega ^{b_{1}}\circ \omega ^{h}\). We begin by noting some properties of the plaquettes in \(\mathsf {adj}(\omega ^{b_{1}},\omega ^{h})\). Since \(\omega \) is a half-space walk, no plaquette in \(\mathsf {adj}(\omega ^{b_{1}},\omega ^{h})\) contains vertices in the half-space \(\pi _{1}^{-1}(\left( -\infty ,0\right] )\). Similarly, no plaquette contains vertices in the half-space \(\pi _{1}^{-1}(\left[ \mathrm {span}(\omega ^{b_{1}})+1,\infty \right) )\), as \(\omega ^{h}\) is contained in \(\pi _{1}^{-1}(\left[ 1,\mathrm {span}(\omega ^{b_{1}})\right] )\).
We first prove (i). A moment of thought shows that each plaquette in \(B\subset \mathsf {adj}_{1}(\omega ^{b_{1}},\omega ^{h})\subset \mathsf {adj}^{\star }_{{\bar{\Phi }}}(\omega )\) is flippable for \(\omega ^{b_{1}}\circ \mathcal {R}_{1}(\omega ^{h})\). Iterating this argument for each bridge in the bridge decomposition of \(\omega \) implies each plaquette in \(\mathsf {adj}_{{\bar{\Phi }}}(\omega )\) is flippable for \(\Psi (\omega )\).
We next prove (ii). The preceding shows each \(\omega '\in \Phi (\omega )\) is given by \(\omega '=\mathcal {F}_{B}(\omega ) = \mathcal {F}_{B}(\omega ^{b_{1}})\circ \cdots \circ \mathcal {F}_{B}(\omega ^{b_{r}})\) for \(B\subset \mathsf {adj}_{{\bar{\Phi }}}^{\star }(\omega )\). This is because each plaquette in B contains exactly one edge of \(\Psi (\omega )\), and this edge is located in exactly one subwalk. By Lemma 3.1 and the first paragraph of the proof, each \(\omega ^{j} = \mathcal {F}_{B}(\omega ^{b_{j}})\) is a bridge with span \(\mathrm {span}(\omega ^{b_{j}})\) for \(j=1,\ldots , r\). As a concatenation of bridges is a bridge and each flip adds exactly two edges, this completes the proof, as each \(\omega '\) results from applying \(\mathcal {F}_{B}\) with \(\left| B\right| =\delta _{k}\).
Lastly we prove (iii). By construction, the last bridge \(\omega ^{b_{r}}\) in the classical bridge decomposition has no flips applied to it in the formation of \(\omega ^{r}\). Given \(\mathrm {span}(\omega ^{j})=\mathrm {span}(\omega ^{b_{j}})\) for each j, \(\omega ^{r}=\omega ^{b_{r}}\) is determined. Hence, by Lemma 3.2, \(\omega ^{b_{r-1}}\) can be reconstructed. Iterating this procedure reconstructs \(\omega \) from \(\omega '\), establishing (iii). \(\square \)
Having established the basic properties of the multivalued unfolding map, we turn to estimating the weight of n-step half-space walks in terms of the weights of bridges. The next lemma gives the basic relation between these objects.
For \(n\in \mathbb {N}\), let P(n) denote the number of partitions of n into distinct natural numbers. Let \(\mathsf {B}_{n}(\ell )\) denote the set of n-step bridges \(\omega \) with \(\mathrm {span}(\omega )\le \ell \), and recall the definition of \(\mathrm {flip}_{\kappa }\) from (3.2).
Proposition 4.4
Consider SAW on \(\mathbb {Z}^{d}\). For \(n,k\in \mathbb {N}\) and \(0\le k\le n\),
Proof
We begin by comparing the weight of \(\omega \in \mathsf {H}_{n}^{k}\) to the weight of a generic \(\omega '\in \Phi (\omega )\). Recall that \(k_{0}=2d(d-1)\), and that \(r=r(\omega )\) is the number of bridges created by the unfolding map.
-
(i)
At each unfolding, there are at most \(k_{0}\) plaquettes that are not flippable for \(\omega ^{b}\) in \(\mathsf {adj}(\omega ^{b},\omega ^{h})\) by Lemma 3.3. Hence,
$$\begin{aligned} \mathcal {W}_{\kappa }(\omega )\le (1+\kappa )^{k+rk_{0}}\mathcal {W}_{\kappa }(\omega ^{b_{1}}\circ \cdots \circ \omega ^{b_{r}}), \end{aligned}$$as there are r unfolding steps.
-
(ii)
As \(\omega '=\mathcal {F}_{B}(\omega ^{b_{1}}\circ \cdots \circ \omega ^{b_{r}})\) and \(\left| B\right| =\delta _{k}\), applying Lemma 3.4\(\delta _{k}\) times implies
$$\begin{aligned} \mathcal {W}_{\kappa }(\omega ^{b_{1}}\circ \cdots \circ \omega ^{b_{r}}) \le \mathrm {flip}_{\kappa }^{\delta _{k}} \mathcal {W}_{\kappa }(\omega '). \end{aligned}$$
This implies
Next we apply the multivalued map principle. Let \(\Phi (H_{n}^{k})=\cup _{\omega \in H_{n}^{k}}\Phi (\omega )\).
where the inequality is by (4.10). To make the inner sum uniform in \(\omega \), we use Proposition 4.2. The spans of the bridges in the bridge decomposition of \(\omega \) are distinct positive integers summing to \(\mathrm {span}(\Psi (\omega ))\le n\). This implies that \(r(\omega )\) is at most \(\frac{3}{2}\sqrt{n}\), as the sum of the first \(\frac{3}{2}\sqrt{n}\) positive integers exceeds n. Hence
Next we estimate \(\left| \Phi (\omega )\right| \) and \(\left| \Phi ^{-1}(\omega ')\right| \).
-
(i)
Lemma 4.3 implies that
$$\begin{aligned} \left| \Phi (\omega )\right| = {\alpha _{k}\atopwithdelims ()\delta _{k}}. \end{aligned}$$(4.15)Note that this is the number of subsets B of \(\mathsf {adj}_{{\bar{\Phi }}}^{\star }(\omega )\) of size \(\delta _{k}\). The claim is true as (i) all plaquettes in B are flippable for \(\Psi (\omega )\), and (ii) every distinct choice of a subset B in the definition of \(\Phi \) results in a distinct image.
-
(ii)
By Lemma 4.3 (iii) we can reconstruct \(\omega \) from an image \(\omega '\in \Phi (\omega )\) given the sequence of spans in the classical bridge decomposition of \(\omega \). The maximal possible span of \(\Psi (\omega )\), the bridge produced by the classical bridge decomposition, is n, and by Proposition 4.2 the spans form a partition of \(\mathrm {span}(\Psi (\omega ))\). Thus the number of preimages \(\left| \Phi ^{-1}(\omega ')\right| \) is at most P(n), the number of partitions of n.
This establishes (4.9) if the index set \(\mathsf {B}_{n+2\delta _{k}}(n)\) of the sum on the right-hand side is replaced with \(\Phi (\mathsf {H}_{n}^{k})\). By Lemma 4.3 (ii), \(\Phi (\mathsf {H}_{n}^{k})\subset \mathsf {B}_{n+2\delta _{k}}(n)\), as \(\mathrm {span}(\omega ^{\prime }) = \mathrm {span}(\Psi (\omega ))\le n\). The proposition thus follows as each summand is non-negative. \(\square \)
Lemma 4.5
For \(\kappa \) sufficiently small, there are \(\delta >0\), \(K>0\), and \(a>0\) such that
for all \(k\in \mathbb {N}\).
Proof
We will show that for \(0<\delta <\frac{1}{2}\) small enough there is a \(\kappa '\) such that for \(\kappa \in \left[ 0,\kappa '\right] \), there are \(a,K>0\) such that (4.16) holds. This implies the statement of the lemma. Since it suffices to prove the validity of (4.16) for \(k>k':=(\delta \alpha )^{-1}\), we will restrict attention to such k.
We begin by estimating the combinatorial prefactor in (4.16). Recall the definition of \(\alpha _{k}\) and \(\delta _{k}\) in (4.8). By using (i) \({n\atopwithdelims ()k}\ge (n/k)^{k}\) for \(1\le k\le n\), (ii) \(\max \{1,x\} \le \lceil x\rceil \le x+1\) for \(x>0\), and (iii) \(k>k'\) and \(\delta <\frac{1}{2}\), we obtain
Thus, when \(k>k'\), the left-hand side of (4.16) is bounded above by
and the claim will follow by showing that the quantity in square brackets is strictly less than one.
By Proposition 4.1, \(\mu _{\mathsf {B}}(\kappa ) = \sup _{n} \big ( b_n (\kappa ) \big )^{1/n}\), and this latter quantity is at most \(\sup _{n} \big ( c_{n}(\kappa ) \big )^{1/n}\). This, in turn, is bounded above by \((1+\kappa )^{2d-2}\), as each edge in a self-avoiding walk can be adjacent to at most \(2d-2\) others. Since \(\delta \alpha k>1\) when \(k>k'\), we can bound above the bracketed quantity of (4.18) by
Recalling the definition (3.2) of \(\mathrm {flip}_{\kappa }\), it follows that when \(\kappa =0\) the quantity in (4.19) is strictly less than one, for \(\delta =\delta (p_{1})\) sufficiently small. Since the expression in (4.19) is continuous in \(\kappa \) for \(\delta \) fixed, it is strictly less than one for small positive \(\kappa \). This proves the claim. \(\square \)
The next theorem is a consequence of a stronger result due to Hardy and Ramanujan; it will be needed to estimate the mass of n-step half-space walks.
Theorem 4.6
(Hardy–Ramanujan [17]) Let P(n) denote the number of partitions of n into distinct parts. Then
meaning that the ratio of the two sides tends to 1 as \(n\rightarrow \infty \).
Proposition 4.7
Consider SAW on \(\mathbb {Z}^{d}\). For \(\kappa \) sufficiently small, there are \(a_{1},K_{1}>0\) such that
Proof
By Proposition 4.1, \(b_{\ell }(\kappa ) \le \mu _{\mathsf {B}}(\kappa )^{\ell }\). Hence, dropping the constraint that the spans of bridges on the right-hand side of (4.3) are at most n yields
The right-hand side of (4.22) is summable in k, and the left-hand side sums to \(h_{n}(\kappa )\). By Theorem 4.6, \((1+\kappa )^{3d(d-1)\sqrt{n}} P(n)\) is at most \(K_{1}e^{a_{1}\sqrt{n}}\) for constants \(K_{1},a_{1}>0\); this completes the proof. \(\square \)
Proof of Theorem 2.1
To prove \(\mu (\kappa ) = \mu _{\mathsf {B}}(\kappa )\), it suffices to prove that there exist \(K'\) and \(a'\) such that
For \(\omega \in \Gamma _{n}\), let m be the maximal i such that \(\pi _{1}(\omega _{i})\) is minimized. Let \(\omega ^{1} = \omega _{\left[ 0,m\right] }\) and \(\omega ^{2}=\mathcal {T}_{(-\omega _{m})}\,\omega _{\left[ m,n\right] }\). The first part of the proof is to define a multivalued map \(\Psi \) that assigns to \((\omega ^{1},\omega ^{2})\) a set of pairs of half-space walks \(\{(\eta ^{1},\eta ^{2})\}\) in an injective way. Note that \(\omega ^{2}\) is a half-space walk.
The reversal of a walk \(\eta =(\eta _{i})_{i=1}^{m}\) is the walk \((\eta _{m-i})_{i=0}^{m-1}\); this walk begins at the endpoint of \(\eta \) and goes back to the initial vertex. Translate the reversal of \(\omega ^{1}\) so that the walk begins at the origin, i.e., consider the reversal of \(\mathcal {T}_{(-\omega _{m})}\omega ^{1}\). This is almost a half-space walk; the only problem is that it may visit the coordinate hyperplane \(\pi _{1}^{-1}(o)\) more than just at the initial vertex.
We now define \(\Psi \). Set \(\eta ^{2} :=\omega ^{2}\). Define \({\tilde{\omega }}^{1}\) to be the concatenation of the one-step self-avoiding walk from o to \(e_{1}\) with the reversal of \(\omega ^{1}\). Let \(x :=e_{1}-\omega _{m}\) denote the vector along which \(\omega ^{1}\) is translated when forming this concatenation. Note that \({\tilde{\omega }}^{1}\) is a half-space walk.
Let \(\mathsf {adj}= \mathsf {adj}(\omega ^{1},\omega ^{2})\), and suppose this set contains k flippable plaquettes for \(\omega ^{1}\). Let \(\mathsf {adj}^{\star }\subset \mathsf {adj}\) be a subset of disjoint flippable plaquettes of size \(\alpha _{k}\); such a subset exists by Lemma 3.5. Then
By an argument as in the proof of Lemma 4.3, \(\eta ^{1}\) is a half-space walk, as any flips do not change the minimal value of the first coordinate of \(\tilde{\omega }^{1}\). Note that if \(\eta ^{2}\in \mathsf {B}_{m}\), then \(\eta ^{1}\in \mathsf {B}_{n-m+2\delta _{k}+1}\).
We now verify that it is possible to reconstruct \((\omega ^{1},\omega ^{2})\), and hence \(\omega \) itself, from any image \((\eta ^{1},\eta ^{2})\). Given \(\eta ^{1}\), the translation applied to \(\omega ^{1}\) is determined, as flips do not change the endpoints of walks. The translation applied to \(\omega ^{1}\) determines the translation applied to \(\eta ^{2}\), and hence determines \(\omega ^{2}\). Hence, by Lemma 3.2, \(\omega ^{1}\) is determined since we know \(\omega ^{2}\) and \(\eta ^{1}\).
Recall that \(\sqcup \) indicates a union of disjoint sets, and note \(\Gamma _{n} = \sqcup _{k=0}^{n}\Gamma _{n}^{k}\), where \(\Gamma _{n}^{k}\) is the set of self-avoiding walks such that \(\left| \mathsf {adj}(\omega ^{1},\omega ^{2})\right| =k\). Proceeding as in the proof of Lemma 4.4 yields
The exponent of \((1+\kappa )\) is \(k+k_{0}\) as we have used Lemma 3.3 in the unfolding step that created the pair of half-space walks. Using Proposition 4.7 to estimate the factors \(h_{\ell }(\kappa )\) and Lemma 4.5 to estimate the remaining terms yields
where \(K'\) is the product of the constant prefactors. The inequality \(\sqrt{x} + \sqrt{y} \le \sqrt{2x+2y}\) combined with the fact that k is at most n implies a further upper bound of the form
for some \(K'',a'>0\). As this establishes (4.23), the proof is complete. \(\square \)
5 Averaged submultiplicativity and initial consequences
The transformation used to estimate entropic gains in Sect. 4 flipped a fixed fraction \(\delta \alpha \) of flippable plaquettes, and this led to \(p_{1}\)-dependent constants in estimates, where we recall \(p_{1}\) depends on the step distribution D. This was convenient as it gave us precise control over the length added to a walk. For a lace expansion analysis the lack of uniformity in \(p_{1}\) complicates matters, and this section defines a greedier transformation that enables estimates uniform in \(p_{1}\) when \(\kappa = \kappa (p_{1})\) is chosen correctly. The price to pay is less control over the increase in length of a walk.
5.1 \(\kappa \)-ASAW with a memory
We first define memories, which will play the role of boundary conditions for self-avoiding walks. Recall that \(\tilde{\Gamma }(o)\) is the set of self-avoiding polygons that begin at the origin.
Definition 10
A memory is a walk \(\eta \in \bigcup _{x}\Gamma (x,o) \cup \tilde{\Gamma }(o)\).
By a slight abuse of notation, let \(\omega \cap \eta \) denote the set of vertices in common to two walks \(\omega \) and \(\eta \). We will now define the law of \(\kappa \)-ASAW conditional on having memory \(\eta \). Let \(\Gamma _{n}^{o}:=\cup _{x}\Gamma _{n}(x)\) denote the set of n-step SAW with initial vertex o. For \(n\in \mathbb {N}\), \(\kappa \ge 0\), and a memory \(\eta \), define n-step\(\kappa \)-ASAW with memory\(\eta \) to be the law \(\mathsf {P}^{\eta }_{n,\kappa }\) on \(\Gamma _{n}^{o}\) given by
where
where we have recalled the definition of \(H_{\kappa }(\omega ;\eta )\) from (2.7) for the convenience of the reader. Thus \(\mathsf {P}_{n,\kappa }^{\eta }\) is supported on self-avoiding walks that intersect \(\eta \) only at their initial vertex \(\omega _{0}=o\), and \(\mathsf {P}_{n,\kappa }^{\eta }\) gives a reward of \((1+\kappa )\) for each pair of adjacent edges in \(\omega \) and for each time an edge of \(\omega \) is adjacent to an edge of \(\eta \).
5.2 Averaged submultiplicativity
Let \(\eta \) be a memory. Define
where (by a slight abuse of the notation in (4.6)) \(\mathsf {adj}_{1}(\omega ,\eta )\) is the set of plaquettes that are flippable for \(\omega \) in \(\mathsf {adj}(\omega ,\eta )\). The (n, k) two-point function with memory \(\eta \) is
The dependence of \(c_{n,k}^{\eta }(x)\) on \(\kappa \) is left implicit. Let \(c_{n}^{\eta } (x) :=\sum _{k\ge 0} c_{n,k}^{\eta }(x)\).
Definition 11
Let \(z\ge 0\), \(\kappa \ge 0\), and \(x\in \mathbb {Z}^{d}\). The two-point function\(G^{\eta }_{z,\kappa }(x)\)with memory\(\eta \) is defined to be
If \(\eta =\emptyset \) this is identically the 2-point function of \(\kappa \)-ASAW as defined in (2.3).
Recall that the critical point \(z_{c}(\kappa )\) was specified in Definition 3. The next proposition will imply that \(G^{\eta }_{z,\kappa }\) is well-defined when \(z<z_{c}(\kappa )\).
Definition 12
Define \(z_{0}(\kappa ):=(1+\kappa )^{-2(d-1)}\).
This choice of \(z_{0}\) will be useful in Sect. 6.5 for making comparisons with simple random walk. Recall that \(k_{0}\) was defined in (3.1).
Proposition 5.1
Suppose that \(\kappa _{0}(d,p_{1})\) is sufficiently small and that \(z\ge z_{0}(\kappa )\). Then, for all \(\kappa < \kappa _{0}\),
In particular, \(G^{\eta }_{z,\kappa }(x)\) is an absolutely convergent power series when \(\left| z\right| <z_{c}(\kappa )\).
Proof
We begin by defining a multivalued map \(\Phi \) that will quantify the entropic gain of forgetting a memory. Let \(\omega \in \Gamma _{m,k}^{\eta }\). By Lemma 3.5, there exists a set \(\mathsf {adj}^{\star } \subset \mathsf {adj}(\eta ,\omega )\) of \(\alpha _{k}=\lceil \alpha k\rceil \) disjoint flippable plaquettes for \(\omega \). Define \(\Phi \) by
The definition of \(\Phi \) implicitly depends on \(\eta \) through \(\mathsf {adj}^{\star }\), but we suppress this dependence from the notation as \(\eta \) is fixed.
To begin, we compare the weight of \(\omega \in \Gamma _{m,k}^{\eta }(x)\) under \(\mathcal {W}_{\kappa }(\cdot ;\eta )\) to the weight \(\mathcal {W}_{\kappa }(\cdot )\) of its image \(\Phi (\omega )\). We claim that
To see this, note that at each \(P\in \mathsf {adj}^{\star }\) a flip may or may not occur. Hence the definition of \(\Phi \) implies
Formally, this bound arises by applying Lemma 3.4\(\left| B\right| \) times to \(\omega ^{\prime }=\mathcal {F}_{B}(\omega )\), and then summing over all \(B\subset \mathsf {adj}^{\star }\). As \(\omega \in \Gamma _{m,k}^{\eta }(x)\), there is a \(\sigma \in \{0,1,\ldots ,k_{0}\}\) such that \(\mathcal {W}_{\kappa }(\omega ) = (1+\kappa )^{-k-\sigma } \mathcal {W}_{\kappa }(\omega ;\eta )\). The possible values for \(\sigma \) follows from the proof of Lemma 3.3, which shows there are at most \(k_{0}\) plaquettes that are not flippable in \(\mathsf {adj}(\omega ,\eta )\), because such plaquettes only occur at points of concatenation. Inserting this formula for \(\mathcal {W}_{\kappa }(\omega )\) into (5.8) and rearranging gives (5.7).
Since \(\kappa \ge 0\),
The right-hand side of (5.9) is at most \((1+\kappa )^{\frac{1}{\alpha }}(1+z_{0}^{2}p_{1}^{2}(1+\kappa )^{-(2d-4)})^{-1}\), which is strictly less than one when \(\kappa =0\). The right-hand side of (5.9) is continuous in \(\kappa \) and hence is strictly less than one for small positive \(\kappa \). Thus, for \(\kappa \) sufficiently small and \(z\ge z_{0}\), (5.7) implies
Sum (5.10) over \(\omega \in \Gamma ^{\eta }_{m}(x) = \sqcup _{k\ge 0}\Gamma ^{\eta }_{m,k}(x)\). To conclude the proof what must be shown is that \(\Phi (\omega )\subset \Gamma (x)\), and that if \(\omega ^{i}\in \Gamma ^{\eta }_{m}(x)\), \(i=1,2\), then
The first claim follows from Lemma 3.1. To prove the second claim, suppose \(\gamma ^{i}\in \Phi (\omega ^{i})\), \(i=1,2\). Then as \(\gamma ^{i}\) is the result of flipping \(\omega ^{i}\) at a disjoint set B of flippable plaquettes, Lemma 3.2 implies \(\omega ^{i}\) is determined by \(\gamma ^{i}\) and \(\eta \). Hence if \(\gamma ^{1}=\gamma ^{2}\), then \(\omega ^{1}=\omega ^{2}\). \(\square \)
For our lace expansion analysis it will be necessary to have a slight generalization of Proposition 5.1. Let \(\eta \) be a memory and define
Thus \(\bar{\mathsf {P}}_{n,\kappa }^{\eta }\) is a law on n-step self-avoiding walks that do not intersect \(\eta \) except for (i) at \(\omega _{0}=o\) and (ii) possibly at \(\omega _{n}\). Let \({\bar{G}}^{\eta }_{z,\kappa }(x)\) denote the two-point function for walks with law \(\bar{\mathsf {P}}_{n,\kappa }^{\eta }\).
Corollary 5.2
Proposition 5.1 holds for \({\bar{G}}^{\eta }_{z,\kappa }\) in place of \(G^{\eta }_{z,\kappa }\) after changing \((1+\kappa )^{k_{0}}\) to \((1+\kappa )^{2k_{0}}\).
Proof
The proof for \({\bar{G}}^{\eta }_{z,\kappa }\) is, mutatis mutandis, the proof of Proposition 5.1. The extra factor of \((1+\kappa )^{k_{0}}\) arises as the proof of Lemma 3.3 allows for the existence of \(2k_{0}\) plaquettes in \(\mathsf {adj}(\eta ,\omega )\) that are not flippable. This is because there may be \(k_{0}\) such plaquettes for each point of concatenation, of which there are at most 2. \(\square \)
Corollary 5.3
Both Proposition 5.1 and Corollary 5.2 hold when the two-point functions are restricted to sums over walks of length at least m for \(m\in \mathbb {N}\).
Proof
The map \(\Phi \) used in the proof of Proposition 5.1 only increases the length of a walk. \(\square \)
5.3 First applications of averaged submultiplicativity
It will be necessary to temporarily consider \(\kappa \)-ASAW in a finite volume. Precisely, let \(\Lambda = (\mathbb {Z}/L\mathbb {Z})^{d}\) be a torus of side length L. Define
Let \(\chi _{\Lambda }(z)\) be the susceptibility associated to \(\kappa \)-ASAW on \(\Lambda \), i.e.,
Note that \(\chi _{\Lambda ,\kappa }(z)\) is a polynomial in z whenever \(\Lambda \) is finite. We will attach the subscript \(\Lambda \) to other finite volume quantities in an analogous way.
Lemma 5.4
Let \(\kappa _{0}(d,p_{1})\) be as in Proposition 5.1. Fix \(\kappa <\kappa _{0}(d,p_{1})\) and \(z\ge z_{0}\). On a finite torus \(\Lambda \),
Proof
The proof we will give is the standard one for self-avoiding walk, with averaged submultiplicativity (Proposition 5.1) replacing submultiplicativity. While Proposition 5.1 is for \(\kappa \)-ASAW on \(\mathbb {Z}^{d}\), the proof applies immediately to \(\Lambda \) as well: the only property of the graph that was used in the proof is that flips of flippable plaquettes are well-defined.
As \(\chi _{\Lambda ,\kappa }(z)\) is a polynomial in z, we can compute
Equation (5.16) follows by using the fact that for \(\omega \in \Gamma \),
and then splitting \(\omega \) into \(\eta =\omega _{\left[ 0,i\right] }\) and \(\omega '\). The third equality follows from the definition of the conditional weight \(\mathcal {W}_{\kappa }(\cdot \,;\eta )\) and the translation invariance of \(G^{\eta }_{z,\kappa ,\Lambda }\) on a torus.
By (the finite-volume version of) Proposition 5.1, the memory \(\eta \) can be ignored to obtain an upper bound. Summing over y results in a factor \(\chi _{\Lambda ,\kappa }(z)\), as does the sum over x. The result is
Computing the derivative on the left-hand side, rearranging, and using \(\chi _{\Lambda ,\kappa }(z)\ge 0\) proves the lemma. \(\square \)
The validity of Lemma 5.4 for all \(z\ge z_{0}\) and all finite \(\Lambda \) implies the continuity of the phase transition for \(\kappa \)-ASAW and a mean-field lower bound on the critical exponent \(\gamma \). Proposition 5.6 below is a formal statement of these facts. We include a proof for completeness, although the implication given Lemma 5.4 is well-known [18]. We need one preparatory lemma.
Lemma 5.5
For any \(z<z_{c}\) there are constants \(c_{1}(z),c_{2}(z)\) such that \(G_{z,\kappa }(x)\le c_{1}(z)\exp (-c_{2}(z)\Vert x\Vert _{\infty })\).
Proof
This follows from the fact that the summation defining \(G_{z,\kappa }(x)\) contains only walks of length at least \(C\Vert x\Vert _{\infty }\) for some \(C>0\), and hence is contained in the tail of the convergent sum \(\chi _{\kappa }(z)\). For more details, see [4, p.11–12]. \(\square \)
Proposition 5.6
Let \(\kappa _{0}(d,p_{1})\) be as in Proposition 5.1. For \(0<\kappa <\kappa _{0}(d,p_{1})\) and \(z_{0}\le z<z_{c}\),
where \(\chi _{\kappa }(z)\) is defined by (2.2).
Proof
Note that \(\chi _{\Lambda ,\kappa }(z)\ge 1\) due to the contribution of the zero-step walk. Fixing \(\epsilon >0\) and integrating (5.14) from \(z\ge z_{0}\) to \(z_{c}+\epsilon \) implies
Let \({\bar{\chi }}_{\Lambda ,\kappa }(z)\) be the contribution to the infinite volume susceptibility \(\chi _{\kappa }(z)\) due to walks restricted to the finite box \(\Lambda \) without periodic boundary conditions. \({\bar{\chi }}_{\Lambda ,\kappa }(z)\) is monotone in \(\Lambda \) and converges to \(\chi _{\kappa }(z)\). Moreover, \(\chi _{\Lambda ,\kappa }(z)\) dominates \({\bar{\chi }}_{\Lambda ,\kappa }(z)\), and hence \(\left( \chi _{\Lambda ,\kappa }(z_{c}+\epsilon )\right) ^{-1}\) tends to zero as \(\Lambda \uparrow \mathbb {Z}^{d}\) by the definition of \(z_{c}\).
To conclude it is enough to prove that \(\left( \chi _{\Lambda ,\kappa }(z)\right) ^{-1}\) converges to \(\left( \chi _{\kappa }(z)\right) ^{-1}\) as \(\Lambda \uparrow \mathbb {Z}^{d}\), as we can then take \(\Lambda \uparrow \mathbb {Z}^{d}\) in (5.20), followed by \(\epsilon \rightarrow 0\). To see this we note that Proposition 5.1 implies
by reasoning as from (5.15) to (5.17); here \(\partial \Lambda \) denotes the boundary vertices of \(\Lambda \). Dividing through by \(\chi _{\Lambda ,\kappa }(z)\) and using that \(G_{z,\kappa }(x)\) decays exponentially in \(\Vert x\Vert _{\infty }\) by Lemma 5.5 proves that \({\bar{\chi }}_{\Lambda ,\kappa }(z)\) has the same limit as \(\chi _{\Lambda ,\kappa }(z)\). This proves the claim as we have already noted that \({\bar{\chi }}_{\Lambda ,\kappa }(z)\) converges to \(\chi _{\kappa }(z)\). \(\square \)
6 A lace expansion for \(\kappa \)-ASAW
This section derives and analyzes a lace expansion for \(\kappa \)-ASAW to prove Theorem 2.3. As self-avoiding walk is the special case \(\kappa =0\) of \(\kappa \)-ASAW, many aspects of our analysis mirror the SAW case. In what follows we therefore focus on the details specific to \(\kappa \ne 0\), and give precise statements and references for the details that we omit.
For the reader unfamiliar with the lace expansion, the following pointers to the literature may be helpful. Our derivation of a lace expansion for \(\kappa \)-ASAW in Sect. 6.2 is an adaptation of the Brydges-Spencer expansion [19]; [4, Ch. 3.2–3.3] and [6, Ch. 5.2] contain pedagogical accounts of this method. For the derivation of diagrammatic bounds our approach in Sect. 6.4 is similar to [8], but the unfamiliar reader may wish to consult [4, Ch. 4] or [6, Ch. 5.4] as a first introduction to the notion of diagrammatic bounds. It is at this step that we make use of averaged submultiplicativity. Lastly, for the convergence of the expansion and proof of Theorem 2.3 we make use of the method of [8]. We recall the method of [8] in Appendix A, and our proof of Theorem 2.3 is by a verification of the hypotheses of this method.
6.1 Explicit \(\kappa \)-ASAW interaction
In this section we give an algebraic formulation of the \(\kappa \)-ASAW weight. Let
Lemma 6.1
If \(\omega \in \mathsf {W}_{n}\) is an n-step walk with \(\omega _{0}=o\), then \(\mathsf {P}_{n,\kappa }(\omega )\) is proportional to
Proof
Recall that \(\omega _{i+1}\ne \omega _{i}\) by the definition of a walk. As \(\omega _{i}=\omega _{j}\) precludes \(\{\omega _{i},\omega _{i+1},\omega _{j-1},\omega _{j}\}\) being a plaquette, the first indicator in (6.1) encodes the self-avoidance constraint between \(\omega _{i}\) and \(\omega _{j}\) for \(j>i+1\). The second indicator encodes the self-attraction between edges; each attraction is counted with weight \(1+\kappa \) when \(\omega _{i}\) is the first visit to a plaquette and \(\omega _{j}\) is the last visit to the plaquette, which requires \(j\ge i+3\). \(\square \)
6.2 Derivation of the lace expansion
In this section we derive a lace expansion for \(\kappa \)-ASAW using the so-called algebraic method [4]. A similar expansion for a vertex attraction was derived in [1].
For \(a\le b\) integers let \(\left[ a,b\right] :=\{a,a+1,\ldots , b\}\), and \(\left[ a,a-1\right] =\emptyset \). An edge\(\{i,j\}\) is an element of \({\left[ a,b\right] \atopwithdelims ()2}\) with \(\left| i-j\right| >1\); \(\{i,j\}\) will be abbreviated ij. A graphG on \(\left[ a,b\right] \) is a (possibly empty) set of edges, and G is connected if for all \(j\in \left[ a+1,b-1\right] \) there are \(i<j<k\) such that ik is an edge in G. Let \(\mathsf {G}_{\left[ a,b\right] }\) denote the set of graphs on \(\left[ a,b\right] \), and \(\mathsf {G}^{\mathsf {c}}_{\left[ a,b\right] }\) the set of connected graphs. Let \(\omega \) be a walk and define
These definitions imply \(K_{\left[ a,a\right] }=K_{\left[ a,a+1\right] }=J_{\left[ a,a\right] }=J_{\left[ a,a+1\right] }=1\) due to the contribution of the empty graph.
Expanding the product of \((1-U_{ij})\) over ij in (6.2) and using (2.3) implies the two-point function can be written in terms of graphs:
In what follows, we manipulate (6.5) by rewriting the term \(K_{\left[ 0,n\right] }(\omega )\) to obtain a convolution equation for \(G_{z,\kappa }\). The first step is a well-known lemma. For notational convenience we will use the convention that \(\sum _{j=b+k}^{b}f(j)=0\) if \(k\ge 1\).
Lemma 6.2
(Lemma 5.2.2 of [6]) For any walk \(\omega \) and \(a<b\),
For \(x\in \mathbb {Z}^{d}\), define \(\Pi _{z,\kappa }(x)\) by
It is not a priori clear that the series defining \(\Pi _{z,\kappa }\) is convergent. When convergence is unknown we will interpret the series and the formulas in which it occurs as formulas relating formal power series in z. We recall that for \(f,g:\mathbb {Z}^{d}\rightarrow \mathbb {R}\) the convolution of f and g is \((f*g)(x) :=\sum _{y\in \mathbb {Z}^{d}}f(y)g(x-y)\), and we also recall that the step distribution D was introduced in (2.1).
Proposition 6.3
(Theorem 5.2.3 of [6]) As formal power series in z,
This is an equality between functions when all terms of (6.8) are absolutely convergent in z.
Proof
Consider the contribution of n-step walks to \(G_{z,\kappa }(\omega )\), i.e.,
Since \(U_{ij}(\omega )\) only depends on those \(\omega _{\ell }\) with \(i\le \ell \le j\), \(K_{\left[ 0,j\right] }(\omega )J_{\left[ j,n\right] }(\omega )\) is equal to \( K_{\left[ 0,j\right] }(\omega _{\left[ 0,j\right] })J_{\left[ j,n\right] }(\omega _{\left[ j,n\right] })\). Hence, by using (6.6) to rewrite the factor \(K_{\left[ 0,n\right] }\) in (6.9), the right-hand side of (6.9) can be rewritten as
To conclude, sum (6.9) over all n. The left-hand side is \(G_{z,\kappa }(x)\). For \(n=0\), the right-hand side is \({\mathbb {1}}_{\left\{ x=o\right\} }\), the contribution of the zero-step walk. For \(n\ge 1\) we use (6.10). The factors of \(G_{z,\kappa }\) arise by (6.5) and the translation invariance of \(\mathcal {W}_{\kappa }\). The term \(\Pi _{z,\kappa }\) arises from the sum over j by (6.7). This proves (6.8) in the sense of formal power series, as the coefficient of \(z^{n}\) consists of only finitely many terms for all n. \(\square \)
6.3 Representation of \(\pi ^{(m)}_{z,\kappa }(x)\)
To make use of Proposition 6.3 requires control on \(\Pi _{z,\kappa }\). Obtaining this control is at the heart of the lace expansion, and requires some further definitions.
Definition 13
A connected graph G is a lace if for any edge \(ij\in G\) the graph \(G{\setminus } ij\) is not connected. Let \(\mathsf {L}_{\left[ a,b\right] }^{(m)}\) denote the set of laces on \(\left[ a,b\right] \) with m edges, and \(\mathsf {L}_{\left[ a,b\right] } = \bigsqcup _{m\ge 1}\mathsf {L}_{\left[ a,b\right] }^{(m)}\).
Lemma 6.4
(pp.126–128 of [6]) For \(G\in \mathsf {G}^{\mathsf {c}}_{\left[ a,b\right] }\), let \(\mathcal {L}(G)\) be the graph with edges \(\{s_{i}t_{i}\}\) defined by \(s_{1}=a\), \(t_{1} = \max \{t \mid s_{1}t\in G\}\), and
Then (i) \(\mathcal {L}(G)\) is a lace and (ii) if \(\mathcal {L}(G)=\mathcal {L}(H)\) then \(\mathcal {L}(G\cup H)=\mathcal {L}(G)\).
Figures 6 and 7 depict a graph G and its associated lace \(\mathcal {L}(G)\).
\(\mathsf {G}_{\left[ a,b\right] }\) is partially ordered by inclusion, and Lemma 6.4 implies that for every lace L there is a maximal graph G such that \(\mathcal {L}(G)=L\). The edges of the maximal graph G can be partitioned into \(L\sqcup \mathsf {C}(L)\), where \(\mathsf {C}(L)\) are called the compatible edges. Explicitly, \(ij\in \mathsf {C}(L)\) if and only if \(ij\notin L\) and \(\mathcal {L}(L\cup \{ij\})=L\). It follows that
Define \(J^{(m)}_{\left[ a,b\right] }\) to be the contribution to (6.11) given by \(L\in \mathsf {L}_{\left[ a,b\right] }^{(m)}\), and let
These definitions imply that as formal power series
and our approach to controlling \(\Pi _{z,\kappa }\) will be to estimate the terms \(\pi ^{(m)}_{z,\kappa }\). This will be done by re-expressing \(\pi ^{(m)}_{z,\kappa }\) in terms of sums of collections of walks subject to conditional interactions \(\mathcal {W}_{\kappa }(\cdot \,;\eta )\) and estimating these sums. The remainder of this section introduces the definitions needed to make the reformulation of \(\pi ^{(m)}_{z,\kappa }\) precise. As noted previously, the arguments are similar to standard ones [4, 6]; see also [1].
A lace \(L\in \mathsf {L}^{(m)}_{\left[ 0,n\right] }\) partitions \(\left[ 0,n\right] \) into \(2m-1\) intervals with disjoint interiors, and this induces a composition of n into \(2m-1\) parts. See Fig. 7. This composition yields a vector \(\varvec{n} :=(n_{1},n_{2},\ldots , n_{2m-1})\) of interval lengths with the properties
and \(n=\textstyle {\sum _{j=1}^{2m-1}}n_{j}\). Conversely, to each such \(\varvec{n}\) there is associated a unique lace graph [4, Exercise 3.6].
Let \(M_{i} :=\sum _{j=1}^{i}n_{j}\). By our convention for sums, \(M_{k}:=0\) for \(k\le 0\). Define \(I_{j} :=\left( M_{j-1},M_{j}\right] \) for \(j=1,2,3,\ldots ,2m-1\) and \(I_{k}:=\emptyset \) for \(k\le 0\). Let \(\mathsf {C}_{i}(L) :=\{i'j'\mid j'\in I_{i}\}\) be the set of compatible edges \(i'j'\) whose right endpoint \(j'\) is in \(I_{i}\). Observing that \(\mathsf {C}(L)=\bigsqcup _{i=1}^{2m-1}\mathsf {C}_{i}(L)\) since the intervals \(I_{i}\) are a partition of \(\left( 0,n\right] \), these definitions imply that, for any lace \(L\in \mathsf {L}^{(m)}_{\left[ 0,n\right] }\) and walk \(\omega \in \mathsf {W}_{n}\),
Because \(\mathsf {C}_{i}(L)\) consists of edges whose right endpoint is in \(I_{i}\), the second product on the right-hand side of (6.15) describes an interaction between the vertices \(\{\omega _{j}\}_{j\in I_{i}}\) and the vertices \(\{\omega _{j'}\}_{j'\le M_{i}}\). Proposition 6.5 below controls this interaction; achieving this control requires characterising the edges \(ij\in \mathsf {C}(L)\).
Recalling that \(M_{k}=0\) and \(I_{k}=\emptyset \) for \(k\le 0\), the compatible edges can be characterized as follows. Let \(M^{k}_{2k-2}=M_{2k-2}\) if \(k\ne 1\), and \(M^{1}_{0}=\emptyset \). For \(k\ge 0\), \(i<j\), and \(m\ge 1\):
-
(i)
if \(j\in I_{2k+1}\), then \(i\in \bigcup _{\ell =2k-1}^{2k+1}I_{\ell }\cup \{M_{2k-2}\}\), and \(j=M_{2m-1}=n\) implies \(i>M_{2m-3}\).
-
(ii)
if \(j\in I_{2k+2}\), then \(i\in \bigcup _{\ell =2k-1}^{2k+2}I_{\ell }\cup \{M_{2k-2}\}\), and \(j=M_{2k+2}\) implies \(i>M_{2k-1}\).
This classification follows by considering the procedure defined in Lemma 6.4. For \(m=1\) the only incompatible edge is 0n. For \(m\ge 2\) the constraints fall into three types: for \(I_{2k+2}\), \(k\ge 1\); for \(I_{2k+1}\), \(k\le m-2\); and for \(I_{2},I_{3},I_{4}\) and \(I_{2m-1}\). The case \(I_{2}\) is distinguished because the only endpoint of a lace between \(s_{1}\) and \(t_{1}\) is \(s_{2}\), while for \(i\ge 2\) we have \(s_{i}<t_{i-1}\le s_{i+1}<t_{i}\). This distinction is manifested above by the triviality of the intervals \(I_{k}\) for \(k\le 0\). \(I_{3}\) and \(I_{4}\) are distinguished as the initial vertex of a compatible edge cannot be 0, and \(I_{2m-1}\) is distinguished for a similar reason. See Fig. 8.
Definition 14
For \(\varvec{n}\) a composition of n into \(2m-1\) parts and \(\omega \in \mathsf {W}_{n}\), let \(\varvec{\omega }:=(\omega ^{(i)})_{i=1}^{2m-1}\) denote the vector of walks determined by \(\omega ^{(i)} :=\omega _{\left[ M_{i-1},M_{i}\right] }\). Note \(\omega ^{(i)}\) has length \(n_{i}\).
Using the characterisation of compatible edges above we will now rewrite the right-hand side of (6.15) in terms of the subwalks \(\omega ^{(i)}\); this requires some further definitions. To keep the notation to a minimum we will in fact give an upper bound.
When \(m=1\) define
For \(m\ge 2\) we introduce: \(\eta ^{(1)}:=\emptyset \); \(\eta ^{(2)}:=\omega ^{(1)}\); for \(k=1,\ldots ,m-1\), \(\eta ^{(2k+1)}:=\omega ^{(2k-1)}\circ \omega ^{(2k)}\); and for \(k=2,\ldots ,m-1\), \(\eta ^{(2k)}:=\omega ^{(2k-3)}\circ \omega ^{(2k-2)}\circ \omega ^{(2k-1)}\). For \(m\ge 2\), \(1\le k\le 2m-1\), and \(L\in \mathsf {L}^{(m)}\) define \(A^{(m)}_{k} = A^{(m)}_{k}(L)\) by
where \(i'\) is the index such that \(\omega ^{(k)}_{i}\) is the \(i'\)th vertex in \(\omega = \omega ^{(1)}\circ \cdots \circ \omega ^{(2m-1)}\), and similarly for \(j'\).
Proposition 6.5
Let \(m\ge 1\) and \(1\le k\le 2m-1\) be integers, let \(L\in \mathsf {L}^{(m)}\) have an associated length vector \(\varvec{n}\), let \(\omega \in \mathsf {W}_{n}\), and let \(\omega ^{(k)}\) be the kth subwalk of \(\omega \) determined by L as in Definition 14. Then
Proof
The proposition is largely a translation of the definition of a compatible edge \(i'j'\in \mathsf {C}_{k}(L)\) and the definitions of the walks \(\eta ^{(k)}\).
Let us first consider \(m=1\), so \(k=1\). In this case \(\eta ^{(1)}=\emptyset \). Each factor \(1-U_{i'j'}(\omega )\) for \(i'j'\in \mathsf {C}_{1}(L)\) enforces \(\omega ^{(1)}_{i'}\ne \omega ^{(1)}_{j'}\) (in the case \(k=1\) there is no distinction between primed and unprimed indices). Since the only edge that is not compatible is 0n, we see that \(\omega _{\left[ 0,n-1\right] }\) is self-avoiding, but \(\omega _{n}=\omega _{0}\) is not forbidden. Hence \(\omega ^{(1)}\in \Gamma \cup \tilde{\Gamma }\), which is precisely the constraint that \(A^{(1)}_{1}\) occurs.
Similarly, the factors of \(1-U_{i'j'}(\omega )\) encode the reward \((1+\kappa )\) if \(\{i',i'+1,j'-1,j'\}\) is a plaquette. Since 0n is not compatible, if the first and last edges of \(\omega ^{(1)}\) are parallel this reward is not present. Since including this reward gives an upper bound we do so, as it allows the right-hand side to be written as \(\mathcal {W}_{\kappa }(\omega ^{(1)};\emptyset )\).
For \(m\ge 2\) and \(1\le k\le 2m-1\), the considerations are almost exactly the same. The fact that \(\omega ^{(k)}\in \Gamma \) follows as \(i'j'\in \mathsf {C}_{k}(L)\) if \(0\le i<j\le n_{k}\) and \(j>i+1\) by the classification of compatible edges for a lace, and this implies \(\omega ^{(k)}_{i}\ne \omega ^{(k)}_{j}\). The definitions of \(A^{(m)}_{k}\) arise from observing that the set of compatible edges have endpoints \(i'\) such that \(\omega _{i'}\) falls into one of the walks comprising \(\eta ^{(k)}\). We obtain an upper bound by including additional rewards \((1+\kappa )\) corresponding to incompatible edges, and this recreates the weight \(\mathcal {W}_{\kappa }(\omega ^{(k)};\eta ^{(k)})\). \(\square \)
6.4 Diagrammatic bounds
Proposition 6.5 leads to an upper bound for \(\pi _{z,\kappa }^{(m)}(x)\) in terms of a sum over collections \(\varvec{\omega }\) of interacting walks. This will be used to estimate the size of \(\left| \pi ^{(m)}_{z,\kappa }(x)\right| \) in terms of convolutions of \(G_{z,\kappa }(x)\); the resulting bounds are what are known as diagrammatic bounds. The next definition will be used in upper-bounding the factors \(-U_{ij}(\omega )\) in (6.11).
Definition 15
Define \(r_{\kappa }(x) :={\mathbb {1}}_{\left\{ x=o\right\} } + \kappa {\mathbb {1}}_{\left\{ \Vert x\Vert _{\infty }=1\right\} }\).
In what follows \(\kappa = \kappa (p_{1})\) will be a function of \(p_{1}\), chosen such that \(\kappa \le \kappa _{0}(d,p_{1})\); in particular Proposition 5.1 applies when \(z\ge z_{0}=(1+\kappa )^{-2(d-1)}\). Let \(H_{z,\kappa }(x) :=G_{z,\kappa }(x) - \delta _{x,o}\) be the sum of contributions to \(G_{z,\kappa }(x)\) due to non-trivial walks.
Proposition 6.6
Fix \(\kappa \le \kappa _{0}\), \(z_{0}\le z<z_{c}\), and \(x\in \mathbb {Z}^{d}\). The following bounds hold. For \(m=1\),
For \(m\ge 2\), let \(\varvec{y} :=(y_{2},y_{3},\ldots ,y_{2m-1})\in \mathbb {Z}^{d(2m-2)}\) denote a \((2m-2)\)-tuple of vertices in \(\mathbb {Z}^{d}\). Then
where the sum runs over all \(\varvec{y}\in \mathbb {Z}^{d(2m-2)}\). If \(m=2\) the product is empty, and hence identically one by definition.
A diagrammatic formulation of these upper bounds can be found in Fig. 9.
Proof of Proposition 6.6
We first outline the strategy of the proof. Recall the definition (6.12) of \(\pi ^{(m)}_{z,\kappa }(x)\) as a sum over walks \(\omega \in \mathsf {W}(x)\) and laces \(L\in \mathsf {L}^{(m)}\). The proof will use the decomposition of a walk \(\omega \) into \(2m-1\) subwalks \(\omega ^{(i)}\) as given by Definition 14. Proposition 6.5 gives a formula for the weight of the ith subwalk in terms of the preceding subwalks, and by using averaged submultiplicativity (Corollary 5.3) we will upper bound the sums over subwalks \(\omega ^{(i)}\) by factors of \(G_{z,\kappa }\) and \(H_{z,\kappa }\). The factors of \(r_{\kappa }\) will arise when we bound the product of \(-U_{ij}(\omega )\) over \(ij\in L\) in (6.12).
Recall the definition (6.1) of \(U_{ij}(\omega )\), and observe that for all walks \(\omega \)
which follows by considering separately \(\Vert \omega _{j}-\omega _{i}\Vert _{\infty }\) being 0, 1, or at least 2.
We first consider the case \(m=1\). By (6.12), (6.11), Proposition 6.5 and the definition (6.1) of \(U_{0n}(\omega )\) we have the upper bound
where the second inequality follows from (6.19) and explicitly separating out and summing over the location y of the first step of the walk.
Recall \(\left| \omega \right| =n\) if \(\omega \in \mathsf {W}_{n}\). Let \(\mathcal {W}_{z,\kappa }(\omega ;\eta ) =z^{\left| \omega \right| } \mathcal {W}_{\kappa }(\omega ;\eta )\), and recall the definition of \({\bar{G}}^{\eta }_{z,\kappa }(x)\) from below (5.12). The sum of \(\mathcal {W}_{z,\kappa }(\omega ;(o,y)) {\mathbb {1}}_{\left\{ (o,y)\circ \omega \in \Gamma \cup \tilde{\Gamma }\right\} }\) over \(\omega \in \mathsf {W}(y,x)\) of length at least one is at most \({\bar{G}}^{(o,y)}_{z,\kappa }(y-x)-\delta _{y-x,o}\). The proposition for \(m=1\) now follows from Corollary 5.3 and the translation invariance of \(H_{z,\kappa }\).
Next we consider \(m\ge 2\); the argument is very similar to \(m=1\). As described in Sect. 6.3, if \(L\in \mathsf {L}^{(m)}\) then \(\omega \) is the concatenation of \(2m-1\) walks \(\omega ^{(i)}\), \(\omega ^{(i)}\) has length \(n_{i}\), and the vector \(\varvec{n}\) of lengths satisfies (6.14). If \(\left| \omega \right| =n\), distribute the factor \(z^{n}\) so that there are \(n_{i}\) factors associated to the walk \(\omega ^{(i)}\). Then by Proposition 6.5 and (6.19),
where the outer sum is over \(\varvec{y}=(y_{2},\ldots , y_{2m-1})\in \mathbb {Z}^{d(2m-2)}\), the inner sum is over \(\varvec{\omega }= (\omega ^{(1)}, \ldots , \omega ^{(2m-1)})\) whose lengths \(n_{i}\) satisfy (6.14) and such that \(\omega ^{(1)}\in \mathsf {W}(y_{2})\), \(\omega ^{(i)}\in \mathsf {W}(y_{i},y_{i+1})\) for \(i=2,\ldots ,2m-2\), and \(\omega ^{(2m-1)}\in \mathsf {W}(y_{2m-1},x)\). The sum over laces has been replaced with a sum over the possible lengths of the subwalks: see the discussion following (6.14).
We now iteratively sum over the subwalks \(\omega ^{(i)}\), starting with \(i=2m-1\). Since \(\omega ^{(j)}\) is fixed for \(j=1\, \ldots , 2m-2\), the walk \(\eta ^{(2m-1)}\) is determined, and it plays the role of a memory for \(\omega ^{(2m-1)}\). Temporarily let \({\tilde{n}} = n_{2m-1}\), \({\tilde{\omega }} = \omega ^{(2m-1)}\), and \({\tilde{\eta }} = \eta ^{(2m-1)}\), and let \({\tilde{\mathsf {W}}}_{{\tilde{n}}} = \mathsf {W}_{{\tilde{n}}}(y_{2m-1},x)\). With these definitions we can upper bound the sum over \(\omega ^{(2m-1)}\) on the right-hand side of (6.20) by
This bound follows from Corollary 5.3, as the event \(A^{(m)}_{2m-1}\) occurs only if \(\omega ^{(2m-1)}\) does not intersect \(\eta ^{(2m-1)}\) except for the initial, and possibly terminal, vertices of \(\omega ^{(2m-1)}\); we have also used the fact that in the sum on the right-hand side of (6.20) the subwalks \(\omega ^{(i)}\) are all self-avoiding due to the events \(A^{(m)}_{i}\), and that these events imply \(\eta ^{(2m-1)}\) is self-avoiding or a self-avoiding polygon. The sum on the right-hand side of (6.21) is \(H_{z,\kappa }(x-y_{2m-1})\), as there is no contribution from zero-step walks due to the constraint \({\tilde{n}}\ge 1\).
Repeating this procedure for \(2m-2,2m-3,\ldots , 1\) gives the two-point functions in the upper bounds of the proposition. Factors of \(H_{z,\kappa }\) arise for edges on which \(n_{i}\ge 1\), and factors of \(G_{z,\kappa }\) for those with \(n_{i}\ge 0\); see (6.14). The overall factor of \((1+\kappa )^{(4m-2)k_{0}}\) arises as we obtain a factor of \((1+\kappa )^{2k_{0}}\) for each factor of \(H_{z,\kappa }\) and \(G_{z,\kappa }\), and there are \(2m-1\) of these. \(\square \)
6.5 Proof of Gaussian decay
We will now prove Theorem 2.3 by making use of Theorem A.6. Recall that \(\left| \left| \left| x\right| \right| \right| :=\max \{\Vert x\Vert _{2},1\}\).
Proposition 6.7
([8, Prop. 1.7]) If \(f,g:\mathbb {Z}^{d}\rightarrow \mathbb {R}\) satisfy \(\left| f(x)\right| \le \left| \left| \left| x\right| \right| \right| ^{-a}\) and \(\left| g(x)\right| \le \left| \left| \left| x\right| \right| \right| ^{-b}\) with \(a\ge b>0\), there exists \(C=C(a,b,d)\) such that
Proposition 6.8
Let \(d>4\). Suppose \(\beta >0\), \(\kappa \le \min \{\kappa _{0},\beta \}\), \(z_{0}\le z \le 2\), and that
If \(\beta \le \beta _{0}(d)\), then there is a \(c=c(d)>0\) such that
Proof
\(G_{z,\kappa }(o)=1\) as only the trivial self-avoiding walk ends at the origin, so (6.23) implies \(G_{z,\kappa }(x)\le \left| \left| \left| x\right| \right| \right| ^{-(d-2)}\) and \(H_{z,\kappa }(x)\le \beta \left| \left| \left| x\right| \right| \right| ^{-(d-2)}\) for all \(x\in \mathbb {Z}^{d}\). In particular, \(\Vert H_{z,\kappa }\Vert _{\infty }\le \beta \).
First consider \(\pi ^{(1)}_{z,\kappa }(x)\). If \(x=o\) then \(r_{\kappa }=1\), so (6.17), \(z\le 2\), and the inequality \(\Vert f*g\Vert _{1}\le \Vert f\Vert _{\infty }\Vert g\Vert _{1}\) imply
since \(\sum _{y}D(y)=1\). If \(x\ne o\) then \(\left| r_{\kappa }(x)\right| \le \kappa {\mathbb {1}}_{\left\{ \Vert x\Vert _{\infty }=1\right\} }\), and an argument as above shows that
where we have used \(\kappa \le \beta \) and \(z\le 2\).
Next we consider \(\pi ^{(m)}_{z,\kappa }(x)\) for \(m\ge 2\). The factors \(r_{\kappa }\) in (6.18) imply the collections \(\varvec{y}\) of vertices that give a non-zero contribution satisfy
Given \(\varvec{y}\) satisfying (6.27), define \(\varvec{\rho }\) to be the collection of vectors
Each \(\rho _{j}\) satisfies \(\Vert \rho _{j}\Vert _{\infty }\le 1\). The sum over \(\varvec{y}\) in (6.18) can be replaced by a sum over \(y_{i}\) for \(i=2,4,\ldots , 2m-2\) and a sum over the possible \(\varvec{\rho }\). Formally, letting \(\pi ^{(m)}=\pi ^{(m)}_{z,\kappa }\), we re-express (6.18) as
where the sum over \(\varvec{y}'\) is over tuples \((y_{2},y_{4},\ldots , y_{2m-2})\) and this defines the terms \(\pi ^{(m)}_{\varvec{y}',\varvec{\rho }}(x)\) as the contributions to (6.18) with the vertices \(y_{i}\) determined by \(\varvec{y}'\) and \(\varvec{\rho }\); we will shortly give an explicit formula for the \(\pi ^{(m)}_{\varvec{y}',\varvec{\rho }}\). We have abused notation in (6.29), but the bold subscripts will ensure that \(\pi ^{(m)}_{\varvec{y}',\varvec{\rho }}\) is distinguished from \(\pi ^{(m)}_{z,\kappa }\) in what follows.
We will now show the proposition follows from the estimate
for a constant \(C>0\) independent of \(\beta \). Equation (6.30) is uniform in \(\varvec{\rho }\), so with (6.29) it implies
where \(C'\) can be taken to be \(C (1+(3^{d}-1)\kappa ) (1+\kappa )^{2k_{0}}\). The factor of \((1+\kappa )^{2k_{0}}\) is from the prefactor in (6.29). The factor of \((1+(3^{d}-1)\kappa )\) arises as (i) each \(\rho _{i}\) has \(3^{d}-1\) non-zero possibilities, (ii) each i with \(\Vert \rho _{i}\Vert _{\infty }=1\) carries a factor of \(\kappa \) from \(r_{\kappa }(\rho _{i})\), and (iii) \(r_{\kappa }(o)=1\). Summing (6.31) over \(m\ge 2\) and combining it with the bounds (6.25) and (6.26) for \(m=1\) implies the proposition. The dependence of \(\beta \) in the proposition is on d alone because \(\kappa \le \min \{\kappa _{0},\beta \}\) by hypothesis, so \(C'\) depends only on the dimension d.
The remainder of the proof establishes (6.30), and for this we need an explicit formula for \(\pi ^{(m)}_{\varvec{y}',\varvec{\rho }}(x)\). Fix \(\varvec{\rho }\), let \(H=H_{z,\kappa }\), \(G=G_{z,\kappa }\), \(r=r_{\kappa }\), and \(y_{0}=o\). Recall that \(\mathcal {T}_{a}f(x)=f(x-a)\) for \(f:\mathbb {Z}^{d}\rightarrow \mathbb {R}\) and \(x,a\in \mathbb {Z}^{d}\). This yields
where the sum is over \(y_{2},\ldots , y_{2m-2}\).
Diagrammatically, see Fig. 10, Equation (6.32) has exactly the form of a self-avoiding walk diagrammatic bound [4], but where the two-point functions G, H have been replaced with their translates. Our estimates for G and H imply there is an \(a= a(d)\) such that
since \(\left| \left| \left| x+\rho \right| \right| \right| /\left| \left| \left| x\right| \right| \right| \) is uniformly bounded above when \(\Vert \rho \Vert _{\infty }\le 1\). Thus, the two-point functions \(\mathcal {T}_{\rho }G\) and \(\mathcal {T}_{\rho }H\) satisfy, up to a constant depending only on d, the same estimates as do G and H.
The remainder of the proof is standard in lace expansion analyses, and hence we will be somewhat brief. See, e.g., [8, proof of Prop. 1.8(a)] for more details.
Define \(\tilde{G}\) and \(\tilde{H}\) to be the upper bounds on G and H given by the right-hand sides of Equations (6.33) and (6.34). Let
With these definitions, we obtain
where in the case \(m=2\) we have degraded the bound slightly by using the estimate \(H\le G\). By (6.33) and (6.34) there is a constant \(c'=c'(d)>0\) such that
Define
When \(d>4\), \(\bar{\mathcal {S}}\) is finite by an elementary convolution estimate [8, Proposition 1.7]. By an induction on m using (6.36) it can be shown [8, p. 381-382] that this implies there is a \(C=C(d)\) such that
which proves Equation (6.30). \(\square \)
Proof of Theorem 2.3
To prove Theorem 2.3, it suffices to verify that there is a \(\kappa _{0}\) such that, if \(\kappa \le \kappa _{0}\), the hypotheses of Sect. A.2 on D, \(G_{z,\kappa }\), and \(\Pi _{z,\kappa }\) are satisfied.
Hypothesis A.1 is trivially satisfied. Hypothesis A.3 is satisfied for \(\kappa \le \kappa _{0}(L)\) for some \(\kappa _{0}(L)\) by Theorem 2.1 which ensures the critical point exists, and Proposition 5.6, which ensures the divergence of the susceptibility.
We now verify the monotonicity hypothesis, (ii), and (iii) of Hypothesis A.4. Since \(G_{z,\kappa }(x)\) is an absolutely convergent power series with positive coefficients when \(z<z_{c}\), it is monotone and continuous for \(z<z_{c}\). The exponential decay hypothesis is provided by Lemma 5.5.
To verify (i) of Hypothesis A.4, let \(z_{0}=(1+\kappa )^{-2(d-1)}\). When \(z\le z_{0}\),
This implies \(G_{z_{0},\kappa }(x)\le S_{1}(x)\), as \(S_{1}(x)\) is clearly an upper bound for the SAW two-point function.
For any D, Hypothesis A.5 follows for \(G_{z,\kappa }\) by Proposition 6.8 when \(\kappa \) is small enough, with \(\beta _{0}\) uniform in \(\kappa \). Thus, for \(\kappa \le \kappa _{0}(L_{0})\), with \(L_{0}\) the constant of Theorem A.6, we can apply Theorem A.6 by the discussion of Sect. A.4. This proves the theorem. \(\square \)
Notes
Note that our definition of \(c_{n}\) involves D, i.e., we are enumerating weighted self-avoiding walks.
References
Ueltschi, D.: A self-avoiding walk with attractive interactions. Probab. Theory Relat. Fields 124(2), 189–203 (2002)
den Hollander, F.: Random Polymers. Lecture Notes in Mathematics, vol. 1974. Springer-Verlag, Berlin (2009)
Bauerschmidt, R., Duminil-Copin, H., Goodman, J., Slade, G.: Lectures on self-avoiding walks, In: Probability and statistical physics in two and more dimensions. Clay Mathematics Proceedings, vol. 15, pp. 395–467. American Mathematical Society, Providence, RI (2012)
Slade, G.: The Lace Expansion and Its Applications. Lecture Notes in Mathematics, vol. 1879. Springer-Verlag, Berlin (2006)
Steele, J.M.: Probability theory and combinatorial optimization. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1997)
Madras, N., Slade, G.: The self-avoiding walk. Modern Birkhäuser Classics, Birkhäuser/Springer, New York (2013). Reprint of the 1993 original
Hammersley, J.M., Welsh, D.J.: Further results on the rate of convergence to the connective constant of the hypercubical lattice. Quart. J. Math. 13(1), 108–110 (1962)
Hara, T., van der Hofstad, R., Slade, G.: Critical two-point functions and the lace expansion for spread-out high-dimensional percolation and related models. Ann. Probab. 31(1), 349–408 (2003)
Hammond, A.: An upper bound on the number of self-avoiding polygons via joining. Ann. Probab. 46(1), 175–206 (2018)
van der Hofstad, R., Slade, G.: A generalised inductive approach to the lace expansion. Probab. Theory Relat. Fields 122(3), 389–430 (2002)
Hara, T., Slade, G.: On the upper critical dimension of lattice trees and lattice animals. J. Stat. Phys. 59(5–6), 1469–1510 (1990)
Sakai, A.: Lace expansion for the Ising model. Commun. Math. Phys. 272(2), 283–344 (2007)
Helmuth, T.: Loop-weighted walk. Ann. Inst. Henri Poincaré D 3(1), 55–119 (2016)
van der Hofstad, R., Holmes, M.: An expansion for self-interacting random walks. Braz. J. Probab. Stat. 26(1), 1–55 (2012)
Bauerschmidt, R., Slade, G., Wallace, B.C.: Four-dimensional weakly self-avoiding walk with contact self-attraction. J. Stat. Phys. 167(2), 317–350 (2017)
Pétrélis, N., Torri, N.: Collapse transition of the interacting prudent walk. Ann. Inst. Henri Poincaré D 5(3), 387–435 (2018)
Hardy, G. H., Ramanujan, S.: Asymptotic formulæ for the distribution of integers of various types [Proceedings of the London Mathematical Society (2) 16 (1917) pp. 112–132]. In: Collected papers of Srinivasa Ramanujan, pp. 245–261, AMS Chelsea Publising, Providence, RI (2000)
Aizenman, M.: Geometric analysis of \(\varphi ^{4}\) fields and Ising models. I, II. Commun. Math. Phys. 86(1), 1–48 (1982)
Brydges, D., Spencer, T.: Self-avoiding walk in \(5\) or more dimensions. Commun. Math. Phys. 97(1–2), 125–148 (1985)
Acknowledgements
The authors would like to thank both referees for their critiques and comments, which have lead to a significantly improved article. T.H. would like to thank Gordon Slade and Remco van der Hofstad for encouraging discussions. A.H. is supported by NSF grant DMS-1512908. The majority of this work was carried out while T.H. was supported by an NSERC postdoctoral fellowship at UC Berkeley; additional support was provided by EPSRC Grant EP/P003656/1.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix A: Gaussian asymptotics
Appendix A: Gaussian asymptotics
This appendix reviews [8, Theorem 1.2], which derives Gaussian asymptotics for critical two-point functions. Our motivation is that the presentation in [8] is, at places, dependent on the particular models being studied. The proofs, however, apply essentially verbatim to other models. Our review axiomatizes sufficient assumptions for models similar to self-avoiding walk. We indicate where these assumptions are used in proofs, but omit the portions of the proofs that purely replicate [8]. We emphasise that the result and techniques are those of [8], and our presentation is primarily for the benefit of the reader who is not familiar with [8].
1.1 Setup
Let \(\mathbb {R}_{\ge 0}\) denote the non-negative reals. For \(z\in \mathbb {R}_{\ge 0}\), \(G_{z}:\mathbb {Z}^{d}\rightarrow \mathbb {R}_{\ge 0}\), \({\tilde{\Pi }}_{z}:\mathbb {Z}^{d}\rightarrow \mathbb {R}\), and D a probability distribution on \(\mathbb {Z}^{d}\), we consider the convolution equation
We will further assume that \(G_{z}\), \({\tilde{\Pi }}_{z}\), and D are all \(\mathbb {Z}^{d}\)-symmetric, and that \(G_{z}(x)\) is a power series in z with non-negative coefficients. We will see in Section A.4 that the analysis of (A.1) also applies to the convolution equation derived for \(\kappa \)-ASAW in the main body of the text.
The critical point\(z_{c}\) is \(z_{c} = \sup \{z\in \mathbb {R}_{\ge 0} \mid \chi (z)<\infty \}\), where the susceptibility\(\chi (z)\) is defined by
1.2 Hypotheses and Theorem
Hypothesis A.1
Assume that D is a spread-out step distribution as defined in Definition 1.
Let \(X_{n}\) be a discrete time simple random walk with step distribution D. Let \(\sigma ^{2} = \sum _{x\in \mathbb {Z}^{d}}D(x)\Vert x\Vert ^{2}_{2}\). Note that \(\sigma ^{2}\) is comparable to the spread-out parameter \(L^{2}\). The non-interacting two-point function\(S_{\mu }\) is defined by
An important consequence of the form of D is the following proposition. Let \(a_{d} :=\frac{d\Gamma (d/2-1)}{2\pi ^{d/2}}\), where \(\Gamma \) is Euler’s gamma function.
Proposition A.2
([8, Prop. 1.6]) Suppose \(d>2\) and Hypothesis A.1 holds. For L sufficiently large, \(\alpha >0\), \(\mu \le 1\), and \(x\in \mathbb {Z}^{d}\),
The implicit constants may depend on \(\alpha \), but not on L.
Note that, for fixed d, the leading coefficient in (A.5) is proportional to \(L^{-2}\). The next two hypotheses deal with the critical point and behaviour of \(G_{z}\) for \(z_{0}\le z<z_{c}\), where \(z_{0}>0\) is a chosen value of the parameter z.
Hypothesis A.3
The critical point \(z_{c}\) satisfies \(z_{0}<z_{c}<\infty \). The susceptibility specified by (A.2) diverges as the critical point is approached from below: \(\lim _{z\uparrow z_{c}}\chi (z)=\infty \).
Hypothesis A.4
\(G_{z}\) is well-defined, not identically zero, and monotone increasing in z. For \(z_{0}\le z<z_{c}\) and for each \(x\in \mathbb {Z}^{d}\),
-
(i)
\(G_{z_{0}}(x)\le S_{1}(x)\),
-
(ii)
\(G_{z}(x)\) is continuous for \(z\in \left[ z_{0},z_{c}\right) \), and
-
(iii)
for \(t>0\) and \(z\in \left[ z_{0},z_{c}-t\right) \) there are constants \(c(t),C(t)>0\) such that
$$\begin{aligned} G_{z}(x)\le C(t)e^{-c(t)\left| \left| \left| x\right| \right| \right| }. \end{aligned}$$(A.6)
The most substantial hypothesis is the next one.
Hypothesis A.5
Assume
Suppose also that \(z_{0}\le z\le 2\). If \(\beta <\beta _{0}\), there is a constant \(c=c(d)>0\) such that
Theorem A.6
([8, Theorem 1.2]) Assume D, \(G_{z}\), and \({\tilde{\Pi }}_{z}\) satisfy the hypotheses of Section A.2. Choose \(0<\alpha <2\). Let \(\beta _{0}\) be the constant of Hypothesis A.5.
There is an \(L_{0}(d,\alpha ,\beta _{0})\) such that, for \(L\ge L_{0}\), the function \(G_{z_{c}}:\mathbb {Z}^{d}\rightarrow \mathbb {R}\) is well-defined, and there is an \(A>0\) such that
The implicit constants are uniform in x and L. The values of \(z_{c}\) and A are \(1+O(L^{\alpha -2})\).
1.3 Proof
The next proposition is the heart of the analysis. In what follows we assume the hypotheses of Theorem A.6; in particular, \(\beta _{0}\) is given.
Proposition A.7
Fix \(\alpha >0\). There is an \(L_{0}=L_{0}(\beta _{0},d,\alpha ,z_{0})\) such that, for \(L\ge L_{0}\),
and \(z_{c}\le 1 + O(L^{-2+\alpha })\).
Lemma A.8
(Lemma 2.1 [8]) Let \(f:[z_{1},z_{c})\rightarrow \mathbb {R}\), and \(a\in (0,1)\). Suppose
-
(i)
f is continuous on \([z_{1},z_{c})\),
-
(ii)
\(f(z_{1})\le a\), and
-
(iii)
for \(z\in [z_{1},z_{c})\) the inequality \(f(z)\le 1\) implies the inequality \(f(z)\le a\).
Then \(f(z)\le a\) for all \(z\in [z_{1},z_{c})\).
Proof of Proposition A.7
The proof is essentially that in [8]. We present the steps in which our hypotheses, as opposed to model-specific facts, are used.
Note that it suffices to prove that (A.10) holds for \(\alpha < \frac{1}{2}\), as the right-hand side is increasing in \(\alpha \). By Hypothesis A.4 and the monotone convergence theorem, it is enough to prove this for all \(z_{0}<z<z_{c}\).
Let K be the optimal constant for the error bound in Proposition A.2:
and note K is finite by (A.4). Define
and let \(g(z) = \sup _{x\ne o}g_{x}(z)\). To prove (A.10), we will use Lemma A.8 with \(f(z) = \max \{g(z),\frac{z}{2z_{0}}\}\), \(z_{1}=z_{0}\), and \(a\in \left( \frac{1}{2},1\right) \) arbitrary. The claim that \(z_{c}=1+O(L^{-2+\alpha })\) will be established in the course of the argument.
Claim
Hypothesis (i) of Lemma A.8 holds.
Proof
For \(x\in \mathbb {Z}^{d}\), \(g_{x}(z)\) is continuous on \([z_{0},z_{c})\) by Hypothesis A.4. It suffices to show \(\sup _{x\ne o}g_{x}(z)\) is continuous on \([z_{0},z_{c}-t)\) for arbitrarily small \(t>0\).
Fix \(t>0\), and let \(z\in [z_{0},z_{c}-t)\). By Hypothesis A.4, \(g_{x}(z)\) decays exponentially in \(\Vert x\Vert _{2}\) with decay rate independent of z. Therefore, \(\sum _{x\in \mathbb {Z}^{d}}g_{x}(z)\) converges exponentially fast with rate independent of z. It follows that the supremum of \(g_{x}(z)\) occurs on \(B_{R}(o)\), the ball of radius R about the origin, for some \(R=R(L)>0\). This proves \(\sup _{x\ne o}g_{x}(z)\) is a continuous function of \(z\in [z_{0},z_{c}-t)\) since the supremum of a finite set of continuous functions is continuous. \(\square \)
Claim
Hypothesis (ii) of Lemma A.8 holds.
Proof
By Hypothesis A.4 and the definition of K, \(g_{x}(z_{0})\le \frac{1}{2}\) for all x. Since \(a>\frac{1}{2}\), this proves the claim. \(\square \)
Claim
Hypothesis (iii) of Lemma A.8 holds.
Proof
Fix \(z_{0}<z<z_{c}\) and suppose \(f(z)\le 1\). Then z is at most \(2z_{0}\), and
Let \(\beta = 2z_{0}KL^{-2+\alpha }\). By Hypothesis A.5, when \(L^{-2+\alpha }\) is sufficiently small there is a \(c>0\) such that
By Hypothesis A.4, \(G_{z}\) is not identically zero. Thus \(\chi (z)>0\), and the sum of (A.1) over all \(x\in \mathbb {Z}^{d}\) can be rearranged to give
By (A.12), \(\Vert {\tilde{\Pi }}_{z}(x)\Vert _{1}<1\) for L large enough. This implies the numerator, and hence the denominator, of (A.13) is strictly positive. Since \(f(z)\le 1\), this implies that
Thus \(\frac{z}{2}\) is bounded above by a for \(a\in \left( \frac{1}{2},1\right) \), provided that L is large enough.
What remains is to prove \(g(z)\le a\) for \(a\in \left( \frac{1}{2},1\right) \) when L is large enough. This exactly follows the presentation in [8, p. 364], and hence we omit it. \(\square \)
By Hypothesis A.4 this proves the desired bounds, as we have proven that \(f(z)\le a\) for \(z_{0}\le z<z_{c}\). The bound on \(z_{c}\) follows from (A.14), which holds as it was derived under the hypothesis that \(f(z)\le 1\). \(\square \)
Proof of Theorem A.6
This follows [8, Theorem 1.2]. The only model specific step in the cited proof is showing that an auxiliary parameter \(\mu _{z}\) increases to \(\mu _{z_{c}}=1\) as \(z\uparrow z_{c}\). We define this parameter below and show that it takes the desired value by Hypothesis A.3.
By (A.12), \({\tilde{\Pi }}_{z}(x)\) has a finite second moment when L is large enough. It therefore makes sense to define
Equation (A.12) implies \(\lambda _{z}\rightarrow 1\) as \(L\rightarrow \infty \) uniformly in \(z\in \left[ z,z_{c}\right] \). By Equation (A.13) and Hypothesis A.3, as \(z\uparrow z_{c}\), the quantity in brackets in (A.16) tends to zero. Thus, \(\mu _{z_{c}}\uparrow 1\) as \(z\uparrow z_{c}\). \(\square \)
1.4 Other convolution equations
Consider the equation
If \(\Pi \) satisfies Hypothesis A.5, it is possible to manipulate (A.17) into the form (A.1). To see this, rewrite (A.17) as
where, in the second equality, we have used (A.17) to rewrite the term in parentheses, and the subscripts z have been omitted. Rewriting the last factor of G using (A.17) yields
where \(A^{*k}\) is the k-fold autoconvolution of A. Iterating this yields (A.1) with
since \(\lim _{n\rightarrow \infty }\Pi ^{*n}=0\) under the assumption that \(\Pi \) satisfies Hypothesis A.5. Finally, [8, Proposition 1.7] implies that, if \(\Pi _{z}\) satisfies Hypothesis A.5, then \({\tilde{\Pi }}_{z}\) defined by (A.18) satisfies Hypothesis A.5, for possibly different constants. The change in constants depends only on d. See [8, Section 4.1] for a further discussion of this point. Thus to apply Theorem A.6 to the convolution equation (A.17), it suffices to verify the hypotheses of Section A.2 for \(G_{z}\), D, and \(\Pi \).
Rights and permissions
About this article
Cite this article
Hammond, A., Helmuth, T. Self-attracting self-avoiding walk. Probab. Theory Relat. Fields 175, 677–719 (2019). https://doi.org/10.1007/s00440-018-00898-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-018-00898-7
Keywords
- Self-interacting random walk
- Self-attracting walk
- Self-avoiding walk
- Linear polymers
- Lace expansion
- Critical phenomena
- Hammersley-Welsh argument