The Mézard–Parisi formula for diluted spin glasses

Proof. At the terminal spin integration, the partition-function ratio is K_LA=Y_{L-1}, because m_L=1. If X_d and X_d^A are the old and new backward logarithms, substitution in the preceding power mean gives

Backward induction proves X_d^A-X_d=\log Y_d and then gives (3.4); the same formula at d=L is the usual Gibbs density ratio.

Multiply the edge density ratios in (3.4) over the tree. An internal vertex at positive depth d receives exponent m_d from its incoming edge and exponent -n_\beta m_{d+1} from its outgoing edges. At the root there is no incoming edge, which agrees with m_0=0. Each terminal vertex receives exponent m_L=1. This proves (3.5). Monotonicity and homogeneity follow at once by backward induction in (3.3).□

Proof. The first derivative is, by (3.6), the expectation of D/A on one updated path. Protect that leaf. Every subsequent derivative can only add a fresh path, because all current leaves are protected. At order k, all k-1 fresh coefficients are negative. After normalization by (3.7), their absolute products are (k-1)! times the probabilities in Q_k. Therefore

Analyticity proves (3.9); the coefficients have absolute value at most \|D\|_\infty^k/k, which proves the stated convergence domain and (3.10).□

Proof. Begin with C=\{a_*\} and G=H. Apply the preceding rule successively, incorporating each new D_j in G. Fresh leaves are protected immediately, so the only unprotected leaves are unused old leaves. At zero all factors A and Y are 1, proving the claimed rule and its coefficients.□

Proof. At the specified divergence vertex, let n be the child count in the entire current tree. The j excluded children contain all references passing through that vertex. Each of the other n-j children roots a subtree containing no reference. Its terminal vertices are therefore unused old leaves. If such a subtree is rooted at depth d+1, its permitted choices are an old leaf, with coefficient 1, or a fresh divergence at an internal vertex in the subtree. If it has q leaves, telescoping within it gives

The formula includes the case of a terminal child, when both sides are 1. Adding these contributions to the fresh choice at the specified vertex gives m_d-nm_{d+1}+(n-j)m_{d+1}=m_d-jm_{d+1}.

For consistent prescribed splitting depths with all reference paths, the deepest required common prefix determines the divergence vertex and its excluded reference children. Thus the one-step sum depends only on the current reference tree, not on which old paths or fresh paths realized it. Sum backwards over successive choices. At a branching vertex of the final prescribed tree, the numbers of excluded reference children when new child groups are first entered are exactly 1,\ldots,a_v-1. Their factors give (3.13), independently of the color order.□

Proof. If the current tree has s leaves, (3.7) says that the total absolute coefficient of all fresh choices is s. There are at most s eligible old choices. Hence the total absolute coefficient at an unrestricted step is at most 2s\leq2(q+k). At any fixed depth there are at most s vertices. Restricting a step to fresh divergences at unary vertices of a prescribed depth therefore gives total absolute coefficient at most s\delta, because each such divergence has coefficient m_d-m_{d+1}=-\delta.

Consider an allowed history and one of its specified target branching vertices. That vertex cannot already be branching in the old tree. At the first step at which it became branching in the current tree, a fresh path must therefore have diverged there while it was unary. The vertex may itself have been created earlier as part of a new unary path; the same conclusion then applies. Distinct target vertices become branching at distinct steps, since a fresh path creates only one branching vertex. Assign each of the b vertices to its creation step. There are at most k!/(k-b)! possible assignments (and necessarily b\leq k).

For each fixed assignment, enlarge the family of histories by discarding all constraints except that a designated step creates a unary split at its assigned depth. Bound its step sum by (q+k)\delta and every other step sum by 2(q+k). Iterated summation over choices gives at most

This proves (3.14), including repeated assigned depths, because the designated steps remain distinct.

For the final assertion, the j=1 factor at each designated vertex has absolute value \delta, whereas for j\geq2

There are only a size-dependent number of the latter factors. Thus |J|\geq\delta^b\eta^{\sum_v(a_v-2)}, and the result follows.□

Proof. Suppose the current tree has n leaves. A new branching vertex is created exactly when the next path diverges at a unary vertex. Each such choice has probability \delta/n by (3.8). At any depth there are at most n vertices; hence for a set B of depths the probability that the next path creates a branching vertex at a depth in B is at most |B|\delta. At each of the first k-1 steps, the boundary depths and the depths within normalized distance \eta of any previous branching vertex form a set of cardinality at most C_k(\eta L+1). If none of these forbidden creation events occurs, the final tree is regular. A union bound proves (3.16). Divergence at an already branching vertex does not create a new coordinate and requires no extra exclusion.

For (3.17), restrict a specified final labeled tree to leaves 1,\ldots,n, retaining every unary stretch. These restrictions determine its successive histories under (3.8). Each of its a branching vertices is first created by a unary divergence, whose probability is at most \delta; every other transition probability is at most 1. The probability of the specified history is therefore at most \delta^a. If a topology description identifies equivalent child orderings, their number is bounded in terms of k alone, which gives the stated version with C_k. Finally, a retained branching vertex after deletion was already a branching vertex of the original tree, at the same depth. Its depth coordinates are a subset of the old ones, so regularity is preserved.□

Proof. First dispose of the degenerate factorization. Put M=\max_{s=\pm1}|f(s)|. If b=0 almost surely or M=0 almost surely, the interaction is a spin-independent random constant c, and

for every trial law. Otherwise choose u,v>0 with \P(M\ge u)>0 and \P(|b|\ge v)>0. Since |b|\prod_{\ell=1}^p M_\ell<1 almost surely, independence gives

Indeed, violating either bound on a set of positive probability and restricting the other independent factors to these lower bounds would violate the strict product condition. All moments used below are therefore finite.

Interpolation. Fix a trial law and set L=r+1. Interpolate between real interactions of mean t\alpha N and, at each site i, independent cavity interactions U_\theta(x_1,\ldots,x_{p-1};\sigma_i) of mean (1-t)\alpha p. Different cavity terms have disjoint message labels. Counts, interactions, fields, and root message measures are quenched. Apply the backward power-mean recursion to the spin partition function and denote its expected root logarithm divided by N by \varphi(t). For r=0 all messages are quenched and there is no auxiliary recursion. Independence between different sites throughout the recursion gives

Poisson differentiation gives \varphi'(t)/\alpha as the expected insertion increment of one real interaction minus p times the increment of one cavity interaction at a uniform site. Each increment has absolute value at most B(\theta), since the recursion preserves multiplicative bounds. Conditioning on the counts justifies the derivative on (0,1), and the same bound gives continuity at the endpoints.

We claim that

All three insertions have the form a(1+D) under (2.3). For a real interaction, D=b\prod_\ell f_\ell(\sigma_{i_\ell}); for a cavity interaction, replace p-1 of the factors by \bar f(x)=\sum_s f(s)q_x(s); for an edge insertion, replace all p. In the last case the independent message process is appended to the unperturbed tilted tree, so its increment is \log T_0V_{\rm e}.

Normalization. We remove a before taking expectations, so no integrability of \log a is needed. Put D_*=b\prod_\ell f_\ell(1) and c=\theta(1,\ldots,1). Subtract c from each insertion increment. These integrable subtractions cancel in the combination with coefficients 1,-p,p-1. Keep the interpolated system fixed. For 0<\lambda<1, replace each normalized increment by

where Y_0 is the insertion recursion of Lemma 3.2. For every spin input, the ratio

lies between e^{-2B(\theta)} and e^{2B(\theta)}. The same is true after averaging any subset of the spin inputs against the q_x’s. It follows that (4.2) is bounded in absolute value by 2B(\theta). For each fixed interaction, convergence as \lambda\uparrow1 is uniform in the spin inputs and messages and is preserved by the finite recursion. Dominated convergence therefore recovers the desired normalized increments.

Convexity. Apply Lemma 3.2 to the regularized increments. On a tree \cT with n replica leaves define

Here \E_f averages one fresh function f, shared by all n replica factors in the product. The expectation \E_{f,x} also averages an entire fresh message-label tree, including its root. This function and message tree are independent of one another and of the old tilted system. Thus B_{\cT} is deterministic for a fixed tree, while P_{\cT} still depends on the old spin replicas. At r=0, the message itself is a root variable shared by all replica leaves. Averaging the independent uniform indices and the independent copies of f and of the new message label gives, respectively, P_{\cT}^p, P_{\cT}B_{\cT}^{p-1}, and B_{\cT}^p. The inserted b is independent of these variables. Thus the order-n coefficient of the combined regularized increment is

The regularized baseline terms cancel. The tree law Q_n is that of Lemma 3.2; it is common to the three insertions. The series is absolutely convergent for \lambda<1, with each insertion controlled by \sum_{n\ge1}\lambda^n/n. Since p is even, convexity of x\mapsto x^p makes the bracket nonnegative, and (2.4) makes (4.3) nonpositive. Taking \lambda\uparrow1 proves (4.1). Integration over t\in[0,1] gives the proposition.□

Proof. The physical interactions. Split the Poisson interaction process of the (N+1)-spin system according to the number of indices equal to N+1. Terms with no new index have mean \rho_N. Terms with exactly one new index have mean \alpha p(N/(N+1))^{p-1}=\alpha p+O(N^{-1}); by permutation invariance we may place the new input last. Their other indices are independent uniform indices in [N], and their interaction functions retain the prescribed law. Terms with at least two new indices have total mean O(N^{-1}). Meanwhile, the N-spin system can be obtained from the same reservoir by adding a Poisson number of old interactions of mean

These quantities are nonnegative for all sufficiently large N.

The perturbations. The old-site perturbation count in the (N+1)-spin system has total mean s_{N+1}N/(N+1), and the new-site count has mean s_{N+1}/(N+1). Couple these processes to the reservoir perturbations using common Poisson points. The expected number of unmatched factors is at most

Deleting or adding a perturbation changes the root logarithm by at most \log2; an interaction changes it by at most B. An unused auxiliary variable can simply be integrated out with its prior, so these comparisons remain valid when the number of auxiliary variables changes.

The increment. We may consequently discard the repeated-new-index interactions, match the perturbations, and replace the two insertion count means by their limits at a total expected cost O(N^{-1/4}). Summing over the new spin gives 2A_{\rm s}, while the old-system correction gives A_{\rm b}. The factor 2 supplies the term \log2 in the increment. The insertion identity for the power means then proves (5.5). Finally,

Together with the coupling estimate this bounds the increments for large N; increasing the constant covers the remaining sizes. All estimates are uniform in L and \mathbf u.□

Proof. Hold the other parameters fixed, write u=u_\nu, n=n_\nu, and put \lambda_\nu=c_\nu s_N. Choose an open interval J_\nu containing I_\nu such that |t_\nu|+|u|<1/2 throughout its closure. On this interval, pathwise,

Fluctuations along a tilted path. Let X_0(u) be the random root log partition function before taking the root expectation. To include the last step in the differentiation, regard the logarithm of the spin weight as X_L and the spin partition function as the step with exponent m_L=1. Differentiation of one backward step gives

Thus, for M_d=\langle D_\nu\mid\mathscr F_d\rangle,

Here the conditional expectations and variances use the tilted path law at the current u. At fixed root all derivatives are justified by the bounded score and its derivatives; the finite recursion then justifies the displayed differentiation formulas. Their root expectations are justified by the finite moments of the Poisson counts.

Integrating (6.8) over I_\nu=[a,b] and using |X_0'|\leq2n yields

Consequently the interval-averaged thermal mean absolute deviation, divided by \lambda_\nu, is at most

Fluctuations of the root mean. It remains to concentrate X_0' over the root. By (6.8), the random function

is convex on J_\nu. Uniformly for u\in J_\nu and all the other parameters,

To prove the first estimate, condition on the physical and total perturbation counts. Conditional on the latter count, its types and sites are independent labels; changing a label replaces a single bounded factor. Apply the Efron–Stein variance inequality [8] \Var Z\le\frac12\sum_j\E(Z-Z^{(j)})^2, where Z^{(j)} is obtained by independently resampling the jth input. For completeness, with independent inputs X_1,\ldots,X_k, let E_j integrate only X_j and let \mathscr G_j=\sigma(X_1,\ldots,X_j). The Doob differences are D_j=\E[Z-E_jZ\mid\mathscr G_j]. Orthogonality and Jensen give

This independent-input decomposition requires neither identical laws nor a symmetric statistic; see Efron–Stein [8, Section 2]. Resampling one interaction, field, or perturbation term changes X_0 by a bounded amount: this is immediate for the spin weights and is preserved by each power mean. When a term is removed, its unused independent mark variables can be integrated out, so the same assertion holds for addition or deletion of a term. Conditional variances are therefore bounded by a constant times the number of root variables. Conditional means are Lipschitz functions of the counts, with bounded Lipschitz constants. If Q,Q' are independent copies of a Poisson variable and b is C-Lipschitz, then

Applying this to the independent counts completes the O(N) estimate. The correction 2nu^2 obeys the same estimates. The derivative bound in (6.11) follows directly from (6.6).

Passing from a convex function to its derivative. Put \bar G=\mathbb E_{\mathbf u}G and Z=G-\bar G. If u\pm\rho lie in J_\nu, forward and backward difference quotients imply

The monotonicity of \bar G' gives

Together with (6.11), this proves

For all sufficiently large N, take \rho=N^{-1/8}, which lies within the fixed neighborhood margin. After division by \lambda_\nu=c_\nu N^{3/4}, both terms tend to zero. Removing the correction to G' costs at most C_\nu\mathbb E|n-\lambda_\nu|/\lambda_\nu \leq C_\nu\lambda_\nu^{-1/2}. Thus the root contribution to (6.4) tends to zero. Combining it with (6.10) proves the result after integration over u_\nu. All estimates are uniform in the other parameters, so their integration against the remaining product measure proves (6.5).□

Proof. Find low averaged increments. The uniform perturbation bound (5.3) gives

Hence infinitely many N satisfy \int\Delta_N\,d\pi\leq \underline F+\varepsilon: otherwise telescoping the averaged increments would contradict this liminf. Lemma 5.1 supplies a constant C such that |\Delta_N(\mathbf u)|\leq C uniformly.

Choose parameters with small score errors. For a finite collection of types, Lemma 6.1 and Markov’s inequality show that the set where all its errors are small has parameter measure tending to one. More explicitly, choose N_j successively among the preceding infinite set so large that

Then the set G_j where e_{\nu,N_j}\leq j^{-1} for all \nu\leq j has complement of measure q_j\leq j^{-2}. Its conditional mean increment is at most

for all sufficiently large j. A vector in G_j with increment at most \underline F+2\varepsilon can therefore be chosen. Relabeling the tail proves (i) and (ii).

Make all finite-tree moments converge. At fixed L the finite labeled tree shapes and finite products of their multioverlaps form a countable collection. Each such product is bounded by one in absolute value. A diagonal subsequence gives (iii), without affecting (i) or (ii).□

Proof. Apply the Poisson add-one identity to the sum over type-\nu terms in D_\nu. After division by its mean c_\nu s_N, the remaining count is again Poisson with mean c_\nu s_N, and all the other counts are unchanged. Thus the remaining model has exactly the original reservoir law. The distinguished term becomes an independent new insertion with parameters t_\nu,u_\nu. Its score is g_0^{a_*}S_0^{a_*}/A^{a_*}. The updated tree density is (3.5), so the anchor factor A^{a_*} cancels. This proves

Equation (6.16) now follows from (6.13). In particular no type has been deleted from the law of the base reservoir. This proves the last assertion.□

Proof. Lemma 3.3 gives a complex neighborhood |t|,|u|<\rho on which the functions in (6.15) are analytic and uniformly bounded in N and in the selected parameter vector. Shrinking \rho gives a uniform bound on their u-derivatives as well. These constants may depend on the fixed tree, L, and \|f\|_\infty, but not on the type index j in the mark specification.

Each Taylor coefficient of H_N(t,0) is a finite linear combination of multioverlap moments and products of two such moments on prescribed trees. Their coefficients are determined by the fixed tree, exponents, mark law, and polynomial test, and are independent of N. Indeed the canceled anchor expansion supplies finitely many extensions at any fixed order; averaging the independent insertion site turns its spin product into a multioverlap. These coefficients converge by Lemma 6.2(iii). The uniform analytic bound then implies, by the geometric bound on the Taylor tails, that H_N(t,0) converges uniformly on each smaller disk to an analytic function H(t).

For every sufficiently large fixed j, the corresponding type and Lemma 6.3 give

Here the score error tends to zero with j fixed, and the same function H_N is used for every j, by Lemma 6.3. Hence |H(j^{-1})|\leq2Cj^{-j}. If the first nonzero Taylor coefficient of H had degree q, then |H(j^{-1})|\geq c j^{-q} for all sufficiently large j, a contradiction. Thus H vanishes identically near zero, proving the claim coefficient by coefficient.□

Proof. For k=0, the claim is the vanishing constant coefficient from Lemma 6.4, using constant marks. For k\ge1, we explain how to extract distinct colored marks. Fix rational-valued functions g_0,g_1,\ldots,g_k, all bounded by one and constructed jointly from the same finite collection of auxiliary marks. The mixed insertion uses A=1+\sum_{j=1}^kz_jg_j\sigma_i. Its mixed derivative in all z_j is the symmetric multilinear form obtained by polarizing the degree-k coefficient for a single g. More explicitly, if Q_N(g)=k![t^k]H_N(t,0), then the mixed derivative is

Every argument of Q_N is rational-valued and bounded by one, so each resulting pair (g,g_0) belongs to the fixed mark family. Lemma 6.4 makes the displayed mixed derivative tend to zero. The mixed derivative expansion is precisely the ordered extension rule: there is no additional factorial in its coefficients.

It remains to arrange that the expectation over the marks selects exactly the extensions satisfying \mathcal C. For a pair of colors a,b\in\{0,\ldots,k\} and a depth 1\leq d\leq L-1, the event that their split depth is at least d is the event that they share their vertex at depth d. Introduce a new independent Rademacher coordinate at that depth and give both g_a and g_b its factor. Its contribution to their joint mark expectation is 1 if the vertex is shared and 0 otherwise. For a finite collection of such requirements, use different independent coordinates for the different requirements and define each g_a as the product of its assigned factors. Then

All marks in this calculation are independent of the base reservoir.

Let H_d(a,b) denote the sharing indicator in (6.18), with H_0=1 and H_L=0 for distinct replica positions. These are positions in the sampled tree, even when their spin configurations happen to agree. Exact splitting at depth d is expressed by H_d-H_{d+1}, for 0\leq d\leq L-1. Products and finite linear combinations therefore select any prescribed consistent colored shape or collection of allowed shapes. For each term of this finite linear combination, the functions g_0,\ldots,g_k are products of signs and hence take values in \{-1,1\}. These functions and their polarization averages belong to the mark family fixed at the start of the section. Constant marks cover k=0.

Finally apply the mixed canceled-anchor expansion to the difference (6.15), average the marks using the selector, and average the independent uniform insertion site. The latter average is exactly R_E. Lemma 6.4 and polarization make the coefficient difference tend to zero, yielding (6.17). Finite linear combinations extend the conclusion from overlap monomials to the stated tests. The construction uses only marks through depth L-1: the extension rule never reuses the anchor or an already used color, so no test of coincidence at depth L is required.□

Proof. Conditional on \mathscr F_d and B, the squared contraction has expectation N^{-2}\sum_{ij}C_{ij}B_iB_j. Its absolute value is at most N^{-2}\sum_{ij}|C_{ij}|. Cauchy–Schwarz, first over i,j and then over the prefix, proves (7.6). For the second assertion, write \mu=\mathbb E[X\mid\mathscr G]. Conditional independence gives

since C is positive semidefinite.□

Proof. Keep the later branching depths of T fixed and sample a single path along its initial stem. On this path, \mu_{t,T} is a bounded vector martingale. Orthogonality of its increments gives

This proves the evaluation-depth assertion after summing over the ranged depth and dividing by L.

Consider a branching vertex at depth q with child shapes T_1,\ldots,T_s. Holding their later depths fixed, its original conditional mean is \prod_j \mu_{q,T_j}, with products understood coordinatewise. If the split is delayed to q+1, its conditional mean at the same prefix of depth q is \mathbb E[\prod_j \mu_{q+1,T_j}\mid\mathscr F_q], where the child means are evaluated on a common one-step continuation. Jensen’s inequality and the product difference inequality on [-1,1]^s yield

Summing over q uses (7.10) with each child shape fixed. Propagating a changed subtree mean towards an ancestral evaluation consists of conditional expectations and multiplication by factors bounded by one. Both operations contract this squared norm. Averaging over all other depth coordinates therefore proves the claimed C/L bound for one shift. For several shifts, change the vertices one at a time and use the squared triangle inequality with a factor equal to the number of shifts. Regularity ensures that the intermediate shapes have the same ancestry relations and, for large L, lie in the enlarged \eta/2-regular domain. All relevant one-prefix marginal laws are unchanged when other sampled branches are omitted, so these estimates hold in any larger sampled tree.□

Proof. We induct on the number k of leaves. The induction replaces each proper child by its conditional mean. It then applies the prescribed-tree identity to two copies with delayed branching depths; after summing the signed coefficients, this becomes a nonnegative three-copy estimate. To keep track of the depth averages, let

The maximum is over finitely many labeled topologies. Averages of any lower-order covariance used below, including averages with extra unused coordinates or shifted depths, are bounded by the appropriate V_{k-1,L}(\eta/2), using (7.2) when fractional powers occur.

One leaf. Take two old paths splitting at d, with path 1 a spin anchor, and add one color required to split from the anchor exactly at d. The available old path 2 has coefficient 1. A fresh path can split from both old paths at d, with coefficient -c_d, or follow path 2 and leave it at \ell>d, with coefficient -c_\ell, where

From the anchor alone the total coefficient is -\delta. Write X=R_{12} and X_\ell=R_{13} for the corresponding fresh extension. Each X_\ell has the marginal law of X, and \sum_{\ell=d}^{L-1}c_\ell=1+\delta. The prescribed-tree identity with f=X therefore gives

For \ell=d, the three spin vectors are conditionally independent below d. Hence (7.7) and c_d\ge\eta give v_N(S,d)\le\delta/\eta+o_N(1) at each fixed L,d. This proves V_{1,L}(\eta)\le\delta/\eta.

Shifted copies and their coefficients. Let |S|=k\ge2, its first split be e>d, and its proper child shapes be T_1,\ldots,T_s. Sample an old tree consisting of two copies of S, denoted I and II, whose stems split at d and whose internal depth assignments are aligned. Fix an old leaf in I as the spin anchor. Let S^+ be the topology S with every internal branching depth increased by one. In the prescribed-tree identity require the anchor and the added colors to form two copies of S^+, separated at d, with the anchor in its original labeled position in the first copy. These constraints involve only the anchor and the added colors. Add all other colors of side I first, then those of side II. Figure 1 illustrates one local shift.

Let \kappa(T) be the reference coefficient (3.13), and put

At each vertex the j=1 factor is -\delta; for j\ge2 its absolute value is at least \eta/2 for all sufficiently large L. If b=b(S), then

For large L, regularity ensures that each shifted depth differs from every branching depth of the old tree, including d. Thus these 2b target branching vertices must be created by fresh unary splits. Lemma 3.5 gives

The two copies have aligned depths but distinct branching vertices: each vertex supplies its own factor \delta. This is the reason for the shift. The full signed coefficient has an additional factor -\delta from separation at d; we divide by J and leave that factor in the identity. Equation (7.20) then controls every projection error after division.

Projecting the two target sides. In every extension, the marginal target tree consists of two ordinary copies of S^+, independent below their separation at d. By (7.13) its multioverlap differs in L^2 from the contraction of its projected means at e+1 by at most 2p_N(S^+,e+1). Change the proper child depths back by one, then change their evaluation depth from e+1 to e. The product difference inequality and Lemma 7.3 show that this adds an error at most h_N(S) in L^2, with

One can take h_N(S) to be the sum of the finitely many L^2(\|\cdot\|_N) distances in these comparisons, multiplied by a size-dependent constant. This definition depends only on the single-copy marginal shapes, not on the particular extension. Thus (7.21) holds uniformly for the comparisons in the extension sum, even though the union of the old and target trees itself need not have regular depths.

Let a,b denote the vectors a_{S,e} on the old stems I and II. The target stem in I shares the old prefix through e because it contains the anchor, so its final projected vector is a.

The signed extension sum. Set f to be the overlap of all 2k old leaves, an allowed fixed overlap monomial. All target-I additions stay in the anchor’s branch below d, so they leave the old-II stem and its child counts unchanged. Classify the first added path of target side II by its prefix through e. It may diverge freshly at \ell=d, with coefficient -c_d, or follow the old II stem and diverge at d<\ell<e, with coefficient -c_\ell=-\delta. In such a class let b_\ell be a_{S,e} on the new stem; it shares the old II prefix through \ell. At \ell=d the stems carrying a,b,b_d are conditionally independent below d. Every remaining possibility follows the old II prefix through e and has final projected vector b. All later target paths in side II follow its first path through e, since their earliest split is e+1.

For a fixed extension history, retain every old path and the first target-II prefix through e, and delete all other new branches. The target-I projection a already depends only on the retained old anchor prefix. Each deleted subtree integrates to one under its probability kernels; a reused old leaf introduces no new variable. The retained tree depends only on the class: it is the old tree with a fresh stem attached at \ell<e, or just the old tree in the remaining class. The history is a combinatorial choice, not a condition on sampled values. Thus the joint marginal of the old paths and projected prefixes is fixed within each class. In particular, the expectation of f times the projected overlap is constant within a class and can be multiplied by its total signed coefficient.

By Lemma 3.4, summing later side-II colors backwards gives \kappa(S^+) for each first-path choice. Summing the side-I choices gives the other factor \kappa(S^+). The fresh class at \ell therefore has total coefficient -c_\ell J. The total coefficient is -\delta J, both from the old tree and from the anchor alone. Since

the remaining prefix-through-e class has coefficient m_eJ. Thus the projected terms have the following coefficients:

Multiply the projected overlap in each row by f and divide the prescribed-tree identity by J. Rearranging gives

where R_{\mathrm{target}} on the right is the target overlap in the anchor-alone extension. Its absolute value is at most one. The error satisfies

Indeed, multiplying a projection error by f, even when correlated with it, costs at most its L^2 norm since |f|\le1. Sum these errors with absolute coefficients and apply (7.20). The final term includes division of the original identity error by J and tends to zero at fixed L.

Closing the induction. Equation (7.13) gives \|f-a\cdot b\|_{L^2}\le2p_N(S,e). Moreover \sum_{\ell=d}^{e-1}c_\ell=(e+1)\delta\le1. Replacing f by a\cdot b on the left of (7.22) therefore costs at most 4p_N(S,e). Each a\cdot b_\ell has the same marginal law as a\cdot b, so that left side becomes

Its summands are nonnegative and c_d\ge\eta. The right side of (7.22) is bounded in absolute value by 2\delta+|\rho_N(S,d)|. Hence

Sample three copies of A_S conditionally independently below d. Projecting each of the two contractions involving the first copy changes it in L^2 by at most 2p_N(S,e). Using (7.7), (7.24), and p_N(S,e)\le k, we obtain

Each child in either p_N has fewer than k leaves. To make the averaging step explicit, the aligned construction has D=b(S)+1 distinct depth coordinates, including d and e. A term belonging to T_j uses only D_j=b(T_j)+1 coordinates. For the shifted term these are \pi_j(\mathbf q)=(e+1,(q_v+1)_{v\in\operatorname{Br}(T_j)}). Every retained assignment has at most L^{D-D_j} preimages, and its coordinates are \eta/2-regular for large L. If w_j is the child covariance as a function of these coordinates, then, for 0<\gamma\le1,

The unshifted term has the same bound without translating the coordinates. Thus the two aligned copies use single-copy estimates; there is no restriction of an independently averaged pair of copies to a diagonal. Taking \gamma=1/4 and then \limsup_N, and using (7.21) and (7.3), gives, for sufficiently large L,

The maximum over smaller topologies in (7.15) can be absorbed in the right side because these covariances are bounded by one. The base case and induction now imply V_{k,L}(\eta)\to0 for every fixed k,\eta, proving the proposition.□

Proof of Theorem 7.1. For a singleton, use the spin-anchor identity with no added colors and f=R_S. It gives \mathbb ER_S^2=(\mathbb ER_S)^2+o_N(1).

Suppose S first splits at e and has proper child shapes T_1,\ldots,T_s. We will condition one step before e. Use S as the old tree, designate one of its leaves as a marker anchor, and add a full copy of S all of whose leaves split from the anchor at e-1. Its first path must be fresh at e-1, because the old tree has not yet branched there. All other target paths lie in the resulting fresh subtree. The extension coefficient on both sides of the prescribed-tree identity is the same nonzero number

The target and old copies are conditionally independent and identically distributed below \mathscr F_{e-1}. With f=R_S and M=\mathbb E[R_S\mid\mathscr F_{e-1}], their product has conditional expectation M^2. On the anchor-alone side, deleting the marker’s continuation below e-1 integrates a probability kernel to one and leaves the ordinary target law S, with mean \mathbb E R_S. The identity therefore gives

and hence

Division by C(S,e) is made only at fixed L; no uniform lower bound as L\to\infty is needed.

It remains to control the conditional variance below this prefix. The child covariances are evaluated at e, which is separated from all their branching depths; the move to e-1 will use martingale continuity instead. Set

The latter is \mathscr F_{e-1}-measurable. By (7.13), \mathbb E(R_S-G)^2\le p_N(S,e)^2. Keeping all proper child depths fixed, the product difference inequality and (7.10) imply

Here e is itself a ranged coordinate, so the one-step increments are summed before division by L. Since conditional expectation is the optimal L^2 projection,

Variance decomposition and (7.30) now show

In this estimate we used p_N(S,e)^2\le s\sum_jv_N(T_j,e)^{1/2} and (7.26) with \gamma=1/2: here the full average has D=b(S) coordinates because d is absent, while still D_j=b(T_j)+1. Proposition 7.4 finishes the proof.□

Proof. Include an independent uniform site i\in[N] in the root variable, along with the reservoir root disorder. Sample the tilted reservoir auxiliary kernels along each path, and let \mathscr G_d be the sigma-field generated by this enlarged root and the full auxiliary prefix through depth d. At depth r=L-1 put

where the brackets denote the leaf Gibbs expectation. This is finite: at finite N all configuration weights are strictly positive, so -1<\angles{\sigma_i}<1. Thus x is determined at depth r, before the terminal spin transition at depth L. At each terminal replica leaf, draw a spin with law q_x. Given the auxiliary prefix, these spins are independent and have exactly the one-site law of the independent terminal Gibbs replicas.

Define the random measures backward by

Then \eta_d\in\mathcal M_{r-d}, so \zeta_{L,N}=\operatorname{Law}(\eta_0)\in\mathcal M_L. All state spaces are standard Borel, so these conditional probability kernels have measurable versions. The auxiliary priors used here may be taken to be finite products of finite mark spaces at each realized root; hence the same assertion also follows directly by finite sums conditional on the root counts.

Here is an explicit verification for every branching pattern. Fix a descendant tree T and prescribe a spin e_a at each terminal leaf. At depth r, its conditional probability is G_T(x)=\prod_a q_x(e_a). At depth d<r, let T_1,\ldots,T_j be the subtrees rooted at its children. Conditional independence of children gives the backward recursion

By induction, this probability depends on the full prefix only through \eta_d. Thus the nested measures preserve the joint output law of every descendant tree, including unary stretches and arbitrary numbers of children. This recursion is precisely the branching version of (2.7). Taking \zeta_{L,N}=\operatorname{Law}(\eta_0) preserves the root mixture as well. In particular, for every subset S of the leaves,

Use independent copies of the entire construction, including the reservoir root and uniform site, for different labels. The resulting messages are independent of the new physical disorder in the cavity insertions.□

Proof. Conditional on the sampled reservoir configurations, the pattern \boldsymbol\sigma_i=(\sigma_i^1,\ldots,\sigma_i^k) at a uniform site has empirical distribution

The trial-label distribution is \bar\pi=\E\pi by (8.2). Independent uniform sampling with replacement gives \pi^{\otimes a} conditionally in the reservoir; the trial distribution is \bar\pi^{\otimes a}. The elementary telescoping bound for product measures gives

Integrating a function bounded by one costs at most twice total variation. Conditioning on the independent insertion disorder proves the last assertion.□

Proof. For each insertion in Lemma 5.1, replace the reservoir spins at its site labels by independent spin processes from Lemma 8.1. Denote the resulting trial insertions by \widetilde A_{\rm s} and \widetilde A_{\rm b}, and their recursions from (3.3) by \widetilde Y_{0,\rm s} and \widetilde Y_{0,\rm b}. These recursions use the trial kernels.

At the terminal spin transition, averaging \widetilde A_{\rm s} over its independent trial spins gives exactly V_{\rm s} in (2.8); hence \widetilde Y_{0,\rm s}=T_0V_{\rm s}. For \widetilde A_{\rm b} the same transition gives a product of K_{\rm b} edge factors with disjoint message labels. Given the physical disorder and all message prefixes at a depth, these label groups remain independent. Their product therefore factors through each conditional power mean, successively from the last level to the first. Consequently,

By (5.5), it remains to compare the reservoir and trial insertion logarithms in the stated limits.

Consider either insertion and first restrict its Poisson count K to K\le M, where M is fixed. Set C=H+BM, z=\cosh C, and c=\tanh C<1. On this event both the reservoir insertion and its trial version can be written as A=z(1+D) with |D|\le c, uniformly in all disorder and path variables. The deterministic term \log z cancels in the comparison.

At each order k of Lemma 3.2, the product of the k copies of D is a bounded function of replica-spin patterns at at most pM labels and of independent insertion disorder. By Lemma 8.2, its evaluation error on a fixed tree is bounded by pM\sum_{S\ne\varnothing}\E|R_S-\E R_S|. Hence (8.4) makes its tree-averaged error tend to zero in the ordered limits. For every fixed M, truncating the expansion after q terms leaves an error at most \sum_{k>q}c^k/k on either side, uniformly in N,L.

Outside the count cutoff the original insertion logarithms, on both sides, are bounded by H+BK. Their expected contribution is therefore at most 2\E[(H+BK)\mathbf1_{\{K>M\}}], which tends to zero as M\to\infty. This proves convergence of the expected insertion logarithms: explicitly, first choose M to control the Poisson tail, then q to control the geometric tail, and then take the limits in N and L for the finitely many remaining expansion terms. Together with the trial identities above and (5.5), this proves (8.6).□

Proof. Write A=\inf_{r\ge0}\Phi_r, which is finite by (2.12). Each encoded trial value is at least A, so (8.1) gives, at every fixed L,

The inner limit uses that depth’s selected sequence. Letting L\to\infty in Proposition 8.3 gives A\le\underline F+2\eps, and then \eps\downarrow0 proves the result.□

Proof. Use the same counts and indices in the two Hamiltonians. Their pointwise log-weight difference is bounded by the sum of the interaction sup-norm differences and field differences. The logarithm of the partition function preserves this bound, which gives (9.1). Each cavity interaction changes by at most the corresponding sup-norm interaction difference, and so does each edge logarithm. The power means preserve these root-measurable bounds. The site term has mean \alpha p interactions and the edge term has coefficient \alpha(p-1), giving (9.2).

For (9.3), the physical constants factor out of the spin partition function and of every power mean. In the functional, the site term shifts by -\alpha p\E c and the edge term contributes +\alpha(p-1)\E c, for a net shift -\alpha\E c.□

Proof of Theorem 2.1. The multiplier a may depend asymmetrically on the labeled input functions, so the original interaction law need not be permutation invariant. We first remove this multiplier by an integrable scalar shift. Set c=\theta(1,\ldots,1) and \widehat\theta=\theta-c. The constant is integrable, since |c|\le B(\theta). The factorization gives

The multiplier a has disappeared. Independence and identical distribution of the f_\ell, and their independence of b, show that the law of \widehat\theta is invariant under permutations of its inputs. Moreover \E B(\widehat\theta)\le2\E B(\theta)<\infty.

For K>0, truncate each entry of \widehat\theta to [-K,K] and truncate h to [-K,K], obtaining \widehat\theta^{(K)},h^{(K)}. Permutation invariance is preserved. The bounded-law lower bound Corollary 8.4 applies whether or not truncation preserves the factorization. By dominated convergence,

Write \widehat I for the infimum of the normalized trial functional over all depths and trial laws, and I_K for the same infimum with the truncated physical laws. The uniform trial estimate gives

The pressure estimate and Corollary 8.4 now imply

Letting K\to\infty proves \liminf_N\widehat F_N\ge\widehat I=\inf_r\widehat\Phi_r. Undoing the constant shift gives \liminf_NF_N\ge\inf_r\Phi_r. Finally Proposition 4.1 gives \limsup_NF_N\le\inf_r\Phi_r. Both limits agree, proving existence and (2.13).□

Proof. Use

The functions f_\ell are deterministic independent copies, and |b|<1 almost surely. Symmetry makes every odd moment of b zero; the even moments are nonnegative. Finally, B(\theta_\beta)=\beta|J| and |h_\beta|=\beta|H|. Thus all hypotheses of Theorem 2.1 hold.□

Proof. The product I_\varepsilon(s)=\prod_\ell(1+\varepsilon_\ell s_\ell)/2 takes values in \{0,1\} and indicates a violated clause. Therefore

Take a=1, b=e^{-\beta W}-1, and f_\ell(s)=(1+\varepsilon_\ell s)/2. The functions are independent copies and independent of b. Since 0\le-b<1, the strict product condition and every positivity inequality hold. Moreover, B(\theta_\beta)=\beta W, so Theorem 2.1 applies.□

Proof. Write g_N=N^{-1}\E\max_\sigma\mathcal E_N(\sigma) and P_N(\beta)=N^{-1}\E\log Z_N(\beta). The first-moment assumptions make g_N finite and uniformly bounded. Since there are 2^N spin configurations,

For each fixed \beta>0, Theorem 2.1 gives P_N(\beta)\to I(\beta), where I(\beta)=\inf_{r,\zeta,\mathbf m}\cB_{r,\beta}(\zeta,\mathbf m). Hence

Letting \beta\to\infty proves that g_N converges to a limit g. Taking N\to\infty in the finite-volume bounds now gives g\le I(\beta)/\beta\le g+\log(2)/\beta, proving (10.1). In the satisfiability model, maximizing the negative violation count is the same as minimizing that count.□