The critical Ising model on trees, concave recursions and nonlinear capacity, , November 27, 2006

Keywords: Ising model, reconstruction, capacity, nonlinear potential theory, trees, iteration, spin-glass, recursion. Subject classification: Primary: 60K35; Secondary: 31C45.

1 Introduction

Let

T

be a finite rooted tree. Let

| v |

denote the distance from a vertex

v \in V (T)

to the root

o

and write

v \to w

v

is the parent of

w

, i.e., the neighbor of

w

closer to the root than

w

. Consider the space

Ω = Ω (T) = {+ 1, - 1}^{V (T)}

of configurations on the vertices of

T

. For each

w \neq 0

there is a unique edge

v w

with

v \to w

; let

J_{w} = J (v w)

be a positive number, so that

{J_{w} : 0 \neq w \in V (T)}

is a fixed set of interaction strengths on the edges of

T

. We assume throughout that the interaction strengths are bounded:

\begin{matrix} 0 < J_{m i n} \leq J_{v} \leq J_{m a x} \forall v \in V (T), v \neq o . \end{matrix}

(1.1)

This assumption loses little generality; see the end of Section 4. Fix an inverse temperature

β

and define the weight of a configuration

η \in Ω

to be the product over all pairs of neighboring vertices:

W (η) = \prod_{v \to w} exp (β J_{w} η (v) η (w)) .

The Ising model under various boundary conditions can be obtained by restricting to suitable subsets of

Ω

and assigning probabilities proportional to

W

. Our aim in this paper is to pinpoint the locations of the phase transitions that occur in these models as

N \to \infty

. In each case the critical temperature for phase transitions to occur is known. We refine these results by giving sharp criteria for the existence of a phase transition in terms of capacities.

2 Main results

Let

T

be any tree, rooted at a vertex

o

, and let

\partial T

denote the set of maximal paths oriented away from the root; these are either infinite or end at a leaf of

T

. For finite trees, we may identify

\partial T

with the set of leaves in

T

different from

o

. Let

{R (e) : e \in E (T)}

be a set of resistances (nonnegative numbers) assigned to the edges of

T

. Let

μ

be a flow on

T

, that is, a nonnegative function on

E (T)

such that the at every vertex (except for the root and the leaves) inflow equals outflow: whenever

v \to w

(

v

is a parent of

w

) and

w

is not a leaf, we have

μ (v w) = \sum_{y : w \to y} μ (w y)

. Denote

| μ | : = \sum_{y : o \to y} μ (o y)

. Fix

p > 1

and set

s = p - 1

. For

y \in \partial T

define

\begin{matrix} V_{μ} (y) & : = & \sum_{e \in y} (μ (e) R (e))^{s}; \end{matrix}

(2.2)

\begin{matrix} V (μ) & : = & sup {V_{μ} (y) : y \in \partial T}; \end{matrix}

(2.3)

\begin{matrix} c a p_{p} (T) & : = & sup {| μ | : V (μ) = 1} . \end{matrix}

(2.4)

These capacities have been studied on more general networks as part of discrete nonlinear potential theory; see, e.g., Murakami and Yamasaki (1992), Soardi (1993, 1994) and the references therein. However, all the properties of

c a p_{p}

that we will use follow readily from the definition. We note that

c a p_{2} (T)

reduces to the electrical conductance between

o

and

\partial T

Let

P

denote the probability measure on

Ω

proportional to

W

P (η) = \frac{W (η)}{\sum_{ξ \in Ω} W (ξ)} .

This is a ferromagnetic Ising model with no external field and free boundary conditions.

There is another construction of the measure

P

as an error-transmission model. To the edge leading to a vertex

v

from its parent, assign the positive bias

\begin{matrix} θ_{v} = \frac{e^{β J_{v}} - e^{- β J_{v}}}{e^{β J_{v}} + e^{- β J_{v}}} = tanh (β J_{v}) . \end{matrix}

(2.5)

Conditional on the sign

η (o)

at the root, let the sign at each other vertex

v

be determined recursively, by copying the sign at the parent with probability

(1 + θ_{v}) / 2

and reversing sign with probability

(1 - θ_{v}) / 2

. When

J_{v} = J

does not depend on

v

, we write

θ

for the common bias. Now suppose

T

is an infinite, locally finite tree, rooted at o, and let

T^{(N)}

be the induced finite subgraph of

T

with vertices

{v \in V (T) : | v | \leq N}

. Letting

P^{(N)}

be the free-boundary Ising measure on

T^{(N)}

, we ask about

P^{(N)} (η (0) = + 1 | η (v) : v \in \partial T^{(N)})

In particular, this converges in probability to

1 / 2

if and only if the free boundary Gibbs measure on

T

is extremal, see Georgii (1988). The question of extremality of the Gibbs measure with free boundary on regular trees was settled by Bleher et al (1995), see also Ioffe (1996a) for an elegant alternative proof.

The same question for general trees was solved by Ioffe (1996b) and Evans et al (2000), where the critical value is computed for an arbitrary tree. However, the question of extremality at the critical temperature was left open. In this paper we settle the critical case by showing that zero

L^{2}

capacity (with respect to certain resistances) implies extremality.

We prove

Theorem 2.1 Let

T

be an infinite, locally finite tree, rooted at o, with no leaves except possibly at o and interaction strengths

J_{v}

satisfying ( 1.1 ). For vertices

y, w

, write

y \leq w

y

is on the path from

o

w

. Assign to each edge

e = v w

with

v \to w

, the resistance

\begin{matrix} R_{w} : = R (e) : = \prod_{o < y \leq w} {(tanh β J_{y})}^{- 2} \end{matrix}

(2.6)

Then the Gibbs measure for free boundary is extremal if and only if

c a p_{2} (T) = 0

One direction of this theorem (that extremality implies zero capacity) was already proved in Evans et al (2000).

Let

Ω_{+} = Ω_{+} (T) \subset Ω (T)

be the configurations with

η (v) = + 1

for

v \in \partial T

. Then the probability measure

P^{+}

Ω_{+}

defined by

P^{+} (η) = \frac{W (η)}{\sum_{ξ \in Ω_{+}} W (ξ)}

is the Ising model with plus boundary conditions and no external field. The critical value of the interaction strength here has long been known for regular trees (see Preston 1974, 1976). Lyons (1991) computes the critical temperature for general trees and allows the interaction strengths to vary as well. We refine the known results by determining what happens at criticality. The sharp criterion turns out to involve an “

L^{3}

-capacity”. We prove

Theorem 2.2 Let

T

be any infinite, locally finite tree rooted at 0 and having no leaves except possibly 0. Let

{J_{v}}

be bounded interaction strengths, i.e., satisfying ( 1.1 ), and assign resistance

R_{v} = \prod_{o < y \leq v} (tanh (β J_{y}))^{- 1}

to the edge between

v

and its parent. Then the decreasing limit

{lim}_{N \to \infty} P^{(N, +)} (η (0) = + 1)

is equal to

1 / 2

if and only if

c a p_{3} (T) = 0

Here

P^{(N, +)}

is the measure on configurations on the first

N

levels of

T

with plus boundary conditions imposed at level

N

For ease of reading, we state the result more explicitly in the special case of spherically symmetric trees, and when the interaction strength is constant.

Corollary 2.3 Under the hypotheses of Theorem 2.2 , assume spherical symmetry as well:

θ_{v} = θ_{| v |}

and

deg (v) = d_{| v |}

depend only on

| v |

. Then there are multiple Gibbs states if and only if

\begin{matrix} {\sum_{n \geq 1}}^{n} \prod_{i = 1} (d_{i} θ_{i})^{- 2} < \infty . \end{matrix}

(2.7)

In particular, for a spherically symmetric tree

T

, suppose that the level cardinalities satisfy

\begin{matrix} | T_{n} | ≍ θ^{- n} n^{α} . \end{matrix}

(2.8)

Then there is a unique Gibbs state for the Ising model at criticality if and only if

α \leq 1 / 2

Note that for

T

satisfying ( 2.8 ), endowed with edge resistances

θ^{- n}

at level

n

, the standard

L^{2}

capacity of

T

is zero as long as

α \leq 1

Corollary 2.4 Suppose that

J_{v} \equiv J

is constant, and let

θ : = tanh (β J)

. Then phase transition occurs with plus boundary conditions if and only if

c a p_{3} (T) > 0

with resistances

θ^{- n}

at distance

n

from the root. If

T

is spherically symmetric, this is equivalent to

\sum_{n \geq 1} θ^{- 2 n} | T_{n} |^{- 2} < \infty .

Define a measure

P^{s g}

by making the signs

η (v)

for

v \in \partial T

i.i.d. fair coin flips, and requiring that the measure be proportional to

W

conditionally on the values on

\partial T

P^{s g} (η) = 2^{- | \partial T |} \frac{W (η)}{\sum_{ξ |_{\partial T} = η |_{\partial T}} W (ξ)} .

This is equivalent to the following spin-glass model considered by Chayes et al (1986):

the Hamiltonian has no external field and interactions of a fixed magnitude, with the signs of the interactions determined by i.i.d. fair coin flips; the boundary conditions are all plus.

The question is whether, conditional upon the signs of the interactions, the sign at the root is influenced at all by the boundary values in the limit as

N \to \infty

. A critical interaction strength is given in Chayes et al (1986) for regular trees; we improve this to the case of general trees and settle what happens at the critical case. The result is a standard (i.e.,

L^{2}

) capacity criterion, exactly equal to the criterion for the case of a free boundary.

Theorem 2.5 Let

T

be an infinite, locally finite tree, rooted at o, with no leaves (except possibly o) and interaction strengths

J_{v}

satisfying ( 1.1 ). Assign resistances

R_{v} = \prod_{0 < y \leq v} (tanh (β J_{y}))^{- 1}

as in ( 2.6 ). Then

P^{s g} (η (o) = 1 | η |_{\partial T}) \to 1 / 2

in probability under the spin-glass measure if and only if

c a p_{2} (T) = 0

Let

x_{v}

denote the likelihood ratio of having spin 1 versus

- 1

v

, given the boundary.

The method in in the plus boundary case is to show that

{x_{v} : v \in V (T)}

satisfy a recursion of the form

\begin{matrix} x_{v} = \sum_{v \to w} f_{w} (x_{w}) . \end{matrix}

(2.9)

This reduces the problem to the question of whether, on a given infinite tree, this recursion has a nonzero solution. We give a general solution to this problem, recursively establishing a set of inequalities relating solutions and sub-solutions of these equations to generalized capacities. In the cases of free and spin-glass boundary conditions, the log likelihood ratios are random variables

{X_{v} : v \in V (T)}

and we obtain versions of ( 2.9 ) for certain moments

{m_{v}}

{X_{v}}

The rest of the paper is organized as follows. The next section focuses entirely on the deterministic aspect of the problem, namely, when the recursion ( 2.9 ) has a nontrivial solution or sub-solution. The theorems in this section are broad enough to handle the recursions arising from the three types of boundary conditions in the Ising model. Then we spend one section on each of the three models and conclude with some questions.

3 Recursions on trees and potential theory

Let

T

be any locally finite rooted tree and let

{f_{v} : v \in V (T)}

be a collection of nonnegative functions indexed by the vertices of

T

. We are interested in whether the simultaneous inequalities

\begin{matrix} x_{v} \leq \sum_{v \to w} f_{w} (x_{w}) \end{matrix}

(3.10)

have any nonzero solutions. A special case of interest is when

f_{v} \equiv f

does not depend on

v

. Our characterization is in terms of generalized capacities, which we defined in ( 2.4 ).

Fix

p > 1

and let

s = p - 1

. In addition to ( 2.2 ) and ( 2.4 ), we define

\begin{matrix} V (T) & : = & inf {V (μ) : | μ | = 1}; \end{matrix}

(3.11)

\begin{matrix} ℰ (μ) & : = & \sum_{e \in E (T)} μ (e)^{p} R (e)^{s} . \end{matrix}

(3.12)

We quote several easy, and well known, consequences of the definitions of energy and capacity.

$(i)$ The supremum in the definition ( 2.4 ) of $c a p_{p}$ is achieved if non-empty.
Furthermore, $inf {ℰ (μ) : | μ | = 1} = V (T) = c a p_{p} (T)^{- s}$ and the infimum is achieved if non-empty.
$(i i)$ Joining several trees at the root sums their capacities.
$(i i i)$ Multiplying all resistances by $α$ decreases capacity by a factor of $α$ .
$(i v)$ A single edge of resistance $R$ in series with a tree $T$ has capacity $\frac{c a p_{p} (T)}{1 + R^{s} (c a p_{p} (T)^{s})^{1 / s}} .$

For instance, to see

(i v)

, observe that there is a one to one correspondence between flows

μ

from the root to the boundary in

T

and flows

μ_{R}

in the enhanced tree, such that

| μ_{R} | = | μ |

and

V (μ_{R}) = V (μ) + R^{s} | μ |^{s}

. These yield the following lemma, which is all we need below. Recall that

T (v)

denotes the subtree from

v

Lemma 3.1 Fix

p > 1

and

s = p - 1

. For any vertex

v

, define

φ (v) : = R_{v} c a p_{p} (T (v)),

where

R_{o}

=1 by convention. (In particular,

φ (v) = R_{v}

v

is a leaf.) Then for any vertex

v

φ (v) = \sum_{v \to w} \frac{(R_{v} / R_{w}) φ (w)}{(1 + φ (w)^{s})^{1 / s}} .

Proof: If

w \neq o

, let

T^{'} (w)

be the tree rooted at the parent of

w

consisting of

T (w)

plus the edge between

w

and its parent. Then

\begin{matrix} φ (v) = R_{v} c a p_{p} (T (v)) & = & \sum_{v \to w} R_{v} c a p (T^{'} (w)) \end{matrix}

\begin{matrix} = & \sum_{v \to w} (R_{v} / R_{w}) \frac{R_{w} c a p_{p} (T (w))}{(1 + R (w)^{s} c a p_{p} (T (w))^{s})^{1 / s}} \end{matrix}

which gives the desired expression.

□

We now relate these computations to the system ( 3.10 ). In the following theorem,

f (\infty)

denotes

{liminf}_{x \to \infty} f (x)

and

s

denotes

p - 1

Theorem 3.2 Suppose that there exist

κ_{1} > 0

p = 1 + s > 1

and a collection of positive constants

{a_{v} : v \in V (T)}

such that for every

v \in V (T)

and

x \geq 0

\begin{matrix} f_{v} (x) \leq \frac{a_{v} x}{(1 + (κ_{1} x)^{s})^{1 / s}} . \end{matrix}

(3.13)

Then the solution to the system

x_{v} = \sum_{v \to w} f_{w} (x_{w})

with boundary conditions

x_{w} = \infty

when

w

is a leaf satisfies

\begin{matrix} x_{0} \leq \frac{c a p_{p} (T)}{κ_{1}}, \end{matrix}

(3.14)

where the resistances are given by

R_{v} = \prod_{0 \leq y \leq v} a_{y}^{- 1}

. Similarly, if

\begin{matrix} \frac{a_{v} x}{(1 + (κ_{2} x)^{s})^{1 / s}} \leq f_{v} (x) \end{matrix}

(3.15)

then

\begin{matrix} \frac{c a p_{p} (T)}{κ_{2}} \leq x_{0} . \end{matrix}

(3.16)

Proof: Let

g (v) = R_{v} c a p_{p} (T (v)) / κ_{2}

, with

g (v) = \infty

v \neq 0

is a leaf. We show by induction that

g (v) \leq x_{v}

for all

v

. If

v

is a leaf, this is true by definition. Assume

v

is not a leaf and, by induction, that

g (w) \leq x_{w}

for all

v \to w

. Applying the previous lemma gives

g (v) = \sum_{v \to w} \frac{(R_{v} / R_{w}) g (w)}{(1 + (κ_{2} g (w))^{s})^{1 / s}} .

By monotonicity of

x / (1 + (c x)^{s})^{1 / s}

, and the induction hypothesis, this is at most

\sum_{v \to w} \frac{(R_{v} / R_{w}) x_{w}}{(1 + (κ_{2} x_{w})^{s})^{1 / s}},

which is equal to

\sum_{v \to w} \frac{a_{w} x_{w}}{(1 + (κ_{2} x_{w})^{s})^{1 / s}} .

This is at most

\sum_{v \to w} f_{w} (x_{w})

by assumption, finishing the induction. An exactly analogous induction establishes that

x_{v} \leq G (v)

for all

v

, where

G (v) = R_{v} c a p_{p} (T (v)) / κ_{1}

. Setting

v = 0

now recovers the statement of the theorem.

□

With regard to sub-solutions, that is, to the system of inequalities ( 3.10 ), we have the following immediate corollary, used in Section 4 to analyze Ising models with free boundaries.

Corollary 3.3 Under the hypothesis ( 3.13 ), any solution to

x_{v} \leq \sum_{v \to w} f_{w} (x_{w})

satisfies

x_{0} \leq c a p_{p} (T) / κ_{1}

□

Although the finitary result in Theorem 3.2 is the most useful, the following corollary for infinite trees is more elegant. The corollary follows directly from the fact that

c a p_{p} (T)

is the decreasing limit of

c a p_{p} (T^{(N)})

, so we omit the details.

Corollary 3.4 Let

T

be infinite and locally finite, having no leaves except possibly the root. If

c a p_{p} (T) = 0

then there are no nontrivial solutions to ( 3.10 ) on

T

. If

c a p_{p} (T) > 0

then any such sub-solution

x_{v} \leq \sum_{v \to w}

satisfies

x_{0} \leq c a p_{p} (T) / κ_{1}

. Furthermore, there is a sub-solution with the property that

x_{0} \geq c a p_{p} (T) / κ_{2}

To see the value in what we have proved, we turn to some special cases.

Corollary 3.5 Suppose

f

satisfies

$(i)$ $f (x) = a x - Θ (x^{p})$ near 0 for some $p > 1$ ; $(i i)$ $f (x) / x$ is bounded away from $a$ except near zero; $(i i i)$ $f (x)$ is bounded away from zero except near zero.

Then there is a nontrivial sub-solution

x_{v} \leq \sum_{x \to w} f (x_{w})

on the vertices of

T

if and only if

c a p_{p} (T) > 0

with resistances

a^{- n}

at distance

n

from the root.

□

Remark: This condition is known to be related to many other conditions of interest. For example, it is sufficient that

T

have branching number greater than

a^{- 1}

and necessary that the branching number be at least

a^{- 1}

. For

p = 2

, it is equivalent to the transience of a homesick random walk with parameter

a^{- 1}

(see Lyons 1992).

Corollary 3.6 Suppose that

T

, an infinite, locally finite, leafless tree, is spherically symmetric, meaning that the degree of

v

depends only on

v

. Suppose

f_{v} = f_{| v |}

depends only on

| v |

as well. Assume the inequalities ( 3.13 ) and ( 3.15 ). Then there is a nonzero solution to

x_{v} = \sum_{v \to w} f_{w} (x_{w})

if and only if

{\sum_{n = 1}^{\infty}}^{n} \prod_{j = 1} \frac{1}{(a_{j} d_{j})^{s}} < \infty .

We use this in the next section with

s = 2

to obtain an exact summability criterion for phase transition of the Ising model on an arbitrary spherically symmetric tree. This refinesthe work of Lyons (1989), who computed the critical value but did not settle the behavior at criticality.

4 Plus boundary conditions

In this section

T

is an infinite tree with no leaves except possibly the root and

T^{(N)}

denotes the truncation to distance at most

N

from the root. We fix interaction strengths

{J_{w} : 0 \neq w \in V (T)}

satisfying ( 1.1 ), set

θ_{v} = tanh (β J_{v}))

, and consider the family of measures

P^{(N, +)}

of configurations of zeros and ones on

T^{(N)}

with plus boundary conditions.

The goal is to determine whether

P^{(N, +)} (η (0) = + 1)

converges to

1 / 2

or is bounded below by

1 / 2 + ε

N \to \infty

. This is accomplished in the following theorem, already stated in the introduction.

Theorem 2.2 Let

T

be any infinite, locally finite tree rooted at 0 and having no leaves except possibly 0. Let

{J_{v}}

be bounded interaction strengths, i.e., satisfying ( 1.1 ), and assign resistances

R_{v} = \prod_{0 < y \leq v} (tanh (β J_{y}))^{- 1}

as in ( 2.6 ). Then the decreasing limit

{lim}_{N \to \infty} P^{(N, +)} (η (0) = + 1)

is equal to

1 / 2

if and only if

c a p_{3} (T) = 0

The key to the proof of Theorem 2.2 and to the main results in each of the next two sections is the following recursive likelihood computation. Recall that

T^{(N)}

is the truncation of

T

N

generations. For any tree denote by

T (v)

the subtree rooted at

v

, so that for

| v | \leq N

, the tree

T^{(N)} (v)

has vertex set

{w \in V (T) : v \leq w, | w | \leq N}

ξ : \partial T \to {\pm 1}

is a boundary configuration, let

P^{ξ}

denote the Ising measure with boundary condition

ξ

and let

P_{v}^{(N, ξ)}

denote the Ising measure on

T^{(N)} (v)

whose boundary condition is

ξ_{| \partial T^{(N)} (v)}

Lemma 4.1 For each

v \neq o

let

θ v = tanh (β J_{v})

. Let

x_{v}^{(N)} = x_{v}^{(N, ξ)} = log [\frac{P_{v}^{(N, ξ)} (η (v) = + 1)}{P_{v}^{(N, ξ)} (η (v) = - 1)}]

be the log-likelihood ratio at the root given the boundary. Then for

| v | < N

x_{v}^{(N)} = \sum_{v \to w} f_{w} (x_{w}^{(N)}),

where

\begin{matrix} f_{v} (x) : = log [\frac{cosh (x / 2) + θ v sinh (x / 2)}{cosh (x / 2) - θ v sinh (x / 2)}] . \end{matrix}

(4.17)

Proof of Lemma 4.1 : Let

η

be a configuration on

T^{(N)} (v)

. If

| v | < N

then for each child

w

v

, let

η_{w}

be the restriction of

η

to the subtree

T^{(N)} (w)

. We may then write

W (η) = \prod_{v \to w} W (η_{w}) exp (η (v) η (w) β J_{w}) .

Let

S

be the set of children of

v

. Summing over all vectors

{ε_{w} : w \in S}

\pm 1

's, and within that, over all

η

coinciding with

ε

S

, and writing

Z

for the normalizing factor (the sum of weights of all configurations), we obtain

\begin{matrix} P_{v}^{(N, ξ)} (η (v) = + 1) & = & Z^{- 1} \sum_{ε, η} \prod_{v \to w} [W (η_{w}) exp (η (w) β J_{w})] \end{matrix}

\begin{matrix} = & Z^{- 1} \prod_{v \to w} \sum_{η_{w} : T^{(N)} (w) \to {\pm 1}} W (η_{w}) exp (η (w) β J_{w}) \end{matrix}

\begin{matrix} = & Z^{- 1} \prod_{v \to w} [e^{β J_{w}} P_{w}^{(N, ξ)} (η (w) = 1) + e^{- β J_{w}} P_{w}^{(N, ξ)} (η (w) = - 1)] . \end{matrix}

Similarly,

P_{v}^{(N, ξ)} (η (v) = - 1) = Z^{- 1} \prod_{v \to w} [e^{- β J_{w}} P_{w}^{(N, ξ)} (η (w) = + 1) + e^{β J_{w}} P_{w}^{(N, ξ)} (η (w) = - 1)] .

Divide these expressions, and then divide top and bottom by

\prod_{v \to w} P_{w}^{(N, ξ)} (η (w) = - 1),

to obtain

\begin{matrix} \frac{P_{v}^{(N, ξ)} (η (v) = + 1)}{P_{v}^{(N, ξ)} (η (v) = - 1)} & = & \prod_{v \to w} \frac{e^{(β J_{w} + x_{w}^{(N)})} + e^{- β J_{w}}}{e^{(- β J_{w} + x_{w}^{(N)})} + e^{β J_{w}}} \end{matrix}

\begin{matrix} = & \prod_{v \to w} \frac{cosh (β J_{w}) (e^{x_{w}^{(N)}} + 1) + sinh (β J_{w}) (e^{x_{w}^{(N)}} - 1)}{cosh (β J_{w}) (e^{x_{w}^{(N)}} + 1) - sinh (β J_{w}) (e^{x_{w}^{(N)}} - 1)} . \end{matrix}

Next, divide numerator and denominator by

cosh (β J_{w})

and recall that

tanh (β J_{w}) = θ

It follows that the log of the likelihood ratio above satisfy

\begin{matrix} x_{v}^{(N)} = \sum_{v \to w} log \frac{e^{x_{w}^{(N)}} + 1 + θ (e^{x_{w}^{(N)}} - 1)}{e^{x_{w}^{(N)}} + 1 - θ (e^{x_{w}^{(N)}} - 1)} . \end{matrix}

(4.18)

Finally, divide numerator and denominator by

e^{x_{w}^{(N)} / 2}

to complete the proof.

□

Proof of Theorem 2.2 : Specialize to plus boundary conditions. Thus we write

P_{v}^{(N, +)}

for

P_{v}^{(N, ξ)}

where

ξ \equiv + 1

. Let

x_{v}^{(N)} = x_{v}^{(N, +)} = log (\frac{P_{v}^{(N, +)} (η (v) = + 1)}{P_{v}^{(N, +)} (η (v) = - 1)})

be the log-likelihood ratio of plus to minus at the root of the subtree

T^{(N)} (v)

. Lemma 4.1 shows that

x_{v}^{(N)} = \sum_{v \to w} f_{w} (x_{w}^{(N)}),

with

f_{v}

as in equation ( 4.17 ). Write

θ

for

θ v

and differentiate

f_{v}

\begin{matrix} f_{v}^{'} (x) = \frac{θ}{{cosh}^{2} (x / 2) - θ^{2} {sinh}^{2} (x / 2)} = \frac{θ}{1 + (1 - θ^{2}) {sinh}^{2} (x / 2)}, \forall x > 0 . \end{matrix}

(4.19)

It is also clear that the denominator in ( 4.19 ) is increasing in

x

and has the expansion

1 + (1 - θ^{2}) x^{2} / 4 + O (x^{3})

near 0. Thus

f_{v} (x)

is a concave function of

x > 0

. Inverting and integrating, we also see that the Taylor expansion of

f_{v}

near 0 has the form

\begin{matrix} f_{θ} (x) = f_{v} (x) = θ x - \frac{θ (1 - θ^{2})}{12} x^{3} + O (x^{4}) . \end{matrix}

(4.20)

Another consequence of ( 4.19 ) is that

f_{v} (x)

is an odd function of

x

. Claim:there are continuous functions

κ_{2} (θ) \geq κ_{1} (θ) > 0

such that

\begin{matrix} \frac{θ x}{(1 + κ_{2} x^{2})^{1 / 2}} \leq f_{v} (x) \leq \frac{θ x}{(1 + κ_{1} x^{2})^{1 / 2}} . \end{matrix}

(4.21)

Indeed, if we establish this, then the boundedness assumption ( 1.1 ) implies that constants

κ_{1}

and

κ_{2}

may be chosen so that ( 4.21 ) holds for all

v

with

θ v

in place of

θ

. It then follows from Theorem 3.2 that

x_{0}^{(N)}

is bounded between

c a p_{3} (T^{(N)}) / κ_{2}

and

c a p_{3} (T^{(N)}) / κ_{1}

for all

N

. Taking decreasing limits finishes the proof of the theorem. It remains to prove the claim.

The choice of

κ_{2}

is easy. When

J_{v}

is bounded away from 0 and infinity,

θ v

and

1 - θ v

are bounded away from 0, so the

x^{3}

term in ( 4.20 ) is bounded away from zero. Thus

δ (θ) > 0

and

κ_{2}^{'} (θ)

may be chosen so that ( 4.21 ) holds for

x \leq δ

. Since the

O (x^{4})

remainder term varies continuously with

p

, the choices of

δ

and

κ_{2}^{'}

can be made continuously in

p

as well.

Now note that

{sup}_{x} (x / (1 + (κ x)^{2})^{1 / 2}) < κ^{- 1}

. Let

f_{θ}

denote

f_{v}

for

v

with

θ_{v} = θ

. Letting

M (θ) = f_{θ} (δ (θ))

and choose

κ_{2} (θ) \geq κ_{2}^{'} (θ)

so that

M (θ) > κ_{2} (θ)^{- 1}

gives a choice of

κ_{2} (θ)

varying continuously with

p

and satisfying ( 4.21 ).

To choose

κ_{1}

, we may again use the expansion near zero to get a

κ_{1}^{*} (θ)

that works for

x \leq δ

. We It is shown later that each

f_{θ}

is concave (Lemma 6.3 below). Also,

f_{θ}

is bounded by

log \frac{1 + θ}{1 - θ}

. Thus

f_{θ} \leq (θ - ε) x \land M

for some

ε, M > 0

and all

x \geq δ

. On the other hand,

θ x / (1 + (κ x)^{2})^{1 / 2}

converges to

θ x

uniformly on the interval

[δ, M / θ]

κ \to 0

. Thus

κ_{1} (θ) \leq κ_{1}^{*} (θ)

may be chosen so that

θ x / (1 + (κ_{1} x)^{2})^{1 / 2} \geq (θ - ε) x \land M

for all

x \geq δ

. Since the right-hand side is an upper bound for

f_{θ}

[δ, \infty)

, and since the choice of

κ_{1}

is evidently continuous in

θ

, this finishes the proof of the theorem.

□

We conclude this section with a discussion of the boundedness condition ( 1.1 ). Given any tree

T

with associated interactions

{J (e) : e \in E (T)}

a new tree

T^{'}

may be constructed by subdividing edges of

T

according to the following scheme. Fix an

ε > 0

. Replace each edge

e

with

θ_{e} < ε

by a series of

n

edges

e (1), \dots, e (n)

with

θ_{e (j)} = θ_{e}^{1 / n}

, where

n

is the least integer making

θ_{e}^{1 / n}

greater than

ε

From the error propagation description of the Ising measure, we see that the measure on

{\pm 1}^{V (T)}

gotten by restricting the Ising measure on

T^{'}

to the vertices of

T

coincides with the Ising measure on

T

. Distances in

T^{'}

no longer coincide with distances in

T

, but it is easy to see that the various definitions of phase transition in this article are unchanged if limits on

T^{'}

are taken with respect to distances in

T

. The associated resistor network to

T^{'}

may be described as follows. Each edge not subdivided retains the same resistance. A subdivided edge with resistance

R (e) = A / θ_{e}

is replaced by

n

edges in series, of resistances

A θ_{e}^{- j / n}

for

j = 1, \dots, n

. Since

θ_{e}^{1 / n} < ε^{1 / 2}

, the total resistance is less than

1 / (1 - \sqrt{ε})

times the greatest resistance, which is

A / θ_{e}

. Thus the resistance of the new network is equal to the old resistance up to a bounded factor, and hence has capacity within a bounded factor of the original capacity. We conclude that no generality is lost by assuming

J_{v}

to be bounded away from zero.

There is some generality lost in assuming

J_{v}

to be bounded above, but for good reason, as shown by the following example. Let

T

be a spherically symmetric tree with

| T_{n} | \approx n^{α} 2^{n}

for some

α > 1 / 2

. As seen in Corollary 2.4 , there is a phase transition on

T

with constant interaction strength satisfying

θ = 1 / 2

. Now replace each edge in generation

n

n

edges having

θ_{e} = 2^{- 1 / n}

. The resistance of each new series of edges in generation

n

is of order

n

times the old resistance, so when

α \leq 3 / 2

, the new tree has zero capacity.Thus the capacity criterion breaks down when the interaction strengths are allowed to have

θ_{v} \to 1

, i.e.,

J_{v} \to \infty

5 Free boundary conditions

The question we ask in this section is: if you generate a configuration on

T^{(N)}

from the free boundary measure, then look only at the boundary, do you have non-vanishing information about the root as

N \to \infty

? To formalize this, let

ξ

be the random boundary configuration induced by the free measure

P^{(N)}

on configurations on all of

T^{(N)}

. In the notation of Lemma 4.1 , let

X_{v}^{(N)} : = x_{v}^{(N, ξ)}

be the log-likelihood ratio of plus to minus at

v

given the boundary. It is important to keep track of the spaces on which these are defined, so we re-iterate:

$x_{v}^{(N)}$ is a map from configurations on $T^{(N)} (v)$ to real numbers. By natural projection, it may be thought of as a map from configurations on $T$ to reals.
$X_{v}^{(N)}$ is a random variable on $Ω (T_{v}^{(N)})$ , which we may view naturally as a projection of $Ω (T^{(N)})$ , or by extension on $Ω (T)$ .
$X_{v}^{(N)}$ is measurable with respect to $ℱ_{v}^{(N)}$ , which we define to be the $σ$ -field generated by boundary values ${η (y) : y \in T_{v}^{(N)}}$ .

We want to know whether the

P^{(N)}

law of

X_{0}^{(N)}

(the free law) converges weakly to a point mass 0 as

N \to \infty

. Evans et al (2000) showed, in the case of constant interaction strength

J

, that

X_{0}^{(N)}

does not go to zero when

T

has positive

L^{2}

capacity with resistances

θ^{- 2 n}

, where

θ = tanh (J / t)

. As mentioned in the introduction, they (as well as Ioffe (1996) have results in the other direction which leave the critical case open. We sharpen this by showing that zero capacity implies

X_{0}^{(N)} \overset{D}{⟶} 0

Theorem 2.1 Let

T

be an infinite, locally finite tree, rooted at o, with no leaves except possibly at o and interaction strengths

J_{v}

satisfying ( 1.1 ) and set

θ v = tanh (β J_{v}))

. Supposethat

c a p_{2} (T) = 0

with resistances assigned as in ( 2.6 ) with

k = 2

. Then

X_{0}^{(N)}

converges in distribution to 0.

Proof of Theorem 2.1 : By Lemma 4.1 , when

| v | < N

\begin{matrix} X_{v}^{(N)} = \sum_{v \to w} f_{w} (X_{w}^{(N)}), \end{matrix}

(5.22)

holds for every sample, with

f_{w}

as in equation ( 4.17 ). To make sense of this functional recursion, we will derive from it a system of real inequalities:

\begin{matrix} m_{v}^{(N)} \leq \sum_{v \to} \frac{θ_{w}^{2} m_{w}^{(N)}}{1 + κ m_{w}^{(N)}} . \end{matrix}

(5.23)

The quantity

m_{v}^{(N)}

will be an expectation of

X_{v}^{(N)}

but it is not obvious what measure should be used to take the expectation. Define the measures

Q_{v}^{N +}

(respectively

Q_{v}^{N -}

) on the

σ

-field

ℱ_{v}^{(N)}

of boundary values by letting

Q_{v}^{N +} (ξ) : = P_{v}^{(N)} (η : η_{| \partial T_{v}^{(N)}} = ξ | η (v) = + 1)

be the conditional distribution of the free boundary given a plus at

v

(respectively, given a minus at

v

). Define

m_{v}^{(N)} : = \int X_{v}^{(N)} d Q_{v}^{N +} = - \int X_{v}^{(N)} d Q_{v}^{N -} .

The properties of the measures

Q_{v}^{N \pm}

summarized in the following lemmas make these appropriate for the study of the free boundary.

Lemma 5.1 For any

v

with

| v | < N

Q_{v}^{N +} = \prod_{v \to w} [\frac{(1 + θ_{w})}{2} Q_{w}^{N +} + \frac{(1 - θ_{w})}{2} Q_{w}^{N -}] .

In particular, the projection of

Q_{v}^{N +}

onto boundary configurations on

T^{(N)} (w)

\frac{(1 + θ_{w})}{2} Q_{w}^{N +} + \frac{(1 - θ_{w})}{2} Q_{w}^{N -} .

□

Lemma 5.2 For any odd function

φ

\int φ (X_{v}^{(N)}) d Q_{v}^{N +} = \int φ (| X_{v}^{(N)} |) tanh (| X_{v}^{(N)} | / 2) d P_{v}^{(N)} .

Lemma 5.3 There is a positive, continuous function

κ

such that when

f_{θ}

is defined as in ( 4.17 ) with

θ = θ v

, then

\int f_{θ} (X_{v}^{(N)}) d Q_{v}^{N +} \leq θ \frac{\int X_{v}^{(N)} d Q_{v}^{N +}}{1 + κ (θ) \int X_{v}^{(N)} d Q_{v}^{N +}} .

To finish the proof from these lemmas, use ( 5.22 ) and Lemma 5.1 to evaluate

\begin{matrix} m_{v}^{(N)} & = & \sum_{v \to w} \int f_{w} (X_{w}^{(N)}) d Q_{v}^{N +} \end{matrix}

\begin{matrix} = & \sum_{v \to w} \int f_{w} (X_{w}^{(N)}) d ((1 + θ_{w}) Q_{w}^{N +} + (1 - θ_{w}) Q_{w}^{N -}) \end{matrix}

\begin{matrix} = & \sum_{v \to w} \int θ_{w} f_{w} (X_{w}^{(N)}) d Q_{w}^{N +} . \end{matrix}

(5.24)

Apply Lemma 5.3 to see that this is at most

\sum_{v \to w} \frac{θ_{w}^{2} m_{v}^{(N)}}{1 + κ (θ v) m_{v}^{(N)}} .

By continuity of

κ (θ)

and the boundedness assumption ( 1.1 ), we arrive at ( 5.23 ). Theorem 3.2 now applies to show that

m_{0}^{(N)} \leq \frac{c a p_{2} (T^{(N)})}{κ}

with resistances as in the hypothesis of the theorem. Hence

c a p_{2} (T) = 0

implies

m_{0}^{(N)} \to 0

N \to \infty

. Finally, by Lemma 5.2 , this implies

X_{0}^{(N)} \overset{D}{⟶} 0

N \to \infty

, finishing the proof.

□

It remains to prove the lemmas. Lemma 5.1 is immediate from the Markov property.

Proof of Lemma 5.2 : We first compare

Q_{v}^{N +}

to the boundary measure induced by the free measure

P_{v}^{(N)}

. We claim that

\begin{matrix} \frac{d Q_{v}^{N +}}{d P_{v}^{(N)}} = 1 + tanh (X_{v}^{(N)} / 2) . \end{matrix}

(5.25)

Indeed, from Bayes' rule, one gets

\frac{d Q_{v}^{N +}}{d P_{v}^{(N)}} = \frac{P_{v}^{(N)} (η (v) = + 1 | ℱ_{v}^{(N)})}{P_{v}^{(N)} (η (v) = + 1)} .

The denominator is

1 / 2

by symmetry, while the numerator is

exp (X_{v}^{(N)}) / (1 + exp (X_{v}^{(N)})) = (1 + tanh (X_{v}^{(N)} / 2)) / 2

by definition of

X_{v}^{(N)}

. This proves the claim. Now if

φ

is any odd function, then

φ (x) = (φ (x) - φ (- x)) / 2

, and thus

\begin{matrix} \int φ (X_{v}^{(N)}) d Q_{v}^{N +} & = & \int \frac{1}{2} (φ (X_{v}^{(N)}) - φ (- X_{v}^{(N)})) d Q_{v}^{N +} \end{matrix}

\begin{matrix} = & \int (φ (X_{v}^{(N)}) - φ (- X_{v}^{(N)})) \frac{e^{X_{v}^{(N)} / 2}}{e^{X_{v}^{(N)} / 2} + e^{- X_{v}^{(N)} / 2}} d P_{v}^{(N)} \end{matrix}

\begin{matrix} = & \int φ (X_{v}^{(N)}) \frac{e^{X_{v}^{(N)} / 2} - e^{- X_{v}^{(N)} / 2}}{e^{X_{v}^{(N)} / 2} + e^{- X_{v}^{(N)} / 2}} d P_{v}^{(N)}, \end{matrix}

yielding the desired conclusion.

□

Proof of Lemma 5.3 : Abbreviate the notation by writing

X

for

X_{v}^{(N)}

E

for integration against

P_{v}^{(N)}

and

E_{+}

for integration against

Q_{v}^{N +}

. First, for any

c > 0

, the product

E_{+} f_{θ} (X) (1 + c E_{+} X) = E_{+} f_{θ} (X) + c (E_{+} f_{θ} (X)) (E_{+} X)

is equal, by Lemma 5.2 , to the sum

E [f_{θ} (| X |) tanh | X / 2 |] + E [f_{θ} (| X |) tanh | X / 2 |)] \cdot E [c | X | tanh | X / 2 |] .

Since the functions

f_{θ} (x) tanh (x / 2)

and

c x tanh (x / 2)

are both nondecreasing on

[0, \infty)

, they are positively correlated functions of

| X |

(under

P_{v}^{(N)}

or any other law), and hence

\begin{matrix} (E_{+} f_{θ} (X)) (1 + c E_{+} X) & \leq & E f_{θ} (| X |) tanh | X / 2 | + E (c | X | f_{θ} (| X |) {tanh}^{2} | X / 2 |) \end{matrix}

\begin{matrix} = & E [f_{θ} (| X |) tanh | X / 2 | (1 + c | X | tanh | X / 2 |)] . \end{matrix}

Recall that

tanh (x) = x - Θ (x^{3})

. Refer to the Taylor expansion for

f_{θ} = f_{v}

in equation ( 4.20 ) to see that for

κ (θ)

sufficiently small, there is a range

x \in [0, δ]

for which

\begin{matrix} f_{θ} (x) (1 + κ (θ) x tanh (x / 2)) < θ x . \end{matrix}

(5.26)

Since

f_{θ}

is itself bounded and less than

θ x - ε (θ) x

[δ, \infty)

, we may choose

κ (θ)

smaller if necessary so that ( 5.26 ) holds for all

x \geq 0

. Clearly the choice of

κ

can be made continuously in

θ

. It follows that

(E_{+} f_{θ} (X)) (1 + κ (θ) E_{+} X) \leq E θ | X | tanh | X / 2 | = θ E_{+} X

by Lemma 5.2 . Dividing by

(1 + κ (θ) E_{+} X)

proves the lemma.

□

6 Spin-glasses

Let

P_{v}^{(N, 0)}

denote the spin-glass measure

P^{s g}

on configurations on the tree

T^{(N)} (v)

(see Section 1 for definitions). Our object in this section is to determine when

P_{0}^{(N, s g)} (η (0) = + 1 | ℱ^{(N)})

converges in distribution to 0, where

ℱ^{(N)} = ℱ_{0}^{(N)}

is the

σ

-field generated by boundary values on

T^{(N)}

. By the Markov random field property (or by the definitions of

P

and

P^{s g}

), the measures

P^{(N)}

and

P^{(N, s g)}

agree when conditioned on the boundary, so the functions

X_{v}^{(N)}

of the previous section compute conditional probabilities with respect to

P^{(N, s g)}

. Thus our task is to see when

X_{0}^{(N)} \overset{D}{⟶} 0

under the laws

P^{(N, s g)}

Theorem 2.5 Let

T

be an infinite, locally finite tree, rooted at 0, with no leaves except possibly at 0 and interaction strengths

J_{v}

satisfying ( 1.1 ) and set

θ_{v} = tanh (β J_{v})

. Then

X_{0}^{(N)} \overset{D}{⟶} 0

under the spin-glass measure if and only if

c a p_{2} (T) = 0

with resistances

R_{v} = \prod_{y \leq v} θ_{y}^{- 2}

as assigned in ( 2.6 ).

Proof: The structure of the proof is similar to that of Theorem 2.1 . We begin with equation ( 5.22 ):

X_{v}^{(N)} = \sum_{v \to w} f_{w} (X_{w}^{(N)}) .

This time we have unconditional independence of boundary values instead of conditional independence, so instead of

m_{v}^{(N)}

we work with

U_{v}^{(N)} : = (X_{v}^{(N)})^{2}

and the mean

u_{v}^{(N)} : = \int (X_{v}^{(N)})^{2} d P_{v}^{(N, s g)},

where the integrating measure in this case is just i.i.d. fair coin-flips on the boundary of

T^{(N)} (v)

. In place of Lemma 5.1 we have the observation that the random variables

X_{w}^{(N)}

have mean zero and are independent as

w

ranges over the children of a fixed

v

. Lemmas 5.2 and 5.3 are replaced by the following two lemmas. Define

g_{v} (x) : = (f_{v} (\sqrt{x}))^{2} .

Lemma 6.1 For all

v

and all

N > | v |

E (U_{v}^{(N)})^{2} \leq 3 (E U_{v}^{(N)})^{2} .

Lemma 6.2 There are continuous functions

κ_{2} (c, θ v) \geq κ_{1} (c, θ v) > 0

such that for any random variable

V

satisfying

E V^{2} \leq c (E V)^{2}

, one has

\begin{matrix} h_{2} (E V) \leq E g_{v} (V) \leq h_{1} (E V), \end{matrix}

(6.27)

with

h_{i} (x) = θ^{2} v x / (1 + κ_{i} (c, θ_{v}) x)

From these two lemmas the proof is finished as follows. Let

E

denote expectation with respect to i.i.d. unbiased (spin-glass) boundary conditions. Since each

f_{v}

is an odd function, the quantities

f (X_{w}^{(N)})

are independent mean-zero as

w

varies over the children of

v

, which gives rise to the recursive formula

\begin{matrix} u_{v}^{(N)} & = & E (X_{v}^{(N)})^{2} \end{matrix}

\begin{matrix} = & E {(\sum_{v \to w} f_{v} (X_{w}^{(N)}))}^{2} \end{matrix}

\begin{matrix} = & \sum_{v \to w} E f_{v} (X_{w}^{(N)})^{2} \end{matrix}

\begin{matrix} = & \sum_{v \to w} E g_{v} (U_{w}^{(N)}) . \end{matrix}

Apply Lemma 6.2 with

V = U_{v}^{(N)}

and

c = 3

(obtaining the hypothesis from Lemma 6.1 ), to get

\sum_{v \to w} h_{2} (u_{w}^{(N)}) \leq u_{v}^{(N)} \leq \sum_{v \to w} h_{1} (u_{w}^{(N)}) .

By continuity and the boundedness assumption ( 1.1 ), we may take

κ_{i}

in the definition of

h_{i}

to be constants independent of

v

. By Theorem 3.2 we see that

{lim}_{N \to \infty} u_{0}^{(N)}

is estimated up to a constant factor by

c a p_{2} (T)

with resistances as stated in the hypothesis of the theorem.

Since

X_{0}^{(N)}

has mean zero and is bounded by

\sum_{0 \to v} log [(1 + θ v) / (1 - θ v)]

, it follows that the random variables

X_{0}^{(N)}

converge in distribution to 0 if and only if their variances

u_{0}^{(N)}

go to zero. This completes the proof of Theorem 2.5 .

□

It remains to prove Lemmas 6.1 and 6.2 . Before proving Lemma 6.1 , we record some preliminary facts.

Lemma 6.3 Suppose

f

is a differentiable, weakly increasing and concave function on

[0, \infty)

, with

f (0) = 0

. Then

x^{2} \circ f \circ \sqrt{x}

is concave.

Proof: Let

φ (x) = f (x_{0}) + (x - x_{0}) f^{'} (x_{0})

be the tangent line for

f

x_{0}

. Concavity implies that

φ (x) \geq f (x)

for all

x \geq 0

and that

h^{'} (x_{0}) \leq f (x_{0}) / x_{0}

. Thus

φ (x) = a x + b

with

b \geq 0

, whence

x^{2} \circ φ \circ \sqrt{x}

is a concave support function, lying above

x^{2} \circ f \circ \sqrt{x}

withequality at

x_{0}^{2}

. We conclude that

x^{2} \circ f \circ \sqrt{x}

is the minimum of a family of concave functions.

□

Lemma 6.4 Let

g : [0, \infty) \to [0, \infty)

be concave with

g (0) = 0

, and let

Y

be a nonnegative random variable with positive finite variance. Then

\begin{matrix} \frac{E [g (Y)^{2}]}{[E g (Y)]^{2}} \leq \frac{E Y^{2}}{(E Y)^{2}} . \end{matrix}

(6.28)

Proof: Let

Z = Y / E Y

and

h (z) = g (z E Y) / E (g (Y))

. Then

E Z = E h (Z) = 1

, so there must exist

z_{1}, z_{2} > 0

such that

h (z_{1}) \geq z_{1}

and

h (z_{2}) \leq z_{2}

. We also may assume that

h (z)

is not identically equal to

z

, and thus by concavity there is a unique fixed point

x > 0

for which

h (x) = x

. For any

z \geq 0

| h (z) - x | \leq | z - x |,

and therefore,

E [h (Z)^{2}] = E (h (Z) - x)^{2} + 2 x - x^{2} \leq E (Z - x)^{2} + 2 x - x^{2} = E Z^{2},

proving the lemma.

□

Lemma 6.5 For any non-negative random variable

X \in L^{4}

, and any concave function

f

with

f (0) = 0

\frac{E f^{4} (X)}{(E f^{2} (X))^{2}} \leq \frac{E X^{4}}{(E X^{2})^{2}} .

Proof: by Lemma 6.3 , the function

g : = x^{2} \circ f \circ \sqrt{x}

is concave. Applying Lemma 6.4 to the function

g

and the random variable

Y = X^{2} \in L^{2}

gives

\frac{E f^{4} (X)}{(E f^{2} (X))^{2}} = \frac{E g^{2} (X)}{[E g (X)]^{2}} \leq \frac{E X^{2}}{(E X)^{2}} = \frac{E X^{4}}{(E X^{2})^{2}},

proving the lemma.

□

Proof of Lemma 6.1 : Recall the definitions of

U_{v}^{(N)}

and

u_{v}^{(N)}

and define the fourth moment

s_{v}^{(N)}

$U_{v}^{(N)} = (X_{v}^{(N)})^{2}$ ; $u_{v}^{(N)} = E U_{v}^{(N)}$ ; $s_{v}^{(N)} = E (U_{v}^{(N)})^{2} = E (X_{v}^{(N)})^{4}$ .

For any

v

, the random variables

{f_{w} (X_{w}^{(N)}) : v \to w}

are independent with mean zero, so any monomial of these will have mean zero unless all exponents are even. The basic recursion ( 5.22 ) yields

\begin{matrix} u_{v}^{(N)} & = & E {(\sum_{v \to w} f_{w} (X_{w}^{(N)}))}^{2} \end{matrix}

\begin{matrix} = & \sum_{v \to w} E f_{w} (X_{w}^{(N)})^{2} . \end{matrix}

Hence

\begin{matrix} (u_{v}^{(N)})^{2} = \sum_{v \to w} {(E f_{w} (X_{w}^{(N)})^{2})}^{2} + \sum_{v \to {w, w^{'}}} 2 E f_{w} (X_{w}^{(N)})^{2} E f_{w^{'}} (X_{w^{'}}^{(N)})^{2} . \end{matrix}

(6.29)

The fourth power expands similarly:

\begin{matrix} s_{v}^{(N)} & = & E {(\sum_{v \to w} f_{w} (X_{w}^{(N)}))}^{4} \end{matrix}

\begin{matrix} = & \sum_{v \to w} E f_{w} (X_{w}^{(N)})^{4} + \sum_{v \to {w, w^{'}}} 6 E f_{w} (X_{w}^{(N)})^{2} E f_{w^{'}} (X_{w^{'}}^{(N)})^{2} . \end{matrix}

(6.30)

It is required to show that

s_{v}^{(N)} \leq 3 (u_{v}^{(N)})^{2}

Proceed by induction on

N - | v |

. First suppose

N - | v | = 1

and that

v

has

d

children.

Then

X_{v}^{(N)}

is the sum of

d

independent mean-zero random variables, each equal to

\pm log (p / (1 - p))

. In this case,

s_{v}^{(N)} / (u_{v}^{(N)})^{2} = 3 - 2 / d < 3

. Now suppose

N - | v | > 1

. By induction,

s_{w} \leq 3 u_{w}^{2}

for each child

w

v

. Applying Lemma 6.5 , we see that for each such

w

E f_{w} (X_{w}^{(N)})^{4} \leq 3 (E f_{w} (X_{w}^{(N)})^{2})^{2} .

Plugging this into equation ( 6.30 ) and comparing with equation ( 6.29 ) shows that

s_{v}^{(N)} \leq 3 (u_{v}^{(N)})^{2}

, completing the induction.

□

Proof of Lemma 6.2 : We observed in the proof of Lemma 6.5 that

g_{v}

is concave; it is bounded as well. For the upper bound, first note that

g_{v} (x) \leq h (x) : = \frac{θ^{2} v x}{1 + κ (θ_{v}) x}

for some

κ

varying continuously with

θ v

. The proof of this is same as the proof of ( 4.21 ), using the Taylor expansion

g_{v} (x) = θ_{v} x - (1 + θ v)) θ v (1 - θ_{v}) x^{2} / 6 + O (x^{3})

together with boundedness and concavity of

g_{v}

. Jensen's inequality gives

E g_{v} (V) \leq E h (V) \leq h (E V)

which proves the upper bound with

κ_{1} = κ

For the lower bound, since

g_{v} (x) = θ v x - O (x^{2})

near 0, we have

g_{v} (x) \geq θ v x - λ x^{2}

for some

λ

and all

x

in some interval

[0, δ]

. Choosing

λ

larger if necessary, we can ensure that

g_{v} (x) \geq θ v x - λ x^{2}

for all

x \geq 0

. Hence

E g_{v} (V) \geq θ^{2} v E V - c λ (E V)^{2} .

Choose

δ (θ v) > 0

so that the right-hand side is positive for

x \in (0, δ (θ v))

. Choose

κ_{2} (θ v)

so that

\frac{θ^{2} v x}{1 + κ_{2} (θ v) x} \leq [θ^{2} v x - λ x^{2}] \land \frac{g_{v} (δ / 2)}{4 c} .

This satisfies ( 6.27 ) when

E V \leq δ

. But when

E V > δ

, then hypothesis on

V

implies that

P (V > δ / 2) \geq 1 / (4 c)

and therefore that

E g_{v} (V) \geq g_{v} (δ / 2) / (4 c)

. Hence ( 6.27 ) is valid for all

x \geq 0

. Together with the evident continuous dependence of

κ_{i}

θ v

, this proves the lemma.

□

7 Concluding remarks

Although we have in general no explicit probabilistic interpretation of

L^{p}

capacities, in the case of integer values of

p

there is a more probabilistic formulation. Positive

L^{p}

capacity is equivalent to the existence of a probability measure

μ

\partial T

such that

p

independent paths picked from

μ

will coincide along a path of finite average resistance. This corresponds to the representation of

L^{p}

-energy as a

p

-fold integral over

\partial T

Finally, we remark that other statistical mechanical models lead to recursions similar to ( 5.22 ) but with functions

f_{v}

that are not necessarily concave. The Potts model with

1 < q < 2

is essentially similar to the Ising model, but when

q > 2

, the functions

f_{v}

are not concave and qualitatively different behavior arises. See Häggström (1996) for a discussion of this as pertains to the random cluster model, and Pemantle and Steif (1999) for the Heisenberg and other continuous-state models on general trees.

Acknowledgement. Much of the research presented here was performed at the Mittag Leffler Institute. We are grateful to E. B. Dynkin for telling us about the importance of

L^{p}

capacities in connection with superprocesses.

References

Bleher, P. M., Ruiz, J. and Zagrebnov V. A. (1995) On the purity of limiting Gibbs state for the Ising model on the Bethe lattice, J. Stat. Phys 79, 473–482.
Chayes, J. T., Chayes, L., Sethna, J. and Thouless, D. (1986). Comm. Math. Phys. 106 41 89.
Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (2000). Broadcasting on trees and the Ising Model, Ann. Appl. Prob. 10, 410–433.
H. O. Georgii (1988). Gibbs Measures and Phase Transitions. W. de Gruyter, Berlin.
Häggström, O. (1996). The random-cluster model on a homogeneous tree. Probab. Th. Related Fields 104, 231–253.
Ioffe, D. (1996a). A note on the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys. 37, 137–143.
Ioffe, D. (1996b) Extremality of the disordered state for the Ising model on general trees. Trees (Versailles, 1995), 3–14, Progr. Probab. 40, Birkhäuser, Basel.
Lyons, R. (1989). The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys. 125 337 353.
Lyons, R. (1992). Random walks, capacity, and percolation on trees. Ann. Prob. 20 2043 2088. Murakami, A. and Yamasaki, M. (1992). Nonlinear potentials on an infinite network. Mem. Fac. Sci. Shimane Univ. 26, 15–28
Pemantle, R. and Steif, J. E. (1999). Robust phase transitions for Heisenberg and other models on general trees. Ann. Probab. 27, 876–912.
Preston, C. J. (1974). Gibbs states on countable sets. Cambridge University Press: Cambridge.
Preston, C. J. (1976). Random fields. Lecture notes in Mathematics, vol. 534. Springer: Berlin.
Soardi, P. M. (1993). Morphisms and currents in infinite nonlinear resistive networks. Potential Anal. 2, 315–347.
Soardi, P. M. (1994) Potential Theory on Infinite Networks. Lect. Notes Math. 1590, Springer, Berlin.