A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 2 OF 3 · Sharp three- and four-state reconstruction thresholds
A Capacity Criterion for Four-State Potts Reconstruction on Trees
expertly designed by an internal OpenAI model · released 2026-10-05
· original PDF
IntroductionLet \(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, \(\operatorname{ch}(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 \[ P_\lambda(j\mid i) =\lambda\mathbf1_{\{i=j\}}+\frac{1-\lambda}{4}. \tag{1}\] For the uniform probability vector \(\mathsf u=(1/4,1/4,1/4,1/4)\), put \[a_n(T,\lambda)= \mathbb E\,\operatorname{TV}\bigl(\mathbb P(\sigma_\rho\in\cdot\mid\sigma_{L_n}), \mathsf u\bigr), \qquad \operatorname{TV}(p,\mathsf u)=\frac12\sum_{i=1}^4|p_i-1/4|.\] 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 \[|\theta|=\sum_{w\in\operatorname{ch}(\rho)}\theta(\rho,w).\] 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 \[\begin{align*} V_\lambda(\theta,\xi) &=\sum_{e\in\xi}\bigl(\lambda^{-2|e|}\theta(e)\bigr)^2, \qquad \xi\in\partial T,\tag{2}\\ \operatorname{Cap}_{3,\lambda}(T) &=\sup\left\{|\theta|: \sup_{\xi\in\partial T}V_\lambda(\theta,\xi)\leq1\right\}. \tag{3}\end{align*}\] 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\) (Pemantle and Peres 2010, sec. 2). Theorem 1. Let \(T\) be an infinite rooted tree with at most \(B<\infty\) children per vertex, and let \(0<\lambda<1\). For the broadcast model (1), \[a_\infty(T,\lambda)>0 \quad\Longleftrightarrow\quad \operatorname{Cap}_{3,\lambda}(T)>0.\] 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 (3) is zero. History and relation to earlier workThe second-eigenvalue scale in tree broadcasting originates in the branching-process work of Kesten and Stigum (Kesten and Stigum 1966). For a regular tree with \(d\) children per vertex, the corresponding bound guarantees reconstruction when \(d\lambda^2>1\) (Mossel and Peres 2003). Evans, Kenyon, Peres, and Schulman (Evans et al. 2000) developed the relation between broadcasting, the Ising model, and electrical capacity. For Potts channels, Sly (Sly 2011) 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 (Mossel et al. 2025) 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 (Sly 2011; Mossel et al. 2025). Pemantle and Peres (Pemantle and Peres 2010) 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 (Pemantle and Peres 2010, 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 (Pemantle and Peres 2010, 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 (OpenAI 2026, 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 are proved below. Proof strategyWe measure a posterior \(p\)’s information by the quadratic statistic \(m=4\mathbb E|p-\mathsf u|^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 \[r=\lambda^2\in(0,1).\] Posterior experiments and the companion inputAn 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 \[L=\begin{pmatrix} 1&1&-1&-1\\ 1&-1&1&-1\\ 1&-1&-1&1 \end{pmatrix},\qquad x=Lp,\qquad A(p)=|x|^2,\] and put \[ m(\mu)=\mathbb E_\mu A, \qquad \tau(\mu)=\mathbb E_\mu[x_1x_2x_3], \qquad h(\mu)=|\tau(\mu)|. \tag{4}\] Here and below, vector norms are Euclidean. The rows of \(L\) are orthogonal and span the orthogonal complement of the constant vector. Consequently \[ A(p)=4|p-\mathsf u|^2,\qquad 0\leq A(p)\leq3, \qquad \frac18A(p)\leq\operatorname{TV}(p,\mathsf u)\leq\frac12\sqrt{A(p)}. \tag{5}\] The lower bound follows from \(|p_i-1/4|^2\leq|p_i-1/4|\); the upper bound is Cauchy–Schwarz. In expectation, \[ \frac18m(\mu)\leq\mathbb E\,\operatorname{TV}(p,\mathsf u) \leq\frac12\sqrt{m(\mu)}. \tag{6}\] 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. Channels and productsIn 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 \(\mathsf u+t(p-\mathsf u)\). Thus \[ x\longmapsto tx,\qquad m\longmapsto t^2m, \qquad \tau\longmapsto t^3\tau, \qquad h\longmapsto t^3h. \tag{7}\] 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 (Mézard and Montanari 2006, secs. 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 \[ Z=4\sum_{i=1}^4p_iq_i, \qquad P_i=\frac{4p_iq_i}{Z}. \tag{8}\] 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 (8) follows by averaging their product over the uniform input. In particular, \(\mathbb EZ=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 \[ \mathbb Ex_i=0,\qquad \mathbb Ex_ix_j=\frac{m}{3}\mathbf1_{\{i=j\}}, \tag{9}\] 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, \[ h(\mu)\leq m(\mu). \tag{10}\] The moment-saving inputWe use the following statement from the companion manuscript. The existence and preservation of the class, not only symmetry, are essential to its upper bound. Proposition 2 (Companion input, (OpenAI 2026, Proposition 3.2 and Equations (3.8)–(3.9))). There is a class \(\mathcal C\) of symmetric posterior laws containing the revealing and uninformative laws and preserved by channel steps with any parameter in \([0,1]\) and by conditionally independent products. For \(\mu,\nu\in\mathcal C\), \[ m(\mu\star\nu)\leq m(\mu)+m(\nu) -c\left(\mathbb E_\mu[A^2]m(\nu)+m(\mu)\mathbb E_\nu[A^2]\right), \qquad c=\frac1{1000}. \tag{11}\] Every finite-depth subtree experiment used here has law in \(\mathcal C\). 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 \(\mathcal C\) will be needed. From reconstruction to capacityThe nonlinear capacity recursion of Pemantle and Peres (Pemantle and Peres 2010, 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. Lemma 3 (A flow from recursive labels). Suppose nonnegative finite labels \((z_v)_{v\in T}\) satisfy \[ z_v\leq\sum_{w\in\operatorname{ch}(v)} \frac{r z_w}{\sqrt{1+z_w^2}}. \tag{12}\] Then there is a flow of mass \(z_\rho\) whose potential (2) is at most one on every ray. In particular, \(\operatorname{Cap}_{3,\lambda}(T)\geq z_\rho\). Proof. At each vertex choose coefficients \[0\leq d_{vw}\leq\frac{r}{\sqrt{1+z_w^2}} \quad\text{such that}\quad z_v=\sum_{w\in\operatorname{ch}(v)}d_{vw}z_w.\] If the upper-bound sum is positive, multiply all its coefficients by the ratio of \(z_v\) to that sum; otherwise all labels in the displayed equality are zero and take all coefficients to be zero. Set \(\ell_\rho=1\), \(\ell_w=\ell_vd_{vw}\) recursively, and define \[\theta(v,w)=\ell_wz_w.\] The displayed equality gives conservation at every nonroot vertex and mass \(z_\rho\) at the root. Put \(g_v=r^{-|v|}\ell_v\). Then \[g_w^2(1+z_w^2)\leq g_v^2, \qquad \bigl(r^{-|w|}\theta(v,w)\bigr)^2 =(g_wz_w)^2\leq g_v^2-g_w^2.\] Summing along any finite initial segment of a ray gives a bound by \(g_\rho^2=1\). Monotone convergence of the nonnegative sums proves the assertion for every infinite ray. ◻ 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 \[m_v=\lim_{n\to\infty}m_v^{(n)}\in[0,3].\] If reconstruction occurs, (6) implies \(m_\rho>0\). We show that these limiting numbers yield labels satisfying Lemma 3 with a positive root label. For a fixed vertex \(v\), put \[b_w=rm_w,\qquad S=\sum_{w\in\operatorname{ch}(v)}b_w, \qquad D=\max_{w\ne w'}b_wb_{w'}(b_w+b_{w'}),\] where \(D=0\) if fewer than two children are present. Then \[ m_v\leq S-cD. \tag{13}\] 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 \(\mathbb EA^2\geq(\mathbb EA)^2\), so Proposition 2 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 \[ S^3\leq\sum_w b_w^3+B^3D. \tag{14}\] Choose \(K>0\) with \(KB^3\leq c\) and set \(y_v=m_v+Km_v^3\). Since \(m_v\leq S\), Equations (13) and (14) yield \[\begin{align*} y_v&\leq S-cD+KS^3 \leq S+K\sum_w b_w^3\\ &=r\sum_w y_w-Kr(1-r^2)\sum_wm_w^3. \tag{15}\end{align*}\] 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 \[\delta=\frac{K(1-r^2)}{(1+9K)^3}>0,\] Equation (15) implies \[y_v\leq r\sum_wy_w(1-\delta y_w^2) \leq r\sum_w\frac{y_w}{\sqrt{1+2\delta y_w^2}}.\] 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 (12), with \(z_\rho>0\). Lemma 3 proves positive capacity and completes the first implication of Theorem 1. Local estimates for information lossFor 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, it does not require membership in \(\mathcal C\). Lemma 4. Fix \(0<\lambda<1\). Let \(\mu,\nu\) be symmetric posterior laws, with \(\nu\) obtained by a channel step of parameter \(\lambda\). There is a finite constant \(C=C(\lambda)\) such that \[\begin{align*} m(\mu\star\nu) &\geq m(\mu)+m(\nu) -C\bigl(h(\mu)m(\nu)+m(\mu)h(\nu)\bigr), \tag{16}\\ h(\mu\star\nu) &\leq h(\mu)+h(\nu)+C m(\mu)m(\nu). \tag{17}\end{align*}\] The first inequality holds with \(C=7\). Proof. All expectations in this proof are over independent marginal posterior vectors \(p,q\) of laws \(\mu,\nu\). Put \[x=Lp,\qquad y=Lq,\qquad s=x\cdot y, \qquad a=m(\mu),\quad b=m(\nu), \quad \alpha=\tau(\mu),\quad\beta=\tau(\nu).\] Since \(p=\mathsf u+L^{\mathsf T}x/4\) and similarly for \(q\), the product rule (8) becomes \[ Z=1+s,\qquad LP=\frac{N}{1+s},\qquad N=x+y+R,\qquad R_i=x_jy_k+x_ky_j, \tag{18}\] where \(\{i,j,k\}=\{1,2,3\}\). Each coordinate of \(q\) is at least \((1-\lambda)/4\), so \[ 1+s\geq1-\lambda>0,\qquad -\lambda\leq s\leq3. \tag{19}\] The quadratic statistic.Using the marginal weight \(Z\) in (8), \[m(\mu\star\nu)=\mathbb E\frac{|N|^2}{1+s}.\] The second moments in (9) give \[\mathbb E|R|^2=\frac23ab,\qquad \mathbb Es^2=\frac13ab.\] In the expansion of \(\mathbb E[|N|^2(1-s)]\), the term \(\mathbb E|R|^2\) therefore cancels \(2\mathbb Es^2\). Terms of degree one in either vector have zero expectation. For the remaining terms, \[\mathbb E[s\,x\cdot R]=2\alpha b,\qquad \mathbb E[s\,y\cdot R]=2a\beta,\qquad \mathbb E[s|R|^2]=6\alpha\beta.\] For example, \(x\cdot R=2(x_1x_2y_3+x_1x_3y_2+x_2x_3y_1)\); after multiplication by \(s\), only terms proportional to \(x_1x_2x_3\) survive expectation over \(x\). The last identity follows in the same way by retaining only terms with all three indices in each vector. Thus the expansion is exactly \[ \mathbb E[|N|^2(1-s)] =a+b-4(\alpha b+a\beta)-6\alpha\beta. \tag{20}\] As \((1+s)^{-1}=1-s+s^2/(1+s)\), we obtain \[ m(\mu\star\nu) =a+b-4(\alpha b+a\beta)-6\alpha\beta +\mathbb E\frac{|N|^2s^2}{1+s}. \tag{21}\] The final term is nonnegative. Moreover, (10) implies \[|\alpha\beta|\leq \frac12\bigl(h(\mu)b+a h(\nu)\bigr).\] This proves (16) with constant seven, without any sign assumption on \(\alpha\) or \(\beta\). The third moment.The corresponding product formula is \[\tau(\mu\star\nu)=\mathbb E\frac{N_1N_2N_3}{(1+s)^2}.\] Use the exact remainder \[ (1+s)^{-2}-(1-2s)=\frac{s^2(3+2s)}{(1+s)^2}. \tag{22}\] The numerator \(N_1N_2N_3\) is bounded, and (19) bounds the multiplier in (22) by a constant depending only on \(\lambda\) times \(s^2\). The error in replacing the denominator factor by \(1-2s\) is consequently at most \(C_0(\lambda)ab\). In the finite polynomial \(N_1N_2N_3(1-2s)\), the only pure terms are \(x_1x_2x_3+y_1y_2y_3\). Every mixed monomial of degree one in one vector has zero expectation. Every other mixed monomial has degree at least two in each vector, so its absolute expectation is at most \(ab\), by independence and the monomial bound following (9). Summing the finitely many coefficients and taking absolute values proves (17). Increase the common \(C(\lambda)\) to at least seven to obtain both estimates. ◻ From capacity to reconstructionAssume \(\operatorname{Cap}_{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 (Janson and Mossel 2004). Here we choose the noise separately at each vertex from the flow and use the resulting information to bound that of the original observations. A flow profile and terminal observationsFor \(0<\epsilon\leq1\), let \(\Theta(v)\) be the flow \(\epsilon\theta\) entering a nonroot vertex \(v\), and define \[\Theta(\rho)=M:=\epsilon|\theta|, \qquad X_v=r^{-|v|}\Theta(v).\] Conservation becomes \[ X_v=r\sum_{w\in\operatorname{ch}(v)}X_w. \tag{23}\] 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 \[ \sum_{j=0}^{\infty}X_{v_j}^2\leq Q\epsilon^2, \qquad Q=1+(Br)^2. \tag{24}\] 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 \[ t_v=\sqrt{X_v/3}. \tag{25}\] 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 \(\mathcal C\), as explained after Proposition 2. By channel scaling, at the terminal level \[ \widehat m_v=X_v,\qquad \widehat h_v\leq X_v \qquad (|v|=n). \tag{26}\] Subadditivity in (11), channel scaling, and (23) give inductively \[ \widehat m_v\leq X_v\qquad (|v|\leq n). \tag{27}\] 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. Local and accumulated lossesFor \(|v|<n\), define the deficit from linear addition by \[ D_v=r\sum_{w\in\operatorname{ch}(v)}\widehat m_w-\widehat m_v. \tag{28}\] We first prove that, with a fixed finite \(C_1\) depending only on \(B,\lambda\), \[\begin{align*} \widehat h_v &\leq\lambda^3\sum_w\widehat h_w+C_1X_v^2, \tag{29}\\ 0\leq D_v &\leq C_1X_v\left(\lambda^3\sum_w\widehat h_w+X_v^2\right). \tag{30}\end{align*}\] 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 \[b_w=r\widehat m_w,\qquad h'_w=\lambda^3\widehat h_w.\] Every partial product has \(m\) at most the sum of its \(b_w\)’s, hence at most \(X_v\). Applying (17) at each addition gives the partial bound \[h\leq\sum_w h'_w+C X_v\sum_wb_w \leq H+CX_v^2,\qquad H=\sum_wh'_w.\] The sums on the right may be taken over all children, so this also proves (29) after increasing \(C_1\). Every addition has nonnegative deficit by Proposition 2. Its deficit is at most \[C\bigl((H+CX_v^2)b_w+X_vh'_w\bigr)\] by (16). Summing and using \(\sum_wb_w\leq X_v\) gives \(D_v\leq2CX_vH+C^2X_v^3\), proving (30). The second input at every use of Lemma 4 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 (29) in (30) and using (26) gives, for \(i=|v|<n\), \[ D_v\leq C_2X_v\left( \sum_{\substack{u\succeq v\\|u|<n}} \lambda^{3(|u|-i)}X_u^2 +\sum_{\substack{u\succeq v\\|u|=n}} \lambda^{3(n-i)}X_u \right). \tag{31}\] 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 (28) over the finite tree above \(L_n\) now yields \[ \widehat m_\rho =r^n\sum_{v\in L_n}X_v -\sum_{|v|<n}r^{|v|}D_v =M-\sum_{|v|<n}r^{|v|}D_v. \tag{32}\] 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\). Averaging the losses along a flow pathSample 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 \[ \mathbb P(V_j=u)=\frac{\Theta(u)}M\qquad (u\in L_j). \tag{33}\] This remains true with early leaves: their flow is zero. Every path with positive probability extends to an infinite ray, so (24) 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 \[ r^i\lambda^{3(j-i)}X_u =\lambda^{j-i}\Theta(u). \tag{34}\] The unique depth-\(i\) ancestor of \(u\) is specified once \(u\) is chosen. Thus, for \(0\leq i\leq j<n\), \[\begin{align*} &\sum_{|v|=i}r^iX_v \sum_{\substack{u\succeq v\\|u|=j}} \lambda^{3(j-i)}X_u^2\\ &\hspace{35mm}=M\lambda^{j-i}\mathbb E[X_{V_i}X_{V_j}], \tag{35}\end{align*}\] whereas the terminal terms satisfy \[ \sum_{|v|=i}r^iX_v \sum_{\substack{u\succeq v\\|u|=n}} \lambda^{3(n-i)}X_u =M\lambda^{n-i}\mathbb EX_{V_i}. \tag{36}\] Combining these identities with (31) gives \[ \sum_{|v|<n}r^{|v|}D_v \leq C_2M\,\mathbb E\left[ \sum_{0\leq i\leq j<n}\lambda^{j-i}X_{V_i}X_{V_j} +\sum_{0\leq i<n}\lambda^{n-i}X_{V_i} \right]. \tag{37}\] For each fixed difference \(k=j-i\geq0\), Cauchy–Schwarz and (24) give, on every path in the support, \[\sum_{i=0}^{n-1-k}X_{V_i}X_{V_{i+k}} \leq \left(\sum_{i=0}^{n-1-k}X_{V_i}^2\right)^{1/2} \left(\sum_{i=0}^{n-1-k}X_{V_{i+k}}^2\right)^{1/2} \leq Q\epsilon^2.\] Each individual \(X_{V_i}\) is at most \(\sqrt Q\,\epsilon\). Summing the geometric weights in (37), the expectation there is at most \[ \frac{Q\epsilon^2}{1-\lambda} +\frac{\sqrt Q\,\epsilon}{1-\lambda}. \tag{38}\] 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 (32) and (37) now give \[\widehat m_\rho\geq M/2>0\qquad\text{for every }n\geq1.\] The original, undegraded level observation has at least this much quadratic information by data processing. By (6), \[a_n(T,\lambda)\geq M/16\qquad(n\geq1).\] Thus \(a_\infty(T,\lambda)>0\), proving the remaining implication of Theorem 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.
Evans, William, Claire Kenyon, Yuval Peres, and Leonard J. Schulman. 2000. “Broadcasting on Trees and the Ising Model.” Annals of Applied Probability 10 (2): 410–33. https://doi.org/10.1214/aoap/1019487349.
Janson, Svante, and Elchanan Mossel. 2004. “Robust Reconstruction on Trees Is Determined by the Second Eigenvalue.” Annals of Probability 32 (3B): 2630–49. https://doi.org/10.1214/009117904000000153.
Kesten, Harry, and Bernt P. Stigum. 1966. “Additional Limit Theorems for Indecomposable Multidimensional Galton–Watson Processes.” Annals of Mathematical Statistics 37 (6): 1463–81. https://doi.org/10.1214/aoms/1177699139.
Mézard, Marc, and Andrea Montanari. 2006. “Reconstruction on Trees and Spin Glass Transition.” Journal of Statistical Physics 124 (6): 1317–50. https://doi.org/10.1007/s10955-006-9162-3.
Mossel, Elchanan, and Yuval Peres. 2003. “Information Flow on Trees.” Annals of Applied Probability 13 (3): 817–44. https://doi.org/10.1214/aoap/1060202828.
Mossel, Elchanan, Allan Sly, and Youngtak Sohn. 2025. “Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees.” Annals of Probability 53 (3): 967–1018. https://doi.org/10.1214/24-AOP1723.
OpenAI. 2026. The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model. OpenAI Math Release preprint OAI:The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026.
Pemantle, Robin, and Yuval Peres. 2010. “The Critical Ising Model on Trees, Concave Recursions and Nonlinear Capacity.” Annals of Probability 38 (1): 184–206. https://doi.org/10.1214/09-AOP482.
Sly, Allan. 2011. “Reconstruction for the Potts Model.” Annals of Probability 39 (4): 1365–406. https://doi.org/10.1214/10-AOP584.
|
| ||||||||
|