A Capacity Criterion for Four-State Potts Reconstruction on Trees

1 Introduction

Let T be an infinite locally finite rooted tree with root \rho. Assume that every vertex has at most B children, where B is a fixed positive integer; vertices with zero or one child are allowed. Write |v| for the depth of a vertex, \children(v) for its children, and L_n=\{v:|v|=n\}. The tree is deterministic and known to the observer.

Fix 0<\lambda<1. Give the root a uniform spin in [4], and transmit spins independently along edges conditional on their parent spins, using

For the uniform probability vector \unif=(1/4,1/4,1/4,1/4), put

Data processing makes a_n nonincreasing. We say that reconstruction occurs if its limit a_\infty(T,\lambda) is positive.

A nonnegative flow \theta to infinity assigns a nonnegative number to each edge, with incoming flow equal to the sum of outgoing flows at every nonroot vertex. Its mass is

For an edge e, let |e| be the depth of its child endpoint, and let \partial T denote the infinite rays from the root. Define

The zero flow is allowed. This is the L^3 nonlinear capacity with edge resistances \lambda^{-2|e|}: in the standard L^p normalization, the path potential has exponent p-1 [8, Section 2].

There is no regularity or growth-rate assumption on the tree. In particular, the criterion applies at the exponential Kesten–Stigum boundary, where an exponential-growth test alone does not settle the question. The exclusion of \lambda=1 is essential: an infinite ray then reconstructs perfectly, whereas its capacity in (1.3) is zero.

History and relation to earlier work

The second-eigenvalue scale in tree broadcasting originates in the branching-process work of Kesten and Stigum [3]. For a regular tree with d children per vertex, the corresponding bound guarantees reconstruction when d\lambda^2>1 [5]. Evans, Kenyon, Peres, and Schulman [1] developed the relation between broadcasting, the Ising model, and electrical capacity. For Potts channels, Sly [9] proved sharpness of the second-eigenvalue bound for three states on regular trees of sufficiently large degree, including nonreconstruction at equality, and proved nonsharpness for at least five states. Mossel, Sly, and Sohn [6] established three- and four-state nonreconstruction at and below the bound for Galton–Watson families of sufficiently large mean degree, under hypotheses covering regular and Poisson offspring. At four states the quadratic correction vanishes, making higher-order terms decisive [9, 6].

Pemantle and Peres [8] formulated critical Ising criteria on arbitrary trees using nonlinear capacities and concave recursions. Their free-boundary criterion uses L^2 capacity with squared channel resistances, whereas their plus-boundary criterion uses L^3 capacity with unsquared channel resistances [8, Theorems 2.1–2.2]. The present four-state reconstruction criterion has the L^3 exponent but the squared channel resistance \lambda^{-2|e|}. The nonlinear recursion used below is the p=3 instance of their capacity recursion [8, Lemma 3.1 and Corollary 3.4]; we give the needed flow construction directly.

Our essential probabilistic input is the preserved class of posterior laws and its moment-saving inequality from The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model [7, Proposition 3.2]. That companion studies the threshold on regular and Poisson Galton–Watson trees. Its posterior-law statement allows arbitrary channel parameters and conditionally independent products, which is the scope needed here. We state this input precisely in Section 2; its polynomial-certificate proof is not repeated. All remaining arguments for Theorem 1.1 are proved below.

Proof strategy

We measure a posterior p’s information by the quadratic statistic m=4\E|p-\unif|^2. The companion inequality saves a cubic term when two informative branches are combined. For the implication from reconstruction to capacity, a change of variables m\mapsto m+Km^3 turns this branching saving into a nonlinear inequality that also has a strict saving at one-child vertices. A direct telescoping construction then produces an admissible flow of positive mass.

The converse starts from a flow and scales it down. At each observation level we add independent noise, chosen separately at each vertex v so that its terminal information equals the scaled flow entering v divided by \lambda^{2|v|}. The resulting information stays below this depth-weighted flow profile. To bound what is lost, we track a signed third moment in addition to m. In the four-state coordinates, the mixed quadratic term in the product formula cancels. The remaining loss is controlled by the third moment, whose propagation along an edge has factor \lambda^3, rather than \lambda^2.

Sampling a ray according to the flow converts the accumulated loss into sums along a single path. The two propagation factors leave a summable kernel \lambda^{j-i} between depths i and j. The capacity bound controls its quadratic path sum, and a single choice of noise scale works at every observation depth. This flow-calibrated degradation and third-moment estimate avoid any need for comparable branch sizes or a strict exponential growth inequality.

Section 2 introduces the posterior calculus and the companion input. Section 3 constructs the flow from reconstruction. Section 4 proves the local moment estimates, and Section 5 uses them to prove the converse. Throughout, set

2 Posterior experiments and the companion input

An experiment consists of an observation about a uniform input spin in [4]. Let p be its posterior vector and \mu the law of p under the marginal law of the observation. A posterior law is symmetric if it is invariant under all permutations of the four entries. Define

and put

Here and below, vector norms are Euclidean. The rows of L are orthogonal and span the orthogonal complement of the constant vector. Consequently

The lower bound follows from |p_i-1/4|^2\leq|p_i-1/4|; the upper bound is Cauchy–Schwarz. In expectation,

Under degradation of an observation, the new posterior is the conditional expectation of the old one given the new observation. Convexity of A therefore makes m nonincreasing under data processing.

2.1 Channels and products

In a channel step with parameter t\in[0,1], first transmit a uniform input I to J through P_t, then observe an experiment about J. The uniform distribution is stationary and the channel is symmetric, so the posterior about I is \unif+t(p-\unif). Thus

The completely revealing experiment has m=3, while the uninformative experiment has m=h=0.

If two observations are independent conditional on the same input spin, write \mu\star\nu for their combined posterior law. The normalized-product rule below is standard in posterior recursions for reconstruction; see Mézard and Montanari [4, Sections 2.2–2.4]. Sample p,q independently from their marginal posterior laws \mu,\nu. The joint marginal law of the observations is obtained by weighting this product law by

The value of P at Z=0 is irrelevant. Indeed, the likelihood of each observation conditional on input i, relative to its marginal law, is 4p_i or 4q_i. Formula (2.5) follows by averaging their product over the uniform input. In particular, \E Z=1. Symmetry is preserved by both channel steps and products.

The columns of L are the four sign triples whose product is one. Permuting these columns acts on x by coordinate permutations and even sign changes. For any symmetric posterior law, it follows that

and every degree-three coordinate monomial except x_1x_2x_3 has zero expectation. Also |x_i|\leq1. Any coordinate monomial of degree at least two is therefore bounded in absolute value by |x|^2: retain two factors and use |x_ix_j|\leq(x_i^2+x_j^2)/2, or |x_i|^2 when the indices agree. In particular,

2.2 The moment-saving input

We use the following statement from the companion manuscript. The existence and preservation of the class, not only symmetry, are essential to its upper bound.

Every finite-depth subtree experiment used here has law in \calC. This includes observations of a descendant level and observations in which each terminal spin is independently passed through its own channel P_t. At the terminals, membership follows from the revealing law and channel closure; an empty observation is uninformative. Working toward the subtree root uses channel steps and products, with conditional independence supplied by the broadcast process. The same argument covers every partial product at a vertex. No assertion about a limiting posterior law belonging to \calC will be needed.

3 From reconstruction to capacity

The nonlinear capacity recursion of Pemantle and Peres [8, Lemma 3.1 and Corollary 3.4] has a particularly direct flow interpretation in the present normalization. We first give that construction, then derive its hypothesis from the posterior information.

For a vertex v, let m_v^{(n)} be the quadratic information about \sigma_v obtained from its descendants at distance n, with m_v^{(0)}=3. Data processing gives limits

If reconstruction occurs, (2.3) implies m_\rho>0. We show that these limiting numbers yield labels satisfying Lemma 3.1 with a positive root label.

For a fixed vertex v, put

where D=0 if fewer than two children are present. Then

At finite depth the parent information is m_v^{(n+1)}, and the child values after their edge channels are b_w=rm_w^{(n)}. Choose any pair of children and combine their branch experiments first. Jensen’s inequality gives \E A^2\geq(\E A)^2, so Proposition 2.1 saves at least c b_wb_{w'}(b_w+b_{w'}). Combine the remaining children using the subadditivity part of the same proposition. Maximize over the pair and pass to the limit. All sums and maxima are finite. With zero or one child, the empty observation or channel scaling gives the assertion directly.

There are at most B^3 ordered triples of children, and every mixed product in S^3 is at most the largest b_w squared times the second largest, hence at most D. Therefore

Choose K>0 with KB^3\leq c and set y_v=m_v+Km_v^3. Since m_v\leq S, Equations (3.2) and (3.3) yield

This correction supplies a saving even at a one-child vertex, where the original pair term vanishes: the positive factor is r-r^3.

The bound m_w\leq3 gives y_w\leq(1+9K)m_w. With

Equation (3.4) implies

The second inequality is the tangent bound (1+2t)^{-1/2}\geq1-t for t\geq0. Thus z_v=\sqrt{2\delta}\,y_v satisfies (3.1), with z_\rho>0. Lemma 3.1 proves positive capacity and completes the first implication of Theorem 1.1.

4 Local estimates for information loss

For the converse, subadditivity alone is not enough: we must bound the information lost when branches are combined. The next lemma uses only symmetry and one channel-smoothed input. Unlike Proposition 2.1, it does not require membership in \calC.

5 From capacity to reconstruction

Assume \Capacity_{3,\lambda}(T)>0 and choose an admissible flow \theta of positive mass. We construct degraded observations at every finite depth and bound their information from below uniformly in that depth. The noise scale will be fixed only after the total loss has been estimated. Noisy boundary observations also underlie robust reconstruction [2]. Here we choose the noise separately at each vertex from the flow and use the resulting information to bound that of the original observations.

5.1 A flow profile and terminal observations

For 0<\epsilon\leq1, let \Theta(v) be the flow \epsilon\theta entering a nonroot vertex v, and define

Conservation becomes

Every positive-flow edge extends to an infinite ray: at every positive-flow vertex, conservation gives at least one positive-flow child. Hence admissibility implies X_v\leq\epsilon for all nonroot vertices. In particular, \theta(\rho,w)\leq r for each child of the root, and |\theta|\leq Br. On every ray \xi=(v_0=\rho,v_1,v_2,\ldots), we therefore have

The extra term in Q is needed because X_\rho=M need not be at most \epsilon.

Fix n\geq1. At each v\in L_n, observe its spin only after an additional independent channel P_{t_v}, where

These are valid parameters since X_v\leq\epsilon\leq1. For |v|\leq n, let \widehat m_v,\widehat h_v be the statistics of the experiment about \sigma_v using these degraded terminal observations in its subtree. The dependence on n is suppressed. These laws and their partial products belong to \calC, as explained after Proposition 2.1.

By channel scaling, at the terminal level

Subadditivity in (2.8), channel scaling, and (5.1) give inductively

A vertex with no observed descendants has the uninformative experiment. Finite branches carry no flow, so early leaves and zero-flow subtrees are consistent with these bounds.

5.2 Local and accumulated losses

For |v|<n, define the deficit from linear addition by

We first prove that, with a fixed finite C_1 depending only on B,\lambda,

The coefficient of the propagated third moment is exactly \lambda^3; the constant C_1 multiplies only the new error.

Combine the child branches one at a time. After the edge channel, their individual statistics, now about the spin at v, are

Every partial product has m at most the sum of its b_w’s, hence at most X_v. Applying (4.2) at each addition gives the partial bound

The sums on the right may be taken over all children, so this also proves (5.7) after increasing C_1. Every addition has nonnegative deficit by Proposition 2.1. Its deficit is at most

by (4.1). Summing and using \sum_wb_w\leq X_v gives D_v\leq2CX_vH+C^2X_v^3, proving (5.8). The second input at every use of Lemma 4.1 is a single child branch after its channel of parameter \lambda, as required.

Write u\succeq v when u is a descendant of v, including u=v. Iterating (5.7) in (5.8) and using (5.4) gives, for i=|v|<n,

Here C_2=\max\{C_1,C_1^2\} suffices. At each internal descendant the term C_1X_u^2 is inserted once and then propagated with a factor \lambda^3 per edge; no power of C_1 grows with depth.

Telescoping the deficits (5.6) over the finite tree above L_n now yields

The last equality uses conservation of \Theta. It remains to show that this total loss is at most a fixed fraction of M, uniformly in n.

5.3 Averaging the losses along a flow path

Sample a vertex of L_n with probabilities \Theta(v)/M and let (V_0=\rho,V_1,\ldots,V_n) be its ancestors. Conservation gives \sum_{v\in L_j}\Theta(v)=M for every j\leq n and therefore

This remains true with early leaves: their flow is zero. Every path with positive probability extends to an infinite ray, so (5.2) bounds the sum of its X_{V_i}^2.

For i\leq j and |u|=j, the identity responsible for the summable path kernel is

The unique depth-i ancestor of u is specified once u is chosen. Thus, for 0\leq i\leq j<n,

whereas the terminal terms satisfy

Combining these identities with (5.9) gives

For each fixed difference k=j-i\geq0, Cauchy–Schwarz and (5.2) give, on every path in the support,

Each individual X_{V_i} is at most \sqrt Q\,\epsilon. Summing the geometric weights in (5.15), the expectation there is at most

Choose \epsilon\in(0,1] so small that C_2 times this expression is at most 1/2. The choice is independent of n. Equations (5.10) and (5.15) now give

The original, undegraded level observation has at least this much quadratic information by data processing. By (2.3),

Thus a_\infty(T,\lambda)>0, proving the remaining implication of Theorem 1.1. The degraded experiments may vary with n; the proof requires only the same positive lower bound at each depth, not their convergence or mutual monotonicity.