{'fraction_non_alphanumeric': 0.05141169861116555, 'fraction_numerical': 0.011419015142607037, 'mean_word_length': 3.77003614608002, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Glauber dynamics on trees:Boundary conditions and mixing time

We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics in the so-called Bethe approximation. Specifically, we show that spectral gap and the log-Sobolev constant of the Glauber dynamics for the Ising model on an n-vertex regular tree with plus-boundary are bounded below by a constant independent of n at all temperatures and all external fields. This implies that the mixing time is O(log n) (in contrast to the free boundary case, where it is not bounded by any fixed polynomial at low temperatures). In addition, our methods yield simpler proofs and stronger results for the spectral gap and log-Sobolev constant in the regime where there are multiple phases but the mixing time is insensitive to the boundary condition. Our techniques also apply to a much wider class of models, including those with hard-core constraints like the antiferromagnetic Potts model at zero temperature (proper colorings) and the hard--core lattice gas (independent sets).


Introduction
In this paper we will analyze the influence of boundary conditions on the Glauber dynamics for discrete spin models on a regular rooted tree. Although in what follows we will focus for simplicity on the well known Ising model, our techniques also apply to other models, not necessarily ferromagnetic and with hard-core constraints.
In the Ising model on a finite graph G = (V, E), a configuration σ = (σ x ) consists of an assignment of ±1-values, or "spins", to each vertex (or "site") of V . The probability of finding the system in configuration σ ∈ {±1} V ≡ Ω G is given by the Gibbs distribution where β ≥ 0 is the inverse temperature and h the external field. Boundary conditions can also be taken into account by fixing the spin values at some specified "boundary" vertices of G; the term free boundary is used to indicate that no boundary condition is specified.
In the classical Ising model, G = G n is a cube of side n 1/d in the d-dimensional Cartesian lattice Z d , and in this case the phase diagram in the thermodynamic limit G n ↑ Z d is quite well understood (see, e.g., [15,38] for more background).
While the classical theory focused on static properties of the Gibbs measure, in the last decade the emphasis has shifted towards dynamical questions with a computational flavor. The key object here is the Glauber dynamics, a (discrete-or continuous-time) Markov chain on the set of spin configurations Ω G in which each spin σ x flips its value with a rate that depends on the current configuration of the neighboring spins of x, and which satisfy the detailed balance condition w.r.t to the Gibbs measure µ G (see Section 2 for more details).
The Glauber dynamics is much studied for two reasons: firstly, it is the basis of Markov chain Monte Carlo algorithms, widely used in computational physics for sampling from the Gibbs distribution; and secondly, it is a plausible model for the actual evolution of the underlying physical system towards equilibrium. In both contexts, one of the central questions is to determine the mixing time, i.e., the time until the dynamics is close to its stationary distribution.
As is well known (see e.g. [36]), the approach to stationarity of a reversible Markov chain with Markov generator L and reversible measure π can be succesfully studied by analyzing two key quantities: the spectral gap and the logarithmic Sobolev constant of the pair (L, π) † . The first of these measures the rate of the exponential decay as t → ∞ of the variance Var π (e tL f ) computed with respect to the invariant measure π, while the second measures instead the rate of decay of the relative entropy of e tL f w.r.t π (see, e.g., [1]). Advances in statistical physics over the past decade have led to remarkable connections between these two quantities and the occurence of a phase transition (see, e.g., [40,30,29,9,28,26]). As an example, on finite n-vertex squares with free boundary in the 2-dimensional lattice Z 2 , when h = 0 and β is smaller than the critical value β c , the spectral gap and the logarithmic Sobolev constant are Ω(1) (i.e. bounded away from zero uniformly in n), while for β > β c they are both exponentially small in √ n.
One of the most interesting and difficult questions left open by the above and related results is the influence of boundary conditions on the spectral gap and the log-Sobolev constant when h = 0 and β > β c . It has been conjectured that, in the presence of an all-(+) boundary, the relaxation process is driven by the mean-curvature motion of interfaces separating droplets of the (−)-phase inside the (+)-phase, and therefore the mixing time should be polynomial in n (most likely n 2/d log n) [7,14]. In particular it has been argued that the spectral gap for the pure phases in high enough dimension should be Ω (1). Proving results of this kind has proved very elusive, † Unfortunately the definition of the logarithmic Sobolev constant is not constant in the literature. The ambiguity arises because there are two definitions, one the inverse of the other. The definition used in this paper is the one that puts the logarithmic Sobolev constant and the spectral gap on the same footing. and the only (presumably sharp) available bounds are upper bounds on the spectral gap and the logarithmic Sobolev constant [7].
In this paper we prove a strong version of the above conjecture in what is known in statistical physics as the Bethe approximation, namely when the lattice Z d is replaced by a regular tree. Among other results, we show that the spectral gap of the Glauber dynamics for the Ising model on a tree with a (+)-boundary condition on its leaves is Ω(1) at all temperatures and all values of the external field, and further that the same holds for the logarithmic Sobolev constant. Notice that, with a free boundary, β large and h = 0, both quantities tend to zero as 1/n a and the exponent a grows arbitrarily large as β → ∞ [3].
Ours is apparently the first result that quantifies the effect of boundary conditions on Glauber dynamics in an interesting scenario. We stress that, while the tree is simpler in many respects than Z d due to the lack of cycles, in other respects it is more complex due to the large boundary: e.g., it exhibits a "double phase transition," and the critical field at low temperature is non-zero (see below). In the next subsection, we briefly describe the Ising model on trees before stating our results in more detail.

The Ising model on trees
Fix b ≥ 2 and let T b denote the infinite b-ary tree. The Ising model on T b is known [15,24] to have a phase diagram in the (h, β) plane quite different from that on the cubic lattice Z d (see Fig. 1), and has recently received a lot of attention as the canonical example of a statistical physics model on a "non-amenable" graph (i.e., one whose boundary is of comparable size to its volume) -see, e.g., [6,19,13,37,22,3,5].  Let us first discuss the behavior on the line h = 0. There is a first critical value β 0 = 1 2 log b+1 b−1 , marking the dividing line between uniqueness and non-uniqueness of the Gibbs measure. Then, in sharp contrast to the model on Z d , there is a second critical point β 1 = 1 2 log √ b+1 √ b−1 which is often referred to as the "spin-glass critical point" [10]. This second critical point is such that, in the "intermediate temperature" region β 0 < β ≤ β 1 , the (+)and (−)-boundary conditions exert arbitrarily long-range influence on the spin at root of the tree and hence give rise to different Gibbs measures, but "typical" boundary conditions (i.e., chosen from the infinite volume Gibbs measure with free boundary) do not. Another way to phrase this peculiar behavior is that the Gibbs measure constructed via a free boundary is extremal for all β ≤ β 1 (see [6,19,20,3] and also [13,33,34] for an analysis in the context of "bit reconstruction problems" for noisy data transmission).
Let us now examine what happens when an external field h is added to the system. It turns out that for all β > β 0 , there is a critical value h = h c (β) > 0 of the field such that the Gibbs measure is not unique when |h| ≤ h c , and is unique when |h| > h c . (When β ≤ β 0 the Gibbs measure is unique for all h, and h c is defined to be zero.) In the presence of a (+)-boundary, the Ising model on the tree with external field h = −h c is rather analogous to the classical case of Z d with zero field. Both models share the following two properties: firstly, the Gibbs measure is sensitive to the choice of boundary condition, and secondly, adding an arbitrarily small negative field causes the Gibbs measure to become insensitive to the boundary condition (i.e., unique in the thermodynamic limit).
Finally we remark that the concentration properties of the Gibbs measure for β > β 0 , h ≥ −h c and (+)-boundary are very different from those on Z d . In the latter case, along the line of first order phase transition, the (negative) large deviations for the bulk magnetization are related to the appearance of a Wulff droplet of the opposite phase and are depressed by a negative exponential in the surface of the droplet (see, e.g., [11]). Here instead, for any value of (β, h) they are always depressed by a negative exponential in the volume of the excess negative spins (the phenomenon of "rigidity of the critical phases" [5]).
The Glauber dynamics for the Ising model on trees has also been studied. In a recent paper [3], it is shown that the associated spectral gap (see (7) for a precise definition) with zero external field and free boundary on a complete b-ary tree T with n vertices is Ω(1) at high and intermediate temperatures (i.e., when β < β 1 ) ‡ . Moreover, at the critical point β = β 1 the same spectral gap is bounded above by c/ log n, and as soon as β > β 1 it becomes smaller than c/n a(β) , with a(β) ↑ ∞ as β → ∞. Thus the critical point β = β 1 is reflected in the dynamics by an abrubt jump in the behavior of the spectral gap as a function of the size of the tree T . Finally, also in [3], it is proved that the spectral gap for arbitrary fixed β, h and boundary condition can never shrink to zero faster than an inverse polynomial in n. Again such a result should be compared to the lattice case where it is known that the spectral gap for a cube with n sites can be exponentially small in the surface n (d−1)/d .

Main results and techniques
Our first main result is a detailed analysis of the spectral gap of the Glauber dynamics in different regions of the phase diagram. The main novelty here is that we are able for the first time to prove a sharp result in the region where the spectral gap is highly sensitive to the boundary condition. Theorem 1.1 In both of the following situations, the spectral gap of the Glauber dynamics on a complete b-ary tree T with n vertices is Ω(1): (i) the boundary condition is arbitrary, and either β < β 1 (with h arbitrary), or |h| > h c (β) (with β arbitrary); (ii) the boundary condition is (+) and β, h are arbitrary.
Remark: On Z d not much is known about the spectral gap when β > β c , h = 0 and the boundary condition is (+), the notable exception being that of Z 2 where it has been recently proved [7] that the spectral gap in a square with n sites shrinks to zero at least as 1/ √ n (neglecting logarithmic corrections). The best known lower bounds are significantly weaker [28]. In high enough dimensions (d ≥ 3) it has been conjectured (see [14] and [7]) that the spectral gap should stay bounded away from zero uniformly in n. The above theorem can be looked upon as evidence in favor of this conjecture.
In our second main result we extend our analysis to the more delicate and difficult logarithmic Sobolev constant (see (7) for a precise definition). ‡ Actually the arguments in [3] prove that the gap is Ω(1) for any β < β1, arbitrary boundary condition and any external field. Their argument, together with some monotonicity properties specific to the Ising model [35], implies a mixing time of O(log n). Thus, although for β0 < β < β1 there exist several Gibbs measures, the mixing time of the Glauber dynamics is insensitive to the boundary condition. Theorem 1.2 In the same situations as in Theorem 1.1, the logarithmic Sobolev constant of the Glauber dynamics on a complete b-ary tree T with n vertices is Ω(1).
As a corollary we obtain that, in the situations of Theorems 1.1 and 1.2, the Glauber dynamics mixes (in a very strong sense) in time O(log n).

Remarks:
(i) In Z d with (+)-boundary condition, β large and zero external field the logarithmic Sobolev constant in a cube with n sites is always smaller than n −2/d , neglecting logarithmic corrections [7], in agreement with heuristic predictions based on mean-curvature motion of phases interfaces.
(ii) We also prove (see Theorem 5.7) an additional result which shows that, for an arbitrary nearest-neighbor spin system on a tree, as soon as the spectral gap is Ω(1) then the logarithmic Sobolev constant cannot shrink faster than (c log n) −1 . This means that, even when a constant lower bound is known for the gap but not for log-Sobolev, one can deduce a mixing time of O((log n) 2 ). While we do not require this fact to derive the results of this paper, we believe it may be of interest for other models on trees.
In order to better appreciate Theorem 1.2, one should keep in mind that for general finite range, translation invariant, compact spin models on Z d , if there exists an infinite volume Gibbs measure µ with a positive logarithmic Sobolev constant, then the system is necessarily in the uniqueness region and µ has exponentially decaying correlations [41] § . We also recall (see, e.g., [25]) that when the log-Sobolev constant is bounded away from zero one can derive very strong (Gaussianlike) concentration properties of the corresponding Gibbs measure, such as those proved in [5].
We now proceed to sketch some of our techniques and point out the main technical innovations. Our analysis of both the log-Sobolev constant and the spectral gap rests on certain spatial mixing conditions that can be stated as follows. Let f be a function of the spin configuration that does not depend on the spins in the first ℓ levels of the tree starting from the root r, and let µ(f | σ r ) be the projection of f onto the spin σ r at the root. If the variance (respectively, the entropy) under the Gibbs measure µ of µ(f | σ r ) decays fast enough with the depth ℓ, then we show by a unified argument how to deduce a bound of Ω(1) on the spectral gap (respectively, the log-Sobolev constant). Crucially, in contrast to previous approaches we do not require the above decay to hold in arbitrary environments, but only for the Gibbs measure µ under consideration. This opens up the possibility that the condition holds for some boundary conditions and not for others (with the same values of temperature and external field). We also prove the converse, thus showing the that our mixing conditions are in fact equivalent to the required bounds on the spectral gap and log-Sobolev constants.
This analysis has several advantages over previous ones [3,35]: it is more direct, applies also when there is an external field, and applies to general nearest-neighbor spin systems on trees.
The second main ingredient of the paper is establishing the above spatial mixing conditions in the scenarios of interest described in the above two theorems. This is done via a rather simple and novel coupling technique for the case of the variance. Such a technique provides, along the way, a new and really elementary proof of the extremality of the Gibbs measure with free boundary below β 1 . Surprisingly, we are also able to exploit the same coupling technique (via strong concentration properties of the Gibbs measure) to establish the entropy mixing condition. Thus in terms of the coupling analysis our conditions for variance and entropy mixing are essentially the same. § A close look at the proof in [41] reveals that the same is true for any infinite, locally finite, bounded degree graph such that the volume of any ball of radius ℓ grows sub-exponentially in ℓ.
Finally, we mention that our results actually hold (with suitable modifications) for a much wider class of spin systems on trees than just the Ising model, including the Potts model and models with hard constraints such as the zero-temperature antiferromagnetic Potts model (proper colorings) and the hard-core lattice gas model (independent sets). We briefly outline some of these extensions at the end of the paper; full details can be found in a companion paper [31].
The remainder of the paper is organized as follows. In Section 2 we give some basic definitions and notation. Then in Section 3 we define the spatial mixing conditions and relate them to the spectral gap and log-Sobolev constant. The mixing conditions in the scenarios of interest for the spectral gap and the log-Sobolev constant are verified in Sections 4 and 5 respectively. Finally, in Section 6 we mention some extensions of our results to other models of interest. The proofs of some technical lemmas omitted from the main text are collected in a supplement, Section 7.

Acknowledgments
F. Martinelli would like to thank the Miller Institute, the Dept. of Statistics and the Dept. of EECS of the University of California at Berkeley for financial support and warm hospitality. We also wish to thank E. Mossel and Y. Peres for very interesting discussions about reconstruction on trees and related topics.

Gibbs distributions on trees
For b ≥ 2, let T b denote the infinite, rooted b-ary tree (in which every vertex has b children). We will be concerned with (complete) finite subtrees T of T b ; if T has depth m then it has n = (b m+1 − 1)/(b − 1) vertices, and its boundary ∂T consists of the children (in T b ) of its leaves, i.e., |∂T | = b m+1 . We identify subgraphs of T with their vertex sets, and write E(A) for the edges within a subset A, and ∂A for the boundary of A (i.e., the neighbors of A in (T ∪ ∂T ) \ A).
Fix an Ising spin configuration τ on the infinite tree T b . We denote by Ω τ T the set of (finite) spin configurations σ ∈ {±1} T ∪∂T that agree with τ on ∂T ; thus τ specifies a boundary condition on T . Usually we abbreviate Ω τ T to Ω. For any η ∈ Ω and any subset A ⊆ T , we denote by µ η A the Gibbs distribution over Ω conditioned on the configuration outside A being η: i.e., if σ ∈ Ω agrees with η outside A then where β is the inverse temperature and h the external field. We define µ η A (σ) = 0 otherwise. In particular, when A = T , µ τ T is simply the Gibbs distribution on the whole of T with boundary condition τ ; we abbreviate µ τ T to µ. For a function f : A . It will be convenient to view µ η A (f ) as a function of η, defined by µ A (f )(η) = µ η A (f ), the conditional expectation of f . Note that µ A (f ) is a function from Ω to R but depends only on the configuration outside A. We write Var η for the variance and entropy of f respectively w.r.t. µ η A . Note that Var η A (f ) = 0 iff, conditioned on the configuration outside A being η, f does not depend on the configuration inside A. The same holds for Ent η A (f ). In case A = T we use the abbreviations µ(f ), Var(f ) and Ent(f ).
We record here some basic properties of variance and entropy that we use throughout the paper: This equation expresses a decomposition of the variance into the local conditional variance in B and the variance of the projection outside B.
(ii) If A = i A i for disjoint A i , and the Gibbs distribution µ η A is the product of its marginals over the A i , then for any function f , (3) (iii) For any two subsets A, B ⊆ T such that (∂A) ∩ B = ∅, and for any function f , Properties (ii) and (iii) are consequences of the fact that variance w.r.t. a fixed measure is a convex functional.
All three properties (i), (ii) and (iii) also hold with Var replaced by Ent.

The Glauber dynamics
The Glauber dynamics on T with boundary conditions τ is the continuous time Markov chain on Ω = Ω τ T with Markov generator L ≡ L τ T given by where σ x denotes the configuration obtained from σ by flipping the spin at the site x, and c x (σ) denotes the flip rate at x. Although all our results apply to any choice of finite-range, uniformly positive and bounded flip rates satisfying the detailed balance condition w.r.t. the Gibbs measure, for simplicity in the sequel we will work with a specific choice known as the heat-bath dynamics: It is a well-known fact (and easily checked) that the Glauber dynamics is ergodic and reversible w.r.t. the Gibbs distribution µ = µ τ T , and so converges to the stationary distribution µ. The rate of convergence is often measured using two concepts from functional analysis: the spectral gap and the logarithmic Sobolev constant. For a function f : Ω → R, define the Dirichlet form of f associated with the generator L by (The l.h.s. here is the general definition for any choice of the flip rates c x ; the last equality holds when specializing to the case of the heat-bath dynamics.) The spectral gap c gap (µ) and the logarithmic Sobolev constant c sob (µ) of the chain are then defined by where the infimum in each case is over non-constant functions f . As is well known, these two quantities measure the rate of exponential decay as t → ∞ of the variance and relative entropy respectively (see, e.g., [36]). The quantity c gap also has a natural interpretation as the smallest positive eigenvalue of −L.
We make the following important note. When discussing the asymptotics of c sob (or c gap ) for a fixed boundary condition τ , we think of the infinite sequence of Gibbs distributions {µ τ T }, where T ranges over all finite complete subtrees of T b . In particular, when we say that c sob (µ) = c sob (µ τ T ) = Ω(1) we mean that there exists a finite constant C > 0 such that for every T (or equivalently, for every µ ∈ {µ τ T }), c sob (µ) ≥ 1/C. We close this section by recalling some well-known relationships between the above constants and certain notions of mixing time of the Glauber dynamics. Define h σ t (η) = Pt(σ,η) µ(η) , where P t (σ, η) := e tL (σ, η) is the transition kernel at time t. Then, for 1 ≤ p ≤ ∞, define where f p denotes the L p (Ω, µ) norm of f . The time T 1 is usually called simply the mixing time of the chain. Standard results relating T p to the spectral gap and log-Sobolev constant (see, e.g., [36]), when specialized to the Glauber dynamics, yield the following: where µ = µ τ T and C 1 , C 2 are constants depending only on b, β and h.
Finally, we note that our choice of the heat-bath dynamics is not essential. Since changing to any other reversible local update rule (e.g., the Metropolis rule) affects c sob and c gap by at most a constant factor, our analysis applies to any choice of Glauber dynamics.

Spatial mixing conditions for spectral gap and log-Sobolev
In this section we define a certain spatial mixing condition (i.e., a form of weak dependence between the spin at a site and the configuration far from that site) for a Gibbs distribution µ, and prove that this condition implies that c gap (µ) = Ω(1). An analogous condition implies that c sob (µ) = Ω(1). Our spatial mixing conditions have two main advantages over those used previously: first, the conditions for the spectral gap and the log-Sobolev constant are identical in form, allowing a uniform treatment; second, and more importantly, they are measure-specific, i.e., they may hold for the Gibbs distribution induced by some specific boundary configuration while not holding for other boundary configurations. Hence, the conditions are sensitive enough to show rapid mixing for specific boundaries even though the mixing time with other boundaries is slow for the same choice of temperature and external field. We also note that the results of this section hold not just for the Ising model but for any nearest-neighbor interaction model on a tree.

Reduction to block analysis
Before presenting the main result of this section, we need some more definitions and background.
In what follows we will think of ℓ as a suitably large constant. By analogy with expression (6) for the Dirichlet form, let A straightforward manipulation (see, e.g., [28], keeping in mind that each site belongs to at most ℓ blocks) shows that c gap can be bounded as follows: As before, the infimum is taken over non-constant functions (and henceforth we omit explicit mention of this). The importance of (9) is that min η,x c gap (µ η B x,ℓ ) depends only on the size of B x,ℓ and β, but not on the size of T ; in fact, it is at least Ω(e −c(b,β)·ℓ ) [3]. Therefore, in order to show that c gap is bounded by a constant independent of the size of T , it is enough to show that, for some finite ℓ, Var(f ) ≤ const × D ℓ (f ) for all functions f . This is what we will show below, under the relevant spatial mixing condition. As a side remark, notice that inf f D ℓ (f ) Var(f ) is exactly the spectral gap of the Glauber dynamics based on flipping blocks B x,ℓ , rather than single sites x.
An identical manipulation yields an analogous bound for the log-Sobolev constant. For a non- Hence to bound c sob (µ) it suffices to show that, for some constant ℓ,

Spatial mixing
We are now ready to state our spatial mixing conditions, first for the variance and then for the entropy. For x ∈ T , write T x for the subtree rooted at x, and T x for T x \ {x}, the subtree T x excluding its root.

Definition 3.1 [Variance Mixing]
We say that µ = µ τ T satisfies VM(ℓ, ε) if for every x ∈ T , any η ∈ Ω τ T and any function f that does not depend on B x,ℓ , the following holds: Let us briefly discuss the above condition. Essentially, ε = ε(ℓ) gives the rate of decay with distance ℓ of point-to-set correlations. To see this, note that the l.h.s. Var η Tx [µ Tx (f )] is the variance of the projection of f onto the root x of T x , which is at distance ℓ from the sites on which f depends. It is also worth noting that the required uniformity in η in VM is not very restrictive: since the distribution µ η Tx depends only on the restriction of η to the boundary of T x , and since η ∈ Ω τ T (i.e., η agrees with τ on ∂T and therefore on the bottom boundary of T x ), the only freedom left in choosing η is in choosing the spin of the parent of x. Thus, VM is essentially a property of the distribution induced by the boundary condition τ . It is this lack of uniformity (i.e., the fact that we need not verify VM for other boundary conditions) that makes it flexible enough for our applications.
As the following theorem states, if VM(ℓ, ε) holds with ε ≈ 1 2ℓ , then we get a lower bound on c gap : In particular, if VM with the above parameters holds for some fixed ℓ and δ > 0, for all for some constants c, ϑ > 0 and all ℓ.

Remark:
The second part of the theorem was already proved in [3], where it was shown that for general nearest-neighbor spin systems on any bounded degree graph, if c gap (µ) is bounded independently of n then µ exhibits an exponential decay of point-to-set correlations (i.e., VM(ℓ, c exp(−ϑℓ)) holds for all ℓ). The authors of [3] posed the question of whether the converse is also true. Theorem 3.2 (which holds for general nearest-neighbor spin systems on a tree) answers this question affirmatively when the graph is a tree. In fact, as is apparent from the above theorem, the decay of point-to-set correlations on a tree is either slower than linear or exponentially fast.
The analogous mixing condition for entropy and the log-Sobolev constant is the following:

Definition 3.3 [Entropy Mixing]
We say that µ = µ τ T satisfies EM(ℓ, ε) if for every x ∈ T , any η ∈ Ω τ T and any non-negative function f that does not depend on B x,ℓ , the following holds: Before stating the analog of Theorem 3.2 relating c sob to EM, we need to define one more constant. Let p min = min x,s,η∈Ω τ T µ η Tx (σ x = s), where s ranges over {+, −}; i.e., p min is the minimum probability of any spin value at any site with any boundary condition. It is easy to see that p min ≥ 1 2 e −2β(b+|h|) , a constant depending only on b, β, h.
In order to prove Theorems 3.2 and 3.4 it is convenient to work with spatial mixing conditions that are somewhat more involved than VM and EM. The main difference is that we want to allow for functions that may depend on B x,ℓ (the first ℓ levels of T x ) and thus need to introduce a term for this dependency. The modified conditions express the property that the variance (entropy) of the projection of any function f onto the root x of T x can be bounded up to a constant factor by the local variance (entropy) of f in B x,ℓ , plus a negligible factor times the local variance (entropy) of f in T x . As the following lemma states, the modified conditions (with appropriate parameters) can be deduced from VM and EM.

Remark:
We note that with extra work, part (ii) of Lemma 3.5 can be improved to hold with ε ′ = c(p min )ε.
We give the weaker bound because it is simpler to prove while still enough for our applications.
Similar statements to those in Lemma 3.5 appeared in [4]. We defer our proof to Section 7.
We can now prove Theorems 3.2 and 3.4 by working with the modified spatial mixing conditions of Lemma 3.5.

Proof of Theorems 3.2 and 3.4:
Here we only prove the forward direction of both theorems. The reverse direction of Theorem 3.2 was proved in [3], as already mentioned above. The proof of the reverse direction of Theorem 3.4 is deferred to Section 7 because it uses machinery developed later in the paper.
The main step in the proof of the forward direction is to show the following claim: If for every x ∈ T , any η ∈ Ω τ T and any function f , then Var(f ) ≤ c δ · D ℓ (f ) for all f . The same implication holds when Var is replaced by Ent, D ℓ is replaced by E ℓ and the function f is restricted to be non-negative.
Observe that the hypothesis of Theorem 3.2 together with part (i) of Lemma 3.5 establishes the hypothesis of Claim 3.6 with c ≤ 3, and similarly, the hypothesis of Theorem 3.4 together with part (ii) of Lemma 3.5 establishes the hypothesis of Claim 3.6 (after the necessary replacement of symbols) with c ≤ 2.
It therefore suffices to prove Claim 3.6. We prove only the formulation with Var and D ℓ since the proof for the formulation with Ent and E ℓ is identical once we make the same replacements in the text of the proof. As will be clear below, the proof uses only properties which are common to both Var and Ent.
Consider an arbitrary function f : Ω → R. Our first goal is to relate Var(f ) to the projections Var η Tx [µ Tx (f )] for x ∈ T , so that we can apply the spatial mixing condition of the hypothesis. Recall that T has m + 1 levels, and define the increasing sequence (2) recursively, and the facts that Now a fundamental property of nearest-neighbor interaction models on a tree is that, given the configuration on T \ F i , the Gibbs distribution on F i becomes a product of the marginals on the subtrees rooted at the sites x ∈ F i \F i−1 . Using inequality (3) for the variance of a product measure, we therefore have that where in the second inequality we used the convexity of the variance as in (4). Notice that so far we have not used the spatial mixing condition in the hypothesis of Claim 3.6, but only a natural martingale structure induced by the tree. Let us denote the final sum in (11) by Pvar(f ). In order to bound c gap , we need to compare the projection terms Var Tx (µ Tx (f )) in Pvar(f ) with the local conditional variance terms in D ℓ (f ). For example, notice that if µ were the product of its single-site marginals then Var Tx (µ Tx (f )) ≤ µ Tx [Var x (f )] and c gap = 1. However, in general the variance of the projection on x may also involve terms which depend on other sites, and may lead to a factor that grows with the size of T x . We will use the spatial mixing condition in order to preclude the latter possibility. Specifically, we show that if for every x ∈ T , any η ∈ Ω τ T and any function g, then for every x ∈ T and η ∈ Ω, where we have abbreviated B x,ℓ to B x and ∂B x stands for the boundary of B x excluding the parent of x, i.e., the bottom boundary of B x . Notice that the last term in (12) is relevant only when x is at distance at least ℓ from the bottom of T . When x belongs to one of the ℓ lowest levels of T then T x = B x , and thus trivially Var η . Let us assume (12) for now and conclude the proof of the theorem. Applying (12) for every x and η, and using the hypothesis that ε = 1−δ ℓ and the fact that each site appears in at most ℓ blocks, we get and hence proving Claim 3.6. We now return to proving (12). Let g = µ Tx\(Bx∪ ∂Bx) (f ). Once we notice that µ Tx (f ) = µ Tx (g), we can use the spatial mixing assumption that precedes (12) to deduce where we used (4) for the second inequality. We will be done once we show that But (13) follows from a similar argument to that used earlier to show Var(f ) ≤ Pvar(f ), starting from the fact that g = µ F ′ k (f ), where the forests F ′ i are defined analogously to the F i earlier but restricted to the subtree T x , and k = height(x) − ℓ. We omit the details.
This concludes the proof of Claim 3.6, and thus of Theorems 3.2 and 3.4.

Verifying spatial mixing for the spectral gap
In this section, we will prove that the spectral gap of the Glauber dynamics is bounded in all of the situations covered by Theorem 1.1 in the Introduction. In light of Theorem 3.2, to bound the spectral gap it suffices to verify the Variance Mixing condition VM(ℓ, ε) with ε = (1 − δ)/2(ℓ + 1 − δ), for some constants ℓ, δ > 0 independent of the size of T . In fact, we will show it with the asymptotically tighter value ε = c exp(−ϑℓ): (ii) τ is the (+)-boundary condition, and β, h are arbitrary.

Remark:
The validity of VM, i.e, the decay of point-to-set correlations, is of interest independently of its implication for the spectral gap (an implication which is new to this paper): e.g., it is closely related to the purity of the infinite volume Gibbs measure and to bit reconstruction problems on trees [13]. In the special case of a free boundary and h = 0, part (i) of Theorem 4.1 was first proved in [6] via a lengthy calculation, which was considerably simplified in [19]. It was later reproved in [3] (for arbitrary boundary conditions) as a consequence of the fact that the spectral gap is bounded in this situation. An extension to general trees can be found in [13] and [20]. Our motivation for presenting another proof of part (i) (in addition to handling general fields h) is the simplicity of our argument compared with previous ones. As far as part (ii) is concerned, we are unaware of any previous results for the case of the (+)-boundary other than the fact that VM(ℓ, ε(ℓ)) must hold with lim ℓ→∞ ε(ℓ) = 0 because the (+)-phase is pure (see, e.g., [15]).
The rest of this section is divided into two parts. First, we develop a general framework based on coupling in order to establish the exponential decay of point-to-set correlations. This framework identifies two key quantities, κ and γ, and states that when their product is small enough then VM holds. Then, in the second part, we go back to proving Theorem 4.1 by calculating κ and γ for each of the above two regimes separately.

A coupling argument for decay of point-to-set correlations
In this section we develop a coupling framework that enables us to verify the exponential decay of point-to-set correlations from a simple calculation involving single-spin distributions.
First we need some additional notation. When x is not the root of T , let µ + Tx (respectively, µ − Tx ) denote the Gibbs distribution in which the parent of x has its spin fixed to (+) (respectively, (−)) and the configuration on the bottom boundary of T x is specified by τ (the global boundary condition on T ) ¶ . For two distributions µ 1 and µ 2 , we denote by µ 1 − µ 2 x the variation distance between the projections of µ 1 and µ 2 onto the spin at x. (Since the Ising model has only two spin values, Recall also that η y denotes the configuration η with the spin at site y flipped.
We now identify two constants that are crucial for our coupling argument: where the maximum is taken over all subsets A ⊆ T , all boundary configurations η, all sites y on the boundary of A and all neighbors z ∈ A of y.
Note that κ is the same as γ, except that the maximization is restricted to A = T z and the boundary vertex y being the parent of z; hence always κ ≤ γ. Since κ involves Gibbs distributions only on maximal subtrees T z , it may depend on the boundary condition τ at the bottom of the tree. By contrast, γ bounds the worst-case probability of disagreement for an arbitrary subset A and arbitrary boundary configuration around A, and hence depends only on (β, h) and not on τ . It is the dependence of κ on τ that opens up the possibility of an analysis that is specific to the boundary condition. For example, at very low temperature and with no external field, κ is close to 1 in the free boundary case, while it is close to zero in the (+)-boundary case.
In our arguments κ will be used to bound the probability of a disagreement percolating one level down the tree, namely, when we fix a disagreement at x and couple the two resulting marginals on a child z of x. On the other hand, γ will be used in order to bound the probability of a disagreement percolating one level up the tree, namely, when we fix a single disagreement on the bottom boundary of a block, say at y (with the rest of the boundary configuration being arbitrary), and couple the marginals on the parent of y.
The novelty of our argument for establishing VM comes from the fact that we identify two separate constants κ and γ, and consider their product, rather than working with κ alone: In particular, if γκb < 1 then there exists a constant ϑ > 0 such that, for every T , the measure µ = µ τ T satisfies VM(ℓ, e −ϑℓ ) for all ℓ, and hence c gap (µ) = Ω(1). ¶ Notice that we do not specify the rest of the configuration outside Tx since it has no influence on the distribution inside Tx once the spin at the parent of x is fixed. However, since our distributions are defined over the whole configuration space, in the discussion below when the configuration outside Tx is relevant it will be understood from the context. Proof: Fix arbitrary T , x ∈ T , η ∈ Ω τ T . We need to show that for every function f that does not depend on B x,ℓ , Var η Tx [µ Tx (f )] ≤ ε · Var η Tx (f ) with ε = (κγb) ℓ , i.e., projecting f onto the root (of T x ) causes the variance to shrink by a factor ε. As is well known, it is enough to establish a dual contraction, i.e., to consider an arbitrary function that depends only on the spin at the root and show that, when projecting onto levels ℓ and below, the variance shrinks by a factor ε. Formally, it is enough to show that for every function g that does not depend on T x we have This is because for a function f that does not depend on B x,ℓ , the variance of the projection can be written as and the last inequality is an application of Cauchy-Schwartz. We then have .
If we assume (14) then the expression on the r.h.s. is bounded by ε · Var η Tx (f ) since g = µ Tx (f ) does not depend on T x .
We therefore proceed with the proof of (14), which goes via a coupling argument. A coupling of two distributions µ 1 , µ 2 on Ω is any joint distribution ν on Ω 2 whose marginals are µ 1 and µ 2 respectively. For two configurations σ, σ ′ ∈ Ω, let |σ − σ ′ | x,ℓ denote the Hamming distance between the restrictions of σ and σ ′ to ∂B x,ℓ , i.e., the number of sites at distance ℓ below x at which σ and σ ′ differ. Notice that |σ − σ ′ | x,ℓ can be at most b ℓ , the number of sites on the ℓth level below x. Let µ + Tx (respectively, µ − Tx ) stand for the Gibbs distribution where the spin at x is set to (+) (respectively, (−)) and, as usual, the configuration on the bottom boundary of T x is specified by τ . Our goal will be to construct a coupling ν of µ + Tx and µ − Tx for which the expectation
(ii) For any η, η ′ ∈ Ω that have the same spin value at the parent of Let us assume Claim 4.4 for the moment and complete the proof of (14). Consider an arbitrary g that does not depend on T x . Let p = µ η Tx (σ x = +) and q = 1 − p = µ η Tx (σ x = −). We also write g + for g(σ), where σ is any configuration that agrees with η outside T x and such that σ x = +. (This is well defined since g does not depend on T x ). We define g − similarly. Without loss of generality we may assume that in the coupling ν from Claim 4.4 both the coupled configurations agree with η Effectively this means that, conditioned on the configuration outside Tx being η, g depends only on the spin at the root x.
outside T x with probability 1. We then have In the sixth line here we have used part (ii) of Claim 4.4, and in the last line we have used part (i). This completes the proof of (14), and hence of Theorem 4.3. We thus go back and prove Claim 4.4. The proof of Claim 4.4 makes use of a standard recursive coupling along paths in the tree (as in, e.g., [3]). We start with part (i), i.e., constructing a coupling ν of µ + Tx and µ − Tx with the required properties. Since the underlying graph is a tree, we can couple µ + Tx and µ − Tx recursively. This goes as follows. First, given the spin at x the measures on T z (where z ranges over the children of x) are all independent of each other, so we can couple the projections on the T z 's independently. Then, we couple the two projections on T z by first coupling the spin at z using the optimal coupling (the one that achieves the variation distance) of the marginal measures on the spin at z. Thus, the spins at z disagree with probability at most κ. Once a coupled pair of spins at z is chosen, we continue as follows: if the spins at z agree then we can make the configurations in T z equal with probability 1 (because the two boundary conditions are the same); if the spins at z differ (i.e., one is (+) and the other (−)) then we recursively couple µ + Tz and µ − Tz . We let ν be the resulting coupling of µ + Tx and µ − Tx , and notice that E ν |σ − σ ′ | x,l ≤ (κb) ℓ since for every site y at distance ℓ below x the probability that the two coupled spins at y disagree is at most κ ℓ .
We go on to prove part (ii) of Claim 4.4. First, by writing a telescopic sum and applying the triangle inequality we get that where k = |η − η ′ | x,ℓ and the sequence of configurations η (i) is a site-by-site interpolation of the differences between η and η ′ in ∂B x,ℓ . (It suffices to interpolate only over the differences in ∂B x,ℓ since the measure µ η B x,ℓ depends only on the configuration in ∂B x,ℓ and since η and η ′ agree on the parent of x.) It is now enough to show that µ η B x,ℓ − µ η w B x,ℓ x ≤ γ ℓ for all η and w ∈ ∂B x,ℓ . This, however, follows by a coupling argument as before, where this time we couple recursively along the path from w to x (i.e., up the tree). Specifically, suppose by induction that in our coupling there is already a path of disagreement going from w to y, where y is some site on the path from w to x. Let z denote the parent of y. At the next step we choose a coupled pair of spins at z from the two distributions µ η A and µ η y A (using an optimal coupling for the projections onto the spin at z), where the subset A is B x,ℓ excluding the path from w to y. The probability of disagreement at z given the disagreement at y is then bounded by γ, by definition. If the resulting spins at z agree then the spins on the rest of the path are coupled to agree with certainty, while if there is a disagreement at z we continue recursively starting from the disagreement at z. We therefore conclude that the probability of disagreement at x in the resulting coupling is γ ℓ , as required.

Remark:
We emphasize that Theorem 4.3 is not specific to the Ising model and generalizes to arbitrary nearest-neighbor models on a tree. Although we used the fact that the Ising model has only two possible spin values, the proof can easily be generalized to more than two spin values at the cost of a factor 1 pmin in front of (γκb) ℓ in VM, where p min is the minimum probability of any spin value as defined just before Theorem 3.4. Thus, since Theorem 3.2 also applies to general nearest-neighbor spin systems on a tree, we conclude that the implication from γκb < 1 to a bounded c gap (µ) holds for any such system (with the definitions of κ and γ extended in the obvious way to systems with more than two spin values). The details can be found in the companion paper [31].

Proof of Theorem 4.1
In this section we go back to proving Theorem 4.1. Using Theorem 4.3, all we need to do for the given choices of the Ising model parameters is to bound κ and γ as in Definition 4.2 such that γκb < 1. In contrast to Sections 3 and 4.1, which apply to general nearest-neighbor spin systems on trees, here the calculations are specific to the Ising model.
For both κ and γ, we need to bound a quantity of the form µ η A − µ η y A z , where y ∈ ∂A and z ∈ A is a neighbor of y. The key observation is that this quantity can be expressed very cleanly in terms of the "magnetization" at z, i.e., the ratio of probabilities of a (−)-spin and a (+)-spin at z. It will actually be convenient to work with the magnetization without the influence of the neighbor y: thus we let µ η,y= * A denote the Gibbs distribution with boundary condition η, except that the spin at y is free (or equivalently, the edge connecting z to y is erased). We then have: Proof: First, w.l.o.g. we may assume that the edge between y and z is the only one connecting y to A; this is because a tree has no cycles, so once the spin at y is fixed A decomposes into disjoint components that are independent. We also assume w.l.o.g. that the spin at y is (+) in η, and we abbreviate µ η A and µ η y A to µ + A and µ − A respectively, and also µ η,y= *

Proposition 4.5 For any subset A ⊆ T , any boundary configuration η, any site y ∈ ∂A and any neighbor z ∈
. Since the only influence of y on A is through z, we have R + = e −2β R and R − = e 2β R. The proposition now follows once we notice that, by definition of R + and R − , µ + Now it is easy to check that K β (a) is an increasing function in the interval [0, 1], decreasing in the interval [1, ∞], and is maximized at a = 1. Therefore, we can always bound κ and γ from above by K β (1) = e β −e −β e β +e −β . Indeed, for γ we must make do with this crude bound because it has to hold for any boundary configuration η and we cannot hope to gain by controlling the magnetization R. However, as we shall see, for κ we can do better in some cases by computing the magnetization at the root; when this differs from 1 we get a better bound than K β (1).
We are now ready to proceed to the proof of Theorem 4.1:

(i) Arbitrary boundary conditions
Here, the boundary condition τ is arbitrary and we first consider the (easy) case when β < β 0 or |h| > h c (β) (i.e., h is super-critical). In this case we do not need to resort to the calculation of κ and γ. As discussed in the Introduction, in this regime there is a unique infinite volume Gibbs measure, so certainly the variation distance at the root max η,η ′ µ η B x,ℓ − µ η ′ B x,ℓ x goes to zero as ℓ increases. In fact, it is not too difficult to see that in the above regime this variation distance goes to zero exponentially fast, which directly implies the desired exponential decay of correlations (VM) by plugging the bound on the variation distance into expression (15) in the proof of Theorem 4.3.
We go on to consider the more interesting regime when β 0 ≤ β < β 1 (i.e., intermediate temperatures) and the external field h is arbitrary. Here we use the fact that κ ≤ γ ≤ K β (1). We then . From the definition of β 1 (see Section 1.1), this corresponds precisely to β < β 1 . (Observe how this nontrivial result drops out immediately from our machinery, as expressed in the condition γ 2 < 1 b .) This completes the verification of Theorem 4.1 part (i).

(ii) (+)-boundary condition
We now assume that τ is the all-(+) configuration and consider arbitrary β and h. For convenience, we assume h ≥ −h c (β) since the case |h| > h c (β) was covered in part (i) for all boundary conditions τ . The important property of the regime h ≥ −h c (β) is that, for the (+)-boundary, the spin at the root is at least as likely to be (+) as it is to be (−). We will show that γκb < 1 throughout this regime. Recall that we already showed that γ ≤ K β (1) < 1 for all finite β. It is therefore enough to show that κ ≤ 1 b . To calculate κ, we need to bound the variation distance µ + Tz − µ − Tz z , which by Proposition 4.5 Tz (σz =+) and µ * Tz is the Gibbs distribution over the subtree T z when it is disconnected from the rest of T and the spins on its bottom boundary agree with τ . We thus have κ = sup T max z∈T K β (R z ).
The final ingredient we need is a recursive computation of the magnetization R z , the details of which (up to change of variables) can be found in [2] or [5]. Let y ≺ z denote that y is a child of z.  (16) and observe that, for any z ∈ T , R z = J (ℓ) (0), where J (ℓ) stands for the ℓ-fold composition of J, and ℓ is the distance of z from the bottom boundary of T . We now describe some properties of J that we use (refer to Fig. 2): J is continuous and increasing on [0, ∞), with J(0) = e −2β(h+b) > 0 and sup a J(a) = e −2β(h−b) < ∞. This immediately implies that J has at least one fixed point in [0, ∞); we denote by a 0 the least fixed point. Since a 0 is the least fixed point and J(0) > 0 then clearly ∂a is the derivative of J. We also note that a 0 ≤ 1 when h ≥ −h c (β), which corresponds to the fact that for the (+)-boundary and the above regime of h, the spin at the root is at least as likely to be (+) as (−). Now, since J is monotonically increasing and a 0 is the least fixed point of J, clearly J (ℓ) (0) converges to a 0 from below, i.e., R z ≤ a 0 for every z ∈ T . Thus, since a 0 ≤ 1 for h ≥ −h c (β), and the function K β (a) is monotonically increasing in the interval [0, 1], K β (R z ) ≤ K β (a 0 ) for every z ∈ T .
What remains to be shown is that K β (a 0 ) ≤ 1 b . This follows from the fact that J ′ (a 0 ) ≤ 1, together with the following lemma: The point a 0 is the smallest fixed point of J.
Proof: From the definitions of J and F we have: This completes the verification of Theorem 4.1 part (ii).

Verifying spatial mixing for log-Sobolev
In this section we will prove a uniform lower bound (independent of n) on the logarithmic Sobolev constant c sob (µ) in all the situations covered by Theorem 1.2 in the Introduction.
In light of Theorem 3.4, to show c sob = Ω(1) we need only prove the validity of the Entropy Mixing condition EM(ℓ, [(1−δ)p min /2(ℓ+1−δ)] 2 ) for some constants ℓ and δ independent of the size of T . In order to establish EM in the situations covered by Theorem 1.2, we extend the coupling framework developed in Section 4.1 so that it can be used to establish EM. As before, we will use a condition on the constants κ and γ, which were defined in Section 4.1. In fact, the condition on κ and γ for establishing EM is practically the same as the one that was used to establish VM, which immediately transfers our Ω(1) bound on c gap for the relevant parameters to an Ω(1) bound on c sob for the same choice of parameters. The main result of this section is the following relationship between (κ, γ) and EM.  depends only on (b, β, h). In particular, if max {γκb, γ} < 1 then there exists a constant ϑ such that, for every T , the measure µ = µ τ T satisfies EM(ℓ, ce −ϑℓ ) for all ℓ, and hence c sob (µ) = Ω(1).

Remark:
We should note that the above theorem, like its counterpart for the spectral gap, holds for any spin system on a tree (with the definitions of κ and γ generalized appropriately). See the companion paper [31] for details.
This completes the proof of our second main result, Theorem 1.2 stated in the Introduction.
The first step in proving Theorem 5.1 is a reduction of EM to a certain strong concentration property of µ, the Gibbs measure under consideration. We believe that this concentration property, as well as its connection to EM, may be of independent interest. The statement of this property and the reduction of EM to it is the content of Section 5.1. Then, in Section 5.2, we complete the proof of Theorem 5.1 by relating the strong concentration property to κ and γ.
It is worth mentioning that we are also able to establish a general (but cruder) bound on c sob as a function of c gap . Specifically, we can show that c sob = Ω(1/ log n) × c gap . Although we do not need this bound in this paper, we present it in Section 5.3 for future reference since its proof is simple and short.

Establishing EM via a strong concentration property.
In this subsection we reduce EM to a certain strong concentration property of µ. In the next subsection, we will then establish this strong concentration property as a function of κ and γ in order to prove Theorem 5.1. For simplicity and without loss of generality, we will analyze the entropy mixing condition only for T x = T (the whole tree), with root r.
Let µ + T and µ − T denote the Gibbs distributions on T with the spin at the root r set to (+) and (−) respectively (the boundary condition on the leaves of T being specified by τ ). Define where p = µ(σ r = +). The key quantity we will work with in the sequel is the following: Note that g (ℓ) + (σ) depends only on the spins in ∂B r,ℓ . Indeed, let σ r,ℓ stand for the restriction of σ to ∂B r,ℓ , i.e., to the sites at distance ℓ below r. It is easy to verify that g (ℓ) µ(σ r,ℓ ) . Thus, for a given configuration σ, g (ℓ) + (σ) is the ratio of the probabilities of seeing the spins of σ at level ℓ below the root r when the spin at r is (+) and when there is no condition on the spin at r, respectively. We define g − and g − is embodied in the following theorem, which says that if these functions are sufficiently tightly concentrated around their common mean value of 1 then the entropy mixing condition EM holds. c (depending only on b, β and h) such that, for any δ ≥ 0, if

Theorem 5.3 There exists a constant
for s ∈ {+, −}, then we have Ent µ T (f ) ≤ cδ Ent(f ) for any non-negative function f that does not depend on B r,ℓ ; in particular, EM(ℓ, cδ) holds.
Proof: Fix ℓ < m and a non-negative function f that does not depend on the spins inside the block B r,ℓ . Since Ent(f ′ ) ≤ Var(f ′ )/µ(f ′ ) for every non-negative function f ′ (see, e.g., [36]) then where Cov denotes covariance w.r.t µ. Now observe that, since f does not depend on B r,ℓ , when computing the covariance term in (18) the function g s can be replaced by g (ℓ) s , which depends only on the spins in ∂B r,ℓ . Thus, if we can show that (17) implies for some constant c, then by plugging (19) into (18) we will get that Ent µ T (f ) ≤ cδ Ent(f ), as required.
To establish (19) we make use of the following technical lemma, whose proof can be found in Section 7.
We apply this lemma with ν = µ and Noting also that g (ℓ) s ∞ ≤ g s ∞ ≤ 1/p min , where p min was defined just before Theorem 3.4, this establishes (19) with c = c ′ /p 2 min and thus completes the proof of the theorem.

Proof of Theorem 5.1
In light of Theorem 5.3, to prove Theorem 5.1 it is sufficient to verify the strong concentration property (17) of the functions g (ℓ) s with δ = (γα) ℓ/5 . In order to do this we appeal to a strong concentration of the Hamming distance under the coupling ν of µ + T and µ − T , as defined in the proof of Claim 4.4. Recall the notation used in that claim, and notice that the Hamming distance is dominated by the size of the population in the ℓth generation of a specific branching process. The following tail bound can be obtained using standard techniques from the analysis of branching processes, and we defer the proof to the end of this section.
. Proof: It is enough to show that since we can then apply Lemma 5.5 with C replaced by p min C. On the other hand, (20) follows from part (ii) of Claim 4.4 once we recall that g (ℓ) s (σ) = µ σ B r,ℓ (g s ) and that g s depends only on the spin at the root, implying that |g Before we go on with the proof of Theorem 5.1, let us compare the way we used the constants κ and γ in the proof of Corollary 5.6 to the way we used them in the proof of Theorem 4.3. In both cases we used κ and γ to get bounds for coupling "down" and "up" the tree respectively. Specifically, we used κ to deduce that the Hamming distance between the coupled configurations at the ℓth level is about (κb) ℓ , and we then used γ to bound the effect of each discrepancy at the ℓth level on the spin at the root (or equivalently, on g (ℓ) s ) by roughly γ ℓ . While in Theorem 4.3 it was enough that the average Hamming distance when coupling down the tree was bounded by (κb) ℓ , here we need that this distance is not much larger than (κb) ℓ with high probability.
We now return to the proof of Theorem 5.1. W.l.o.g. we may assume that γα ≤ 1 since EM(ℓ, 1) always holds, and also that γα > 0 since if γ = 0 then EM(ℓ, 0) holds because then the spin at the root r is independent of the rest of the configuration. Let a = (γα) −1 ≥ 1. Recall that we wish to establish (17) with δ = a −ℓ/5 for all large enough ℓ. We will show only that since the same bound on the negative tail can be achieved by an analogous argument. We start by applying Corollary 5.6 with C = a ℓ/4 to get that, for every ε > 0, where A = e Next, we notice that by definition of g Combining (22) and (23) we get that, for every ε > 0, This immediately yields that, for every non-negative integer k and ε > 0, where we applied (24) k + 1 times, each time increasing ε by a −3ℓ/4 . Inequality (21) then follows (assuming ℓ is large enough) by applying (25) with ε = a −ℓ/4 and k = ⌈a ℓ/2 ⌉. This concludes the proof of Theorem 5.1.
Finally, we supply the missing proof of Lemma 5.5.
Proof of Lemma 5.5: First notice that, by an exponential Markov inequality, it is enough to show that E ν e t|σ−σ ′ | r,ℓ ≤ e 2etα ℓ for all t ≤ (2e(ℓ + 1)α ℓ ) −1 ≤ 1. We thus fix t as above and let D x,i = E ν e t|σ−σ ′ | x,i , where ν is the coupling of µ + Tx and µ − Tx . Note that D x,i can be calculated recursively as follows. The main observation is that, given a disagreement at x, the random variable |σ − σ ′ | x,i is the sum of the b independent random variables |σ − σ ′ | z,i−1 where z ranges over the children of x. In turn, the random variable e t|σ−σ ′ | z,i−1 takes the value D z,i−1 with probability at most κ (the probability of a disagreement at z given a disagreement at x) and the value 1 with the remaining probability (since |σ − σ ′ | z,i−1 = 0 if there is no disagreement at z). Thus, if we let We wish to show that, for t in the above range, δ ℓ ≤ 2etα ℓ , which implies E ν e t|σ−σ ′ | r,ℓ ≤ δ ℓ + 1 ≤ e 2etα ℓ , as required. In fact, we show by induction that δ i ≤ 2t[ ℓ+1 ℓ · α] i for every 0 ≤ i ≤ ℓ. For the base case i = 0, notice that |σ − σ ′ | x,0 = 1 when starting from a fixed disagreement at x, so δ 0 = e t − 1 ≤ 2t for t in the given range. For i + 1 > 0, we use the fact that δ i+1 ≤ e αδ i − 1 ≤ αδ i 1−αδ i ≤ ℓ+1 ℓ · αδ i , since by the induction hypothesis δ i ≤ 1 α(ℓ+1) for all 0 ≤ i ≤ ℓ − 1 and t in the given range.

A crude bound on log-Sobolev via the spectral gap
In this section we state and prove a general bound on c sob using a bound on c gap . Although we do not require this bound for the results in this paper, we believe that it may find applications in the future. We state the bound for the Ising model, but it can be easily verified that it generalizes to any nearest-neighbor spin system on a tree. It is useful to compare this bound with the well-known bound c sob (µ) = c gap (µ) × Ω(1/n) (see, e.g., [36]), which though much weaker is also more general (for example, it applies to spin systems on any graph). Theorem 5.7 is a consequence of the following lemma.
This lemma immediately implies Theorem 5.7, once we notice that c gap (µ η Tx ) ≥ c ′ · c gap (µ τ T ) for a constant c ′ = c ′ (b, β, h) and every x ∈ T and η ∈ Ω τ T , as can easily be checked.
Proof of Lemma 5.8: For simplicity and w.l.o.g. we will prove the recursive inequality (26) only for T x = T (the whole tree), with root r. Let f be a non-negative function. We then write (using the entropy version of (2)) Using the definition of c sob we have The second term on the r.h.s. of (27), being the entropy of a Bernoulli random variable, is bounded above by ≤ αVar( f ) where α ≡ α(p) is a constant that depends on p = µ(σ r = +); specifically α(p) = log(p/1−p) 2p−1 for p = 1/2, and α(1/2) = 1/2 (see [36]).
Putting together (28) and (30), the expression in (27) is bounded above by so that from the definition of c sob we have

Extensions to other models
As we have already indicated, our techniques extend beyond the Ising model to general nearestneighbor interaction models on trees, including those with hard constraints. In this final section we mention some of these extensions. For a fuller treatment of this material, the reader is referred to the companion paper [31]. A (nearest neighbor) spin system on a finite graph G = (V, E) is specified by a finite set S of spin values, a symmetric pair potential U : S × S → R ∪ {∞}, and a singleton potential W : S → R. A configuration σ ∈ S V of the system assigns to each vertex (site) v ∈ V a spin value σ v ∈ S. The Gibbs distribution is given by Thus the Ising model corresponds to the case S = {±1}, and U (s 1 , s 2 ) = −βs 1 s 2 , W (s) = −βhs, where β is the inverse temperature and h is the external field. Note that setting U (s 1 , s 2 ) = ∞ corresponds to a hard constraint, i.e., spin values s 1 , s 2 are forbidden to be adjacent. We denote by Ω the set of all valid spin configurations, i.e., those for which µ(σ) > 0.
As for the Ising model, we allow boundary conditions which fix the spin values of certain sites. We carry over our notation from the Ising model: thus, e.g., µ τ A denotes the Gibbs distribution on a subset A ⊆ V with boundary condition τ on ∂A.
The (heat-bath) Glauber dynamics extends in the obvious way to general spin systems. We first note that, as the reader may easily check, neither the spatial mixing conditions in Section 3 nor their proofs made any reference to the details of the Ising model. All of this material therefore carries over without modification to general spin systems on trees.

Theorem 6.1 The statements of theorems 3.2 and 3.4 hold for general nearest-neighbor spin systems on trees.
Likewise, the machinery developed in Sections 4 and 5 for verifying the conditions VM and EM also extends to general models, though the details of the calculations are model-specific. In particular, Theorems 4.3 and 5.1 relating VM and EM to the coupling quantities κ and γ of Definition 4.2 still hold (with very minor modifications). Thus all we need to do is to carry out the detailed calculations of κ and γ for the model under consideration. We now state without proof the results of these calculations for several models of interest. For the proofs, together with further discussion and extensions, the reader is referred to the companion paper [31].

The hard-core model (independent sets)
In this model S = {0, 1}, and we refer to a site as occupied if it has spin value 1, and unoccupied otherwise. The potentials are U (1, 1) = ∞; U (1, 0) = U (0, 0) = 1; W (1) = L; W (0) = 0, where L ∈ R. The hard constraint here means that no two adjacent sites may be occupied, so Ω can be identified with the set of all independent sets in G. Also, the aggregated potential of a valid configuration is proportional to the number of occupied sites. Hence the Gibbs distribution takes the simple form where N (σ) is the number of occupied sites and the parameter λ = exp(−L) > 0, which controls the density of occupation, is referred to as the "activity." The hard-core model on a b-ary tree undergoes a phase transition at a critical activity λ = λ 0 = b b (b−1) b+1 (see, e.g., [39,23]). For λ ≤ λ 0 there is a unique Gibbs measure regardless of the boundary condition on the leaves, while for λ > λ 0 there are (at least) two distinct phases, corresponding to the "odd" and "even" boundary conditions respectively. The even boundary condition is obtained by making the leaves of the tree all occupied if the depth is even, and all unoccupied otherwise. The odd boundary condition is the complement of this. (These boundary conditions are derived from the two maximum-density configurations on the infinite tree T b in which alternate levelseither odd or even -are completely occupied.) For λ > λ 0 , the probability of occupation of the root in the infinite-volume Gibbs measure differs for odd and even boundary conditions. Relatively little is known about the Glauber dynamics for the hard-core model on trees, beyond the general result of Luby and Vigoda [27,43] which ensures a mixing time of O(log n) (after translation to our continuous time setting) when λ < 2 b−1 . This result actually holds for any graph G of maximum degree b + 1.
Our results for the Glauber dynamics in the hard-core model mirror those given earlier for the Ising model. First, for sufficiently small activity λ we show that both c gap and c sob are uniformly bounded away from zero for arbitrary boundary conditions. Second, for even (or, symmetrically, odd) boundary conditions, we get the same result for all activities λ. (i) τ is arbitrary, and λ ≤ max (ii) τ is even (or odd), and λ ≥ 0 is arbitrary.
Part (ii) of this theorem is analogous to our earlier result for the Ising model with (+)-boundary and zero external field at all temperatures. This is in line with the intuition that the even boundary eliminates the only bottleneck in the dynamics. Part (i) identifies a region in which the mixing time is insensitive to the boundary condition. We would expect this to hold throughout the low-activity region λ ≤ λ 0 , and indeed, by analogy with the Ising model, also in some intermediate region beyond this. Our bound in part (i) confirms this behavior: note that the quantity 1 √ b−1 exceeds λ 0 for all b ≥ 5, and indeed for large b it grows as 1 √ b compared to the 1 b growth of λ 0 . Thus for b ≥ 5 we establish rapid mixing in a region above the critical value λ 0 . To the best of our knowledge this is the first such result. (Note that the result of [27,43] mentioned earlier establishes rapid mixing for λ < 2 b−1 , which is less than λ 0 for all b and so does not even cover the whole uniqueness region.) We should also mention that our coupling analysis of c gap in this region has consequences for the infinite volume Gibbs measure itself, implying that when λ ≤ 1 √ b−1 any µ = lim T →∞ µ τ T that is the limit of finite Gibbs distributions for some boundary configuration τ is extremal, again a new result. We elaborate on these points in the companion paper [31].

The antiferromagnetic Potts model (colorings)
In this model S = {1, 2, . . . , q}, and the potentials are U (s 1 , s 2 ) = βδ s 1 ,s 2 , W (s) = 0. This is the analog of the Ising model except that the interactions are antiferromagnetic, i.e., neighbors with unequal spins are favored. The most interesting case of this model is when β = ∞ (i.e., zero temperature), which introduces hard constraints. Thus if we think of the q spin values as colors, Ω is the set of proper colorings of G, i.e., assignments of colors to vertices so that no two adjacent vertices receive the same color. The Gibbs distribution is uniform over proper colorings. In this model it is q that provides the parameterization. For background on the model, see [8].
For colorings on the b-ary tree it is well known that, when q ≤ b + 1, there are multiple Gibbs measures; this follows immediately from the existence of "frozen configurations," i.e., colorings in which the color of every internal vertex is forced by the colors of the leaves (see, e.g., [8]). Recently Jonasson [21] proved that, as soon as q ≥ b+ 2, the Gibbs measure is unique. Moreover, it is known that there is again an "intermediate" region that includes the value q = b + 1, in which the Gibbs measure, while not unique, is insensitive to "typical" boundary conditions (chosen from the free measure); see [8].
The sharpest result known for the Glauber dynamics on colorings is due to Vigoda [42], who shows that for arbitrary boundary conditions the mixing time is O(log n) provided q > 11 6 (b + 1). Actually this result holds for any n-vertex graph G of maximum degree b + 1. * * Our techniques extend this rapid mixing result all the way down to the critical value q ≥ b + 2 for which uniqueness holds, with arbitrary boundary conditions. Again, our result is a consequence of the fact that the associated log-Sobolev constant is bounded below by a constant independent of n: Theorem 6.3 For the colorings model on the n-vertex b-ary tree with q ≥ b+2 and arbitrary boundary conditions, both c gap (µ) and c sob (µ) are Ω(1).

The ferromagnetic Potts model
Here we have S = {1, 2, . . . , q} and potentials U (s 1 , s 2 ) = −βδ s 1 ,s 2 , W (s) = 0. This is a straightforward generalization of the (ferromagnetic) Ising model studied earlier in the paper, in which the spin at each site can take one of q possible values, and the aggregated potential of any configuration depends on the number of adjacent pairs of equal spins. There are no hard constraints.
Qualitatively the behavior of this model is similar to that of the Ising model, though less is known in precise quantitative terms. Again there is a phase transition at a critical β = β 0 , which depends on b and q, so that for β > β 0 (and indeed for β ≥ β 0 when q > 2) there are multiple phases. This value β 0 does not in general have a closed form, but it is known [16] that β 0 < (iii) the boundary is free (i.e., the boundary spins are unconstrained) and β < β 1 , where β 1 is the solution to the equation e 2β 1 −1 e 2β 1 +q−1 · e 2β 1 −1 e 2β 1 +1 = 1 b . * * A recent sequence of papers [12,32,17] have reduced the required number of colors further for general graphs, under the assumption that the maximum degree is Ω(log n); the current state of the art requires q ≥ (1 + ǫ)(b + 1) for arbitrarily small ǫ > 0 [18]. However, these results do not apply in our setting where the degree b + 1 is fixed. Part (i) of this theorem shows that c gap and c sob are Ω(1) for arbitrary boundaries throughout the uniqueness region; also, since 1 2 ln( √ b+1 √ b−1 ) ≥ 1 2 ln( b+q−1 b−1 ) > β 0 when q ≤ 2( √ b + 1), this result extends into the multiple phase region for many combinations of b and q. Part (ii) of the theorem is an analog of our earlier results for the Ising model with (+)-boundaries at all temperatures. Part (iii) is of interest for two reasons. First, since β 1 > β 0 always, it exhibits a natural boundary condition under which c gap and c sob are Ω(1) beyond the uniqueness region (but not for arbitrary β) for all combinations of b and q. Second, because of an intimate connection between the free boundary case and so-called "reconstruction problems" on trees [33] (in which the edges are noisy channels and the goal is to reconstruct a value transmitted from the root), we obtain an alternative proof of the best known value of the noise parameter under which reconstruction is impossible [34]. Indeed, a slight strengthening of part (iii) allows us to marginally improve on this threshold. Again, we spell out the details in [31].

Proofs omitted from the main text
In this final section, we supply the proofs of some technical lemmas that were omitted from the main text.

Proof of Lemma 3.5
The lemma in fact holds in a more general setting, where in place of T x and B x,ℓ we think of two arbitrary subsets A, B such that A ∪ B = T x . Also, in this proof we write ν = µ η Tx and Var and Ent for variance and entropy with respect to ν. For part (i) we will show that if for any function g that does not depend on B we have Var[ν A (g)] ≤ ε · Var(g), then for any function f , Notice that by the convexity of variance we have Var(g 1 + g 2 ) ≤ 2[Var(g 1 ) + Var(g 2 )] for any two functions g 1 , g 2 . We therefore write  (2). We therefore conclude that Var[ν A (f )] ≤ 2(1−ε) 1−2ε · ν[Var B (f )] + 2ε 1−2ε · ν[Var A (f )], as required. We proceed to part (ii). Here we have to show that if for any non-negative function g that does not depend B we have Ent[ν A (g)] ≤ ε · Ent(g), then for any non-negative function f , where ε ′ = √ ε/p and p stands for the minimum non-zero probability of any configuration in T x \ A.
We will in fact show that which implies (31)  where we wrote · 1 for the ℓ 1 norm with respect to µ and used the fact that f − µ(f ) 2 1 ≤ 2µ(f ) Ent(f ) for any non-negative function f (see, e.g., [36]). The proof of Claim 7.1 is now complete.

Proof of reverse direction of Theorem 3.4
In the main text we proved the forward direction of Theorem 3.4. Here we prove the reverse direction, i.e., that min x,η c sob (µ η Tx ) = Ω(1) implies EM(ℓ, ce −ϑℓ ) for all ℓ, where c = c(b, β, h) and ϑ = ϑ(b, β, h) are constants independent of ℓ. To do this, we follow the same line of reasoning as in the proof of Theorem 5.2: namely, we establish the strong concentration property of the functions g (ℓ) s as in Section 5.1 and then appeal to Theorem 5.3. The proof of concentration is accomplished via hypercontractivity bounds, assuming the above condition on c sob .
For a function f , let Λ f ⊆ T denote the subset of sites on whose spins f depends. We then have: Lemma 7.2 Let ν be any Gibbs measure on T , f any function, and B any subset that includes all sites within distance ℓ from Λ f . Then there exists a constant ϑ ′ , depending only on the degree b, such that where q = 1 + e c sob (ν)ϑ ′ ℓ and norms are taken w.r.t. ν.
We first assume Lemma 7.2 and complete the proof of the reverse direction of Theorem 3.4. For simplicity, we verify EM only for the case T x = T (the whole tree), with root r. Recall the functions g (ℓ) s from Section 5.1, the fact that g (ℓ) s = µ B r,ℓ (g s ) by definition, and that g s depends only on the spin at r. Applying Lemma 7.2 with ν = µ, f = g s , and B = B r,ℓ , together with the fact that c sob (µ) = Ω(1) by hypothesis, we conclude that there exists a constant ϑ ′′ such that where q = 1 + e ϑ ′′ ℓ and norms are taken w.r.t. µ. Therefore, using a Markov inequality, there exist constants ℓ 0 and ϑ such that, for all ℓ ≥ ℓ 0 , This establishes the strong concentration property of g (ℓ) s as in (17), from which EM follows by Theorem 5.3.

Remark:
A similar claim to Lemma 7.2 was proved in [41] in the context of Z d ; we reprove it below for completeness. The proof, as well as the fact that a Ω(1) logarithmic Sobolev constant implies EM(ℓ, ce −ϑℓ ), applies to general, finite range models on any graph of bounded degree.

Proof of Lemma 7.2:
The proof has two main ingredients: the first is a bound on the speed at which information propagates under the Glauber dynamics, while the second is a standard relationship between c sob and hypercontractivity bounds.
Let P t = e tL stand for the transition kernel at time t (as discussed in Section 2) of the dynamics under consideration, reversible w.r.t. the Gibbs measure ν, and let P B t stand for the transition kernel of a modified dynamics where the spins of the sites outside the subset B are fixed to their values at time zero (the sites inside B being updated according to the same rule as in the original dynamics). It is well known (see, e.g., [41]) that there exists a constant k 0 depending only on b (or on the degree of the graph in the general case) and the maximum flip rate max x c x ∞ (which is bounded by 1 in the case of the heat bath dynamics) such that, for any function f , any t and any subset B that includes all sites within distance k 0 t of Λ f , Equation (33) is a manifestation of the fact that it takes at least ℓ k 0 time before the spin at a site can become sensitive to the configuration at distance ℓ from it.
The second ingredient we need is a hypercontractivity bound. From Gross's integration lemma (see, e.g., [1]), we have P t f q ≤ f 2 for any mean-zero function f , any t, and 2 ≤ q ≤ 1 + e c sob t , where c sob = c sob (ν). Adding to this the fact that c gap > c sob , we may write for suitable numerical constants c 1 , c 2 .